葉 方 孫 雪 李一兵

(哈爾濱工程大學(xué)信息與通信工程學(xué)院 哈爾濱 150001)

(先進船舶通信與信息技術(shù)工業(yè)和信息化部重點實驗室 哈爾濱 150001)

1 引言

無線Mesh網(wǎng)絡(luò)(Wireless Mesh Networks, WMN)因其多跳、自組織、非視距傳輸?shù)葍?yōu)點，以及在覆蓋范圍、成本控制、組網(wǎng)速度等方面的優(yōu)良表現(xiàn)，廣泛應(yīng)用于災(zāi)后網(wǎng)絡(luò)重建等應(yīng)急通信場景[1,2]。然而隨著網(wǎng)絡(luò)規(guī)模的增大，網(wǎng)絡(luò)拓?fù)鋸?fù)雜化，WMN中信道干擾的情況也會越來越嚴(yán)重，多射頻多信道(Multi-Radio Multi-Channel, MRMC)技術(shù)是一種能夠顯著降低共信道干擾，提高網(wǎng)絡(luò)性能的方案[3]，但也隨之帶來了頻譜利用和鏈路沖突等問題。因傳輸范圍遠而被廣泛使用的IEEE 802.11b/g標(biāo)準(zhǔn)中相鄰信道的頻譜部分重疊，正交信道只有3條[4]，因此如何在一定限制條件下合理高效地對有限頻譜資源進行分配，在降低干擾的同時保持網(wǎng)絡(luò)穩(wěn)定是應(yīng)急通信網(wǎng)絡(luò)面臨的重要挑戰(zhàn)。

針對WMN信道分配中頻譜資源有限的問題，Mishra等人[5]提出了干擾因子的概念來描述IEEE 802.11b/g標(biāo)準(zhǔn)中信道的重疊程度，研究表明利用部分重疊信道 (Partially Overlapped Channels, POCs)能夠在一定程度上提高信道頻譜資源復(fù)用。Bokhari等人[6]提出了一種利用部分重疊信道實現(xiàn)干擾感知的信道分配方法，證明了所提算法能夠顯著降低由MRMC引起的網(wǎng)絡(luò)干擾，相比于僅使用正交信道網(wǎng)絡(luò)性能提高了37.3%。文獻[7]在保證網(wǎng)絡(luò)連通性的同時使干擾最小化，證明了適當(dāng)使用重疊信道的信道分配可以提高網(wǎng)絡(luò)吞吐量，尤其是在密集拓?fù)渚W(wǎng)絡(luò)中，然而該方法以犧牲時間復(fù)雜度為代價尋求性能的提升，需要設(shè)計更高效的算法降低復(fù)雜度。

針對節(jié)點增加時引起的網(wǎng)絡(luò)復(fù)雜化問題，許多研究將信道分配過程轉(zhuǎn)化為帶有約束條件的線性規(guī)劃模型，利用群智能算法求最優(yōu)解[8]。文獻[9]采用禁忌搜索算法進行信道分配，避免在搜索過程中出現(xiàn)已經(jīng)訪問過的解決方案，能夠一定程度上提高局部搜索能力，但是禁忌搜索的結(jié)果完全依賴于初始解和鄰域的映射關(guān)系，全局搜索能力弱。文獻[10]針對應(yīng)急通信需求提出了基于權(quán)重的粒子群優(yōu)化算法，構(gòu)建有序鏈路矩陣和鏈路鄰接矩陣解決重要鏈路的網(wǎng)絡(luò)擁塞問題，精確地將不同鏈路在網(wǎng)絡(luò)中的重要性進行區(qū)別和記錄，但是該方法沒有考慮MRMC中的接口約束條件和頻譜資源問題，同時粒子群算法收斂速度慢且易陷入局部最優(yōu)。文獻[11]引入“載波偵聽多路訪問(Carrier Sense Multiple Access,CSMA)感知”的共享鏈路容量模型解決鏈路容量計算和流量感知的問題，采用混合整數(shù)規(guī)劃來優(yōu)化信道分配過程[11]。但是該算法只實現(xiàn)了3～5個正交信道的無沖突分配，且當(dāng)節(jié)點增多時混合整數(shù)規(guī)劃求解困難。文獻[12]通過貪婪啟發(fā)式算法進行以最小化鄰信道干擾為目標(biāo)的信道分配，但該方法以從0～1變化的公平性指數(shù)來衡量流量變化，沒有將流量對網(wǎng)絡(luò)性能的影響考慮在目標(biāo)優(yōu)化函數(shù)內(nèi)。文獻[13]基于時隙模型以節(jié)點間最大流量為目標(biāo)進行全局鏈路調(diào)度來提高網(wǎng)絡(luò)容量，但沒有考慮干擾對吞吐量的影響且缺少公平性約束。

以上WMN信道分配方案大多存在著頻譜資源利用不充分，沒有考慮實際工作中可能存在的流量匯聚情況和接口約束條件的問題。針對上述問題，本文綜合考慮鄰接鏈路數(shù)量和信道干擾建立以最小化鏈路加權(quán)干擾為目標(biāo)的優(yōu)化函數(shù)，將靜態(tài)信道分配過程轉(zhuǎn)化為帶有約束條件的線性規(guī)劃模型，使算法在節(jié)點數(shù)目增加時仍能保證網(wǎng)絡(luò)的穩(wěn)定性和連通性。針對節(jié)點增加時網(wǎng)絡(luò)拓?fù)鋸?fù)雜化導(dǎo)致信道分配效率低的問題，考慮蝙蝠算法在資源調(diào)度領(lǐng)域展現(xiàn)的優(yōu)秀搜索能力[14]，提出改進離散蝙蝠算法(Improved Discrete Bat Algorithm, IDBA)求解最優(yōu)信道分配方案，在標(biāo)準(zhǔn)蝙蝠算法的基礎(chǔ)上，將種群位置和速度的更新離散化，參考樽海鞘群算法中的鏈?zhǔn)叫袨樘岣呔植克阉髂芰?，引入動態(tài)慣性權(quán)重有效平衡算法的全局搜索和局部開發(fā)能力從而得到更快的收斂速度，大幅度減少全局鏈路干擾，提高網(wǎng)絡(luò)吞吐量。

2 系統(tǒng)模型及問題描述

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

在如圖1(a)所示的應(yīng)急場景中，各Mesh路由器自主構(gòu)建多跳自組織的網(wǎng)絡(luò)系統(tǒng)拓?fù)?，為?yīng)急現(xiàn)場的終端設(shè)備提供通信服務(wù)并完成面向指揮中心的信息回傳等任務(wù)。

采用如圖1(b)所示的WMN骨干型結(jié)構(gòu)，在IEEE 802.11b標(biāo)準(zhǔn)基礎(chǔ)上用一個無向圖G(V,E)來表示W(wǎng)MN。其中，V是網(wǎng)絡(luò)節(jié)點的集合，代表Mesh路由器；E是網(wǎng)絡(luò)節(jié)點形成的鏈路集合。Mesh路由器配備K(K ≥2)個無線接口，可用部分重疊信道集為C，其中信道個數(shù)為cn。C(v)表 示節(jié)點v分配的信道集合，集合中元素的個數(shù)為|C(v)|。

圖1 WMN網(wǎng)絡(luò)拓?fù)?/p>

考慮所有Mesh路由器的無線接口發(fā)射功率和傳輸范圍相同；信道分配與路由獨立跨層優(yōu)化，在信道分配之前已經(jīng)設(shè)計好路由路徑。設(shè)傳輸范圍為Rt， 即一跳的傳輸距離。對于網(wǎng)絡(luò)中的節(jié)點i,j∈V，定義它們之間的距離為dij，g(eij)表示節(jié)點間的鏈路存在情況，當(dāng)dij ≤Rt時 ，節(jié)點i和 節(jié)點j之間的鏈路eij存在；當(dāng)dij>Rt時，兩節(jié)點之間不存在鏈路，即

網(wǎng)絡(luò)中的每個節(jié)點在某個時刻進行數(shù)據(jù)通信時，同一時刻1個射頻接口或者只被分配了1個信道，或者沒有被分配信道，因此節(jié)點上被分配的信道數(shù)不可能超過節(jié)點自身配備的無線接口數(shù)[15]，即滿足式(4)約束條件

2.2 干擾模型

采用基于雙徑傳播的協(xié)議干擾模型[16]進行干擾建模，由于正交信道(Orthogonal Channels, OCs)只受同信道干擾影響，節(jié)點i和 節(jié)點j之間的干擾范圍RI(0)為

其中，Pt是 節(jié)點的發(fā)射功率；Gr是接收節(jié)點的天線增益； CSth是載波感知門限；k是路徑損耗因子；Gt是發(fā)射節(jié)點的天線增益；hr是接收天線的高度；ht是發(fā)射天線的高度。

而POCs的干擾范圍與信道重疊度有關(guān)，od(x,y)表示兩信道cx和cy間隔為τ=|x ?y|時的信道重疊度，具體如表1所示[17]。

表1 信道重疊度

使用POCs的干擾范圍為

為了更清楚地反映網(wǎng)絡(luò)整體的干擾情況，本文用沖突圖Gc(Vc,Ec)來描述鏈路間干擾[18]。定義圖2(b)中的沖突圖頂點為圖2(a)中拓?fù)鋱D兩頂點之間形成的鏈路，即Vc={eij|eij ∈E}。 若圖2(a)中鏈路lab處于鏈路lac的 干擾范圍內(nèi)，則圖2(b)中的lab和lac間有一條連接線，表示一條干擾鏈路。

圖2 拓?fù)鋱D與沖突圖對應(yīng)關(guān)系

a為所求鏈路eij的編號，b為與a之間存在干擾的鏈路的編號，鏈路eij受到的總干擾為

2.3 問題描述

在實際網(wǎng)絡(luò)環(huán)境中，相鄰鏈路越多的鏈路表現(xiàn)為流量越多，易形成瓶頸鏈路，所以在信道分配時需要對相鄰鏈路多的鏈路著重考慮，以提高應(yīng)急通信網(wǎng)絡(luò)在流量匯聚情況下的穩(wěn)定性。定義鄰接鏈路權(quán)重ωij為所求鏈路eij的相鄰鏈路數(shù)量在全部鏈路中的占比，Lij為所求鏈路eij的相鄰鏈路數(shù)量總和，L為網(wǎng)絡(luò)中的全部鏈路數(shù)，即

綜合考慮網(wǎng)絡(luò)的鄰接鏈路權(quán)重和鏈路干擾，網(wǎng)絡(luò)總加權(quán)干擾為

3 基于改進離散蝙蝠算法的部分重疊信道分配

蝙蝠算法通過模擬自然界中蝙蝠利用超聲波感知獵物并捕獲的能力進行最優(yōu)化目標(biāo)求解[19]。標(biāo)準(zhǔn)蝙蝠算法[20]求解的都是連續(xù)型問題，為了使其能夠處理WMN信道分配問題，需將其進行離散化并做相應(yīng)改進。

3.1 改進的蝙蝠運動方式

表2 蝙蝠位置編碼示例

3.2 改進的局部搜索方式

3.3 信道分配算法

在建立網(wǎng)絡(luò)模型和干擾模型的基礎(chǔ)上，算法的適應(yīng)度函數(shù)為網(wǎng)絡(luò)的總鏈路加權(quán)干擾，即

4 實驗結(jié)果及分析

4.1 仿真環(huán)境與參數(shù)設(shè)置

在Matlab環(huán)境下對本文所提基于IDBA的WMN部分重疊信道分配方法進行仿真，并與文獻[10]中基于離散粒子群優(yōu)化 (Discrete Particle Swarm Optimization, DPSO)算法的信道分配方法、文獻[22]中基于布谷鳥搜索算法 (Cuckoo Search Algorithm, CSA)的信道分配方法和文獻[23]中基于離散鴿群優(yōu)化 (Binary Pigeon-Inspired Optimization, BPIO)算法的信道分配方法進行對比分析。所用計算機的配置參數(shù)為：AMD Ryzen 9 3900X 12-Core Processor；3.8 GHz主頻；32 GB RAM；Windows10操作系統(tǒng)。具體參數(shù)設(shè)置如表4所示。

表4 仿真參數(shù)設(shè)置表

4.2 模型建立

為了使算法更加具有一般性同時避免均勻網(wǎng)格類拓?fù)洚a(chǎn)生不必要的通信鏈路開銷，仿真實驗中在一個1000 m×1000 m的2維空間內(nèi)采用Salama模型隨機部署25個Mesh節(jié)點，部署后各節(jié)點固定不動。同時實驗采用K-means聚類算法使網(wǎng)絡(luò)節(jié)點均勻分布避免隨機部署時節(jié)點過于集中或分散，從而覆蓋更大的應(yīng)急通信范圍。生成如圖3所示的網(wǎng)絡(luò)拓?fù)鋱D，該圖反映了當(dāng)兩節(jié)點間距離小于傳輸距離時，兩節(jié)點間存在鏈路，即兩個節(jié)點之間存在一條邊。

圖3 網(wǎng)絡(luò)拓?fù)鋱D

設(shè)置相同網(wǎng)絡(luò)區(qū)域內(nèi)的網(wǎng)絡(luò)節(jié)點數(shù)分別為20和40，根據(jù)建立的干擾模型得到了圖4(a)稀疏節(jié)點和圖4(b)密集節(jié)點下的網(wǎng)絡(luò)沖突圖。圖4反映了鏈路間的干擾情況，標(biāo)號代表鏈路編號，可見當(dāng)節(jié)點數(shù)目增多時鏈路間的干擾十分嚴(yán)重，因此進行合理的信道分配以減少網(wǎng)絡(luò)干擾是十分必要的。

圖4 網(wǎng)絡(luò)沖突圖

4.3 算法復(fù)雜度分析與對比

表3 信道分配過程

圖5描述了在不同節(jié)點數(shù)量下各算法達到收斂時的平均迭代次數(shù)變化情況，設(shè)置相同網(wǎng)絡(luò)區(qū)域內(nèi)節(jié)點數(shù)目分別為20, 25, 30, 35, 40, 45, 50，其他網(wǎng)絡(luò)環(huán)境相同。可見DPSO算法雖然時間復(fù)雜度低但是其收斂時間緩慢，甚至在迭代次數(shù)即將達到100時才開始收斂，搜索效率低；CSA和BPIO算法不穩(wěn)定，在搜索過程中易陷入局部最優(yōu)，收斂時間較長；而IDBA在不同網(wǎng)絡(luò)規(guī)模下，其收斂時的平均迭代次數(shù)均為最低，因此具有較高的搜索效率。

圖5 不同節(jié)點數(shù)下收斂時間對比

表5通過描述各算法在不同網(wǎng)絡(luò)規(guī)模下仿真的運行時間來進一步反映算法的總計算時間，仿真環(huán)境相同。可見DPSO耗時最少，這是通過犧牲算法的搜索性能換來的；BPIO時間復(fù)雜度最高，因此算法總計算時間最長，尤其是在大規(guī)模網(wǎng)絡(luò)下性能不佳。IDBA和CSA信道分配方法的數(shù)學(xué)估計時間復(fù)雜度相同，但是CSA通過隨機游走進行局部搜索，容易陷入局部最優(yōu)，因此仿真消耗的總時間較長。綜上所述，IDBA能夠在不同網(wǎng)絡(luò)規(guī)模下保持較高搜索效率，同時具有較低的時間復(fù)雜度。

表5 不同算法總耗時對比(s)

4.4 算法性能分析與對比

圖6通過描述各算法隨著迭代次數(shù)的增加適應(yīng)度值(鏈路加權(quán)干擾值)的收斂情況來反映算法的優(yōu)化效率和優(yōu)化程度，所有算法均采用相同的最大迭代數(shù)100次，種群數(shù)量50和網(wǎng)絡(luò)節(jié)點數(shù)25。由圖6分析可知，隨著迭代次數(shù)的增加，各算法鏈路干擾逐漸降低直至收斂。在收斂速度上進一步證明了IDBA在迭代10次左右時其適應(yīng)度值就可以收斂到最優(yōu)；DPSO算法在信道分配中搜索能力表現(xiàn)不佳，收斂速度十分緩慢；CSA和BPIO算法搜索速度相對較快但是易陷入局部最優(yōu)。在搜索能力上，IDBA表現(xiàn)最好，收斂時的網(wǎng)絡(luò)干擾最低，因為蝙蝠根據(jù)響度和頻率的變化逐漸向最優(yōu)目標(biāo)靠近保證了其優(yōu)秀的全局搜索能力，同時引入了樽海鞘群的鏈?zhǔn)叫袨樘岣咂渚植块_發(fā)能力，動態(tài)慣性系數(shù)有效平衡了全局搜索和局部開發(fā)之間的關(guān)系。

圖6 不同算法適應(yīng)度收斂曲線對比

圖7描述了隨著網(wǎng)絡(luò)節(jié)點數(shù)目的增加網(wǎng)絡(luò)干擾的變化情況，設(shè)置網(wǎng)絡(luò)環(huán)境中節(jié)點數(shù)目分別為20,25, 30, 35, 40, 45, 50，其他網(wǎng)絡(luò)環(huán)境相同。隨著網(wǎng)絡(luò)節(jié)點數(shù)目的增加，在迭代相同次數(shù)后得到的鏈路加權(quán)干擾值增加，DPSO算法的鏈路干擾十分嚴(yán)重，尤其在節(jié)點密集的情況下性能不佳；CSA,BPIO和IDBA在節(jié)點數(shù)小于30的情況下性能相差不大，但在節(jié)點密集時IDBA算法鏈路干擾值最小且隨著網(wǎng)絡(luò)規(guī)模的增大鏈路干擾值增長幅度最小。

圖7 不同節(jié)點數(shù)下全局干擾值對比

圖8描述了隨著網(wǎng)絡(luò)節(jié)點數(shù)目的增加網(wǎng)絡(luò)吞吐量的變化情況，設(shè)置網(wǎng)絡(luò)環(huán)境中節(jié)點數(shù)目分別為20, 25, 30, 35, 40, 45, 50，其他網(wǎng)絡(luò)環(huán)境相同。各算法迭代相同次數(shù)后根據(jù)鏈路分配的最優(yōu)信道計算網(wǎng)絡(luò)吞吐量，在節(jié)點數(shù)目不超過35時，隨著節(jié)點數(shù)目的增加，各算法的網(wǎng)絡(luò)吞吐量都增加，IDBA算法的性能最好，吞吐量最大，優(yōu)于其他3種算法；當(dāng)節(jié)點數(shù)目大于35時，DPSO算法由于鏈路干擾急劇增加而使網(wǎng)絡(luò)變得不穩(wěn)定，網(wǎng)絡(luò)吞吐量下降并產(chǎn)生波動；在網(wǎng)絡(luò)規(guī)模達到40個節(jié)點后IDBA和CSA吞吐量有明顯下降；IDBA算法的吞吐量在小幅度增長后趨于一個穩(wěn)定值，且其吞吐量總是高于其他3種算法，由于此時網(wǎng)絡(luò)可兼容量達到峰值，故網(wǎng)絡(luò)吞吐量不再有顯著的提升，說明IDBA在節(jié)點密集場景下仍能較好地保持網(wǎng)絡(luò)穩(wěn)定性。

圖8 不同節(jié)點數(shù)下網(wǎng)絡(luò)吞吐量對比

5 結(jié)束語

本文討論了應(yīng)急通信背景下WMN的集中式靜態(tài)信道分配問題，利用部分重疊信道提高頻譜利用率和網(wǎng)絡(luò)性能。針對流量匯聚場景下存在的瓶頸鏈路問題和網(wǎng)絡(luò)干擾情況，建立以最小化鏈路加權(quán)干擾為目標(biāo)的信道分配優(yōu)化模型，采用改進的離散蝙蝠算法進行目標(biāo)求解，將蝙蝠的運動方式離散化并引入樽海鞘群的鏈?zhǔn)叫袨樘岣呔植克阉髂芰?，通過迭代得到最優(yōu)信道分配方案。實驗表明了本方案能夠有效降低網(wǎng)絡(luò)干擾，提高網(wǎng)絡(luò)吞吐量，能夠應(yīng)用在流量密集的應(yīng)急通信場景下為客戶端提供穩(wěn)定的通信服務(wù)。