Approximation Skyline Query Algorithm In Wireless Sensor Network

Skyline query in wireless sensor network gradually becomes a focus of the researches.However,these researches mainly involves precise skyline query results,due to the high communication cost of skyline queries,it is not energy efficient to conduct precise skyline over wireless sensor networks.In many applications,approximation query results is enough for users to investigate data and make decisions.In this paper,approximation skyline query problem in wireless sensor networks has been studied.The major contributions are summarized as following:A bitmap-based filtering ? approximation skyline algorithms(BAS)is proposed,where ? is the threshold determining the two data satisfy the approximate relationship.This algorithm divides data space into cells that contain a specific size,making the points within the same cell satisfied approximate relationship.Select the point having the maximum ability to control others,while filtering out other points which satisfied approximation relationships with this point.Thereby reducing communication overhead.According to the positions of skyline set in the data space,Select the approximate skyline set which uses approximate threshold ? as radius covering the skyline set with the least points in entire data space.Based on this idea,we propose a dancing-links based ? approximation skyline algorithm(DAS),which transformed this problem into a mathematical model of set covering problem taking use of dancing-links method to minimize data collection,thereby reducing communication overhead.Theoretical analysis and experimental results show that the algorithm can reduce the amount of data transmission,and get a more accurate approximation result.We also presents a bitmap-based ? approximation skyline algorithm(BBS),this algorithm takes use of approximate definition translated skyline set into bitmap.During the process of Aggregation data uses bitmap instead of skyline set,the bitmap obtained in the base station will be finally transfer into approximation skyline set.Theoretical analysis and experimental results show that the algorithm is efficient,reducing communication overhead,thereby prolonging the network life time.