邹长忠

(福州大学数学与计算机科学学院，福建福州 350116)

0 引言

无线传感器网络(WSNS)涉及众多学科，扩展了人们的信息获取能力，能够获取客观物理信息，具有广阔的应用前景．它主要由大量具有传感能力和计算能力、数据传输能力的小型传感节点构成．传感器网络部署问题是根据特定的要求，在给定的环境下，如何放置节点，达到预定的要求．其中很重要的一个指标就是覆盖度．覆盖可以有区域覆盖、点集覆盖、栅栏覆盖．部署方面根据目标区域是否可以靠近，分为决定性部署和随机性部署．但是在环境恶劣地方，如高原、雪山，或者要部署在敌区附近等这些人为不可能靠近的地方，只能采用随机部署方法，即通过空投等方式．这样必然造成节点分布不均，或者达不到任务要求．随着可移动节点的引入利用，可以在随机部署后，利用节点的移动来重新部署，达到预定的要求．文［1－5］利用虚拟合力算法，节点的移动依靠虚拟合力作用，节点沿合力方向虚拟移动，形成新的位置．文献［6－10］提出基于计算几何模型的节点部署方案．文［11］利用行列扫描法来均衡节点．文［12］将问题转化为最小成本最大流问题，通过求解此问题，实现对网络的优化部署．文［13］提出一种基于二部图匹配的重新部署算法，将初始网络描述成一个二部图，图的顶点集合由移动节点集合和需要覆盖的网格集合组成．如果某个移动节点可覆盖某个网格，则它们之间存在一条边，衡量……