多条件QoS路由选择的一个动态规划算法

第２０卷第５期　

２０１３年１０月　莆田学院学报　

Ｊｏｕｒｎａｌ　ｏｆ　Ｐｕｔ　ｉａｎ　Ｕｎｉｖｅｒｓｉｔｙ　ＶＯ１．２０　Ｎｏ．５　

Ｏｃｔ．２０１３　

文章编号：１６７２．４１４３（２０１３）０５．００５９．０４　中图分类号：ＴＰ３０１．６　

ＱｏＳ　一个动态规划算法　

吴景岚　，朱文兴ｚ　文献标识码：Ａ　

（１．闽江学院计算机科学系，福建福州３５０１０８；２．福州大学数学与计算机学院，福建福州３５０１０８）　

摘　要：研究具有可加性和可乘性参数约束的ＱｏＳ路由选择问题，以丢失率约束为例，给出了把问题的可乘性　参数约束变换为可加性约束的方法，据此给出具有丢失率约束最小时延问题的一个线性Ｏ－１规划模型。利用该　变换，对一个简单的网络拓扑，给出了该问题的一个动态规划算法，算法具有拟多项式时间复杂性。　关键词：ＱｏＳ路由选择；动态规划算法；时延；线性０－１规划；丢失率　

Ａ　Ｄｙｎａｍｉｃ　Ｐｒｏｇｒａｍｍｉｎｇ　Ａｐｐｒｏａｃｈ　ｆｏｒ　

Ｍｕｌｔｉ－ｃｏｎｓｔｒａｉｎｅｄ　ＱｏＳ　Ｒｏｕｔｉｎｇ　Ｐｒｏｂｌｅｍ　

ＷＵ　Ｊｉｎｇ—ｌａｎ　．ＺＨＵ　Ｗｅｎ－ｘｉｎｇ￣　

（１．Ｄｅｐａｒｔｍｅｎｔ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ，Ｍｉｎｊｉａｎｇ　Ｕｎｉｖｅｒｓｉｔｙ，Ｆｕｚｈｏｕ　Ｆｕｊｉａｎ　３５０　１　０８，Ｃｈｉｎａ；　２．Ｃｏｌｌｅｇｅ　ｏｆＭａｔｈｅｍａｔｉｃｓ　ａｎｄ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ，Ｆｕｚｈｏｕ　Ｕｎｉｖｅｒｓｉｔｙ，Ｆｕｚｈｏｕ　Ｆｕｊｉａｎ　３５０１０８，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：Ｔｈｅ　ＱｏＳ　ｒｏｕｔｉｎｇ　ｐｒｏｂｌｅｍ　ｗｉｔｈ　ｍｕｌｔｉｐｌｅ　ａｄｄｉｂｌｅ　ａｎｄ　ｍｕｌｔｉｐｌｉｃａｂｌｅ　ｃｏｎｓｔｒａｉｎｔｓ　ｗａｓ　ｃｏｎｓｉｄｅｒｅｄ　ｉｎ　

ｔｈｉｓ　ｐａｐｅｒ．　Ａ　ｍｅｔｈｏｄ　ｗａｓ　ｐｒｏｐｏｓｅｄ　ｔｏ　ｔｒａｎｓｆｏｒｍ　ｍｕｌｔｉｐｌｉｃａｂｌｅ　ｃｏｎｓｔｒａｉｎｔｓ　ｓｕｃｈ　ａｓ　ｌｏｓｓ　ｒａｔｅ　ｃｏｎｓｔｒａｉｎｔ　ｅｑｕｉｖａｌｅｎｔｌｙ　ｉｎｔｏ　ａｄｄｉｂｌｅ　ｃｏｎｓｔｒａｉｎｔｓ．　Ｂｙ　ｕｓｉｎｇ　ｔｈｉｓ　ｍｅｔｈｏｄ，ｔｈｅ　ｍｉｎｉｍｉｚａｔｉｏｎ　ｏｆ　ｔｉｍｅ　ｄｅｌａｙ　ｓｕｂｊｅｃｔ　ｗａｓ　ｍｏｄｅｌｅｄ　ｔｏ　ａ　ｌｏｓｓ　ｒａｔｅ　ｃｏｎｓｔｒａｉｎｔ　ｏｖｅｒ　ａ　ｓｉｍｐｌｅ　ｎｅｔｗｏｒｋ　ａｓ　ａ　ｌｉｎｅａｒ　０－１　ｐｒｏｇｒａｍｍｉｎｇ　ｐｒｏｂｌｅｍ，　ａｎｄ　ａ　ｐｓｅｕｄｏ—ｐｏｌｙｎｏｍｉａｌ　ｔｉｍｅ　ｄｙｎａｍｉｃ　ｐｒｏｇｒａｍｍｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｗａｓ　ｐｒｅｓｅｎｔｅｄ．　

Ｋｅｙ　ｗｏｒｄｓ：ＱｏＳ　ｒｏｕｔｉｎｇ；ｄｙｎａｍｉｃ　ｐｒｏｇｒａｍｍｉｎｇ；ｄｅｌａｙ；ｌｉｎｅａｒ　０－１　ｐｒｏｇｒａｍｍｉｎｇ；ｌｏｓｓ　ｒａｔｅ　

０引言　

目前的网络为了支持各种ＱｏＳ需求，在进行　

路由选择时所考虑的路由参数主要有网络路由　

的跳数和时延，网络带宽，时延抖动及丢失率等参　

数『ｌ＿３］。这些参数可以分为以下三类：１）可加性参　

数，如时延、跳数和时延抖动等；２）可乘性参数，　

如丢失率；３）取小参数，如带宽。其中带宽和时延　

是最常考虑的参数［２１。　

ＱｏＳ路由选择问题是ＮＰ完全问题。目前的　

ＱｏＳ路由选择算法一般是选取部分路由参数并构　造近似算法［２－５】，而考虑多参数条件约束的完全性　

算法则少见嘲。文［２，６］指出满足带宽要求的链路可　

以预先找出，故只须考虑可加性和可乘性参数。文　

［６］指出网络中的服务通常要求在丢失率不超过一　

个限定值的前提下求最小时延，并给出该问题的　

一个非线性０．１规划模型和完全性求解算法。该　

模型具有一般性，可以处理多个可加性和可乘性　

参数的情况，但其求解算法只能处理一个非线性　

约束，且算法每次迭代要求解一个线性０．１规划　

问题，工作量大。　

本文的基本假设同文［６］，在下一节中指出满　

收稿日期：２０１３．０９．２７　基金项目：国家自然科学基金资助项目（６１０７００２０）　作者简介：吴景岚（１９６９一），女，福建福州人，副教授，硕士；朱文兴（１９６８一），男，福建莆田人，教授，博士，博士生导师。

　６０　莆　田　学　院学　报　２０１３年１０月　

足丢失率约束的最小时延问题的可乘性约束可以　

化为可加性约束，并给出把可乘性约束变换为可　

加性约束的方法。因此满足丢失率约束的最小时　

延问题可以用线性０—１规划问题作为模型，且只　

须求解一个线性０．１规划问题即可求出问题的最　

优解。该模型具有一般性，可以处理多个可加性和　

可乘性参数以及复杂网络拓扑的情况。进一步，本　

文在第２节中对一个简单的网络拓扑给出满足丢　

失率约束的最小时延问题的一个动态规划算法，　

该算法具有拟多项式时间复杂性。　

１线性Ｏ．１规划模型　

同文［６］，考虑图１的简化的通信网络（对复　

杂的通信网络，本节的处理方法完全类似），其源　

地址Ｓ。到目的地址Ｓ　之间共有ｍ一１个结点，任　

意两个相邻结点Ｓ川和Ｓ　之间有　条通信链路，　

其中第ｉ条通信链路的时延是ｔ　丢失率是Ｐ　＝　

１，…，ｎ　。假设丢失率与时延相互独立。则只有丢　

失率约束的最小时延问题是找从源地址到目的地　

址的一条通信链路，该链路的丢失率不超过给定　

的概率Ｐ。，且时延最小。　

１１　１２　翘，ｍ　／，、／，　、＼／＿、＼、　、、　岛　Ｉ＿鱼旦　一轭丝　一　一ｆｉｔ２　＼／　＼：／　

ｎ　２＃ｈ　ｎ　ｍｎ　图ｌ通信网络图　给定一条从源地址８。到目的地址Ｓ　的通信　

链路ｌｉ。，２ｉ　，…，ｍｉ　，该链路的时延是∑ｔ　，总　

丢失率是１—１－Ｉ（１－ｐ　）。因此丢失率约束是　

１—１－Ｉ（１－ｐ帆）　（１）　

式（１）等价于　

击　

两边取对数得　

Ｉ　＝　１一　

令　ｎ去　＜－ｌｎ　

，　・ｎ　。　（２）　

于是上述问题等　价于求从源地址８。到目的地址８　的一条通信链　

路ｌｉ　，２ｉ　，…，ｍｉ　，使∑ｑ　ｇ。，且∑￡　最小。　＝Ｉ　ｋ＝ｌ　显然该问题是ＮＰ一困难的。令　

ｆ１，若信息从第ｋ一１个结点经其第ｉ条　

钆　｛　链路传输到第ｋ个结点　

【０，否则　

由于每次传输只经过一条链路，因此有∑甄　１，　＝ｌ　＝１，…，ｍ。于是满足丢失率约束的系统最小时延　

的０—１规划模型为：　

（ＩＰ）　ｍｉｎ∑∑　钆　＝ｌ　ｉ＝１　ｍ　ｎ　ｓ．【．ｔ∑∑ｑａｉ甄　＝１　ｉ＝１　ｎｋ　∑　１，　＝１，…，ｍ　

ｘｋ　∈｛０，１｝，　＝１，…，ｎ　，　＝ｌ，…，ｍ　

问题（ＩＰ）是线性０—１规划模型，可以用线性　

０—１规划中的有效方法（如分解方法等）求解　。含　

有其他可加性和可乘性约束的路由问题可作类似　

处理化为线性０—１规划问题。　ｍ　注意到问题（ＩＰ）共有　个变量，故即使对　Ｊ＝ｌ　图１的简单的通信链路，问题（ＩＰ）的规模都可能较　

大，从而导致求解时间较长『７＿。下一节对图１的网　

络拓扑，把满足丢失率约束的最小时延问题的参　

数ｑ　用有理数近似，并给出该问题的一个动态规　

划算法。　

２动态规划算法　

在图１中，若把结点８　，ｋ＝０，…，ｍ看作状　

态，每个状态ｓ　作一个决策：从链路　ｌ，　２，…，ｋｎ　

中选择一条作为通信的链路，使所选择的从Ｓ。到　

ｍ　Ｓ　的通信链路ｌｉ　，２ｉ２，…，ｍｉ　上　ｑ　≤ｇ。，且　ｋ＝１　ｍ　最小，则问题是多阶段决策问题，是实系数　ｋ＝１　背包问题的推广，其每个状态有多种选择。　

由于丢失率是概率，本身是一个近似值，故把　

上述实系数多选择背包问题的约束中的所有实系　第５期　吴景岚，等：多条件ＱｏＳ路由选择的一个动态规划算法　６１　

数口　用有理数ｑ。ｋ　近似，则丢失率约束是　证毕。　

∑　ｇ０　

不等式两边同乘一个正整数ｎ，使所有　是正　

整数，得　

∑　口　＜－ｎｑ。　

令Ｌ　ｊ是不大于ｎｑｏ的最大整数。因为　是　

正整数，故上述不等式等价于　

１　ｎｑ’ｋｔ　ｓ　ｂｎｑ０　

例设ｍ＝３，链路上各ｇ　的值为：　

ｇ¨　１ｎ　，蚴　ｌｎＴ＝击　，　

ｇ３ｌ＝ｌｎ　击　，ｇ０＝ｌｎ　

精确到小数点后２位有效数字有ｑ。。　０．１１，ｑ　

０．０７，ｑ３ｌ　Ｏ．１５，故令ｑ。ｌｌ＝０．１１，ｑ。２１＝０．０７，　ｌ＝０．１５。　

把各　乘以１００可化为整数，而ｌＯＯｑｏ￣４１．８６，　

故ＬｌＯＯｑ。　＝４１。　

命题对某条链路的丢失率Ｐ，令ｇ＝　

Ｉｎ＿Ｌ。把ｑ精确到小数点后ｋ位有效数字（ｋ－－　Ｉ　们　１）得ｑ．，并令口．＝ｌｎ＿『＝　。则有Ｉｐ—　ｌ　ｅ　０一ｌ　１　

＿－１ｌｏ一。　

证因为ｑ．是由ｑ精确到小数点后ｋ位有效　

数字得到，故Ｉｇ一口．Ｉ　丢１０一，即　

Ｉ　击　ｎ专ｌ＜　・　

也就是　

・ｎＩ器ｌ＜专　

若　墨ｐ，则有　１－ｐ≤ｅ÷。。。因为ｐ是概率，必须　

满足０　ｐ＜１，故有　

—　＜鲁　ｅ　小÷　

若　＞　，同理有　

ｐ＇－ｐ＜ｅ　一１　１　１０一　命题表明对口作有理近似大体上相当于对相　

应的丢失率作同样位数的有理近似。　

为不引入更多符号，以下不妨假设ｇ　及ｑ。　

已是正整数，并把对实系数作有理近似后得到的可　

加性约束最小时延问题称为整系数最小时延问题。　

显然，满足丢失率约束的最小时延问题有解　

的充分必要条件是：　

∑ｍｉｎ｛ｑ　ｑ　…，ｑ　）　ｑＤ　

故判断上述不等式是否成立即可判断满足丢　

失率约束的最小时延问题是否有解。不妨假设问　

题有解。　

令　＝　ｍｉｎ．ｍｉｎ　ｑ　ｋ　１，…，　ｌ　０　１，‘一，竹　令　＝｛ｋｌ，ｋ２，…，ｋｎｋ｝，　

（ｄ）＝ｍｉｎ｛∑￡　）：∑ｑ　）－＜ｄ，　）∈　，　

１　＝１，…，ｋ｝，ｋ＝１，…，ｍ　

则Ｚｍ（ｇ。）是整系数最小时延问题的最小值。　

下面给出由　一。递归计算Ｚ　的公式。　

对Ｚｌ（ｄ），当ｄ＜ｍｉｎ｛口　…，ｑ１　．｝时，Ｚ１（ｄ）不　

存在，则令Ｚ１（ｄ）＝＋∞；当ｄ－－ｍｉｎ｛ｑｌ，，…，ｇｌ　．）时，　

Ｚ１（ｄ）＝ｍｉｎ｛ｔｘ（１）：ｑｘ（１）　ｄ，Ｘ（１）∈　｝　

＝ｍｉｎ｛ｔｌｊ：ｑｔｊ￣－ｄ，Ｊ　１，２，…，　ｌ｝　

对　（ｄ），当ｄ＜∑ｍｉｎ｛ｑ；　一，　｝时，Ｚ％（　Ｊ＝１　

不存在，则令　（ｄ）＝＋∞；当ｄ　∑ｍｉｎ｛　一，　）　

时，　

（ｄ）＝ｍｉｎ｛∑　：∑　（Ｊ）－＜ｄ，　）∈　，　

１　Ｊ＝ｌ，…，ｋ｝　

＝ｍｉｎ　ｔｘ㈨＋∑　：∑　＜－ｄ—ｑｘ㈤，　

１　（ｊｆ）∈　，Ｊ　１，…，ｋ｝　

一ｉｎ　ｔｘ（￣）＋ｍｉｎｉ　ｑｘ（ｊ）￣－ｄ－ｑｘ㈦，