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