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

Clc Number:

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    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.

    Reference
    Related
    Cited by
Get Citation

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

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:May 02,2011
  • Revised:July 29,2011
  • Adopted:
  • Online: January 02,2012
  • Published:
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063