基于能量分級和位置預(yù)測的高效路由算法*

裴　芳,鄭　瑩，董龍明

（1.湖南機(jī)電職業(yè)技術(shù)學(xué)院，長沙　410073；2.常德職業(yè)技術(shù)學(xué)院，湖南　常德　415000；3.陸軍駐南京地區(qū)軍事代表室，南京　210000）

基于能量分級和位置預(yù)測的高效路由算法*

裴芳1,鄭瑩2，董龍明3

（1.湖南機(jī)電職業(yè)技術(shù)學(xué)院，長沙410073；2.常德職業(yè)技術(shù)學(xué)院，湖南常德415000；3.陸軍駐南京地區(qū)軍事代表室，南京210000）

針對車載傳感器網(wǎng)絡(luò)節(jié)點(diǎn)移動速度快、網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)不穩(wěn)定、終端傳感器節(jié)點(diǎn)能量不確定性等特點(diǎn)，提出了一種能量分級和位置預(yù)測的高效路由算法ERLP（Energy Rank and Location Prediction based routing）。該算法根據(jù)具有不同能量等級的節(jié)點(diǎn)將消息傳遞距離的不同選擇那些能量高的節(jié)點(diǎn)作為中轉(zhuǎn)節(jié)點(diǎn)，并結(jié)合節(jié)點(diǎn)的分布區(qū)域和當(dāng)前速度，盡量將多個消息副本傳遞給覆蓋不同方向的節(jié)點(diǎn)，避免消息傳遞的局部性。仿真結(jié)果表明，與當(dāng)前典型延遲容忍網(wǎng)絡(luò)的路由算法相比，ERLP算法在傳輸成功率、平均延遲時間上具有較大提升。

車載傳感器網(wǎng)絡(luò)，能量分級，位置預(yù)測，路由算法

0　引言

車載傳感器網(wǎng)絡(luò)是一種新興的技術(shù)，主要面向日益龐大的汽車用戶群體,具有節(jié)點(diǎn)移動速度快、網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)不穩(wěn)定、車載終端傳感器節(jié)點(diǎn)能量充足等特點(diǎn)。在傳統(tǒng)的網(wǎng)絡(luò)中，數(shù)據(jù)傳輸依賴于穩(wěn)定的端到端連接，而車載傳感器網(wǎng)絡(luò)不可能存在一條完整的端到端路徑，因此，傳統(tǒng)的路由算法已經(jīng)不再適用于車載傳感器網(wǎng)絡(luò)。為了解決車載傳感器網(wǎng)絡(luò)中移動節(jié)點(diǎn)間數(shù)據(jù)傳輸問題，出現(xiàn)了延遲-容忍網(wǎng)絡(luò)DTN（Delay-Tolerant Network）［1-2］，一般采用“存儲-攜帶-轉(zhuǎn)發(fā)”的方式動態(tài)規(guī)劃路由路勁，完成數(shù)據(jù)的傳輸。

國內(nèi)外研究學(xué)者針對DTN網(wǎng)絡(luò)特點(diǎn)相繼提出了多種DTN路由算法，如：傳染路由算法（Epidemic routing）［3］、PROPHET［4］、FAD［5］、SimBet［6］等。這些算法都是采用多復(fù)制路由策略實現(xiàn)DTN網(wǎng)絡(luò)中消息的傳遞，將同一報文在移動網(wǎng)絡(luò)中復(fù)制多次并發(fā)送到不同的節(jié)點(diǎn)中，通過增加復(fù)本數(shù)來增加消息傳輸?shù)某晒β屎徒档蛡鬏敃r延。這種方法消耗大量的帶寬和移動節(jié)點(diǎn)的能量，在網(wǎng)絡(luò)帶寬和節(jié)點(diǎn)緩存資源充分的情況下可以獲得較好的效果，但是移動傳感器網(wǎng)絡(luò)往往這些資源是有限的，會使網(wǎng)絡(luò)的帶寬開銷特別大，隨著節(jié)點(diǎn)的增多網(wǎng)絡(luò)的性能急劇下降。王建新等人［7］針對多副本消息冗余問題以及消息擴(kuò)散局部性問題，提出了一種基于副本限制和社會性的路由算法RACS，通過限制最大消息副本數(shù)來減少消息副本的冗余，在擴(kuò)展中通過比較節(jié)點(diǎn)的中心性，使中心性較高的節(jié)點(diǎn)獲得相對較多的消息副本，來完成消息副本的擴(kuò)散和遞交。但是，這種方法通過過去一段時間內(nèi)所遇到其他節(jié)點(diǎn)個數(shù)距離計算中心節(jié)點(diǎn)的中心性，沒有根據(jù)節(jié)點(diǎn)當(dāng)前速度方向預(yù)測節(jié)點(diǎn)位置，可能多個中心性節(jié)點(diǎn)將來匯聚到某個區(qū)域，未能夠避免消息傳遞的局部性。

本文根據(jù)車載傳感器網(wǎng)絡(luò)中具有不同能量等級的節(jié)點(diǎn)和消息傳遞距離的不同，選擇那些能量高的節(jié)點(diǎn)，盡量將多個消息副本傳遞給覆蓋不同方向的節(jié)點(diǎn)，盡可能地將消息傳遞給網(wǎng)絡(luò)中其他區(qū)域，避免消息傳遞的局部性。

1　基于能量分級和位置預(yù)測路由算法

基于能量分級和位置預(yù)測的路由算法中，如何利用車載傳感器網(wǎng)絡(luò)中移動節(jié)點(diǎn)的通信能力和動態(tài)特性，選擇最優(yōu)的轉(zhuǎn)發(fā)節(jié)點(diǎn)，在最少的延遲和帶寬下把數(shù)據(jù)從源節(jié)點(diǎn)傳輸?shù)侥繕?biāo)節(jié)點(diǎn)，是路由算法的關(guān)鍵。

1.1節(jié)點(diǎn)能量分級模型

在車載傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)的能量等級決定了節(jié)點(diǎn)的通信能力和節(jié)點(diǎn)間的傳送能力，能量等級較高的節(jié)點(diǎn)具有較強(qiáng)的信息傳播能力，能讓消息擴(kuò)散到更遠(yuǎn)的節(jié)點(diǎn)，因此，選擇能量高的節(jié)點(diǎn)作為轉(zhuǎn)發(fā)節(jié)點(diǎn)比較合理。

車載傳感器網(wǎng)絡(luò)中，移動節(jié)點(diǎn)的能量可以多樣，但一般都很有限，按照節(jié)點(diǎn)的類型可以分為多個等級：網(wǎng)絡(luò)中中繼節(jié)點(diǎn)一般具有較高的能量等級和較多的緩沖區(qū)單元，同時能夠存儲發(fā)送多個消息給較遠(yuǎn)的距離；一般傳感器節(jié)點(diǎn)具有中等能量等級和有限的緩沖區(qū)單元，只能將消息轉(zhuǎn)發(fā)給相鄰單元；末端節(jié)點(diǎn)沒有傳輸能量，只能接受其他節(jié)點(diǎn)傳輸?shù)哪芰俊＼囕d傳感器網(wǎng)絡(luò)中存在大量的一般傳感器節(jié)點(diǎn)，末端節(jié)點(diǎn)數(shù)量有限，為了提高網(wǎng)絡(luò)傳輸效率，車載傳感器網(wǎng)絡(luò)一般設(shè)置有限的專門用來傳輸?shù)闹欣^節(jié)點(diǎn)，盡可能地理上均勻分布在車載移動網(wǎng)絡(luò)中，減少了轉(zhuǎn)發(fā)的次數(shù)，減少節(jié)點(diǎn)間傳輸?shù)难舆t。

車載傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)能量等級可以用EN表示，EN=｛0,1,2，…，max｝?？梢愿鶕?jù)網(wǎng)絡(luò)中節(jié)點(diǎn)的類型，給所有節(jié)點(diǎn)賦予一個能量等級值，如下：

節(jié)點(diǎn)能量等級可以表示節(jié)點(diǎn)能夠?qū)⑾鬏數(shù)姆秶總€en可以對應(yīng)一個距離值Disen,表示在距離范圍Disen內(nèi)的目標(biāo)節(jié)點(diǎn)能夠接受到該消息。另一方面，節(jié)點(diǎn)能量等級en表示能將消息傳輸距離的能力，當(dāng)節(jié)點(diǎn)選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)時，節(jié)點(diǎn)的能量等級是一個重要的考核指標(biāo)，可以使用en/max來衡量節(jié)點(diǎn)的中轉(zhuǎn)能力。

1.2位置預(yù)測計算

車載傳感器網(wǎng)絡(luò)中的移動節(jié)點(diǎn)攜帶GPS模塊，節(jié)點(diǎn)可以隨時獲取自己的位置信息和移動速度矢量，其位置可以通過廣播形式使各個方向周圍節(jié)點(diǎn)能夠感知。

節(jié)點(diǎn)下一個時刻Δt的位置不僅與當(dāng)前的位置有關(guān)，還與節(jié)點(diǎn)當(dāng)前動態(tài)速度矢量有關(guān)。假設(shè)目標(biāo)節(jié)點(diǎn)d的位置為：（xd，yd），速度為：v→d=＜x→d，y→d＞，源節(jié)點(diǎn)s的位置為：（xs，ys），速度為：v→s=＜x→s，y→s＞，可以得到源節(jié)點(diǎn)s和目標(biāo)節(jié)點(diǎn)d的相對位置和速度：

Δxsd=xd-xs，Δysd=yd-xs。

Δvsd=-，各個分量上的相對速度分別為：

可以根據(jù)Δxsd和Δ、Δysd和Δ的值判斷目標(biāo)節(jié)點(diǎn)與源節(jié)點(diǎn)的將來距離情況。節(jié)點(diǎn)在x軸方向上距離和速度表示含義如下，節(jié)點(diǎn)在y軸方向上距離和速度同x軸方向。

當(dāng)Δxsd＞0時：

當(dāng)Δxsd＜0時：

源節(jié)點(diǎn)在選擇中轉(zhuǎn)結(jié)點(diǎn)時，應(yīng)該考慮在將來的方向上選擇越來越遠(yuǎn)的節(jié)點(diǎn)作為中轉(zhuǎn)結(jié)點(diǎn)。

距離因素Dsd可以使用下面公式表示：

速度因素Vsd可以使用下面公式表示：位置綜合因素可以使用公式，位置綜合因子α取值的大小表示位置預(yù)測是速度主導(dǎo)還是距離主導(dǎo)。移動節(jié)點(diǎn)如果網(wǎng)絡(luò)分布距離不是很遠(yuǎn)，節(jié)點(diǎn)移動平凡速度比較快，α取值比較小，一般為：0.2；移動節(jié)點(diǎn)如果網(wǎng)絡(luò)分布距離很廣，移動速度比較慢，α取值比較大，一般為：0.8。

1.3算法描述

算法ERLP能夠?qū)⒕W(wǎng)絡(luò)中數(shù)據(jù)以最快的方式擴(kuò)散從源節(jié)點(diǎn)轉(zhuǎn)發(fā)給目標(biāo)節(jié)點(diǎn)，在進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)前，根據(jù)中轉(zhuǎn)節(jié)點(diǎn)的能量和位置預(yù)測信息進(jìn)行綜合分析，選擇最優(yōu)的轉(zhuǎn)發(fā)節(jié)點(diǎn)d，盡量將數(shù)據(jù)擴(kuò)散到網(wǎng)絡(luò)其他區(qū)域。節(jié)點(diǎn)d的綜合傳遞能力Q（d），計算方式如下：。

平衡因子β取值的大小表示能量分級因素和位置預(yù)測因素所占的比重，β一般取值為：0.5。算法的基本原理是：源節(jié)點(diǎn)s需要將消息m傳遞給目標(biāo)節(jié)點(diǎn)d，當(dāng)前，節(jié)點(diǎn)s通信范圍內(nèi)有若干相鄰節(jié)點(diǎn)，首先節(jié)點(diǎn)通過廣播和簡單的握手收集相鄰節(jié)點(diǎn)的通信信息，包括：相鄰的節(jié)點(diǎn)能量等級ei/max、節(jié)點(diǎn)的位置、速度等信息，然后計算相鄰節(jié)點(diǎn)的綜合傳遞能力，選擇最優(yōu)的相鄰節(jié)點(diǎn)傳遞消息，接收到消息的中轉(zhuǎn)節(jié)點(diǎn)將消息傳遞給下一個節(jié)點(diǎn)，直至將消息傳遞給目表節(jié)點(diǎn)d。

該算法偽代碼描述如下：

2　仿真實驗及結(jié)果分析

本文采用基于Java的DTN仿真工具ONE（Opportunistic Network Environment）［8］進(jìn)行仿真實驗。仿真環(huán)境區(qū)域面積為：18 000 m×18 000 m，整個網(wǎng)絡(luò)由100個移動節(jié)點(diǎn)組成，節(jié)點(diǎn)的速度區(qū)間為：5.6 m/s～33 m/s，相當(dāng)于汽車等交通工具的速度，節(jié)點(diǎn)的通信半徑為：0 m～250 m，根據(jù)50 m共分為5個能量等級，傳輸消息大小為：100 kB～500 kB。實驗中，位置綜合因子α=0.8，β=0.5。

對ERLP算法進(jìn)行仿真，選取與經(jīng)典的算法Epidemic和多副本的社會網(wǎng)絡(luò)SimBet路由算法進(jìn)行比較，分別從傳輸成功率和平均延遲進(jìn)行性能比較。

圖1　不同緩存下傳輸成功率

圖2　不同緩存下平均延遲時間

圖1和圖2分別表示在不同的緩存情況下，節(jié)點(diǎn)的傳輸成功率及傳輸平均延時。由圖可知：由于ERLP路由算法根據(jù)節(jié)點(diǎn)的能量等級及位置預(yù)測綜合傳輸效能選擇性地選取傳輸節(jié)點(diǎn)，減少了節(jié)點(diǎn)的轉(zhuǎn)發(fā)次數(shù)，能更迅速地擴(kuò)散消息到不同區(qū)域，提高了消息傳輸成功率，并且減少了傳輸延時。

3　結(jié)論

本文針對車載傳感器網(wǎng)絡(luò)節(jié)點(diǎn)移動速度快、網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)不穩(wěn)定、終端傳感器節(jié)點(diǎn)能量不確定性等特點(diǎn)，提出了一種能量分級和位置預(yù)測的高效路由算法。該算法選擇能量等級高的節(jié)點(diǎn)作為中轉(zhuǎn)節(jié)點(diǎn)，并結(jié)合節(jié)點(diǎn)的分布區(qū)域和當(dāng)前速度，盡量將多個消息副本傳遞給覆蓋不同方向的節(jié)點(diǎn)，避免消息傳遞的局部性。仿真結(jié)果表明，與當(dāng)前典型延遲容忍網(wǎng)絡(luò)的多副本路由算法相比，有更好地適用于車載傳感器網(wǎng)絡(luò)的特點(diǎn)，在消息傳輸成功率和平均延遲時間上具有較好的效果。建立各種實際特定應(yīng)用的車載傳感器移動自組織網(wǎng)絡(luò)模型是下一步研究重點(diǎn)。

［1］F K，F(xiàn) S.DTN：An architectural retrospective［J］.IEEE Journal on Selected Areas in Communications，2008，26（5）：828-836.

［2］肖明軍，黃劉生.容遲網(wǎng)絡(luò)路由算法［J］.計算機(jī)研究與發(fā)展，2009，46（7）：1065-1073.

［3］MUSOLESI M，HAILES S.Adaptive routing for intermittently connected mobile ad hoc networks［C］//Proceedings of WOWMOM'2005.Taormina：IEEE Computer Society Press，2005：813-820.

［4］LINDGREN A，DORIA A，SEHELEN O.Probabilistic routing in intermittently connected networks［J］.ACM SIGMOBILE Mobile Computing and Communications Review，2003，7 （3）：19-20.

［5］WANG Y，WU H.Analytic，simulation，and empirical evaluation of delay-fault-tolerant mobile sensor networks［J］.IEEE Transactions onWireless Communications，2007，6（7）：3287-3296.

［6］DALY E，HAAHR M.Social network analysis for routing in disconnected delay-tolerant MANETs［C］//Proceddings of ACM Mobi-Hoc，2007：32-40.

［7］王建新，朱敬，劉耀.基于副本限制和社會性的延遲容忍網(wǎng)絡(luò)路由算法［J］.華南理工大學(xué)自然學(xué)報（自然科學(xué)版），2009，37（5）：84-89.

［8］KERANEN A，OTT J，KARKKAINEN T.The ONE simulator for DTN protocol evaluation［C］//SIMUTools'09：Proceedings of the 2nd International Conference on Simulation Tools and Techniques，New York，NY，USA，2009.

Efficient Routing Algorithm based on Energy Rank and Location Prediction

PEI Fang1，ZHENG Ying2，DONG Long-ming3
（1.Hunan Mechanical and Electrical Polytechnic，Changsha 410151，China；2.Changde Vocational Technical College，Changde 415000，China；3.Nanjing Military Representative Office of PLA Army，Nanjing 210000，China）

Nodes move rapidly，the topology of network is instable and energy of terminal sensors cannot be undetermined in the vehicular sensor networks.An efficient routing algorithm is proposed based on energy rank and location predication.Nodes with different energy can transfer messages to ones in the different distance.So，the algorithm chooses nodes with high energy as transfer ones.Also，the algorithm transfers message copies to nodes of different direction according to their distributed region and current speed and can overcome the local message transmission.In the end，the simulation results show that compared with other routing algorithms of delay-tolerant networks，our algorithm performs better on transmission rate and mean delay time.

vehicular sensor networks，energy rank，location predication，routing algorithm

E911

A

1002-0640（2016）07-0014-04

2015-06-05

2015-07-07
*

湖南省教育廳基金（13C258）；湖南省常德市科技局基金資助項目（2014JF11）

裴芳（1977-），女，湖南常德人，碩士，副教授。研究方向：無線傳感器網(wǎng)。