Gezgin tasarsız ağlar için yeni bir konum tabanlı melez yönlendirme algoritması

Abstract

Ad hoc kablosuz ağlar baz istasyonu veya erişim cihazı gibi bir altyapı olmaksızın birbirleriyle iletişim kuran gezgin düğümlerden oluşur. Bu tür ağlarda düğümlerin hareketliliğine bağlı olarak sık sık topoloji değişikliği olur. Bundan dolayı düğümlerin birbirleriyle iletişimde kalmaları için ağda yayın paketlerinin sıklıkla gönderimine gereksinim bulunmaktadır. Gezgin tasarsız ağlarda tabloya dayalı ve isteğe bağlı yönlendirme algoritmaları kullanılmaktadır. Her iki tür algoritmada da düğüm sayısının çok olduğu ve aşırı düğüm hareketliliği durumlarında yönlendirme ek yükü artmaktadır. Sınırlı bant genişliği ve düğüm batarya ömürlerinin iki önemli kaynak olduğu bu ağlarda, yönlendirme ek yükünün en düşük seviyeye indirilerek sınırlı kaynakların verimli bir şekilde kullanılması gerekmektedir.Bu tez çalışmasında, tasarsız ağların sınırlı ve en önemli iki kaynağı olan bant genişliği ve batarya kullanımını optimize eden yeni bir yönlendirme algoritması geliştirilmiştir. Konum Tabanlı Melez Yönlendirme Algoritması (KTMYA) adı verilen bu algoritma ile yönlendirme ek yükü azaltılarak bant genişliğinin etkin kullanımı sağlanmaktadır. Bununla birlikte, ağdaki her bir düğüm tarafından yönlendirme amacıyla yapılacak işlem sayısı ve bellekte tutulacak veri miktarı azaltılarak batarya ömrü uzatılmaktadır. KTMYA hem tabloya dayalı hem de isteğe bağlı algoritmaların çalışma esaslarından fatdalanılarak geliştirilmiştir. Ancak KTMYA, yönlendirme kararı verilirken düğüm pozisyon bilgileri, düğüm batarya miktarları ve düğüm yoğunluk bilgileri kullanımı açısından bu iki yöntemin dışında yeni bir yaklaşım içermektedir.Geliştirilen algoritma, MATLAB 7.0.1'de kodlanan bir benzetim programı ile başarım değerlendirmesi yapılarak, paket dağıtım oranı, yönlendirme ek yükü ve uçtan uca paket gecikmesi açısından tabloya dayalı, isteğe bağlı ve konum tabanlı yönlendirme algoritmaları ile karşılaştırmalı olarak sunulmaktadır. KTMYA, yönlendirme ek yükü, paket dağıtım oranı ve uçtan uca paket gecikmesi açısından daha iyi sonuçlar vermektedir.

Ad hoc wireless networks consist of nodes which communicate with each other without infrastructure such as base station and access point. In these type networks, the network topology frequently changes due to the movements of the nodes. Broadcast packets are regularly sent to network so that nodes in network can stay in communication with each other. Reactive and proactive routing algorithms are used in ad hoc networks, where routing overhead increases in the case of large number of nodes and raised mobility. Bandwidth and battery lives of nodes are two main sources in ad hoc networks. The reduction of routing overhead and efficiently use of sources are very important issues in these networks.In this study, a new routing algorithm called Position Based Hybrid Routing Algorithm (PBHRA) was developed to optimize bandwidth usage of ad hoc networks. The main goal of PBHRA is effective use of bandwidth by reducing the routing overload. Additionally, the other goals of the algorithm are to extend battery life of the mobile devices by reducing the required number of operations for route determination and reduce the amount of memory used. Although in the PBHRA, some features of both table driven and on-demand algorithms were used to achieve these goals at some stages, PBHRA algorithm is a completely different approach from them in terms of giving routing decision that use node position information, node battery life and node buffer value.The PBHRA was coded and simulated in MATLAB 7.0.1 to evaluate its performance and compared with other algorithms. The results showed that PBHRA performs better in terms of routing overload, packet delivery fraction, and end-to-end average packet delay compared to table driven, on demand, and position based algorithms.