基于選播機制的無線Mesh網(wǎng)絡網(wǎng)關選取路由算法*

李陶深，丘小蘭，葛志輝

（廣西大學計算機與電子信息學院 南寧 530004）

1 引言

無線Mesh網(wǎng)絡（wireless mesh network,WMN）與因特網(wǎng)互連成為近年來研究的熱點。為了完成WMN與因特網(wǎng)的互連，通常在一個WMN中配備多個Mesh網(wǎng)關。若節(jié)點有連接因特網(wǎng)的需求，它首先要找到所有可連接的網(wǎng)關，然后通過有效的網(wǎng)關選取策略在這些備選網(wǎng)關中根據(jù)一定的判定標準選擇一個最佳網(wǎng)關接入因特網(wǎng)。然而，由于現(xiàn)實的WMN中流量分布明顯不均，網(wǎng)內(nèi)大部分業(yè)務流量都匯聚于網(wǎng)關，使得一部分網(wǎng)關負載過重，容易造成局部網(wǎng)絡擁塞，所以網(wǎng)關節(jié)點往往是形成網(wǎng)絡擁塞的熱點區(qū)域及網(wǎng)絡性能的瓶頸[1]。因此，網(wǎng)關選擇策略是優(yōu)化Mesh網(wǎng)絡吞吐量、改善網(wǎng)絡性能的主要途徑。

目前在WMN網(wǎng)關選取策略方面的解決方案主要有3類：第1類是以移動節(jié)點到網(wǎng)關的跳數(shù)為選擇標準[2]，這種策略簡單、易實現(xiàn)、收斂快、時延小，但在網(wǎng)絡出現(xiàn)擁塞時會導致網(wǎng)絡性能嚴重下降[3]；第2類是將跳數(shù)和其他因素綜合起來作為選取標準，如參考文獻[4]提出將跳數(shù)和網(wǎng)絡的擁塞水平、信道爭用水平綜合起來考慮，參考文獻[5]則用跳數(shù)和網(wǎng)關負載作為網(wǎng)關選擇和切換的標準；第3類是將跳數(shù)之外的因素作為選擇標準，如參考文獻[6]提出的WMN網(wǎng)關選取策略著重于如何把終端分配到各個網(wǎng)關。這3類網(wǎng)關選取策略在尋找路徑或更新路由時，基本上都采用泛洪的方式，當網(wǎng)內(nèi)節(jié)點數(shù)較多、負載很大時，這些協(xié)議尋徑和更新路由的控制開銷迅速增多，不僅嚴重阻塞網(wǎng)絡，而且大大減少數(shù)據(jù)發(fā)送成功率，降低路由算法的性能。

選播是一種新的網(wǎng)絡服務通信模式，己被IPv6定義為標準的通信服務[7]。選播的關鍵在于，對于一個給定的應用和一組可提供相同服務的服務器，它能夠為客戶端有效地尋找到性能“最好”的服務器。本文將研究基于選播思想的WMN網(wǎng)關選取優(yōu)化問題，將網(wǎng)關的選取問題看作網(wǎng)絡選播通信來處理，并提出了基于選播機制的網(wǎng)關選取路由模型，設計實現(xiàn)相關的協(xié)議與算法，分析比較其性能。

2 網(wǎng)絡模型與選播路由樹

2.1 網(wǎng)絡模型

本文把WMN抽象為一個無向圖G=(V，E)，其中，V表示W(wǎng)MN中有限節(jié)點的集合，這些節(jié)點在一定范圍內(nèi)通過無線信道進行通信，其中一些節(jié)點是通過有線電纜與因特網(wǎng)直接相連的網(wǎng)關節(jié)點,用G(A)={g1,g2,…,gk}表示；E表示網(wǎng)絡中連接節(jié)點對的通信鏈路集合。如果節(jié)點u和v之間的距離小于或等于節(jié)點通信的有效距離r，則稱這兩個節(jié)點互為鄰居節(jié)點且它們之間存在一條邊（即有路由鏈路相連）。

WMN網(wǎng)關選取的路由問題可以描述如下：給定一個WMN網(wǎng)絡G=(V，E)和一個選播 QoS請求Q=(C，G(A)，Req)，其中，C是請求服務的Mesh客戶節(jié)點，G(A)表示網(wǎng)關組（選播組）節(jié)點集合，Req為QoS參數(shù)約束。這樣就可以將WMN的網(wǎng)關選取問題轉(zhuǎn)化為QoS約束的路由選擇問題。

2.2 選播模型

WMN中有若干網(wǎng)關節(jié)點時，終端用戶需要選擇一個合適的網(wǎng)關節(jié)點接入因特網(wǎng)，這就屬于典型的網(wǎng)絡選播通信問題。為了提高網(wǎng)絡服務的可用性和健壯性，本文將選播機制引入網(wǎng)關選取路由，如圖1所示，將所有接入因特網(wǎng)的網(wǎng)關節(jié)點抽象成一個選播組，這些網(wǎng)關節(jié)點分布在網(wǎng)絡的各個部分，每個網(wǎng)關節(jié)點都是這個選播組成員。當帶QoS約束的用戶端需要服務時，通過有效的選播機制能夠自適應地選擇最優(yōu)的網(wǎng)關節(jié)點為其服務，從而節(jié)省網(wǎng)絡帶寬，減少阻塞，保證WMN良好的接入性能。

2.3 選播路由樹

選播路由樹（也稱網(wǎng)關樹）模型如圖2所示，它包含3類節(jié)點。第1類是網(wǎng)關組（即選播組）組長節(jié)點，此節(jié)點所在的網(wǎng)絡區(qū)域的單播地址空間必須與其所擁有的選播地址空間相同，即目的地址為單播地址的數(shù)據(jù)分組，可以按照正常的單播路由方式被路由到此組長節(jié)點。在本模型中，組長主要負責維護網(wǎng)關組的序列號碼，以及在路由模塊中自適應地選擇“最優(yōu)”的網(wǎng)關節(jié)點為請求節(jié)點提供服務。第2類節(jié)點是中間節(jié)點，也稱作樹成員節(jié)點，它們不能提供接入因特網(wǎng)服務而只用于支撐網(wǎng)關樹框架，這類節(jié)點一般都是路由器。第3類節(jié)點是葉子節(jié)點，也稱作網(wǎng)關組成員節(jié)點，這類節(jié)點是可以提供接入因特網(wǎng)服務的節(jié)點，一般都是網(wǎng)關。在本模型中，組長節(jié)點與葉子節(jié)點都可以提供接入因特網(wǎng)服務，具有一個共同的選播地址。

圖2 選播路由樹模型示意

3 基于最小時延的WMN網(wǎng)關選取路由算法

本文提出的基于最小時延的網(wǎng)關選取路由算法（DGRA）是在AODV協(xié)議上的選播擴展，由選播路由樹的構(gòu)造、選播路由樹的維護、路由分析3部分組成。

3.1 選播路由樹的構(gòu)造

選播路由樹構(gòu)造的具體步驟如下。

·將源節(jié)點S放入集合U中，TE=Null。

·在所有 u∈U 且 u埸G’(A),v∈P的邊（u,v）中，找出時延小于源節(jié)點S對業(yè)務提出的最小時延限制的所有邊，計算樹上所有節(jié)點的不在樹上的鄰居節(jié)點若加入后的所有可能干擾度，然后從中選出干擾度最小的節(jié)點v。將節(jié)點v并入U中，并將節(jié)點v與它的父節(jié)點間的鏈路加入集合TE。

·若P為空，在選播樹T上選擇從源節(jié)點S到網(wǎng)關選播組成員中時延最小的一條路徑，轉(zhuǎn)下一步。否則，轉(zhuǎn)上一步繼續(xù)構(gòu)造選播樹T。

·輸出在網(wǎng)中建立的以源節(jié)點S為根的選播路由樹T=(U,TE)，過程結(jié)束。

3.2 選播路由樹的維護

本模塊主要完成節(jié)點加入網(wǎng)關組、節(jié)點離開網(wǎng)關組、樹的鏈路斷開時的處理、樹的重建等工作。

（1）節(jié)點加入網(wǎng)關組其操作步驟大致如下。

·當節(jié)點欲加入網(wǎng)關組時，將廣播帶有J_flag標志的路由請求信息分組RREQ。不是網(wǎng)關組成員的中間節(jié)點收到此RREQ后，再把這個RREQ廣播給鄰節(jié)點。該節(jié)點將建立逆向路由條目，更新選播路由表。

·選播組成員節(jié)點收到RREQ后，更新路由和選播表，單播RREP給源節(jié)點。路徑上節(jié)點更新路由表和選播表，建立前向路由。

·源節(jié)點選擇最大序列號和時延最小的路由，并激活所選擇路由的下一跳信息，然后沿著所選路徑選播激活信息（AACT）。

（2）節(jié)點離開網(wǎng)關組

如果欲離開的網(wǎng)關組成員節(jié)點不是樹中的葉子節(jié)點，則只需把組地址置0；如果節(jié)點是樹的葉子節(jié)點,則單播P_flag標志的AACT分組信息到上游節(jié)點并刪除自己對應的路由表項,將自己從樹中刪除,上游節(jié)點收到這個P_flag標志的AACT后將刪除選播表中的有關項；如果自己是組成員或不是葉節(jié)點，剪枝過程就結(jié)束，否則繼續(xù)給自己的上游節(jié)點發(fā)送P_flag標志的AACT。

（3）樹的鏈路斷開時的處理

其操作步驟如下。

·下游節(jié)點廣播帶有J_flag標志的RREQ重新加入網(wǎng)關組，擴展域Agroup_delay為自己到組長的時延，只有具有最新的序列號且到群首的時延小于此RREQ中的Agroup_delay的樹成員才能回復。

·如果響應的上游節(jié)點不是組成員或是葉子節(jié)點，則設置定時器等待樹枝通過它重建，如果一段時間后沒有對應組激活的下游節(jié)點，則發(fā)送剪枝消息將自己從樹中剪去。

·如果鏈路修復失敗，網(wǎng)絡被分割，新分出來的網(wǎng)絡需要新的組長。如果發(fā)起修復的節(jié)點是組成員，則成為新組長，否則通過發(fā)送GL_flag標志的AACT選擇新的組長。

（4）樹的重建

當原本已分開的網(wǎng)絡部分又連接在一起時，就會帶來分開的樹又合并的問題。節(jié)點會收到一個hello分組，它所包含的信息與節(jié)點所保持的信息有所不同。如果節(jié)點是網(wǎng)關組的成員且是含有地址較低的組長的那部分樹的成員，那么它就會啟動樹的重新構(gòu)造過程。

3.3 路由分析

路由分析模塊主要完成產(chǎn)生路由請求RREQ分組、處理和傳輸RREQ、處理路由請求、產(chǎn)生路由應答RREP、轉(zhuǎn)發(fā)RREP、網(wǎng)關組的維護等任務。下面是路由協(xié)議的具體實現(xiàn)過程。

·若源節(jié)點需要向網(wǎng)關組成員發(fā)送數(shù)據(jù)，它首先查詢單播路由表。如果有到該組相關成員的路由項，則直接選擇一條時延最小的路由返回即可；如果沒有路由項，則源節(jié)點發(fā)送RREQ報文。

·如果接收到RREQ的中間節(jié)點不是選播組成員，則檢查自己是否有到該選播組的路由。如果有此路由項，則選擇一條最新時延最小的路由即可；如果沒有，則該節(jié)點重新廣播收到的RREQ，在選播路由表中添加到源節(jié)點的路由項，并把下一跳設置成將RREQ發(fā)送給它的節(jié)點。

·如果接收到RREQ的中間節(jié)點是選播組成員，則更新選播路由表，并把本節(jié)點的時延信息發(fā)送給網(wǎng)關組組長。組長節(jié)點可能會收到多個帶有時延信息的信息分組。

·網(wǎng)關組組長記錄這段時間內(nèi)收到的最大序列號、最小時延的路由請求信息分組，等待時間到達后，向源節(jié)點發(fā)送RREP消息。

·轉(zhuǎn)發(fā)RREP。RREP以單播的方式沿RREQ傳播時所建立的反向路徑發(fā)送到源節(jié)點，這樣就建立了源節(jié)點到網(wǎng)關組某成員的正向路徑。

4 仿真實驗與算法性能

4.1 NS2仿真場景設置

為了分析算法的性能，采用Linux下的NS-2.31版本進行仿真。首先在1 000×1 000 m2的區(qū)域內(nèi)生成6×5個節(jié)點的拓撲結(jié)構(gòu)，如圖3所示，節(jié)點4、15、19為網(wǎng)關節(jié)點。各節(jié)點都是WMN骨干層的MR，包括網(wǎng)關節(jié)點，處于靜止狀態(tài)。節(jié)點間的通信范圍是250 m，相鄰節(jié)點直線距離是190 m。業(yè)務流類型為CBR（恒定比特率，屬于UDP業(yè)務流），流量為每秒發(fā)送8個數(shù)據(jù)分組，分組大小為512 byte。業(yè)務流數(shù)目分別為 3、6、9、12、15、20 條，仿真時間為 300 s。

4.2 實驗結(jié)果與分析

以不同業(yè)務流數(shù)目下協(xié)議的分組投遞率、端到端時延和平均路由控制開銷為性能指標，對本文的DGRA算法和AODV算法進行比較。其中，分組投遞率是指實際收到和期望收到的分組數(shù)的比值，用于反映網(wǎng)絡所能支持的最大吞吐量，從而在一定程度上刻畫了算法的完整性和正確性；端到端時延則表示從數(shù)據(jù)源發(fā)送數(shù)據(jù)分組起到所有目的節(jié)點接收到該數(shù)據(jù)分組時的平均時間間隔，時延越小，說明響應越快，網(wǎng)絡性能越好；平均路由開銷是指路由控制分組數(shù)目與網(wǎng)絡層業(yè)務數(shù)據(jù)分組數(shù)目之比。

圖3 仿真拓撲結(jié)構(gòu)

圖4給出了分組投遞率的實驗比較情況。從圖4可以看出，AODV算法根據(jù)跳數(shù)選擇路由，網(wǎng)絡中某些節(jié)點容易形成熱點區(qū)域，導致?lián)砣?，使得?jīng)過這些熱點區(qū)域的分組丟失率增大。而本文引入選播機制的DGRA算法能平衡網(wǎng)絡負載，從眾多路徑中選擇最優(yōu)路徑，從而避免擁塞區(qū)域，因此分組投遞率高于AODV。

圖4 分組成功投遞率對比

圖5給出了端到端時延的實驗比較情況。從圖5可以看出，隨著網(wǎng)絡擁塞程度的增加，AODV數(shù)據(jù)分組的時延增加明顯，而DGRA在算法中支持了時延約束的要求，能夠進行局部路由重構(gòu)以盡快找到新的到達網(wǎng)關節(jié)點的QoS路由，整體上降低了網(wǎng)絡中傳輸?shù)臅r延。

圖5 端到端時延對比

圖6 平均路由開銷對比

圖6為不同業(yè)務流數(shù)目下平均路由控制開銷的變化情況。從圖6可看出，當網(wǎng)絡負載比較輕時，DGRA算法的平均路由控制開銷比AODV高，其原因是：DGRA通過選播樹實現(xiàn)對選播組成員的管理與維護，算法將產(chǎn)生大量的路由開銷。但是當網(wǎng)絡負載較重時，由于DGRA算法采用選播機制，源節(jié)點能夠自適應選擇更可靠的傳輸路徑，在傳輸過程中能夠減少鏈路發(fā)生斷裂的概率，使得路由協(xié)議的開銷減少。

5 結(jié)束語

本文對無線Mesh網(wǎng)絡網(wǎng)關選取策略進行研究，將選播通信機制應用于多網(wǎng)關選取路由的問題中，并針對實時性要求比較高的傳輸業(yè)務，設計了一種基于最小時延的無線Mesh網(wǎng)絡網(wǎng)關選取路由算法。該算法在引入選播機制的網(wǎng)關選取模型的基礎上，以時延為度量，為客戶節(jié)點提供響應最快的高質(zhì)量的因特網(wǎng)無線寬帶接入。仿真實驗結(jié)果表明，在WMN中，通過選播路由機制DGRA算法，能有效地解決多網(wǎng)關選取問題，保持較高的分組傳遞率、較低的數(shù)據(jù)分組時延，使接入網(wǎng)絡穩(wěn)定高效地運行。這在應用中具有很大的現(xiàn)實意義，能有效滿足網(wǎng)絡規(guī)模擴大的因特網(wǎng)流量需求。當WMN規(guī)模增大到一定程度時，可平衡往來于因特網(wǎng)的網(wǎng)絡流量負載，通過本文算法的選播機制就近選擇最優(yōu)的網(wǎng)關出口為用戶提供接入服務。

1 葛志輝,李陶深,張繼成.無線Mesh網(wǎng)絡逐層信道分配策略研究.廣西大學學報(自然科學版),2010,35(6):13～17

2 Shin C,Kim S,An S.Stable gateway selection scheme based on MANET with Internet.In:The Sixth IEEE International Conference on Computer and Information Technology,Dhaka,Bangladesh,2006

3 Brannstrom R,Ahlund C,Zaslavsky A.Maintaining gateway connectivity in multi-hop ad hoc networks.In:The IEEE Conference on LocalComputerNetworks30th Anniversary,Sydney,Australia,2005

4 宋文,方旭明.無線Mesh網(wǎng)絡公平感知路由算法設計與仿真.系統(tǒng)仿真學報,2007,19(18):4 320～4 325

5 Draves R,Padhye J,Zill B.Routing in multi-radio,multi-hop wireless mesh networks. In: ACM Annual International Conference on Mobile Computing and Nerworking,Philadelphia,USA,September 2004

6 Kim Y,Jeong Y,Seo M,et al.Load-balanced Mesh portal selection in wireless mesh network.In:Military Communications Conference,Orlando,USA,Oct 2007

7 Li Taoshen，Zhao Zhigang. An adaptive particle swarm optimization algorithm for anycast routing. Journal of Computational Information Systems,2011,7(5):1 559～1 566