一種移動自組網基于距離穩定的路由協議

白 媛，栗晨亮，宋 焱，張會兵

（1.天津理工大學 電氣電子工程學院，天津 300384；2.桂林電子科技大學 廣西可信軟件重點實驗室，廣西 桂林 541004；3.天津理工大學 光電器件與通信技術教育部工程研究中心，天津 300384）

移動自組網絡（mobile ad hoc networks，MANET）是一種小規模、無統一管理、網絡節點具備路由功能的動態無線移動網絡。節點的移動方向和速度具有隨機性，拓撲變化頻繁［1］。此類網絡適用于多跳路徑的特殊環境，常用于臨時組網應用場景，隨著D2D［2］及IoT［3］的提出與發展，MANET將發揮更重要的作用。

路由協議的選擇將直接決定無線網絡數據傳輸的效率和性能，根據不同的需求，大量路由方案不斷出現［4，5］。AODV［6］基于移動自組織網絡特點設計，能夠很好地適用于不斷變化的拓撲環境。AODV的選路依據是路由條目的新舊和跳數，未考慮所建路由的穩定性，重路由概率較高。選擇高穩定性路由是提高網絡性能的有效措施［7-10］，能夠有效地降低重路由頻率及其帶來的負面影響。針對該問題，大量提高所建鏈路穩定性的路由協議被陸續提出［8-15］。

文獻［11］對接收到的鄰節點功率進行采樣并設計鏈路穩定預測度量函數，在傳統協議基礎上增加鏈路穩定預測值選路依據，重新設計路由過程，網絡性能提高明顯。該方法為組播方法，不適用于單播。文獻［12］通過識別不安全節點來提高鏈路穩定性的組播方法，未考慮鄰節點間關系。

根據節點之間的距離，文獻［13］將鄰居關系分為遠離和靠近的相對狀態，利用不同狀態及節點間的距離估計鏈路生存時長。文獻［14］根據節點自身和鄰節點的歷史位置信息，計算節點間距離、相對運動速度及運動角度，考慮多種因素預測鄰節點之間的運動狀態，該方法認為在一次節點停留前，節點的運動狀態不變，與實際環境有差異。文獻［15］根據節點的距離、速度和運動方向對節點的狀態和運動過程進行預測，計算網絡斷裂或切換時間，提高了鏈路穩定性。文獻［16］在AODV基礎上進行改進，該方法考慮距離、開銷和節點能量的消耗，對路由生存時間進行估計。協議使用參量較多，方法復雜性較高。

考慮節點的移動速度，文獻［17］提出了2種速度感知概率模型，即簡單速度感知概率模型和高級速度感知概率模型。目標是改變AODV協議的路由請求方式，模型的設計減少了鏈路中斷的次數。文獻［18］提出了一種車聯網環境下的路由策略，節點不斷獲取鄰節點的速度信息并記錄，根據所鄰節點的平均速度與本地速度比較，若本地速度較小，則參與轉發。協議適用于有固定速度方向的車聯網環境，普通移動自組網速度方向的隨機性和速度值的瞬時性，不再適用。

根據上述方法中存在的問題，本文提出一種移動自組網基于距離穩定路由協議。協議考慮節點運動隨機性特點，適用于一般移動自組網單播路由協議。利用節點之間一段時間內相對運動關系來預測路徑穩定性強弱，相對運動關系由節點之間的距離變化計算得出。同時考慮鄰居保持時間、路由跳數及相對運動關系設計距離穩定度量值改善網絡性能。鄰居關系保持時間長，相鄰節點收集信息充分，路徑穩定性預測更加準確。

1 基于距離的鏈路穩定性度量

距離穩定路由協議（distance-stability routing protocol，DSRP）是在按需距離矢量路由協議（AODV）的基礎上進行改進。目的節點獲取多條不交叉路由，選擇路由跳數最少且距離穩定值較好的一條路由作為終選路由。路由距離穩定值由兩節點之間的單跳距離穩定值確定。兩相鄰節點之間增加單跳距離穩定值作為改進路由協議的選路標準，單跳距離穩定值由相對穩定值和絕對穩定值確定。相對距離穩定值考慮數據傳輸兩節點的相互移動性，表明兩節點一段時間內的相對運動性。絕對穩定值表示接收節點自身在鄰居拓撲中的相對運動性。

DSRP改進了參考文獻［11］的組播協議，使其適用于單播路由協議。引入基于地理位置路由方法，根據連續多次獲取的到達鄰節點距離值，設計距離穩定度量值函數，重新設計路由流程，選擇更加穩定高效的路徑。協議設計和實驗仿真在自由空間模型基礎上完成，節點間的距離根據設備的GPS定位信息計算得到。

1.1 最大接收距離閾值

網絡場景構建：節點總數為N，其中存在任意兩相鄰節點為Ni，Nj，i≠j，且i，j≤N。其中發送節點Ni，接收節點Nj，使用式（1）計算歐式距離，即

式中：（xNi，yNi）和分別為兩鄰居節點的位置；R為節點的傳輸距離。為節點Nj第n次接收到鄰節點的位置并由式（1）計算得出的距離，其中n＝［1，2，…，K］，表示記錄鄰節點距離信息的次數，K為允許記錄的最大數目，仿真實驗中取K＝5。當n＞K時，記錄表去除最早的一項，并記錄新的一項。

在實際應用中，移動網絡中各節點的網絡環境存在差異，各節點能夠正確接收到鄰節點數據分組的距離值有差異。根據數據正確接收時的距離信息，各節點維護本地最大接收距離閾值Nk是網絡中任意的節點。使用每次Nk與其任意鄰節點Nl之間鄰居鏈路斷裂前最后一次距離信息更新節點的最大接收閾值為：

任意節點Nk維護取值，若鄰節點Nl距離大于該值，認為該鄰節點Nl有鏈路斷裂風險，當前節點Nk不再參與該節點轉發的路由建立過程。

1.2 距離穩定度量

1.2.1 相對距離穩定值

式中，n表示穩定值的次序。

對Nj與Ni的距離穩定度量值集做方差，定義距離穩定值為：

D_stabNiNj用來衡量兩鄰節點之間的距離變化劇烈程度。越小則表明兩節點距離變化小，相對運動性弱。相鄰兩節點須連續保持一段時間的鄰居關系才能計算該值，鄰居關系斷裂將清除相應的距離記錄條目。

1.2.2 絕對距離穩定值

假定Nj有多個鄰居節點，其中第k個表示為Njk。Nj計 算 與 多 個Njk的 穩 定 度 量 值 集：｛SNj（Nj1），SNj（Nj2），SNj（Nj3），…，SNj（Njk）｝，其中各項計算方法為：

對穩定度量值集求方差，得出絕對距離穩定值為：

I_stabNj表明Nj在拓撲區域內與鄰節點之間的相對運動程度。

1.3 單跳距離穩定值

將2種穩定值以一定權重合成，得到某兩相鄰中間節點的單跳穩定值，該值由接收節點Nj計算得到，定義為：

考慮兩相鄰節點以及接收節點在鄰居拓撲中的運動關系，得出上述結果。DSNiNj作為單跳距離穩定值。DSNiNj越小，認為Ni和Nj間的鏈路越穩定。

2 距離穩定路由協議

AODV協議僅以跳數作為度量值，路由建立由第一條傳遞到目的節點的路由請求（RREQ）報文決定，該方式易選擇處于網絡邊緣的節點作為中間轉發節點，路徑斷裂可能性高。DSRP增加路由穩定度量，重新設計路由流程。

2.1 路由策略

當RREQ報文從源節點傳遞到目的節點，并回復路由回復（RREP）報文，源節點接收到RREP時，源節點激活路由，一條路由得以建立。在此路由歷經的節點序列中，若有2個相鄰節點之間的單跳距離穩定值較高，則表明該對節點之間的鏈路不穩定，會增加整條路由斷裂的概率。目的節點在接收到的多條跳數最少的路由中，選擇路徑上所有相鄰節點間最大單跳穩定值最小的路由為終選路由，以增加路由穩定度。

定義路由距離穩定值為：

式中：節點Nx和Ny是路徑path上任意一對鄰節點，Ny為Nx的下一跳；Ny計算得到DSNxNy。源目節點間形成多條路由時，將使用Spath最小的路由。

DSRP未改變AODV協議中間節點通過RREQ廣播ID和源節點ID確定同一個廣播報文的判定機制。同一RREQ能夠建立多條不交叉的路由。路由選擇如圖1所示。

路由過程如圖1所示，根據DSRP路由策略，S→A→B→E的路由距離穩定值為0.2，而S→C→D→E路由距離穩定值為0.3，第一條路由將被選擇并建立反向路由。協議同時考慮跳數和路由穩定性，跳數最少且路由穩定值較小的將被作為終選路由。

2.2 路由流程

DSRP數據包結構和路由表項與AODV協議相似，協議總流程見圖2，DSPR主要針對圖2中路由請求部分和路由建立部分做出改進。根據對鄰節點信息收集及穩定路徑選擇流程需求，對數據包格式及路由流程作以下修改。

2.2.1 報文格式及本地信息

1）在HELLO報文中增加本地當前位置信息Location字段。路由請求RREQ報文及RREP報文在原有跳數度量值基礎上，增加Path_stab字段用于更新及傳遞路由穩定值。

2）鄰居表增加接收到某鄰居HELLO報文的次序n和與之對應的記錄鄰居的距離值項。路由表項增加路由穩定值選項，用于記錄RREQ到達當前節點路由穩定值。

2.2.2 協議流程

根據圖2所示的總流程框圖，協議流程步驟如下。

步驟1初始化。

1）網絡初始化流程如圖3所示。網絡建立后，網絡中任意節點Ni每HELLO_INTERVAL時長，獲取自身定位并更新至其HELLO報文中Location字段，并廣播HELLO報文。

2）Ni的鄰節點Nj收到HELLO報文，根據報文中Location字段和自身位置信息，計算節點間距離并記錄到鄰居表，記錄次數n初始值為1，每次連續接收Ni的HELLO報文更新n+1。每個節點根據與鄰節點之的歷史距離信息記錄，利用式（2）維護本地最大接收閾值。

3）Nj判斷次數n是否等于5，如果等于5，記錄新到達的距離值，并將最早n＝1對應的距離值刪除，保證連續接收到鄰節點距離值最新且不超過5次。

步驟2路由請求。

1）路由請求流程如圖4所示。若有源節點Ns需要和某一目的節點Nd交換數據，Ns首先查找路由表，若有已建立的路由條目，則根據條目單播傳輸數據；否則轉入下一步。

2）源節點Ns構建RREQ報文，其中Path_stab＝0，廣播RREQ報文。

3）鄰居Ny接收到RREQ，解析RREQ并確定自身是否為目的節點，若是，則轉8）；否則轉入下一步。

4）Ny判斷是否接收過該報文，若是，則直接丟棄；否則轉入下一步。

5）Ny提取RREQ報文中攜帶的Nd信息并搜索本地路由表，若存在最新的到達Nd路由條目，記錄到達Ns的路由條目并單播回復RREP，轉入步驟3；否則轉入下一步。

6）節點不參與路由建立的條件是：Ny未記錄5次上跳節點Nx的距離或Nx處于自身最大接收距離閾值外，節點不參與路由建立，丟棄該RREQ報文；否則轉入下一步。

7）Ny根據式（7），利用鄰居表中記錄的鄰節點的距離信息，計算單跳距離穩定值DSNxNy，取DSNxNy和RREQ中Path_stab較大值，更新RREQ的Path_stab字段并轉發RREQ，轉入3），路由路徑上所有節點轉發RREQ時均做以上判斷。

8）若RREQ到達Nd，不再丟棄已接收過的相同RREQ報文，Nd等待一定時間，根據路由更新規則，收斂后會生成一條跳數最少路由穩定值較好的路由條目，路由回復轉步驟3。

當有RREQ到達時，路由表更新規則為：查找到達Ns路由條目，若不存在，則更新路由表，記錄RREQ中的Sequence、Hops和Path_stab等相關信息。若存在路由條目，則更新到達Ns路由的優先級順序為：Sequence、Hops、Path_stab。即保證路由最新和跳數最少條件下，判定路由穩定值大小。

步驟3路由建立。

1）路由建立流程如圖5所示，RREQ轉發過程中，路由上各節點已經建立到達Ns的路由，根據路由請求、路由更新規則更新路由表。

2）若RREQ到達Nd，Nd不再根據廣播ID和源節點ID丟棄RREQ報文，等待0.1 s，等待時間不斷更新路由表。等待結束后，根據路由表記錄，單播回復RREP，各中間節點根據本地路由表轉發。

3）若某中間節點存在最新到達Nd的路由條目，直接單播回復RREP。

4）RREP到達Ns，各中間節點反向路由條目成功建立，激活路由并開始轉發數據。

分析上述路由過程可知，DSRP每個節點增加最大接收距離閾值的判定，節點根據自身最大接收距離閾值和與上跳節點之間的距離信息，距離超出閾值的節點不再轉發接收到的RREQ報文，即不再參與該次路由建立過程，可以有效減少處于通信邊緣節點轉發RREQ的次數，減少RREQ報文的廣播，提高路由穩定性的同時減少參與選路的中間節點的個數。

在DSRP中僅與RREQ發送節點保持一定時長鄰居關系的節點參與選路，即兩鄰節點須保持5次連續HELLO間隔的鄰居關系時間才參與RREQ報文的轉發，否則直接丟棄RREQ報文，不再接收和轉發，避免部分移動相對頻繁的節點參與路由的建立。進一步降低協議對網絡的開銷并提高路由的穩定性。

根據式（8），DSPR路由選擇過程中增加路由穩定值參數Spath，該參數在RREQ報文傳遞過程中被選擇出來，代表多條不交叉路由中一條路由的路由穩定值，該值越小，認為該條路由的穩定性越好。某條路由建立成功后，路由上任意兩相鄰節點之間鏈路斷裂，將導致整條路由的斷裂，該值為整條路由中各中間相鄰節點單跳穩點值最大值，即認為路由上相鄰節點單跳穩定值最大的一段決定整條路徑的穩定性。該值可預測鄰節點之間的運動關系，選擇相對移動性較小的路由，減少路由斷裂次數。下文通過仿真實驗分析其網絡性能。

3 仿真分析

為驗證DSRP與AODV性能，使用NS-2（2.35版本）仿真平臺并使用Matlab分析數據。節點移動模型選擇Randem Way-point。由于仿真過程需要使用HELLO報文實現位置信息交換，使用AODV-WITH-HELLO模式，開啟NS-2中AODV協議的鏈路層探測功能。仿真場景參數見表1。

表1 仿真場景參數

3.1 網絡性能評價

無線協議性能度量存在多種標準［19］。對以下參數進行仿真比較。

1）分組投遞率：網絡中所有節點實際接收到的數據分組數量與節點發送的數據分組數量之比，分組投遞率的大小代表網絡可靠性高低。

2）吞吐量：所有已建立連接的所有目的節點交換數據分組總量與仿真時間的比值。

3）控制分組發送量：網絡存在期間，所有節點路由控制分組交換總數量，仿真實驗時長設置為600 s。

4）歸一化路由開銷［20］：網絡中所有節點發送和轉發路由請求總數量與總接收數據分組的數量比值。表示路由協議的開銷。

5）路由發起頻率：整個網絡發起路由過程的頻率，表示鏈路斷裂概率。

3.2 仿真實驗設置

主要對DSRP和AODV進行仿真實驗。仿真實驗場景參數見表1，有關參數見表2，仿真圖每點結果均為20次仿真實驗所得數據平均值。

表2 仿真實驗參數

3.3 仿真實驗結果分析

3.3.1 仿真實驗一

仿真實驗結果如圖6所示。

圖6（a）顯示了數據包投遞率與節點移動最大速度關系。由圖6（a）可知，隨著節點移動最大速度的提高，2種協議的分組投遞率都降低。AODV協議下降速度較快，DSRP大于AODV。DSRP能夠有效減少拓撲變化對網絡傳輸的影響。分析可得，當節點移動最大速度為20 m／s時，DSRP數據包投遞率相比AODV提高了2%～3%。

圖6（b）描述了節點移動最大速度與路由發起頻率的變化關系。路由發起頻率直觀地反映了路由路徑斷裂與網絡拓撲變化劇烈程度的關系。根據AODV和DSRP協議描述可知，只有在路由初建和路由斷裂時才會發起路由建立過程，路由請求的次數越少，路由發起頻率越低，路由斷裂次數越少，路由生存時間越長，所選路由越穩定。分析可知，隨著最大移動速度增加，AODV和DSRP的路由發起頻率都逐漸增高，其中AODV增長速度更快。DSRP建立的路由具有更好的防路由斷裂能力，節點最大移動速度為20m／s時，DSRP路由發起頻率比AODV降低了約20%。

圖6（c）顯示了吞吐量隨節點移動最大速度的變化關系。與圖6（a）對比，更高的數據包投遞率意味著更高的吞吐量。與AODV相比，最大移動速度為20 m／s時，DSRP在相同網絡環境下提高2%～3%。

圖6（d）描述了2種協議的歸一化路由開銷與節點移動最大速度的關系。歸一化路由開銷表明路由協議尋路過程對網絡資源的消耗大小。隨著網絡拓撲變化，DSRP和AODV的歸一化開銷隨之增加，AODV協議增長較快。節點移動最大速度為20 m／s時，DSRP比AODV下降約20%，性能提升明顯。DSRP由于加入了距離閾值和5次HELLO轉發的限制，減少了中間節點轉發RREQ次數，降低了RREQ泛洪對網絡資源的浪費。另外距離穩定值的加入，減少了因路徑斷裂而造成的路徑修復帶來的額外開銷。

圖6（e）是網絡控制包發送總量與節點最大移動速度之間的關系，控制分組主要包括路由協議相關控制分組及數據包頭部。歸一化路由開銷表明了路由請求次數與接收數據分組數量之間的關系。控制包總量則顯示路由協議整體的開銷數據，而不只是路由請求過程。隨著節點移動性的增強，2種協議的控制包總量增大，DSRP比AODV需要更少的控制包，降低了節點處理路由協議需要的控制包的數量，有利于降低擁塞和節點能量消耗。

仿真結果表明，DSRP-1比DSRP-2具有更好的性能，ω＝0.8比ω＝0.5時性能更好，絕對距離穩定值所起作用更具優勢。

3.3.2 仿真實驗二

實驗二仿真結果如圖7所示，改變網絡中節點數目，DSRP 5種性能指標均比AODV更好。節點個數增加時，路由可選擇節點增加，路由建立成功的概率提高，分組投遞率和吞吐量上升。但增加的節點數目將會增加路由過程控制包處理數量，歸一化路由開銷和控制包總量提高。更多的路徑節點將會增加路由斷裂的概率，路由發現頻率也有所提升。

根據上述結果分析，DSRP實現了對AODV性能的提升，DSPR具有高效性。降低路由開銷的同時，能夠提高數據分組投遞率，降低路由發起頻率。提升了所選路徑的穩定性。

4 結論

基于現有的選路方式，對傳統AODV進行改進。根據定位信息計算節點間距離信息并設計路由距離穩定值評估路徑的穩定性。仿真實驗結果顯示，相比AODV，新協議能夠更好地適應移動自組網絡拓撲的變化，實現性能的提升。本文在節點移動完全隨機的場景下進行仿真實驗，未考慮車輛網絡、傳感器網絡等特殊網絡場景，在不同網絡場景下，權重值ω對網絡的影響仍需驗證。