Topology-aware Optimal Task Allocation for Mission Critical Environment - A decentralized approach

A typical mission consists of several deadline-driven, inter-dependent tasks which need to adhere to specific resource constraints. This makes Optimal Task Allocation (OTA) of a particular mission a daunting task, even for simple and less-challenging environments. The inherent challenges of Mission Critical Environment (MCE) (e.g., Disconnected, intermittent, and limited communication among nodes, high error rate, node mobility, etc.) make OTA even harder to accomplish. To address this problem, earlier, we proposed an automated approach, namely, Centralized Optimal Task Allocation Algorithm (COTAA). While COTAA performs OTA in an efficient manner, it is based on some assumptions (e.g., nodes must follow publish/subscribe-based communication model, there is no inter-dependency among tasks, and static central unit is solely responsible for task allocation) that make COTAA applicable only to specific MCEs (e.g., post-disaster recovery) and do not work well for other MCEs such as group-based UAV (Unmanned Aerial Vehicle) operation, robot-driven mission, etc. In this paper, we propose another novel automated approach, Decentralized Optimal Task Allocation Algorithm (DOTAA), which relaxes the above-mentioned assumptions and performs OTA in an efficient manner. In DOTAA, we have exploited the concept of application-layer hash and bidding approach to perform the OTA for larger classes of MCEs. We have also evaluated our solution using ns-2 simulator and our results show that DOTAA outperforms COTAA in terms of scalability, task allocation time, and bandwidth consumption.