计算机工程与应用
計算機工程與應用
계산궤공정여응용
COMPUTER ENGINEERING AND APPLICATIONS
2011年
6期
78-81,115
,共5页
IP Mesh网络%多约束QoS路由算法%剪枝
IP Mesh網絡%多約束QoS路由算法%剪枝
IP Mesh망락%다약속QoS로유산법%전지
多约束QoS路由算法一直是研究重点和难点,是一个有待解决的NP完全问题.针对IP Mesh网络的特点,设计出相应的完全图,并且推出了n个节点的完全图路径总数目公式.提出了一种CBFS MCP算法,首先用Dijsktra最短路径算法对节点和边进行删减,将完全图简化,再在简化图上用类BFS算法通过"约束条件夹逼"和不断剪枝,寻找一条从起点s到终点t的符合两个约束条件的可行路径.实验结果表明CBFS MCP算法有着良好的算法性能.
多約束QoS路由算法一直是研究重點和難點,是一箇有待解決的NP完全問題.針對IP Mesh網絡的特點,設計齣相應的完全圖,併且推齣瞭n箇節點的完全圖路徑總數目公式.提齣瞭一種CBFS MCP算法,首先用Dijsktra最短路徑算法對節點和邊進行刪減,將完全圖簡化,再在簡化圖上用類BFS算法通過"約束條件夾逼"和不斷剪枝,尋找一條從起點s到終點t的符閤兩箇約束條件的可行路徑.實驗結果錶明CBFS MCP算法有著良好的算法性能.
다약속QoS로유산법일직시연구중점화난점,시일개유대해결적NP완전문제.침대IP Mesh망락적특점,설계출상응적완전도,병차추출료n개절점적완전도로경총수목공식.제출료일충CBFS MCP산법,수선용Dijsktra최단로경산법대절점화변진행산감,장완전도간화,재재간화도상용류BFS산법통과"약속조건협핍"화불단전지,심조일조종기점s도종점t적부합량개약속조건적가행로경.실험결과표명CBFS MCP산법유착량호적산법성능.
