基于蛙跳算法的Mesh網(wǎng)絡(luò)最優(yōu)路徑

邵伯樂

(亳州職業(yè)技術(shù)學院,安徽 亳州 236800)

0 引言

Mesh網(wǎng)絡(luò)是一種高速率和低成本的無線網(wǎng)網(wǎng)絡(luò),并隨著IEEE802.11和無線網(wǎng)絡(luò)快速發(fā)展獲得廣泛應(yīng)用[1-2]．Mesh網(wǎng)絡(luò)能根據(jù)具體的業(yè)務(wù)需求而進行定制,能充分利用無線局域網(wǎng)和無線自組織網(wǎng)絡(luò)的優(yōu)點,其應(yīng)用范圍也多種多樣,如可以用于組建家庭寬帶網(wǎng)、用于構(gòu)造區(qū)域網(wǎng)、用來建立公共緊急通信和戰(zhàn)場通信等[3]．在傳統(tǒng)的無線網(wǎng)絡(luò)中,網(wǎng)絡(luò)質(zhì)量和負載影響了網(wǎng)絡(luò)的吞吐量,而Mesh網(wǎng)路由于具備較高的傳輸速率、較大的覆蓋范圍、方便的架設(shè)方法以及完美的容錯能力,已被認為是無線組網(wǎng)技術(shù)中的最優(yōu)前途的技術(shù)之一[4]．

Mesh網(wǎng)絡(luò)作為一種無線網(wǎng)絡(luò),當數(shù)據(jù)傳輸?shù)穆窂桨l(fā)生阻塞或中斷時,Mesh網(wǎng)絡(luò)仍然會面臨著數(shù)據(jù)包丟失的問題．為了獲得更優(yōu)的路徑,一些文獻提出一些方法來改進Mesh網(wǎng)絡(luò)的最優(yōu)路徑．如喬宏等[5]提出了一種實現(xiàn)網(wǎng)絡(luò)公平協(xié)作的路由算法,將該問題轉(zhuǎn)換為最大化網(wǎng)絡(luò)整體效用的凸化問題,利用對偶分解和子梯度來實現(xiàn)mesh網(wǎng)絡(luò)的公平路由．沈小建[6]等提出了一種基于編碼感知和負載均衡的多播路由,基于負載均衡路由量來綜合考慮節(jié)點通信密集度和網(wǎng)絡(luò)擁塞程度,仿真實驗該協(xié)議能在提高吞吐量的前提下進行網(wǎng)絡(luò)編碼,實現(xiàn)負載均衡．張維維等[7]提出了一種基于博弈論和無線Mesh網(wǎng)絡(luò)路由與信道分配聯(lián)合優(yōu)化算法,通過建立極小極大合作納什均衡信道分配方案,并對博弈算法和貪婪算法對網(wǎng)絡(luò)吞吐量的影響進行比較．鄧曉衡等[8]提出了一種基于鏈路質(zhì)量與負載敏感的無線Mesh路由協(xié)議,在該協(xié)議中考慮鏈路多速率和負載動態(tài)性,以對鏈路的質(zhì)量進行準確評估．符琪[9]提出了一種基于業(yè)務(wù)感知的多路徑Qos路由策略,通過4個固定信道的競爭參數(shù)的AC隊列來實現(xiàn)不同業(yè)務(wù)數(shù)據(jù)包的存儲轉(zhuǎn)發(fā),通過改進信道競爭的分配參數(shù)來提出不同業(yè)務(wù)數(shù)據(jù)類型的路由判斷,該策略能實現(xiàn)不同業(yè)務(wù)流的信道和鏈路的公平使用．

以上工作均著眼于建立Mesh網(wǎng)絡(luò)的最優(yōu)路徑,并對其優(yōu)化,然而這些工作均以優(yōu)化整個路由為目標,未對其中的路徑的最優(yōu)化策略進行考慮[10],因此,提出了一種基于蛙跳算法和神經(jīng)網(wǎng)絡(luò)的Mesh網(wǎng)絡(luò)最優(yōu)路徑,并通過實驗證明了所提方法的正確性．

1 改進的蛙跳算法

1.1 蛙跳算法概述

蛙跳算法是由Eusuff和Lansey提出的混合蛙跳算法(Shuffled Frog Leaping Algorithm, SFLA),是在模因演化算法和粒子群算法的基礎(chǔ)上發(fā)展而來,該算法結(jié)合了這兩種方法的優(yōu)點,能廣泛地應(yīng)用于非線性、不連續(xù)、多目標和不可導問題．

隨機采取定義域內(nèi)的N只青蛙作為初始種群,第i只青蛙的坐標為xi={xi1,xi2,xi3,…,xin},將整個青蛙種群隨機劃分為a個種群,每個種群包含的個體數(shù)為b,則青蛙的總數(shù)和各個種群之間的關(guān)系滿足:

N=a*b

(1)

圖1 種群總體與子種群的關(guān)系

種群總體與各子種群的關(guān)系如圖1所示.

1.2 改進蛙跳算法

在每輪迭代中,適應(yīng)度最優(yōu)的個體和最差的個體分別記為po和pw,而整個種群中的最優(yōu)個體為pg,則種群個體pw被更新為:

p=pw+α(po-pw)

(2)

其中,p表示新一代種群中的個體,而α為學習率,即新的個體在最差適應(yīng)度個體的基礎(chǔ)上,要進行的改進．此時,計算個體的適應(yīng)度,如果p的適應(yīng)度小于pw,則在新的種群中采用p來替代pw,重復(fù)以上過程,直到局部搜索次數(shù)達到最大值．

圖2 青蛙個體更新方法

除最差個體外的其他個體的更新方法如下:

p=(1-C)po

(3)

其中,C的值域為大于0并小于1的可調(diào)參數(shù)．當其值隨著算法進行不斷變化時,會對算法產(chǎn)生影響．當該值設(shè)置合理時,設(shè)置為較小的值,以充分利用最優(yōu)值的信息．隨著迭代次數(shù)的不斷增加,青蛙的個體差距進一步降低,此時如果將C設(shè)置為較小的值,算法容易陷入局部最優(yōu)．C值的更新可以表示為:

C=1-e-20*(t/tmax)L

(4)

其中,參數(shù)t表示當前迭代次數(shù),tmax表示最大的迭代次數(shù),L為調(diào)整參數(shù)．

基于以上改進的青蛙個體更新方法,則改進的蛙跳算法如圖3所示.

2 基于改進蛙跳算法的mesh網(wǎng)絡(luò)路由獲取

該算法將網(wǎng)絡(luò)中的所有節(jié)點分為若干的簇,分簇協(xié)議采用Leach協(xié)議,然后再通過改進的蛙跳算法來建立多個簇頭之間的多跳路由．

圖3 改進的蛙跳算法

2.1 簇的個數(shù)

該算法根據(jù)Leach協(xié)議將網(wǎng)絡(luò)分為若干個簇,簇頭的數(shù)量根據(jù)下式來確定:

(5)

其中,參數(shù)εfs表示自由空間傳播模型對應(yīng)的功率放大所需的功耗系數(shù),參數(shù)εmp表示多路衰減傳播模型下功率放大所需要的功耗系數(shù)．

2.2 路由優(yōu)化算法描述

為了采用蛙跳算法來獲取最優(yōu)路由,首先需要定義適應(yīng)度函數(shù),這里設(shè)計的適應(yīng)度函數(shù)為:

(6)

其中,β和γ表示權(quán)重因子,β+γ=1,E為傳感器節(jié)點的剩余能量,E0為傳感器節(jié)點的初始能量,dmax為種群中所有個體距離基站的最大距離,dσ為該傳感器到基站的距離．

采用改進的蛙跳算法來實現(xiàn)mesh網(wǎng)絡(luò)的多簇路由的算法可以定義為:

算法1 基于改進蛙跳算法最優(yōu)路由算法

初始化: 參數(shù)β和γ, 調(diào)整參數(shù)L,種群的個數(shù)a,每個種群包含的個體數(shù)b;

步驟1: 個體編碼:根據(jù)簇的數(shù)量確定個體的位數(shù),確定個體的編碼的長度;

步驟2: 生成種群:根據(jù)種群的編碼隨機生成初始種群,并劃分為多個子種群,子種群個數(shù)為a,每個子種群包含的個體數(shù)b;

步驟3: 根據(jù)公式(6)計算種群個體的適應(yīng)度,根據(jù)適應(yīng)度對種群中的所有個體進行排序,將適應(yīng)度最優(yōu)的個體和最差的個體標記為po和pw,整個種群中的最優(yōu)個體為pg;

步驟4:對每個子種群中最差的個體采用公式(2)進行更新;

步驟5:對子種群中的其他個體按照公式(3)進行更新;

步驟6:判斷算法是否已經(jīng)達到最大的迭代次數(shù):

如果已經(jīng)達到,則算法結(jié)束;

否則返回步驟3繼續(xù)進行迭代．

3 仿真實驗

為了對本文提出的方法進行驗證,采用NS2工具來產(chǎn)生實際mesh網(wǎng)絡(luò)最近似的無線拓撲結(jié)構(gòu),然后對其擴展,使其能進行網(wǎng)絡(luò)編碼．Mesh網(wǎng)絡(luò)的總節(jié)點數(shù)為100個,仿真的區(qū)域為1 000*1 000的區(qū)域,分別對不同負載對應(yīng)的路由時延、吞吐量和帶寬消耗總量．仿真參數(shù)為:蘇劇分組大小為1 000字節(jié),節(jié)點傳輸范圍為200m,節(jié)點的干擾半徑為100 m,節(jié)點的傳輸帶寬為10 Mbit/s．將文中方法與文獻[6],文獻[7]和文獻[8]進行比較,4種方法得到的網(wǎng)絡(luò)吞吐量的比較如圖4所示.

圖4 網(wǎng)絡(luò)吞吐量比較

圖5 時延比較

圖6 帶寬消耗總量比較

圖4為4種方法的網(wǎng)絡(luò)吞吐量與網(wǎng)絡(luò)負載之間的關(guān)系,從中可以明確看出本文方法的網(wǎng)絡(luò)吞吐量遠遠大于其他三種方法．其原因可能是本文方法通過優(yōu)化了傳輸路由,縮短了傳輸路徑,從而使得網(wǎng)絡(luò)的總吞吐量更大．

網(wǎng)絡(luò)吞吐量與時延的關(guān)系如圖5所示,從圖中可以看出,4種方法的路由時延隨著網(wǎng)絡(luò)傳輸數(shù)據(jù)量的增加而逐漸增加,但相對于其他3種方法,本文方法的路由時延較慢,這是因為優(yōu)化的數(shù)據(jù)傳輸路徑使得總的傳輸時間減少,因此,使得網(wǎng)絡(luò)的總時延大大降低．

帶寬總耗量與數(shù)據(jù)發(fā)送速率之間的關(guān)系如圖6所示,與前面仿真的時延和網(wǎng)絡(luò)吞吐量類似,帶寬總耗量也隨著數(shù)據(jù)發(fā)送速率的增加而逐漸增大,但本文方法增加的最少．