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

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

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

0 引 言

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

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

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

1 系統模型

1.1 網絡模型

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

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

(1)

下面列出本文中的一些假設：

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

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

(3)集中式信道分配由網關節點集中計算，進而發送給整個網絡；

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

1.2 干擾模型

本文采用發送、接收端沖突避免協議干擾模[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(τ) 與信道間隔τ有關。建立雙徑地面傳播模型，通過發送節點的功率、天線增益等值推導得到同信道節點干擾范圍RI(τ)

(3)

進一步可推導得到信道間隔為τ時對應的節點干擾范圍值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) 為半徑的圓形區域，是節點ui的干擾范圍；D(vi,RI(0)) 為節點vi的干擾范圍。

(7)

1.3 鏈路重要因子

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

(8)

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

2 信道分配算法

本文提出的LBIA-POCA算法主要由兩個階段組成，第一階段為節點間通信接口分配，確定節點接口間的連接關系。第二階段是無干擾信道分配階段：根據網絡干擾情況，對鏈路進行迭代信道分配，并使用靜態鏈路調度來保證網絡連接；最后，利用啟發式算法優先為重要程度較高的鏈路分配無干擾時隙，對鏈路調度進行優化，以提高網絡性能。

2.1 結點間通信接口分配

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

2.2 無干擾信道分配

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

(9)

(10)

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

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

3 仿真與結果分析

3.1 仿真環境

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

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

表3 仿真參數

分別驗證網絡并發流數量和網絡大小對網絡吞吐量、端到端時延和丟包率的影響。為了減少誤差和隨機結果的影響，對每個方案運行10次，運行結果取均值來保證一致性和再現性。

3.2 并發流數量對性能的影響

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

圖1 不同并發流數量下的網絡吞吐量

圖2 不同并發流數量下的網絡平均端到端時延

圖3 不同并發流數量下的網絡平均丟包率

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

3.3 網格尺寸大小對性能的影響

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

圖4 不同網格大小下的網絡吞吐量

圖5 不同網格大小下的網絡平均端到端時延

圖6 不同網格大小下的網絡平均丟包率

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

由圖4～圖6可見，LBIA-POCA算法的各項網絡性能優于其它算法。當網絡規模為9×9時，LBIA-POCA算法的網絡吞吐量為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%。這是因為本文提出的算法能均衡網絡負載同時避免網絡干擾，更加合理地為承載網絡流量的鏈路分配信道，避免了瓶頸鏈路帶來的網絡擁塞問題，獲得更高的網絡整體吞吐量。驗證了LBIA-POCA算法在MRMC-WMN中信道分配的優越性。

4 結束語

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