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

李 鋒

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

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

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

李 鋒

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

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

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

1 引 言

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

無線傳感網(wǎng)絡(luò)一般應(yīng)用于惡劣環(huán)境或是人無法抵達的區(qū)域。由于節(jié)點數(shù)量繁多，并且無法精準(zhǔn)定位，傳感節(jié)點通常采用隨機散播方式部署，節(jié)點與節(jié)點之間通過彼此交換狀態(tài)信息以發(fā)現(xiàn)和維護路由，組成統(tǒng)一網(wǎng)絡(luò)。網(wǎng)絡(luò)層路由協(xié)議是WSN通信的基礎(chǔ)，是實現(xiàn)網(wǎng)絡(luò)可靠、有效傳輸?shù)年P(guān)鍵，既要考慮節(jié)點加入、移動和死亡過程，也要有一定的穩(wěn)定性、容錯性和擴展性［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é)點感知的路由信息具有相似性，為減少數(shù)據(jù)傳輸冗余，節(jié)點只廣播其他節(jié)點沒有的路由信息，從而共同維護全網(wǎng)路由，降低節(jié)點能耗［4－5］。SPIN路由算法簡單，對發(fā)現(xiàn)新節(jié)點動作迅速，但對判斷死亡節(jié)點耗時較長，不適合用于節(jié)點頻繁加入和離開的場合。

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

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

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

2．3 TTDD路由

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

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

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

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

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

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

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

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

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

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

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

其中Di－Sink是節(jié)點i到匯聚節(jié)點之間的距離，MaxRadius是螞蟻最大通信半徑。

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

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

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

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

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

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

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

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

5 仿真測試

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

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

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

圖2 WSN全局路由信息圖

6 結(jié)束語

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

［1］ 張輪，陸琰，董德存．一種無線傳感器網(wǎng)絡(luò)覆蓋的粒子群優(yōu)化方法［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］ 徐云劍，彭沛夫，郭艾寅．基于改進蟻群算法的WSN移動代理路由算法研究［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］ 孫力娟，王良俊，王汝傳．改進的蟻群算法及其在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］ 高堅．基于自適應(yīng)蟻群算法的多受限網(wǎng)絡(luò)QoS路由優(yōu)化［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］ 季瑩瑩，章堅武，虞成磊．無線傳感器網(wǎng)絡(luò)權(quán)值分簇路由協(xié)議改進［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］．計算機科學(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)席會議教改項目（GDXLHQN012）；2014年廣東省高等職業(yè)教育教學(xué)改革項目；2014中國交通教育研究會科研項目（交教研1402－136）

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

2015－01－16