VERTEX COVER BASED LINK MONITORING TECHNIQUES FOR WIRELESS SENSOR NETWORKS
Züleyha Akusta Dağdevıren · 2020
VERTEX COVER BASED LINK MONITORING TECHNIQUES FOR WIRELESS SENSOR NETWORKS Abstract Wireless sensor networks (WSNs) are generally composed of numerous battery-powered tiny nodes that can sense from the environment and send this data through wireless communication. WSNs have wide range of application areas such as military surveillance, healthcare, miner safety, and outer space exploration. Inherent security weaknesses of wireless communication may prone WSNs to various attacks such as eavesdropping, jamming and spoofing. This situation attracts researchers to study countermeasures for detection and prevention of these attacks. Graph theory provides a very useful theoretical basis for solving WSN problems related to communication and security issues. One of the important graph theoretic structures is vertex cover (VC) in which a set of nodes are selected to cover the edges of the graph where each edge is incident to at least one node in VC set. Finding VC set having the minimum cardinality for a given graph is an NP-hard problem. In this paper, we describe VC algorithms aiming link monitoring where nodes in VC are configured as secure points. We investigate variants of VC problems such as weight and capacity constrained versions on different graph types to meet the energy-efficiency and load-balancing requirements of WSNs. Moreover, we present clustering and backbone formation operations as alternative applications of different VC infrastructures. For each VC sub-problem, we propose greedy heuristic based algorithms. Keywords: Wireless Sensor Networks, Link Monitoring, Graph Theory, Vertex Cover, NP-Hard Problem. KABLOSUZ SENSOR AĞLARI ICIN KOSE ORTME TABANLI BAĞLANTI IZLEME TEKNIKLERI Ozet Kablosuz sensor aglar (KSAlar) genellikle ortamdan algilayabilen ve bu verileri kablosuz iletisim yoluyla gonderebilen pille calisan cok sayida kucuk dugumden olusur. KSAlar askeri gozetim, saglik hizmetleri, madenci guvenligi ve uzay kesfi gibi cok cesitli uygulama alanlarina sahiptir. Kablosuz iletisimin dogasinda var olan guvenlik zayifliklari, KSAlari gizli dinleme, sinyal bozma ve sahtekarlik gibi cesitli saldirilara egilimli hale getirebilmektedir. Bu durum, arastirmacilari bu saldirilarin tespiti ve onlenmesine yonelik karsi onlemleri incelemeye yoneltmektedir. Cizge teorisi, iletisim ve guvenlik sorunlari ile ilgili KSA sorunlarini cozmek icin cok yararli bir teorik temel saglar. Onemli cizge teorik yapilardan biri kose ortmedir (KO), bu yapida her bir kenarin KO kumesindeki en az bir dugume bitisik olacak sekilde cizgenin tum kenarlarini kapsayacak bir dizi dugum secilmektedir. Verilen bir cizge icin en az elemana sahip KO kumesini bulmak NP-zor bir problemdir. Bu makalede, KOdeki dugumlerin guvenli noktalar olarak yapilandirildigi baglanti izlemeyi amaclayan KO algoritmalari aciklanmaktadir. KSAlarin enerji verimliligi ve yuk dengeleme gereksinimlerini karsilamak icin, farkli cizge yapilarinda KO problemlerinin agirlik ve kapasite kisitli versiyonlari gibi cesitli turleri calisilmaktadir. Ayrica kumeleme ve omurga olusturma islemlerini farkli KO altyapilarinin alternatif uygulamalari olarak sunulmaktadir. Her KO alt problemi icin, acgozlu sezgisel tabanli algoritmalar onerilmektedir. Anahtar Kelimeler: Kablosuz Sensor Aglari, Baglanti Izleme, Cizge Teorisi, Kenar Ortme, NP-Zor Problem.