Algoritmi za dodelu zadataka izvršiocima u bežičnim mrežama mikrokontrolerskih senzorskih uređaja i autonomnih robota
| Autor: | Lukić Milan |
|---|---|
| Jazyk: | srbština |
| Rok vydání: | 2015 |
| Předmět: | |
| Druh dokumentu: | Diplomová práce |
| Popis: | U bežičnoj mreži senzora i robota, senzorski moduli vrše nadzorfizičkih veličina od značaja, a roboti imaju ulogu izvršilacazadataka koji im se dodeljuju primenom odgovarajućeg algoritma. Nakondetekcije događaja od strane statičkih senzorskih čvorova iprosleđivanja informacija o događajima robotima, potrebno jedodeliti zadatke robotima na efikasan način. Dodela zadataka vršise u skladu sa prirodom različitih scenarija koji se mogu javiti upraksi. U okviru disertacije razmatran je slučaj kada se konkurentnojavlja više događaja kojima je potrebno dodeliti izvršioce. U pogleduenergetske efikasnosti, u ovakvim sistemima kao ključni problemijavljaju se minimizacija ukupne dužine kretanja robota i optimizacijakomunikacije u mreži. Od komunikacinih protokola za otkrivanjeizvršilaca, u ovoj disertaciji predstavljena su poboljšanjapostojećeg iMesh protokola i uveden je novi vCell protokol zasnovan nalokalizovanom formiranju ćelija Voronoi dijagrama. Takođe,upoređene su performanse novog protokola sa postojećim (pravougaonikvorum i iMesh) u gustim mrežama, retkim mrežama i mrežama sarupama u topologiji. Uz to, uvedeni su algoritmi za ažuriranje lokacijekojima mreža reaguje na kretanje robota. Rezultati simulacija pokazujuda vCell postiže efikasnost blizu 100% u nalaženju najbližeg robota ugustim mrežama. U retkim mrežama, efikasnost mu je do 40% bolja uodnosu na ostala rešenja.Kao glavni rezultat u disertaciji prikazani su novi algoritmi zadodelu robota kao izvršilaca zadataka događajima, čime suprevaziđni nedostaci više do sada poznatih rešenja ovog problema.Za zadati skup događaja i skup robota, svakom događaju dodeljen je pojedan robot koji je zadužen za obilazak lokacije događaja. Tokompojedinačnih rundi, robotima je dozvoljen obilazak jednog događajakada se vrši uparivanje, ili više događaja, kada se vršisekvencijalna dodela. U distribuiranom slučaju, statički senzorskiuređaji detektuju događaje i prijavljuju ih obližnjim robotima.Algoritam PDM koji se odnosi na unapređeno uparivanje sa mogućnošćurazmene partnera, eliminiše dugačke ivice koje se mogu javitiprilikom uparivanja. Algoritam SQD za sekvencijalnu dodelu događajarobotima iterativno pronalazi par robot-događaj sa najmanjimmeđusobnim rastojanjem, uvrštava izabrani događaj u listu za oblazakizabranog robota i ažurira poziciju robota. Takođe su predloženegeneralizacije koje omogućavaju da događaji budu posećeni od straneviše robota i koje uzimaju u obzir vremenska ograničenja.Distribuirani algoritam MAD, koji je zasnovan na iMeshinformacionoj strukturi i lokalnim aukcijama u robotskoj mreži,vrši dodelu robota događajima na lokalizovan i energetski efikasannačin. Rezultati simulacija potvrđuju prednosti predloženihalgoritama u odnosu na postojeća rešenja, kako u pogledu skraćivanjadužina putanja robota, tako i u produženju životnog vremena sistema. In a typical wireless sensor and robot network, sensor nodes monitor physicalvalues of interest, while robots perform some automated tasks. The tasks areassigned to robots by means of an appropriate algorithm. Upon theoccurrence of events which are detected by sensor nodes, the informationabout the events needs to be delivered to robots. Afterwards, it is necessaryto assign tasks to robots in an efficient way. Task assignment is performedaccording to the nature of different scenarios which might occur in practice.This thesis is focused on the case when multiple events, all of which requireto be visited by robots, happen simultaneously. Regarding energy efficiency,the key issues which arise in such systems are minimization of robot travelpaths, and optimization of the network traffic. In this thesis, the followingservice discovery protocols are presented: improvements of the existingiMesh protocol, and the novel vCell protocol, which is based on localizedformation of an information structure which resembles Voronoi diagram.Furthermore, the performaces of new vCell protocol is compared with theexisting protocols (Quorum and iMesh) in dense networks, sparse networks,and networks with holes in topology. Also, location update algorithms areintroduced, which deal with robot mobility. The simulations show that vCellachieves nearly 100% success rate in finding the nearest robot in densenetworks. In sparse networks, it outperforms the other existing solutions by upto 40%.As a key contributtion, the novel dispatch lgorithms have been introduced.Given a set of events and a set of robots, the dispatch problem is to allocateone robot for each event to visit it. In a single round, each robot may beallowed to visit only one event (matching dispatch), or several events in asequence (sequence dispatch). In a distributed setting, each event isdiscovered by a sensor and reported to a robot. In this thesis, novelalgorithms are presented, whichh are aimed at overcoming the shortcomingsof several existing solutions. Pairwise distance based matching algorithm(PDM) eliminates long edges by pairwise exchanges between matching pairs.Sequence dispatch algorithm (SQD) iteratively finds the closest event-robotpair, includes the event in dispatch schedule of the selected robot andupdates its position accordingly. When event-robot distances are multiplied byrobot resistance (inverse of the remaining energy), the corresponding energybalancedvariants are obtained. Also, generalizations are introduced whichhandle multiple visits and timing constraints. Distributed algorithm MAD isbased on information mesh infrastructure and local auctions within the robotnetwork for obtaining the optimal dispatch schedule for each robot. Thesimulations conducted confirm the advantages of our algorithms over otherexisting solutions in terms of average robot-event distance and lifetime. |
| Databáze: | Networked Digital Library of Theses & Dissertations |
| Externí odkaz: |
|