基于WSN數(shù)據(jù)匯集應(yīng)用的汽車電子節(jié)點(diǎn)負(fù)載均衡算法研究

劉輝　趙磊　歐陽陳華

摘要：該文針對基于WSN數(shù)據(jù)匯集的汽車電子節(jié)點(diǎn)負(fù)載均衡問題提出了可以使負(fù)載分配均衡、延長網(wǎng)絡(luò)壽命的動態(tài)負(fù)載均衡算法，并對動態(tài)負(fù)載均衡算法的原理、各方面計(jì)算模型以及相關(guān)算法進(jìn)行了具體闡述，并進(jìn)一步驗(yàn)證了該算法的可行性和優(yōu)勢。

關(guān)鍵詞：WSN；數(shù)據(jù)匯集；汽車電子節(jié)點(diǎn)；負(fù)載均衡

中圖分類號：TP391 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2015）14-0211-02

WSN（無線傳感器網(wǎng)絡(luò)）當(dāng)前是一個最新研究熱點(diǎn)，具有大規(guī)模、自組織、功率消耗低、成本投入低等特點(diǎn)，在未來的網(wǎng)絡(luò)應(yīng)用有很廣闊的發(fā)展前景。無線傳感器網(wǎng)絡(luò)主要適用于環(huán)境監(jiān)測，例如 大氣、水質(zhì)監(jiān)測、深林防火一級智能交通等等領(lǐng)域。無線傳感器網(wǎng)絡(luò)的應(yīng)用過程中，傳感器把周期性獲取的環(huán)境數(shù)據(jù)不斷的匯集至Sink節(jié)點(diǎn)的相關(guān)應(yīng)用稱為數(shù)據(jù)匯集應(yīng)用。該應(yīng)用過程中，相關(guān)數(shù)據(jù)從多個節(jié)點(diǎn)以多跳的方式向Sink節(jié)點(diǎn)匯集，因?yàn)樯嫌喂?jié)點(diǎn)需要負(fù)責(zé)將數(shù)據(jù)轉(zhuǎn)發(fā)給下游節(jié)點(diǎn)的工作，因此上游節(jié)點(diǎn)比下游節(jié)點(diǎn)要承擔(dān)更大的負(fù)載，進(jìn)而形成漏斗效應(yīng)。如果數(shù)據(jù)流量分配過程中分支流量不均衡，上游節(jié)點(diǎn)就可能因?yàn)槌休d過大成為熱節(jié)點(diǎn)。節(jié)點(diǎn)負(fù)載過重會加快熱節(jié)點(diǎn)能量的消耗，縮短網(wǎng)絡(luò)的壽命，出現(xiàn)提前死亡現(xiàn)象。雖然針對WSN負(fù)載均衡的相關(guān)方法有很多，但整體效果都不太理想，本文基于WSN數(shù)據(jù)匯集應(yīng)用，提出了一種應(yīng)用于汽車電子系統(tǒng)節(jié)點(diǎn)的節(jié)點(diǎn)負(fù)載均衡新算法——動態(tài)負(fù)載均衡算法（DLB-DGA）。動態(tài)負(fù)載均衡算法把負(fù)載壓力消息由上游節(jié)點(diǎn)傳輸給下游節(jié)點(diǎn)，然后結(jié)合壓力消息由下游節(jié)點(diǎn)對父節(jié)點(diǎn)的流量進(jìn)行調(diào)整分配，盡可能使上游節(jié)點(diǎn)的負(fù)載均衡到達(dá)最大程度，進(jìn)而降低熱點(diǎn)負(fù)載，達(dá)到延長網(wǎng)絡(luò)壽命的目的。

1 動態(tài)負(fù)載均衡算法原理

WSN數(shù)據(jù)匯集中的節(jié)點(diǎn)除了Sink節(jié)點(diǎn)以外剩下的網(wǎng)絡(luò)節(jié)點(diǎn)都是數(shù)據(jù)源。網(wǎng)絡(luò)節(jié)點(diǎn)把采集到的信息數(shù)據(jù)都匯集至Sink節(jié)點(diǎn)，整個過程形成了一個多對一形式的網(wǎng)絡(luò)數(shù)據(jù)流。與Sink節(jié)點(diǎn)距離較近的內(nèi)層節(jié)點(diǎn)（又稱上游節(jié)點(diǎn)）相對距離較遠(yuǎn)的外層節(jié)點(diǎn)（（又稱下游節(jié)點(diǎn)））負(fù)載較重，這可以稱為一種漏斗效應(yīng)。

通過對WSN數(shù)據(jù)匯集的應(yīng)用特點(diǎn)的分析研究可得到以下定理和推論：

定理：上游節(jié)點(diǎn)負(fù)載的總和大于下游負(fù)載總和。定理證明：設(shè)定M為網(wǎng)絡(luò)總層數(shù)，i、j代表層次，且0

推論：Sink相鄰節(jié)點(diǎn)的負(fù)載總大于其他任何層次節(jié)點(diǎn)負(fù)載總和。推論證明：假設(shè)i層為Sink相鄰節(jié)點(diǎn)，i=1，因?yàn)槎ɡ?成立，所以1

通過鄰居發(fā)現(xiàn)以及廣播算法，WSN能夠讓每個節(jié)點(diǎn)清楚與Sink節(jié)點(diǎn)的層次關(guān)系，并且可以知道自己上跳節(jié)點(diǎn)的信息。Sink的非相鄰節(jié)點(diǎn)與Sink節(jié)點(diǎn)之間不能直接進(jìn)行通信，而必須通過父節(jié)點(diǎn)把數(shù)據(jù)信息轉(zhuǎn)發(fā)給Sink節(jié)點(diǎn)。一般情況下，每個WSN對應(yīng)的父節(jié)點(diǎn)有很多個，當(dāng)每個父節(jié)點(diǎn)的數(shù)據(jù)分配不合理時就會出現(xiàn)父節(jié)點(diǎn)或者上游節(jié)點(diǎn)負(fù)載不均衡的問題，負(fù)載過重的情況下很容易導(dǎo)致節(jié)點(diǎn)提前死亡，縮短網(wǎng)絡(luò)壽命。因此動態(tài)負(fù)載均衡算法的一個關(guān)鍵問題就是要如何讓上游節(jié)點(diǎn)負(fù)載得到最大程度的均衡。

動態(tài)負(fù)載均衡算法的基本思想：上游節(jié)點(diǎn)報給下游節(jié)點(diǎn)的上游節(jié)點(diǎn)數(shù)據(jù)轉(zhuǎn)發(fā)量經(jīng)過下游節(jié)點(diǎn)分析、處理之后，即對父節(jié)點(diǎn)的數(shù)據(jù)流量進(jìn)行動態(tài)調(diào)整，進(jìn)而使上游節(jié)點(diǎn)的負(fù)載到達(dá)最佳均衡狀態(tài)。

可以用節(jié)點(diǎn)的數(shù)據(jù)傳輸壓力來形象定義上游節(jié)點(diǎn)數(shù)據(jù)轉(zhuǎn)發(fā)量情況，可以簡稱為壓力，數(shù)據(jù)傳輸壓力的方向和數(shù)據(jù)流方向是相反的。首先提出壓力計(jì)算模型，節(jié)點(diǎn)通過該計(jì)算模型計(jì)算出對下游節(jié)點(diǎn)施加的壓力，并把計(jì)算結(jié)果通過一定方式匯報給下游節(jié)點(diǎn)。上游節(jié)點(diǎn)的負(fù)載情況通過壓力來反映，隨著上游節(jié)點(diǎn)轉(zhuǎn)發(fā)情況的變化，壓力值也不斷變化，如果上游的數(shù)據(jù)量大，壓力值就大。子節(jié)點(diǎn)通過流量均衡計(jì)算模型對父節(jié)點(diǎn)的壓力差進(jìn)行均衡分配，得到父節(jié)點(diǎn)流量分配比例表，最后子節(jié)點(diǎn)根據(jù)父節(jié)點(diǎn)流量分配比例表來進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)。該應(yīng)用過程屬于一個動態(tài)反饋過程，最終使得上游節(jié)點(diǎn)的負(fù)載達(dá)到最佳均衡狀態(tài)。

2 動態(tài)負(fù)載均衡算法解析

2.1動態(tài)負(fù)載均衡算法中的壓力計(jì)算模型

對動態(tài)負(fù)載均衡算法原理進(jìn)行分析可以得出數(shù)據(jù)轉(zhuǎn)發(fā)情況是決定壓力值的關(guān)鍵性因素，所以壓力與數(shù)據(jù)轉(zhuǎn)發(fā)量之間成正比關(guān)系。從定理1中的漏斗效應(yīng)中上游節(jié)點(diǎn)負(fù)載的總和大于下游負(fù)載總和以及節(jié)點(diǎn)的網(wǎng)絡(luò)層次關(guān)系可以發(fā)現(xiàn)，低層次的壓力貢獻(xiàn)相對于高層次要大，此時就可以對壓力進(jìn)行量化性定義。節(jié)點(diǎn)i（i取任意值）轉(zhuǎn)發(fā)數(shù)據(jù)形成的壓力表示如下：[p（i）=f（i）2h（i）-1] （ p（i）表示產(chǎn)生的壓力，f（i）表示數(shù)據(jù)傳輸量， h（i）表示層次跳數(shù)）。

2.3動態(tài)負(fù)載均衡算法步驟

為了實(shí)現(xiàn)網(wǎng)絡(luò)負(fù)載的動態(tài)均衡，在該算法中定義出3個以廣播方式傳輸?shù)南⒅噶睢Ｖ噶?由Sink節(jié)點(diǎn)發(fā)出，主要為了發(fā)現(xiàn)節(jié)點(diǎn)層次，讓節(jié)點(diǎn)知道與Sink節(jié)點(diǎn)的層次關(guān)系，并建立父子列表。指令2用于子節(jié)點(diǎn)對父節(jié)點(diǎn)的節(jié)點(diǎn)流量報告，如果有數(shù)據(jù)需要傳輸給父節(jié)點(diǎn)時，指令2可以在數(shù)據(jù)上傳過程中稍到。指令3是父節(jié)點(diǎn)匯報子節(jié)點(diǎn)壓力。動態(tài)負(fù)載均衡算法步驟主要步驟如下：

第一，Sink節(jié)點(diǎn)發(fā)出指令1，網(wǎng)絡(luò)節(jié)點(diǎn)收到指令1后通過廣播算法發(fā)現(xiàn)層次，獲取每個節(jié)點(diǎn)與Sink節(jié)點(diǎn)的層次關(guān)系，并建立父子節(jié)點(diǎn)列表。節(jié)點(diǎn)沒有初始化的情況下初始化父節(jié)點(diǎn)壓力為零，對父節(jié)點(diǎn)進(jìn)行流量平均分配，然后進(jìn)行采集和傳輸數(shù)據(jù)。

第二，父節(jié)點(diǎn)的壓力處于均衡狀態(tài)時可以依據(jù)當(dāng)前父節(jié)點(diǎn)流量表的比例進(jìn)行數(shù)據(jù)傳輸，如果不均衡就需要執(zhí)行第四步操作。

第三，如果有子節(jié)點(diǎn)存在，需要結(jié)合公式[p父（i）=p父（i）m父（i）+f父+fi2h（i）-1]來計(jì)算子節(jié)點(diǎn)壓力，當(dāng)壓力值變化時需要通過指令3來告知子節(jié)點(diǎn)，然后返回第二步驟。

第四，根據(jù)流量計(jì)算模型的相關(guān)公式對新的父節(jié)點(diǎn)流量表進(jìn)行計(jì)算，并通過指令2把新的流量信息通告給父節(jié)點(diǎn)，之后返回第三步驟。

利用TOSSIM進(jìn)行仿真實(shí)驗(yàn)，實(shí)驗(yàn)中對動態(tài)負(fù)載均衡算法與動態(tài)負(fù)載平衡樹方法、靜態(tài)負(fù)載平衡樹方法、最短路徑樹方法等節(jié)點(diǎn)負(fù)載均衡算法進(jìn)行對比發(fā)現(xiàn)，動態(tài)負(fù)載均衡算法有可行性，并且相比其它算法表現(xiàn)出更優(yōu)越的效果。

3 結(jié)束語

文章針對用于汽車電子系統(tǒng)的WSN數(shù)據(jù)匯集應(yīng)用中負(fù)載分配不均衡的問題提出了動態(tài)動態(tài)負(fù)載均衡算法（DLB-DGA），該算法可以有效解決節(jié)點(diǎn)負(fù)載不均衡導(dǎo)致的早死現(xiàn)象，延長了網(wǎng)絡(luò)壽命。而且動態(tài)負(fù)載均衡算法的應(yīng)用環(huán)境要求低，實(shí)用性強(qiáng)，應(yīng)用過程中不需要其他手段支持。由于該算法的實(shí)現(xiàn)是在一定假設(shè)條件下進(jìn)行的，所以要需要進(jìn)一步探究、完善。

參考文獻(xiàn)：

[1] 陳志濤. 淺談無線傳感器網(wǎng)絡(luò)研究現(xiàn)狀與應(yīng)用[J]. 計(jì)算機(jī)光盤軟件與應(yīng)用. 2012（09） .

[2] 何麗莉，孫冰怡，姜宇，等. 基于ZigBee的無線傳感器網(wǎng)絡(luò)管理系統(tǒng)架構(gòu)設(shè)計(jì)[J]. 吉林大學(xué)學(xué)報：理學(xué)版， 2012（04） .

[3] 邢唱白. 淺談基于MSP430和nRF905的無線傳感器網(wǎng)絡(luò)設(shè)計(jì)[J]. 科技信息， 2012（23）.

[4] 梁毓明，張振利. 井下無線傳感器網(wǎng)絡(luò)網(wǎng)關(guān)節(jié)點(diǎn)的設(shè)計(jì)[J]. 金屬礦山， 2012（07） .

[5] 李琦，張坤，李旭東. 熱網(wǎng)遠(yuǎn)程監(jiān)控中的無線傳感器網(wǎng)絡(luò)硬件設(shè)計(jì)與實(shí)現(xiàn)[J]. 化工自動化及儀表. 2012（07） .

[6] 潘紹明，羅功坤，勞有蘭. 基于無線傳感器網(wǎng)絡(luò)的RFID系統(tǒng)[J]. 儀表技術(shù)與傳感器，2012（06）.

[7] 彭鑫. 車載自組網(wǎng)節(jié)點(diǎn)定位及頻譜分配策略研究[D].湖南大學(xué)， 2011 .

[8] Perillo M，Zhao C，Heinzelman W.On the problem of unbalancedload distribution in wireless sensor networks[C]//Globe ComWorkshops 2004.[S.l.]：IEEE，2004：74-79.

[9] 張重慶，李明祿，伍民友.數(shù)據(jù)收集傳感器網(wǎng)絡(luò)的負(fù)載平衡網(wǎng)絡(luò)構(gòu)建方法[J].軟件學(xué)報， 2007，18（5）：1110-1121.