中继蜂窝网中基于负载均衡的中继节点选择算法✴

江帆，王本超

中继蜂窝网中基于负载均衡的中继节点选择算法✴

江帆1，王本超2

（1.西安邮电学院通信与信息工程学院，西安710121；2.华为技术有限公司，广东深圳518129）

提出了一种中继蜂窝网络的基于负载均衡的中继节点选择策略（Load Balancing Relay Selection，LB-RS）。根据每个用户的具体信道状况以及中继节点服务的用户数目，LB-RS以分布式的方式为每个用户选择最优的中继节点。仿真结果表明，与基于单一物理层参数的中继节点选择算法相比，所提出的中继选择算法综合考虑了物理层的信道状况以及MAC层的资源与用户状况，有效地利用中继节点选择来实现小区内的负载均衡，获得了吞吐量性能与用户公平性之间的折衷。

中继蜂窝网络；中继选择；负载均衡；协作中继

1 引言

在协作中继网络中，通过合理的中继选择策略［1-4］，多个参与协作的中继以类似于虚拟MIMO的形式来实现空间分集，从而提高系统容量。目前广泛研究的中继选择策略一般基于最短距离、最小路径损耗、最大接收功率、最大信噪比等准则，用户根据不同的节点选择准则选择一个或多个最优的中继节点实现协作传输。针对不同场景下的中继节点选择问题，许多研究者都提出了相应的算法。Cai［2］探讨了AF中继转发模式下的协作节点选择与功率分配联合优化算法，研究了如何以半分布式的方式来选择一个最优中继节点的问题。Bletsas［3］提出了基于无线信道的即时测量和互异性的分布式中继选择方法。Sreng［4］研究了中继蜂窝系统中的中继选择策略，分析了基于最短距离、基于最小路径损耗和基于最佳信道状况3种中继选择策略的性能。

上述的中继选择策略一般都以不同的物理层参数（信噪比、功率、距离、路径损耗等）为依据来选择最优的中继节点，而事实上，中继蜂窝小区中的每个移动台的吞吐量不仅取决于当前物理层的信道状况，还取决于当前小区中的基站和中继节点所服务的用户数以及MAC层的调度算法。如果当前中继服务的用户数过多，即使选择了最优的中继节点，仍然不能保证获得最大的用户吞吐量，这是因为无法保证中继节点有足够的资源，使得用户能够通过中继节点而获得协作传输增益。

为了解决上述问题，本文首先提出了一种理想条件下基于负载均衡的集中式中继节点选择算法，并分析了其应用中存在的问题。在此基础上，提出了一种基于负载均衡分布式的中继节点选择算法（LB-RS）。LB-RS综合考虑了每个用户的信道状况以及其所选择中继节点的服务用户数目，以分布式的方式为每个用户选择最优的中继节点，从而在避免选择热点中继节点的同时有效提高了用户吞吐量，获得吞吐量性能与用户公平性之间的折衷。

2 算法描述

2.1 系统模型

假设系统中有N个小区，每个小区中布设6个位置固定的中继节点（RN），如图1所示。整个系统中均匀分布着K个移动台（MS），对于任意一个移动台k（k∈K），仅能选择一个基站i（i∈N）作为其服务基站（BS）。小区内部采用OFDMA物理层接入技术，每个MS根据当前信道状况决定直接接入BS或者通过RN两跳接入BS。为了减小用户之间的干扰，每个MS使用1个正交的子信道接入。假设MS和RN可以完全获得信道状态信息。小区内是全网时间同步的，将时间轴划分为一系列的时间帧，若MS直接接入BS，则MT在每个时隙内直接将数据发送到BS；若MS采用协作传输接入BS，则MS在第1个时隙向RN发送数据请求，RN在第2个时隙向BS转发从MT收到的数据。RN以解码转发（DF）的方式工作。

2.2 基于负载均衡的集中式最优中继节点选择算法

首先从经济学角度建立使得整个网络效用最大的多小区效用模型［5］：

式中，R（t）表示系统中k个用户效用之和，Uk（·）表示时刻t时用户k平均吞吐量的非递减效用函数，Tk（t）表示用户k的平均吞吐量。因此，在中继蜂窝小区中，当用户选择两跳传输时，最优的中继节点选择策略的目标应该使得R（t）最大。定义分配指示变量：

用来标识t时刻移动台k选择位于小区i中的中继节点m来实现两跳协作传输，则分配指示矢量I（t）=｛Ii，m，k（t），i∈1，2，…，N，m∈1，2，…，6，k∈1，2，…，K｝代表了基站、中继、用户之间的一一对应关系。另外，I（t）仅仅是整个解集中的一个解，因此式（1）变换为

约束条件为

其中，式（4）表示一个MS仅能选择一个小区内的一个RN，而式（5）和式（6）表示对于BS或者RN来说，每个时隙内每个子信道只能分配给一个MS使用。

对小区中的用户k来说，在时刻t定义其到小区中基站i、到小区中任意一个中继节点m以及中继节点m到基站i的3条链路的SINR可以表示为

式中，pk、pm分别表示MS和RN的发射功率，li，k（t）、lk，m（t）、lm，i（t）分别表示t时刻MS到BS、MS到RN以及RN到BS的路径损耗，hk，i、hk，m、hm，i分别代表MS到BS、MS到RN以及RN到BS的多径衰落以及阴影衰落，式（7）～（9）的分母分别表示来自于本小区及其它小区的MS到BS、MS到RN以及RN到BS的干扰以及接收端白噪声之和。

根据香农定理，若t时刻用户k直接接入基站，则用户k在带宽B上可达数据速率上限为

如果用户通过中继m以协作传输的方式两跳接入基站，则用户k在带宽B上可达数据速率的上限为

假设信道是遍历性的，则用户k在t时隙末的平均吞吐量可表示为

从式（12）中可看出，Tk（t）的取值不仅取决于当前时隙的用户k的可达数据速率，还取决于当前的分配指示矢量Ik，m，i（t），而Ik，m，i（t）的取值又受到用户k所在小区的基站及中继所服务的用户数、具体的资源状况和调度算法的影响。

理想状况下，为了使MS的吞吐量最大，BS需要根据MS的信道状况、RN的服务用户数、资源状况选择最优的中继节点。假设每个时隙Δt足够小，对于构造的非递减效用函数，在逐个时隙上取最陡的梯度值，则到每个MS在每个时隙上Δt最优的中继节点选择集合I*（t）为

其中Tk（t）可以根据下式［6］

来计算，并且Ik，m，i（t）的取值受限于式（4）和式（6）。式（13）所给出的最优中继节点选择集合I*（t）表示了使得每个MS吞吐量最大的基站、中继、用户之间的一一对应关系。由于BS需要综合考虑当前小区中MS的信道状况、BS和RN的服务用户数、资源的分配情况来在每个时隙动态为每个MS选择最优的中继节点Ik，m，i，因此，求解出的中继节点选择集合对每个MS都是最有效的。从而式（13）表示了理想状况下，具有负载均衡特性的集中式最优中继选择算法。如果以BS为中心，利用匈牙利算法［7］，通过穷尽搜索来选择最优中继节点，可获得最差情况下算法的复杂度为O（K6N）。

但是，在实际系统中，如果采用上述集中式的方式选择最优的中继节点，每个BS需要在每个时隙实时地获得当前MS在系统中所有小区内的每个子信道上瞬时速率以及t-1时刻的MS的吞吐量，然后以集中式的方式来计算。运算的复杂度以及所需的实时信息量，都使得该最优中继选择集合在实际的多小区系统中难以获得。

2.3 LB-RS算法

为了解决上述集中式算法在实际中的应用问题，提出如下的基于负载均衡的分布式中继节点选择策略。

（1）每个MS根据当前信道状况确定采用直接传输或者通过中继实现两跳协作传输。如果直接传输能获得更大的增益，则用户k直接将数据发送给BS；否则用户k采用两跳协作传输。

（2）如果MS采用两跳协作传输，首先在本小区内计算每个中继节点信号的接收信噪比（SINR），并侦听每个中继节点当前所服务的用户数；然后，在周围小区中选择一个接收到信噪比最大的中继节点，并侦听其所服务的用户数。

（3）MS根据式（11）计算选择不同中继节点的两跳传输可达速率建立中继节点选择函数

选择使式（15）最大的中继节点。

（4）根据具体的调度策略，在MS所分配的子载波上进行两跳传输。

之间的信道状况以及中继节点的服务用户数目，选择能够兼顾用户负载均衡以及吞吐量的中继节点，避免由于选择某些热点中继节点而造成无法协作传输的情况，从而提高系统资源利用率，得到性能与用户公平性之间的折衷。

3 仿真结果及性能分析

3.1 仿真参数设定

考虑一个工作在3.5 GHz频段的OFDMA蜂窝系统，包含有27个蜂窝小区，每个小区中均匀布设6个RN，小区半径为1 km，中继节点位于小区半径2／3处。

仿真参数选用3GPP LTE目前所规定的OFDMA系统的参数：时隙长度1ms，每时隙OFDM符号数14个；每个调度时隙包含24个子信道，每个子信道包含12个子载波数，每个子载波带宽15 kHz。假定收发信机之间保持时间同步。每个MS的发射功率PMT=50mW，RN的发射功率PRN=1W，接收机热噪声σ2=10-10W。

3.2 仿真结果

为了进行对比，我们在仿真实验中分别考虑了4种中继选择策略下的用户吞吐量以及公平性性能：一是直接传输（Without Relay，W／O Relay）；二是基于最小距离的中继选择策略（Shortest Distance Based Relay Selection，SD-RS）；三是基于最大SINR的中继选择策略（Maximum SINR Based Relay Selec

tion，MSINR-RS）；四是本算法提出的中继选择策略（LB-RS）。假设在每个资源分配时隙，每个中继节点最多能够同时服务8个MS。所采用资源调度的准则是照轮询调度（Round Robin，RR）［8］。

图2给出了随着小区中用户数目增加，小区用户吞吐量的变化情况。从仿真结果中可以观察到，当小区中用户数目较少时（用户数小于20时），SDRS、B-RS及MSINR-RS的性能都好于直接传输的性能，且三者性能差别不大。但是，随着用户数目的增加，由于每个中继覆盖范围内的用户数增加，更多的用户会选择协作传输机制，从而导致某些中继节点需要服务的用户数激增。然而，无论采用SD

RS，还是采用MSINR-RS，都无法避免用户拥塞的发生。而根据所提出的LB-RS中继选择算法，每个用户都会根据当前时隙其自身的信道状况，结合中继节点的用户服务数目，以分布式的方式来综合选择最优的中继节点，使得某些负载较轻的中继节点能够帮助用户实现协作传输，从而提高了整个小区的用户吞吐量。

图3给出了随着用户数目变化情况下公平因子的变化情况。公平性因子F定义为［9］

式中，rk表示用户k的平均吞吐量。从仿真结果中可以看出，随着用户数目的增加，所提出的LB-RS算法并没有明显地降低用户的公平性，而对于MSINR-RS以及SD-RS算法，用户之间的公平性却大大降低了。这是由于所提出的LB-RS算法综合考虑了用户当前的信道状况以及中继节点之间的负载情况，避免了某些用户一直得不到服务情况的发生。与之相反，MSINR-RS以及SD-RS算法则仅仅从用户当前的信道状况出发来选择中继节点，并未考虑到网络中的实际用户情况，从而降低了用户的公平性。

图4 给出了小区边缘用户吞吐量的变化情况。可以看出，当小区中的用户数目较小时，MSINR-RS的性能好于所提出的LB-RS，这是因为LB-RS的目标是在保证用户吞吐量最大的同时达到小区内的负载均衡。因此在用户数目较少时，为了保证小区内中继节点之间的负载均衡，LB-RS会选择一些信道状况次优的中继节点，牺牲一定的吞吐量来获得用户公平性的增加。但是随着小区中用户数目的增加，LB-RS的负载均衡的效果逐渐显现出来，这是由于LB-RS综合考虑了整个小区中的负载，从而有效地使得每个中继节点参与到协作传输的过程中来。反之，对于MSINR-RS以及SD-RS算法，由于每个中继节点的资源受限，当用户数目增加时，会造成中继节点之间负载分配不均衡，从而使得小区整体的性能下降。

图5 给出了中继节点服务的平均用户数的情况。随着用户数的增加，中继节点服务的平均用户数逐渐增加。对于LB-RS算法，由于考虑到了中继节点之间的负载均衡，用户能够均衡地接入到每个中继节点，从而使得每个中继节点所能服务的平均用户数逐渐趋于上限；MSINR-RS及SD-RS由于仅仅采用单一的中继选择标准，因此无法调整每个中继节点的用户接入情况，从而导致某些中继节点资源空闲，使得系统的资源利用率大大降低。

4 结论

本文首先提出了一种理想状况下基于负载均衡的集中式中继节点选择算法，分析了其应用的难点和存在的问题。在此基础之上，提出了一种基于负载均衡分布式的中继节点选择（LB-RS）算法。所提出的LB-RS综合地考虑每个用户的信道状况及其所选择中继节点的服务用户数，以分布式的方式为每个用户选择最优的中继节点。仿真结果表明，与已有基于单一的物理层参数的中继选择算法相比，所提出的中继选择算法综合考虑了物理层的信道状况以及MAC层的用户状况，从而有效地利用中继节点选择实现了小区内的负载均衡，提升了整个系统的资源利用率，获得了吞吐量性能与用户公平性之间的折衷。

［1］Ge Yue，Wen S，Ang Y-H，et al.Optimal relay selection in IEEE 802.16jmulti-hop relay vehicular networks［J］. IEEE Transactions on Vehicular Technology，2010，59（5）：2198-2206.

［2］Cai Jun，Shen Xuemin，Mark JW，et al.Semi-distributed user relaying algorithm for amplify-and-forward wireless relay networks［J］.IEEE Transactions onWireless Communications，2008，7（4）：1348-1358.

［3］Bletsas A Shin，Hyundong Win，Moe Z.Cooperative communicationswith outage-optimal opportunistic relaying［J］. IEEE Transactions on Wireless Communications，2007，6（9）：3450-3460.

［4］Sreng V，Yanikomeroglu H，Falconer DD.Relayer selection strategies in cellular networks with peer-to-peer relaying［C］／／Proceedings of Vehicular Technology Conference 2003.Orlando：IEEE，2003：1949-1953.

［5］Aimin Sang，Xiaodong Wang，Mohammad Madihian，et al. Coordinated load balancing，handoff／cell-site selection，and scheduling inmulti-cell packet data systems［J］.Wireless Networks，2008，14（1）：103-120.

［6］Giuseppe Bianchi，Ilenia Tinnirello.Channel-dependent load balancing in wireless packet networks［J］.Wireless Communications and Mobile Computing，2004，4（1）：43-53.

［7］Papadimitriou CH，Steiglitz K.Combinatorial Optimization：Algorithms and Complexity［M］.New York：Dover Publications，1998：103-155.

［8］Hahne E L.Round-robin scheduling formax-min fairness in data networks［J］.IEEE Journal on Selected Areas in Communications，1991（9）：1024-1039.

［9］Jain R，Chiu D，HaweW.A quantitivemeasure of fairness and discrimination for resource allocation in shared computer systems［R］.Hudson：Digital Equipment Corporation，1984.

JIANG Fan was born in Yancheng，Jiangsu Province，in 1982. She received the Ph.D.degree from Beijing University of Posts and Telecommunications in 2010.She is now a lecturer.Her research concerns next generation wireless network，cooperative relay network，cognitive radio networks.

Email：fjiangwbc＠gmail.com

王本超（1981—），男，山东淄博人，2007年于西安电子科技大学获工学硕士学位，现为华为技术有限公司工程师，主要研究方向为中继网络关键技术。

WANG Ben-chao was born in Zibo，Shandong Province，in 1981.He received theM.S.degree from Xidian University in 2007. He is now an engineer.His research concerns key technology of relay networks.

A Load Balancing Relay Selection Algorithm for Relay Based Cellular Networks

JIANG Fan1，WANGBen-chao2
（1.School of Communication and Information Engineering，Xi′an University of Posts and Telecommunications，Xi′an 710121，China；2.Huawei Technologies Co.，Ltd.，Shenzhen 518129，China）

A load balancing relay selection algorithm（LB-RS）is presented for relay based cellular networks. According to currentuser channel conditions aswell as the user numbers that relay serves，LB-RS chooses the optimal relay node for each user in a distributed way.Simulation results demonstrate that compared with other relay selection schemes only based on physical parameters，LB-RSachieves load balancing through effective relay selectionmethod.This is realized by jointly considering physical layer conditions aswell asMAC layer conditions，so as to efficiently obtain a tradeoff between the system throughput and the user equity.

relay based cellular network；relay selection；load balancing；cooperative relay

The Natural Science Foundation of Shaanxi Province（2011JQ8027）；The Natural Science Foundation of Education Department of Shaanxi Province（11JK1009）；The New Century Excellent Talents Supporting Project of Ministry of Education（NCET-08-0891）

TN925.8

A

10.3969／j.issn.1001-893x.2011.10.017

江帆（1982—），女，江苏盐城人，2010年于北京邮电大学获工学博士学位，现为西安邮电学院讲师，主要研究方向为下一代无线网络关键技术、协作中继网络、认知无线网络等；

1001-893X（2011）10-0080-06

2011-06-10；

2011-08-03

陕西省自然科学基金资助项目（2011JQ8027）；陕西省教育厅自然科学基金项目（11JK1009）；教育部新世纪优秀人才支持计划（NCET-08-0891）