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

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

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

中圖分類號：TP312 文獻標識碼：A 文章編號：2095-1302（2016）06-00-03

0 引 言

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

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

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

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

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

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

（2）保證將報文準確完整地傳送到基站。

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

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

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

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

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

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

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

算法設(shè)計具體過程如下：

（1）發(fā)送能量傳輸請求報文。報文格式如下：

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

應(yīng)答報文有節(jié)點ID、節(jié)點類型、報文類型、節(jié)點間距離、節(jié)點剩余能量幾個字段。

（3）選擇能量發(fā)射節(jié)點Wz。請求能量傳輸?shù)墓?jié)點收到返回的報文后，需要根據(jù)報文的信息，計算出能量傳輸?shù)男?。能量在空氣中傳輸，像光和聲音一樣會出現(xiàn)衰竭，因此效率與距離成反比，但效率與兩個節(jié)點間的能量差成正比。因此能量發(fā)射結(jié)點Ni的選取函數(shù)定義為：

Ni =Nsel （MAX（Eri/Li2））

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

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

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

3 基于Dijkstra算法動態(tài)計算傳輸節(jié)點的策略

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

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

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

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

3.2 圖調(diào)整

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

3.3 算法

該算法分為如下幾個步驟：

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

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

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

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

算法偽代碼如下：

（1）圖中包含n+1個頂點，分別為源點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不包括終點）

（8）Begin

（9）u=集合U中dis（u）最小的頂點

（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

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

4 仿真實驗分析

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

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

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

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

（2）能量均衡因子

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

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

5 結(jié) 語

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

參考文獻

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

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

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

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

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

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

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

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

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

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

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

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

[13]呂斌斌，包震斌，張明樂.基于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]馮文江，沈嘉皓，李林.基于負載平衡的分層無線Mesh網(wǎng)絡(luò)路由協(xié)議[J].計算機應(yīng)用研究，2011，28（2）：651-653.

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

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

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