一種基于改進蟻群優化算法的WSNs路由協議

史寶會，劉海燕

一種基于改進蟻群優化算法的WSNs路由協議

史寶會，劉海燕

（北京信息職業技術學院計算機工程系，北京100018）

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

蟻群優化算法；信息素；自主；路由協議；無線傳感網

doi：10.11857/j.issn.1674-5124.2015.09.024

0　引言

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

由于帶寬受限，多數低功率無線網的鏈路不可靠，鏈路質量嚴重受到環境因素的影響［3-4］。此外，網絡短暫的有效期也是WSNs最常見的問題之一。為此，WSNs中的路由協議必須考慮到WSNs這些特性，并注意到一個事實：多數數據只有短的有效期。因此，設計WSNs路由協議必須考慮實時性和能量消耗［5］。

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

然而，SRTLD路由協議也存在一些不足，其中最突出的是在每一跳需通過廣播Hello消息發現新的鄰居節點。每一跳的廣播導致大的功率消耗、額外的時延以及數據包丟失。

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

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

1　SRTLD和基于ACO路由協議

1.1SRTLD

SRTLD是一個實時負載路由協議，通過選取最佳下一跳節點轉發數據包。SRTLD由5個管理模塊組成，包括路由、功率、鄰居、位置以及安全。功率管理模塊決定發射功率的狀態，鄰居管理模塊負責發現鄰居節點，并維持鄰居節點表。SRTLD依據下式計算最優轉發（optimal forwarding，OF）節點。

式中：PRR——數據包接收率；

Vbatt——剩余電量；

Vmbatt——初始電量；

V——當前端到端時延；

Vm——最大的端到端時延；

λ1、λ2、λ3——權重系數。

SRTLD依據這些參數從鄰居節點中選擇最佳轉發節點。為此，在決策轉發節點時，需建立鄰居表。在每一跳的數據包轉發時需進行鄰居的發現過程。

在發現階段，節點（假定節點i）廣播路由請求消息（request-to-route，RTR），接收節點（假定節點k）將PRR、Vbatt、V信息回復給節點i；最后，節點i將這些信息存于當前節點的鄰居表中。

BIOSARP是基于SRTLD路由協議的擴展。在BIOSARP中，采用改進的ACO［15］去實現WSN中的自治路由。BIOSARP算法利用端到端傳輸時延、剩余電量和鏈路質量計算信息素，并據此信息決策最優轉發節點，而ACO算法僅依據螞蟻的合作行為搜索轉發節點，并沒有從優化的角度尋找轉發節點。BIOSARP由3個功能模塊組成，包括路由管理、鄰居管理以及功率管理。這些模塊相互合作、協調，共同提供自身優化的路由。

1.2基于ACO路由協議

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

在ACO算法中，采用兩類螞蟻：前向螞蟻（forward ants，FA）、后向螞蟻（backward ants，BA）。前向螞蟻FAs探索、收集從源節點至目的節點的路徑信息，隨著螞蟻的移動，形成通往目的地的路徑，數據沿著路徑進行傳輸。前向螞蟻FAs的移動有兩個關鍵的因素：沿路存儲的信息素和節點電位（node potentials），其中node potentials表示螞蟻到達目的地還需移動多遠。而后向螞蟻BAs，指從目的地向源節點移動的螞蟻，它們更新經歷過路徑的信息。

2　BIOSARP

BIOSARP路由協議流程圖如圖1所示。當有數據包需要被傳輸或轉發時，開始啟動BIOSARP路由。改進后的多代理ACO算法依賴于搜索螞蟻代理和轉發螞蟻代理。首先，檢測鄰居表是否包含決定下一跳最佳節點的信息值，如包含，就利用之前選擇的路徑轉發數據包；否則，就啟動類似于SRTLD策略去發現鄰居節點，并計算、決策下一跳最佳節點。當每一跳的第一個數據包被傳輸后，基于ACO計算得到的信息值存于路由表中，重復這個過程直到第一數據包到達目的節點。然而，當尋找最佳下一跳節點出現問題時，類似SRTLD，啟動再發現策略。

圖1　BIOSARP設計方案

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

利用ACO算法計算信息值pkcυ（t），表示當前節點c在鄰居節點k的幫助下移動到節點υ的概率值。pkcυ（t）取決于速度τcυ、鏈路質量的數據包接收率ωcυ和剩余電量ηcυ。節點依據最優的pkcυ（t）值選取下一跳節點。pkcυ（k）按下式進行計算：

式中參數α、β、γ為權值系數，可依據不同應用需求進行設置。

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

速度τcυ依據端到端時延參數，如下式所示：

式中：V——數據包速率；

Vm——最大端到端時延，是射頻信號的最大速率，等于光速。

能量因子ηcυ等于傳感節點最大存儲電量與當前電量的比值，如下式所示：

式中：Vmbatt——傳感節點最大存儲電量，設置為3.6V；

Vbatt——當前傳感節點的電量。

3　性能仿真及分析

采用NS2軟件對系統進行仿真，并將BIOSARP 與SRTLD、E&D ANTS、IEEABR和仿生自組織（bioinspired self-organized，BSO）［11］進行比較。同時，假定每個參數具有相同的優先級，即α、β、γ均為0.5。

考慮100m×100m仿真區域，50個節點隨機分布于仿真區域。每條鏈路的帶寬為250Kb/s，數據包大小為32B，流量負載為5packets/s，仿真時間200s。

圖2、圖3分別為BIOSARP、SRTLD、E&D ANTS、IEEABR和BSO的數據傳遞率、能量消耗隨數據包產生速度的變化曲線。從圖2可知，BIOSARP的數據包傳遞率明顯優于STRLD，平均提高24.75%。這主要是因為BIOSARP采用按需轉發數據包，避免了不必要的數據包傳輸。

從圖3可知，BIOSARP、SRTLD、E&D ANTS、IEEABR和BSO的能量消耗隨數據包傳輸率的上升而增加。在整個數據包傳輸率的變化過程中，BIOSARP的能量消耗均低于SRTLD，下降了31.8%。這主要是因為BIOSARP在路由決策過程中采用了改進的ACO策略，有效地節約了節點能量。

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

從表中可知，BIOSARP在路由負載、能量消耗和數據包傳遞率方面優于SRTLD、E&D ANTS、IEEABR 3個路由協議。其中，BIOSARP的能量消耗僅為4.3 J，約為SRTLD的一半。

圖2　數據包傳輸率

圖3　能量消耗

表1　仿真數據比較

4　結束語

針對無線傳感網絡的路由問題，并基于SRTLD的路由協議展開分析，提出BIOSARP協議。BIOSARP采用了改進的ACO算法，依據數據包接收率、端到端傳輸時延和剩余電量計算最優路由，并將最優值存于鄰居表，用于前向數據轉發，從而降低轉發時延和流量負擔。通過仿真分析了BIOSARP的性能。數據證明，提出的BIOSARP在數據包傳遞率、轉發時延、能量消耗方面優于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，Fisal 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，Fisal 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，Fisal 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

國家自然科學基金（20121302167）水沙科學與水利水電工程國家重點實驗室科研課題（2012-KY-05）

史寶會（1964-），女，北京市人，副教授，碩士，主要研究領域為計算機網絡技術、網絡存儲與數據安全技術。