1.   引言

在5G网络中，需要支持海量的低速率机器类型通信(Machine-Type Communication, MTC)设备以及传统的人类型通信(Human-Type Communications, HTC)用户^[1]。作为5G通信系统关键技术之一的小蜂窝基站技术，通过在现有的单层蜂窝小区中叠加一些低成本、低功耗的接入点，达到提升网络容量的目标^[2,3]。在这种多个蜂窝小区共存的超密集网络中，多基站之间如何进行用户分配，达到负载均衡和用户服务质量(Quality of Service, QoS)保障是一个需要解决的重要问题^[3-11]。目前，研究这方面的文献[3-7]主要考虑下行链路中的用户分配问题。但是机器到机器(Machine-to-Machine, M2M)通信中的业务主要集中在上行传输。然而上行用户分配与传统人与人(Human-to-Human, H2H)通信下行用户分配存在比较大的差异。一方面，下行用户分配问题主要考虑如何有效地将宏蜂窝的负载分流到小蜂窝中，提高网络的资源利用率。然而在上行通信中，由于小蜂窝部署得多，所以用户往往优先选择小蜂窝基站接入。在上行用户分配问题中，需要考虑为小蜂窝基站负载分流。另一方面，与宏蜂窝基站不同，小蜂窝基站的资源受限(如覆盖范围小和服务用户数少)，这也会对用户分配问题造成比较大的影响。由于存在以上两方面的差异，所以下行用户分配策略不能用于解决上行用户分配问题。

目前也有很多学者设计一些上行用户分配策略，如基于大学招生博弈的上行用户分配策略^[8]以及联合上下行用户分配策略^[9,10]等。然而这些策略没有考虑M2M通信中海量用户接入的特点，所以不能够用于解决共存场景中的用户分配问题。此外，能效也是用户分配问题中的一个重要研究方向。在用户分配的能效问题研究中，由于基站的能耗过大，所以大部分学者，如文献[10]研究如何设计用户分配策略来有效地降低基站的能耗。但是在M2M通信中，MTC设备侧的能耗则是关注的重点。因此，如文献[10]所提能量有效的用户分配策略不能直接用于解决共存场景下能量有效的用户分配问题。

针对异构蜂窝网络中H2H和M2M业务共存场景下有QoS保障和负载均衡的上行用户分配问题，本文提出一种基于匹配理论的上行用户分配算法，在用户分配过程中设计两种接入控制策略：针对HTC用户的非竞争接入控制策略和针对MTC设备的基于接入限制的竞争随机接入控制策略，实现两类节点QoS保障、网络负载均衡以及最大化节点能效；同时，还分析算法的收敛性和复杂度。仿真结果表明，提出的算法能够获得与穷举搜索法相同的性能。此外，该算法在网络能效、负载均衡以及QoS保障方面都优于现有对比算法。

本文结构安排如下：第2节给出系统模型以及接入控制协议；第3节对用户分配问题进行建模分析；第4节提出一种用户分配算法；第5节通过仿真结果对所提用户分配算法的性能进行评估；第6节给出本文的结论。

2.   系统模型

2.1   网络模型

考虑一个由N个基站和M个节点构成的异构蜂窝网络，其中，N个基站包括宏基站、皮基站和飞基站这3种类型。M个节点包括H个HTC用户和D个MTC设备。设$\mathcal{N}$, $\mathcal{M}$, $\mathcal{H}$和$\mathcal{D}$分别表示所有基站、所有节点、所有HTC用户和所有MTC设备的集合。${{\cal{B}}_j}$, ${\cal{B}}_j^{{\rm{HTC}}}$, ${\cal{B}}_j^{{\rm{MTC}}}$分别表示归属于基站j的节点、HTC用户和MTC设备的集合。本文主要考虑异构蜂窝网络中节点到基站的上行链路。

同时，考虑这个异构蜂窝网络采用正交频分多址接入(Orthogonal Frequency Division Multiple Access, OFDMA)技术，所以网络资源为时间-频率2维资源。在这种网络中，业务资源分配最小单元结构为一个正交资源块(Resource Block, RB)。假设基站j所拥有的${L_j}$个资源块构成的集合表示为${{\cal L}_j} \buildrel \Delta \over = \left\{ {1,2,\cdots,{L_j}} \right\}$。假设节点与基站之间的信道模型服从慢衰落和平坦衰落。所以，信道的相关时间和相干带宽分别大于一个资源块在时域和频域间隔大小。同时，还假设在基站处采用了一些干扰消除的方法，如上行协同调度的多用户多入多出(Multi-User Multiple Input Multiple Output, MU-MIMO)技术^[11]，来自相邻小区的干扰可以忽略不计。需要说明的一点是，由于用户的发射功率较小，且基站的处理能力很强，因此假设完全消除相邻小区的干扰是具有一定可行性的。

本文考虑在上行传输中采用单载波频分多址接入(Single Carrier Frequency Division Multiple Access, SC-FDMA)。在SC-FDMA传输过程中，由于每一个数据符号都扩展到整个分配带宽上，所以在分配给该节点带宽上的信道增益可认为各个子信道带宽的均值。假设基站j给节点i分配了${n_{kj}}$个资源块，节点i到基站j的最大传输速率为${r_{ij}} =$${n_{ij}}\Delta f{\log _2}(1 + \gamma _{ij}^{\rm{ave}})$。其中，$\Delta f$表示每个资源块的带宽，$\gamma _{ij}^{\rm{ave}}$表示基站j分配给节点i的所有资源块上平均接收信噪比(Signal-Noise Ratio, SNR)，其计算公式为$\gamma _{ij}^{\rm{ave}} = {{\displaystyle\sum\nolimits_{l \in \mathcal{L}_l^i} {\gamma _{ij}^l} } / {{n_{ij}}}}$。$\gamma _{ij}^l$表示基站j在第l个资源块上，接收到节点$i \in \mathcal{M}$发送信号的SNR，可以计算为$\gamma _{ij}^l = {{{P_i}{G_{ij}}{{\left| {h_{ij}^l} \right|}^2}} / {{N_0}}}$。其中，P_i表示节点i在每一个资源块上的发射功率，G_ij表示从节点i到基站j之间链路的大尺度衰落影响，包括路径损耗、对数正态阴影衰落以及天线增益等，h_ij表示小尺度衰落下的信道增益，N₀表示加性高斯白噪声功率。

2.2   混合接入控制协议

在H2H和M2M业务共存场景中，为了保证H2H通信性能不受M2M通信的影响，本文假设HTC用户具有高优先级接入网络，根据其QoS需求分配无线资源。在H2H通信中，HTC用户采用一种非竞争接入控制协议，在基站分配的无线资源上传输业务。

为了降低实现复杂度，本文只是考虑保证HTC用户的传输速率需求。由于节点与基站间瞬时传输速度会随着信道的波动而变化。如果要保证瞬时传输速率大于某个门限值，那么基站需要根据当前信道状态来实时调整资源分配策略。然而在实际中存在反馈延迟和估计误差，通过动态调整资源分配策略来保证HTC用户的传输速率需求实现难度较大。所以，本文考虑保证HTC用户与基站间的长期传输速率^[6]大于所需的速率门限值。在这种策略中，基站只需要周期性估计HTC用户与其之间信道的大尺度衰落影响，然后再判断是否需要调整资源分配方案。所以基站调整资源分配方案的频率比较低，可实现性大。

假设HTC用户k($\forall k \in \mathcal{H}$)归属于基站j($\forall j \in \mathcal{N}$)。那么基站j接收到HTC用户k发送信号的长期SNR可表示为${\bar \gamma _{kj}} = {{{P_k}{G_{kj}}} / {{N_0}}}$。假设基站j给HTC用户k分配了n_kj个资源块。因此，HTC用户k到基站j的长期传输速率记为${\bar r_{kj}}$，可表示为${\bar r_{kj}} =$${n_{kj}}\Delta f{\log _2}(1 + {\bar \gamma _{kj}})$。

注意长期SNR、容量和速率并不是瞬时SNR、容量和速率的统计平均值。瞬时SNR、容量和速率的统计平均值通过SNR、容量和速率在信道增益的概率分布上积分所获得。尽管从信息论角度看参数的长期值并不是其均值，但是二者却保持相同的趋势。此外，在实际中，参数的长期值更容易获得。

考虑保证每个HTC用户的长期传输速率大于其所需的最小传输速率，即门限值。设HTC用户k的最小传输速率为$r_k^{\rm{R}}$。那么，当HTC用户k归属于基站j后，所需要的最少资源块数量为：$n_{kj}^{\rm{R}} =$$\left\lceil {{{r_k^{\rm{R}}} / {\Delta f{{\log }_2}(1 + {{\bar \gamma }_{kj}})}}} \right\rceil$，其中，$\left\lceil \cdot \right\rceil$为向上取整函数。那么，HTC用户k到基站j的瞬时传输速率为$r_{kj}^s = n_{kj}^{\rm{R}}\Delta f{\log _2}(1 + \gamma _{kj}^{\rm{ave}})$。

在M2M通信中，MTC设备也考虑采用竞争随机接入方式，将接入限制(Access Class Barring, ACB)机制^[12]与竞争随机接入相结合，来保证不同类型MTC设备的QoS需求。在ACB机制中，每个基站都会广播一个接入参数p，称为ACB因子，然后每个设备产生一个随机数q。当q < p时，设备可以接入基站。否则设备按照基站设定的回退参数，确定下一次发起接入的时间。与传统的ACB机制不同，本文考虑每个基站向MTC设备广播一组ACB因子${{\boldsymbol{U}}_j},\forall j \in \mathcal{N}$，其中${{\boldsymbol{U}}_j}$包含针对不同类型的MTC设备的QoS需求的多个ACB因子，如对于实时性要求高的MTC设备，其ACB因子大，对于那些容延迟类的MTC设备，其ACB因子小。在接收到${{\boldsymbol{U}}_j}$后，MTC设备$d \in {\cal{B}}_j^{{\rm{MTC}}}$根据节点的类型确定自己的ACB因子u_dj。此外，为了简化接入控制协议，本文没有考虑ACB机制和竞争随机接入过程失败后的退避机制。

设${\tilde L_j}$表示基站j在为HTC用户分配资源之后剩余的资源块数量。对于一个给定的资源块，MTC设备d竞争成功的概率为$p_{dj}^{\rm{S}} = {u_{dj}}{p_{dj}}{\left( {1 - {p_{dj}}} \right)^{\left| {{\cal{B}}_j^{\rm{MTC}}} \right| - 1}}$，其中，p_dj表示在基站j中MTC设备d选择某个资源块的概率。假设每个MTC设备都以相同的概率选择任意一个资源块，即${p_{vj}} = {p_{dj}} = {1 / {{{\tilde L}_j}}}{\rm{ = }}{p_j}$, $\forall v,$$d \in {\cal{B}}_j^{{\rm{MTC}}}$且 $v \ne d$, $\forall j \in \mathcal{N}$。

3.   上行用户分配问题

用户分配问题本质就是确定每个基站所服务节点集合，来实现某个指标最大化。因此本文的上行用户分配问题是以最大化网络整体能效为目标，确定每个基站所服务的节点集合${{\cal{B}}_j},\forall j \in \mathcal{M}$，实现两类节点QoS保障和网络负载均衡。这里将用户分配问题的一个解定义为所有节点集合的一个分割${\boldsymbol{\varOmega}} = \left\{ {{{\cal{B}}_1},{{\cal{B}}_2}, \cdots,{{\cal{B}}_N}} \right\}$。由于一个用户只能归属于一个基站，所以在一个分割中任意两个集合的交集为空，即${{\cal{B}}_f} \cap {{\cal{B}}_g}{\rm{ = }}\varnothing,\forall f,g \in \mathcal{N}$。且一个分割中所有集合的并集为全部节点，即$\bigcup\nolimits_{j = 1}^N {{{\cal B}_j}} = {\cal M}$。此外，对于一个分割中的任意一个集合${{\cal{B}}_j}$($\forall j \in \mathcal{N}$)都可拆分成由所有HTC用户和MTC设备构成的两个子集，即${{\cal{B}}_j} = {\cal{B}}_j^{{\rm{HTC}}} \cup {\cal{B}}_j^{{\rm{MTC}}}$，且${\cal{B}}_j^{{\rm{HTC}}} \cap {\cal{B}}_j^{{\rm{MTC}}} = \varnothing$。为了从数学上描述这个问题，首先对节点的能效和网络的整体能效进行定义。

本文将节点的能效定义为单位焦耳所能传输的最大比特数，单位为bit/J。在考虑了非竞争接入控制协议后，HTC用户k的能效，记为${\rm{EE}}_{kj}^{{\rm{HTC}}}$，等于该用户到基站j的瞬时传输速率除以该用户的发送功率，即

在考虑了基于ACB的竞争随机接入控制协议后，MTC设备d的能效，记为${\rm{EE}}_{dj}^{{\rm{MTC}}}$，等于该设备到基站j最大传输速率的期望除以发射功率，即

其中，$E_{dj}^{{{\tilde L}_j}}$表示MTC设备d竞争基站j的${\tilde L_j}$个资源块所获得的平均传输速率。

当给定一个分割${\boldsymbol{\varOmega}} = \left\{ {{{\cal{B}}_1},{{\cal{B}}_2}, \cdots,{{\cal{B}}_N}} \right\}$后，基站j($\forall j \in \mathcal{N}$)的能效可表示为

其中，${\rm{EE}}_{{\rm{BS}}\_{\rm{H}}}^j$表示归属于基站j的所有HTC用户的能效之和，${\rm{EE}}_{{\rm{BS}}\_{\rm{M}}}^j$表示归属于基站j的所有MTC设备的能效之和。那么，全网整体能效可以表示为

因此，上行用户分配问题可表述为

其中，约束(1)表示HTC用户的传输速率限制，约束(2)表示任意一个节点只能分配给一个基站，约束(3)确保每一个节点都会有归属的基站。

求解该问题的一个常用方法是穷举搜索法，但是该方法的计算复杂度随着节点的增加呈指数增长，即为一个NP-hard问题。因此，本文将优化问题式(5)拆分成两个子问题：有速率保证和负载均衡的HTC用户分配子问题和有负载均衡的MTC设备分配问题。定义这两个子问题的解分别为分割${{\boldsymbol{\varOmega}} _{{\rm{HTC}}}} = \left\{ {{\cal{B}}_1^{{\rm{HTC}}},{\cal{B}}_2^{{\rm{HTC}}}, \cdots,{\cal{B}}_N^{{\rm{HTC}}}} \right\}$和${{\boldsymbol{\varOmega}} _{{\rm{MTC}}}} = \{ {\cal{B}}_1^{{\rm{MTC}}},$${\cal{B}}_2^{{\rm{MTC}}}, \cdots,{\cal{B}}_N^{{\rm{MTC}}}\}$，其中${\boldsymbol{\varOmega}} = {{\boldsymbol{\varOmega}} _{{\rm{HTC}}}} \cup {{\boldsymbol{\varOmega}} _{{\rm{MTC}}}}$, ${{\boldsymbol{\varOmega}} _{{\rm{HTC}}}}$$\cup {{\boldsymbol{\varOmega}} _{{\rm{MTC}}}}{\rm{ = }}\varnothing$。下面分别讨论这两个子问题。

3.1   有速率保证和负载均衡的HTC用户分配

有速率保证和负载均衡的HTC用户分配子问题的目标是通过确定HTC用户的分割${{\boldsymbol{\varOmega}} _{{\rm{HTC}}}} =$$\left\{ {{\cal{B}}_1^{{\rm{HTC}}},{\cal{B}}_2^{{\rm{HTC}}}, \cdots,{\cal{B}}_N^{{\rm{HTC}}}} \right\}$，在保证HTC用户的传输速率需求的前提下，最大化所有HTC用户的能效，以及在多基站间均衡HTC用户。因此，有速率保证的HTC用户分配子问题可表示为

其中，约束(1)表示HTC用户的传输速率限制，约束(2)表示分割中两个集合的交集为空集，约束(3)表示分割中所有集合的并集为整个HTC用户集合。

在HTC用户分配过程中，为了避免基站出现过载现象以及某一个基站将所有资源分配给HTC用户，每个基站设定能够用于服务HTC用户的最大资源块数目，即为$L_j^{{\rm{HTC}}}$, $\forall j \in \mathcal{N}$。每个基站可设置不同的$L_j^{{\rm{HTC}}}$，在保证HTC用户传输速率需求的同时，实现HTC用户在多基站间的均衡，以及MTC设备的性能保障。而每个基站如何设置$L_j^{{\rm{HTC}}}$不在本文的讨论范围。

此外，有速率保证的HTC用户分配子问题可视为一个多对一的匹配问题，即HTC用户根据自己的偏好申请选择接入的基站，而基站也根据自己的偏好选择接收哪些用户。为了求解这个匹配问题，首先需要定义偏好关系，利用该关系，HTC用户和基站能够对彼此进行逐一排序。

首先，将HTC用户$k \in \mathcal{K}$在所有基站集合$\mathcal{N}$上的偏好关系定义为${ \succcurlyeq _k}$，对于任意两个基站$a,b \in \mathcal{N}$, $a \ne b$，都有

其中，${D_{ka}}$和${D_{kb}}$分别表示HTC用户k与基站a和基站b之间的距离。令${\mathcal{A}_j}$表示基站j的申请者集合。然后，将基站$j \in \mathcal{N}$在其申请者集合${\mathcal{A}_j}$上的偏好关系定义为${ \succcurlyeq _j}$，对于任意两个HTC用户$s,l \in {\mathcal{A}_j}$,$s \ne l$，都有

其中，${\rm{SNR}}_{sj}^{\rm{rec}}$表示HTC用户s到基站j的接收SNR。在根据偏好关系式(8)对申请者排序后，基站j获得了一个按照降序排列的偏好列表$\mathcal{A}_j^{\rm{rank}} = \{ {z_1},{z_2},$$\cdots,{z_{\left| {{\mathcal{A}_j}} \right|}}\}$，其中${z_c} \in {\mathcal{A}_j}$，$1 \le c \le \left| {{\mathcal{A}_j}} \right|$。下面介绍每个基站根据$L_j^{{\rm{HTC}}}$和每个申请者的传输速率需求，计算最大服务用户数${q_j}$。对于任意一个给定的$\mathcal{A}_j^{\rm{rank}}$，基站j的最大服务用户数${q_j}$的计算公式为

其中，函数$W(l)$的计算表达式为$W(l) = L_j^{{\rm{HTC}}}$$- \displaystyle\sum\nolimits_{i = 1}^l {n_{{z_i}j}^{\rm{R}}}$，该函数的定义域为${\bf{dom}}\;W=\left\{l|l\in {\boldsymbol{N}}^{*},$${\text{且}}W(l)\ge 0\right\}$。

3.2   有负载均衡的MTC设备分配

在第2个子问题中，根据HTC用户的分配结果${{\boldsymbol{\varOmega}} _{{\rm{MTC}}}}$，各个基站确定MTC设备分配方案，即MTC设备分割${{\boldsymbol{\varOmega}} _{{\rm{MTC}}}} = \left\{ {{\cal{B}}_1^{{\rm{MTC}}},{\cal{B}}_2^{{\rm{MTC}}},\cdots,{\cal{B}}_N^{{\rm{MTC}}}} \right\}$，达到最大化所有MTC设备能效的目的。因此，有负载均衡的MTC设备分配子问题可表示为

其中，约束(1)表示分割中两个集合的交集为空集，约束(2)表示分割中所有集合的并集为整个MTC设备集合。

从式(2)可知，MTC设备的能效与接入冲突概率和ACB因子有关。在MTC设备分配阶段，MTC设备会倾向被分配到接入冲突概率低，且ACB因子高的基站，来保证能效的最大化。因此，第2个子问题以最大化能效为目标进行MTC设备分配，就等于实现网络负载均衡和MTC设备的QoS保障。

4.   有QoS保障和负载均衡的两阶段能量有效用户分配算法

4.1   算法描述

在第3节中，上行用户分配优化问题式(5)被拆分两个子问题式(6)和式(10)。因此本节将提出一种有QoS保障和负载均衡的能量有效用户分配(Energy Efficient User Association for QoS guarantees and Load balance, EEUAQL)算法，来求解两个子问题。下面依顺序介绍EEUAQL算法的两个过程。

在有速率保证和负载均衡的HTC用户分配子问题中，受到文献[13]提出的延期接收(deferred acceptance)方法的启发，本节设计一个基于偏好的分布式迭代准入(Preference-based Distributed Iterative Admission, PDIA)子算法来获得第1个子问题的解，即HTC用户的分割${{\boldsymbol{\varOmega}} _{{\rm{HTC}}}}$。PDIA子算法的详细过程如表1的阶段1所示。对于HTC用户，他们可以选择最能够保证速率需求的基站。对于基站，利用偏好列表，它们可以用更少的资源块来保证HTC用户的传输速率需求。此外，PDIA子算法在保证HTC用户的传输速率需求的前提下，通过设置每个基站最大服务数目，实现多基站间HTC用户均衡，从而有效地避免基站出现超载以及预留给MTC设备的资源过少的问题。

表 1  有QoS保障和负载均衡的能量有效用户分配(EEUAQL)算法

阶段1：基于偏好的分布式迭代准入(PDIA)子算法

初始化迭代次数${t_1} = 0$；每一个HTC用户根据式(7)定义的偏好关系对所有基站排序，然后向偏好程度最高的基站发送接入申请和传输速率需求；

在收到基站发送的申请后，

For 基站j，$j = 1:N$

基站j根据式(8)计算得到偏好列表$\mathcal{A}_j^{\rm{rank}}$，并根据式(9)计算${q_j}$；

如果${q_j} \ge \left| {{\mathcal{A}_j}} \right|$，基站j将所有的申请者都添加到接收列表中，否则，基站j只是将偏好列表$\mathcal{A}_j^{\rm{rank}}$中前${q_j}$个申请者添加到接收列表中，并拒绝其他申请者；

End For

Repeat

新一轮的申请开始：首先，被拒绝的HTC用户将申请接入偏好程度次好的基站；

For基站j，$j = 1:N$

基站j会获得一个基于新申请者和已经接收的HTC用户的新偏好列表，并且重新计算${q'_j}$；

如果${q'_j}$大于申请者和已经接收的HTC用户数目之和，基站j将所有的申请者都添加到接收列表中，

否则，基站j只是将新偏好列表中前${q'_j}$个申请者添加到接收列表中，拒绝其他申请者；

End For

${t_1} = {t_1}{\rm{ + }}1$;

Until 所有HTC用户都在基站的接收列表中，然后得到HTC用户的分割${{\boldsymbol{\varOmega}} '_{{\rm{HTC}}}}$。

阶段2：最大化能效的转移(TEEM)子算法

初始化迭代次数${t_2} = 0$；每一个MTC设备向距离自己最近的基站发送申请，此时形成一个初始MTC设备分割${\boldsymbol{\varOmega}} _{{\rm{MTC}}}^{\rm{initial}}$；

根据${\boldsymbol{\varOmega}} _{{\rm{MTC}}}^{\rm{initial}}$和HTC用户的分割${{\boldsymbol{\varOmega}} '_{{\rm{HTC}}}}$，基站两两之间进入如下MTC设备转移过程：

Repeat

For基站$a$, $b = a + 1:N,$

For 基站b, $b = a + 1:N,$

基站a与基站b遍历两个集合的所有元素，若存在满足转移条件式(11)的MTC设备，执行转移；

End For

End For

${t_2} = {t_2}{\rm{ + }}1$;

Until 没有基站进行转移，即可获得MTC设备分割${{\boldsymbol{\varOmega}} '_{{\rm{MTC}}}}$。

下载: 导出CSV 

| 显示表格

考虑到MTC设备数量多、处理能力低且功耗要求低的特点，所设计的MTC设备分配算法最好能够降低设备与基站间的数据交互次数，利用基站和用户之间有限的信息，获得MTC设备的分配结果。因此，针对有负载均衡的MTC设备分配问题，本文设计一种最大化能效的转移(Transfer for Energy Efficiency Maximization, TEEM)子算法，以基站为执行主导，在利用MTC设备与基站间的有限反馈信息，通过MTC设备在多基站间的转移，求解该优化问题。算法的主要思想如下。

首先，MTC设备也向离自己最近的基站申请接入。假设每个基站都接收所有申请。所以这时可以得到MTC设备的一个初始分割${\boldsymbol{\varOmega}} _{{\rm{MTC}}}^{\rm{initial}} =$$\left\{ {\hat {\cal{B}}_1^{{\rm{MTC}}},\hat {\cal{B}}_2^{{\rm{MTC}}}, \cdots,\hat {\cal{B}}_N^{{\rm{MTC}}}} \right\}$。由于所有MTC设备按照距离接入基站，所以容易造成有些基站的MTC设备数目过多或过少。因此，基站间有动力通过转移MTC设备均衡网络负载，来增加全网整体能效。然而并不是所有MTC设备转移都能带来全网的整体能效增加，所以需要定义基站间的MTC设备转移规则，避免不必要的转移。当满足以下转移条件时，MTC设备d从基站a转移到基站b

其中，转移条件式(11a)表明转移后能够保证用户的能效增加。转移条件式(11b)表明转移能够增加两个基站的能效，会使得全网整体能效增加。在MTC设备分割${\boldsymbol{\varOmega}} _{{\rm{MTC}}}^{\rm{initial}}$和HTC用户的分割${{\boldsymbol{\varOmega}} '_{{\rm{HTC}}}}$的基础上，每次迭代中，基站之间进行满足条件式(11a)和式(11b)的MTC设备转移，来最大化全网整体能效。当基站间停止转移MTC设备时，即可得到第2个子问题的解${{\boldsymbol{\varOmega}} '_{{\rm{MTC}}}} =$$\left\{ {{\cal B}_1^{{\rm{'MTC}}},{\cal B}_2^{{\rm{'MTC}}}, \cdots ,{\cal B}_N^{{\rm{'MTC}}}} \right\}$。TEEM子算法的详细过程请参见表1的阶段2。

TEEM子算法在执行过程中，同时考虑了用户能效和全网的整体能效增加。在算法的执行初期，通过MTC设备向基站发送申请，基站获得用户的信息。然后利用该信息，基站间进行协商和计算，最终获得MTC设备的分配方案。由于在该子算法的整个执行过程中MTC设备只需与基站交互一次信息，所以算法实现难度小，适合大规模MTC设备场景中的用户分配问题。

4.2   算法的收敛性和复杂度分析

通过下面的定理分析算法的收敛性。

定理1　当所有基站的资源大于所有HTC用户所需资源时，EEUAQL算法能够收敛到一个分割${{\boldsymbol{\varOmega}} ^{\rm{final}}}$。

证明　首先证明PDIA子算法的收敛性。当所有基站的资源大于所有HTC用户所需资源时，即基站有充足的资源保障HTC用户的传输速率需求，所用HTC用户都可以被基站所接收。因此，PDIA子算法在这个条件下，一定能够收敛到一个分割${\boldsymbol{\varOmega}} _{{\rm{HTC}}}^{\rm{final}}$。

下面来分析TEEM子算法的收敛性。TEEM子算法在每一执行转移时，都会可得一个新的分割。同时，根据转移条件式(11b)可知，每次转移都在增加整体能效。因此TEEM子算法的转移过程可以看成一个全网整体能效单调递增的MTC设备分割前进路径，即${\boldsymbol{\varOmega}} _{{\rm{MTC}}}^{\rm{initial}} \to {\boldsymbol{\varOmega}} _{{\rm{MTC}}}^1 \to {\boldsymbol{\varOmega}} _{{\rm{MTC}}}^2 \to \cdots$。注意在前进路径中的两个相邻分割只有一个MTC设备发生转移。又因为MTC设备的分割总数是有限的，等于贝尔数(Bell number)^[14]，所以全网的整体能效一定存在上限。因此，TEEM子算法的转移过程一定能够收敛到一个最终的MTC设备分割${\boldsymbol{\varOmega}} _{{\rm{MTC}}}^{\rm{final}}$。

综上所述，EEUAQL算法一定能够收敛到一个最终分割${{\boldsymbol{\varOmega}} ^{\rm{final}}} = \left\{ {{\boldsymbol{\varOmega}} _{{\rm{HTC}}}^{\rm{final}},{\boldsymbol{\varOmega}} _{{\rm{MTC}}}^{\rm{final}}} \right\}$。定理得证。

下面分析EEUAQL算法复杂度，其中，主要分析算法执行过程中的计算次数和发送消息数量这两个指标。首先分析PDIA子算法。本节主要分析在最差情况下PDIA子算法的最大迭代次数和所有HTC用户发送消息的最大值。由定理1可知，当网络资源不足时，PDIA子算法无法收敛。因此，这里只考虑基站处的资源块数量多于所有HTC用户所需数量。在每一次迭代中，每一个没有被基站接收的HTC用户向其可选的偏好程度最高基站(去除被拒绝过的基站)发送接入申请和传输速率需求。每一个接收到申请的基站计算偏好列表和最大服务用户数。如果所有HTC用户具有相同选择基站的偏好顺序，且对于偏好顺序中前M–1个基站，每一个基站的最大服务用户数目为1，最后一个基站的最大服务用户数目等于H，这时PDIA子算法所需的迭代次数和HTC用户与基站间的数据交互信息都是最多的。在经过T次迭代后，还没有被基站所接收的HTC用户数为H–T。由于基站有足够的资源，当所有HTC用户被基站所接收时，迭代次数达到最大值，记为${T_{\max }}$。此时，$H - {T_{\max }} = 0$。因此，迭代计算复杂度为$\mathcal{O}\left( H \right)$。再者，所有HTC用户发送消息数量的最大值，记为${{\rm{SE}}_{\max }}$，可表示为

然后分析TEEM子算法的复杂度。在TEEM子算法执行过程中，每个MTC设备只需要向基站发送一次消息。在每次迭代中，所有基站都要两两进行MTC设备转移判断，计算出这两个基站的MTC设备哪个符合转移条件式(11a)和式(11b)，因此每次迭代总共需要计算DN次。假设TEEM子算法经过W次迭代后收敛，那么这个过程中的计算复杂度为$\mathcal{O}\left( {WDN} \right)$，发送的总消息数目为$\mathcal{O}\left( D \right)$。

5.   仿真结果分析

本节通过数值仿真结果评估所提算法的性能。仿真中，考虑在一个1000 m×1000 m的方形区域中存在宏基站、皮基站和飞基站3种类型基站。皮基站和飞基站的数目分别表示为${N_{\rm{pico}}}$和${N_{\rm{femto}}}$，而宏基站、皮基站和飞基站可用的资源块数目分别表示为${{\rm{RB}}_{\rm{macro}}}$, ${{\rm{RB}}_{\rm{pico}}}$和${{\rm{RB}}_{\rm{femto}}}$。在下面的仿真中考虑5种MTC设备类型，每个基站对于这5类设备的ACB因子设置为${{\boldsymbol{U}}_j} = \left\{ {0.1,0.3,0.5,0.7,1} \right\}$($\forall j \in \mathcal{N}$)，且在每个基站中的5类MTC设备数量相等。每个基站分配预留给HTC用户的资源比例为50%，即每个基站用于服务HTC用户和MTC设备的资源各占1/2。HTC用户和MTC设备的发送总功率分别设置为23 dBm和18 dBm。本节所有仿真结果都是通过MATLAB仿真软件采用蒙特卡罗仿真方法所获得的。仿真中的每一个HTC用户的最小传输速率设定为2 Mbps。

图1—图4中的术语含义如下：基于负载均衡的用户分配(User Association for Load Balance, UALB)算法表示文献[5]中所提的用户分配算法；基于大学招生博弈用户分配(User Association based on College Admission Game, UACAG)表示文献[8]中所提适用于上行传输的用户分配算法；Max SNR算法表示文献[15]中所提的基于接收SNR的用户分配算法，即每个节点都会分配到具有最大接收SNR的基站；随机分配(Random Allocation, RA)算法表示随机用户分配算法，即每个节点会随机分配到某个基站；平均分配(Average ALlocation, AAL)表示平均用户分配算法，即每个基站分配的用户数目相同。

图 1  EEUAQL算法的收敛速度曲线图

下载: 全尺寸图片 幻灯片

图 2  HTC用户平均传输速率随MTC设备数目变化曲线图

下载: 全尺寸图片 幻灯片

图 3  整体能效随基站的资源块数目变化曲线图

下载: 全尺寸图片 幻灯片

图 4  不同算法的Jain公平指数对比柱状图

下载: 全尺寸图片 幻灯片

图1描述了节点数目对EEUQAL算法收敛性能的影响。其中，图1(a)给出了PDIA子算法的收敛性。从图1(a)可看出，PDIA子算法的收敛速度很快(当HTC用户数目为100时，算法收敛的平均迭代次数不超过4次)。同时，PDIA子算法收敛所需要的平均迭代次数随着HTC用户数量的增加而增加。但是，增加基站数量却能够降低算法的平均迭代次数。这是因为在增加基站数量后网络可用的资源也会迅速地提升，每次迭代中被基站拒绝的用户数变少了，所以完成接收相同数量的HTC用户所需的平均迭代次数会降低。图1(b)描述了TEEM子算法的收敛性能曲线图。图1(b)显示，TEEM子算法收敛的平均迭代次数不会随着MTC设备数增加而改变。这是由于TEEM子算法主要是在基站间迭代计算，算法的收敛速度与MTC设备的数目无关。并且TEEM子算法的收敛速度对基站数目的变化也不敏感。因此，TEEM子算法非常适用于解决大规模MTC设备场景下的用户分配问题，且收敛速度较快。

图2描述MTC设备数目对HTC用户平均传输速率的影响。其中，该仿真图中的参数设置如下：$K =$$100$, ${N_{\rm{pico}}} = 4$, ${N_{\rm{femto}}} = 10$, ${{\rm{RB}}_{\rm{macro}}}{\rm{ = }}150$, ${{\rm{RB}}_{\rm{pico}}} =$${\rm{100}}$和${{\rm{RB}}_{\rm{femto}}}{\rm{ = 50}}$。从图2可知，EEUQAL算法能够满足HTC用户的最小传输速率需求。同时，在本文所提的EEUQAL算法中，HTC用户的平均传输速率不会受到MTC设备变化的影响。而对于UACAG, UALB, Max SNR, AAL以及RA算法，由于采用竞争接入协议，HTC用户的平均传输速率会随着MTC设备数目的增加而降低。这一结果也验证了本文所提非竞争接入协议是保证HTC用户传输速率需求的一种有效的方法。由于考虑基站间的负载均衡，UACAG和UALB算法在HTC用户的平均传输速率方面要优于Max SNR, AAL以及RA算法。

图3描述了基站的资源块数目对整体能效的影响。其中，该仿真图中的参数设置如下：$K = 5$, $D = 10$, ${N_{\rm{pico}}} = 1$和${N_{\rm{femto}}} = 1$。在该仿真中，假设所有基站都具有相同的资源块数目${{\rm{RB}}_{{\rm{num}}}}$，即${{\rm{RB}}_{\rm{macro}}} = {{\rm{RB}}_{\rm{pico}}} = {{\rm{RB}}_{\rm{femto}}} = {{\rm{RB}}_{{\rm{num}}}}$。如图3所示，EEUQAL算法能获得与ES算法相同的性能，而且明显要优于UACAG, UALB和Max SNR算法的性能。而且随着基站的资源块数目增加(成功接入概率增加)，这3种算法与EEUQAL算法之间的性能差距会越来越大。由于考虑了上行用户分配的特点，UACAG算法的性能要优于UALB算法。从图3可知，在每个基站的资源相对充足的情况下，选择信道质量好的飞基站接入能够获得更好的能效，所以Max SNR算法获得的全网整体能效要高于UALB算法。

图4利用Jain公平指数^[16](Fairness Index, FI)描述了不同算法的公平性。该仿真图中的参数设置如下：$K = 10$, $D = 1000$, ${{\rm{RB}}_{\rm{macro}}}{\rm{ = }}150$, ${{\rm{RB}}_{\rm{pico}}} =$${\rm{100}}$和${{\rm{RB}}_{\rm{femto}}} = 50$。Jain公平指数FI可表示为${\rm{FI}} = {{{{\left( {\displaystyle\sum\nolimits_{j = 1}^N {{\rm{EE}}_{\rm{BS}}^j} } \right)}^2}} \bigg/ {{{\displaystyle\sum\nolimits_{j = 1}^N {\left( {{\rm{EE}}_{\rm{BS}}^j} \right)} }^2}}}$。指数FI的值越接近1，每个基站的能效值越接近，公平性越好。这就意味着分配结果的负载均衡性能越好。图4表明，本文所提算法的公平性能最好(公平指数接近1)。这是因为EEUAQL算法在分配节点时会考虑每个基站当前的服务能力，不会在某些基站出现过载现象。当基站数目较少时(如$N = 5$)，由于Max SNR和UALB算法会导致资源较少的飞基站服务过多的节点，这就会导致飞基站的能效性能降低，所以这两种算法的公平性能要劣于EEUAQL, UACAG和RA算法。但是随着基站数的增加，每个飞基站所服务的节点数减少，所以Max SNR和UALB算法的公平性也在不断地提升。

6.   结论

本文研究H2H和M2M业务共存下有QoS保障和负载均衡的用户分配问题。考虑到H2H通信的高优先级，HTC用户采用非竞争的接入控制策略来保证其传输速率需求。而MTC设备采用基于接入限制的竞争随机接入控制策略以保证其QoS需求和网络负载均衡。在考虑两种接入控制策略对能效的影响后，将最大化节点能效的用户分配问题拆分成两个子问题，在最大全网能效的同时，实现HTC用户和MTC设备的QoS保障以及多基站间的负载均衡；为求解这两个优化问题，提出一种有QoS保障和负载均衡的两阶段能量有效用户分配算法，即EEUAQL算法，并分析了该算法的收敛性和复杂度。仿真结果表明，提出的EEUAQL算法能够同时保证HTC用户和MTC设备的QoS需求，并且获得最好的公平性。同时，与其他算法相比，EEUAQL算法能够利用有限的资源服务更多节点。这就表明EEUAQL算法能够适用于解决大规模节点场景中有QoS保障的用户分配问题。