20.500.12556/DKUM-16342 Prometno uravnoteženi usmerjevalni algoritmi za brezžična senzorska omrežja : doktorska disertacija Load balanced routing protocols for wireless sensor networks Brez i ne komunikacije, kot na primer GSM tehnologija, WiFi vstopne točke, digitalna televizija in drugo postajajo v naših ž ivljenjih vedno bolj prisotna. Cenovna dostopnost komponent in nagel industrijski razvoj je vzpodbudil uporabo brezžičnih komunikacij tudi v osebne namene (kot primer podajmo samo GSM telefon in BlueTooth slušalko). Ljudje smo vedno bolj vpeti v svet komunikacij pa se često tega niti ne zavedamo. Vedno manjše, cenejše in zmogljivejše komponente so pripomogle k uporabi brezžičnih komunikacij v prej nepredstavljivih aplikacijah. Eno izmed takšnih aplikacij predstavljajo tudi brezžična senzorska omrežja (BSO). Brezžična senzorska omrežja so omrežja, sestavljena iz majhnih, baterijsko napajanih, pametnih senzorjev sposobnih brezžične komunikacije. Njihova radijska vidljivost je ponavadi majhna, cena pa tako nizka, da senzorske enote po uporabi preprosto zavržemo. Namenjena so spremljanju različnih fenomenov (sezmiologija, spremljanje habitata, spremljanje požarov, vojaške aplikacije... ). Med intenzivnejše raziskave brežičnih senzorskih omrežij že od vsega začetka spadajo raziskave usmerjevalnih algoritmov. Standardni usmerjevalni algoritmi uporabljeni v standardih IEEE 802.11x zaradi posebnosti BSO niso uporabni ali pa je njihova uporaba v BSO nesmiselna (zaradi velike potrošnje procesorskih ali spominskih virov ter energije). Posledično so raziskave usmerjene v za brezžična senzorska omrežja posebej prilagojene protokole usmerjanja prometa. V tezi smo se omejili na raziskave prometno uravnote enih algoritmov, ki sporočila pošiljajo po najkrajši možni poti (minimalno število etap). Raziskovali smo usmerjanje v statičnih BSO, kjer senzorji s časom ne spreminjajo svoje lege ali pa jo spreminjajo v intenziteti, ki ni bistvena za delovanje algoritmov. Predlagan usmerjevalni protokol je sestavljen iz dveh algoritmov: BFS algoritma in optimalnega polprirejanja. Algoritem za izra un minimalnega števila potrebnih etap, da je sporočilo poslano od vozlišča do bazne postaje je v bistvu dodelan BFS algoritem. Z BFS algoritmom izračunamo nivo vsakega vozlišča (nivo predstavlja oddaljenost od bazne postaje v etapah) v omrežju. Vozlišča iz dveh sosednjih nivojev za potrebe algoritma iskanja optimalnega polprirejanja predstavimo kot virtualni dvodelni graf. Teh virtualnih grafov je za ena manj kot število nivojev vozlišč (n -1). Na vsak kem virtualnem dvodelnem grafu posebej izračunamo optimalno polprirejanje. Cilj optimalnega polprirejanja je uravnotežitev prometa med vozlišči. Skupen rezultat obeh algoritmov je topologija imenovana topologija prirejanja. Topologija prirejanja je v bistvu vpeto drevo, ki ga uporablja protokol usmerjanja. Kvaliteto uravnotežitve na vseh nivojih vpetega drevesa ocenimo po metriki faktorja uravnotežitve (Chebyshevo sumo). V delu predlagamo tudi nov, hitrejši algoritem za izračun optimalnega polprirejanja. Eksperimenti so pokazali, da je izvajanje algoritma vsaj 15 % hitrejše kot pri ostalih, do sedaj znanih algoritmih. Za testiranje in simuliranje usmerjevalnega protokola smo uporabili standardni MAC protokol (IEEE 802.15.4), temelje na CSMA-CA izmikanju kolizij, kateremu smo dodali e RTS/CTS kontrolne okvirje. Za potrditev teze smo uporabili simulacijsko okolje OPNET kjer smo razvili model prototipa brezžičnega senzorskega vozlišča SPaRCMosquito razvitega v laboratoriju. Rezultati simulacij so potrdili, da protokol zaradi svojega načina delovanja pripomore k manj i porabi energije celotnega senzorskega omre ja in kraj im latentnim časom sporočil poslanih od senzorskih vozlišč do bazne postaje. Predlagan usmerjevalni algoritem Wireless communications, such as GSM telephony, WiFi access points, digital television over the air, and others have great impact on our lives. Low prices of electronic components and rapid hardware development are encouraging personal use of a wireless communications (i.e., GSM phones, Bluetooth headsets). We are becoming part of a digital communication society without really realizing it. The foundations of wireless technology were set with smaller, cheaper and more powerful wireless components were foundations. Nowadays they are a common part in building previously unimaginable applications. One area of expertise in wireless communications are Wireless Sensor networks. Wireless sensor networks are assembled from small, battery powered, smart sensors capable of a wireless communication called Sensor Nodes (or joust nodes). Node radio range of sight is normally limited to a few ten meters or less. These nodes are low-cost hardware equipment, thus in majority of cases after battery depletion, they are discarded. One of the most intensely researched topics in WSN are routing algorithms and protocols. Standard routing algorithms, like those used in IEEE 802.11x are, due to WSN characteristics (e.g., limited energy consumption, low CPU and memory resources...) not appropriate for use in the wireless sensor networks. In the PhD thesis we have focused on traffic balanced algorithms which sends messages over shortest path possible or available (expressed as minimum number of hops). Our research target was static wireless sensor network, where the sensors do not change position in time, or the speed of a moving node does notimpact the algorithm calculations. Routing algorithm implements two sub algorithms: BFS and semi matching. Algorithm for determining minimum number of hops needed from message to be send from a node to the base station is basically a BFS algorithm. BFS algorithm calculates the level of each node (hop distance from the BS) in the network. Nodes irons the two neighboring levels are then assigned as members of a virtual bipartite graph. On every bipartite graph semi matching is calculated. Semi matching algorithm balances the load evenly across nodes. Result of the BFS and semi matching algorithm isa topology (called matching topology) - a spanning tree which is Later used in a routing protocol. We accomplish to write new, fastest algorithm for calculating optimal semi matching. The experimental results showed that our proposed algorithm gives optimal results and preforms at least 15 % faster than other state of art algorithms. For testing and simulation purposes we used standard IEEE 802.15.4 PHY and MAC protocol, based on CSMA-CA algorithm. Later on we added RTS and CTS control packets for avoiding hidden node problem. Simulations for confirming thesis were done in OPNET simulation tool,where we have developed a model of a wireless sensor network node called SPaRCMosquito. Simulation results have confirmed that using protocol SPaRCRoute results in lower power consumption, lower latency, and a higher throughput of the network. Proposed routing algorithm SPaRCRoute was implemented on a test network consisted of 9 SPaRCMosquito nodes. brezžična senzorska omrežja protokoli usmerjanja teorija grafov uravnoteževanje obremenitev wireless sensor networks routing protocol graph theory load balancing true true false [K. Benkič] Slovenski jezik Angleški jezik Doktorska disertacija 2010-10-12 12:49:24 2010-10-12 12:49:24 2022-04-13 08:05:13 2023-12-20 03:29:10 2010 0 Maribor 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 681.586.5:621.396(043.3) 14454806 URN:SI:UM:DK:DTJABQA0 DR_Benkic_Karl_2010.pdf DR_Benkic_Karl_2010.pdf 1 89535F7CCE293BB5FB0CDAEB9B79EC74 fdb27d3cd072f8a75f99595f6ed2887d8ad7fa8a659933e3997ceeed1db85714 a0534931-7c04-11eb-bb7a-00155d0001ca 20.500.12556/dkum/898f68d2-bd96-4812-9d0a-ede45cb8fdf8 https://dk.um.si/Dokument.php?lang=slv&id=18480 Fakulteta za elektrotehniko, računalništvo in informatiko 0 0 0