基于改進離散蝙蝠算法的無線Mesh網絡部分重疊信道分配

葉 方 孫 雪 李一兵

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

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

1 引言

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

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

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

以上WMN信道分配方案大多存在著頻譜資源利用不充分，沒有考慮實際工作中可能存在的流量匯聚情況和接口約束條件的問題。針對上述問題，本文綜合考慮鄰接鏈路數量和信道干擾建立以最小化鏈路加權干擾為目標的優化函數，將靜態信道分配過程轉化為帶有約束條件的線性規劃模型，使算法在節點數目增加時仍能保證網絡的穩定性和連通性。針對節點增加時網絡拓撲復雜化導致信道分配效率低的問題，考慮蝙蝠算法在資源調度領域展現的優秀搜索能力[14]，提出改進離散蝙蝠算法(Improved Discrete Bat Algorithm, IDBA)求解最優信道分配方案，在標準蝙蝠算法的基礎上，將種群位置和速度的更新離散化，參考樽海鞘群算法中的鏈式行為提高局部搜索能力，引入動態慣性權重有效平衡算法的全局搜索和局部開發能力從而得到更快的收斂速度，大幅度減少全局鏈路干擾，提高網絡吞吐量。

2 系統模型及問題描述

2.1 網絡模型

在如圖1(a)所示的應急場景中，各Mesh路由器自主構建多跳自組織的網絡系統拓撲，為應急現場的終端設備提供通信服務并完成面向指揮中心的信息回傳等任務。

采用如圖1(b)所示的WMN骨干型結構，在IEEE 802.11b標準基礎上用一個無向圖G(V,E)來表示WMN。其中，V是網絡節點的集合，代表Mesh路由器；E是網絡節點形成的鏈路集合。Mesh路由器配備K(K ≥2)個無線接口，可用部分重疊信道集為C，其中信道個數為cn。C(v)表 示節點v分配的信道集合，集合中元素的個數為|C(v)|。

圖1 WMN網絡拓撲

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

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

2.2 干擾模型

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

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

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

表1 信道重疊度

使用POCs的干擾范圍為

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

圖2 拓撲圖與沖突圖對應關系

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

2.3 問題描述

在實際網絡環境中，相鄰鏈路越多的鏈路表現為流量越多，易形成瓶頸鏈路，所以在信道分配時需要對相鄰鏈路多的鏈路著重考慮，以提高應急通信網絡在流量匯聚情況下的穩定性。定義鄰接鏈路權重ωij為所求鏈路eij的相鄰鏈路數量在全部鏈路中的占比，Lij為所求鏈路eij的相鄰鏈路數量總和，L為網絡中的全部鏈路數，即

綜合考慮網絡的鄰接鏈路權重和鏈路干擾，網絡總加權干擾為

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

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

3.1 改進的蝙蝠運動方式

表2 蝙蝠位置編碼示例

3.2 改進的局部搜索方式

3.3 信道分配算法

在建立網絡模型和干擾模型的基礎上，算法的適應度函數為網絡的總鏈路加權干擾，即

4 實驗結果及分析

4.1 仿真環境與參數設置

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

表4 仿真參數設置表

4.2 模型建立

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

圖3 網絡拓撲圖

設置相同網絡區域內的網絡節點數分別為20和40，根據建立的干擾模型得到了圖4(a)稀疏節點和圖4(b)密集節點下的網絡沖突圖。圖4反映了鏈路間的干擾情況，標號代表鏈路編號，可見當節點數目增多時鏈路間的干擾十分嚴重，因此進行合理的信道分配以減少網絡干擾是十分必要的。

圖4 網絡沖突圖

4.3 算法復雜度分析與對比

表3 信道分配過程

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

圖5 不同節點數下收斂時間對比

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

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

4.4 算法性能分析與對比

圖6通過描述各算法隨著迭代次數的增加適應度值(鏈路加權干擾值)的收斂情況來反映算法的優化效率和優化程度，所有算法均采用相同的最大迭代數100次，種群數量50和網絡節點數25。由圖6分析可知，隨著迭代次數的增加，各算法鏈路干擾逐漸降低直至收斂。在收斂速度上進一步證明了IDBA在迭代10次左右時其適應度值就可以收斂到最優；DPSO算法在信道分配中搜索能力表現不佳，收斂速度十分緩慢；CSA和BPIO算法搜索速度相對較快但是易陷入局部最優。在搜索能力上，IDBA表現最好，收斂時的網絡干擾最低，因為蝙蝠根據響度和頻率的變化逐漸向最優目標靠近保證了其優秀的全局搜索能力，同時引入了樽海鞘群的鏈式行為提高其局部開發能力，動態慣性系數有效平衡了全局搜索和局部開發之間的關系。

圖6 不同算法適應度收斂曲線對比

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

圖7 不同節點數下全局干擾值對比

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

圖8 不同節點數下網絡吞吐量對比

5 結束語

本文討論了應急通信背景下WMN的集中式靜態信道分配問題，利用部分重疊信道提高頻譜利用率和網絡性能。針對流量匯聚場景下存在的瓶頸鏈路問題和網絡干擾情況，建立以最小化鏈路加權干擾為目標的信道分配優化模型，采用改進的離散蝙蝠算法進行目標求解，將蝙蝠的運動方式離散化并引入樽海鞘群的鏈式行為提高局部搜索能力，通過迭代得到最優信道分配方案。實驗表明了本方案能夠有效降低網絡干擾，提高網絡吞吐量，能夠應用在流量密集的應急通信場景下為客戶端提供穩定的通信服務。