大规模无线传感器网络(ε,δ)近似计数算法

(ε,δ)-approximate counting algorithm for large scale wireless sensor networks

研究了大规模无线传感器网络中的近似计数问题,提出2个基于数字二叉树(DBT,digital binary tree)协议的近似计数算法DBT-ACA和DBT-BACA。算法能够以O(loglog n)的时间复杂性返回(ε,δ)-精度保证的近似计数结果。DBT-BACA采用了二分搜索、逐层转发和延迟响应等技术,有效地减少了查询时间和数据通信量。理论分析和实验结果表明,提出的算法在近似结果的精准度、时间效率和能量开销等方面均优于现有的近似计数算法。

The problem of approximate counting for large scale wireless sensor networks was studied. Two approximate counting algorithms, DBT-ACA and DBT-BACA, based on DBT （digital binary tree） protocol were also proposed. The algorithms presented could attain the counting result in O（log log n）time while meeting the （ε,δ） accuracy requirement. DBT-BACA exploits binary search, level-by-level forwarding and delay response technique to effectively reduce the query delay and transmission cost. Theoretical analysis and experimental results show that the proposed algorithms out- perform existing approaches in terms of estimation accuracy, time efficiency and energy cost.