基于人工鱼群的ＡBC支持型QoS单播路由机制王兴伟 秦培玉 黄敏（东北大学信息科学与工程学院 沈阳 1１0０04）摘 要 下一代互联网NGI(Ｎeｘt Ｇenｅratｉon Internｅt)需要提供服务质量QｏS(Ｑuality of Ｓervｉｃｅ)路由能力，支持总最佳连接ABC(Always Ｂesｔ Connｅcted) .但是，由于链路状态的难以精确测量与用户ＱoＳ需求的难以准确表达,因此ＱoS路由基于的信息实际上是模糊的.同时，在网络运营日益商业化的环境下，支持ABC需要兼顾用户和网络提供方利益,考虑双方效用共赢．为此,本文引入模糊数学、概率论和博弈论知识，设计了一种ABＣ支持型QｏS单播路由机制．该机制采用区间形式描述用户QoＳ需求和边(链路)参数，引入用户满意度和边评价，通过博弈分析，基于人工鱼群算法，寻找使用户和网络提供方效用达到或接近Ｎａsh均衡下Ｐａｒetｏ最优的QoS单播路径．仿真结果表明,该机制是可行和有效的.关键词 服务质量；单播路由;总最佳连接；人工鱼群算法；Ｎaｓh均衡;Pａｒetｏ最优中图法分类号 ＴP393ＡBC Supporｔｉng QoS Unｉcａst Routｉng Schemｅ Bａsｅd on ｔhe Artｉfiｃial Fish ＳｗarｍWAＮG Xinｇ-Wei Qin Peｉ-Ｙu ＨＵANＧ Min(Cｏｌlege of Iｎｆormatiｏn Sｃience ａnｄ Ｅｎgｉneeｒing, Ｎoｒｔheａstern University, Ｓhenyａｎg 110004）Aｂstrａcｔ NGI (Next Geｎerａtion Ｉnterｎｅt) neeｄｓ to proｖide QoＳ (Ｑｕaｌｉty ｏｆ Service) roｕting aｎd support ABC （Ａlways Best connected）. Howeｖer, due ｔo the ｄiｆficuｌty on tｈe exact meaｓurｅｍent ｏf the nｅtwoｒｋ ｓｔaｔuｓ ａｎｄ the exａｃt expression of thｅ user QoS requiｒements, QｏS rouｔｉnｇ should bｅ bａsed oｎ the ｆuzzｙ infｏrmatiｏn． Meaｎwhile, with the grａdｕａｌ cｏmｍerｃiaｌiｚatｉｏn of thｅ nｅｔwork oｐｅrａtions， bｏth ｔhe ｎetwork provideｒ anｄ tｈe uｓｅr ｐｒofitｓ should be considｅｒｅd tｏ supｐort AＢC, thus tｈeir utiｌity ｗin－wiｎ should be sｕppｏrted. In this pａpｅr， by introducing tｈe kｎowｌedge of ｔhe ｆuzｚy matheｍａtiｃs, pｒｏbabｉlity ｔheｏｒy aｎd gaｍinｇ ｔheoｒy, a QoS unｉcaｓt roｕtiｎｇ ｓcheｍe wｉth ABC supported is proposed. Ｔhe prｏposed scheｍe usｅs the ranｇe to ｄeｓcｒibe the uｓeｒ ＱoS rｅqｕiremｅnt aｎｄ tｈe edｇｅ （link） pａraｍeter and introduces the user ｓａtｉsfａctｉｏn degｒee funcｔiｏn aｎｄ the edｇe ｅvａｌuation funcｔion． With the hｅlp oｆ tｈe gaminｇ anaｌｙsis aｎd based ｏn the artｉficial ｆish swaｒm algoｒithm， ｉｔ trｉeｓ tｏ finｄ ａ QoS ｕｎｉcast ｐath ｗitｈ thｅ Paｒetｏ ｏptｉmuｍ under the Nash ｅqｕilｉbrｉum on bｏth the ｎetwoｒk ｐroｖｉder utility ａnd tｈｅ user ｕｔｉｌiｔｙ achiｅved ｏｒ approａｃhed. Simuｌation reｓｕlts ｈａve shｏwn thａｔ tｈe propｏsｅd schemｅ is bｏｔh ｆeasiｂle anｄ eｆfeｃtivｅ．Kｅyｗｏrdｓ QｏS(Qualitｙ of Sｅｒviｃe）; Ｕnicast routinｇ； AＢC （Aｌwａyｓ Beｓt Cｏnnecｔｅd); Ａrtificial fish sｗarm algorithm; Nash equilibｒiuｍ； Pareto oｐtiｍum1 引言 国家自然科学基金资助项目（60673159, 70671020, 70931001, 60802023）；国家高技术研究发展计划资助项目（2007AA041201）；国家科技支撑计划资助项目（2008BAH37B03, 2008BAH37B07）；高等学校博士学科点专项科研基金资助课题(20070145017)；中央高校基本科研业务费资助（N090504003, N090504006）.王兴伟，男，1968年1月生，博士，教授，博士生导师，主要研究领域为下一代互联网、移动Internet和IP/DWDM光Internet等.E-mail：wangxw@.秦培玉，男，1985年2月生，硕士研究生，主要研究领域为QoS路由机制.黄敏，女，1968年2月生，博士，教授，博士生导师，主要研究领域为智能算法设计与优化、调度理论与方法等.近年来,随着Ｉｎｔｅrnet、多媒体内容、移动通信技术等的发展与融合，下一代互联网NGI(Next Ｇeｎｅｒation Iｎteｒnet）很可能发展成为地面网与空天网、固定网与移动网等异构多段多提供方网络融合而成的一体化网络，出现主干和接入链路多样化的局面.在通信端到端路径上，每一跳都可能存在多种不同类型链路供用户选择,从而使得在通信开始时和进行期间支持用户对NGI的总最佳连接AＢC(Alwayｓ Besｔ Coｎnected)成为可能[１]，实现服务质量QoS（Ｑuａlitｙ ｏf Ｓｅrvice)全局无缝漫游[2，3]．ABC意味着用户在任何时间和任何地点都可以获得当前最佳可用连接，通过当前最佳方式使用ＮGI,而且每当有更好的连接方式出现时就可以自适应透明切换．然而，“最佳”本身就是一个模糊概念,依赖很多因素（如用户QoS需求、愿付费用、偏爱、终端能力、接入点可用情况等）.在网络运营日益商业化的环境下，ＡBC也不是用户一厢情愿的事,需要兼顾用户和网络提供方利益,支持双方效用共赢[4]．此外,NGＩ组成部分的异构与动态、终端乃至网络移动等的影响和信息传递不可避免的时延及其不确定性等，都导致路由所依赖的链路状态信息难以精确测量.另一方面,用户QoS需求受主观因素影响较大,难以准确表达，需要体现一定柔性．这些都使AＢC支持型QoS路由变得非常复杂．受两个或两个以上加性或乘性参数约束的QoS单播路由问题是ＮP完全的[5]，需采用启发式或智能优化算法解决.在文献[5]中，设计了一种算法，先在网络拓扑中剪掉带宽不满足要求的边，而后以延迟为权值使用Dｉjksｔra算法[6]计算带宽约束最短延迟路径.在文献[7]中，设计了一种分布式启发算法,通过构造延迟和费用向量完成路由计算.在文献[８]中,基于概率论把延迟和费用整合成一个参数用于路由选择．在文献[９]中,把QoS参数分为敏感和非敏感两类,简化路由计算．在文献[1０]中,引入量化费用函数,基于Bellｍan-Ford算法[11]设计了一种路由预计算方法.在文献[12]中,设计了一种延迟受限的分布式路由算法.在文献[1３]中，设计了一种多约束源路由算法．在文献[14]中，提出了一种可在逐跳路由协议中使用的近似算法,用来寻找多加性QoＳ参数约束路径.在文献[１5]中,通过引入单一混成指标求解多约束QｏS路由．在文献[16］中,提出了两个基于贡献区域的算法求解多约束ＱoS路由．在文献[17]中，把QｏＳ指标平均和广度优先搜索相结合来求解多QoＳ约束路由.在文献［1８-２0]中，把遗传、蚁群和模拟退火这三个智能优化算法分别用于寻找QoＳ路径．在文献[21]中，引入Ｐａreｔｏ最优,设计了两可加QoS约束动态权重系数单播路由算法．在文献[２２]中，提出了一种基于概率的不精确链路信息下QｏS单播路由算法，寻找延迟与带宽受限费用最小QｏS路由．在文献[23］中,把不精确信息下带宽与延迟约束路径问题分解成带宽约束路径和延迟约束路径两个子问题，首先获得非劣解集，而后基于效用函数从中选取特定路径作为问题解.在文献［2４]中，针对不精确信息下多加性ＱoS约束路径问题，采用模糊逻辑从一组候选路径中选择符合要求的QoS路由．在文献[2５]中,提出了一种基于模糊塔的QｏＳ 单播路由算法,寻找两节点之间既满足用户QｏＳ需求又试图最大化网络提供方概率收益的路径.在文献［２６］中,提出了一种基于微观经济学的模糊QoS单播路由机制，采用启发式选路算法，使得找到的路径不仅满足用户QoS需求，而且双方在其上的效用达到或接近Ｎａsh均衡下的Pareto最优．但是，上述算法尚未从支持ABＣ的角度出发充分考虑在链路状态信息难以精确测量与用户ＱoS需求难以准确表达的情况下如何实现支持用户和网络提供方效用共赢的QoS单播路由机制．本文引入模糊数学、概率论和博弈论知识，设计了一种AＢＣ支持型ＱoＳ单播路由机制，采用区间形式描述用户ＱｏＳ需求和边（链路）参数，引入用户满意度和边评价，通过博弈分析,基于人工鱼群算法[２7],寻找使用户和网络提供方效用达到或接近Nash均衡下Ｐareto最优的QoS单播路径．仿真结果表明,该机制是可行和有效的．2 问题描述2．1 网络模型与路由请求网络建模为图,是节点集，是边集．,其间可能存在多条边．简单起见，本文把节点参数归并到边参数中．，考虑如下参数:网络提供方编号、可用带宽、延迟、出错率、带宽单位成本.用户ＱoS单播路由请求表示为 ，其元素依次代表源节点、目的节点、带宽、延迟、出错率需求区间和愿付费用上限.采用区间形式表示带宽、延迟和出错率是为了适应边（链路）参数值的难以精确测量和用户QoS需求的难以准确表达．2.2 边参数概率与用户满意度向用户提供带宽的概率与用户对在上实际得到带宽的满意度分别定义如下: (1） (２)的定义表明,越接近边可用带宽区间下限，则边越可能向用户提供此带宽；的定义表明,越接近用户带宽需求区间上限，则用户对从边实际得到的带宽越满意.设延迟取值在上均匀分布［28]，则的延迟等于的概率和用户对在上实际经历延迟的满意度分别定义如下：(3） (4)设出错率取值在上均匀分布,则的出错率等于的概率和用户对在上实际经历出错率的满意度分别定义如下:(5) （６)和的定义表明,边在延迟区间和出错率区间各点取值机会均等；和的定义表明,越接近用户延迟和出错率需求区间的下限,则用户对在边实际经历的延迟和出错率越满意．在上述定义中,,是远小于1的纯小数。
2.3边评价边评价函数表征边对用户QoS需求的适合隶属度．设用户在上实际占用带宽、实际经历延迟和实际经历出错率分别为、和，则定义、和对用户带宽、延迟和出错率需求的适合隶属度函数即边带宽、延迟和出错率评价函数、和如下：ﻩﻩﻩ (７)ﻩﻩﻩ (8) ﻩﻩ (9）上述定义表明,带宽、延迟和延迟抖动在一条边上实际取某值的概率越高，用户对在该边上取该值的满意度越大，则该边越适合满足。