k- Nearest Neighbor Algorithm for Improving Accuracy in Clutter Based Location Estimation of Wireless Nodes

Abstract

This research is focusing on the precise location estimation of mobile node by using k - nearest neighbor algorithm (k-NN). It is based on our previous research findings in which we divided the geographical area into thirteen clutters/terrains based on the behavior of radio waves. We calculated the point-to-point distance from the antennas to mobile node by using receive signal strength and available signal strength information. A C# prototype was developed by using WiFi (IEEE 802.11 b/g standard) to record data points in different clutters at every 2 meter distance. We derived Clutter based Enhanced Error Rate Table (CERT) for precision. Although CERT minimizes errors due to the atmospheric considerations but in highly attenuated clutters the error rate was still high. The k-NN algorithm is used to minimize the error ranging from 1-3 meters to 0.4- 1.2 meter only, depending on the clutter we are dealing with. Current research is divided into three steps. First we calculate the P2P distance in all different clutters by using available signal strength and receive signal strength at five different time intervals (t0 – t4). In step 2 we construct three triangles at random by using the data gathered in step 1 and calculate mean value of predicted locations. Finally based on locations calculated in step 2 we apply the k-NN algorithm to minimize error in the estimated location. Results show that the k-NN can produce from 217% - 289% better results compare to the famous triangulation method. The purpose of this research is to reduce errors in order to achieve estimated position near to accurate.