| 摘要: |
| 在无线传感器网络中,为了均衡节点的能量消耗,达到延长网络寿命的目的,轮转控制节点的睡眠调度机制被提出来.控制划分问题是睡眠调度机制的一个抽象,该问题的实质是寻找多个不相交的控制集,通过轮转控制集进行能量有效的睡眠调度.研究解决了2-控制划分问题,基于均匀分簇的方法在单位圆盘图上提出一种具有常数近似比的2-控制划分近似算法DPUC(domatic partition by uniform clustering),其近似比为(δ+1)/4,其中δ为节点的最小度.DPUC算法可以在常数轮的时间内运行,并且可以扩展为k-DP近似算法.同时,该算法解决了Pemmaraju和Pirwani提出的开放问题,即在仅知道节点间连接信息的情况下,是否可以在常数轮的时间内得到一个k-DP近似算法.最后通过仿真验证了算法DPUC的正确性和可行性. |
| 关键词: 无线传感器网络 单位圆盘图 均匀分簇 均匀划分 2-控制划分 控制划分数 |
| DOI： |
| 分类号: |
| 基金项目:国家自然科学基金(60373012,10871119);山东省自然科学基金(ZR2009GM009,ZR2009AM013);山东省科技攻关计划(2009GG10001014);山东省高校科技计划(J10LG09) |
|
| Approximation Algorithm Based on Uniform Clustering for 2-Domatic Partition |
|
ZHANG Qing-Bo1, YU Ji-Guo1,2, WANG Guang-Hui3
|
|
1.School of Computer Science, Qufu Normal University, Rizhao 276826, China;2.Key Laboratory of Intelligent Control Technology of Shandong Province, Rizhao 276826, China;3.School of Mathematics, Shandong University, Ji’nan 250100, China
|
| 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. |
| Key words: wireless sensor network unit disk graph uniform clustering uniform partition 2-domatic partition (2-DP) domatic number |
