Tez Arşivi

Tez aramanızı kolaylaştıracak arama motoru. Yazar, danışman, başlık ve özetlere göre tezleri arayabilirsiniz.


İstanbul Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Anabilim Dalı

2003

A GA/Heuristic based hybrid technique for routing and wavelength assignment in WDM networks

WDM ağlarda yol ve dalgaboyu atama için bir genetik algoritma/sezgisel yöntem melez tekniği

Bu tez, YÖK tez merkezinde bulunmaktadır. Teze erişmek için tıklayın. Eğer tez bulunamazsa, YÖK Tez Merkezi'ndeki tarama bölümünde tez numarasını arayabilirsiniz. Tez numarası: 151343

Tezi Bul
Özet:

WDM AĞLARDA YOL VE DALGABOYU ATAMA İÇİN BİR GENETİK ALGORİTMA/SEZGİSEL YÖNTEM MELEZ TEKNİĞİ ÖZET Son yıllarda, optik ağlarda, özellikle de Dalgaboyu Aîamalı WDM ağlarda (Wavelength Routed WDM Networks) önemli ilerlemeler sağlanmıştır. Optik iletim teknolojisi, çok büyük bant genişliği ve oldukça yüksek hızlarda iletim yeteneğine sahip bir teknolojidir. Bu nedenle WDM teknolojisinin gelecekte yaygın olarak ağların omurgasını teşkil edeceği öngörülmektedir. Statik trafik isteklerinin yol seçim işleminin tek bir dalgaboyunda uçtan uca yapıldığı düşünüldüğünde, optik ağların ulaşım katman dizaynında, her bağlantının kullanacağı yolun ve hangi dalgaboyunun kullanılacağına ne şekilde karar verileceğinin seçimi önemli bir faktördür. Bu problem ve varyantları önemli ölçüde dikkat çekmiş ve içlerinde, sezgisel yöntemlerin, genetik algoritmaların, ve lineer programlamanın da olduğu, çeşitli çözüm önerileri ortaya atılmıştır. Bu yöntemler, makul zaman kısıtları içerisinde iyi sonuçlar üretmelerine rağmen, pratik hayatta uygulanabilirlikleri sınırlı ölçülerde kalmaktadır. Bu çalışmada kullanılan yaklaşım, başarılı sezgisel yöntemlerle, genetik algoritmaları birleştirerek çözüme ulaşmaya çalışmaktır. Genetik Algoritmalar, Darwin'in evrim teorisini ve Mendel'in kalıtım prensiplerini modelleme yaklaşımına dayanan stokastik, global en iyileme yöntemleridir. Evrim teorisinin temelinde doğal seçim kavramı yatmaktadır. Bu teoriye göre, doğal seçim sonucunda diğerlerine göre bazı avantajları olan bireylerin yaşama ve sonraki kuşaklara yavru bırakma olasılıkları daha yüksektir. Bu avantajı sağlayan özellikler kalıtımsal ise bu özelliğe sahip bireylerden doğan yavrularında bir kısmı bu özelliği taşıyacak ve dolayısıyla aynı avantajlara sahip olacaklardır. Birkaç kuşak sonucunda bu iyi özelliği sağlayan bireylerin sayısı toplumda artacaktır. Bu çalışmada benimsenen Genetik Algoritma/Sezgisel yaklaşım yöntemi, Davis'in çalışmalarından esinlenilerek, nesneye dayalı bir ağ modeli, adaptif bir genetik algoritma, ve sezgisel yaklaşımlara dayanan operatörlerden oluşmaktadır. Bu şekilde bir nesneye dayalı ağ modeli, ikili sayı katarlarıyla yapılan kodlamadan daha doğal bir temsil olarak düşünülmektedir. Sezgisel yöntemlere dayanan operatörlerin kullanımı, bu yöntemlerin probleme dayalı bilgilerinin kullanımına olanak vermiştir. Ayrıca, operatör olasılık adaptasyonunun kullanılmasıyla operatörlerin koşturma sırasındaki verimliliklerine göre uygulanmaları sağlanmaya çalışılmıştır. Çalışmada iki farklı uygunluk fonksiyonu (verimlilik yargısı) kullanılmıştır. Bunlardan birincisi ağın kullanması gereken minimum dalgaboyu sayısına, diğeri ise basitleştirilmiş bir ağ maliyet modeline dayanmaktadır. Önerilen teknikle elde edilen sonuçlar, daha önce önerilmiş olan bazı sezgisel yöntemlerin sonuçlarıyla karşılaştırılarak başarımının daha iyi olduğu görülmüştür. XII

Summary:

A GA/HEURISTIC BASED HYBRID TECHNIQUE FOR ROUTING AND WAVELENGTH ASSIGNMENT IN WDM NETWORKS SUMMARY Recently, there has been considerable progress in the area of all-optical networks which are based on wavelength division multiplexing (WDM). WDM technology provides the capacity required by backbone networks. WDM based all optical networks offering multi-gigabit rate per wavelength may soon become economical as the underlying backbone in wide area networks. When individual static traffic requirements are to be routed independently on a single wavelength end-to-end based on wavelength continuity constraint, the problem is to determine the route, fibers, and wavelength each connection will use. This problem and its variants have attracted considerable interest, with a variety of solution approaches including heuristics, genetic algorithms (GAs), and integer linear programming (ILP) techniques. Those heuristic algorithms can produce good solutions in a reasonable amount of time. However, they have restricted applicability in a practical environment because they have a number of fundamental problems including high time complexity, lack of robustness and no performance guarantee as input changes. Our approach is to incorporate advanced heuristics into an overall genetic algorithm. Genetic Algorithms are a class of stochastic, global optimization algorithms that model the biological principles of Darwin's theory of evolution and Mendel's principles of classical genetics. The theory of evolution centers on the principle of natural selection that mainly states that those individuals that have a certain characteristics. The characteristics that give the individuals some advantage above others are more likely to survive and reproduce. If this characteristic is inheritable, then some of these individuals' offspring will be born with it and thus have the advantage over the others. After a few generations, the number of individuals with the favorable trait will increase in the population. The GA/heuristic hybrid approach adopted in this thesis, inspired by Davis' work, employs an object-oriented network model, an adaptive overall GA framework, and heuristic operators. Such an object-oriented network model would appear to be a natural representation for network problems, rather than a linear bit-string encoding. Using heuristic operators allows problem-specific knowledge to be applied, while operator-probability adaptation should allow the blend of operators to be adjusted according to their relative productivities during execution. Two metrics for network effectiveness assessment are used: one is based on NWR (network wavelength requirement), and the other is based on a simplified model of network cost. The results obtained with the hybrid technique are compared with those obtained from the recent wavelength-allocation heuristics. It is observed that the proposed hybrid technique has very promising results when compared with the results of the other techniques under various parameters. XI