WMN中的干擾避免部分重疊信道分配算法

楊 路，李玉潔，王詩言，肖皓月

(重慶郵電大學(xué) 通信與信息工程學(xué)院，重慶 400065)

0 引 言

網(wǎng)絡(luò)容量的大小是決定無線mesh網(wǎng)絡(luò)(wireless mesh network，WMN)[1]性能的關(guān)鍵因素，相鄰信道并行傳輸?shù)母蓴_是引起WMN容量銳減的主要原因[2]。多射頻多信道(multi-radio multi-channel，MRMC)技術(shù)可以有效提升網(wǎng)絡(luò)傳輸效率，增大網(wǎng)絡(luò)容量。稀缺的頻譜資源使得網(wǎng)絡(luò)中共信道干擾增加，引發(fā)WMN容量下降等問題[3]。

文獻[4-11]從不同角度驗證了有效的信道分配對WMN整體性能的改善。但大多數(shù)算法的使用范圍十分有限，文獻[10,11]提出的兩種干擾沖突圖都不適用于部分重疊信道的分配方案。已有學(xué)者證明，合理設(shè)計部分重疊信道(partially overlapping channels，POC)分配方法可以有效提高頻譜資源利用率和信道資源空間復(fù)用[12]。文獻[13]考慮了更貼合實際網(wǎng)絡(luò)的流量類型，充分利用部分重疊信道來設(shè)計端到端信道分配方案，有效改善了WMN網(wǎng)絡(luò)的性能。

以上分析可得，信道分配算法可以合理地使用部分重疊信道來提高網(wǎng)絡(luò)性能。因此，本文基于文獻[13]，提出了一種有效干擾避免和負載均衡的部分重疊信道分配(load balance and interference-avoid partially overlapped channels assignment，LBIA-POCA)算法，旨在提高網(wǎng)絡(luò)吞吐量，降低丟包率。

1 系統(tǒng)模型

1.1 網(wǎng)絡(luò)模型

本文基于IEEE802.11b標(biāo)準(zhǔn)，將MRMC-WMN建模為一個無向圖G(V,E)。 其中，V為節(jié)點集，代表mesh路由器、mesh網(wǎng)關(guān)和mesh客戶端。E為鏈路集，表示mesh路由器之間的無線鏈路。mesh路由器配備k(k≥2) 個無線接口，客戶端僅配備一個接口?？捎貌糠种丿B信道集C， 其可用信道個數(shù)為cn。

用F表示網(wǎng)絡(luò)中流的集合，定義流fi的負載為li，pi為流fi的路徑。從G(V,E) 中提取出加權(quán)流量子圖Gf=(Vf,Ef)， 則鏈路l上的權(quán)重和load(l)

(1)

下面列出本文中的一些假設(shè)：

(1)所有mesh路由器都是靜態(tài)的，以相同的傳輸功率工作，具有相同的傳輸范圍，mesh客戶端可以移動，但接入點不改變；

(2)mesh路由器的無線接口具有相同的配置、功能及發(fā)射功率；

(3)集中式信道分配由網(wǎng)關(guān)節(jié)點集中計算，進而發(fā)送給整個網(wǎng)絡(luò)；

(4)使用AODV路由協(xié)議預(yù)先確定路由路徑。

1.2 干擾模型

本文采用發(fā)送、接收端沖突避免協(xié)議干擾模[13]來建模。鏈路li=(ui,vi) 與lj=(ui,vi) 間的歐式距離d(li,lj) 定義為鏈路li的任意一個端點與鏈路lj的任意一個端點間的最短歐式距離，即

d(li,lj)=min(d(ui,uj),d(ui,vj),d(uj,vi),d(vi,vj))

(2)

對于部分重疊信道，由于兩個不同信道的頻譜重疊程度不同，干擾范圍RI(τ) 與信道間隔τ有關(guān)。建立雙徑地面?zhèn)鞑ツＰ?，通過發(fā)送節(jié)點的功率、天線增益等值推導(dǎo)得到同信道節(jié)點干擾范圍RI(τ)

(3)

進一步可推導(dǎo)得到信道間隔為τ時對應(yīng)的節(jié)點干擾范圍值RI(τ)

RI(τ)=Ir(τ)×RI(0)

(4)

RI(τmin)

(5)

定義鏈路li的潛在干擾范圍為IR(li)， 則IR(li) 可以表示為

IR(li)=D(ui,RI(0))∪D(vi,RI(0))

(6)

其中，D(ui,RI(0)) 為以點ui為圓心，以RI(0) 為半徑的圓形區(qū)域，是節(jié)點ui的干擾范圍；D(vi,RI(0)) 為節(jié)點vi的干擾范圍。

(7)

1.3 鏈路重要因子

為了最大化網(wǎng)絡(luò)公平性，將鏈路負載值作為衡量鏈路重要程度的一個指標(biāo)。定義鏈路重要因子，記為S, 用以確定網(wǎng)絡(luò)中鏈路的信道分配順序，鏈路l的S值定義為

(8)

由式(1)定義可知，load(l) 為鏈路l上的負載值，定義鏈路l兩端節(jié)點到網(wǎng)關(guān)節(jié)點的最小跳數(shù)為h(l)。 目前WMN的主要業(yè)務(wù)是提供Internet接入為用戶獲取網(wǎng)絡(luò)服務(wù)。因此，越靠近網(wǎng)關(guān)的節(jié)點，其承受的網(wǎng)絡(luò)壓力越大。由S值的定義可以看出，鏈路重要因子與鏈路負載、鏈路端節(jié)點距網(wǎng)關(guān)的最小跳數(shù)有關(guān)。S值越大，鏈路的重要程度越高，因此按照S值降序排列順序為鏈路進行信道分配。

2 信道分配算法

本文提出的LBIA-POCA算法主要由兩個階段組成，第一階段為節(jié)點間通信接口分配，確定節(jié)點接口間的連接關(guān)系。第二階段是無干擾信道分配階段：根據(jù)網(wǎng)絡(luò)干擾情況，對鏈路進行迭代信道分配，并使用靜態(tài)鏈路調(diào)度來保證網(wǎng)絡(luò)連接；最后，利用啟發(fā)式算法優(yōu)先為重要程度較高的鏈路分配無干擾時隙，對鏈路調(diào)度進行優(yōu)化，以提高網(wǎng)絡(luò)性能。

2.1 結(jié)點間通信接口分配

由于MRMC-WMN每個節(jié)點配有多個無線接口，因此在信道分配之前，確定結(jié)點間通信接口的連接關(guān)系是決定信道分配是否合理的關(guān)鍵因素。假設(shè)節(jié)點vi的度為d， 具有k個接口，與其通信的鄰居節(jié)點集N={n1,n2,…,nn}。 每個鄰居應(yīng)該選擇一個接口來傳送數(shù)據(jù)包給節(jié)點vi， 并且最好應(yīng)該將鄰居節(jié)點均勻地關(guān)聯(lián)到節(jié)點vi的k個接口，即每個接口上分配的負載是平衡的。而當(dāng)鄰居節(jié)點數(shù)大于節(jié)點接口數(shù)時，不能實現(xiàn)接口與鄰居節(jié)點的一一匹配，為實現(xiàn)節(jié)點接口間的負載均衡，采用基于Huffman樹的組合算法對鄰居節(jié)點進行組合。定義節(jié)點vi與其鄰居節(jié)點間的負載分別為r1,r2,…,rn， 確保具有所有可能組合的方差最小，即盡可能實現(xiàn)負載均衡。組合的鄰居節(jié)點與節(jié)點vi的一個接口匹配，并在信道分配階段整體考慮，分配相同信道。節(jié)點間通信接口分配見表1。

2.2 無干擾信道分配

本文采用集中式信道分配方式，集中服務(wù)器用于獲取網(wǎng)絡(luò)流的信息，并周期性更新信道分配。由于信道資源的有限性，無干擾傳輸?shù)男诺朗窒∪?。為此，按照鏈路重要因子S(l) 對各鏈路進行降序排列，將所有鏈路分成M個無干擾鏈路集。相應(yīng)地將每個數(shù)據(jù)幀的傳輸時間也劃分為M個時隙，對應(yīng)于M個無干擾鏈路集，每個時隙只有相應(yīng)的無干擾鏈路集中的鏈路會被調(diào)度。定義一個三維矩陣MCT， 包含鏈路、時隙和信道分配信息

(9)

(10)

最后為重要程度較高的鏈路分配更多滿足無干擾約束的時隙，根據(jù)鏈路重要因子S(l) 的順序，依次優(yōu)化鏈路調(diào)度。例如，對于鏈路lk， 若已為其分配時隙si， 則計算出鏈路lk與其余任意時隙sj(j≠i) 中各鏈路間是否存在干擾。若無則為鏈路lk增加改調(diào)度時隙，即可在時隙sj內(nèi)調(diào)度該鏈路；若無，則不能在時隙si內(nèi)調(diào)度鏈路lk。 無干擾信道分配算法流程見表2。

表2 無干擾信道分配算法偽代碼

3 仿真與結(jié)果分析

3.1 仿真環(huán)境

本文的算法性能驗證基于NS-3仿真平臺進行。使用N×N方格網(wǎng)格拓撲，即，每個頂點部署有mesh路由器，每條邊表示無線鏈路，網(wǎng)格步長設(shè)置為250 m，網(wǎng)關(guān)位于右下角?；贗EEE 802.11b標(biāo)準(zhǔn)，可用信道有11條，其中3條為正交信道。物理層的數(shù)據(jù)傳輸速率為2 Mbps。每個節(jié)點配置3個射頻接口。對于每個接口，傳輸范圍為250 m，載波偵聽范圍為550 m。使用的網(wǎng)絡(luò)數(shù)據(jù)流為恒定比特率數(shù)據(jù)流(constant bit rate，CBR)，數(shù)據(jù)包大小固定為512 Byte，數(shù)據(jù)包發(fā)送速率為200 kbps。具體的網(wǎng)絡(luò)參數(shù)設(shè)置見表3。

在仿真過程中，將實驗結(jié)果與端到端負載感知部分重疊信道分配(ELIA)[14]、負載平衡鏈路層協(xié)議(LBLP)[15]以及僅使用正交信道的分配算法(LBIA-OCA)進行比較。

表3 仿真參數(shù)

分別驗證網(wǎng)絡(luò)并發(fā)流數(shù)量和網(wǎng)絡(luò)大小對網(wǎng)絡(luò)吞吐量、端到端時延和丟包率的影響。為了減少誤差和隨機結(jié)果的影響，對每個方案運行10次，運行結(jié)果取均值來保證一致性和再現(xiàn)性。

3.2 并發(fā)流數(shù)量對性能的影響

在5×5網(wǎng)格拓撲中，將并發(fā)流數(shù)量從4條遞增到25條用以觀察網(wǎng)絡(luò)性能。隨著流量增加，各種算法的網(wǎng)絡(luò)吞吐量，平均端到端延遲和平均丟包率如圖1～圖3所示。

圖1 不同并發(fā)流數(shù)量下的網(wǎng)絡(luò)吞吐量

圖2 不同并發(fā)流數(shù)量下的網(wǎng)絡(luò)平均端到端時延

圖3 不同并發(fā)流數(shù)量下的網(wǎng)絡(luò)平均丟包率

圖1為所有算法網(wǎng)絡(luò)拓撲的平均吞吐量的比較圖。由圖1可得，隨著網(wǎng)絡(luò)中并發(fā)流數(shù)量逐漸增加，網(wǎng)絡(luò)吞吐量呈現(xiàn)增長趨勢。使用部分重疊信道分配的3種算法的性能明顯優(yōu)于基于正交信道分配的算法。當(dāng)網(wǎng)絡(luò)中的數(shù)據(jù)流數(shù)量為4和5時，網(wǎng)絡(luò)中的負載較輕，4種方案的信道分配均可以得出較好的結(jié)果，網(wǎng)絡(luò)吞吐量性能幾乎相同。此時網(wǎng)絡(luò)被劃分為幾個互不干擾的子網(wǎng)，并且正交信道足以實現(xiàn)非干擾數(shù)據(jù)傳輸。由于LBIA-OCA僅使用3個正交信道，因此當(dāng)流量增加時，很可能為相鄰鏈路分配相同的信道，由此產(chǎn)生的同信道干擾會阻止這些鏈路進行并行傳輸。適當(dāng)?shù)厥褂貌糠种丿B信道可以減少相鄰鏈路之間的干擾，并提高頻譜效率以實現(xiàn)更多并行傳輸，因此可以改善網(wǎng)絡(luò)性能。隨著網(wǎng)絡(luò)負載的增加，LBIA-POCA可以實現(xiàn)比LBLP和ELIA更高的網(wǎng)絡(luò)吞吐量。例如，當(dāng)網(wǎng)絡(luò)中的數(shù)據(jù)流數(shù)量為7時，LBIA-POCA，LBLP和ELIA方案的網(wǎng)絡(luò)吞吐量分別為3894.9 kbps、3221.4 kbps、2499.2 kbps。與ELIA相比，LBLP接口分配相對簡單，而ELIA的接口分配可以根據(jù)節(jié)點的負載情況自適應(yīng)調(diào)整，因此性能更好。LBLP沒有考慮部分重疊信道的特性，因此干擾模型不適合LBIA-POCA。由于合理的鄰居接口綁定和無時隙傳輸?shù)臅r隙劃分，LBIA-POCA實現(xiàn)了更好的網(wǎng)絡(luò)性能。圖2和 圖3 分別顯示了所有算法的平均端到端延遲和丟包率的比較圖。由于本文提出的算法分時隙傳輸，因此平均端到端延遲性能改善程度較小。平均丟包率與吞吐量互補，網(wǎng)絡(luò)丟包越多，吞吐量越低。

3.3 網(wǎng)格尺寸大小對性能的影響

在研究網(wǎng)格尺寸大小對性能的影響時，本文將網(wǎng)格大小從5×5逐漸增加到10×10，并在網(wǎng)絡(luò)上同時施加一定量的CBR流，以觀察網(wǎng)絡(luò)大小對性能的影響。隨著網(wǎng)格尺寸的增加，各種方案的網(wǎng)絡(luò)吞吐量，平均端到端延遲和平均丟包率如圖4～圖6所示。

圖4 不同網(wǎng)格大小下的網(wǎng)絡(luò)吞吐量

圖5 不同網(wǎng)格大小下的網(wǎng)絡(luò)平均端到端時延

圖6 不同網(wǎng)格大小下的網(wǎng)絡(luò)平均丟包率

隨著網(wǎng)絡(luò)規(guī)模的增加，網(wǎng)絡(luò)吞吐量不斷提高，平均端到端延遲和丟包率有一定程度的下降。當(dāng)網(wǎng)絡(luò)拓撲很小時，正交信道分配方案網(wǎng)絡(luò)的性能表現(xiàn)較差，主要是因為該方案無法為這些數(shù)據(jù)流分配不同的信道，數(shù)據(jù)包到達目標(biāo)節(jié)點需要很長時間，從而對網(wǎng)絡(luò)造成更嚴(yán)重的干擾。隨著網(wǎng)絡(luò)規(guī)模的擴大，網(wǎng)絡(luò)吞吐量和平均端到端延遲性能得到了提升，原因是較大的網(wǎng)絡(luò)允許更多的并行傳輸，為正交信道分配和部分重疊信道分配解決方案提供了更多空間來減少平均端到端延遲并提高網(wǎng)絡(luò)吞吐量。與正交信道分配方案相比，部分重疊信道分配利用的可用信道資源，數(shù)據(jù)包可以更快地到達目標(biāo)節(jié)點。

由圖4～圖6可見，LBIA-POCA算法的各項網(wǎng)絡(luò)性能優(yōu)于其它算法。當(dāng)網(wǎng)絡(luò)規(guī)模為9×9時，LBIA-POCA算法的網(wǎng)絡(luò)吞吐量為4367.3 Kbps，相比LBLP、ELIA和LBIA-OCA分別提高了6.5%、12.2%和40.8%；LBIA-POCA算法的平均端到端時延為1.4 s，相比LBLP、ELIA和LBIA-OCA分別減少了15.6%、24.8%和44.9%；LBIA-POCA算法的平均丟包率為0.073，相比LBLP、ELIA和LBIA-OCA分別降低了37.8%、38.9%和62.9%。這是因為本文提出的算法能均衡網(wǎng)絡(luò)負載同時避免網(wǎng)絡(luò)干擾，更加合理地為承載網(wǎng)絡(luò)流量的鏈路分配信道，避免了瓶頸鏈路帶來的網(wǎng)絡(luò)擁塞問題，獲得更高的網(wǎng)絡(luò)整體吞吐量。驗證了LBIA-POCA算法在MRMC-WMN中信道分配的優(yōu)越性。

4 結(jié)束語

針對WMN中存在的網(wǎng)絡(luò)容量和干擾問題，本文提出了一種部分重疊信道分配算法，對具有混合流量的WMN實現(xiàn)有效的干擾避免和負載均衡。仿真結(jié)果表明本文提出的LBIA-POCA算法有效地避免了網(wǎng)絡(luò)干擾，提高了網(wǎng)絡(luò)吞吐量并降低了平均端到端延遲和丟包率。本方案是針對單播通信的WMN而設(shè)計的，而多播通信可以更有效地節(jié)省信道資源，下一步工作將研究如何解決多播通信的信道分配問題。