劉盛銘， 劉力天

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

IEEE802.16j標(biāo)準(zhǔn)是移動(dòng)多跳中繼（mobile multi－h(huán)op relay，MMR）的系統(tǒng)規(guī)范，通過(guò)在基站信號(hào)弱的地區(qū)布建成本相對(duì)低的中繼站（relay station，RS）作為網(wǎng)絡(luò)拓展，主要用于擴(kuò)大網(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摒棄），它支持移動(dòng)性且向后兼容點(diǎn)對(duì)多點(diǎn)方式（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ò)布站問(wèn)題（BS and RS placement problem，BRPP）轉(zhuǎn)化為0－1型整數(shù)規(guī)劃（integer programming，IP）問(wèn)題，建立了3跳結(jié)構(gòu)的網(wǎng)絡(luò)規(guī)劃模型，并對(duì)布站結(jié)果進(jìn)行了比較和分析。

1 相關(guān)研究

IEEE802.16j網(wǎng)絡(luò)使用一級(jí)或多級(jí)RS通過(guò)無(wú)線方式在基站和用戶之間進(jìn)行信號(hào)轉(zhuǎn)發(fā)，選擇站點(diǎn)布設(shè)位置是設(shè)計(jì)和規(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ū)域信號(hào)質(zhì)量和業(yè)務(wù)質(zhì)量。IEEE802.16j系統(tǒng)覆蓋范圍廣，BS和RS的站址選擇是否合理，在很大程度上影響著網(wǎng)絡(luò)的覆蓋效果。根據(jù)構(gòu)建模型的不同，對(duì)IEEE802.16j網(wǎng)絡(luò)站點(diǎn)布設(shè)的研究可以分為以下2類。

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

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

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

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

2 規(guī)劃模型

2.1 建立模型

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

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

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

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

約束條件如下：

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

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

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

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

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

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

又根據(jù)

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

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

其次，根據(jù)IEEE802.16j對(duì)RS之間傳輸信令所規(guī)定使用的調(diào)制方式［16］，RS1與RS2間傳輸鏈路SNR不能低于5.0dB，又因?yàn)镽S2開(kāi)設(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)無(wú)線傳輸鏈路適合16－QAM 3／4等高階調(diào)制方式的SS直接與BS通信，否則使用RS中繼信號(hào)，而且限制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站點(diǎn)可供布設(shè)的候選位置分別是20、60、60個(gè)，TP點(diǎn)的個(gè)數(shù)是200個(gè)。各點(diǎn)坐標(biāo)隨機(jī)產(chǎn)生，構(gòu)建的布站場(chǎng)景如圖2所示。

圖2 布站場(chǎng)景

3 結(jié)果分析

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

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

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

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

表3 布站結(jié)果

4 總 結(jié)

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

（

）

［1］華強(qiáng)電子網(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ú)線網(wǎng)絡(luò)資源復(fù)用的建模及算法設(shè)計(jì)［J］.軟件學(xué)報(bào)，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］.中國(guó)臺(tái)北：真理大學(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.