| 无线传感器网络最小连通覆盖集问题求解算法 |
| |
| 引用本文： | 蒋杰,方力,张鹤颖,窦文华.无线传感器网络最小连通覆盖集问题求解算法[J].软件学报,2006,17(2):175-184. |
| |
| 作者姓名： | 蒋杰 方力 张鹤颖 窦文华 |
| |
| 作者单位： | 1. 国防科学技术大学,计算机学院,湖南,长沙,410073
2. 国防科学技术大学,网络信息中心,湖南,长沙,410073 |
| |
| 基金项目： | 中国科学院资助项目;科技部科研项目 |
| |
| 摘 要： | 降低能耗以延长网络生存时间是无线传感器网络设计中的一个重要挑战.在传感器节点高密度部署的环境中,在保证网络性能的前提下,仅将最少量的节点投入活跃工作状态,而将其余节点投入低功耗的睡眠状态,是一种节约系统能量的有效方法.如何计算同时满足"覆盖要求"(工作节点必须能够完全覆盖目标区域)和"连通性要求"(工作节点组成的通信网络必须是连通的)的最小节点集合,是一个NP难问题.设计了一种基于目标区域Voronoi划分的集中式近似算法(centralized Voronoi tessellation,简称CVT),用于计算完全覆盖目标区域所需要的近似最小节点集.当节点通信半径大于等于2倍感知半径时,CVT算法构造的节点集是连通的;当节点通信半径小于2倍感知半径时,设计了一种基于最小生成树(minimum spanning tree,简称MST)的连通算法来计算确保CVT算法构造的覆盖集连通所需的辅助节点.理论分析和实验数据表明,CVT(+MST)算法的性能在时间复杂性和连通覆盖集大小方面都优于已有的贪婪算法.
|
| 关 键 词： | 无线传感器网络 网络生存时间 最小连通覆盖集 Voronoi划分 最大独立集 最小生成树 |
| 收稿时间： | 2005-03-10 |
| 修稿时间： | 8/3/2005 12:00:00 AM |
An Algorithm for Minimal Connected Cover Set Problem in Wireless Sensor Networks |
| |
| JIANG Jie,FANG Li,ZHANG He-Ying and DOU Wen-Hua.An Algorithm for Minimal Connected Cover Set Problem in Wireless Sensor Networks[J].Journal of Software,2006,17(2):175-184. |
| |
| Authors: | JIANG Jie FANG Li ZHANG He-Ying and DOU Wen-Hua |
| |
| Affiliation: | 1.School of Computer, National University of Defense Technology, Changsha 410073, China; 2.Network Information Center, National University of Defense Technology, Changsha 410073, China |
| |
| Abstract: | |
| |
| Keywords: | WSN (wireless sensor network) network lifetime MCCS (minimal connected cover set) Voronoi tessellation MIS (maximal independent set) MST (minimum spanning tree) |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《软件学报》浏览原始摘要信息 |
|
点击此处可从《软件学报》下载全文 |
|
