基于遗传算法的求解时延约束的选播QoS路由算法

选播是一种新型的网络服务,它使用户通过一个选播地址就能访问到该地址所表示的一组服务器,并且对用户来说是“最近”的一个。实时性要求较高的业务传输过程中,保证信息传输时延尽可能小是非常重要的。本文研究有时延约束的选播QoS路由问题,提出一种改进的遗传算法以求解该问题。仿真实验表明,该算法是有效且切实可行的。

一种满足带宽和时延约束的选播QoS路由算法

建立一个满足带宽和时延约束的选播通信服务模型,提出相应的选播QoS路由算法。仿真实验结果表明:该算法是有效且切实可行的,它能同时满足带宽和时延的约束条件,较好地平衡网络负载,改善了网络服务质量。

移动无线传感网能量时延约束的自适应路由及性能评估

针对间歇性连通的移动无线传感网提出一种能量时延约束的自适应路由协议(EDCA),EDCA由初始化阶段、转发决策阶段、转发阶段和等待阶段组成,传感器节点根据目标时延实时判断是否转发副本,并选择剩余能量多的节点进行副本转发.EDCA对平均时延和网络负载具有控制力,对网络环境变化具有自适应能力,能够有效延长网络生命周期.

带时延约束的FPGA布线算法

基于ＳＲＡＭ 编程结构的门海型ＦＰＧＡ 连线上的时延较之ＡＳＩＣ来说比较大，连线延迟不可预测．在很多应用中必须对关键路径的时延加以定量限制（包括上限、下限和一组路径的时延差）．时延约束的实现需要布图算法来保证．一般时延驱动的布线算法只能定性地优化时延性能，不能满足定量要求．本文提出了高性能ＦＰＧＡ 最短路径布线算法，以它为主体的ＦＰＧＡ 布线器能全面地考虑各种时延约束，更好地利用布线资源，对其它无时延约束的线网也可进行时延优化。

基于负载均衡与时延约束的AODV协议

为了降低无线网格网(Wireless mesh network,WMN)中节点间的端到端传输时延,该文提出了一种改进的基于负载均衡与时延约束的自组织网络按需距离矢量路由协议(Enhancedrouting protocol on ad hoc on-demand distance vector(AODV)with load balance and delay restriction,BD_AODV)。BD_AODV要求源节点在进行路由请求时,包含对传输时延的要求和节点的负载信息,选择满足传输时延要求的节点转发路由请求至目的节点,目的节点搜集并将每条链路的平均负载反馈给源节点,使其能够据此选择合适的传输路由。网络模拟软件仿真实验表明,BD_AODV有助于保持网络的负载均衡,缩短端到端的传输时延,减少数据包丢失,提高无线网格网的服务质量。

一种基于带宽和时延约束的分布式组播路由算法

针对已有分布式组播路由算法在寻找QoS路由时的低成功率问题,本文提出了一种新的基于带宽和时延约束的分布式组播路由算法-QDMR(QoS-based Distributed Multicast Routing).在为新组播成员搜索连接到组播树的可行路径时,QDMR算法使用RBMF(Reverse Best Metric Forwarding)转发算法代替RPF(Reverse Path Forwarding)转发算法,从而优先搜索满足带宽和时延约束要求的路径,然后才考虑代价的优化.模拟分析表明,QDMR提高了路由搜索的成功率,并且降低了协议开销.

时延约束下的等效带宽估计

本文利用流体流方法计算了实时媒体流在缓冲区中的时延概率分布函数 ,给出了时延约束下实时媒体流的等效带宽的表达式。讨论了相关参数对等效带宽的影响。进行了仿真分析和验证。该表达式计算简单 ,便于实时带宽估计和控制。

基于MPH的时延约束Steiner树算法

为了在时延约束条件下进一步优化组播树代价,并降低算法计算复杂度,研究了时延受限的Steiner树问题.分析了MPH(minimum path heuristic)算法的计算复杂度;在此基础上设计了一个时延约束Steiner树算法DCMPH(delay-constrained MPH)用于构造时延约束最小代价组播树.该算法中每个目的结点通过与当前组播树有最小代价的路径加入组播树;若时延不满足要求,则通过合并最小时延SPT(shortest path tree)树进而产生一个满足时延约束的最小代价组播树.仿真实验表明,DCMPH算法生成的组播树在保证时延要求的情况下,与同类算法相比取得了很好的代价性能和较低的计算复杂度.

基于精确罚函数法的遗传算法求解时延约束组播路由问题

有时延约束的组播问题是通信网络多点路由优化问题中的重要部分 ,已被证明是NP complete问题 .本文提出了一种基于罚函数法的启发式遗传算法以求解该问题 ,并讨论了违反时延约束不可行解的罚函数选取问题 ,进化过程中采用适于此类问题的动态交配概率、变异概率以提高算法的收敛速度 .最后分析了算法的复杂度 .仿真表明 ,本文算法是有效的。

求解带时延约束组播路由问题的启发式遗传算法

组播是一点到多点的信息传送方式 在视频会议等实时性要求较高的组播应用中 ,保证信息的传输时延尽可能小非常重要 有时延约束的组播路由问题已被证明是NP Complete问题 研究带时延约束的组播路由问题 ,给出了一种遗传算法以求解该问题 ,算法采用了适合问题特点的遗传算子 。

一种时延约束的多共享组播树构造算法

该文提出了一种时延约束的多共享组播树构造算法,以解决多点到多点组播路由情况下单棵共享树无法满足时延约束的问题。该算法构造覆盖所有源节点和目的节点子集的多棵共享树以满足时延约束的要求,并通过减少共享树个数降低管理开销。该算法计算以每个节点为中心的共享树所能达到的目的节点的子集,将原问题转换为集合覆盖问题,并采用基于矩阵的启发式算法进行求解。仿真实验将该算法和同类算法进行比较,结果表明该算法在不增加管理开销和中心数的情况下,有效地减少了运行时间。

一种具有时延约束的组播路由算法研究

对于多媒体应用等实时组播业务而言,组播路由算法不仅要考虑优化代价,还要考虑时延约束。针对这一问题,提出一种支持动态组播的时延受限低代价组播路由启发式算法(delay-constrained multicast algorithm,DCMA)。该算法基于DDMC算法进行扩展,采用新的指示函数和链路选择函数,综合考虑了时延和代价,有效保证了组播树的性能,而且时间复杂度低,可用于实际的应用系统中。

一种带时延约束的FPGA布局算法

基于ＳＲＡＭ编程结构的ＦＰＧＡ由于编程ＭＯＳ管的导通电阻，与ＡＳＩＣ相比连线时延较大，为使电路能正常工作，很多情况下设计者必须对电路中某些路径的延迟作出限制．例如，对某些关键路径，要求时延小于某个值；或对一组路径，要求其中任意２条路径的时延差不能大于某个值．提出的一种能考虑这些时间约束条件的ＦＰＧＡ模拟退火布局算法——ＰＴＣＰ，用约束条件指导模拟退火的方向．为了提高实现约束条件的成功率和获得更优化的结果，在模拟退火过程中，不是按常规单向降低温度，而是在适当的时刻提高温度，反复退火．最后，给出了实例证明ＰＴＣＰ算法的有效性．

树上时延约束的代理服务器放置问题

该文考虑网络数据更新,需要控制代理服务器与目标服务器的距离时,树状网络上代理服务器的放置问题。利用二叉树结构和动态规划方法,得到了一个时间复杂度O(nhk)为多项式时间算法,其中n为网络结点数,k为代理服务器要放置的个数,h为树高。

一种时延约束的多点到多点组播路由启发式算法

多点到多点组播路由是组播研究领域内的一个重要问题。当单棵共享组播树不能满足时延约束时,需要建立多棵共享组播树,但同时又会增加管理开销。因此,如何尽量减少共享组播树的个数成为关键问题。本文提出了一种启发式算法DCMMHA,用来解决时延约束的多共享组播树问题(DCMSMT),该问题已被证明为NP完全问题。本文算法按照特定规则生成候选中心列表,在不违反时延约束条件下,将源节点和目的节点加入共享树,并且对已选择中心进行更新。仿真实验将DCMMHA算法同其它四种同类算法进行比较,结果表明本文的算法所获得的中心数最少,显著降低了共享树的管理开销。

基于时延约束的分布式QoS单播路由算法

提出了一种基于分布式点到点延迟受限路由的DCLC-K算法,解决了分布式QoS路由算法运行过程中历史信息最大利用问题,仿真表明,该算法在不要求中间路由器记录寻路信息和适中的消息复杂性基础上取得了良好的代价性能.

一种基于链路优化的时延约束组播路由算法

研究具有时延约束的最小代价组播路由问题,提出一种基于链路优化的组播路由算法求解该问题。算法从最小时延树开始,不断地用低代价链路代替树中高代价链路,以求得满足条件的组播树。仿真实验结果表明,该算法能根据组播应用对时延的要求,快速、有效地构造最优组播树,具有较低的时延。

一种有时延约束的动态组播路由算法

贪婪算法是一种动态组播路由算法,该算法获得的通信树时延较大。文章在改进的多标号算法基础上,提出了一种有时延约束的动态组播路由算法,可以获得满足时延约束的通信树,仿真显示该算法可以获得问题的次优解。

一种基于时延约束的社会网络信用分布优化模型

基于时延约束的影响力最大化问题(influence maximization with time-delay constraint,IMTC)定义为在时延约束条件下,选取网络中一部分初始用户,使得影响力传播过程结束后网络中被成功影响的用户数量最多.现有研究工作主要依据网络结构优化影响力传播模型,或改进启发式算法提高初始节点的选取质量,影响力传播过程中的时间延迟特性及时延约束条件往往被忽略.针对这点不足,基于时延约束的信用分布模型(credit distribution with time-delay constraint model,CDTC)综合考虑见面概率和条件激活概率对信用分配进行优化定义,同时将相邻节点之间不断见面并激活对信用分配的阻碍作用映射到传播增量路径中,最后根据信用分布函数,使用基于时延约束的贪心算法GA-TC,递归选取边际收益最大的节点组成初始节点集合.实验结果表明:在CDTC模型上使用GA-TC算法不仅能够保证初始节点的选取质量,而且具有更高的执行效率及更好的行为执行预测能力.

一种动态的时延约束费用优化多播路由算法

对动态环境下满足时延约束且费用最优的多播路由算法进行了研究。改进了一种触发重组算法,该算法根据一个区域内的节点加入或退出次数来确定对多播树的损害程度,若达到所给定平衡因子的值则触发重组。仿真表明,该算法具有较好的性能,能满足某些特殊的场合的要求。