Topology-aware optimal task allocation framework for mission critical environment: Centralized and decentralized approaches

A Mission Critical Environment (MCE) consists of error-prone, highly variable, and highly rate limited communication channels. Paradoxically, this environment substantially increases the need to perform Optimal Task Allocation (OTA), while at the same time making it much harder to perform OTA efficiently. To perform OTA in MCE, in this thesis, I have proposed two novel automated algorithms. The first algorithm is called Centralized Optimal Task Allocation Algorithm (COTAA), where I consider OTA for publish/subscribe-based MCE since it has unique characteristics such as high level publish/subscribe node and task differentiation and high scalability. I also propose an architectural framework and communication protocols emphasizing the unique challenges of MCE. I adopt well known Hungarian Algorithm and Rectangular Assignment Algorithm to solve the OTA problem in polynomial time. The second algorithm is called Decentralized Optimal Task Allocation Algorithm (DOTAA) which exploits the concept of application-layer Distributed Hash Table (DHT) to perform OTA in MCE. Through simulations, I evaluate the performance of both COTAA and DOTAA for multiple mission critical scenarios. The results indicate that both COTAA and DOTAA achieve the goal of OTA in highly dynamic MCEs, with low processing time and communication overhead.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2011

Author dc:creator

• Ahmed, Shameem

Contributors dc:contributor

• Nahrstedt, Klara

• Mission Critical Environment
• Optimal Task Allocation
• Centralized Optimal Task Allocation Algorithm (COTAA)
• Decentralized Optimal Task Allocation Algorithm (DOTAA)

Statement dc:rights

• Copyright 2011 Shameem Ahmed

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/24267

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/24267