基于萤火虫算法的无线传感器网络的分簇路由协议

刘奇奇，张曦煌

(江南大学物联网工程学院，江苏无锡214000)

0 引言

无线传感器网络(WSNs)是由在空间上相互离散的各类传感器相互协作构成的传感器网络系统，使得分布于不同场所的数量庞大的传感器之间能够实现更加有效、可靠的通信。由于无线传感器网络节点的电量有限，且由于条件限制难以补充或更改，故延长无线传感器网络的存活时间是目前无线传感器网络研究的主要问题。鉴于无线传感器网络的特殊性，为无线传感器网络设计特有的路由协议具有非常重要的意义。目前研究人员已经提出多种路由协议，其中比较经典的路由协议比如 LEACH［1～4］协议、PEGASIS协议等，这些协议都是基于层次思想，通过分簇等手段减少能量损耗，延长网络存活时间。

但是由于经典LEACH算法簇头选举是随机的，可能导致最后的分簇的不合理性，使网络可能过早死亡，故合理的分簇机制是十分必要的。本文提出了一种基于萤火虫算法的分簇机制，通过萤火虫算法寻求最优解，对网络分簇进行优化，使网络节点能耗均衡，延长网络寿命。

1 萤火虫算法

萤火虫算法［5～7］(firely algorithm，FA)是一种启发式算法，灵感来自于萤火虫的闪光行为。萤火虫的闪光，其主要目的是作为一个信号系统，以吸引其他的萤火虫。萤火虫算法是通过模拟萤火虫的群体行为构造出的一类随机优化算法。其仿生原理是用搜索空间中的点模拟自然界中的萤火虫个体，将搜索和优化过程模拟成萤火虫个体的吸引和移动过程，将求解问题的目标函数度量成个体所处位置的优劣，将个体的优胜劣汰过程类比为搜索和优化过程中用好的可行解取代较差可行解的迭代过程。其假设为:

1)萤火虫不分性别，它将会被吸引到所有比它更亮的萤火虫那去;

2)萤火虫的吸引力和亮度呈正比，对于任何两只萤火虫，其中一只会向着比它更亮的另一只移动，然而，亮度是随着距离的增加而减少的。

在该算法中，萤火虫彼此吸引的原因取决于两个要素，即自身亮度和吸引度。其中，萤火虫发出荧光的亮度取决于自身所在位置的目标值，亮度越高表示所处的位置越好，即目标值越佳。吸引度与亮度相关，越亮的萤火虫拥有越高的吸引力，可以吸引视线范围内亮度比其弱的萤火虫往自身方向移动。如果发光亮度相同，则萤火虫各自随机移动。亮度和吸引度与萤火虫之间的距离呈反比，都随着距离的增加而减小，这相当于模拟了荧光在空间传播时被传播媒介吸收而逐渐衰减的特性。

2 基于萤火虫算法的分簇路由协议

由于开始萤火虫都是随机选择，可能会导致算法搜索太慢，故对于萤火虫的选取的优化是必要的。

2.1 萤火虫的选取

自组织神经网络映射(SOM)是一种非监督的神经网络，可以对样本数据进行初步的分类和聚类，故本文采用SOM对所有传感器节点进行初步的聚类，进而对萤火虫的选取进行优化。

假设在M×M的区域内存在N个传感器节点，对于每个传感器节点 C(i)，其对应的属性为(xi，yi，Ei)，其中 xi为节点X轴坐标，yi为Y轴坐标，Ei为节点当前剩余能量。

对于每一个节点，通过对节点属性归一化处理，作为输入样本。本文中采用线性归一转换，即

归一转换后每个传感器节点C(i)对应于输入样本T(i)，通过自组织神经网络完成初步聚类，获得输出集合S={s1，s2，…，sn}，n 为初步聚类中心数目。

2.2 基于萤火虫算法的分簇

根据文献可知，最优簇头数为

对于由SOM获得的输出集合S和最优簇头数K，选取G个萤火虫样本，其中

而对于G个萤火虫样本，可以有以下定义:

定义1 假设第i个萤火虫定义为F(i)={CH1i，CH2i，…，CHKopti}。

定义2 网络簇集合为CCHi，即簇头CH所在簇集合。

在传感器网络中，节点剩余能量、节点之间的距离都是影响分簇的重要因素，故给出萤火虫荧光素函数YS(F(i))

在萤火虫算法中，亮度体现了萤火虫所处位置的优劣并决定其移动方向，吸引度决定了萤火虫移动的距离，通过亮度和吸引度不断更新，从而使目标值不断优化。

对于萤火虫，其亮度会随着距离的增加而渐渐减弱，萤火虫亮度计算公式为

其中，YS(F(i))为计算的荧光素，r为距离影响因子，d为两只萤火虫的距离，d=‖F(i)-F(j)‖。

萤火虫的吸引度决定了移动的距离，其计算公式为

其中，H0为最大吸引度，设为1.0，r和d同上。

通过萤火虫亮度和吸引度，可以获得萤火虫的移动更新公式为

其中，β为步长因子，x为坐标。

综上所述，基于萤火虫算法的分簇算法流程如下:

1)对所有传感器节点，通过自组织神经网络将节点初步聚类，从而获得萤火虫样本集合。

2)根据最优簇头数和萤火虫样本集合，生成每一个萤火虫。

3)对于每一个萤火虫，计算其他萤火虫的相对亮度，选择亮度大于自身的萤火虫，作为其移动的方向。

4)根据步骤(3)选择萤火虫的吸引度，计算萤火虫的更新距离，更新萤火虫的位置。

5)对于更新后的萤火虫，若满足搜索精度或达到搜索次数，则终止搜索;否则，继续执行步骤(3)。

6)输出簇头结果。

2.3 数据传输阶段

在传统的Leach协议中簇头融合数据后一般通过单跳和基站通信，把获取的数据传输给基站，这样导致如果簇头距离基站很远，传输消耗能量将非常大，故采用改进的簇头多跳路由协议［8］是必要的。

路由簇头:根据公式(8)选择距离最近的Route(num)个簇头充当路由簇头，路由簇头将负责传输其他簇头传输过来的数据

对其他簇头，则向全局广播信息，广播半径从d0开始依次增加，若在此范围内有其他簇头CH(i)回应广播簇头，且d(CH_BS)＞d其他(CH_BS)，则将簇头CH(i)加入此簇头的邻居节点中，并终止广播;否则，增大广播半径，直到有簇头回应，从而获得每个簇头的邻居簇头表。

对于每个簇头，若其邻居簇头表中含有路由簇头，则将数据直接发送给路由簇头;若没有邻居簇头，则将数据发送给邻居簇头，并循环路由。

3 仿真与结果分析

3.1 仿真环境

在边长为200 m×200 m的正方形区域内，随机分布200个传感器节点，所有传感器节点能量有限，位置固定不变。仿真采用Matlab 2010b模拟，仿真具体环境为:基站坐标为(100，250)m;初始能量为0.5 J;发送与接收消耗能量为50 nJ·bit-1;数据包为400 bit;数据融合消耗能量为5 nJ·bit-1;光吸引强度系数为1.0;步长因子为2。

3.2 仿真结果

实验中随机生成200个网络节点。

网络节点初始分布如图1。

图1 节点初始分布Fig 1 Initial distribution of node

第一个节点死亡、第50个死亡、第100个节点死亡、所有节点死亡时间如表1所示。

表1 节点死亡时间Tab 1 Death time of nodes

图2为经典LEACH算法和本文算法的比较，通过仿真实验可以看出:本文算法第一个节点死亡时间相对推迟，这是因为本文算法的分簇相对于LEACH来说更加的合理:LEACH算法的簇头选举是随机的，导致分簇可能不是最优，而本文通过萤火虫算法寻求最优解，使分簇更加合理。

4 结束语

图2 算法比较Fig 2 Comparison of algorithms

本文采用萤火虫算法，通过迭代获得最优解，以进行合适的分簇，同时由于萤火虫样本初始是随机的，会造成最优解搜索过慢，故一开始通过自组织映射神经网络对样本数据进行初步的处理，在数据传输阶段则通过采用多跳路由，仿真表明:本文算法在一定程度上改善了网络存活时间。

［1］Heinzelman W，Chandrakasan A，Balakrishnan H.An application-specific protocol architecture for wireless microsensor networks［J］.IEEE Transactions on Wireless Communications，2002，1(4):660-670.

［2］宋 文.无线传感器网络技术与应用［M］.北京:电子工业出版社，2007.

［3］孙利民，李建中，陈 渝.无线传感器网络［M］.北京:清华大学出版社，2005.

［4］任丰原，黄海宁，林 闯.无线传感器网络［J］.软件学报，2003，14(7):1282-1291.

［5］吴昌友，王福林，马 力.一种新的改进粒子群优化算法［J］.控制工程，2010，17(3):359-362.

［6］牛小娇，吕程林.一种基于LEACH协议的分簇路由算法［J］.计算机技术与发展，2011，21(7):13-16.

［7］刘长平，叶春明.一种新颖的仿生群智能优化算法:萤火虫算法［J］.计算机应用研究，2009，28(9):3295-3297.

［8］Hooman Ghaffarzadeh.Two-phase data traffic optimization of wireless sensor networks for prolonging network lifetime［J］.Wireless Network，2014，20:671-679.