基于均匀分簇的2-控制划分近似算法

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