Paper Info
Title
Approximate multiple count in Wireless Sensor Networks
Abstract
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.
Year
DOI
Venue
2014
10.1109/INFOCOM.2014.6848082
INFOCOM
Keywords
DocType
ISSN
routing tree,trees (mathematics),approximation theory,distributed approximate multiple count algorithm,approximate multiple count,aggregation operation,wireless sensor networks,telecommunication network routing,communication cost constraint,TOSSIM
Conference
0743-166X
Citations 
PageRank 
References 
0
0.34
0
Authors
4
Name
Order
Citations
PageRank
Xiaolin Fang1747.27
Hong Gao21086120.07
Jianzhong Li33196304.46
Yingshu Li467153.71