改進蟻群算法在WSN路由優化中的應用*

李 鋒

（廣東交通職業技術學院，廣州510650）

·微機網絡與通信·

改進蟻群算法在WSN路由優化中的應用*

李 鋒

（廣東交通職業技術學院，廣州510650）

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

無線傳感網絡；蟻群算法；路由協議；無線自組織網絡；傳感節點；匯聚節點

1 引 言

無線傳感網絡是一種由大量傳感節點構成的分布式網絡系統，由傳感節點、匯聚節點和管理節點組成，見圖1。傳感節點感知目標信息后以多跳接力方式傳給匯聚節點，匯聚節點對附近傳感節點信息匯總后通過衛星基站、互聯網傳送給管理用戶［1－2］。

無線傳感網絡一般應用于惡劣環境或是人無法抵達的區域。由于節點數量繁多，并且無法精準定位，傳感節點通常采用隨機散播方式部署，節點與節點之間通過彼此交換狀態信息以發現和維護路由，組成統一網絡。網絡層路由協議是WSN通信的基礎，是實現網絡可靠、有效傳輸的關鍵，既要考慮節點加入、移動和死亡過程，也要有一定的穩定性、容錯性和擴展性［3］。目前，業界針對無線傳感網絡不同應用場合和需求研究出不同的路由協議。

2 無線傳感網絡路由協議

2．1 SPIN路由協議

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

圖1 WSN體系結構

2．2 定向擴散協議

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

2．3 TTDD路由

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

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

3 標準蟻群算法

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

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

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

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

（4）螞蟻根據下一節點信息素濃度Tg選擇最優路徑，概率為：

4 蟻群算法在WSN網絡中的應用

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

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

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

（2）螞蟻在節點i選擇節點j的路徑轉移概率為：

其中P是式（5）的行進距離，α和β是節點i和節點j各自權重。

（3）螞蟻根據轉移概率行進至下一節點，完成一次循環迭代，信息素濃度更新如下式：

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

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

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

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

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

5 仿真測試

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

表1 四種算法結果比較

算法在第162次完成迭代，找到全局最優路徑。根據各節點轉移概率連接節點連通狀態，構成無線傳感網絡全局路由信息圖。其中圓點表示傳感節點，方框表示匯聚節點，如圖2所示。

圖2 WSN全局路由信息圖

6 結束語

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

［1］ 張輪，陸琰，董德存．一種無線傳感器網絡覆蓋的粒子群優化方法［J］．同濟大學學報（自然科學版），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］．計算機工程與應用，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中的應用研究［J］．通信學報，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］ 高堅．基于自適應蟻群算法的多受限網絡QoS路由優化［J］．計算機工程，2003（19）：242－248．Gao Jian．OptimizationOfMultipleConstrainsQoS Routing Based On Ant Colony System Algorithm［J］．Computer Engineering，2003（19）：242－248．

［5］ 葉志偉，鄭肇葆．蟻群算法中參數α、β、ρ設置的研究—以TSP問題為例［J］．武漢大學學報（信息科學版），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］ 季瑩瑩，章堅武，虞成磊．無線傳感器網絡權值分簇路由協議改進［J］．杭州電子科技大學學報，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］ 汪學清，楊永田，孫亭．無線傳感器網絡中基于網格的覆蓋問題研究［J］．計算機科學，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］ 梁華為，陳萬明，李帥．一種無線傳感器網絡蟻群優化路由算法［J］．傳感技術學報，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］ 楊文國，郭田德．求解無線傳感器網絡路由問題的蟻群最優化算法及其收斂性［J］．系統科學與數學，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年廣東省高等學校教學質量與教學改革工程省級精品資源共享課程（粵教高函［2013］13號）；2013年廣東省高職高專校長聯席會議教改項目（GDXLHQN012）；2014年廣東省高等職業教育教學改革項目；2014中國交通教育研究會科研項目（交教研1402－136）

李鋒（1981－），男，廣東省龍川縣人，碩士研究生，講師，主研方向：計算機系統結構和網絡安全方向的研究。

2015－01－16