Topology control in wireless ad hoc and sensor networks

ACM Computing Surveys - Tập 37 Số 2 - Trang 164-194 - 2005
Paolo Santi1
1Istituto di Informatica e Telematica, Pisa, Italy

Tóm tắt

Topology Control (TC) is one of the most important techniques used in wireless ad hoc and sensor networks to reduce energy consumption (which is essential to extend the network operational time) and radio interference (with a positive effect on the network traffic carrying capacity). The goal of this technique is to control the topology of the graph representing the communication links between network nodes with the purpose of maintaining some global graph property (e.g., connectivity), while reducing energy consumption and/or interference that are strictly related to the nodes' transmitting range. In this article, we state several problems related to topology control in wireless ad hoc and sensor networks, and we survey state-of-the-art solutions which have been proposed to tackle them. We also outline several directions for further research which we hope will motivate researchers to undertake additional studies in this field.

Từ khóa


Tài liệu tham khảo

Aldous D., 1992, Asymptotics for euclidean minimal spanning trees on random points, Probab. Theo. Relat. Fields, 92, 247, 10.1007/BF01194923

Althaus E., Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC)'03

Bahramgiri M., Proceedings of the IEEE International Conference on Computer Communications and Networks. 392--397

Bao L., 2001, Proceedings of Discrete Algorithms and Methods for Mobile Computing and Communications (DIALM). 9--18

10.1109/90.811446

Bettstetter C., 2001, Proceedings of the ACM Workshop on Modeling, Analysis and Simulation of Wireless and Mobile Systems (MSWiM). 19--27

Bettstetter C., 2002, Proceedings of the 56th IEEE Vehicular Technology Conference (VTC). 1706--1710

Bettstetter C., 2002, Proceedings of the ACM MobiHoc 02

Bettstetter C., Proceedings of the IEEE International Conference on Mobile and Wireless Communication Network (MWCN).]]

10.1109/TMC.2003.1233531

Blough D., Proceedings of the IFIP Conference on Theoretical Computer Science. 71--82

Blough D., Proceedings of the ACM MobiHoc 03

Blough D., Proceedings of the ACM Workshop on Modeling, Analysis, and Simulation of Wireless and Mobile Systems (MSWiM). 30--37

Bollobás B. 1985. Random Graphs. Academic Press London UK.]] Bollobás B. 1985. Random Graphs. Academic Press London UK.]]

Booth L., Proceedings of the IEEE International Symposium on Information Theory (ISIT).]]

Borbash S., Proceedings of the IEEE International Joint Conference on Neural Networks. 355--360

Bruck J., Proceedings of the IEEE Symposium on Antennas and Propagation. 220--223

Burkhart M., Proceedings of ACM MobiHoc 04

Cagali M., Proceedings of the ACM Mobicom 02

Calinescu G., Proceedings of the IFIP Conference on Theoretical Computer Science. 119--130

Calinescu G., Proceedings of the Ad Hoc Networks and Wireless. 235--246

Camp T., 2002, A survey of mobility models for ad hoc network research, Wirel. Comm. Mobile Comput., 2, 483, 10.1002/wcm.72

10.1023/A:1019186624837

Cisco. 2004. Aironet data sheets. Available at http://www.cisco.com/en/US/products/hw//wireless.]] Cisco. 2004. Aironet data sheets. Available at http://www.cisco.com/en/US/products/hw//wireless.]]

Clementi A., Proceedings of the 8th European Symposium on Algorithms (ESA). 143--154

Clementi A., Proceedings of the 2nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (RANDOM/APPROX). 197--208

Clementi A., Proceedings of the 17th Symposium on Theoretical Aspects of Computer Science (STACS). 651--660

Dette H., 1989, The limit distribution of the largest nearest-neighbor link in the unit d-cube, J. Appl. Probab., 26, 67, 10.2307/3214317

10.1017/S0963548300004454

Dousse O., Proceedings of IEEE Infocom. 1724--1733

Dousse O., Proceedings of IEEE Infocom. 1079--1088

Estrin D., Proceedings of the ACM Mobicom. 263--270

Faragó A., 2002, Proceedings of ACM Discrete Algorithms and Methods for Mobile Computing and Communication (DIALM). 43--50

Gao J., Proceedings of the ACM MobiHoc. 45--55

10.1007/BF01200845

Goodman J. and O'Rourke J. 1997. Handbook of Discrete and Computational Geometry. CRC Press New York NY.]] Goodman J. and O'Rourke J. 1997. Handbook of Discrete and Computational Geometry. CRC Press New York NY.]]

Grossglauser M., Proceedings of IEEE Infocom. 1360--1369

Gupta P. and Kumar P. 1998. Critical power for asymptotic connectivity in wireless networks. Stochastic Analysis Control Optimization and Applications. Birkpauser Boston MA. 547--566.]] Gupta P. and Kumar P. 1998. Critical power for asymptotic connectivity in wireless networks. Stochastic Analysis Control Optimization and Applications. Birkpauser Boston MA. 547--566.]]

Gupta P., 2000, The capacity of wireless networks, IEEE Trans. Inf. Theo., 46, 388, 10.1109/18.825799

Heinzelman W., Proceedings of ACM Mobicom. 174--185

Holst L., 1980, On multiple covering of a circle with random arcs, J. Appl. Probab., 16, 284, 10.2307/3212948

Huang Z., Proceedings of the IEEE International Conference on Computer Communications and Networks. 16--21

IEEE. 1999. Wireless lan medium access control and physical layer specifications. In IEEE 802.11 Standard (IEEE Computer Society LAN MAN Standards Committee).]] IEEE. 1999. Wireless lan medium access control and physical layer specifications. In IEEE 802.11 Standard (IEEE Computer Society LAN MAN Standards Committee).]]

Janson S., 1993, The birth of the giant component, Rand. Struct. Algor., 4, 233, 10.1002/rsa.3240040303

Johnson D. and Maltz D. 1996. Dynamic source routing in ad hoc wireless networks. In Mobile Computing. Kluwer Academic Publishers. 153--181.]] Johnson D. and Maltz D. 1996. Dynamic source routing in ad hoc wireless networks. In Mobile Computing. Kluwer Academic Publishers. 153--181.]]

Khan J., 2000, Emerging challenges: Mobile networking for smart dust, J. Comm. Netw., 2, 186

Kim D., Proceedings of IEEE Globecom. 2798--2803

10.1016/S0304-3975(98)00223-0

Ko Y., Proceedings of ACM Mobicom. 66--75

Kolchin V. Sevast'yanov B. and Chistyakov V. 1978. Random Allocations. V.H. Winston and Sons Washington D.C.]] Kolchin V. Sevast'yanov B. and Chistyakov V. 1978. Random Allocations. V.H. Winston and Sons Washington D.C.]]

Li J., Proceedings of ACM Mobicom. 61--69

Li L., Proceedings of ACM Principles of Distributed Company (PODC). 264--273

Li N., Proceedings of ACM Mobicom. 275--286

Li N., Proceedings of the IEEE Infocom. 1702--1712

Li X., Proceedings of ACM Mobihoc. 283--286

Li X., Proceedings of the IEEE Hawaii International Conference on System Sciences (HICSS).]]

10.1109/TPDS.2004.77

Liang W., 2002, Proceedings of ACM Mobihoc. 112--122

Liu J., Proceedings of the IEEE International Conference on Computer Communications and Networks. 570--574

Loyd E., Proceedings of ACM Mobihoc. 123--134

Mainwaring A., Proceedings of ACM Wireless Sensor Networks and Applications (WSNA). 88--97

Marina M., Proceedings of ACM Mobihoc. 12--23

Meester R. and Roy R. 1996. Continuum Percolation. Cambridge University Press Cambridge U.K.]] Meester R. and Roy R. 1996. Continuum Percolation. Cambridge University Press Cambridge U.K.]]

10.1023/A:1025137811334

Moaveni-Nejad K. and Li X. 2005. Low-interference topology control for wireless ad hoc networks. Ad Hoc Sensor Netw.: Int. J. To appear.]] Moaveni-Nejad K. and Li X. 2005. Low-interference topology control for wireless ad hoc networks. Ad Hoc Sensor Netw.: Int. J. To appear.]]

10.1007/BF01193336

Narayanaswamy S., Proceedings of European Wireless. 156--162

Palmer E. 1985. Graphical Evolution. John Wiley and Sons New York NY.]] Palmer E. 1985. Graphical Evolution. John Wiley and Sons New York NY.]]

Panchapakesan P., Proceedings of IEEE Signal Processing Communication (SPCOM).]]

Papadimitriou I., 2004, Energy-aware broadcast trees in wireless networks, Mobile Netw. Appls., 9, 567, 10.1023/B:MONE.0000042496.99241.53

Pearlman M., Proceedings of Wireless Communications and Networking Conference (WCNC). 532--537

Penrose M., 1997, The longest edge of the random minimal spanning tree, Annals Appl. Probab., 7, 340, 10.1214/aoap/1034625335

Penrose M., 1998, Extremes for the minimal spanning tree on normally distributed points, Advances Appl. Probab., 30, 628, 10.1239/aap/1035228120

10.1002/(SICI)1098-2418(199909)15:2%3C145::AID-RSA2%3E3.0.CO;2-G

Penrose M., 1999, A strong law for the largest nearest-neighbour link between random points, J. London Math. Soci., 60, 951, 10.1112/S0024610799008157

Penrose M., 1999, A strong law for the longest edge of the minimal spanning tree, The Annals Probab., 27, 246, 10.1214/aop/1022677261

Philips T., 1989, Connectivity properties of a packet radio network model, IEEE Trans. Inform. Theo., 35, 1044, 10.1109/18.42219

Piret P., 1991, On the connectivity of radio networks, IEEE Trans. Inform. Theo., 37, 1490, 10.1109/18.133276

10.1145/332833.332838

10.1023/A:1012371402221

10.1145/564585.564602

Ramanathan R., Proceedings of IEEE Infocom 00

Ramasubramanian V., Proceedings of IEEE Infocom. 1258--1267

Rappaport T., 2002, Wireless Communications: Principles and Practice, 2

Rodoplu V., 1999, Minimum energy mobile wireless networks, IEEE J. Select. Areas Comm., 17, 1333, 10.1109/49.779917

Royer E., Proceedings of the IEEE International Conference on Communications. 857--861

Sadler C., Proceedings of ACM SenSys. 227--238

Sanchez M., Proceedings of Multiaccess, Mobility and Teletraffic for Wireless Communications Conference.]]

10.1109/TMC.2005.45

Santi P., Proceedings of IEEE Dependable Systems and Networks (DSN). 89--98

10.1109/TMC.2003.1195149

Santi P., Proceedings of ACM Mobihoc. 212--220

Schwiebert L., Proceedings of ACM Mobicom. 151--165

Seada K., Proceedings of ACM SenSys. 108--121

Sen A., Proceedings of IEEE Infocom. 1116--1124

Song W., Proceedings of ACM MobiHoc. 98--108

Srivastava M., Proceedings of ACM Mobicom. 132--138

Steele J., 1988, Growth rates of euclidean minimal spanning trees with power weighted edges, Annals Probab., 16, 1767, 10.1214/aop/1176991596

Steere D., Proceedings of ACM Mobicom. 292-- 299

Szewczyk R., Proceedings of ACM SenSys. 214--226

10.1023/A:1020381720601

Wan P., Proceedings of ACM MobiHoc. 1--8.]] 10

Wang W. Li X. MoaveniNejad K. Wang Y. and Song W. 2003. The spanning ratio of β-skeletons.]] Wang W. Li X. MoaveniNejad K. Wang Y. and Song W. 2003. The spanning ratio of β-skeletons.]]

Wang Y., 2002, Distributed spanners with bounded degree for wireless ad hoc networks. Int, J. Found. Comput. Sci. To appear.]]

Wattenhofer R., Proceedings of IEEE Infocom. 1388--1397

Wattenhofer R., the 4th International Workshop on Algorithms for Wireless, Mobile, Ad Hoc and Sensor Networks (WMAN).]]

Wieselthier J., Proceedings of IEEE Infocom. 585--594

10.1023/B:WINE.0000013081.09837.c0

Yi C., Proceedings of IEEE Wireless Communications and Networking Conference (WCNC) To appear.]]

Yi C., Proceedings of IEEE Wireless Communications and Networking Conference (WCNC). 1585--1590

Yukich J., 2000, Asymptotics for weighted minimal spanning trees on random points, Stochastic Proc. Appl., 85, 123, 10.1016/S0304-4149(99)00068-X