杨凯，刘全，张书奎,2，李瑾，翁东良

(1. 苏州大学 计算机科学与技术学院，江苏 苏州 215006；2. 南京大学 计算机软件新技术国家重点实验室，江苏 南京 210093)

1 引言

无线传感器网络是当前研究的热点，通过向目标区域部署大量价格低廉、具有移动、感知和通信能力的传感器节点构成的无线传感器网络，可广泛应用于军事、交通、医疗和救灾等领域。随着电子技术的不断发展，传感器节点的功能不断增强，体积不断缩小，使得利用无线传感网络完成对某一区域的监测成为可能。但是由于节点部署不均匀、环境外力影响或电量耗尽等因素而产生感知区域大型空洞，影响感知信息的精确性或降低通信的效率。因此，如何探测这些空洞区域，并对之进行修复成为传感器网络研究的重要内容之一。

空洞修复算法包括2部分：空洞探测和空洞修补。在空洞探测方面，文献[1]提出一种使用Voronoi图来发现空洞。文献[2]提出了 K覆盖(K-coverage)算法，使用计算几何中覆盖弧的相关性质进行空洞探测。在空洞探测中很少研究以地理信息作为辅助[3～6]。在空洞进行修复时，借助地理信息较多。文献[7～9]中，作者利用网格对传感器网络进行划分，部分文章使用地理信息进行空洞修复。文献[10]使用节点之间洪泛信息方式对空洞进行探测，只需要节点之间的相对位置。文献[3]使用移动节点获得不精确位置信息。文献[4～6]使用相互通信方式来确定节点位置，同样需要地理信息、GPS等设备的支持，对于大规模传感器网络来说成本昂贵，并且空洞修复问题本身就是一个NP问题， 使用地理信息仅仅将解决问题的精度提高，仍不能得到最优解。……