摘要：针对节点约束型链路分离问题其分离的两条链路需要经过各自的必经点集的特点，提出了一种以遗传算法和迪杰斯特拉算法为基础的节点约束型链路分离算法。该算法通过改进的遗传算法得到较优的必经点集排列，再采用带有禁忌搜索的迪杰斯特拉最短距离算法求必经点对之间无环的最短路径，得到给定起点和终点之间的两条受必经点约束路径，保证路径内无环路、路径间重边最少。通过大量的模拟仿真实验，证明了该算法的有效性和可行性。

关键词：链路分离 遗传算法 迪杰斯特拉 禁忌搜索 无环路；

• 引言

随着通讯技术的不断发展，通讯服务类型也在不断更新，例如视频通话、在线会议等，而这些服务都需网络通讯技术支持。高速的网络传输速度，即使短暂的链路失效也会造成大量信息丢失，因此如何快速恢复网络通讯成为当下研究热点^[1-3]。

采取链路是快速恢复端到端之间通讯的一项常规举措，当主用链路因故障失效而快速切换到备用链路，便能够快速网络两端之间的路径。现基于Qos(Quality of Service)的链路分离算法已经得到较为广泛的研究，基于Qos约束的链路分离问题从具体的约束条件上可以分为加性约束、凹性约束、乘性约束等。带宽就是典型的加性约束条件，张品等人提出了在路径计算之前，将不满足凹性要求的链路删除 ^[4]。路由延迟，跳数等都属于加性约束，损失率等属于乘性约束条件，加性约束条件和乘性约束条件属于比较难处理的类型，约束条件超过两个时就是NP难问题^[5]，目前相关学者也已经提出了较好的算法用以解决这类问题^[6-7]。

然而还有一类链路分离问题还未得到充分的研究，即节点约束型链路分离问题，它要求端到端的两条链路各自经过一条不相交的必经点序列，该问题的解决可以在路由计算等相关领域得到应用。遗传算法是以达尔文生物进化论为基础提出的启发式智能搜索算法，由于遗传算法具有过程简单、较大的随机性以及较强的扩展性（容易与其他的算法结合）等优点，该算法在TSP问题^[8-9]等大规模路径搜索上有着较好的应用。迪杰斯特拉算法是经典的最短距离算法，从提出至今已经成为许多改进最短路径算法^[10]的基础。本文以遗传算法、迪杰斯特拉算法为基础提出的节点约束型链路分离算法能对上述的链路分离问题有一个较为有效的解决。

以上就是部分论文写作范文，如写好论文后想在查重的小伙伴，可以点击论文查重，然后选择相应的论文查重系统。PS：要先了解自己学校是什么检测系统！