無線自組織網路由算法研究

魏長虎

摘要：無線自組織網因其快速自動組網和無中心節點等特性，得到越來越廣泛的應用。無線自組網的核心技術包括MAC層接入技術和網絡節點間的路由算法。不同的路由算法應用于不同的場景，也各有其優缺點，本文主要介紹幾種常用路由算法，并對其做簡要對比。

關鍵詞：自組網;OLSR;AODV

1.引言

無線自組網具有在無中心節點參與的情況下自行組網的特點，特別適合應用于某些特殊場景。MAC層接入技術和路由算法作為其核心，一直都是專家們研究的熱點內容。MAC層接入技術主要有競爭機制和預留機制以及混合機制三種方式，而路由算法主要分表驅動路由和按需路由，以及在某些應用中兩種方式的結合，即混合式路由。本文將分別介紹每一分類的特點及其典型的代表算法，并簡要對比其優缺點。

2. 路由算法

無線自組織網絡具有節點多跳可達、節點快速移動等等特點，這些特點使得承載其上的應用靈活方便，但也需要健壯且穩定的路由協議予以支持。自組網路由協議必須能夠在節點快速移動時快速收斂路由表，并維持網絡連接的可靠性和穩定性。無線自組織網絡路由協議的主要功能是實現分包路由，確保分包從源節點到目的節點的逐跳正確傳輸。除此以外，自組織網絡寶貴的帶寬資源、無線通信信道不對稱等特點，也對承載其運行的路由協議提出了嚴格要求。路由算法的分類方法有很多，按照路由條目的生成時機可分為表驅動路由協議、按需路由協議和混合路由協議（圖1）。

2.1 表驅動路由

表驅動路由協議也叫先驗式路由協議。使用這類路由協議的節點全程保存并動態更新一張全網可達的路由表。當節點有數據要發送時，可以實時的查到下一跳路由，因此此類路由最大的優勢是實時性強。這類路由協議一般需要定期發送路由幀，來更新和維持路由條目，所以其開銷較大。下面簡要介紹典型的表驅動協議OLSR協議。

2.1.1 OLSR

OLSR是優化鏈路狀態路由協議的簡稱。通過在全網范圍內周期性地交換網絡拓撲信息和鏈路狀態信息，運行OLSR協議的每個節點都維護全網路由條目。該協議采用了多點中繼（Multiple Point Relay，MPR）算法來減少路由幀的發送和轉發數量，即只有MPR節點才能轉發控制幀，而不是全網洪范，這將節省大量的網絡開銷。MPR節點的計算有一套比較復雜的步驟，為了全網有一個統一的計算結果，節點需要使用“HELLO”消息發布全網在線節點，實際就是自己的一跳鄰居節點。從“HELLO”報文的在線節點向量表中，節點學習到一個一跳鄰居集合，通過該集合中的一跳鄰居節點，可以到達所有的二跳鄰居，節點利用學習到的全網拓撲圖，就可以計算出到達所有其它節點的最優路徑，一般是最短路徑，生成最終的路由條目，并將其存儲在路由表中，路由表常駐內存。這種以空間換時間的思想，使得節點發送數據業務時能夠最快速的查找到路由條目，具有最高的實時性和最短的業務時延。

優點：業務時延可忽略，并且優化了鏈路狀態路由協議算法，盡量減少了協議開銷。

缺點：節點依然需要定期維護路由，因此不支持休眠;路由收斂較慢;開銷較大。

2.2 按需路由

顧名思義，按需路由[4]協議在節點發送數據業務并且查找不到合適的路由條目時，會啟動路由發現過程，這點與表驅動路由不同。由于是按需建立路由，所以節點維護的路由一般僅僅是網絡拓撲的一小部分，其需要的協議開銷非常小。按需路由分為路由發現和路由維護兩個階段。此類路由協議的主要差別體現在路由發現的過程、計算和維持信息的方法、數據傳輸的方法。此類路由主要有AODV、DSR等協議。

2.2.1 DSR

DSR（Dynamic Source Route）的路由[1]發現過程：如圖2所示，節點S發送報文給節點D，先查找路由表，發現沒有相應的路由條目，于是節點S發起到節點D的路由發現。源節點S洪泛一個Route Request（RREQ）;每一個中間節點在轉發該RREQ的時候，都將自己的地址信息加在RREQ中。目的節點D收到RREQ后，發送一個Route Reply（RREP），RREP中保存了從S到D的中間節點，及S到D的路由信息;RREP的發送依據的是將RREQ中保存的節點路徑反轉;節點S收到RREP幀之后，可學習到S到D的路由條目;

DSR的路由維護過程：當節點S向D發送數據的時候，整個路由信息都包含在報文頭部，中間節點就依據報文頭中的路由信息來轉發。因此使用該路由算法，報文的頭部大小與路由長短有關系。

優點：

1）源路由，可保證無環路;

2）不要求中繼節點緩存全網路由，允許偵聽建立局部路由信息;

3）由于是按需路由，降低了路由規模和開銷;

4）支持單向鏈路;

缺點：

1）每個數據包頭帶有完整路由信息，額外開銷;

2）泛洪路由搜索，可能導致沖突和短暫廣播風暴;

3）路由緩存，路由過期失效。

2.2.2 AODV

本節描述AODV（Ad Hoc On-Demand Distance Vector Routing）協議[2]的路由發現過程。在節點需要發送數據而又查不到路由條目時，開啟路由發現過程，使用廣播報文發送RREQ分組。AODV協議支持已有鏈路上的中間節點回應RREQ請求。找到可用路由條目，則中間節點或目的節點將采用單播的方式向源節點回復一個RREP報文，RREP剛剛建立的反向路由逐跳傳輸。因此，AODV要求鏈路必須時雙向可用的。與DSR不同的是，AODV在節點上維護路由表，所以數據包不需要再頭部攜帶路由信息，提高了幀效率。AODV的路由發現過程如圖3所示。

2.3 混合式路由

802.11s HWMP（Hybrid Wireless Mesh Protocol） [3]。該協議融合了表驅動式和按需式兩種路由路由思想。HWMP的表驅動式路由是一種基于樹的路由，主要用于拓撲相對靜態的環境中，使用主動式路由需要確定一個根節點，根節點周期性地廣播路由路徑請求包（PREQ），HWMP協議據此構建和維護樹形邏輯拓撲。HWMP協議中的按需路由使用PREQ和PREP機制在兩節點之間建立路由，節點間使用PREQ和PREP消息進行度量信息交互，并且在PREQ中采用序列號來保證路由的時效性。

2.4 表驅動路由與按需路由比較

使用表驅動路由協議，由于節點全程維護一張全網路由表，所以節點發送數據時可實時的獲取到下一跳，業務的延遲較小，但為此產生的周期性路由控制報文開銷也是巨大的。隨著網絡規模的增加，表驅動路由的開銷將帶來巨大的影響甚至無法使用。與之不同的是，按需路由協議無需維持全網路由表，在路由開銷方面的表現優秀。但因為發送數據時可能需要比較復雜的路由發現過程，故業務的時延方面表現略差。

按需路由協議和表驅動路由協議各有其優缺點，一般來講，應該根據自組網使用場景的不同選取合適的路由協議。目前越來越多的研究將表驅動路由與按需路由結合，取長補短，這將更能提升自組織網絡的系統性能。

3. 結束語

在自組網中，路由算法的優劣直接決定了數據轉發經過幾跳可達、路由查找是否實時，對業務的性能影響很大。因此根據網絡的規模、具體的業務場景、以及成本的考慮，選擇合適的路由算法尤為重要。本文介紹了幾種常用路由算法的原理，但由于時間原因，還沒有給出對應算法的仿真結果。對算法的仿真將是本人下一步的研究重點。

參考文獻

[1] 張簡麗，許洪光. 基于DSR的路由協議綜述[J]. 通信技術. 2009. （204）：137-139.

[2] C. Perkins， E. Belding-Royer， S.Das. Ad hoc On-Demand Distance Vector（AODV） Routing. July 2003.

[3] 李艷，王娜. 基于HWMP協議的無線MESH動態備份路由協議[J]. 福建師大福清分校學報. 2016. （5）：6-9.

[4] 張立明，唐海濤，王健，魏曉輝，張仲明. DSR和AODV路由協議虛擬仿真實驗平臺設計[J]. 《實驗室科學期刊》. 2018. （6）：21-3.BC88E35E-4677-4FB4-AD3E-D944F6A698AB