帶有相遇預測的自適應路由機制

吳大鵬，楊正川，劉喬壽，王汝言

(重慶郵電大學寬帶泛在接入技術(shù)研究所，重慶400065)

0 引言

機會網(wǎng)絡［1］的拓撲結(jié)構(gòu)具有極強的動態(tài)性，源節(jié)點和目的節(jié)點間不存在完整的端到端路徑，鏈路頻繁中斷特性，因此，消息傳輸過程的延時較高。為了充分利用節(jié)點運動過程與其他節(jié)點相遇的機會，機會網(wǎng)絡以“存儲、攜帶、轉(zhuǎn)發(fā)”的方式來進行消息的傳遞。

可見，路由機制是機會網(wǎng)絡的關(guān)鍵技術(shù)之一。針對機會網(wǎng)絡的特性，研究人員提出了相應的路由機制。按照是否對消息進行復制，可以把現(xiàn)有的路由算法分為單副本路由和多副本路由。單副本路由協(xié)議中，節(jié)點將消息副本轉(zhuǎn)發(fā)給另一個節(jié)點后，本身將不再保存該消息，即每個消息在網(wǎng)絡中始終都只有一個副本。單副本路由機制能夠有效地降低消息傳輸過程所產(chǎn)生的開銷，但通常投遞率都不高，延時也比較大。相比之下，通過多個副本在網(wǎng)絡中的泛洪，多副本路由協(xié)議有效地提高了網(wǎng)絡中消息投遞成功的概率。

Epidemic［2］是一種消息副本數(shù)不受限制的多副本路由協(xié)議。節(jié)點將自身所攜帶的消息復制并傳遞給與之相遇的所有節(jié)點，通過無限制的泛洪以達到最大化投遞成功率和最小化投遞延時的目的，但網(wǎng)絡中存在大量的冗余副本，造成嚴重的網(wǎng)絡擁塞和資源競爭。Prophet［3］是一種受限的泛洪路由算法。節(jié)點首先估計到達目的節(jié)點的傳遞概率，并利用概率傳遞性來為消息選擇相應的中繼節(jié)點。

噴灑等待(spray and wait，SnW)路由機制［4］預先計算并限定了網(wǎng)絡中消息副本的數(shù)量，只進行固定數(shù)量的副本傳輸，有效地減少了因消息過度復制所造成的資源浪費和競爭，該算法分為噴灑階段和等待階段。在噴灑階段，源節(jié)點產(chǎn)生L個消息副本，當擁有n(n＞1)個消息副本的節(jié)點A與節(jié)點B相遇時，會將一個(source spray and wait)或者一半(binary spray and wait)消息副本傳遞給節(jié)點B。當n=1時，進入等待階段，該階段節(jié)點會一直攜帶該消息副本直到遇到目標節(jié)點。

顯然，最佳中繼節(jié)點的選擇是設(shè)計高效機會網(wǎng)絡路由協(xié)議的關(guān)鍵問題。噴灑等待路由在選擇中繼節(jié)點時，并未考慮相遇節(jié)點之間的差異，具有一定的盲目性。針對這個方面的問題，本文提出了一種帶有相遇預測的自適應路由機制(adaptive routing mechanism with encounter prediction，EP－ARM)，通過動態(tài)地感知網(wǎng)絡中其他節(jié)點的狀態(tài)信息，節(jié)點實現(xiàn)自適應的消息轉(zhuǎn)發(fā)決策，以達到合理的選擇中繼節(jié)點并提高網(wǎng)絡資源利用率的目的。

1 帶有相遇預測的自適應路由機制

1.1 轉(zhuǎn)發(fā)策略分析

研究表明，消息的副本數(shù)越多，其被成功投遞的概率就越大［5］。多副本路由機制的本質(zhì)是對消息進行多次復制，以使得多個副本能夠通過不同路徑進行轉(zhuǎn)發(fā)，從而提高消息的投遞成功率。當消息的副本數(shù)有限時，路由協(xié)議的性能取決于消息副本的轉(zhuǎn)發(fā)策略的合理性。

SnW中提出的源端噴灑(source spray)和二元噴灑(binary spray)兩種噴灑方案都沒有考慮到不同節(jié)點間相遇概率的差別，因此在消息轉(zhuǎn)發(fā)決策的時候有盲目性。QoN－BSW［6］根據(jù)相遇節(jié)點的個數(shù)來計算節(jié)點質(zhì)量(quality of node，QoN)，并根據(jù)QoN的差異進行轉(zhuǎn)發(fā)決策;DHN－SaW［7］根據(jù)相遇節(jié)點的歷史狀態(tài)來決定轉(zhuǎn)發(fā)的副本數(shù)。QoN－BSW和DHNSaW雖然考慮了本地節(jié)點的轉(zhuǎn)發(fā)能力，卻沒有將相遇節(jié)點進行區(qū)分。DPER［8］將網(wǎng)絡簡化為只有兩跳的虛擬網(wǎng)絡，根據(jù)與目標節(jié)點的相遇概率的差異以選擇中繼節(jié)點，但與目標節(jié)點的相遇概率并不能準確地反映節(jié)點的轉(zhuǎn)發(fā)能力。

在拓撲結(jié)構(gòu)多變的機會網(wǎng)絡中，如果不能充分利用節(jié)點的特性，其轉(zhuǎn)發(fā)決策可能并不合理。為了準確地量化節(jié)點的轉(zhuǎn)發(fā)能力，EP－ARM綜合考慮了節(jié)點與目標節(jié)點的相遇概率以及與歷史相遇節(jié)點的相遇概率，通過動態(tài)地感知網(wǎng)絡中節(jié)點的信息，自適應地選擇轉(zhuǎn)發(fā)能力高的節(jié)點作為中繼節(jié)點。

EP－ARM主要包含兩個過程:網(wǎng)絡狀態(tài)感知和消息轉(zhuǎn)發(fā)決策。與多數(shù)路由協(xié)議類似，本文所提出的路由策略中，當兩個節(jié)點相遇之后，需要交換消息概要向量以及本地所收集的相關(guān)信息。然后，節(jié)點通過交換所得的信息進行消息轉(zhuǎn)發(fā)決策。

1.2 網(wǎng)絡狀態(tài)感知

機會網(wǎng)絡中的節(jié)點按照一定的規(guī)律進行運動，節(jié)點運動過程中將記錄與其他節(jié)點的相遇信息，進而根據(jù)歷史數(shù)據(jù)預測節(jié)點間的相遇概率;同時，相應的預測結(jié)果需要隨著節(jié)點間的每一次相遇進行更新。顯然，若兩個節(jié)點相遇頻繁，則表明它們的相遇概率就高。當任意節(jié)點A與節(jié)點B相遇后，相應的相遇概率按照(1)式進行更新。

(1)式中:P(a，b)表示節(jié)點A與節(jié)點B的相遇概率;P(a，b)old表示更新之前節(jié)點A與節(jié)點B的相遇概率;Pinit表示初始概率。

相遇概率會隨著時間的變化而更新，若節(jié)點A和節(jié)點B在較長時間內(nèi)沒有再次相遇，則表明兩者之間的相遇概率在隨時間衰減，其更新過程如(2)式所示。

(2)式中:γ∈(0，1)是衰減系數(shù);k表示自從上一次相遇到現(xiàn)在所經(jīng)歷的時間單位。

如果節(jié)點與其他節(jié)點的相遇越頻繁，則該節(jié)點轉(zhuǎn)發(fā)消息的機會就越多，也就是該節(jié)點的轉(zhuǎn)發(fā)能力越強。為了量化節(jié)點的轉(zhuǎn)發(fā)能力，本文定義并記錄節(jié)點活躍度E(a，b)，其計算方式如(3)式所示。

(3)式中，E(a，b)表示任意節(jié)點A中所記錄的節(jié)點B的活躍度，其值越大，則節(jié)點B就越活躍，與其他節(jié)點的相遇概率就越高。在記錄節(jié)點活躍度E(a，b)的同時，需同時標記它的記錄時間t(a，b)，并與其他節(jié)點進行比較，以更新節(jié)點活躍度和記錄時間。

機會網(wǎng)絡的拓撲結(jié)構(gòu)具有較強的時變性，節(jié)點中所保存的信息不可能實時地反映當前網(wǎng)絡狀態(tài)。按照機會網(wǎng)絡中消息轉(zhuǎn)發(fā)過程基本原理，節(jié)點相遇之后需要交換各自的本地信息，以動態(tài)地感知網(wǎng)絡中其他節(jié)點的信息。當節(jié)點A和節(jié)點B進入通信范圍后，節(jié)點A首先根據(jù)(1)式和(2)式更新本地保存的相遇概率信息，并根據(jù)(3)式更新節(jié)點活躍度E(a，b)。然后，節(jié)點A與節(jié)點B比較節(jié)點性能的記錄時間，若 t(a，i)＜ t(b，i)，則 E(a，i)=E(b，i)。

1.3 消息轉(zhuǎn)發(fā)決策

在消息轉(zhuǎn)發(fā)決策階段，節(jié)點根據(jù)網(wǎng)絡狀態(tài)感知階段所得到的信息，利用相遇概率和節(jié)點活躍度的差異進行消息的轉(zhuǎn)發(fā)決策。本文所提出的機制中，為了減少消息低效率洪泛，節(jié)點有限制性地將消息轉(zhuǎn)發(fā)給活躍度高于自身的節(jié)點。

對于任意節(jié)點A，定義Qa為節(jié)點A的轉(zhuǎn)發(fā)能力。該參數(shù)綜合考慮了節(jié)點與目標節(jié)點的相遇概率，以及歷史相遇節(jié)點的相遇概率和節(jié)點活躍度，其計算如(4)式所示。

(4)式中:C為所有節(jié)點的集合;α為權(quán)重系數(shù)。

對于節(jié)點A中目標節(jié)點為iD的消息，若當前副本數(shù)為La，則轉(zhuǎn)發(fā)給任意相遇節(jié)點B的副本數(shù)Lb如(5)式所示。

轉(zhuǎn)發(fā)能力強的節(jié)點將被分配更多的消息副本，以獲得更多的轉(zhuǎn)發(fā)機會。

帶有相遇預測的自適應路由機制的偽代碼如下所示。

當任意節(jié)點A和節(jié)點B建立連接后，首先根據(jù)(1)式和(2)式更新相遇概率，并根據(jù)(3)式更新節(jié)點活躍度;然后，相互交換并更新消息概要向量以及本地所感知的相關(guān)網(wǎng)絡狀態(tài)信息;最后，若節(jié)點A中的消息副本數(shù)La＞1，則根據(jù)(4)式和(5)式計算得到的副本數(shù)進行轉(zhuǎn)發(fā)決策，確定是否將消息轉(zhuǎn)發(fā)給節(jié)點B以及轉(zhuǎn)發(fā)的副本數(shù);若La=1，則進入等待階段，直至與目的節(jié)點相遇。

2 性能分析

本文利用機會網(wǎng)絡環(huán)境(opportunistic network environment，ONE)［9］對所提出的機制進行驗證。為了充分體現(xiàn)所提出機制具有較強的實際應用價值，本文選取Infocom06數(shù)據(jù)集中的實測數(shù)據(jù)作為節(jié)點運動軌跡。

2.1 數(shù)據(jù)模型及參數(shù)

相關(guān)參數(shù)設(shè)置如表1所示。

表1 仿真參數(shù)表Tab.1 Parameter settings

仿真中關(guān)于路由決策計算的相關(guān)參數(shù)分別設(shè)置為 Pinit=0.75;β =0.25;γ =0.98;α =0.85。

2.2 結(jié)果分析

為了全面驗證EP－ARM算法的性能，本文使用了3個性能評估參數(shù):投遞延時、投遞率和投遞開銷。投遞延時表示從消息產(chǎn)生到最終被投遞到目標節(jié)點所需的平均時間;投遞率表示最終投遞成功的消息占產(chǎn)生消息總數(shù)的比例;投遞開銷則定義為未成功投遞的消息副本總數(shù)和成功投遞的消息數(shù)量的比值。對于消息副本數(shù)不同的情況下，本文對提出的路由協(xié)議上述3個方面的性能進行了比較和分析，結(jié)果分別如圖1－圖3所示。

圖1 投遞延時Fig.1 Delivery latency

圖2 投遞率Fig.2 Delivery probability

圖3 投遞開銷Fig.3 Delivery overhead

由圖1可以看出，本文所提出的路由投遞延時明顯低于SnW路由。由于EP－ARM在中繼節(jié)點的選擇上更加合理，這樣可以使消息迅速地被轉(zhuǎn)發(fā)到目標節(jié)點。相比于SnW路由的盲目洪泛，選擇合適的中繼節(jié)點可以有效地減少消息的低收益洪泛。仿真結(jié)果表明，與SnW相比較，所提出的路由策略平均延遲降低了20%左右。

圖2比較了所提出的路由協(xié)議與SnW路由協(xié)議的消息投遞率。由圖2可知，EP－ARM的投遞率要高于SnW。因為前者綜合考慮了節(jié)點的性能，使消息的洪泛更具目的性，而后者則因為洪泛的盲目性，使得網(wǎng)絡資源的利用率降低，這一點在副本數(shù)較少時更為明顯。

由圖3可知，EP－ARM與SnW相比投遞開銷幾乎沒有變化。這是因為EP－ARM并沒有增加消息副本的總數(shù)量，二者在網(wǎng)絡中洪泛的副本數(shù)相同，所以在投遞開銷上幾乎一致。

3 總結(jié)

針對SnW選擇中繼節(jié)點時的盲目性，本文利用相節(jié)點性能的差異，自適應地選擇合理的中繼節(jié)點，提高了網(wǎng)絡資源的利用率。仿真結(jié)果表明，在不明顯改變投遞開銷的情況下，本文提出的路由投遞延時更低，投遞率更高。

［1］ELIZABETH M，MADS H.The challenges of disconnected delay－tolerant MANETs ［J］.Ad Hoc Networks，2010，8(2):241－250.

［2］AMIN V，DAVID B.Epidemic Routing for Partially Connected Ad Hoc Networks［R］.Durham NC，USA:Duke University，2000.

［3］LINDGREN A，DORIA A，SCHELEN O.Probabilistic routing in intermittently connected networks［J］.ACM SIGMOBILE Mobile Computing and Communications Review，2003，7(3):19－20.

［4］SPYROPOULOS T，PSOUNIS K，RAGHAVENDRA C.Spray and wait:Efficient routing in intermittently connected mobile networks［C］//Kevin.Proceedings of the 2005 ACM SIGCOMM workshop on Delay－tolerant networking.New York:ACM，2005:252－259.

［5］ZHANG Z S.Routing in intermittently connected mobile ad hoc networks and delay tolerant networks Overview and challenges ［J］.IEEE Communications Surveys Tutorials，2006，8(1):24－37.

［6］WANG G，WANG B，GAO Y.Dynamic Spray and Wait Routing algorithm with Quality of Node in Delay Tolerant Network［C］//International Conference on Communications and Mobile Computing.China:CMC，2010:452－456.

［7］PRUEKSASRIV， INTANAGONWIWATC， ROJVIBOONCHAI K.DNH－SaW:The Different Neighbor－History Spray and Wait Routing Scheme for Delay Tolerant Networks［C］//International Symposium on Intelligent Signal Processing and Communications Systems.Thailand:ISPACS，2011:1－5.

［8］彭敏，洪佩琳，薛開平，等.基于投遞概率預測的DTN高效路由［J］. 計算機學報，2011，34(1):174－181.PENG M，HONG Peilin，XUE Kaiping，et al.Delivery probability prediction based efficient routing in DTN［J］.Chinese Journal of Computers，2011，34(1):174－181.

［9］KER?NEN A，OTT J，K?RKK?INEN T.The ONE simulator for DTN protocol evaluation［C］//ICST.The 2nd International Conference on Simulation Tools and Techniques.Italy:ACM，2009:1－10.