趙晗，黃少卿

（中國(guó)移動(dòng)通信集團(tuán)設(shè)計(jì)院有限公司河北分公司，河北 石家莊 050021）

基于改進(jìn)蟻群算法的無(wú)線傳感器網(wǎng)絡(luò)最小跳數(shù)路由選擇方法

趙晗，黃少卿

（中國(guó)移動(dòng)通信集團(tuán)設(shè)計(jì)院有限公司河北分公司，河北 石家莊 050021）

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

物聯(lián)網(wǎng)；無(wú)線傳感器網(wǎng)絡(luò)；蟻群算法；最小跳數(shù)

1 引言

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

2 無(wú)線傳感器網(wǎng)絡(luò)

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

圖1 無(wú)線傳感器網(wǎng)絡(luò)結(jié)構(gòu)

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

無(wú)線傳感器網(wǎng)絡(luò)中，最小跳數(shù)路由協(xié)議（minimum hop routing protocol）算法是一種平面拓?fù)渎酚伤惴ǎㄟ^(guò)尋找從收集信號(hào)的節(jié)點(diǎn)到匯聚節(jié)點(diǎn)之間的最小跳數(shù)路徑，盡量減小開(kāi)銷，節(jié)約能量和資源，并且通過(guò)路由表信息的維護(hù)來(lái)增強(qiáng)網(wǎng)絡(luò)的頑健性［8］。但傳統(tǒng)的方法存在自身開(kāi)銷過(guò)大、信息更新不及時(shí)等問(wèn)題。

3 蟻群算法原理

3.1 算法描述

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

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

3.2 算法模型

假定存在一個(gè)具有n個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)模型，人工螞蟻的數(shù)量為m，這些螞蟻可以根據(jù)信息素的濃度和啟發(fā)模式對(duì)下一節(jié)點(diǎn)的轉(zhuǎn)移概率進(jìn)行調(diào)整，已經(jīng)經(jīng)過(guò)的節(jié)點(diǎn)會(huì)存儲(chǔ)在記憶表中，不會(huì)重復(fù)經(jīng)過(guò)，當(dāng)完成一次循環(huán)后，就會(huì)更新路徑上的信息素?cái)?shù)據(jù)。

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

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

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

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

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

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

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

3.3 算法的改進(jìn)

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

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

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

4 改進(jìn)蟻群算法求解最小跳數(shù)路由選擇問(wèn)題

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

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

改進(jìn)蟻群算法求解最小跳數(shù)路由路徑的流程如圖2所示。

圖2 改進(jìn)蟻群算法求解最小跳數(shù)路由路徑的流程

5 仿真實(shí)驗(yàn)

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

·下一跳可達(dá)；

·下一跳未曾經(jīng)過(guò)；

·若不滿足前兩個(gè)條件，則按概率公式轉(zhuǎn)移。

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

首先對(duì)單一節(jié)點(diǎn)信號(hào)傳遞路徑進(jìn)行模擬，假設(shè)某一節(jié)點(diǎn)位置感應(yīng)到信息，將自動(dòng)選擇最小跳數(shù)路由路徑傳遞至R20節(jié)點(diǎn)。

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

圖3 感應(yīng)器與匯聚節(jié)點(diǎn)最小跳數(shù)路徑

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

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

圖4 多節(jié)點(diǎn)選擇最小跳數(shù)路徑

圖5 R4節(jié)點(diǎn)損壞時(shí)R1節(jié)點(diǎn)路徑選擇

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

6 結(jié)束語(yǔ)

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

［1］任豐原，黃海寧，林闖.無(wú)線傳感器網(wǎng)絡(luò)［J］.軟件學(xué)報(bào)，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］屈峰，楊華，王立軍，等.無(wú)線傳感器網(wǎng)絡(luò)及其應(yīng)用 ［J］.四川兵工學(xué)報(bào)，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)網(wǎng)的無(wú)線傳感器網(wǎng)絡(luò)綜述［J］.電子與信息學(xué)報(bào)，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］夏俐，陳曦，趙千川，等.無(wú)線傳感器網(wǎng)絡(luò)及應(yīng)用簡(jiǎn)介［J］.自動(dòng)化博覽，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］李炯，汪文勇，潘家根.無(wú)線傳感器網(wǎng)絡(luò)洪泛路由研究［J］.計(jì)算機(jī)科學(xué)，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］魏輝，朱艷.無(wú)線傳感器網(wǎng)絡(luò)的能量有效性網(wǎng)絡(luò)層路由算法——最小跳數(shù)路由算法［J］.計(jì)算機(jī)與信息技術(shù)，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］段海濱.蟻群算法原理及其應(yīng)用［M］.北京：科學(xué)出版社，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問(wèn)題分段求解算法［J］.計(jì)算機(jī)學(xué)報(bào)，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-），男，中國(guó)移動(dòng)通信集團(tuán)設(shè)計(jì)院有限公司河北分公司助理咨詢?cè)O(shè)計(jì)師，主要研究方向?yàn)樯窠?jīng)網(wǎng)絡(luò)、核心網(wǎng)技術(shù)。

黃少卿（1988-），男，中國(guó)移動(dòng)通信集團(tuán)設(shè)計(jì)院有限公司河北分公司系統(tǒng)分析師，主要研究方向?yàn)檐浖こ?、Web數(shù)據(jù)挖掘、IT支撐系統(tǒng)。