一种分布式的PCPO单播路由算法  

A Distributed QoS Unicast Routing Algorithm for PCPO Problem

作　　者：韩玲[1] 孔令山[1] 曾志民[1] 丁炜[1] 

机构地区：[1]北京邮电大学继续教育学院,北京100876

出　　处：《北京邮电大学学报》2004年第5期70-74,共5页Journal of Beijing University of Posts and Telecommunications

基　　金：教育部博士学科点专项科研基金项目(20020013011)

摘　　要：针对非确定多项式时间完备(NPC)的路径约束路径优化(PCPO)路由问题提出一种分布式算法:两向选择式探测QoS路由算法(TSQR).以PCPO中的时延约束代价优化(DCLC)问题为例,TSQR基于源节点与目的节点间的最小代价和最短时延路径,由源节点向目的节点发送2种不同的探测消息(MinCProbe1/MinDProbe1,MinCProbe2/MinDProbe2),分别对应2种不同的路由选择操作;沿途节点搜集探测消息走过路径的信息,继续沿原方向转发探测消息的同时,变异此探测消息进行变向探测;目的节点从收到的探测消息所代表的可行路由集中选择一条或多条路径.TSQR具有自然无环特性,在存储和计算开销等方面都具有优越性.仿真表明,与同类参考算法相比,TSQR具有最优的路径优化性能.TSQR (two-way selective probing QoS routing), a distributed algorithm for NPC PCPO (path-constrained path-optimization) problem is proposed. Taking example for DCLC (delay-constrained least-cost) problem that belongs to PCPO problem, according to TSQR algorithm, source node sends two kinds of probing messages (MinCProbe1/MinDProbe1, MinCProbe2/MinDProbe2) to destination node based on the minimum-cost path and the least-delay path between them, and these two kinds of probing messages correspond to two kinds of path-selection operations; the mid nodes collect the path information that a message has traversed, and mutate the message to probe in another direction while sending the message in original direction; destination node selects one or more paths from feasible paths set. TSQR can remove loop paths naturally, and has low storage and computation complexity. Simulation results show that TSQR has best path-optimization performance compared with some other referenced algorithms.

关 键 词：服务质量 路由 路径约束路径优化 时延约束代价优化 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]