Tez No İndirme Tez Künye Durumu
442212
An adaptive, energy-aware and distributed fault-tolerant topology-control algorithm for heterogeneous wireless sensor networks / Heterojen kablosuz sensör ağları için uyarlanabilir, enerji seviyesi farkında ve dağıtık hata toleranslı topoloji kontrol algoritması
Yazar:FATİH DENİZ
Danışman: PROF. DR. ADNAN YAZICI
Yer Bilgisi: Orta Doğu Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Konu:Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control
Dizin:
Onaylandı
Doktora
İngilizce
2016
112 s.
Kablosuz sensör ağları savaş gözetimi, çevresel izleme ve trafik kontrolü gibi birçok alanda kullanılmaktadır. Bu ağlar, algılama, işleme ve aktarma yeteneğine sahip çok sayıda küçük sensör düğümlerinden oluşmaktadır. Bu ağları oluşturan sensör düğümleri genellikle herhangi bir altyapısı bulunmayan bir ortamda kendi kendilerine organize bir şekilde çalışmakta ve kendilerine verilen görevi işbirliğiyle yerine getirmektedir. Bu ağların en büyük üç problemi sensör düğümlerinin sınırlı kaynakları sebebiyle enerjilerinin tükenmesi, çalışma ortamlarının zorlu koşulları nedeniyle bazı sensor düğümlerinin bozulması ve veri iletişiminde yaşanan problemler olarak sayılabilir. Bu nedenle, bu problemlere çözüm olarak önerilen ağ ömrünü uzatan algoritmalar ve hata toleranslı topoloji kontrol algoritmaları yüksek öneme sahiptir. Bu tezde heterojen kablosuz sensör ağları için uyarlanabilir, enerji seviyesi farkında ve dağıtık bir hata toleranslı topoloji kontrol algoritması sunulmaktadır. Temel alınan heterojen mimaride kaynak bakımından zengin süper düğümler ve süper düğümlere bağlı olması gereken sınırlı kaynağa sahip sıradan sensör düğümleri bulunmaktadır. Sensör düğümlerinin herhangi bir sebeple ölmesi ve ağın hata toleransının belirli bir seviyenin altına inmesi durumunda Adaptif Ayrık Yol (ADPV) algoritması sensör düğümlerinin iletim güçlerini ayarlamakta ve ağdaki hata toleransının belirli bir seviyenin altına inmemesini garanti etmekte, enerji seviyesi farkındalığı sayesinde de yükü dengeli bir şekilde dağıtabilmektedir. ADPV algoritması iki evreden oluşmaktadır: bilgi toplama ve alternatif yollar belirleme adımlarından oluşan başlangıç aşaması ve sensör düğümlerinin süper sensörler ile olan bağlantıları koptuğu durumlarda çalışan restorasyon aşamaları. Restorasyon aşamaları sırasında kullanılan alternatif yollar, bilinen matematiksel bir optimizasyon problemi olan maksimum küme paketleme algoritması kullanılarak oluşturulmaktadır. Gerçekleştirilen simülasyonlar, ADPV'nin ağın bağlantılı bir şekilde çalışmasındaki başarısını göstermektedir. DPV algoritması ile ağdaki düğümlerin en fazla %5'i öldüğünde ağ bağlantısı koparken, ADPV algoritması ile sensör düğümlerinin %95'i ölene kadar ağ bağlantılı bir şekilde çalışabilmektedir. Bununla birlikte, ADPV algoritması, DPV algoritmasına göre iki kat daha fazla bağlantılı bir ağ ömrü elde edebilmektedir.
Wireless sensor networks (WSNs) are being used in numerous fields, such as battlefield surveillance, environmental monitoring and traffic control. They are typically composed of large numbers of tiny sensor nodes with limited resources. Because of their limitations and because of the environments they are being used, there are problems unique to WSNs. Due to the error-prone nature of wireless communication, especially in harsh environments, fault-tolerance emerges as an important property in WSNs. Also, because of the battery limitations, solutions to reduce energy consumption and prolong network lifetime are quite valuable. In this thesis, we propose two algorithms, namely Adaptive Disjoint Path Vector (ADPV) and Minimum Supernode Disjoint Path Vector (MSDPV), for heterogeneous WSNs. In this heterogeneous model, we have resource-rich supernodes as well as ordinary sensor nodes that are supposed to be connected to the supernodes. MSDPV algorithm considers the desired fault-tolerance degree and the positions of ordinary sensor nodes to determine optimal number of supernodes and their locations. It provides a novel optimization based on the well-known set-cover problem. ADPV is an adaptive, energy-aware and distributed fault-tolerant topology-control algorithm. Unlike the static alternative Disjoint Path Vector (DPV) algorithm, the focus of ADPV is to secure supernode connectivity in the presence of node failures, and ADPV achieves this goal by dynamically adjusting the sensor nodes' transmission powers. The ADPV algorithm involves two phases: a single initialization phase, which occurs at the beginning, and restoration phases, which are invoked each time the network's supernode connectivity is broken. Restoration phases utilize alternative routes that are computed at the initialization phase by the help of a novel optimization based on the well-known set-packing problem. Through extensive simulations, we demonstrate that ADPV is superior in preserving supernode connectivity. In particular, ADPV achieves this goal up to a failure of 95% of the sensor nodes; while the performance of DPV is limited to 5%. In turn, by our adaptive algorithm, we obtain a two-fold increase in supernode-connected lifetimes compared to DPV algorithm.