基于演化博弈的用户接入机制

王月平，徐 涛

（1.南京航空航天大学计算机科学与技术学院，南京211106； 2.中国民航大学计算机科学与技术学院，天津300300）（∗通信作者电子邮箱84545773@qq.com）

0 引言

随着网络结构的密集化、异构化，以及全双工等新技术的引入，许多无线通信网络中的基础问题需要进行重新研究，用户接入（user association 或cell association）便是其中之一［1-2］。在无线通信网络特别是超密集异构网络中，一个无线终端通常处于多个基站的服务范围内。用户接入问题就是为无线终端选择接入某个基站进行服务和数据传输的问题，无论采用何种无线技术以及网络部署方式，用户接入机制都是不可或缺的。同时用户接入机制作为无线资源管理的第一步，对于网络性能有着重要的影响，在实现负载均衡、干扰控制、提高频谱和能量效率等方面起着非常重要的作用［3］。

异构网络中的用户接入机制可以分为网络端驱动的集中式设计Network-driven，即由网络中心节点作出接入决策；以及用户端驱动的分布式设计User-driven，即由用户终端作出接入决策。网络端驱动的集中式设计的优点就是中心节点能够收集网络的整体信息，因此可以作出针对系统整体的最优接入决策，代价就是具有较高的复杂度。相比而言，用户端驱动的用户接入机制的优势则具有较低的复杂度。两种方案各有其优缺点，适用于不同的网络结构及节点类型。在超密集异构网络中，大部分的小基站由不同的组织、机构、甚至个人（如家庭基站）进行部署。针对这种情况，将面向包含宏基站和全双工小基站的多层异构自组织网络研究用户端驱动的低复杂度用户接入机制。

现有的用户接入机制的研究［3-8］与设计几乎都是基于上行下行关联的，即用户终端在上行和下行必须接入到同一个基站［9］。对于单层同构网络来说，这种接入机制简单而有效。首先，采用上下行关联的接入机制便于网络的设计与运行，特别是便于信令同步、资源管理等；其次，在单层同构网络中，能提供最好下行连接的基站通常也能提供最好的上行连接。而在多层异构网络中，存在着不同层次基站之间以及上行下行之间的不对称问题，即不同层次的基站之间以及上行下行之间通常在发射功率、覆盖范围、信道质量、数据流量、回程容量以及硬件等方面有较大差别，并且这种不对称会随着各层基站密度的增加而更加突出。这时基于上行下行关联的用户接入将会严重制约系统的性能，如负载均衡、干扰、频谱和能量效率等。例如，当采用基于最强下行信号且上下行关联的用户接入机制时，因为宏基站与小基站发射功率存在较大差异，该机制将会使大部分用户都连接到宏基站，从而造成严重的负载不均衡，并降低了小基站部署的意义。此外基于频谱效率的考虑，宏基站与小基站通常复用同一频谱资源，这时会存在以下情况：基于最强下行信号用户连接到较远的宏基站；然而在进行上行数据传输时，该用户需要使用较大的传输功率来达到其上行性能要求，但这样会对附近的小基站造成严重的上行干扰，从而影响网络的整体性能并增加自身的能量消耗。为此，上行下行分离的概念被提出［10］，即上行传输和下行传输可以选择接入不同的基站。上行下行关联的用户接入可以看作是上下行分离用户接入的一种特例，因此，从理论上说上下行分离可以带来更好的性能。初步的仿真研究［11-13］已经证明在两层异构网络中，简单的上行下行分离机制可以带来较大的性能提升，例如，可以提高上行传输速率、降低发射功率和上行干扰，以及实现更好的负载均衡等。目前只有少量研究面向超密集异构网络。考虑到超密集网络中基站密度大、用户接入选择多的特点，一些学者提出了采用双连接［14］或者多连接［15］的用户接入机制，即用户可以同时连接到两个或者多个基站。上述工作目前只研究了最简单的多接入机制，即选择接入最近的k个基站，但是没有作进一步的优化设计。

本文考虑允许一个用户在上行和下行接入多个不同的基站，将自组织分离多接入问题建模成演化博弈问题，并用一组微分方程（即复制者动态）来描述用户接入策略的选择调整过程；提出了演化均衡作为博弈的均衡解，并分析了其稳定性；此外，基于强化学习和深度强化学习设计了自组织用户接入算法，用户可以根据当前的策略选择收益来进行策略调整，并最终达到均衡状态，实现了用户之间的公平性。

1 系统建模

1.1 网络模型

考虑由1个宏基站、K个小基站和N个用户组成的双层异构网络，其中小基站可以进行全双工传输。假设网络中的小基站和用户在空间上都是随机分布，在所考虑的网络中，将使用提出的分离多接入机制，其中用户只在下行时可以选择接到宏基站。此外，假设用户在上行时只能选择接入1个小基站，而下行时可以选择多个小基站。两个节点i和j之间的信道增益Gi，j可以定义为：

式（3）表示只有接入概率大于0，用户才能成功访问该信道进行数据传输。

1.2 干扰模型

下面分析一下系统中的干扰情况。与传统的上行下行耦合的用户接入方法相比，分离多接入不可避免会导致节点之间产生额外的干扰，这又会影响节点最后的性能。本节分别分析上行和下行传输中的干扰，具体如下：

上行链路传输中的干扰 上行链路传输中，用户作为发送端，小基站作为接收端，必须分析小基站收到的干扰情况。每一个小基站在上行和下行允许多用户同时接入，同时，对于某个用户来说，能在上行和下行连接到多个不同的小基站。在这样的系统中，在小基站接收到的与上行干扰包括3个部分：来自其他进行下行传输全双工小基站的干扰、来自其他进行上行传输的用户的干扰，以及自干扰，具体表示为：

下行链路传输中的干扰 用户作为下行链路传输的接收者会受到其他节点传输的干扰。类似的，对连接到小基站k的UE（User Equipment）的干扰进行分析，干扰也包含3个部分，具体表示如下：

1.3 数据传输速率

在所考虑的网络中，将用户和小基站之间数据传输速率作为用户接入的性能衡量指标。显然，一个用户更希望接入到能够提供更高传输速率的小基站。影响传输速率的关键因素是小基站能提供的带宽、发送功率，以及节点之间的干扰。对于给定的小基站k，用户n连接到k的上行和下行传输速率可以用Shannon-Hartley定理计算：

其中SINRnk是信号干扰噪声比。对于分离多接入，有：

其中σ2是加性高斯白噪声（Additive White Gaussian Noise，AWGN），假设对所有用户都是一样的。这样，用户n在上行和下行连接到小基站k的上行和下行速率可以相应表达为：

2 演化博弈建模及分析

本文将基于演化博弈来设计用户端驱动的多接入机制，演化博弈论是研究有限理性博弈方之间相互作用的数学工具。在演化博弈论中，博弈方根据自己的适应度（即收益）选择策略。在无线网络中，博弈方可以是一定区域内争夺无线资源的N个用户，这也构成了群体。用nl(t)表示t时刻选择纯策略l∈L的代理人数量，其中L为纯策略集合。标准化变量xl(t)=nl()

t N表示策略l的群体份额，此处所有纯策略|L|的群体份额构成种群状态，可以用向量示，其中X是状态空间。π(l，x)表示使用纯策略l的玩家的期望收益，也表示适应度。因此群体的平均收益可以推导为，动态策略适应过程（即演化博弈中的选择机制）可用以下微分方程描述的复制者动态方程来建模：

其中δ是群体的学习速率，控制着选择变化的速度。根据复制者动态，预期收益高于平均收益的策略的总体份额将增加，而预期收益低于平均收益的策略的总体份额将减少。当所有的群体份额不变时，演化均衡就会达到（i.e.，ẋl=0对于所有的l∈L）。演化均衡是沿着动态轨迹的不动点，也就是说，当群体状态演化为这样的固定点时，群体状态将保持不变。演化均衡的物理意义是，在这个均衡中，没有一个个体想要改变策略因为它的收益等于总体的平均收益。虽然可能存在多种演化均衡，但并不是所有的均衡都是稳定的。

本文采用演化博弈的动机如下：

有限理性假设 在传统非合作博弈论中通常假设博弈方都是完全理性的，即博弈方完全清楚在某个策略组合下自己的收益和别人的收益，并选择策略追求自身收益的最大化。这是一个非常强的假设，在很多实际情况下无法满足该假设，而演化博弈只要求博弈方具有有限理性，即在了解部分收益的情况下，通过不断学习调整策略，逐渐提高自己的收益。

博弈动态描述 演化博弈可以对群体之间各博弈方之间的动态交互进行描述建模。一个博弈方可以观察到其他博弈方的行为，并从观察中学习，然后再作出策略调整。此外，通过复制者动态，任意时间t的博弈状态可以被确定，这样可以用来研究博弈方策略调整的一个轨迹或者趋势。

筛选博弈均衡解 在传统博弈论中，纳什均衡是最常用的解的形式。纳什均衡能保证在其他博弈方法不偏离均衡策略时，一个博弈方不能单独通过调整自己的策略来获得更高的收益。然而，在许多情况下，一个博弈可能有多个纳什均衡解，因此，就需要进行均衡解的筛选。在演化博弈中，演化均衡提供了一种筛选方法，并且能保证筛选过后的解的稳定性。

低复杂度学习机制 在演化博弈中，各博弈可以通过一些低复杂度的学习机制来达到演化均衡，这在许多对算法复杂度要求较高的实际问题中很有用处。

公平性 在演化博弈中，在通过不断动态调整达到演化均衡状态时，选择不同策略会得到同样收益，实现了公平性。

2.1 问题建模

考虑用户接入的策略动态调整过程，建模演化博弈问题G=(N，S，π)，具体介绍如下：

博弈方 在本文的系统模型中，每个能接入到小基站的活跃用户都是一个博弈方。用N={1，2，…，N}来表示本博弈中的博弈方的集合。

群体 在演化博弈中，博弈方的集合构成了一个群体。

策略集合 每个博弈方的策略就是选择要接入的小基站。需要注意的是，同一群体中的博弈方拥有相同的策略集。

群体比例 指在一个群体中，选择某个策略的博弈方数量占整个群体数量的比例，即xi=ni N，其中i∈S，ni是选择策略i的博弈方数量。显然

群体状态 一个群体中的所有策略的群体比例构成了群体状态，可以通过[x1，x2，…，xi，…，xs] ∈X来表示，其中X表示在给定网络模型下包含了所有可能群体状态的状态空间。

收益函数 每个用户作为博弈方需要根据收益来调整其接入策略。在本博弈中，定义一个博弈方的收益函数为接入速率和接入费用之间的加权差。其中在不同策略下的用户速率可以表示为r=[r1，r2，…，ri，…，rs]。根据系统模型部分的数据传输速率公式，可以得到：

其中：ku、kd表示用户n在上行和下行连接到的基站集合，相应的速率是连接到每个小基站的速率之和。基于此，一个博弈方选择某个策略的收益函数可以定义如下：

其中：λ代表收益权重，c(bi，pi)是用户接入小基站的费用函数，与分配的带宽b和发射功率p相关，具体定义如下：

其中μ和ν分别是单位带宽和功率的费用。

2.2 接入策略动态选择

正如博弈建模阶段所述，用户接入是一个动态选择过程，每个博弈方在时间t会根据其收到的效益πi(t)以及当前整个群体的平均收益来动态调整其策略，这一过程不断重复，从而不断地提升自己的收益，直到达到均衡状态。可以用复制者动态来对这个策略动态调整的过程建立数学模型。复制者动态是一个常微分方程表达如下：

其中：ẋi(t)是xi(t)关于t的微分，代表选择策略i的群体比例xi的变化率，ẋi(t)＞0时表示选择该策略的博弈方将增加；γ是设定的学习率，用来控制用户接入策略调整的频率；πˉ(t)是同一群体中所有博弈方的平均收益，可以根据式（22）计算得出：

从式（22）可以看出，一个策略的群体比例变化率与选择该策略得到的收益与整个群体平均收益成正比。

即使用复制者动态来描述群体比例的动态调整的过程中，所有策略的群体比例之和始终为1。为了验证这一点，令fi(x)=γxi(t)[πi(t)-πˉ(t)]。首先可以得到，即所有群体比例之和不会随时间变化。此外，还可以得到当xi(t)=0时fi(x)≥0，当xi(t)=1时fi(x)≤0，所以可以保证xi(t)∈ [0，1]。

2.3 演化均衡、演化稳定策略分析

复制者动态描述了所有的群体比例变化率。从用户接入的复制者动态方程可以看出，当采用某个策略的收益比群体平均收益要高时（即πi(t)＞πˉ(t)，πi(t)-πˉ(t)＞ 0），相应的ẋi(t)＞0，这表示采用策略i的用户数量会相应增加。考虑演化均衡作为该演化博弈的均衡解。演化博弈可以定义为上述复制者动态中的不动点，即ẋi(t) ＞ 0，∀i。根据定义，演化均衡可以通过求解一组代数方程ẋi=0，∀i得到。

当达到演化均衡时，群体中选择不同策略能得到相等的收益（即πi(t)=πˉ(t)），因此一方面保证了公平性，另一方面，在达到均衡时，没有博弈方有动机来改变选择的策略。需要注意的是，根据上面方法求解代数方程可能得到多组演化均衡，其中包括边界均衡点（即∃i，xi=1）以及内点均衡点（即x i∈ [0，1]，∀i）。对于本文定义的用户接入演化博弈来说，边界均衡解不是一个稳定的解，任何小的扰动都会让系统偏离这个均衡解。相比而言，可以证明所求的内点均衡是渐近稳定并且是一个演化稳定策略（Evolutionary Stable Strategy，ESS）［8］解。下面首先介绍一下演化稳定策略解。

如果对于任一群体状态∈X且y≠x，存在εy∈(0，1)使得ε∈ (0，εy)不等式π(x，εy+(1-ε)x)＞π(y，εy+( )1-εx)成立，则均衡群体状态x*∈X是演化稳定的。演化稳定策略（ESS）对入侵者具有很强的抵抗能力，即群体中所有的突变体最终都会消失。对于ESS群体分布，状态的微小扰动并不影响收敛到均衡态。物理意义是，扰动态的平均效益小于均衡态的平均效益。这样，ESS对入侵者（即扰动）具有很强的抵抗力。实际上，在某些情况下，复制动态是全局渐近稳定的。在这种情况下，任何偏离均衡的地方都会收敛回均衡。

首先来证明建立的用户接入演化博弈是一个稳定群体博弈，因为下面条件对所有群体状态x≠y都满足：

因此，所建模的演化博弈具有如下均衡是中性稳定（neutrally stable）的属性。此外，根据复制者动态的特征方程，其系数矩阵总是有2M个负特征值，这样表明所建立的复制者动态具有渐近稳定属性（asymptotically stable property）。因此，用户接入动态系统能够从任何非边界初始群体状态渐进演化到一个内点演化均衡点，因此可以知道所得到的内点演化均衡点是一个演化稳定策略解（ESS）。

3 基于演化博弈的分离多接入算法设计

针对基于演化博弈的异构网络中分离多接入，本文设计了两种具体的实现算法：第一种方法是基于强化学习，其中每个用户尝试不同的接入策略，观察其得到收益，并在必要的条件下尝试策略调整；第二种是在强化学习的机基础上引入了深度学习，基于深度强化学习改进了第二种算法。下面具体介绍这两种算法。

3.1 基于强化学习的方法

在无中心节点条件下，每个用户需要独立地通过尝试、观察和学习来调整策略，并最终达到均衡状态。针对这一情况，基于Q学习（强化学习的一种，如图1所示）设计了一个无需其他用户信息的分布式算法（见算法1）。在算法中，使用一个Q值来维护每个策略的相关信息。

图1 强化学习架构Fig.1 Framework of reinforcement learning

在基于强化学习的用户接入算法中，一个用户以概率γ执行探索阶段，相应的以概率1-γ执行利用阶段。λ是学习速率，用来控制Q值的调整速率。Q值代表用户对未来迭代过程中的预期收益，Q值的更新依赖于之前的Q值与新观察到的收益值。在这一更新迭代过程中，用户通过与环境交互学习逐渐提高其收益。

3.2 基于深度强化学习的方法

传统的强化学习局限于动作空间和样本空间都很小。当网络规模增加，可选基站数量也将会大幅度增加，从而一个用户的可选策略将会极大增加。上述强化学习方法难以有效解决。因此，针对大状态空间和策略空间的情况，进一步考虑了基于深度强化学习的方法。深度强化学习将深度学习的感知能力和强化学习的决策能力相结合，深度强化学习原理框架如图2所示。

图2 深度强化学习架构Fig.2 Architectureof deep reinforcement learning

其学习过程可以描述为：

1）在每个时刻Agent与环境交互得到一个高维度的观察，并利用深度学习方法来感知观察，以得到具体的状态特征表示；

2）基于预期回报来评价各动作的价值函数，并通过某种策略将当前状态映射为相应的动作；

3）环境对此动作做出反应，并得到下一个观察，通过不断循环以上过程，最终可以得到实现目标的最优策略。

基于深度强化学习的算法和上述强化学习的一大区别就是采用一个深度网络代表价值函数，代替了强化学习中的Q表。然后依据强化学习中的奖励值，为深度网络提供目标值，对网络不断更新直至收敛。本文使用的人工神经网络（Aritifical Neural Network，ANN）架构如图3所示。具体算法过程与基于强化学习算法类似，因此不再赘述。

图3 ANN架构Fig.3 Framework of ANN

4 实验与结果分析

为了验证所提方法，本文在Matlab中进行仿真。具体考虑一个包含1个宏基站、2个小基站与10个用户的异构网络，基站与用户都随机分布在一个半径100 m的区域内，同时，考虑每个基站有不同的信道资源。

图4展示了复制者动态的收敛性，可以观察到，经过迭代后，不同策略群体比例最终也从初始状态达到了一个稳定的均衡状态。在达到均衡点后，策略选择的变化率为0，也就是说选择其他策略对于该用户并不能提高收益，因此没有偏离均衡策略的动机。这个均衡点也是复制者动态的不动点。此外，能够观察到初始占比较高的策略，在达到均衡时占比不一定很高，它反映出了提出的动态接入算法的公平性。

图4 群体比例演进Fig.4 Population proportion evolution

在图5中，以用户选择策略l的收益为例，验证了所提出的两种算法（基于强化学习的算法以及基于深度强化学习的算法）的收敛性，并与传统基于群体状态演进算法进行了比较。可以看到：经过迭代三种算法都收敛到了一个均衡状态，并获得了相应的收益；基于深度强化学习的方法能较快地收敛，并且能够获得较高的收益，而基于群体状态演进和基于强化学习的算法最终能获得相同的收益。

图5 不同算法比较（策略i=1）Fig.5 Comparison of different algorithms（i=1）

5 结语

在本文中，研究了自组织网络的用户接入优化问题。针对多层异构网络特点，提出了分离多接入机制。本文将自组织分离多接入问题建模成演化博弈问题，其中用户可以根据当前的策略选择收益来进行策略调整，并最终达到均衡状态。使用复制者动态对这一策略动态调整进行了数学建模。基于群体状态演进、强化学习、深度强化学习设计了自组织用户接入算法。通过仿真验证了复制者动态以及所提出算法的收敛性并比较了三种算法的性能。