張千里

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

基于蟻群的Mesh網(wǎng)絡(luò)路由算法模型的設(shè)計(jì)

張千里

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

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

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

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

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

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

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

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

2 蟻群算法概述

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

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

說(shuō)明：

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

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

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

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

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

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

模擬現(xiàn)實(shí)網(wǎng)絡(luò)，作如下標(biāo)記：

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

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

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

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

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

τij：邊（i,j）上的信息素軌跡強(qiáng)度.

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

pkij：包k的轉(zhuǎn)移概率，j是尚未訪問(wèn)的節(jié)點(diǎn).

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

4 基于蟻群的無(wú)線Mesh網(wǎng)絡(luò)路由算法設(shè)計(jì)

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

圖2 蟻群算法模型方程1

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

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

圖3 蟻群算法模型方程2

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

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

5 總結(jié)

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

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

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

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

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

〔5〕宋文,方旭明.無(wú)線網(wǎng)格網(wǎng)絡(luò)技術(shù)及其應(yīng)用[C]//2004西南交通大學(xué)研究生學(xué)術(shù)論壇論文集，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