基于正方形剖分的连通覆盖集快速实现算法

摘要

本文从快速回应用户或者其他指令中心发出的空间数据查询的应用需求出发,探讨了传感器网络中如何快速有效地构造查询区域的连通覆盖集问题,并提出了一种基于正方形的连通覆盖集快速实现算法SFAMCCS。通过将查询区域按一定尺寸的正方形剖分,节点利用临近节点的位置及覆盖的格点等信息构造查询区域的连通覆盖集。理论分析和仿真实验表明,SFAMCCS算法通过节点协作的方式,在较短的时间内得到的连通覆盖集大小可与已有集中式算法相当,与类似的其他算法相比,在运行时间和连通覆盖集大小等方面具有更优的性能。