# Mobility-Aware Routing Algorithm for Mobile Ad Hoc Networks

Authors: Chalew Zeynu Sirmollo; Mekuanint Agegnehu Bitew
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

Mobile ad hoc network (MANET) is a group of wireless mobile nodes that create a temporary network without the help of any central administration or standard support services. Mobility of nodes determines the overall performance of MANET networks. High mobility of nodes causes frequent changes in the network topology, and this leads to link breakage and increases reinitiating of the route discovery process. MANETs commonly use broadcasting techniques for route discovery process. However, it can cause redundant rebroadcasts, packet collisions, and channel contention. The main objective of this paper is to design and develop the mobility-aware routing algorithm (MARA) to enhance the performance of the routing protocol in MANETs. The proposed scheme allows mobile nodes to rebroadcast or discard received broadcasted messages. The decision is based on the combination of node speed, distance between nodes, and residual energy of nodes. These parameters are considered both in route request and route reply process to reduce the chance of link breakage and broadcast storm problems. The proposed algorithm has been evaluated based on the performance metrics: packet delivery ratio, average end-to-end delay, throughput, and routing overhead. We have used network simulator NS-2 V-2.35. The simulation results revealed that MARA outperforms ad hoc on-demand distance vector (AODV), mobility and direction aware (MAD), and mobility and energy-aware (MAE) routing protocols.


---

## Body

## 1. Introduction

MANET is an autonomous system of mobile nodes with routing capabilities connected by wireless links [1]. Every mobile node can act as a router, and it can communicate directly with another node in its physical neighborhood. MANET is a collection of mobile nodes that can dynamically change locations to form a network to exchange information. The main features of MANETs are automatic self-configuring, self-maintenance, inexpensive deployment, and lack of the need for fixed network infrastructures or centralized administration [2]. Due to its flexible nature, MANETs are widely applicable in battlefield communications, disaster relief, emergency operation, and educational, commercial, rescue and search operations [3]. One of the basic challenges in MANET is the designing of dynamic routing protocols that can be mobility aware and efficient to determine the routes between the communicating nodes with better performance and less overhead [1]. Routing protocols in MANETs can be categorized into three groups based on how routing information is acquired and maintained by mobile nodes [1, 4, 5]. The first category belongs to proactive (table-driven) routing protocols. In these routing protocols, mobile nodes calculate routes to all reachable nodes a priori and maintain consistent and up-to-date routing information using a periodic route update process [1]. Examples of proactive routing protocols are destination-sequenced distance-vector routing (DSDV) and optimized link state routing protocol (OLSR). The second category of routing protocols is named as reactive (on-demand) routing protocols. In these protocols, when any node wants to communicate to the other node, it applies on-demand route discovery mechanism for creating connections. Examples of reactive routing protocols are dynamic source routing (DSR) and AODV. Hybrid routing protocols are the third category of MANET routing protocols. Hybrid routing protocols combine the best practices of both proactive and reactive routing protocols. The zone routing protocol (ZRP) is an example of hybrid routing protocols.Reactive routing protocols such as AODV [5] do not adapt well in high-mobility environments. Reactive protocols select the shortest path between the source and destination nodes. However, the shortest path may not be always reliable or active due to mobility of nodes. The frequent breakage of the established path degrades the performance of MANETs [6]. When an active route between the source and the destination node breaks, the routing protocol executes route maintenance procedures. However, this consumes network resources and eventually influences negatively on the performance of the network [6].Broadcasting is an information distribution mechanism for sending a packet from a source to all nodes within a network [3]. Several routing protocols broadcast route request to seek multihop route to the destination. For example, AODV [5] typically uses broadcasting in the route discovery process. In MANETs, broadcasting occurs frequently for finding a route to a specific host, paging a specific host, and other network operations [7]. Broadcasting through flooding causes contention when many adjacent nodes broadcast concurrently [3]. Additionally, node mobility creates continuously changing network topology, in which routing paths are broken and new routes are formed dynamically. Therefore, broadcasting is one of the challenging problems in MANETs. Several approaches have been proposed to solve the issue as we have discussed in Related Works. However, they did not combine multiple parameter metrics simultaneously with decision methods such as the speed, direction, and residual energy of mobile nodes to aware dynamic change of the network topology.In this paper, we proposed new mobility-aware routing scheme for MANETs, which can adapt dynamic changes of the network topology. The proposed algorithm considers node mobility and a broadcasting decision mechanism to reduce the chance of link breakage and broadcast storm problems. We used node speed, node direction, and residual energy of nodes.


## 2. Related Works

Broadcasting in MANETs can be classified as simple (blind) flooding, location-based, distance-based, neighbor-knowledge-based, counter-based, and probabilistic-based [8–12]. In [12]; the authors have proposed a dynamic probabilistic-based routing scheme. In this scheme, packets forwarded to the neighbor node with dynamically computed probability, which is forwarding probability. The probability function is calculated based on the density of the local neighbors and cumulative amount of neighbor mobile nodes. The proposed approach showed improvement on performance as compared to AODV and fixed probability AODV (FP-AODV) routing protocols. However, the throughput is very low when the region of the network is spare. This is because of poor connectivity ratio among the mobile nodes in the sparse region and the end-to-end delay is high. Hence, the failure of a route request packet is high. The authors in [13] aimed to establish more stable data routes over vehicular ad hoc networks. However, they did not consider residual energy during route path selection. The authors of [14] proposed a mobility and load aware routing scheme which has a stable route and load balancing among several routes in high-mobility and high traffic load situation. This scheme uses speed and traffic load of intermediate nodes to determine the reliable route during the route discovery process. The Markovian decision process tool was used to rebroadcast or discard when each node receives a request packet. Simulation results showed that this scheme reduced the effects of broadcast storm problem, increased throughput, and reduced routing overhead as compared to the AODV protocol. However, the authors did not consider residual energy and direction of nodes. In [15], the authors proposed personalized ad hoc on-demand distance vector algorithm that deals with link breakage during exchange of data in MANETs. In this algorithm, selection of routing path based on delay and bandwidth metrics helped to improve the quality of service. It did not consider residual energy and speed of mobile nodes. In [16], the authors designed and implemented a mobility adaptive ad hoc on demand distance vector routing protocol which extends the AODV routing protocol using a hello message. This protocol has a capability of predicting mobility of nodes. However, it increases overhead due to maintenance of an active neighbor list to provide an alternative link during mobility. In [17], the authors proposed an MBMA-OLSR routing scheme. The paper extends and enhances the conventional MP-OLSRv2 routing protocol. Control messages (hello and TC) gather all the network topology information to construct the network graph. Through the network graph, MBMA-OLSA can avoid nodes with higher speeds and lower residual energy and choose more stable links. MBMA-OLSR is significantly superior to MP-OLSRv2 in throughput, end-to-end latency, and packet delivery rates in the range of 5-30 m/s. In [18], the authors presented the new energy and mobility-aware multipoint relay (EMA-MPR) selection mechanism which is an extension of the conventional MP-OLSRv2 protocol. Energy and mobility aware parameters decide the willingness of the node to become a multipoint relay node in the OLSR routing protocol. The proposed scheme concentrated on the fact that considering nodes speed alongside the residual battery of the node results in stable paths to the destination. As the authors stated, the scheme provides its effectiveness for high-speed scenarios with heavy traffic. However, it did not consider the distance between the communicating nodes through movement. In [19], the authors proposed a multicriteria-based hybrid multipath routing protocol. This study computed the multicriteria node rank metric by combining several parameters that are associated with energy and quality of service (QoS) for reducing the control overhead. Based on the computed metric, the multipoint relay nodes are selected by considering the energy and QoS metric. This work focuses on control routing overhead. In [20], the author has studied the performance of the proposed multipath routing protocols for energy-efficient and QoS awareness depending on the node’s mobility in MANETs. This works focus on evaluating the performance of the multipath battery and queue aware routing (MBQA-OLSRv2), multipath battery, and mobility aware routing (MBMA-OLSRv2). The obtained results show that the MBMA-OLSRv2 scheme outperformed MBQA-OLSRv2 routing, the scheme in terms of several metrics like throughput, total packets dropped, energy cost per packet, consumed energy, and delay particularly in high-mobility scenarios. Mobility and direction aware (MDA) proposed in [21] is aimed at establishing stable routes and reducing the chance for link breakages based on node speed and direction with respect to the source and destination nodes. Compared to AODV, MDA improved delivery ratio, end-to-end delay, routing overhead, and energy consumption. However, it did not consider the number of the redundant rebroadcasting packets generated by nodes. The selected most reliable path may contain low-power mobile nodes, which leads to link breakage. In addition, MDA considered the speed of nodes’ movement only in the route request packet (RREQ) broadcasting process. It did not take into account the direction of the node in the RREQ process. The mobility and energy-aware routing algorithm (MEA) proposed in [20] used relative mobility and residual energy of nodes. However, the remaining energy and relative mobility were considered only in the route replay phase; it did not considered these parameters in the route discovery process. In addition, the scheme has a broadcast storm problem because nodes broadcast RREQ packet into its neighbor without any consideration.In general, many researchers tried to enhance the performance of MANET routing algorithms by considering different metrics. However, there are limitations in combining multiple parameters with decision-making techniques to exchange information through the network and to reduce mobility and broadcasting problems. To the best of our knowledge, there is no work, which considers node speed, distance calculation, and residual energy simultaneously to establish a stable and reliable route between the source and destination nodes in route request and route reply phases. In this paper, we have considered node speed, direction value, and the remaining energy of a mobile node as a factor and proposed the MARA scheme.


## 3. Proposed Routing Algorithm

Nodes in MANETs change position quite frequently, and this has a great impact on the performance of the routing algorithm. To reduce this problem, the node’s mobility should be considered when designing a routing protocol for MANETs. Our proposed algorithm is capable of adapting to frequently changing network topology because we considered the node’s mobility. The knowledge of the position is significant for successful routing of packets. We assumed that nodes are equipped with global position system (GPS) and connect to each other using an omnidirectional antenna. Each node sends a RREQ message to the neighbor nodes to get their position at the current time. When a node broadcasts RREQ message, neighbors will get the required parameters and store in its neighbor fields in the routing table. Based on this information, mobile nodes can compute their speed and distance between neighbor nodes. Hence, nodes are aware of neighboring node information.


### 3.1. Description of Route Discovery and Reply Phases

#### 3.1.1. Route Discovery Phase

The proposed algorithm is an on-demand routing protocol. When a source node wants to transmit data to a destination node and it has no routing entry for this destination, then the route discovery process of the proposed algorithm is initiated. The initiation of a route discovery process is done by broadcasting new RREQ packets to all neighbor nodes. This new RREQ packet is an extension of the AODV RREQ packet, Table1. Figure 1 shows the flow chart of route discovery and reply phases of the proposed algorithm, MARA. When a RREQ packet is received by a neighbor node, it checks whether the RREQ packet is a duplicate or not. If it is a duplicate, the node discards or drops the RREQ packet immediately. If it is not, it searches for the reverse route towards the source node. If a route exits, it updates the existing route otherwise create a reverse route. If the receiving neighbor node is not the destination node and there is no valid route, it checks whether its speed is below a predefined threshold speed. Then, the neighbor or intermediate node checks whether the two nodes’ direction value is one. In addition, check whether the neighbor node residual energy value is greater than the threshold value of energy. Finally, if the condition is satisfied, the node updates the route to the originator, increments the hop count by one, and broadcast the RREQ. If it is not, the node discards or drops the RREQ packet. Each node will follow this process until the RREQ packet reaches the destination or an intermediate node that has a valid route to the destination.Table 1
Modified RREQ message format [5].
….XpositionYpositionSpeed (m/s)Figure 1
Flowchart of MARA in the route discovery and reply phases.


#### 3.1.2. Route Reply Phase

In the above section, we have described how the RREQ packet reaches the destination or intermediate node that has a valid route to the destination. The destination node needs to verify the speed and direction of its neighbors through which the request was received. This process has two different conditions based on where this node is: the destination itself or an intermediate node that has an active route to the destination. If the node is an intermediate node which has an active route to the destination, the node updates its route and initiates RREP packet to the previous-hop from which it has received the RREQ packet only the previous hop, and if its intermediate node is moving with the speed below the average speed, all neighbor nodes and the direction value is one. If the node is the destination, it updates its route and initiates RREP packet to the previous-hop from which it has received the RREQ packet; if only the previous hop is moving with the speed below average speed, all neighbor nodes and the node direction value is one, and if not, discard or drop the RREQ packet. If the number of previous-hop direction values is greater than equal to one, generate RREPs and select the path which contains nodes with having minimum relative speed values in order to achieve better link stability. If not, it discards or drops the RREQ packet. Each intermediate node that received the RREP packet until the RREP packet reaches the original source node will follow this process.


### 3.2. Distance Calculation between Mobile Nodes

Location, speed, and direction of mobile nodes change dynamically in MANETs. We computed the Euclidean distance between two neighbor nodes to determine whether the nodes are moving towards each other or away from each other. Suppose that there are two mobile nodesn1 andn2 with transmission range of r, as shown in Figure 2. Nodes n1 and n2 are moving at the speed of Vn1 and Vn2, respectively.Figure 2
Position estimation for mobile nodes [22].The distance betweenn1 and n2, Dn1,n2tat a time t can be calculated as
(1)Dn1,n2t=Xn2t−Xn1t2+Yn2t−Yn1t2,where Xn1t,Yn1tandXn2t,Yn2t are the locations of n1 and n2 at a time t, respectively.At (t+∆t) time, the distance between n1 and n2, Dn1,n2t+∆t can be calculated as
(2)Dn1,n2t+∆t=Xn2t+∆t−Xn1t+∆t2+Yn2t+∆t−Yn1t+∆t2,whereXn1t+∆t,Yn1t+∆tandXn2t+∆t,Yn2t+∆t are the locations of n1 and n2 at a time of (t+∆t), respectively.As mobility discussed in [23], mobility is the average change in distance between all nodes over that period of time. It is a function of speed and movement pattern. Speed of a node at a time t can be calculated as follows:
(3)Vt,t+∆t=/X2−X1+Y2−Y1/t+∆t−t,whereVt,t+∆t is the speed field values that are discussed below in the structure of the route request and routing table. Hence, each node can compute its distance from its neighbors as well as its speed at any time t.After determining the distance betweenn1 and its neighbors at t and t+∆t, we can determine whether n1 is joining or separating from its neighbors. If Dn1,n2t>Dn1,n2t+∆t, then nodes n1 and n2 are closer to each other within the time interval between t and (t+∆t). Hence, the two nodes are joining each other for this time interval. On the other hand, if Dn1,n2t<Dn1,n2t+∆t, the nodes are moving away from each other and the nodes have a high probability to be disconnected.


### 3.3. Route Request Message Format

We modified the RREQ message format used in the AODV protocol because the route discovery process of MARA is based on speed, distance between nodes, and the remaining energy of nodes. The AODV protocol did not consider these parameters in its RREQ message format. The entries of the RREQ message format of the AODV protocol extended by adding three new fields to its structure. The newly added fields are(i)
Xposition: this field contain the X coordinate of the mobile node(ii)
Yposition: this field contain the Y coordinate of the mobile node(iii)
Speed: this field indicates the speed of the mobile nodeThe dots in Table1 indicate the RREQ message fields of the well-known AODV protocol [5]. When a node broadcasts a RREQ message, neighbor nodes get the required parameters from the broadcasted RREQ message and store these parameters in their neighbor fields. In this regard, every node gets updated location information from its neighbors at a certain interval of time.


### 3.4. Routing Table Format

A routing table is a set of rules, which contains information necessary to forward a packet about its origin in addition, along the best path towards its destination. It stores information in the form of a table. Based on equations (1) and (2), the routing table of the proposed algorithm contains two new fields, as shown in Table 2. These are the following:
(i)
Speed of the neighbor node(ii)
Direction values: it contains the value of node movement based on the difference of distance between communicating mobile nodes as we discussed in Section3.1Table 2
Modified routing table Format [5].
…..Speed (m/s)Direction valuesThe direction in the routing table is used to set whether neighbors are joining or separating. In order to set the direction value, we compare the distance between the mobile nodes using equations (1) and (2). If the nodes are joining each other and the distance between the two nodes is constant, the direction value is set to one. Otherwise, the direction value is set to zero. Each mobile node maintains its routing table based on this way.


### 3.5. Residual Energy of Mobile Nodes

To improve the lifetime of MANETs, we considered the residual energy of nodes at the time of transmission. Because the mobile nodes run using battery, its energy is restricted. A mobile node loses a certain amount of energy when it transmits/receives packets. The proposed algorithm used a generic radio energy model [24] to estimate initial energy (IE), residual energy (RE), and consumption energy (CE) at a time t. The following equation is used to compute the RE of nodes:
(4)REt=IE−ECt,whereECt is the energy consumed by a node after time t. To estimate the energy consumed for transmitting N number packets, we used the following equation:
(5)TEt=N∗PTt,whereTEt refers to the transmission energy of a node and PTt refers to the power spent through the transmission of N number of data packets and at a certain period of time the neighbor nodes exchange routing information. The estimated energy consumption in a receiving N numbers of packets can be calculated by
(6)REt=N∗PRt,whereREt refers to the receiving energy of a node and PRtrefers to the power spent through receiving N number of data packets and at certain period of time the neighbor nodes exchange routing information. Therefore, the total energy consumption of a node at the time t for transmission and reception is given by
(7)ECt=TEt+REt.Based on this, our proposed algorithm considered the residual energy in the broadcasting decision in order to reduce the chance of a broadcast storm problem. The following pseudocode shows the detailed explanation of the route request and route reply process of the proposed algorithm.Algorithm 1: Pseudocode of the proposed routing algorithm (MARA).
Notations:1. SA: Source or initiator address2.DA: Destination address3.IN: Intermediate node that has a valid route to the desired destination node4.EDi: Euclidian distance between the initiator node and a destination node in the initial time5.EDf: Euclidian distance between initiator node and destination node of in final time6.RT: Route table7.RRM: Route request message8.RREP: Route request reply9.Received pair: Source address and RREQ_ID10.REn: Residual energy of node11.SIn: Speed of source or initiator nodes.12.SNn []: Speed of all neighbor nodes in a recipient routing table13.SPn: Previous hop speed14.PHn: Number of previous hop15.SN: Source node16.DM: Direction of movement ifEDi>EDf set to 1 and EDi<EDf set to 0 in recipient routing table17.BEGIN18.SN Broadcast RRM into all neighbor nodes, then find match received pair to do this:19. Boolean found = False20.  For (a=1 to Rout_Table. Length)21.  If (Received_pair == RT [a]) then22.   found = True;23.   End if24.  if (found) then25.  Drop RRM26.  Else27. If (SA! = DA) then28.  If (REn > Threshold_Energy && SIn < Threshold_Speed && Its DM==1) then29.  Update RT30.  Update RRM31.  Broadcast RRM into its neighbor nodes32.      Else33.        Drop RRM34.        Loop Break35.       End else36.    End if37.  Else38. Switch (Node category)39.   Case: “IN” then40.     Count =041.      For (b=1 to neighbors. Length)42.       Count = Count + SNn [b]43.      End for44.  Average_Speed = count/neighbors. Length45.  If (SPn & SIn < Average_Speed && both DM==1) then46.      Fun()47.        Counter =048.For (i=1 to Rout Table. Length)49.    if (PHn value of DM =1) then50.      Counter ++51.      End if52.     End for53.    if (Counter>=1) then54.    Update Routing Table55.    It send back an RREP packet to the previous hop that has minimum speed.56.      Drop Received RRM57.       Loop Break58.       Else59.         Drop RREP packet60.       Loop Break61.       End Fun62.      End else63.    End If64.   End If65.    End Case66.  Case: “Final destination” then67.Count=068.  For (c=1 to neighbors. Length)69.      Count = count + SNn[c]70.       End for71.  Average_Speed = Count/neighbors. Length72.  If (SPn < Average_Speed && DM==1) then73.      Call to fun()74.     Update Routing Table75. Its send back a RREP packet to the previous hop76.      Drop Received RRM77.      Loop Break78.        Else79.      Drop Received RRM80.       Loop Break81.      End else82.     End If83.   End Case84. End If85. End for86.End BEGIN


### 3.6. Simulation Scenarios

To evaluate the proposed scheme, we used network simulator two (NS2) [25] under the random waypoint (RWP) model [26] and reference point group mobility model (RPGM) [27]. The deployment considers 10, 20, 30, 40, 50, 60, and 70 mobile nodes with a simulation area of 1000m×1000m. We have evaluated the performance of the proposed algorithm by varying node density and node mobility. Each node uses an IEEE 802.11 MAC layer protocol to send and receive messages. The connection between the source and destination node spread randomly over the network. The network bandwidth is 2 Mbps. We used a two-ray ground model for radio propagation [28]. We have considered two simulation scenarios: impact of node density and node mobility. Table 3 shows the details of the simulation parameters.Table 3
Simulation parameters of all scenarios.
ParametersValueRouting protocolMARA, AODV, MAD, and MAEPropagation modelTwo-ray groundSimulation area1000m×1000mMAC typeIEEE 802.11Antenna typeOmnidirectionalInterface typePhy/WirelessPhyPacket rate10 packets/secTraffic typeConstant bit rate (CBR)Min speed0Max speed10, 20, 30, 40, and 50 m/sNumber of nodes10, 20, 30, 40, 50, 60, and 70CBR flows15Mobility modelRWP and RPGMPacket size512 bytesTransmission range250 mQueue length50Pause time10 sSimulation time120 s


### 3.7. Performance Evaluation Metrics

In order to evaluate the performance analysis of the proposed algorithm, we considered the packet delivery ratio, average end-to-end delay, throughput, and routing overhead which are widely used performance metrics MANET [29, 30]. The description of these performance metrics is given below:
(a)
Packet delivery ratio (PDR) refers to the ratio between the number of packets sent by constant bit rate sources and the number of packets received by the CBR sink at the destination. It is the measure of reliability of a protocol(b)
Average end-to-end delay (AETED) refers to the average time data packets spent to reach to the desired destinations. It includes delays caused by buffering throughout the route discovery process, processing in intermediate nodes, queuing at the interface queue, and retransmission delays(c)
Throughput is defined as the total number of packets received by the destination in a given time period and typically measured in bits per second (bps)(d)
Normalized routing load (NRL) is defined as the number of routing packets transmitted per data packet delivered at the destination. When a packet sent over several hops, each transmission of the packet counts as one transmission


## 3.1. Description of Route Discovery and Reply Phases

### 3.1.1. Route Discovery Phase

The proposed algorithm is an on-demand routing protocol. When a source node wants to transmit data to a destination node and it has no routing entry for this destination, then the route discovery process of the proposed algorithm is initiated. The initiation of a route discovery process is done by broadcasting new RREQ packets to all neighbor nodes. This new RREQ packet is an extension of the AODV RREQ packet, Table1. Figure 1 shows the flow chart of route discovery and reply phases of the proposed algorithm, MARA. When a RREQ packet is received by a neighbor node, it checks whether the RREQ packet is a duplicate or not. If it is a duplicate, the node discards or drops the RREQ packet immediately. If it is not, it searches for the reverse route towards the source node. If a route exits, it updates the existing route otherwise create a reverse route. If the receiving neighbor node is not the destination node and there is no valid route, it checks whether its speed is below a predefined threshold speed. Then, the neighbor or intermediate node checks whether the two nodes’ direction value is one. In addition, check whether the neighbor node residual energy value is greater than the threshold value of energy. Finally, if the condition is satisfied, the node updates the route to the originator, increments the hop count by one, and broadcast the RREQ. If it is not, the node discards or drops the RREQ packet. Each node will follow this process until the RREQ packet reaches the destination or an intermediate node that has a valid route to the destination.Table 1
Modified RREQ message format [5].
….XpositionYpositionSpeed (m/s)Figure 1
Flowchart of MARA in the route discovery and reply phases.


### 3.1.2. Route Reply Phase

In the above section, we have described how the RREQ packet reaches the destination or intermediate node that has a valid route to the destination. The destination node needs to verify the speed and direction of its neighbors through which the request was received. This process has two different conditions based on where this node is: the destination itself or an intermediate node that has an active route to the destination. If the node is an intermediate node which has an active route to the destination, the node updates its route and initiates RREP packet to the previous-hop from which it has received the RREQ packet only the previous hop, and if its intermediate node is moving with the speed below the average speed, all neighbor nodes and the direction value is one. If the node is the destination, it updates its route and initiates RREP packet to the previous-hop from which it has received the RREQ packet; if only the previous hop is moving with the speed below average speed, all neighbor nodes and the node direction value is one, and if not, discard or drop the RREQ packet. If the number of previous-hop direction values is greater than equal to one, generate RREPs and select the path which contains nodes with having minimum relative speed values in order to achieve better link stability. If not, it discards or drops the RREQ packet. Each intermediate node that received the RREP packet until the RREP packet reaches the original source node will follow this process.


## 3.1.1. Route Discovery Phase

The proposed algorithm is an on-demand routing protocol. When a source node wants to transmit data to a destination node and it has no routing entry for this destination, then the route discovery process of the proposed algorithm is initiated. The initiation of a route discovery process is done by broadcasting new RREQ packets to all neighbor nodes. This new RREQ packet is an extension of the AODV RREQ packet, Table1. Figure 1 shows the flow chart of route discovery and reply phases of the proposed algorithm, MARA. When a RREQ packet is received by a neighbor node, it checks whether the RREQ packet is a duplicate or not. If it is a duplicate, the node discards or drops the RREQ packet immediately. If it is not, it searches for the reverse route towards the source node. If a route exits, it updates the existing route otherwise create a reverse route. If the receiving neighbor node is not the destination node and there is no valid route, it checks whether its speed is below a predefined threshold speed. Then, the neighbor or intermediate node checks whether the two nodes’ direction value is one. In addition, check whether the neighbor node residual energy value is greater than the threshold value of energy. Finally, if the condition is satisfied, the node updates the route to the originator, increments the hop count by one, and broadcast the RREQ. If it is not, the node discards or drops the RREQ packet. Each node will follow this process until the RREQ packet reaches the destination or an intermediate node that has a valid route to the destination.Table 1
Modified RREQ message format [5].
….XpositionYpositionSpeed (m/s)Figure 1
Flowchart of MARA in the route discovery and reply phases.


## 3.1.2. Route Reply Phase

In the above section, we have described how the RREQ packet reaches the destination or intermediate node that has a valid route to the destination. The destination node needs to verify the speed and direction of its neighbors through which the request was received. This process has two different conditions based on where this node is: the destination itself or an intermediate node that has an active route to the destination. If the node is an intermediate node which has an active route to the destination, the node updates its route and initiates RREP packet to the previous-hop from which it has received the RREQ packet only the previous hop, and if its intermediate node is moving with the speed below the average speed, all neighbor nodes and the direction value is one. If the node is the destination, it updates its route and initiates RREP packet to the previous-hop from which it has received the RREQ packet; if only the previous hop is moving with the speed below average speed, all neighbor nodes and the node direction value is one, and if not, discard or drop the RREQ packet. If the number of previous-hop direction values is greater than equal to one, generate RREPs and select the path which contains nodes with having minimum relative speed values in order to achieve better link stability. If not, it discards or drops the RREQ packet. Each intermediate node that received the RREP packet until the RREP packet reaches the original source node will follow this process.


## 3.2. Distance Calculation between Mobile Nodes

Location, speed, and direction of mobile nodes change dynamically in MANETs. We computed the Euclidean distance between two neighbor nodes to determine whether the nodes are moving towards each other or away from each other. Suppose that there are two mobile nodesn1 andn2 with transmission range of r, as shown in Figure 2. Nodes n1 and n2 are moving at the speed of Vn1 and Vn2, respectively.Figure 2
Position estimation for mobile nodes [22].The distance betweenn1 and n2, Dn1,n2tat a time t can be calculated as
(1)Dn1,n2t=Xn2t−Xn1t2+Yn2t−Yn1t2,where Xn1t,Yn1tandXn2t,Yn2t are the locations of n1 and n2 at a time t, respectively.At (t+∆t) time, the distance between n1 and n2, Dn1,n2t+∆t can be calculated as
(2)Dn1,n2t+∆t=Xn2t+∆t−Xn1t+∆t2+Yn2t+∆t−Yn1t+∆t2,whereXn1t+∆t,Yn1t+∆tandXn2t+∆t,Yn2t+∆t are the locations of n1 and n2 at a time of (t+∆t), respectively.As mobility discussed in [23], mobility is the average change in distance between all nodes over that period of time. It is a function of speed and movement pattern. Speed of a node at a time t can be calculated as follows:
(3)Vt,t+∆t=/X2−X1+Y2−Y1/t+∆t−t,whereVt,t+∆t is the speed field values that are discussed below in the structure of the route request and routing table. Hence, each node can compute its distance from its neighbors as well as its speed at any time t.After determining the distance betweenn1 and its neighbors at t and t+∆t, we can determine whether n1 is joining or separating from its neighbors. If Dn1,n2t>Dn1,n2t+∆t, then nodes n1 and n2 are closer to each other within the time interval between t and (t+∆t). Hence, the two nodes are joining each other for this time interval. On the other hand, if Dn1,n2t<Dn1,n2t+∆t, the nodes are moving away from each other and the nodes have a high probability to be disconnected.


## 3.3. Route Request Message Format

We modified the RREQ message format used in the AODV protocol because the route discovery process of MARA is based on speed, distance between nodes, and the remaining energy of nodes. The AODV protocol did not consider these parameters in its RREQ message format. The entries of the RREQ message format of the AODV protocol extended by adding three new fields to its structure. The newly added fields are(i)
Xposition: this field contain the X coordinate of the mobile node(ii)
Yposition: this field contain the Y coordinate of the mobile node(iii)
Speed: this field indicates the speed of the mobile nodeThe dots in Table1 indicate the RREQ message fields of the well-known AODV protocol [5]. When a node broadcasts a RREQ message, neighbor nodes get the required parameters from the broadcasted RREQ message and store these parameters in their neighbor fields. In this regard, every node gets updated location information from its neighbors at a certain interval of time.


## 3.4. Routing Table Format

A routing table is a set of rules, which contains information necessary to forward a packet about its origin in addition, along the best path towards its destination. It stores information in the form of a table. Based on equations (1) and (2), the routing table of the proposed algorithm contains two new fields, as shown in Table 2. These are the following:
(i)
Speed of the neighbor node(ii)
Direction values: it contains the value of node movement based on the difference of distance between communicating mobile nodes as we discussed in Section3.1Table 2
Modified routing table Format [5].
…..Speed (m/s)Direction valuesThe direction in the routing table is used to set whether neighbors are joining or separating. In order to set the direction value, we compare the distance between the mobile nodes using equations (1) and (2). If the nodes are joining each other and the distance between the two nodes is constant, the direction value is set to one. Otherwise, the direction value is set to zero. Each mobile node maintains its routing table based on this way.


## 3.5. Residual Energy of Mobile Nodes

To improve the lifetime of MANETs, we considered the residual energy of nodes at the time of transmission. Because the mobile nodes run using battery, its energy is restricted. A mobile node loses a certain amount of energy when it transmits/receives packets. The proposed algorithm used a generic radio energy model [24] to estimate initial energy (IE), residual energy (RE), and consumption energy (CE) at a time t. The following equation is used to compute the RE of nodes:
(4)REt=IE−ECt,whereECt is the energy consumed by a node after time t. To estimate the energy consumed for transmitting N number packets, we used the following equation:
(5)TEt=N∗PTt,whereTEt refers to the transmission energy of a node and PTt refers to the power spent through the transmission of N number of data packets and at a certain period of time the neighbor nodes exchange routing information. The estimated energy consumption in a receiving N numbers of packets can be calculated by
(6)REt=N∗PRt,whereREt refers to the receiving energy of a node and PRtrefers to the power spent through receiving N number of data packets and at certain period of time the neighbor nodes exchange routing information. Therefore, the total energy consumption of a node at the time t for transmission and reception is given by
(7)ECt=TEt+REt.Based on this, our proposed algorithm considered the residual energy in the broadcasting decision in order to reduce the chance of a broadcast storm problem. The following pseudocode shows the detailed explanation of the route request and route reply process of the proposed algorithm.Algorithm 1: Pseudocode of the proposed routing algorithm (MARA).
Notations:1. SA: Source or initiator address2.DA: Destination address3.IN: Intermediate node that has a valid route to the desired destination node4.EDi: Euclidian distance between the initiator node and a destination node in the initial time5.EDf: Euclidian distance between initiator node and destination node of in final time6.RT: Route table7.RRM: Route request message8.RREP: Route request reply9.Received pair: Source address and RREQ_ID10.REn: Residual energy of node11.SIn: Speed of source or initiator nodes.12.SNn []: Speed of all neighbor nodes in a recipient routing table13.SPn: Previous hop speed14.PHn: Number of previous hop15.SN: Source node16.DM: Direction of movement ifEDi>EDf set to 1 and EDi<EDf set to 0 in recipient routing table17.BEGIN18.SN Broadcast RRM into all neighbor nodes, then find match received pair to do this:19. Boolean found = False20.  For (a=1 to Rout_Table. Length)21.  If (Received_pair == RT [a]) then22.   found = True;23.   End if24.  if (found) then25.  Drop RRM26.  Else27. If (SA! = DA) then28.  If (REn > Threshold_Energy && SIn < Threshold_Speed && Its DM==1) then29.  Update RT30.  Update RRM31.  Broadcast RRM into its neighbor nodes32.      Else33.        Drop RRM34.        Loop Break35.       End else36.    End if37.  Else38. Switch (Node category)39.   Case: “IN” then40.     Count =041.      For (b=1 to neighbors. Length)42.       Count = Count + SNn [b]43.      End for44.  Average_Speed = count/neighbors. Length45.  If (SPn & SIn < Average_Speed && both DM==1) then46.      Fun()47.        Counter =048.For (i=1 to Rout Table. Length)49.    if (PHn value of DM =1) then50.      Counter ++51.      End if52.     End for53.    if (Counter>=1) then54.    Update Routing Table55.    It send back an RREP packet to the previous hop that has minimum speed.56.      Drop Received RRM57.       Loop Break58.       Else59.         Drop RREP packet60.       Loop Break61.       End Fun62.      End else63.    End If64.   End If65.    End Case66.  Case: “Final destination” then67.Count=068.  For (c=1 to neighbors. Length)69.      Count = count + SNn[c]70.       End for71.  Average_Speed = Count/neighbors. Length72.  If (SPn < Average_Speed && DM==1) then73.      Call to fun()74.     Update Routing Table75. Its send back a RREP packet to the previous hop76.      Drop Received RRM77.      Loop Break78.        Else79.      Drop Received RRM80.       Loop Break81.      End else82.     End If83.   End Case84. End If85. End for86.End BEGIN


## 3.6. Simulation Scenarios

To evaluate the proposed scheme, we used network simulator two (NS2) [25] under the random waypoint (RWP) model [26] and reference point group mobility model (RPGM) [27]. The deployment considers 10, 20, 30, 40, 50, 60, and 70 mobile nodes with a simulation area of 1000m×1000m. We have evaluated the performance of the proposed algorithm by varying node density and node mobility. Each node uses an IEEE 802.11 MAC layer protocol to send and receive messages. The connection between the source and destination node spread randomly over the network. The network bandwidth is 2 Mbps. We used a two-ray ground model for radio propagation [28]. We have considered two simulation scenarios: impact of node density and node mobility. Table 3 shows the details of the simulation parameters.Table 3
Simulation parameters of all scenarios.
ParametersValueRouting protocolMARA, AODV, MAD, and MAEPropagation modelTwo-ray groundSimulation area1000m×1000mMAC typeIEEE 802.11Antenna typeOmnidirectionalInterface typePhy/WirelessPhyPacket rate10 packets/secTraffic typeConstant bit rate (CBR)Min speed0Max speed10, 20, 30, 40, and 50 m/sNumber of nodes10, 20, 30, 40, 50, 60, and 70CBR flows15Mobility modelRWP and RPGMPacket size512 bytesTransmission range250 mQueue length50Pause time10 sSimulation time120 s


## 3.7. Performance Evaluation Metrics

In order to evaluate the performance analysis of the proposed algorithm, we considered the packet delivery ratio, average end-to-end delay, throughput, and routing overhead which are widely used performance metrics MANET [29, 30]. The description of these performance metrics is given below:
(a)
Packet delivery ratio (PDR) refers to the ratio between the number of packets sent by constant bit rate sources and the number of packets received by the CBR sink at the destination. It is the measure of reliability of a protocol(b)
Average end-to-end delay (AETED) refers to the average time data packets spent to reach to the desired destinations. It includes delays caused by buffering throughout the route discovery process, processing in intermediate nodes, queuing at the interface queue, and retransmission delays(c)
Throughput is defined as the total number of packets received by the destination in a given time period and typically measured in bits per second (bps)(d)
Normalized routing load (NRL) is defined as the number of routing packets transmitted per data packet delivered at the destination. When a packet sent over several hops, each transmission of the packet counts as one transmission


## 4. Simulation Results and Discussion

In this section, we present the simulation results and discussions of the proposed algorithm. The performance of proposed routing algorithm, MARA, is compared with AODV [5], MAD [21], and MAE [31]. We used the quantitative performance metrics used in [22, 23].


### 4.1. Impact of Node Density

In order to check the impact of node density, the number of nodes deployed has been changed over a1000m×1000m area by keeping all other parameters unchanged. Based on the mobility models RWP and RPGM, the packet delivery ratio of all protocols is decreasing as the number of nodes increases (Figures 3 and 4). Increasing the density causes link breakage and congestion which leads to packet drop. In order to check the impact of node density, the number of nodes deployed has been changed over a 1000m×1000m area by keeping all other parameters unchanged. The packet delivery ratio of all protocols is decreasing as the number of nodes increases. Increasing the density causes link breakage and congestion which leads to packet drop. The packet delivery ratio (PDR) of the proposed algorithm, MARA, is higher than AODV, MAD, and MAE. MARA reduces the chance of several link breakages, which reduces the amount of packet loss. It also decreases the number of rebroadcasting packets, which decreases the possibility of collision and contention. Since we considered speed, distance between communicating nodes, and low energy in RREQ and RREP phases, the established path between the nodes has less chance of breakage. Increasing the density of nodes increases end-to-end delay (Figures 5 and 6). Increasing the network density increases the possibility of packet collision and contention. This leads to frequent rebroadcasting of packets and increases end-to-end delay. MARA achieved a significant improvement as compared to AODV, MAD, and MAE. MARA reduces the possibility of reinitiating RREQ packets.Figure 3
PDR vs. number of nodes using RWP.Figure 4
PDR vs. number of nodes using RPGM.Figure 5
AETED delay vs. no. of nodes using RWP.Figure 6
AETED delay vs. no. of nodes using RPGM.Increasing the number of nodes increases the routing load gradually in Figures7 and 8. The routing load of MARA is less than AODV, MAD, and MAE in both mobility models. Because of the reduction of redundant rebroadcast of the RREQ packet, there is less chance of packet collisions and less link breakage. Reducing the link breakage reduces the reinitiation of route discovery and maintenance process. The obtained result in Figures 9 and 10 describes the throughput of the proposed algorithm as a function of the maximum number of nodes. The results demonstrate that MARA scheme outperforms AODV, MAD, and MAE in all cases. MARA considers node mobility to select the best route, which has less probability of link break. However, the AODV protocol selects the shortest route and does not consider mobility. Selecting a route that may cause the frequent link breakage affects the overall throughput of the network.Figure 7
NRL vs. no. of nodes using RWP.Figure 8
NRL vs. no. of nodes using RPGM.Figure 9
Throughput vs. no. of nodes using RWP.Figure 10
Throughput vs. no. of nodes using RPGM.


### 4.2. Impact of Node Mobility

In order to evaluate and compare, the performance of MARA, AODV, MAD, and MAE simulations have been conducted by changing the speed of mobile nodes. 50 mobile nodes have been deployed on a1000m×1000m area. We have analyzed the impact of node mobility on the PDR as shown in Figures 11 and 12. Increasing the node speed decreases the PDR of all protocol. This is because a valid route begins to break as the speed of node increases that causes to initiate RREQ retransmitting, which leads to consume more bandwidth and increase rebroadcast. However, MARA outperforms AODV, MAD, and MAE in all cases. The packet delivery ratio in MARA has been improved due to rebroadcasting and chance of link break. As we have considered high speed, direction, and low energy of the mobile nodes, the established path has less chance of breakage. Therefore, fewer rebroadcast of the routing message causes smaller bandwidth consumption and reduces collisions and contentions, which affected the significance of the network.Figure 11
PDR vs. speed using RWP.Figure 12
PDR vs. speed using RPGM.Figures13 and 14 results indicate the impact of node mobility on the performance of MARA, AODV, MAD, and MAE. MARA has achieved less end-to-end delay as compared to the other schemes in all cases. This is because the route discovery process of MARA is less than AODV, MAD, and MAE due to the link breakage possibility being less. Figures 15 and 16 show the impact of node mobility on the performance of MARA, AODV, MAD, and MAE protocol in terms of network routing load. The overhead has increased when we increased the speed of mobile nodes. The reason is the paths between the sources and destination node repeatedly breaks and reestablishes due to mobility. Moreover, the RREQ packets may not reach the desired destinations. Hence, this leads to reinitiate a route discovery process that eventually increases the network routing load or overhead. MARA scheme has achieved better performance in terms of routing load in all cases, because it reduces the unnecessary rebroadcast of the RREQ packet and selects the reliable route at the destination with reducing the redundant rebroadcast of the RREQ packet.Figure 13
AETED vs. speed using RWP.Figure 14
AETED vs. speed using RPGM.Figure 15
NRL vs. speed using RWP.Figure 16
NRL vs. speed using RPGM.The obtained result in Figures17 and 18 shows that increasing the speed of nodes decreases the throughput. Due to mobility, the valid route between the source and destination node breaks causes to reinitiate RREQ packet. This leads to more rebroadcast and greater bandwidth consumption. Therefore, the throughput decreased when the node speed is increased. The proposed algorithm reduces link breakage and number of rebroadcast RREQ packets that makes it to minimize bandwidth consumption and reduces the chance of collisions and contentions. Therefore, it has a higher throughput.Figure 17
Throughput vs. speed using RWP.Figure 18
Throughput vs. speed using RPGM.


## 4.1. Impact of Node Density

In order to check the impact of node density, the number of nodes deployed has been changed over a1000m×1000m area by keeping all other parameters unchanged. Based on the mobility models RWP and RPGM, the packet delivery ratio of all protocols is decreasing as the number of nodes increases (Figures 3 and 4). Increasing the density causes link breakage and congestion which leads to packet drop. In order to check the impact of node density, the number of nodes deployed has been changed over a 1000m×1000m area by keeping all other parameters unchanged. The packet delivery ratio of all protocols is decreasing as the number of nodes increases. Increasing the density causes link breakage and congestion which leads to packet drop. The packet delivery ratio (PDR) of the proposed algorithm, MARA, is higher than AODV, MAD, and MAE. MARA reduces the chance of several link breakages, which reduces the amount of packet loss. It also decreases the number of rebroadcasting packets, which decreases the possibility of collision and contention. Since we considered speed, distance between communicating nodes, and low energy in RREQ and RREP phases, the established path between the nodes has less chance of breakage. Increasing the density of nodes increases end-to-end delay (Figures 5 and 6). Increasing the network density increases the possibility of packet collision and contention. This leads to frequent rebroadcasting of packets and increases end-to-end delay. MARA achieved a significant improvement as compared to AODV, MAD, and MAE. MARA reduces the possibility of reinitiating RREQ packets.Figure 3
PDR vs. number of nodes using RWP.Figure 4
PDR vs. number of nodes using RPGM.Figure 5
AETED delay vs. no. of nodes using RWP.Figure 6
AETED delay vs. no. of nodes using RPGM.Increasing the number of nodes increases the routing load gradually in Figures7 and 8. The routing load of MARA is less than AODV, MAD, and MAE in both mobility models. Because of the reduction of redundant rebroadcast of the RREQ packet, there is less chance of packet collisions and less link breakage. Reducing the link breakage reduces the reinitiation of route discovery and maintenance process. The obtained result in Figures 9 and 10 describes the throughput of the proposed algorithm as a function of the maximum number of nodes. The results demonstrate that MARA scheme outperforms AODV, MAD, and MAE in all cases. MARA considers node mobility to select the best route, which has less probability of link break. However, the AODV protocol selects the shortest route and does not consider mobility. Selecting a route that may cause the frequent link breakage affects the overall throughput of the network.Figure 7
NRL vs. no. of nodes using RWP.Figure 8
NRL vs. no. of nodes using RPGM.Figure 9
Throughput vs. no. of nodes using RWP.Figure 10
Throughput vs. no. of nodes using RPGM.


## 4.2. Impact of Node Mobility

In order to evaluate and compare, the performance of MARA, AODV, MAD, and MAE simulations have been conducted by changing the speed of mobile nodes. 50 mobile nodes have been deployed on a1000m×1000m area. We have analyzed the impact of node mobility on the PDR as shown in Figures 11 and 12. Increasing the node speed decreases the PDR of all protocol. This is because a valid route begins to break as the speed of node increases that causes to initiate RREQ retransmitting, which leads to consume more bandwidth and increase rebroadcast. However, MARA outperforms AODV, MAD, and MAE in all cases. The packet delivery ratio in MARA has been improved due to rebroadcasting and chance of link break. As we have considered high speed, direction, and low energy of the mobile nodes, the established path has less chance of breakage. Therefore, fewer rebroadcast of the routing message causes smaller bandwidth consumption and reduces collisions and contentions, which affected the significance of the network.Figure 11
PDR vs. speed using RWP.Figure 12
PDR vs. speed using RPGM.Figures13 and 14 results indicate the impact of node mobility on the performance of MARA, AODV, MAD, and MAE. MARA has achieved less end-to-end delay as compared to the other schemes in all cases. This is because the route discovery process of MARA is less than AODV, MAD, and MAE due to the link breakage possibility being less. Figures 15 and 16 show the impact of node mobility on the performance of MARA, AODV, MAD, and MAE protocol in terms of network routing load. The overhead has increased when we increased the speed of mobile nodes. The reason is the paths between the sources and destination node repeatedly breaks and reestablishes due to mobility. Moreover, the RREQ packets may not reach the desired destinations. Hence, this leads to reinitiate a route discovery process that eventually increases the network routing load or overhead. MARA scheme has achieved better performance in terms of routing load in all cases, because it reduces the unnecessary rebroadcast of the RREQ packet and selects the reliable route at the destination with reducing the redundant rebroadcast of the RREQ packet.Figure 13
AETED vs. speed using RWP.Figure 14
AETED vs. speed using RPGM.Figure 15
NRL vs. speed using RWP.Figure 16
NRL vs. speed using RPGM.The obtained result in Figures17 and 18 shows that increasing the speed of nodes decreases the throughput. Due to mobility, the valid route between the source and destination node breaks causes to reinitiate RREQ packet. This leads to more rebroadcast and greater bandwidth consumption. Therefore, the throughput decreased when the node speed is increased. The proposed algorithm reduces link breakage and number of rebroadcast RREQ packets that makes it to minimize bandwidth consumption and reduces the chance of collisions and contentions. Therefore, it has a higher throughput.Figure 17
Throughput vs. speed using RWP.Figure 18
Throughput vs. speed using RPGM.


## 5. Conclusions and Future Work

MANET is a collection of mobile nodes that can dynamically change locations to form a network to exchange information. Mobility causes link breakage and increases the reinitiating of the route discovery process. In this study, we designed a MANET routing algorithm that overcomes the limitation of existing routing protocols. We combined multiple parameter metrics such as speed, direction, and residual energy of mobile nodes for decision-making in route discovery and route reply processes. Unlike the previous works, the proposed routing algorithm is based on node speed, direction, and residual energy to select more stable routes, among the intermediate nodes located in the path of the source and destination nodes. It has shown through extensive simulations that the proposed schemes in several operating conditions and scenarios. The proposed algorithm was tested and evaluated through simulation by varying node density and node speeds in different mobility models. MARA outperforms AODV, MAD, and MAE in terms of the widely used performance metrics: packet delivery ratio, average end-to-end delay, throughput, and normalized routing load.In our future works, we will consider other decision-making techniques like wireless link quality and routing load. In addition, the network topology in MANETs is very dynamic due to the mobility of nodes. Hence, the wireless link is vulnerable to attacks. Therefore, it needs a secure solution to the dynamic behavior of the network.



---

*Source: 6672297-2021-05-13.xml*