传感器网络中连通覆盖算法研究  

Connected Cover Algorithm in Sensor Networks

作　　者：于浩[1] 朱志勇[2] 蒋朝惠[3] 

机构地区：[1]贵阳中医学院,贵州贵阳550002 [2]长沙学院计算系,湖南长沙410003 [3]贵州大学计算机科学与信息学院,贵州贵阳550025

出　　处：《湘潭大学自然科学学报》2009年第3期148-153,共6页Natural Science Journal of Xiangtan University

基　　金：湖南省教育厅资助项目(07C167);长沙学院资助项目(CDJJ06010112)

摘　　要：作为一种新型的无线自组网络,传感器网络在环境与军事监控,地震与气候预测等许多方面都具有广泛的应用前景.基于正方形网格剖分的良好特性,提出了一种分布式的近似最小连通覆盖集的构造算法.新算法中:Sink节点首先将其目标区域剖分为正方形网格,并将得到的剖分信息广播给网络中的所有传感器节点;然后,网络中的传感器节点再通过周期性与其邻节点交换信息,来构造目标区域的近似最小连通覆盖集.算法分析和仿真实验表明,与已有类似算法相比,新算法在连通覆盖集大小方面具有更优的性能.As a new type of wireless ad hoe network, sensor network has broad applied prospects in many fields, such as military monitoring, earthquake and whether forecasting, based on the good characteristics of ＂square grid partition＂, a new distributed approximate algorithm for constructing the Minimal Connected Cover Set is presented, in which, Sink partitions its area of interest into square grids firstly, and then broadcasts the partition information to all the sensors in the whole network. According to those received partition information of the area of interest, each sensor node will construct the Minimal Connected Cover Set of G through information exchanges among its neighbors only. Algorithm analysis and simulation results show that, the newly given algorithm outperforms the traditional similar algorithms in the size of constructed connected cover set.

关 键 词：传感器网络 最小连通覆盖集 正方形网格剖分 分布式 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]