基于人工蜂群算法的无线传感器网络路由协议

，，2， ，

(1.浙江工业大学 信息工程学院，浙江 杭州 310023；2.金华市中心医院，浙江 金华 321000)

无线传感器网络(Wireless sensor network, WSN)是由一系列微小的自主节点组成，具有组网灵活、监测精度高、部署迅速、容错性好、抗毁性强等优点，在军事战争、环境科学、灾难救援、智能家居、医疗卫生等领域具有广阔的应用前景[1-3].研究人员长期对生物种群进行观察研究，发现一个有趣的现象：自然界中某些生物个体表现出的行为非常简单，但当个体间相互协作所表现出的行为特征非常复杂，而不仅仅是个体行为简单的叠加[4-5].研究者根据不同的生物群体表现出的不同行为提出了不同的群体智能算法，包括粒子群算法(Particle swarm optimization, PSO)[6]、蚁群算法(Ant colony algorithm, ACA)[7]、人工鱼群算法(Artificial fish school algorithm, AFS)[8]、细菌觅食算法(Bacterial foraging optimization, BFO)[9]、人工蜂群算法(Artificial bee colony algorithm, ABC)[10]等.蜂群的自组织模拟模型最早由Seeley于1995年提出，后来Karaboga将蜂群算法成功应用于函数的极值优化问题，系统的提出了人工蜂群算法，Basturk等在2006年将人工蜂群算法理论用于解决优化问题，得到了很好的结果.

节点间通信消耗了网络的大部分能量，采用合理的路由方式可以减少能量消耗.为了延长整个网络的寿命，结合人工蜂群算法和图论中的最短路径树的思想对LEACH协议进行改进，提出一种新的路由协议.利用改进后的人工蜂群算法完成网络中簇首节点的选择，解决LEACH协议中簇首节点分布不均匀的问题；根据需要在簇内生成最短路径树，使簇内每一个节点与簇首节点通信的代价最小，从而减少整个网络的能量消耗.

1 人工蜂群算法

在人工蜂群算法中，将蜜蜂分为引领蜂、跟随蜂和侦察蜂三种，其中引领蜂的数量与食物源的数量相等.初始化阶段，随机产生N个解作为食物源的位置，然后对解进行评估，得到适应度fitness，适应度大小表示食物源的质量好坏[11].

引领蜂位置的更新公式为

Yi(t+1)=Yi(t)+δ(Yi(t)-Yk(t))

(1)

式中：Yi(t+1)为新产生的第i个食物源的位置；Yi(t)为原来的第i个食物源的位置；δ为[-1,1]之间的随机数；i,k∈{1,2,…,N},i≠k.

引领蜂在蜂巢内的舞蹈区，将食物源的信息告诉给跟随蜂，跟随蜂根据食物源的适应度选择食物源.

(2)

式中：Fi为第i个食物源的适应度大小；pi为第i个食物源被跟随蜂选中的概率.

随着采蜜工作的进行，食物源的丰富程度会降低，可能出现食物源枯竭的情况.为防止这种现象发生，若在限定循环次数后食物源适应度仍没有得到改善，则放弃该食物源，对应的引领蜂就变成侦察蜂，然后产生一个新的食物源位置，即

Yi=Ymin+η(Ymax-Ymin)

(3)

式中η为(0，1)之间产生的一个随机数.

2 基于ABC的WSN分簇算法

LEACH协议是无线传感器网络路由协议中非常重要的一种层次型路由协议.在LEACH协议引入了“轮数”的概念，每一轮都需要重新选择簇首节点，且每一个节点当选为簇首节点的概率相等.通过分簇的方式将整个网络的能耗均衡的分配到各个节点，从而提高了整个网络的寿命.与平面路由协议相比，LEACH协议具有非常明显的优势，但簇首节点按随机方式选择，无法确定每一轮簇首节点在网络中分布的位置，可能会出现当选的簇首节点聚集在一块的情况.网络中簇首节点分布不均匀，会使某些节点必须与较远的簇首节点进行通信，增大了通信时的能耗.另一方面，在簇首节点选定后，LEACH协议采用TDMA方式使簇首节点与簇内每一个节点直接通信，这种通信方式对于离簇首节点较远的节点来说能量消耗太大，容易造成节点的快速死亡.为减少这两方面问题对网络的影响，通过人工蜂群算法来选择网络中的簇首节点，在簇首节点确定后，根据图论中的最短路径思想，在簇内以簇首节点为树根建立一颗最短路径树，使每个簇内节点与簇首节点通信时所消耗的能量最少.

2.1 人工蜂群算法选择簇首节点

无线传感器网络中节点消耗的总能量主要取决于节点通信所消耗的能量，而节点通信消耗能量由通信距离决定[12].要保证整个网络消耗的总能量最少，就要确保每个簇内节点到簇首节点通信所消耗的能量与簇首节点到基站通信所消耗的能量的和最小.对于ABC算法，只要能够构造出合适的适应度函数，就可以得到最优解.

Friis自由空间方程式表明：在自由空间环境中，节点天线的接收功率为

(4)

式中：P1，P2分别为发射功率和接收功率；G1，G2分别为发射端增益和接收端增益；λ为工作波长；d为节点间的距离.

由式(4)可知：节点之间的距离可以通过测量接收端和发射端的信号强度来获得，即

(5)

每个节点由于自身的硬件限制，只有在接收到的信号功率P2大于某一值S时才能正常的接收数据，结合式(4)有

(6)

对于一个具有n个节点的簇，消耗的总能量为

(7)

式中：i为节点号；d为簇内节点到簇首节点的距离；l为簇首节点到基站的距离.

由上面的分析可以得到应用于无线传感器网络中人工蜂群算法的适应度函数为

(8)

为保证簇首节点有充足的能量接收簇内节点发送的数据，并把接收到的数据发送给基站，在通过ABC算法选择簇首节点时应保证候选簇首节点的剩余能量大于接收簇内所有节点数据包消耗的能量与发送融合后的数据包到基站消耗的能量的和，对于最大剩余能量小于给定值的节点不能当选为簇首节点.

2.2 簇内生成最短路径树

LEACH协议在选定簇首节点后，簇首节点广播信息，通知其他节点加入.网络中其他节点根据接收信息的信号强度大小来选择簇首节点，从而完成簇的建立.簇首节点与每个簇内节点之间采用TDMA方式直接通信.由式(6)可以看出：节点通信时的发射功率与节点间距离的平方成正比，对于某些离簇首节点较远的节点直接通信会过多的消耗节点能量.相对于直接通信，采用多跳通信的方式消耗的总能量可能比直接通信消耗的能量更少，而且可以确保网络节点能量消耗更加均衡.根据最短路径思想，建立以簇首节点为根的最短路径树，使每个簇内节点发送数据到簇首节点能耗最小.

Dijkstra算法是图论中计算最短路径的经典算法，其思想是为每个节点v保留目前为止所找到的从源节点S到节点v的最短距离.只要确定了边的权值就能够通过Dijkstra算法在网络中构建最短路径树，边的权值Q由节点间的距离d和节点剩余能量Er共同决定，距离越大，边的权值越大；节点剩余能量越大，边的权值越小.

2.3 算法描述

为表述方便，将利用人工蜂群算法对LEACH协议中簇首节点的选择过程进行改进后的算法简称为ABCCR算法；将结合人工蜂群算法和最短路径树算法对LEACH协议进行改进后的算法简称为ABCCR-SPT算法.ABCCR-SPT算法与LEACH协议的主要区别在于簇首节点的选择过程和簇首节点与簇内节点之间的通信.网络节点部署完成后，节点以广播的方式向网络发送报文，通过式(5)计算节点之间的距离.基站收集网络中节点间的距离信息和节点的剩余能量信息后，通过ABC算法选择网络中的簇首节点，该计算过程是在基站内部完成.确定网络中的簇首节点后，按照节点间的距离大小和节点剩余能量大小把网络中其他节点分配给各个簇，然后利用Dijkstra算法以簇首节点为树根在各个簇内建立最短路径树路由表，基站将各个簇对应的树路由表发送给簇首节点，最后在各个簇内构建最短路径树.算法的主流程图如图1所示.

图1 算法主要流程

3 仿真实验

仿真实验是在理想情况下进行，假设节点在数据发送过程中不存在丢包现象，不考虑数据传输过程中重发、出错以及计算消耗的能量.建立Matlab环境，对协议进行仿真，设传感器节点个数为100，传感区域为300 m×300 m，节点随机分布在传感区域中，基站位置分别为(300，150)，节点初始能量为0.5 J，其他参数与文献[13]中仿真参数相同.在簇首节点的选举和簇首节点与簇内节点的通信两方面与LEACH协议，分别作了比较.

图2描述的是ABCCR算法与经典的LEACH协议关于网络中存活节点总数随着时间变化的关系图.

图2 ABCCR算法与LEACH存活节点数比较

从图2可以看出：ABCCR算法中节点存活的时间明显比LEACH协议中节点存活的时间长.在网络运行到700轮左右的时候，LEACH协议中80%左右的节点已经失效，无法提供有价值的信息，意味着网络已经瘫痪.而此时ABCCR中还剩下大约60%的节点，网络仍能运行正常.相对于LEACH协议，ABCCR算法构造出基于节点间距离信息和节点剩余能量信息的适应度函数，应用于无线传感器网络的分簇过程，能够减缓节点失效的速度，延长了网络的寿命.

为了进一步说明ABCCR算法的特性，对基站位于分布区域的中心位置(150，150)的情况进行实验，仿真结果如图3所示.

图3 基站位于分布区域中心时ABCCR算法与LEACH存活节点数比较

由图3可以看出：此时LEACH协议表现出较好的性能，只是略差于ABCCR算法.这是因为当基站在网络的中心位置时，基站与网络中的簇首节点的距离较近，即使簇首节点在网络中分布不均，与基站通信消耗的能量也不会太多.对比图2，3：对于基站位于网络的边缘和位于网络中心两种情况，LEACH协议的存活节点数目变化非常大；而ABCCR算法对于这两种情况所表现出的性能差别不大.这说明ABCCR算法能够根据网络结构的不同，合理的对网络进行分簇，从而达到减少网络的能量消耗的效果.

图4描述的是ABCCR-SPT算法、ABCCR算法及LEACH关于网络中存活节点总数随着时间变化的关系图.从图4中可以看出：ABCCR-SPT算法在存活节点数目上略优于ABCCR算法，表明在簇内构建以簇首节点为根的最短路径树，能够优化簇内节点通信的能量消耗，保证网络中节点存活的时间更长.

图4 三种算法存活节点数比较

4 结 论

针对LEACH协议在选择簇首节点时存在的不足，对人工蜂群算法进行研究，根据Friis自由空间方程式推导出了人工蜂群算法中的适应度函数，并应用于无线传感器网络中簇首节点的选择.另外，结合图论中的最短路径思想，提出在簇首节点确定后，以簇首节点为树根最短路径树，尽可能的保证每个簇内节点与簇首节点通信所消耗的能量最少，从而优化了簇内节点间通信的能量消耗.仿真结果表明：所提出的协议在降低网络节点能量消耗和延长网络的生命周期方面比传统的LEACH协议有了较大的改善.

参考文献：

[1] 周晓，李杰，边裕挺．基于无线传感器网络的环境温度监测系统设计[J]．浙江工业大学学报，2013，41(4):440-443．

[2] 周晓，边裕挺，李杰．基于Android智能终端的WSN监控系统[J]．浙江工业大学学报，2013，41(5):558-561．

[3] 陆欢佳，俞立，董齐芬，等．基于无线传感器网络的楼宇环境监测系统设计[J]．浙江工业大学学报，2011，39(6):684-687．

[4] 杨淑莹，张桦．群体智能与仿生计算—Matlab技术实现[M]．北京：电子工业出版社，2012．

[5] SALEEM M, GIANNI A, FAROOQ M, et al. Swarm intelligence based routing protocol for wireless sensor networks: survey and future directions[J]. Information Sciences,2011，181(20):4597-4624.

[6] KENNEDY J, EBERHART R．Particle swarm optimization[C]//Proceedings of IEEE International Conference on Neural Networks．Perth: IEEE Neural Networks,1995:1942-1948．

[7] DORIGO M, GAMBARDELLA L M. Ant colony system: a cooperative learning approach to the traveling salesman problem[J]．IEEE Transaction on Evolutionary Computation,1997,1(1):53-66.

[8] 李晓磊.一种新型的智能优化方法—人工鱼群算法[D]．杭州：浙江大学，2003．

[9] PASSINO K M．Biomimicry of bacterial foraging for distributed optimization and control[J]. IEEE Control Systems Magazine,2002,22(3):52-67.

[10] KARABOGA D．An idea based on honey bee swarm for numerical optimization[R]. Kayseri: Computer Engineering Department of Erciyes University,2005.

[11] DELAVA A G, JAVIZ E. A routing algorithm based on bee colony for energy consumption reduction in wireless relay networks[J]. International Journal of Ad Hoc, Sensor & Ubiquitous Computing，2012,3(4)：1-9.

[12] KARABOG D, OKDEM S, OZTURK C. Cluster based wireless sensor network routing using artificial bee colony algorithm[J]. Wireless Networks,2012,18(7):847-860.

[13] HEINZELMAN W, CHANDRAKASAN A, BALAKRISHNAN H. Energy-efficient communication protocol for wireless microsensor networks[C]// Proceedings of the 33rd Annual Hawaii International Conference on System Sciences. Maui: Western Periodicals Company,2000:1-10.