蔣慶豐，門朝光，田澤宇,馬英瑞

(1.哈爾濱工程大學計算機科學與技術學院,黑龍江 哈爾濱 150001；2.常熟理工學院計算機科學與工程學院，江蘇 常熟 225500;3.大慶師范學院計算機科學與信息技術學院,黑龍江 大慶 163712)

1 引言

移動自組網(wǎng)MANET(Mobile Ad hoc NETwork)是一種由移動節(jié)點構成的非中心化、多跳無線網(wǎng)絡。按需距離矢量路由AODV(Ad hoc On-demand Distance Vector Routing)[1]、目的節(jié)點序列距離矢量路由DSDV(Destination-Sequenced Distance-Vector Routing)[2]和最優(yōu)鏈路狀態(tài)路由OLSR(Optimized Link State Routing)[3]等MANET路由協(xié)議能夠在網(wǎng)絡連通時有效傳遞數(shù)據(jù)，但當無線網(wǎng)絡由于節(jié)點移動、環(huán)境惡劣或者遭受攻擊造成中斷、間歇性連接時，上述常規(guī)路由協(xié)議將無法成功發(fā)送數(shù)據(jù)。延遲容忍網(wǎng)絡DTN(Delay Tolerant Network)是一種具有長時延、鏈路經常中斷特點的網(wǎng)絡，在環(huán)境監(jiān)測、軍事戰(zhàn)略、深空探測等方面具有廣泛的應用前景和實用價值[4]。因為DTN中節(jié)點間不存在完全路徑，所以節(jié)點需通過“存儲-攜帶-轉發(fā)”方式來傳遞數(shù)據(jù)，即一個節(jié)點臨時存儲消息直到遇到一個和目的節(jié)點相遇概率更大的節(jié)點，然后將消息發(fā)送給此中繼節(jié)點，由中繼節(jié)點將消息發(fā)送給目的節(jié)點。

針對MANET和DTN的特點，相關文獻設計了一些MANET和DTN混合路由協(xié)議，以在網(wǎng)絡連通和中斷情況下有效傳遞數(shù)據(jù)。文獻[5]針對MANET和DTN混合網(wǎng)，實現(xiàn)了一種簡單的混合路由協(xié)議延遲容忍動態(tài)自組按需路由DT-DYMO(Delay-Tolerant DYnamic MANET On-demand routing)。該協(xié)議首先基于AODV的RREQ消息查找連通區(qū)域內的目的節(jié)點，若找到直接使用AODV發(fā)送消息；否則將消息發(fā)送給RREQ查找過程中發(fā)現(xiàn)的DTN節(jié)點，由該節(jié)點“存儲-攜帶-轉發(fā)”消息。文獻[6]針對車載自組網(wǎng)VANET (Vehicular Ad hoc NETworks),同樣設計了一種結合AODV協(xié)議和DTN的“存儲-攜帶-轉發(fā)”機制的按需路由協(xié)議DT-AODV,來提高數(shù)據(jù)傳遞率。文獻[7]提出了一種基于分組的混合容遲自組網(wǎng)路由協(xié)議HYMAD(HYbrid DTN-MANET routing)，該路由協(xié)議將移動節(jié)點分成多個組，在組內使用MANET中的距離矢量路由發(fā)送消息，在組間則采用DTN的Spray-and-Wait路由。針對間歇性連接的移動網(wǎng)絡環(huán)境，文獻[8]提出一種新的增強基礎設施DTN路由協(xié)議IEDR(Infrastructure Enhanced DTN Routing)。IEDR在網(wǎng)絡中斷時利用節(jié)點間相遇的機會交換數(shù)據(jù)，并將無線接入點AP (Access Point)作為輔助數(shù)據(jù)傳播的有效途徑，擴大網(wǎng)絡連通范圍。文獻[5-8]中每個節(jié)點只能獲得其所在連通網(wǎng)絡中部分節(jié)點的傳遞信息，當和目的節(jié)點之間的網(wǎng)絡中斷時，將無法選擇傳遞效率最大的下一跳中繼節(jié)點來傳遞消息，從而影響消息的傳遞效率。文獻[9]為在間歇性連接的移動網(wǎng)絡中有效傳遞數(shù)據(jù)，提出一種上下文感知的自適應單播路由協(xié)議CAR(Context-aware Adaptive Routing)。CAR協(xié)議在網(wǎng)絡連通時通過DSDV協(xié)議轉發(fā)消息，在網(wǎng)絡中斷時通過卡爾曼濾波技術和多屬性決策理論來選擇下一跳中繼節(jié)點。DSDV適應于規(guī)模較小、速度變化慢的網(wǎng)絡環(huán)境，當網(wǎng)絡規(guī)模增大和節(jié)點移動速度增大時，CAR的性能會下降。文獻[10]提出結合OLSR協(xié)議和DTN的DTS-OLSR協(xié)議，該協(xié)議利用部分具有OLSR和DTN功能的節(jié)點形成重疊網(wǎng)絡，重疊網(wǎng)絡中的節(jié)點在網(wǎng)絡中斷時會臨時存儲消息，以防止消息丟失。該協(xié)議中只有部分節(jié)點具有DTN功能，會影響路由效率，而本文中所有節(jié)點都進行DTN轉發(fā)。文獻[11]提出一種結合OLSR和DTN的有效混合路由協(xié)議OLSR-OPP(OLSR-OPPortunistic)，OLSR-OPP針對的是多副本路由，不同于本文研究的單副本路由。

本文針對間歇性連接移動網(wǎng)絡提出一種基于OLSR協(xié)議的自適應路由協(xié)議ARPBO(Adaptive Routing Protocol Based on OLSR)。OLSR是一種先驗式路由協(xié)議，每個節(jié)點可以獲得連通網(wǎng)絡的全網(wǎng)拓撲結構，并計算各自的路由表。該協(xié)議采用多點中繼MPR(MultiPoint Relay)的思想，減少了網(wǎng)絡中廣播分組的數(shù)量，適用于節(jié)點分布密集、網(wǎng)絡規(guī)模大的網(wǎng)絡。ARPBO協(xié)議為一種單副本路由協(xié)議，能夠在網(wǎng)絡連通時利用OLSR協(xié)議快速轉發(fā)消息，在網(wǎng)絡中斷時通過擴展OLSR協(xié)議，獲得消息發(fā)送節(jié)點的局部連通網(wǎng)絡中傳遞效率最大的下一跳中繼節(jié)點，能夠在高移動的密集網(wǎng)絡中有效傳遞數(shù)據(jù)。

2 路由協(xié)議概述

ARPBO路由協(xié)議運行過程如下：

(1) 節(jié)點間通過消息交換生成路由表。

(2) 節(jié)點發(fā)送一個消息時，如果路由表中有到達目的節(jié)點的直接路由，則發(fā)送消息。

(3) 如果沒有，表明網(wǎng)絡中斷，則根據(jù)路由表選擇連通網(wǎng)絡中傳遞效率(概率)最大的中繼節(jié)點。

(4) 如果選擇的中繼節(jié)點傳遞效率大于自身，則節(jié)點通過連通網(wǎng)絡將消息發(fā)送給中繼節(jié)點，由中繼節(jié)點“存儲-攜帶-轉發(fā)”消息。當中繼節(jié)點和目的節(jié)點連通時，將消息發(fā)送給目的節(jié)點。

(5) 如果中繼節(jié)點傳遞效率小于自身，則將消息臨時存儲在自身緩存中，直到遇到傳遞效率大的節(jié)點或者目的節(jié)點。

具體流程如圖1所示。

Figure 1 Flow chart of ARPBO routing protocol圖1 ARPBO路由協(xié)議流程圖

假設節(jié)點A向H發(fā)送消息，如圖2所示，圖中UIJ表示節(jié)點I和J間的傳遞效率，由于沒有到達目的節(jié)點H的直接路由，則節(jié)點A將消息發(fā)送給連通網(wǎng)絡中傳遞效率最大的中繼節(jié)點E，當節(jié)點E和F相遇時，則直接將消息發(fā)送給處于同一連通網(wǎng)絡的目的節(jié)點H。如果F的傳遞效率小于自身，節(jié)點A自身將先存儲消息。

Figure 2 Instance of ARPBO routing protocol圖2 ARPBO路由協(xié)議實例

3 路由協(xié)議詳細設計

3.1 傳遞效率計算

同文獻[12]一樣，假設網(wǎng)絡中斷時兩個節(jié)點間相遇時間服從均值為1/λ的指數(shù)分布，λ代表兩節(jié)點的接觸率。兩節(jié)點Ni和Nj的接觸率λij的值可通過式(1)進行計算。

(1)

由于節(jié)點間相遇時間服從均值為1/λ的指數(shù)分布，所以節(jié)點Ni和Nj在timeij時間間隔內相遇的概率密度函數(shù)如式(2)所示：

f(timeij)=λije-λijtimeij

(2)

假設節(jié)點Ni中消息m的目的節(jié)點為Nj，剩余生存時間為timeremain，則節(jié)點Ni對消息m的傳遞效率，即和目的節(jié)點Nj相遇的概率Pij如式(3)所示：

Pij=P(timeij≤timeremain)=

1-e-λij×timeremain

(3)

消息剩余時間timeremain的值如式(4)所示：

timeremain=TTL+tgen-trec

(4)

其中，TTL(Time to Live)為消息的生存期；tgen和trec分別為消息生成時刻和節(jié)點Ni接收消息m的時刻。

ARPBO路由協(xié)議中，當節(jié)點傳輸時間有限時會優(yōu)先發(fā)送傳遞效率大的消息，而當緩存溢出時會首先刪除傳遞效率小的消息。

3.2 路由表生成

ARPBO路由表的生成實現(xiàn)包括Hello消息發(fā)送、拓撲生成、路由表計算三個過程。節(jié)點首先發(fā)送Hello消息，進行鄰居感知、MPR節(jié)點的選擇以及中斷時節(jié)點間平均相遇時間的統(tǒng)計；然后通過消息廣播獲得網(wǎng)絡中節(jié)點的連接信息和相遇信息，從而生成全網(wǎng)絡的拓撲模型；最后根據(jù)網(wǎng)絡拓撲信息生成路由表，在網(wǎng)絡連通和中斷情況下有效選擇下一跳節(jié)點傳遞消息。

3.2.1 Hello消息發(fā)送

OLSR協(xié)議對標準鏈路狀態(tài)路由協(xié)議進行了優(yōu)化，其核心是多點中繼技術。多點中繼的思想是通過減少同一個區(qū)域中相同控制消息的轉發(fā)次數(shù)來達到減少網(wǎng)絡中廣播分組數(shù)量的目的。網(wǎng)絡中每個節(jié)點選擇其鄰居節(jié)點集合的一個子集(MPR集)來轉發(fā)該節(jié)點的控制消息，這個子集中的節(jié)點就是該節(jié)點的MPR節(jié)點，而該節(jié)點就是MPR節(jié)點的多點中繼選擇節(jié)點(MPR Selector)。只有被選為MPR的節(jié)點才產生并周期性洪泛拓撲控制信息，這樣可以顯著地減少網(wǎng)絡中廣播的控制分組數(shù)量。

移動節(jié)點周期性地發(fā)送Hello消息，可以進行鄰居感知和MPR節(jié)點的選擇。每個節(jié)點從其一跳鄰居中選擇自己的MPR集，通過該集合轉發(fā)的分組能夠覆蓋該節(jié)點所有的二跳鄰居節(jié)點。節(jié)點選擇MPR節(jié)點后可以在連通網(wǎng)絡中有效傳遞信息。

3.2.2 拓撲生成

節(jié)點計算和非連通節(jié)點間最近相遇(即兩節(jié)點連通)時間的平均值，從而根據(jù)式(1)計算兩節(jié)點的接觸率，然后生成如表1所示的TC消息并廣播給網(wǎng)絡中其他節(jié)點。

Table 1 TC message

序列號用來判斷消息的新舊；MPR Selector為多點中繼選擇節(jié)點地址；最近相遇節(jié)點地址存放當前非連接、最近相遇過的節(jié)點地址；接觸率存放的是當前節(jié)點和最近相遇節(jié)點的接觸率信息。

節(jié)點收到TC消息后，根據(jù)TC消息來感知全網(wǎng)的拓撲，生成如表2所示的連通拓撲表項和表3所示的中斷拓撲表項。

Table 2 Connected topology table item

表2中，序列號用于記錄本節(jié)點收到的最后一個TC消息的序號，當收到一個新的TC消息時，將新的TC消息的序列號與表項序列號相比較來決定接收還是丟棄該消息；目的節(jié)點地址為TC消息中的MPR Selector節(jié)點地址；連通的上一跳地址為發(fā)送TC消息的源節(jié)點地址。

Table 3 Interrupted topology table item

表3中，序列號用于記錄本節(jié)點收到的最后一個TC消息的序號；目的節(jié)點地址為消息源節(jié)點最近相遇的節(jié)點的地址；中斷的上一跳地址為TC消息源節(jié)點地址；上一跳接觸率為TC消息源節(jié)點和目的節(jié)點的接觸率。

3.2.3 路由表計算

節(jié)點發(fā)送消息時，需要根據(jù)拓撲結構圖生成如表4所示的路由表項，從而在網(wǎng)絡連通和中斷時有效選擇下一跳節(jié)點。ARPBO路由協(xié)議在網(wǎng)絡連通時，基于連通拓撲表，根據(jù)Dijkstra算法計算出跳數(shù)最少的路徑及下一跳地址；在網(wǎng)絡中斷時，根據(jù)中斷拓撲表選擇接觸率最大的中繼節(jié)點，并將接觸率填入路由表中。

Table 4 Routing table item

路由表項中存儲了網(wǎng)絡連通和中斷時的下一跳節(jié)點地址及接觸率信息。其中，第1項為目的節(jié)點地址；第2項為網(wǎng)絡連通時根據(jù)連通拓撲結構圖計算出的下一跳地址；第3項為網(wǎng)絡連通時消息源節(jié)點和目的節(jié)點之間的跳數(shù)；第4項為網(wǎng)絡中斷時選擇的接觸率值最大的下一跳節(jié)點地址；第5項為節(jié)點間接觸率值。

節(jié)點在發(fā)送消息時，會根據(jù)路由表和式(3)計算緩存中每個消息的下一跳節(jié)點的傳遞效率，并對消息進行排序，然后優(yōu)先發(fā)送和存儲傳遞效率大的消息。

4 性能評估

4.1 實驗設置

為驗證ARPBO路由協(xié)議的性能，通過NS3模擬器對其性能進行仿真。同文獻[9]一樣，默認情況下，仿真區(qū)域為1000 m×1000 m，包括50個移動節(jié)點。移動模型為根據(jù)社會網(wǎng)絡理論設計的基于社區(qū)的節(jié)點移動模型CM(Community Model)[13]，該模型可以很好地代表人類的移動。CM模型中節(jié)點被分為5個社區(qū)即組，其中每個節(jié)點表示人類攜帶的具有無線通信功能的移動設備，每組節(jié)點代表關系較密切的社會團體。仿真時間為2 400 s，共發(fā)送1 000個消息，消息大小為1 KB，緩存大小為100 KB，節(jié)點無線傳輸范圍為200 m，移動速度為1～6 m/s，TTL為2 000 s。

4.2 性能比較

為驗證路由的性能，將ARPBO路由協(xié)議與OLSR[3]、DT-DYMO[5]、HYMAD[7]、CAR[9]進行性能對比。使用傳遞成功率、平均傳遞時延、負載率3個性能評價指標來對路由性能進行評價。傳遞成功率為成功傳遞的消息數(shù)與發(fā)送消息數(shù)比例。平均傳遞時延是指所有傳遞成功消息的傳遞時延的平均值。負載率為消息轉發(fā)數(shù)和成功傳遞消息數(shù)的比值，表示成功傳遞一個消息需要多少次轉發(fā)，負載率越大意味著網(wǎng)絡能耗越高，資源消耗越大。下面通過改變節(jié)點移動速度、節(jié)點數(shù)目的大小來驗證路由性能。

(1)節(jié)點移動速度對性能的影響。

節(jié)點移動速度對傳遞成功率的影響如圖3所示?？梢钥闯?，所有路由協(xié)議的消息傳遞成功率都隨著節(jié)點移動速度的增大而變小。隨著節(jié)點移動速度的增大，節(jié)點在同一連通網(wǎng)絡的概率變小，所以導致傳遞成功率減小。由于ARPBO路由協(xié)議能夠利用連通網(wǎng)絡拓撲信息，在網(wǎng)絡連通和中斷時自適應地高效轉發(fā)消息，所以傳遞成功率高于其他協(xié)議。由于CAR協(xié)議在節(jié)點移動速度增大時，路由信息失效較快，所以傳遞成功率在速度較大時低于其他路由協(xié)議。由于OLSR協(xié)議在網(wǎng)絡中斷時無法有效選擇下一跳節(jié)點，所以傳遞成功率最低。

Figure 3 Impact of varying speeds on delivery success ratio圖3 速度對傳遞成功率的影響

節(jié)點移動速度對時延的影響如圖4所示?？梢钥闯觯新酚蓞f(xié)議的消息傳遞時延都隨著節(jié)點移動速度的增大而增大。因為節(jié)點移動速度增大時，消息在連通網(wǎng)絡中被傳遞的概率減小，消息需要在網(wǎng)絡中斷情況下通過“存儲-攜帶-轉發(fā)”方式轉發(fā)，導致傳遞時延增大。OLSR協(xié)議傳遞時延最小，是因為其傳遞成功率較低，許多長時延的消息沒有被成功傳遞。ARPBO路由協(xié)議的傳遞時延小于DT-DYMO等協(xié)議的傳遞時延。

Figure 4 Impact of varying speeds on delivery delay圖4 速度對傳遞時延的影響

節(jié)點移動速度對負載率的影響如圖5所示。可以看出，消息負載率隨著節(jié)點移動速度的增大而減小。因為節(jié)點移動速度增大，連通網(wǎng)絡中包含的節(jié)點減少，成功傳遞消息的轉發(fā)次數(shù)變少，并且消息在網(wǎng)絡中斷情況下轉發(fā)次數(shù)也變少，所以負載率變小。由于ARPBO路由協(xié)議有效傳遞消息，所以負載率略高，但獲得了較高的傳遞成功率和較低的傳遞時延。

Figure 5 Impact of varying speeds on overhead ratio圖5 速度對負載率的影響

(2)節(jié)點數(shù)對性能的影響。

節(jié)點數(shù)對消息傳遞成功率的影響如圖6所示?？梢钥闯?，所有路由協(xié)議的消息傳遞成功率都隨著節(jié)點數(shù)的增大而增長。這是因為節(jié)點數(shù)越大，網(wǎng)絡越密集，節(jié)點在同一連通網(wǎng)絡的概率增大，并且網(wǎng)絡中斷時節(jié)點相遇的概率也增大，所以傳遞成功率增大。由于DT-DYMO通過AODV路由協(xié)議不能獲取連通網(wǎng)絡全局拓撲信息，從而不能有效選擇傳遞效率大的中繼節(jié)點傳遞消息，導致傳遞成功率低。HYMAD中組內節(jié)點只能夠獲得組內拓撲信息，而無法獲得連通時組外節(jié)點的傳遞效率信息，所以傳遞成功率不高。由于ARPBO路由協(xié)議能夠有效利用OLSR協(xié)議感知全局網(wǎng)絡拓撲來獲得節(jié)點的傳遞效率，在網(wǎng)絡中斷時有效選擇下一跳中繼節(jié)點，并且在網(wǎng)絡密集時能夠利用MPR機制進行廣播消息的優(yōu)化，所以獲得了比CAR高的傳遞成功率，成功率最高。OLSR協(xié)議在網(wǎng)絡中斷時無法有效傳遞消息，所以傳遞成功率最低。

Figure 6 Impact of varying node numbers on delivery success ratio圖6 節(jié)點數(shù)對傳遞成功率的影響

節(jié)點數(shù)對時延的影響如圖7所示?？梢钥闯?，消息傳遞時延隨著節(jié)點數(shù)的增大而減小。因為節(jié)點越多，消息在網(wǎng)絡連通和中斷情況下被快速轉發(fā)的機會增大，所以平均傳遞時延減小。由于ARPBO路由協(xié)議能夠在網(wǎng)絡連通和中斷情況下有效轉發(fā)消息，所以傳遞時延小于除OLSR以外的其他協(xié)議。

Figure 7 Impact of varying node numbers on delivery delay圖7 節(jié)點數(shù)對傳遞時延的影響

節(jié)點數(shù)對負載率的影響如圖8所示?？梢钥闯觯⒇撦d率隨著節(jié)點數(shù)增大而增大。因為節(jié)點增多、網(wǎng)絡密集，一些消息能夠通過更多的節(jié)點轉發(fā)，從而導致負載率增大。由于ARPBO路由協(xié)議能夠有效利用局部連通網(wǎng)絡中節(jié)點間的信息，在網(wǎng)絡連通和中斷情況下快速轉發(fā)消息，所以負載率略大。

Figure 8 Impact of varying node numbers on overhead ratio圖8 節(jié)點數(shù)對負載率的影響

5 結束語

為在間歇性連接移動網(wǎng)絡中有效傳遞消息，本文提出一種基于OLSR協(xié)議的自適應路由協(xié)議ARPBO，并對其性能進行仿真。實驗結果表明，ARPBO協(xié)議在網(wǎng)絡連通時能夠利用OLSR協(xié)議快速轉發(fā)消息；在網(wǎng)絡中斷時能夠有效選擇傳遞效率大的下一跳中繼節(jié)點傳遞數(shù)據(jù)。下一步工作將針對間歇性連接移動網(wǎng)絡研究設計更加有效的中繼選擇策略及多對多的數(shù)據(jù)分發(fā)協(xié)議。

[1] Perkins C E,Belding-Royer E M,Das S R. Ad hoc on-demand distance vector (AODV) routing:RFC 3561[S].NY:The Internet Society:2003.

[2] Perkins C,Bhagwat P.Highly dynamic destination-sequences distance-vector routing (DSDV) for mobile computers[C]∥Proc of ACM SIGCOMM,1994:232-244.

[3] Clausen T,Jacquet P. Optimized link state routing protocol (OLSR):RFC 2326[S].NY:The Internet Society:2003.

[4] Zhang Long, Zhou Xian-wei,Wang Jian-ping,et al.Routing protocols for delay and disruption tolerant networks[J].Journal of Software,2010,21(10):2554-2572.(in Chinese)

[5] Kretschmer C, Ruhrup S,Schindelhauer C.DT-DYMO:Delay-tolerant dynamic MANET on-demand routing[C]∥Proc of the 29th IEEE International Conference on Distributed Computing Systems Workshops,2009:493-498.

[6] Zhu D J,Cui G F,Zhong C.DT-AODV:An on-demand routing protocol based DTN in VANET[J].Applied Mathematics & Information Sciences,2014,8(6):2955-2963.

[7] John W, Vania C.HYMAD:Hybrid DTN-MANET routing for dense and highly dynamic wireless networks[J].Computer Communications,2010,33(13):1483-1492.

[8] Yu Zhen, Xu Jing-dong,Zhang Jian-zhong,et al.IEDR:An infrastructure enhanced DTN routing protocol[J].Journal on Communications,2013,34(8):44-52.(in Chinese)

[9] Musolesi M,Mascolo C.CAR:Context-aware adaptive routing for delay-tolerant mobile networks[J].IEEE Transactions on Mobile Computing,2009,8(2):246-260.

[10] Pant R,Tunpan A,Mekbungwan P,et al.DTN overlay on OLSR network[C]∥Proc of AINTEC’10,2010:56-63.

[11] Azzuhri S R,Ahmad H,Portmann M,et al.An efficient hybrid MANET-DTN routing scheme for OLSR[J].Wireless Pers Commun,2016,89(4):1335-1354.

[12] Gao W,Li Q H,Zhao B,et al.Multicasting in delay tolerant networks:A social network perspective[C]∥Proc of ACM MobiHoc,2009:299-308.

[13] Musoles M，Mascolo C.Designing mobility models based on social network theory[J].ACM SIGMOBILE Mobile Computing and Comm,2007,1(2):1-12.

附中文參考文獻：

[4] 張龍,周賢偉,王建萍,等.容遲與容斷網(wǎng)絡中的路由協(xié)議[J].軟件學報,2010,21(10):2554-2572.

[8] 于振，徐敬東，張建忠，等.基礎設施增強的DTN路由協(xié)議[J].通信學報,2013,34(8):44-52.