多基站协作无线资源分配方法

宋亚楠，仲 茜，曲光亮，李兴立

(1. 清华大学计算机科学与技术系，北京 10008 4；2. 72241部队，济南 25002 9)

多基站协作无线资源分配方法

宋亚楠1,2，仲 茜2，曲光亮2，李兴立2

(1. 清华大学计算机科学与技术系，北京 10008 4；2. 72241部队，济南 25002 9)

现有基于效用的无线网络资源分配方法大多未考虑网络整体效用最优的问题，只关注基站内的资源分配最优化，没有将基站选择问题与基站内资源分配问题相结合。鉴于此，提出一种基于效用的多基站协作无线资源分配方法，将无线网络资源分配划分为2个阶段，即基于拥塞度选择基站与基于边际效用实现基站内的资源分配。仿真实验结果表明，在268次基站选择中，该方法与效用最优的基线方法有218次相同，占81.3%，但其平均用时只有0.066 s，远低于基线方法的0.926 s，从而验证了该基站选择方法的合理性，以及基站内资源分配方法的有效性和高效性。

效用；效用函数；边际效用；无线网络；资源分配；多基站协作

1 概述

效用(utility)资源分配方法[1-2]克服了传统的基于带宽共享的分配方法[3-4]在满足用户对网络服务质量(Quality of Service, QoS)需求方面的不足，成为网络资源分配研究的热点。效用原本是经济学中的概念，由文献[5]引入到网络研究中，表示用户对网络服务质量的满意程度。随着无线网络的高速发展[6]，无线网络中利用效用的资源分配问题逐渐引起了研究人员的重视，出现了许多有价值的研究成果[7-8]。特别是文献[9]在文献[8]的基础上，提出了统一形式的效用函数和多业务下基于效用的资源分配方法，是较有效的无线网络资源分配方法。然而上述方法只关注单一无线基站的资源分配，忽略了基站选择对网络整体效用的影响，无法获得网络整体效用最大化。并且，资源分配方法的速度较低，在实际应用中存在一定的实用性问题。

为了克服目前方法的不足，本文提出了一种两阶段多基站协作无线网络资源分配方法，该方法首先基于拥塞度选择基站，与传统的基于信号强度的基站选择方法[10]相比，该方法综合应用信号强度、资源总量、资源需求量等参数，更全面合理；然后利用高速的基于边际效用的资源分配方法[2]实现各个基站内的资源分配。

2 基本概念

定义1 效用函数是效用的量化表示形式，记作U(ri)，ri为服务i分配到的资源参数(如带宽)。

定义2 边际效用指在一定时间内消费者增加一个单位商品或服务所带来的新增效用。

定义3 边际效用函数是相关网络资源参数与边际效用间的映射关系，记作u(ri)，是U的导函数。

[2-5]，将网络业务分为弹性业务和非弹性业务。弹性业务(如Web、Email等)和非弹性业务(如VoIP、IPTV等)如图1所示。

图1 弹性、非弹性业务的边际效用函数曲线

3 模型与求解

3.1 模型应用场景

图2为典型的具有资源控制实体功能的无线网络示意图，无线基站1有效区域中的用户数量远比无线基站2有效区域中的用户多，更易产生拥塞。当拥塞发生时，其重叠区域中的用户终端1、终端2、终端3就可能选择或切换到无线基站2，以获得整体网络效用最大。

图2 具有资源控制实体功能的无线网络示意图

如图2所示，多基站(网络)协作资源分配由资源控制实体负责实现，如果协作资源分配的基站集合过大，会导致较大延迟，考虑到用户终端的基站选择具有局部性，因此，可以采用局部资源控制实体实现基站集合内的协作资源分配，文献[11]中对上述问题进行了研究。

基于图2描述的无线网络场景，本文提出了一种两阶段基于效用的无线网络资源分配方法，该方法不仅可以实现基站内资源分配效用最大，同时也可以确保最大化全网效用。第一阶段为基于拥塞度的基站选择。此阶段中的相关数由基站发送给资源控制实体，由其协助用户终端选择为其提供服务的基站。第二阶段基于边际效用的资源分配方法实现各基站内的最优化资源分配。

3.2 无线基站选择

移动通信和集成电路等技术飞速发展，影响与改变了传统无线网络中的单一接入技术，多种网络接入技术相互融合的异构无线网络逐渐出现并成为未来无线网络的发展趋势，同时无线移动终端能支持的服务类型也越来越丰富，譬如普通智能手机都支持多模功能和多种接入网络选择等。随着异构网络的发展，实现无隙漫游目标的提出令基站选择问题变得更广泛。目前较常用的方法是基于信号强度的方法，即选择信号强度最好的基站作为服务基站。

信道质量(Channel Quality, CQ)是无线信道通信质量的重要指标，无线信道质量的值越大，表示信道质量越好，反之亦然。无线信道质量估算通常基于某些重要的无线网络性能参数，如信噪比(Signal to Noise Ratio, SNR)、信干噪比(Signal-to-Interference plus Noise Ration, SINR)、信噪失真比(Signal-to-Noise plus Distortion Ratio, SNDR)等。除了与上述参数有关外，还与无线通信系统的传输(调制)方案有关。如使用CDMA(Code Division Multiple Access)方案的无线通信系统使用的估算方法与采用OFDM(Orthogonal Frequency Division Multiplexing)方案的估算方法不同，同时它也与接收器类型有关，其中还需要考虑各种对通信性能产生损害的因素，如多普勒频移、信道估算误差、干扰等。通常在所采用的传输方案和相关约束条件间进行综合权衡确定估算参数。文献[12]给出了一个基于SNR的无线信道强度估算方法。

3.3 基于效用的无线网络资源分配模型

文献[2]给出本文的分配模型：

其中，Ui为第i个基站的效用值；Ci为基站i的总资源数；n为基站数；Ri为第i个基站被分配的资源，通常为时域或频域资源。

基站内部的资源分配模型由下式描述：

3.4 弹性、非弹性业务的边际效用与效用函数

3.4.1 弹性业务的边际效用函数与效用函数

弹性业务的边际效用与效用函数如下：

其中，r为无线网络资源；q为信号强度；b为有效资源。通过λ可调整效用增长的快慢，通过µ可调整基本可用状态(边际效用最大)的资源量。

3.4.2 非弹性业务的边际效用函数与效用函数

非弹性业务的边际效用与效用函数如下：

其中，σ表示梯度；µ表示边际效用最大时的资源。

关于上述效用函数的具体特征和相关参数的确定方法请参见文献[2]。

3.5 模型求解

与模型定义相适应，采用两阶段求解方法，式(1)模型求解方法的过程描述如下：

输入T={tk|1≤k≤Nt，tk为第k个网络流，Nt为网络流数量}；BS={bsi|1≤i≤Nbs，bsi为第i个基站，其作用距离为di，Nbs为基站数量}

输出S={rk| 1≤k≤Nt，rk为分配给tk的资源}

(1)确定每个无线网络流tk的候选基站集合BSk，在BSk中选择基站bsi将tk加入其流集合Ti。

(2)在每个基站bsi中，将资源分配给Ti中的每个流，T为基站i中流的集合。

3.5.1 基站选择方法

定理 当向某个基站增加一个网络流时，式(2)模型的最优总效用值不会降低。

证明：设在增加流tk之前，式(2)模型的最优解为{ri|0＜i＜k-1}，此时的总效用值为Uk-1。增加流tk之后，显然解{r1, r2, …,rk-1, 0}为式(2)的可行解，取该解时的总效用值仍为Uk-1，所以增加tk后的最优模型总效用值Uk-1≤Uk。证毕。

随着拥塞度的提高，式(2)模型总效用的增速通常会越来越低。因为随着网络流的增加，需要将其他流的资源调整给新增流，由于非弹性流调节能力有限(要么满足其资源需求，要么不分配给它资源)，因此通常需通过调整弹性流的资源来实现；当拥塞度增大时，每个弹性流的资源占用量呈下降趋势，观察图1(a)，可以发现资源占用量越小，减少单位资源，效用下降就越大，其增速也就越低。这一点在下文的实验结果中得到了验证。基于以上分析，本文方法在为流选择基站时总选择拥塞度最低的基站，从而在流增加的同时保证总效用增长速度最快。

基站选择方法的描述如下：

输入BSk={bski|bski为tk的候选基站}

输出bsk为选中的基站

(1)tk发送接入请求至BSk中每一个候选基站bski。

(2)对于BSk中每一个候选基站bski分别就tk的请求通知资源控制实体。

(3)资源控制实体分别计算候选基站bski的拥塞度cdki。

(4)资源控制实体指定cdki最小的bski作为bsk。

根据文中的定义，拥塞度可由如下式计算：cdi=，综合考虑了信号强度、资源总量、资源需求量，比当前使用基于信号强度的方法更为合理。拥塞度的值由基站通知用户终端。

3.5.2 基站内资源分配方法

本文中基站内资源分配模型是对文献[2]中基于边际效用资源分配模型的改进，主要考虑了无线网络的特点。

其中，u为U的边际效用函数。由式(5)和式(6)可以推出式(2)中模型最优解的必要条件。

必要条件 对于任意数i 和 j (i≠j, i, j∈[1, N])，式(2)中模型全局最优解必需满足如下约束：

根据上述必要条件给出模型求解方法：

(1)式(2)模型求解方法

(2)非弹性流解的选择方法

式(2)模型求解方法中第2)步的主要问题是如何选择非弹性边际效用函数的有效资源，使总效用最大。为典型的组合优化问题，文中通过贪婪算法进行求解。

3)存储结果，结束。

第2)步中选取符合条件的最大vi′主要为了收敛速度快，并使资源和尽量接近最大可用资源量。

4 实验结果与分析

为了验证方法的求解效果和速度，设计了如下仿真实验。

4.1 实验设置

选择4类网络业务，分别是弹性业务VoIP、IPTV和非弹性业务TCP、HTTP业务。实验中设置4个基站(BS1、BS2、BS3、BS4)，如图3所示，作用距离为1.2，信道强度为[0,1]间的随机数。实验时，各流相继在阴影区域出现，其横纵坐标为[0,2]间的随机数。文献[2]设置最大有效资源(实验中为带宽)为64 00 2、107、108和107，最小有效资源量为64 000、0、0和0，Ci为109。

图3 实验基站布局示意图

4.2 参与对比的方法

基线方法：当网络流在目标区域中出现时，尝试将其分配到每个候选基站，使用本文方法在基站内实现分配，然后选择总效用最大的基站完成最终的分配。

方法1：本文方法。

方法2：将本文方法第1阶段的基站选择方法更换为传统的基于信道质量的无线基站选择方法，其他与本文方法相同。

上述3种方法的主要不同体现在基站选择上，这是实现全网效用最优的关键。基线方法直接采用了纯基于效用的方法，通过轮询各个候选基站，实现效用最优的基站选择，理论上具有最优的基站选择结果；方法1采用了基于无线网络拥塞度的方法，该方法是一种基于效用的启发式基站选择方法；方法2采用了基于信道质量的方法，这是目前实际中常采用的基站选择方法。通过对上述方法在基站选择、求解总效用和求解用时上进行比较，验证本文方法的有效性、高效性和实用性。

4.3 结果分析

4.3.1 基站分配方法分析

表1给出了实验中不同业务的网络流在不同拥塞度下，在各个基站中的分配情况。CD表示拥塞度，单元格中的数字串为实验中方法将相应业务的流分配到各基站的数量。其中，第1个数字为方法1的分配结果，第2个数字为方法2的分配结果，第3个数字为基线方法的分配结果。由表1的结果可见，从各基站相应流的数量看，在全部

160组数据中，方法1与基线方法有88组相同，占55%。在不相同的数据中，除5个值两者差距较大外(如拥塞度为10时，BS1中HTTP流的分配相差4个)，其他数据值的差距都在2个以内；方法2与基线方法只有61组相同，占38%，共有19个值超过3，其中，拥塞度为9时BS1中HTTP流和拥塞度为10时BS2中TCP流分配数量差均达到5。从具体基站选择情况看，在所有268次选择中，方法1与基线方法有218次相同，占81.3%；而方法2与基线方法只有168次相同，占67.1%。上述结果表明，同基于信道质量的基站选择方法相比，本文提出的基站选择方法的选择结果与基线方法更接近，一定程度上验证了本文基站选择方法的合理性。

表1 基站选择结果

4.3.2 求解效果及分析

各方法求解效果的对比实验结果如图4所示，在实验中参与对比的3种方法中，基线方法和方法1获得的总效用相差很小。在各拥塞度下，方法1仅比基线方法低0.28%，方法1在基站选择结果上与基线方法有所不同，但因综合考虑了资源总需求、资源总量、信道质量等因素，依然获得了理想的总效用。而方法2由于基站选择结果与前2种方法差异加大，且在选择时未充分考虑到整体效用最优问题，因此总效用较差，比基线方法低7.1%，比方法1低7%。

图4 求解效果

4.3.3 求解时间及分析

求解速度对资源分配方法至关重要，决定了所用方法的实用性，尤其是在无线网络中，运行时间的好坏直接决定方法的可行与否。如果分配方法需几分钟才能完成，即便求解结果非常好，也不可能在实际中应用。图5在求解时间上对各方法作了对比。

图5 求解时间

由图5可见，基线方法由于每次选择基站要分别计算各候选基站的效用，而其他方法则无需进行这种复杂计算。因此，基线方法的用时远高于方法1和方法2，分别为方法1和方法2的12.36倍和12.76倍。基线方法平均耗时为0.926 s，方法1为0.066 s，而方法2只有0.064 s，由于网络延迟会大大降低用户体验，因此对资源分配方法效率的要求较高，后2种方法资源分配时间均低于0.1 s，只要不是频繁发生网络切换，不会对用户应用造成影响，基本达到了实际应用的要求。

5 结束语

本文针对无线网络中的资源分配问题，提出了一种基于效用的两阶段多基站协作无线资源分配方法。该方法将资源分配过程分为2个阶段，首先根据拥塞度选择基站，然后在基站内部利用基于边际效用的方法实现高效的资源分配。实验结果表明，本文方法具有良好的求解效果和较高的求解速度。今后将针对其他新型网路，如云计算网络、数据中心网络等，研究针对性的基于效用的资源分配方法。

参考文献

[1] 宋亚楠, 仲 茜, 胡成臣, 等. 基于效用函数簇的效用类服务分层调度模型[J]. 电子学报, 2012, 40(2): 247-253.

[2] 宋亚楠, 仲 茜, 刘 斌, 等. 基于边际效用函数的网路资源调度[J]. 电子学报, 2013, 41(4): 632-638.

[3] 董春玲, 朱晓丽, 郑明春. 分层组播中MAX-MIN公平速率分配算法的运用[J]. 计算机应用, 2005, 25(3): 533-535.

[4] 贺 媛, 刘 佳, 曾烈光. 宽带无线接入网的成比例带宽分配[J]. 清华大学学报, 2008, 48(7): 1131-1134.

[5] Shenker S. Fundamental Design Issues for the Future Internet[J]. IEEE Journal on Selected Areas in Communications, 1995, 13(9): 1176-1188.

[6] 赵 晗. 现代无线通信技术的发展现状及未来发展趋势[J].企业技术开发, 2011, 30(16): 86, 89.

[7] Song Guocong, Li Ye. Utility-based Resource Allocation and Scheduling in OFDM-based Wireless Broadband Networks[J]. IEEE Communications, 2005, 43(12): 127-134.

[8] Kuo W H, Liao W. Utility-based Resource Allocation in Wireless Networks[J]. IEEE Transactions on Wireless Communications, 2007, 6(10): 3600-3606.

[9] Chen Li, Wang Bin, Chen Xiaohang. U tility-based Resource Allocation for Mixed Traffic in Wireless Networks[C]//Proc. of International Workshop o n Fu ture Media Networks an d IP-based TV. Shanghai, China: [s. n.], 2011: 91-96.

[10] 王 华, 李鲁群, 王 力. LTE-A中基于准入控制的切换决策算法[J]. 计算机工程, 2011, 37(5): 88-90.

[11] 陈 力. B 3G/4G系统中的无线资源分配的研究[D]. 北京:北京邮电大学, 2012.

[12] David R P, Norman C B. A Comparison of SN R Estimation Techniques for the AWGN Channel[J]. IEEE Transacations on Communications, 2000, 48(10): 1681-1691.

编辑 任吉慧

Multi-base-station Cooperation Wireless Resource Allocation Method

SONG Ya-nan1,2, ZHONG Qian2, QU Guang-liang2, LI Xing-li2
(1. Department of Compute Science and Technology, Tsinghua University, Beijing 100084, China; 2. 72241 Unit, Jinan 250029, China)

Most utility based wireless resource allocation methods only focus on the optimal allocation within a base station. Because of ignoring the issue of base station selection, these methods can not achieve the o ptimal utility of wh ole network. Therefore, this paper proposes a utility based multi-base-station cooperati on wireless resource allocation method, which is divided into two stages. In the first stage, base stations are selected according to their congestion degree. And in the second stage, the resource in each base station is allocated according to marginal utility. The simulation experiments show that, between the a pproach and the baseline method, of all the 268 base station selections there are 218 accounting for 81.3% having the same selection result and the average elapse time of the proposed method is only 0.066 s, which is much lower than the baseline method 0.926 s. These facts show the rationality of the base station selection method as well as the efficiency and effectiveness of the resource allocation method.

utility; utility function; marginal utility; wireless network; resource allocation; multi-base-station cooperation

10.3969/j.issn.1000-3428.2014.05.011

国家自然科学基金资助项目(61202489)。

宋亚楠(1977－)，女，讲师、博士研究生，主研方向：无线资源分配，下一代互联网络；仲 茜，讲师、博士；曲光亮，讲师、硕士；李兴立，工程师。

2013-02-20

2013-04-25E-mail：songyn77@gmail.com

1000-3428(2014)05-0049-05

A

TP393.03

·移动互联与通信技术·