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

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

0 引言

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

1 系統(tǒng)模型

1.1 多接口WMN架構(gòu)

Hyacinth無線Mesh網(wǎng)絡(luò)架構(gòu)如圖1所示。圖中,網(wǎng)關(guān)節(jié)點作為樹型拓撲的根節(jié)點,承載網(wǎng)絡(luò)中大部分流量的輸入和輸出,并負責對網(wǎng)絡(luò)負載狀況做出評估和分配方案,假設(shè)網(wǎng)關(guān)節(jié)點有足夠能力來進行相關(guān)處理。Mesh路由節(jié)點負責匯聚和轉(zhuǎn)發(fā)由終端節(jié)點上傳的業(yè)務(wù)流量,起到負載均衡和多跳傳輸?shù)淖饔?。終端節(jié)點多用于業(yè)務(wù)流上傳的發(fā)起者或者業(yè)務(wù)流反饋回來的接收者。

圖1 Hyacinth無線Mesh網(wǎng)絡(luò)架構(gòu)

1.2 節(jié)點優(yōu)先級評估

網(wǎng)關(guān)節(jié)點承載網(wǎng)絡(luò)中大部分流量,作為樹形拓撲的根節(jié)點,其優(yōu)先級設(shè)為最高。其余節(jié)點優(yōu)先級表示為:

式中,R(i)為節(jié)點i的優(yōu)先級;ATi為節(jié)點i的總流量;Mi為節(jié)點i距離網(wǎng)關(guān)中心節(jié)點的最小跳數(shù);NICi為節(jié)點i的網(wǎng)絡(luò)接口數(shù)量;N為節(jié)點i的相鄰節(jié)點數(shù)。

這樣,流量承載負荷越大、距離網(wǎng)關(guān)節(jié)點跳數(shù)越小的節(jié)點優(yōu)先級越高。這樣的節(jié)點等級劃分可以適應(yīng)集中式無線Mesh網(wǎng)絡(luò)架構(gòu)的流量承載要求。

1.3 節(jié)點鏈路分組

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

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

1.4 鏈路負載和鏈路干擾

每個接入路由節(jié)點把自身的流入流出負載信息發(fā)送給網(wǎng)關(guān)節(jié)點,網(wǎng)關(guān)節(jié)點由此計算出端到端業(yè)務(wù)流對鏈路的占用比例。

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

2 信道分配設(shè)計和算法

2.1 負載評估

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

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

然后計算出鏈路l的預(yù)期負載為:

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

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

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

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

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

2.2 信道分配

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

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

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

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

圖2 CAR-NL算法流程

3 仿真

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

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

圖3 系統(tǒng)吞吐量仿真

圖4 系統(tǒng)丟包率仿真

4 結(jié)束語

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

[1]HOSSAIN E.無線Mesh網(wǎng)絡(luò)架構(gòu)與協(xié)議[M].易 燕,李 強,譯.北京:機械工業(yè)出版社,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.