文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 工程科技 > 信息与通信 > 无线传感器网络最小连通覆盖集问题求解算法
侵权投诉

无线传感器网络最小连通覆盖集问题求解算法

ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn

Journal of Software, Vol.17, No.2, February 2006, pp.175 184 doc.guandang.net DOI: 10.1360/jos170175 Tel/Fax: +86-10-62562563 © 2006 by Journal of Software. All rights reserved.

无线传感器网络最小连通覆盖集问题求解算法

蒋 杰1+, 方 力2, 张鹤颖1, 窦文华1

12

(国防科学技术大学 计算机学院,湖南 长沙 410073) (国防科学技术大学 网络信息中心,湖南 长沙 410073)

An Algorithm for Minimal Connected Cover Set Problem in Wireless Sensor Networks

JIANG Jie1+, FANG Li2, ZHANG He-Ying1, DOU Wen-Hua1

12

(School of Computer, National University of Defense Technology, Changsha 410073, China) (Network Information Center, National University of Defense Technology, Changsha 410073, China)

+ Corresponding author: Phn: +86-731-4575830, Fax: +86-731-4575830, E-mail: jiangjie@nudt.edu.cn, doc.guandang.net

Jiang J, Fang L, Zhang HY, Dou WH. An algorithm for minimal connected cover set problem in wireless sensor networks. Journal of Software, 2006,17(2):175 184. doc.guandang.net 1000-9825/17/175.htm Abstract: 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. Key words:

WSN (wireless sensor network); network lifetime; MCCS (minimal connected cover set); Voronoi tessellation; MIS (maximal independent set); MST (minimum spanning tree)

摘 要: 降低能耗以延长网络生存时间是无线传感器网络设计中的一个重要挑战.在传感器节点高密度部署的环境中,在保证网络性能的前提下,仅将最少量的节点投入活跃工作状态,而将其余节点投入低功耗的睡眠状态,是一种节约系统能量的有效方法.如何计算同时满足“覆盖要求”(工作节点必须能够完全覆盖目标区域)和“连通性要求”(工作节点组成的通信网络必须是连通的)的最小节点集合,是一个NP难问题.设计了一种基于目标区域Voronoi划分的集中式近似算法(centralized Voronoi tessellation,简称CVT),用于计算完全覆盖目标区域所需要的近似最小 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))

Received 2005-03-10; Accepted 2005-08-03

第1页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email