Scate: A Scalable Time and Energy Aware Actor Task Allocation Algorithm in Wireless Sensor and Actor Networks

ETRI Journal

关键词: min-min;    max-min;    scalability;    energy-awareness;    task allocation algorithm;    Wireless sensor actor networks;   

Others  :  1186366
DOI  :  10.4218/etrij.12.0111.0366

【 摘 要 】

In many applications of wireless sensor actor networks (WSANs) that often run in harsh environments, the reduction of completion times of tasks is highly desired. We present a new time-aware, energy-aware, and starvation-free algorithm called Scate for assigning tasks to actors while satisfying the scalability and distribution requirements of WSANs with semi-automated architecture. The proposed algorithm allows concurrent executions of any mix of small and large tasks and yet prevents probable starvation of tasks. To achieve this, it estimates the completion times of tasks on each available actor and then takes the remaining energies and the current workloads of these actors into account during task assignment to actors. The results of our experiments with a prototyped implementation of Scate show longer network lifetime, shorter makespan of resulting schedules, and more balanced loads on actors compared to when one of the three well-known task-scheduling algorithms, namely, the max-min, min-min, and opportunistic load balancing algorithms, is used.

   

【 参考文献 】

• [1]F. Xia et al., “Wireless Sensor Actuator Network Design for Mobile Control Applications,” Sensors, vol. 7, 2007, pp. 2157-2173.
• [2]I.F. Akyildiz and I.H. Kasimoglu, “Wireless Sensor and Actor Networks: Research Challenges,” Ad-Hoc Netw., vol. 2, 2004, pp. 351-367.
• [3]A. Nayak and I. Stojmenovic, Wireless Sensor and Actuator Networks: Algorithms and Protocols for Scalable Coordination and Data Communication, Hoboken, New Jersey: Wiley Press, 2010.
• [4]I. Stojmenovic, Energy Conservation in Sensor and Sensor-Actuator Networks, Wireless Ad-Hoc Networking: Personal-Area, Local-Area, and Sensory-Area Networks, S.-L. Wu and Y.-C. Tseng, Eds., Auerbach Publications, 2007, Ch. 4, pp. 107-133.
• [5]X. Cao et al., “Building Environment Control with Wireless Sensor and Actuator Networks: Centralized vs. Distributed,” IEEE Trans. Ind. Electron., vol. 57, no. 11, 2010, pp. 3596-3605.
• [6]J. Chen et al., “Distributed Collaborative Control for Industrial Automation with Wireless Sensor and Actuator Networks, IEEE Trans. Ind. Electron., vol. 57, no. 12, 2010, pp. 4219-4230.
• [7]R. Armstrong, D. Hensgen, and T. Kidd, “The Relative Performance of Various Mapping Algorithms is Independent of Sizable Variances in Run-Time Predictions,” Proc. IEEE Int. Workshop Heterogeneous Comput., 1998, pp. 79-87.
• [8]R.F. Freund et al., “Scheduling Actors in Multi-User, Heterogeneous, Computing Environments with SmartNet,” Proc. IEEE Int. Workshop Heterogeneous Comput., 1998, pp. 184-199.
• [9]R.F. Freund and H.J. Siegel, “Heterogeneous Processing,” IEEE Comput., vol. 26, 1993, pp. 13-17.
• [10]T.D. Braun et al., “A Comparison of Eleven Static Heuristics for Mapping a Class of Independent Tasks onto Heterogeneous Distributed Computing Systems,” Parallel Distrib. Comput., vol. 61, 2001, pp. 810-837.
• [11]M. Maheswaran et al., “Dynamic Mapping of a Class of Independent Tasks onto Heterogeneous Computing Systems,” Parallel Distrib. Comput., vol. 59, 1999, pp. 107-121.
• [12]Y. Tian, E. Ekici, and F. Ozguner, “Energy-Constrained Task Mapping and Scheduling in Wireless Sensor Networks,” Proc. IEEE Int. Conf. Mobile ad-hoc Sensor Syst., 2005, pp. 8-16.
• [13]Y. Yu and V.K. Prasanna, “Energy-Balanced Task Allocation for Collaborative Processing in Wireless Sensor Networks,” Mobile Netw. Appl., vol. 10, 2005, pp. 115-131.
• [14]M. Okhovvat, M. Sharifi, and H. Momeni, “Task Allocation to Actors in Wireless Sensor Actor Networks: An Energy and Time Aware Technique,” Procedia Computer Science, vol. 3, 2011, pp. 484-490.
• [15]S. Shivle et al., “Static Mapping of Subtasks in a Heterogeneous Ad-Hoc Grid Environment,” Symp. Parallel Distrib. Process., 2004.
• [16]M.H.A. Awadalla and R.R. Darwish, “Quality of Service Constrained Task Mapping and Scheduling Algorithm for Wireless Sensor Networks,” Computer Eng. Research, vol. 2, 2011, pp. 8-18.
• [17]P. Brucker, Scheduling Algorithms, 5th ed., Springer Press, 2007.
• [18]O.H. Ibarra and C.E. Kim, “Heuristic Algorithms for Scheduling Independent Tasks on Non-Identical Processors,” J. ACM, vol. 24, 1977, pp. 280-289.
• [19]K.S. Golconda and F.O. Zguner, “A Comparison of Static QoS-based Scheduling Heuristics for a Meta-Task with Multiple QoS Dimensions in Heterogeneous Computing,” Symp. Parallel Distrib. Process., 2004.
• [20]H. Liu, Y.W. Leung, and X. Chu, Eds., Ad-hoc and Sensor Wireless Networks: Architectures, Algorithms and Protocols, Bentham Science Publishers, 2009, Ch. 1.
• [21]A. Cenedese, L. Schenato, and S. Vitturi, “Wireless Sensor/Actor Networks for Real-Time Climate Control and Monitoring of Greenhouses,” ING-INF/04 Automatica, 2008. Available at paduaresearch.cab.unipd.it/1045/01
• [22]B.H. Calhoun et al., “Design Considerations for Ultra-Low Energy Wireless Microsensor Nodes,” IEEE Trans. Comput., vol. 54, no. 6, 2005, pp. 727-740.