Reliable spatial window aggregation query processing algorithm in wireless sensor networks

After wireless sensor network is deployed, users often submit spatial window aggregation queries to obtain statistical information of the regions of interest, such as maximum temperature, average humidity etc. Existing spatial window aggregation query processing algorithms are based on the assumption that the communication links are ideal which means there are perfect communication links within a given communication range, and none beyond. However, it is not valid in realistic sensor networks, which leads to high retransmissions of data frames. In order to address this problem, a reliable spatial window aggregation query processing algorithm called RESA is proposed in this paper. RESA only requires each node to maintain locations and residual energy of its neighbors and link qualities between them. According to the information, it divides the query area into several sub-regions, followed by collection of sensor readings in each sub-region. RESA traverses all the sub-regions within the query area to ensure the correctness of query result. Based on RESA's energy consumption formula derived, two highly efficient methods for sub-regional division are proposed to reduce packet loss rate during data communication and balance the load of nodes, hence saving energy consumption and extending lifetime. Experimental results show that in most cases RESA outperforms the existing algorithms in terms of energy consumption, quality of query results and lifetime.     

Opportunistic sampling-based query processing in wireless sensor networks

High resolution sampling of physical phenomenon is a prime application of large scale wireless sensor networks (WSNs). With hundreds of nodes deployed over vast tracts of land, monitoring data can now be generated at unprecedented spatio-temporal scales. However, the limited battery life of individual nodes in the network mandates smart ways of collecting this data by maximizing localized processing of information at the node level. In this paper, we propose a WSN query processing method that enhances localized information processing by harnessing the two inherent aspects of WSN communication, i.e., multihop and multipath data transmission. In an active WSN where data collection queries are regularly processed, multihop and multipath routing leads to a situation where a significant proportion of nodes relay and overhear data generated by other nodes in the network. We propose that nodes opportunistically sample this data as they communicate. We model the data communication process in a WSN and show that opportunistic sampling during data communication leads to surprisingly accurate global knowledge at each node. We present an opportunistic query processing system that uses the accumulated global knowledge to limit the data collection requirements for future queries while ensuring temporal freshness of the results.     

Efficient skyline query processing in wireless sensor networks

How to process a skyline query efficiently has received considerable attention in recent years. A skyline query identifies a set of non-dominated data records in a multidimensional dataset. Whereas most previous studies have resolved this problem in a centralized environment, this work considers it in a distributed sensor network environment. An algorithm, known as Skyline Sensor Algorithm (SkySensor), is presented to efficiently retrieve skyline results from a sensor network. A cluster-based architecture is designed in SkySensor to collect all sensor readings. A pruning method is then proposed to progressively sift out the skyline results from the sensor network. SkySensor avoids the need of collecting data from all sensors in the network, which is an extremely expensive action, when searching for the skyline results. The performance study indicates that SkySensor is highly efficient, and significantly outperforms previous methods in processing skyline queries.     

Energy and quality aware query processing in wireless sensor database systems

Query processing has been studied extensively in traditional database systems. However, few existing methods can be directly applied to wireless sensor database systems (WSDSs) due to their characteristics, such as decentralized nature, limited computational power, imperfect information recorded, and energy scarcity in individual sensor nodes. This paper proposes a quality-guaranteed and energy-efficient (QGEE) algorithm. QGEE utilizes in-network query processing method to task WSDSs through declarative queries, and confidence interval strategy to determine the accuracy of query answers. In QGEE, the correlation between a query and a node is calculated by vector space model (VSM), and a query correlation indicator (QCI) is designed to quantify the priority of becoming active for individual nodes. Given a query, the QGEE algorithm will adaptively form an optimal query plan in terms of energy efficiency and quality awareness. This approach can reduce disturbance from measurements with extreme error and minimize energy consumption, while providing satisfying service for various applications. Simulation results demonstrate that QGEE can reduce resource usage by about 50% and frame loss rate by about 20%. Moreover, the confidence of query answers is always higher than, or equal to, the users’ pre-specified precision.     

无线传感器网络数据环区域查询处理算法

针对无线传感器网络节点能量高效问题以及Skyline查询位置属性决策问题,提出了基于无线传感器网络数据环区域查询处理算法。该算法以查询位置P为中心进行数据环划分,查询位置P最近的K个Skyline值时,根据剪枝策略只需对距离小于P的其它属性值进行比较,从而缩小了数据规模,提高了查询效率。另外,环内节点采用链簇式结构组织,环内查询处理过程采用串行数据处理与并行数据处理模式,从而提高了K-Skyline的数据查询能耗与节点处理延迟。仿真实验表明,数据环区域查询处理算法比Flooding算法与TAG算法具有更小的数据处理能耗和延迟。     

无线传感器网络中数据查询处理算法研究

提出一种改进的定向扩散路由,将传感器网络分簇,查询兴趣由sink节点发,只在各簇头节点扩散,簇头以广播的方式在簇内发散兴趣消息,簇成员将感知数据传送到簇头节点,簇头负责将收到的数据进行融合后传到sink节点。仿真结果表明,改进后的查询路由比典型的查询路由定向扩散具有更高的能量有效性和更低的时延,能较好地延长网络的生命周期,提高了传感器网络数据查询处理效率。     

An adaptive in-network aggregation operator for query processing in wireless sensor networks

A wireless sensor network (WSN) is composed of tens or hundreds of spatially distributed autonomous nodes, called sensors. Sensors are devices used to collect data from the environment related to the detection or measurement of physical phenomena. In fact, a WSN consists of groups of sensors where each group is responsible for providing information about one or more physical phenomena (e.g., group for collecting temperature data). Sensors are limited in power, computational capacity, and memory. Therefore, a query engine and query operators for processing queries in WSNs should be able to handle resource limitations such as memory and battery life. Adaptability has been explored as an alternative approach when dealing with these conditions. Adaptive query operators (algorithms) can adjust their behavior in response to specific events that take place during data processing. In this paper, we propose an adaptive in-network aggregation operator for query processing in sensor nodes of a WSN, called ADAGA (ADaptive AGgregation Algorithm for sensor networks). The ADAGA adapts its behavior according to memory and energy usage by dynamically adjusting data-collection and data-sending time intervals. ADAGA can correctly aggregate data in WSNs with packet replication. Moreover, ADAGA is able to predict non-performed detection values by analyzing collected values. Thus, ADAGA is able to produce results as close as possible to real results (obtained when no resource constraint is faced). The results obtained through experiments prove the efficiency of ADAGA.     

On query processing in wireless sensor networks using classes of quality of queries

This paper introduces the concept of quality of queries (QoQs) towards a more adaptive query processing in wireless sensor networks (WSNs). This approach aims at the intelligent consumption of the limited resources (energy and memory) available in these networks while still delivering a reasonable level of data quality as expected by client applications. In a nutshell, the concept of QoQ stipulates that the results of different queries injected into the same WSN can be tailored according to different criteria, in particular the levels of query result accuracy and energy consumption. For this purpose, four classes of QoQ (CoQoQ) are specified having in mind distinct requirements in terms of these criteria. To allow the implementation of these classes in a real WSN setting, a new novelty-detection based algorithm, referred to as AdaQuali (which stands for “ADAptive QUALIty control for query processing in WSN”), is also proposed in a manner as to control the sensor node activities through the dynamic adjustment of their rates of data collection and transmission. In order to validate the novel approach, simulations with a prototype implemented in Sinalgo have been conducted over real temperature data. The results achieved evidence the suitability of the proposal and point to gains of up to 66.76%, for different CoQoQ, in terms of reduction in energy consumption.     

Distributed query processing in flash-based sensor networks

Wireless sensor networks are used in a large array of applications to capture, collect, and analyze physical environmental data. Many existing sensor systems instruct sensor nodes to report their measurements to central repositories outside the network, which is expensive in energy cost. Recent technological advances in flash memory have given rise to the development of storagecentric sensor networks, where sensor nodes are equipped with high-capacity flash memory storage such that sensor data can be stored and managed inside the network to reduce expensive communication. This novel architecture calls for new data management techniques to fully exploit distributed in-network data storage. This paper describes some of our research on distributed query processing in such flash-based sensor networks. Of particular interests are the issues that arise in the design of storage management and indexing structures combining sensor system workload and read/write/erase characteristics of flash memory.     

Distributed query processing in flash-based sensor networks

Wireless sensor networks are used in a large array of applications to capture, collect, and analyze physical environmental data. Many existing sensor systems instruct sensor nodes to report their measurements to central repositories outside the network, which is expensive in energy cost. Recent technological advances in flash memory have given rise to the development of storage-centric sensor networks, where sensor nodes are equipped with high-capacity flash memory storage such that sensor data can be stored and managed inside the network to reduce expensive communication. This novel architecture calls for new data management techniques to fully exploit distributed in-network data storage. This paper describes some of our research on distributed query processing in such flash-based sensor networks. Of particular interests are the issues that arise in the design of storage management and indexing structures combining sensor system workload and read/write/erase characteristics of flash memory.     

Accident aware localization mechanism for wireless sensor networks

Accurate location information is important for event reporting, coverage estimation, and location-aware routing in a Wireless Sensor Network (WSN). Recently, a number of range-free localization schemes have been proposed to provide each static sensor with location information, which is represented by a rectangular region. However, most WSN applications are applied in outdoor environments where the sensors’ location regions could be incorrect due to sudden accidents. This paper proposes an Active Location Correction Protocol, called ALCP, for detecting and correcting the occurrence of location error based on the bounding box technology. Performance study reveals that applying the ALCP to improve the location accuracies can enhance the performance of the well-known GPSR routing in terms of routing length, sensing coverage, and packet arrival rate.     

Instance optimal query processing in spatial networks

The performance optimization of query processing in spatial networks focuses on minimizing network data accesses and the cost of network distance calculations. This paper proposes algorithms for network k-NN queries, range queries, closest-pair queries and multi-source skyline queries based on a novel processing framework, namely, incremental lower bound constraint. By giving high processing priority to the query associated data points and utilizing the incremental nature of the lower bound, the performance of our algorithms is better optimized in contrast to the corresponding algorithms based on known framework incremental Euclidean restriction and incremental network expansion. More importantly, the proposed algorithms are proven to be instance optimal among classes of algorithms. Through experiments on real road network datasets, the superiority of the proposed algorithms is demonstrated.     

Optimized query routing trees for wireless sensor networks

In order to process continuous queries over Wireless Sensor Networks (WSNs), sensors are typically organized in a Query Routing Tree (denoted as T) that provides each sensor with a path over which query results can be transmitted to the querying node. We found that current methods deployed in predominant data acquisition systems construct T in a sub-optimal manner which leads to significant waste of energy. In particular, since T is constructed in an ad hoc manner there is no guarantee that a given query workload will be distributed equally among all sensors. That leads to data collisions which represent a major source of energy waste. Additionally, current methods only provide a topological-based method, rather than a query-based method, to define the interval during which a sensing device should enable its transceiver in order to collect the query results from its children. We found that this imposes an order of magnitude increase in energy consumption.     

无线传感器网络Top-k多查询算法

针对无线传感器网络中多个Top-k查询问题,提出了一种Top-k多查询处理的算法,对接收到的多个Top-k查询请求进行预处理,预处理依据是约束条件,得出两类不同的查询集合:单约束条件的多查询和多约束条件的多查询。针对单约束条件的多查询提出了ETOP算法,该算法首先对排在时间序列最前面的Top-k查询请求进行基于网内处理,然后把查询结果存入基站缓存,并把结果的最小值设定为阈值传输到各个节点,再根据后续查询请求的查询范围进行相应的查询,从而快速地获得Top-k查询结果。实验表明:Top-k多查询方法在能够很好地实现查询的同时,减少了无线传感器网络中的传输消耗和能量消耗。     

无线传感器网络空间查询算法 IWQE 优化研究

针对当前流行的窗口路线查询处理 IWQE 算法,若查询路线上节点选择不当(节点剩余能耗过低或节点相距偏远)而导致通信传输中断、查询结果丢失的问题,提出了相应的优化算法 EIWQE。算法以剩余能耗为节点选择基础,采用基于位置的路由协议 GPSR 构建多边形,通过增加中继节点保证查询路线的连通性,并根据最大剩余能耗选择邻居节点分担信息收集与处理任务,以进一步降低查询路线上节点的能耗。给出了 EIWQE的详细实现流程,并在 OMNET ＋＋平台上用仿真方法从查询成功率、查询遍及率、节点能耗的均匀度等方面验证了 EIWQE 算法的优越性。     

Sensor-centric energy-constrained reliable query routing for wireless sensor networks

Standard wireless sensor network models emphasize energy efficiency and distributed decision-making by considering untethered and unattended sensors. To this we add two constraints—the possibility of sensor failure and the fact that each sensor must tradeoff its own resource consumption with overall network objectives. In this paper, we develop an analytical model of energy-constrained, reliable, data-centric information routing in sensor networks under all the above constraints. Unlike existing techniques, we use game theory to model intelligent sensors thereby making our approach sensor-centric. Sensors behave as rational players in an N-player routing game, where they tradeoff individual communication and other costs with network wide benefits. The outcome of the sensor behavior is a sequence of communication link establishments, resulting in routing paths from reporting to querying sensors. We show that the optimal routing architecture is the Nash equilibrium of the N-player routing game and that computing the optimal paths (which maximizes payoffs of the individual sensors) is NP-Hard with and without data-aggregation. We develop a game-theoretic metric called path weakness to measure the qualitative performance of different routing mechanisms. This sensor-centric concept which is based on the contribution of individual sensors to the overall routing objective is used to define the quality of routing (QoR) paths. Analytical results on computing paths of bounded weakness are derived and game-theoretic heuristics for finding approximately optimal paths are presented. Simulation results are used to compare the QoR of different routing paths derived using various energy-constrained routing algorithms.     

SNEE: a query processor for wireless sensor networks

A wireless sensor network (WSN) can be construed as an intelligent, large-scale device for observing and measuring properties of the physical world. In recent years, the database research community has championed the view that if we construe a WSN as a database (i.e., if a significant aspect of its intelligent behavior is that it can execute declaratively-expressed queries), then one can achieve a significant reduction in the cost of engineering the software that implements a data collection program for the WSN while still achieving, through query optimization, very favorable cost:benefit ratios. This paper describes a query processing framework for WSNs that meets many desiderata associated with the view of WSN as databases. The framework is presented in the form of compiler/optimizer, called SNEE, for a continuous declarative query language over sensed data streams, called SNEEql. SNEEql can be shown to meet the expressiveness requirements of a large class of applications. SNEE can be shown to generate effective and efficient query evaluation plans. More specifically, the paper describes the following contributions: (1) a user-level syntax and physical algebra for SNEEql, an expressive continuous query language over WSNs; (2) example concrete algorithms for physical algebraic operators defined in such a way that the task of deriving memory, time and energy analytical cost-estimation models (CEMs) for them becomes straightforward by reduction to a structural traversal of the pseudocode; (3) CEMs for the concrete algorithms alluded to; (4) an architecture for the optimization of SNEEql queries, called SNEE, building on well-established distributed query processing components where possible, but making enhancements or refinements where necessary to accommodate the WSN context; (5) algorithms that instantiate the components in the SNEE architecture, thereby supporting integrated query planning that includes routing, placement and timing; and (6) an empirical performance evaluation of the resulting framework.     

大规模无线传感器网络查询方法——CBQM*

提出一种适用于大规模、高查询率而单次查询需要传输的数据量很小、位置信息无关的无线传感器网络查询方法——CBQM。该方法以小世界理论为依据,在CARD和TRANSFER协议的基础上,引入了方向边节点,改进了contact的选择方法,降低了协议的能耗,提高了网络生命周期。通过仿真得出,在保证查询成功率的前提下,CBQM的查询最优能耗与CARD相比降低了约38%,比TRANSFER降低了40%以上。