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

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

An analytical study of central and in-network data processing for wireless sensor networks

This paper compares the performance of centralized and in-network data processing for wireless sensor networks (WSNs) under various deployment conditions on the real sensor hardware Sun SPOT from Sun Microsystems. We define several criteria to measure the quality of responses in WSN applications. Guided by an extensive experimental study, we discuss in detail the performance impacts of different deployment factors on algorithms that implement both centralized and in-network computing. Finally, performance guidelines are given to algorithm designers for WSN applications.     

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.     

Power efficiency through tuple ranking in?wireless sensor network monitoring

In this paper, we present an innovative framework for efficiently monitoring Wireless Sensor Networks (WSNs). Our framework, coined KSpot, utilizes a novel top-k query processing algorithm we developed, in conjunction with the concept of in-network views, in order to minimize the cost of query execution. For ease of exposition, consider a set of sensors acquiring data from their environment at a given time instance. The generated information can conceptually be thought as a horizontally fragmented base relation R. Furthermore, the results to a user-defined query Q, registered at some sink point, can conceptually be thought as a view V. Maintaining consistency between V and R is very expensive in terms of communication and energy. Thus, KSpot focuses on a subset V??(?V) that unveils only the k highest-ranked answers at the sink, for some user defined parameter k. To illustrate the efficiency of our framework, we have implemented a real system in nesC, which combines the traditional advantages of declarative acquisition frameworks, like TinyDB, with the ideas presented in this work. Extensive real-world testing and experimentation with traces from UC-Berkeley, the University of Washington and Intel Research Berkeley, show that KSpot provides an up to 66% of energy savings compared to TinyDB, minimizes both the size and number of packets transmitted over the network (up to 77%), and prolongs the longevity of a WSN deployment to new scales.     

Adaptive processing of historical spatial range queries in peer-to-peer sensor networks

We investigate the problem of processing historical queries on a sensor network. Since data is considered to have been already collected at the sensor nodes, the main issue is exploring the spatial component of the query in order to minimize its cost represented by the energy consumption. We assume queries can be issued at any network node, i.e., there is no central base station and all nodes have only local knowledge of the network. On the one hand, a globally optimum query processing plan is desirable but its construction is not possible due to the lack of global knowledge of the network. On the other hand, while a simple network flooding is feasible, it is not a practical choice from a cost perspective. To address this problem we propose a two-phase query processing strategy, where in the first phase a path from the query originator to the query region is found and in the second phase the query is processed within the query region itself. This strategy is supported by analytical models that are used to dynamically select the best processing strategy depending on the query specifics. Our extensive analytical and experimental results show that our analytical models are accurate and that the two-phase strategy is better suited for small to medium sized queries, being up to 10 times more cost effective than a typical network flooding. In addition, the dynamic selection of a query processing technique proved itself capable of always delivering at least as good performance as the most energy efficient strategy for all query sizes. Research supported in part by NSERC Canada.     

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.     

无线传感器网络智能信息处理研究

由大量微小传感器节点组成的无线传感器网络主要用于从目标对象收集信息,但由于节点资源受限,给无线传感器网络的信息处理带来了严峻挑战,为此,必须采取简单、高效的处理策略.本文综述了无线传感器网路环境下智能信息处理的最新研究进展,包括网内聚合、数据压缩和分布式存储和查询等方法,对各种算法的优缺点进行评述,并指出了其关键问题.孙优贤(1940-),男,教授,博士生导师,中国工程院院土,研究方向为复杂系统理论、分布控制系统以及企业综合自动化等.     

传感器网络中基于域的聚集算法

聚集运算是传感器网络查询处理中最重要的一个运算。提出了一种基于域聚簇的网内聚集算法PIA。在PIA中,首先结合传感器网络的节点特性和位置信息,提出了一种基于域的分布式数据汇聚模型,把传感器网络按域划分来构建连通核,查询只需在连通核中寻径,因而能明显降低寻径时间复杂度并且具有更好的分布性。在PIA中,核心节点把当前路径中的Max和Min值传送到节点上,如果节点的值不符合要求就放弃本次传送,因而能够明显减少数据的传送次数,从而达到节省能量的目的。理论分析和实验表明该算法较传统算法在节省能量上有较好的表现。     

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.     

Improving the QoS for information discovery in autonomic wireless sensor networks

Wireless sensor networks (WSN) are attractive for information gathering in large-scale data rich environments. In order to fully exploit the data gathering and dissemination capabilities of these networks, energy-efficient and scalable solutions for data storage and information discovery are essential. Traditionally, the communication pattern in WSNs has been assumed to be many-to-one; i.e., numerous sensors gather information which is routed to a central point commonly referred to as the sink. However, many emerging applications for WSNs require dissemination of information to interested clients within the network requiring support for differing traffic patterns. Further, in-network query processing capabilities are required for autonomic information discovery.In this paper, we formulate the information discovery problem as a load-balancing problem, with the combined aim being to maximize network lifetime and minimize query processing delay resulting in quality of service (QoS) improvements. We propose novel methods for data dissemination, information discovery and data aggregation that are designed to provide significant QoS benefits. We make use of affinity propagation to group “similar” sensors and have developed efficient mechanisms that can resolve both ALL-type and ANY-type queries in-network with improved energy-efficiency and query resolution time.Simulation and Analytical results prove the proposed method(s) of information discovery offer significant QoS benefits for ALL-type and ANY-type queries in comparison to previous approaches.     

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.     

A pure peer-to-peer approach for kNN query processing in mobile ad hoc networks

Together with advanced positioning and mobile technologies, P2P query processing has attracted a growing interest number of location-aware applications such as answering kNN queries in mobile ad hoc networks. It not only overcomes drawbacks of centralized systems, for example single point of failure and bottleneck issues, but more importantly harnesses power of peers’ collaboration. In this research, we propose a pure mobile P2P query processing scheme which primarily focuses on the search and validation algorithm for kNN queries. The proposed scheme is designed for pure mobile P2P environments with the absence of the base station support. Compared with centralized and hybrid systems, our system can reduce energy consumption more than six times by making use of data sharing from peers in a reasonable mean latency of processing time for networks with high density of moving objects as can be seen in the simulation results.     

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.     

A holistic approach to decentralized structural damage localization using wireless sensor networks

Wireless sensor networks (WSNs) have become an increasingly compelling platform for Structural Health Monitoring (SHM) applications, since they can be installed relatively inexpensively onto existing infrastructure. Existing approaches to SHM in WSNs typically address computing system issues or structural engineering techniques, but not both in conjunction. In this paper, we propose a holistic approach to SHM that integrates a decentralized computing architecture with the Damage Localization Assurance Criterion algorithm. In contrast to centralized approaches that require transporting large amounts of sensor data to a base station, our system pushes the execution of portions of the damage localization algorithm onto the sensor nodes, reducing communication costs by two orders of magnitude in exchange for moderate additional processing on each sensor. We present a prototype implementation of this system built using the TinyOS operating system running on the Intel Imote2 sensor network platform. Experiments conducted using two different physical structures demonstrate our system’s ability to accurately localize structural damage. We also demonstrate that our decentralized approach reduces latency by 65.5% and energy consumption by 64.0% compared to a typical centralized solution.     

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.     

Algebraic equivalences of nested relational operators

Algebraic optimisation is both theoretically and practically important for query processing in complex value databases. In this paper, we consider this issue and investigate some algebraic properties concerning the nested relational operators.The join operation is one of the most time-consuming operations in nested relational query processing. We introduce a new join operator, called P-join, which combines the advantages of Roth's extended natural join and Colby's recursive join for efficient data access. We also investigate some algebraic properties concerning the P-join operator and extended relational operators, which can be used for query optimisation in nested relational databases.We then examine the role of the restructuring operators nest and unnest in their interactions with the extended relational operators proposed by Roth et al. Under certain functional and mutual data dependencies, the six nested relational equations will hold.Finally, we outline the steps of a heuristic optimisation algorithm that utilises algebraic transformation rules developed in this paper and previous related work to transform an initial query to an optimised one that is more efficient to execute.     

HIPaG: An energy-efficient in-network join for distributed condition tables in sensor networks

In sensor networks, the event-detection process can be considered as a join of two relations, i.e., a sensor table and a condition table, where a condition table is a set of tuples each of which contains condition information about a certain event. When join operations are used for event-detection, it is desirable, if possible, to perform ‘in-network’ joins in order to reduce the communication cost. In this paper, we propose an in-network join algorithm, called HIPaG. In HIPaG, a condition table is partitioned into several fragments. Those fragments are stored either in paths from the base station to sensor nodes, or in groups of nodes each of which are within the broadcast range among each other. By distributing a condition table in this way, a distributed join of a sensor table and a condition table can be effectively performed in the network. The experimental results show that our proposed HIPaG works much better than the existing method.     

An In-Network Querying Framework for Wireless Sensor Networks

In contrast to traditional wireless sensor network (WSN) applications that perform only data collection and aggregation, the new generation of information processing applications such as pursuit-evasion games, tracking, evacuation, and disaster relief applications require in-network information storage and querying. Due to the resource limitations of WSNs, it is challenging to implement in-network querying in a distributed, lightweight, resilient, and energy-efficient manner. We address these challenges by exploiting location information and the geometry of the network and propose an in-network querying framework, namely, the Distributed Quad-Tree (DQT). DQT is distance sensitive for querying of an event: the cost of answering a query for an event is at most a constant factor (2sqrt{2} in our case) of the distance “d” to the event. DQT construction is local and does not require any communication. Moreover, due to its minimalist infrastructure and stateless nature, DQT shows graceful resilience to node failures and topology changes. Since event-based querying is inherently limited to the anticipated types of inquiries, we further extend our framework to achieve complex range-based querying. To this end, we use a multiresolution algorithm, which is optimal with respect to least square errors that models the data in a decentralized way. Our model-based scheme answers queries with approximate values accompanied by certainty levels with increased resolution at lower layers of the DQT hierarchy. Our analysis and experiments show that our framework achieves distance sensitivity and resiliency for event-based querying, as well as greatly reduces the cost of complex range querying.     

Scalable keyword search on large data streams

It is widely recognized that the integration of information retrieval (IR) and database (DB) techniques provides users with a broad range of high quality services. Along this direction, IR-styled m-keyword query processing over a relational database in an rdbms framework has been well studied. It finds all hidden interconnected tuple structures, for example connected trees that contain keywords and are interconnected by sequences of primary/foreign key relationships among tuples. A new challenging issue is how to monitor events that are implicitly interrelated over an open-ended relational data stream for a user-given m-keyword query. Such a relational data stream is a sequence of tuple insertion/deletion operations. The difficulty of the problem is related to the number of costly joins to be processed over time when tuples are inserted and/or deleted. Such cost is mainly affected by three parameters, namely, the number of keywords, the maximum size of interconnected tuple structures, and the complexity of the database schema when it is viewed as a schema graph. In this paper, we propose new approaches. First, we propose a novel algorithm to efficiently determine all the joins that need to be processed for answering an m-keyword query. Second, we propose a new demand-driven approach to process such a query over a high speed relational data stream. We show that we can achieve high efficiency by significantly reducing the number of intermediate results when processing joins over a relational data stream. The proposed new techniques allow us to achieve high scalability in terms of both query plan generation and query plan execution. We conducted extensive experimental studies using synthetic data and real data to simulate a relational data stream. Our approach significantly outperforms existing algorithms.     

PEJA: Progressive Energy-Efficient Join Processing for Sensor Networks

Sensor networks are widely used in many applications to collaboratively collect information from the physical environment. In these applications,the exploration of the relationship and linkage of sensing data within multiple regions can be naturally expressed by joining tuples in these regions. However,the highly distributed and resource-constraint nature of the network makes join a challenging query. In this paper,we address the problem of processing join query among different regions progressively and energy-efficiently in sensor networks. The proposed algorithm PEJA(Progressive Energy-efficient Join Algorithm) adopts an event-driven strategy to output the joining results as soon as possible,and alleviates the storage shortage problem in the in-network nodes. It also installs filters in the joining regions to prune unmatchable tuples in the early processing phase,saving lots of unnecessary transmissions. Extensive experiments on both synthetic and real world data sets indicate that the PEJA scheme outperforms other join algorithms,and it is effective in reducing the number of transmissions and the delay of query results during the join processing.