. 39
( 87 .)


) = e“e“
lim Pr(n M 2 “ ln n

for any fixed real number . Here Pr(X) is the probability of event X. Remember that the
longest edge of EMST is always the critical power [26, 51]. Thus, the result in [71] is ac-
tually stronger than that in [72] since it will give the probability that the network is con-
nected. For example, if we set = ln ln n, we have Pr(n M 2 ln n + ln ln n) = e“1/ln n. It
implies that the network is connected with probability at least e“1/ln n if the transmission
radius of each node rn satisfies n r 2 = ln n + ln ln n. Notice that e“1/ln n > 1 “ (1 “ ln n)
from e > 1 “ x for x > 0. By setting = ln n, the probability that the graph G(V, rn) is
connected is at least e“1/n > 1 “ (1/n), where n r 2 = 2 ln n. Notice that the above probabil-
ity is only true when n goes to infinity. When n is a finite number, then the probability of
the graph being connected is smaller. In [73], Li et al. presented the experimental study of
the probability of the graph G(V, rn) being connected for finite number n.
One closely related question is the coverage problem: disks of radius r are placed in a
two-dimensional unit-area disk D with centers from a Poisson point process with intensity
n. A result shown by Hall [87] implies that, if n · r2 = ln n + ln ln n +c(n) and c(n) ,
then the probability that there is a vacancy area in D is 0 as n goes infinity; if c(n) “,
the probability that there is a vacancy in D is at least 1/20. This implies that the hitting ra-
dius rn such that G(V, rn) is connected satisfies · r 2 4[ln n + ln ln n + c(n)/n] for c(n)

Let B[n, p(n)] be the set of graphs on n nodes in which each edge of the completed
graph Kn is chosen independently with probability p(n). Then it has been shown that the
probability that a graph in B[n, p(n)] is connected goes to one if p(n) = [ln n + c(n)/n] for
any c(n) . Although their asymptotic expressions are the same as those by Gupta and
Kumar [72], we cannot apply this to the wireless model as, in wireless networks, the exis-
tences of two edges are not independent, and we do not choose edges from the completed
graph using the Bernoulli model.
For geometric graphs, it was proved by Penrose [74] that, given any metric lp with 2
p and any positive integer k,

lim Pr[ (Xn, k) = (Xn, k)] = 1

The result is analogous to the well-known results in the graph theory [75] that a graph be-
comes k-vertex connected when it achieves the minimum degree k if we add the edges
randomly and uniformly from ( n )! possibilities.
This result by Penrose [74] says that a graph of G(Xn, r) becomes k-connected almost
surely at the moment it has minimum degree k by letting r go from 0 to . However, this
result does not imply that, to guarantee a graph over n points k-connected almost surely,
we only have to connect every node to its k-nearest neighbors. Let V be n points randomly
and uniformly distributed in a unit square (or disk). Xue and Kumar [86] proved that, to
guarantee a geometry graph over V connected, the number of nearest neighbors that every
node has to connect is asymptotically (ln n). Dette and Henze [76] studied the maxi-
mum length of the graph by connecting every node to its k nearest neighbors asymptoti-
cally. Li et al. [73] showed that, given n random points V over a unit-area square, to guar-
antee a geometry graph over V k-connected, the number of nearest neighbors that every
node has to connect is asymptotically ln n + (2k “ 3)ln ln n.
Similarly, instead of considering Xn, Penrose also considered a homogeneous Poisson
point process with intensity n on the unit-area square C. Penrose gave loose upper and
k) as (ln n/2d+1) nr d
lower bounds on the hitting radius rn,k = (Pn, d!2 ln n for a
homogeneous Poisson point process on a d-dimensional unit cube, This result is too loose.
More importantly, the parameter k does not appear in this estimation at all. In [73], a
tighter bound on rn,k was derived for two-dimensional n points V randomly and uniformly
distributed in C such that the graph G(V, rn,k) is k-connected with high probability.
Bettstetter [79] conducted the experiments to study the relations of the k-connectivi-
ty and the minimum node degree using a toroidal model. Li et al. [73] also conducted
experiments to study the probability that a graph has minimum degree k and has vertex
connectivity k simultaneously using a Euclidean model. Surprisingly, they found that
this probability is sufficiently close to 1 even when n is at the scale of 100. This obser-
vation implies a simple method (by just computing the minimum vertex degree) to ap-
proximate the connectivity of a random geometry graph. Recently, Bahramgiri et al. [20]
showed how to decide the minimum transmission range of each node such that the re-
sulting directed communication graph is k-connected. Here, it is assumed that the unit
disk graph, by setting each node with the maximum transmission range, is k-connected.
Lukovszki [88] provided a method to construct a spanner that can sustain k-nodes or k-
links failures.
Penrose [71, 74] also studied the k-connectivity problem for d-dimensional points dis-
tributed in a unit-area cube using the toroidal model instead of the Euclidean model as

one way to eliminate the boundary effects. He showed that the hitting radius rn,k such that
the graph G(V, rn,k) is k-connected satisfies

ln n + (k “ 1) ln ln n “ ln (k “ 1)! + ] = e“e“
lim Pr[n r 2

Dette and Henze [76] studied the largest length, denoted by n,k here, of the kth nearest
neighbor link for n points drawn independently and uniformly from the d-dimensional
unit-length cube or the d-dimensional unit volume sphere. They gave asymptotic results
of this length according to k < d, k = d, or k < d. For unit-volume cube, they use the norm
l instead of l2. For the unit-volume sphere, their result implies that when d = 2 and k > 2,

+ 2 ] = e“e“
lim Pr[n ln n + (2k “ 3)ln ln n “ 2 ln (k “ 1)! “ 2 (k “ 2)ln 2 + ln

Notice that, Penrose [74] had showed that when the domain is a unit-area square, the prob-
ability that a random geometry graph G(V, rn,k) is k-connected and has minimum vertex
degree k goes to 1 as n goes to infinity. Following from a combination of [76] and [74], Li
et al. [73] showed that if the transmission range rn,k satisfies n · r 2 ln n + (2k “ 1) ln
ln n “ 2 ln k! + + 2 ln (8k/2 ), then G(V, rn,k) is (k + 1)-connected with probability at
least e as n goes to infinity.


Wireless ad hoc networks have attracted considerable attention recently due to their poten-
tial wide applications in various areas and, moreover, the ubiquitous computing. In this
chapter, we presented an overview of the recent progress in topology control and localized
routing in wireless ad hoc networks. Nevertheless, there are still many excellent results
that are not covered in this survey due to space limitations.
There are many interesting open questions for topology control in wireless ad hoc net-
works. First, we would like to know whether the YaoYao structure YYk(V [and, similarly,
the structure YHk(V)] is a length spanner. Second, when the overhead cost c of signal
transmission is not negligible, are the structures reviewed here still power spanners? Third,
how can one control the network topology when different nodes have different transmis-
sion ranges such that the topology has some nice properties? Fourth, can we design a lo-
calized routing protocol that achieves constant ratio of the length of the found path to the
minimum? The answer is probably negative; see [89].


The author would like to thank Dr. Ivan Stojmenovic for some helpful suggestions in
preparing this chapter, and Dr. Mathew Penrose for reviewing it.


1. S. Capkun, M. Hamdi, and J. P. Hubaux, “Gps-Free Positioning in Mobile Ad-Hoc Networks,”
in Proceedings of the Hawaii International Conference on System Sciences, 2001.

2. P. Sinha, R. Sivakumar, and V. Bharghavan, “Cedar: Core Extraction Distributed Ad Hoc Rout-
ing,” in Proceedings of IEEE INFOCOMM ™99, 1999.
3. B. Das and V. Bharghavan, “Routing in Ad-Hoc Networks Using Minimum Connected Domi-
nating Sets,” in 1997 IEEE International Conference on Communications (ICC™97), 1997, vol.
1, pp. 376“380.
4. J. Wu and H. Li, “A Dominating-Set-Based Routing Scheme in Ad Hoc Wireless Networks,”
Telecommunication Systems Journal, 3, 63“84, 2001.
5. I. Stojmenovic, M. Seddigh, and J. Zunic, “Dominating Sets and Neighbor Elimination Based
Broadcasting Algorithms in Wireless Networks,” IEEE Transactions on Parallel and Distributed
Systems, 13, 1, 14“25, 2002.
6. K. M. Alzoubi, P.-J. Wan, and O. Frieder, “New Distributed Algorithm for Connected Dominat-
ing Set in Wireless Ad Doc Networks,” in Proceedings of HICSS, Hawaii, 2002.
7. P.-J. Wan, K. M. Alzoubi, and O. Frieder, “Distributed Construction of Connected Dominating
Set in Wireless Ad Hoc Networks,” in Proceedings of INFOCOM, 2002.
8. Y. Wang and X.-Y. Li, “Geometric Spanners for Wireless Ad Hoc Networks,” in Proceedings of
22nd IEEE International Conference on Distributed Computing Systems (ICDCS), 2002.
9. X.-Y. Li, “Algorithmic, Geometric and Graphs Issues in Wireless Networks,” Survey paper in
WCMC, 2002.
10. C. E. Perkins and E. M. Royer, “Ad-Hoc on Demand Distance Vector routing,” in Proceedings
of the 2nd IEEE Workshop on Mobile Computing Systems and Applications, New Orleans, pp.
90“100, February 1999.
11. J. Broch, D. Johnson, and D. Maltz, “The Dynamic Source Routing Protocol for Mobile Ad Hoc
Networks,” 1998.
12. C. E. Perkins and P. Bhagwat, “Highly Dynamic Destination-Sequenced Distance-Vector Rout-
ing (dsdv) for Mobile Computers,” Computer Communications Review, 234“244, October
13. M. Joa-Ng and I-T. Lu, “A Peer-to-Peer Zone-Based Two-Level Link State Routing for Mobile
Ad Hoc Networks,” IEEE Journal on Selected Areas in Communication, 17, 8, 1415“1425,
August 1999.
14. Vincent D. Park and M. Scott Corson, “A Highly Adaptive Distributed Routing Algorithm for
Mobile Wireless Networks,” in Proceedings of IEEE INFOCOM, 1997.
15. E. Royer and C. Toh, “A Review of Current Routing Protocols for Ad-Hoc Mobile Wireless
Networks,” IEEE Personal Communications, April 1999.
16. P. Bose, P. Morin, I. Stojmenovic, and J. Urrutia, “Routing with Guaranteed Delivery in Ad Hoc
Wireless Networks,” ACM/Kluwer Wireless Networks, 7, 6, 609“616, 2001; Third International
Workshop on Discrete Algorithms and methods for mobile computing and communications,
1999, 48“55.
17. B. Karp and H. T. Kung, “Gpsr: Greedy Perimeter Stateless Routing for Wireless Networks,” in
ACM/IEEE International Conference on Mobile Computing and Networking, 2000.
18. M. Mauve, J. Widmer, and H. Harenstein, “A Survey on Position-Based Routing in Mobile Ad
Hoc Networks,” IEEE Network Magazine, 15, 6, 30“39, 2001.
19. I. Stojmenovic and X. Lin, “Power-Aware Localized Routing in Wireless Networks,” in IEEE
International Parallel and Distributed Processing Symposium, 2000.
20. M. Bahramgiri, M. T. Hajiaghayi, and V. S. Mirrokni, “Fault-Tolerant and 3-Dimensional Dis-
tributed Topology Control Algorithms in Wireless Multi-Hop Networks,” in Proceedings of the
11th Annual IEEE Internation Conference on Computer Communications and Networks (ICC-
CN), 2002, pp. 392“397.
21. M. Grünewald, T. Lukovszki, C. Schindelhauer, and K. Volbert, “Distributed Maintenance of
Resource Efficient Wireless Network Topologies,” 2002, Submitted for publication.

22. L. Hu, “Topology Control for Multihop Packet Radio Networks,” IEEE Trans. Communica-
tions, 41, 10, 1993.
23. Li Li, Joseph Y. Halpern, Paramvir Bahl, Yi-Min Wang, and Roger Wattenhofer, “Analysis of a
Cone-Based Distributed Topology Control Algorithms for Wireless Multi-Hop Networks,” in
ACM Symposium on Principle of Distributed Computing (PODC), 2001.
24. L. Lloyd, Rui Liu, Madhav V. Marathe, Ram Ramanathan, and S. S. Ravi, “Algorithmic Adpects
of Topology Control Problems for Ad Hoc Networks,” in IEEE MOBIHOC, 2002.
25. S. Narayanaswamy, V. Kawadia, R. Sreenivas, and P. Kumar, “Power Control in Ad-Hoc Net-
works: Theory, Architecture, Algorithm and Implementation of the Compow Protocol,” in Euro-
pean Wireless Conference, 2002.
26. R. Ramanathan and R. Rosales-Hain, “Topology Control of Multihop Wireless Networks Using
Transmit Power Adjustment,” in IEEE INFOCOM, 2000.
27. Y.-C. Tseng, Y.-N. Chang, and B.-H. Tzeng, “Energy-Efficient Topology Control for Wireless
Ad Hoc Sensor Networks,” in Proceedings of International Conference on Parallel and Distrib-
uted Systems (ICPADS), 2002.
28. R. Wattenhofer, L. Li, P. Bahl, and Y.-M. Wang, “Distributed Topology Control for Wireless
Multihop Ad-Hoc Networks,” in IEEE INFOCOM™01, 2001.
29. R. Rajaraman, “Topology Control and Routing in Ad Hoc Networks: A survey,” SIGACT News,
33, 60“73, 2002.
30. Godfried T. Toussaint, “The Relative Neighborhood Graph of a Finite Planar Set,” Pattern
Recognition, 12, 4, 261“268, 1980.
31. K. R. Gabriel and R. R. Sokal, “A New Statistical Approach to Geographic Variation Analysis,”
Systematic Zoology, 18, 259“278, 1969.
32. P. Bose, L. Devroye, W. Evans, and D. Kirkpatrick, “On the Spanning Ratio of Gabriel Graphs
and Beta-Skeletons,” in Proceedings of the Latin American Theoretical Infocomatics (LATIN),
33. X.-Y. Li, P.-J. Wan, and Y. Wang, “Power Efficient and Sparse Spanner for Wireless Ad Hoc
Networks,” in IEEE International Conference on Computer Communications and Networks
(ICCCN01), pp. 564“567, 2001.
34. T. Lukovszki, New Results on Geometric Spanners and Their Applications, Ph. D. thesis, Uni-
versity of Paderborn, 1999.
35. X.-Y. Li, P.-J. Wan, Y. Wang, and O. Frieder, “Sparse Power Efficient Topology for Wireless
Networks,” in IEEE Hawaii International Conference on System Sciences (HICSS), 2002.
36. S. Arya, G. Das, D. Mount, J. Salowe, and M. Smid, “Euclidean Spanners: Short, Thin, and
Lanky,” in Proceedings of 27th ACM STOC, pp. 489“498, 1995.
37. Y. Wang and X.-Y. Li, “Distributed Spanner with Bounded Degree for Wireless Ad Hoc Net-
works,” in International Parallel and Distributed Processing Symposium: Parallel and Distrib-
uted Computing Issues in Wireless Networks and Mobile Computing, April 2002.
38. H. B. Hunt III, M. V. Marathe, V. Radhakrishnan, S. S. Ravi, D. J. Rosenkrantz, and R. E.
Stearns, “NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric
Graphs,” Journal of Algorithms, 26, 2, 238“274, 1999.
39. X.-Y. Li, I. Stojmenovic, and Y. Wang, “Partial Delaunay Triangulation and Degree Limited Lo-
calized Bluetooth Multihop Scatternet Formation,” 2002, Submitted for publication. The short
version appeared at AdHocNow, 2002.
40. S. Datta, I. Stojmenovic, and J. Wu, “Internal Node and Shortcut Based Routing with Guaran-
teed Delivery in Wireless Networks,” Cluster Computing, 5, 2, 169“178, 2002.
41. I. Stojmenovic and S. Datta, “Power and Cost Aware Localized Routing with Guaranteed Deliv-
ery in Wireless Networks,” in Proc. Seventh IEEE Symposium on Computers and Communica-
tions ISCC, 2002.

42. M. Seddigh, J. Solano Gonzalez, and I. Stojmenovic, “Rng and Internal Node Based Broadcast-
ing Algorithms for Wireless One-to-One Networks,” ACM Mobile Computing and Communica-
tions Review, 5, 2, 37“44, 2002.
43. D. P. Dobkin, S. J. Friedman, and K. J. Supowit, “Delaunay Graphs are Almost as Good as Com-
plete Graphs,” Discr. Comp. Geom., 399“407, 1990.
44. J. M. Keil and C. A. Gutwin, “The Delaunay Triangulation Closely Approximates the Complete
Euclidean Graph,” in Proc. First Workshop Algorithms Data Structure (LNCS 382), 1989.
45. J. M. Keil and C. A. Gutwin, “Classes of Graphs which Approximate the Complete Euclidean
Graph,” Discr. Comp. Geom., 7, pp. 13“28, 1992.
46. X.-Y. Li, G. Calinescu, and P.-J. Wan, “Distributed Construction of Planar Spanner and Routing
for Ad Hoc Wireless Networks,” in 21st Annual Joint Conference of the IEEE Computer and
Communications Societies (INFOCOM), vol. 3, 2002.


. 39
( 87 .)