ENERGY EFFICIENT

ROUTING IN WIRELESS
SENSOR NETWORKS

Authors:
Author Name Roll Number
M Ashwinth Anbu CS22B2055
Kathiravan S CS22B2052

Date: April 25, 2024

Contents
1 Introduction 2

2 Problem Statement 2

3 Proposed Methodology 3

4 A-star Algorithm 4

5 Simulated Annealing 5

6 Experimental Setup 7

7 Results 8
7.1 A-star . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
7.2 Simulated Annealing . . . . . . . . . . . . . . . . . . . . . . . . . 9

8 Individual Contributions 9

9 Conclusion 9

10 References 10

1
1 Introduction
Wireless Sensor Networks (WSNs) are networks of small, smart devices called
sensors scattered across different locations. These sensors constantly monitor
various things like temperature, humidity, or movement in their surroundings.
They communicate wirelessly with each other, sending the data they collect to
a central hub. WSNs have numerous applications, such as environmental moni-
toring, agricultural tracking, and industrial supervision. They are cost-effective
and provide real-time data even in remote areas, making them valuable tools
for efficient monitoring and management.

In Wireless Sensor Networks (WSNs), a routing protocol is a set of rules that

guides how data travels from one sensor node to another and eventually to a
central hub. These protocols determine the most efficient path for data trans-
mission, considering factors like node energy levels, network topology, and com-
munication reliability. By intelligently directing data flow, routing protocols
optimize network performance and conserve energy, extending the network’s
lifespan. They play a crucial role in ensuring reliable and timely data delivery
in WSNs.

2 Problem Statement
Since energy sources are scarce and constrained and batteries are low-powered,
energy-efficient data forwarding is supposed to be a critical challenge in WSN
applications. Energy consumption should be managed so that network lifetime
of WSNs is significantly prolonged. On the other hand, the majority of rout-
ing algorithms in WSNs require reliable and real-time data forwarding to the
sink node in many-to-one [Link], energy-efficiency and QoS-based data
routing are considered as a crucial challenge in WSNs and there is a trade-off
between energy-efficiency and QoS parameters. On the other hand, non-uniform
energy consumption and load unbalancing are vital problems in many routing
protocols of WSNs which result in network partitioning. Consequently, network
partitioning has a negative impact on the successful packet delivery to the sink
and hence it hinders the performance and the proper function of WSNs. With
regard to the significance of WSNs’ applications, reduction in the packet de-
livery ratio will have a negative impact on the energy consumption and hence
network lifetime of WSNS.

On the other hand, non-uniform energy consumption and load unbalancing are
vital problems in many routing protocols of WSNs which result in network
partitioning. Consequently, network partitioning has a negative impact on the
successful packet delivery to the sink and hence it hinders the performance and
the proper function of WSNs. With regard to the significance of WSNs’ ap-
plications, reduction in the packet delivery ratio will have a negative impact
on the energy consumption and hence network lifetime of WSNS. In WSNs,

2
transmission and reception of data packets are considered as the chief sources
of energy consumption. As a result, to design energy-aware routing protocols
for WSNs, we must efficiently control and manage energy consumption. Due
to many-to-one traffic scheme, lack of energy consumption management will re-
sult in the quick loss and destruction of energy resource of the nodes near the
sink; this is referred to as energy hole problem. In the majority of routing algo-
rithms, the periodical choice of the optimal path and the energy hole problem
together impact on the life time of WSNs. As a result of these two problems,
the network will be partitioned and the WSN will not be able to accomplish its
intended critical function. The major problem in such routing protocols is that
they minimize total energy consumption at the expense of non-uniform energy
drainage in the network.
The following parameters should be taken into consideration:
• Energy consumption balancing
• Load balancing

• Selection of the shortest path

• Reducing packet retransmission with concern to packet reception rate
Our main objective is to come up with an algorithm such that it accurately
determines the most energy efficient path from the source to [Link]
and reception of data packets are considered as chief sources of energy consump-
tion. If the routing protocol in a Wireless Sensor Network is energy-efficient,
then the total residual energy of all the nodes in the network after successful
transmission of data from source to sink is maximum. Taking the energy effi-
cient path will result in maximum residual energy of all the nodes in the network
which will significantly prolong the network lifetime.

3 Proposed Methodology
We tried to approach this problem in two different ways:
• Heuristic based A-star algorithm

• Probablistic Simulated Annealing

The reason for choosing A-star is that it arrives at the optimum in just one
iteration. If the heuristic function gives a reasonable estimate of the cost, then
arriving at the optimal solution is almost guaranteed. Traditional algorithms
like Breadth First Search (BFS) and Depth First Search (DFS), on the other
hand, take a lot of time exploring all possible paths. A-star outperforms both
of these algorithms when the heuristic is accurate.

The reason for choosing Simulated Annealing is its probabilistic nature. Con-
sider a large network consisting of hundreds of nodes. In this case, the heuristic

3
function might not always give a good estimate of the cost. So, in such cases,
A-star algorithm has a high chance of failing. But Simulated Annealing works
well when the number of entities involved is large. It is obvious because is
such scenarios the algorithm can explore a larger range of solutions and has less
chance of getting struck at local optima.

4 A-star Algorithm
Our goal is to find the optimal path from the source node to the destination
node (base station) with regard to some parameters of sensor nodes such as
residual energy, packet reception rate (PRR) and node buffer state. In order
to find the optimal path, the sink node should be aware of the criteria of each
node. Thus, at the initial phase, each node must send its aforementioned pa-
rameters to the sink node. In the remaining round, if the sensor node has data
to send toward the sink node, it will append its parameters to the data packet.
Based on the gathered parameters, the sink node must determine and broadcast
the routing schedule to each sensor node. Then, A* algorithm will search for
the optimal path from the source node to the destination node. If the residual
energy of sensor node is less than the energy threshold value , that node cannot
participate in the routing process and hence will not send its parameters to the
base station. The network load will be balanced with regard to the threshold
value of the energy, and as a result, the network lifetime will be enhanced.

A-star uses a distance plus cost heuristic function of node n, f (n) to determine
the order in which the search visits nodes in the tree. The heuristic function is
a sum of two functions as follows:

f (n) = g(n) + h(n)

Where g(n) is the cost from the source node to the current node n and h(n) is an
admissible heuristic estimate of the distance from the node n to the destination
node.

Our intention is to forward data packets to the next neighbour node which
has higher residual energy, higher free buffer, and higher packet reception rate.
To achieve this, we made use of aggregated weight of the above-mentioned rout-
ing parameters. Here, we define the aggregated weight of a next neighbour node
as the sum of normalized weights of its routing metrics as follows:
n o
Bf (n)
g(n) = M ax α E res (n) Nr (n)
Eini (n) + β Nt (n) + γ Bini (n)

Where Eres (n) and Eini (n) are residual and initial energy of node n respec-
tively. In addition, Nr (n) and Nt (n) are the number of transmitted and received
packets [Link] (n) and Bini (n) referred to the number of free and initial

4
buffer of node n respectively. α, β and γ are weight parameters and α + β + γ
=1

The first parameter includes normalized residual energy which illustrates the
residual energy of the next neighbouring node n. This parameter is aimed to
ascertain that the sensor nodes’ energy consumptions are balanced. Energy load
must be evenly distributed among all the sensor nodes in order to prolong the
network lifetime. The second parameter is called normalized number of received
packets in n node. This metric corresponds with the packet reception rate of the
next node. In other words, maximizing this metric is equal to maximizing the
packet transmission efficiency. As a result of taking this metric into account,
the majority of the probability and hence this will prevent the retransmission
of data packets which will significantly reduced the amount of energy consump-
tion in the node. The third parameter stands for the magnitude of the available
free buffer at the next neighbouring candidate, node n this parameter plays the
remarkable role in the proper distribution of traffic load. The packet will be
sent to the next node which has the maximum free buffer.

The value for the heuristic function h(n) can be calculated as follows:
1
h(n) = min(hc s)
n

Where, min(hcsn ) is the minimum hop count from node n to the destination
node. In order to compute the minimum hop count from node n to the sink
node, we must calculate the distance between node n and sink node via eu-
clidean distance formula as follows:
p
d(n, s) = (xn − xs )2 + (yn − ys )2

Where, ¸d(n, s) is equal to the Euclidian distance between the node n and sink
node. Moreover, the hop count from node n to the sink node can be calculated
as follows:
d(n,s)
hcsn = avg(d(n,j))

Where, avg(d(n, s)) is the average distance between the node n and its one
hop neighbouring nodes (j). Thus, for choosing the optimal path, we will select
that node n which has the maximum evaluation function, f (x). The value of
f (x) can be used to obtain the optimal path.

5 Simulated Annealing
Simulated annealing (SA) is a probabilistic technique for approximating the
global optimum of a given function. Specifically, it is a metaheuristic to approx-
imate global optimization in a large search space for an optimization problem.
For large numbers of local optima, SA can find the global optima. It is often

5
used when the search space is discrete. For problems where finding an approx-
imate global optimum is more important than finding a precise local optimum
in a fixed amount of time, simulated annealing may be preferable to exact al-
gorithms such as gradient descent or branch and bound.
It follows the below steps to arrive at the optimum:

• Start from an initial point

• Repeatedly consider various new solution points
• Accept or reject some of these solution candidates
• Converge to the optimal solution

Algorithm:
Let the objective function be F (x)
• Initialize the initial temperature T0 and initial guess X = X 0 and i = 0
• Set the minimum temperature Tmin and max number of iterations N, and
cooling rate α
• Define cooling schedule T −→ b αT
• While (T < Tm in and i < N )
– Move randomly to new locations X (i+1) = X (i) + rand
– Calculate ∆f = f (i+1) − f (i)
– Accept the new solution if better i.e. f (i+1) < f (i)
– If not improved i.e. f (i+1) > f (i)
∗ Generate a random number r
∗ Accept if p = exp( −∆f
T )>r
– End if
– Update the best X and f
– i=i+1
• End While
Our main goal is to maximize the residual energy of the network after successful
transmission of the data [Link], the objective function, F (x) in this scenario
is the sum of residual energy of all the nodes in the network. We set the
temperature at 1000 and cooling rate to be 0.1. Initially we randomly select a
source to sink path. Then at each iteration we randomly flip some nodes in the
path and accept/reject it based on the residual energy of the network if that
path was taken.

6
6 Experimental Setup
Here we discuss the representation of the Wireless Sensor Network in our sim-
ulation. The network is assumed to be a Directed Graph with sensor nodes as
vertices. The entire network is represented as a dictionary of dictionaries where
the key is the number of the node and value is a dictionary of the node’s param-
eters. We have considered the following parameters of nodes in our simulation:

• Position - Represented as a tuple of two values x and y

• Neighbors - Represented as a list where each entry denotes an adjacent
node
• Initial Energy - The initial energy of the node when the network was
deployed
• Residual Energy - The residual energy of the node
• PRR - The Packet Reception Ratio of the node
• Buffer Capacity - The total buffer capacity of the node

• Free Buffer - Amount of Buffer space available

• Data packet - The data packet which is transferred through this node
• PTR - The Packet Transmission Ratio of the node

7
7 Results
We created a network of 25 nodes and executed both A-star algorithm and Sim-
ulated Annealing in this network. Both the algorithms gave promising results.
This is the Wireless Sensor Network: In this figure, the leftmost node(node 1)

Figure 1: The Wireless Sensor Network

is the source node and the rightmost node(node 25) is the sink node.
Our results are elaborated below:

7.1 A-star
We implemented A-star algorithm to find the energy efficient routing in the
above network and it gave near-optimal [Link] path chosen by this algo-
rithm is:

1 −→ 5 −→ 10 −→ 15 −→ 20 −→ 24 −→ 25

The initial energy of the network before the simulation is 1676 and the final
residual energy after the transmission of the data packet is 1435.8847. This is
very close to the optimal path which is:

1 −→ 3 −→ 7 −→ 12 −→ 18 −→ 23 −→ 25
The residual energy of the network if this path was taken : 1435.9331

Hence we can say that A-star algorithm, although not always gives the opti-
mum solution but it gives a solution which is very close to the optimal solution

8
7.2 Simulated Annealing
We also implemented the Simulated Annealing algorithm to find the energy ef-
ficient routing in the above network. The initial temperature was set to 1000
and the cooling rate is 0.95. It arrived at the optimal solution in 270 iterations.
This is the path given by the Simulated Annealing Algorithm:

1 −→ 3 −→ 7 −→ 12 −→ 18 −→ 23 −→ 25

The residual energy of the network if this path was taken is 1435.9331 which is
the optimal solution. Hence we can say that Simulated Annealing indeed arrives
at the optimal solution.

8 Individual Contributions
Kathiravan’s Contributions:

• Ideation and implementation of Simulated Annealing.

Ashwinth Anbu’s Contributions:
• Data simulation, implementation of A-star algorithm and documentation.

9 Conclusion
In this project, we have addressed the crucial issue of energy-efficient routing
in wireless sensor networks (WSNs) by employing the A-star algorithm and
simulated annealing. Our primary objective was to develop routing strategies
that minimize energy consumption while maintaining effective data transmission
within the network.
Through the implementation and evaluation of the A-star algorithm and
simulated annealing, we have achieved promising results in enhancing energy
efficiency in WSNs. The A-star algorithm, known for its efficiency in finding
optimal paths, provided a reliable framework for routing decisions, optimizing
energy consumption by selecting paths with minimal energy requirements. Ad-
ditionally, the application of simulated annealing allowed for the exploration of
alternative routing solutions, enabling the network to adapt to changing envi-
ronmental conditions and network dynamics.
In conclusion, our project underscores the importance of energy-efficient
routing strategies in WSNs and presents a viable solution using the A-star al-
gorithm and simulated annealing. Moving forward, further research and ex-
perimentation could explore optimization techniques, scalability considerations,
and real-world deployment scenarios to advance the practical applicability of
energy-efficient routing in WSNs.

9
10 References
Our work is inspired from the research paper titled ”An Energy Efficient Routing
Protocol for Wireless Sensor Networks using A-star Algorithm” by Ali Ghaffari.

The paper can be found here: An Energy Efficient Routing Protocol for Wire-
less Sensor Networks using A-star Algorithm

This paper foucses on determining the routing protocol using A-star algorithm.
We thought of improving this algorithm for large networks by proposing a hy-
brid algorithm that used both A-star algorithm and Simulated Annealing to
find the energy efficient routing.

10