逼近纳什均衡的动态蜂窝选择方案

王文浩,王禄生,开彩红,刘 超

(合肥工业大学 计算机与信息学院,安徽 合肥 230601)

0 引 言

蜂窝选择指的是异构蜂窝网络中终端选择不同蜂窝进行接入的技术,可以是以系统性能最优为目的的蜂窝选择优化,也可以是以每个终端自身选择最佳接入策略为目的的蜂窝选择博弈[1-2]。蜂窝范围扩展是蜂窝选择优化中一种具有代表性的方法,在根据参考信号接收功率门限确定小蜂窝接入边界的基础上,加上一个偏置值以扩大小蜂窝的覆盖范围。一个场景中不同地方的稀疏程度不同,对应着完全不同的最优偏置值,这意味着固定的偏置值设置是不能得到系统最优的,而针对每个蜂窝设置不同偏置值的做法在有大量终端和基站的高密度网络中需要消耗非常长的优化时间[3-4]。同时,通过蜂窝选择优化来追求系统全局最优可能会牺牲一些终端的利益,使得这些终端可能期望改变选择策略来提升自身收益。因此,也有许多文献对蜂窝选择博弈的纳什均衡[5](即没有任何决策者单独改变策略而获益的策略组合)进行研究。例如,文献[6]从开放式和封闭式2种接入方式的角度分析了系统性能,同时证明了2种博弈模型纯策略纳什均衡的存在性。文献[7]提出了一个异构蜂窝选择博弈模型,并从理论上证明了混合策略纳什均衡的存在性;文献[8]针对不同无线接入技术场景,提出了3种支付函数的蜂窝选择博弈模型,并通过数学规划理论解决最优纳什均衡问题。然而,上述研究中均未提出搜索纳什均衡的有效方法。文献[9]证明了势博弈存在接近全局最优的纳什均衡点,同时提出了扩展性的最大分对数算法,得到了场景接近全局最优的纳什均衡点;文献[10]从蜂窝选择和资源分配联合的角度,分别研究终端选择最佳基站的蜂窝间博弈与终端选择最佳子信道的蜂窝内资源博弈,并针对该2层模型分别提出了2个纳什均衡收敛算法;文献[11]在有多种接入方式的异构蜂窝场景内,利用演化博弈分析蜂窝选择过程,并且通过增强型学习算法得到演化均衡;文献[12]通过博弈理论模型对流量卸载问题进行分析,提出基于回报的对数线性学习算法,并收敛得到ε-纳什均衡。

虽然文献[9-12]均提出了搜索纳什均衡的方法,但是这些方法都需要耗费大量的时间。在异构网络场景中终端会不断地移动,导致此前选择的结果偏离原纳什均衡,但是利用上述搜索纳什均衡的方法无法非常快速地重新逼近到新的纳什均衡。本文提出一种动态逼近纳什均衡的蜂窝选择方案,能够迅速调整终端的蜂窝选择策略,使整个系统始终保持逼近纳什均衡。

1 系统模型

本文研究的蜂窝选择是针对2层异构蜂窝场景中的上行信道特征,场景内分布M个基站,表示为Ω={1,…,M},其中包括若干个宏蜂窝基站和飞蜂窝基站。假设任意基站k∈Ω和其他任意基站l∈Ω的距离为Dl→k,由于不涉及蜂窝内的终端资源分配与调度,只能假设来自蜂窝l的干扰是其内终端的平均效应,可将其简化为蜂窝l的中心到基站k的干扰,计算公式为:

(1)

(2)

因此,基站k受到的总干扰计算公式为:

(3)

在场景内分布m个终端,它们的蜂窝选择策略组合为S={si|i=1,…,m}。其中,si为终端i的选择策略,其可选策略集为所有基站,因此选择基站k的终端个数计算公式为:

(4)

其中,bki为终端i选择接入基站k的二进制变量,即

(5)

本文采用信道容量评估终端i性能的效用,计算公式为:

(6)

定义1 若∀i∈{1,…,m},有

(7)

表示当前没有任何一个终端可以通过单独改变策略来获益,则此时所有终端组成的纯策略组合S*对应1个纯策略纳什均衡。

2 逼近纳什均衡的动态方案

在一个2层异构多蜂窝的动态网络场景中,整个系统以纳什均衡点作为终端的蜂窝选择结果。由于终端在场景中不断地移动,导致此前的蜂窝选择结果偏离了原有的纳什均衡,系统若想要在短时间内重新逼近到新的纳什均衡,就必须不停地快速搜索出纳什均衡点。但是,传统搜索纳什均衡的方法需要反复地判断当前场景中是否有终端想改变策略,而这个过程需要耗费大量的时间,这将导致系统的蜂窝选择结果因终端不断移动而始终无法逼近新的纳什均衡。因此,打破传统搜索纳什均衡方法中的思维定式是解决这个问题的突破口。本文根据原有的纳什均衡点,构造出一组经验公式,系统通过这组公式计算出当前网络状态下各个蜂窝内需要更改策略的终端数量,并根据蜂窝边缘终端更改策略的意愿强度对这些终端进行降序排列,从而直接对应出各个蜂窝内需要改变策略的终端。这是本文提出的逼近纳什均衡的动态蜂窝选择方案的核心思想。

按照上述思路,系统可以非常快速地逼近到新的纳什均衡。但是,系统只能得到近似的纳什均衡点,而经过数次调整终端的蜂窝选择策略后,可能会逐渐偏离纳什均衡。因此,为了保证系统始终动态逼近到新的纳什均衡,系统每隔一段时间就需要通过传统搜索纳什均衡的算法进行一次慢速的纳什均衡搜索。

本文逼近纳什均衡的动态蜂窝选择方案(简称“本文方案”),如图1所示。图1中,将时间轴分成了无数个长周期,每个长周期再分成若干个短周期。每个长周期结束后,系统触发一个传统搜索纳什均衡的算法搜索纳什均衡进行精确调整,该算法为本文改进的Milchtaich算法(简称“改进Milchtaich算法”);每个短周期结束后,系统通过设计的经验公式进行粗略调整,从而快速校正纳什均衡。

图1 逼近纳什均衡的动态蜂窝选择方案

2.1 经验公式粗略调整

每当短周期结束时,系统需要快速校正纳什均衡,即要调整相邻蜂窝边缘交界处终端的蜂窝选择策略,而这些终端所获得的频谱资源量是影响它们决策的主要因素,这与它们所选择蜂窝的终端数量有直接的关系。事实上,这些蜂窝内终端的数量不仅与其蜂窝内部可能移出的终端有关,还与这些蜂窝的相邻蜂窝边缘交界处可能移入的终端有关。换句话说,需要调整策略的终端受到覆盖它们的蜂窝以及这些蜂窝的相邻蜂窝的综合影响。因此,为方便后续描述,定义了蜂窝k和蜂窝l以及它们相邻蜂窝的相关符号。

假设基站k有若干个相邻基站,表示为Φk⊆Ω,其任意相邻基站为基站i∈Φk。蜂窝k内的终端数量在终端移动之前与在终端移动之后分别表示为Nk、Nk′,蜂窝i内的终端数量在终端移动之前与在终端移动之后分别表示为Ni、Ni′。对于位于蜂窝k与蜂窝i的边缘交界处且接入基站k的任意终端u,它们的集合表示为Ψk,i;同样,基站l也有若干个相邻基站,表示为Φl⊆Ω,其任意相邻基站表示为基站j∈Φl。蜂窝l内的终端数量在终端移动之前与在终端移动之后分别表示为Nl、Nl′。由蜂窝k和蜂窝l相邻可知,l∈Φk且k∈Φl。具体算法过程如下。

(8)

(9)

(10)

下文中将上述经验公式粗略调整终端蜂窝选择策略称为“方案1”。

2.2 改进Milchtaich算法精确调整

为了得到蜂窝选择博弈纳什均衡的结果,本文引用文献[14]中的一个算法,称为Milchtaich算法。该算法采用在拥塞博弈中1次改变1个终端的策略,并最终使场景达到纳什均衡状态。但是,该算法不适用于大规模终端的异构蜂窝场景,原因有2个:

(1) 该算法在异构蜂窝网络场景中效率很低。由于终端数量庞大,若在某个场景状态下只改变1个终端,则场景达到纳什均衡状态需要很长的时间。

(2) 终端会在2个基站之间来回切换,产生“乒乓效应”。当场景达到近似均衡的状态时,可能会有少数在2个蜂窝边缘的终端不停地切换基站,场景始终都无法达到纳什均衡的状态。

因此,本文对该算法做了改进和拓展。当场景处于某个状态下,所有需要改变策略的终端以一定的概率同时离开原来的蜂窝。这大大减少了算法循环判断场景内是否有终端需要改变策略的次数,同时降低了少部分终端在相邻蜂窝之间同时来回切换的概率。这样做提高了算法的效率,也能减少“乒乓效应”带来的影响。同时,本文改进后的算法不仅适用于1个宏蜂窝(macrocell)和1个微微蜂窝(picocell)构成的简单场景,还适用于多蜂窝的复杂场景。改进Milchtaich算法步骤如下:

(1) 初始状态下,任意终端给其所有基站发送1个有效传输信号,根据这些基站接收信号强度的最大值,终端做出决策接入相应的基站,此时,场景内所有终端的蜂窝选择策略组合表示为S。

(2) 所有终端接收到资源管理决策中心广播的有关场景状态的信息,并由此判断,在当前状态下是否需要改变策略。

(3) 资源管理决策中心收集所有需要改变策略的终端和它们需要接入基站的信息,以0.5的概率选出被允许更改策略的终端,再通知相应的终端改变策略;终端改变策略后,更新场景内所有终端的蜂窝选择策略组合,本轮算法结束。

(4) 下一轮算法重复本轮算法的过程,直到场景达到纳什均衡为止。

下文中将改进Milchtaich算法精确调整终端蜂窝选择策略称为“方案2”。

3 性能仿真结果分析

本文考虑拥有大量飞蜂窝基站和终端的高密度蜂窝的仿真场景,参数设置[13,15]如下:宏蜂窝和飞蜂窝的终端发射功率分别为23、13 dBm,宏蜂窝基站和飞蜂窝基站的载波频率分别为2.0、3.5 GHz,宏蜂窝和飞蜂窝的路径损耗因子分别为3.00、3.19,宏蜂窝和飞蜂窝的阴影衰落分别为6.80、8.29 dB,宏蜂窝和飞蜂窝的带宽均为20 MHz,噪声功率密度为-174 dBm/Hz。

3.1 仿真场景设计

在异构蜂窝网络场景中,终端会不断地移动。为了方便研究,设置终端周期性地在场景内移动。若终端在整个场景内随机移动,则新的纳什均衡结果相比于第1次的纳什均衡结果不会发生明显的变化。因此,将场景平均分成4个正四边形区域,场景内的终端均在各自的区域内逆时针移动。以其中1个正四边形区域为例,将该区域再分成4个小的正四边形区域。在某个短周期内,当场景达到纳什均衡状态后,从某个小区域内开始,随机选取该小区域内10%～20%的终端,并以逆时针的方向同时向相邻小区域随机移动,终端移动到任意蜂窝内就接入该蜂窝的基站。同理,下个短周期再从终端到达的小区域内开始,终端按照上一轮短周期的方式移动。终端移动场景与蜂窝选择纳什均衡结果如图2所示。

图2 终端移动场景与蜂窝选择纳什均衡结果

通过直观地对比方案1、方案2得出的仿真场景图,大致地评估方案1的性能。由于每个短周期内,只有场景中的某个区域内有终端发生位置移动,本文仿真终端移动4个短周期后的蜂窝场景。图2b、图2c中,更改策略的终端与其更改策略后接入的基站图形相同,由此可以直观地看出由方案1蜂窝选择结果逼近方案2结果。

3.2 方案性能对比

为了评估本文方案的效率,本文引用了基于Q学习的蜂窝选择方案(简称“方案3”)。方案3能够帮助终端学习它们过去的知识,并且在未知其他终端完全信息的情况下可以使它们做出近似最优的决策。在终端做决策时,为了避免ε-贪婪算法使其陷入局部最优的蜂窝选择结果,本文采用Boltzmann搜索方法[16]。

(1) 时间消耗量。方案1、方案2及方案3的时间消耗量对比如图3所示。对于传统的搜索纳什均衡的方案2、方案3,所有蜂窝边缘的终端需要不断地变更策略,因此需要经过很多次迭代运算。而方案1是根据经验公式直接得出每个蜂窝内需要变更策略的终端,它比任何搜索纳什均衡的方案都快。

图3 蜂窝选择方案的时间消耗量对比

(2) 平均信道容量。为了评估本文方案的系统性能,本文引用了经典的基于接收信号强度方案(简称“方案4”)。由于传统搜索纳什均衡方案的运行速度太慢,这些方案在动态的场景中不具

有应用性,因此,不考虑算法的运行时间,直接比较这些方案所得的动态系统平均信道容量。考虑到每个周期内变更蜂窝选择的终端总是位于蜂窝边缘附近,这里的动态系统平均信道容量是指蜂窝边缘终端的平均信道容量。4种方案终端移动的动态场景系统性能如图4所示。由图4可知,本文方案所得的蜂窝边缘终端性能与传统搜索纳什均衡方案所得结果的性能相近,并且比方案4的结果性能好。

图4 蜂窝选择方案的性能对比

(3) 存在不同蜂窝选择策略终端的数量。为了检验本文方案所得的系统蜂窝选择结果逼近纳什均衡的程度,对方案2和本文方案所得的蜂窝选择结果进行比较,并统计2种结果中存在不同蜂窝选择策略终端的数量λ。共有15个长周期,每个长周期包含20个短周期,每个短周期内均有20个终端移动,本文随机选取5个有终端移动场景的仿真结果,如图5所示。

图5本文方案的蜂窝选择结果与纳什均衡点的对比中存在策略不同的终端数量

图6 本文方案逼近纳什均衡的程度

4 结 论

在异构蜂窝网络中,对于以每个终端自身选择最佳接入策略为目的的蜂窝选择博弈问题,在终端移动的网络场景下,传统搜索纳什均衡的方法无法使整个系统从近似的纳什均衡快速逼近到新的纳什均衡。针对这个问题,本文提出了一种逼近纳什均衡的动态蜂窝选择方案。通过仿真发现,该方案可以使整个系统始终动态地逼近纳什均衡,所得的蜂窝边缘终端性能与传统搜索纳什均衡方案所得结果的性能相近,并且比经典的基于接收信号强度方案的结果性能好。