Keywords

1 Introduction

Mobile Ad-Hoc Network is a self-organizing network without wired backbone or a centralized control, in which the node forwards the packets to each other in a multi-hop manner. Typical applications include military, cell phone, laptop, personal conferences, meeting rooms etc.

As the Mobile Ad-Hoc network is infrastructure less, so it faces different challenges [1] that are not present in wired network. Topology changes occur in MANET both rapidly and unexpectedly. Working with limited bandwidth, maintaining quality, and assuring security—these are considered as important challenges in MANET. Power efficient routing is very important in MANET because the transmission power is expensive in wireless network when the nodes have limited battery energy.

Mobile devices in MANET use lithium batteries with average lifetime of one day. Conventional MANET routing protocols search routing path based on the delay which mainly result in the shortest path. But the nodes in the selected path will ‘die’ soon since they are overused. A single node in the routing path going to ‘dead’ condition can cause the entire network to fail.

In recent years, a large number of researchers are trying to solve the problem of energy-efficient data transfer in the context of Mobile Ad-Hoc networks [2]. The different existing protocols can be classified in the following two categories:

The protocols in the first category are based on minimum-power routing algorithms. A standard protocol in this category selects the route by minimizing the total power consumption of the entire network. The second category of protocols is based on battery aware routing algorithms that take care about battery life of individual nodes.

This paper is organized as follows- Sect. 20.2 gives a classification of different protocols of MANET based on power aware routing. Section 20.3 contains reviews of some existing research on power aware routing algorithm. Section 20.4 describes the details of the proposed power aware routing protocol using standard deviation. Section 20.4.1 elaborates the case study with a network scenario which compares the proposed protocol with some existing battery aware routing protocols.

2 Classification of Power Aware Ad-Hoc Routing Protocol

Several power aware routing protocols have been proposed in recent years. A classification [3] of these protocols has been shown in Fig. 20.1. The power-aware routing protocols can be classified into two categories: activity-based and connectivity-based. The activity based protocols deal with the power consumption based on network activity and connectivity based protocols maintain an effective connectivity.

Fig. 20.1
figure 1

Classification of power aware ad-hoc routing protocol

Full size image

2.1 Multicasting/Broadcasting

Multicasting/broadcasting protocols deal with power consumption efficiency when a single data or packet is sent to multiple destinations. Some examples are: Energy-efficient multicasting routing protocol (E2MRP) [4], On demand multicasting routing protocol (ODMRP) [5].

2.2 Active Energy Saving

Active energy saving protocol deals with minimizing the total energy consumed for a single packet. When a source n i has some data to send to the destination n k , the energy consumed per packet e is formulated by,

$$ e = \sum\limits_{i = 0}^{k - 1} {T(n_{i} ,n_{i + 1} )} $$

where T(n i , n i+1) represents the power consumption to transfer packet from node n i to n i+1 . This protocol selects the route by minimizing the energy consumed per packet. Some examples of this type of protocols are Power-Aware Routing Optimization (PARO) [6], Location-Aided Power-Aware Routing Protocol (LAPAR) [7].

2.3 Maximizing Network Lifetime

The maximizing network lifetime protocol focuses on the energy consumption for the individual nodes to ensure that it is used in a balanced manner. Overuse of single node can cause network failure. So this protocol selects the route through the node which has sufficient battery remaining. Some examples of this type of protocols are Minimal Battery Cost Routing (MBCR) [8], Power-Aware Source Routing (PSR) [9].

2.4 Topology Controlled

The protocols in topology controlled category adjust the node’s transmission power while maintaining desired topology. Some examples of this type of protocols are: Small Minimum-Energy Communication Network (SMECN) [10], Minimum-Energy Communication Network (MECN) [11].

2.5 Passive Energy Saving

Passive energy saving protocols deal with some passive mechanism by allowing a set of nodes to go to sleep mode at different period of time when the nodes are idle while maintaining the desired connectivity. Some examples are: PAMAS [12], Adaptive Fidelity Energy-Conserving Algorithm (AFECA) [13].

3 Review of Existing Power Aware Protocols

Several researches on power aware routing have been done in recent years. In this part we have presented a short review on these power aware routing protocols for MANET.

The MTPR [12] is a basic power aware routing protocol which always tries to minimize the total transmission power. In MTTPR, first it calculates the total transmission power for all possible routes between source 0 and destination D. Calculation of the total transmission power P(n i , n j ) between two hosts n i and n j can be used as a metric. The total transmission power \( P_{l} = \sum\nolimits_{i = 0}^{D - 1} {P(n_{i,} n_{i + 1} )} . \)

Finally it selects the route with minimum total transmission power to transfer a packet from source to destination. The MTTPR algorithm does not take care of battery life of every individual node, so MBCR algorithm is proposed by introducing an extra battery cost function [12] which is the inverse of remaining battery capacity. This algorithm minimizes the total summation of the inverse of remaining battery capacities for all routing paths. The algorithm cares about the individual nodes but still it does not protect those critical nodes which have very low remaining battery capacity. MMBCR [12] is a modification of the MBCR algorithm in such a way that no critical node will be overused. Without summing the battery cost functions of all nodes of every individual route, MMBCR finds the maximum battery cost among all nodes of different routes to find the critical nodes. Then it selects the route based on the minimum battery cost among those critical nodes. So this algorithm gives balanced use of the battery capacity of the nodes in the network. A hybrid approach- CMMBCR, was devised by C.K Toh [12], that tries to minimize the total transmission power and also avoid the battery having low remaining capacity by adding an extra threshold to each battery node. This algorithm first finds the minimum battery capacity (R i ) for all nodes of each route. If R i  ≥ Y (chosen threshold value) is true for some or all routes between a source and destination, then the MTPR scheme is applied to select the route among all possible paths which satisfy the previous condition. If any path does not satisfy the condition then the route is selected with the help of maximum battery remaining capacity by using the protocol MMBCR. Protocol MRPC [14] is a power aware routing algorithm that increases the lifetime of wireless network. It works in the same way as basic protocol MMBCR however MRPC chooses the nodes, not just by their remaining battery capacity but also with the energy required in network transmission for forwarding a packet over a specific link. MRPC first selects the node having smallest residual packet transmission capacity as ‘critical’ node among different possible paths. Then it selects the path having largest packet capacity among those ‘critical’ nodes. Another protocol PSR [9] tries to extend the lifetime of every node because if any one node dies there is a possibility of network partition. The algorithm finds a route π at route discovery time t such that the following cost function is minimized.

$$ C\left( {\pi ,{\text{t}}} \right) = \mathop \sum \limits_{i \in \pi } \rho i\left( {\frac{{F_{i} }}{{R_{i} (t)}}} \right)^{\alpha} $$

where, ρ i is the transmit power of node i, F i : full-charge battery capacity of node i, R i : remaining battery capacity of node i at time t and α is a positive weighting factor. Maleki et al. [15] proposed an on-demand routing protocol named Lifetime Prediction Routing that is based upon the prediction of battery lifetime of individual nodes. The main objective of this protocol is to extend the lifetime of the MANET. The objective function of LPR is as follows: \(\mathop {\hbox{max} }\nolimits_{\pi } T_{\pi } (t) = \mathop {\hbox{min} }\nolimits_{i \in \pi } (T_{i} (t)), \) where T π (t) is lifetime of path π and T i (t) is the predicted lifetime of the node i in path π. LPR uses dynamic distributed load balancing approaches to avoid the power-congested nodes and to use the path that is lightly loaded.

4 Proposed Work on Power Aware Routing Protocol Based on Standard Deviation

The main objectives of power aware routing are maintaining the minimum transmission power and increasing the network lifetime. There should be a balance between these two goals.

The optimal route from the battery life point of view will be such a route where all the nodes in the route lie in an average manner. For building such a protocol for power aware routing the mean can be used. But the mean cannot give a proper route selection if the battery costs are highly spread out from its mean. So the formulation of the standard deviation [16] can be applied for optimal path selection. Standard deviation actually shows a given set, how much spread out from its mean or average. After calculating the possible routes’ standard deviation from different node’s battery cost function, the optimal route can be selected in such a way that its standard deviation value is minimized. Another approach is introduced by multiplying a weight factor. This weight factor is calculated based on the number of nodes and nodes below mean value which gives more accurate results from the total link cost point of view.

4.1 Assumption

  1. 1.

    Every node is capable of calculating its remaining battery life.

  2. 2.

    Every node maintains a Remaining Energy Table which contains the details about battery capacity of that node and its neighbor nodes.

  3. 3.

    Link cost is dependent directly upon the hop count.

4.2 Algorithm Description

Our proposed power aware routing protocol PARSD is based on two phases: route discovery and route establishment.

In the first phase the protocol tries to find the possible paths and their remaining battery capacity by sending a Route Discovery Request packet. If the sender has some data to send, it sends the RDR packet to its neighbor nodes. The neighbor nodes attach its IP address and its remaining battery capacity in the RDR packet and forward the packet to its neighbor nodes except from where it was received, until the packet reaches its destination. After receiving the packet, the destination starts a timer (Tr) and waits for other RDR packets from the same source. When the timer (Tr) expires, it sends Reply RDR packet containing all the possible path list and its nodes remaining battery capacity details to the source. The RRDR packet is sent to the sender via the route through which the first RDR packet was received, because that path contains the minimum hop count. When the sender receives the RRDR packet, it stores the list of possible paths with its remaining battery capacity details.

The second phase does the route establishment by calculating the weight factor and standard deviation of the possible routes. First, it calculates the battery cost function of the nodes in the possible routes, which is the inverse of its remaining battery capacity. Then it calculates the mean of the battery cost functions for every possible route. The weight factor is calculated as the ratio between the total number of nodes on the selected path and the number of nodes whose battery cost function is below the mean in that path. The standard deviation is calculated by taking the battery cost functions of the nodes as population for the possible routes. The optimal value is calculated by multiplying the summation of standard deviation and mean. The final route is selected with the minimum optimal value among possible routes.

Algorithm 1: Route discovery

  1. Step 1.

    The sender node floods RDR packets to initiate a route discovery to all its neighbor nodes.

  2. Step 2.

    After receiving RDR packet every node checks whether it is destination node or not

    1. 2.1.

      If the node is not the destination, then

      1. 2.1.1.

        Attach its IP address in the RDR packet.

      2. 2.1.2.

        Attach its remaining battery capacity to the RDR packet.

      3. 2.1.3.

        Forward the packet to its neighbor nodes except the node from where the packet was received.

    2. 2.2.

      Else, the node is the destination node

      1. 2.2.1.

        Starts a timer (T r ) for a specific period of time.

      2. 2.2.2.

        Collects all the arriving packets of the same source until the timer (T r ) expires.

      3. 2.2.3.

        When the timer expires, attach the possible path list and the remaining battery capacity of the nodes in a Reply RRD packet.

      4. 2.2.4.

        Sends the packet to source node by the path from where the first RDR packet was received.

Algorithm 2: Route establishment

  1. Step 1.

    The source node receives RRDR packet.

  2. Step 2.

    The source node collects the possible path list and the remaining battery capacities of the nodes belong to that path from the packet.

  3. Step 3.

    The source node calculates the battery cost function of the nodes in the possible route. The battery cost function is the inverse of battery remaining which can be achieved from the following equation.

    $$ f_{i} \left( {c_{i}^{t} } \right) = \frac{1}{{c_{i}^{t} }} $$

    where \( c_{i}^{t} \) is the battery capacity of a host n i at time t and \( f_{i} (c_{i}^{t} ) \) is a battery cost function of node n i at time t.

  4. Step 4.

    The source node calculates the mean μ of those battery cost functions for every possible route. If N is the total number of nodes and x is the number from the population set then,

    $$ \mu = \frac{1}{N}\mathop \sum \limits_{i = 1}^{n} x $$
  5. Step 5.

    The algorithm then finds out the total number of nodes having a lower battery cost function than mean on every selected path. Then it calculates the weight factor by dividing the total number of nodes on the selected path and the number of nodes with battery cost function below the mean.

    $$ weight\,factor = \frac{Total\,number\,of\,nodes}{Number\,of\,nodes\,below\,mean } $$
  6. Step 6.

    Then it finds the standard deviation for each possible route by using each nodes cost function as a population. The standard deviation σ can be found using the following equation,

    $$ \sigma = \sqrt {\frac{1}{N}\mathop \sum \limits_{i = 1}^{N} (x_{i} - \mu )^{2} } $$

    where x i is the variable of population set and μ is the mean value. The standard deviation is calculated in following steps.

    1. 6.1.

      Take the battery cost function of all nodes for a single path as population set.

    2. 6.2.

      Calculate mean μ for the selected population set of the path.

    3. 6.3.

      Find list of deviations set by subtracting the mean from every population set

    4. 6.4.

      Square the deviation values.

    5. 6.5.

      Find the variance by calculating the average of all the square values of deviations.

    6. 6.6.

      Find standard deviation by calculating the square root of the average value.

  7. Step 7.

    For every route an optimal value is calculated from the following equation,

    $$ Optimal\,value = \left( {Standard\,Deviation + mean} \right) *weight\,factor $$
  8. Step 8.

    The final route is selected based on the minimum optimal value among all possible paths.

4.3 Case Study

Let’s take a network scenario with 6 possible paths between source and destination. A single path consists of minimum 2 nodes and maximum 8 nodes. The values in the nodes are the battery cost function of the nodes (Fig. 20.2; Tables 20.1, 20.2, 20.3).

Fig. 20.2
figure 2

Example network scenario

Full size image
Table 20.1 Battery cost function
Full size table
Table 20.2 Weight factor calculation
Full size table
Table 20.3 Standard deviation and optimal value calculation
Full size table

MTTPR selects the route by minimizing the total transmission cost. So, MTTPR scheme will select route c. The selection is not desirable from the network longevity point of view because the node 10 has very low remaining battery capacity. The path will be disconnected as soon as the node will die.

MBCR selects the route by minimizing the total battery cost function for a single path. The total battery cost of route a, b, c, d, e, and f are 150, 280, 100, 150, 190, and 260. So it will select the route c. But route c contains a critical node 10. So the selected path is not an optimal route.

MMBCR first finds the maximum battery cost and then select the minimum among them. The maximum battery cost among route a, b, c, d, e, and f are 60, 90, 90, 60, 60, and 50. Route f (50) has minimum among them. So, route f will be selected. The route f contains 8 hop counts which increase the total transmission cost. With respect to total battery cost (which is 260), it is greater than other four routes. The route selection is not optimal from both the battery cost and total transmission power point of view.

Our proposed protocol PARSD selects the route based on minimum optimal value which can be derived by multiplying the weight factor with the summation of standard deviation and mean value for every possible route. Here route d has minimum optimal value. So route d will be selected. Route d contains node 11, 12, 13, 15 which has enough battery remaining to transfer data. The total battery cost 150 is also less and the route does not contain any critical node. This ensures the even dissipation of power by all the nodes and consequently longer network lifetime.

5 Conclusion

Designing an efficient power aware routing protocol is a very challenging task which requires meeting both the goals of minimizing the total transmission cost and increasing the network lifetime. Our proposed protocol PARSD tries to achieve both these goals. The technique of using standard deviation enables us to select an optimal route where the difference in the energy level between the highest and lowest battery capacity nodes is minimum. This proper power optimization actually ensures an even distribution of the battery power dissipation by the nodes thereby increasing the overall lifetime of the network. The weight factor gives the result more accuracy as it increases the optimal value for those routes where maximum nodes lie above the mean. From the link cost point of view this weight factor tries to select the minimum hop count route thereby reducing the total transmission power.