Optimal placement, scheduling and routing to maximize lifetime in wireless sensor networks under connectivity restrictions

Abstract

Bir kablosuz duygaç ağı, duygaç adı verilen, dağıtık ve bağımsız çalışabilenelektronik aygıtlardan oluşur. Duygaçlar yakınlarında meydana gelen değişiklikleriduyumsayabilir, bu bilgiyi veri paketi olarak işleyebilir ve verileri diğer duygaçlara yada ana alıcılara iletebilir. ?Ilgilenilen b¨olge ile ilgili değişiklikleri takip edebilen etkinbir duygaç ağı oluşturabilmek için kısıtlı pil enerjisine sahip duygaçların birbirleriyleuyumlu çalışması gerekmektedir. Uyumlu calışma, duygaçlar sadece belli bir aralıktayer alan duygaçlarla iletişim kurabildiğinden, toplanan bilgilerin sonunda bir alıcıyailetilebilmesi için de ¨onemlidir. Uygulamaların çoğunda, bir kablosuz duygaç ağı içinağın istenildiği gibi çalışabildiği d¨onem sayısı anlamlı bir başarı göstergesidir.Bu tezde, ilkin duygaçların en iyi yerlerini, en iyi etkinlik çizelgelerini, çalışanduygaçların alıcı atamalarını ve duygaçlardan alıcılarına olan en iyi bilgi akış rotalarınıbularak ağın ömrünü enbüyükleyen karışık tamsayılı programlama gösterimlerigeliştirilmektedir. Gösterimler sonlu bir planlama çevreni içinde kaplama, akış korunumu,enerji tüketimi ve bütçe kısıtlarını dikkate almaktadırlar. Daha sonra, problemikolayca çözebilmeyi sağlayan geçerli eşitsizlikler önerilmektedir. Problemin yapısısebebiyle, dikkate değer bir süre içinde küçük örnekler için dahi en iyi çözümler hesaplanamamaktave doğrusal programlama gevşetmeleri zayıf üst sınırlar vermektedir.Bu sebeple, Lagrange gevşetmesi ve açgözlü seçim ölçütü gibi teknikleri kullanansezgisel yöntemler geliştirilmektedir. Yapılan bilgisayısal deneyler bu sezgisel yöntemlerindoğru ve etkin olduğunu göstermektedir.

A wireless sensor network consists of distributed autonomous electronic devicescalled sensors. They are capable of sensing the changes in their vicinity, process theinformation as data packets and transmit the data to other sensors or a base stationnamely sink. In order to have an effective sensor network that can keep track ofthe changes in the interested region, sensors have to work cooperatively since theyhave limited battery energy. Working in accordance is also important to transmit thecollected information eventually to a sink, since sensors can communicate only with theothers that fall in a certain range. In most of the real life applications, for a wirelesssensor network the number of periods that the network can operate as desired is asignificant performance indicator.In this thesis, we propose mixed-integer linear programming models to maximizethe network lifetime by optimally determining the locations of sensors, activity schedulesof the deployed sensors, sink assignments of the active sensors and their data flowroutes to the corresponding sink over a finite planning horizon subject to coverage,flow conservation, energy consumption and budget constraints. Then, we introducevalid inequalities to solve the problem easily. Due to the characteristics of the problem,even the small instances cannot be solved exactly in considerable amount of timeand the linear programming relaxations give poor upper bounds. Hence, we developheuristics using techniques such as Lagrangean relaxation and greedy selection criterion.Computational experiments indicate that the heuristic methods are accurate andefficient.