物聯(lián)網(wǎng)中鏈路穩(wěn)定和能量感知混合模型的組播路由協(xié)議

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

摘要：針對物聯(lián)網(wǎng)絡(luò)中容易出現(xiàn)節(jié)點(diǎn)能量消耗不均衡，路由穩(wěn)定性差，數(shù)據(jù)容易丟失等問題，提出了一種改進(jìn)的鏈路穩(wěn)定和節(jié)點(diǎn)剩余能量感知的物聯(lián)網(wǎng)路由算法。該路由算法首先建立了一種基于鏈路穩(wěn)定性和節(jié)點(diǎn)剩余能量的混合路由模型，利用該模型對節(jié)點(diǎn)的能量和鏈路穩(wěn)定參數(shù)進(jìn)行綜合預(yù)判，選出最優(yōu)節(jié)點(diǎn)來組成網(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

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

1路由模型

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

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

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

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

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

假設(shè)節(jié)點(diǎn)坐標(biāo)為（xi，xj），其移動(dòng)速度、運(yùn)動(dòng)方向和信號傳播半徑分別用vi、θi和Ri來表示。則兩個(gè)移動(dòng)節(jié)點(diǎn)ai和aj之間的鏈路保持時(shí)間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é)點(diǎn)能量描述

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

將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時(shí)，α等于2，當(dāng)d>d0，α等于4。

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

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

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

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

2LEHMR算法描述

21LEHMR算法路由建立流程

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

圖具體描述如下：首先判斷接收RREQ包的節(jié)點(diǎn)中是否存在有效路由，若存在，則建立鏈路；否則根據(jù)公式（1）和公式（5）分別計(jì)算出接收RREQ包節(jié)點(diǎn)的剩余能量和接收RREQ包節(jié)點(diǎn)和發(fā)送RREQ包節(jié)點(diǎn)間的鏈路保持時(shí)間；判斷接收RREQ包節(jié)點(diǎn)與發(fā)送RREQ包節(jié)點(diǎn)間的鏈路保持時(shí)間和接收RREQ包節(jié)點(diǎn)的剩余能量值是否大于閾值，若大于設(shè)定的閾值，在發(fā)送RREQ節(jié)點(diǎn)的路由信息表中記錄滿足條件的節(jié)點(diǎn)路徑信息。反之，則放棄該節(jié)點(diǎn)。并根據(jù)公式（1）和和公式（5）選擇最優(yōu)節(jié)點(diǎn)轉(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é)點(diǎn)各項(xiàng)參數(shù)進(jìn)行初始化設(shè)置，包括節(jié)點(diǎn)的能量值，鏈路穩(wěn)定值，能量閾值，鏈路穩(wěn)定閾值等。

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

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

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

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

3仿真與分析

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

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

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

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

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

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

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

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

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

4結(jié)束語

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

參考文獻(xiàn)：

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

[2]鄭石，吳偉強(qiáng). 基于能量感知的ad hoc路由算法研究[J]. 通信學(xué)報(bào)， 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é)報(bào)， 2006， 17（7）： 1 588-1 600.

[7]林亞平. 傳感器網(wǎng)絡(luò)中一種分布式數(shù)據(jù)匯聚層次路由算法[J]. 電子學(xué)報(bào)， 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]周杰. 移動(dòng)Ad-Hoc網(wǎng)絡(luò)的路由算法和位置管理方案[J]. 計(jì)算機(jī)工程與應(yīng)用，2004（7）：22-26.

[12]唐勇. 無線傳感器網(wǎng)絡(luò)路由協(xié)議研究進(jìn)展[J]. 軟件學(xué)報(bào)， 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ì)算機(jī)應(yīng)用與軟件， 2012， 29（9）： 66-70.

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

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

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

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

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

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