Approximate multiple count in Wireless Sensor Networks

COUNT is a typical aggregation operation in Wireless Sensor Networks (WSNs). In such an operation, the total number of the items which are of the same kind is obtained and only one numerical value is returned as the result. This paper identifies the multiple count problem which counts items belonging to multiple categories. For each category, the total number of the items belonging to this category is calculated. Therefore, the returned result is a set of values instead of a single value. The multiple count problem is more challenging than the traditional count problem as the former incurs more communication overhead. This paper proposes a distributed approximate multiple count algorithm which can derive an error bounded result under a specified communication cost constraint for each node. The error of the derived result is hN/L, where h is the depth of the routing tree, N is the total number of all the items belonging to all the categories, and L is a representation of the communication cost constraint for each node. Furthermore, the weighted multiple count problem is investigated where different kinds of items to be counted have different weights. The proposed algorithms are evaluated through TOSSIM, a widely used simulation tool for WSNs. The theoretical analysis and simulation results both demonstrate the correctness and effectiveness of the proposed algorithms.