基于选择函数的分布式启发算法DCLC-DSF

摘要

QoS路由的DCLC单播路由(Delay-Constrained Least-Cost Unicast Routing)问题属于NP-完全问题.本文提出一种多项式复杂度的分布式启发算法DCLC-DSF.DCLC-DSF基于简单的选择函数,每个网络结点只需维持本地的状态信息:相邻链路的延时和代价度量.该算法有以下优点:1)简单性;2)动态性;3)重路由功能;4)协商功能.在最坏情况下,DCLC-DSF的消息复杂度为O(e2),结点的计算复杂度为O(n2);在稳定的网络环境下,消息复杂度为O(e).此外,本文还给出DCLC-DSF算法的有限状态机模型.仿真实验表明:DCLC-DSF算法的平均代价不精确度是最佳算法的5-8%,证明它是一种简单、精确、健壮的启发式算法.