Abstract: The study on the strategy of saving energy and protecting lower energy nodes is attracting more and more attention, because energy resource is one of the most important resources in ad hoc networks where, terminals are always supplied with limited battery. In this study, a novel energy-based local-maintenance protocol EBLM is introduced. In the routing discovery mechanism, relevant algorithm is adopted according to the different levels of node's remaining battery. This hybrid routing protocol considers not only power conservation, but also protecting the nodes with scarce battery. Furthermore, it is effective for load balance on a certain extent. On the other hand, a large reduction of substitute routing discovery time is achieved because of remaining energy awareness and warning strategy in the routing maintenance. Compared with AODV and CMMBCR protocol in various configurations of environment, simulation results showed that this routing protocol prolongs the lifetime and releases the traffic load of the overused nodes effectively.
INTRODUCTION
Mobile ad hoc network (MANET) which is an autonomous system of mobile terminals connected by wireless links becomes more and more concerned. Ad hoc network is a non-central, self-organized, multi-hop network. Dynamic topology, unstable links and limited energy capacity are features of ad hoc network. It is important that packets are transmitted successfully and quickly to the destination through the forwarding nodes. Therefore, efficient routing protocols are focused on all the time. Widely used protocols, such as DSR, AODV routing protocol, have strategy of routing chosen based on shortest path, namely, the least hops routing (Sesay et al., 2004). These protocols make packets sent along the path which includes as fewer as possible forwarding nodes, but not considers that some limited resources will be exhausted quickly. However, straightly adopting the shortest path may cause the resources overused, such as energy and bandwidth. Furthermore, routing discovery based on this strategy can easily cause that traffic is transferred through some nodes frequently. And, because most terminals in ad hoc network are supplied with the limited batteries, the energy of these nodes may be exhausted quickly and some nodes with little energy will be partitioned from the network. As a result, the congestion is added and lifetime in ad hoc network will bring down sharply at the same time. Especially, for some joint nodes, they should not be used frequently as the forwarding nodes. Otherwise, it will be fatal for the network because of energy of these nodes consumed too quickly.
In order to solve the problem above, protocols based on power-aware and energy consumption are studied in recent years instead of that with only hop-count algorithm. On the one hand, energy is saved through power control and node sleep mechanism in MAC layer; on the other hand, activity-based protocols are adopted in network layer which address the issue of power and energy as it relates to network activity (Jiageng et al., 2005; Meng et al., 2008; Dan-Yang et al., 2009). Nirisha (2007) study is based on the number of neighbors and their battery reserves in the course of routing discovery. In Routing decision is based on a load balancing approach and the nodes which have a tendency to die out very soon are avoided to use during the routing discovery of this protocol (Mohammed et al., 2005). E-TORA (Yu et al., 2007) selects routing according to hop count and residual energy of nodes that is, the nodes that have more energy have more probability to be chosen. LBAR (Nayak and Pradhan, 2004) defines a new routing metric known as the degree of nodal activity which represented the number of active paths passing through a mobile node. It assumes that the greater the value of activity is, the more traffic passing through a node will be LDAR. Zhang et al. (2007) proposes leisure degree which represents the capability of a node to accommodate more traffic. But, both of them above do not consider the remaining battery energy of each node. In these methods need the global information of the whole network and the routing decision is made at each node by using only local neighborhood information (Sanchez and Ruiz, 2006). Commonly, performance of routing protocol based on location is better than that not based on location. However, routing protocol based on location has a lot of control overhead and needs extra GPS instrument. Furthermore, it will make the terminals more complicated and more limited by environment. But, most of the protocols are simplex strategy applied for routing discovery. In other words, a routing discovery is adopted all the time. Considered the changes of the links and mobile nodes and so on, an energy-aware routing metric may only be appropriate a period of communication, the performance in other periods may get worse. CMMBCR (Qin et al., 2007) is a hybrid routing protocol defined a threshold. This protocol considers between the total energy consumption and residual energy of nodes, but it does not balance the traffic load and may cause more end to end delay because of chosen more forward nodes.
A new routing protocol EBLM in which energy consumption is considered is presented in this study. According to the aware of energy consumed and remained of the nodes in the network, the right path is chosen for packets transmitting. This protocol uses the ratio of remaining energy capacity as the cost metric, which means the fairness of energy consumption in the whole network. In the different levels of the remaining energy of the nodes, different energy related routing metrics are applied. The whole energy of a node is divided into three levels by two thresholds. The unit link cost and the whole link cost are considered in these three levels. By using this strategy, congestion will be reduced and the network lifetime will be prolonged effectively. In the routing maintenance, the local nodes can utilize the messages of remaining energy to keep the connection of link.
ENERGY-BASED LOCAL-MAINTENANCE ROUTING PROTOCOL
Before we introduce the routing protocol, it is necessary to define two models.
Energy consumption model: In the free space, energy consumption in the course of transmission corresponds Eq. 1 as follows:
| (1) |
Where n is integer between 2 and 4. In this paper, n = 2 k is constant and Eamp denotes the energy consumption when the inter amplifier transmits a unit. While, transmitting a k-bit packet the energy consumption is defined in Eq. 2 and that of receiving is in Eq. 3. Eelec is energy consumption of node's inter circuit in the course of transmission and receiving:
| (2) |
| (3) |
So, to a pair of communication ends, the whole cost of energy for transmission k-bit packet is as follows:
| (4) |
where, Ei is initial energy of node i. Er is energy remained of node i. Ec is energy consumed of node i. Ep is energy remained ratio of node i. We defined energy remained ratio of node i is expressed in the following formula:
| (5) |
The remaining energy Er of node i above is given as:
| (6) |
When, a path is chosen from source to the destination, it is necessary to through several forwarding nodes. The whole cost of the nodes belonging to the path is given as follows. M is the total number of nodes in the path:
| (7) |
In this study, we adopted energy remained percents Ep as the available value of the nodes, which instead of absolute value as the available value used in CMMBCR and some of other energy-aware protocols. Initial energy of terminal is different from each other. If remaining energy of some nodes in the network is much bigger than others, sum of the remaining energy is mainly related to the nodes with bigger energy and smaller ones are ignored. To avoiding this, by getting the result of Ep, namely doing normalization to remain energy of the nodes in the path (excluding weights of the nodes), the status of remaining energy of nodes are equalized. In addition, percentage of remain energy Ep, rather than Er, can show the state of the traffic load in a period.
If some nodes in the path have lower Ep, the path including these nodes should not be chosen in priority. This condition has little effect on the sum of Ep, but has much effect on the product of Ep, because the product will become very small. Therefore, this kind of path will have lower priority in the candidate paths and protect lower remaining energy nodes on a certain extent.
To the whole network, the forwarding nodes with heavy traffic load consume more energy. Therefore, the quantity of remaining energy means the degree of using this node. The probability of congestion is reduced much on account of using the nodes with more remaining energy as the forwarding nodes.
Lifetime model: Consider a directed graph G(N, L), where N is the set of all nodes and L is the set of all directed links (i, j). Let, Si be the set of nodes that can be reached by node i with certain power level in its dynamic range. Let. Ei be the initial energy of node i and Er be the remained energy of node i. The transmission energy required by node i to transmit one bit data to its neighbor nodes is denoted by Etx (1,d) and the received energy required by node i is Erx (Eq. 1). Energy consumption of node i with transmission k-bit packet and receiving m-bit packet is shown as:
| (8) |
The time when Ewi equals to Ei is defined as the lifetime of node i denoted by Ti. Thus, the network lifetime is denoted by:
| (9) |
We can define the network lifetime with another method. Ti=T1,T2,...,TN, T1<T2<... <TN. Thus, the network lifetime Tnek is as follows:
| (10) |
Routing discovery: For the network with enough remaining energy, in another word, at the beginning of network construction or when a new node is connected into, more attention should be paid to the whole cost of a link, because it presents the state of traffic load and energy balance. So, it is chosen as the routing discovery metric. After a period of time, energy consumption of the nodes is becoming more and the energy remained is limited. The energy of nodes becomes various. At this time, we should focus on unit cost to protect nodes with lower energy remained. As a result, the lifetime of the node is prolonged and network partitioning is prevented. When a node has little energy remained, warning to other nodes is necessary and at the same time, we should not let it be the forwarding node as if as possible. According to the analysis above, two thresholds r1 and r2 are set which divide the energy into three levels and have corresponding routing metric, respectively. r1 is set to be 50% and r2 is 10% in this study. So, based on energy aware and level distribution routing rc should satisfy the following formula.
| (11) |
| (12) |
| (13) |
If Er>r1, namely energy of each node is abundant, the path with the maximum Ecw is preferred as the rule for the source node choosing the route for packets transferring. If r1>Er>r2, namely there are some nodes that consumed much energy, the path with the minimum remaining energy is chosen as the optimization. If r2>Er, the path is protected for use.
Course of routing request: When, a node requires to transmit packets, its routing table will be checked for the available path to the destination. If there is not any available routing in the table, the routing discovery course will be started up. The RREQ is sent to the neighbors from the source. The RREQ will carry the Source ID, which means source sequence number, Destination ID, Sequence number, Ecw and Er, as is shown in Fig. 1.
When the forwarding node receives the RREQ, its routing table will be checked for the available path to the destination. If there is available path, it will give a RREP with the right path to the source along the RREQ path. If not, Er and Ecw value in the RREQ will be calculated and updated by the forwarding node i as follows. The new RREQ is transmitted until they reach the destination. Before this, the sequence number will be check for avoiding the loop path.
| (14) |
| (15) |
| (16) |
Course of routing reply: Routing reply packet RREP is sent by the intermediate node which has valid routing to the destination when received the RREQ, or by the destination node.
| Fig. 1: | Format of RREQ |
| Fig. 2: | The course of warning node’s link maintenance |
When the destination node receives the RREQ, it will start a timer to delay the time T for collecting the corresponding routing. Among the valid routing, the rest energy Er is compared with threshold r1 and r2 and then, the right routing according to Eq. 11-13 is chosen according to the metric above and sent to the source in the RREP.
Course of routing maintenance: Because the movement of the nodes, the changing channel or exhausting of the terminal energy can cause the broken link, the routing maintenance is necessary. When a node detects the broken links, it will inform the upper node through the routing error (RERR) packet. It is adopted that the strategy of energy awareness and protecting of lower energy remained in the routing discovery, so we can get the information of the node's rest energy. According to this, we can inform other nodes in this link and discover other right routing ahead. It is shown in Fig. 2 that the course of how a danger node warms the situation to the neighbor and a new path is built up quickly with the local maintenance. It is not necessary to inform the source to perform a new routing discovery in this course.
It is a normal link ABCDE to transmit packets from A to E, as is shown in Fig. 2a-d. The rest energy of node D is lower than the threshold, so it starts the local maintenance strategy to inform other nodes. It includes the ID of node C and E. The nodes F and G receive this message and check their own energy remained and whether there is valid routing to get both of them. The node G is up to the mustard. So, it will inform the nodes C and D that it could be the forwarding node. If the link is built up successfully, the packets will be transmitted along the new link ABCGE.
RESULTS AND DISCUSSION
All the results are computed on the NS-2 platform. AODV, CMMBCR and EBLM protocol are compared in the similar background.
| Table 1: | Simulation model parameter |
CMMBCR is one of efficient routing protocols on energy-aware. Level-distribute strategy is also adopted in this protocol, in other words, different routing discovery metric is chosen in different levels of battery energy, but it only considers the absolute value of available battery power of the bottleneck nodes. And the warning nodes do not be protected, which can cause the decrease of network lifetime. The performance of lifetime and end to end delay are compared in different rate of mobile nodes and traffic load. The simulation results show that the lifetime is prolonged effectively in EBLM, especially in the low speed of node’s mobility. The energy efficiency is improved with the new protocol because of local maintenance. Simulation model parameter are shown in Table 1.
The performance of network lifetime and end to end delay is shown in the following figures in different conditions. In this group of simulation, different mobility speed of the nodes and different traffic load are adopted. We want to compare with the influence by different scenarios. In the results, generally speaking, the performance of EBLM is more stable than that of these two.
Lifetime is prolonged with EBLM in different traffic load as shown in Fig. 3 and 4. Based on the scale of the network in simulation, network lifetime is defined as the average value of node's lifetime of the first 10 exhausted nodes and the node's lifetime of the first exhausted node, respectively.
| Fig. 3: | Lifetime in different traffic load (lifetime is defined as the average value of node’s lifetime of the first 10 exhausted nodes) |
| Fig. 4: | Lifetime in different traffic load (lifetime is defined as the node’s lifetime of the first exhausted node) |
| Fig. 5: | Lifetime in different mobility speed |
By adopting energy-distribute routing algorithm, for CMMBCR and EBLM, when there are some nodes with low remaining energy, it helps to extend the lifetime of low energy nodes by using strategy of preferentially choosing high energy node to release the traffic load of low energy nodes. And EBLM enhances protection for danger nodes and routing maintenance, in effect release the traffic load of danger nodes ulteriorly. The simulation results show that network lifetime of EBLM is better than that of CMMBCR and much better than that of AODV. In Fig. 3, the network lifetime tends to decrease with the traffic load increases from 2 to 20 packets sec-1. In this scenario, the maximum speed of mobile nodes is 1 m sec-1. The performance of AODV protocol is the worst in these three and CMMBCR
extends the lifetime a little. EBLM achieves a large extension through energy-based strategy. The result shows that the increase from 5.5% with the traffic load 2 packets sec-1 to 15% with the traffic load 20 packets sec-1, however, CMMBCR only has the values 1.1 and 7%. The same extension presents in Fig. 4. It shows that the proportion of increase gets larger than that of in Fig. 3. We can see that the effect is better when the time of battery of the first node exhausts is set to the network lifetime.
In Fig. 5-8, network lifetime is defined as the average value of node's lifetime of the first 10 exhausted nodes. Fig. 5 is on the condition of 2 packet sec-1 and shows the difference of network lifetime between the two protocols with nodes from immobile to higher speed 10 m sec-1. We can see that EBLM still has the longer lifetime almost in the whole course. With the increase of the mobility speed, the probability of overused decreases, so the network lifetime is prolonged without the energy balance in AODV. The difference of the three becomes smaller with the max speed of 10 m sec-1.
In Fig. 6, we can see that the energy consumption becomes more when the mobility speed is from 0 to 10 m sec-1. It is shown that disparity of these performance gets larger because EBLM considered the local maintenance strategy. Through this strategy, the packets can be transmitted to the destination with less retransmission which is presented by unstable topology.
The value in Fig. 7 is almost the same with the different traffic load from 2 to 20 packet sec-1. But, with the increase of mobility speed in Fig. 8, the performance of CMMBCR becomes worse than that of other two.
| Fig. 6: | Energy consumption of packet in different mobility speed |
| Fig. 7: | Delay in different traffic load |
| Fig. 8: | Delay in different mobility speed |
As is shown in Fig. 8, when there is heavy traffic load, if the mobility speed of the nodes are extremely slow, packets are always transferred trough some joint nodes. As a result, there will be congestion around those nodes and increase end to end delay. While, the mobility speed is increased, nodes in this area will change. Therefore, the packets which are transferred through the area will be distributed to different forwarding nodes. The congestion will be decreased and end to end delay will be cut down.
CONCLUSIONS
In ad hoc network, that some nodes are overused usually causes the battery exhausted quickly and the congestion of the nodes around. These all make the nodes and network lifetime reducing sharply. Furthermore, the network needs different strategy according to variety of network parameters. In this study, we studied the energy consumed model in ad hoc network and proposed an efficient routing protocol based on energy-aware and local maintenance. The protocol considered much about the different influence for different periods of energy remained and using the corresponding tactics. The joint nodes and overused nodes are protected in time, which avoids the nodes being partitioned from the network. On the other hand, through the calculation on energy consumption and remaining battery, this protocol achieves the estimate of the whole link. In the routing maintenance, by using energy warning mechanism, time of the substitute routing discovery is shortened. The simulation results show that EBLM protocol prolongs the lifetime more than CMMBCR and AODV in the whole network, especially for the static network and nodes with slower mobility. Because, strategy of energy balance is adopted, EBLM and CMMBCR have much superior performance than AODV in the aspect of load balance. In the high speed of mobility, the end to end delay in EBLM is shortened more effectively than in CMMBCR because of the strategy of local maintenance. In future work, we will consider the cross-layer design between MAC layer and network layer. The sleep and power control mechanism will be considered.
ACKNOWLEDGMENT
This study was supported by the National Basic Research Program (973 Program) under Grant No. 2009CB320400.