中繼蜂窩網中基于負載均衡的中繼節點選擇算法?

江帆，王本超

中繼蜂窩網中基于負載均衡的中繼節點選擇算法?

江帆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）