An Efficient Position based Power Aware Routing Algorithm in Mobile Ad-hoc Networks

Published Online July 2016 in MECS

A Mobile Ad Hoc Network (MANET) is the only means of communication where there is no other network (battle field or ocean operations) or the established network is completely collapsed due to any natural disaster and rescue teams have no other way of communication. Where communicating entities are highly mobile in nature communication using position based routing protocol is the most suitable methodology [1]. Efficient routing among a set of mobile nodes is one of the most important purposes in Mobile Ad-Hoc networks (MANETs). But all the routing protocols do not consider the other MANET factors like speed and battery remaining power. Thereby, we recommend an algorithm that results a more balanced use of the battery capacity of the nodes in the network. We proposed an efficient routing algorithm over existing position based protocols to obtain the following objectives:

• i.    To reduce packet loss this increases with the throughput of nodes,

• ii.    To extend the service life of MANET.

• II.    Background

• A.    Routing

Routing is the procedure of selecting paths in a network along which to send network traffic or packet. Routing is performed for several types of networks, including the telephone network, electronic data networks (such as the Internet) , and transportation networks. Here we are concerned mainly with routing in electronic data networks using packet switching technology. In packet switching networks, routing directs packet forwarding, the transfer of logically addressed packets from their source toward their final destination through intermediate nodes; naturally hardware devices called routers, bridges, gateways, firewalls, or switches are used in routing [2].

Fig.1. MANET in Military Environment

General-purpose computers with multiple network cards can also advance packets and perform routing, though they are not dedicated hardware and may experience limited performance. The routing process typically directs forwarding on the basis of routing w hich maintains an algorithm or technique of the routes to reach the network destinations [2].

• B.    Mobile Ad hoc Network (MANET)

A mobile ad hoc network (MANET), also called a mobile mesh network, is a self-configuring network of mobile devices connected by wireless links. It consists of wireless nodes making a form of a temporary network without the aid of any centralized administration or fixed based-station control. Each mobile node in the network can generate, transmit, receive or route data packets simultaneously. The routing decisions are taken from the neighboring nodes by calculating the nodes distance using GPS (global positioning system) or LBS (Location based Service) and broadcast this location by sending broadcast packets [2].

A preliminary classification of the routing protocols can be done via the type of cast property, whether they use the Unicast, Multicast, Broadcast and Geo-cast forwarding [4].

• C.    Routing Protocol types of MANET

Mobile nodes in an Ad Hoc network join and leave the network totally in an asynchronous manner anytime anywhere. All the existing routing protocols of Ad Hoc networks can be divided into two main categories:

• > Topology-based

> Position-based.

Topology-based routing protocols use information about links that exists in the network to perform packet forwarding [6]. Position-based protocols are performed by a scheme based on the updated information and situation of the node.

Fig.2. Classification of Routing Protocols in MANET.

Since the beginning of Defense Advanced Research Projects Agency (DARPA) packet radio networks in the early 1970s [4], numerous protocols have been developed for ad hoc mobile networks. Such protocols must deal with the typical limitations of these networks, which include high power consumption, low bandwidth, and high error rates.

In recent developments, position-based routing protocols exhibit better scalability, performance and robustness against frequent topological changes [7]. The primary goal of every routing scheme is to increase the delivery rate as well as reduce the packet loss.

• III.    Related Work

• A.    Position based routing protocol

Position based routing protocol uses the geographical position of nodes to make routing decisions, which results in improved efficiency and performance [9].

In the same fashion each intermediate node selects a next hop node until the packet reaches the destination. They periodically broadcast small packets to announce their position and enable other nodes maintain a one-hop neighbor table.

The distance between two neighbor nodes can be estimated on the basis of incoming signal strengths. The destination node is known and addressed by means of its location. Relative coordinates of neighbor nodes can be obtained by exchanging such information between neighbors [3].

• B.    MFR and DSR Routing Protocol

MFR [3] or Most Forward within Radius is a common position based routing protocols in which source uses the nearest node within its radius to send the message to the desired destination. In Position based routing, the destination node is determined by means of its location or distance get optimum routes for a particular radio range (see circle in Figure 2 where node 1 and 4 node’s range is shown with circle).

The inter-node distance is premeditated by its Euclidean length is given below from the two graphs axis or position [4].

A_e =7 ^(x 2 — ^X i )² + Ob ^- У 1 У (1)

But using only the distance metric to find the route where the packet to be sent is not suitable for all conditions [4].

Fig.3. Routing Path from MFR Method.

In figure 1, if the source node 1 wants to reach for the destination node 8, using the traditional MFR method the intermediate node 4 will be selected here.

Dynamic Source Routing (DSR) is one of the more generally accepted reactive routing protocols also known as On-Demand Routing Protocol. In DSR, each neighbor broadcasts this RREQ, adding its own address in the header of the packet. When the RREQ is received by the destination or by a node with a route to the destination, a route reply (RREP) is generated and sent back to the sender along with the addresses accumulated in the RREQ header [6].

• C.    Power Concern Routing

Energy is a source and non-renewable in wireless ad hoc network, energy- efficient protocol design is a key concern. The design and performance analysis of such protocols require proper modeling for the measurement of energy consumption.

The cost associated with each packet at a node is represented as the total of incremental cost “m” proportional to the packet size and a fixed cost “b” associated with channel acquisition.

Thus, the cost of a broadcast packet will be of the form [12]:

Cost= m× size +b              (2)

Since mobile nodes are usually battery-operated, one of the major reasons of node failure is battery drain out.

For example, in Figure 2, let’s assume that the intermediate node 4 is running with low battery power. If the low battery powered node 4 is chosen in communicating between node 1 and node 8 as intermediate node the battery of node 4 will eventually go down quickly which in turn will impact the network lifetime and QoS.

Each node in the network functions as a mobile router of data packets for other nodes and should maintain the network routes for long standing which is not possible due to limited battery source. Also, due to node mobility, link failures in such networks are very frequent and render certain standard protocols inefficient resulting in wastage of power and loss in throughput. The power consumption is an important issue with the goal to maintain the network lives for long by consuming less power [12].

Lifetime Prediction Routing (LPR) is an on demand source routing protocol that uses battery lifetime prediction. This protocol favors the path whose lifetime is maximum, i.e.

Мах „ Т„(t) = Мах _{t е} „ (T (t)) &№ Ту)  (3)

Where, T ^ Ct): lifetime of path n,

T_t (t): predicted lifetime of node i in path n [5].

• D.    Problems of MFR and Existing Protocols

In MFR, nodes focus on distance as deciding factor to forward packet to a neighbor node and it does not consider the node conditions which are not suitable for all circumstances. The main disadvantage of this protocol is it may select the least-power cost routes [8].

If there are situation such as

• a)    The closest neighbor to target node has very low battery power; it may go down before forwarding the packet which results packet loss.

• b)    The closest neighbor to target node; may have high or low speed with respect to source or target node speed. When the directions are different, the nodes may speared out and go out of range from the source or target node .

Such critical situations can occur anytime, and then the network link may be down or will face packet loss which decreases network throughput as well as lifetime [9].

Fig.4. Problems in MFR Method (a node dead situation).

To tackle such situation, when the remaining lifetime decreases and goes beyond a threshold level, the node in a path sends a route error back to the destination as if the route was rendered invalid. The destination sends this route error message to the source. Then the source initiates route discovery again. Node i generate a route error at time t when the following condition is met:

T_t ( t0)- T(t)<5            (4)

Where,

δ: change threshold for lifetime prediction t0: route discovery time, t: current time

Ti: predicted lifetime of node i [5]. But detecting the vulnerable node and then initiating a new route discovery is time consuming.

The hybrid combination of Ant Colony Optimization (ACO) and Multi Agent System (MAS) [13] also cannot manage the above situation for ensuring a balanced MANET.

Also Temporarily Ordered Routing Algorithm (TORA) and Associativity Based Routing (ABR) have some challenges to avoid this node dead situation in their comparative study [14].

Therefore, we proposed an efficient position based power-aware routing algorithm in mobile ad-hoc networks which considers the power and velocity issues in advance. Thus the proposed scheme addresses the load balancing issues and eventually increases the network lifetime and network performance.

• IV.    Proposed Scheme

In our approach, a modified RREQ is sent out and the entry in the route cache corresponding to the node that has moved out of range is purged. We have introduced four new variables to measure the node metric and cost, so the additional information are included in the modified packet format accordingly.

Fig.5. Modified RREQ Message Structure.

Figure-4 shows the modified RREQ packet format through which every node communicates and exchanges their information where they have the necessary protocol information [5].

Our proposed algorithm is described below:

• a)    Select nodes, J= {N i } where N i is within the range of S toward the direction of target what we get from RREQ message of above like Fig-2.

• b)    For every    N_i,    Calculate,    Distance,

= 7(^2 - -^)2 + (У2 —У1 )2  // Dt = distance between two nodes: 1(Source) and 2(intermediate).

• c)    Calculate, Relative speed,   R _t = |S_s — SJ;  //

S_s and S[ are the speeds of Source node S and intermediate node N_i

• d)    Compute, Cost Z i = (D i *W d ) –( P i *W p ) + (R i *W r ); //Where P_i, D_i and    are remaining power,

distance and relative speeds respectively.

//here, , and are the weight of remaining power, distance and relative speeds.

• e)    Select, MIN {Z _t } from every N i ;

• f)    Transmit data through MIN {  };

Fig.6. Path Selection through Simulation of Proposed Scheme.

Where we can control the preference by changing the weights , and any time.

Relative speed towards direction will carry a negative value and opposite will carry a positive value. In this proposed model, the preference order for selecting weights is followed in accepted ways [10]:

> Distance

• >    Battery Remaining Power

• >    Relative Speed.

Table 1. Sample Calculation of Total Cost from Figure-3 According to the Proposed Algorithm.

Selected Nodes position,(X, Y) N i	Weight Calculation From Proposed Algorthm
	Relative Distance in meter, D i	Battery Power in %, P i	Relative Speed in meter/ second, S i	Cost, Z i
(120, 130)N 3	86.02	70	5.5	21.52
(140, 80)N 4	72.80	30	6.5	49.30
(90, 20)N 5	44.72	15	7.2	36.92
(160, 10 )N 6	102.95	55	4.8	52.75

A sample calculation is shown in Table 1 for the topology shown in Figure 3. Here, it is seen that the minimum cost will be incurred if node 3 is chosen. So, according to the proposed method, the routing path will be: 1--->3--->8.

Here we can see that the node 3 has higher battery power than the other two comparable nodes, adjustable speed with respect to the source and destination node, also its range or distance is not out of coverage. As a result, the proposed algorithm will select node 3 rather than the node 4 which would be chosen by existing MFR method.

Though node 2 may have the highest battery power than node 3 but, this method avoids node 2 as an intermediate node. Other power-aware routing algorithm will choose node 2 in that case. The reason of not choosing node is in fact, it may have relative speed which eventually sends the node out of the range and this is not most forwarded to the destination path.

In summary, the proposed scheme uses priority based combination of metrics of battery power, velocity and distance in selecting the best node through which packet will be delivered. To prolong the lifetime of MANETs, we have to maximize the battery back-up of a mobile node at the same time selecting the mobile nodes which will remain within the coverage [12]. We also proposed to balanced use of nodes battery power in an efficient way over MFR and DSR routing.

• V.    Experimental Result Analysis

• A.    Simulations

The proposed method has been implemented using Network Simulator (NS-2.35). We designed Existing and

Table 2. Simulation Parameters

Parameters Greedy MFR Proposed Algorithm MAC protocol 802.11 802.11 Number of nodes 9 9 Mobility model Random way point Random way point Transmission range 500m 500m Terrain range 1000m *1000m 1000m *1000m PHY layer Phy Wireless Phy Wireless Queue type DropTail/PreQ DropTail/PreQ Simulation 300s 300s proposed strategy, with network topology generator software named NAM 1.1.

PDR=

∑ Recieved packets ∑ Send packets

×100

There were nine (9) mobile nodes, sender and destination nodes, and others were intermediate nodes. We executed this simulation for the 5 simulations in the same environment by varying their weights (±2, ±3) ppp , W_d and W_r and their outputs received and analyzed with NS-2 Wireless Trace Analyzer.

Node Utilization

"о

■ Greedy MFR

Intermediate Nodes

Proposed

Algorithm

Fig.7. Node Utilization Graph after 300 Second Simulation on Certain Situation.

In the Figure 6, it is depicting that In Greedy MFR had used node 4 maximum times (approximately 80%) until it goes dead. But in contrast, in spite of using node 4 in our algorithm it used node 3 and did used node 4 around 20% because it had a lower battery power.

• B.    Packets Delivery Rate (PDR)

The primary goal of every routing scheme is to increase the delivery rate as well as reduce the packet loss [11].

Fig.8. Packet Delivery Comparison Graph in 60 Second.

PDR is calculated in percent and it is expressed by the following formula [15]:

The following table .3 shows the throughput or PDR.

Table 3. Minimum, Maximum and Average Throughput of Existing MFR and Proposed Scheme.

Throughput of Schemes Throughput Comparison between Existing MFR and Proposed Algorithm. Lowestb Highestb Average Existing MFR 0.14 536 78.01 % Proposed Scheme 0.01 752 92.36 % a. In Bit per second. (kb/s)

From the above table we can see that the proposed method yield better throughput than that of the existing MFR scheme.

• C.    Packet Loss Rate

The proposed method successfully reduced packet loss than that of existing MFR scheme which can be seen from the summary shown in the table below. The packet loss rate was compared with existing MFR.

Fig.9. Packet Loss Comparison after 300 Second Simulation on Certain Situation.

From the experimental result shown in figure 6 we can see that the overall packet received has been increased in the proposed scheme.

Table 4. Packets Loss Comparison from the Sample Network.

Simulations Packets Loss Calculation Packets loss in actual in totala Average of 5 samplea In percentage Existing MFR 291 58.2 21.99 % Proposed Scheme 207 41.4 7.64 % b. In Bit per second. (kb/s)

• D.    Remaining Energy of Nodes (REN)

In our simulated network there are 9 nodes that their coordinates is determined randomly. Our testing for the remaining energy of network nodes comprises of selecting 1-4-8 nodes from Greedy MFR method and 1-38 nodes from our proposed method. The variance of remaining energy of nodes had been minimized, especially with our proposed protocols, which finally leads to the stability of the network; see Figure 6.

Fig.10. Remaining Battery Power Comparison after 300 Second Simulation on Certain Situation.

• E.    Delay Average of End-To-End Network

The average amount of time that one packet takes from source to destination, is specified as the delay packet. End-to-End delay of packets is characterized by these parameters: propagation delay, queuing delay, transmission delay and processing delay [15].

∑ Arraive Time— ∑ Sent Time

Average End To End Delay =

∑ Send packets

Table 5. Packet Delay for Greedy MFR and Proposed Scheme

Scheme	Minimum	Maximum	Average
Greedy	0.000936802	0.93698968	0.083337618
MFR	(sec)	(sec)	(sec)
Proposed	0.000840719	0.18695047	0.012050933
Scheme	(sec)	(sec)	(sec)

In these types of dynamic environments, the proposed algorithm considers all the parameters (3 parameters of all nodes) to find out a better route for the MANET to make the system to survive as much as possible.

It is a hybrid algorithm of position based and power-aware schemes with parameter tuning options by the operators or network administrator. Here we have avoided the node failure situation due to power exhaustion and skipped the risky nodes as router to make the network a healthy one.

• VI.    Conclusion

In this paper, we proposed an efficient position based MFR routing scheme with its qualitative evaluation. The method is scalable and resilient to topology changes. We presented a new weight based metric which encompasses the distance deciding metric, remaining battery power and relative speed in selecting next node to deliver packets compared to distance deciding metric used in traditional Existing MFR routing algorithms. The main goal of the proposed scheme is to find- out most suitable intermediate nodes with minimum packet loss and maximum network life time. The proposed algorithm considers the power and velocity issues in advance in selecting intermediate nodes addressing the load balancing issues and eventually increasing the network lifetime and network performance. Besides low packet loss, experimental results also reveal that the proposed strategy achieves higher throughput (14.35%) rate than that of existing MFR.