在三跳的IEEE802.16j網絡中布設基站和中繼站

劉盛銘， 劉力天

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

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

1 相關研究

IEEE802.16j網絡使用一級或多級RS通過無線方式在基站和用戶之間進行信號轉發，選擇站點布設位置是設計和規劃IEEE802.16j網絡的重要內容。網絡規劃作為網絡建設的關鍵環節，不僅需要考慮成本因素，而且要確保網絡能夠提供最佳的覆蓋區域信號質量和業務質量。IEEE802.16j系統覆蓋范圍廣，BS和RS的站址選擇是否合理，在很大程度上影響著網絡的覆蓋效果。根據構建模型的不同，對IEEE802.16j網絡站點布設的研究可以分為以下2類。

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

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

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

圖1 3跳結構的IEEE802.16j網絡BRPP描述

2 規劃模型

2.1 建立模型

在圖1所示的網絡中，對本文使用的符號定義如下：

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）決策變量。當BS、RS1和RS2布設在候選站址i處時，決策變量Bi、R1i和R2i的值為1，否則為0；當第i個TP分配給第j個BS、RS1和RS2時，決策變量xij、yij和zij的值為1，否則為0；當第i個RS1分配給第j個BS時，決策變量r1ij的值為1，否則為0；當第i個RS2分配給第j個RS1時，決策變量r2ij的值為1，否則為0。這些決策變量都是0－1型變量。

建立目標函數以使網絡的成本最小，網絡規劃的數學模型可表示為

約束條件如下：

式（1）表示網絡成本，以成本最小化即站點布設數量最少為優化目標；式（2）限制TP只分配給1個站點；式（3）～式（5）確保TP不會分配給1個不存在的站點；式（6）確保1個RS1只分配給1個BS；式（7）限制分配給BS的站點數量，因為RS1過多會導致系統信令開銷增大；式（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小區內的接收功率進行限制；式（18）限制RS2在BS通信范圍之外；式（19）限制RS2在RS1通信范圍之內。

2.2 設定參數

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

表1 系統參數

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

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

又根據

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

表2 接收機RSN對應的RSS

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

最后，在10km×10km的規劃地域內，令b＝20，r1＝r2＝60，t＝200，即BS、RS1、RS2站點可供布設的候選位置分別是20、60、60個，TP點的個數是200個。各點坐標隨機產生，構建的布站場景如圖2所示。

圖2 布站場景

3 結果分析

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

對于3跳網絡的站點布設模型，在10km×10km地域內，分別考慮只使用BS，使用BS和RS1，使用BS、RS1和RS2進行布設的情況，站點分布的結果如圖3所示。

圖3 網絡站點布建結果（線段表示通信鏈路）

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

表3 布站結果

4 總 結

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

（

）

［1］華強電子網.基于WiMAX的多跳技術的應用［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－hop 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－hop 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－hop 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－hop relay stations［J］.International Journal of Communications，2010，4（2）：39－46.

［9］郭欣，馬文超，郭子華，等.多跳中繼無線網絡資源復用的建模及算法設計［J］.軟件學報，2009，20（2）：425－436.

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

［11］江鈺雯.WiMAX網路之中繼站布建演算法［D］.中國臺北：真理大學，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.