KNN Query Processing in Wireless Sensor and Robot Networks

Abstract

In Wireless Sensor and Robot Networks (WSRNs), static sensors report event information to one of the robots. In the k nearest neighbour query processing problem in WSRNs, the robot receives event report needs to find exact k nearest robots (KNN) to react to the event, among those connected to it. We are interested in localized solutions, which avoid message flooding to the whole network. Several existing methods restrict the search within a predetermined boundary. Some network density-based estimation algorithms were proposed but they either result in large message transmission or require the density information of the whole network in advance which is complex to implement and lacks robustness. Algorithms with tree structures lead to the excessive energy consumption and large latency caused by structural construction. Itinerary based approaches generate large latency or unsatisfactory accuracy. In this thesis, we propose a new method to estimate a search boundary, which is a circle centred at the query point. Two algorithms are presented to disseminate the message to robots of interest and aggregate their data (e.g. the distance to query point). Multiple Auction Aggregation (MAA) is an algorithm based on auction protocol, with multiple copies of query message being disseminated into the network to get the best bidding from each robot. Partial Depth First Search (PDFS) attempts to traverse all the robots of interest with a query message to gather the data by depth first search. This thesis also optimizes a traditional itinerary-based KNN query processing method called IKNN and compares this algorithm with our proposed MAA and PDFS algorithms. The experimental results followed indicate that the overall performance of MAA and PDFS outweighs IKNN in WSRNs.