多Sink方式提升网络聚合吞吐量

根据定理6.1、定理6.2和定理6.3，得知即使引入block coding技术，系统瓶颈仍然是在局部聚合阶段。更为具体地说，每个局部同位图的大小（顶点数目）都太大。从而开始考虑如何减小这种局部同位图的大小以提高网络吞吐量。为此，引入并行调度技术[80]。

（1）并行聚合机制

根据引理6.3，L1中的格子包含的节点数目范围为（logn/2，8logn）。因此，直观地看，从每个格子中随机选取logn/2个节点作为站点，则在L1的每行（列）中将可以构建logn/2条聚合骨干。然而，每条骨干的速率不会超过机制AN，n下骨干速率。因此，可尝试同时调度多条骨干上的链接，且保持速率为Ω（（logn）-α/2）。记这种新的机制为。与AN，n类似，机制也是分为两个阶段：局部聚合阶段和骨干聚合阶段，且骨干聚合阶段可进一步分为水平骨干和垂直骨干阶段。

骨干聚合阶段：记L1中格子Ci，j里的聚合站点为bi，j（ι），1≤ι≤。从而，可用图6-5所示的方法来构造水平骨干：

图6-5　并行聚合骨干

●当i为偶数时，对所有的j为偶数的站点bi，j（ι），一对一连接起来。

●当i为奇数时，对所有的j为奇数的站点bi，j（ι），一对一连接起来。

与之类似，可以在第δ-1列和第δ列构造垂直骨干。注意，不是所有的格子中，都设立站点。

为了描述方便，不失一般性，假设δ是偶数。在水平骨干聚合阶段，数据将被聚合到两列中的站点上；在垂直骨干聚合阶段，数据将被聚合到格子Cδ-1δ-1和Cδ，δ中的站点上。当δ为奇数时，数据最终将聚合到格子Cδ-1δ和Cδ，δ-1中。

现在，关键的问题是如何调度聚合骨干以提高骨干总速率。采用一个4-TDMA机制调度水平骨干，记为，其中一个调度单元由2×4个格子组成，如图6-6（a）所示。因为每个调度单元中只有4个格子需要被调度，因此需要4个调度时间片来完成一次调度。与之类似，可采用另一个4-TDMA机制，记作，来调度垂直骨干，如图6-6（b）所示。对于，关键的技术是允许logn/2个站点同时被调度以使得骨干总速率得到提高。

运用类似于引理3.17的证明方法，可以得到：

引理6.14

在调度机制（或）下，每条水平（或垂直）骨干的速率都可达到Ω（（logn）-α/2）。

骨干聚合阶段：先讨论如何有效率地将测量值收集到站点上来。仍旧将一个调度单元定义为一个2×4的格子集合，如图6-6（a）所示。具体来讲，用Uh，v来表示一个调度单元，其由格子

（如果存在）组成。从而，并行路由和调度机制可以如下描述（为了简化描述，令表示在调度时间片t0-t1中，所有来自格子Ci，j中点的测量值均匀地聚合到格子Ck，l中的个站点上）：调度中的所有链接需要时间为128个调度时间片。

图6-6　并行聚合骨干调度

在以上的调度机制中，每个链接的长度为。根据引理6.14，可以同时调度logn/2个站点，且保证每条边的速率保持在Ω（（logn）-α/2）。另一方面，调度所有从一个格子中的点到另外一个格子中的站点的链接，需要的时间至多为16个调度时间片。

（2）并行聚合机制下的聚合吞吐量

首先，对于局部聚合阶段，则有：(www.xing528.com)

引理6.15

在并行聚合机制下，完成N轮测量值的局部聚合所需的时间为

下面，来考虑骨干阶段。在并行机制下，对所有i，j，ι，记bi，j（ι）及其所有后继的集合为；对所有i，ι和j=δ-1，δ，记bi，j（ι）及其所有后继的集合为。因为有个站点分担每个格子的负担，因此有：

从而，在水平和垂直骨干阶段，第k轮测量值在站点bi，j（ι）上产生的负载为

进一步定义

运用类似于引理6.9和引理6.11的证明过程，则有：

引理6.16

在并行聚合机制下，完成N轮测量值的骨干聚合所需的时间为

结合引理6.15和引理6.16，则有：

定理6.7

在并行聚合机制下，设定N=，将测量值聚合在无穷小比例（即，）的区域中的Θ（logn）个sink节点上，可达吞吐量为

对于DPC-AFs，吞吐量可达Λ（n）=Ω（（logn）-α/2）。

（3）结论的相关含义

缓解干扰限制（Interference-limitedness）：根据引理6.2，任意的聚合树中，都以高概率存在一条长度为的边，由于能量限制（powerlimitedness），边的速率为O（（logn）-α/2）。根据定理6.7，这个上界实际上通过从一个相对无穷小的区域内随机选取Θ（logn）个传感器作为sink节点得以达到。

多sink节点的增益：通过增加sink可以提升系统吞吐量，这是显而易见的。这里，我们讨论以下两个问题：

1）为什么不直接从整个部署区域随机选取传感器作为sink节点？原因有两个方面：①通常来讲，每个sink节点要通过一个可靠链接连接到一个处理站点（比方说计算机），且需要保证稳定的能源供给。从而，将sink节点部署在较小的区域内，对于整个网络的管理和部署来讲，会更加方便。②从整个部署区域随机选取传感器作为sink节点实际上并不能提高系统吞吐量的阶。一个直观的解释是：将网络等分为Θ（logn）个子区域，然后从每个区域内随机选取一个传感器作为sink节点来负责本子区域的数据汇集。通过这种方法不能增加吞吐量的阶，因为子区域的面积为Θ（n/logn），其仍旧太大而不能缓解整个网络的瓶颈。

2）是否能够通过增加sink节点的数目来进一步提高系统的吞吐量？增加大量sink节点显然能够提高网络吞吐量。一个极端的例子便是所有的传感器都被作为sink节点。当然，这是不现实的。实际上，猜想当sink节点的数目限制在O（n/logn）的条件下，定理6.7中给出的吞吐量将是最优的（只需要设定Θ（logn）个sink节点）。