呼损率计算对步进式带宽分配性能的影响

在对电信网虚路径的带宽分配算法的研究中,罗茂松等人提出了一种单虚路径条件下的带宽分配算法,与典型的"二分法"相比,其优点是误差小,运算速度快,其缺点是运行时间起伏波动大.本文在步进式最优算法的基础上,结合计算呼叫损失概率(CBP)的单虚路径近似算法,给出步进式最优带宽分配的快速算法.此快速算法与原有步进式算法相比较,运算速度明显加快,并克服了步进式算法运行时间起伏波动大的缺点.     

一种高效的虚路径带宽分配最优算法

作者提出了一种在电信网中对虚路径的带宽进行分配的步进式最优算法．在给定网络拓扑结构、链路容量、虚路径路由以及通信量的条件下，此算法能够对虚路径的带宽进行优化分配，从而使得网络中所有(源-目的)点对的最大呼损率(Call Blocking Probability．CBP)达到最小．在每一点对之间只取一条虚路径的条件下，该文对此算法的最优性进行了证明．基于该文中给出的测试网络，作者将另一种流行的最优算法“二分法”和此算法的性能进行了对比．从实验结果中可以看到，步进式算法能给出最优的最大呼损率．速度是二分法的三倍以上，而且平均呼损率相对降低了20％以上．     

对等网端到端多路径选择建模及算法研究*

在对等网上利用多路径分发视频是一种重要的机制,虽然在一对节点之间找出符合条件的多条路径并不困难,但发送端如何从可用路径集中选出最优路径子集,并为其最优地分配发送速率仍是一个难题。为此,提出一种新的对等网端到端最优多路径选择与速率分配(OMPSRA)算法。首先,应用排队论建立OMPSRA模型,并推导出一种新的OMPSRA公式,公式既给出最优分配的计算方法,也给出路径的最优速率分配与各路径最大可用带宽之间的关系,利用此关系可选出最优路径子集。最后基于公式实现OMPSRA算法。理论分析和仿真实验结果表明提出的算法能对通信量进行全局最优分配,最小化视频传输的端到端时延,有效提高视频传输质量,比同类算法有更好的性能。     

基于人工势场法和启发式采样的最优路径收敛方法

具有渐进最优性的快速搜索随机树（RRT^*）算法在路径规划过程中确保了其概率完备性和渐进最优性,然而仍存在收敛速度慢且产生大而密集的采样空间等问题。为了加快算法的收敛速度,提出了一种基于人工势场法和启发集合采样来快速获取最优路径的方法。首先,利用人工势场法构建出一条由起点到目标点的初始路径;然后,以起点和目标点的位置和之间的距离以及初始路径的路径代价作为参数来构建初始启发采样集合;最后,限定在启发集合内进行采样,并且在算法进行的过程中调整启发采样集合的范围,进而加快路径收敛速度。仿真实验中,获取相同路径代价的路径时,所提人工势场结合启发式采样的方法为基础的结合人工势场法和启发采样策略的快速获取最优路径的RRT^*（PI-RRT^*）算法相较于RRT^*算法,采样点数减少了约67%,算法运行时间平均缩短了约74.5%;相较于启发式RRT^*（Informed-RRT^*）算法,采样点数减少了约40~50%,算法运行时间平均缩短了约62.5%。所提出的最优路径收敛方法大量减少了冗余采样次数并缩短了算法运行时间,具有更高的算法效率,收敛到最优路径的速度更快。     

CollectCast模型中活动节点的选择算法改进

主要讨论了非结构化的P2P流媒体系统中活动节点选择算法,分析了如何将路径带宽分配给各提供节点,从而为接收节点选出最优的活动节点集并提供尽可能大的带宽.指出了CollectCast模型在拓扑感知节点选择策略中存在的不足,提出多个节点共享多条路段情况下的路段带宽分配原则,并利用数学归纳法和递归法证明了按节点可用率大小顺序分配路径带宽可获得最大有效带宽,从而得出改进的活动节点选择算法.该算法使接收节点获得的有效带宽接近最大值,且复杂性较低.     

基于改进RRT-Connect算法的机械臂路径规划

针对RRT^*算法速度较慢问题,提出一种快速收敛至最优路径的最优双向快速扩展随机树(Optimal Bidirectional Rapidly-exploring Random Trees,Obi-RRT)算法。Obi-RRT使用改进的RRT-Connect算法快速得到较低成本路径,通过路径修剪得到关键点,围绕关键点提出三种采样空间并进行采样,通过不断更新关键点从而得到最优或接近最优的路径。平面和机械臂关节空间下的仿真实验表明,Obi-RRT算法运行时间仅为RRT^*算法的十分之一,并且路径成本更低。     

基于动态规划的遥感卫星数据分发策略研究

对于多遥感卫星地面站数据分发场景的多样性,针对加权平均算法在中高轨遥感数据的种类和体积增大时出现的带宽冗余快速增大的不足,提出了一种根据遥感数据的种类以及数据量大小,由地面站的传输系统动态地分发遥感数据的带宽分配算法。根据数据的时效性以及约束关系,将传输系统中的网络带宽分配问题按时间划分成若干个小阶段,利用各个阶段之间的关联性,在每个阶段都做出一个最优决策,逐个求解以此得到最优解。给出了自适应动态带宽分配算法与加权平均算法的性能对比。实验结果表明,改进算法在减小带宽冗余方面取得了良好的结果。     

无线/移动网络中基于遗传算法的带宽适应方案

无线链路带宽的快速波动推动了无线／移动网络中对适应的多媒体服务的研究．以无线网络系统的利润最大化为目标．研究适应的多媒体应用的带宽适应方案．达到利润最大化的最优带宽适应算法是一个NP-hard问题．提出一个基于遗传算法的带宽适应方案，在算法复杂度大大低于最优算法的同时，获得的利润值近似最优．性能分析和实验结果证明了这一结论．     

车辆路径问题的禁忌搜索算法研究

简要回顾了车辆路径问题的禁忌搜索算法的发展现状,提出了一种改进的禁忌搜索算法。该算法将路径问题按不同的车辆-顾客分配结构分解成若干子问题,然后用禁忌搜索算法求解每个子问题,最后从所有子问题的最优解中选出全局最优解。理论分析和实验结果表明该算法比以往的算法有以下优点：拓展了搜索空间,提高了最优解的效果;是一种将问题进行空间分解的并行算法,可采用多台计算机同时运算以减少整体运行时间。     

求解车辆路径问题的改进伊藤算法

针对车辆路径问题中选取客户节点易陷入局部最优的缺点,引入节约法并结合路径权重和距离启发因子来改进选取 客户节点的决策规则。根据粒子实际运动过程的特点和伊藤算法在迭代过程中逐步收敛的特性,结合算法的波动算子和漂移算子设计了对路径权重的更新规则,提升了算法的收敛速度。通过增大波动系数和提高环境温度来应对伊藤算法迭代过程中出现的搜索停滞、局部最优现象。引入2-opt局部优化算法来优化当前迭代取得的最优解。实验结果表明,改进后的伊藤算法有效地加快了收敛速度,提高了搜索全局最优解的能力。     

基于双维序路由策略的低能耗NoC网络分配

在片上网络(NoC)的网络分配与任务映射相配合的路径分配中,单维序路由策略会限制可行解空间。为此,提出一种基于双维序路由策略的网络分配方法。在路径分配步骤中采用双维序路由法,设计以带宽、延时和无死锁为约束条件、以降低动态及静态能耗为优化目标的遗传算法。实验结果表明,该方法可以扩大任务映射的可行解空间,求解最小所需带宽比单维序法平均减少6.3%,且在各种带宽场合时均能求得更低能耗解。     

物联网动态带宽资源分配算法及其应用

在物联网环境中,网络需要传输的数据和信息量急剧增加,从而造成带宽不足。为此,提出一种采用动态带宽资源分配算法的物联网远程机械控制方案,通过改变控制信号的采样速率,达到优化分配带宽资源的目的。仿真结果表明,在相同网络带宽条件下,该方案可降低重构信号的误差,并有效提高物联网系统智能分配带宽资源的能力。     

云环境下基于SLA的优化资源分配研究

针对云计算环境下如何高效分配资源,实现资源供应者利润最大化这一难题,提出了一种基于服务级别协议（SLA）的动态云资源分配策略。该策略通过将SLA中的计算力、网络带宽、数据存储等属性作为优化参数,构造了一种服务请求与资源的映射模型,同时设计相应的效用函数,并结合改进的与模拟退火算法相融合的混合粒子群算法（SA-PSO）,实现云环境下的优化资源分配。实验分析结果表明,基于SLA参数的SA-PSO算法具有更好的全局最优值,在给定虚拟资源相同情况下,调用该算法完成用户任务实现的利润更高。     

Bandwidth‐aware divisible task scheduling for cloud computing

Task scheduling is a fundamental issue in achieving high efficiency in cloud computing. However, it is a big challenge for efficient scheduling algorithm design and implementation (as general scheduling problem is NP‐complete). Most existing task‐scheduling methods of cloud computing only consider task resource requirements for CPU and memory, without considering bandwidth requirements. In order to obtain better performance, in this paper, we propose a bandwidth‐aware algorithm for divisible task scheduling in cloud‐computing environments. A nonlinear programming model for the divisible task‐scheduling problem under the bounded multi‐port model is presented. By solving this model, the optimized allocation scheme that determines proper number of tasks assigned to each virtual resource node is obtained. On the basis of the optimized allocation scheme, a heuristic algorithm for divisible load scheduling, called bandwidth‐aware task‐scheduling (BATS) algorithm, is proposed. The performance of algorithm is evaluated using CloudSim toolkit. Experimental result shows that, compared with the fair‐based task‐scheduling algorithm, the bandwidth‐only task‐scheduling algorithm, and the computation‐only task‐scheduling algorithm, the proposed algorithm (BATS) has better performance. Copyright © 2012 John Wiley & Sons, Ltd.     

PVM网络并行计算实现方案

使用双网卡方案实现了基于PVM平台的网络并行计算环境，并在该环境下测试了并行整体光照算法。对实际的测试结果进行了分析，讨论了利用PVM进行网络并行计算的机制和优化方法。     

基于负载均衡的无线虚拟网络映射算法

针对网络僵化的问题,目前多采用网络虚拟化（NV）方法进行解决,其关键技术是虚拟网络映射（VNE）。为解决无线VNE过程中功率和带宽资源使用不均衡的问题,基于负载均衡原理提出一种联合资源分级的无线VNE算法。首先,采用新的节点资源排序方式,其中将节点功率和平均链路带宽作为排序依据;其次,对资源进行分级,以动态调整虚拟网络请求对功率和带宽资源的需求;最后,改进功率和带宽资源的单位成本,并以最小化成本为目标函数选择资源分配方案。与原有的无线VNE算法WVNE-JBP相比,所提算法的总体接受率提高了11.7个百分点,平均功率利用率提高了4.4个百分点,平均带宽利用率提高了1.6个百分点。实验结果表明,所提算法能有效提高虚拟网络接受率和资源利用率。     

大规模通信网络带宽优化分配问题研究

提出一种大规模通信网络带宽分配的新方法．作者将大系统理论中的分解—协调方法运用于解决大规模通信网络带宽分配的优化问题，大型网络的优化问题被分解成一些互相关联的小型子网的优化问题．整个带宽优化分配问题的解决分为三个阶段：分解、协调优化及合并优化．计算结果表明，与现有算法相比，分解—协调大规模带宽管理算法(DCLPBM)既保证了很高的计算精度，又降低了时间与空间复杂度．由于算法中用到的协调机制较简单，DCLPBM易于推广到分布式计算环境，从以网络来治理网络的角度看，它具有较广的前景．     

Avoiding request–request type message-dependent deadlocks in networks-on-chips

When an application is running on a network-on-chip (NoC)-based multiprocessor system-on-chip (MPSoC), two types of deadlocks may occur: (i) the routing-dependent deadlocks, and (ii) the message-dependent deadlocks. The former type of deadlocks can be avoided by removing any cyclic paths on the application’s channel dependency graph. The message-dependent deadlocks, caused by mutual dependency of different control and/or data messages, on the other hand, are very complicated to deal with. In this paper, we focus our study on the request–request type message-dependent deadlocks which may appear in a peer-to-peer streaming system. This type of deadlocks can have devastating effects on applications using streaming protocols that often demands real-time processing over continuous data streams. We show that request–request type of deadlocks can be avoided by proper inclusion of virtual channels (VCs) for the links along the selected routing path. These VCs are not bounded to a particular communication path. Instead, they can be shared among multiple existing communication flows. In this paper, we have formally proved a sufficient condition that determines the minimum number of VCs actually needed for each link of a communication flow such that, request–request type message-dependent deadlocks can be completely avoided. Following this sufficient condition, we propose a path selection and minimum VC allocation (PSMV) algorithm to help determine the minimum number of non-uniform VCs for each link. The PSMV algorithm consists of two major steps. In the first step, we attempt to minimize the maximum number of VCs among all the links. This problem is NP-complete in nature, and it is solved using the proposed mixed integral linear programming (MILP)-based algorithm. In the second step, based on the solution suggested in the first step, the minimum number of VCs for each link is finally determined. The PSMV algorithm can literally be integrated with any existing application mapping algorithm to provide deadlock-free mapping results. One such deadlock-free mapping algorithm is suggested in this paper. Our experiments also show that, compared to an existing flow control based deadlock avoidance method (CTC) and a deadlock recovery method (DR), increase of buffers size in PSMV is within 5% compared to a baseline network configuration. The message latency of PSMV is the lowest among all three designs.     

一种改进的OPBM快速算法

在对大规模通信网络中的最优带宽分配算法(OPBM)的实现及其性能的研究过程中发现影响呼叫阻塞概率(CBP)的因素包括两部分预留带宽的影响和非预留带宽的影响,而预留带宽对CBP的影响要大过非预留带宽的影响。基于此发现,该文在OPBM方法的基础上,提出了一种改进式的OPBM算法,与原算法进行了对比,改进OPBM算法的误差很小并且运算速度加快。     

A lexicographically fair allocation of discrete bandwidth for multirate multicast traffics

Fair bandwidth allocation is an important issue in the multicast network to serve each multicast traffic at a fair rate commensurate with the receiver's capabilities and the capacity of the path of the traffic. Lexicographically fair bandwidth layer allocation problem is considered and formulated as a nonlinear integer programming problem. A nonincreasing convex function of the bandwidth layers of the virtual sessions is employed to maximize the bandwidth of each virtual session from the smallest.To solve the fairness problem a genetic algorithm (GA) is developed based on the fitness function, ranking selection and the shift crossover. Outstanding performance is obtained by the proposed GA in various multicast networks. The effectiveness of the GA becomes more powerful as the network size increases.