一种用于无线网络中实时业务的跨层调度算法

就同时包含了有线链路和无线链路的异构网络上的实时应用,提出了一种满足其端到端服务质量(QoS)需求的无线网络MAC(media access control)层调度算法(real-time cross-layer scheduling algorithm for real-time application,简称RTCLA).该算法采用跨层的思想,结合了自适应调制编码(adaptive modulation and coding,简称AMC)技术和选择性自动请求重传(selective repeat-automatic repeat request,简称SR-ARQ)技术,在满足应用的系统误包率(packet error rate,简称PER)要求、尽可能减少基站中等待超时分组数目的前提下,提高系统吞吐性能和频谱利用率.通过仿真来验证算法分组超时率、平均系统有效吞吐率和公平性3个方面的性能,并与改进的比例公平算法(modifiedpro portional fair,简称MPF)、最早到期优先(earliest deadline first,简称EDF)和改进的最大加权延时优先(modified largest weighted delay first,简称M-LWDF)等3种广泛使用的算法进行了比较.仿真结果还表明,综合考虑实时应用的严格时延要求和无线网络资源稀缺以及信道的时变特性,RTCLA更适合于对时延敏感的实时应用,尤其是分组超时率性能方面表现突出.此外,仿真结果还表明,RTCLA在稳定性方面的表现与其他3种算法基本相同.     

基于跳数的公平性增强RED及其分类器实现

为了同时兼顾改善不同往返时延(RTT)和多拥塞链路所引发的不公平性问题,在实际网络环境测量结果的基础上,提出了利用数据包所经过的路由器跳数来增强公平性的思路,并构造了一个二维两类分类器来对REI)算法进行简单的修改,实现了一个公平性增强的REI)算法。NS2下的模拟表明,该算法可有效增强公平性,而且具有实现简单、易于在实际网络中部署的优点。     

WRR算法在多类别实时数据流调度中的优化

随着融合型网络的发展,服务质量(包括可用带宽、端到端的时延、抖动和丢包率)对一些实时数据流应用(语音流、视频流等)越来越重要。由于传统的WRR算法只能满足各个应用队列的公平性要求,而不能保证多类别实时数据的低时延和低抖动性要求,所以本文在WRR算法的基础上提出了BSTL-RR调度算法,此算法运用了二层循环和借用时隙的两个思想。BSTLRR调度算法不仅在调度低时延和低抖动的多类别实时数据流帧方面要优于WRR调度算法,而且在一定程度上也保证了各优先级队列调度上的公平性。     

基于IEEE802.11 DCF的优化竞争窗口算法

针对现有IEEE802.11分布式协调功能DCF(Distribute Coordination Function)方式下吞吐量较小、时延较大的缺点,提出了一种优化竞争窗口的算法。该算法通过增加最小竞争窗口和最大竞争窗口,改进其退避算法,并综合考虑到了公平性的问题。经OPNET仿真验证表明,该算法提高了系统的吞吐量,减小了接入时延。     

Packets Schedule Algorithm for LTE Downlinks Based on QoS

提出一种基于服务质量(QoS)的长期演进(LTE)下行分组调度算法.根据业务的QoS对分组进行分类,提高时延敏感业务的优先级,通过分析传输流量,进行资源分配的公平性补偿.仿真实验结果表明,该算法能有效平衡吞吐量和用户公平性,且在丢包率方面性能较优.     

一种支持DiffServ模型的全分布式调度算法

调度算法设计对于网络路由设备实现区分服务(DiffServ)模型的单跳行为(per hop behavior,简称PHB)至关重要.现有支持DiffServ模型的调度算法普遍基于输出排队(output queued,简称OQ)或是输入排队(input queued,简称IQ)交换结构进行设计,均无法在高速环境下提供高性能的调度.基于联合输入/交叉节点排队(combinedinput-crosspoint-queued,简称CICQ)交换结构提出一种支持DiffServ模型的全分布式调度算法DDSS (distributed DiffServ supporting scheduling),并通过理论分析对其公平性进行了验证.DDSS算法采用基于预约带宽的逐级流量控制机制实现所有预约带宽在快速转发(expedited forwarding,简称EF)业务与确保转发(assured forwarding,简称AF)业务之间的分配,采用优先级调度机制为EF业务提供低延迟服务,算法复杂度为O(log N).仿真结果表明,DDSS算法具有良好的时延性能和公平特性,与现有算法相比,能够更好地支持DiffServ模型.     

基于无线网络的混合业务资源调度算法

WCDMA系统混合业务下的资源调度算法要区分业务以保证用户的服务质量(QoS)。基于此,在研究最大加权延时优先算法(M-LWDF)的基础上通过引入QoS监测机制提出一种保证混合业务服务质量的资源调度算法,在业务调度中同时考虑时延优先级和吞吐量优先级,并采用传输时延保证的资源分配准则。仿真结果表明,该算法在时延和吞吐量水平上要优于已有的调度算法。     

长期演进系统基于加权平均时延的下行资源调度

针对长期演进（LTE）移动通信系统下行链路传输中多用户的实时（RT）与非实时（NRT）业务传输性能需求问题，提出一种基于用户加权平均时延的改进型的最大加权延时优先（MLWDF）资源调度算法。该算法在考虑信道感知与用户服务质量（QoS）感知的基础上引入反映用户缓冲区状态的加权平均时延因子，该因子通过用户缓冲区中待传输数据与已发送数据的平均时延均衡得到，使具有较大时延和业务量的实时业务优先调度，提升了用户的性能体验。理论分析与链路仿真表明，提出算法在保证各业务时延及公平性的基础上，提升了实时业务的QoS性能，在用户数量达到50的条件下，对比MLWDF算法实时业务的丢包率降低了53.2%，其用户平均吞吐量提升了44.7%，虽牺牲了非实时业务的吞吐量，但仍优于VT-MLWDF算法。实验结果表明，所提算法在多用户多业务传输条件下提升了实时业务的传输性能，并在QoS性能上明显优于对比算法。     

KIR:一种TCP拥塞避免阶段的公平性算法及在GEO卫星环境下的仿真

传统的TCP拥塞避免机制对长时延链接存在歧视,随着竞争流的增加,TCP共享瓶颈带宽的公平性和有效性降低.在研究CR,IBK,CANIT等现有算法的基础上,提出了一个新的均衡公平性算法KIR （K and additive increase ratio）来纠正对长时延链接的歧视,新算法的思想是在拥塞避免阶段分别对长时延链接与短时延链接的窗口增加方案做了平滑修改,同时经过数学推导,给出一个能够取得较好公平性和带宽利用率的K的表达式.通过一系列仿真实验比较了不同公平性机制的性能,分析了它们之间的不同特性,结果显示KIR算法不仅能够提高TCP公平性,而且取得了比较理想的链路吞吐率.针对地球同步轨道GEO卫星环境,在NewReno,Sack,Tcpw三种TCP拥塞控制机制中对KIR算法的有效性进行了仿真验证.     

无人机辅助MEC系统中面向用户公平性的三维部署和卸载优化

针对无人机辅助移动边缘计算系统存在的用户公平性不足问题, 本文提出了一种面向用户公平性的三维部署和卸载优化算法. 该算法综合考虑用户匹配、无人机三维部署、计算资源分配、卸载因子对系统总时延及用户公平性的影响, 建立了一个最小化系统总时延的多元优化问题, 并针对该问题提出了一种两阶段联合优化算法, 其中第1阶段使用带有平衡约束的聚类算法解决用户匹配和无人机的水平部署问题, 第2阶段使用凸优化算法迭代求解无人机高度部署, 资源分配和卸载因子优化问题. 实验结果表明, 与4种基准算法相比, 所提算法在系统总时延和用户公平性两方面具有更好的性能.     

自适应Ad hoc分布式互斥算法

Ad hoc网络的动态拓扑结构和节点自组织给分布式算法的实现带来了诸多困难.针对Ad hoc分布式互斥算法研究滞后的现状,提出了一种自适应的Ad hoc分布式算法ADMUTEX. ADMUTEX算法基于令牌查询方法,它采用Lamport逻辑时戳保证消息的时序性,避免了节点饿死.同时,它在消息复杂度与同步延迟之间作了折衷,而且它不需要节点了解系统的全局信息,能够适应Ad hoc网络的动态拓扑结构和节点频繁出入的情况.分析与仿真结果表明该算法具有较低的消息复杂度、小响应延迟和公平性.     

一种使用历史信息的长期公平队列调度算法

经典的基于时延的队列调度仅关注调度时刻的队列延时,对历史信息并无记忆性,从而在业务流突变时排队延时公平性无法得到保障。本文提出一种长期公平调度算法,不仅综合考虑队列长度、到达速率等即时参量,而且考虑历史参量--历史延时累计量,使得调度更加理性,排队延时不会随流量突变而突变。另外,3个调度参量的关系式并非人为给出,而是通过对长期公平性的建模和对长期优化问题的推导得来。仿真对比了WRR, RPF, EDF算法,证实该算法中的队列延时不仅具有较高的公平性还具有较高的稳定性。     

实时多播流的弹性公平性和基于门限的拥塞控制策略

该文提出了关于实时IP多播流基于速率弹性的公平性定义，并结合有关多播组规模估计的机制和多播拥塞控制算法。实现了一种基于门限的实时多播业务的等级拥塞控制策略，使实时多播流在满足瞬态弹性公平性的同时，也基本满足稳态的比例公平性，并对此进行了仿真验证。     

基于低频子图的运动估计算法

为了减少运动估计的计算复杂度并提高其搜索性能,提出了一种基于低频子图的运动估计算法。该算法首先将当前帧和参考帧通过低通滤波器得到数据量减为1/4的低频子图,然后用全搜索得到最佳匹配的低频子块,最后对低频子块所覆盖的原参考帧区域进行精细搜索得到最优点。实验结果表明,与传统运动估计算法相比,该算法极大的提高了运动估计的精确度和降低了计算复杂度,并且对各类视频都有很高的鲁棒性。     

一种REM算法辅助的分层组播流量控制方案

基于分层组播中公平速率分配算法实施过程中存在的问题以及分层组播协议策略中同步点的优化问题，提出了将主动队列管理算法REM作为对端系统的辅助加入到分层组播流量控制中，将分层组播同步点策略、满足Max-Min公平性要求的速率分配算法以及基于REM的显式拥塞指示技术有机地结合起来，设计了一种基于速率的、由接收者和发送者混合驱动的分层组播流量控制方案。仿真实验结果表明该方案使得分层多速率组播在保证会话内、会话间公平性的前提下，提高了流量控制机制的高效性和对网络状态适应的灵敏性。     

一种MPLS流量工程中的动态路由算法

提出了一种MPLS流量工程中新的保证带宽的动态路由算法。传统的算法如SPF(Shortest Path First)算法、WSP算法（Widest Shortest Path）等都没有利用业务分布或入出路由器对（Ingress-Egress Pairs）的信息,可能导致严重的网络资源使用不充分的问题。该方法分两步：①离线路由,基于业务分布和日常统计的静态研究;该阶段能充分利用网络资源,有助于在线路由阶段动态路径的选择及避免拥塞;②根据第①步的结论及实际的网络状态,在线路由。重点针对在线路由提出了一种新的动     

An improved FPTAS for Restricted Shortest Path

Given a graph with a cost and a delay on each edge, Restricted Shortest Path (RSP) aims to find a min-cost s-t path subject to an end-to-end delay constraint. The problem is NP-hard. In this note we present an FPTAS with an improved running time of O(mn/ε) for acyclic graphs, where m and n denote the number of edges and nodes in the graph. Our algorithm uses a scaling and rounding technique similar to that of Hassin [Math. Oper. Res. 17 (1) (1992) 36-42]. The novelty of our algorithm lies in its “adaptivity”. During each iteration of our algorithm the approximation parameters are fine-tuned according to the quality of the current solution so that the running time is kept low while progress is guaranteed at each iteration. Our result improves those of Hassin [Math. Oper. Res. 17 (1) (1992) 36-42], Phillips [Proc. 25th Annual ACM Symposium on the Theory of Computing, 1993, pp. 776-785], and Raz and Lorenz [Technical Report, 1999].     

Efficient fair algorithms for message communication

A computer network serves distributed applications by communicating messages between their remote ends. Many such applications desire minimal delay for their messages. Beside this efficiency objective, allocation of the network capacity is also subject to the fairness constraint of not shutting off communication for any individual message. Processor Sharing (PS) is a de facto standard of fairness but provides significantly higher average delay than Shortest Remaining Processing Time (SRPT), which is an optimally efficient but unfair algorithm. In this paper, we explore efficient fair algorithms for message communication where fairness means that no message is delivered later than under PS. First, we introduce a slack system to characterize fair algorithms completely and develop efficient fair algorithms called Pessimistic Fair Sojourn Protocol (PFSP), Optimistic Fair Sojourn Protocol (OFSP), and Shortest Fair Sojourn (SFS). Then, we prove that a fair online algorithm does not assure minimal average delay attainable with fairness. Our analysis also reveals lower bounds on worst-case inefficiency of fair algorithms. We conduct extensive simulations for various distributions of message sizes and arrival times. During either temporary overload or steady-state operation, SFS and other newly proposed fair algorithms support SRPT-like efficiency and consistently provide much smaller average delay than PS.     

A proportional fairness scheduling for wireless sensor networks

This paper describes a packet scheduling algorithm for wireless sensor networks (WSNs) that meets the proportional fairness principle. Based on the weighted round-robin strategy, the proposed scheduling algorithm allocates a different service quota to different traffic according to the average packet arrival rate. This guarantees proportional fairness in terms of the average packet delivery delay and the average packet loss ratio. Since the scheduling algorithm does not perform high-load operations such as time stamping and sorting, it can be implemented easily and is suitable for resource-limited WSNs. The proposed scheduling algorithm is tested in a WSN and is found to guarantee the proportional fairness of the average packet delivery delay when this is used as the performance metric, and to realize proportional fairness in the average packet loss ratio when all the queues are overflowing and the average packet loss ratio is used as the performance metric.     

MHWSN中保证混合业务QoS的跨层调度算法

针对中高速传感器网络中混合业务QoS（Quality of Service）要求,跨层考虑物理层和数据链路层参数,提出了一种保证混合业务服务质量的调度算法AM-LWDF。该算法同时考虑时延优先级和吞吐量优先级,在满足实时业务QoS约束的前提下,以最大化系统吞吐量为目标建立了相应的优化模型,对实时业务能够满足时延较小的要求,对非实时业务满足吞吐量较大的要求。仿真结果表明,该调度算法可以灵活地在时延和吞吐量之间取得满意的折衷,并保证不同类型业务用户间的公平性。