基于改進OLSR路由協(xié)議mesh網絡的研究

蘭 鵬，李二濤，何桂仙

(1.杭州電子科技大學計算機應用研究所，浙江 杭州310018;2.東陽市東政電機有限公司，浙江 東陽322100)

0 引言

無線mesh網絡是一種基于多跳自組織、對等網絡技術的新型網絡結構，具有移動寬帶的特性，無線mesh網絡廣泛應用于軍事通信、災后緊急救援、傳感器網絡等眾多領域［1］。由于無線mesh網絡的分布式、無中心、自組織、節(jié)點可移動等技術特點，使得它存在很多技術難題需要解決，其中最關鍵的是路由協(xié)議的改進［2］。為了實現(xiàn)網路節(jié)點之間的負載均衡，提高系統(tǒng)資源的利用率和網絡的吞吐量，降低網絡延時［3］，本文基于最優(yōu)化鏈路狀態(tài)(Optimized Link State Routing，OLSR)協(xié)議［4］，提出一種 MPR 集合選擇算法，綜合最小化MPR的冗余性和每個節(jié)點的負載，避免了原有算法可能會導致網絡節(jié)點負載過重、出現(xiàn)網絡擁塞的情況［5－7］。

1 OLSR路由協(xié)議

OLSR路由協(xié)議是由移動自組網工作組提出的一種表格驅動、主動式路由協(xié)議，它繼承了鏈路狀態(tài)算法的穩(wěn)定性，同時對經典的鏈路狀態(tài)算法進行了優(yōu)化。它的核心是多點中繼(Multi Point Relay，MPR)，MPR是被專門選定的節(jié)點，用于在洪泛過程中轉發(fā)廣播消息。OLSR路由協(xié)議對純鏈路狀態(tài)算法所做的優(yōu)化如下:

(1)采用多點中繼機制有效的減少了洪泛過程中的轉發(fā)廣播消息。每個節(jié)點都從其鄰居節(jié)點中選擇一組節(jié)點作為MPR，只有被選作MPR的節(jié)點才負責轉發(fā)控制消息。相比經典的洪泛機制極大的降低了信息開銷，這是一種高效的洪泛機制。其工作機制如圖1所示。

圖1中節(jié)點a選擇它的鄰居節(jié)點m1、m2、m3作為它的MPR集合，當節(jié)點a洪泛廣播消息的過程中只有節(jié)點m1、m2、m3轉發(fā)這條消息，然后節(jié)點m1、m2、m3分別在它們自己的一跳鄰居節(jié)點里面選擇MPR集合，進行洪泛消息的轉發(fā)，依此類推，將節(jié)點a洪泛消息傳播到網絡中的每一點，建立起了可靠的網路拓撲;

圖1 MPR洪泛機制

(2)只有MPR節(jié)點才產生鏈路狀態(tài)消息，縮減了控制分組的大小。網絡中的節(jié)點并不發(fā)布與所有一跳鄰居節(jié)點的鏈路信息，而只聲明與其中繼選擇節(jié)點(MPR Selector)之間的鏈路。對比經典鏈路狀態(tài)算法，OLSR協(xié)議的局部鏈路狀態(tài)信息分布在網絡中。

OLSR協(xié)議非常適用于規(guī)模大、節(jié)點密度高的網絡，這是因為采用了MPR的優(yōu)化在這種網絡中表現(xiàn)良好。對比經典鏈路狀態(tài)算法，網絡的規(guī)模越大、節(jié)點密度越高，MPR優(yōu)化的效果越好。OLSR協(xié)議使用逐跳路由，即每個節(jié)點使用其本地信息為分組選擇傳輸路由。

2 OLSR協(xié)議MPR選擇的不足及改進

一個節(jié)點的MPR集合應該滿足:該節(jié)點通過其MPR集合中的節(jié)點能夠到達所有對稱兩跳相鄰節(jié)點;一個節(jié)點的MPR集合選擇得盡可能小，以便降低協(xié)議的開銷。

標準OLSR協(xié)議的貪婪算法雖然可以成功的選擇了一個MPR集，但是存在如下問題:(1)MPR集合存在冗余;(2)在選擇MPR集合時沒有考慮節(jié)點的負載，有的節(jié)點出現(xiàn)負載過重，有的節(jié)點處于閑置狀態(tài)，降低了整個網絡的資源利用率。

基于上述問題，提出了一種改進的選擇MPR集合的算法，改進了原有算法在選擇MPR集時的不足。在OLSR路由協(xié)議的HELLO消息里面有個意愿程度(willingness)字段，用它表示一個節(jié)點愿意承載和轉發(fā)其他節(jié)點的信息，其意愿程度可以設為0－7之間的任意一個整數(shù)。為了避免一個節(jié)點的被多次被其他節(jié)點選為MPR，我們可以動態(tài)的設置意愿程度這個字段，改進的MPR集合的選擇算法描述如下:

(1)將節(jié)點的MPR集合置為空，將節(jié)點的一跳鄰節(jié)點的意愿程度設為最大，即N_willingness域設為WILL_ALWAYS(既為7);(2)如果存在到達某個兩跳鄰節(jié)點的唯一通路的鄰節(jié)點，則選擇此節(jié)點作為MPR，并將N_willingness的值減1，刪除N2中目前被MPR集覆蓋的節(jié)點。如果此時N2中不存在任何節(jié)點，算法結束，否則進入下面步驟;(3)統(tǒng)計N_willingness的值，選擇集合N中的willingness值最小的，如果只有一個刪除掉，如果有多個，刪除其中可到達性最小的，然后跳到b中繼續(xù)執(zhí)行。這里刪除willingness最小的，表示不能選擇負載較大的節(jié)點作為MPR集合，因為前面已經有很多節(jié)點選擇其作為MPR集合，選擇其他負載較小的節(jié)點可以優(yōu)化網絡性能，且此時選擇的MPR集合的冗余性最小;(4)將一個節(jié)點的每個接口的MPR集合組合在一起，則建立MPR集合。

算法的流程如圖2所示:

圖2 改進MPR選擇算法的流程圖

該改進算法在選擇MPR集合時通過一跳鄰節(jié)點的willingness實時記載該節(jié)點的負載?？紤]了網絡的多路徑的負載，提高了系統(tǒng)的資源利用率，不會出現(xiàn)一些節(jié)點負載過重，一些節(jié)點處于閑置的狀態(tài)，又通過刪減N中的willingness最小的節(jié)點，減小了MPR的冗余，也減小了路由的開銷。

3 實驗系統(tǒng)及結果分析

為了驗證本文提出的MPR改進算法在mesh網絡上性能的提高與改進，基于標準的OLSR路由協(xié)議和改進的路由協(xié)議分別在網絡的吞吐量、延時、轉發(fā)TC消息分組數(shù)等方面進行比較。

實驗采用的硬件節(jié)點是ubiqiti公司的router-station pro，在空曠的200m×200m區(qū)域布置10個節(jié)點組成多跳、自組的無線mesh網絡。在測試網速的吞吐量及網絡延時采用的是NetIQ Chariot，統(tǒng)計轉發(fā)TC消息分組數(shù)是通過監(jiān)聽MPR集合接口收到的數(shù)據(jù)包獲取。

如圖3所示，原OLSR路由協(xié)議組成的mesh網絡的吞吐量大概為4.8Mbps，而修改后MPR選擇算法后網絡的吞吐量大概為5.2Mbps，有了一定程度的提高。因為改進的MPR算法均衡了網絡節(jié)點的負載，不會出現(xiàn)某些節(jié)點過載，而一些節(jié)點出現(xiàn)空閑的狀態(tài)，提高了網絡的傳輸數(shù)據(jù)的容量。

圖3 無線mesh網絡的吞吐量

如圖4所示，原OLSR協(xié)議的端到端的延時時0.023s，改進的算法組成的mesh網絡的延時0.018s，可以看出較大程度上改進了網絡的延時，原因是節(jié)點的鏈路選擇避開了負載較重的鏈路，充分利用了網絡的資源。

OLSR協(xié)議的TC消息由MPR廣播和轉發(fā)，將整個消息洪泛到整個網絡，通過收集網絡中的的轉發(fā)TC分組的數(shù)量，可以反映網絡中的MPR集的冗余程度。如圖5所示，改進的OLSR的路由協(xié)議在TC消息轉發(fā)(50個)方面要優(yōu)于原來的OLSR協(xié)議(55個)，減少了MPR集合的冗余，降低了原協(xié)議10%的開銷，改進了原來OLSR協(xié)議的性能。

圖4 無線mesh網絡的端到端的延時

圖5 無線mesh網絡的轉發(fā)TC分組統(tǒng)計

4 結束語

本文從改進mesh網絡的節(jié)點負載的、提高網絡資源利用率出發(fā)，提出了一種新的OLSR協(xié)議MPR集合的算法，把節(jié)點的負載信息加到節(jié)點的意愿程度的字段上，在選擇節(jié)點作為MPR集合時，通過排序，把節(jié)點負載較重的節(jié)點排除出去，既均衡了MPR集合中節(jié)點的負載，也減少了MPR集合的冗余度。通過實驗收集數(shù)據(jù)，改進的OLSR協(xié)議在網絡延時、網絡吞吐量、網路轉發(fā)TC消息數(shù)量等方面均優(yōu)于原來的通過貪婪算法所選擇的MPR集。

［1］陳林星，曾曦，曹毅.移動Ad-Hoc網絡—自組織分組無線網絡技術［M］.北京:電子工業(yè)出版社，2006:1－44.

［2］Navda v，Kashyap A，Das S R.Design and Evaluation of iMesh:an Infrastructure-mode Wireless Mesh Network［C］.WoWMoM:Sixth IEEE International Symposium on a World of Wireless Mobile and Multimedia Networks，2005:164－170.

［3］Song Wen，F(xiàn)ang Xu-ming.Routing with congestion control and load balancing in wireless mesh networks［C］.Chengdu:6th International Telecommunications Conference，2006:719 －724.

［4］Clausen T，Jacquet P.Optimized Link State Routing Protocol(OLSR)［EB/OL］.http://www.ietf.org/rfc/rfc3626.txt，2003－03－20.

［5］Bai Yun-fei，Liu Yuan-an，Yuan Dong-ming.An Optimized Method for Minimum MPRs Selection Based on Node Density［C］.Chengdu:Wireless Communications Networking and Mobile Computing 2010 6th International Conference，2010:1－4.

［6］Kenji Yamada，Tsuyoshi Itokawa，Teruaki Kitasuka.Cooperative MPR Selection to Reduce Topology Control Packet in OLSR［C］.Fukuoka:TENCON 2010 IEEE Region 10 Conference，2010:293 －298.

［7］Zhao Xian-ming，Song Hua-zhu，Xia Hong-xia.Using Ant Colony Algorithm for Solving Minimum MPR set and OPNET Simulation［C］.Nanjing:The 1st International Conference on Information Science and Engineering，2009:898 －901.