Topology Aware Task Allocation and Scheduling for Real-Time Data Fusion Applications in Networked Embedded Sensor Systems

In networked embedded sensor systems, data fusion is a viable solution to significantly reduce energy consumption while achieving real-time guarantee. Emerging data fusion applications demand efficient task allocation and scheduling techniques. However, existing approaches can not be effectively applied concerning both network topology and wireless communications. In this paper, we formally model TATAS, the topology-aware task allocation and scheduling problem for real-time data fusion applications, and show it is NP-complete. We also propose an efficient three-phase heuristic to solve the TATAS problem. We implement our technique and conduct experiments based on a simulation environment. Experimental results show that, as compared with traditional approaches, our technique can achieve significant energy saving and effectively meet the real-time requirements as well.