粒子群优化算法实现的WSN路由协议的可靠性验证

王晓慧

（太原工业学院电子工程系， 山西 太原 030008）

无线传感器网络（WSN） 是由很多传感器组成的能监测环境的一种新型信息获取系统，比如监测环境温度和湿度、土壤成分等。无线传感器网络已广泛应用于智能家居、环境监测、医疗护理、军事、城市交通等多个领域[1]。 但是，通常WSN传感器节点体积微小，并且只能通过自带的电池供电，对于大多环境比较复杂的情况，监测人员很难为传感器节点更换电池，如果个别节点任务量大，能量耗尽，会使整个网络失去意义；然而，传感器节点的能量消耗主要体现在无线通信模块，因此，设计一个好的WSN路由协议能降低传感器节点的能耗，并且能均衡所有节点的能耗，延长网络寿命，避免出现边缘节点能量过早耗尽而影响整个网络性能。

1 原始粒子群算法

粒子群算法(Particle Swarm Optimization，PSO)是一种算法简单、收敛快、易实现的新兴智能方法，源于鸟类捕食的群体行为研究：一群鸟搜寻同一块食物，所有鸟仅知道自己与食物的距离，而不知道食物的具体位置，所以通过先找到距离食物最近的鸟再来找食物。由于大多分簇算法在选择簇头时或者随机选择或者只考虑到簇头节点的状态，从而影响到网络的生命周期，基于此粒子群算法能综合各指数找到最优的簇头节点。在WSN中每个传感器节点就是一个“粒子”，通过粒子群算法初始化后，通过叠代方式找到最优解。即粒子通过跟踪两个极值来更新自己：一个是粒子自身找到的最优解（个体极值Pid）；另一个是整个种群目前找到的最优解（全局极值Pgd），找到这2个最优解后，粒子根据公式（1）和公式（2）更新自己的速度和位置：

式 中 ：t为迭代次数；vid、 xid分 别 为 粒 子i的 速度和位置；r1， r2是 0和1之间的随机数；c1和 c2是控制粒子移动速度的系数；w控制粒子历史值对当前值的影响程度[2,3]。

2 PSO-LP协议的特点

PSO-LP协议是利用改进的粒子群算法为基础选取簇头，采用双簇头和单簇头结合的工作方式，并且簇间路由协议实行单路与多路相结合设计的无线传感器网络路由协议算法，由此提高网络节点的能量利用率，延长整个网络的生命周期。

2.1 粒子群算法的改进

粒子群算法中的适应度函数（下页公式（3））是评价最优解的综合因子，因此，通过改进PSO的适应度函数来提高WSN路由协议选取的簇头质量（最优位置、最高能量等因素），PSO-LP的适应度函数综合考虑因素：f1表示候选簇头节点当前的剩余能量（显然，节点剩余能量越高，其被选为簇头后，工作效率越高）；f2表示当选簇头与簇内成员节点的平均距离（由于簇内节点间数据传输消耗的能量与节点间的距离成正比，故f2越小，整个网络能耗也越小）；f3评价簇头节点对网络均衡性的贡献，如图1所示（选簇头时在考虑f1和 f2的前提下，如果网络中簇头距离能量较低的节点更近一些，使网络提高低能量节点的能量利用率，因此更加均衡了整个网络能耗，避免网络空洞的出现）；f4等于当选簇头与基站（S）的最大欧式距离除以基站至网络中心（N）的距离。由此，适应度函数（T）可以定义为公式（3）：

图1 两种簇结构

2.2 簇头节点的选择及主、从簇头的分配

为了解决网络中节点间剩余能量不平衡的问题，PSO-LP协议在同一个簇选取主、从2个簇头，2个簇头分工合作。网络初期：计算粒子群算法的适应度函数值，选取主、从簇头，主簇头的主要工作是收集簇内成员节点的信息并融合后将其直接发送至基站或通过最近的从簇头发送至基站；网络中期：同一簇的2个簇头互相维护彼此的信息，如果在实际应用中某个簇头由于异常原因失效或者能量耗尽时，由同一簇的另一簇头同时担任主、从簇头的功能，从而避免信息混乱和网络盲区的出现，提高网络的稳定性；网络后期：当2个簇头都失效后，再进行新一轮的簇头重选，通过延长网络簇头重选的周期，从而延长网络数据稳定传输的时间，提高网络生命周期。

2.3 数据传输阶段

PSO-LP协议的数据传输分为簇内数据传输和簇间数据传输2个过程。

1）簇内数据传输。簇内数据传输为同一个簇内成员节点间的数据传输，与LEACH协议中传感器节点进行数据传输的发送、接收、空闲和休眠的状态类似，即节点在发送和接收信息的时间之外，可以处于休眠状态，从而很好的节约单个节点的能量[4]。

2）簇间数据传输。簇间数据传输即簇头节点将本簇成员融合的数据发送至基站的过程，设为单跳传输和多跳传输：当主簇头到基站的距离小于或等于d0（假设所有主簇头到基站距离的平均值为d0）时，主簇头将信息直接传送给基站，形成了单跳的簇间传输；当主簇头到基站的距离大于d0时，主簇头先将信息传送给最近的从簇头，从簇头再通过粒子群算法搜索最优路径将信息传送到基站，形成了多跳的簇间路由。通过簇内和簇间数据传输的分工合作，避免某些簇头因工作任务大而过早死亡，避免网络盲区的过早出现，从而提高了路由的健壮性，也很好地改善了LEACH协议中唯一的单跳数据传输方式带来的缺陷。

3 对PSO-LP协议的可靠性验证策略

无线传感器网络路由协议主要针对传感器节点能量有限的问题提出的，以降低网络节点的能耗来延长网络运行时间的。针对PSO-LP协议的特点，主要从以下三方面来验证协议的可靠性：

1）生命周期。生命周期是评价无线传感器网络性能的一个重要指标。不同的应用环境，生命周期的定 义也不同，一般将网络运行一段时间后监测区域内存活的节点数量来描述生命周期；本文中生命周期定义为从网络开始运行到一半节点死亡所延续的时间[5]。

2）网络剩余总能量。指网络运行一定时间后所有传感器节点剩余能量的总和。

3）簇头节点分布。通过统计监测区域内簇头总数目，分析簇的大小和簇头分布的均匀性，从而降低通信协议的开销，以适应动态变化的网络拓扑结构。

因此，传感器节点的自身因素、周围变化的环境都会影响网络的生命周期和剩余总能量，为延长网络生命周期，在路由协议设计时首要考虑的还是如何降低节点的能量消耗，能量信息能够比较直观反映WSN路由协议的性能指标。

4 仿真及仿真分析

4.1 仿真环境

通过MATLAB2008软件对PSO-LP路由协议的性能进行了仿真验证。将模拟环境设置为一个正方形，并设置2个不同大小的区域，即对区域面积和节点数量增大时，簇的数量也比较多而容易出现信息冗余和重叠的情况下，将2个实验做对比分析，从而验证PSOLP算法不受节点数目和监测区域面积大小的影响。2个实验中相同的主要参数为：每个节点的初始能量均为0.5 J，c1= c2=2，w=0.9，rand值在运行过程中动态地随机给出，评价因子取a1=0.25，a2=0.25，a3=0.3，a4=0.2。

4.2 仿真结果及分析

1）实验一。在100 m×100 m的正方形区域内随机分布100个传感器节点运行LEACH，LEACH-PSO，PSO-LP协议。种群规模Q=20个，rmax=3 500轮。

如图2-1、图2-2分别是基站位于中心时100个节点运行3种协议后的网络生命周期和剩余能量情况。结果表明，执行PSO-LP算法相比LEACH和LEACH-PSO，网络的生命周期得到较大的延长。

如表1是由图2-1分别对网络中第一个节点、一半节点、80%节点死亡所需要的时间进行比较。可以看出，若以50%节点死亡轮数作为生命周期，PSO-LP比LEACH算法延长了近80%，比LEACH-PSO算法生命周期延长了47%。运行PSO-LP协议的网络工作主要在一半节点死亡之前，从网络一半节点死亡到80%节点死亡这段时间，PSO-LP运行时间最短，也说明PSOLP中网络节点能耗更均衡。图2-2的结果是执行PSOLP后，网络的剩余能量总是大于LEACH和LEACHPSO协议。

图2 100个节点实验结果

表1 生命周期比较 轮

2）实验二。200 m×200 m的正方形网络监测区域内200个传感器节点运行LEACH，LEACH-PSO，PSO-LP协议，Q=40个，rmax=5 000轮。

如下页图3-1、3-2分别是200个节点基站位于中心时3种协议的实验结果。同样的结果，图3-1显示了PSO-LP协议的生命周期比LEACH和LEACH-PSO得到延长，图3-2显示在任何周期PSO-LP协议剩余总能量都比LEACH和LEACH-PSO高。

图3 200个节点实验结果

由以上2个实验可见：增加节点数目、扩大网络区域面积并不影响PSO-LP的有效性，因为PSO-LP利用了粒子群算法智能化选取簇头、合理分配簇结构的背景，有效地节约了时间和节点能耗，并能提高大区域内节点能耗的均衡性，很好地避免网络空洞的出现。

4.3 簇头数目分布统计

据统计，1个无线传感器网络中最优簇头节点数目应为整个网络节点数目的5%，本文通过比较PSOLP与LEACH协议中每轮的簇头数目来分析最优簇头数目（由于PSO-LP协议采用双簇头，但主、从簇头数目相同，因此只统计主簇头数目）[6]。

结果如图4为LEACH协议中每轮的簇头总数目，其中簇头总数在4~6个之间的约占总轮数的51%，簇头1~3个约占总轮数的32%，簇头6~10个约占总轮数的17%。图5是对PSO-LP协议的统计，每轮簇头数目大多数在4~6个，其占总轮数的69%，而簇头数目在1~3个的仅占总轮数的17%，簇头数目在7~10个的占总轮数的14%，其中簇头数目为1、2、9、10的轮数几乎没有，由此得出，PSO-LP协议通过粒子群算法选取的簇头更符合WSN路由协议最优簇头数目的要求（5%）。

图4 LEACH簇头总数统计

图5 PSO-LP簇头总数统计

5 结语

通过优化粒子群算法实现了WSN的优化分簇，又通过选择主、从2个簇头，并在数据传输阶段分工合作，进一步做到能耗均衡，达到延长网络生命周期的效果。最后通过MATLAB2008仿真实验，设置两个不同区域大小、不同节点数量的实验，分别将PSO-LP协议的生命周期、网络能耗和最优簇头数目等性能方面与经典的LEACH和LEACH-PSO做了比较，结果充分表明了PSO-LP的优越性：说明PSO-LP不仅相对LEACH和LEACH-PSO提高了性能，而且也适合应用于大面积、大数量的无线传感器网络，如对100个节点的网络，PSO-LP的生命周期比LEACH延长约80%，而200个节点的网络，PSO-LP的生命周期比LEACH延长近150%。

[1] 王晓慧,胡 彧 .利用粒子群实现能耗均衡的网络主从簇头分簇路由协议[J].中国科技论文在线,2011(5):401.

[2] 肖刘军,邓平.一种基于位置和能量的 WSN 改进分簇协议[J].通信技术,2010,43(8):43-45.

[3] 侯志荣,吕振肃.基于MATLAB的粒子群优化算法及其应用[J].计算机仿真，2003,20(10):68-70.

[4] 苏炳均,李林. 粒子群优化的无线传感器网络仿真研究[J]. 计算机仿真，2010,27(9):150-152.

[5] 苏淼，钱海，王煦法.基于蚁群的无线传感器网络双簇头算法[J].计算机工程，2008,34(13):174-177.

[6] 周冬鑫,金文光,容志能.基于分层的无线传感网络多跳分簇路由算法[J].传感技术学报,2011,24(1)：73-78.