信息不可见混合式接入网络纳什均衡问题的研究①

刘 俊 余 靖 齐佳兴 金顺福

(燕山大学信息科学与工程学院 秦皇岛 066004)

0 引 言

随着移动电子设备的普及，移动用户希望在任意时间和任意地点访问互联网，因此对混合式接入网络的需求越来越大[1]。如何科学、高效和均衡地使用混合式接入网络，成为相关领域的研究热点。

针对cellular网络、Wi-Fi网络和混合式接入网络的传输过程，相关学者研究了网络资源管理算法。文献[2]为消除微蜂窝型基站传输功率对网络服务质量消极的影响，给出一种启发式搜索算法(power search algorithm，PSA)，提高了cellular网络的传输效率，并降低了微蜂窝型基站的传输功耗。文献[3]考虑Wi-Fi网络致密化情况，设计了一种具有灵活、可伸缩和易扩展特点的高效管理密集Wi-Fi接入网络的控制架构(control architecture for efficient management of dense Wi-Fi access networks，CADWAN-A)，提升了Wi-Fi网络的传输性能。文献[4]针对可用合法频谱稀缺致使网络资源分配出现混乱的问题，研究一种基于软件定义蜂窝网络(software defined cellular networks，SDCN)的分布式资源分配算法，增大了混合式接入网络的资源使用率。文献[5]通过研究多覆盖Wi-Fi接入点组成的异构网络中的下行Wi-Fi模型，提出一种面向混合式接入网络的分布式资源分配算法，增加了流量传输效率。以上算法专注于网络传输过程的研究，但是缺少对用户接入行为的研究。

部分学者将排队博弈理论和网络传输理论相结合，从系统性能出发，研究了移动用户的行为策略。文献[6]利用排队模型和博弈论研究了认知无线网络(cognitive radio network，CRN)的决策问题，将移动用户之间的决策行为视为一种非合作博弈，并根据CRN的平均等待时间，给出CRN中用户访问的最优行为及纳什均衡策略，实现了CRN用户之间的资源合理分配。文献[7]考虑移动终端用户之间的资源竞争现象，构建一种非合作博弈排队模型，证明了纳什均衡的存在性，给出用户最优策略，提升了移动终端无线通信的性能。文献[8]考虑无线传感网络中的资源竞争问题，给出一种基于博弈思想的多任务调度策略，不仅满足了移动用户多样化的需求，而且提升了节点和链路资源的利用率。文献[9]针对可开闭异构网络，提出基于纳什均衡的离散粒子群算法，以用户和基站为博弈参与方建立博弈模型，给出非合作博弈条件下的纳什均衡策略和社会最优策略。以上文献从排队论和博弈论的角度，研究了移动用户的接入行为，但是缺少对混合式接入网络传输过程的研究，尤其是对社会最优策略的研究。

本文基于信息不可见情况，考虑数据传输与网络连接状态的特点，在离散时域下，建立具有2种工作状态单服务台的马尔可夫排队系统。采用矩阵几何解方法获得系统的稳态分布，给出移动用户平均响应时间的封闭解。按照混合式接入网络工作原理进行仿真实验，给出系统性能指标统计结果。权衡移动用户回报与损耗，构造预期收益函数，分别从个人与社会角度给出移动用户的纳什均衡进入策略与社会最优进入策略。改进灰狼智能寻优算法，以最大化系统收益为目标，获得社会最优到达率和纳什均衡到达率。针对不同系统参数，面向移动用户给出合理收费方案。

1 系统模型与模型分析

1.1 系统模型

移动用户交替使用的cellular网络和Wi-Fi网络可以看作是一个混合式接入网络。在混合式接入网络系统中，cellular网络和Wi-Fi网络被视为2种不同的服务状态。假设移动用户发送访问请求后不会反悔，发出的数据包可能会在cellular网络下传输完成，也可能在Wi-Fi网络下传输完成。考虑cellular网络和Wi-Fi网络交替出现，建立服务台状态可变的系统排队模型。

假设用户数据包的到达服从参数为Λ的二项分布，Wi-Fi连接的持续时间xw服从参数为pw的几何分布，Wi-Fi连接的间断时间xc服从参数为pc的几何分布。假设用户发出的数据包在Wi-Fi网络持续连接状态下所需的传输时间Sw服从参数为μw的几何分布，在cellular网络持续连接状态下所需的传输时间Sc服从参数为μc的几何分布。实际应用中，Wi-Fi网络下的传输速度往往比cellular网络下的传输速度快，规定μw>μc。

1.2 转移概率矩阵

将t时刻系统中数据包的数量表示为L(t)=i,i∈{0, 1, 2,…}，称为系统水平，将t时刻接入网络的状态表示为J(t)=j,j∈{0, 1}，其中j=0表示cellular网络，j=1表示Wi-Fi网络。{L(t),J(t),t≥0}构成了一个二维离散时间马尔可夫链，其状态空间表示为

Ω={(i,j)|i∈{0, 1, 2,…},j∈{0, 1}}

(1)

假设{L(t),J(t),t≥0}的一步状态转移概率矩阵为P，系统由水平i(i=0, 1, 2, …)至水平k(k=0, 1, 2,…)的一步转移概率子阵为Pi, k。接下来分析子阵Pi, k的5种表现形式。

(1) 当i=0，k=0时，表明系统未发生用户数据包的到达。一步转移概率子阵P0,0为

(2)

(2) 当i=0，k=1时，表明系统到达了一个用户数据包。一步转移概率子阵P0,1为

(3)

(3) 当k=i-1(i≥1)时，表明系统未发生用户数据包的到达，且有一个用户数据包离去。一步转移概率子阵Pi,i-1为

(4)

(4) 当k=i(i≥1)时，表明系统未发生用户数据包的到达和离去，或者系统发生一个用户数据包的到达和一个用户数据包的离去。一步转移概率子阵Pi,i为

(5)

(5) 当k=i+1(i≥1)时，表明系统发生一个用户数据包的到达，且没有用户数据包离去。一步转移概率子阵Pi, i+1为

(6)

由以上分析可知，系统的状态转移仅发生于相邻水平且状态转移从水平i≥1开始重复。令A0=P0,0，C0=P0,1，A=Pi,i，B=Pi,i-1，C=Pi,i+1，给出一步转移概率矩阵P的分块三对角形式的系统如下式所示。

(7)

1.3 稳态概率分布

令πi, j表示稳态下混合式接入网络水平为i、网络连接状态为j的概率分布，则有：

i=0, 1, 2,…,j=0, 1 (8)

令πi表示稳态下系统水平为i的概率向量，则有：

πi={πi,0,πi,1}i=0, 1, 2, …

(9)

二维马尔可夫链{L(t),J(t),t≥0}的稳态分布Π为

Π={π0,π1,π2, …}

(10)

由一步转移概率矩阵P的结构可知{L(t),J(t),t≥0}是一个拟生灭过程[10](quasi birth and death process, QBD)，通过高斯-赛德迭代法[11]与矩阵几何解[12]求解其稳态分布。

构造二次矩阵等式：

R2B+R(A-I)+C=0

(11)

其中，设R为率阵。式(11)具有非负解且最小非负解小于1，即谱半径[13](spectral radius, SR)小于1，QBD{L(t),J(t),t≥0}正常返具有稳态分布。

构造方程组如下：

(12)

其中，I为单位矩阵，e为全1列向量。

使用高斯-赛德尔方法求解式(12)可得π0和π1，基于矩阵几何解的形式，进一步得到：

πk=π1Rk-1k≥1

(13)

2 系统响应性能

数据包的平均逗留时间D定义为数据包从进入系统开始到服务完成为止的平均时间长度。在潜在到达率Λ一定的情形下，数据包平均逗留时间与数据包进入系统的概率q有关，表示为

(14)

其中，πi+1，0、πi+1，1为有效到达率λ=qΛ条件下的系统稳态分布。

以pc=0.4、pw=0.6为例，揭示了数据包的进队概率q对平均逗留时间D(q)的影响。理论分析实验在Matlab R2016a的环境下实现，仿真统计实验在MyEclipse 2017 CI环境下使用Java语言实现。计算机操作系统为Windows 10 企业版，处理器为Intel Core i5-6 500 3.20 GHz，内存为4 GB。图1揭示了不同cellular网络服务率μc和Wi-Fi网络服务率μw下，平均逗留时间D(q)随数据包的进队概率q的变化趋势。

图1 数据包平均逗留时间的变化趋势

从图1中可以看出，当数据包的进队概率q较低(如q<0.6)时，平均逗留时间D(q)随进队概率q的变化趋势平缓，而且Wi-Fi网络服务率μw和cellular网络服务率μc对平均逗留时间D(q)的影响很小。当数据包的进队概率q适中(如0.60.8)时，平均逗留时间D(q)随进队概率q的变化趋势快速增长，且Wi-Fi网络服务率μw或cellular网络服务率μc越小，该趋势增长越强。

3 纳什均衡与社会最优

3.1 纳什均衡进队概率

一个数据包进入系统后的平均收益Yp(q)是回报M与逗留期间成本D(q)N的差，则

Yp(q)=M-D(q)N

(15)

标记到达混合式接入网络的一个数据包，根据该数据包收益情况讨论其均衡进队概率qe[14]。

(1) 如果M

(2) 如果M>D(1)N，则数据包进入系统后，预期收益是正值。因此进队概率qe=1是唯一的均衡策略。

(3)当M-D(0)N

M=D(qe)N

(16)

以pc=0.4、pw=0.6为例，图2揭示了不同cellular网络服务率μc和Wi-Fi网络服务率μw下，数据包的个人收益Yp(q)随进队概率q的变化趋势。

从图2中可以看出，数据包的个人收益Yp(q)随进队概率q的增加呈现单调递减的趋势。当进队概率q较低(如q<0.6)时，数据包的个人收益Yp(q)随进队概率q的增加呈现缓慢下降的趋势，且个人收益Yp(q)的3条曲线之间的分散距离较小。当进队概率q较高(如q>0.6)时，数据包的个人收益Yp(q)随进队概率q的增加呈现快速下降的趋势，而且个人收益Yp(q)的3条曲线之间的分散距离逐渐加大，个人收益Yp(q)的3条曲线到达0点(纳什均衡点)的快慢也不相同。此时，若固定Wi-Fi网络服务率μw，增大cellular网络服务率μc，则个人收益Yp(q)随进队概率q的增加延后到达0点(纳什均衡点)。若固定cellular网络服务率μc，增大Wi-Fi网络服务率μw，则个人收益Yp(q)随进队概率q的增加延后到达0点(纳什均衡点)。此时，延后的程度较增大cellular网络服务率μc延后的程度小一些(免费使用的Wi-Fi网络，对比收费使用的cellular网络，减少了使用费用的支出，使得个人收益Yp(q)的下降趋势得以减缓)。因此，在相同条件下，适当增大Wi-Fi网络服务率μw或cellular网络服务率μc，可以有效提升数据包的个人收益Yp(q)及混合式接入网络的性能体验。

图2 数据包个人收益的变化趋势

3.2 社会最优进队概率

混合式接入网络的社会收益Ys定义为单位时间内进入系统的全部数据包在完成服务后所获收益的总和。混合式接入网络的社会收益Ys为

Ys(q)=qΛ(M-ND(q))

(17)

为了使社会收益Ys最大，混合式接入网络的社会最优进队概率q*为

(18)

以pc=0.4、pw=0.6为例，图3揭示了不同cellular网络服务率μc和Wi-Fi网络服务率μw下，混合式接入网络的社会收益Ys(q)随进队概率q的变化趋势。

图3 混合式接入网络社会收益的变化趋势

由图3可知，混合式接入网络的社会收益Ys(q)随进队概率q从0开始快速增长，到达峰值后又呈现大幅下降的趋势。当进队概率q略低时，社会收益Ys(q)随进队概率q的加大呈现单调上升趋势，而且社会收益Ys(q)的3条曲线在前期分散程度不明显，在后期分散程度逐渐加大。当进队概率q略高时，社会收益Ys(q)随进队概率q的加大呈现单调下降趋势，并最终达到0点。在社会最优进队概率q*下，会有最高的社会收益Ys(q*)，也就是社会最优策略下的收益。

4 智能寻优算法和收费方案

4.1 智能寻优算法的数值结果

为了获得纳什均衡进队概率和社会最优进队概率，引入仿生群智能优化算法。灰狼智能优化算法[15]是模拟自然界中灰狼种群抓捕猎物过程构造的随机群体算法。灰狼智能优化算法的求解精确度与灰狼群体位置的初始值、预判猎物位置的收敛性质及灰狼群体更新位置的方法密切相关。本文在原有灰狼智能优化算法的基础上，增加了混沌初始化，使得灰狼群体的初始位置分布更加均匀，从而提高全局搜索的精确度；在原有的非线性收敛函数基础上，增加了收敛性较高的对数函数，以提升全局最优解的确定速度。该算法的主要步骤如下。

步骤1设定初始迭代次数为t=1，最大迭代次数为tmax，灰狼种群数量为n，搜索空间上界为ub、下界为lb。

步骤2采用混沌logistic映射初始化第1次迭代(t=1)灰狼种群位置Xi(t)(i=1, 2,…,n)。

X1(t)=rand

%rand表示(0， 1)之间的随机生成数%

fori=2:n

Xi(t)=uXi-1(t)(1-Xi-1(t))

%u为混沌因子，设定u=3.5%

endfor

步骤3计算灰狼种群的适应度，依次找出最好的3个灰狼α、β、γ，位置分别为Xα(t)、Xβ(t)、Xγ(t)。

%在纳什均衡下，适应度绝对值最小的位置为最佳位置%

%在社会最优下，适应度最大的位置为最佳位置%

步骤4计算影响灰狼移动的协同系数。

C(t)=2rand

步骤5更新灰狼种群的位置。

fori=1:n

Y1=Xα(t)-A(t)|C(t)Xα(t)-Xi(t)|

Y2=Xβ(t)-A(t)|C(t)Xβ(t)-Xi(t)|

Y3=Xγ(t)-A(t)|C(t)Xγ(t)-Xi(t)|

ifXi(t+1)ub

Xi(t+1)=Xi(t)

endif

endfor

步骤6判断迭代过程是否结束。

ift

t=t+1

转到步骤3

else

输出灰狼α的位置Xα(tmax)。

%在纳什均衡条件下，Xα(tmax)作为纳什均衡进队概率qe%

%在社会最优条件下，Xα(tmax)作为社会最优进队概率q*%

endif

设定tmax=50、n=12、ub=1、lb=0，利用改进的灰狼智能优化算法，给出不同cellular网络服务率μc和Wi-Fi网络服务率μw下的纳什均衡进队概率qe和社会最优进队概率q*，如表1所示。

表1 纳什均衡与社会最优进队概率

4.2 社会最优进队概率

从表1中，可以看出纳什均衡进队概率qe普遍要比社会最优进队概率q*大。为确保社会收益的最大化，需调整纳什均衡进队概率qe，使其与社会最优进队概率q*保持一致。因此，需要征收额外的接入费用支付给网络服务商。假设接入费用为f，数据包进入系统后的平均收益变更为

Yp(q)=M-D(q)N-f

(19)

令Yp(q)=0，可得网络用户的接入费用为

f=M-D(q)N

(20)

将表1中社会最优进队概率q*带入式(20)，得到不同cellular网络服务率μc和Wi-Fi网络服务率μw下的接入费用f，如表2所示。

表2 接入费用

5 结 论

在互联网接入系统中，cellular网络一般收费使用，Wi-Fi网络则对特定用户免费使用。移动用户通常根据实际情况，交替使用cellular网络和Wi-Fi网络，即混合式接入网络访问互联网。基于信息不可见的情形，研究了混合式接入网络的纳什均衡策略和社会最优策略。结合系统中数据包数量和接入网络状态建立马尔可夫链，利用矩阵几何解方法给出了移动用户的平均响应时间表达式。通过建立收益函数，从移动用户个体出发，给出了纳什均衡进队策略，综合考虑混合式接入网络的服务提供者与移动用户全体，给出了社会最优进队策略。针对不同cellular网络服务率和Wi-Fi网络服务率进行系统实验，揭示出纳什均衡进队概率高于社会最优进队概率。改进灰狼智能寻优算法，给出了纳什均衡进队概率和社会最优进队概率数值结果。面向数据包制定收费方案，实现了纳什均衡进队概率和社会最优进队概率的统一。本文的研究为混合式接入网络的控制与管理提供了理论依据，同时也为排队理论和博弈理论在混合式接入网络中的应用提供了有效途径。