武玉坤

摘要：為了提高無(wú)線Mesh 網(wǎng)絡(luò)（WMN） 的傳輸性能，提出基于擁塞規(guī)避的路由算法來(lái)優(yōu)化WMN網(wǎng)關(guān)負(fù)載均衡問(wèn)題。蟻群算法中選用路徑選擇概率與信息素濃度呈反比的規(guī)則，同時(shí)引入增減調(diào)整因子進(jìn)行信息素的更新策略。實(shí)驗(yàn)結(jié)果驗(yàn)證，該算法有效避免了WMN網(wǎng)絡(luò)擁塞，使網(wǎng)絡(luò)負(fù)載得以均衡。

關(guān)鍵詞：無(wú)線Mesh網(wǎng)； 蟻群算法；擁塞規(guī)避；服務(wù)質(zhì)量

中圖分類(lèi)號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2015）07-0065-04

Abstract： In order to improve the Wireless Mesh Network （WMN） transmission performance， the paper proposes routing congestion avoidance algorithm to optimize the WMN gateway load. Ant colony algorithm adopts the rules of path selection probability being inversely proportional pheromone concentration， while adjustment factor is introducted to update pheromone. Experimental results show that the algorithm can effectively avoid the WMN network congestion and the load can be balanced.

Key words： Wireless mesh network（WMN） ； Ant Colony Algorithm（ACA）； congestion avoidance； Quality of Service（QoS）

1 引言

無(wú)線Mesh網(wǎng)是在移動(dòng)自組織網(wǎng)絡(luò)基礎(chǔ)上發(fā)展起來(lái)的一種無(wú)線多跳網(wǎng)絡(luò)。具有自組網(wǎng)、自管理、高速率、性能穩(wěn)定等優(yōu)勢(shì)，能夠?yàn)橛脩?hù)提供高速的無(wú)線接入服務(wù)，已成為移動(dòng)通信領(lǐng)域的研究熱點(diǎn)[1]。在兩個(gè)節(jié)點(diǎn)之間設(shè)計(jì)一個(gè)高質(zhì)量，高效率通信的路由協(xié)議是WMN路由協(xié)議研究的一個(gè)熱點(diǎn)問(wèn)題，又因?yàn)閃MN承載多種多媒體應(yīng)用與實(shí)時(shí)任務(wù)，故保證QoS顯得尤為重要。已有大量學(xué)者對(duì)WMN中QoS路由算法做了研究：如王霄等提出的基于改進(jìn)蟻群算法的無(wú)線Mesh網(wǎng)QoS路由算法研究[2]，劉楓等無(wú)線MESH網(wǎng)中基于蟻群算法的多約束QoS路由研究[3]；但這些算法只考慮了其可行性以及對(duì)路由的優(yōu)化，沒(méi)考慮到網(wǎng)絡(luò)擁塞的情況，由于WMN中大部分采用最短路徑的路由算法，導(dǎo)致WMN中心區(qū)域的路由器很容易產(chǎn)生擁塞。針對(duì)WMN中QoS路由特點(diǎn)，本文對(duì)蟻群算法進(jìn)行改進(jìn)后應(yīng)用在WMN的QoS路由優(yōu)化中，仿真實(shí)驗(yàn)驗(yàn)證該算法能夠有效解決上述擁塞狀況。

2 WMN的QoS路由模型

2.1 網(wǎng)絡(luò)拓?fù)淠Ｐ?/p>

WMN架構(gòu)如圖1所示，架構(gòu)中通常包含Mesh路由器和Mesh客戶(hù)機(jī)兩種節(jié)點(diǎn)。

（1） Mesh路由器

Mesh路由器間通過(guò)互聯(lián)形成Mesh網(wǎng)，構(gòu)成整個(gè)網(wǎng)絡(luò)的骨干，Mesh路由器位置一般是固定的，且有電源供應(yīng)，部分Mesh路由器具有網(wǎng)關(guān)/網(wǎng)橋功能，為用戶(hù)提供高速的網(wǎng)絡(luò)接入。WMN中的Mesh路由器可以收集全網(wǎng)信息，為在實(shí)現(xiàn)Mesh網(wǎng)QoS 路由中運(yùn)用蟻群算法提供了保障。

（2） Mesh客戶(hù)端

Mesh客戶(hù)端可分為固定節(jié)點(diǎn)（如臺(tái)式機(jī)）和移動(dòng)節(jié)點(diǎn)（平板電腦、智能手機(jī)等）。和Mesh 路由器節(jié)點(diǎn)不同的是不具備網(wǎng)關(guān)和網(wǎng)橋的功能，具有簡(jiǎn)單的硬軟件平臺(tái)。與Mesh 路由器進(jìn)行通信采用多跳方式。移動(dòng)節(jié)點(diǎn)靠電池供電，受能源限制較大。

2.2 WMN的QoS 數(shù)學(xué)模型

在求解可乘性度量的過(guò)程中，可以參照可加性度量的有關(guān)求解方法，故本文只考慮延時(shí)與帶寬這兩種可加性度量和最小性度量。WMN中QoS路由的目標(biāo)就是選擇一條從源節(jié)點(diǎn)S到目標(biāo)節(jié)點(diǎn)d的最優(yōu)路徑，使之滿(mǎn)足業(yè)務(wù)的QoS要求，同時(shí)最大化網(wǎng)絡(luò)利用率。

3 蟻群算法的改進(jìn)

3.1算法的設(shè)計(jì)思想與實(shí)現(xiàn)規(guī)則

蟻群算法應(yīng)用于網(wǎng)絡(luò)QoS 路由時(shí)，數(shù)據(jù)包代表螞蟻，路徑上的路由表視作螞蟻留下的信息素，以概率值來(lái)表示表中的信息素濃度，要求路由節(jié)點(diǎn)維持一個(gè)路由表。在傳統(tǒng)蟻群算法中，信息素的多少能夠影響螞蟻的決策，選擇某一路徑的螞蟻越多，信息素就會(huì)越多，此路徑對(duì)下一只螞蟻就變得越有吸引力。信息素的累積過(guò)程構(gòu)成了一種正向反饋，正反饋的過(guò)程引導(dǎo)著整個(gè)系統(tǒng)向著最優(yōu)解的方向進(jìn)化，盡快找到最優(yōu)路徑。

本文針對(duì)WMN中擁塞的特點(diǎn)對(duì)蟻群算法進(jìn)行如下改進(jìn)：采用路徑被選擇概率與信息素濃度與呈反比的原則；同時(shí)通過(guò)引入增減調(diào)整因子來(lái)進(jìn)行信息素的更新。

3.2 轉(zhuǎn)移概率公式

5 實(shí)驗(yàn)仿真分析

由于網(wǎng)絡(luò)擁塞主要是由網(wǎng)絡(luò)中丟棄的數(shù)據(jù)包引起的，故本文用平均時(shí)延和網(wǎng)絡(luò)丟包率來(lái)對(duì)改進(jìn)的路由算法進(jìn)行評(píng)價(jià)。

WMN中的Mesh路由器在10個(gè)左右即可滿(mǎn)足實(shí)際應(yīng)用需求，本文選取如圖2所示的由13個(gè)節(jié)點(diǎn)組成的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖進(jìn)行仿真實(shí)驗(yàn)，鏈路的QoS約束用二元組（寬帶，延時(shí)）描述，各條鏈路的寬帶以及延時(shí)在圖中標(biāo)出。

從仿真結(jié)果可以看出，改進(jìn)的蟻群算法拓寬了螞蟻搜尋更多其他的路徑，豐富了解空間；當(dāng)網(wǎng)絡(luò)發(fā)生擁塞后，信息素更新規(guī)則使其他螞蟻選擇該路徑的幾率大大降低，避開(kāi)了網(wǎng)絡(luò)中的擁塞路徑，使網(wǎng)絡(luò)負(fù)載得到均衡，同時(shí)網(wǎng)絡(luò)丟包率和數(shù)據(jù)包的平均傳輸時(shí)延都大大降低。實(shí)驗(yàn)證明本文算法對(duì)規(guī)避WMN中的網(wǎng)絡(luò)擁塞是可行、有效的。

6 結(jié)束語(yǔ)

本文通過(guò)對(duì)傳統(tǒng)蟻群算法中概率轉(zhuǎn)移公式的反用，引入信息素的增減調(diào)整因子，對(duì)蟻群算法進(jìn)行了改進(jìn)。改進(jìn)后的算法仿真實(shí)驗(yàn)表明，該算法能夠有效避免網(wǎng)絡(luò)中的擁塞路徑，均衡網(wǎng)絡(luò)負(fù)載；具有有明顯的優(yōu)越性。

參考文獻(xiàn)：

[1] 姜紅旗，康凱，林孝康.拓展寬帶接入的無(wú)線Mesh網(wǎng)技術(shù)[J].電信科學(xué)，2005，1：24-30.

[2] 王霄，吳開(kāi)軍.基于改進(jìn)蟻群算法的無(wú)線Mesh網(wǎng)QoS路由算法研究[J].計(jì)算機(jī)系統(tǒng)應(yīng)用，2011，20（7）：111-115.

[3] 劉楓，全惠云，肖偉.無(wú)線MESH網(wǎng)中基于蟻群算法的多約束QoS路由研究[J].計(jì)算機(jī)工程與應(yīng)用，2008，44（13）：122-125.

[4] 古明家，宣士斌，廉侃超.基于自適應(yīng)變異蟻群算法的QoS路由算法[J].計(jì)算機(jī)工程，2009，35（23）： 209-211.

[5] 馬良，朱剛.寧愛(ài)兵.蟻群優(yōu)化算法[M].北京：科學(xué)出版社，2008.

[6] 趙有健，張鐵蕾，崔 勇.多約束服務(wù)質(zhì)量路由中的路徑壓縮算法[J].計(jì)算機(jī)學(xué)報(bào)，2007，30（12）： 2090-2100.

[7] 謝玉城，李陶深，葛志輝基于用戶(hù)QoS分析的無(wú)線Mesh網(wǎng)絡(luò)部署優(yōu)化[J].計(jì)算機(jī)技術(shù)與發(fā)展，2014（1） ：54-56

[8] 吳文甲，楊明，羅軍舟.無(wú)線Mesh網(wǎng)絡(luò)中滿(mǎn)足帶寬需求的路由器部署方法[J].計(jì)算機(jī)學(xué)報(bào)，2014（2） ： 344-355.

[9] 楊云，徐永紅，李千目.一種QoS 路由多目標(biāo)遺傳算法[J].軟件學(xué)報(bào)，2004，25（1） ： 43- 51.

[10] 王姍姍.基于蟻群算法的無(wú)線傳感器網(wǎng)絡(luò)路由技術(shù)研究[D].長(zhǎng)春理工大學(xué)，2013.