机制Me下的混合网络组播链路负载和吞吐量优化

混合机制可以进一步分为两种类型：连通机制和渗流机制。

（1）连通机制

首先要说明，在ρ=O（n/logn）时，连通机制有效。本书记针对扩展网的连通机制为，记其路由和传输机制分别为。连通机制是依据机制网格（定义3.7）（其中的格子称为连通格子）设计的，其中=2θ·logn且θ是一个满足条件θ＞1/（2log2-log e）的常数。进一步将每个格子水平（或垂直）等分为两个部分，称为半格，如图5-3所示。从而，运用引理3.2，可以证明每个半格中的节点数目以高概率为。

路由机制：基于每个，运用类似算法3.1的方法构造得到一个，1≤ι≤φk。并在每个区域中以图5-3的方式构造水平并行连通路径（Horizontal Parallel Connectivity Path）和垂直并行连通路径（Vertical Parallel Connectivity Path）。

传输调度机制：采用一个9-TDMA机制调度连通路径。把每个时隙等分4个子时隙，调度每个连通格子对应的4个半格。这里的调度机制（图5-4）类似于第3章的并行调度机制。

类似于引理3.17的方法，则得到：

引理5.3

运用并行调度机制，每条连通路径容量可达Ω（（logn）-α/2）。

机制下的吞吐量：首先，主要依据引理5.2，给出每条连通路径的负载。

图5-3　构造连通路径

图5-4　连通路径的并行调度机制

引理5.4

在机制下，每条连通路径的负载至多为

从而，结合引理5.3和引理5.4，有以下结论：

定理5.3

当ρ=O（n/logn）时，在机制下，不考虑可能位于基站的瓶颈的情况，网络的组播吞吐量

下面考虑可能位于基站的瓶颈。在机制下，所有位于子区域Sι中的源节点，只要其目的节点中存在一个点在Sι之外，就需要将该源节点产生的数据传输给基站bι。从而，当源节点数目超过一定的值，基站可能成为整个系统的瓶颈。运用类似于引理5.4的方法，则得到：

引理5.5

在机制下，基站和一般ad hoc节点之间的链接（B-O链接）的负载至多为

根据引理5.3，则有：

引理5.6

在机制下，经过B-O链接的吞吐量为

结合定理5.3和引理5.6，得出机制的瓶颈位于B-O链接。最后，得到连通机制的可达吞吐量。

定理5.4

在机制下，混合扩展网的组播吞吐量为

当m：[1，n/logn]时，

当m：[n/logn，n]时，

（2）渗流机制

首先要说明，在ρ=O（n/（logn）2）时，渗流机制有效。本书记针对扩展网的渗流机制为Me，记其路由和传输机制分别为。渗流机制是依据机制网格（定义3.7）（其中的格子称为渗流格子）设计的。从而，每个渗流格子是开（open）的概率为。运用类似于[68]中的方法构造高速公路：将部署区域分成大小为的长方块（称之为高速公路块），其中，，通过调整使得为整数。从而，类似于引理3.14，我们有：

引理5.7

对任意κ＞0和ae＞log6+2/κ，存在一个常数δ1=δ1（κ，ae）使得以高概率保证每个高速公路块中至少包含δ1logn条高速公路。

基于引理5.7，可以把每个水平（垂直）高速公路块等分为大小的高速公路条，其中，κ5=δ1/（2κ）是一个常数。可以定义从高速公路集合到条的集合之间的一个映射。换句话说，可以保证每个条中产生的流量将由对应的高速公路来负责，且每条高速公路至多负载一个高速公路条的流量。

路由机制：基于每个，1≤ι≤φk，用两个阶段来实现每条边之间的路由：连通路径阶段和高速公路阶段。具体的方法类似于算法3.2，需要指出，这里的连通路径类似于第3章中的二级高速公路，二者构造方法不同，但可以达到相同的速率和密度。(www.xing528.com)

传输调度机制：采用两个独立的TDMA机制调度高速公路和连通路径。将调度周期等分为两个部分，分别称为高速公路调度和连通路径调度。其中，可用[68]中对高速公路的调度方法，从而，有高速公路的速率可达Ω（1）。

因为只能保证至少有一条连通路径，而不是高速公路，经过特定基站bι，因此类似于连通策略，则有：

引理5.8

在机制Me下，经过B-O链接的吞吐量为，其中，的定义在引理5.6。

关于调度机制，我们可以采用，从而根据引理5.3，则有：

引理5.9

在调度机制下，连通路径的速率可达Ω（（logn）-α/2）。

机制Me下的吞吐量：首先，分为高速公路和连通路径的负载。

引理5.10

在机制Me下的高速公路阶段，高速公路的负载为

证明　给定高速公路上的一点，定义在高速公路阶段经过的组播会话数量为。将考虑的一致上界。定义一个事件：组播会话在高速公路阶段经过点。显然，如果发生，则存在一条边其路由在高速公路阶段经过点；也就是说，存在一条经过的垂直（或水平）线与uiui，j（或ui，juj）相交，其中，pi，j为经过ui的水平线和经过uj的垂直线的交点，ui，j是离pi，j最近的节点。则有：

其中，κ5～κ8是常数。因此，的一个上界，记为ηt，服从Poisson分布，其参数为

因此，得证在高速公路阶段，高速公路上点的负载为。从而证得引理。

则有：

引理5.11

在机制Me下的高速公路阶段，网络组播吞吐量可达：

引理5.12

在机制Me下的连通路径阶段，连通路径的负载为=O（nd（logn）1/2）。

结合引理5.9和引理5.11，则有：

引理5.13

在机制Me下的连通路径阶段，网络组播吞吐量可达：

依据引理5.11和引理5.13，得到以下定理。

定理5.5

当ρ=O（n/（logn）2）时，在渗流机制Me下，不考虑可能位于基站的瓶颈的情况，混合扩展网络的组播吞吐量可达：

当ρ：[1，n/（logn）α+1]，

当ρ：[n/（logn）α+1，n/（logn）2]，

根据引理5.8和定理5.5，得到以下结果。

定理5.6

在渗流机制Me下，混合扩展网络的组播吞吐量可达：

当m：[1，n/logn]，

当m：[n/logn，n]，

最后，结合定理5.4和定理5.6，得到混合扩展网在混合机制下的吞吐量可达（定义见定理5.6）。