基于遗传模拟退火算法的无线传感器网路由协议*

崔小勇， 林 宁,2

(1.上海海洋大学 信息学院，上海 201306；2.国家海洋局信息中心,天津 300171)

基于遗传模拟退火算法的无线传感器网路由协议*

崔小勇1， 林 宁1,2

(1.上海海洋大学 信息学院，上海 201306；2.国家海洋局信息中心,天津 300171)

在无线传感器网络中(WSNs)中，由于节点能量有限，为了延长整个网络的生存周期，提出一种基于遗传模拟退火算法的无线传感器网络路由协议。利用模拟退火(SA)算法具有较强的局部搜索能力并能以稳定的速度收敛，克服遗传算法(GA)局部搜索能力差并容易早熟收敛等缺点。该路由协议在簇头节点选举时充分考虑了节点的剩余能量，并根据网络中数据转发能量耗损和延迟时间建立个体适应度函数，采用遗传模拟退火算法找到簇头节点到基站的最优路径。仿真结果表明:与其他协议比较，该方法不仅可以均衡各个节点的剩余能量，还可以有效延长整个网络生存周期和提高网络的数据传输能力。

无线传感器网络； 遗传算法； 模拟退火； 生存周期

0 引 言

无线传感器网络(WSNs)[1]是由分布在不同区域内大量的微型传感器节点组成。它是以一种无线通信的方式形成一个网络系统，其主要工作目的是采集和处理网络覆盖地理区域内感知对象的信息，并发布给观察者[2]。由于无线传感器网络节点携带的电池能量有限,且节点布置之后不容易更换电池，所以,减少无线传感器网络的能量消耗，延长无线传感器网络的生命周期是目前无线传感器网络研究的主要问题[3]。

针对无线传感器网络路由协议，从网络拓扑结构来分主要有两种路由协议：层次路由协议和平面路由协议[4]。LEACH协议[5,6]就是一种比较常用和成熟的分层路由协议。LEACH协议将整个网络划分成多个簇，每个簇包括一个簇首节点跟其余普通节点，周期性的轮换簇头节点[7]。但由于LEACH算法簇头随机产生，没有考虑网络中节点的剩余能量，可能导致最后的分簇不合理，降低了网络的生存周期。簇头直接与基建通信，若两者之间的距离过大，会增大整个网络的能耗。

为了平衡无线传感器网络节点的能量消耗，延长无线传感器网络的生存周期，提出了一种遗传模拟退火算法的无线传感器网络路由协议。仿真结果表明，遗传模拟退火算法的无线传感器网路由协议不仅可以延长网络的生存周期，还可以提高网络数据传输能力。

1 通信能耗模型与网络模型

任意传感器节点发送mbit的数据到距离d的位置，传感器节点所消耗的能量为

(1)

(2)

式中Eelec为发送电路和接收电路每发送或接收单位比特币所消耗的能量,εfs为自由空间传播模型下功率放大所需要的耗能系数,εmp为多路径衰减传播模型下功率放大所需要的耗能系数,D0为门限距离[8]。

2 改进遗传算法的路由协议

2.1 簇的建立阶段

一般情况下，无线传感器网络会被分成多个大小不同的簇，每个簇中包括一个簇头节点跟多个普通节点。由于簇头节点不仅要负责接收、融合、传输簇内节点的数据而且还要负责转发其他簇头节点传输的数据，因此，簇头节点的选择应考虑传感器节点的剩余能量。本文在选择簇头节点的时候，综合考虑传感器节点的剩余能量，首先计算整个无线传感器网络节点的能量平均值Eavg，然后再计算每一个传感器节点的剩余能量，如果该传感器节点能量低于Eavg则退出簇首节点的选择。对于每一个传感器节点，如果被选中当簇头节点，那么该节点向整个无线传感网广播自己的信息，其他传感器节点根据自己与簇头节点的距离加入相应的簇。

2.2 数据传输阶段

设无线传感器网络的簇头集合为S=(s1,s2,…,skopt)，其中，skopt表示最优簇头数本文采用遗传模拟退火算法选择最佳数据传输路径。

1)个体编码方式

个体编码采用整数编码方式，每个基因表示经过的簇头节点，比如当经过的簇头节点数目为5，染色体为[2,3,4,1,5]，表示簇头节点遍历从2开始经过3，4，1，最后到5，从而完成遍历。

2)适应度函数确定

为了延长无线传感器网络生命周期，尽量减少数据传输过程中的时间延时，适应度函数可以描述如下

(3)

式中 ei为簇头节点消耗的能量，t为时间延迟，a,b为权重系数，且a+b=1。

3)选择操作

选择的目的是尽量保留种群的最优化个体，首先将最优的个体保留到下一代，其他个体采用轮盘赌的方法，个体适应度值越大，被选择作为下一代父代的概率越大。根据个体适应度值计算其被选择的概率，每个个体被选中的概率为

(4)

式中 fi为个体适应度值，f为平均适应度值。

4)交叉操作

交叉算法是以某一概率相互交换两个个体之间的部分染色体。本文采用单点交叉的方法，具体交叉方式如图1所示。

图1 两个染色体的交叉方式Fig 1 Two chromosomal crossover mode

5)变异操作

变异操作时为了提高种群的适应能力，保证种群的多样性。具体操作方式如下：随机选择一个个体中的传感器节点xk，然后选择一个新的传感器节点xl代替xk。

6)模拟退火操作

3 仿真与结果分析

3.1 仿真环境

在边长100m×100m的正方形区域内，随机分布100个传感器节点，仿真采用Matlab2013b模拟，仿真具体环境设置如表1。

表1 实验参数设置 Tab 1 Experimental parameters settings

3.2 结果与分析

在不同的工作次数下，遗传算法与本文算法相比，第1个节点死亡、第40个死亡、最后一个节点死亡时间如表2所示。

表2 传感器节点死亡时间Tab 2 Time of death of sensor nodes

无线传感网络生存周期如图2所示。

图2 节点剩余数对比Fig 2 Contrast of node number of remaining

从图2中可以看出，本文采用的无线传感器路由协议可以延长整个网络的生命周期，这主要由于本文算法在选择簇头节点的时候充分考虑了网络中传感器节点自身的剩余能量，同时也考虑了数据传输过程中节点与基站之间的跳数。

4 结束语

为了延长无线传感器网络的生存周期，提出一种基于遗传模拟退火算法的无线传感器网络路由协议。仿真对比实验说明：本文提出的算法不仅可以延长网络的生存周期还可以提升网络的数据传输能力。

[1] Xiao Renyi,Wu Guozheng.A survey on routing in wireless sensor networks[J].Progress in Natural Science,2007(3):261-269.

[2] 毕 冉,李建中.无线传感器网络关键技术研究[J].智能计算机与应用,2014(6):54-56,60.

[3] 唐 宏,谢 静,兽玉芬,等.无线传感器网络原理及应用[M].北京:人民邮电出版社,2010.

[4] AI-Karaki J N,Kamal A E.Routing techniques in wireless sensor networks:A survey[J].IEEE Wireless Communications,2004,11(6):6- 28.

[5] Heinzelman W,Chandrakasan A,Balakrishnan H.An application-specific protocol architecture for wireless microsensor network-s[J].IEEE Transactions on Wireless Communications,2002,1(4):660- 670.

[6] 任丰原,黄海宁,林 闯.无线传感器网络[J].软件学报,2003,14(7):1282-1291.

[7] 卢建刚,乐红兵.基于节点相对密度的无线传感器网络成簇算法[J].传感技术学报,2011(4):587-592.

[8] 李成法,陈贵海,叶 懋,等.一种基于非均匀分簇的无线传感器网络路由协议[J].计算机学报,2007(1):27-36.

WSNs routing protocol based on genetic simulated annealing algorithm*

CUI Xiao-yong1， LIN Ning1,2

(1.College of Information Technology,Shanghai Ocean University,Shanghai 201306,China;2.National Marine Data & Information Service,Tianjin 300171,China)

In wireless sensor networks(WSNs),due to limited energy of node,in order to extend life cycle of the whole network,a kind of WSNs routing protocol based on genetic simulated annealing algorithm is proposed.Using the simulated annealing algorithm has strong local search ability and can converge in stabilize speed,overcome shortcomings of poor local search ability and easy to premature convergence of Genetic algorithm.The routing portocol fully considers residual energy of nodes in election of cluster head nodes,and according to energy loss of data forwarding in network and delay time to establish individual fitness function,using genetic simulated annealing algorithm to find the optimal path from cluster head nodes to base station. Simulation results show that,compared with other protocols,this method can not only balance remaining energy of each node,but also can effectively prolong the network life cycle and improve data transmission capability of network.

wireless sensor networks(WSNs); genetic algorithm(GA); simulated annealing(SA); life cycle

10.13873/J.1000—9787(2016)07—0032—03

2015—10—29

国家自然科学基金资助项目(61272098);上海市科委科研计划重点支撑资助项目(1251050200)

TP 393

A

1000—9787(2016)07—0032—03

崔小勇(1990-)，男，江苏盐城人，硕士研究生，主要研究领域为嵌入式系统开发、无线传感器网络。