Parallel heuristics for location management in mobile networks


Thesis Type: Postgraduate

Institution Of The Thesis: Marmara University, Institute for Graduate Studies in Pure and Applied Sciences, Turkey

Approval Date: 2005

Thesis Language: English

Student: FATMA CORUT ERGİN

Supervisor: Haluk Rahmi Topcuoğlu

Abstract:

Yerleşim Planlama mobil iletişim kullanımının artışıyla önemli bir problem haline geldi. Mobil iletişimlerde bir kullanıcıya arama geldiğinde sistem kullanıcıyı bir yerleşim alanı içerisindeki baz istasyonlarında arar. Kullanıcılar da bir yerleşim alanını terkettiklerinde yerleşim yönetimi veritabanlarını güncellemek için kayıt sinyali gönderirler. Yerleşim Yönetimindeki amaç toplam kayıt ve arama maliyetlerini azaltmaktır. Bu problem baz istasyonlarının yerleşim alanlarına ve anahtar noktalara atanmasını içeren NP-hard bir problemdir. Problem NP-hard olduğu için ve birçok sınırlamayı yerine getirebilmek için dört farklı keşfe dayalı algoritma önerdik: Genetik Algoritma, Paralel Genetik Algoritma, Memetik Algoritma ve Paralel Memetik Algoritma. Bu çalışmada biz maliyeti düşürmek (programın çalışma zamanı) ve performansı artırmak (toplam ağ maliyeti) için bu metodların paralelleştirilmesi üzerinde durduk. Buna ek olarak, bu çalışma genetic çaprazlama ve mutasyon işlemlerinden sonra oluşan sonuçlar için modeldeki bütün kısıtlamaları gözönünde bulunduran detaylı bir geçerli hale getirme operasyonu içerir. Deney aşamasında, önerilen bütün yöntemler hem büyük boyutlu hem küçük boyutlu farklı ağ özellikleri için test edildi. Test sonuçlarına göre, Paralel Memetik Algoritma ağ maliyeti çözümü açısından en iyi sonucu verirken Paralel Genetik Algoritma da zaman açısından en iyi algoritma olarak tespit edildi. Ekim 2005 Fatma CORUT ERGİN ABSTRACT Location management has become an important problem with the increasing usage of mobile communication. In mobile communication when a call arrives to a mobile terminal, the system pages the mobile terminal among a set of Base Stations (BS) in a Location Area (LA). Also, when a mobile terminal leaves a LA, it sends a registration signaling to update its location management databases. The target in location management is to minimize the total of paging and registration costs. The problem is an NP-hard problem, which requires cell-to-LA (i.e. BS-to-LA) and cell-to-switch assignments. Due to its NP-hardness and to satisfy a large set of constraints, we propose four heuristics for the problem which are: Genetic Algorithms (GA), Memetic Algorithms (MA), Parallel Genetic Algorithms (PGA) and Parallel Memetic Algorithms (PMA). Our main emphasis is the parallel evolutionary algorithms due to their significant decreases in cost (i.e. the running time) for generating solutions and promising improvements in solution quality (i.e. the total network cost). Additionally, this study includes complete validation phases after crossover and mutation operators by considering all constraints given in the system model. In our experimental study, the proposed heuristics were tested with respect to various network characteristics for both small-size and large- size networks. Based on the experiments, the PMA provides the highest quality solutions with respect to the total network cost, while the PGA requires the lowest running time to generate the solutions. October 2005 Fatma CORUT ERGİN