一种基于改进蚁群优化算法的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-），女，北京市人，副教授，硕士，主要研究领域为计算机网络技术、网络存储与数据安全技术。