A task-based approach for modeling distributed applications on mobile ad hoc networks

Mobile ad hoc networks (MANETs) are inherently prone to network partitioning and link failures due to node mobility. Distributed applications executed on such environments must cope with these events. In this dissertation, a novel application execution framework and model called a task graph is presented that enables a class of distributed applications suitable for MANETs. The framework allows the representation of the logical requirements of a distributed application via a set of sub-tasks that are assigned to computing devices with suitable attributes for their execution. Each sub-task is represented as a node in a graph and patterns of data-flow between them induce dependencies among the corresponding nodes, thus resulting in a task graph (TG) representation. Application requirements can be expressed in terms of attributes assigned to nodes and edges of the task graph.; Discovery of resources, required for assignment of sub-tasks of the application to physical devices, is achieved by matching of node and edge attributes of the task graph with corresponding attributes of physical resources in the MANET. This process is referred to as embedding of the task graph into the dynamic MANET topology. The corresponding optimization problem is shown to be computationally hard (NP-complete) with respect to average graph dilation even when nodes in TG possess distinct attributes. For tree task graphs with the same property, an exact optimal algorithm is proposed with polynomial time complexity. Because the optimal solution is impractical, requiring global attribute and topological information, and quickly invalidated by node mobility, we propose an alternative approach that can be performed efficiently in distributed fashion. The proposed distributed protocol utilizes a greedy algorithm that uses local search for discovering suitable candidate nodes with matching attributes while satisfying the constraints imposed by the task graph structure. The proposed protocol is also capable of recovering from node and route failures inherent in a MANET by scalable mechanisms of disconnection detection, re-instantiation, and TG-patching.; The proposed algorithms are evaluated using a set of metrics proposed for quantifying the performance of MANETs and that of distributed applications executed on them. Simulation results are reported for application scenarios with varying complexity of task graphs, network traffic, and device mobility patterns. These results demonstrate that instantiation of large task graphs occurs reasonably fast even under high mobility scenarios. For example, a 63 node binary tree task graph takes less than 10 seconds to instantiate on average on a reasonably dense MANET consisting of 100 devices that are moving randomly with an average velocity of 10 m/s. Effective throughput is high up to medium degrees of mobility and degrades gracefully with further increase in mobility. Finally, we demonstrate the viability of the approach by the implementation of a proof-of-concept prototype using a network of devices including desktop workstations and handheld computers.