WSN中有效的最小单位圆集覆盖算法详解.pdf

第26卷第 6期 计 算 机 应 用 研 究 V o.l 26 N o. 6 2009年6月 ApplicationR esearch of Computers Jun. 2009 WSN , , (哈尔滨工程大学 计算机科学与技术学院, 哈尔滨 150001) : 针对具有不同传输半径的无线传感 网络覆盖与广播数据转发问题, 提出了一种以最小单位圆覆盖集 作为广播数据转发集的算法该算法能有效计算出覆盖范围的轮廓集, 具有最优的时间复杂度O ( n log n) 对 每 个节点, 该算法以其最少数量的邻居节点子集实现所有邻居节点的覆盖, 并证明了该算法找到的最小单位圆 覆盖集与其轮廓集是相等的详细的仿真实验及与现有算法的比较表明, 提出的覆盖算法不仅以最少数量的节 点实现了网络覆盖与广播数据转发, 同时延长了网络生命期 : 无线传感 网络; 覆盖算法; 单位圆覆盖集; 能量 : TP302 : A : 2009) doi: 10. 3969 /j. issn. 2009. 06. 059 Efficientm inmi um unit disks set coverage algorithm in w ireless sensor networks ZHANG Jin, LIU Dax in, XU Yuezhu ( Colleg e of Computer S cience Technology, Harbin E ng ineering University, Harbin 150001, Ch ina) Ab stract: To overcom e coverage and broadcasting data forward ing problem s inw ireless sensor newt orks w ith different trans m ission rad ius nodes, th is paper proposed a novel algorithm based on m inmi um un it disks cover set to forw ard broadcasting da ta, wh ich cou ld calcu late skyline set efficiently w ith the optmi al tmi e complexityO ( n log n ). The proposed algorithm covered each node w ith m in mi um un it disk cover set, and the m in mi um un it disk cover set of a nodew as equivalent to its skyline set. Detailed smi u lation resu lts and comparisonsw ith existed algorithm sp rove that the proposed algorithm not only covers all nodes w ith m in mi um nodes, but also prolongs the network lifetmi e. K ey words: w ireless sensor networks(W SN ); covering algorithm; unit disk cover set; energy (WSN) , ( ), , W SN