Adaptive resource allocation in mobile ad hoc computational grids

Two key components contribute to task completion time: execution cost and communication cost. The communication cost is induced by data transfers from one task to another residing on separate nodes. To reduce communication cost, interdependent tasks are allocated to closely located nodes. However, once tasks are allocated, nodes can move within a Grid. The node mobility within a Grid can increase communication distance and may result into multi-hop communication between nodes executing dependent tasks. The multi-hop communication increases communication cost and thus task completion time. In order to avoid multi-hop communication between dependent tasks, we have developed an adaptive and distance-based resource allocation scheme which exploits the characteristics of an application and nodes, and applies migration heuristics to reduce communication cost. The scheme is validated in a simulated environment using various workloads and parameters.