An Energy-Efficient Skyline Query for Massively Multidimensional Sensing Data

Yan Wang, Wei Wei, Qingxu Deng, Wei Liu, Houbing Song2016 · DOI

TL;DR

This paper introduces E2Sky, a novel algorithm designed to efficiently query massive, multi-dimensional sensor data in Cyber-Physical Systems (CPS). E2Sky tackles the challenge of high communication costs and slow response times in traditional skyline query methods by employing a "node cut" strategy to prune dominated nodes and a "tuple cut" strategy within nodes to filter data locally, significantly reducing data transmission and improving query efficiency.

What Problem Does This Paper Address?

Modern Cyber-Physical Systems (CPS), such as those used for smart grids and disaster monitoring, rely heavily on vast amounts of multi-dimensional data collected by wireless sensor networks (WSNs). A critical task in these systems is performing skyline queries, which help identify optimal data points across multiple objectives (e.g., finding the best combination of wind speed, temperature, and humidity for ice-disaster prediction). However, traditional skyline query algorithms struggle with the sheer volume and dimensionality of WSN data. They often incur high communication overhead due to transmitting large amounts of non-skyline data, leading to increased energy consumption, slow response times, and poor scalability, especially in large-scale WSNs where sensor energy is limited and communication is a major drain. This paper aims to bridge this gap by proposing an energy-efficient skyline query method that significantly reduces communication costs and improves query performance.

Methods

The core of E2Sky lies in two novel strategies:

  • Node Cut Strategy: This approach dynamically identifies and prunes "dominated nodes" within the sensor network's routing tree. A node is considered dominated if all its data is worse than or equal to the data in another node. By identifying these dominated nodes early, E2Sky avoids unnecessary data collection and transmission from them. This is achieved through the generation of "filter tuples" that summarize the data characteristics of nodes and their sub-trees, allowing for efficient comparison and pruning.
  • Tuple Cut Strategy (Local Cutting Tuple): Within each sensor node, E2Sky further refines data filtering. It generates a "local cutting tuple" based on the data within a node's sub-tree. This tuple acts as a local filter, enabling the node to discard non-skyline data before it's transmitted to parent nodes. This "tuple cutting" within the node significantly reduces the amount of data that needs to be uploaded, further conserving energy and improving efficiency.

The algorithm initializes by building a routing tree with the base station as the root. Each node normalizes its data and computes qdata tuples. These are then used to generate filter_tuples, which are propagated upwards. The node cut algorithm uses these filter tuples to identify and remove dominated nodes from the query path. Subsequently, the tuple cut strategy is applied within the remaining nodes to filter local data.

Datasets

The paper does not introduce new datasets. Instead, it uses synthetic data generated by a standard dataset generator for skyline queries. The experiments simulate data for applications like transmission line monitoring, where attributes like temperature, humidity, and wind speed are relevant. The data is generated with varying network sizes, numbers of sensors, and data dimensions to evaluate the algorithm's performance under different conditions.

Key Insights and Ideas

  • Decentralized Filtering is Key: The paper strongly emphasizes that effective skyline query processing in WSNs requires aggressive, decentralized filtering. Relying on a central server to process all data is inefficient.
  • Domination is Not Just Data-Level: E2Sky extends the concept of domination from individual data tuples to entire sensor nodes, enabling a more powerful pruning mechanism.
  • Dynamic Filtering Reduces Overhead: Generating dynamic filters on-the-fly, rather than pre-defining static filters, allows E2Sky to adapt to changing data and query interests, leading to better efficiency.
  • Tuple Cutting Within Nodes is Crucial: Even after node-level pruning, further filtering at the individual sensor node level is essential to minimize data transmission.

Key Results

The experimental results demonstrate that E2Sky significantly outperforms existing methods (TAG, MINMAX, SkySensor) in several key metrics:

  • Average Communications Cost: E2Sky consistently shows the lowest average communication cost across varying network sizes, numbers of sensors, and data dimensions. For instance, in Figure 4, E2Sky's cost is substantially lower than others as network size increases.
  • Real Skyline Percentage (Accuracy): E2Sky achieves a high and stable real skyline percentage, indicating that it returns accurate results. While other methods' accuracy declines with increasing network size or data dimensions, E2Sky maintains its performance.
  • Response Time: E2Sky exhibits the shortest response time, often achieving it in a single "time unit" (comparable to TAG's performance but with significantly less communication). This is attributed to its efficient data pruning.
  • Scalability: The paper highlights E2Sky's good scalability, with its performance degradation being much slower than other methods as the WSN size increases.

Limitations and Future Work

  • Limitations: The paper primarily relies on synthetic data for evaluation. While this allows for controlled experiments, real-world WSN environments might present additional complexities (e.g., node failures, unreliable links) not fully captured. The paper also mentions that the response time of SkySensor decreases with network size, which is an interesting observation but not deeply explored for E2Sky's advantage.
  • Future Work: The authors suggest that their algorithms can be applied to warning systems for failure or disaster prediction, implying potential for real-time anomaly detection and early warning applications. Further research could explore the integration of E2Sky into such systems and evaluate its performance in dynamic, real-world scenarios. The paper also implies that while E2Sky's computational overhead is small, further optimization might be possible.

Summary updated

BibTeX
@misc{wang2016energy,
  author = {Yan Wang and Wei Wei and Qingxu Deng and Wei Liu and Houbing Song},
  title = {{An Energy-Efficient Skyline Query for Massively Multidimensional Sensing Data}},
  year = {2016},
  doi = {10.3390/s16010083},
}
Figure