基于可伸缩视频流用户体验质量的D2D网络搭建方法

摘要

一种基于可伸缩视频流用户体验质量的D2D网络搭建方法，将D2D通信组织为一个传输可伸缩自适应视频流的生成树。在初始化阶段，将这个D2D网络组织为一棵拥有可接受的用户体验质量和公平性的生成树。在管理阶段，在不同的设备到达或离开的情况下分别维护服务的连续性。基于局部搜索技术，该方案结合了不相交集的数据结构和局部搜索技术，能够达到O(mnα(m,n))的运行时间。该方案能够提供高服务网络的容量，并保证服务的体验质量、公平性和连续性，能够支持大量用户。

说明书

技术领域

本发明提出了一种基于可伸缩视频流的D2D多媒体网络搭建方案(称为DMaster)，将D2D通信组织为一个传输基于自适应可伸缩视频流的生成树。该方案能够提高服务网络的容量，并保证服务的体验质量、公平性和连续性，能够支持大量用户。

背景技术

由于通信网络对高带宽需求的不断增加，与视频流有关的通信服务出现了许多相关的问题。一般情况下，用户通过移动设备访问网络，通过蜂窝链路连接到互联网。但是，由于大量的移动终端加入到带宽要求很高的服务中，固定网络的接入点几乎不能为每个用户提供高效的比特率。此外，移动用户总是有特定的用户体验质量要求。在这种情况下，用户之间的用户体验质量和公平问题是服务提供商的主要考虑因素。

为了支持一个庞大的用户群，D2D广泛地被研究界认为是一个有效的方法。由于D2D适用于扩展覆盖范围，减轻通信量，并通过提高频谱效率来实现高用户体验质量的服务，因此在第五代(5G)网络工程中已经引起了无线通信界的极大关注。N.Lee等人在“Powercontrol for D2D underlaid cellular networks:modeling,algorithms,and analysis”中提出了一个功率控制策略，以最大限度地提高D2D链路的数量。在“Incentivizingsharing in realtime D2D streaming networks:A mean field game perspective”中，设计了一个激励框架用来促进D2D服务。因此，我们考虑使用D2D通信来支持大量用户并提供高用户体验质量服务。

为了满足不同用户的需求，提高客户的用户体验质量，一些关键技术被提出。A.Bentaleb等人在“SDNDASH:Improving QoE of HTTP adaptive streaming usingsoftware defined networking”中提供了高品质的视频服务，传输HTTP自适应流，这被越来越频繁地采用，并成为一类视频流标准。H.264/SVC视频流可伸缩视频流被专门设计用于增强视频编码，并已被应用到新的访问模型中以改进用户体验质量。通过在包含不同视频分辨率的编码流中生成各个层的方式，它提供了一种在不同分辨率下传输一个视频的有效方法。低分辨率视频只需要基层，高分辨率视频需要基层和增强层。

但是，现有的工作很少关注可伸缩视频流和D2D通信的整合。由于不同用户有不同的用户体验质量需求，将可伸缩视频流引入D2D通信必须考虑相邻用户的用户体验质量，这是一个理论和实际的难题。此外，移动设备在一般情况下是不稳定的，这会导致拓扑变化，并严重影响其他相邻用户的服务连续性。以往的工作，要么不符合实际情况，要么需要较高的运行时间。

发明内容

针对现有技术中存在的上述不足，本发明的目的是提供一种基于可伸缩视频流用户体验质量的D2D网络搭建方法，该方法所适用的系统是一个大规模的D2D群，由大量移动设备组成，在一个目标区域中，设备之间以可伸缩视频流进行流传输；该方法同时关注以用户体验质量为目标的多媒体流服务管理，适用于结合了D2D和可伸缩视频流的移动设备。

为实现上述目的，本发明采用了如下技术方案。

一种基于可伸缩视频流用户体验质量的D2D网络搭建方法(简称为D2D网络搭建方案(DMaster))，包括初始化和管理两个阶段。包括以下步骤：

初始化阶段：将D2D网络组织为一棵拥有可接受的用户体验质量和公平性的生成树；

管理阶段：在不同的设备到达或离开D2D网络的情况下，分别维护D2D网络服务的连续性。

优选地，所述的初始化阶段为：把用户体验质量问题建模成最小化的优化问题，将用户公平性设置为限制条件，则：

优化目标：最小化其中：E表示树T中的树的边的集合，E_d表示用户体验质量决定函数，表示设备的度函数，d表示树中任意设备，s表示设备d接收的SVC视频流层数，表示在树T中的设备d的度，T表示初始化后的服务的生成树；

限制条件1：其中：f(QoE)表示若干面向用户的体验指标的加权；

限制条件2：其中R表示生成树中设备负载的极差，其体现了用户公平性，极差R越小，公平性越强。

优选地，所述的初始化阶段，具体包括以下步骤：

步骤S0，给定一组在目标区域中被建模为无向图G的设备，G＝(D,L)，其中，D表示一组设备的集合，L表示潜在链接的集合；定义转发数据的设备为可育设备，不转发数据的设备为不育设备；

步骤S1，为图G中的可育设备构建初始化后的服务的生成树T，并将不育设备连接到树T上；

步骤S2，将集合L以非递减排序，Low初始化为0；其中，Low为参数，其初始值为0，在后续满足条件时逐1递增；

步骤S3，L_t赋值为树T的负载；

步骤S4，对集合D中所有的设备d，若d为可育设备，则重复步骤S5和步骤S6；

步骤S5，如果满足函数为真，其中，L_t表示树T的负载，表示用户体验质量决定函数，L为递增序列，包含全部设备所有可能的负载的值；

步骤S6，调用函数Adjust-Tree()后返回步骤S3重复执行步骤S3至步骤S5；其中，函数Adjust-Tree()表示调整树结构的函数。

优选地，所述的函数Adjust-Tree()具体包括如下步骤：

步骤S61，初始化：设W为负载大于L[Low]的设备的集合，S为负载等于L_t的设备的集合；

步骤S62，构造一个有|L|个元素的序列，其中第M[i]个元素是一串满足条件的节点的链表；

步骤S63，在集合S中任意选取一个设备d作为根，利用BFS算法初始化每个设备的depth、parent、old、new指针，其中，depth为设备在树中的深度；parent为设备在树结构上的父节点；old为算法中作为标记的指针，其含义为可能会被从树中去除的边；new为算法中作为标记的指针，其含义为可能会被添加到树中的边；

步骤S64，对所有属于集合D但不属于集合W的节点x调用函数Make-Set(x)；其中，函数Make-Set(x)表示并查集中经典的建立集合操作；

步骤S65，对所有边如果是树边，则调用函数Union(x,y)，否则调用函数Q.add(x,y)；其中，函数Union(x,y)表示合并两个并查集的操作，函数Q.add(x,y)表示将边(x,y)添加到集合Q中；

步骤S66，如果集合Q非空，则调用函数Q.deleteFirst()并将返回值赋给边(u,v)，调用函数Link-Merge(u,v)返回值赋给ω；否则进入步骤S67；其中，函数Q.deleteFirst()表示从集合Q中删除其头部的节点并返回该节点，Q表示符合要求的边的集合；u、v表示边的两个端点，函数Link-Merge(u,v)表示调整树结构的关键操作，ω表示经函数Link-Merge(u,v)调用后返回的节点；

步骤S67，Low自增1，对所有设备x∈M[Low]∩W，若则返回，否则调用函数Device-Merge(x)；其中，E_x表示用户体验质量决定函数，函数Device-Merge(x)表示调整树结构的操作；

步骤S68，循环执行步骤S66和步骤S67，直到ω不为NULL；

步骤S69，调用函数Reduce(ω)；其中，函数Reduce(ω)表示对树进行删减、增添边的操作，具体步骤见权利要求7。

优选地，还包括如下步骤：调用函数Device-Merge(x)调整树T的结构，包括以下步骤：

步骤a，从集合W中移除节点x，然后调用函数Make-Set(x)；

步骤b，对每个节点若(x,y)为树边，则调用函数Union(x,y)，否则调用函数Q.add(x,y)。

优选地，还包括如下步骤：调用函数Link-Merge(x,y)调整树T的结构，包括以下步骤：

步骤A，判断函数Find-Set(x)与函数Find-Set(y)之间的关系，如果Find-Set(x)＝＝Find-Set(y)，则返回NULL；其中，函数Find-Set(x)表示返回x所在的并查集的公共祖先，函数Find-Set(y)表示返回y所在的并查集的公共祖先；

步骤B，赋值u∶＝LCA(x),v∶＝LCA(y),ω∶＝NULL；其中，LCA表示设备所在的并查集的公共祖先；

步骤C，若u.depth<v.depth，则交换u和v；

步骤D，若u∈W，则调用函数Device-Merge(u)；而后若u∈S并且ω＝＝NULL，则将u赋值给ω；

步骤E，若u.parent∈W，则赋值u.parent.old:＝(u,u.parent)；u.parent.new:＝(x,y)；u:＝u.parent否则赋值u:＝LCA(u.parent)；

步骤F，循环执行步骤C至步骤E，直到u＝＝v；

步骤G，返回ω。

优选地，还包括如下步骤：调用函数Reduce(ω)调整树T的结构，包括如下步骤：

若ω.old≠NULL，则将ω.new指向的边添加到树T中，并将ω.old指向的边从树T中移除；赋值(u,v):＝ω.new；对u、v分别调用函数Reduce(u)与Reduce(v)。

优选地，所述的管理阶段为：为支持对设备的加入和离开管理，包括以下两个步骤：

-保证服务的连续性；

-完善所改变的树的分支的局部结构。

优选地，所述的管理阶段，具体包括以下步骤：

步骤s0，定义转发数据的设备为可育设备，不转发数据的设备为不育设备；

步骤s1，当任意一个设备d₁到达的时候，将设备d₁连接到任意可育设备t₁；若满足函数Satisfy(t₁)＝＝false，则调用函数Adjust-Tree()并赋值S:＝{t₁}；其中，Satisfy(t₁)表示判断是否满足条件，函数具体内容与步骤S5中相同，S表示函数Adjust-Tree()返回的满足条件的设备的集合；

步骤s2，当可育设备d₂离开的时候，对所有可育设备d₂的后代节点中的设备t₂执行步骤s3；

步骤s3，若(t₂,τ)∈LE∩τ.depth≤d₂.depth则执行步骤s4，否则执行步骤s5；其中，τ表示与t₂之间存在边联系的设备节点；

步骤s4，连接t与τ，若Satisfy(τ)＝＝false，则调用函数Adjust-Tree()并赋值S:＝{τ}；

步骤s5，基站采取控制。

与现有技术相比，本发明具有如下有益效果：

1、运行时间复杂度低，可达运行时间是O(mnα(m,n))；提高了服务的用户体验质量，保障公平性和连续性，支持大量用户。

2、从服务提供商角度考虑问题，模型架构配合所提出的算法更适用于服务提供商。

附图说明

通过阅读参照以下附图对非限制性实施例所作的详细描述，本发明的其它特征、目的和优点将会变得更明显：

图1为用户带宽使用时流质量的变化示意图；

图2为室内场馆模拟实验的示意图；

图3为不育设备的服务时间示意图，其中，(a)为短测试视频，(b)为长测试视频；

图4为可育设备的服务时间示意图，其中，(a)为短测试视频，(b)为长测试视频；

图5为DMaster的性能评价实验的仿真结果，其中，(a)为各设备的用户体验质量指数，(b)为用户体验质量指数随设备数量变化曲线。

具体实施方式

下面对本发明的实施例作详细说明：本实施例在以本发明技术方案为前提下进行实施，给出了详细的实施方式和具体的操作过程。应当指出的是，对本领域的普通技术人员来说，在不脱离本发明构思的前提下，还可以做出若干变形和改进，这些都属于本发明的保护范围。

实施例

本实施例所适用的系统是一个大规模的D2D群，由大量移动设备组成，在一个目标区域中，设备之间以可伸缩视频流进行流传输。

本实施例关注以用户体验质量为目标的多媒体流服务管理，适用于结合了D2D和可伸缩视频流的移动设备。为了提供这种服务，设计一个新颖的D2D网络搭建方案(DMaster)，包括初始化和管理两个阶段。

由于在D2D网络系统中的设备d的用户体验质量非常依赖于它的度和对其后代的可伸缩视频流所需的层数，因此设计一个用户体验质量决定函数为：其中由D接收的可伸缩视频流层数是s，f(QoE)是一种面向用户的加权积分，包括包错误率，能量限制，服务延时，视频质量和品质变化的影响。定义转发数据的为可育设备，不转发数据的为不育设备。特别是，对于所有不育设备，指定E_d(1,s)＝0，并且E_d(x,s)＝∞,此外，被定义为的平均值，

定义1：生成树T＝(D,E)的负载函数定义为：其中是在树T中的设备d的度。

定义2：(D2D服务初始化问题)给定一组在目标区域中被建模为图G＝(D,L)的设备，每个设备d有一个用户体验质量决定函数因此目标是找到一个拥有最小负载函数的生成树T＝(D,E)。

优化目标：最小化

限制条件：其中f(QoE)包含了若干面向用户的体验指标的加权。

在初始化阶段，将这个D2D网络组织为一棵拥有可接受的用户体验质量和公平性的生成树。这个问题被证明是NP完全的。基于局部搜索技术，结合了不相交集的DMaster能够达到O(mnα(m,n))的运行时间，其中m为边数，n为设备的数量，α为逆阿克曼函数。在管理阶段，Dmaster负责在不同的设备到达或离开的情况下分别维护服务的连续性。

一般情况下，对于给定的一组由无向图组成的设备G＝(D,L)，假设可伸缩视频流层数最多是因此需要将这个系统初始化为一个生成树T＝(D,E)，其中G是初始图，不分配D2D链接，D是一组设备，L是潜在链接的集合，T是初始化后的服务的生成树，E是T中的树的边的集合。为了维护这棵树，必须考虑到几个情况，包括可育设备的到达，可育设备的离开，不育设备到达，和不育设备离开。

下面对本实施例进一步详细描述。

本实施例方案包括初始化和管理两个阶段：

A.初始化阶段

在初始化阶段，提出了几个基于局部搜索的操作来解决服务初始化问题。

在本实施例方案中，首先构造一棵任意树并通过函数Adjust-Tree()反复调整它的结构，直到存在一个可育设备d，满足小于L[Low]并且当其度增加1时，不小于树的负载L_t。其中集合L定义为：以递增的顺序维护L中的元素，细节见算法1。

算法1：初始化阶段的Dmaster算法

1)为G中的可育设备构建一棵任意的树T，并将不育设备连接到树T上；

2)将集合L以非递减排序，Low初始化为0；

3)L_t赋值为树T的负载；

4)对D中所有的设备d，若其为可育设备，则重复步骤5)和6)；

5)如果则返回树T，否则进入步骤6)；

6)调用函数Adjust-Tree()后返回步骤3重复执行；

算法2：关于函数Adjust-Tree()

1)初始化：W为负载大于L[Low]的设备的集合，S为负载等于L_t的设备的集合；

2)构造一个有|L|个元素的序列，其中第M[i]个元素是一串满足条件的的链表；

3)在集合S中任意选取一个设备d作为根，利用BFS算法初始化每个设备的depth,parent,old,new指针；

4)对所有属于DW的节点x调用函数Make-Set(x)；

5)对所有边如果是树边，则调用Union(x,y)，否则调用Q.add(x,y)；

6)循环调用步骤7)和8)，直到ω不为NULL；

7)如果Q非空，则调用Q.deleteFirst()并将返回值赋给边(u,v)，调用Link-Merge(u,v)返回值赋给ω；否则进入步骤8)；

8)Low自增1，对所有设备d∈M[Low]∩W，若则返回，否则调用Device-Merge(d)；

9)调用Reduce(ω)；

在算法2中，本实施例建立和维护两个设备子集S和W，并有同时，T被W中的设备划分为连通分支，而链表Q是一个边的子集，其中包含的非树边(x,y)连接着属于集合T但不属于集合W的两个连通分支。本实施例不断选择Q中的一条边，以取代一条通过算法4找到的连接着S中设备的树边。为了表示连通分支，本实施例利用了标准的不相交集的数据结构与其一些经典的操作：构造(Make-Set)，搜索(Find-Set)，和合并(Union)。LCA(x)是用来计算包含节点x的连通分支的最近共同祖先的操作。

算法3到算法5是三个协助树结构调整的操作。设备合并函数Device-Merge(x)将x合并到与之相关的连通分支中。链路合并函数Link-Merge(x,y)将从x和y的路径分别遍历到两者的最近公共祖先，更新集合W中设备的指针，并返回一个可能的设备ω来减少度。操作Reduce(x)添加非树边并移除连接到x的另一条边，这将使x的度数至少减少1。

算法3：Device-Merge(x)

1)从集合W中移除x，然后调用Make-Set(x)；

2)对每个节点若(x,y)为树边，则调用Union(x,y)，否则调用Q.add(x,y)；

算法4：Link-Merge(x,y)

1)如果Find-Set(x)＝＝Find-Set(y)，则返回NULL；

2)赋值u∶＝LCA(x),v∶＝LCA(y),ω∶＝NULL；

3)循环执行步骤4)～6)，直到u＝＝v；

4)若u.depth<v.depth，交换u与v；

5)若u∈W，则调用Device-Merge(u)；而后若u∈S并且ω＝＝NULL，则将u赋值给ω；

6)若u.parent∈W，则赋值u.parent.old:＝(u,u.parent)；u.parent.new:＝(x,y)；u:＝u.parent否则赋值u:＝LCA(u.parent)；

7)返回ω

算法5：Reduce(x)

1)若x.old≠NULL，则将x.new指向的边添加到树T中，并将x.old指向的边从树T中移除；赋值(u,v):＝x.new；调用函数Reduce(u)与Reduce(v)；

B.管理阶段

为支持对可育和不育设备的加入和离开管理，主要保证两点:(1)必须保证服务的连续性；(2)需要尽快完善本地的结构。对于设备的到达，结合了可育和不育的情况下，并对于不育设备的离开，没有必要去细化结构。最坏的情况是可育的设备离开时，其他可育的设备不能在没有服务延迟的情况下接管其子树，这就是为什么基站必须采取控制的原因。由于函数Ajdust-Tree()适合对结构进行微调，仍然调用该函数。细节在算法6展示，

算法6：管理阶段的DMaster

1)当设备d到达的时候，将设备d连接到任意可育设备t；若Satisfy(t)＝＝false则调用函数Adjust-Tree()并赋值S:＝{t}；

2)若设备d为可育节点，则其离开的时候，对所有d的后代节点中的设备t执行步骤3)；

3)若(t,τ)∈LE∩τ.depth≤d.depth则执行步骤4)，否则执行步骤5)；

4)连接t与τ，若Satisfy(τ)＝＝false则调用函数Adjust-Tree()并赋值S:＝{τ}；

5)基站采取控制；

模拟实验结果

本实施例在图2所示的室内场馆中部署了模拟实验，在这里，随机选择几个持有不同设备的志愿者组成一个D2D通信网络。为了对多媒体传输进行建模，选择了两个参考源视频文件：“Big Buck Bunny”它的预告片文件，分辨率为480p、720p和1080p，这是多媒体传输领域的标准测试文件。由于信道很容易受到网络环境的干扰，两个测试设备之间的适用范围不超过14m，执行5次传输，以获得平均统计数据。

由于现成的无线设备不能同时通过D2D通信等方式来支持接收和转发，所以进行了分段传输，然后将传输时间和期望的延迟时间合并在一起，得出可靠的结果。结果在图3(a)、图3(b)、图4(a)和图4(b)中给出。

在图3(a)和图3(b)中，与目前的WIFI传输时间t_W相比，不育设备的平均服务时间t_D随着其普通父设备的增加而扩展。当更多的不育设备参加服务时，虽然t_D/t_W增加了，但最好在可育设备的度小于5时提供D2D服务。图4(a)和图4(b)表明，与目前的WIFI传输时间相比，在一个可育设备中完成的一个服务的总传输时间t_D明显缩短。图4(a)及图4(b)显示，多媒体传输方案在高服务质量上表现很好。这个实验在一个真实的环境中验证了本实施例方法的效率。

此外，通过模拟D2D服务网络的初始化来评估DMaster的性能。在模拟中，设备是在2D虚拟空间中随机生成的。根据图5(a)，由DMaster初始化的n＝20设备的用户体验质量索引通常比随机树结构高得多。同时，DMaster所实现的用户体验质量的波动性也很低，在很大程度上保证了用户的公平。图5(b)表示平均用户体验质量指数与DMaster或随机树结构所服务的设备数量之间的关系，其中n从10到100取值间隔期间为10。在每个案例中进行了50次模拟，平均结果表明，即使服务规模很大，DMaster也能保持50％用户体验质量，而随机树的用户体验质量则迅速减少。因此，DMaster能够通过支持众多设备来扩大服务能力，提高服务提供商的收入。

以上对本发明的具体实施例进行了描述。需要理解的是，本发明并不局限于上述特定实施方式，本领域技术人员可以在权利要求的范围内做出各种变形或修改，这并不影响本发明的实质内容。