無線Mesh網絡集中式信道分配算法設計

劉 賀,張陸勇,陳明剛,李 茁

(北京郵電大學信息與通信工程學院,北京100876)

0 引言

無線Mesh網絡多接口多信道分配方案中,公共信道分配(CCA)是常見的分配方案[1,2]。該方案中,每個節點的射頻端都分配相同信道,不能有效提高多信道的利用率。文獻[3]根據Hyacinth架構提出了一種集中式的WMN信道分配算法,但該方案限定了路由模式為靜態路由,應用場景有限。在此基礎上提出了CAR-NL算法,通過采用節點優先級和鏈路分組的方法,保證了網絡中流量集中區域的帶寬需求,而且通過網關節點對網絡信道質量的評估,提高了全網的整體容量,降低了鏈路間干擾。

1 系統模型

1.1 多接口WMN架構

Hyacinth無線Mesh網絡架構如圖1所示。圖中,網關節點作為樹型拓撲的根節點,承載網絡中大部分流量的輸入和輸出,并負責對網絡負載狀況做出評估和分配方案,假設網關節點有足夠能力來進行相關處理。Mesh路由節點負責匯聚和轉發由終端節點上傳的業務流量,起到負載均衡和多跳傳輸的作用。終端節點多用于業務流上傳的發起者或者業務流反饋回來的接收者。

圖1 Hyacinth無線Mesh網絡架構

1.2 節點優先級評估

網關節點承載網絡中大部分流量,作為樹形拓撲的根節點,其優先級設為最高。其余節點優先級表示為:

式中,R(i)為節點i的優先級;ATi為節點i的總流量;Mi為節點i距離網關中心節點的最小跳數;NICi為節點i的網絡接口數量;N為節點i的相鄰節點數。

這樣,流量承載負荷越大、距離網關節點跳數越小的節點優先級越高。這樣的節點等級劃分可以適應集中式無線Mesh網絡架構的流量承載要求。

1.3 節點鏈路分組

文獻[1,3]中指出了信道分配問題和圖著色問題很類似,但是標準圖著色算法無法解決一些實際場景中的限制問題。比如通過邊著色公式無法解決節點的射頻端數量有限的限制問題,因為每個節點對應的色彩數量應該不大于該節點的射頻端數量。

通過按照優先級遞減的順序遍歷節點,在當前節點所屬的所有單跳鏈路中,選取該節點和優先級更低的節點組成的鏈路進行分組,分組數量(包括當前節點和優先級更高的節點組成的組)與該節點的射頻端數量一致,以此來解決節點分配信道數量超過自身接口數量的矛盾,并且通過鏈路分組實現每個節點所屬鏈路的信道分配只經過一次優化過程就可以達到最優,防止出現多次調整已分配方案以及由此引發的漣漪效應。分組按照鏈路中節點優先級和鏈路預期流量負荷為標準,將優先級高、預期流量負荷較大的鏈路單獨分組,即給予更高的鏈路帶寬。

1.4 鏈路負載和鏈路干擾

每個接入路由節點把自身的流入流出負載信息發送給網關節點,網關節點由此計算出端到端業務流對鏈路的占用比例。

傳統的基于IEEE 802.11無線網絡數據傳輸會受到路徑內干擾和路徑間干擾[4]。路徑內干擾是指在發送節點載波偵聽范圍內同一時刻只能有一個節點進行接收,其余節點要保持空閑狀態;路徑間干擾是指不同鏈路中相鄰節點發送或者接收信息時對對方造成的干擾。這些都會造成鏈路數據傳輸速率的降低和網絡系統吞吐量的降低。減少這些干擾的有效手段就是調整不同鏈路在同一節點或者相鄰近節點處的帶寬分配,即通過評估鏈路負載,給不同業務流路徑分配不同傳輸質量的信道,來保證不同帶寬需求的業務流路徑,達到高效利用有限帶寬的目的。

2 信道分配設計和算法

2.1 負載評估

假設在傳輸范圍內每一對Mesh路由節點都有直接的鏈路連接。網絡的連接性由每個節點上分配的公共信道來保證,所有的控制信息均通過固定的公共信道來進行傳輸。首先計算出鏈路l的容量:

式中,Cl為鏈路l的容量;Q為可用信道數量;CQ為每條信道的信道容量;Ll為鏈路l干擾范圍內虛擬鏈路的數量。

然后計算出鏈路l的預期負載為:

式中,對于節點對(s,d),φl為鏈路l預期負載;Pl(s,d)為節點對(s,d)間所有可行路徑(Path)中通過鏈路l的數量;P(s,d)為節點對(s,d)間所有可行路徑數量;B(s,d)為節點對(s,d)在業務流中預期的負載(所需帶寬)。式(3)表明,鏈路的初始預期負載就是所有可行路徑上的負載之和。

根據式(1)計算出每個節點的優先級,并根據節點優先級和預期負載通過遍歷節點對所屬鏈路進行分組。當可用分組數(即節點射頻模塊數量)大于節點鏈路數時,可以進行非重疊信道的均勻分配;反之則需要將負載較低的多條鏈路合并到相同分組中。

考慮到相鄰鏈路間可能的信道干擾,在相鄰鏈路分配相同信道時按照式(4)進行鏈路容量評估[3],

式中,bwl為鏈路l的評估容量;φl為鏈路l的預期負載;Intf(l)為鏈路l干擾范圍內鏈路集合;C為理論信道容量。

如果相同信道上鏈路容量之和大于信道理論帶寬時,則更換負載較低鏈路分配的信道來進行調整。

2.2 信道分配

節點優先級和節點鏈路分組完成后,首先對節點和鏈路進行降序排序,然后遍歷節點依次為節點所屬的鏈路進行信道分配。假設節點擁有射頻模塊數量為q,節點a和節點b通過鏈路l連接,會有以下2種情況:

①節點a和節點b的已分配信道數量小于q,則從未分配信道列表里面選取負載最小的信道添加到節點a和節點b的已分配信道列表中;

②有一個節點(假設節點a)已經分配了q條信道,b還有剩余鏈路組未分配信道,則從a中選取鏈路l所屬組已分配的信道,分配給鏈路l。并且將信道添加到節點b的已分配信道列表中。

CAR-NL算法信道分配流程如圖2所示。

圖2 CAR-NL算法流程

3 仿真

使用NS2作為仿真平臺進行CAR-NL算法信道分配方案的驗證。使用帶有 RTS/CTS的 IEEE 802.11MAC協議,路由則采用AODV協議,主要通過CAR-NL算法和CCA算法在多信道多射頻模塊前提下進行無線Mesh網絡的系統吞吐量和丟包率的比較。網絡拓撲采用9節點矩陣網絡結構。為了簡化和產生模擬實驗,將矩陣初始節點設為網關節點。每個信道的初始帶寬設為1 M,業務流設為CBR類型,速率設定為300 kbit/s和600 kbit/s兩種,每個節點最多的接口數設為3。節點水平和垂直間距為200 m,每個節點的接收范圍小于節點兩跳距離,同時又大于單跳距離。

對吞吐量和丟包率的仿真結果如圖3和圖4所示。在系統中有8個隨機業務流時,單信道網絡和CCA網絡中的系統吞吐量明顯低于CAR-NL網絡吞吐量。表明當網絡中業務流逐漸增大時,單信道網絡系統容量由于多個業務流的干擾沒有明顯增長,而CAR-NL網絡系統吞吐量則實現了較大的增長。與此同時,隨著網絡負載的增大,不同業務流間的干擾也在逐漸增大,但從整體上看,CAR-NL網絡的丟包情況要明顯好于前二者,同時,有2個業務流丟包極少,即通過信道的高效利用實現了降低干擾的目標。

圖3 系統吞吐量仿真

圖4 系統丟包率仿真

4 結束語

在集中式無線Mesh網絡基礎上,分析了網絡負載要求和鏈路間干擾,提出了信道分配改進算法,并通過仿真表明,該算法在保持較低丟包率的同時能有效提高網絡整體吞吐量。集中式無線Mesh網絡多信道分配算法的發展方向大多集中在反映網絡拓撲和鏈路質量變化的動態自適應調整方面,對于無線Mesh網絡性能的提高具有重要的意義。

[1]HOSSAIN E.無線Mesh網絡架構與協議[M].易 燕,李 強,譯.北京:機械工業出版社,2009:235-380.

[2]DRAVES R,PADHYE J,ZILL B.Routing in Multi-radio,Multi-hop Wireless Mesh Networks[C].MobiCom'04,2004:114-128.

[3]RANIWALA A,GOPALAN K,CHIUEH T.Centralized Channel Assignment and Routing Algorithms for Multi-channel Wireless Mesh Networks[J].ACM Mobile Computing and Communications Review(MC2R),2004:50-65.

[4]REN J,QIU Z.Centralized Quasi-static Channel Assignment in Multi-Radio Wireless Mesh Networks[C].Communication Systems.ICCS 2008.11th IEEE SingaporeInternational Conference,2008:1149-1154.