Delay Constrained Optimal Relay Placement for Planned Wireless Sensor Networks

Download Now Free registration required

Executive Summary

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.

  • Format: PDF
  • Size: 350.04 KB