Connectivity of Communication Networks

Connectivity of large wireless networks has been a primary concern for which asymptotic analysis is a useful tool. Three related but logically distinct network models are often considered in asymptotic analyses, viz., the dense network model, the extended network model, and the infinite network model, which considers respectively a network deployed in a fixed finite area with a sufficiently large node density, a network deployed in a sufficiently large area with a fixed node density, and a network deployed in an infinite plane with a sufficiently large node density. The infinite network model originated from continuum percolation theory and asymptotic results obtained from the infinite network model have often been applied to the dense and extended networks indiscriminately. In this chapter, through two case studies related to network connectivity on the expected number of isolated nodes and on the vanishing of components of finite order k > 1 respectively, we demonstrate some subtle but important differences between the infinite network model and the dense and extended network models. Therefore, extra scrutiny has to be used in order for the results obtained from the infinite network model to be applicable to the dense and extended network models. Asymptotic results are also established on the expected number of isolated nodes, the vanishingly small impact of the boundary effect on the number of isolated nodes and the vanishing of components of finite order k > 1 in the dense and extended network models using a general random connection model.

This chapter studies the sufficient and necessary condition for a large wireless network to be asymptotically almost surely connected. Consider a dense network model, we show that as the node density approaches infinity, (a) the distribution of the number of isolated nodes converges to a Poisson distribution; (b) asymptotically almost surely (a.a.s.) there is no component of fixed and finite order k > 1; (c) a.a.s. the number of components with an unbounded order is one. Therefore, as the node density approaches infinity, the network a.a.s. contains a unique unbounded component and isolated nodes only; a sufficient and necessary condition for the network to be a.a.s. connected is that there is no isolated node in the network. These results, established assuming a general random connection model, readily incorporate existing results established assuming the unit disk connection model and the fewer results assuming the log-normal connection model as its special cases.

In this chapter, we study the giant component, the largest component containing a nonvanishing fraction of nodes, in large wireless networks in both one-dimensional and two-dimensional space. Specifically, consider a network with a total of n nodes randomly, independently, and uniformly distributed in a unit interval or unit square. For one-dimensional networks, we derive a closed-form analytical formula for calculating the probability of having a giant component of order above pn with any fixed 0. 5 < p ≤ 1. The asymptotic behavior of one-dimensional network having a giant component is then investigated, which is distinctly different from its two-dimensional counterpart. For two-dimensional networks, we derive an asymptotic analytical upper bound on the minimum transmission range at which the probability of having a giant component of order above qn for any fixed 0 < q < 1 tends to one as n → ∞. Using the result, we show that significant energy savings can be achieved if we only require a large percentage of nodes (e.g., 95%, 99%) to be connected rather than requiring all nodes to be connected. That is, with a slightly relaxed requirement on connectivity, substantial energy savings can be achieved for a large network. For one-dimensional space, we study the network assuming the unit disk connection model. For two-dimensional space, we first consider the unit disk connection model and then discuss how results obtained assuming the unit disk connection model can be extended to more general connection models.

In this chapter we investigate the critical node density required to ensure that an arbitrary node in a large wireless network is connected (via multi-hop paths) to infinitely many other nodes with a positive probability, known as the percolation probability. A network is said to percolate if there exists a component of infinite order in the network. Specifically, assuming the infinite network model and the random connection model, we first obtain an upper and a lower bounds for the critical density. Then, we compare the bounds with other existing bounds in the literature under the unit disk connection model and the log-normal connection model, which are special cases of the random connection model. Percolation is an important subject in the study of connectivity of large random networks.

In this chapter, we study the phase transition behavior of k-connectivity (k = 1, 2, …) in large wireless networks where a total of n nodes are randomly and independently distributed following a uniform distribution in a unit cube [0, 1] ^d (d = 1, 2, 3), and each node has an identical transmission range r(n). It has been shown that the phase transition of k-connectivity becomes sharper as the total number of nodes n increases. In this chapter, we investigate how fast such phase transition happens, and derive a general formula for the phase transition width of k-connectivity for large enough n and for any fixed positive integer k in d-dimensional space by resorting to a Poisson approximation for the node placement. The results in this chapter are important for understanding the phase transition phenomenon in network connectivity.

In this chapter, we investigate connectivity of large wireless networks in the presence of interference. Different from previous chapters where connections are assumed to be independent, the presence of interference implies that signals transmitted at the same time will mutually interfere with each other. Hence, connections become mutually correlated. Specifically, consider the extended network model and the SINR connection model, we establish a sufficient condition and a necessary condition, i.e., an upper bound and a lower bound, on the transmission power required for a network adopting the carrier sense multiple access protocol to be asymptotically almost surely connected. The two bounds differ by a constant factor only. It is shown that the transmission power only needs to be increased by a constant factor to combat interference and maintain connectivity compared with that considering a unit disk connection model without interference.

In this chapter, we study the information propagation process in one-dimensional dynamic networks with vehicular ad hoc networks being the motivating example. Particularly, we consider a vehicular ad hoc network formed by vehicles Poissonly distributed on a highway. Corresponding to different lanes of the highway and different types of vehicles, we consider that vehicles in the network can be categorized into a number of traffic streams, where vehicles in the same traffic stream have the same speed distribution while the speed distributions of vehicles in different traffic streams are different. We analyze the information propagation process of the above vehicular network and characterize the information propagation speed. The results established in this chapter allow one to study the impact of parameters such as radio range, vehicle traffic density, vehicle speed distribution, and the temporal variation of vehicle speed on the information propagation speed.

In this chapter, we investigate the information propagation process in two-dimensional dynamic networks with mobile ad hoc networks being the motivating example. Particularly, we consider a two-dimensional mobile ad hoc network where nodes are initially randomly distributed and then move following a random direction mobility model. Adopting a popularly used Susceptible-Infectious-Recovered epidemic broadcast scheme, we analyze performance measures such as the fraction of nodes that can receive the information and the delay of the information dissemination process. The accuracy of analytical results is verified using simulations driven by both the random direction mobility model and a real world trace.

In this chapter, we study the connectivity of one-dimensional small to medium sized networks with and without infrastructure support. Different from the connectivity of large static networks and dynamic networks where asymptotic analysis is a major tool used in the analysis, for small to medium sized networks, the number of nodes in the network is not necessarily large enough to warrant the use of asymptotic analysis. Therefore, for small to medium sized networks, our focus is on characterizing three related connectivity measures, collectively called the probabilities of k-hop connection or hop count statistics, viz., 1) the probability that a randomly selected node is k-hops apart from another randomly selected node, i.e., the length of the shortest path from the first node to the second node measured by the number of hops is k; 2) the probability that a node \(\boldsymbol{x}\) apart from another node is connected to that node in exactly k hops; and 3) the spatial distribution of the nodes k-hops apart from another designated node. In this chapter, we investigate the aforementioned three connectivity measures for one-dimensional small to medium sized networks with and without infrastructure support.

In this chapter, we continue to investigate connectivity of two-dimensional small to medium sized networks by analyzing the three connectivity related measures: 1) the probability that a randomly selected node is k-hops apart from another randomly selected node, i.e., the length of the shortest path from the first node to the second node measured by the number of hops is k; 2) the probability that a node \(\boldsymbol{x}\) apart from another node is connected to that node in exactly k hops; and 3) the spatial distribution of the nodes k-hops apart from another designated node, which are collectively called the probabilities of k-hop connection or hop count statistics. We start with networks assuming the unit disk connection model and then move to networks assuming the random connection model and the log-normal connection model.

Despite intensive research in the area of network connectivity, there is an important category of problems that remain unsolved: how to characterize and measure the quality of connectivity of a wireless network which has a realistic number of nodes, not necessarily large enough to warrant the use of asymptotic analysis, and which has unreliable connections, reflecting the inherent unreliability of wireless communications? The quality of connectivity measures how easily and reliably a packet sent by a node can reach another node. It complements the use of capacity to measure the quality of a network in saturated traffic scenarios and provides an intuitive measure of the quality of (end-to-end) network connections. In this chapter, we introduce a probabilistic connectivity matrix as a tool to measure the quality of network connectivity. Some interesting properties of the probabilistic connectivity matrix and their connections to the quality of connectivity are demonstrated. We demonstrate that the largest magnitude eigenvalue of the probabilistic connectivity matrix, which is positive, can serve as a good measure of the quality of network connectivity. Furthermore, we provide a flooding algorithm whereby the nodes repeatedly flood the network with packets, and by measuring just the number of packets a given node receives, the node is able to asymptotically estimate this largest eigenvalue.

Connectivity studies play a vital role in the design, deployment, and management of a network. Furthermore, connectivity of a network conveys topological information of the network, which can be subsequently used to infer topology-related information of the network, e.g., location of nodes and boundary of the network. In this chapter, we give three examples on the applications of the connectivity studies. The first example is on the analysis of two key performance measures, viz., the access probability and the connectivity probability, of vehicular networks. The analysis reveals the tradeoffs between key system parameters, such as distance between vehicular infrastructure, e.g., base stations (BS) and road side units, vehicle density, transmission ranges of a BS and a vehicle, and their collective impact on the access probability and the connectivity probability under different communication channel models. The analysis enables network designers and operators to effectively improve network planning, deployment, and radio resource management. In the second example, we demonstrate the use of connectivity information to estimate the distance between a pair of neighboring nodes. Such distance estimates can be subsequently used to derive the relative location of nodes. In the third example, we introduce a category of connectivity-based wireless localization schemes that estimate the location of nodes directly using the connectivity information, without the need to first estimating the distances between particular pairs of neighboring nodes.