Autonomous Deployment and Repair of a Sensor Network using an ...
To Appear in IEEE International Conference on Robotics and Automation (ICRA),
New Orleans, USA, 2004
Autonomous Deployment and Repair of a Sensor
Network using an Unmanned Aerial Vehicle
P. Corke∗ , S. Hrabar‡ R. Peterson† , D. Rus†§ , S. Saripalli‡ and G. Sukhatme‡ ,
∗ CSIRO Manufacturing & Infrastructure Technology, Queensland, Australia
† Department of Computer Science, Dartmouth College, Hanover, New Hampshire, USA
§ Computer Science and Artiﬁcial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA, USA
‡ Center for Robotics and Embedded Systems, University of Southern California, Los Angeles, California, USA
Abstract— We describe a sensor network deployment method
using autonomous ﬂying robots. Such networks are suitable
for tasks such as large-scale environmental monitoring or for
command and control in emergency situations. We describe in
detail the algorithms used for deployment and for measuring
network connectivity and provide experimental data we collected
from ﬁeld trials. A particular focus is on determining gaps in
connectivity of the deployed network and generating a plan for a
second, repair, pass to complete the connectivity. This project is
the result of a collaboration between three robotics labs (CSIRO,
USC, and Dartmouth.)
I. I NTRODUCTION
We investigate the role of mobility in sensor networks.
Mobility can be used to deploy sensor networks, to maintain
and repair connectivity, and to enable applications such as Fig. 1. AVATAR Autonomous Helicopter
monitoring and surveillance. We examine sensor networks
that consist of static and dynamic nodes. The static sensor
nodes are “Motes” and the mobile nodes are autonomous node, which is incorporated into the existing network. This
helicopters. Integrating static nodes with mobile robots en- approach to autonomous deployment of sensor networks will
hances the capabilities of both types of devices and enables allow the on-demand instrumentation of remote environments
new applications. Using networking, the sensors can provide that may be inaccessible by ground methods, and supporting
the Unmanned Aerial Vehicle (UAV) with information which applications to navigation, monitoring, and search and rescue.
is out of the range of the robot. Using mobility, the robot We have implemented the deployment algorithms on a
can deploy the network, localize the nodes in the network, hardware platform that integrates hardware and software from
maintain connectivity by introducing new nodes as needed, three labs: USC’s helicopter, Dartmouth’s sensor network,
and and act as “data mules” to relay information between and CSIRO’s interface between a helicopter and a sensor
disconnected wireless clouds. network. The three groups conducted joint experiments which
We combine ad-hoc networking, sensing, and control to demonstrate, for a desired network topology, (1) autonomous
deploy and use a sensor network. We use an autonomous heli- sensor network deployment with a helicopter, (2) ground to
copter to deploy a sensor network with a controlled topology, ground and ground to air connectivity measurements for the
for example a star, grid, or random. The helicopter deploys resulting network and (3) uses the results to repair the network
the sensors one at a time at designated locations. Once on the connectivity when the deployed topology does not match the
ground, the sensors establish an ad-hoc network and compute desired topology.
their connectivity map in a localized and distributed way.
The helicopter is equipped with a sensor node so that it is II. R ELATED W ORK
a mobile component of the sensor network and it can com- Our work builds on important previous work in sensor
municate to the ground. This system can handle on-demand networks and robotics, and bridges the two communities by
node deployment. The connectivity map is used to determine integrating autonomous control of ﬂying vehicles with multi-
ground locations that require additional nodes (for example to hop message routing in ad-hoc networks.
repair connectivity or to increase bandwidth). The helicopter Autonomous aerial vehicles have been an active area of
responds by ﬂying to that location and deploying a new research for several years. Autonomous model helicopters
have been used as testbeds to investigate problems ranging
from control, navigation, path planning to object tracking
and following. Flying robot control is a very challenging
problem and our work here builds on successes with hovering
for two autonomous helicopters , . Several other teams
are working on autonomous control of helicopters. A good
overview of the various types of vehicles and the algorithms
used for control of these vehicles can be found in  . Recent
work has included Autonomous Landing ,  Aggressive
maneuvering of AFV’s  and pursuit-evasion games .
Research in sensor networks has been very active in the
recent past. An excellent general introduction on sensor net-
works can be found in . An overview of hardware and
software requirements for sensor networks can be found in
 who describe the Berkeley Mica Motes. Algorithmic work
for positioning a sensor network where sensors have mobility
and can self-propel includes even dispersal of sensors from Fig. 2. Deployment Mechanism on the Helicopter
a source point and redeployment for network rebuilding ,
. Other important contributions include –.
In our previous work on networked robots we used ﬂying each point and later in the paper explain the mechanism used
helicopters to localize a deployed sensor network , we to accomplish this.
computed and represented paths in sensor networks that could
guide the motion of a mobile node such as a helicopter , Algorithm 1 Algorithm for controlling an autonomous heli-
, and we used sensor network mobility to cover a given copter to deploy a sensor network.
area while maintaining connectivity . Input: desired network topology
Initialization: Embed topology in the plane at the desired
III. D EPLOYMENT C ONTROL
scale and extract waypoints.
Our approach to deployment consists of three phases. In Sort waypoints into buckets by their x coordinate.
the ﬁrst phase, an initial network deployment is executed. for each x bucket do
In the second phase, we measure the connection topology Sort waypoints by y.
of the deployed network and compare that to the desired while more sensors in the deployment mechanism do
topology. If they match, the procedure is complete. Otherwise go to next way-point
the measured connectivity graph is used to compute new hover
deployment locations that will repair the desired topology. The deploy sensor
last two phases can be run at any point in time to detect
the potential failure of sensor nodes and ensure sustained
connectivity. The same approach can also be used to increase B. Connectivity Measurement Algorithm
the sensor density in an area. A Mote sensor that has been specially modiﬁed to add phys-
ical user interface controls (a potentiometer and switch) is used
A. Deployment Algorithm to control and conﬁgure the sensor side of the connectivity
Our goal is to develop control algorithms that allow a ﬂying tests as shown in Algorithm 2. The controls are set for the
robot to deploy a sensor network with a speciﬁed communi- number of ping iterations and whether the sensors should reply
cation topology. Given a speciﬁed network topology, and a to pings or not and then a multi-hop message is broadcast to
deployment scale, we embed the topology in the plane and the sensors to start an experiment. A reset message can also
extract desired node locations from the resulting embedding. be sent to reset the sensor to an initial state. Data collected
Network topology is represented as a graph whose edges during the experiment is later read from the sensors via a
correspond to sensors. Edges connect sensors who are within laptop basestation that sends a download command and reads
communication range of each other (with two-way commu- the data via RF messages.
nication between the nodes.) Embedding such a topology in
the plane reduces to computing actual GPSs coordinates for C. Connectivity Repair Algorithm
the sensors to be deployed. The scale of the embedding is Our general repair algorithm has the following structure.
determined by the inter-node communication range. We then The connectivity algorithm results in a connectivity graph.
sort and convert the resulting points to waypoints in a way We can compare this graph against the desired topology
that optimizes the robot’s required trajectory for covering the embedding using graph isomorphism algorithms , . If
points. We assume the robot can hover and deploy a node at the two graphs are isomorphic we are done. If they are not
Algorithm 2 Algorithm for controlling the mote side of a Algorithm 3 Distributed algorithm for identifying the con-
connectivity experiment. nected components in a sensor network. All the nodes in one
Wait for experiment conﬁguration/start message connected component will have the same component value as
Initialization: Set conﬁguration mode = air-to-ground, a result of this protocol.
ground-to-ground, or ground-to-air. Set count = number of for each node in the sensor network do
ping iterations. component = id
Send a multi-hop forwarding of start message to other for each node in the sensor network do
motes. broadcast node id.
while listen for newid broadcasts do
for i=1 to count do if received id > component then
if mode = ground-to-ground OR mode = ground-to-air component = newid
then broadcast newid
broadcast a ping message. Helicopter collects all component values
Sleep a random interval Helicopter determines unique component values as the
number of connected components.
while Listen for messages do
if message is a ping then IV. E XPERIMENTS
if mode = air-to-ground OR mode = ground-to-ground
then We have implemented the algorithms for deployment and
reply to ping. network connectivity using a sensor network with 50 nodes
else if Message is a ping reply. then and an autonomous ﬂying robot.
tabulate reply. Our experiments targetted the three main control tasks: (1)
deployment; (2) connectivity measurements; and (3) repair.
Termination: broadcast counts of replies per mote ID in We executed each of these tasks in manual mode (where the
response to download message. helicopter was controled by a pilot) and in autonomous mode
(where the helicopter operated fully autonomously once in the
air.) In this section we describe our testbed and present some
of the data collected from these different sets of experiments.
A. The Helicopter
their difference can be computed using subgraph embeddings.
This step results in a list of missing graph nodes and their Our experimental testbed, the AVATAR (Autonomous Ve-
coordinates, which can be represented as a set of waypoints. hicle for Aerial Tracking And Reconnaissance)  is a gas-
These are given as input to Algorithm 1. powered radio-controlled model helicopter ﬁtted with a PC-
104 stack augmented with sensors (Figure 1). A Novatel RT-2
In our implementation we have used a simpliﬁed version DGPS system provides position data with a 2 cm CEP, Cross-
of this procedure. We wish to deploy sensor networks whose bow VGX 6-axis IMU unit provides rate information to the
connectivity graph is one connected component. Therefore the onboard computer where it is fused using a 16-state Kalman
task of the connectivity repair algorithm is to determine the ﬁlter. The ground station is a laptop that is used to send high-
number of connected components in the deployed network. level control commands and differential GPS corrections to the
Algorithm 3 shows the protocol for determining the number helicopter. Communication with the ground station is carried
of connected components. The sensors broadcast their ids via 2.4 GHz wireless Ethernet. Autonomous ﬂight is achieved
and forward the ids they hear. Each sensor keeps the largest using a behavior-based control architecture .
value it hears. The number of distinct values is the number of
connected components in the graph. The helicopter can collect B. The Sensor Network
this information and determine how many components there Our sensor network platform is the Berkeley Mica Mote .
are. If the network has at least two connected components The Mote hardware conﬁguration includes a main processor
we compute the separation region and determine how to board with a microcontroller that handles data processing
cover it with waypoints in a way that connects the two tasks, A/D conversion of sensor output, state indication via
components. In the simplest algorithm we compute the line LED’s, serial I/O, and control of a low-power radio transceiver.
segment between the two closest nodes in the disconnected It consists of an Atmel ATMega128 microcontroller (with 4
components and determine waypoints along that line using MHz 8 bit CPU, 128KB ﬂash program space, 4K RAM, 4K
the sensor communication range. A different approach is to EEPROM), a 916 MHz RF transceiver (50Kbits/sec, 100ft
compute the region of separation between the two connected range), a UART, an Atmel AT90LS2343 coprocessor, and a
components and randomly pick waypoints in that region. 4Mbit serial ﬂash memory. The radio communication consists
of an RF Monolithics 916.50 MHz transceiver (TR1000), an-
tenna, and some components to adjust the physical layer char-
acteristics such as broadcast power and transmission rate. An Sensor
auxiliary sensor board contains light, sound, and temperature (Vision/GPS)
sensors with space for adding other types of sensors. Sensor
boards can be stacked for additional sensor functionality. A
Mote runs for approximately one month on two AA batteries. If position within
The operating system support for the Motes is provided by Position and
TinyOS, an event-based operating system. Our testbed consists Object
of 50 Mote sensors deployed in the form of a regular 7×7 grid,
see Figure 3. An extra Mote sensor is ﬁtted to the helicopter Deploy
using a system developed by CSIRO, see Section IV-D.
Low Level Controller
Fig. 4. Deployment architecture
controller, it tasks the helicopter to deploy an object or sensor
at that location. This division of controllers ensures that the
autonomous control of helicopter is completely decoupled
from the task at hand. Hence if a new sensor (e.g. vision)
was used for deployment instead of GPS, only the higher level
controller needs to be changed.
Fig. 3. Helicopter Deploying Sensors in a 7 × 7 grid
D. The Helicopter-Sensor Network Interface
The helicopter carries one Mote to allow communications
C. The Deployment Mechanism with the deployed sensor network. The Mote is plugged onto a
programming and serial interface board which is serially con-
The deployment mechanism consists of a radio con-
nected to the helicopter’s linux computer. Several applications
troller(RC) servo which rotates a wire coil. The sensors to be
were run, depending on the experiment. The ping application
deployed are attached to the loops on the coil at even intervals,
sends a broadcast message with a unique id once per second
and are dropped off the coil one at a time when it has rotated
and logs all replies along with the associated Mote identiﬁer.
the speciﬁed number of rotations. A toggle switch is used to
This data allows us to measure air-ground connectivity, and
count the number of rotations. In this way we can accurately
results are presented in IV-G. The gps application receives
time and drop sensors at the given GPS location, see Figure 2.
GPS coordinates via a socket from the helicopter navigation
The architecture for deployment consists of a two stage
software and broadcasts it. Simple algorithms in each Mote
controller (see Figure 4). The higher level controller depends
are able to use these position messages to reﬁne an estimate
on the sensor modality being used (either GPS or vision).
of their location .
For GPS based deployment, the controller obtains the current
position of the helicopter from GPS and continually checks E. Experimental Procedure
whether it is sufﬁciently close to a drop location, if it is then a Our ﬁeld experiments have been performed on a grass ﬁeld
deploy command is sent to the low-level controller. For vision on the USC campus. We marked a 7 × 7 grid on the ground
based control a Kalman ﬁlter continually updates the estimate with ﬂags. We used an empirical method to determine the
of the object and if the estimate is within the required error a spacing of the grid. We established that on that ground, the
deploy command is sent to the low-level controller. Mote transmission range was 2.5 meters1 . We selected the grid
The primary function of the low-level controller is to keep
1 This communication range is much lower than the expected range for
the helicopter in hover and also to navigate the helicopter
Motes. We believe the reduced range is due to the close proximity of the
to the desired way-points. Once this controller receives a ground which absorbs a signiﬁcant amount of RF energy, particularly when
command for deployment from the higher level deployment moist.
spacing at 2 meters so that we would guarantee communication
between any neighbors in the ﬁeld.
16 37 36
200 13 18 41 4
number of responses
3 10 40 3
0 200 400 600 800 1000 1200
Fig. 5. Measured Position of the Sensors. 1
0 100 200 300 400 500 600
2 ping number
Fig. 7. Number of responses to ping messages (by message).
0 0.5 1 1.5 2 2.5 3 3.5 4
Deployment error (m)
Fig. 6. Histogram of deployment error.
number of pings
F. Deployment using an Autonomous Helicopter 40
The helicopter is given a waypoint ﬁle with the GPS
location (x, y, z) coordinates where the sensors need to be 30
deployed. It then ﬂies to each of those points and drops
the sensors. Figure 5 indicates the measured position of the
sensors deployed with respect to the actual position to be
deployed. Figure 6 shows a histogram of sensor deployment
error distance which has a median value of 1.2 metres. In 10
this particular set-of experiments the deployment was done
manually. The Helicopter was being teleoperated by a pi- 0
0 10 20 30 40 50 60
lot on the prescribed ﬂight path. When the helicopter was mote id
within a radius of 1.5 meters from the deployment location a
“drop” command was issued to deploy the motes. Completely
autonomous deployment experiments were also performed, Fig. 8. Number of responses to ping messages (by mote).
although we haven’t collected connectivity data for them yet. ﬂown during the experiment. The range over which these
motes responded is shown in Figure 9 where we see that
G. Air-to-ground connectivity the maximum range was nearly 13 meters, but the median
The number of responses to each air-to-ground ping is range was 9 meters. Note that the air-to-ground range is
shown in Figure 7. The maximum number of responses to any much greater than the 2.5 meter ground-to-ground range we
ping was 6 and the mean number was 2.1. In our experience measured, which is a typical asymmetry between ground-to-
the Mote radio is probabilistic with only a modest probability ground and air-to-ground radio transmissions.
that a message is successfully transferred. It is very likely that
more Motes received the ping and transmitted responses than H. Ground to ground connectivity
the number of responses which were actually received. The sensor network as ﬁrst deployed exhibited some discon-
The number of responses by mote id is shown in Figure 8 nection in communications between sensors. This was mea-
where we can see that only 19 motes (39%) responded. This sured by having each of the fourteen sensors broadcast ping
is a not a limitation of the motes, but a fact of the path messages and listen for replies from its neighbors. Figures 10
maximum distance (m)
Fig. 11. Connectivity of the originally deployed sensors.
0 10 20 30 40 50 60
mote id Fig. 12. Connectivity of the repaired network of deployed sensors.
Fig. 9. Maximum range at which ping message was acknowledged (by mote).
1) now participating in the network. Sensor 1 was found to
have been disconnected due to a hardware failure in its radio
transceiver. Note that the connectivity of the outlying sensors
(8, 14, 19, 20) has been improved even though the sensors that
were deployed to improve connectivity were not near them.
13 10 While intuitively this may not appear to make sense, there are a
variety of factors that can account for it. In particular, increases
in message trafﬁc can alter packet collision characteristics
20 3 which could improve connectivity in areas. For example, note
that although the connectivity between 20 and 14 improved,
the connectivity between 14 and 19 did not. This suggests that
18 1 deployment patterns for network repair may need to take into
account some characteristics of the radios used in the sensor
network. E.g., VHF radios which can penetrate obstacles may
require a different repair strategy than UHF radios which are
line of sight.
I. Lessons Learned
Fig. 10. Connectivity of the originally deployed sensors.
Our experiments have given us several insights into mobile
• The communication range is highly dependent on relative
and 11 show the resulting connectivity pattern as both a antenna orientation, shielding (eg. helicopter between
circular connection diagram and a diagram with the sensors two Motes), and when close to the ground, on ground
in their actual locations. Each sensor is a vertex in the graphs moisture. We found widely different ranges in Brisbane,
and the lines show which sensor could communicate via a LA, Dartmouth, and Pittsburgh.
round trip path with its neighbors. The thickness of the lines • The communication links are asymmetric and congestion
correspond to the percentage of ping replies received, with is a signiﬁcant concern.
thicker lines indicating better connectivity. Although connec- • In all our experiments two passes with the helicopter
tivity is good between some of the motes, overall the graphs were required for deploying and subsequently repairing
are sparsely linked indicating disconnection in the network. the network.
Based on this connectivity analysis another seven motes were • With Good Control of the Helicopter a disconnected
deployed from the helicopter to repair the communication network can be repaired in one more pass. Note that
gaps. Figures 13 and 12 show the result of the round trip this assumes that the Helicopter can carry the required
connectivity analysis on the repaired network. Connectivity number of sensors to repair the network and the topology
has been greatly improved, with all sensors (except sensor for repair is known.
 G. Buskey, J. Roberts, P. Corke, P. Ridley, and G. Wyeth, “Sensing
40 3 and control for a small-size helicopter,” in Experimental Robotics,
B. Siciliano and P. Dario, Eds. Springer-Verlag, 2003, vol. VIII, pp.
 S. Saripalli, J. M. Roberts, P. I. Corke, G. Buskey, and G. S. Sukhatme,
“A tale of two helicopters,” in IEEE/RSJ International Conference on
Intelligent Robots and Systems, Las Vegas, USA, Oct 2003, (To appear).
 S. Saripalli, J. F. Montgomery, and G. S. Sukhatme, “Visually-guided
landing of an unmanned aerial vehicle,” IEEE Transactions on Robotics
and Automation, vol. 19, no. 3, pp. 371–381, June 2003.
37 10  O. Shakernia, Y. Ma, T. J. Koo, and S. S. Sastry, “Landing an unmanned
air vehicle:vision based motion estimation and non-linear control,” in
Asian Journal of Control, vol. 1, September 1999, pp. 128–145.
36 11  V. Gavrilets, I. Martinos, B. Mettler, and E. Feron, “Control logic for
automated aerobatic ﬂight of miniature helicopter,” in AIAA Guidance,
Navigation and Control Conference, Monterey, CA, USA, Aug 2002.
 R. Vidal, O. Shakernia, H. J. Kim, D. Shim, and S. Sastry, “Probabilistic
pursuit-evasion games: Theory, implementation and experimental eval-
uation,” IEEE Transactions on Robotics and Automation, Oct 2002.
20 13  D. Estrin, R. Govindan, J. Heidemann, and S. Kumar, “Next century
challenges: Scalable coordination in sensor networks,” in ACM Mobi-
19 14 Com 99, Seattle, USA, August 1999.
18 16  J. Hill, R. Szewczyk, A. Woo, S. Hollar, D. Culler, and K. Pister,
“System architecture directions for network sensors,” in ASPLOS, 2000.
 M. Batalin and G. Sukhatme, “Spreading out: A local approach to multi-
Fig. 13. Connectivity of the repaired network of deployed sensors. robot coverage,” in Distributed Autonomous Robotic Systems 5, 2002,
 A. Howard, M. Mataric, and G. Sukhatme, “Mobile sensor network
deployment using potential ﬁelds: A distributed, scalable so lution to the
area coverage problem,” in Distributed Autonomous Robotic Systems 5,
• Deployment strategies are likely to need to be tailored 2002, pp. 299–308.
to sensor radio characteristics such as range, obstacle  G. J. Pottie, “Wireless sensor networks,” in IEEE Information Theory
Workshop, 1998, pp. 139–140.
penetrating capabilities, and antenna patterns.  J. Agre and L. Clare, “An integrated architeture for cooperative sensing
networks,” Computer, pp. 106 – 108, May 2000.
V. C ONCLUSION  P. Gupta and P. R. Kumar, “The capacity of wireless networks,” IEEE
Transactions on Information Theory, vol. IT-46, no. 2, pp. 388–404,
We have described control algorithms and experimental  A. Scaglione and S. Servetto, “On the interdependence of routing and
results from sensor network deployment with an autonomous data compression in multi-hop sensor networks,” in ACM Mobicom,
helicopter. By sprinkling sensor nodes using a ﬂying robot, we Atlanta, GA, 2002.
 Y. Chen and T. C. Henderson, “S-NETS: Smart sensor networks,” in
can reach remote or dangerous environments such as rugged Seventh International Symposium on Experiemental Robotics, Hawaii,
mountain slopes, burning forests, etc. We believe that this Dec. 2000.
kind of autonomous approach will enable the instrumentation  P. Corke, R. Peterson, and D. Rus, “Networked robots: Flying robot
navigation with a sensor network,” in ISRR, 2003.
of remote sites with communication, sensing, and computa-  Q. Li, M. DeRosa, and D. Rus, “Distributed algorithms for guiding
tion infrastructure, which in turn will support navigation and navigation across sensor networks,” in MOBICOM, 2003.
monitoring applications. From what we’ve learned in these  M. Batalin and G. S. Sukhatme, “Coverage exploration and deployment
by a mobile robot and communication network,” in 2nd International
experiments we plan to develop systems for automatic network Workshop on Information Processing in Sensor Networks, Palo Alto
repair. This will require the ground sensors and helicopter Research Center, Palo Alto, California, USA, April 2003, pp. 376–391.
to cooperate to identify network disconnections and guide  D. Corneil and C. Gotlieb, “An efﬁcient algorithm for graph isomor-
phism,” Journal of the ACM, vol. 17, no. 1, pp. 51–64, March 1970.
the helicopter to appropriate locations for autonomous sensor  J. E. Hopcraft and J. K. Wong, “Linear time algorithm for isomorphism
deployment. of planar graphs,” in 6th Annual ACM Symposium on Theory of
Computing, Seattle, Washington, 1974, pp. 172–184.
 University of Southern California Autonomous Flying Vehicle Home-
ACKNOWLEDGMENT page, “http://www-robotics.usc.edu/˜avatar.”
Support for this work was provided through the Institute
for Security Technology Studies, NSF awards EIA-9901589,
IIS-9818299, IIS-9912193, EIA-0202789 and 0225446, ONR
award N00014-01-1-0675 and DARPA Task Grant F-30602-
00-2-0585. This work is also supported in part by NASA
under JPL/caltech contract 1231521, by DARPA under grants
DABT63-99-1-0015 and 5-39509-A 9 (via UPenn) as part of
the Mobile Autonomous Robot Software (MARS) program.
Our thanks to our safety pilot Doug Wilson for keeping our
computers from (literally) crashing.