Scheduling algorithms for next generation cellular networks

Abstract

Yeni nesil telsiz haberleşme sistemleri kullanıcıların artan isteklerini karşılamak için hızlı bir gelişme göstermektedir. Fakat, sınırlı frekans tayfı genişliği ve kablosuz kanal karakteristiğinin zamanda ve frekansta değişkenlik göstermesi sebebi ile kullanıcıların isteklerini karşılamak ve yüksek verim elde etmek için yeni çizelgeleme ve kaynak tahsis yöntemlerinin geliştirilmesi gerekmektedir. Bu tezde farklı çizelgeleme problemleri incelenmiş ve bu problemler için verimli çizelgeleme algoritmaları geliştirilmiştir.Fırsatçı çizelgeleme algoritmalarının en önemli özelliklerinden biri yeni gelişen teknolojiler ile kolay bir şekilde bütünleşebilmesidir. Bu bağlamda iki önemli teknoloji incelenmiştir. _Ilk olarak, frekans tayfının halihazırda verimsiz kullanımını azaltmak için geliştirilmiş olan bilişsel radyo ağları için optimum çizelgeleme algorithmları tasarlanmış ve incelenmiştir. Bu problemde, ikincil ve birincil kullanıcılar arasında işbirlikçi biryöntem benimsenerek, birincil kullanıcıların performansının arttırılması amaçlanmıştır. Lyapunov en iyileme yöntemi ile kullanıcıların isterlerini karşılarken toplam sistemfaydasını en iyileyen algoritmalar geliştirilmiştir.Frekans tayfının daha verimli kullanılmasına yarıyacak olan diğer bir teknoloji ise çoklu bilgi iletimi yöntemidir. Bu yöntem ile baz istasyonu iki veya daha fazla kullanıcıya aynı anda hizmet verebilecektir. Bu tezde, çoklu bilgi iletim yöntemi ile yeni çizelgeleme algoritması geliştirilmiş ve bu algoritmanın en iyi oldugu Lyapunov analiz yöntemi ile ıspatlanmıştır.Fırsatçı çizelgeleme algoritmalarının birçok faydası olmasına rağmen, bu tür algoritmaların uygulanabilmesi için baz istasyonunun bütün ağ durumunu bilmesi gerekmektedir. Bu durumlar ise bütün kullanıcıların kanal durumunu ve kuruk uzunluğunun bilinmesini içermektedir. Tezin ikinci bölümü, bu durum bilgisi baz istasyonunda olmadığında geliştirilen çizelgeleme algoritmalarını içermektedir. Bu kısımda üç temelproblem belirlenmiş olup bütün problemler için kullanıcıların kuyruk işleminin dengelenmesi amaçlanmıştır. İlk problem için, kullanıcıların baz istasyonundan veri aldıkları varsayılarak ve kullanıcıların kanal durumlarının zaman içinde bağımsız olarak değiştiği kabul edilerek optimum çizelgeleme algoritması geliştirilmiştir. Ayrıca, bu algoritmanınMax-Weight algoritmasına göre ne kadar performans kazancı sağladığı matematiksel olarak gösterilmiştir.İkinci problemde ise daha gerçekci kanal durumları benimsenip ve baz istasyonun ise sadece belli sayıdaki kullanıcıdan kanal durum bilgisi alabileceği kabul edilip yeni çizelgeleme algoritması geliştirilmiştir. Bu algoritma kanal durum bilgisini tahmin ederek ve bu tahmin değeri ile hangi kullanıcılardan gerçek kanal bilgisini alacağınakarar vermektedir. Daha sonra ise en iyi kullanıcıya kanalı tahsis etmektedir. Bu algoritmanın destekleyebileceği hız bölgesi tanımlanmış ve belirli durumlar için bu bölgematematiksel olarak belirlenmiştir. Son olarak kullanıcıların baz istasyonuna veri iletmek istedikleri durum incelenmiş, kanal ve kuyruk bilgisi olmadan ve bir merkezi sistemegerek duymayan dağıtık çizelgeleme algoritması tasarlanması amaçlanmıştır. Sürekli zamanlı geri adım olduğu varsayılarak geliştirilen algoritmanın merkezi sistem olduğundaki verime erişebileceği gösterilmiştir. Daha sonra ayrık zamanlı geri adım kabul edilerek yeni bir dağıtık çizelgeleme algoritması geliştirilmiş olup bu algoritma için ne kadar masrafgerekeceği hesaplanmıştır.

Next generation wireless and mobile communication systemsare rapidly evolving to satisfy the demands of users. Due tospectrum scarcity and time-varying nature of wireless networks,supporting user demand and achieving high performance necessitate the design of efficient scheduling and resource allocation algorithms. Opportunistic scheduling is a key mechanism for such a design, which exploits the time-varying nature of the wireless environment for improving the performance of wireless systems. In this thesis, our aim is to investigate various categories of practical scheduling problems and to design efficient policies withprovably optimal or near-optimal performance.An advantage of opportunistic scheduling is that it caneffectively be incorporated with new communication technologies to further increase the network performance. We investigate two key technologies in this context. First, motivated by the current under-utilization of wireless spectrum, we characterize optimal scheduling policies for wireless cognitive radio networks by assuming that users always have data to transmit. We consider cooperative schemes in which secondary users share the time slot with primary users in return for cooperation, and our aim is to improve the primary system?s performance over the non-cooperative case. By employing Lyapunov Optimization technique, we develop optimal scheduling algorithms which maximize the total expected utility and satisfy the minimum data rate requirements of the primary users. Next, we study scheduling problem with multi-packet transmission. The motivation behind multi-packet transmission comes from the fact that the base station can send more than one packets simultaneously to more than one users. By considering unsaturated queueing systems we aim to stabilize user queues. To this end, we develop a dynamic control algorithm which is able to schedule more than one users in a time slot by employing hierarchical modulation which enables multi-packet transmission. Through Lyapunov Optimization technique, we show that our algorithm is throughput-optimal. We also study the resulting rate region of developed policy and show that it is larger than that of single user scheduling.Despite the advantage of opportunistic scheduling, thismechanism requires that the base station is aware of networkconditions such as channel state and queue length information of users. In the second part of this thesis, we turn our attention to the design of scheduling algorithms when complete network information is not available at the scheduler. In this regard, we study three sets of problems where the common objective is to stabilize user queues. Specifically, we first study a cellular downlink network by assuming that channels are identically distributed across time slots and acquiring channel state information of a user consumes a certain fraction of resource which is otherwise used for transmission of data. We develop a joint scheduling and channel probing algorithm which collects channel state information from only those users with sufficiently good channel quality. We also quantify the minimum number of users that must exist to achieve larger rate region than Max-Weight algorithm with complete channel state information.Next, we consider a more practical channel models wherechannels can be time-correlated (possibly non-stationary) and only a fixed number of channels can be probed. We develop learning based scheduling algorithm which tracks and predicts instantaneous transmission rates of users and makes a joint scheduling and probing decision based on the predicted rates rather than their exact values. We also characterize the achievable rate region of these policies as compared to Max-Weight policy with exact channel state information. Finally, we study a cellular uplink system and develop a fully distributed scheduling algorithm which can perform overgeneral fading channels and does not require explicit controlmessages passing among the users. When continuous backoff time is allowed, we show that the proposed distributed algorithm can achieve the same performance as that of centralized Max-Weight algorithm in terms of both throughput and delay. When backoff time can take only discrete values, we show that our algorithm can perform well at the expense of low number of mini-slots for collision resolution.