0HAL编号：tel-030306320https://theses.hal.science/tel-030306320提交日期：2020年11月30日0HAL是一个多学科开放获取存储库，用于存储和传播科学研究文档，无论其是否已发布。这些文档可能来自法国或国外的教学和研究机构，也可能来自公共或私人研究中心。0HAL（开放获取存储库）是用于存储和传播法国或国外教育和研究机构、公共或私人实验室发布或未发布的研究文档的多学科开放获取存储库。0无线网络中在线资源分配的机器学习技术0Nikolaos Liakopoulos0引用此版本：0Nikolaos Liakopoulos. 无线网络中在线资源分配的机器学习技术. 优化与控制 [math.OC]. SorbonneUniversité, 2019. 英文. �NNT : 2019SORUS529�. �tel-03030632�0论文0作为对SorbonneUniversit´es博士学位要求的部分完成0专业领域0通信系统0巴黎信息技术、电信和电子学院（Paris）0作者：0Nikolaos LIAKOPOULOS0无线网络中在线资源分配的机器学习技术0答辩定于2019年7月8日0由以下委员会审查：0Dr. E. Veronica Belmega 副教授 审查员 Dr. Georgios Paschos 主要研究员 工业监督员Dr. Leandros Tassiulas 教授 评审员 Dr. Marceau Coupechoux 教授 审查员 Dr. NavidNikaein 教授 论文监督员 Dr. Thrasyvoulos Spyropoulos 副教授 学术共同监督员 Dr.Urtzi Ayesta 研究主任 评审员0摘要0传统上，网络优化用于基于数学模型和统计假设在实际网络系统问题中提供良好的配置。最近，这一范式正在发展，受数据可用性爆炸的推动。网络问题的现代趋势是利用数据的力量来提取模型并处理不确定性。本论文旨在通过提出基于经典或数据驱动优化和机器学习的算法框架，来增强针对特定网络问题的算法库。在无线网络中，优化的应用在实践和研究中都在增长，随着无线通信的普及和对资源利用效率的极大需求。对无线数据的需求呈指数增长，网络中的设备和小区变得极其密集，服务具有极端和多样化的QoS要求。当前基于一种服务适用于所有类型和频谱重用的网络架构已经变得不再盈利。因此，在无线网络中的资源配置正在成为一个非常具有挑战性的问题。这可以简要归因于以下几点：i）需求的高时空变化，ii）优化的高维度和iii）决策的耦合。挑战在于提出快速、可扩展并能够快速适应输入变化的优化方法；同时对波动具有鲁棒性，以保证服务要求。我们针对两个用例，用户关联和云资源预留。用户关联的基本方法是将无线设备连接到提供最强信号的基站，这导致当前和未来无线网络中非常低效的配置。我们专注于根据底层网络需求，调整基于资源效率和服务需求满足（QoS保证）的用户关联。首先，我们研究了两种网络服务（第2章）的用户关联问题；一种需要VIP流的QoS保证，一种是最佳效果服务。目标是利用统计复用来优化资源的使用，同时确保VIP流享有主动的性能保证。我们将其构建为一个优化问题，表明问题是凸的，并最终证明最优点实际上可以通过分布式用户关联规则实现。0我0摘要0在第3章中，我们着手处理用户关联问题，重点是开发一个中心可扩展的算法。我们通过设计设备关联规则，将无线流量引导到云无线接入网络（C-RANs），以实现网络负载均衡。为了解决大规模连接和由此产生的计算瓶颈的挑战，我们提出了一种基于最优输运理论的方法，该理论研究了两个分布之间的概率经济转移。此外，我们提出了一个基于数据驱动的用户关联框架，利用鲁棒优化理论，详见第4章。主要思想是预测未来的流量波动，并利用这些预测在实际流量到达之前设计关联图。尽管由于预测误差，地图的实际播放是随机的，但这些地图被鲁棒地设计来处理不确定性，防止约束违规，并最大化凸型效用函数的期望，该函数用于准确平衡基站负载。最优地图具有一个有趣的特性，即它们共同优化了预测负载和预测误差的方差。我们在密集覆盖的米兰地区跟踪数据中验证了我们的鲁棒地图。转向云资源预留的话题，我们开发了一个新颖的框架，用于处理最坏情况下的资源预留，其中需求是由一个旨在损害我们性能的对手设计的。我们提供了“无悔”政策，并保证在这样的工作负载下在预算约束条件下渐近可行性，这补充了最近云计算和更重要的在线凸优化（OCO）文献的结果。在第5章中，我们提出了一个云资源预留政策，最终学习到最小成本预留，同时满足违规的时间平均约束。这利用了Lyapunov优化理论和基于最近过去的线性预测的组合。我们在真实的云系统跟踪数据上验证了我们的政策。接下来，在第6章中，我们推广了第5章的结果，创建了一个具有长期预算约束的在线凸优化问题的框架。这样的问题在网络中自然产生，如可靠性保证或总消耗约束。我们的建议是谨慎的在线Lagrange下降（COLD），我们推导了明确的界限，既涉及产生的后悔，又涉及剩余预算违规。最后，第7章包含了我们工作的结论和我们的未来目标，以及对所提出方法的比较的一些初步结果。0ii0致谢0在这个小页面上，我想要感谢所有参与让这些年变得更加愉快和远远超出教学过程的人们。他们在艰难的时刻给予支持，增强了美好的时刻，从许多方面让这段经历变得更好。首先，我想要感谢George和Akis。他们都对工作和科学有着极大的热情，但最终他们的心在于指导和教导，这些品质使他们成为了出色的导师。我的巴黎、雅典和其他地方的新老朋友，都应该被包括在内！我将不再一一列举他们，因为在这些年里，我意外地结识了许多伟大的朋友，无论是工作中还是在外面，都与他们建立了深厚的友谊。特别感谢Apostolos、Gregory和Nicoleta，浪费了我大部分的时间。对于George、Praxitelis、Ioanna、Mike和Electra，这些自本科以来的好朋友，我们都在巴黎度过了一段时间，无论我们身在何处，我们仍会共度时光。对于Joao、Michele、Ana和Lucie，他们总是在附近。最后但绝对不是最不重要的，是Maria、Theo、Revekka和最近加入的Marina。最后，最重要的是，我要感谢我的母亲Maria和我的兄弟Panayiotis，在这些年里给予我的无条件的爱和支持，以及我的已故父亲Petros，他是我这段旅程的灵感来源。0iii0致谢0ivv0目录0摘要........i0致谢........iii0目录........v0图表目录........xi0表格目录........xv0首字母缩略词........xvii01介绍1 1.1无线网络中的优化........101.1.1使用案例........201.2论文的贡献和大纲........301.2.1贡献和大纲........302具有服务质量保证的分布式用户关联11 2.1介绍........1102.1.1相关工作及我们的贡献........1202.2架构........1402.2.1系统模型........1402.2.2队列延迟模型........1502.2.3双重服务问题表述........1602.3分布式受限用户关联........1802.3.1部分拉格朗日松弛........1802.3.2最优用户关联规则........1902.3.3最大化方法........2002.3.3.1α > 0的梯度上升........2002.3.3.2α=0的次梯度方法........2002.3.4分布式受限用户关联算法........2102.4数值评估........2202.4.1模拟设置........2202.4.2在米兰数据集上验证结果........2302.4.3服务隔离........2402.5结论........250目录03基于计算最优传输的集中式可扩展用户关联27 3.1介绍........2703.2设备关联问题........2803.2.1下行链路模型........2803.2.2 RRH负载........2903.2.3相关工作........3003.3最优传输........3003.3.1最优传输简介........3003.3.2正则化OT........3103.3.3 Sinkhorn vs LP........3403.4 OT作为启发式负载平衡器........3503.5学习RRH负载........3703.6结论........3904基于鲁棒优化的数据驱动用户关联 41 4.1介绍........4104.1.1相关工作及我们的贡献......4204.2架构......4304.2.1系统模型......4304.2.2用户关联图......4504.2.3移动流量预测的统计方法......4604.2.4鲁棒用户关联图......4904.3广义鲁棒地图算法......5004.3.1凸形式......5004.3.2部分拉格朗日松弛......5204.3.3投影梯度下降......5204.3.4双子梯度法......5304.3.5 GRMA的示例应用......5604.4近似鲁棒地图......5804.4.1 RUA的泰勒逼近......5904.4.2最小化预期负载成本（MCEL）......5904.4.3最小化最坏情况成本（MWCC）......6004.4.4近似鲁棒地图的评估......6004.5数值评估......6204.5.1模拟设置......6204.5.2鲁棒地图1 vs MaxSINR......6204.5.3鲁棒地图2 vs自适应算法......6304.6高级预测方法......6604.6.1高斯估计误差模型验证......6604.6.2数值比较......6804.7结论......680vi6.1.1Related work . . . . . . . . . . . . . . . . . . . . . . .956.1.2Our contributions. . . . . . . . . . . . . . . . . . . .966.2OCO with long-term budget constraints . . . . . . . . . . . .976.2.1Problem formulation and assumptions . . . . . . . . .986.2.2Performance metric. . . . . . . . . . . . . . . . . . .986.2.2.1Feasibility. . . . . . . . . . . . . . . . . . .986.2.2.2Regret over K-benchmark . . . . . . . . . . .996.3The algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 1006.3.1Regularized drift plus loss framework . . . . . . . . . . 1016.4Performance analysis . . . . . . . . . . . . . . . . . . . . . . . 1036.4.1Outline of the proofs . . . . . . . . . . . . . . . . . . . 1056.5Numerical results . . . . . . . . . . . . . . . . . . . . . . . . . 1066.5.1Accuracy of performance guarantee . . . . . . . . . . . 1066.5.2Impact of the Cautiousness Parameter V. . . . . . . 1086.6Conclusion. . . . . . . . . . . . . . . . . . . . . . . . . . . . 1097Conclusions and Future Research1117.1Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1117.2Future Work. . . . . . . . . . . . . . . . . . . . . . . . . . . 1137.2.1Online Network Optimization on Traffic Steering . . . 1147.2.1.1Performance Evaluation and Comparison . . 114vii0目录05在线云资源预订与预算约束71 5.1介绍......7105.1.1之前的工作......7205.1.2我们的贡献......7305.2系统模型......7405.2.1修改对手......7505.3队列辅助在线学习算法......7605.3.1约束凸化......7705.3.2预测队列......7805.3.3漂移加惩罚加平滑用于在线学习......7805.3.4在线预订策略......7905.4性能分析......8105.4.1预测队列上界......8205.4.2约束残差......8305.4.3不后悔对抗K基准策略......8505.4.4 THOR无后悔并且可行......8805.5数值评估......8805.5.1 Google集群数据分析......8805.6结论......9106通用在线资源预订与预算约束：一个新框架93 6.1介绍......93CONTENTS7.2.1.2Which Method to Choose? . . . . . . . . . . 115Appendices117A Online Convex Optimization with Long-Term Budget Con-straints119A.1 Proof of Proposition 1 . . . . . . . . . . . . . . . . . . . . . . 119A.1.1Proof of the bound on the Constraint Residual . . . . 119A.1.1.1Proof of the Regret Bound . . . . . . . . . . 128A.1.2Upper Bound on �K−1τ=0 Q(t + τ)ˆgt+τ(xt+τ). . . . . . 130A.2 Proof of Theorem 1 . . . . . . . . . . . . . . . . . . . . . . . . 1338R´esum´e [Fran¸cais]1358.1Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1358.2Association d’Utilisateurs Distribu´ee avec des Garanties deQualit´e de Service. . . . . . . . . . . . . . . . . . . . . . . . 1378.2.1Garanties de Qualit´e de Service . . . . . . . . . . . . . 1388.2.2Formulation du probl`eme. . . . . . . . . . . . . . . . 1388.2.3R`egles d’Association d’Utilisateurs Distribu´ee . . . . . 1398.2.4R´esultats. . . . . . . . . . . . . . . . . . . . . . . . . 1408.2.5Publications . . . . . . . . . . . . . . . . . . . . . . . . 1418.3Association d’Utilisateurs Centralis´ee et Scalable Bas´ee sur leTransport Optimal Computationnel. . . . . . . . . . . . . . . 1428.3.1Transport Optimal R´egularis´e . . . . . . . . . . . . . . 1428.3.2Sinkhorn Algorithme . . . . . . . . . . . . . . . . . . . 1438.3.3Choix de design pour l’association d’utilisateurs. . . 1438.3.4Association d’Utilisateurs Performance d’Algorithmede Sinkhorn . . . . . . . . . . . . . . . . . . . . . . . . 1448.3.5Equilibrage Heuristique de la Charge . . . . . . . . . . 1448.3.7Publications . . . . . . . . . . . . . . . . . . . . . . . . 1468.4.2Robust User Association Maps . . . . . . . . . . . . . 1488.4.3Algorithme de Carte Robuste G´en´eralis´e . . . . . . . . 1498.4.4Approximation de Cartes Robustes . . . . . . . . . . . 1508.4.5R´esultats. . . . . . . . . . . . . . . . . . . . . . . . . 1508.4.6Publications . . . . . . . . . . . . . . . . . . . . . . . . 1528.5R´eservation en Ligne de Ressources en Nuages avec des Con-traintes Budg´etaires. . . . . . . . . . . . . . . . . . . . . . . 1538.5.1Charge de Travail sur le Cloud Non-Stationnaire . . . 1538.5.2Mod`ele de Syst`eme . . . . . . . . . . . . . . . . . . . . 153viii08.3.6 结果. . . . . . . . . . . . . . . . . . . . . . . . . 14408.4基于鲁棒优化的数据驱动用户关联. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .147 8.4.1用于移动流量预测的统计方法. . . . . . . . . . . . . . . . . . . . . . . . . . . . 147CONTENTS8.5.3Time Horizon Online Reservation . . . . . . . . . . . . 1558.5.4R´esultats de Performance . . . . . . . . . . . . . . . . 1558.5.5R´esultats Num´eriques . . . . . . . . . . . . . . . . . . 1568.5.6Publications . . . . . . . . . . . . . . . . . . . . . . . . 1578.6R´eservation G´en´erale de Ressources en Nuages en Ligne avecContraintes Budg´etaires: Un Nouveau Cadre. . . . . . . . . 1588.6.1Hypoth`eses . . . . . . . . . . . . . . . . . . . . . . . . 1588.6.1.1Regret sur K-benchmark . . . . . . . . . . . 1598.6.2Cautious Online Lagrangian Descent . . . . . . . . . . 1598.6.3Analyse des Performances . . . . . . . . . . . . . . . . 1608.6.4R´esultats Num´eriques . . . . . . . . . . . . . . . . . . 1618.6.5Publications . . . . . . . . . . . . . . . . . . . . . . . . 161ixCONTENTSxList of Figures2.1Simplified example for different association policies . . . . . .132.2Milano Data Set. (a) Overview of Milano City Grid and (b)Color map of arrival intensity per square of the grid on a busytime instance . . . . . . . . . . . . . . . . . . . . . . . . . . .222.3Constraint violation comparison between the algorithms, redmeans violation, yellow is tight, blue means below threshold.(b) and (c) are calculated for α = 1.. . . . . . . . . . . . . .232.4Average Delay and Load metric comparison per base station .242.5Service Isolation. Increasing BE arrival intensity, while notchanging VIP arrival intensity, has no effect on VIP guaranteedperformance inside the Feasibility Region. . . . . . . . . . . .253.1Devices associate to RRHs causing various load levels. . . . . . . .283.2OT studies the mass transportation cost that satisfies initial (red)and final (blue) conditions. . . . . . . . . . . . . . . . . . . . . .323.3Device association to RRHs. . . . . . . . . . . . . . . . . . . . .343.4Relative completion time (uniform traffic) . . . . . . . . . . . . .363.5Comparison of maxSINR and Optimal Transport. . . . . . . . . .384.1Representation of an association map. . . . . . . . . . . . . .454.2Traffic Prediction based on Eq.(4.3) for 3 different areas ofMilano from Monday 2/12/2013 to Friday 6/12/2013 andcomparison with the actual traffic (a) Duomo Area (b) NavigliDistrict (c) Bocconi University. . . . . . . . . . . . . . . . . .474.3Convergence on cost and violation of GRMA for differentobjectives (a) max rate (b) proportional fairness. . . . . . . .574.4Examples of User Association maps, colors and borders indi-cate areas covered by each base station. (a) MaxSINR Cells (b)robust maximum rate map (ϵ = 0.05) (c) robust proportionalfair map (ϵ = 0.05). . . . . . . . . . . . . . . . . . . . . . . . .57xi4.5Cost plot of approximate methods, robust maps are generatedfor each of the approximate methods for the delay minimiza-tion objective (α = 2), 10000 samples are generated based onthe prediction of traffic for a peak hour in the dataset, samplesare ordered by taylor approximation cost. . . . . . . . . . . .614.7Decomposition of the Bocconi area time series.. . . . . . . .664.9ACF plot of residuals. . . . . . . . . . . . . . . . . . . . . . .675.2Average cost comparison in a repeated randomly generatedinstance. Adversary uniformly selects λti ∈[0, Λti] in the courseof the experiment, while Λti is maintained between the multipleruns of the experiment. The plotted points represent the costof K(=[1,40])-slot benchmark policy, the black line is theT-slot benchmark policy and the red line is our policy. . . . .776.1Achievable bounds for K = T k, k = 0 : 1 : 0.2. . . . . . . . . . 1056.3Running averages of constraint residual and utility perfor-mance of COLD for different values of parameter V . . . . . . 108xii0图表目录04.6 左列：微基站设置，强SLA保护 ϵ = 0.001，12月2-6日(a) 违规 (c)平均系统延迟 (e) 成本。右列：2层基站设置，轻SLA保护 ϵ =0.05，12月2-6日(b) 违规 (d) 平均系统延迟 (f) 成本。. . . . . . . . . 6504.8 SARIMA(2,0,0)x(2,1,0)24的残差分布。. . 6705.1Google集群的资源利用率。资源相对于内存和CPU最高的服务器进行了标准化。每个点对应5分钟，最长测量29天。波动被描述为[1]中的不可预测。. . . . . . .. . . . . . . . . . . . . . . 7205.3不同策略的预留更新比较图。浅灰色背景是服务器实际所需资源的样本路径。从子图中我们可以看到，在CPU资源需求的非平稳情况下，FTL策略在资源预留方面明显落后，违规率远高于最大10%。对于内存，我们可以看到FTL与最佳静态相似，而我们的算法通过跟踪波动实现了更好的性能。具体数字比较请参见表5.3。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8906.2 在线广告投放示例的模拟。(a) COLD效用与1基准和T 0.9基准的比较。(b)K基准相对于T基准的相对超额损失。(c) 不同K值的K基准效用。. . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 107LIST OF FIGURES8.2Comparaison de violation de contrainte entre les algorithmes,rouge signifie violation, jaune est ´etroit, bleu signifie inf´erieurau seuil. (b) et (c) sont calcul´es pour α = 1. . . . . . . . . . . 1408.4Courbes de coˆuts pour les m´ethodes d’approximation. Lescartes robustes sont g´en´er´ees pour chaque m´ethode d’approximationpour l’objectif de minimisation du delai (α = 2).10000´echantillons sont g´en´er´es en se basant sur la pr´ediction dutrafic pour une heure de pointe de l’ensemble de donn´ees. Les´echantillons dont ordonn´es par le coˆut de l’approximationde Taylor. On observe que le coˆut pour MCEL explose ens’approchant de la queue de distribution, tandis que les autresm´ethodes restent robustes. . . . . . . . . . . . . . . . . . . . . 15008.1 不同关联策略的简化示例。. . 13708.3 MaxSINR和最优传输的比较。. . . . . . . . 14508.5左侧列：Micro基站配置，ϵ=0.001，12月2日至6日（a）违规（c）平均系统延迟（e）成本。右侧列：两级基站配置，ϵ=0.05，12月2日至6日（b）违规（d）平均系统延迟（f）成本。. . . . . . . . . . . . . . . . . . . . . 15108.6Google集群资源的整体利用率[2]。资源相对于具有最大内存和CPU的服务器进行了标准化。每个点对应5分钟，最多测量29天。波动被认为是不可预测的[1]。08.7Google集群轨迹更新策略比较图[2]。查看表8.5进行数字比较。. . . . . 15608.8K=Tk，k=0:1:0.2的可实现限制。. . . . . . . . 16108.9在线广告放置示例的模拟。（a）COLD相对于1-benchmark和T0.9-benchmark的效用比较。（b）相对于T-benchmark的K-benchmark的绝对相对损失。（c）不同K-benchmark的效用。. . . . . . . 16208.10COLD的剩余约束和使用约束的浮动平均性能，对于不同的参数V。. . . . . .. . . . . . . . . 1630xiii0图表清单0xiv0表格清单02.1模拟参数。2202.2米兰数据集的模拟结果。2403.1运行时间（毫秒）比较Sinkhorn vs LP-glpk。3404.1符号描述表。4504.2不同α目标函数的预期性能。6104.3模拟参数。6204.4鲁棒地图1 vs MaxSINR。6304.5十二月第一周微型设置的聚合结果。6304.6十二月第一周高峰流量微型设置。6404.7流量预测方法之间的比较。6805.1根据保证的CPU性能比较表。9005.2根据保证的内存性能比较表。9005.3策略比较表，ϵ=10% . . . . . . . . . . . . . . . 9006.1具有长期预算约束的OCO的现有结果。所有论文都假设ft，gt是凸的且Lipschitz连续的。（a）剩余指的是长期预算约束的违规。（b）随机Slater假设存在一个动作x�∈X，使得E[gt(x�)]<0对于所有t。（c）Slater假设存在一个动作x�∈X，使得gt(x�)<0对于所有t。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9407.1每天和整个周期的总结统计数据：(i)白天所有基站的平均延迟（即7:30至20:30之间）的平均延迟（以毫秒为单位）；(ii)所有基站的平均延迟的均方误差（MSE）与最佳延迟的均方误差；(iii)拒绝的流量占总流量的百分比。为了计算平均延迟和MSE值，将具有无限延迟的时间段排除在外。我们用粗体标出每天和整体的最低值。. . . 11408.1米兰数据集的模拟结果。14108.2 Sinkhorn与LP-glpk执行时间比较（毫秒）。. . . . 1440xv0表格目录08.3 12月第一周的流量峰值微型设置。. . . . 15008.4流量预测方法比较。. . . . 15208.5政策比较表，ϵ = 10%。. . . . 1570xvi0首字母缩略词0以下是文本中使用的首字母缩略词列表。0UA用户关联0UDN超密集网络0SINR信号干扰加噪声比0BS基站0QoS服务质量0NR新无线电0BE最佳努力0LTE长期演进0PS处理器共享0DPS歧视性处理器共享0URLLC超可靠低延迟通信0MAC介质访问控制0DCUAA分布式约束用户关联算法0OT最佳传输0C-RAN云无线接入网络0RRH远程无线电头0CoMP协调多点0RUAM鲁棒用户关联图0GRMA广义鲁棒映射算法0SLA服务层协议0xvii
我的内容管理
展开
