Optimal Path Selection in MANET Considering Network Stability and Power Cost

INTRODUCTION

A Mobile Ad hoc Network (MANET) is an autonomous system that has battery-operated wireless devices connected by wireless links that work independent of any central control. Typically in MANET, each node acts as a router in a routing path that forwards data for the other nodes in the network. Historically, cost efficiency has been a key objective for network routing protocols. The cost of forwarding data packets can be defined and determined in various ways, taking into account several factors, such as cost of energy used to forward the packets, hop count and delay. Recent MANET routing protocols focus on energy efficiency and power awareness (Anderegg and Eidenbenz, 2003; Doshi et al., 2002; Wieselthier et al., 2002; Yin and Lin, 2005) because of the limited battery power supply of the nodes. In the context of this study, the routing cost of a packet means the amount of battery energy required to send the packet from the source node to the destination node. The common criterion for these protocols is to use a route that incurs a minimal overall power cost. However, it may possess a harmful impact on the network connectivity. When the selected path contains nodes with little remaining energy, those nodes would lose all their energy and die within a short amount of time. Also, nodes with a large number of paths through them would die out sooner and the network may get disconnected, when a node in the current route dies.

Figure 1 shows an ad hoc network with the nodes (circles) and their active links (lines). The active links between the nodes are labeled with the single packet forwarding cost through them. Note that, nodes 6 and 14 may have a very large number of connections through them and their packet forwarding costs are lower. These two nodes will be used most frequently for forwarding data packets in the network, resulting in their early death and affecting the network connectivity or stability.

Roughly speaking, the lifetime of a MANET is the time duration for which most of the nodes remain connected, which in turn depends upon the lifetime of the nodes.

Fig. 1:	Ad hoc network with active nodes and their connecting links

The target of Lifetime Prediction-based Routing (LPR) protocols (Kim et al., 2002; Korsnes et al., 2005; Maleki et al., 2003; Sankar and Liu, 2004) is the maximum lifetime of the network. These algorithms estimate the probable lifetime of many paths between the source and the destination and select the path with the longest lifetime. In other words, they use the path in which the nodes have the most residual energy. However, these algorithms do not take into consideration the routing cost in their path selection. Thus, they suffer from higher routing power consumption (from the nodes having relatively higher residual energy). With this higher power consumption in the packet forwarding, the overall power loss in the network increases, resulting in a shorter network lifetime.

Present proposed routing protocol, called Cost-effective Lifetime Prediction-based Routing (CLPR), is a reactive routing protocol like Dynamic Source Routing (DSR) (Johnson, 2003). A preliminary version of the protocol was presented at the ICOIN’05 conference (Huda et al., 2005). The objectives of CLPR are to maximize the network lifetime by balancing the variance in the residual energy of the nodes and to minimize the overall power consumption in the network. We tried to find a balance between these two contradictory parameters. CLPR results in a more stable network than the Minimum Energy Routing (MER) algorithms (Anderegg and Eidenbenz, 2003; Yin and Lin, 2005; Wieselthier et al., 2002) and also results in less power loss than LPR (Agarwal et al., 2000; Kim et al., 2002; Korsnes et al., 2005; Maleki et al., 2003; Sankar and Liu, 2004). Experimental results show that the path efficiency of CLPR, which is the ratio of the lifetime of the path and the routing cost through that path, is better than that of MER and LPR and on average, a node lasts longer when using CLPR than a node when using MER or LPR.

RELATED WORKS

Due to the limited power supplies of the nodes in MANET, many energy efficient broadcast/multicast algorithms have emerged (Chang and Tassiulas, 2000; Doshi et al., 2002; Singh et al., 1998; Wan et al., 2002; Wieselthier et al. 2002; Yin and Lin, 2005). One major approach for energy conservation is to route a communication session along the path that requires the lowest total energy consumption. This optimization problem is also referred to as Minimum-Energy Routing (MER) (Doshi et al., 2002; Wan et al., 2002). Singh et al. (1998) proposed a routing algorithm based on the minimization of the amount of power (or energy per bit or packet) required to get a packet from the source to the destination. The path selection is chosen based on the following equation

(1)

where T_i,i+1 denotes the power expended during transmission (and receiving) between two consecutive nodes, n_i and n_i+1 (i.e., link cost), in route π.

The link cost can be defined for two cases: (a) when the transmit power is fixed and (b) when the transmit power is varied dynamically as a function of the distance between the transmitter and intended receiver. In the first case, the energy for each operation (receive, transmit, broadcast, discard, etc.) of a packet is given by

(2)

where b and c are the appropriate coefficients for each operation. Coefficient b denotes the packet size-dependent energy consumption, whereas c is a fixed cost that accounts for the acquisition of the channel and for the MAC layer control negotiation.

Energy efficiency has also been considered for Medium Access Control (MAC) and new MAC schemes have been proposed (Jin and Cho, 2000; Stojmenovic and Lin, 2000). Stojmenovic and Lin (2002) proposed a local routing algorithm for the second link cost case. The authors assumed that the power needed for transmission and reception was a linear function of d^α, where d is the distance between the two neighboring nodes and α is a parameter that depends on the physical environment. The authors made use of GPS position information to transmit packets with the minimum required transmit energy. The key requirement of this technique was that all the nodes in the MANET must know the relative positions of the nodes. However, this information may not be readily available and the power dissipation overhead of the GPS device became an additional power draw on the battery source of the mobile node.

Unfortunately, minimum energy (or energy efficient or power aware) routing protocols may need frequent re-routing and may even cause a network disconnection if the minimum power loss route contains some nodes with little remaining energy. Korsnes et al. (2005), Kim et al. (2002), Maleki et al. (2003) and Sankar and Liu (2004) have presented network Lifetime Prediction-based Routing (LPR) techniques. These routing protocols use the lifetime of nodes, which is a function of the remaining battery energy, as the metric for selecting a routing path. These protocols favor the path with the maximum predicted lifetime. Maleki et al. (2003) calculated the lifetime of a node based on the residual battery capacity and the past rate of energy discharge of that node. The lifetime of a path is considered the minimum lifetime of all the nodes along the path and is calculated by

(3)

where T_π(t) is the lifetime of path π and T_i(t) is the predicted lifetime of node n_i in path π.

The minimum lifetimes of all the paths from the source to the destination are calculated and finally the path, which has the maximum value of the calculated minimum lifetimes, is selected for packet forwarding. The main objective of LPR is to minimize the variance in the remaining energy of all the nodes and thereby prolong the service time of the MANET. Although, LPR selects the path that has the maximum predicted lifetime, this technique does not take into consideration the routing cost (power cost) of the selected path. It would often select a path with a very high cost. Thus, LPR protocols suffer from poor cost effectiveness. The rates of energy drain from the network in these protocols are higher than those in the minimum energy routing protocols. Due to the selection of a high power consumption route, the overall power loss of the network is higher, resulting in a shorter network lifetime.

COST-EFFECTIVE LIFETIME PREDICTION-BASED ROUTING

Our network model: In present network model, we use a mobile ad hoc network N = (V, E) consisting of a set of nodes V = {v₁,…..,v_n} that represent mobile devices, a set E ⊆V xV of edges {(v_i, v_j), 1 = I, j = n} that connect all the nodes and a weight function ω for each edge (v_i, v_j) that indicates the transmission cost of a data packet between node v_i and v_j. Each node has a unique identification number, but which nodes are currently in the network are not known a priori, nor is edge set E or weight function ω known. A node cannot control the direction in which it sends data and thus data are broadcast to all the nodes inside its transmission range. Nodes can move and the edge cost between any two nodes can change over time. Also, the lifetime of any node can change over time. However, for simplicity, we assume a static network during the route discovery phase.

Lifetime prediction: For lifetime prediction, each node tries to estimate its battery lifetime based on its past activity (Maleki et al., 2003). This is achieved by keeping track of the last N (= 10) values of residual energy and the corresponding time instances for the last N packets received/relayed by each mobile node using a Simple Moving Average (SMA) predictor. This information is recorded and stored at each node.

Packet routing cost: The most important cost function in wireless ad hoc networks is the transmission power of the nodes in the route. We define the packet routing cost of a route as the total energy consumed during transmission by all the nodes along the path from the source to the destination.

Route setup: CLPR is a reactive routing protocol, which only starts computing routing paths when a node initiates a session. It is a DSR-like (Johnson, 2003) route discovery protocol, which channels all information regarding the cost and lifetime to the destination node. The destination node computes the cost and lifetime of each path and selects the path according to the path selecting parameter and sends this path information back to the source.

Let us assume that the maximum possible lifetime of any node is L and the maximum possible transfer cost between any two nodes is C. We define a scaling factor ξ as the ratio of the two parameters.

(4)

At any instance, let there be n paths (π₁, π₂,…. π_n) from the source to the destination. The lifetime of a path is bounded by the lifetime of all the nodes along the path. When a node dies along a path, we can say that the path no longer exists. So, we can say that the lifetime of a path is the same as the minimum lifetime among the lifetimes of all the nodes along the path. The network lifetime is defined as the time taken for a fixed percentage of the nodes to die due to energy exhaustion.

In CLPR, all the nodes along the path, except the destination node, calculate their predicted lifetime T_i with the following equation and replaces the minimum lifetime in the packet header with T_i, if T_i is lower than the existing minimum lifetime value in the header.

(5)

where E_r,i(t) is the remaining energy at the given instance, when the i^th packet is being sent or relayed through the current node, R_k(t) is the rate of energy depletion of the current node when the k^th packet was sent, which is calculated by the ratio of the difference between the residual energies of the nodes for (k-1)^th and k^th packets and the difference between the arrival times of these two packets and N is the length of the history used.

The lifetime τ_i of a path π_i can be defined as:

(6)

where T_j(t) is the predicted lifetime of node n_j in path π_i.

The cost of a path is the sum of all the costs calculated between two consecutive nodes along the path from the source to the destination. The cost of a path π_i can be defined as:

(7)

where is the number of nodes in the path π_i and is the cost between nodes n_j and n_j+1 of the path π_i.

Similar to LPR, when an intermediate node receives a RREQ packet, it starts a timer (T_r) and stores its minimum lifetime in the header of that packet. When a new RREQ packet arrives at a node, if its partially built path does not contain the node itself, the lifetime and cost of this route is updated and the new RREQ packet is forwarded.

In CLPR, the destination waits for a threshold amount of time (T_r) after the first RREQ packet arrives. During that time, the destination examines the cost of the route of every RREQ packet that arrives and when the timer (T_r) expires, it will subsequently drop any received RREQs. The destination node calculates the path selecting parameter β value of all the paths with the following equation.

(8)

where τ_i is the total cost of this path represented by Eq. 6 and ς_i is the lifetime of this path represented by Eq. 7.

CLPR selects the path with the largest β value. If more than one path having a max β_i value is found, the path that contains the least number of nodes among them is selected. Thus, the proposed method is inclined to select a path having a longer lifetime τ and lower cost ς. The receiver sends back the route reply (RREP) along the selected path. Every node that hears this route reply adds this route information to its route cache.

Figure 2 is an example of an ad hoc network with different path selections. The nodes are labeled with their lifetime values and the edges are labeled with the cost between its two adjacent nodes.

Fig. 2:	Different path selection in LPR, MER and CLPR

There are six paths from source (S) to destination (D). They are S→A→B→D, S→A→B→C→F→G→D, S→E→F→C→B→D, S→E→F→G→D, S→C→F→G→D and S→C→B→D. If we calculate the total cost along each path, we get a cost value of 19 for the S→A→B→D path, 36 for the S→A→B→C→F→G→ D path, 40 for the S→E→F→C→B→D path, 29 for the S→E→F→G→D path, 24 for the S→C→F→G→ D path and 21 for the S→C→B→D path. Similarly, if we calculate the lifetimes of each path, we get a lifetime value of 100 for the S→A→B→D path, 100 for the S→A→B→C→F→G→D path, 400 for the S→E→F→C→B→D path, 450 for the S→E→F→G→D path, 400 for the S→C→F→G→D path and 400 for the S→C→B→D path.

If we select the path with the minimum cost value, as is done in minimum energy routing, we get the S→A→B→D path that has a cost value of 19 and a lifetime of 100. In LPR, the S→E→F→G→D route is chosen because of its lifetime of 450 and cost value of 29. While MER is greedy about cost minimization, LPR is greedy for (probable) the highest predicted lifetime. Therefore, MER suffers from a poor path lifetime and LPR suffers from a high routing cost.

For the CLPR protocol, let us assume that the maximum possible cost © between any two nodes is 15 and the maximum possible lifetime (L) of any node is 600. So the scaling factor ξ becomes 40. Therefore, using CLPR, the path selecting parameter β for the paths S→A→B→D, S→A→B→C→F→G→D, S→E→F→C→B→D, S→E→F→G→D, S→C→F→G→D and S→C→B→D are 0.1316, 0.069, 0.25, 0.3879, 0.4166 and 0.476, respectively. The S→C→ B→D path has the highest β value. So, the selected path is S→C→B→D having a cost value of 21 and a lifetime of 400.

Route maintenance: A route may become invalid if the connection between two nodes on the path is lost due to the movement of the nodes or one of the intermediate nodes uses up all its energy and dies. In the first case, a new RREQ is sent out and the entry in the route cache corresponding to the node that has moved out of range is purged. To cope with the termination of a node due to its energy loss, the following policy is adopted. Once the route is established, the weakest node in the path (the node with minimum β value at the route discovery time) monitors the decrease in its battery lifetime. When this remaining lifetime decrease goes beyond a threshold level, the node sends a route error back to the source. This route error message forces the source to re-initiate a route discovery. CLPR adopts this local approach because it minimizes the control traffic.

SIMULATIONS

Simulation setup: In present discrete event driven simulation, we used 10 to 40 nodes. The lifetimes of the nodes were taken randomly between 1 and 600 sec while the transmission costs of the neighboring nodes were varied from between 1 and 15 units. Every node had a fixed transmission power that allowed for a 50 m transmission range with a free space propagation model. The sources and destinations were spread uniformly over the simulation area; a random number of source destination pairs were set up; the area was 300x300 m. A link was considered established when two nodes reached each other’s transmission radius and broken when their distances exceeded the transmission radius. Random connections were established between the nodes within the transmission range. The data packet was 512 bytes with CBR traffic at a rate of 4 packets sec^-1. The simulation time was normalized to 15000 sec. The nodes followed the random waypoint mobility model with a 5 m sec^-1 of velocity and no pause time. Each relayed or transmitted packet had a cost factor and that cost was considered the cost at the transmitter node.

Simulation results: Here, we describe the results obtained from the simulation for various parameters. Figure 3 compares the lifetime of a link in CLPR with those of the two other related protocols. From Fig. 3, we can see that in CLPR, the lifetime of a path between the source node and the destination node was very close to the maximum lifetime (as in LPR), while the lifetime of MER was the worst among the three. In any case, as the number of nodes increases, the mean hop counts of the paths increase. Therefore, the minimum lifetime among the nodes’ lifetimes (i.e., lifetime of the path) decreases. Thus, the lifetime of the selected path decreases. If we consider the lifetime of LPR 100%, then on average MER and CLPR have 47 and 95% lifetimes, respectively, when compared to LPR. As the number of nodes in the network increases, the lifetimes in LPR and CLPR draw closer to each other.

Fig. 3:	Relative lifetime of route (before data packets routed) in LPR, MER and CLPR versus No. of nodes

Fig. 4:	Relative routing cost in LPR, MER and CLPR versus No. of nodes

This is because, with higher node densities, more paths exist having similar costs and CLPR can select the path having the highest lifetime (closer to that of LPR).

The routing cost of a packet has been projected in Fig. 4. From the Fig. 4, we see that as the number of nodes increases, the data routing cost from the source to the destination decreases. This is because the links of a path shorten, which requires less power.

The MER requires the minimum cost (i.e., power) among the three protocols, followed by the CLPR and the LPR. The difference in routing costs between MER and LPR increases with an increase in the number of nodes. The average routing cost of MER is much less than that of LPR and that of CLPR lies between them. The routing cost of MER is about 26% less than that of LPR and that of CLPR is about 12% less than that of LPR.

Although, MER requires the least amount of cost among the three, its network stability is poor. On the other hand, LPR seems to have the maximum network lifetime, but it requires a higher routing cost. Due to the higher routing cost (power consumption) in LPR, in networks with lower node mobility, a node will lose its energy earlier in LPR than in CLPR. We find that CLPR is better than LPR when we take the cost factor into consideration and also better than MER when considering the stability. The CLPR protocol does not suffer extremely from either high routing cost or poor network stability. Although CLPR may select a path with a cost that is a little higher than one with the least cost and a path with slightly less lifetime than one with the highest lifetime, it reaches an equilibrium between the two contradictory goals, the network stability and the cost-effectiveness of the route.

The path efficiency expresses how efficient a path is in terms of lifetime and cost. We define path efficiency as the ratio of the lifetime of the path and the routing cost through that path. The longer the lifetime, the higher its efficiency; the lower the cost, the higher its efficiency.

The path efficiency of CLPR was always the best among the three protocols followed by LPR (Fig. 5). The path efficiency of all the protocols decreased with an increase in the number of nodes because of the decrease in the path lifetime. The path efficiency in CLPR was better than that in LPR, because it used lower cost paths and the path efficiency in MER was the lowest, because it did not consider the path lifetime. On an average, the path efficiency in CLPR was about 7% higher than that of LPR and the path efficiency in MER was about 47% lower than that of LPR. Due to the higher path efficiency of CLPR, a route will last longer in CLPR than in LPR and MER. Even though, the (predicted) lifetime of a selected route in LPR is the highest, due to higher energy consumption, a node in an active path dies earlier in LPR than in CLPR, especially under low mobility conditions.

Figure 6 shows the time taken for a number of nodes to die (in a 20 node scenario, 5 m sec^-1 velocity) in the three protocols. According to the definition of network stability (time before a fixed percentage of nodes to die), the network using CLPR was the most stable.

Figure 7 shows the Root Mean Square (RMS) value of the percentage of energy (E_rms) used as a function of time (Schurgers and Srivastava, 2002). The energy used by a node in CLPR was the lowest (residual energy of a node is the highest) for longer durations. This means that the energy consumption in the network was distributed more uniformly among the nodes and a node was not overloaded like MER. So, the variance of the residual energy is minimal in CLPR, resulting in the highest network stability. However, with the increase in node mobility, the network stability of MER and LPR approaches that of CLPR.

Fig. 5:	Relative path efficiency in LPR, MER and CLPR versus No. of nodes

Fig. 6:	Time versus No. of dead nodes

Fig. 7:	Erms value of energy consumption for node

If the node mobility is increased, a route remains valid for a shorter time duration in any protocol and more route discoveries are required. As a result, automatic load balancing is achieved. Thus, under higher mobility conditions, the MER will perform better than under a lower mobility condition.

Figure 8 shows the packet delivery ratio (ratio of the number of delivered data packets to the number of generated data packets of all the nodes) of the three protocols with varying mobilities.

Fig. 8:	Packet delivery ratio in three related protocols

With an increase in the mobility, an active route becomes invalid more frequently and more packets are lost. The packet delivery ratio in CLPR is better than that in LPR and MER, especially under lower node mobility conditions because of its fewer route discoveries and re-routing requirements. In MER, a route becomes invalid more frequently than in CLPR because of the lower lifetime paths being used. In LPR, a route becomes invalid earlier than in CLPR because it uses a costlier path (more power consumption) than in CLPR.

The original DSR protocol does not need to find a lot of possible paths between the source and the destination. However, CLPR (also LPR and MER) does and based on their route selection criteria, they select one path among these for sending a data packet. Thus, the route discovery overhead (e.g., latency and number of control packets) in these protocols will be higher than that of DSR. However, since the network stability of mobile ad hoc networks is very important, the route discovery overhead in CLPR may be acceptable.