一种新的无线传感网络路由算法的仿真设计与研究

王林林

（中山火炬职业技术学院，广东中山528436）

一种新的无线传感网络路由算法的仿真设计与研究

王林林

（中山火炬职业技术学院，广东中山528436）

本文主要是对关于网络路由算法中的蚁群算法进行研究与分析，并对其仿真数据的报文进行研究.首先分析了互联网络中的无线传感网络的数据传输与跳转特性，提出了基于网络拓扑结构的平面路由协议中扩散法的路由协议算法以及层次路由协议中的LEACH协议，在分析中发现这些算法过重依赖于网络节点的功能，在性能方面表现不好.在此基础上，详细阐述了蚁群算法的基本情况、算法原理、实现过程以及在无线传感网络中作为路由协议基本算法的在执行效率上的不足，并提出了添加节点能量值为影响因素的优化算法，最后对基于蚁群算法的路由协议的无线传感网络的传输仿真进行报文设计，从而实现无线传感网络的数据传输.

无线传感网络；蚁群算法；信息素；通信报文

1　引言

随着科学技术的不断发展，人们对于生活质量和物质水平的要求越来越高.互联网络以其特有的连通性和开放性，已经成为人们生活的基础设施，成为人们日常生活所需的必不可少的一部分.而互联网络的实现，在网络末端是由各个不同类型的网络构成，通过将不同类型的终端设备信息连接到互联网络中，来实现网络数据传输与共享.在互联网络中，无线传感网络是目前较为新型的网络，它是集传感与信息转换技术、嵌入式技术以及分布式信息处理技术与于一体的特有的新型无线网络，在民用、军工、医疗、科研等各个领域中得到了广泛的应用.对于无线传感网络的数据传输与跳转的实现，是需要基于相关协议的网络软件和硬件设施来实现，而这些网络软件和硬件的设计与实现，则需要遵循专门的路由协议.网络路由协议本身，规定了数据传输的格式、方式、传输过程以及跳转规则等，按照专门的网络协议，才能实现无线传感网络数据的准确传输与路由跳转.所以对于无线传感网络路由算法的研究与仿真设计，对于了解与学习无线传感网络的工作机制与具体实现来说，具有非常重要的现实意义.

2　无线传感器网络的路由协议

无线传感网络属于互联网络的子网络，是在互联网络的末端实现不同类型的网络终端设备的数据接入和传输的较为新型的无线网络系统.无线传感网络通过嵌入式的信息传感、采集设备和数据传输设备，将无线传感网络终端设备的数据接入到互联网络中，与其他服务器或网络设备进行数据传输与交换.无线传感网络的主要结构包括了负责信息收集的汇聚节点、信息转换的传感节点、信息接收节点以及数据传输任务的管理节点，通过大范围随机的传感节点接收数据，通过其他接收节点，最终将数据传送到汇聚节点，经过互联网络或其他中转设备可实现数据传输到最终检测设备上.如图1.所示，为无线传感网络的节点组成示意图.

图1　无线传感网络节点组成示意图

在无线传感网络的硬件平台上，通过网络中各个通信协议，实现数据的传输与网络路由跳转.在无线传感网络中，网络路由协议是在不同的应用环境中有所差别的，大体上可以分为两类路由协议，分别是以网络拓扑结构为分层的平面路由协议、层次路由协议等，和以不同的应用目的而设计的QoS路由协、协商路由协议、耦合处理路由协议等.

在平面路由协议中，扩散法是常见的较为容易实现的算法.在无线传感网络中，当一个节点向目标节点发送数据时，该节点会同时向其附近的所有节点都发送一份相同的数据，这些节点在接收到该数据时，会分析出该数据是否为当前节点所需数据，如果是，按照同样的方法，向其附近的其他节点继续扩散，直至到目标节点.如图2，为屏幕路由协议的扩散法原理示意图.

图2　扩散法原理示意图

基于扩散法实现的网络路由数据转换，能够适应不同拓扑结构的网络，健壮性较高，资源浪费少，在无线传感网络中很容易实现.

基于层次路由协议中，LEACH协议（Low Energy Adaptive Clustering Hierarchy Protocol）是应用较为广泛的网络路由协议.LEACH协议以簇为单位，将无线传感网络进行均匀划分，而每个簇内部，选择一个网络节点作为簇头，该节点主要负责网络中的汇聚节点进行数据传输，而簇内部的其他节点，则负责信息数据转换与收集，并将最终数据传送至簇头节点.值得说明的是，LEACH协议对于簇内簇头节点的选取，并非固定式，而是采用动态循环的方式对簇内的所有节点进行选取，这样一样，簇头节点的信息汇总与发送的资源消耗则平均地分配到整个簇中，有效地利用了无线传感网络的资源利用率.簇头节点的选取的基本过程是首先簇内某个节点在0到1之间随机选取一个数值，然后与F(n)进行比较，如果小于该值，则此节点则为簇头节点.F(n)如下表达式.

其中，x为一个簇内某个节点能够成为簇头节点的可能性，一般以百分比形式显示，r为循环的次数，N为该簇内为当过簇头节点的集合.使用LEACH协议进行无线传感网络的数据传输时，首先确定簇，然后选定簇头节点，然后对各个簇头节点与基本网络建立传输调度与传输机制，最终实现各个无线传感网络的数据传输.如图3，是LEACH协议构建的网络拓扑结构示意图.

图3　基于LEACH协议的网络拓扑结构示意图

3　蚁群算法的路由协议

3.1蚁群算法简介

在无线传感网络实现的路由协议较多，功能也都较为齐全，但是就整个无线网络的能量消耗、服务质量、可靠性、鲁棒性等各个方面综合考虑，基于仿生学原理的蚁群算法则能够很好地在实现无线传感网络数据传输与跳转的前提下，将网络能量耗损、网络数据质量、鲁棒性等各个方面达到很好的标准.

蚁群算法是典型的仿生学算法，主要是仿照蚂蚁在觅食过程中寻找最短路径的思路来实现的算法.蚂蚁在觅得食物后，会返回到蚁巢中通知其他蚂蚁一起来搬运食物，而这只蚂蚁在返回到蚁巢过程中，会在路上释放信息素，以确定其他蚂蚁在出来觅食时能正确找到食物源.假如从食物到蚁穴之间，并非一条直线路程，而是有多条路径，那么初次时，可能会有不同的蚂蚁从不同的路径出发，而在众多的路径中，肯定存在一条最优的路径，能够让蚂蚁以最短的时间折返，而折返过程中，它们就会留下信息素，此时，其他路径的蚂蚁并会返回到蚁穴.而后续的蚂蚁，则会优先选择有信息素的路径去搬运食物，而如此过往之后，在最后路径上留下的信息素最多，而这条路径也就是食物与蚁穴之间的最优路径.从上述蚂蚁觅食的过程中可以发现，最优路径的选择是由路径上的信息素来决定，信息素越多，后续的蚂蚁选择这条路径的概率就越大，而折返之间则又释放更多的信息素.

蚁群算法在无线传感网络中的应用无论是从技术上还是从基本原理上是非常适合的，首先，蚁群算法是采用仿生学算法，蚂蚁本身没有思维，所有的动作全都来自于本能，而蚁群算法的基本理念就是采用蚂蚁本能的行为，与无线传感网络中的数据传输方式非常相似，采用蚁群算法最终使得无线传感网络中的数据自组织、自适应，并且能够根据不同的网络环境动态地寻找到最优的传输路径，大大降低了控制平台的应用，降低了无线传感网络的设计实施和维护成本.其次，由于基于蚁群算法的无线传感网络节点与传输路径，都是动态的、实时的，所以对于当前无线传感网络来说，传输数据的方式具有实时性，即方式永远是最优的.同时，对于无线传感网络中单一节点来说，计算与存储、能量供给等各个资源非常有限，蚁群算法使无线传感网络的节点突破了单一性，抛弃了单一节点的限制，每个节点只需要按照既定的简单的规则实现相应的功能，彼此之间相互协作最终形成了一个完整的整体，无论从计算能力、传输时间还是从能量耗损来说，都使无线传感网络实现质的飞跃.再者，基于蚁群算法路由协议的无线传感网络，每个节点包含了与之关联的所有路径的信息素浓度值，实际运行时，该节点的每条路径都有可能被通过，从整体来看，无线传感网络的连通路径是非常多样的.最后，蚁群算法路由协议使得整个网络的拓扑结构能够灵活动态调整，无论是节点添加或更换，还是节点或路径破坏失效，在蚁群算法的路由协议中，这些都不会改变整体结构，通过信息素值的设定，网络是不会受外界环境变换而影响正常工作的.

3.2蚁群算法建模

蚁群算法就是以蚂蚁觅食寻找最优路径的方法来设计整个计算过程.以旅行商问题为例，假如一共有n个城市，要求选择出从一个城市出发，对其他城市都要经过一次，最后能够回到出发城市的最短的路径.假设有m个蚂蚁，在初始化时，各个城市之间的路径上信息素的浓度值都为零.那么在某个时刻t，蚂蚁a从城市x到城市y移动的概率为：

在上式中，Paxy为蚂蚁a从x城市移动到y城市的概率.α与β分别为路径的信息素与路径启发因子，二者会对蚂蚁a的路径选择做出影响，G则代表蚂蚁a为经过的城市.假如x，y城市距离为d，则ηxy=

随着时间的推移，在蚂蚁a走完了所有的城市之后，路径上的信息素会不断挥发，假设其挥发参数为z，那么在经过n时刻后，路径上的信息素就会不断挥发，则信息素影响的参数将会动态变化，变化公式如下：

3.3蚁群算法流程

按照蚁群算法的基本原理，以及蚁群算法的仿生学过程，蚁群算法的基本流程就是按照蚂蚁觅食过程的来设计.其大致过程包括三个步骤，第一就是初始化整个蚁群数据以及路径信息素数据，第二阶段就是设置路径上信息素添加与挥发的规则，即蚂蚁走过路径之后的信息素添加的规则算法以及信息素的挥发算法，第三阶段设定蚂蚁的判断路径和添加信息素，即蚂蚁根据路径信息素浓度判断路径以及走过路径后增加信息素值的算法.其具体的流程如下：

（1）初始化所有参数变量，设定路径信息素值为零，设定蚂蚁留下信息素和信息素挥发的参数与τxy

（2）随机分配蚂蚁总数，使其在所有城市内

（3）记录当前所有蚂蚁的所有位置信息

（4）计算每个蚂蚁的状态移动概率，选择概率最大值的城市最为下一个移动目标城市

（5）汇总所有蚂蚁的最优解，整合数据，记录最优解

（6）按照信息素值变化规则修改路径信息素值

（7）判断是否满足结束条件，如果是，输出当前最优解，如果否则跳至第三步

如图4所示，为蚁群算法的基本流程

图4　蚁群算法流程

3.4蚁群算法的优化

在蚁群算法实现路由协议，应用到无线传感网络之后，会通过信息素值的不断积累和动态更新，很容易找到网络传输的最优路径，但是在性能方面却有所不足，例如，蚁群算法执行时间较长，而且很难进行更深层次的搜索，尤其是在节点能量变化之后，对算法的执行效率更是影响较大，所以在最初的蚁群算法上，需要进行改进.

首先是选择下个节点的概率计算，改进的计算公式如下：

在上述公式中，E0为无线传感网络节点的初始电量值，Exy表示该无线传感网络节点当前可用电量值，θ1与θ2表示两个加权值，分别为路径距离以及节点当前可用电量的影响比例，二者和为1.这样一样，蚂蚁在选择下一个目标节点时，需要考虑的因素就要添加上路径距离以及节点的可用电量.

4　基于蚁群算法的路由协议仿真的报文设计

基于蚁群算法实现的无线传感网络路由协议的仿真，完全是按照蚁群算法的基本定义变量以及实现流程，来设计相应的数据和流程，在一定的平台上进行实现.

基于蚁群算法的描述和改进后蚁群算法的概率计算公式，在一个无线传感网络的路由协议仿真中，需要有以下几个变量，存储网络节点的信息表和变量，存储走过路径长度（经过节点个数）的变量，节点电量的原始值与当前值的变量，记录路径的信息素浓度值的变量，蚂蚁信息表和变量，单个蚂蚁所处的节点变量以及下一个目标节点的变量，为了方便使用与计算，将无线传感网络的节点属性值设定节点信息表，包含节点ID值，当前节点到汇聚节点的节点个数，当前节点电量值；相邻节点信息表，包含相邻节点ID，二者之间路径的信息素浓度值，以及相邻节点的可用电量值；蚂蚁信息表，包含蚂蚁ID值，当前所处节点ID以及目标节点ID.

其次，为了能够是整个无线传感网络实现蚁群算法的基本功能，需要通过发送数据报文来模拟蚂蚁觅食的行为，那么在网络路由协议模拟仿真时，需要设计专门的各种报文来实现相应的操作.如蚂蚁觅食报文，节点向汇聚节点反馈数据报文，能量节点报文等.首先，蚂蚁觅食报文是最主要的报文形式，也是基于蚁群算法实现的网络路由协议的无线传感网络中传输数据相对较多的数据格式之一.那么在设计蚂蚁数据报文时，首先有专门的字段表示该报文类型，然后还有其他字段信息表示当前报文经过的节点数，以及源节点地址信息与目标节点地址信息，从而形成一个完整的数据报文格式.反馈数据报文的设计，同样首先需要有字段保存报文类型信息，然后有专门的字段包含想汇聚节点发送信息的源节点信息，最后包含数据信息以及相关的控制、校验等控制配置信息，从而形成为完整的数据报文.能量报文是更新相邻节点电量值的报文数据，首先需要专门的字段包含报文类型，然后是包含报告电量信息的节点ID值以及当前可用的有效电量值的数据信息，从而形成完整的能量报文.通过设计的相应报文信息，按照蚁群算法的基本流程，就可以对蚁群算法的路由协议进行仿真.

5　总结

蚁群算法实现的无线传感网络路由协议，主要是依靠仿生学的蚂蚁觅食的基本原理来实现，通过设计专门的数学模型，来详细分析其基本的工作原理，通过对改进后的蚁群算法的仿真，可以学习到无线传感网络中数据传输的基本机制，对于学习研究无线传感网络以及路由协议设计，进而提升和优化路由算法，都是非常有帮助的.

〔1〕郭彦芳.基于蚁群算法的典型路由协议的比较研究[J].无线电通信技术，2015(04).

〔2〕沈琳.基于遗传蚁群算法的QoS多播路由算法在AdHoc网络中运用方法的研究[J].电子技术与软件工程，2015(13).

〔3〕李锋.改进蚁群算法在WSN路由优化中的应用[J].微处理机，2015(04).

〔4〕孟建东.基于改进蚁群算法的计算机网络路由优化研究[J].数字技术与应用，2015(08).

〔5〕杨婷，白云丽，姜新华.基于改进蚁群算法的无线传感器网络路由[J].内蒙古大学学报(自然科学版)，2015(01).

〔6〕郑波，崔宝同.基于混沌粒子群与蚁群算法的WSN路由协议[J].电子设计工程，2015(01).

〔7〕S.Nakrani,C.Tovey.On honey bees and dynamic server allocation in internet hosting centers. AdaptiveBehavior-Animals,Animats,Software Agents,Robots,Adaptive Systems.2004.

〔8〕MichelGendreau,Fran?oisGuertin,Jean-Yves Potvin,RenéSéguin.Neighborhoodsearch heuristicsforadynamicvehicledispatching problemwithpick-upsanddeliveries[J]. Transportation Research Part C.2006(3).

〔9〕李靖平.基于802.11MAC协议的无线传感器数据流优先级模型.通化师范学院学报,2014(6):15.

TP212；TP393

A

1673-260X（2016）03-0032-04

2015-12-30