# Energy-Efficient Probabilistic Routing Algorithm for Internet of Things

Authors: Sang-Hyun Park; Seungryong Cho; Jung-Ryun Lee
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

In the future network with Internet of Things (IoT), each of the things communicates with the others and acquires information by itself. In distributed networks for IoT, the energy efficiency of the nodes is a key factor in the network performance. In this paper, we propose energy-efficient probabilistic routing (EEPR) algorithm, which controls the transmission of the routing request packets stochastically in order to increase the network lifetime and decrease the packet loss under the flooding algorithm. The proposed EEPR algorithm adopts energy-efficient probabilistic control by simultaneously using the residual energy of each node and ETX metric in the context of the typical AODV protocol. In the simulations, we verify that the proposed algorithm has longer network lifetime and consumes the residual energy of each node more evenly when compared with the typical AODV protocol.


---

## Body

## 1. Introduction

Internet of Things (IoT) is a network that enables new forms of communication between people and things and between things themselves. Each of the things or objects in IoT communicates with the others and plays a defined role [1–4]. In the future network with IoT, each node acquires information by itself, and humans only verify the information gathered [5]. IoT can be used in the fields of transportation, healthcare, smart environments, and so forth [1] and key network systems for communicating with things in IoT are radio-frequency identification (RFID) systems, wireless sensor network (WSN), and RFID sensor network (RSN).In such networks for IoT, nodes are distributed in a certain region for specific purpose and gather the required information, for example, the information about the temperature, motion, and physical changes [6–8]. The nodes forward the gathered information to the intermediate nodes because of the limited transmission range of the node [9, 10]. Therefore, the intermediate nodes use the unintended energy for the packet forwarding of the source node, which induces high energy consumption of the nodes and thus acceleratesnetwork partitioning. Therefore, the energy efficiency of the nodes is the key factor that affects the network performance in distributed networks for IoT [11–15].In addition, relaying information from a source to a destination is one of the most important tasks to be carried out in a large scale and dynamic IoT environment. The typical reactive routing protocols such as ad hoc on-demand distance vector (AODV) and dynamic source routing (DSR) are designed to find just the shortest path [16, 17] without any consideration of the energy consumption of a node. Thus a certain specific node can be selected repeatedly, which may decrease the lifetime of the node and thus cause network partitioning. Also, the reactive routing protocols use the flooding algorithm that forwards route request (RREQ) packets to its all one-hop neighbor nodes to find the routing path. Since excessive RREQ packets lead to mobile node battery run-out [8], it is required to limit the excessive transmission of RREQ packets.Algorithms to enhance the efficiency of the energy consumption have been widely proposed. In [18], the authors proposed an algorithm that controls the probability of forwarding RREQ packets according to the residual energy of the node, so the nodes having more residual energy are selected in the routing process. The authors of [19] proposed an energy-efficient routing protocol based on AODV protocol by considering the transmission power and remaining energy capacity of the mobile nodes. However, the above two methods do not consider the link quality of the route, which decreases the network lifetime by wasting the residual energy of the nodes with poor link quality. The authors of [20] proposed probability based improved broadcasting algorithm, which reduces the RREQ messages by using a broadcasting probability together with the consideration of the residual energy of nodes.On the other hand, most of the current routing protocols use hop count as their route selection metric to find the shortest path between source and destination nodes. However, using only hop count as the routing metric is not appropriate in IoT with dynamic network topology, since it is insensitive to packet loss, data rates, link capacity, link quality, channel diversity, interference, or various other routing requirements. Expected transmission count (ETX) [21] is a metric that aims to provide high throughput, by measuring the packet delivery ratio of the link between neighboring nodes.In this paper, we propose the energy-efficient probabilistic routing (EEPR) algorithm, which employs both the ETX metric and the residual energy of each node as the routing metrics at the same time. By using the ETX metric, the EEPR algorithm composes the routing path with good link quality. Using the residual energy of each node as a routing metric makes it possible for all the nodes in the network to use their residual energy more evenly. In addition, the EEPR algorithm controls the flooding of RREQ packets in an opportunistic way, so reduces the overhead in the routing process, and finds the energy-efficient routing path more efficiently compared to the typical protocols.


## 2. Proposed Algorithm

The proposed EEPR algorithm controls the request packet forwarding process in order to reduce the packet loss and network congestion in the context of the AODV protocol. A source node that has data packets to transmit forwards the RREQ packets to its one-hop neighbor nodes. In the typical AODV protocol, each node that receives a RREQ packet forwards it to all their one-hop neighbor nodes. On the other hand, a node does not forward the RREQ packet all the time but calculates the forwarding probability via the proposed forwarding probability formula and decides stochastically whether to forward or discard it.In this paper, we employ two different routing metrics. The first one is the ETX metric which presents the link quality between nodes. In general, probe packets are used to heuristically obtain the ETX value of a link [21]. Each node periodically broadcasts the small-sized probe packets to its one-hop neighbor nodes. The ETX metric is defined as
(1)ETX=1pq,
where p and q denote the forward packet delivery ratio and the reverse packet delivery ratio, respectively [21]. Notice that p and q are parameters obtained heuristically. Suppose that each node remembers the number of probe packets from the other nodes within w seconds. When each node periodically broadcasts the probe packets in τ cycles, the probe packet delivery ratio of one node at time t is defined as
(2)r(t)=count(t-w,t)w/τ.The denominator of (2) means the number of probe packets that one node has to receive in w seconds. The numerator of (2) means the number of probe packets that one node receives from (t-w) seconds to t seconds. Therefore, from (2), each node can calculate the delivery ratio by counting the number of probe packets. Each node periodically calculates the ETX metric between itself and the neighbor nodes and stores it.In this paper, we induce the ETX value metric not by using the heuristic method but by using the bit error rate (BER) based on the path-loss model. The received signal strength (RSS), the signal strength that the receiving node senses, is calculated as(3)RSSdB(x)=PdBmtx-PdBloss(x),
where RSSdB(x), PdBmtx, and PdBloss(x) are RSS at a node which is away x km from the source node (dB scale), transmission power of the source node (dBm scale), and path loss at x km from the source node (dB scale), respectively. Regarding the path loss model, we employ the ITU Ped A channel [22]. Then, signal-to-noise ratio (SNR) is calculated as
(4)SNR(x)=2×RSSW(x)PWnoise,
where SNR(x), RSSW(x), and PWnoise are SNR value at a node which is away x km from the source node, RSS at a node which is away x km from the source node (Watt scale), and noise power (Watt scale), respectively. By using the above SNR value, the BER is calculated with the assumption of the ITU Pedestrian A model [22]. Then the desired packet error rate (PER) is obtained as
(5)Epp=1-(1-Eb)Lpp,
where Epp, Eb, and Lpp are PER of a probe packet, BER, and the size of a probe packet, respectively.We calculate the ETX of each link by counting the number of probe packets that a node receives when the total number of probe packets is 10. The result of the ETX metric via distance is shown in Figure1.Figure 1
ETX metric via distance.In this paper, we defineETXi-1,i and ETXmax⁡ as the ETX value between node i-1 and node i and the maximum ETX value that a link may have, respectively.The second routing metric to be used in the proposed EEPR algorithm is the residual energy of a node which shows efficiency of the energy consumption in the network. We define the residual energy of nodei and maximum residual energy of node i as Ei, Emax⁡, respectively.Then, the forwarding probabilityp of node i under the proposed EEPR algorithm is determined by
(6)p=[pmin⁡+EiA[1+(ETXi-1,i-ETXmax⁡)(1-ETXmax⁡)]]1/α,A=1-pmin⁡2×Emax⁡,
where pmin⁡ and α are predefined minimum forwarding probability and the weighted factor for variation of the forwarding probability, respectively. From (6), when a node has high residual energy and the link has low ETX value, the forwarding probability is high. Even when a link has far lower ETX value because of good link quality, when the amount of residual energy of a node is small, the forwarding probability is low. Figure 2 shows the forwarding probability as functions of the ETX value and the residual energy when ETXmax⁡=45, α = 1, and pmin⁡=0.7.Figure 2
Forwarding probability via ETX and residual energy.When forwarder nodei is set to forward the request packets by using the forwarding probability p, node i forwards the request packets to its one-hop neighbor nodes similar to the typical AODV protocol. On the other hand, forwarder node i is not set to forward the request packet by using the forwarding probability p, and node i discards the request packet. An example of this algorithm is shown in Figure 3. When source node S has data packets to transmit, node S forwards the RREQ packet to its neighbor nodes 1 and 2. Node 1 has higher residual energy, and the ETX value between node 1 and node S is good. In this case, node 1 has high forwarding probability. However, node 2 has lower residual energy, and the ETX value between node 2 and node S is bad. So node 2 has lower forwarding probability.Figure 3
Example of the EEPR algorithm.According to (6), a node with lower residual energy has lower forwarding probability. However, when all nodes in the network have low residual energy, most of forwarder nodes discard the RREQ packets because of low forwarding probability. In this case, routing process can be failed continuously.To solve the above problem, we propose the advanced EEPR algorithm considering both the residual energy of its one-hop neighbor nodes and the average value of residual energy of all nodes in the network. To describe the advanced EEPR algorithm, we should assume two factors. First, it is assumed that each node knows the average value of residual energy of all nodes in the network,Eavg, which is calculated by the network controller using the periodically received information about the residual energy from each node. Second, each node usually knows the residual energy of its one-hop neighbor nodes from the hello packets which are periodically broadcasted by each node in order to indicate the existence and some information of the node.The operational procedure of the advanced EERP algorithm is as follows. When source node needs a routing path, source node broadcasts the RREQ packet to its one-hop neighbor nodes. Then, a forwarder node that receives the RREQ packet calculates forwarding probabilityp using its residual energy and ETX value in the EEPR algorithm. However, the node under the advanced EEPR algorithm compares the average value of residual energy of all nodes, Eavg, with the predefined residual energy threshold, Eth. If Eavg is bigger than Eth, the node regards that the network is in a good energy condition and it is not necessary to make the forwarding probability higher. So, the node calculates the forwarding probability as in (6). If Eavg is smaller than  Eth, the node thinks that the network is in a low energy condition and tries to make the forwarding probability higher by executing the advanced EEPR algorithm. Each node defines the maximum value of its neighbor node’s residual energy as a new Emax⁡(Emax⁡new), in place of previous Emax⁡(Emax⁡previ), and calculates the new forwarding probability. So, by using the updated Emax⁡new instead of Emax⁡previ, we can solve the problem (the forwarding probability is so low that RREQ packets can be hardly transmitted to the destination node). This algorithm is described as follows:(7)p=[pmin⁡+EiA[1+(ETXi-1,i-ETXmax⁡)(1-ETXmax⁡)]]1/α,A={1-pmin⁡2×Emax⁡previ,If,Eavg>Eth,1-pmin⁡2×Emax⁡new,If,Eavg≤Eth.An example of the advanced EEPR algorithm is shown in Figure4. Node 3 has to calculate the forwarding probability p and has one-hop neighbor nodes 1, 2, 4, and 5. Before calculating the forwarding probability p, node 3 has to compare the average value of the residual energy of all the nodes in the network (Eavg) with Eth. In this example, Eavg is lower than Eth. Therefore, node 3 has to implement the advanced EEPR algorithm. According to the residual energy of one-hop neighbor nodes, node 4 has the highest residual energy. Therefore, node 3 replaces the previous Emax⁡ value with the residual energy value of node 4. Further, node 3 calculates the forwarding probability p and determines whether to forward the RREQ packet or not.Figure 4
Example of the advanced EEPR algorithm.In the case of using the advanced EEPR algorithm,Eavg is the global factor to represent the energy condition of the entire network. In addition, this algorithm considers the residual energy of its one-hop neighbor nodes and updates the value of Emax⁡. So, the advanced EEPR algorithm considers the energy condition of both local and global networks together. Figure 5 shows the advanced EEPR algorithm in form of a flow chart.Figure 5
Flow chart of the advanced EEPR algorithm.


## 3. Simulations and Performance Evaluation

In this paper, we evaluate the performance of the proposed EEPR algorithm and compared it with the typical AODV protocol.


### 3.1. Simulation Setup

Simulations have been performed by the NS-2 simulator version 2.35 on the Linux Fedora 13 [23]. The simulation parameters that are used for the simulation run are listed in Table 1 [24, 25]. In one simulation iteration, the source node requests the routing path and transmits 10 data packets and the size of each packet is 1,000 bytes. This process is iterated 1,500 times and is terminated when all the nodes wear out their residual energy. The initial residual energy of each node is uniformly distributed between 10 J and 100 J.Table 1
Factors used in the simulation.
Simulation factor
Value
Topology
1000 m by 1000 m grid random
Number of nodes
50
Path loss model
128.1
+
37.6
log
10
⁡
(
dist.
(
km
)
) (dB)
Noise power
10−11 W
Transmission range
300 m
Packet size
1,000 bytes
Initial node energy
10 J~100 J, uniform distribution
Transmission power
0.1 mW
Power consumption for transmission
1.65 W
Power consumption for reception
1.1 W
E
max
⁡
100
E
th
40
ETX
max
⁡
45
P
min
⁡
0.7
α
1


### 3.2. Performance Evaluation

#### 3.2.1. Network Lifetime

Generally the network lifetime is defined as the time difference between the time when the simulation starts and the time when a node having zero residual energy happens. In our work, we extend the concept of the network lifetime and measure the time between the simulation starting time and the time whennth node having zero residual energy happens.Figure6 shows that the nodes using the EEPR algorithm have approximately 12.57% higher network lifetime when compared with the nodes using the typical AODV protocol. As a result, the EEPR algorithm uses the residual energy of all the nodes in the network more evenly compared with the typical AODV protocol.Figure 6
Time as a function of the number of nodes having zero residual energy.


#### 3.2.2. Variance of the Residual Energy

We measure the residual energy of all the nodes and calculate the variance of the residual energy when the simulation ends. The smaller the variance is, the more evenly the algorithm uses the residual energy of the nodes. For performance comparison, the configuration of residual energy distribution is not changed but fixed regardless of the method used.The result for the variance of the residual energy of all the nodes in the network is shown in Figure7. The variance of the residual energy of the nodes under the EEPR algorithm is smaller than that under the typical AODV protocol. The simulation result shows that the nodes under the EEPR algorithm spend the residual energy more evenly compared with typical AODV protocol.Figure 7
Variance of the residual energy.


#### 3.2.3. Delay Time in the Routing Process

Since the EEPR algorithm stochastically controls the number of request packets, the forwarder nodes do not forward the request packets so frequently. This can result in greater routing setup delay compared with the typical AODV protocol. In this paper, we define the routing setup delay as the time difference between the time when a source node forwards the RREQ packets and the time when a destination node receives the first RREQ packet.The result of the routing setup delay is shown in Figure8. The routing setup delay under the EEPR algorithm has approximately 0.4 ms higher than that under the typical AODV protocol. It is because the number of forwarded RREQ packets in the network decreases by stochastically controlling the number of the RREQ packets.Figure 8
Routing setup delay.


#### 3.2.4. Routing Success Probability

The EEPR algorithm stochastically controls the number of the RREQ packets. Therefore, as shown in Section3.2.3, there is a chance that the intermediate nodes on the routing path do not forward the request packets frequently, which may result in the decrease of the routing success probability.The result for the routing success probability in Figure9 shows that the routing success probability of the typical AODV protocol is 93.5335%, whereas that of the EEPR algorithm is 91.7647%. It is approximately 1.8% lower than that of the typical AODV protocol, which may be regarded as minor effect.Figure 9
Routing success probability.


## 3.1. Simulation Setup

Simulations have been performed by the NS-2 simulator version 2.35 on the Linux Fedora 13 [23]. The simulation parameters that are used for the simulation run are listed in Table 1 [24, 25]. In one simulation iteration, the source node requests the routing path and transmits 10 data packets and the size of each packet is 1,000 bytes. This process is iterated 1,500 times and is terminated when all the nodes wear out their residual energy. The initial residual energy of each node is uniformly distributed between 10 J and 100 J.Table 1
Factors used in the simulation.
Simulation factor
Value
Topology
1000 m by 1000 m grid random
Number of nodes
50
Path loss model
128.1
+
37.6
log
10
⁡
(
dist.
(
km
)
) (dB)
Noise power
10−11 W
Transmission range
300 m
Packet size
1,000 bytes
Initial node energy
10 J~100 J, uniform distribution
Transmission power
0.1 mW
Power consumption for transmission
1.65 W
Power consumption for reception
1.1 W
E
max
⁡
100
E
th
40
ETX
max
⁡
45
P
min
⁡
0.7
α
1


## 3.2. Performance Evaluation

### 3.2.1. Network Lifetime

Generally the network lifetime is defined as the time difference between the time when the simulation starts and the time when a node having zero residual energy happens. In our work, we extend the concept of the network lifetime and measure the time between the simulation starting time and the time whennth node having zero residual energy happens.Figure6 shows that the nodes using the EEPR algorithm have approximately 12.57% higher network lifetime when compared with the nodes using the typical AODV protocol. As a result, the EEPR algorithm uses the residual energy of all the nodes in the network more evenly compared with the typical AODV protocol.Figure 6
Time as a function of the number of nodes having zero residual energy.


### 3.2.2. Variance of the Residual Energy

We measure the residual energy of all the nodes and calculate the variance of the residual energy when the simulation ends. The smaller the variance is, the more evenly the algorithm uses the residual energy of the nodes. For performance comparison, the configuration of residual energy distribution is not changed but fixed regardless of the method used.The result for the variance of the residual energy of all the nodes in the network is shown in Figure7. The variance of the residual energy of the nodes under the EEPR algorithm is smaller than that under the typical AODV protocol. The simulation result shows that the nodes under the EEPR algorithm spend the residual energy more evenly compared with typical AODV protocol.Figure 7
Variance of the residual energy.


### 3.2.3. Delay Time in the Routing Process

Since the EEPR algorithm stochastically controls the number of request packets, the forwarder nodes do not forward the request packets so frequently. This can result in greater routing setup delay compared with the typical AODV protocol. In this paper, we define the routing setup delay as the time difference between the time when a source node forwards the RREQ packets and the time when a destination node receives the first RREQ packet.The result of the routing setup delay is shown in Figure8. The routing setup delay under the EEPR algorithm has approximately 0.4 ms higher than that under the typical AODV protocol. It is because the number of forwarded RREQ packets in the network decreases by stochastically controlling the number of the RREQ packets.Figure 8
Routing setup delay.


### 3.2.4. Routing Success Probability

The EEPR algorithm stochastically controls the number of the RREQ packets. Therefore, as shown in Section3.2.3, there is a chance that the intermediate nodes on the routing path do not forward the request packets frequently, which may result in the decrease of the routing success probability.The result for the routing success probability in Figure9 shows that the routing success probability of the typical AODV protocol is 93.5335%, whereas that of the EEPR algorithm is 91.7647%. It is approximately 1.8% lower than that of the typical AODV protocol, which may be regarded as minor effect.Figure 9
Routing success probability.


## 3.2.1. Network Lifetime

Generally the network lifetime is defined as the time difference between the time when the simulation starts and the time when a node having zero residual energy happens. In our work, we extend the concept of the network lifetime and measure the time between the simulation starting time and the time whennth node having zero residual energy happens.Figure6 shows that the nodes using the EEPR algorithm have approximately 12.57% higher network lifetime when compared with the nodes using the typical AODV protocol. As a result, the EEPR algorithm uses the residual energy of all the nodes in the network more evenly compared with the typical AODV protocol.Figure 6
Time as a function of the number of nodes having zero residual energy.


## 3.2.2. Variance of the Residual Energy

We measure the residual energy of all the nodes and calculate the variance of the residual energy when the simulation ends. The smaller the variance is, the more evenly the algorithm uses the residual energy of the nodes. For performance comparison, the configuration of residual energy distribution is not changed but fixed regardless of the method used.The result for the variance of the residual energy of all the nodes in the network is shown in Figure7. The variance of the residual energy of the nodes under the EEPR algorithm is smaller than that under the typical AODV protocol. The simulation result shows that the nodes under the EEPR algorithm spend the residual energy more evenly compared with typical AODV protocol.Figure 7
Variance of the residual energy.


## 3.2.3. Delay Time in the Routing Process

Since the EEPR algorithm stochastically controls the number of request packets, the forwarder nodes do not forward the request packets so frequently. This can result in greater routing setup delay compared with the typical AODV protocol. In this paper, we define the routing setup delay as the time difference between the time when a source node forwards the RREQ packets and the time when a destination node receives the first RREQ packet.The result of the routing setup delay is shown in Figure8. The routing setup delay under the EEPR algorithm has approximately 0.4 ms higher than that under the typical AODV protocol. It is because the number of forwarded RREQ packets in the network decreases by stochastically controlling the number of the RREQ packets.Figure 8
Routing setup delay.


## 3.2.4. Routing Success Probability

The EEPR algorithm stochastically controls the number of the RREQ packets. Therefore, as shown in Section3.2.3, there is a chance that the intermediate nodes on the routing path do not forward the request packets frequently, which may result in the decrease of the routing success probability.The result for the routing success probability in Figure9 shows that the routing success probability of the typical AODV protocol is 93.5335%, whereas that of the EEPR algorithm is 91.7647%. It is approximately 1.8% lower than that of the typical AODV protocol, which may be regarded as minor effect.Figure 9
Routing success probability.


## 4. Conclusions

In this paper, we proposed EEPR algorithm which employs both the residual energy of a node and the ETX value as the routing metrics, at the same time. The proposed EEPR algorithm stochastically controls the number of the RREQ packets using the residual energy and ETX value of a link on the path and thus facilitates energy-efficient route setup. Simulation results show that the proposed EEPR algorithm has longer network lifetime and consumes the residual energy of each node more evenly when compared with the typical AODV protocol while the routing setup delay is slightly increased and the routing success probability is slightly decreased.



---

*Source: 213106-2014-04-15.xml*