基于選播機制的無線Mesh網絡網關選取路由算法*

李陶深，丘小蘭，葛志輝

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

1 引言

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

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

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

2 網絡模型與選播路由樹

2.1 網絡模型

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

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

2.2 選播模型

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

2.3 選播路由樹

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

圖2 選播路由樹模型示意

3 基于最小時延的WMN網關選取路由算法

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

3.1 選播路由樹的構造

選播路由樹構造的具體步驟如下。

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

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

·若P為空，在選播樹T上選擇從源節點S到網關選播組成員中時延最小的一條路徑，轉下一步。否則，轉上一步繼續構造選播樹T。

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

3.2 選播路由樹的維護

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

（1）節點加入網關組其操作步驟大致如下。

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

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

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

（2）節點離開網關組

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

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

其操作步驟如下。

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

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

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

（4）樹的重建

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

3.3 路由分析

路由分析模塊主要完成產生路由請求RREQ分組、處理和傳輸RREQ、處理路由請求、產生路由應答RREP、轉發RREP、網關組的維護等任務。下面是路由協議的具體實現過程。

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

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

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

·網關組組長記錄這段時間內收到的最大序列號、最小時延的路由請求信息分組，等待時間到達后，向源節點發送RREP消息。

·轉發RREP。RREP以單播的方式沿RREQ傳播時所建立的反向路徑發送到源節點，這樣就建立了源節點到網關組某成員的正向路徑。

4 仿真實驗與算法性能

4.1 NS2仿真場景設置

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

4.2 實驗結果與分析

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

圖3 仿真拓撲結構

圖4給出了分組投遞率的實驗比較情況。從圖4可以看出，AODV算法根據跳數選擇路由，網絡中某些節點容易形成熱點區域，導致擁塞，使得經過這些熱點區域的分組丟失率增大。而本文引入選播機制的DGRA算法能平衡網絡負載，從眾多路徑中選擇最優路徑，從而避免擁塞區域，因此分組投遞率高于AODV。

圖4 分組成功投遞率對比

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

圖5 端到端時延對比

圖6 平均路由開銷對比

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

5 結束語

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

1 葛志輝,李陶深,張繼成.無線Mesh網絡逐層信道分配策略研究.廣西大學學報(自然科學版),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網絡公平感知路由算法設計與仿真.系統仿真學報,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