Database Reference
In-Depth Information
n
i
is in a level whose value equals to the minimum number of hops
from
n
i
to
n
0
. This is called minimum-hop routing [39]. If there is a
fixed packet loss rate for each hop, minimum-hop routing minimizes the
message losses.
Figure 3.1(b)
shows an example of the Rings topology.
As before, the black node represents the base station while other nodes
are sensors. We omit the physical connections and only present the
connections maintained in the routing protocol. The sensors are divided
into two levels, which are represented by different gray scales. In order
for
n
i
to transmit a message
m
i
to
n
0
, it attaches its level information
along with
m
i
, i.e.,
m
i
.level
=
l
i
, and broadcasts
m
i
. A node
n
j
hears
m
i
checks whether
l
j
equals to
m
i
.level
1. If so, it is one of the parents of
n
i
and broadcasts
m
i
after setting
m
i
.level
to
l
j
; the process is repeated
until
m
i
eventually reaches
n
0
through multiple paths.
−
3.3 Hybrid Topology
In a network with high link quality, trees are preferable to multi-path
topologies because of their energy eciency. On the other hand, if the
network suffers low link quality, it is better to use a multi-path-based
topology for robustness. Manjhi et al. [9] propose a hybrid topology,
called the Tributaries and Deltas, which adjusts the topology in different
areas of the network according to the local link qualities. The motiva-
tion is to reduce energy consumption in low-packet-loss-rate areas, while
increasing robustness in high-packet-loss-rate areas.
Figure 3.1(c)
shows
an example of the Tributaries and Deltas topology. The black node
represents the base station while gray ones correspond to sensors. The
nodes located in the gray area apply a multi-path-based topology, while
the rest form trees. The overall network topology is a directed graph,
where the direction of an edge agrees with the direction of the data flow,
i.e., from outer nodes towards the base station. The nodes labeled with
T (resp. M) run the tree-based (resp. multi-path-based) topology. An
edge is assigned with the same label as its source node. Generally, trees
incur no duplicate data transmissions, as opposed to multi-path-based
topologies. In order to ensure the correctness of the aggregation results,
the authors propose two constraints:
Edge Correctness: An
M
edge can never be incident on a
T
vertex,
i.e., an
M
edge is always between two
M
vertices.
Path Correctness: In any path in the directed graph, a
T
edge can
never appear after an
M
edge.
The two constraints are actually equivalent. Either of them ensures
that a multi-path partial result can only be received by a node in the
