Distributed topology control of wireless networks
Tóm tắt
We propose and analyaze a distributed control law that will maintain prescribed local properties of a wireless ad hoc network in the presence of node mobility, MAC layer power control and link fades. The control law uses a simple and intuitive power adaptation mechanism. We consider as an example the topology requirement of maintaining the out-degrees of each node at prescribed values and keeping the in-degree close to the out-degree. The topology objective is achieved by adapting the transmission power based only on local information. This power adaptation algorithm is analyzed using the o.d.e. approach to stochastic approximation. Simulation results verify the analysis and demonstrate its effectiveness. We also study the ability of the proposed objective to maintain connectivity. Although many heuristics are described in the literature to maintain local topological properties, the algorithm proposed in this paper is the first one that has proven convergence properties.
Tài liệu tham khảo
M. Benaim, Dynamics of stochastic approximations, in: Le Seminaire de Probabilites, eds. J. Azema, et al. Springer Lecture Notes in Mathematics no. 1709 (Springer Verlag, Berlin-Heidelberg, 1999) pp. 1–68.
M. Benaim and M.W. Hirsch, Stochastic approximation algorithms with constant stepsize whose average is cooperative, The Annals of Applied Probability 9 (1999) 216–241.
A. Benveniste, M. Metivier and P. Priouret, Adaptive Algorithms and Stochastic Approximations (Springer Verlag, Berlin-Heidelberg, 1990).
V.S. Borkar, Stochastic approximations with two time scales, Systems and Control Letters 29 (1997) 291–294.
V.S. Borkar, Asynchronous stochastic approximation, SIAM Journal of Control and Optimization 36 (1998) 840–851.
V.S. Borkar and S.P. Meyn, The O.D.E. approach to convergence of stochastic approximation and reinforcement learning, SIAM Journal of Control and Optimization 38(2) (2000) 447–469.
M.P. Desai and D. Manjunath, On the connectivity of finite ad hoc networks, IEEE Communications Letters 10(6) (2002) 437–490.
G. Foschini and Z. Miljanic, A simple distributed autonomous power control algorithm and its convergence, IEEE Transactions on Vehicular Technology 42(4) (1993).
J. Gomez, A.T. Campbell, M. Naghshineh and C. Bisdikian, Conserving transmission power in wireless ad hoc networks, in: Proceedings of Ninth IEEE Conference on Network Protocols (ICNP) (2001).
P. Gupta and P.R. Kumar, Critical power for asymptotic connectivity in wireless networks, in: Stochastic Analysis, Control, Optimization and Applications: A Volume in Honor of W.H. Fleming, eds W.M. McEneaney, G. Yin and Q. Zhang (Birkhüser, Boston, 1998).
M.W. Hirsch, Systems of differential equations that are competitive or cooperative II: Convergence almost everywhere, SIAM Journal of Mathematical Analysis 16 (1985) 423–439.
T. Hou and V. Li, Transmission range control in multihop packet radio networks, IEEE Transactions Communications 34 (1986) 38–44.
D.B. Johnson, D.A. Maltz, Y.-C. Hu and J.G. Jetcheva, The dynamic source routing protocol (DSR) for mobile ad hoc networks, Internet Draft: draft-ietf-manet-dsr-07.txt (21 February 2002).
V. Kawadia and P.R. Kumar, Power control and clustering in ad hoc networks, in: Proceedings of IEEE INFOCOM (2003).
V. Kawadia and P.R. Kumar, Power control in ad hoc networks, To appear in IEEE Journal on Selected Areas in Communications, Preprint available from http://black1.csl.uiuc.edu/∼prkumar.
L. Kleinrock and J.A. Silvester, Optimum transmission radii in packet radio networks or why six is a magic number, in: Proceedings of the National Telecommunications Conference, Birmingham, Alabama (1978) pp. 04.3.1–5.
H.J. Kushner and G.G. Yin, Stochastic Approximation Algorithms and Applications (Springer Verlag, New York, 1997).
L. Li, J.Y. Halpern, V. Bahl, Y.M. Wang and R. Wattenhofer, Analysis of a cone-based distributed topology control algorithm for wireless multihop networks, in: Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), Newport, RI (2001) pp. 264–273.
R. Mathar and J. Mattfeldt, Analyzing routing strategy NFP in multihop packet radio network on a line, IEEE Transactions on Communications 43(2–4) (1995) 977–988.
J.P. Monks, V. Bhargavan and M.W. Hwu, A power controlled mutiple access protocol for wireless packet networks, in: Proceedings of IEEE INFOCOM (2001) pp. 219–228.
S. Narayanaswamy, V. Kawadia, R.S. Sreenivas and P.R. Kumar, Power control in ad hoc networks: Theory, architecture, algorithm and implementation of the COMPOW protocol, in: Proceedings of European Wireless 2002. Next Generation Wireless Networks: Technologies, Protocols, Services and Applications, Florence, Italy (2002) pp. 156–162.
J.M. Ortega and W.C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables (Academic Press, New York, 1970).
R. Ramanathan and R. Rosalie-Hain, Topology control of multihop wireless networks using transmit power adjustment, in: Proceedings of the IEEE INFOCOM (2000) pp. 404–413.
V. Rodoplu and T.H. Meng, Minimum energy mobile wireless networks, IEEE Journal on Selected Areas in Communications 17(8) (1999).
S. Singh and C.S. Raghavendra, Power efficient MAC protocol for multihop radio networks, in: Proceedings of the IEEE International Symposium on Personal, Indoor and Mobile Radio Communincations (1998) pp. 153–157.
H.L. Smith, Monotone Dynamical Systems (American Math. Society, Providence, R.I., 1995).
H. Takagi and L. Kleinrock, Optimal transmission ranges for randomly distributed packet radio terminals, IEEE Transactions on Communications 32 (1984) 246–257.
R. Wattenhofer, L. Li, P. Bahl and Y.-M. Wang, Distributed topology for power efficient operation in multihop wireless ad hoc networks, in: Proceedings of IEEE INFOCOM (2001).
F. Xue and P.R. Kumar, The number of neighbors needed for connectivity of wireless networks, Wireless Networks 10(2) (2004) 169–181.
F. Xue and P.R. Kumar, On the θ-coverage and connectivity of large random networks, Preprint (2005).