基于蟻群的Mesh網(wǎng)絡路由算法模型的設計

張千里

（1.安徽理工大學 計算機科學與工程學院；2.淮南聯(lián)合大學，安徽 淮南 232001）

基于蟻群的Mesh網(wǎng)絡路由算法模型的設計

張千里

（1.安徽理工大學 計算機科學與工程學院；2.淮南聯(lián)合大學，安徽 淮南 232001）

隨著當今無線網(wǎng)絡的快速發(fā)展，人們對無線網(wǎng)絡的依賴性越來越強，本文主要對基于Mesh無線網(wǎng)絡的核心Mesh路由進行研究，提出基于蟻群的Mesh路由算法，蟻群算法具有自組織能力，因此將蟻群算法應用到Mesh路由中有一定的優(yōu)越性.該算法通過相鄰節(jié)點交換高度及現(xiàn)存能量，在整個網(wǎng)絡中建立梯度和平面路徑上的信息濃度，在路由維護階段，算法通過對路由傳送中的數(shù)據(jù)的信息素濃度進行相應的增加，并模仿螞蟻信息素的揮發(fā)過程.

無線Mesh網(wǎng)；路由算法；蟻群算法；信息素

1 無線Mesh網(wǎng)絡的發(fā)展

隨著當今無線網(wǎng)絡的快速發(fā)展，人們對無線網(wǎng)絡的依賴性越來越強.當前用戶連接無線網(wǎng)主要通過三種方式：（1）通過2G的GPRS連接；（2）通過3G網(wǎng)絡連接；（3）通過802.11無線局域網(wǎng)連接.這三種方式都具有信號穩(wěn)定、性能可靠、維護方面，但2G和3G基站建立費用較高，用戶聯(lián)網(wǎng)費用高，通過802.11無線局域網(wǎng)連接方式覆蓋范圍小，信號難以進行大面積覆蓋.基于Mesh的無線網(wǎng)絡是在Ad Hoc網(wǎng)絡發(fā)展起來的一種無線網(wǎng)絡技術，其具有自組網(wǎng)功能、費用低、覆蓋范圍廣和性能穩(wěn)定等優(yōu)點.

基于Mesh的無線網(wǎng)絡（WMN）主要有兩類節(jié)點組成：Mesh路由器和Mesh客戶.其中Mesh路由器具有網(wǎng)關路由和Mesh組網(wǎng)路由兩個功能.無線Mesh網(wǎng)絡，如1圖所示，眾多無線路由器（WR）相互合作，成網(wǎng)狀分布，從而將無線網(wǎng)絡對城市任意位置覆蓋，實現(xiàn)無線移動通信.

圖1 無線Mesh網(wǎng)絡

由于無線Mesh網(wǎng)絡具有自動組網(wǎng)功能，能夠提供無線網(wǎng)主干的靈活性，在無線網(wǎng)高速發(fā)展的今天特別受關注，無線Mesh網(wǎng)絡的如今的應用非常廣泛如：社區(qū)網(wǎng)絡、小區(qū)監(jiān)控系統(tǒng)、無線公交等.

2 蟻群算法概述

蟻群算法 （ant colony optimization,ACO），又稱螞蟻算法，它由Marco Dorigo于1992年在他的博士論文中提出，其核心思想是來自于大自然螞蟻尋食過程，螞蟻在尋食過程中，會在所經(jīng)過的路徑上留下一定濃度的信息素，當下次螞蟻經(jīng)過時，會判斷信息素的濃度，以判斷到達食物的最短路徑.從螞蟻尋食過程可以看出，螞蟻表現(xiàn)出一種存在信息正反饋傾向，也就是某一路徑經(jīng)過的螞蟻越多，信息素濃度也就越強，則后面選擇該路徑的概率越大，是一種用來在圖中尋找優(yōu)化路徑的機率型算法.

蟻群算法最早被應用在旅行商問題（TSP）的求解中，在蟻群算法中，每個經(jīng)過路徑的螞蟻都要根據(jù)當前路徑狀態(tài)選擇下一跳的節(jié)點，而路徑上的信息素依據(jù)全局更新規(guī)則進行更新.

說明：

（1）上式中△τ*表示精英螞蟻引起的路徑（i,j）上的信息素量的增加；

（2）σ是精英螞蟻的個數(shù)；

（3）L*是所找出的最優(yōu)解的路徑長度.

3 無線Mesh網(wǎng)路由算法模型

針對無線Mesh網(wǎng)的特點，設計路由算法，首先要考慮網(wǎng)絡中可能遇到的各種情況，所要數(shù)據(jù)有不同的需求，然后根據(jù)不同的情況和需求選擇最優(yōu)的路徑來完成數(shù)據(jù)的傳輸.

為說明問題，首先建立一個簡單的網(wǎng)絡模型：給定n個節(jié)點和兩兩節(jié)點間的距離，要求確定一條經(jīng)過各節(jié)點且每個節(jié)點只經(jīng)過一次的最短路線.圖論描述為G=（V,A），V節(jié)點集，A為邊集，已知各頂點間的連接距離，要求確定一個最短的Hamilton回路.

模擬現(xiàn)實網(wǎng)絡，作如下標記：

每個數(shù)據(jù)包都具有以下特征：在從節(jié)點i到節(jié)點j無能運動的過程中，數(shù)據(jù)包k在邊（i,j）上留下一定量的信息.

數(shù)據(jù)包概率地選擇下一個將要訪問的節(jié)點，這個概率是兩個節(jié)點間距離和兩個節(jié)點間路徑上存有的信息量的函數(shù).

bi（t）：t時刻位于節(jié)點 i的包數(shù)

dij：兩節(jié)點i和j之間的距離.

ηij：邊（i,j）的能見度，反映由節(jié)點i轉移到節(jié)點j的啟發(fā)程度，這個量在系統(tǒng)的運行中是不變的.

τij：邊（i,j）上的信息素軌跡強度.

△τij：包k在邊（i,j）上留下的單位信息長度軌跡信息素量.

pkij：包k的轉移概率，j是尚未訪問的節(jié)點.

為了滿足問題的約束條件，在完成一次循環(huán)后，不允許數(shù)據(jù)包選擇已經(jīng)訪問過的路徑，基于以上模型，用蟻群算法（ANT）來實現(xiàn).

4 基于蟻群的無線Mesh網(wǎng)絡路由算法設計

初始時刻，由于每條路徑上的信息量是相同的，不妨設τij=C（C為為常），螞蟻k（k=1,2,3…）在運動過程中的轉移方向取決于路徑上的信息量.依據(jù)隨機比例規(guī)則，可以確定螞蟻k從節(jié)點i到j的轉移概率.在t時刻螞蟻k在節(jié)點i選擇節(jié)點j的轉移概率為pkij（t），如圖2所示.

圖2 蟻群算法模型方程1

其中，allowedk={0,1,2,3…,n-1}表示螞蟻k下一步可以選擇的節(jié)點.依據(jù)方程 1 可知，概率 pkij（t）與 ταij*ηβij成正比.α為信息啟發(fā)因子，β為期望啟發(fā)式因子，分別反映了螞蟻在運動過程中所積累的信息和啟發(fā)信息在螞蟻選擇路徑中的相對重要性，ηij為能見度因數(shù).但與真實蟻群的區(qū)別在于人工蟻群系統(tǒng)具有記憶功能.為了滿足約束條件（即螞蟻必須經(jīng)過所有n個不同的節(jié)點），為每只螞蟻都設計了一個禁忌表（tabu list），禁忌表記錄了在t時刻螞蟻已經(jīng)走過的節(jié)點，且在本次循環(huán)中該螞蟻不走重復節(jié)點.在本次循環(huán)結束后，禁忌表被用來計算該螞蟻所經(jīng)過的路徑長度.之后，清空禁忌表，該螞蟻可再次進行自由地選擇.

經(jīng)過n個時刻，螞蟻完成一次循環(huán)，各路徑上信息量依據(jù)方程2進行調(diào)整，如圖3所示.

圖3 蟻群算法模型方程2

其中，△τkij（t,t+1）表示第k只螞蟻在時刻（t,t+1）留在路徑（i,j）上的信息素濃度，其值取決于螞蟻表現(xiàn)的優(yōu)劣程度.ρ（0<ρ<1）為信息素的揮發(fā)系數(shù)，能夠避免路徑上軌跡量的無限累加.

根據(jù)具體算法的不同，△τij，△τkij及 pkij的表達式形式允許不同，要依據(jù)具體情況而定.

5 總結

無線Mesh網(wǎng)絡是一種新型的寬帶無線網(wǎng)絡結構，是非常有前途的一種無線接入技術，文本簡單介紹了無線Mesh的基本原理及其發(fā)展，然后對蟻群算法進行了概述，鑒于蟻群算法具有自組織優(yōu)點，提出基于蟻群的無線Mesh網(wǎng)絡路由算法，并建立算法模型.

〔1〕劉美茹，程世杰.C++程序設計教程[M].哈爾濱:哈爾濱工業(yè)大學出版社,2005.

〔2〕方旭明，等.下一代無線因特網(wǎng)技術[M].北京:人民郵電出版社,2006.

〔3〕鄭相全.無線自組網(wǎng)技術實用教程[M].北京:清華大學出版社，2004.

〔4〕張會霞.基于Wireless Mesh技術的寬帶無線接入系統(tǒng)[J].現(xiàn)代電信科技,2003,（12）:29-30.

〔5〕宋文,方旭明.無線網(wǎng)格網(wǎng)絡技術及其應用[C]//2004西南交通大學研究生學術論壇論文集，2004.1-8.

〔6〕Ian F.Akyildiz,Xudong Wang.A Survey on WirelessMesh Networks[J].IEEE Radio Communications.2005,43（9）:s23-s30.

〔7〕Fowlers T P.Mesh networks for broadband access[J].IEE Review,2001,47（1）:17-22.

TP302

A

1673-260X（2012）09-0028-02