Introduction
A Mobile ad hoc network (MANET) is a wirelessly interconnected class of networks where nodes can freely move and communicate directly with any nearby neighbors. Owing to this mobility characteristic, MANET is normally a self-configuring and infrastructure-less network and thus, can be dynamically formed under any topology [1]. However, there should not be any centralized infrastructure in a MANET. In contrast to the infrastructure-based wireless network, where the deployment of administering devices, e.g., base stations or access points, is required for the network operation, each node in a MANET must be able to send, receive, and relay network packets [2].
Owing to the flexibility in the architecture, MANETs are highly versatile and thus, can be beneficial for a variety of applications [3]. For example, they can be employed by many military units [4], [5], [6] because their rapid deployment does not require any previously installed network resources, thus facilitating the establishment of an information communication system between the soldiers on duty. In addition, MANETs can be exploited for public safety and disaster management [7], [8]. For instance, during natural hazards, existing telecommunication towers may be dysfunctional and an instant installation of a wireless ad hoc communication system is extremely critical for the rescue party to communicate with one another while supporting the endangered victims [9]. Furthermore, the dynamic topology nature of this network type enables the rescuers to change their positions without losing connectivity with the rest of the team [10].
Considering these application areas, MANET routing protocols have been intensively studied in the literature [11], [12] owing to their importance in deciding the successful operation of a MANET system. However, despite the ease of the establishment process, MANET routing protocols are uniquely presented with many challenges [3], [13]. First, owing to the limited range of radio communication links, nodes within the network must maintain multi-hop paths between one another [14], [15]. In addition, as the nature of MANET is typically characterized by numerous properties, MANET routing protocols must be designed to address them upon discovering the paths. A few examples are limited battery capacity [16], security [17], neighboring signal strength [18], link reliability [19], or their combinations [20], [21]. Moreover, following the determination of the paths, a fault-tolerant transmission strategy is required to guarantee that critical data packets are sent to the destination without substantial delays. To the best of the authors’ knowledge, only a few of the proposed routing protocols focus on both an efficient routing scheme and a fault-tolerant capability for packet transmissions.
This study proposed a fault-tolerant ad hoc on-demand routing protocol, referred to as FT-AORP. It provides reliable transmission for the deployment of MANETs in scenarios where safety-critical information must be guaranteed to be successfully exchanged amongst nodes in the network. The main contributions of this study are as follows.
A path selection strategy employing three different routing metrics relevant to MANET characteristics: node mobility, radio signal strength measurement, and energy usage rate, was proposed to identify the optimal paths to the destination for data transmission. These routing metrics can be easily collected without requiring any supplemental sensor devices.
We developed a simple multipath discovery scheme that returns, if possible, more than one path towards the destination for the requesting source node. Based on these determined paths, the source node can select the two desired ones using the aforementioned selection strategy. Then, we introduced a fault-tolerant transmission technique that involves duplicating the important data packets and transmitting them using two separate node-disjointed paths. This fault-tolerant design ensured that packets were delivered successfully even if transmission issues occurred in one path.
We implemented the proposed protocol as a simulation framework using OMNeT++ [22] and modeled the evaluation testbed as close to the real-world environment as possible with various configurable simulation parameters. Moreover, by employing several evaluation metrics, the better performance of the proposed protocol compared to other revisited routing protocols was demonstrated in many testing scenarios.
The rest of this paper is organized as follows. In Section II, certain relevant state-of-the-art studies that have addressed the MANET routing problem are reviewed. Section III presents the problem formulation through a system model and introduces the proposed routing metrics for the path selection issue. In Section IV, the routing protocol is described in detail, including the route request, route reply, and node discovery schemes. The performance of the proposed routing protocol indicated by simulation results is evaluated in Section V. Finally, the conclusions are presented in Section VI.
Related Work
A. Fundamental Routing Protocols
Routing schemes for MANETs have been extensively studied in the literature. Pioneering routing protocols can be classified into two main categories: proactive and reactive protocols [23]. Several well-known proactive protocols are destination-sequenced distance vector (DSDV) [24], global state routing (GSR) [25], and optimized link state routing (OLSR) [26]. Meanwhile, certain popular reactive routing solutions that have been proposed to reduce the overheads of proactive approaches are ad hoc on-demand distance vector [27], dynamic source routing (DSR) [28], and temporally ordered routing algorithm (TORA) [29]. Such protocols have mostly been adapted from traditional routing schemes for wired networks with minor modifications for wireless networks. Consequently, they were originally designed to select the route with the minimum hop count to transmit the packets through. Although this hop count metric is straightforwardly useful in cabled networks as the network components are often static, MANETs are more dynamic and the number of intermediate nodes between the source and destination is thus highly likely to change over time.
B. State-of-the-Art Routing Metrics
Considering the limits of the hop count, many studies have incorporated different routing metrics into MANET routing protocols. Taha et al. [16] proposed an energy-efficient multipath routing protocol that adopted a fitness function as an optimization method to select the best route based on two criteria: the number of intermediate nodes and their remaining energy level. Although this scheme can prolong the network lifetime, the power consumption rate alone appeared relatively insufficient when considering aggressive scenarios with more factors affecting the connection links between network nodes. For instance, when an arbitrary node is in an isolated area, it is certainly not an ideal next hop for the entire route although it might have sufficient energy supply. Therefore, more measures are being exploited to design routing protocols.
For example, Chen et al. [30] proposed a topological change adaptive ad hoc on-demand multipath distance vector (TA-AOMDV) routing protocol that can adapt to the aggressively dynamic nature of mobile networks. Through the combination of individual node information (i.e., residual energy, queue length, and current bandwidth) as route selection metrics with the probability of link stability between nodes, the proposed scheme exhibited better performance in many notable metrics such as packet delivery ratio and end-to-end delay. However, while the protocol is a prospective choice for applications in high-speed MANETs with quality-of-service (QoS) constraints, it may not be suitable for life-critical systems as its packet delivery rate performance is not consistently satisfactory as the network nodes move chaotically fast (e.g., 30 m/s and higher).
In a similar manner, Dhananjayan and Subbiah [31] proposed a trust-aware ad hoc routing protocol using stability factors such as energy level, mobility, and RSSI-based distance measurement from each node’s accumulated logging information to select the optimal next hop from surrounding neighbors. Simulation results showed that this reputation-based protocol achieved high throughput, improved packet delivery rate, and low end-to-end delay. However, the log collection and examination process performed by each node might demand enormous computational costs and subsequently high-power consumption, which is normally limited for resource-constrained MANETs.
More recently, Sirmollo and Bitew [32] proposed a mobility-aware routing scheme for MANETs. This protocol takes multiple factors into consideration, such as the speed of the nodes, the relative distance between them, and their residual energy level, to choose the best nodes to forward the packets to during the route request and route discovery phases. Simulation results also demonstrated the superior performance over other routing protocols. However, the proposed scheme mainly relies on the calculation of the node distance, which requires an accurate positioning system. In reality, this might not always be possible, especially when it comes to indoor contexts.
C. Fault-Tolerant Routing Protocols
Regarding fault tolerance in MANETs, Nsaif et al. [33] introduced an approach referred to as seamless routing for wireless ad hoc networks (SRAD). Here, each pair of nodes had two link-disjointed paths, which were used to transmit two redundant frame copies to the destination such that zero-recovery time was achieved in the case where one of the operating paths fails. Instead of using the shortest paths, the path selection is based on its bit error rate (BER) measurement. However, the process to calculate the BER for the links is unclear and the proposed protocol has been evaluated for a benign scenario only (e.g., the network containing only 21 nodes moving at 10 m/s).
Song et al. [34] proposed several topology control algorithms employing the Kalman filter, which can anticipate the movement tendency of other surrounding nodes and consequently adjust its movement to maintain wireless links with other nodes. In addition, they are localized algorithms wherein no more than two hops’ information is required. Simulation results against node velocity and the number of cluster members showed that one of the proposed schemes can effectively restore connectivity while maintaining a minimal deviation from the original task-based direction. However, these proposed algorithms require the network nodes to change their movement patterns, which may not always be plausible owing to the highly unpredictable MANET mobility [35].
Recently, Srilakshmi et al. [36] proposed a secure optimization routing protocol that simultaneously addresses the energy and communication issues of MANETs. In detail, there are certain cluster heads in the network that are in charge of routing the packets, and they are chosen based on their calculated trust values. However, the trust values are mainly derived from the transmission duration, which is partially susceptible to the dynamic nature of MANETs. Interestingly, Pattnaik et al. [37] presented a multipath routing scheme for MANETs, which makes use of De Casteljau’s algorithm with the Bezier curve for the mobility awareness of multiple speed levels. The optimal routing path for data transmission is then selected based on various factors. Routing in obstacle-ridden environments is certainly a promising research topic. However, it is outside of the scope of this work and can be of great potential for our future research directions.
In addition, Naseem et al. [38] proposed a novel energy-efficient routing protocol for MANETs that also employs manifold routing criteria, such as the number of hops, the round-trip time, and the remaining energy level, to discover the optimal data transmission path. Additionally, it is also a multipath-enabled routing scheme that aims to offload the data transmission among various paths for load balancing. In contrast, in our work, the discovered paths are used to simultaneously send data packets to the desired destination node. As a result, we can guarantee the maximization of fault tolerance for MANETs. Likewise, Sarhan and Sarhan [39] employed the elephant herding optimization algorithm to choose the routing paths with optimal residual energy in an on-demand multipath routing protocol called EHO-AOMDV. Then, various paths are also used for the data transmission’s load balancing between the source and destination nodes. The actual number of packets assigned to a path will be determined using the minimum energy level of its intermediate nodes, which ensures that the path with higher residual energy will be responsible for relaying more data packets.
Problem Statement
In this section, we describe the general system model, formulate the routing problem, and introduce our proposed routing metrics as part of the routing protocol. The commonly used notation in this paper is shown in Table 1.
A. System Model and Problem Formulation
A path
consisting ofp_{ij} nodes is denoted asl , wherep_{ij} = [v_{i},\ldots,v_{j}] with\lVert p_{ij} \rVert = l being the cardinality of a set;\lVert \cdot \rVert For two adjacent nodes, e.g., nodes
andv_{i} , a bidirectional link is denoted asv_{i+1} ;(v_{i}, v_{i+1}) \in E There should be
possible paths betweenk andv_{i} , they collectively form a routev_{j} , wherer_{ij} = \left [{ p_{ij}^{(1) },p_{ij}^{(2) },\ldots,p_{ij}^{(k)} }\right] .\lVert r_{ij} \rVert = k
Next, to maximize the fault-tolerant capability, discovered paths should be node-disjointed [42], [43] instead of simply link-disjointed. This is because, for two node-disjointed paths, there is no common node, whereas link-disjointed paths can share one or more intermediate nodes, as depicted in Fig. 1. In this example, following the node-disjointed design scheme, the routing protocol can avoid the situation where a single point of failure occurs at the single common node of two paths, which is denoted as node
In addition, as this study considered \begin{equation*} \Theta ^{(p)} = \frac {1}{l} \sum _{v_{i} \in p} \Phi ^{(v_{i})}.\tag{1}\end{equation*}
Definition 1:
From many possible paths between nodes
Therefore, in the proposed study, the act of selecting the two optimal paths was equal to selecting the two paths with the two largest routing measures
B. Node Routing Measure
In the proposed scheme, when the network nodes are operating, each one computes its own node routing measure
Mobility indicator
;\Phi _{m} Neighboring signal strength
;\Phi _{s} Energy level
.\Phi _{e}
The proposed routing metrics can be easily obtained from commercially available wireless products without any additional designated sensors or peripherals. In particular, the mobility indicator suggests the tendency of a node to change its neighbors, neighboring signal strength indicates if a node is within an area of strong wireless signal coverage, and energy level reveals the current energy level of a node and its power consumption rate. Finally, the routing measure \begin{equation*} \Phi ^{(v)} = \Phi _{m} + \Phi _{s} + \Phi _{e}.\tag{2}\end{equation*}
1) Mobility Indicator
Mobility indicator metric was first proposed in [44] to incorporate the mobility pattern of a node considering changes in its neighboring nodes. A node is deemed more reliable to be part of a transmission link if it tends to stay with a higher number of other surrounding nodes. The mobility indicator \begin{align*} \Phi _{m}(t) \!=\! \begin{cases} 0, & \text {if}~\lVert N^{(v)}_{t} \rVert \!=\! \lVert N^{(v)}_{t- \Delta t} \rVert \! =\! 0, \\ \sqrt {\dfrac {\lVert N^{(v)}_{t} \cap N^{(v)}_{t- \Delta t} \rVert }{\lVert N^{(v)}_{t} \cup N^{(v)}_{t- \Delta t} \rVert }}, & \text {otherwise,}~\end{cases} \tag{3}\end{align*}
Lemma 1:
Proof:
First, it is evident from (3) that, in the case of
From Lemma 1, it is apparent that the fewer the changes in the neighbor set at the two different time instances, the larger the value of
2) Neighboring Signal Strength
Mobility indicator suggests the change rate in the number of neighboring nodes within a certain amount of time. However, this information alone does not indicate whether the node is currently within a sufficiently close distance to properly receive the radio signal from other transmitting nodes. Therefore, this study introduced the neighboring signal strength metric that employs the received signal strength indicator (RSSI) to show the proximity of a node within the transmission ranges of its neighbors.
As a node receives a packet from one surrounding node, it can retrieve information on the strength level of the signal, from which it successfully receives that packet. In particular, for \begin{align*} \beta=&\left \{{\dfrac {(\Gamma (v,v_{i}))^{-1}}{\sum _{v_{i} \in N^{(v)}_{t} }(\Gamma (v,v_{i}))^{-1}} \mid v_{i} \in N^{(v)}_{t} }\right \} \\=&\left \{{ \gamma _{v_{i}} \mid v_{i} \in N^{(v)}_{t} }\right \},\tag{4}\end{align*}
\begin{equation*} 0 < \gamma _{v_{i}} \leq 1,\tag{5}\end{equation*}
\begin{equation*} \sum _{v_{i} \in N^{(v)}} \gamma _{v_{i}} = 1.\tag{6}\end{equation*}
\begin{align*} \Phi _{s}(t) = \begin{cases} 0, & \text {if}~\lVert N^{(v)} \rVert = 0,\\ - \dfrac {\sum _{v_{i} \in N^{(v)}} \gamma _{v_{i}} \ln \gamma _{v_{i}}}{\ln (\lvert \bar {\alpha } \rvert + \lVert N^{(v)} \rVert) }, & \text {otherwise,}~\end{cases}\tag{7}\end{align*}
Lemma 2:
Proof:
From (7), for \begin{align*} \sum _{v_{i} \in N^{(v)}} \gamma _{v_{i}} \ln (\gamma _{v_{i}})=&\sum _{v_{i} \in N^{(v)}} \gamma _{v_{i}} \ln \left ({\frac {\gamma _{v_{i}}}{1} }\right) \\\geq&\left ({\sum _{v_{i} \in N^{(v)}} \gamma _{v_{i}} }\right) \ln \frac { \sum _{v_{i} \in N^{(v)}} \gamma _{v_{i}} }{ \sum _{v_{i} \in N^{(v)}} 1 } \\=&-\ln \lVert N^{(v)} \rVert,\tag{8}\end{align*}
In particular, this study exploited the characteristics of the entropy concept [48] to compute the routing metric
Remark 1:
The entropy value of a set has the following relevant properties, which can be used to describe the relationship between the RSSI values
should be proportional to\Phi _{s} , implying that a small increase or decrease in\gamma _{v_{i}} values result in a small increase or decrease in\gamma _{v_{i}} , respectively. According to this property, a node obtaining higher RSSI values exhibits a higher\Phi _{s} value, thus, it is more likely to be chosen to be part of a routing path;\Phi _{s} should be maximal if\Phi _{s} values are equally likely. This implies that if all RSSI values are equally high, the node is in an area with strong signal coverage and therefore becomes an optimal candidate to be included in a routing path. However, there is a case when\gamma _{v_{i}} values are equally low and\gamma _{v_{i}} still has its maximum value. To overcome this, the denominator\Phi _{s} as given in (7) was introduced. With\ln \left ({\lvert \bar {\alpha } \rvert + \lVert N \rVert }\right) being the absolute value of the mean of the RSSI set, this implies that if all the RSSI values are equally small, the\lvert \bar {\alpha } \rvert of the node will be divided by a large value as the absolute value of a non-positive RSSI value is being used. In contrast, if all the RSSI values are equally high,\Phi _{s} will be larger.\Phi _{s}
3) Energy Level
Assume that a node is able to acquire its battery level at time \begin{align*} \Phi _{e} (t)\,\,= \begin{cases} 0, & \text {if}~E^{(v)}_{t} < \zeta, \\ \dfrac {E^{(v)}_{t} } {E^{(v)}_{t-\Delta t}}, & \text {otherwise,}~\end{cases}\tag{9}\end{align*}
Lemma 3:
Proof:
First, because the battery level is always non-negative,
Through the introduction of this metric, this study aimed to calculate the power consumption rate of a node and make decisions accordingly. For example, if the node is quickly drawing power from its battery for network activities such as packet transmission or reception (i.e.,
C. Path Routing Measure
Now, recall that path \begin{equation*} \Theta ^{(p)} = \frac {1}{l} \sum _{v_{i} \in p} \Phi ^{(v_{i})} = \frac {1}{l} \sum _{v_{i} \in p} \left ({\Phi ^{(v_{i})}_{m} + \Phi ^{(v_{i})}_{s} + \Phi ^{(v_{i})}_{e} }\right).\tag{10}\end{equation*}
Lemma 4:
Proof:
First, from Lemmas 1 to 3, it is clear that for every \begin{align*} \max {\Theta ^{(p)}}=&\max { \frac {1}{l} \sum _{v_{i} \in p} \left ({\Phi ^{(v_{i})}_{m} + \Phi ^{(v_{i})}_{s} + \Phi ^{(v_{i})}_{e} }\right) } \\\leq&\frac {1}{l} \sum _{v_{i} \in p} \max {\left ({\Phi ^{(v_{i})}_{m} + \Phi ^{(v_{i})}_{s} + \Phi ^{(v_{i})}_{e} }\right)} \\leq&\frac {1}{l} \sum _{v_{i} \in p} \left ({\max {\Phi ^{(v_{i})}_{m}} + \max {\Phi ^{(v_{i})}_{s}} + \max {\Phi ^{(v_{i})}_{e}} }\right) \\=&\frac {1}{l} \sum _{v_{i} \in p} \left ({1 + 1 + 1 }\right) \\=&\frac {3\lVert p \rVert }{l} \\=&3,\tag{11}\end{align*}
From Definition 1, the act of selecting the best path is equal to selecting the route with the maximum path measure
Theorem 1:
For a path with the maximum
Proof:
From Lemmas 1 and 4, it is evident that one of the conditions for achieving the maximum value of path measure
Theorem 2:
For a path with the maximum
Theorem 3:
For a path with the maximum
Proof:
From Lemmas 3 and 4, it can be observed that one of the conditions for achieving the maximum value of path measure
From (10), it is observed that the routing measure for a path is the summation of the routing metrics of all the nodes in that path, including the source and the destination nodes. However, a node is not required to know the entire network topology to calculate the routing measure for every possible path between itself and the desired destination node. In fact, this computation is distributedly performed by each intermediate hop during the route discovery procedure, which is addressed in the next section.
Proposed Routing Protocol
In this section, a fault-tolerant ad hoc on-demand routing protocol (FT-AORP) is presented. First, the manner in which the conduction of the route discovery procedure as a source node requires the transmission of a data packet to a specific destination (route information is not yet available) is discussed. Next, after the source node acquires the route information of the destination node inside its routing table, a fault-tolerance scheme of data packet transmission was proposed, wherein two duplicates of the original data packet were sent over the network to guarantee reliable transmission for critical data packets.
A. Route Discovery
The route discovery strategy of FT-AORP is partially based on the well-known ad hoc on-demand distance vector (AODV) routing protocol [27] with certain modifications for the multipath routing purpose. Similar to the AODV protocol, there are two phases from the point the source node initiates the route discovery until it is responded to with the requested route: route request (RREQ) and route reply (RREP). In general, the route request process floods the RREQ packets into the network and as they reach the desired destination node, it sends back the RREP packets to the source node via unicast.
1) Route Request
RREQ is a broadcast packet that is sent by a source node if it does not know a route to a destination. Thus, the source node wants to send a data packet to a certain node and it searches its routing table for an entry that contains relevant information regarding the destination node. As the node finds nothing, it starts the route request process by broadcasting the RREQ packet. The format of the RREQ packet is shown in Fig. 2. It should be noted that all the packet structures proposed in this paper are for illustrative purposes only and are not byte aligned.
As evident from Fig. 2, the RREQ packet defines the following fields:
Type is the type of FT-AORP control packets and RREQ packet is type number 1;
is the unknown sequence number flag, indicating that the destination sequence number is unknown;{U} Hop Count is the number of intermediate hops from the originator node of an RREQ packet to the node currently handling it. This value is incremented for every node that the RREQ packet passes;
RREQ ID is a monotonically increasing number that, coupled with the originator IP address, uniquely identifies an RREQ packet. RREQ ID number is incremented by one whenever an RREQ packet is created;
Destination IP Address is the IP address of the destination node of the route that is being discovered;
Destination Sequence Number is the most recently received sequence number by the originator for any route to the destination;
Originator IP Address is the IP address of the node that started the route discovery and initiated the route request;
Originator Sequence Number is the current sequence number to be used for the route entry to the initiator of the route request;
Routing Measure is the accumulated routing measure value
of all the nodes from the originator node to the current node. The routing measure of a node is computed using (2).\Phi
Before eventually sending the RREQ packet, the source node must encapsulate its RREQ-identifying information inside. Thus, it increments its own RREQ ID number by one and embeds this value inside the RREQ ID field of the packet. Later, as other nodes receive this broadcasted RREQ packet, they can check whether it has received the earlier copy before by examining both the RREQ ID and Originator IP Address fields. In addition, each node maintains a sequence number such that other nodes can check for this information by examining the Originator Sequence Number field to ensure that it is updated with the originator node regarding the routing control packets. The route request process performed by the source node is described in Fig. 3.
If a node receives an RREQ packet, it (with the exception of the destination node), determines whether it has received an earlier RREQ packet with the same RREQ ID and Originator IP Address or not. If it has, the node simply discards the newly arrived RREQ packet to avoid unnecessary dissemination of the RREQ packet all over the network. However, if the node cannot find the RREQ packet’s identity inside its record, it increases the Hop Count field by one, adds its own routing measure value to the accumulated Routing Measure, and rebroadcasts the RREQ packet. In contrast to the original AODV protocol, if the destination node receives RREQ packets, it does not check for any duplications. Instead, it maintains a record of every arrived RREQ packet inside its routing table to enable multipath routing. Subsequently, the destination node responds to each RREQ packet with an RREP packet, which begins the route reply phase.
2) Route Reply
As the destination node receives an RREQ packet, it immediately generates an RREP packet; thus, the number of the RREQ packets possibly reaching the destination is equal to the number of paths between the source and destination nodes. In contrast to the broadcasted RREQs, the RREP responses are performed via unicast as the destination and intermediate nodes already learn the reverse route from the destination back to the source node during the route request period. The format of the RREP packet is shown in Fig. 4.
Specifically, the RREP packet defines the following fields:
Type is the type of FT-AORP control packets and RREP is type number 2;
Hop Count is similar to that defined in the RREQ packet’s structure;
Destination IP Address is the IP address of the destination node of the route. As the RREP packet is always created by the destination node, this field should contain the IP address of the destination itself;
Destination Sequence Number is similar to that defined in the RREQ packet, and its purpose is to ensure that other nodes are up-to-date regarding its routing activities;
Originator IP Address is the IP address of the node that started the route discovery and initiated the route request;
Routing Measure is similar to that defined in the RREQ packet’s structure, except that it is added up from the destination back to the source node. This is because the nodes should have the latest possible information regarding routing measure values of the path.
Analogous to the creation of RREQ packets, the destination node also attaches the necessary information to the RREP packet. In fact, the RREP packet’s structure has fewer fields as it does not need to carry any identifiable information, such as the RREQ ID field, as required in the case of the RREQ packet. However, the RREP packets still must contain their latest sequence number to facilitate other nodes in determining the freshness level of the received RREP packets via the Destination Sequence Number field. Thus, the destination node increments its own sequence number by one every time it sends an RREP packet. In addition, the RREP packet defines the new Routing Measure compared to the conventional AODV protocol, which is initialized with the destination node’s routing measure
Because the RREP packets are sent via unicast, an intermediate hop need not check if it has received the same packet earlier or not. Instead, it increments the Hop Count value by one, adds its own routing measure to the Routing Measure field, and simply forwards the RREP packet to the next hop according to its routing table. However, as the source node receives the RREP packets through which it has requested the route, it updates its routing table with the obtained route information from such RREP packets and becomes ready to transmit the data packet to the desired destination.
An example of the entire route request and route reply procedures is shown in Fig. 5. In this scenario, first, the source node
B. Data Packet Transmission
After a successful route discovery, the source node can finally utilize the paths found to send the data packets. However, as now there can be more than two possible paths to the destination (there is no limit to the number of RREQ packets that the destination node can reply to), the source node is required the decision on which paths to use. As introduced earlier in Definition 1, the optimal path has the largest calculated routing measure
Algorithm 1 Path Selection Algorithm
Input: List
Output: Two selected paths
if
else if
else
end if
From Algorithm 1, it is evident that if there is no path available even after the route discovery scheme, the source is still unable to transmit the data packet. In the case of only one path being found, the two output paths
Finally, as the copies of the data packet reach the destination node, the sequence number attached to a packet is checked to determine whether it has received the same one earlier. If the sequence number of the packet is not in the destination node’s record, it accepts the packet and processes the encapsulated payload. In contrast, if this packet has been already received, the destination node silently ignores it. Thus, by using multipath routing, the reliability of packet transmission is maximized even if one path is not operational.
C. Node Discovery and Routing Table
Along with the route discovery scheme and data packet transmission, the network activities also include node discovery. A node’s discovery of its neighbors enables it to beware of the existence of the other surrounding nodes. Hence, it should be able to compute its own routing measures
Another important component of the routing protocol is the routing table maintained by every node in the network. More specifically, Table 2 presents an example of the routing table with two entries. The routing table has the following fields:
Destination is the IP address of the destination node;
Next hop is the IP address of the next hop that also contains the path information towards the destination node;
Routing measure is the associated cost of the path and is used to determine the optimal path to the destination;
Hop count is the number of intermediate hops that this path includes;
Lifetime is the point of time at which a path in the routing table is considered obsolete. Here, the entry associated with this path is removed from the routing table.
D. Complexity Analysis
Because the route discovery process of the proposed FT-AORP is mainly based on the original AODV protocol, the complexity analysis of FT-AORP can be straightforwardly inferred from the AODV protocol [49], [50]. We describe two classes of complexity that can be used to characterize the proposed algorithm: time complexity and communication complexity.
In detail, time complexity is defined as the amount of time that is required for the entire network to perform a complete protocol operation (in this case, we consider a successful route discovery). Meanwhile, communication complexity denotes the number of protocol messages that are used to do the same task. Without a loss of generality, we assume that the whole network operates in a synchronous manner. This means that all the nodes collectively execute at fixed time instants; in other words, both the processing and propagation delays of packets are negligible for all nodes. Subsequently, FT-AORP has the time complexity of
Similarly, the communication complexity of FT-AORP is
Performance Evaluation
In this section, the proposed routing protocol is implemented in the OMNeT++ discrete event simulator [22] and thus evaluated by conducting various extensive simulation experiments. The performance was assessed in terms of packet delivery ratio, end-to-end delay, and path energy level. In addition, for each evaluation metric above, three network configurations were altered to observe their impact on the overall performance, including the node density or the number of network nodes, the node speed, and the data packet sending rate as follows.
For the node density scenario, node speeds were fixed at 15 m/s and the source node’s sending rate was fixed at 0.5 Mbps;
Regarding the node speed scenario, there were a total of 20 nodes and the source node’s sending rate was also 0.5 Mbps;
For the sending rate scenario, 20 nodes were used, while the node speed was fixed at 15 m/s.
For comparative analysis, four representative routing protocols, namely ad hoc on-demand distance vector (AODV) [27], ad hoc on-demand multipath distance vector (AOMDV) [51], AOMDV with the fitness function (FF-AOMDV) [16], and load-balanced multi-path routing protocol with energy constraints (EE-LB-AOMDV) [38] were employed. It is noted that for the EE-LB-AOMDV protocol, we did not implement the load balancing function and we instead use the discovered paths to transmit multiple copies of the same packet to enable fault tolerance. These protocols were re-implemented in the simulation environment and were provided with the exact same configurations for each simulation run in all scenarios.
A. Simulation Model
In the simulation testbed, every simulation run shared the following configurations. First, various numbers of nodes were initially randomly scattered within a
transmitter power: 1.2 mW;
receiver sensitivity: −87 dBm;
signal-to-noise-plus-interference ratio (SNIR) threshold: 3 dB.
B. Packet Delivery Ratio
Packet delivery ratio (PDR) is computed as the ratio of the number of successfully delivered packets from the source to the destination to the number of generated packets by the source node in a simulation run. This metric is crucial to data-critical packet transmissions because it demonstrates the reliability and fault-tolerant capability of a protocol. Therefore, given \begin{equation*} \textrm {PDR} = \frac {n_{d}}{n_{g}}.\tag{12}\end{equation*}
Fig. 6 shows the evaluation of the PDR performance of five protocols under three different scenarios. First, it was measured as the number of nodes increased from 10 to 80, as shown in Fig. 6a. It is evident that, with only 10 nodes, all the protocols succeeded in delivering more than 90% of the data packets to the destination node. However, as the number of nodes increased to 80, the other four protocols, except for FT-AORP, failed to provide reliable transmission and their PDRs were as low as 0.8. In contrast, FT-AORP guaranteed a PDR of more than 80%, even in the most aggressive scenario of the network density. This may be justified by the fact that FT-AORP employs various relevant routing metrics to avoid the occurrence of potential link failures on one path.
Packet delivery ratio performance against (a) node density, (b) node speed, and (c) sending rate.
In addition, Fig. 6b shows the PDR performance against various node speeds, from 5 to 60 m/s. It can be observed that as node speed increases, PDR decreases owing to the high likelihood of link breaks as the nodes constantly change their positions. However, EE-LB-AOMDV and FT-AORP outperformed the other three baseline protocols in nearly every scenario. Even at a very high speed of 60 m/s, the two protocols were still able to deliver 70% of the data packets to the destination, whereas the recorded numbers of the remaining protocols were all 10% lower. Because FT-AORP considers the node mobility and its location with respect to other nodes when selecting the optimal paths, its results were marginally better than EE-LB-AOMDV in general.
Fig. 6c further demonstrates the fault tolerance of FT-AORP against different packet sending rates between 0.1 and 5 Mbps. In general, the PDR performance of the three protocols was less materially affected by this factor than by the network density and node speed. At 0.1 Mbps, the reduced packet delivery efficiency is possibly due to the low data rate compared to the predetermined node speed and density. To be more specific, a certain number of packets might be undelivered due to the fast changes in the network topology. In the scenario that required the largest throughput (i.e., 5 Mbps), FT-AORP successfully transmitted nearly 85% of the data packets, which was just 3% fewer compared to the other less throughput-demanding scenarios of 0.1, 0.5, and 1 Mbps. Meanwhile, EE-LB-AOMDV had a very comparable simulation result, and AODV did not provide such a satisfactory performance. Thus, FT-AORP is also an ideal routing protocol for bandwidth-demanding applications, such as voice and video calls.
C. End-To-End Delay
End-to-end delay is the elapsed time from when a data packet is generated by the source node to when it is successfully received by the destination node. This latency includes all potential delays such as queuing at the wireless interface and re-transmission attempts by the Medium Access Control. For this metric, the average delay of all the successfully transmitted packets in a simulation run was calculated as \begin{equation*} \textrm {End-to-end delay} = \frac {\sum ^{n_{d}}_{i = 1} \left ({\tau ^{d}_{i} - \tau ^{g}_{i} }\right)}{n_{d}},\tag{13}\end{equation*}
Fig. 7 shows the end-to-end delay performance under three different simulation parameters. In particular, Fig. 7a compares end-to-end latency with different levels of the network density measured in the number of nodes. In most cases, the latency increased as the network grew larger because there were possibly more nodes involved in a transmission path. However, the FT-AORP protocol exhibited smaller delays overall than the other four protocols for all network sizes. This may be because the intermediate nodes move away from one another and potentially cause link breaks, while the four protocols mainly transmit packets using the path with the smallest number of hop counts
End-to-end delay performance against (a) node density, (b) node speed, and (c) sending rate.
Fig. 7b depicts the delay performance with regard to various node speed values. It is evident that as the nodes sped up, the network topology kept changing, possibly causing the nodes to lose their current established links. At 5 and 15 m/s, all the protocols showed approximately the same delay in packet transmission of 0.013 and 0.008 s, respectively. As the speed increased to 30 m/s and higher, FF-AOMDV and EE-LB-AOMDV exhibited the best delay results, while the performance of FT-AORP was also very similar. This is because they could choose more stable paths compared to AODV and AOMDV.
Regarding the end-to-end delay results against various sending rates, as shown in Fig. 7c, as the data packets being injected into the network in a time instant increased, the transmission delay increased. This may be attributed to lower-layer channel conflicts, as the nodes compete for channel access. On the whole, the four multipath protocols outperformed AODV in all scenarios because they could transmit the packets using two paths and thus avoid conflicts happening on one path. In fact, EE-LB-AOMDV performed slightly better than FT-AORP because it considered round-trip time as a routing metric. Overall, the applicability of FT-AORP to time-critical systems where the packet’s transmission time should be stably minimal in a variety of contexts is proven.
D. Path Energy
With this metric, the average energy level of the immediate nodes in a path that is used to transmit a data packet was computed. It indicates that the FT-AORP protocol prefers to choose the path with high-energy intermediate nodes. Because there may be two discovered paths for data transmission between the source and the destination, the path that delivers the data packet to the destination first, was considered. The path energy level for a simulation run is computed as \begin{equation*} \textrm {Path energy} = \frac {1}{n_{d}} \sum _{i = 1}^{n_{d}} \left ({\frac {1}{\lVert p^{(i)} \rVert } \sum _{v_{j} \in p^{(i)}} E^{(v_{j})} }\right),\tag{14}\end{equation*}
Fig. 8 presents the average energy level of the transmitting paths with three different simulation parameters. First, the performance of the protocols was compared in the testbed including from 10 to 80 nodes, as shown in Fig. 8a. It is evident that both AODV and AOMDV shared very similar simulation results, as there was not much discrepancy in their operating principles. Regarding FF-AOMDV, EE-LB-AOMDV, and FT-AORP, because these protocols can learn and select paths of higher in the energy levels, they certainly exhibited better performance regardless of the node density.
Path energy performance against (a) node density, (b) node speed, and (c) sending rate.
Next, Fig. 8b shows the measured path energy against variations in node mobility. It is evident that the overall trend is an increase in the energy level as the node speed increases for all the routing protocols. For certain speed values, specifically 5, 30, and 60 m/s, FT-AORP exhibited slightly lower energy level results compared to the other protocols. However, for the remaining scenarios, FT-AORP was capable of selecting paths with higher energy nodes. Consequently, the network lifetime was significantly improved, as the energy-depleted nodes did not participate in the data transmission activities.
Finally, Fig. 8c depicts the path energy performance with multiple data-sending rates. It is obvious that higher the sending rates result in more power being consumed by the nodes to transmit the data packets. In detail, AODV and AOMDV had the two smallest path energy levels overall because they did not consider energy as a routing metric. Meanwhile, FF-AOMDV, EE-LB-AOMDV, and FT-AORP exhibited the highest remaining energy levels overall, especially at 5 Mbps, where FT-AORP outperformed all other routing protocols.
Conclusion
This study proposed a fault-tolerant ad hoc on-demand routing protocol for MANET systems, referred to as FT-AORP. Considering the mobility tendency of network nodes, the radio signal strength levels they obtain from their neighbors, and their energy consumption rate, the proposed routing protocol can make rational decisions on the prospective paths to be used to transmit the data packets. Simulation results using the OMNeT++ environment indicated that FT-AORP can improve the packet delivery ratio, reduce the end-to-end transmission delay, and select high-energy paths. Consequently, the proposed protocol is helpful for applications where data-critical packets are required to be successfully delivered to the destination with low latency, and a rapid installation of an ad hoc network is strongly favored.
In future work, other routing metrics will be developed to guarantee the quality of service for specific applications where a traffic prioritization scheme is demanded. In addition, the route discovery strategy can be improved to reduce the protocol control overhead. Finally, because radio signal characteristics could not be entirely modeled by simulations conducted, the proposed protocol will be implemented on real-world mobile devices to further experiment and prove the applicability potential of FT-AORP.