# Enhanced Distributed Dynamic Skyline Query for Wireless Sensor Networks
## 2 Related Work  
According to the current state-of-the-art, skyline operator in database community was first introduced by [PERSON] _et al._[5]. In their work, they proposed the solution based on block nested loop (BNL) and divide-and-conquer (D & C). Inspired by BNL, [PERSON] _et al._[18] and [PERSON] _et al._[19] proposed two variants of BNL named sort-filter-skylines (SFS) and linear elimination sort for skyline (LESS), respectively. Later, two progressive processing algorithms such as Bitmap and Index were proposed by [PERSON] _et al._[20]. Nearest neighbor (NN) method and its variant NN with branch-and-bound (BB) were later presented by [PERSON] _et al._[21] and [PERSON] _et al._[22], respectively. However, these approaches are mainly suitable for centralized environments with high computational and energy resources and thus inappropriate for WSN environments. A filter-based distributed algorithm for skyline evaluation and maintenance in WSN is proposed by [PERSON] _et al._[23]. Each sensor node uses a greedy algorithm to compute a local skyline certificate, which is a subset of the local skyline and forwards it to its parent. The parent or non-leaf node calculates the certificate based on a set of local skyline points plus the certificate received from child nodes. Following this process, the root calculates the set of skyline points, which is used as a Global Skyline Filter (GSF) or global certificate. The root broadcasts the global certificate followed by a simple merge-based algorithm to filter out the points from transmissions that cannot utilize the certificate. An energy efficient Sliding Window Skyline Monitoring Algorithm (SWSMA) is proposed in [24] to continuously maintain sliding window skylines over WSN. It reduces the amount of data transferred and reduces energy consumption, as a consequence, by devising two filter based algorithms: (1) Single point filter based algorithm referred to as a Tuple Filter (TF); and (2) Grid Filter (GF) based algorithm. [PERSON] _et al._[25] proposed two evaluation algorithms for finding the skyline points on a dataset progressively. The dataset is first partitioned into disjoint subsets. Then skyline points are returned through the examination of each subset progressively using discovered skyline points to filter out the unlikely skyline points from transmission. However, the features of DCS have not been considered in these approaches and thus direct implication of them in DCS is not suitable. [PERSON] _et al._[26] propose a skyline query processing algorithm exploiting the key features of DCS. The algorithm processes a query in three stages on the basis of four assumptions: (1) choice of DCS framework is limited to KDDCS [27], GDCS [28] and DIM [29]; (2) all nodes are identified by unique ID; (3) each node knows the geographic location of its own and its neighbor nodes; and (4) each node knows the range of data stored in its neighbor nodes. In the first stage, the base station locates the Start Node (SN) where the query is to commence. In the second stage, SN creates a Skyline Query Message (SQM) and propagates the SQM to neighbor nodes to search for Candidate Nodes (CNs) where candidate data for the query are stored. This SQM transmission process is repeated until the complete candidate results are found. In the third and final stage BS generates a final query result from its gathered candidate dataset. The aforementioned assumptions made in this work are particularly expensive in a distributed environment like WSN especially DCS framework. [PERSON] _et al._[30] proposed an algorithm, known as Skyline Sensor Algorithm (SkySensor), in a customized DCS method in order to collect and store all sensor readings and retrieve skyline results efficiently from the network.