Research on Query Processing Methods for Location-based Services in MANETs
Yuka Komai · OUKA (Osaka University Knowledge Archive) (Osaka University) · 2016
Recently, there has been an increasing interest in mobile ad hoc networks (MANETs), which are comprised solely of mobile nodes.Since no special infrastructure is required, many applications are expected to be developed for MANETs, in various fields such as military affairs, rescue operations at disaster sites, and information sharing at event sites.Location-based services (LBS) are typical applications for MANETs, which are typically composed of a large number of nodes over a wide area.In an LBS, realtime location-specific queries to search for information held by mobile nodes are often used; and in such cases, it is effective to process the queries as k nearest neighbor (kNN) queries which acquire the information on kNNs from the specified location (query point), and convex hull queries which retrieve the information necessary for calculating the convex hull of all the nodes composing a given network.Although there has been many existing studies for kNN search and convex hull detection in networks where there is a central server, there is no research focused on query processing of such queries in MANETs.MANETs possess notable characteristics, such as limitations on network bandwidth, and dynamic topology change due to the movement of mobile nodes.Therefore, a naïve approach acquiring the information on all nodes within the entire network does not work well because it produces excessive message transmission (i.e., traffic), resulting decrease in the accuracy of the query result due to packet losses.In addition, existing location-specific query processing methods in wireless sensor networks do not work well either because in wireless sensor networks, sensor nodes are stationary or loction-aware (i.e., know their own neighbors in advance).In MANETs, it is difficult to accurately know the information on neighboring nodes since the network topology dynamically changes due to the movement of mobile nodes.Therefore, we design query processing methods for reducing traffic and maintaining high accuracy of the query result without knowing neighboring nodes' information in advance.Moreover, in an LBS, it is required to search for not only nodes themselves but also data items associated with a given location (location-dependent data).As nodes move in MANETs, data items which have been held by a node since long time ago are likely no longer related to the node's current location, because these data items are associated vi with the node's former location.In such cases, the query-issuing node cannot effectively search for requested data items using location information.Therefore, new techniques searching for location-dependent data items are required.In this thesis, we propose kNN and convex hull query processing methods for LBS in MANETs.This thesis consists of five chapters.First, we introduce the research background and issues for LBS in MANETs in Chapter 1.In Chapters 2 and 3, we address kNN query processing to search for the k nearest nodes and for the k nearest data items, respectively.In Chapter 4, we address query processing for calculating the convex hull of nodes in MANETs and also discuss how to know the convex hull of location-dependent data items in MANETs.Finally, in Chapter 5, we summarize this thesis and discuss our future work.More specifically, in Chapter 2, we propose two kNN query processing methods to search k nearest nodes from the query point in MANETs which can reduce the traffic for query processing, as well as maintain high accuracy of the query result.In our methods, queries are transmitted only to neighboring nodes near from the query point to avoid receiving replies from the nodes far from the query point.More specifically, the query-issuing node first forwards a kNN query using geo-routing to the nearest node from the query point.Then, the nearest node from the query point forwards the query to other nodes close to the query point, and each node receiving the query replies with the information on itself.Since these methods require neither flooding a kNN query over the entire network nor knowing other nodes' information in advance, they can solve the problems faced by the naïve and existing approaches, which are caused by the bandwidth limitation and dynamical changes of network topology.We conduct simulation experiments to verify that our proposed methods reduce traffic and achieve high accuracy of the query result, in comparison with the existing methods.In Chapter 3, we propose a method for processing kNN queries that are used to search for the k nearest location-dependent data items in MANETs.In this chapter, we focus on kNN search for data items held by nodes unlike the information on nodes as assumed in Chapter 2. This method achieves low traffic and high accuracy of the query result by limiting the search area.To make the search area small, our method keeps data items at the nodes near the locations with which the items are associated, and nodes cache the data items whose associated locations are near to them.A node issues a query and then the neighboring nodes answer to the query by sending back their copies vii without duplicate copies, although each node does not know which data items the other nodes cache.We conduct simulation experiments to verify that our method reduces the traffic involved in processing kNN queries, and also achieves high accuracy of the query result.In Chapter 4, we propose two convex hull query processing methods; Local Convex Hull (LCH) and Local Wrapping (LW) methods, for reducing the traffic for query processing and maintaining high accuracy of the query result in MANETs.More specifically, in the LCH method, the query-issuing node first floods a convex hull query throughout the entire network.Then, each node replies with information on the nodes that are the vertices of its local convex hul.Here, the local convex hull is the convex hull composed of nodes whose information has already been received.In the LW method, to avoid transmitting queries throughout the entire network, the query-issuing node first sends a convex hull query to a node located on the outer boundary of the network, using a geo-routing technique.Then, the query is basically transmitted only to the nodes on the outer boundary and the query path forms a loop.In this way, unnecessary reply transmissions can be suppressed, even if mobile nodes do not know their neighbors in advance.We also show experimental results for verifying that our proposed methods can reduce the traffic for query processing compared with a naïve method, and also achieve high accuracy of the query result.CONTENTS xi 4.4.1 Simulation Model . . . . . . .