基于路径搜索算法的通信业务优化研究

陈郁乔

【摘要】 随着光纤逐步成为传输业务的主要载体，越来越多的接入业务基于光路通道开放，由于通信网络资源有限，业务扩张带来的压力与日俱增，如何通过有效的方法，对现网业务进行调整优化，实现更好的市场效应，成为通信维护管理工作的一大挑战。本文尝试引入路径搜索算法，对主干业务系统进行路径分析和优化，找到基于资源现状且面向业务最优分配的调度方案，在完成业务需求的同时，实现最佳的资源配置，并在现网中实践应用。

【关键词】 路径搜索 通信资源 业务优化

一、引言

在日常资源调度中，由于现网业务的紧迫性，需要及时根据资源情况调配业务需求。前期的调配本着快速完工形成市场效益，在资源分配上并非最优，甚至会使部分片区资源呈现不合理的紧缺。随着网络规模扩大和建设拓展，维护管理中亟需对业务合理优化，释放紧缺资源，优化网络架构。

随着数年来资源数据信息化的建设，已经实现了资源数据的平台化。在实际分配过程中，不同的需求部门对业务分配方式有各自的侧重关注点，如市场部门关注业务覆盖范围，即资源的可达性；网络线条关注资源的提供和承载能力；业务维护部门关注开通和维护的便利性；建设部门关注建设和当前需求的均衡性等。此外，还有业务的稳定性、后期的扩容性等等。

基于这种全局化的资源分配需求，以及对后续拓展进行网络优化工作的探索，必须有能够兼顾各方面需求的算法来进行资源调配，本文将针对线路资源数据的特点，采用搜索规划的算法解决优化问题。这种算法能够就对一定规模的网络节点和线段进行分析，寻求具备合理性的最佳业务路线。

二、业务模型概述

当前网络基本建立在划分城区而成的网格上，每个规划的网格中都存在相应的业务侧设备，并通过中继段连通至接入侧设备。为了便于简化模型，假定在一个较小的片区中进行传输业务规划，在整个业务的流向中，数据从源端设备到宿端设备所经过的承载载体进行遍历，不难发现业务的走向是经由“始端设备→交接设施→中继段→交接设施→…→交接设施→中继段→末端设备”这种点线交替的形式。剔除首末端固定的设备，该路径是由“点-线”间插交替的路径模型。

针对该业务模型，可定义拟定优化方向的判定标准：①总体和当前业务覆盖能力，②交接设施成端的比率，③局向纤芯使用率。

为简化模型计算的呈现，对运算变量统一标识，表述基础数据如下：

交接设施点集（m为总节点数）：S={S1，S2，S3，…，Sm}

中继段集（n为总线段数）：L={L1，L2，L3，…，Ln}

中继段长度集：Len={Len1，Len2，Len3，…，Lenn}

中继段纤芯占用率：Ф={Ф1，Ф2，Ф3，…，Фn}

中继段纤芯数：n={n1，n2，n3，…，nn}

vik代表规划路径所经交接设施，第i条可达路径的第k个跳接点。有vik∈S。

lik代表规划路径经中继线段，第i条可达路径的第k条线段。有lik∈L。

lenik代表第i条可达路径的第k条线段的长度，有lenik∈Len。

所有规划出的路径集合（Trace Route）：

TRi= （1）

如上，则第i条可达业务路径的跳接次数为Ni，vi0=v0，viNi+1=vd。

假定某次业务优化路径数量为，全程功率损耗为λi dB，单位线长的损耗为λadB，跳接点的熔接损耗为λbdB，全程可供的最大损耗为λT，则可以得出每条规划路径的全程损耗为：

λi=∑Leni ×λa +Ni ×λb≤λT （2）

对于第i条规划业务路径自至的跳接次数Ni，假定有序集合TRi中的元素个数为Ri（Ri=CardiTRi），则：

Ni=（Ri-1）/2-1 （3）

在整个业务路径规划中，路径损耗是业务开通的关键因素，路径损耗必须在业务要求的功率范围内满足，且取最小。损耗主要包括光路中的单位损耗和跳接点的接续损耗。而跳接点的数量也会在现场布线操作时产生人工消耗和业务不稳定因素，所以确定路径规划的两个基本约束条件为：a. 损耗最小，b. 跳接点最少。

由此，该模型可转变为：在有限的跳接次数以内，使得功率损耗最小的路径，即目标函数为：

MINTRi U（Ni，λi）≤λT （4）

其中U（Ni，λi）为以目标优先的二元目标函数集，也就是说在满足最少跳接次数Ni的前提下使得λi可控且最优的方案集合。

从函数的性质上看，应该有■U/■Ni>0，■U/■λi>0。从目标优先的次序看，有■U/■Ni>>■U/■λi。

规划路径的节点集：

PA={P1，P2，P3，…，PNi} （5）

规划路径的线路集：

QA={Q1，Q2，Q3，…，QNi+1} （6）

路径损耗：

n'

根据上述推演，求解式（1）-（7）所形成基本约束条件。

三、算法求解思路

根据上述算法，拟定求解思路如下：

（1）根据业务点坐标确认覆盖该业务范围的业务设施位置，拟定为通路起点P1，确认设施P1的业务提供能力；（2）从所选择业务点坐标确认覆盖范围内是否含有末梢光交接设施，得出最近直线距离内交接设施点坐标，拟为路径终点PNi；（3）分别从P1、PNi点出发，对比各中继段所能到达的交接设施，追溯由P1至PNi的可达路径，通过比较跳接次数和全程功率损耗来确定最优路径；（4）从搜索算法来看，需设定多个路线集和点集，运算量会随网络规模和跳接次数的增加成级数增长，为节约算法复杂度和计算成本，需考虑限定措施。

具体算法设计如下：

A. 先将起始点作为P1，假定P1到目标点PNi存在直通通路（直通缆段），则直接得出最优路径；

B. 当直通缆段不存在时，匹配经过节点P1的所有线路{QP1}和经过节点PNi的所有线路{QPNi}，确认是否存在公共节点P2，若存在，则P1-P2-PNi为所求通路路径；

C. 当{QP1}和{QPNi}中不存在公共节点P2时，将问题转换为节点P2和节点PNi之间是否存在公共节点P3的问题求解，以确定P1-P2-P3-PNi的通路路径；

D. 以此类推，考虑N次跳接的情况，逐步追溯得出结果；

E. 同步考虑功率损耗，当最短路径已超出光功率限额范围时，自动退出搜索并返回；

F. 当结果TRi存在多个时，通过对比各个结果的λi选择最优的业务规划路径。

不难看出，对业务优化的模型可以转换为对点线模型路径规划的算法演绎。受到路径规划算法复杂度的限制，算法的计算成本随着网络规模增长而加大，在本文应用的模型中，过多的跳接点会带来额外的路径损耗，而路径损耗是业务规划模型的基本约束条件，常规场景下，布线跳接次数应有限限定，因此，在算法中也可通过减少或限定计算的跳接次数（如NiMax≤5），使算法的计算成本基本可控。

四、结论

经测试算法内容通过输入测试数据圆满实现业务优化。基于自动化算法的模拟资源调配方案，可用于现网有限资源的调整，为新增业务腾出空间，同时也可推广应用到基于现网资源基础的工程预设计中，从方案初期就介入方案合理性，减少后期因资源优化带来的业务中断影响客户感知。

参 考 文 献

[1] Santanu Saha Ray. Graph Theory with Algorithms and Its Applications[M]. 北京：Springer，India，PrivateLtd，2013

[2] 王海英. 图论算法机器MATLAB实现[M]. 北京：北京航空航天大学出版社，2010