3N Ağlarda Hücre Planlama

1. GİRİŞ

Hücre planlama sorunu, gerekli baz istasyonu sayısının belirlenmesi, baz istasyonlarının kurulacağı alanların tespit edilmesi ve baz istasyonlarının hangi alanlar içindeki kullanıcılara hizmet vereceği konularını kapsamaktadır. Burada planlama yapılırken baz istasyonlarının kurulum maaliyetlerinin en aza indirilmesi amaçlanmaktadır. Bu çalışmada 3N ağlar  üzerinde hücre içi planlama için bir yöntem önerilmiştir. Şekil 1 ’de 3N mimarisinin tüm yapısı görülmektedir. Kırmızı dikdörtgen içinde  bulunan kısım ise hücre planlama alt bölümüdür.

3N ağlarda karşılaşılan hücre planlaması sorunları, 2N ağlara göre farklılık göstermektedir. 2N ağlarda bir baz istasyonunun kapasitesi yani aynı anda aktif olan kullanıcı sayısı limiti sabittir.3N ağlardaki baz istasyonu yeri belieleme problemi sadece bir kapsama alanı problemi olarak düşünülmemeli, ayrıca bir kapasite problemi oldugu anlaşlmalıdır [4]. 3N ağlarda ise uzaklık-yakınlık sorunu nedeniyle, baz istasyonuna yakın olan bir kullanıcı uzaktaki kullanıcının sinyalini ezebilir ya da bozabilir. Bu soruna 3N ağlarda önerilmiş çözümler bulunmaktadır [1]. [1]’de 3N ağlardaki planlama sadece yer-baz istasyonu bağı göz önünde bulundurularak yapılmıştır. ( Baz istasyonu – yer bağını modelleyen çalışmalar da [5] ve [6]’da mevcuttur. )

Planlama sorunu üzerine literatürde çok sayıda değişik öneriler mevcuttur. Bunlardan [2]’de planlama sorunu daha evrensel olarak ele alınmıştır. Sorun üç alt başlıkta toplanmıştır; hücre, erişim ağı ve çekirdek ağ. Evrensel buluşsal yöntemlerle üç alt bölüme aynı anda çözüm aranmıştır. Ayrıca [2]’de, sorunun genel olduğu ve bütün alt sorunlar aynı anda çözüldüğünde ancak en iyi sonuca ulaşılacağı öne sürülmüştür

1 :3N mimarisi [3]

2. GÜÇ KONTROL MEKANİZMASI

Yukarıda bahsettiğimiz sorunu çözebilmek için çalışmamızda [1]’de önerilen güç kontrol mekanizmasını kullanılmıştır. Bu mekanizmaya göre, kullanıcılardan baz istasyona ulaşan sinyalin gücü bütün kullanıcılar için eşit olmalıdır. Şekil 2 ’de görüldüğü gibi uzaktaki bir kullanıcı yüksek güç ile yakındaki kullanıcı ise düşük bir güç ile yayın yapmalıdır.

2 :Güç kontrol mekanizması

3. AMAÇ FONKSİYONU VE KISITLAMALAR

Kullandığımız modelde [1]‘deki model referans alınmıştır.

• S = { 1, …, m} olası baz istasyonu kurulum alanı kümesi.
• Her baz istasyonun c_j  j E S kadar kurulma masrafı var.
• Kullanıcıların yerleştiği  I = {1, … , n} deneme noktaları mevcut.
• Her deneme noktası  i E I ERLANG cinsinden d_i  kadar bir trafiğin ağırlık merkezi  olarak görülür.
•  Bir deneme noktasına i E I, en fazla u_ikadar aynı anda bağlantı olabilir.
• Amaç: Baz istasyon kurma masraflarını düşürmek.
• Kısıtlamalar:
• Her kullanıcı sadece bir baz istasyonuna bağlı olabilir.
• Bir olası baz istasyonu kurulum alanı, sadece bir baz istasyonu tarafından doldurabilir. Bir kurulum alanına birden fazla baz istasyonu kurulamaz.
• Baz istasyonuna olan bağlantılar baz istasyonu kapasitesini aşamaz.
• Baz istasyonunda oluşan gürültü belli bir eşik değerinden fazla olamaz.
• Her kullanıcı en fazla güç kontrolünün izin verdiği aralıktaki güçlerde yayın yapabilir.

4. ÇÖZÜM YÖNTEMİ

Bu çalışmada yukarıda belirttiğimiz problem K-means buluşsal yöntemi (Lloyd algoritması [10]) ve Benzetimli Tavlama [9] yöntemi kullanılarak çözülmeye çalışılmıştır.

4.1 K-means

Bu yöntem gerekli baz istasyonu sayısını(K) bulmak için başlangıçta olası en düşük K değeriyle başlayıp, mantıklı bir sonuç buluncaya dek K rakamının arttırılmasına dayanmaktadır. Koyulan kısıtlamalara uyan en küçük K’ye ulaşıldığında algoritma sona ermektedir.

Bütün K-means yöntemlerinde olduğu gibi bu uygulamada da başlangıç noktalarının seçimi sonucu büyük ölçüde etkilemektedir. Bu nedenle uygulanan algoritmada başlangıç noktalarının seçimi için bir yöntem geliştirilmiştir. Test senaryolarında kare alanlar kullanıldığı düşünülerek, başlangıç çözümü bu alanın ortasına bir daire çizilerek yapılmıştır. Şekil 3’te de görüldüğü gibi okların gösterdiği noktalar başlangıç noktaları olarak belirlenmiştir ve koordinatları aşağıdaki formulasyonla belirlenmiştir. Her okun gösterdiği noktaya en yakın olan kurulum alanı başlangıç baz istasyonu olarak seçilmiştir.

Xi= d/2 + d/4*(cos((360/k)*i)),
Yi= d/2 + d/4*(sin((360/k)*i))

3 :Başlangıç çözümü

4.2 Benzetimli tavlama

Hücre planlama sorunununa K-means yöntemi dışında, rastgele seçilmiş baz istasyonlarıyla oluşturulmuş mantıklı bir çözümü benzetimli tavlama yöntemiyle geliştirmeye dayanan bir yöntem önerilmiştir. Şekil 4’de bu yöntemin akış diyagramı gösterilmiştir

Şekil 4 : Benzetimli tavlama yöntemi akış diyagramı

Kullanılan komşu sonuca giden hareketler ise (olasılıkları yanlarında yazılı):

• Bir baz istasyonunu sökme (p = 0.25)
• Bir (veya birden fazla) baz istasyonunu yerinden  söküp başka bir yere nakil etme (p = 0.25)
• Bir baz istasyonuna bağlı kullanıcıyı başka baz istasyonunda yer varsa oraya taşıma, veya oradaki başka bir kullanıcıyla değiş tokuş etmedir. (p = 0.5)

Bilindiği gibi bir BT yönteminde soğutma işlemi parametreleri büyük önem taşımaktadır. Seçilen değişkenlerin değerleriyle algoritma sonucu birebir ilişki içerisindedir. Bilindiği gibi bu değişkenler; başlangıç sıcaklığı, sıcaklığın ne zaman ve ne kadar düşürüleceği ve ayrıca algoritmanın ne zaman durdurulacağıdır.
Başlangıç sıcaklığı yapılan dört hareketten sonra, bunların arasındaki en büyük sıcaklık değişimini alarak belirlenmiştir. Bu en büyük değişikliğe göre kabul etme olasılığını 0.99 yapan sıcaklık ilk sıcaklık olarak belirlenmiştir (Ilk sıcaklık genelde ~100 deereceye tekabül etmektedir).
Sıcaklık α = 0.95 ile çarpılarak azaltılmıştır. Ve bu azaltma işlemi her baz istasyonu değişiminde, dört kullanıcı değiş tokuş işleminden sonra veya arka arkaya baz istasyonu saysının karesi kadar sonuçsuz deneme yapıldığında yapılmıştır.
Sıcaklık 0.001 olunca da program durdurulmuştur.

5. TESTLER

5.1 Test Senaryosu

Kullanılan test senaryosu [1]’de kullanılan ilk senaryo ile aynı olup: 400 x 400 m2 bir alanda, 22 olası istasyon kurulum alanı ve 95 kullanıcı yerinden (her kullanıcı grubu merkezindeki trafik talebiyle, erlang cinsinden ifade edilmiştir) oluşmaktadır. Hem istasyon kurulum alanları hem de kullanıcı yerleri birörnek (uniform) dağılımla yerleştirilmiştir. Baz istasyonu ile kullanıcılar arasındaki yayılım modeli de Hata’nın modeli [7] kullanılarak oluşturulmuştur.

5.2 Test Sonuçları

Yukarıdaki senaryo ile gerçekleştirilen testlerde K-means yöntemiyle 10 farklı veride de hep 6 baz istasyonu ile sonuca ulaşılmıştır. Aynı verilerle yapılan benzetimli tavlama sonucunda ise 5 baz istasyonu ile sonuca ulaşılmıştır. Aynı veri üzerinde K-means ve benzetimli tavlama yöntemlerini kullanarak çıkardığılan sonuçlar Şekil 5, Şekil 6 , Şekil 7 ’de görülmektedir.

Deney senaryolarının alındığı yayında, [1]’de ise sonuca 4 baz istasyonuyla ulaşılmıştır. Yayında yöntem olarak bir ekleme buluşsal yöntemi (Add heuristic) ,çıkarma buluşsal yöntemi (Remove heuristic) ve Tabu Search [8] yöntemi kullanılmıştır

Şekil 5 :K means

Şekil 6 :Benzetimli tavlama sonuç 1

Şekil 7 : Benzetimli tavlama sonuç 2

6. SONUÇ

Çalışmada 3N ağlarda hücre planlama sorununu ele alınmıştır. Baz istasyonu yerlerini, verilen kullanıcı yerlerine göre en az maliyeti hedefleyerek yerleştirmek amçlanmıştır. Bu yerleştirmeyi yaparken bir güç kontrol mekanizmasından yararlanılmıştır.
K-means buluşsal yöntemi ve benzetimli tavlama yöntemi kullanılarak sonuçlar elde edilmiştir.
Testlerde alınan sonuçlar karşılaştırma yapılan [1]’in sonuçlarına yakın sonuçlardır. Ayrıca çalışma zamanları da gayet kısadır ( < 3 dak). Bu bakımdan çalışma belli ülçüde başarılı sayılabilir.

7. GELECEKTE YAPILABİLECEK İŞLER

Karşılaştırma yapılan makalede iki tane daha test senaryosu bulunmaktadır. Kullanılan yöntemlerin daha sağlıklı karşılaştırmasını yapabilmek için kalan test senaryolarının da bu çalışmada önerilen sistemle denenmesi gereklidir.

Ayrıca daha gerçekçi senaryolar kullanılması gereklidir. Örnek olarak, kullanıcıları alana birörnek dağıtım yoluyla yerleştirmek yerine, gercek hayattan alınmış veriler kullanılmalıdır

8. KAYNAKLAR

E. Amaldi, A. Capone and F. Malucelli. Planning UMTS Base Station Location: Optimization Models with Power Control and Algorithms, IEEE Transactions on Wireless Communications, 2(5):939–952, 2003.
Marc St-Hilaire, Steven Chamberland, Samuel Pierre. A Local Search Heuristic for the Global Planning of UMTS Networks, IWCMC ’06, Vancouver, British Columbia, Canada. July 3-6 2006.
Büyükbaş A.,Cdma ve Umts: Üçüncü Nesil Mobil Haberleşme Teknolojilerinin Karşilaştirilmasi, Türkiye Önerisi, uzmanlık tezi,Telekomünikasyon Kurumu, Mayıs 2005.
E. Berruto, M. Gudmundson, R. Menolascino, W. Mohr, and M. Pizarroso, “Research activities on UMTS radio interface, network architectures,and planning,” IEEE Commun. Mag., vol. 36, pp. 82–95, Feb. 1998.
E. Amaldi, A. Capone, and F. Malucelli, “Base station configuration and location problems in UMTS networks,” in Proc. 9th Int. Conf. Telecommunication Systems, Modeling, and Analysis, 2001, pp. 341–348.
E. Amaldi, A. Capone, F. Malucelli, and F. Signori, “Optimization models and algorithms for downlink UMTS radio planning,” in Proc.IEEE Wireless Communications and Networking Conf., vol. 2, Mar.2003, pp. 827–831.
M. Hata, “Empirical formula for propagation loss in land mobile radio service,” IEEE Trans. Veh. Technol., vol. VT-29, pp. 317–325, Aug. 1980.
F. Glover, “Tabu search—Part I,” ORSA J. Computing, vol. 1, no. 3, pp. 190–206, 1989.
Metropolis, N., A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller and E. Teller, “Equation of State Calculations by Fast Computing Machines”, Journal of Chemical Physics, Vol. 21, No. 6, pp. 1087-1092, June 1953.
S. P. Lloyd, ªLeast Squares Quantization in PCM,º IEEE Trans. Information Theory, vol. 28, 129-137, 1982.

Hazırlayan : Derya Çavdar, Yunus Durmuş ve Cem Ersoy