10.4225/03/58a654f5a58e0
Abd Aziz, Azrina
Distributed connected dominating set techniques for energy-efficient topology control in wireless sensor networks.
2017
Monash University
monash:120449
thesis(doctorate)
Connected dominating set
1959.1/912948
Topology control
Open access
ethesis-20131127-134710
Wireless sensor networks
2012
2017-02-17 01:42:10
article
https://bridges.monash.edu/articles/thesis/Distributed_connected_dominating_set_techniques_for_energy-efficient_topology_control_in_wireless_sensor_networks_/4664107
Despite the considerable research efforts devoted to extending the lifetime of
wireless sensor networks (WSNs) by making them more energy efficient, there
are still a number of unresolved issues. Among the possible solutions for improving
their overall energy efficiency, topology control has significant potential.
Distributed topology control is a difficult problem, and optimal solutions are not
possible except for very simple topologies. Because of this, heuristic methods
are used, but the solutions proposed in the research literature are usually tested
with overly simplistic simulation models and consequently they fail to perform
satisfactorily in real networks.
The research project reported in this thesis proposes three new topology control
methods that are tested on highly realistic simulation models calibrated with data
collected on an experimental wireless sensor network. These models accurately
handle interference effects, realistic transmission ranges and imperfect communication
links. Additionally, the correctness of the proposed methods was verified
using theoretical analysis. Two leading algorithms were used as benchmarks.
Based on the outcomes of a thorough literature review and analysis of existing
techniques, distributed connected dominating set (CDS) approach was selected
as the starting point for the design of the proposed algorithms. The proposed
algorithms are not only distributed but also use localized information for computing
a CDS. Given that the CDS serves various tasks in a WSN, a fair load
distribution strategy was adopted to prolong the network lifetime. This strategy
takes into account the remaining energy levels at each node when choosing the
eligible CDS nodes.
The first topology control technique called the three-phase single initiator (TPSI)
was developed to form a small CDS for medium and dense networks (i.e., in
deployments when average node degree is relatively high) with minimal communication
overhead, computational complexity and energy consumption. The
simulation results demonstrate that the TPSI algorithm generates a small CDS
for both medium and dense networks but not for sparse networks. These results
also prove that the impact of network density on performance of an algorithm is
significant and cannot be ignored.
The second technique, single-phase single initiator (SPSI) on the other hand was
proposed for applications that require fast convergence, and is best suited to WSN
applications that have sparse topologies. The simulation results show that SPSI
can generate a small CDS for sparse networks using low message overhead and
energy consumption, and compute a CDS faster than the TPSI algorithm.
The third one, the Two-phase multiple initiator (TPMI) algorithm adapts well to dynamic
topology changes, thus it is suitable for applications that require frequent
topology updates. Instead of relying on a single initiator to construct the CDS as
in the TPSI and SPSI, the TPMI algorithm uses multiple initiators. The simulation
results show that although the CDS size of TPMI is larger than the ones generated
by TPSI or SPSI, it outperforms them in terms of energy consumption, network
lifetime and convergence time in networks with rapidly changing topologies.
Best suited algorithm for a particular installation can be selected manually, or by
using some measurement techniques, the structure of a network can be probed to
activate the optimal method automatically.