Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Keyword
Articles 1 - 3 of 3
Full-Text Articles in Physical Sciences and Mathematics
Randomized Algorithms For Approximating A Connected Dominating Set In Wireless Sensor Networks, Akshaye Dhawan, Michelle Tanco, Aaron Yeiser
Randomized Algorithms For Approximating A Connected Dominating Set In Wireless Sensor Networks, Akshaye Dhawan, Michelle Tanco, Aaron Yeiser
Mathematics and Computer Science Faculty Publications
A Connected Dominating Set (CDS) of a graph representing a Wireless Sensor Network can be used as a virtual backbone for routing through the network. Since the sensors in the network are constrained by limited battery life, we desire a minimal CDS for the network, a known NP-hard problem. In this paper we present three randomized algorithms for constructing a CDS. We evaluate our algorithms using simulations and compare them to the two-hop K2 algorithm and two other greedy algorithms from the literature. After pruning, the randomized algorithms construct a CDS that are generally equivalent in size to those constructed …
A Distributed Greedy Algorithm For Constructing Connected Dominating Sets In Wireless Sensor Networks, Akshaye Dhawan, Nicholas A. Scoville, Michelle Tanco
A Distributed Greedy Algorithm For Constructing Connected Dominating Sets In Wireless Sensor Networks, Akshaye Dhawan, Nicholas A. Scoville, Michelle Tanco
Mathematics and Computer Science Faculty Publications
A Connected Dominating Set (CDS) of the graph representing a Wireless Sensor Network can be used as a virtual backbone for routing in the network. Since sensor nodes are constrained by limited on-board batteries, it is desirable to have a small CDS for the network. However, constructing a minimum size CDS has been shown to be a NP-hard problem. In this paper we present a distributed greedy algorithm for constructing a CDS that we call Greedy Connect. Our algorithm operates in two phases, first constructing a dominating set and then connecting the nodes in this set. We evaluate our algorithm …
Fault-Tolerant Coverage In Dense Wireless Sensor Networks, Akshaye Dhawan, Magdalena Parks
Fault-Tolerant Coverage In Dense Wireless Sensor Networks, Akshaye Dhawan, Magdalena Parks
Mathematics and Computer Science Faculty Publications
In this paper, we present methods to detect and recover from sensor failure in dense wireless sensor networks. In order to extend the lifetime of a sensor network while maintaining coverage, a minimal subset of the deployed sensors are kept active while the other sensors can enter a low power sleep state. Several distributed algorithms for coverage have been proposed in the literature. Faults are of particular concern in coverage algorithms since sensors go into a sleep state in order to conserve battery until woken up by active sensors. If these active sensors were to fail, this could lead to …