基于Memetic算法的无线传感网络覆盖优化-论文.pdf

《基于Memetic算法的无线传感网络覆盖优化-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第27卷第2期河南工程学院学报(自然科学版)Vo1．27．No．22015年6月JOURNALOFHENANINSⅡTUrE0FENGINEERINGJun．2015基于Memetic算法的无线传感网络覆盖优化陈伟佳，关健(1．闽江学院数学系，福建福州350108；2．闽江学院现代教育技术中心，福建福州350108)摘要：针对无线传感网络覆盖优化中工作节点集难以选取的问题，提出了一种基于Memetic的覆盖优化算法．该算法主要由选择算子、交叉算子、变异算子、禁忌局部搜索算法和种群更新策略组成．利用相邻节点间的区域覆盖关系，减少局部搜索中邻域的目标函数值计算量、提高计算速度，并利用随

2、机和贪婪的策略构造一个质量较好的初始种群．仿真结果表明，该算法具有较强的搜索能力，能快速收敛于优秀解、实现工作节点集的优化选取、降低网络冗余和能耗、延长网络的生存时间．关键词：无线传感网络；覆盖优化；禁忌搜索算法；Memetic中图分类号：TP391文献标志码：A文章编号：1674—330X(2015)02—0073—05无线传感网络(WSNs)在军工和民用领域有着广泛的应用，如战场侦察、机械故障诊断、生物检测、家庭安防等⋯．由于无线传感网络通常应用在偏远无人值守的地方、电池更换不便，所以能耗控制是无线传感网络应用一个重要的研究方向．由于无线传感网络节点的高密度部署会带来大量的节点

3、冗余，所以需要进行网络覆盖优化，从大量的传感节点中合理地选取一组节点进入工作状态，以保证区域充分覆盖．覆盖优化通过降低网络冗余，节省了能源并延长了网络的生存时间，是一种非常有效的能耗控制技术．近年来，学者们陆续提出不同的智能优化算法求解无线传感网络的覆盖优化问题，如遗传算法J、粒子群算法J、鱼群算法L6等．遗传算法(GA)具有搜索速度快、并行搜索能力强的特点，但是容易陷入“早熟”收敛和局部最优，不利于找到全局最优解．禁忌搜索算法(rI’S)具有较强的“爬山”能力，在搜索过程中可以接受劣解，从而跳出局部最优解、转向其他区域搜索更好的解或全局最优解，但收敛速度慢，较难满足动态节点选取的

4、实时性要求．Memetic算法是一种将全局寻优与局部搜索相结合的算法框架J，兼顾广度和深度．基于Memetic算法框架，融合了遗传算法和禁忌算法，采用禁忌搜索算法作为局部搜索来增强遗传算法的搜索能力，并通过改进目标函数值的计算公式来提高算法的运算速度，同时利用随机和贪婪的策略构造较优的初始种群，仿真实验表明该算法是可行、有效的．1WSNs覆盖模型假定在一个形状规则的二维监测区域中投放Ⅳ个传感节点，各传感节点参数相同、坐标可知且相互独立．定义1监测区域离散化为mxn个像素，则整个监测区域记为像素集A={(，Y)I∈{1，2，⋯，m}，Y∈{1，2，⋯，／／,}}，(，Y)为像素点．定

5、义2传感节点C的坐标为(，Y)，有效感知半径为r，则该传感节点记为圆c=，Y，r}，E{1，2，⋯，Ⅳ}，所有节点记为C={c，C，⋯，C}．1．1网络节点利用率用布尔向量S={s。，s，⋯，s一，s}标志各传感节点的状态，si=1表示节点c。处于工作状态，s=0表示节点c处于休眠状态，则网络节点利用率收稿日期：2015—03—01基金项目：闽江学院科研育苗项目(YKY12009)；大学生创新创业训练项目(201410395029)作者简介：陈伟佳(1993一)，男，福建泉州人，本科生，主要从事智能算法的研究．通信作者：关健(1984一)，男，福建莆田人，工程师，主要从事网络通信技

6、术与智能算法的研究．E—mail：gjian_mail@163．tom．·74·河南工程学院学报(自然科学版)2015生∑．s()=．(1)1．2网络有效覆盖率像素点(，Y)被传感节点c覆盖的事件记为h(，Y)，i∈{1，2，⋯，Ⅳ}．当像素点(，Y)与传感节点c圆心的距离不大于半径r且传感节点c处于工作状态时，像素点(，Y)被传感节点c覆盖，记P{h(，Y)}=1，否则像素点(，Y)未被传感节点c覆盖，记P{h(，Y)}=0．事件h发生的概率P{h(，Y)}为一个二值函数：Pc，y={：．+y—yi’≤r且’c2，像素点(，Y)被节点集c中各节点覆盖的事件是相互独立的，则(，Y)

7、被节点集C覆盖的概率P{h(x，Y)}=P{h(，Y)}=1一P{[1h(，Y)}．(3)传感节点集C中工作节点所覆盖的像素点之和即为该节点集的覆盖区域，记为ⅣA(c)，有NA(c)=∑∑Pt(，y)}，(4)则网络有效覆盖率)=．(5)1．3覆盖优化数学模型WSNs覆盖优化的目标是在保证网络有效覆盖率尽可能大的情况下努力减少节点的利用率，可以通过加权将有效覆盖率和节点利用率两个子目标函数转化为总体目标函数，作为算法求解的适应值，定义为厂06(S)=∞1(1一())+