Less Traffic and Maintaining High Accuracy of Query Result in MANET using KNN Algorithm

Less Traffic and Maintaining High Accuracy of Query Result in MANET using KNN Algorithm

P. Priyadharshini1 Dr. N. Mahesp

1M.E Student, 2Professor,

Department of Computer Science and Engineering, Institute of Road and Transport Technology, Erode.

Abstract – This paper presents the maintenance of query result with high accuracy and also we used two beacon-less kNN query processing methods for reduction of traffic in mobile ad hoc networks (MANETs). In these methods, the query-issuing node first forwards a kNN query to the nearest node from the point using geo-routing specified by the query (query point). Then, the nearest node from the query point forwards the query to other nodes which is close to the query point and the query replies Which is received on each node with the information on itself. In this process, here we adopt two different methods: the Explosion (EXP) method and the Spiral (SPI) method. In the EXP method, the node which is nearest from the query point floods the query to nodes within a circular region and the each receiving node with the query replies has information on itself. In the SPI method, the node which is nearest from the query point forwards the query to other nodes in a spiral manner and the node which collects a satisfactory kNN result will transmits the result to the query-issuing node. Experimental results show that our proposed methods to achieve high accuracy and to reduce traffic of the query result, in comparison with the existing methods.

Keywords MANETs, kNN query, locations-based service

1. INTRODUCTION

   Mobile Computing is a technology that allows transmission of data, voice and video via a computer or any other wireless enabled device without having to be connected to a fixed physical link. This tutorial will give an overview of Mobile Computing and then it will take you through how it evolved and where is the technology headed to in future along with the classifications and security issues involved.

   In LBS, a node issuing of k Nearest Neighbor (kNN) queries will proceed on the k nearest neighbors (kNNs) in search of information from the specified location which is known as query point. Many in-network processing techniques for kNN queries have been proposed for wireless sensor networks (WSNs). In mobile ad hoc networks (MANETs), the provision of quality of service (QoS) guarantees is much more challenging mainly due to node mobility and resource constraints. Therefore it is important that routing protocols incorporate QoS metrics in route finding and maintenance to support end-to-end QoS. Many revisions are done to the KNN based existing protocol to meet QoS challenges focused on bandwidth, end to end delay, Packet delivery ratio, energy and mechanism overheads.

   However, MANETs there is some good characteristics about MANET such as dynamic topology change due to the mobility of mobile nodes and limitations on network bandwidth. When messages exchanged frequently between the nodes in order to know the changing locations of near neighboring nodes accurately such as the traffic increases and this causes frequent loss of packet resulting decrease in the accuracy of the query result.

   Hence , it becomes very necessary for MANETS to have an efficient routing and QoS mechanism to support various application. So we proposed this protocol based on location based forward aware routing (LBFAR) algorithm, which having issues.

2. BACKGROUND STUDY AND RELATED

   WORK

   kNN query processing method, it is important to appropriately estimate the range that includes kNNs. While the range could be estimated based on the node density in the entire network, it is not always appropriate because the density of nodes in the network is not uniform. In this paper, we propose two kNN query processing methods in MANETs where the density of nodes is ununiform; the One-Hop (OH) method and the Query Log (QL) method. In the OH method, the nearest node from the point specified by the query acquires its neighbours location and then determines the size of a circle region (the estimated kNN circle) which includes kNNs with high probability.

   In the QL method, a node which relays a reply of a kNN query stores the information on the query result for future queries. We proposed a kNN query processing method, the Explosion (EXP) method, which can reduce traffic and also maintain high accuracy of the query result in MANETs. In the EXP method, the query-issuing node first transmits a kNN query using geo-routing to the nearest node from the query point (the global coordinator). Then, the global coordinator floods the kNN query to nodes within a specific circle region (the estimated kNN circle) whose center is the query point, which looks like a query message that explodes at the global coordinator. Each node that received the query replies with the information on itself to the global coordinator, and the global coordinator sends back kNNs to the query-issuing node. It is very important to appropriately determine the size of the estimated kNN circle because it directly affects performance. If the estimated kNN circle is set too small,

   the information of all kNNs may not be acquired because there may be less than k nodes within the estimated kNN circle. On the other hand, if the estimated kNN circle is set too large, unnecessary traffic increases because nodes that are not included in the result of the kNN query reply with their information. In the EXP method, the estimated kNN circle is determined based on the density of nodes in the entire MANET. However, in a real environment, it is not always easy to know the total number of nodes in the entire MANET and the area size beforehand. Moreover, since the density of nodes is generally not uniform in a MANET, the estimated kNN circle, which is set based on the density in the entire area, is not always appropriate.

   Fig 2.1 EXAMPLE OF KNN QUERY IN A MANET.

   We also explain some experimental results to verify that our proposed methods can reduce traffic compared with the EXP method and also achieve high accuracy of the query result.

   The contributions of this paper are as follows:

   • Since the network bandwidth and batteries of mobile nodes are limited in MANETs, it is very important for kNN query processing to reduce unnecessary query messages and replies (i.e., traffic) as much as possible

   • We propose two effective kNN query processing methods the Explosion method and the spiral method) for reducing traffic and also maintaining high accuracy of the query result.

     The performance of these methods is affected by several factors such as k and network topology. Thus, by adaptively choosing one of the two methods, we can adapt to various system situations.

   • Through extensive simulations, we show that our proposed methods work very well in terms of both traffic reduction and high accuracy of the query result.

   Fig 2.2 (a)EXPLOSION METHOD (b)SPIRAL METHOD

3. EXIXTING METHOD

   Many strategies have been proposed for processing kNN queries in WSNs Here, we focus on the most relevant existing studies on WSNs involving features similar to MANETs, such as wireless communication and multi-hop relaying, and discuss the differences in our approach.

   1. Research issues

      Location-based services, such as kNN calculation have been addressed in many existing works in various types of networks except for MANETs. Most of the works assume that central servers calculate the answers, and focus on designing fast algorithms. As there is no centralized server in MANETs, existing query processing metods based on a centralized server are not applicable to MANETs. In this section, we describe three research issues for processing location-specific queries including kNN queries in MANETs.

   2. Traffic Reduction

      In MANETs, since nodes communicate using wireless links where the network bandwidth is limited, the increase of query messages and replies (i.e., traffic) makes packet losses. If packet losses often occur during query processing, the query-issuing node cannot acquire necessary information (i.e., information in an answer set of query processing),which results in decrease of accuracy of the query result. location information on all the nodes. However, many unnecessary replies that are not included in the query result (kNNs or vertices of the convex hull) are sent back to the query-issuing node, and thus, the traffic increases. We should avoid acquiring information on all nodes in the network, since it is a wasteful use of network bandwidth and batteries of the mobile nodes and also may degrade the accuracy of the query result due to packet losses. Therefore, we need to design query processing methods for reducing traffic while preserving the high accuracy of query results.Our approach is as follows queries are selectively transmitted only to the nodes that have the information (and data items) included in the query result, and the nodes receiving the query accurately prune unnecessary information based on their own information, the query expression (e.g., the size of the search range), and replies from other nodes.

   3. Query Processing without Using Beacons

   Many in-network processing techniques for kNN queries and boundary detection have been proposed for wireless sensor networks (WSNs) where sensor nodes are stationary or location-aware. For example, in [19, 74, 78],the authors proposed kNN query processing methods which are efficient in retrieving kNN information on the fly with low message overhead (traffic) since they do not require the maintenance of indexing structures like R-tree. In their methods, location aware environments are assumed, e.g., mobile nodes must periodically transmit beacon messages (including the location of the sender) to their neighbors to announce changing locations of nodes. As described above, MANETs possess notable characteristics, such as limitations on network bandwidth, and highly dynamic topology change due to the movement of mobile nodes. When nodes frequently exchange beacon messages to accurately know changing locations of neighboring nodes, traffic increases, and this causes frequent packet losses, resulting in lower accuracy of the query result. On the other hand, when nodes do not frequently exchange beacon messages, traffic is reduced, but nodes cannot accurately know the neighboring nodes locations, which also decreases the accuracy of the query result.

4. PROPOSED METHOD

   Here the authors proposed kNN query processing methods in location aware sensor networks based on the query propagation method proposed . In the authors proposed an infrastructure-free kNN query processing method called DIKNN. This method consists of three phases; routing phase, kNN boundary estimation phase, and query dissemination phase. In this method, first a sink node sends a query message to the nearest node from the query point.

   The information on the density of

   nodes is collected during the query transmission. The nearest node to the query point estimates the kNN boundary which represents a search range, based on the information on the density of nodes, and partitions the area inside the kNN boundary into sectors. In each sector, a sensor node collects partial results (the information on the nodes within the nodes communication range) and propagates the query to the next node in the sector according to a well-devised itinerary structure Finally, the partial results are individually sent back from each sector to the query-issuing node, enabling the query-issuing node to acquire kNNs. In the authors proposed an infrastructurefree kNN query processing method, called PCIKNN, which consists of the same phases as DIKNNs. This method also sets the kNN boundary and partitions it into sectors.With respect to each sector, a sensor node collects partial results along a well-devised itinerary structure, and then, the last node on the itinerary in each sector sends back the information on the nodes in each sector to the nearest node from the query point. .After the nearest node from the query point receives the information

   on the nodes in all sectors, it aggregates the partial results and sends them back to the query-issuing node.

   In DIKNN and PCIKNN, by partitioning the search range (i.e., the area inside the kNN of query execution can be reduced even if the search range is large.

5. GEO-ROUTING

   In various network research fields, many studies on geo- routing have been conducted Because our proposed methods use geo-routing, we present typical existing geo- routing protocols.In this the authors proposed GPSR which is a geo-routing method in wireless networks.

   In this method, a node that received a message forwards the message to the nearest node from the query point among its neighboring nodes. In addition, when a node has no closer node from the query point than itself, the query makes detour in order to avoid an obstacle and a network hole.

   Therefore, this method enables a message to reach the query point even in the case that a relaying node cannot find any nodes closer to the query point than itself. In this the authors proposed GOAFR which is a geo-routing method in MANETs. This method is similar to GPSR but is more adaptive to the worst case such as the case that a relaying node has no closer node.

   These methods assume the environment where a node knows its neighboring nodesinformation by broadcasting beacon messages including its location information, and thus, a node can directly forward (unicast) a message to a specific node using that information. However, in MANETs, since the network topology dynamically changes due to the movement of mobile nodes, each node has to frequently exchange beacon messages.

   A geo-routing method for reducing unnecessary transmission of messages in MANETs. In their method, when a node that received a message is closer than the sender node from the query point, it re-broadcasts the message. Since their method produces multi-paths, the traffic for routing increases.

   1. Geo-routing for Forwarding a Query

      To dynamically construct a route to the query point, we extend a beacon-less geo-routing

      method proposed in to avoid the construction of multiple routes to forward messages.Our geo-routing method adopts a three-way handshake protocol to enable a given node to find the node nearest to the query point among its neighboring nodes, and then send a query to this node. By repeating this procedure, the query is forwarded to the global coordinator.Specifically, in our geo-routing method, first the query-issuing node broadcasts a neighbor search message. When a node receives this message, if it is closer to the query point than the source node, and within the neighbor search range which is a circular region centered on the source node (discussed below), it stores the ID of the

      source node as the parent node and sets the waiting time t

      for sending a reply, according to the following equation:

   2. Geo-routing for Forwarding a Query

      To dynamically construct a route to the query point, we extend a beacon-less geo-routing method proposed to avoid the construction of multiple routes to forward messages.Our geo-routing method adopts a three-way handshake protocol to enable a given node to find the node nearest to the query point among its neighboring nodes, and then send a query to this node. By repeating this procedure, the query is forwarded to the global coordinator. Specifically, in our geo-routing method, first the query- issuing node broadcasts a neighbor search message.

      When a node reeives this message, if it is closer to the query point than the source node, and within the neighbor search range which is a circular

      region centered on the source node, it stores the ID of the source node as the parent node and sets the waiting time t for sending a reply, according to the following equation:

      Fig 5.1 QUERY PROCESSING IN EXPLOSION METHOD

6. REFERENCES

1. Ference, G., Lee, W.-C., Jung, H.-J., and Yang, D.-N.: Spatial search for K diverse-near neighbors, in Proc. of Intl Conf. on Information and Knowledge Management (CIKM), pp. 1928 (2013).

2. Fu, T.-Y., Peng, W.-C., and Lee, W.-C.: Parallelizing itinerary- based KNN query processing in wireless sensor networks, IEEE Trans. on Knowledge and Data Engineering (TKDE), Vol. 22, No. 5, pp. 711729 (2010).

3. Fujii, T., Kaji, M., Sasaki, Y., Hara, T., and Nishio, S.: A flooding control method with ack-carry for location-based information dissemination in mobile ad hoc networks, in Proc. of Intl

   Symposium on Applications and the Internet (SAINT), pp. 128 135 (2011).

4. Gao, Y., Zheng, B., Chen, G., Lee,W.-C., Lee, K. C., and Li, Q.: Visible reverse knearest neighbour query processing in spatial databases, IEEE Trans. on Knowledge and Data Engineering (TKDE), Vol. 21, No. 9, pp. 13141327 (2009).

5. Gao, Y., Zheng, B., Chen, G., and Li, Q.: Algorithms for constrained k-nearest neighbor queries over moving object trajectories, Geoinformatica, Vol. 14, No. 2,pp. 241276 (2010).

6. Hagihara, R., Shinohara, M., Hara, T., and Nishio, S.: A message processing method for top-k query for traffic reduction in ad hoc networks, in Proc. of Intl Conf. on Mobile Data Management (MDM), pp. 1120 (2009).

7. Hamida, E. B.,and Chelius, G.: A line-based data dissemination protocol for wireless sensor networks with mobile sink, in Proc. of Intl Conf. on Communications (ICC), pp. 22012205 (2008).

8. Hara, T., and Madria, S. K.: Consistency management strategies for data replicationin mobile ad hoc networks, IEEE Trans. on Mobile Computing, Vol. 8, No. 7, pp. 950967 (2009).

9. Heissenb¨uttel, M., Braun, T., Bernoulli, T., and W¨aLchli, M.: BLR: Beaconless routing algorithm for mobile ad hoc networks, Computer Communications, Vol. 27, No. 11, pp. 10761086 (2004).

10. D.J. Baker, J. Wieselthier and A. Ephremides, A Distributed Algorithm for Scheduling the Activation of Links in a Self- Organizing, Mobile, Radio Network, Proc. IEEE ICC, 1982, pp. 2F6.12F6.5.

11. J. Broch, D.A. Maltz, D.B. Johnson, Y.C. Hu and J. Jetcheva, A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols, Proc. Int. Conf. on MobiCom, 1998, pp. 159164.

12. T. Camp, J. Boleng and V. Davies, A Survey of Mobility Models for Ad Hoc Network Research, Wireless Communications and Mobile Computing 2(5) (2002), 483502.

13. M. Demirbas and H. Ferhatosmanoglu, Peer-to-Peer Spatial Queries in Sensor Networks, Proc. Int. Conf. on Peer-to-Peer Computing (2003), 3239.

14. T.Y. Fu, W.C. Peng and W.C. Lee, Parallelizing Itinerary-Based KNN Query Processing in Wireless Sensor Networks,IEEE Transactions on Knowledge and Data Engineering 22(5) (2010), 711729.

15. Y. Gao, B. Zheng, G. Chen and Q. Li, Algorithms for Constrained K-Nearest Neighbor Queries over Moving Object Trajectories, GeoInformatica 14(2) (2010), 241276.

16. T. Hara and S.K. Madria, Consistency Management Strategies for Data Replication in Mobile Ad Hoc Networks, IEEE Transactions on Mobile Computing 8(7) (2009), 950967.

17. M. Heissenbüttel, T. Braun, T. Bernoulli and M. Walchli, BLR: Beacon-Less Routing Algorithm for Mobile Ad-HocNetworks, Computer Communications 27(11) (2004), 10761086.

18. P.P. Jayaraman, A. Zaslavsky and J. Delsing, Cost-Efficient Data Collection Approach Using K-Nearest Neighbors in a 3D Sensor Network, Proc. Int. Conf. on Mobile Data Management, 2010, pp. 183188.