Solution methods for planning problems in wireless mesh networks

Kablosuz Çokgen Bağlantılı Ağlar (KÇBA) sonlu sayıda telsiz düğümünden oluşur. Bu düğümlerin ağ geçidi adı verilen bir alt kümesi İnternete doğrudan kablo ile bağlı iken, ağ geçidi olmayan noktalar trafiklerini kablosuz ortamda birbirleri üzerinden ağ geçidine aktarırlar. Aynı frekans bandında aynı anda yayınlanan kablosuz iletişim sinyalleri alıcıda birbirine karışabilir ve bu sebeple başarılı veri aktarımını engelleyebilir. Bu problemi engellemek için ağdaki düğümler, farklı zaman dilimlerinde ve farklı frekanslar kullanacak şekilde ayarlanabilir. Ayrıca, bir telsiz düğümünün güç seviyesi ayarlanarak aktarım aralığı değiştirilebilir. Bu çalışmada, verilen bir KÇBA için, düğümlerin lokasyonları, her düğümün talep oranı ve en yüksek güç seviyesi bilindiğinde, düğümlerin trafiklerinin İnternete nasıl taşınacağı problemine odaklandık. Amacımız, kapasiteleri her düğümün talebiyle orantılı bir şekilde ve en küçük oranı en büyükleyerek bölüştürmektir. Bu sebeple, verilen ağ düğümleri arasından ağ geçidi lokasyonlarını seçen, her nodun seçilen ağ geçitleri üstünden trafiklerini belirleyen, kablosuz sinyallerin karışmasını önleyecek şekilde veri aktarımının zaman aralıklarını belirleyen ve aktarımın güç seviyelerine karar veren bir Karışık Tam Sayılı Program (KTSP) önerdik. Bu çalışmada, protokol karışma modeli yerine daha gerçekçi olan fiziksel karışma modelini baz aldık.İlk önerilen KTSP formulasyonu büyük örnekler için olurlu sonuçlar elde edemediğinden farklı yaklaşımlar üzerine yoğunlaştık. Önce bu model üzerine yapıla eklemelerle yeni yöntemler geliştirirken, sonrasında bir kombinatoryal optimizasyon modeli geliştirdik. Önerdiğimiz model ve yöntemleri farklı veri kümeleri üzerinde yapılan deneylerin sonuçları üzerinden karşılaştırdık. Kombinatoryal eniyileme modelinin diğerlerinden daha iyi sonuçlar verdiğini gözlemledik. Anahtar Kelimeler: Kablosuz Çokgen Bağlantılı Ağlar, Tam Sayılı Programlama, Ağ Geçidi Seçimi, Rotalama, Aktarım Zaman Aralığı Ataması.