可伸缩视频流的覆盖网络分层组播资源最优分配方法

摘要

本发明涉及一种可伸缩视频流的覆盖网络分层组播资源最优分配方法。针对可伸缩视频流在覆盖网络中的分层组播通信，提出了一种新的组播性能度量标准——“层伸展度”，用于测定各视频层在数据分发时的端到端时延。为了实现层伸展度总体最小化，对中继节点的网络编码、接收端驱动的流量控制，以及多路径路由策略进行联合优化，采用线性规划方法建立覆盖网络下的分层组播资源最优分配模型。一方面自适应匹配了可伸缩视频编码的层间依赖性；另一方面允许接收节点自行决定和调整所需要的视频质量。此外，还提出了一种低复杂度、逼近全局最优解的分布式启发式算法，应用于可伸缩视频流分发网络的构建。

主权项

1.一种可伸缩视频流的覆盖网络分层组播资源最优分配方法，其特征在于：第一，采用了一种新的组播性能度量方法——“层伸展度”，测定各视频层数据传输时的端到端时延大小；第二，以端到端的层伸展度最小化为总体目标，对中继节点的网络编码、接收端驱动的流量控制，以及多路径路由策略进行联合优化，建立覆盖网络下的分层组播资源最优分配模型；第三，针对上述最优分配模型，采用线性规划方法进行求解；第四，采用一种低复杂度、逼近全局最优解的分布式启发式算法，构建可伸缩视频流分发网络；所述“层伸展度”定义为覆盖网络中从源点到各个组播组成员的传输路径长度之和与对应的IP层单播传输路径长度之和的比值；所述对中继节点的网络编码技术和接收端驱动的流量控制的方法是：一方面自适应匹配了可伸缩视频编码的层间依赖性；另一方面允许接收节点自行决定所需要的视频质量，从而使层伸展度总体最小化；所述分层组播资源最优分配模型中，接收节点可自适应地调整接收的视频层数来避免覆盖网络的链路资源冲突和网络拥塞；所述针对最优化分配模型，采用线性规划方法求解是：以端到端的层伸展度最小化为目标函数，兼顾所有接收端的吞吐量以及可伸缩视频流解码的层间依赖关系，以信息流平衡条件、链路容量限制、网络编码条件为约束函数，建立覆盖网络分层组播资源分配的线性规划优化模型；具体的线性规划算法如下：(1)覆盖网络模型：将覆盖网络抽象为有向图G(V，E)，其中V是节点的集合，分为源节点集合S和接收节点集合R，E是节点之间链路的集合；对于每条链路(i，j)都有相应的权值：传输带宽C(i，j)和时延D(i，j)；假定可伸缩视频流在源节点编码为M层{l_1，，l₂，...，l_M}，每层数据以速率B_m，通过组播组m进行分发；系数表示接收节点r是否加入了组播组m，即是否接收第m层数据；代表r申请加入组播组m，反之f_m(i，j)代表第m层视频分发网络在各条链路上消耗的带宽；假设从源节点到每个接收节点r都有多条传输路径P(r)，矩阵Z^r表示链路和接收节点r的传输路径之间的关系，其中Z^r的元素表示链路(i，j)包含于接收节点r的第k条传输路径中；表示接收节点r接收第m层数据时，其第k条路径在链路(i，j)上消耗的带宽大小；和分别表示第m层视频分发时，接收节点r在IP层单播网络和覆盖网络上的传输时延，s_m表示覆盖网络上第m层数据的伸展度；(2)线性规划算法 Subject to：优化目标：使总的端到端层伸展度最小化；p_m对应于每一层的权值，满足：p₁+p₂+...+p_M＝1；考虑到可伸缩视频编码的层间依靠性，使p₁＞p₂＞...＞p_M；约束条件：1)对应于各个节点的流量平衡限制条件；2)对应于每条路径的流量平衡限制条件；3)规定每条链路上的实际带宽消耗量为所有接收节点在该链路上消耗带宽的最大值；该条件表示在链路上采用网络编码的限制条件，实现不同节点在同一链路上的资源共享；4)对应于链路上带宽的限制条件；5)指示链路是否被使用；如果即接收节点r在接收第m层数据时，使用了第k条路径在的链路(i，j)，那么反之，6)规定为节点r接收第m层数据时所使用的路径中传输时延的最大值；所述分布式启发式算法，它不需要了解整个网络的全局信息，降低了算法的复杂度；该算法在传输低层视频数据时使用时延小的链路，以保证重要信息优先到达接收端，同时增强了覆盖网络视频分发的鲁棒性；具体地，每个接收节点按照时延递增的顺序依次选择传输路径；设定节点r要求接收基本层，它首先选择时延最小的第k条路径，当该路径的带宽容量无法满足基本层的传输要求，剩余的流量将由时延次小的路径来传递；基本层的速率分配结束后，更新覆盖网络的可用带宽，继续构建高层视频流的分发网络；第m层视频分发时，为节点r进行速率分配的过程如下：步骤1.检测的值，若表示节点r无法接收第m层数据，即停止对第m层的数据分配；步骤2.若设定未分配流量R_un等于当前第m层的速率B_m；步骤3.若R_un＞0，表示第m层的速率分配还未完成，继续在P(r)中选择时延最小的路径k；步骤4.若表示路径k上的带宽容量能够承受第m层的传输速率；首先，执行路径k上的流量分配：其次，更新网络带宽，去除已分配掉的容量：步骤5.若表示仅依靠路径k的带宽量不能完成第m层的数据传输；首先，执行路径k上的流量分配：；其次，更新网络带宽：从P(r)中去除路径k；最后，更新未分配流量：；返回步骤3，执行至R_un＝0，即完成了第m层的流量分配。