<p>U bežičnoj mreži senzora i robota, senzorski moduli vrše nadzor<br />fizičkih veličina od značaja, a roboti imaju ulogu izvršilaca<br />zadataka koji im se dodeljuju primenom odgovarajućeg algoritma. Nakon<br />detekcije događaja od strane statičkih senzorskih čvorova i<br />prosleđivanja informacija o događajima robotima, potrebno je<br />dodeliti zadatke robotima na efikasan način. Dodela zadataka vrši<br />se u skladu sa prirodom različitih scenarija koji se mogu javiti u<br />praksi. U okviru disertacije razmatran je slučaj kada se konkurentno<br />javlja više događaja kojima je potrebno dodeliti izvršioce. U pogledu<br />energetske efikasnosti, u ovakvim sistemima kao ključni problemi<br />javljaju se minimizacija ukupne dužine kretanja robota i optimizacija<br />komunikacije u mreži. Od komunikacinih protokola za otkrivanje<br />izvršilaca, u ovoj disertaciji predstavljena su poboljšanja<br />postojećeg iMesh protokola i uveden je novi vCell protokol zasnovan na<br />lokalizovanom formiranju ćelija Voronoi dijagrama. Takođe,<br />upoređene su performanse novog protokola sa postojećim (pravougaoni<br />kvorum i iMesh) u gustim mrežama, retkim mrežama i mrežama sa<br />rupama u topologiji. Uz to, uvedeni su algoritmi za ažuriranje lokacije<br />kojima mreža reaguje na kretanje robota. Rezultati simulacija pokazuju<br />da vCell postiže efikasnost blizu 100% u nalaženju najbližeg robota u<br />gustim mrežama. U retkim mrežama, efikasnost mu je do 40% bolja u<br />odnosu na ostala rešenja.</p><p>Kao glavni rezultat u disertaciji prikazani su novi algoritmi za<br />dodelu robota kao izvršilaca zadataka događajima, čime su<br />prevaziđni nedostaci više do sada poznatih rešenja ovog problema.<br />Za zadati skup događaja i skup robota, svakom događaju dodeljen je po<br />jedan robot koji je zadužen za obilazak lokacije događaja. Tokom<br />pojedinačnih rundi, robotima je dozvoljen obilazak jednog događaja<br />kada se vrši uparivanje, ili više događaja, kada se vrši<br />sekvencijalna dodela. U distribuiranom slučaju, statički senzorski<br />uređaji detektuju događaje i prijavljuju ih obližnjim robotima.<br />Algoritam PDM koji se odnosi na unapređeno uparivanje sa mogućnošću<br />razmene partnera, eliminiše dugačke ivice koje se mogu javiti<br />prilikom uparivanja. Algoritam SQD za sekvencijalnu dodelu događaja<br />robotima iterativno pronalazi par robot-događaj sa najmanjim<br />međusobnim rastojanjem, uvrštava izabrani događaj u listu za oblazak<br />izabranog robota i ažurira poziciju robota. Takođe su predložene<br />generalizacije koje omogućavaju da događaji budu posećeni od strane<br />više robota i koje uzimaju u obzir vremenska ograničenja.<br />Distribuirani algoritam MAD, koji je zasnovan na iMesh<br />informacionoj strukturi i lokalnim aukcijama u robotskoj mreži,<br />vrši dodelu robota događajima na lokalizovan i energetski efikasan<br />način. Rezultati simulacija potvrđuju prednosti predloženih<br />algoritama u odnosu na postojeća rešenja, kako u pogledu skraćivanja<br />dužina putanja robota, tako i u produženju životnog vremena sistema.</p> / <p>In a typical wireless sensor and robot network, sensor nodes monitor physical<br />values of interest, while robots perform some automated tasks. The tasks are<br />assigned to robots by means of an appropriate algorithm. Upon the<br />occurrence of events which are detected by sensor nodes, the information<br />about the events needs to be delivered to robots. Afterwards, it is necessary<br />to assign tasks to robots in an efficient way. Task assignment is performed<br />according to the nature of different scenarios which might occur in practice.<br />This thesis is focused on the case when multiple events, all of which require<br />to be visited by robots, happen simultaneously. Regarding energy efficiency,<br />the key issues which arise in such systems are minimization of robot travel<br />paths, and optimization of the network traffic. In this thesis, the following<br />service discovery protocols are presented: improvements of the existing<br />iMesh protocol, and the novel vCell protocol, which is based on localized<br />formation of an information structure which resembles Voronoi diagram.<br />Furthermore, the performaces of new vCell protocol is compared with the<br />existing protocols (Quorum and iMesh) in dense networks, sparse networks,<br />and networks with holes in topology. Also, location update algorithms are<br />introduced, which deal with robot mobility. The simulations show that vCell<br />achieves nearly 100% success rate in finding the nearest robot in dense<br />networks. In sparse networks, it outperforms the other existing solutions by up<br />to 40%.<br />As a key contributtion, the novel dispatch lgorithms have been introduced.<br />Given a set of events and a set of robots, the dispatch problem is to allocate<br />one robot for each event to visit it. In a single round, each robot may be<br />allowed to visit only one event (matching dispatch), or several events in a<br />sequence (sequence dispatch). In a distributed setting, each event is<br />discovered by a sensor and reported to a robot. In this thesis, novel<br />algorithms are presented, whichh are aimed at overcoming the shortcomings<br />of several existing solutions. Pairwise distance based matching algorithm<br />(PDM) eliminates long edges by pairwise exchanges between matching pairs.<br />Sequence dispatch algorithm (SQD) iteratively finds the closest event-robot<br />pair, includes the event in dispatch schedule of the selected robot and<br />updates its position accordingly. When event-robot distances are multiplied by<br />robot resistance (inverse of the remaining energy), the corresponding energybalanced<br />variants are obtained. Also, generalizations are introduced which<br />handle multiple visits and timing constraints. Distributed algorithm MAD is<br />based on information mesh infrastructure and local auctions within the robot<br />network for obtaining the optimal dispatch schedule for each robot. The<br />simulations conducted confirm the advantages of our algorithms over other<br />existing solutions in terms of average robot-event distance and lifetime.</p>
| Identifer | oai:union.ndltd.org:uns.ac.rs/oai:CRISUNS:(BISIS)95502 |
| Date | 02 November 2015 |
| Creators | Lukić Milan |
| Contributors | Novak Ladislav, Mezei Ivan, Struharik Rastislav, Menićanin Aleksandar, Borovac Branislav, Vukobratović Dejan |
| Publisher | Univerzitet u Novom Sadu, Fakultet tehničkih nauka u Novom Sadu, University of Novi Sad, Faculty of Technical Sciences at Novi Sad |
| Source Sets | University of Novi Sad |
| Language | Serbian |
| Detected Language | Unknown |
| Type | PhD thesis |
Page generated in 0.0023 seconds