Continuous K-Means Monitoring with Low Reporting Cost in Sensor Networks

In this paper, we study an interesting problem: continuously monitoring k-means clustering of sensor readings in a large sensor network. Given a set of sensors whose readings evolve over time, we want to maintain the k-means of the readings continuously. The optimization goal is to reduce the reporting cost in the network, that is, let as few sensors as possible report their current readings to the data center in the course of maintenance. To tackle the problem, we propose the reading reporting tree, a hierarchical data collection, and analysis framework. Moreover, we develop several reporting cost-effective methods using reading reporting trees in continuous k-means monitoring. First, a uniform sampling method using a reading reporting tree can achieve good quality approximation of k-means. Second, we propose a reporting threshold method which can guarantee the approximation quality. Last, we explore a lazy approach which can reduce the intermediate computation substantially. We conduct a systematic simulation evaluation using synthetic data sets to examine the characteristics of the proposed methods.