An Effective Routing Protocol with Guaranteed Route Preference for Mobile Ad Hoc Networks

Abstract

Battery power and queue conservation are critical issues in mobile ad hoc network (MANET). These two factors not only affect the delivery ratio but also the lifetime of the network. In this work, we will propose a simple and effective routing protocol to extend the lifetime and to evenly distribute the traffic loads of the networks as possible. Furthermore, a concept of serving capacity is introduced to reflect the level of congestion around a node. In this way, the proposed routing protocols can avoid network congestion and achieve higher packet delivery ratios. The extensive computer simulation is conducted to compare the proposed protocol against many existing routing protocols. The results show that the proposed routing protocol can have better performance in terms of queueing length, lifetime, and packet delivery ratio and have comparable end-to-end delays.

1. Introduction

Recently, with the emergence of mobile applications [1–3], mobile ad hoc networks (MANETs) have attracted significant research activities due to their flexibility. In MANETs, wireless nodes form a temporary network without the help of any existing infrastructure and are allowed to move freely. Thus, two arbitrary nodes, which would like to communicate with each other, may not be in the radio range of each other. In this case, direct communication is not possible. Therefore, a routing path consisting of other nodes in the networks has to be established before the actual communication can be ensured. In view of this, the routing protocol becomes the key to the success of MANETs and has been an active field of research in MANETs [4–6].

In MANETs, mobile nodes are battery-powered and have limited queue size. When a node falls short of battery power, it would not be able to provide any service to other nodes in the network. As the number of such nodes increases, to some extent, the network becomes partitioned and communication among some nodes cannot be possible. On the other hand, when the queueing length of a node increases, the delay experienced by a packet arriving at this node increases as well. If no measure is taken, the overflow occurs and the packets start to get dropped. This degrades the performance of network. In light of these, balancing the loading and avoiding the low-battery-power nodes to prolong the lifetime of the network are two important issues when designing a routing protocol for MANET. These two issues inspire two main categories of routing protocols, namely, the power-aware routing protocols [7–12] and the queueing-aware routing protocols [12–15].

The power-aware routing protocols take the available battery power of nodes in the network as a whole and pay more attention to how to tap this resource in an efficient way and how to extend the lifetime of the network as much as possible. On the other hand, the queueing-aware routing protocols use metrics as functions of the queueing length for helping search the route. The protocols in this category mainly aim at distributing the traffic evenly over the network and avoiding the selection of those nodes with longer queueing length as much as possible. Both categories have their advantages and disadvantages. It would be more desirable if a routing protocol can take both the factors of battery power and queueing length into account. The merits of taking both factors into consideration have been shown in [12].

In this work, we will propose a new metric to help us find a route with preferable remaining battery power level and queueing length. In addition, how to avoid the network congestion [15–18] is also essential when selecting a route for communication. Traditionally, the way to judge the level of contention is based on either the queueing length of a node [15, 16, 19], packet drops [19], or delay [17, 18, 20]. However, the available bandwidth around a node can also reflect the congestion around that node. The reason behind it is that the bandwidth in the wireless environment is a shared medium. In power-aware routing protocols or queueing-aware ones, a node with higher remaining battery power or shorter queueing length would be selected with higher chance. However, if the available bandwidth around this node is little, the network in this area will become congested and this will consequently degrade the performance of the network. We will introduce a concept of serving capacity to prevent this from happening.

Section 2 will introduce some related works. Section 3 shows the details of the proposed protocol. Section 4 presents the simulation results of the proposed protocol and other protocols. The concluding remark is given in Section 5.

2. Related Works

In MANETs, many routing protocols were proposed and each of them adopted its own metric to help select a suitable route for a pair of nodes. Among these routing protocols, Ad hoc On Demand Distance Vector (AODV) [21] and Dynamic Source Routing (DSR) [22] are the most common routing protocols in MANETs due to their simplicity. AODV and DSR have their merits and demerits [23]. Since the proposed routing protocol is based on AODV, a brief description of AODV will be given below.

In AODV, the route discovery of these routing protocols is achieved by flooding the route request (RREQ) messages towards the destination node. When an intermediate node receives a RREQ message for the first time, it creates a reverse link to the upstream node of the received RREQ message and rebroadcasts the RREQ message immediately. The later arrived RREQ messages will be dropped. When the destination receives the first RREQ message, it replies a route reply (RREP) message to the source node along the traversed route of the replied RREQ message and creates the forward link. If the later received RREQ message has less hop counts than the replied RREQ message, the destination node replies a RREP message again to tell source node using the shorter one. In this way, a route with the minimum hop counts can be found. However, AODV does not take other factors such as the remaining battery power and the queueing length into consideration when selecting a route for a pair of nodes.

The objective of the power-aware routing protocols is to prolong the network lifetime. The lifetime can be extended by avoiding those nodes with low remaining battery power and directing the traffic to those nodes with abundant remaining battery power. To this end, much of the literature [7–10, 24] proposed avoiding selection of the low-battery-power nodes. In these protocols, the mechanisms of route selection are modified versions of [21, 22]. In the route searching, when an intermediate node receives a RREQ message, it delays for a while to collect RREQ messages and selects the RREQ message with minimum cost. The cost of current node is calculated and the cost of the RREQ message will be updated. Then, the node rebroadcasts the RREQ message with minimum cost. The destination also selects the RREQ message with minimum cost and replies an RREP message along the traversed path of selected RREQ message.

The main difference of the proposed protocols is the design of the cost function. In [7, 8], the cost of the RREQ message is the inverse of the summation of the remaining battery power of the traversed nodes. For [9, 10], the cost is the inverse of the minimum remaining battery power of the traversed nodes. Using either type of the cost, a route with more remaining battery power can be found and the lifetime of the network can be prolonged. However, the main disadvantage of the power-aware routing protocol lies in the unbalanced usage of battery power of a node. The extension of the network lifetime is achieved at the expense of extensive usage of battery power of those nodes favored by the metrics adopted in those protocols.

Another category of prolonging the lifetime in the network is to balance the loading of the nodes according to the queueing length of the nodes [13, 14]. The rationale behind the queueing-aware routing protocols is that the bottleneck of the network happens at nodes with high load and with long queueing length. By distributing load more evenly throughout the entire network, hot spots can be reduced and the lifetime of the network is expected to extend. The assumption behind this is that the battery power of each node in the network is similar. When the remaining battery power of nodes is highly diverse, the advantage of queueing-aware protocols is compromised. Thus, it is sensible to adopt a routing protocol considering both the remaining battery power and the queueing length of nodes in the network.

The work in [12] proposed a protocol which takes both remaining battery power and queueing length into consideration. They found that the lifetime can be further improved when using a metric as a function of both remaining battery power and queueing length. However, in these protocols [7–10, 12–14], the available bandwidth around a node is not considered when choosing a route for a given communicating pair. Thus, it may run into a situation where a node has abundant remaining battery power and available queue size but little available bandwidth is chosen to provide service. This will cause extra contention, incur unwanted packet drops, and, as a result, induce additional delay. To avoid this, in this work, we will adopt a metric called serving capacity to help find a route with more available bandwidth. By considering the battery power, queueing length, and serving capacity, the proposed routing protocol can enjoy higher delivery ratio, shorter queueing length, longer network lifetime, and comparable end-to-end delay when comparing with the existing protocols.

3. The Proposed Routing Protocol

We assume each node in the mobile ad hoc network is power-limited and has limited queue size. Here, let $P_i$ be the remaining battery power and $Q_i$ be the current queueing length of node i. $P_i$ and $Q_i$ are normalized by the maximum battery power and maximum queue size, respectively. We assume that the maximum battery capacity and the maximum queue size of each node in the network are the same. We let the maximum receiving rate and the maximum transmission rate of node i be $R_i^s$ and $R_i^t$ , respectively. $R_i^s$ and $R_i^t$ may not be the same due to the effect of the channel. $R_i^s$ and $R_i^t$ can be determined by first evaluating the SNR of received signals from the upstream node and the downstream one and adopting the Shannon capacity to estimate the receiving and transmission rate.

The proposed routing protocol takes three factors into account. The first one is the transmitting or receiving capability of a node, the second one is the minimum battery power of a route, and the third one is the maximum queueing length of a route. The first factor reflects the availability of a node. When either the transmitting or receiving capability of a node cannot support further request, a node will not participate in the current route search. In this work, a serving capacity of a node is defined in the following section to judge whether a node is able to respond to route requests. To extend the lifetime of a chosen route, it is necessary to search for a route whose minimum battery power should be as large as possible. In view of this, the second factor is taken into account when designing the proposed protocol.

However, with first two factors only, we can imagine that those nodes having better serving capacity and higher batter power will be chosen more often than those who do not. In this case, the queue could be built up at those nodes and this would cause excessive queueing delay at those nodes. To avoid this, the proposed routing protocol also would like to find a route whose maximum queueing length can be minimized as much as possible at the same time. In the following subsections, we will first give the route selection criterion of the proposed routing protocol and its reason behind following the route search mechanism and route maintenance mechanism.

3.1. Route Selection Criterion

In this subsection, we will present the route selection criterion and the reason why we choose such a criterion. We first define ${\mathrm{\Lambda }}_i=\max \{\min \{R_i^t-{\check{r}}_i,R_i^s-{\widehat{r}}_i\},\mathrm{0}\}$ as the serving capability of node i, where ${\check{r}}_i$ and ${\widehat{r}}_i$ are the current transmission rate and receiving rate, respectively. The defined serving capacity is used to reflect the transmitting or the receiving capacity of a node. When the serving capacity is zero, it means that a node cannot support additional incoming or outgoing traffic. When this happens, a node cannot participate in any further route requests. In addition, since serving capacity indicates the level of traffic load of node i, it can also reflect the level of congestion around a node. If a node has a smaller serving capacity, this means that either its available outgoing rate or its available incoming rate is smaller. Compared to the regions around the nodes with larger serving capacities, the level of the congestion of the region around this node would be severer. Consequently, if more traffic is injected into this region, it would be easier to get congested than the regions around those nodes having larger serving capacities. Therefore, the serving capacity in this work is used to achieve two purposes: the first one is to decide whether a node can participate in a route discovery and the second one is to be used to reflect the level of congestion around a node.

One of the goals of the proposed routing protocol is to choose a route with less chance of the occurrence of congestion. As mentioned above, the serving capacity can be used to reflect the congestion level. Based on this, under what conditions will a route have less chance of having congestion? First, let us see what happens if the serving capacities of nodes along a route are similar. When the serving capacities of nodes along a route are close, with high chance, the levels of congestion of nodes along the route would be similar as well. Nevertheless, under this situation, if the maximum serving capacity of this route is small, the likelihood of having congestion along the route would be high.

In addition, multiple points of bottleneck could occur along this route. Thus, if we would like to choose a route to avoid congestion occurring at multiple nodes, the chosen route has to fulfill two conditions in terms of serving capacity. The first condition is that the maximum serving capacity of this route should be as large as possible. The second one is that the serving capacities of nodes along the chosen route should be as similar as possible. This condition would lead to the ratio of the minimum and the maximum serving capacities being as large as possible. To achieve these two conditions, we adopt the following metric to judge whether a route can possibly fulfill these criteria. Let ${\mathrm{\Psi }}_i$ be the set of routes perceived by node i for a given communicating pair and let ${\mathrm{\Psi }}_{ij}$ be the jth route in ${\mathrm{\Psi }}_i$ , which contains the information of the traversed nodes up to node i. The proposed metric is defined as

$$\begin{array}{cc}& \left(\frac{{\mathrm{\Lambda }}_{{\mathrm{\Psi }}_{ij}}^{\min }}{{\mathrm{\Lambda }}_{{\mathrm{\Psi }}_{ij}}^{\max }}\right){\exp }^{{\mathrm{\Lambda }}_{{\mathrm{\Psi }}_{ij}}^{\max }/{\tilde{\mathrm{\Lambda }}}_{{\mathrm{\Psi }}_i}^{\max }},\end{array}$$

(1)

where ${\mathrm{\Lambda }}_{{\mathrm{\Psi }}_{ij}}^{\min }={\min }_{\kappa \in {\mathrm{\Psi }}_{ij}}{\mathrm{\Lambda }}_{\kappa }$ , ${\mathrm{\Lambda }}_{{\mathrm{\Psi }}_{ij}}^{\max }={\max }_{\kappa \in {\mathrm{\Psi }}_{ij}}{\mathrm{\Lambda }}_{\kappa }$ , and ${\tilde{\mathrm{\Lambda }}}_{{\mathrm{\Psi }}_i}^{\max }={\max }_j{\max }_{\kappa \in {\mathrm{\Psi }}_{ij}}{\mathrm{\Lambda }}_{\kappa }$ . The metric in (1) serves two purposes. The first term in (1) is called the service ratio of the jth route perceived at node i and is used to judge the closeness of the minimum and maximum serving capacity of a given route up to the current node. When ${\mathrm{\Lambda }}_{{\mathrm{\Psi }}_{ij}}^{\min }$ and ${\mathrm{\Lambda }}_{{\mathrm{\Psi }}_{ij}}^{\max }$ are close, the ratio between these two quantities will be close to one. Thus, as the service ratio becomes larger, the difference between the minimum and maximum serving capacity normalized by the maximum serving capacity becomes smaller. However, using this ratio alone will lead to the situation of choosing a small ${\mathrm{\Lambda }}_{{\mathrm{\Psi }}_{ij}}^{\max }$ while ${\mathrm{\Lambda }}_{{\mathrm{\Psi }}_{ij}}^{\min }/{\mathrm{\Lambda }}_{{\mathrm{\Psi }}_{ij}}^{\max }$ is large. In addition, the purpose of the second term in (1) is to prevent this situation from occurring too often. It is clear that the second term is large when ${\mathrm{\Lambda }}_{{\mathrm{\Psi }}_{ij}}^{\max }$ is close to ${\tilde{\mathrm{\Lambda }}}_{{\mathrm{\Psi }}_i}^{\max }$ . This factor will help us choose a route whose maximum serving capacity is close to the overall maximum serving capacity of all perceived nodes at an intermediate node or at the destination.

Combining the above two terms, the metric would have the following properties. First, if two or more potential routes have the same service ratio, the second term will guarantee that a route with higher maximum serving capability will be selected. This means that the traffic will be directed to a route with less traffic and the congestion can be prevented. Secondly, if two or more potential routes have the same second term, the first term ensures a route with higher service ratio and it will be chosen. That is, the route with smaller discrepancy in the minimum and the maximum serving capacities will be favored against those routes with larger discrepancy when the second terms of (1) of different routes perceived at a node are the same. Thus, under this situation, this metric routes the traffic towards area with lighter load and bypasses the congestion region. These two properties suggest the proposed metric distributes the traffic load evenly throughout the entire network by way of congestion speculation based on the serving capacities of nodes of routes.

The metric in (1) only serves to choose a route with larger ${\mathrm{\Lambda }}_{{\mathrm{\Psi }}_{ij}}^{\min }/{\mathrm{\Lambda }}_{{\mathrm{\Psi }}_{ij}}^{\max }$ and larger ${\mathrm{\Lambda }}_{{\mathrm{\Psi }}_{ij}}^{\max }$ as much as possible. However, the preference of a route in terms of battery power and queueing length is not well addressed. To guarantee the route preference, we adopt the following weighting function to help choose a route whose minimum and maximum serving capacity can be close while its preference can be fulfilled. In this work, the weighting function for the jth route perceived at node i is defined as

$$\begin{array}{cc}& f(P^{j,\min },Q^{j,\max })=\frac{{\left(P^{j,\min }-P_{\text{TH}}\right)}^{\mathrm{2}}}{{\left(\mathrm{1}-P_{\text{TH}}\right)}^{\mathrm{2}}}\frac{{\left(Q_{\text{TH}}-Q^{j,\max }\right)}^{\mathrm{2}}}{{\left(Q_{\text{TH}}-\mathrm{0}\right)}^{\mathrm{2}}},\end{array}$$

(2)

where $P_{\text{TH}}$ and $Q_{\text{TH}}$ are the preference of a route, $P^{j,\min }$ is the minimum battery power of the jth route, and $Q^{j,\max }$ is the maximum queueing length of the jth route. Also, $f_i(\mathrm{1,0})=\mathrm{1}$ , $f_i(P_{\text{TH}},Q_i)=\mathrm{0}$ , and $f_i(P_i,Q_{\text{TH}})=\mathrm{0}$ . This weighting function gives a route whose minimum battery power and maximum queueing length are far away from the respective thresholds, namely, $P_{\text{TH}}$ and $Q_{\text{TH}}$ . In this fashion, this proposed weighting function can help further differentiate routes in terms of their minimum battery power and the maximum queueing length.

With the proposed weighting function and the metric, we define the cost of the jth route at an intermediate node, say node i, as

$$\begin{array}{l}J(P^{j,\min },Q^{j,\max },{\mathrm{\Lambda }}_i)\\ \hspace{1em}\hspace{1em}=-f(P^{j,\min },Q^{j,\max })\left[\left(\frac{{\mathrm{\Lambda }}_{{\mathrm{\Psi }}_{ij}}^{\min }}{{\mathrm{\Lambda }}_{{\mathrm{\Psi }}_{ij}}^{\max }}\right){\exp }^{{\mathrm{\Lambda }}_{{\mathrm{\Psi }}_{ij}}^{\max }/{\tilde{\mathrm{\Lambda }}}_{{\mathrm{\Psi }}_i}^{\max }}\right].\end{array}$$

(3)

A route for a given communication pair is chosen if that route can yield the minimum cost. By incorporating this weighting function, we hope to find a route whose service ratio and minimum power can be as large as possible and the maximum queueing length can be as small as possible. To show the capability of the proposed route selection criterion in (3), we conduct a theoretical simulation of the proposed criterion along with other existing criterions such as Max-Min power [7, 10], Min-Max queueing length [13, 14], Max average power [9], and Min average queueing length [12]. The details of these criteria for comparison can be found in the respective reference.

In the simulation, we assume that the number of perceived routes at a node is $\mathrm{1}{\mathrm{0}}^{\mathrm{3}}$ . In this way, we can obtain the asymptotic behavior of those criteria. The remaining battery power and the queueing length of a node are randomly chosen between 0 and 1. Then we observe the behavior of the service ratio, the minimum remaining battery power, and the maximum queueing length of a chosen route under different route lengths. These results are shown in Figures 1(a)–1(c). Figures 1(a)–1(c) show that the proposed selection criterion can select a route to find a balance point among the service ratio, the minimum remaining battery power, and the maximum queueing length. Furthermore, from Figures 1(a)–1(c), though Max-Min power and Max average power have better minimum remaining battery power than the proposed criterion, their maximum queueing lengths are higher than the proposed criterion. Thus, the advantage of better minimum remaining battery power of these two criterions is compromised by having longer maximum queueing lengths. Longer maximum queueing length means more battery power will be spent on transmitting queued packets.

Figure 1

The comparison of the proposed cost function in (3) against other criteria.

Another example of the route chosen by the proposed criterion is illustrated in Figure 2. As shown in Figure 2, the proposed criterion chooses a route, S-5-6-D for the source node S and the destination node D. It is clear from this example that the proposed selection criterion can choose a route to avoid the congested area of the network.

Figure 2

An illustration of the route chosen by the proposed criterion.

3.2. Route Search Mechanism

The purpose of the proposed routing protocol aims at finding a route to have minimal service ratio, larger minimum remaining battery power, and smaller maximum queueing length as much as possible. To this end, the proposed cost function plays an essential role. As seen in the previous subsection, the proposed cost function is able to achieve these goals to some extent. Next, we would like to describe the proposed routing protocol, which is comprised of the route search mechanism and the route maintenance mechanism. We start with the route search mechanism. It is worthwhile to mention at this point that the proposed route search mechanism is based on AODV [21] with modifications. The way to handle the creation of reverse link and forward link and route reply is the same as AODV [21].

Assume that node s would like to establish a link with node d. Node s sends a route request (RREQ) packet out to seek a route. Initially, this RREQ packet contains the IP address of node s, the destination IP address, the address of node d, source sequence number (SSN), the request transmission rate, the delay constraint, $W_{\text{TH}}$ , the constraint of minimum queueing size, $Q_{\text{TH}}$ , the constraint of the minimum remaining battery power, $P_{\text{TH}}$ , the time stamp, $T_{\text{RREQ}}$ , the current maximum serving capability, and the current minimum serving capacity. $T_{\text{RREQ}}$ records the time when node s generates its RREQ packets.

Upon receiving a new RREQ packet, node i starts a predefined waiting window to see if there are more RREQ packets with the same SSN, source, and destination. Further RREQ packets are dropped after the expiration of the waiting window. Once this waiting window expires, node i first checks whether it is able to participate in this route search by comparing its current remaining battery power and the queueing length against $P_{\text{TH}}$ and $Q_{\text{TH}}$ , respectively. If one or both constraints are violated, node i drops this RREQ packet. Otherwise, node i calculates its serving capacity ${\mathrm{\Lambda }}_i$ to see whether it can accommodate the traffic of node s. If either ${\mathrm{\Lambda }}_i=\mathrm{0}$ or ${\mathrm{\Lambda }}_i$ is smaller than the request transmission rate, node i simply ignores the route request of node s. If node i satisfies all these requirements, it computes the costs of all potential routes that it perceives during the waiting window for the same SSN, source, and destination and chooses the one with minimal cost. After this, it updates the current maximum serving capacity and the minimum serving capacity and broadcasts the RREQ packet with minimal cost. Once the RREQ packet is sent, node i creates a reverse link towards its upstream node of the sent RREQ packet and starts a RREQ timer same as AODV [21]. If the route reply is not received before the expiration of the RREQ timer, node i neglects this route request from node s.

When the route request packets arrive at node d, same as node i, it begins a predefined waiting window to collect as many route requests as possible. Node d will find the costs of all routes arriving during this waiting window and choose the one with minimal cost. Once the route with minimal cost is chosen, node d will reply the route request from node s along the chosen route. Upon receiving the route reply from node d, each node along this route allocates the resource requested by node s. When node s gets the route reply from node d, these two nodes can start to communicate.

3.3. Route Maintenance Mechanism

The chosen route could fail to function normally either when one or more nodes are out of function, when the communication channel is bad for transmission, or when they are unable to provide services due to lack of available battery power or available queue size. To deal with these three situations, we propose the following route maintenance mechanism shown below.

For the first situation, let node k be the node right before the first broken link along the route. Under this situation, node k on behalf of node s initiates a route search starting from itself to the destination node. The route maintenance packet generated by node k contains the address of node s, the destination address, the address of node k, the request transmission rate, delay requirement, current time stamp of node k minus the delay, ${\tau }_{sk}$ , from node s to k, the maximum and minimum serving capabilities set to the serving capability of node k, and the partial information of this route up to node k. Each node receiving this route maintenance packet treats this as an RREQ packet and functions accordingly. At the node d, when it receives the route maintenance packets from node k, it functions as in the route search stage but replies the information of the new chosen route to node k instead of node s. When node k obtains this reply, node k continues to forward the packets from node s.

At the same time, when the route initiated by node k is found, node d also initiates a notification packet back to the node s along the newly repaired route. The notification packet will collect the information of the maximum and minimum serving capacities, the minimum remaining battery, and the maximum queueing length when it traverses this route. When node s receives the notification from node d, it compares the minimum remaining battery power or the maximum queue length of this notification. If the minimum remaining battery power is smaller than the power threshold, $P_{\text{TH}}$ , or the maximum queue length is greater than the queueing threshold, $Q_{\text{TH}}$ , the node s initiates a new route search. Otherwise, it can decide to adopt this new route or to initiate a new route search according to a probabilistic function. The larger value of the probabilistic function means that the chance to adopt this new route would be higher. If node s decides to initiate a new route search, it generates a new RREQ packet with new SSN to discover a new route.

For the second situation, also let node k be the node right before the link with bad channel condition along the route. It is known that wireless fading channel is time-varying [25, 26]. Thus, when a channel is in bad condition, with high chance, it would return to the good condition after some time duration. Even when the channel is in bad condition, the reliable communication is still possible by giving the packet more protection at the expense of reduction in transmission rate. Therefore, in this situation, the route cannot be taken as a broken route completely. The proposed route maintenance mechanism under this situation is as follows. When $N_{\mathrm{1}}$ consecutive NAKs for the same packet are received from the next hop, node k perceives the channel is bad in all likelihood. When this happens, node k takes the following actions.

• (i)

Node k chooses to reduce the code rate of the channel coding to a lower value and sends the same packet again. It is possible that the original packet will be divided into smaller packets due to the change of the code rate. If a NAK is received again, node k reduces the code rate further.

(ii)

If $N_{\mathrm{2}}$ consecutive ACKs for a series of packets are received after the reduction of code rate, node k increases the code rates until the normal code rate.

(iii)

If $N_{\mathrm{3}}$ consecutive NAKs for the same packet are received again after the reduction of code rate, node k initiates a route maintenance packet and takes action like in the first situation.

In this situation, $N_{\mathrm{1}}$ , $N_{\mathrm{2}}$ , and $N_{\mathrm{3}}$ are chosen to minimize the need of seeking a new route and avoid resource wasting as much as possible. $N_{\mathrm{1}}$ has to be chosen to minimize the false alarm of link failure without introducing excessive delay of a packet as much as possible. When a series of ACKs are received, this means that the channel state is getting better along the time. The code rate should be adjusted to normal code rate as soon as the channel state returns to the original channel state before the reduction of code rate. Thus, $N_{\mathrm{2}}$ has to do with the turnaround time of the fading channel. $N_{\mathrm{3}}$ is chosen to avoid excessive wait for the channel state to return to the original channel state before the reduction of code rate. Note that $N_{\mathrm{1}}$ , $N_{\mathrm{2}}$ , and $N_{\mathrm{3}}$ are design parameters.

For the third situation, when the new route is found, the destination initiates a notification packet back to the source periodically. It records the minimum remaining battery power and the maximum queueing length of the route. When the source receives the notification packet, if the minimum remaining battery power is smaller than $P_{\text{TH}}$ or the maximum queueing length is greater than $Q_{\text{TH}}$ , two actions are taken in this situation:

• (i)

lack of available battery power: when the source receives the notification of the lack of the available battery power. It has no choice left. The source initiates a new route search to seek a new route;

(ii)

lack of available queueing buffer: if the source node receives consecutive $N_{\mathrm{4}}$ notifications of the lack of queueing buffer, the source initiates a new route search to seek a new route. It is possible that a node originally with insufficient queueing buffer can digest the queued packets timely and its queueing length can meet the constraints once again. Spending time waiting for that to happen costs less than initiating a new round of route discovery. Note that $N_{\mathrm{4}}$ is the system parameter such that the impact of lack of available queueing size on the system can be minimized as much as possible.

4. Simulation Results

4.1. Simulation Setup

Our simulation is evaluated using QualNet 4.5 simulator. Simulations are running over a 1000 m × 1000 m area. The number of mobile nodes is 150. 30 topologies of the network are randomly generated. For each topology, the initial battery power and queueing length of a node are randomly generated and the simulation results are the average over all realizations. The mobility model we use is the random waypoint model. The nodes in the networks are either static or moving at various velocities (1 m/s, 5 m/s, and 20 m/s). There are 25 CBR sessions for each topology and the data rates are 2, 1, and 0.5 packets/second, which correspond to high load, medium load, and low load, respectively. In the simulation, each packet size is 512 bytes. FIFO queue is adopted, the maximum queue size of a node is 3000 bytes, and the queueing model is assumed to be an M/M/1/k. In the simulation, IEEE 802.11b is utilized with rate of 2 Mbps. The transmission power is 15 mW and the radio range is 250 m. In addition, the battery model is a linear model. The power consumption is the duration of the packet transmission (or the reception) times the power of transmission (or the reception). In addition, the lifetime in this work is defined as the n-of-n lifetime, which is the time when the first node dies [27].

The power-aware routing protocols to be compared against the proposed one are PAR-AODV [9], LPR-AODV [8], and PSR-AODV [7] routing protocols. The queueing-aware routing protocols to be compared against the proposed one are AODVM [13], WLBR [12], and QoS-AODV [14]. In addition, we also compare the proposed protocol with three extreme protocols. One aims at finding a route whose maximum remaining battery power is the largest among all the maximum remaining powers of all perceived routes at the intermediate nodes and the destination and it is called max battery power. The other aims at finding a route whose minimum queueing length is the smallest among all the minimum queueing lengths of all perceived routes at the intermediate nodes and the destination and it is called min queueing length. Another one is to find a route whose metric is the largest among all the maximum remaining powers of all perceived routes at the intermediate nodes and the destination and is called max metric. These three protocols serve as the benchmarks to see how good a newly route is in terms of remaining battery power, queueing length, and service ratio, respectively.

4.2. Simulation Results of Route Discovery Only

In this subsection, we will focus on the comparison of the battery power and serving capacity of a newly discovered route among the proposed and other existing protocols under the condition that the network size is fixed to 1000 m × 1000 m. First, we look at the maximum, minimum, and average battery power of a newly discovered route, which are shown in Figures 3(a), 3(b), and 3(c), respectively. The proposed protocol is able to find a route which has the largest minimum battery power, the average battery power, and the good maximum battery power among all protocols. The proposed protocol has comparable performance to max battery power in terms of the maximum battery power. However, the minimum battery power of the route found by max battery power is much worse than the proposed protocol.

Figure 3

Comparison of the maximum, minimum, and average battery power.

Next, let us turn to the serving capacity. We will compare the maximum and minimum serving capacity and the service ratio. The results are shown in Figure 4. As illustrated in Figure 4, all the protocols have similar maximum serving capacity. However, since the proposed protocol has the largest minimum serving capacity, the service ratio of the proposed protocol is the best among all the protocols. This means that the proposed protocol is capable of discovering a route whose serving capacity is more consistent. The consistency in serving capacity of the chosen route helps distribute the traffic load of the network more evenly. The last two things we would like to show are the comparison of the hop count and initial delay of a newly discovery route. Figure 5 illustrates the comparison of the hop count of a newly discovery route among all protocols. This figure shows the proposed protocol is able to find a route, which yields the smallest hop count among all protocols. Meanwhile, in Figure 6, we can see that the route found by the proposed protocol has the shortest initial delay. The reason for this is that the proposed protocol can find a route smallest hop count, which compensates the negative effect of the delayed broadcast at nodes during the phase of route discovery.

Figure 4

Comparison of the maximum and minimum serving capacity and service ratio.

Figure 5

Comparison of average hop count of a newly discovery route.

Figure 6

Comparison of average initial delay of a newly discovery route.

4.3. Simulation Results of Overall Proposed Protocol: AWGN Channel

Figure 7 shows the simulation results under the high traffic loading under AWGN channel. The results of average queueing length of all protocols are shown in Figure 7(a). The proposed protocol enjoys the shortest average queueing length. However, as shown in Figure 7(e), the shorter average queueing length of the proposed protocol does not necessarily imply that the proposed protocol will have the best end-to-end delay. The proposed protocol has the best end-to-end delay only when the moving speed of node is high. When the moving speed is low, the proposed protocol is worse than AODV, WLBR, and QoS-AODV. The comparison of lifetime among all protocols is given in Figure 7(b). The proposed protocol has the longest lifetime among all protocols. However, the lifetimes of the rest of the protocols are similar. This might be due to the fact that the metrics adopted in these protocols favor some certain nodes and, thus, create unwanted hot spots at these nodes. Consequently, these nodes quickly run out of their battery power, which results in comparable lifetime of these protocols. Next, we will look at the delivery ratio of these protocols presented in Figure 7(c). Due to the high traffic load, the delivery ratio of all protocols is low as expected. For most protocols, the delivery ratio is lower than 0.18, but for the proposed protocol the delivery ratio is about 0.22, which is relatively higher than others. Even though the proposed protocol has many advantages over other protocols, the main disadvantage of the proposed protocol is the higher overhead as shown in Figure 7(d).

Figure 7

High-rate case under AWGN channel.

Figures 8 and 9 show the performance under the medium traffic loading and low traffic loading, respectively. Because the traffic rate decreases, the average queueing length of medium and lower traffic loading decrease as shown in Figures 8(a) and 9(a) and the delivery ratios in Figures 8(c) and 9(c) increase. The proposed protocol has comparable low end-to-end delay as shown in Figures 8(e) and 9(e).

Figure 8

Medium-rate case under AWGN channel.

Figure 9

Low-rate case under AWGN channel.

The total number of RREQ messages of our proposed protocol for all traffic loadings are more than others as shown in Figures 7(d), 8(d), and 9(d). In the high loading scenario, the number of RREQ messages of our proposed protocol is about 1.4 times more than other protocols. In the medium and the low traffic loading scenario, the number of RREQ messages of our protocol is about 1.2 times more than other protocols. This is because the proposed protocol has several mechanisms of handling the link failure and the lack of resource. When the queueing length is near full or the battery power of a node is going to be exhausted soon, the proposed protocol takes action to perform the local route maintenance or reroute to relieve the loading of busy nodes. As the results, the number of overheads in the proposed protocol is more than other protocols, especially in the high traffic loading scenario.

Another thing we should note is why queueing-aware routing protocol does not have good queueing performance in the high traffic loading scenario. The main reason behind this is that the service capacity is not taken into account. The selected route may not be able to support additional traffic. This would cause the queue accumulation. Those routing protocols taking only the battery power into consideration also have the similar problem. As we can see in Figure 7(b), the lifetime of power-aware routing protocols in high loading is a little better than AODV and queueing-aware protocols. But when the traffic loading decreases, the lifetime of power-aware protocols is worse than AODV and queueing-aware protocols. That proves that taking only the remaining battery power into consideration cannot help in prolonging the network lifetime.

4.4. Simulation Results of Overall Proposed Protocol: Fading Channel

We also simulate the proposed protocols and the other existing protocols under fading channel to see how the fading channel variation affects the performance of these protocols. It is clear that the performance of all the protocols under fading channel is worse than that under nonfading channel.

The simulation results of queueing size under fading channel are shown in Figures 10(a), 11(a), and 12(a) for high-rate, medium-rate, and low-rate cases, respectively. For the proposed protocol, the average queueing length is 0.3, 0.22, and 0.12 for high-rate, medium-rate, and low-rate cases, respectively. From these three figures, we can see that the proposed protocol outperforms other existing protocols in the case of fading channel.

Figure 10

High-rate case under fading channel.

Figure 11

Medium-rate case under fading channel.

Figure 12

Low-rate case under fading channel.

Figures 10(e), 11(e), and 12(e) show the end-to-end delay in high-rate, medium-rate, and low-rate cases, respectively. In both high-rate and medium-rate cases, the proposed protocol has the smallest end-to-end delay among all the protocols. However, when being in the low-rate case, the performance of the end-to-end delay of the proposed protocol is comparable to other protocols and is slightly better than others when the mobility is high.

The results of the delivery ratio are shown in Figures 10(c), 11(c), and 12(c) for the high-rate, medium-rate and low-rate cases, respectively. The proposed protocol has the highest delivery ratio in all three cases. Comparing with the situation when the channel is AWGN, we find that the delivery ratio under the fading environment is much lower than that under the AWGN channel. From the above simulation results, it is clear that the data forwarding under the fading channel is harder than that under nonfading channel. A packet stays longer in the queue of a node and takes more time to reach the destination due to the increased number of retransmission under the fading channel. For the proposed protocol, we have an adaptive retransmission mechanism to overcome the channel variation due to fading. The results show the effectiveness of the proposed mechanism, which explains why the proposed protocol has better performance in the fading channel.

The lifetimes under the fading channel are shown in Figures 10(b), 11(b), and 12(b) for high-rate, medium-rate, and low-rate cases, respectively. As the rate increases, the lifetime under the same setting becomes smaller. Compared with the results under AWGN channel, the performance of lifetime of the proposed protocol is degraded. This is due to the fact that more energy is spent in the retransmission, which in turn reduces the lifetime of the network. However, the proposed protocol still has the best lifetime performance among all the protocols.

The fading channel increases the chance of the link failure. As a result, the overhead grows under fading channel. In Figures 10(d), 11(d), and 12(d), we find that numbers of RREQ messages under the fading channel in all cases are more than those under the nonfading channel.

5. Conclusions

In this work, we proposed a simple and effective routing protocol with a new route selection criterion. The adopted route selection criterion aims at finding a balance among the remaining battery power, the queueing length, and the service capacity. As we can see from the simulation results, by making use of the proposed routing protocol, the network lifetime can be further extended, the delivery ratio is improved, the average queueing length can be reduced, and the end-to-end delay is greatly improved especially under the fading channel.