Optimal Relay Placement for Indoor Sensor Networks

To many sensor networks, the robust operation depends on deploying relays to ensure wireless coverage. This paper considers the crucial problem of optimal relay placement for wireless sensor networks in indoor environments. The placement of relays is essential for ensuring communication quality and data collection. A number of existing algorithms have been proposed for ensuring full sensing coverage and network connectivity. These algorithms can hardly be applied to indoor environments because of the complexity of indoor environments, in which a radio signal can be dramatically degraded by obstacles like walls. We firstly theoretically prove that the indoor relay placement problem is NP-hard. We then predict radio coverage of a given relay deployment in indoor environments, and then propose a efficient greedy algorithm for computing the relay deployment locations for required coverage quality. This algorithm is proved to provide a H_n factor approximation to the theoretical optimum, where H_n = 1 + 1/2 + ⋯ + 1/n = ln(n) + 1, and n is the number of all grid points. Experimental results demonstrate the proposed algorithm achieves better performance than two other algorithms. To our knowledge, our work is the very first that study the optimal relay placement problem for sensor networks in complex indoor environments.