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

• 作者: 王征应 石冰心
• 来源期刊: 小型微型计算机系统
• 学科: 工学
• 关键词: QoS路由 NP-完全问题 有限状态机
• 年，卷（期）: 2001,（5）
• 页码范围: 573-577
• 页数: 5页
• 分类号: TP393.04
• 字数: 4732字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-1220.2001.05.017

摘要

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%,证明它是一种简单、精确、健壮的启发式算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王征应	华中理工大学电子信息工程系	8	276	4.0	8.0
2	石冰心	华中理工大学电子信息工程系	38	541	11.0	22.0