Stochastic Geometry and Random Graphs for the Analysis and Design of Wireless Networks

Wireless networks are fundamentally limited by the intensity of the received signals and by their interference. Since both of these quantities depend on the spatial location of the nodes, mathematical techniques have been developed in the last decade to provide communication-theoretic results accounting for the network?s geometrical configuration. Often, the location of the nodes in the network can be modeled as random, following for example a Poisson point process. In this case, different techniques based on stochastic geometry and the theory of random geometric graphs ? including point process theory, percolation theory, and probabilistic combinatorics ? have led to results on the connectivity, the capacity, the outage probability, and other fundamental limits of wireless networks. This tutorial article surveys some of these techniques, discusses their application to model wireless networks, and presents some of the main results that have appeared in the literature. It also serves as an introduction to the field for the other papers in this special issue.     

The Availability and Reliability of Wireless Multi-Hop Networks with Stochastic Link Failures

The network reliability and availability in wireless multi-hop networks can be inadequate due to radio induced interference. It is therefore common to introduce redundant nodes. This paper provides a method to forecast how the introduction of redundant nodes increases the reliability and availability of such networks. For simplicity, it is assumed that link failures are stochastic and independent, and the network can be modelled as a random graph. First, the network reliability and availability of a static network with a planned topology is explored. This analysis is relevant to mesh networks for public access, but also provides insight into the reliability and availability behaviour of other categories of wireless multi-hop networks. Then, by extending the analysis to also consider random geometric graphs, networks with nodes that are randomly distributed in a metric space are also investigated. Unlike many other random graph analyses, our approach allows for advanced link models where the link failure probability is continuously decreasing with an increasing distance between the two nodes of the link. In addition to analysing the steady-state availability, the transient reliability behaviour of wireless multi-hop networks is also found. These results are supported by simulations.     

Guest Editorial: Geometry and Random Graphs for the Analysis and Design of Wireless Networks

Confronted with the difficulties of analyzing large wireless networks such as cellular, ad hoc, and sensor networks, researchers have realized that the mathematical techniques used need to incorporate and explicitly model the network geometry, which is crucial to their connectivity, capacity, and reliability. As a consequence, stochastic geometry and the theory of random geometric graphs have emerged as essential tools in the analysis and design of large wireless systems. In the last decade, these techniques have led to important results and insights into the fundamental limits of wireless networks and the coverage of sensor networks. Specifically, point process theory and percolation theory were instrumental in recent breakthroughs. The deployment of wireless networks will continually become more dense and ubiquitous as time progresses, and hence become increasingly interference-limited. Therefore, the importance of the geometry of the transmitters and receivers in the network will increase further and understanding its effects will be crucial to the design of future wireless communication systems.     

Distributed Approximation Algorithms for Spectrum Allocation in Wireless ad Hoc Networks

Spectrum allocation is a difficult and hot issue in wireless ad hoc networks. An efficient method of spectrum allocation is a key factor to improve quality of service and performance of wireless networks. In this paper, we consider the spectrum allocation problem which asks how to allocate the least number of spectrum blocks in a field to ensure the service on any random k locations simultaneously. Our solution to the spectrum allocation problem is the minimum k-Roman dominating set. We propose two distributed algorithms for the issue of spectrum allocation in wireless ad hoc networks. One is a distributed 6k-approximation algorithm for the spectrum allocation of satisfying any random k (k ≥ 2) locations in the class of unit ball graphs. The other one is a better distributed algorithm for finding a (1 + ε)-approximation for the spectrum allocation problem of serving any random two locations, in the class of growth-bounded graphs. We also describe the simulation results and analyze them.     

Interference and Outage in Clustered Wireless Ad Hoc Networks

In the analysis of large random wireless networks, the underlying node distribution is almost ubiquitously assumed to be the homogeneous Poisson point process. In this paper, the node locations are assumed to form a Poisson cluster process on the plane. We derive the distributional properties of the interference and provide upper and lower bounds for its distribution. We consider the probability of successful transmission in an interference-limited channel when fading is modeled as Rayleigh. We provide a numerically integrable expression for the outage probability and closed-form upper and lower bounds. We show that when the transmitter–receiver distance is large, the success probability is greater than that of a Poisson arrangement. These results characterize the performance of the system under geographical or MAC-induced clustering. We obtain the maximum intensity of transmitting nodes for a given outage constraint, i.e., the transmission capacity (of this spatial arrangement) and show that it is equal to that of a Poisson arrangement of nodes. For the analysis, techniques from stochastic geometry are used, in particular the probability generating functional of Poisson cluster processes, the Palm characterization of Poisson cluster processes, and the Campbell–Mecke theorem.      

Transmission capacity for inhomogeneous overlaid wireless Ad-hoc networks

In the analysis of overlaid wireless Ad-hoc networks, the underlying node distributions are commonly assumed to be two independent homogeneous Poisson point processes. In this paper, by using stochastic geometry tools, a new inhomogeneous overlaid wireless Ad-hoc network model is studied and the outage probability are analyzed. By assuming that primary （PR） network nodes are distributed as a Poisson point process （PPP） and secondary （SR） network nodes are distributed as a Matern cluster processes, an upper and a lower bounds for the transmission capacity of the primary network and that of the secondary network are presented. Simulation results show that the transmission capacity of the PR and SR network will both have a small increment due to the inhomogeneity of the SR network.     

A Theory of Network Localization

In this paper, we provide a theoretical foundation for the problem of network localization in which some nodes know their locations and other nodes determine their locations by measuring the distances to their neighbors. We construct grounded graphs to model network localization and apply graph rigidity theory to test the conditions for unique localizability and to construct uniquely localizable networks. We further study the computational complexity of network localization and investigate a subclass of grounded graphs where localization can be computed efficiently. We conclude with a discussion of localization in sensor networks where the sensors are placed randomly     

低能耗节点位置未知无线传感器网络控制方案

介绍了一种低能耗节点位置未知的网络控制方案,根据不同的网络运行轮数设定网络节点的通信半径,使网络具有良好的能量有效性.网络中基站经过构建阶段的启动过程、节点信息收集过程和节点信息上报过程,获得了整个网络节点的相对位置分布,然后整合节点-节点信息支路,得到具有回路链接的簇首节点集,其他节点根据自己邻居信息选择簇首节点,实现网络近似最小能耗拓扑的构建.通过仿真与同类典型算法LEACH-C、MCLB进行比较,结果显示该方案应用于网络运行时具有更长的网络生命周期、更少的信息总数和更低的网络构建代价.     

Small worlds in wireless networks

In this study, the concept of small worlds is investigated in the context of wireless networks. Wireless networks are spatial graphs that tend to be much more clustered than random networks and have much higher path length characteristics. We observe that by adding a few short cut links, path length of wireless networks is reduced drastically. More interestingly, such short cut links need not be random but may be confined to a limited number of hops; a fraction of the network diameter. This facilitates the design of practical distributed algorithms, based on contacts, to improve performance of resource discovery in wireless networks.     

Mobile Target Positioning Using Refining Distance Measurements with Inaccurate Anchor Nodes in Chain-Type Wireless Sensor Networks

As a class of long and narrow structures widely exist such as the river, road, mine tunnel, pipe, chain-type wireless sensor networks (CWSN) can be applied to monitor these environments. The accurate position estimation is a key technology for the mobile target in CWSN. This paper proposes an innovative positioning method to estimate the position of mobile target. Firstly, wireless signals can be affected by measurement noises, coordinate errors of anchor nodes, and chain scene structure. Kernel canonical correlation analysis is applied to analyze the correlation coefficients of these nonlinear wireless signal sets. Secondly, we search out two maximum correlative sets of wireless signals and integrate them into a set of optimal wireless signals. Thirdly, the uncertainty coordinate of anchor node is modeled and the position of mobile target is estimated under measurement and geometry constraints. Furthermore, we simulate the proposed method for mobile target, in comparison with the weighted least squares (WLS) and CHAN methods. Estimation results indicate that the proposed method can refine distance measurement accuracy and perform better positioning performance than WLS and CHAN methods, when we vary the conditions of TDOA/AOA measurement errors, anchor nodes coordinate errors, and anchor nodes spacing distance. Finally, the actual positioning experiments are implemented in a corridor, which show that the practical estimation results are similar to the simulation results.     

Performance analysis of energy efficient cooperations in WSNs over frequency-selective channels

Energy efficient cooperations in wireless sensor networks (WSNs) subject to flat fading channels have attracted a considerable amount of attention recently. However, wireless channels of WSNs operating in indoor environments are supposed to have a frequency-selective nature, yet a comprehensive analysis of cooperative communications in these WSNs practically does not exist. Therefore, this paper has studied energy efficient cooperative communications over frequency-selective fading channels. Investigations of the energy efficient decode-and-forward and the adaptive decode-and-forward cooperations are provided in terms of the optimal power allocation and the partner selection region. The study is based on a network geometry of a fixed source node and a destination node with a range of potential partner node locations. Numerical results of optimal power allocation and the partner selection region are generated, and contour graphs of the resulting cooperative energy savings achieved from cooperations are provided using MATLAB. Results have indicated that cooperations can seek for potential partner nodes within a specified region to form energy efficient communications in WSNs operating in indoor environments. Furthermore, we have compared our results to the existing work which studies cooperations over flat fading channels, and several interesting findings have been revealed.     

Product Multicommodity Flow in Wireless Networks

We provide a tight approximate characterization of the n-dimensional product multicommodity flow (PMF) region for a wireless network of n nodes. Separate characterizations in terms of the spectral properties of appropriate network graphs are obtained in both an information-theoretic sense and for a combinatorial interference model (e.g., protocol model). These provide an inner approximation to the n ²-dimensional capacity region. Our results hold for general node distributions, traffic models, and channel fading models. We first establish that the random source-destination model assumed in many previous results on capacity scaling laws, is essentially a one-dimensional approximation to the capacity region and a special case of PMF. We then build on the results for a wireline network (graph) that relate PMF to its spectral (or cut) properties. Specifically, for a combinatorial interference model given by a network graph and a conflict graph, we relate the PMF to the spectral properties of the underlying graphs resulting in simple computational upper and lower bounds. These results show that the 1/radicn scaling law obtained by Gupta and Kumar for a geometric random network can be explained in terms of the scaling law of the conductance of a geometric random graph. For the more interesting random fading model with additive white Gaussian noise (AWGN), we show that the scaling laws for PMF can again be tightly characterized by the spectral properties of appropriately defined graphs-such a characterization for general wireless networks has not been available before. As an implication, we obtain computationally efficient upper and lower bounds on the PMF for any wireless network with a guaranteed approximation factor.     

认知Ad Hoc网络吞吐量分析与优化

考虑两个无线Ad Hoc网络（主网络与次级网络）的并存模型:主网络与次级网络节点依照不同密度的空间泊松点过程并存于同一区域并共享同一频谱,两种网络节点均采用时隙ALOHA协议,按照各自的传输概率进行通信。本文首先根据随机几何理论对来自本网络的自干扰与来自其它网络的互干扰进行建模,然后分别推导了在AWGN信道和Rayleigh衰落信道下,单网络及并存式网络时节点平均吞吐量的闭合表达式,最后采用优化准则得到最佳传输概率,使节点平均吞吐量达到目标性能上的最优。仿真结果表明:经推导的闭合表达式与仿真值相近;在比例公平准则下,传输控制策略能达到主网络与次级网络之间公平性与高效性的折中。      

Capacity of wireless erasure networks

In this paper, a special class of wireless networks, called wireless erasure networks, is considered. In these networks, each node is connected to a set of nodes by possibly correlated erasure channels. The network model incorporates the broadcast nature of the wireless environment by requiring each node to send the same signal on all outgoing channels. However, we assume there is no interference in reception. Such models are therefore appropriate for wireless networks where all information transmission is packetized and where some mechanism for interference avoidance is already built in. This paper looks at multicast problems over these networks. The capacity under the assumption that erasure locations on all the links of the network are provided to the destinations is obtained. It turns out that the capacity region has a nice max-flow min-cut interpretation. The definition of cut-capacity in these networks incorporates the broadcast property of the wireless medium. It is further shown that linear coding at nodes in the network suffices to achieve the capacity region. Finally, the performance of different coding schemes in these networks when no side information is available to the destinations is analyzed.     

Topology matters in network coding

Seeking to understand the potential of network coding in future internet endeavors, we consider the vital role of network topology with respect to the potential benefits of Random Linear Network Coding (RLNC). First, we propose a set of metrics that capture the essential trade-offs between throughput, confidentiality and decoding delay. Using large network simulation, we are able to evaluate the behavior of RLNC for various topological classes based on random graphs. Our results show significant differences between local dissemination of information (typical of wireless networks) and long range connectivity (typical of peer-to-peer environments). We believe that our results can help pave the way for the creation of better overlay topologies for RLNC protocols in future internet applications.     

无线传感器网络的神经网络模型

无线传感器网络是复杂的无线网络。无线传感器网络拥有大量的网络节点。网络节点是无线传感器网络的基础。为了研究复杂的无线传感器网络，采用了神经元描述了WSN的网络节点，用神经元模型表示了无线传感器网络。给出了无线待感器网络节点的神经元模型和无线传感器网络的神经网络模型，并将神经网络应用于无线传感器网络的数据融合应用。结果表明，基于神经网络的无线传感器网络研究可以使得复杂研究变得简单，利于开展WSN的深入研究。     

无线mesh网中最小编码代价低时延多播路由

提出了一种无线mesh网中最小网络编码代价低时延多播路由协议(MNCLDMR, minimal network coding and low delay multicast routing)。MNCLDMR的目标是选择合适的网络编码节点,最小化网络编码代价,降低网络时延。MNCLDMR主要思想是引入拓扑关键节点和网络编码关键节点的概念,以下一跳的节点是否是网络编码关键节点或拓扑关键节点作为路由判据,采用MNCLD算法构造多播树。仿真结果表明,MNCLDMR可以达到预定目标,合理形成网络编码机会,能实现最小网络编码代价低时延多播路由。     

Efficient Topology Control for Ad-Hoc Wireless Networks with Non-Uniform Transmission Ranges

Wireless network topology control has drawn considerable attention recently. Priori arts assumed that the wireless ad hoc networks are modeled by unit disk graphs (UDG), i.e., two mobile hosts can communicate as long as their Euclidean distance is no more than a threshold. However, practically, the networks are never so perfect as unit disk graphs: the transmission ranges may vary due to various reasons such as the device differences, the network control necessity, and the perturbation of the transmission ranges even the transmission ranges are set as the same originally. Thus, we assume that each mobile host has its own transmission range. The networks are modeled by mutual inclusion graphs (MG), where two nodes are connected iff they are within the transmission range of each other. Previously, no method is known for topology control when the networks are modeled as mutual inclusion graphs.The paper proposes the first distributed mechanism to build a sparse power efficient network topology for ad hoc wireless networks with non-uniform transmission ranges. We first extend the Yao structure to build a spanner with a constant length and power stretch factor for mutual inclusion graph. We then propose two efficient localized algorithms to construct connected sparse network topologies. The first structure, called extended Yao-Yao, has node degree at most O(log ), where = max_u max_uvMG . The second structure, called extended Yao and Sink, has node degree bounded by O(log ), and is a length and power spanner. The methods are based on a novel partition strategy of the space surrounded each mobile host. Both algorithms have communication cost O(n) under a local broadcasting communication model, where each message has O(log n) bits.Xiang-Yang Li has been an Assistant Professor of Computer Science at the Illinois Institute of Technology since 2000. He received MS (2000) and PhD (2001) degree at Department of Computer Science from University of Illinois at Urbana-Champaign. He received his Bachelor degree at Department of Computer Science and Bachelor degree at Department of Business Management from Tsinghua University, P.R. China in 1995. His research interests span the computational geometry, wireless ad hoc networks, game theory, cryptography and network security. Recently, he focuses on performing research on the cooperation, energy efficiency, and distributed algorithms for wireless ad hoc and sensor networks. He served various positions at a number of international conferences. He recently co-organized a special issue of ACM MONET on non-cooperative computing in wireless networks. He is a member of the ACM, IEEE.Wen-Zhan Song received the B.S. degree and M.Eng. degree in computer science from Nanjing University of Science and Technology, Nanjing, in 1997 and 2000. He joined the Department of Computer Science, Illinois Institute of Technology as a Ph.D candidate in 2001. His research interests include wireless networks, and Peer-to-Peer systems.Yu Wang received the PhD degree in computer science from Illinois Institute of Technology in 2004, the BEng degree and the MEng degree in computer science from Tsinghua University, China, in 1998 and 2000. He has been an assistant professor of computer science at the Univeristy of North Carolina at Charlotte since 2004. His current research interests include wireless networks, mobile computing, algorithm design, and artificial intelligence. He is a member of the ACM, IEEE, and IEEE Communication Society.     

On Joint MAC and Network Coding in Wireless Ad Hoc Networks

This paper addresses network coding in wireless networks in conjunction with medium access control (MAC). It is known that coding over wired networks enables connections with rates that cannot be achieved by routing. However, the properties of wireless networks (e.g., omnidirectional transmissions, destructive interference, single transceiver per node, finite energy) modify the formulation of time-varying network coding in a way that reflects strong interactions with underlying MAC protocols and deviates from the classical approach used in wired network coding. To perform network coding over conflict-free transmission schedules, predetermined network realizations are separately activated by a time-division mechanism and the content of network flows is derived through network coding to optimize performance measures such as achievable throughput and energy costs. A systematic method is presented to construct linear wireless network codes and interactions with MAC schedules are discussed under wireless assumptions. Network coding is also extended to operate with arbitrary (random or scheduled access based) MAC protocols. Alternatively, conflict-free transmission schedules are jointly constructed with network codes by decomposing wireless networks into subtrees and employing graph coloring on simplified subtree graphs. Finally, network coding and plain routing are compared in terms of throughput, energy and delay performance under different MAC solutions.     

Clique Number vs. Chromatic Number in Wireless Interference Graphs: Simulation Results

Interference due to transmissions by adjacent nodes in a multi-hop wireless network can be modeled using a unit disc graph (UDG). We investigate the reliability associated with using the clique number instead of the chromatic number of the UDG while computing the interference. In our extensive simulations with UDGs of random networks, we observed that the clique number and the chromatic number values were typically very close to one another and the maximum deviation was much less than the theoretical bounds. This implies very high reliability in the proposed approximation.