Database Reference
In-Depth Information
Figure 3.1.
Network topologies
most of the data processing techniques do not depend on the specific
routing tree. Instead, the resulting network should have the following
two properties:
1 It should be able to deliver query requests to all nodes in the
network.
2 It should be able to transmit data from every node to the base
station.
TinyDB [7], TAG [13], CONCH [10] and HAT [11] are based on the tree-
based topologies. In addition, some algorithms require that the routing
protocol generates no data duplication during transmission [13].
3.2 Multi-Path-Based Topology
In a multi-path-based topology [12], each node has multiple children
and parents. A sensor receives data from its children, processes the data
and broadcasts the partial results to all its parents. Consequently, a
message reaches the base station through multiple paths, increasing the
possibility for data to be successfully delivered. However, if several copies
of a reading reach the base station through different paths, duplication
arises and the algorithm has to take care of it. A popular multi-path-
based topology is Rings [14], where each node works in a certain level.
The topology is constructed iteratively starting from the base station
n
0
, which is in level
l
0
= 0. To initiate the construction procedure,
n
0
broadcasts a signal
m
0
, which contains the level information of itself,
i.e.,
m
0
.level
=0. Onhearing
m
0
, a node
n
i
checks the level
l
i
of itself.
If
l
i
has not been assigned yet,
n
i
assigns
l
i
as
m
0
.level
+ 1, i.e., one
level lower than its parent. Otherwise,
l
i
is already assigned,
n
i
sets
l
i
to
min
, i.e., to be as close to the base station
n
0
as
possible. After updating its level information,
n
i
broadcasts a signal
q
i
with
q
i
.level
=
l
i
to its neighborhood. This procedure keeps propagating
until the level information of all nodes is stable. As a result, each node
{
l
i
,m
0
.level
+1
}
