基于跨層快速鄰居感知的OLSR協(xié)議*

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

(西北工業(yè)大學(xué)自動化學(xué)院，西安710129)

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

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

1OLSR協(xié)議

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

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

2 幾種鄰居感知方法

2．1OLSR 協(xié)議

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

具體的過程如圖1所示。

圖1 OLSR鄰居感知

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

2．2 Fast-OLSR 協(xié)議

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

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

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

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

2．3 鏈路層反饋機制

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

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

3 基于跨層快速鄰居感知的OLSR協(xié)議

3．1 跨層快速鄰居感知

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

算法1 OLSR_nb_set更新算法

鏈路層采用802．11協(xié)議，支持CTS/RTS，網(wǎng)絡(luò)層采用OLSR協(xié)議。

當(dāng)OLSR_nb_set的更新是由網(wǎng)絡(luò)層hello消息觸發(fā)的時，采用OLSR協(xié)議中鄰居感知的處理過程，如圖1所示。若OLSR_nb_set的更新是由鏈路層反饋引起的，則:

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

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

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

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

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

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

圖2 簡單場景

圖3 鄰居感知過程

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

仿真過程中，當(dāng)t=9．3s時，節(jié)點3進入網(wǎng)絡(luò)中，至完成組網(wǎng)所需的時間如表1所示。

表1 組網(wǎng)時間比較

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

3．3FS-OLSR

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

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

算法2 mpr_computation

4 仿真

4．1 仿真場景

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

表2 仿真相關(guān)參數(shù)

鏈路層采用支持RTS-CTS的802．11協(xié)議，網(wǎng)絡(luò)層分別采用OLSR、Fast-OLSR和FS-OLSR協(xié)議，路由協(xié)議相關(guān)參數(shù)見表3。

表3 路由協(xié)議相關(guān)參數(shù)

4．2 仿真結(jié)果

4．2．1 路由開銷

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

圖4 路由開銷

4．2．2 丟包率

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

圖5 丟包率

5 結(jié)論

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

［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］ 孫雨耕，張靜，孫永進．無線自組傳感器網(wǎng)絡(luò)［J］．傳感技術(shù)學(xué)報，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］韓瀟，郭達偉，劉航，等．一種無線傳感器網(wǎng)路異步MAC廣播機制［J］．傳感技術(shù)學(xué)報，2011，24(5):719－723．

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