An Approach to Construct Weighted Minimum Spanning Tree in Wireless Sensor Networks - Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing - page 69

The next section will discuss the Simple Weighted Spanning Tree (SWST)
algorithm.

3 The SWST Algorithm

The proposed Simple Weighted Spanning Tree (SWST) algorithm builds a
weighted Minimum Spanning Tree in which the weight is one of the following:
parent node or children node energy level; or the Euclidian distance between
parent and children nodes. Due to parent nodes exhibiting a closer proximity to the
sink node (lower hop numbers), parent nodes will transmit messages more often
on average during a sensing event resulting in the parent nodes more likely
depleting their energy resources before children nodes (higher hop numbers) will.
The proposed SWST algorithm mainly focuses on load balancing among parent
nodes. In this SWST protocol, children nodes choose parent nodes exhibiting the
highest energy level. For this reason, parent nodes will enable the network to run
for a more extended period of time until the topology maintenance (TM) protocol
starts. Each node has a threshold energy level associated with it; if the node
energy falls under this threshold, the node tends to utilize Euclidian MST protocol
in order to increase its own node life. The energy consumed to transmit decreases
due to the reduced transmission range of the transceiver. After a node chooses its
final parent, its transmission range will be set to the Euclidean distance between
the final parent node and itself.
However, if the energy level of the child node is more than the maximum
energy level of the parent nodes for the child node, energy weighted MST will be
utilized instead of Euclidian MST protocol. This is due to the fact that it is better
to have more energy in the parent nodes than the children nodes when using the
SWST algorithm. If children nodes exhibit higher energy levels, the parent nodes
will deplete energy sooner and produce an unconnected link in the communication
backbone. In that case, children nodes will not be able to communicate with the
sink node and thus, a child node will attempt to choose the strongest node even if
that depletes its own resources.
Sink node: A sink node has significantly more energy and longer transmission
range than the ordinary sensor nodes. In the TC phase, sink nodes set their
transmission range equal to the range of ordinary nodes since child nodes that
exhibit a shorter transmission range would be incapable of transmitting messages
directly to the sink node if the distance from the child node to the sink node is
further than the child node's own transmission range. During topology
maintenance, the sink node switches its transmission range to the highest level to
initiate the maintenance protocol in all ordinary nodes within the maximum
transmission distance of the sink node. This description assumes all nodes are
within the sink node's maximum transmission range.
Active nodes: Active nodes possess energy levels sufficient to perform sensing
and communication. These nodes actively listen for message delivery request and
sense the environment for an event of interest. They deliver messages for events of