基于跨層快速鄰居感知的OLSR協議*

李 楊，劉 航，郭達偉，閆丁麗

(西北工業大學自動化學院，西安710129)

近年來，由于便攜式設備在移動性、儲存能力和無線通信能力等方面的迅速發展，各種無線傳輸網絡得到廣泛應用，也對個人通信提出了更高的要求，這種需求引起了對無需基站支持并可及時部署應用的無線網絡——Ad Hoc網絡的研究興趣。Ad Hoc網絡作為一種多跳路由、無中心、自組織的無線網絡，無需預先架設固定基礎設施，組網方便、快捷，不受時間和空間限制，既可用于軍事戰地網絡、災難救援、移動會議、遠距離或危險環境中的目標監控等場合，還可用于有線網系統或蜂窩末端網絡的擴展。

Ad Hoc網絡無線傳輸和多跳路由的特點，使處于移動場景中的節點頻繁地發現、丟失與鄰居之間的鏈路，對鄰居感知算法提出了更高的要求，本文即是在此背景下，對Ad Hoc網絡路由協議進行研究，并對基于 OLSR［1－4］路由協議的鄰居感知方法、MPR計算進行了改進。

1OLSR協議

OLSR協議是由IETF MANET(Mobile Ad Hoc Network)工作組提出的一種表驅動式的鏈路狀態路由協議，節點之間周期性地交換各種控制信息，通過分布式計算來更新和建立自己的網絡拓撲圖，協議中的關鍵思想是多點中繼(multipoint relaying，MPR)，被鄰居節點選為MPR的節點需要周期性地向網絡廣播控制信息，非MPR節點不產生也不轉發控制信息，與傳統的鏈路狀態路由協議相比，該算法大大降低了控制信息洪泛的開銷。

OLSR主要采用兩種控制消息分組:HELLO分組和TC(Topology Control)分組。OLSR協議采用周期性廣播HELLO分組來偵聽鄰居節點的狀態;MPR節點產生并向全網絡廣播TC消息，聲明該節點與MPR Selector(選該節點做MPR的節點)之間的鏈路。網絡中的節點通過TC消息可以獲取網絡的拓撲結構，通過Dijkstra算法，動態的計算到達各個節點的最短路由路徑，形成路由表。

2 幾種鄰居感知方法

2．1OLSR 協議

OLSR協議通過周期性發送hello消息實現鄰居感知，節點通過hello消息在網絡中公告自己的存在，通過對接收到的hello消息處理來感知和鄰居節點的鏈路狀態，如A和B為兩個互為鄰居節點，具體的操作為:①初始情況下，A發送一個空的hello消息，在網絡中告知鄰接點自己的存在。②當B收到該hello消息時，B感知到了A的存在，在鄰居表中添加A的表項，并標注與A的狀態為單向鄰居。③B在生成hello消息時把自己的鄰居節點加入到廣播鄰居節點列表中，此時A的地址存在于B廣播的hello信息的廣播鄰居節點列表中。B等待HELLO_INTERVAL超時廣播該hello消息。④當A接收到B發送的hello消息，若在該hello消息的廣播鄰居節點列表中存在A的地址，則表明A和B為雙向鄰居，A在本地的鄰居表中添加B的表項，并標記狀態為雙向鄰居。

具體的過程如圖1所示。

圖1 OLSR鄰居感知

OLSR協議中節點通過hello消息的交互感知鄰居節點的存在以及判斷鄰居的狀態是否為雙向鄰居，在OLSR協議中，只有雙向的鄰居才能用于路由計算，并且只有雙向的鄰居才能被選作MPR，當一個節點選擇出一些節點作為MPR后，也是通過在hello消息中廣播告知鄰居的。

2．2 Fast-OLSR 協議

Fast-OLSR［5－7］是針對快速移動場景提出的基于OLSR協議的改進方法，在快速移動的場景中，由于路由信息發送周期相對比較長，致使路由更新不及時，從而導致大量丟包，然而單純地提高控制信息的發送頻率又會帶來路由開銷大量的增加，Fast-OLSR提出了對OLSR協議的改進，在盡量增加少的路由開銷的情況下，提高路由更新的速度。

在Fast-OLSR協議中，支持默認模式和快速模式，當節點感知到自己處于快速運動的情況下，節點由默認模式切換到快速模式(反之，由快速模式切換到默認模式)，當處于快速模式時，節點通過Fast-Hello和Fast-TC的交互進行控制信息的交互。Fast-OLSR鄰居感知的機制與OLSR相同，但具有較高的發送頻率，同時在Fast-Hello消息的廣播鄰接點列表中，設置一個最大值(如5個)，當節點接收到Fast-Hello，對消息進行處理并回復一個Fast-Hello。

Fast-OLSR通過具有更高發送頻率的Fast-Hello消息進行鄰居的感知，在Fast-OLSR協議中，只有處于默認模式的節點才被選作MPR，并把已選的MPR節點通過Fast-Hello消息告知鄰接點，當MPR節點與該節點鏈路失效，節點通過Fast-TC消息告知網絡中的其他節點該鏈路的丟失。

Fast-OLSR通過增大快速移動節點控制信息的發送頻率提高路由更新的速度，解決了由于路由更新不及時導致的丟包問題，然而同時也引入了更多的路由開銷，使Fast-OLSR不能適應帶寬資源有限的網絡。

2．3 鏈路層反饋機制

文獻［8］提出了一種跨層鄰居感知機制，通過鏈路層反饋的信息，快速的感知到鄰居節點與本節點之間的鏈路丟失情況，當一個包重發的次數超過某個值(例如7次)時，在本地的鄰居表中把該鄰居的狀態標記為單向，系統則通過重新計算路由獲取可用的路徑，再次重發該包，有效減少了因鄰居鏈路失效而導致的丟包。當再次收到該鄰居的hello消息時，若在廣播鄰居節點列表中找到本節點的地址，則把該鄰居的狀態恢復為雙向鄰居。

文獻［8］中提出的跨層機制通過鏈路層反饋的信息，能快速感知到鄰居之間的鏈路的丟失，但是并不能有效提高發現鄰居的頻率。鄰居的發現依然是依靠hello消息。

3 基于跨層快速鄰居感知的OLSR協議

3．1 跨層快速鄰居感知

在現有OLSR 鄰居感知方法的基礎上，采用跨層［9－11］機制，利用鏈路層反饋的信息，對網絡層的鄰居表(OLSR_nb_set)進行添加、刪除和更新，可以在不增加控制開銷的情況下，提高與鄰居節點之間鏈路的感知頻率。具體的操作如算法1所示。

算法1 OLSR_nb_set更新算法

鏈路層采用802．11協議，支持CTS/RTS，網絡層采用OLSR協議。

當OLSR_nb_set的更新是由網絡層hello消息觸發的時，采用OLSR協議中鄰居感知的處理過程，如圖1所示。若OLSR_nb_set的更新是由鏈路層反饋引起的，則:

(1)當鏈路層檢測到信道上有數據傳輸時，若幀目的地址不是本節點或者是廣播［12］幀，則把幀源節點地址添加到OLSR_nb_set中，并標注鄰居狀態為單向，若在OLSR_nb_set中已存在該節點，則把單向鄰居的有效時間更新。

(2)若幀目的地址是本節點，表明兩個節點之間至少存在單向鏈路，在OLSR_nb_set中更新或添加相應的表項:(a)若幀類型為CTS:則表明兩個節點間進行了RTS-CTS過程，是雙向鄰居，在OLSR_nb_set中更新或添加該表項;(b)若幀類型為ACK:表明對方已成功接收到數據，兩個節點間存在雙向鏈路，為雙向鄰居，在OLSR_nb_set中更新或添加該表項;(c)若幀類型為data:802．11協議中，對于點對點的單播數據，在傳輸數據幀之前，需要完成信道的爭搶占用，即RTS-CTS的過程，MAC層接收到目的地址為本節點的數據幀，表明兩個節點間存在雙向鏈路，為雙向鄰居，在OLSR_nb_set中更新或添加對應的表項。

(3)若在MAC傳輸數據時，對于某一個節點，連續重傳多次(如7次)，仍收不到ACK，表明該本節點和該鄰居之間的鏈路丟失或者為單向鏈路，則在OLSR_nb_set中更新對應的表項并重新計算路由，獲取可用的路徑重發該數據。

3．2 跨層快速鄰居感知方法分析

該方法通過鏈路層反饋的信息，可以在不增加控制開銷的情況下，感知到節點之間的鏈路狀態及其變化，在網絡層對鄰居表進行更新，從而有效提高鄰居感知能力和鏈路狀態更新頻率，尤其對于后入網的節點與周圍節點的鄰居感知速度有了很大的提高。

如圖2所示的場景中，節點1和2之間有數據流傳輸，節點3由遠端向節點1和2移動，當t時刻節點3移動到網絡中，對于OLSR協議和Fast-OLSR協議，節點3與節點1的鄰居感知過程如圖1所示，需要三次hello消息的交互;而當采用跨層快速鄰居感知方法時，在節點3與節點1的鄰居感知過程中，三次hello消息交互則不是必需的。例如，在圖3所示的鄰居感知過程中，當節點3進入到網絡中后，感知到節點1在發送數據，此時節點3把節點1加入到OLSR_nb_set中，并標注狀態為單向鄰居;當發送hello消息時，把節點1的地址加入到廣播鄰居列表中，當節點1收到該hello消息，把節點3加入到OLSR_nb_set，且鄰居狀態為雙向;若節點1有數據需要發送給節點3，當節點3收到該數據即在OLSR_nb_set中更新與節點1的鄰居狀態為雙向。

圖2 簡單場景

圖3 鄰居感知過程

通過NS2仿真軟件對該場景的仿真可以驗證其有效性。其中，鏈路層采用支持RTS/CTS的802．11協議，網絡層分別采用OLSR協議(HELLO_INTERVAL分別設置為2s，1s)和支持跨層快速鄰居感知的OLSR協議(HELLO_INTERVAL=2s)，比較節點3加入到網絡所需的時間(移動到通信范圍時至組網完成所需的時間)。

仿真過程中，當t=9．3s時，節點3進入網絡中，至完成組網所需的時間如表1所示。

表1 組網時間比較

從表1中可以看出，對于后入網節點，由于采用跨層快速鄰居感知方法，改進后的協議所需的組網時間明顯小于OLSR協議，當提高OLSR協議hello消息的發送頻率(Fast-OLSR)時，所需的組網時間降低，但同時由于增加了控制消息的數量，使得控制開銷大大增加。

3．3FS-OLSR

由以上的仿真分析可知，快速鄰居感知方法利用鏈路層信息更新鄰居表，使得鄰居感知能力提高，降低了鄰居感知所需的時間，結合OLSR協議，本文提出了一種適用快速移動場景的快速鄰居感知OLSR協議(Fast Neighbor Sensing-OLSR，FS-OLSR):(a)鄰居感知采用本文提出的跨層快速鄰居感知方法;(b)MPR算法的改進:鑒于節點的移動性，在選擇MPR集時參考節點鏈路信息的及時性［13］，定義鄰居節點的新鮮度為:對應鄰居表項的更新時間。

把雙向的一跳鄰居按照新鮮度進行排序，在MPR計算過程中，優先選擇新鮮度較大的鄰居作為MPR，直至覆蓋所有的兩跳鄰居。MPR的計算過程如算法2所示。

算法2 mpr_computation

4 仿真

4．1 仿真場景

64個節點分布在1 000 m×1 000 m的場景中。其中，50個節點是靜止的，其余的節點以相同的速度隨機快速移動，分別在移動速度為4 m/s、8 m/s、12 m/s、16 m/s、20 m/s、24 m/s、28 m/s、32 m/s 情況下進行仿真。靜止節點間有一定的數據傳輸，在靜止節點與移動節點間CBR數據流傳輸;仿真相關參數分別見表2。

表2 仿真相關參數

鏈路層采用支持RTS-CTS的802．11協議，網絡層分別采用OLSR、Fast-OLSR和FS-OLSR協議，路由協議相關參數見表3。

表3 路由協議相關參數

4．2 仿真結果

4．2．1 路由開銷

由圖4的仿真結果可以看出，當節點移動速度為0 m/s時，FS-OLSR協議的路由開銷大于OLSR和Fast-OLSR協議，這是由于FS-OLSR在MPR計算時可能增加MPR的個數，致使TC消息的產生和轉發節點個數增加，路由開銷相應增加，略大于OLSR的路由開銷，當節點靜止時，不會產生和發送Fast-Hello和Fast-TC，即沒有提高控制信息的發送頻率，因此，在節點速度為0 m/s時，OLSR協議和Fast-OLSR協議的路由開銷大致相同。隨著移動速度提高(4 m/s～32 m/s)，Fast-OLSR路由開銷明顯大于FS-OLSR;這是由于快速移動節點提高了控制信息的發送頻率，導致Fast-OLSR協議的開銷明顯增加。

圖4 路由開銷

4．2．2 丟包率

當節點移動速度較低時(小于4 m/s)，OLSR和Fast-OLSR的丟包率要低于FS-OLSR，這是由于FSOLSR增加了路由開銷，使得丟包增多。而當速度大于4 m/s，FS-OLSR的丟包率明顯低于OLSR，這是因為FS-OLSR協議中MPR攜帶的信息是更加及時的消息，使得路由的準確性提高，有效降低了丟包率;在一定的速度范圍內(8 m/s～24 m/s)，FS-OLSR得性能要優于Fast-OLSR，因為Fast-OLSR路由開銷明顯大于FS-OLSR，大量的路由開銷增加網絡的負載，造成大量的丟包，但當速度繼續增加(大于24 m/s)，Fast-OLSR得性能優于FS-OLSR，這是因為FS-OLSR并沒有提高拓撲消息的更新速度，使得路由消息的更新速度極不適應拓撲的高速度變化。

圖5 丟包率

5 結論

本文分析了幾種OLSR鄰居感知的方法，并提出了一種基于跨層機制的快速鄰居感知方法，仿真表明跨層快速鄰居感知的方法能有效提高鄰居感知的能力，降低鄰居感知所需的時間和開銷，在此基礎上提出了一種基于OLSR協議的改進方法，采用快速鄰居感知方法，并對MPR計算進行改進，使更加適合于快速運動的場景。并對其進行了仿真，仿真結果表明，FS-OLSR在快速移動的場景中有比較好的性能，但同時也應看到，FS-OLSR并沒有提高拓撲的更新頻率，在速度太高的情況下，路由協議的性能變得很差，這也是今后的工作中需要研究解決的問題。

［1］ Adjih C，Clausen T，Jacquet P，et al．Optimized Link State Routing Protocol［S］．RFC3626，IETF，October 2003．

［2］ ZHANG huawei，ZHOU yun．Comparison and Analysis AODV and OLSR Routing Protocols in Ad Hoc Network［C］//International Conference on Wireless Communications，Networking and Mobile Computing，2008．1－4．

［3］ LI Zhiyuan，Hu Jinhong．Simulation and Analysis of Optimized OLSR［C］．Multimedia Information Networking and Security，2010．97－100．

［4］ 孫雨耕，張靜，孫永進．無線自組傳感器網絡［J］．傳感技術學報，2004，17(6):331－335．

［5］ Benzaid M，Minet P，Al Agha K．Analysis and Simulation of Fast-OLSR［C］//Vehicular Technology Conference，2003．1788－1792．

［6］ Mounir Benzaid，Pascale Minet，Khaldoun Al Agha．Integrating Fast Mobility in the OLSR Routing Protocol［C］//Conference:Mobile and Wireless Communication Networks-MWCN，2002．217－221．

［7］ Hakim Badis，Khaldoun Al Agha．Scalable Model for the Simulation of OLSR and Fast-OLSR Protocols［C］//Proceedings of IFIP Med-Hoc-Net’03．2003．

［8］ Michael Voorhaen，Chris Blondia．Analyzing the Impact of Neighbor Sensing on the Performance of the OLSR protocol［C］//Proceedings of the 4th International Symposium on Modeling and Optimization in Mobile，Ad Hoc and Wireless Networks，2006．1－7．

［9］ Marco Conti，Enrico Gregori，Giovanni Turi．A Cross-Layer Optimization of Gnutella for Mobile Ad Hoc Networks［C］//Proceedings of the 6th ACM International Symposium on Mobile Ad Hoc Networking and Computing，2005．343－354．

［10］ Michelle X Gong，Scott F Midfiff，Shiwen Mao．A Cross-Layer Approach to Channel Assignment in Wireless Ad Hoc Networks［J］．Mobile Networks and Applications，2007，12(1):43－56．

［11］ Yung-Sze Gan，Masson S，Guibe G，et al．Cross-Layer Optimization of OLSR with a Clustered MAC［C］//Military Communications Conference，2006．1－7．

［12］韓瀟，郭達偉，劉航，等．一種無線傳感器網路異步MAC廣播機制［J］．傳感技術學報，2011，24(5):719－723．

［13］張洪，黃閩英．基于高速移動節點網絡的OLSR路由協議改進［J］．成都大學學報(自然科學版)，2008，27(1):38－44．