Abstract:
Çizge teorinin çeşitli uygulamalarını inceliyoruz ve bunları OSI modelinin 7 katmanına göre sınıflandırıyoruz. Uygulamaların çoğu renklendirme ve bir MAC katmanı uygulaması olan kanal ataması problemi ile ilgilidir. Diğer uygulamalar yönlendirme, topoloji kontrolü, girişim azaltma, algılama işlev ataması, trellis ve durum diyagramlarıdır. Bir çapraz katman (MAC ve fiziksel katman) uygulaması olarak, kavramsal radyo networklerde, işaret girişim gürültü oranı (IGGO) kısıtı altında spektrum paylaşımı sırasında toplam çıktıyı maksimize etme problemini ele alıyoruz. Renklendirme, fiyat teklifi ve açık arttırma teorisi üzerine kurulu, hem birincil hem de ikincil kullanıcılar için toplam faydayı maksimize etmeye çalışan, aynı zamanda da birincil alıcıların kesintiye uğramaması için IGGO koşulunun geçerli kalmasını sağlayan yeni bir algoritma önermekteyiz. Önerilen algoritma ile sonuçları karşılaştırabilmek için girişim etkisini hesaba katmayan bir greedy algoritmayı da ele almaktayız. Bunun için, birincil alıcının kesintiye uğrama olasılığını da hesaba katan net bir çıktı tanımlamaktayız. Simülasyon sonuçları daha yüksek IGGO kısıtı uygulamanın hem toplam hem de ikincil kullanıcıların faydalarını azaltırken, kanal dağılım başarısını da düşürdüğünü göstermektedir. Diğer taraftan açık arttırma yönteminin algoritmaya ilavesi, toplam ve ayrı ayrı kullanıcıların kazançlarını ciddi biçimde arttırmıştır. Özellikle 20 dB IGGO eşik değerlerine kadar, son derece büyük fayda sağladığı görülmüş, sonuçların girişim kısıtı uygulanmayan greedy yönteme yakın performans gösterdiği görülmüştür. Simülasyon sonuçlarında görülen diğer önemli bir nokta da önerilen ve greedy yöntemlerin net çıktılarının bir IGGO eşik değerinde kesişmeleri ve bu değerden sonra önerilen algoritmanın daha iyi sonuçlar vermesidir. Üstelik kesişmenin gerçekleştiği noktanın üstündeki SINR değerleri pratik SINR değerleri ile son derece uyuşmaktadır. Bu da önerilen mekanizmanın açık bir şekilde üstünlüğünü göstermektedir. We investigate various applications of graph theory and classify them based on 7 layers of OSI. Most of its applications are related to coloring and channel assignment problem (MAC). Other applications can be summarized as routing, topology control, interference reduction, sensing function allocation, trellis and state diagrams. As a cross layer application (MAC and physical layers) of graph theory, we consider the problem of throughput maximization during spectrum allocation under Signal to Interference plus Noise Ratio (SINR) constraint in cognitive radio networks. We propose a novel auction-based channel allocation algorithm, in which graph coloring and bidding theory play an important role and which tries to maximize both total and primary users? utilities while satisfying SINR constraint on primary receivers, without controlling secondary user powers. For comparison, we discuss a greedy algorithm as well, however, which does not consider interference issue. In order to compare results of proposed and greedy algorithms, we define net throughput by taking into account outage probability of primary receiver. Simulation results show that exposing higher SINR (outage) threshold not only decreases total gain and primary users? utilities but also worsens channel distribution performance. On the other hand adding auction mechanism significantly increases total gain throughput and primary user? s utility. Especially till SINR threshold values of 20 dBs, auction provides outstanding performance and proposed algorithm has total throughput results close to those of the greedy one even though no interference constraint is applied in the greedy algorithm. Another noticeable point of simulation results is crossover of net throughputs of proposed and greedy algorithms at a SINR threshold level after which results of ABSA-UNIC and NASA-UNIC are much better. This clearly shows superiority of proposed mechanism.