无线传感器网络能量优化策略研究*

施开林，江 虹

（西南科技大学 信息工程学院，四川 绵阳 621010）

0 引 言

无线传感器网络（Wireless Sensor Network）是由部署在监测区域内的低成本﹑低功耗﹑具备感知﹑存储和无线通信能力的大量传感器节点通过自组织方式形成的网络[1]。由于网络节点由电池供电，导致其自身能量有限。如何降低节点的能量消耗与延长网络的生存时间，已成为当前研究的热点[2]。从单个节点的能量消耗途径来看，其能量消费可分为通信消费和计算消费两部分[3]。

文献[4]基于LEACH[5]，根据簇头的期望转发负荷来调整簇大小，使得所有簇头的能耗接近，网络能量消耗均衡，但其使用到基站单跳的通信方式会造成远离基站的节点因通信距离过长率先死亡。文献[6]在LEACH协议基础上，提出一种基于跨层功率控制的按需路由算法，通过按需建立多个不同功率级的路由来降低能量消耗，但未考虑网络整体的能量均衡。文献[7]运用遗传算法在两层网络中寻找路由中间节点，以探寻优化路径，虽然设计并未针对无线传感器网络，但设计思想值得借鉴。本文在LEACH路由协议的基础上，首先提出一种基于遗传算法的全新分簇机制，并改进了簇头选举方式；其次，改变原有的单跳传输方式为簇间多跳，并基于跨层设计，结合网络层和MAC层制定联合选路策略。

1 网络模型

在WSN中，获得监测数据的传感器节点为源节点，其数据经过多跳传输到汇聚节点（Sink Node）或基站（Base Station），再通过互联网或卫星到达管理节点或用户。本文将WSN的监测区域进行集群分组（称为簇），每个簇选出一个簇头节点（Cluster Head）负责簇内节点和基站的通信。

作如下假设和定义：

（1）网络中任意节点初始能量相等，且有唯一的识别编号(1,2,3…n)，均匀分布于监测区。

（2）所有节点位置固定，坐标为(xi,yi)，能量有限；基站固定，位置为(xsink, ysink)，能量不受限。

（3）链路是对称的，节点可互相传输数据。

（4）所有节点都能调整自己的发射功率。

（5）每个节点周期执行数据采集任务，并始终有数据传送至基站。

2 基于GA的分簇策略

2.1 分簇思想描述

在LEACH基础上做以下两点改进：

（1）由于文献[8]证明了合理的拓扑结构可以使得形成的簇在整体上功耗较低，达到节省能量的目的，所以综合考虑节点的能量信息﹑簇头数目﹑节点之间的距离，运用遗传算法控制和优化全局簇结构的生成。

（2）采用全新的簇头候选机制，即在簇的形成阶段，簇头会根据簇内其他非簇头节点传输的数据包判断其能量强度，选择能量最高的作为候选簇头，以减少重新分簇的数，降低频繁分簇带来的网络整体能耗。

2.2 算法流程描述

设计中，基站在获取所有节点的状态信息后，采用指定的编码方式构造染色体结构﹑初始化种群，计算染色体的适应度﹑采取选择﹑变异﹑交叉等操作，并不断迭代搜索得到最优的染色体，即最优簇结构。得到最优簇结构的同时，也就得到了最优分布的簇头。最后，各个簇头向全网发送控制报文，选择候选簇头，创建低能量的簇。应用遗传算法的关键操作有以下几点。

（1）染色体编码

采用01编码的方式，即用一条染色体来表示一种分簇状态，一个簇内的所有节点都位于该染色体上，区域内一个节点代表了该染色体中的一个基因位，簇头节点和成员节点分别用1和0来编码表示。

（2）建立适应度函数

适应度函数是衡量一个染色体能否正确优化的指标，决定着遗传算法能否不断向预设的优化目标有效趋近，即生成结构优化﹑能量消耗低的分簇结构。如何保证分簇均匀且总体耗能较低，是一个多目标优化问题。采用的各目标函数如下。

簇头总距离（g1），表示某个簇头的总距离等于簇内成员节点与簇头节点之间的距离﹑簇头和基站之间的距离之和。该值越小，则各个节点在数据传输时的相对距离最优。

能量消耗（g2），表示簇内信息报文传输到基站所消耗的能量。它包括成员节点将报文传输到簇头节点和簇头节点经过多跳将报文传输到基站所消耗的能量之和。该值越小，表示能量消耗越少。

无线传感器网络中，各分簇中成员节点数目的方差（g3）。该值越小，表明网络分簇使得簇内节点数目越均匀，各簇首承担的负载也相对均衡。

式（1）中，num表示节点总数目。式（2）中，TE(m)表示簇内第m个普通节点向簇头传输报文的能量消耗，Mj表示第j个簇头，Re表示簇头接收报文能耗，TE1表示簇头和基站之间的能耗。式（3）中，N表示节点总数目，p为最优簇头数目的概率，通常为0.05；u表示网络各分簇的非簇首子节点平均数。

设置适应度函数为：

其中a1+a2+a3=1。

对各个待优化的目标函数皆取对数，目的是为了使各个性能指标尺度能够控制在同一个数量级上，避免某个性能指标过度影响整个遗传优化的过程，导致某些优秀解被淘汰，陷入局部最优。

（3）遗传操作

选择操作。选择操作是从当前群体中选出优良个体，使它们有机会作为父代繁殖下一代子孙。适应度值越高的染色体，表示使用该染色体所对应的簇状态将会使得传感器节点能量节省﹑延长网络生命周期[9]，其被选中进行选择操作的概率越大。本文使用赌轮选择。

交叉操作。本文采用单点交叉，在两条染色体中随机产生一个交叉位置。如果一个普通节点通过交叉操作成为簇头，所有其他的普通节点应该检查它们是否接近该簇头，以便判断是否需要更新簇头标记；若一个簇头节点通过交叉操作成为了普通节点，它所有的成员必须查询新的簇头。

变异操作。在路径中随机选择一个传感器节点作为变异节点，对该传感器节点变异概率pc=0.09进行基因的变异操作。

（4）终止条件

本文GA采取复合准则，设定最大进化代数和设定收敛条件。具体地，连续进化20代，最优解均未发生变化，且种群的平均适应度提高值不足1%就判定为收敛。

（5）具体算法流程

基于遗传算法的无线传感器网络路由的基本流程如下：

①置群体代数gen=0，随化产生规模M=100个个体的初始种群；

②计算群体中所有个体的适应度值，并根据结果按从小到大的顺序排序；

③选取适应度高的个体，并对其进行遗传操作产生下一代；

④检验结果是否为最优解或者gen=genmax，若是，则算法终止并输出最优解；否则gen=gen+1，转到②继续操作。

3 基于跨层的簇间多跳选路策略

本文拟采用将MAC层与路由层相结合的方式进行整体设计来选择簇间多跳的路由路径，同时考虑MAC层协议如何避免节点间的碰撞和网络层路由信息。

3.1 概念定义

能量标识符（El）：节点发送的路由包中带有一个自身能量等级标志，共有三个等级，分别为normal﹑warning﹑danger。由式（5）可得出。

簇首节点侦听状态：簇首节点发射模块打开状态下，只要没有数据发送，节点就一直处于侦听信道状态。

簇首节点数据发送状态：簇首节点有新的大量数据需要发送至其他簇首节点或作为中继节点转发数据时，将会结束侦听状态。

中继节点：能够转发其他簇头节点发过来数据包的节点。规定能量等级为normal的节点才能担当此功能。

随机选择标识符（RSD）：用来唯一标识节点名称。

源梯度标识符（SGD）：由基站根据节点位置﹑节点与基站距离，经过特定公式计算得出的结果，并由基站广播给节点。计算原则是距离基站越近的节点，其结果值越小，处于越低的梯度区间。

3.2 跨层多跳路由选择机制

（1）当簇首有数据准备发送时，节点首先会等待一个时隙，称为监听时间，用t表示。在该期间，节点将会判断信道是否为空闲状态。

（2)若信道空闲，则进入随机侦听时间2t。若信道空闲，进入步骤（3）；如果信道忙，则节点一直侦听信道，直到信道的空闲时间超过该间隔。当信道最终空闲下来时，节点使用二进制退避算法进入退避状态避免发生碰撞。退避状态下，只有当检测到信道空闲时才进行计时。如果信道忙，退避计时器中止计时，直到检测到信道空闲时间大于帧间间隔后才继续计时。当多个节点推迟且进入随机退避时，利用随机函数选择最小退避时间的节点作为竞争优胜者。

（3）节点发送一个请求中继信号RT_R。此处，RT_R包含RSD与SGD。发送RT_R后，节点一直处于等待允许中继信号（CT_R），并同时进入请求状态。

（4）当位于低梯度的节点即下一跳节点接收到RT_R信号时，系统自动丢弃SGD比它小的节点，回复SGD比它大的节点。为避免与其他潜在的位于同一梯度的节点竞争，它在回复源节点前会等待一个随机退避时间Tb，此期间则继续侦听信道。若在这个退避时间里，下一跳节点又侦听到来自同一梯度的另一个下一跳节点的CT_R，且该CT_R包含了符合规定的RSD或是来自于源节点的数据，则说明存在其他传输在占用信道，节点返回至侦听状态。否则，退避时间超时后，该下一跳节点将发出含有SGD﹑RSD以及接收层标识符（RGD）的允许中继信号CT_R。此时，它会等待源节点的数据，并进入接收状态。

（5）一旦源节点成功接收到CT_R信号，它将马上向下一跳节点发送数据。若下一跳节点接收到数据，则将向源节点发送ACK确认信号。通过该种方式，数据与确认在节点间形成快速交换，且使用了明确的中继节点和源节点的标识符。为确保数据的无误传输，在源节点和接收节点中设置了溢出时间Ta和Td，而下一跳节点成功接收数据帧后，将发送一个确认帧至发送节点。发送节点接收到该确认帧，说明发送成功。在规定时间内若未接收到确认帧，则将重发该数据帧。

（6）成功接收完数据后，更为靠近基站的下一跳节点则成为新的源节点，并将向更低梯度的节点请求数据的中继转发，并一直传输数据至基站。这样就可以通过一个联合设计的跨层方法解决接入与路由。

4 算法描述

（1）网络初始化后按照遗传算法将网络区域分为面积大小不等的簇，同时选出每个簇的簇头和候选簇头。

（2）簇内普通节点按照TDMA的方式将数据发送给簇头，簇头根据跨层策略选择到达目的节点的多跳路径。

（3）基站根据传来的数据包的能量字段计算，经过最终实验验证当，网络中有1/3的节点能量为danger时，则重复（1）重新分簇，进行下一轮数据传输。此时，最能兼顾能量均衡和分簇轮数过多带来的额外消耗。

5 仿真结果与分析

仿真工具采用EXata平台，信道传输速率为2 Mb/s，信道传输范围为250 m，无线电波干扰范围为500 m。在100 m×100 m的矩形区域内，随机分布100个无线节点，节点初始能量为1 J，每传输单位比時数据所消耗的能量Et=1 nJ。

确定最优簇头数目采取LEACH协议中的计算方法，实验中最优簇头数目比率为0.05；交叉概率设定为0.6；兼顾质量和求解代价，取适应函数各权值为a1=a2=0.2﹑a3=6。表1是经过五轮后，LEACH协议和改进后的协议各簇头剩余能量统计表。由表1可看出，改进后的协议各节点剩余能量更为均衡，变化量仅从0.49～0.70 J，而LEACH剩余能量不均，其分布范围为0.20～0.91 J。因此，改进协议通过GA重新分簇达到了能量均衡的目的。

表1 剩余能量对比图

图1为网络中死亡节点的个数随仿真时间变化的情况。可以看出，在同一仿真时段，改进算法的节点能量耗尽数目明显少于LEACH协议。原因是LEACH协议中远离sink节点的簇头节点通信距离太长，使得节点能量消耗速度加快，较早出现了能量耗尽。而改进算法采用簇间多跳，且多跳时避免选择能量过低的节点，均衡了簇间能量消耗，优化了系统能量消耗。

图1 节点生存时间对比图

图2为LEACH和改进算法每轮剩余能量。可知，由于改进算法应用了遗传算法分簇，该过程消耗了一定能量，导致开始阶段能量消耗过快。但是，改进算法使用了MAC层选路策略，能更好避免信道干扰，保证了链路质量，避免了数据包重发。此外，多跳策略能比LEACH更好地避免能量空洞。所以，经过3 000 s后，改进算法比LEACH多节约5%能量。

图2 网络剩余总能量对比图

6 结 语

本文在LEACH路由协议基础上，提出一种基于GA的分簇算法和跨层的簇间多跳路由算法。通过GA优化网络拓扑结构，均衡了网络能耗。通过将路由层和MAC层结合设计，采用簇间多跳方法，避免了能量空洞。仿真实验结果表明，改进后的算法可以有效均衡网络能量消耗，减少系统能量消耗，延长网络生命周期。

[1] WANG Ying-guan,WANG Zhi.Wireless Sensor Network[M].Beijing:Publishing House of Electronics Industry,2012:2-3.

[2] Raman K K,Singh V.Transmission Energy Management for Wireless Sensor Network[C].2014 International Conference on Optimization,Reliabilty,and Information Technology(ICROIT),2014:245-248.

[3] Vazifehdan J,Prasad R V,Niemegeers I.Energy-Efficient Reliable Routing Considering Residual Energy in Wireless Ad Hoc Networks[J].IEEE Transactions on Mobile Computing,2014,13(02):434-447.

[4] Liao Q,Zhu H.An Energy Balanced Clustering Algorithm based on LEACH Protocol[J].Applied Mechanics&Materials,2013:341-342.

[5] H einzelman W B,Chandrakasan A P,Balakrishnan.An Application-specific Protocol Architecture for Wireless Micro Sensor Network[J].IEEE Transaction Wireless Communications,2000,1(04):1-10.

[6] Zuo J,Dong C,Ng S X,et al.Cross-Layer Aided Energy-Efficient Routing Design for Wireless Sensor Networks[J].IEEE Communications Surveys & Tutoria ls,2015,17(03):1214-1238.

[7] Ataul B,Shamsul W,Arunita,et al.A Genetic Algorithm Based Approach for Energy Efficient Routing in Two-tired Sensor Networks[J].Ad Hoc Networks,2009(07):665-676.

[8] Sanchez S M,Souza R D,Fernandez E M G,et al.Rate and Energy Efficient Power Control in a Cognitive Radio Ad Hoc Network[J].IEEE Signal Processing Letters,2013,20(05):451-454.

[9] Jin S,Zhou M,Wu A S.Sensor Network Optimization Using a Genetic Algorithm[C].7th World Multiconference on Systemic,Cyberbetics and Information,2003.