基于感应区域像素的无线传感器最小覆盖集近似算法  

Approximation Algorithm of Minimum Cover Set in WSN Based on Pixels of Sensing Region

作　　者：洪刚[1,2] 汤宝平[2] 裴勇[2] 

机构地区：[1]长江师范学院数学与计算机学院,重庆408001 [2]重庆大学机械工程学院,重庆408030

出　　处：《微电子学与计算机》2012年第12期120-123,共4页Microelectronics & Computer

基　　金：重庆市科委自然科学杰出青年基金计划(CQCSTC2011jjjq0006);重庆市科技攻关计划(CQCSTC2011AAC3063)

摘　　要：提出了基于感应区域像素的最小覆盖集问题求解算法.算法通过将节点感应区域离散化为一系列像素点,用感应区域像素点的点阵来近似逼近节点感应区域,通过判定感应区域内所有像素点的被其他节点覆盖的情况即可确定节点是否冗余.理论分析了算法的可行性以及性能,讨论了影响算法精度的因素,并通过实验对算法的性能进行了评估,验证了理论的正确性.通过与CVT算法对比实验数据表明,算法可以得到和CVT算法相当的最小覆盖集,而其时间复杂度要优于现有的CVT算法.This paper presents an approximation algorithm of minimum cover set based on pixels of sensing region. The node sensing area is discredited into a series of pixels, and a node is redundancy if all of its pixels are covered by other nodes. So we can get the maximum redundancy node set, and also its complement -- the minimal cover set. The feasibility and performance of the algorithm is discussed, correctness of the algorithm was evaluated by experiment. Compared experimental data show that its minimum cover set is equivalent to the CVT algorithm, and its time complexity is superior to the CVT algorithm.

关 键 词：无线传感器网络 最小覆盖集 冗余 像素点 

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