K-Nearest Neighbor Based Missing Data Estimation Algorithm in Wireless Sensor Networks
- 1
- 2
Abstract
In wireless sensor networks, the missing of sensor data is inevitable due to the inherent characteristic of wireless sensor networks, and it causes many difficulties in various applications. To solve the problem, the missing data should be estimated as accurately as possible. In this paper, a k-nearest neighbor based missing data estimation algorithm is proposed based on the temporal and spatial correlation of sensor data. It adopts the linear regression model to describe the spatial correlation of sensor data among different sensor nodes, and utilizes the data information of multiple neighbor nodes to estimate the missing data jointly rather than independently, so that a stable and reliable estimation performance can be achieved. Experimental results on two real-world datasets show that the proposed algorithm can estimate the missing data accurately.
- D. E. Cullar, D. Estrin, and M. Strvastava, “Overview of sensor networks,” IEEE Computer, Vol. 37, No. 8, pp. 41–49, 2004.
- W. F. Fung, D. Sun, and J. Gehrke, “Cougar: the network is the database,” In SIGMOD Conference, pp. 621, 2002.
- S. Madden, M. J. Franklin, J. M. Hellerstein, and W. Hong, “The design of an acquisitional query processor for sensor networks [C],” In SIGMOD. San Diego, Califor- nia, 2003.
- Y. Yao and J. Gehrke, “The cougar approach to in- network query processing in sensor networks,” In SIGMOD Record, Vol. 31, No. 3, pp. 9–18, 2002.
- G. Tolle, “Sonoma redwoods data,” 2005. http://www.cs. berkeley.edu/~get/sonoma/.
- S. Madden, “Intel Berkeley research lab data,” 2003. http://berkeley.intel-research.net/labdata.
- X. Zhu, S. Zhang, J. Zhang, and C. Zhang, “Cost- sensitive imputing missing values with ordering,” In AAAI. Vancouver, Canada, pp. 1922–1923, 2007.
- N. A. Setiawan, P. A. Venkatachalam, and A. F. M. Hani, “Missing attribute values prediction based on artificial neural network and rough set theory,” In BMEI. Sanya, Hainan, China, pp. 306–310, 2008.
- M. S. B. Sehgal, I. Gondal, L. Dooley, and R. L. Coppel, “Ameliorative missing value imputation for robust biological knowledge inference,” Journal of Biomedical Informatics, Vol. 41, No. 4, pp. 499–514, 2008.
- M. S. B. Sehgal, I. Gondal, and L. Dooley, “Collateral missing value imputation: A new robust missing value estimation algorithm for microarray data,” Bioinformatics, Vol. 21, No. 10, pp. 2417–2423, 2005.
- H. Kim, G. H. Golub, and H. Park., “Missing value estimation for dna microarray gene expression data: local least squares imputation[J],” Bioinformatics, Vol. 22, No. 11, pp. 1410–1411, 2006.
- O. G. Troyanskaya, M. Cantor, G. Sherlock, P. O. Brown, T. Hastie, R. Tibshirani, D. Botstein, and R. B. Altman, “Missing value estimationmethods for dna microarrays,” Bioinformatics, Vol. 17, No. 6, pp. 520–525, 2001.
- C. Zhang, X. Zhu, J. Zhang, Y. Qin, and S. Zhang, “Gbkii: An imputation method for missing values,” In PAKDD. Nanjing, China, pp. 1080–1087, 2007.
- S. Zhang, J. Zhang, X. Zhu, Y. Qin, and C. Zhang, “Missing value imputation based on data clustering,” Transactions on Computational Science, Vol. 1, No. 1, pp. 128–138, 2008.
- A. Manjhi, S. Nath, and P. B. Gibbons, “Tributaries and deltas: efficient and robust aggregation in sensor network streams,” In SIGMOD Conference. Baltimore, Maryland, pp. 287–298, 2005.