聚合容量的上限优化

本节计算type-sensitive DPC-AFs和type-threshold DPC-AFs在随机扩展网中的聚合容量上界。

（1）针对Type-Sensitive DPC-AFs的容量上界

定理6.4

在RE-WSN中针对type-sensitive DPC-AFs的聚合容量的阶。

证明　根据引理6.2，在任意的聚合路由树当中，以高概率存在一条长度为的边，记为uv，在这条边的容量上界为

其中，κ1＞0是个常数。根据type-sensitive DPC-AFs的属性，完成来自所有传感器上的N轮测量值的聚合需要经过个传输，其中，κ2＞0是个常数（其具体取值不影响最终结果的阶）。通过一个类似于引理6.3的证明过程，可以得到网格中的每个格子至少要进行κ3logn次传输，其中，1/2＜κ3＜8。因为一般物理模型下arena-bounds的阶为O（logn）[69，71]，则κ3logn个传输汇聚到μ个接收点时，其总速率阶为O（μ（logn）-α/2），其中，μ=O（logn）。对任意聚合树，考虑中的格子，从最远（跳数距离）的格子到包含sink的格子一定存在一种情况是μ=Θ（1），因为所有数据必须汇聚到sink节点上。在这种情况下，κ3logn个传输共用O（（logn）-α/2）阶的总速率，且需要完成聚合时间为。因此，聚合容量的上界为

（2）针对Type-Threshold DPC-AFs的容量上界(www.xing528.com)

定理6.5

在RE-WSN中针对type-threshold DPC-AFs的聚合容量的阶。

证明　对于type-threshold DPC-AFs，通过类似于定理6.4的过程并根据[93]中的定理4，当每个传感器产生N轮测量值时，网格中的格子必须进行至少κ5N log logn次传输，其中，κ4，κ5＞0是两个常数。从而，存在一层其聚合需要时间至少为

结合考虑下界（定理6.2及定理6.3）和上界（定理6.4及定理6.5），有

定理6.6

在RE-WSN中针对type-sensitive DPC-AFs和type-threshold DPC-AFs的聚合容量的阶分别为。