Study On Skyline Query Processing Techniques In Wireless Sensor Networks

Recently, wireless sensor network has been widely used in so many fields of national economy, with its important applicable value. At the same time, as the main means of multi-criteria decision making, skyline query plays a more and more important role in the applications of wireless sensor network. Although the techniques of both sensing data management in wireless sensor network and skyline query in traditional database system have been widely studied, these existing solutions cannot be directly used in the environment of wireless sensor network. This is because (1) the computation ability, the storage and the energy resource of the sensor nodes in wireless sensor network are limited and the skyline query algorithms in traditional database literature do not consider these properties; (2) in the skyline query, the dominance relationship between tuples is an partial order relation, and the skyline query has a lot of differences with aggregate query, join query and top-k query in the sensing data management.This dissertation deeply studies the skyline query and its corresponding problems over wireless sensor networks. Its contributions are summarized as follows:(1) The problem of sliding window skyline query in wireless sensor network is discussed. According to the property of decomposability of skyline query, a merge-based sliding window skyline query algorithm (MBA) is proposed; on the base of MBA, another new filter-based sliding window skyline query algorithm (FBA) is also proposed to reduce data transmission cost by employing two types of filters within each sensor node. The experimental results show that FBA can greatly decrease the communication cost, while continuous sliding window skyline query is executed, in the sensor network.(2) According to the characteristics of sensing applications, it discusses the approximate skyline query in wireless sensor networks and proposes a selection-based approximant skyline query algorithm, SBS, which takes the place of the exact results with parts of the tuples in the skyline; in order to solve the problem of losing the skyline precision after multi-level selections, a mapping-based approximant skyline query algorithm (MBS) is proposed. MBS maps a large number of tuples in the real domain into corresponding tuples in the integral domain, and therefore reducing the cost of data transmission of wireless sensor nodes since the number of the mapped tuples in the integral domain is much less than that of the original tuples in the real domain. The experimental results show that MBS both guarantees the precision of the approximate skyline query and reduces the communication cost of the wireless sensor network.(3) This dissertation discusses the problem of the skyline monitoring, a bottom-up skyline monitoring algorithm BSM is proposed that uses local filtering to reduce the unnecessary data transmission and a top-down algorithm TSM that uses global filtering to achieve the same aim. By combining these two algorithms, a hybrid algorithm HSM is proposed that has both the advantages of the two algorithms above. The experimental results show that HSM only needs to transmit a little data to achieve real-time monitoring of the skyline of the wireless sensor network.(4) An energy-efficient multiple subspace skyline query algorithm EMSE is proposed to achieve high efficiency of executing multiple skyline queries in wireless sensor network, according to the property that there are so many end users to the wireless sensor network. By making full use of the high computation ability of the base station, EMSE rewrites multiple skyline queries to reduce the query propagation cost and avoid the redundant result transmission cost of the skyline tuples. What's more, according to the property of the sensor node sharing communication channel, this dissertation discusses the techniques of sharing data transmission and in-network filtering, which aim at further reducing the communication cost. The experimental results show that EMSE calculates the skyline query in all subspaces correctly and avoids the large amount of communication cost brought by executing all skyline queries separately and is an energy-efficient multi-subspace skyline query algorithm.