一种多用户协作博弈的视频机会传输路由算法*

微电子和无线通信技术的飞速发展,使得智能终端设备在近10 年间得以快速普及,而其内嵌的各种传感设备也赋予了人们对外部环境进行视频感知的能力.同时,受益于移动互联网的快速发展,视频数据可以随时随地在用户间进行分享,并能够给用户提供各种应用和服务[1-5].但是,移动设备的激增带来了移动数据流量的爆炸式增长,而其中视频数据占据了很大比重,依据思科的预测,该数值在2018 年末将达到84%[6].然而移动数据流量主要通过移动蜂窝网络(3G/4G,LTE)进行传输,尽管移动通信技术在最近几年得以长足发展,但其仍然无法满足海量的数据流在传输速率和网络容量等方面对网络的需求[7].

把需要通过移动蜂窝网络进行传输的移动数据流通过其他辅助的网络和手段进行传输和分流,称之为移动数据卸载(mobile data offloading).目前,移动数据卸载被认为是能够解决上述困境的最有效的方法[8-10].Wi-Fi热点常被用来作为移动蜂窝网络的辅助手段进行数据传输,但由于部署成本和传输距离等因素,其很难在一个广域的范围内组成一个全覆盖的无线网络提供数据传输服务.因此,如何进行便捷、高效的移动数据卸载,尤其是视频数据卸载,已成为当前学术界和工业界广泛关注的一个问题.针对该问题,本文提出通过移动机会网络,基于用户间的机会传输进行视频数据卸载.图1 给出了一个具体的应用实例.在城市区域,移动用户和配置智能终端的车辆组成一个机会网络.用户A 可以充分利用设备间的机会接触,通过无线多跳的方式把视频数据投递给用户B,而不是通过移动蜂窝网络进行数据传输.这样,通过一系列有序的D2D(device-to-device)数据通信,成功实现对蜂窝网络的视频数据卸载.

Fig.1 Example of video data offloading through mobile opportunistic networks
图1 视频数据通过机会传输实现流量卸载示例

尽管上述方法能够有效实现数据卸载,但视频数据通过移动机会网络进行传输时仍面临两个挑战性问题.

· 数据通过机会网络进行传输时,为了提高传输质量(投递率和投递时延等),往往采用多备份的方式进行数据投递.过多的数据备份不仅会浪费大量设备资源(存储、带宽等),同时还会增加网络传输开销,降低投递性能.相对于一般的标量数据(温湿度等),视频数据具有较强的传输持续性和较大的数据量,所以该问题对于视频数据传输就变得尤为突出.因此,为了有效控制数据冗余,视频数据机会传输面临的第1 个挑战就是当传输机会来临时,如何对视频数据包的复制还是直接转发进行自适应判决;

· 另一方面,多用户相遇是移动机会网络中的常态,而同时,相遇的移动用户会形成动态连通的子网,虽然其拓扑持续时间较短,但为视频数据传输提供了良好机会.因此,视频机会传输面临的第2 个挑战就是,当多用户相遇时,如何对视频数据包的转发或者复制目标进行自适应判决.

针对机会网络中一般数据的传输问题,已经存在很多算法和机制,但由于下述原因,其都无法直接适用于视频数据的机会传输:首先,视频数据在本质上和一般数据有很大差异,路由算法在设计时应充分考虑其独特性,如持续性、局部相关性等;其次,算法设计的性能目标存在较大差异,一般数据传输主要把投递率和传输时延作为性能度量的标准,而视频数据传输则把视频数据的投递质量作为路由算法设计的衡量指标,其不仅包括传输时延,同时还包括视频数据的重建质量;最后,现有机会路由算法主要考虑两节点间的数据传输,而在城市环境中,多节点相遇则是常态,考虑多节点间的数据交换,则能给数据传输质量提供更大的提升和优化空间.

因此,针对上述问题,本文提出一种基于多用户协作博弈的视频机会路由算法VOR-MG(video opportunistic routing based on multi-player cooperative game),其不仅能够使得视频传输质量最大化,同时能够降低数据包的平均最大备份数,从而使得网络的传输开销最小化.具体来讲:首先,考虑视频数据本身和网络特征对视频投递质量进行建模,并且基于该模型构建效用函数;然后,把相遇的多个节点看作是一个连通的网络,并把其间的数据交换过程建模为一个多用户协作博弈的过程;最后,基于几何空间表示方法计算出该博弈的近似最优纳什解,各相遇节点都依据该最优解分别进行数据的复制或者转发.

本文的主要贡献可以归纳如下.

· 充分考虑视频数据本身和机会网络自身的特征,建立视频数据重建质量模型;

· 基于上述模型,定义了一个全新的度量指标,即边缘质量增益,对每个视频数据包的重要性进行量化;

· 基于上述模型和度量指标,以优化视频传输质量,最小化视频传输开销为目标,提出了一种面向视频传输的机会路由协议.

本文第1 节介绍问题提出的背景、研究意义及创新性.第2 节对相关工作进行综述.第3 节介绍本文的系统模型和问题建模.第4 节讲述视频边缘质量的建模.第5 节详细介绍基于多用户博弈的路由算法,并用几何表示算法对多用户博弈进行求解.第6 节对本文的工作做简单总结.

1 相关工作

如何降低网络开销和传输代价,是数据机会传输面临的一个非常重要的问题,其从移动机会网络出现之初就引领着机会路由算法的发展,是贯穿数据机会传输研究的脉络;同时,国内外的专家和学者也较早就对该问题展开研究,并做了大量卓有成效的工作[11-24].从传输代价的角度来进行划分,移动机会网络中的路由算法可以分为两类:单备份路由算法和多备份路由算法.而多备份路由算法则可以按照数据包复制的方法进一步细分为先决性路由协议和自适应路由协议.

单备份路由协议在数据传输过程中仅仅把数据包转发给其他节点,而不产生新的备份.Direct Delivery[13]是单备份路由算法的一个典型例子,其在实施过程中,源节点只有在遇到目的节点的情况下才会把数据转发出去.First Contact[14]同样也是一种单备份协议,但其能够基于预测选择中继节点,通过多次转发进行数据投递.文献[15]的算法也属于该类型,其主要基于时间齐次的半马尔可夫模型对两个节点间的接触情况进行预测.

尽管单备份协议具有资源消耗少、网络负载低等优点,但其数据投递质量相对较差.因此,人们开始对多备份路由算法展开研究,以设备和网络资源的消耗为代价换取较高的数据投递质量.Epidemic[16]是一种基于洪泛的、典型的多备份路由算法,其以病毒感染的模式,通过数据包无限复制的方式进行数据传输.如果设备和网络资源不受限,其可以达到最优的数据投递质量(投递率和传输时延),因此也常被用来作为基准和其他算法进行比较.但是在实际应用中,设备和网络资源都是有限的,大量冗余备份对设备和网络资源的过度消耗必然会严重降低数据的投递质量,因此人们开始考虑在设计路由算法时对数据包的备份数进行限制.早期应用较为广泛的方法就是在数据包投递前就设定其传输过程中的最大备份个数,本文称之为先决性机会路由算法.Spray-and-Wait[17]是最为典型的代表,其主要包含数据包复制扩散和直接投递两个阶段:前一阶段类似Epidemic 算法,但是数据包最大备份数已经预先设定;而在后一阶段,携带副本的节点在遇到目的节点前不再对其进行转发或复制.Spray-and-Focus[18]也属于该类算法,可以看作是对Spray-and-Wait 算的改进,其最大副本数也预先设定.不同点在于:当无法继续进行复制时,携带数据包的节点可以把数据包转发给效用值较高的节点进行数据中转.除此之外,文献[19-21]中所提出的算法都属于这种类型.

通过直接限制数据包的最大备份数,先决性机会路由算法可以有效降低网络的负载和对设备及网络资源的消耗,但是其并不能保证数据投递率、传输时延等指标达到最优,因此人们提出了自适应备份机会路由算法,其能够以效用值的最优化为目标,在数据投递过程中自适应地调整网络中每个数据包的最大备份个数.Delegation Forwarding[22]是该类算法的典型代表,其通过对前一时间段内转发实例的观察,基于自由停止理论进行转发决策,从而使得数据投递性能最优而数据传输代价最小.GameR[24]则把节点间的数据交换看作是一个讨价还价的过程,利用博弈论来指导数据包的转发和复制,在保证数据投递性能的基础上,使得数据包的平均备份数最低.

但是,由于视频数据独特的特征和不同的投递质量要求,上述算法都无法用来对视频数据进行高效机会传输.VideoFountain[25]通过在一些人流量较为密集的街道上部署一些类似“小货摊”的节点用来存储多媒体数据,并通过Wi-Fi 接入点把这些数据转发给经过的用户,从而实现多媒体数据的机会传输.但是,其仅仅把多媒体数据当作是一个应用背景,路由算法的设计并没有考虑多媒体数据的任何特性.此外,还有很多与车载网中视频数据传输相关的工作,比如文献[26-28],但是车联网中的路由算法设计和一般移动机会网络的算法有很大差异,其可以充分利用城市道路的拓扑信息.

2 系统模型和问题建模

2.1 系统模型

在城市区域,所有移动用户和配置移动智能终端的车辆都可以被看作是移动节点;而从网络的角度来看,这些节点以有意识或无意识的方式组成了一个移动机会网络.视频数据通过节点间的机会接触,利用D2D 的方式进行数据传输.因此,视频数据卸载其实就是视频数据通过移动机会网络进行传输的过程.图2 给出了视频数据卸载的系统模型,其主要由两部分组成,即平台侧和用户侧.在平台侧,管理平台可以看作是部署在传统网络中的一台服务器,主要负责参与用户的招募和管理、视频数据请求和响应管理、视频数据包扩散信息收集等,其可以和移动用户通过移动蜂窝网或者Wi-Fi 网络进行通信和交互.在用户侧,所有的用户都在进行非受控自主移动,其间可以通过D2D 方式直接进行数据交换,同时,每个用户还可以通过3G/4G,Wi-Fi 接口与平台进行信息交互.当用户参与或者退出视频卸载任务,其必须及时通知管理平台,以便后者实时掌握参与用户的确切信息;同时,当携带数据发生变化时,每个用户也要把变化情况以数据包的形式上报给管理平台.由于用户和数据包的信息可以用来对效用值和用户收益进行计算,从而辅助视频数据进行投递,本文也把这些数据称为控制信息.在视频数据传输的过程中,只有控制信息可以通过传统无线网络进行传输.

在图2 中,步骤①～步骤⑤给出了视频数据卸载的流程.

· 如果一个用户想要获取一个视频段,其首先会向管理平台发送请求消息(步骤①、步骤②);

· 平台收到请求消息后,会把它发送给存储有该视频的用户(步骤③、步骤④);

· 最终,后者会通过D2D 的方式把请求的视频数据发送给请求者.

Fig.2 System model of video data offloading through mobile opportunistc transmission
图2 视频数据通过机会传输实现流量卸载

2.2 问题建模

视频数据卸载的本质就是通过移动机会网络进行数据传输,从而使得移动数据流量绕过传统的无线蜂窝网络,因此,要解决的根本问题是设计能够满足下述要求的高效视频机会路由算法:(1) 使得视频重建质量最大化;(2) 使得视频传输代价最小化;(3) 适用于多用户相遇的场景.为了对该问题进行建模,首先给出如下定义.

定义1(边缘质量增益).对于一个在网络中进行投递的视频数据包,如果其被目的节点成功接收,则会对视频重建质量产生一定的贡献.我们把该贡献称之为该视频数据包的期望边缘质量增益,用MQG(marginal quality gain)进行表示.

假设N 个节点在时刻t 相遇,这些节点共携带M 个不同的视频数据包,而这些视频数据包分别属于X 个不同的视频段.如果用二进制数δ对节点是否携带数据包进行标示,则对任意节点n(n∈{1,2,…,N}),可以用向量βn=(δn,1,δn,2,…,δn,M)标示其携带的视频数据包,向量β=(β1,β2,…,βN)标示M 个视频数据包在这N 个节点上的分布情况.我们的目标是:最大化视频数据的重建质量,同时尽可能地降低视频传输代价.因此,要解决的问题可以描述为:当节点相遇时,最大化每个节点对视频重建质量的贡献,而尽可能地降低视频数据包复制的次数.该问题可以建模如下:

其中,MQGn′,m 和MQGn,m 分别表示数据传输前后,节点n 携带的视频数据包m 的质量边缘增益;δn′,m和δn,m 分别标示数据交换前后,节点n 是否携带数据包m;β*表示最优的向量β,其属于向量空间(β1×β2×…×βN).这样,根据最优的分布向量β*,相遇的节点不仅知道数据包应该被转发还是被复制,同时还知道数据包被转发或复制的对象.

3 视频边缘质量增益模型

视频在网络中进行传输时,其首先被分割成很多视频数据包;当足够多的视频数据包被目的节点接收,则该视频数据就可以进行重建.在视频数据传输过程中,参与节点都会对其携带的数据包进行复制或者转发,但是去量化节点转发或者复制一个视频数据包对视频重建质量的贡献是非常困难的,原因主要来自于视频数据本身和传输网络.本节将综合这两个方面的因素进行建模.

3.1 视频数据的帧结构

每个视频段都可以分成多个GoP(group of pictures),而属于同一视频段的GoP 都具有相同的帧结构[29].图3给出了一个GoP 的帧结构示例,其由固定数量的I 帧、P 帧和B 帧按照固定的顺序组成.帧的个数原则上可以是任意整数,为了方便描述,本文以9 为例,每个帧依次分别被标注为I1,B1,B2,P1,B3,B4,P2,B5,B6.当视频数据在网络中传输时,每一个帧会被分割成多个数据包,因此,网络中存在I,B 和P 这3 种类型的视频数据包.

Fig.3 Example of a GoP structure of video data
图3 视频数据的GoP 结构示例

由于压缩技术的应用,同一GoP 中的帧间存在很强的相关性,其使得不同的帧对视频数据的重建具有不同的重要性,从而使得来自不同帧的视频包也相应地具有不同的重要性.具体来讲:I 帧是参考帧,当其数据包被成功投递以后可以独立重建;P 帧是前向预测帧,其重建不仅需要成功接收其数据包,同时还依赖于其前一I 或P帧的成功恢复;B 帧是双向预测帧,其重建要依赖于前后两个视频帧的成功恢复.如图3 所示,P2 重建依赖于P1,而B2 的重建则依赖于I1 和P1.

3.2 视频机会传输重建质量模型

节点每次对视频数据包的转发和复制都会对视频重建质量产生一定的增益.为了对该增益进行量化,首先必须选择合适的度量指标.PSRN 常被用来对视频质量进行量化,但其无法适用于移动机会网络.原因在于:当属于某一个帧的视频数据包尚未完全接收时该帧就无法重建,从而无法计算其PSNR.因此,本文提出了一个新的度量标准,即帧投递率,对视频的投递质量进行量化.

定义2(帧投递率).对于一个在网络中进行投递的视频段,其帧投递率定义为在目的节点成功重建的视频帧的数目与投递的所有视频帧数量之间的比值,用变量FDR(frame delivery rate)进行表示.

假设对于一个视频段,NG 表示其GoP 个数,NT 表示其总的视频帧个数;MI,MP,MB 分别表示每个I,P,B 帧可以被平均分割成的视频数据包个数;RI,RP,RB 分别表示I,P,B 这3 种类型的视频数据包的成功投递概率;NI,NP,NB分别表示成功投递的I,P,B 帧的期望值.则,可以得到下述公式:

当一个视频段被分割并在网络中进行传输时,与其相关的参数,比如NG,MI,MP,MB 都是已知的,因此,帧投递率可以看作是以RI,RP,RB 为变量的函数,即:

在视频传输的过程中,假设在时刻t 网络中不相同的I 类型的视频数据包个数为KI(t),且具有相同的TTL(time-to-live)值;对任意I 类型的视频数据包i,TI,i(t)表示在时刻t 该数据包已经消耗的生命时长,MI,i(TI,i(t))表示曾经收到过该视频数据包的节点个数,NI,i(TI,i(t))表示当前仍然携带该视频数据包的节点个数,RI,i(t)表示该视频数据包剩余的生命时长;此外,NS 表示所有参与视频传输的节点个数.那么,下述关系成立:

由于节点间的接触时间间隔服从接触频率λ的指数分布[29,30],该视频数据包i 不能被投递成功的概率等于其任何一个备份数据包与目的节点下一次相遇的时间都大于RI,i(t)的概率,即exp(-λRI,i(t)).因此,用PI,i 表示I类型的视频数据包i 在其生存时间内能够被成功投递的概率,则有:

3.3 视频数据包边缘质量增益

在视频传输过程中,任意未被成功接收的视频数据包对视频重建质量都有一个期望的增益.据公式(6)、公式(8)可知,视频的帧投递率实际上是其视频数据包备份数的函数.对任意视频数据包,其备份数增加或者减少,该函数值都会发生变化.我们把某一视频数据包备份数的单位变化而导致的帧投递率变化的大小称为该视频数据包相对于视频重建质量的边缘增益.边缘增益可以通过偏微分方程离散化进行计算.

对任意I 类型的视频数据包i,其在t 时刻的边缘质量增益计算如下:

4 基于多用户博弈的路由算法设计

本文路由算法设计的初衷是最大化视频数据的传输质量,同时尽可能地降低视频数据传输的代价.为达到该目的,我们把多用户间的视频传输建模为一个多用户协作博弈,利用Nash Pareto 优化理论给出最优解决方案.

4.1 多人协作博弈

多人协作博弈是一个非零和博弈模型,每一参与博弈的对象都是理性和自私的,并希望通过竞争和妥协实现共赢的目的.所有参与博弈的用户用集合Q={1,2,…,n}进行表示;用户i 所有可能的采取的策略组成了一个策略空间,用si 进行表示,则S=s1×s2×…×sn 表示联合的策略集.在博弈过程中,任意用户i 具有一个效用函数Fi,其效用值会随着策略的不同而发生变化.对于一个多人协作博弈,如果除了当前联合策略集之外,不存在其他的联合策略能够使得每一个用户同时获得更高的效用值,这时就认为该博弈达到均衡[31-33].

定理1(纳什定理[33]). 多人协作博弈的最优解能够满足下述4 个特性:不变性、对称性、独立性和帕累托最优等,其可以表述如下:

其中对表示用户i 在均衡状态下的最优收益,Fi 0表示在非协作状态下用户i 的收益称为纳什乘积.

4.2 效用函数设计

当多个移动节点在时刻t 相遇时,其就组成了一个全连通的子网,相遇的节点可以利用这样的接触机会进行视频数据传输.我们用N 表示相遇的节点个数,M 表示它们携带的不相同的视频数据包个数,V 表示同时传输的视频段个数.因为对任意视频段v,其都有各自的目的节点,我们用pn,v 表示节点n 和视频段v 的目的节点之间的接触概率,用MQGn,v,m 表示被节点n 携带的、属于视频段v 的视频数据包m 的边缘质量增益,则移动节点n对投递质量的贡献可以用其携带的所有视频数据包的边缘质量增益之和来进行量化.因此,节点n 的效用函数可以设计如下:

当节点相遇时,每个节点都希望通过这次数据交换,尽可能多地增加各自对视频重建质量的贡献,也就是其中, Fn′表示节点n 接触前的效用值.因此,每个节点都不会把视频数据包进行无偿直接转发;同样,视频数据包的复制会使其备份数会增加,进而降低该数据包对视频重建质量的边缘质量增益,因此移动节点也不愿对其携带的视频数据包进行无偿复制.因此可以说,各个节点从其自身来看是利益相悖的.而在另一方面,所有参与视频传输的节点都希望能够完成视频传输任务,因此其都具有强烈的协作意愿.基于此,我们把多节点相遇时其间的视频数据传输建模为一个多节点协作博弈(注:博弈的过程发生在相遇的多个节点之间,数据包信息交换完成以后,对最优解的计算由设备资源比如能量、计算能力等最为冗余的移动节点进行承担).依据定理1 可知:使得纳什乘积最大的解即为纳什均衡解,其能够使得相遇的多个节点都获得最大的收益.因此,我们可以得到如下公式:

其中,Fn 和 Fn′分别表示数据交换前后,节点n 携带数据包的边缘质量增益.

这样,如果能够找到β*,那么每个相遇节点对视频数据包的转发和复制都可以依据β*来进行,从而实现算法设计的目的.多人协作博弈的求解可以通过无限次的讨价还价来逼近最优解,但是计算复杂度会随着数据包个数M 的增加而呈指数级增加.为了解决该问题,本文提出用几何空间表示算法[34]去寻找最优解.

4.3 基于几何表示的纳什最优解

高的计算复杂度使得对博弈均衡的求解非常困难,而几何空间表示算法则可以较为容易地给出最优近似解[33].具体来讲,每一个数据包,其相对于每一个博弈用户都存在一个对应的效用值.数据包与博弈用户之间的距离定义为经过归一化的该效用值的倒数.数据包对应于某一博弈用户的效用值越大,则其与该用户之间的距离越短;而效用值越小,则距离越大.

对于视频数据传输,我们用pn,vMQGn,v,m 表示视频数据包m 相对于节点n 的效用值,则它们之间的效用距离dn,m 可以计算如下:

从距离的计算公式可以看到:如果视频数据包相对于博弈用户的重要性或价值更大,则其与该节点的效用距离将越短,并且它对该节点具有更高的优先级.因此,相对于任意一个节点n,都可以把这些视频数据包按照其对该节点的效用距离,按照从小到达的顺序进行排列,而得到一个列表Ln.

据文献[34]可知:分配一个效用值过小或者过高的数据包给一个博弈用户,都会使得均衡偏离帕累托最优点;而如果按照效用值从高到低的顺序对每一个数据包进行遍历,又将会极大增加计算复杂度.为了解决该问题,其提出了效用距离乘积的概念.具体来讲,针对视频数据传输,经过归一化的视频数据包m 相对于博弈用户n的效用距离乘积φn,m 可以计算如下:

从上式可以看出:对一个给定的视频数据包,其对应于所有的博弈用户都具有相同的效用距离乘积.则依据文献[33]的均衡条件可以表示如下:

其中,un 是用来决定视频数据包分配终止的门限条件.

这样,可以从对应于移动节点n 的列表Ln 中选取前K 个视频数据包分配给n,使得这K 个视频数据包对节点n 的效用距离之和刚刚达到临界值un,也即K 应该满足下述条件:

这样,所有相遇节点都知道哪些视频数据包需要被转发或者被复制给哪一个节点.在分配过程中,一个效用值较高的视频数据包可能被分配给多个节点,因此,这些视频数据包会被复制,但是副本的数量由纳什近似最优解决定;另一方面,个别重要性很低的视频数据包可能不会被分配给任何一个用户,其将会被丢弃.

5 仿真和性能验证

如前所述,目前,关于视频数据机会传输方面的研究还相对比较有限.与本文较为相近的机制为GameR[24],其也考虑多节点相遇的场景,但仅限于一般数据的传输.另外一个要进行比较的传输机制是我们所提算法VOR-MG 的一个变种,即VOR-TG,其也用来对视频数据进行传输,但是仅限于两个节点相遇时的数据交换.此外,由于是多备份的算法,我们也和Epidemic[16]进行了对比.

5.1 仿真环境介绍

为了对性能进行验证,我们基于NS-2 网络仿真工具开发了一个类似DTN 网络的仿真环境.在这个仿真环境中,每个节点被当作一个移动用户,其有效传输距离被设为是100 米,可以基于802.11b 与其他节点进行通信.每个节点的存储空间被划分为两个队列:第一个队列用于存放由其自身生成的视频分组,而另一个队列用于缓存从其他节点接收的视频分组.这两个队列具有相同的长度,最多可以存放128 个视频分组.为了对视频传输进行模拟,我们选用标准的视频序列“foreman.qcif”作为数据源.此外,为了更加方便地对视频数据进行传输,我们把工具myevalvid[35]也集成到该仿真环境.借助于该工具,视频数据源可以被分割成659 个视频分组,并依照他们在原始视频序列中的位置和时间间隔被发送到网络中去.同样,借助于该工具,被传输的视频数据可以很方便地得以重建.

5.2 基于合成移动轨迹数据集的性能分析

人工合成轨迹数据集基于移动模型Random Waypoint 生成,共包含60 个移动节点,运动区域为1000×1000 m2.在每一次仿真实验中,每个节点都具有相同的生存时长(TTL),源节点和目的节点随机选择.

图4 给出了和传输质量相关的仿真结果,主要从平均帧投递率和平均PSNR 两个方面进行对比.从图4(a)可以看到:当TTL 设定为不同的数值时,Epidemic 的平均帧投递率最低,而我们的算法则表现最优.尽管算法GameR 的平均帧投递率要远高于Epidemic,但其和VOR-TG 之间仍存在一定的距离.从总体上看,每个算法的平均帧投递率都会随着TTL 值得增加而增大.原因可以解释如下:由于无限制的节点复制,Epidemic 很快就耗尽了设备的资源,大量的视频数据包在传输过程中由于缓冲区溢出而被丢弃,因此表现出最差的投递性能.GameR 算法主要用来进行一般数据的传输,其设计目标是实现高的数据投递率,而不是视频投递质量,设计过程也未考虑任何视频数据的特点,因此其视频投递性能落后于本文所提出的算法VOR-MG 和其变种算法VOR-TG.而VOR-MG 和VOR-TG 之间的差异在于:前者是对多个节点之间的数据交换进行优化,而后者则仅关注一对节点之间的数据交换,因此会有如图4(a)所示的性能表现.此外,为了使得上述算法的性能比较更加直观,我们也给出了其基于平均PSNR 的对比结果,如图4(b)所示.从图上可以看出,各个算法和后文图5(a)有相同的性能表现,这也验证了我们设计帧投递率的合理性.

Fig.4 Performance comparisons based on random mobity trances
图4 基于人工合成数据集的仿真性能对比

5.3 基于真实移动轨迹数据集的性能分析

为了在更加真实的情况下对算法性能进行验证,我们基于真实的移动轨迹KAIST[36]进行仿真.该数据集包含92 个节点,活动范围为10000×10000m2.为了观察并行传输的视频段个数对算法性能的影响,我们设定视频段个数为1 和5 分别进行仿真.

图5 和图6 分别给出了平均帧投递率和平均PSNR 的数据对比.

Fig.5 Comparisons of average FDR based on real mobity traces
图5 基于真实数据集的平均帧投递率对比

Fig.6 Comparisons of average PSNR based on real mobity traces
图6 基于真实数据集的平均PSNR 对比

除了在图4 中呈现的性能性能趋势,从这些图上还可以看到:随着并行传输的视频数量的增加,所有算法的性能都有不同幅度的回落.VOR-MG,VOR-TG 和GameR 回落幅度较小(平均帧投递率:0.01,平均PSRN:0.4dB 左右),而Epidemic 回落幅度较大(平均帧投递率:0.023,平均PSRN:1.5dB 左右).原因可以解释如下:随着并发传输的视频段的增加,节点设备资源变得越来越紧张;节点缓冲区较快溢出而不能继续容纳Epidemic 无限复制的大量数据备份,从而降低了视频的投递质量;而其他3 个算法都采取受控的数据包复制算法,网络中的冗余数据包相对较少,所以并行视频段的增加对其性能的影响较为有限.

为了能够更加直观地对上述算法对设备资源的消耗进行对比,图7 给出了每种算法在视频传输过程中的平均最大转发次数(并发传输的视频段个数等于5).从图上可以看出:如果把TTL 设定为2 000s,Epidemic 的平均最大转发次数能够达到80,而GameR 和VOR-MG 能够接近20,VOR-TG 则接近30.这个结果符合我们对Epidemic 算法的预期.尽管其他3 种算法都是进行受控复制,但是VOR-TG 仅仅考虑两个节点间的数据转发和复制,而没有对多节点相遇的场景加以考虑,因此其平均最大复制次数高于算法GameR 和VOR-MG.

Fig.7 Comparisons of average maximum of video packet replication based on real mobity traces
图7 基于真实数据集的视频数据包最大平均转发次数对比

6 总结

移动数据卸载是近年来的一个备受关注的研究课题,而基于D2D 通信的数据机会传输被认为是解决这一问题的理想方法.然而,由于智能终端用户移动和接触的不确定性,使得视频数据的机会传输最终归结为一个路由设计问题.在本文中,我们提出了一种面向视频质量的路由算法VOR-MG,用于解决移动机会网络中的视频数据高效传输问题.该算法把多用户间的数据传输建模为多用户协作博弈,利用纳什近似最优解来引导视频数据包的复制和转发,从而在实现最大化视频传输质量而最小化视频传输代价的目的.算法的性能在人工合成的数据集和真实数据集上都得到验证.