Energy-efficient skyline query optimization in wireless sensor networks

With the deployment of wireless sensor networks (WSNs) for environmental monitoring and event surveillance, WSNs can be treated as virtual databases to respond to user queries. It thus becomes more urgent that such databases are able to support complicated queries like skyline queries. Skyline query which is one of popular queries for multi-criteria decision making has received much attention in the past several years. In this paper we study skyline query optimization and maintenance in WSNs. Specifically, we first consider skyline query evaluation on a snapshot dataset, by devising two algorithms for finding skyline points progressively without examining the entire dataset. Two key strategies are adopted: One is to partition the dataset into several disjoint subsets and produce the skyline points in each subset progressively. Another is to employ a global filter that consists of some skyline points in the processed subsets to filter out unlikely skyline points from the rest of unexamined subsets. We then consider the query maintenance issue by proposing an algorithm for incremental maintenance of the skyline in a streaming dataset. A novel maintenance mechanism is proposed, which is able to identify which skyline points from past skylines to be the global filter and determine when the global filter is broadcast. We finally conduct extensive experiments by simulations to evaluate the performance of the proposed algorithms on both synthetic and real sensing datasets, and the experimental results demonstrate that the proposed algorithms significantly outperform existing algorithms in terms of network lifetime prolongation.     

Energy-efficient DSPs for wireless sensor networks

There are many new challenges to be faced in implementing signal processing algorithms and designing energy-efficient DSPs for microsensor networks. We study system partitioning of computation to improve the energy efficiency of a wireless sensor networking application. We explore system partitioning between the sensor cluster and the base station, employing computation-communication tradeoffs to reduce energy dissipation. Also we show that system partitioning of computation within the cluster can also improve the energy efficiency by using dynamic voltage scaling (DVS)     

基于高能效RSSI的WSN定位

传感器自我定位是无线传感器网络中许多和定位有关的技术之一。虽然定位的主要目的是提高定位精度,但是能量消耗对定位提出了新的挑战。文中在考虑估计误差的同时,研究了最优功率分配的参考节点在一定意义上的最小能量消耗。为了对一个参考节点和一个利用了接收信号强度指示器(RSSI)的未知节点之间的相对距离有一个更好的估计,把接收到的信标的平均能量作为一种新的决策度量。基于此得到一个作为精度参数的平方位置误差和一个提高定位性能的优化问题。仿真结果表明,通过优化传输功率的配置可以实现能耗的大幅减少。     

Energy-efficient optical acquisition schemes in wireless sensor networks

Energy-efficiency is an essential feature of wireless sensor networks (WSNs) where the longevity of autonomous sensor nodes is limited by their battery life and/or energy-harvesting capability. Base-station-initiated optical wireless communication with nodes equipped with a passive optical transmitter in the form of a corner cube retroreflector (CCR) provides sensor acquisition with no energy expenditure on the part of the sensor node itself and is therefore an attractive option for WSN. However, the return signal from an illuminated sensor node is a stochastic variable dependant on fabrication parameters, ambient conditions and receiver noise so that the sensor acquisition process is inherently error-prone. In this paper we propose an energy-aware, base station-initiated interrogation scheme based on exponentially increasing beam scan areas, that takes into consideration the error-prone trait of CCR-outfitted sensor nodes. We analyse the scheme performance subject to different values of signal variance and various cost functions. We extend the analysis to address the circumstance of a spatially-limited sensor-failure event, such as may be caused by deliberate tampering or by environmental factors. We show that agile beam-steering on the basis of accrued knowledge of contaminated sensor distributions promotes energy-conserving acquisition. The validity of a Poisson spatial distribution model for the sensor dispersion is discussed and the impact of this initial assumption on acquisition error is demonstrated.     

Location-centric storage and query in wireless sensor networks

Location-centric storage (LCS) is envisioned as a promising scheme for robust and user-friendly on-demand data storage in networking environments such as the roadway sensor networks [Xing K et al. J Parallel Distributed Comput 67:336–345, 2007; Xing K et al. in: IEEE wireless communication and networking conference (WCNC), 2005]. In this paper, we analyze the performance of LCS in terms of storage and query overheads. This study indicates that LCS utilizes network resource efficiently and achieves good scalability. In particular, the storage overhead of sensors is independent of the network size, and is evenly distributed across the network. We also propose two algorithms for data retrieval in LCS-enabled one-dimensional and two-dimensional sensor networks. Our algorithms guarantee that acquiring the stored data of any event only takes a small number of communication hops to query a small number of sensors.     

Energy-efficient node deployment strategy for wireless sensor networks

To balancing energy consumption in wireless sensor networks, we proposed a fixed time interval node broadcasting scheme under variational acceleration straight-line movement model. Simulation results show that the approach proposed in this paper has a superior performance on energy consumption balance compared to uniform broadcasting methods.     

Energy-efficient routing for correlated data in wireless sensor networks

In this paper, we investigate the reduction in the total energy consumption of wireless sensor networks using multi-hop data aggregation by constructing energy-efficient data aggregation trees. We propose an adaptive and distributed routing algorithm for correlated data gathering and exploit the data correlation between nodes using a game theoretic framework. Routes are chosen to minimize the total energy expended by the network using best response dynamics to local data. The cost function that is used for the proposed routing algorithm takes into account energy, interference and in-network data aggregation. The iterative algorithm is shown to converge in a finite number of steps. Simulations results show that multi-hop data aggregation can significantly reduce the total energy consumption in the network.     

Energy-efficient and fault-tolerant drone-BS placement in heterogeneous wireless sensor networks

Wireless Networks - This paper introduces a distributed and energy-aware algorithm, called Minimum Drone Placement (MDP) algorithm, to determine the minimum number of base stations mounted on...     

WSN中能量有效分簇多跳路由算法

针对现有无线传感器网络(WSN)分簇路由算法存在的能耗不均衡问题,提出一种能量有效分簇多跳路由算法,该算法包括两个方面:一是选举簇首时引入簇内平均剩余能量因子,根据上一轮结束后簇内各节点剩余能量和簇内节点的平均剩余能量的比值更新簇首在所有节点中所占的百分比;二是要求簇首根据MTE多跳路由协议与基站通信,从而均衡WSN整...     

Energy-efficient neighbor discovery protocol for mobile wireless sensor networks

Low energy consumption is a critical design requirement for most wireless sensor network (WSN) applications. Due to minimal transmission power levels, time-varying environmental factors and mobility of nodes, network neighborhood changes frequently. In these conditions, the most critical issue for energy is to minimize the transactions and time consumed for neighbor discovery operations. In this paper, we present an energy-efficient neighbor discovery protocol targeted at synchronized low duty-cycle medium access control (MAC) schemes such as IEEE 802.15.4 and S-MAC. The protocol effectively reduces the need for costly network scans by proactively distributing node schedule information in MAC protocol beacons and by using this information for establishing new communication links. Energy consumption is further reduced by optimizing the beacon transmission rate. The protocol is validated by performance analysis and experimental measurements with physical WSN prototypes. Experimental results show that the protocol can reduce node energy consumption up to 80% at 1–3 m/s node mobility.     

Energy-efficient event pattern recognition in wireless sensor networks using multilayer spiking neural networks

Wireless Networks - Motivated by the energy-efficient computation of the brain, an energy-efficient wireless sensor network infrastructure is built for solving the pattern recognition task. In this...     

Energy-efficient relaying in wireless networks

It has been shown that there is a certain distance beyond which multi-hop data transmission is more energy-efficient than direct transmission in wireless networks. In this letter we investigate the effects of noise level on the minimal energy-efficient relay distance. We find that under optimal conditions (i.e., optimal packet length and transmit power level) there is an inverse power-law relation between the noise level and the minimal energy-efficient relay distance.     

Connectivity maintenance and coverage preservation in wireless sensor networks

In wireless sensor networks, one of the main design challenges is to save severely constrained energy resources and obtain long system lifetime. Low cost of sensors enables us to randomly deploy a large number of sensor nodes. Thus, a potential approach to solve lifetime problem arises. That is to let sensors work alternatively by identifying redundant nodes in high-density networks and assigning them an off-duty operation mode that has lower energy consumption than the normal on-duty mode. In a single wireless sensor network, sensors are performing two operations: sensing and communication. Therefore, there might exist two kinds of redundancy in the network. Most of the previous work addressed only one kind of redundancy: sensing or communication alone. Wang et al. [Intergrated Coverage and Connectivity Configuration in Wireless Sensor Networks, in: Proceedings of the First ACM Conference on Embedded Networked Sensor Systems (SenSys 2003), Los Angeles, November 2003] and Zhang and Hou [Maintaining Sensing Coverage and Connectivity in Large Sensor Networks. Technical report UIUCDCS-R-2003-2351, June 2003] first discussed how to combine consideration of coverage and connectivity maintenance in a single activity scheduling. They provided a sufficient condition for safe scheduling integration in those fully covered networks. However, random node deployment often makes initial sensing holes inside the deployed area inevitable even in an extremely high-density network. Therefore, in this paper, we enhance their work to support general wireless sensor networks by proving another conclusion: “the communication range is twice of the sensing range” is the sufficient condition and the tight lower bound to ensure that complete coverage preservation implies connectivity among active nodes if the original network topology (consisting of all the deployed nodes) is connected. Also, we extend the result to k-degree network connectivity and k-degree coverage preservation.     

Energy-efficient detection in sensor networks

There is significant interest in battery-powered sensor networks to be used for detection in a wide variety of applications, from surveillance and security to health and environmental monitoring. Severe energy and bandwidth constraints at each sensor node demand system-level approaches to design that consider detection performance jointly with system-resource constraints. Our approach is to formulate detection problems with constraints on the expected cost arising from transmission (sensor nodes to a fusion node) and measurement (at each sensor node) to address some of the system-level costs in a sensor network. For a given resource constraint, we find that randomization over the choice of measurement and over the choice of when to transmit achieves the best performance (in a Bayesian, Neyman-Pearson, and Ali-Silvey sense). To facilitate design, we describe performance criteria in the send/no-send transmission scenario, where the joint optimization over the sensor nodes decouples into optimization at each sensor node.     

Energy-efficient cluster-based cooperative FEC in wireless networks

In this article, we introduce a novel link layer cooperation technique in noisy wireless networks to improve overall system throughput and reliability, and to reduce the cost of retransmission and energy consumption. Under a cluster-based network design, Chase combining (Chase, IEEE Transactions on Communications 33(5):385–393, 1985) is used together with FEC to improve the link layer reliability. This approach is different from how combining is used in the conventional hybrid ARQ, which is in a sequential way. The analytical results and the simulations show that with the cooperation of nodes in a clustering network, the link reliability will be greatly improved with the same power consumption. We also show that not only transmission power is greatly reduced, but also the aggregate power consumption for a successful transmission and reception.     

Energy-efficient collaborative target tracking algorithm using cost-reference particle filtering in wireless acoustic sensor networks

Target tracking is one of the most important applications of wireless sensor networks. Optimized computation and energy dissipation are critical requirements to save the limited resource of sensor nodes. A new robust and energy-efficient collaborative target tracking framework is proposed in this article. After a target is detected, only one active cluster is responsible for the tracking task at each time step. The tracking algorithm is distributed by passing the sensing and computation operations from one cluster to another. An event-driven cluster reforming scheme is also proposed for balancing energy consumption among nodes. Observations from three cluster members are chosen and a new class of particle filter termed cost-reference particle filter (CRPF) is introduced to estimate the target motion at the cluster head. This CRPF method is quite robust for wireless sensor network tracking applications because it drops the strong assumptions of knowing the probability distributions of the system process and observation noises. In simulation experiments, the performance of the proposed collaborative target tracking algorithm is evaluated by the metrics of tracking precision and network energy consumption.     

Active query forwarding in sensor networks

While sensor networks are going to be deployed in diverse application specific contexts, one unifying view is to treat them essentially as distributed databases. The simplest mechanism to obtain information from this kind of a database is to flood queries for named data within the network and obtain the relevant responses from sources. However, if the queries are (a) complex, (b) one-shot, and (c) for replicated data, this simple approach can be highly inefficient. In the context of energy-starved sensor networks, alternative strategies need to be examined for such queries.We propose a novel and efficient mechanism for obtaining information in sensor networks which we refer to as ACtive QUery forwarding In sensoR nEtworks (ACQUIRE). The basic principle behind ACQUIRE is to consider the query as an active entity that is forwarded through the network (either randomly or in some directed manner) in search of the solution. ACQUIRE also incorporates a look-ahead parameter d in the following manner: intermediate nodes that handle the active query use information from all nodes within d hops in order to partially resolve the query. When the active query is fully resolved, a completed response is sent directly back to the querying node.We take a mathematical modelling approach in this paper to calculate the energy costs associated with ACQUIRE. The models permit us to characterize analytically the impact of critical parameters, and compare the performance of ACQUIRE with respect to other schemes such as flooding-based querying (FBQ) and expanding ring search (ERS), in terms of energy usage, response latency and storage requirements. We show that with optimal parameter settings, depending on the update frequency, ACQUIRE obtains order of magnitude reduction over FBQ and potentially over 60–75% reduction over ERS (in highly dynamic environments and high query rates) in consumed energy. We show that these energy savings are provided in trade for increased response latency. The mathematical analysis is validated through extensive simulations.     

Query similarity index based query preprocessing mechanism for multiapplication sharing wireless sensor networks

In multiapplication sharing wireless sensor networks, various application queries exhibit similarity in their spatial, temporal, and sensing attribute requirements, thus result in redundant sensing tasks. The dissemination and execution of such redundant sensing tasks cause network traffic overhead and quick energy drop of the sensor nodes. Existing task scheduling and allocation mechanisms focus on reducing upstream traffic by maximizing data sharing among sensing tasks. However, downstream traffic due to sensing tasks dissemination plays a crucial role in large-scale WSNs and required to be addressed. This paper proposes a query similarity index based query preprocessing mechanism that prevents the generation of redundant sensing tasks by creating a common query corresponding to the overlapping functional requirements of the queries and reduces the downstream as well as upstream traffic significantly. The performance evaluation reveals approximately 60% reduction in downstream traffic, 20–40% reduction in upstream traffic, and 40% reduction in energy consumption when compared with state-of-the-art mechanisms.

     

Relay sensor placement in wireless sensor networks

This paper addresses the following relay sensor placement problem: given the set of duty sensors in the plane and the upper bound of the transmission range, compute the minimum number of relay sensors such that the induced topology by all sensors is globally connected. This problem is motivated by practically considering the tradeoff among performance, lifetime, and cost when designing sensor networks. In our study, this problem is modelled by a NP-hard network optimization problem named Steiner Minimum Tree with Minimum number of Steiner Points and bounded edge length (SMT-MSP). In this paper, we propose two approximate algorithms, and conduct detailed performance analysis. The first algorithm has a performance ratio of 3 and the second has a performance ratio of 2.5. Xiuzhen Cheng is an Assistant Professor in the Department of Computer Science at the George Washington University. She received her MS and PhD degrees in Computer Science from the University of Minnesota - Twin Cities in 2000 and 2002, respectively. Her current research interests include Wireless and Mobile Computing, Sensor Networks, Wireless Security, Statistical Pattern Recognition, Approximation Algorithm Design and Analysis, and Computational Medicine. She is an editor for the International Journal on Ad Hoc and Ubiquitous Computing and the International Journal of Sensor Networks. Dr. Cheng is a member of IEEE and ACM. She received the National Science Foundation CAREER Award in 2004. Ding-Zhu Du received his M.S. degree in 1982 from Institute of Applied Mathematics, Chinese Academy of Sciences, and his Ph.D. degree in 1985 from the University of California at Santa Barbara. He worked at Mathematical Sciences Research Institutea, Berkeley in 1985-86, at MIT in 1986-87, and at Princeton University in 1990-91. He was an associate-professor/professor at Department of Computer Science and Engineering, University of Minnesota in 1991-2005, a professor at City University of Hong Kong in 1998-1999, a research professor at Institute of Applied Mathematics, Chinese Academy of Sciences in 1987-2002, and a Program Director at National Science Foundation of USA in 2002-2005. Currently, he is a professor at Department of Computer Science, University of Texas at Dallas and the Dean of Science at Xi’an Jiaotong University. His research interests include design and analysis of algorithms for combinatorial optimization problems in communication networks and bioinformatics. He has published more than 140 journal papers and 10 written books. He is the editor-in-chief of Journal of Combinatorial Optimization and book series on Network Theory and Applications. He is also in editorial boards of more than 15 journals. Lusheng Wang received his PhD degree from McMaster University in 1995. He is an associate professor at City University of Hong Kong. His research interests include networks, algorithms and Bioinformatics. He is a member of IEEE and IEEE Computer Society. Baogang Xu received his PhD degree from Shandong University in 1997. He is a professor at Nanjing Normal University. His research interests include graph theory and algorithms on graphs.