1 Introduction

Mobile ad hoc networks (MANETs) [4] are complex distributed systems that freely and dynamically enable self-organized wireless mobile nodes to form arbitrary and temporary ad hoc network topologies. MANETs allow people and devices to work in areas with no preexisting communication infrastructure.

Routing is the major functionality of a network, providing the paths on which the packets travel across the network [3]. The nature of MANETs makes traditional routing protocols impractical for ad hoc networks [9]. Therefore, a number of new routing protocols for ad hoc networks have been introduced. These can be classified into two different groups: proactive routing protocols, including optimized link state routing [19] and destination sequenced distance vector [23], and on-demand protocols, such as dynamic source routing (DSR) [12], temporally ordered routing algorithm [21], and ad hoc on-demand distance vector routing (AODV) [24, 41]. Unfortunately, proactive schemes consume more energy as they incur large routing overheads, and reactive protocols suffer from route discovery latencies.

The appearance of multipath routing protocols was a major factor in solving many routing issues, especially in MANETs. However, route discovery latencies and overheads persist. Multipath on-demand protocols such as AOMDV and MP-DSR attempted to circumvent this limitation by allowing the transfer of data through multiple disjoint routes [16, 17]. Specifically, under the AOMDV route discovery process, alternate loop-free reverse paths are formed at intermediate nodes using the routing information obtained through duplicate route request (RREQ) copies. The destination node generates multiple route replies (RREPs), which travel along multiple loop-free reverse paths to the source. The data forwarded from the source node based on routing metrics is then used to select the best multiple loop-free forward paths for forwarding packets to the destination node [39]. Multiple paths may be used to enhance the reliability of the routing, as they can be applied when a route failure or congestion occurs [29], or to provide load balancing, which is especially important considering the limited bandwidth between nodes in MANETs.

Load balancing [32] distributes the data and traffic load across multiple paths to achieve optimal resource utilization, maximize throughput, minimize response time, increase network life time, and avoid overheads. An unbalanced data load will lead to power depletion on heavily loaded nodes that drop out of the network. Unless nodes are replaced or recharged, the network will eventually be partitioned. Additionally, heavily loaded nodes will suffer large delays and high packet loss ratios.

In recent years, energy-preserving load balancing routing protocols for ad hoc networks have received considerable attention. In this paper, I introduce an energy-efficient load balancing multipath routing protocol based on maximal minimal nodal residual energy (MMRE) in the AOMDV routing protocol. The proposed load balancing (LB)MMRE-AOMDV protocol is an enhancement of AOMDV that reduces traffic and takes advantage of MMRE in balancing the data load among generated link-disjoint paths while maintaining the nodes’ energy.

This paper is organized as follows. Section 2 briefly reviews energy-efficient multipath routing protocols, both with and without load balancing. In Sect. 3, the proposed efficient-energy LBMMRE-AOMDV protocol is described. Section 4 presents simulation results, and Sect. 5 outlines the conclusions to this study.

2 Background

Wireless networks represent a fertile field for researchers to investigate and introduce novel solutions and protocols to keep up with the rapid evolution in wireless network types and achieve better quality of service (QOS) metrics [5, 30]. As different network types, topologies, and applications require different routing protocols, particularly with regard to efficient energy consumption [40], path-finding methodologies (unipath or multipath), and routing schemes (unicast, broadcast, or even multicast) [22, 38].

Starting from traditional wireless networks as MANETs [41], vehicular ad hoc networking is considered one of the major factors in providing road safety and innovative mobile applications [42], and could assist in forming wireless sensor networks [15, 25, 34, 37].

Cognitive radio networks [2, 28] represent an innovative approach to wireless engineering in which radios are designed with an unprecedented level of intelligence and agility, and wireless mesh networks [7] form a backbone network composed of mesh routers that are usually static and have no constraints on energy consumption. The most recent wireless networks are known as opportunistic networks and delay-tolerant networks (DTNs). Opportunistic networks mainly support information sharing through new mobile applications by enabling communication between two mobile nodes when they are in each other’s transmission range or are on the same multihop path [33]. DTNs are designed to operate over extreme distances, such as in space, where delays are measured in hours or days rather than seconds [8, 27, 31].

As mentioned, different wireless networks need different routing protocols. As this paper is concerned with MANETs, AOMDV, and MMRE-AOMDV, the following subsections describe multipath distance vector protocols and the updated MMRE-AOMDV, which is the basis of this research. Finally, the concept of load balancing is discussed.

2.1 Ad hoc on-demand multipath distance vector

The AODV [1] was one of the first powerful reactive routing protocols. Through the route discovery phase, a limited flooding of RREQs with a ring expansion to the destination is processed to obtain a route through the corresponding RREPs. AODV is a unipath routing protocol in which the route generation phase carries a huge overhead, which limits its performance. The AOMDV protocol reduces the overhead by generating multiple loop-free and link-disjoint paths. In AOMDV, the source node keeps several different routes from the multiple RREPs.

Through AOMDV [16, 18], RREQ propagation from the source node to the destination node establishes multiple reverse paths, both at intermediate nodes and the destination. Multiple RREPs traverse these reverse paths to form multiple forward paths to the destination at the source and intermediate nodes. AOMDV also supports intermediate nodes with alternate paths, as they are found to be useful in minimizing the frequency of route discovery.

Although the AOMDV employs a minimum-hop metric to select a route, it does not take energy consumption into consideration. It also causes the network to be flooded with RREQs and RREPs. This produces a massive overhead during the route discovery phase, which may lead to network congestion.

2.2 Maximal minimal nodal residual energy ad hoc on-demand multipath distance vector

Liu et al. [14] introduced an energy-aware multipath routing protocol called MMRE-AOMDV. The MMRE-AOMDV protocol basically exploits the available routing information that already exists in the underlying AOMDV protocol. Thus, little additional overhead is required to compute the maximal nodal residual energy in the route. The MMRE-AOMDV routing protocol exploits the MMRE concept. It balances the nodal energy consumption as it selects and routes packets over multiple paths based on minimum nodal residual energy. The MMRE-AOMDV protocol detects the minimal nodal residual energy of each route in the route discovery process, then sorts the multiple routes in descending order of nodal residual energy, and finally starts with the maximal residual energy route to forward data packets.

MMRE-AOMDV [14] outperforms AOMDV in terms of packet delivery fraction, throughput, and network lifetime, but suffers from an increasing number of dead nodes as the data load increases.

2.3 Load balancing multipath routing protocol

Effective load balancing is a challenging task in MANETs because of their dynamic behavior and unpredictable topology changes. The load should be efficiently distributed through the network. Otherwise, heavily-loaded nodes may cause a bottleneck, resulting in congestion, larger delays, and worse network performance. With the increasing interest in multipath routing, load balancing became a key issue in MANETs. Many multipath routing protocols have considered the best technique for load balancing.

Some researchers have dealt with the load balancing concept by picking the best path from all of the generated paths to send data. Hassanein and Zhou [10] proposed a load-balancing routing (LBR) protocol that exploits the node activity and traffic interference to select the source–destination path that encounters the minimum traffic load for transmission and the minimum interference by nodes in the neighborhood.

Song et al. [26] proposed a load-aware on-demand routing (LAOR) protocol for MANETs. During the route selection phase, LAOR selects the optimal path based on the estimated total path delay and hop count. The delay of each node is calculated based on packet arrival times and packet transmission times.

LBR and LAOR depend on sending data over the best path (single path routing) [20] considering energy, traffic load, or even hop count, so they do not strictly apply the load balancing concept. Load balancing basically depends on balancing data loads across multipaths. Protocols such as LBR and LAOR tend to maximize delay, energy consumption, and the number of dead nodes as they deplete the selected path.

Many researchers have concentrated on the ranking and energy status of paths, ignoring how to balance the data load itself. Most studies have concentrated on distributing the data load equally across the selected paths. Lee et al. [13] presented a workload-based adaptive load balancing technique that uses the idea of dropping RREQs depending on the load status of each node; thus, nodes can be excluded from route paths. Their algorithm uses the message queue length in the nodes and the outstanding workload, defined as the combination of queue length and residence time of packets in the queue.

Nagarjun et al. [35] proposed a packet count-based routing mechanism. This extension of the DSR protocol selects the least-used path for sending data packets, rather than selecting the minimum hop count as in DSR.

Deshmukh and Raisinghani [6] presented the energy-efficient and load balancing multi-path (EALBM) routing protocol to exploit multiple paths at the same time. EALBM consists of three phases: neighbor discovery, multipath discovery, and data transmission. The source node initiates multipath discovery processes to determine all existing disjoint multipaths from source to destination. Each disjoint path is assigned a weight based on the energy level of nodes along that path, with lower weights signifying preferred paths. EALBM was tested in four different scenarios, and exhibited a noticeable improvement over AOMDV in terms of packet loss, latency, and normalized load.

As this section has shown, a number of routing protocols have tried to achieve optimal load balancing, but all suffer from some deficiencies. In the next section, the proposed LBMMRE-AOMDV protocol is discussed in detail.

3 LBMMRE-AOMDV

This section explains the basic operations of the LBMMRE-AOMDV protocol, as well as its more complex path maintenance and load balancing methodologies.

The LBMMRE-AOMDV protocol involves two phases. The first generates link disjoint paths and maintains them in case of one or more path failures. The second phase balances the data load among the generated link-disjoint paths.

3.1 Disjoint path discovery and maintenance

This phase of the proposed protocol is mainly based on the generation of multi-link disjoint paths in MMRE-AOMDV and AOMDV. The major modifications are as follows.

In the original AOMDV and MMRE-AOMDV, if a node receives several redundant copies of the same RREQ, all duplicate copies are examined for potential alternatives. In LBMMRE-AOMDV, however, redundant RREQs with the same < source address, request id > pair will be discarded.

Second, in the standard MMRE-AOMDV protocol, new path discovery only starts when one or more paths fail, and an RERR message is forwarded to the source when the last path to the destination breaks. The LBMMRE-AOMDV protocol only starts to forward the RERR at the beginning of the new transmission round if

$$ {\text{N }} = {\text{ N}} - 2$$
(1)

where N is the number of generated disjoint paths. The LBMMRE-AOMDV protocol permanently requires a spare path to move data on if any path fails, as well as an external path for the load balancing phase. The LBMMRE-AOMDV protocol relies on switching the data transmission between paths so as not to consume the paths’ energy. For example, if four disjoint paths are available, only three will be used for transmission, and the fourth will be used as a spare in case any of the working paths fail. If two paths fail, the transmitted data may be lost, as the transmission power needed for the data may exceed the available paths’ power. Preventing this scenario is an important area of study. In the first transmission round, assume that paths 1, 2, and 3 will be used for transmission. In the second round, the path with the maximum consumed energy will be replaced by the spare one, and the transmission will continue.

Similar to MMRE-AOMDV, the LBMMRE-AOMDV protocol sorts the generated paths in descending order of nodal residual energy, and uses the path with the maximal nodal residual energy to forward data packets. The LBMMRE-AOMDV protocol computes the maximum number of packets the path can transmit, but this must not exceed the maximum useable bandwidth of the path.

The LBMMRE-AOMDV protocol involves:

  1. 1.

    Generating the N link-disjoint paths.

  2. 2.

    Sorting the generated N link-disjoint paths in descending order based on the maximal nodal residual energy [11]:

    $$ \upmu_{\text{j}} = \mathop {\hbox{min} }\limits_{{{\text{i}} \in {\text{k}}}} {\text{E}}_{\text{ij}} $$
    (2)

    where Eij is the residual energy of node i on path j and µj is the nodal residual energy of path j.

  3. 3.

    Setting the path with the minimal nodal residual energy as a spare path, and continue with the remaining N-1 link-disjoint paths.

  4. 4.

    Computing the maximum number of packets the path can transmit [11]:

    $$ \upalpha = \left( {\sum\limits_{i = 1}^{k - 1} {T\left( {n_{i} ,n_{i + 1} } \right)} } \right) $$
    (3)

    where α is the energy consumed for one packet, ni,…, nk−1 are the nodes in the path, and T denotes the energy consumed in transmitting and receiving a packet over one hop. The maximum number of packets that can be transmitted over path j is:

    $$ {\text{P}}_{\text{j}}^{\max} = \frac{{\upmu_{\text{j}} }}{\alpha } $$
    (4)
  5. 5.

    Computing the actual number of packets that can be transmitted over path j:

    $$ {\text{ATP}}_{\text{j}} = \frac{{\mu_{j} \times ATP}}{{\mathop \sum \nolimits_{j = 1}^{N - 1} \mu_{j} }} $$
    (5)

    where ATP is the actual total number of packets to be transmitted from source to destination on a network. ATPj depends on the ratio of the residual energy of path j to the total residual energy of all generated paths.

  6. 6.

    Checking which of Pmaxj or ATPj is smaller and start the transmission process.

  7. 7.

    Repeat steps 2–7 until the transmission is complete.

For example the following graph represents a MANET, where S is the source node and D is the destination node. A, B, C, E, and M are the intermediate nodes (the residual energy of these nodes is shown next to the node). Applying LBMMRE-AOMDV to send 50 packets from S to D involves the following steps:

First:

the source S propagates an RREQ to the destination node, where duplicated RREQs from the same source nodes are ignored, as shown by the black arrows

Second:

all available link-disjoint paths are generated:

$$ {\text{Path }}1: \, \left[ {\text{S - E - D}} \right] $$
$$ {\text{Path }}2: \, \left[ {\text{S - A - B - D}} \right] $$
$$ {\text{Path }}3: \, \left[ {\text{S - M - C - D}} \right] $$
Third:

to calculate each generated path’s nodal residual energy (µj), the source S and destination D are excluded from the calculations:

$$ \upmu_{1} = \hbox{min} (120) = 120 $$
$$ \upmu_{2} = \hbox{min} (100,70) = 70 $$
$$ \upmu_{3} = \hbox{min} (90,130) = 90 $$

The paths are then sorted in descending order of nodal residual energy, and the path with the least energy is set as the spare path:

  1. 1.

    Path 1: [S-E-D]

  2. 2.

    Path 3: [S-M-C-D]

  3. 3.

    Path 2: [S-A-B-D] (set as spare path)

Fourth:

Pmaxj and ATPj are calculated as in Table 1.

Table 1 LBMMRE-AOMDV calculations
Full size table

Table 1 indicates that path 1 can transmit 28 of the 30 packets. This is the maximum the path can transmit, but deplete the path energy. Path 3 can only transmit 15 out of 21 packets. Finally, the previous steps will be repeated until the transmission has been completed. The next section gives a detailed description of the simulation environment (Fig. 1).

Fig. 1
figure 1

Route selection using LBMMRE-AOMDV

Full size image

4 Simulation settings

4.1 Simulation environment

The performance of LBMMRE-AOMDV, MMRE-AOMDV, and AOMDV was evaluated using the Network Simulator (NS) v2.34 [36]. NS is a discrete event simulator targeted at networking research, and provides substantial support for the simulation of TCP, routing, and multicast protocols over wired and wireless networks.

NS began as a variant of the REAL network simulator in 1989, and has evolved substantially over the past few years. In 1995, NS development was supported by DARPA through the VINT project at LBL, Xerox PARC, UCB, and USC/ISI. Currently, NS development is supported through DARPA with SAMAN and through NSF with CONSER, both in collaboration with other institutes including ACIRI. The simulation settings and parameters employed in the experiments are summarized in Table 2.

Table 2 Simulation parameters
Full size table

4.2 Performance metrics

The following metrics were considered in the evaluation:

  • Packet delivery ratio the ratio of the number of data packets delivered to the destination. Packet delivery ratio is obtained by dividing the number of data packets correctly received at the destination by the number of data packets sent by the source.

  • End-to-end delay average delay of data packets from source to destination.

  • Average energy consumption average energy consumed by all nodes in the network.

  • Routing overhead the number of control packets transmitted through the network.

  • Number of dead nodes number of nodes dropping out of the network at different simulation times.

5 Results and discussion

5.1 Packet delivery ratio

The packet delivery ratio was tested for packet sizes of 512 and 1024 bytes. Figure 2 illustrates how many 512-byte data packets each protocol delivers successfully. LBMMRE-AOMDV exhibited a higher packet delivery ratio than MMRE-AOMDV and AOMDV for all numbers of nodes. For example, with 10 nodes, the LBMMRE-AOMDV packet delivery ratio was 99 %, compared with 97 % for MMRE-AOMDV and 91 % for AOMDV. With 200 nodes, LBMMRE-AOMDV successfully delivered 85 % of packets, whereas MMRE-AOMDV delivered 80 % and AOMDV delivered just 79 %. It is clear that the packet delivery ratio of LBMMRE-AOMDV is less affected by the simulation time than the other two protocols.

Fig. 2
figure 2

Packet delivery ratio for different numbers of nodes, packet size 512 bytes

Full size image

Figure 3 demonstrates how many 1024-byte data packets each protocol delivers successfully. It can be seen that the packet delivery ratio is generally lower for this higher packet size. With 10 nodes, the LBMMRE-AOMDV packet delivery ratio was 97 %, compared with 94 % for MMRE-AOMDV and 85 % for AOMDV. With the maximum of 200 nodes, LBMMRE-AOMDV achieved a packet delivery ratio of 83 %, whereas MMRE-AOMDV achieved 75 % and AOMDV scored just 63 %. AOMDV suffers a higher attrition rate in both cases.

Fig. 3
figure 3

Packet delivery ratio for different numbers of nodes, packet size 1024 bytes

Full size image

5.2 End-to-end delay

Figure 4 shows the average end-to-end delay with different numbers of packets. LBMMRE-AOMDV suffered the highest average end-to-end delay, followed by MMRE-AOMDV and AOMDV. This is because the main goal of LBMMRE-AOMDV is to deliver the maximum possible amount of data safely. LBMMRE-AOMDV averaged 2.47 s end-to-end delay for 1000 packets, whereas AOMDV achieved the lowest average end-to-end delay of 1.89 s. It is clear that the increase in the average end-to-end delay with respect to the number of packets is much higher for LBMMRE-AOMDV than the other two protocols.

Fig. 4
figure 4

Average end-to-end delay with respect to the number of packets

Full size image

5.3 Average energy consumption

Reducing energy consumption is an important goal. Figure 5 shows that the average amount of energy consumed by LBMMRE-AOMDV is much less than that of the other two protocols. It can also be seen that the rate of increase in energy consumed is less for LBMMRE-AOMDV than for MMRE-AOMDV and AOMDV. The highest energy consumption was 0.49 J by AOMDV with 200 nodes, whereas LBMMRE-AOMDV consumed just 0.35 J for the same topology.

Fig. 5
figure 5

Average energy consumption with respect to the number of nodes

Full size image

5.4 Routing overhead

Lowering overheads is a goal of all routing algorithms, as it implies lower energy consumption, fewer dead nodes, and less traffic. The overhead was tested for different pause times, as the pause time represents the time for which the nodes freeze and the effect of their mobility disappears.

As Fig. 6 illustrates, LBMMRE-AOMDV achieved a notable decrease in routing overhead. For a 10 s pause time, LBMMRE-AOMDV incurred an overhead of 0.32, compared with 0.38 for AOMDV. LBMMRE-AOMDV also achieved a lower overhead than MMRE-AOMDV. Finally, it is clear that the attrition in the routing overhead is higher for LBMMRE-AOMDV than for the other two protocols.

Fig. 6
figure 6

Routing overhead with respect to pause time

Full size image

5.5 Number of dead nodes

The fewer dead nodes suffered by LBMMRE-AOMDV is a clear advantage over MMRE-AOMDV. The number of dead nodes was counted at different simulation times when sending 1000 512-byte packets over 50 and 100 nodes.

Figure 7 plots the number of dead nodes at various simulation times in a network of 50 nodes. Under LBMMRE-AOMDV, only three nodes were dead after a 900 s simulation, whereas MMRE-AOMDV suffered three times more than this number. Figure 8 shows the number of dead nodes in a 100-node network over a 900 s simulation. The difference between LBMMRE-AOMDV, MMRE-AOMDV, and AOMDV decreases in this instance, but LBMMRE-AOMDV still outperforms the other protocols.

Fig. 7
figure 7

Number of dead nodes (out of 50) at various simulation times

Full size image
Fig. 8
figure 8

Number of dead nodes (out of 100) at various simulation times

Full size image

The above results indicate that LBMMRE-AOMDV is superior to MMRE-AOMDV and AOMDV in terms of maximizing packet delivery ratio, reducing energy consumption, minimizing the number of dead nodes, and decreasing the routing overhead. However, LBMMRE-AOMDV suffers from higher end-to-end delay, as it is basically designed to deliver the maximum number of packets with the minimum energy, taking into account the number of dead nodes. Hence, LBMMRE-AOMDV is highly applicable in systems that are focused on the delivery of data, such as banking and online shopping.

6 Conclusions

A new load balancing multipath routing protocol (LBMMRE-AOMDV) has been proposed in this research. The LBMMRE-AOMDV protocol evaluates the generated paths to determine the maximal nodal residual energy and the actual number of packets that can be transmitted over that path without depleting the nodes’ energy.

The performance of LBMMRE-AOMDV relative to MMRE-AOMDV and AOMDV was studied under a wide range of scenarios using NS v2.34. LBMMRE-AOMDV achieved better performance in four of the five evaluation metrics, but encountered higher end-to-end delay.

In applying LBMMRE-AOMDV, the tradeoff between node energy consumption and the data load to be transmitted over the network is effectively balanced. It is recommended that LBMMRE-AOMDV be applied in systems where the delivery of data is especially important, as in banking, plane reservations, and online shopping.