Information Technology Reference
In-Depth Information
developed an energy efficient weighted MST algorithm- Simple Weighted
Spanning Tree (SWST), and analyzed and compared it with the two above
mentioned algorithms.
Dynamic Global Topology Recreation (DGTRec) was implemented as the
topology maintenance protocol that will recreate the reduced topology at
predefined time intervals. The simulation results show improvements in network
load balancing after utilization of the proposed SWST algorithm. The SWST
algorithm has many advantages such as being easily scalable and distributed in
nature as well as exhibiting increased load balancing and simplicity. The rest of
the sections are organized as follows: Related Work is discussed in section 2,
section 3 proposes the Simple Weighted Spanning Tree (SWST) algorithm,
section 4 includes the Performance Evaluation and the last section is the
Conclusion.
2
Related Work
Distributed algorithms for topology construction (TC) in WSNs utilize and require
significantly less hop information than centralized algorithms. There are two
commonly employed methods for distributed algorithms- cluster head technique
and connected dominating set (CDS) technique. For the latter approach,
determination of minimum connected dominating set (MCDS) is one of the most
important tasks to build the communication backbone [6]. Much research has been
published in the literature that addresses this problem [7-14]. Many proposed
algorithms construct the topology by first creating a preliminary CDS and adding
or removing nodes to or from the set to create an approximate MCDS [5, 15]. Two
energy efficient CDS based topology construction protocols- CDS-Rule-K and
Energy Efficient CDS (EECDS) were discussed in [11, 14]. Also, Euclidian
Minimum Spanning Tree (Euclidian MST) and Random Nearest Neighbor Tree
(Random NNT) was proposed in the literature to construct low-cost spanning tree
in WSNs [1].
A. Random Nearest Neighbor Tree
: The Nearest Neighbor Tree algorithms
avert many of the issues resulting from the overhead produced by the Minimum
Spanning Tree by picking a unique rank and making a node connect with a node
of higher rank [1]. In fact, it is in many ways similar to an approximation
algorithm for solving the Traveling Salesman problem in [2, 3]. The Random
NNT is an effective method to create a low cost spanning tree. In this algorithm,
nodes pick a random rank between 0 and 1 and connect to the closest node of
higher rank [1]. To start the topology construction, a predefined node begins
broadcasting messages. All nodes that receive a broadcasted message will send an
acknowledgment message to the sender. The sender node will connect to recipient
node since it possesses higher rank than the sender. As the next step, the recipient
node broadcast messages. This is then repeated in the network at every node
Search WWH ::
Custom Search