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
Yazar: EMRULLAH GAZİOĞLU
Danışman: DOÇ. DR. AYŞE ŞİMA UYAR
İstanbul Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Yüksek Lisans, 2015
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control
Dizin: Metasezgiseller = Metaheuristics

Ö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.

Abstract:
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.