资源预覆盖自动路由检索系统设计与研发*

2018-05-25喻敏

通信技术 2018年5期

喻敏

（中国移动通信集团广东有限公司中山分公司，广东中山528400）

0 引言

通信运营商全业务运营战略发展规划中，基础网络资源未来呈极快速、规模化发展趋势。基础网络资源数据管理必须更加规范化、准确化和可视化，以应对由传统业务转变为全业务运营。目前，通信运营商在进行网络和业务规划时，无法准确根据现有网络资源和目标用户分布作出最适应当前基础网络分布情况的网格化规划管理，给全业务运营工作及业务推广带来了一定影响。为提高对全业务规划的支撑，需研发出全业务网络和业务支撑应用系统，功能要实现资源预覆盖，规划移动新业务。系统可查找出待规划点与最近光交设备间的最优路由，该路由经过的传输媒介包括了管道、人手井、吊线和撑点等。在当前移动通信网络规模大、结构复杂的情况下，要实现高效的寻找最优路由，需要制定出一套高效的路由搜索算法。

1 智能算法原理

Dijkstra算法在地理信息系统（GIS）领域的所有求解最短路径算法[1]中，是最普遍的算法之一。但是，由于现行系统网络规模很大，顶点数目多，导致算法效率低下。本系统采用启发式搜索算法——A*算法，能保证最短路的搜索向终点方向进行，明显优于Dijkstra算法毫无方向的向四周搜索。

Dijkstra算法原理。首先，引进一个辅助向量，它的每个分量D表示当前所找到的从始点V到每个终点Vi的最短路径的长度。如D[3]=2表示从始点V到终点3的路径相对最小长度为2。这里强调相对，就是说在算法过程中D的值是在不断逼近最终结果，但在过程中不一定就等于最短路径长度。它的初始状态为：若从V到Vi有弧，则D为弧上的权值；否则，置D为∞。显然，长度为D[j]=Min{D|Vi∈V-S}的路径就是从V出发的长度最短的一条最短路径，此路径为(V,Vj)。那么，下一条长度次短的最短路径是哪一条呢？假设该次短路径的终点是Vk，则这条路径或者是(V,Vk)，或者是(V,Vj,Vk)。它的长度或者是从V到Vk的弧上的权值，或者是D[j]和从Vj到Vk的弧上的权值之和。一般情况下，假设S为已求得最短路径的终点的集合，则可证明下一条最短路径（设其终点为X）或者是弧(V,X)，或者是中间只经过S中的顶点而最后到达顶点X的路径。因此，下一条长度次短的最短路径的长度必是D[j]=Min{D|Vi∈V}。其中，D或者是弧(V,Vj)上的权值，或者是D[k](Vk∈S)和弧(Vk,Vi)上的权值之和。

Dijkstra算法描述：

（1）arcs表示弧上的权值。若不存在，则置arcs为∞。S为已找到从V出发的最短路径的终点的集合，初始状态为空集。那么，从V出发到图上其余各顶点Vi可能达到的最短路径长度的初值为D=arcs[Locate Vex(G,V),i](vi∈ v2)；

（2）选择Vj，使得D[j]=Min{D|Vi∈S}；

（3）修改从V出发到集合V-S上任一顶点Vk可达的最短路径长度。

Dijkstra算法是无方向的向四周搜索，针对移动通信网络规模大的情况，如采用以上经典Dijkstra算法用于搜索资源预覆盖路由，将无法保证搜索效率。考虑到移动通信传输网络中可以根据资源经纬坐标估算各点的距离值，即可估算到某一点到目标点的距离，因此本系统考虑用改进A*算法进行路由搜索。

A*算法描述如下：A*（A-Star）算法是一种静态网络中求解最短路最有效的方法[2]。公式表示为 f ( n )= g (n )+ h(n)，其中 f ( n)是从初始点经由

节点n到目标点的估价函数， g ( n)是在状态空间中从初始节点到n节点的实际代价， h ( n)是从n到目标节点最佳路径的估计代价。

保证找到最短路径（最优解的）条件，关键在于估价函数 h ( n)的选取。估价值 h ( n)≤ n 到目标节点的距离实际值，这种情况下搜索的点数多，搜索范围大，效率低，但能得到最优解。如果估价值大于实际值，搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。

对于几何网络来说，可以取两节点间欧几理德距离（直线距离）做为估价值，即：

这样估价函数f在g值一定的情况下，或多或少会受估价值h的制约。节点距目标点近，h值小，f值相对就小，能保证最短路的搜索向终点方向进行，明显优于Dijstra算法毫无方向地向四周搜索。

搜索过程伪代码如下：

创建两个表，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点；

计算起点的估价值；

将起点放入OPEN表；

while(OPEN!=NULL)

{

从OPEN表中取估价值f最小的节点n;

if(n节点==目标节点){

break;

}

for(当前节点n的每个子节点X)

{

算X的估价值;

if(X in OPEN)

{

if(X的估价值小于OPEN表的估价值){

把n设置为X的父亲;

更新OPEN表中的估价值;//取最小路径的估价值

}

if(X inCLOSE){

if(X的估价值小于CLOSE表的估价值){

把X设置为X的父亲;

更新CLOSE表中的估价值;

把X节点放入OPEN//取最小路径的估价值}

if(X not inboth){

n设置为X的父亲;

求X的估价值;

并将X插入OPEN表中;//还没有排序

}

}//end for

将n节点插入CLOSE表中;

按照估价值将OPEN表中的节点排序;//实际上是比较OPEN表内节点f的大小，从最小路径的节点向下进行。

}//end while(OPEN!=NULL)

保存路径，即从终点开始，每个节点沿着父节点移动直至起点。

2 系统设计与实现

资源预先覆盖所在的应用系统属于典型的B/S体系结构，如图1所示。

图1 系统架构

针对资源预覆盖这种实际应用，网络环境是典型的静态环境，网络结构为“管井-管道段-管井”或“撑点-吊线段-撑点”这种点-线结构。因此，采用A*算法非常适合。

其中，网络各资源信息存储在数据库的多个数据表中。从数据库表中可获取各个资源的经纬度坐标、管道/吊线长度等组成网络的各环节基本信息。但是，这些数据都处于松耦合存储状态，不能直接用于执行路由算法。因此，需要从编写接口函数获取各资源的基本信息情况用于算法执行：

Double GetDistance()//此接口用于计算指定两点经纬度坐标间的距离，需要根据GIS地理信息模型，按照标准公式计算两经纬度间的距离，可直接利用GIS平台的相关接口计算

List

Double GetLineLength()//获取指定管道段/吊线段的长度，这是资源的基本属性，可直接获取

以上接口内部实现基本原理，是通过SQL语句对数据库表进行查询，并根据各库表间的主外键关系进行整合查询得出，此处不展开描述。

当准备好以上接口后，按照如下应用A*算法：

f ( n)为起始点到目标光交设施的最短距离，

g ( n)为起始点经由管井或撑点n到目标光交设施的估价函数。这里，直接通过GetDistance计算两点间的距离为估价值。

h( n)是从管井或撑点n到目标光交接设施的最佳路径的估计代价。

程序按照以上伪代码进行展开运行，从而完成此模块的设计。模块运行情况如表1所示。

表1 模块运行情况

根据以上运算结果可以看出，执行效果并不让人满意，执行情况不够稳定，算法应用仍需改进。

经过对原有算法程序的分析研究发现，存在如下问题：

（1）GetDistance()、GetNextNodes() 和GetLineLength()等函数接口，均需要实时读取数据库中的资源信息来整合这些基本数据。整个算法执行下来需重复多次执行这些函数，每次都需进行数据库访问，效率很低；

（2）GetDistance是通过GIS地理模型计算两经纬度间的距离，计算过程需要调用GIS平台的应用服务，因此也较耗时。

以上两点为导致算法执行效率低下的原因，因此作如下改进：

（1）在执行算法前，预先把半径1 000 m范围内的所有资源一次读取出来，在内存中形成一份资源数据。当需要获取资源属性或计算资源距离时，直接从内存中读取。如果在内存中找不到对应的数据，再考虑从数据库中读取。这样改进可减少大量重复读取数据库的操作。

（2）考虑到做资源预覆盖时要搜索的范围主要都在半径1 000 m内，在这种局部范围内，空间地理坐标可近似看作平面坐标，因此该函数采取两点间欧几理德距离（直线距离）做为计算估价值。

经过以上改进后，再次运行后的结果如表2所示。

表2 改进后的运行结果

分析以上运行结果发现，本次算法改良很成功。无论起始和目标点远近与否，计算时间均稳定在7～8 s，计算得到的结果也均符合要求。因此，算法在移动资源预覆盖的自动路由应用中获得了成功。

3 系统功能验证

资源预覆盖用于业务人员开通业务时的资源预判断，以即将开通业务的地方为中心，查找指定范围内的接入设备（分光器设备、光交接箱），并将搜索结果按距离进行排序，用户选择距离适合的分光器设备、光交接箱后，系统将会生成推荐的最短路由走向。

点击“资源分析—500 m预覆盖分析”，点击“自选圆心”，然后在地图上面点击一个点，会自动获取X、Y坐标。然后，将搜索出附近的资源，并在下面的列表中显示出来，如图2所示。图2中圈圈的位置有人样的位置，代表圆心的位置。

图2 资源搜索

而此处的搜索资源只有一处，双击列表上面的资源。资源的位置就在500 m范围的区域内高亮显示出来，如图3所示。图3中圈圈的地方就是资源高亮显示的位置。

双击查询列表上面的一项资源，就可以定位到该项资源的路由信息，路由的走向如图4所示。

4 结语

本文通过对Dijkstra和A*算法的对比，选用了搜索效率更高的A*算法，并在应用算法时作出了改进。改进算法后的系统可查找出待规划点与最近光交设备间的最优路由，而该路由经过的传输媒介包括了管道、人手井、吊线和撑点等。在移动通信网络规模大、结构复杂的情况下，该系统实现了高效的寻找最优路由。经过系统使用验证，最终证明了该设计是成功可行的。