Skip to main content
main-content

Über dieses Buch

This book introduces a number of recent developments on connectivity of communication networks, ranging from connectivity of large static networks and connectivity of highly dynamic networks to connectivity of small to medium sized networks. This book also introduces some applications of connectivity studies in network optimization, in network localization, and in estimating distances between nodes. The book starts with an overview of the fundamental concepts, models, tools, and methodologies used for connectivity studies. The rest of the chapters are divided into four parts: connectivity of large static networks, connectivity of highly dynamic networks, connectivity of small to medium sized networks, and applications of connectivity studies.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Introduction

This chapter provides an overview of the fundamental concepts, models, tools, and methodologies used for connectivity studies. We start with an introduction to the major connection models used to describe the establishment of communication links between devices or nodes. These include the Erdős–Rényi connection model, the unit disk connection model, the log-normal connection model, the random connection model, and the SINR connection model. The relationship of these models and their impact on connectivity studies are discussed. Next, we cover the network models that have been widely used to capture the spatial distribution of nodes. Particularly, the dense network model, the extended network model, and the infinite network model are discussed. Finally, we briefly introduce the main tools and methodologies used for connectivity studies, including Continuum percolation theory, branching process, and algebraic graph theory, and present the main results, established using these tools, on network connectivity.
Guoqiang Mao

Connectivity of Large Static Networks

Frontmatter

Chapter 2. Large Network Models and Their Implications

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.
Guoqiang Mao

Chapter 3. Connectivity of Large Wireless Networks: Sufficient and Necessary Conditions

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.
Guoqiang Mao

Chapter 4. Giant Component in Large Wireless Networks

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.
Guoqiang Mao

Chapter 5. Critical Density for Percolation

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.
Guoqiang Mao

Chapter 6. Phase Transitions in Large 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.
Guoqiang Mao

Chapter 7. Connectivity of Large Wireless Networks in the Presence of Interference

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.
Guoqiang Mao

Connectivity of Highly Dynamic Networks

Frontmatter

Chapter 8. Connectivity of Dynamic Networks

In this chapter, we study connectivity of networks with dynamically changing network topology. In wireless networks, a change in topology can be caused by node mobility, by node or link failure, or by nodes being switched on or off for energy saving purposes. Dynamic networks offer many interesting and unique challenges than its static counterparts. Particularly, a dynamic network may be disconnected at any time instant but a message transmitted by any node can still reach any other node over time. That is, a dynamic network may become connected over time. In this chapter, we introduce those properties of dynamic networks that are different from statistic networks from the connectivity perspective. We extend and develop the concepts of route matrix, connectivity matrix, and probabilistic connectivity matrix as convenient tools to characterize and investigate properties of dynamic networks. The properties of these matrices are established and their relevance to properties of dynamic networks are introduced.
Guoqiang Mao

Chapter 9. Information Propagation in One-Dimensional Dynamic Networks

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.
Guoqiang Mao

Chapter 10. Information Propagation in Two-Dimensional Dynamic Networks

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.
Guoqiang Mao

Connectivity of Small to Medium Sized Networks

Frontmatter

Chapter 11. Connectivity of One-Dimensional Small to Medium Sized Networks

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.
Guoqiang Mao

Chapter 12. Connectivity of Two-Dimensional Small to Medium Sized Networks

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.
Guoqiang Mao

Chapter 13. A New Measure of Wireless Network Connectivity

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.
Guoqiang Mao

Applications of Connectivity Studies

Frontmatter

Chapter 14. Applications of Connectivity Studies

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.
Guoqiang Mao

Backmatter

Weitere Informationen

BranchenIndex Online

Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.

Whitepaper

- ANZEIGE -

Globales Erdungssystem in urbanen Kabelnetzen

Bedingt durch die Altersstruktur vieler Kabelverteilnetze mit der damit verbundenen verminderten Isolationsfestigkeit oder durch fortschreitenden Kabelausbau ist es immer häufiger erforderlich, anstelle der Resonanz-Sternpunktserdung alternative Konzepte für die Sternpunktsbehandlung umzusetzen. Die damit verbundenen Fehlerortungskonzepte bzw. die Erhöhung der Restströme im Erdschlussfall führen jedoch aufgrund der hohen Fehlerströme zu neuen Anforderungen an die Erdungs- und Fehlerstromrückleitungs-Systeme. Lesen Sie hier über die Auswirkung von leitfähigen Strukturen auf die Stromaufteilung sowie die Potentialverhältnisse in urbanen Kabelnetzen bei stromstarken Erdschlüssen. Jetzt gratis downloaden!

Bildnachweise