Research On The Top-k Query Processing Optimization Algorithms For The Sensor Networks

Wireless sensor network is a data-centric network, which exhibit many features, such as self-organization, large-scale, topology-dynamic and application-related. Holding the functions of information collection, processing and query, the information query is the key of the wireless sensor network (WSN) research. According to these characteristics and functions of the wireless sensor network, many scholars put forward the related algorithms and solutions, the Top-k query algorithm occupies the important position. Efficient implementation of the top-k queries is the key for information searching. But the traditional network or database’s Top-k query is not suitable for sensor network, it should be corresponding modification or adjustment based on the characteristics of the wireless sensor network (WSN). With the new frontier such as the cyber-physical systems, where there can be a large number of users searching information directly into the physical world, many new challenges arise for top-k query processing. From the perspective of client, the user can set different priorities to request different set of information. Therefore, the top-k not only should be search the data of multi-dimensional, but also could be query the data of meets user specified criteria (preference function). From the perspective of system, the data collection is usually carried out by tiny sensing devices, these devices are usually suffered strictly energy-constraints, so the system efficiency is crucial.This paper proposed a framework which was based on layer sorting to meet the two aspects. Firstly, we adopted arena principle to construct the non-dominated set by using sensor data. Secondly, in order to build the Dominant Graph, we used the data sets of non-dominated set to construct the parent-child relationships. The sensor network maintained an efficient dominant graph data structure for data readings including constructing and updating Dominant Graph, in order to ensure that the data getting from DG diagram was correct. In this paper, the experimental results demonstrated that the running time of construct non-dominated set of the arena principle algorithm was lower than both the quick sort algorithm and the improved quick sort algorithm. Therefore, both the energy cost and the construction time consumption were reduced greatly, and the efficiency of the top-k query processing was improved obviously. Finally, this paper proposed a simple Top-k query algorithm, experimental results showed that the query algorithm could still get better query efficiency, and reduce the energy consumption in the process of data extraction, under the condition which the k value was smaller, even if the amount of data was very large.