周朝榮，徐小瓊，楊 柳，馬小霞(. 四川師范大學物理與電子工程學院 成都 600；2. 無線傳感器網(wǎng)絡(luò)四川省高校重點實驗室 成都 600)

?

基于小世界與能效的容遲網(wǎng)絡(luò)路由算法

周朝榮1,2，徐小瓊1,2，楊 柳1，馬小霞1
(1. 四川師范大學物理與電子工程學院 成都 610101；2. 無線傳感器網(wǎng)絡(luò)四川省高校重點實驗室 成都 610101)

【摘要】容遲網(wǎng)絡(luò)(DTN)具有小世界特性，一條消息至多需要五至六跳中間節(jié)點就可從源節(jié)點到達目的節(jié)點。為此，算法(TBSF)結(jié)合小世界特性通過限制中間節(jié)點數(shù)目來提高消息的交付率，但該方法沒有考慮節(jié)點的能耗以及社會權(quán)威的問題。該文從節(jié)點能效與社會權(quán)威出發(fā)提出一種改進的算法。該算法設(shè)計了能量控制機制，并在擴展度中心性的基礎(chǔ)上討論節(jié)點的社會權(quán)威，在消息的轉(zhuǎn)發(fā)過程中突出權(quán)威節(jié)點的作用。仿真結(jié)果表明，該算法在保持較高消息交付率的同時能夠降低網(wǎng)絡(luò)的能耗。

關(guān) 鍵 詞度中心性； 容遲網(wǎng)絡(luò)； 能量控制； 小世界特性； 社會權(quán)威

A Routing Algorithm Based on Small World and Energy Efficiency in Delay Tolerant Network

ZHOU Zhao-rong1,2, XU Xiao-qiong1,2, YANG Liu1, and MA Xiao-xia1
(1. School of Physics and Electronic Engineering, Sichuan Normal University Chengdu 610101; 2. Key Laboratory of Wireless Sensor Networks, Sichuan Province Higher Education System Chengdu 610101)

Abstract Due to the small-world property in delay tolerant network (DTN), messages can reach destination nodes at most by five or six intermediate nodes. Therefore, the algorithm of the-best-so-far (TBSF) improved the delivery probability by limiting the number of intermediate nodes with the small-world property. Nevertheless, the issues of energy efficiency and social authority are not concerned in TBSF. In this paper, an enhanced algorithm is proposed by considering energy efficiency and social authority. The algorithm includes the energy control mechanism, considers the social authority of nodes by extending the degree centricity and highlights the role of nodes with higher social authority during forwarding messages. The corresponding simulation results show that the proposed algorithm can maintain the high message delivery probability and reduce the energy consumption..

Key words degree centricity; DTN; energy control; small-world property; social authority

DTN是一類特殊的移動自組織網(wǎng)絡(luò)，這類網(wǎng)絡(luò)具有拓撲變化快、傳輸時延高、間歇性連通等特點。任意節(jié)點對之間不一定存在端到端的即時通信路徑，消息在網(wǎng)絡(luò)中的傳播采用“存儲→攜帶→轉(zhuǎn)發(fā)”的路由機制。節(jié)點之間若要進行通信，需要借助相對運動所形成的通信機會。相應(yīng)地，路由算法成為這類網(wǎng)絡(luò)相關(guān)研究工作中的關(guān)鍵[1]。由于網(wǎng)絡(luò)帶寬資源以及消息生存時間的限制，經(jīng)歷多跳中間節(jié)點后依然滯留在網(wǎng)絡(luò)中的消息副本不僅無助于提升消息的交付率，反而會造成不必要的資源開銷。因此，需要在路由算法中考慮如何限制中間節(jié)點的數(shù)目。此外，由于便攜性的要求，移動節(jié)點設(shè)備的能量極其有限，路由算法的設(shè)計還需要兼顧節(jié)點的能量控制機制。這些問題在現(xiàn)有的路由算法中未能較好地解決，因此，還有深入研究路由算法的必要。

1 相關(guān)工作

近年來，研究人員針對DTN的不同應(yīng)用場景提出了多種路由算法。其中，泛洪路由算法Epidemic[2]基于消息的洪泛機制，可以實現(xiàn)較高的消息交付率，但同時產(chǎn)生了大量的消息副本，占用較多的網(wǎng)絡(luò)資源，容易造成網(wǎng)絡(luò)的堵塞。為了解決這一問題，文獻[3]提出了ProphetV2算法。該算法利用節(jié)點間相遇的歷史信息估算節(jié)點對消息的轉(zhuǎn)發(fā)概率，雖然消息交付率低于Epidemic算法，但極大地降低了網(wǎng)絡(luò)資源的開銷。需要說明的是，ProphetV2算法僅僅基于節(jié)點的歷史接觸信息，并未考慮節(jié)點的社會屬性。節(jié)點設(shè)備通常是人們所使用或攜帶的，人的行為具有社會屬性，對應(yīng)的節(jié)點設(shè)備也將表現(xiàn)出一定的社會屬性，因此，有必要從社會屬性的角度設(shè)計路由算法。Simbet算法[4]結(jié)合社會相似性與介數(shù)性指標，提出了如何選取合適的中間節(jié)點轉(zhuǎn)發(fā)消息。文獻[5]基于社團與中心性兩種指標提出了Bubble rap的轉(zhuǎn)發(fā)機制，該機制分別基于全局中心性與局部中心性采用冒泡過程實現(xiàn)消息的轉(zhuǎn)發(fā)。此外，考慮到便攜性的要求，節(jié)點設(shè)備的能量極其有限，路由算法中還需要兼顧能耗的問題。為此，文獻[6]在Bubble rap算法的基礎(chǔ)上給出了節(jié)點能量敏感的路由算法，該算法在估算轉(zhuǎn)發(fā)概率時引入能量模塊，將消息轉(zhuǎn)發(fā)給高能效的節(jié)點。需要指出的是，上述算法雖然在一定程度上降低了消息的傳輸時延、提高了交付率，但沒有限制消息轉(zhuǎn)發(fā)過程中的中間節(jié)點數(shù)目。根據(jù)小世界特性[7-8]，文獻[9]根據(jù)小世界特性提出了TBSF算法，該算法限制消息傳播過程中的中間節(jié)點數(shù)目，但沒有考慮節(jié)點的能耗以及社會權(quán)威等問題。本文將在TBSF算法的基礎(chǔ)上設(shè)計節(jié)點的能量控制機制并結(jié)合度中心性討論節(jié)點的社會權(quán)威，進一步地提出能效敏感的改進路由算法。

2 節(jié)點的社會權(quán)威與能量控制機制

2.1 節(jié)點權(quán)威性

在人類社會中，不同的人有著不同的社會屬性，比如不同的社會權(quán)威或者社會影響力，若能夠充分利用這類社會屬性，將有效地提高信息的傳播效率。在DTN中，節(jié)點設(shè)備的攜帶者通常為具有一定社會屬性的人，相應(yīng)地，由多個節(jié)點設(shè)備所構(gòu)成的網(wǎng)絡(luò)類似于人類社會，不同的節(jié)點設(shè)備體現(xiàn)不同的社會權(quán)威，在消息轉(zhuǎn)發(fā)的過程中發(fā)揮不同的作用?？坍嬌鐣?quán)威可以借助度中心性，定義為：

式中，ni表示與節(jié)點i直接相連的鄰居個數(shù)；K為網(wǎng)絡(luò)中的節(jié)點總數(shù)。節(jié)點的度中心性越高，意味著與該節(jié)點直接相連的鄰居節(jié)點數(shù)目越多，該節(jié)點就越有可能位于網(wǎng)絡(luò)的中心位置，也就具有更高的社會權(quán)威。相應(yīng)地，這類節(jié)點可在消息轉(zhuǎn)發(fā)的過程中扮演更加重要的角色。

需要指出的是，上述度中心性只考慮一跳鄰居節(jié)點的情況，這樣定義的社會權(quán)威僅僅涉及局部信息，不能全面地反映節(jié)點在整個網(wǎng)絡(luò)中的影響力。本文擴展上述度中心性的定義，除了一跳鄰居之外，還考慮其他多跳的鄰居。在同時考慮一跳與兩跳鄰居節(jié)點的前提下，擴展后的度中心性定義為：

式中，nk為節(jié)點k的鄰居節(jié)點個數(shù)；n(i , k )為節(jié)點i和k的共同鄰居節(jié)點數(shù)目。擴展后的度中心性能夠更加準確地反映節(jié)點在整個網(wǎng)絡(luò)的社會權(quán)威。

2.2 能量控制機制

為了降低節(jié)點的能量損耗并提高消息的交付率，按照如下的方法設(shè)計能量控制機制。首先，定義節(jié)點的當前可用能量比( ava_energyratio )以及能量比閾值(energy_threshold )為：

式中，current_energy為節(jié)點的當前能量；initial_energy為節(jié)點的初始能量；N為節(jié)點所攜帶的消息總數(shù)；mk為消息k的字節(jié)大?。籺ransmit_energy為傳輸每字節(jié)所需要的能量；e為基準的可用能量比。

對應(yīng)的能量控制機制為：

1) 若ava_energyratio< e，意味著節(jié)點的剩余能量不多，由于節(jié)點活躍需要耗能，為了增加節(jié)點的生存時間，節(jié)點只將消息轉(zhuǎn)發(fā)給相遇節(jié)點為消息目的地的節(jié)點。

3 結(jié)合能效的改進路由算法

3.1 算法思想

首先，比較相鄰節(jié)點的度中心性使消息盡量流向社會權(quán)威較高的節(jié)點；然后，根據(jù)小世界特性，控制消息轉(zhuǎn)發(fā)過程中的中間節(jié)點數(shù)目，減少網(wǎng)絡(luò)中的消息副本數(shù)量，提高帶寬的利用率；最后，通過比較鄰居節(jié)點的連接強度，將消息交給鄰居節(jié)點中連接強度大的節(jié)點進行轉(zhuǎn)發(fā)。

3.2 算法流程

在改進的算法中，首先初始化各條消息的跳數(shù)Hop= 0，消息每經(jīng)過一次中間節(jié)點的轉(zhuǎn)發(fā)，跳數(shù)Hop就加1。當Hop= 6時，為了抑制網(wǎng)絡(luò)中的消息副本數(shù)量，消息被丟棄。假設(shè)節(jié)點i攜帶有目的節(jié)點為d的一條消息，當節(jié)點i與另一節(jié)點j相遇，節(jié)點i根據(jù)以下的準則判斷是否將該消息轉(zhuǎn)發(fā)給節(jié)點j。

1) 若節(jié)點i的ava_energyratio小于e或者節(jié)點j的ava_energyratio小于energy_threshold，則節(jié)點i不向j轉(zhuǎn)發(fā)消息；否則，執(zhí)行下一步。

2) 若節(jié)點i的ava_energyratio小于energy_ threshold且大于等于e，連接強度P( j , d )大于為了不因能量耗盡而丟棄緩存中的消息，節(jié)點i將消息轉(zhuǎn)發(fā)給節(jié)點j。

3) 若節(jié)點i的ava_energyratio大于等于energy_threshold，節(jié)點有足夠的能量轉(zhuǎn)發(fā)消息，根據(jù)消息的Hop來決定是否將消息交由節(jié)點j轉(zhuǎn)發(fā)。

其中，連接強度的計算類似文獻[9]，完整的算法偽碼如下。

節(jié)點i向節(jié)點j轉(zhuǎn)發(fā)消息的偽代碼：if 節(jié)點i的可用能量比小于e or節(jié)點j的可用能量比小于能量閾值 then

continue else

for (節(jié)點i緩存中的消息) {

if 節(jié)點i的可用能量比小于能量閾值 &&

節(jié)點i向節(jié)點j轉(zhuǎn)發(fā)消息；

else if 節(jié)點i可用能量比不小于能量閾值 then

switch (節(jié)點i緩存消息的Hop )

case (Hop< 2 ) :

節(jié)點i向節(jié)點j轉(zhuǎn)發(fā)消息； break;

節(jié)點i向節(jié)點j轉(zhuǎn)發(fā)消息； break;

節(jié)點i向節(jié)點j轉(zhuǎn)發(fā)消息； break;

else

continue

end if

end for

end if

4 仿真結(jié)果分析

4.1 仿真場景

本文采用機會網(wǎng)絡(luò)環(huán)境(opportunistic network environment, ONE)仿真器[10]進行路由算法的仿真比較。為了使實驗更接近真實情況，采用MIT數(shù)據(jù)[11]、Pmtrs數(shù)據(jù)[12]以及Infocom06數(shù)據(jù)[13]3種真實的移動Trace。MIT數(shù)據(jù)記錄了97個持有智能手機Nokia6600的師生在9個月里的接觸信息；Pmtrs數(shù)據(jù)持續(xù)19天，通過49個移動軌跡記錄器記錄設(shè)備間的接觸信息；Infocom06數(shù)據(jù)來自于2006年某會議現(xiàn)場的數(shù)據(jù)收集，記錄了78個參會人員攜帶的藍牙設(shè)備以及20個靜止設(shè)備之間的接觸信息。

4.2 仿真參數(shù)設(shè)置

初始化基準的可用能量比為e =0.1，度中心性調(diào)節(jié)因子β=1.2，節(jié)點能耗的設(shè)置參考文獻[14]，此外，考慮到各個場景對應(yīng)著不同的仿真時長，對于仿真時長較高的場景，應(yīng)該允許更加寬松的消息生存時間，對應(yīng)的參數(shù)設(shè)置如表2所示。

表2　仿真參數(shù)設(shè)置

4.3 算法評價指標

為了比較路由算法的性能，評價指標如下：

1) 消息交付率，定義為網(wǎng)絡(luò)中成功轉(zhuǎn)發(fā)的消息數(shù)與產(chǎn)生的總消息數(shù)的比值，高的消息交付率意味著網(wǎng)絡(luò)中更多的消息能夠成功到達到目的節(jié)點，這是評價路由算法性能優(yōu)劣的最重要指標。

2) 網(wǎng)絡(luò)開銷，它是衡量網(wǎng)絡(luò)帶寬效率的重要指標，定義為成功轉(zhuǎn)發(fā)一條消息平均需要的消息副本數(shù)。開銷越大意味著消息副本越多，由于存儲轉(zhuǎn)發(fā)節(jié)點的資源有限而極易造成網(wǎng)絡(luò)傳輸性能的下降。

3) 能量損耗，考慮到節(jié)點能耗的因素，定義能量損耗指標為平均每節(jié)點成功交付一條消息所消耗的能量，計算為：

式中，cost_energy表示能量損耗；total_energy為網(wǎng)絡(luò)消耗的總能量；K為網(wǎng)絡(luò)中的節(jié)點總數(shù)；M為成功交付的消息數(shù)。能量損耗可用于評價路由算法在有限能量前提下的資源利用率。

4.4 仿真結(jié)果分析

基于上述真實移動Trace的場景，在不同消息生存周期下仿真比較了TBSF、ProphetV2以及本文提出的改進路由算法的網(wǎng)絡(luò)性能。

4.4.1 3種場景下的交付率

圖1～圖3分別給出MIT、Pmtrs以及Infocom06 在3種場景下的消息交付率，此處的TBSFMODI代表本文所提出的改進路由算法。從圖中可以看出，在不同的場景下，TBSFMODI的消息交付率均優(yōu)于ProphetV2與TBSF。這是由于TBSFMODI算法在度中心性的基礎(chǔ)上擴展了節(jié)點的社會權(quán)威，并在消息的轉(zhuǎn)發(fā)過程中突出權(quán)威節(jié)點的作用，從而使得消息在有限的跳數(shù)和生存時間內(nèi)更快地被轉(zhuǎn)發(fā)至目的節(jié)點。

圖1　MIT場景下的交付率

圖2　Pmtrs場景下的交付率

圖3　Infocom06場景下的交付率

4.4.2 3種場景下的網(wǎng)絡(luò)開銷

圖4~圖6分別給出3種場景下的網(wǎng)絡(luò)開銷。由于TBSFMODI考慮了容遲網(wǎng)絡(luò)的小世界特性，在消息轉(zhuǎn)發(fā)時限制消息的中間節(jié)點數(shù)目，降低了過多消息副本所帶來的網(wǎng)絡(luò)開銷，因此，TBSFMODI的網(wǎng)絡(luò)開銷明顯低于ProphetV2算法與TBSF算法。

圖4　MIT場景下的網(wǎng)絡(luò)開銷

圖5　Pmtrs場景下的網(wǎng)絡(luò)開銷

圖6　Infocom06場景下的網(wǎng)絡(luò)開銷

4.4.3 3種場景下的能量損耗

圖7~圖9展示了在3種場景下的能量損耗。結(jié)果表明，TBSFMODI的能量損耗均低于其他兩種算法。這是由于TBSFMODI算法設(shè)計了合理的能量控制機制，在消息轉(zhuǎn)發(fā)時根據(jù)節(jié)點當前剩余能量來設(shè)計消息轉(zhuǎn)發(fā)方式，并且針對消息的轉(zhuǎn)發(fā)跳數(shù)進行了更加細致的劃分，從而有效地減少了能量損耗。

圖7 MIT場景下的能量損耗

圖8　Pmtrs場景下的能量損耗

圖9　Infocom06場景下的能量損耗

5 結(jié) 束 語

本文針對容遲網(wǎng)絡(luò)中現(xiàn)有路由算法的不足，通過擴展度中心性討論節(jié)點的社會權(quán)威，并結(jié)合容遲網(wǎng)絡(luò)的小世界特性，在設(shè)計能量控制機制的基礎(chǔ)上，提出了改進的路由算法。進一步地，根據(jù)真實移動場景進行了仿真實驗。仿真結(jié)果表明，本文所提出的改進算法有著較好的系統(tǒng)性能，能夠在保持高交付率、低開銷的同時節(jié)省能量。

參 考 文 獻

[1] FALL K. A delay-tolerant network architecture for challenged internets[C]//Proceedings of the 2003 Conference on Applications, Technologies, Architectures, And Protocols for Computer Communications. Karlsruhe, Germany: ACM, 2003: 27-34.

[2] VAHDAT A, BECKER D. Epidemic routing for partially connected ad hoc networks[EB/OL]. [2014-10-10]. http:// link.springer.com/chapter/10.1007%2F978-3-540-27767-5_ 24.

[3] GRASIC S, DAVIES E, LINDGREN A, et al. The evolution of a DTN routing protocol-PRoPHETv2[C]//Proceedings of the 6th ACM Workshop on Challenged Network. Las Vegas, Nevada: ACM, 2011: 27-30.

[4] DALY E, HAAHR M. Social network analysis for routing in disconnected delay-tolerant MANET[C]//Proceedings of the 8th ACM International Symposium on Mobile Ad Hoc Networking and Computing. Montreal, Canada: ACM, 2007: 32-40.

[5] HUI P, CROWCROFT J, YONEKI E. Bubble rap: Social-based forwarding in delay-tolerant networks[J]. IEEE Transactions on Mobile Computing, 2011, 10(11): 1576-1589.

[6] CHILIPIREA C, PETRE A, DOBRE C. Energy-aware social-based routing in opportunistic networks[C]//27th International Conference on Advanced Information Networking and Applications Workshops (WAINA). Murcia, Spain: IEEE, 2013: 791-796.

[7] MILGRAM S. The small world problem[J]. Psychology Today, 1967, 2(1): 60-67.

[8] ANGELA S, FRANCESCO C, MARCELLO C. Human-mobility enabled networks in urban environments:Is there any (mobile wireless) small world out there?[J]. Ad Hoc Networks, 2012(10): 1520-1531.

[9] WEI K, ZENG D, GUO S, et al. Social-aware relay node selection in delay tolerant networks[C]//22nd International Conference on ICCCN: Computer Communications and Networks. Nassau, Bahamas: IEEE, 2013: 1-7.

[10] KERANEN A, OTT J, KARKKAINEN T. The one simulator for DTN protocol evaluation[C]//Proceedings of the 3rd International ICST Conference on Simulation Tools and Techniques. Arizona, USA: IEEE, 2009.

[11] EAGLE N, PENTLAND A. Reality mining: Sensing complex social systems[J]. Personal and Ubiquitous Computing, 2006, 10(4): 255-268.

[12] MERONI P, GAITTO S, PAGANI E, et al, Data setunimi/pmtr[DB/OL]. [2014-09-30]. http://crawdad.cs. dartmouth.edu /unimi/pmtr, Dec. 2008.

[13] SCOTT J, GASS R, CROWCROFT J, HUI P, et al. DataSetCambridge/haggle/imote/infocom2006[DB/OL]. [2009-05-29].http://crawdad.cs.d-artmouth.edu/cambridge/ haggle/imote/infocom2006, May 2009.

[14] DERANGO F, AMELIO S, FAZIO P. Enhancements of epidemic routing in delay tolerant networks from an energy perspective[C]//9th International Wireless Communications and Mobile Computing Conference (IWCMC). Valencia, Italy: IEEE, 2013: 731-735.

編 輯 葉 芳

作者簡介：周朝榮(1975 ? )，男，博士，副教授，主要從事無線網(wǎng)絡(luò)方面的研究.

基金項目：四川省教育廳重點項目(14ZA0033, 15CZ0004)；無線傳感器網(wǎng)絡(luò)四川省高校重點實驗室開放項目(SCWSN201404)

收稿日期：2015 ? 01 ? 10；修回日期： 2015 ? 10 ? 30

中圖分類號TP393

文獻標志碼A

doi:10.3969/j.issn.1001-0548.2016.01.022