Document Type

Article

Publication Date

2014

College/Unit

Statler College of Engineering and Mining Resources

Department/Program/Center

Lane Department of Computer Science and Electrical Engineering

Abstract

We present a distributed algorithm for creation of geometric spanners in a wireless sensor network. Given any connected network, we show that the algorithm terminates in O(1)" role="presentation" style="display: inline; line-height: normal; font-size: 16px; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px 2px 0px 0px; margin: 0px; position: relative;">𝑂(1)O(1) time, irrespective of network size. Our algorithm uses an underlying clustering algorithm as a foundation for creating spanners and only relies on the periodic heartbeat messages associated with cluster maintenance for the creation of the spanners. The algorithm is also shown to stabilize locally in the presence of node additions and deletions. The performance of our algorithm is verified using large scale simulations. The average path length ratio for routing along the spanner for large networks is shown to be less than 2.

Source Citation

Ranganath, G., & Kulathumani, V. (2014). FLOC-SPANNER: An O(1) Time, Locally Self-Stabilizing Algorithm for Geometric Spanner Construction in a Wireless Sensor Network. International Journal of Distributed Sensor Networks, 10(2), 923751. https://doi.org/10.1155/2014/923751

Share

COinS
 
 

To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.