monitoring WSN may issue the following sliding-window
query: “sample seismic data every 10 s and archive at the BS
every 10 minutes,” where the deadline is 10 minutes. Second,
the delay bound may also be imposed due to the recharging
cycle of the BS. For instance, the battery of Robomote node
lasts for about 30 minutes [5] during movement. Although a
mobile BS can periodically replenish its energy (e.g., by
moving to a fixed docking station), frequent battery rechar-
ging should be avoided to reduce the disruptions to normal
operation of the network.
3.2 Network Model
According to several empirical studies [4], the speed that
data packets are relayed in a WSN is about several hundred
meters per second, which is much higher than the speed
that a mobile device moves. Therefore, the data collection
deadline can be mapped to the maximum allowable length
of the BS tour that visits all RPs. We denote the maximum
length of the BS tour, L ¼ v
m
D, where D is a data collection
deadline and v
m
is the average movement speed of BS. The
notation used in the rest of the paper is listed in Table 1.
We assume that data from different sources can be
aggregated at a node before being relayed. Data aggregation
[22] has been widely adopted by data collection applications
to reduce network traffic. Specifically, we assume the N-to-
one aggregation model in which a node can aggregate
multiple data packets it received into one packet before
relaying it. Such a model is applicable to a number of
scenarios of in-network data aggregation. First, many
monitoring WSNs allow use rs to query environ mental
information that are aggregated from spatially distributed
sensor readings [22]. For instance, a user may periodically
query the maximum or average value of temper ature
readings from all sensors deployed in a large biological
habitat. Second, many WSNs adopt in-network signal
processing techniques such as data fusion [32] for improving
the accuracy of sensing based on noisy measurements from
multiple sensors. For instance, data fusion schemes may
aggregate values or local decisions of multiple sensors to
improve the probability of detecting phenomenon of interest
[32]. In both applications described above, N sensor readings
can be aggregated into one, which significantly reduces the
energy consumption of the network.
We assume that nodes are densely deployed in a region
and all nodes use the same transmission power. Accord-
ingly, the total energy consumed by transmitting a data
packet along a multihop path is proportional to the euclidean
distance between sender and receiver. This assumption is
justified by the fact that the euclidean distance between two
nodes in a dense wireless network is approximately
proportional to the hop count between the same nodes
[24]. We note that such an energy model is also adopted by
several existing power-efficient data communication proto-
cols in WSNs [15]. This assumption also allows the BS to
estimate the network energy consumption without knowing
the global network topology. Although we assume that the
nodes are densely distributed in a network, our solutions are
not dependent on any particular distribution of nodes.
We assume that the storage capacity of a node is large
enough to buffer the total volume of data generated by the
sources within delivery deadline D. Several recent sensor
network platforms [23] can integrate 10-100 Mb NAND
flash memory with ultralow power consumption. Finally,
nodes and the BS are assumed to know their own physical
locations through the GPS units on them or a location
service in the network. An important function of many
WSNs is to gather spatially distributed information of the
environment. Therefore, the information gathered by
sensors often needs to be tagged with geographic location
in order for it to be useful. Accordingly, numerous
localization protocols [27] have been proposed for WSNs
in the literature. We also note that mobile BSs are typically
equipped with GPS units for the purpose of motion
planning, which can be utilized to significantly reduce the
overhead of localization.
3.3 Overview of the Approach
We investigate two rendezvous design problems in this
paper. In the first problem, the BSs may freely move within
the network deployment region. In the second problem, the
motion of the BSs is constrained on a fixed track. Although
such limited mobility reduces the contacts with fixed nodes
in a network, it significantly simplifies the motion control of
BSs and improves the system reliability. For instance,
several mobile sensor systems (e.g., XYZ [21] and NIMs
[2], [25]) are designed to move along fixed cables.
For each rendezvous design problem, we develop
approximation algorithms that are executed by BSs to find
a data collection tour, a set of RPs on the tour, and a set of
routing trees that are rooted at the RPs and connect all
sources. As we assume that the BS does not have the global
information about the network except the locations of
sources, the RPs found are physical locations at which there
may not exist real nodes. This issue can be addressed in the
following two ways. First, the BS may find a real node near
each RP through the network. For instance, it may send an
area anycast [12] message addressed to the physical location
of an RP. The message will be delivered to a node in the
vicinity of the intended location, which may serve as the RP.
Alternatively, BSs may travel along the calculated tour and
recruit nodes to serve as RPs.
4RENDEZVOUS DESIGN WITH A VARIABLE
BS TRACK
In this section, we study the rendezvous design problem
when the BS can freely move in the network deployment
region along any track. Our objective is to find a BS tour no
XING ET AL.: EFFICIENT RENDEZVOUS ALGORITHMS FOR MOBILITY-ENABLED WIRELESS SENSOR NETWORKS 49
TABLE 1
List of Notations