中繼蜂窩網(wǎng)中基于負載均衡的中繼節(jié)點選擇算法?

江帆，王本超

中繼蜂窩網(wǎng)中基于負載均衡的中繼節(jié)點選擇算法?

江帆1，王本超2

（1.西安郵電學(xué)院通信與信息工程學(xué)院，西安710121；2.華為技術(shù)有限公司，廣東深圳518129）

提出了一種中繼蜂窩網(wǎng)絡(luò)的基于負載均衡的中繼節(jié)點選擇策略（Load Balancing Relay Selection，LB-RS）。根據(jù)每個用戶的具體信道狀況以及中繼節(jié)點服務(wù)的用戶數(shù)目，LB-RS以分布式的方式為每個用戶選擇最優(yōu)的中繼節(jié)點。仿真結(jié)果表明，與基于單一物理層參數(shù)的中繼節(jié)點選擇算法相比，所提出的中繼選擇算法綜合考慮了物理層的信道狀況以及MAC層的資源與用戶狀況，有效地利用中繼節(jié)點選擇來實現(xiàn)小區(qū)內(nèi)的負載均衡，獲得了吞吐量性能與用戶公平性之間的折衷。

中繼蜂窩網(wǎng)絡(luò)；中繼選擇；負載均衡；協(xié)作中繼

1 引言

在協(xié)作中繼網(wǎng)絡(luò)中，通過合理的中繼選擇策略［1-4］，多個參與協(xié)作的中繼以類似于虛擬MIMO的形式來實現(xiàn)空間分集，從而提高系統(tǒng)容量。目前廣泛研究的中繼選擇策略一般基于最短距離、最小路徑損耗、最大接收功率、最大信噪比等準則，用戶根據(jù)不同的節(jié)點選擇準則選擇一個或多個最優(yōu)的中繼節(jié)點實現(xiàn)協(xié)作傳輸。針對不同場景下的中繼節(jié)點選擇問題，許多研究者都提出了相應(yīng)的算法。Cai［2］探討了AF中繼轉(zhuǎn)發(fā)模式下的協(xié)作節(jié)點選擇與功率分配聯(lián)合優(yōu)化算法，研究了如何以半分布式的方式來選擇一個最優(yōu)中繼節(jié)點的問題。Bletsas［3］提出了基于無線信道的即時測量和互異性的分布式中繼選擇方法。Sreng［4］研究了中繼蜂窩系統(tǒng)中的中繼選擇策略，分析了基于最短距離、基于最小路徑損耗和基于最佳信道狀況3種中繼選擇策略的性能。

上述的中繼選擇策略一般都以不同的物理層參數(shù)（信噪比、功率、距離、路徑損耗等）為依據(jù)來選擇最優(yōu)的中繼節(jié)點，而事實上，中繼蜂窩小區(qū)中的每個移動臺的吞吐量不僅取決于當前物理層的信道狀況，還取決于當前小區(qū)中的基站和中繼節(jié)點所服務(wù)的用戶數(shù)以及MAC層的調(diào)度算法。如果當前中繼服務(wù)的用戶數(shù)過多，即使選擇了最優(yōu)的中繼節(jié)點，仍然不能保證獲得最大的用戶吞吐量，這是因為無法保證中繼節(jié)點有足夠的資源，使得用戶能夠通過中繼節(jié)點而獲得協(xié)作傳輸增益。

為了解決上述問題，本文首先提出了一種理想條件下基于負載均衡的集中式中繼節(jié)點選擇算法，并分析了其應(yīng)用中存在的問題。在此基礎(chǔ)上，提出了一種基于負載均衡分布式的中繼節(jié)點選擇算法（LB-RS）。LB-RS綜合考慮了每個用戶的信道狀況以及其所選擇中繼節(jié)點的服務(wù)用戶數(shù)目，以分布式的方式為每個用戶選擇最優(yōu)的中繼節(jié)點，從而在避免選擇熱點中繼節(jié)點的同時有效提高了用戶吞吐量，獲得吞吐量性能與用戶公平性之間的折衷。

2 算法描述

2.1 系統(tǒng)模型

假設(shè)系統(tǒng)中有N個小區(qū)，每個小區(qū)中布設(shè)6個位置固定的中繼節(jié)點（RN），如圖1所示。整個系統(tǒng)中均勻分布著K個移動臺（MS），對于任意一個移動臺k（k∈K），僅能選擇一個基站i（i∈N）作為其服務(wù)基站（BS）。小區(qū)內(nèi)部采用OFDMA物理層接入技術(shù)，每個MS根據(jù)當前信道狀況決定直接接入BS或者通過RN兩跳接入BS。為了減小用戶之間的干擾，每個MS使用1個正交的子信道接入。假設(shè)MS和RN可以完全獲得信道狀態(tài)信息。小區(qū)內(nèi)是全網(wǎng)時間同步的，將時間軸劃分為一系列的時間幀，若MS直接接入BS，則MT在每個時隙內(nèi)直接將數(shù)據(jù)發(fā)送到BS；若MS采用協(xié)作傳輸接入BS，則MS在第1個時隙向RN發(fā)送數(shù)據(jù)請求，RN在第2個時隙向BS轉(zhuǎn)發(fā)從MT收到的數(shù)據(jù)。RN以解碼轉(zhuǎn)發(fā)（DF）的方式工作。

2.2 基于負載均衡的集中式最優(yōu)中繼節(jié)點選擇算法

首先從經(jīng)濟學(xué)角度建立使得整個網(wǎng)絡(luò)效用最大的多小區(qū)效用模型［5］：

式中，R（t）表示系統(tǒng)中k個用戶效用之和，Uk（·）表示時刻t時用戶k平均吞吐量的非遞減效用函數(shù)，Tk（t）表示用戶k的平均吞吐量。因此，在中繼蜂窩小區(qū)中，當用戶選擇兩跳傳輸時，最優(yōu)的中繼節(jié)點選擇策略的目標應(yīng)該使得R（t）最大。定義分配指示變量：

用來標識t時刻移動臺k選擇位于小區(qū)i中的中繼節(jié)點m來實現(xiàn)兩跳協(xié)作傳輸，則分配指示矢量I（t）=｛Ii，m，k（t），i∈1，2，…，N，m∈1，2，…，6，k∈1，2，…，K｝代表了基站、中繼、用戶之間的一一對應(yīng)關(guān)系。另外，I（t）僅僅是整個解集中的一個解，因此式（1）變換為

約束條件為

其中，式（4）表示一個MS僅能選擇一個小區(qū)內(nèi)的一個RN，而式（5）和式（6）表示對于BS或者RN來說，每個時隙內(nèi)每個子信道只能分配給一個MS使用。

對小區(qū)中的用戶k來說，在時刻t定義其到小區(qū)中基站i、到小區(qū)中任意一個中繼節(jié)點m以及中繼節(jié)點m到基站i的3條鏈路的SINR可以表示為

式中，pk、pm分別表示MS和RN的發(fā)射功率，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）的分母分別表示來自于本小區(qū)及其它小區(qū)的MS到BS、MS到RN以及RN到BS的干擾以及接收端白噪聲之和。

根據(jù)香農(nóng)定理，若t時刻用戶k直接接入基站，則用戶k在帶寬B上可達數(shù)據(jù)速率上限為

如果用戶通過中繼m以協(xié)作傳輸?shù)姆绞絻商尤牖?，則用戶k在帶寬B上可達數(shù)據(jù)速率的上限為

假設(shè)信道是遍歷性的，則用戶k在t時隙末的平均吞吐量可表示為

從式（12）中可看出，Tk（t）的取值不僅取決于當前時隙的用戶k的可達數(shù)據(jù)速率，還取決于當前的分配指示矢量Ik，m，i（t），而Ik，m，i（t）的取值又受到用戶k所在小區(qū)的基站及中繼所服務(wù)的用戶數(shù)、具體的資源狀況和調(diào)度算法的影響。

理想狀況下，為了使MS的吞吐量最大，BS需要根據(jù)MS的信道狀況、RN的服務(wù)用戶數(shù)、資源狀況選擇最優(yōu)的中繼節(jié)點。假設(shè)每個時隙Δt足夠小，對于構(gòu)造的非遞減效用函數(shù)，在逐個時隙上取最陡的梯度值，則到每個MS在每個時隙上Δt最優(yōu)的中繼節(jié)點選擇集合I*（t）為

其中Tk（t）可以根據(jù)下式［6］

來計算，并且Ik，m，i（t）的取值受限于式（4）和式（6）。式（13）所給出的最優(yōu)中繼節(jié)點選擇集合I*（t）表示了使得每個MS吞吐量最大的基站、中繼、用戶之間的一一對應(yīng)關(guān)系。由于BS需要綜合考慮當前小區(qū)中MS的信道狀況、BS和RN的服務(wù)用戶數(shù)、資源的分配情況來在每個時隙動態(tài)為每個MS選擇最優(yōu)的中繼節(jié)點Ik，m，i，因此，求解出的中繼節(jié)點選擇集合對每個MS都是最有效的。從而式（13）表示了理想狀況下，具有負載均衡特性的集中式最優(yōu)中繼選擇算法。如果以BS為中心，利用匈牙利算法［7］，通過窮盡搜索來選擇最優(yōu)中繼節(jié)點，可獲得最差情況下算法的復(fù)雜度為O（K6N）。

但是，在實際系統(tǒng)中，如果采用上述集中式的方式選擇最優(yōu)的中繼節(jié)點，每個BS需要在每個時隙實時地獲得當前MS在系統(tǒng)中所有小區(qū)內(nèi)的每個子信道上瞬時速率以及t-1時刻的MS的吞吐量，然后以集中式的方式來計算。運算的復(fù)雜度以及所需的實時信息量，都使得該最優(yōu)中繼選擇集合在實際的多小區(qū)系統(tǒng)中難以獲得。

2.3 LB-RS算法

為了解決上述集中式算法在實際中的應(yīng)用問題，提出如下的基于負載均衡的分布式中繼節(jié)點選擇策略。

（1）每個MS根據(jù)當前信道狀況確定采用直接傳輸或者通過中繼實現(xiàn)兩跳協(xié)作傳輸。如果直接傳輸能獲得更大的增益，則用戶k直接將數(shù)據(jù)發(fā)送給BS；否則用戶k采用兩跳協(xié)作傳輸。

（2）如果MS采用兩跳協(xié)作傳輸，首先在本小區(qū)內(nèi)計算每個中繼節(jié)點信號的接收信噪比（SINR），并偵聽每個中繼節(jié)點當前所服務(wù)的用戶數(shù)；然后，在周圍小區(qū)中選擇一個接收到信噪比最大的中繼節(jié)點，并偵聽其所服務(wù)的用戶數(shù)。

（3）MS根據(jù)式（11）計算選擇不同中繼節(jié)點的兩跳傳輸可達速率建立中繼節(jié)點選擇函數(shù)

選擇使式（15）最大的中繼節(jié)點。

（4）根據(jù)具體的調(diào)度策略，在MS所分配的子載波上進行兩跳傳輸。

之間的信道狀況以及中繼節(jié)點的服務(wù)用戶數(shù)目，選擇能夠兼顧用戶負載均衡以及吞吐量的中繼節(jié)點，避免由于選擇某些熱點中繼節(jié)點而造成無法協(xié)作傳輸?shù)那闆r，從而提高系統(tǒng)資源利用率，得到性能與用戶公平性之間的折衷。

3 仿真結(jié)果及性能分析

3.1 仿真參數(shù)設(shè)定

考慮一個工作在3.5 GHz頻段的OFDMA蜂窩系統(tǒng)，包含有27個蜂窩小區(qū)，每個小區(qū)中均勻布設(shè)6個RN，小區(qū)半徑為1 km，中繼節(jié)點位于小區(qū)半徑2／3處。

仿真參數(shù)選用3GPP LTE目前所規(guī)定的OFDMA系統(tǒng)的參數(shù)：時隙長度1ms，每時隙OFDM符號數(shù)14個；每個調(diào)度時隙包含24個子信道，每個子信道包含12個子載波數(shù)，每個子載波帶寬15 kHz。假定收發(fā)信機之間保持時間同步。每個MS的發(fā)射功率PMT=50mW，RN的發(fā)射功率PRN=1W，接收機熱噪聲σ2=10-10W。

3.2 仿真結(jié)果

為了進行對比，我們在仿真實驗中分別考慮了4種中繼選擇策略下的用戶吞吐量以及公平性性能：一是直接傳輸（Without Relay，W／O Relay）；二是基于最小距離的中繼選擇策略（Shortest Distance Based Relay Selection，SD-RS）；三是基于最大SINR的中繼選擇策略（Maximum SINR Based Relay Selec

tion，MSINR-RS）；四是本算法提出的中繼選擇策略（LB-RS）。假設(shè)在每個資源分配時隙，每個中繼節(jié)點最多能夠同時服務(wù)8個MS。所采用資源調(diào)度的準則是照輪詢調(diào)度（Round Robin，RR）［8］。

圖2給出了隨著小區(qū)中用戶數(shù)目增加，小區(qū)用戶吞吐量的變化情況。從仿真結(jié)果中可以觀察到，當小區(qū)中用戶數(shù)目較少時（用戶數(shù)小于20時），SDRS、B-RS及MSINR-RS的性能都好于直接傳輸?shù)男阅?，且三者性能差別不大。但是，隨著用戶數(shù)目的增加，由于每個中繼覆蓋范圍內(nèi)的用戶數(shù)增加，更多的用戶會選擇協(xié)作傳輸機制，從而導(dǎo)致某些中繼節(jié)點需要服務(wù)的用戶數(shù)激增。然而，無論采用SD

RS，還是采用MSINR-RS，都無法避免用戶擁塞的發(fā)生。而根據(jù)所提出的LB-RS中繼選擇算法，每個用戶都會根據(jù)當前時隙其自身的信道狀況，結(jié)合中繼節(jié)點的用戶服務(wù)數(shù)目，以分布式的方式來綜合選擇最優(yōu)的中繼節(jié)點，使得某些負載較輕的中繼節(jié)點能夠幫助用戶實現(xiàn)協(xié)作傳輸，從而提高了整個小區(qū)的用戶吞吐量。

圖3給出了隨著用戶數(shù)目變化情況下公平因子的變化情況。公平性因子F定義為［9］

式中，rk表示用戶k的平均吞吐量。從仿真結(jié)果中可以看出，隨著用戶數(shù)目的增加，所提出的LB-RS算法并沒有明顯地降低用戶的公平性，而對于MSINR-RS以及SD-RS算法，用戶之間的公平性卻大大降低了。這是由于所提出的LB-RS算法綜合考慮了用戶當前的信道狀況以及中繼節(jié)點之間的負載情況，避免了某些用戶一直得不到服務(wù)情況的發(fā)生。與之相反，MSINR-RS以及SD-RS算法則僅僅從用戶當前的信道狀況出發(fā)來選擇中繼節(jié)點，并未考慮到網(wǎng)絡(luò)中的實際用戶情況，從而降低了用戶的公平性。

圖4 給出了小區(qū)邊緣用戶吞吐量的變化情況?？梢钥闯觯斝^(qū)中的用戶數(shù)目較小時，MSINR-RS的性能好于所提出的LB-RS，這是因為LB-RS的目標是在保證用戶吞吐量最大的同時達到小區(qū)內(nèi)的負載均衡。因此在用戶數(shù)目較少時，為了保證小區(qū)內(nèi)中繼節(jié)點之間的負載均衡，LB-RS會選擇一些信道狀況次優(yōu)的中繼節(jié)點，犧牲一定的吞吐量來獲得用戶公平性的增加。但是隨著小區(qū)中用戶數(shù)目的增加，LB-RS的負載均衡的效果逐漸顯現(xiàn)出來，這是由于LB-RS綜合考慮了整個小區(qū)中的負載，從而有效地使得每個中繼節(jié)點參與到協(xié)作傳輸?shù)倪^程中來。反之，對于MSINR-RS以及SD-RS算法，由于每個中繼節(jié)點的資源受限，當用戶數(shù)目增加時，會造成中繼節(jié)點之間負載分配不均衡，從而使得小區(qū)整體的性能下降。

圖5 給出了中繼節(jié)點服務(wù)的平均用戶數(shù)的情況。隨著用戶數(shù)的增加，中繼節(jié)點服務(wù)的平均用戶數(shù)逐漸增加。對于LB-RS算法，由于考慮到了中繼節(jié)點之間的負載均衡，用戶能夠均衡地接入到每個中繼節(jié)點，從而使得每個中繼節(jié)點所能服務(wù)的平均用戶數(shù)逐漸趨于上限；MSINR-RS及SD-RS由于僅僅采用單一的中繼選擇標準，因此無法調(diào)整每個中繼節(jié)點的用戶接入情況，從而導(dǎo)致某些中繼節(jié)點資源空閑，使得系統(tǒng)的資源利用率大大降低。

4 結(jié)論

本文首先提出了一種理想狀況下基于負載均衡的集中式中繼節(jié)點選擇算法，分析了其應(yīng)用的難點和存在的問題。在此基礎(chǔ)之上，提出了一種基于負載均衡分布式的中繼節(jié)點選擇（LB-RS）算法。所提出的LB-RS綜合地考慮每個用戶的信道狀況及其所選擇中繼節(jié)點的服務(wù)用戶數(shù)，以分布式的方式為每個用戶選擇最優(yōu)的中繼節(jié)點。仿真結(jié)果表明，與已有基于單一的物理層參數(shù)的中繼選擇算法相比，所提出的中繼選擇算法綜合考慮了物理層的信道狀況以及MAC層的用戶狀況，從而有效地利用中繼節(jié)點選擇實現(xiàn)了小區(qū)內(nèi)的負載均衡，提升了整個系統(tǒng)的資源利用率，獲得了吞吐量性能與用戶公平性之間的折衷。

［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，F(xiàn)alconer 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年于西安電子科技大學(xué)獲工學(xué)碩士學(xué)位，現(xiàn)為華為技術(shù)有限公司工程師，主要研究方向為中繼網(wǎng)絡(luò)關(guān)鍵技術(shù)。

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年于北京郵電大學(xué)獲工學(xué)博士學(xué)位，現(xiàn)為西安郵電學(xué)院講師，主要研究方向為下一代無線網(wǎng)絡(luò)關(guān)鍵技術(shù)、協(xié)作中繼網(wǎng)絡(luò)、認知無線網(wǎng)絡(luò)等；

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

2011-06-10；

2011-08-03

陜西省自然科學(xué)基金資助項目（2011JQ8027）；陜西省教育廳自然科學(xué)基金項目（11JK1009）；教育部新世紀優(yōu)秀人才支持計劃（NCET-08-0891）