<<

. 49
( 87 .)



>>


1 Unknown Location
5
4


3

6
2 Beacon

Figure 8.9. An example collaborative multilateration topology.
250 LOCATION DISCOVERY


The difference from the single-hop setup is that that two types of measurements need
to be considered, beacon-unknown and unknown-unknown. The former measurement is
the same type as the one described by Equation 8.3. The latter involves two unknowns that
use each other as an anchor point, and the Taylor expansion of this has the form

ri,k = f 0 + xa xb + ya yb + xb xa + yb ya + O( 2
) (8.9)
i


Note that both nodes a and b have unknown locations. The position estimates can still
be computed using an iterative solution similar to the one described in Section 8.3.4. The
matrices for the setup in Figure 8.9 will be

r1,a “ f (0)
x1,a y1,a 0 0 1,a
xa
r2,a “ f (0)
x2,a y2,a 0 0 2,a
ya
r3,b “ f (0)
0 0 x3,b y3,b
= xb , A= and z= 3,b
r4,b “ f (0)
0 0 x4,b y4,b 4,b
yb (0)
xb,a yb,a xa,b ya,b ra,b “ f a,b


Distributed Computation. The distributed computation model is an approximation to
the centralized computation model described in the previous section. Instead of estimating
locations by considering all measurements at once, each node is responsible for comput-
ing its own position estimate based on the current estimate of its neighboring nodes. In
this algorithm, each node in the network uses its neighboring nodes (both beacons and
nodes with unknown locations) to estimate its location. First the node generates a new es-
timate of its location using atomic multilateration based on the current position estimates
of its neighbors. Once the computation is completed, the node then forwards its new posi-
tion estimate to its neighbors. The neighbors with unknown locations use this information
to generate a new estimate of their locations. By repeating this action across a well-con-
strained configuration of nodes, the nodes can estimate their locations over multiple itera-
tions.
If the well-constrained configuration has more than two nodes with unknown loca-
tions, then all the nodes should generate their position updates at the same rate so that a
gradient with respect to the global constraints is formed. This can be achieved by having
nodes generate their updates sequentially using a depth-first traversal. The algorithm re-
peats until all nodes with unknown locations reache a prespecified tolerance.

Computation and Communication Tradeoffs. Besides robustness, the distributed
computation model results in considerable savings in computation. This is because in the
distributed model the matrices grow with respect to the number of neighbors of a node. In
the centralized computation model, the matrices grow much faster since their size de-
pends on the number of unknowns and the number of nodes in the network. Figure 8.10
shows a comparison of the total number of floating point operations required by MAT-
LAB to solve the same network using the centralized and distributed computation models.
The distributed computation model provides a more scalable behavior in the number of
nodes, which is highly desirable in an ad hoc setup.
In addition to the savings in computation, the distributed approach also has favorable
results on the communication patterns. Since nodes only have to communicate occasion-
251
8.5 FUTURE DIRECTIONS IN LOCATION DISCOVERY


10,000

9,000
Distributed Centralized
8,000

7,000
6,000
MFlop s




5,000

4,000
3,000

2,000

1,000

0
10 20 30 40 50 60 70 80 90 100
No. of Unknown Node s

Figure 8.10. Computation cost comparison between centralized and distributed models.




ally with their one-hop neighbors, the communication overhead is evenly divided among
all nodes. From an energy perspective, this is desirable since it avoids the uneven power
consumption caused by the forwarding of packets across a multihop network.


8.5 FUTURE DIRECTIONS IN LOCATION DISCOVERY

With the new technological developments, the application space of location-based appli-
cations is exploding. Despite this progress and the recent work described in this chapter,
localization in the ad hoc setup still imposes a set of challenges at many different levels.
At the physical layer, controlling measurement error in different environments is an issue.
Many researchers are considering the fusion of measurements from orthogonal sensing
modalities in an effort to reduce measurement uncertainties. Others are focusing on the
development of new measurement methods, and other research studies the error behavior
characteristics and provides network-level algorithms location estimates [29]. Sensor
transducer calibration is another important issue that researchers try to handle at the net-
work level. Recent efforts in this direction are described in [32].
In addition to the position estimation challenges, localization systems and protocols
need to be tightly integrated with other protocols and applications. These protocols should
handle transitions between different technologies and different location accuracies as
nodes move into environments (or hierarchical systems) supporting a diverse set of loca-
tion discovery mechanisms.
With such mechanisms in place, the application space of location-based services is ex-
pected to advance very rapidly, enabling a new era of context-aware, ubiquitous computa-
tion and communication (see Table 8.1). Such knowledge of fine-grained location infor-
mation about people and devices, however, will also impose additional problems
252 LOCATION DISCOVERY


Table 8.1. Ad Hoc Localization System Summary
Measurement
System technology Main characteristic Reported accuracy
GPSLC RF connectivity Proximity, Distributed operation Depends on beacon pattern
CPE RF connectivity Proximity, 0.64“0.72 tx range
Requires rigorous centralized
computation
GPSFP RF ToF Distributed operation, N/A
local coordinate system
LTSTS Acoustic ToF Centralized opeation, 11.5 RMS error for bases,
constructs a local 9.3 RMS error for
coordinate system small nodes
SLM& Acoustic ToF Centralized operation 0.35 m
APS Radio signal strength Distributed operation 1/3 tx range
RPAD Radio signal strength Distributed operation 1/3 randio range at 5%
or acoustic beacons
AHLoS Ultrasound ToF Distributed operation 3“5 cm



regarding security and privacy. These issues should be carefully considered before many
types of localization systems are deployed on a large scale.


REFERENCES

1. The Active Badge System, http://www.uk.research.att.com/ab.html.
2. P. Bahl, V. Padmanabhan, “An In-Building RF-based User Location and Tracking System,” Pro-
ceedings of INFOCOM 2000, Tel Aviv, Israel, vol 2, pp. 775“784, March 2000.
3. N. Bulusu, J. Heidemann, and D. Estrin, “GPS-Less Low Cost Outdoor Localization For Very
Small Devices,” IEEE Personal Communications Magazine, Special Issue on Networking the
Physical World, August 2000.
4. S. Capkun, M. Hamdi, and J. P. Hubaux, “GPS-Free Positioning in Mobile Ad-Hoc Networks,”
in Proceedings of Hawaii International Conference on System Sciences, HICCSS-34 Jan, 2001.
5. P. Castro, P. Chiu, and R. Muntz, “A Probabilistic Location Service for Wireless Network Envi-
ronments,” in Proceedings of Ubicomp 2001.
6. L. Doherty, L. El Ghaoui, and K. S. J. Pister, “Convex Position Estimation in Wireless Sensor
Networks,” in Proceedings of INFOCOM 2001, Anchorage, AK, April 2001.
7. L. Girod and D. Estrin, “Robust Range Estimation Using Acoustic Multimodal Sensing,” in
Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems
(IROS), Maui, Hawaii, October 2001.
8. R. Fontana, A. Ameti, E. Richley, L. Beard, and D. Guy, “Recent Advances In Ultra Wideband
Communications Systems,” in Proceedings of IEEE Conference on Ultra Wideband Systems
and Technologies, Baltimore, May 2002.
9. R. Fontana and S. Gunderson, “Ultra Wideband Precision Asset Location System,” in Proceed-
ings of IEEE Conference on Ultra Wideband Systems and Technologies, May 2002.
253
REFERENCES


10. W. Foy, “Position-Location Solution by Taylor Series Estimation,” IEEE Transactions on Aero-
space and Electronic Systems, AES-12, 2, 187“193, March 1976.
11. J.-P. Hubaux, J. -Y. Le Boudec, S. Giordano, M. Hamdi, Lj. Blazevic, L. Buttyan, and M. Vo-
jnovic, “Towards Mobile Ad-Hoc WANs: Terminodes,” IEEE WCNC, September 2000.
12. A. Howard, M. Mataric, and G. Sukhatme, “Relaxation on a Mesh: A Formalism for General-
ized Localization,” in Proceedings of IEEE/RSJ International Conference on Intelligent Robots
and Systems (IROS), Wailea, Hawaii, Oct. 2001.
13. J. Hightower and G. Boriello, “Location Systems for Ubiquitous Computing,” IEEE Computer,
34(8), 57“66, Aug 2001.
14. T. Imielinski and J. Navas, “GPS-Based Geographic Addressing, Routing and Resource Discov-
ery,” Communications of the ACM, 42, 4, April 1999.
15. Intersense, Inc., http://www.isense.com.
16. E. Kaplan, Understanding GPS Principles and Applications, Artech House, 1996.
17. B. Karp and H. T. Kung, “GPSR: Greedy Perimeter Stateless Routing for Wireless Networks,”
in Proceedings of Mobicom 2000.
18. A. Ladd, K. Bekris, A. Rudys, G. Marceau, L. E. Kavraki, and S. Dan, “Robotics-Based Loca-
tion Sensing Using Wireless Ethernet,” in Proceedings of Mobicom, Atlanta, Georgia, Septem-
ber 2002.
19. J. Li, J. Jannotti, D. S. J. De Couto, D. Karger, and R. Morris, “A Scalable Location Service for
Geographic Ad-Hoc Routing,” in Proceedings of Mobicom 2000.
20. A. Nasipuri and K. Li, “A Directionality Based Location Scheme for Wireless Sensor Net-
works,” in Proceedings of First ACM International Workshop on Wireless Sensor Networks and
Applications, pp. 105“111, September 28, Atlanta, Georgia 2002.
21. D. Nicolescu and B. Nath, “Ad-Hoc Positioning System,” in Proceedings of IEEE GlobeCom,
November 2001.
22. M. Mauve, J. Widmer, and H, Hartenstein, “A Survey on Position Based Routing in Mobile Ad-
hoc Networks,” IEEE Network Magazine, 15(6), 30“39, November 2001.
23. R. L. Moses and R. M. Patterson, “Self-calibration of sensor networks,” in Unattended Ground
Sensors Technologies and Applications IV (Proceedings of SPIE, Vol. 4743), E. M. Carapezza
(Ed.), pp. 108“119, April 1“4, 2002.
24. N. Priyantha, A Chakraborthy, and H. Balakrishnan, “The Cricket Location Support System,” in
Proceedings of International Conference on Mobile Computing and Networking, pp. 32“43,
Boston, August 2000.
25. RF Technologies, http://www.rftechnologies.com/pinpoint.
26. C. Savarese, J. Rabay, and K. Langendoen, “Robust Positioning Algorithms for Distributed Ad-
Hoc Wireless Sensor Networks,” in Proceedings of USENIX Technical Annual Conference, June
2002.
27. A. Savvides, C. C. Han, and M.B. Srivastava, “Dynamic Fine-Grained Localization in Ad-Hoc
Networks of Sensors,” in Proceedings of Fifth Annual International Conference on Mobile
Computing and Networking, Mobicom, pp. 166“179, Rome, Italy, July 2001.
28. A. Savvides, H. Park, and M. B. Srivastava, “The Bits and Flops of the n-Hop Multilateration
Primitive for Node localization Problems,” in Proceedings of the First International Conference
on Wireless Sensor Networks and Applications, Mobicom, September 2002.
29. S. Slijepcevic, S. Megerian, and M. Potkonjak. “Location Errors in Wireless Embedded Sensor
Networks: Sources, Models, and Effects on Applications.” ACM Mobile Computing and Com-
munications Review, 6, 3, 67“78, 2002.
30. R. Wand, A. Hopper, V. Falcao, and J. Gibbons, “The Active Bat Location System,” ACM Trans-
actions on Information Systems, pp. 91“102, January 1992.
254 LOCATION DISCOVERY


31. WhereNet, http://www.wherenet.com.
32. K. Whitehouse and D. Culler, “Calibration as Parameter Estimation in Sensor Networks,” in
Proceedings of the First ACM International Workshop on Wireless Sensor Networks and Appli-
cations, pp. 59“67, Atlanta, Georgia, September 2002.
33. H. L. Van Trees, Chapter 12 in Detection Estimation and Modulation Theory, Part I, Wiley,
1968.
34. VOR System http://www.navfltsm.addr.com/vor-nav.htm.
CHAPTER 9




MOBILE AD HOC NETWORKS (MANETs):
ROUTING TECHNOLOGY FOR DYNAMIC
WIRELESS NETWORKING

JOSEPH P. MACKER and M. SCOTT CORSON




The fact that mobile networking is a “hot” topic of present technology research and devel-
opment hardly needs stating. Recent technical publications are inundated with reports of
promising technologies and approaches for a better wireless future. This is understand-
able, as wireless networking is expanding into many varied dimensions of application
space. Wireless data networking was once viewed as a highly limited business, with ac-
cess obtainable only by privileged players or amateur operators. Yet, it is now seen as a
rapidly expanding general business and public resource. Much of this is due to the prolif-
eration of low-cost, low-power, high-capacity wireless local area network (WLAN) tech-
nologies. The reusability of the radio spectrum and widespread deployment of the unli-
censed spectrum is now standard practice across society and is being applied within a
diverse set of industries. With the recent explosion of inexpensive home and business

<<

. 49
( 87 .)



>>