EQOWSN: Evolutionary-based query optimization over self-organized wireless sensor networks

In this paper, a new approach has been introduced that integrates an evolutionary-based mechanism with a distributed query sensor cover algorithm for optimal query execution in self-organized wireless sensor networks (WSN). An algorithm based on an evolutionary technique is proposed, with problem-specific genetic operators to improve computing efficiency. Redundancy within a sensor network can be exploited to reduce the communication cost incurred in execution of spatial queries. Any reduction in communication cost would result in an efficient use of battery energy, which is very limited in sensors. Our objective is to self-organize the network, in response to a query, into a topology that involves an optimal subset of sensors that is sufficient to process the query subject to connectivity, coverage, energy consumption, cover size and communication overhead constraints. Query processing must incorporate energy awareness into the system by reducing the total energy consumption and hence increasing the lifetime of the sensor cover, which is beneficial for large long running queries. Experiments have been carried out on networks with different sensors Transmission radius, different query sizes, and different network configurations. Through extensive simulations, we have shown that our designed technique result in substantial energy savings in a sensor network. Compared with other techniques, the results demonstrated a significant improvement of the proposed technique in terms of energy-efficient query cover with lower communication cost and lower size.     

In-network wireless sensor network query processors: State of the art,challenges and future directions

In wireless sensor networks (WSNs), energy is valuable because it is scarce. This causes their life time to be determined by their ability to use the available energy in an effective and frugal manner. In most of the earlier sensor network applications, the main requirement consisted mainly of data collection but transmitting all of the raw data out of the network may be prohibitively expensive (in terms of communication) or impossible at given data collection rates.In the last decade, the use of the database paradigm has emerged as a feasible solution to manage data in a WSN context. There are various sensor network query processors (SNQPs) (implementing in-network declarative query processing) that provide data reduction, aggregation, logging, and auditing facilities. These SNQPs view the wireless sensor network as a distributed database over which declarative query processor can be used to program a WSN application with much less effort. They allow users to pose declarative queries that provide an effective and efficient means to obtain data about the physical environment, as users would not need to be concerned with how sensors are to acquire the data, or how nodes transform and/or transmit the data.This paper surveys novel approaches of handling query processing by the current SNQP literature, the expressiveness of their query language, the support provided by their compiler/optimizer to generate efficient query plans and the kind of queries supported. We introduce the challenges and opportunities of research in the field of in-network sensor network query processing as well as illustrate the current status of research and future research scopes in this field.     

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.     

Duty cycle aware spatial query processing in wireless sensor networks

The recent evolution in sensor node location technology has spurred the development of a special type of in-network processing for wireless sensor networks (WSN), called spatial query processing. These queries require data from nodes within a region (called region of interest) defined by the users. The state of the art of spatial query processing considers, in general, that nodes are always on. However, nodes can go to sleep mode (turn off the radio in duty cycles) in order to save energy. This work proposes an energy-efficient in-network spatial query processing mechanism that assumes nodes having no knowledge about their neighbors. The proposed mechanism is able to process spatial queries without the necessity of periodic beacon transmissions for neighbor table updates or for synchronization. Hence, it can work properly over different types of duty cycle algorithms.     

Spatial query processing in wireless sensor networks – A survey

Wireless sensor networks (WSN) are particularly useful for obtaining data concerning events limited to a well-defined geographic region, such as a disaster site or a malfunctioning subsection of a factory plant. Such applications typically use spatial queries, which are SQL-like queries where location constraints are imposed on the collected data. Further, spatial queries allow changing the set of nodes (the region of interest) at runtime. This work surveys spatial queries in WSN. Due to the particular energy and resource constraints of WSN, spatial queries are performed by mechanisms having several stages, each of them implemented using localized distributed algorithms. This article categorizes the existing strategies for each stage, in order to ease the understanding of the state of the art. Finally, we analyze the most recent works on spatial query processing, identifying which classes of algorithms are used on each stage.     

Novel itinerary-based KNN query algorithm leveraging grid division routing in wireless sensor networks of skewness distribution

Wireless sensor networks (WSN) is a key enabling technique for achieving the vision of the Internet of Things. In many applications of WSN such as environmental monitoring and vehicle tracking, they may require to launch spatial queries for collecting and gathering sensory data for achieving certain goals. One such query is the \(K\) nearest neighbor (KNN) query, which aims to collect sensory data from \(k\) sensor nodes nearest to a certain query location. Techniques, namely the itinerary-based KNN query algorithms, are recently developed for facilitating KNN queries. Generally, these techniques propagate queries and collect data along a predetermined itinerary. However, query accuracy and boundary expansion are two challenges that are not well addressed. To mitigate these issues, in this paper, we propose a novel KNN query algorithm based on grid division routing in the setting of skewness distribution, where the itinerary is formed based on the connectivity of adjacent grid cells centers. This technique can achieve better query accuracy and cause less energy consumption by executing the query concurrently in subregions. Besides, the void region problem is well addressed based on the proximity of neighbor grid cells. Experiment result shows that our technique performs better in several aspects including query accuracy, data redundancy, and energy efficiency.     

MaD‐WiSe: a distributed stream management system for wireless sensor networks

Wireless sensor networks (WSN) are composed of several sensors having limited memory, processing power, communication bandwidth, and energy, which cooperate in performing a given task. The use of the database paradigm has emerged in the last few years as a viable solution to manage data in such a context. In this paper we present the MaD‐WiSe system, a distributed query processing framework that moves the processing of the query into the network. MaD‐WiSe reconsiders various aspects related to database system design and it reinterprets them according to the WSN constraints and requirements. In particular it considers the aspects related to the definition of a query language to formalize the queries, a stream model to manage data acquired by the sensors, a query algebra to define the operators that actually perform the query, and energy efficiency and query optimization strategies for saving energy. Copyright © 2010 John Wiley & Sons, Ltd.     

无线传感器网络能量有效的实时查询处理方法

实时性和能量有效性是战争、抢险救灾等无线传感器网络系统应用的重要指标,因而提出了在查询截止期内,访问节点数目最大化,同时尽可能减少能量消耗的方法.此方法提出了松弛时间和数据传递模式的概念,并利用松弛时间计算跳步数的门限值,对比节点的不同路由方式的跳步数和门限值的关系,从而确定节点的数据传递模式,制定有效的实时查询计划的查询处理方法.仿真实验证明,利用这种查询处理方法能够有效的提高在截止期内查询的准确度和减少查询所需能量.     

QoS-aware optimization of sensor network queries

The resource-constrained nature of mote-level wireless sensor networks (WSNs) poses challenges for the design of a general-purpose sensor network query processors (SNQPs). Existing SNQPs tend to generate query execution plans (QEPs) that are selected on the basis of a fixed, implicit expectation, for example, that energy consumption should be kept as small as possible. However, in WSN applications, the same query may be subject to several, possibly conflicting, quality-of-service (QoS) expectations concomitantly (for example maximizing data acquisition rates subject to keeping energy consumption low). It is also not uncommon for the QoS expectations to change over the lifetime of a deployment (for example from low to high data acquisition rates). This paper describes optimization algorithms that respond to stated QoS expectations (about acquisition rate, delivery time, energy consumption and lifetime) when making routing, placement, and timing decisions for in-WSN query processing. The paper shows experimentally that QoS-awareness offers significant benefits in responding to, and reconciling, diverse QoS expectations, thereby enabling QoS-aware SNQPs to generate efficient QEPs for a broader range WSN applications than has hitherto been possible.     

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.     

无线传感器网络不确定数据PT-Top k查询处理技术

在无线传感器网络现实应用中,感知数据普遍存在不确定性。由于不确定数据引入了概率维度,使得不确定数据查询种类更加丰富,同时也给查询处理带来困难。不确定数据Top-k查询是一个典型的不确定数据查询任务。考虑到无线传感器网络查询处理技术对查询响应时间和网络通信消耗的高要求,研究了面向层次聚簇结构的无线传感器网络不确定数据Top-k查询处理技术。通过分析不确定数据特点,基于x-tuple规则元组模型,采用簇内与簇间的两阶段数据查询处理机制,提出了基于Poisson分布的分布式不确定数据PT-Top k查询处理近似算法TPQP。通过实验,从总体通信消耗、与概率阈值p相关分析、与排序数k相关分析以及数据敏感度分析等方面,说明了TPQP算法在通信消耗、查询响应时间上的优越性。     

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.     

基于节点分布密度的传感器网络查询处理机制

为了使传感器网络在进行数据查询时降低能耗和提高网络生命期,引入了一种分布式查询处理机制。这种机制是先将查询分发到网络后再进行优化,这种方法更具有针对性,优化效果也更明显。分簇路由协议与分布式查询有着天然的结合点。每个簇头相当于传统数据库中的一个索引,负责查询的分析、优化和数据融合。簇头根据本区域的节点分布和数据特性可以自主地选择区域内结构而不受其他区域的影响,这样就可以把每个区域看成一个自治系统,而整个传感器网络就是多个自治系统的集合。结果表明：设计查询处理机制时考虑这些因素可以降低能耗和提高网络生命期。     

链路感知的传感器网络空间范围查询处理算法

在无线传感器网络环境中,用户经常提交空间范围查询以获取网络某局部区域的统计信息,如最大温度、平均湿度等。现有的基于路线的空间范围查询处理算法假设节点通信模型为理想的圆盘模型,而实际的网络并不满足该假设,导致其能量消耗大且查询结果质量差。提出了一种链路感知的空间范围查询处理算法LSA,它根据网络拓扑和链路质量动态地将查询区域划分为若干个网格,依次收集各网格中节点的感知数据,以生成最终的查询结果。LSA算法通过遍历查询区域内的所有网格,保证了算法查询结果的质量。提出了启发式的网格划分方法以降低节点间数据通信的丢包率,给出链路感知的数据收集算法,以减少算法的能量消耗,提高查询结果的质量。通过仿真实验系统地分析和比较了LSA算法和现有的IWQE算法的能量消耗及查询结果质量,结果表明,在绝大多数情况下,LSA算法优于IWQE算法。     

Distributed adaptive top-k monitoring in wireless sensor networks

Top-k monitoring queries are useful in many wireless sensor network applications. A query of this type continuously returns a list of k ordered nodes with the highest (or lowest) sensor readings. To process these queries, a well-known approach is to install a filter at each sensor node to avoid unnecessary transmissions of sensor readings. In this paper, we propose a new top-k monitoring method, named Distributed Adaptive Filter-based Monitoring. In this method, we first propose a new query reevaluation algorithm that works distributedly in the network to reduce the communication cost of sending probe messages. Then, we present an adaptive filter updating algorithm which is based on predicted benefits to lower down the transmission cost of sending updated filters to the sensor nodes. Experimental results on real data traces show that our proposed method performs much better than the other existing methods in terms of both network lifetime and average energy consumption.     

Information discovery in mission-critical wireless sensor networks

Wireless sensor networks (WSN) are attractive for information gathering in large-scale data rich environments and can add value to mission-critical applications such as battlefield surveillance and reconnaissance. However, in order to fully exploit these networks for such applications, energy-efficient and scalable solutions for data storage and information discovery are essential. In this paper, we propose a novel method of information management in wireless sensor networks that can significantly increase network lifetime and minimize query processing delay resulting in quality of service (QoS) improvements that are of significant benefit to mission-critical applications. We propose novel methods for data dissemination, information storage and discovery that are totally distributed and also take into account the energy limitations of individual sensors. We present analytical and simulations results that prove the proposed methods of information management to offer significant improvements in the resolution of global ALL-type as well as individual ANY-type queries in comparison to current approaches. In addition, the results prove that the QoS improvements come with significant network-wide energy savings that will result in an increase of the network lifetime.     

传感器网络中节点个数约束查询处理算法

对传感器网络中一类新查询--节点个数约束查询,提出能量有效的查询处理算法.算法主要由查询下发和结果回收两部分构成.查询下发算法首先根据节点个数约束查询的特点提出相关节点选择以及基于Steiner树的查询下发算法.然后对该下发算法以及一种基于洪泛的能量有效查询下发算法的能量消耗进行分析,并对比两种算法的能量消耗从中选择适当的下发算法.结果回收算法提出直接和间接两种结果回收方式,并给出两种方式在进行结果回收时能够节省能量的条件.仿真实验表明,提出的能量有效节点个数约束查询处理算法能够在满足用户查询精度的同时,使其能量消耗低于其他查询处理算法.     

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

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

Optimizing in-network aggregate queries in wireless sensor networks for energy saving

This study proposes a method of in-network aggregate query processing to reduce the number of messages incurred in a wireless sensor network. When aggregate queries are issued to the resource-constrained wireless sensor network, it is important to efficiently perform these queries. Given a set of multiple aggregate queries, the proposed approach shares intermediate results among queries to reduce the number of messages. When the sink receives multiple queries, it should be propagated these queries to a wireless sensor network via existing routing protocols. The sink could obtain the corresponding topology of queries and views each query as a query tree. With a set of query trees collected at the sink, it is necessary to determine a set of backbones that share intermediate results with other query trees (called non-backbones). First, it is necessary to formulate the objective cost function for backbones and non-backbones. Using this objective cost function, it is possible to derive a reduction graph that reveals possible cases of sharing intermediate results among query trees. Using the reduction graph, this study first proposes a heuristic algorithm BM (standing for Backbone Mapping). This study also develops algorithm OOB (standing for Obtaining Optimal Backbones) that exploits a branch-and-bound strategy to obtain the optimal solution efficiently. This study tests the performance of these algorithms on both synthesis and real datasets. Experimental results show that by sharing the intermediate results, the BM and OOB algorithms significantly reduce the total number of messages incurred by multiple aggregate queries, thereby extending the lifetime of sensor networks.     

Effective query aggregation for data services in sensor networks

Providing efficient data services has been required by many sensor network applications. While most existing work in this area focuses on data aggregation, not much attention has been paid to query aggregation. For many applications, especially ones with high query rates, query aggregation is very important. In this paper, we study a query aggregation-based approach to provide efficient data services. In particular: (1) we propose a multi-layer overlay-based framework consisting of a query manager and access points (nodes), where the former provides the query aggregation plan and the latter executes the plan; (2) we design an effective query aggregation algorithm to reduce the number of duplicate/overlapping queries and save overall energy consumption in the sensor network. We also design protocols to effectively deliver aggregated queries and query results in the sensor network. Our performance evaluations show that by applying our query aggregation algorithm, the overall energy consumption can be significantly reduced and the sensor network lifetime can be prolonged correspondingly.