Energy Efficient and Load Balanced Routing for Wireless Multihop Network Applications

Abstract

Wireless Sensor Networks (WSNs) can benefit from ad hoc networking technology characterized by multihop wireless connectivity and infrastructure less framework. These features make them suitable for next-generation networks to support several applications such M2M applications for smart cities and public safety scenarios. Pivotal design requirements for these scenarios are energy efficiency, since many of these devices will be battery powered placing a fundamental limit on network, and specifically node lifetime. Moreover, the way in which traffic is managed also influences network lifetime, since there is a high probability for some nodes to become overloaded by packet forwarding operations in order to support neighbour data exchange. These issues imply the need for energy efficient and load balanced routing approaches that can manage the network load and not only provide reduced energy consumption on the network but also prolong the network lifetime providing robust and continuous. This work proposes a new energy efficient and traffic balancing routing approach that can provide a weighted and flexible trade-off between energy consumption and load dispersion. Simulation results show that the proposed protocol achieves high energy efficiency, decreases the percentage of failed nodes due to lack of battery power, and extends the lifespan of the network.

1. Introduction

WSN is a key enabling technology for next-generation networks, having significant application in connecting a multitude of wireless tiny sensors or being able to operate in a more advanced mode by locally connecting different “things” of different capabilities, such as Personal Device Assistance (PDAs), Mobiles, and laptops, making then an ideal solution for next-generation networks. WSNs technology has a profound effect on our everyday life due to its inherent features such as being ubiquitous in nature and offering an inexpensive alternative to traditional networks.

WSNs are more specific use-cases for ad hoc wireless networks that today are autonomous in nature and support flexible topologies to deliver fast and everywhere connectivity. A self-configuring WSN, constituting distributed autonomous wireless nodes, can benefit from a multihopping ad hoc approach, in which nodes operate not only as a transceiver but also as a router and forward packets to other nodes in the network which may not be within direct transmission range of each other. Therefore, by operating in “ad hoc” mode, packet travelling from a source node toward a destination node may pass through multiple nodes to reach its destination.

A key enabler in ad hoc networks is a routing approach that needs to be robust and low in complexity to support end-to-end connectivity in highly dynamic operating environments. However, the effect of node/user mobility, dynamic topologies, frequent link breakages in the communication path, limitation on nodes resources such as battery power, and lack of central point such as base stations or servers means that routing in ad hoc networks can be a very challenging issue. Beside these aforementioned issues, there are also several qualities of service (QoS) metrics that should be considered in a communication, such as data throughput, delay, energy efficiency, traffic balancing, and the protocol overhead. Furthermore, due to the distributed and cooperated nature of ad hoc networks, attributes such as the number, velocity, and the mobility pattern of mobile nodes may affect the QoS metrics provided by the routing protocol.

Providing a concrete routing solution that is energy efficient, but on the other hand able to deliver adequate QoS, is challenging, especially in a highly mobile environment. Usually each protocol tries to focus only on one or some of these QoS metrics. Different approaches reactive and proactive have been explored, and each has distinctive advantages.

Ad Hoc On-demand Distance Vector version 2 (AODVv2) protocol [1] is a well-known routing protocol presented by Mobile Ad Hoc NETwork (MANET) group of Internet Engineering Task Force (IETF) [2]; it applies a uniformed message format and has inherent features to support many required QoS metrics, but it is limited in terms of energy and traffic management. We exploit AODVv2 as a fundamental building block and go beyond this by designing and implementing energy and traffic aware capability. This work proposes an Energy Efficient Ad Hoc On-demand Distance Vector version 2 (E2AODVv2) that can have several applications specifically in WSNs. We implemented several simulation scenarios to test the capability of E2AODVv2, where results have shown that our proposed approach achieves higher performance in terms of energy consumption and load balancing compared to the baseline routing protocols.

This work is structured as follows: Section 2 presents the literature review and related works, Section 3 describes the current implementation of the AODVv2 protocol, Section 4 introduces the new proposed E2AODVv2 routing protocol, Section 5 presents the analysis and simulation results, and finally Section 6 presents conclusions and future works.

2. Related Works

2.1. Ad Hoc Routing Protocols Category

Many routing algorithms have been proposed for ad hoc networks in the literature. These routing protocols can be divided into several categories based on various criteria. In this section, we briefly review these categories and provide one sample from each category.

2.1.1. Flat Routing Protocols

Flat routing protocols in ad hoc networks adopt a flat addressing scheme which means all nodes participating in the routing process play an equal role. Flat routing protocols may generally be classified into two main categories.

(A) Proactive Protocols. This type of protocols attempts to find and maintain consistent, up-to-date routes between all source-destination pairs regardless of the use or need of such routes. Therefore, each node maintains one or more tables to store routing information (table driven protocols). Proactive protocols require periodic control messages to maintain routes up to date for each node. Routing techniques are either link-state or distance vector (or a mixture of both) [3, 4].

• (i)

Distance Vector (DV) based routing protocols: Destination Sequenced Distance Vector (DSDV) [5] is a proactive table-driven protocol based on the classical Bellman-Ford algorithm. All nodes try to find all paths to the possible destination nodes in a network and to save them in their routing tables.

(ii)

Link-State Based (LS) routing protocols: Optimized Link-State Routing Protocol (OLSR) [6] uses selected nodes called multipoint relays (called MPRs) for routing operations in order to forward broadcast messages during the flooding process. Link-state information is generated only by MPRs and this information is then used for route calculation.

(B) Reactive Protocols. Routes are created only when a source node requests them (on-demand protocols). Forwarding process is accomplished according to two main techniques.

• (i)

Source routing protocols: Dynamic Source Routing (DSR) [7] is a source routing protocol and requires the sender to know the entire route to the destination. It is based on route discovery and route maintenance process. Discovered routes will be cached in the relative nodes.

(ii)

Hop-by-hop routing protocols: like Ad Hoc On-demand Distance Vector (AODV) [8], it uses the on-demand mechanism of route discovery and route maintenance from DSR and also a mechanism for the hop-by-hop routing and sequence number. Per each destination, AODV creates a routing table, while DSR uses node cache to maintain routing information.

2.1.2. Hierarchical Routing Protocols

In hierarchical routing protocols, the network's nodes are divided into clusters. Each cluster has an admin entity (head cluster) which is responsible for routing inside that cluster; therefore, in this context, nodes have different responsibilities and importance in routing algorithm. Also, the cluster head election can be a dynamical and distributed operation. Zone Routing Protocol (ZRP) [9] is a hybrid/hierarchical routing protocol that takes advantage of both proactive and reactive schemes by creating overlapped zones based on the separation distances between wireless nodes. ZRP tries to limit the flooding area per each node by assigning a routing zone to that node [10].

2.1.3. Geographical Position Based

These types of protocols assume that each node in the network is aware of its own location and the status of its one-hop neighbors, for example, via a Global Positioning System (GPS). In the Greedy Perimeter Stateless Routing (GPSR) [11] protocol, in any communication between a source-destination pair of nodes, the source node is aware of the destination node's location. All one-hop neighbors exchange beacon control messages between each other to simultaneously update their routing tables and limit control message overhead [10].

2.1.4. Hybrid Protocols

Hybrid protocols, by mixing different routing algorithms, try to take the advantage of previously mentioned protocols to reach to the highest efficiency. Temporally-Ordered Routing Algorithm (TORA) [12] is a highly adaptive loop-free distributed routing algorithm based on the concept of link reversal and it applies a reactive (on demand) source routing scheme. The key design concept of TORA is the reduction of control messages to a very small set of topological changes by performing three basic functions: route creation, route maintenance, and route deletion. All nodes in TORA use a “height” metric to establish a direct acyclic graph (DAG) rooted at the destination [13].

A category of current ad hoc routing protocols is shown in Figure 1. Also, a survey on current routing algorithms for wireless ad hoc networks can be found in [10]. The new proposed routing protocol, the so-called “E2AODVv2,” can be conveniently positioned as shown by Figure 1.

Figure 1

A structure of ad hoc routing protocols categories.

2.2. Power-Aware Routing Protocols

Hard QoS routing guarantee in ad hoc networks is a Nondeterministic Polynomial time- (NP-) Complete problem [14]. Therefore, the current works focus on providing a soft QoS routing guarantee for ad hoc networks as a more realistic solution. In this paper, we consider battery power consumption and traffic balancing as a measurement of efficiency.

Most of current routing protocols, proposed in MANET group of IETF [2], consider the path length metric when choosing the best route between a source (S) and a destination node (D). However, this approach may, in most cases, minimize the end-to-end delay in a communication between the source and the destination node, but it may not be adept to handle other QoS metrics such as energy efficiency and load balancing, because they do not consider the node residual energy as a criterion in the route selection process [15].

The dynamic topology in ad hoc networks implies that some nodes may relay more traffic than others, mainly because of their location in the network; these hot spots will consume their energy reserves sooner than the others. Unbalanced battery power consumption in the network nodes can leads to early node failure rate a, network partitioning, and to a reduction in the route reliability. Traffic concentration on these nodes may increase radio jamming, delay, and packet loss. Also, since the majority of the network traffic can potentially pass these nodes, they can become an important target for attackers.

Power-aware routing algorithms aim to deliver new routing paths that take into account energy as a metric [16]. Gomez et al. [17] add new intermediate nodes to a route from a source to a destination to reduce the overall required transmission power of the intermediate nodes. Lindgren and Schelen [18] improve the AODV routing protocol in terms of energy efficiency, by selecting paths through Power Base Stations (PBSs) instead of through normal nodes. Edwards et al. [19, 20] present two power-aware extensions of the original DSR ad hoc routing protocol that use energy aware metrics such as the remaining battery power to decide which nodes should participate more often in packet forwarding. Load balancing and homogeneous distribution of battery power consumptions between networks nodes are other solutions to achieve a power-aware ad hoc routing algorithm [21].

However, most of current power-aware approaches lead to some common drawbacks, such as increased delay and increase in the number of required control messages that should be created by the routing protocol to deliver users’ data packets (called Normalized Routing Load), limited scalability, among others.

3. Revised Ad Hoc On-Demand Distance Vector (AODVv2)

AODVv2 is a successor to the AODV that is being developed by IETF MANET; prior to the 26th revision [1], AODVv2 was called DYnamic MANET On-demand (DYMO).

3.1. Protocol Description

AODVv2 tries to simplify the current reactive protocols, such as DSR and AODV, and simultaneously conserves their two main well-known routing operations: route discovery and route maintenance [22]. It has multipath capability (optional) and is also a hop-by-hop routing protocol. Therefore, intermediate nodes, located in a route between a source and a destination node, are able to extract additional information from the traversing control packets. AODVv2 applies a standard generalized MANET Packet/Message format [23] for control packets: a uniformed message format, called Routing Message (RM), is used for all control messages and routing packets. Another interesting feature of AODVv2 is the capability to Internet Protocol (IP) [24] versions 4 and 6 (IPv4 and IPv6, resp.) which can be considered an essential feature for next-generation networks.

Several works analysed the performance and benefits of AODVv2 [22, 25, 26]. To improve the performance of AODVv2 [22, 25, 26], Kretschmer et al. [27] focused on reducing the delay and on increasing the packet delivery ratio, by finding routes with high probability to be used in future. Also, there are few works, such as [25], that try to extend a multipath version of AODVv2 to switch between different paths from source to destination in order to balance the battery power consumption and the traffic of the nodes on different routes. However, these works do not provide a mechanism for handling both load balancing and energy efficiency in highly dynamic topologies.

3.2. Routing Operation

All routing operation in AODVv2 can be categorized into three phases.

3.2.1. Route Request Phase

In a communication between a source node (S) and a destination node (D), S originates a Route Message (RM), called ROUTE REQUEST (RREQ) message, and broadcasts this to all of its neighbours. These RREQs are then flooded in the network until they reach D. An intermediate node which does not know the route to D should forward the RREQ to its neighbours. The intermediate node will also drop the repeated request for the same destination and will not forward them anymore, as shown by Figure 2. RM has several fields such as current node address, next node address, HopLimit (the default value is 10 based on [1]), Target (destination node address if it is an RREQ message), and the Origin (source node address if it is an RREQ message) [1]. By tracing the RREQ traversed path (called accumulated path), each node, such as intermediate or destination node, which receives an RREQ message, can extract routing information. Figure 2 shows the RREQ phase in AODVv2 routing protocol for a sample network.

Figure 2

A sample of RREQ phase in AODVv2.

3.2.2. Route Reply Phase

As shown by Figure 3, when RREQs finally reach the destination node, another RM, which is called ROUTE REPLY (RREP), will be originated by the destination node. The intermediate nodes which have, in their routing table, an entire route towards that destination node also can immediately reply to the RREQ originated by the source node (known as gratitude reply and it is an optional feature of AODVv2). Both the RREQ and the RREP have the same uniform structure.

Figure 3

A sample of RREP phase in AODVv2.

3.2.3. Routing Operation: Route Error Phase

An intermediate node may originate an RM, called an ROUTE ERROR (RERR), in the two main scenarios. In the first case, the intermediate node does not have a valid route for the destination of a received data packet and consequently the packet is undeliverable. In the second case, the intermediate node detects a link breakage, as shown in Figure 4.

Figure 4

A sample of RERR phase in AODVv2.

4. Energy Efficient AODVv2 (E2AODVv2)

The inherent benefits of AODVv2 due to standardized control packets following IETF uniform packet formats and the capability to support IPv6 suggest that this protocol will have a strong legacy in ad hoc networks. Therefore, if we are to pursue energy efficient operation for routing in ad hoc networks, then exploring AODVv2 as the fundamental building block can be potentially a springboard for promoting significant energy savings in the network. In this section, we describe our proposed approach to increase the energy efficiency of AODVv2.

4.1. Routing Messages in E2AOVv2

E2AODVv2 introduces two new fields for each routing message which are discussed in this section.

4.1.1. Energy Field

Suppose that, for a communication between a source and a destination node, there are N routes and the number of nodes in the ith route, called $\text{Rout}{\text{e}}_i$ , is $M_i$ (as shown in Figure 5). In E2AODVV2, each kth node in $\text{Rout}{\text{e}}_i$ , has a battery power ( ${\text{BP}}_k$ ) level quantified as 16 different values (from 0 to 15).

Figure 5

Multiple routes between source and destination.

Moreover, there is a Critical Battery Power Level (CBPL) whose default value is 3 ( $\text{CBPL}=\mathrm{3}$ ). Therefore node k in $\text{Rout}{\text{e}}_i$ , which has a BP of less than CBPL, is suffering from energy depletion and is considered as a critical node in terms of battery power (i.e., ${\text{BP}}_k<\text{CBPL}$ ). Critical nodes should not be selected for packet forwarding in E2AODVv2.

The Energy field of RREQ in E2AODVv2 has three cells: totbat, MinBat, and CritBat. TotBat_i is the summation of the total battery power level of all nodes of $\text{Rout}{\text{e}}_i$ , as shown by (1). The ${\text{MinBat}}_i$ cell in the energy field of ${\text{RREQ}}_i$ shows the minimum value of BP for all nodes in ${\text{Route}}_i$ , whilst ${\text{CritBat}}_i$ shows the number of nodes which have a BP less than CBPL in ${\text{Route}}_i$ :

$$\begin{array}{cc}& {\text{TotBat}}_i=\sum _{k=\mathrm{1}}^{{k=M}_i}{\text{BP}}_k.\end{array}$$

(1)

Figure 6 shows a network based on the previous sample that has a simpler topology. In this example, there are 8 nodes. The battery power level and the traffic parameter of all these nodes are given in Table 1 (the traffic parameter will be introduced later in this paper). Based on Table 1, the energy and the traffic parameters of all paths of the network in Figure 6 are calculated and given by Table 2.

Table 1

Battery power level and traffic parameter of all nodes of the network in Figure 6.

Node	Battery power(BP)	Traffic parameter(TP)
A	6	0.7
B	8	0.5
C	2	0.8
F	12	0.3
I	10	0.6
G	5	0.9
H	14	0.4

Table 2

The energy and traffic features of all these nodes of the network in Figure 6.

Path	S-C-I-D	S-A-B-F-H-D	S-A-B-G-D
Path number	$i=1$	$i=2$	$i=3$
CritBat	1	0	0
TotBat	12	40	19
MinBat	2	6	5
M	2	4	3
TotTra	1.4	1.9	1.8
MaxTra	0.8	0.7	0.7

Figure 6

D originates route replies (RREP) toward S in AODVv2.

For example, as the first column of Table 2 shows, the first path ( $i=1$ ) from S to D (i.e., S-C-I-D) has one node with a critical battery level ( $\text{CritBat}=\mathrm{1}$ ); the minimum battery power level of all nodes in this path is 2 which belongs to node C, as shown in Table 1 ( $\text{MinBat}=\mathrm{2}$ ); the total battery power level of all nodes in this path is 12 ( $\text{TotBat}=\mathrm{12}$ ), and the number of intermediate nodes in this path is 2 ( $M=\mathrm{2}$ ).

For this network, the original AODVv2 chooses the shortest path (i.e., the first path S-C-I-D); however, the new proposed protocol, E2AODVv2, will choose the second path (i.e., S-A-B-F-H-D), which is a stronger alternative in terms of energy efficiency, and even traffic load which is discussed later on.

4.1.2. Traffic Field

In Figure 5, if the queue size of the interface of node k located in ${\text{Route}}_i$ is $\text{A}{\text{Q}}_k$ and the maximum queue size is ${\text{MQ}}_k$ , then the traffic parameter of node k in E2AODVv2 (i.e., ${\text{TP}}_k$ ) will be calculated based on

$$\begin{array}{cc}& {\text{TP}}_k=\frac{{\text{AQ}}_k}{{\text{MQ}}_k}.\end{array}$$

(2)

The Traffic field of RREQ has two cells: TotTra and MaxTra. The first one is the summation of all traffic parameters in ${\text{Route}}_i$ , as defined by

$$\begin{array}{cc}& {\text{TotTra}}_i=\sum _{k=\mathrm{1}}^{{k=M}_i}{\text{TP}}_k.\end{array}$$

(3)

The second one, that is, ${\text{MaxTra}}_i$ , is the maximum TP values of ${\text{Route}}_i$ . The traffic parameters of all nodes of the network, which is presented in Figure 6, are given by Table 1, whilst the traffic parameters of all paths are given in Table 2.

For example, as the first column of Table 2 shows, for the first path $(i=1)$ from S to D (i.e., S-C-I-D), the total traffic parameter of all intermediate nodes is 1.4 (i.e., $\text{TotTra}=\mathrm{1.4}$ ) and the maximum traffic parameter is 0.4 (i.e., $\text{MaxTra}=\mathrm{0.4}$ ) which belongs to node C as shown in Table 1. Also, M is the number of intermediate (relay) nodes in a path; for example, the first path S-C-I-D has two intermediate nodes; therefore $M=2$ .

Therefore, in E2AODVv2, when the intermediate node k receives RREQ, it updates TotTra_i and MaxTraiof the traffic field of the RREQ and forwards the RREQ toward the next node. A sample node routing table is shown in Table 3.

Table 3

A sample of routing table of a node in E2AODV2.

Dest. add.	Route seq. num.	Hop count	Next hop	Lifetime (ms)	Last used (ms)	Forward flag	Broken flag	$\cdots$
D	112	3	I	30000	10000	T	F	$\cdots$
E	36	2	S	20000	15000	T	F	$\cdots$
K	76	4	I	50000	1000	T	F	$\cdots$
$⋮$	$⋮$	$⋮$	$⋮$	$⋮$		$⋮$	$⋮$	$⋮$

4.2. Route Selection Process

In E2AODVv2, when a destination node receives several RREQs from different routes, as in Figure 5, it runs a route selection process to determine the best route in terms of energy and traffic parameters.

4.2.1. Calculating Energy Parameter of a Route in E2AODVv2

The energy parameter of ${\text{Route}}_i$ , called $E(i)$ , indicatesthe priority of the ${\text{Route}}_i$ , in terms of the battery power level as presented by

$$\begin{array}{cc}& E_i=\frac{\text{TotBat}\left(i\right)}{M_i\times \text{InitialBat}},\end{array}$$

(4)

where $M_i$ is the number of nodes in ${\text{Route}}_i$ , TotBat(i) is the total battery power level of all nodes in ${\text{Route}}_i$ , as presented in (1), and InitialBat is the initial battery power level of a node (which is preset to the same value for all nodes). In some scenarios, a route may have a few nodes with a very low energy level, but a high overall energy level; this route should be avoided due to these bottleneck nodes. Therefore, the negative impact of MinBat(i) (which is the minimum battery power level of ${\text{Route}}_i$ ) should be applied to $E(i)$ , as given by

$$\begin{array}{cc}& E_i=\frac{\text{TotBat}\left(i\right)\times \text{MinBat}\left(i\right)}{M_i\times {\text{InitialBat}}^{\mathrm{2}}}.\end{array}$$

(5)

As mentioned before, CritBat(i) identifies the number of nodes in ${\text{Route}}_i$ which have reached to a critical battery level and hence should be avoided from packet relaying functions (otherwise, the route is likely to break down). A large value for CritBat(i) triggers an alert that this route has several nodes with a critical battery level. Consequently, $E(i)$ can be revised to reflect also the negative impact of these nodes in ${\text{Route}}_i$ . The final $E(i)$ of a route in E2AODVv2 will be calculated based on (6). When a destination node receives an RREQ, it can calculate $E_i$ , via the energy field of the RREQ:

$$\begin{array}{cc}& E_i=\frac{\text{TotBat}\left(i\right)\times \text{MinBat}\left(i\right)}{M_i\times {\text{InitialBat}}^{\mathrm{2}}\times \left(\text{CritBat}\left(i\right)+\mathrm{1}\right)}.\end{array}$$

(6)

4.2.2. Calculating Route Traffic Parameter in E2AODVv2

A route with a lower traffic metric cost has a higher priority in the routing process of E2AODVv2. Nevertheless, a route may have a low overall traffic metric even if one of its nodes is overloaded with traffic, thus creating a bottleneck, and should be potentially avoided. The traffic parameter of Route _i is shown by $T(i)$ and is calculated by

$$\begin{array}{cc}& T_i=\frac{\text{TotTra}\left(i\right)\times \text{MaxTra}\left(i\right)}{M_i},\end{array}$$

(7)

where $M_i$ is the number of nodes in ${\text{Route}}_i$ . When a destination node receives an RREQ, it can calculate $T_i$ via the traffic field of the RREQ.

4.2.3. Precedence Function

The function that determines the precedence of ${\text{Route}}_i$ is given by RoutePrio(i). This function depends on the energy and the traffic parameters of ${\text{Route}}_i$ that are calculated by (6) and (7), respectively:

$$\begin{array}{cc}& \text{RoutePrio}\left(i\right)=\frac{E_i}{T_i}.\end{array}$$

(8)

However, we can choose a trade-off between energy efficiency and traffic balancing, but this function is flexible and can be customized by giving a higher weight to the energy or traffic parameter.

4.2.4. Routing Behaviour of Nodes in E2AODVv2

In E2AODVv2, each node shows different routing behaviour that depends on the role of the node in the communication.

• (i)

Source node: when a source node wants to send an RREQ, it initializes the values of the energy and the traffic fields (they will be set to zero).

(ii)

Intermediate nodes: these update the energy and traffic fields accordingly: (i) each node who receives an RREQ adds its own BP to TotBat value; (ii) if the current node k in ${\text{Route}}_i$ , has a ${\text{BP}}_k$ less than MinBat, then MinBat will be updated by ${\text{BP}}_k$ (i.e., if ${\text{BP}}_k<{\text{MinBat}}_i$ then ${\text{MinBat}}_i={\text{BP}}_k$ ); (iii) if ${\text{BP}}_k<\text{CBPL}$ , then CritBat will be increased by one- (iv) each node, which receives an RREQ and adds its ${\text{TP}}_k$ number to the TotTra number; (v) if ${\text{TP}}_k>\text{MaxTra}$ , then MaxTra will be updated by ${\text{TP}}_k$ . However, the intermediate node in traditional AODVv2 will drop the repeated request for the same destination and will not forward them anymore, as Figure 2 shows, but, in our protocol, the intermediate nodes will forward these RREQs as well, as shown in Figure 7.

(iii)

Destination nodes: when a destination node receives n RREQs from different n routes, by extracting the required information from RREQ, it can calculate the Route Priority for all these RREQs and finally the route which has the best Route Priority will be chosen.

Figure 8 shows the role of the source, the intermediate, and the destination nodes in a communication. Each route request, such as ${\text{RREQ}}_i$ , should be initialized by a source node. It will pass from one node to another within the route, and each node has the opportunity to update the energy and traffic fields accordingly (where each route will have $M_i$ intermediate nodes). It finally reaches the destination node which is responsible for running the Precedence Function, finding the best route and initializing the RREP. Therefore, via this distributed mechanism, the nodes in E2AODVv2 can cooperatively balance the load in the network, in terms of traffic and battery power consumption.

Figure 7

A sample of RREQ phase in E2AODVv2.

Figure 8

RREQ and RREP processes: the routing behaviour of source, intermediate, and destination nodes in E2AODVv2.

5. Analysis of E2AODVv2

5.1. Analytical Analysis

As we discussed in Section 4.1, the traditional AODVv2 for the network in Figure 6 chooses the first path ( $i=1$ ) from S to D (i.e., S-C-I-D). The battery power level and the traffic parameter of all these nodes are given in Table 1. Also, based on Table 1, the energy parameter, the traffic parameters, and the priority of all paths of the network in Figure 6 are calculated and given in Table 4. Our proposed E2AODVv2 protocol, based on Table 4, chooses the second path (i.e., S-A-B-F-H-D), which provides equal priority towards reducing energy and balancing traffic load. Therefore, E2AODVv2 send RREP messages through this optimized path as shown by Figure 9.

Table 4

The energy and traffic features of all paths in the network of Figure 9.

Path	S-C-I-D	S-A-B-F-H-D	S-A-B-G-D
Path number	$i=1$	$i=2$	$i=3$
CritBat	1	0	0
TotBat	12	40	19
MinBat	2	6	5
M	2	4	3
E	0.026	0.26	0.14
TotTra	1.4	1.9	1.8
MaxTra	0.8	0.7	0.7
T	0.56	0.3325	0.63
RoutePrio (E/T)	0.046	0.781	0.22
Best path	×	√	×

Figure 9

A sample of RREP phase in E2AODVv2.

5.2. Evaluating Proposed Protocol

We use Two-Ray Ground Reflection Model which considers both the direct path and a ground reflection path between two mobile nodes. Also all nodes in the network move based on the Random Way Point Mobility Model. In this movement model, a mobile node starts its travel from a random location inside the topology area after pausing for a certain period of time (called “pause time”). After the initial pause time, the mobile node chooses another random location inside the topology area and moves toward this new location by a speed that is uniformly distributed between a predefined minimum and maximum speed. Upon arrival, the mobile node pauses again for the pause time and repeats the previous process again till the simulation time is expired [3, 28].

The simulation results presented in this paper were obtained using the ns-2 simulator [29]. Traffic sources are CBR (Constant Bit Rate) and the packet sending rate at the source nodes is 8 packets per second. Table 5 presents a summary of the parameters for the simulated scenarios (movement and traffic files).

Table 5

Parameters of movement models and communication model.

Parameters of movement model I, characterized by number of nodes
Topology area	500 m × 500 m
Maximum mobility of nodes	5 m/s
Number of nodes	$1,\dots ,\mathrm{20}$
Simulation time	300 s
Parameters of movement model II, characterized by simulation time
Topology area	500 m × 500 m
Maximum mobility of nodes	5 m/s
Number of nodes	20
Simulation time	$\mathrm{200},\dots ,\mathrm{1800}$  s
Parameters of traffic model
Traffic sources	CBR
Data packets size	512 bytes
Sending rate	8 packets/second

5.2.1. Performance Metrics

We evaluated the proposed protocol using five metrics: $(1)$ balancing energy consumption, $(2)$ scalability, $(3)$ network lifetime, $(4)$ node's failure level, and $(5)$ jitter.

(I) Balancing Energy Consumption. This metric will allow measuring the effectiveness of the energy balancing algorithm used by E2AODVv2. Let us denote the energy load of all the nodes in the network consisting of N nodes; is a set $\text{EL}=\{el(i)\in \text{El}:i=1,\dots ,N\}$ ,

where element of this set, for example, $\text{el}(i)$ , is calculated as ration of the consumed energy node i to the total aggregate energy consumed in all the nodes, including node i. That is,

$$\begin{array}{cc}& \text{el}\left(i\right)=\frac{\text{Consumed}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{Energy}\left(i\right)}{\text{Total}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{Consumed}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{Energy}}.\end{array}$$

(9)

Having calculated all N elements of the EL, we can now calculate the standard deviation of $EL$ for a network consisting of  N nodes (i.e., ${\sigma }_{\text{EL}}^N$ ). The value of ${\sigma }_{\text{EL}}^N$ will be our energy balancing metric for comparing different protocols; the smaller the ${\sigma }_{\text{EL}}^N$ , the more effective the energy balancing capability.

(II) Scalability. Another interesting metric is the scalability of the proposed protocol in terms of load balancing, that is, if the proposed protocol can balance the load of the network when we increase the number of network nodes (i.e., N in our settings). For this purpose we change the number of nodes N (the network size) to a maximum number (which is 20 in our setting, based on Table 5) and calculate the related ${\sigma }_{\text{EL}}^N$ for each network size.

(III) Network Lifetime. Network lifetime is another important metric that reflect the load balancing capability of the routing protocol; the bigger the lifetime, the more effective the energy balancing capability. To compare the lifetime of the proposed protocol with other protocols, we take two parameters into consideration: $(1)$ the first failure time FT_first (the time that the first node in the network ran out of battery power) and $(2)$ last failure time FT_last.

(IV) Node Failure Level. Finally the last performance metric that we use is the node failure level, which determines the capability of E2AODVv2 in keeping nodes alive for longer durations. The node failure level, for a time window T, is the percentage of nodes in the topology that have failed due to a depleted battery. This value is calculated as follows:

$$\begin{array}{cc}& \text{Node}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{Failure}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{Level}=\frac{\#\text{failed}\_\text{nodes}\_\text{in}\_T}{\#\text{nodes}\_\text{in}\_\text{topology}}.\end{array}$$

(10)

(V) Jitter. In a data transmission between a pair of source and sink nodes, jitter is the variation in the time between packets arriving at the source node. Let us assume that, at time $S_i$ , the source node sends packet $P_i$ and the sink node receives it at time $R_i$ . The jitter of packet $P_i$ is calculated as follows:

$$\begin{array}{ll}{\text{Jitter}\mathrm{\hspace{0.17em}\hspace{0.17em}}P}_i& =\left|\left(R_{i+\mathrm{1}}-R_i\right)-\left(S_{i+\mathrm{1}}-S_i\right)\right|\\ & =\left|\left({R_{i+\mathrm{1}}-S}_{i+\mathrm{1}}\right)-\left(R_i-S_i\right)\right|.\end{array}$$

(11)

During the entire simulation time, in a communication between a pair of source and sink nodes, there are M streams of packets, with each stream consisting of P packets. We studied the average jitter of all streams of data in the network.

5.2.2. Simulation Results

This section presents the simulation results for the comparison between two reactive protocols AODV and DSR that are considered baselines in this work, against our proposed E2AODVv2 protocol.

(A) Balancing Energy Consumption and Scalability. For this metric, simulation results are presented in terms of the capability of our approach to balance battery power (energy) consumption. The traffic model is the one presented in Table 5 with the following variants.

• (i)

Distributed traffic amongst nodes: traffic sources and destinations will be chosen randomly in time. This variant is shown by “Distributed” in Table 6.

(ii)

Concentrated traffic with overloaded nodes: traffic destinations will be predefined (all traffic in the network goes toward those sink nodes). This variant is shown by “Concentrated” in Table 6.

The metric for energy consumption balancing in a network consisting of N nodes is ${\sigma }_{EL}^N$ as discussed in Section 5.2.1. As a sample, the value of ${\sigma }_{EL}^N$ when network consists of 12 nodes (i.e., ${\sigma }_{EL}^{12}$ ) is marked in Figure 10 per different protocols for the distributed traffic mode and similarly in Figure 11 for the Concentrated traffic mode. Also, Table 6 summarizes these sample values for ${\sigma }_{EL}^{12}$ .

Table 6

Balancing energy consumption metric ${\mathrm{\sigma }}_{\text{EL}}^{\mathrm{N}}$ , the first failure time FT_first (s), and the last failure time FT_last (s), for both distributed and concentrated traffic modes.

	${\mathrm{\sigma }}_{\text{EL}}^{\mathrm{12}}$ Distributed	${\mathrm{\sigma }}_{\text{EL}}^{\mathrm{12}}$ Concentrated	FTfirst Distributed (second)	FTfirst Concentrated (second)	FTlast Distributed (second)	FTlast Concentrated (second)
E2AODVv2	0.029	0.085	500	500	1700	1800
DSR	0.045	0.182	400	400	1700	1500
AODV	0.05	0.202	300	300	1400	1300

Figure 10

Balancing of energy consumption ( ${\sigma }_{\text{EL}}^N$ ) and the scalability of protocols versus number of nodes (when distributing traffic amongst nodes).

Figure 11

Balancing of energy consumption ( ${\sigma }_{\text{EL}}^N$ ) and the scalability of protocols versus number of nodes (when traffic is concentrated in few nodes).

Furthermore, the value of ${\sigma }_{EL}^N$ decreases as the network size N increases, demonstrating the scalability of the protocols as shown in Figures 10 and 11 for Distributed and Concentrated traffic modes, respectively.

For the first variant, distributed traffic amongst nodes, all protocols show a similar performance (Figure 10): increasing the number of nodes leads to improved energy balancing (lower standard deviation). This can be explained due to the chosen traffic model since multiple traffic source/destinations are chosen randomly throughout the simulation, and thus more nodes will participate in the routing process.

For the second variant, that targets concentrated traffic with overloaded nodes, we chose n nodes, amongst all network nodes (N), as destination nodes (sink nodes) for the generated traffic in the network. The number of n is set to 20% of N, which due to the many-to-one traffic pattern, creates overload conditions at destination nodes. Simulation results show that, in such scenarios, the standard deviation behaviour is similar to the previous variant but with the worst performance (Figure 11). However, as in the previous scenario, all three protocols improve in terms of performance as the number of nodes in topology increases (Figure 11). As both Figures 10 and 11 show, the proposed protocol E2AODVv2 reaches a higher performance in terms of battery power efficiency, balancing, and scalability in contrast to the baselines.

(B) Network Lifetime and Node Failure Level. This metric is measured using movement model II described in Table 5. Similar to the previous case, here again there are two different traffic models: Distributed traffic amongst nodes (Figure 12) and Concentrated traffic with some overloaded nodes (Figure 13). As discussed in Section 5.2.1, we use the first failure time FT_first and the last failure time FT_last as the network lifetime metrics. The values of FT_first and FT_last are marked in Figures 12 and 13 and also summarized in Table 6. As these results show, E2AODVv2 has always better value for both FT_first and FT_last. Also, as expected, the number of failing nodes increases with simulation time. When nodes use E2AODVv2, their lifetime gets extended due to the energy balancing capabilities of E2AODVv2 and shows a lower Node failure level (Figure 12). This feature is even more pronounced when traffic is concentrated in a few nodes (Figure 13).

Figure 12

Percentage of failed nodes versus simulation time (when distributing traffic amongst nodes).

Figure 13

Percentage of failed nodes versus simulation time (when traffic is concentrated in a few nodes).

(C) Jitter. Jitter has several sources such as network congestion, route changes, and delaying packets in the buffer queues of the intermediate nodes in a source-sink communication session. Usually a jitter buffer is used at sink nodes to counteract the jitter.

Jitter is a measurement for the quality of the communication; a small jitter indicates a high quality communication by a low latency. As Figure 14 shows, the performance of the proposed protocol is better than DSR and very close to the original AODV. This can be explained due to the more complicated algorithm of E2AODVv2 for choosing a route which leads to a higher delay.

Figure 14

Jitter versus number of nodes.

Future work will extend the proposed approach in this paper for energy efficiency and load balancing to include other QoS metrics such as delay and data throughput by varying the topology area and velocity of nodes. Another metric that could be considered in the future works to obtain the required power for transmitting the data between two nodes is the signal to noise ratio (SNR). A high SNR value for a link between two neighbor nodes shows that we should find an alternative energy efficient link and eventually a path for the data transmission between a pair of source and sink nodes. This approach may also lead to the need for a cross-layer design [30] for our protocol.

6. Conclusion

Next-generation wireless sensor networks, constituting distributed autonomous wireless sensors and nodes, can benefit from ad hoc networking technology. However a key requirement for this technology that should be satisfied is an energy efficient and load balanced routing protocol. This paper proposes a new energy efficient and traffic balancing routing protocol based on the well-known IETF AODVv2 protocol, a popular approach for routing in ad hoc networks. The protocol uses a standard generalized MANET Packet/Message format. The E2AODVv2 has been enhanced with battery power efficiency and balancing capability that can detect the nodes that reach a critical battery level in the network and switch the route in order to avoid network fragmentation and to achieve a higher network lifetime. The same behaviour is also fulfilled when bottlenecks are detected in a specific route in terms of traffic load. These additional functionalities are achieved without the need to create new disruptive approach in the protocol messages. E2AODVv2 achieves a higher performance with respect to energy consumption balancing, scalability, network lifetime, and the percentage of failed nodes in comparison to well-known baseline protocols such AODV and DSR and a jitter value very close to the AODV. As shown by the simulation results, the E2AODVv2 routing protocol specifically outperforms in scenarios where the load of the network is not balanced. Moreover, the proposed approach can be said to be technology agnostic in that it can be applied to many other reactive ad hoc protocols.