运用模糊数解决非确定环境下的路由问题

Using Fuzzy Number to Solve Routing Problems on the Uncertain Condition

本文基于模糊数学的有关原理 ,论述了网络环境不确定的条件下路由问题的求解 .本文假定网络链路延迟是模糊数 ,给出了路径延迟小于端到端延迟约束的可信度的定义 ,提出了路径可信度判定 (PathReliabilityDeci sion :PRD) ,最优可信度路由 (MostOptimalReliabilityPath :MORP) ,最优路径分解 (PathOptimalPartition :POP) ,及最优分解路径 (MostOptimalPartitionPath :MOPP)等问题 .本文证明 ,PRD是多项式可解的 ,POP可以用等可信度分解实现 ,一般情况下 ,MORP和MOPP是等价的 .在所有链路延迟的宽度都相同时 ,MORP转化为约束为跳数的最短路径问题 ,因此是多项式可解的 .最后我们给出了MORP的近似算法 ,算法的时间复杂度为O(log(ε) -1(vlog(v) +e) ) .

Based on the principles of fuzzy mathematics, we describe the routing problem on the condition of the network with uncertain information. Assuming the link delay is a fuzzy number, we make the definition on the reliability that the path delay is less than the delay constraint. We also propose the notion of Path Reliability Decision (PRD), Most Optimal Reliability Path (MORP), Path Optimal Partition (POP), Most Optimal Partition Path (MOPP). We find if all the link delay have the same width, MORP or MOPP can be turned to the restricted shortest path problem whose constraint is the jump and so they are polynomial solvable. At last we give the approximate algorithm for MORP. The time complexity is 0 (log(Ε)-1 (vlog(v)+e)).