无线传感网络中基于覆盖度优化的自适应遗传算法*

王 骐，王青萍

(湖北第二师范学院 物理与机电工程学院，湖北 武汉 430205)

无线传感网络中基于覆盖度优化的自适应遗传算法*

王 骐，王青萍

(湖北第二师范学院 物理与机电工程学院，湖北 武汉 430205)

在资源受限、多跳的无线传感器网络中，节点分布或网络拓扑结构不合理，将会产生感知阴影和覆盖盲区，严重影响数据感知和网络能效。为此提出一种基于节点移动的总适应度的遗传算法，通过节点的移动对节点进行分簇和重定位，实现网络节点覆盖度的优化和高能效的节点动态部署。仿真表明，算法对节点的重定位优化了节点部署和路由配置，能量在各种不同功能性节点之间的分配更加合理，在适应度参数保持平衡的情况下，减少了网络内节点“重分簇”的次数，最大限度地提高了网络覆盖度和生存期。

动态部署；覆盖度；能效；适应度；遗传算法；仿真

0 引言

在无线传感器网络中，节点的分布以及网络拓扑结构的构成，对于数据的感知和俘获以及网络的生存都具有十分重要的意义。在节点随机部署的静态传感器网络中，为了获取良好的感知效果，在环境中往往会部署大于实际需要的冗余节点，因此网络中有可能因为节点分布的不合理，造成感知阴影和覆盖盲区[1-2]，使得有些被监测事件无法进行及时跟踪。特别是当某个特定区域需要多个传感器节点协同感知数据时，如果这个区域节点分布稀疏，那么就无法完成更精准的测量。在能效方面，由于传感器节点负载的分布高度不均，当向汇聚节点进行数据传递时，那些远离汇聚节点的传感器节点将会消耗大量能量，从而导致资源迅速枯竭。另外，由于单跳或多跳网络的跳长固定不变，通信路径无法优化，不利于有效降低能耗。

相比于节点的静态部署，基于节点移动性的动态部署能够很好地解决上述问题。特别是在资源受限、多跳的移动传感器网络中，可通过节点的移动性构建新的最短路径，变多跳传输为少跳或单跳传输，从而缩短通信路径，不仅可以均衡传感器节点的负载分布，还可以最大限度减少通信开销[3]。

本文基于对生物进化机制的模仿，采用“进化算法簇”中的遗传算法(Genetic Algorithm，GA)，实现节点分布的动态部署，进一步优化网络节点的覆盖度，最大限度提高电池和传感器节点的使用寿命。

1 遗传算法适应度函数的构建

在网络模型中按照功能将传感器节点进行了分类：(1)非活动节点(断电状态)；(2)簇头(CH)；(3)簇间路由器(ICR)；(4)传感器节点(NS)。遗传算法的适应度函数是用来判断群体中个体的优劣程度的指标，它根据所求问题的目标函数来进行评估。在具体应用中，适应度函数的设计直接影响到遗传算法的性能，因此要结合求解问题本身的要求来定。本节将介绍移动性的遗传算法适应度函数的构建及其重要参数。

1.1 覆盖均匀性适应度

覆盖均匀性适应度(Coverage Uniformity Fitness，CUF)表示覆盖度的变化情况及其对环境的适应能力。节点的移动可提高网络覆盖度，从而减小“覆盖盲区”或增大监测面积，这可通过重新调整簇内成员节点之间的通信距离来实现。当节点之间处于最佳距离时，相邻节点间的最大距离以及所需的传输功率将趋于最小化，这有助于最大限度提高“节点通信适应度NCF[4]”。CUF表示为：

(1)

其中M表示簇的数量，dj_min和dj_mean分别表示簇j内节点间的最小通信距离和平均通信距离，ej_min和ej_mean分别表示簇j内节点与簇头间的最小通信距离和平均通信距离。

1.2 簇节点迁移适应度

系统奖励传感器节点在具有较低“簇头适应度CHF[4]”的簇头之间进行迁移，以此来改进传感器节点和簇头分布的均匀性，这种均匀性的改进用簇节点迁移适应度(Cluster-Node Migration Fitness，CNMF)表示。簇节点迁移适应度CNMF可表示为：

(2)

(3)

(4)

其中n表示第n个迁移对(源簇-目标簇)，N表示迁移对的总数量，χns表示源簇内冗余的传感器节点数量，χnt表示目标簇内废弃的传感器节点数量，ρns和ρnt分别表示源簇和目标簇内簇头下的节点数量，ρ表示每个簇的平均节点数，表示为：

(5)

从以上适应度公式可看出，如果传感器节点位于较低CHF的簇内，且从源簇到目标簇具有较高的扩散梯度，那么这种情况有利于节点的迁移。

1.3 簇头迁移适应度

簇头迁移适应度(Cluster-Head Migration Fitness，CHMF)奖励簇头(CH)和具有较低“路由器负载适应度RLF[4]”的簇间路由器(ICR)的移动。CH和ICR的移动可获得较高的RLF，这是因为：

(1)ICR或CH的移动可改变ICR的成员身份，从而优化CH/ICR的数量[4]。

(2)通过移动，ICR可与其他的功能性节点(簇头和传感器节点)交换角色。比如通过交换，可以使具有较高电池容量的节点作为路由器使用，这有利于维护现有的拓扑结构。

簇头迁移适应度(CHMF)可表示为：

(6)

这里N表示移动的节点总数，RLFn表示第n个节点的“路由器负载适应度[4]”，BFnt表示非ICR节点的“电池适应度[4]”，它与第n个ICR节点(电池适应度为BFns)进行交换形成交换对。ηn是布尔值，表示第n个ICR的交换对是否存在。显然，根据式(6)可知，具有较低的电池容量和路由器负载适应度的ICRs和CHs是易于进行移动的。

1.4 节点移动适应度

节点移动的平均距离与它的移动轨迹有关。由于节点的移动会消耗电池的能量，因此在有限的能量范围内，节点移动距离的期望值可看成是节点移动所需能量的估计值。所以，要实现优化覆盖度和提高网络能效的总体目标，需要保持节点移动特性的稳定性，即节点移动的频率和幅度。

节点移动适应度(Node Motion Fitnes, NMF)可表示为：

NMF=(1-Fi(Q,distance)+(1-φi(n)))/2

(7)

其中φi(n)表示对第i个传感器节点进行惩罚的一种度量，原因是它移动时位置不稳定，到达同一个位置的次数达到n次(0≤φi(n)≤1)。Fi(·)表示第i个传感器节点的惩罚函数，且0≤Fi(Q,NodeType)≤1，其中Q是电池的状态，表示成一种量化步长，distance表示节点移动的预估距离，它是采用基于能量的定位方法，根据节点在不同位置的多个能量读数间接估计出来的。

假定yi(t)表示第i个传感器节点在时间间隔t内的信号能量，则：

(8)

其中Gi表示第i个传感器节点的增益因子，α(≈2)表示能量衰减因子，εi(t)表示参数建模误差的累积效应，S(t)表示目标节点在时刻t释放的能量，r(t)是D×1的向量，表示目标节点在时刻t的坐标，ri也是D×1的向量，表示第i个静态传感器节点的笛卡尔(直角)坐标。

1.5 传感器节点数据适应度

传感器节点数据适应度(Sensor Data Fitness，SDF)衡量的是传感数据的效率，并据此重新定位传感器节点，使其数据传输能通过融合、消除或压缩等方式被统一优化。在给定信噪比(SNR)下，通过提高传感质量还可使数据传输进一步优化[5]。在资源(通信、电池等)受限情况下的最佳传感质量可表示为θ(B,F)，其中B表示与传感操作相关的QoS条件，F表示定时策略。实施QoS属性是为了充分利用可变数据的压缩和融合规则，而实施定时策略是为了根据传感器节点的不同情况(比如说密度等)来改变比特率[6]。一般来说，降低簇的平均能耗有利于传感器的移动。SDF表示为：

(9)

(10)

1.6 节点移动的总适应度

根据以上所述，节点移动的总适应度(Total Node Motion Fitness, TNMF)可表示为：

TNMF=α1CUF+α2CNMF+α3NMF+α4CHMF+α5SDF

(11)

其中α1+α2+α3+α4+α5=1，单个αi的权值可根据外部启发式算法[7]进行自适应调整。算法根据节点的运行情况在一定时间内进行多阶段决策过程的优化处理，以最大限度取得单个αi的最优组合值为目标。

2 节点部署遗传算法

根据式(11)，采用GA遗传算子，可设计出节点的最优动态部署算法。本节将介绍节点重定位的染色体表示，以及算法的主要流程。

2.1 染色体的表示

GA的染色体是解决目前问题的关键模块，形式上与遗传算子和适应度函数相适应[8]。染色体串由每个传感器节点的移动矢量形成，该矢量由7位二进制数表示，称为“基因”[9]，如图1所示。

图1 基于遗传算法的节点重定位及其染色体表示

将染色体串的层次结构定义成：

(3)只有当其中一个x的值为1时，传感器节点才会移动。

在图1中，根据节点坐标的变化，节点1、2的位置改变了3次，节点3、4改变了2次，而节点5、6、9只改变1次，其他节点没有改变。因此，每个节点重定位后的染色体表示为：

(9 0010001→0010001→0010001)、(10 0000000→0000000→0000000)。

2.2 算法的流程

算法的流程如图2所示。

图2 算法流程图

产生初始种群时，初始染色体串一部分由随机数发生器(RNG)产生，另一部分则由以前的种群样本产生。每个染色体串根据TNMF函数(节点部署函数)对适应度进行评估，参见式(11)。繁殖使得具有较高适应度的染色体串能够以较大概率产生下一代染色体子串。因此，根据TNMF定义的适应度公式，具有最高TNMF值的染色体将更有机会繁殖下一代染色体子串。繁殖期间，算法采用“标准加权轮盘”的方式，选择n个染色体串投入到“配对库”中，以“交叉概率”产生N个染色体。染色体繁殖期间，多个交叉点的位置由随机数发生器(RNG)计算产生。染色体变异时，将生成的N个染色体放入突变库，突变算子根据自适应突变概率(与平均适应度成反比)使其产生突变，采用类似抛硬币的方式来决定是否要将比特位进行逆变处理(即0→1，1→0)。设突变概率的最大值为pm，则：

pg=pm(1-(N*TNMFavg)/TNMFtotal)

(12)

在选择阶段，根据适应度值，从N+n个(n个双亲，N个孩子)染色体中选取n个染色体延续到下一代[10]。算法运行时，比较每一次迭代得到的最优适应度，如果最大适应度值和平均适应度值变化不大、趋于稳定，那么此适应度值即为近似全局最优解，算法终止，否则循环进行。

3 算法仿真与结果分析

仿真的实验场景由100个节点组成，这些节点随机分布在30×30的区间内，每个节点具有唯一的UUID，随机分配量化值介于0～15之间的电池容量，坐标介于(0,0)～(30,30)之间。为简化起见，每个节点覆盖的范围为3×3，并假定节点之间的通信为视距传播(即无线信号的直线传播)[11]。一旦所有的节点都处于监听模式，那么GA运行时的交叉率为60%，初始变异率为6%。式(11)中节点移动的TNMF的单个αi组合值由外部启发式算法运行得到，α1～α5分别为：0.113 4、0.356 3、0.229 4、0.107 5、0.193 4。

实验模拟汇聚节点的运行，NS-2软件模拟网络的流量。尽管每个GA适应度函数彼此存在竞争，但它们收敛于系统的平衡点，从而最大限度提高了网络生存期，获得了网络的最佳覆盖度。节点静态和动态部署时，迭代次数与覆盖度的函数关系如图3所示。

图3 节点静态部署和动态部署的第n次迭代与覆盖度的函数关系

从图3可以看出，在节点具有移动性的动态部署中，覆盖度增加了大约30%。但由于节点具有移动性，覆盖度的增加也可能会导致通信开销的增加，原因是：(1)对节点的移动指令进行加密和认证；(2)节点的移动可能会导致临时数据包的丢失以及数据的损坏，从而引起通信路由上的安全认证属性进一步增强。尽管节点重新部署会降低通信成本，但是节点的移动会增加电池成本，因此可能会降低系统的总体效益。

图4 节点静态和动态部署的第n次迭代与节点损失(电池的原因)百分率的函数关系

迭代次数与节点损失之间的关系如图4所示。从此图可以看出，动态部署明显优于静态部署，损失的节点数减少15%～20%。在静态部署情况下，节点的损失呈指数级，而在动态部署的情况下，由于总能量的分配更加优化，节点在簇内是逐渐消亡的。静态部署方式下，节点的消亡会给覆盖度带来损失，由此会延长数据传输的路径，增加数据传输的能耗。

4 结论

本文基于多目标的遗传算法，提出了一种移动传感器节点的动态且高能效的部署方式。这种方式利用节点的移动性，以最佳方式对传感器节点进行重新定位，从而进一步优化节点的分配、路由配置，进而最大限度提高网络覆盖度和生存期。在实验中可以观测到，由于节点的重定位提高了电池利用率(适应度)，因此能量在各种不同功能性节点之间的分配更加合理。在适应度参数保持平衡的情况下，节点位置的改变会导致节点功能的改变，这也会减少网络内节点“重分簇”的次数。

[1] 付华,韩爽.基于新量子遗传算法的无线传感器网络感知节点的分布优化[J]. 传感技术学报,2008,21(7): 1259-1263.

[2] 陈喻,王飞宇,杨任尔,等.利用sink的移动性提高无线传感器网络寿命[J].机电工程, 2013,30(5):636-640.

[3] 黄月,项妹,肖磊,等. 无线传感器网络的节点部署问题研究[J]. 控制工程,2012,19(4):648-649.

[4] KHANNA R, Liu Huaping， CHEN H H. Self-organization of sensor networks using genetic algorithms[C]. IEEE International Conference on Communication, Istanbul, 2006：3377-3382.

[5] 张石,鲍喜荣,陈剑,等. 无线传感器网络中移动节点的分布优化问题[J]. 东北大学学报(自然科学版), 2007,28(4):489-492.

[6] 唐明虎，张长宏，昝风彪. 无线传感器网络APIT定位算法[J]. 微型机与应用，2010,29(21):1-4.

[7] 班冬松,温俊,蒋杰,等. 移动无线传感器网络k-栅栏覆盖构建算法[J]. 软件学报, 2011,22(9): 2089-2103.

[8] 何璇, 郝群, 宋勇. 一种移动无线视频传感器节点的覆盖算法[J]. 传感技术学报, 2009, 22(8):1163-1168.

[9] 叶苗,王宇平，代才，等. 无线传感器网络中新的最小暴露路径问题及其求解算法[J]. 通信学报，2016,37(1):49-60.

[10] 丁凡，周永明. 移动性无线传感器网络吞吐量跨层优化[J]. 电子技术应用, 2013,39(2):100-102.

[11] 王璨，骆坚，张大方，等. 一种基于移动性的无线传感器网络分簇路由协议[J].计算机工程与科学,2012,34(3):6-12.

An adaptive genetic algorithm based on coverage optimization in wireless sensor metworks

Wang Qi, Wang Qingping

(College of Physics and Electromechanical Engineering, Hubei University of Education, Wuhan 430205, China)

In resource-constrained and multi-hop wireless sensor networks, unreasonable nodes distribution or network topology will bring about the sensing shadow and coverage holes, which will badly affect data sensing and energy efficiency of the network. According to the total fitness associated with node movement, a genetic algorithm based on node mobility was proposed, which divided all nodes into clusters and relocated them to achieve the optimization of coverage and dynamic deployment of nodes with high energy efficiency. Simulation experiments showed that this approach optimally relocated sensor nodes, further optimized node deployment and route assignment, which made a better distribution of energy among various functional nodes, also reduced frequent re-clustering by just exchanging the positions while maintaining fitness parameters in equilibrium, thus maximized coverage and network lifetime.

dynamic deployment; coverage; energy efficiency; fitness; genetic algorithm; simulation

湖北省高等学校优秀中青年科技创新团队计划项目(T201417)

TN918.91

A

10.19358/j.issn.1674- 7720.2017.08.003

王骐，王青萍.基于覆盖度优化的自适应遗传算法[J].微型机与应用，2017,36(8)：7-10，14.

2016-11-21)

王骐(1970-)，男，博士，副教授，主要研究方向：无线传感器网络安全、嵌入式系统应用。

王青萍(1980-)，女，博士，副教授，主要研究方向：光电功能材料与器件。

________________________