PRACTICAL STATELESS GEOGRAPHICAL ROUTING (PSGR) - 3-D
STATELESS GEOGRAPHIC ROUTING FOR UNDERWATER
ACOUSTIC SENSOR NETWORKS
Except where reference is made to the work of others, the work described in this
thesis is my own or was done in collaboration with my advisory committee. This
thesis does not include proprietary or classifled information.
Sang Joon Lee
Certiflcate of Approval:
Saad Biaz
Associate Professor
Computer Science and
Software Engineering
Min-Te Sun, Chair
Assistant Professor
Computer Science and
Software Engineering
Yu Wang
Assistant Professor
Computer Science and
Software Engineering
George T. Flowers
Interim Dean
Graduate School
PRACTICAL STATELESS GEOGRAPHICAL ROUTING (PSGR) - 3-D
STATELESS GEOGRAPHIC ROUTING FOR UNDERWATER
ACOUSTIC SENSOR NETWORKS
Sang Joon Lee
A Thesis
Submitted to
the Graduate Faculty of
Auburn University
in Partial Fulflllment of the
Requirements for the
Degree of
Master of Science
Auburn, Alabama
May 10, 2008
PRACTICAL STATELESS GEOGRAPHICAL ROUTING (PSGR) - 3-D
STATELESS GEOGRAPHIC ROUTING FOR UNDERWATER
ACOUSTIC SENSOR NETWORKS
Sang Joon Lee
Permission is granted to Auburn University to make copies of this thesis at its
discretion, upon the request of individuals or institutions and at
their expense. The author reserves all publication rights.
Signature of Author
Date of Graduation
iii
Thesis Abstract
PRACTICAL STATELESS GEOGRAPHICAL ROUTING (PSGR) - 3-D
STATELESS GEOGRAPHIC ROUTING FOR UNDERWATER
ACOUSTIC SENSOR NETWORKS
Sang Joon Lee
Master of Science, May 10, 2008
(M.E., Chung Buk National University, 2002)
(B.S., Chung Buk National University, 1999)
53 Typed Pages
Directed by Min-Te Sun
Underwater acoustic sensor networks have recently gained increasing research at-
tentions due to their vast potential applications. Although the limited bandwidth and
power resources in such networks have made stateless geographic routing a favorable
choice, the existing detouring strategies in geographic routing are either ine?cient
or simply fail in 3-D underwater environments. In this thesis, we propose the flrst
stateless geographic routing protocol for 3-D networks, namely Practical Stateless
Geographic Routing. The proposed routing protocol not only performs efiectively in
underwater environments but also degrades smoothly when the location information
is either inaccurate or simply unavailable for a portion of nodes in the network. In
addition, we propose a light-weight path pruning algorithm, namely Departed Tree-
Branch Pruning, that can be combined with the proposed routing protocol to enhance
iv
the routing performance with very little overhead. The extensive simulation results
have shown that the proposed routing protocol as well as the path pruning tech-
nique perform signiflcantly better than the existing routing protocols for underwater
acoustic sensor networks in terms of delivery rate, delay, hop stretch, and energy
consumption.
v
StylemanualorjournalusedJournalofApproximationTheory(togetherwiththe
style known as \aums"). Bibliograpy follows van Leunen?s A Handbook for Scholars.
Computer software used The document preparation package TEX (speciflcally
LATEX) together with the departmental style-flle aums.sty.
vi
Table of Contents
List of Figures viii
List of Tables ix
1 Introduction 1
2 Literature Review 5
3 Practical Stateless Geographic Routing 10
3.1 Practical Stateless Geographic Routing . . . . . . . . . . . . . . . . . 10
3.2 Illustration of Practical Stateless Geographic Routing . . . . . . . . . 14
3.3 Departed Tree-Branch Pruning . . . . . . . . . . . . . . . . . . . . . 15
4 Performance Evaluation 19
4.1 Simulation Conflgurations . . . . . . . . . . . . . . . . . . . . . . . . 19
4.2 Physical Layer Conflgurations . . . . . . . . . . . . . . . . . . . . . . 20
4.3 MAC Layer Conflgurations . . . . . . . . . . . . . . . . . . . . . . . . 21
4.4 Evaluation Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4.5 Accurate Location Information Scenario . . . . . . . . . . . . . . . . 24
4.6 Partial Accurate Location Information . . . . . . . . . . . . . . . . . 29
4.7 Inaccurate Location Information . . . . . . . . . . . . . . . . . . . . . 34
5 Conclusions and Future Work 38
Bibliography 40
vii
List of Figures
1.1 A 3-D underwater acoustic sensor network for  oating oil production
platform. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
3.1 PSGR routes a packet from S to D. . . . . . . . . . . . . . . . . . . . 15
4.1 Delivery rate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.2 End to end delay . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.3 Average Hop Stretch . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.4 Energy Consumption . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.5 Communication Overhead . . . . . . . . . . . . . . . . . . . . . . . . 29
4.6 Storage Overhead . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4.7 Average Hop Stretch . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.8 Storage Overhead . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.9 Delivery Rate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.10 Energy Consumption . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.11 Average Hop Stretch . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.12 Storage Overhead . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.13 Delivery Rate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.14 Energy Consumption . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
viii
List of Tables
3.1 The Practical Stateless Geographic Routing Protocol . . . . . . . . . 12
3.2 The Practical Stateless Geographic Routing Protocol with Departed
Tree-Branch Pruning . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
ix
Chapter 1
Introduction
Underwater acoustic sensor networks (UWSNs) [1,2] are a special type of wireless
sensor networks arising from various applications such as ocean environment moni-
toring, tactical military surveillance, target tracking, and undersea navigation [3]. As
an example, Fig. 1.1 illustrates a 3-D UWSN that monitors the condition of sub sea
equipment for a  oating oil production platform. Due to the limitation of each node?s
transmission range and the possibility of nodal failure in the erosive underwater envi-
ronment, data collected by individual sensor node are usually forwarded to a control
center through a network of nodes [4]. Thus, proper routing algorithms are needed
to direct data packets from their source to the destination.
Traditional routing algorithms in wireless sensor networks can be classifled into
two categories: proactive protocols and reactive protocols. In proactive protocols
[5,6], each node maintains a routing table by exchanging link state or distance vector
control packets with neighboring 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, difierent metrics, including hop count, available bandwidth, and congestion
status, can be taken into consideration in the construction of the routing table [6].
The major disadvantage of proactive routing, however, is that the communication
and storage overheads of routing table maintenance grow quickly as the size of the
network increases or network topology changes. In reactive protocols [7,8], when a
1
Figure 1.1: A 3-D underwater acoustic sensor network for  oating oil production
platform.
node has a packet to send, it  oods the network with queries to discover a route to the
destination. The primary difierence among various reactive protocols is how the re-
sponded path information is cached at intermediate nodes and reused. While reactive
routing avoids the overhead incurred in routing table maintenance, the network-wide
query  ooding of path discovery is an extremely expensive operation and may create
additional problems, such as the infamous broadcast storm problem [9]. Therefore,
while proactive and reactive routing protocols do not rely on assumptions of net-
work topology and link characteristics, they incur heavy communication and storage
overhead, which becomes a serious issue in resource-constrained UWSNs.
2
In recent years, a new class of routing protocols { namely geographic routing
protocols [10{13] { have been proposed. Under the assumptions that each node
knows the geographic locations of itself and its neighbors as well as the source knows
and encodes the geographic location of the destination in the packet, geographic
routing can determine where to forward the packet without maintaining the routing
table or  ooding the network, an important property known as stateless. While
GPS signal is not available under the surface of the ocean, the relative location of
each underwater sensor node can be pinpointed via triangulation [14]. The stateless
property of geographic routing is especially useful for UWSNs. It helps the routing
overhead to be better decoupled with the size of the network, allows additional sensor
nodes to be deployed transparently, and permits some nodes to be turned ofi for power
saving so long as the network remains connected. As a result, geographic routing has
been suggested for UWSNs in [1,4].
In general, for the existing geographic routing algorithms to function correctly,
three assumptions are commonly required. First, the location information at each
node needs to be accurate. Second, the link model is assumed to be the unit disk
model i.e., nodes within a predeflned transmission radius can always exchange packets
with each other. Last, the network topology needs to be on a 2-D plane. In practice,
it is di?cult to obtain accurate location information at each node regardless what
localization algorithm is used. The unit disk link model does not apply to underwater
acoustic links, which have highly dynamic physical characteristics due to time-varying
multipath intersymbol interferences and Doppler shifts and spreads [15]. In addition,
3
nodes in UWSNs are mostly deployed over 3-D space at difierent depths and on the
bottom of the ocean that is normally not  at. As a result, these assumptions render
the existing geographic routing protocols unusable for UWSNs. While there are some
attempts [13,16,17] recently to do away with some of these assumptions for geographic
routing, they either introduce heavy communications overhead or require each node
to proactively maintain routing information.
In this thesis, we propose a novel geographic routing protocol, namely Practical
Stateless Geographic Routing (PSGR). Unlike the existing geographic routing proto-
cols, PSGR does not rely on the aforementioned impractical assumptions and is able
to route the tra?c e?ciently and statelessly in 3-D UWSNs. The performance of
PSGR degrades gracefully when the location information becomes less accurate. To
further optimize the route obtained by PSGR, we propose a light-weight algorithm,
namely Departed Tree-Branch Pruning (DTBP), which efiectively removes the loops
in the path. The extensive simulation results validate that the proposed routing algo-
rithms signiflcantly outperform Delay Sensitive Distributive Routing (DSDR) [32] and
Dynamic Source Routing (DSR) [7], the routing protocol adopted by the well-known
underwater AUSNET project [47].
The rest of the thesis is structured as follows. Chapter 2 surveys the related
work of geographic routing. The Practical Stateless Geographic Routing protocol as
well as the Departed Tree-Branch Pruning algorithm are illustrated in Chapter 3 and
the experimental results are presented in Chapter 4. Finally, Chapter 5 concludes the
thesis and outlines future research directions.
4
Chapter 2
Literature Review
Geographic routing is a powerful routing scheme which is able to identify a route
from source to destination statelessly with the help of the location information (see
e.g., [11]). In general, geographic routing consists of two parts { greedy forwarding
and a detouring strategy. If a node holding a packet flnds some neighbors that are
\better" than itself for a given destination, the node forwards the packet to the best
neighbor. This is called greedy forwarding. Note that greedy forwarding alone has low
delivery rate even in a connected network. When a local minimum is reached (i.e.,
no \better" neighbor can be found), the geographic routing protocol falls back to its
detouring strategy to flnd a detour to leave the local minimum and then move toward
the destination. To design a complete geographic routing protocol, two fundamental
issues need to be addressed: How to deflne the better neighbors and what strategy
should be used to flnd a detour? Difierent geographic routing protocols propose
difierent means to address these two issues.
Assume that the node currently holding the packet is denoted as n and the
destination as d. For a pair of nodes a and b, the distance between them is denoted as
dist(a;b). In [11,12,19{21], a better neighbor a for node n is deflned as one such that
dist(a;d) < dist(n;d). In [22], a better neighbor a is deflned as the one with a smaller
anglespanfrom?!ndto?!na. In[24], abetterneighboraistheonewhoseprojectiononnd
yields the most advancement toward d. In [25], a better neighbor is the one whose cell
5
in Voronoi diagram intersects nd. In [26], an analytical model is given to show that to
achieve more reliable packet delivery, the criteria of the better neighbor in geographic
routing protocols should base on the product of the expected reception power and the
forwarding distance. In [32], a non-linear optimization technique is used to flnd the
greedy criteria for delay-sensitive and delay-insensitive data in UWSNs. Note that,
if only the forwarding mode of the skeleton is involved in the routing process, it has
been shown in [20] that any deflnition of the better neighbor in [11,12,19{22,24,25,32]
leads to a sub-optimal path. However, greedy forwarding alone achieves low delivery
rate even when the networks are connected.
When there is no better neighbor i.e., a local minimum is present, several de-
touring strategies were proposed [10{12,19,21,23] that flnd a detour to a node closer
to the destination than the current local minimum. In [19,23],  ooding, the simplest
recovery plan, was proposed when the greedy forwarding does not yield a path to the
destination. This strategy, however, is expensive and not preferred. In [10{12,21],
several non- ooding detouring strategies were proposed. The basic idea of these
strategies is to forward the packet in the network according to certain rules so that
no loop will be repeated. Obviously, if the network remains connected and network is
explored this way, eventually the destination will be reached. Although it is di?cult
to guarantee the traverse contains no repeated loop for an arbitrary network topology
distributively, there exist several heuristics to achieve this guarantee if the underlying
topology is a planar graph. Hence, these strategies employ a similar two-step process:
6
? They flrst reduce the network topology to a planar graph distributively. After
the reduction, the topology contains no cross edges and the network is most
likely still connected. The remaining edges divide the two-dimensional space
into faces.
? Each strategy picks a certain set of faces in the resulting planar graph. The
boundaries of these faces are then explored until the destination is reached or
the packet is switched back to the greedy forwarding mode.
For a given network topology, several distributed algorithms [27{30] are avail-
able to planarize a network topology. In these algorithms, each node autonomously
eliminates its connections (i.e., edges) to its neighbors from the consideration of the
routing based on the locations of the neighbors so that the network topology contains
no cross edges. In the Relative Neighborhood Graph (RNG) [29], a node u eliminates
a link to a neighbor v if there exists at least one node in the intersection of radio
coverages of u and v. In the Gabriel Graph (GG) [27], a node u eliminates a link
to a neighbor v if there exists at least one node in the circle with diameter uv. The
Planar Spanner in [28] and the Morelia test in [30] employ more complicated algo-
rithms to compute the planar graph so that a smaller number of edges are deleted
from the original topology. In the computation of any of these distributed planariza-
tion algorithms, it is crucial that the location information of nodes to be accurate or
some edges will be incorrectly dropped. In addition, these algorithms implicitly as-
sume that the network is on a 2-D plane and a node is always connected to all nodes
7
within a flxed radio transmission range (i.e., ideal unit disk link model). In [16],
a planarization algorithm is proposed that relaxes the assumptions of the accurate
location information and unit disk link model, but it introduces a large amount of
signaling [13] among neighboring nodes and still relies on the 2-D assumption.
After the network topology is planarized, the resulting graph is composed of a
set of faces. Each non- ooding based geographic routing protocol picks a subset of
faces and explores the boundaries of the faces to flnd a detour to the destination. The
GPSR [11] algorithm and the face routing family (e.g., AFR, GOAFR+) [12,20,21] are
among the most popular geographic routing protocols. For instance, in the perimeter
mode of GPSR, the packet is forwarded successively on closer faces of the planar
graph (i.e., faces toward the perimeter of all faces) until it reaches the destination
or a node closer to the destination than the previous local minimum, where the
packet is switched back to the greedy forwarding mode. GOAFR+ uses a dynamically
adjustable bound in its face exploration and falls back to the greedy forwarding mode
if one has visited (up to a constant factor) more nodes on the face boundary closer
to the destination than nodes not closer to the destination. In any of these face-
traversal algorithms, it is crucial to identify the \left" or \right" side of a face. This,
unfortunately, can not be well-deflned in a 3-D network topology.
Although the criteria and performance analysis of greedy forwarding for UWSNs
have been well-studied in [32], the  ooding-based detouring strategy is too expen-
sive for the resource-constraint UWSNs and non- ooding detouring strategies require
8
assumptions that are not available in the 3-D UWSNs. How to route the tra?c
statelessly and e?ciently in 3-D UWSNs is still an issue at large.
9
Chapter 3
Practical Stateless Geographic Routing
In Chapter 2, we have identifled three assumptions commonly shared by the
existing geographic routing protocols but unavailable in 3-D UWSNs. These assump-
tions are primarily stemmed from non- ooding detouring strategies and have made
the existing geographic routing protocols inappropriate for 3-D UWSNs. This has
motivated us to design a new detouring strategy for geographic routing. In the fol-
lowing sections, we intend to answer the question: Is it possible to flnd a detour
directly (i.e., without the planarization process) from a given network topology?
3.1 Practical Stateless Geographic Routing
Notice that flnding a detour means locating a node that is closer to the destina-
tion than the previous local minimum. Without planarization and subsequent face
routing, any node in the network can lead to a detour. This implies that the detour-
ing strategy which works directly for a given network topology will need to visit all
nodes in the network in the worst case. Given a connected graph, two well-known
approaches to visit all nodes in the graph are breath-flrst search (BFS) and depth-flrst
search (DFS) [45]. If the information of the visited nodes is kept in the packet, both
approaches have the potential to flnd a detour statelessly after a local minimum is
encountered.
10
To ensure BFS or DFS to function properly as a detouring strategy, there are also
three required assumptions: i) the link needs to be bi-directional so that a packet can
traverse back as needed, ii) source and destination are connected, and iii) the network
topologyremainsstaticduringtheroutingprocess. Thebi-directionallinkassumption
can be had by using a three-way handshaking localized link-layer protocol. As for the
source-destination connectivity assumption, since any pair of nodes can be selected
as source and destination, this assumption implicitly requires that the network is
connected. The connectivity of a sensor network can be verifled at the time of network
deployment or be checked by one of localized topology control algorithms [41{44],
regardless of the network dimension 2-D or 3-D. The last assumption is commonly
assumed by most of the routing protocols. In fact, no routing protocol can guarantee
the delivery of the packet if the network topology changes fast during the routing
process. In other words, these assumptions can be fulfllled much more easily than the
aforementioned impractical assumptions required by the existing geographic routing
protocols.
In BFS, a packet will traverse back and forth among nodes that are near the node
initiating the BFS (i.e., the local minimum), an undesirable property when it is used
for routing. On the other hand, DFS does not go back until a branch is fully explored.
If a node has some information to estimate which neighbor is better to explore the
next, DFS seems to be a better choice than BFS counterpart. The remaining design
issues are i) what partial topology information that has been explored should be kept
in the packet, and ii) what data structure should be used to keep the partial explored
11
topology. Theoretically the more partial explored topology information is recorded in
the packet, the more e?cient the routing is likely to be. On the other hand, if more
information is recorded in the packet, it will likely to take up more space in the packet
and increase the communication overhead of packet forwarding. As for the type of
data structure, intuitively it seems that the partial explored topology should be kept
as a graph. However, keeping the partial explored topology by means of a graph
data structure, regardless adjacency lists or adjacency matrix is used, will increase
the data processing complexity and thus the time to process each packet. To solve
these issues, we develop an algorithm that seamlessly integrates DFS and the greedy
forwarding. Our algorithm strategically records the partial explored topology by using
a simple list of visited nodes. In Table 3.1, we present the flrst stateless geographic
routing protocol that works without those impractical assumptions, namely Practical
Stateless Geographic Routing (PSGR).
Table 3.1: The Practical Stateless Geographic Routing Protocol
A node n holding packet m with destination d
append n at the end of the partial path list of m
if n appears on the list twice
color nodes in between blue (i.e., the \tried branch")
delete the previous n on the list
if n has neighbors not on the lis
forward m to the one nearest to d
else
forward m back to where it originally came from
12
PSGR is a prioritized DFS that gives the visit (i.e., packet forwarding) priority
to the neighbor closer to the destination. When a node n receives a packet m destined
for d, it flrst appends itself to the partial path list of m and checks if it appears on
the list more than once. If n appears on the list twice, the nodes in between two
entries are one of the branches m has just visited. There is no need to keep both
n?s entries in the list, so in the algorithm the earlier duplicated entry is removed. At
this moment, if n still has unvisited neighbors, n forwards m to the one closest to d
among them. Otherwise, n will just forward m back to where it originally came from,
which will appear as the flrst neighbor of n on the list.
Because PSGR is basically a variation of DFS, it goes without saying that a
packet will deflnitely reach the destination as long as the network topology remains
stable during the time of routing process and source and destination are connected,
regardless how accurate the location information at each node is. In case if some nodes
in the network do not have the location information at all, the order of exploration
among neighbors can be assigned so that the priority is given to those that lead the
packet closer to the destination, then to those without the location information, and
flnally to those that lead the packet away from the destination.
The communication overhead is bounded by the size of the list, which is the
number of nodes a packet traverses. When a node receives a packet, it also needs to
scan through the list to check if it is on the list or not. Hence, the time complexity
of data processing is also bounded by the number of nodes a packet traverses.
13
3.2 Illustration of Practical Stateless Geographic Routing
In Fig. 3.1, a 2-D example is provided to illustrate how PSGR routes a packet. In
the flgure, the source and destination are S and D, respectively. The neighborhood
relationship of the network is denoted by the dotted lines. According to the PSGR
algorithm, S appends itself to the list (< S >) and forwards it to N1 since N1 is closer
to D than N2. N1 again appends itself to the list (< S;N1 >) and then forwards it
to N3 as N3 is closer to D than N2. N3 appends itself to the list (< S;N1;N3 >) and
forwards the packet to N4, the neighbor closest to D. N4 is a dead-end, so it appends
itself to the list (< S;N1;N3;N4 >) and send it back to N3, which it originally
received the packet from. Afterwards, N3 appends itself to the list and flnds that
there are duplicated entry of N3 on the list, so it deletes the previous entry on the
list (< S;N1;N4;N3 >) and forwards the packet to N5, the last neighbor not on the
list. N5 is also a dead-end, so it appends itself to the list (< S;N1;N4;N3;N5 >)
and forwards the packet back to N3. At this moment, all of N3?s neighbors have
been visited and on the list, so it appends itself to the list again, deletes the previous
duplicated entry (< S;N1;N4;N5;N3 >), and then forwards the packet to N1, the flrst
neighbor of N3 on the list. Similarly, after N1 receives the packet, it again appends
itself to the list, deletes the duplicated entry (< S;N4;N5;N3;N1 >), and forwards
the packet to N2, the only neighbor of N1 not on the list. Consequently, N2, N6, N7,
N9, N12, and N13 will append themselves to the list as the packet travels through
them before the packet eventually reaches D.
14
Figure 3.1: PSGR routes a packet from S to D.
As shown in Fig. 3.1, PSGR will pay dearly if some branch explored earlier (e.g.,
N1 to N3) fails to reach the destination. However, as we will show in our performance
studies in Chapter 4 that even with very inaccurate location information PSGR will
give us very satisfactory routing performance on average. Notice that all of the non-
 ooding detouring strategies, including perimeter routing [11] and face routing [12],
perform poorly at critical network density regions [12,18].
3.3 Departed Tree-Branch Pruning
In [18], a post optimization technique, namely Path Pruning (PP), is introduced
that can be applied to improve the performance of geographic routing protocols. We
have found that the similar technique works even better with PSGR. The basic idea
15
of PP is that a node listens to the wireless radio channel after it transmits a packet.
If after a short period of time the node flnds that the same packet is transmitted by
one of its neighbors difierent from the one it previously forwarded the packet to, it
identifles this neighbor as the next hop of the destination of the packet and forwards
the subsequent packets for the same destination directly to this neighbor. PP helps
identify the shortcuts that are not utilized by the non- ooding detouring strategies
in the existing geographic routing.
Although PP keeps next hop entries at a subset of nodes on the path, this
informationispassivelyacquiredbylistening tothewirelessradiochannel. Thereisno
communication cost to maintain the next hop entry for terrestrial wireless networks.
In addition, the state information is kept only for active connections. If a node
with a next hop entry for a destination does not receive subsequent packets for the
destination, the next hop entry will time out and be deleted. With the help of PP, the
routing performance of geographic routing protocols improves dramatically at critical
network densities.
Unfortunately, the path pruning algorithm, if directly applies to UWSNs, may
have some issues. First, it takes much higher energy level for an underwater sensor
node to even passively listen to acoustic signals. Second, the inferior physical charac-
teristics of underwater acoustic links have tendency to produce higher bit error rates,
which may prevent a node from identify a neighbor sending the same packet. Third,
in order to flnd shortcuts, each node will have to keep the information of each packet
16
it transmits for a period of time in the path pruning algorithm. In resource-constraint
underwater environment, this storage requirement may not be feasible.
Table 3.2: The Practical Stateless Geographic Routing Protocol with Departed Tree-
Branch Pruning
A node n holding packet m with destination d
if m is the flrst packet from source to destination d
append n at the end of the partial path list of m
if n appear on the list twice
color nodes in between blue (i.e., the \tried branch")
delete the previous n on the list
if n has neighbors not on the list
forward m to the one nearest to d
else
forward m back to where it originally came from
if m is forwarded to a neighbor difierent from n?s greedy choice
record the neighbor as the next hop for destination d
else
remove the next hop entry for d if there is one
else
if n has no next hop entry for d
forward m to the neighbor of greedy choice
else
forward m to the neighbor indicated in the next hop entry
To minimize the overhead of path pruning, we propose a light-weight path prun-
ing, namely Departed Tree-Branch Pruning (DTBP) that goes with PSGR. In DTBP,
if a node forwards a packet to a neighbor difierent from its greedy choice, it keeps a
next hop entry for the destination of that packet. When a packet comes back from
17
one neighbor and gets forwarded to another one, the next hop entry is updated ac-
cordingly. If a node receives subsequent packets for a destination and it has a next
hop entry for the destination, it forwards the packets directly to the one indicated in
the next hop entry. Otherwise, it forwards subsequent packets to its greedy choice.
Table 3.2 illustrates the protocol of Practical Stateless Geographic Routing with De-
parted Tree-Branch Pruning. As an example, in Fig. 3.1, when N1 flrst forwards a
packet destined for D to N3, N1 will not record the next hop entry for D as N3 is the
greedy choice for destination D. However, when N1 later forwards the packet to N2,
N1 will keep a next hop entry < D;N2 > and N1 will then forward the subsequent
packets for D directly to N2.
Since there is no planarization process involved in PSGR, all edges, including
difierent types of shortcuts, will be considered for packet routing. In addition, DTBP
helps PSGR to identify and remove loops. As a result, although PSGR with DTBP
does not require a node to passively listen to the acoustic signals looking for the same
packet it transmitted earlier nor an underwater sensor node to keep the information
of every packet it transmits, it shows excellent routing performance. The only type of
shortcuts PSGR with DTBP fails to identify is those that lead the packet away from
the destination, such as the link between N6 and N9 in Fig. 3.1. In the original path
pruning algorithm, N6 will overhear the transmission of the same packet from N9, so
N6 is able to identify a shortcut to N9. However, we have found that such shortcuts
appear rather infrequently in our performance studies.
18
Chapter 4
Performance Evaluation
To evaluate the performance of the proposed PSGR and DTBP algorithms, we
compared our protocols with other two well-known underwater routing protocols {
DSR [7] and DSDR [32] by using ns-2 [33]. In this section, the simulation conflgura-
tions, metrics, and results of difierent routing protocols are presented.
4.1 Simulation Conflgurations
In our simulations, the network topology is randomly generated by placing nodes
ina4000mx4000mx1000mvolumefleld. The transmission powerissettobe97 dB
which approximately corresponds to 500 m of transmission range. the total number of
nodes ranges from 100 to 500, which corresponds to network density ranging from 3.27
to 16.35 neighbors per node. For a given network density, 200 realizations of network
topology are generated. For each realization, three pairs of source and destination,
which are connected through the network, are randomly selected. Each source node
generates constant bit-rate (CBR) tra?c  ows to its destination simultaneously. Each
CBR  ow sends 5 consecutive packets of 100 bytes at the transmission rate of 10 Kbps.
The inter arrival time of packets is set to be 30 seconds.
To simulate the characteristics of the underwater environment, the ns-2 under-
water module [34] is used. For MAC protocol, CSMA/CA [35] with stop-n-wait ARQ
19
(i.e., ACK) is implemented. The following sections elaborate on physical and MAC
layer conflgurations.
4.2 Physical Layer Conflgurations
In [34], the physical characteristics of UWSN are realized by the creation of
propagation, channel, and physical layer models. The propagation model calculates
the signal-to-noise ratio (SNR) at each receiver node after attenuation, ambient noise,
and the interference range of a signal. The attenuation is based on the spreading
loss [37] and on Thorp?s approximation [38] for the absorption loss. In addition, the
orientation of the link (i.e., whether it is horizontal or vertical) afiects the signal
attenuation through acoustic fading channels. The ambient noise in the underwater
environment is obtained from turbulence, shipping, wind, and thermal.
The channel model is used for the calculation of neighbor sets, collision, and so
on. In addition, it calculates propagation delay, which is formulated by the speed of
the sound, the depth of the water, and the temperature of the water [39].
The physical layer model is responsible for packet reception including transmis-
sion error, transmission time, and propagation delay by calling the function in the
propagation and channel models. In addition, it calculates the energy consumption
for transmission. The hardware related parameters of the physical interface, such as
the receiving signal strength threshold and the maximum transmission power, are set
according to the WHOI micro modem [40].
20
Although the underwater model in [34] does not provide the bit error rate (BER),
it is able to calculate the receiving power, which can be used to infer the BER from
the experiment results presented in [36]. Without loss of generality, we adopt the
error model in [36] as an exponential equation, 0:4?exp(?0:323?Pr), where Pr is
the receiving power. In this equation, BER increases quickly as the receiving power
decreases. For instance, when Pr is 30 dB, BER is 2?10?5, and when Pr is 40 dB,
BER is 10?6.
4.3 MAC Layer Conflgurations
As suggested in [48], the CSMA/CA with ARQ is adopted as the medium access
control mechanism for our underwater simulations. The RTS/CTS handshaking is
removed because it causes serious delays in a low rate and high delay underwater en-
vironment. To battle with high BER, the stop-n-wait ARQ (i.e., link layer ACK [46])
is used in our underwater simulations. If a node does not receive ACK within the
period of the ACK timeout after it transmits a packet, it assumes the packet is lost
and retransmits the packet. A packet can be retransmitted as needed up to a preflxed
number of times. To simplify the simulation design, the forward error correction [46]
is not implemented and the packet error rate (PER) is approximated as the product
of BER and packet size. In other words, if any bit in a packet is lost, the whole packet
will be discarded.
Due to the special physical characteristics of underwater acoustic links, the MAC
parameters are adjusted accordingly. For instance, the value of the slot time in
21
the CSMA/CA backofi mechanism has to account for the propagation delay of the
physical layer. Since the speed of sound in water is approximately 1500 m=s, the
slot time should be much longer than that in wireless media. The MAC parameters
in our simulations are set similar to what are used in [32]. The inter frame spacing
and the slot time are both set to be 0.18 second. The minimum and maximum
contention window size are set to be 4 and 32, respectively. To accommodate the
high propagation delay of acoustic signals, the duration of the ACK timeout is set to
be 5 seconds and the number of maximum link retransmissions is set to be 10.
4.4 Evaluation Metrics
To evaluate routing protocols, flve difierent metrics, including delivery rate, end-
to-end delay, hop stretch, energy consumption, and communication overhead, are
used. Their deflnitions are provided as follows.
1. Delivery rate { The delivery rate is deflned as the ratio of the total number of
received packets and the total number of generated packets.
2. End-to-end delay { The end-to-end delay is deflned as the duration from the
time a packet is generated to the time the packet is received by its destination
without collision. It is afiected by many factors, but the dominating one in the
underwater environment is the propagation delay.
3. Hop stretch { The hop stretch, as deflned in [21], is calculated by the following
formula.
22
PA(i) = hA(Ni;nsi;ndi)h
D(Ni;nsi;ndi)
: (4.1)
In Eq. 1, hA(Ni;nsi;ndi) denotes the number of hops of the route obtained
by routing algorithm A on network Ni with source nsi and destination ndi,
and hD(Ni;nsi;ndi) is the number of hops of the shortest path between nsi
and ndi on network Ni computed by Dijkstra?s algorithm [45] assuming the
transmission range of each node to be 500 m. In the case of unit disk link
model, the number of hops obtained by Dijkstra?s algorithm is guaranteed to
be the smallest. However, in our ns-2 simulations depending on the orientation
of a link the transmission range can be slightly more than 500 m at times.
Thus, hop stretch of some routing algorithms can be less than one. Similar to
end-to-end delay, hop stretch only accounts for successfully delivered packets.
4. Energy consumption { Energy consumption is calculated by the ns-2 underwater
module [34]. The unit of energy consumption is Joule.
5. Communication overhead { For PSGR, the extra information (i.e., source node
ID, destination node ID, location of the destination, and partial path list) stored
in the packet header is considered as its communication overhead. The size of
the partial path list increases by 4 bytes (to store the ID of the node currently
holding the packet) for each hop. For DSDR source node ID, destination node
ID, and the location of the destination are considered as its communication
23
overhead. For DSR, the communication tra?c in the path discovery phase is
calculated as its communication overhead.
In addition, to evaluate DTBP, the storage overhead is used and is deflned as
the number of nodes that keep the next hop entry in the DTBP algorithm. A next
hop entry consists of destination ID, next hop ID, and a time stamp of the entry.
In the following sections, the simulation results of three types of scenarios are
presented. The flrst scenario is that all nodes possess accurate location information;
the second scenario is that some nodes do not have their location information; the
third scenario is that there is location error at each node.
4.5 Accurate Location Information Scenario
In this section, the simulation results in the scenario that all nodes have accurate
location information are presented.
Fig. 4.1 illustrates the delivery rate of difierent routing protocol with respect to
the network density. As can be seen in Fig. 4.1, the critical density region in 3-D
networks that results in lower greedy success rate ranges from 5 to 7, which is slightly
higher than the critical region (3 to 7) in 2-D networks found in [12,18]. As observed,
PSGR achieves much higher delivery rate compared with DSDR and DSR, regardless
whether DTBP is adopted or not. The delivery rate of DSDR reaches the lowest in
the critical density region because DSDR does not have a detouring strategy and in
the critical density region many packets will likely be forwarded to the local minimum.
The delivery rate of DSDR is slight lower than the greedy success rate in the ideal
24
 0
 20
 40
 60
 80
 100
 4  6  8  10  12  14  16
Delivery Rate (%)
Network Density
Greedy Success Rate (Ideal Environment)
DSR
DSDR
PSGR
PSGR w/ DTBP
Figure 4.1: Delivery rate
environment where the efiects of MAC and physical layer are completely ignored. The
delivery rate of DSR decreases as the network density increases. This is due to the
fact that DSR uses  ooding in its path discovery phase, which incurs a large number
of packet collisions and severe channel contention when the number of neighbors
increases. This conflrms that in the resource-constraint underwater environment, the
 ooding operation is not efiective.
Fig. 4.2 shows the end-to-end delay of difierent routing protocol with respect
to the network density. DSDR has the shortest delay among all routing protocols.
However, note that this delay only accounts for packets successfully delivered and
the number of successfully delivered packets for DSDR is the lowest as depicted in
Fig. 4.1. The end-to-end delay of PSGR reaches the highest point in the critical
25
 0
 50
 100
 150
 200
 4  6  8  10  12  14  16
Delay (sec.)
Network Density
DSR
DSDR
PSGR
PSGR w/ DTBP
Figure 4.2: End to end delay
density region. This is because that packets are likely to traverse a longer route in
case of the critical density region. PSGR with DTBP leads to slightly shorter delay
than PSGR because after the delivery of the flrst packet subsequence packets can go
through a pruned shorter route. DSR results in the longest end-to-end delay because
the delay includes the time of path discovery phase in DSR.
Fig. 4.3 demonstrates the average hop stretch of difierent routing protocol with
respect to the network density. Similar to the end-to-end delay, DSDR has the small-
est hop stretch among all routing protocols, but that is because DSDR only deliver
a small number of packets that do not lead to any local minimum. Since only the
greedy forwarding is involved, the paths these packets traverse are guaranteed to be
sub-optimal [25]. DSR produces small hop stretch at low network density, but the
26
 0.8
 1
 1.2
 1.4
 1.6
 1.8
 2
 4  6  8  10  12  14  16
Average Hop Stretch
Network Density
DSR
DSDR
PSGR
PSGR w/ DTBP
Figure 4.3: Average Hop Stretch
hop stretch increases along with the network density. This is because  ooding done in
networks with higher density will sufier from the broadcast storm problem [9]. As a
result, the path discovery phase of DSR fails to produce short paths at high network
density. Both PSGR and PSGR with DTBP produce longer hop stretch in the critical
network density region, and the hop stretch of PSGR with DTBP is slightly lower
than PSGR. Note that even the largest hop stretch produced by PSGR (approxi-
mately 1.6) is much smaller than that produced by GPSR [11] and GOAFR+ [12] in
2-D networks (approximately 6 to 8) [18].
Fig. 4.4 shows the energy consumption of difierent routing protocol with respect
to the network density. PSGR and PSGR with DTBP consume almost the same low
amount of energy. DSDR consumes even less energy, but it is because it delivers fewer
27
 0
 1000
 2000
 3000
 4000
 5000
 6000
 7000
 4  6  8  10  12  14  16
Energy Consumption (J)
Network Density
DSR
DSDR
PSGR
PSGR w/ DTBP
Figure 4.4: Energy Consumption
packets. DSR consumes the most energy among all routing protocols. Since the hop
stretch of DSR is not higher than that of PSGR in most of the density region, the
reason of more energy consumption of DSR can only be the  ooding operations in
the path discovery phase.
Fig. 4.5 illustrates the communication overhead of difierent routing protocol with
respect to the network density. As can be seen in Fig. 4.5, all the geographic routing
protocols, including DSDR, PSGR, and PSGR with DTBP, have low communication
overhead and their communication overhead is insensitive to the network density. On
the other hand, DSR introduces much more communication overhead due to  ooding
in the path discovery phase and the overhead grows quickly as the network density
increases.
28
 0
 50
 100
 150
 200
 250
 4  6  8  10  12  14  16
Communication Overhead (byte)
Network Density
DSR
DSDR
PSGR
PSGR w/ DTBP
Figure 4.5: Communication Overhead
Fig. 4.6 demonstrates the storage overhead of the DTBP. On average there are
only few (< 3) nodes on the path that need to keep the next hop entry. Interestingly,
when the network density increases, more nodes in the network will not cause more
nodes to keep the next hop entry. This is because the probability of greedy forwarding
increases along with the network density.
4.6 Partial Accurate Location Information
To validate the robustness of PSGR and PSGR with DTBP, in this section the
simulation results of them in the scenario that a portion of nodes in the network do
not have the location information are presented. The percentage of nodes with the
29
 0
 1
 2
 3
 4
 5
 4  6  8  10  12  14  16
Storage Overhead
Network Density
PSGR w/ DTBP
Figure 4.6: Storage Overhead
location information is set to be 50%, 75%, and 100%. Note that the rest of nodes in
the network is assumed to have no location information at all.
Fig. 4.7 shows the hop stretch of PSGR and PSGR with DTBP with respect
to the network density in the scenario where only a percentage of nodes have the
location information. As expected, the fewer nodes possess the location information,
the larger the hop stretch is. This is because the probability for a node to forward a
packet to a neighbor away from the destination increases as more and more neighbors
have no location information. The hop stretch goes above 4 in the critical network
density region when only 75% nodes have the location information. The hop stretch
is doubled (approximately 8) in the critical network density region when only half of
nodes in the network have the location information. However, it is worth noting that
30
 2
 4
 6
 8
 10
 12
 4  6  8  10  12  14  16
Average Hop Stretch
Network Density
PSGR; 100% of Nodes w/ Location Information
PSGR;   75% of Nodes w/ Location Information
PSGR;   50% of Nodes w/ Location Information
PSGR w/ DTBP; 100% of Nodes w/ Location Information
PSGR w/ DTBP;   75% of Nodes w/ Location Information
PSGR w/ DTBP;   50% of Nodes w/ Location Information
Figure 4.7: Average Hop Stretch
in the critical density region DTBP helps reduce the hop stretch by more than 50%
regardless of the percentage of nodes that possess the location information.
Fig. 4.8 illustrates the storage overhead of PSGR with DTBP with respect to the
network density in the scenario where only a percentage of nodes have the location
information. The lack of location information at some nodes increases the probability
for PSGR with DTBP to produce longer path, which in turn results in more nodes
to keep the next hop entry. However, by keeping few extra next hop entries, DTBP
is able to prune the path by more than 50% as depicted in Fig. 4.7 in critical density
region. In addition, the storage overhead decreases quickly when network density
increases.
31
 0
 5
 10
 15
 20
 4  6  8  10  12  14  16
Storage Overhead
Network Density
100% of Nodes w/ Location Information
75% of Nodes w/ Location Information
50% of Nodes w/ Location Information
Figure 4.8: Storage Overhead
 0
 20
 40
 60
 80
 100
 4  6  8  10  12  14  16
Delivery Rate (%)
Network Density
100% of Nodes w/ Location Information
75% of Nodes w/ Location Information
50% of Nodes w/ Location Information
Figure 4.9: Delivery Rate
32
Fig. 4.9 demonstrates the delivery rate of PSGR with respect to the network
density in the scenario where only a percentage of nodes have the location information.
In case when 75% of nodes have location information, the delivery rate of PSGR is
almost 100% except at the critical density, where the delivery rate of PSGR is reduced
to around 90%. In case when only half of nodes have the location information, the
delivery rate is still more than 90%. Recall in Fig. 4.1 DSR and DSDR can never
achieve the delivery rate higher than 90%, it shows that PSGR is very robust even
when a large portion of nodes in the network do not have location information.
 0
 200
 400
 600
 800
 1000
 4  6  8  10  12  14  16
Energy Consumption (J)
Network Density
100% of Nodes w/ Location Information
75% of Nodes w/ Location Information
50% of Nodes w/ Location Information
Figure 4.10: Energy Consumption
Fig. 4.10 shows the energy consumption of PSGR with respect to the network
density in the scenario where only a percentage of nodes have the location information.
As can be seen in Fig. 4.10, more energy is consumed by PSGR if more nodes have
33
no location information. However, if we compare the energy consumption between
PSGR and DSR in Fig. 4.10 and Fig. 4.4, it is clear that PSGR consumes much less
energy than DSR even when 50% of nodes do not have the location information.
4.7 Inaccurate Location Information
In this section, we further validate the robustness of PSGR and PSGR with
DTBP on location information errors. Suppose that a node has transmission range r.
The location error is modeled as a uniform random value between [?e%?r;e%?r]
on each dimension. That means if a nodes true location is [x;y;z], then the location
information is generated as any 3-tuple value within the cube bounded by [x?e%?
r;x + e%?r], [y ?e%?r;y + e%?r] and [z ?e%?r;z + e%?r]. The location
error is set to be either 0%, 50%, or 100%.
Fig.4.11, 4.12, 4.13, and4.14illustratethehopstretch, storageoverhead, delivery
rate, and energy consumption of PSGR and PSGR with DTBP with respect to the
network density in the scenario where there is location error at each node. It is
not di?cult to see that the trend in these flgures is very similar to that in Fig. 4.7,
4.8, 4.9, and 4.10, respectively. In general, the routing performance of PSGR and
PSGR with DTBP in the scenario where there is location error at each node is
better (i.e., lower hop stretch, lower storage overhead, higher delivery rate, and lower
energy consumption) than that in the scenario where only a portion of nodes have
the location information, regardless which metric is used. For instance, the peak of
the hop stretch of PSGR in the scenario of the huge 100% of location error at each
34
 1
 2
 3
 4
 5
 6
 7
 8
 4  6  8  10  12  14  16
Average Hop Stretch
Network Density
PSGR; Location Error     0%
PSGR; Location Error   50%
PSGR; Location Error 100%
PSGR w/ DTBP; Location Error     0%
PSGR w/ DTBP; Location Error   50%
PSGR w/ DTBP; Location Error 100%
Figure 4.11: Average Hop Stretch
 0
 5
 10
 15
 20
 4  6  8  10  12  14  16
Storage Overhead
Network Density
Location Error     0%
Location Error   50%
Location Error 100%
Figure 4.12: Storage Overhead
35
 0
 20
 40
 60
 80
 100
 4  6  8  10  12  14  16
Delivery Rate (%)
Network Density
Location Error     0%
Location Error   50%
Location Error 100%
Figure 4.13: Delivery Rate
 0
 200
 400
 600
 800
 1000
 4  6  8  10  12  14  16
Energy Consumption (J)
Network Density
Location Error     0%
Location Error   50%
Location Error 100%
Figure 4.14: Energy Consumption
36
node (approximately 5.8) is much smaller than the peak of hop stretch of PSGR in
the scenario that 50% of nodes have location information (approximately 7.5).
From these simulation results, we conclude the following two observations: First,
PSGR as well as PSGR with DTBP is robust no matter the location information is
missing or there is error in the location information at each node. Second, a little
location information, evena veryinaccurate one, can improvethe routing performance
signiflcantly.
37
Chapter 5
Conclusions and Future Work
Routing in 3-D underwater acoustic sensor networks is challenging due to the
resource constraints in underwater environment and inferior physical characteristics
of acoustic links. Although geographic routing has been suggested for such networks,
the existing detouring strategies are not appropriate for the 3-D underwater envi-
ronment. In this thesis, we propose the flrst stateless geographic routing protocol
for 3-D underwater acoustic sensor networks, namely Practical Stateless Geographic
Routing. Our routing protocol is based on the concept of depth-flrst search and is
robust in the sense that it functions well even when the location information is not
available. In addition, we propose a light-weight algorithm, namely Departed Tree-
Branch Pruning, to efiectively optimize the path obtained from the proposed routing
protocol. The extensive simulation results have validated that the proposed rout-
ing algorithms achieve much better routing performance than the existing routing
protocols for underwater networks in terms of difierent metrics.
As we have pointed out in Chapter 4, our proposed protocol performs better
when all nodes have huge errors than when a large portion of nodes have accurate
location information but the rest have none. This observation teaches us that even a
very rudimental and light-weight localization algorithm (e.g., a node sets its location
as the average of neighbor?s) may help the routing performance signiflcantly. In
the future, we would like to investigate difierent localization algorithms and study
38
which one provides the best trade-ofi between the routing performance gains and the
communication/computational overheads for localization.
39
Bibliography
[1] E. M. Sozer, M. Stojanovic,, and J. G. Proakis,\Underwater Acoustic Networks,"
IEEE Journal of Oceanic Engineering.,Vol. 25, pp. 72-83, 2000.
[2] Ian F. Akyildiz and Dario Pompili and Tommaso Melodia,\State-of-the-art in
protocol research for underwater acoustic sensor networks," WUWNet ?06: Pro-
ceedings of the 1st ACM international workshop on Underwater networks., pp.
7-16, 2006.
[3] M. Hahn,\Undersea Navigation via a Distributed Acoustic Communication Net-
work," Master?s Thesis of Naval Postgraduate School., 2005.
[4] Ian F. Akyildiz and Dario Pompili and Tommaso Melodia,\Challenges for E?-
cient Communication in Underwater Acoustic Sensor Networks," Special Interest
Group on Embedded Systems (SIGBED) Rev.,Vol. 1, pp. 3-8, 2004.
[5] Charles E. Perkins and Pravin Bhagwat,\Highly Dynamic Destination-
Sequenced Distance-Vector Routing (DSDV) for Mobile Computers," Proceed-
ings of the ACM International Conference on Communications Architectures,
Protocols and Appliations (SIGCOMM), pp. 234-244, 1994.
[6] \Open Shortest Path First v3," RFC 2740., 1999.
[7] D. B. Johnson,\Routing in Ad Hoc Networks of Mobile Hosts," Proceedings of
IEEE Internatinal Workshop on Mobile Computing Systems and Applications.,
1994.
[8] C. E. Perkins and E. M. Royer,\Ad-hoc On-Demand Distance Vector Routing,"
wmcsa., Vol. 0, pp. 90, 1999.
[9] Y.-C. Tseng and S.-Y. Ni and Y.-S. Chen and J.-P. Sheu,\The Broadcast Storm
Problem in a Mobile Ad Hoc Network," Wireless Networks.,Vol. 8, pp. 153-167,
2002.
[10] P. Bose and P. Morin and I. Stojmenovic and J. Urrutia,\Routing with Guar-
anteed Delivery in Ad Hhoc wireless Networks," Proceedings of the 3rd Inter-
national Workshop on Discrete Algorithms and Methods for Mobile Computing
and Communications (DIAL-M)., pp. 48-55, 1999.
40
[11] B. Karp and H. T. Kung,\GPSR: Greedy Perimeter Stateless Routing for Wire-
less Networks," Proceedings of the ACM International Conference on Mobile
Computing and Networking (MOBICOM)., pp. 243-254, 2000.
[12] F. Kuhn and R. Wattenhofer and Y. Zhang and A. Zollinger,\Geometric Ad-hoc
Routing: of Rheory and Practice," Proceedings of the 22nd Annual Symposium
on Principles of Distributed Computing (PODC)., pp. 63-72, 2003.
[13] A. Rao and S. Ratnasamy and C. Papadimitriou and S. Shenker and I. Sto-
ica,\Geographic Routing without Location Information," Proceedings of the 9th
Annual International Conference on Mobile Computing and Networking (Mobi-
Com)., pp. 96-108, 2003.
[14] H. Liu and Houshang Darabi and P. Banerjee and Jing Liu,\Survey of Wireless
Indoor Positioning Techniques and Systems," IEEE Transactions on Systems,
Man, and Cybernetics, Part C.,Vol. 37, pp. 1067-1080, 2007.
[15] M. Stojanovic,\Recent Advances in High-Speed Underwater Acoustic Commu-
nications," IEEE Journal of Oceanic Engineering.,Vol. 21, pp. 125-136, 1996.
[16] Y.-J. Kim and R. Govindan and B. Karp and S. Shenker,\Geographic Routing
Made Practical," Proceedings of the USENIX Symposium on Networked Systems
Design and Implementation (NSDI)., pp. 217-230, 2005.
[17] L. Zhang and T.-H. Kim and C. Liu and M.-T. Sun and A. Lim,\TART: Tra?c-
Aware Routing Tree for Geographical Routing," Proceedings of IEEE Wireless
Communication and Network Conference (WCNC)., 2008.
[18] X. Ma and M.-T. Sun and X. Liu and G. Zhao,\An E?cient Path Pruning
Algorithm for Geographical Routing in Wireless Networks," IEEE Trans. on
Vehicular Technology.
[19] Y.-B. Ko and N. H. Vaidya,\Location-Aided Routing (LAR) in Mobile Ad Hoc
Networks," Proceedings of the ACM/IEEE International Conference on Mobile
Computing and Networking (MOBICOM)., pp. 66-75, 1998.
[20] F. Kuhn and R. Wattenhofer and A. Zollinger,\Asymptotically Optimal Geomet-
ric Mobile Ad-Hoc Routing," Proceedings of the 6th International Workshop on
Discrete Algorithms and Methods for Mobile Computing and Communications
(DIALM)., pp. 24-33, 2002.
41
[21] F. Kuhn and R. Wattenhofer and A. Zollinger,\Worst-Case Optimal and
Average-Case E?cient Geometric Ad-Hoc Routing," Proceedings of the ACM
International Symposium on Mobile Ad Hoc Networking and Computing (Mo-
biHoc)., pp. 267-278, 2003.
[22] E. Kranakis and H. Singh and J. Urrutia,\Compass Routing on Geometric Net-
works," Proceedings of 11th Canadian Conference on Computational Geometry.,
pp. 51-54, 1999.
[23] S. Basagni and I. Chlamtac and V. R. Syrotiuk and B. A. Woodward,\A Dis-
tance Routing Efiect Algorithm for Mobility (DREAM)," Proceedings of the
ACM/IEEE International Conference on Mobile Computing and Networking
(MOBICOM)., pp. 76-84, 1998.
[24] I. Stojmenovic and X. Lin,\Loop-Free Hybrid Single-Path/Flooding Routing
Algorithms with Guaranteed Delivery for Wireless Networks," IEEE Tran. on
Parallel Distributed Systems.,Vol. 12, pp. 1023-1032, 2001.
[25] G. Xing and C. Lu and R. Pless and Q. Huang,\On Greedy Geographic Routing
Algorithms in Sensing-Covered Networks," Proceedings of the ACM Interna-
tional Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc).,
pp. 31-42, 2004.
[26] Ka. Seada and M. Zuniga and A. Helmy and B. Krishnamachari,\Energy-
E?cient Forwarding Strategies for Geographic Routing in Lossy Wireless Sensor
Networks," Proceedings of the 2nd International Conference on Embedded Net-
worked Sensor Systems (SenSys)., pp. 108-121, 2004.
[27] K. Garbriel and R. Sokal,\A New Statistical Approach to Geographic Variation
Analysis," Systematic Zoology.,Vol. 18, pp. 259-278, 1969.
[28] X.-Y. Li and G. Calinescu and P.-J. Wan,\Distributed Construction of Pla-
nar Spanner and Routing for Ad Hoc Wireless Networks," Proceedings of
the IEEE 23rd International Conference on Computer Communication (INFO-
COM)., 2002.
[29] G. Toussaint,\The Relative Neighborhood Graph of A Finite Planar set," Pat-
tern Recognition.,Vol. 12, pp. 261-268, 1980.
[30] P. Boone and E. Ch?avez and L. Gleitzky and E. Kranakis and J. Opatrny and
G. Salazar and J. Urrutia,\Morelia Test: Improving the E?ciency of the Gabriel
Test and Face Routing in Ad-Hoc Networks," Structural Information and Com-
munication Complexity (SIROCCO)., pp. 23-34, 2004.
42
[31] Y.-J. Kim and R. Govindan and B. Karp and S. Shenker,\On the pitfalls of
geographic face routing," Proceedings of the International Workshop on Dis-
crete Algothrithms and Methods for Mobile Computing and Communications
(DIALM-POMC)., pp. 34-43, 2005.
[32] D. Pompili and T. Melodia and I. F. Akyildiz,\Routing Algorithms for Delay-
Insensitive and Delay-Sensitive Applications in Underwater Sensor Networks,"
Proceedings of the ACM/IEEE International Conference on Mobile Computing
and Networking (MOBICOM)., pp. 298-309, 2006.
[33] \The Network Simulator (ns-2)," http://www.isi.edu/nsnam/ns/
[34] A. F. Harris III and M. Zorzi,\Modeling the Underwater Acoustic Channel in
ns2," Proceedings of the 2nd International Conference on Performance Evalua-
tion Methodologies and Tools (ValueTools)., pp. 1-8, 2007.
[35] G. Sidhu and R. Andrews and A. Oppenheimer,\Inside AppleTalk, Addison-
Wesley," , 1989.
[36] M. Stojanovic and J. G. Proakis and J. Catipovic,\Performance of High-Rate
Adaptive Equalization on a Shallow Water Acoustic Channel," Journal of the
Acoustical Society of America.,Vol. 100, pp. 2213-2219, 1996.
[37] R. Urick,\Principles of Underwater Sound," McGraw-Hill., 1983.
[38] L. Berkhovskikh and Y. Lysanov,\Fundamentals of Ocean Acoustics," Springer.,
1982.
[39] \Temperature of Ocean Water," The National Center for Atmospheric Reserach.,
http://www.windows.ucar.edu/tour/link=/earth/Water/temp.html
[40] L. Freitag and M. Grund and Sa. Singh and J. Partan and P. Koski and K.
Ball,\The WHOI Micro-Modem: An Acoustic Communications and Navigation
System for Multiple Platforms," Proceedings of MTS/IEEE OCEANS 2005.,Vol.
2, pp. 1086-1092, 2005.
[41] R. Ramanathan and R. Hain,\Topology Control of Multihop Wireless Networks
Using Transmit Power Adjustment," Proceedings of the IEEE 23rd International
Conference on Computer Communication (INFOCOM)., pp. 404-413, 2000.
[42] Y. Wang and X.-Y. Li,\Minimum Power Assignment in Wireless Ad Hoc Net-
works with Spanner Property," Journal of Combinatorial Optimization.,Vol. 11,
pp. 99-112, 2006.
43
[43] M. Bahramgiri and M. Hajiaghayi and V. S. Mirrokni,\Fault-Tolerant and 3-
Dimensional Distributed Topology Control Algorithms in Wireless Multi-Hop
Networks," Wireless Networks.,Vol. 12, pp. 179-188, 2006.
[44] A. Ghosh and Y. Wang and B. Krishnamachari and M. Hsieh,\E?cient Dis-
tributed Topology Control in 3-Dimensional Wireless Networks," Proceedings of
the IEEE 4th International Conference on Sensor, Mesh and Ad Hoc Communi-
cations and Networks (SECON).,Vol. 12, pp. 91-100, 2007.
[45] T. H. Cormen and C. E. Leiserson and R. L. Rivest and C. Stein,\Introduction
to Algorithms," The MIT Press; 2nd Edition., 2001.
[46] A. S. Tanenbaum,\Computer Networks," Prentice Hall PTR; 4 edition., 2002.
[47] C. Benton and J. Kenney and S. G. Chappell and D. R. Blid-
berg,\Autonomous Undersea Systems Network (AUSNET) Development Status
Update," IEEE.,Vol. 1, pp. 325-330, 2002.
[48] R. K. Creber and J. A. Rice and P. A. Baxley and C. L. Fletcher,\Performance
of Undersea Acoustic Networking using RTS/CTS Handshaking and ARQ Re-
transmission," the MTS/IEEE Conference and Exhibition (OCEANS).,Vol. 4,
pp. 2083-2086, 2001.
44