<< Предыдущая стр. 39(из 87 стр.)ОГЛАВЛЕНИЕ Следующая >>
) = eвЂ“eвЂ“
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  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
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 , 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)
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 , 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
n

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.
2
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
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 , 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
n,k
n

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вЂ“
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  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
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 .

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(из 87 стр.)ОГЛАВЛЕНИЕ Следующая >>