基于改進蟻群算法的無線傳感器網絡最小跳數路由選擇方法

趙晗，黃少卿

（中國移動通信集團設計院有限公司河北分公司，河北 石家莊 050021）

基于改進蟻群算法的無線傳感器網絡最小跳數路由選擇方法

趙晗，黃少卿

（中國移動通信集團設計院有限公司河北分公司，河北 石家莊 050021）

無線傳感器網絡是一種依靠網絡中互聯(lián)節(jié)點傳遞數據的自組織網絡，其發(fā)展將為物聯(lián)網技術提供重要支撐。為了優(yōu)化無線傳感器網絡節(jié)點傳播和處理數據的能力，減少節(jié)點能量消耗，研究了基于改進蟻群算法的無線傳感器網絡最小跳數路由選擇方法。利用改進蟻群算法出色的全局尋優(yōu)能力，對無線傳感器網絡中最小跳數路由選擇問題進行優(yōu)化，仿真實驗證明了其有效性。

物聯(lián)網；無線傳感器網絡；蟻群算法；最小跳數

1 引言

在現(xiàn)代信息技術中，無線傳感器網絡（wireless sensor network，WSN）技術與通信技術以及計算機技術有著同樣重要的地位，并且已經被廣泛運用于軍事、交通、農業(yè)、醫(yī)療等多個領域［1-3］。物聯(lián)網的發(fā)展需要在自然環(huán)境中部署大量節(jié)點，無線傳感器網絡技術的進步對物聯(lián)網的發(fā)展有著重要的推動作用。無線傳感器網絡節(jié)點傳感器有多種不同類型，可感應如振動、電磁波、溫度、濕度、聲音、壓力等信號，這些不同特點的節(jié)點為無線傳感器網絡在實際應用中的推廣打下堅實基礎［4］。在很多情況下，微小傳感器節(jié)點的部署安裝可以在其他工具無法進入的環(huán)境中完成重要任務。由于節(jié)點能量有限，供電裝置不易更換，所以在實際應用中應考慮如何減少節(jié)點的能量損耗和傳輸帶寬資源消耗問題。傳統(tǒng)的洪泛（flooding）算法是最傳統(tǒng)且簡單的方法［5］，其無須建立網絡和維護路由，頑健性強，但是廣播的發(fā)送方式會消耗大量能量。信息協(xié)商傳感器算法［6］是一種以數據為中心的算法，解決了洪泛算法的冗余問題，但需要大量的控制信息。LEACH算法是一種層次路由算法［7］，按照簇進行數據分組，性能優(yōu)越但實現(xiàn)相對復雜。此外，還有樹型算法、SPEED算法等，在能量消耗、時延、復雜度、頑健性等方面均有不足之處。而在節(jié)點路由選擇過程中找到最小跳數傳播路徑，減少一次信息傳播需要通過的節(jié)點數，可以有效改善能量和帶寬的問題。

2 無線傳感器網絡

無線傳感器網絡作為一種由大量節(jié)點元件組成的自組織網絡，與傳統(tǒng)的無線通信網絡有很大相似之處，又有所不同。組成網絡的傳感器節(jié)點具有處理、存儲和傳輸數據的功能，在實際工作中它們協(xié)作將從環(huán)境中感知的物理信息轉換為數字信號后，發(fā)送給匯聚（sink）節(jié)點。sink節(jié)點可以看作一個功能增強的傳感器節(jié)點，上連外部網絡和管理節(jié)點，這樣就形成一條從末端到用戶的數據通路。其過程如圖1所示。

圖1 無線傳感器網絡結構

無線傳感器網絡節(jié)點在整個網絡中數量最多，而且承載了邊緣收集、處理和傳遞信息的任務，具有大規(guī)模性、自組織性、動態(tài)性、資源有限等特性。然而，傳感器節(jié)點由于能量有限、位置分散且數量多等原因，很難進行持續(xù)維護，所以在無線傳感器網絡實際使用中，應當考慮節(jié)約能耗和傳輸帶寬資源的問題。

無線傳感器網絡中，最小跳數路由協(xié)議（minimum hop routing protocol）算法是一種平面拓撲路由算法，通過尋找從收集信號的節(jié)點到匯聚節(jié)點之間的最小跳數路徑，盡量減小開銷，節(jié)約能量和資源，并且通過路由表信息的維護來增強網絡的頑健性［8］。但傳統(tǒng)的方法存在自身開銷過大、信息更新不及時等問題。

3 蟻群算法原理

3.1 算法描述

意大利學者Dorego M等通過模擬蟻群覓食的行為特征，提出了蟻群優(yōu)化算法。一群螞蟻在不知道食物位置的情況下，開始向不同方向移動覓食。當其中的一只螞蟻發(fā)現(xiàn)食物，它就會向環(huán)境中分泌一種稱為信息素的物質，從而吸引同伴來到食物的位置。但群體中會存在另外一些并沒有沿著已知路徑移動的個體，如果它們另辟蹊徑發(fā)現(xiàn)了更近的道路，漸漸地就會有更多螞蟻被吸引到較短路徑上來。如此反復進行一段時間后，就會有最多數量的螞蟻在一條最短的路徑上行進的現(xiàn)象。蟻群優(yōu)化（ant colony optimization，ACO）算法作為一種群體智能優(yōu)化算法，自從被提出后，在解決TSP（travelling salesman problem，旅行商問題）以及最短路徑等問題中的優(yōu)勢得到了廣泛認可［9］，并且在其他領域得到了推廣。與其他一些群體智能優(yōu)化算法一樣，蟻群算法同樣存在可能陷入局部最優(yōu)、出現(xiàn)早熟停滯現(xiàn)象的問題。Stuzle T提出了 “最大最小蟻群系統(tǒng)”［10］，允許各個路徑上的信息量進行規(guī)定范圍內的動態(tài)變化，在解決 TSP、QoS（quality of service，服務質量）問題中具有明顯優(yōu)勢。吳斌等［11］在蟻群算法基礎上提出了相遇max-min算法，提高了蟻群一次周游的質量，并結合分段求解方法，用于解決旅行商問題。

蟻群算法是一種正反饋系統(tǒng)，路徑上個體的增多會產生更多的信息素，而信息素的增加又會吸引更多的個體，通過這個過程使算法收斂。在對真實的螞蟻行為進行人工模擬的同時，個體增加了存儲信息的智能，這樣蟻群就擺脫了盲目性，可以在離散的空間進行隨機搜索。此外，蟻群算法還具有分布式、全局性等特性。

3.2 算法模型

假定存在一個具有n個節(jié)點的網絡模型，人工螞蟻的數量為m，這些螞蟻可以根據信息素的濃度和啟發(fā)模式對下一節(jié)點的轉移概率進行調整，已經經過的節(jié)點會存儲在記憶表中，不會重復經過，當完成一次循環(huán)后，就會更新路徑上的信息素數據。

在算法中，螞蟻選擇下一跳節(jié)點的概率并不是完全隨機的，節(jié)點i上的螞蟻k移動向節(jié)點j的概率為q0，j就 是使信息素濃度τisα（t）ηisβ（t）最大的節(jié)點，移動狀態(tài)表示為：

q0是0～1之間的常數，q是0～1之間的偽隨機數。q產生在螞蟻選擇下一跳之前，如果 q≤q0，就可以向 τisα（t）ηisβ（t）最大的節(jié)點前進，否則，就按照式（2）選擇下一節(jié)點。

其中，τijα和ηijβ分別表示 ij邊上的信息素濃度和可視度是兩個節(jié)點間的距離，α和β分別表示信息素濃度的權值和啟發(fā)信息的權值，pijk表示k個體由i向j移動的概率，allowedk包含k個體當前可以直接到達的下一跳節(jié)點。

尋找最優(yōu)的過程包含局部更新和全局更新。在局部更新中，個體選擇一個節(jié)點按照式（3）更新路徑上的信息素。

其中，信息素揮發(fā)因子 ξ∈［0，1］，τ0表示信息素初始濃度。

當所有個體完成循環(huán)后，會按照式（4）和式（5）進行全局范圍內的更新。

信息素的 全局 揮 發(fā) 因子 ρ∈［0，1］，?τ表示本次相應路徑上信息素濃度的變量，當前全局最優(yōu)路徑用Lgb表示。

3.3 算法的改進

蟻群算法在路徑尋優(yōu)方面具有先天優(yōu)勢，但其本身存在易出現(xiàn)早熟停滯、陷入局部最優(yōu)的不足。

改進的蟻群算法優(yōu)化了信息素全局更新規(guī)則，可以更好地達到全局收斂，可表示為：

其中，Lbest和Lworst分別表示本次迭代的最優(yōu)路徑和最差路徑數據。另外，在使用過程中引入了最大最小信息素系統(tǒng)［10］，更好地控制了早熟停滯問題。

4 改進蟻群算法求解最小跳數路由選擇問題

傳統(tǒng)的最小跳數路由選擇方法由匯聚節(jié)點首先通過洪泛算法向全部節(jié)點多播廣播分組，分組在傳播過程中進行計數，到達每一個節(jié)點后，反向傳播就可以得到一個通路，而計數的目的就是找到跳數最少的路徑。這種方法在每次通信過程中都會造成全部節(jié)點提前運行一次，大大消耗了能量和帶寬資源。

本文將改進的蟻群算法路徑尋優(yōu)的特點運用到最小跳數路由選擇中，通過一次多播確定傳感器節(jié)點之間的路由表連接情況，當某個傳感器節(jié)點產生數據時，就會自動尋找經過節(jié)點最少的最小跳數路徑到達匯聚節(jié)點。而由于蟻群算法的智能尋優(yōu)特點，當傳感器網絡中某個通路中的節(jié)點損壞造成無法正常工作時，那么傳感器網絡就可以自動尋找其他通路向目標節(jié)點傳遞信息。

改進蟻群算法求解最小跳數路由路徑的流程如圖2所示。

圖2 改進蟻群算法求解最小跳數路由路徑的流程

5 仿真實驗

以下仿真均在VS2010環(huán)境通過C++語言編程實現(xiàn)。在仿真試驗中，假設環(huán)境中有20個傳感器節(jié)點，節(jié)點之間并不是全部互通。以R20節(jié)點作為匯聚節(jié)點。在尋優(yōu)過程中，人工螞蟻選擇下一跳路由時，應遵循以下條件：

·下一跳可達；

·下一跳未曾經過；

·若不滿足前兩個條件，則按概率公式轉移。

系統(tǒng)中參數設置如下：ρ=0.1，α=0.7，β=1，ξ=0.5，q0=0.9，蟻群數量為m=5，最大迭代次數為20。

首先對單一節(jié)點信號傳遞路徑進行模擬，假設某一節(jié)點位置感應到信息，將自動選擇最小跳數路由路徑傳遞至R20節(jié)點。

在圖3中可以明顯看出，當位于邊緣的R1和R3節(jié)點接收到信號后，可以很好地找到最小跳數路徑（不唯一），并傳輸至匯聚節(jié)點。

圖3 感應器與匯聚節(jié)點最小跳數路徑

如果在環(huán)境中同時有多點感應到信號，那么每個節(jié)點仍可以很好地找到各自的最小跳數路徑，將信息傳遞至匯聚節(jié)點，如圖4所示。

而當網絡中的某個傳感器節(jié)點發(fā)生損壞不能正常工作時，蟻群算法可以迅速找到另外的次優(yōu)路徑。如圖5所示，當R4節(jié)點損壞，則R1的信息將按照另外的最小跳數通路傳輸。

圖4 多節(jié)點選擇最小跳數路徑

圖5 R4節(jié)點損壞時R1節(jié)點路徑選擇

通過仿真實驗可以看出，基于改進蟻群算法的路由最小跳數路徑選擇方法可以很好地完成無線傳感器網絡節(jié)點間的路由選擇，并且當網絡中節(jié)點發(fā)生損壞時，算法可以很好地隨機應變更改線路。選擇最小跳數路徑可以很好地節(jié)約能量和帶寬資源，而算法的頑健性使網絡情況發(fā)生變化時也可以很好地完成路徑優(yōu)化選擇。

6 結束語

無線傳感器網絡在社會發(fā)展中得到了廣泛應用，尤其對物聯(lián)網的發(fā)展具有積極推進作用。利用改進蟻群優(yōu)化算法對網絡最小跳數路由路徑進行選擇，仿真實驗證明了其有效性，使無線傳感器網絡在應用中可以更好地進行能量和資源優(yōu)化，有利于其進一步發(fā)展。但任何方法都不是完美的，如優(yōu)化算法可能增加時間消耗等，這將是進一步研究的問題。

［1］任豐原，黃海寧，林闖.無線傳感器網絡［J］.軟件學報，2003，14（7）：1282-1291.RRN F Y，HUANG H N，LIN C.Wireless sensor networks［J］.Journal of Software，2003，14（7）：1282-1291.

［2］屈峰，楊華，王立軍，等.無線傳感器網絡及其應用 ［J］.四川兵工學報，2013，34（2）：111-113.QU F，YANG H，WANG L J，et al.Application of wireless sensor networks［J］.Sichuan Ordnance Journal，2013，34（2）：111-113.

［3］錢志鴻，王義君.面向物聯(lián)網的無線傳感器網絡綜述［J］.電子與信息學報，2013（1）：215-227.QIAN Z H，WANG Y J.Internet of things-oriented wireless sensor networks review［J］.Journal of Electronics&Information Technology，2013（1）：215-227.

［4］夏俐，陳曦，趙千川，等.無線傳感器網絡及應用簡介［J］.自動化博覽，2004，21（1）：34-37.XIA L，CHEN X，ZHAO Q C，et al.The introduction of wireless sensor network and its application ［J］.Automation Panorama，2004，21（1）：34-37.

［5］李炯，汪文勇，潘家根.無線傳感器網絡洪泛路由研究［J］.計算機科學，2006，33（5）：74-76.LI J，WANG W Y，PAN J G.Research of flooding route of wireless sensor network［J］.Computer Science，2006，33（5）：74-76.［6］ESSA I A. Ubiquitous sensing for smart and aware environments：technologies towards the building of an aware home［J］.Position Paper for the Darpa／nsf／nist Workshop on Smart Environment，1999.

［7］YAO Y K，CHEN Y C.Highenergy-efficientclustering algorithm forWSNs ［C］／／The InternationalConferenceon Computer Science and Information Processing，August 24-26，2012，Xi’an，China.New Jersey：IEEE Press，2012：437-440.

［8］魏輝，朱艷.無線傳感器網絡的能量有效性網絡層路由算法——最小跳數路由算法［J］.計算機與信息技術，2007（4）：47-50.WEI H，ZHU Y.Energy efficient network layer routing algorithm for wireless sensor networks：a minimum hop routing algorithm［J］.Computer and Communication Technology，2007（4）：47-50.

［9］段海濱.蟻群算法原理及其應用［M］.北京：科學出版社，2005：17-103.DUAN H B.Principle and application of ant colony algorithm［M］.Beijing：Science Press，2005：19-103.

［10］INTELLEKTIK F，INFORMATIK F，DARMSTADT T H，et al.Parallelization strategies for ant colony optimization ［M］.Berlin：Springer，1998：722-731.

［11］吳斌，史忠植.一種基于蟻群算法的TSP問題分段求解算法［J］.計算機學報，2001，24（12）：1328-1333.WU B，SHI Z Z.An ant colony algorithm based partition algorithm for TSP［J］.Chinese Journal of Computer，2001，24（12）：1328-1333.

Routing optimization method of WSN based on improved ant colony algorithm

ZHAO Han，HUANG Shaoqing
Hebei Branch of China Mobile Group Design Institute Co.，Ltd.，Shijiazhuang 050021，China

Wireless sensor network is a self-organizing network that storing and transferring the data by the interconnected nodes.It will promote the development of the internet of things technology.In order to optimize the ability of data communication and data process，and reduce the energy consumption，the routing optimization method of wireless sensor network based on improved ant colony algorithm was proposed.Improved ant colony algorithm had excellent global optimization ability，so it could be used to optimize the minimum hop routing problem in wireless sensor network.And the simulation proves its validity.

internet of things，wireless sensor network，ant colony algorithm，minimum hop

TN919

A

10.11959／j.issn.1000-0801.2016036

2015-11-04；

2015-12-15

趙晗（1988-），男，中國移動通信集團設計院有限公司河北分公司助理咨詢設計師，主要研究方向為神經網絡、核心網技術。

黃少卿（1988-），男，中國移動通信集團設計院有限公司河北分公司系統(tǒng)分析師，主要研究方向為軟件工程、Web數據挖掘、IT支撐系統(tǒng)。