Accelerated collection of sensor data by mobility-enabled topology ranks

We study the problem of fast and energy-efficient data collection of sensory data using a mobile sink, in wireless sensor networks in which both the sensors and the sink move. Motivated by relevant applications, we focus on dynamic sensory mobility and heterogeneous sensor placement. Our approach basically suggests to exploit the sensor motion to adaptively propagate information based on local conditions (such as high placement concentrations), so that the sink gradually “learns” the network and accordingly optimizes its motion. Compared to relevant solutions in the state of the art (such as the blind random walk, biased walks, and even optimized deterministic sink mobility), our method significantly reduces latency (the improvement ranges from 40% for uniform placements, to 800% for heterogeneous ones), while also improving the success rate and keeping the energy dissipation at very satisfactory levels.     

Cellular automaton-based algorithms for the dispersion of mobile wireless sensor networks

Due to the advent of sensor technology and its applications, mobile wireless sensor networks (MWSNs) have gained a significant amount of research interest. In a typical MWSN, sensors can move within the network. We develop a set of probabilistic and deterministic cellular automaton (CA)-based algorithms for motion planning problems in MWSNs. First, we consider a scenario where a group of sensors are deployed and they need to disperse in order to maximise the area covered by the network. In this variant of the problem we do not explicitly consider that the sensors should maintain the connectivity of the network while they move. Second, we consider a scenario where the sensors are initially randomly distributed and they need to disperse autonomously to both maximise the coverage of the network and maintain its connectivity. We carry out extensive simulations of both deterministic and randomised variants of the algorithms. For the first variant of the problem we compare our algorithms with one previous algorithm and find that our algorithm yields better network coverage than the earlier algorithm. We also find that probabilistic algorithms have better overall performance for the second variant. CA algorithms rely only on local information about the network and, hence, they can be used in practice for MWSN problems. On the other hand, locality of the algorithm implies that maintaining connectivity becomes a non-trivial problem.     

Optimal Sensor Networks for Area Monitoring Using Rotating and Beam Sensors

We consider the problem of monitoring the Euclidean plane using rotating sensors with detection sectors and beam sensors. We assume that intruders can appear anywhere at any time and move arbitrarily fast, and may have full knowledge of the sensor network. We require that such intruders be detected within a finite amount of time. We give an optimal network for this problem consisting of a combination of rotating sensors of angle 0 and beam sensors that uses the minimum number of both types of sensors. We show a trade-off between the density of beam sensors needed and the angle of the detection sector of the rotating sensors. Secondly, we give a family of sensor networks using only rotating sensors for the same problem, that demonstrate a trade-off between the detection time and the density of rotating sensors used. We show that the density of rotating sensors required in this case can be significantly reduced by increasing the angle of detection sectors. Finally, we show that our results on the infinite plane can be used to derive sensor networks that monitor some finite regions using a density of sensors that is asymptotically the same, or close to that of the infinite plane case.     

An efficient trajectory design for mobile sink in a wireless sensor network

Mobile sink trajectory plays a pivotal role for network coverage, data collection and data dissemination in wireless sensor networks. Considering this, we propose a novel approach for mobile sink trajectory in wireless sensor networks. Our proposed approach is based on Hilbert Space Filling Curve, however, the proposed approach is different from the previous work in a sense that the curve order changes according to node density. In this paper, we investigate the mobile sink trajectory based on Hilbert Curve Order which depends upon the size of the network. Second, we calculate the Hilbert Curve Order based on node density to re-dimension the mobile sink trajectory. Finally, we perform extensive simulations to evaluate the effectiveness of proposed approach in terms of network coverage and scalability. Simulation results confirm that our proposed approach outperforms with size based Hilbert Curve in terms of network coverage, packet delivery ratio and average energy consumption.     

Termite-hill: Performance optimized swarm intelligence based routing algorithm for wireless sensor networks

A wireless sensor network (WSN) is a large collection of sensor nodes with limited power supply, constrained memory capacity, processing capability, and available bandwidth. The main problem in event gathering in wireless sensor networks is the formation of energy-holes or hot spots near the sink. Due to the restricted communication range and high network density, events forwarding in sensor networks is very challenging, and require multi-hop data forwarding. Improving network lifetime and network reliability are the main factors to consider in the research associated with WSN. In static wireless sensor networks, sensors nodes close to the sink node run out of energy much faster than nodes in other parts of the monitored area. The nodes near the sink are more likely to use up their energy because they have to forward all the traffic generated by the nodes farther away to the sink. The uneven energy consumption results in network partitioning and limit the network lifetime. To this end, we propose an on-demand and multipath routing algorithm that utilizes the behavior of real termites on hill building termed Termite-hill which support sink mobility. The main objective of our proposed algorithm is to efficiently relay all the traffic destined for the sink, and also balance the network energy. The performance of our proposed algorithm was tested on static, dynamic and mobile sink scenarios with varying speed, and compared with other state-of-the-art routing algorithms in WSN. The results of our extensive experiments on Routing Modeling Application Simulation Environment (RMASE) demonstrated that our proposed routing algorithm was able to balance the network traffic load, and prolong the network lifetime.     

基于网络效率的线性无线传感器网络优化部署算法

基于多跳的无线传感器网络,靠近sink的传感器节点因需要转发更多的数据,其能量消耗较多,从而在sink周围形成"能量空洞".采用更符合实际的单位部署成本的网络寿命,即网络效率作为优化目标.在仅已知网络规模和节点感知半径r的情况下,如何通过有效的节点部署来避免"能量空洞"并使网络效率最大,是一个极具挑战性的研究课题.提出了一种高效节点部署算法,求解出了最优工作节点数、最佳中继节点部署方案、最优节点传输距离.理论分析与模拟实验结果表明,算法不仅能够避免"能量空洞",而且相对于已有均匀与非均匀算法都能有效提高网络效率,因此该算法对构建低成本的无线传感网络应用系统具有重要意义.     

Analyzing multi-hop routing feasibility for sensor data harvesting using mobile sinks

This paper presents a modeling framework for characterizing the feasibility and impacts of multi-hop packet routing in sensor networks with mobile sinks. Data collection in sensor networks using mobile sinks has recently been investigated to improve energy performance at the cost of collection delay. Although the data collection can be accomplished with varying degrees of multi-hop routing, for a given data generation rate, as the extent of multi-hop routing increases, the round traversal time of the sink decreases. At the same time, the interference experienced by the mobile sink-to-sensor links and the consequent upload time go up. This paper characterizes these competing effects and develops a methodology for determining the extent of multi-hop routing that is feasible for given network and application parameters such as sensor data generation rate, wireless link capacity between sensors and mobile sink, the speed of the mobile sink and node density.     

基于轨迹受限的移动Sink低能耗数据收集协议

无线传感器网络数据收集的能耗问题一直以来都是研究的热点。本文主要研究基于移动Sink轨迹受限的数据收集协议。首先针对轨迹受限的无线传感网络提出一种通用的系统模 型,将该问题形式化为最大化降低全网总路径长度轨迹设计问题 (Maximizing total length reduction for constrained trajectory, MTRC),并证明了MTRC为NP-Hard问题;然后设计一种轨迹约束低能耗贪心算法 (Trajectory constrain of low energy consumption, TCLEC),通过 TSP近似算法设计最大化降低有效长度的Sink移动轨迹。理论分析和仿真实验结果表明,TCLEC在网络拓扑数据收集树的初始化以及优化方面是高效的,并且相对于同类基于移动Sink的无线传感网络分层数据收集方法,其能耗降低了7%左右。     

Sleep–wake up scheduling with probabilistic coverage model in sensor networks1

Energy optimisation is one of the important issues in the research of wireless sensor networks (WSNs). In the application of monitoring, a large number of sensors are scattered uniformly to cover a collection of points of interest (PoIs) distributed randomly in the monitored area. Since the energy of battery-powered sensor is limited in WSNs, sensors are scheduled to wake up in a large-scale sensor network application. In this paper, we consider how to reduce the energy consumption and prolong the lifetime of WSNs through wake-up scheduling with probabilistic sensing model in the large-scale application of monitoring. To extend the lifetime of sensor network, we need to balance the energy consumption of sensors so that there will not be too much redundant energy in some sensors before the WSN terminates. The detection probability and false alarm probability are taken into consideration to achieve a better performance and reveal the real sensing process which is characterised in the probabilistic sensing model. Data fusion is also introduced to utilise information of sensors so that a PoI in the monitored area may be covered by multiple sensors collaboratively, which will decrease the number of sensors that cover the monitored region. Based on the probabilistic model and data fusion, minimum weight probabilistic coverage problem is formulated in this paper. We also propose a greedy method and modified genetic algorithm based on the greedy method to address the problem. Simulation experiments are conducted to demonstrate the advantages of our proposed algorithms over existing work.     

Data Gathering with Tunable Compression in Sensor Networks

We study the problem of constructing a data gathering tree over a wireless sensor network in order to minimize the total energy for compressing and transporting information from a set of source nodes to the sink. This problem is crucial for advanced computationally intensive applications, where traditional "maximum" in-network compression may result in significant computation energy. We investigate a tunable data compression technique that enables effective trade-offs between the computation and communication costs. We derive the optimal compression strategy for a given data gathering tree and then investigate the performance of different tree structures for networks deployed on a grid topology, as well as general graphs. Our analytical results pertaining to the grid topology and simulation results pertaining to the general graphs indicate that the performance of a simple greedy approximation to the Minimal Steiner Tree (MST) provides a constant-factor approximation for the grid topology and good average performance on the general graphs. Although, theoretically, a more complicated randomized algorithm offers a polylogarithmic performance bound, the simple greedy approximation of MST is attractive for practical implementation.     

Promoting Heterogeneity, Mobility, and Energy-Aware Voronoi Diagram in Wireless Sensor Networks

We prove that the energy sink-hole problem can be solved provided that sensors adjust their communication ranges so they can send data over distances less than the radii of their nominal communication range. This solution, however, imposes a severe restriction on the size of a monitored field. To overcome this limitation, we propose a sensor deployment strategy based on energy heterogeneity with a goal that all sensors deplete their energy simultaneously. Our simulation results show that such a sensor deployment strategy helps all sensors deplete their initial energy at the same time. To solve the energy sink-hole problem for homogeneous WSNs, however, where all sensors have the same initial energy, we propose a localized energy-aware Voronoi diagram-based data forwarding (EVEN) protocol. EVEN combines sink mobility with a new concept, called energy-aware Voronoi diagram whose virtual sites (i.e., virtual sensors' locations) are computed based on the remaining energy of the corresponding sensors. Through simulations, we show that EVEN outperforms similar greedy geographical data forwarding protocols and has performance that is comparable to that of an existing data collection protocol that uses a joint mobility and routing strategy. Precisely, we find that EVEN yields an improvement of more than in terms of network lifetime.     

On the energy balance problem in distributed sensor networks

We investigate the problem of how to achieve energy balanced data propagation in distributed wireless sensor networks. The energy balance property guarantees that the average per sensor energy dissipation is the same for all sensors in the network, throughout the execution of the data propagation protocol. This property is crucial for prolonging the network lifetime, by avoiding early energy depletion of sensors.We survey representative solutions from the state of the art. We first present a basic algorithm that in each step probabilistically decides whether to propagate data one-hop towards the final destination (the sink), or to send it directly to the sink. This randomized choice trades-off the (cheap, but slow) one-hop transmissions with the direct transmissions to the sink, which are more expensive but bypass the bottleneck region around the sink and propagate data fast. By a detailed analysis using properties of stochastic processes and recurrence relations we precisely estimate (even in closed form) the probability for each propagation option necessary for energy balance.The fact (shown by our analysis) that direct (expensive) transmissions to the sink are needed only rarely, shows that our protocol, besides energy balanced, is also energy efficient. We then enhance this basic result by surveying some recent findings including a generalized algorithm and demonstrating the optimality of this two-way probabilistic data propagation, as well as providing formal proofs of the energy optimality of the energy balance property.     

Self-organized routing for wireless microsensor networks

In this paper, we develop an energy-aware self-organized routing algorithm for the networking of simple battery-powered wireless microsensors (as found, for example, in security or environmental monitoring applications). In these networks, the battery life of individual sensors is typically limited by the power required to transmit their data to a receiver or sink. Thus, effective network-routing algorithms allow us to reduce this power and extend both the lifetime and the coverage of the sensor network as a whole. However, implementing such routing algorithms with a centralized controller is undesirable due to the physical distribution of the sensors, their limited localization ability, and the dynamic nature of such networks (given that sensors may fail, move, or be added at any time and the communication links between sensors are subject to noise and interference). Against this background, we present a distributed mechanism that enables individual sensors to follow locally selfish strategies, which, in turn, result in the self-organization of a routing network with desirable global properties. We show that our mechanism performs close to the optimal solution (as computed by a centralized optimizer), it deals adaptively with changing sensor numbers and topology, and it extends the useful life of the network by a factor of three over the traditional approach.     

基于虚拟力的混合感知网节点部署

感知网一般是由静态的或移动的节点组成,为保证感知网的感知功能,节点应该有自部署和自修复能力.然而全部由移动传感器组成的感知网的成本太高,为保证感知网的覆盖功能和低成本,提出了一种在静态传感器节点中加入移动传感器节点的混合感知网形式.为了更好地部署这些节点,最大化覆盖待感知区域,提出了一种基于节点间虚拟力的移动节点部署方法,利用静态节点和移动节点以及移动节点之间的虚拟人工势场产生的作用力来控制移动节点的运动,使移动节点能够在较短的时间内,以较少的能量消耗到达自己合适的位置.在理论上分析了算法的可行性,用仿真实验验证了此算法的有效性,并和其他3种类似算法进行了性能比较.     

Energy-efficient topology control algorithm for maximizing network lifetime in wireless sensor networks with mobile sink

Uneven energy consumption is an inherent problem in wireless sensor networks characterized by multi-hop routing and many-to-one traffic pattern. Such unbalanced energy dissipation can significantly reduce network lifetime. In this paper, we study the problem of prolonging network lifetime in large-scale wireless sensor networks where a mobile sink gathers data periodically along the predefined path and each sensor node uploads its data to the mobile sink over a multi-hop communication path. By using greedy policy and dynamic programming, we propose a heuristic topology control algorithm with time complexity O(n(m + n log n)), where n and m are the number of nodes and edges in the network, respectively, and further discuss how to refine our algorithm to satisfy practical requirements such as distributed computing and transmission timeliness. Theoretical analysis and experimental results show that our algorithm is superior to several earlier algorithms for extending network lifetime.     

Sensor selection for parameterized random field estimation in wireless sensor networks

We consider the random field estimation problem with parametric trend in wireless sensor networks where the field can be described by unknown parameters to be estimated. Due to the limited resources, the network selects only a subset of the sensors to perform the estimation task with a desired performance under the D-optimal criterion. We propose a greedy sampling scheme to select the sensor nodes according to the information gain of the sensors. A distributed algorithm is also developed by consensus-based ...     

无线传感器网络一种不相交路径路由算法

无线传感器网络经常被用来采集物理数据,监测环境变化.由于低功耗无线通信不确定性、链路质量不稳定性以及节点失效等问题,传感器网络很容易导致路由数据包丢失.为了提高网络路由的可靠性,人们提出多路径路由算法.多路径路由中源节点到目的节点的多条路径可能含有公共节点,或者公共边,如果公共节点或者公共链路失效,则这个数据包也丢失,因此又有人提出不相交多路径路由算法.不相交多路径路由算法又分为链路不相交多路径路由算法和节点不相交多路径路由算法.提出了一种不相交路径路由算法,可以将感知节点采集到的数据通过不相交路径传送到汇聚节点,提高路由的可靠性.而且,这个算法还可以很方便地应用到多Sink节点的网络当中.该路由算法用到的路由表大小为|K|,其中|K|表示路径数.算法的运行时间复杂度是O(|L|),其中|L|表示网络中的边数.     

An Energy-Efficient Data Collection Framework for Wireless Sensor Networks by Exploiting Spatiotemporal Correlation

Limited energy supply is one of the major constraints in wireless sensor networks. A feasible strategy is to aggressively reduce the spatial sampling rate of sensors, that is, the density of the measure points in a field. By properly scheduling, we want to retain the high fidelity of data collection. In this paper, we propose a data collection method that is based on a careful analysis of the surveillance data reported by the sensors. By exploring the spatial correlation of sensing data, we dynamically partition the sensor nodes into clusters so that the sensors in the same cluster have similar surveillance time series. They can share the workload of data collection in the future since their future readings may likely be similar. Furthermore, during a short-time period, a sensor may report similar readings. Such a correlation in the data reported from the same sensor is called temporal correlation, which can be explored to further save energy. We develop a generic framework to address several important technical challenges, including how to partition the sensors into clusters, how to dynamically maintain the clusters in response to environmental changes, how to schedule the sensors in a cluster, how to explore temporal correlation, and how to restore the data in the sink with high fidelity. We conduct an extensive empirical study to test our method using both a real test bed system and a large-scale synthetic data set.     

Signal reconstruction in sensor networks with flat and clustered topologies

We apply signal processing techniques to the study of wireless sensor networks, whose nodes are deployed over a planar region for environmental monitoring. We address the problem of reconstructing the phenomenon of interest at a sink node, from the samples gathered by the sensors, and we evaluate the system performance in presence of both a flat and a clustered network topology. When the sensors are grouped into (possibly overlapping) clusters, the data collected within each cluster are compressed by the cluster head and sent to the sink node. By representing the compressed data through the Fourier coefficients of the field spectrum, we analyze both the case where the sensor positions are known to the sink, and the case where they are available at the cluster head only. We show that clustering significantly reduces the energy expenditure due to data transmission with respect to the case of a flat network topology, and, most importantly, we derive the possible degradation of the quality of the reconstructed field due to compression.