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

(安徽理工大學(xué)電氣與信息工程學(xué)院，安徽　淮南　232001)

?

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

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

(安徽理工大學(xué)電氣與信息工程學(xué)院，安徽淮南232001)

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

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

在許多實(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)題，傳輸效率不高。針對(duì)上述問(wèn)題，本文提出了一種基于鏈路穩(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)。該方法采用廣播請(qǐng)求應(yīng)答(RREQ-RREP)方式，利用網(wǎng)絡(luò)節(jié)點(diǎn)間的鏈路狀態(tài)信息和節(jié)點(diǎn)的剩余能量信息來(lái)建立路由選擇機(jī)制，來(lái)建立網(wǎng)絡(luò)路由。

1路由模型

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

如圖1所示，主要展示了LEHMR算法路由建立的過(guò)程。當(dāng)有數(shù)據(jù)轉(zhuǎn)發(fā)時(shí)，源節(jié)點(diǎn)將廣播一個(gè)RREQ包，鄰居節(jié)點(diǎn)將根據(jù)自身的節(jié)點(diǎn)剩余能量和鏈路保持時(shí)間來(lái)判斷是否接受該數(shù)據(jù)包，來(lái)轉(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)的剩余能量作為度量值，來(lái)搜索數(shù)據(jù)轉(zhuǎn)發(fā)路徑，建立網(wǎng)絡(luò)路由。

圖1　鏈路穩(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中若無(wú)有效的到節(jié)點(diǎn)D的路由，節(jié)點(diǎn)1，2，3都將轉(zhuǎn)播RREQ包。在LEHMR算法中，將檢測(cè)節(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滿(mǎn)足能量和鏈路保持時(shí)間要求，只有節(jié)點(diǎn)3再次廣播RREQ包，從而建立起S-3-D的路徑傳送數(shù)據(jù)。

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

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

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

LETij=

(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)所示

(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=

(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)表示

(5)

2LEHMR算法描述

2.1LEHMR算法路由建立流程

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

圖3　LEHMR算法路由建立流程圖

具體描述如下：首先判斷接收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)的路由信息表中記錄滿(mǎn)足條件的節(jié)點(diǎn)路徑信息。反之，則放棄該節(jié)點(diǎn)。并根據(jù)公式(1)和和公式(5)選擇最優(yōu)節(jié)點(diǎn)轉(zhuǎn)發(fā)RREQ包，直到建立路由。

2.2LEHMR算法流程

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

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

算法流程說(shuō)明：

1) 對(duì)節(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í)將檢測(cè)自身的路有信息表，是否存在從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的有效路由信息。

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

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

3仿真與分析

利用NS2對(duì)LEHMR算法仿真，條件設(shè)定如下，節(jié)點(diǎn)數(shù)：150個(gè)，傳輸距離：250 m，隨機(jī)分布范圍：700m×700m，采用隨機(jī)路徑來(lái)構(gòu)建節(jié)點(diǎn)移動(dòng)模型。測(cè)試時(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ò)開(kāi)銷(xiāo)

如圖5所示，AODV算法和LEHMR算法相比，隨著節(jié)點(diǎn)移動(dòng)速度變大，兩種算法的網(wǎng)絡(luò)開(kāi)銷(xiāo)都會(huì)變大。AODV算法的網(wǎng)絡(luò)開(kāi)銷(xiāo)要明顯大于LEHMR算法，這是因?yàn)锳ODV算法沒(méi)有選取最優(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)的能量增加，路由開(kāi)銷(xiāo)相應(yīng)減少。

v/(m·s-1)1. AODV;2.LEHMR energy=1；3.LEHMR energy=2；4.LEHMR energy=3；5.LEHMR energy=4圖5　網(wǎng)絡(luò)開(kāi)銷(xiāo)與節(jié)點(diǎn)速度的關(guān)系

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

從圖6顯示結(jié)果表明，綜合考慮能量和移動(dòng)因素的影響。LEHMR算法的數(shù)據(jù)包的平均轉(zhuǎn)移率要高于AODV算法，通過(guò)這個(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)沒(méi)有此種功能，它們間發(fā)送了大量的冗余信息，導(dǎo)致了節(jié)點(diǎn)能量很快耗盡，因此具有較低的轉(zhuǎn)發(fā)率。

v/(m·s-1)1. AODV;2.LEHMR energy=1；3.LEHMR energy=2；4.LEHMR energy=3；5.LEHMR energy=4圖6　數(shù)據(jù)轉(zhuǎn)發(fā)率與節(jié)點(diǎn)速度的關(guān)系

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)定度的路由會(huì)減少用于路由維護(hù)控制數(shù)據(jù)包，同時(shí)消耗的能量更少。

v/(m·s-1)1. AODV;2.LEHMR energy=1；3.LEHMR energy=2；4.LEHMR energy=3；5.LEHMR energy=4圖7　網(wǎng)絡(luò)生存周期與節(jié)點(diǎn)速度的關(guān)系

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

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

v/(m·s-1)1. AODV;2.LEHMR energy=2；3.LEHMR energy=3；4.LEHMR energy=4圖8　網(wǎng)絡(luò)延遲與節(jié)點(diǎn)速度的關(guān)系

4結(jié)束語(yǔ)

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

參考文獻(xiàn)：

[1]夏輝，賈智平. 移動(dòng) Ad Hoc 網(wǎng)絡(luò)中基于鏈路穩(wěn)定性預(yù)測(cè)的組播路由協(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]陶洋， 李冉， 李勇. 無(wú)線(xiàn) Ad Hoc 網(wǎng)絡(luò)中基于鏈路穩(wěn)定預(yù)測(cè)的路由協(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ú)線(xiàn)傳感器網(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ú)線(xiàn)傳感器網(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ú)線(xiàn)自組織網(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)感知的無(wú)線(xiàn)Mesh網(wǎng)優(yōu)化路由算法[J].計(jì)算機(jī)科學(xué)，2012，39(11)：37-40.

[17]朱斌，曾孝平.能量高效與移動(dòng)預(yù)測(cè)的路由算法分析[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ù)測(cè)的組播路由協(xié)議[J].計(jì)算機(jī)學(xué)報(bào)，2013，36(5)：926-936.

(責(zé)任編輯：李麗，范君)

A Multicast Routing Protocol Based on the Hybrid Model of Link Stability and Energy Aware in Internet of Things

XU Shan-yong, LI Bao, HUANG You-rui, WANG Hao

(School of Electrical and Information Engineering, Anhui University of Science and Technology, Huainan Anhui 232001, China)

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

收稿日期：2015-04-05

基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(51274011、61300001)；2014大學(xué)生創(chuàng)新創(chuàng)業(yè)計(jì)劃基金資助項(xiàng)目(AH201410361180)

作者簡(jiǎn)介：徐善永(1983-)，男，安徽固鎮(zhèn)人，實(shí)驗(yàn)師，碩士，研究方向：物聯(lián)網(wǎng)及智能信號(hào)處理研究。

中圖分類(lèi)號(hào)：TP393.03

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1672-1098(2016)01-0019-06