ENERGY EFFICIENT RELIABLE ROUTING CONSIDERING RESIDUAL ENERGY IN WIRELESS AD HOC NETWORKS
ABSTRACT
Two novel energy-aware routing algorithms to be proposed for wireless ad hoc networks, called reliable minimum energy cost routing (RMECR) and reliable minimum energy routing (RMER). RMECR addresses three important requirements of ad hoc networks: energy-efficiency, reliability, and prolonging network lifetime. It considers the energy consumption and the remaining battery energy of nodes as well as quality of links to find energy-efficient and reliable routes that increase the operational lifetime of the network. RMER, on the other hand, is an energy-efficient routing algorithm which finds routes minimizing the total energy required for end-to-end packet traversal. RMER and RMECR are proposed for networks in which either hop-by-hop or end-to-end retransmissions ensure reliability. Simulation studies show that RMECR is able to find energy-efficient and reliable routes similar to RMER, while also extending the operational lifetime of the network. This makes RMECR an elegant solution to increase energy-efficiency, reliability, and lifetime of wireless ad hoc networks. In the design of RMECR, we consider minute details such as energy consumed by processing elements of transceivers, limited number of retransmissions allowed per packet, packet sizes, and the impact of acknowledgment packets. This adds to the novelty of this work compared to the existing studies.
AIM
To devise a state-of-the-art energy-efficient routing algorithm for ad hoc networks called reliable minimum energy routing (RMER). The routes discovered by RMER minimize the consumed energy of the E2E packet traversal in the network. RMER does not consider the remaining battery energy of nodes, and will be used as a benchmark to evaluate energy-efficiency of the RMECR algorithm.
INTRODUCTION
Energy-efficient routing is an effective mechanism for reducing energy cost of data communication in wireless ad hoc networks. Generally, routes are discovered considering the energy consumed for end-to-end (E2E) packet traversal. Nevertheless, this should not result in finding less reliable routes or overusing a specific set of nodes in the network. Energy-efficient routing in ad hoc networks is neither complete nor efficient without the consideration of reliability of links and residual energy of nodes. Finding reliable routes can enhance quality of the service. Whereas, considering the residual energy of nodes in routing can avoid nodes from being overused and can eventually lead to an increase in the operational lifetime of the network.
ENERGY EFFICIENT WIRELESS ADHOC ROUTING
Wireless ad hoc networks have been deployed at an increasingly fast rate, and are expected to reshape. For example, wireless ad hoc networks combined with satellite data networks are able to provide global information delivery services to users in remote locations that could not be reached by traditional wired networks. Meanwhile, advances in hardware technology are constantly proliferating various wireless communication terminals to an exploding user population. In many scenarios, designs of wireless ad hoc network protocols are guided by two requirements – energy efficiency and resilience to packet losses. Efficiently handling losses in wireless environments, therefore, assumes central importance. Generally, routes are discovered considering the energy consumed for end-to-end (E2E) packet traversal. Nevertheless, this should not result in finding less reliable routes or overusing a specific set of nodes in the network. Energy-efficient routing in ad hoc networks is neither complete nor efficient without the consideration of reliability of links and residual energy of nodes.
EXISTING SYSTEM
Existing work on increasing energy-efficiency, reliability, and the lifetime of wireless ad hoc networks can broadly group them into three categories.
Ø Algorithms that consider the reliability of links to find more reliable routes.
Ø Algorithms that aim at finding energy-efficient routes
Ø Algorithms that try to prolong the network lifetime by finding routes consisting of nodes with a higher level of battery energy
Disadvantages
Algorithms that consider the reliability of links to find more reliable routes
Ø Although such routes may consume less energy since they require less number of retransmissions, they do not necessarily minimize the energy consumption for E2E packet traversal.
Ø A higher priority for reliability of routes may result in overusing some nodes.
Ø If there are some links more reliable than others, these links will frequently be used to forward packets. Nodes along these links will then fail quickly, since they have to forward many packets on behalf of other nodes.
Algorithms that aim at finding energy-efficient routes
Ø These algorithms do not consider the remaining battery energy of nodes to avoid overuse of nodes, even though some of them, namely, address energy-efficiency and reliability together.
Ø They do not consider the actual energy consumption of nodes to discover energy-efficient routes. They only consider the transmission power of nodes neglecting the energy consumed by processing elements of transmitters and receivers.
Ø This negatively affects energy-efficiency, reliability, and the operational lifetime of the network altogether.
Algorithms that try to prolong the network lifetime by finding routes consisting of nodes with a higher level of battery energy
Ø These algorithms, however, do not address the other two aspects, i.e., reliability and energy-efficiency.
Ø Discovered routes by these algorithms may neither be energy-efficient nor be reliable.
Ø This can increase the overall energy consumption in the network.
Ø The network lifetime may be reduced.
PROPOSED SYSTEM
Ø Propose a novel energy-aware routing algorithm, called reliable minimum energy cost routing (RMECR).
Ø RMECR finds energy efficient and reliable routes that increase the operational lifetime of the network.
Ø RMECR is proposed for networks with hop-by-hop (HBH) retransmissions providing link layer reliability, and networks with E2E retransmissions providing E2E reliability.
Ø HBH retransmission is supported by the medium access control (MAC) layer (more precisely the data link layer) to increase reliability of packet transmission over wireless links.
Advantages
Ø Considers energy efficiency, reliability, and prolonging the network lifetime in wireless ad hoc networks.
Ø The impact of limited number of transmission attempts on the energy cost of routes in HBH systems is considered.
Ø The impact of acknowledgment packets on energy cost of routes in both HBH and E2E systems is considered.
Ø Energy consumption of processing elements of transceivers is considered.
Ø RMECR extends the operational lifetime of the network
Ø It finds reliable routes
LITERATURE SUMMARY
Ø Shortest-path routing algorithm like Dijkstra’s algorithm which has been considered as an optimum solution for the problem of minimum energy routing in wireless ad hoc networks does not provide an optimal solution.
Ø It is a heuristic solution, and it can be an optimal solution only if the number of retransmissions on each link is large enough to ensure complete reliability of links.
Ø In E2E systems, the energy cost of packet transmission from a source node to an intermediate node depends on both upstream and downstream links of that intermediate node. Neglecting the impact of acknowledgement packets means that we disregard the impact of downstream links on the energy cost.
LITERATURE SURVEY
Minimum Energy Reliable Paths Using Unreliable Wireless Links
Qunfeng Dong, Department of Computer Sciences, University of WisconsinMadison; Suman Banerjee, Department of Computer Sciences, University of WisconsinMadison; Micah Adler, Department of Computer Science, University of Massachusetts at Amherst; Archan Misra, IBM T J Watson Research Center, 19 Skyline Drive, Hawthorne, NY
We address the problem of energy-efficient reliable wireless communication in the presence of unreliable or lossy wireless link layers in multi-hop wireless networks. Prior work [1] has provided an optimal energy efficient solution to this problem for the case where link layers implement perfect reliability. However, a more common scenario of a link layer that is not perfectly reliable, was left as an open problem. In this paper we first present two centralized algorithms, BAMER and GAMER, that optimally solve the minimum energy reliable communication problem in presence of unreliable links. Subsequently we present a distributed algorithm, DAMER, that approximates the performance of the centralized algorithm and leads to significant performance improvement over existing singlepath or multi-path based techniques.
Minimum Energy Paths for Reliable Communication in Multi-hop Wireless Networks
Suman Banerjee, Department of Computer Science, University of Maryland at College Park, College Park, MD 20742, USA; Archan Misra, IBM T J Watson Research Center, 19 Skyline Drive, Hawthorne, NY 10532, USA
Current algorithms for minimum-energy routing in wireless networks typically select minimum-cost multi-hop paths. In scenarios where the transmission power is fixed, each link has the same cost and the minimum-hop path is selected. In situations where the transmission power can be varied with the distance of the link, the link cost is higher for longer hops; the energy-aware routing algorithms select a path with a large number of small-distance hops. In this paper, we argue that such a formulation based solely on the energy spent in a single transmission is misleading —the proper metric should include the total energy (including that expended for any retransmissions necessary) spent in reliably delivering the packet to its final destination. We first study how link error rates affect this retransmission-aware metric, and how it leads to an efficient choice between a path with a large number of short-distance hops and another with a smaller number of large-distance hops. Such studies motivate the definition of a link cost that is a function of both the energy required for a single transmission attempt across the link and the link error rate. This cost function captures the cumulative energy expended in reliable data transfer, for both reliable and unreliable link layers. Finally, through detailed simulations, we show that our schemes can lead to upto 30-70% energy savings over best known current schemes, under realistic environments.
A HighThroughput Path Metric for MultiHop Wireless Routing
Douglas S. J. De Couto Daniel Aguayo John Bicket Robert Morris, M.I.T. Computer Science and Artificial Intelligence Laboratory
This paper presents the expected transmission count metric (ETX), which finds high-throughput paths on multi-hop wireless networks. ETX minimizes the expected total number of packet transmissions (including retransmissions) required to successfully deliver a packet to the ultimate destination. The ETX metric incorporates the effects of link loss ratios, asymmetry in the loss ratios between the two directions of each link, and interference among the successive links of a path. In contrast, the minimum hop-count metric chooses arbitrarily among the different paths of the same minimum length, regardless of the often large differences in throughput among those paths, and ignoring the possibility that a longer path might offer higher throughput.
This paper describes the design and implementation of ETX as a metric for the DSDV and DSR routing protocols, as well as modifications to DSDV and DSR which allow them to use ETX. Measurements taken from a 29- node 802.11b test-bed demonstrate the poor performance of minimum hopcount, illustrate the causes of that poor performance, and confirm that ETX improves performance. For long paths the throughput improvement is often a factor of two or more, suggesting that ETX will become more useful as networks grow larger and paths become longer.
Power-Aware Routing in Mobile Ad Hoc Networks
Suresh Singh and Mike Woo, Department of ECE, Oregon State University,Corvallis, OR 97331; C. S. Raghavendra, Aerospace Corporation, El Segundo, CA 90245
In this paper we present a case for using new power-aware metrics for determining routes in wireless ad hoc networks. We present five different metrics based on battery power consumption at nodes. We show that using these metrics in a shortest-cost routing algorithm reduces the cost/packet of routing packets by 5-30% over shortest-hop routing (this cost reduction is on top of a 40-70% reduction in energy con- sumption obtained by using PAMAS, our MAC layer pro- tocol). Furthermore, using these new metrics ensures that the mean time to node failure is increased significantly. An interesting property of using shortest-cost routing is that packet delays do not increase. Finally, we note that our new metrics can be used in most traditional routing protocols for ad hoc networks.
SYSTEM ARCHITECTURE
MODULES
Ø Network Model
Ø Energy Consumption for Packet Transmission
Ø Minimum Energy Cost Path
Ø Energy-Aware Reliable Routing
Network Model
Create topology of a wireless ad hoc networks by a graph G(V;E), where V and E are the set of nodes (vertices) and links (edges), respectively. Each node is assigned a unique integer identifier between 1 and N =|V|. Nodes are assumed to be battery powered. The remaining battery energy of node u ЄV is represented by Cu. If the battery energy of a node falls below a threshold Cth, the node is considered to be dead. Without loss of generality, we assume Cth =0. A link in the network is denoted by (u; v), in which u and v are sending and receiving nodes, respectively. The criterion for having a link from u to v is as follows: There could be a link from u to v, if the received signal strength by v is above a threshold. This threshold is usually specified in such a way that a targeted link error probability is satisfied.
Energy Consumption for Packet Transmission
The energy consumption for packet is given while activating the individual node in the network. This should be a constant value. Let x bit denotes the size of a packet transmitted over the physical link and E, the energy consumed by a transmitting node u to transmit a packet of length x [bit] to a receiving node v through the physical link (u; v). Let (u;v) (x)[J] denote the energy consumed by the receiving node v to receive and process the packet of length x [bit] transmitted by u. The energy consumed by nodes during packet transmission could be abstracted into two distinct parts. The first part represents the energy consumed by the transmission circuit excluding the power amplifier of the transmitter. The second part represents the energy consumed by the power amplifier to generate the required output power for data transmission over the air.
Minimum Energy Cost Path
The minimum energy cost path (MECP) between a source and a destination node is a path which minimizes the expected energy cost for E2E traversal of a packet between the two nodes in a multihop network. Since energy cost is an additive metric, it may seem that the Dijkstra’s shortest path routing algorithm could be used to find MECP in the HBH system. However, the Dijkstra’s shortest path routing algorithm is only a heuristic solution for finding MECP, but under some circumstances it could be the optimal solution.