A dominating set based communication architecture for distributed applications in mobile ad hoc networks

Abstract

Bu tezde, dağıtık ortamlarda gezgin tasarsız ağlar için kümeleme, omurga oluşturma ve verimli yönlendirme problemlerini çözmek üzere algoritmalar tasarlanması ve gerçeklenmesi amaç edinilmiştir. İlk amaç, bir bağlı hakim küme bulup küme başları kullanılarak ağ üzerinde kümeler oluşturulması ve yöntem geliştirilerek çok seviyeli kümeler belirlenmesidir. Gezgin ağlarda kümeleme için yeni bir Bağlı Hakim Set Tabanlı Kümeleme Algoritması (BHSTKA) önerilmiştir. BHSTKA, Wu ve Li'nin kümeleme algoritması tabanlı olarak tasarlanmıştır, ancak küme başları seçlirken düğümlerin derecelerini de gözönünde bulundurmak gibi iyileştirmeler ve buluşsal yöntemler kullanılarak önemli değişiklikler sağlanmıştır. Bunun yanısıra hiyerarşik kümeler oluşturmak amacıyla İki Seviyeli Bağlı Hakim Set Tabanlı Kümeleme Algoritması (İSBHSTKA) geliştirilmiştir. İkinci amaç, bağlı hakim kümeler üzerinde taşırma tabanlı bir yönlendirme mekanizması oluşturulmasıdır. Bağlı hakim kümenin üyelerini geçit olarak kullanan iki seviyeli bir yönlendirme mekanizması önerilmiştir. Algoritmalar tanımlanmış, zaman ve mesaj karmaşıklıkları analiz edilmiş ve benzetim ortamlarındaki başarım ölçümleri sağlanmıştır.

In this thesis, we aim to design and implement algorithms in a distributed environment in order to solve clustering, backbone formation and efficient routing problems for mobile ad hoc networks(MANET)s. Our first goal is to find a connected dominating set (CDS), then construct clusters using the clusterhead information and extend this approach to multi-level clusters. We propose a new Connected Dominating Set based clustering algorithm for clustering in MANETs. Our algorithm is based on Wu and Li's algorithm, however we provide significant modifications and heuristics such as considering the degrees of the nodes during marking process. We also extend our algorithm in order to generate a hierarchy of clusters. Our second goal is to implement a flooding based routing mechanism on top of CDS based clusters. We propose a two level flooding mechanism by using the CDS members as the gateways of the clusters. We describe the algorithms, analyze their time and message complexities and measure their performance in the simulation environments.