Motivated by application to wireless sensor networks, we study the following problem. We are given a set  S of wireless sensor nodes, given as a set of points in the two-dimensional plane, and real numbers 0  r ≤  R . We must place a minimum-size set  Q of wireless relay nodes in the two dimensional plane to connect  S , where connectivity is explained formally next. The nodes of  S can communicate to nodes within distance  r , and the relay nodes of  Q can communicate within distance  R . Once the nodes of  Q are placed, they together with  S  induce an undirected graph  G = ( V , E ) defined as follows:  V =  S ?  Q , and $E = \{ uv | u,v \in Q \mbox{ and } ||u,v|| \leq R \} \cup \{ xu | x \in S \mbox{ and } u \in (Q \cup S) \mbox{ and } ||u,x|| \leq r\}$, where || u , v || denotes the Euclidean distance from  u to  v .  G must be connected.#R##N##R##N#It was shown in [1] that an algorithm based on Minimum Spanning Tree achieves approximation ratio 7. We improve the analysis of this algorithm to 6, and propose a post-processing heuristic called  Post-Order Greedy to practically improve the performance of the approximation algorithms. Experiments on random instances give Post-Order Greedy applied after Minimum Spanning Tree an average improvement of up to 23%. Applying Post-Order Greedy after an optimum Steiner Tree algorithm results in another circa 6% improvement considering the same instances.
['Gruia Călinescu', 'Sutep Tongngam']
Relay Nodes in Wireless Sensor Networks