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

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