在三跳的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.