移動Ad hoc網基于鏈路質量和局部拓撲的機會路由協議

汪紅霞

(安徽新華學院 信息工程學院, 合肥 230088)

移動自組織網絡(MANETs)是通過無線鏈路連接組成的一組可移動節點。在不借助靜態基礎設施的情況下，無線自組網中的每個節點都充當路由器，將數據包轉發給其它節點。在傳統的無線自組網路由協議(主動式或被動式)中，每個源節點或中繼節點維護一張路由表來保存到達其它節點的路徑。在反應式路由協議中，當一個節點想要與另一個節點通信時，如果連接兩個節點的路徑在路由表中沒有找到，路由發現過程就會啟動并在網絡中廣播一個路由請求包。當鏈路斷開時，將啟動一個新的路由發現。因此，反應式路由協議在路由發現中可能引起很大的負載。另一方面，在主動式路由協議中，節點通過周期性的交換路由信息包維護網絡拓撲信息。傳統的確定性路由協議適合靜態或低動態環境。然而，在高速移動場景下，由于節點的移動拓撲頻繁的改變，造成了每一個移動的節點很難維護確定性的路由。頻繁交換拓撲更新信息也會導致資源的浪費。

機會路由利用廣播的特性，使用某種路由度量來確定轉發優先級。數據包以單跳廣播的方式被轉發，所以在轉發數據包之前不需要維護確定的路由。與傳統的路由相比，機會路由可以很好地適應節點頻繁移動和拓撲信息難以維護的場景，克服了不可靠的無線傳輸的弊端。

然而，利用拓撲信息和移動性特征為移動場景設計路由協議仍存在挑戰[1]。基于拓撲的機會路由協議,例如ExOR[2]在維護全局拓撲信息時存在很大的困難，它需要和相鄰節點頻繁的交換信息[3]。基于地理信息的機會路由在解決路由空洞問題上需要花費額外的負載[4]，這意味著這個節點除了本身外不能找到離目的節點更近的節點。況且，由于節點的移動性，地理轉發機制不可能總是較適合的。一方面，機會路由將廣播作為轉發方法。這樣，當一個節點向鄰居節點轉發數據包時，它可能會遭受來自其它發送節點的干擾，這將影響無線傳輸。另一方面，在移動自組網中，所有節點不可以預測地移動導致兩個通信節點距離的變化。隨著彼此之間移進或移出通信半徑，節點之間的鏈路質量發生變化，這也影響了無線傳輸。

本文為移動自組織網提出一種基于鏈路質量和局部拓撲機會路由協議，該協議綜合考慮移動場景下的拓撲位置信息和利用干擾與移動性去優化機會路由的兩個關鍵過程：候選集的選擇和節點的優先級的評定，從而本文的主要貢獻如下：

(1)為發送節點確定候選節點集合。本文提出的協議綜合考慮了MAC層引入的干擾以及節點移動性導致的鏈路剩余生存期的變化，通過更準確的評定節點間的鏈路質量確定更合適的候選節點集合。

(2)為候選節點評定優先級。本文提出的協議綜合考慮了兩跳范圍內的位置信息、局部拓撲信息以及節點移動的自適應性，選出合適的轉發節點，降低路由空洞的出現次數。

1 相關工作

機會路由可以歸結為三大類：基于拓撲的、地理位置的和混合的機會路由。Biswas[2]等提出一種基于拓撲的機會路由稱ExOR。ExOR首先在候選集中通過節點序列轉發每個數據包，然后確定根據期望傳輸次數(ETX)選擇哪個節點作為轉發節點，ETX即所有節點成功接收數據包數。然而，在移動自組織網中，每個節點可能隨機頻繁地移動。估計一條不穩定路徑上的ETX是很困難的，而且鏈路相關也影響ETX的準確性[5]。Wang等人[6]提出一種局部協作中繼方法以擴展ExOR，這樣可以進一步探索廣播特性和橋梁失效鏈接。它利用多個不在候選集中的節點進行機會數據轉發來維持一個健壯的拓撲。Yang等人[7]提出一種基于節點地理位置的機會路由。前一跳根據本地位置信息確定預定義的順序。預定義的順序插入節點IP報頭中以通知候選集中的節點。Seada等人[8]研究了基于鏈路損耗模型的多中轉發策略性能，分析了距離和跳數之間的權衡關系。他們發現數據包接受率(PRR)和距離目的地距離相乘(PRR*D),是一個非常適合無線傳感器網絡的地理轉發度量。然而，PRR*D度量可以被推薦用于靜態或低動態環境中，如環境監測。在高動態環境下，整個時間鏈路質量可能變化很大，PRR的穩定估計可能無法獲得。Zhao等人[9]提出混合式協議CAOR，其中候選集每個節點利用采用多跨層信息，如地理進程、能量、鏈路質量和移動來決定自己的優先級。具有最高優先級的節點具有轉發數據包的權限，CAOR也能調整在運行時上下文信息的權重。

2 基于鏈路質量和局部拓撲的機會路由

當源節點需要發送數據包到目的節點時，OR-LqT首先會選擇候選集中具有優先權的節點作為下一跳，然后再到候選集中所有節點。每一個收到數據包的節點發送一個ACK應答源節點。然后根據ACK源節點為候選集所有節點分配優先級。具有最高優先級的節點將數據包轉發給鄰居并繼續該過程，直到數據包到達目的節點為止。

地理信息可以引導機會路由協議向正確的方向轉發，并加速協議的收斂性。然而，它也可能會導致路由空洞。這種邊界轉發方案產生了數據包轉發死角區。雖然一些機制被提出用來解決這個問題，但需要花費額外的時延和跳數。拓撲信息可以在一定程度上反映網絡的全局連接，可以引導轉發數據包朝正確的方向轉發，然而，由于無線自組網的維護成本高，拓撲信息很難獲得。一個好的機會路由在無線自組網應具有快速收斂和低成本轉發數據包。更重要的是，它應該適應節點移動帶來的頻繁變化的拓撲。

本文將分別討論機會路由中候選集和優先級這兩個處理過程，以及它們的決定因素。

2.1 候選集的影響因素

候選集的選擇是控制機會路由負載的一個重要程序。只有侯選集里的節點才有權轉發數據包。如果集合太大，有限的能量就會被浪費很多。因為有些節點可能收到冗余包，這會給其他的發送節點造成大量的干擾。如果集合太小，它可能轉發失敗。本案確定候選集的決定性因素是傳輸時的鏈路質量，這是由機會路由的特征決定的。機會路由利用廣播特性，每次轉發都是一個新的程序，與上一次轉發毫無聯系。如果鏈路質量好就足以完成轉發。節點可能被選做發送節點集。當發送節點需要轉下一次數據包時，需要開啟一個新的廣播。

與無線網絡不同，在移動Ad hoc網絡中，節點隨意地獨立移動，這個節點的移動可能引起鏈路質量的變化。因此，解決變化的鏈路質量問題需精確的鏈路質量測量。精確的鏈路質量測量可以降低發現成本、減少未知鏈路質量引起的數據重發；同時，還需要具備高效、靈活、低成本等特性。

2.2 哪些候選節點應獲得更高的優先級

為所有候選做優化是機會路由中的一個重要過程，它決定了不同候選的轉發概率。一個好的優化方案，可以提高轉發效率和避免重復轉發。在無線自組織網絡中，優先級由兩個因素決定，一個是地理位置，另一個是移動適應性。位置意味著下一個節點應該有一個更接近目標的的節點。移動適應性有兩層含義：一是下一個節點應該有一個正確移動趨勢。當節點朝目標節點相反方向移動時，它不是很好的下一跳選擇，即使它有一個更近目標的位置，它也可能將數據包傳送到一個不必要的區域，所以，這個數據包可能被轉發遠離目的地。移動趨勢的另一層含義是，下一個節點還應該有它的下一跳選擇。當發送節點轉發數據包到下一個節點時，需要考慮下一個節點的下一跳選擇。這是一個重要的概念,因為，雖然對于下一個節點來說是一跳的信息，但對于發送節點來說是一個兩跳的信息，更多了解候選集的拓撲結構能夠有效降低路由空洞產生的概率。

2.3 詳細設計

一個精確的鏈路質量測量可以幫助節點在一個更穩定的環境中通信，可以減少沖突概率和重傳次數。自組織網中，兩個節點之間通信受節點移動性和沖突的影響。節點的移動性引起兩個節點之間距離的變化，從而導致變化的鏈路質量。當一個節點發送一個數據包給另一個節點時，數據包可能會遇到從其它同步數據包傳輸的沖突。本文同時考慮節點的移動性和沖突。

關于沖突的影響。當一個節點s想要發送數據包，節點s成功傳輸數據包給節點r的概率為：

Psucc=1-(PaPc)N,

(1)

其中，Pa為結點s，是在一個虛擬時間槽內試圖傳輸的概率，Pc為假定傳輸條件下的沖突概率，N為有限的重傳次數。

Pc=1-(1-pa)|CS∩INr|,

(2)

其中|CS∩INr|是在載波偵聽范圍(CS)和干擾區(INr)干擾結點次數。從文獻[10]獲知：

(3)

至于移動性影響，使用一個簡單而有效的方案估計兩個節點移出彼此通信范圍的概率，文獻[11]假設D0、D1和D2是節點s和節點r在T0、T1和T2時刻之間的距離。在t時刻的距離可以表示為D(t)2=At2+Bt+C，能夠得出：

(4)

其中，t1=T1-T0，t2=T2-T0。

RLL(t)=Tb-t=tb+T0-t

(5)

則節點s和節點r之間的鏈路穩定性可以表示為：

(6)

由公式(1)和(6)，可以得出節點之間的鏈路質量為：

Pq=Psucc*Ps,

(7)

本文使用Pq來選擇候選集。當節點i和發送節點s之間的鏈路質量Pq滿足Pq>ε時，節點i可以被選作為候選節點集中的候選，ε是一個域值。

在候選集中要選擇一個最佳的轉發節點，需要把兩跳相關的位置信息、局部拓撲和移動適應都考慮在內。離目的地較近的位置，可以減少傳輸期間的跳數，從而降低路由協議的成本。然而，一味的求近也會讓路由空洞產生更多無用的邊界轉發。移動適應性矯正優化傳輸方向。在網絡中這點很重要，因為一個朝目的節點相反方向移動的節點轉發有負面的影響，應該消除這種節點。此外，這樣的節點可能會導致路由空洞，也應該被淘汰。

綜上所述，當節點s轉發數據包時，下一個節點應該位于節點s和目標節點組成的矩形區域內。當一個節點發送數據包給鄰居時，會插入自己當前位置的信息。鄰居接收到數據后，會重新計算發送節點的位置，更新自己的鄰居集。節點i的優先級定義為：

(8)

圖1 節點i的優先級的示例

本文修改了ACKs、hello和數據包的格式。在ACK包中插入移動自適應信息、“更好的鄰居”集和位置，使發送節點能夠作優先級的評估。在hello包和數據包中插入發送節點的位置和鄰居信息，使接收者能夠更新其“更好的鄰居”集。

圖1闡述了節點i的優化，算法1描述了OR-LqT協議。

算法1基于鏈路質量與局部拓撲信息的機會路由協議定義：Ns()：節點s的鄰居集.Nbs()：離節點s到目的地更近的一組鄰居集.Lqs，a()：節點s與節點a之間的鏈路質量.Cs()：節點s的候選集.ds，D：節點S與節點D之間的距離.ifnodesreceivesadatapacketfromnodeathen{replyanACKwithNbs()Ns()andmovingdirectionmd}endififnodeshasadatapackettoforward：then{determinethecandidatesetCs()basedonlinkqualityLqs，a()}{broadcastthepackettoallthenodesinCs()；}endififnodesreceivesanACKfromnodekthen{computethepriority；}foreverynodeiinCs()doifmd>0&&Nbi()！=0thenPr=1-di，Dds，D?è???÷×Nbi()Ni()endifendforendif

3 協議實現和性能評價

本文利用NS-2，將PRR*d[8]、貪婪地理路由協議GPSR[4]、反應式路由協議AODV協議[12]和OR-LqT進行對比仿真。設置網絡45,80,125,180個節點的傳輸范圍250米和每12500平方一個節點的密度。移動模型采用隨機移動模型(RWP)[13]暫停時間為0秒。仿真參數如表1所示。

表1 仿真參數

對比不同的移動速度與鏈路質量參數，使用空洞數、丟包率、時延和路由負載度量反映這些協議性能實驗結果如下：

空洞數：空洞節點意味著除了自己不能找到一個更接近目的地的節點。圖2顯示了傳統的GPSP、PRR*d和OR_LqT空洞的數量。在GPSR和PRR*d中貪婪轉發可能產生一個局部最大值，這意味著一個節點不能找到比它自己更好的下一跳。在本文的OR_LqT協議里，拓撲和地理信息都被考慮，其中包含移動自適應性和位置。移動自適應性，指示移動方向和一個更好下一次選擇，矯正轉發到最佳區域并減少空洞數。與GPSR協議相比，減少了41.5%的空洞數目，而與PRR*d相比，OR_LqT減少了大約33.5%。

圖2 空洞數與節點數的關系圖

圖3 丟包率與節點數的關系圖

丟包率：比較OR_LqT與其他協議的丟包率。圖3顯示，在GPSR中采用貪婪轉發，而在PRR*d候選集選擇地理距離和鏈路成功接收率乘積的最大值。在AODV中，節點的移動性導致拓撲頻繁變化和鏈路故障的發生。因此，它增加了丟包率。在OR_LqT協議中可以獲得更精確的鏈路質量測量，這種測量考慮了干擾和移動性，使用了MAC層成功傳輸概率的信息和路由層的移動模型。因此,避免了不穩定的傳輸。平均而言，OR_LqT與AODV相比丟包率減少大約62%，與PRR*d相比，丟包率減少大約21%。

圖4 平均端到端時延與節點數的關系圖

圖5 標準化路由負載與節點數的關系圖

平均端到端時延：圖4顯示所提出的OR_LqT，PRR*d，GPSR和AODV的平均時延。在AODV協議中，每個節點保持一個確定的路由。頻繁的鏈路故障引起了很多的改變，從而增加路由發現的次數。也增加了平均時延。因為GPSR僅考慮地理轉發，所以可能會導致路由空洞。邊界轉發為了擺脫空洞需要采取額外的跳數和時延，而提出的OR_LqT考慮了位置和移動適應性。如圖2所示。空洞的數目隨著周邊轉發次數的減少而減少。此外，精確的鏈路質量測量帶來一個更穩定的傳輸環境，減少數據包的沖突概率和重傳次數。由于上述原因，平均時延降低。相比AODV協議，提出的OR_LqT降低了約61%的平均時延，而與PRR*d相比，平均時延降低約22%。

圖6 標準化路由負載與速度的關系圖

標準化路由負載：圖5顯示了OR_LqT、PRR*d、GPSR和AODV的負載。機會路由負載計數了hello包和ACK的數量，而路由控制分組的數量，像RREQ、RREP和hello包都算在AODV路由協議中。當路由失敗時，一個新的路由發現開啟。因此，在AODV中增加了路由控制包的數量和路由負載。然而，機會路由數據包被廣播轉發，在AODV協議中較少的路由控制包產生，包的大小如ACK也比RREQ、RREP、RRER包小。如上圖所示。OR_lqT降低了丟包率和空洞數，以至于重傳和去除空洞的額外轉發次數也減少，因此，降低了負載。平均而言，與PRR * D相比，負載減少了約21%，與GPSR相比，負載減少約32%。

OR_lqT針對高速動態環境，本文也驗證了其在不同場景下的性能。仿真了四個不同的協議在網絡大小為1250*1250平方米和125個節點，速度從0m/s到20m/s。圖6顯示變化速度的標準化路由負載。當網絡是靜態或者接近靜態時，通過路由發現獲得的路由信息可以維持很長一段時間。因此，AODV比機會路由性能更好，但在AODV中，隨著節點速度的增加，拓撲結構的變化更頻繁，路由發現次數增多，導致更多的負載。

5 結語

本文為移動Ad Hoc網絡提出了一種基于鏈路質量和局部拓撲的機會路由協議。該協議通過鏈路質量選擇候選集，并通過優先級選擇下一個轉發節點，增加直接轉發概率，減少路由空洞數。其中鏈路質量同時考慮了干擾和節點的移動性，而候選集的優先級則根據它們的位置、局部拓撲和移動適應性來決定。仿真結果表明，同樣的移動環境下，本文提出的OR_LqT在空洞數量、平均時延、丟包率和負載方面比其它路由協議具有更好的性能。

參考文獻：

[1] Q Wang, X Wang, X Lin. Mobility Increases the Connectivity of K-hop Clustered Wireless Networks[J]. Proc.ACM MobiCom，2009(9)：121-132.

[2] S Biswas， R Morris. ExOR:Opportunistic Multi-Hop Routing for Wireless NetWorks[J]. Proc.ACM SIGCOM，2005，35(4)：133-144.

[3] Z Zhang， R KrishnanAn. An Overview of Opportunistic Routing in Mobile Ad Hoc Networks[C]// Proc.IEEE MILCOM, San Diego:2013：119-121.

[4] B Karp Harvard, H T Kung. GPSR:greedy perimeter stateless routing for wireless networks[C]// Proc.ACM MobiCom，Boston:Harvard University,2000：243-254.

[5] M K Song, S Guo, T He， et al. Link Correlation Aware Opportunistic Routing[J]. Proc.IEEE INFOCOM.2012,14(1)：3036-3040.

[6] Z Wang, C Li, Y Z Chen. Local cooperative relay for opportunistic data forwarding in mobile ad-hoc networks[J]. Proc.IEEE ICC，2012,1(8)：5381-5386.

[7] S Yang, F Zhong, C K Yeo, et al. Position based Opportunistic Routing for Robust Data Delivery in MANETs[J]. Proc.IEEE GLOBECOM，2009(1)：1-6.

[8] K Seada, M Zuniqa, A Helmy， et al. Energy-efficient forwarding strategies for geographic routing in lossy wireless sensor networks[J]. Proc.ACM SenSys， 2008(4):108-121.

[9] Z Zhao, T Braun, D Rosario， et al. CAOR:Context-aware Adaptive Opportunistic Routing in Mobile Ad-hoc Networks[J]. Proc.IFIP WMNC，2014(10)：1-8.

[10] Y Yang, H J C, L Kung. Modeling the Effect of Transmit Power and Physical Carrier Sense in Multi-hop Wireless Networks[C]. Proc.IEEE INFOCOM，2007：2331-2335.

[11] X M Zhang, K Chen, Y Zhang， et al. A Probabilistic Broadcast Algorithm Based on the Connectivity Information of Predictable Rendezvous Nodes in Mobile Ad hoc Networks[C]. Proc.IEEE ICCN workshop of BDeHS,2014.

[12] C Perkins, E Belding-Royer, S Das. Ad Hoc On-Demand Distance Vector (AODV) Routing[C]. IETF RFC Santa Barbara:University of California,2003:3561.

[13] D B Johnson, D A Maltz. Dynamic Source Routing in Ad Hoc Wireless Networks[J]. Mobile Computing,Kluwer Academic Publishers,1996(353)：153-181.