蔣麗麗，陳國彬，張廣泉

(1.重慶工商大學(xué) 融智學(xué)院，重慶400033;2.蘇州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 蘇州215006;3.中國科學(xué)院 計(jì)算機(jī)科學(xué)國家重點(diǎn)實(shí)驗(yàn)室，北京100080)

0 引 言

無線網(wǎng)狀網(wǎng)(wireless mesh network，WMN)［1，2］是因特網(wǎng)的一種無線版本，具有較強(qiáng)的擴(kuò)展性和兼容性，是一種新型的寬帶無線網(wǎng)絡(luò)，同時(shí)，具有無中心、多跳路由、自組織的特性，是一種高容量、高速率的分布式網(wǎng)絡(luò)。WMN 能夠很好地與其它無線網(wǎng)絡(luò)結(jié)合，使無線接入系統(tǒng)變得更加方便、快捷，從而使運(yùn)行成本大大降低，有效地提高了無線接入系統(tǒng)的帶寬容量和通信的可靠性。目前，以何種路由協(xié)議運(yùn)行才能使WMN 在所工作的環(huán)境中達(dá)到性能最優(yōu)是WMN路由協(xié)議所要考慮的關(guān)鍵問題。

由于WMN 的網(wǎng)絡(luò)拓?fù)浜凸?jié)點(diǎn)特性與Ad Hoc 網(wǎng)絡(luò)類似，因此，最初的WMN 路由協(xié)議沿用了Ad Hoc 網(wǎng)絡(luò)現(xiàn)有的一些路由協(xié)議，如Ad Hoc 按需距離矢量(Ad Hoc on－demand distance vector，AODV)，動(dòng)態(tài)源路由(dynamic source routing，DSR)協(xié)議，目的序列距離矢量(destination sequenced distance vector，DSDV)協(xié)議等［3～5］。然而，上述協(xié)議都是試圖找到一條當(dāng)前最優(yōu)路徑，然后沿這一路徑進(jìn)行通信。由于無線信道的不可靠性和不可預(yù)知性而使得通信鏈路質(zhì)量變化較大，可能當(dāng)前所選的最優(yōu)路徑在下一時(shí)刻已經(jīng)不是最優(yōu)，甚至性能變得很差，導(dǎo)致吞吐量下降，從而不能夠保證通信質(zhì)量。傳統(tǒng)的基于最優(yōu)路徑的路由機(jī)制被證明只適合于鏈路質(zhì)量可靠的有線網(wǎng)絡(luò)，而并不能夠適應(yīng)于丟包率高、鏈路狀況不穩(wěn)定的無線網(wǎng)絡(luò)［6］。

從WMN 的網(wǎng)絡(luò)特點(diǎn)來看，其與蟻群算法系統(tǒng)的特征有非常相似之處，蟻群算法可以較好地適應(yīng)動(dòng)態(tài)網(wǎng)絡(luò)環(huán)境。但該算法容易出現(xiàn)過早收斂和后期搜索效率降低的現(xiàn)象［7］。

為此，本文提出了一種基于螞蟻模擬退火(ant simulated annealing，ASA)混合算法的WMN 路由算法，它結(jié)合了蟻群優(yōu)化(ant colony optimization，ACO)算法搜索速度快和模擬退火(simulated annealing，SA)算法所具有的概率突跳特性，通過SA 來進(jìn)一步調(diào)整路由發(fā)現(xiàn)算法，克服了ACO算法在收斂速度上的缺陷，同時(shí)避免了因搜索方向問題導(dǎo)致的停滯現(xiàn)象的發(fā)生。

1 蟻群算法與SA 算法分析

1.1 ACO 算法分析

意大利學(xué)者Dorigo M 等人［8］從螞蟻群體的覓食行為中得到啟發(fā)，于1991 年，提出了人工蟻群算法，一種模擬自然界蟻群行為的模擬進(jìn)化算法。該算法實(shí)際上是進(jìn)化算法中的一種新型啟發(fā)式算法，融合了分布式計(jì)算、信息的正反饋以及啟發(fā)式搜索的功能。起初它主要是為了解決旅行商問題(TSP)，后來Kwang M S 等人［9］將蟻群算法應(yīng)用到網(wǎng)絡(luò)路由中去，并稱這種算法為Antnet。

WMN 的路由發(fā)現(xiàn)問題與蟻群尋路的問題有很大的相似性，都是尋找可以到達(dá)目的地的最優(yōu)路線。在蟻群算法中，螞蟻選擇下一個(gè)跳節(jié)點(diǎn)依據(jù)的是狀態(tài)轉(zhuǎn)移規(guī)則，而信息素值則根據(jù)全局更新規(guī)則來計(jì)算。

1)信息素值全局更新規(guī)則:從m 只螞蟻的覓食行動(dòng)中，選出尋覓路徑最大的來對(duì)全局的信息素進(jìn)行更新。若i，j 為兩個(gè)相鄰的節(jié)點(diǎn)，則鏈路(i，j)上的信息素更新可表示為

式中 信息素的揮發(fā)系數(shù)為ρ(0 ＜ρ ＜1);Δti，j為螞蟻尋覓過程中在鏈路(i，j)上留下的最優(yōu)路徑信息素

式中 Q 為最初的常數(shù)值，F(xiàn)k為此次周游的最優(yōu)路徑值。

2)狀態(tài)轉(zhuǎn)移規(guī)則:螞蟻在尋徑過程中在節(jié)點(diǎn)i 處選擇下一跳節(jié)點(diǎn)j 的概率為Pij

式中 U={0，1，…，n－1}為螞蟻下一跳可能選擇的所有節(jié)點(diǎn);ηi，j為啟發(fā)因子，表示選擇節(jié)點(diǎn)j 的傾向性，而控制參數(shù)α，β，ρ，η 影響著算法的收斂速度，其自身的選取也與網(wǎng)絡(luò)本身有關(guān)，也即是不同的網(wǎng)絡(luò)對(duì)應(yīng)的參數(shù)組合是不同的。

1.2 SA 算法分析

Metropolis 最早提出了SA 算法的思想，Kirkpatrick 等人在1983 年將其用于組合優(yōu)化。SA 算法是以物理退火過程與組合優(yōu)化之間的相似性為基礎(chǔ)的，從某一個(gè)較高的初溫開始，隨著溫度的不斷降低，固體內(nèi)部粒子也由無序狀漸趨于有序，在每個(gè)溫度都達(dá)到基態(tài)，最后在常溫時(shí)達(dá)到基態(tài)，內(nèi)能減為最小。根據(jù)Metropolis 準(zhǔn)則，重復(fù)抽樣過程，最終得到問題的全局最優(yōu)解［10］。

2 基于蟻群算法優(yōu)化SA 的WMN 路由算法

2.1 算法設(shè)計(jì)思想

采用蟻群算法容易產(chǎn)生早熟現(xiàn)象，多個(gè)螞蟻個(gè)體可能趨于相同的解，致使網(wǎng)絡(luò)流量集中在某些路徑上而導(dǎo)致負(fù)載不均衡［11，12］。SA 算法具有很強(qiáng)的局部搜索能力，它實(shí)質(zhì)上是利用鄰域解增加解的多樣性，即不斷地在當(dāng)前解的鄰域中找出一個(gè)適合解替代當(dāng)前解的過程，將其引入蟻群算法中可改進(jìn)當(dāng)前解，對(duì)每代螞蟻生成的解進(jìn)行處理，當(dāng)蟻群算法出現(xiàn)一定的迭代次數(shù)的停滯現(xiàn)象時(shí)，則對(duì)全局的最優(yōu)解進(jìn)行變更同時(shí)進(jìn)行變更路徑信息素的交換，這就可以保持種群的有效多樣性，有效地避免局部最優(yōu)。

2.2 算法描述

將WMN 抽象為圖G(V，E)，其中，V 為圖G 的節(jié)點(diǎn)集，元素v∈V 為圖G 的一個(gè)節(jié)點(diǎn)，E 為圖G 的邊集，元素ei，j∈E 為圖G 的一條從vi到vj的邊，令集合Ni∈V 為節(jié)點(diǎn)vi的鄰居節(jié)點(diǎn)集。在WMN 中，由于有部分節(jié)點(diǎn)的失效、新增或是休眠，集合V，E，Ni則可以看成是變化的。在圖G 中，若對(duì)i=1，2，…，k－1 有ei，i+1∈E，則P=(v1，v2，…，vk)為圖G的一條從vi到vk的路徑。路徑P 的度量需要通過如下度量來實(shí)現(xiàn):節(jié)點(diǎn)的負(fù)載接納率為Ql，節(jié)點(diǎn)的拓?fù)鋭?dòng)態(tài)率為Qt。令端到端時(shí)延為Qd。其中，Ql，Qt是可乘性度量，Qd是可加性度量。在算法中，每個(gè)節(jié)點(diǎn)的路由表由信息素表來代替。此算法對(duì)螞蟻進(jìn)行了三種分組，分別為前向螞蟻(forward ant，F(xiàn)A)和后向螞蟻(backward ant，BA)以及告警螞蟻(warning ant，WA)，其分別用于路由的發(fā)現(xiàn)和對(duì)擁塞斷裂的通知。

2.3 算法實(shí)施步驟

ASA 算法運(yùn)行的具體步驟如下:

1)初始化:令初始化網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)的信息素初始值為0，路由選擇算法對(duì)系統(tǒng)中的各節(jié)點(diǎn)都適用。

2)源節(jié)點(diǎn)廣播FA:為保證FA 能反映數(shù)據(jù)包的傳輸延時(shí)，F(xiàn)A 能與數(shù)據(jù)包以相同的優(yōu)先級(jí)發(fā)送。將FA 中的Ql，Qt都設(shè)置為1，而Qd設(shè)為0，記錄FA 所經(jīng)過的節(jié)點(diǎn)Qn為空。

3)中間節(jié)點(diǎn)收到FA 后，根據(jù)Qn判斷是否出現(xiàn)環(huán)路，出現(xiàn)，則丟棄;如果沒出現(xiàn)環(huán)路，則根據(jù)節(jié)點(diǎn)的WA 判斷是否可以接納FA。如果拒絕，F(xiàn)A 死亡;如果接納，則根據(jù)Seq判別接納的FA 是否為來自不同路徑的重復(fù)分組，若為重復(fù)分組，則丟棄;若是非重復(fù)分組，則按下式更新或建立本節(jié)點(diǎn)到FA 源節(jié)點(diǎn)的信息素表

4)當(dāng)FA 傳送到目的節(jié)點(diǎn)后，目的節(jié)點(diǎn)會(huì)首先建立其與源節(jié)點(diǎn)之間的信息素表，然后將產(chǎn)生BA 沿原路送回到源節(jié)點(diǎn)。這期間收到BA 的中間節(jié)點(diǎn)會(huì)依據(jù)所記錄的信息重新建立到目的節(jié)點(diǎn)的信息素表。當(dāng)BA 到達(dá)源節(jié)點(diǎn)后，也即是建立了一條完整的路徑。

5)當(dāng)本次循環(huán)超時(shí)，調(diào)用SA 局部?jī)?yōu)化算法:在溫度Tk下進(jìn)行當(dāng)前解領(lǐng)域的鄰域探索，從而產(chǎn)生新的可行解。用能量函數(shù)評(píng)價(jià)信息素表中的可行路徑，在SA 過程中，解的接收概率將服從Boltzmann 概率分布。

3 仿真實(shí)驗(yàn)與性能分析

目前，為了檢驗(yàn)協(xié)議的負(fù)載均衡效果，本文主要從分組成功遞交率、平均端到端延時(shí)數(shù)據(jù)丟失率以及附加開銷等方面對(duì)路由協(xié)議的性能進(jìn)行評(píng)估。使用軟件NS2 對(duì)ASA算法、ANT 算法和AODV 協(xié)議的性能進(jìn)行比較的仿真結(jié)果如圖1～圖3 所示。

仿真參數(shù)設(shè)置為:MAC 層采用的是IEEE 802.11DCF，帶寬為2 Mbps，有40 個(gè)節(jié)點(diǎn)在1000 m×1000 m 區(qū)域內(nèi)隨機(jī)的移動(dòng)，移動(dòng)的速度也均勻的分布在0～20 m/s 間，以不同的停頓時(shí)間分別表示網(wǎng)絡(luò)不同分布和網(wǎng)絡(luò)不同的移動(dòng)性。節(jié)點(diǎn)間的直線通信距離為250 m，仿真中使用了20 個(gè)源節(jié)點(diǎn)，而目的節(jié)點(diǎn)則是從其余的網(wǎng)絡(luò)節(jié)點(diǎn)中隨機(jī)的選取的，令每個(gè)小組的數(shù)據(jù)凈荷都為512 字節(jié)。從圖1、圖2 可看出:ASA 比ANT 和AODV 對(duì)于動(dòng)態(tài)網(wǎng)絡(luò)具有更好的適應(yīng)穩(wěn)健性，當(dāng)然，對(duì)于網(wǎng)絡(luò)拓?fù)鋭?dòng)態(tài)變化影響的適應(yīng)也明顯優(yōu)于后者。

圖1 分組投遞率Fig 1 Packet delivery ratio

圖2 平均端到端延時(shí)數(shù)據(jù)丟失率Fig 2 Average end to end delay data loss rate

在拓?fù)浣Y(jié)構(gòu)變化頻繁的情況下，路徑容易中斷，而ASA可在一次路由發(fā)現(xiàn)過程中找出多條信息素路徑，即使鏈路發(fā)生中斷，仍可以啟用備用的路由。這就大大地降低了因路由中斷必須重新建立路由而產(chǎn)生的大量的控制開銷，所以，圖3 表明ASA 獲得最低的控制開銷。

圖3 路由開銷Fig 3 Routing overhead

4 結(jié) 論

在ACO 算法的基礎(chǔ)上，本文提出了一種基于ASA 混合算法的WMN 路由算法，它結(jié)合了ACO 搜索速度快和SA 所具有的概率突跳特性，通過SA 來進(jìn)一步調(diào)整路由發(fā)現(xiàn)算法，克服了ACO 算法在收斂速度上的缺陷，提高了算法的啟發(fā)性，拓寬了搜索范圍，避免了搜索過程中停滯現(xiàn)象的發(fā)生。通過仿真實(shí)驗(yàn)對(duì)ASA、僅基于蟻群算法的路由算法和傳統(tǒng)的按需路由算法的方法進(jìn)行了性能比較，結(jié)果表明:在WMN 環(huán)境下，ASA 算法在數(shù)據(jù)包投遞率、端到端延時(shí)數(shù)據(jù)丟失率和歸一化路由開銷等網(wǎng)絡(luò)性能上均表現(xiàn)出更好的適應(yīng)性。

［1］ Bruno R，Conti M，Gregori E.Mesh networks:Commodity multihop Ad Hoc networks［J］.IEEE Communications Magazine，2012，43(3):123－131.

［2］ 羅云月，孫志峰.基于自適應(yīng)蟻群優(yōu)化算法的認(rèn)知決策引擎［J］.計(jì)算機(jī)科學(xué)，2011，38(8):253－256.

［3］ 劉 佳，劉麗娜，李 靖，等.基于模擬退火算法的改進(jìn)人工魚群算法［J］.計(jì)算機(jī)仿真，2010，28(10):195－198.

［4］ 李芳芳，王 靖.基于模擬退火算法的無線傳感器網(wǎng)絡(luò)最優(yōu)簇類求解方案［J］.傳感技術(shù)學(xué)報(bào)，2011，24(6):900－904.

［5］ Stelano M F，Wijting C，Kneckt J.Mesh WLAN networks:Concept and system design［J］.IEEE Wireless Communication，2013，13(2):10－17.

［6］ 王 珺，曹涌濤，糜正琨.無線傳感器網(wǎng)絡(luò)Mobile Agent 路由問題的模擬退火解法［J］.南京郵電大學(xué)學(xué)報(bào):自然科學(xué)版，2012，27(1):64－68.

［7］ 肖樂樂，蔡樂才，李 鵬.改進(jìn)的蟻群算法在移動(dòng)Agent 遷移中的應(yīng)用研究［J］.四川大學(xué)學(xué)報(bào):自然科學(xué)版，2011，27(1):41－44.

［8］ Dorigo M，Gambardella L M.Ant colony system:A cooperative learning approach to the traveling salesman problem［J］.IEEE Transactions on Evolutionary Computation，1997，1(1):53－66.

［9］ Kwang M S，Weng H S.Ant colony optimization for routing and load balancing:Survey and new directions［J］.IEEE Transactions on Systems，Man and Cybernetics:Part A，2013，33(5):560－572.

［10］Li B L，Li Z S，Zhang J Y.An automated test case generation approach by genetic simulated annealing algorithm［C］∥The 3rd International Conference on Natural Computation，Haikou，China，2011:106－111.

［11］王正成，鏈構(gòu)建，潘曉弘，等.基于蟻群算法的網(wǎng)絡(luò)化制造資源服務(wù)［J］.計(jì)算機(jī)集成制造系統(tǒng)，2010，16(1):174－181.

［12］王水貴，韓瑞蓮.基于改進(jìn)蟻群算法的云環(huán)境任務(wù)調(diào)度研究［J］.計(jì)算機(jī)測(cè)量與控制，2011，19(5):1203－1204.