Master of Science in Electrical Engineering (MSEE)
Electrical and Computer Engineering
First Committee Member
Second Committee Member
Third Committee Member
Fourth Committee Member
Fifth Committee Member
Kathryn H. Korgan
Number of Pages
Topic of this master's thesis is connected with task allocation algorithms and mesh networks. Author of this work has already graduated from Wroclaw, University of Technology (Poland) where during his studies he created software simulation environment for two different task allocation algorithms for mesh networks:Adaptive ScanandFrame Sliding. Those algorithms were compared by two, main parame- ters: simulation time and average mesh fulfillment (utilization level). All simulations were done in software environment which was developed specially for that research. This application was based on few, different types of objects: task (width, height, processing time), task queue (different number of tasks), task allocator (where different allocation strategies were implemented) and mesh structure (width, height). Whole environment was implemented using C++ language and Xcode IDE (no GUI - simulator is only a tool for this specific research, not a final product).
This work is based on three very well known task allocation algorithms:First Fit,Frame SlidingandAdaptive Scanand also one new approach (author's own idea based on the Adaptive Scan approach) -Snail Algorithm. If new algorithm is able to scan mesh network more accurately, then tasks from the queue are allocated faster than for other algorithms (time needed for processing whole queue will be shorter). If there are more tasks on the mesh at the same time, then overall mesh utilization level (mesh fulfillment) is higher.
It was assumed that all the nodes were exactly the same and there was no delay between them so the communication was instant. This simulator is not taking into account a lot of different parameters and delays which are however present in real life situations. For example communications delays, time needed for allocator to allocate tasks from queue on the mesh structure etc. All the experiments are based only on the execution time inside the mesh so it was easier to compare all algorithms and conclude which task arrangement is providing shorter task queue execution time and better mesh utilization level.
Adaptivescan; Algorithms; Allocation; Computer networks; Firstfit; Framesliding; Mesh; Snail
Computer Engineering | Electrical and Computer Engineering
Duszel, Bartosz, "Snail Algorithm For Task Allocation In Mesh Networks" (2013). UNLV Theses, Dissertations, Professional Papers, and Capstones. 1983.