徐伊恒,田 祎,楊 華

(商洛學院 經濟管理學院,陜西 商洛 726000)

0 引言

無線Mesh網(wǎng)絡(Wireless Mesh Networks, WMN)也稱為無線網(wǎng)狀網(wǎng),是一種新型無線網(wǎng)絡架構。它能夠動態(tài)地自組織、自配置,并且具有成本低、易維護、業(yè)務穩(wěn)定、擴展性好、網(wǎng)絡容量大等優(yōu)勢,可用于蜂窩網(wǎng)絡的回程傳輸、家庭網(wǎng)絡、企業(yè)網(wǎng)絡的接入,也可以用于校園網(wǎng)絡覆蓋范圍的擴大化[1-3]。

隨著無線網(wǎng)絡和移動互聯(lián)網(wǎng)業(yè)務的不斷發(fā)展,網(wǎng)絡規(guī)模在不斷地增大,用戶數(shù)量在不斷增加,用戶對帶寬的需求也在不斷上漲,網(wǎng)絡拓撲的復雜化和網(wǎng)絡流量的急劇增長,導致WMN中鏈路間的干擾急劇增加。如何有效降低鏈路間的干擾,提高網(wǎng)絡容量成為WMN被廣泛應用的關鍵問題之一。多射頻多信道(Multi-radio Multi-channel Wireless Mesh Networks,MRMC)技術可有效降低WMN中同信道間的干擾,提升網(wǎng)絡容量,但隨之帶來頻譜資源和鏈路沖突問題。因此,信道分配問題在MRMC WMNs中受到廣泛的關注。IEEE 802.11 2.4 GHz標準由于其廣泛的適用性而被MRMC WMNs采用。然而,IEEE 802.11 2.4 GHz標準中相鄰信道的頻譜部分重疊,正交信道只有3條,如何在一定限制條件下合理高效地對有限頻譜資源進行分配,在降低鏈路間干擾的同時保持網(wǎng)絡穩(wěn)定是MRMC WMNs面臨的重要挑戰(zhàn)。大多數(shù)現(xiàn)有研究將信道分配局限于非重疊信道,即正交信道(Orthogonal Channels,OCs), 并側重于通過結合路由、Qos等其他方面來緩解同信道干擾[4-10]。Yi等[11-12]引入載波偵聽多路訪問感知的干擾模型和共享鏈路模型容量模型,采用混合整數(shù)規(guī)劃來優(yōu)化信道分配過程,實現(xiàn)無干擾信道分配策略,但算法只實現(xiàn)了3～5個正交信道的無干擾分配。

為了提高頻譜資源的利用率,部分重疊信道(Partially Overlapping Channels, POCs)的概念被引入。Arunesh等[13-14]提出了干擾因子的概念來描述IEEEE 802.11 2.4 GHz標準中信道的重疊度,研究表明利用POCs能夠在一定程度上提高信道頻譜資源的復用。此后,在無線網(wǎng)絡中利用POCs進行信道分配受到研究者的關注。Mogaibel等[15]提出了一種聯(lián)合信道、接口分配和調度算法,該算法使用了所有信道且被描述為線性混合整數(shù)規(guī)劃問題。仿真結果表明,該算法在提升網(wǎng)絡容量和降低瓶頸鏈路利用率方面有顯著的性能改進。Zhao等[16]通過貪婪啟發(fā)式算法進行以最小化鄰信道干擾為目標的信道分配,但該方法以從0～1變化的公平性指數(shù)來衡量流量變化,沒有將流量對網(wǎng)絡性能的影響考慮在目標優(yōu)化函數(shù)內。Backhaus等[17]基于時隙模型以節(jié)點間最大流量為目標進行全局鏈路調度來提高網(wǎng)絡容量,但沒有考慮干擾對吞吐量的影響且缺少公平性約束。由于路由配置可以有效地減少鏈路間的干擾,它可以通過不使用流量來“激活”鏈路的一部分,從而消除了信道分配中要考慮的潛在干擾。因此,本文將路由和信道分配相結合,提出一種無干擾的部分重疊信道分配策略。雖然本研究和Mogaibel等[15]所提出的算法類似,但在Mogaibel等[15]的算法中,他們假設路由路徑是預先確定的。

1 問題描述和定義

1.1 網(wǎng)絡模型

本文中MRMC WMN定義為有向圖G=(L,V),其中L代表有向鏈路集合,V代表節(jié)點集合,在G中每個節(jié)點V都配備了基于IEEE 802.11技術構建的Nv塊網(wǎng)絡接口卡,每個網(wǎng)絡接口卡都工作在不同頻率的信道上。如果一條鏈路從節(jié)點u到節(jié)點v使用了信道c∈C, 將此鏈路定義為l=(u,v,c), 其中C代表信道集合。因此,在每個相鄰的節(jié)點u和v之間存在2|C|條可供通信的鏈路。

1.2 干擾模型

本文假設兩個相同信道c1和c2(c1=c2)之間的干擾距離為R,并且通信距離與干擾距離相同,因此R也稱為同信道干擾距離。但是對于部分重疊信道,根據(jù)其重疊程度的不同,它們之間的干擾范圍會隨著相隔距離的增大而減小,實驗證明它們之間存在著一定比率,本文中這個比率直接引用Wang等[18]研究中的值,如表1所示。將Irrr(c1,c2)定義為干擾范圍比,并將其歸一化為[0,1]范圍,用于描述在部分重疊信道c1和c2上的干擾比率。

表1 干擾范圍比

干擾模型引用Tian[11-12]中所定義的參考模型,定義d(u,v)為空間中兩個節(jié)點之間的歐氏距離,當節(jié)點u和v之間歐氏距離大于干擾距離R或信道c1和c2之間間隔大于5時,兩條鏈路之間被認定為無干擾。此外,干擾范圍內使用相同信道或使用兩個不同信道間隔距離小于5時,鏈路之間的干擾可以通過載波偵聽多址訪問(Carrier Sense Multiple Access,CSMA)協(xié)議避免。當鏈路l1=(u1,v1,c1)和l2=(u2,v2,c2)同時滿足式(1)和(2)時,文中定義鏈路l1對l2產生干擾,稱l1和l2是鏈路集合L中對干擾對。

d(u1,v2)≤Irrr(c1,c2)R

(1)

d(u1,u2)≤Irrr(c1,c2)R

(2)

在式(1)和(2)中,節(jié)點v2位于節(jié)點u1和u2的干擾范圍內,但節(jié)點u1和u2相互不在對方的方擾范圍內,因此當節(jié)點u1和u2同時分別向鄰居節(jié)點v1和v2發(fā)送幀時,它們將在節(jié)點v2發(fā)生碰撞,其中節(jié)點v1和v2可能是同一節(jié)點。在此模型中,假設干擾是不對稱的,即鏈路l1的傳輸對l2傳輸產生干擾,記為l1→l2?；谏鲜龇治?定義干擾對集合如式(3)所示,SILP可從給定的網(wǎng)絡拓撲結構中計算得到。

SILP={(l1,l2)|l1,l2∈L,l1→l2}

(3)

2 問題求解

為得到無干擾信道分配策略,上述問題可轉化為混合線性規(guī)劃問題進行求解, 為實現(xiàn)負載均衡,目標函數(shù)設定如式(4)所示,其中Umax為一個變量,表示鏈路的最大利用率,其取值范圍為0～1。

MinUmax

(4)

約束條件為,

(5)

Al1+Al2≤1,?(l1,l2)∈SILP

(6)

(7)

?v∈V,?c∈C

(8)

3 實驗評估

本文中的混合線性規(guī)劃問題使用IBM CPLEX Optimizer version 12.10進行求解。網(wǎng)絡模型設計為2 000×2 000 m2內具有30個節(jié)點的隨機網(wǎng)絡。每個網(wǎng)絡節(jié)點配置2塊IEEE 802.11 G網(wǎng)絡接口卡,通信距離為530 m,傳輸功率為20 dBm,傳輸速率為6 Mbps。IEEE 802.11 2.4 GHz的13個信道全部用來進行信道分配。在網(wǎng)絡中隨機產生20條CBR流,使用Scenargie version 2.1網(wǎng)絡模擬器進行仿真,并將仿真結果和Mogaibel等[15]結果進行對比分析。仿真時間設置為5 000 s,實驗結果取5次仿真模擬的平均值。

圖2展示了兩個策略在網(wǎng)絡總吞吐量性能比較,當網(wǎng)絡傳輸速率較低時,兩個策略都展現(xiàn)了良好的性能,這證明了負載平衡功能可以很好地提高網(wǎng)絡吞吐量。本文提出的策略提供了額外的容量空間來支持更大的網(wǎng)絡流量,因此信道的利用率較高。然而,Mogaibel等[15]提出的策略使用了最短路由路徑,仿真發(fā)現(xiàn)相當多的幀阻塞在源節(jié)點無法發(fā)送出去。因此,就網(wǎng)絡容量而言,Mogaibel等[15]提出的策略中吞吐量性能遠遠低于本文提出策略。

圖3展示了由于碰撞或干擾而導致的MAC層中的幀丟失的狀態(tài)。在Mogaibel等[15]提出的策略,幀丟失隨著通信量的增加而增加。當重傳次數(shù)超過限制時,會看到大量丟失的幀,其中大多數(shù)是由于隱藏終端的沖突問題造成的。相比之下,本文提出的策略中丟棄的幀數(shù)量非常少,在日志文件只觀察到只有少量幾個幀的丟失;盡管實際上幀之間存在多個干擾或同時退避失效的情況,但大多數(shù)情況都是通過CSMA協(xié)議重傳恢復的。因此,本文提出的策略幾乎沒有因干擾而導致的幀丟失。這意味著本文提出的干擾模型性能良好,減少了節(jié)點間的干擾。

圖3 幀丟失量比較

4 結語

本文討論了多射頻多信道WMN信道分配問題,利用IEEE 802.11 2.4 GHz頻段信道中定義的所有信道,以提高信道利用率和網(wǎng)絡性能目標,設計了一種新的聯(lián)合信道分配和路由策略,并通過混合整數(shù)線性規(guī)劃算法進行目標求解,最終得到最優(yōu)信道分配方案。實驗表明了本方案能夠有效提高射頻信號的空間重用性,并實現(xiàn)了無干擾傳輸,網(wǎng)絡吞吐量顯著提高。研究的下一步目標是對目標函數(shù)約束進行進一步細化,并在實際應用場景中進行實驗驗證。