無線Mesh網(wǎng)按需路由算法的研究與實現(xiàn)

李建利

（山西警察學院，山西 太原 030021）

無線Mesh網(wǎng)按需路由算法的研究與實現(xiàn)

李建利

（山西警察學院，山西 太原 030021）

針對無線Mesh網(wǎng)QoS的路由特點，本文主要以蟻群算法為基礎，將其應用到無線Mesh網(wǎng)絡中，系統(tǒng)地分析了這種算法，對其性能進行了改進，并在此基礎上，提出了一種全新的基于蟻群算法的無線Mesh網(wǎng)按需路由算法.實驗結(jié)果表明，結(jié)合貪婪搜索和分布式計算，本文提供的算法具有強大的搜索能力.

無線Mesh網(wǎng)；Ad Hoc網(wǎng)絡；蜂窩無線網(wǎng)；蟻群算法

隨著計算機網(wǎng)絡技術，移動技術的更新?lián)Q代，人們對技術的需求逐漸轉(zhuǎn)換為便捷化，通過手機,PAD等設備把計算機無線網(wǎng)絡推向一個的高峰.國內(nèi)外的專家學者對無線組網(wǎng)進行了大量研究與實踐.其中，一種新型寬帶無線網(wǎng)絡結(jié)構——無線Mesh網(wǎng)絡(WMN)成為無線網(wǎng)絡研究中的一個熱點課題.在OSI的參考模型中，網(wǎng)絡操作系統(tǒng)實現(xiàn)的通信協(xié)議主要通過網(wǎng)絡層完成，網(wǎng)絡層通過地址來確定信息，并且實現(xiàn)了邏輯地址到物理地址的翻譯.首先通過源點，然后到網(wǎng)絡結(jié)點，最后到目標節(jié)點對路由器進行選擇，并且實現(xiàn)業(yè)務流處理.例如通過路由控制了數(shù)據(jù)分組阻塞.在OSI模型中，網(wǎng)絡層最復雜，由于無線Mesh網(wǎng)絡與傳統(tǒng)的ad hoc網(wǎng)絡和有線網(wǎng)絡是完全不同的網(wǎng)絡，傳統(tǒng)的ad hoc網(wǎng)絡必須首先訪問集中接入的點才能進行無線連接，這樣最少要兩個節(jié)點相鄰，網(wǎng)絡中的每個節(jié)點，也只能通過接入點才能實現(xiàn)相互間的通信.這就意味著兩個節(jié)點的實際距離不能太遠，這樣就大大地限制了無線網(wǎng)絡的應用范圍.

1 基于蟻群的按需路由算法設計

針對無線網(wǎng)絡路由選擇問題，設計按需路由算法，首先分析無線MESH網(wǎng)絡中出現(xiàn)的各種問題，然后確定不同的數(shù)據(jù)，最后根據(jù)不同的需求，數(shù)據(jù)的傳輸通過最優(yōu)路徑來實現(xiàn).通過算法設計建立簡單模型：設定N個節(jié)點和節(jié)點之間的距離，確定一個經(jīng)過每個節(jié)點，并且每次經(jīng)歷的節(jié)點都是最短路線.設定G=（V,A）,其中，A是G的邊，V是G的頂點，通過每個節(jié)點之間的距離，對Hamilton回路確定一個最短的.

2 基于蟻群算法（ACO）實現(xiàn)的算法流程

為了說明問題，首先將以上問題實例化，以建立一個螞蟻模型.通過圖論進行定義，設定G=（V,A）,其中，A是G的邊，V是G的頂點，通過每個節(jié)點之間的距離，對Hamilton回路確定一個最短的.

蟻群算法的簡單個體特點如下：

2.1 節(jié)點i-j的運動實現(xiàn)了循環(huán)的過程，邊(i,j)通過螞蟻進行物質(zhì)的釋放，這種方式叫做信息素軌跡.

2.2 訪問的節(jié)點通過螞蟻概率進行選擇，2個節(jié)點之間的距離和路徑函數(shù)通過螞蟻概率實現(xiàn).

2.3 在循環(huán)之前，訪問的過節(jié)點不能讓螞蟻進行選擇，滿足了約束條件.簡單蟻群算法如下：(1)對初始化蟻群A(t)；(2)通過目標函數(shù)實現(xiàn)螞蟻適應的評價A(t)；(3)對適應度選擇，根據(jù)螞蟻經(jīng)過的路徑釋放信息素，如果適應度越高，那么信息素的釋放越多；(4)依據(jù)選擇路徑和節(jié)點信息素通過螞蟻進行節(jié)點移動；(5)通過時間不斷消散進行信息素揮發(fā).

3 基于蟻群無線MESH網(wǎng)路由算法實現(xiàn)

3.1 基于蟻群算法（ANT）實現(xiàn)模型

首先每條路徑的信息量在初始時刻都是相等的.設置τij=C(C為為常），螞蟻k(k=1,2,3…)，信息量的轉(zhuǎn)移方向通過運動的路徑實現(xiàn).隨機比例規(guī)則是通過螞蟻系統(tǒng)的轉(zhuǎn)移規(guī)則進行實現(xiàn)，隨機比例規(guī)則針對節(jié)點i，對螞蟻k選擇給出節(jié)點j的概率.節(jié)點i的轉(zhuǎn)移概率 在t時刻為：

其中，allowedk={0,1,2,3…,n-1}表示進行選擇的節(jié)點，通公式（1），τijα(t)*ηijβ和pijk(t)成正比.節(jié)點能見度通過ηij表示，參數(shù)α和β表示在運動過程中，螞蟻的啟發(fā)和積累的信息進行路徑的選擇非常重要.人工蟻群針對不同的真實蟻群有記憶功能.通過不同的n個節(jié)點，螞蟻經(jīng)過的路徑都實現(xiàn)了一個數(shù)據(jù)結(jié)構的設計，這種設計叫做禁忌表.通過禁忌表實現(xiàn)了螞蟻在t時刻經(jīng)過的節(jié)點，螞蟻在本循環(huán)中不能在t時刻經(jīng)過這些節(jié)點.循環(huán)結(jié)束后，通過禁忌表來建立和設計螞蟻經(jīng)過節(jié)點路徑的長度.螞蟻進行路徑自由選擇，最后清空禁忌表.

在完成循環(huán)的過程，在t時刻，經(jīng)過路徑的信息如下:

其中，,螞蟻k在(t,t+1)時刻，信息信息素量在經(jīng)過路徑(i,j)為△τijk(t,t+1)，這個值是螞蟻的優(yōu)劣程度.信息素釋放多，那么螞蟻經(jīng)過的路徑就越短.在循環(huán)中，針對信息素量經(jīng)過的路徑(i,j)為△τijk(t,t+1).信息素軌跡系數(shù)是(1-ρ)，通過系數(shù)ρ＜1對螞蟻經(jīng)過路徑軌跡量進行累加.依據(jù)不同的算法，根據(jù)不同的問題，△τij，△τijk及Pijk三種可以表達不同的形式.

3.2 蟻量系統(tǒng)和蟻密模型

蟻密蟻量模型和△τijk(t,t+1)的對不，他們的表示方式不同.蟻密模型中，每個單位的長度通過螞蟻經(jīng)過路徑(i,j)進行信息量的釋放.蟻密模型中，每單位長度Q/dij表示螞蟻經(jīng)過路徑(i,j)進行信息量的釋放.蟻密模型中,螞蟻在路徑(i,j)上，從i向j移動信息軌跡強度和dij沒有關系.蟻量模型中，和dij成反比.蟻量模型中螞蟻對短路徑有吸引力，并且增加見度因數(shù)ηij.蟻密和蟻量模型中，通過偽碼對實現(xiàn)過程進行表示.(1)算法的初始化過程：

設t:=0；t是計數(shù)器

Nc:=0；Nc是計數(shù)器

τij(t):=C；{為每條路徑(i,j)設一個軌跡強度的初始值}

在n個節(jié)點上把m只螞蟻進行設置：

設置s：=1，表索引通過s表示，在禁忌表中對螞蟻初始節(jié)點設置

(2)對禁忌表進行重復(n-1)次

設s:=s+1

通過pijk(t)對節(jié)點j進行選擇

針對螞蟻k，在tabuk中加入節(jié)點j

對于每個路徑(i,j)，根據(jù)方程式5-2計算τij(t,t+1)；

最短路徑的記錄if Nc＜Ncmaxthen對禁忌表進行清空.

設s:=1

循環(huán)結(jié)束后，回初始位置.

設t:=t+1

設△τij(t,t+1):=0

else設置最短路徑；

蟻周模型實現(xiàn)：

以上2種模型和蟻周模型主要區(qū)別為△τijk(t,t+1)對螞蟻經(jīng)歷的路徑不同，在循環(huán)中，螞蟻經(jīng)過n步通過(t,t+n)，更新值如下：

方程不是每步軌跡更新，所以ρ1與ρ不同，通過建立完整的路徑后，螞蟻在更新軌跡量.

蟻周模型算法實現(xiàn)如下.（1）蟻周模型初始化：

設t:=0；t是計數(shù)器

Nc=0；Nc是循環(huán)次數(shù)

τij(t):=C；{為每條路徑(i,j)設一個軌跡強度的初始值}

τij=0；{軌跡強度的增量的初始值為0}

模型中，ηij=1/dij，通過啟發(fā)式算法對ηij進行確定

在n個節(jié)點中，對m只螞蟻進行地置

設置s:=1

(2)針對禁忌表重復(n-1)次

設s:=s+1

for k:=1 to n-1 do{搜索螞蟻k的禁忌表}

設(h.l):=(tabuk(s),tabuk(s+1)){(h,l)是在螞蟻k的禁忌表中連接節(jié)點(s,s+1)的路徑}

每一路徑(i,j)依據(jù)公式5計算τij(t+n)

設△τij(t,t+n):=0

if Nc＜Ncmax，禁忌表被清空

設s:=1

tabuk(s)=i{一次循環(huán)后螞蟻又重新回到初始位置}

設t:=t+1

本文主要以蟻群算法為基礎，將其應用到無線Mesh網(wǎng)絡中，系統(tǒng)地分析了這種算法，對其性能進行了改進，實驗表明算法可以加快計算速度，減少時延；增加穩(wěn)定性并且有利于負載平衡.實驗表明本文提出的算法具有很強并行性，通過信息素實現(xiàn)合作，這種方式具有很好的可擴充性.在無線Mesh網(wǎng)絡中節(jié)點中，移動性需要一種全新的簡單快捷的算法，應用蟻群算法不失為一種好的選擇.

〔1〕喬宏,張大方,謝鯤,何施茗,張繼.多射頻無線mesh網(wǎng)中的聯(lián)合協(xié)作路由與信道分配算法 [J].電子學報,2016(06): 1400-1405.

〔2〕國潤竹.面向無線Mesh網(wǎng)絡的DSDV路由協(xié)議算法研究[D].遼寧大學,2016.

〔3〕付永濤.無線Mesh網(wǎng)絡中的機會路由算法研究[D].電子科技大學,2015.

〔4〕謝忠明.無線Mesh網(wǎng)絡多徑路由算法的研究與應用[D].蘇州大學,2015.

〔5〕楊陽.無線Mesh網(wǎng)絡中具有QoS保障的路由算法研究[D].北京郵電大學,2015.

TN926；TP393

A

1673-260X（2017）08-0013-02

2017-05-29

本文系關心下一代“十三五”國家規(guī)劃教科研微型課題，國家級階段性成果（GGWEDU-W011）