基于節(jié)點(diǎn)綜合效能的DTN路由算法*

鄭瑩，裴芳，董龍明

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

基于節(jié)點(diǎn)綜合效能的DTN路由算法*

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

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

針對(duì)容忍延遲網(wǎng)絡(luò)（DTN）高延遲、數(shù)據(jù)傳輸成功率低等問題，提出了一種基于節(jié)點(diǎn)綜合效能的DTN路由算法SERA。該算法綜合考慮移動(dòng)節(jié)點(diǎn)的活躍度和剩余能量，使消息副本向綜合效能高的節(jié)點(diǎn)擴(kuò)散。SERA節(jié)點(diǎn)活躍度描述了節(jié)點(diǎn)的社會(huì)和動(dòng)態(tài)特性，SERA盡量將消息副本傳遞給活躍度高的節(jié)點(diǎn)，以提高消息傳輸?shù)某晒β?；在選擇中繼節(jié)點(diǎn)時(shí)，充分考慮節(jié)點(diǎn)的能量狀態(tài)，以避免能量不足的節(jié)點(diǎn)承擔(dān)更多的信息傳輸任務(wù)，從而提高網(wǎng)絡(luò)節(jié)點(diǎn)的存活率。仿真結(jié)果表明，與典型的DTN路由算法相比，SERA能夠更好地平衡節(jié)點(diǎn)的能耗，獲得更高的消息遞交成功率和更長的網(wǎng)絡(luò)生存期。

節(jié)點(diǎn)綜合效能，DTN路由算法，節(jié)點(diǎn)活躍度，能量狀態(tài)

0 引言

容忍延遲網(wǎng)絡(luò)（Delay Tolerant Networks，DTN）是近年廣受關(guān)注的一類新興的網(wǎng)絡(luò)體系結(jié)構(gòu)，是由Kevin在2003年SIGCOMM國際會(huì)議上提出［1］。能夠在寬闊惡劣的條件下，實(shí)時(shí)收集大量詳實(shí)可靠的一手?jǐn)?shù)據(jù)，被廣泛應(yīng)用于星際網(wǎng)絡(luò)、無線車載網(wǎng)絡(luò)、工業(yè)控制、環(huán)境監(jiān)測(cè)、交通管理、國防軍事等領(lǐng)域。與傳統(tǒng)網(wǎng)絡(luò)相比，DTN的節(jié)點(diǎn)能夠協(xié)作地感知、采集、匯總和處理監(jiān)測(cè)區(qū)域的各種信息，DTN通常分布密集，節(jié)點(diǎn)數(shù)量能達(dá)到幾百至上千，傳感器節(jié)點(diǎn)體積小，采用電池供電，限制了節(jié)點(diǎn)的處理和通信能力。由于具有節(jié)點(diǎn)頻繁移動(dòng)、間隙性連接、能量和存儲(chǔ)資源受限等特點(diǎn)，DTN的通信節(jié)點(diǎn)間幾乎不存在端到端完整固定的傳輸路徑。因此，高效節(jié)能的DTN路由算法已成為DTN網(wǎng)絡(luò)研究熱點(diǎn)，如何在延長節(jié)點(diǎn)存活生命期的前提下提高消息遞交成功率是衡量一個(gè)DTN優(yōu)劣的重要指標(biāo)。

目前，已有的DTN路由算法主要分為兩類［2］：基于轉(zhuǎn)發(fā)的路由算法和基于泛洪的路由算法?；谵D(zhuǎn)發(fā)的路由算法主要思想是消息被逐跳從源節(jié)點(diǎn)向目的節(jié)點(diǎn)轉(zhuǎn)發(fā)，在整個(gè)轉(zhuǎn)發(fā)過程中僅有一個(gè)消息副本，典型的路由算法見文獻(xiàn)［3-7］。但是，在傳遞副本受限的消息和同時(shí)面對(duì)多個(gè)相鄰節(jié)點(diǎn)時(shí)，如何選擇綜合性能更高的節(jié)點(diǎn)來承擔(dān)傳遞的任務(wù)，使得消息能更快更成功地傳遞到目標(biāo)節(jié)點(diǎn)，成為這類路由算法的需解決的難點(diǎn)和重點(diǎn)。

本文提出一種基于節(jié)點(diǎn)綜合效能的DTN路由算法SERA（synthetical effectiveness based routing alogirthm）。該算法主要思想是基于泛洪多副本路由算法，將節(jié)點(diǎn)能量狀態(tài)和節(jié)點(diǎn)動(dòng)態(tài)活躍度作為衡量節(jié)點(diǎn)綜合效能的指標(biāo)，以此來評(píng)判選擇消息中繼的節(jié)點(diǎn)。本文通過仿真試驗(yàn)，將SERA路由算法與典型的Epidemic和基于SWA算法的ESR算法［8］進(jìn)行比較，結(jié)果表明SERA算法在消息遞交成功率、網(wǎng)絡(luò)生命周期等方面具有良好的優(yōu)勢(shì)。

1 節(jié)點(diǎn)綜合效能模型

SERA算法主要面向節(jié)點(diǎn)隨機(jī)移動(dòng)的DTN網(wǎng)絡(luò)，因此，節(jié)點(diǎn)的綜合效能主要包括：節(jié)點(diǎn)的的能量等級(jí)、通信覆蓋能力、緩沖空間、移動(dòng)速度等。在SERA算法中，主要考慮節(jié)點(diǎn)的能量等級(jí)和節(jié)點(diǎn)活躍度反應(yīng)節(jié)點(diǎn)消息遞交能力的指標(biāo)。

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

定義1節(jié)點(diǎn)i的相鄰節(jié)點(diǎn)j的能量等級(jí)為：

其中：Ei、Ej分布表示當(dāng)前節(jié)點(diǎn)i和節(jié)點(diǎn)j所攜帶的能量。

節(jié)點(diǎn)消息傳遞能力不僅與自身所攜帶的能量有關(guān)，還與節(jié)點(diǎn)所在DTN群體中社會(huì)活動(dòng)度有關(guān)：節(jié)點(diǎn)所能感知的相鄰節(jié)點(diǎn)越多，表示節(jié)點(diǎn)DTN社會(huì)關(guān)系越廣，能夠?qū)⑾V播更廣的范圍；節(jié)點(diǎn)的移動(dòng)速度越快，表示節(jié)點(diǎn)在相同的時(shí)間內(nèi)能夠?qū)y帶的消息傳播更廣的范圍。選擇這樣的節(jié)點(diǎn)有助于消息更快地?cái)U(kuò)散到DTN更多節(jié)點(diǎn)，并且增大了消息的傳播的成功率。

定義2節(jié)點(diǎn)相對(duì)活躍度為：

假設(shè)節(jié)點(diǎn)i的位置為：（xi，yi），速度為：→i=＜→i，i＞，相鄰節(jié)點(diǎn)j的位置為：（xj，yj），速度為：→j=＜→j，y→j＞，可以得到節(jié)點(diǎn)i和相鄰節(jié)點(diǎn)j的相對(duì)位置和速度：Δxij=xj-xi，Δyij=yj-xi。，各個(gè)分量上的相對(duì)速度分別為：。

當(dāng)Δxij＞0時(shí)：

當(dāng)Δxij＜0時(shí)：

如果節(jié)點(diǎn)i在某個(gè)方向上速度為0，則在某個(gè)方向上的比值為0，即：若→i=0，則：若→i=0，則：。i、j為符號(hào)值，不僅與節(jié)點(diǎn)的距離方向有關(guān)，還與運(yùn)動(dòng)的方向有關(guān)。

因此，i取值可以表示如下：

同樣地，節(jié)點(diǎn)i與相鄰節(jié)點(diǎn)j在y軸方向上距離和速度同x軸方向，j取值可以表示如下：

綜上分析，SERA算法的節(jié)點(diǎn)i的相鄰節(jié)點(diǎn)j的綜合效能模型為：

式中，參數(shù)α用于反映可以能量比與節(jié)點(diǎn)活躍度兩個(gè)指標(biāo)在節(jié)點(diǎn)綜合效能模型的權(quán)重，在本文方案中，根據(jù)測(cè)試數(shù)據(jù)經(jīng)驗(yàn)值選擇α為：0.2。

2 基于節(jié)點(diǎn)綜合效能的DTN路由算法

SERA算法的基本思想如下：首先，DTN初始化時(shí)，設(shè)置各種權(quán)重參數(shù)：ε=0.2，α=0.2；規(guī)定每個(gè)消息能夠向網(wǎng)絡(luò)中注入的最大副本配額L，即任意時(shí)刻DTN中該消息的所有副本攜帶的配額總合不超過L；然后，收集所有鄰居節(jié)點(diǎn)參數(shù)并計(jì)算鄰居節(jié)點(diǎn)的相對(duì)綜合效能值，根據(jù)綜合效能值按比例向鄰居節(jié)點(diǎn)擴(kuò)散該消息的副本；當(dāng)該消息的副本攜帶的配額減為1時(shí)，節(jié)點(diǎn)不再擴(kuò)散該消息，而是選擇所有鄰居節(jié)點(diǎn)綜合效能值最大的節(jié)點(diǎn)轉(zhuǎn)發(fā)。為了防止節(jié)點(diǎn)能量耗盡，保證網(wǎng)絡(luò)的生命周期，SERA算法提出了基于可能能量的節(jié)點(diǎn)狀態(tài)轉(zhuǎn)移策略：

①當(dāng)Ei≥ThresholdE，節(jié)點(diǎn)能量充足，節(jié)點(diǎn)處于活躍狀態(tài)，該狀態(tài)下節(jié)點(diǎn)能夠發(fā)送和接受消息，并且能夠周期性地主動(dòng)掃描，以及時(shí)獲知周圍相鄰節(jié)點(diǎn)綜合效能信息；

②當(dāng)ThresholdE/2≤Ei≤ThresholdE，節(jié)點(diǎn)能量比較低，節(jié)點(diǎn)進(jìn)入轉(zhuǎn)發(fā)狀態(tài)，節(jié)點(diǎn)能夠周期性地主動(dòng)掃描，節(jié)點(diǎn)不再擴(kuò)散和存儲(chǔ)消息，但是將所攜帶的消息直接轉(zhuǎn)發(fā)給相鄰節(jié)點(diǎn)；

③當(dāng)Ei＜ThresholdE/2，節(jié)點(diǎn)能量過低，節(jié)點(diǎn)進(jìn)入靜默狀態(tài)，不再進(jìn)行周期性主動(dòng)掃描，不再轉(zhuǎn)發(fā)信息，只接受以本節(jié)點(diǎn)為目地節(jié)點(diǎn)的消息；

④當(dāng)Ei=0，節(jié)點(diǎn)能量為0，節(jié)點(diǎn)處于死亡狀態(tài)，不能進(jìn)行任何操作。

綜上分析，本文提出的SERA路由算法具體描述如下：

①節(jié)點(diǎn)首先根據(jù)當(dāng)前的可用能量，判斷自己的狀態(tài)：如果處于活躍狀態(tài)和轉(zhuǎn)發(fā)狀態(tài)，則更新自己的地理位置，并進(jìn)行主動(dòng)掃描以發(fā)現(xiàn)自己的相鄰節(jié)點(diǎn)集合，廣播請(qǐng)求相鄰節(jié)點(diǎn)的效能參數(shù)，并計(jì)算相對(duì)綜合效能值；如果處于靜默狀態(tài)，則只更新地理位置信息，不進(jìn)行主動(dòng)掃描，只接受以本節(jié)點(diǎn)為目地節(jié)點(diǎn)的消息；如果節(jié)點(diǎn)處于死亡狀態(tài)，則不做任何操作。

②處于活躍狀態(tài)的節(jié)點(diǎn)，首先判斷是否緩存有以相鄰節(jié)點(diǎn)為目的節(jié)點(diǎn)的消息，若有，則直接向目地節(jié)點(diǎn)轉(zhuǎn)發(fā)給消息；對(duì)于非以鄰居節(jié)點(diǎn)為目地節(jié)點(diǎn)的消息，則根據(jù)該消息的副本攜帶的配額，依次向鄰居節(jié)點(diǎn)擴(kuò)散或轉(zhuǎn)發(fā)消息副本。若該消息副本配額大于1，則按比例擴(kuò)散消息；若該消息副本的配額為1，則選擇綜合效能最大的節(jié)點(diǎn)轉(zhuǎn)發(fā)該消息。

③處于轉(zhuǎn)發(fā)狀態(tài)的節(jié)點(diǎn)，同樣，首先判斷是否緩存有以相鄰節(jié)點(diǎn)為目的節(jié)點(diǎn)的消息，若有，則直接向目地節(jié)點(diǎn)轉(zhuǎn)發(fā)給消息；對(duì)于非以鄰居節(jié)點(diǎn)為目地節(jié)點(diǎn)的消息，選擇綜合效能最大的節(jié)點(diǎn)轉(zhuǎn)發(fā)該消息。該算法偽代碼描述如下：

在算法SERA中，由于節(jié)點(diǎn)不斷地接受相鄰節(jié)點(diǎn)的消息，會(huì)導(dǎo)致消息緩存區(qū)溢出，為此，SERA采用先進(jìn)先刪除策略對(duì)緩存區(qū)進(jìn)行覆蓋管理。此外，當(dāng)消息已成功傳遞到目的節(jié)點(diǎn)后，函數(shù)Broadcast（ms.ID，ACK）會(huì)將該消息的ACK向整個(gè)DTN網(wǎng)絡(luò)泛洪，以盡快通知各節(jié)點(diǎn)停止不必要的消息傳輸，以及釋放緩存區(qū)中存儲(chǔ)該消息的空間，從而提高系統(tǒng)資源利用率。

3 性能分析

3.1 參數(shù)設(shè)置

本文采用基于Java的DTN仿真工具ONE（Opportunistic Network Environment）［9］進(jìn)行仿真實(shí)驗(yàn)。采用與文獻(xiàn)［10］相同的能耗模型，能量衰減模型隨發(fā)送距離的遠(yuǎn)近分為自由空間模型和多路衰減模型：當(dāng)發(fā)送距離在一定閾值d0（d0為常量）內(nèi)，發(fā)送數(shù)據(jù)的功耗和距離的平方成正比；當(dāng)發(fā)送距離大于d0時(shí)，功耗和距離的四次方成正比，當(dāng)節(jié)點(diǎn)向距離d以外的另一個(gè)節(jié)點(diǎn)發(fā)送k個(gè)字節(jié)的數(shù)據(jù)時(shí)，其所消耗的能量由式（5）計(jì)算：

其中，Eelec表示收發(fā)電路所消耗的能量，Eamp表示信號(hào)放大器消耗的能量，∈fr和∈mp分別表示自由空間模型和多路衰減模型的放大器能耗。

節(jié)點(diǎn)接受數(shù)據(jù)所消耗的能量由式（6）計(jì)算得到。

為了驗(yàn)證本文算法的有效性，分別對(duì)Epidemic［5］、ESR［8］和SERA 3種算法分別從消息遞交成功率和網(wǎng)絡(luò)生存周期進(jìn)行對(duì)比。實(shí)驗(yàn)中參數(shù)設(shè)置如表1所示。節(jié)點(diǎn)是否產(chǎn)生消息包是隨機(jī)的，消息產(chǎn)生間隔為：25/s～35/s，節(jié)點(diǎn)的運(yùn)動(dòng)速度是隨機(jī)的，速度大小范圍：［0.5 m/s，14 m/s］，副本配額L=10。模擬真實(shí)傳感網(wǎng)環(huán)境的消息傳遞。

表1 實(shí)驗(yàn)參數(shù)列表

3.2 實(shí)驗(yàn)結(jié)果及分析

3種算法的消息遞交成功率隨著仿真時(shí)間推移變化情況如下頁圖1所示?？梢钥闯觯珽pidemic在6 000 s之前消息遞交成功率是最優(yōu)的，但是隨著仿真時(shí)間的增加，節(jié)點(diǎn)能量和緩存逐漸消耗，在8 000 s以后，其消息遞交成功率開始大幅度下降；SERA的消息遞交成功率率高于ESR，尤其是在10 000 s以后，由于ESR節(jié)點(diǎn)能量很大，SERA由于引入能量分級(jí)管理機(jī)制，很好地緩解了能量衰減過快節(jié)點(diǎn)的死亡，因此，SERA一直能保持70%以上的消息遞交成功率。

圖1 消息遞交成功率對(duì)比

網(wǎng)絡(luò)生命周期定義為當(dāng)前時(shí)間內(nèi)還能夠接受和發(fā)送消息的節(jié)點(diǎn)數(shù)，實(shí)驗(yàn)結(jié)果如圖2所示。SERA算法的網(wǎng)絡(luò)生存期比其他兩種算法都長。主要是由于SERA采用分級(jí)能量管理機(jī)制，當(dāng)節(jié)點(diǎn)能量低于能量閾值時(shí)進(jìn)入轉(zhuǎn)發(fā)模式，能夠有效地緩解節(jié)點(diǎn)能量的損耗；當(dāng)節(jié)點(diǎn)能量低于能量閾值一半時(shí)，節(jié)點(diǎn)只接受目標(biāo)節(jié)點(diǎn)為該節(jié)點(diǎn)的消息，因此，一方面能保證足夠高的消息遞交成功率，也能夠保證網(wǎng)絡(luò)具有比較高的生命周期。

圖2 網(wǎng)絡(luò)生命周期對(duì)比

4 結(jié)論

為了提高DTN網(wǎng)絡(luò)消息遞交成功率和延長網(wǎng)絡(luò)生命期，本文提出了一種基于節(jié)點(diǎn)綜合效能的DTN路由算法SERA。該算法通過設(shè)置合理的節(jié)點(diǎn)綜合效能模型和有效的節(jié)點(diǎn)消息復(fù)制和轉(zhuǎn)發(fā)策略，仿真實(shí)驗(yàn)結(jié)果驗(yàn)證了該路由算法能夠在消息遞交成功率和網(wǎng)絡(luò)生命周期方面取得比較好的均衡效果。消息副本配額的設(shè)置關(guān)系到消息復(fù)制和轉(zhuǎn)發(fā)的次數(shù)，如何設(shè)計(jì)更加合理的消息副本配額，使其在消息遞交延遲和網(wǎng)絡(luò)平均資源開銷等方面同時(shí)具有較優(yōu)的性能是下一步研究的方向。

［1］VIDYASAGAR P，ATIF S，ELIZABETH C.Wireless sensor networks：a survey［C］//International Conference on AdvancedInformationNetworkingandApplications Workshops.Bradford，United Kingdom，2009：636-641.

［2］LIU M J，YANG Y，QIN Z G.A survey of routing protocols and simulations in delay-tolerant networks［C］//Proceedings of the 6th International Conference on Wireless Algorithms，Systems，andApplications（WASA2011）.Berlin Heidelberg：Springer-Verlag，2011：243-253.

［3］ZHAO W，AMMAR M，ZEGURA E.A message ferrying approach for data delivery in sparse mobile ad hoc networks［C］//Proceedings of the 5th ACM International Symposium on Mobile Ad hoc Networking and Computing.New York：ACM，2004：187-198.

［4］DALY E，HAAHR M.Social network analysis for routing in disconnected delay-tolerant MANETs［C］//Proceedings of the 8th ACM International Symposium on Mobile ad hoc Networking and computing.New York：ACM，2007：32-40.

［5］VAHDAT A，BECKER D.Epidemic routing for partially connected ad hoc networks［R］.Durham，NC，USA：Duke University，2000.

［6］SPYROPOULOS T，PSOUNIS K，RAGHAVENDRA C S. Spray and wait：an efficient routing scheme for intermittently connected mobile networks［C］//Proceedings of the 2005 ACM SIGCOMM Workshop on Delay-tolerant Networking. New York：ACM，2005：252-259.

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

［8］ZHANG L J，GAO S A.Energy-aware multi-replica routing indelaytolerantmobilesensornetwork［J］.China Communications，2011（12）：87-97.

［9］KERANEN A，OTT J，KARKKAINEN T.The ONE simulator for DTN protocol evaluation［C］//SIMUTools’09：Proceedingsofthe2ndInternationalConferenceon Simulation Tools and Techniques，New York，NY，USA，2009.

［10］HEINZELMANWB，CHANDRAKASANAP，BALAKRISHNAN H.An application-specific protocol architecture for wireless microsensor networks［C］//IEEE Transactions on Wireless Communications，2002.

Synthetical Effectiveness Based DTN Routing Algorithm

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

Delay-Tolerant Network（DTN）is a type of new network characterized by long delay，frequent movement and low message delivery ratio.This paper presents a routing alogrithm based on synthetical effectiveness of nodes，called SERA.The SERA combines the activity of nodes with remaining energy，and sprays message copies to nodes with stronger synthetical effectiveness.In SERA，the node activity describes the social and dynamic characteristic of nodes.So，SERA tries to transfer message copies to nodes with higer activity in order to impove the success rate of message transimission.Furthermore，it can select nodes based on the energy state to avoid nodes without engouh energy to take on more transimisson tasks，thus protecting the survival of network nodes effectively. Simulation results show that SERA can balance the energy consumption of nodes better，and thus increase the sussess ratio of the message delivery and prolong the lifetime of WSN，compared with other typical routing algorithms.

synthetical effectiveness，DTN routing algorithm，node activity，energy state

TP316.4

A

1002-0640（2017）02-0119-05

2016-01-05

2016-02-24

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

鄭瑩（1977-），女，湖南常德人，副教授。研究方向：網(wǎng)絡(luò)安全、無線傳感網(wǎng)。