Distributed Construction of the Critical Geometric Graph in Dense Wireless Sensor Networks

Details Distributed Construction of the Critical Geometric Graph in Dense Wireless Sensor Networks Distributed Construction of the Critical Geometric Graph in Dense Wireless Sensor Networks

2010-11-15

arxiv.org/abs/1011.3482v1

Computer Science

Networking and Internet Architecture

20 pages, 11 figures

Scientific paper

Wireless sensor networks are often modeled in terms of a dense deployment of smart sensor nodes in a two-dimensional region. Give a node deployment, the \emph{critical geometric graph (CGG)} over these locations (i.e., the connected \emph{geometric graph (GG)} with the smallest radius) is a useful structure since it provides the most accurate proportionality between hop-count and Euclidean distance. Hence, it can be used for GPS-free node localisation as well as minimum distance packet forwarding. It is also known to be asymptotically optimal for network transport capacity and power efficiency. In this context, we propose DISCRIT, a distributed and asynchronous algorithm for obtaining an approximation of the CGG on the node locations. The algorithm does not require the knowledge of node locations or internode distances, nor does it require pair-wise RSSI (Received Signal Strength Indication) measurements to be made. Instead, the algorithm makes use of successful Hello receipt counts (obtained during a Hello-protocol-based neighbour discovery process) as edge weights, along with a simple distributed min-max computation algorithm. In this paper, we first provide the theory for justifying the use of the above edge weights. Then we provide extensive simulation results to demonstrate the efficacy of DISCRIT in obtaining an approximation of the CGG. Finally, we show how the CGG obtained from DISCRIT performs when used in certain network self-organisation algorithms.

Affiliated with

Also associated with

No associations

Rating

Distributed Construction of the Critical Geometric Graph in Dense 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 Distributed Construction of the Critical Geometric Graph in Dense Wireless Sensor Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distributed Construction of the Critical Geometric Graph in Dense Wireless Sensor Networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-299596