基于改进的微粒群算法的WSN节点部署策略.pdf

《基于改进的微粒群算法的WSN节点部署策略.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第29卷第4期广西师范大学学报：自然科学版Vo1．29No．42011年l2月JournalofGuangxiNormalUniversity：NaturalScienceEditionDec．2011基于改进的微粒群算法的WSN节点部署策略郑磊，朱正礼h。，侯迎坤(1．南京林业大学信息科学技术学院，江苏南京210037；2．南京理工大学计算机科学与技术学院，江苏南京2100943．泰山学院信息科学技术学院，山东泰安271021)摘要：在无线传感网络部署中，必须保证无线传感器节点能够有效地覆盖被监测区域。为了减少

2、节点部署时产生覆盖盲区，提高网络的覆盖率，本文提出了一种基于改进微粒群算法的无线传感器网络节点部署优化策略，以网络的覆盖率为适应值函数，将传感器节点的部署问题转化为目标优化问题，通过采用k-means聚类算法划分子种群，并且对子种群进行动态重组，减弱微粒对局部最优点的追逐，实现对基本PSO算法的改进，有效地解决了标准PSO算法中的粒子“早熟”问题，同时也加快了算法收敛速度。实验结果表明，该部署策略最大可能地减少了网络中的覆盖盲区，有效提高了网络覆盖率。与基本微粒群算法、传统遗传算法和蜂群算法的优化效果相比较，其覆

3、盖率分别提高了4．11Ao、9．75和5．25％。关键词：无线传感器网络；微粒群算法；k-means聚类；子种群中图分类号：TP393文献标识码：A文章编号：1001—6600(2011)O4—0056—070引言无线传感器网络(WSN)是由大量具有通信和计算能力的传感器节点以自组织和多跳的方式构成的无线网络，能够协作地感知、采集、处理和传输网络覆盖区域内感知对象的监测信息，并将其报告给用户_】J。无线传感器网络在军事、交通、医疗护理以及环境监测等很多方面都有很大的潜在应用价值l_2]。节点部署是无线传感器网络中

4、的一个重要问题，它反映了网络所能提供的感知服务质量。目前，无线传感器网络的节点部署主要有两种方式：确定性部署和随机部署]。确定性部署方式是指，在无线传感器网络状态相对固定或待部署的区域大小确定的情况下，可以根据预先配置的节点位置确定网络拓扑结构或增加关键区域内的传感器节点密度。然而在实际自然环境中，由于监测区域环境恶劣或网络情况不能预先确定，通常采用高空抛撒的随机部署方式，但是这种部署方式容易产生覆盖盲区，在一定的部署密度下很难达到预期的覆盖率要求。因此，如何减少覆盖盲区、提高网络的覆盖率，是无线传感器网络中一个

5、亟待解决的重要问题。文献Es-1利用鱼群算法并行寻优、收敛快速的特点，提出了一种基于鱼群算法的WSN覆盖优化策略。文献E6]提出了基于虚拟力的移动传感器布置算法(virtualforcealgorithm，VFA)，该方法综合了场势和盘包的概念，但VFA没有解决“盲区”的问题。文献[7]提出了一种基于虚拟菱形网格的传感器节点部署算法，该方法将确定性部署和自组织部署两种方法集成到一个统一的平台内。文献[8]和文献[9]都提出了一种基于微粒群算法的无线传感网络部署优化方法，虽然证明微粒群算法能够有效实现无线传感网络部

6、署优化，但是标准粒子群算法在空间搜索时，容易陷入“早熟”现象，限制了微粒的搜索范围。针对以上问题，本文提出一种基于改进微粒群算法(KMPSO)的无线传感器网络节点部署优化策略。在优化的过程中，通过引入是一means聚类算法，将种群划分为几个子种群，使各子种群之间彼此独立优化；同时，为了增强子种群间的信息交流，对子种群进行动态重组，减弱微粒对局部最优点的追逐，避免基本PSO算法中的粒子“早熟”现象，提高网络的覆盖率。收稿日期：2011-09—25基金项目：国家自然科学基金资助项目(61072148)；南京林业大学科

7、研创新基金资助项目(163070037)通讯联系人：朱正礼(1966一)，男，江苏南京人，南京林业大学副教授。E—mail：haitian2001@163．corn第4期郑磊等：基于改进的微粒群算法的WSN节点部署策略1微粒群算法(PSO)标准微粒群算法n。将每个个体看作是Ⅳ维搜索空间中的一个没有质量和体积的微粒，在搜索空间中以一定的速度飞行。该飞行速度由个体的飞行经验和群体的飞行经验进行动态调整。设X一(xX⋯，XⅣ)为微粒i的当前位置，V一(V⋯，VⅣ)为微粒的当前飞行速度，P一(PP⋯，PⅣ)为微粒i所经历

8、过的最好位置，也称作Pbest；种群中所有微粒所经历的最好位置用表示，也称作gbest。对第t次迭代，微粒i在d维空间(1≤≤N)的位置与速度遵循如下公式进化：(f+1)一wV耐(￡)+f1rand()(Pf—X(￡))+C2rand()(Pg—X埘(￡))，(1)耐(f+1)=X耐(f)+V(f+1)，(2)其中：为惯性系数，它使微粒具有扩展搜索空间的趋势，有能力探索新