一种P2P直播覆盖网的可靠性最优树状核心拓扑求解方法

摘要

本发明旨在提供一种P2P直播覆盖网的可靠性最优树状核心拓扑求解方法，包括通过分层出度加权将P2P直播覆盖网的骨干节点的出度和可靠性转换为加权可靠性，用加权可靠性作为排序依据逐层构造树状核心拓扑；用进化规划算法对分层权重数组进行优化，进化过程中以所有节点的累积可靠性之和作为进化指标，求解得到可靠性最优的树拓扑。本发明所述的P2P直播覆盖网的可靠性最优树状核心拓扑求解方法提高了P2P直播覆盖网的稳定性，降低了直播时延。

说明书

技术领域

本发明涉及网络通信，更具体地说，涉及一种采用树状或树形/网状混合拓扑的P2P直 播覆盖网的可靠性最优树状核心拓扑求解方法。

背景技术

据调查，目前因特网上70％的流量是P2P应用，在P2P架构中，共享的资源可以直接交 换，不需要集中服务器的中转和参与，同时P2P系统对覆盖网络的不稳定和可变连通性具有 良好的容错能力，并保持良好的可靠性。

当前，P2P直播覆盖网是大规模网络电视的主要分发方式，P2P直播覆盖网的拓扑结构 大体上可以分为四种模式：(1)单纯模仿IP组播树的树状结构，并出现了多棵树的互补分发。 (2)网络中每个节点以自己为中心，在数据需求驱动下主动去拉数据，这样形成没有明确拓扑 结构的网状结构。(3)将树状结构的高效性和数据驱动的鲁棒性相结合，形成混合结构。(4) 节点管理覆盖网与数据分发覆盖网各自组织，以节点管理引导数据分发。

早期的P2P直播覆盖网组播通常采用树状结构，如NICE，ESM系统。此类树状结构的数 据分发采用推的方式，额外开销小，时延较短，Bullet则利用多颗树互补的方式，提高了分 发的速度。AnySee较早地在网状的节点管理拓扑上建立多棵数据分发树，并且在多棵分发树 之间进行传输资源的互补优化。但是由于节点动态性引起的结构维护困难，导致树状结构覆 盖网的大规模应用受到限制。

DONet(Data-driven Overlay Network)是通过构建纯粹的网状拓扑结构实现数据的分 发，无需构建复杂的控制结构基于DONet协议的实时流媒体播放系统CoolStreaming，其 出色的播放效果、较低的延迟已经在实际运行中得到了证实和肯定。其他得以大规模应用的 系统，如PPLive，PPStream，UUSee，GridMedia，Sopcast，TVants等，也在数据调度中使 用了类似的方法。DONet数据调度主要采用拉的方式，为此节点间需要频繁地交换缓冲映射 图(BM)，导致其额外的带宽消耗较大，时延也较长。

为了克服拉模式的不足，又出现了推拉结合的混合分发模式，在拉的过程中建立局部树 状结构，然后进行推的方式。推的方式中为避免叶子节点上传带宽得不到利用，往往采用多 子流(Substream)，即在多颗树上同时传输的方法。

除了在数据分发中进行树状和网状结构的混合使用，还存在节点管理和数据分发中使用 不同结构的混合模式。而在AnySee2中，采用树状结构进行节点监控和管理，采用网状结构 进行流媒体数据传输的方法，称为TCMM(Tree-Control-Mesh-Media)。

综上所述，为了利用树状拓扑结构的高效率和低时延的优点，又要避免因为节点频繁加 入退出而引起的拓扑维护成本过高的缺陷，需要一种优化的拓扑结构，使其即具有良好的鲁 棒性和可靠性，又能提高覆盖网的稳定性并降低直播的时延。

发明内容

本发明提供了一种P2P直播覆盖网的可靠性最优树状核心拓扑求解方法，利用了树状拓 扑结构的高效率和低时延的优点，同时避免采用树状拓扑时因为节点频繁加入退出引起的拓 扑维护成本过高的问题。

本发明提供一种P2P直播覆盖网的可靠性最优树状核心拓扑求解方法，所述可靠性最优 树状核心拓扑求解方法包括：

(1)在所述P2P直播覆盖网中根据出度和可靠性选取骨干节点；

(2)根据骨干节点的数量和平均出度计算出度权重数组的长度；

(3)按照步骤(2)中所述出度权重数组的长度，随机产生一组出度权重数组，将所述 的随机产生的一组出度权重数组作为初始种群；

(4)对于所述初始种群中每个个体构造相应的树拓扑，并计算每棵树拓扑的所有节点 的累积可靠性之和；

(5)将步骤(4)所述初始种群或步骤(6)所述的初始种群作为进化种群，对所述进 化种群的每个个体进行复制并变异，形成变异种群；根据所述变异种群每个个体 构造相应的树拓扑，并计算每棵树拓扑的所有节点的累积可靠性之和。

(6)将所述进化种群与所述变异种群所有个体对应的节点的累积可靠性之和进行递减 排序，选择排序在前的一半个体作为新一轮进化的初始种群；

(7)对于步骤(6)中产生的所述新一轮进化的初始种群，进行是否满足进化结束条件 的判断，如果不满足所述进化结束条件，重复执行步骤(5)到步骤(7)，直到满 足进化结束条件为止；

(8)步骤(7)中满足进化结束条件的所述新一轮进化的初始种群，即为可靠性最优树 状核心拓扑。

优选的是，所述出度权重数组的长度是所述树状拓扑的最大深度。

优选的是，所述满足进化结束条件为所有节点的累积可靠性之和的最大值、平均值的变 化小于阈值或者所述满足进化结束条件为进化代数达到上限。

优选的是，所述节点的累积可靠性的计算方法，包括：

(1)所述树拓扑的根节点的累积可靠性即为其自身可靠性；

(2)从步骤(1)中所述根节点开始，广度遍历所有孩子节点，对每个节点按步骤(3) 计算其累积可靠性；

(3)所述节点的自身可靠性乘以其双亲节点的累积可靠性作为所述节点的累积可靠 性。

优选的是，在所述P2P直播覆盖网中根据出度和可靠性选取骨干节点中，所述出度大于 流媒体速率，所述可靠性大于可靠性阈值的节点被选取为骨干节点。

优选的是，所述可靠性阈值通过设定固定值实现。

优选的是，所述可靠性阈值通过指定骨干节点数量占总节点数量中的比例实现。

优选的是，根据所述选取的骨干节点的数量和平均出度，通过公式：

计算所述树拓扑结构的最大深度，其中c表示所述选取的骨干节点的数量，d表示所述选 取的骨干节点的平均出度，l表示所述树拓扑结构的深度。

优选的是，所述构造相应的树拓扑的方法，包括：

(1)按照前后次序获取出度权重数组的元素，对每个元素进行步骤(2)到步骤(3) 的处理，直到所有节点加入到树中；

(2)根据所述数组元素计算所有未加入树的节点的加权可靠性，并进行从高到低的排 序；

(3)根据所述的节点加权可靠性排序结果，将排序在前的节点逐个加入到树中。如果 树中没有节点，则只取一个节点作为根，否则将节点加到原有树的叶子节点上， 直到用尽所有叶子节点的出度或者没有待加入节点。

本发明提供的可靠性最优树状核心拓扑求解方法提高了树状拓扑在直播覆盖网拓扑构造 中的适用性，即发挥树状拓扑高效率、低时延的优点，又尽量降低其拓扑维护的成本。本发 明提供的可靠性最优树状核心拓扑求解方法用于直播覆盖网中全局或局部的骨干节点组成树 状核心拓扑，可提高覆盖网的稳定性，降低直播的时延。与随机构造树拓扑比较，本发明提 供的方法在树拓扑的可靠性和时延上都能够显著改善；与出度优先构造树拓扑比较，本发明 提供的方法可靠性明显改善，时延接近；与单纯节点自身可靠性优先构造树拓扑比较，本发 明提供的方法可靠性有所提高，时延显著提高。

附图说明

为了使本发明便于理解，现在结合附图描述本发明的具体实施例。

图1示出了本发明所使用的P2P直播覆盖网的拓扑结构图。

图2示出了本发明一优选实施例的具体实施步骤的流程图。

图3示出了计算节点累积可靠性之和的步骤示意图。

图4示出了进化过程中个体(出度加权数组)变异的程序代码示意图。

图5示出了构建覆盖树结构的构造过程的程序代码示意图。

具体实施方式

下面结合附图和具体实施方式对本发明作进一步详细描述。

图1示出了本发明所使用的P2P直播覆盖网的拓扑结构图。其中，101表示骨干节点，102 表示普通节点，103表示树状核心拓扑的边，104表示网状拓扑的边。P2P直播覆盖网分发的 拓扑通常采用树状拓扑和网状拓扑混合的方式。因为，树状拓扑有效率高、低时延的有点， 也有因为节点动态引起的拓扑维护代价过大的缺点。树状拓扑适合于直播覆盖网中的稳定节 点，而网状拓扑适合于更多高度动态的边缘节点。为了尽量克服树状拓扑维护的不足，提高 其优势发挥的适用性，在树状拓扑构造中应该选择部分稳定的骨干节点，并且以可靠性优化 为首要目标，同时降低时延。

本发明所使用的P2P直播覆盖网的拓扑结构图的拓扑结构原理为：根据历史统计每个节 点的出度(上传带宽)和可靠性，选择所有节点中出度和可靠性满足设定阈值的的节点为骨 干节点，其他节点为普通节点。

其中，所述骨干节点参与构造树状拓扑，也参与网状拓扑构造。骨干节点用于树状拓扑 传输的出度(上传带宽)是流媒体速率的整数倍，剩余带宽用于网状拓扑的传输。

所述普通节点与所述骨干节点共同参与构造网状拓扑，其中骨干节点为网状拓扑只贡献 流媒体速率整数倍之外的剩余带宽。

图2示出了本发明一优选实施例的具体实施步骤的流程图。步骤201表示选择骨干节点， 根据历史统计选择出度(即上传带宽)大于流媒体速率，并且可靠性大于设定阈值的节点为 骨干节点。其中，所述设定的可靠性阈值可以通过下述两种方法实现：第一，设定固定数值 为所述阈值，即可靠性大于所述设定的固定数值，即为骨干节点；第二，设定相对数值为所 述阈值，即通过指定骨干节点数量在总节点数量中的比例决定。

步骤202表示计算出度权重数组长度，所述出度权重数组的长度是所述树状拓扑的最大 深度，所述树拓扑结构的最大深度采用取对数的方式，公式如下：

其中，c表示所述选取的骨干节点的数量，d表示所述选取的骨干节点的平均出度，l表示 所述树拓扑结构的深度。

步骤203表示随机产生s个个体，每个个体是长度为l的出度权重数组，其中，s表示参数 设定值。

步骤204表示形成一代出度权重数组种群，所述出度权重数组种群的规模为s，所述出度 权重数组种群可以来源于进化前步骤203中产生的s个出度权重数组，还可以来源于进化过程 中步骤208所选择的较优个体。其中，对于来源于进化前步骤203中产生的s个出度权重数组 的，对种群中每个个体的调用采用如图3所示的步骤计算其节点累积可靠性之和。

步骤205表示产生变异出度权重数组种群，将步骤204中的种群中的每个个体复制一份 并进行变异，并且，对变异个体的调用采用如图3所示的步骤计算其节点累积可靠性之和。 所述变异的具体实现参考图4，图4示出了进化过程中个体(出度加权数组)变异的程序代 码示意图。

步骤206表示选择产生下一代出度权重种群，将所述变异前后的所有个体按照节点累积 可靠性之和进行降序排序，选择s个排序在前的个体作为新一代种群。

步骤207表示判断是否满足进化结束的条件，根据最优个体的节点累积可靠性之和r_m(T)、 s个排序在前的个体的节点累积可靠性之和的平均值r_a(T)和进化代数g，判断进化是否结束。 进化结束条件的公式如下，(1)(2)同时成立或者(3)成立，进化结束：

(1)$r_m\left(T\right)-r_m^{\prime }\left(T\right)<{▿}_m*r_m^{\prime }\left(T\right)$

(2)$r_a\left(T\right)-r_a^{\prime }\left(T\right)<{▿}_a*r_a^{\prime }\left(T\right)$

(3)g≥g_m

其中，g_m是设定参数，r′_m(T)、r_a′(T)是上一代(也是之前进化过程中)对应的 节点累积可靠性之和的最优和平均值。

(1)(2)同时成立表示所有节点的累积可靠性之和的最大值、平均值的变化小于阈值； (3)成立表示进化代数达到上限。

步骤208表示获得可靠性最优树状核心拓扑，即满足进化结束条件后得到的最优个体所 对应的树就是求解的P2P直播覆盖网的可靠性最优树状核心拓扑。

图3示出了计算节点累积可靠性之和的步骤示意图。即本发明的一优选实施例中根据进 化个体(出度加权数组)构造树并计算该树的节点累积可靠性之和。

步骤301表示构造树状拓扑。根据出度加强数组，进行分层构造树结构，所述构造过程 的具体实现参考图5，图5示出了构建覆盖树结构的构造过程的程序代码示意图。

步骤302表示计算树的节点累积可靠性之和。根据步骤301中构造的树拓扑，计算该树 的所有节点累积可靠性之和，每个节点累积可靠性通过下述公式计算：

r_a(p)＝r(p)*∏_u∈path(p)r(u)

其中，path(p)表示从根节点到节点p的路径上的除了p之外的所有节点。所述覆盖树可靠 性通过下述公式计算：

r(T)＝∑_p∈Tr_a(p)

图4示出了进化过程中个体(出度加权数组)变异的程序代码示意图。其中，输入表 示出度加权权重数组，即进化个体；输入g表示当前进化代数；输入r表示用构建的覆盖树 在种群中的排名；g_m表示最大进化代数；s表示种群规模；δ表示设定的参数。

f_g表示进化代数因子，通过代数式f_g＝1-g/g_m获得，其中，g_m为最大进化代数。

f_r表示个体排名因子，通代数式f_r＝r/s获得，s为种群规模。

图5示出了构建覆盖树结构的构造过程的程序代码示意图。所述的构建的覆盖树的根节 点是源节点所述源节点也是骨干节点。输入表示规模为c的节点集合(集合的节点中 不包含源节点)。输入表示出度加权权重数组，即种群中的每个进化个体。

其中，种群中的每个进化个体中的ω_i表示第i层节点(根节点的层次为 0层)的选择。

选择是通过对节点进行出度加权可靠性排序进行的。节点的出度加权可靠性计算通过如 下公式计算：

r_w(p)＝r(p)+(d(p)-1)*w_i

r(p)表示节点集合p的可靠性，d(p)表示节点集合p的出度。

上述详细描述通过实施例和/或示意图阐明了系统和/或过程的各种实施例。就这些示意 图和/或包含一个或多个功能和/或操作而言，本领域技术人员将理解，这些示意图或实施例 中的每一个功能和/或操作都可由各种各样的硬件、软件、固件、或实际上其任意组合来单独 地和/或共同地实现。

应该理解，本文描述的方法可以结合硬件或软件，或在适当时结合两者的组合来实现。 因此，本发明的方法，可以采用包含在诸如软盘、CD-ROM、硬盘驱动器或任何其他机器可读 存储介质等有形介质中的程序代码(即，指令)的形式，其中，当程序代码在可编程计算机 上执行的情况下，计算设备通常包括处理器、该处理器可读的存储介质(包括易失性存储器和 /或存储元件)、至少一个输入设备、以及至少一个输出设备。一个或多个程序可以例如，通 过使用API，可重用控件等来实现或利用结合本发明描述的过程。这样的程序优选地用高级 过程语言或面向对象编程语言来实现，以与计算机系统通信。然而，如果需要，该程序可以 用汇编语言或机器语言来实现。在任何情形中，语言可以是编译语言或解释语言，且与硬件 实现相结合。

尽管具体地参考其优选实施例来示出并描述了本发明，但本领域的技术人员可以理解， 可以作出形式和细节上的各种改变而不脱离所附权利要求书中所述的本发明的范围。以上结 合本发明的具体实施例做了详细描述，但并非是对本发明的限制。凡是依据本发明的技术实 质对以上实施例所做的任何简单修改，均仍属于本发明技术方案的范围。