CROSS: A probabilistic constrained random sensor selection scheme in wireless sensor networks

Due to the application-specific nature of wireless sensor networks, the sensitivity to coverage and data reporting latency varies depending on the type of applications. In light of this, algorithms and protocols should be application-aware to achieve the optimum use of highly limited resources in sensors and hence to increase the overall network performance. This paper proposes a probabilistic constrained random sensor selection (CROSS) scheme for application-aware sensing coverage with a goal to maximize the network lifetime. The CROSS scheme randomly selects in each round (approximately) k data-reporting sensors which are sufficient for a user/application-specified desired sensing coverage (DSC) maintaining a minimum distance between any pair of the selected k sensors. We exploit the Poisson sampling technique to force the minimum distance. Consequently, the CROSS improves the spatial regularity of randomly selected k sensors and hence the fidelity of satisfying the DSC in each round, and the connectivity among the selected sensors increase. To this end, we also introduce an algorithm to compute the desired minimum distance to be forced between any pair of sensors. Finally, we present the probabilistic analytical model to measure the impact of the Poisson sampling technique on selecting k sensors, along with the optimality of the desired minimum distance computed by the proposed algorithm.     

Probabilistic filters: A stream protocol for continuous probabilistic queries

Pervasive applications, such as natural habitat monitoring and location-based services, have attracted plenty of research interest. These applications, which deploy a lot of sensor devices to collect data from external environments, often have limited network bandwidth and battery resources. The sensors also cannot record accurate values. The uncertainty of data captured by a sensor should thus be considered for query evaluation. To this end, probabilistic queries, which consider data impreciseness and provide statistical guarantees in answers, have been recently studied.     

Bandwidth-constrained queries in sensor networks

Sensor networks consist of battery-powered wireless devices that are required to operate unattended for long periods of time. Thus, reducing energy drain is of utmost importance when designing algorithms and applications for such networks. Aggregate queries are often used by monitoring applications to assess the status of the network and detect abnormal behavior. Since radio transmission often constitutes the biggest factor of energy drain in a node, in this paper we propose novel algorithms for the evaluation of bandwidth- constrained queries over sensor networks. The goal of our techniques is, given a target bandwidth utilization factor, to program the sensor nodes in a way that seeks to maximize the accuracy of the produced query results at the monitoring node, while always providing strong error guarantees to the monitoring application. This is a distinct difference of our framework from previous techniques that only provide probabilistic guarantees on the accuracy of the query result. Our algorithms are equally applicable when the nodes have ample power resources, but bandwidth consumption needs to be minimized, for instance in densely distributed networks, to ensure proper operation of the nodes. Our experiments with real sensor data show that bandwidth-constrained queries can substantially reduce the number of messages in the network while providing very tight error bounds on the query result.     

A note on efficient aggregate queries in sensor networks

We consider a scenario where nodes in a sensor network hold numeric items, and the task is to evaluate simple functions of the distributed data. In this note we present distributed protocols for computing the median with sublinear space and communication complexity per node. Specifically, we give a deterministic protocol for computing median with polylog complexity and a randomized protocol that computes an approximate median with polyloglog communication complexity per node. On the negative side, we observe that any deterministic protocol that counts the number of distinct data items must have linear complexity in the worst case.     

Energy-efficient filtering for skyline queries in cluster-based sensor networks

Filtering is a generic technique for skyline retrieval in sensor networks, for the purpose of reducing the communication cost, the dominant part of energy consumption. The vast majority of existing filtering approaches are suitable for uniform and correlated datasets, whereas in many applications the data distribution is clustered or anti-correlated. The only work considering anti-correlated dataset requires significant energy for filtering construction, and it is hard to be efficiently adapted to clustered databases. In this paper, we propose a new filtering algorithm, which settles the problem by utilizing individual node characteristics and generating personalized filters. Given a fraction k, a personalized filter prunes at least k percent of points on assigned nodes. A novel scheme for data cluster representation and a sampling method are then proposed to reduce the filtering cost and maximize the benefit of filtering. Extensive simulation results show the superiority of our approach over existing techniques.     

Direction-based vacancy queries in camera sensor networks

World Wide Web - In a camera sensor network, given a target q and a set of cameras ${mathcal P}$ , q may not be recognized by ${mathcal P}$ due to its facing direction even if every $p_{i} in...     

A probabilistic approach for predictive congestion control in wireless sensor networks

Any node in a wireless sensor network is a resource constrained device in terms of memory, bandwidth, and energy, which leads to a large number of packet drops, low throughput, and significant waste of energy due to retransmission. This paper presents a new approach for predicting congestion using a probabilistic method and controlling congestion using new rate control methods. The probabilistic approach used for prediction of the occurrence of congestion in a node is developed using data traffic and buffer occupancy. The rate control method uses a back-off selection scheme and also rate allocation schemes, namely rate regulation （RRG） and split protocol （SP）, to improve throughput and reduce packet drop. A back-off interval selection scheme is introduced in combination with rate reduction （RR） and RRG. The back-off interval selection scheme considers channel state and collision-flee transmission to prevent congestion. Simulations were conducted and the results were compared with those of decentralized predictive congestion control （DPCC） and adaptive duty-cycle based congestion control （ADCC）. The results showed that the proposed method reduces congestion and improves performance.     

Efficient processing of aggregation queries in sensor networks

Continuous aggregation queries with a tolerable error threshold have many applications in sensor networks. Since the communication cost is important in the lifetime of sensor networks, there have been a few methods to reduce the communication cost for continuous aggregation queries having a tolerable error threshold. In previous methods, the error threshold in each node is periodically adjusted based on the global statistics collected in the central site that are obtained from all the nodes in the network. These methods require that users specify a few parameters, e.g., adjustment period. However, determination of these parameters by users, in practice, is very difficult and undesirable for sensor network applications demanding unattended operations in dynamically changing environments. In this paper, we propose a new in-network data aggregation protocol, called the Distributed Adaptive Filtering (DAF) protocol. It works in a distributed manner and proceeds adaptively in the sense that the filtering condition in each node is adaptively changed by using only local information. It does not require user parameters that are used in the previous method. We show through various experiments that the proposed method outperforms other existing methods. Recommended by: Ahmed Elmagarmid     

A cache invalidation scheme for continuous partial match queries in mobile computing environments

The continuous partial match query is a partial match query whose result remains consistently in the client’s memory. Conventional cache invalidation methods for mobile clients are record ID-based. However, since the partial match query uses content-based retrieval, the conventional ID-based approaches cannot efficiently manage the cache consistency of mobile clients. In this paper, we propose a predicate-based cache invalidation scheme for continuous partial match queries in mobile computing environments. We represent the cache state of a mobile client as a predicate, and also construct a cache invalidation report (CIR), which the server broadcasts to clients for cache management, with predicates. In order to reduce the amount of information that is needed for cache management, we propose a set of methods for CIR construction (in the server) and identification of invalidated data (in the client). Through experiments, we show that the predicate-based approach is very effective for the cache management of mobile clients.     

Processing approximate aggregate queries in wireless sensor networks

In-network data aggregation has been recently proposed as an effective means to reduce the number of messages exchanged in wireless sensor networks. Nodes of the network form an aggregation tree, in which parent nodes aggregate the values received from their children and propagate the result to their own parents. However, this schema provides little flexibility for the end-user to control the operation of the nodes in a data sensitive manner. For large sensor networks with severe energy constraints, the reduction (in the number of messages exchanged) obtained through the aggregation tree might not be sufficient. In this paper, we present new algorithms for obtaining approximate aggregate statistics from large sensor networks. The user specifies the maximum error that he is willing to tolerate and, in turn, our algorithms program the nodes in a way that seeks to minimize the number of messages exchanged in the network, while always guaranteeing that the produced estimate lies within the specified error from the exact answer. A key ingredient to our framework is the notion of the residual mode of operation that is used to eliminate messages from sibling nodes when their cumulative change to the computed aggregate is small. We introduce two new algorithms, based on potential gains, which adaptively redistribute the error thresholds to those nodes that benefit the most and try to minimize the total number of transmitted messages in the network. Our techniques significantly reduce the number of messages, often by a factor of 10 for a modest 2% relative error bound, and consistently outperform previous techniques for computing approximate aggregates, which we have adapted for sensor networks.     

A hybrid scheme for energy-efficient object tracking in sensor networks

Energy saving is a critical issue in many sensor-network-based applications. Among the existing sensor-network-based applications, the surveillance application has attracted extensive attention. Object tracking in sensor networks (OTSNs) is a typical surveillance application. Previous studies on energy saving for OTSNs can be divided into two main approaches: (1) improvements in hardware design to lower the energy consumption of attached components and (2) improvements in software to predict the movement of objects. In this paper, we propose a novel scheme, namely hybrid tracking scheme (HTS), for tracking objects with energy efficiency. The scheme consists of the two parts: (1) adaptive schedule monitoring and (2) a recovery mechanism integrated with seamless temporal movement patterns and seeding-based flooding to relocate missing objects with the purpose of saving energy. Furthermore, we also propose a frequently visited periods mining algorithm, which discovers the corresponding frequently visited periods for adaptive schedule monitoring efficiently from the visitation information of sensor nodes. To decrease the number of sensor nodes activated in flooding, a seeding-based flooding mechanism is first proposed in our work. Empirical evaluations of various simulation conditions and real datasets show that the proposed HTS delivers excellent performance in terms of energy efficiency and low missing rates.     

A cross-layer transmission scheduling scheme for wireless sensor networks

In a wireless sensor network, the sensor nodes are densely deployed for detecting in many cases. One design challenge for such a network is how to devise a good data fusion algorithm for information retrieval. Noting that the channel state information (CSI) between the cluster head and the sensor nodes will influence the received bit energy noise ratio of the sensor nodes, we propose an optimal data fusion algorithm taking into account the CSI for a one-hop clustered wireless sensor network. On the basis of the fusion algorithm, we consider the redundancy of the sensor deployment and propose a cross-layer transmission scheduling scheme. By selecting proper set of sensor nodes to transmit their local information back in turn, the scheme can prolong the lifetime of the sensor network. The numerical and simulation results show that it can get a good tradeoff between the energy efficiency and the performance.     

Biologically inspired probabilistic coverage for mobile sensor networks

Coupling sensors in a sensor network with mobility mechanism can boost the performance of wireless sensor networks (WSNs). In this paper, we address the problem of self-deploying mobile sensors to reach high coverage. The problem is modeled as a multi-objective optimization that simultaneously minimizes two contradictory parameters; the total sensor moving distance and the total uncovered area. In order to resolve the aforementioned deployment problem, this study investigates the use of biologically inspired mechanisms, including evolutionary algorithms and swarm intelligence, with their state-of-the-art algorithms. Unlike most of the existing works, the coverage parameter is expressed as a probabilistic inference model due to uncertainty in sensor readings. To the best of our knowledge, probabilistic coverage of mobile sensor networks has not been addressed in the context of multi-objective bio-inspired algorithms. Performance evaluations on deployment quality and deployment cost are measured and analyzed through extensive simulations, showing the effectiveness of each algorithm under the developed objective functions. Simulations reveal that only one multi-objective evolutionary algorithm; the so-called multi-objective evolutionary algorithm with decomposition survives to effectively tackle the probabilistic coverage deployment problem. It gathers more than 78 % signals from all of the targets (and in some cases reaches 100 % certainty). On the other hand, non-dominated sorting genetic algorithm II, multi-objective particle swarm optimization, and non-dominated sorting particle swarm optimization show inferior performance down to 16–32 %, necessitating further modifications in their internal mechanisms.     

A top-down positioning scheme for underwater wireless sensor networks

In order to increase the localization coverage while keeping the localization error small in a unique network architecture in which there are not evenly distributed anchor nodes with great ability of communication or additional infrastructure,a Top-down Positioning Scheme(TPS)for underwater acoustic sensor networks is proposed.By defining node’s confidence reasonably,TPS insures the quality of the new reference nodes.TPS also refines the nodes which have just been positioned via the gradient method and helps non-localized nodes search for more reference nodes via the new scheme for 3D Euclidean distance estimation.By comparing the new scheme for 3D Euclidean distance estimation with the existing scheme,the new scheme is shown to have greater ability to estimate two-hop Euclidean distance in 3D space.Simulation results show that TPS which integrates node’s confidence defined reasonably,the gradient method,and the new scheme for 3D Euclidean distance estimation can increase the localization coverage ratio,while keeping the localization error small.     

A secure routing scheme for mobile wireless sensor networks

Frequency-hopping (FH) is a well-known spread-spectrum method of transmitting radio signals by hopping frequency channels along a predefined hopping sequence known to both transmitter and receiver. Although FH is resistant to jamming by external malicious nodes which have no knowledge of the sequence, it is of no effect against attacks by internal compromised nodes which know the sequence. In this article, we propose a secure scheme for creating the hopping sequence for mobile wireless sensor networks. The proposed scheme is based on the idea of a statistical en-route filtering (SEF). SEF exploits collective decision making by multiple detecting nodes in the dense deployment of large sensor networks. We demonstrate the effectiveness of our scheme thorough simulations.     

A probabilistic and opportunistic flooding algorithm in wireless sensor networks

In wireless sensor networks, many communication protocols and applications rely on flooding for various networking purposes. Prior efforts focus on how to design efficient flooding algorithms; that is, they seek to achieve full reliability while reducing the number of redundant broadcasting across the network. To achieve efficient flooding, most of the existing protocols try to reduce the number of transmissions, which is decided without considering any online transmission result. In this paper, we propose a probabilistic and opportunistic flooding algorithm that controls rebroadcasts and retransmissions opportunistically. It seeks to achieve a target reliability required by an application. For this purpose, it makes a given node select only the subset of its one-hop neighbors to rebroadcast the same message. It considers node relations such as link error rates among nodes in selecting eligible neighbors to rebroadcast. The sender controls the number of retransmissions opportunistically by tracking the current status of message reception at its neighbors. Simulation is carried out to reveal that our proposed scheme achieves the given target reliability with less overhead than other flooding algorithms in most cases, thus prolonging the network lifetime.     

An efficient mechanism for processing similarity search queries in sensor networks

The similarity search problem has received considerable attention in database research community. In sensor network applications, this problem is even more important due to the imprecision of the sensor hardware, and variation of environmental parameters. Traditional similarity search mechanisms are both improper and inefficient for these highly energy-constrained sensors. A difficulty is that it is hard to predict which sensor has the most similar (or closest) data item such that many or even all sensors need to send their data to the query node for further comparison. In this paper, we propose a similarity search algorithm (SSA), which is a novel framework based on the concept of Hilbert curve over a data-centric storage structure, for efficiently processing similarity search queries in sensor networks. SSA successfully avoids the need of collecting data from all sensors in the network in searching for the most similar data item. The performance study reveals that this mechanism is highly efficient and significantly outperforms previous approaches in processing similarity search queries.