Kablosuz algılayıcı ağlarda en düşük ağırlıklı röle düğümlerinin yerleştirilmesi
Minimum weighted relay node placement for wireless sensor networks
Yazar: ŞENER KİMENÇE
Danışman: YRD. DOÇ. DR. İLKER BEKMEZCİ
Hava Harp Okulu Komutanlığı / Havacılık ve Uzay Teknolojileri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı / Yazılım Mühendisliği Bilim Dalı
Derece: Yüksek Lisans, 2012
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control
Dizin: Kablosuz ağlar = Wireless networks ; Sensörler = Sensors

Özet:
Kablosuz Algılayıcı Ağlar (KAA), mikro-elektro-mekanik sistemlerinin hızla ilerlemesi sonucu ortaya çıkan düşük maliyetli, düşük seviyede enerji tüketen, fiziksel olarak küçük, çok fonksiyonlu algılayıcı düğümlerden oluşan bir ağdır. Algılayıcı düğümler tarafından, ihtiyaç durumuna göre hesaplama işlemi de enerji, maliyet gibi kısıtlar göz önüne alınarak kendi üzerlerinde gerçekleştirebilir. Birbirleri arası haberleşme ise sınırlı mesafesi olan radyo frekansı (RF) veya bluetooth protokolü aracılığı ile yapılır. Üzerinde algılayıcı bulunan bu düğümler, algılanılması istenen ortama planlı veya plansız (rasgele) olarak bırakılabilirler. Bırakılma öncesi ve esnası yapılan çalışmalar, bırakılma sonrası düğümler arası kurulacak haberleşmede önemli rol oynamaktadır.Bu haberleşmeyi sağlayacak ağ omurgasının (backbone) oluşturulma yöntemlerinden biri Röle Düğüm kullanımıdır. Röle düğümleri sıradan algılayıcı düğümler arasından seçilebileceği gibi, onlardan daha fazla enerjiye sahip, maliyeti yüksek, tek görevi algılayıcı düğümler ile Baz İstasyonu (Bİ) arası iletişimi sağlayacak düğümler de olabilirler. Röle Düğümü Yerleştirme Problemi (RDYP), en az sayıda RD kullanarak kapsama alanı (coverage), enerji (power), bağlılık (connectivity), maliyet (cost) gibi sorunları amaç fonksiyonunu en iyileyecek şekilde çözmeye çalışır. Buradan anlaşılacağı üzere, RDYP aslında algılayıcı düğümler arasında Steiner ağacı oluşturulması esnasında kullanılması gereken RDlerin sayısını bulmaya yöneliktir. RDYP, NP-zor problem sınıfına girmektedir. Dolayısıyla bulunan çözümler çokterimli (polinomial) zamanda ve belirli bir yakınsama oranına (approximation ratio) sahip olmaktadır.Bu tezde, röle düğümü yerleştirme problemi için, yukarıda belirtilen kriterlerden farklı olarak, aday noktaların sahip olduğunu varsaydığımız ağırlık değerlerine göre RD yerleştirilmesini en iyileyen optimal ve sezgisel olmak üzere iki çözüm üzerinde çalışılmıştır. Ağırlık sadece maliyet olarak değil, aynı zamanda aday noktaya RD yerleştirmenin zorluğu, güvenlik gereksinimleri, bölgeye ulaşma güçlüğü gibi durumları da yansıtabilir. Bir arazi ve yapılandırma için bulunan tek bir ağırlık değeri yerine, bu değere öngörülemeyen sebeplerden dolayı eklenen ağırlık ile ağırlık eklenmiş halinin karesinin alındığı üç durum üzerinde çalışılmıştır.Ağırlık yönünden, sabit arazi boyutlu-artan RD yoğunluklu durumda, sezgisel algoritma optimale yakın sonuçlar vermiştir. Bunun yanında rasgele RD dağılımı yapıldığında, planlı olandan %30a yakın fazla ağırlık çıkmıştır.Ağırlıklar toplamı bakımından incelendiğinde, planlı dağılımda plansıza göre daha az ağırlık çıkmasına rağmen daha fazla RD kullanıldığının gözlemlenmesidir. Ayrıca, üç farklı ağırlık değerlerinin kullanıldığı aynı yapılandırmaya sahip arazilerde farklı sayıda/konumdaki RDlerin kullanıldığı da gözlemlenmiştir. Dolayısıyla ağırlıkların eşit şekilde değişime uğraması, oluşturulan ağacın yapısını beklenenin aksine değiştirmektedir.Sonuç olarak, KAA'larda enerji, hayatta kalma, bağlanırlık, kapsama alanı maksimizasyonunda çözüm olarak başvurulan röle düğümü kullanımı, beraberinde bir optimizasyon problemini de getirmektedir. Bugüne kadar yapılan çalışmalar, amaç fonksiyonu olarak yukarıda belirtilen kısıtlar altında en az sayıda RD kullanmayı hedeflerken, yaptığımız bu çalışma ile ağırlık faktörünün hesaba katıldığı ve sonuçlarının en az sayıda RD kullanma ile hem zaman hem de sayı olarak farklılık gösterdiği sonuca ulaştık. Kullandığımız sezgisel yöntem zaman ve yakınsama derecesi olarak kabul edilebilir sınırlar içerisindedir.

Abstract:
Wireless sensor network (WSN), with the help of rapid improvement in MEMS (micro electro mechanic systems), is a network that consists low-cost, less energy consuming, physically small, multi-functional sensor nodes. Depending on the constrains like energy, and cost, Sensor nodes also execute computing process on their own. Communication between these nodes is established by radio frequency (RF) or Bluetooth protocol which has rather a limited range. Nodes having sensors are deployed into to the medium to sense the sound, light, temperature etc. in a planned way or randomly. The planning that takes place pre-deployment and during deploying plays an important role in the communication that will be settled after the deployment between nodes.One of the methods to constitute the network backbone that will enable this communication is using Relay nodes (RN). Relay nodes can also be selected among regular sensor nodes or have only relaying mission with more power and cost between sensor nodes and base too. Relay Node Placement Problem (RNP) tries solving the optimization of an object function to maintain coverage/connectivity, consume less power, and be cost-effective by using minimum number of RNs. As can be seen here, the intention of RNP is to find the necessary number and locations of RNs to form the Steiner Tree subject to the purpose. Concurrently, RNP is an NP-complete problem. Thus, the duration of the solution and result will have polynomial time and approximation ratio, respectively.In this thesis, apart from the criteria above, two solution methods including optimal and heuristics are studied according to the weight values which supposedly belong to the candidate points of RNs. Weight might be defined not only as cost but also as difficulty of placing an RN, keeping RNs safe and secure, challenge for reaching that candidate point, and so on. Instead of a single weight for each field and node configuration, two more variations like adding a secondary weight due to unforeseen reasons and square of the added weight are studied.From the standpoint of weight, in constant field size-increasing RN density configuration, heuristic method yielded proximate results when compared with optimal. Furthermore, the results were same when the RN density to a certain value. Besides, deploying RNs randomly yielded with a weight approximately %30 percent high when compared with the planned one.With respect to sum of RN density, despite deploying the RNs randomly with a higher weight than planned one, random replacement facilitates less number of RNs. And what is more, assigning three different weight sets for the same field size and node density led to utilize different sets of RNs. Thus, altering the weight sets equally affects the form of the Steiner tree in the same configuration.To sum up, the heuristics method combined with a criterion of weight set brought a new scope for RNP, which also introduced striking results.