## 3 Proposed Skyline Query Processing Method Based on DCS
### Proposed Skyline Query Processing Method  
The proposed method is also based on the following assumptions: first, a DCS is built on a sensor network and sensor readings are geographically ordered across the sensor network like KDDCS, GDCS and DIM. Second, all the sensor nodes in a sensor network have a unique identifier (ID). Third, they know their geographic locations and their neighbor nodes' IDs. A neighbor node refers to a node to which a sensor node can communicate within one hop. The last assumption is that each node knows the ranges of data stored in its neighbor nodes. We call the range of data stored in a neighbor node NDR. On the basis of these assumptions, a skyline query is processed in three stages. To describe the proposed skyline query processing method more clearly, we use an example sensor network as shown in Figure 2. We assume that GDCS which uses virtual grid technique is built on the sensor network. In the figure, the GDCS is based on 5 \(\times\) 5 grid. The sensor network is deployed to monitor CO\({}_{2}\) and SO\({}_{2}\). In this figure, the sensor nodes at the left-lower corner stores sensor readings whose values are smallest, while the sensor nodes at the right-upper corner store the data whose CO\({}_{2}\) and SO\({}_{2}\) values are largest. In the first stage, whenever a skyline query is issued, a start node (SN) where query processing is started is selected, and then the skyline query is transmitted to the SN. For example, in Figure 2, let us assume that a skyline query \"find the most polluted area\" is issued. In this case, candidate query results may be stored in the sensor node 24 at the upper-right corner and its neighbor nodes. Therefore, the sensor node 24 is selected as a SN. On the other hand, if the query is \"find the area in which atmospheric pollution is the least\", the sensor node 0 at the lower-left corner and its neighbor nodes may store candidate query results. For this query, the sensor node 0 is selected as a SN. A skyline query may be given by a user, and the query is injected into the sensor network by a base station (BS). The BS analyzes the skyline query to select a SN which is expected to process the result most effectively, and transmits it to the SN. The SN really starts to process the skyline query. The second stage is started by the SN. The SN creates a skyline query message (SQM) and sends it to propagate the SQM to neighbor nodes to search for candidate nodes (CNs) where candidate data for the query are stored. The SQM consists of (Q, CSR, SIDs, TIDs), where Q is the contents of the skyline query, and CSR is the range of candidate data set which is currently gathered, SIDs are the set of all sensor nodes' IDs that the SQM is passed by, and TIDs are the sensor nodes' IDs that will receive the SQM. The CSR, SIDs and TIDs of the SQM which is created by the SN may have NULL values. The SQM transmission process is repeated until complete candidate results are found through the following process. When a sensor node (or a SN) receives a SQM, it reads the CSR of the SQM, and updates the CSR to reflect the range of data stored in the sensor node. Of course, if the sensor node  
Figure 2: Sensor network where GDCS is deployed  
does not have any data, there would be no need to change the CSR. After updating the CSR, the sensor node checks whether the CSR is NULL. If the CSR is NULL, the sensor node transmits the SQM to all the neighbor nodes since the sensor node does not dominate any other node. If the CSR is not NULL, the sensor node selects neighbor nodes which have NDRs that are not dominated by the CSR and other NDRs. The current sensor node excludes sensor nodes that transmit the SQM to it. The selected nodes are included in the TIDs of the SQM. After that, the sensor node transmits to selected sensor nodes the SQM, and the sensor nodes that receive the SQM repeat the above process. The sensor node that transmits the SQM stores the CSR of the SQM to avoid unnecessary message transmission.