Page 36 - 网络电信2019年6月刊上
P. 36
图 2 完全随机搜索算法的流程示意 2. 最长距离优先搜索策略
不同节点配置OTDR模块，其能覆盖的光缆里程是不同的，
因此在最少化全覆盖问题中，优先考虑最长距离节点是搜索最
佳覆盖方案的方法之一。最长距离优先搜索策略是指在选择节
点时，先计算所有节点的覆盖距离量，选择覆盖距离总数最大
的节点，通过树形展开遍历该节点可覆盖的光缆，并将这部分
光缆从光缆网络中剔除，然后在剩余光缆网络中选择下一个覆
盖距离总数最大的节点，直至所有光缆均从光缆网络中剔除。
在计算所有节点的覆盖距离量时，需以每个节点作根节
点进行树形展开多层后方可获得，该步骤的复杂度即为O(md k0/
ka
)，其中k 0 是OTDR的量程公里数，k a 是光缆的平均长度，一般
k 0 /k a 的值在2~3之间。
3. 最高价值优先搜索策略
最高价值优先搜索策略是指以节点的价值量取代距离作
为节点选择的指标。即在选择节点时，先计算所有节点的价值
量，选择价值量最高的节点，通过树形展开遍历该节点可覆盖
的光缆，计算该节点的OTDR覆盖价值量，并将这部分光缆从光
缆网络中剔除，然后在剩余光缆网络中选择下一个价值量最高
以图1中的拓扑图为例说明，先随机选择一个节点如v 0 ，在
的节点，直至所有光缆均从光缆网络中剔除。最高价值优先搜
该节点配置OTDR模块，假设OTDR模块量程为100km。通过树形展
索策略倾向于优先承载重要业务的光缆，在OTDR模块数量极为
开后（如图3），可覆盖至节点v 1 和节点v 5 的光缆，因节点v 1 和
有限，无法覆盖全网的运维场景中，更利于避免重要光缆的测
节点v 5 配置有自动光交换装置，v 0 配置的OTDR模块可通过纤芯
量盲区。
的串接，继续覆盖至节点v 2 和节点v 6 ，但无法覆盖至节点v 4 的光
缆。
三、测试分析
图 3 光缆拓扑树形展开示意 本节以Matlab为仿真平台，算法以c++语言编制，对上文
所属的几种算法进行仿真分析。以个例的分析求解，剖析对比
几种算法得到的最少节点全覆盖方案。以大数量随机案例的仿
真，对比几种算法的性能。
以公式（5）~（8）表示的光缆图为示例，采用第2章的3种
算法，分别搜索出以下OTDR布置方案（见表2）。
剩余的光缆拓扑即更新为图4所示。
图 4 一次遍历后剩余未覆盖拓扑示意
68 网络电信 二零二零年六月
