一种基于遗传算法的无线传感器网络覆盖模型一种基于遗传算法的无线传感器网络覆盖模型
在无线传感器网络中,传感器节点的分布通常具有随机性和密集性,监测区域会出现覆盖盲区或者覆盖重叠。
为此,推导出了无线传感器最优覆盖模型计算最少节点个数的公式,对遗传算法中的适应度函数公式做了改
进,将多重覆盖率和覆盖率的组合作为适应度函数。根据遗传算法的相关内容和流程图,利用遗传算法对覆盖
策略做了仿真模拟,证明了所选用的方法的正确和优越性。
摘摘 要:要: 在
关键词:关键词: 无线传感器网络;覆盖;节点;遗传算法
无线传感器网络
遗传算法[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。
评论1