Distributed Algorithms for

constructing spanning trees in wireless sensor networks

Introduction

A Wireless Sensor Network (WSN) is a

particular ad hoc network which is composed of many sensor nodes and a base

station or sink. The sensor nodes are deployed in a sensing field to collect

data and information from the supervised environment. The data collected from

sensor nodes are transferred to the sink via multi-hop communication.

The most important constraints in a

WSN are energy constraint and data collection. Therefore, researches investigate

the data routing in WSN to maximize the network lifetime and improve the data

collection process considering the limited computational resources of the

sensor nodes.

For data traffic, trees are

classical structure wildly used in WSN. In tree structure, sensor nodes need to

transfer the data collected to their parent and parents do the same until the

data reach the root which is the sink in the case of WSN. Using this structure avoids sensor nodes to

process frequently the route discovery mechanism and maintain the routing

tables to store all routing paths.

In the literature, there are some

distributed algorithms for constructing spanning trees in WSN such as Shortest

Hop Multipath (SHP) , Distributed Bellman Ford (DBF) , Depth First Search

(DFS) B, Efficient Bellman Ford

(EBF) .

Wireless Sensor Networks and challenges

A WSN is composed of a set of

autonomous sensor nodes deployed in a sensing area with the purpose of monitor

physical or environmental conditions such as temperature, pressure, movements,

sounds or video surveillance and it is composed of a special node in the

network called the sink or the base station which has the role of collect the

data or the information captured by the sensor nodes, hence, a WSN is also can

defined as self-configuration network.

Figure 1. architecture of a WSN

Sensor nodes in WSN are inherently

resource constrained. They have some limitations such as the computational

resources because they have a limited processing speed, limited communication

bandwidth, small capacity of storage and a limited energy.

The limited resources and

constraints of WSN make this kind of networks subject to several challenges especially for

transferring and routing data to the sink or the base station.

Maximizing

the life time of the network is an important challenge in WSN since the sensor

nodes has a limited energy and they are usually non-renewable. Therefore,

researches investigate in designing protocols suitable with WSN such as the

routing protocols. The routing protocols can consume an important part of the

network energy due to the configuration of routing protocol and the message

exchanged for that.

Another challenge is the fault

tolerance. Sensor nodes are vulnerable and prone to failure because of their

limited energy, they exhausted their batteries, or they deployed in dangerous

area, in some application, thus, the protocols designed for WSN especially the

routing protocols, should be able to deal with this issue in order to insure

the connectivity and reliability of the network by providing alternative

routes.

The scalability of routing protocols

is also an important challenge for WSN. The routing protocols deployed in

sensor networks need to be scalable and adaptive to the change in the WSN

topology and for the large-scale networks.

Spanning Trees

Constructing spanning tree is a

classic structure wildly used for routing the data and the information

collected by sensor nodes to the sink in WSN. In the literature, there are some

distributed algorithms for constructing spanning trees in WSN such as Shortest

Hop Multipath (SHP) , Distributed Bellman Ford (DBF) , Depth First Search

(DFS) B, Efficient Bellman Ford

(EBF) .

In the context of WSN, spanning tree

are rooted at the sink such that the cost of link or the path from any sensor

node in the network to the sink is the minimal 1. There are also some other

metrics used to calculate the cost of links in the literature 1 such the

number hops, the distance to the sink, energy dissipation, remaining energy,

the message queue length, the link quality etc.

Shortest Hop Multipath

The algorithm Shortest Hop Multipath

proposed in is a synchronized distributed algorithm used in WSN. The

proposed algorithm uses five types of messages probe, acknowledgment (ack),

pulse, pulseAck, and pulseNack. The algorithm considers the number of hops to

the sink as the cost of the links.

The sink is responsible for initializing

and finalizing the spanning tree construction, which is performed in layers.

The sink starts the constructing of the tree by broadcasting a message probe to

offer its paternity to its possible neighbors and then waits for the

acknowledgment message (ask) from each sensor node received its paternity offer

and accepts it. When the sink receives all expected ack messages, it broadcasts

a pulse message to inform which layer must offer paternity.

For the other sensor

nodes that offer paternity by sending the probe message wait for the ack

message from sensor nodes that accept paternity offer. After they receive the

ack messages from their children they unicast a messages pulseAck to their

parents. Sensor nodes that have not possible children do not offer paternity

and they unicast a message pulseNack to their parents. If a node

receives only pulseNack messages from its children as a reply for a pulse

message, it unicasts a pulseNack message to its parent. Otherwise, the node

unicasts a pulseAck message to its parent. These messages (pulseAck and

pulseNack) are relayed from parent to parent, until they reach the sink.

When the sink receives only pulseNack

messages from its children as a replay for a pulse message, the sink determines

the termination detection of the constructing tree process. While the algorithm is executed, sensor nodes

construct a set of alternative parents to be used for fault tolerance or load

balancing.

Figure 2 shows the behavior of the

proposed algorithm in Shortest Hop Multipath while it constructs the

spanning tree.

Figure 2. Shortest Hop Multipath

Cost

The time complexity and message complexity

of this algorithm are O(D2) and O(V.D+V) respectively, where D is

the diameter of the network from the sink to the furthest sensor node in the

network and V is the node count of the network .

Depth First Search

Depth First Search algorithm

proposed in B can be used for constructing spanning trees in WSNs. The

Depth First Search algorithm uses two types of messages Forward and Return to

build the spanning tree. These messages contain the set of the sensor nodes

that have been visited by the algorithm. This algorithm does not have a

specific metric to build the spanning tree.

The sink starts the tree

construction by sending a message Forward to its one of its neighbors

containing the set of the its children sensor nodes i.e. this message contains

the set of the visited nodes by the process of constructing the tree. When a

sensor node i receives a Forward message containing the set of the visited

sensor nodes from a neighbor sensor node j, it selects this sensor node j as its

parent and it adds itself to the set of the visited sensors, then it sends Forward

to its parent in the case of all its neighbors have been visited. Otherwise, it

propagates the algorithm to one of its neighbors that has not yet been visited

and update its children set by adding this unvisited sensor node to it.

When a sensor node i receives

a Return message containing the set of the visited sensor nodes and all its

neighbors have been visited, it claims the global termination if it is the sink

or else it continues forwarding the message Return to its parent until the

message reach the sink. In the case where there still some neighbors of a

sensor node i have not yet visited, it selects a sensor node from them, propagates

the Depth First Search by sending Forward message containing the visited set to

it and adds the unvisited sensor node to its children set.

Cost

The time complexity and message complexity

of this algorithm are O(V), where V is the number of sensor nodes in the

network .

Distributed Bellman Ford

The Distributed Bellman Ford

algorithm is classical asynchronized algorithm to construct spanning trees .

This algorithm uses the distance as a metric to build the spanning tree. The

basic idea of the Distributed Bellman Ford algorithm is to the minimal cost of

link in term of distance from any sensor node in the network to the sink.

Before starting the construction of

the spanning tree, the weight of the sink is equal to zero and the weight of

any sensor nodes i in the network to the sink is infinite. The weight of paths

is calculated in each iteration for constructing the spanning tree in the following

equation:

Where is the set of the sensor nodes in the WSN, is the weight of the sensor node i in the

iteration t and is the cost of the link between i

and j.

The sink initiates the constructing

of the spanning tree by broadcasting a message containing its identification

and its weight to its neighbors. When a sensor node i receives a message from a

sensor node j, it calculates the cost of the path to the sink passing by the

sensor node j. If the cost of the path passed by sensor node j is less than the

current cost of path at the sensor node i, then the node i selects j as its

parent and update its weight then broadcasts it to its neighbors.

Cost

The time complexity and message complexity

of this algorithm are O(D) and O(E.D) respectively, where D is the diameter of

the network from the sink to the furthest sensor node in the network and E is the

number of edges or connections between sensor nodes in the network.

Efficient Bellman Ford

Efficient Bellman Ford algorithm is

an asynchronous distributed algorithm based on the basic Distributed Bellman

Ford algorithm . This algorithm is proposed in . The authors of adds two

strategies to the first algorithm, the first strategy is the advantage factor

?, where ? is 0 < ? < 1. This factor is
used to determine how much a new offer of paternity a sensor node i received it
from a sensor node j, must be more or equal to the factor ? to the sensor node i accepts the sensor node j as a parent. In other
word, the cost of the path offered by the sensor node j must be at least ?% minimal than the current cost at the sensor node i, where . The second
strategy is the alternative parents set, the authors of inspired this
strategy from in order to provide multiple path for the data transfer to the
sink. Since the proposed algorithm in is based on the basic algorithm of Distributed
Bellman Ford in , the Efficient Bellman Ford has the same initial conditions
before the sink start the construction of the spanning tree, which are the
weight of the sink is equal to zero and the weight of any sensor nodes i in the
network to the sink is infinite.
The sink initiates the process of
the tree construction by broadcasting a message with its weight to its neighbors.
When a sensor node i receives a message from a sensor node j and i does not
have a parent so i selects j as its temporary parent and updates its weight
then broadcasts to its neighbors. In the other case, where the sensor node I has
already a parent and receives a new offer of paternity from a sensor node j,
the node I calculates the advantage of the node j offer, the advantage of a paternity offer is calculated as fellow:
Where is the advantage of the offer
paternity of sensor node j to the sensor node i and is the current weight of the
sensor node i, while the is the weight of sensor node j
plus the cost of the link between i and j.
If the advantage of the paternity offer
of the sensor node j is more or equal to the factor of advantage ? which means that the paternity offer is advantageous, the sensor
node i checks if j is its current parent. If j is not the current parent of i, i
adds its current parent to its alternative parents sent, selects j as its
parent and updated its weight then broadcasts it. In the other case, where the
offer of the sensor node j is not advantageous then the sensor node i adds j to
its alternative parents set. If a sensor node sends multiple offer of paternity
only the last one is stored at the node receiving these offers.
Cost
The complexity of time and message
of this algorithm are the same as the Distributed Bellman Ford algorithm
because in the worst case all the paternity offers received by the sensor node i
are advantageous then i broadcasts its new weight. Therefore, O(D) is the complexity
of time and O(E.D) is the complexity of message, where D is the diameter of the
network from the sink to the furthest sensor node in the network and E is the
number of edges or connections between sensor nodes in the network.
Analysis