We consider a navigation problem in a distributed, self-organized and coordinate-free Wireless Sensor and Ac-
tuator Network (WSAN). We rst present navigation algorithms that are veried using simulation results. Con-
sidering more than one destination and multiple mobile Unmanned Ground Vehicles (UGVs), we introduce a
distributed solution to the Multi-UGV, Multi-Destination navigation problem. The objective of the solution to
this problem is to eciently allocate UGVs to dierent destinations and carry out navigation in the network en-
vironment that minimizes total travel distance. The main contribution of this paper is to develop a solution that
does not attempt to localize either the UGVs or the sensor and actuator nodes. Other than some connectivity as-
sumptions about the communication graph, we consider that no prior information about the WSAN is available.
The solution presented here is distributed, and the UGV navigation is solely based on feedback from neigh-
boring sensor and actuator nodes. One special case discussed in the paper, the Single-UGV, Multi-Destination
navigation problem, is essentially equivalent to the well-known and dicult Traveling Salesman Problem (TSP).
Simulation results are presented that illustrate the navigation distance traveled through the network.
We also introduce an experimental testbed for the realization of coordinate-free and localization-free UGV
navigation. We use the Cricket platform as the sensor and actuator network and a Pioneer 3-DX robot as the
UGV. The experiments illustrate the UGV navigation in a coordinate-free WSAN environment where the UGV
successfully arrives at the assigned destinations.
Detection and patching of coverage holes in Wireless Sensor Networks (WSNs) are important measures of Quality of
Service (QoS) for security and other applications that emphasize sensor network coverage. In this paper, we model a
WSN using simplicial complexes based on its communication graph by which the network can be represented as
connections of sensor nodes without knowing exact locations of nodes. Thus, the coverage problem is converted to a
connectivity problem under some assumptions presented in the paper. We discuss two major topics in this paper, namely
sensor network coverage hole detection and patching. We present a novel, decentralized, coordinate-free, node-based
coverage hole detection algorithm. The algorithm can be implemented on a single node with connectivity information
gathered from one-hop away neighbors. Thus, the coverage hole detection algorithm can be run on individual nodes and
does not require time-consuming, centralized data processing. The hole-patching algorithm is based on the concept of
perpendicular bisector line. Every hole-boundary edge has a corresponding perpendicular bisector and new sensor nodes
are deployed on hole-boundary bisectors. Deployment of new sensor nodes maintains network connectivity, while
reduces coverage holes.
Access to the requested content is limited to institutions that have purchased or subscribe to SPIE eBooks.
You are receiving this notice because your organization may not have SPIE eBooks access.*
*Shibboleth/Open Athens users─please
sign in
to access your institution's subscriptions.
To obtain this item, you may purchase the complete book in print or electronic format on
SPIE.org.
INSTITUTIONAL Select your institution to access the SPIE Digital Library.
PERSONAL Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.