k Nearest Neighbor Search for Location Dependent Sensor Data in MANETs using ns2


K nearest neighbour (kNN) queries, which retrieve the k nearest sensor data items associated with a location (location-dependent sensor data) from the location of the query issuer, are useful for location based services in mobile environments. Here, we focus on the kNN query processing in mobile ad hoc networks (MANETs). Key challenges in designing system protocols for the MANETs include low-overhead adaptability to network topology changes due to node mobility, and query processing that achieves high accuracy of the query result without a centralized server. In this paper, we propose the Filling area (FA) method to efficiently process kNN queries in the MANETs. The FA method achieves low overhead in query processing by reducing a search area. In the FA method, data items remain at nodes near the locations with which the items are associated, and nodes cache data items whose locations are near their own so that the query issuer retrieves kNNs from nearby nodes. Through extensive simulations, we verify that our proposed approach achieves low overhead and high accuracy of the query result.


we introduce some existing studies on location-dependent data management in LBS and kNN query processing, which are somewhat related to our work.


In, the authors proposed a line-based data dissemination protocol for sensor networks. Sinks disseminate data items to nodes within a vertical virtual line which divides into two parts, and nodes search for data items there. 
This method does not assume kNN query processing and replication of location-dependent data. In the authors proposed the Skip-Copy method, specifically aimed at managing location-dependent data items in MANETs. 
This methods parsley distributes copies of location-dependent data items to increase data availability in a wide range. However, in this method, nodes access a single location-dependent data item, in contrast to our method s aim of acquiring multiple location-dependent data items near a specific point. 
In authors proposed a system to provide LBS which does not depend on pre-established infrastructure. The system uses a mobile agent that remains within a certain geographical area, moving among mobile nodes in the area. Our method is inspired from this approach in keeping data items within a specific region.


Bandwidth Constraints

The bandwidth of the wireless links is always much lower than in wired counterparts. Indeed, several Gbps are available for wired LAN, while, nowadays, the commercial applicationsfor wireless LANs work typically around 2 Mbps.

Energy constraints

The power of the batteries is limited in all the devices, which does not allow infinitive operation time for the nodes. Therefore, energy should not be wasted and that is why some 
energy conservingalgorithms has been implemented.

High Latency

In an energyconserving design nodes are sleeping or idle when they do not have to transmit any data. When the data exchange between two nodes goes through nodes that are sleeping, the delay may be higher if the routing algorithm decides that these nodes have to wake up.



In, the authors proposed a method for efficiently acquiring kNNs from mobile query points. This method can reduce disk access search costs for databases, when the query point is moving and kNN results change. 
It assumes that the information of all static objects (such as hospitals or schools)has been previously obtained (i.e., a centralized method).In, the authors defined Continuous All k-Nearest Neighbour (CAkNN) queries which continuously identify all nodes closest neighbouring nodes, and proposed a `Proximity algorithm for efficiently processing such queries in smart phone networks. 
This algorithm only works well in areas covered by a set of network connectivity points(e.g., cellular towers for cellular networks).Moreover, each node must regularly report its positional information to the query processor, which is too costly in MANETs. 
In, the authors proposed a method to continuously monitor Knn sin a wireless sensor network. Here, sensors detect objects moving around the target region, and these sensors collaborate to continuously monitor the kNNs (k nearest objects) from the query point. However, since this method assumes that the sensors are statically deployed, it is not applicable to MANETs.


1. Router Free
Connection to the internet without any wireless router is the main advantage of using a mobile ad hoc network. Because of this, running an ad hoc network can be more affordable than traditional network.
2. Fault Tolerance
MANET supports connection failures, because routing and transmission protocols are designed to manage these situations.
3. Cost
MANET could be more economical in some cases as they eliminate fixed infrastructure costs and reduce power consumptions at mobile nodes.


                       KNN ALGORITHM



Operating System           :   Linux
Simulation Tool                          :    NS2
Documentation                :Ms-Office


CPU type                                  :    Intel Pentium 4
Clock speed                              :    3.0 GHz
Ram size                                   :    512 MB
Hard disk capacity                    :    80 GB
Monitor type                             :    15 Inch color monitor
Keyboard type                          :     Internet keyboard
CD -drive type                          :     52xmax


D. J. Baker and J.Wieselthier, ``A distributed algorithm for scheduling the activation of links in a self-organizing, mobile, radio network, in Proc. ICC, 1982, pp. 2F6.1_2F6.5.