劉友武

(三明學院 經(jīng)濟與管理學院，福建 三明 365004)

無線Mesh網(wǎng)絡[1]作為新興一代無線技術出現(xiàn)，其動態(tài)、自適應、高帶寬、多跳及易擴展等特點為很多場景解決“最后一公里”提供了優(yōu)良的方案。自2006年發(fā)布的《國家中長期科學和技術發(fā)展規(guī)劃綱要》實施和2015年互聯(lián)網(wǎng)大會以來，無線mesh網(wǎng)絡作為我國信息化發(fā)展的重要戰(zhàn)略領域，取得了長足發(fā)展[2-3]。無線Mesh網(wǎng)絡廣泛應用于各個領域，小到家庭，大到學校、醫(yī)院及休閑場所等，為國家的安全穩(wěn)定、社會的進步和經(jīng)濟的發(fā)展做出了巨大貢獻。

在無線Mesh網(wǎng)絡部署中，雖然網(wǎng)絡性能可以通過增加網(wǎng)關節(jié)點數(shù)量有效提升，但是網(wǎng)關節(jié)點數(shù)量的增加也造成部署成本和后期維護成本的增加。網(wǎng)關節(jié)點作為無線Mesh網(wǎng)絡和外部網(wǎng)絡之間的橋梁，其負載積累將對無線Mesh網(wǎng)絡的容量產生消極影響。如圖1的WMN骨干網(wǎng)架構圖所示，圖中兩個網(wǎng)關節(jié)點（Gateway1和Gateway2）和10個路由節(jié)點（router1～10）共同組成了一個WMN骨干網(wǎng)，其中兩個網(wǎng)關節(jié)點與Internet直連，10個路由節(jié)點分別以兩個網(wǎng)關節(jié)點為簇頭形成了兩個簇，簇區(qū)域內的路由節(jié)點通過鏈路與簇頭進行數(shù)據(jù)傳輸通信。圖中顯示Gateway1負責四個路由節(jié)點的數(shù)據(jù)匯聚，而Gateway2負責六個路由節(jié)點的數(shù)據(jù)匯聚，顯然Gateway1相對于Gateway2負載較輕，整個WMN網(wǎng)絡資源沒有得到充分利用。在具有多個網(wǎng)關節(jié)點的WMN中，負載均衡在網(wǎng)絡中低帶寬的回程鏈接時具有重要作用。網(wǎng)關鏈路的帶寬和延遲受限于WMN的類型和具體環(huán)境，而且網(wǎng)關自身性能對流量和負載表現(xiàn)不同，對負載均衡的影響程度具有差異性。另外，網(wǎng)關也有耗盡回程鏈路帶寬容量的可能性。因此，WMN中網(wǎng)關節(jié)點的合理部署對緩解節(jié)點過載問題具有重要作用。

圖1 WMN骨干網(wǎng)架構圖

1 相關工作

目前網(wǎng)關負載均衡的策略主要可以分為3種[4]。第一種是基于移動邊界的負載均衡（moving boundary-based load balancing,MBLB）。 文獻[5]提出一種最大流量最短路徑的網(wǎng)關部署算法來滿足無線網(wǎng)絡中路由器的帶寬需要；文獻[6]以分層思想為基礎、根據(jù)簇的大小并以之為條件提出多層的網(wǎng)關部署算法。第二種是基于分區(qū)的負載均衡（partitioned host-based load balancing,PHLB）。文獻[7]將網(wǎng)絡當中的節(jié)點分成不相關的簇，簇首為網(wǎng)關節(jié)點，簇中各節(jié)點以生成樹中的路徑來進行數(shù)據(jù)轉發(fā)；文獻[8]綜合考慮了網(wǎng)關數(shù)量和MR-GW(mesh router-gateway)路徑長度，提出一種網(wǎng)關部署優(yōu)化的啟發(fā)式算法。第三種是基于概率分割的負載均衡。文獻[9]同時考慮了路由器數(shù)量、客戶端數(shù)量以及客戶端對流量的需求，提出了以網(wǎng)關的位置多路通信的流權值為判定的算法；文獻[10]提出一種在滿足QOS的約束條件下尋求最小的網(wǎng)關數(shù)目的算法；文獻[11]通過對粒子的速度、相關運算規(guī)則及其運動方程的重新定義和設計,提出了一種基于粒子群的無線Mesh網(wǎng)關優(yōu)化部署算法。

近年來，有學者將螢火蟲算法（combination of firefly and particle swarm optimization，CFPSO）和粒子群優(yōu)化算法應用到無線網(wǎng)絡的研究中。螢火蟲算法（FF）[12]是一種生物啟發(fā)式算法，常用于解決無線網(wǎng)絡的聚類問題。螢火蟲算法由螢火蟲根據(jù)發(fā)光的亮度進行驅動，兩只螢火蟲個體通過亮度對比，其中較暗的個體被較亮的個體吸引，從而驅動進行空間搜索。

粒子群優(yōu)化（particle swarm optimization,PSO）算法是由Kennedy和Eberhart[13]提出,該算法由鳥群捕食行為演化而來,其思想主要源于鳥類和魚類群體的社會行為[14]。在PSO算法中，群體中的每個粒子根據(jù)被賦予的速度值在空間中不斷搜索運動，每個粒子被賦予一個儲存單元，儲存單元將記錄位置和速度的信息，通過對比后迭代得出全局最優(yōu)化值。

文獻[15]針對傳感器網(wǎng)絡中計算復雜度和性能之間的優(yōu)化平衡問題,提出一種基于多傳感器的HAR（human activity recognition）系統(tǒng)，通過一種改進的二進制螢火蟲群優(yōu)化算法(improved binary glowworm swarm optimization，IBGSO),并選取了對HAR性能有顯著影響的傳感器源,進而針對HAR構建了基于優(yōu)化傳感器部署的集成學習系統(tǒng)。文獻[16]提出了一種融合GSO（glowworm swarm optimization）和 FF（Firefly algorithm）關鍵元素的網(wǎng)絡螢火蟲算法(cyber firefly algorithm，CFA)，并通過多引導解、模式搜索、多起始搜索、群體重建和目標景觀分析等AMP（adaptive memory programming）響應策略，進一步發(fā)揮了CFA的優(yōu)勢。文獻[17]針對變電站選址定容規(guī)劃的經(jīng)濟性與供電可靠性的問題，提出了一種運用參數(shù)方差調節(jié)的螢火蟲優(yōu)化算法對基于設備全壽命周期成本的變電站選址定容新模型進行求解，該算法通過區(qū)分螢火蟲種群的搜索階段來提高尋優(yōu)速度和全局尋優(yōu)能力。文獻[18]針對無線傳感器網(wǎng)絡節(jié)點的分布優(yōu)化問題,提出了一種有效的混沌螢火蟲優(yōu)化算法。利用螢火蟲算法的優(yōu)越的尋優(yōu)能力來實現(xiàn)最優(yōu)的網(wǎng)絡節(jié)點分布,并引入立方映射混沌算子來提高算法的局部搜索能力和保持種群的多樣性。文獻[19-21]通過粒子群優(yōu)化算法在無線網(wǎng)絡定位和干擾點部署方面進行了應用研究。文獻[22]針對無線傳感器的網(wǎng)絡節(jié)點參與構建網(wǎng)絡的問題，通過模糊粒子群算法，利用每個粒子代表一個可能解，進行迭代尋優(yōu)，對節(jié)點進行優(yōu)化部署。

從上述研究可見，無線Mesh網(wǎng)絡的網(wǎng)關部署問題主要集中于網(wǎng)關節(jié)點的定位、數(shù)量以及負載均衡等方面。首先，網(wǎng)關節(jié)點本身作為無線mesh網(wǎng)絡的關鍵節(jié)點所承擔的“責任”非常重要，因此無線mesh網(wǎng)絡中網(wǎng)關節(jié)點的數(shù)量和定位決定了其它mesh節(jié)點是否能高質量地與Internet進行連接。網(wǎng)關節(jié)點的數(shù)量和定位對部署成本具有重要影響，因此如何在可控的成本范圍內達到網(wǎng)絡的最佳狀態(tài)，網(wǎng)關節(jié)點的數(shù)量和定位顯得尤其重要。其次，網(wǎng)關節(jié)點作為內外網(wǎng)絡的橋梁，負載均衡問題也對整個網(wǎng)絡的拓展產生極大的影響。再者，已經(jīng)有學者利用螢火蟲和粒子群優(yōu)化的組合算法來解決在端對端的WMN中提高資源共享效率的問題，如文獻[23]利用螢火蟲和粒子群優(yōu)化的混合方法應用于多跳網(wǎng)絡中以提升和弦協(xié)議(chord protocol)的性能，進而希望能在端對端的無線mesh網(wǎng)絡中提高資源共享效率，但是該算法只是立足于WMN節(jié)點中端與端之間,并沒有考慮到整個WMN的負載均衡,實驗結果也只是說明提高了端與端之間的和弦協(xié)議的性能，僅解決了WMN局部的性能優(yōu)化問題。

以上所述說明目前還沒有發(fā)現(xiàn)將螢火蟲和群粒子算法應用到無線mesh網(wǎng)絡的網(wǎng)關部署優(yōu)化問題的實例。因此,針對網(wǎng)關節(jié)點的數(shù)量與定位控制、負載均衡等問題，本文在文獻 [23]的基礎上對螢火蟲和粒子群優(yōu)化算法進行組合優(yōu)化，在給定的網(wǎng)絡拓撲結構中，利用螢火蟲算法，尋找目標網(wǎng)關節(jié)點，實現(xiàn)冗余節(jié)點的移動和更新，并將粒子群優(yōu)化算法融入螢火蟲算法中以解決螢火蟲算法陷入局部極小的局限性問題，改善螢火蟲算法在尋找最優(yōu)解過程中的行為。

2 網(wǎng)絡模型

本文參考文獻[24]以無向圖 G=（V,E)來表示 WMN 的網(wǎng)關部署問題,其中 V={v1，v2，v3，…，vn}表示網(wǎng)絡中的網(wǎng)關節(jié)點，N為網(wǎng)關節(jié)點的總數(shù)。用eij表示網(wǎng)絡中的節(jié)點i與節(jié)點j之間的雙向鏈路，eij∈E,E表示網(wǎng)絡中的節(jié)點在指定的傳輸閾值內雙向通信的有向鏈路集合。本文假設了一個平面，平面中所有的射頻端都有一個覆蓋范圍R和一個相同的干擾范圍R'。當覆蓋范圍小于干擾范圍，即R＜R'時，說明接收點處于相對應的兩個發(fā)射節(jié)點所覆蓋的位置交叉范圍內，那么此時的節(jié)點分組傳輸就會產生相互干擾。

本文將無線mesh網(wǎng)絡劃分的簇區(qū)域規(guī)定為具有獨立性，網(wǎng)關將覆蓋網(wǎng)絡中簇區(qū)域的所有節(jié)點，簇中的成員節(jié)點通過網(wǎng)關與Internet進行聯(lián)通。本文用S={s1，s2，s3，…，sk}表示網(wǎng)絡中候選的網(wǎng)關集合，用表示網(wǎng)絡中候選網(wǎng)關節(jié)點的數(shù)量。node（sk）用來表示普通成員節(jié)點的集合。本文用εi記錄算法中節(jié)點vi未被覆蓋的次數(shù)，初始值為0。

2.1 相關概念

定義1網(wǎng)關節(jié)點的負載均衡指數(shù)(Gateway node load index,GNLI)。GNLI表示無線mesh網(wǎng)絡中網(wǎng)關節(jié)點的負載情況。

式中βki為節(jié)點k的負載流量所需通過網(wǎng)關發(fā)送的部分;Tk表示節(jié)點k在通信過程中產生的負載;Di表示該節(jié)點與網(wǎng)關之間的回程鏈路的帶寬。LI表示網(wǎng)關節(jié)點占用返程鏈路的比例。網(wǎng)關節(jié)點負載均衡的目標就是根據(jù)網(wǎng)關最大化返程鏈路開銷，使GNLI值最小化。

定義2簇Di的平均有效載荷（average payload，AP）

其中，γij的取值為0或1，表示如果mesh路由器的指定網(wǎng)關節(jié)點為vj∈Di，則γij=1；反之γij=0。

定義3節(jié)點距離關系

假設 M={m1，m2，…，mn}其中節(jié)點 mi的位置坐標為（xi，yi）（i=1,2，…，N），且任何一個節(jié)點性能具有排它性。本文參考文獻[25]，為了優(yōu)化節(jié)點數(shù)量，設定節(jié)點的感知半徑為RS，節(jié)點的檢測半徑為r，RS且大于r。在節(jié)點vi的檢測半徑內，假設存在一個冗余節(jié)點vj，它的位置坐標為(xj，yj)，則可得兩節(jié)點之間的距離Dij。

2.2 目標描述

無線MESH網(wǎng)絡在QOS服務保障要求下，通過算法能實現(xiàn)網(wǎng)關數(shù)量和負載均衡的最小化及對網(wǎng)絡有效載荷的最大化。即具體優(yōu)化目標為：

3 基于螢火蟲和粒子群優(yōu)化組合的網(wǎng)關部署算法

3.1 螢火蟲算法

螢火蟲算法中，螢火蟲在相互吸引過程中無關性別，螢火蟲的關注度與螢火蟲本身亮度有關，即一只螢火蟲會根據(jù)亮度與本身對比而受到影響，而且螢火蟲之間的吸引力與它們之間的亮度成正比，而與距離成反比[26]。

其中r表示源個體與目標個體的距離，IS表示源個體的強度。

其中β0表示的吸引力變化，γ是光吸收系數(shù)。

3.2 粒子群優(yōu)化算法

3.2.1 粒子表示

在PSO算法中，利用群中每個粒子具有的位置和速度的特性，本文定義Xi（t）為群中粒子i在 t時刻的位置向量;Vi（t）為粒子在時刻的速度向量;Pi（t）為粒子i在 t時刻的局部最優(yōu)位置向量。

3.2.2 粒子的適應度

粒子適應度函數(shù)作為粒子群中粒子性能的表現(xiàn)，粒子適應度值與粒子所處的位置成正比關系。因此適應度值越大表示粒子位置最優(yōu)，適應度函數(shù)f（Xi）的計算式如式（6）

式中GNLI為網(wǎng)關節(jié)點的負載均衡指數(shù);n（xi）指所部署網(wǎng)絡的網(wǎng)關節(jié)點的總量;其中α+β=1，Si表示候選網(wǎng)關節(jié)點。

3.2.3 粒子位置及速度相關公式

式中，c1和c2為學習因子;r1和r2是介于 [0，1]的隨機數(shù);vij∈[-vmax,vmax],vmax是一個由用戶設定的常數(shù)，所設定的值限定粒子在一個循環(huán)中的最大移動距離。

3.3 基于螢火蟲和粒子群優(yōu)化的組合網(wǎng)關部署算法

由于螢火蟲算法移動方向隨機，很難從全局最優(yōu)位置找到最優(yōu)解。采用粒子群優(yōu)化算法能較好地消除螢火蟲算法的局限性，改善螢火蟲算法從全局尋找最優(yōu)解。

本文先利用螢火蟲算法，在指定監(jiān)測區(qū)域內，通過k均值聚類算法（k-means clustering algorithm,k-means）[25]對網(wǎng)絡節(jié)點進行分簇，選出冗余節(jié)點，然后使冗余節(jié)點處于睡眠狀態(tài)[27]，在WMN運行一段時間后，簇首承載和傳輸了大量數(shù)據(jù)，當節(jié)點負載達到一定閾值，此時喚醒冗余節(jié)點，計算出節(jié)點間相對距離進而進行排序，最后通過粒子群優(yōu)化算法對節(jié)點全局進行優(yōu)化。算法流程圖如圖2所示。

圖2 基于螢火蟲和粒子群優(yōu)化的組合（CFPSO）算法流程圖

Step1根據(jù)螢火蟲算法初始化粒子群，根據(jù)k-means算法對節(jié)點進行分簇，選出冗余節(jié)點。設置粒子種群數(shù)量、最大距離閾值及迭代次數(shù)等。

Step2根據(jù)公式(3)計算網(wǎng)絡中的簇間的距離并根據(jù)距離進行排序。

Step3根據(jù)公式(6)對群中每個粒子的適應度函數(shù)和速度進行計算并將得到的結果進行相應更新處理。

Step4根據(jù)粒子適應度值的比較，得出粒子個體最佳情況，并將位置標記為最佳。

Step5使用粒子群組合算法產生下一代粒子，根據(jù)算法對粒子群進行重新分簇，并且將下一代粒子的適應度值進行重新計算與前一代粒子進行比較排序。

算法中產生的下一代粒子將會與上一代粒子進行比較，擇優(yōu)算出適應度值以保證算法的收斂性。算法根據(jù)下一代粒子的適應度值與上一代粒子的適應度值的比較來判斷規(guī)則是否有效,如果判斷有效則流程轉向Step2，否則轉向Step6。

Step6輸出位置和速度最佳的粒子。

4 仿真實驗

4.1 環(huán)境參數(shù)

為了驗證算法的時效性，利用NS2（network simulator version 2）網(wǎng)絡仿真工具模擬無線mesh網(wǎng)絡環(huán)境。仿真實驗中部署4種算法，即CFPSO算法、SMS算法、FF算法和PSO算法[23]。通過網(wǎng)關負載、有效荷載、數(shù)據(jù)投遞率和端到端延遲等四個方面進行比較。實驗中預設隨機生成50個擁有100個網(wǎng)絡節(jié)點的無線mesh網(wǎng)絡拓撲結構，并采用隨機抽取的方式將候選網(wǎng)關節(jié)點的數(shù)量控制在總節(jié)點數(shù)量的20%內，其中α=0.3,β=0.3,L=20,w=0.7,c1=c2=2,vmax=4,C=120。根據(jù)網(wǎng)絡中的節(jié)點總數(shù)計算候選網(wǎng)關和Mesh節(jié)點的數(shù)量。具體仿真環(huán)境參數(shù)如表1所示。

表1 仿真實驗參數(shù)列表

4.2 實驗結果及分析

仿真實驗中部署的四種算法在不同時間維度下針對、、數(shù)據(jù)投遞率和端到端延遲等四個方面進行比較，得到的結果如圖3～6所示。

圖3 網(wǎng)關負載指數(shù)的比較

圖4 網(wǎng)關有效載荷的比較

圖5 數(shù)據(jù)包投遞率的比較

圖6 端到端延遲的比較

圖3顯示仿真時間下4種算法的網(wǎng)關負載指數(shù)的情況比較。由于CFPSO算法根據(jù)K-means算法對節(jié)點進行分簇，并利用螢火蟲算法選出冗余節(jié)點，然后通過粒子群優(yōu)化算法對全局進行了進一步優(yōu)化，因此CFPSO算法在GNLI值上比其它幾種算法要低，說明CFPSO算法相對于其它算法更加有效地實現(xiàn)網(wǎng)關的負載均衡。

圖4顯示仿真時間下網(wǎng)關有效荷載的情況。隨著通信鏈路聯(lián)通，網(wǎng)絡節(jié)點增加的情況下，節(jié)點相互的吸引力也隨之加大，從而也促使網(wǎng)關節(jié)點的有效荷載增大。結果顯示，CFPSO算法總體性能優(yōu)于其它幾種算法。

數(shù)據(jù)包投遞率（packet delivery ratio，PDR）是目標節(jié)點接收到的數(shù)據(jù)包與源節(jié)點發(fā)送的數(shù)據(jù)包的比值。PDR主要體現(xiàn)網(wǎng)絡可靠性和網(wǎng)絡擁塞狀況。圖5的仿真結果表明，隨著網(wǎng)絡節(jié)點通信數(shù)量的增加，數(shù)據(jù)包投遞率的前期呈現(xiàn)上升趨勢，在60s～90s時間段時由于節(jié)點通信出現(xiàn)擁塞，四種算法的數(shù)據(jù)包投遞率都有大幅降低，之后數(shù)據(jù)包投遞率穩(wěn)步上升。本文提出的算法采用分簇思想，改善了螢火蟲算法從全局尋找最優(yōu)解的問題，因此數(shù)據(jù)包投遞率總體表現(xiàn)好于其它幾種算法

圖6的仿真結果表明，在仿真時間前期四種算法的端到端延遲時間差別不大，但是隨著隨著時間的推移，網(wǎng)絡節(jié)點數(shù)量不斷增加，從而端到端的延遲時間也變大。本文提出的算法在仿真時間后期由于采用了分簇的策略，將區(qū)域分為多個簇區(qū)，較好地實現(xiàn)了節(jié)點間的負載均衡，因此，簇區(qū)內的節(jié)點通信延遲相對于其它幾種算法要低。

5 結論

根據(jù)螢火蟲算法在聚類應用方面的優(yōu)勢及粒子群優(yōu)化算法的全局優(yōu)化的特性，研究了網(wǎng)關部署與網(wǎng)關負載均衡的問題，提出了螢火蟲與粒子群優(yōu)化的組合算法，具有如下幾點優(yōu)勢：（1）該算法考慮了節(jié)點間的距離，實現(xiàn)網(wǎng)關節(jié)點部署與網(wǎng)關之間負載均衡的動態(tài)平衡。（2）與文獻[23]相比，本文研究立足于整個WMN中網(wǎng)關部署和負載均衡的全局問題,克服了文獻研究僅針對WMN中端對端的和弦協(xié)議優(yōu)化的局部問題。文獻[23]是本文研究的一個局部特例，本文是文獻[23]算法應用的衍生，是對文獻[23]算法的進一步利用和拓展。(3)模擬仿真實驗結果表明CFPSO算法在負載均衡、網(wǎng)關有效載荷、數(shù)據(jù)投遞率和端到端延遲等4個方面優(yōu)于其它算法。今后的研究將考慮螢火蟲算法與其它的自然啟發(fā)算法相結合，進一步提高網(wǎng)絡性能。