主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2019年第10期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
陆克中,孙宏元.无线传感器网络最小覆盖集的贪婪近似算法.软件学报,2010,21(10):2656-2665
无线传感器网络最小覆盖集的贪婪近似算法
Greedy Approximation Algorithm of Minimum Cover Set in Wireless Sensor Networks
投稿时间:2009-01-15  修订日期:2009-07-07
DOI:
中文关键词:  无线传感器网络  网络生命期  节点调度  最小覆盖集  贪婪算法  近似算法
英文关键词:wireless sensor network  network lifetime  nodes scheduling  minimum cover set  greedy algorithm  approximation algorithm
基金项目:Supported by the National Natural Science Foundation of China under Grant No.60602066 (国家自然科学基金); the Guangdong Provincial Natural Science Foundation of China under Grant No.2008254 (广东省自然科学基金); the Science and Technology Planning Project of Guangdong Province of China under Grant No.2006B36430001 (广东省科技计划项目)
作者单位
陆克中 深圳大学 计算机与软件学院,广东 深圳 518060 深圳大学 国家高性能计算中心深圳分中心,广东 深圳 518060 
孙宏元 深圳大学 ATR国防科技重点实验室,广东 深圳 518060 
摘要点击次数: 3424
全文下载次数: 3893
中文摘要:
      网络生命期是限制无线传感器网络发展的一个瓶颈.在保证网络监控性能的前提下,仅调度部分节点工作而让其余节点处于低功耗的休眠状态,可以有效节省能耗,延长网络生命期.节点调度的目标是寻找一个能够覆盖监控区域的最小节点集合,这是一个NP难问题,目前,其近似算法的性能较低.提出了一种基于贪婪法的最小覆盖集近似算法,在构造覆盖集的过程中,优先选择扩展面积最大的有效节点加入覆盖集.理论分析表明,该算法能够构造出较好的覆盖集,时间复杂度为O(n),其中,n为初始节点总数.实验数据表明,该算法的性能要优于现有算法,得到的覆盖集的平均大小比现有算法减小了14.2%左右,且执行时间要短于现有算法.当初始节点分布较密时,该算法得到的平均覆盖度小于1.75,近似比小于1.45.
英文摘要:
      Network lifetime is a bottleneck that restricts the development of wireless sensor networks. One approach to save energy effectively and prolong network lifetime is to schedule some nodes to work and put other nodes into a low-powered sleep mode, while monitoring performance of network. The object of scheduling nodes is to obtain a minimum node set that can cover a monitored region. This is a NP-hard problem. Performances of present approximation algorithms have not been good. An approximation algorithm of a minimum cover set problem based on methodology is proposed. During the process of constructing a cover set, effective node that extends to maximal areas are selected to join the cover set. Theoretical analyses show that the algorithm can construct a cover set that perform well and has a time complexity that is O(n), where n is initial node number. Experimental results show that performance of this new algorithm outperform that of present algorithms. The size of a cover set is decreased by 14.2%. Also, execution time is less than that of present algorithms. When initial nodes are deployed densely, the average degree of coverage obtained by the algorithm is below 1.75 and has an approximation ratio below 1.45.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

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