One of the fundamental properties of an ad hoc network is its connectivity. Maintaining connectivity in wireless networks is extremely difficult due to dynamic changing topology of MANETs. There are several techniques to understand the connectivity level for a given network topology. In this paper, we examine the existing methods and discuss the issues and challenges that are still insurmountable in order to enhance the connectivity properties of wireless multi hop networks.
KeywordsAd Hoc NetworksConnectivityTopology ControlCritical Transmitting RangeNode DensityEnergy Consumpution RoutingCritical Pointsk-Connectivity
Basu, S.S. and Chaudhari, A. (2003) Self Adaptive Topology Management for Mobile Ad Hoc Network. Journal of the Institution of Engineers (India), 84, 7-13.
Johnson, D.B. and Maltz, D.A. Dynamic Source Routing in Ad Hoc Wireless Networks. Computer Science Department, Carneige Mellon University, Pittsburg, 213-3891.
Jublin, J. and Tornow, J. (1987) The DARPA Packet Radio Network Protocols. Proceedings of the IEEE, 75, 21-32. http://dx.doi.org/10.1109/PROC.1987.13702
Leiner, B.M., Nielson, D.L. and Tobagi, F.A. (1987) Issue in Packet Radio Network Design. Proceedings of the IEEE, Special Issue on Packet Radio Networks, 75.
Haas, Z.J., Gerla, M., Johnson, D.B., Perkins, C.E., Pursley, M.B., Steenstrup, M. and Toh, C.-K. (1999) IEEE Journal on Selected Areas in Communications, Special issue on Wireless Ad Hoc Networks, 17.
Kermani, P. and Vaidya, N.H. (2001) IEEE Personal Communication, Special Issue on Advances in Mobile Ad Hoc Networking.
Perkins, C.E. (2001) Ad Hoc Networking. Addison-Wesley, Boston.
Royer, E.M. and Toh, C.-K. (1999) A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks. IEEE Personal Communications Magazine, 6, 46-55. http://dx.doi.org/10.1109/98.760423
Hong, X., Xu, K. and Gerla, M. (2002) Scalable Routing Protocols for Mobile Ad Hoc Networks. IEEE Network, 16, 11-21. http://dx.doi.org/10.1109/MNET.2002.1020231
Abolhasan, M., Wysocki, T. and Dutkiewicz, E. (2004) A Review of Routing Protocols for Mobile Ad Hoc Networks. Elsevier ADHOC Networks Journal, 2, 1-22.
Mauve, M., Widmer, J. and Hartenstein, H. (2001) A Survey On Position—Based Routing in Mobile Ad Hoc Networks. IEEE Network, 1, 30-39. http://dx.doi.org/10.1109/65.967595
Costa, L.H.M.K., Amorim, M.D. and Fdida, S. (2004) Reducing Latency and Overhead of Route Repair with Controlled Flooding. ACM/Kluwer Wireless Networks, 10, 347-358.
Yih-Chun, H. and Perrig, A. (2004) A Survey of Secure Wireless Ad Hoc Routing. IEEE Security and Privacy Magazine, 2, 28-39. http://dx.doi.org/10.1109/MSP.2004.1
Karlof, C. and Wagner, D. (2003) Secure Routing in Wireless Sensor Networks: Attacks and Countermeasures. Ad Hoc Networks, 1, 293-315. http://dx.doi.org/10.1016/S1570-8705(03)00008-8
Wood, A.D. and Stankovic, J.A. (2002) Denial of Service in Sensor Networks. IEEE Computer, 35, 54-62. http://dx.doi.org/10.1109/MC.2002.1039518
Aad, I., Hubaux, J.-P. and Knightly, E.W. (2004) Denial of Service Resilience in Ad Hoc Networks. Proceedings of ACM MobiCom’04, 202-215. http://dx.doi.org/10.1145/1023720.1023741
Hollick, M., Schmitt, J., Sepil, C. and Steinmetz, R. (2004) On the Effect of Node Misbehavior in Ad Hoc Networks. Proceedings of IEEE ICC’04, 6, 3759-3763.
Srinivasan, V., Nuggehalli, P., Chiasserini, C.F. and Rao, R.R. (2003) Co-Operation in Wireless Ad Hoc Networks. Proceedings of IEEE INFOCOM’03, 30 March-3 April 2003, 808-817.
Basagni S., Bruschi, D. and Chlamtac, I. (1999) A Mobility Transparent Deterministic Broadcast Mechanism for Ad Hoc Networks. IEEE Transactions on Networking, 7, 7999-807. http://dx.doi.org/10.1109/90.811446
Gerla, M. and Tzu-Chen Tsai, J. (1995) Multicluster, Mobile, Multimedia Radio Network. Wireless Networks, 1, 255-265.
Intanagonwiwat, C., Govindan, R. and Estrin, D. (2000) Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks. Proceedings of the 6th Annual International Conference on Mobile Computing and Networking, Boston, 6-11 August 2000, 56-67. http://dx.doi.org/10.1145/345910.345920
Ko, Y.B. and Vaidya, N.H. (1998) Location-Aided Routing (LAR) in Mobile Ad Hoc Networks. Proceedings of the 4th Annual ACM International Conference on Mobile Computing and Networking, Dallas, 25-30 October 1998, 66-75. http://dx.doi.org/10.1145/288235.288252
Murthy, S. and Garcia-Luna-Aceves, J.J. (1996) An Efficient Routing Protocol for Wireless Network. Mobile Networks and Applications, 1, 183-197. http://dx.doi.org/10.1007/BF01193336
Park, V.D. and Corson, M.S. (1997) A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks. Proceedings of the Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, Kobe, 7-12 April 1997, 1405-1413.
Perkins, C.E. and Bhagwat, P. (1994) Highly Dynamic Destination Sequenced Distance Vector Routing (DSVD) for Mobile Computers. Proceedings of the ACM SIGCOMM’94 Conference on Communications Architectures, Protocols and Applications, London, 31 August-2 September 1994, 234-244. http://dx.doi.org/10.1145/190314.190336
Ramanathan, S. and Steestrup, M. (1996) A Survey of Routing Techniques for Mobile Communication Networks. Mobile Networks and Applications, 1, 89-104. http://dx.doi.org/10.1007/BF01193330
Chlamtac, I. and Fargo, A. (1999) A New Approach to the Design and Analysis of Peer to Peer Mobile Networks. ACM/Kluwer Wireless Networks, 5, 149-156. http://dx.doi.org/10.1023/A:1019186624837
Cheng, Y.-C. and Robertazzi, T.G. (1989) Critical Connectivity Phenomena in Multihop Radio Models. IEEE Transactions on Communications, 37, 770-777. http://dx.doi.org/10.1109/26.31170
Philips, T.K., Panwar, S.S. and Tantawi, A.N. (1989) Connectivity Properties of a Packet Radio Network Model. IEEE Transactions on Information Theory, 35, 1044-1047. http://dx.doi.org/10.1109/18.42219
Piret, P. (1991) On the Connectivity of Radio Networks. IEEE Transactions on Information Theory, 37, 1490-1492. http://dx.doi.org/10.1109/18.133276
Gupta, P. and Kumar, P.R. (1998) Critical Power for Asymptotic Connectivity in Wireless Networks. In: McEneany, W.M., Yin, G. and Zhang, Q., Eds., Stochastic Analysis, Control, Optimization and Applications: A Volume in Honor of W. H. Fleming, Birkhauser, Boston, 547-566.
Meesterand, R. and Roy, R. (1996) Continuum Percolation. Cambridge University Press, Cambridge, MA. http://dx.doi.org/10.1017/CBO9780511895357
Dousse, O., Thiran, P. and Hasler, M. (2002) Connectivity in Ad Hoc and Hybrid Networks. Proceedings of the Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies, New York, 23-27 June 2002, 1079-1088. http://dx.doi.org/10.1109/infcom.2002.1019356
Xue, F. and Kumar, P.R. (2004) The Number of Neighbors Needed for Connectivity of Wireless Networks. Wireless Networks, 10, 161-181. http://dx.doi.org/10.1023/B:WINE.0000013081.09837.c0
Khuller, S. (1996) Approximation Algorithms for Finding Highly Connected Subgraphs. In: Hochbaum, D.S., Ed., Approximation Algorithms for NP Hard Problems, PWS Publishing Co., Boston.
Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A. and Protasi, M. (1999) Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer-Verlag, Berlin. http://dx.doi.org/10.1007/978-3-642-58412-1
Santi, P., Blough, D.M. and Vainstein, F. (2001) A Probabilistic Analysis for the Radio Range Assignment Problem in Ad Hoc Networks. Proceedings of the Symposium on Mobile Ad Hoc Networking and Computing, Long Beach, 4-5 October 2001, 212-220.
Appel, M.J.B. and Russo, R.P. (1997) The Minimum Vertex Degree of a Graph on Uniform Points in [0,1]d. Advances in Applied Probability, 29, 582-594. http://dx.doi.org/10.2307/1428077
Krishnamachari, B., Wicker, S.B. and Bejar, R. (2001) Phase Transition Phenomenon in Wireless Ad Hoc Networks. Proceedings of the IEEE Global Telecommunications Conference, San Antonio, 25-29 November 2001, 2921-2925.
Bettstetter, C. (2002) On the Minimum Node Degree and Connectivity of Wireless Multihop Network. Proceedings of the 3rd ACM International Symposium on Mobile Ad Hoc Networking & Computing, Lausanne, 9-11 June 2002, 80-91. http://dx.doi.org/10.1145/513800.513811
Bettsetter, C. (2002) On the Connectivity of Wireless Multihop Networks with Homogeneous and Inhomogeneous Range Assignment. Proceedings of the IEEE 56th Vehicular Technology Conference, Vancouver, 24-28 September 2002, 1706-1710.
Bettstetter, C. and Zangl, J. (2002) How to Achieve a Connected Ad Hoc Network with Homogeneous Range Assignment: An Analytical Study with Consideration of Border Effects. Proceedings of the IEEE Conference on Mobile and Wireless Communication Networks (MWCN), Stockholm, 9-11 September 2002, 125-129. http://dx.doi.org/10.1109/MWCN.2002.1045708
Bettstetter, C. (2004) On the Connectivity of Ad Hoc Networks. The Computer Journal, 47, 432-447.
Bettstetter, C. (2003) Topology Properties of Ad Hoc Networks with Random Waypoint Mobility. Proceedings of the ACM International Symposium on Mobile Ad Hoc Networking and Computing, Annapolis, 1-3 June 2003.
Ling, Q. and Tian, Z. (2007) Minimum Node Degree and K-Connectivity of a Wireless Multihop Network in Bounded Area. Proceedings of the IEEE Global Telecommunications Conference, Washington DC, 26-30 November 2007, 1296-1301. http://dx.doi.org/10.1109/glocom.2007.249
Zang, H.H. and Hou, J.C. (2005) On the Critical Total Power for Asymptotic K-Connectivity in Wireless Networks. Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies, Miami, 13-17 March 2005, 466-476.
Santi, P. and Blough, D.M. (2003) The Critical Transmitting Range for Connectivity in Sparse Wireless Ad Hoc Networks. IEEE Transactions on Mobile Computing, 2, 25-39. http://dx.doi.org/10.1109/TMC.2003.1195149
Desai, M. and Manjunath, D. (2002) On the Connectivity in Finite Ad Hoc Networks. IEEE Communications Letters, 6, 437-439.
Nakano, K., Shirai, Y., Sengoku, M. and Shinoda, S. (2003) On Connectivity and Mobility in Mobile Multi Hop Wireless Networks. Proceedings of the 57th IEEE Semiannual Vehicular Technology Conference, Jeju, 22-25 April 2003, 89-98. http://dx.doi.org/10.1109/vetecs.2003.1208793
Wan, P.J. and Yi, C.W. (2004) Asymptotic Critical Transmission Radius and Critical Neighbor Number for K-Connectivity in Wireless Ad Hoc Networks. 5th ACM Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc).
Panchapakesan, P. and Manjunath, D. (2001) On the Transmission Range in Dense Ad Hoc Radio Networks. Proceedings of IEEE SPCOM’01.
Penrose, M.D. (1999) A Strong Law for the Longest Edge of the Minimal Spanning Tree. The Annals of Probability, 27, 246-260. http://dx.doi.org/10.1214/aop/1022677261
Penrose, M.D. (1999) The Longest Edge of the Random Minimal Spanning Tree. The Annals of Probability, 15, 340-361.
Ramanathan, R. and Rosales-Hain, R. (2000) Topology Control of Multihop Wireless Networks Using Transmit Power Adjustment. Proceedings of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies, Tel Aviv, 26-30 March 2000, 404-413. http://dx.doi.org/10.1109/infcom.2000.832213
Rodolpu, V. and Meng, T.H. (1999) Minimum Energy Mobile Wireless Networks. IEEE Journal on Selected Areas in Communications, 17, 1333-1344. http://dx.doi.org/10.1109/49.779917
Li, L., Halpern, J.H., Bahl, P., Wang, Y. and Wattenhofer, R. (2001) Analysis of a Cone-Based Distributed Topology Control Algorithm for Wireless Multi Hop Networks. Proceedings of the ACM Symposium on Principles of Distributed Computing, Newport, 26-28 August 2001. http://dx.doi.org/10.1145/383962.384043
Goyal, D.D. and Caffery, J.J. (2002) Partioning Avoidance in Mobile Ad Hoc Networks Using Network Survivability Concepts. Proceedings of the Seventh International Symposium on Computers and Communications, Sicily, 1-4 July 2002.
Milic, B. and Malek, M. (2007) Adaptation of the Breadth First Search Algorithm for Cut Edge Detection in Wireless Multihop Networks. Proceedings of the 10th ACM Symposium on Modeling, Analysis, and Simulation of Wireless and Mobile Systems, Chania, 22-26 October 2007, 377-386.
Jorgic, M., Goel, N., Kalaichevan, K., Nayak, A. and Stojmenovic, I. (2007) Localized Detection of K-Connectivity in Wireless Ad Hoc, Actuator and Sensor Networks. Proceedings of the 16th IEEE International Conference on Computer Communications and Networks (ICCCN), Honolulu, 13-16 August 2007, 33-38. http://dx.doi.org/10.1109/icccn.2007.4317793
Kumar, V. and Venkataram, P. (2002) A Prediction Based Location Management Using Multi-Layer Neural Netwoks. Journal of the Indian Institute of Science, 82, 7-21.
Kanniche, H. and Kamoun, F. (2010) Mobility Prediction in Wireless Ad Hoc Networks Using Neural Networks. Journal of Telecommunications, 2, 95-101.
Romoozi, M. and Babaezi, H. (2011) Improvement of Connectivity in Mobile Ad Hoc Networks by Adding Static Nodes Based on Realistic Mobility Model. International Journal of Computer Science Issues, 8, 176-183.
Kumar, N., Kumar, M. and Patel, R.B. (2010) Coverage and Connectivity Aware Neural Network Based Energy Efficient Routing in Wireless Sensor Networks. Journal on Application of Graph Theory in Wireless Ad Hoc Networks and Sensor Networks, 2, 45-60.
Janson, S., Luczak, T. and Rucinski, A. (2000) Random Graphs. John Wiley & Sons, New York. http://dx.doi.org/10.1002/9781118032718
Bollobas, B. (1998) Modern Graph Theory. Springer, New York.
Feller, W. (1950) An Introduction to Probability Theory and Its Applications. John Wiley & Sons, New York.
Diestel, R. (2000) Graph Theory. 2nd Edition, Springer, New York.
Gore, D.A. (2006) Comments on the Connectivity in Finite Ad Hoc Networks. IEEE Communication Letters, 10, 88-90.
Diaz, J., Penrose, M.D., Petit, J. and Serna, M. (2000) Convergence Theorems for Some Layout Measures on Random Lattice and Random Geometric Graphs. Combinatorics, Probability and Computing, 9, 489-511. http://dx.doi.org/10.1017/S0963548300004454
Nemeth, G. and Vattay, G. (2003) Giant Clusters in Random Ad Hoc Networks. Physical Review E, 67, Article ID: 036110. http://dx.doi.org/10.1103/PhysRevE.67.036110
Hekmat, R. and Mieghem, P.V. (2006) Connectivity in Wireless Ad-Hoc Networks with a Log-Normal Radio Model. Mobile Networks and Applications, 11, 351-360. http://dx.doi.org/10.1007/s11036-006-5188-7