Received 10 September 2015; accepted 19 January 2016; published 22 January 2016
Amobilead hoc network (MANET) is formed by a group of wireless autonomous mobile nodes to create a typical environment for dynamic communication with no fixed infrastructure or administration. They operate in a decentralized and self organizing manner   . This type of network has been existing since 1970s   , but only last couple of years has witnessed a tremendous research in this area  -  . There are several issues related to MANETs that include route construction with minimum overhead  -  , less bandwidth consumption, energy issue, security attacks  -  , node misbehavior  -  , etc. Some of the important routing protocols, broadcast protocols, and clustering protocols designed especially for ad hoc networks have been discussed in  -  . Some of them are designed for energy-efficient operation in an existing network topology, some deal with the effects of mobility, and some consider both the aspects. There are various studies in literature, but none discusses the latest developments related tothe ad hoc network connectivity. To the best of authors’ knowledge, this is the first such study that reviews the importance of node connectivity unlike other properties like stable route construction, bandwidth, energy consumption, etc. in multihop wireless networks.
The advantage of ad hoc networks is that the mobile devices communicate with each other in a peer-to-peer fashion, establish a self organizing network without the need of any access point or any pre-existing infrastructure. In short, they can be formed in a spontaneous way, that’s why they are known as ad hoc networks. In these networks, each node plays two vital roles: as mobile node and as router to transfer the packets of other nodes. To achieve a fully connected ad hoc network, there must be a multihop path from a node to every other node depending on two topology attributes: radio transmission range and node density. Their combination plays a vital role in node connectivity.
In a cellular network, also known as infrastructure network, the mobile devices remain connected even if there is a wireless link to at least one of the base stations within its communication range. In ad hoc networks, there are no fixed routers; all nodes are capable of movement that can be dynamically connected in an arbitrary manner. Each node acts as router to maintain the connectivity of the entire network. In case the communication gets broken, the connectivity between other nodes also gets destroyed. If the substantiality or spatial density of nodes is too low, the multihop system for communication will not perform well. In this paper, we study and analyze various techniques related to network connectivity along with their impact on the network topology. The organization of the remaining paper is as follows. Section II discusses the importance of connectivity in ad hoc networks. Section III discusses the research works done in the area. Section IV points out the major issues and challenges in ad hoc network connectivity. Finally, the paper is concluded in section V.
2. Why Node Connectivity Is Important?
Connectivity in ad hoc networks varies because of the continuous movement of the nodes due to their dynamic nature. It is possible that the movement of one or more nodes from one point to another causes the network partitioning. Maintaining connectivity is a challenge due to unstructured nature of the network topology and the frequent occurring of links and nodes failures due to interference, mobility, radio channel effects, and battery limitations  . This makes connectivity as one of the main problems in an ad hoc network. Many researchers have discussed methods to improve the network connectivity, which will be discussed in next section. The factors leading to network failure that partitions it into two or more components and can annihilate the end-to-end connectivity as well may be divided into the following four categories:
Node or Device Failure
Critical Points or Weak Points
Link or Edge Failure
Power or Battery Failure
a) Node Failure: The node failure occurs when an intermediate node or device acting as router is not available due to hardware/software failure or the node moves out of the communication range or the network. The situation has been described in Figure 1. Here node A and Dare communicating through node C. If node C fails due to battery failure or it moves out of the communication range, then an alternate route must be discovered and communication should be restored by rerouting the traffic through some other node B. The amount of time that two mobile nodes will stay connected is calculated by expression:
Figure 1. Illustration of Node Failure or Power Failure of Node C.
In the above equations, are the speeds and , are the moving directions of two nodes I and j respectively.
After calculating the link expiration time (LET) in all
Links within the network, the highest amount of LET is determined:
The probability of the proper operation of link between node I and node j is obtained by:
where is the biggest time period which the two nodes are connected in the network.
b) Power Failure: Power failure occurs when the battery of the node is too low, making it unable to serve as router. The situation has been explained in Figure 1.
c) Link Failure: Link failure can occur due to various factors: link obstacle between communication nodes, fading, node mobility and excessive interference. Figure 2 illustrates the link fault when node Y moves to different position, resulting in communication link between X and Y, degrading because of an obstacle. Obviously these failures break the local connectivity between nodes and can disrupt the end-to-end connectivity as well. The path stability can be expressed by the following mathematical expression:
, where is the expiration time of the path joining S & D, is the expiration time of the link connecting node and the node, k is an integer where
d) Critical Points: The weak or critical points of a topology are those links and nodes whose failure results in partioning the network into two or more components. For example, the critical node or articulation node is defined as a node that partitions the network due to its failure. The node C in Figure 3 is a critical node because the network is partitioned if this node fails. Similarly the link CD in Figure 4 is a critical link since failure of the link CD partitions the network into two components. Such links are also known as bridge links.
Figure 2. Illustration of Link between X and Y breaks due to some obstacle.
Figure 3. Illustration of critical node C.
Figure 4. Illustration of critical link CD.
3. Literature Overview
The problem of node connectivity was very first time discussed by Cheng and Robertazziin 1989  . They investigated the influence of node density and transmission range of a node‘s broadcast in a multihop radio network modeled by spatial Poisson process. They suggested that for optimizing the transmission range, its value should be lower bounded to maintain desired network connectivity. However, they could not implement it in real scenario. The paper  , an extension of  , discusses the disconnectedness of Poisson distributed nodes. It provides some insights on critical coverage range vs. critical transmission range of the nodes placed in a square area according to Poisson fixed density. This problem is further discussed in  for one dimensional line segment that determines the critical transmitting range for Poisson distributed nodes in square area. However, these works   are difficult to apply in real scenarios because in a Poisson process the actual number of deployed nodes is a random variable itself whose only average value can be found. The paper  discusses the critical power of nodes in a network for transmission to ensure network connectivity by using the percolation theory  . The probabilistic lower and upper bounds for isolated and connected nodes fail to explain about nodes not placed independently in a disc. The paper  investigates the connectivity of hybrid ad hoc networks consisting the Poisson distributed nodes using the percolation theory. It reports that for populated regions one dim sparse network is well suited and the pure ad hoc network is useful relatively low density areas. For density critical areas, the cellular network can provide the acceptable connectivity. The paper  estimates the nearest neighbors when network becomes disconnected. In this work, the same number of nearest neighbors is maintained for each node. If each node is connected to less than 0.074 logn nearest neighbors the network is asymptotically disconnected. If each node is connected to more than 5.1774 logn nearest neighbors, then it is asymptotically connected. The paper  discusses the connectivity augmentation problem and determines a set of edges of minimum weight to be inserted in order to make the resulting graph λ-vertex edge connected. It is reported that the problem is NP hard for λ > 1. In  , the same work has been discussed by using the concept of minimum geometric disk cover (MGDC) problem, commonly used in wireless networking applications or facility location problems. The MGDC problem is “for a given set of points P in Euclidean plane and a rational number r > 0, it intends to find a set of centers C with minimum cardinality such that every point P is covered by a r radius disk centered at one of the points in C.” This problem is however NP−hard problem. The paper  uses the random graph theory and theory of Kolmogorov complexity to establish the network connectivity via building local cluster head connections between nearby cluster heads without considering global network topology. In  , the radio transmission range problem is analyzed and the probabilistic bounds for isolated nodes and connected nodes with uniform nodes on 1 - 2- and 3-dimension are calculated. It reports that the transmitting range of nodes can be reduced substantially from the deterministic requirements if there is high probability of connectedness. The paper  extends the work  and discusses the asymptotic minimum node degree of a graph on uniform points in d dimension .Some more studies on radio transmission range problem are discussed in  -  . The works  -  however do not consider inhomogeneous nodes. The issue of k-connectivity with respect to different transmission ranges has been discussed in   . The same has been analyzed using the stochastic connectivity properties of the wireless multihop networks in  . The paper  discusses the connectivity for inhomogeneous node distributions with random waypoint (RWP) nodes. The paper  extends the Bettsetter’s work  by incorporating the deployment border effects on the range to provide k-connectivity. In  , the critical transmission power based on Bettsetter  is discussed to maintain k-connectivity, ensuring k-neighbors of a node is a necessary condition but not the sufficient condition for k-connectivity. It is because the network graph may have critical points which can cause the network failure and destroys the end-to-end network connectivity. In   , the critical transmitting range for connectivity in both stationary and mobile ad hoc networks has been analyzed. The paper  also discusses the probability for establishing a multihop path between two Poisson distributed nodes on an infinite line with a given distance. The paper  discusses about the node that keeps a multihop path to a fixed base station with the nodes moving in a straight line away from the base station. The k-connectivity concept has been further extended in  that studies the critical number of neighbors needed for k-connectivity. There are critical or weak points that play a major role in destroying the network connectivity. The works      have not discussed critical points. The paper  characterizes the critical transmitting range by using the asymptotic distribution of the longest minimum spanning tree   . In  , the problem of minimizing the maximum of node transmitting ranges while achieving connectedness is discussed. The basic assumption here is that the relative distance of all nodes is considered as input to the centralized topology control algorithm. In  , a distributed topology control protocol is discussed to minimize the energy required to communicate with a given master node. In this work, every node is equipped with a GPS receiver to provide position information. Initially every node iteratively broadcasts its position to different search regions. When the node is able to calculate a set of nodes, called as its enclosure, based on the position information obtained from neighbors, this process stops. Its major drawback is that the number of iterations to determine the enclosure depends on the definition of initial search region, which affects the energy consumption of the protocol. The same problem has been analyzed in  using directional information obtained by using multi-directional antenna. But such setup is not possible in sensor networks because the nodes are very simple and have no centralized communication facility.
In order to prevent failures from partitioning the network and to maintain end-to-end connectivity, researchers recommend the network topology to be K-connected. The K-connectivity refers that the network should have K-disjoint routes between each node pair, which may be edge disjoint or noded is joint. Till now, the main focus has been on to determine the combination of node density and transmission range in order to provide k-node cconnectivity in a specific deployment scenario in homogeneous nodes or non-homogenous nodes in MANETs. However, very few papers  -  have defined the critical points or weak points in MANETs which results in the network partition in two or more components.
The work of different authors have been analyzed with their viewpoints on the ad hoc network connectivity along with techniques used and defects in more pristine manner in Table 1. Besides such rigorous works, there are still some major issues and challenges left that need be looked uponin order to have better node connectivity in MANETs.
4. Issues and Challenges
a) Mobility Prediction: Mobility prediction of a node is the estimation of its future locations. The definition of location depends on the type of wireless networks. In infrastructure networks location refers to the access points to which mobile terminal is connected. In infrastructureless networks the location refers to geographical coordinates. Its main advantage is to predict the link expiration time to improve the node connectivity and routing performance. Many location prediction methods are discussed in literature   . However, no studies discuss about the prediction of future locations considering realistic scenarios. This is one of the biggest challenges in MANETs.
b) Connectivity Efficiency and Cost Objective: Since in order to deploy static nodes in place of critical nodes in which lack of nodes are felt, deployment cost of static nodes must be considered. While placing such nodes attention must be paid on to maximize the connectivity and to have minimum cost. But to achieve both connectivity efficiency and cost objective while deploying the critical points is a NP-complete problem. Since few authors have attempt this part  but no work has done to find the critical links and critical nodes considering the both factor cost objective and connectivity efficiency. Since it is NP-complete problem, more optimized technique need to be followed in order to achieve this goal
c) Energy Consumption issues: One of the key challenges is to save the limited energy and use it to prolong the network lifetime considering the network connectivity constraints. Since the energy is the most valuable resources in MANETs, its status should continuously be monitored after network deployment. The paper  -   discusses this issue. Researchers have considered the random waypoint mobility model, which is unrealistic model. There is a need to look this aspect in real scenarios.
Table 1. Analysis of the existing work related to network connectivity in ad hoc networks.
In this paper, we have reviewed the existing literature with respect to network connectivity. The network connectivity is an important property of ad hoc network because the mobile nodes change the network topology very frequently. If the network becomes disconnected, the data may not be sent to the desired destination. Most of the existing works have considered unrealistic scenarios and very less works discuss the major factors contributing to network disconnectivity in MANETs. We have highlighted important parameters that affect the network connectivity, which include battery/power failure, link failure, critical points, and node failure. The main issues in network connectivity are mobility prediction, energy consumption and connectivity efficiency along with connectivity cost and these issues need to be explored further to understand network connectivity.
 Jublin, J. and Tornow, J. (1987) The DARPA Packet Radio Network Protocols. Proceedings of the IEEE, 75, 21-32.
 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.
 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.
 Hong, X., Xu, K. and Gerla, M. (2002) Scalable Routing Protocols for Mobile Ad Hoc Networks. IEEE Network, 16, 11-21.
 Mauve, M., Widmer, J. and Hartenstein, H. (2001) A Survey On Position—Based Routing in Mobile Ad Hoc Networks. IEEE Network, 1, 30-39.
 Yih-Chun, H. and Perrig, A. (2004) A Survey of Secure Wireless Ad Hoc Routing. IEEE Security and Privacy Magazine, 2, 28-39.
 Karlof, C. and Wagner, D. (2003) Secure Routing in Wireless Sensor Networks: Attacks and Countermeasures. Ad Hoc Networks, 1, 293-315.
 Wood, A.D. and Stankovic, J.A. (2002) Denial of Service in Sensor Networks. IEEE Computer, 35, 54-62.
 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.
 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.
 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.
 Murthy, S. and Garcia-Luna-Aceves, J.J. (1996) An Efficient Routing Protocol for Wireless Network. Mobile Networks and Applications, 1, 183-197.
 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.
 Ramanathan, S. and Steestrup, M. (1996) A Survey of Routing Techniques for Mobile Communication Networks. Mobile Networks and Applications, 1, 89-104.
 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.
 Cheng, Y.-C. and Robertazzi, T.G. (1989) Critical Connectivity Phenomena in Multihop Radio Models. IEEE Transactions on Communications, 37, 770-777.
 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.
 Piret, P. (1991) On the Connectivity of Radio Networks. IEEE Transactions on Information Theory, 37, 1490-1492.
 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.
 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.
 Xue, F. and Kumar, P.R. (2004) The Number of Neighbors Needed for Connectivity of Wireless Networks. Wireless Networks, 10, 161-181.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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).
 Penrose, M.D. (1999) A Strong Law for the Longest Edge of the Minimal Spanning Tree. The Annals of Probability, 27, 246-260.
 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.
 Rodolpu, V. and Meng, T.H. (1999) Minimum Energy Mobile Wireless Networks. IEEE Journal on Selected Areas in Communications, 17, 1333-1344.
 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.
 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.
 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.
 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.
 Nemeth, G. and Vattay, G. (2003) Giant Clusters in Random Ad Hoc Networks. Physical Review E, 67, Article ID: 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.