Telekomünikasyon şebekelerinin trafik yönlendirmesinde yapay zeka uygulamaları

Abstract

Bu tezde, mühendislik optimizasyon problemlerinin çözümünde yeni bir yaklaşım olan Genetik Algoritma ile telekomünikasyon şebekelerinde trafik yönlendirme için en iyi çözümün bulunması amaçlanmış, ayrıca indüktif öğrenme ve yapay sinir ağlan gibi diğer yapay zeka uygulamalarından kısaca bahsedilmiştir. İletişim sistemlerinde yönlendirme (routing) fonksiyonu, hizmet kalitesi, dayanaklılık (survivability), maliyet ve güvenilirlik gibi önemli sistem özelliklerini etkiler. Yönlendirmenin hedefi, şebekedeki herhangi iki düğüm arasında başarılı bir bağlaşma kurmaktır. Bunun için, belli bir bağlaşma girişimi için, bir düğümde belirli bir devre grubu seçilir. Bu seçim, şebekedeki hata veya yığılma durumunda etkilenir. Bundan dolayı yönlendirme seçimi, şebekenin o andaki durumuna göre belirlenebilmelidir. Yönlendirme algoritması, düğüm çiftleri arasındaki bağlantıların hangi yollar üzerinden kurulacağım belirler. Eğer bu yollar her zaman aynıysa "sabit yönlendirme şeması", zamanla değişiyorsa "dinamik yönlendirme şeması", denir. Tezde kullanılan yönlendirme şeması, şebekenin değişen trafik akış şartlarına göre zamanla değiştiğinden dinamiktir. Genetik Algoritmalar, doğal seçim ve doğal genetik temellerine dayalı bir arama algoritmasıdır. Bu yöntem ile her yeni nesilde meydana getirilen suni yaratıkların (0 ve 1 'lerden oluşan diziler) dayanıklılığı hesaplanmaktadır. Bu diziler uygunluk fonksiyonu nisbetince bir sonraki nesilde temsil edilebilir. Her nesilde yürütülen çaprazlama (crossover) ve mutasyon işlevleri yeni yaratıklar meydana getirirler. Bu yaratıklar elemine edilerek gelen nesillerin çeşitlemelerinden daha iyi nesiller elde edilir. vıu Yönlendirme algoritmalarının kullanıldığı şebekelerde en kısa izi bulmaya yönelik tanımlanmış üç standart algoritma vardır. Deterministik hesaplama yöntemlerine dayanan bu algoritmalara alternatif olarak rastgele yönlendirilmiş bir algoritma olan GA (Genetik Algoritma), diğer algoritmalara oranla daha basittir ve kısa süreli hesaplama avantajına sahiptir. Tezde tasarlanan yüz düğümlü, merkezi yönlendirme esasına göre işleyen geniş alan şebekesinde birinci düğümden yüzüncü düğüme, değişen trafik şartlarına bağlı olarak, en kısa izin bulunması amacıyla GA yöntemi uygulanmıştır. Sonuç olarak bu yöntemin, her nesilde daha iyi sonuçlar vermek üzere, istenilen amacı sağladığı görülmüştür. Dinamik bir yöntem olarak tasarlanan GA yönlendirmesi seçilen nesil sayısına bağlı olarak daha iyi sonuçlar verebilir. Bu yöntemde düğümler arası hatlar belirli sırada numaralanır ve istenilen düğüm çiftleri arasındaki yollar ikili kod halinde yazılır. Bu diziler daha sonra GA operasyonlarıyla değiştirilerek en yüksek uygunluk fonksiyonu değeri elde edilmeye çalışılır. En son nesildeki en yüksek uygunluktaki dizi seçilerek deşifre edilir ve en uygun yol bulunur. Uygunluk fonksiyonu; hatlardaki gecikme, hat uzunluğu, iletim kalitesinin kombinasyonundan oluşan bir fonksiyon olup içeriği bilgisayar programının başlangıcında belirlenir. Örnek bir tasarım ve sonuçlan, yorumlarıyla beraber sunulmuştur.

In this thesis, a new approach to the engineering, optimization problem, optimization Via Genetic Algorithms, has been objected to find optimum solution of routing for telecommunication networks, in addition has been discussed, in brief the other applications of artifical intelligence like inductive learning and neural networks. The routing function is one of the function in a communication system with most influence on important system characteristic like; grade of service, survivability, cost and reliability. The objective of the routing is to establish a successful connection between any two nodes in the network. The function of the traffic routing is the selection of a special circuit group, for a given connection attempt, at a node in the network. The choice of a circuit group may be affected by information of the availibity of failure or overload conditions of the network. So, it should be determined the selection of routing for the state of the network at that time. The routing scheme defines how a set of routes is made available for calls between a pair of nodes. If the set of routes in the routing scheme is called "fixed", if the set of routes in the routing pattern varies, this is called "dynamic" or "adaptive". The routing scheme that is used in the thesis is dynamic because of changing traffic conditions within time. Genetic Algorithms are search algorithms based on the procedure of natural selection and natural genetics. By this method, it is calculated the fitness of every artifical creature (string made of Os or Is) in every generation. These strings are represented to the next generation for their fitness function values. The operators of crossover and mutation which are running in every generation, form new creatures. By elemination of these creatures it has been gotten better generation from previous generation. These has been defined three standart algorithm to find minimum weight path in the networks that are used with routing schemes. It is a random directed algorithm, GA (Genetic Algorithm) is easy to understand and has got the advantage of short calculation duration proper to the other algorithms which are based on deterministic calculation methods. The planned network defined in this thesis is a wide area network running on the ultimate of central routing, has got a hundred nodes and GA method is implemented to find the shortest path between first and last nodes related to the conditions of traffic variety. As a conclusion, it has been seen that this method provides the desired conditions. GA routing may gives better results depend on selected generation number. In this way, the links between nodes are numbered and the desired ways are descripted as binary strings. Then, these strings are changed by the ways of GA operations to find and get the maximum fitness function value. The fitness function is produced from delay on links, length of links, quality of communication and it has been determined at the beginning of computer programme. A network pattern and its result are given at the appendix with its comments.