基于改进蚁群算法的无线传感器网络最小跳数路由选择方法

 赵晗，黄少卿

 （中国移动通信集团设计院有限公司河北分公司，河北石家庄050021）

摘  要：无线传感器网络是一种依靠网络中互联节点传递数据的自组织网络，其发展将为物联网技术提供重要支撑。为了优化无线传感器网络节点传播和处理数据的能力，减少节点能量消耗，研究r基于改进蚁群算法的无线传感器网络最小跳数路由选择方法。利用改进蚁群算法出色的全局寻优能力，对无线传感器网络中最小跳数路由选择问题进行优化，仿真实验证明了其有效性。

关键词：物联网；无线传感器网络；蚁群算法；最小跳数

中图分类号：TN919 doi:10.1 1959/j.issn.1000P0801.2016036

1  引言

 在现代信息技术中，无线传感器网络(wireless sensornetwork．WSN)技术与通信技术以及计算机技术有着同样重要的地位，并且已经被广泛运用于军事、交通、农业、医疗等多个领域。物联网的发展需要在自然环境中部署大量节点，无线传感器网络技术的进步对物联网的发展有着重要的推动作用。无线传感器网络节点传感器有多种不同类型，可感应如振动、电磁波、温度，湿度、声音、压力等信号，这些不同特点的节点为无线传感器网络在实际应用中的推广打下坚实基础。在很多情况下，微小传感器节点的部署安装可以在其他工具无法进入的环境中完成重要任务。由于节点能量有限，供电装置不易更换，所以在实际应用中应考虑如何减少节点的能量损耗和传输带宽资源消耗问题。传统的洪泛( flooding)算法是最传统且简单的方法。其无须建立网络和维护路由，顽健性强，但是广播的发送方式会消耗大量能量。信息协商传感器算法是一种以数据为中心的算法，解决了洪泛算法的冗余问题，但需要大量的控制信息。LEACH算法是一种层次路由算法，按照簇进行数据分组，性能优越但实现相对复杂。此外，还有树型算法、SPEED算法等，在能量消耗、时延、复杂度、顽健性等方面均有不足之处。而在节点路由选择过程中找到最小跳数传播路径，减少一次信息传播需要通过的节点数，可以有效改善能量和带宽的问题。

2无线传感器网络

 无线传感器网络作为一种由大量节点元件组成的自组织网络，与传统的无线通信网络有很大相似之处，又有所不同。组成网络的传感器节点具有处理、存储和传输数据的功能，在实际工作中它们协作将从环境中感知的物理信息转换为数字信号后，发送给汇聚( sink)节点。sink节点可以看作一个功能增强的传感器节点，上连外部网络和管理节点，这样就形成一条从末端到用户的数据通路。其过程如图1所示。

 无线传感器网络节点在整个网络中数量最多，而且承载了边缘收集、处理和传递信息的任务，具有大规模性、自组织性、动态性、资源有限等特性。然而，传感器节点由于能量有限、位置分散且数量多等原因，很难进行持续维护，所以在无线传感器网络实际使用中，应当考虑节约能耗和传输带宽资源的问题。

 无线传感器网络中，最小跳数路由协议(minimum hoprouting protocol)算法是一种平面拓扑路由算法，通过寻找从收集信号的节点到汇聚节点之间的最小跳数路径，尽量减小开销，节约能量和资源，并且通过路由表信息的维护来增强网络的顽健性。但传统的方法存在自身开销过大、信息更新不及时等问题。

3  蚁群算法原理

3.1  算法描述

 意大利学者Dorego M等通过模拟蚁群觅食的行为特征，提出了蚁群优化算法。一群蚂蚁在不知道食物位置的情况下，开始向不同方向移动觅食。当其中的一只蚂蚁发现食物，它就会向环境中分泌一种称为信息素的物质，从而吸引同伴来到食物的位置。但群体中会存在另外一些并没有沿着已知路径移动的个体，如果它们另辟蹊径发现了更近的道路，渐渐地就会有更多蚂蚁被吸引到较短路径上来。如此反复进行一段时间后，就会有最多数量的蚂蚁在一条最短的路径上行进的现象。蚁群优化( antcolony optimization，ACO)算法作为一种群体智能优化算法，自从被提出后，在解决TSP (travelling salesman problem，旅行商问题)以及最短路径等问题中的优势得到了广泛认可，并且在其他领域得到了推广。与其他一些群体智能优

化算法一样，蚁群算法同样存在可能陷入局部最优、出现早熟停滞现象的问题。Stuzle T提出了“最大最小蚁群系统”，允许各个路径上的信息量进行规定范围内的动态变化，在解决TSP、QoS（quality of service，服务质量）问题中具有明显优势。吴斌等在蚁群算法基础上提出了相遇max-nun算法，提高了蚁群一次周游的质量，并结合分段求解方法，用于解决旅行商问题。

 蚁群算法是一种正反馈系统，路径上个体的增多会产生更多的信息素，而信息素的增加又会吸引更多的个体，通过这个过程使算法收敛。在对真实的蚂蚁行为进行人工模拟的同时，个体增加了存储信息的智能，这样蚁群就摆脱了盲目性，可以在离散的空间进行随机搜索。此外，蚁群算法还具有分布式、全局性等特性。

3.2算法模型

假定存在一个具有n个节点的网络模型，人工蚂蚁的数量为m，这些蚂蚁可以根据信息素的浓度和启发模式对下一节点的转移概率进行调整，已经经过的节点会存储在记忆表中，不会重复经过，当完成一次循环后，就会更新路径上的信息素数据。

寻找最优的过程包含局部更新和全局更新。在局部更新中，个体选择一个节点按照式(3)更新路径上的信息素。

 当所有个体完成循环后，会按照式(4)和式(5)进行全局范围内的更新。

3.3算法的改进

 蚁群算法在路径寻优方面具有先天优势，但其本身存在易出现早熟停滞、陷入局部最优的不足。

 改进的蚁群算法优化了信息素全局更新规则，可以更好地达到全局收敛，可表示为：

4改进蚁群算法求解最小跳数路由选择问题

 传统的最小跳数路由选择方法由汇聚节点首先通过洪泛算法向全部节点多播广播分组，分组在传播过程中进行计数，到达每一个节点后，反向传播就可以得到一个通路，而计数的目的就是找到跳数最少的路径。这种方法在每次通信过程中都会造成全部节点提前运行一次，大大消耗了能量和带宽资源。

 本文将改进的蚁群算法路径寻优的特点运用到最小跳数路由选择中，通过一次多播确定传感器节点之间的路由表连接情况，当某个传感器节点产生数据时，就会自动寻找经过节点最少的最小跳数路径到达汇聚节点。而由于蚁群算法的智能寻优特点，当传感器网络中某个通路中的节点损坏造成无法正常工作时，那么传感器网络就可以自动寻找其他通路向目标节点传递信息。

 改进蚁群算法求解最小跳数路由路径的流程如图2所示。

首先对单一节点信号传递路径进行模拟，假设某一节点位置感应到信息，将自动选择最小跳数路由路径传递至R20节点。

在图3中可以明显看出，当位于边缘的R1和R3节点接收到信号后，可以很好地找到最小跳数路径（不唯一），并传输至汇聚节点。

 如果在环境中同时有多点感应到信号，那么每个节点仍可以很好地找到各自的最小跳数路径，将信息传递至汇聚节点，如图4所示。

 而当网络中的某个传感器节点发生损坏不能正常工作时，蚁群算法可以迅速找到另外的次优路径。如图5所示，当R4节点损坏，则R1的信息将按照另外的最小跳数通路传输。

 通过仿真实验可以看出，基于改进蚁群算法的路由最小跳数路径选择方法可以很好地完成无线传感器网络节点间的路由选择，并且当网络中节点发生损坏时，算法可以很好地随机应变更改线路。选择最小跳数路径可以很好地节约能量和带宽资源，而算法的顽健性使网络情况发生变化时也可以很好地完成路径优化选择。

6  结束语

无线传感器网络在社会发展中得到了广泛应用，尤其对物联网的发展具有积极推进作用。利用改进蚁群优化算法对网络最小跳数路由路径进行选择，仿真实验证明了其有效性，使无线传感器网络在应用中可以更好地进行能量和资源优化，有利于其进一步发展。但任何方法都不是完美的，如优化算法可能增加时间消耗等，这将是进一步研究的问题。