劉盛銘， 劉力天

（1.裝備學(xué)院 研究生管理大隊，北京101416； 2.裝備學(xué)院 信息裝備系，北京101416）

IEEE802.16j標(biāo)準是移動多跳中繼（mobile multi－h(huán)op relay，MMR）的系統(tǒng)規(guī)范，通過在基站信號弱的地區(qū)布建成本相對低的中繼站（relay station，RS）作為網(wǎng)絡(luò)拓展，主要用于擴大網(wǎng)絡(luò)覆蓋范圍、提高系統(tǒng)吞吐量和容量等方面，其網(wǎng)絡(luò)亦被 稱 為MMR網(wǎng) 絡(luò)［1］。該 組 網(wǎng) 方 式 不 同 于IEEE802.16—2004定義的網(wǎng)狀網(wǎng)（mesh）方式（已被IEEE802.16—2009摒棄），它支持移動性且向后兼容點對多點方式（point to multi－point，PMP）。RS的引入使得傳統(tǒng)WiMAX基站（base station，BS）—用戶站（subscriber station，SS）的網(wǎng)絡(luò)結(jié)構(gòu)發(fā)生了變化，雖然中繼技術(shù)并不是新概念，但在網(wǎng)絡(luò)中如何布設(shè)BS和RS值得思考和研究。本文將IEEE802.16j網(wǎng)絡(luò)布站問題（BS and RS placement problem，BRPP）轉(zhuǎn)化為0－1型整數(shù)規(guī)劃（integer programming，IP）問題，建立了3跳結(jié)構(gòu)的網(wǎng)絡(luò)規(guī)劃模型，并對布站結(jié)果進行了比較和分析。

1 相關(guān)研究

IEEE802.16j網(wǎng)絡(luò)使用一級或多級RS通過無線方式在基站和用戶之間進行信號轉(zhuǎn)發(fā)，選擇站點布設(shè)位置是設(shè)計和規(guī)劃IEEE802.16j網(wǎng)絡(luò)的重要內(nèi)容。網(wǎng)絡(luò)規(guī)劃作為網(wǎng)絡(luò)建設(shè)的關(guān)鍵環(huán)節(jié)，不僅需要考慮成本因素，而且要確保網(wǎng)絡(luò)能夠提供最佳的覆蓋區(qū)域信號質(zhì)量和業(yè)務(wù)質(zhì)量。IEEE802.16j系統(tǒng)覆蓋范圍廣，BS和RS的站址選擇是否合理，在很大程度上影響著網(wǎng)絡(luò)的覆蓋效果。根據(jù)構(gòu)建模型的不同，對IEEE802.16j網(wǎng)絡(luò)站點布設(shè)的研究可以分為以下2類。

一類是單個BS小區(qū)如何選擇RS的位置。文獻［2］考慮了根據(jù)信號強度和輸出量選擇中繼的方法，結(jié)合2種時隙分配方案計算整個系統(tǒng)的輸出量，從而得到RS的最佳布設(shè)位置；文獻［3］使用透明和非透明2種模式的RS（T＿RS，NT＿RS）布建網(wǎng)絡(luò)，將布站問題轉(zhuǎn)化為0－1型IP問題，不僅證明了此類問題屬NP－Hard問題，還通過設(shè)計算法求解RS的數(shù)量和布設(shè)點位；文獻［4］使用NT＿RS，網(wǎng)絡(luò)的跳數(shù)不再限于2跳，選擇布站的同時還考慮了鏈路的容量，將RS的布設(shè)問題轉(zhuǎn)化為混合IP問題。

另一類是BS和RS具有多個候選位置時如何進行布站即BRPP。此類研究以文獻［5］922－925為典型。該論文將布站問題轉(zhuǎn)化為0－1型IP問題，其輸入是BS、RS的候選位置和代表用戶流量要求的測試點（test point，TP），網(wǎng)絡(luò)跳數(shù)不超過2跳，通過設(shè)置一系列約束條件得到網(wǎng)絡(luò)成本和SS全部發(fā)射功率最小時的BS和RS位置。該論文作者后續(xù)還通過使用分簇方法以及考慮系統(tǒng)容量的限制條件，進一步深化了對布站問題的研究［6－7］。文獻［8］在文獻［5］923－924的基礎(chǔ)上，提出了另一種網(wǎng)絡(luò)設(shè)計的優(yōu)化模型，跳數(shù)同樣是2跳，但網(wǎng)絡(luò) 中 增 加 了 信 號 測 試 點（signal test point，STP），并利用優(yōu)化軟件求解BS和RS的位置。

中繼跳數(shù)是指基站與用戶之間通信所需的最大鏈路級數(shù)［9］。對于IEEE802.16j多跳網(wǎng)絡(luò)，一般建議跳數(shù)不超過3［10］。對于SS通信傳輸是否需要借助RS，文獻［11］26－31認為，當(dāng)BS－SS鏈路適合16－QAM3／4等傳輸速率更高的調(diào)制方式時，SS無需使用RS。文獻［12］的仿真結(jié)果也表明，在16－QAM3／4等傳輸速率更高的小區(qū)地域內(nèi)，布設(shè)T＿RS不會提高系統(tǒng)的吞吐量。對BRPP的研究，很少有論文考慮SS是否需要中繼的條件和構(gòu)建3跳結(jié)構(gòu)的網(wǎng)絡(luò)，如圖1所示。本文在研究BRPP時，使用NT＿RS并結(jié)合文獻［11］31關(guān)于中繼使用的條件，建立了IEEE802.16j網(wǎng)絡(luò)3跳結(jié)構(gòu)的規(guī)劃模型，求解時利用軟件進行計算并確定BS和RS最終布設(shè)的點位。

圖1 3跳結(jié)構(gòu)的IEEE802.16j網(wǎng)絡(luò)BRPP描述

2 規(guī)劃模型

2.1 建立模型

在圖1所示的網(wǎng)絡(luò)中，對本文使用的符號定義如下：

1）集合。ABS＝｛1，2，…，b｝、ARS1＝｛1，2，…，r1｝、ARS2＝｛1，2，…，r2｝、ATP＝｛1，2，…，t｝分別表示BS的候選站址、第1層RS即RS1的候選站址、第2層RS即RS2的候選站址、代表用戶流量要求的測試點TP。

2）決策變量。當(dāng)BS、RS1和RS2布設(shè)在候選站址i處時，決策變量Bi、R1i和R2i的值為1，否則為0；當(dāng)?shù)趇個TP分配給第j個BS、RS1和RS2時，決策變量xij、yij和zij的值為1，否則為0；當(dāng)?shù)趇個RS1分配給第j個BS時，決策變量r1ij的值為1，否則為0；當(dāng)?shù)趇個RS2分配給第j個RS1時，決策變量r2ij的值為1，否則為0。這些決策變量都是0－1型變量。

建立目標(biāo)函數(shù)以使網(wǎng)絡(luò)的成本最小，網(wǎng)絡(luò)規(guī)劃的數(shù)學(xué)模型可表示為

約束條件如下：

式（1）表示網(wǎng)絡(luò)成本，以成本最小化即站點布設(shè)數(shù)量最少為優(yōu)化目標(biāo)；式（2）限制TP只分配給1個站點；式（3）～式（5）確保TP不會分配給1個不存在的站點；式（6）確保1個RS1只分配給1個BS；式（7）限制分配給BS的站點數(shù)量，因為RS1過多會導(dǎo)致系統(tǒng)信令開銷增大；式（8）確保1個RS2只分配給1個RS1；式（9）限制分配給RS1的RS2不超過2個；式（10）確保RS1不會分配給1個不存在的BS；式（11）確保RS2不會分配給1個不存在的RS1；式（12）限定分配給BS的TP的接收功率；式（13）限定分配給RS1的TP的接收功率；式（14）確保分配給RS1的TP在RS2通信范圍之外；式（15）限定分配給RS2的TP的接收功率；式（16）和式（17）對RS1在BS小區(qū)內(nèi)的接收功率進行限制；式（18）限制RS2在BS通信范圍之外；式（19）限制RS2在RS1通信范圍之內(nèi)。

2.2 設(shè)定參數(shù)

無線信道作為無線通信的媒介，是影響通信質(zhì)量的關(guān)鍵因素。對于任何一個無線網(wǎng)絡(luò)規(guī)劃問題，選擇信號傳播模型非常重要。本文使用IEEE802.16工作組推薦的經(jīng)過修改了的SUI模型［13］6－8。相關(guān)的系統(tǒng)參數(shù)如表1所示。

表1 系統(tǒng)參數(shù)

IEEE802.16—2009規(guī)定在基于10－6誤碼率條件下，RSS的計算方法［15］如下：

式中：RSN是不同調(diào)制編碼方案（modulation and coding scheme，MCS）所對應(yīng)的接收機信噪 比（signal－to－noise ratio，SNR）要求；R是指采用了R次重復(fù)編碼技術(shù)，這里取1；Fs是采樣頻率，單位是Hz；Nused是使用的子載波數(shù)量，取值840，對應(yīng)于10 MHz的帶寬；NFFT是快速傅里葉變換（fast Fourier transform，F(xiàn)FT）維數(shù)，取值1 024；ImpLoss是接收機余量，對抗由非理想接收機產(chǎn)生的各種誤差和產(chǎn)生的噪聲，參考IEEE802.16—2009，取ImpLoss＝5dB；NF是接收機噪聲，參考IEEE802.16—2009，取8dB。

又根據(jù)

式中：n為采樣因子；BW為系統(tǒng)帶寬；floor為向下取整運算，并依照IEEE802.16—2009中不同調(diào)制編碼方案所對應(yīng)的RSN，可計算相應(yīng)的RSS，如表2所示。

表2 接收機RSN對應(yīng)的RSS

其次，根據(jù)IEEE802.16j對RS之間傳輸信令所規(guī)定使用的調(diào)制方式［16］，RS1與RS2間傳輸鏈路SNR不能低于5.0dB，又因為RS2開設(shè)在BS覆蓋范圍之外，考慮SS使用中繼的條件，所以令PTP－BS＝PRS1－1＝－77.363 dBm，PTP－RS1＝PTP－RS2＝PRS1－2＝PRS2－1＝PRS2－2＝－86.363dBm，則小區(qū)內(nèi)無線傳輸鏈路適合16－QAM 3／4等高階調(diào)制方式的SS直接與BS通信，否則使用RS中繼信號，而且限制RS1布設(shè)在BS小區(qū)中的16QAM 3／4以外、QPSK 1／2以內(nèi)的區(qū)域內(nèi)。

最后，在10km×10km的規(guī)劃地域內(nèi)，令b＝20，r1＝r2＝60，t＝200，即BS、RS1、RS2站點可供布設(shè)的候選位置分別是20、60、60個，TP點的個數(shù)是200個。各點坐標(biāo)隨機產(chǎn)生，構(gòu)建的布站場景如圖2所示。

圖2 布站場景

3 結(jié)果分析

CPLEX Studio IDE是一個運用優(yōu)化技術(shù)補充支持重要資源的軟件平臺。本文不考慮具體的優(yōu)化算法，在CPLEX Studio IDE中建立規(guī)劃模型、輸入相關(guān)數(shù)據(jù)、執(zhí)行優(yōu)化計算、獲得數(shù)值結(jié)果。運行計算的CPU型號是Pentium（R）Dual－Core 2.5GHz，內(nèi)存是2GB，為了便于分析，時間都設(shè)置為500s。因為在具體運行時，由于計算的復(fù)雜性，CPU運行24h后依然沒有得出最優(yōu)的數(shù)值結(jié)果，但從500s后，數(shù)值結(jié)果不再發(fā)生大的波動。

對于3跳網(wǎng)絡(luò)的站點布設(shè)模型，在10km×10km地域內(nèi)，分別考慮只使用BS，使用BS和RS1，使用BS、RS1和RS2進行布設(shè)的情況，站點分布的結(jié)果如圖3所示。

圖3 網(wǎng)絡(luò)站點布建結(jié)果（線段表示通信鏈路）

從圖3可以看出，只使用BS布建WiMAX網(wǎng)絡(luò)，10km×10km的地域內(nèi)每個BS候選站點都布設(shè)上BS，還不能滿足全部TP的流量要求；使用BS和RS1布建的2跳網(wǎng)絡(luò)，所有TP流量要求都得到了滿足，但站點布設(shè)的情況并不理想；使用BS、RS1和RS2布建的3跳網(wǎng)絡(luò)，BS的數(shù)量比2跳網(wǎng)絡(luò)的顯著減少，BS和RS的站點布局趨于合理。表3比較了以上3種情況的布站結(jié)果。在該表中，3跳網(wǎng)絡(luò)的建設(shè)成本得到了合理控制和顯著降低，而且全部TP流量要求都得到了滿足。

表3 布站結(jié)果

4 總 結(jié)

本文對IEEE802.16j網(wǎng)絡(luò)的BRPP進行了研究，考慮SS使用RS的條件，提出了2層RS、3跳網(wǎng)絡(luò)的布站模型，將布站問題轉(zhuǎn)化為0－1型IP問題，并利用軟件進行優(yōu)化求解，其結(jié)果對實際的網(wǎng)絡(luò)建設(shè)具有一定的指導(dǎo)和借鑒意義。在今后的工作中，還可以進一步研究其他的布站方法，考慮小區(qū)之間的干擾、網(wǎng)絡(luò)成本預(yù)算限制、服務(wù)質(zhì)量保證等等因素。

（

）

［1］華強電子網(wǎng).基于WiMAX的多跳技術(shù)的應(yīng)用［EB／OL］.（2011－09－07）［2012－02－25］.http：／／www.hqew.com／tech／sheji／525759.html.

［2］WANG Lichun，SU Wenshan，HUANG Janehwa，et al.Optimal relay location in multi－h(huán)op cellular systems［C］／／XIAO Chengshan.2008 Wireless Communication and Networking Conference.Las Vegas，Nevada：IEEE，2008：1306－1310.

［3］LU H，LIAO W，LIN Y F.Relay station placement strategy in IEEE802.16j WiMAX networks［J］.IEEE Transactions on Communications，2011，59（1）：151－158.

［4］ABICHAR Z，KAMAL E A，CHANG M J.Planning of relay station locations in IEEE802.16（WiMAX）networks［C］／／SWEENEY A H.2010IEEE Wireless Communication ＆Networking Conference（WCNC 2010）.Sydney，Australia：IEEE，2010：1－6.

［5］YU Y，MURPHY S，MURPHY L.Planning base station and relay station locations in IEEE802.16j multi－h(huán)op relay networks［C］／／KAPLAN A.2008 Consumer Communications and Networking Conference.Las Vegas，Nevada：IEEE，2008：922－926.

［6］YU Y，MURPHY S，MURPHY L.A clustering approach to planning base station and relay station locations in IEEE802.16j multi－h(huán)op relay networks［C］／／ZHANG Lin.2008IEEE International Conference on Communications.Beijing：IEEE，2008：2586－2591.

［7］YU Y，MURPHY S，MURPHY L.Planning base station and relay station locations for IEEE802.16j network with capacity constraints［EB／OL］.（2010－01－09）［2012－02－25］.http：／／ieeexplore.ieee.org／xpl／freeabs＿all.jsp？tp＝arnumber＝5421766.

［8］PROMMAK C，WECHTAISON C.WiMAX network design for cost minimization and access data rate guarantee using multi－h(huán)op relay stations［J］.International Journal of Communications，2010，4（2）：39－46.

［9］郭欣，馬文超，郭子華，等.多跳中繼無線網(wǎng)絡(luò)資源復(fù)用的建模及算法設(shè)計［J］.軟件學(xué)報，2009，20（2）：425－436.

［10］WEI Zou.Capacity analysis for multi－h(huán)op WiMAX relay［EB／OL］.（2007－03－12）［2012－02－25］.http：／／express.lib.uts.edu.au／dspace／handle／2100／145.

［11］江鈺雯.WiMAX網(wǎng)路之中繼站布建演算法［D］.中國臺北：真理大學(xué)，2009：26－31.

［12］GENC V.Performance analysis of transparent mode IEEE802.16j relay－based WiMAX systems［D］.Dublin：University College Dublin，2010：92.

［13］SENARATH G，TONG Wen，ZHU Peiying，et al.Multihop relay system evaluation methodology（channel model and performance metric）［EB／OL］.（2006－09－05）［2012－02－25］.http：／／ieee802.org／16／relay／docs／80216j－06＿013r3.pdf.

［14］VELEZ J F，NAZIR K M，AGHVAMI H A，et al.Cost／revenue tradeoff in the optimization of fixed WiMAX deployment with relays［J］.IEEE Transactions on Vehicular Technology，2011，60（1）：298－312.

［15］IEEE.IEEE802.16—2009（Revision of IEEE802.16—2004）IEEE standard for local and metropolitan area networks－part 16：air interface for broadband wireless access systems［S］.New York：IEEE，2009：619，692.

［16］IEEE.IEEE802.16j—2009（Amendment of IEEE802.16—2009）IEEE standard for local and metropolitan area networks－part16：air interface for broadband wireless access systems－amendment 1：multihop relay specification［S］.New York：IEEE，2009：201.