QoS Aware and Survivable Network Design for Planned Wireless Sensor Networks

Details QoS Aware and Survivable Network Design for Planned Wireless Sensor Networks QoS Aware and Survivable Network Design for Planned Wireless Sensor Networks

2011-10-21

arxiv.org/abs/1110.4746v2

Computer Science

Networking and Internet Architecture

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

QoS Aware and Survivable Network Design for Planned Wireless Sensor Networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with QoS Aware and Survivable Network Design for Planned Wireless Sensor Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and QoS Aware and Survivable Network Design for Planned Wireless Sensor Networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-85088