一種基于改進(jìn)蟻群優(yōu)化算法的WSNs路由協(xié)議

史寶會(huì)，劉海燕

一種基于改進(jìn)蟻群優(yōu)化算法的WSNs路由協(xié)議

史寶會(huì)，劉海燕

（北京信息職業(yè)技術(shù)學(xué)院計(jì)算機(jī)工程系，北京100018）

面對(duì)無(wú)線(xiàn)傳感網(wǎng)絡(luò)（wireless sensor network，WSN）路由問(wèn)題，提出新穎生物激勵(lì)-自我組織的安全自適應(yīng)路由協(xié)議（biological inspired self-organized secure autonomous routing protocol，BIOSARP）。BIOSARP采用改進(jìn)蟻群優(yōu)化算法（improved ant colony optimization，IACO），利用端到端傳輸時(shí)延、剩余電量和鏈路質(zhì)量計(jì)算信息素，并據(jù)此信息決策最優(yōu)轉(zhuǎn)發(fā)節(jié)點(diǎn)，從而減小廣播次數(shù)和數(shù)據(jù)包負(fù)擔(dān)，降低時(shí)延、數(shù)據(jù)包丟失率和功率消耗。仿真結(jié)果表明：提出的BIOSARP在數(shù)據(jù)包傳遞率、能量消耗優(yōu)于安全實(shí)時(shí)負(fù)荷分配協(xié)議（secure real-time load distribution，SRTLD），數(shù)據(jù)包傳遞率提高24.75%，能量消耗降低31.8%。

蟻群優(yōu)化算法；信息素；自主；路由協(xié)議；無(wú)線(xiàn)傳感網(wǎng)

doi：10.11857/j.issn.1674-5124.2015.09.024

0　引言

集成電路和微處理器的發(fā)展使得部署低功率、多功能、低成本的無(wú)線(xiàn)傳感節(jié)點(diǎn)成為可能［1］。這些無(wú)線(xiàn)傳感節(jié)點(diǎn)以多跳方式相互通信，形成無(wú)線(xiàn)傳感網(wǎng)絡(luò)（wireless sensor networks，WSNs）。WSNs根據(jù)IEEE 802.15.4標(biāo)準(zhǔn)構(gòu)建框架，為收集某一事件信息，需在事件附近部署大量的傳感節(jié)點(diǎn)，并將收集到的信息發(fā)送給信宿節(jié)點(diǎn)（sink node）。然而，微型無(wú)線(xiàn)傳感節(jié)點(diǎn)存在成本、尺寸的限制，并且計(jì)算速度、記憶、能量以及帶寬也受限，使得傳感節(jié)點(diǎn)不能正常工作，即失效，給WSNs應(yīng)用提出了挑戰(zhàn)［1］。通常，傳感節(jié)點(diǎn)的失效是由多種原因引起的，如電池耗盡、休眠期以及小型傳感節(jié)點(diǎn)的故障等［2］。

由于帶寬受限，多數(shù)低功率無(wú)線(xiàn)網(wǎng)的鏈路不可靠，鏈路質(zhì)量嚴(yán)重受到環(huán)境因素的影響［3-4］。此外，網(wǎng)絡(luò)短暫的有效期也是WSNs最常見(jiàn)的問(wèn)題之一。為此，WSNs中的路由協(xié)議必須考慮到WSNs這些特性，并注意到一個(gè)事實(shí)：多數(shù)數(shù)據(jù)只有短的有效期。因此，設(shè)計(jì)WSNs路由協(xié)議必須考慮實(shí)時(shí)性和能量消耗［5］。

相比于LQER，MMSpeed，RTPC，RPAR，安全實(shí)時(shí)負(fù)荷分配協(xié)議（secure real-time load distribution，SRTLD）具有較好的性能［6］。SRTLD是基于地理-方向的定位路由協(xié)議，在數(shù)據(jù)包轉(zhuǎn)發(fā)時(shí)，先選取最佳下一跳節(jié)點(diǎn)。在選取過(guò)程中，利用端到端傳輸時(shí)延、數(shù)據(jù)包接收率（packet reception rate，PRR）和剩余電量信息決策最佳下一跳節(jié)點(diǎn)。選擇過(guò)程和geo-cast轉(zhuǎn)發(fā)過(guò)程考慮了負(fù)載分布信息，提高WSNs的壽命、數(shù)據(jù)吞吐量。此外，SRTLD通過(guò)最小化發(fā)射功率降低了功率消耗。

然而，SRTLD路由協(xié)議也存在一些不足，其中最突出的是在每一跳需通過(guò)廣播Hello消息發(fā)現(xiàn)新的鄰居節(jié)點(diǎn)。每一跳的廣播導(dǎo)致大的功率消耗、額外的時(shí)延以及數(shù)據(jù)包丟失。

上述的不足，如休眠期長(zhǎng)、功率消耗、節(jié)點(diǎn)故障、額外時(shí)延和數(shù)據(jù)包丟失率，激發(fā)了自治機(jī)制的產(chǎn)生［7］。而生物激勵(lì)優(yōu)化技術(shù)在數(shù)字通信中具有良好的性能［8］。蟻群優(yōu)化算法（ant colony optimization，ACO）是實(shí)際應(yīng)用中最佳元啟發(fā)式算法之一。ACO算法以真實(shí)螞蟻行為進(jìn)行工作，可以有效解決復(fù)雜計(jì)算和多方面的離散優(yōu)化問(wèn)題［9-11］。

為此，本文提出一種生物激勵(lì)-自我組織的安全自適應(yīng)路由協(xié)議（biological inspired self-orga nized secure autonomous routing protocol，BIOSARP）。BIOSARP基于蟻群優(yōu)化算法，并利用實(shí)時(shí)負(fù)荷分配（real-time load distribution，RTLD）策略，決策路由。在仿真過(guò)程中，與能效和時(shí)延（energy and delay ants，E&D ANTS）算法［12］、SRTLD［6］以及改進(jìn)的高效節(jié)能螞蟻路由（energy-efficient ant-based routing，IEEABR）［14］進(jìn)行比較。

1　SRTLD和基于ACO路由協(xié)議

1.1SRTLD

SRTLD是一個(gè)實(shí)時(shí)負(fù)載路由協(xié)議，通過(guò)選取最佳下一跳節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)包。SRTLD由5個(gè)管理模塊組成，包括路由、功率、鄰居、位置以及安全。功率管理模塊決定發(fā)射功率的狀態(tài)，鄰居管理模塊負(fù)責(zé)發(fā)現(xiàn)鄰居節(jié)點(diǎn)，并維持鄰居節(jié)點(diǎn)表。SRTLD依據(jù)下式計(jì)算最優(yōu)轉(zhuǎn)發(fā)（optimal forwarding，OF）節(jié)點(diǎn)。

式中：PRR——數(shù)據(jù)包接收率；

Vbatt——剩余電量；

Vmbatt——初始電量；

V——當(dāng)前端到端時(shí)延；

Vm——最大的端到端時(shí)延；

λ1、λ2、λ3——權(quán)重系數(shù)。

SRTLD依據(jù)這些參數(shù)從鄰居節(jié)點(diǎn)中選擇最佳轉(zhuǎn)發(fā)節(jié)點(diǎn)。為此，在決策轉(zhuǎn)發(fā)節(jié)點(diǎn)時(shí)，需建立鄰居表。在每一跳的數(shù)據(jù)包轉(zhuǎn)發(fā)時(shí)需進(jìn)行鄰居的發(fā)現(xiàn)過(guò)程。

在發(fā)現(xiàn)階段，節(jié)點(diǎn)（假定節(jié)點(diǎn)i）廣播路由請(qǐng)求消息（request-to-route，RTR），接收節(jié)點(diǎn)（假定節(jié)點(diǎn)k）將PRR、Vbatt、V信息回復(fù)給節(jié)點(diǎn)i；最后，節(jié)點(diǎn)i將這些信息存于當(dāng)前節(jié)點(diǎn)的鄰居表中。

BIOSARP是基于SRTLD路由協(xié)議的擴(kuò)展。在BIOSARP中，采用改進(jìn)的ACO［15］去實(shí)現(xiàn)WSN中的自治路由。BIOSARP算法利用端到端傳輸時(shí)延、剩余電量和鏈路質(zhì)量計(jì)算信息素，并據(jù)此信息決策最優(yōu)轉(zhuǎn)發(fā)節(jié)點(diǎn)，而ACO算法僅依據(jù)螞蟻的合作行為搜索轉(zhuǎn)發(fā)節(jié)點(diǎn)，并沒(méi)有從優(yōu)化的角度尋找轉(zhuǎn)發(fā)節(jié)點(diǎn)。BIOSARP由3個(gè)功能模塊組成，包括路由管理、鄰居管理以及功率管理。這些模塊相互合作、協(xié)調(diào)，共同提供自身優(yōu)化的路由。

1.2基于ACO路由協(xié)議

Dorigo等［15］首先提出多代理ACO機(jī)制解決復(fù)雜優(yōu)化問(wèn)題，如蟻群算法（ACO meta-heuristic）、二次分配問(wèn)題（quadratic assignment problem，QAP）以及旅行商問(wèn)題（traveling salesman problem，TSP）［16］；其中，ACO算法應(yīng)用廣泛，該算法利用現(xiàn)實(shí)螞蟻的合作行為，解決復(fù)雜計(jì)算，在解決多條件離散優(yōu)化問(wèn)題上的效率得到有效驗(yàn)證［16］。

在ACO算法中，采用兩類(lèi)螞蟻：前向螞蟻（forward ants，F(xiàn)A）、后向螞蟻（backward ants，BA）。前向螞蟻FAs探索、收集從源節(jié)點(diǎn)至目的節(jié)點(diǎn)的路徑信息，隨著螞蟻的移動(dòng)，形成通往目的地的路徑，數(shù)據(jù)沿著路徑進(jìn)行傳輸。前向螞蟻FAs的移動(dòng)有兩個(gè)關(guān)鍵的因素：沿路存儲(chǔ)的信息素和節(jié)點(diǎn)電位（node potentials），其中node potentials表示螞蟻到達(dá)目的地還需移動(dòng)多遠(yuǎn)。而后向螞蟻BAs，指從目的地向源節(jié)點(diǎn)移動(dòng)的螞蟻，它們更新經(jīng)歷過(guò)路徑的信息。

2　BIOSARP

BIOSARP路由協(xié)議流程圖如圖1所示。當(dāng)有數(shù)據(jù)包需要被傳輸或轉(zhuǎn)發(fā)時(shí)，開(kāi)始啟動(dòng)BIOSARP路由。改進(jìn)后的多代理ACO算法依賴(lài)于搜索螞蟻代理和轉(zhuǎn)發(fā)螞蟻代理。首先，檢測(cè)鄰居表是否包含決定下一跳最佳節(jié)點(diǎn)的信息值，如包含，就利用之前選擇的路徑轉(zhuǎn)發(fā)數(shù)據(jù)包；否則，就啟動(dòng)類(lèi)似于SRTLD策略去發(fā)現(xiàn)鄰居節(jié)點(diǎn)，并計(jì)算、決策下一跳最佳節(jié)點(diǎn)。當(dāng)每一跳的第一個(gè)數(shù)據(jù)包被傳輸后，基于ACO計(jì)算得到的信息值存于路由表中，重復(fù)這個(gè)過(guò)程直到第一數(shù)據(jù)包到達(dá)目的節(jié)點(diǎn)。然而，當(dāng)尋找最佳下一跳節(jié)點(diǎn)出現(xiàn)問(wèn)題時(shí)，類(lèi)似SRTLD，啟動(dòng)再發(fā)現(xiàn)策略。

圖1　BIOSARP設(shè)計(jì)方案

數(shù)據(jù)轉(zhuǎn)發(fā)之前，檢測(cè)路由表Rυk。如果路由管理在路由表中不能找到任何節(jié)點(diǎn)的入口，就啟動(dòng)鄰居管理模塊進(jìn)行鄰居發(fā)現(xiàn)。當(dāng)接收到RTR數(shù)據(jù)包后，傳感節(jié)點(diǎn)計(jì)算該數(shù)據(jù)包的轉(zhuǎn)發(fā)特性。這些轉(zhuǎn)發(fā)度量（forwarding metrics）可通過(guò)跨層設(shè)計(jì)（cross layer design，CLD）參數(shù)推導(dǎo)，包括信號(hào)強(qiáng)度、剩余功率以及時(shí)戳。傳感節(jié)點(diǎn)從RTR回復(fù)數(shù)據(jù)包中提取，并且路由管理模塊在鄰居管理模塊的幫助下將這些信息存于鄰居表中。如果源節(jié)點(diǎn)不能接收任何RTR或RTR回復(fù)數(shù)據(jù)包，就啟動(dòng)路由問(wèn)題管理者，如圖1所示。

利用ACO算法計(jì)算信息值pkcυ（t），表示當(dāng)前節(jié)點(diǎn)c在鄰居節(jié)點(diǎn)k的幫助下移動(dòng)到節(jié)點(diǎn)υ的概率值。pkcυ（t）取決于速度τcυ、鏈路質(zhì)量的數(shù)據(jù)包接收率ωcυ和剩余電量ηcυ。節(jié)點(diǎn)依據(jù)最優(yōu)的pkcυ（t）值選取下一跳節(jié)點(diǎn)。pkcυ（k）按下式進(jìn)行計(jì)算：

式中參數(shù)α、β、γ為權(quán)值系數(shù)，可依據(jù)不同應(yīng)用需求進(jìn)行設(shè)置。

考慮鏈路質(zhì)量的數(shù)據(jù)包接收率ωcυ、能量因子ηcυ目的在于提高數(shù)據(jù)傳遞率和能量效率。鏈路質(zhì)量ωcυ可通過(guò)數(shù)據(jù)包接收率PRR測(cè)量，其反映了在傳輸范圍內(nèi)的鏈路質(zhì)量，如下式所示：

速度τcυ依據(jù)端到端時(shí)延參數(shù)，如下式所示：

式中：V——數(shù)據(jù)包速率；

Vm——最大端到端時(shí)延，是射頻信號(hào)的最大速率，等于光速。

能量因子ηcυ等于傳感節(jié)點(diǎn)最大存儲(chǔ)電量與當(dāng)前電量的比值，如下式所示：

式中：Vmbatt——傳感節(jié)點(diǎn)最大存儲(chǔ)電量，設(shè)置為3.6V；

Vbatt——當(dāng)前傳感節(jié)點(diǎn)的電量。

3　性能仿真及分析

采用NS2軟件對(duì)系統(tǒng)進(jìn)行仿真，并將BIOSARP 與SRTLD、E&D ANTS、IEEABR和仿生自組織（bioinspired self-organized，BSO）［11］進(jìn)行比較。同時(shí)，假定每個(gè)參數(shù)具有相同的優(yōu)先級(jí)，即α、β、γ均為0.5。

考慮100m×100m仿真區(qū)域，50個(gè)節(jié)點(diǎn)隨機(jī)分布于仿真區(qū)域。每條鏈路的帶寬為250Kb/s，數(shù)據(jù)包大小為32B，流量負(fù)載為5packets/s，仿真時(shí)間200s。

圖2、圖3分別為BIOSARP、SRTLD、E&D ANTS、IEEABR和BSO的數(shù)據(jù)傳遞率、能量消耗隨數(shù)據(jù)包產(chǎn)生速度的變化曲線(xiàn)。從圖2可知，BIOSARP的數(shù)據(jù)包傳遞率明顯優(yōu)于STRLD，平均提高24.75%。這主要是因?yàn)锽IOSARP采用按需轉(zhuǎn)發(fā)數(shù)據(jù)包，避免了不必要的數(shù)據(jù)包傳輸。

從圖3可知，BIOSARP、SRTLD、E&D ANTS、IEEABR和BSO的能量消耗隨數(shù)據(jù)包傳輸率的上升而增加。在整個(gè)數(shù)據(jù)包傳輸率的變化過(guò)程中，BIOSARP的能量消耗均低于SRTLD，下降了31.8%。這主要是因?yàn)锽IOSARP在路由決策過(guò)程中采用了改進(jìn)的ACO策略，有效地節(jié)約了節(jié)點(diǎn)能量。

為了更充分地比較BIOSARP的性能，將BIOSARP 與SRTLD、E&D ANTS、IEEABR從路由負(fù)載、能量消耗和數(shù)據(jù)包傳遞率3方面性能進(jìn)行比較，數(shù)據(jù)統(tǒng)計(jì)結(jié)果如表1所示。

從表中可知，BIOSARP在路由負(fù)載、能量消耗和數(shù)據(jù)包傳遞率方面優(yōu)于SRTLD、E&D ANTS、IEEABR 3個(gè)路由協(xié)議。其中，BIOSARP的能量消耗僅為4.3 J，約為SRTLD的一半。

圖2　數(shù)據(jù)包傳輸率

圖3　能量消耗

表1　仿真數(shù)據(jù)比較

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

針對(duì)無(wú)線(xiàn)傳感網(wǎng)絡(luò)的路由問(wèn)題，并基于SRTLD的路由協(xié)議展開(kāi)分析，提出BIOSARP協(xié)議。BIOSARP采用了改進(jìn)的ACO算法，依據(jù)數(shù)據(jù)包接收率、端到端傳輸時(shí)延和剩余電量計(jì)算最優(yōu)路由，并將最優(yōu)值存于鄰居表，用于前向數(shù)據(jù)轉(zhuǎn)發(fā)，從而降低轉(zhuǎn)發(fā)時(shí)延和流量負(fù)擔(dān)。通過(guò)仿真分析了BIOSARP的性能。數(shù)據(jù)證明，提出的BIOSARP在數(shù)據(jù)包傳遞率、轉(zhuǎn)發(fā)時(shí)延、能量消耗方面優(yōu)于SRTLD、E&D ANTS、IEEABR。

［1］Vuran M C，Akyildiz I F.XLP：A cross-layer protocol for efficient communication in wireless sensor networks［J］. IEEE Trans Mobile Comput，2010，9（11）：1578-1591.

［2］He T，Stankovic J，Lu C，et al.SPEED：A stateless protocol for real-time communication in sensor networks［C］∥Proc of 23rd Int Conf Distrib Comput Syst，Providence RIUSA，2003：46-55.

［3］Wenning B L，Pesch D A.Environmental monitoring aware routing：Making environmental sensor networks more robust［J］.Telecommun Syst，2010，43（2）：3-11.

［4］Cerpa A，Wong J L，Kuang L，et al.Statistical model of lossy links in wireless sensor networks［C］∥Proc of ACM/IEEE 4th Int Symp IPSN，Los Angeles，USA，2005：81-88.

［5］Garcia M，Sendra S，Lloret J，et al.Saving energy and improving communications using cooperative groupbased wireless sensor networks［J］.Telecommun Syst，2013，52（4）：2489-2502.

［6］Ahmed A，F(xiàn)isal N F.Secure real-time routing protocol with load distribution in wireless sensor networks［J］. Security Commun Netw，2011，4（8）：839-869.

［7］Mármol F G，Pérez G M.Providing trust in wireless sensor networks using a bio-inspired technique［J］. Telecommun Syst，2011，46（2）：163-180.

［8］Mu?oz A，Anton P，Ma?a A.Multiagent systems protection［J］.Adv Softw Eng，2011，4（3）：23-31.

［9］Zhang B，Wu Y，Lu J，et al.Evolutionary computation and its applications in neural and fuzzy systems［J］. Appl Comput Intell Soft Comput，2011，9（2）：34-40.

［10］Zungeru A M，Ang L M，Seng K P.Classical and swarm intelligence based routing protocols for wireless sensor networks：A survey and comparison［J］.J Netw Comput Appl，2012，35（5）：1508-1536.

［11］Saleem K，F(xiàn)isal N.Empirical studies of bio-inspired self-organized secure autonomous routing protocol［J］. IEEE Sensors Journal，2014，14（7）：2232-2240.

［12］Wen Y F，Chen Y Q，Pan M.Adaptive ant-based routing in wireless sensor networks using energy delay metrics［J］.J Zhejiang Univ Sci，2008，9（4）：531-538.

［13］Zungeru A M，Seng K P，Ang L M，et al.Energy efficiency performance improvements for ant-based routing algorithm in wireless sensor networks［J］.J Sensors，2013 （4）：34-42.

［14］Saleem K，F(xiàn)isal N，Baharudin M A，et al.Ant colony inspired self-optimized routing protocol based on cross layer architecture for wireless sensor networks［J］.Wseas Trans Commun，2010，9（10）：669-678.

［15］Chen G，Guo T D，Yang W G，et al.An improved ant based routing protocol in wireless sensor networks［J］. Collaborative Comput，2006，3（4）：1-7.

［16］Ghoseiri K，Morshedsolouk F.ACS-TS：Train scheduling using ant colony system［J］.Math Decision Sci，2006，45 （6）：23-31.

A novel improved ant colony optimization-based routing protocol in w ireless sensor networks

SHI Baohui，LIU Haiyan
（Computer Department，Beijing Information Technology College，Beijing 100018，China）

To solve routing problems in wireless sensor networks（WSN），a biological inspired selforganized secure autonomous routing protocol（BIOSARP）has been proposed in this paper.In the BIOSARP mechanism，an optimal forwarding decision was obtained by the improved ant colony optimization（IACO）.With the help of the IACO，the pheromone value was computed according to the end-to-end delay，remaining battery power，and link quality metrics.The proposed BIOSARP has been designed to reduce the broadcast and packet overhead to minimize the delay，packet loss，and power consumption in WSNs.Simulation results show that the delivery ratio of the BIOSARP has been improved by 24.75%so as to reduce the energy consumption by 31.8% compared to the secure real-time load distribution（SRTLD）.

ant colony optimization；pheromone；autonomous agents；routing protocols；wireless sensor networks

A

1674-5124（2015）09-0106-04

2014-11-27；

2015-02-01

國(guó)家自然科學(xué)基金（20121302167）水沙科學(xué)與水利水電工程國(guó)家重點(diǎn)實(shí)驗(yàn)室科研課題（2012-KY-05）

史寶會(huì)（1964-），女，北京市人，副教授，碩士，主要研究領(lǐng)域?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)技術(shù)、網(wǎng)絡(luò)存儲(chǔ)與數(shù)據(jù)安全技術(shù)。