  We study the problem of wireless sensor network design by deploying a minimum
number of additional relay nodes (to minimize network 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, while
meeting a certain specified hop count bound (the hop count bound is chosen to
ensure a pre-determined probability of the data being delivered to the BS
within a given maximum delay). We study two variations of the problem.
  First we sudy the problem of guaranteed QoS connected network design, where
the objective is to have at least one path from each source to the BS with the
specified hop count bound. We show that the problem is NP-Hard. For a problem
in which the number of existing sensor nodes and potential relay locations is
n, we propose an O(n) approximation algorithm of polynomial time complexity.
Results show that the algorithm performs efficiently (in over 90% of the tested
scenarios, it gave solutions that were either optimal or were worse than
optimal by just one relay) in various randomly generated network scenarios.
  Next, we study the problem of survivable network design with guaranteed QoS,
i.e, the requirement is to have at least k > 1 node disjoint hop constrained
paths from each source to the BS. We show that the problem is NP-Hard. We also
show that the problem of finding a feasible solution to this optimization
problem is NP-Complete. We propose two polynomial time heuristics for this
problem, and compare their performance on various randomly generated network
scenarios.
