贾国庆，裴　冬

(1.青海民族大学 物理与电子信息工程学院，青海 西宁 810007；2.中国科学院上海微系统与信息技术研究所 无线传感网与通信重点实验室，上海 200050）

一种基于异构云无线接入网的资源管理方案*

贾国庆1，2，裴冬2

(1.青海民族大学 物理与电子信息工程学院，青海 西宁 810007；2.中国科学院上海微系统与信息技术研究所 无线传感网与通信重点实验室，上海 200050）

基于有限网络资源和多用户队列的异构云无线接入网络，分析了两种不同用户到达场景：有突发用户到达和没有突发用户到达。提出了一种基于异构云无线接入网的高稳定动态资源管理方案：针对多队列的稳定性提出了一种基于动态背压技术的框架，利用李雅普诺夫漂移保持用户需求队列稳定；使用一种基于匈牙利算法的分配方案，以便尽量有效地将网络资源分配给各个队列成员。仿真结果表明，提出的资源管理方案能够有效保证多队列的稳定性，相较于传统的比例公平或随机分配算法，系统开销较小。

异构云网络；接入控制；无线资源分配；排队论

0　引言

异构网是应对日益增长的数据传输需求挑战的一种有效途径。文献[1]提出了一种新型的无线云接入网络，并在文献[2]中给出了详细的描述。之前针对异构网资源管理的研究主要分为两个场景：单接入网的资源分配和多接入网的资源分配。在第一个研究场景中，移动终端只能从单一的接入网中获取资源[1-3]。在第二个场景中，移动终端可以同时从所有可用的无线接入网络中获取资源，因此也被称为多寻解方案[4]。之前的研究都集中在提高传统的多队列网络的延迟性能。一种方法是使用大偏差理论将平均延迟约束转化为等效平均速率，再利用约束条件下的信息理论公式求解优化问题[5]；另一种方法是使用李雅普诺夫稳定性理论来建立一个高吞吐量的最优控制方案，例如计算机资源优化[6]，或实现分组交换系统的稳定[7-9]。

本文的研究主要集中在基站用户需求队列的稳定性，采用李雅普诺夫漂移保证队列的稳定性和改进的匈牙利来实现更高效的资源分配。

1　系统模型与问题分析

1.1网络模型

如图1所示，本文提出了一种多队列多服务的异构云无线接入网络架构。在该架构中，将节点视为队列并将节点中等待服务的用户视为队列成员，根据节点的流量来调节不同节点用户的相互转移。

假设异构云无线接入网络有 n(n∈{1，2，…，N})个节点，节点间有 l(l∈{1，2，…，L})传输链路。图2给出了多用户多服务系统图，其中λn表示网络外新到达第n个节点的数据，an表示第n个节点包括新到达数据和节点间转移数据在内的总的数据，从节点a到节点b的数据转移表示为((al，bl)，a，b∈{1，2，…，N})。S(t)∈S表示网络的拓扑状态，S是状态集。在平稳状态下，S(t)被认为是恒定的。I(t)∈IS表示分配控制决策，IS表示在给定状态S下的所有资源分配决策集。该网络结构的特点是：S(t)是根据一个有限状态空间 S和时间平均概率的不可约马尔可夫链的拓扑状态。I(t)是一个具有潜在拓扑状态的控制空间的控制决策变量。

图1　异构云无线接入网络

图2　多用户多服务系统图

C(I(t)，S(t))={Cab(I(t)，S(t))|a，b∈{1，2，…，N}，a≠b}定义为传输速率函数矩阵，其中 Cab(I(t)，S(t))表示在分配控制 IS和网络拓扑状态 S下经过链路(al，bl)的传输速率，它是有界的任意值。

1.2队列模型

用Qn(t)表示在时间间隙t时在第n个节点等待网络服务的队列成员数目，an(t)表示第 n个节点包括新到达数据和节点间转移数据在内的总的数据，un(t)表示在时间间隙t时，第n个节点中获得网络服务的用户数据，则动态队列长度表示式：

a(t)=(a1(t)，a2(t)，…，an(t))和 u(t)=(u1(t)，u2(t)，…，un(t))表示是随机事件的一般函数。表示随机事件w(t)的一般函数表达式及一个控制行为表达式为α(t)：αn(t)=an(α(t)，w(t))。每个时隙中由网络控制器观察w(t)并选择合适的α(t)∈Aw(t)，Aw(t)表示与事件 w(t)的控制空间集。李雅普诺夫漂移是一种有助于网络队列稳定并进行稳定的控制的有效数学工具，利用负李雅普诺夫漂移理论，在马尔可夫链中可以形成一个成熟的的稳定理论。

定理1：队列被称为强稳定，如果有：

即如果队列有一个有界的时间平均累积，则该队列强稳定。

定理2：如果网络中所有独立队列是强稳定的，则网络是强稳定的。

本文假设满足以下条件时，系统是稳定的：

1.3问题的定义

系统的目标是找到一个资源分配和调度方案，最大化减少队列的延迟和长度，该问题表示为：

2　高稳定性动态资源管理方案

2.1动态背压资源管理框架

如图3所示，对任一节点n，其队列模型包括：新到的数据 λn，转移数据 Dn，队列长度 Qn，网络服务量 un。在多个节点的队列的基础上进行无线资源的分配，时间间隙t表示时间为[t，t+1)。所有的节点都会存在新到用户数据，且相互独立。而转移用户数据则与节点及其相邻节点的数据流量有关，新到数据服从泊松分布，且E[λn(t)]=λn。由此根据不同的节点流量，可以将动态队列分为以下3种情况：

(1)节点只有新到数据，没有转移数据，则队列为Qn(t+1)=max[Qn(t)-un(t)，0]+λn(t)，an(t)=λn(t)；

(2)节点流量较大，会转移部分数据Dn(t)到相邻节点，Qn(t+1)=max[Qn(t)-un(t)，0]+λn(t)-Dn(t)，an(t)=λn(t)-Dn(t)；

(3)节点流量较小，会从相邻的节点中得到部分数据Dn(t)，Qn(t+1)=max[Qn(t)-un(t)，0]+λn(t)+Dn(t)，an(t)=λn(t)+ Dn(t)。

图3　典型节点的数据队列图

(1)选择合适的资源控制I(t)策略来优化如下目标：

根据各节点的队列长度和服务速率，使用改进的匈牙利算法来实现更好的效用匹配。

(2)根据式(4)即时更新队列数据。

首先介绍背压控制策略wn(t)。假设 wn(t)表示是一个概率分布为 π(w)的平稳过程，wn(t)在集合 Ω中取值，对任意 wn(t)∈Ω，π(t)表示关联队列长度 Qn(t)和到达数据an(t)的概率函数，且：

除了队列需要稳定的 Qn(t)，本文也使用一个辅助的随机相关量 y(t)，它的时间平均值会小于或接近特定值y*，假设 y(t)的下界为 ymin，因此任意时隙以及任何可能的分配控制策略都会存在E{y(t)}≥ymin。

定理 3：假设有 L(Q(t))，ymin，E[L(Q(0))]＜∞，则存在常数 B≥0，V≥0，ε≥0和 ymin，使得对任意时隙和所有的队列值，有：

则所有的队列都是稳定的，而且若V≥0，ε≥0，有：

任一时隙，网络观察当前的队列长度值Qn(t)和到达数据量 an(t)，然后用匈牙利算法来匹配 Qn(t)和 an(t)，以减少Δ(Q(τ))+VE{y(t)|Q(τ)}表示的漂移值。

2.2针对多队列的李雅普诺夫漂移技术

2.3针对资源分配的改进匈牙利算法

将 an(t)和 Qn(t)视为由 wn(t)控制的配对问题，配对问题由U和V两部分组成，以及带有权重的边集合E。假定ai(t)∈V，i∈1，2，…，N，Qj(t)∈U，j∈1，2，…，N，则 xij为n×n单位阵。假设在一个时隙内一个用户终端只能与一个基站相连接，即表示对相同的边矩阵任一行列中仅有一个值为 1，通过匈牙利算法来调制 xij以匹配相应的an(t)和 Qn(t)来实现：

3　仿真实验

仿真中，有5个节点和充足的用户终端数据。在没有突发数据到达的情况下，新到达的数据服从泊松分布，到达速率均为λ=2/3；在有突发数据到达的情况下，新到数据同样服从泊松分布，且速率也为λ=2/3，只是在某一时间节点会到达大量的用户数据。先到先服务是队列成员获得网络服务的准则，各信道状态S(t)在同一时隙相互独立，且其概率设定为20%。各节点的服务速率是固定的，网络的总服务速率为 r=1，为了计算简便，假定各节点的最大容量均为10，并给定相应的服务质量标准。

本文做了两种不同场景下的仿真，在第一种场景中，用户终端数据随机到达5个节点，由此可以得到某一时隙网络的总效用结果；在第二种场景中，200个用户终端数据到达一个节点，由此可以得到某一时隙节点的平均开销结果和队列长度。本文将所提出的方案与随机分配策略、最短优先策略和比例公平策略进行了对比，且在第二种场景中，当 V=25时，设定不同的突发用户数据量，仿真结果如图4～图6所示。

图4　所有节点的总效用

图4给出了第一种场景下的仿真结果，从图中可以看出，当V接近40时，队列趋于稳定。

图5给出了没有突发用户数据的场景，设节点服务率 r(AP5)＞r(AP4)＞r(AP3)＞r(AP2)＞r(AP1)，且 r(AP3)比r(AP2)略大。从图5可以看出，当V∈[35，50]时，各个用户队列趋于稳定，节点的服务速率越大，队列稳定的越快。然而，尽管AP3的服务速率比AP2略高，AP3的平均开销却比AP2要低一些，这表明平均开销并非仅由节点服务速率决定。当队列趋于稳定后，各节点队列的平均开销依然维持在较低值。

图6给出了没有突发用户数据场景下不同方案的总开销，结果表明本方案中队列会更快趋于稳定，且有更低的开销，比随机分配策略和比例公平策略要好，仅次于最短优先策略。

图5　各节点的平均开销

图6　不同方案的总开销

4　结论

本文研究异构的资源管理问题，重点分析了拥挤用户时的队列稳定性问题，以及用户对无线资源的需求，并提出了一种新的高稳定的动态资源管理方案。与其他研究不同之处是，本文假定各节点的容量是有限的，并进而提出了一种新的用户队列模型，在此基础上，分析了两种不同场景下的资源管理问题并进行了仿真实验。仿真结果表明，本文基于李雅普诺夫漂移和匈牙利算法的异构云无线接入网络资源管理方案，相较于传统的随机分配、比例公平以及最短有限方案而言，在队列的稳定性以及开销上有更好的性能。

[1]BLAU I，WUNDER G，KARLA I.Decentralized utility maximization in heterogeneous multicell scenarios with interference limited and orthogonal air interfaces[J].EURASIP Journal on Wireless Communications and Networking，2009，20(12)：104-116.

[2]SHEN W，ZENG Q.Resource management schemes for multiple traffic in integrated heterogeneous wireless and mobile networks[C].Proceedings of 17th International Conference on Computer Communications and Networks，US Virgin Islands，2008：1-6.

[3]PEI X，JIANG T，QU D，et al.Radio resource management and access control mechanism based on a novel economic model in heterogeneous wireless networks[J].IEEE Transactions on Vehicular Technology，2010，59(6)：3047-3056.

[4]NIYATO D，HOSSAIN E.Bandwidth allocation in 4G heterogeneous wireless access networks:A non cooperative game theoretical approach[C].Proceedings of IEEE Global Telecommunications Conference，San Francisco，CA，2006：1-5.

[5]TAO M，LIANG Y C，ZHANG F.Resource allocation for delay differentiated traffic in multiuser OFDM systems[J].IEEE Transactions on Wireless Communications，2008，7(6)：2190-2201.

[6]BHATTACHARYA P，GEORGIADIS L，TSOUCAS P.Adaptive lexicographic optimization in multi-class M/GI/1 queues[J].Math.Operat.Res.，1993，18(3)：705-740.

[7]RADUSINOVIC I，PEJANOVIC M，PETROVIC Z.An ILPF cell scheduling algorithm for ATM input-queued switch with service class priority[C].Proceedings of 6th International Conference on Telecommunications in Modern Satellite，Cable and Broadcasting Service，2003，1：26-29.

[8]KUMAR P R，MEYN S P.Stability of queueing networks and scheduling policies[J].IEEE Transactions on Automatic Control，1995，40(2)：251-260.

[9]ANDREWS M，KUMARAN K，RAMANAN K，et al.Providing quality of service over a shared wireless link[J].IEEE Commun.Mag，2001，39(2)：150-154.

A resource management scheme based on heterogeneous wireless network

Jia Guoqing1，2，Pei Dong2
(1.School of Pyhsics and Electronic Information Engineering，Qinghai University for Nationalities，Xining 810007，China；2.Shanghai Institue of Microsystem&Information Technology，Chinese Academy of Sciences，Shanghai 200050，China)

A cloud based HetNet architecture with limited network resources and multiple queues regarding to users′requirements is presented and two different users′arrival scenarios with and without burst traffic are studied.Then a novel High Stable dynamic Resource Management Scheme(HS-RMS)for the HetNet is proposed.Specifically,a dynamic backpressure technique based framework for multiple queues′stability is presented,and then a Lyapunov drift method is applied to keep users′requirement queues stable.A Hungarian algorithm based allocation scheme is provided to allocate resources to each queue member efficiently.Extensive simulations have been done,and results show that the proposed resource allocation scheme is very robust to keep the queues stable and the overhead is low as compared to conventional proportional fairness or round-robin algorithms.

heterogenous network；access control；radio resource allocation；queueing theory

TN911

A

10.16157/j.issn.0258-7998.2016.10.027

中国科学院上海微系统与信息技术研究所无线传感网与通信重点实验室开放基金（2016002）；青海省自然科学基金(2016-ZJ-922Q)

（2016-04-28）

贾国庆（1984-），男，博士，副教授，主要研究方向：无线通信物理层关键技术。

裴冬（1989-），通信作者，男，硕士研究生，主要研究方向：无线通信车联网技术，E-mail：dong.pei@wico.sh。

中文引用格式：贾国庆，裴冬.一种基于异构云无线接入网的资源管理方案[J].电子技术应用，2016，42(10)：104-107.

英文引用格式：Jia Guoqing，Pei Dong.A resource management scheme based on heterogeneous wireless network[J].Application of Electronic Technique，2016，42(10)：104-107.