度限制条件下最大概率恢复树的路由算法设计

The Design of the Routing Algorithm for the Degree-Constrained Recovery Tree with the Maximum Probability

摘要: 随着通信网络规模的日益扩大，对通信网络的可靠性提出了更高要求，因此针对提高通信效率的路径设计及其优化问题的研究具有广阔的应用前景。通信网络中存在着各种干扰因素，并且由于通信网络中节点的数据处理能力以及信息交互能力有限，所以与该节点同时进行通信的节点个数也是有限的。基于上述分析，该文章主要考虑节点容量和节点间高效通信的概率，构建点、边赋权的网络模型，并提出度限制条件下的最大概率红蓝恢复树问题，旨在最大化源点与任意汇点间的两条点不交容错路径的传输总概率。在路径优化过程中，利用耳分解和点插入法设计有效多项式算法构造出包含所需路径的最大概率红蓝恢复树，得到满足度限制的高效传输路径。最后，通过实例仿真验证了该算法能够提供通信网络中稳定且具有容错性的有效路径设计方案。

Abstract: With the increasing scale of communication network, higher requirements are put forward for the reliability of communication network. Therefore, the research on path designs and related optimi-zation problems for improving communication efficiency has broad application prospects. There are various interference factors and due to the limited data processing ability and information interac-tion ability of nodes in the communication network, the number of nodes communicating with one node at the same time is also limited. Based on the above analysis, this paper mainly considers the capacity of nodes and the probability of efficient communication between nodes, and constructs a network model with node and edge weights; then, proposes the maximum probability red/blue re-covery trees problem under degree constraints, which is aiming to maximize the total transmission probability of two node disjoint fault tolerant paths between source node and any sink node. In the process of path optimization, ear decomposition and node insertion are used to design an effective polynomial algorithm to construct a maximum probability red/blue recovery trees containing the required path, and an efficient transmission path satisfying the degree constraints is obtained. Fi-nally, the simulation results show that the algorithm can provide a stable and fault-tolerant path design scheme in the communication network.