An improved centralized algorithm for distance-preserving dominating sets in heterogeneous wireless sensor networks
Attakorn Putwattana, Jittat Fakcharoenphol · 2016
This paper studies a dominating set problem in heterogeneous wireless sensor networks, motivated by routing backbone design. In this problem, the goal is to find a bidirectional dominating set that preserves the hop distance up to a factor of α. In recent work of Liu, Huang, Du and Jia (INFOCOM'16), they presented centralized and distributed algorithms for finding the solution to the problem when α ≥ 5 that uses at most 3/2 (8ρ+1)2(2ρ+1)2·opt node, where ρ is the ratio between the maximum and the minimum transmission ranges and opt is the size of the optimal bidirectional dominating set. This paper presents a simple observation that can be applied to both centralized and distributed algorithms of Liu et al so that they use only 2(6ρ+1)2(2ρ+1)2·opt nodes (at least 19% improvements). We also employ more aggressive heuristic to choose nodes into the dominating set in the centralized setting. Experimentally, this centralized algorithm improves over the previous algorithm of Liu et al approximately by 43.7%-52.0% (for dense instances) to 21.1%-38.1% (for sparse instances). Two key observations are the reasons for the improvements. First, to create connected dominating sets, the modified algorithm joins nodes one hop closer than the original algorithm. This first observation has theoretical justification and can be applied directly to both centralized and distributed algorithms of Liu et al to obtain some performance improvement. Secondly, by employing a more aggressive strategy when choosing nodes to include in the dominating set, the number of nodes used can be decreased. We provide only the centralized implementation of the second observation.