Efficient and adaptive resource scheduling in IEEE 802.16j transparent relay networks

Relaying is regarded as a promising technique for enhancing the system throughput and coverage of emerging broadband wireless access networks. While next generation broadband wireless standardization bodies (e.g., LTE-advanced and IEEE 802.16j) have specified the support of relays in general terms, the problem of allocating network resources in an efficient and effective manner remains a challenging issue. In this study, the utility-based resource scheduling optimization problem for IEEE 802.16j transparent relay networks is formulated mathematically and proven to be NP-hard. Two efficient heuristic algorithms, namely Relay Resource Scheduling (RRS) and Adaptive Relay Resource Scheduling (ARRS), are proposed to resolve the resource scheduling problem. RRS maximizes the system utility in networks containing direct and relay mobile stations by exploiting the benefits of optional transmissions. ARRS enhances upon the performance of RRS by adaptively determining the split ratio between the access zone and the transparent zone in the downlink subframe. The computational complexities of both algorithms are shown to be polynomial and proportional to the number of links and subchannels in the network. The simulation results show that the proposed algorithms achieve significantly better throughput and fairness performance than existing schemes such as Partial Proportional Fairness (PPF) and GenArgMAX.     

An efficient scheduling algorithm for radio resource reuse in IEEE 802.16j multi-hop relay networks

The IEEE 802.16j standard for WiMAX introduced the concept of relay station in order to increase the service area and decrease the deployment cost of the network. In this paper, we have proposed an efficient scheduling scheme for IEEE 802.16j networks, which maximizes the number of connections that are scheduled in a particular time slot. The proposed scheme schedules the connections based on their priority, which is decided by the quality of service (QoS) requirement of the connections. A selected connection can be scheduled in the current timeslot only if it is not having interference with any of the already scheduled connections. Our algorithm considers scheduling of lower priority connections even if any higher priority connection is not scheduled due to interference. Thus, the delay for lower priority connections is reduced without increasing the delay for higher priority connections. In addition, our algorithm achieves higher frame utilization and higher system throughput by reducing the length of the schedule.     

Power-aware opportunistic downlink scheduling in IEEE 802.16 wireless networks

The IEEE 802.16 is a standard for fixed and mobile Broadband Wireless Access (BWA). In this paper, we deal with two key challenges of 802.16-based networks. First, terminals close to cell edge experience poor channel quality, due to severe path-loss and high interference from concurrent transmissions in nearby cells. To address this issue, we propose a framework based on a static partitioning of bandwidth into chunks with different transmission power levels. Terminals with impaired channel conditions can then benefit from being allocated a higher amount of transmission power than the others. Secondly, transmissions should be scheduled according to Quality of Service (QoS) requirements to keep users with real-time video or voice calls satisfied, while best-effort connections should fairly share the remaining capacity. To this aim, we propose a scheduling algorithm, called Power-aware Opportunistic Downlink Scheduling (PODS), that aims at meeting both the QoS and fairness requirements, while taking into account the different power levels of the bandwidth chunks. The performance of the proposed scheduler is assessed through detailed packet-level simulation in realistic scenarios and compared with well-known scheduling algorithms. Results confirm that PODS is able to exploit power boosting to provide real-time connections with the desired level of QoS, irrespectively of their MSs’ channel quality.     

Efficient forwarding scheme for downlink broadcast messages in IEEE 802.16j multi-hop relay networks

Although the IEEE 802.16j standard introduces a connection identifier (CID)-based forwarding scheme and a tunnel-based forwarding scheme, these schemes exhibit poor performance when forwarding broadcast messages. This study considers a CID translation strategy and proposes two CID-translated forwarding schemes for IEEE 802.16 multi-hop relay networks. The basic CID-translated forwarding scheme does not require to append the relay MAC header of the tunnel-based scheme to the broadcast messages. The enhanced CID-translated forwarding scheme further divides a broadcast message into a common part and a specific part and forwards these parts in a multicast manner and a broadcast manner, respectively. Simulation results validate that the basic CID-translated forwarding scheme uses fewer resources than the tunnel-based forwarding scheme. Moreover, the enhanced CID-translated forwarding scheme outperforms the basic CID-translated forwarding scheme in terms of the system resources used and transmission latency.     

LASER: A load-aware spectral-efficient routing metric for path selection in IEEE 802.16j multi-hop relay networks

For coverage extension and throughput enhancement, the IEEE 802.16j task group has developed a novel multi-hop relay network architecture to enable typical IEEE 802.16 networks to achieve data transmission between base stations and mobile stations via a multi-hop path with relay stations deployment. How to determine an effective path for throughput gain and overhead reduction is emerging and crucial in IEEE 802.16 multi-hop relay networks. This paper introduces a load-aware spectral-efficient routing metric, called LASER, to evaluate paths, and proposes an efficient scheme to determine a proper path. Based on the LASER metric, the proposed path selection scheme formulates the path cost as the summation of cost of each link, and the path with the minimum cost will be selected as the appropriate one. Simulation results show that the proposed LASER-based path selection scheme significantly outperforms existing path selection schemes in network throughput and map overhead.     

A novel resource scheduling algorithm for QoS-aware services on the Internet

The popularity and availability of Internet connection has opened up the opportunity for network-centric collaborative work that was impossible a few years ago. Contending traffic flows in this collaborative scenario share different kinds of resources such as network links, buffers, and router CPU. The goal should hence be overall fairness in the allocation of multiple resources rather than a specific resource. In this paper, firstly, we present a novel QoS-aware resource scheduling algorithm called Weighted Composite Bandwidth and CPU Scheduler (WCBCS), which jointly allocates the fair share of the link bandwidth as well as processing resource to all competing flows. WCBCS also uses a simple and adaptive online prediction scheme for reliably estimating the processing times of the incoming data packets. Secondly, we present some analytical results, extensive NS-2 simulation work, and experimental results from our implementation on Intel IXP2400 network processor. The simulation and implementation results show that our low complexity scheduling algorithm can efficiently maximise the CPU and bandwidth utilisation while maintaining guaranteed Quality of Service (QoS) for each individual flow.     

Performance analysis of authentication and key distribution scheme for mobile multi-hop relay in IEEE 802.16j

Mobile multi-hop relay (MMR) network is known to be easy to install and convenient to manage because of its self-organizing and self-healing characteristics. However, MMR is vulnerable to security problems because of the same reason. In this paper, we propose a new hybrid authentication and key distribution algorithm for IEEE 802.16j MMR service. The proposed scheme uses centralized authentication when a mobile station or a relay station initially joins the MMR network and uses distributed authentication for hop-by-hop authentication between mobile nodes. We examine the procedure of the proposed scheme and its usefulness when applied to MMR networks. We also analyze the performance of the hybrid scheme. The proposed scheme can be used in any mobile multi-hop network as well as IEEE 802.16j MMR network.     

IEEE802．16中的无线Mesh网络研究

1980年3月13日,IEEE批准了一个新的的工程802。IEEE802由LAN／MAN Standard Committee（LMSC）负责。就无线通信而言,802WG定义了802．11WLAN,802．15WPAN和802．16WMAN。与以前的无线技术一样,随着通信实体的距离的增大,数据的传输速率随之降低。对新的应用层业务而言,无论距离多远,都必须要保障高的数据率。要克服链路速率的限制,必须密集地布置无线网路设备。WMN有助于克服当前的无线通信系统对有线主干网络的依赖,因为它们价格便宜并能保证新的无线应用。概括了WMN的发展历程和最新的发展动态,并指出了进一步的发展方向。     

A novel radio resource allocation scheme for IEEE 802.16e multicell networks

In this paper,we propose a new media access control (MAC) protocol,which is compatible with the IEEE 802.16e-2005 Orthogonal Frequency Division Multiple Access (OFDMA) wireless interface.In this protocol,the same radio resource can be shared by neighboring cells in the wireless mesh network (WMN) and collisions can be reduced in the overlapping areas.This protocol consists of two schemes: a downlink transmission and an uplink transmission.For downlink transmission we use a cross layer adaptive radio resourc...     

An embedded fuzzy expert system for adaptive WFQ scheduling of IEEE 802.16 networks

WiMAX is a futuristic technology which provides simultaneous support for web, video, and voice applications. WiMAX networks are best suitable to real time traffic however the quantity of non real time and best effort traffic cannot be neglected. Distribution of resources in such heterogeneous applications is therefore a challenging task. There are many schedulers available for WiMAX but adaptive and adequate schedulers are still in growing stage of development. This paper introduces a novel method using which a system is developed based on concepts of fuzzy logic to schedule traffic in WiMAX networks. The proposed fuzzy expert system simplifies fair allocation of resources to real as well as non real time traffic. The implementation is based on changing the weights of the queues serving real and non- real time traffic adaptively. New weights will be calculated for each bandwidth request made to base station and these weights will in turn decide amount of bandwidth allocated to different traffic classes. The weights are calculated based on three parameters that are amount of real time and non real time traffic in queues, change in throughput requirement for non real time flows and latency requirement of real time input data. Results obtained by virtue of simulations justify the significance of the proposed method.     

Heuristic algorithms for two-dimensional uplink burst construction in IEEE 802.16 networks

Many burst construction algorithms have been proposed for Orthogonal Frequency Division Multiple Access (OFDMA). However, none meets the burst structure characteristics required by the IEEE 802.16 standard. In this study, two heuristic algorithms, Best Corner Oriented (BCO) and Best Subchannel Oriented (BSO), are proposed to provide high throughput for uplink burst construction in IEEE 802.16 networks. The BCO maintains all available slots as a continuous area and attempts to construct each burst from one of the two ending slots of this area. The BSO, however, constructs each burst in its best quality subchannels to adopt a better modulation coding scheme (MCS). The simulation results under a heavy load indicate that BSO and BCO achieve 2 and 1.5 times, respectively, the throughput achieved by Raster, the conventional algorithm. However, the superior performance of BSO is achieved at the expense of increased time complexity.     

Uplink Scheduling for Supporting Real Time Voice Traffc in IEEE 802.16 Backhaul Networks

In this paper we propose simple enhancements to the bandwidth (BW) request messages in IEEE 802.16 for supporting real-time packet voice traffc. Three different BW request formats are proposed, each requiring a different amount of latency information about the buffered packets at the SS. On this basis, packet scheduling schemes are proposed for the BS to make resource allocations for real-time traffc. Our results show that the proposed BW request and scheduling schemes achieve significantly lower packet loss probability than the standard IEEE 802.16 BW request with round robin scheduling. The results further show that there is an optimum point about how much delay information the SS should report to the BS in order to best utilize the uplink resources while the SS provides satisfactory real-time performance for the voice traffc.     

一种IEEE 802.16宽带无线接入系统的QoS架构

IEEE 802.16 MAC协议虽然对各类业务的QoS提供支持,却没有定义完整的QoS保证机制.本文通过分析IEEE 802.16现有的QoS架构,提出了一种具体的QoS架构,并对相应的调度算法进行了分析.仿真结果表明,该架构能够对实时业务提供较好的支持,同时维持其它业务的带宽在可接受的范围之内.     

A novel approach to resource scheduling for parallel query processing on computational grids

Advances in network technologies and the emergence of Grid computing have both increased the need and provided the infrastructure for computation and data intensive applications to run over collections of heterogeneous and autonomous nodes. In the context of database query processing, existing parallelisation techniques cannot operate well in Grid environments because the way they select machines and allocate tasks compromises partitioned parallelism. The main contribution of this paper is the proposal of a low-complexity, practical resource selection and scheduling algorithm that enables queries to employ partitioned parallelism, in order to achieve better performance in a Grid setting. The evaluation results show that the scheduler proposed outperforms current techniques without sacrificing the efficiency of resource utilisation. Recommended by: Ioannis Vlahavas     

A sleep-mode interleaving algorithm for layered-video multicast services in IEEE 802.16e networks

In this paper we investigate efficient mechanisms to support layered-video multicast services in IEEE 802.16e (Mobile WiMAX) networks.¹ Given the bandwidth eager and energy hungry nature of layered-video multicast services, network systems should employ efficient bandwidth allocation and energy saving mechanisms. We first investigate how the WiMAX energy saving mechanisms significantly degrade the performance of multicast bandwidth allocation mechanisms for layered-video multicast services. Then, we present a theoretical model for illustrating this interaction problem. To the best of our knowledge, this paper offers the first investigation into and the first theoretical model of the interaction problem between multicast bandwidth allocation and WiMAX energy saving mechanisms. To solve the interaction problem, we propose a novel sleep-mode interleaving algorithm beyond the existing mechanisms. The proposed algorithm has full compatibility with the existing multicast bandwidth allocation mechanisms and with IEEE 802.16e standards. By appropriately adjusting one sleep mode parameter defined in the standard, the proposed sleep-mode interleaving algorithm effectively guarantees the bandwidth efficiency of the video multicast mechanisms while mobile users can execute the standard sleep mode operations. Simulation results demonstrate the effectiveness of the proposed algorithm in terms of packet delivery ratio, user satisfaction, energy efficiency and computational complexity.     

Solving project scheduling problems with resource constraints via an event list-based evolutionary algorithm

There are various scheduling problems with resource limitations and constraints in the literature that can be modeled as variations of the Resource Constrained Project Scheduling Problem (RCPSP). This paper proposes a new solution representation and an evolutionary algorithm for solving the RCPSP. The representation scheme is based on an ordered list of events, that are sets of activities that start (or finish) at the same time. The proposed solution methodology, namely SAILS, operates on the event list and relies on a scatter search framework. The latter incorporates an Adaptive Iterated Local Search (AILS), as an improvement method, and integrates an event-list based solution combination method. AILS utilizes new enriched neighborhoods, guides the search via a long term memory and applies an efficient perturbation strategy. Computational results on benchmark instances of the literature indicate that both AILS and SAILS produce consistently high quality solutions, while the best results are derived for most problem data sets.     

中继OFDMA系统用户公平性的资源分配算法的研究

在OFDMA解码—转发中继系统中,为了公平地进行资源分配,提出了在两个用户模型下,在保证每个用户最小速率需求的前提下,先按照用户预定速率比进行子载波分配,再根据实际速率比对用户的子载波进行调整的分配算法,最后使整个系统的吞吐量达到最大。提出了三种方案。方案一通过对Lagrange对偶函数问题的求解,根据所得代价函数值的大小对用户的子载波做重新调整。这样不仅考虑到了公平性,也减少了用户的速率损失。方案二、方案三分别从子载波端和用户端出发考虑子载波的分配问题,且从不同的分配角度分析了公平性问题。研究结果表明,三种方案获得的公平性均有所提高。     

GAME based dynamic resource scheduling in QoS aware radio access networks

Radio resource management and QoS are finally inseparable in wideband CDMA networks. In this paper, we propose a novel wireless resource scheduler, called GAME-C, that integrates our genetic algorithm for mobiles equilibrium (GAME) with the standard CDMA transmitter closed loop power control (CLPC). GAME assigns optimally both transmitting power and bit rate to every mobile station. Optimal allocation is in the sense that every user gets only enough resources necessary for meeting or exceeding its QoS requirements while minimizing interference to other users. Having done that, we gain further benefits as well. In addition to QoS provisioning, lower transmitting power extends a mobile station battery life. Moreover, the base station coverage efficiency is improved by decreasing the probability of blocking new connections or dropping current ones. In short, GAME-C expands the number of QoS-satisfied mobile stations in a cell. Various simulations show improvements achieved over the established (CLPC) basic scheme.     

A probabilistic and adaptive scheduling algorithm using system-generated predictions for inter-grid resource sharing

Rapid advancement and more readily availability of Grid technologies have encouraged many businesses and researchers to establish Virtual Organizations (VO) and make use of their available desktop resources to solve computing intensive problems. These VOs, however, work as disjointed and independent communities with no resource sharing between them. We, in previous work, have proposed a fully decentralized and reconfigurable Inter-Grid framework for resource sharing among such distributed and autonomous Grid systems (Rao et al. in ICCSA, [2006]). The specific problem that underlies in such a collaborating Grids system is scheduling of resources as there is very little knowledge about availability of the resources due to the distributed and autonomous nature of the underlying Grid entities. In this paper, we propose a probabilistic and adaptive scheduling algorithm using system-generated predictions for Inter-Grid resource sharing keeping collaborating Grid systems autonomous and independent. We first use system-generated job runtime estimates without actually submitting jobs to the target Grid system. Then this job execution estimate is used to predict the job scheduling feasibility on the target system. Furthermore, our proposed algorithm adapted itself to the actual resource behavior and performance. Simulation results are presented to discuss the correctness and accuracy of our proposed algorithm.