無線Mesh網按需路由算法的研究與實現

李建利

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

無線Mesh網按需路由算法的研究與實現

李建利

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

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

無線Mesh網；Ad Hoc網絡；蜂窩無線網；蟻群算法

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

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

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

2 基于蟻群算法（ACO）實現的算法流程

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

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

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

2.2 訪問的節點通過螞蟻概率進行選擇，2個節點之間的距離和路徑函數通過螞蟻概率實現.

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

3 基于蟻群無線MESH網路由算法實現

3.1 基于蟻群算法（ANT）實現模型

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

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

在完成循環的過程，在t時刻，經過路徑的信息如下:

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

3.2 蟻量系統和蟻密模型

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

設t:=0；t是計數器

Nc:=0；Nc是計數器

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

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

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

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

設s:=s+1

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

針對螞蟻k，在tabuk中加入節點j

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

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

設s:=1

循環結束后，回初始位置.

設t:=t+1

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

else設置最短路徑；

蟻周模型實現：

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

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

蟻周模型算法實現如下.（1）蟻周模型初始化：

設t:=0；t是計數器

Nc=0；Nc是循環次數

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

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

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

在n個節點中，對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的禁忌表中連接節點(s,s+1)的路徑}

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

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

if Nc＜Ncmax，禁忌表被清空

設s:=1

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

設t:=t+1

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

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

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

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

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

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

TN926；TP393

A

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

2017-05-29

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