基于路由算法均衡物聯(lián)網(wǎng)傳感器節(jié)點(diǎn)能耗的分析研究

孟鳳嬌+鐘志軍+蔡玉俊+張華東

摘 要：在基于無(wú)線傳感器建立的物聯(lián)網(wǎng)中，節(jié)點(diǎn)能耗不均會(huì)減少整個(gè)網(wǎng)絡(luò)的生命周期。因此，文章對(duì)物聯(lián)網(wǎng)中無(wú)線傳感器節(jié)點(diǎn)的能量消耗進(jìn)行了分析，提出了基于Dijkstra路由算法的能量均衡策略，該策略的節(jié)點(diǎn)間無(wú)線能量傳輸可以互補(bǔ)，并給出了如何動(dòng)態(tài)選擇核心節(jié)點(diǎn)和求解最佳能量的傳輸路徑，以最優(yōu)化使用節(jié)點(diǎn)的能量，從而延長(zhǎng)了整個(gè)網(wǎng)絡(luò)的壽命。

關(guān)鍵詞：能耗；能量均衡；路由算法；網(wǎng)絡(luò)生存時(shí)間

中圖分類(lèi)號(hào)：TP312 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2095-1302（2016）06-00-03

0 引 言

物聯(lián)網(wǎng)中的傳感器節(jié)點(diǎn)是物聯(lián)網(wǎng)的基礎(chǔ)單元，這些傳感器節(jié)點(diǎn)一般都只有有限的能源，很難從外界主動(dòng)獲取額外的能量，節(jié)點(diǎn)之間對(duì)能量的消耗也存在較大差異。工作一段時(shí)間后，由于節(jié)點(diǎn)間的能耗不均勻，網(wǎng)絡(luò)中核心耗能的節(jié)點(diǎn)容易過(guò)早死亡，從而導(dǎo)致整個(gè)物聯(lián)網(wǎng)絡(luò)的癱換。因此，在電池研究比較滯后的今天，物聯(lián)網(wǎng)中傳感器節(jié)點(diǎn)對(duì)整體能量均勻合理的使用，已成為物聯(lián)網(wǎng)研究中的一個(gè)關(guān)鍵問(wèn)題。本文重點(diǎn)研究了基于Dijkstra路由算法的物聯(lián)網(wǎng)節(jié)點(diǎn)間能耗均衡策略，以合理利用物聯(lián)網(wǎng)絡(luò)總體的有限能量，從而實(shí)現(xiàn)整個(gè)物聯(lián)網(wǎng)絡(luò)耗能的均衡。

1 物聯(lián)網(wǎng)中存在能耗的分析

物聯(lián)網(wǎng)中傳感器節(jié)點(diǎn)的能量主要由傳感元件、無(wú)線通信芯片和微型處理器消耗。2002年，Deborah Estrin在Mobicom國(guó)際會(huì)議上指出，物聯(lián)網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)1 b數(shù)據(jù)傳輸100 m消耗的能量，相當(dāng)于處理3 000個(gè)機(jī)器指令所消耗的能量。無(wú)線傳感器網(wǎng)絡(luò)體系結(jié)構(gòu)如圖1所示。

從無(wú)線傳感器網(wǎng)絡(luò)體系結(jié)構(gòu)可以看出，物聯(lián)網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)承擔(dān)著通信任務(wù)，并且還需轉(zhuǎn)發(fā)來(lái)自周?chē)渌?jié)點(diǎn)的數(shù)據(jù)，因此可以看出，傳感器節(jié)點(diǎn)的數(shù)據(jù)通信在整個(gè)物聯(lián)網(wǎng)路中的能耗最大。

在傳感器節(jié)點(diǎn)進(jìn)行無(wú)線通信的過(guò)程中，發(fā)送數(shù)據(jù)、接受數(shù)據(jù)、空閑偵聽(tīng)以及沖突重傳、串音等情況均有可能導(dǎo)致整個(gè)網(wǎng)絡(luò)的能量被浪費(fèi)。其中，源節(jié)點(diǎn)到基站路徑選擇的路由協(xié)議有以下兩方面的使命：

（1）在物聯(lián)網(wǎng)源節(jié)點(diǎn)和基站之間尋找最佳通信鏈路；

（2）保證將報(bào)文準(zhǔn)確完整地傳送到基站。

物聯(lián)網(wǎng)絡(luò)中的路由協(xié)議應(yīng)能降低和避免選擇剩余能量低的節(jié)點(diǎn)或重復(fù)節(jié)點(diǎn)作為通信鏈路的節(jié)點(diǎn)，從而使整個(gè)物聯(lián)網(wǎng)絡(luò)中的能量消耗盡量達(dá)到均衡。

GEAR路由的核心算法是一個(gè)局部最優(yōu)算法，基于物聯(lián)網(wǎng)節(jié)點(diǎn)的位置信息，運(yùn)用在己知局部拓?fù)浣Y(jié)構(gòu)上，建立匯聚節(jié)點(diǎn)到該節(jié)點(diǎn)的最優(yōu)路徑，這樣可以有效降低路由建立的耗能。但是該方法對(duì)完整的拓?fù)浣Y(jié)構(gòu)依賴性較強(qiáng)，如果拓?fù)浣Y(jié)構(gòu)未知，則會(huì)導(dǎo)致路由空白，從而降低路由效率。

美國(guó)麻省理工學(xué)院的學(xué)者設(shè)計(jì)出了無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)間數(shù)據(jù)通信的路由協(xié)議LEACH，該協(xié)議是首個(gè)層次型、低功耗的路由協(xié)議，改善了傳統(tǒng)平面路由協(xié)議占用存儲(chǔ)空間較多、路由表項(xiàng)過(guò)大等缺陷。但其也存在一些問(wèn)題，例如在選取物聯(lián)網(wǎng)絡(luò)簇頭時(shí)，忽略了節(jié)點(diǎn)的剩余能量，若將剩余能量低的節(jié)點(diǎn)作為簇頭節(jié)點(diǎn)時(shí)，該節(jié)點(diǎn)會(huì)因過(guò)早達(dá)到能量最小閾值而導(dǎo)致節(jié)點(diǎn)失效，從而致使整個(gè)物聯(lián)網(wǎng)絡(luò)的生存周期大大減少。另外，LEACH協(xié)議的簇頭選取策略是隨機(jī)的，在能量有限的物聯(lián)網(wǎng)絡(luò)中是不可取的。

當(dāng)網(wǎng)絡(luò)運(yùn)行處于數(shù)據(jù)傳輸階段時(shí)，核心節(jié)點(diǎn)能量消耗過(guò)大，容易過(guò)早死亡。有些節(jié)點(diǎn)由于電量不足而失效，這些都凸顯出在物聯(lián)網(wǎng)絡(luò)能量受限時(shí)，保證傳感節(jié)點(diǎn)能量消耗均衡對(duì)物聯(lián)網(wǎng)絡(luò)生命周期的影響。傳統(tǒng)的網(wǎng)絡(luò)層分簇路由協(xié)議通常采用各種改進(jìn)算法來(lái)均衡或減少網(wǎng)絡(luò)中各節(jié)點(diǎn)的能耗，以延長(zhǎng)整個(gè)網(wǎng)絡(luò)的生存時(shí)間，最終實(shí)現(xiàn)整個(gè)網(wǎng)絡(luò)的能耗均衡。

本文提出了基于Dijkstra路由算法的能量均衡策略。MatLab仿真實(shí)驗(yàn)表明，當(dāng)核心節(jié)點(diǎn)能量低于設(shè)定值時(shí)，通過(guò)能量無(wú)線傳輸來(lái)為核心節(jié)點(diǎn)補(bǔ)充能量，從而實(shí)現(xiàn)整個(gè)物聯(lián)網(wǎng)絡(luò)中的能耗均衡。

2 基于路由算法動(dòng)態(tài)計(jì)算剩余能量的策略

參考已有的物聯(lián)網(wǎng)能量均衡策略，考慮到在無(wú)線傳輸中能量消耗最大，因此主要解決傳輸過(guò)程中的能量均衡路由算法，其主要設(shè)計(jì)思想是每次傳輸前先動(dòng)態(tài)計(jì)算各傳感器節(jié)點(diǎn)的剩余能量，然后基于剩余能量級(jí)別進(jìn)行傳輸。在數(shù)據(jù)傳輸階段，檢測(cè)到該節(jié)點(diǎn)能量低于預(yù)設(shè)的臨界能量值（設(shè)為T(mén)E_MIN）時(shí)，以半徑r廣播能量獲取的報(bào)文。接收到報(bào)文節(jié)點(diǎn)則返回本節(jié)點(diǎn)ID、剩余能量和節(jié)點(diǎn)間距離等信息。之后該節(jié)點(diǎn)通過(guò)計(jì)算能量傳輸效率和傳輸距離，選出能量發(fā)射節(jié)點(diǎn)和中繼節(jié)點(diǎn)，最終建立一條能量傳輸通道路由。通過(guò)無(wú)線能量傳輸技術(shù)完成節(jié)點(diǎn)間的能量傳輸。從而實(shí)現(xiàn)了物聯(lián)網(wǎng)絡(luò)中節(jié)點(diǎn)能量過(guò)低時(shí)，能量高的節(jié)點(diǎn)可以向該節(jié)點(diǎn)傳輸能量的目的，避免了網(wǎng)絡(luò)中耗能節(jié)點(diǎn)過(guò)早的死亡，進(jìn)而延長(zhǎng)了整個(gè)網(wǎng)絡(luò)的生存周期。

算法設(shè)計(jì)具體過(guò)程如下：

（1）發(fā)送能量傳輸請(qǐng)求報(bào)文。報(bào)文格式如下：

（2）接受能量傳輸應(yīng)答報(bào)文。節(jié)點(diǎn)接收到廣播的報(bào)文后，首先判斷是數(shù)據(jù)報(bào)文還是能量傳輸報(bào)文。如果是數(shù)據(jù)轉(zhuǎn)發(fā)報(bào)文，按路由協(xié)議進(jìn)行轉(zhuǎn)發(fā)，如果是能量傳輸報(bào)文，首先檢測(cè)自身是否是核心節(jié)點(diǎn)，如果是，直接丟棄報(bào)文；如果不是，則計(jì)算剩余能量是否滿足要求。如果不滿足要求，則直接丟棄報(bào)文；如果滿足則向請(qǐng)求節(jié)點(diǎn)返回應(yīng)答報(bào)文。其判斷的分支圖如圖2所示。

應(yīng)答報(bào)文有節(jié)點(diǎn)ID、節(jié)點(diǎn)類(lèi)型、報(bào)文類(lèi)型、節(jié)點(diǎn)間距離、節(jié)點(diǎn)剩余能量幾個(gè)字段。

（3）選擇能量發(fā)射節(jié)點(diǎn)Wz。請(qǐng)求能量傳輸?shù)墓?jié)點(diǎn)收到返回的報(bào)文后，需要根據(jù)報(bào)文的信息，計(jì)算出能量傳輸?shù)男省Ｄ芰吭诳諝庵袀鬏?，像光和聲音一樣?huì)出現(xiàn)衰竭，因此效率與距離成反比，但效率與兩個(gè)節(jié)點(diǎn)間的能量差成正比。因此能量發(fā)射結(jié)點(diǎn)Ni的選取函數(shù)定義為：

Ni =Nsel （MAX（Eri/Li2））

其中，Li為接收節(jié)點(diǎn)到發(fā)射節(jié)點(diǎn)Ni的距離，Eri為節(jié)點(diǎn)在某個(gè)時(shí)刻的剩余能量，且Li

（4）選擇能量傳輸中繼節(jié)點(diǎn)。能量傳輸?shù)膬蓚€(gè)節(jié)點(diǎn)間的距離越遠(yuǎn)，能量損失越多，并且直接從能量的發(fā)射節(jié)點(diǎn)傳輸能量到能量的接收節(jié)點(diǎn)，會(huì)使發(fā)射節(jié)點(diǎn)的能量急劇下降，造成發(fā)射節(jié)點(diǎn)的過(guò)早死亡。這里使用Dijkstra最短路徑算法，節(jié)點(diǎn)間的能量傳輸效率作為權(quán)值，選出能量損耗最小的傳輸路徑。選出傳輸路徑之后，傳輸路徑的節(jié)點(diǎn)作為能量傳輸?shù)闹欣^節(jié)點(diǎn)。

（5）建立節(jié)點(diǎn)間能量傳輸鏈路。找到物聯(lián)網(wǎng)中的能量發(fā)射節(jié)點(diǎn)及能量傳輸路徑上的能量中繼節(jié)點(diǎn)，就可以在能量請(qǐng)求節(jié)點(diǎn)和能量發(fā)射節(jié)點(diǎn)之間建立一條能量傳輸鏈路。中繼節(jié)點(diǎn)收到能量后，按能量轉(zhuǎn)發(fā)報(bào)文將一定的能量傳輸?shù)较乱恢欣^節(jié)點(diǎn)，同時(shí)轉(zhuǎn)發(fā)能量轉(zhuǎn)發(fā)報(bào)文，直到能量傳輸?shù)侥芰空?qǐng)求節(jié)點(diǎn)。

3 基于Dijkstra算法動(dòng)態(tài)計(jì)算傳輸節(jié)點(diǎn)的策略

上述路由算法實(shí)現(xiàn)的關(guān)鍵是運(yùn)用Dijkstra算法求解最佳電量節(jié)點(diǎn)構(gòu)成的傳輸路徑，即需要核心節(jié)點(diǎn)進(jìn)行信息傳輸，由于核心節(jié)點(diǎn)的電力存儲(chǔ)影響整個(gè)網(wǎng)絡(luò)的壽命，因此，需要?jiǎng)討B(tài)變化這些核心節(jié)點(diǎn)。根據(jù)節(jié)點(diǎn)剩余電量情況，定時(shí)動(dòng)態(tài)計(jì)算參與傳輸?shù)暮诵膫鞲泄?jié)點(diǎn)，以形成物聯(lián)網(wǎng)結(jié)構(gòu)上的傳輸網(wǎng)絡(luò)。

本文運(yùn)用Dijkstra算法求解最佳電量節(jié)點(diǎn)構(gòu)成的傳輸路徑圖，圖中的每個(gè)節(jié)點(diǎn)代表一個(gè)參與傳輸?shù)膫鞲衅鞴?jié)點(diǎn)，每條弧代表一條通信線路。為一對(duì)給定節(jié)點(diǎn)之間選擇一條傳輸路徑，只需在圖中找到這對(duì)節(jié)點(diǎn)之間的最短路徑即可。在最短傳輸路徑上的節(jié)點(diǎn)，即為本次能量傳輸?shù)闹欣^和后續(xù)節(jié)點(diǎn)。

3.1 圖結(jié)構(gòu)

圖結(jié)構(gòu)的定義：節(jié)點(diǎn)信息存儲(chǔ)物聯(lián)網(wǎng)傳感器節(jié)點(diǎn)的剩余電量；彼此直接通訊的則對(duì)應(yīng)圖中的邊；每次發(fā)生信息傳輸時(shí)，找其后續(xù)節(jié)點(diǎn)中剩余電量最大的作為中繼節(jié)點(diǎn)進(jìn)行傳輸。

3.2 圖調(diào)整

圖初建時(shí)設(shè)置幾個(gè)主要核心傳感器節(jié)點(diǎn)作為參與數(shù)據(jù)傳輸?shù)墓?jié)點(diǎn)，并彼此連邊，形成初始圖。在傳輸過(guò)程中，一旦網(wǎng)絡(luò)中的某一個(gè)節(jié)點(diǎn)的剩余能量低于預(yù)設(shè)的臨界能量值TE—MIN，則該低能量節(jié)點(diǎn)就會(huì)退出無(wú)線能量傳輸，只傳播該節(jié)點(diǎn)采集的信息給其他中繼節(jié)點(diǎn)，以傳輸其信息到服務(wù)器。從而實(shí)現(xiàn)高能量節(jié)點(diǎn)向低能量節(jié)點(diǎn)的能量補(bǔ)充。

3.3 算法

該算法分為如下幾個(gè)步驟：

（1）設(shè)置一個(gè)未選擇為最短路徑的節(jié)點(diǎn)集合U，一個(gè)已選擇為最短路徑的節(jié)點(diǎn)集合S，S+U=V（G）。在初始情況下，S為空，U中包含所有節(jié)點(diǎn)。源點(diǎn)s的距離dis（s）=0，其他節(jié)點(diǎn)v的距離dis（v）=∞。

（2）從U集合中選擇一個(gè)到S集合任一點(diǎn)距離最短的點(diǎn)，將其加到S集中，并從U集中刪除。

（3）修改U中各節(jié)點(diǎn)的距離，重復(fù)過(guò)程（2）直到到達(dá)終點(diǎn)。

Dijkstra算法流程圖如圖3所示。

算法偽代碼如下：

（1）圖中包含n+1個(gè)頂點(diǎn)，分別為源點(diǎn)s=v0和v1，v2，…vn，邊的權(quán)值為w（vi，vj）

（2）for i=1 to n

（3）dis（vi） =∞

（4）dis（s）=0

（5）S=φ

（6）U=V[G]-S

（7）while（S不包括終點(diǎn)）

（8）Begin

（9）u=集合U中dis（u）最小的頂點(diǎn)

（10） S=S+{u}

（11） U=U-{u}

（12） for（v∈U）

（13） dis（v）=min{dis（v）， dis（u） +w（u，v）}

（14） End

從上面明顯可以看出，在動(dòng)態(tài)調(diào)整傳輸?shù)暮诵墓?jié)點(diǎn)時(shí)，需要定時(shí)計(jì)算節(jié)點(diǎn)的能量作為Dijkstra算法的基礎(chǔ)。

4 仿真實(shí)驗(yàn)分析

利用Matlab對(duì)本文算法建立了仿真場(chǎng)景，在仿真實(shí)驗(yàn)中有30個(gè)傳感器節(jié)點(diǎn)，按一定的隨機(jī)策略分布在面積為100m×200 m的正方形區(qū)域內(nèi)，基站位置為（50 m，175 m）。

網(wǎng)絡(luò)生存時(shí)間和能量均衡因子這兩個(gè)網(wǎng)絡(luò)性能衡量指標(biāo)，是驗(yàn)證網(wǎng)絡(luò)路由協(xié)議性能優(yōu)劣的較為常用的指標(biāo)。

（1）網(wǎng)絡(luò)生存時(shí)間

網(wǎng)絡(luò)生存時(shí)間是指從整個(gè)網(wǎng)絡(luò)開(kāi)始到消耗完畢的時(shí)間。網(wǎng)絡(luò)生存時(shí)間越長(zhǎng)，算法的性能越好，本文給出的算法能夠根據(jù)節(jié)點(diǎn)剩余能量動(dòng)態(tài)調(diào)整傳輸信息路徑中的節(jié)點(diǎn)，使能量較低的節(jié)點(diǎn)盡可能不參與傳輸信息，只用于收發(fā)采集信息，因此達(dá)到了延長(zhǎng)網(wǎng)絡(luò)生存周期的效果。

（2）能量均衡因子

能量均衡因子是指在物聯(lián)網(wǎng)絡(luò)運(yùn)行的某一時(shí)刻，網(wǎng)絡(luò)中節(jié)點(diǎn)剩余能量的最大值與最小值的比值。由于本文方法可使能量均衡因子最小，因此可以延長(zhǎng)網(wǎng)絡(luò)的生命周期。

本文算法實(shí)驗(yàn)運(yùn)行前要預(yù)設(shè)臨界能量值TE_MIN，該值對(duì)網(wǎng)絡(luò)生存時(shí)間有著重要影響。該值過(guò)大，會(huì)使節(jié)點(diǎn)間能量傳輸次數(shù)過(guò)于頻繁，傳輸所消耗的能量也會(huì)隨之增多，這樣便造成能源的浪費(fèi)，使網(wǎng)絡(luò)生存時(shí)間減少；但該值過(guò)小，則剩余能量無(wú)法完成能量傳輸請(qǐng)求的處理過(guò)程。

5 結(jié) 語(yǔ)

本文主要針對(duì)物聯(lián)網(wǎng)中無(wú)線傳感器節(jié)點(diǎn)的能耗問(wèn)題進(jìn)行分析，基于Dijkstra算法動(dòng)態(tài)計(jì)算剩余能量的策略，給出了如何均衡使用物聯(lián)網(wǎng)中節(jié)點(diǎn)以達(dá)到減少其消耗的方法。

參考文獻(xiàn)

[1]孫躍，戴欣，唐春森，等.分布式無(wú)線電能傳輸網(wǎng)[J].電力電子，2010（3）：59-61，84.

[2]許國(guó)，胡瑜，張瑩，等.一種能量有效的無(wú)線傳感器網(wǎng)絡(luò)分簇路由算法[J].天津科技大學(xué)學(xué)報(bào)，2009，24（1）：58-61.

[3]陳志奎，倪晶晶，姜國(guó)海，等.WSN中一種基于剩余能量級(jí)別的負(fù)載均衡路由協(xié)議[J].微電子學(xué)與計(jì)算機(jī)，2010，27（12）：82-86.

[4]段其昌，陳艷，周元.基于能量距離復(fù)合權(quán)值Dijkstra算法的新型能量均衡WSN路由算法[J].傳感技術(shù)學(xué)報(bào)，2010，23（11）：1610-1616.

[5]傅文珍，張波，丘東元，等.自諧振線圈耦合式電能無(wú)線傳輸?shù)淖畲笮史治雠c設(shè)計(jì)[J].中國(guó)電機(jī)工程學(xué)報(bào)，2009，29（18）：21-26.

[6]孫利民.無(wú)線傳感器網(wǎng)絡(luò)[M].北京：清華大學(xué)出版社，2005.

[7]張春花，劉方愛(ài)，吳楠.WSN中基于能量和距離的自適應(yīng)分層路由算法[J].計(jì)算機(jī)應(yīng)用研究，2014，31（11）：3434-3437.

[8]潘中強(qiáng)，劉亮亮，張東.基于非均勻分簇的能耗高效WSN路由協(xié)議[J].微電子學(xué)與計(jì)算機(jī)，2012（1）：93-96，101.

[9]張玉娟，樊曉平，劉少?gòu)?qiáng)，等.太陽(yáng)能補(bǔ)給下無(wú)線傳感器網(wǎng)絡(luò)分簇路由算法[J].計(jì)算機(jī)應(yīng)用研究，2012，29（1）：260-262.

[10]詹思瑜，李建平.基于遺傳算法的Adhoc路由協(xié)議優(yōu)化[J].小型微型計(jì)算機(jī)系統(tǒng)，2012，33（1）：24-27.

[11]馬向南，陳兵.一種具有動(dòng)態(tài)負(fù)載均衡功能的LB_HWMP路由協(xié)議[J].小型微型計(jì)算機(jī)系統(tǒng)，2012，33（2）：343-346.

[12]張敬，許宗澤.一種剩余能量感知的異構(gòu)AdHoc網(wǎng)絡(luò)跨層路由協(xié)議[J].小型微型計(jì)算機(jī)系統(tǒng)，2012，33（2）：353-356.

[13]呂斌斌，包震斌，張明樂(lè).基于SNMP協(xié)議的網(wǎng)絡(luò)拓樸發(fā)現(xiàn)算法分析[J].信息網(wǎng)絡(luò)安全，2012（1）：46-49.

[14]劉曉培，李穎，張豪，等.高效率的小規(guī)模AdHoc組播路由協(xié)議[J].現(xiàn)代電子技術(shù)，2011，34（1）：7-10.

[15]馮文江，沈嘉皓，李林.基于負(fù)載平衡的分層無(wú)線Mesh網(wǎng)絡(luò)路由協(xié)議[J].計(jì)算機(jī)應(yīng)用研究，2011，28（2）：651-653.

[16]陳培培，張華忠.MHST-LEACH—基于LEACH-EE高效聚類(lèi)路由算法[J].計(jì)算機(jī)工程與應(yīng)用，2011，47（1）：120-122.

[17]李梅，周繼鵬.基于負(fù)載均衡的DSR路由協(xié)議改進(jìn)[J].計(jì)算機(jī)應(yīng)用研究，2011，28（1）：256-258.

[18]錢(qián)志鴻，王義君.面向物聯(lián)網(wǎng)的無(wú)線傳感器網(wǎng)絡(luò)綜述[J].電子與信息學(xué)報(bào)，2013，35（1）：215-227.