ńňđ. 39 |

lim Pr(n M 2 â€“ ln n

n

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

n

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)

n

â€“x

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-

n

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)

n

+.

197

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 [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

n

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.

2

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

n,k

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

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

n,k

n

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â€“

2

lim Pr[n ln n + (2k â€“ 3)ln ln n â€“ 2 ln (k â€“ 1)! â€“ 2 (k â€“ 2)ln 2 + ln

n,k

n

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

n,k

k

ln n â€“ 2 ln k! + + 2 ln (8k/2 ), then G(V, rn,k) is (k + 1)-connected with probability at

â€“eâ€“

least e as n goes to infinity.

6.5 CONCLUSION

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].

ACKNOWLEDGMENT

The author would like to thank Dr. Ivan Stojmenovic for some helpful suggestions in

preparing this chapter, and Dr. Mathew Penrose for reviewing it.

REFERENCES

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.

199

REFERENCES

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

1994.

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.

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),

2002.

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.

201

REFERENCES

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 |