Klasik ve ağ kodlamalı OFDMA sistemlerde alt-taşıyıcı atama
Subcarrier allocation in conventional and network coded OFDMA systems
Yazar: BUĞRA ENGİN
Danışman: PROF. DR. İBRAHİM ALTUNBAŞ
İstanbul Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Elektronik ve Haberleşme Mühendisliği Ana Bilim Dalı / Telekomünikasyon Mühendisliği Bilim Dalı
Derece: Yüksek Lisans, 2015
Konu: Elektrik ve Elektronik Mühendisliği = Electrical and Electronics Engineering
Dizin: Gauss ağ modeli = Gaussian network model ; Hücresel ağlar = Cellular networks ; Kablosuz ağlar = Wireless networks ; OFDM = Orthogonal frequency division multiplexing ; Rayleigh sönümü = Rayleigh fading ; Telefon ağları = Telephone networks ; Telefon ağları = Telephone networks ; Telekomünikasyon ağı = Telecommunication network ; İletişim şebekeleri = Communication networks

Özet:
Telsiz haberleşmedeki performansı etkileyen en temel unsurlardan olan sönümleme, güvenilir ve kaliteli bir iletişim için problem teşkil etmektedir. Sönümlemenin yanında iletim hızı, bandverimliliği, kaynak ataması gibi unsurlar da sistemlerin performansını büyük ölçüde etkilemektedir. Sönümleme etkisini azaltmak için kullanılan tekniklerden biri olan işbirlikli çeşitleme sayesinde haberleşme sistemlerinin hata performansı, iletim hızından kayıp karşılığında iyileşmektedir. Ağ kodlama tekniği, işbirlikli sistemlerin iletim hızındaki bu kaybı önlemek amacıyla geliştirilmiş ve üzerinde son zamanlarda yoğun biçimde çalışmalar yapılan tekniklerden biridir. Ağ kodlamanın geliştirilmiş bir versiyonu olan rastgele ağ kodlamada ağ düğümlerine gelen veri paketleri, rastgele üretilen katsayılar ile çarpılarak kodlanmaktadır. Böylece rastgele ağ kodlamada, paket kaybına ve gecikmeye karşı daha çok direnç sağlanmaktadır. Aynı zamanda rastgele ağ kodlama ile sistemlerin iletim oranı ve bandverimliliğinin de iyileşmesi sağlanmaktadır. Telsiz haberleşmede, iletim oranı ve bandverimliliği ile yakından ilişkili olan önemli bir problem de kaynak ataması problemidir. Sınırlı frekans bandının sistemde bulunan kullanıcılar tarafından olabildiğince verimli bir şekilde kullanılması gerekmektedir. 

OFDM (Orthogonal Frequency Division Multiplexing, Dik Frekans Bölmeli Çoğullama) tekniği, frekans seçici kanallar üzerindeki iletişim güvenilirliği ve esnekliğini geliştirme potansiyeli nedeniyle; halihazırdaki ve gelecek nesil haberleşme sistemleri için önem teşkil etmektedir. OFDM'in çok kullanıcılı iletişim için önemli bir uygulaması da OFDMA'dir (Orthogonal Frequency Division Multiplexing Access, Dik Frekans Bölmeli Çoğullama Erişimi). Özellikle çok kullanıcılı sistemlerde mevcut kaynakları, bandgenişliği sınırlamaları altında en uygun şekilde kullanmak gerekmektedir. Gelişen teknolojinin ve gezgin cihazları kullanan kullanıcı sayısının artmasıyla kaynak ataması, günümüzde büyük bir problem olarak karşımıza çıkmaktadır. OFDMA sistemlerinde kaynak ataması ile ilgili olarak alt-taşıyıcılar kullanılmaktadır ve veriler bu alt-taşıyıcılar aracılığıyla iletilmektedir. Kullanıcılara en uygun şekilde alt-taşıyıcı ataması yapılarak mevcut kapasite en uygun biçimde kullanılabilmektedir. Bir sistemde, alt-taşıyıcı ataması yaparak kullanıcıların mümkün olduğunca az kesinti durumunda kalmaları sağlanmaktadır. Alt-taşıyıcı atamasına ilişkin olarak, bir OFDMA sistemi, diyagram kuramı kapsamındaki rastgele ikili diyagram modeli ile gösterilebilmektedir. Rastgele ikili diyagramlarda,  maksimum eşleme yöntemleri ile mevcut alt-taşıyıcılar kullanıcılara, en az sayıda kullanıcıyı kesintide bırakacak şekilde atanabilmektedir. Her kullanıcı, alt-taşıyıcı atanması bakımından aynı fırsata sahip olmaktadır. Rastgele ikili diyagramlarda maksimum eşleme ile alt-taşıyıcı ataması yapmak için Hopcroft-Karp algoritmasını kullanarak geliştirilen RVRHK (Random Vertex Rotation based Hopcroft-Karp, Hopcroft-Karp tabanlı Rastgele Düğüm Döndürmesi)  algoritması kullanılmaktadır. Elde edilen sonuçlara göre, sadece maksimum eşleme algoritmaları ile alt-taşıyıcı ataması yaparak çeşitleme kazancı elde edilebilmektedir. RVRHK algoritmasının yanında, daha genel durumlar için en uygun alt-taşıyıcı ataması yapılması ile ilgili olarak ℋ-eşleme yaklaşımından yararlanılmıştır. ℋ-eşleme yaklaşımının ele alındığı alt-taşıyıcı atama algoritması olarak RVRHK'nın daha geliştirilmiş hali olan R^2 EHK (Random Rotation and Expansion based Hopcroft-Karp, Hopcroft-Karp tabanlı Rastgele Döndürme ve Çoğullama) algoritması kullanılmaktadır. 

Bu tezde, literatürde ilk olarak RVRHK ve R^2 EHK algoritmalarının sağladığı performans Nakagami-m kanallar için incelenmiştir. Bunun yanında, farklı kullanıcı ihtiyaçlarına uygun biçimde, Çoklu-R^2 EHK algoritması geliştirilmiştir. Gerçekten de, faydalanılan çalışmaların hepsinde kullanıcıların karşılamaları gereken iletim oranı her zaman sabit olarak kabul edilmiştir. Bir OFDMA sistemindeki kullanıcıların farklı servisleri kullanmaları durumunda, her kullanıcının farklı bandgenişliği ihtiyacı olacağından her kullanıcıya atanması gereken alt-taşıyıcı sayısı ve de her kullanıcının karşılaması gereken iletim oranı farklı olmaktadır. Bu nedenle, literatürde ele alınmayan ve diyagram kuramı ile geliştirilen yeni atama yöntemleri geliştirilerek kullanıcılara farklı sayıda alt-taşıyıcı atanması konusu ve kullanıcıların karşılamaları gereken iletim oranlarının farklı olma durumları da tez kapsamında ele alınmaktadır. Sabit sayıda alt-taşıyıcı atamasına göre farklı sayılarda alt-taşıyıcı atamasında, daha az sayıda alt-taşıyıcı ataması yapılan kullanıcılar, sistemin genel performansını belirlemede baskın olmaktadırlar. Kullanıcıların karşılaması gereken iletim oranı sabit iken, sistemdeki herhangi bir kullanıcıya diğerlerinden çok daha az sayıda alt-taşıyıcı ataması yapıldığında o sistemin genel performansı, her kullanıcıya sabit sayıda alt-taşıyıcı ataması yapılan sistemin genel performansına göre kötüleşmektedir. Buradaki amaç, kullanıcıların ihtiyaçlarına yönelik atama yapmak olduğundan performanstan ödün verilmektedir; fakat kullanıcıların ihtiyaçlarına göre başarılı bir şekilde alt-taşıyıcı ataması yapılabilmektedir. Ayrıca, kullanıcıların karşılaması gereken iletim oranlarının, atanacak olan alt-taşıyıcı sayısı ile orantılı olarak belirlenmesi durumunda tüm kullanıcılar aynı performansı vermektedirler. 

Bu tezin son bölümünde, klasik OFDMA sistemi için yapılan analizler, ağ kodlamalı OFDMA sistemlerine genelleştirilmiştir. Ağ kodlamalı OFDMA sistemlerinde, alt-taşıyıcıları kullanıcılara bağlayan yolları göstermek amacıyla ikili bir hiperdiyagram modeli önerilmektedir. Hiperdiyagramlar üzerinden ağ kodlamalı OFDMA sistemlerinde, kullanıcıların kesinti olasılıkları en az olacak şekilde alt-taşıyıcı ataması yapılmaktadır. Ağ kodlamalı bir OFDMA sisteminde, röle kullanımından dolayı elde edilen çeşitleme derecesi, klasik OFDMA sistemlerinde elde edilen çeşitleme derecesine göre artmaktadır. Böylece, kesinti olasılığı da oldukça iyileşmektedir. Tezden elde edilen sonuçlara göre sistemdeki kullanıcıların veri türlerine ve iletim hızlarına göre alt-taşıyıcı ataması yaparak sistemdeki bandgenişliği en uygun şekilde kullanılabilmektedir ve sistem verimi olabildiğince artırılmaktadır. Ağ kodlamalı OFDMA sistemleri daha karmaşık yapıya sahip olduğundan kaynak ataması, hız ve bandverimliliğinin hedeflenen şekilde sağlanması için kullanıcıların ihtiyaçları doğrultusunda alt-taşıyıcı ataması yapmak çok büyük avantajlar sağlamaktadır. Ağ kodlama tekniklerinin, gelecek nesil haberleşme sistemlerinde yer alacağı düşünüldüğünde, bu tez kapsamında önerilen yöntemler ve elde edilen sonuçlar, OFDMA kullanan yeni nesil telsiz haberleşme sistemlerinde alt-taşıyıcı ataması konusuna farklı bir bakış açısı getirmekte ve yeni çalışmalar için fikirler vermektedir.

Abstract:
In wireless communications systems, the fading effect, one of the basic factors which degrades the performance, is an important problem for reliable and qualified transmission. Thanks to channel coding and diversity techniques which are used to reduce fading effect. Cooperative diversity is one of the diversity techniques and by using this technique, error performance is improved by sacrificing the data rate. It is a solution for the increasing number of users and the increasing demand for high quality wireless services. The cooperation among mobile users of a wireless system has the potential to provide an increased capacity in comparison with the systems without using cooperation. Network coding is a technique developed to avoid the loss of data rate for cooperative systems and there have been many ongoing researches about this topic in recent years. It is a useful technology that can increase  the total throughput of wireless networks and allows intermadiate nodes in networks to encode several received packets into a coded packet before forwarding. In random network coding that is a more advanced version of network coding, data packets are encoded by multiplexing with random generated coefficients. Thus, random network coding is more robust against the packet loss and latency. At the same time, transmission rate and bandwidth efficiency of the systems are improved by using this technique. In wireless communications, a problem which is closely related with transmission rate and bandwitdh efficiency is resource allocation problem. Basic principle of resource allocation is to maximize the system capacity. By dynamically allocating resources to users in a system, system capacity maximization can be done. Therefore, it is important that restricted frequency band must be used by users effectively as much as possible.

OFDM is a multiplexing technique which subdivides the available bandwidth into multiple orthogonal frequency subbands and has an importance for existing systems and new generation communications systems due to its ability to improve the transmission efficiency and reliability in frequency selective fading channels. OFDM systems are able to maximize spectral efficiency without causing adjacent channel interference. One of the important applications of OFDM for multi-user communications is OFDMA and it is a multiplexing scheme that provides multiplexing operation of user data onto the subcarriers. Especially in the multi-user systems, available sources must be used optimally under bandwidth limitations. The source allocation comes up as a more important problem in recent years due to increasing number of users who use the mobile devices. In OFDMA systems, user data packets are transmitted via subcarriers. Available capacity is used effectively by allocating subcarriers to the users optimally. By this way, outage probability of users can be minimized. 

In an OFDMA system, if instantaneous channel capacity is lower than a target transmission rate due to frequency selective slow fading, subcarriers may be in outage. Besides, if all subcarriers for a user are in outage, that user will also be in outage. So, allocating non-outage subcarriers to users is an important problem for OFDMA systems. In order to solve this allocation problem, an OFDMA system can be represented by using random bipartite graph model which is a subject of graph theory. Random bipartite graphs can be used to analyse the multi-user subcarrier allocation problem over frequency selective slow fading channels. In random bipartite graphs, subcarriers can be allocated to users by employing maximum matching algorithms. This minimizes the user outage probability. Moreover, each user have the same opportunity in terms of subcarrier allocation. In other words, the fairness between the users is guaranteed. RVRHK algorithm developed based on the Hopcroft-Karp algorithm can be used for subcarrier allocation with maximum matching in random bipartite graphs. According to the results obtained in the literature, diversity gain can be achieved via maximum matching algorithms. RVRHK algorithm takes advantage of the maximum matching technique to resolve the user conflicts in OFDMA systems. In addition, the channel state information needed by this algorithm is only 1 bit/subcarrier/user to resresent the outage scenario. This algorithm allocates only one subcarrier to each suitable user. For more general cases, H-matching approach is utilized. An improved version of RVRHK algorithm is R^2 EHK algorithm where ℋ -matching approach is utilized. In order to guarantee the fairness between users, a randomly rotation operation is performed among users in random bipartite graph for both RVRHK and R^2 EHK algorithms. By using H-matching approach in R^2 EHK algorithm, equal number of multiple subcarriers can be allocated to users in an OFDMA system as long as each user which is not in outage has same number of subcarriers.

In this thesis, the performances of RVRHK and R^2 EHK algorithms are investigated for Nakagami-m channels for the first time in literature. The obtained results show that diversity order of the OFDMA systems increases with m parameter for Nakagami-m fading channels. By this way, outage probability is also improved. Besides, Multi-R^2 EHK algorithm is developed in accordance with requirements of users. Indeed, in subcarrier allocation solutions via random bipartite graphs, it is generally assumed that user transmission rates are fixed. In case of users in an OFDMA system utilize different services, they may have different bandwidth requirements. So, the number of subcarriers to be allocated to users and the user transmission rates may be different. Therefore, different numbers of subcarrier allocation problem is examined under two headings: fixed bandwidth efficiency per user and variable bandwidth efficiency per user. For the first topic, a fixed bandwidth efficiency is promised for each user, but they have different numbers of subcarriers. So, the user transmission rates will be different according to number of subcarriers allocated. For the second topic, the bandwidth efficiencies of the users will be variable.

In this thesis, a new version of R^2 EHK algorithm, which allows different numbers of subcarrier allocation to users, is developed. The proposed algorithm uses the H-matching approach. By using this new algorithm, different numbers of subcarrier allocation can be done optimally according to the user requirements at the cost of a degradation in the outage performance. The results obtained for fixed bandwidth efficiency by using Multi-R^2 EHK algorithm show that the outage probability of users with more number of subcarriers is lower than the others. In addtion, it is shown that the users with less number of subcarriers are dominant in determining general outage performance of the system compared to the users with equal number of subcarriers. If the bandwidth efficiency is assumed to be fixed, when a user in the system has less number of subcarriers than the others, its user outage performance becomes worse. It is also observed from the results obtained for variable bandwidth efficiency by employing Multi-R^2 EHK algorithm, a users with more number of subcarriers should satisfy a higher transmission rate. In this case, the outage probability of this user will be higher than other users. In addition, if the bandwidth efficiency for each user is changed proportionally with the number of subcarriers, all users will have same outage performance.

In the last chapter of this thesis, the analyses given for traditional OFDMA systems are generalized to network coded OFDMA systems. A new bipartite hypergraph model is proposed to represent the connections between users and user/relay subcarriers in the network coded OFDMA systems. As in aforementioned techniques, subcarrier allocation can be done via bipartite hypergraphs by minimizing the user outage probabilities. The proposed Multi-R^2 EHK algorithm is used for different numbers of subcarrier allocations. Since one of the main objectives of network coding systems is to improve the transmission rate and bandwidth efficiency, it is important to allocate different numbers of subcarriers for fixed and variable bandwidth efficiency cases in network coded OFDMA systems. Utilizing the relay in the network coded OFDMA system, the diversity order and therefore outage performance can be increased with respect to the traditional OFDMA system. Moreover, available bandwidth can be used efficiently according to the user requirements by this way. Considering the obtained results, it can be argued that the proposed techniques in this thesis will provide a different perspective and new insights into the subcarrier allocation problem of traditional and network coded OFDMA systems.