基于遗传算法的农业无线传感器节点部署算法设计

张伯琰，邹腾跃

(福建农林大学机电工程学院，福建 福州 350002)

0 引言

利用农业无线传感器网络(Agricultural Wireless Sensor Network，AWSN)精确获取农作物生长环境信息是现代农业发展的重要技术手段，农业无线传感器网络通常由多个无线传感器节点(Wireless Sensor Network Nodes，WSNN)组成，组成传感器网络的传感器检测半径大多相同，传感器的布局会直接影响到农业无线传感器网络的成本、效率和使用寿命。在无线传感器网络部署阶段，传感器的检测范围为圆形，多个传感器进行部署，不可避免地产生重叠区域。若传感器数量过多，检测范围重叠程度较大，会导致传感器检测数据的冗余，数据处理烦琐，无线传感器网络系统整体电量耗能增加，缩短无线传感器网络寿命[1]。农业无线传感网络设置环境复杂，维护困难，大大增加了农业无线传感器网络的安装维护成本。

孙宇晶[2]提出了一种基于感知模型的传感器部署算法，感知模型与遗传算法相结合，实现了传感器节点部署的遗传求解过程。程龙等[3]就无线传感器的等边部署方法进行了讨论，将不同条件下的等边多边形部署方法做了仿真，并得出不同条件下使用不同等边多边形部署的结论。许佳慧等[4]进行了基于网络扫描算法估算传感器位置的仿真试验。吴传程等[5]提出了一种基于区域面积覆盖强度的虚拟力覆盖优化算法，有效解决了不同传感器数量情况下的节点部署问题，但存在大面积重叠现象。针对农业无线传感器网络节点部署，本文提出一种基于离散计算的遗传算法部署策略。

1 问题描述与模型建立

1.1 问题描述

随着智能技术的发展，智慧农业成为热点问题。基于大数据的智慧农业发展迅速，物联网技术在智慧农业中发挥了极大的作用[6]。物联网技术可以监控农业的生长情况和环境条件，并构建信息交流网络平台，实现信息的互通与交流[7]。合理的无线传感器部署算法可以延迟黑洞效应的产生时间，有效提升无线传感器网络生命周期[8]。传统的农业无线传感器部署通常采用正多边形的部署办法，可以实现检测区域的高覆盖率，但是这会使传感器数量大大增加，同时因为传感器数量的增加，使得重叠面积增加，冗余数据也会随之增加，进而促进了节点的衰亡。

1.2 模型建立

为了改进上述问题，在确保高覆盖率的同时，减少传感器数量，设计了一种基于改进遗传算法的农业无线传感器网络节点部署算法。本算法以舍差取优点策略作为算子选择方案。用整个分布图的节点坐标作为遗传个体，每个个体的染色体包含一个多点坐标。本设计没有使用二进制编码，而是直接对染色体进行保留或舍弃操作，利用图形计算，更加精确地计算相关参数。假设传感器检测范围都为半径相同的圆形区域，对检测半径为7 m的传感器检测范围圆S进行细分为1 m/pixel离散的示意如图1所示。

图1 传感器检测范围圆离散化Fig.1 Discretized circle of sensor detection range

(1)

式中P(x，y)——离散化后的圆(x，y)坐标的值

r——待离散化圆的半径

当P(x，y)与圆心O的距离小于等于半径时，P(x，y)=1，否则P(x，y)=0。为了方便计算，并没有直接赋予颜色值，而是用1代表覆盖范围，0代表未被覆盖。

代数计算无线传感器检测圆面积公式为

S=π·r2

(2)

式中S——传感器检测范围面积

经过离散化后，计算无线传感器检测范围圆面积公式为

(3)

式中S′——离散化后圆的面积

针对此模型给出以下定义。

定义1：单层有效覆盖面积，在一个无线传感器的覆盖范围里，除去其他传感器造成的重叠区域部分的面积。

定义2：覆盖值，样本区域被分割为多个长宽各1 m的区域，当该区域被n个传感器覆盖时，其覆盖值为n。该值用于表达每块区域被传感器覆盖的程度。

定义3：覆盖率，表示样本被传感器覆盖的程度。

如图2所示，当两个节点的覆盖面积发生重叠，执行离散圆的加和操作，基因表达模型公式为

图2 两个节点检测范围发生重叠示意Fig.2 Schematic diagram of overlapping monitoring range of two nodes

p(xr+x，yr+y)n+1=p(xr+x，yr+y)n+P(r+x，r+y)x，y∈[-r，r]

(4)

式中p(x，y)——样本中点(x，y)坐标的值

按照本算法拟对基因为{(1，2)，(6，9)，(11，1)，r=7}的个体进行基因表达，表达模型过程如图3、图4和图5所示。

图3 基因表达模型过程步骤一Fig.3 Gene expression model process′s step one

图4 基因表达模型过程步骤二Fig.4 Gene expression model process′s step two

图5 基因表达模型过程步骤三Fig.5 Gene expression model process′s step three

如图3所示，首先将离散化的传感器检测范围圆按照染色体记录的坐标映射到画布上，对应位置覆盖值相加，传感器检测范围圆内覆盖值为0+1=1。超出边界部分不予记录。

表达完染色体1后表达染色体2，同样也是对应位置相加，两圆重叠部分的值为2

最后表达染色体3，对应位置相加，3个圆重叠部分值为3；至此本算法完成了该基因的表达工作。

2 算法设计

2.1 算法设计思想

在一定的试验条件下，无线传感器网络节点的部署是个非确定多项式问题，该问题不确定能否在多项式时间内找到答案，传统估计计算覆盖率的方法为样本区域中划分出n个采样点，然后通过统计计算这几个采样点的覆盖情况大致得出覆盖率情况[9]。这种办法原理可行，但误差较大，容易出现极端情况。本算法用离散化的方法，取代原先的代数计算，且比粗略估计覆盖率的方法更为准确，不易出现极端误差，算法易懂，通过遗传算法优胜劣汰的特点，可以得出比较好的部署方案。本算法类似遗传算法，将覆盖率作为适应度函数可以较为直观地观测其收敛过程，不同于以往遗传算法的是，本算法在产生新的父代时并不是先产生固定数量的子代后择优产生下一代的父代，而是在产生子代地过程中，若子代的适应度高于父代时，直接代替上代父代作为新的父代。由于产生新的父代适应度总是高于上一代父代，且逐步趋于一个极限值，所以本算法是收敛的。由于在产生子代的配对样本的坐标是随机产生的，相当于一部分子代全部变异，所以本文未设置另外的变异概率。同时遍历样本中每个区域的覆盖值，可直接获得该区域的传感器覆盖情况。

2.2 算法设计步骤

步骤一：建立一个样本个体，设定该样本个体中染色体数量即无线传感器数量N，并随机生成含传感器坐标的N个染色体。

步骤二：产生首次遗传的父代之一。随机产生K个样本进行两两相融。每次先产生染色体数目为2N的样本，通过图像处理的办法将基因表达出来，保留覆盖率最大的二倍体样本。

步骤三：计算每个传感器节点染色体的单层有效覆盖面积，将单层覆盖面积最小的染色体移除，重复此移除过程，直到该样本中保留最后的N个染色体。

步骤四：算法随机产生一个新的样本，新样本与上一步骤产生的父代做杂交，先产生染色体数目为2N的样本，通过图像处理的办法将基因表达出来，接着重复步骤三，产生的新个体与父代做比较，若适应度高于父代则代替原父代成为新的父代，否则舍弃该子代重复步骤四，直到适应度在很长一段时间里不再发生变化，到达了要求的适应度或者达到了循环次数即表示完成了算法过程。

主程序算法流程如图6所示。

图6 主程序算法流程Fig.6 Flow chart of main program algorithm

K的值取5，使得初始父代有较高的覆盖率，减少算法循环次数，杂交算法流程如图7所示。

图7 杂交算法流程Fig.7 Flow chart of hybrid algorithm

本算法设计杂交时先形成二倍体，然后表达该二倍体，再剔除差的基因，重复此循环，直到新形成的个体，染色体数目正常，至此视为产生了符合要求的子代。

3 仿真试验与数据分析

将试验样本条件设置为长和宽均为100 m，细分0.1 m/pixel；设置所有传感器检测圆半径r=12 m，即传感器检测圆半径为120像素；设置染色体(无线传感器节点)个数N分别为25、28、30和32个，单代杂交最大次数为19时，对此算法进行仿真。

无线传感器节点数目为25、28、31和32个时，通过本算法得到的无线传感器网络部署如图8所示，对应的适应度曲线如图9所示。孙宇晶[2]的研究中，长和宽各90 m的环境下，传感器半径12 m、覆盖率达到92%时，传感器最少需要35个；而通过本算法，在长和宽均为100 m的情况下仅仅需要25个即可达到93.64%的覆盖率。从适应度曲线不难看出，随着适应度越来越高，出现更优的新一代所需的杂交次数也越来越多，传感器个数越多，其覆盖率也越高，但覆盖率与传感器个数并不成线性关系。此算法是一种随机排布的加速算法，使随机得到的部署图能快速符合需求，并且随运行时间推移，子代的适应度将收敛于一个极限值，并随着传感器个数的增加，适应度也在增加。

图8 N为不同值时的传感器节点部署Fig.8 Sensor nodes deployment when N is different value

图9 N为不同值时适应度曲线Fig.9 Fitness curve when N is different value

4 结束语

本算法利用离散的图形计算方法，实现了农业无线传感器网络节点的部署算法。利用本算法，可以方便地求得特定条件下覆盖率较高的无线传感器网络部署方案。本算法的时间复杂度与无线传感器节点数量和离散细分有关，若试验精确度要求不高则可将细分设置为1 m/pixel，可大幅度提高运算速度。遗传迭代次数越多，本算法得到的试验结果越好。当细分值越小时，相同条件下结果的精确度越好。该算法的计算过程可以进一步改进，先在高细分下求得较好的部署方案，再通过低细分继承其结果进一步求取结果；其次优化杂交算法可以提升计算速度。