随着大数据时代到来，数据中心承载着比以往更多的分布式计算任务，如分布式机器学习^[1]、MapReduce^[2]大数据处理任务等。这些应用在计算过程中需要传输大量数据同步计算结果，不仅导致应用自身存在末端拥塞问题^[3]，也持续占用大量网络带宽，影响其他任务的执行效率^[4-6]。

针对此问题，研究者提出在网计算的概念^[7-8]，即把一部分计算卸载到网络设备单元(如智能网卡，可编程交换机等)上完成，我们以图 1为例说明在网计算在分布式应用执行过程中起到的作用。

图 1(a)是一个简化的数据中心网络FatTree^[9]，架内的矩形框代表服务器，单词右侧数字代表其出现的次数。此时网络中正运行着一个统计单词“hello”数量的MapReduce任务，每台相关服务器需要将自己统计的结果发送给接收端机架D上的服务器做求和处理。

图 1(b)表示任务在网络中产生的汇聚树，阴影节点表示交换节点被选作计算节点(下文也称汇聚节点)，可对进入的数据包进行合并，虚线框是合并的结果。“/”前后数字分别代表不使用和使用在网计算技术边上经过的数据包数量。我们定义汇聚树的代价为其在网络中产生的数据量总和，则通过图中汇聚点2、3、5、8的聚合作用，总代价从原来的30减为13。

图 1(b)中的完全汇聚树是理想情况下的结果，即任务可以使用任意交换节点作为汇聚点使得每条边上经过的数据量等于1。此时求最小代价的汇聚树问题等价于斯坦纳树问题^[10]，无线传感器领域的信息收集^[11-12]，以及组播领域的组播树构造^[13-14]对此问题都有深入研究。本文的不同之处在于考虑了资源对汇聚树代价的影响，这包含两个方面。

一方面，交换节点的容量有限，以内存资源为例，由于到达交换节点的各条流存在时间差，节点需要为汇聚树预留内存保存中间结果^[15-16]，如果交换节点没有空闲内存使用，将只能作为转发节点将收到的所有数据包原封不动发往下一跳，此时汇聚树中只有部分交换节点可以起到汇聚的作用；另一方面，考虑在网计算作为服务提供给租户付费使用^[17]，租户可能只购买了少量资源，此时如何在交换节点上分配这些资源也是影响汇聚树代价的重要因素，如图 2(a)和2(b)，假如用户购买的资源只够使用2个汇聚点，则图 2(b)的分配方式能够产生的汇聚树代价更小。容易证明，在上述2个资源限制下为任务找出最小代价汇聚树是一个NP难问题。

定理 1  资源限制下的最小汇聚树问题(minimum aggregation tree with constrained resource, MATCR)是NP难问题。

证明  当任务可使用资源量和节点可使用资源量无限大时，任意交换节点都可以作为汇聚点，于是所有边上的数据量都为1，最小代价汇聚树问题就退化为在图中寻找斯坦纳树，这个问题已经被证明为NP-complete问题^[18]。由于此问题只是本文问题的特例，因此MATCR问题是NP难问题。□

文献[19]针对FatTree网络提出多播树的构造方法；文献[20-21]分别针对网络拓扑CamCube^[22]、BCube^[23]提出汇聚树的构造方法，但是都没有考虑资源对汇聚结果(树的代价)的影响。

文献[17]研究当已知汇聚树时汇聚点的选择问题，提出一个基于双层动态规划的算法SOAR，但是并没有给出汇聚树的构造方法，并且该方法只适用于单棵汇聚树的情况。

综上，本文的贡献在于提出一种在任意网络中构造(多棵)汇聚树的算法，同时还考虑了资源对于汇聚树代价的影响。

1 问题描述

表 1列出本文中出现的重点符号和变量，G表示原始物理拓扑(有向图)，总的节点集合N包含交换节点V和终端节点H。终端节点指的是可以接收或发送数据包的节点，发送端S和接收端r都属于此类节点。H中的节点只和V中的节点相连，H内部节点之间不相连。

T代表一次传输S→r形成的汇聚树(有向图)，发送端集合S是汇聚树的叶子节点，接收端r是根节点。一个任务往往包含多棵汇聚树，用上标k∈K区分不同的汇聚树，即T_k代表传输S_k→r_k形成的汇聚树。

本文假设在汇聚树中每个汇聚点上消耗的资源都是相同且已知的(单位1)，这类资源包括保存中间结果的内存资源^[15]、指示汇聚数据包下一跳的路由表条目^[24]等。对于使用多种资源的情况，只要这些资源的消耗不互相影响，模型里只需加入相应的约束即可。为简化分析，本文只考虑一种资源约束。由于一棵汇聚树在汇聚点上消耗的资源为单位1，所以节点上的剩余资源量m_i也可以理解为节点容量，即节点能同时容纳的汇聚树数量。任务消耗的总资源量不能超过可使用的总资源量M。

本文使用交换节点、转发节点、汇聚节点3种称呼区分汇聚树上的节点：一棵汇聚树除了发送端和接收端以外都是交换节点，交换节点不受资源限制，可以在网络中任取。只有当a(i)=1时，交换节点i才可以作为汇聚节点合并数据包，否则只能作为转发节点(即输入的数据量等于输出的数据量)。

汇聚树T_k在边e上经过的数据量为x^k(e)，一棵树的代价是其所有边上的数据量之和，本文的目标是最小化任务的所有汇聚树代价之和，即$\min \sum\limits_{k \in \mathscr{K}} \sum\limits_{e \in E} x^k(e)$。

2 单汇聚树的线性整数规划建模

这一节讨论任务只包含一棵汇聚树的情况，因此不涉及上标k的使用。单汇聚树的线性整数规划(linear integer programming，ILP)建模有2个关键部分，一是确定汇聚树经过的边，二是确定资源量的分配，即路径约束和资源约束。

2.1 流的路径约束

$\sum\limits_{e \in O(i)} y(e)=1, \forall i \in S,$

(1)

$\sum\limits_{e \in O(i)} y(e)-\sum\limits_{e \in I(i)} y(e)=0, \forall i \in V,$

(2)

$\sum\limits_{e \in I(r)} y(e)=|S|,$

(3)

$x(e) \leqslant y(e), \forall e \in E,$

(4)

$|S| \cdot x(e) \geqslant y(e), \forall e \in E \text {, }$

(5)

$\sum\limits_{e \in O(i)} x(e)-\sum\limits_{e \in I(i)} x(e)=1, \forall i \in S .$

(6)

定理1说明斯坦纳树问题只是本文的特例，所以并不能直接使用斯坦纳树问题的ILP模型^[10]，原因在于交换节点的输入、输出量之间存在多种情况。以图 3(a)为例，节点1和节点5作为汇聚节点，输入的数据量分别是2和4，而输出量只有1，流量不守恒；节点2、3、4作为转发节点，输入量等于输出量，流量守恒。然而交换节点的类型是资源分配结果a(i)决定的，于是路径约束和资源分配之间存在耦合，难以列出相关约束。

为此引入辅助汇聚树(图 3(b))，辅助汇聚树和实际的汇聚树(图 3(a))拓扑相同，但是没有汇聚节点对流起汇聚作用，设实际和辅助汇聚树边e上的流量分别为x(e), y(e)。辅助汇聚树可以看成从发送端集合S到接收端r的|S|条流的路径形成的汇聚树，所以容易写出路径约束(1)~(3)。这样y>0的边就构成了最终汇聚树的边，然后利用约束(4)(5)限制实际数据量x只经过这些边，就能保证辅助汇聚树和实际汇聚树经过相同的边。加入约束(6)是因为本文不考虑终端节点作为转发节点。

2.2 资源约束

$\sum\limits_{e \in O(i)} x(e)-\sum\limits_{e \in I(i)} x(e)+z(i)=0, \forall i \in V,$

(7)

$z(i) \leqslant|S| \cdot a(i), \forall i \in V,$

(8)

$z(i) \geqslant a(i), \forall i \in V,$

(9)

$a(i) \leqslant m_i, \forall i \in V,$

(10)

$\sum\limits_{i \in V} a(i) \leqslant M .$

(11)

容易看出，节点的输入输出量之间只存在2种情况：a(i)=0时，节点i为转发节点，流量守恒；a(i)=1时，节点i为汇聚节点，流量不守恒，但是输出量之和为1。因此，引入辅助变量z(i)和约束(7)~(9)，在不破坏模型的线性前提下区分这2种情况。

z(i)的作用原理解释如下：当a(i)=1时，约束(8)、(9)允许z(i)大于0，因为目标是最小化总代价，x(e)应尽可能小，所以在约束(7)中z(i)会尽可能地大，但是约束(5)又保证了节点i起码有一条出边e使得x(e)=1，所以z(i)最大为∑_e∈I(i)x(e)-1，因此z(i)可以理解为汇聚节点i消耗掉的流量。约束(9)还有一个作用是防止最后解中出现无效汇聚点，因为其要求a(i)=1时，节点一定消耗了流量(z(i)>0)，所以不会出现某个节点只有一条流进入但是却被指定为汇聚点，这种情况会出现在比如总资源量M很大时。当a(i)=0时，z(i)被约束(8)限制为0，此时约束(7)就是普通的流量守恒约束。

$\begin{aligned} & \min\limits _{a(i), y(e), x(e)} \sum\limits_{e \in E} x(e), \\ & \text { s.t. }(1)-(11) . \end{aligned}$

(P1)

约束(10)和(11)分别对应节点的容量限制以及总资源量约束，最终完整的最小代价汇聚树模型如(P1)所示。

2.3 提取流路径算法EXTRACTPATHS

在网计算的部署需要在交换节点上配置相应的路由项才能引导流到达汇聚节点进行合并，为此需要得到每条流的路径。

因为树状图中每个节点的父节点(即汇聚树中每个节点的下一跳)只有一个，所以大多数情况下，沿着x(e)>0的出边寻找就能确定每一条流的路径，但是当流的路径发生重叠，一个节点就会有2条出边：如图 4(b)所示，以发送端c、d为起点的流先到汇聚节点1，和a、b汇聚后再一起发送到接收端r，产生的代价会比直接到接收端r(图 4(a))产生的代价更小。虽然图 4(b)看上去有环路，但是经过节点3的实际是2条不同的流(见展开图 4(c))。

造成这个问题的根本原因在于模型(P1)是一个基于边的模型，其中变量x(e)只代表边上的流量，而无法区分流量具体属于哪条流，为此需要一个额外的算法EXTRACTPATHS(表 2)来准确提取每条流的路径，算法的正确性证明见下文。

在说明算法之前先引入2个记号PATH和DIST：PATH(v₁, v₂, …, v_n)代表v₁→v_n的最短路径，同时这条路径必须按照顺序依次经过点v₁, …, v_n。其中v_i可以是单独的点也可以是点集合，当表示点集合时，PATH(v₁, v₂, …, v_n)代表所有可能路径中最短的那一条。DIST表示相应PATH的长度。

算法分成2步：首先确定流起始点属于A的路径，然后确定流起始点属于S的路径：

第1步，行4~13，对于起点是汇聚点a∈A的流，用Prim算法从r开始生成关于A∪r的最小树，即只考虑汇聚点(转发节点只会影响汇聚点之间的距离)。

第2步，行14~16，对于起点是发送端s∈S的流，其终点是离其最近的汇聚点或终点。

定理 2  已知汇聚点集合A，如果按照EXTRACTPATHS找出的汇聚树是合理的，则此汇聚树是关于A的最小代价汇聚树。

证明  第1步，只考虑汇聚点和接收端集合A∪r，以汇聚点为起点的汇聚流一定有且只有1条，即节点的出度为1，并且终止于另外一个汇聚点或接收端r。符合所有节点出度≤1，且保证A∪r连通的最小图显然是一棵最小有向树。

因为本文的优化目标只和边上的数据量有关，和边的方向无关，所以使用无向图的最小生成树算法Prim算法即可(只要每次加入新边时，保证一个节点只有1条出向边即可)。如果优化的目标和边的方向有关，即边的权重不是对称的(如路径的时延)，则需要使用专门的有向树生成算法^[25]。

第2步，对于A∪r这个整体，以发送端为起点的流只要取到这个集合内最近的节点的最短路径即可。因为如果没有汇聚点，某个发送端s对于汇聚树贡献的代价最小是DIST(s, r)，而如果有汇聚点，流s到汇聚点可能会比直接到达接收端增加的代价更小，因此取这两类距离中最小的即可。□

要注意的是，定理2中强调了最后的汇聚树必须是合理的，如果给定的汇聚点集合A不合理，按照EXTRACTPATHS生成的汇聚树也可能是不合理的，如某个汇聚点处于单条流的路径上，并没有起到聚合作用。

2.4 汇聚树问题的复杂度分析

利用上一步的EXTRACTPATHS算法，容易得到这样一个暴力搜索算法：给定任务可使用的资源量M(目前还只考虑单棵汇聚树，因此M即汇聚节点数量)，依次尝试在网络中选择n=1, 2, …, M个汇聚点，每个n会带来C_|V|ⁿ种组合，然后根据EXTRACTPATHS求出可能的汇聚树，删去不合理的汇聚树，从剩余汇聚树中选出代价最小的。

而EXTRACTPATHS算法复杂度分析如下：选用没有任何优化的Dijistra算法作为寻找节点之间最短路径算法，算法复杂度为O(|V|²)。一开始确定S, A, r之间的所有最短路径对的复杂度为O((|S|+|A|)|V|²)。第1步，确定A∪r构成的最小树的算法复杂度为O(|A|²)。第2步，确定以发送端S为起点的流路径，每个发送端需要比较|A|+1条路径，这一步和上一步可以独立进行，而且这种比较在刚开始寻找最短路径时就可以顺带完成，因此这一步没有产生额外的复杂度。综上，整个算法复杂度为O((|S|+|A|)|V|²+|A|²)，最差情况为A取V时，复杂度为O(|V|³)。

因此，假如采用暴力搜索的方法求解汇聚树，考虑资源M足够大时(M≥|V|)，需要遍历V的所有子集和，此时复杂度为O(2^|V|·|V|³)。

3 GCAT算法

考虑到大规模求解ILP的复杂度过高，本文提出一个启发式算法(greedy cost aggregation tree, GCAT)(表 3)，其输入为发送端集合S，接收端r，最大可用资源量M，以及节点容量C向量。输出为流的路径集合P(汇聚树可由流路径构造出来)。

算法原理类似梯度下降法：令f(S, A, r)表示由发送端集合S，集合A(只有A中节点可作为汇聚节点)以及接收端r构成的最小汇聚树的代价。容易看出，随着集合A内节点的增加，S→r这棵汇聚树的代价f总是单调不增，因此GCAT算法每次扩张A时总是选择使得f下降最多的节点(行8~13)进行扩张。

由2.3节提出的EXTRACTPATHS算法可得到所有流的路径集合P，而f实际上就是P中所有流的路径长度之和。以图 4(c)为例，所有流的路径长度之和为1+1+3+3+3+3=14(表 3中COST(P)的计算方式)，这和按照ILP模型(P1)基于边的计算方式1×8+2×3=14是相等的。

如果遍历V的所有子集计算f，2.4节已指出其具有指数复杂度，因此问题关键在于如何确定最小的集合A使得汇聚树代价最小。

3.1 逐点加入的贪心算法

为减少排列组合复杂度，算法GCAT做了2处改进。一是采取贪心的策略避免穷举：每一轮只从待选节点集合W中选出1个价值最大(使树代价减少最多)的节点加入A，后一轮的价值计算基于上一轮的选择结果，而不是从头开始(行17)；二是待选节点集合W动态地进行扩展，一开始W为S→r的最短路径树上的交换节点(行4)，在汇聚树构造过程中，不断向W内添加新探索到的路径上的节点，同时删除已经加入A的节点(行18)。这样就避免从一开始就考虑整个节点集合V。

以图 5(a)中的拓扑为例，假设任务可使用4份资源，每个交换节点的容量为1，图 5(b)是根据GCAT算法最终得到的汇聚树，图中的虚线是没有数据流经过的物理链路。图 6(a)~6(d)展示了算法的每一轮结果，有向边上标出的是经过的数据量(只有大于1才标出)，图中的阴影圆节点代表汇聚点。一开始，W={1, 2, 3, 4, 6, 7, 8}，A=Ø，COST(P)=24，即集合S到r的所有最短路径长度之和。

第1轮，从集合W逐点代入EXTRACTPATHS得到路径并计算代价，最终发现节点4能够使代价减少最多，为4，因此节点4加入集合A，从集合W中删除节点4。第1轮结束，结果如图 6(a)所示。

第2轮，在W={1, 2, 3, 6, 7, 8}，A={4}的前提下，继续从集合W中代入节点计算，选出能够使得代价减少最多的节点也就是节点3加入集合A，从集合W中删除节点3。第2轮结束，结果如图 6(b)所示。

第3、4轮同理。整个过程中值得注意的有2处：1)从节点d出发的流在前3轮并没有直接走到r的最短路径(d→7→6→3→r)，而是选择先到交换节点4和其他流合并(d→7→4)后再从节点4走最短路径，因为这样从总的代价上看会减少2。2)原始拓扑中的节点5始终没有加入待选节点集合W，这样就减少了需要考虑的节点数量。

3.2 复杂度分析

考虑当M充分大时，因为最后形成的汇聚树上必然只有流的交汇点作为汇聚点，而|S|个叶子节点的树，最多只会有|S|-1个交汇点(考虑二叉树的情况)，所以最多只需要循环|S|-1轮。

在确定第i个汇聚点时，已经确定的汇聚点有i-1个，构造这i-1个汇聚点和r的生成树复杂度为O(i²)，每个发送端出发的流判断是否要切换终点，总判断次数为|S|，需执行|W|次，总的复杂度为∑_{i=1…| S |-1}(O(i²)+O(|S|))·O(|W|)=O(|S|³|W|)。这个过程中需要求得的最短路径复杂度为O((|S|+|W|)|V|²)。虽然W的大小是动态变化的，但是总是V的子集，因此总的复杂度为O(|S|³|V|+|V|³)。

4 多汇聚树模型

上文针对单棵汇聚树给出了ILP模型(P1)和启发式算法GCAT，这部分讨论如何将这两者推广到处理多棵汇聚树的场景。

$\sum\limits_{k \in \mathscr{K}} a^k(i) \leqslant m_i, \forall i \in V,$

(12)

$\sum\limits_{k \in \mathscr{K}} \sum\limits_{i \in V} a^k(i) \leqslant M .$

(13)

模型(P1)的约束(1)~(9)对于各汇聚树而言都是独立的，我们用(i)^k表示汇聚树T^k的有关约束。由于每棵汇聚树共享了节点上资源以及任务可使用资源量，约束(10)(11)需要重写为约束(12)(13)。

$\begin{aligned} & \quad \min\limits _{\substack{a^k(i), y^k(e), x^k(e)}} \sum\limits_{k \in \mathscr{K}} \sum\limits_{e \in E} x^k(e), \\ & \text { s.t. }(1)^k-(9)^k, (12)(13), \forall k \in \mathscr{K} . \end{aligned}$

(P2)

优化目标是最小化所有汇聚树代价之和，最后关于多棵汇聚树的ILP模型整理为(P2)。

算法EXTRACTPATHS只和汇聚树的发送端S^k，汇聚点集合A^k和接收端r^k有关，因此为每棵汇聚树单独执行一次即可得到每棵汇聚树上的流路径。

算法GCAT运用在多棵汇聚树上时，只要为每棵树分别记录A^k, W^k, P^k, v^k，然后在GCAT的while循环内每次从K棵树中选出能够使c^k-COST(P^k)最小的汇聚点v，更新相应的汇聚树的路径。此处无法直接比较COST(P^k)，因为生成的汇聚树自身的代价小并不能说明加入的汇聚点减少的代价多，可能汇聚树原本代价就很小。

需要注意的是，由于所有的汇聚树共享了节点资源，当某些节点资源被一棵树使用后为0时，也要将此节点从其他W^k中删除。

除了第1轮所有树都要计算一遍以外，之后每一轮只有上一轮被加入了汇聚点的树才需要重新评估节点，所以K棵树的GCAT复杂度为O(K|S|³|V|+|V|³)。

5 仿真结果与分析 5.1 生成树算法和网络拓扑

已有算法^[19-21]都只针对特定网络拓扑提出生成树的构造方法，本实验分别使用各自文献中的网络拓扑和其对比效果，同时还额外加入Erdos-Rényi随机网络^[26]和2个通用算法：最短路径树(Shortest)和Takashami算法^[18](一种斯坦纳树算法)用作比较。最后为比较GCAT算法和最优解(即2.4节提出的暴力搜索算法)之间的差距，对于每种网络拓扑都做了小规模仿真验证。下面对涉及到的算法以及网络拓扑规模作简要说明。

Avalanche算法^[19]在FatTree网络中构造多播树，目标是使得最后多播树总的边数尽可能少。本实验中FatTree网络pod数量为16，即总共有320台交换机，终端只连接在边缘交换机上。Camdoop算法^[20]在Torus网络(一种立方体结构的网络，每个交换机和上下左右前后连接)中构造汇聚树，这种网络中每个节点都有1个三维坐标，该算法根据发送端的三维坐标在每个维度上依次汇聚。本实验中的Torus网络规模为8×8×8=512的交换机阵列，每个交换机都连接1个终端。IRS算法^[21]在BCube(n, k)网络(一种递归结构网络，n为交换机端口数量，k为递归的次数，终端和交换机都参与数据转发，但本实验中只允许交换机转发)中构造汇聚树，由于每个节点也有相应坐标，因此方法跟Camdoop算法类似，也是根据发送端的坐标维度依次汇聚。本实验中选择BCube(4, 3)作为实验网络，该网络共由4³⁺¹=256个终端和(3+1)×4³=256个交换机组成。

随机网络中交换节点以一定概率p和其他交换机相连。交换节点数量|V|设置为300~400之间的随机值，服从均匀分布，每个交换节点上都连有一个终端。交换节点之间的连接概率设置为p=2ln(|V|)/|V|(这样设置能够保证生成的随机图大概率是连通的)，则每个节点连接的边数服从关于节点数量|V|和p的二项分布，1个节点和大约|V|p=2ln(|V|)≈12个节点相连，方差为|V|p(1-p)≈12。

由于这些算法没有考虑资源的分配问题，还需加入一个资源分配策略：当可使用资源量M小于生成树上的交汇点数目时，优先选择能使得流合并后减少代价最多的交汇点作为汇聚点，同时最后输出路径集合P时检查以发送端为起点的流终点是否为汇聚点，如果不是，要将其恢复成到r的最短路径，因为在执行生成树算法时这些流的路径可能被延长了。这些算法扩展为处理K棵树的方法和第4节类似。

5.2 仿真参数

仿真参数以及性能指标已经列在表 4中，这里做简要说明。一棵有|S|个发送端的汇聚树最多需要|S|-1个汇聚点，因此K棵汇聚树需要的资源量不超过KS。任务可使用的资源量为M，定义任务的资源充裕度为α=M/KS。α=0时，由于任务没有资源可使用，此时相当于|S|条最短路径构成的汇聚树；α≥1时，任务可使用资源量大于其所需的，多余资源量不起作用。因此我们只需关注0≤α≤1的部分。所有交换节点的容量都设置为m，定义交换节点资源充裕度为β=m/K。当β=0时，由于节点上没有资源，此时相当于|S|条最短路径构成的汇聚树。当β≥1时，每个交换节点都能容纳≥K棵汇聚树，多余的容量不起作用。因此只需关注0≤β≤1的部分。

任务的汇聚树数量K为20~50之间的随机值，每棵汇聚树包含的发送端|S|数量为50~100之间的随机值，两者均服从均匀分布，接收端r任取不同于S的终端。

将α=0或β=0时的汇聚树代价，即|S|条最短路径P₀长度之和COST(P₀)作为基准，将加入汇聚点后的代价的减少量COST(P)-COST(P₀)除以此基准称作代价减少率θ，其含义为汇聚树每多使用一份资源带来的传输数据量的减少，这个值越大越好。

由于K棵汇聚树并不一定会使用完K|S|大小的资源量，即任务实际使用的资源量M_used≤K|S|，定义θ/M_used(每单位资源带来的代价减少率)为资源利用率，其含义是每消耗一份资源能够减少的数据量(百分比)，这个值越大越好。

每次实验确定|V|, K, |S|，调节α和β值，可分别得到|α|×|β|=100个数据点，将其分成4组场景：1.α∈(0, 0.5], β∈(0, 0.5]，节点容量和资源量都偏少; 2.α∈(0, 0.5], β∈(0.5, 1]，节点容量偏少，资源量充足; 3.α∈(0.5, 1], β∈(0, 0.5]，节点容量充足，资源量偏少; 4.α∈(0.5, 1], β∈(0.5, 1]，节点容量和资源量都充足，此种情况接近于理想情况，最优解应是一棵斯坦纳树。最后统计各自区间平均值，各网络拓扑下各算法的θ和η结果如图 7、图 8所示。

对于和最优解对比的仿真实验，拓扑规模和前文所述一致，为减少穷举时间，网络中只有40个节点可作为汇聚点，任务只包含一棵发送端数量为10的汇聚树。实验结果展现的是场景1~4下启发式算法和最优解比值即θ/θ_OPT的平均值，结果如图 9所示。

5.3 实验结果分析

可以看出，无论是节点容量还是总资源量成为瓶颈(场景1~3)，在4种网络下GCAT对于汇聚树代价的减少都是最多的(图 7(a)~7(c))。当资源几乎不会成为瓶颈(场景4)，即此问题等价于斯坦纳树问题时，GCAT在ER随机网络中的表现要略逊于启发式斯坦纳算法Takashami(图 7(d))。

从资源利用率(图 8)的角度看，GCAT在各个场景下均显著高于其他算法。原因在于，最初的每份资源带来的代价减少较大，随着资源的增加，每份资源带来的代价减少会逐渐变小，当代价的减少需要≥2个汇聚点时，由于GCAT一次只考虑1个汇聚点，会提前停止对汇聚点的使用，这种特性使其对资源有着较高的利用率，但同时也减少了其进一步降低代价的可能性。因此GCAT算法尤其适用于资源受限的场景，这一点在图 7、图 8的场景1体现得尤为明显。在小规模实验中(图 9)，GCAT算法相比其他启发式算法明显更接近最优解，带来显著差异的主要原因是其他算法缺少像GCAT一样的探索机制(代码行18)，因此如果一开始确定的生成树上缺少可作为汇聚点的交汇点，这些算法不能有效寻找到新的可用节点。

6 总结

本文提出并研究在资源限制下的最小代价汇聚树问题。首先说明此问题和斯坦纳树问题之间的关系，证明其是NP难问题，然后分别给出问题的ILP模型和启发式算法GCAT。仿真结果表明，相较于其他启发式算法，算法GCAT能更高效地减少汇聚树在网络中产生的数据量，尤其是在资源受限明显的场景下性能更为突出。