分层优化网络资源规划方法

1 分层优化网络资源规划方法分层优化网络资源规划方法 介绍介绍 随着对移动通信业务需求的巨大增长 系统设计优化和无线网络规划的问题变 得越来越重要 虽然在移动蜂窝网络规划领域作了很多关于覆盖分析 信道分配 路由选择和传播等方面的研究 但在关于成本有效系统设计的网络规划方面的研究 却不多 1 5 实际上 在复杂的移动通信设计中必须考虑很多因数 如系统性能 系统容量 小区覆盖 话务量 地形和传播特征等 关于小区数量 小区位置 基 站和移动单元的设计参数及信道分配的决定必须根据相互之间的关系作出 小区的 位置可以根据给定的小区数量 覆盖性能 话务分布和传播环境来确定 基站和移 动单元的设计参数必须要等到小区的部署全部完成后才能具体化 最后 在话务和 避免干扰等方面能改善系统性能的信道分配 6 8 只有在移动蜂窝网络的结构被详 细说明后才能决定 在决定任何通信系统经济上的可行性时成本都是一个关键因素 一个好的设计 方法应该能在诸如网络性能标准 话务量和技术升级等因素中进行权衡 使成本最 优化 9 至今已有几个商用软件包被成功应用于移动蜂窝系统的网络规划中 如 plaNET 软件 但不管怎样 它们在规划中都没有直接包括金融上的规划或者考虑 成本 另一方面 如 Analysis STEM 建模系统等的一些软件是决策支持工具以获得 金融模型并提供蜂窝移动系统的成本分析 但在它们的成本模型中又没有考虑网络 规划 这篇论文试图同时考虑成本和网络规划因数以填补这个缺口 这种唯一的组 合对移动网络业务的供应商有极大的意义 它发展了最优化的网络规划方法 在系 统设计上既使总的系统成本最小化同时又保证了好的系统性能 可操作的研究策略 分层优化的规划早已被成功应用于大规模制造系统的生产 规划和健康关心及服务系统的决策制定中 10 12 在这些事例中 集合规划通常 是不可行的 因为对于大型的复杂系统的集合规划模型通常不能被公式化或无法求 解 在本论文中 我们描述了关于移动蜂窝通信系统设计的网络规划的分层特性 提出了一个分层优化规划方法 HOP 以确定无线网络的结构 即小区的数量 小区 的大小 小区的安置 天线增益及天线高度的参数和基站及移动单元的发射功率 一个组合优化模型被推导出来以确定小区的最佳数量和基站的最佳位置使得在总的 系统成本最小化的同时又能保证良好的覆盖质量和话务性能 规划模型是一个有难度的组合优化问题 13 诸如分支界限法和动态规划法之 类的优化算法不能在合理的时间内求得优化解 13 因为牵涉到很多变量和复杂的 约束 被用来解决大型组合优化问题的分解法和拉格朗日松驰法 14 可能也无法应 用到规划模型中 在本论文中 一个建立在模拟退火 SA 基础上的算法被推导出来 用于解决此问题 并在合理的计算量内求得了逼近的最优结果 本论文的安排如下 在第二节 我们描述了蜂窝无线网络规划问题 第三节提 出了解决这个问题的分层优化规划方法 在这一节还提出了组合优化模型和模拟退 火算法 最后 在第四节给出了用 HOP 方法实现新加坡的蜂窝移动通信服务系统 的网络规划的模拟结果 2 问题陈诉问题陈诉 如图 1 所示 假如我们想要发展一个蜂窝移动通信系统为新加坡地区提供服务 整个地区将覆盖三种类型的土地 市区 郊区和农村 我们需要考虑非一致的话务 分布 话务高峰通常在市中心 局部话务高峰在郊区中心 给定与覆盖性能相关的 地区覆盖概率 边界处的定位概率和覆盖边界处接收信号强度的门限电平 a P L P 可以从覆盖概率和要求的信号强度 即载干比 C N 2 中推导得出 服务等 cell P a P 级被设定为在忙时发起呼叫的阻塞概率 为满足业务要求在系统中采用了频 block P 率复用方案 问题是怎样设计一个最优网络结构 即确定小区的数量 小区的大小 每个基 站的位置和基站及移动单元的参数 以保证达到要求的性能目标 并使总的系统成 本最小化 基站设备的成本是由机器设备及安装 天线 建筑物及铁塔和发射机及 收信机等的成本决定的 为了设计这样一个系统 必须考虑许多因素 1 9 需要作出许多不同层次的 决策 涉及的主要因素如下 系统性能的详述 小区的覆盖 话务分布 地形 传 播数据和系统成本因素 所有的这些因素相互影响 它们之间的复杂关系需要确定 由于系统的复杂性 在实际中网络规划过程是分层次的 规划活动包括 性能的说 明和分析 从小区的数量及小区的位置方面来说的形式上的小区规划 和关于射频 小区参数的设置及信道分配的详细小区设计 网络规划和设计方法网络规划和设计方法 我们提出了蜂窝移动通信网络设计的三层HOP 方法 网络规划的三层结构如 图 2 所示 在第一层 决定了小区数量的上界和相应的小区覆盖范围 HOP 的输入参数如 下 忙时的话务负荷 覆盖要求和整个服务区域的地形特征 并选择典型情况下的 传播参数 任务为用最小的小区数量覆盖整个区域并满足平均话务需求 在第二层 小区的数量和最佳的小区位置由大型的组合优化模型决定 模型的 规划目标是使总的系统成本最小化 同时确保覆盖的质量 并努力符合非一致话务 负载的要求 我们考虑到了不同用户的话务密度和不同类型服务区域的地形特征 如图 1 所示 整个区域被划分为市区 郊区和农村 这些区域进一步被划分为更 小的网格 环境结构方面的信息 用户密度和每个网格的平均俯角等都可以从地理 信息系统 GIS 的数据库里得到 详细规划在第三层进行 每个小区的具体参数 如天线模型及其增益 发射功 率 天线高度和信道利用率等都在这一层设置 最后 把成本估计出来 3 规划过程的总体系统性能很大程度上取决于不同层次上的不同活动和决策相结 合的程度 如图 2 所示 决策必须在双向上相互调整和加强 为了获得这个 HOP 方法和最优成本模型 需要考虑几个复杂的关系 覆盖率 的要求 小区的覆盖范围和小区边界信号强度之间的关系 2 传播损失和具体的 人造建筑物及地形外表之间的关系 17 设备和成本之间的关系 传播损失可以用 Hata 传播模型预测 18 Hata 模型刻划了对于市区 郊区和农 村等地形是准光滑或不规则的不同环境下无线传播的特性 在蜂窝系统的设计中这 个模型广泛应用于预测不同环境下的路径损失 17 19 关于市区内基本传输损耗的 Hata 公式由下式给出 Lu db 69 55 26 26 log f 13 82 log a b h m h 44 9 6 55 log log d 1 b h 其中移动台天线高度的校正因子 a 为 对于中小城市 a 1 1 log f m h m h 0 7 1 56 log f 0 8 对于大城市 a 3 2 log 11 75 m h m h m h 2 4 97 且频率 f 400MHz 郊区和农村的传播损失 Lsu 和 Lrqo 由下式给出 Lsu Lu 2 log f 28 5 4 2 2 Lrqo Lu 4 78 log f 18 33 log f 35 94 3 2 Hata 公式适用的范围为频率 f 在 150 MHz 到 1000 MHz 之间 基站天线高度 介于 30m 和 100m 之间 移动台天线高度介于 1m 和 10m 之间 距离 d 的变化 b h m h 范围为从 1km 到 20km 在以下各节中 将给出 HOP 方法每一层的细节 A 第一层 小区数量和小区大小的最初决定 首先 根据整个地区的覆盖性能和平均话务需求决定需要的最小基站数 为了 确定系统设计中需要的小区数的上界 这个最小的基站数是在最差的情况下计算的 的 在此我们取小区复用因子 k 7 并给定地区覆盖概率和用户阻塞率 a P block P 把覆盖区域对移动话务量的要求考虑为在忙时由在此区域内的移动单元发起的 所有呼叫尝试 它是根据覆盖区域内车辆的交通流量来预测的 给定预估的呼叫尝 试率 该区域的话务负载就转化为忙时在此区域内的移动用户数 我们定义以下符号 根据每个小区的信道数和给定的阻塞率得到的每个小区可以提 pt C block P 4 供的话务量 用户数 小时 整个服务区的总话务量 用户数 小时 tt C 覆盖边界处的接收信号强度的门限电平 cell P 射频输出的峰值功率 dbW pp P 发射天线的输入功率 dbW t P 接收天线的接收功率 dbW r P 分别为基站和移动单元的天线增益 db b g m g 分别为基站和移动单元的天线高度 b h m h d 小区的平均辐射半径 km S 服务区的总面积 km 2 首先考虑覆盖性能 从发射机到接收机射频功率的链接预算资源由下列方程给 出 1 9 L d 4 r P t P b g m g l 5 t P pp P 其中 L d 是传输损耗 db 而 l 是绝缘体 组合器和射频电缆的复合损耗 整个地区小区数量的上界由关于市区的 Hata 传播模型决定 关于郊区和农村的 模型将在规划的下一层考虑 假设有下列条件 1 9 pp P 10W 30m 3m 12dBi 2dBi l 4dB f 900MHz 则关于传 b h m h b g m g 播损失 L 的公式 1 变为 L d 123 73 35 22 log d 6 为保证满足覆盖要求 我们有 73 73 35 22 log d 7 r P cell P 即 log d log d 73 73 35 22 8 maxcell P 其中 d是在大城市市区环境下最大的小区辐射半径 max 那么 小区的最小数量为 5 9 2 max 1 d S n 如果由业务量的分布情况来确定覆盖区图形 小区数量就由话务量决定 1 在这 种情况下 小区的最小数量为 10 pt tt C C n 2 由此可以给出小区的最小数量为 n max 11 1 n 2 n 在最初的系统设计中 我们设 n 为小区数量的上界以得到成本有效的设计 在给定 小区数量后 平均小区辐射半径由 d 决定 n S B 第二层 最优小区位置和小区数量及小区大小的确定 在这一层 考虑了整个区域的非一致话务分布 有关地形结构和环境的数据 话务密度 俯角均存储在每个网格中 一旦已知小区数量的上界 下一步就是要确 定那一个网格属于那一个小区 进而就确定了小区的数量 不同的小区位置和小区 大小 一般地 小区由相邻的具有相同分类的几个网格组成 在本论文中 建立了 一个组合优化模型来确定那个网格属于那个小区和基站参数的最优值 我们考虑关 于覆盖标准的 硬 约束和非一致话务需求的 软 约束 软 约束可被放松且 可通过补偿项合并入目标函数 模型的目标是使整个系统成本最小化 在轻话务量 条件下 小区的数量可进一步减少 1 经济优化模型的数学阐述 为了阐明这个问题 我们引入以下决策变量 1 若网格 i 属于小区 k 1 若小区 k 被网格占据 ik x k Y 0 若网格 i 不属于小区 k 0 若小区 k 内没有网格 节约一个小区 进一步 我们定义如下 1 网格 i 内的市区结构 2 网格 i 内的郊区结构 1 i G 3 网格 i 内的农村结构 网格 i 内的话务密度 用户数 小时 2i G n 总的小区数 m 总的网格数 交换机房 硬件和安装的固定成本 so C 基站内的硬件和安装的成本 cell C 考虑其增益的天线的成本系数 a C 6 考虑其发射功率的发射机和接收机的成本系数 t C 小区 k 内的基站发射功率 且 其中和 tk P UBtkLB PPP LB P 分别是其相应的上界和下界 UB P 分别为小区 k 内的基站和移动单元的天线增益 且 mkbk gg 其中和分别是其相应的上界和下界 UBtkLB ggg LB g UB g 分别为小区 k 内的基站和移动单元的天线高度 mkbk hh 小区 k 的辐射半径 k d 网格的范围 g S 关于蜂窝移动通信网络的经济优化模型 EOM 阐述如下 EOM min 12 sfc so C k k Y cell C a C bk g t C tk P 受约束于 k 1 2 n 13 tk P bk g mk g cellkk PdL k 1 2 n 14 i ptiik CGx 2 k 1 2 n i 1 2 m i 15 0 1 1 i i ki ik GGxx i i i 1 2 m 16 i ik x1 k 1 2 n 17 i gikk Sxd 2 1 0 k 1 2 n 18 k d k Y 1 k 1 2 n 19 k d k Y 对所有 i 和 k 的值为 1 或 0 20 ik x k Y 在 EOM 模型中 目标函数 12 的目的是最小化总的系统成本 约束 13 用 sfc 来确保覆盖性能 约束 14 保证设计满足非一致话务量的要求 约束 15 17 确保 7 小区由具有相同结构且彼此相邻的网格组成 约束 18 20 给出了和之间的 k d k Y 关系 即当 0 时 0 当0 时 1 k d k Y k d k Y 信号传播损耗通过 Hata 预测模型进行计算 根据以下条件 1 9 kk dL 10W 30m 3m 12dBi 2dBi l 4dB f 900MHz 我 pp P b h m h b g m g 们有 35 22 log 21 kk dL k d 其中当小区 k 分别覆盖市区 郊区和农村区域时 123 73 113 79 和 102 22 2 用模拟退火算法求解EOM模型 EOM 模型是个有难度的组合优化问题 因 为在模型中有很多变量和复杂的约束 13 没有一种优化算法能在合理的时间里求 得最优解 在文献 15 和 16 中报导的建立在模拟退火 SA 基础上的算法被用来解 决这个问题 并在合理的时间内求得了逼近最优解 对于求解 NP 完全组合问题的逼近解来说模拟退火是种好方法 13 它已被成功 应用于某些领域 如计算机的优化设计 16 图象处理 信道分配 8 20 和规划布 局问题 算法采用一种迭代方案 它模拟物理退火过程 加热固体直到其融化 然 后花最少的能量冷却它使其结晶至基态 为了用模拟退火过程解决 EOM 问题 需要考虑下面四个方面 配置空间 成 本函数 相邻结构和冷却进度表 a 配置空间 对于 EOM 模型 配置空间 S 是所有满足覆盖约束 13 和其它约束 15 20 可行解 的集 kik Yx b 成本函数 在实际的系统设计中 首先要考虑覆盖性能 对于给定的小区数 量 由于非一致话务分布的存在 如果要满足覆盖和话务两者的要求 没有几个可 行解可被求得 因而引入话务约束 14 到目标函数 目标函数就从 12 变为最小化 基站的总设备成本和破坏话务负载后引起的总补偿 即 22 k kc Ysf i ptiiktraftktbkacell CGxCPCgCC 2 其中函数 x max 0 x 因为 12 中的系统固定成本不影响 EOM 模型的最优解 故在成本函数中不 so C 再包含这一项 c 相邻结构 用 N s 表示的解 s 的邻域由在满足约束 15 17 时 移动网格 k 从当前小区 i 到相邻小区 j 时产生 d 冷却进度表 决定初始温度t 以确保可接受转换与提议转换之比的特定接受 0 8 率 接近 1 15 这可以通过从一个小的正数 t 出发 迭代地变换它直到达到接 0 受率 来得到 Huang 21 用在某一温度的成本分布的标准偏差来决定下个温度的减小量 并提 出下面的温度递减规则 23 exp exp 2 1kkkkkkk ttcttt 其中是在温度 t 的成本分布的标准偏差 是发生在两个连续温度 t 和 t之 k k c k1 k 间的平均成本的减少量 为保持准平衡 当 的典型值 0 7 cc 1 在某个温度平衡意味着齐次马尔可夫链的固定成本分布的建立 Huang 假设了 一个关于平衡的成本的正态分布 它们的平均值和标准偏差都由马尔可夫链c 估计而来 他们提出了完成固定分布检查的平衡条件 一旦平衡建立 其成本限制 在范围内可接受的转换次数的比率将达到一个稳定值 erf 其中介 于平均成本 它被称为次数内 和可接受转换总次数之间 erf x 是 x 的误差函数c 22 的典型值为 0 5 从而可得 erf 0 38 两个平衡参数 一个目 标次数内和一个最大容许偏差极限 都根据问题的大小建立 如果次数内在容许偏 差次数超过最大极限值以前达到了目标值 我们就认为保持了平衡 21 对于我们的 EOM 问题 我们设置次数内 0 38 3 m n 和最大容许偏差 0 62 3 m n 我们说取得了最后温度 如果在那个温度的马而可夫链的整个轨迹里 最大和 最小成本的差值等于在那个温度的一次可接受转换里的成本的最大一次变化 下列伪代码程序描述了解决 EOM 问题的模拟退火过程 SAEOM 解决EOM问题的模拟退火过程 SAEOM Begin 初始化 tosstart k 0 s start s Repeat Until 平衡达到 do Begin 从 N s 产生 s If then s sfsf cc s 9 Else If exp f s f t random 0 1 then s s k s End k k 1 计算 t k Until 停止准则成立 End 与 Kirpatrick 16 提出的模拟退火技巧相比 这个用 Huang 方法 21 的新 SA 技 巧能通过退火过程动态调节马尔可夫链的长度达到平衡 退火需要的 CPU 时间也 大大地下降了 C 详细规划和准确的成本估计 在这一层 确定每个小区内的基站位置 诸如天线塔高度 天线增益和发射功 率等参数都进一步根据每个小区的地形不规则性的特征 表面覆盖和环境进行调整 从上面两层得到的结果已满足了覆盖性能 并试图满足话务要求 但不管怎样 在 某些小区的话务过载可能仍然存在 在这一层 可以用 Hale 6 和 Gamst 23 的信道 分配策略来提供信道数的下界 把在 7 8 20 中提到的固定和动态信道分配策略应 用于蜂窝系统的网络规划以提供足够的容量来为预期的话务量服务 并保持无线干 扰到最小限度 如果系统性能在调整后达到了要求 最后的系统设计就确定了 也就可以估计 出蜂窝系统的成本 否则在这一层的结果将反馈到第一层和第二层 然后重复整个 过程 在这种情况下 可能需要增加小区的数量以满足规定的服务质量 模拟结果模拟结果 A HOP模型的应用 分层优化方法被用来设计提供如图 1 和图 3 所示的为新加坡地区提供服务的蜂 窝系统 在我们的研究中使用了模仿新加坡地形 话务分布和人口的数据 整个地 区被分为三种类型和 100 个网格 表 1 列出了关于每个网格的话务密度和地面类型 等信息 服务区域 S 有 625km 每个网格的区域面积约为 2 5 2 5 km 在系统 22 设计中采用了 7 小区频率复用模型 假设要达到 90 的区域覆盖率并且忙时 a P 初始呼叫的阻塞率 5 b P 当2 3 时 相应于 90 的区域覆盖率 边界处的位置覆盖 75 pp n L P 其中是接收信号的慢衰落部分的标准偏差 是距离因子的指数 2 对于给定 p p n 10 的位置覆盖概率和要求的 C N 和 C I 设置边界处的接收信号强度 L P 93dbm 1 9 假设每个小区的信道数为 45 平均通话时长为 cell P 1 76min call 呼叫尝试率为 0 9call h 则每小区可提供的话务负载为 39 6 爱尔兰 能为 39 6 60 1 76 0 9 1500subscribers h 的总移动单元数提供服务 pt C 首先 开始进行设计时先需要确定小区数的上界 从 4 6 我们可得 17 d 3 53km 从 7 我们有 29400 同时考虑覆盖和话务性能 1 n max2 n 我们选择 n max 20 1 n 2 n 接着 来确定 20 个小区的安置 假设给出系统成本的标准化参数如下 1000 5 0 10 0 0 5 基站和移动单元的参数选择如下 cell C a C t C traf C 9 对所有的小区 k dBigdBmPdBmPdBigdBig mkULUL 0 36 30 18 8 根据 24 和 25 我们得到了天线成本和其增益及发射机 或接收机 成本和其发 射功率之间的逼近线性关系 假设给出关于天线增益 g 的成本函数如下 gCA 40 Ca g gCA U gg 0 M U gg 关于发射功率 P 的成本函数如下 PCT 60 Ct P PCT U PP 0 M U PP 其中 M 是一个大的正数 我们根据上面的具体参数应用模拟退火算法 SAEOM 来求解 EOM 问题 冷却进度 表的控制参数如下 初始接受率 0 9 次数内目标 0 38 3 20 100 最大容 许偏差 0 62 3 m n 最大生成极限 4 MUB 21 在 HP C180 的 UNIX 系统上 用 C 语言执行了这个算法 图 3 给出了一个初始可行解 初始设计 具有相同阴影的相邻网格组成一个小 区 总系统成本为 24349 68 图 4 给出了用 SAEOM 算法求出的最优解 这个最 优解是在用不同的初始可行解运行程序 10 次后才获得的 最终设计 fc s 的邻近最 优系统成本是 20139 20 小区数进一步减少了 6 个 图 5 显示了收敛记录 即用 SAEOM 算法求解 EOM 问题的退火曲线 退火需要的平均 CPU 时间为 34 65 分钟 11 为了评估 SA 方法求得的解 我们把它与用 Aarts 和 Korst 15 的本地搜索过程 求得的最佳解和用随机生成过程获得的解比较 用本地搜索过程求得的最佳解为系 统成本 fc s 20452 4 和小区数 n 13 如成本函数 19 所示 每个小区的固定成本 决定总系统成本 这意味着成本有效设计应该有较少的小区数和每个小区较 cell C 高的平均话务负载 图 6 和图 7 分别表示用 SAEON 和本地搜索方法求得的最佳解 中的话务量柱形图 图 8 表示在小区数也是 13 这种情况下 随机生成过程获得的 解的话务量分布 虚线和实心条分别代表每个小区能提供的话务负载和需要的话务 负载 从图 6 8 我们观察到用 SAEON 求得的逼近最优解在能提供的话务负载和 需要的话务负载之间取得了好的折衷 与其它两个过程相比 每个小区的话务负载 也呈均匀分布 如图 4 的最终设计所示 这个设计能满足覆盖要求 同时也努力 用最小的小区数和最佳的小区安置适应非一致话务负载 天线增益和发射功率的逼近最优值可从最佳解中获得 在最后一步 基站和移动单元的所有参数都要根据所在小区内具体的地形数据 和覆盖特征进行调整 从上面两层获得的结果能满足覆盖的质量要求 但并不能提 供每个小区的所有预期话务量 在最后一层 Gamst 23 技巧被用来确定要分配的 信道数下界 然后进一步应用 Dugue anton 20 的信道分配过程去满足话务要求和 避免干扰 B SA算法的性能 模拟退火方法 S