基于RARA算法的绿色PON网络最小成本规划的研究

摘 要 我们计划新建一个绿色无源光网络，最大限度地减少他们的总部署成本。本文提出了一个高效率的启发叫做递归联合和迁移算法（RARA）来解决优化问题。与直观的随机划分扇形方法相比，该算法可以显著地减少PON网络部署成本。同时通过对RARA算法进行延伸，利用共享电缆管道的方法进一步降低了成本。

【关键词】PON 最小成本 划分扇形方法 RARA

随着带宽密集型的日益普及服务，如HDTV、VOD、点到点、视频会议等的应用，增加了带宽接入的需求。为了满足这一需求，接入网络正在从传统的DSL和电缆技术发展到新一代的基于光纤的接入技术。光纤从路边（FTTC），通过楼房（FTTB）和节点（FTTN），最终扩散到户（FTTH）。现在有两种主要类型的无源光纤接入网络（PON），以太无源光网络（EPON）和千兆无源光网络（GPON）。EPON是基于传统以太网技术的一种网络。一个EPON网络在上行和下行方向都能提供1Gb/s的容量，达到了20km的覆盖距离，而且支持20km的差分距离。相反，GPON是从传统的ATM PON（APON）逐渐发展起来的一个标准技术。GPON能支持更高的带宽，在上行和下行方向都能达到2.5Gb/s。它能覆盖更长的距离，达到60km，而且支持20km的差分距离。

本文考虑的是绿色PON网络部署的一般方法，一个大的网络场景容纳了好几百个ONU。我们详细地阐述了关于PON网络设计和规划的研究问题。提出了关于这个问题的数学最优化模型。由于解决最优化模型的计算复杂性高，我们也提出了一个有效的启发，叫做递归联合与迁移算法（RARA）作为不是最理想的解决方法。大量的仿真研究表明所提出的RARA方法比直接的随机切分的方法更有效。此外，在PON总部署成本中，我们评价了PON系统约束条件的影响，比如光分路比， PON最大传输距离和PON最大差分距离。

1 启发式算法

为了解决以上PON的部署问题，我们提出递归协会和迁移算法（RARA），它采用一个递归进程不断地执行ONU分配协议和分配器重置的子程序，直到发现最优（至少在本地最小）的方法。由于在所有PON的部署成本中，铺设光缆的成本是最昂贵的，它超过了整个网络部署中的其他所有成本，在这两种启发中，我们把铺设光纤的总距离作为最小化的主要目标。

1.1 递归联合和迁移算法（RARA）

递归联合和迁移算法（RARA）是从Cooper算法中延伸而来的，用于解决MLAP在后勤中的研究。图1显示了RARA的流程图。

左栏中实现了一个外循环，包括几个步骤。第一步，随机的生成一些初始的分配器，即设置初始位置。找到最佳方案，初始分配器尺寸所有的值都是从最小值到最大值之间取值。最小值等同于连接到所有ONU所需分配器的最小个数（U的绝对值），Smin=U/n的绝对值，1：n是允许的最大光分路比。Smax是ONU的总个数，它相当于每个分配器连接一个单独的ONU这样一个极端的例子。此外，为了避免陷入局部最小值，每个具体的分配器设置尺寸，必须是在Smin到Smax之间的一个值，我们随机地产生N个不同的初始分配器位置。图3中这N个分配器初始位置相当于一个从i=1到i=N的循环。总计，在研究算法中，有N（Smax-Smin+1）个初始分配器位置作为起始点。例如，如果我们设Smin=30，Smax=480，N=100，那么可以估算出总共有45100个初始位置作为起始点。

第二步，如果他们都连接到所有的ONU，验证当前的分配器的初始位置是否能够满足所有PON系统的限制，包括最大传输距离，最大差分距离，和最大光分路比。如果设置是有效的，这个算法调用一个递归进程。第三步，利用分配器的初始设置作为起始点找到最佳的分配器和他们的位置。例如，当前的初始分配可能包含100个分配器。完成递归之后，分配器的总数量可能降到80，而所有的ONU仍然能连接到相应的分配器，没有阻断PON系统的限制。

第四步，是建立在返回ONU和分配器之间协议关系和分配器设置的基础上，它需要一个PON网络规划，如果PON用这种方法部署，我们可以通过计算总成本来估计最优结果。这个成本包括在第二部分的A中所描述的所有的子成本，在第五步中将它和当前最熟悉的成本相比较。最熟悉的成本是基于一个先前最好的方案。如果新成本比当前最熟悉的成本更好，那么我们把最新的成本升为当前最好的成本并记录在当前PON网络的规划中。与此同时，如果这两个成本非常接近（预先定义在不同的范围），我们就说搜索过程是融合的，然后停止递归进程并返回到第三步。否则，我们将重复第4步和第5步直到总成本最终融合或预先定义的循环执行R次。对于后一种情况，即非融合的情况，我们进一步采用模拟退火法（SA）类似进程，最终确定一个好的方法。

2 结果与分析

在本节中，我们比较不同规划方法的性能。图2显示了方案一在最大分路比为1：16的情况下，所有ONU的总成本是怎样变化的。我们可以看到，RARA方法比随机切分方法可以达到更好的性能，如降低成本。而且，随着ONU总数的增加，RARA表现得更有效。此外，比较电缆管道共享和没有共享（MST与传统的没有MST的相比）的结果，我们可以看到电缆管道共享可以帮助我们明显的降低部署成本。在降低成本的同时，也增加了ONU的总数量。对于其他的最大分路比，我们也进行了类似的仿真，并观察到类似的结果。

为了强调RARA和电缆管道共享的重要性，我们也比较了两个极端的情况，即没有电缆管道共享的划分方法和有电缆管道共享的RARA方法（也即RARA+MST）。我们发现，对于500个网络设计，RARA方法和管道共享的结果都能带来50%的成本降低。图3和4显示了环面场景也即场景2和最大的环面场景3各自的结果。对这些小圆形场景都做类似的观察。具体来说，就是没有MST性能最差的划分方法，以及带MST而且没有PON系统限制（即允许任何最大传输距离和最大差分距离）性能最好的RARA方法。

特别是对于环形场景，Sectoring+MST方法比RARA+MST方法做得更好看起来似乎是不正常的。这是因为划分方法没有考虑PON系统的限制（包括最大传输距离和最大差分距离），而RARA方法总是考虑这些限制。为了评价RARA方法的有效性，我们也显示了没有考虑系统限制的RARA+MST的结果，明显的比Sectoring+MST方法更好。

3 总结

设计了绿色PON网络以尽量减少他们的总部署成本。提出了一个数学最优化模型，由于它的非线性和NP-完全功能，使得它是很难解决的。因此，进一步提出了一个有效的启发叫做RARA，找到一个较为理想的方法来解决这个问题。仿真研究表明，与随机划分扇形方法相比，RARA方法可以有效的减少PON部署成本。

参考文献

[1] J.Li and G.Shen，“Cost minimization planning for passive optical networks，”in Proc.OFC/NFOEC 2008，Feb 2008.

[2] G.Kramer，B.Mukherjee，and G.Pesavento，“IPACT：a dynamic protocol for an Ethernet PON （EPON），” IEEE Commun.Mag.，vol.40，no.2，pp.74-80，Feb.2002.

[3] F.Effenberger，D.C.Calix，G.Kramer，R.Li，M.Oron，and T.Pfeiffer，“An introduction to PON technologies，” IEEE Commun.Mag.，vol.45，no.3，pp.S17-S25，Mar.2007.

[4] “Ethernet in the First Mile，”IEEE 802.3ah，June，2004.

作者单位

北京铁路局北京通信段 北京市 100000