Güvenilir kablosuz algılayıcı ağlar için çok merkezi düğümlü şartlı çok kopyalı bir yol atama stratejisi
A conditional multi-copy strategy with multiple central nodes for more reliable wireless sensor networks
Yazar: MERVE EKMEN
Danışman: YRD. DOÇ. DR. AYŞEGÜL ALTIN KAYHAN
TOBB Ekonomi ve Teknoloji Üniversitesi / Fen Bilimleri Enstitüsü / Endüstri Mühendisliği Ana Bilim Dalı
Derece: Yüksek Lisans, 2015
Konu: Endüstri ve Endüstri Mühendisliği = Industrial and Industrial Engineering

Özet:
Mikro-elektro-mekanik sistemler (MEMS) teknolojisindeki ilerlemeler, düşük maliyetli, kısıtlı batarya enerjisine sahip, küçük boyutta, fonksiyonel ve kısa mesafelerde fiziksel olarak bağlı olmadan birbirleriyle iletişim kurabilen sensörlerin gelişimine olanak tanımıştır. Kablosuz Algılayıcı Ağlar (KAA'lar), sıcaklık, nem, ses, basınç vb. fiziksel veya çevresel faktörleri gözlemleyerek veri üreten ve birbiri üzerinden verileri özel bir bölge veya noktaya ileten, belirli bir alana dağıtılmış bağımsız sensörlerden oluşan bilgi iletim sistemleridir.

Bu tezde KAA Tasarım Problemi altında ağ ömrünün ve güvenilirliğinin iyileştirilmesi amacıyla koşullu çok kopyalı ve çok yollu bir rotalama stratejisi geliştirilmiştir. Önerilen strateji, her sensörün kendi verisini iki kez baz istasyonuna (BS) gönderdiği basitçe kısıtlanmış çok kopyalı rotalama stratejileri için ağ ömrü ve güvenilirliği arasındaki ödünleşimin dikkate alındığı bir iyileştirme niteliğindedir. Buna göre kaynak algılayıcılar, kendi sezdikleri bütün veri yerine sadece ağ bütünlüğü açısından nispeten daha kritik bir rol oynayan ve merkezi olarak adlandırılan düğümler üzerinden gönderdikleri veriyi kopyalayarak düğüm ayrık yollar üzerinden BS'ye göndermektedirler. Böylece dışarıdan gelebilecek saldırılara veya düğümlerde meydana gelebilecek arızalara karşı korunaklılık bütün verinin değil sadece kritik düğümlere uğrayan kısmın korunması ile sağlanmaktadır. Problem için öncelikle iki farklı karma tamsayılı programlama modeli önerilmiştir. Sunulan çoklu merkezi düğüm ve şartlı kopyalama stratejisi farklı stratejilerle ağ ömrü ve güvenilirliği açısından çeşitli büyüklükteki ağlar üzerinde karşılaştırılmıştır. Önerilen kopyalama stratejisinin kıyaslandığı farklı çoklu kopyalama stratejilerine oranla ağ ömründen fazla feragat etmeden ağ güvenliğini belirgin şekilde iyileştirdiği anlaşılmıştır. Devamında öncelikle her iki modelin ticari çözücüyle çözüm sürelerini önemli şekilde kısaltan bazı geçerli eşitsizlikler sunulmuştur. Ayrıca özellikle büyük ölçekli örneklerin çözümü için çok aşamalı bir sezgisel geliştirilmiştir.  Geliştirilen sezgisel yöntemin, bir çözücünün kabul edilebilir bir süre içinde çözemediği durumlarda daha kısa sürelerde kaliteli çözümler bulduğu ve belirtilen zaman limiti içerisinde modelin optimal çözümün bulamadığı durumlarda ise sezgiselin modelin sunduğu aralık (gap) değerini yarıya düşürdüğü görülmüştür. Son olarak sunulan modelde kullanılan bazı parametrelerin model üzerindeki etkilerini incelemek için onların farklı değerleri ile birtakım testler yapılıp elde edilen sonuçlar ile duyarlılık analizi gerçekleştirilmiştir.

Anahtar Kelimeler: Kablosuz algılayıcı ağ, koşullu çoklu kopya, çoklu yol atama, güvenilirlik, matematiksel modelleme.

Abstract:
Recent advances in micro-electronic mechanical systems (MEMS) led to the development of tiny, cost-efficient, independent and functional sensors with limited capabilities. Wireless Sensor Networks (WSNs) are information delivery systems and they consist of independent sensors generating data by sensing physical or environmental conditions such as temperature, humidity, sound, pressure etc., and transmit it to a special point or location within a cooperation. 

In this thesis, we consider the Wireless Sensor Network (WSN) Design Problem under an energy efficient conditional multi-copy and multi-path routing strategy so as to improve network reliability. Our strategy is an improvement over the simple restricted multi-copy strategies where every sensor duplicates its data since we provide comparable levels of network reliability and yet extend network lifetime significantly. Hereunder, instead of whole data only the data routed through the central nodes which are more critical in terms of network reliability would be duplicated at its source and sent to the BS (base station) on another node disjoint path.  Hence, instead of the whole data in the network only the data visiting central nodes is protected while safeguarding against malicious attacks or failures on nodes. 

We offer two different mixed integer programming models for two variates of the our strategy. The novel conditional multi-copying with multiple central nodes strategy, CM (Conditional Multi-copying,) and other multi-copying strategies are compared with respect to the network lifetime and reliability metrics. According to the test results, CM improves network reliability by giving of a little reliability in contrast with other strategies. Afterwards, we present several valid inequalities significantly shortening solution times in commercial solvers for both models. Moreover, we present a multi step heuristic method especially for tests on larger networks. The algorithm provides good solutions in reasonable times when compared with the commercial solver. Finally, a series of sensitivity analyses are done on CM by changing the values of some parameters.

Keywords: Wireless sensor networks, conditional multi-copying, multi-path routing, reliability, mathematical modelling.