ENERGY-EFFICIENT TRAFFIC-AWARE ROUTING IN UNDERWATER ACOUSTIC SENSOR NETWORKS Except where reference is made to the work of others, the work described in this dissertation is my own or was done in collaboration with my advisory committee. This dissertation does not include proprietary or classified information. _____________________________________ Lei Zhang Certificate of Approval: ________________________ Kai Chang Professor Computer Science & Software Engineering ________________________ Alvin S. Lim, Chairman Associate Professor Computer Science & Software Engineering ________________________ David Umphress Associate Professor Computer Science & Software Engineering _______________________ Min-Te Sun Assistant Professor Computer Science & Software Engineering _______________________ George T. Flowers Dean Graduate School ENERGY-EFFICIENT TRAFFIC-AWARE ROUTING IN UNDERWATER ACOUSTIC SENSOR NETWORKS Lei Zhang A Dissertation Submitted to the Graduate Faculty of Auburn University in Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy Auburn, Alabama August 9, 2008 iii ENERGY-EFFICIENT TRAFFIC-AWARE ROUTING IN UNDERWATER ACOUSTIC SENSOR NETWORKS Lei Zhang Permission is granted to Auburn University to make copies of this dissertation 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 DISSERTATION ABSTRACT ENERGY-EFFICIENT TRAFFIC-AWAREROUTING IN UNDERWATER ACOUSTIC SENSOR NETWORKS Lei Zhang Doctor of Philosophy, August 9, 2008 (Master of Science, August 8, 2005) 135 Typed Pages Directed by Alvin S. Lim Underwater acoustic networks are a special type of wireless sensor networks deployed in a harsh oceanic environment for mission critical tasks. In this unique sensor network, energy efficiency is the most critical problem. When Maximum Residual Energy Routing is adopted in actual battery-powered underwater acoustic sensor networks, further improving the energy consumption in this protocol and prolonging the system lifetime becomes a significant problem. In this study, we examine the Maximum Residual Energy Routing Protocol (MREP) and propose a new model for energy utilization by considering the relationship between successful packet sending probability v 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. The limited bandwidth and power resources as well as the 3-D topology in underwater acoustic sensor networks have made the geographic routing a favorite choice. While most of the detouring strategies in the existing geographic routing do not work well for underwater sensor networks, the spanning tree routing detouring strategy can efficiently find a detour for a packet when greedy forwarding fails. However, the effectiveness of the spanning tree routing depends largely on the quality of the pre- constructed spanning tree. Most of the existing spanning tree construction algorithms build trees in a top-down and centralized fashion and do not consider the traffic load and residual energy level in the network, and therefore is likely to create trees with poor routing performance. In this research, we propose novel spanning trees, namely Distributed Traffic-Aware Routing Tree (TART) and Distributed Energy-Aware Routing Tree (EART) which are constructed completely in a bottom-up fashion with the traffic load and residual energy level in mind. Simulation results show that those spanning trees have very few conflicting hulls, result in much higher path throughput and residual energy level when compared against other spanning trees, leading to a better routing performance in a 3-D underwater sensor network. vi 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 dissertation. Particularly, his suggestions, criticism, guidance and general exchange of ideas contributed so much to this dissertation. His mentorship is paramount in providing a well rounded experience, which will be valuable treasure in future career. The author also wants to express her deepest gratitude to the advisory committee members, Dr Chang, Dr. Umphress, and Dr. Sun, the professors in the Department of Computer Science and Software Engineering at Auburn University for their excellent advice, constructive criticism, helpful and critical reviews throughout the Ph.D program. A special thank goes to Dr. Mao in Electrical and Computer Engineering Department at Auburn University, who kindly agreed to serve in this Ph.D. Dissertation as an outside reader. Finally, sincere thanks to her husband Ju Wang, who 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. vii Style manual or journal used: Guide to preparation and Submission of Thesis and Dissertation Computer software used: MS Office 2003 viii TABLE OF CONTENTS LIST OF FIGURES xi LIST OF TABLES xiii 1. INTRODUCTION ......................................................................................................... 1 1.1 Background Introduction ......................................................................................... 1 1.2 Organization of this Dissertation ............................................................................. 6 2. LITERATURE REVIEW .............................................................................................. 7 2.1 Preliminaries ............................................................................................................ 7 2.2 Multi-dimensional UW-ASNs ................................................................................. 7 2.3 Centralized or Distributed........................................................................................ 8 2.4 Energy Efficiency Routing Methodologies ........................................................... 10 2.4.1 Maximizing System Lifetime ......................................................................... 11 2.4.2 Minimizing Energy Cost................................................................................. 12 2.4.3 Improvement................................................................................................... 13 2.5 Other Methodologies ............................................................................................. 14 2.6 Methodology Analysis........................................................................................... 15 2.7 Transmission Distance & Reception Probability................................................... 15 2.8 ExOR...................................................................................................................... 20 2.8.1 Introduction..................................................................................................... 20 2.8.2 Properties of Multi-Hop Wireless Networks .................................................. 21 2.8.3 ExOR Operation.............................................................................................. 22 2.8.4 ExOR Processes.............................................................................................. 23 2.8.5 Whether to Forward ........................................................................................ 24 2.9 Summary................................................................................................................ 24 3. ENERGY EFFICIENT ROUTING ALGORITHMS .................................................. 25 3.1 Introduction............................................................................................................ 25 3.2 Algorithms ............................................................................................................. 26 3.2.1 Optimal Energy Consumption ........................................................................ 26 3.2.2 Flow Redirection (FR) .................................................................................... 26 3.2.3 Minimum Transmitted Energy Routing (MTE).............................................. 26 3.2.4 Maximum Residual Energy Path (MREP)...................................................... 27 3.2.5 Analysis and Comparison ............................................................................... 27 3.3 Implementation of MREP...................................................................................... 28 3.4 Examples of MREP................................................................................................ 31 ix 4. EXTENSIONS TO MREP ALGORITHM.................................................................. 33 4.1 Background Introduction ........................................................................................... 33 4.2 Introducing Reception Probability to Ad-hoc Network......................................... 34 4.3 The Drawback of MTE .......................................................................................... 36 4.4 Improvement.......................................................................................................... 36 4.5 MREP Analysis...................................................................................................... 37 4.6 Design and Mathematical Model........................................................................... 38 4.7 MREPE and MREPC............................................................................................. 42 4.7.1 MREP Extension............................................................................................. 43 4.7.2 MREP Combination........................................................................................ 44 4.8 Summary................................................................................................................ 46 5. PERFORMANCE EVALUATION............................................................................. 48 5.1 Introduction............................................................................................................ 48 5.2 Experimental Setting and Assumptions................................................................. 48 5.3 Performance Measurement .................................................................................... 50 5.4 Criteria of Evaluation............................................................................................. 50 5.4.1 System Lifetime.............................................................................................. 50 5.4.2 Remaining Energy .......................................................................................... 51 5.4.3 Network Density ............................................................................................. 53 5.5 Comparing Simulated Annealing with MREP....................................................... 59 5.6 Three Dimensional Networks ................................................................................ 61 5.7 Summary................................................................................................................ 62 6. DETOURING ROUTING TREE ................................................................................ 64 6.1 Background............................................................................................................ 64 6.2.1 Detouring Strategies with Planarization ......................................................... 67 6.2.2 Detouring Strategies without Planarization .................................................... 69 6.3 Detouring Routing Tree ......................................................................................... 73 6.4 Routing Tree Algorithms ....................................................................................... 75 6.4.1 Search Trees.................................................................................................... 75 6.4.2 Minimum Spanning Trees............................................................................... 76 6.4.3 Minimum Path Trees....................................................................................... 77 6.5 Algorithm Description ........................................................................................... 79 6.6 The Gravity Functions ........................................................................................... 89 6.6.1 Traffic Aware Gravity Function ..................................................................... 89 6.4.2 Energy Aware Gravity Function..................................................................... 91 6.7 Node Failure Management..................................................................................... 96 7. RESULTS AND EVALUATION OF ROUTING TREES ......................................... 97 7.1 Traffic Aware Routing Tree................................................................................... 97 7.1.1 Simulation Settings ......................................................................................... 97 7.1.2 Results and Analysis for Centralized Algorithms........................................... 98 7.1.3 Results and Analysis for Distributed Algorithms ......................................... 101 7.2 Results Evaluations for Energy Aware Routing Tree.......................................... 105 7.2.1 Simulation Settings ....................................................................................... 105 7.2.2 Results and Analysis for Energy Aware Routing Tree................................. 107 x 7.3 Time Complexity Analysis .................................................................................. 108 7.4 Summary.............................................................................................................. 111 8. CONCLUSION AND FUTURE WORK .................................................................. 112 REFERENCES ............................................................................................................... 115 xi LIST OF FIGURES Figure 1.1 Underwater Acoustic Sensors........................................................................... 3 Figure 2.1 Effect of the maximum transmission distance constraint on the average energy consumed per packet........................................................................... 16 Figure 2.2 Effect of Maximum Transmission Distance On Lifetime Metrics................. 17 Figure 2.3 Contour of Probability of Packet Reception From A Central Node At Two Different Transmission Power Settings. ......................................................... 19 Figure 2.4 Probability Of Packet Reception Over Distance With Different Transmission Power Settings.......................................................................... 20 Figure 2.5 Simple Networks Example With Different Receiving Probabilities.............. 22 Figure 3.1 Modified Dijkstra?s Algorithm....................................................................... 30 Figure 3.2 Example Of Routing Network........................................................................ 31 Figure 3.3 An Example Graph With Bandwidth Costs On Edges................................... 32 Figure 3.4 A Spanning Tree Output By The Modified Dijkstra?s Algorithm ................. 32 Figure 4.1 Relationship Between d And p .................................................................... 39 Figure 4.2 An Example Network In 50m?50m Area...................................................... 42 Figure 4.3A Work Mechanism of MREPE...................................................................... 45 Figure 4.3B Work Mechanism of MREPE...................................................................... 46 Figure 4.3C Work Mechanism of MREPE...................................................................... 46 Figure 5.1 Illustration of Uniform Traffic Fields............................................................. 49 Figure 5.2 System lifetime Comparisons Under 50m?50 m Network Density .............. 52 Figure 5.3 Residual Energy Level Comparisons Under 50m?50 m Network Density... 53 Figure 5.4 Average System Lifetime under Different Density........................................ 54 Figure 5.5 Average Remaining Energy under Different Density .................................... 55 Figure 5.6 Number of retransmission vs. packets in MREPE ......................................... 58 Figure 5.7 Percentage of Total Number of Packets vs. Number of Retransmission Packets in MREPE.......................................................................................... 59 Figure 5.8 System Lifetime Comparisons with SA ......................................................... 60 Figure 5.9 Residual Energy Level Comparisons with SA ............................................... 60 Figure 5.10 Average System Lifetime under Different Node Densities in 3D Network Topology....................................................................................................... 62 Figure 6.1 Packet Forwarding Using Convex Hull (To the Child Node) ........................ 70 Figure 6.2 Packet Forwarding Using Convex Hull (To the Parent Node)....................... 71 Figure 6.3 Conflicting Convex Hulls............................................................................... 72 Figure 6.4 Example of Clusters and Traffic Between Clusters ....................................... 81 Figure 6.5 Initial Stage of Tree Construction .................................................................. 82 Figure 6.6 Intermediate Stage of Tree Construction........................................................ 83 xii Figure 6.7 Intermediate Stage of Tree Construction........................................................ 84 Figure 6.8 Final Stage of Tree Construction.................................................................... 84 Figure 6.9 Routing Tree Without Conflicting Convex Hulls .......................................... 85 Figure 7.1 Number of Conflicting Convex Hulls ............................................................ 98 Figure 7.2 Average Path Length ...................................................................................... 99 Figure 7.3 Average Path Throughput............................................................................. 100 Figure 7.4 Number of Conflicting Convex Hulls in Distributed TART........................ 101 Figure 7.5 Average Path Length in Distribute Traffic-Aware Routing Tree................. 102 Figure 7.6 Average Path Throughput in Distribute Traffic-Aware Routing Tree ......... 104 Figure 7.7 Average Path Residual Energy in Energy Aware Routing Tree .................. 106 Figure 7.8 Average Path Residual Energy in DEAR Tree............................................. 106 xiii LIST OF TABLES Table 3.1 Performance comparisons of the three algorithms .......................................... 28 Table 5.1 Retransmission energy cost rate under different network density................... 58 1 CHAPTER 1 INTRODUCTION 1.1 Background Introduction In ad hoc networks, there is no communication infrastructure infrastructure, wireless users are still able to communicate with each other. In such a network, each node operates not only as a host but also as a router, taking the responsibility of packets forwarding even to the nodes outside the direct wireless transmission range. Each node participating in routing allows itself to discover ?multi-hop? paths through the network to any other node. The idea of ad hoc networking is sometimes called infrastructureless networking [13], since the nodes in the network dynamically establish routing among themselves to form their own network ?on the fly?. Wireless Sensor Network (WSN) can be classified into the category of ad hoc networks. As described in [1], it is a kind of wireless network consisting of spatially distributed autonomous devices using sensors to cooperatively monitor physical or environmental conditions, such as temperature, sound, vibration, pressure, motion or pollutants, at different locations. The unique characteristics of WSN can be summarized as: limited power, ability to withstand harsh environmental conditions, capability to deal with node failures and mobility, automatic reconfiguration, heterogeneity nodes organization, scalability, and unattended operation. 2 The development of wireless sensor networks was originally motivated by military applications such as battlefield surveillance. However, wireless sensor networks are now used in many civilian application areas, including environment and habitat monitoring, healthcare applications, home automation, and traffic control. Each node in a sensor network is typically equipped with a radio transceiver and a small microcontroller. The size of a single sensor node can vary from shoebox-size down to grain of dust size, although functioning 'motes' of genuine microscopic dimensions have yet to be created. The cost of sensor nodes is similarly variable, ranging from hundreds of dollars to a few cents, depending on the size of the sensor network and the complexity of individual sensor nodes. Size and cost constraints on sensor nodes result in corresponding constraints on resources such as energy, memory, computational speed and bandwidth. There is a unique kind of wireless sensor networks, called Underwater Acoustic Sensor Networks, as shown in Figure 1.1. Just as demonstrated in [3], underwater sensor networks have the potential to enable unexplored applications and enhance our ability to observe and predict the ocean. Unmanned or Autonomous Underwater Vehicles (UUVs, AUVs), equipped with underwater sensors, are also envisioned to find application in exploration of natural undersea resources and gathering of scientific data in collaborative monitoring missions. These potential applications will be made viable by enabling communications among underwater devices. Underwater Acoustic Sensor Networks (UW-ASNs) will consist of sensors, vehicles deployed underwater and networked via acoustic links to perform collaborative monitoring tasks. There is a broad range of applications for underwater acoustic sensor networks, such as: Ocean Sampling, Assisted 3 Navigation, Environmental Monitoring, Mine Reconnaissance, Distributed Tactical Surveillance, Undersea Biological Explorations, and Disaster Prevention. In contrast to ground sensor networks, which depend on radio transmission, Underwater Acoustic Sensor Networks adopt acoustic communication as their communication methodology. This is because radio waves propagate at long distances through conductive salty water only at extra low frequencies. Normally, the frequency ranges from 30-300 Hz. These extra low frequencies need large antennae and high transmission power. As demonstrated in [3], optical waves do not suffer from high attenuation, but are affected by scattering. Furthermore, transmitting optical signals requires high precision in pointing the narrow laser beams. So, links in underwater sensor networks are typically based on acoustic wireless communication instead of radio transmission. This special transmission method leads to many challenges in the protocols design of underwater acoustic networks. Figure 1.1 Underwater Acoustic Sensors 4 For underwater wireless communication applications, such as long-term monitoring tasks, energy efficiency is the most important issue to be considered in the protocol design. This is because batteries cannot be recharged, and solar energy cannot be exploited. Besides this, acoustic transmission requires more energy than radio transmission. One of the research directions of this research is to investigate energy efficiency issue in underwater acoustic sensor networks. By modifying one of the current optimal energy efficiency algorithms (MREP), we try to provide a solution to improve system lifetime. And then an effective cluster based routing tree algorithm is also proposed to tackle this problem. Underwater acoustic sensor network is a special type of wireless sensor networks deployed in a harsh oceanic environment for mission critical tasks. Its unique way of transmission makes its bandwidth limited. How to make a good use of limited available bandwidth and route the packets effectively is a significant problem to investigate in the underwater acoustic sensor networks routing research. Previous research shows that geographic routing can be a favorite choice for underwater acoustic sensor networks routing. In underwater environment, if some sensor nodes die and it is not feasible to replace them immediately. This might be end up with some void areas in the networks. In this case, an efficient detouring method in the geographic routing will be very necessary. In geographic routing, while most of the detouring strategies do not work well for underwater acoustic sensor networks, especially under the three dimensional networks topology. The spanning tree routing detouring strategy can efficiently find a detour when greedy forwarding fails. This research focuses on developing an effective spanning tree 5 based detouring method and considering about the limitation of bandwidth at the same time. Furthermore, we also propose an alternative idea of detouring spanning tree, which is to make the detouring method effective from the point of energy efficiency. However, the validity of the overall routing performance largely depends on the quality of the pre-constructed spanning tree. Most of the existing spanning tree construction algorithms build trees in a top-down and centralized fashion and do not consider the traffic load and residual energy level in the network, and therefore are likely to create trees with poor routing performance. In this research, we propose a novel spanning tree, namely Distributed Traffic-Aware Routing Tree (DTART), which is constructed completely in a bottom-up fashion with traffic load in mind. Simulation results show that DTART has very few conflicting hulls, shorter path length, higher path throughput when compared against other spanning trees, leading to a better routing performance in a three dimensional underwater acoustic sensor network. Beside this, Distributed Energy-Aware Routing Tree (DEART) is also proposed in this research by a substitute routing tree construction methodology. Those two methods not only try to find a detour, but also make the routing more efficient by including network traffic pattern and residual energy level aware at the same time. In geographic routing, coordinates of each node must be available in the routing process. Location Service has to be implemented to discover the coordinates of destination nodes. In this research, we assume that we do not address the design of a geographic location service. In addition, this research focus on underwater acoustic sensor networks, so the overall protocol design assumes that the nodes in the system are quasi-static. The routing 6 protocol has some built-in mechanisms to deal with intermittent node failures and occasional nodes joining or leaving the system, but it is not designed to handle dynamic change of the network in a very short time period. 1.2 Organization of this Dissertation The rest of the dissertation is organized as follows: In Chapter 2, we provide an overview of the previous work on underwater acoustic networks, such as energy efficiency routing issue and bandwidth limitation issue; In Chapter 3, we give a detailed analysis and solution of the energy efficiency routing; In Chapter 4, we provide our own solutions for two dimensional underwater acoustic networks routing; In Chapter 5, we evaluate the performance of both two dimensional and three dimensional energy efficiency routing protocols; In Chapter 6, three dimensional centralized and decentralized geographic routing detouring methods are proposed; In Chapter 7, we provide the results and evaluation analysis of our geographic routing algorithm with different metrics; In Chapter 8, we summarize the work in this research and describe open questions and possible future direction. 7 CHAPTER 2 LITERATURE REVIEW 2.1 Preliminaries This research work is to develop effective routing protocols and tackle the routing problems of underwater acoustic sensor networks. In this chapter, we will discuss communication architecture of underwater acoustic sensor networks and provide analysis of the potential research challenges. The survey on different protocols is also targeted at these research challenges. In addition, we make our own analysis and comparisons based on this survey. 2.2 Multi-dimensional UW-ASNs Based on general idea, some researchers in [16] have classified underwater acoustic sensor networks into the following architectures: Pompili [6] proposed a novel architecture for underwater acoustic sensor networks, three dimensional underwater acoustic sensor networks, which are to detect and observe phenomena that cannot be adequately observed by means of ocean bottom sensor nodes, i.e., to perform cooperative sampling of the three dimensional ocean environment. In this architecture, each sensor is anchored to the ocean bottom and equipped with a floating buoy that can be inflated by a pump. The buoy pushes the sensor towards the ocean surface. The depth of the sensor can then be regulated by adjusting the length of the wire 8 that connects the sensor to the anchor, by means of an electronically controlled engine that resides on the sensor. A challenge to be addressed in such architecture is resource limitation, such as energy, bandwidth, memory, and computation capability limitation. How to prolong the overall system lifetime and how to make good use of limited bandwidth are the research topics in this study. The following architectures for underwater sensor networks have been proposed by [32]: Static two dimensional underwater acoustic sensor networks can be applied to ocean bottom monitoring: They are constituted by sensor nodes that are anchored to the bottom of the ocean. They are interconnected to one or more underwater sinks by wireless acoustic links. These underwater sinks relay data from the ocean bottom network to a surface station. Typical applications may be environmental monitoring or monitoring of underwater plates in tectonics. Three dimensional networks of autonomous underwater vehicles: These networks include fixed portions composed of anchored sensors and mobile portions constituted by autonomous vehicles. Typical applications may be oceanography, environmental monitoring and underwater resources study. From the architecture above, we can obviously see that it is very necessary to propose both two dimensional and three dimensional routing protocols to solve the special source limitation problems in underwater acoustic sensor networks. 2.3 Centralized or Distributed In the routing protocol design, the first key issue is to decide whether the protocol should be centralized or distributed. This decision is made based on the different requirements of applications. The application with a big scale, but without clustering, 9 needs to be distributed. A smaller scale or cluster based application, centralized algorithm is good enough. 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 very well, e.g. the gateway, or distributed among the sensors themselves. Both centralized and distributed routes require updating of the routing table every time when the network topology changes. Though 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 sensors? energy that can be dedicated to serve the application. In addition, for large scale distributed routing algorithms, exchanging routing messages among the sensors will create excessive traffic that drains unnecessary energy since the receivers on the sensors may overhear the routing message transmissions not destined to them. The above analysis points out some common disadvantages of distributed algorithms from energy consumption aspect. As demonstrated in [7], underwater acoustic sensor networks are small in scale, less dense and have extremely limited energy resources. Compared with distributed routing algorithm, a centralized energy efficiency routing algorithm will be more appropriate for some small scale or cluster-based energy sensitive applications in underwater acoustic sensor networks. Managing the routing decision centrally at the cluster head or gateway can be seen as a logical extension to their roles, especially as all sensor readings have to be forwarded to them for aggregation and application-specific processing. Moreover, centralized routing is simple and fits the nature of the underwater acoustic sensor networks. Since acoustic 10 sensors are involved in data processing and communication, it is advantageous to make the offload routing decision from some resource-constrained acoustic sensor nodes. In addition, since the gateway has a cluster-wide view of the whole network, the routing decisions should be more optimal than the ones based on local views at individual sensor level. Given that, the gateway organizes the sensors in the cluster, it can combine the consideration for energy consumption in 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 or cluster head, which has more power than the other nodes and can make the routing decision within the cluster. In addition, we also can adapt some existing cluster head selection algorithm for the cluster head rotation [57]. In this way, the sufficient energy supply of cluster head can be guaranteed. However, this is beyond the scope of this research and we will not discuss it in detail. Our research assumes that the underwater acoustic sensor network has already been organized into clusters and cluster head has been decided. To simplify the problem, our research focus is on energy efficiency routing within the cluster. We will investigate the inter-cluster routing in our future work. 2.4 Energy Efficiency Routing Methodologies Before we design an energy efficiency routing protocol for underwater acoustic sensor networks, we do some survey about related work of wireless sensor networks. We try to find an appropriate one we can make modification according to the special characters of 11 underwater acoustic sensor networks, so that it can be tailored to this kind of sensor networks pretty well. Traditionally, research work on energy efficient routing in wireless sensor networks always focus on multi-hop routing. There are mainly two types of multi-hop routing protocols: maximizing system lifetime and minimizing energy cost. 2.4.1 Maximizing System Lifetime The first methodology, such as in [8], is to maximize the time at which the first node drains out 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 two nodes. The problem with this technique is that nodes on the minimum-energy path quickly use up power, thus the network will be partitioned when some nodes are dead. A rigorous formulation using linear programming has been presented by [9] which attempted to capture the issue of power consumption more precisely. The idea is to route the packets maximize network lifetime. Heuristics algorithms were proposed to select routes in a distributed manner to maximize network lifetime. However, these heuristics do not always lead to routes that are globally optimal. So the behavior can be poor in the worse case. Madan [8] provides one solution 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 12 problem above as minimizing the maximum ratio of power consumption to energy supply at each node. Sankar and Liu [10] formulate the problem as a maximum concurrent flow problem. All routing problems have analogous flow realizations, where the flow 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 maximum flow algorithms to the problems 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.4.2 Minimizing Energy Cost The other methodology is to minimize the total energy consumption of the networks, such as [11] and [12]. 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 [11], by using a 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 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 requires minimum energy is selected. In order to improve the protocol of [11], [12] proposed the idea of subnetwork. In the subnetwork, there are 13 fewer edges and less transmission energy consumption from the source node to the destination node than the original networks. Compared with protocol proposed by [11], protocol [12] shows its advantages of smaller network, lower link maintenance cost, a significant saving in energy usage, and computational simplicity. Wattenhofer [15] proposes a novel way of minimizing total energy consumption for wireless sensor 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 self made decisions. Since this algorithm assumes that there is no GPS for each node. Therefore, each node makes local decisions about its transmission power and this decision collectively guarantees 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 is created, in which the power consumption of each route can be achieved arbitrarily close to optimal. Further research work on this algorithm [14], introduces a cone of degree ? around each node. The parameter ?=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 is 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.4.3 Improvement Still focusing on the power control from the routing decision point of view, [27] separates the problem into two parts: single power level and multiple power level. For the 14 single level ones, the problem is reduced to a maximum flow problem with node capacities and the algorithms converge closing 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 et al. [9] also describes the shortcoming of the algorithms, which try to minimize the total energy consumed, but ignore the imbalance of the power usage. 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 lifetime of the system has been considered. Under the assumption of a set of source and destination node pairs, flow augmentation algorithm and flow redirection algorithm, which balance the energy consumption rates among the nodes in proportion to their energy reservation, have been adapted in this approach. By as much as 60% on average over the conventional minimum transmitted energy routing, the local and amenable distributed algorithm improve system lifetime. 2.5 Other Methodologies Many research work has been done from the point of flow-based energy-efficient routing algorithm. Gandham et al. [17] propose 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 overhead), integral flow values are highly desirable. A solution offered in [17] is to round the non- 15 integral flow values by using a sub-optimal rounding procedure. Moreover, this still cannot guarantee any bound on running time of the ILP-based method. Further work has been done by Gandham et al. [17], which introduces 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, [17] results in integral flow values, 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 [17], they mitigate this possibility by limiting the amount of energy each node can spend per round. 2.6 Methodology Analysis From the issues above, the conclusion can be drawn, maximizing system lifetime can be regarded as a better method of energy efficient routing. To further optimize this methodology, distributing the energy cost as uniformly as possible is the essential idea. So in this study, we start from the idea of multi-hop routing, integrate the method of maximizing system lifetime, and make efforts to distribute the energy usage as evenly as possible. 2.7 Transmission Distance & Reception Probability Younis [18] introduces a new energy-aware routing protocol for wireless sensor networks that uses distance as a measurement for transmission energy consumption. 16 Figure 2.1 shows that as the maximum transmission distance constraint increases, the average energy consumed per packet increases. 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. As the maximum transmission distance constraint increases, fewer of hops are chosen by the minimum number of hops routing algorithm lead 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 energy consumed per packet increases, the network lifetime parameters are decreased as shown in Figure 2.2. Figure 2.1 Effect of the maximum transmission distance on the average energy consumed per packet Low values for the maximum transmission distance constraint, the network topology graph is sparse and the length of the links is small which lead to reducing average energy Maximum Transmission Distance En erg y En erg y 17 consumed per packet. However, the end-to-end delay is increased due to the increase of the number of hops between a sensor node and the gateway. Figure 2.2 shows 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. Figure 2.2 Effect of Maximum Transmission Distance On Lifetime Metrics From a theoretical point of view, the protocol above provides a powerful verification that the transmission distance plays an important role in energy-aware routing and adjusting transmission distance wisely will result in good energy efficiency. Next, we want to show an experimental result regarding the role of transmission distance. Ganesan [19], attempts to quantitatively define and measure the effective communication radius at a given transmit power in a real setting and explore packet Maximum Transmission Distance Tim e Tim e 18 reception statistics over distance. They also several proposed important concepts that are very helpful to designers. o Backward link is the link where the recipient of the flood is closer to 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 provides us with a great 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 has 65% receiving rate, while the bad link has only 25% receiving rate as provided by the experimental results. There are a few facts that are proven in their experiments. square4 The distribution of packets reception rate over distance is non uniform. See Fig 2.1 and Fig 2.2 for reference. square4 Individual contours clearly exhibit directionality with propagation being better at some directions than others as shown in Fig 2.3 and Fig 2.4 square4 In Fig 2.3 and Fig 2.4, 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. 19 The observations clearly indicate the presence of long-links, which result in greater propagation in some directions than others. square4 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 available energy resources. Figure 2.3 Contour of Probability of Packet Reception From A Central Node At Two Different Transmission Power Settings (modified from [19]). 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 significant factor 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. 20 Figure 2.4 Probability of Packet Reception Over Distance With Different Transmission Power Settings (modified from [19]) 2.8 ExOR 2.8.1 Introduction Multi-hop wireless networks typically use routing techniques similar to those found in wired networks [20-23]. A routing protocol chooses a path 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 [24], 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 Pro ba bil ity of su cce ssf ul rec ep tio n Pro ba bil ity of su cce ssf ul rec ep tio n 21 concurrently. Then, the destination chooses the best of many relayed signals, or combines information from multiple signals. Proposed by [25], 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 and chooses one of them only after knowing the nodes, which actually received the packets. ExOR delays forwarding decisions until 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.8.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 a simple network for the purpose 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 22 wide range of receiving rates, so that packets occasionally travel a long way towards the ultimate destination. Another advantage of ExOR compared to 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. Figure 2.5 Simple Networks Example With Different Receiving Probabilities 2.8.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 wait the end of the batch. The highest priority forwarder then broadcasts the packets in its buffer, including its copy of the batch 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 23 then transmit in order and send 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, wait 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.8.4 ExOR Processes There are several processes in ExOR packet transmission. square4 Batch Preparation: The source begins by preparing a batch of packets for transmission. square4 Fragment Transmission: At transmission time, forwarding nodes send a batch fragment containing the subset of the received packets, which have not been acknowledged by higher priority nodes. square4 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 24 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 timer 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.8.5 Whether to Forward When the forwarding timer expires, the node inspects its in-memory batch map, sends 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 will send a small number of packets. 2.9 Summary Just as hown above, every node has non-zero receive probability from multiple nodes, and the transmissions reach potential receivers with a wide range of receiving rates. This is one of the important characteristics of multi-hop routing. In addition, this motivates us to consider how to make good use of the relationship of reception rates and transmission distance in energy efficient routing. We will demonstrate the method for energy efficient routing that takes the advantage of the different successful reception rate. 25 CHAPTER 3 ENERGY EFFICIENT ROUTING ALGORITHMS 3.1 Introduction In underwater acoustic sensor networks, battery power is a vital resource for each wireless sensor. Many methods for energy conservation at different layers have been investigated in wireless sensor networks. However, there is very little research on underwater acoustic sensor networks, especially in the routing layer, even though, routing path selection plays the most important role in energy conservation in underwater acoustic sensor networks routing. In this chapter, we will discuss some related routing algorithms. Some research work has been done in [26-27] based on the metrics of the energy efficient route. They are: square4 Optimal Energy Consumption. square4 Flow Redirection (FR) square4 Minimum Transmitted Energy routing (MTE) square4 Maximum Residual Energy Path (MREP) 26 3.2 Algorithms 3.2.1 Optimal Energy Consumption This mechanism introduces the idea of information flow, which is the information- transmission rate from one node to another. The conservation of flow condition at each node is 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 be the redirection. Secondly, calculating the amount of redirection. Thirdly, according to the computation results above, redirect 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 27 path. The clear drawback of this algorithm is that nodes close to source node will use up their energy quickly due to their frequent use. 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, where the minimum residual energy after the flow augmentation will be the largest. In fact, this routing algorithm routes packets through paths with maximum residual energy so that energy consumption in all paths will be balanced. [27] proposed a mathematical model to implement MREP. Define Lp 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 Lp for link (j,k) is ueE jkj ? 1 ? , Ej 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 In table 3.1 from [26], provides comparison data of different energy efficient routing algorithms. Ratio R is defined as the ratio between the global optimal system life time and local system life time made by different energy efficient routing algorithms. The analysis results show: On average, FR and MREP were both close to optimum with comparable performances, while MTE was not as good as the other two. The mean of the ratio R of MTE was about 0.75, those of FR and MREP were about 0.96. The ratio R of 28 FR and MREP were over MTE by 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 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 efficient routing. The key point is that MREP can distribute energy usage in multiple paths as even as possible. But the MTE always transmits packets through the minimum transmission path, which will drain out the energy of those nodes quickly. Table 3.1 Performance comparisons of the three algorithms R MTE FR MREP Average 0.7519 0.9538 0.9607 Worst case 0.2160 0.6567 0.8349 Over 0.9 37% 84% 89% *Based on results of [26] 3.3 Implementation of MREP In [28], the same idea of MREP was implemented in a different way. They start off from the point that ?the best path is the 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 to take the energy cost from vertices and put them on the edges and then run the max-bottleneck algorithm. 29 The algorithm?s input is a directed graph G= (V, L) with vertex energies uE , sending costs vuS , 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. 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 energy available at node u before transmitting 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 uR denote the residual energy of u after routing a message. = iv R ? ? ? ? ? +1,1 2,1 )( )( ivvi vvi SVE SVE 1,....,3,2 1 ?= = ki i Given definition of D (P) is Minimum Residual Energy (MRE) of path P }{min)( ,...1 ivki 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 30 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) - Su,v Another important equation for the algorithm implementation is: D(P)=min(E(vk), )))((min 1,1 + ? ?? ii vviki svE =B( P ) D (P) =min (E (vk), )))((min 1,1 + ? ?? ii vviki svE =B ( P ) Figure 3.1 Modified Dijkstra?s Algorithm (base on J.Edmonds, R.M.Karp, et al.(1972)). C[w] is the cost of an optimal(max) bottleneck path between s and w. The algorithm builds a tree (stored using the predecessor P[w] links) such that the unique path in the tree from s to w is an optimal s-w path. This algorithm takes advantages of bandwidth of the edge to use the maximum MRE among all paths. Given Vts ?, , the max-bottleneck problem, sometimes known as the max-bandwidth problem, is to find a path from s to t that maximizes B(P). This problem has been extensively studied and it is well known that such a path can be found using a simple modification of Dijkstra?s shortest path algorithm in [29], which builds a tree rooted at s and the unique path from s to t is a max-bottleneck path between s and t. The modified 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 Gv ? do {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 { w F? and C[w]0. When one node sends a packet to a neighbor, an energy e will be consumed and the value of e depends on the packet size and the transmission distance. Similar to previous work, we assume that the maximum transmission range of each node is D0. Within this range, a packet sent by a node can be received by its neighbors successfully. But if the distance between two nodes is 0Dd > , we assume that the packet can only be received with a receiving probability p, where 10 << p 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 p?1 . 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 np)1(1 ?? . Since 10 << p , this probability is always smaller than 1, but with the increase of n , this probability can approach to 1. In reality, it is impractical to send the same packet many times to achieve a very high successful rate. So in our scenario, we define the maximum number of transmissions to be maxn =10, we also assume that sending the packet multiple times, if the probability for the packet to be received at least once is higher than a given threshold 0p (say, 0.999), then we will consider that the packet is sent successfully, i.e., 0)1(1 pp n ??? (1) Then, we have, )1ln( )1ln( 0ppn ??? (2) 39 So, with a given p , we can calculate how many times a packet needs to be sent in order to achieve a successful rate 0p . On the other hand, with a n value, we can find the smallest receiving probability between two nodes, n pp 011 ??? (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, 100 ?= dDep dD (4) 10 12 14 16 18 20 0.4 0.5 0.6 0.7 0.8 0.9 1 Figure 4.1 Relationship Between d and p When 100 =D m The reason we use this equation to represent the mathematic relationship is that we try to formulize the relationship as close to the experimental results in Figure 2.4 as possible. From equation 4, we can draw Figure 4.1 shows the relationship between d and p when 100 =D m, D0 is maximum transmission distance. The tendency of equation 4 40 shown in Figure 4.1 is similar with the experimental results which are shown in Figure 2.4. Of course, many other probability models can be adopted, and it can also be determined by experiments. Firstly, applying the user defined parameters maxn (the largest number of times that a packet can be sent between two nodes), and 0p (the threshold probability that the packet to be received at least once) to Equation 3 and 4, we can find maxd , the extended maximum transmission distance for the current node. Based on this maxd 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 calculated result maxd and given D0 (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 number of times the packet needs to be sent in order to be received at least once with a probability 0p . As an example, we set ,999.00 =p maxn =10, and then we have 04617.1 Dd ? ( 0max 4617.1 Dd = ), which means if the distance between two nodes is less than 04617.1 D , a packet sent by one node can be received by another node with a probability no less than 0p if it is sent out n times, where 10?n . In summary, our model can be described as below: Let d denotes the distance between two nodes, if 41 1. 0Dd ? , 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 )(dEe = , the larger the value of d , the larger the value of e . 2. 0max Ddd >> , the packet sent by one node can only be received by another node with a probability p, 10 << p . The energy cost to send the packet is )( 0DEe = , i.e. the battery works at its largest power. To make the information be received with a probability 0p (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 find how many times the packet needs to be sent (Equation 2). If the packet is sent n times, then the energy cost is )( 0DnEe = . For our example, if we set 10?n , then all the nodes within the range of 04617.1 Dd ? can all be regarded as the neighbors of a node. 3. maxdd > , the packet sent by one node cannot be received by neighboring nodes. This means p=0. Figure 4.2 shows an example of a wireless sensor network. 50 nodes are randomly distributed in an area of 50?50 m. S is the source node and T is the destination node. If a packet can be sent only when 10?d , then all the packets from S to T must pass node A and B, 8.9=ABd m. If one of the two nodes runs out of energy, then the network has to die. However, since 1.10=AEd m, 6.13=ADd m, 2.11=CDd m and 0.12=AEd m, then according to our modification, all these node pairs can be selected in a routing path. 42 0 1 0 2 0 3 0 4 0 5 00 1 0 2 0 3 0 4 0 5 0 S T A B C D E Figure 4.2 An Example Network In 50m?50m Area For example, using Equation 4, the transmission probability 9803.0=AEp , if a packet is sent twice from A to E, then it will be received by E at least with a probability 0.9996. Of course, more energy cost will be required by this approach since a packet is sent twice. However the advantage is that more nodes can participate in the transmission. Thus the problem that a few nodes are used heavily while most nodes are not used at all 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 the system is increased. 4.7 MREPE and MREPC In order to improve the performance of original MREP, we propose two modified MREP algorithms [61]. They are MREP Extension (MREPE) and MREP Combination (MREPC). 43 4.7.1 MREP Extension Execute the following steps: First, calculate the maximum extended distance and define the range of the extended neighborhood. With the application-defined P0 (the least receiving success rate) and maxn (maximum number of transmissions), maxd (extended maximum distance between two nodes) can be derived. In this way, the neighborhood can be defined as the nodes within the range of maxd . As an example, we set P0 =0.999, maxn =10, and then we have maxd =1.4617D0, which means if the node is in the range of 1.4617D0, 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 algorithms based on pseudocode given in [28]. Modified Dijkstra?s algorithm is implemented here to get optimal maximum bottleneck paths (Maximum Residual Energy Path). The operation of this algorithm is as follows. Starting from the source node, for each node (or parent node) in the network, after transmission compares its bottleneck energy value (the minimum residual energy value of all the ancestor nodes) with the residual energy value of each its neighbor (child node), and put the minimum of the two as the bottleneck value of the corresponding child node. All the children nodes of each parents, select the node with maximum bottleneck energy value and add it in the optimal path. Third, check the distance to the node with Maximum Residual Energy. If it is larger than D0, but still smaller than dmax, then with its d value, calculate the n value. Retransmit n-1 times to compensate for the packet loss due to the long distance. 44 Continue the path selection from the chosen node, check its neighboring nodes and ignore the nodes not being selected until the destination node is reached. See Figure 4.3A-C 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 to the mathematical model. In the examples, the routing path selection algorithm is the same as the original MREP. The difference is that in MREPE, there may be some legal paths that may not be legal in MREP. For example, A->G->I->L in Figure 4.3A, N->S->Sink in Figure 4.3B and B->J- >N->Q in Figure 4.3C are legal paths in MREPE but not in 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.3C, only the MREPE can work well since neighbor nodes are always far away and no close neighbors have enough energy. 4.7.2 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 following steps show how this model works. First, the algorithm works the same as the original MREP. Find the nodes with the Maximum Residual Energy. 45 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 paths selection, the node will die after the transmission or no transmission can be done due to energy depletion. In this way, system lifetime can be increase by the participation of MREPE. 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.3A Work Mechanism of MREPE 46 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.3 B. Work Mechanism of MREPE Figure 4.3 C. Work Mechanism of MREPE 4.8 Summary In this chapter, we analyze energy efficient routing. The conclusion is that the broadcasting in the entire network is so expensive because it not only wastes energy, but 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 47 also involves excessive traffic. So it is wise to avoid broadcasting by adopting local unicast communication. Our strategy in this research work is to find the routing path based on alternative mathematic models of energy efficiency. By investigating previous research work done by [27, 28], 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 transmission distance between two nodes, we enable more nodes in the network to participate in the transmission. This avoids the unfortunate situation where most of nodes in the network still have lots of energy left when some nodes die and there is no path available. By retransmitting the same packet multiple times, both extended maximum transmission distance and low packet loss can be guaranteed at the same time. Using application-defined parameters, it is easy to compute the number of transmissions required. In this way, energy usage in the whole network is balanced. 48 CHAPTER 5 PERFORMANCE EVALUATION 5.1 Introduction In the previous chapter, we analyze the major reason for the limitation of system life is unbalanced energy usage. Based on the original MREP algorithm, we provide solutions to the problem, they are MREP Extension and MREP Combination. This chapter reports some performance results and analysis for both two dimensional and three dimensional network topologies, 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)?. This chapter describes our simulation schemes, test methodologies and compares the performance. We also have results on the number of transmissions and retransmission energy cost. 5.2 Experimental Setting and Assumptions To compare the performance of our algorithms with the original MREP, we took some of the experimental parameters from [28]. No matter it is a two dimensional or three dimensional network topology, all the experimental setting are the same except the node density ranges. The experiments are conducted on random networks. There are always 50 49 nodes randomly generated and distributed in a square of 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 Figure 5.1 Illustration of Uniform Traffic Fields values. All the experiments are done under the assumption that the maximum transmission range ( 0D ) of each node is 10 m for application-defined receiving rate to be 99.9%. The energy expenditure model for one bit transmission is: ),/(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 6105? nJ is applied to all the experiments regardless whether the network is sparse or dense. However, simulations showed that less initial energy does not affect the performance comparisons. Our assumption is that the packet size is fixed at 600 bits. Traffic is uniformly distributed among all source-destination pairs. Each result in each run is based on twenty randomly generated sample network topology graphs. 0 1 2 3 4 5 0 1 2 3 4 5 S T A B C D E 50 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 important; it is the difference between the results that indicate the relative performance of each routing algorithm makes a great deal on the evaluation. 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 is measured by 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 system lifetime (this is in terms of time), in our experiments, we translate this into the 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 [28] 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 51 more valid packets sent indicates the longer system lifetime and more efficient the algorithm is. In two dimensional routing scenario, 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, the longer the system lifetime. The simple reason for this is that a denser network can provide more available paths than a sparser one, so that it can improve the energy distribution of whole network. If an algorithm performs well under sparse network, it can certainly perform well under dense network. The trend of MREP and MREPE in Figure 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 in each experiment. 5.4.2 Remaining Energy Another evaluation metric we used is remaining energy, which is defined as the total residual energy value of all nodes in the network when the system is dead. High remaining energy level at system death does not necessarily mean a better result of algorithm since there is still much 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 two dimensional scenario, a 50 ? 50 sparse area, with 50 randomly created nodes for 20 runs of experiments. From this typical case, we can tell 52 Figure 5.2 System lifetime Comparisons Under 50m?50 m Network Density that in two dimensional scenario, our MREPE algorithm always has much lower energy left than the original MREP. The reason behind this result is that our MREPE always extends the range of neighborhood and 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 difference in the level of energy left. MREPE remaining energy is much lower than that of MREP. We can conclude that in MREPE, the remaining energy is used to prolong system lifetime, since there are always tradeoff between the remaining energy level and system lifetime. Sometime, in order to increase system lifetime, we have to consume of the remaining system energy. Our experiment shows that average system residual energy for MREPE is decreased by 50% compared to the original MREP. 0 5 10 15 20 0 500 1000 1500 2000 2500 3000 3500 4000 4500 MREP MREPE Times of Run Sy ste m Li fet im e 53 Figure 5.3 Residual Energy Level Comparisons Under 50m?50 m Network Density 5.4.3 Network Density We investigate the performance of algorithms under different network density. 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. 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, a sparse network has higher possibility of the 0 5E6 MREP MREPE 3E6 2E6 1E6 4E6 0 5 10 15 20 Times of Run Re sid ua l E ne rg y L ev el 54 unavailable path than a dense network. This 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 a 35?35 area, the distance between nodes is relatively short. There are more close nodes pairs, which mean more legal paths available. This helps prolong the system lifetime. Figure 5.4 Average System Lifetime under Different Density In Figure 5.4, we compare the results of the average system lifetimes of the three algorithms under different densities which range 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 a little advantage over MREPC under certain network densities, such as, 35 ? 35 and 55 ? 55 in Figure 5.4. Our 0 1000 2000 3000 4000 5000 6000 7000 35 40 45 50 55 MREP MREPE MREPC Size of Network Area Av era ge Sy ste m life tim e 55 experiment shows that the average system lifetime under different densities can be increased by 20~30% in both MREPE and MREPC compared to the original MREP. Figure 5.5 Average Remaining Energy under Different Density Fig 5.5 shows that the sparser the network is, the more energy is left when system dies. One reason for this result may be that in sparser networks, there are fewer paths 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 densities, our new algorithms perform better than the original MREP in terms of both system residual energy and system lifetime. Since network density plays an important role in routing algorithm performance, if an algorithm works better than other algorithms in the sparse networks, it will certainly work better in 0% 10% 20% 30% 40% 50% 60% 70% 80% 90% 35 40 45 50 55 MREP MREPE MREPC Size of Network Area Av era ge R em ain ing E ne rg y R ate 56 dense networks. MREPE performs much better in sparser networks than the original MREP, so that we do not need to test its performance under very denser networks. In the real underwater acoustic sensor networks, the acoustic sensors are very expensive. It is economic and efficient to deploy the acoustic sensors as sparse as possible as long as the normal transmission and sensing can be guaranteed. In this way, our MREPE algorithm will show much more advantageous over original MREP algorithm. 5.4.4 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 the 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 retransmission and 27% of them by two retransmissions. From the statistical results, we can tell that most (about 34%) packets are sent with one retransmission, while very few (about 5%) packets are sent through five retransmissions. The reason we did the experiment in sparse network is that sparse network is the worst case. Retransmission results of dense networks will be much better than this. The question is how much energy is actually used for retransmission. The next section will give answer to the question. 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 ends. Table 5.1 shows the retransmission energy cost rate of MREPE. We analyze the statistic data from 57 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 packets sent without retransmission. Table 5.1 shows that with the increase in sparseness, the rate of retransmission energy cost increases accordingly. This means the average retransmission energy cost rate is proportional to sparseness of network density. The reason behind this fact is that in sparse network, the distance between nodes is longer. MREPE shows its advantage by transmitting to the far away neighbors as well as guaranteeing the QOS by the means of retransmissions. However, with the same sparse network, for some cases, the original MREP cannot find valid paths including two neighboring nodes with long distance. 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 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 sparse network densities. Whether in sparse networks, our protocol can still work as well as in dense ones really depends on quality of long distance transmission and retransmissions. 58 Figure 5.6 Number of retransmission vs. packets in MREPE 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 100 200 300 400 500 600 Number of Retransmission Nu mb er of Pa ck ets 59 Figure 5.7 Percentage of Total Number of Packets vs Number of Retransmission Packets in MREPE 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 optimization 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 comparisons, we can conclude that SA cannot compete with MREP in the energy efficient routing problem. It is difficult to find another algorithm to perform much better than MREP in the energy efficient optimal problem. Thus, basing on MREP, and making efforts to improving performance of MREP using a different mathematical model becomes the goal of this study. 18% 34%27% 11% 8% 2% 0 1 2 3 4 5 Number of Retransmissions 60 Figure 5.8 System Lifetime Comparisons with SA Figure 5.9 Residual Energy Level Comparisons with SA 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 1 2 3 4 5 6 7 8 9 10 Number of Run Re sid ua l E ne rg y U nt il sy st em d ea th MREP SA 61 5.6 Three Dimensional Networks In the previous sections, we provide comprehensive analysis about the performance evaluations of energy efficient routing protocols (MREPE and MREPC) in two dimensional networks. We can draw the conclusion that in two dimensional network topology the modified MREP algorithms have shown their advantages over original MREP in a variety of aspects. The key idea of modified MREP is to uniformly distribute energy usage by extending the neighborhood. Dimension change from two to three cannot lead to a big influence on neighborhood extension. So the overall performance will not have a big difference between three dimensional energy efficient routing and two dimensional energy efficient routing. The research work mainly focuses on the improvement of system lifetime, thus we only test the modified MREP algorithms with system lifetime under the three dimensional networks scenario, which is the most convincing metric of all. However, in three dimension networks, it is difficult to generate a feasible topology in very sparse node density, since it is impossible for some nodes to be reached by any other nodes. To capture major tendencies of system lifetime under different node densities and collect most valuable data, three dimensional networks energy efficient routing node densities range differently from two dimensional networks. The simulation results in Figure 5.10, the node densities range from 30 30? 30? to 50 50? 50? . From Figure 5.10, it is obvious that both MREPC and MREPE perform better than original MREP in term of average system lifetime under all node densities. However, between MREPC and MREPE there is only slight difference under different node densities. MREPC demonstrates its advantage over MREPE only under extremely high node density, such as in 30 30? 30? . It is obvious that when modified MREP 62 algorithms are applied to three dimensional networks topology, they can still produce satisfactory results in term of system lifetime. Figure 5.10 Average System Lifetime under Different Node Densities in 3D Network Topology 5.7. Summary The performance of MREPE, MREPC and MREP are compared and evaluated in detail in sparse and dense networks in both two dimensional and three dimensional networks scenarios. In all cases, MREPE and MREPC are energy efficient, even under the sparse networks. The special characters of underwater acoustic sensor networks make the deployment of the acoustic sensors sparse. The advantage of our algorithms over original MREP will benefit underwater acoustic sensor networks application a lot. Both MREPE and MREPC make good use of the system remaining energy, so that the total system lifetime is increased and more valid packets can be sent before the system dies. 63 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 packets are sent successfully by 1 or 2 retransmissions, and very few packets are sent with 5 retransmissions or more. 64 CHAPTER 6 DETOURING ROUTING TREE 6.1. Background Underwater acoustic networks [31], [3] are special types of wireless sensor networks used by various applications such as ocean environment monitoring, tactical military surveillance, target tracking, and undersea navigation [33]. Due to the demand of some real-time applications and the likelihood of nodal failure in erosive underwater environment, it is preferred that the data collected by individual sensor nodes sent to the control center in a multi-hop fashion [34].To accomplish this task, many research issues, such as the need of a robust coding scheme that can combat time-varying multipath intersymbol interferences and Doppler shifts and spreads [35], and a reliable and efficient media access control [36] over the unreliable acoustic links with long propagation delay, will have to be properly addressed. In this research, we also focus on the issue of three- dimensional routing in underwater acoustic sensor networks. The traditional routing algorithms in wireless sensor networks can be classified into proactive and reactive routing protocols. In proactive routing protocols [37], [38], each node maintains a routing table by actively exchanging link state or distance vector control packets among nodes. The advantage of proactive routing is that the routing table allows each node to quickly identify the next hop of a packet. In addition, different metrics, including hop count, available bandwidth, and congestion status, can be incorporated into 65 the construction of the routing table [38]. The major disadvantage of proactive routing, however, is that the communication and storage overhead of routing table maintenance grows quickly as the size of the network increases. In reactive routing protocols [39], [40], a node floods the network with query to search for a route to the destination when it has a packet to send. The primary difference between these reactive routing protocols is how the path information is cached and reused. While reactive routing avoids the overhead incurred by routing table maintenance, the network-wide flooding introduced in the path discovery is an extremely expensive operation and may create additional problems, such as the infamous broadcast storm problem [41]. We conclude that, while these proactive and reactive routing protocols do not rely on special assumptions of the network topology and link model, they tend to incur heavy communication and storage overhead especially when they are adopted for resource-constraint underwater acoustic sensor networks. 6.2 Geographic Routing In recent years, a new class of routing protocols ? geographic routing [42]?[45] - have been proposed. Under the assumption that each node knows the geographic locations of itself, its neighbors, and the destination, geographic routing can determine where to forward a packet without the need of routing table maintenance and flooding mechanism. While GPS signal is not available under the surface of the ocean, the relative location of each undersea sensor node can be computed via the exchanges of acoustic beacons between neighbors in a manner similar to [51]. In general, geographic routing consists of two parts - greedy forwarding and detouring strategy. If a node holding a packet finds some better neighbors within its own proximity, 66 the node forwards the packet to the best one. This is referred to as greedy forwarding. Note that greedy forwarding alone has a low delivery rate even in a connected network. When a local minimum is reached (i.e., no better neighbor can be found), each geographic routing protocol falls back to its own detouring strategy to recover the packet by finding a detour to leave the local minimum and then move toward the destination. In underwater acoustic sensor networks routing, it is more significant to build up some robust routing protocols to deal with the dead end cases. This is because acoustic sensor networks transmission will deplete energy quicker than ordinary sensor networks. Besides this, it is more difficult to recharge or replace the battery of underwater sensors. When certain nodes are out of battery, the void areas show up in the networks. This case is more common in the underwater sensor networks. So, it is necessary to create some routing methodologies which can detour out of the void area as effectively as possible, so that the system lifetime can be prolonged. Without the help of routing tables, most of the existing non-flooding detouring strategies first reduce the original network topology to a planar graph by dropping some edges and then apply one of the heuristics (e.g., perimeter routing [43], face routing [44]) to explore the network via the links in the planar graph. Compared with traditional proactive and reactive protocols, these planer graph-based geographic routing protocols tend to create relatively lower overhead and have been suggested in [31], [34] to be adopted for underwater acoustic sensor networks. However, the criteria and performance analysis of geographical routing [31]?[34] have been proposed in recent years used for ad hoc and sensor networks. It makes good a use of localized geographical location information to route the traffic, and thus is able to avoid most of the communication and 67 storage overhead experienced by the proactive and reactive routing protocols [35], [36]. In general, geographic routing forwards a packet in a greedy manner when possible. Each packet is stamped with the positions of its destination; all nodes in the network are assumed to know their own positions; and a node forwards a packet to its neighbor that is geographically closest to the destination, as long as that neighbor is closer to the destination. Local minimum may exist where no neighbor is closer to the destination. In such cases, greedy forwarding would fail, and a detouring strategy must be applied to continue making progress toward the destination. 6.2.1. Detouring Strategies with Planarization Different geographical routing protocols have different detouring strategies. In [31], flooding is used to find a detour when a packet reaches a local minimum. This detouring strategy is expensive and not preferable, especially when it comes to networks of large scale. Theoretically, geographic face routing algorithm, which is non-flooding detouring, such as in [3], [33], the network topology is first reduced to a planar graph distributively [37], [38], and then a certain heuristic traversal is applied on the planar graph to find a detour. In fact, the nodes in the network are traversed in the fashion that no loop is repeated. As long as the traverse does not repeat loops and the network is connected, eventually the destination will be reached. Although it is known to be extremely hard to guarantee this no-repeated-loop property without the global knowledge for an arbitrary network topology, there are still several heuristics to achieve this guarantee when the topology is a planar graph. As a result, most non-flooding detouring strategies first reduce the original network topology to a planar graph by dropping some edges and then apply one of the heuristics to explore the network without repeated loops. However, this 68 is the main reason why the resulting detour has large number of hops. This detouring strategy has an edge over flooding in terms of the communication overhead, but it requires several impractical assumptions to work correctly, such as the unit disk link model and a flat network topology. Unit disk link is often violated in practice because of obstacles and the physical characteristics of real radios [41]. Further more, errors in the location of the nodes can also cause planarization to fail [49, 50]. To avoid the main obstacles in the detouring strategy above, a major breakthrough was made by Kim et al. in developing the Cross-Link Detection Protocol (CLDP) [42], which produces a subgraph on which face-routing-based algorithms are guaranteed to work correctly. Their key insight is that starting from a connected graph, nodes can independently probe each of their links using a right-hand rule to determine if the link crosses another link in the network. CLDP uses a two-phase locking protocol to ensure that no more than one link is removed at any time from any given face; in this way it guarantees that the removal of a crossed link will not disconnect the network. Though CLDP is able to planarize an arbitrary graph, every single link in the network has to be probed multiple times, and has a high cost. While distributed planarization is now a solved problem, the high maintenance costs and complexities associated with the deployment of face routing algorithms (with CLDP) make it worthwhile to consider an alternative approach to face routing. In particular, since we know that geographic routing tends to work best when packets are forwarded greedily [44], a natural approach would be to consider a backup routing mode that does not require the use of a planar graph and hence allows us to avoid the planarization problem altogether [44]. The hypothesis is that a geographic routing algorithm that does 69 not require planarization would be able to avoid the associated costs of planarization and hence make geographic routing less costly and more practical. 6.2.2. Detouring Strategies without Planarization As described in [58], in computational geometry, it is common to use the term "convex hull" for the boundary of the minimal convex set containing a given non-empty finite set of points in the plane. The convex hull for a set of points is the minimal convex polygon that contains all the points; it is minimal because the convex hull will be contained in any convex polygon that contains the given points. As proposed in [59], convex hull contains the locations of all its descendant nodes. A hull tree is a spanning tree where each node has an associated convex hull. In general, it restricts the search problem to a small subtree of the full spanning tree for a given destination. This is because it provides a way of aggregating location information and they are built by aggregating convex hull information up the tree. This information is used in routing to avoid paths that are not productive; instead we traverse a significantly reduced subtree, consisting of only the nodes with convex hulls containing the destination point. Each node in a basic hull tree stores information about the convex hulls that contain the coordinates of all the nodes in subtrees associated with each of its child nodes. The convex hull information is aggregated up the tree. Each node computes its convex hull from the union of its coordinate and the points on the convex hulls of all its child nodes, and this information is communicated to the parent node. Consequently, the convex hull associated with the root node is the convex hull of the entire network and contains all the nodes in the network. 70 Figure 6.1 Packet Forwarding Using Convex Hull (To the Child Node) See Figure 6.1 as one example of the convex hull application in routing. Node C receives packet P, and looks up the convex hulls information. And then plug the packet P?s location information into convex hull1, convex hull2, and convex hull3 respectively. It finds that packet P? location information is included in convex hull2. This is the reason that it will forward packet P to its child node L. In this way, routing process has been made more efficient by choosing the correct routing direction closer to the destination. Figure 6.2 can be another example to show how convex hull works in routing. Node C receives another packet G. Node C looks up all of its children?s convex hulls information. Since it cannot find one convex hull which can include packet G?s location, thus, it has to forward this packet G to its parent node R and let the upper level nodes in the tree make the routing decision. This is because the upper level the node is, the more global information about the whole tree it has. This is another ideal case of convex hulls? advantage in routing. P L M N P R B C G I K H A D F 1 2 3 71 Figure 6.2 Packet Forwarding Using Convex Hull (To the Parent Node) However, in some special cases, such as the one shown in Figure 6.3, the thing is totally different from the ideal case. Nodes are distributed around the void area. Based on some scenario, routing tree is constructed and the convex hull1 and convex hull2 are figured out. However convex hull1 and convex hull2 have an overlap node, which is node I in Figure 6.3. This intersection of two or more convex hulls is called conflicting convex hull. This overlap leads to the ambiguity in the routing process. As shown in the figure above, when node A receives packet Q, it searches both its children?s convex hulls. It finds packet Q?s information has been included in both children?s convex hulls. This is difficult for routing decisions because conflicting convex hulls might be misleading to the routing process. Though both convex hulls include the destination location, it is hard to tell which one is really linked or connected to the destination. G L M N P R B C G I K H A E D F 72 Figure 6.3 Conflicting Convex Hulls In this way, convex hulls lose their functionalities in improvement of routing process. This disadvantage can be avoided as much as possible by changing the scenario of routing tree construction and paying attention to the distant factor in the routing tree construction. In fact, the key purpose of the hulls in the hull tree is to maintain a summary of the area that contains the points in each subtree. The reason we choose to use convex hulls is it turns out that the convex hull is a relatively compact representation for a set of points and it is relatively easy to perform mathematical computations, such as the checking of Q A B C D E F G I J K L M Void ? ? ?? 1 2 73 containment of points and finding intersections. It is plausible to use non-convex hulls or other shapes like circles and ellipses to summarize the regions covered by each subtree. 6.3 Detouring Routing Tree From the characteristics of geographic routing algorithm, we can see that it tends to be most efficient when packets are forwarded greedily as much as possible [60], since greedy forwarding avoids switching to the costly guaranteed-delivery forwarding mode. Also, as the density of nodes in the network increases, the shortest path between pairs of nodes corresponds increasingly to the Euclidean straight line between them. Another characteristic is that concave voids in the routing topology are harmful for geographic routing since packets will tend to end up in the concave dead ends. This characteristic prompted us to explore the hypothesis that we can improve routing performance by choosing virtual coordinates that increase the success rate of greedy forwarding. GDSTR in [34] is a new routing approach that avoids the need for planarization by using trees to route around voids. It is based on the idea that virtual coordinates which allow greedy forwarding to succeed more often will indeed improve the routing performance of existing geographic routing algorithms. To aggregate geographic information, they use a new kind of spanning tree, called a hull tree, where each node maintains information about the points that can be reached below it in the tree. Hull trees are much cheaper to build initially and to maintain in a distributed environment than a planar graph. When a packet reaches a local minimum, it is forwarded to the child node whose convex hull contains the location of the destination. If no such child is available, the packet is forwarded to the parent node. If multiple children?s convex hulls contain the location of the destination, they will be exploited in turn until a node closer to the 74 destination than the current local minimum is found, where the greedy forwarding takes over again. The routing tree detouring strategy does not rely on impractical assumptions and has been shown in [34] to perform well compared to the other geographical routing protocols [3],[33]. However, the success of the tree-based detouring largely depends on the quality of the pre-constructed tree. If there are many overlapped convex hulls (i.e., conflicting hulls) among siblings, the routing performance will likely to be low. In [34], several different types of routing trees are studied and the minimum path tree is suggested to be a better choice. However, in their study, the root of a tree is always fixed. This places a serious constraint to the construction of the tree. Without knowing the locations of nodes in the tree, a bad selection of the root can easily lead to a large number of conflicting hulls. Additionally, the traffic pattern of the network is not taken into account in their study. In the case if two geographically close nodes with a high traffic volume between them are placed logically far apart in the tree, it is likely to create bottlenecks in the routing tree. In this research, we proposed two kinds of geographic routing without Planarization methods, they are Traffic-Aware Routing Tree (TART) [62] and Energy-Aware Routing Tree (EART). Unlike existing routing trees, both routing trees are constructed completely in a distributed bottom-up fashion. This allows the number of conflicting hulls to be reduced significantly. In addition, the traffic pattern of the network and residual energy level are considered in the tree constructions respectively. This helps remove the bottleneck of the tree routing. The totally distributed fashion of routing tree construction makes message exchanges locally, so that no flooding is conducted among the whole 75 networks and no global information is necessary. The simulation results show that both routing trees rarely encounter the situation of conflicting convex hulls, have fewer average path length compared against other routing trees, higher average path throughput and average path residual energy level. In the following sections, we discuss the related work of this research and then present the main design and report a set of simulation results and its evaluation analysis to draw the conclusion and give the future work. 6.4 Routing Tree Algorithms 6.4.1 Search Trees In the routing tree detouring strategy, data packets are delivered toward their destinations along a path in the preconstructed tree topology. The depth-first search (DFS) and the breadth-first search (BFS) are two principal algorithms to traverse a connected network and to create the routing trees [35]. In the DFS algorithm, the starting point of traversal becomes the root of the tree. At each step of the traversal, DFS visits neighboring unvisited nodes as deep as possible until no such node is available. Whenever a new unvisited node is reached for the first time, it is attached as a child to the node from which it is being reached. If there are multiple such unvisited nodes, a tie can be resolved arbitrarily. This process continues until a dead end, i.e., a node without adjacent unvisited node, is encountered. At a dead end, the tree construction method backs up one link to the node where it came from and tries to continue visiting the unvisited node from there. Eventually, it halts after backing up to the starting node, with the latter being a dead end. By then, all the nodes in the same connected components as the starting node have been visited. 76 The BFS algorithm, on the other hand, visits the neighboring unvisited nodes as wide as possible until no such node is available. It proceeds in a concentric manner by first visiting all the nodes that are adjacent to the starting node, then all unvisited nodes two links apart from it, and so on, until all the nodes in the same connected component as the starting node are visited. While DFS tries going as far as it can, BFS tries exhausting the neighborhood first. The results of these traversals are the DFS trees and the BFS trees. Both DFS and BFS trees provide a route to reach every node in the network. DFS trees are not so balanced that some nodes have more children than others. However, the subtrees in the DFS trees are more compacted than BFS tree. While, the BFS Trees have shorter height and fatter subtrees than the DFS tree. In this way BFS trees introduce more convex hull overlaps among the sibling subtrees, which lead to ambiguity in geographic routing based on the preconstructed tree. From the traffic load balanced point of view, though there is no traffic weight concern in both of the tree construction methods, the natural attributes of relatively lower height and wider subtree distribution of BFS trees may be more beneficial to the traffic distribution unintentionally in tree based geographic routing. 6.4.2 Minimum Spanning Trees A spanning tree of a connected network is defined as a tree that contains all the nodes in the network without cycles. Clearly, both DFS and BFS trees are spanning trees of the original network. While a network can have many spanning trees, among them, a minimum spanning tree has the smallest total weight of links among all spanning trees of the network. The minimum spanning tree for a network can be constructed by using either the Prim?s or the Kruskal?s algorithm [35]. The methodology of construction of 77 MST can be regarded as a kind of greedy algorithm. The greedy idea of weight selection during the construction process of MST can be applied to build the routing tree with multiple metrics consideration. If additional nodes and links may be added in the process of constructing the minimum spanning tree, the total weight can be further reduced. The result is called a Steiner tree [35]. Similar to the minimum spanning tree, the Steiner Tree is a kind of greedy algorithm: given a set of nodes, interconnect them by a network of shortest path, where the path is the sum of the lengths of all links. The difference between the Steiner tree and the minimum spanning tree is that, in the Steiner tree, extra intermediate vertices and edges may be added in order to reduce the length of the spanning tree. It has been proved that the resulting connection is a tree, known as the Steiner tree. There may be several Steiner trees for a given set of initial vertices. Most of the Steiner trees are NP- complete, i.e. thought to be computationally hard. Some restricted cases can be solved in polynomial time. In practice, heuristics are used. Though Steiner Tree has the same contribution to the traffic load awared routing, it is difficult to construct. So it is not a good idea to apply it in routing protocol design. 6.4.3 Minimum Path Trees Minimum Path Tree has a goal of building a tree that minimizes overlap among the convex hulls of different branches. Such kind of spanning tree has the fixed root, which is at the extreme end of the network. When building the tree, each node chooses the neighbor with the minimum number of hops to the root as its parent. If a node has a choice between multiple neighboring nodes that have same number of hops from the root, the geographical closest node will be chosen. The shorter links in the tree construction 78 process reduce the occurrences of crossing links, and result in a tree with subtrees that are more clustered together, thereby reducing the probability of intersections between convex hulls and creating fewer conflict hulls. However, one of the disadvantages of the minimum path tree is that the root is pre-selected without knowing the locations of the nodes in the network. This puts a serious constraint in the tree construction. In case if the root is poorly chosen, it may lead to a large number of conflicting hulls. Another disadvantage of such tree is that when the network density is high, some intermediate nodes may end up with a large number of children thus more conflict hulls show up. Though the motivation of Minimum Path Tree construction methodology comes from minimization of interleaving of sibling subtrees, it does not care about the traffic load factor at all. From these aspects, it cannot be the best routing tree construction algorithm for the geographic routing. The above tree construction methods all follow the top-down approach. They usually require centralized knowledge about the entire network, and therefore are difficult to develop a distributed algorithm to construct the trees. In practice, the centralized algorithms are implemented by sending information from all nodes to a centralized node, and then disseminating the decision to the entire network. This normally involves intensive message exchanges and may cause bottlenecks and low reliability. Clearly, distributed algorithms are more preferred in practice. In addition, these methods construct the trees according to the node locations, but do not consider the traffic of the network. Therefore, some links may be congested because the tree is not constructed with the full use of traffic knowledge. Consequently, the resulting routing will not be optimal. In the following, we will develop a greedy spanning tree construction algorithm that considers 79 both the location and the traffic pattern in the network with the intention to minimize the number of the conflicting hulls and balance the traffic load of the network. 6.5 Algorithm Description As described in previous section, the existing routing trees suffer from a number of issues that will cause the tree construction as well as the tree routing to be inefficient. To address them, we propose two kinds of bottom-up tree construction methods for three dimensional routing in underwater acoustic sensor networks. One is distributed, the other is centralized. The centralized routing tree algorithm can be applied to the small scale networks or inner cluster routing. The distributed routing algorithm can be applied to large scale networks. The routing tree, weather centralized or distributed, we assume that each node learns the virtual bandwidth and residual energy level to each of its neighbors from the past history record. Another assumption is that the sink and source pairs are fixed with constant transmission rates during each time period. It is obvious to see that the routing tree can adapt to the slow changes of the network conditions, but not too frequent changes. So in this way, we can guarantee the validity of routing tree in each time period. For the next time period, some network parameters, such as traffic pattern, source and sink pairs, transmission rates and residual energy level change, which will lead to the change of routing tree accordingly. Thus for each time period, it is necessary to construct the routing tree according to updated network information. How long is each time period depends on different applications. This is out of the scope of our research. The notations and terms used for the remainder of the research are defined as follows. A cluster is defined to be a set of nodes. Each cluster has a cluster head (or simply head if no confusion is caused), and each node belongs to exactly one cluster. The center of a 80 cluster is defined to be the geometric center of the cluster. The distance between two clusters C1 and C2, denoted as dist (C1, C2), is defined as the Euclidean distance between their centers. Two clusters are said to be neighboring clusters if at least one node in the first cluster is a neighbor of a node in the second cluster. Notice that in our definition the distance between neighboring clusters can be greater than the transmission range of a node. To demonstrate the basic idea of the detouring routing tree construction algorithm, let us start from Traffic Aware Routing Tree construction. In order to take into account the traffic factor, we assume each node learns the average available bandwidth to each of its neighbors from the past traffic history. The virtual bandwidth between two neighboring clusters C1 and C2, denoted as bandwidth(C1,C2), is defined as the sum of all available bandwidth between nodes of two clusters. Notice that the virtual bandwidth between two neighboring clusters is an approximation to the actual average available bandwidth between them. The reason to use the virtual bandwidth instead of the actual average available bandwidth is because it requires much lower computational and communication overhead to compute the virtual bandwidth after the merge of clusters. For instance, in Fig.6.4, the cluster with head P has two neighboring clusters. The virtual bandwidth between the cluster with head P and the one with head Q is the sum of the bandwidth between neighboring pairs (A, X), (B, Y), and (C, Y). The size of a cluster C is the number of nodes in C, and is denoted as |C|. The head of a cluster maintains the cluster information, including the center of the cluster, the size of the cluster, and the virtual bandwidth as well as the link with the largest average available bandwidth to each neighboring cluster. 81 Figure 6.4 Example of Clusters and Traffic Between Clusters The basic idea of detouring routing tree algorithm is that each pair of neighboring clusters has a gravity, which is computed according to a gravity function. There are two kinds of gravity functions, one is Traffic Aware Routing Tree gravity function and the other is Energy Aware Routing Tree gravity function. For Traffic-Aware Routing Tree, the gravity function is composed of the distance and virtual bandwidth between them. For Energy-Aware Routing Tree, the gravity function includes the distance and residual energy levels between two clusters. The stronger the gravity between two clusters, the higher the probability they will be merged into one cluster. This process is repeated until there is only one cluster left or no gravity between any pair of neighboring clusters. As shown in Figure 6.5, nodes are distributed around void area, initially, each node is treated Cluster Head A X B Y C Cluster Member P Q R 82 as a one-node cluster, the target cluster is set to be the neighbor with the strongest gravity to the node itself. As shown in Figure 6.6 and Figure 6.7 with the development of cluster combination, more clusters show up, each newly built cluster includes cluster head and its members. From Figure 6.8, it is obvious that in this bottom up routing tree construction fashion, the very last node to be added to the routing tree will be the root of the tree, while the first node in the tree is definitely the leaf node. For traffic aware routing tree, in this way, the heavier traffic flows are bonded to the lower level of the routing tree and avoid being routed to the root each time in certain extent. Figure 6.5 Initial Stage of Tree Construction 83 Figure 6.6 Intermediate Stage of Tree Construction From Figure 6.6-Figure 6.8, we can easily see that the head of the larger cluster becomes the head of the merged cluster, and the head of the smaller cluster turns into a regular cluster member. In each merge, the link with the highest traffic volume between two original clusters is the link to connect those two clusters. It is not difficult to see that this process will introduce n ? 1 links to connect n number of nodes. In other words, the result of the algorithm will naturally form a tree. Every time, two neighboring clusters with the maximum gravity function value will be combined together. After updating the information of corresponding clusters, a new pair of neighboring clusters combination begins. The iterative will continue until all of the clusters are included to the routing tree. 84 Figure 6.7 Intermediate Stage of Tree Construction Figure 6.8 Final Stage of Tree Construction 85 Figure 6.9 Routing Tree Without Conflicting Convex Hulls Figure 6.9 shows the convex hulls based on our detouring tree construction algorithm. Because our routing tree algorithm takes into account of the distance between two neighboring clusters during the clusters combinations, the number of conflicting convex hulls is greatly reduced, such as in Figure 6.9, there is no conflicting convex hull at all. The main idea of the Distributed Traffic-Aware Routing Tree algorithm is that each pair of neighboring clusters has gravity, which is the same with the centralized algorithm. It can be computed according to a function of the distance and bandwidth between them. The information between neighboring clusters pairs can be gained by periodically exchanging messages locally. The stronger gravity two clusters have between them, the sooner they will be merged into one cluster, which is controlled by their timers. Each individual cluster has the cluster head and timer, so that it can switch between the different states and make decision of cluster merging locally without global information. 86 This process is repeated until there is only one cluster left or no gravity between any pair of neighboring clusters. There are four states for each individual cluster: comparing, requested, responded, and committed. To form the distributed Traffic-Aware Routing Tree, each cluster head runs the Distributed Traffic-Aware Routing Tree Algorithm stated below: DISTRIBUTED TRAFFIC-AWARE ROUTING TREE ALGORITHM /* The cluster head of a cluster C runs the following */ if |C| = 1 { // Initialization compute the gravity Gi to its neighboring clusters Ci find the largest gravity iiT GG ?= max set target cluster as TC and timer T as TGT /max set state to be comparing } while (true) { if ( state = comparing ) { repeat { reduce timer T value if ( receive an update message from cluster AC ) update information about AC } until ( T expires ) or ( receive a m-request) if ( T expires ) send a m-request to TC and set state to be requested else { set target cluster TC to be the one sending m-request send a m-response to TC and set state to be responded } } else if ( state = requested ) { wait for mergeT for m-response if ( mergeT expires before receiving a response) rollback TC and T, and set state to be comparing else send a commit message and set state to be committed } else if ( state = responded ) { wait for mergeT for the commit message if ( mergeT expires before receiving the commit message) rollback TC and T, and set state to be comparing else set state to be committed 87 } else if ( state = committed ) { if ( |C| < | TC | ) { send cluster info to the cluster head of TC turn into a regular cluster member } else { wait for mergeT for the cluster info from TC if ( mergeT expires before receiving the cluster info ) rollback TC and T, and set state to be comparing else { add a link to connect C and TC compute the gravity Gi to its neighboring clusters Ci find the largest gravity iiT GG ?= max set timer T as TGT /max set state to be comparing } } } } Initially, each node is treated as a one-node cluster, the target cluster is set to be the neighbor with the strongest gravity to the node itself, and the timer is set to be maxT divided by the gravity to the target cluster. When the timer of a cluster head expires, it sends a merge request containing the size of the cluster to the head of its target cluster to solicit a merge response. After exchanging merge request and response, the two cluster heads execute the merge process. The head of the larger cluster becomes the head of the merged cluster, and the head of the smaller cluster submits its cluster information to its new cluster head and turns into a regular cluster member. As in the centralized algorithm, in each merge, the head of the merged cluster includes the link with the highest virtual bandwidth between the two original clusters. It is obvious that this process introduces n ? 1 links to connect n number of nodes at the end. In other words, the distributed algorithm will naturally form a distributed routing tree. Similarly, the virtual bandwidth between the merged cluster and the neighboring clusters can be calculated directly from the virtual bandwidth value of the original 88 clusters to their neighboring clusters. As long as the head of the merged cluster obtains these pieces of information from the original head of the smaller cluster during the merge process, it can then calculate the new gravity to all its neighboring clusters without the need to introduce additional messages. After two clusters merge into one, the head of the merged cluster will have to send an update message to the head of each neighboring cluster containing the size of the merged cluster and the virtual bandwidth between them. A cluster head receiving an update message from a neighboring cluster will update the information about the neighboring cluster, but will not reset its timer if it is in the comparing state. This is to ensure that the timer of a cluster head will eventually expire. It is possible that more than one clusters have their timer expired before their merge process is complete. In this case, there will be multiple concurrent merge requests sent out in the network. If the sender and receiver pairs of these requests are different, these merges can be performed in parallel. Otherwise, the merges have to be performed sequentially to avoid creating inconsistent states. In distributed algorithm demonstrated above, when the head of a cluster intends to merge with its target cluster, it first tries to get the head of the target cluster to agree with the merge. These cluster heads will go through a process similar to the two-phase commit protocol [36]. The one sending out the merge request will go through the requested and committed states; while the other one will go through the responded and committed states. In addition, the statements associated with the committed state should be treated as one atomic action i.e., the cluster head will not be preempted before the merge process is complete. By incorporating these protection mechanisms, a cluster head will involve in at most one merge request. For instance, in Fig. 6.1, after cluster heads P and Q go through the two-phase commit and 89 execute the merge process under the committed state, if P receives an m-request from R before its merge process is complete, it will ignore the request. For cluster head R, it will go back to comparing state after it waits for a short period of time maxT . In this way, the concurrent problem of distributed algorithm has been solved. In the previous paragraph, we demonstrate distributed pattern of the Traffic Aware Routing Tree, since all of the clusters combinations are done simultaneously distributedly in the whole network. Beside this, if the global information is available, centralized routing tree can be built. In the implementation point of view, centralized algorithms are much easier than distributed ones. Thus, it is not necessary to mention the detailed construction of centralized detouring routing tree. Notice that according to our algorithm the cluster head is not necessarily the root of the tree. 6.6 The Gravity Functions 6.6.1 Traffic Aware Gravity Function To minimize the possibility of having conflicting hulls between siblings, the closer clusters should be given stronger gravity so that they are merged earlier. In addition, to alleviate the bottleneck issue, the neighboring clusters with higher available bandwidth should be merged early so that the traffic between them will not suffer bottleneck issue. Given two neighboring clusters C1 and C2, these observations lead us to set the gravity function between them as follows: 2)]2,1([ )2,1()2,1( CCdist CCbandwidthCCgravity = (1) Notice that if two nodes are neighbors to each other, similar to what has been defined in IEEE802.11b specification [13], they will exchange beacons periodically. This means 90 that any pair of neighboring nodes will have a non-zero virtual bandwidth between them. According to the equation above, there will be a non-zero gravity between any pair of neighboring nodes. Consequently, if all nodes are connected in the network, after a series of merges all nodes should eventually belong to the same and only one cluster. Notice that the gravity function is symmetric i.e. for a pair of neighboring clusters C1 and C2, the gravity from C1 to C2 is the same as from C2 to C1. When two clusters merge, the center of the new cluster may shift and the virtual bandwidth to its neighboring clusters may change due to the inclusion of new cluster members. Both of these will affect the gravity value to the neighboring clusters. However, the center of the cluster is its geometric center, which is the average of the locations of nodes in the cluster, and can be calculated directly from the centers and the sizes of the original clusters. Similarly, the virtual bandwidth of the merged cluster to the neighboring clusters can be calculated directly from the virtual bandwidth of the original clusters to their neighboring clusters. During the merge process, the new gravity values to all its neighboring clusters can be calculated. To further optimize the performance of the algorithm, two different data structures can be used at each cluster head. The first one is the disjoint set data structure, which is to keep track of the membership of each node in each cluster. Initially each node is treated as one single cluster in the disjoint set. As clusters are merged, sets corresponding to the clusters are union together. The disjoint set data structure is implemented with union-by size and find-with-path-compression. The second data structure is the priority queues, which is to store the gravity function of the neighboring clusters. By making use of these queues, the time required to find the target neighboring cluster can be reduced. Whenever 91 an update is received from a neighboring cluster, the entries in the priority queues will have to be updated accordingly. This means every time, the binding action is taken, the newly built cluster has some updated neighboring relationship with its neighboring clusters. All of these new relationships have to be added as the new entries in the priority queue, which is implemented by the data structure max heap. By the operation of max heap, the maximum gravity value can be found each time. Before the extraction of this maximum gravity value from this maximum heap tree, the corresponding information of the maximum gravity value in the maximum heap tree needs to be compared with the information in the disjoint set. If these two pieces of information don?t match with each other, which means the information in the max heap tree is outdated, only deletion action will be taken to the root node in the max heap tree. Otherwise, beside the root deletion, real merge action needs to be taken in the disjoint set by the method of union by size. And then, the corresponding updated neighboring information is added as new entries of the max heap tree. In fact, the max heap tree enumerates all the possible gravity values with their corresponding neighboring relationships. Notice that in the case of merge, the head of the smaller cluster will have to include both data structures as part of the cluster information to submit to its new cluster head should these data structures be used. 6.4.2 Energy Aware Gravity Function Since the energy consumption issue is a key issue in the underwater acoustic sensor networks. We want to investigate more about it through different scenarios. According to the requirements of different underwater wireless communication applications, the Distributed Traffic Aware Routing Tree can be modified to Distributed Energy Aware Routing Tree by changing one parameter in the gravity function. This is the modification 92 to traffic aware routing tree. This gravity function is to support some energy sensitive applications. The energy aware routing tree, whether centralized or distributed, to take into account the factor, such as average residual energy, we assume that each node learns the residual energy level to each of its neighbors from the past history record. In this energy aware scenario, we also assume that traffic flows keep constant in each time period. This means even though the applications might have multiple sink and source pairs, the sink and source pairs are fixed with constant transmission rates during each time period. So in this way, we can guarantee the validity of this energy aware routing tree in each time period. One energy aware routing tree lasts one time period. For the next time period, some network parameters, such as traffic pattern, source and sink pairs, and transmission rates change, and the residual energy level distribution in the whole network will change accordingly. Thus after each time period, the energy aware routing tree will be reconstructed according to updated network parameters. How long is each time period depends on different applications. This is out of the scope of our research. Besides this, we have the assumption that the initial energy value for each node is the same and each transmission cost the same amount of energy. The basic idea of our Distributed Energy-Aware Routing Tree algorithm is that each pair of neighboring clusters has a gravity, which is computed distributedly according to a gravity function of the distance and residual energy values between them. The stronger gravity two clusters have between them, the higher possibility they will be merged into one cluster. This process is repeated until there is only one cluster left or no gravity between any pair of neighboring clusters. Initially, each node is treated as a one-node cluster, the target cluster is set to be the neighbor with the strongest gravity to the node 93 itself. In this distributed bottom up routing tree construction fashion, the very last node to be added to the routing tree will be the root of the tree, while the first node in the tree is definitely the leaf node. Through this way, the nodes with sufficient residual energy level are bonded to the lower level of the distributed routing tree and avoid being routed to the root each time in certain extent. We discuss substitute energy aware gravity function to the traffic aware gravity function in the previous paragraph. This gravity function is to support some energy sensitive applications. In this energy aware scenario, we assume that traffic flows keep constant for each time period. This means even though the applications might have multiple sink and source pairs, the sink and source pairs are fixed with constant transmission rates during each time period. Besides this, the initial energy value for each node is the same and each transmission cost the same amount of energy. The head of the larger cluster becomes the head of the merged cluster, and the head of the smaller cluster turns into a regular cluster member. In each merge, the link with the highest traffic volume between two original clusters is the link to connect those two clusters. It is not difficult to see that this process will introduce n ? 1 links to connect n number of nodes. In other words, the result of the algorithm will naturally form a tree. Since all of the clusters combinations are done simultaneously distributedly in the whole network. Since the tree is distributedly constructed according to the residual energy level, we call this routing tree Distributed Energy-Aware Routing Tree (DEART). Notice that according to our algorithm the cluster head is not necessarily the root of the tree. In gravity function, distance between two neighboring clusters will be maintained to minimize the possibility of having conflicting hulls between siblings, the closer clusters 94 should be given stronger gravity so that they are merged earlier. In addition, to alleviate energy cost issue, the neighboring clusters with higher available residual energy should be merged early so that the energy level between them will be as sufficient as possible to support transmissions. Given two neighboring clusters C1 and C2, these observations lead us to set the gravity function between them as follows: 2)]2,1([ )2,1()2,1( CCdist CCergyresidualenCCgravity = (2) Notice that if two nodes are neighbors to each other, similar to what has been defined in IEEE802.11b specification [13], they will exchange beacons periodically. This means that any pair of neighboring nodes will get to know neighboring nodes? non-zero residual energy level. According to the equation above, there will be a non-zero gravity between any pair of neighboring nodes. Consequently, if all nodes are connected in the network, after a series of merges all nodes should eventually belong to the same and only one cluster. Notice that the gravity function is symmetric i.e. for a pair of neighboring clusters C1 and C2, the gravity from C1 to C2 is the same as from C2 to C1. When two clusters merge, the center of the new cluster may shift and the residual energy level to its neighboring clusters may change due to the inclusion of new cluster members. Both of these will affect the gravity value to the neighboring clusters. However, the center of the cluster is its geometric center, which is the average of the locations of nodes in the cluster, and can be calculated directly from the centers and the sizes of the original clusters. Similarly, the residual energy level of the merged cluster to the neighboring clusters can be calculated directly from the residual energy level of the 95 original clusters to their neighboring clusters. During the merge process, the new gravity values to all its neighboring clusters can be calculated. As in distributed traffic aware routing tree, to further optimize the performance of the algorithm, two different data structures can be used at each cluster head. The first one is the disjoint set data structure, which is to keep track of the membership of each node in each cluster. Initially each node is treated as one single cluster in the disjoint set. As clusters are merged, sets corresponding to the clusters are union together. The disjoint set data structure is implemented with union-by size and find-with-path-compression. The second data structure is the priority queues, which is to store the gravity function of the neighboring clusters. By making use of these queues, the time required to find the target neighboring cluster can be reduced. Whenever an update is received from a neighboring cluster, the entries in the priority queues will have to be updated accordingly. This means every time, when the binding action taken, the new built cluster has some updated neighboring relationship with its neighboring clusters. All of these new relationships have to be added as the new entries in the priority queue, which is implemented by the data structure max heap. By the operation of max heap, the maximum gravity value can be found each time. Before the extraction of this maximum gravity value from this maximum heap tree, the corresponding information of the maximum gravity value in the maximum heap tree needs to be compared with the information in the disjoint set. If these two pieces of information don?t match with each other, which means the information in the max heap tree is outdated, only deletion action will be taken to the root node in the max heap tree. Otherwise, beside the root deletion, real merge action needs to be taken in the disjoint set by the method of union by size. The corresponding updated neighboring 96 information is added as new entries of the max heap tree. In fact, the max heap tree enumerates all the possible gravity values with their corresponding neighboring relationships. Notice that in the case of merge, the head of the smaller cluster will have to include both data structures as part of the cluster information to submit to its new cluster head should these data structures be used. 6.7 Node Failure Management In the underwater acoustic sensor networks, there are two kinds of failure which are very common. They are node failure and intermittent link failure. Node failure could be due to corrosion, energy depletion, where network partition might be formed. Intermittent link failure is a common phenomenon in underwater environments, especially shallow water where there is impulsive ambient noise. To deal with node failure, detouring routing tree algorithms keep redundant link information in the cluster heads. The cluster heads should always record the several links information according to each individual link?s traffic volume or the energy volume. Put redundant links into the priority queue according to the volume of the links? traffic and residual energy levels. If the link between two neighboring clusters breaks, the cluster head will detect it quickly, dequeue the next link from the priority queue and set it up as the next link. Each cluster member also maintains one redundant link with one of the neighboring node in the cluster in case of breakage of major link. 97 CHAPTER 7 RESULTS AND EVALUATION OF ROUTING TREES In order to evaluate our algorithm, we simulate them in both centralized and distributed fashions. We compare the performance with other two routing tree methods: Breadth First Search Tree (BFST) and Minimum Path Tree (MPT) also in centralized and distributed fashions respectively. To showcase the capability of the tree routing, the simulations are carried out in three dimensional network scenario. 7.1 Traffic Aware Routing Tree 7.1.1 Simulation Settings The simulation settings for both TART and DTART are the same. The transmission range of each node is set to be 300 meters. We randomly generate the topologies by placing nodes in a three dimensional cube with side length 1000 meters according to uniform distribution. The cube is wrapped at both ends of each dimension to eliminate the edge effect. The total number of nodes placed in the cube ranges from 100 to 200, which corresponds network densities from 8.5 to 17 neighbors per node. For each network density, we generate 10 topologies and use them to evaluate the performance of the three routing trees. For each pair of neighbors, the available traffic load between them is randomly generated in the range of 1 and 1000 with a uniform distribution. 98 7.1.2 Results and Analysis for Centralized Algorithms Figure 7.1 Number of Conflicting Convex Hulls The performance of routing trees is evaluated using three metrics. The first metric is the average number of conflicting hulls in the routing tree. After the routing trees are produced by the three algorithms, we calculate the convex hulls of the subtrees and find the number of conflicting convex hulls among siblings. Each result in Fig 7.1 is the average of the number of conflicting hulls in 10 different topologies under the same network density. As discussed in previous sections, more conflicting hulls result in more complicated routing. As shown in Fig. 7.1, the number of conflicting hulls of TART is almost zero for all density levels and is consistently smaller than the other methods. This is because TART is built from bottom up. Closer clusters are merged first so that the convex hulls between siblings have slim chance of overlapping. Therefore, it results in a geographically ?compact? tree. 99 0.0 5.0 10.0 15.0 20.0 25.0 30.0 35.0 40.0 45.0 11.3 12.4 13.6 14.7 15.8 17.0 18.1 19.2 20.3 21.5 22.6 Density (Average Number of Neighbors) Av er ag e Pa th L en gt h TART MPT BFS Figure 7.2 Average Path Length The second metric is the average path hops of the routing path, which is defined as the average number of hops between source and destination pairs. For each generated network topology, 10 pairs of source and destination are randomly selected to perform routing. Each result in Fig. 7.2 is the average of 100 source-destination pairs on top of 10 different network topologies for a given network density. A smaller number of average path hops means less energy is spent on each routing, which prolongs the lifetime of nodes in the network. In addition, a smaller number of path hops means that the information flow can reach the destination faster. This will help reduce the delay and improve the system throughput. While MPT is formed by the shortest paths from each node to the root, the path hops between source and destination pair may not be the lowest because the root may be neither the source nor the destination. As shown in Fig. 7.2, TART has the smallest average path hops. MPT considers the location of the nodes and thus has a smaller average path hops than BFST, but the location information does not seem to be fully utilized. In TART, the distance between neighboring clusters is one of 100 the two factors that determine the merge of clusters. The resulting tree therefore has the smallest average path hops. 0.0 50.0 100.0 150.0 200.0 250.0 300.0 350.0 11.3 12.4 13.6 14.7 15.8 17.0 18.1 19.2 20.3 21.5 22.6 Density (Average Number of Neighbors) Av er ag e Pa th T hr ou gh pu t TART MPT BFS Figure 7.3 Average Path Throughput The third metric is the average path throughput of the routing path, which is defined as the smallest available link bandwidth along the path from the sender to the receiver. The larger the path throughput is, the less chance the bottleneck is likely to occur. Similar to the average path length, each result in Fig. 7.3 is the average path throughput of the 100 source destination pairs on top of 10 different network topologies for a given network density. As shown in Fig. 7.3, TART has the largest path throughput because clusters of nodes are merged based on the inter-cluster available bandwidth as well as their distances. By merging clusters with more bandwidth between them earlier, TART includes links with more bandwidth in the tree. An interesting observation is that although the average path throughput of BFST is lower than TART?s, it is higher than MPT?s because a node in BFST includes all unvisited neighbors as its children during tree construction. This 101 indirectly allows BFST to include links with more available bandwidth in the tree than MPT. 7.1.3 Results and Analysis for Distributed Algorithms Performance of the distributed algorithms is evaluated and the result is shown in Figure 7.4-7.6. Figure 7.4 Number of Conflicting Convex Hulls in Distributed TART The performance of routing trees is evaluated using three metrics. The first metric is the average number of conflicting convex hulls in the routing tree. After the routing trees are built by the three distributed algorithms, we calculate the number of convex hulls of the subtrees and find the number of conflicting convex hulls among siblings. Each result in Fig 7.4 is the average of the number of conflicting hulls in 10 different topologies under the same network density. As discussed previous part, more conflicting hulls result in more ambiguity to the routing. As shown in Fig. 7.4, the number of conflicting hulls of 102 DTART is almost zero or one for all density levels and is consistently smaller than the other two methods. This is because DTART is built from bottom up distributely. In the whole networks, closer clusters are merged first so that the convex hulls between siblings have slim chance of overlapping. This merge action is triggered by timer timeout. Each local action is taken in the neighborhood without centralized control mechanism and global information. Therefore, it results in a geographically ?compact? distributed tree. From Figure 7.4, it is obvious that the results of all three distributed algorithms cannot compete with their centralized counterparts. The simple reason is that distributed algorithm always takes local information into account, but without global information support. The goal of each distributed algorithm is just to try to approach global optimization and has the centralized algorithm?s performance as its performance?s upper bound. Figure 7.5 Average Path Length in Distribute Traffic-Aware Routing Tree 103 The second metric is the average path hops of the routing path, which is defined as the average number of hops between source and destination pairs. For each generated network topology, 10 pairs of source and destination are randomly selected to perform routing. Each result in Fig. 7.5 is the average of 100 source-destination pairs on top of 10 different network topologies for a given network density. A smaller number of average path hops means less energy cost on each routing, which prolongs the lifetime of nodes in the network. In addition, a smaller number of path hops means the information flow can reach the destination faster. This will help reduce the end to end delay as well as improving the overall system throughput. While DMPT is formed by the shortest paths from each node to the root, the path hops between source and destination pair may not be the lowest because the root may be neither the source nor the destination. As shown in Fig. 7.5, DTART has the smallest average path hops, while it is difficult to tell if DMPT is better than DBFS or versus. Their average path length curves twist together with the increase of node density. This is because, from local point of view, the constructions of both DMPT and DBFS have lots of similarities. Though DMPT considers the location of the nodes and shows its advantage by having a smaller average path hops than DBFST in centralized algorithm, the location information does not seem to be fully utilized. In the distributed scenario, the global information is not available, each step of tree construction is based on local message exchanges. Compared with centralized algorithms, all three distributed algorithms seem not having more advantages in the overall performance over their centralized counterpart, because local information cannot be as optimal as global information. In DTART construction, the distance between neighboring clusters is one of the most important factors to determine the merge of clusters. Though local view of 104 networks cannot achieve global optimization, the distance emphasis of neighboring clusters in DTART construction leads to fewest conflicting convex hulls and therefore smallest average path hops. Figure 7.6 Average Path Throughput in Distribute Traffic-Aware Routing Tree The third metric is the average path throughput of the routing path, which is defined as the smallest available link bandwidth along the path from the sender to the receiver. The larger the path throughput is, the less chance the bottleneck is likely to occur. Similar to the average path length, each result in Fig. 7.6 is the average path throughput of the 100 source destination pairs on top of 10 different network topologies for a given network density. As shown in Fig. 7.6, DTART has the largest path throughput because clusters of nodes are merged based on the inter-cluster available bandwidth as well as their distances. For both DSPT and DBFS do not consider the available bandwidth issues in the design. 105 Beside that, both of them have similar local views of networks, which lead to the fact that their throughput curves in Figure 7.6 twist together and no obvious advantages appeared in this evaluation metric. For DTART, by merging clusters with more bandwidth between them earlier locally and distributed, it includes links with more bandwidth in the tree. This is the major reason of its obvious throughput advantage over other two routing tree algorithms. 7.2 Results Evaluations for Energy Aware Routing Tree 7.2.1 Simulation Settings The simulation settings for both centralized energy aware algorithm and distributed energy aware algorithm are the same. The transmission range of each node is set to be 300 meters. We randomly generate the topologies by placing nodes in a 3 dimensional cube with side length 1000 meters according to uniform distribution. The cube is wrapped at both ends of each dimension to eliminate the edge effect. The total number of nodes placed in the cube ranges from 100 to 200, which corresponds network densities from 8.5 to 17 neighbors per node. For each network density, we generate 10 topologies and use them to evaluate the performance of the three routing trees. For each pair of neighbors, the available residual energy value between them is randomly generated in the range of 1 and 500 with a uniform distribution. 106 Figure 7.7 Average Path Residual Energy in Energy Aware Routing Tree Figure 7.8 Average Path Residual Energy in Distributed Energy Aware Routing Tree 107 7.2.2 Results and Analysis for Energy Aware Routing Tree The only metric for evaluating routing performance is the average residual energy of the routing path, which is defined as the smallest link residual energy level along the path from the sender to the receiver. The link residual energy level is defined as the sum of residual energy values of two neighboring hops on that link. The larger the link residual energy level is, the less chance the entire path will die out. As in the average path length, each result in Figure 7.7 and Figure 7.8 is the average path residual of the 100 source destination pairs on top of 10 different network topologies for a given network density. As shown in both Figure 7.7 and Figure 7.8, both EART and DEART have the largest average path residual energy, because clusters of nodes are merged based on the inter- cluster residual energy as well as their distances. By merging clusters with more residual energy between them earlier, EART includes links with more residual energy level in the tree. An interesting observation for centralized energy aware algorithm is that although the average path residual energy of BFST is lower than EART?s, it is higher than MPT?s because a node in BFST includes all unvisited neighbors as its children during tree construction. This indirectly allows BFST to include links with more available residual energy in the tree than MPT. In the distributed energy aware routing tree, both DBFS and DMPT have similar local views of networks, which lead to the fact that their throughput curves in Figure 7.8 twist together and no obvious advantages appeared in this evaluation metric. For DEART, by merging clusters with more residual energy level between two neighboring clusters earlier locally and distributed, it includes links with more residual energy in the tree each 108 time in the tree construction. Through this method, DEART wins the competition of DBFS and DMPT with obvious performance advantage. With similar motivation as DTART and TART, both DEART and EART try to route the traffic as low level in the tree as possible by bounding the clusters with more residual energy closer to leaves in the routing tree. This mechanism can save the number of hops in the whole route path by avoiding the traffic flows passing through the root node. In addition, both DTART and TART construction, consider the distance factor, which reduces the number of conflicting convex hulls to a certain extent, and improves the routing performance positively and effectively. The deduction of conflicting convex hulls can get rid of ambiguity in the routing process and lead the route directly and more efficiently to destination. The detouring shortcut provided by the routing algorithm cannot only save the number of hops, but also provide a novel energy efficient solution for the applications. 7.3 Time Complexity Analysis At the beginning, there are n nodes in the networks. In the worst case scenario, every node has all of the nodes except itself as its neighbors. This means any two nodes in the network can be neighbors. So in this way, we have 2nC possible neighboring node pairs, each of them has the possibility of having the Maximum value of gravity value. Our goal is to find the Maximum value of gravity value, so it is necessary to calculate the gravity values of all the 2nC neighboring node pairs. For these 2nC =n*(n-1)/2 node pairs, each node pair can be one element in the max heap tree. The time complexity of building this max heap tree at this step is: 109 O ((n*(n-1)/2) lg (n*(n-1)/2)) = O (n 2 lg n). After building a max heap tree, the root node in the tree, which has Maximum gravity value is deleted. The corresponding operation in disjoint set is Union by size, which takes constant time complexity of O (1).This will not influence the overall time complexity of this algorithm. So this analysis only focuses on the time complexity of max heap tree operation. The combination of clusters leads to a new composition possibility of cluster- cluster. Correspondingly, more gravity values will show up. To consider the worst case scenario of this step, there are at most n-2 nodes added to the tree. So after deletion of the root node, there are n*(n-1)/2+ (n-2)-1 nodes in tree. By this analysis, we can roughly conclude that after the next step, for the worst case scenario, total node numbers is at most n*(n-1)/2+ (n-2)-1+ (n-3)-1 in the tree. Until the very last step, there are n*(n-1)/2 + (n-2)-1 + (n-3)-1?. (n-n)-1 nodes totally in the tree. So it is obvious that in this worst scenario induction, the number of nodes in the max heap tree at last is (n 2 -3n+2) which is bounded by n 2 . The first time max heap tree includes n*(n-1)/2 nodes, with this step, there will be n-2, n-3, n-4, n-5?..n-n nodes added each time respectively. In total, there are n-1 times for node insertions and (((n-2) + (n-n))*(n-1))/2, which is O (n 2 ) nodes inserted. Each insertion?s time complexity is O (2lgn) = O (lgn) and totally the time complexity is O (n 2 lgn) To analyze the time complexity of calculating the conflict hulls, we make several assumptions. We assume that each node has k children, so that each child node has at most n/k children if there are n nodes in the network. Since each convex hull operation takes O (n lg n) if there are n nodes. So for a certain node, actually all of its children will at most have 110 )1log()1( ,1,1 ++? ?== ffj k jfjf kkk (3) operations when calculating the conflict hulls, jf kk , are the number of nodes in any of two sibling children. To simplify (1) we assume if kk =+1 (4) We can get ii k jiij j kkk log ,1,1 ? ?== (5) Since nk k i i ?? =1 (6) We have j k jiji iij k jiji i kknkkk ?? ?==?== ? ,1,1,1,1 lglog (7) Since we have j k jiji i k i i k i i kkkk ??? ?==== += ,1,11 22 1 2)()( (8) So 2 )()( 1 1 22 ,1,1 ? ?? = = ?== ? = k i k i iik jiji ji kk kk (9) Since =? = k i ik 1 2)( k n2 (10) And 22 1 )( nk k i i =? = (11) So )( 2 ,1,1 nOkk j k jiji i =? ?== (10) Also 111 So )lg(lg 2 ,1,1 nnOkkk ij k jiji i =? ?== (11) The time complexity analysis above is about one node?s children conflict hull calculation, for the whole tree, it should be bounded by O ( )lg3 nn . 7.4 Summary The previous sections discuss our methods for both Traffic-Aware Routing and Energy Aware Routing Tree. However, in the real world, if there is a small scale network or a cluster, the centralized algorithm can always work well. The cluster head takes the responsibility to get global information in the cluster and build the routing tree correspondingly. In reality, the centralized algorithms are implemented by sending information from all nodes to a centralized node, and then disseminating the decision to the entire network. In a small scale network or clustered network, centralized routing tree construction will be an ideal choice, since it is simple and easy to implement. While in some cases, such as large scale networks, centralized routing tree construction normally involves intensive message exchanges and may cause network traffic congestion and low reliability. Then, distributed algorithms are preferred in practice and the centralized routing tree is not optimal. 112 CHAPTER 8 CONCLUSION AND FUTURE WORK There are some critical problems in the new research field of underwater acoustic sensor networks. The problems involve system lifetime and system throughput. In this research, we try to propose some effective and robust routing protocols which can tackle these problems. For the improvement of system lifetime, we proposed two centralized energy efficiency algorithms, in this research which can be applied to the inner cluster routing. In addition, geographic routing is known to be light-weight and efficient in wireless sensor networks, but when it is adopted for three dimensional applications, such as underwater acoustic sensor networks, most of the detouring strategies fail because their assumptions do not apply to the environment of such networks. In [34], spanning tree routing has been shown to be a good detouring strategy alternative for geographic routing without the need of those assumptions. However, the performance of the spanning tree routing is largely dependent on the quality of the pre-constructed spanning trees. In this research work, the Distributed Traffic-Aware Routing Tree (DTART) as well as the Distributed Energy-Aware Routing Tree (DEART) are presented. Compared to the existing spanning trees, the proposed detouring routing trees make better uses of the information, such as location, bandwidth and residual energy of nodes in the network. 113 The simulation results confirm that the detouring spanning trees achieve a much better routing performance in terms of the number of conflicting hulls, average path hops, the average path throughput and average path residual energy. One challenge of underwater wireless sensor networks is to detect and handle disconnections due to node failures, unforeseen mobility of nodes or battery depletion. Our pre-built routing tree is built in an absolutely distributed fashion and has the local clusters combination as the routing tree construction scenario. The advantage of a localized algorithm allows disconnection discovery to be easier by periodically exchanging messages inside a neighborhood. Setting up inter-cluster and intra-cluster backup mechanisms during the routing tree construction makes local failure recovery feasible and practical. This will greatly reduce latency due to the network reconfiguration and avoid flooding overhead during the global route discovery. However, the quality of acoustic links is highly unpredictable in underwater environment, because it mainly depends on fading and multi-path, which are hard phenomena to model. It is necessary to revise our routing algorithm with a more accurate clusters merge function, which can make the protocol quicker and more adaptable with respect to the intermittent connectivity of acoustic channels. Furthermore, for delay-tolerant application, there is a need to develop mechanisms to handle loss of connectivity without provoking immediate retransmissions. Strict integration with transport and data link layer mechanisms may be advantageous to this. Routing protocol is always application oriented. Current pre-built tree based geographic routing protocol is just general one, which only considers three general metrics: transmission distance, residual energy level and traffic load. When the current 114 routing tree based protocol targets different underwater applications, it needs to be extended and include multiple metrics, such as, average transmission delay, average throughput, optimal transmission rate, optimal packet size and fairness. If we consider all of these metrics as equal, when constructing the routing tree, this will guarantee the optimal overall routing performance, while placing different weights on different metrics regarding each application?s requirements. This will greatly benefit each individual application. For instance, real time application needs more weight on latency as well as average throughput, while the application with big volume of data transmission needs to consider more about the packet size and optimal transmission rate. Besides this, for the geographic routing protocols, it is essential to develop underwater location discovery techniques, which can calculate the location precisely. The ultimate goal of our research will be to find appropriate solutions for various underwater applications and implement them in the real underwater environment. 115 REFERENCES [1] http://en.wikipedia.org/wiki/Wireless_sensor_network [2] webs.cs.berkeley.edu/papers/hotchips-2004-motes.ppt [3] Ian F. Akyildiz, Dario Pompili, and Tommaso Melodia, State of the Art in Protocol Research for Underwater Acoustic Sensor Networks, Proceedings of the 1st ACM international workshop on Underwater networks, WUWNet?06, September 25, 2006, Los Angeles, CA, USA [4] Jinyang Li, John Jannotti, Douglas S.J. De Couto, David R. Karger, and Robert Morris. A Scalable location service for geographic ad hoc routing. In Proceedings of the 6th ACM International Conference on Mobile Computing and Networking (Mobicom?00), pages 120-130, 2000. [5] Ananth Rao, Christos H. Papadimitriou, Scott Shenker, and Ion Stoica. Geographic routing without location information. In Proceedings of the 9th ACM International Conference on Mobile Computing and Networking (MobiCom?03), pages 96-108, San Diego, CA, September 2003. [6] Dario Pompili Efficient Communication Protocol For Underwater Acoustic Sensor Networks. Doctor of Philosophy Degree Thesis in the School of Electrical and Computer Engineering, Georgia Institute of Technology, August 2007. 116 [7] Jun-Hong Cui Jiejun Kong Gerla, M. Shengli Zhou The challenges of building mobile underwater wireless networks for aquatic applications. Network, IEEE, May-June 2006, Volume: 20, Issue: 3, page(s): 12- 18, ISSN: 0890-8044. [8] Madan, R. and Lall, S., Distributed Algorithms for Maximum Lifetime Routing in Wireless Sensor Networks, IEEE GLOBECOM, Dallas, TX, Nov,2004. [9] 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. [10] Sankar, A. and Liu, Z., Maximum Lifetime Routing in Wireless Ad-hoc Networks, INFOCOM 2004 [11] Rodoplu, V. and Meng, T.H., Minimum Energy Mobile Wireless Networks, IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, 17(8), 1999, 1333-1344. [12] Li, L and Halpern,J.Y., Minimum-Energy Mobile Wireless Networks Received, IEEE International Conference on Communications (ICC), June 2001. [13] National Science Foundation. Research priorities in wireless and mobile communications and networking: Report of a workshop held March 24?26, 1997, Airlie House, Virginia. Available at http://www.cise.nsf.gov/anir/ww.html. [14] 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. [15] Wattenhofer, R. and Li L., Distributed Topology Control for Power Efficient Operation in Multihop Wireless Ad Hoc Networks, IEEE INFOCOM, 2001, pp 1388- 1397. 117 [16] Mari Carmen Domingo, Rui Prior, Energy Analysis of Routing Protocols for Underwater Wireless Sensor Networks, Computer Communications archive Volume 31 , Issue 6 (April 2008), Pages 1227-1238, ISSN:0140-3664. [17] Gandham, S., Dawande, M. and Prakash, R., Energy Efficient Schemes for Wireless Sensor Networks with Multiple Mobile Base Stations, Globecom August 2003. [18] Younis, M. and Youssef, M., Energy-Aware Routing in Cluster-Based Sensor Networks, IEEE/ACM MASCOTS, October, 2002. [19] 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 [20] 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. [21] Draves, R., Padhye, J. and Zill, B., Comparison of routing metrics for static multi- hop Wireless networks, SIGCOMM?04, Aug.30-Sept. 3,2004,Portland,Oregon. [22] Johnson, D.B, Routing in ad hoc networks of mobile hosts, IEEE Workshop on Mobile Computing Systems and Applications, December 1994. [23] 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. [24] 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 118 [25] Biswas, S. and Morris, R. Opportunistic Routing in Multi-Hop Wireless Networks, ACM SIGCOMM Computer Communication, 2004, 34(1): 69-74. [26] 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. [27] Chang, J.-H. and Tassiulas, L., Energy Conserving Routing in Wireless Ad-hoc Networks?, In IEEE INFOCOM, pp 22-31, 2000. [28] Xie, Q., et al., Maximum Residual Energy Routing with Reverse Energy Cost, IEEE GLOBECOM, August 2003 [29] 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. [30] 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. [31] Sozer, E.M., Stojanovic, M., and Proakis, J.G.,?Underwater Acoustic Networks,? IEEE Journal of Oceanic Engineering, Vol.25, pp. 72-83, Jan. 2000. [32] I. F. Akyildiz, D. Pompili, and T. Melodia, Underwater acoustic sensor networks: research challenges, Ad Hoc Networks Journal (Elsevier) (March) (2005). [33] Hahn, M., ?Undersea Navigation via a Distributed Acoustic Communication Network, ? Master?s thesis of Naval Postgraduate School, Jun. 2005. 119 [34] Ian F. Akyildiz, Dario Pompili and Tommaso Melodia, ?Challenges for efficient communication in underwater acoustic sensor networks,? ACM SIGBED Review, vol. 1, pp. 3 - 8, Jul. 2004. [35] M. Stojanovic, ?Recent Advances in High-Speed Underwater Acoustic Communications,? IEEE Journal of Oceanic Engineering, vol.121, No. 2, pp.125-136, April 1996. [36] Creber, R.K., Rice, J.A., Baxley, P.A. and Fletcher, C.L., ?Performance of undersea acoustic networking using RTS/CTS handshaking and ARQ retransmission,? OCEANS, 2001. MTS/IEEE Conference and Exhibition, Vol. 4, pp. 2083-2086, Nov. 2001. [37] C. Perkins and P. Bhagwat, ?Highly dynamic destination-sequenced distance-vector routing (DSDV) for mobile computers,? Proc. ACM Conference on Communications architectures, protocols and applications (SIGCOMM), pp. 234?244, Oct. 1994. [38] Open Shortest Path First v3, RFC 2740, 1999. [39] David B. Johnson, ?Routing in Ad Hoc Networks of Mobile Hosts,? Proc. of the Workshop on Mobile Computing Systems and Applications, pp.158-163, IEEE Computer Society, Santa Cruz, CA, Dec. 1994. [40] C. E. Perkins and E. M. Royer, ?Ad-hoc on-demand distance vector routing,? Proc. the Second IEEE Workshop on Mobile Computing Systems and Applications, pp. 90?100, Feb. 1999. [41] Y.-C. Tseng, S.-Y. Ni, Y.-S. Chen, and J.-P. Sheu, ?The Broadcast Storm Problem in a Mobile Ad Hoc Network,? Wireless Networks 8(2-3), pp. 153-167, 2002. [42] P. Bose, P. Morin, I. Stojmenovic, and J. Urrutia, ?Routing with guaranteed delivery in ad hoc wireless networks,? Proc. the Sixth ACM International Workshop on Discrete 120 Algorithms and Methods for Mobile Computing and Communications (DIALM), pp. 48?55, Aug. 1999. [43] B. Karp and H. T. Kung, ?GPSR: Greedy perimeter stateless routing for wireless networks,? Proc. the 6th ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom 2000), pp. 243-254, Boston, MA, Aug. 2000. [44] F. Kuhn, R. Wattenhofer, Y. Zhang, and A. Zollinger, ?Geometric ad-hoc routing: of theory and practice,? Proc. the 22nd ACM Annual Symposium on the Principles of Distributed Computing (PODC 2003), pp. 63-72, Boston, MA, Jul. 2003. [45] B. Leong, B. Liskov, and R. Morris,?Geographic Routing Without Planarization,? Proc. of NSDI 2006, pp. 339352, May 2006. [46] D. Pompili, T. Melodia, and I. F. Akyildiz, ?Routing Algorithms for Delay- insensitive and Delay-sensitive Applications in Underwater Sensor Networks,? in Proc. of ACM Conference on Mobile Computing and Networking (MobiCom), Los Angeles, CA, September 2006. [47] G. Toussaint. ?The relative neighborhood graph of a finite planar set,? Pattern Recognition 12, 4 (1980), pp. 261268. [48] K. Garbriel and R. Sokal. ?A new statistical approach to geographic variation analysis,? Systematic Zoology, 18 (1969), pp. 259278. [49] X.-Y. Li, G. Calinescu, and P.-J.Wan, ?Distributed construction of planar spanner and routing for ad hoc networks,? Proc. IEEE INFOCOM, vol. 3, pp. 1268-1277, Jun. 2002. 121 [50] Y.-J. Kim, R. Govindan, B. Karp, and S. Shenker, ?Geographic Routing Made Practical,? In Proc. of the USENIX Symposium on Networked Systems Design and Implementation, pp. 217 ? 230, Boston, MA, May 2005. [51] 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) [52] B. Leong. New Techniques for Geographic Routing, PhD thesis, MIT, 2006. [53] T. H. Cormen, et al, Introduction to Algorithms, the MIT Press; 2nd edition, Sep. 2001. [54] IEEE 802.1d standard, http://standards.ieee.org/getieee802/download/802.1D- 1998.pdf [55] IEEE 802.11b Standard, http://standards.ieee.org/getieee802/download/802.11b- 1999.pdf [56] C. Papadimitriou, The Theory of Database Concurrency Control, Computer Science Press, Jul. 1986. [57] Domingo, Mari Carmen Prior, Rui, Design and Analysis of a GPS-free Routing Protocol for Underwater Wireless Sensor Networks in Deep Water, International Conference on Sensor Technologies and Applications, 2007. (SensorComm 2007) [58] http://en.wikipedia.org/wiki/Convex_hull [59] B. Leong. New Techniques for Geographic Routing. PhD thesis, 2006. [60] Young-Bae Ko and Nitin H. Vaidya. Location-aided routing (LAR) in mobile ad hoc networks. In Proceedings of the 4th ACM International Conference on Mobile Computing and Networking (MobiCom ?98), pages 66.75, October 1998 122 [61] Lei Zhang, Alvin Lim, Improving Lifetime in Maximum Residual Energy Routing With Increased Transmission Distance and Retransmission, IEEE Int. Conf on Communications, Circuits and Systems (ICCCS), June 25-28, 2006, Gui Lin, China. [62] Lei Zhang, Tae-Hyun Kim, Chunlei Liu, Min-Te Sun, and Alvin Lim. TART: Traffic-Aware Routing Tree for Geographical Routing. In proceedings of IEEE Wireless Communications and Networking Conference (WCNC) March 31-April 3, Las Vegas, USA, 2008