AN IMPROVEMENT ON MAXIMUM RESIDUAL ENERGY ROUTING OF SENSOR NETWORKS Except where reference is made to the work of others, the work described in this thesis is my own or was done in collaboration with my advisory committee. This thesis does not include proprietary or classified information. _____________________________________ Lei Zhang Certificate of Approval: ________________________ ________________________ Cheryl D. Seals Alvin S. Lim, Chairman Assistant Professor Associate Professor Computer Science & Software Engineering Computer Science & Software Engineering ________________________ ________________________ Chung-Wei Lee Stephen L. McFarland Assistant Professor Acting Dean Computer Science & Software Engineering Graduate School AN IMPROVEMENT ON MAXIMUM RESIDUAL ENERGY ROUTING OF SENSOR NETWORKS Lei Zhang A Thesis Submitted to the Graduate Faculty of Auburn University in Partial Fulfillment of the Requirements for the Degree of Master of Science Auburn, Alabama August 8, 2005 iii AN IMPROVEMENT ON MAXIMUM RESIDUAL ENERGY ROUTING OF SENSOR NETWORKS Lei Zhang Permission is granted to Auburn University to make copies of this thesis at its discretion, upon request of individuals or institutions and at their expense. The author reserves all publication rights. ______________________________ Signature of Author ______________________________ Date of Graduation iv THESIS ABSTRACT AN IMPROVEMENT ON MAXIMUM RESIDUAL ENERGY ROUTING OF SENSOR NETWORKS Lei Zhang Master of Science, August 8, 2005 (B.S., Tianjin Institute of Technology, 1998) 124 Typed Pages Directed by Dr. Alvin S. Lim When Maximum Residual Energy Routing is adopted in actual battery-powered sensor networks, how to further improve the energy consumption in this protocol and prolong the system lifetime becomes a critical problem. In sensor networks where energy use maps directly affect the lifetime and overall performance, energy utilization is an important metric. In this study, we examine the Maximum Residual Energy Routing Protocol (MREP) and propose a new model for energy utilization in wireless network by considering the relationship between successful packet sending probability and node- distance. Based on this model, we develop a new method for improving MREP. Compared with previous model, the network energy usage is more uniform in the new model and the result is an increase of 20%~30% in system lifetime. v ACKNOWLEDGEMENTS The author would like to express the special appreciation to her advisor, Dr. Alvin Lim, professor, Department of Computer Science and Software Engineering, for his instruction, guidance, encouragement and patience in the completion of the research and thesis. Particularly, his suggestions, criticism and general exchange of ideas contributed much to this thesis. Thanks also due to the advisory committee members, Dr Lee and Dr. Seals, and the professors and staff members in the Department of Computer Science and Software Engineering at Auburn University for their kindness and help throughout these years. Finally, a sincere thanks to my husband Ju Wang, he gives the biggest support and encouragement to help the author finish all the research work. Also the author wants to thank her parents, who provide the inspiration and support during these years. vi Style manual or journal used: Guide to preparation and Submission of Thesis and Dissertation Computer software used: MS Office 2003 vii TABLE OF CONTENTS LIST OF TABLES . . . . . . . . . . . . . . . . . . . . . . . . . . . ix LIST OF FIGURES . . . . . . . . . . . . . . . . . . . . . . . . . . . x CHAPTER 1. INTRODUCTION. . . . . . . . . . . . . . . . . 1 1.1 Background and history . . . . . . . . . . . . . . . . . . . . . 1 1.2 Methodologies for Power Management in Different Layer. . . . . . . . 3 1.3 The Goal of This Study . . . . . . . . . . . . . . . . . . . . . . 8 1.4 The Structure of the Thesis . . . . . . . . . . . . . . . . . . . . 8 CHAPTER 2. MOTIVATIONS AND BASIC CONCEPTS . . . . . . . . . . . 11 2.1 Routing Decision Making . . . . . . . . . . . . . . . . . . . 11 2.2 Energy Efficiency Routing Methodologies. . . . . . . . . . . . . . 12 2.3 Other Methodologies . . . . . . . . . . . . . . . . . . . . . . 16 2.4 Methodology Analysis . . . . . . . . . . . . . . . . . . . . . 17 2.5 Transmission Distance & Reception Probability . . . . . . . . . . . 18 2.6 ExOR . . . . . . . . . . . . . . . . . . . . . . . . . . 21 CHAPTER 3.ENERGY EFFICIENT ROUTING ALGORITHMS . . . . . . . 30 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 30 viii 3.2 Different Algorithms . . . . . . . . . . . . . . . . . . . . . 30 3.3 Implementation of MREP . . . . . . . . . . . . . . . . . . . 33 3.4 Examples of MREP . . . . . . . . . . . . . . . . . . . . . . 36 CHAPTER 4. EXTENSION TO MREP . . . . . . . . . . . . . . . . . . . 40 4.1 Background Introduction . . . . . . . . . . . . . . . . . . . . 40 4.2 Introducing Reception Probability to Ad-hoc Network . . . . . . . . . 41 4.3 The Drawback of MTE . . . . . . . . . . . . . . . . . . . . . 42 4.4 Improvement . . . . . . . . . . . . . . . . . . . . . . . . . . 43 4.5 MREP Analysis . . . . . . . . . . . . . . . . . . . . . 44 4.6 Design & Mathematical Model . . . . . . . . . . . . . . . . . 44 4.7 MREPE & MREPC. . . . . . . . . . . . . . . . . . . . . . . 48 4.8 Summary. . . . . . . . . . . . . . . . . . . . . . . . . . . 50 CHAPTER 5. PERFORMANCE EVALUATION . . . . . . . . . . . . . . 57 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 57 5.2 Experiment Setting and Assumptions . . . . . . . . . . . . . . . 57 5.3 Performance Measurement . . . . . . . . . . . . . . . . . . . 58 5.4 Criteria of Evaluation . . . . . . . . . . . . . . . . . . . . 59 5.5 Comparing Simulated Annealing with MREP . . . . . . . . . . . 64 5.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . 64 CPARTER 6. CONCLUSIONS AND FUTURE WORK . . . . . . . . . . . 76 6.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . 76 6.2 Future work . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 REFERENCES . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 ix LIST OF TABLES Table 3.1 Performance comparisons of the three algorithms. . . . . . . . . . . . . 36 Table 5.1 Retransmission Energy Cost Rate under different network Density . . . . 66 LIST OF FIGURES Figure 1.1 The TinyDB power management API . . . . . . . . . . . . . . . . . 10 Figure 2.1 Contour of probability of packet reception from a central node at two different transmission power settings . . . . . . . . . . . . . . . . . . 25 Figure 2.2 Probability of packet reception over distance with different transmission power settings . . . . . . . . . . . . . . . . . . . . . . . . . . 26 Figure 2.3 Effect of the maximum transmission distance constrain on the average energy consumed per packet . . . . . . . . . . . . . . . . . . . . . 27 Figure 2.4 Effect of the maximum transmission distance constraint on lifetime metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 Figure 2.5 A simple network example, with various receiving probabilities . . . . . . 29 Figure 3.1 Modified Dijkstra?s algorithm . . . . . . . . . . . . . . . . . . . . 35 Figure 3.2 Example of routing network . . . . . . . . . . . . . . . . . . . . 37 Figure 3.3 An example graph with bandwidth costs on edges . . . . . . . . . . . . 38 Figure 3.4 A spanning tree output by the modified Dijkstra?s algorithm . . . . . . . 39 Figure 4.1 Relationship between d and p when 10 0 =Dm . . . . . . . . . . . . 52 Figure 4.2. An example network . . . . . . . . . . . . . . . . . . . . . . . . 53 Figure 4.3. An example showing how MREPE works (1) . . . . . . . . . . . . . 54 Figure 4.4. An example showing how MREPE works (2) . . . . . . . . . . . . . . 54 x xi Figure 4.5 An example shows the advantages of MREPE compared with MREP . . . . 55 Fig 5.1. Illustration of Uniform Traffic Fields . . . . . . . . . . . . . . . . . 67 Figure 5.2 System lifetime comparisons . . . . . . . . . . . . . . . . . . . 68 Figure 5.3 Residual Energy Level Comparisons . . . . . . . . . . . . . . . . 69 Figure 5.4 Average System Lifetime under Different Density . . . . . . . . . . 70 Figure 5.5 Average Remaining Energy under Different Density . . . . . . . . . 71 Figure 5.6 Retransmission Times with corresponding Number of Packets . . . . . 72 Figure 5.7 Percentage of packet sent . . . . . . . . . . . . . . . . . . . . . . 73 Fig 5.8 System Lifetime comparison with SA . . . . . . . . . . . . . . . . . 74 Fig 5.9 Residual Energy Level comparing with SA . . . . . . . . . . . . . . . 75 1 CHAPTER 1 INTRODUCTION 1.1 Background and history Sensor networks can enable ?smart environment? which can monitor ambient conditions such as temperature, movement, sound, light, location and others. Wireless sensor networks technology poses its unique design challenges. One important feature that distinguishes sensor networks from traditional distributed systems is their need for energy efficiency. Many nodes in the emerging sensor systems will have finite energy reserves from a battery. The scale of a sensor network?s deployment will make recharging these energy reserves impossible. Although energy efficiency can be improved at various layers of the communication protocol stack, most research has focused on hardware-related energy efficiency aspects of wireless communications. Low- power electronics, power-down modes, and energy efficient modulation are examples of work in this category. However, due to fundamental physical limitations, progress towards further energy efficiency is expected to be achieved in different layers. The energy efficiency issues can be traced back to the portable computer energy consumptions. There are a few software strategies, which take advantage of designed low-power hardware have been proposed by Lorch et al. (1997) With the mode selection under software control, many architectural features have both high performance and low power modes. The software controls are grouped as follows: transition, load- 2 change, and adaptation. The transition problem is deciding when to switch to low-power, reduced-functionality modes by getting to know the mode characteristics and future functionality requirements of each component. The load change problem is determining how to modify the load on a component so that it can make further use of its low-power modes. This method is achieved by changing the configuration (such as designing software that reduces paging activity) or usage of the cache. The adaptation problem is how to create software that allows components to be used in novel, power-saving ways. Since each component has its energy consumption and performance characteristic, it is wise to treat each component individually. However, in some work the devices were dealt collectively (Rpllins et al., 2002). The strategy is to view a collection of devices as a single unit and managing data available across them using power-aware schemes. This increases the amount of time that useful data remains available, even in the face of a power loss on a subset of the devices. Migrate content from devices that are in danger of energy dying. One big problem of the scheme is that when there is big amount of data to be moved, which the user isn?t interested in accessing. Allowing the user to tag data?s characteristics can solve this. Generally speaking, it is hard to tell which method is more energy efficient: treating the pervasive devices individually or corporately. This should depend on the each application that runs on it. 3 1.2 Methodologies for Power Management In Different Layers 1.2.1 MAC Layer MAC layer plays lots of roles to deal with the energy control issues. There are so many kinds of MAC layer protocols, such as 802.11,EC-MAC, PRMA, MDR-TDMA and DQRUMA in Cheng et al. (1998). The protocols those aim at reducing the number of contentions perform better from an energy consumption perspective than others?. Because through the mathematic analysis, it is obvious that retransmission is the greatest source of energy waste. Since the chief sources of energy consumption in the mobile unit considered for MAC related activities are the CPU, the transmitter, and the receiver. Mobile CPU usage may be reduced by relegating most of the high-complexity computation (related to media access) to the stationary network. Therefore, the focus of the work is on transceiver usage. The radio can operate in three modes: standby, receive, and transmit. In general, the radio consumes more power in the transmit mode than in the receive mode, and consumes least power in the standby mode. The objective of MAC protocol design should minimize energy consumption while maximize protocol performance. The protocols should be defined such that energy consumption due to the transceiver and CPU is low. The following are some principles that may be observed to conserve energy at the MAC level: o Collision should be eliminated as far as possible since it results in retransmissions, which leads to unnecessary energy consumption and also to possibly unbounded delays. 4 o In a typical wireless broadcast environment, the receiver has to be powered on all times resulting in significant energy consumption. One possible way to reduce receiver power-on time is to broadcast a data transmission schedule for each mobile. This will enable a mobile to be in standby mode except during its alloted slots. o In order to reduce turnaround, which leads to significant time and power spent, a mobile should be allocated contiguous slots for transmission and reception whenever possible. o In 802.11 standard, a mobile can conserve energy by switching to sleep mode. By transmitting beacon, the base station can keep in touch with the mobile hosts. Though this approach conserves energy at the mobile hosts, results in additional delays that affect quality of service. o The mobile should request larger chunks of bandwidth to reduce the reservation overhead leading to better bandwidth and energy consumption efficiency. o A centralized scheduling mechanism will be more energy efficient. Other issues in energy-efficient MAC protocol beside collision are discussed by Ye et al. (2002), which identify the major sources of energy waste as: overhearing, control packet overhead, and idle listening. S-MAC is the protocol, which is based on finding the ways to avoid the major sources of energy waste above. The design of the S-MAC follows similar procedures as 802.11 at the side of collision avoidance. It includes both virtual and physical carrier sense and RTS/CTS exchange. The scheme of S-MAC is to periodic listen and sleep. This reduces energy consumption by avoiding idle listening. The use of synchronization to form virtual 5 clusters of nodes on the same sleep schedule is to coordinate nodes and minimize additional latency. The use of in-channel signaling, which puts each node to sleep when its neighbor is transmitting to another node. This method avoids the overhearing problem. Applying message passing (divide the long message into small fragments and transmit them in a burst.) is to reduce application-perceived latency and control overhead. Per- node fragment-level fairness is reduced since sensor network nodes are often collaborating towards a single application. This protocol is not only shows its better energy conserving properties compared with IEEE 802.11,but also has the ability to make trade-offs between energy and latency according to traffic conditions. The collaborative relationship between the operating system and applications can be applied to energy aware adaptation for mobile applications. Odyssey in Flinn et al. (1999) can predict future energy demand for measurements of past usage. It must perform three tasks periodically. First, it must determine the residual energy available. Secondly, it must predict future energy demand. Third, based on these two pieces of information and the application specified fidelity level, it must decide if applications should change fidelity and notify them accordingly. Odyssey is conceptually part of the operating system, even though it is implemented in user space for simplicity. In this way, the applications can dynamically modify their behavior to conserve energy. When energy is plentiful, application behavior is in good fidelity, otherwise the behavior must be in energy conservation mode. It balances the tradeoff between the fidelity and energy usage. 1.2.2 Transport Layer Since wireless MAC layer protocols always incur additional overhead of delays due to power management, they cannot improve energy efficiency by taking advantage of 6 application-specific information. Kravets et al. (1998) designed a transport layer protocol which reducing the power usage by selectively choosing short periods of time to suspend communication and shut down the communication device. In this scheme, the mobile host is regarded as the maser and base station is regarded as the slave. Because this is a transport layer protocol for power control, which is controlled by the mobile host, it can offer power management interface to applications. So adaptive power management can be driven by the needs of applications. During the period of suspending of the mobile host, the base station has to queue all of the data waiting for transmission. Due to the limitation of base station?s buffer, amount of time in suspension is very significant. To get out of this problem, the design of the protocol gives lots of timing consideration, such as timeout period, sleep duration, all application strategy and independency of specific network card. This protocol still needs improvement. That is to develop techniques to estimate when there is queued data at the base station, so that reception delays can be reduced. 1.2.3 Cross-Layer A good example of cross-layer power management is given in TinyOS in Madden et al. (2002), which manages power management through the interaction of three elements (see Figure 1.1). First, each service can be stopped through a call to its StdControl.stop command; components in charge of hardware peripherals can then switch them to a low-power state. Second, the HPLPowerManagement component puts the processor into the lowest-power mode compatible with the current hardware state, which it discovers by examining the processor?s I/O pins and control registers. Third, the 7 TinyOS timer service can function with the processor mostly in the extremely low power power-save mode. TinyDB uses these features to support sensor network deployments that last for months. In this context, idle listening dominates energy consumption. Low-power listening reduces the cost of idle listening by increasing the cost of transmission. However, instead of low power listening, TinyDB uses communication scheduling. Using coarse-grained (millisecond) time synchronization, TinyDB motes coordinate to all turn on at the same time, sample data, forward it to the query root, and return to sleep. To further reduce the average power consumption of the network, low power listening can be combined with the periodic listening. Running both schemes simultaneously results in listening at reduced power for only a fraction of the time. But periodic listening may cause query failure when a query arrives within interval of two listening period. These techniques attempt to minimize the energy usage at all levels of system operation. Thus, in addition to minimizing energy usage, the system lifetime can be increased by modifying the task allotment according to the energy available at network nodes. Some examples of such techniques can be found in many works (such as Nabar et al. 2004; Biswas and Morris, 2004; Ganesan and Estin, 2001) for routing and data gathering. The first requirement for these techniques is to get the information about energy availability at the nodes. The remaining energy in a battery can be estimated from its discharge function and measured voltage supplied (Chang and Tassiulas, 1999). Additionally, Sankar and Liu (2004) proposed environmental energy harvesting framework (EEHF) toward energy harvesting to adaptively learn the energy properties of the environment and the renewal opportunity at each node through local measurements, 8 make the information available in a succinct form for use in energy aware task assignment such as load balancing, leader elections for clustering. This is a way to allocate task with the spatial-temporal characteristics of energy availability. Implementing energy harvesting in real networks is complex because the harvesting process itself cost energy too. Idling listening adopted in TinyOS is a good mechanism to save energy and manage the power efficiently. 1.3 The Goal of This Study Though there are different solutions in different layers for the energy efficiency problem in sensor networks, we focus our study on routing layer protocol design. Adopting energy efficiency as the metric to route packets in the network, we develop methods for improving the system lifetime by the means of balancing the energy utilization load. System lifetime is the time where valid packets are sent until the system is dead. In this study we identified energy usage imbalance as one of the major sources that impedes effective energy usage. Introducing novel mechanisms in order to eliminate this problem in energy efficient routing protocol design is the goal of this research work. 1.4 The Structure of the Thesis The thesis includes six chapters: Chapter 1: General introduction to energy-efficient protocols in different layers; Chapter 2: Discussion on related work on energy-efficient protocol design and the motivation of this study; Chapter 3: Introducing the mechanisms to solve the routing problem; 9 Chapter4: Problems with existing MREP and methods to improve it; Chapter5: Analysis of performance and results from our algorithms; Chapter6: Conclusions. Figure 1.1 The TinyDB power management API. The application calls StdControl.stop to halt the low-level hardware. HPLPowerManagement.nc sees changes to the hardware status registers, which causes it to put the CPU into a low-power sleep state 10 11 CHAPTER 2 MOTIVATIONS AND BASIC CONCEPTS There are many issues in sensor network routing, which guide our protocol design in this study, such as routing decision making, energy efficient routing methodologies, transmission distance and reception probability. In the following sections, we?ll discuss each of the issues in detail. 2.1. Routing Decision Making Usually routes are represented in a table that specifies the path of messages between two nodes. Setting routes for sensor data can be performed in a central node that knows the network topology, e.g. the gateway, or distributed among the sensors themselves. Both centralized and distributed routing requires maintenance of the routing table every time when the network topology changes. While distributed approaches are scalable for larger networks, updating routing tables and ensuring consistency among the local versions that the sensor nodes have consume significant computation and communication resources, thus limiting the portion of the already limited sensor?s energy that can be dedicated to serve the application. In addition, exchanging routing messages among the sensors will create excessive traffic that drains unnecessary energy since radio receivers on the sensors may overhear the routing message transmissions not destined to them. 12 Managing the routing decision centrally at the gateway can be seen as a logical extension to the gateway?s role, especially as all sensor readings have to be forwarded to the gateway for fusion and application-specific processing. Moreover, centralized routing is simple and fits the nature of the sensor networks. Since the sensor is committed to data processing and communication, it is advantageous to offload routing decision from the resource-constrained sensor nodes. In addition, since the gateway has a cluster-wide view of the network, the routing decisions should be more efficient than the decisions based on local views at the sensor level. Given that the gateway organizes the sensors in the cluster, it can combine the consideration for energy commitments to data processing, remaining sensor energy, sensor?s location, and acceptable latency in receiving the data in efficiently setting message routes. Based on the benefits above, we set the source node in our scenario as the gateway node, which makes the routing decision within the cluster. This is under the assumption that the sensor network has already been organized into clusters. To simplify the problem, our research focus is on energy efficient routing within a cluster. We?ll put the inter-cluster routing in the future work. 2.2 Energy Efficiency Routing Methodologies Traditionally, research work of energy efficiency routing in wireless networks always focus on multi-hop routing. There are mainly two types of multi-hop routing protocols. They are maximizing system lifetime and minimizing energy cost. 13 2.2.1 Maximizing System Lifetime The first methodology, such as in Madan et al (2004), is to maximize the time at which the first node drains out of its energy. The common aim of these protocols is to minimize the energy consumed per packet in order to deliver it to the destination more efficiently. A typical approach is to use a distributed shortest path algorithm in which the edge costs are related to the power required to transmit a packet between the two nodes involved. The problem with this technique is that nodes on the minimum-energy path quickly use up power, affecting the network connectivity when they fail. A rigorous formulation using linear programming has been presented by Chang and Tassiulas (1999) which attempted to capture the issue of power consumption more precisely. The idea is to route the packets in the maximization of the network lifetime. Heuristics algorithm was proposed to select routes in a distributed manner to maximize the network lifetime. However, these heuristics do not always lead to selection of routes that are globally optimal. So the behavior is arbitrarily bad in the worse case. Madan et al (2004) provides one solution to this by exploiting the separable nature of this problem using dual decomposition and distributed subgradient algorithms to compute the data rates between each pair of nodes. They developed a distributed algorithm to compute an information flow that maximizes the network lifetime by the means of interpreting the problem above as minimizing the maximum ratio of power consumption to energy supply at each node. Sankar & Liu (2004) formulate the problem as a maximum concurrent flow problem. All routing problems have analogous flow realizations, where the flow 14 represents the routes that packets take, and the demands represent the rate at which packets are generated by various nodes. This formulation allows one to apply the extensive literature of maxflow algorithms to problem of routing for maximum network lifetime. The algorithm finds an approximation to a feasible flow if one exits. The advantage of this algorithm compared with the previous work is that the approximation factor is guaranteed, which is a significant improvement over the heuristic algorithm previously proposed. 2.2.2. Minimizing Energy Cost The other methodolgy is to minimize the total energy consumption of the networks, such as Rodoplu & Meng (1999) and Li & Halpern (2001). These types of protocols try to maximize the total battery life of a wireless network by the means of minimizing the energy consumption of the entire network. In Rodoplu & Meng (1999), by using a very localized search, each node can eliminate the nodes in its relay regions from consideration and pick only those few links in its immediate neighborhood to be the only potential candidate. This is because the experiments show that power-efficient transmission can be achieved by each node when it considers only its immediate locality. After that, the cost metric distribution, which is the total power required for a node to reach destination node along a directed path is computed and compared. The node that require minimum energy is selected. In order to improve the protocol of Rodoplu & Meng (1999), Li & Halpern (2001) proposed the idea of subnetwork. In the subnetwork, there are fewer edges and less transmission energy consumption from the source node to the destination node than the original networks. Compared with protocol proposed by 15 Rodoplu & Meng (1999), protocol Li & Halpern (Aug.2001) shows its advantages of smaller network, lower link maintenance cost, achieve a significant saving in energy usage, and computational simplicity. Wattenhoferet & Li (2001) proposed a novel way of minimizing total energy consumption for wireless networks, which is called cone-based distributed topology control algorithm. The basic idea behind this is to vary the transmission power of each node according to its local decisions made by itself. Since this algorithm assumes that there is no GPS for each node. So each node makes local decisions about its transmission power and this decision collectively guarantee global connectivity. Specifically, based on the directional information, a node grows its transmission power until it finds a neighbor node in every direction. Through this way, network lifetime can be increased by reducing transmission power and network traffic interference. By choosing suitable parameters, an approximation scheme in which the power consumption of each route can be achieved arbitrarily close to optimal. Further research work has been done on this algorithm by Li & Halpern (2001), which introduces every cone of degree ? around each node. Taking the parameter of ?=5?/6 is a necessary and sufficient condition to guarantee that network connectivity is preserved. This is under the condition that a node, which transmits with the minimum power required to ensure that in every cone of degree ? around it, there will be some node that it can reach with the minimum power. 2.2.3 Improvement Still focusing on the power control from the routing decision point of view, Chang & Tassiulas (2000) separate the problem into two parts: single power level and 16 multiple power level. For the single level ones, the problem is reduced to maximum flow problem with node capacities and the algorithms converge to the optimal solution. While for the multiple level ones, the achievable lifetime is close to the optimal most of time. Here, the routing decision and the transmission energy level selection are intrinsically connected in the power-controlled ad-hoc network since the power level will be adjusted depending on the location of the next hop node. Chang & Tassiulas (1999) also proposed the shortcoming of the algorithms, which try to minimize the total energy consumed. It points out that if all of the traffic is routed through the minimum energy path from the source to the destination, the nodes in that path will use up their batteries quickly even though the other nodes still have plenty of energy. So, instead of trying to minimize the consumed energy, the performance objective of maximizing the time lifetime of the system has been considered. Under the assumption of a set of source and destination nodes, a class of flow augmentation algorithms and a flow redirection algorithm, which balance the energy consumption rates among the nodes in proportion to their energy reserves have been adapted in this approach. As much as 60% of system lifetime on average over the conventional minimum transmitted energy routing has been improved by the local and amenable distributed algorithm. 2.3 Other Methodologies Lots of research work has been done from the point of flow-based energy ? efficient routing algorithm. Gandham et al (2003), proposed an Integer Linear Program (ILP)-based method for routing in sensor networks. But this kind of ILP-based method does not guarantee integral routes. As it is not advisable to split the packets (due to 17 overhead), integral flow values are highly desirable. Some solution offered in Gandham et al (2003) was to round the non-integral flow values by using a sub-optimal rounding procedure. Moreover, this still cannot guarantee any bound on running time of the IL- based method. Further work has been done by Gandham et al (2003), which introduced a novel idea called Integral Flow-based Energy-Efficient Routing algorithm. Based on modeling the routing problem during a round as well-known polynomial-time solvable network flow problem, Gandham et al (2003) results in integral flow values and therefore the flow information can be used without any rounding in a routing protocol. There are two objectives of this algorithm, (1) minimizing the total energy spent in a round and (2) minimizing the maximum energy spent by any node in a round. For the consideration of routing all the data along a shortest path might potentially drain all the energy from upstream nodes, thus losing coverage in some regions of the network. In Gandham et al (2003), they mitigate this possibility by limiting the amount of energy each node can spend per round. 2.4 Methodology Analysis From the issue above, the conclusion is that maximizing system lifetime can be regarded as a better method of energy efficiency routing. To further optimize this methodology, distributing the energy cost uniformly is essential. So in this study, we start from the multi-hop routing, integrate the method of maximizing system lifetime, and make effort to distribute the energy usage as evenly as possible. 18 2.5 Transmission Distance & Reception Probability Younis et al (2002) introduces a new energy-aware routing protocol for wireless sensor networks that uses distance as a measurement for transmission energy consumption. The Figure 2.3 shows that as the maximum transmission distance constrain increases, the average energy consumed per packet increases. This is expected, as when the maximum transmission distance constraint increases, the network topology graph becomes denser and minimum number of hops routing algorithm chooses the long links to minimize number of hops. These long links leads to more transmission energy consumption per packet. The same effect is shown in Figure 2.4. As the maximum transmission distance constraint increases, fewer number of hops chosen by the minimum number of hops routing algorithm leading to decreased end-to-end delay. As the end-to- end delay is decreased, the throughput increases as more packets reach the gateway. As the average consumed per packet increases, the network lifetime parameters are decreased as shown in Figure 2.4 For low values for the maximum transmission distance constraint, the network topology graph is sparse and the length of the links is small leading to reduced average energy consumed per packet. However, the end-to-end delay is increased due to the increase of the number of relays between a sensor node and the gateway. From Figure 2.4 shown, see that a good value for the maximum transmission distance constraint should be between 200 and 400 meters to obtain good values for the performance metrics. 19 From a theoretical point of view, the protocol above provides powerful verification that the transmission distance plays important role in energy-aware routing and adjusting transmission distance wisely will have good results. Next, there is an experimental result about the role of transmission distance. The experiments of Ganesan et al (2001), attempt to quantitatively define and measure the effective communication radius at a given transmit power in a real setting and explore packet reception statistic over distance. There are also several important concepts proposed which are very helpful in designs. o Backward link is the link where the recipient of the flood is closer from the base station than the transmitter. From the routing protocol design point of view, loop effect should be removed due to the harmful influence of backward link. o Long link is significantly longer than expected at given transmit power level. This concept gives us the motivation in our scenario design, which is the extension of maximum transmission distance. o Connectivity radius is based on a packet reception threshold. The threshold is defined by the raw packet throughput in experiments. The good link is 65% receiving rate, while the bad link is one 25% receiving rate provided by the experiment result. There are a few facts that are proven in their experiments. null The distribution of packets reception rate over distance is quite non-uniform. See Fig 3.1 and Fig 3.2 for reference. 20 null Individual contours clearly exhibit directionality with propagation being better at some direction than others as shown in Fig 3.1 and Fig 3.2 null In Fig 3.1 and Fig 3.2, there is a relationship between the packet reception rate and transmission distance. Though packet reception falls off quite rapidly with distance, the plots have a heavy tail i.e. there is non-zero probability of receiving a packet at a long distance from the transmitter. The observations clearly indicate the presence of long-links, which result in greater propagation in some directions than others. null The receiving rate is lower than 100% even at short distances from the transmitter. The reason for this is that increased fading rate due to deployment on the ground and insufficient signal processing and forward error correction due to the limited computational and energy resources available. From both theoretical and experimental verification above, a conclusion can be drawn: There is strong relationship between the transmission distance and receiving rate, which becomes another important consideration in our protocol design. In the next sub- section, we will give an example of a design which combines the reception probability with transmission distance. 21 2.6 ExOR 2.6.1 Introduction Multi-hop wireless networks typically use routing techniques similar to those found in wired networks (Couto et al (2003), R.Draves et al (2003), D.B Johnson (1994), C.E.Perkins et al (1994)). A routing protocol chooses a path of nodes between the source and destination, and each packet is forwarded along the path through one node at a time. Proposed by the information theory community (Nabar et al (2004)), cooperative diversity schemes, suggest an alternate approach that may produce higher throughput. Cooperative diversity takes advantage of broadcast transmission to send information through multiple relays concurrently. Then, the destination chooses the best of many relayed signals, or combine information from multiple signals. Proposed by Biswas & Morris (2004) ExOR is an integrated routing and MAC technique that aims to realize some of the cooperative diversity on standard radio hardware such as 802.11. ExOR broadcasts each packet to multiple potential forwarders, choosing one of them only after knowing the nodes, which actually received the packets. Delaying forwarding decisions until after reception allows ExOR to try multiple long but radio lossy links concurrently, resulting in highly expected progress per transmission. Unlike cooperative diversity schemes, only a single ExOR node forwards each packet, making ExOR suitable for use with existing radios. 2.6.2 Properties of Multi-Hop Wireless Networks ExOR benefits from two properties of multi-hop wireless networks: the broadcast nature of the wireless medium, and links with high loss rates. Figure 2.5 shows 22 a simple network for purposes of illustration; suppose that node A wishes to route a packet to node D. Using conventional routing, and assuming the indicated delivery probabilities, the highest throughput route is A?B?C?D; this route minimizes the expected number of times that the packet will have to be re-sent to recover from loss. At a high level, ExOR benefits from the possibility that A?s transmissions might reach C or even D as well as (or instead of) B. From the example above, we can see that ExOR can be most effective when: 1) Every node has non-zero receiving probability to multiple other nodes, so that there is a choice of forwarders; 2) transmissions reach potential receivers with a wide range of receiving rates, so that packets occasionally travel a long way towards the ultimate destination. Another advantage of ExOR compared with traditional routing is that it depends on a gradual delivery probability fall-off; if there is a distance at which the probability abruptly drops from high to low, then conventional routing via a node just before that distance is the best strategy. The delivery probability depends on the interaction between modulation (and coding) and sources of error such as interference and multi-path fading. 2.6.3 ExOR Operation To help receivers agree with as little communication overhead as possible, ExOR operates on batches of packets. The source node includes a list of candidate forwarders in each packet, prioritized by closeness degree to the destination. Receiving nodes buffer successfully received packets and await the end of the batch. The highest priority forwarder then broadcasts the packets in its buffer, including its copy of the batch 23 map in each packet. The batch map contains the sender?s best guess of the highest priority node to have received each packet. Each node maintains an in-memory copy of the batch map, which is updated with information from received batch maps. The remaining forwarders then transmit in order, sending a batch fragment including only packets, which were not acknowledged in the batch maps of higher priority nodes. The forwarders continue to cycle through the priority list until the destination has enough packets to recover the original data using forward error correction. To avoid collisions, forwarding nodes initially delay transmissions based on their priority order, waiting for higher priority nodes to forward packets first. As nodes forward, each node updates its local batch map based on received packet headers and adjusts a transmission timer, which expires when it is the node?s turn to forward. Forwarding nodes, including the source node, continue forwarding the packets of a particular batch until 90% of them have been received by higher priority nodes or the destination. There may be multiple iterations through the forwarding. 2.6.4 ExOR Processes There are several processes in ExOR packet transmission. null Batch Preparation: The source begins by preparing a batch of packets for transmission. null Fragment Transmission: At transmission time, forwarding nodes send a batch fragment containing the subset of the received 24 packets, which have not been acknowledged by higher priority nodes. null Packet Reception: All nodes examine the header of every successfully decoded packet. If the node is listed in the forwarder set, the packet is added to a buffer the in-memory batch map is updated with the sender?s batch map contents, and an estimate of when the fragment will end is updated using the fragment information. If the received packet is from the next highest priority forwarder in the list, the local node sets the estimated forwarding time timer for immediately after the predicted end of the fragment. Otherwise, the forwarding timer is set to the minimum forwarding time (five packet durations in the implementation) times the number of higher priority nodes in the list. This estimate is intentionally aggressive; the estimate is revised if any other packets belonging to the batch are heard, but if they are not, then the medium is assumed to be clear. 2.6.5 Deciding whether to forward and completion When the forwarding timer expires, the node inspects its in-memory batch map, sending packets that have not been acknowledged by higher priority nodes. The node forwards only if less than 90% of the batch map has been acknowledged by a higher priority receiver. If it is the destination?s turn to forward packets, it sends a small number of packets A B Figure 2.1 Contour of probability of packet reception from a central node at two different transmission power settings (modified from Ganesan et al 2001). 25 P r o b ab i l i t y o f su cc e s sf u l r e ce p t i o n P r o b ab i l i t y o f su cc e s sf u l r e ce p t i o n Figure 2.2 Probability of packet reception over distance with different transmission power settings (modified from Ganesan et al., 2001) 26 Maximum Transmission Distance En er gy En er gy Figure 2.3 Effect of the maximum transmission distance constrain on the average energy consumed per packet (Younis et al., 2002) 27 Maximum Transmission Distance Tim e Tim e Figure 2.4 Effect of the maximum transmission distance constraint on lifetime metrics (Younis et al. 2002) 28 90% A B C D 90% 90% 40% 10% Figure 2.5 A simple network example, with various receiving probabilities 29 30 CHAPTER 3 ENERGY EFFICIENT ROUTING ALGORITHMS 3.1 Introduction In the wireless sensor networks, power of battery is a vital resource for each wireless device. There are lots of methods in different layers for the solution of energy conservation problem has been done so far. But routing path selection plays most important role in energy conservation. The central part of any routing research is the definition of the path metric. Of course in this study, we regard the energy cost as our routing metric. In this chapter, we?ll discuss some related routing algirhtms of previous research one by one. Some research work has been done by J.-H. Chang & Tassiulas (1999) and Chang & Tassiulas (2000) based on the metrics of the energy efficiency route. They are: null Optimal Energy Consumption. null Flow Redirection (FR) null Minimum Transmitted Energy routing (MTE) null Maximum Residual Energy Path (MREP) 3.2 Different Algorithms 3.2.1 Optimal Energy Consumption This mechanism introduces the idea of information flow, which is the information- transmitted rate from one node to the other. The conservation of flow condition at each node is 31 that the sum of all incoming flow must be the same as the sum of the outgoing flow. Since the definition of system lifetime under certain information flow is the minimum battery lifetime over all nodes. The goal is to maximize the system lifetime with the given information generation rates. This problem can be solved as a linear programming problem. 3.2.2 Flow Redirection (FR) Further research work has been done by FR, which is based on the idea of Optimal Energy Consumption. By using an iterative feasible descent method, this algorithm tries to balance the minimum lifetime of each flow path. FR redirects a portion of the current flow at each node in a way that the minimum lifetime over all the nodes will increase so that the resulting flow to the destination node will have the same lifetime in all paths. There are several steps in the FR algorithm. Firstly, determining from which path to which path should do the redirection. Secondly, calculating the amount of redirection. Thirdly, according to the computation results above, redircting the flow properly so that the lifetime of the system can be increased. 3.2.3 Minimum Transmitted Energy routing (MTE): This is a shortest path algorithm and minimum transmitted energy algorithm where the path length is the sum of energy expenditures per bit transmission over each link in the path. The clear drawback of this algorithm is that the nodes close to source node will use up their energy very quickly due to their frequently used to do the transmission. 3.2.4 Maximum Residual Energy Path (MREP): This is another shortest path algorithm whose path length is link cost. The idea is to augment the flow on the path, which minimum residual energy after the flow augmentation will be the largest. In fact, this routing algorithm is to route packets through paths with maximum residual energy so that energy consumption in all paths will be balanced. J.-H. Chang & Tassiulas (2000) proposed one mathematical model to implement MREP. Define L p as a vector whose elements are the reciprocal of the residual energy for each link in the path after the route has been used by a unit flow.Element of L p for link (j,k) is ueE jkj ? 1 ? , E j is the residual energy at node j, ue jk ) is the energy cost of unit flow By using the lexicographical ordering in this case by comparing the largest elements first and so on, shortest path from each node to the destination can be obtained using a slightly modified version of the distributed Bellman-Ford algorithm. A unit flow is transmitted via the shortest path. 3.2.5 Analysis and Comparison Chang & Tassiulas (2000) also gave the analysis of three algorithms as: On the average, FR and MREP were both close to optimum with comparable performances, while MTE was not as good as the two. While the mean of the ratio R of MTE was about 0.75, that of FR and MREP were about 0.96. The ratio R of FR and MREP were over MTE were over 90% of the true optimum in 84% and 89% of the case respectively, while that of MTE was so in only 37% of the case. The worst case performance of MTE was 32 0.2160 of the optimum. Note that the performance of MTE was shown to be arbitrarily bad. The worst case of FR was 0.6567, and the worst case of MREP was 0.8349, which is better than that of FR. See table 3.1 for detail. From the analysis above, it is obvious that MREP is the best choice of the energy efficiency routing among the all performance. The key point is that MREP can distributed energy usage in multiple paths. But the MTE always does the transmission through the minimum transmission path, which will drain out the energy very quickly of the nodes. 3.3 Implementation of MREP Xie et al (2003) implemented the same idea of MREP in another way. They start off from the point that ?the best path is one that has the maximum residual energy left after sending the message?. In their implementation, they transform the MREP problem into a bottleneck one. That is taking the energy costs from vertices and puts them on the edges and then runs the max-bottleneck algorithm. The algorithm?s input are a directed graph G=(V, L) with vertex energies , sending costs and two vertices s (source node) and t (destination). The output is an s-t path in G that maximizes the Minimum Residual Energy (MRE) denoted by D(P) of path P among all s-t paths P in G. u E vu S , The routing problem can be modeled as a directed graph G =(V, L), where V is a set of vertices (wireless nodes) and L is a set of directed connections (u, v) from a vertex u to another vertex v. Initially, each vertex u has a battery charged with energy Eu ? 0. This energy will be consumed by transmitting messages. E(u) is the current battery 33 energy available at node u before routing a message. With each edge e=(u, v) associates the sending cost se (or su,v) for sending a message along e, sending a message along e will reduce E(u), the energy of u, by se. Of course, sending a message is only possible if none of the residual energies becomes negative. Formally, if a message is routed along a path P=(v1, v2,?, vk-1, vk) in G, where v1,?, vk are vertices and (v1, v2),?, (vk-1, vk) are the edges, then each node on P loses a certain amount of energy due to the sending cost. Let denote the residual energy of u after routing a message. u R = i v R ? ? ? ? ? +1,1 2,1 )( )( i vvi vvi SVE SVE 1,....,3,2 1 ?= = ki i Given definition of D(P) is Minimum Residual Energy(MRE) of path P }{min)( ,...1 i v ki RPD = = Let G = (V, L) be a directed graph such that associated with each edge. There is a bandwidth b(u, v) ?0. Now let P=v1, v2,?, vk-1, vk be a path in G. The bottleneck cost B(P) of the path is defined to be )(min)( 1, ,...1 + = = ii ki vvbPB The bandwidth b(u,v) has the definition b(u,v)=E(u)- S u,v Another important equation for the algorithm implementation is: D(P)=min(E(v k ), )))((min 1, 1 + ? ?? ii vvi ki svE =B( P ) 34 35 Modified Dijkstra?s algorithm for finding max-bottleneck paths Input: Source s and destination t. Out: A max-bottleneck spanning tree rooted at s containing a path to t 1. for every node v do G? {P[v]=0; C[v]= ?? } 2. C[s]=+ ; F=? ? . 3. for every neighbor w of s do {P[w]=s; C[w]=b(s,w); add w to F} repeat remove the node with maximum C[u] from F; for every neighbor w of u do if C[w]= - ? {P[w]=u; C[w]=min(C[u],b(u,w)); add w to F } else if { wF? and C[w]0. In sending a packet to one of its neighbors, an energy m 44 e will be consumed and the value of e depends on the packet size and the distance between the two nodes. Similar to previous work, we assume that the maximum transmission range of each node is D 0 . Within this range, a packet sent by a node can be received by its neighbors successfully. But if the distance between two nodes is , we assume that the packet can only be received with a receiving probability p, where and it decreases with the increase of the distance between the two nodes. The probability that the packet cannot be received by its neighbor is . According to the theory of probability, if we send the same packet from one node to its neighbor n times, then the probability that this packet can at least be received once is . Since , this probability is always smaller than 1, but with the increase of n , this probability can approach to 1. In application, it is impractical to send the same packet a lot of times to achieve a very high successful rate. So in our scenario, we define the maximum times of transmission to be =10, we also assume that when sending the packet multiple times, if the probability for the packet to be received at least once is higher than a given threshold (say, 0.999), then we consider the packet is sent successfully, i.e., 0 Dd > 10 << p p?1 n p)1(1 ?? 10 << p max n 0 p (1) 0 )1(1 pp n ??? Then, we have, )1ln( )1ln( 0 p p n ? ? ? (2) 45 So, with the given p , we can calculate how many times a packet needs to be sent in order to achieve a successful rate . On the other hand, with the given , we can find out the smallest receiving probability permitted between two nodes, 0 p n n pp 0 11 ??? (3) As discussed above, p is the probability that a packet sent by a node can be received by its neighbor, and it decreases with the increase of the distance between the two nodes. As an example, we adopt the following formula, 1 0 0 ? = d D ep d D (4) Figure 4.1 shows the relationship between d and p when 10 0 =Dm, D 0 is maximum transmission distance. Of course, many other probability models can be adopted, and it can also be determined by experiment. The reason we adopt 1 0 0 ? = d D ep d D in our experiment is that the tendency of this equation shown in Figure 4.1 is similar with the experimental result which is shown in Figure 2.2. Firstly, applying the user defined parameters (the largest number of times that a packet can be sent between two nodes), and (the threshold probability that the packet to be received at least once) max n 0 p to Equation 3 and 4, we can find out , the extension maximum transmission distance for the current node. Based on this value, we know the range of current node?s neighborhood. For each neighbor in the neighborhood, the distance to it is known. And then with calculation result and given D max d max d max d 0 (Maximum transmission distance), P(the probability for a packet to be successfully received between the node pair) can be derived from Equation 4. Finally, we apply the P value to Equation 2 and find n, which is the times the packet needs to be sent in order for it to be received at least once with a probability . As an example, we set =10, and then we have 0 p ,999.0 0 =p max n 0 4617.1 Dd ? ( 0max 4617.1 Dd = ), which means if 46 the distance between two nodes is less than , a packet sent by one node can be received by another node with a probability no less than if it is sent out n times, where . 0 4617.1 D 0 p 10?n Summarily, our model can be described as below: Let d denotes the distance between two nodes, if 1. , the packet sent by one node can be received by another node with a probability 1, and the energy cost to send the packet is 0 Dd ? )(dEe = , the larger the value of , the larger the value of . d e 2. , the packet sent by one node can only be received by another node with a probability . The energy cost to send the packet is 0 Dd > 10 << p )( 0 DEe = , i.e., the battery works at its largest power. To make the information be received with a probability (for example, 0.999), the node can send the packet multiple times, then, the probability for the packet to be received at least once is given by Equation 1. If we know the relationship between the transmission probability and distance (for example, Equation 4), we can then find out how many times the packet needs to be sent (Equation 2). If the packet is sent times, then the energy cost is 0 p n )( 0 DnEe = . For our example, if we set , then all the nodes with can all be considered as neighbors of a node. 10?n 0 4617.1 Dd ? Figure 4.2 shows an example of wireless network. 50 nodes randomly distribute in a range of 50?50 m. S is the source node and T is the termination node. If a packet can be sent only when , then all the packets from S to T must pass node A and B, m. If one of the two nodes is out of energy, then the network has to die. But 10?d 8.9= AB d 47 actually, m, m, 1.10= AE d 6.13= AD d 2.11= CD d m and 0.12= AE d m. According to our scenario, all these node pairs can be selected in a routing path. For example, using Equation 4, the transmission probability 9803.0= AE p , if a packet is sent twice from A to E, then it will be received at least by E with a probability 0.9996. Of course, higher energy cost will be required by this approach since a packet is sent twice. But the advantage is that more nodes can participate the transmission. Thus the problem that a few nodes are used heavily and most nodes are still full of energy is avoided. Using this method, more valid packets can be sent from the source node to the destination node, and of course the lifetime of system is increased. 4.7 MREPE and MREPC In order to compare the actual performance of original MREP and our modified MREP, we design two types of models: MREP Extension: For each node do the few steps below: First, calculate the maximum extension distance and define range of the extension neighborhood. With the application defined P 0 (the least receiving success rate) and (maximum times of transmission), (extension maximum distance between two nodes) can be derived. In this way, the neighborhood can be defined as the nodes within the range of . As an example, we set P max n max d max d 0 =0.999, =10, and then we have =1.4617D max n max d 0 , which means if the node is in the range of 1.4617D 0 , it can be regarded as a neighbor. Second, apply the original MREP to each node in the neighborhood. In order to compare the performance with original MREP algorithm, we implement our scenario 48 49 based on pseudocode given in Xie et al (2003). Modified Dijkstra?s algorithm is implemented here to get maximum bottleneck paths (Maximum Residual Energy Path). The operation of this algorithm is starting from the source node, for each node (or parent node) in the network, compares its bottleneck energy value (the minimum residual energy value of all the ancestor nodes) with the residual energy value of each of its neighbor node (child node)?s after transmission, and put the minimum of the two to the bottleneck value of the corresponding child node. Among the all of children nodes of each parent, select the node with maximum bottleneck energy value and put it into the optimal path. Third, check the distance to the node with Maximum Residual Energy, if it is larger than D 0 , then with its d value, calculate the n value. Retransmit n times to compensate for the packet loss due to long distance. Continue the path selection from the chosen node, check with its neighbor nodes and ignore the nodes not being selected until destination node is reached. See Figure 4.3-Figure 4.5 for examples. M0 represents the valid links of original MREP and M1 represents valid links of MREPE. MREP and MREPE work alternately. Since there is no modification to MREP algorithm at all, we just make a change in the mathematical model. In the examples, the route path selection algorithm is as the same as the original MREP. The difference is that with MREPE there may be legal paths that may not be legal in MREP. For example, A->G->I->L in Figure 4.3, B->J->N->Q in Figure 4.5 and N->S- >Sink in Figure 4.4 are legal paths in MREPE but not MREP. In this scenario, the original MREP and MREPE work alternately, which means if transmission distance is longer than the defined maximum transmission distance, it works as MREPE. In the extreme case, where MREPE shows its advantages, such as Figure 4.5, only the MREPE 50 can work well since neighbor nodes are always far away and no close neighbors have enough energy. MREP combination: This model prolongs the system lifetime by switching over from the original MREP to the new MREP extension model above after certain threshold. The several steps below show how this model works. First, the algorithm is same as the original MREP. Find the nodes with Maximum Residual Energy. Second, when there is no path available for the next transmission with the original MREP, switch over to the new MREP extension model and continue transmission using this method. If we still depend on the original MREP for finding paths, there will be node death after the transmission or no transmission can be done due to depleted energy. 4.8 Summary In this chapter, the analysis of the main reasons for energy consumption in sensor network routing is conducted. The conclusion is that the broadcasting the entire networks not only waste lots of energy but also involve lots of traffic. So it must be avoided by adopting the local unicast communication. Our strategy in this research work is to find the route path based on alternative metrics of energy efficiency. By investigating previous research work done by Chang & Tassiulas (2000), and Xie et al (2003), we discover that the main obstacle to increasing lifetime is the imbalance in energy usage. Based on the original MREP model, our goal is to distribute the energy load as uniformly as possible. By means of extending the maximum 51 transmission distance between two nodes, we enable more nodes in the network to participate in the transmission. This avoids the unfortunate result where most of nodes in the network still have lots of energy left when some nodes die and there is no path available. Both the extension of maximum transmission distance and low packet loss is achieved by retransmitting of the same packet. Using application defined parameters, it is easy to compute the number of transmission required. 10 12 14 16 18 20 0.4 0.5 0.6 0.7 0.8 0.9 1 Figure 4.1 Relationship between and d p when 10 0 =Dm 52 0 10 20 30 40 50 0 10 20 30 40 50 S T A B C DE Figure 4.2. An example network in 50m?50m area 53 Source A C B D F E O N R S Sink H G I K J M P L Q M0 M1 M1 M1 M0 M0 Figure 4.3. An example showing how MREPE works (1) 54 Source A C B D F E O N R S Sink H G I K J M P L Q M0 M0 M0 M1 M1 Figure 4.4 An example showing how MREPE works (2) 55 56 Source A C B D F E O N R S Sink H G I K J M P L Q M0 M0 M1 M1 M1 Figure 4.5 An example that shows the advantages of MREPE compared with MREP 57 CHAPTER 5 PERFORMANCE EVALUATION 5.1 Introduction In the previous chapter, we analyze the major reason for the limitation of system life in networks with unbalanced energy usage. Based on the original MREP algorithm, we provide solutions to the problem of uneven distribution of energy cost. The solutions are MREP Extension and MREP Combination. This chapter reports some performance results from extensive tests, which have been implemented in Matlab simulation software. Our new versions of models are named ?Maximum Residual Energy Routing Extension (MREPE)? and ?Maximum Residual Energy Routing Combination (MREPC)?. Both of them are derived from original MREP algorithm and they are similar to each other. Thus sometimes, in our analysis, we use MREPE as the typical case to illustrate the performance results. This chapter describes our simulation schemes and test methodology and compares the performance of both the algorithms with the original one in terms of system lifetime and residual energy until system death under different density. We also generate results on the number of transmission and retransmission energy cost. 5.2 Experiment Setting and Assumptions To compare the performance of our algorithms with the original MREP, we took some of the experimental parameters from Xie et al (2003). The experiments are conducted on random networks. There are always 50 nodes generated randomly and distributed in a square of size x by x (see Figure 5.1). We tried different x values, such as 35 m (dense graph), 50 m (sparse graph) and other typical values. All the experiments are done under the assumption that the maximum transmission range ( ) of each node is 10 m for application-defined receiving rate to be 99.9%. The energy expenditure model for sending one bit is assumed to be given by: 0 D ),/(1.0 2 bitnJde ?= md 10? (5.1) Where d is the distance in terms of meters. For the initial node energy, a value around nJ is applied to all the experiments regardless of whether the network is sparse or dense. However, simulations showed that less initial energy does not affect the performance comparison. Our assumption is that the packet size is fixed to be 600 bits. Traffic was uniformly distributed between all source-destination pairs. Each result in each run is based on twenty randomly generated sample network topology graphs. 6 105? 5.3 Performance Measurement In the following, three routing algorithms are compared from different aspects. They are the original MREP, MREP Extension (MREPE), and MREP Combination (MREPC). The key performance measurement is the system life, which is defined as the time until the first node in the network depletes its energy. In the implementation of our algorithms, we regard the system death as when no legal path is available. In this study, we define the system lifetime as the number of valid packets routed during the lifetime of the system. The actual number does not seem to be 58 important; it is the difference between the results that indicate the relative performance of each routing algorithm. 5.4 Criteria of Evaluation There are several criteria in our experiments to evaluate the performance of our algorithms. 5.4.1 System Lifetime It measures the number of valid packets sent from the source node to the sink node until the death of system. The definition of system death is the time when the first node depletes its energy and there is no legal path available. Though the goal of all the energy-efficient routing algorithms is to increase the lifetime of system (this is in terms of time), in our experiments, we translate this into number of valid packets sent during the limited system lifetime (this is in terms of number of packets). The reasons for adopting the latter method are: First, we took this evaluation method from Xie et al?s (2003) paper in order to standardize our evaluation method. Second, from the implementation point of view, counting the number of packets sent during system lifetime is more convenient. The more valid packets sent indicates the longer of the system lifetime and more efficient the algorithm. The lifetime of MREPE is always higher than the lifetime of MREP in the 20 runs under 50?50 sparse networks (Figure 5.2). We show this typical case in Figure 5.2 and Figure 5.3 because it is under sparse networks. Later we will discuss the important influence of network density on system lifetime. The denser the network is, the longer the system lifetime. If an algorithm performs well under sparse network, it can certainly perform well under dense network. The trend of MREP and MREPE in Figure 59 5.2 are almost the same, which means under a certain network topology, if MREP can send maximum number of valid packets, so can MREPE. However, MREPE results in much larger number of valid packets sent for each experiment. 5.4.2 Remaining Energy Until Death of System In another measurement, we compute the total residual energy level of all nodes in the network when the system is dead. High remaining energy level at system death does not necessarily mean better algorithm since there are still lots of unused energy that cannot be used. Obviously this is a waste from the energy usage point of view. From Figure 5.3 we can see an example of system remaining energy level in a 50?50 sparse area, with 50 randomly created nodes for 20 runs of experiments. From this typical case, we can tell that our MREPE algorithm always has much lower energy left than the original MREP. The reason behind this result is that our MREPE always let more nodes participate in transmission though there is retransmission energy cost due to longer distance of transmission. With the same initial energy, the two algorithms (MREP & MREPE) show a big different in the level of energy left. MREPE remaining energy is much lower than that of MREP. We can conclude that the remaining energy is used to prolong system lifetime, since there are always tradeoff between the system remaining energy and system lifetime. Sometime, in order to increase system lifetime, we have to consume more system remaining energy. Our experiment shows that average system energy left for MREPE decreased by 50% compared to the original MREP. 60 5.4.3 Network Density The performance of the algorithms under different network distribution is investigated. It is a method to evaluate the algorithms from the robustness and Quality Of Service point of view. From Figure 5.4, the trends of the three algorithms are the same, which is inversely proportional to the density of the network. Sparse networks have lower average system lifetime than dense ones. It is easy to understand why. For example, there are 50 nodes in the network. If they are distributed in a sparse network such as a 55?55 area, the distance between nodes are relatively long. The worst case is that there is no legal path available in some cases. As shown in Figure 5.4, the unavailability of paths in the sparse networks is the key point influencing the system lifetime no matter what algorithm is used. On the other hand, in the dense network case, 50 nodes are distributed in 35?35 area, the distance between nodes are relatively short. There are more close nodes, and more legal paths available. This helps prolong the system lifetime. In Figure 5.4, we compare the results of the average system lifetimes of the three algorithms under different density which ranges from 35?35 to 55?55. It is obvious that MREPE and MREPC perform much better than MREP. However, between MREPE and MREPC, there is only a slight difference. MREPE has little advantage over MREPC when the network topologies are dense or sparse, such as, 35?35 and 55?55 in Figure 5.4. Our experiment shows that the average system lifetime under different density can be increased by 20~30% in both MREPE and MREPC compared to the original MREP. Fig 5.5 shows that the sparser the network, the more energy is left when system dies. One reason for this result may be that for sparser networks, there are fewer paths 61 available and fewer valid packets transmitted during the system lifetime. Thus with the same initial energy level, there will be more energy left when the system dies. Fig 5.4 & Fig 5.5 show that under different network density, our new algorithms perform better than the original MREP in terms of both system energy left and system lifetime. Since we have already establish that network density plays an important role in routing algorithm performance, MREPE performs much better in sparser networks than in denser networks compared to the original MREP. 5.4.4 Number of packets retransmitted: Figure 5.6 and 5.7 show a typical retransmission statistic in the MREPE algorithm. In the 55?55 sparse network area, which is the least dense case in our experiment, the total system lifetime is 1705 packets and application-defined receiving rate is 99.9%. Among the 1705 packets, there are 18% of them have been transmitted successfully without retransmission, 34% of them by one time of retransmission and 27% of them by 2 retransmission. From the statistical result, we can tell that most (about 34%) packets are sent with one retransmission, while very few (about 5%) packets are sent through 5 retransmission. The reason that we did the experiment of sparse network distribution is that the sparse network is the worst case. Retransmission result of denser networks will be much better than this. The question is how much energy is actually used for retransmission. The next section discuss this evaluation criterion. 5.4.5 Retransmission Energy Cost Rate The general definition of retransmission energy cost rate is the mount of retransmission energy cost in the total transmission energy cost when the system lifetime 62 ends. Table 5.1 shows the retransmission energy cost rate of MREPE. We analyze the statistic data from several different factors such as density of network, average retransmission energy cost rate, standard deviation of average retransmission energy cost rate, minimum and maximum value of average retransmission energy cost rate, total number of valid packet sent without retransmission. Table 5.1 shows that with the increase of sparseness, the rate of retransmission energy cost increases accordingly. This means that the average retransmission energy cost rate is proportional to sparseness of network distribution. The reason behind this fact is that with sparse network, the distance between nodes is longer. MREPE shows its advantage by communicating with far away neighbors and guarantee the QOS by the means of retransmission. However, with the same sparse network, for some cases, the original MREP cannot find valid paths due to the long distance between the neighbor nodes and no route path being available. There are cases of no retransmission at all for the network of 35?35, 40?40, 45?45, 50?50. For packets sent without retransmission, in network density of 40?40, MREPE performs best. But a surprising fact is that when the network density is 35?35, there are only 86 packets sent successfully without doing retransmission. When the network densities are 55?55 or 60?60, there is no packet sent without retransmission, which means retransmission plays an important role in the sparse network distribution cases. Whether sparse networks can still work as well as dense ones really depend on communication between long distance neighbors and the retransmission of packets. 63 64 5.5 Comparing Simulated Annealing with MREP Since there are various suboptimal algorithms developed for optimization problems, among which, Simulated Annealing (SA) has been found to be generally the most efficient. We can regard this energy efficient routing problem as a type of optimazation problem. So we first tried to apply SA to the energy efficient routing problem. See Figure 5.8 and Figure 5.9 for reference. In Figure 5.8, the lifetimes of SA are always less than the lifetimes of MREP in the 10 runs. While for the comparison of residual energy level until the system death in Figure 5.9, there is almost no statistical difference in the 10 experiments. Based on the second comparison, we can conclude that SA cannot compete with MREP in the energy path route problem, which means it is difficult to design new algorithms to perform much better than MREP. Thus, based on the algorithm of MREP, and making efforts to improve performance of MREP using a different mathematical model for radio transmission becomes the motivation of our study. 5.6. Summary The performance of MREPE, MREPC and MREP are compared and evaluated in detail in sparse and dense network distribution. In all cases, MREP and MREPC are energy efficient, especially under the denser network distribution. Both MREPE and MREPC make good use of system remaining energy, so that the total system lifetime is increased and more valid packets can be sent before the system dies. The fact is that the remaining energy level of both MREPE and MREPC is much lower than the original MREP. There is also statistical data showing the relationship between the retransmission times and corresponding percentage of the packets. Even though we test this under 50?50 sparse network distribution, and 99.9% successful reception rate, we can see that most of packets are sent successfully by 1 or 2 retransmissions, and very few packets are sent with 5 retransmissions or more. 65 66 Table 5.1 Retransmission Energy Cost Rate under different network Density X Retransmission Cost Rate Standard Deviation Minimum Maximum Number of PKG Without Retransmission 35 0.5752 0.1749 0 0.8622 86 40 0.4969 0.2837 0 0.8644 904 45 0.4056 0.2584 0 0.854 618 50 0.5657 0.1265 0 0.8546 18 55 0.7892 0.0181 0.7423 0.8369 0 60 0.7614 0.053 0.6293 0.8757 0 0 1 2 3 4 5 0 1 2 3 4 5 C B DE A S T Fig 5.1. Illustration of Uniform Traffic Fields 67 4500 68 MREP MREPE 4000 3500 3000 System Lifetime 2500 2000 1500 1000 500 0 0 5 10 15 20 Times of Run Figure 5.2 System lifetime comparisons under 50m 50? m network density 5E6 MREP MREPE 4E6 Residual Energy Level 3E6 2E6 1E6 0 0 5 10 Times of Run 15 20 Figure 5.3 Residual Energy Level Comparisons under 50m?50m network density 69 MREPC MREPE MREP 50 55 4535 40 Size of Square 7000 6000 5000 4000 3000 2000 1000 0 Average System lifetime Figure 5.4 Average System Lifetime under Different Density 70 71 0% 10% 20% 30% 40% 50% 60% 70% 80% 90% 35 40 45 50 55 MREP MREPE MREPC Size of Square Average Remaining Energy Rate Figure 5.5 Average Remaining Energy under Different Density 72 01234 5 0 100 2 3 4 00 00 00 500 600 N u m b e r o f P a c k e t Number of retransmission Figure 5.6 Number of Retransmission with corresponding Number of Packets in MREPE 18% 34% 27% 11% 8% 2% 0 1 2 3 4 5 Number of Retransmissions Fig5.7 Percentage of Total Number of Packets Vs Number of Retransmission packets in MREPE 73 System Lifetime 0 1000 2000 3000 4000 5000 12345678910 Number of Run S yst em L i f e t i m e MREP SA Fig 5.8 System Lifetime comparison with SA 74 Residual Energy Level 0.00E+00 5.00E+05 1.00E+06 1.50E+06 2.00E+06 2.50E+06 3.00E+06 3.50E+06 4.00E+06 4.50E+06 12345678910 Number of Run R e s i d u a l E n e r g y U n t il sy st em d eat h MREP SA Fig 5.9 Residual Energy Level comparing with SA 75 76 CHAPTER 6 CONCLUSIONS AND FUTURE WORK 6.1 Summary In order to improve energy efficiency and increase system lifetime of sensor networks, several modification of MREP algorithm have been made and tested in this research work. Two algorithms based on the original MREP have been proposed: MREPE and MREPC. The main conclusion and achievements are summarized as follows: 1. MREPE extends the node distance beyond that in the original MREP. By extending transmission distance between sender and its neighboring receiver, more neighbor nodes are included, and more paths can be chosen. Under the assumption that 99.9% receiving rate can be guaranteed, MREPE compensates for transmission loss (due to longer distance) with retransmission. The performance of MREPE under different network distribution is much better than MREP, especially under denser networks. This algorithm can increase system lifetime by 20%~30%. At the same time, it decreases the system energy left by about 50%. 2. MREPC combines the original MREP with MREPE. It works as the original MREP when there are path available in the network, but switch over to MREPE when there is no legal path using the original MREP or when the first node will die if the 77 original MREP is still in use. This allows network transmission to continue beyond the lifetime of MREP. More valid packet is sent and system lifetime is increased. Experimental results of MREPC and MREPE show that they give similar performance. The major lesson learned so far from this study is that the optimal algorithm itself is hard to improve, but changing the mathematical model of radio transmission allows the performance to be improved. Introducing probabilistic concepts to network communication and extending transmission distance with multiple transmissions are novel ideas in our routing protocol design. 6.2 Future work A future work will investigate minimizing retransmission cost further. An alternate mathematical model or new implementation algorithm of MREP can also be introduced. In this study, we only deal with routing path design within a cluster. Inter cluster routing design will definitely be an interesting research topic. This study assumes that nodes distribution is static. How well will this algorithm perform in a dynamic sensor network? Our future research work will investigate this issue. Only sending energy cost has been used in this research. In the future, we will test the performance of the algorithm under the consideration of both sending and receiving energy consumption. 78 REFERENCE Biswas, S. and Morris, R. Opportunistic Routing in Multi-Hop Wireless Networks, ACM SIGCOMM Computer Communication, 2004, 34(1): 69-74 . Chang, J.-H. and Tassiulas, L., Routing for Maximum System Lifetime in Wireless Ad- hoc Networks?, 37 Annual Allerton Conf. on Communication, Control, and Computing, Monticello, IL, Sept. 1999. Chang, J.-H. and Tassiulas, L., Energy Conserving Routing in Wireless Ad-hoc Networks?, In IEEE INFOCOM, pp 22-31, 2000. Chen, J.-C., et al., A comparison of MAC Protocols for wireless Local Networks Based on Battery Power Consumption, Proc. IEEE INFOCOM '98, San Francisco, CA, Mar. 29--Apr. 2, 1998, pp. 150-57. De Couto, D., Aguayo, D., Bicket, J. and Morris, R., A high-throughput path metric for multi-hop wireless routing, The Ninth Annual International Conference on Mobile Computing and Networking (MobiCom '03), San Diego, California, September 2003. Draves, R., Padhye, J. and Zill, B., Comparison of routing metrics for static multi- 79 hop Wireless networks, SIGCOMM?04, Aug.30-Sept. 3,2004,Portland,Oregon. Flinn, J. and Satyanarayanan,M., Energy-aware adaptation for mobile applications, In Proceedings of the 17th Symposium on Operating Systems Principles, December 1999, pp 48-63. Gandham, S., Dawande, M. and Prakash, R., Energy Efficient Schemes for Wireless Sensor Networks with Multiple Mobile Base Stations, Globecom August 2003. Ganesan, D. and Estin, D., Complex Behavior at Scale: An Experimental Study of Low- Power Wireless Senor Networks, Technical report, UCLA/CSD-TR 02-0013, 2001 Intanagonwiwat, C., Govindan, R. and Estrin, D., Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks, In Proceedings of the Sixth Annual International Conference on Mobile Computing and Networking (MobiCOM '00), Boston, Massachusetts, August 2000. Johnson, D.B, Routing in ad hoc networks of mobile hosts, IEEE Workshop on Mobile Computing Systems and Applications, December 1994. Johnson, D., Maltz, D. and Broch, J., DSR: The Dynamic Source Routing Protocol for Multihop Wireless Ad Hoc Networks, In C. Perkins, editor, Ad Hoc Networking, chapter 5, pages 139--172. Addison-Wesley, 2001. 80 Kravets, R. and Kishnan, P., Power Management Techniques for Mobile Communication, ACM MOBICOM 98 Dallas Texas USA Li, L and Halpern,J.Y., Minimum-Energy Mobile Wireless Networks Received, IEEE International Conference on Communications (ICC), June 2001. Li, L., Halpern, J.Y., Analysis of a Cone-Based Distributed Topology Control Algorithm for Wireless Mylti-hop Networks, Proceedings of the 20th annual ACM symposium on Principles of distributed computing, Aug. 2001. Lorch, J.R. and Smith, A.J., Software Strategies for Portable Computer Energy Management, Technical Report: CSD-97-949, 1997. Madan, R. and Lall, S., Distributed Algorithms for Maximum Lifetime Routing in Wireless Sensor Networks, IEEE GLOBECOM, Dallas, TX, Nov,2004. Malpani, N. and Chen, J., A Note on Practical Constructions of Maximum Bandwidth Paths, http://www.cs.tamu.edu/course-info/cpsc629/chen/notes/ Marco Zuniga Z. and Krishnamachari, B., Optimal Transmission Radius for Flooding in Large Scale Sensor Networks, Proceedings of 23 rd international Conference on Distributed Computing Systems Workshops(ICDCSW?03) 81 Nabar, R.U., Bolcskei, H. and F.W.Kneubuhler. Fading relay channels: Performance limits and space-time signal design?, IEEE Journal on Selected Areas in Communications, June 2004 Perkins, C.E and Bhagwat, P. Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers, ACM SIGCOMM'94 Conference on Communications Architectures, Protocols and Applications, 1994. Rodoplu, V. and Meng, T.H., Minimum Energy Mobile Wireless Networks, IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, 17(8), 1999, 1333-1344. Rpllins, S., et al., Power-Aware Data Management for Small Devices, ACM WoWMoM?02, Sept, 2002, Atlanta, Georgia, USA. Sankar, A. and Liu, Z., Maximum Lifetime Routing in Wireless Ad-hoc Networks, INFOCOM 2004 Wattenhofer, R. and Li L., Distributed Topology Control for Power Efficient Operation in Multihop Wireless Ad Hoc Networks, IEEE INFOCOM, 2001, pp 1388-1397. Xie, Q., et al., Maximum Residual Energy Routing with Reverse Energy Cost, IEEE GLOBECOM, August 2003 82 Ye, W., Heidemann, J. and Estrin, D., An Energy-Efficient MAC Protocol for Wireless Sensor Networks, IEEE INFOCOM, New York, NY, June 2002, pp 1567-1576. Younis, M. and Youssef, M., Energy-Aware Routing in Cluster-Based Sensor Networks, IEEE/ACM MASCOTS, October, 2002. Youssef, M., Younis, M. and Arisha, K.A., A Constrained Shortest-Path Energy-Aware Routing Algorithm for Wireless Sensor Networks, Proceedings of the IEEE Wireless Communications and Networking conference 2002,Vol.2, pp.794-799,March 2002.