Database Reference
In-Depth Information
3. Topologies of WSNS
The connectivity graph is a common tool to represent the connec-
tions between sensors of a WSN. A WSN consists of a set of sensors,
V
, each of which acts as a node of the graph. We hereupon use the
terms sensor and node interchangeably. A node
n
i
∈
V
connects to
another node
n
j
∈
V
if
n
j
is within the radio range of
n
i
,thatis,
n
i
directly communicates with
n
j
. For such pair of nodes, we add an edge
e
i,j
from
n
i
to
n
j
. The set of sensors along with the connections con-
sist the connectivity graph
G
=
<V,E>
of the network [38]. In most
applications, the sensors are of the same type and have the same radio
range. Thus, the connectivity between
n
i
and
n
j
is bidirectional. For
simplicity, it is a common practice to treat the connectivity of a WSN
as an undirected graph. A naive approach for message transmitting
is called flooding. In flooding, whenever a node receives a message, it
broadcasts the message to its neighbor sensors (i.e., sensors are within
the radio range). However, this simple approach is extremely energy
consuming due to the large amount of redundant transmissions. In or-
der to facilitate effective messages transmission, the network protocols
organize WSNs into certain topologies. Network protocols for WSNs
follow various approaches depending on the desired trade-off between
communication overhead and robustness. There are mainly three types
of topologies: the tree-based topology, the multi-path-based topology
and the hybrid topology. In tree-based topologies [4 13], every pair of
nodes communicate through a single path. This minimizes the trans-
mission cost, but is very sensitive to packet loss and node failures, which
happen frequently in WSNs. Specifically, when a transmission or a node
fails, the data from the corresponding sub-tree are lost. On the other
hand, multi-path-based topologies [12 14] allow a message to propagate
through multiple paths until it reaches the base station, so that even if
it gets lost in one path, it is able to be successfully delivered through
another one. The trade-off is the higher communication cost and possi-
bly duplicated results compared to the tree-based approaches. Hybrid
approaches [9] organize part of the WSN (e.g., reliable nodes with stable
communication links) using a tree-based topology, and the rest accord-
ing to a multi-path approach. In the following, we discuss the three
kinds of topologies in Sections 3.1, 3.2 and 3.3, respectively.
3.1 Tree-Based Topology
Given the connectivity graph
G
, a tree-based topology [4][13] con-
structs a spanning tree
T
of
G
rooted at the base station. The base
station acts as the data sink and the entrance of the network. On re-
