基于均匀分簇的2-控制划分近似算法
DOI:
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

国家自然科学基金(60373012,10871119);山东省自然科学基金(ZR2009GM009,ZR2009AM013);山东省科技攻关计划(2009GG10001014);山东省高校科技计划(J10LG09)


Approximation Algorithm Based on Uniform Clustering for 2-Domatic Partition
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    在无线传感器网络中,为了均衡节点的能量消耗,达到延长网络寿命的目的,轮转控制节点的睡眠调度机制被提出来.控制划分问题是睡眠调度机制的一个抽象,该问题的实质是寻找多个不相交的控制集,通过轮转控制集进行能量有效的睡眠调度.研究解决了2-控制划分问题,基于均匀分簇的方法在单位圆盘图上提出一种具有常数近似比的2-控制划分近似算法DPUC(domatic partition by uniform clustering),其近似比为(δ+1)/4,其中δ为节点的最小度.DPUC算法可以在常数轮的时间内运行,并且可以扩展为k-DP近似算法.同时,该算法解决了Pemmaraju和Pirwani提出的开放问题,即在仅知道节点间连接信息的情况下,是否可以在常数轮的时间内得到一个k-DP近似算法.最后通过仿真验证了算法DPUC的正确性和可行性.

    Abstract:

    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.

    参考文献
    相似文献
    引证文献
引用本文

张庆波,禹继国,王光辉.基于均匀分簇的2-控制划分近似算法.软件学报,2011,22(zk1):165-174

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2011-05-02
  • 最后修改日期:2011-07-29
  • 录用日期:
  • 在线发布日期: 2012-01-02
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号