主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2019年第10期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
张庆波,禹继国,王光辉.基于均匀分簇的2-控制划分近似算法.软件学报,2011,22(zk1):165-174
基于均匀分簇的2-控制划分近似算法
Approximation Algorithm Based on Uniform Clustering for 2-Domatic Partition
投稿时间:2011-05-02  修订日期:2011-07-29
DOI:
中文关键词:  无线传感器网络  单位圆盘图  均匀分簇  均匀划分  2-控制划分  控制划分数
英文关键词:wireless sensor network  unit disk graph  uniform clustering  uniform partition  2-domatic partition (2-DP)  domatic number
基金项目:国家自然科学基金(60373012,10871119);山东省自然科学基金(ZR2009GM009,ZR2009AM013);山东省科技攻关计划(2009GG10001014);山东省高校科技计划(J10LG09)
作者单位E-mail
张庆波 曲阜师范大学 计算机科学学院, 山东 日照 276826  
禹继国 曲阜师范大学 计算机科学学院, 山东 日照 276826
智能控制技术山东省重点实验室, 山东 日照 276826 
jiguoyu@sina.com 
王光辉 山东大学 数学学院, 山东 济南 250100  
摘要点击次数: 2480
全文下载次数: 2432
中文摘要:
      在无线传感器网络中,为了均衡节点的能量消耗,达到延长网络寿命的目的,轮转控制节点的睡眠调度机制被提出来.控制划分问题是睡眠调度机制的一个抽象,该问题的实质是寻找多个不相交的控制集,通过轮转控制集进行能量有效的睡眠调度.研究解决了2-控制划分问题,基于均匀分簇的方法在单位圆盘图上提出一种具有常数近似比的2-控制划分近似算法DPUC(domatic partition by uniform clustering),其近似比为(δ+1)/4,其中δ为节点的最小度.DPUC算法可以在常数轮的时间内运行,并且可以扩展为k-DP近似算法.同时,该算法解决了Pemmaraju和Pirwani提出的开放问题,即在仅知道节点间连接信息的情况下,是否可以在常数轮的时间内得到一个k-DP近似算法.最后通过仿真验证了算法DPUC的正确性和可行性.
英文摘要:
      To balance the energy consumption of nodes and maximize the lifetime of wireless sensor networks,a sleeping schedule mechanism which rotates the dominators is proposed.One abstraction considered for the sleeping schedule is the domatic partition problem,whose essence is to find some disjoint dominating sets and to achieve an energy efficient sleeping schedule by rotating them.This paper solves the 2-domatic partition problem.Based on uniform clustering,a constant-factor approximation algorithm DPUC(domatic partition by uniform clustering)is proposed for 2-domatic partition with the approximate radio of (δ+1)/4,where δ is the minimum degree of nodes. The algorithm runs in a constant-rounds time and can be extended into a k-DP approximation algorithm.Meanwhile, the algorithm solves one open problem proposed by Pemmaraju and Pirwani.That is,whether a k-DP algorithm can run in a constant-rounds time using connectivity information only.Finally,the simulations demonstrate the correctness and feasibility of the DPUC algorithm.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

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