Abstract. Nowadays, distributed computing (DC) applications such as ubiquitous participatory sensing, wireless sensor networks (WSNs), and in-network DC are available everywhere due to the low cost of small-sized devices which have processing and wireless communication capabilities. These scenarios impose new constraints to DC, namely, a highly dynamic topology, a considerable number of computing elements (CEs), with restricted computing-power and limited amount of power for consumption. The success of this new class of applications is closely related to scalability issues and to the efficient use of both the limited energy resources and computing power of the CEs. To do so, control mechanisms must be provided to applications and CEs so that they can deal with the problem of smartly and transparently distributing and executing applications among the CEs.

This research effort tackles the problem of efficiently allocating applications onto the available CEs of a distributed computing system (DCS). Here, the specific class of DC applications where hand-held devices and wireless sensors collect, process and disseminate spatial, temporal and/or environmental information, at different time scales, will be considered. The resource allocation problem regarded here aims to answer the questions of: How to efficiently map an application onto a finite number of CEs, while considering their energy consumption, their limited and heterogeneous computing power, the highly dynamic behavior of both the communication network as well as the CEs, and the scalability of the solutions to be provided. By answering this research question, control mechanisms may be provided to applications and CEs so that they can efficiently and transparently distribute and execute applications among the CEs.

Methodology. This project consists in a theoretical and an experimental effort. The theoretical effort aims to develop scalable mathematical models for both the DCS and its applications, and resource allocation algorithms for improving the performance of applications executed on a DCS. The major tools to employ in the modeling are graph theory, optimization, and probability theory. The key ideas for achieving scalability are: (i) organizing applications and the DCS in a hierarchical fashion; and (ii) limiting the amount of communication exchanged among the CEs. The experimental effort consists in implementing prototype DC applications and resource allocation algorithms of interest to the Chilean users of WSNs and pervasive systems. This effort considers also the experimental characterization of the CEs and the implemented applications. Such characterization will be fed into the theoretical models to obtain more practical versions of the theoretical models.

Goals. The main goals of this research proposal are:

1. to develop novel simple and scalable mathematical models for large-scale, energy-constrained DCS;
2. to develop novel off-line scalable resource allocation algorithms for partitioning DC applications on a finite number of computing grids
3. to develop novel computationally cheap resource allocation algorithms which can be implemented on-line at the CEs; and (iv) to implement prototype applications over WSNs and pervasive computing systems composed of smart-phones and tablets.

Expected outcomes. By developing scalable, energy-efficient algorithms and models for DCSs it is expected also to contribute to the field of scalable pervasive computing. The research effort to conduct would enable the analytical optimization of DC applications and the practical implementation of prototype WSNs and smart-phone– and tablet–based DCSs.

Publications.

1. “Implementing the distributed consensus-based estimation of environmental variables in unattended wireless sensor networks,” R. Contreras, S. E. Restrepo, and J. E. Pezoa. In Proc. SPIE Security + Defence, September 22–25, 2014 in Amsterdam, Netherlands.
2. “Impact of Correlated Failures on Wireless Sensor Networks Reliability.” J. E. Pezoa and S. E. Restrepo. Chapter 27 of The Handbook of Sensor Networking: Advanced Technologies and Applications. CRC Press. To be published in September 2014.
3. “An Adaptive Architecture for Ambient Intelligence Based on Meta-modeling, Smart Agents, and Wireless Sensor Networks,” S. E. Restrepo, J. E. Pezoa, and D. A. Ovalle-Carranza. IEEE Latinamerican Transactions, 12(8), pp. 1500-1506, December 2014.
4. “Energy-aware Image Allocation for Distributed Video Processing on Handheld Devices,” S. E. Restrepo, P. Pinaud, J. Pezoa, and S. Sobarzo. In Proc. of the 32nd International Performance, Computing, and Communications Conference (IPCCC 2013), San Diego, CA, USA, December 6–8, 2013.
5. “Wireless Sensor Networks in Forest Fire Detection,” D. E. Parra-Beratto, S. E. Restrepo, and J. E. Pezoa. In Proc. of Communications Workshop, 5th IEEE Latin-American Conference on Communications 2013, Santiago, Chile, November 24-26, 2013.
6. “Optimizing Mission Allocation in Wireless Sensor Networks Under Geographically Correlated Failures,” J. E. Pezoa. In Proc. of the 11th ACM Conference on Embedded Networked Sensor Systems (SenSys 2013), Rome, Italy, November 11-15, 2013.
7. “A Markov Random Field Approach for Modeling Correlated Failures in Distributed Systems,” J. E. Pezoa. In Proc. of The Fourth International Conference on Advances in System Simulation (SIMUL 2012), Lisbon, Portugal, November 18-23, 2012.
8. “CobCel: Distributed and Collaborative Sensing of Cellular Phone Coverage Using Google Android,” J. Pino and J. E. Pezoa. In Proc. of The Seventh International Conference on Systems and Networks Communications (ICSNC 2012), Lisbon, Portugal, November 18-23, 2012.
9. “Modeling and Discrete-event Simulation of Generally Distributed Computing Systems,” J. E. Pezoa. In Proc. of the International Conference on Computational Engineering in Systems Applications CESA 2012, Santiago, Chile, April 25-27, 2012.
10. “Reliability of Heterogeneous Distributed Computing Systems in the Presence of Correlated Failures,” J. E. Pezoa and M. M. Hayat. IEEE Transactions on Parallel and Distributed Computing, 25(4), pp 1034-1043, 2014.

Funding agency: FONDECYT.

Program: FONDECYT Iniciación en Investigación 2011.

Grant number: 11110078.

Funding period: October 2011 — September 2014.

PI: Jorge E. Pezoa.