最优DT路线规划

作者：大木叉叉

邮箱：destild@sina.com

摘要：无线网络的RF(Radio Frequency)优化是检测网络覆盖的重要手段，尤其是在LTE网络的单站验证、簇优化中。DT(Drive Test)路线规划是RF优化的第一步，最优DT路线可以理解为在最短测试里程的条件下遍历所有的待测道路。在大范围(市、区级别)的DT测试中，即拉网测试，路线规划是必不可少的。该类测试具有时间长、范围广、路线复杂、重复道路多等特点。基于该类问题进行研究，本文给出了最短测试路径规划的参考方案，并通过计算机算法实现路线的自动规划。

关键词：RF优化；DT测试；最优路线规划；中国邮路问题

1. RF优化与路线规划

1.1 RF优化概要

RF(Radio Frequency)优化是指对无线射频信号的优化，其目的是根据系统的实际表现对系统进行分析，并通过对网络资源和系统参数的调整，使系统性能逐步得到改善，达到系统现有配置条件下的最优服务质量。RF优化的主要目标包括：覆盖优化、容量优化以及质量优化。RF优化的基本思想：关注网络的覆盖、容量、质量等，通过覆盖调整，干扰调整，参数调整，故障处理等等各种网络优化手段达到网络动态平衡，提高网络质量，保障用户感知[1]。

RF优化的基本流程可以用如下的流程图表示：

路测可以分为DT(Drive Test)和CQT(Call Quality Test)，DT测试主要包括：覆盖是否正常、扇区有无接反、扇区方位角是否和规划一致、切换是否正常、业务是否正常等等。DT路测路线选取应该遵循如下的原则：

1)      测试路线应包含主要街道、重要地点和VIP区域；

2)      为了保证基本的优化效果，测试路线应尽量包括所有小区，并且测试路线应遍历所有小区；

3)      为了准确地比较性能变化，每次路测是最好固定相同的路测线路；

4)      重复测试路线要区分表示，在规划线路中，会不可避免的出现交叉和重复的情况，尽量减少重复测试的路线。

路测是RF优化的一个重要的组成部分，路测的第一步就是路测道路规划。

1.2路线规划

为了便于阐述，假设测试道路如图1.所示，其中所有的道路都是双向可达的，道路交叉节点用字母{A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P}表示，各相邻节点之间的距离为1个单位。对于图1.所示的交通道路，根据不同的测试需求，可以规划出不同的测试方案，如图2.所示。

图1.理想测试道路图

图2.不同测试方案的对比图

方案1依次通过的节点为： A B C D H L P O N M I E A B F J N O K G C D H G F E I J K L；方案2依次通过的节点为： A B C D H G F E I J K L P O N M I E A B F J N O K G C D H L P；方案3依次通过的节点为： A B F E A B C G F B C D H G C D H L K G H L P O K L P O N J K O N M I J N M I E F J；

在不考虑测试需求的情况下，图.2中三种不同的测试方案所花费的里程比为29：30：42，显然方案3走的重复道路是最多的，所以方案3的“代价”也是最大的。现在我们期望以最小的里程走完所有的路，即不走或者尽量少走重复路，这就是本文所研究的最小代价的路线规划问题。

2. 路线规划的数学模型

2.1 Konigsberg七桥问题

最短路线规划问题，也就是一笔画问题起源于瑞士数学家莱昂哈德·欧拉(Leonhard Euler)的Konigsberg七桥问题[2]。在所有桥只走一遍的前提下，如何才能把所有的桥走遍。七桥问题可以简化成点线模型，其中陆地用{A,B,C,D}四个点来表示，七座桥用相应的点之间的连线表示。如图3.所示：

图3.七桥问题模型

为了便于问题的阐述，首先给出图论里面的一些概念的定义。一个图(Graph) G=(V,E)由定点(vertex)的集合V和边(edge)的集合E组成。每一条边都是一副点对(v,w)，如果点对是有序的，那么图就称之为有向图。如果在一个无向图中每一个顶点到每个其他的点都存在一条路径，则称该无向图是连通的。交通图可以用一个图来模型化，每一条街道交叉口表示一个顶点，而每一条街道就表示一条边。图中的一条路径(path)是一个顶点序列w₁,w₂,w₃,...,w_n使得(w_i,w_i+1)∈E,1<i≤N，这样一条路径的长(length)是为该路径上的边数，它等于N-1。欧拉环游(Euler circuit)问题即寻找图中的一条路径，使得该路径访问图的每条边恰好一次。设无向图G(V,E)为连通图，若边E₁∈E，在图G中删除E₁得到的子图示不连通的，则称E₁是图G桥。给出了欧拉环游存在的条件。欧拉定理

1.       当图是连通的并且每个顶点的度(边的条数)是偶数。

2.       如果恰有两个顶点的度是奇数，欧拉环游从一个奇数度的顶点出发终止在另一个奇数度的顶点。

2.2 中国邮路问题

历史总是惊人的相似，早在60年代我国学者管梅谷根据实际问题的需要对于该类路线规划问题进行了研究，即著名的中国投递员问题[3]，就是：“一个投递员应该怎样选择一条路线，才能既走遍由他负责送信的所有街道，而所走的路程又最短。”该类问题的解决方案用图论的术语可以叙述为：

“设E₁是图G=(V,E)的一个边集，若把E₁中的边加入G中（作为重复边），得到的图G’所有的顶点的度均为偶次，就称E₁为一组可行解，总长度最短的可行解叫做最优解。不难看出，可行解一般可以看成是一些吧G的奇次顶点一对一对地连接起来的链。由于G’没有奇次度的顶点，即图G’存在欧拉环游。”

3. 路线规划与算法设计

根据欧拉总结的规律，对于七桥问题显然是不存在答案的。那么如何去实现最短路线走完七桥呢？联系到实际中，如果我们在路测这样的七条道路，我们如何能够尽快的走完这里的七条路，这对于现实有着很重要的指导意义。

3.1 路线规划

根据欧拉定理，规划图.1的测试路线。

第一步：构造偶数点连线

图.1中，从节点B,C,E,H,I,L,N,O出发的路线都是奇数条，把这些基数点用一条辅助道路两两连接，使图满足欧拉回路的条件。而这条虚拟的辅助道路的实际意义就是在实际行走的过程中需要重复走过的道路。这样我们就可以清晰的设计出要重复走的路，而且把重复走的路缩减到最少。根据这个基本的思路，构造如图.4的欧拉图：

图4.添加辅助道路的欧拉回路图

如图4.所示，道路Q、R、S、T是添加的辅助点及辅助道路，添加完辅助道路后的图所有的节点都是偶数节点。所以图4为Euler图且必存在Euler环游。

第二步：设计欧陆路径

添加了辅助道路的测试路径满足欧拉回路的条件，所以必定是能够构造出若干条欧拉路径的。如图5.所示。

通过图5.所给出的欧拉路径可以看出，重复走过的路线包括BC，HL，ON，IE，更为重要的是这些重复的路径是可以人为选定设计的。与图2所给出的方案相比，图4的方案重复路线是最少的，他们所花费的里程之比是28：29：30：42。

图.5 带有辅助道路的欧拉路径

3.2 算法设计

在实际的DT过程中，常常会出现道路多，路况复杂的情况。为此我们借用计算机编程辅助我们来设计Euler环游。首先建立测试道路的数学模型。以图1.的测试道路为例，该图主要由16个节点（A~P）及其之间的连线组成，构造图4的16×16的矩阵模型。其中每一行（列）分别表示某一个节点，该行（列）的数值意义为：1表示两点之间存在道路，0表示两点之间不存在道路，其中节点自身之间不存在连线。如：(E,G)=0，(K,G)=1表示节点E和G之间没有连线而节点K和G之间存在连线。

图6.测试道路的矩阵模型

参考Fleury算法[4]，编写程序来搜索Euler环游，

结果输出为：

表1.策略表

3.3 实际应用

基站发出的载波信号在空中传播过程中，由于地形、建筑物及其他一些环境因素的影响，或者受到实际建设时基站选址上的不确切性及网络运行中基站周围环境发生较大的变化的因素的影响，使得系统实际建成以后的覆盖情况发生了较大的变化。因此只有通过实地的测量才能真正了解系统的实际覆盖情况。

通过路测可以准确记录测试过程中的位置信息、事件信息、地貌信息和覆盖情况，对于基站覆盖区域有一个全面的了解。

如图7.北京市二环内主要道路分布图(二环道路图)所示，对于北京市二环内(含二环)的主干道路进行DT测试。测试要求1.走完所有的道路；2.重复测试路线尽量减少。

图7.北京市二环内主要道路分布图

对于北京市二环道路测试，为了简化模型，首先我们进行如下假设：任意存在连接的两个节点之间都是连通，且双向可达。通过程序可以得出如下策略：

通过表1.可以看出，在405步之后，可以遍历完图7.中所有的道路，重复测试的道路用红色在图7.中标出。

表2. 策略表

4.总结

在进行RF优化的过程中，遇到了最短DT测试路线规划问题。为了更加解决该类问题，同时节约测试成本提高测试效率，对于该类问题进行了深入的研究。在建立实际问题的数学模型时，才恍然发现对于该类问题前辈学者已经有了深入的研究并给出最优路线规划方案。借鉴前人的研究成果，利用现代的计算机算法，根据DT测试问题的特性，最终给出合理的解决方案。

参考文献

[1] 林世明,高志斌,高凤连,黄联芬.基于路测的TD-LTE网络优化分析[A],现代电子技术,2015,(38):12-15

[2] 高中印. 用数学建模方法解决哥尼斯堡七桥问题[J]. 河北民族师范学院学报, 2010, 30(2):14-15

[3] 管梅谷. 中国投递员问题综述[J]. Journal of Mathematical Research with Applications(数学研究与应用(英文)), 1984, 4(1):113-119.

[4] 吕义忠. 关于Fleury算法的一点注记[J]. 南京航空航天大学学报, 1998(4):470-472