萬(wàn) 冰

（摩托羅拉系統(tǒng)（中國(guó)）有限公司 成都分公司，四川 成都 611731）

基于社會(huì)環(huán)境的一種優(yōu)化Prophet延遲容忍網(wǎng)絡(luò)路由算法

萬(wàn) 冰

（摩托羅拉系統(tǒng)（中國(guó)）有限公司 成都分公司，四川 成都 611731）

在移動(dòng)智能終端普及的今天，延遲容忍網(wǎng)絡(luò)作為數(shù)據(jù)的補(bǔ)充傳輸方案具有重要的意義。在社會(huì)環(huán)境中，節(jié)點(diǎn)移動(dòng)規(guī)律具有明顯周期性，Prophet路由算法在該類(lèi)場(chǎng)景中效果較好。因此文章提出了一種基于加強(qiáng)傳統(tǒng)概率的路由算法，其在工作日模型下對(duì)E Prophet算法進(jìn)行了仿真實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，所提出的E Prophet算法在該場(chǎng)景下優(yōu)于傳統(tǒng)的Prophet算法。

延遲容忍網(wǎng)絡(luò)；社會(huì)環(huán)境；移動(dòng)規(guī)律；路由算法

延遲容忍網(wǎng)絡(luò)（（Delay Tolerant Network，DTN））又稱(chēng)為容斷或容遲網(wǎng)絡(luò)，由多個(gè)移動(dòng)對(duì)象攜帶具備無(wú)線(xiàn)通信能力的傳感器組成[1]。在延遲容忍網(wǎng)絡(luò)中數(shù)據(jù)利用節(jié)點(diǎn)之間相遇的機(jī)會(huì)進(jìn)行轉(zhuǎn)發(fā)，因此這種“存儲(chǔ)—攜帶—轉(zhuǎn)發(fā)”的傳輸方式可以較少地依賴(lài)于基礎(chǔ)設(shè)施，網(wǎng)絡(luò)中的鏈接頻繁中斷[2]。因此從延遲容忍網(wǎng)絡(luò)出現(xiàn)就廣泛圍繞挑戰(zhàn)性環(huán)境中的應(yīng)用討論，如戰(zhàn)場(chǎng)環(huán)境[3]、車(chē)輛交通環(huán)境[4]、水下場(chǎng)景[5]等。隨著智能移動(dòng)終端的普及，在城市區(qū)域中利用移動(dòng)智能終端所構(gòu)建的延遲容忍網(wǎng)絡(luò)具有傳輸成本低、移動(dòng)性支持好、對(duì)通信基礎(chǔ)設(shè)施需求較低等優(yōu)勢(shì)。不同場(chǎng)景中節(jié)點(diǎn)的移動(dòng)規(guī)律不一致，導(dǎo)致現(xiàn)有的延遲容忍網(wǎng)絡(luò)路由算法不能在城市場(chǎng)景中發(fā)揮網(wǎng)絡(luò)應(yīng)有的性能[6]。

前期研究表面，社會(huì)環(huán)境中節(jié)點(diǎn)具有一定的周期移動(dòng)規(guī)律性，所以基于概率預(yù)測(cè)的Prophet在社會(huì)環(huán)境中具有較好的表現(xiàn)[7]。

為了提升延遲容忍網(wǎng)絡(luò)在城市環(huán)境中的性能表現(xiàn)，本文提出一種適用于社會(huì)環(huán)境的優(yōu)化Prophet路由算法（Enhanced Prophet，E Prophet），E Prophet算法中的衰老因子符合城市環(huán)境中節(jié)點(diǎn)的相遇規(guī)律。本文利用工作日模型（Working Day Mode，WDM），建立了趨于真實(shí)社會(huì)環(huán)境節(jié)點(diǎn)的移動(dòng)狀態(tài)，并在多次實(shí)驗(yàn)的基礎(chǔ)上，觀(guān)察了隨時(shí)間變化下兩種算法在社會(huì)環(huán)境中的網(wǎng)絡(luò)關(guān)鍵性能指標(biāo)，并對(duì)結(jié)果進(jìn)行了相關(guān)的分析。

1 Prophet路由算法簡(jiǎn)介

Prophet算法由A·Lindgren等[8]提出，其基本思想是在節(jié)點(diǎn)中加入冗余知識(shí)，以便記錄節(jié)點(diǎn)之間的相遇概率。在Prophet算法中，每個(gè)節(jié)點(diǎn)都存在一個(gè)概率據(jù)測(cè)矩陣，依據(jù)所設(shè)計(jì)的策略進(jìn)行概率預(yù)測(cè)值的更新。如節(jié)點(diǎn)a與節(jié)點(diǎn)b的相遇概率定義如式1所示。

其中P(a,b)old表示上一個(gè)狀態(tài)的相遇概率，Pinit表示初始化概率。在算法中狀態(tài)值P(a,b)s1與P(a,b)s2分別表示兩個(gè)時(shí)間狀態(tài)下節(jié)點(diǎn)之間概率預(yù)測(cè)值。狀態(tài)S1，S2兩個(gè)狀態(tài)之間預(yù)測(cè)值變化函數(shù)，它基于算法中所設(shè)計(jì)的衰老因子γ的設(shè)計(jì)。當(dāng)節(jié)點(diǎn)a與節(jié)點(diǎn)b分開(kāi)后，由于衰老因子的存在，導(dǎo)致兩個(gè)節(jié)點(diǎn)之間的概率預(yù)測(cè)值持續(xù)減少。其衰減計(jì)算函數(shù)如式2所示。

式中γk因子是一個(gè)冪指數(shù)函數(shù)，其中0＜γ＜1，k為與時(shí)間相關(guān)整數(shù)。由于冪指數(shù)的存在，隨著時(shí)間的增加節(jié)點(diǎn)之間概率預(yù)測(cè)值會(huì)持續(xù)降低。通過(guò)這樣的設(shè)計(jì)，相互接觸較為頻繁的節(jié)點(diǎn)，其概率預(yù)測(cè)值會(huì)維持一個(gè)較為高的預(yù)測(cè)值。在社會(huì)環(huán)境中，由于節(jié)點(diǎn)之間的存在的社會(huì)屬性，因此可以用社交圖（Social Graph）（見(jiàn)圖1）表現(xiàn)節(jié)點(diǎn)之間的接觸或社交情況[9]。

圖1 社會(huì)環(huán)境中節(jié)點(diǎn)社交

基于圖1社會(huì)環(huán)境中的社交圖可以發(fā)現(xiàn)，在網(wǎng)絡(luò)中節(jié)點(diǎn)之間的接觸規(guī)律受制于節(jié)點(diǎn)的社交圈。而在社會(huì)網(wǎng)絡(luò)中社交圈的存在，也表明了節(jié)點(diǎn)與節(jié)點(diǎn)之間的接觸概率并不服從均勻分布。由此，Prophet算法中的概率預(yù)測(cè)方式，在社會(huì)環(huán)境的延遲容忍網(wǎng)絡(luò)中符合節(jié)點(diǎn)的相遇規(guī)則，因此也可以得到較好的表現(xiàn)。

2 Prophet算法在社會(huì)環(huán)境下延遲容忍網(wǎng)絡(luò)中的問(wèn)題

基于概率預(yù)測(cè)的Prophet算法從提出到現(xiàn)在并沒(méi)有針對(duì)的場(chǎng)景，但是其概率預(yù)測(cè)的方式，較為適應(yīng)一些具有相遇規(guī)律的場(chǎng)景，因此在基于社會(huì)網(wǎng)絡(luò)的延遲容忍網(wǎng)絡(luò)中，得到了眾多學(xué)者的關(guān)注[10]。在社會(huì)環(huán)境中，具有通信能力的移動(dòng)節(jié)點(diǎn)往往由移動(dòng)智能終端與攜帶智能終端的車(chē)輛等組成，因此移動(dòng)節(jié)點(diǎn)同樣具有社會(huì)屬性。在社會(huì)環(huán)境中，白天人們活動(dòng)，具有一定的目的性與規(guī)律性，如上班、逛街等。晚上人們?cè)诩倚菹⒒顒?dòng)范圍局限在一個(gè)較小的范圍當(dāng)中，甚至不移動(dòng)。這也就構(gòu)成了社會(huì)環(huán)境中節(jié)點(diǎn)移動(dòng)的基本規(guī)律。通過(guò)Infocom數(shù)據(jù)集（41節(jié)點(diǎn)）在72小時(shí)采集的相遇數(shù)據(jù)如圖2所示。

圖2 Infocom數(shù)據(jù)集在72小時(shí)的相遇規(guī)律

基于圖1可以看到，節(jié)點(diǎn)在不同的時(shí)間段中相遇次數(shù)具有較大的差別。節(jié)點(diǎn)相遇具有一定的周期性。在一個(gè)周期中，節(jié)點(diǎn)具有高相遇次數(shù)期間與低相遇次數(shù)期間。低相遇次數(shù)期間，網(wǎng)絡(luò)中節(jié)點(diǎn)總體的相遇次數(shù)趨近于零，這也是人們晚上休息所導(dǎo)致的。在高相遇次數(shù)期間，節(jié)點(diǎn)相遇次數(shù)出現(xiàn)了較大的波動(dòng)，可以理解為在社會(huì)環(huán)境中人們的早高峰與晚高峰。從周期上面看，其總體的相遇規(guī)律可以由式3所示。

fn(t)=f(t+NT) （3）

其中，fn(t)表示在當(dāng)前時(shí)間網(wǎng)絡(luò)中節(jié)點(diǎn)相遇次數(shù)，N為整數(shù)，T為12小時(shí)常量。可以看到，在低相遇期間，時(shí)間持續(xù)較長(zhǎng)為12小時(shí)，因此在Prophet路由算法中，由于如式2中衰老因此的存在，預(yù)測(cè)矩陣中節(jié)點(diǎn)之間的預(yù)測(cè)概率值，會(huì)在這個(gè)低相遇次數(shù)周期中由于節(jié)點(diǎn)間相遇次數(shù)的減少而持續(xù)降低。當(dāng)節(jié)點(diǎn)相遇次數(shù)再次進(jìn)入到高相遇周期時(shí)，節(jié)點(diǎn)之間的預(yù)測(cè)概率值都處于一個(gè)較低的水平，節(jié)點(diǎn)之間的預(yù)測(cè)概率需要一個(gè)重新收斂的過(guò)程。因此，Prophet算法在社會(huì)場(chǎng)景中，無(wú)法較好地適應(yīng)這種節(jié)點(diǎn)的相遇周期，影響了算法的性能發(fā)揮。

3 一種優(yōu)化的E Prophet路由算法

基于Prophet在社會(huì)環(huán)境中無(wú)法較好適應(yīng)低相遇次數(shù)周期與高次數(shù)相遇周期的問(wèn)題，文章提出了一種優(yōu)化的Prophet路由算法。重新設(shè)計(jì)了衰老因子的策略方式。同樣路由算法基于節(jié)點(diǎn)之間相遇的情況，其算法的描述如下。

步驟1：網(wǎng)絡(luò)中全體節(jié)點(diǎn)建立相遇概率矩陣E，以存儲(chǔ)全體網(wǎng)絡(luò)節(jié)點(diǎn)的預(yù)測(cè)概率值。

步驟2：基于式1進(jìn)行相遇概率連續(xù)狀態(tài)的更新。

步驟3：基于式4進(jìn)行相遇概率衰減。

式中，T1表示在低相遇次數(shù)周期中時(shí)間，反之T2表示在高相遇周期中時(shí)間。衰老方式計(jì)算在不同節(jié)點(diǎn)所處時(shí)間段中存在區(qū)別。其中K1與K2如式5—6所示。

式中tnow表示網(wǎng)絡(luò)運(yùn)行的當(dāng)前時(shí)間，tT為上一更新時(shí)間，β為常量。

其中定義時(shí)間周期判斷(tnow/Thour)/δ為真時(shí)，為T(mén)2時(shí)間區(qū)間，反之亦然。

4 仿真環(huán)境與實(shí)驗(yàn)結(jié)果

由于真實(shí)數(shù)據(jù)集的節(jié)點(diǎn)過(guò)少，或部分真實(shí)數(shù)據(jù)集節(jié)點(diǎn)移動(dòng)范圍過(guò)小，因此這里選擇由F.EKman等提出的工作日模型（Working Day Movement Model，WDM）[11]。

其仿真場(chǎng)景中節(jié)點(diǎn)分組如表1所示。

表1 節(jié)點(diǎn)分組類(lèi)型

仿真場(chǎng)景中選擇了其關(guān)鍵仿真參數(shù)如表2所示。

表2 關(guān)鍵仿真參數(shù)

設(shè)置與社交環(huán)境較為近似的仿真場(chǎng)景后，對(duì)延遲容忍網(wǎng)絡(luò)中關(guān)鍵指標(biāo)如網(wǎng)絡(luò)投遞成功率、平均投遞延遲與網(wǎng)絡(luò)負(fù)載比3個(gè)關(guān)鍵指標(biāo)與傳統(tǒng)Prophet指標(biāo)進(jìn)行對(duì)比分析如圖3—5所示，以觀(guān)察優(yōu)化的Prophet算法與Prophet算法性能。

圖3 兩種算法的網(wǎng)絡(luò)投遞成功率

圖4 兩種算法的平均投遞延遲

圖5 兩種算法的網(wǎng)絡(luò)負(fù)載比

通過(guò)兩種算法在3種延遲容忍網(wǎng)絡(luò)的關(guān)鍵指標(biāo)中對(duì)比發(fā)現(xiàn)，所提出的E Prophet路由算法在社會(huì)環(huán)境中明顯優(yōu)于原始的Prophet算法。由于WDM模型中節(jié)點(diǎn)相遇分布在時(shí)間維度的劇烈波動(dòng)，也導(dǎo)致了3種指標(biāo)隨著時(shí)間出現(xiàn)了較為劇烈的波動(dòng)。

5 結(jié)語(yǔ)

隨著智慧城市的發(fā)展，社會(huì)環(huán)境中對(duì)數(shù)據(jù)的需求具有多種多樣的解決方案，而延遲容忍網(wǎng)絡(luò)作為數(shù)據(jù)傳輸?shù)囊环N解決方案具有移動(dòng)性支持強(qiáng)、成本低、系統(tǒng)抗災(zāi)性強(qiáng)的特點(diǎn)。文章提出的E Prophet算法一定程度上提升了Prophet算法在社會(huì)環(huán)境中延遲容忍網(wǎng)絡(luò)的系統(tǒng)性能，有利于提高基于延遲容忍網(wǎng)絡(luò)的應(yīng)用系統(tǒng)的性能。

[1]GAO L, YU S, LUAN T H, et al. Routing Protocols in Delay Tolerant Networks[M].German：Springer International Publishing, 2015.

[2]MAYER C P, WALDHORST O P. Offloading Infrastructure Using Delay Tolerant Networks and Assurance of Delivery[J]. Jochen Furthmüller, 2011（1）：1-7.

[3]DINI G, DUCA A L. Towards a reputation-based routing protocol to contrast blackholes in a delay tolerant network[J]. Ad Hoc Networks, 2012（7）：1167-1178.

[4]UCHIDA N, ITO K, HIRAKAWA G, et al. Vehicle-to-Vehicle Delay Tolerant Networks with Area of Interest for Road Surveillance System[C]. Poland：International Conference on Broadband and Wireless Computing, Communication and Applications[A] .Computer Society, 2015：466-471.

[5]劉燦.容延容斷網(wǎng)絡(luò)中基于負(fù)載均衡的路由算法的研究[D].長(zhǎng)沙：國(guó)防科學(xué)技術(shù)大學(xué)，2011.

[6]李文藻，林鋒.節(jié)點(diǎn)緩沖區(qū)大小對(duì)城市部署的DTN網(wǎng)絡(luò)的影響分析[J].無(wú)線(xiàn)互聯(lián)科技，2014（10）：117-119.

[7]MOREIRA W，F(xiàn)ERREIRA R，CIRQUEIRA D，et al. SocialDTN：a DTN implementation for digital and social inclusion[C].ACM MOBICOM Workshop on Lowest Cost Denominator NETWORKING for Universal Access. ACM，2013：25-28.

[8]LINDGREN A, DORIA A, SCHELéN O. Probabilistic Routing in Intermittently Connected Networks[J]. Acm Sigmobile Mobile Computing & Communications Review, 2004（3）：19-20.

[9]BONNEAU J, ANDERSON J, ANDERSON R, et al. Eight friends are enough：social graph approximation via public listings[J]. ACM EUROSYS Workshop on Social Network Systems, 2009（3）：13-18.

[10]SCHURGOT M R, COMANICIU C, JAFFRES R K. Beyond traditional DTN routing: social networks for opportunisticcommunication[J]. Communications Magazine, 2012（7）：155- 162.

[11]EMAN F, KER, NEN A, et al.Working day movement model[C].ACM Wi-Fi Multimedia, 2008：33-40.

An optimized Prophet delay tolerant network routing algorithm based on social environment

Wan Bing
（Chengdu Branch of Motorola Systems（China）Co., Ltd., Chengdu 611731, China）

With the popularity of the mobile terminal today, as a supplement to the data transmission project, delay tolerant network is of great significance. In the social environment, node movement law has obvious periodic node movement, prophet routing algorithm has better effect in the scene. Therefore, this paper proposes a kind of routing algorithm based on .strengthening traditional probability. The E Prophet algorithm is simulated under the mode during the working day.The simulation results show that the proposed E Prophet algorithm is superior to the traditional Prophet algorithm in this scenario.

delay tolerant network; social environment; movement law; routing algorithm

四川省科技廳軟科學(xué)項(xiàng)目；項(xiàng)目編號(hào)：2014ZR0146。四川省教育廳重點(diǎn)項(xiàng)目；項(xiàng)目編號(hào)：16ZA0218。

萬(wàn)冰（1978— ），女，四川成都，碩士；研究方向：計(jì)算機(jī)通信與網(wǎng)絡(luò)研究設(shè)計(jì)。