Algoritmi za dodelu zadataka izvršiocima u bežičnim mrežama mikrokontrolerskih senzorskih uređaja i autonomnih robota

Abstract

U bežičnoj mreži senzora i robota, senzorski moduli vrše nadzor fizičkih veličina od značaja, a roboti imaju ulogu izvršilaca zadataka koji im se dodeljuju primenom odgovarajućeg algoritma. Nakon detekcije događaja od strane statičkih senzorskih čvorova i prosleđivanja informacija o događajima robotima, potrebno je dodeliti zadatke robotima na efikasan način. Dodela zadataka vrši se u skladu sa prirodom različitih scenarija koji se mogu javiti u praksi. U okviru disertacije razmatran je slučaj kada se konkurentno javlja više događaja kojima je potrebno dodeliti izvršioce. U pogledu energetske efikasnosti, u ovakvim sistemima kao ključni problemi javljaju se minimizacija ukupne dužine kretanja robota i optimizacija komunikacije u mreži. Od komunikacinih protokola za otkrivanje izvršilaca, u ovoj disertaciji predstavljena su poboljšanja postojećeg iMesh protokola i uveden je novi vCell protokol zasnovan na lokalizovanom formiranju ćelija Voronoi dijagrama. Takođe, upoređene su performanse novog protokola sa postojećim (pravougaoni kvorum i iMesh) u gustim mrežama, retkim mrežama i mrežama sa rupama u topologiji. Uz to, uvedeni su algoritmi za ažuriranje lokacije kojima mreža reaguje na kretanje robota. Rezultati simulacija pokazuju da vCell postiže efikasnost blizu 100% u nalaženju najbližeg robota u gustim mrežama. U retkim mrežama, efikasnost mu je do 40% bolja u odnosu na ostala rešenja. Kao glavni rezultat u disertaciji prikazani su novi algoritmi za dodelu robota kao izvršilaca zadataka događajima, čime su prevaziđni nedostaci više do sada poznatih rešenja ovog problema. Za zadati skup događaja i skup robota, svakom događaju dodeljen je po jedan robot koji je zadužen za obilazak lokacije događaja. Tokom pojedinačnih rundi, robotima je dozvoljen obilazak jednog događaja kada se vrši uparivanje, ili više događaja, kada se vrši sekvencijalna dodela. U distribuiranom slučaju, statički senzorski uređaji detektuju događaje i prijavljuju ih obližnjim robotima. Algoritam PDM koji se odnosi na unapređeno uparivanje sa mogućnošću razmene partnera, eliminiše dugačke ivice koje se mogu javiti prilikom uparivanja. Algoritam SQD za sekvencijalnu dodelu događaja robotima iterativno pronalazi par robot-događaj sa najmanjim međusobnim rastojanjem, uvrštava izabrani događaj u listu za oblazak izabranog robota i ažurira poziciju robota. Takođe su predložene generalizacije koje omogućavaju da događaji budu posećeni od strane više robota i koje uzimaju u obzir vremenska ograničenja. Distribuirani algoritam MAD, koji je zasnovan na iMesh informacionoj strukturi i lokalnim aukcijama u robotskoj mreži, vrši dodelu robota događajima na lokalizovan i energetski efikasan način. Rezultati simulacija potvrđuju prednosti predloženih algoritama u odnosu na postojeća rešenja, kako u pogledu skraćivanja dužina putanja robota, tako i u produženju životnog vremena sistema.

In a typical wireless sensor and robot network, sensor nodes monitor physical values of interest, while robots perform some automated tasks. The tasks are assigned to robots by means of an appropriate algorithm. Upon the occurrence of events which are detected by sensor nodes, the information about the events needs to be delivered to robots. Afterwards, it is necessary to assign tasks to robots in an efficient way. Task assignment is performed according to the nature of different scenarios which might occur in practice. This thesis is focused on the case when multiple events, all of which require to be visited by robots, happen simultaneously. Regarding energy efficiency, the key issues which arise in such systems are minimization of robot travel paths, and optimization of the network traffic. In this thesis, the following service discovery protocols are presented: improvements of the existing iMesh protocol, and the novel vCell protocol, which is based on localized formation of an information structure which resembles Voronoi diagram. Furthermore, the performaces of new vCell protocol is compared with the existing protocols (Quorum and iMesh) in dense networks, sparse networks, and networks with holes in topology. Also, location update algorithms are introduced, which deal with robot mobility. The simulations show that vCell achieves nearly 100% success rate in finding the nearest robot in dense networks. In sparse networks, it outperforms the other existing solutions by up to 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 allocate one robot for each event to visit it. In a single round, each robot may be allowed to visit only one event (matching dispatch), or several events in a sequence (sequence dispatch). In a distributed setting, each event is discovered by a sensor and reported to a robot. In this thesis, novel algorithms are presented, whichh are aimed at overcoming the shortcomings of 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-robot pair, includes the event in dispatch schedule of the selected robot and updates its position accordingly. When event-robot distances are multiplied by robot resistance (inverse of the remaining energy), the corresponding energybalanced variants are obtained. Also, generalizations are introduced which handle multiple visits and timing constraints. Distributed algorithm MAD is based on information mesh infrastructure and local auctions within the robot network for obtaining the optimal dispatch schedule for each robot. The simulations conducted confirm the advantages of our algorithms over other existing solutions in terms of average robot-event distance and lifetime.