无源光网络拓扑还原

凭借带宽使用效率高、传输距离长、铺设成本低等优点，无源光网络广泛应用 于光纤接入网，但无源光器件发生故障时定位困难，费时费力。利用网管系统记 录的数据还原无源光网络拓扑，可以提高故障处理效率，减低运维成本。 本文研究了无源光网络的拓扑还原问题。对于二级分光网络拓扑还原，本文 提出了对性能指标数据提取特征直接聚类还原拓扑、基于告警数据使用层次聚类 算法还原拓扑、基于深度度量学习还原拓扑等方法。实验结果表明，直接提取性 能指标数据中的时间序列特征进行聚类来还原网络拓扑效果较差，准确率仅略高 于随机生成拓扑结构；采用神经网络对性能指标数据进行深度度量学习效果较差， 数据集中有标签的样本少、性能指标数据中有效信息较少、神经网络调参困难等 原因导致难以将深度学习技术应用到该领域。基于告警数据的二级拓扑还原算法 利用凝聚层次聚类算法结合余弦距离，在现网存量数据上的拓扑还原准确率可达 95%。 由于缺少真实数据，本文根据光功率衰减模型设计了生成仿真数据的方法，提 出了三级等比分光结构、混存组网结构、三级不等比分光结构的拓扑还原算法，并 设计了多级聚类准确率的评价指标对拓扑还原的准确率进行评估。三种网络的拓 扑还原算法均以凝聚层次聚类算法为基础，提取性能指标数据突变时刻特征，根 据聚类过程中簇间距离的变化自适应确定聚类阈值。仿真实验结果表明本文提出 的拓扑还原算法具有一定可行性，当光网络单元数量占据网络接口总数一半以上 时，算法在理论上可以取得 90% 以上的准确率。

Passive optical network (PON) is widely used in optical fiber access networks due to its advantages of high bandwidth efficiency, long transmission distance and low con struction cost. Recovering the passive optical network topology using the data recorded by the network device improves the efficiency of troubleshooting and reduces operation and maintenance costs. In this paper, we study the problem of passive optical network topology recovery. For topology recovery of PON with 2-level uniform optical splitters, three schemes were explored: direct clustering of extracted features from Key Performance Indicator (KPI) data, hierarchical clustering algorithm based on alarm data, and deep metric learning for clustering method. Experimental results show that performance of KPI feature-based clus tering is poor, and the accuracy is only slightly higher than that of randomly generated results. It is difficult to apply deep metric learning to this problem because of few labeled samples in the dataset, less effective information in KPI data, and difficulty in neural net work parameter tuning. Alarm-data-based hierarchical clustering algorithm using cosine distance can achieve 95% accuracy on the data of real network. Because of a lack of real data, based on the optical power attenuation model, the simulated data was generated to explore the topology recovery algorithm for PON with 3-level uniform optical splitters, PON with hybrid levels optical splitters and PON with 3-level ununiform optical splitters, and designed a multi-level clustering accuracy eval uation index to evaluate the proposed algorithm. The topology recovery algorithms are all based on the hierarchical clustering algorithm, extracting the mutation features of KPI data, and adaptively determining the clustering threshold according to the change of the distance between clusters. The simulation results show that the proposed topology recov ery algorithm has certain feasibility. When the number of optical network units occupies more than half of the total number of network interfaces, the algorithm can achieve more than 90% accuracy in theory.

[1] 赵冰, 刘志民, 袁益明, 等. SoftCOM AI, 自动驾驶电信网络解决方案[J]. 电信科学, 2019, 35(4): 103-113.
[2] 华为. 品质宽带智能家宽运维，重塑智慧运营、极致体验新时代[EB/OL]. 2019. http: //www.sdnfv.org.cn/article/content/view?id=253786.
[3] 华为技术有限公司. ODN 的逻辑拓扑信息的获取方法、装置、设备和存储介质: CN110838928A[P]. 2020.02.25.
[4] 华为技术有限公司. 拓扑识别方法、装置及系统: CN111818403A[P]. 2020.10.23.
[5] 华为技术有限公司. 网络拓扑信息的获取方法、装置、设备及存储介质: CN111836134A [P]. 2020.10.27.
[6] 华为技术有限公司. 一种获取无源网络拓扑信息的方法及相关设备: CN111884832A[P]. 2020.11.03.
[7] 中兴通讯. 中兴通讯自主进化网络白皮书[EB/OL]. 2020. https://res-www.zte.com.cn/medi ares/zte/Files/PDF/white_book/202008171748.pdf?la=zh-CN.
[8] YI B, FALOUTSOS C. Fast Time Sequence Indexing for Arbitrary Lp Norms[C]//VLDB 2000, Proceedings of 26th International Conference on Very Large Data Bases, September 10-14, 2000, Cairo, Egypt. Morgan Kaufmann, 2000: 385-394.
[9] GOLAY X, KOLLIAS S, STOLL G, et al. A new correlation-based fuzzy logic clustering algorithm for FMRI[J]. Magnetic resonance in medicine, 1998, 40(2): 249-260.
[10] BERNDT D J, CLIFFORD J. Using Dynamic Time Warping to Find Patterns in Time Series[C]//Knowledge Discovery in Databases: Papers from the 1994 AAAI Workshop, Seattle, Washington, USA, July 1994. Technical Report WS-94-03. AAAI Press, 1994: 359-370.
[11] DAHLHAUS R. On the Kullback-Leibler information divergence of locally stationary processes [J]. Stochastic Processes and their Applications, 1996, 62(1): 139-168.
[12] PAPARRIZOS J, GRAVANO L. k-Shape: Efficient and Accurate Clustering of Time Series[C]// Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, Melbourne, Victoria, Australia, May 31 - June 4, 2015. ACM, 2015: 1855-1870.
[13] FAYYAD U M, REINA C, BRADLEY P S. Initialization of Iterative Refinement Clustering Algorithms[C]//Proceedings of the Fourth International Conference on Knowledge Discovery and Data Mining (KDD-98), New York City, New York, USA, August 27-31, 1998. AAAI Press, 1998: 194-198.
[14] KARYPIS G, HAN E, KUMAR V. Chameleon: Hierarchical Clustering Using Dynamic Modeling[J]. Computer, 1999, 32(8): 68-75.
[15] GUHA S, RASTOGI R, SHIM K. CURE: An Efficient Clustering Algorithm for Large Databases[C]//SIGMOD 1998, Proceedings ACM SIGMOD International Conference on Management of Data, June 2-4, 1998, Seattle, Washington, USA. ACM Press, 1998: 73-84.
[16] ZHANG T, RAMAKRISHNAN R, LIVNY M. BIRCH: An Efficient Data Clustering Method for Very Large Databases[C]//Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data, Montreal, Quebec, Canada, June 4-6, 1996. ACM Press, 1996: 103- 114.
[17] OATES T, SCHMILL M D, COHEN P R. A Method for Clustering the Experiences of a Mobile Robot that Accords with Human Judgments[C]//Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on on Innovative Applications of Artificial Intelligence, July 30 - August 3, 2000, Austin, Texas, USA. AAAI Press / The MIT Press, 2000: 846-851.
[18] ESTER M, KRIEGEL H, SANDER J, et al. A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise[C]//Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96), Portland, Oregon, USA. AAAI Press, 1996: 226-231.
[19] ANKERST M, BREUNIG M M, KRIEGEL H, et al. OPTICS: Ordering Points To Identify the Clustering Structure[C]//SIGMOD 1999, Proceedings ACM SIGMOD International Conference on Management of Data, June 1-3, 1999, Philadelphia, Pennsylvania, USA. ACM Press, 1999: 49-60.
[20] CHANDRAKALA S, SEKHAR C C. A density based method for multivariate time series clustering in kernel feature space[C]//2008 IEEE International Joint Conference on Neural Networks (IEEE World Congress on Computational Intelligence). 2008: 1885-1890.
[21] DING R, WANG Q, DANG Y, et al. YADING: Fast Clustering of Large-Scale Time Series Data [J]. Proc. VLDB Endow., 2015, 8(5): 473-484.
[22] KEOGH E J, CHAKRABARTI K, PAZZANI M J, et al. Dimensionality Reduction for Fast Similarity Search in Large Time Series Databases[J]. Knowl. Inf. Syst., 2001, 3(3): 263-286.
[23] LI Z, ZHAO Y, LIU R, et al. Robust and Rapid Clustering of KPIs for Large-Scale Anomaly Detection[C]//26th IEEE/ACM International Symposium on Quality of Service, IWQoS 2018, Banff, AB, Canada, June 4-6, 2018. IEEE, 2018: 1-10.
[24] SU Y, ZHAO Y, XIA W, et al. CoFlux: robustly correlating KPIs by fluctuations for service troubleshooting[C]//Proceedings of the International Symposium on Quality of Service, IWQoS 2019, Phoenix, AZ, USA, June 24-25, 2019. ACM, 2019: 13:1-13:10.
[25] POLLARD K S, VAN DER LAAN M J. A Method to Identify Significant Clusters in Gene Expression Data[J]. U.C. Berkeley Division of Biostatistics Working Paper Series, 2002.
[26] LI S, HONG D, WANG H. Relation Inference among Sensor Time Series in Smart Buildings with Metric Learning[C]//The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020. AAAI Press, 2020: 4683-4690.
[27] HOFFER E, AILON N. Deep Metric Learning Using Triplet Network[C]//Similarity-Based Pattern Recognition - Third International Workshop, SIMBAD 2015, Copenhagen, Denmark, October 12-14, 2015, Proceedings: volume 9370. Springer, 2015: 84-92.
[28] CHE Z, HE X, XU K, et al. DECADE: a Deep Metric Learning Model for Multivariate Time Series[C]//KDD Workshop on Mining and Learning from Time Series. 2017.
[29] PEI W, TAX D M J, VAN DER MAATEN L. Modeling Time Series Similarity with Siamese Recurrent Networks[J/OL]. CoRR, 2016, abs/1603.04713. http://arxiv.org/abs/1603.04713.
[30] CHOPRA S, HADSELL R, LECUN Y. Learning a Similarity Metric Discriminatively, with Application to Face Verification[C]//2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 2005), 20-26 June 2005, San Diego, CA, USA. IEEE Computer Society, 2005: 539-546.
[31] COSKUN H, JOSEPH TAN D, CONJETI S, et al. Human motion analysis with deep metric learning[C]//Proceedings of the European Conference on Computer Vision (ECCV). 2018: 667-683.
[32] DUDOIT S, FRIDLYAND J. Bagging to Improve the Accuracy of A Clustering Procedure[J]. Bioinform., 2003, 19(9): 1090-1099.
[33] FRED A L N. Finding Consistent Clusters in Data Partitions[C]//Multiple Classifier Systems, Second International Workshop, MCS 2001 Cambridge, UK, July 2-4, 2001, Proceedings: volume 2096. Springer, 2001: 309-318.
[34] FRED A L N, JAIN A K. Combining Multiple Clusterings Using Evidence Accumulation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005, 27(6): 835-850.
[35] STREHL A, GHOSH J. Cluster Ensembles — A Knowledge Reuse Framework for Combining Multiple Partitions[J]. J. Mach. Learn. Res., 2002, 3: 583-617.
[36] FERN X Z, BRODLEY C E. Solving cluster ensemble problems by bipartite graph partitioning [C]//BRODLEY C E. Proceedings of the Twenty-first International Conference on Machine Learning (ICML 2004), Banff, Alberta, Canada, July 4-8, 2004: volume 69. ACM, 2004.
[37] KARYPIS G, KUMAR V. A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs[J]. SIAM Journal on scientific Computing, 1998, 20(1): 359-392.
[38] NG A Y, JORDAN M I, WEISS Y. On spectral clustering: analysis and an algorithm[C]// Advances in Neural Information Processing Systems 14 [Neural Information Processing Systems: Natural and Synthetic, NIPS 2001, December 3-8, 2001, Vancouver, British Columbia, Canada]. MIT Press, 2001: 849-856.
[39] CHRIST M, BRAUN N, NEUFFER J, et al. Time Series FeatuRe Extraction on basis of Scalable Hypothesis tests (tsfresh–A Python package)[J]. Neurocomputing, 2018, 307: 72-77.
[40] MUSGRAVE K, BELONGIE S, LIM S N. PyTorch Metric Learning[A]. 2020. arXiv: 2008.09164.
[41] 薛东亮. 光网络宽带端到端判障系统的设计与实现[D/OL]. 哈尔滨理工大学, 2020. DOI: 10.27063/d.cnki.ghlgu.2020.000627.
[42] 王斐. PON 网络故障分析与维护建议[J]. 中国有线电视, 2020(11): 1279-1284. 6