Page 273 - 《软件学报》2020年第12期

吴红海 等:一种多用户协作博弈的视频机会传输路由算法 3939

• 数据通过机会网络进行传输时,为了提高传输质量(投递率和投递时延等),往往采用多备份的方式进行
数据投递.过多的数据备份不仅会浪费大量设备资源(存储、带宽等),同时还会增加网络传输开销,降低
投递性能.相对于一般的标量数据(温湿度等),视频数据具有较强的传输持续性和较大的数据量,所以
该问题对于视频数据传输就变得尤为突出.因此,为了有效控制数据冗余,视频数据机会传输面临的第
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] 是一种基于洪泛
的、典型的多备份路由算法,其以病毒感染的模式,通过数据包无限复制的方式进行数据传输.如果设备和网络