计算机工程与科学
計算機工程與科學
계산궤공정여과학
COMPUTER ENGINEERING & SCIENCE
2011年
9期
19-23
,共5页
熊李军%谢政%陈挚%张军
熊李軍%謝政%陳摯%張軍
웅리군%사정%진지%장군
QoS路由%路径选择%多约束条件%启发式算法%MCP
QoS路由%路徑選擇%多約束條件%啟髮式算法%MCP
QoS로유%로경선택%다약속조건%계발식산법%MCP
由于多媒体通信的需要,QoS路由技术已成为通信网络中研究的热点.通常情况下,在网络中寻找同时满足多个独立加性约束条件的路由是一个NP完全问题.本文探讨了多约束条件下的路径选择(MCP)问题,通过将MCP问题转化为离散化的动态网络,得到了一个性能更好的启发式QoS路由算法,复杂度从O(Tmn)降低为O( Tm),其中m、n分别是节点数和边数,T是算法定义的正整数,并在理论上证明了算法的正确性.最后给出实验举例,并通过与现有算法性能比较,表明改进的启发式算法能快速、有效地解决MCP问题,且适用于大规模的网络系统.
由于多媒體通信的需要,QoS路由技術已成為通信網絡中研究的熱點.通常情況下,在網絡中尋找同時滿足多箇獨立加性約束條件的路由是一箇NP完全問題.本文探討瞭多約束條件下的路徑選擇(MCP)問題,通過將MCP問題轉化為離散化的動態網絡,得到瞭一箇性能更好的啟髮式QoS路由算法,複雜度從O(Tmn)降低為O( Tm),其中m、n分彆是節點數和邊數,T是算法定義的正整數,併在理論上證明瞭算法的正確性.最後給齣實驗舉例,併通過與現有算法性能比較,錶明改進的啟髮式算法能快速、有效地解決MCP問題,且適用于大規模的網絡繫統.
유우다매체통신적수요,QoS로유기술이성위통신망락중연구적열점.통상정황하,재망락중심조동시만족다개독립가성약속조건적로유시일개NP완전문제.본문탐토료다약속조건하적로경선택(MCP)문제,통과장MCP문제전화위리산화적동태망락,득도료일개성능경호적계발식QoS로유산법,복잡도종O(Tmn)강저위O( Tm),기중m、n분별시절점수화변수,T시산법정의적정정수,병재이론상증명료산법적정학성.최후급출실험거례,병통과여현유산법성능비교,표명개진적계발식산법능쾌속、유효지해결MCP문제,차괄용우대규모적망락계통.
