Bilişsel radyo ağlarında üst sezgiseller ile kanal atama probleminin çözülmesi
Solving channel assignment problem with hyper-heuristics in cognitive radio networks
- Tez No: 397957
- Danışmanlar: DOÇ. DR. AYŞE ŞİMA UYAR
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2015
- Dil: Türkçe
- Üniversite: İstanbul Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 81
Özet
Yazılım Tanımlı Radyolar'ın (Software Defined Radio) son versiyonu olan Bilişsel Radyolar (Cognitive Radio) alanında yapılan çalışmalar giderek artmaktadır. Bilişsel Radyolar, çevrelerinde olan bitenden haberdar olmaları için tasarlanmış yazılımlardır. Böylece, çevresinden geri bildirim alarak öğrenme yapar ve topladığı verileri kullanarak çevreye uyum göstermeye çalışır. Bilişsel radyoların en büyük avantajı, lisanslı olmamasına rağmen lisanslı sistemlerde çalışabilmesidir. Kablosuz iletişimdeki hızlı büyüme sonucunda hem lisanslı hem de lisanssız frekans spektrumundaki talep giderek artmaktadır. Son yapılan çalışmaların sonuçlarına göre, sabit spektrum atama politikası, spektrum kullanımının çok zayıf kalmasına sebep olmaktadır. Bu sorunu çözmek için Bilişsel Radyo teknolojisi,“Beyaz Boşluk”ya da“Spektrum Boşluğu”da denilen, işgal edilmemiş spektrum bantlarının kesikli periyotlarına erişimi sağlayabilmek adına iyi sonuçlar vermeye başlamıştır. Bilişsel radyo ağlarının en önemli gerekliliği spektrum boşluklarını algılamaktır. Bilişsel radyoların önemli bir özelliği ise başka kullanıcıları rahatsız etmeden kullanılmayan spektrumları algılayıp, paylaşmaktır. Spektrumun hangi aralıklarının uygun olduğunu belirler ve lisanslı kullanıcılar spektrumu kullandığı sırada bunu tespit ederler. Spektrum algılama, bilişsel radyonun spektrum boşluklarını tespit etmesine olanak sağlar. Merkezi işbirlikli algılamada, Baz İstasyonu adı verilen bir yapı işbirlikli algılamanın üç adımlı sürecini kontrol eder. İlk olarak baz istasyonu bir frekans bandı ya da kanalı seçer ve tüm Bilişsel Radyolara yerel algılama yapmaları talimatını verir. İkinci olarak, tüm Bilişsel Radyolar topladıkları bilgileri kontrol kanalı üzerinden baz istasyonuna rapor ederler. Üçüncü ve son olarak da, birleştirme merkezi, bu verileri kullanarak birincil kullanıcının varlığı hakkında karar verir ve verdiği bu kararı tekrardan Bilişsel Radyolara geri dağıtır. Bilişsel Radyo Ağları terminolojisinde, Birincil Kullanıcı, bir spektruma atanmış olan lisanslı kullanıcı anlamına gelirken, İkincil Kullanıcı ise spektruma erişebilmesi için izni olmayan lisanssız kullanıcı anlamına gelmektedir. Bu sebepten dolayı, ikincil kullanıcılar bilişsel radyo teknolojisi kullanarak, spektrum birincil kullanıcılar tarafından kullanılmadığı sırada hatta erişim sağlarlar. Bir bilişsel radyo ağı temel olarak birincil ağlar ve ikincil ağlardan oluşur. Normalde, birincil ağlar, ikincil kullanıcılar ile spektrum paylaşımı yapmazlar. Hatta, böyle bir özellikleri de yoktur. Diğer taraftan, ikincil ağların, kanalları ikincil kullanıcılara atamalarını sağlayan bir baz istasyonu vardır. Literatürde bir çok bilişsel radyo ağı çeşidi vardır. Bu çalışmada, Merkezi bilişsel radyo ağları üzerinde durulmuştur. Kanal Atama Problemi, bilişsel radyo ağlarında çakışmaları önlemek için kullanılan temel bir tekniktir. kanal atamanın amacı kanal kullanım oranını maksimize etmek için kanalların ikincil kullanıcılara da atanmasıdır. kanal atamada, kanal kullanım oranı, ikincil kullanıcılara ait veri ile birincil kullanıcılara ait veri aynı anda iletime geçirilerek artırılabilir. Doğa Esinli Sezgiseller, gerçek doğadaki bazı olaylar ve onların işleyişinden esinlenilmiş mekanizmalardır. Doğa esinli sezgisellerin son yıllarda popülerleşmesinin sebebi olarak bir çok optimizasyon probleminin oldukça karmaşık olmasıdır. Karınca kolonisi optimizasyonu, en çok kullanılan sürü zekası tekniklerinden biridir ve gerçek karıncaların davranışlarından esinlenilmiştir. Karınca kolonisi optimizasyonu yönlendirme problemleri, atama problemleri, zamanlama ve sıralama problemleri ve altküme problemleri gibi bir çok katışımsal optimizasyon problemlerine oldukça başarılı bir şekilde uygulanmıştır. Adaptif İteratif Yapıcı Arama, karınca kolonisi optimizasyonunun tek karınca ile uygulanmış farklı bir formudur. Karınca kolonisi optimizasyonunda olduğu gibi Adaptif İteratif Yapıcı Aramada da karınca bir çözüm adayı oluşturur ve sonraki iterasyon için feromon tablosunu günceller. Bu çalışmamızda, AİYA'yı bir ÜS mekanizması olarak kullandık. Üst sezgiseller, düşük seviyeli sezgisellerin arama uzayında çalışan metotlardır. Dinamik ortam problemlerini çözmek için şimdiye kadar bir çok yöntem denenmiş ve belli sonuçlar alınmıştır. Ancak, bu yöntemlerin de bazen ortamın durumuna göre birbirlerinden daha iyi oldukları anlar görülmüştür. İşte bu noktada, üst sezgiseller, yani“sezgisel seçen sezgisel”teknikler devreye girer. Bu tezde, kanal atama problemini çözmek için adaptif iteratif yapıcı arama algoritmasını kullanan bir üst sezgisel tasarladık. söz konusu tasarım altı farklı düşük seviyeli sezgisel içermektedir. Yaptığımız çalışmayı test etmek için 72 farklı test örneği oluşturduk ve her birini ayrı ayrı hem önerdiğimiz algoritma ile hem de her bir düşük seviyeli sezgisel ile ayrı ayrı çözdük. Aldığımız sonuçlara baktığımızda, üst sezgisellerin, bilişsel radyolarda kanal ataması problemi için oldukça başarılı olduğunu gözlemledik.
Özet (Çeviri)
Wireless networks communicate with each other using radio spectrum bands which are assigned to license owners. Traditionally, there is a fixed spectrum assignment policy issued by the governments or the communication companies. Because of the fixed spectrum assignment policy, a large portion of the spectrum stays unused. To utilize these unused spectrum portions, the idea of Cognitive Radio was proposed by J.Mitola. The aim of Cognitive Radio is maximizing spectrum utilization in an intelligent way. By doing that, Cognitive Radio enables the unlicensed users to also access the spectrum. However, this process should be done in such a way that when an unlicensed user attempts to use a spectrum, it should not interfere with the licensed users. In Cognitive Radio Networks terminology, a primary user is a licensed user which has been assigned a spectrum, while a secondary user is an unlicensed user which does not have a license to access a spectrum. For this reason, Secondary users use the cognitive radio technology to access the spectrum when the spectrum is not occupied by the primary user. This unoccupied spectrum portion is represented by a spectrum hole or white space. In Cognitive Radio Networks, primary users are known as the owners of a spectrum. They can use the spectrum whenever they want. On the other hand, secondary users can use the spectrum if and only if the spectrum is not currently occupied by the primary user. However, recently, a new data transmission protocol, which allows a primary user and a secondary user to work cooperatively, was proposed. In this method, a primary user releases a portion of the bandwidth to the secondary user to transmit its own data in exchange for making the secondary user to also relay the primary user's data. Channel Assignment is a fundamental technique to control interference in the cognitive radio networks. The aim of channel assignment is to assign channels to secondary users in order to maximize channel utilization. In channel assignment, the percentage of channel utilization can be increased by transmitting secondary user's data and primary user's data simultaneously. In this study, we use hyper-heuristics to solve the channel assignment problem. In literature, channel assignment algorithms try to optimize various objectives such as utilization optimization, interference minimization, network overhead minimization, throughput maximization, etc. Our objective is to maximize channel utilization. Hyper-heuristics are methods that work on the search space of low level heuristics rather than on the search space of solution candidates. Single point based search heuristics or population based meta-heuristics can serve as hyper-heuristics. In this study we use a single point based search heuristic, namely Adaptive Iterated Construction Search. Hyper-heuristics are defined as heuristics that select heuristics. A more recent definition of Hyper-heuristics is as:“A hyper-heuristic is an automated methodology for selecting or generating heuristics to solve hard computational search problems”. Hyper-heuristics work on a search space of low-level heuristics as opposed to working on the search space of solutions. There are two types of Hyper-heuristics, i.e. Selection Hyper-heuristics and Generation Hyper-heuristics. Selection Hyper-heuristics choose from existing heuristics defined for a problem, while generation Hyper-heuristics generate new heuristics fora given problem by using components of existing heuristics. In this study we work with selection Hyper-heuristics, so for the rest of the paper we will use Hyper-heuristics to denote selection Hyper-heuristics. Single point based search approaches as well as population based meta-heuristics, such as ant colony optimization algorithms, can be used as Hyper-heuristics. In this study we use a single point based search approach, namely Adaptive Iterated Construction Search. Adaptive Iterated Construction Search can be considered as being a simple Ant Colony Optimization algorithm which works using a single ant. In our channel assignment problem model, both primary users and secondary users can transmit their data simultaneously on the same channel. In this study, we assume an underlying network architecture. More specifically, a secondary user can utilize the vacant channel as long as it does not disturb the primary user. To solve the channel assignment problem, we use a Hyper-heuristic approach based on Adaptive Iterated Construction Search. Given a traffic matrix, i.e. the primary users' spectrum usage information for each channel and for each time slot, the Hyper-heuristic aims to assign a channel to the secondary users for each time slot. To accomplish this, first, the Hyper-heuristic constructs a solution candidate which includes a set of low-level heuristics. Then, each low-level heuristic in the solution candidate is invoked in the order given by the solution candidate, to assign a channel to a secondary user. Next, the fitness value of the resulting assignments is calculated. In this study, we proposed a solution approach to the channel assignment problem in cognitive radio networks which uses the Adaptive Iterated Construction Search algorithm as a Hyper-heuristic to select the secondary users at each step of the channel assignment. To test the proposed approach we generated several test instances based on four parameters as follows: (i) Traffic matrix: We generated the traffic matrix using the Poisson distribution to determine the arrival times of the packets. (ii) Packet counts: We used two different packet counts in the experiments. (iii) Number of secondary users: Four different settings were used for this parameter. (iv) Number of channels: Three different settings were used while generating the test instances. By using the above parameters we created 72 different test instances. We evaluate the approaches tested in this study based on two criteria: (i) Channel Assignment Success Rate shows the success rate of an approach. It is calculated as the percentage of feasible assignments to the total number of channels. (ii) Channel Utilization Rate shows the utilization rate of the channels at time t, weighted by the Channel Assignment Success Rate. To show the effectiveness of the Hyper-heuristic approach which uses six low-level heuristics, each of the 72 test instances was solved with the proposed Hyper-heuristic (Adaptive Iterated Construction Search) as well as each low-level heuristic separately. Since Adaptive Iterated Construction Search is a stochastic algorithm, we ran the Adaptive Iterated Construction Search algorithm 20 times independently for each test instance. For this reason, in our result plots, we show the average value of 20 runs for Adaptive Iterated Construction Search. The results are shown as Weighted Channel Utilization Rates over Time. The results show that among the low-level heuristics, Max. Degree and Max. Priority low-level heuristics are the best performers with regard to channel utilization rate in all cases. Similarly, Min. Request is the best performer among all low-level heuristics with regard to channel assignment success rate. However, the channel utilization rate for this low-level heuristic is very low. The reason for this behavior is that this low-level heuristic chooses the secondary users in the increasing order of their requests. It is easier to find a channel assignment for smaller requests, therefore the channel assignment success rate of this low-level heuristic is high. However, since it assigns channels to those secondary users with lower requests first, the channel assignment rates of the assigned channels do not increase much after the assignments. Min. Degree, Max. Request and Random are the worst performing low-level heuristics. In the results given in the thesis, Adaptive Iterated Construction Search is either the best performer or it has a performance of similar quality to the well performing low-level heuristics.
Benzer Tezler
- Bilişsel radyo ağlarında çok ölçütlü karar verme yöntemlerine dayalı yeni bir spektrum yönetim modeli
A novel spectrum management model based on multi criteria decision making methods in cognitive radio networks
ZHALEH SADREDDINI
Doktora
Türkçe
2018
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolKaradeniz Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ TUĞRUL ÇAVDAR
- Cooperative spectrum sensing and radio environment map construction in cognitive radio networks
Bilişsel radyo ağlarında işbirlikçi spektrum algılama ve frekans haritası oluşturma
HÜSEYİN BİRKAN YILMAZ
Doktora
İngilizce
2012
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolBoğaziçi ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. TUNA TUĞCU
- Providing QoS to secondary users employing VoIP applications in cognitive radio networks
Bilişsel radyo ağlarında IP üzerinden ses ileten ikincil kullanıcılara hizmet kalitesi oluşturulması
ESRA HATİCE DEMİRTAŞ
Yüksek Lisans
İngilizce
2012
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. SEMA FATMA OKTUĞ
- Resource allocation for underlay cognitive radio networks
Taban yaklaşımlı bilişsel radyo ağlarında kaynak düzenlemesi
MUTHANA HATEM DAHHAM AL JANABI
Yüksek Lisans
İngilizce
2019
Elektrik ve Elektronik MühendisliğiÇankaya ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ ÖZGÜR ERGÜL
- Design and performance analysis of relay-based cooperative overlay cognitive radio networks
Röle tabanlı işbirlikli üstüne serme bilişsel radyo ağlarının tasarımı ve başarım analizi
SAID ABDELMONEIM ABDELWAHAB EMAM
Doktora
İngilizce
2018
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
Prof. Dr. MEHMET ERTUĞRUL ÇELEBİ