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

魏長虎

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

關鍵詞：自組網;OLSR;AODV

1.引言

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

2. 路由算法

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

2.1 表驅動路由

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

2.1.1 OLSR

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

優(yōu)點：業(yè)務時延可忽略，并且優(yōu)化了鏈路狀態(tài)路由協(xié)議算法，盡量減少了協(xié)議開銷。

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

2.2 按需路由

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

2.2.1 DSR

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

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

優(yōu)點：

1）源路由，可保證無環(huán)路;

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

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

4）支持單向鏈路;

缺點：

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

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

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

2.2.2 AODV

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

2.3 混合式路由

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

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

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

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

3. 結束語

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

參考文獻

[1] 張簡麗，許洪光. 基于DSR的路由協(xié)議綜述[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協(xié)議的無線MESH動態(tài)備份路由協(xié)議[J]. 福建師大福清分校學報. 2016. （5）：6-9.

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