一種間歇性連接移動網絡自適應路由協議*

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

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

1 引言

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

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

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

2 路由協議概述

ARPBO路由協議運行過程如下：

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

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

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

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

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

具體流程如圖1所示。

Figure 1 Flow chart of ARPBO routing protocol圖1 ARPBO路由協議流程圖

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

Figure 2 Instance of ARPBO routing protocol圖2 ARPBO路由協議實例

3 路由協議詳細設計

3.1 傳遞效率計算

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

(1)

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

f(timeij)=λije-λijtimeij

(2)

假設節點Ni中消息m的目的節點為Nj，剩余生存時間為timeremain，則節點Ni對消息m的傳遞效率，即和目的節點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分別為消息生成時刻和節點Ni接收消息m的時刻。

ARPBO路由協議中，當節點傳輸時間有限時會優先發送傳遞效率大的消息，而當緩存溢出時會首先刪除傳遞效率小的消息。

3.2 路由表生成

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

3.2.1 Hello消息發送

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

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

3.2.2 拓撲生成

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

Table 1 TC message

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

節點收到TC消息后，根據TC消息來感知全網的拓撲，生成如表2所示的連通拓撲表項和表3所示的中斷拓撲表項。

Table 2 Connected topology table item

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

Table 3 Interrupted topology table item

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

3.2.3 路由表計算

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

Table 4 Routing table item

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

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

4 性能評估

4.1 實驗設置

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

4.2 性能比較

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

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

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

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

節點移動速度對時延的影響如圖4所示。可以看出，所有路由協議的消息傳遞時延都隨著節點移動速度的增大而增大。因為節點移動速度增大時，消息在連通網絡中被傳遞的概率減小，消息需要在網絡中斷情況下通過“存儲-攜帶-轉發”方式轉發，導致傳遞時延增大。OLSR協議傳遞時延最小，是因為其傳遞成功率較低，許多長時延的消息沒有被成功傳遞。ARPBO路由協議的傳遞時延小于DT-DYMO等協議的傳遞時延。

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

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

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

(2)節點數對性能的影響。

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

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

節點數對時延的影響如圖7所示。可以看出，消息傳遞時延隨著節點數的增大而減小。因為節點越多，消息在網絡連通和中斷情況下被快速轉發的機會增大，所以平均傳遞時延減小。由于ARPBO路由協議能夠在網絡連通和中斷情況下有效轉發消息，所以傳遞時延小于除OLSR以外的其他協議。

Figure 7 Impact of varying node numbers on delivery delay圖7 節點數對傳遞時延的影響

節點數對負載率的影響如圖8所示。可以看出，消息負載率隨著節點數增大而增大。因為節點增多、網絡密集，一些消息能夠通過更多的節點轉發，從而導致負載率增大。由于ARPBO路由協議能夠有效利用局部連通網絡中節點間的信息，在網絡連通和中斷情況下快速轉發消息，所以負載率略大。

Figure 8 Impact of varying node numbers on overhead ratio圖8 節點數對負載率的影響

5 結束語

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

[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] 張龍,周賢偉,王建萍,等.容遲與容斷網絡中的路由協議[J].軟件學報,2010,21(10):2554-2572.

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