一種基于生存時間的Ad hoc網絡不相交多路徑路由算法

摘 要:針對無線移動Ad hoc網絡的節點具有移動性和能量限制等問題，提出了一種根據網絡動態拓撲結構和節點能量來進行多路由選擇的混合式路由算法PEMP-OLSR。該算法以改進的鏈路狀態路由算法為基礎，通過在網絡拓撲構造過程中引入鏈路和節點生存時間等參數來提高所選路徑的穩定性，同時通過設定影響鏈路和節點權重的迭代因子來提高多條路徑的不相交性，以提高此并行多路徑算法的傳輸效率。通過大量仿真實驗結果表明，該算法能有效地提高所選擇的多條路徑的穩定性和不相交性。

關鍵詞:自組織網絡;多路徑路由協議;最優鏈路狀態路由;生存時間;不相交

中圖分類號:TP393 文獻標志碼:A

文章編號:1001-3695(2010)03-1157-04

doi:10.3969/j.issn.1001-3695.2010.03.098

Disjointed multi-path routing algorithm based onliving time in Ad hoc networks

HUANG Min， LIU Qiong， XI Jian-qing

(School of Software Engineering， South China University of Technology， Guangzhou 510006， China)

Abstract:To solve the problem of the mobility and limited power of nodes in wireless mobile Ad hoc networks，this paper designed a mixed multi-path routing algorithm of PEMP-OLSR in the paper. Based on the energy model of nodes，PEMP-OLSR algorithm took the living time of nodes and linked as the selecting factors of routing，which was helpful to advance the stability of paths. At the same time， it used the iterative genes to increase the weights of links and nodes after each routing process， by which to find more disjointed paths and enhance the parallel transmitting efficiency of data. A lot of simulation experiments show that the PEMP-OLSR algorithm can find more multi disjointed paths with higher stabilities.

Key words:Ad hoc network; multi-path routing algorithm; OLSR(optimized link state routing); living time; disjointed

0 引言

隨著無線Ad hoc網絡的快速發展，對其路由算法的研究也日益深入。由于Ad hoc網絡中的任何節點都具有終端和路由兩項功能，在源節點與目標節點之間建立多條路徑能更好地適應Ad hoc網絡拓撲結構的動態變化性，并實現均衡負載、縮短傳輸延遲、有效利用帶寬、增強容錯性和可靠性等，因此近年來對于多路徑路由算法的研究更為廣泛[1~4]。

目前所提出的各種多路徑路由協議中，從鏈路使用的并發性角度考慮可分為備份多路徑協議和并行多路徑協議。前者指源端到目的端之間所獲得的多條路徑中，在同一時刻僅有一條路徑進行流量傳輸，只有當該路徑中斷時，才能使用其他路徑，如AODV-BR協議[5];后者指源端到目的端的多條路徑中可同時使用兩條及以上的路徑來進行流量傳輸，如AOMDV協議[6]。雖然備份型多路徑協議因同一時刻只有一條路徑上具有通信流量而不存在信號干擾等問題，從而能獲得較高的傳輸質量，但它沒有發揮出多路徑并發傳送的諸多優點，因此并行多路徑協議在有效利用帶寬、提高傳輸效率方面具有更大優勢。由于無線網絡存在節點的移動、天線模式、發射功率、干擾源以及能量等諸多影響因素，使得無線網絡的拓撲結構處于動態變化之中，這就需要并行性多路徑協議充分考慮這些因素來進行路徑選擇，以提高所選擇路徑的穩定性。

近年來，有很多學者對移動自組織網絡中考慮網絡拓撲變化和節點能量等問題的路由協議展開了研究，如文獻[7]提出了一種使用路徑池的面向連接的路由算法PPRP (path-pool routing protocol)，該算法通過源節點和目的節點間的路由請求、路由應答及路由確認過程實現路由發現，并通過數據的確認流來進行路由維護和跟蹤動態變化的網絡拓撲。文獻[8]對文獻[7]進行了改進，增加了節點的能量感知過程，通過在路由選擇過程中考慮路徑剩余能量來提高路徑的實用性。以上兩種路由算法都是屬于反應式算法，主要通過源節點到目的節點所包含的兩兩節點之間的路由發現和路由維護過程來確認路徑，雖然沒有周期性的路由信息廣播，也不要求節點之間的鏈路是雙向的，但其路由維護過程中對于失效的鏈路不能在本地進行修復，失效鏈路信息必須返回到源點。本文提出了一種基于OLSR[9]的、同時引入鏈路和節點生存時間評估的混合式多路徑算法PEMP-OLSR。該算法在優化鏈路狀態協議基礎上引入鏈路狀態和節點能量評估因素來尋找路由，同時通過迭代因子來獲得多條不相交的、可并行化的穩定路徑。

1 PEMP-OLSR多路由算法的描述

PEMP-OLSR多路由算法是一種混合式路由算法，與先應式路由算法類似，它通過周期性地發送用于鏈路感知的HELLO消息以及用于拓撲控制的TC消息使網絡中的節點得到網絡拓撲信息;但它又有不同的地方，即該算法不要求每一個節點總是維護一個到網絡中其他所有節點的路由表并周期性地進行路由表更新，而是僅僅在有發送需求時才進行路由計算。

PEMP-OLSR多路由算法的路由發現包括鄰居發現、鏈路感知、鏈路狀態信息構造、信息擴散以及路由計算等步驟。此過程可簡單描述為:節點周期性地構造鏈路狀態分組LSP并通過洪泛方式擴散給網絡中其他節點。其中，LSP包含了本節點的基本信息、通過HELLO消息獲得的、包含節點生存時間的鄰居節點基本信息，以及由GPS預測的與所有鄰居節點相連的鏈路生存時間等信息。網絡中的其他節點接收到該LSP后將其保存到本地的網絡鏈路集NLS (network link set)中。當某個節點有傳輸需求時，通過本地NLS中所存儲的所有網絡節點的鏈路狀態信息來構造整個網絡的拓撲結構，并計算迭代因子，根據迭代因子的不同取值，運用基于穩定性迭代因子的、改進的多路徑Dijkstra算法[10]獲得到其他節點的多條路徑，并將得到的多路徑信息采用源路由方式保存在數據包的頭部，在數據傳遞過程中一般不需要中間節點進行逐跳路由計算。由此既繼承了鏈路狀態算法的較小網絡延時和穩定性等優點，又減少了鏈路狀態分組的洪泛數量，同時降低了中間節點的路由計算開銷。

2 PEMP-OLSR多路由算法的相關數據結構

2.1 HELLO消息和拓撲控制TC信息

在相鄰兩個節點間進行傳遞的HELLO消息包中包含了包的長度、序列號、有效時間、生成節點、發送周期等基本信息域，還包括是否作為某鄰居節點的MRP的標志、鏈路集、鄰居節點集和MPR集等用于后續路由發現任務的信息;在網絡中以洪泛方式發送的拓撲控制TC消息用于非相鄰節點之間進行信息交換，它不僅包含發送該消息的節點信息，還包含該節點所有鄰居節點的信息，并被該節點的MRP廣播到整個網絡。為滿足網絡對消息長度的限制，當節點鄰居數量較多時，TC消息可被分成多個包在一個更新間隔內發送完。

為跟蹤和體現無線移動網絡的拓撲變化以及節點和鏈路的可用度，本算法在這兩個消息中增加了關于鏈路生存時間和考慮能量的節點生存時間。

將Ad hoc網絡抽象為一個有向圖模型G=(V，E)。其中:V是移動節點的有限集合，E是無線鏈路邊的有限集合;(xi， yi)是移動節點i在全網中的坐標，Vi和θi分別為節點i在網絡中的移動速度和移動方向;Ri為節點i的有效傳播半徑。鏈路和節點的生存時間可通過如下計算獲得[7，11]:

a)節點i和節點j之間的鏈路生存時間TLij

TLij=-(ab+cd)+(a2+c2)r2-(ad-bc)2a2+c2a=vi cos θi-vjcos θj，b=xi-xjc=vi sin θi-vj sin θj，d=yi-yjr=Ri(1)

b)考慮能量的節點生存時間TNi

如果Ad hoc網絡中的節點具有不同的發射功率且不具備功率調整能力，則節點i向任意處于其傳播半徑Ri之內的鄰居節點j發射數據的功率都為ei。當節點i的剩余能量為Ei時，可求得其生存時間為TNi，其中fij為從節點i發送到節點j的數據流。

TNi=Ei/(eij∈Nifij)(2)

2.2 鄰居集、鏈路集和拓撲集

通過相鄰節點之間的HELLO消息傳送，一個節點的鄰居集中包含了該節點的所有一跳和兩跳鄰居節點的相關信息，如節點名稱、地址等，鄰居集在節點收到各鄰居對其HELLO消息的回應時更新;鏈路集中包含了一個節點的所有鏈路情況，如鏈路連接的節點地址、鏈路存活期、鏈路的通信模式(單向或雙向)等，它通過該節點與所有鄰居節點周期性交換HELLO消息來獲得。其中，單向鏈路是指該節點與某個鄰居節點之間的通信處于非對稱狀態，即可以收到來自鄰居節點的HELLO消息，但尚未確認鄰居節點可以收到本節點的HELLO消息;而雙向鏈路是指雙方處于可以互相傳送消息的對稱狀態;拓撲集保存了所有來自于除鄰居節點以外的其他節點的TC消息，拓撲表中的每個條目記錄了節點收到的每一條TC消息的序列號、接收時間、發送節點、到達發送節點的一跳鄰居節點等信息，由此可獲得整個網絡的拓撲信息。

2.2.1 基于選擇性中繼點SR的LSP洪泛優化

由于網絡中的相鄰節點通過HELLO消息的相互發送構建了鄰居集和鏈路集，可以考慮在每個節點的LSP洪泛過程中減少對所有鄰居節點的廣播，只選擇部分鄰居節點作為選擇性中繼點SR(selective relay)來轉發LSP，從而減少LSP包的洪泛數量。作為節點i的SR節點的條件是:節點i的一跳對稱(即鏈路是雙向的，彼此可以互發信息)鄰居節點;所有SR節點的前向一跳鄰居節點集合能覆蓋節點i的所有對稱兩跳鄰居節點。這樣，網絡中的任意一個節點既有自己的SR集合，同時也可能成為其他節點的SR，通過在節點內部維護一張SR集合表和一張SR被選者集合表來實現，前者記錄轉發自己的LSP的鄰居節點，后者記錄自己需要轉發其LSP的鄰居節點。如圖1所示，以中心灰色節點為例，它選擇第二層的黑色節點作為其SR，由它們負責將其LSP轉發給所有兩跳及以上節點，而第二層中的白色節點不參與中心節點的LSP轉發，由此可以有效減少LSP在同一區域內的重傳數量，從而減少網絡路由的開銷。

2.3 路由表

路由表是每個節點的核心數據，在有路由請求時通過下面的多路徑路由算法獲得到目標節點的多條不相交并發路徑，并以源路由方式將源節點到目標節點的路由信息以及路由有效期、時間標簽等信息保存到路由表和數據包頭部，中間節點在收到數據包時只需檢查其頭部的源路由信息便可進行轉發。

3 基于生存時間的多路徑路由算法

針對以上網絡節點移動情況和節點能源限制問題，在多路徑計算過程中，將鏈路生存時間和節點生存時間等因素進行綜合考慮，一方面要選擇維持時間較長的路徑和節點來減少路由的更新次數，以防止某條鏈路的失效或節點的能源耗盡影響整條路徑的生存時間，同時減少多條并發路徑的相交性以提高數據傳輸效率。下面介紹采用以鏈路和節點的生存時間為路徑選擇因素的單路徑路由選擇算法和增加迭代因子的多路徑路由算法。

3.1 基于鏈路和節點生存時間的單路徑算法

該算法以某個具有傳輸需求的節點s為源節點，目的節點設為d，通過該節點周期性獲得關于網絡拓撲和其他節點的相關信息，可以構造出一張包含全網節點的能量圖G′=(V，E)，該圖在上文中有向圖G的基礎上對每個節點和每條鏈路增加了生存時間參數TNi和TLij。其中:TNi表示任意節點i∈V的生存時間;TLij表示任意鏈路〈i， j〉∈E的生存時間。本文采用基于節點和鏈路能量的、改進的Dijkstra算法來尋找從s到d的具有最高穩定性的路徑。

算法基于傳統的最短路徑Dijkstra算法的思想，但在路徑發現時不是考慮路徑的長度，而是考慮路徑所經過的節點和鏈路的生存時間。具體過程如下:

a)初始化網絡拓撲圖和X、Y、Z三個集合。其中:X包括所有已經拓展的節點，初始時只包含源節點s，每執行一步加入一個新節點，直到所有節點都加入X中;Y包括尚未拓展的節點，每執行一步移走一個節點，最后直到該集合為空; Z包含s到d所選擇的最穩定鏈路，初始時為空，每執行一步增加新拓展的弧。

b)從初始節點v出發，按照以下條件進行路徑選擇:

(a)從v的所有輸出鏈路中選擇具有最大生存時間的弧;

(b)如果從v出發存在多條具有相同最大生存時間的弧，則比較各條弧所對應的鄰居節點的生存時間，選擇具有最大生存時間的鄰居節點的弧;

(c)如果存在多條有相同鏈路生存時間和對應節點生存時間的弧，則從中任意選擇一條。

按照以上方法進行拓展，每次將選擇的弧及其對應的另一端節點分別加入Z和X，直到圖中所有節點都包含到X中，則到目的節點d的最穩定路徑也包含在Y中了。

3.2 基于迭代因子的多路徑算法MP-Dijkstra’

MP-Dijkstra’算法是通過多次迭代使用Dijkstra’算法來尋找多條路徑，在迭代的過程中，通過迭代因子調整路徑所包含弧和節點的權重，從而得到多條穩定性逐次遞減的不同路徑。

MP-Dijkstra′算法的描述如下:

for ( i=1; i<=m; i++)

PathTreei=Dijkstra’ (Gi， s);

Pi=GetPath (PathTreei， s， d);

E=GetEdges(Pi);

V=GetVertex(Pi);

for 〈i， j〉∈E do

 TLij= (1-α) TLij ;

end for

for i∈V do

TNi= (1-β) TNvi;

 end for

end for

 return (P1，P2，P3，…，Pm)

以上算法的主要思路為:

若在第i次迭代過程中得到s到d的穩定路徑Pi，則在i+1次路徑計算過程中通過減少路徑Pi所包含弧的生存時間和所經過節點的生存時間來降低這些弧和節點在i+1次路徑尋找過程中的重用率，使得下次得到的路徑Pi+1不同于Pi，其中迭代因子α和β分別是弧和節點的代價調整因子，取值范圍均為 [0，1]。在本文中的α和β值分別設置為α=TLmax-TLminTLaver和β=TNvi-TNthrdTNthrd。此外，也可以根據多路徑選擇過程中對鏈路不相交路徑和節點不相交多路徑的不同傾向來調整α和β的計算方法。如果增大α，則算法趨向于尋找鏈路不相交路徑;而增大β，則算法趨向于尋找節點不相交路徑。4 路由修復

PEMP-OLSR多路由算法采用源路由方式進行數據傳遞，即通過路由算法獲得的多條路徑在初始傳遞時就保存在數據的頭部，從而減少中間節點對路由的重新計算工作，這樣不僅能提高數據傳輸的效率，也能發揮并行多路徑算法的優勢，但由于算法實現過程中TC消息的傳播需要一定的延時，加上Ad hoc 網絡的動態變化特性，用于多路徑計算的鏈路狀態信息不一定與當前實際的網絡狀況相一致，可能存在某個鏈路或節點失效的情況，使得原來獲得的某條路徑在實際傳輸過程中不可用，這樣就必須在算法中增加路由修復的功能。

該算法的路由修復通過在失效路徑或節點附近進行路由的重新計算來實現，具體過程為:在每個節點接收到一個數據包并從其頭部獲得傳輸路徑信息時，會檢查路徑中的下一跳節點及對應鏈路是否在該節點當前的鄰居集和鏈路集中，如果下一跳節點是其鄰居節點且鏈路有效，則按此鏈路轉發數據;否則，說明下一跳節點或對應鏈路已經不可用，則由該節點以自身為源節點，重新計算到目標節點的路徑，并通過新的路徑轉發數據包。由于存儲在該節點內的鄰居集和鏈路集等信息是通過HELLO消息在本地實時獲得，這些信息比起源節點通過TC消息獲得的整個網絡狀況信息要更能反映最新的本地鏈路情況。通過在算法中增加路由修復過程，能更有效地提高路徑的可靠性和數據包傳輸的成功率。

5 仿真結果

本文對PEMP-OLSR多路由算法進行了兩個方面的仿真實驗。

實驗1 采用Network Simulator version2(NS2)[12]模擬了一個范圍為1 000 m×1 000 m、具有100個主機的網絡，將PEMP-OLSR協議和傳統的OLSR協議從數據包發送成功率和路由負載兩個方面進行了比較。在模擬運行前:a)對協議的代理節點進行了設置，包括無線傳播模型、信道、鏈路層協議、網絡延遲、帶寬、網絡節點數等網絡基本參數;b)設置包括節點移動場景和網絡傳輸場景的網絡模擬，前者定義了節點位置、移動方向和移動速度，并將文中上述基于能量的節點生存時間模型代入到節點設置中，而后者定義數據包的大小、發送速率、持續時間等。仿真試驗的結果分別如圖2和3所示。

圖2顯示的是在有50個CBR數據源時，數據包傳輸率隨節點移動速度變化的趨勢圖。從圖2中可知，由于在路徑選擇中增加了對節點能量的考慮，所選擇的路徑和節點具有更高的傳輸能力和穩定性，從而使得PEMP-OLSR協議比傳統OLSR協議的數據包傳輸成功率高出10%~20%左右。從圖3所顯示的路由負載比較曲線圖可以看出，由于PEMP-OLSR協議應用了基于迭代因子的多路徑路由算法，降低了路徑在不穩定節點或鏈路上的相交度，從而減少了由于路由失敗而頻繁進行的路由發現和路由修復過程，因此，路由控制包的減少對于路由負載有很好的減輕作用，PEMP-OLSR協議比傳統OLSR協議路由負載要低。

實驗2 仿真實驗的內容是對PEMP-OLSR協議進行路徑重合的測試，在上述模擬網絡環境下，對所求的多路徑條數分別為4、8、10、12、15時的協議進行測試，路由選擇結果如表1所示。其中，每個路徑數量下進行了30次測試，以求得更為平均的算法效率。

表1 多路徑仿真結果

多路徑數量/條平均路徑長度/跳平均路徑生存時間/ms平均相交節點/個平均相交鏈路/條平均路徑修復/次

49100001

81280111

101470212

121550222

151730323

從表1可以看出，隨著所求并行路徑數量的增加，路經的平均長度、相交節點和鏈路條數也會有所增加，說明該算法不能完全避免求得的多條路徑在某些節點和鏈路上的重合，但重合節點和鏈路的數量隨著路徑條數而增加的速度并不快。另外，路徑修復次數較少，說明該算法在路徑選擇過程中考慮了節點和鏈路的生存時間，能減少對即將失效路徑和節點的選擇，從而減少重新計算路由的次數，有效地增強了所選路徑的穩定性。同時，根據木桶原理——一個由若干木板拼成的木桶容量是由最短一條木板決定的，因此從s到d的一條完整路徑的生存時間應為該路徑所有鏈路生存時間之中的最短時間。實驗結果顯示，源節點和目標節點之間的平均路徑生存時間會隨著所求路徑條數的增加而減少，這說明雖然求得的路徑條數越多，源節點到目標節點之間有效路徑的整體生存時間就越短，但如果這些路徑都能并行使用，則這種多路徑并行帶來的傳輸優勢就會體現得更明顯。

6 結束語

本文提出了一種基于鏈路和節點生存時間的混合式不相交Ad hoc多路徑路由算法，該算法以改進的鏈路狀態算法為基礎，為提高所選路徑的穩定性，在網絡拓撲構造和路徑選擇過程中引入鏈路和節點的生存時間作為參數，并采用源路由方式減少中間節點的路由計算開銷，同時通過迭代因子來提高多條路徑的不相交性。通過大量仿真實驗表明，該算法能有效提高所選擇路徑的穩定性和節點及鏈路的不相交程度，從而提高算法的并行傳輸能力。對算法所選擇的路徑質量和性能的進一步分析將是本文下一步的工作。

參考文獻:

[1]安輝耀，盧錫城.移動自主網絡多路徑路由技術研究進展[J]， 計算機工程與科學，2006， 28(2): 4-9.

[2]LEUNG R，LIU J，POON E，et al.MP-DSR:a QoS-aware multipath dynamic source routing protocol for wireless Ad hoc networks[C]//Proc of the 26th IEEE Annual Conference on Local Computer Networks.Minnesota:IEEE Computer Society，2001: 132-141.

[3]AN Hui-rao，LU Xi-cheng，PENG Wei.A cluster-based multipath routing for MANET[C]//Proc of IEEE International Conference on Networking and Communications.2005:369-376.

[4]MARINA M K，DAS S R.On-demand multipath distance vector routing in Ad hoc networks [C]//Proc of IEEE International Conference for Network Protocols.Washington DC:IEEE Computer Society，2001:14-23.

[5]LEE S J，GERLA M.AODV-BR:backup routing in Ad hoc network [C]//Proc of IEEE WCNC.2000:1311-1316.

[6]MARINA M K，DAS S R.On-demand multipath distance vector routing in Ad hoc networks[C]//Proc of the Int’l Conference onfor Network Protocols(ICNP).Washington DC:IEEE Computer Society，2001:14-23.

[7]陳晉倫，周正，呂國英.一種適用于非對稱鏈路的Ad hoc網絡路由協議[J].電路與系統學報，2004， 9(6):76-80.

[8]陳晉倫，蔣挺，周正. 一種具有能量感知的多路徑Ad hoc路由算法[J].電子與信息學報， 2006， 28(7):1298-1302.

[9]JACQUET P， MUHLETHALER P， CLAUSEN T， et al. Optimized link state routing protocol for Ad hoc networks[C]//Proc of the 5th IEEE Multi Topic Conference (INMIC).2001:439-456.

[10]DIJKSTRA E W.A note on two problems in connection with graphs [J]. Numerical Mathematic， 1959， 1:269-271.

[11] LEE S J， SU W.Ad hoc wireless multicast with mobility prediction[C]//Proc for IEEE ICCCN.1999:4-9.

[12] 柯志亨，鄧德雋.NS2仿真實驗[M].北京:電子工業出版社，2009.