C-RAN回传网络中下行资源调度策略

工程科学学报，第40卷，第5期：629-638.2018年5月 Chinese Joural of Engineering,Vol.40,No.5:629-638,May 2018 DOI:10.13374/j.issn2095-9389.2018.05.014;http://journals.ustb.edu.cn C-RAN回传网络中下行资源调度策略 王汝言12)，周静2)，吴大鹏12) 1)重庆邮电大学通信与信息工程学院，重庆4000652)重庆邮电大学光通信与网路重点实验室，重庆400065 区通信作者，E-mail:1902414442@q4.com 摘要随着移动互联网技术的快速发展、无线终端设备与移动应用流量需求与日俱增，移动用户对无线通信网络的服务质 量(quality of service,QoS)要求越来越高、回传网络的压力也越来越大.新出现的云无线接人网(cloud radio access network,C~ -RAN)能够有效提升网络容量、提高用户服务质量，同时采用无源光网络(passive optical network,PON)作为其回传网络 (backhaul),能够为其提供大带宽、高可靠、低时延的回传支撑.在移动应用需求不断变化和回传网络资源有限的条件下，高 效的资源调度策略至关重要，其能够有效的提升回传网络资源利用率、降低传输等待时延.为节约回传网络波长资源、提高波 长负载均衡性和资源利用率，提出一种下行资源调度策略.根据高热点区域无线用户实时网络需求，综合考虑回传网络波长 使用数量、负载均衡性和实时业务分配均匀度等优化目标，采用自适应权重并行遗传算法完成其优化过程，从而实现波长资 源动态分配，提升网络资源利用率。仿真结果表明，提出的下行资源调度策略能有效提高网络负载均衡性和网络资源利用率， 并降低实时业务等待传输时间. 关键词云无线接入网：光回传网络：资源调度：遗传算法：自适应权重：分组调度 分类号TP393.0 A downlink resource scheduling strategy for C-RAN backhaul network WANG Ru-yan2,ZH0UJmg2)回，WUDa-peng2) 1)School of Communication and Information Engineering,Chongqing University of Posts and Telecommunications,Chongqing 400065,China 2)Key Laboratory of Optical Communication and Network,Chongqing University of Posts and Telecommunications,Chongqing 400065,China Corresponding author,E-mail:1902414442@qq.com ABSTRACT With the rapid development of mobile internet technology and daily increase in wireless user equipment as well as de- mand of mobile applications,the required quality of service (QoS)by mobile users for wireless communication networks is increasing, and the pressure of backhaul network is also increasing.The emerging cloud radio access network (C-RAN)can effectively improve the network capacity and user service quality.Meanwhile,Passive Optical Network (PON)was used for backhaul network that offers a large bandwidth,high reliability,and low latency backhaul.When the demand of mobile applications is ever-changing and backhaul network resource is limited,an efficient backhaul network resource scheduling strategy is of great importance.This can improve the backhaul network resource utilization and waiting-transmitting delay in C-RAN.To save backhaul network resource,improve the load balance of wavelengths and the utilization of network resource,a downlink resource scheduling strategy was proposed.According to the network demand of wireless users in hot spots,three optimization objectives including the number of used wavelengths,load balance, and well-distribution of real-time traffic were considered in the optimization of adaptive-weighted parallel genetic algorithm.Thus,the wavelength resources were dynamically allocated and resource utilization was improved.The results demonstrate that the proposed downlink resource scheduling strategy can effectively improve the load balance and resource utilization and reduce the waiting-transmit- ting delay of real-time traffic. 收稿日期：2017-07-12 基金项目：国家自然科学基金资助项目(61371097,61771082)

工程科学学报,第 40 卷,第 5 期:629鄄鄄638,2018 年 5 月 Chinese Journal of Engineering, Vol. 40, No. 5: 629鄄鄄638, May 2018 DOI: 10. 13374 / j. issn2095鄄鄄9389. 2018. 05. 014; http: / / journals. ustb. edu. cn C鄄鄄RAN 回传网络中下行资源调度策略 王汝言1,2) , 周 静1,2) 苣 , 吴大鹏1,2) 1) 重庆邮电大学通信与信息工程学院, 重庆 400065 2) 重庆邮电大学光通信与网络重点实验室, 重庆 400065 苣 通信作者, E鄄mail:1902414442@ qq. com 摘 要 随着移动互联网技术的快速发展、无线终端设备与移动应用流量需求与日俱增,移动用户对无线通信网络的服务质 量(quality of service, QoS)要求越来越高、回传网络的压力也越来越大. 新出现的云无线接入网(cloud radio access network, C鄄 鄄RAN)能够有效提升网络容量、提高用户服务质量,同时采用无源光网络( passive optical network, PON) 作为其回传网络 (backhaul),能够为其提供大带宽、高可靠、低时延的回传支撑. 在移动应用需求不断变化和回传网络资源有限的条件下,高 效的资源调度策略至关重要,其能够有效的提升回传网络资源利用率、降低传输等待时延. 为节约回传网络波长资源、提高波 长负载均衡性和资源利用率,提出一种下行资源调度策略. 根据高热点区域无线用户实时网络需求,综合考虑回传网络波长 使用数量、负载均衡性和实时业务分配均匀度等优化目标,采用自适应权重并行遗传算法完成其优化过程,从而实现波长资 源动态分配,提升网络资源利用率. 仿真结果表明,提出的下行资源调度策略能有效提高网络负载均衡性和网络资源利用率, 并降低实时业务等待传输时间. 关键词 云无线接入网; 光回传网络; 资源调度; 遗传算法; 自适应权重; 分组调度 分类号 TP393郾 0 收稿日期: 2017鄄鄄07鄄鄄12 基金项目: 国家自然科学基金资助项目(61371097, 61771082) A downlink resource scheduling strategy for C鄄鄄RAN backhaul network WANG Ru鄄yan 1,2) , ZHOU Jing 1,2) 苣 , WU Da鄄peng 1,2) 1) School of Communication and Information Engineering, Chongqing University of Posts and Telecommunications, Chongqing 400065, China 2) Key Laboratory of Optical Communication and Network, Chongqing University of Posts and Telecommunications, Chongqing 400065, China 苣 Corresponding author, E鄄mail:1902414442@ qq. com ABSTRACT With the rapid development of mobile internet technology and daily increase in wireless user equipment as well as de鄄 mand of mobile applications, the required quality of service (QoS) by mobile users for wireless communication networks is increasing, and the pressure of backhaul network is also increasing. The emerging cloud radio access network (C鄄鄄RAN) can effectively improve the network capacity and user service quality. Meanwhile, Passive Optical Network (PON) was used for backhaul network that offers a large bandwidth, high reliability, and low latency backhaul. When the demand of mobile applications is ever鄄changing and backhaul network resource is limited, an efficient backhaul network resource scheduling strategy is of great importance. This can improve the backhaul network resource utilization and waiting鄄transmitting delay in C鄄鄄RAN. To save backhaul network resource, improve the load balance of wavelengths and the utilization of network resource, a downlink resource scheduling strategy was proposed. According to the network demand of wireless users in hot spots, three optimization objectives including the number of used wavelengths, load balance, and well鄄distribution of real鄄time traffic were considered in the optimization of adaptive鄄weighted parallel genetic algorithm. Thus, the wavelength resources were dynamically allocated and resource utilization was improved. The results demonstrate that the proposed downlink resource scheduling strategy can effectively improve the load balance and resource utilization and reduce the waiting鄄transmit鄄 ting delay of real鄄time traffic

.630· 工程科学学报，第40卷，第5期 KEY WORDS cloud radio access network;optical backhaul network;resource scheduling;genetic algorithm:adaptive weight; packets scheduling 近年来，随着移动互联网迅猛发展，移动应用流 利用率，同时所采用的无源光网络(passive optical 量需求与用户接入数量急剧增加，移动用户对于移 network,PON)也不适合现今回传网络的实际应用 动通信网络资源需求越来越大、质量要求越来越高. 环境.除此之外，针对传统固定模式下回传网络资 未来第五代移动通信系统(ffh-generation mobile 源利用率低的问题，文献[11]提出一种基于博弈论 communication,5G)能够满足这样的需求，其可以为 的回传资源调度算法，以解决不同服务商的基站共 用户提供更高速率、更低时延、更广覆盖的网络服务 享同一回传网络设施时的资源分配问题.但该文献 体验山：同时，研究人员提出将移动无线网络与无 没有考虑无线蜂窝网中不同热点区域的资源需求存 源光网络融合的想法，充分利用光网络高带宽、高可 在差异，并且其采用传统模式的PON做回传，同样 靠的优势将其作为回传网络，以满足移动用户的服 不适合现今回传网络应用环境.文献[12]采用波分 务质量需求2-).面对日益增长的移动流量需求，光 复用无源光网络(wavelength division-multiplexed 回传网络必须能够为移动网络提供大容量、低时延、 passive optical network,WDM-PON)实现▣传，以提 无缝连接的回传支撑，那么在有限回传网络资源条 升用户数据分组的传输时延为主要目标，提出了一 件下，如何为更多的用户提供更优质的服务，如何有 种下行波长选择与调度的优化算法.但该文献只考 效调度融合网中光纤回传资源已成为一大研究热 虑了时延性能，并且不能动态调整波长数量，同时当 点，这对于提升网络的服务质量(quality of service, 光网络单元(optical network unit,ONU)的负载不均 QoS)性能尤其重要) 匀时，其波长之间协调比较困难. 针对上述问题，国内外研究人员对回传网络的 针对上述不足，在云无线接入网(cloud radio 资源调度做了一些相关研究.文献[5-7]提出了多 access network,C-RAN)与时分波分复用无源光网 种回传网络资源调度算法，但这些算法并没有考虑 time and wavelength division-multiplexing passive 与光网络结合.在光无线融合网(fiber-wireless,Fi- optical network,TWDM-PON)的融合网中充分考虑 W)中，文献[8]针对无线域路由节点如何有效地管 高热点区域用户需求量大、网络需求不均匀时造成 理及均衡地转发本地流量与非本地流量和当路由节 回传资源分配不均衡的问题，本文提出一种自适应 点需求资源较少时可能无资源可用的问题，提出了 权重并行遗传算法(adaptive-weighted parallel genetic 一种基于重复博弈论框架的带宽分配算法，通过阻 algorithm,AWPGA)来解决回传网络资源调度问题， 止使用无用资源、避免转发会被丢弃的数据包和保 光链路终端(optical line terminal,OLT)通过光网络 持队列时延较小的方式，实现节点带宽公平分配. 单元(ONU)获取高热点区域用户需求，并依据区域 文献[9]利用网络效用最大化模型定义了在资源分 需求大小动态分配并行遗传算法各适应值函数的权 配中的公平性概念，并以此提出了一种公平分配额 重，从而得到优化问题的解，进而完成波长分配与下 外带宽的动态带宽分配算法，目的在于公平分配带 行数据分组调度，最终实现下行回传资源调度 宽，同时改善网络的时延、抖动等性能.在长期演进 1TWDM-PON与C-RAN的融合网络 (long term evolution,LTE)与吉比特以太无源光网 络(gigabit Ethernet PON,GEPON)的融合网中，为了 作为一种全新的无线接入网架构，C-RAN可以 提高有线用户与无线用户的QoS,文献[10]预测将 显著提高系统容量、降低能耗，比传统网络架构拥有 要到达的流量，并在QoS映射策略基础上，提出一 更好的灵活性和更高的资源利用率，并且，C-RAN 种上行带宽分配机制，以提升用户保证比特速率 也是一种5G移动蜂窝接入网候选技术)]，可适用 (guaranteed bit rate,GBR)服务的QoS性能.文献 于大多数经典应用场景，如蜂窝分裂、区域覆盖、高 [8-10]都是基于光与无线融合网进行资源分配研 热点区域、高速运动等.另一方面，PON具有大容 究，其中文献[8-9]针对网络资源分配的公平性展 量、高带宽、高可靠性等特点，用其作移动网络的回 开研究，而文献[10]针对网络用户特定业务进行资 传更是一种有前景的回传问题解决方案[).可见， 源分配，但上述文献主要针对上行带宽分配，没有考 融合具有大容量、高带宽、高可靠等特点的PON和 虑下行方向的资源分配，并且也没有考虑网络资源 高资源利用率、高能效的C-RAN,结合两者优势可

工程科学学报,第 40 卷,第 5 期 KEY WORDS cloud radio access network; optical backhaul network; resource scheduling; genetic algorithm; adaptive weight; packets scheduling 近年来,随着移动互联网迅猛发展,移动应用流 量需求与用户接入数量急剧增加,移动用户对于移 动通信网络资源需求越来越大、质量要求越来越高. 未来第五代移动通信系统 ( fifth鄄generation mobile communication, 5G)能够满足这样的需求,其可以为 用户提供更高速率、更低时延、更广覆盖的网络服务 体验[1] ;同时,研究人员提出将移动无线网络与无 源光网络融合的想法,充分利用光网络高带宽、高可 靠的优势将其作为回传网络,以满足移动用户的服 务质量需求[2鄄鄄3] . 面对日益增长的移动流量需求,光 回传网络必须能够为移动网络提供大容量、低时延、 无缝连接的回传支撑,那么在有限回传网络资源条 件下,如何为更多的用户提供更优质的服务,如何有 效调度融合网中光纤回传资源已成为一大研究热 点,这对于提升网络的服务质量( quality of service, QoS)性能尤其重要[4] . 针对上述问题,国内外研究人员对回传网络的 资源调度做了一些相关研究. 文献[5鄄鄄7]提出了多 种回传网络资源调度算法,但这些算法并没有考虑 与光网络结合. 在光无线融合网( fiber鄄wireless, Fi鄄 Wi)中,文献[8]针对无线域路由节点如何有效地管 理及均衡地转发本地流量与非本地流量和当路由节 点需求资源较少时可能无资源可用的问题,提出了 一种基于重复博弈论框架的带宽分配算法,通过阻 止使用无用资源、避免转发会被丢弃的数据包和保 持队列时延较小的方式,实现节点带宽公平分配. 文献[9]利用网络效用最大化模型定义了在资源分 配中的公平性概念,并以此提出了一种公平分配额 外带宽的动态带宽分配算法,目的在于公平分配带 宽,同时改善网络的时延、抖动等性能. 在长期演进 (long term evolution, LTE)与吉比特以太无源光网 络(gigabit Ethernet PON, GEPON)的融合网中,为了 提高有线用户与无线用户的 QoS,文献[10]预测将 要到达的流量,并在 QoS 映射策略基础上,提出一 种上行带宽分配机制,以提升用户保证比特速率 (guaranteed bit rate, GBR) 服务的 QoS 性能. 文献 [8鄄鄄10]都是基于光与无线融合网进行资源分配研 究,其中文献[8鄄鄄9]针对网络资源分配的公平性展 开研究,而文献[10]针对网络用户特定业务进行资 源分配,但上述文献主要针对上行带宽分配,没有考 虑下行方向的资源分配,并且也没有考虑网络资源 利用率,同时所采用的无源光网络( passive optical network, PON)也不适合现今回传网络的实际应用 环境. 除此之外,针对传统固定模式下回传网络资 源利用率低的问题,文献[11]提出一种基于博弈论 的回传资源调度算法,以解决不同服务商的基站共 享同一回传网络设施时的资源分配问题. 但该文献 没有考虑无线蜂窝网中不同热点区域的资源需求存 在差异,并且其采用传统模式的 PON 做回传,同样 不适合现今回传网络应用环境. 文献[12]采用波分 复 用 无 源 光 网 络 ( wavelength division鄄multiplexed passive optical network, WDM鄄鄄PON)实现回传,以提 升用户数据分组的传输时延为主要目标,提出了一 种下行波长选择与调度的优化算法. 但该文献只考 虑了时延性能,并且不能动态调整波长数量,同时当 光网络单元(optical network unit, ONU)的负载不均 匀时,其波长之间协调比较困难. 针对上述不足,在云无线接入网( cloud radio access network, C鄄鄄RAN)与时分波分复用无源光网 络( time and wavelength division鄄multiplexing passive optical network, TWDM鄄鄄PON)的融合网中充分考虑 高热点区域用户需求量大、网络需求不均匀时造成 回传资源分配不均衡的问题,本文提出一种自适应 权重并行遗传算法(adaptive鄄weighted parallel genetic algorithm, AWPGA)来解决回传网络资源调度问题, 光链路终端(optical line terminal, OLT)通过光网络 单元(ONU)获取高热点区域用户需求,并依据区域 需求大小动态分配并行遗传算法各适应值函数的权 重,从而得到优化问题的解,进而完成波长分配与下 行数据分组调度,最终实现下行回传资源调度. 1 TWDM鄄鄄PON 与 C鄄鄄RAN 的融合网络 作为一种全新的无线接入网架构,C鄄鄄RAN 可以 显著提高系统容量、降低能耗,比传统网络架构拥有 更好的灵活性和更高的资源利用率,并且,C鄄鄄 RAN 也是一种 5G 移动蜂窝接入网候选技术[13] ,可适用 于大多数经典应用场景,如蜂窝分裂、区域覆盖、高 热点区域、高速运动等. 另一方面,PON 具有大容 量、高带宽、高可靠性等特点,用其作移动网络的回 传更是一种有前景的回传问题解决方案[14] . 可见, 融合具有大容量、高带宽、高可靠等特点的 PON 和 高资源利用率、高能效的 C鄄鄄RAN,结合两者优势可 ·630·

王汝言等：C-RAN回传网络中下行资源调度策略 ·631· 以为移动用户提供更好的服务，通过PON能够为 TWDM-PON作回传与C-RAN融合，研究融合网络 C-RAN提供更优的回传资源传输.因此，本文采用 的下行资源调度，其网络拓扑结构如图1所示. ONU BBU pool 核心网 OLT ONU BBU pool 高热点区域 高热点区域 回传 ONU BBU pool 前传 用户 RRH 图1TWDM-PON与C-RAN融合网络结构图 Fig.1 Architecture of TWDM-PON-enabled C-RAN backhaul 从图1可以看出融合网络分为两个部分，OLT 种可行的资源调度方案，以满足热点区域用户的 到ONU之间是回传(backhaul);基带处理单元池 网络需求，提高资源分配均衡性、提升网络资源利 (baseband unit pool,BBU pool)到射频拉远头(re- 用效率. mote radio head,RRH)之间是前传(fronthaul).回 回传网络资源调度首先要解决TWDM-PON的 传采用TWDM-PON进行数据传输，其中存在多条 波长分配问题.充分考虑无线网络需求后，本文根 波长为多个ONU服务s).无线域部分，在C-RAN 据负载均衡的思想进行波长分配以实现波长之间的 网络结构下，包括由多个低功率无线接入节点 负载均衡性、提高资源利用率，并保证实时业务均匀 (small cell)组成的高热点区域.在这些热点区域 分配以减少等待传输时间.综上，可得如下三个优 中，用户的数量和需求在不同时刻是不完全相同的， 化目标： 并且，热点区域的网络需求量的变化会影响回传网 (1)传输无线用户下行数据所用波长数量最 络的资源调度.可见，在上述融合网络结构中，当各 少； 个热点区域内的无线用户数量和网络需求随时间发 (2)无线用户网络需求均衡分配到各波长，提 生变化时，回传网络需要根据这些变化，有针对性地 高波长负载均衡性； 实施网络资源调度策略，在满足用户下行网络需求 (3)实时业务能够尽量均匀分配给波长，以减 时，尽可能地节约网络资源、提高网络资源利用率和 少实时业务的等待传输时间. 降低实时业务的等待传输时间.故而，本文解决从 为了得到上述多目标优化问题的最优解，本文 核心网到热点区域的下行资源调度问题，使得回传 采用整数非线性规划(integer non--linear program- 网络能够依据实时网络需求变化而动态调整调度方 ming,INLP)多目标优化数学模型来解决此问题. 案，从而达到回传资源有效调度的目的. 由此NLP多目标优化模型，可得到波长分配的最 优解，此模型的数学描述如下所示，其中涉及到的符 2多目标优化模型 号参数如表1所示. 在高热点区域密集部署small cell,是极具应用 目标函数： 前景的5G高热点覆盖接入问题解决方案之一.虽 minN=∑0. (1) 然，密集部署small cell可以提供更高的频谱效率、 weW 更大的网络容量，但是，大规模部署small cell形成 minB=（ o.o...- 多个热点区域时，将导致接入用户数量和网络需求 急剧增加，这不仅需要提高回传网络容量和传输 (2) 速率等指标，还需要对回传资源提出相应的资源 minV= 调度方法.因此，本文根据热点区域网络需求分布 (gk-三0k =1=1+1 不均匀、回传网络资源分配不均衡等情况，提出一 (3)

王汝言等: C鄄鄄RAN 回传网络中下行资源调度策略 以为移动用户提供更好的服务,通过 PON 能够为 C鄄鄄RAN提供更优的回传资源传输. 因此,本文采用 TWDM鄄鄄PON 作回传与 C鄄鄄RAN 融合,研究融合网络 的下行资源调度,其网络拓扑结构如图 1 所示. 图 1 TWDM鄄鄄PON 与 C鄄鄄RAN 融合网络结构图 Fig. 1 Architecture of TWDM鄄鄄PON鄄鄄 enabled C鄄鄄RAN backhaul 从图 1 可以看出融合网络分为两个部分,OLT 到 ONU 之间是回传( backhaul);基带处理单元池 (baseband unit pool, BBU pool) 到射频拉远头( re鄄 mote radio head, RRH) 之间是前传( fronthaul). 回 传采用 TWDM鄄鄄 PON 进行数据传输,其中存在多条 波长为多个 ONU 服务[15] . 无线域部分,在 C鄄鄄 RAN 网络结构下,包括由多个低功率无线接入节点 (small cell)组成的高热点区域. 在这些热点区域 中,用户的数量和需求在不同时刻是不完全相同的, 并且,热点区域的网络需求量的变化会影响回传网 络的资源调度. 可见,在上述融合网络结构中,当各 个热点区域内的无线用户数量和网络需求随时间发 生变化时,回传网络需要根据这些变化,有针对性地 实施网络资源调度策略,在满足用户下行网络需求 时,尽可能地节约网络资源、提高网络资源利用率和 降低实时业务的等待传输时间. 故而,本文解决从 核心网到热点区域的下行资源调度问题,使得回传 网络能够依据实时网络需求变化而动态调整调度方 案,从而达到回传资源有效调度的目的. 2 多目标优化模型 在高热点区域密集部署 small cell,是极具应用 前景的 5G 高热点覆盖接入问题解决方案之一. 虽 然,密集部署 small cell 可以提供更高的频谱效率、 更大的网络容量,但是,大规模部署 small cell 形成 多个热点区域时,将导致接入用户数量和网络需求 急剧增加,这不仅需要提高回传网络容量和传输 速率等指标,还需要对回传资源提出相应的资源 调度方法. 因此,本文根据热点区域网络需求分布 不均匀、回传网络资源分配不均衡等情况,提出一 种可行的资源调度方案,以满足热点区域用户的 网络需求,提高资源分配均衡性、提升网络资源利 用效率. 回传网络资源调度首先要解决 TWDM鄄鄄 PON 的 波长分配问题. 充分考虑无线网络需求后,本文根 据负载均衡的思想进行波长分配以实现波长之间的 负载均衡性、提高资源利用率,并保证实时业务均匀 分配以减少等待传输时间. 综上,可得如下三个优 化目标: (1)传输无线用户下行数据所用波长数量最 少; (2)无线用户网络需求均衡分配到各波长,提 高波长负载均衡性; (3)实时业务能够尽量均匀分配给波长,以减 少实时业务的等待传输时间. 为了得到上述多目标优化问题的最优解,本文 采用整数非线性规划 ( integer non鄄linear program鄄 ming, INLP)多目标优化数学模型来解决此问题. 由此 INLP 多目标优化模型,可得到波长分配的最 优解,此模型的数学描述如下所示,其中涉及到的符 号参数如表 1 所示. 目标函数: min N = 移w沂W Ow (1) minB = ( 移w沂W Ow·( 移m沂M Ow,m Rm - 移m沂M Rm 移w沂W Ow ) ) 2 移w沂W Ow (2) minV = 移 | W| -1 w = 1 移 | W| x = w+ ( 1 移m沂M Ow,m Rm,1 - 移m沂M Ox,m Rm,1 ) 2 (3) ·631·

.632· 工程科学学报，第40卷，第5期 表1符号参数 Table 1 Notation parameters 0..-1.0..1.Vwew.Vman 符号参数 符号描述 (8) 波长集合 式(8)确保了每个ONU有且只会被一条波长 M ONU集合 服务，但一条波长可以服务多个ONU 波长容量 1≤∑0.≤IWl,Hoew (9) Rm 第m个热点区域(ONU)的用户网络需求 式(9)确保了波长使用数量不得超过波长总 第m个热点区域(ONU)用户实时业务与非实时业 Re.1.Rm2 数，且网络中至少有一条波长在使用. 务网络需求 0. 0-1变量，表示第条波长的使用情况 ∑0.Rn≤C,oew (10) 0-1变量，表示第w条波长与第m个ONU的光路建 式(10)确保了波长分配时，每条波长上的负载不得 0g,m 立状态 超过其容量上限 整数变量，表示回传网络中波长使用数量 上述即是TWDM-PON中NLP多目标波长分 B 实数变量，表示回传网络中波长之间负载均衡情况 配优化问题的数学描述，所以解决此NLP多目标 实数变量，表示回传网路中波长之间实时业务分配 优化问题即可得到波长分配问题的最优解. 差异 3自适应权重并行遗传算法 ∑R mel 由第2部分可知，光回传网络波长分配问题可 u C·N (4) 以利用NLP多目标优化模型来解决，然而NLP多 目标优化模型需要进行全局搜索才能得到问题最优 C t>d (5) 解，具有较高的计算复杂度，因而它不适合解决大规 模网络优化问题.此外，当网络负载状态变化时，资 上述式(1)~(3)是波长分配的目标函数，式 源调度策略也需要做适当改变.因此，本文在并行 (4)和(5)是在完成波长分配以及下行分组调度后， 遗传算法和权重系数遗传算法的基础上，提出一种 仿真分析时所用的目标函数.其中，式(1)表示分配 启发式自适应权重并行遗传算法来解决不同网络负 的波长数量最少，尽量节约波长资源：式(2)中，用 载状态下C-RAN回传网络波长分配问题.考虑到 均方误差衡量波长之间负载均衡性，使各个波长之 遗传算法通常有遗传编码和遗传操作等过程，具体 间的负载能够均衡：式(3)中，为避免单条波长中实 的算法过程如下所述 时业务过多而造成不必要的等待传输时间而尽量保 3.1遗传编码 证实时业务均匀分配，以满足用户实时业务的QS； 遗传算法是一种基于自然进化法则的启发式优 式(4)中表示在网络资源分配后，在用波长的资源 化方法，根据遗传算法的一般操作，首先要对原问题 利用率情况，其中u表示资源利用率：式(5)表示当 进行遗传编码.在光回传网络波长分配问题中，因 完成波长分配以及下行分组调度后，实时业务分组 为每个ONU有且只会被一条波长服务，那么可以用 未顺利传输完成的情况，其定义为网络中实时业务 一个基因gm.表示第0条波长与第m个ONU的光 数据分组未顺利完成传输的数量与实时业务数据分 路建立关系，用一个0-1整数表示，1表示当前波长 组总量的比值，用f表示，式中山表示第i个实时数 与当前ONU有光路建立，没有建立则为0.同时，网 据分组能够容忍的最大时延，tl,:表示第i个实时业 络中存在IMI个ONU和IWI条波长，因此波长分配 务数据分组完成传输所用的时间，即式中分子表示 问题的一组可行解就可以编码为一组含有1M1× 了未顺利完成传输的实时数据分组个数，s表示所 IWI个基因的集合，即个体（或染色体），用I= 有传输的实时数据分组个数. g182,283,,…,8m,4,0g∈W,m∈M}表示.例 约束条件： 如，若有2条波长及4个0NU,那么可以用I={1, 0.∈{0,1}，Hw∈W (6) 0,1,0,0,1,0,1}表示一条染色体，前4个整数表示 0.m∈{0,1}，Ho∈W,HmeM (7) 第1条波长所服务的第1、3个0NU,同理后4个则 式(6)和(7)限制了变量0.、0.m的取值范围， 是第2条波长服务的第2、4个ONU.然后，随机生 确保它们是0-1整数变量. 成初始个体，并利用惩罚函数确保它们是可行解，最

工程科学学报,第 40 卷,第 5 期 表 1 符号参数 Table 1 Notation parameters 符号参数 符号描述 W 波长集合 M ONU 集合 C 波长容量 Rm 第 m 个热点区域(ONU)的用户网络需求 Rm,1 ,Rm,2 第 m 个热点区域(ONU) 用户实时业务与非实时业 务网络需求 Ow 0鄄鄄1 变量,表示第 w 条波长的使用情况 Ow,m 0鄄鄄1 变量,表示第 w 条波长与第 m 个 ONU 的光路建 立状态 N 整数变量,表示回传网络中波长使用数量 B 实数变量,表示回传网络中波长之间负载均衡情况 V 实数变量,表示回传网络中波长之间实时业务分配 差异 u = 移m沂M Rm C·N (4) f = 移 s i = 1 {1 | t real,i > di} s (5) 上述式(1) ~ (3) 是波长分配的目标函数,式 (4)和(5)是在完成波长分配以及下行分组调度后, 仿真分析时所用的目标函数. 其中,式(1)表示分配 的波长数量最少,尽量节约波长资源;式(2) 中,用 均方误差衡量波长之间负载均衡性,使各个波长之 间的负载能够均衡;式(3)中,为避免单条波长中实 时业务过多而造成不必要的等待传输时间而尽量保 证实时业务均匀分配,以满足用户实时业务的 QoS; 式(4)中表示在网络资源分配后,在用波长的资源 利用率情况,其中 u 表示资源利用率;式(5)表示当 完成波长分配以及下行分组调度后,实时业务分组 未顺利传输完成的情况,其定义为网络中实时业务 数据分组未顺利完成传输的数量与实时业务数据分 组总量的比值,用 f 表示,式中 di 表示第 i 个实时数 据分组能够容忍的最大时延,t real,i表示第 i 个实时业 务数据分组完成传输所用的时间,即式中分子表示 了未顺利完成传输的实时数据分组个数,s 表示所 有传输的实时数据分组个数. 约束条件: Ow沂{0,1},坌w沂W (6) Ow,m沂{0,1},坌w沂W,坌m沂M (7) 式(6)和(7)限制了变量 Ow 、Ow,m的取值范围, 确保它们是 0鄄鄄1 整数变量. 移w沂W Ow,m = 1, 移m沂M Ow,m逸1,坌w沂W,坌m沂M (8) 式(8) 确保了每个 ONU 有且只会被一条波长 服务,但一条波长可以服务多个 ONU. 1臆 移w沂W Ow臆| W| ,坌w沂W (9) 式(9) 确保了波长使用数量不得超过波长总 数,且网络中至少有一条波长在使用. 移m沂M Ow,m Rm臆C,坌w沂W (10) 式(10)确保了波长分配时,每条波长上的负载不得 超过其容量上限. 上述即是 TWDM鄄鄄 PON 中 INLP 多目标波长分 配优化问题的数学描述,所以解决此 INLP 多目标 优化问题即可得到波长分配问题的最优解. 3 自适应权重并行遗传算法 由第 2 部分可知,光回传网络波长分配问题可 以利用 INLP 多目标优化模型来解决,然而 INLP 多 目标优化模型需要进行全局搜索才能得到问题最优 解,具有较高的计算复杂度,因而它不适合解决大规 模网络优化问题. 此外,当网络负载状态变化时,资 源调度策略也需要做适当改变. 因此,本文在并行 遗传算法和权重系数遗传算法的基础上,提出一种 启发式自适应权重并行遗传算法来解决不同网络负 载状态下 C鄄鄄RAN 回传网络波长分配问题. 考虑到 遗传算法通常有遗传编码和遗传操作等过程,具体 的算法过程如下所述. 3郾 1 遗传编码 遗传算法是一种基于自然进化法则的启发式优 化方法,根据遗传算法的一般操作,首先要对原问题 进行遗传编码. 在光回传网络波长分配问题中,因 为每个 ONU 有且只会被一条波长服务,那么可以用 一个基因 gm,w表示第 w 条波长与第 m 个 ONU 的光 路建立关系,用一个 0鄄鄄1 整数表示,1 表示当前波长 与当前 ONU 有光路建立,没有建立则为 0. 同时,网 络中存在| M | 个 ONU 和 | W | 条波长,因此波长分配 问题的一组可行解就可以编码为一组含有 | M | 伊 | W|个基因的集合, 即个体 ( 或 染 色 体), 用 I = {g1,w1 ,g2,w2 ,g3,w3 ,…,gm,wk ,wk沂W,m沂M}表示. 例 如,若有 2 条波长及 4 个 ONU,那么可以用 I = {1, 0,1,0,0,1,0,1}表示一条染色体,前 4 个整数表示 第 1 条波长所服务的第 1、3 个 ONU,同理后 4 个则 是第 2 条波长服务的第 2、4 个 ONU. 然后,随机生 成初始个体,并利用惩罚函数确保它们是可行解,最 ·632·

王汝言等：C-RAN回传网络中下行资源调度策略 ·633· 终得到初始群体P~并且，提出的启发式遗传算 得到： 法的适应值函数与NLP的多目标优化函数相同， ∑R 即式(1)~(3) meM qad=W1·C (12) 3.2遗传操作 在实际网络环境中，每个热点区域内的网络需 在遗传算法中，通过编码组成初始种群后，接下 来便是实现遗传操作.遗传操作的任务就是对群体 求会随着时间的变化而变化，并且热点区域之间的 网络需求在不同时段也存在差异.显然，当网络负 中的个体按照它们对环境的适应程度（适应度评 估)施加一定的操作，从而实现优胜劣汰的进化过 载较小即q较小时，较少的网络资源也能够满足 网络中用户需求，所以这时可以考虑以节约网络资 程.从优化搜索的角度而言，遗传操作可使问题的 解，一代又一代的优化，并逼近最优解. 源为主：当网络负载明显较大、接入用户较多时即 遗传算法的遗传操作包含三个遗传算子：选择、 q较大时，此时网络资源占用率较高，考虑节约资 交叉和变异，通过它们可以实现具体的遗传操作. 源无太大意义，因此可以从用户角度出发，在有限网 在光回传网络资源分配问题中，结合权重系数和并 络资源下提升用户的网络服务质量. 行遗传算法来实现求解多目标优化问题，通过并行 综上所述，由于网络负载的变化必将导致波长 遗传算法可以实现快速求解多目标优化问题，而权 使用数量的改变，因此可根据网络负载大小决定适 重系数法则是为了对不断变化的网络需求进行有针 应值函数N的权重系数.如式(13)所示，因为权重 对性的波长分配. 系数和为1，故而将N的权重系数分配为1-qd, 根据并行遗传算法的基本思想，首先将种群平 使之随着网络负载的增加而减少.当负载增加时， 均分为三个子种群，每个子种群有1PI个个体，再 波长使用数量也会不可避免的增加，若是限制波长 分别为每个子种群分配一个子目标适应值函数N、B 使用数量会适得其反，故而其权重系数应当随着负 和V,然后在每个子种群内通过选择算子独立进行 载增加而减少.同时，网络中存在实时业务与非实 选择算法.为减少算法复杂度，本文采用常用的轮 时业务数据，由式(13)可得，当负载增加时，N的权 盘赌选择算子(roulette wheel selection operation),在 重会减少，相应必有B与V的权重增加：网络中实 当前子种群中重复1P。次选择适应度高的个体，组 时业务需要均匀分配，因此可将实时业务流量所占 成种群规模同样是|PI的新子种群.当完成新种 的比重作为权重分配的参考，如式(15)所示进行分 群的选择之后，将这三个新子种群重新合并为一个 配.V权重系数的分配，不仅随着网络负载的变化， 新种群P,继而再依据自适应交叉率P。和自适应变 还会根据网络中实时业务数据量的变化而变化，这 异率Pm进行相应的交叉和变异操作.这样，通过选 样既动态调整了B与V的权重系数，还考虑到实时 择、交叉和变异操作后，就会生成适应度更高的新 业务时延要求，所以最终的权重系数分配如式(13)~ 种群 (15)所示： 然后，在并行遗传算法的基础上，根据网络负载 q1=1-9ad (13) 大小并结合权重系数变换法，本文提出一种动态权 ∑Rm2 重分配方法.针对实时网络需求，有目的的调整多 meM 92=qload" ∑R (14) 目标适应函数的权重系数，从而可以自适应的分配 meM 网络资源.按照一般权重系数法可知，各个子目标 ∑Rl 适应函数线性加权和可如式(11)表示： mel q3=q1ad· (15) F=qN+q2B+93V (11) ∑R me 其中，9：表示第i个子目标适应函数在资源分配时 综上，得到各个适应值函数的权重后，个体适应 的重要程度，那么依据网络负载情况，则需要计算并 值便可以根据式(11)计算得到.除此之外，在进行 确定权重q:的值.在实际情况下，各个热点区域的 交叉与变异操作时，本文采用一种基于个体适应值 需求会随着时间的变化而改变，因此需要针对这种 自适应调整p。Pm的机制16，根据文献[16]所述， 不断变化的网络需求而动态调整网络资源调度策 为了解决遗传算法不能完全收敛或陷入局部最优解 略，即由负载大小确定各个函数的权重值.由网络 而导致算法性能变差的问题，文中提出这种根据种 中负载变化而动态调整权重系数，首先定义网络负 群适应度变化的自适应交叉率和变异率，以提高遗 载比qd,用它来表示网络负荷程度，其由下式 传算法性能，P。和Pm可由式(16)和(17)得到：

王汝言等: C鄄鄄RAN 回传网络中下行资源调度策略 终得到初始群体 Pinitial . 并且,提出的启发式遗传算 法的适应值函数与 INLP 的多目标优化函数相同, 即式(1) ~ (3). 3郾 2 遗传操作 在遗传算法中,通过编码组成初始种群后,接下 来便是实现遗传操作. 遗传操作的任务就是对群体 中的个体按照它们对环境的适应程度(适应度评 估)施加一定的操作,从而实现优胜劣汰的进化过 程. 从优化搜索的角度而言,遗传操作可使问题的 解,一代又一代的优化,并逼近最优解. 遗传算法的遗传操作包含三个遗传算子:选择、 交叉和变异,通过它们可以实现具体的遗传操作. 在光回传网络资源分配问题中,结合权重系数和并 行遗传算法来实现求解多目标优化问题,通过并行 遗传算法可以实现快速求解多目标优化问题,而权 重系数法则是为了对不断变化的网络需求进行有针 对性的波长分配. 根据并行遗传算法的基本思想,首先将种群平 均分为三个子种群,每个子种群有 | Psub | 个个体,再 分别为每个子种群分配一个子目标适应值函数 N、B 和 V,然后在每个子种群内通过选择算子独立进行 选择算法. 为减少算法复杂度,本文采用常用的轮 盘赌选择算子(roulette wheel selection operation),在 当前子种群中重复| Psub |次选择适应度高的个体,组 成种群规模同样是 | Psub | 的新子种群. 当完成新种 群的选择之后,将这三个新子种群重新合并为一个 新种群 P,继而再依据自适应交叉率 pc 和自适应变 异率 pm 进行相应的交叉和变异操作. 这样,通过选 择、交叉和变异操作后,就会生成适应度更高的新 种群. 然后,在并行遗传算法的基础上,根据网络负载 大小并结合权重系数变换法,本文提出一种动态权 重分配方法. 针对实时网络需求,有目的的调整多 目标适应函数的权重系数,从而可以自适应的分配 网络资源. 按照一般权重系数法可知,各个子目标 适应函数线性加权和可如式(11)表示: F = q1·N + q2·B + q3·V (11) 其中,qi 表示第 i 个子目标适应函数在资源分配时 的重要程度,那么依据网络负载情况,则需要计算并 确定权重 qi 的值. 在实际情况下,各个热点区域的 需求会随着时间的变化而改变,因此需要针对这种 不断变化的网络需求而动态调整网络资源调度策 略,即由负载大小确定各个函数的权重值. 由网络 中负载变化而动态调整权重系数,首先定义网络负 载比 qload , 用它来表示网络负荷程度, 其由下式 得到: qload = 移m沂M Rm | W |·C (12) 在实际网络环境中,每个热点区域内的网络需 求会随着时间的变化而变化,并且热点区域之间的 网络需求在不同时段也存在差异. 显然,当网络负 载较小即 qload较小时,较少的网络资源也能够满足 网络中用户需求,所以这时可以考虑以节约网络资 源为主;当网络负载明显较大、接入用户较多时即 qload较大时,此时网络资源占用率较高,考虑节约资 源无太大意义,因此可以从用户角度出发,在有限网 络资源下提升用户的网络服务质量. 综上所述,由于网络负载的变化必将导致波长 使用数量的改变,因此可根据网络负载大小决定适 应值函数 N 的权重系数. 如式(13)所示,因为权重 系数和为 1,故而将 N 的权重系数分配为 1 - qload , 使之随着网络负载的增加而减少. 当负载增加时, 波长使用数量也会不可避免的增加,若是限制波长 使用数量会适得其反,故而其权重系数应当随着负 载增加而减少. 同时,网络中存在实时业务与非实 时业务数据,由式(13)可得,当负载增加时,N 的权 重会减少,相应必有 B 与 V 的权重增加;网络中实 时业务需要均匀分配,因此可将实时业务流量所占 的比重作为权重分配的参考,如式(15)所示进行分 配. V 权重系数的分配,不仅随着网络负载的变化, 还会根据网络中实时业务数据量的变化而变化,这 样既动态调整了 B 与 V 的权重系数,还考虑到实时 业务时延要求,所以最终的权重系数分配如式(13) ~ (15)所示: q1 = 1 - qload (13) q2 = qload· 移m沂M Rm,2 移m沂M Rm (14) q3 = qload· 移m沂M Rm,1 移m沂M Rm (15) 综上,得到各个适应值函数的权重后,个体适应 值便可以根据式(11)计算得到. 除此之外,在进行 交叉与变异操作时,本文采用一种基于个体适应值 自适应调整 pc、pm 的机制[16] ,根据文献[16] 所述, 为了解决遗传算法不能完全收敛或陷入局部最优解 而导致算法性能变差的问题,文中提出这种根据种 群适应度变化的自适应交叉率和变异率,以提高遗 传算法性能, pc 和 pm 可由式(16)和(17)得到: ·633·