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.     

Identifying Neighbor and Connectivity of Wireless Sensor Networks with Poisson Point Process

Identifying neighbor and connectivity are the fundamental requirements in wireless sensor networks. The sensor nodes are scattered randomly over the area of interest and their first step is to identify their immediate neighbors, i.e., the nodes with which they have direct wireless communication. On the other hand, connectivity ensures that sensor nodes can communicate with each other in order to aggregate sensing data hop by hop to the base stations (sink nodes). In this paper, we study identifying neighbor and connectivity in the context of wireless sensor networks, using Poisson point process theory.     

The study on degree distribution property of complex network based on cooperative communication

Complex networks have been widely studied. Recently, many results show that the degree dis-tributions of some large networks follow the form of power-law and these networks possess better robust-ness against random nodes failure. As an effective technology on combating the channel fading, wireless co-operative communication is becoming one of the most important methods to improve the wireless communi-cation performances. In this paper, the complex network models based on cooperative communication and non-cooperative communication are established; and the degree distribution properties for them are studied. The simulation results show that the degree distributions of these networks also follow the form of power-law, which means that the addition of cooperative communication links will not change the property of degree distribution and then these networks will possess better robustness against random nodes failure as well.     

Capacity and interference modeling of CSMA/CA networks using SSI point processes

The relative location of simultaneous transmitters, i.e. the set of nodes transmitting a frame at a given time, has a crucial impact on the performance of multi hop wireless networks. Two fundamental aspects of wireless network performances are related to these locations: capacity and interference. Indeed, as interference results from the summation of signals stemmed by concurrent transmitters, it directly depends on the transmitters’ location. On the other hand, the network capacity is proportional to the number of simultaneous transmitters. In this paper, we investigate original point processes that can be used to model the location of transmitters that comply with the CSMA/CA policies, i.e. the Medium Access Control protocol used in 802.15.4 and 802.11 families of wireless technologies. We first propose the use of the Simple Sequential Inhibition point process to model CSMA/CA networks where clear channel assessment depends on the strongest emitter only. We then extend this point process to model a busy medium detection based on the strength of all concurrent signals. We finally compare the network capacity obtained through realistic simulations to a theoretical capacity estimated using the intensity of the SSI point process. It turns out that the proposed model is validated by the simulations.     

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.     

On providing location privacy for mobile sinks in wireless sensor networks

A common practice in sensor networks is to collect sensing data and report them to the sinks or to some pre-defined data rendezvous points via multi-hop communications. Attackers may locate the sink easily by reading the destination field in the packet header or predicting the arrival of the sink at the rendezvous points, which opens up vulnerabilities to location privacy of the sinks. In this paper, we propose a random data collection scheme to protect the location privacy of mobile sinks in wireless sensor networks. Data are forwarded along random paths and stored at the intermediate nodes probabilistically in the network. The sinks will move around randomly to collect data from the local nodes occasionally, which prevents the attackers from predicting their locations and movements. We analyze different kind of attacks threatening the location privacy of the sinks in sensor networks. We also evaluate the delivery rate, data collection delay and protection strength of our scheme by both analysis and simulations. Both analytical and simulation results show that our scheme can protect location privacy of mobile sinks effectively, while providing satisfactory data collection services.     

Some Fundamental Results on Complex Network Problem for Large-Scale Wireless Sensor Networks

Wireless sensor networks (WSNs) are typically constituted by a large number of connected wireless sensors (nodes), generally distributed at random on a given surface area. In such large-scale networks, the desired global system performance is achieved by gathering local information and decisions collected from each individual node. There exist two fundamental global issues on WSNs that we consider here, i.e. full network connectivity and network lifetime. Full connectivity can be obtained either by increasing transmission range, at the expense of consuming higher transmission power, or by increasing the number of sensors, i.e. by increasing network costs. Both of them are closely related to global network lifetime, in the sense that the higher the power consumption or the more sensors deployed the shorter the network lifetime [31]. So the main question is, how can one design large-scale random networks in order to have both global connectivity and maximum network lifetime? Although these questions have been addressed often in the past, a definite, simple predicting algorithm for achieving these goals does not exist so far. In this paper, we aim to discuss such a scheme and confront it with extensive simulations of random networks generated numerically. Specifically, we study the minimum number of nodes required to achieve full network connectivity, and present an analytical formula for estimating it. The results are in very good agreement with the numerical simulations as a function of transmission range. In addition, we study in detail several other statistical properties of large-scale WSNs, such as average path distance, clustering coefficient, degree distribution, etc., also as a function of the transmission range, both qualitatively and quantitatively. We discuss results on how to further improve network energy consumption from the original networks considered by switching off (deleting) some nodes at random but keeping whole network connectivity. The present results are expected to be useful for the design of more efficient large-scale WSNs.     

Distributional Properties of Euclidean Distances in Wireless Networks Involving Road Systems

Stochastic models for hierarchical telecommunication networks are considered, which can be applied to the analysis and planning of large wireless networks. The network geometry is modelled by random geometric graphs, and the locations of network nodes by point processes on the edges of these graphs. In particular, the locations of high-level components (HLC) are modeled by Cox processes concentrated on the edge sets of random graphs, where their serving zones are the cells of Voronoi tessellations induced by these Cox processes. The locations of low-level components (LLC) are either modeled by planar Poisson processes or by Cox processes concentrated on the same edge sets as the HLC. Distributional properties of distances between the locations of network nodes are closely related with the interference geometry and, consequently, the performance of wireless networks. Representation formulas are derived for the distribution function and density of the typical Euclidean connection distance between LLC and HLC. They lead to suitable estimators of these characteristics, which can be computed by Monte Carlo simulation of the typical serving zone and the typical segment system in it, respectively.     

CRWSNP: cooperative range-free wireless sensor network positioning algorithm

Sensing events occur in an area without knowing the events locations, is meaningless. Since there is no priorly knowledge about the locations of most of the sensors which scattered randomly in an area, wireless sensor network localization methods try to find out where sensors are located. A new cooperative and distributed range-free localization algorithm, based on only connectivity information is proposed in this paper. The method first uses convex optimization techniques to find primitive target nodes locations estimation, then nodes cooperate with each other in several iterations to improve the whole network location estimation. CRWSNP converges after a finite number of iterations because of applying two novel heuristic location correction techniques. As well as, results of the algorithm have been compared with six range-free based methods like CPE, DV-hop, APIT; and CRWSNP algorithm provides more accurate results over 50 random topologies for the network, in mean error and maximum error metrics.     

Cooperative data collection in ad hoc networks

This paper studies the problem of data gathering in multi-hop wireless ad hoc networks. In this scenario, a set of wireless devices constantly sample their surroundings and initiate report messages addressed to the base station. The messages are forwarded in a multi-hop fashion, where the wireless devices act both as senders and relays. We consider data gathering without aggregation, i.e. the nodes are required to forward all the messages initiated by other nodes (in addition to their own) to the base station. This is in contrast to the well studied problem of data gathering with aggregation, which is significantly simpler. As some nodes experience a larger load of forward requests, these nodes will have their battery charges depleted much faster than the other nodes—which can rapidly break the connectivity of the network. We focus on maximizing the network lifetime through efficient balancing of the consumed transmission energy. We show that the problem is NP-hard for two network types and develop various approximation schemes. Our results are validated through extensive simulations.     

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

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

LIP: an efficient lightweight iterative positioning algorithm for wireless sensor networks

Wireless sensor networks (WSNs) are increasingly being used in remote environment monitoring, security surveillance, military applications, and health monitoring systems among many other applications. Designing efficient localization techniques have been a major obstacle towards the deployment of WSN for these applications. In this paper, we present a novel lightweight iterative positioning (LIP) algorithm for next generation of wireless sensor networks, where we propose to resolve the localization problem through the following two phases: (1) initial position estimation and (2) iterative refinement. In the initial position estimation phase, instead of flooding the network with beacon messages, we propose to limit the propagation of the messages by using a random time-to-live for the majority of the beacon nodes. In the second phase of the algorithm, the nodes select random waiting periods for correcting their position estimates based on the information received from neighbouring nodes. We propose the use of Weighted Moving Average when the nodes have received multiple position corrections from a neighbouring node in order to emphasize the corrections with a high confidence. In addition, in the refinement phase, the algorithm employs low duty-cycling for the nodes that have low confidence in their position estimates, with the goal of reducing their impact on localization of neighbouring nodes and preserving their energy. Our simulation results indicate that LIP is not only scalable, but it is also capable of providing localization accuracy comparable to the Robust Positioning Algorithm, while significantly reducing the number of messages exchanged, and achieving energy savings.     

Estimation of the Average Search Length of Random Walks in Power-Law Networks

In this paper we introduce a model to study random walks in power-law networks with one-hop replication. Basically, this model gives a set of expressions that captures how the knowledge about the network evolves as the random walk traverses the network: how many nodes have been known, either because they or their neighbors have been visited by the random walk. With this, we obtain an expression that gives a good estimation of the average number of hops needed to find some random peer from any other random peer. We denote this metric the average search length, and we deem it can be very useful to evaluate random walk based resource location solutions in P2P networks.     

The Impact of Deployment Pattern and Routing Scheme on the Lifetime in Multi-Sink Wireless Sensor Network

Extensive use of sensor and actuator networks in many real-life applications introduced several new performance metrics at the node and network level. Since wireless sensor nodes have significant battery constraints, therefore, energy efficiency, as well as network lifetime, are among the most significant performance metrics to measure the effectiveness of given network architecture. This work investigates the performance of an event-based data delivery model using a multipath routing scheme for a wireless sensor network with multiple sink nodes. This routing algorithm follows a sink initiated route discovery process with the location information of the source nodes already known to the sink nodes. It also considers communication link costs before making decisions for packet forwarding. Carried out simulation compares the network performance of a wireless sensor network with a single sink, dual sink, and multi sink networking approaches. Based on a series of simulation experiments, the lifetime aware multipath routing approach is found appropriate for increasing the lifetime of sensor nodes significantly when compared to other similar routing schemes. However, energy-efficient packet forwarding is a major concern of this work; other network performance metrics like delay, average packet latency, and packet delivery ratio are also taken into the account.

     

Anomaly detection in wireless sensor networks

Anomaly detection in wireless sensor networks is an important challenge for tasks such as fault diagnosis, intrusion detection, and monitoring applications. The algorithms developed for anomaly detection have to consider the inherent limitations of sensor networks in their design so that the energy consumption in sensor nodes is minimized and the lifetime of the network is maximized. In this survey article we analyze the state of the art in anomaly detection techniques for wireless sensor networks and discuss some open issues for research.     

带有黑洞节点探测的间断连接无线网络数据转发机制

间断连接无线网络利用节点移动产生的通信机会完成数据传输,但网络中的恶意节点通过伪造节点的相遇信息等方法,吸引并丢弃数据,影响网络的运行。该文提出带有黑洞攻击探测的间断连接无线网络数据转发机制,通过节点诚信度、信用度、间接信任度及数据转发能力4维信任属性的评估,获知攻击节点的行为规律,并采用粗糙集理论降低网络运行过程中产生的不确定状态信息引发的误判率,更加准确地对节点的可信性进行判断,进而,合理地为数据选择中继节点。结果表明,所提出的方法能有效提升黑洞节点的辨识率,对网络中其它非协作行为也有一定探测和防御能力,能显著改善网络性能。     

Design and analysis of novel quorum-based sink location service scheme in wireless sensor networks

Geographic routing in wireless sensor networks requires sources nodes to be aware of the location information of sinks to send their data. To provide the sink location service, quorum-based schemes have been proposed, which exploit crossing points between a quorum of a sink location announcement (SLA) message from a sink and a quorum of a sink location query (SLQ) message from a source node. For guaranteeing at least one crossing point in irregular sensor networks with void areas or irregular boundaries, the previous schemes however collect and flood the network boundary information or forward a SLA and SLQ message along the whole network boundary. In this paper, we design a novel quorum-based sink location service scheme that exploits circle and line quorums, which does not require the network boundary information and send a SLA and SLQ message along the whole network boundary. In the proposed scheme, a source node sends a SLQ message to the network center and sends another SLQ message to an edge node in the network boundary, thus generating a SLQ line quorum. On the other hand, a sink node sends a SLA message along a circle path whose center is the network center, thus forming a SLQ circle quorum. By this way, it is guaranteed that the SLQ and SLA quorums have at least one crossing point in irregular sensor networks. Both numerical analysis and extensive simulation results verify that the proposed scheme outperforms the existing schemes in terms of the delivery distance, the delivery hop count, and the energy consumption for providing sink location service.     

Realistic mobility simulation of urban mesh networks

It is a truism that today’s simulations of mobile wireless networks are not realistic. In realistic simulations of urban networks, the mobility of vehicles and pedestrians is greatly influenced by the environment (e.g., the location of buildings) as well as by interaction with other nodes. For example, on a congested street or sidewalk, nodes cannot travel at their desired speed. Furthermore, the location of streets, sidewalks, hallways, etc. restricts the position of nodes, and traffic lights impact the flow of nodes. And finally, people do not wander the simulated region at random, rather, their mobility depends on whether the person is at work, at lunch, etc. In this paper, realistic simulation of mobility for urban wireless networks is addressed. In contrast to most other mobility modeling efforts, most of the aspects of the presented mobility model and model parameters are derived from surveys from urban planning and traffic engineering research. The mobility model discussed here is part of the UDel Models, a suite of tools for realistic simulation of urban wireless networks. The UDel Models simulation tools are available online.     

基于信号幅度衰减测距的水下定位方法

无线传感器网络中节点规模大、能量有限、可靠性差、随机部署,无线模块的通信距离有限,虽然运用全球定位系统是个很好的选择,但是其体积大、成本高、能耗多而且需要基础设施,不适用于低成本、自组织的无线传感器网络。通过研究发现,基于信号幅度衰减测距的水下定位方法不仅能够满足无线传感器网络节点定位的要求,而且其成本较低,易理解及操作,精度高。     

Queuing network models for delay analysis of multihop wireless ad hoc networks

In this paper we analyze the average end-to-end delay and maximum achievable per-node throughput in random access multihop wireless ad hoc networks with stationary nodes. We present an analytical model that takes into account the number of nodes, the random packet arrival process, the extent of locality of traffic, and the back off and collision avoidance mechanisms of random access MAC. We model random access multihop wireless networks as open G/G/1 queuing networks and use the diffusion approximation in order to evaluate closed form expressions for the average end-to-end delay. The mean service time of nodes is evaluated and used to obtain the maximum achievable per-node throughput. The analytical results obtained here from the queuing network analysis are discussed with regard to similarities and differences from the well established information-theoretic results on throughput and delay scaling laws in ad hoc networks. We also investigate the extent of deviation of delay and throughput in a real world network from the analytical results presented in this paper. We conduct extensive simulations in order to verify the analytical results and also compare them against NS-2 simulations.