主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公English
2022年专刊出版计划 微信服务介绍 最新一期:2021年第3期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
蒋杰,方力,张鹤颖,窦文华.无线传感器网络最小连通覆盖集问题求解算法.软件学报,2006,17(2):175-184
无线传感器网络最小连通覆盖集问题求解算法
An Algorithm for Minimal Connected Cover Set Problem in Wireless Sensor Networks
投稿时间:2005-03-10  修订日期:2005-08-03
DOI:
中文关键词:  无线传感器网络  网络生存时间  最小连通覆盖集  Voronoi划分  最大独立集  最小生成树
英文关键词:WSN (wireless sensor network)  network lifetime  MCCS (minimal connected cover set)  Voronoi tessellation  MIS (maximal independent set)  MST (minimum spanning tree)
基金项目:Supported by the National Natural Science Foundation of China under Grant No.90104001 (国家自然科学基金); the National Grand Fundamental Research 973 Program of China under Grant No.2003CB314802 (国家重点基础研究发展规划](973))
作者单位
蒋杰 国防科学技术大学,计算机学院,湖南,长沙,410073 
方力 国防科学技术大学,计算机学院,湖南,长沙,410073 
张鹤颖 国防科学技术大学,计算机学院,湖南,长沙,410073 
窦文华 国防科学技术大学,计算机学院,湖南,长沙,410073 
摘要点击次数: 4251
全文下载次数: 5435
中文摘要:
      降低能耗以延长网络生存时间是无线传感器网络设计中的一个重要挑战.在传感器节点高密度部署的环境中,在保证网络性能的前提下,仅将最少量的节点投入活跃工作状态,而将其余节点投入低功耗的睡眠状态,是一种节约系统能量的有效方法.如何计算同时满足"覆盖要求"(工作节点必须能够完全覆盖目标区域)和"连通性要求"(工作节点组成的通信网络必须是连通的)的最小节点集合,是一个NP难问题.设计了一种基于目标区域Voronoi划分的集中式近似算法(centralized Voronoi tessellation,简称CVT),用于计算完全覆盖目标区域所需要的近似最小节点集.当节点通信半径大于等于2倍感知半径时,CVT算法构造的节点集是连通的;当节点通信半径小于2倍感知半径时,设计了一种基于最小生成树(minimum spanning tree,简称MST)的连通算法来计算确保CVT算法构造的覆盖集连通所需的辅助节点.理论分析和实验数据表明,CVT(+MST)算法的性能在时间复杂性和连通覆盖集大小方面都优于已有的贪婪算法.
英文摘要:
      Reducing power consumption to extend network lifetime is one of the most important challenges in designing wireless sensor networks. One promising approach to conserving system energy is to keep only a minimal number of sensors active and put others into low-powered sleep mode, while the active sensors can maintain the communication connectivity and cover the target region completely. The problem of computing such minimal active sensor set is NP-hard. In this paper, a centralized Voronoi tessellation (CVT) based approximate algorithm is proposed to construct a near optimal cover set of active sensors required to cover the target region completely. The communication graph induced by the cover set computed by CVT algorithm is connected if sensor’s communication radius is at least twice of its sensing radius. In case of sensor’s communication radius is smaller than twice of its sensing radius, a minimum spanning tree (MST) based connection algorithm is proposed to ensure the communication connectivity of the cover set. Finally, the performance of the proposed algorithm is evaluated through theoretical analysis and extensive numerical experiments. Experimental results show that the proposed algorithm outperforms the greedy algorithm in terms of the runtime and the size of the constructed connected cover set.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利