A New Energy Efficient Forwarder Set Based Dynamic Duty Cycled Routing In Wireless Sensor Networks

Abstract

Kablosuz sensör ağları günümüzde yaygın olarak kullanılmaktadır. Kablosuz sensör ağlarında, bir ortama rastgele veya düzenli olarak yerleştirilmiş yüzlerce düğüm sıcaklık, nem, basınç vb. çevresel etmenlerin ölçümünü yaparak bir veya birden fazla merkez düğüme iletir. Sensör düğümlerin işlemci kapasitesi düşüktür ve enerji kısıtlamaları vardır. Sensör düğümlerin enerji kısıtı kablosuz sensör ağlarında enerji veriminin önemini arttırmıştır. Sensör düğümler paket iletimi yapmadıkları sırada dinleme durumunda bulunurlar. Sensör düğümler, paket iletimi yapmadıkları ancak çevreyi dinledikleri zamanlarda gereksiz bir enerji tüketiminde bulunurlar. Bu dinleme durumuna boş dinleme (idle listening) denir. Boş dinlemenin sebep olduğu enerji tüketimini azaltmak için görev çevrimli çalışma sıkça kullanılan bir yöntemdir. Görev çevriminde sensör düğümler uyku ve dinleme zamanlarından oluşan bir periyodu takip etmektedirler. Düğümler uyku zamanlarında herhangi bir paket alışverişi yapmamakta ve enerji tüketimlerini olabilecek minimum seviyeye düşürmektedirler. Dinleme zamanlarında ise paket alış verişi yapabilmektedirler. Görev çevrimi(duty cycling) periyodu bütün düğümler için belirli ve ağın yaşam süresi boyunca sabit olabilir. Sabit görev çevrimli (static duty cycling) sensör düğümler, ağın dinamiklerine uyum sağlayamaz ve düğümler ağdaki konum ve görevlerine göre görev çevrimlerini güncelleyemez. Diğer yandan görev çevrimi periyodunu dinamik olarak güncellenen düğümler ağın yaşamı süresince değişen şartlarına daha kolay uyum sağlar. Bu sebeple bu tez kapsamında dinamik görev çevrimli(dynamic duty cycling) sensör düğümler üzerinde bir çalışma yapılmıştır. Dinamik görev çevrimli sensör düğümlerde akla gelen en önemli soru görev çevriminin sensör düğümlerce nasıl güncelleneceğidir. Sensör düğüm görev çevrimini başka sensör düğümler veya merkez düğüm(sink) ile haberleşerek güncelleyebilir. Bu yöntem, düğümler arasında paket aktarımı gerektirdiğinden ağ içinde haberleşme yüküne (communication overhead) dolayısı ile enerji tüketimine sebep olur. Bu sebeple bu çalışmada sensör düğümlerin paket aktarımına gerek duymadan görev çevrimlerini güncelleyeceği yöntem geliştirilmiştir. Yönlendirme kümesine göre dinamik görev çevriminde (forwarder set based dynamic duty cycling), sensör düğümler paket iletimleri sonucunda elde ettikleri verileri kullanarak bazı istatistikler elde ederler. Bu istatistiki verileri kullanan sensör düğümler, görev çevrimlerini günceller. Geliştirilen yöntemde düğümün kalan enerji miktarı bir kısıt olarak belirlenmiştir. Dinamik görev çevrimi yönteminde düğümler, görev çevrimlerini güncellerken başka düğümler ile paket alışverişine gerek duymamıştır. Görev çevrimi, Ortam Erişim Katmanı(MAC Layer) ile alakalı bir konudur. Ortam Erişim Katmanında görev çevrimini içeren birçok protokol literatürde bulunmaktadır. Dinamik görev çevrimli yöntem gerçeklenmeden önce Ortam Erişi Katmanında çalışmamıza uygun bir protokol olan XMAC gerçeklenmiştir. XMAC protokolünde, gönderici düğüm kısa süreli paketler göndererek, uygun olan komşularına haber verir. Komşu düğümlerden uyku durumunda olmayan veya o sırada paket iletimi yapmayan alıcı düğüm, bir geri bildirim paketi(ACK) gönderir. Daha sonra gönderici düğüm ve alıcı düğüm arasında paket iletimi başlar. Fırsatçı yönlendirme(opportunistic routing) protokolleri görev çevrimli kablosuz sensör ağlarda sıkça kullanılır. Kaynak ve varış arasında belirlenmiş sabit bir yol üzerinden paket iletimi yapan yönlendirme protokollerinde, yol üzerindeki alıcı düğümün uyanması için uzun süre beklenilebilir veya bu düğüm enerjisinin tükenmesi vb. sebebiyle paket iletimi yapmıyor olabilir. Paketin potansiyel bütün alıcı düğümler yardımı ile, statik yollar belirlenmeden aktarılması, gecikme ve iş çıkarımı performansı konusunda daha iyi sonuçlar alınmasını sağlar. Bu çalışmada ağ katmanında, düğümlerin coğrafi konumlarına göre fırsatçı yönlendirme yapan çekişme temelli coğrafi yönlendirme(contention-based geographic forwarding) protokolü gerçeklenmiştir. Çekişme temelli coğrafi yönlendirme protokolünde alıcı düğümler, göndericiden gelen kısa paketlerden(preamble) birini aldığında merkez düğüme olan uzaklıklarına göre bir zamanlayıcı kurar. Merkez düğüme en yakın olan düğümün zamanlayıcısı en erken sürede sona erer. Zamanlayıcının süresi dolduktan sonra merkez düğüme en yakın olan düğüm gönderici düğüme bir geri bildirim paketi gönderir. Bu geri bildirim paketini alan gönderici düğüm paket iletimine başlar, zamanlayıcısı dolmayan diğer düğümler de görev çevrimlerine geri döner. XMAC protokolü ve çekişme temelli coğrafi yönlendirme protokolü arasında uyumluluğu sağlamak için göndericinin gönderdiği kısa paketlere, gönderici düğümün konum bilgisi de eklenmiştir. Kablosuz sensör ağındaki her düğüm, gönderici düğümün yönlendirme kümesinde(forwarder set) bulunup bulunmadığı ve alıcı düğüm olup olmadığı konusunda bilgi sahibidir. Sensör düğümler kaç kere yönlendirme kümesinde bulunduğu bilgisi ve kaç kere alıcı düğüm olma çekişmesini kazandığı bilgisine sahiptir. Bu çalışmada sensör düğümlerin paket aktarımları sırasında elde ettikleri bu veriyi kullanarak görev çevrimlerini güncellemesi sağlanmıştır. Bir sensör düğüm yönlendirme kümesinde çok kez bulunuyor ancak alıcı düğüm olarak seçilmiyorsa bu düğüm görev çevrimindeki uyanıklık süresini artırarak alıcı düğüm olma ihtimalini arttırır. Tam tersi olarak, eğer bir düğüm yönlendirme kümesinde bulunma sayısının büyük bir kısmında alıcı düğüm oluyor ise bu düğüm uyanıklık süresini azaltarak hem uyanıklık süresinde harcadığı enerji miktarını azaltır hem de alıcı düğüm olarak seçilme olasılığı azalır. Bunun dışında, kalan enerji miktarı da görev çevrimi güncellemesinde kısıtlayıcı olarak kullanılmıştır. Eğer bir düğümün kalan enerji miktarı azalmışsa görev çevriminde uyanıklık süresi arttırılacaksa bile daha küçük bir oranda arttırılır. Bu sayede, bu düğümün kalan enerjisini de tüketip, kısa sürede ölmesi engellenir. Yönlendirme kümesine dayalı görev çevrimi yöntemi ile ağın yaşam süresi, sabit görev çevrimine göre altı kat, düğüm derecesine dayalı dinamik görev çevrimi(node degree based duty cycling) yöntemine göre ise iki kat artırıldı. Ağın yaşam süresi dolduktan sonra, düğümlerin kalan enerji miktarları diğer yöntemlere göre daha dengeli bir dağılım gösterdi. Diğer yandan, gecikme konusunda da sabit görev çevrimine göre tolere edilebilir bir artış gözlemlendi. Bu tezde geliştirilen bir diğer yöntem ise sensör düğümlerin düğüm bozulmalarına karşı duruma dayalı merkez düğüm seçimidir(adaptive sink selection). Düğüm bozulmalarına karşı dayanıklı kablosuz sensör ağlar günümüzde gittikçe önem kazanmaktadır. Bu amaçla ağa birden fazla merkez düğüm yerleştirilmektedir. Düğüm bozulmaları sonucunda paketlerin düşmesi ağda istenmeyen bir durumdur. Ayrıca, düğüm bozulmaları sonucu ağda oluşan boşluklar(routing hole) sık görülmektedir. Geliştirilen yöntem ile düğümler bozulduğu veya düğümlere erişilemediği zaman paketler, cofrafi olarak başka yönlere ve başka merkez düğümlere yönlendirilmiştir. Geliştirilen yöntemde gönderici düğüm paket göndereceğine dair kısa paketler yayınlamaya başlar. Eğer kısa paketleri gönderme süresi ağdaki izin verilen maksimum uyuma süresinde fazlaysa ve herhangi bir düğümden geri bildirim alamadıysa, gönderici düğüm yönlendirme kümesinin tümleyenini alır. Kısacası yönlendirme kümesine farklı düğümler dahil edilir. Bu durumda gönderici düğüm elindeki paketi, merkez düğüme kendisinden daha uzak olan düğümlere de iletebilir. Paketler diğer merkez düğümlerin olduğu bölgelere doğru yönlendirilmiş olur. Coğrafi yönlendirme protokollerinde, düğüm bozulması durumunda, gönderici düğüm paketi coğrafi kazanım ile gönderebileceği bir alıcı düğüm bulamayabilir. Bu durumda paketler gönderici düğümler tarafından iletilemez ve gönderici düğüm sürekli kısa bildirim paketleri göndererek enerjisini tüketir. Gönderici düğümün diğer merkez düğümlere doğru paketleri yönlendirmesi gereklidir. Önerilen yöntemde gönderici düğümler yeterli süre bekledikten sonra, paketi iletemediklerine karar verip yönlendirme kümesini tümlemektedirler. Bu sayede paketlerin düşme oranı azalmakta ve iş çıkarımı artmaktadır. Duruma göre merkez düğüm seçimi yöntemi, çeşitli düğüm bozulması senaryoları ile test edilmiştir. Bu senaryolarda düğümlerin bozulması sonucu ağda boşluklar oluşturulmuştur. Düğüm bozulmaları içeren senaryolarda, geliştirdiğimiz yöntem paketlerin başka merkez düğümlere yönlendirilmesini sağlamıştır. Yapılan simulasyonlar sonucunda, coğrafi yönlendirmeye(geographic forwarding) göre paket düşme oranları azalmış ve iş çıkarımında artış görülmüştür. Gecikme performasında cofrafi yönlendirmeye göre bir düşüş gözlemlenmiştir. Bu beklenen bir sonuçtur. Çünkü paketler diğer merkez düğümlere yönlendirildiğinde kaynak ve varış arasındaki yol uzamaktadır. Gecikmedeki artış, iş çıkarımında elde edilen artış ile karşılaştırıldığında tolere edilebilecek seviyededir. Sensör düğümlerin dağıtık bir şekilde karar alarak görev çevrimini güncellediği ve duruma göre merkez düğüm seçimi yaptıkları bir sistem tasarlanmıştır. Tasarlanılan sistemde ortam erişim katmanında XMAC protokolü, ağ katmanında ise çekişme temelli coğrafi yönlendirme protokolü kullanılmıştır. Simulasyon sonuçları olay tabanlı kablosuz bir ağın gerçeklenmesi ile elde edilmiştir. Bu sebeple her düğümün kaynak(source) olabileceği ve bütün paketlerin bir merkez düğüme ulaşmak istedikleri var sayılmıştır. Ağ trafiği belleksiz özelliği ile gerçeklenebilir olan poisson dağılımına göre yaratılmıştır. Ağın yaşam süresi(network lifetime) ağın bölünmesi(network partition) olarak belirlenmiştir. Sonuç olarak, geliştirilen yöntemde fazladan haberleşme yükü ve gereksiz enerji tüketimi engellenmeye çalışılmıştır. Sensör düğümler, ağ hakkında global bir bilgiye sahip olmadan yerel düzeyde ağın dinamiklerine uyum sağlamıştır. Bu da geliştirilen yöntemlerin büyük boyutlu kablosuz sensör ağlara da uyumlu olmasını sağlamıştır.

Wireless sensor networks (WSN) consists of energy-constrained, tiny sensor nodes that collect data (temperature, pressure, humidity etc.) from environment. Sensor nodes have low computational capabilities and constrained energy. So energy efficiency of sensor nodes becomes critical for WSNs. Idle listening causes unnecessary energy consumption for nodes. Sensor nodes consume energy in idle listening as much as in packet receiving. Duty cycling is widely applied for preventing idle listening. Forwarder set based dynamic duty cycling method is proposed. In proposed model, nodes update their duty cycle in a distributed manner. There are no communication overhead and energy consumption due to coordination among sensor nodes. XMAC in MAC layer and contention-based geographic forwarding in network layer are adopted in the thesis. In XMAC, sender sends short preambles to next hop. If one of the preambles is detected by the intended receiver, the node sends back an ACK. If the detecting node is not the intended next hop, the node goes back to sleep. In contention-based geographic forwarding, the nodes in the forwarder set a timer, when the node receives one of the preambles. The closest node to the sink has the smallest timer. So the timer of the closest nodes expires first. Then the closest node sends back an ACK and the other nodes in the forwarder set return back their duty cycle. Finally data transmission between sender and receiver begins. XMAC is modified for supplying compatibility between XMAC and contention-based geographic forwarding. Therefore, preambles contain the geographic location of sender node. Each sensor node knows the times that it has been in the forwarder set and the times that it has been next hop in packet transmission. If sensor node has been in forwarder set but it is not selected as next hop frequently, then it decreases its duty cycle for increasing the probability of being next hop. Vice versa, if sensor node has been next hop so frequently, it implies that the node has been the next hop at many packet transmissions. Then duty cycle of the node is reduced to decrease the energy consumption of node. Furthermore remaining energy of the nodes is used as a constraint in proposed duty cycle adjustment model. Proposed duty cycle adjustment scheme obtains two times longer lifetime comparing with node degree based duty cycling scheme and six times longer lifetime comparing with constant duty cycling. Remaining energy of nodes distributed evenly in WSN comparing with node degree based dynamic duty cycling and constant duty cycling. Alternatively, delay performance degraded slightly comparing with constant duty cycling. Secondly, adaptive sink selection scheme is applied to nodes that works with forwarder set based dynamic duty cycling for failure resistance. Multi-sink WSNs are adopted in the scheme. Sender nodes tries to send its packet to a potential receiver. If any node in forwarder set does not send ACK after maximum allowable sleeping time, sender node feels node failure. Then, the sender node complements its forwarder set. It can forward the packets through the nodes that are farther to the sink than itself. Packets can be forwarded to other sink by this way. If sender node cannot send its packet to a neighbour node after determined number of preambles, the node sends its packet any of its neighbours by complementing its forwarder set. In the evaluations for adaptive sink selection scheme, WSN with four sink is adopted. Proposed model is tested with four node failure scenario. Each sink creates its virtual regions that consists of the nodes whose closest sink is itself. In the proposed scheme, it works same as regular geographic forwarding in no failure case. Packet loss rate is dropped and throughput is increased comparing with geographic forwarding in node failure scenarios. Furthermore, delay performance is slightly decreased comparing with geographic forwarding. It is an expected results. When re-routing the packet to other sinks, the number of hops that packets are forwarded, is increased. Here, degradation in delay is tolerable compared with reduced packet loss rates. To sum up, we have studied dynamic duty cycle assignment problem and introduced a distributed scheme based on remaining energy and forwarder set of nodes. Secondly, we have studied fault tolerance in multi-sink WSNs and introduced an adaptive geographic forwarding technique in order to prevent packet loss due to node failures. Number of preambles is employed to estimate node failures. In this thesis, we aim to develop a self-organized WSN. Nodes decide their duty cycles and their forwarder set themselves. Coordination causes communication overhead and energy consumption due to packet transmissions. There is no need to coordination amongst sensor nodes for duty cycle adjustment and failure detection. In the future work, we are planning to improve the performance of the next hop nodes by working on preambles. The forwarder set based duty cycle scheme introduced will be studied extensively by simulations under heavy traffic with ultra-low duty cycled nodes paying attention to collisions. Furthermore we are planning to fine tune the detection of node failures by varying the number of preambles, Nmax and using some other parameters obtained from the sensor nodes.