14
0 引言
随着智能手机、平板电脑等移动终端的普及，以及各种移动接入技术的出现，Wi-Fi 、BMSB 、DVB-T/H 、ATSC-H/M 等组播应用需要满足人们随时随地的接入需求[2]。通过移动终端人们可以观看网络视频、进行多人游戏、举行视频会议和完成协同办公。这些应用需要组播技术的支持，而目前较为普遍的应用层组播模型都是基于传统的Internet 网络，在节点性能差异巨大的移动互联网中并不适用。
目前应用层组播根据构建组播控制拓扑和数据拓扑的顺序可以分为三类：基于网的组播模型、基于树的组播模型和基于隐含组播转发拓扑的组播模型[1]。较为常用应用层组播模型Nice 和Zigzag 是基于隐含组播转发拓扑的组播模型，Nice 是为大量接收者的组播应用设计的可扩展的应用层组播模型，使用了分层和分簇的思想，通过控制簇的大小来保持负载均衡和降低树的高度[3]。Zigzag 也是一种基于分层和分簇的应用层组播模型，将控制拓扑与数据拓扑分离，在簇的头节点的推举过程中考虑了带宽，适用于大规模组播网的应用[4]。
在节点性能差异较大的网络环境中，这两种组
基于节点性能的分层组播模型
王 雷 文泽鹏
（中国科学技术大学自动化系）
摘 要：随着移动互联网的快速发展以及各种不同性能的移动终端的普及，基于传统的Internet网络设计的应用层组播模型不再适用于新的移动互联网环境。通过对现有的分层分簇组播模型Nice和Zigzag的分析，本文对Zigzag模型进行了改进，提出了一种基于节点性能的分层分簇组播模型，并对组播结构的调整和优化进行了描述，最后通过仿真实验与Nice和Zigzag在平均时延、平均链路延伸度和平均链路压力三个方面进行了对比，证明了组播模型的有效性。
关键词：移动互联网；应用层组播；组播模型；Zigzag
A Hierarchical Multicast Architecture Based On Node Performance
Wang Lei Wen Zepeng
(Department of Automation, University of Science and Technology of China)
Abstract : With the rapid development of mobile Internet and the prevalence of mobile terminals with various performances, the multicast model of application layer which is designed for traditional Internet is no longer suitable for the current environment of mobile Internet. Through the analysis of existing hierarchical and clustering multicast models, Nice and Zigzag, this paper improves the Zigzag model, proposes a node performance-based hierarchical and clustering model, and describes the adjustment and optimization of the multicast structure. The simulation experiment proves the validity of the proposed multicast model by the comparison between Nice with Zigzag on three aspects - average delay, average link extension, and average link stress.
Key words : mobile Internet; application layer multicast; multicast model; Zigzag
播模型均有较大的缺陷。Nice 模型没有考虑成员节点能力的差异，簇的头节点选举使用最大最小距离法，可能造成能力弱的节点处于组播树的上层。Zigzag 模型在推举头节点时虽然考虑了时延和带宽，但是也没有针对节点的处理能力进行优化。并且这两种组播模型对簇中节点数的范围固定在[k,3k]，常数k 值在节点性能差异较大的环境中难以确定。
针对传统的基于Internet 网络环境设计的组播模型的缺陷，本文通过对Zigzag 组播模型的改进，提出了一种基于节点性能的分层分簇组播模型。1 组播模型定义1.1 名词定义
由于本文提出的组播模型为Zigzag 模型的改进，所以沿用Zigzag 的名词定义。
源节点（Source ）：在组播树中提供数据源的节点称为源节点。
头节点（Head ）：在一个簇中，被选举为进入上一层的节点称为该簇的头节点，其在组播结构中主要负责组建控制拓扑。
辅助节点（Associate head ）：在一个簇中，辅助
10.3969/j.issn.1000-0755.2012.10.005
节点为除了头节点外的其他节点的父节点，其在组播结构中主要负责组建数据传输拓扑。
普通节点（Subordinate）：在一个簇中，既非头节点也不是辅助节点的节点就是该簇的普通节点。
外头节点（Foreign Head）：节点k为第j层中的非头节点，对于第j－1层的除k所在簇的任意非头节点v，k为v的外头节点。
外簇（Foreign Cluster）：第j层的头节点k和v，如果k，v在第j+1层位于同一簇，k与v所在簇互为外簇。
上层簇（Super Cluster）：如果第j层的簇A的头节点所在的第j+1层的簇X中，那么X称为A的上层簇。
1.2 约束条件
组播模型的构建必须满足下面的约束条件：
（1）第0层包含了组播网络中所有的节点。
（2）一个簇由[kP(u k),3kP(u k)]的节点组成，其中k为正整数，P(u k)为簇的辅助节点u k的性能值。
（3）一个簇C i中的辅助节点a的性能值为P(u a)≥P(u k)，u k∈C i，u k≠u h且u k≠u a，其中u h为簇C i的头节点。
（4）一个簇中的头节点h的能力估值P(u h)≥P(u a)，其中u a为簇中的辅助节点。
（5）被簇中推举为头节点的节点将进入上一层，成为上一层的成员。
（6）在整个组播树的最高层，只有一个簇，该簇由[2,3kP(u s)]个节点组成，其中u s为源节点。
（7）在树的最高层，源节点同时为头节点和辅助节点。
1.3 连接规则
组播树的节点连接规则如下：
规则1：当一个节点不在它所在层次的最上层时，它在该层即没有入度，当节点不在其所在层次的次上层时也没有出度。如图1所示，第2层中使用虚线圈出的节点，第0层既没有出度也没有入度，在第1层没有入度有出度。
图1 节点连接规则
规则2：在一个簇中，如果节点既非头节点也不是辅助节点，那么该节点只能从簇中辅助节点接
收组播数据流，如图1中的白色节点所示，其只能从
所在簇中的辅助节点接收数据。
规则3：簇中的辅助节点只能从它的外头节点接收组播数据流，如图1所示，第0层中的黑色节点只能从其头节点所在的上层节点接收组播数据流。
2 组播模型的调整与优化
在组播应用运行的过程中，会不断地有节点加入和退出，伴随着节点的加入和退出，若簇中的节点数超过簇所能容纳节点数的上限则需要对簇进行分裂，若簇中的节点数低于簇容纳的节点数的下限则需要对簇进行合并；并且随着组播结构的变化，组播模型将不能保持最优的状态，需要对模型进行周期性的优化。
2.1 节点加入算法
在节点请求加入组播网络时，首先使用Hotz距离[5]找到与其最近的第0层簇的辅助节点，将其加入到该簇中，如果其性能优于该簇的辅助节点则与辅助节点进行交换。设节点向节点u x发出加入组播树请求，具体算法如图2所示。
图2 节点加入算法
其中，函数Addable(u i)在存在一条从u i到第0层某个簇的路径并簇的大小在区间[kP(u k),3kP(u k)－1]时返回true，否则返回false；函数Reachable(u y)在存在一条从u y到第0层某个簇的路径时返回true，否则返回false；d(u y)表示节点u y到组播源之间的距离，d(u y, u i)表示节点uy到节点ui之间的距离。
2.2 节点退出算法
组播树中节点退出的情况较节点加入复杂，由节点所处的层次和承担的角色不同可以分为四种情况，如图3所示。
图3 节点退出的四种情况(参见下页)
设簇C中的节点u x
退出了组播结构，为了保持
15
16
电子技术研发 Electronics R & D
图3 节点退出的四种情况
组播结构稳定，具体算法如图4所示。
图4 节点退出算法
其中，HighQoSSet 函数为获取簇C 中QoS 评估值高的节点集合，Split函数为簇分裂函数，其目的为将节点数超过簇所能容纳节点数上限的簇分裂为两个簇。
2.3 簇的分裂算法
在组播模型的定义中，每一个簇中不能超过3kP (u a )个节点，其中P (u a )是簇的辅助节点性能值。因此，当一个簇的节点数超过3kP (u a )，就要进行分裂，将原来的簇中的节点分出一部分组成新的簇。这样可以减轻原有簇的辅助节点的负载，维持组播模型性能的稳定。
如图5所示，分裂的过程分为三个步骤：1）将超容簇中的普通节点按性能排序，将性能较好的一半移动到新簇。2）将新簇中性能最优的节点作为头节点，性能次优的作为辅助节点，并将新簇的头节点原有子节点连接到新簇的普通节点上。3）将新簇的头节点加入上层的簇中作为普通节点，并将新簇的辅助
节点的父节点更改为其上层簇中的适合的普通节点。
图5 簇的分裂过程
根据簇所在的层次不同，分裂操作分为三种情况，分别为簇位于第0层、位于中间层和位于最顶层。三种情况下，簇分裂的过程与图5所示的过程类似，在分裂簇位于最顶层时，将会分裂出新的簇增加组播结构的高度。
2.4 簇的合并算法
在组播树模型的定义中，每一个簇中节点数应该在kP (u a )到3kP (u a )，如果某一个层的簇中的节点数小于kP (u a )，那么为了有效利用节点性能并降低组播树的高度，则需要将该簇与另外的簇进行合并。
设位于第j 层的簇U 中的节点少于kP (u a )，算法选取簇V 与簇U 进行合并。对V 的选取需要遵循下面三个条件：1）簇V必须和簇U具有相同的上层簇。2）N v +N u ≤max{3kP (u h ), 3kP(vh)}，其中N v 和N u 分别为簇V 和簇U 当前拥有的普通节点个数，u h 和v h 分别为簇U 和簇V 的头节点。3）max{max{3kP (u h ), 3kP (v h )}－(N v +N u )}，V ∈C i ，其中C i 为簇U 所在层的簇的集合。
如图6所示，簇合并的过程也分为三个步骤：1）从参与合并簇的头节点和辅助节点中选出性能最优和次优的作为新簇的头节点和辅助节点。2）将参与合并簇的原辅助节点的所有子节点以及它自己重新连接到新的辅助节点。3）将被合并簇的头节点下移一层，将其上层的子节点的父节点，置为上层簇中其他性能较高的节点；根据情况，重新设置其父节点。
图6 簇的合并过程
根据参与合并的簇的头节点在上层簇中的角色不同，簇的合并分为三种情况，分别为头节点为上层的普通节点、为上层的辅助节点和为上层的头节点。这三种情况下，簇的合并均可用类似图6所示的步骤完成。
2.5 周期性优化更新
在组播应用运行一段时间后，随着节点不断的加入离开，簇不断的分裂合并，组播树的结构将变得不稳定，出现性能强的节点在组播树的下层而性能弱的节点在组播树的上层等现象。对于组播树动态变化过程中所出现的问题，本文使用了周期性更新机制来优化组播树的结构，每隔一段时间对整个组播树进行全局调整，将性能强的节点上移，性能弱的节点下移，使得组播树充分利用节点能力，并有效地降低树的高度。
本文借鉴文献[6]中TCP/IP协议中对拥塞控制的有限慢启动（limited slow start）算法的思想来设置优化时间间隔。首先设置初始更新时间间隔t start，正常步长时间t d和最小步长时间t min，初始时系统每隔t start 时间更新一次组播树结构，随着节点数每增加k，系统更新时间间隔增加t d，当系统中节点数达到设定值N max时，节点数每增加k，更新时间增加t min。设当前系统更新时间间隔为t i，那么当节点数增加k后新的更新时间间隔如式（1）所示。
（1）
其中，N current为当前组播系统中的节点数，在节点数减少时，更新时间间隔的计算与增长过程相反。
优化算法如图7所示，对组播树结构的调整采用自底向上的方法，首先从第0层簇开始进行调整，遍历所有第0层簇，选出簇中除辅助节点外性能值最高的节点集，若簇的头节点不在集合中则随机地挑选集合中的一个节点代替头节点进入上一层代替原头节点功能，并将原头节点下移到簇中作为普通节点，递归地进行此过程直至最高层，算法调整完毕。
图7 组播结构优化算法
3 仿真实验
本节使用NS2和GT-ITM对本文提出的基于节点性能的分层分簇组播模型进行仿真。仿真环境由GT-ITM生成Transit-stub结构网络，并对网络环境中的节点性能参数进行随机设置，通过C++编写组播模型的连接规则。从平均时延，平均路径延伸度和平均链路压力三个方面将本文提出的组播模型与Nice模型和Zigzag模型进行了比较。
平均时延是指组播数据包从源到系统端主机处的延迟的平均值。
图8 平均时延对比
仿真结果如图8所示，三种模型的平均时延均随网络中节点数的增多而增大，由于本文提出的组播模型考虑了节点性能的因数使得在降低组播树高度的同时降低了端系统的延迟，所以平均时延增长较Nice和Zigzag缓慢。
平均路径延伸度是指在组播网络中组播源到端系统的链路长度与组播源在单播网络中到端系统的链路长度的比值的平均值。
图9 平均路径延伸度对比
仿真结果如图9所示，本文的模型相较于Nice、Zigzag有更好的平均路径延伸度。因为性能好的节点位于组播结构的上层，降低了组播树的高度，使
得平均路径延伸度降低。
平均链路压力是在组播网络中在同一链路上同一数据包需要传输的次数的平均值。
图10 平均链路压力对比
仿真结果如图10所示，本文提出的组播模型的平均链路压力较Nice和Zigzag小。由于本文模型中性能较差的节点在组播结构下层不承担分发任务，所以降低了平均链路压力。
4 结语
本文对节点性能差异较大的网络环境下的组播模型进行了研究，对基于传统的Internet网络的组播模型进行了改进，提出了一种基于节点性能的应用层分层分簇的组播模型，并对模型的调整和优化过程进行了描述。通过仿真实验，证明了本文提出的组播模型的有效性。
参考文献：
[1] 章淼,徐明伟,吴建平.应用层组播研究综述[J]. 电子学报,2004,32(12A):22-25.
[2] Franciso F, Belda R, Guerri J C. Evaluation of a
background push download service for personal
multicast devices[C]//2011 IEEE International Conference on Consumer Electronics, 2011: 231-232.
[3] Banerjee S, Bhattacharjee B, Kommareddy C.
Scalable application layer multicast[J]. ACM
SIGCOMM Computer Communication. 2002,32(4): 205-217.
[4] Tran D A, Hua K A, Do T T. A peer-to-peer architecture for media streaming[J]. IEEE Journal on Selected Areas in Communications, 2004,22(1): 121-133. [5] Ng T S E, Zhang H. Predicting Internet network
distance with coordinates-based approaches[C]
//Twenty-First Annual Joint Conference of the
IEEE Computer and Communications Societies
(INFOCOM 2002): 170-179.
[6] Park H, Burmeister E F, Bjorlin S, et al. 40-Gb/s
optical buffer design and simulation[C]//Proceeding of the 4th International Conference on Numerical Simulation of Optoelectronic Devices. Santa Barbara, 2004: 19-20.
作者简介：
王雷，男，1972年生，中国科学技术大学自动化系，副教授，硕士研究生导师，研究方向：网络多媒体、复杂系统建模、仿真与优化控制
手机：139********
电子信箱：wangl@https://www.doczj.com/doc/3b17511422.html,
联系地址：安徽省合肥市四号信箱自动化系 王雷（收）（230027）