徐伊恒,田 祎,楊 華

(商洛學(xué)院 經(jīng)濟(jì)管理學(xué)院,陜西 商洛 726000)

0 引言

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

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

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

1 問題描述和定義

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

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

1.2 干擾模型

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

表1 干擾范圍比

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

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

(1)

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

(2)

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

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

(3)

2 問題求解

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

MinUmax

(4)

約束條件為,

(5)

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

(6)

(7)

?v∈V,?c∈C

(8)

3 實(shí)驗(yàn)評估

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

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

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

圖3 幀丟失量比較

4 結(jié)語

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