Yönlü algılayıcı ağlarda dönme ve hareket yetenekleri ile kapsama alanının iyileştirilmesi
Coverage enhancement exploiting both motility and mobility in directional sensor networks
Yazar: M. AMAÇ GÜVENSAN
Danışman: YRD. DOÇ. DR. A. GÖKHAN YAVUZ
Yıldız Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Doktora, 2011
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control

Özet:
Dairesel-yönlüalgılayıcı ağlarda kapsama alanı optimizasyon problemi son 10 yılda çok detaylı bir şekilde incelenmiştir. Öte yandan, yönlü algılayıcı ağlarda (YAA) kapsama alanı problemi son yıllarda, özellikle çoklu ortam algılayıcı ağların yaygınlaşması ile araştırmacıların ilgisini çekmektedir. Sesüstü, kızıl ötesi, video kamera vb. sensörlere sahip yönlü algılayıcı düğümler (YAD), geleneksel dairesel-yönlü algılama yapan düğümlerden, görüş açısı, çalışma yönü, görüş açıklığı (Line of Sight (LoS)) vb. kendilerine özel karakterleri nedeniyle farklıdırlar. Bu nedenle, yönlü algılayıcı ağlardaki kapsama alanı problemi daha özel çözüm ve tekniklere ihtiyaç duyar.Yönlü algılayıcı ağlarda rasgele dağıtım, görüş alanlarının örtüşmesine, engellerden olumsuz etkilenmesine, kapsama boşluklarının oluşmasına, dolayısıyla kapsama alanının verimli kullanılamamasına yol açmaktadır. Tekrar dağıtım, fazla sayıda YAD kullanılması, tam kapsama için önerilen çözümlerden bazılarıdır. Fakat yüksek maliyetleri, çevreye verilen zarar ve istenilen kapsama oranının garanti edilememesi bu yöntemlerin pek tercih edilmemesine yol açmaktadır. Kapsama alanı problemi için üretilen çözümlerin başında, ilk dağıtım sonrası YAD'ların kendilerini organize ederek görüş alanlarını verimli kullanmaları gelir. Bu çözümler arasında iki temel yaklaşım söz konusudur; dönme yeteneği (motility) ve hareket yeteneği (mobility). Dönme yeteneği, YAD'ların kendi etraflarında dönerek çalışma yönlerini belirlemesini ifade ederken, hareket yeteneği ise YAD'ların fiziksel olarak bir noktadan başka bir noktaya gidebilmesine karşılık gelmektedir.YAA'larda kapsama alanı problemini çözmek için ortaya atılan çalışmalar dört grupta toplanmıştır; hedef-tabanlı çözümler, alan-tabanlı çözümler, bağlanabilirlik garantili çözümler ve ağ yaşam süresi uzatan çözümler. Önerilen çözümlerin çoğunda YAD'ların dönme yeteneğinden faydalanılmıştır. Öte yandan, hareket yeteneği sunduğu esneklik sayesinde oldukça önemli bir özelliktir. Fakat yüksek enerji maliyeti, hareket yeteneğinin araştırmacılar tarafından ortaya atılan çözümlerde pek tercih edilmemesine neden olmuştur.Bu tez çalışmasında, dönme ve hareket yeteneğinin kapsama alanı iyileştirme oranına ve enerji tüketimine etkisi incelenmiştir. Sadece dönme yeteneğinin kapsama alanı iyileştirmede belirli bir eşik değerini aşamaması, sadece hareket yeteneğinin ise yüksek enerji tüketimi bizi hibrit bir çözüm oluşturmaya yöneltmiştir. Tez çalışması kapsamında, sırasıyla dönme ve hareket yeteneklerinin ardışıl bir şekilde kullanıldığı hibrit bir çözüm olan yeni bir yöntem, hibrit hareket stratejisi (HHS), önerilmiştir. Önerilen çözüm, dönme yeteneğinin düşük enerji tüketimi ile hareket yeteneğinin esnekliğini biraraya getirmektedir. Hibrit hareket stratejisi, kapsama alanı iyileştirme oranı ile enerji tüketimi arasında dengeyi kuran en iyi çözümdür.Hibrit hareket stratejisi, literatürde yeni bir yöntem olması sebebiyle bir benzeri mevcut değildir. Öte yandan, hibrit çözümün, sadece dönme ve sadece hareket yeteneklerinin kullanıldığı yöntemlere göre üstünlüğünü (verimliliğini) ortaya koymak amacıyla iki adet dönme yeteneğinden faydalanan ve iki adet de hareket yeteneğinden faydalanan toplam 4 adet algoritmik çözüm önerilmiştir. Bu algoritmalar, ölçeklenebilirliği desteklemek, en az seviyede enerji tüketmek ve gerçek hayatta uygulanabilirliklerini sağlamak amacıyla dağıtık yapıda tasarlanmıştır. Ayrıca dönme yeteneğinden faydalanan algoritmik çözümlerimizin, engelsiz ve engelli ortamlarda literatürdeki mevcut çözümlere göre daha fazla iyileştirme sağladığı görülmüştür.Geliştirilen benzetim ortamında yapılan testler sonucunda, hibrit hareket stratejisinin ilk dağıtım sonrası oluşan kapsama alanını %47'ye varan oranlarda iyileştirdiği ve örtüşen alanların tamamına yakınını ortadan kaldırıldığı görülmüştür. Aynı zamanda hibrit hareket stratejisi, sadece dönme yeteneğinin kullanıldığı çözüme göre %7'ye varan daha fazla iyileştirme sağlamıştır. Öte yandan, hibrit çözümde hareket yeteneğinin kontrollü kullanımı, sadece hareket yeteneğinden faydalanılan çözüme göre en az %40 oranında enerji tasarrufu sağlamıştır.Anahtar Kelimeler: Yönlü ve video algılayıcı ağlar, kapsama alanı, örtüşme, görüş açıklığı, enerji tüketimi, dönme yeteneği, hareket yeteneği, hibrit hareket stratejisi

Abstract:
The coverage optimization problem has been examined thoroughly for omni-directional sensor networks in the past decades. However, the coverage problem in directional sensor networks (DSN) has newly taken attraction, especially with the increasing number of wireless multimedia sensor network (WMSN) applications. Directional sensor nodes equipped with ultrasound, infrared, and video sensors differ from traditional omni-directional sensor nodes with their unique characteristics, such as angle of view, working direction, and line of sight (LoS) properties. Therefore, DSN applications require specific solutions and techniques for coverage enhancement.In DSNs, random deployment causes overlapped and occluded regions, coverage holes, i.e. the inefficient usage of the nodes in the observed area. Redeployment and deployment of excessive number of nodes are two well-known solutions for the full-coverage. However, they are not popular, since they pollute the environment, need high budgets and can not guarantee the expected coverage. For the coverage enhancement after the initial deployment, self-orientation of the nodes is a necessity in randomly deployed DSNs. There exist two main approaches for the coverage improvement. motility and mobility. Motility refers to the adjustment of the working direction of the nodes, whereas mobility describes the physical movement of the nodes.Available studies about coverage enhancement are categorized into four groups. Target-based coverage enhancement, area-based coverage enhancement, coverage enhancement with guaranteed connectivity, and network lifetime prolonging. Most existing studies propose solutions based on the motility capability of the directional sensor nodes. On the other hand, mobility is a powerful feature offering great flexibility. Nevertheless, the high energy consumption of mobility discourages researchers to utilize this approach in their solutions.In this thesis, we examine the coverage improvement ratios and energy consumption of motility and mobility capabilities of the directional sensor nodes. Since both motility only solutions can improve the coverage up to a limit and mobility only solutions consumes too much energy, we are encouraged to design a hybrid solution for the coverage problem. In this thesis, we proposed a novel approach, a hybrid movement strategy (HMS), where we exploit motility/mobility in a cascaded manner for the coverage enhancement in DSNs. The proposed approach combines the low-energy consumption of motility with the flexibility of mobility.The hybrid movement strategy is an unique solution among the available methods for the coverage problem. We have designed two algorithms for motility and two algorithms for mobility in order to show the effectiveness of the hybrid movement strategy. These algorithms are distributed algorithms in order to achieve the scalability and the minimization of the energy consumption to use them in real-scenarios easily. We also show that the algorithms based on motility capability outperform the existing solutions for both unobstructed and obstructed scenarios.Simulation results show that the hybrid movement strategy improves the initial coverage up to 47% and minimizes the overlapped regions close to zero. Moreover, the proposed solution achieves up to 7% more coverage than the motility only solution. On the other hand, the controlled usage of mobility has provided at least 40% energy-saving compared to the mobility only solution in our scenarios.Key words: Directional and video sensor networks, coverage, overlapping, line of sight, energy consumption, hybrid movement strategy, motility assisted mobility