Delay Constrained Optimal Relay Placement for Planned Wireless Sensor Networks
Source: Indian Institute of Science
In this paper, the authors study the problem of wireless sensor network design by deploying a minimum number of additional relay nodes (to minimize network design cost) at a subset of given potential relay locations in order to convey the data from already existing sensor nodes (hereafter called source nodes) to a Base Station within a certain specified mean delay bound. They formulate this problem in two different ways, and show that the problem is NP-Hard. For a problem in which the number of existing sensor nodes and potential relay locations is n, they propose an O(n) approximation algorithm of polynomial time complexity.