改進(jìn)蟻群算法在WSN路由優(yōu)化中的應(yīng)用*

李 鋒

（廣東交通職業(yè)技術(shù)學(xué)院，廣州510650）

·微機(jī)網(wǎng)絡(luò)與通信·

改進(jìn)蟻群算法在WSN路由優(yōu)化中的應(yīng)用*

李 鋒

（廣東交通職業(yè)技術(shù)學(xué)院，廣州510650）

無線傳感網(wǎng)絡(luò)是一種由大量傳感節(jié)點(diǎn)構(gòu)成的分布式網(wǎng)絡(luò)系統(tǒng)，節(jié)點(diǎn)與節(jié)點(diǎn)之間通過彼此交換狀態(tài)信息以發(fā)現(xiàn)和維護(hù)路由，組成統(tǒng)一網(wǎng)絡(luò)。針對目前無線傳感網(wǎng)絡(luò)路由協(xié)議的不足，提出基于視野極值的改進(jìn)蟻群路由算法，并通過信息素局部更新避免全部螞蟻選擇相同路徑，算法提前收斂的問題。仿真實(shí)驗(yàn)證明，新算法具有正反饋、全局收斂和動態(tài)適應(yīng)等優(yōu)點(diǎn)，能很好適應(yīng)無線傳感網(wǎng)絡(luò)節(jié)點(diǎn)隨機(jī)分布，節(jié)點(diǎn)頻繁加入和死亡的現(xiàn)象。

無線傳感網(wǎng)絡(luò)；蟻群算法；路由協(xié)議；無線自組織網(wǎng)絡(luò)；傳感節(jié)點(diǎn)；匯聚節(jié)點(diǎn)

1 引 言

無線傳感網(wǎng)絡(luò)是一種由大量傳感節(jié)點(diǎn)構(gòu)成的分布式網(wǎng)絡(luò)系統(tǒng)，由傳感節(jié)點(diǎn)、匯聚節(jié)點(diǎn)和管理節(jié)點(diǎn)組成，見圖1。傳感節(jié)點(diǎn)感知目標(biāo)信息后以多跳接力方式傳給匯聚節(jié)點(diǎn)，匯聚節(jié)點(diǎn)對附近傳感節(jié)點(diǎn)信息匯總后通過衛(wèi)星基站、互聯(lián)網(wǎng)傳送給管理用戶［1－2］。

無線傳感網(wǎng)絡(luò)一般應(yīng)用于惡劣環(huán)境或是人無法抵達(dá)的區(qū)域。由于節(jié)點(diǎn)數(shù)量繁多，并且無法精準(zhǔn)定位，傳感節(jié)點(diǎn)通常采用隨機(jī)散播方式部署，節(jié)點(diǎn)與節(jié)點(diǎn)之間通過彼此交換狀態(tài)信息以發(fā)現(xiàn)和維護(hù)路由，組成統(tǒng)一網(wǎng)絡(luò)。網(wǎng)絡(luò)層路由協(xié)議是WSN通信的基礎(chǔ)，是實(shí)現(xiàn)網(wǎng)絡(luò)可靠、有效傳輸?shù)年P(guān)鍵，既要考慮節(jié)點(diǎn)加入、移動和死亡過程，也要有一定的穩(wěn)定性、容錯性和擴(kuò)展性［3］。目前，業(yè)界針對無線傳感網(wǎng)絡(luò)不同應(yīng)用場合和需求研究出不同的路由協(xié)議。

2 無線傳感網(wǎng)絡(luò)路由協(xié)議

2．1 SPIN路由協(xié)議

SPIN（Sensor Protocols for Information via Negoti-ation）協(xié)議是一種自適應(yīng)路由協(xié)議。由于鄰居傳感節(jié)點(diǎn)感知的路由信息具有相似性，為減少數(shù)據(jù)傳輸冗余，節(jié)點(diǎn)只廣播其他節(jié)點(diǎn)沒有的路由信息，從而共同維護(hù)全網(wǎng)路由，降低節(jié)點(diǎn)能耗［4－5］。SPIN路由算法簡單，對發(fā)現(xiàn)新節(jié)點(diǎn)動作迅速，但對判斷死亡節(jié)點(diǎn)耗時較長，不適合用于節(jié)點(diǎn)頻繁加入和離開的場合。

圖1 WSN體系結(jié)構(gòu)

2．2 定向擴(kuò)散協(xié)議

定向擴(kuò)散協(xié)議（Directed Diffusion，DD）是以數(shù)據(jù)為中心的路由協(xié)議，匯聚節(jié)點(diǎn)周期性廣播路由興趣消息，通告整個網(wǎng)絡(luò)中其他節(jié)點(diǎn)所需路由。途經(jīng)節(jié)點(diǎn)通過建立反向梯度信息建立反向路徑，并將梯度信息傳至匯聚節(jié)點(diǎn)，由匯聚節(jié)點(diǎn)計算全網(wǎng)路由并返回給網(wǎng)絡(luò)中所有節(jié)點(diǎn)。在定向擴(kuò)散協(xié)議中，節(jié)點(diǎn)需要維護(hù)共同興趣路由消息，加上洪泛機(jī)制影響，路由代價和消耗較大，不適合應(yīng)用于大規(guī)模無線傳感網(wǎng)絡(luò)。

2．3 TTDD路由

TTDD（Two－Tier Data Dissemination）是針對網(wǎng)絡(luò)中眾多匯聚節(jié)點(diǎn)和匯聚節(jié)點(diǎn)移動問題所設(shè)計的路由協(xié)議。當(dāng)多個節(jié)點(diǎn)感知新的路由信息時，共同選擇中心節(jié)點(diǎn)作為源節(jié)點(diǎn)，由源節(jié)點(diǎn)計算相鄰交叉點(diǎn)位置，利用貪心算法請求鄰居節(jié)點(diǎn)成為新交叉點(diǎn)，新交叉點(diǎn)重復(fù)該過程直到網(wǎng)絡(luò)邊緣，從而構(gòu)成格狀網(wǎng)絡(luò)［6］。匯聚節(jié)點(diǎn)計算格狀網(wǎng)絡(luò)鄰近交叉點(diǎn)位置，而交叉點(diǎn)又保存了路由事件和源節(jié)點(diǎn)信息，匯聚節(jié)點(diǎn)通過泛洪廣播交叉節(jié)點(diǎn)坐標(biāo)，告知網(wǎng)絡(luò)中節(jié)點(diǎn)完整的路由信息。TTDD計算與維護(hù)格狀網(wǎng)開銷較大，節(jié)點(diǎn)必須知道自身位置否則無法計算路由信息，路由精度對節(jié)點(diǎn)密度依賴較高。

無線自組織網(wǎng)絡(luò)MANET（Mobile Ad Hoc Network）是一個由眾多節(jié)點(diǎn)組成的無線通信對等網(wǎng)絡(luò)，與無線傳感網(wǎng)絡(luò)相比十分接近，如節(jié)點(diǎn)能量有限，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)易變，部分路由協(xié)議相通等［7－8］。目前，無線自組織網(wǎng)絡(luò)已利用蟻群算法應(yīng)用于節(jié)點(diǎn)路由之中，通過信息素正向反饋機(jī)制找到全局最優(yōu)路徑。針對目前無線傳感網(wǎng)絡(luò)路由協(xié)議不足，提出基于視野極值的改進(jìn)蟻群路由算法，并應(yīng)用于無線傳感網(wǎng)絡(luò)路由協(xié)議之中。新算法具有分布式、正反饋、全局收斂和動態(tài)適應(yīng)等優(yōu)點(diǎn)，通過螞蟻間的協(xié)同工作可以有效減少搜索最優(yōu)路徑的復(fù)雜度。

3 標(biāo)準(zhǔn)蟻群算法

蟻群算法（Ant Colony Algorithm）是基于蟻群覓食行為提出的一種仿生算法［9］。每個螞蟻在覓食時在其所經(jīng)路徑分泌信息素進(jìn)行標(biāo)識，信息素會隨時間蒸發(fā)直至消失，后繼螞蟻根據(jù)信息素濃度選擇移動方向。路徑長度越短，信息素?fù)]發(fā)越少，信息素越濃，后繼螞蟻選擇幾率越大；反之，路徑越長，所經(jīng)時間越多，直至信息素?fù)]發(fā)殆盡，所選路徑被淘汰。大量螞蟻分泌的信息素構(gòu)成路徑選擇反饋機(jī)制，最終整個蟻群找到巢穴到食物之間的最優(yōu)路徑。算法模型如下：

（1）初始化節(jié)點(diǎn)和蟻群數(shù)量，蟻群隨機(jī)選擇路徑，直到抵達(dá)目的節(jié)點(diǎn)。

（2）每個節(jié)點(diǎn)存儲其鄰居節(jié)點(diǎn)通往目的節(jié)點(diǎn)的路徑開銷，后繼螞蟻根據(jù)路徑開銷值計算節(jié)點(diǎn)轉(zhuǎn)向概率。設(shè)節(jié)點(diǎn)i路徑開銷為Qi，其鄰居節(jié)點(diǎn)j的路徑開銷值為Qj，則對于節(jié)點(diǎn)i選擇下一節(jié)點(diǎn)j的轉(zhuǎn)向概率為：

（3）若螞蟻在t時刻探索路徑，在t＋1時刻選擇到下一路由，完成一次循環(huán)迭代，則在t＋1時刻節(jié)點(diǎn)i選擇節(jié)點(diǎn)j的信息素濃度增量將按照以下公式更新：

（4）螞蟻根據(jù)下一節(jié)點(diǎn)信息素濃度Tg選擇最優(yōu)路徑，概率為：

4 蟻群算法在WSN網(wǎng)絡(luò)中的應(yīng)用

蟻群算法通過單個螞蟻活動和協(xié)作完成路徑搜索，個體之間相互獨(dú)立，按照既定規(guī)則運(yùn)行，共同決定全局最優(yōu)路徑。這種自組織、自適應(yīng)、并行搜索和動態(tài)反饋機(jī)制能夠在最短時間內(nèi)找到全局最優(yōu)解。在無線自組織網(wǎng)絡(luò)中，節(jié)點(diǎn)鋪設(shè)成本較高，密度均勻，結(jié)構(gòu)相對穩(wěn)定，蟻群算法利用信息素反饋以適應(yīng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的微小變化。而在無線傳感網(wǎng)絡(luò)中，第一，節(jié)點(diǎn)會因?yàn)閺?fù)雜環(huán)境變化重啟和失效，節(jié)點(diǎn)加入和死亡更為頻繁，必須重新定義信息素轉(zhuǎn)移概率和揮發(fā)系數(shù)，否則螞蟻將花費(fèi)大量時間等待信息素更新；第二，節(jié)點(diǎn)成本低廉，一般采用空投方式部署，隨機(jī)性很大，節(jié)點(diǎn)分布極不均勻，此時基于跳數(shù)的路徑開銷會產(chǎn)生局部路徑計算不合理的問題，必須限制螞蟻每次行進(jìn)最大距離，即視野范圍；第三，信息素的正向反饋機(jī)制會促使所有螞蟻?zhàn)叩酵宦窂剑斐伤惴ㄟ^早收斂，找到的解是全局近優(yōu)解，此時必須在螞蟻抵達(dá)目的節(jié)點(diǎn)后對其所選路徑的信息素進(jìn)行局部更新，減少相同路徑信息素濃度值。綜上所述，改進(jìn)的蟻群算法在無線傳感網(wǎng)絡(luò)中應(yīng)用如下：

（1）初始化參數(shù)，定義蟻群數(shù)量n和螞蟻每次行進(jìn)距離P，P取值區(qū)間為：

其中Di－Sink是節(jié)點(diǎn)i到匯聚節(jié)點(diǎn)之間的距離，MaxRadius是螞蟻?zhàn)畲笸ㄐ虐霃健?/p>

（2）螞蟻在節(jié)點(diǎn)i選擇節(jié)點(diǎn)j的路徑轉(zhuǎn)移概率為：

其中P是式（5）的行進(jìn)距離，α和β是節(jié)點(diǎn)i和節(jié)點(diǎn)j各自權(quán)重。

（3）螞蟻根據(jù)轉(zhuǎn)移概率行進(jìn)至下一節(jié)點(diǎn)，完成一次循環(huán)迭代，信息素濃度更新如下式：

（4）螞蟻抵達(dá)目的節(jié)點(diǎn)后，利用式（9）對其所選路徑局部更新，減少相同路徑的信息素濃度，避免所有螞蟻收斂至同一路徑。

其中τ（i，j）是節(jié)點(diǎn)i選擇節(jié)點(diǎn)j的信息素跡量。

（5）重復(fù)步驟（3）和步驟（4），直到所有螞蟻都生成完整路徑。

（6）全部螞蟻根據(jù)式（10）更新全局信息素濃度。

（7）循環(huán)步驟（2）至步驟（6），每次迭代找出的路徑長度將越來越短，直至算法收斂獲得全局最優(yōu)解，或超出最大循環(huán)次數(shù)，此時算法終止。

5 仿真測試

定義傳感節(jié)點(diǎn)分布區(qū)域?yàn)?00*100，匯聚節(jié)點(diǎn)8個，均勻分布，其中匯聚節(jié)點(diǎn)⑧為根節(jié)點(diǎn)；傳感節(jié)點(diǎn)80個，隨機(jī)生成。初始化蟻群數(shù)量n為30，最大迭代次數(shù)200，α＝1．5，β＝1．7，ρ＝0．5，節(jié)點(diǎn)加入和死亡率分別為5%和8%，表1是四種算法的結(jié)果。從表1可以看出，SPIN算法簡單，能耗較低，但選擇的路徑長度偏大，并且判斷死亡節(jié)點(diǎn)耗時較長，導(dǎo)致節(jié)點(diǎn)失效率很高。DD和TTDD算法利用節(jié)點(diǎn)泛洪更新路由信息，節(jié)點(diǎn)能耗較大，并且全局最優(yōu)解與節(jié)點(diǎn)密度相關(guān)，路徑算法偏差較大。而新算法找出的路徑長度最短，路徑平均費(fèi)用最低，能量消耗也適中，能很好滿足無線傳感網(wǎng)絡(luò)的工程應(yīng)用需求。

表1 四種算法結(jié)果比較

算法在第162次完成迭代，找到全局最優(yōu)路徑。根據(jù)各節(jié)點(diǎn)轉(zhuǎn)移概率連接節(jié)點(diǎn)連通狀態(tài)，構(gòu)成無線傳感網(wǎng)絡(luò)全局路由信息圖。其中圓點(diǎn)表示傳感節(jié)點(diǎn)，方框表示匯聚節(jié)點(diǎn)，如圖2所示。

圖2 WSN全局路由信息圖

6 結(jié)束語

針對目前無線傳感網(wǎng)絡(luò)路由協(xié)議不足，提出基于視野極值的改進(jìn)蟻群路由算法，并通過信息素局部更新避免全部螞蟻選擇相同路徑。新算法具有正反饋、全局收斂和動態(tài)適應(yīng)等優(yōu)點(diǎn)，能很好的適應(yīng)無線傳感網(wǎng)絡(luò)節(jié)點(diǎn)隨機(jī)分布，節(jié)點(diǎn)頻繁加入和死亡的現(xiàn)象。

［1］ 張輪，陸琰，董德存．一種無線傳感器網(wǎng)絡(luò)覆蓋的粒子群優(yōu)化方法［J］．同濟(jì)大學(xué)學(xué)報（自然科學(xué)版），2009（2）：181－185．Zhang Lun，Lu Yan，Dong De Cun．A New Wireless Sensor Network Optimization Algorithm Base On Particle［J］．Journal Of Tongji University（NATURAL SCIENCE EDITION），2009（2）：181－185．

［2］ 徐云劍，彭沛夫，郭艾寅．基于改進(jìn)蟻群算法的WSN移動代理路由算法研究［J］．計算機(jī)工程與應(yīng)用，2009（4）：45－49．Xu yun jian，Peng Pei Fu，Guo Ai Yan．Study Of Mobile Agent Routing Algorithm Based On Improved Ant Colony Algorithm In WSN［J］．Computer Engineering And Application，2009（4）：45－49．

［3］ 孫力娟，王良俊，王汝傳．改進(jìn)的蟻群算法及其在TSP中的應(yīng)用研究［J］．通信學(xué)報，2004（10）：238－241．Sun Li Juan，Wang Liang Jun，Wang Ru Chuan．Study Of Improved Ant Colony Algorithm And Application In TSP［J］．Journal On Communications，2004（10）：238－241．

［4］ 高堅(jiān)．基于自適應(yīng)蟻群算法的多受限網(wǎng)絡(luò)QoS路由優(yōu)化［J］．計算機(jī)工程，2003（19）：242－248．Gao Jian．OptimizationOfMultipleConstrainsQoS Routing Based On Ant Colony System Algorithm［J］．Computer Engineering，2003（19）：242－248．

［5］ 葉志偉，鄭肇葆．蟻群算法中參數(shù)α、β、ρ設(shè)置的研究—以TSP問題為例［J］．武漢大學(xué)學(xué)報（信息科學(xué)版），2004（7）：95－100．Ye Zhi Wei，Zheng Zhao Bao．Study On The Parameter α、β、ρSet In Ant Colony Algorithm—Taking TSP For Example［J］．Journal Of Wuhan University（Information Science Edition），2004（7）：95－100．

［6］ 季瑩瑩，章堅(jiān)武，虞成磊．無線傳感器網(wǎng)絡(luò)權(quán)值分簇路由協(xié)議改進(jìn)［J］．杭州電子科技大學(xué)學(xué)報，2008（6）：193－197．Ji Ying Ying，Zhang Jian，Yu Cheng Lei．An Improvement Routing Protocol by Weighted Clustering Algorithm in WSN［J］．Journal of Hangzhou Dian Zi University，2008（6）：193－197．

［7］ 汪學(xué)清，楊永田，孫亭．無線傳感器網(wǎng)絡(luò)中基于網(wǎng)格的覆蓋問題研究［J］．計算機(jī)科學(xué)，2006（11）：215－221．Wang Xue Qing，Yang Yong Tian，Sun Ting．Research On The Grid－based Coverage Problem In Wireless Sensor Networks［J］．Computer Science，2006（11）：215－221．

［8］ 梁華為，陳萬明，李帥．一種無線傳感器網(wǎng)絡(luò)蟻群優(yōu)化路由算法［J］．傳感技術(shù)學(xué)報，2007（11）：65－69．Liang Hua Wei，Chen Wan Ming，Li Shuai．A Wireless Sensor Network Routing Optimization Algorithm Base On Ant Colony［J］．Journal Of Sensor Technology，2007（11）：65－69．

［9］ 楊文國，郭田德．求解無線傳感器網(wǎng)絡(luò)路由問題的蟻群最優(yōu)化算法及其收斂性［J］．系統(tǒng)科學(xué)與數(shù)學(xué)，2007（2）：195－201．Yang Wen Guo，Guo Tian De．Ant Colony Optimization Algorithm And Convergence For Wireless Sensor Network Routing Problem［J］．System Science And Mathematics，2007（02）：195－201．

Application of Improved Ant Colony Algorithm in WSN Routing Optimization

Li Feng
（Guangdong Communication Polytechnic，Guangzhou 510650，China）

Wireless sensor network，as a distributed network system，is composed of a large number of sensor nodes．By exchanging state information，the nodes can discover and maintain routing information to form a unified network．Aiming at the problems of routing protocol in wireless sensor networks，this paper describes a new ant algorithm based on vision extremes，and avoids all the ants to choose the same path by update partial pheromones．The simulation results show that new algorithm has advantages of positive feedback，global convergence and dynamic adaptation and is suitable for the phenomenon of large nodes join and death in wireless sensor network．

WSN；Ant Colony Algorithm；Routing Protocol；Mobile Ad Hoc Network；Sensor Node；Sink Node

10．3969／j．issn．1002－2279．2015．04．004

TP393

A

1002－2279（2015）04－0011－04

2012年廣東省高等學(xué)校教學(xué)質(zhì)量與教學(xué)改革工程省級精品資源共享課程（粵教高函［2013］13號）；2013年廣東省高職高專校長聯(lián)席會議教改項(xiàng)目（GDXLHQN012）；2014年廣東省高等職業(yè)教育教學(xué)改革項(xiàng)目；2014中國交通教育研究會科研項(xiàng)目（交教研1402－136）

李鋒（1981－），男，廣東省龍川縣人，碩士研究生，講師，主研方向：計算機(jī)系統(tǒng)結(jié)構(gòu)和網(wǎng)絡(luò)安全方向的研究。

2015－01－16