经济学、组合学、物理学和信号处理等因素共同导致设计、构建和运行高质量、经济高效的无线网络变得十分困难。与我们的手机通信的无线电收发器、支持它们的设备（如电源和有线网络）以及它们占用的物理空间都很昂贵，因此在为新收发器选择站点时必须谨慎。即使可用站点数量有限，也可以构建出指数级多的网络。例如，如果只有 50 个站点，就有 250 （超过一百万亿）种可能性！
更复杂的是，对于每个需要服务的位置，必须知道哪个收发器提供最强的信号以及信号强度。然而，在包含建筑物、山丘、树叶和其他杂波的环境中，无线电传播的物理特性极其复杂，因此准确的预测需要复杂的、计算密集型的模型。建设所有可能的站点将产生最佳的覆盖范围和容量，但即使成本不高，也会在附近的收发器之间产生不可接受的干扰。平衡这些权衡是一个核心的数学难题。
无线网络规划的目标是决定在何处放置新的收发器，以最大限度地提高覆盖范围和容量，同时最大限度地降低成本和干扰。几十年来，建立一个自动网络规划系统（又称自动规划器），以精细的分辨率快速解决全国性问题，而不损害解决方案的质量，一直是电信研究领域最重要和最困难的开放挑战之一。
为了解决这些问题，我们正在试用网络规划工具，这些工具使用从高分辨率地理数据中得出的详细几何模型构建而成，并输入由分布式计算驱动的无线电传播模型。该系统可以快速、高精度地预测信号强度。然后，我们的优化算法会智能地筛选可能的网络的指数空间，以输出一小部分候选网络，每个网络都能在成本、覆盖范围和干扰之间实现不同的理想权衡，同时确保足够的容量来满足需求。
北卡罗来纳州夏洛特的自动规划项目示例。蓝点表示选定的候选站点。热图表示来自传播引擎的信号强度。插图强调了市中心的非各向同性路径损耗。
无线电传播
无线电波在地球表面附近的传播非常复杂。就像池塘里的涟漪一样，它们会随着传播距离的增加而衰减，但它们也会穿透、反弹或绕过障碍物，从而进一步削弱信号。计算现实世界景观中的无线电波衰减（称为路径损耗）是一个混合过程，结合了传统的基于物理的计算和学习校正，以考虑杂物（例如树木和建筑物）对信号的阻碍、衍射、反射和散射。
我们开发了一个无线电传播建模引擎，它利用与 Google 地球、地图和街景相同的高分辨率地理数据来绘制植被和建筑物的 3D 分布图。在考虑信号来源、频率、广播强度等因素的同时，我们使用大量现实世界测量数据来训练信号校正模型，这些测量数据考虑了各种传播环境 - 从平坦到丘陵地形，从人口稠密的城市到人烟稀少的农村地区。
虽然这种混合方法很常见，但使用详细的地理数据可以实现低于一米分辨率的精确路径损耗预测。我们的传播引擎提供快速的点对点路径损耗计算，并通过分布式计算大规模扩展。例如，使用 1000 个 CPU 核心，仅需 1.5 小时即可以 4 米分辨率计算分布在美国大陆的 25,000 个收发器的覆盖范围。
Google Earth 中的照片级逼真 3D 模型（左上）和相应的杂波高度模型（右上）。杂波模型中从源到目的地穿过建筑物和树木的路径剖面图（底部）。灰色表示建筑物，绿色表示树木。
自动规划输入
一旦获得准确的覆盖率估计值，我们就可以利用它们来优化网络规划，例如，决定在何处放置数百个新站点以最大限度地提高网络质量。自动规划求解器使用快速、稳健、可扩展的方法解决此类大规模组合优化问题。
形式上，自动规划输入实例包含一组将提供服务的需求点（通常是方形网格）、一组候选收发器站点、从候选站点到需求点的预测信号强度（由传播模型提供）以及成本预算。每个需求点包括需求量（例如，根据无线用户数量估算），每个站点包括成本和容量。低于某个阈值的信号强度将被忽略。最后，输入可能包括总体成本预算。
大型实例的数据汇总
自动规划输入可能非常庞大，这不仅是因为候选站点的数量（数万）和需求点的数量（数十亿），还因为它需要所有附近候选站点到所有需求点的信号强度。简单的下采样是不够的，因为人口密度在给定区域内可能差异很大。因此，我们应用优先级采样等方法来缩小数据。该技术可以对原始数据进行低方差、无偏估计，保留网络流量和干扰统计数据的准确视图，并将输入数据缩小到足以使城市大小的实例适合一台机器的内存。
通过局部搜索进行多目标优化
组合优化仍然是一项艰巨的任务，因此我们创建了一个特定领域的局部搜索算法来优化网络质量。局部搜索算法范式广泛应用于解决计算困难的优化问题。此类算法通过应用小的局部变化，在候选解决方案的搜索空间中从一个解决方案移动到另一个解决方案，在时间限制或解决方案达到局部最优时停止。为了评估候选网络的质量，我们将不同的目标函数合并为一个，如下一节所述。
在处理实际网络时，达到局部最优的局部步骤数、我们每一步评估的候选移动数以及评估每个候选的时间都可能很大。为了实现在数小时（而不是数天）内完成的高质量算法，我们必须解决这些组件中的每一个。快速候选评估极大地受益于动态数据结构，该结构维护每个需求点与候选解决方案中为其提供最强信号的站点之间的映射。随着候选解决方案在局部搜索过程中的发展，我们会有效地更新此“最强信号”图。以下观察有助于限制收敛步骤数和每步评估数。
表示候选站点（左）和需求点（右）的二分图。选定的站点用红色圈出，每个需求点都分配到其最强的可用连接。最顶部的需求点没有服务，因为唯一可以到达它的站点未被选中。如果灰色边缘上的信号强度仅略低于红色边缘上的信号强度，则从顶部开始的第三和第四个需求点可能会受到严重干扰。最底部的站点拥堵严重，因为许多需求点从该站点获得服务，可能超出了其容量。
选择两个相邻的站点通常并不理想，因为它们会相互干扰。我们的算法明确禁止这样的站点对，从而引导搜索走向更好的解决方案，同时大大减少每一步考虑的移动次数。我们根据站点覆盖的需求点（以加权Jaccard 指数衡量）来确定禁用站点对。这比简单的地理距离更能捕捉它们的功能接近度，尤其是在无线电传播高度非各向同性的城市或丘陵地区。
将局部搜索分为多个时期也有帮助。第一个时期主要是增加站点以增加覆盖范围，同时避免禁用对。当我们接近成本预算时，我们开始第二个时期，其中包括在禁用对之间交换移动以微调干扰。此限制限制了每一步的候选移动数量，同时专注于那些改善干扰且对覆盖范围影响较小的移动。
三种候选局部搜索动作。红色圆圈表示选定的站点，橙色边缘表示禁用对。
输出多种优质解决方案
如前所述，自动规划必须平衡三个相互竞争的目标：最大化覆盖范围，同时最小化干扰和容量违规，但要遵守成本预算。没有单一的正确权衡，因此我们的算法通过提供具有不同重点的候选网络的小菜单，将最终决策委托给用户。我们对每个目标应用乘数并优化总和。提高某个组件的乘数会引导算法强调它。我们对乘数和预算进行网格搜索，生成大量解决方案，过滤掉所有四个组件（包括成本）上比其他解决方案更差的解决方案，最后选择一个代表不同权衡的小子集。
候选解决方案菜单，每行一个，显示指标。单击解决方案将使选定站点变为粉红色，并显示覆盖区域和需求的干扰分布图。未选择的站点为蓝色。
结论
我们描述了我们为解决电信网络运营商面临的最棘手挑战所做的努力。通过结合组合优化与地理空间和无线电传播建模，我们为无线电信网络构建了一个可扩展的自动规划器。我们正在积极探索如何扩展这些功能以最好地满足客户的需求。敬请期待！
致谢
这些技术进步得益于我们合作者的不懈努力：Aaron Archer、Serge Barbosa Da Torre、Imad Fattouch、Danny Liberty、Pishoy Maksy、Zifei Tong 和 Mat Varghese。特别感谢 Corinna Cortes、Mazin Gilbert、Rob Katcher、Michael Purdy、Bea Sebastian、Dave Vadasz、Josh Williams 和 Aaron Yonas，以及 Serge 和 Aaron Archer 对本博文的帮助。
评论