Minimum Connected R-Hop k-Dominating Set in Wireless Networks
Minimum Connected R-Hop k-Dominating Set in Wireless Networks
复制标题
DOI：
10.1142/s1793830909000087
复制
发表时间：
2009-03
期刊：
影响因子：
--
通讯作者：
Deying Li;Lin Liu;Huiqiang Yang
中科院分区：
文献类型：
--
作者：
Deying Li;Lin Liu;Huiqiang Yang
在本文中，我们研究无线网络中的连通 r 跳 k 支配集问题。我们针对该问题提出了两种算法。我们证明 UDG 的算法 I 对于 k ≤ (2r + 1)2 具有 (2r + 1)3 近似比率，对于 k > (2r + 1)2 具有 (2r + 1)((2r + 1)2 + 1)-近似比率。算法 II 对于任何无向图都有 (2r + 1)ln(Δr) 近似比，其中 Δr 是网络中所有 r 跳邻域中最大的基数。仿真结果表明我们的算法是有效的。
In this paper, we study the connected r-hop k-dominating set problem in wireless networks. We propose two algorithms for the problem. We prove that algorithm I for UDG has (2r + 1)3 approximate ratio for k ≤ (2r + 1)2 and (2r + 1)((2r + 1)2 + 1)-approximate ratio for k > (2r + 1)2. And algorithm II for any undirected graph has (2r + 1)ln(Δr) approximation ratio, where Δr is the largest cardinality among all r-hop neighborhoods in the network. The simulation results show that our algorithms are efficient.