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  is ac-
tually stronger than that in  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 , 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  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)
6.4 STOCHASTIC GEOMETRY
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 , 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  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  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  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  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  studied the maxi-
mum length of the graph by connecting every node to its k nearest neighbors asymptoti-
cally. Li et al.  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 , 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  conducted the experiments to study the relations of the k-connectivi-
ty and the minimum node degree using a toroidal model. Li et al.  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. 
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  provided a method to construct a spanner that can sustain k-nodes or k-
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
198 TOPOLOGY CONTROL IN WIRELESS AD HOC NETWORKS
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  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  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  and , Li
et al.  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 .
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
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
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,
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,
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.
200 TOPOLOGY CONTROL IN WIRELESS AD HOC NETWORKS
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.