Distributed Planarization and Local Routing Strategies in Sensor Networks

Details Distributed Planarization and Local Routing Strategies in Sensor Networks Distributed Planarization and Local Routing Strategies in Sensor Networks

2011-07-26

arxiv.org/abs/1107.5154v1

Computer Science

Networking and Internet Architecture

Scientific paper

We present an algorithm which computes a planar 2-spanner from an Unit Disk Graph when the node density is sufficient. The communication complexity in terms of number of node's identifier sent by the algorithm is $6n$, while the computational complexity is $O(n\Delta)$, with $\Delta$ the maximum degree of the communication graph. Furthermore, we present a simple and efficient routing algorithm dedicated to the computed graph. Last but not least, using traditional Euclidean coordinates, our algorithm needs the broadcast of as few as $3n$ node's identifiers. Under the hypothesis of sufficient node density, no broadcast at all is needed, reducing the previous best known complexity of an algorithm to compute a planar spanner of an Unit Disk Graph which was of $5n$ broadcasts.

Affiliated with

Also associated with

No associations

Rating

Distributed Planarization and Local Routing Strategies in 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 Distributed Planarization and Local Routing Strategies in Sensor Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distributed Planarization and Local Routing Strategies in Sensor Networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-93298