徐善永+李豹+黃友銳+王浩

摘要：針對物聯(lián)網(wǎng)絡(luò)中容易出現(xiàn)節(jié)點能量消耗不均衡，路由穩(wěn)定性差，數(shù)據(jù)容易丟失等問題，提出了一種改進(jìn)的鏈路穩(wěn)定和節(jié)點剩余能量感知的物聯(lián)網(wǎng)路由算法。該路由算法首先建立了一種基于鏈路穩(wěn)定性和節(jié)點剩余能量的混合路由模型，利用該模型對節(jié)點的能量和鏈路穩(wěn)定參數(shù)進(jìn)行綜合預(yù)判，選出最優(yōu)節(jié)點來組成網(wǎng)絡(luò)。仿真結(jié)果表明，與AODV算法相比，該算法可以有效控制網(wǎng)絡(luò)開銷，提高數(shù)據(jù)轉(zhuǎn)發(fā)率，延長網(wǎng)絡(luò)生存周期，降低網(wǎng)絡(luò)延遲。

關(guān)鍵詞：物聯(lián)網(wǎng)；路由算法；鏈路穩(wěn)定；能量感知

中圖分類號：TP39303文獻(xiàn)標(biāo)志碼：A文章編號：1672-1098（2016）01-0019-06

Abstract：In view of the problem that the energy consumption is not balanced， the routing stability is poor， and the data is easy to be lost in Internet of Things （IoTs）， an improved network routing algorithm based on link stability and node residual energy aware is proposed.Firstly， a hybrid routing model based on link stability and residual energy of nodes is established. By using this model， the energy and the link stability parameters of nodes are combined to predict the optimal nodes to form the network.Simulation results showed that compared with AODV algorithm， the algorithm can effectively control the network overhead， improve the data transfer rate， prolong the network lifetime， and reduce the network delay.

Key words：internet of things； routing algorithm； link stability； energy aware

在許多實際應(yīng)用中，由于傳統(tǒng)的物聯(lián)網(wǎng)路由協(xié)議中傳感器節(jié)點的移動性、能量的有限性和射頻距離的有限性，容易出現(xiàn)節(jié)點的能量消耗不均衡，路由穩(wěn)定性差，數(shù)據(jù)容易丟失等問題，傳輸效率不高。針對上述問題，本文提出了一種基于鏈路穩(wěn)定和節(jié)點能量感知混合模型的組播路由協(xié)議（Link Stability and Energy-aware Hybrid model-Based Multicast Routing Protocol，LEHMR），LEHMR路由算法的主要思想是根據(jù)節(jié)點間的鏈路狀態(tài)和節(jié)點的當(dāng)前剩余能量控制整個網(wǎng)絡(luò)的路由發(fā)現(xiàn)。該方法采用廣播請求應(yīng)答（RREQ-RREP）方式，利用網(wǎng)絡(luò)節(jié)點間的鏈路狀態(tài)信息和節(jié)點的剩余能量信息來建立路由選擇機(jī)制，來建立網(wǎng)絡(luò)路由。

1路由模型

11鏈路穩(wěn)定和節(jié)點能量混合的路由選擇機(jī)制

如圖1所示，主要展示了LEHMR算法路由建立的過程。當(dāng)有數(shù)據(jù)轉(zhuǎn)發(fā)時，源節(jié)點將廣播一個RREQ包，鄰居節(jié)點將根據(jù)自身的節(jié)點剩余能量和鏈路保持時間來判斷是否接受該數(shù)據(jù)包，來轉(zhuǎn)發(fā)數(shù)據(jù)。該算法與以往任何算法的不同之處在于，每個節(jié)點在接受RREQ包時，要根據(jù)節(jié)點的剩余能量和鏈路保持時間綜合判斷出是否接收RREQ包，而成為路由鏈路上的節(jié)點，進(jìn)而接收并轉(zhuǎn)發(fā)RREQ包。該RREQ包中的節(jié)點以鏈路的保持時間與節(jié)點的剩余能量作為度量值，來搜索數(shù)據(jù)轉(zhuǎn)發(fā)路徑，建立網(wǎng)絡(luò)路由。

鏈路穩(wěn)定和節(jié)點能量混合的路由選擇機(jī)制當(dāng)節(jié)點S向節(jié)點D發(fā)送數(shù)據(jù)時，節(jié)點S將廣播RREQ數(shù)據(jù)包，所有鄰居節(jié)點將接收這個RREQ數(shù)據(jù)包。在傳統(tǒng)的AODV算法中，節(jié)點1，2，3中若無有效的到節(jié)點D的路由，節(jié)點1，2，3都將轉(zhuǎn)播RREQ包。在LEHMR算法中，將檢測節(jié)點1，2，3與節(jié)點S的鏈路保存時間和節(jié)點1，2，3的剩余能量，因節(jié)點1的剩余能量少、節(jié)點2與節(jié)點S的鏈路保持時間小，根據(jù)LEHMR算法節(jié)點1與節(jié)點2將放棄接收到的RREQ包。只有節(jié)點3滿足能量和鏈路保持時間要求，只有節(jié)點3再次廣播RREQ包，從而建立起S-3-D的路徑傳送數(shù)據(jù)。

12鏈路穩(wěn)定和節(jié)點能量混合數(shù)學(xué)模型

1） 鏈路穩(wěn)定性描述

假設(shè)節(jié)點坐標(biāo)為（xi，xj），其移動速度、運(yùn)動方向和信號傳播半徑分別用vi、θi和Ri來表示。則兩個移動節(jié)點ai和aj之間的鏈路保持時間LET可用公式（1）表示

LETij=

-（ab+ad）+（a2+c2）r2-（ad-bc）2a2+c2（1）

式中：a=vicos θi-vjcos θj，b=xi-xj、c=visin θi-vjsin θj，d=yi-yj、r=Ri

2） 節(jié)點能量描述

如圖2所示，物聯(lián)網(wǎng)路由算法的研究大都采用此節(jié)點能量消耗模型， 該模型由傳送裝置、放大裝置和接收裝置三部分構(gòu)成，傳感器節(jié)點所消耗的總體能量為上述三部分所消耗的能量總和。圖2節(jié)點能量消耗模型

將L bit的信息量數(shù)據(jù)傳送d距離所消耗能量的公式模型如式（2）所示

EL.Tx（L）=L×Eb.txe+L×εfs×d2d≤d0

L×Eb.txe+L×εmp×d4d>d0（2）

接收L bit信息量數(shù)據(jù)所消耗能量的公式模型如式（3）所示

EL .Rx（L）=L×Eb.Rx（3）

中轉(zhuǎn)L bit信息量數(shù)據(jù)所消耗能量的公式模型如式（4）所示

Eralay（L）=EL .Rx（L）+EL .Tx=

L×Eb.txe+L×Eb.Rx+L×εfs×d2d≤d0

L×Eb.txe+L×Eb.Rx+L×εmp×d2d≤d0（4）

式中：εfs和εmp是所選用模型的發(fā)送放大器系數(shù)，Eb.Rx表示接收1bit信息量數(shù)據(jù)所需能量，Eb.Tx表示發(fā)送1bit信息量數(shù)據(jù)所需能量。路徑損耗指數(shù)為α值，當(dāng)d≤d0時，α等于2，當(dāng)d>d0，α等于4。

節(jié)點發(fā)送、接收或轉(zhuǎn)發(fā)的Lbit信息量數(shù)據(jù)后的剩余能量Es（L）用公式（5）表示

Es（L）=E0-EL.Tx節(jié)點為源節(jié)點

E0-EL.Rx節(jié)點為目的節(jié)點

E0-Eralay節(jié)點為源節(jié)點（5）

2LEHMR算法描述

21LEHMR算法路由建立流程

LEHMR算法路由建立的流程圖，如圖3所示。

圖具體描述如下：首先判斷接收RREQ包的節(jié)點中是否存在有效路由，若存在，則建立鏈路；否則根據(jù)公式（1）和公式（5）分別計算出接收RREQ包節(jié)點的剩余能量和接收RREQ包節(jié)點和發(fā)送RREQ包節(jié)點間的鏈路保持時間；判斷接收RREQ包節(jié)點與發(fā)送RREQ包節(jié)點間的鏈路保持時間和接收RREQ包節(jié)點的剩余能量值是否大于閾值，若大于設(shè)定的閾值，在發(fā)送RREQ節(jié)點的路由信息表中記錄滿足條件的節(jié)點路徑信息。反之，則放棄該節(jié)點。并根據(jù)公式（1）和和公式（5）選擇最優(yōu)節(jié)點轉(zhuǎn)發(fā)RREQ包，直到建立路由。

22LEHMR算法流程

本文提出的LEHMR路由算法，是屬于應(yīng)答式的組播路由協(xié)議。該算法中將鏈路穩(wěn)定度和能量信息結(jié)合到路由發(fā)現(xiàn)機(jī)制中，改進(jìn)路由選擇機(jī)制，只有滿足鏈路穩(wěn)定度和能量要求的路徑才能被選擇，其總體的流程如圖4所示。

圖4LEHMR路由算法的總體流程圖算法流程說明：

1） 對節(jié)點各項參數(shù)進(jìn)行初始化設(shè)置，包括節(jié)點的能量值，鏈路穩(wěn)定值，能量閾值，鏈路穩(wěn)定閾值等。

2） 首先源節(jié)點將以廣播的形式進(jìn)行傳送，RREQ信息包中記錄有：各個節(jié)點的能量值，鏈路穩(wěn)定值，能量閾值，鏈路穩(wěn)定閾值、源節(jié)點和目標(biāo)節(jié)點的位置以及有效的路徑信息。

3） 在發(fā)送RREQ節(jié)點的通信范圍內(nèi)的所有鄰居節(jié)點將接收RREQ數(shù)據(jù)包，同時將檢測自身的路有信息表，是否存在從源節(jié)點到目的節(jié)點的有效路由信息。

4） 若某節(jié)點路由信息表中存在從源節(jié)點到目的節(jié)點的有效路由信息，則向前一級節(jié)點發(fā)送RREP路由回應(yīng)數(shù)據(jù)包，建立路由。若所有鄰節(jié)點中都沒有有效的路徑信息，則各個節(jié)點判斷自身的能量值和前級節(jié)點間的鏈路保持時間是否滿足設(shè)定的閾值。

5） 根據(jù)判斷條件，若節(jié)點的能量信息和鏈路穩(wěn)定信息滿足設(shè)定的閾值，則該節(jié)點繼續(xù)轉(zhuǎn)發(fā)RREQ路由請求數(shù)據(jù)包，繼續(xù)執(zhí)行3）。若節(jié)點的能量信息和鏈路穩(wěn)定信息不滿足設(shè)定的閾值，則丟棄RREQ路由請求數(shù)據(jù)包，路由請求結(jié)束。

3仿真與分析

利用NS2對LEHMR算法仿真，條件設(shè)定如下，節(jié)點數(shù)：150個，傳輸距離：250 m，隨機(jī)分布范圍：700m×700m，采用隨機(jī)路徑來構(gòu)建節(jié)點移動模型。測試時，節(jié)點移動速度變化范圍：5～25 m/s，仿真持續(xù)時間：500 s，數(shù)據(jù)包的恒定比特率為：1 000 bit，數(shù)據(jù)包固定間隔生成比率為：4包每秒。在仿真中，15個移動節(jié)點被隨機(jī)配置成源節(jié)點和目標(biāo)節(jié)點。

1） 網(wǎng)絡(luò)開銷

如圖5所示，AODV算法和LEHMR算法相比，隨著節(jié)點移動速度變大，兩種算法的網(wǎng)絡(luò)開銷都會變大。AODV算法的網(wǎng)絡(luò)開銷要明顯大于LEHMR算法，這是因為AODV算法沒有選取最優(yōu)鄰居節(jié)點廣播RREQ消息，LEHMR算法要求任意節(jié)點在接收轉(zhuǎn)發(fā)RREQ消息前都要檢查節(jié)點的能量水平和與發(fā)送RREQ包節(jié)點間的鏈路保持時間。這個規(guī)則減少了RREQ包的轉(zhuǎn)發(fā)量，提高了路徑的穩(wěn)定性，因此，生成的節(jié)點路由有一個很好的鏈路生存周期和很好的能量水平。由圖5可知：當(dāng)節(jié)點的能量水平在1到4之間變化時，由于節(jié)點的能量增加，路由開銷相應(yīng)減少。

2） 數(shù)據(jù)轉(zhuǎn)發(fā)率

從圖6顯示結(jié)果表明，綜合考慮能量和移動因素的影響。LEHMR算法的數(shù)據(jù)包的平均轉(zhuǎn)移率要高于AODV算法，通過這個可得出結(jié)論：與AODV算法相比，LEHMR算法建立的路由要穩(wěn)定，具有較高的網(wǎng)絡(luò)生存周期。LEHMR算法選擇路徑時，構(gòu)建路由的節(jié)點都具有很高的剩余能量、節(jié)點間具有很高的鏈路生存周期。而AODV算法構(gòu)成路由的節(jié)點沒有此種功能，它們間發(fā)送了大量的冗余信息，導(dǎo)致了節(jié)點能量很快耗盡，因此具有較低的轉(zhuǎn)發(fā)率。

3） 網(wǎng)絡(luò)生存周期

圖7顯示，當(dāng)增大網(wǎng)絡(luò)節(jié)點的能量值時，網(wǎng)絡(luò)生存周期相應(yīng)增大。節(jié)點能量閾值的提高意味著若節(jié)點的能量低于閾值的，將停止轉(zhuǎn)發(fā)RREQ數(shù)據(jù)包，這將造成大量的節(jié)點為節(jié)省能量而停止轉(zhuǎn)發(fā)RREQ包，同時整個網(wǎng)絡(luò)區(qū)域內(nèi)的其它節(jié)點因不轉(zhuǎn)發(fā)RREQ包，也節(jié)省了能量，高穩(wěn)定度的路由會減少用于路由維護(hù)控制數(shù)據(jù)包，同時消耗的能量更少。

4） 網(wǎng)絡(luò)延遲

如圖8所示的仿真結(jié)果表明：LEHMR算法的延遲時間要明顯優(yōu)于AODV算法，因為LEHMR算法中的路由節(jié)點擁有非常好鏈路生存周期和能量。另外，觀察到當(dāng)提高鏈路生存周期閾值，網(wǎng)絡(luò)的延遲時間將增大，因為在節(jié)點移動的狀態(tài)下，滿足這么高的鏈路生存周期和高能量水平的節(jié)點很難找到，數(shù)據(jù)包通過少量跳數(shù)進(jìn)行轉(zhuǎn)發(fā)。

4結(jié)束語

本文提出了一種基于鏈路穩(wěn)定和節(jié)點能量感知混合模型的組播路由算法。該路由算法根據(jù)節(jié)點的剩余能量和鏈路生存時間來控制路由發(fā)現(xiàn)，在路由發(fā)現(xiàn)的過程中，大大減少了傳感器節(jié)點間交互信息量和計算任務(wù)。仿真結(jié)果表明：該算法明顯增大了數(shù)據(jù)包轉(zhuǎn)移率，減小了控制開銷和網(wǎng)絡(luò)延遲。

參考文獻(xiàn)：

[1]夏輝，賈智平. 移動 Ad Hoc 網(wǎng)絡(luò)中基于鏈路穩(wěn)定性預(yù)測的組播路由協(xié)議[J]. 計算機(jī)學(xué)報， 2013， 36（5）： 926-936.

[2]鄭石，吳偉強(qiáng). 基于能量感知的ad hoc路由算法研究[J]. 通信學(xué)報， 2012， 33（4）： 9-16.

[3]陶洋， 李冉， 李勇. 無線 Ad Hoc 網(wǎng)絡(luò)中基于鏈路穩(wěn)定預(yù)測的路由協(xié)議[J]. 廣東通信技術(shù)， 2012， 32（2）： 43-46.

[4]曾文鋒，戴建輝. 能量感知和鏈路穩(wěn)定度的多徑 MANET 路由[J]. 通信技術(shù)， 2011， 44（8）： 54-57.

[5]ZHENG Z. WDM： An Energy-Efficient Multi-hop Routing Algorithm for Wireless Sensor Networks[C]// International Conference on Computational Science， 2005.

[6]沈波. 無線傳感器網(wǎng)絡(luò)分簇路由協(xié)議 [J]. 軟件學(xué)報， 2006， 17（7）： 1 588-1 600.

[7]林亞平. 傳感器網(wǎng)絡(luò)中一種分布式數(shù)據(jù)匯聚層次路由算法[J]. 電子學(xué)報， 2004，32（11）： 1 801-1 805.

[8]HONG LI. Overall energy-balanced routing protocol[J]. Computer Engineering and Applications，2010，46 （2）：86-90.

[9]LIANG W F. Prolonging network lifetime via a controlled mobile sink in wireless sensor networks[C]// In：IEEE Communications Society，IEEE Globecom 2010，Proceedings of IEEE Globecom 2010： 978-983.

[10]LU G. An adaptive energy-effieient and Low-latency MAC for data gathering in wireless sensor networks[C]// Proeeedings of 18th International Parallel and Distributed Proeessing Symposium， 2004：26-30.

[11]周杰. 移動Ad-Hoc網(wǎng)絡(luò)的路由算法和位置管理方案[J]. 計算機(jī)工程與應(yīng)用，2004（7）：22-26.

[12]唐勇. 無線傳感器網(wǎng)絡(luò)路由協(xié)議研究進(jìn)展[J]. 軟件學(xué)報， 2006， 17（3）： 410-421.

[13]WU K， HARMS J. Location trace aided routing in mobile ad hoc networks[C]// Computer Communications and Networks， 2000. Proceedings. Ninth International Conference on. IEEE， 2000： 354-359.

[14]任敬安，涂亞慶.基于蟻群優(yōu)化的無線自組織網(wǎng)絡(luò)能量感知路由協(xié)議與參數(shù)優(yōu)化研究[J]. 計算機(jī)應(yīng)用與軟件， 2012， 29（9）： 66-70.

[15]蔡蘇亞. 改進(jìn)的最優(yōu)鏈路狀態(tài)路由協(xié)議算法[J].計算機(jī)與現(xiàn)代化，2014（8）：106-109.

[16]王靖，李芳芳.基于鏈路狀態(tài)感知的無線Mesh網(wǎng)優(yōu)化路由算法[J].計算機(jī)科學(xué)，2012，39（11）：37-40.

[17]朱斌，曾孝平.能量高效與移動預(yù)測的路由算法分析[J].重慶大學(xué)報，2010，33（10）：88-93.

[18]洪利，楊淑玲.一種全局能量均衡的路由協(xié)議[J].計算機(jī)工程與應(yīng)用，2010，46（2）： 86-90.

[19]周德榮，夏齡.一種改進(jìn)的AODV路由協(xié)議的實現(xiàn)與仿真[J].實驗室研究與探索，2014，33（11）：67-71.

[20]夏輝，賈智平.移動Ad Hoc網(wǎng)絡(luò)中基于鏈路穩(wěn)定性預(yù)測的組播路由協(xié)議[J]