Dual power-saving modes for voice over IP traffic supporting voice activity detection

In the context of the IEEE 802.16e standard, a dual power-saving mode (DPSM) algorithm for voice over IP (VoIP) traffic whose voice codec supports voice activity detection is proposed. The proposed algorithm utilises the inactivity of the voice codec of each conversing party during mutual silence periods. Using the suggested method, the length of the sleep intervals varies during mutual silence periods, while during talk-spurt periods it is fixed according the VoIP packet generation ratio. The performance of the proposed DPSM algorithm for the average packet-buffering delay in the base station (BS) and the energy consumption of a mobile station (MS) is evaluated numerically and validated with the aid of computer simulation. The results show that when the proposed combined method is used, the energy consumption of an MS is considerably less when a PSM that only uses sleep intervals of a fixed length is operating. This improvement in performance comes at the cost of greater packet-buffering delay in the BS.     

Mesh模式下基于最小干扰流量的带宽调度算法

研究了干扰链路流量大小对IEEE802．16Mesh网络传输性能的影响,提出了一种通过计算用户站（SS）和基站（BS）的通信路径干扰的总流量来寻找总干扰流量最小的路由算法,并结合路由树给出了一种冲突避免调度的方法。该算法既考虑了干扰链路的数量,又考虑了干扰链路的实际通信强度,在建立路由树的过程中能够更快地使系统达到更佳的负载均衡状态,最大强度地避免调度中可能出现的带宽冲突。由于干扰流量的影响可以得到有效的控制,系统的吞吐量可以明显提高。仿真结果验证了该算法的有效性。     

Improved power-saving medium-access protocol for IEEE 802.11e QoS-enabled wireless networks

The performance of a new pointer-based medium-access control protocol that was designed to significantly improve the energy efficiency of user terminals in quality-of-service-enabled wireless local area networks was analysed. The new protocol, pointer- controlled slot allocation and resynchronisation protocol (PCSARe), is based on the hybrid coordination function-controlled channel access mode of the IEEE 802.11e standard. PCSARe reduces energy consumption by removing the need for power-saving stations to remain awake for channel listening. Discrete event network simulations were performed to compare the performance of PCSARe with the non-automatic power save delivery (APSD) and scheduled-APSD power- saving modes of IEEE 802.11e. The simulation results show a demonstrable improvement in energy efficiency without significant reduction in performance when using PCSARe. For a wireless network consisting of an access point and eight stations in power-saving mode, the energy saving was up to 39% when using PCSARe instead of IEEE 802.11e non-APSD. The results also show that PCSARe offers significantly reduced uplink access delay over IEEE 802.11e non-APSD, while modestly improving the uplink throughput. Furthermore, although both had the same energy consumption, PCSARe gave a 25% reduction in downlink access delay compared with IEEE 802.11e S-APSD.     

An interference and latency aware uplink scheduling mechanism in IEEE 802.16j networks

IEEE 802.16j spreads out the coverage of WiMAX networks and strengthens wireless signal transmission using relay technology. To take advantage of relaying in IEEE 802.16j networks, an efficient scheduling schedule with quality of service (QoS) provision for multiple link transmissions is necessary, especially when link interference exists. In this paper, we propose an uplink scheduling mechanism in the transparent mode of IEEE 802.16j, which enables multiple devices to transmit without interference. The maximum latency of each connection has been considered in order to optimize the violation and transmission rate. An interference detection task is first carried out, and then a resource allocation algorithm and a dynamic frame adjustment method are developed. Two simulation experiments were conducted with different interference levels. The results demonstrate that under a fixed QoS type of connection, when the total number of connections goes up to 360 and 420 and the maximum latency violation rate approaches 20%, the average uplink transmission rate of the proposed mechanism can achieve 6.67 and 7.92 Mbps, which apparently outperform regular relay scheduling schemes with rate of 4 and 3.91 Mbps, respectively.     

基于语音流统计特性的VoIP容量分析与提升算法

在研究IEEE 802.16标准关于VoIP传输机制的基础上,指出语音流的静默特性严重制约了VoIP的容量.通过分析VoIP业务流的统计特性得出了在统计复用情况下VoIP的容量极限.提出了一种基于统计复用的带宽调度方法及其实现算法,以克服由于语音静默带来的语音速率波动.仿真结果表明,该调度方法与UGS(unsolicited grant service)调度相比能够显著提升VoIP的容量,同时使BS和SS之间的VoIP丢包率和传输时延保持在0.02%和5.1ms以下.     

以太无源光网络单级多功能ONU内调度算法

针对以太无源光网络(EPON),为各类业务提供服务质量支持,特别是保障时延敏感型业务的服务质量,提出一种调度算法,应用到EPON的光网络单元(ONU)中.我们设法让这个单级调度算法具备多级调度功能.通过理论分析和仿真测试,证明本算法具有灵活的优先级机制和公平调度功能.     

Dynamic resource allocation for supporting real-time multimedia applications in IEEE 802.15.3 WPANs

The IEEE 802.15.3 medium access control (MAC) protocol is an emerging standard for high-rate wireless personal area networks (WPANs), especially for supporting high-quality real-time multimedia applications. Despite defining quality of service (QoS) signalling mechanisms for interoperability between devices, IEEE 802.15.3 does not specify resource allocation algorithms that are left to manufacturers. To guarantee the QoS of real-time variable bit rate (VBR) videos and utilise the radio resource efficiently, the authors propose a dynamic resource allocation algorithm. The proposed bandwidth allocation algorithm is based on a novel traffic predictor. Recently, the variable step-size normalised least mean square (VSSNLMS) algorithm was employed for on-line traffic prediction of VBR videos. However, the performance of the VSSNLMS algorithm significantly degrades due to the abrupt traffic variation occurring at the scene boundary. To tackle this problem, the authors design a novel traffic predictor based on a simple scene detection algorithm and the VSSNLMS algorithm. Analyses using real-life MPEG video traces indicate that the proposed traffic predictor significantly outperforms the VSSNLMS algorithm with respect to the prediction error. The performance of the proposed bandwidth allocation algorithm is also investigated by comparing several existing algorithms. Simulation results demonstrate that the proposed bandwidth allocation algorithm surpasses other mechanisms in terms of channel utilisation, buffer usage and packet loss rate.     

Application of the generalised ballot theorem for evaluation of performance in packet buffers with non-first in first out scheduling

Packet scheduling is a vital component to support different classes of service in all-packet networks. In classical queuing systems, the waiting-time performance of non-first in first out buffer scheduling systems could be predicted through the use of analysis. However, all-packet networks feature traffic patterns that do not conform to classical Poisson-like processes, and this greatly complicates the evaluation of their performance. Our novel approach to this problem is through a hybrid combination of analysis and simulation. The authors derive a combinatorial algorithm, using the generalised ballot theorem, which predicts waiting times for low-priority traffic. When this algorithm is combined with prior work on traffic aggregation, the authors achieve a significant reduction in the state space associated with the buffer under study. To numerically test this algorithm, the authors demonstrate its use in simulation, where state space and event count reduction is a fundamental requirement to ensure experiments complete in a timely fashion. Numerical results from these simulations show a very significant reduction in the number of events processed combined with improved state coverage. This is achieved while maintaining a highly accurate representation of packet delays compared with a conventional approach.     

Medium access control access delay analysis of IEEE 802.11e wireless LAN

The IEEE 802.11e standard is specified to support quality-of-service in wireless local area networks, and different contention parameters are designated to each type of service. This developed model is presented to analyse the scheduling and the contention between packets with different priorities, where the new features of the enhanced distributed channel access such as virtual collision, backoff, minimum contention window and different arbitration inter-frame spaces are taken into account. Based on the model, the delay performance of differentiated service traffic is analysed and a recursive method is proposed, which is capable of calculating the mean access delay. Simulations show that the model and the analysis provide an insight into the protocol and the effects of different parameters on the performance.     

Providing differentiated services in CDMA wireless networks

With much more advanced techniques employed, various applications can be supported by 3G CDMA-based wireless networks. Providing differentiated service over wireless networks has become a very important issue in the design of wireless networks. A new media access control protocol with a hierarchical scheduling algorithm to provide differentiated service for CDMA-based wireless networks is proposed. This protocol evolves from the distributed queuing random access protocol for CDMA wireless network. The proposed protocol has been designed to have an ability to accommodate integrated traffic in the networks with effective scheduling schemes. A series of simulation experiments have been carried out to evaluate the performance of the proposed protocol with the hierarchical scheduling algorithm. The results reveal that the proposed solution performs effectively in the integrated traffic composed of messages with or without time constraints and achieves proportional fairness among different types of traffic.     

A pinwheel packet scheduling scheme for broadband wireless networks

Abstract

A frame‐based packet scheduling scheme, the pinwheel scheduling (PWS) scheme, is proposed and investigated at the medium access control (MAC) layer in broadband wireless networks. The objective of the proposed scheduling scheme is to provide low delay and low jitter for real‐time traffic. We have demonstrated in this paper that the proposed PWS scheme not only satisfies the packet‐level QoS requirements but also has low implementation cost. The PWS scheme gives the highest priority to CBR connections in a service cycle to minimize their delay and jitter. For ABR traffic, a number of slots are allocated to fit their MCR. The remaining time slots are then allocated to VBR traffic according to their PCR. Thus, the VBR traffic may suffer large delay and jitter when the number of CBR connections increases. The PWS with modular strategy (PWS/MS) is proposed to improve the performance of the VBR traffic. We also introduce three different slot‐reuse strategies named real‐time traffic first (RTF), non‐real‐time traffic first (NRTF) and longest queue first (LQF), respectively, to improve resource utilization. In order to demonstrate the performance of the PWS and PWS/MS schemes, comparisons are made with existing schemes such as the round‐robin (RR) and weighted‐round‐robin (WRR) by using OPNET software. Simulation results show that the proposed schemes are capable of maintaining the lowest delay and jitter for VBR and CBR traffic while not sacrificing the available bit rate (ABR) traffic.     

A branch and bound algorithm for optimal cyclic scheduling in a robotic cell with processing time windows

A branch and bound algorithm is described for optimal cyclic scheduling in a robotic cell with processing time windows. The objective is to minimise the cycle time by determining the exact processing time on each machine which is limited within a time window. The problem is formulated as a set of prohibited intervals of the cycle time, which is usually applied in the robotic cyclic scheduling problem with fixed processing times. Since both bounds of these prohibited intervals are linear expressions of the processing times, we divide these prohibited intervals into a series of the subsets and transform the problem into enumerating the non-prohibited intervals of cycle time in each subset. This enumeration procedure is completed by an efficient branch and bound algorithm, which could find an optimal solution by enumerating partial non-prohibited intervals. Computational results on the benchmark instances and randomly generated test instances indicate that the algorithm is effective.     

Hybrid simulated annealing with memory: an evolution-based diversification approach

This study presents an efficient metaheuristic approach for combinatorial optimisation and scheduling problems. The hybrid algorithm proposed in this paper integrates different features of several well-known heuristics. The core component of the proposed algorithm is a simulated annealing module. This component utilises three types of memories, one long-term memory and two short-term memories. The main characteristics of the proposed metaheuristic are the use of positive (reinforcement) and negative (inhibitory) memories as well as an evolution-based diversification approach. Job shop scheduling is selected to evaluate the performance of the proposed method. Given the benchmark problem, an extended version of the proposed method is also developed and presented. The extended version has two distinct features, specifically designed for the job shop scheduling problem, that enhance the performance of the search. The first feature is a local search that partially explores alternative solutions on a critical path of any current solution. The second feature is a mechanism to resolve possible deadlocks that may occur during the search as a result of shortage in acceptable solutions. For the case of job shop scheduling, the computational results and comparison with other techniques demonstrate the superior performance of the proposed methods in the majority of cases.     

Multi-product continuous plant scheduling: combination of decomposition,genetic algorithm,and constructive heuristic

We propose a polylithic method for medium-term scheduling of a large-scale industrial plant operating in a continuous mode. The method combines a decomposition approach, a genetic algorithm (GA) and a constructive MILP-based heuristic. In the decomposition, decisions are made at two levels, using the rolling horizon approach. At the upper level, a reduced set of products and the time period is chosen to be considered in the lower level. At the lower level, a short-term scheduling MILP-model with event-based representation is used. A heuristic solution to the lower level problem is found using a constructive Moving Window heuristic guided by a genetic algorithm. The GA is applied for finding efficient utilisation of critical units in the lower level problem. For solving the one unit scheduling problem, a parallel dynamic programming algorithm is proposed. Implementation of the dynamic programming algorithm for a graphics processing unit (GPU) is incorporated in the GA for improving its performance. The experimental study of the proposed method on a real case of a large-scale plant shows a significant improvement of the solution quality and the solving time comparing to the pure decomposition algorithm proposed in the earlier study, and confirmed suitability of the proposed approach for the real-life production scheduling. In particular, the reduction of the number of changeovers and their duration in the obtained solution as well as the CPU time of solving the problem was about 60% using the new approach.     

一种基于带缓存crossbar的优先级排队机制及其调度算法

基于带缓存crossbar的交换结构提出了一种支持多优先级的调度方案.该方案在带缓存crossbar交换结构的输入端口提出了一种基于端口与优先级标识的层次化排队机制,并结合该排队机制提出了一种加权双轮询(DWRR)的调度算法,在crossbar内部交叉节点处的缓存队列提出了一种易于实现的补偿优先轮询(CPRR)调度算法.这种DWRR-CPRR优先级调度方案不需要在crossbar交叉节点设置多个优先级缓存队列,避免了在带缓存crossbar内部进行复杂的调度,实现简单.时延特性与带宽分配特性的仿真结果表明,该方案可以获得接近于采用加权公平排队(WFQ)调度策略的OQ交换结构的性能.     

A beam search-based algorithm and evaluation of scheduling approaches for flexible manufacturing systems

This paper presents a new algorithm for the flexible manufacturing system (FMS) scheduling problem. The proposed algorithm is a heuristic based on filtered beam search. It considers finite buffer capacity, routing and sequence flexibilities and generates machine and automated guided vehicle (AGV) schedules for a given scheduling period. A new deadlock resolution mechanism is also developed as an integral part of the proposed algorithm. The performance of the algorithm is compared with several machine and AGV dispatching rules using mean flow time, mean tardiness and makespan criteria. It is also used to examine the effects of scheduling factors (i.e., machine and AGV load levels, routing and sequence flexibilities, etc.) on the system performance. The results indicate that the proposed scheduling algorithm yields considerable improvements in system performance over dispatching rules under a wide variety of experimental conditions.     

面向Jobshop调度的时间映射算法

现实的Jobshop生产环境中的生产日历和班次等把设备资源的有效工作时间段分割成离散状态。为了降低调度在确定工序开始和结束时间时的计算复杂性,提出了一种时间映射算法。通过该算法实现了离散作业时间到整数连续区间和整数连续区间到离散作业时间的快速转换;并以遗传调度算法为例,研究了时间映射算法与调度算法的融合技术,实现了在连续整数区间上的调度。研究结果表明,相比未采用时间映射算法的调度算法,采用时间映射算法能大幅降低调度在确定工序开始和结束时间上的计算复杂性,计算时间降幅达到39.7%,从而提高了调度的计算效率。     

共享策略下甩挂车辆调度问题的分析及求解

目的为了克服现阶段下甩挂货运过程中存在的空载率高、牵引车利用率低等问题,从服务点间的货运关系出发,对货运单循环系统中共享策略下甩挂车辆调度问题进行设计研究。方法以牵引车行驶总里程为目标函数,构建共享策略下甩挂车辆调度模型,并基于模拟退火算法对其进行优化求解。结果以山东省的2家小型运输企业为案例进行了仿真分析,与普通车辆调度模式分析比较可知,共享策略下调度模式的空载率、单位货运成本、单位货运油耗、牵引车利用率分别优化了79.6%,50%,22.6%,171.4%。结论文中构建的共享策略下甩挂车辆调度模型及其求解算法可行有效,在减少空载行程、提高燃油利用率等方面具有良好的效果。     

有模具约束的并行机批量流调度问题研究

大多数调度问题均假设产品以单个或整批的方式进行生产,而实际生产过程中,会把产品分批后再进行生产。但当考虑模具约束时,对如何解决产品分批以及制定合理调度方案的问题,本文以最小化最大完工时间为优化目标,建立了考虑模具约束的并行机批量流调度模型,并提出了一种基于遗传算法和差分算法结合的混合差分遗传算法（DEGA）,实现分批与调度两个问题并行优化。最后通过对算例测试,DEGA算法得到更优的解,证明了该算法的优越性和稳定性。结合实际案例,验证了模型和算法的可行性。