Data ferries based compressive data gathering for wireless sensor networks

The latest research progress of the theory of compressive sensing (CS) over graphs makes it possible that the advantage of CS can be utilized by data ferries to gather data for wireless sensor networks. In this paper, we leverage the non-uniform distribution of the sensing data field to significantly reduce the required number of data ferries, yet ensuring the recovered data quality. Specially, we propose an intelligent compressive data gathering scheme consisting of an efficient stopping criterion and a novel learning strategy. The proposed stopping criterion is based only on the gathered data, without relying on the priori knowledge on the sparsity of unknown sensing data. Our learning strategy minimizes the number of data ferries while guaranteeing the data quality by learning the statistical distribution of the gathered data. Simulation results show that the proposed scheme improves the reconstruction accuracy and stability compared to the existing ones.

     

Energy equalizing routing for fast data gathering in wireless sensor networks

Energy saving and fast responding of data gathering are two crucial factors for the performance of wireless sensor networks. A dynamic tree based energy equalizing routing scheme (DTEER) was proposed to make an effort to gather data along with low energy consumption and low time delay. DTEER introduces a dynamic multi-hop route selecting scheme based on weight-value and height-value to form a dynamic tree and a mechanism similar to token passing to elect the root of the tree. DTEER can simply and rapidly organize all the nodes with low overhead and is robust enough to the topology changes. When compared with power-efficient gathering in sensor information systems (PEGASIS) and the hybrid, energy- efficient, distributed clustering approach (HEED), the simulation results show that DTEER achieves its intention of consuming less energy, equalizing the energy consumption of all the nodes, alleviating the data gathering delay, as well as extending the network lifetime perfectly.     

An incentive energy-efficient routing for data gathering in wireless cooperative networks

Because of energy-constraint, it is an attractive problem to select energy-efficient paths from source nodes to sink for data gathering in wireless ad hoc networks. Cooperative communication is a promising mechanism to reduce transmit energy in such kind of case. One of the fundamental assumptions for cooperative communication is that each node should be unselfish, responsible, and willing to forwarding data he has received. However, in energy-constrained environment, because of limited energy, each node hates participating in data transmission without any incentive and tries to avoid forwarding data (this behavior is selfish). In this paper, a utility function is proposed to stimulate nodes to behave unselfishly. We prove that it is a Nash Equilibrium when nodes work in an unselfish manner. Also, we show that the selection of forwarding nodes and relay nodes for data transmission is a NP-hard problem even when nodes behave unselfishly. A heuristic algorithm (Algorithm for Node Selection Problem, ANSP) is provided to solve this selection problem. We also prove the convergence of this algorithm. The analysis shows that this algorithm can reach the approximate performance ratio of 2?(1+α), where α is the maximal ratio of two power consumptions on two adjacent links in the network. The numerical results show that in a 100 node network, if nodes behave unselfishly, they will obtain a better utility, and more energy will be saved. The average saved energy when each node takes a selfish behavior, is 52.5% less than the average when nodes behave in an unselfish manner.     

IRIS: Integrated data gathering and interest dissemination system for wireless sensor networks

This paper presents IRIS, an integrated interest dissemination and convergecasting solution for wireless sensor networks (WSNs). The interest dissemination protocol is used to build and maintain the network topology and for task/instruction assignment, while convergecasting implements data gathering at the network sink. Convergecasting heavily exploits cross-layering in that MAC and routing operation are performed jointly and relay selection is based on flexible cost functions that take into account information from different layers. The definition of the IRIS cost function enables tradeoff between key end-to-end performance metrics. In addition, it provides mechanisms for supporting efficient network behavior such as in-network data aggregation or processing. Energy usage is minimized by exploiting density estimation, sleeping modes and duty cycle control in a distributed and autonomous manner and as a function of the traffic intensity. Finally, IRIS is self adaptive, highly localized and imposes limited control overhead. IRIS performance is evaluated through ns2 simulations as well as through experiments on a WSN testbed. Comparative performance results show that IRIS outperforms previous cross-layer solutions. The flexibility introduced by the IRIS cross-layer approach results in higher robustness than that of well-known approaches such as BoX-MAC and CTP.     

Accurate compressive data gathering in wireless sensor networks using weighted spatio-temporal compressive sensing

The high number of transmissions in sensor nodes having a limited amount of energy leads to a drastic decrease in the lifetime of wireless sensor networks. For dense sensor networks, the provided data potentially have spatial and temporal correlations. The correlations between the data of the nodes make it possible to utilize compressive sensing theory during the data gathering phase; however, applying this technique leads to some errors during the reconstruction phase. In this paper, a method based on weighted spatial-temporal compressive sensing is proposed to improve the accuracy of the reconstructed data. Simulation results confirm that the reconstruction error of the proposed method is approximately 16 times less than the closest compared method. It should be noted that due to applying weighted spatial-temporal compressive sensing, some extra transmissions are posed to the network. However, considering both lifetime and accuracy factors as a compound metric, the proposed method yields a 12% improvement compared to the closest method in the literature.     

Nature inspired discrete firefly algorithm for optimal mobile data gathering in wireless sensor networks

Nowadays wireless sensor networks enhance the life of human beings by helping them through several applications like precision agriculture, health monitoring, landslide detection, pollution control, etc. The built-in sensors on a sensor node are used to measure the various events like temperature, vibration, gas emission, etc., in the remotely deployed unmanned environment. The limited energy constraint of the sensor node causes a huge impact on the lifetime of the deployed network. The data transmitted by each sensor node cause significant energy consumption and it has to be efficiently used to improve the lifetime of the network. The energy consumption can be reduced significantly by incorporating mobility on a sink node. Thus the mobile data gathering can result in reduced energy consumption among all sensor nodes while transmitting their data. A special mobile sink node named as the mobile data transporter (MDT) is introduced in this paper to collect the information from the sensor nodes by visiting each of them and finally it sends them to the base station. The Data collection by the MDT is formulated as a discrete optimization problem which is termed as a data gathering tour problem. To reduce the distance traveled by the MDT during its tour, a nature-inspired heuristic discrete firefly algorithm is proposed in this paper to optimally collect the data from the sensor nodes. The proposed algorithm computes an optimal order to visit the sensor nodes by the MDT to collect their data with minimal travel distance. The proposed algorithm is compared with tree-based data collection approaches and ant colony optimization approach. The results demonstrate that the proposed algorithm outperform other approaches minimizing the tour length under different scenarios.     

EDGO: UAV-based effective data gathering scheme for wireless sensor networks with obstacles

Wireless Networks - One of the most important requirements for effective UAV–WSN operations is to perform data collection in timely and safe manner. Identifying an effective path in an...     

An exact algorithm for maximum lifetime data gathering tree without aggregation in wireless sensor networks

In wireless sensor networks, maximizing the lifetime of a data gathering tree without aggregation has been proved to be NP-complete. In this paper, we prove that, unless P = NP, no polynomial-time algorithm can approximate the problem with a factor strictly greater than 2/3. The result even holds in the special case where all sensors have the same initial energy. Existing works for the problem focus on approximation algorithms, but these algorithms only find sub-optimal spanning trees and none of them can guarantee to find an optimal tree. We propose the first non-trivial exact algorithm to find an optimal spanning tree. Due to the NP-hardness nature of the problem, this proposed algorithm runs in exponential time in the worst case, but the consumed time is much less than enumerating all spanning trees. This is done by several techniques for speeding up the search. Featured techniques include how to grow the initial spanning tree and how to divide the problem into subproblems. The algorithm can handle small networks and be used as a benchmark for evaluating approximation algorithms.

     

An image processing inspired mobile sink solution for energy efficient data gathering in wireless sensor networks

Wireless Networks - This paper presents a gradient-based multi-hop clustering protocol combined with a mobile sink (MS) solution for efficient data gathering in wireless sensor networks. The main...     

Optimal physical carrier sense in wireless networks

We investigate the problem of maximizing Medium Access Control (MAC) throughput in Carrier Sense Multiple Access (CSMA) wireless networks. By explicitly incorporating the carrier sense threshold and the transmit power into our analysis, we derive an analytical relation between MAC throughput and system parameters. In homogeneous networks, we derive the optimal carrier sense range at a given node density as a function of the ratio between the transmit power and the carrier sense threshold. The obtained optimal carrier sense range is smaller than that for covering the entire interference range, which is in sharp contrast to what has been considered to be optimal in previous studies. Only when the node density goes to infinity, the optimal carrier sense range converges to that for exactly covering the interference range, thereby eliminating all the hidden nodes. For nonhomogeneous networks, any distributed algorithm for tuning the carrier sense threshold, in which each node tries to maximize its own throughput without coordination, may significantly degrade MAC throughput. In order to properly design a distributed algorithm, each node not only considers its own throughput, but also needs to take account of its adverse impact on others. Our analysis is verified by simulation studies under various network scenarios.     

Quality-of-service mechanisms in all-IP wireless access networks

In this paper, we focus on resource reservation protocol (RSVP)-based quality-of-service (QoS) provisioning schemes under Internet protocol (IP) micromobility. We consider QoS provisioning mechanisms for on-going RSVP flows during handoff. First, the rerouting of RSVP branch path at a crossover router (CR) at every handoff event can minimize resource reservation delays and signaling overheads, and in turn the handoff service degradation can be minimized. We show that RSVP branch path rerouting scheme could give a good tradeoff between the resource reservation cost and the link usage. Second, the new RSVP reservation can be made along the branch path toward the CR via a new base station in advance, while the existing reservation path is maintained, and in turn the on-going flow can be kept with the guaranteed QoS. We also show that seamless switching of RSVP branch path could provide the QoS guarantee by adaptively adjusting the pilot signal threshold values. Third, during RSVP resource reservation over wireless link, dynamic resource allocation scheme is used to give a statistical guarantee on the handoff success of on-going flows. We finally obtain the forced termination probability of guaranteed service flows, the average system time of best effort flows by using a transition rate matrix approach.     

机会移动传感器网络中的自适应数据收集机制

针对多种类型数据具有不同传输质量需求的信息采集应用,提出了一种自适应的数据收集机制.每个节点关联一个持续变化的"转发概率"参数,每个消息关联一个动态调整的"重要因子"参数,这2个参数自适应确定消息在网络中的复制次数,使数据收集机制既能满足数据传输性能的要求,又具有小的网络开销.模拟实验结果验证了该收集机制在传输性能和网络开销之间达到很好折衷.     

Best and worst-case coverage problems for arbitrary paths in wireless sensor networks

The path-based coverage of a wireless sensor network is to analyze how well the network covers the sensor field in terms of paths. Known results prior to this research, however, considered only a single source–destination pair and thus do not provide a global outlook at the given network but a local feature for the given source–destination pair. In this paper, we propose a new coverage measure of sensor networks that considers arbitrary source–destination pairs. Our novel measure naturally extends the previous concept of the best and the worst-case path-based coverage to evaluate the coverage of a given network from a global point of view, taking arbitrary paths into account.In terms of the present coverage measure, we pose the evaluation and the deployment problems for give a network; the former is to evaluate the new coverage measure of a given sensor network, and the latter is to find an optimal placement of k additional sensor nodes to improve the coverage for a given positive integer k. We present several algorithms that are either centralized or localized that solve the problems with theoretical proofs and simulation results, thus showing that our algorithms are efficient and easy to implement in practice while the quality of their outputs is guaranteed by formal proofs. For the purpose, we show an interesting relation between the present coverage measure and a certain quantity of a point set, called the bottleneck, which has been relatively well studied in other disciplines such as computational geometry and operations research.     

Optimal base-station locations in two-tiered wireless sensor networks

We consider generic two-tiered wireless sensor networks (WSNs) consisting of sensor clusters deployed around strategic locations, and base-stations (BSs) whose locations are relatively flexible. Within a sensor cluster, there are many small sensor nodes (SNs) that capture, encode, and transmit relevant information from a designated area, and there is at least one application node (AN) that receives raw data from these SNs, creates a comprehensive local-view, and forwards the composite bit-stream toward a BS. This paper focuses on the topology control process for ANs and BSs, which constitute the upper tier of two-tiered WSNs. Since heterogeneous ANs are battery-powered and energy-constrained, their node lifetime directly affects the network lifetime of WSNs. By proposing algorithmic approaches to locate BSs optimally, we can maximize the topological network lifetime of WSNs deterministically, even when the initial energy provisioning for ANs is no longer always proportional to their average bit-stream rate. The obtained optimal BS locations are under different lifetime definitions according to the mission criticality of WSNs. By studying intrinsic properties of WSNs, we establish the upper and lower bounds of maximal topological lifetime, which enable a quick assessment of energy provisioning feasibility and topology control necessity. Numerical results are given to demonstrate the efficacy and optimality of the proposed topology control approaches designed for maximizing network lifetime of WSNs.     

Optimal network selection in heterogeneous wireless multimedia networks

The complementary characteristics of different wireless networks make it attractive to integrate a wide range of radio access technologies. Most of previous work on integrating heterogeneous wireless networks concentrates on network layer quality of service (QoS), such as blocking probability and utilization, as design criteria. However, from a user’s point of view, application layer QoS, such as multimedia distortion, is an important issue. In this paper, we propose an optimal distributed network selection scheme in heterogeneous wireless networks considering multimedia application layer QoS. Specifically, we formulate the integrated network as a restless bandit system. With this stochastic optimization formulation, the optimal network selection policy is indexable, meaning that the network with the lowest index should be selected. The proposed scheme can be applicable to both tight coupling and loose coupling scenarios in the integration of heterogeneous wireless networks. Simulation results are presented to illustrate the performance of the proposed scheme.     

Optimal information extraction in energy-limited wireless sensor networks

The current practice in wireless sensor networks (WSNs) is to develop functional system designs and protocols for information extraction using intuition and heuristics, and validate them through simulations and implementations. We address the need for a complementary formal methodology by developing nonlinear optimization models of static WSN that yield fundamental performance bounds and optimal designs. We present models both for maximizing the total information gathered subject to energy constraints (on sensing, transmission, and reception), and for minimizing the energy usage subject to information constraints. Other constraints in these models correspond to fairness and channel capacity (assuming noise but no interference). We also discuss extensions of these models that can handle data aggregation, interference, and even node mobility. We present results and illustrations from computational experiments using these models that show how the optimal solution varies as a function of the energy/information constraints, network size, fairness constraints, and reception power. We also compare the performance of some simple heuristics with respect to the optimal solutions.     

A localized algorithm for finding disjoint paths in wireless sensor networks

This letter presents a localized algorithm that finds multiple node-disjoint paths in wireless sensor networks. The algorithm needs only local topology knowledge and provides automatic path restoration. We describe the algorithm, give the proof of correctness, and evaluate its performance using simulation. We conclude that the proposed algorithm is more suitable for wireless sensor networks than the existing distributed algorithms     

Optimal deployment of large wireless sensor networks

A spatially distributed set of sources is creating data that must be delivered to a spatially distributed set of sinks. A network of wireless nodes is responsible for sensing the data at the sources, transporting them over a wireless channel, and delivering them to the sinks. The problem is to find the optimal placement of nodes, so that a minimum number of them is needed. The critical assumption is made that the network is massively dense, i.e., there are so many sources, sinks, and wireless nodes, that it does not make sense to discuss in terms of microscopic parameters, such as their individual placements, but rather in terms of macroscopic parameters, such as their spatial densities. Assuming a particular interference-limited, capacity-achieving physical layer, and specifying that nodes only need to transport the data (and not to sense them at the sources, or deliver them at the sinks once their location is reached), the optimal node placement induces a traffic flow that is identical to the electrostatic field created if the sources and sinks are replaced by a corresponding distribution of positive and negative charges. Assuming a general model for the physical layer, and specifying that nodes must not only transport the data, but also sense them at the sources and deliver them at the sinks, the optimal placement of nodes is given by a scalar nonlinear partial differential equation found by calculus of variations techniques. The proposed formulation and derived equations can help in the design of large wireless sensor networks that are deployed in the most efficient manner, not only avoiding the formation of bottlenecks, but also striking the optimal balance between reducing congestion and having the data packets follow short routes.