無線Mesh網絡中基于離散粒子群優化的信道分配算法

摘 要： 無線Mesh網絡中配置多接口Mesh路由器并使用多信道可有效增加網絡容量并降低干擾。信道分配問題已被證明是一個NP難題。信道分配的目的是將可用信道分配到通信鏈路以實現網絡干擾最小的目標。針對多接口多信道無線Mesh網絡中的信道分配，提出了基于粒子群優化（PSO）算法。在實現過程中，通過增加交叉操作將其改進為離散粒子群優化（DPSO）用以處理信道分配這一離散問題。同時，引入了信道合并過程用以消除違背接口約束情況。通過仿真試驗并與Tabu?Based算法對比，該算法能有效降低網絡干擾并提升網絡性能。

主題詞： 無線Mesh網絡； 多接口多信道； 信道分配； 離散粒子群優化算法

中圖分類號： TN911?34； TP393 文獻標識碼： A 文章編號： 1004?373X（2013）08?0031?04

0 引 言

無線Mesh網絡（Wireless Mesh Networks，WMN）作為下一代寬帶接入的關鍵技術，由于具備動態自組織、自配置的優勢，網絡節點可以自動建立和維護，具備低投入、易維護、安全性強，覆蓋范圍廣而引起業界和學術界極大的研究興趣。WMN中一個重要的設計目標是使容量最大化，但無線干擾嚴重限制了多跳無線網絡中的網絡容量。采用多接口多信道能改進網絡容量，如何給接口或鏈路分配信道依然是一個復雜的問題，許多文獻都對信道分配問題進行了探討。

粒子群優化（Particle Swarm Optimization，PSO）算法是1995年由J.Kennedy博士和R.Eberhart博士基于對鳥群、魚群捕食行為的模擬而提出的群智能優化算法。信道分配問題是一個離散優化問題，雖然傳統的PSO算法并不適合求解離散問題，但通過將其位置和速度更新公式進行改進后，其求解離散優化問題的效果也比較明顯。文獻[1]提出了基于節點組織的拓撲保護信道分配算法，并采用離散離子群優化算法針對節點進行信道分配。但針對節點的信道分配有可能造成網絡隔離，因為相鄰的節點有可能出現沒有共同信道的情況。為此，本文提出了基于離散粒子群優化算法的信道分配方案，主要是將信道分配給網絡中的鏈路，目標是使網絡干擾最小化。主要實現了以下功能：

（1）建立了基于網絡干擾最小的信道分配模型；

（2）提出了基于離散粒子群算法的信道分配方案；

（3）對基于沖突圖信道分配可能違背接口約束的問題進行信道合并處理。最后，通過仿真實驗對所提算法進行分析驗證，結果表明該算法能有效降低網絡干擾并提高吞吐量。

1 離散粒子群優化算法

為了解決實際工程中的離散問題，Kennedy等人于1997年提出了離散二進制離子群算法[1]，采用二進制方式對粒子位置進行編碼，通過采用Sigmoid函數將速度約束[0，1]區間，并以此確定取1的概率。隨后，Hu等對文獻[2]中的方法進行了改進，用于解決置換排列問題，其中：粒子用置換排列來表示，而速度則根據兩個粒子的相似度來定義，決定粒子位置變化的概率，同時引入變異操作防止最優粒子陷入局部極小[1]。文獻[1]在PSO算法的基礎上提出了求解離散變量優化問題的DPSO算法，定義了粒子的離散位置來表示解空間，在此基礎上給出離散位置之間的差運算、離散速度之間和運算、常數與離散速度間的乘運算以及離散位置與離散速度之間的和運算，由此可得DPSO算法的基本公式為：

[vi（t+1）=c1?vi（t）c2?（pi（t）Θxi（t）⊕c3?（pgΘxi（t））] （1）

[xi（t+1）=xi（t）⊕vi（t+1）] （2）

式中：xi為第i個粒子的離散位置；vi為第i個粒子的離散速度；pi為第i個粒子的個體極值；pg為種群的全局極值。c1，c2，c3，為相應的權值，取值為[0，1]之間的常數；[“·”，“⊕”，“Θ”“]分別表示DPSO中的乘法、加法和減法。

2 網絡模型及問題描述

下面主要對網絡模型及信道分配問題進行建模。

2.1 網絡模型

網絡模型采用無向圖[G=（V，E）]表示。其中，V表示Mesh路由器（節點）；E表示節點間的邊（通信鏈路），當節點i與節點j處于各自的通信范圍且有節點配置了相同的信道，則構成一條通信鏈路。網絡中可用信道數目是有限的，在此用K表示。

2.2 干擾模型

由于無線媒介的廣播特性，處于通信范圍內的兩個節點間的通信可能干擾附近屬于其干擾范圍內的其他節點。兩條相互干擾的鏈路使用相同信道不能同時傳輸。目前，對干擾的描述主要有物理模型和協議模型。

本文采用協議模型進行描述，即根據節點間的距離判斷其組成的鏈路之間是否存在干擾，相互干擾用1表示，否則為0。在第4節中，將采用沖突百分比對干擾進行量化描述。

對于給定的干擾模型，假設相互干擾的鏈路同時使用相同信道，可用沖突圖表示。為了定義沖突圖，首先要定義其頂點集[Vc]與網絡中的通信鏈路相對應，即：

[Vc={lij（i，j） isacommunicationlink}]

沖突圖Gc（Vc，Ec）可定義為頂點集Vc，沖突邊集Ec表示鏈路（lij，lab）之間使用同一信道時相互干擾。根據上面的定義，沖突圖可用于表示所有干擾模型，信道分配不改變其沖突圖。圖1表示通信圖和干擾圖之間的對應關系。

2.3 信道分配問題

多接口無線Mesh網絡中的信道分配問題可描述為：對多接口路由器組成的Mesh網絡，通過給通信鏈路分配特定的信道使得使干擾最小且保持網絡連接性，還要考慮給每個節點分配的不同信道數目不能超過其接口數目。基于上述分析，信道分配問題就可以描述為：對配置了N個節點的WMN，信道分配問題即是求解函數[f：Vc→K]使得網絡總的干擾[I（f）]最小且滿足如下的接口約束。

接口約束：

[?i∈N，{kf（e）=kforsomee∈E（i）}≤Ri]

網絡干擾[I（f）]：

[I（f）={u，v}∈Ecf（u）=f（v）] （3）

下面采用離散粒子群優化算法對信道分配問題進行求解。

3 基于粒子群優化的信道分配算法

針對多接口信道分配問題，文獻[3]已證明了多接口信道分配問題是NP?hard，要想完全消除網絡中鏈路之間的干擾是幾乎不可能的，只能盡力減小干擾。顯然，采用窮舉搜索可解決這一問題，但在合理的時間內很難找到最優解。針對信道分配問題，已有很多解決辦法。本文采用DPSO算法對信道分配問題進行求解。

3.1 粒子的編碼

無線Mesh網絡中節點數目為N，可用信道數目為K，算法中的粒子代表一個可行的信道分配方案，即為沖突圖中的每個頂點與可用信道間的對應關系。第i個粒子在時刻t的位置可表示為：[Xti=（xti1，xti2，…，xtim）]，其中，[xtik]記作通信圖中邊k在t時刻分配的信道。

3.2 適應度函數

粒子將根據當前和全局最優位置改變當前位置，所以需要設計一個適應度函數來度量粒子位置。信道分配的目標是實現網絡干擾最小，因此采用網絡干擾數目[I（f）]對信道分配的性能進行評價。

[I（f）=e∈VcIN（e）] （4）

式中[IN（e）]表示鏈路e的受到的干擾數量。

3.3 約束的處理

針對沖突圖頂點（即通信圖中鏈路）的信道分配算法，在滿足網絡干擾最小約束的前提下，可能違背每個節點分配的信道數目不超過其接口數目的約束。因此，在粒子群優化迭代過程中，增加了信道合并操作，確保每個節點所分配的信道數目不超過其接口數目。

3.4 信道分配過程

在引入約束處理的同時，對DPSO算法的更新迭代過程進行了改進，引入了隨機擾動操作，改進了DPSO算法易陷入局部最優的不足，從而改進了算法的全局搜索能力。改進后的位置更新公式如下：

[xt+1i=c3⊕F（c2⊕F（c1⊕F（xti，pi），pg），random（K，Edgenum））] （5）

式中，c1，c2，c3為[0，1]間的常數，函數[c⊕F（x1，x2）]為本算法定義的特殊運算形式，即當系統隨機產生數小于等于c時切換為x2，大于時保持x1；pi代表個體最優解，pg全局最優解，random（K，EdgeNum）粒子中的某一條邊的隨機擾動。信道分配的偽代碼見表1。

4 仿真實驗與分析

為了測試所提出算法的性能，利用Matlab軟件實現所提算法，并與文獻[4]中的Tabu?based算法進行對比。用沖突百分比評價算法性能，其定義為網絡干擾數量與總鏈路數量之間的比值。

首先，通過改變算法相關參數研究參數對算法結果的影響。其次，模擬兩種場景進行實驗：

（1）可用信道數目固定，每個節點接口數目變化時干擾的變化；

（2）接口數目固定，可用信道數目變化。算法主要參數如表2所示。

4.1 參數對算法的影響

圖2顯示了變異因子取值不同時對算法性能的影響。在此實驗中，每個節點的接口數目設置為3，可用信道數目為12個。當c3=0.3時，由于最終解的變異概率較小，初期解收斂較快，但容易陷入局部最優解中，致使后期解的效果不是很明顯；而當c3=0.8時，由于對尋找出來的解變異的概率比較大，在初期收斂較慢，但在迭代后期解的質量較高。

4.2 接口和信道數目變化對干擾的影響

實驗中25個節點隨機分布在參數表內所設定的區域內，節點之間的傳輸距離為250 m，干擾距離為500 m，根據節點分布情況編寫程序自動生成通信圖和沖突圖，算法即是根據沖突圖進行信道分配。

圖3顯示了可用信道數目為12時，在所有情況下，由于接口數目的增加，每個節點相應可用信道數目增加，網絡沖入百分比呈下降趨勢。本文所提算法在沖突百分比方面均優于Tabu?Based算法。例如，接口數目為4，可用信道數目為12時，沖突百分比降低了近50%。

圖4顯示了在每個節點配置3個接口時，在可用信道數目相同時，本文所提算法優于Tabu?Based算法。

5 結 語

針對多接口多信道無線Mesh網絡，分析了網路干擾模型，并提出了基于粒子群優化的信道分配算法，采用Matlab設計實現算法。仿真表明，該算法有效降低了網絡干擾并顯著提升網絡性能。

參考文獻

[1] AKYILDIZ I F， WANG X， WANG W. Wireless mesh networks： a survey [J]. Computer Networks， 2005， 47： 445?487.

[2] KENNEDY J， EBERHART R. A discrete binary version of the particle swarm algorithm [C]// IEEE Int Conf on Computional Cybernetics and Simulation. Orlando， US： IEEE， 1997： 4104?4108.

[3] RANIWALA A， GOPALAN K， CHIUEH T. Centralized channel assignment and routing algorithms for multi?channel wireless mesh networks [J]. ACM Mobile Computing and Communications Review， 2004， 8（2）： 50?65.

[4] SUBRAMANIAN A P， GUPTA H. Minimum interference channel assignment in multiradio wireless mesh networks [J]. IEEE Transactions on Mobile Computing， 2008， 7（12）： 1459?1473.

[5] RAMACHANDRAN K N， BELDING E M， Almeroth KC. Interference?aware channel assignment in multi?radio wireless mesh networks [C]// Proceedings of INFOCOM. [S.l.]： INFOCOM， 2006： 111?121.

[6] KO B J， MISHRA V， PADHYE J， et al. Distributed channel assignment for multi?radio 802.11 mesh networks [R]. US： Colombia University， 2006.

[7] SKALLI H， GHOSH S， DAS S K， et al. Channel assignment strategies for multiradio wireless mesh networks： issues and solutions [J]. IEEE Communications Magazine， 2007， 45（11）： 86?95.

[8] CHENG H， XIONG N. Nodes organization for channel assignment with topology preservation in multi?radio wireless mesh networks [J]. Ad Hoc Networks， 2012 （10）： 760?773.

[9] SHAO B， TAO J， WANG F. Static channel assignment with the physical interference model for maximum capacity in multi?radio multi?channel wireless mesh networks [C]// 2010 Ninth International Conference on Grid and Cloud Computing. Nanjing， China： ICGCC， 2010： 338?343.

[10] HU X H，EBERHART R，SHI Y H. Swarm intelligence for permutation optimization a case study of n?queens problem [C]// Proc. of the 2003 IEEE Swarm Intelligence Symposium. Indianapolis， US： IEEE， 2003： 243?246.

[11] 胡家聲，郭創新，葉彬.離散離子群優化算法在輸電網絡擴展中的應用[J].電子系統自動化，2004，28（20）：31?36.

[12] JAIN K， PADHYE J， PADMANABHAN V N， et al. Impact of interference on multi?hop wireless network performance [C]// Proc. of ACM MobiCom. US： ACM， 2003： 45?54.

[13] 高廣恩，劉全利，王偉.基于離散粒子群優化的工業無線網多信道分配算法[J].控制與決策，2012，27（5）：697?702.