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

3944 Journal of Software 软件学报 Vol.31, No.12, December 2020

现共赢的目的.所有参与博弈的用户用集合 Q={1,2,…,n}进行表示;用户 i 所有可能的采取的策略组成了一个策
略空间,用 s i 进行表示,则 S=s 1 ×s 2 ×…×s n 表示联合的策略集.在博弈过程中,任意用户 i 具有一个效用函数 F i ,其效
用值会随着策略的不同而发生变化.对于一个多人协作博弈,如果除了当前联合策略集之外,不存在其他的联合
策略能够使得每一个用户同时获得更高的效用值,这时就认为该博弈达到均衡 [31−33] .
定理 1(纳什定理 [33] ). 多人协作博弈的最优解能够满足下述 4 个特性:不变性、对称性、独立性和帕累托
最优等,其可以表述如下:
*
,
(FF * ,...,F * ) = argmax ∏ (F − F 0 ) (11)
1 2 n i i
∈
iQ
*
0
其中, F 对表示用户 i 在均衡状态下的最优收益, F 表示在非协作状态下用户 i 的收益, ∏ (F − F 0 ) 称为纳什
i i i i
∈
iQ
乘积.
4.2 效用函数设计
当多个移动节点在时刻 t 相遇时,其就组成了一个全连通的子网,相遇的节点可以利用这样的接触机会进
行视频数据传输.我们用 N 表示相遇的节点个数,M 表示它们携带的不相同的视频数据包个数,V 表示同时传输
的视频段个数.因为对任意视频段 v,其都有各自的目的节点,我们用 p n,v 表示节点 n 和视频段 v 的目的节点之间
的接触概率,用 MQG n,v,m 表示被节点 n 携带的、属于视频段 v 的视频数据包 m 的边缘质量增益,则移动节点 n
对投递质量的贡献可以用其携带的所有视频数据包的边缘质量增益之和来进行量化.因此,节点 n 的效用函数
可以设计如下:
V ⎛ M ⎞
F = n ∑ p , n v ⎜ MQG n , , v m × δ , n m ⎟∑ (12)
v= 1 ⎝ m= 1 ⎠
当节点相遇时,每个节点都希望通过这次数据交换,尽可能多地增加各自对视频重建质量的贡献,也就是
max(F − F′ n ) ,其中, F′ 表示节点 n 接触前的效用值.因此,每个节点都不会把视频数据包进行无偿直接转发;同
n
n
样,视频数据包的复制会使其备份数会增加,进而降低该数据包对视频重建质量的边缘质量增益,因此移动节点
也不愿对其携带的视频数据包进行无偿复制.因此可以说,各个节点从其自身来看是利益相悖的.而在另一方
面,所有参与视频传输的节点都希望能够完成视频传输任务,因此其都具有强烈的协作意愿.基于此,我们把多
节点相遇时其间的视频数据传输建模为一个多节点协作博弈(注:博弈的过程发生在相遇的多个节点之间,数据
包信息交换完成以后,对最优解的计算由设备资源比如能量、计算能力等最为冗余的移动节点进行承担).依据
定理 1 可知:使得纳什乘积最大的解即为纳什均衡解,其能够使得相遇的多个节点都获得最大的收益.因此,我们
可以得到如下公式:
N
β * (,δ = 1 * δ 2 * ,...,δ * N ) ← maxarg ∏ (F − n F n ) ′ (13)
n= 1
其中,F n 和 F′ 分别表示数据交换前后,节点 n 携带数据包的边缘质量增益.
n
*
*
这样,如果能够找到β ,那么每个相遇节点对视频数据包的转发和复制都可以依据β 来进行,从而实现算法
设计的目的.多人协作博弈的求解可以通过无限次的讨价还价来逼近最优解,但是计算复杂度会随着数据包个
数 M 的增加而呈指数级增加.为了解决该问题,本文提出用几何空间表示算法 [34] 去寻找最优解.
4.3 基于几何表示的纳什最优解
高的计算复杂度使得对博弈均衡的求解非常困难,而几何空间表示算法则可以较为容易地给出最优近似
解 [33] .具体来讲,每一个数据包,其相对于每一个博弈用户都存在一个对应的效用值.数据包与博弈用户之间的
距离定义为经过归一化的该效用值的倒数.数据包对应于某一博弈用户的效用值越大,则其与该用户之间的距
离越短;而效用值越小,则距离越大.
对于视频数据传输,我们用 p n,v MQG n,v,m 表示视频数据包 m 相对于节点 n 的效用值,则它们之间的效用距离
d n,m 可以计算如下: