A two-tier data dissemination model for large-scale wireless sensor networks.
mobility brings new challenges to large-scale sensor networking. It suggests that information about each mobile sink's location be continuously propagated through the sensor field to keep all sensor nodes updated with the direction of forwarding future data reports. Unfortunately frequent location updates from multiple sinks can lead to both excessive drain of sensors' limited battery power supply and increased collisions in wireless transmissions. In this paper we describe TTDD, a Two-Tier Data Dissemination approach that provides scalable and efficient data delivery to multiple mobile sinks. Each data source in TTDD proactively builds a grid structure which enables mobile sinks to continuously receive data on the move by flooding queries within a local cell only. TTDD's design exploits the fact that sensor nodes are stationary and location-aware to construct and maintain the grid structures with low overhead. We have evaluated TTDD performance through both analysis and extensive simulation experiments. Our results show that TTDD handles multiple mobile sinks efficiently with performance comparable with that of stationary sinks.
INTRODUCTION
Recent advances in VLSI, microprocessor and wireless communication
technologies have enabled the deployment of large-scale
sensor networks where thousands, or even tens of thousands
of small sensors are distributed over a vast eld to
obtain ne-grained, high-precision sensing data [9, 10, 15].
These sensor nodes are typically powered by batteries and
communicate through wireless channels.
This paper studies the problem of scalable and e-cient
data dissemination in a large-scale sensor network from potentially
multiple sources to potentially multiple, mobile sinks.
In this work a source is dened as a sensor node that detects
a stimulus, which is a target or an event of interest, and
generates data to report the stimulus. A sink is dened as
a user that collects these data reports from the sensor net-
work. Both the number of stimuli and that of the sinks may
vary over time. For example in Figure 1, a group of soldiers
collect tank movement information from a sensor network
deployed in a battleeld. The sensor nodes surrounding a
tank detect it and collaborate among themselves to aggregate
data, and one of them generates a data report. The
soldiers collect these data reports. In this paper we consider
a network made of stationary sensor nodes only, whereas
sinks may change their locations dynamically. In the above
example, the soldiers may move around, and must be able
to receive data reports continuously.
mobility brings new challenges to large-scale sensor
networking. Although several data dissemination protocols
have been developed for sensor networks recently, such as Directed
Diusion [10], Declarative Routing Protocol [5] and
GRAB [20], they all suggest that each mobile sink need to
continuously propagate its location information throughout
the sensor eld, so that all sensor nodes get updated with the
direction of sending future data reports. However, frequent
location updates from multiple sinks can lead to both increased
collisions in wireless transmissions and rapid power
consumption of the sensor's limited battery supply. None
of the existing approaches provides a scalable and e-cient
solution to this problem.
In this paper, we describe TTDD, a Two-Tier Data Dissemination
approach to address the multiple, mobile sink
problem. Instead of propagating query messages from each
sink to all the sensors to set up data forwarding informa-
tion, TTDD design uses a grid structure so that only sensors
located at grid points need to acquire the forwarding
information. Upon detection of a stimulus, instead of passively
waiting for data queries from sinks | the approach
taken by most of the existing work, the data source proactively
builds a grid structure throughout the sensor eld and
sets up the forwarding information at the sensors closest to
grid points (henceforth called dissemination nodes). With
this grid structure in place, a query from a sink traverses
two tiers to reach a source. The lower tier is within the
local grid square of the sink's current location (henceforth
called cells), and the higher tier is made of the dissemination
nodes at grid points. The sink
oods its query within a cell.
When the nearest dissemination node for the requested data
receives the query, it forwards the query to its upstream dissemination
node toward the source, which in turns further
forwards the query, until it reaches either the source or a
dissemination node that is already receiving data from the
source (e.g. upon requests from other sinks). This query
forwarding process lays information of the path to the sink,
to enable data from the source to traverse the same two tiers
as the query but in the reverse order.
TTDD's design exploits the fact that sensor nodes are
both stationary and location-aware. Because sensors are assumed
to know their locations in order to tag sensing data [1,
8, 18], and because sensors' locations are static, TTDD can
use simple greedy geographical forwarding to construct and
maintain the grid structure with low overhead. With a grid
structure for each data source, queries from multiple mobile
sinks are conned within their local cells only, thus avoiding
excessive energy consumption and network overload from
global
ooding by multiple sinks. When a sink moves more
than a cell size away from its previous location, it performs
another local
ooding of data query which will reach a new
dissemination node. Along its way toward the source this
query will stop at a dissemination node that is already receiving
data from the source. This dissemination node then
forwards data downstream and nally to the sink. In this
way, even when sinks move continuously, higher-tier data
forwarding changes incrementally and the sinks can receive
data without interruption. Furthermore, because only those
sensors on the grid points (serving as dissemination nodes)
of a data source participate in its data dissemination, other
sensors are relieved from maintaining states. Thus TTDD
can eectively scale to a large number of sources and sinks.
The rest of this paper is organized as follows. Section 2 describes
the main design including grid construction, the two-tier
query and data forwarding, and grid maintenance. Section
3 analyzes the communication overhead and the state
complexity of TTDD, and compares with other sink-oriented
data dissemination designs. Simulation results are presented
in Section 4 to evaluate the eectiveness of our design and
analyze the impact of important parameters. We discuss
several design issues in Section 5 and compare with the related
work in Section 6. Section 7 concludes the paper.
2. TWO-TIER
This section presents the basic design of TTDD which is
based on the following assumptions:
A vast eld is covered by a large number of homogeneous
sensor nodes which communicate with each
other through short-range radios. Long distance data
delivery is accomplished by forwarding data across multiple
hops.
Each sensor node is aware of its own location (for example
through receiving GPS signals or through techniques
such as [1]). However, mobile sinks may or may
not know their own locations.
Once a stimulus appears, the sensors surrounding it
collectively process the signal and one of them becomes
the source to generate data reports [20].
Sinks (users) query the network to collect sensing data.
There can be multiple sinks moving around in the sensor
eld and the number of sinks may vary over time.
The above assumptions are consistent with the models for
real sensors being built, such as UCLA WINS NG nodes
[15], SCADDS PC/104 [4], and Berkeley Motes [9].
In addition, TTDD design assumes that the sensor nodes
are aware of their missions (e.g., in the form of the signatures
of each potential type of stimulus to watch). Each
mission represents a sensing task of the sensor network. In
the example of tank detection of Figure 1, the mission of the
sensor network is to collect and return the current locations
of tanks. In scenarios where the sensor network mission
changes, the new mission can be
ooded through the eld
to reach all sensor nodes. In this paper we do not discuss
how to manage the missions of sensor networks. However we
do assume that the mission of a sensor network changes only
infrequently, thus the overhead of mission dissemination is
negligible compared to that of sensing data delivery.
As soon as a source generates data, it starts preparing
for data dissemination by building a grid structure. The
source starts with its own location as one crossing point of
the grid, and sends a data announcement message to each of
its four adjacent crossing points. Each data announcement
message nally stops on a sensor node that is the closest to
the crossing point specied in the message. The node stores
the source information and further forwards the message to
its adjacent crossing points except the one from which it
received the message. This recursive propagation of data
announcement messages noties those sensors that are closest
to the crossing locations to become the dissemination
nodes of the given source.
Once a grid for the specied source is built, a sink can
then
ood its query within a local cell to receive data. The
query will be received by the nearest dissemination node on
the grid, which then propagates the query upstream through
other dissemination nodes toward the source. Requested
data will
ow down in the reverse path to the sink.
The above seemingly simple TTDD operation poses several
research challenges. For example, given that locations
of sensors are random and not necessarily on the crossing
points of a grid, how do nearby sensors of a grid point decide
a
a

Figure

2: One source B and one sink S
which one should serve as the dissemination node? Once the
data stream starts
owing, how can it be made to follow the
movement of a sink to ensure continued delivery? Given
individual sensors are subject to unexpected failures, how
is the grid structure maintained, once it is built? The remaining
of this section will address each of these questions
in detail. We start with the grid construction in Section
2.1, and present the two-tier query and data forwarding in
Section 2.2. Grid maintenance is described in Section 2.3.
2.1 Grid Construction
To simplify the presentation, we assume that a sensor eld
spans a two-dimensional plane. A source divides the plane
into a grid of cells. Each cell is an    square. A source
itself is at one crossing point of the grid. It propagates
data announcements to reach all other crossings, called dissemination
points, on the grid. For a particular source at
location dissemination points are located at
A source calculates the locations of its four neighboring
dissemination points given its location (x; y) and cell
size . For each of the four dissemination points Lp , the
source sends a data-announcement message to Lp using simple
greedy geographical forwarding, i.e., it forwards the message
to the neighbor node that has the smallest distance to
Lp . The neighbor node continues forwarding the data announcement
message in a similar way till the message stops
at a node that is closer to Lp than all its neighbors. If this
node's distance to Lp is less than a threshold =2, it becomes
a dissemination node serving dissemination point Lp
for the source. In cases where a data announcement message
stops at a node whose distance to the designated dissemination
point is greater than =2, the node simply drops the
message.
A dissemination node stores a few pieces of information for
the grid structure, including the data announcement mes-
sage, the dissemination point Lp it is serving and the up-stream
dissemination node's location. It then further propagates
the message to its neighboring dissemination points
on the grid except the upstream one from which it receives
the announcement. The data announcement message is recursively
propagated through the whole sensor eld so that
each dissemination point on the grid is served by a dissemination
node. Duplicate announcement messages from different
neighboring dissemination points are identied by the
sequence number carried in the announcement and simply
dropped.

Figure

2 shows a grid for a source B and its virtual grid.
The black nodes around each crossing point of the grid are
the dissemination nodes.
2.1.1 Explanation of Grid Construction
Because the above grid construction process does not assume
any a-priori knowledge of potential positions of sinks,
it builds a uniform grid in which all dissemination points are
regularly spaced with distance  in order to distribute data
announcements as evenly as possible. The knowledge of the
global topology is not required at any node; each node acts
based on information of its local neighborhood only.
In TTDD, the dissemination point serves as a reference
location when selecting a dissemination node. The dissemination
node is to be selected as close to the dissemination
point as possible, so that the dissemination nodes are evenly
distributed to form a uniform grid infrastructure. However,
the dissemination node is not required to be globally closest
to the dissemination point. Strictly speaking, TTDD
ensures that a dissemination node is locally closest but not
necessarily globally closest to the dissemination point, due
to irregularities in topology. This will not aect the correct
operation of TTDD. The reason is that each dissemination
node includes its own location (not that of the dissemination
point) in its further data announcement messages. This way,
downstream dissemination nodes will still be able to forward
future queries to this dissemination node, even though the
dissemination node is not globally closest to the dissemination
point in the ideal grid. This is to be further discussed
in Section 2.2.1.
We set the =2 distance threshold for a node to become
a dissemination node in order to stop the grid construction
at the network border. For example, in Figure 3, sensor
node B receives a data announcement destined to P which
is out of the sensor eld. Because sensor nodes are not
aware of the global sensor eld topology, they cannot tell
if a location is out of the network. Comparing with =2
provides nodes a simple rule to decide if the propagation
should be terminated.
When a dissemination point falls in a void area without
any sensor nodes in it, the data announcement propagation
might stop on the border of the void area. But propagation
can continue along other paths of the grid and go around
the void area, since each dissemination node forwards the
data announcement to all three other dissemination points.
As long as the grid is not partitioned, data announcements
will bypass the void by taking alternative paths.
We choose to build the grid on a per-source basis, so
that dierent sources recruit dierent sets of dissemination
nodes. This design choice enhances scalability and provides
load balancing and better robustness. When there are many
sources, as long as their grids do not overlap, a dissemination
node only has states about one or a few sources. This
allows TTDD to scale to large numbers of sources. We will
analyze the state complexity in section 3.3. In addition,
the per-source grid eectively distributes data dissemination
load among dierent sensor nodes to avoid bottlenecks.
This is motivated by the fact that each sensor node is energy-constrained
and the sensor nodes' radios usually have limited
bandwidth. The per-source grid construction also leads
to enhanced robustness in the presence of node failures.
a

Figure

3: Termination on border
The grid cell size  is a critical parameter. As we can see
in the next section, the general guideline to set the cell size
is to localize the impact of sink mobility within a single cell,
so that the higher-tier grid forwarding remains stable. The
choice of  aects energy e-ciency and state complexity.
It will be further analyzed in Section 3 and evaluated in
Section 4.
2.2 Two-Tier Query and Data Forwarding
2.2.1 Query Forwarding
Our two-tier query and data forwarding is based on the
virtual grid infrastructure to ensure scalability and e-ciency.
When a sink needs data, it
oods a query within a local
area about a cell size large to discover nearby dissemination
nodes. The sink species a maximum distance in the
query thus the
ooding stops at nodes that are more than
the maximum distance away from the sink.
Once the query reaches a local dissemination node, which
is called an immediate dissemination node for the sink, it is
forwarded on the grid to the upstream dissemination node
from which this immediate dissemination node receives data
announcements. The upstream one in turn forwards the
query further upstream toward the source, until nally the
query reaches the source. During the above process, each
dissemination node stores the location of the downstream
dissemination node from which it receives the query. This
state is used to direct data back to the sink later (see Figure
4 for an illustration).
With the grid infrastructure in place, the query
ooding
can be conned within the region of around a single cell-size.
It saves signicant amount of energy and bandwidth compared
to
ooding the query across the whole sensor eld.
Moreover, two levels of query aggregation 1 are employed
during the two-tier forwarding to further reduce the over-
head. Within a cell, an immediate dissemination node that
receives queries for the same data from dierent sinks aggregates
these queries. It only sends one copy to its upstream
dissemination node, in the form of an upstream update. Sim-
ilarly, if a dissemination node on the grid receives multiple
upstream updates from dierent downstream neighbors, it
forwards only one of them further. For example in gure
4, the dissemination node G receives queries from both the
cell where sink S1 is located and the cell where sink S2 is
located, and G sends only one upstream update message
toward the source.
When an upstream update message traverses the grid,
it installs soft-states in dissemination nodes to direct data
1 For simplicity, we do not consider semantic aggregation [10]
here, which can be used to further improve the aggregation
gain for dierent data resolutions and types.
Lower-tier Data Trajectory Forwarding
Higher-tier Data Grid Forwarding
Higher-tier Query Grid Forwarding
Lower-tier Query Flooding
G
PA
A
Figure

4: Two-tier query and data forwarding between
Source A and Sink S 1
.
starts with
ooding its
query with its primary agent PA's location, to its immediate
dissemination node Ds . Ds records PA's location
and forwards the query to its upstream dissemination
node until the query reaches A. The data are returned
to Ds along the way that the query traverses. Ds forwards
the data to PA, and nally to Sink S 1
. Similar
process applies to Sink S 2
, except that its query stops
on the grid at dissemination node G.
streams back to the sinks. Unless being updated, these
states are valid for a certain period only. A dissemination
node sends such messages upstream periodically in order
to receive data continuously; it stops sending such update
messages when it no longer needs the data, such as when
the sink stops sending queries or moves out of the local re-
gion. An upstream disseminate node automatically stops
forwarding data after the soft-state expires. In our current
design, the values of these soft-state timers are chosen an
higher than the interval between data
messages. This setting balances the overhead of generating
periodic upstream update messages and that of sending data
to places where it is no longer needed.
The two-level aggregation provides scalability with the
number of sinks. A dissemination node on the query forwarding
path maintains at most three states about which
neighboring dissemination nodes need data. An immediate
dissemination node maintains in addition only the states of
sinks located within the local region of about a single cell-
size. Sensor nodes that do not participate in query or data
forwarding do not keep any state about sinks or sources. We
analyze the state complexity in details in Section 3.3.
2.2.2 Data Forwarding
Once a source receives the queries (in the form of upstream
updates) from anyone of its neighbor dissemination nodes,
it sends out data to this dissemination node, which in turn
forwards data to where it receives the queries, so on and so
forth until the data reach each sink's immediate dissemination
node. If a dissemination node has aggregated queries
from dierent downstream dissemination nodes, it sends a
data copy to each of them. For example in Figure 4 the dissemination
node G will send data to both S1 and S2 . Once
the data arrive at a sink's immediate dissemination node,
trajectory forwarding (see Section 2.2.3) is employed to further
relay the data to the sink which might be in continuous
motion.
IA
PA
Immediate Agent (IA) Update
Trajectory Data Forwarding
Figure

5: Trajectory Forwarding from immediate dissemination
node Ds to mobile sink S 1 via primary agent
PA and immediate agent IA. Immediate agent IA is one-hop
away from S 1 . It relays data directly to sink S 1 .
moves out of the one-hop transmission range
of its current IA, it picks a new IA from its neighboring
nodes.
then sends an update to its PA and old IA
to relay data. PA is not changed as long as S 1
remains
within some range to PA.
With the two-tier forwarding as described above, queries
and data may take globally suboptimal paths, thus introducing
additional cost compared to forwarding along shortest
paths. For example in Figure 4, sink S1 and S2 may
nd straight-line paths to the source if they each
ooded
their queries across the whole sensor eld. However, the
path a message travels between a sink and a source by the
two-tier forwarding is at most
2 times the length of that
of a straight-line. We believe that the sub-optimality is well
worth the gain in scalability. A detailed analysis is given in
Section 3.
2.2.3 Trajectory Forwarding
Trajectory forwarding is employed to relay data to a mobile
sink from its immediate dissemination node. In trajectory
forwarding, each sink is associated with two sensor
nodes: a primary agent and an immediate agent. A sink
picks one neighboring sensor node as its primary agent and
includes the location of the primary agent in its queries. Its
immediate dissemination node sends data to the primary
agent, which in turn relays data to the sink. Initially the
primary agent and the immediate agent are the same sensor
node.
When a sink is about to move out of the range of its
current immediate agent, it picks another neighboring sensor
node as its new immediate agent, and sends the location of
the new immediate agent to its primary agent, so that future
data are forwarded to the new immediate agent. To avoid
losing data that have already been sent to the old immediate
agent, the location is also sent to the old immediate agent
(see

Figure

5). The selection of a new immediate agent can
be done by broadcasting a solicit message from the sink,
which then chooses the node that replies with the strongest
signal-to-noise ratio.
The primary agent represents the mobile sink at the sink's
immediate dissemination node, so that the sink's mobility is
made transparent to its immediate dissemination node. The
immediate agent represents the sink at the sink's primary
agent, so that the sink can receive data continuously while
in constant movement. Thus a user that does not know his
own location can still collect data from the network.
When the sink moves out of a certain distance, e.g., a cell
size, from its primary agent, it picks a new primary agent
and
oods a query locally to discover new dissemination
nodes that might be closer. To avoid receiving duplicate
data from its old primary agent, TTDD lets each primary
agent time out once its timer, which is set approximately to
the duration a mobile sink remains in a cell, expires. The
old immediate agent times out in a similar way, except that
it has a shorter timer which is approximately the duration
a sink remains within the one-hop distance. If a sink's immediate
dissemination node does not have any other sinks
or neighboring downstream dissemination nodes requesting
data for a certain period of time (similar to the timeout
value of the sink's primary agent), it stops sending update
messages to its upstream dissemination node so that data
are no longer forwarded to this cell.
An example is shown in gure 4, when the soft-state at the
immediate dissemination node Ds expires, Ds stops sending
upstream updates because it does not have any other sinks
or neighboring downstream dissemination nodes requesting
data. After a while, data forwarded at G only go to sink S2 ,
if S2 still needs data. This way, all states built on the grid
and in the old agents by a sink's old query are cleared.
With trajectory forwarding, sink mobility within a small
range, e.g., a cell size, is made transparent to the higher-
tier grid forwarding. Mobility beyond a cell-size distance
that involves new dissemination node discoveries might affect
certain upstream dissemination nodes on grids. Since
the new dissemination nodes that a sink discovers are likely
to be in adjacent cells, the adjustment to grid forwarding
will typically aect a few nearby dissemination nodes only.
2.3 Grid Maintenance
To avoid keeping grid states at dissemination nodes in-
denitely, a source includes a Grid Lifetime in the data announcement
message when sending it out to build the grid.
If the lifetime elapses and the dissemination nodes on the
grid do not receive any further data announcements to up-date
the lifetime, they clear their states and the grid no
longer exists.
Proper grid lifetime values depend on the data availability
period and the mission of the sensor network. In the example
of

Figure

1, if the mission is to return the \current"
tank locations, a source can estimate the time period that
the tank will stay around, and use this estimation to set the
grid lifetime. If the tank stays longer than the original es-
timation, the source can send out new data announcements
to extend the grid's lifetime.
For any structure, it is important to handle unexpected
component failures for robustness. To conserve the scarce
energy supply of sensor nodes, we do not periodically refresh
the grid during its lifetime. Instead, we employ a mechanism
called information duplication, in which each
dissemination node recruits from its neighborhood several
sensor nodes and replicates in them the location of its up-stream
dissemination node. When this dissemination node
fails, the upstream update messages from its downstream
dissemination node that needs data will stop at one of these
recruited nodes. The one then forwards the update message
to the upstream dissemination node according to the stored
information. 2 When data come from upstream later, a new
dissemination node will emerge following the same rule as
This neighbor can detect the failure of the dissemination
the source initially builds the grid.
Since this new dissemination node does not know which
downstream dissemination node neighbors need data, it simply
forwards data to all the other three dissemination points.
A downstream dissemination node neighbor that needs data
will continue to send upstream update messages to re-establish
the forwarding state; whereas one that does not need data
drops the data and does not send any upstream update, so
that future data reports will not
ow to it. Note that this
mechanism also handles the scenario where multiple dissemination
nodes fail simultaneously along the forwarding path.
The failure of the immediate dissemination node is detected
by a timeout at a sink. When a sink stops receiving
data for a certain time, it re-
oods a query to locate a new
dissemination node. The failures of primary agents or immediate
agents are detected by similar timeouts and new
ones will be picked.
Our grid maintenance is triggered on-demand by on-going
queries or upstream updates. Compared with periodic grid
refreshing, it trades computational complexity for less consumption
of energy, which is a more critical resource. We
show the performance of our grid maintenance through simulations
in Section 4.4.
3. OVERHEAD ANALYSIS
In this section we analyze the e-ciency and scalability of
TTDD. We measure two metrics: the communication overhead
for a number of sinks to retrieve a certain amount of
data from a source, and the complexity of the states that
are maintained in a sensor node for data dissemination. We
study both the stationary and the mobile sink cases.
We compare TTDD with the sink-oriented data dissemination
approach (henceforth called SODD), in which each
sink rst
oods the whole network to install data forwarding
state at all the sensor nodes, and then sources react to deliver
data. Directed Diusion [10], DRP [5] and GRAB [20]
all take this approach, although each employs dierent optimization
techniques, such as data aggregation and query
aggregation, to reduce the number of messages to be deliv-
ered. Because both aggregation techniques are applicable to
TTDD as well, we do not consider these aggregations when
we compare the communication overhead. Instead, our analysis
will focus on the worst-case communication overhead
of each protocol. We aim at making the analysis simple
and easy to follow while capturing the fundamental dier-
ences between TTDD and other approaches. We will add
the consideration of the aggregations when we analyze the
complexity in sensor state maintenance.
3.1 Model and Notations
We consider a square sensor eld of area A in which N
sensor nodes are uniformly distributed so that on each side
there are approximately
sensor nodes. There are k sinks
in the sensor eld. They move at an average speed v, while
receiving d data packets from a source in a time period of
T . Each data packet has a unit size and both the query and
data announcement messages have a comparable size l. The
communication overhead to
ood an area is proportional to
the number of sensor nodes in it, and to send a message along
node either through MAC layer mechanisms such as acknowledgments
when available, or explicitly soliciting a reply
if it does not overhear the dissemination node.
a path by greedy geographical forwarding is proportional to
the number of sensor nodes in the path. The average number
of neighbors within a sensor node's wireless communication
range is D.
In TTDD, the source divides the sensor eld into cells;
each has an area  2 . There are
A sensor nodes in
each cell and p n sensor nodes on each side of a cell. Each
sink traverses m cells, and m is upper bounded by 1
.
For stationary sinks,
3.2 Communication Overhead
We rst analyze the worst-case communication overhead
of TTDD and SODD. We assume in both TTDD and SODD
a sink updates its location m times, and receives d
data
packets between two consecutive location updates. In TTDD,
a sink updates its location by
ooding a query locally to
reach an immediate dissemination node, from which the
query is further forwarded to the source along the grid. The
overhead for the query to reach the source, without considering
query aggregation, is:
N)l
where nl is the local
ooding overhead, and c
N is the
average number of sensor nodes along the straight-line path
from the source to the sink (0 < c
2). Because a query
in TTDD traverses a grid instead of straight-line path, the
worst-case path length is increased by a factor of
2.
Similarly the overhead to deliver d
data packets from a
source to a sink is
m . For k mobile sinks, the
overhead to receive d packets in m cells is:
km
d
d)
Plus the overhead N l in updating the mission of the sensor
network and 4N p n l in constructing the grid, the total overhead
of TTDD becomes:
l d)
In SODD, every time a sink
oods the whole network, it
receives d
data packets. Data traverse straight-line path(s)
to the sink. Again, without considering aggregation, the
communication overhead is:
d
For k mobile sinks, the total worst-case overhead is:
c
d
Note that here we do not count the overhead to update
the sensor network mission because SODD can potentially
update the mission when a sink
oods its queries.
To compare TTDD and SODD, we have:
COTTDD
COSODD
mk
d
Thus, in a large-scale sensor network, TTDD has asymptotically
lower worst-case communication overhead compared
TTDD
Normalized

Figure

v.s. cell size
with an SODD approach as the sensor network scale (N ),
the number of sinks (k), or the sink mobility (characterized
by m) increases.
For example, a sensor network consists of
sensor nodes, there are sensor nodes in a TTDD
grid cell. Suppose data
packets:
COTTDD
COSODD
For the stationary sink case, suppose we have
four sinks
CO SODD
0:89. When the sink mobility
increases, CO TTDD
CO SODD
1. In this
network setup, TTDD has consistently lower overhead compared
with SODD in both the stationary and mobile sink
scenario.
Equation (1) shows the impact of the number of sensor
nodes in a cell (n) on TTDD's communication overhead.
For the example above, Figure 6 shows the TTDD communication
overhead as a function of n under dierent sink
moving speed. Because the overhead to build the grid decreases
while the local query
ooding overhead increases as
the cell size increases, Figure 6 shows the total communication
overhead as a tradeo between these two competing
components. We can also see from the Figure 6 that the
overall overhead is lower with smaller cells when the sink
mobility is signicant. The reason is that high sink mobility
leads to frequent in-cell
ooding, and smaller cell size limits
the
ooding overhead.
3.3 State Complexity
In TTDD, only dissemination nodes and their neighbors
which duplicate upstream information, sinks' primary agents
and immediate agents maintain states for data dissemina-
tion. All other sensor nodes do not need to maintain any
state. The state complexities at dierent sensor nodes are
analyzed as follows:
Dissemination nodes There are totally
dis-
semination nodes in a grid, each maintains the location
of its upstream dissemination node for query forward-
ing. For those on data forwarding paths, each maintains
locations of at most all the other three neighboring
dissemination nodes for data forwarding. The state
complexity for a dissemination node is thus O(1). A
dissemination node's neighbor that duplicate upstream
dissemination node's location also has O(1) state complexity

Immediate dissemination nodes A dissemination node
maintains states about the primary agents for all the
sinks within a local cell-size area. Assume there are
local sinks within the area, the state complexity for
an immediate dissemination node is thus O(k local ).
Primary and immediate agents A primary agent maintains
its sink's immediate agent's location, and an immediate
agent maintains its sink's information for trajectory
forwarding. Their state complexities are both
O(1).
Sources A source maintains states of its grid size, and locations
of its downstream dissemination nodes that request
data. It has a state complexity of O(1).
We consider data forwarding from s sources to k mobile
sinks. Assume in SODD the total number of sensor nodes on
data forwarding paths from a source to all sinks is P , then
the number of sensor nodes in TTDD's grid forwarding paths
is at most
2P . The total number of states maintained
for trajectory forwarding in sinks' immediate dissemination
nodes, primary agents, and immediate agents are k(s
The total state complexity is:
s

r
where b is the number of sensor nodes around a dissemination
point that has the location of the upstream dissemination
node, a small constant.
In SODD, each sensor node maintains a state to its up-stream
sensor node toward the source. In the scenario of
multiple sources, assuming perfect data aggregation, a sensor
node maintains at most per-neighbor states. For those
sensor nodes on forwarding paths, due to the query aggre-
gation, they maintain at most per-neighbor states to direct
data in the presence of multiple sinks. The state complexity
for the whole sensor network is:
(D 1)  N (D
The ratio of TTDD and SODD state complexity is:
That is, for large-scale sensor networks, TTDD maintains
around only sb
of the states as an SODD approach.
For the example of Figure 1 where we have 2 sources and 3
sinks, suppose 5 and there are 100 sensor nodes within
a TTDD grid cell and each sensor node has 10 neighbors on
average, TTDD maintains only 1.1% of the states of that
of SODD. This is because in TTDD sensor nodes that are
out of the grid forwarding infrastructure generally do not
maintain any state for data dissemination.
3.4

Summary

In this section, we analyze the worst-case communication
overhead, and the state complexity of TTDD. Compared
with an SODD approach, TTDD has asymptotically lower
worst-case communication overhead as the sensor network
size, the number of sinks, or the moving speed of a sink
increases. TTDD has a lower state complexity, since sensor
nodes that are not in the grid infrastructure do not need to
maintain states for data dissemination. For a sensor node
that is part of the grid infrastructure, its state complexity is
bounded and independent of the sensor network size or the
number of sources and sinks.
number
Average
success
ratio
over
all
source-sink
pairs
source
sources
sources
sources

Figure

7: Success rate for dierent
numbers of sinks and sources
Total
energy
consumed
in
transmission
and
receiving
source
sources
4 sources
8 sources

Figure

8: Energy for dierent numbers
of sinks and sources
number
Average
delay
(sec)
source
sources
4 sources
8 sources

Figure

9: Delay for dierent numbers
of sinks and sources
4. PERFORMANCE EVALUATION
In this section, we evaluate the performance of TTDD
through simulations. We rst describe our simulator imple-
mentation, simulation metrics and methodology in Section
4.1. Then we evaluate how environmental factors and control
parameters aect the performance of TTDD in Sections
4.2 to 4.5. The results conrm the e-ciency and scalability
of TTDD to deliver data from multiple sources to multiple,
mobile sinks. Section 4.6 shows that TTDD has comparable
performance with Directed Diusion [10] in stationary sink
scenarios.
4.1 Metrics and Methodology
We implement the TTDD protocol in ns-2. We use the
basic greedy geographical forwarding with local
ooding to
bypass dead ends [6]. To facilitate comparisons with Directed
Diusion, we use the same energy model as adopted
in its implementation in ns-2.1b8a, and the underlying MAC
is 802.11 DCF. A sensor node's transmitting, receiving and
idling power consumption rates are 0.66W, 0.395W and 0.035W
respectively.
We use three metrics to evaluate the performance of TTDD.
The energy consumption is dened as the communication
(transmitting and receiving) energy the network consumes;
the idle energy is not counted since it depends largely on
the data generation interval and does not indicate the efciency
of data delivery. The success rate is the ratio
of the number of successfully received reports at a sink to
the total number of reports generated by a source, averaged
over all source-sink pairs. This metric shows how eective
the data delivery is. The delay is dened as the average
time between the moment a source transmits a packet and
the moment a sink receives the packet, also averaged over
all source-sink pairs. This metric indicates the freshness of
data packets.
The default simulation setting has 4 sinks and 200 sensor
nodes randomly distributed in a 20002000m 2 eld, of
which 4 nodes are sources. Each simulation run lasts for
200 seconds, and each result is averaged over three random
network topologies. A source generates one data packet per
second. Sinks' mobility follows the standard random Way-point
model. Each query packet has 36 bytes and each data
packet has 64 bytes. Cell size  is set to 600 meters and a
sink's local query
ooding range is set to 1:3; it is larger
than  to handle irregular dissemination node distributions.
4.2 Impact of the numbers of sinks and sources
We rst study the impact of the number of sinks and
sources on TTDD's performance. The number of sinks and
sources varies from 1, 2, 4 to 8. Sinks have a maximum
speed of 10m/s, with a 5-second pause time. Figure 7 shows
the success rates. Each curve is for a specic number of
sources. For each curve, given the xed number of sources,
the success rate slightly decreases as the number of sinks
increases. For example, in the 2-source case, success rate
decreases slightly from 0.98 to 0.92 when the number of sinks
reaches 8. For a specic number of sinks, the success rate
decreases more visibly as the number of source increases. In
the 8-sink case, the success rate decreases from close to 1.0
to about 0.8 as the sources increase to 8. This is because
more sources generate more data packets, which lead to more
contention-induced losses. Despite some
uctuations, the
reasonably high success rates show that TTDD delivers most
data packets successfully from multiple sources to multiple,
mobile sinks, and the delivery quality does not degrade much
as the number of sources or sinks increases.

Figure

8 shows the energy consumption. We make two ob-
servations. First, for each curve, the energy increases as the
number of sinks increases, but the slope tends to decrease
slightly. As the number of sinks doubles, the energy consumed
for queries at the lower-tier
ooding typically dou-
bles. However, in the higher-tier grid forwarding, queries
may be merged into one upstream update message toward
the source and thus lead to energy savings. Therefore, when
the number of sinks doubles, total energy consumption does
not double. This is why the slope tends to decrease. Sec-
ond, for a specic number of sinks (e.g., 4 sinks), energy
consumption typically doubles as the number of sources dou-
bles. This is because the total data packets generated by the
sources increase proportionally and result in proportional increase
in energy consumptions. An exception happens when
the number of sources increases from one to two. This is
because the lower-tier query
ooding remains xed as the
number of sources increases, but it contributes a large portion
of the total energy consumption in the 1-source case.

Figure

9 plots the delay metric, which tends to increase
when there are more sinks or sources. More sources generate
more data packets, and more sinks need more local
query
ooding. Both increase the tra-c volume and lead
to longer delivery time. Some exception points of the gure
occur because data packets that have been cached in a sink's
immediate dissemination node for some time are included in
the delay calculation.
4.3 Impact of Sinks' Mobility
We next evaluate the impact of the sink's moving speed
on TTDD. In the default simulation setting, we vary the
maximum speed of sinks from 0, 5, 10, to 20m/s.
Max sink speed
Average
success
ratio
over
all
source-sink
pairs

Figure

10: Success rate for sinks' mobilit

Max sink speed
Total
energy
consumed
in
transmission
and
receiving

Figure

11: Energy for sinks' mobility
Max sink speed
Average
delay
(sec)

Figure

12: Delay for sinks' mobility
Average
Success

Figure

13: Success rate for sensor
node failures
Total
energy
consumed
in
transmission
and
receiving

Figure

14: Energy for sensor node failure

Cell size
Average
energy
consumption
in
transmission
and
receiving

Figure

15: Energy consumption with
dierent cell sizes

Figure

shows the success rate as the sinks' moving
speed changes. The success rate remains around 0:9 1:0
as sinks move faster. This shows that trajectory forwarding
is able to deliver data to mobile sinks without much interruption
even when sinks move at very high speed of 20m/s.

Figure

11 shows that the energy consumption increases as
the sinks' moving speed increases. The faster a sink moves,
the more frequently the sink needs a new immediate dissemination
node, and the more frequently the sink
oods its
local queries to discover it. However, the slope of the curve
decreases since the higher-tier grid forwarding is much less
aected by the mobility speed. Figure 12 plots the delay for
data delivery, which increases only slightly as the sink moves
faster. This shows that high-tier grid forwarding eectively
localizes the impact of sink mobility.
4.4 Resilience to Sensor Node Failures
We further study how node failures aect TTDD. In the
default simulation setting of 200 nodes, we allow 5% or 10%
randomly-chosen nodes to experience sudden, simultaneous
failures at 20s. The detailed study of simulation traces
shows that under such scenarios, some dissemination nodes
on the grid fail. Without any repairing, failure of such dissemination
nodes would have stopped data delivery to all
downstream sinks and decreased the success ratio substan-
tially. However, Figure 13 shows that the success rate drops
mildly. This conrms that our grid maintenance mechanism
of Section 2.3 works eectively to reduce the impact of node
failures. As node failure becomes more severe, energy consumption
also decreases due to reduced data packet delivery.
This is shown in Figure 14. Overall, TTDD is quite resilient
to node failures in all simulated scenarios.
4.5 Cell Size
We have explored the impact of various environmental
factors in previous sections. In this section we evaluate how
cell size  aects TTDD. To extend the cell size to larger
values while still having enough number of cells in the simulated
sensor eld, we would have to simulate over 2000
sensor nodes if the node density remains the same. Given
the computing power available to us to run ns-2, we have to
reduce the node density in order to reduce the total number
of simulated sensor nodes. We use 960 sensor nodes in
a 6200x6200m 2 eld, which are spaced at 200m distances
regularly to make the simple, greedy geographical forwarding
algorithm still work. There are one source and one sink.
The cell size varies from 400m to 1800m with an incremental
step of 200m. Because of the regular node placement, the
success rate and the delay do not change much so we focus
on studying the energy consumption trend.

Figure

15 shows that the energy consumption evolves the
same as predicted in our analysis of Section 3. The energy
rst decreases as the cell size increases because it takes less
energy to build a grid with larger cell size. Once the cell size
increases to 1000m, however, the energy starts to increase.
This is because the local query
ooding consumes more energy
in large cells. It degrades to global
ooding if only one
big cell exists in the entire sensor network.
4.6 Comparison with Directed Diffusion
In this section we compare the performance of TTDD and
Directed Diusion in the scenario of stationary sinks. We
apply the same scenarios of Section 4.2 (except that sinks are
stationary now) on both TTDD and Directed Diusion to
study the impact of dierent numbers of sinks and sources.
All simulations have 200 sensor nodes in a 20002000m 2
eld. The simulation results are shown in Figures 16{21.
We rst look at success rates, shown in Figures 16 and 19.
TTDD and Directed Diusion have similar success rates,
ranging between 0.8 and 1.0, except that Directed Diusion
number
Average
success
ratio
over
all
source-sink
pairs
source
sources
4 sources
8 sources

Figure

Success rate for TTDD of
stationary sinks
number
Energy
consumed
by
Tx/Rx
packets
(Joules)
sources
source
4 sources
8 sources

Figure

17: Energy for TTDD of stationary
sinks
Average
delay
(sec)
source
sources
sources
sources

Figure

18: Delay for TTDD of stationary
sinks
Average
success
ratio
over
all
source-sink
pairs
source
sources
4 sources
8 sources

Figure

19: Success rate for Directed
Diusion
number
Energy
consumed
by
Tx/Rx
packets
(Joules)
source
sources
4 sources
8 sources

Figure

20: Energy for Directed Diu-
sion
Average
delay
(sec)
source
sources
4 sources
8 sources

Figure

21: Delay for Directed Diu-
sion
has slightly larger
uctuations in some cases.

Figures

17 and 20 plot the energy consumption for TTDD
and Directed Diusion. For the same number of sinks, energy
consumption nearly doubles as the number of sources
doubles (except for the case of 1 to 2 sources). Given a
specic number of sources, more energy is consumed as the
number of sinks increases, but the slope of each curve tends
to decrease. This shows that both TTDD and Directed Diffusion
scale similarly to the number of sources and stationary
sinks in terms of energy consumption. When the number
of sinks is small (1 or 2 sinks), TTDD consumes less energy
than Directed Diusion. This is because query
ooding in
TTDD is conned to a local cell, while in Directed Diusion
a query propagates throughout the network eld. For larger
number of sinks (say, 8 sinks), Directed Diusion aggregates
queries from dierent sinks more aggressively; therefore, its
energy consumption increases less rapidly.

Figures

and 21 plot the delay experienced by TTDD
and Directed Diusion, respectively. When the number of
sources is 1, 2, or 4, they have comparable delay values.
When the number of sources increases to 8, TTDD experiences
much lower delay. This is because in Directed Diu-
sion data forwarding paths from dierent sources may cross
or overlap with each other anywhere, thus there are more
interferences when the number of sources is large. Whereas
in TTDD each source has its own grid, thus data
ows on
dierent grids do not interfere each other that much.
5. DISCUSSIONS
In this section, we comment on several design issues and
discuss future work.
Knowledge of the cell size Sensor nodes need to know
the cell size  so as to build grids once they become sources.
The knowledge of  can be specied through some external
mechanism. One option is to include it in the mission
statement message, which noties each sensor the sensing
task. The mission statement message is
ooded to each sensor
at the beginning of the network operation or during a
mission update phase. The sink also needs  to specify the
maximum distance a query should be
ooded. It can obtain
from its neighbor. To deal with irregular local topology
where dissemination nodes may fall beyond a xed
ooding
scope, the sink may apply expanded ring search to reach the
dissemination node.
Greedy geographical routing failures Greedy geographical
forwarding may fail in scenarios where the greedy
path does not exist, that is, a path requires temporarily forwarding
the packet away from the destination. This problem
has been solved by several approaches such as GPSR [11].
However, due to the the complexity of the complete solutions
and the fact the greedy path almost always exists in
a densely deployed sensor network [12], we only use a very
basic version of greedy forwarding. In the rare cases where
the greedy path does not exist, that is, the packet is forwarded
to a sensor node without a neighbor that is closer
to the destination, the node locally
oods the packets to
get around the dead end [6]. We nd out that this simple
technique works quite well in TTDD.
Mobile stimulus TTDD focuses on handling mobile sinks.
In the scenario of a mobile stimulus, the sources along the
stimulus' trail may each build a grid. To reduce the overhead
of frequent grid construction, a source can reuse the grid already
built by other sources. Specically, before a source
starts to build its grid, it locally
oods a \Grid Discovery"
message within the scope of about a cell size to probe any
existing grid for the same stimulus. A dissemination node
on the existing grid replies to the new source. The source
can then use the existing grid for its data dissemination. We
leave this as future work.
Non-uniform grid layout So far we assume no a priori
knowledge on sink locations. For this case, a uniform
grid is constructed to distribute the forwarding states as
evenly as possible. However, this even distribution has a
drawback of incurring certain amount of resource waste in
regions where sinks never roam into. This problem can be
partially addressed through learning or predicting the sinks'
locations. If the sinks' locations are available, TTDD can
be further optimized to build a globally non-uniform grid
where the grid only exists in regions where sinks currently
reside or are about to move into. The accuracy in estimation
of the current locations or prediction of the future locations
of sinks will aect the performance. We intend to further
explore this aspect in the future.
Mobile sensor node This paper considers a sensor net-work
that consists of stationary sensor nodes only. It is
possible to extend this design to work with sensor nodes of
low mobility. However, the grid states may be handed over
between mobile dissemination nodes. Fully addressing data
dissemination in highly mobile sensor network needs new
mechanisms and is beyond the scope of this paper.
mobility speed TTDD addresses sink mobility by
localizing the mobility impact on data dissemination within
a single cell and handling the intra-cell mobility through
trajectory forwarding. However, there is also a limit for our
approach to accommodate sink mobility. The sink cannot
move faster than the local forwarding states are updated
(within a cell size). The two-tier forwarding is best suited
to deal with \localized" mobility patterns, in which a sink
does not change its primary agent frequently.
Data aggregation We assume a group of nodes that detect
an object or an event of interests can collaboratively
process the sensing data and only one node generates a report
as a source. Although TTDD benets further from
en-route semantic data aggregation [10], we do not evaluate
this performance gain since it is highly dependent on the
specic applications and their semantics.
6. RELATED WORK
Sensor networks have been a very active research eld in
recent years. Energy-e-cient data dissemination is among
the rst set of research issues being addressed. SPIN [7] is
one of the early work that focuses on e-cient dissemination
of an individual sensor's observations to all the sensors in a
network. SPIN uses meta-data negotiation to eliminate the
transmission of redundant data. More recent work includes
Directed Diusion [10], Declarative Routing Protocol (DRP)
[5] and GRAB [20]. Directed Diusion and DRP are similar
in that they both take the data-centric naming approach
to enable in-network data aggregation. Directed Diusion
employs the techniques of initial low-rate data
ooding and
gradual reinforcement of better paths to accommodate certain
levels of network and sink dynamics. GRAB targets
at robust data delivery in an extremely large sensor net-work
made of highly unreliable nodes. It uses a forwarding
mesh instead of a single path, where the mesh's width can
be adjusted on the
y for each data packet.
While such previous work addresses the issue of delivering
data to stationary or very low-mobility sinks, TTDD design
targets at e-cient data dissemination to multiple, both stationary
and mobile sinks in large sensor networks. TTDD
diers from the previous work in three fundamental ways.
First of all, TTDD demonstrates the feasibility and benets
of building a virtual grid structure to support e-cient data
dissemination in large-scale sensor elds. A grid structure
keeps forwarding states only in the nodes around dissemination
points, and only the nodes between adjacent grid
points forward queries and data. Depending on the chosen
cell size, the number of nodes that keep states or forward
messages can be a small fraction of the total number of sensors
in the eld. Second, this grid structure enables mobile
sinks to continuously receive data on the move by
ooding
queries within a local cell only. Such local
oodings minimize
the overall network load and the amount of energy
needed to maintain data-forwarding paths. Third, TTDD
design incorporates eorts from both sources and sinks to
accomplish e-cient data delivery to mobile sinks; sources
in TTDD proactively build the grid structure to enable mobile
sinks learning and receiving sensed data quickly and
e-ciently.
Rumor routing [3] avoids
ooding of either queries or data.
A source sends out \agents" which randomly walk in the sensor
network to set up event paths. Queries also randomly
walk in the sensor eld until they meet an event path. Although
this approach shares a similar idea of making data
sources play more active roles, rumor routing does not handle
mobile sinks. GEAR [21] makes use of geographical location
information to route queries to specic regions of a
sensor eld. If the regions of data sources are known, this
scheme provides energy savings over network
ooding approaches
by limiting the
ooding to a geographical region,
however it does not handle the case where the destination
location is not known in advance.
TTDD also bears certain similarity to the study on self-
conguring ad hoc wireless networks. GAF [19] proposes
to build a geographical grid to turn o nodes for energy
conservation. The GAF grid is pre-dened and synchronized
in the whole sensor eld, with the cell size determined by
the communication range of nodes' radios. The TTDD grid
diers from that of GAF in that the former is constructed
dynamically as needed by data sources, and we use it for a
dierent purpose of limiting the impact of sink mobility.
There is a rich literature on mobile ad hoc network clustering
algorithms [2, 13, 14, 16]. Although they seem to
share similar approaches of building virtual infrastructures
for scalable and e-cient routing, TTDD targets at communication
that is data-oriented, not that based on underlying
network addressing schemes. Moreover, TTDD builds
the grid structure over stationary sensor nodes using location
information, which leads to very low overhead in the
construction and maintenance of the infrastructure. In con-
trast, node mobility in a mobile ad hoc network leads to
signicantly higher cost in building and maintaining virtual
infrastructures, thus osetting the benets.
Perhaps TTDD can be most clearly described by contrasting
its design with that of DVMRP [17]. DVMRP supports
data delivery from multiple sources to multiple receivers and
faces the same challenge as TTDD, that is how to make
all the sources and sinks meet without a prior knowledge
about the locations of either. DVMRP solves the problem
by letting each source
ood data periodically over the entire
network so that all the interested receivers can grasp on
the multicast tree along the paths data packets come from.
Such a source
ooding approach handles sink mobility well
but at a very high cost. TTDD inherits the source proactive
approach with a substantially reduced cost. In TTDD
a data source informs only a small set of sensors of its existence
by propagating the information over a grid structure
instead of notifying all the sensors. Instead of sending data
over the grid TTDD simply stores the source information;
data stream is delivered downward specic grid branch or
branches only upon receiving queries from one or more sinks
down that direction or directions.
7. CONCLUSION
In this paper we described TTDD, a two-tier data dissemination
design, to enable e-cient data dissemination in large-scale
wireless sensor networks with sink mobility. Instead of
passively waiting for queries from sinks, TTDD exploits the
property of sensors being stationary and location-aware to
let each data source build and maintain a grid structure in an
e-cient way. Sources proactively propagates the existence
information of sensing data globally over the grid structure,
so that each sink's query
ooding is conned within a local
gird cell only. Queries are forwarded upstream to data
sources along specic grid branches, pulling sensing data
downstream toward each sink. Our analysis and extensive
simulations have conrmed the eectiveness and e-ciency
of the proposed design, demonstrating the feasibility and
benets of building an infrastructure in stationary sensor
networks.
8.

ACKNOWLEDGMENT

We thank our group members of Wireless Networking
Group (WiNG) and Internet Research Lab (IRL) at UCLA
for their help during the development of this project and
their invaluable comments on many rounds of earlier drafts.
Special thanks to Gary Zhong for his help on the ns-2 simu-
lator, and Jesse Cheng for his verication on the simulation
results. We would also like to thank the anonymous reviewers
for their constructive criticisms.
9.



--R

Recursive Position Estimation in Sensor Networks.
Distributed Clustering for Ad Hoc Networks.
Rumor Routing Algorithm for Sensor Networks.
Application Driver for Wireless Communications Technology.
Declarative ad-hoc sensor networking
Routing and Addressing Problems in Large Metropolitan-scale Internetworks
Adaptive Protocols for Information Dissemination in Wireless Sensor Networks.
Location Systems for Ubiquitous Computing.
System Architecture Directions for Networked Sensors.
Directed Di
GPSR: Greedy Perimeter Stateless Routing for Wireless Networks.
A Scalable Location Service for Geographic Ad Hoc Routing.
Adaptive Clustering for Mobile Wireless Networks.
A Mobility-Based Framework for Adaptive Clustering in Wireless Ad-Hoc Networks
Integrated Network Sensors.
CEDAR: Core Extraction Distributed Ad hoc Routing.
Distance Vector Multicast Routing Protocol.
A New Location Technique for the Active O-ce
Geography Informed Energy Conservation for Ad Hoc Routing.
GRAdient Broadcast: A Robust
A Recursive Data Dissemination Protocol for Wireless Sensor Networks.
--TR
Adaptive protocols for information dissemination in wireless sensor networks
integrated network sensors
Directed diffusion
A scalable location service for geographic ad hoc routing
GPSR
Habitat monitoring
System architecture directions for networked sensors
Geography-informed energy conservation for Ad Hoc routing
Location Systems for Ubiquitous Computing
Distributed Clustering for Ad Hoc Networks

--CTR
Wensheng Zhang , Guohong Cao, Optimizing tree reconfiguration to track mobile targets in sensor networks, ACM SIGMOBILE Mobile Computing and Communications Review, v.7 n.3, July

Kavitha Gundappachikkenahalli , Hesham H. Ali, ADPROC: an adaptive routing framework to provide QOS in wireless sensor networks, Proceedings of the 24th IASTED international conference on Parallel and distributed computing and networks, p.76-83, February 14-16, 2006, Innsbruck, Austria
Bhaskar Krishnamachari , Fernando Ordez, Fundamental limits of networked sensing: the flow optimization framework, Wireless sensor networks, Kluwer Academic Publishers, Norwell, MA, 2004
Wensheng Zhang , Guohong Cao , Tom La Porta, Dynamic proxy tree-based data dissemination schemes for wireless sensor networks, Wireless Networks, v.13 n.5, p.583-595, October 2007
Wensheng Zhang , Hui Song , Sencun Zhu , Guohong Cao, Least privilege and privilege deprivation: towards tolerating mobile sink compromises in wireless sensor networks, Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing, May 25-27, 2005, Urbana-Champaign, IL, USA
Xuhui Hu , Yong Liu , Myung J. Lee , Tarek N. Saadawi, A novel route update design for wireless sensor networks, ACM SIGMOBILE Mobile Computing and Communications Review, v.8 n.1, January 2004
Zehua Zhou , Xiaojing Xiang , Xin Wang, An Energy-Efficient Data-Dissemination Protocol inWireless Sensor Networks, Proceedings of the 2006 International Symposium on on World of Wireless, Mobile and Multimedia Networks, p.13-22, June 26-29, 2006
Umut Ozertem , Deniz Erdogmus, Information Regularized Sensor Fusion: Application to Localization  With Distributed Motion Sensors, Journal of VLSI Signal Processing Systems, v.49 n.2, p.291-299, November  2007
Jeong-Hun Shin , Jaesub Kim , Keuntae Park , Daeyeon Park, Railroad: virtual infrastructure for data dissemination in wireless sensor networks, Proceedings of the 2nd ACM international workshop on Performance evaluation of wireless ad hoc, sensor, and ubiquitous networks, October 10-13, 2005, Montreal, Quebec, Canada
Yu He , Cauligi S. Raghavendra , Steven Berson , Robert Braden, An autonomic routing framework for sensor networks, Cluster Computing, v.9 n.2, p.191-200, April     2006
Jeff Hornsberger , Gholamali C. Shoja, Geographic grid routing: designing for reliability in wireless sensor networks, Proceeding of the 2006 international conference on Communications and mobile computing, July 03-06, 2006, Vancouver, British Columbia, Canada
Sushant Jain , Rahul C. Shah , Waylon Brunette , Gaetano Borriello , Sumit Roy, Exploiting mobility for energy efficient data collection in wireless sensor networks, Mobile Networks and Applications, v.11 n.3, p.327-339, June 2006
Hsing-Jung Huang , Ting-Hao Chang , Shu-Yu Hu , Polly Huang, Magnetic diffusion: disseminating mission-critical data for dynamic sensor networks, Proceedings of the 8th ACM international symposium on Modeling, analysis and simulation of wireless and mobile systems, October 10-13, 2005, Montral, Quebec, Canada
Fan Ye , Gary Zhong , Songwu Lu , Lixia Zhang, GRAdient broadcast: a robust data delivery protocol for large scale sensor networks, Wireless Networks, v.11 n.3, p.285-298, May 2005
Rui Zhang , Hang Zhao , Miguel A. Labrador, The Anchor Location Service (ALS) protocol for large-scale wireless sensor networks, Proceedings of the first international conference on Integrated internet ad hoc and sensor networks, May 30-31, 2006, Nice, France
Gregory Hartl , Baochun Li, Loss inference in wireless sensor networks based on data aggregation, Proceedings of the third international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA
Wei-Peng Chen , Jennifer C. Hou , Lui Sha, Dynamic Clustering for Acoustic Target Tracking in Wireless Sensor Networks, IEEE Transactions on Mobile Computing, v.3 n.3, p.258-271, July 2004
Xiaojiang Du , Fengjing Lin, Maintaining differentiated coverage in heterogeneous sensor networks, EURASIP Journal on Wireless Communications and Networking, v.5 n.4, p.565-572, September 2005
Wei Liu , Yanchao Zhang , Wenjing Lou , Yuguang Fang, A robust and energy-efficient data dissemination framework for wireless sensor networks, Wireless Networks, v.12 n.4, p.465-479, July 2006
Hao Yang , Fan Ye , Yuan Yuan , Songwu Lu , William Arbaugh, Toward resilient security in wireless sensor networks, Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing, May 25-27, 2005, Urbana-Champaign, IL, USA
K. Shashi Prabh , Tarek F. Abdelzaher, Energy-conserving data cache placement in sensor networks, ACM Transactions on Sensor Networks (TOSN), v.1 n.2, p.178-203, November 2005
Hyung Seok Kim , Tarek F. Abdelzaher , Wook Hyun Kwon, Dynamic delay-constrained minimum-energy dissemination in wireless sensor networks, ACM Transactions on Embedded Computing Systems (TECS), v.4 n.3, p.679-706, August 2005
Ossama Younis , Sonia Fahmy, HEED: A Hybrid, Energy-Efficient, Distributed Clustering Approach for Ad Hoc Sensor Networks, IEEE Transactions on Mobile Computing, v.3 n.4, p.366-379, October 2004
Yihong Wu , Lin Zhang , Yiqun Wu , Zhisheng Niu, Interest dissemination with directional antennas for wireless sensor networks with mobile sinks, Proceedings of the 4th international conference on Embedded networked sensor systems, October 31-November 03, 2006, Boulder, Colorado, USA
Hyung Seok Kim , Tarek F. Abdelzaher , Wook Hyun Kwon, Minimum-energy asynchronous dissemination to mobile sinks in wireless sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA
Xin Li , Young Jin Kim , Ramesh Govindan , Wei Hong, Multi-dimensional range queries in sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA
Qun Li , Daniela Rus, Navigation protocols in sensor networks, ACM Transactions on Sensor Networks (TOSN), v.1 n.1, p.3-35, August 2005
Qun Li , Michael De Rosa , Daniela Rus, Distributed algorithms for guiding navigation across a sensor network, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA
Nadeem Ahmed , Salil S. Kanhere , Sanjay Jha, The holes problem in wireless sensor networks: a survey, ACM SIGMOBILE Mobile Computing and Communications Review, v.9 n.2, April 2005
Rik Sarkar , Xianjin Zhu , Jie Gao, Double rulings for information brokerage in sensor networks, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA
Taejoon Park , Kang G. Shin, Soft Tamper-Proofing via Program Integrity Verification in Wireless Sensor Networks, IEEE Transactions on Mobile Computing, v.4 n.3, p.297-309, May 2005
Tian He , Brian M. Blum , Qing Cao , John A. Stankovic , Sang H. Son , Tarek F. Abdelzaher, Robust and timely communication over highly dynamic sensor networks, Real-Time Systems, v.37 n.3, p.261-289, December  2007
Niki Trigoni , Yong Yao , Alan Demers , Johannes Gehrke , Rajmohan Rajaraman, WaveScheduling: energy-efficient data dissemination for sensor networks, Proceeedings of the 1st international workshop on Data management for sensor networks: in conjunction with VLDB 2004, August 30-30, 2004, Toronto, Canada
Jian Li , Prasant Mohapatra, Analytical modeling and mitigation techniques for the energy hole problem in sensor networks, Pervasive and Mobile Computing, v.3 n.3, p.233-254, June, 2007
Zoltn Vincze , Dorottya Vass , Rolland Vida , Attila Vidcs , Andrs Telcs, Adaptive sink mobility in event-driven multi-hop wireless sensor networks, Proceedings of the first international conference on Integrated internet ad hoc and sensor networks, May 30-31, 2006, Nice, France
Niki Trigoni , Yong Yao , Alan Demers , Johannes Gehrke , Rajmohan Rajaraman, Wave scheduling and routing in sensor networks, ACM Transactions on Sensor Networks (TOSN), v.3 n.1, p.2-es, March 2007
Alan Demers , Johannes Gehrke , Rajmohan Rajaraman , Niki Trigoni , Yong Yao, The Cougar Project: a work-in-progress report, ACM SIGMOD Record, v.32 n.4, December
Brian Blum , Prashant Nagaraddi , Anthony Wood , Tarek Abdelzaher , Sang Son , Jack Stankovic, An entity maintenance and connection service for sensor networks, Proceedings of the 1st international conference on Mobile systems, applications and services, p.201-214, May 05-08, 2003, San Francisco, California
Taejoon Park , Kang G. Shin, LiSP: A lightweight security protocol for wireless sensor networks, ACM Transactions on Embedded Computing Systems (TECS), v.3 n.3, p.634-660, August 2004
S. Subramaniam , T. Palpanas , D. Papadopoulos , V. Kalogeraki , D. Gunopulos, Online outlier detection in sensor data using non-parametric models, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
Xiang-Yang Li , Wen-Zhan Song , Weizhao Wang, A unified energy-efficient topology for unicast and broadcast, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany
two-tier model;sensor networks;sink mobility