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

  • Article
  • | |
  • Metrics
  • |
  • Reference [17]
  • |
  • Related [20]
  • | | |
  • 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
    [1] Yang J,Zhang DY,Zhang YY,Wang Y.Cluster-Based data aggregation and transmission protocol for wireless sensor networks. Journal of Software,2010,21(5):1127-1137(in Chinese with English abstract).http://www.jos.org.cn/1000-9825/3534.htm[doi: 10.3724/SP.J.1001.2010.03534]
    [2] Islam K,Akl SG,Meijer H.Maximizing the lifetime of a sensor network through domatic partition.In:Proc.of the 34th IEEE Conf.on Local Computer Networks(LCN).2009.
    [3] Cardei M,Maccallum D,Cheng X,Min M,Jia X,Li D,Du D.Wireless sensor networks with energy efficient organization.Journal of Interconnection Networks,2002,3:213-229.
    [4] Feige U,Halldorsson MM,Kortsarz G,Srinivasan A.Approximating the domatic number.SIAM Journal on Computing,2003, 32(1):172-195.
    [5] Moscibroda T,Wattenhofer R.Maximizing the lifetime of dominating sets.In:Kielmann T,Aubanel E,et al.,eds.Proc.of the 19th IEEE Int’l Parallel and Distributed Processing Symp.(IPDPS).2005.
    [6] Pemmaraju SV,Pirwani IA.Energy conservation via domatic partitions.In:Sergio P,Marco C,Raghupathy S,eds.Proc.of the 7th ACM Int’l Symp.on Mobile Ad Hoc Networking and Computing.New York:ACM,2006.143-154.
    [7] Pandit S,Pemmaraju SV,Varadarajan K.Approximation algorithms for domatic partitions of unit disk graphs.In:Irit D,Klaus J, Joseph N,Jose R,eds.Proc.of the 12th Int’l Workshop on Approximation Algorithms for Combinatorial Optimization Problems and the 13th Int’l Workshop on Randomization and Computation.Berlin:Springer-Verlag,2009.312-325.
    [8] Mahjoub D,Matula DW.Employing(1-ε)dominating set partitions as backbones in wireless sensor networks.In:Rajaraman R,et al.,eds.Proc.of Workshop on Algorithm Engineering and Experiments(ALENEX).San Francisco:SIAM,2010.98-111.
    [9] Mahjoub D,Matula DW.Building(1-ε)dominating sets partition as backbones in wireless sensor networks using distributed graph coloring.In:Rajmohan R,Thomas M,Adam D,Anna S,eds.Proc.of the 6th IEEE Int’l Conf.on Distributed Computing in Sensor Systems(DCOSS).Berlin:Springer-Verlag,2010.144-157.
    [10] Misra R,Mandal C.ClusterHead rotation via domatic partition in self-organizing sensor networks.In:Proc.of 2007 the 2nd Int’l Conf.on Communication System Software and Middleware.Bangalore:IEEE Computer Society,2007.1-7.
    [11] Misra R,Mandal C.Efficient clusterhead rotation via domatic partition in self-organizing sensor networks.Wireless Communications and Mobile Computing,2009,9(8):1040-1058.
    [12] Misra R,Mandal C.Rotation of CDS via connected domatic partition in ad hoc sensor networks.IEEE Trans.on Mobile Computing,2009,8(4):488-499.
    [13] Zelinka B.On k-domatic numbers of graphs.Czechoslovak Mathematical Journal,1983,33(2):309-311.
    [14] Zhou XL,Wu M,Xu JB.BPEC:An energy-aware distributed clustering algorithm in WSNs.Journal of Computer Research and Development,2009,46(5):723-730(in Chinese with English abstract).
    [15] Yu JG,Qi YY,Wang GH.An energy-driven unequal clustering protocol for heterogeneous wireless sensor networks.Journal of Control Theory and Applications,2011,9(1):133-139.
    [16] Liu M,Cao JN,Chen GH,Chen LJ,Wang XM,Gong HG.EADEEG:An energy-aware data gathering protocol for wireless sensor networks.Journal of Software,2007,18(5):1092-1109(in Chinese with English abstract).http://www.jos.org.cn/1000-9825/18/ 1092.htm[doi:10.1360/jos181092]
    [17] Cui XX,Fang HY,Zhu XL.Probabilistic character for localization problem in sensor networks.Journal of Computer Research and Development,2007,44(4):630-635(in Chinese with English abstract).
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

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

Copy
Share
Article Metrics
  • Abstract:3585
  • PDF: 5167
  • HTML: 0
  • Cited by: 0
History
  • Received:May 02,2011
  • Revised:July 29,2011
  • Online: January 02,2012
You are the first2032512Visitors
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