双向搜索多约束路由启发式计算方法

为提高大型通信网络中搜索满足多约束条件路由的速度,提出一种双向搜索路由的计算方法.首先从源和目的节点同时出发,计算到达各中间节点的可达路径.然后在各可达路径中进行路径的筛选.可达路径是采用邻接矩阵变换方式获得的,筛选路径是根据非线性开销函数,采用启发方式择优选取.当两方向搜索的节点数累计达到n-2后,对接合并两方向到达中间节点的路径,从中再选择最佳路径作为路由输出.通过算例详细介绍了可达路径计算及启发式选优方法.阐述了算法的正确性及特点,分析了最大时间杂性.通过仿真实验评估,不仅更进一步验证了新算法的正确性,而且表明新算法在搜索路由速度上要优于其他算法.

Heuristic computing method of bidirectional searching routing with multiple restrictions

In order to improve the speed of searching routing with multiple restrictions over the large communication network,a computing method for bidirectional searching routing is proposed. Starting from the source node and the target node,the reachable paths to middle nodes are calculated and filtered,respectively. The reachable paths are obtained by converting the adjacent matrix,whereas the filter paths are heuristically selected based on non-linear cost function. After the total number of bidirectional searched nodes reaches n-2,the paths in two directions are jointed and combined,from which the optimal path is chosen as an output path. The calculation of reachable paths and the heuristic method of optimal selection are introduced by examples. Their validity and characteristic are discussed,and the maximum time complexity is analyzed. Evaluation of emulation experiments validates the validity of the proposed algorithm and it is indicated that the time consuming in searching routing using this proposed algorithm is shorter than that using other methods.