摘 要： 在无线传感器网络中，传感器节点的分布通常具有随机性和密集性，监测区域会出现覆盖盲区或者覆盖重叠。为此，推导出了无线传感器最优覆盖模型计算最少节点个数的公式，对遗传算法中的适应度函数公式做了改进，将多重覆盖率和覆盖率的组合作为适应度函数。根据遗传算法的相关内容和流程图，利用遗传算法对覆盖策略做了仿真模拟，证明了所选用的方法的正确和优越性。
关键词： 无线传感器网络；覆盖；节点；遗传算法
无线传感器网络WSN(Wireless Sensor Network)最早来源于军事领域，1978年，卡内基—梅隆大学就在美国国防高级研究项目组(DARPA)的资助下成立了分布式传感器网络工作组，专门研究以WSN为基础的军事监视系统。该系统是传感器技术、嵌入式计算技术、现代网络及无线通信技术、分布式信息处理技术等的综合应用。
遗传算法[1]GA(Genetic Algorithm)是模拟达尔文的遗传选择和自然淘汰生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。该算法最早是1975年由美国Michigan大学HOLLAND J教授提出来的，它是一种基于自然选择和群体遗传机理的高度并行、随机、自适应搜索算法。GA模拟了自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，将每一个可能的解看作是群体中的一个个体，并将每一个个体编码成字符串的形式，根据预定的目标函数对每个个体进行评价，给出一个适应值，利用遗传算子选择、交叉、变异等过程对这些个体进行组合，得到一群新个体。这一群新个体由于继承了上一代的一些优良性状，所以明显优于上一代，这样就逐步向着更优解的方向进化。
遗传算法的主要优点[2]是从代表问题可能潜在解集的一个种群开始并行操作的，而不是从一个初始点开始寻优，在一定程度上避免了搜索过程收敛与局部最优解。其中一个种群则由经过基因编码的一定数目的个体组成。初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的近似解，在每一代根据问题域中个体的适应度大小挑选个体，并借助于自然遗传学的遗传算子进行组合交叉和变异，产生出代表新的解集的种群。
1 传感器网络最大覆盖度的理想模型
2 最优部署模型节点数目公式
针对基于网格的WSN理想最优部署图，要求解所使用的最少节点数目Ns，并不能简单地利用矩形长边的节点个数与宽边的节点个数相乘的积得出。因为由图可以看出，每列的节点并不是一一对齐的，而是错落排列的。根据右边界位置的不同，区域中每行节点的数目也不同。在右边界选择可以改变的情况下，每行节点的数目有时相同有时不同。在推导节点数目Ns时，要对右边界位于不同位置的情况分别进行讨论。在图1的基础上，为了便于对Ns进行推导，在原图上增添了一些辅助线，作出求解最优模型节点数目的分析图，如图2所示。将各点坐标标注其上，底边横坐标从0开始，每隔
R依次标注。左边界从R/2开始，每隔3R/2依次标注。把矩形各角依次标注字母A、B、C、D。
假设传感器的感知半径为R，被监测矩形区域的长为L，宽为W，节点的行数为Ws，每行节点的数目为Ls，所有节点的数目为Ns。由图2可以看出，由底边向上算起，作第2行圆的下切线一条辅助线l，则底边到l的距离为:
3 基于遗传算法的最优覆盖策略
3.1 算法网络模型
3.2 算法适应度函数的求解
在监测区域A的面积和传感器的感知半径一定的情况下，要使得节点数目最少且覆盖度最大就是要使节点的分布尽量均匀，使得A内的多重覆盖的区域最小。所谓多重覆盖区域[4]就是区域被两个或两个以上的传感器节点覆盖(覆盖重数≥2)。因此，问题就转化为在一定的覆盖度的前提下，如果能使重叠面积最小，才能使用最少的传感器节点且分布更加均匀。将具有多重覆盖区域的面积设为So，将m个活动节点的面积相加即为展开后的总面积，则可以写作m×Asi=mπRs2。对于监测区域A有如下公式：
遗传算法的适应度函数[5]尤为重要，它的选择直接关系算法最后的仿真实验结果的准确性，本模型统一由式(4)和式(5)两个子函数构成，并分别加上一个权值w1、w2，保证w1+w2=1，具体值可以由网络设计者针对网络的需要来决定。
F=w1×f1+w2(1-f2) (6)
遗传算法就是要使得适应度函数取最大值，而本文的目标是使多重覆盖度越小越好。因此对于f2函数应该取相反值，可以得到(6)的适应度函数。本文对遗传算法的适值函数F做了改进，由面积占有率的函数表达式组成，式(5)比用节点的利用率[5]表示能获得更好的效果。
4 仿真实验
本实验采用MATLAB 7.0对遗传算法求解最优覆盖节点的方法进行仿真。
设监测区域为150×150的二维平面，传感器的感知半径R=15，初始群体随机部署节点个数n=150，对于以上取值也满足算法的要求，n远大于上面所计算出的Ns的数值。基于遗传算法进行求解，交叉概率一般在[0.4，0.99]中选取，因为在优化过程中，交叉概率太大容易破坏种群中的优良模式，太小虽然容易找到全局最优解但进化的速度太慢。变异概率选取一般是要求小于0.1。考虑以上原因，实验选取交叉概率定为0.8，变异概率定为0.05，其目的就是既可以使节点最好的遗传上一代的优秀节点又防止节点出现节点局部最优而使算法过早地收敛。根据遗传算法的流程图和以上实验选取的参数因子，可以进行算法的仿真。实验中对每运行100代的相关数据(包括覆盖度、多重覆盖度、活动节点的个数等信息)都做了数据记录，图3(a)、3(b)、3(c)、3(d)依次为算法初始状态、100、200和300代时的仿真图，图中所显示的节点均是处于活动状态节点的分布情况。本文选取运行代数为300代时作为最后的最优部署图。
有些遗传算法[6]是采用了覆盖度和节点利用率作为适应度函数，从而达到在满足覆盖度要求的前提下使节点数目最少的目的。本文利用覆盖度和节点利用率作为适应度函数做了仿真实验，在算法其他参数不变的前提下，将式(6)中以多重覆盖率作为适应度函数改为节点利用率的函数，对实验进行重新模拟，同样将实验运行到第300代，并记录了与上面实验同样的相关数据信息，分别从覆盖度和活动节点这两个数目与上面的实验做比较分析，可以得到图3(e)和3(f)的比较图。
从图3(e)中可以看出，随着代数的增加，选用覆盖率和多重覆盖率的组合作为适应度函数要比选用覆盖率和节点利用率的组合作为适应度函数所得到的覆盖度高。并且改进前的波形曲线有时有震荡的现象，即得到的覆盖度的结果会出现不稳定的现象。改进后的波形基本接近正态分布曲线，整个实验过程很稳定，不会出现覆盖度忽高忽低的现象。
从图3(f)中可以看出，随着代数的增加，选用覆盖率和多重覆盖率的组合作为适应度函数所用的节点数目要比选用覆盖率和节点利用率的组合作为适应度函数的节点淘汰速度要快。并且到300代时，改进后的算法所用节点数目为47个，比改进前的算法所用节点数目58个要少，所以改进后的算法更加接近最优模型中节点的数目。由图3(e)、3(f)可以看出，在整个实验的过程中，改进后的算法的节点数目基本一直都小于改进前的节点的数目，即使实验运行到某一代停止了，改进后的算法依然要明显优越于改进前的算法。
本文改进的遗传算法通过以上仿真实验数据对覆盖度和节点数目的比较，可以明显地看出，本实验选用的多重覆盖度代替节点利用率作为适应度函数的遗传算法是切实可行的。也达到了所要求的在满足一定的覆盖度的前提下，减少节点利用率的实验目标。
参考文献
[1] WARNEKE B， LAST M， LIEBOWITZ B. Smart dust: communicating with a cubic-millimeter computer[J]. IEEE Computer Magazine， 2001，34(1):44-51.
[2] CHONG Chee-Yee， KUMAR S P. Sensor Networks: Evolution[J]. Opportunities and Challenges Proceedings of the IEEE， 2003，9(8):1247-1256.
[3] SLIJEPCEVIC S， POTKONJAK M. Power efficient organization of wireless sensor networks[C]. In: Glisic S， ed. Proc. of the IEEE Conf.on Communications. Helsinki: IEEE Press，2001:472-476.
[4] ZHANG H， HOU J C. Maintaining sensing coverage and connectivity in large sensor networks[J]. Wireless Ad Hoc and Sensor Networks， 2005，1(1):89-124.
[5] 蒋杰，方力，张鹤颖，等.无线传感器网络最小连通覆盖集问题求解算法[J].软件学报，2006，17(2):175-184.
[6] 刘华峰，金士尧.三维无线传感器网络综述[J].计算机应用，2007，27.