. 45
( 87 .)


Hoc Wireless Networks Using Connected Dominating Sets,” in Proceedings of IASTED WOC
02, July 2002; Wireless Communications and Mobile Computing, 3, 4, 425“438, June 2003.
53. L. M. Feeney and M. Nilsson, “Investigating the Energy Consumption of a Wireless Network
Interface in an Ad Hoc Networking Environment,” in Proceedings of IEEE INFOCOM, 2001.
54. Y. Xu, J. Heidemann, and D. Estrin, “Geography-informed Energy Conservation for Ad Hoc
Networks,” in Proceedings of MobiCom, 2001.
55. B. Chen, K. Jamieson, H. Balakrishnan, and R. Morris, “Span: An Energy-Efficient Coordina-
tion Algorithm for Topology Maintenance in Ad Hoc Wireless Networks,” in Proceedings of
ACM MobiCom, 2001.
56. L. M. Feeney, “A QoS Aware Power Save Protocol for Wireless Ad Hoc Networks,” in Proceed-
ings of Mediterranean Workshop on Ad Hoc Networks Med-Hoc, Sardinia, Italy, Sept., 2002.
57. Di Tian and N. Georganas, “A Node Scheduling Scheme for Energy Conservation in Large
Wireless Sensor Networks,” Wireless Networks and Mobile Computing, 3, 2, 271“290, 2003.
58. W. R. Heinzelman, J. Kulik, and H. Balakrishnan, “Adaptive Protocols for Information Dissem-
ination in Wireless Sensor Networks,” in Proceedings of ACM MobiCom, Seattle, pp. 174“185,
59. M. Seddigh, J. Solano Gonzalez, and I. Stojmenovic, “RNG and Internal Node Based Broad-
casting Algorithms for Wireless One-to-One Networks,” ACM Mobile Computing and Commu-
nications Review, 5, 2, 37“44, 2001.
60. G. Toussaint, “The Relative Neighborhood Graph of a Finite Planar Set,” Pattern Recognition,
12, 4, 261“268, 1980.
61. J. Cartigny, D. Simplot, I. Stojmenovic, “Localized Energy Efficient Broadcast for Wireless
Networks,” in Proceedings of IEEE INFOCOM, 2003.
62. J. E. Wieselthier, G. D. Nguyen, and A. Ephremides, “On the Construction of Energy-Efficient
Broadcast and Multicast Trees in Wireless Networks,” in Proceedings of IEEE INFOCOM, Tel
Aviv, Israel, pp. 585“594., 2000
63. J. Cartigny, D. Simplot, and I. Stojmenovic, “Localized Energy Efficient Broadcast for Wireless
Networks with Directional Antennas,” in Proceedings of Mediterranean Workshop on Ad Hoc
Networks Med-Hoc, Sardinia, Italy, Sept., 2002.
64. J. Lipman, P. Boustead, and J. Judge, “Efficient and Scalable Information Dissemination in Mo-
bile Ad Hoc Networks,” in Proceedings of the First International Conf. on Ad-hoc Networks and
Wireless ADHOC-NOW, Toronto, September 2002, pp. 119“134.
65. P. Jacquet, A. Laouiti, P. Minet, and L. Viennot, “Performance of Multipoint Relaying in Ad
Hoc Mobile Routing Protocols,” in Proceedings of IFIP Networking 2002, Pisa, Italy, pp.
387“398, May 2002.
66. M. Mosko and J. J. Garcia-Luna-Aceves, “Performance of Group Communication over Ad Hoc
Networks,” in Proceedings of IEEE International Symposium on Computers and Communica-
tions ISCC, Taormina, Italy, July 2002, pp. 545“552.
67. J. Shaikh, J. Solano, I. Stojmenovic, and J. Wu, “New Metrics for Dominating Set Based Energy
Efficient Activity Scheduling in Ad Hoc Networks,” in Proceedings of WLN Workshop at IEEE
Conference on Local Computer Networks, Bonn, Germany, October 20“24, 2003.
68. D. M. Blough and P. Santi, “Investigating Upper Bounds on Network Lifetime Extension for
Cell-Based Energy Conservation Techniques in Stationary Ad Hoc Networks,” in Proceedings
of ACM MobiCom, Atlanta, Sept. 2002.




Location discovery is a broad topic that has received considerable attention from the re-
search community during the past few decades. Its significance stems from its wide spec-
trum of applications ranging from navigation to context-aware applications in ubiquitous
computing. As expected, the location requirements vary across applications, resulting in the
development of a rich and diverse set of technologies and location discovery algorithms. In
cellular telephony systems, for example, knowledge of handset locations is primarily re-
quired for routing calls to mobile users. Such location is found either by observing the re-
ceived signal strength of a broadcast signal transmitted by the base stations or by measur-
ing the round-trip signal propagation time between a handset and a set of base stations.
Although cell-level localization granularity is sufficient for routing calls to mobile
handset users, new applications require more precise handset locations. The main motiva-
tor for these applications was the 1996 Federal Communications Commission (FCC) sec-
ond-phase mandate for E911 (enhanced 911) services, which required that by October 1st,
2001 all cellular carriers should be able locate phones that make 911 emergency calls
within 50“100 meters, in most cases either by triangulating the positions of handsets that
used the received signals or by using GPS [15]. Although the FCC requirements where
not entirely met in October 2001 and many extensions and waivers have been granted by
the FCC, the E911 mandate has spawned an entirely new industry for location-aware ap-
plications, formally named location-based services (LBS). Since then, LBS has become a
rapidly growing market and, according to the ARC Group (http://www.arcgroup.com),
will grow to U.S. $11 billion in North America, U.S. $13 billion in Asia Pacific, and U.S.
$12 billion in Europe.

Mobile Ad Hoc Networking. Edited by Basagni, Conti, Giordano, and Stojmenovic.
ISBN 0-471-37313-3 © 2004 Institute of Electrical and Electronics Engineers, Inc.

The background infrastructure development for LBS services over cellular networks is
well underway. A notable example is the Qualcomm gpsOne chipset, which provides low-
cost GPS-based technologies with 5 to 10 meter accuracy outdoors and 20 meter accuracy
in indoor and suburban environments, making it the key enabler for numerous LBS appli-
cations. Another two companies in the United States, TeleCommunication Systems Inc.
(TCS) and LocatioNet, have recently created the messaging and middleware infrastruc-
tures for developing LBS applications such as point-of-interest (i.e., where are the closest
ATM machines, restaurants, movie theaters, etc.), driving directions, and navigation,
friend-finder applications (are any of my friends or family nearby?) and mobile com-
merce applications (are there any deals today in this mall?), yellow page services, and
child safety services.
Besides the cellular technologies and LBS, location discovery is the key enabler for a
plethora of applications across different domains ranging from navigation systems to virtu-
al reality and augmented systems. Asset and personnel tracking, access control, location-
specific billing services, automated inventory control, power control in smart buildings,
camera motion tracking, various security applications, and user-context transfer according
to user location are just a few of the applications that will revolutionize a whole new era of
ubiquitous computing and communication. For the great majority of applications, location
discovery is mutually coupled with networking technologies. Location-aware applications
require networking support to function, whereas networking protocols and applications, on
the other hand, can greatly benefit from utilizing knowledge of location.

8.1.1 The Impact of Location Discovery on Ad Hoc Networks
In ad hoc wireless networks and wireless sensor networks, location discovery plays a ma-
jor role in the development of geographic-aware routing and multicasting protocols that
result in new more efficient ways for routing data in multihop networks that span large ge-
ographic regions. Furthermore, with the inexorable progress of wireless and MEMS tech-
nologies, and the ever-expanding application space of wireless sensor networks, location
discovery is becoming an indispensable component for establishing correspondence be-
tween the Internet and the physical world.
Geographic routing protocols such as GPSR, described in [17], use geographic infor-
mation at the node level to make localized decisions based on the current position of a for-
warding node and the geographic location of the destination. This localized decision
process relaxes the requirements for maintaining massive amounts of state information at
each node, and reduces the amount of traffic generated during the route discovery
process, thus enabling network scalability to large number of nodes spanning large re-
gions. The core component of such geographic routing protocols is a geographic forward-
ing algorithm, which decides the next-hop destination of a packet based on the coordi-
nates of the forwarding node and knowledge of the geographic location of the destination.
If the destination is provided as a particular geographic region, then the packet-forwarding
mechanisms are sufficient to deliver the packets to the destination. If the a node address is
used as a destination, then the packet-forwarding mechanisms also require the support of
location services such as those described in [19] to establish the correspondence between
a node address and the current geographical location of the node. A detailed survey of ge-
ographic-aware protocols is provided in [22].
Geographic multicasting protocols make use of location information in a similar man-
ner to control-packet flooding to user-specified regions of the network. Furthermore, in

wireless sensor networks, knowledge of sensor locations is required to correctly report the
origins of events when setting alarms, to assist with target tracking, to evaluate network
coverage, and to perform different network maintenance tasks (e.g., replace the batteries
on specific sensor nodes).
The remainder of this chapter is organized as follows: The first half of the chapter pro-
vides a brief background on location discovery and surveys the existing location discov-
ery systems. The second half of the chapter focuses on the recent developments in ad hoc
location discovery.


8.2.1 What is Location?
The term “location” is used in many contexts to denote the position of an object in physi-
cal space with respect to a specific frame of reference that varies across applications. In
the case of the Global Positioning System (GPS), absolute location is provided in terms of
latitude, longitude, and altitude. In the terrestrial counterpart of GPS, the LORAN system,
locations are usually given with respect to fixed beacon locations. In some applications
that also use inertial sensors such as accelerometers, magnetometers, odometers, and gy-
roscopes, locations are usually referenced with respect to a starting point, whereas in in-
door systems, locations are usually provided according a local coordinate system that rep-
resents the dimensions of an area of interest or the building coordinates.
Location discovery is fundamentally based on two main phases: a measurement phase
that produces a set of measurements of distance, angularly or optically to/from a set of an-
chor points; and a combining phase that combines the measurements to produce a final
estimate. The granularity of the derived locations depends on the accuracy of the measure-
ment technologies used and the sophistication of the algorithms employed to combine the
measurements. For many applications, where cost and simplicity are the dominating deci-
sion factors, the determination of proximity is adequate, whereas in other applications
such as robotic navigation systems and augmented reality applications, fine-grained loca-
tions of objects with centimeter-level accuracies are required.

8.2.2 Measurement Technologies
Measurements are made using different techniques that leverage known characteristics of
signal propagation. The most common measurement methods used in location discovery
systems are received signal strength, time-based, and directional methods and they are
typically applied to radio, acoustic, or optical signals. Inertial measurement is also a pop-
ular measurement method, especially in the fields of mobile robotics and augmented real-
ity systems.
Signal-strength-based methods make use of signal attenuation with distance to deter-
mine proximity. These methods are not used for accurate distance measurements because
of the large variations in signal attenuation in different environments, especially when
multipath and shadowing effects are present. Instead, signal-strength-based methods are
used to determine proximity or are combined with other methods to determine locations.
Olivetti™s active badge system [1] is based on infrared base stations deployed in each
room. Each active badge in a certain room can determine if it can receive an infrared sig-
nal from that room. RFID tags work in a similar manner using strategically placed tag

readers. In this case, the locations of tags can be determined relative to their proximity to
tag readers. The GPS-less localization system proposed by Bulusu et al. [3] uses signal re-
ception to determine proximity. A node can determine its proximity to be the centroid of
the beacons from which it can receive packets. Microsoft™s RADAR system [2], for exam-
ple, uses radio received signal strength on wireless network cards during an offline phase
to create signal strength maps of a building based on the receiver signal strength measure-
ments to different base stations placed around the building. With the help of these maps,
the system is then able to determine user locations within the building. A similar approach
is used in various localization systems that use Bayesian estimation schemes. First, the
system is trained by creating a probabilistic model based on received signal strength and
then these models are used to estimate user locations.
Time-based methods measure distances by recording the time of flight (ToF) of a signal
from the transmitter to the receiver. One type of time-based methods assumes that the re-
ceiver and the transmitter are time synchronized, so the ToF of a signal to reach the receiv-
er can be accurately recorded. The GPS system is an example of such a system. In GPS, the
satellites transmit a code and each receiver locally generates a replica of the signal. When
the signals transmitted from the satellite arrive at the receiver, the receiver compares the re-
ceived code with the locally generated replica to determine ToF. Since the satellite clocks
and the receiver clock are not perfectly time synchronized, in practice the receiver combines
an additional satellite reading and simultaneously computes the time drift between the re-
ceiver and satellite clocks. Another type of ToF method uses two signals with different
propagation speeds. The time difference between the arrivals of the two signals is used to
determine distances. An example system that uses this approach is Active Bat from AT\&T
Cambridge research labs [30]. Active Bat uses RF signals to synchronize the receiver to the
transmitter so that the ToF of an ultrasonic signal can be accurately recorded. Finally, a third
type of time-based method uses the round-trip time of a signal to determine distance. In
such systems, the receiver will transmit back the receiver signal immediately upon recep-
tion or right after a deterministic delay period. The transmitter records the roundtrip time of
this signal to determine distances. The PinPoint system manufactured by RF Technologies
[25] operates in this fashion. Other systems employ ToF methods that measure distances us-
ing Ultra Wide Band (UWB) radios [8] and laser ranging systems. Finally, another notable
distance measurement technique based on wideband acoustics has been developed by
Girod et al. [7]. By encoding the signal and transmitting at different frequencies, this sys-
tem provides robust distance measurement in the presence of interference.
Directional methods use angle of arrival (AoA) or direction of arrival (DoA) for com-
puting locations. The VHF Omnidirectional Range navigation system (VOR) [34] used in
airplane navigation is an example of a direction-based system. The basic principle of op-
eration of the VOR is very simple: the VOR facility transmits two signals at the same
time. One signal is constant in all directions, while the other is rotated about the station.
The airborne equipment receives both signals, looks (electronically) at the difference be-
tween the two signals, and interprets the result as a radial distance from the station. The
system proposed in [20] uses RF transmissions from rotating directional antennas to de-
termine the locations of wireless sensor nodes.

8.2.3 Geometric Algorithms for Location Discovery
The location of an object can be computed if the set of measurements to a set of land-
marks is known. If the measurements are distances, at least three noncollinear measure-

x1 x3 d3
Base Station 1
x2 Base Station 1
Base Station 3
Base Station 3
Mobile node
Mobile node

(a) (b)
(a) (b)
= =
Sines Rule:
sin a sin b sin c
C 2 = A 2 + B 2 + 2 AB cos(c)


. 45
( 87 .)