Skip to main content
Erschienen in: Annals of Telecommunications 3-4/2018

01.04.2018

Assignment and collaborative execution of tasks on transient clouds

verfasst von: Mina Guiguis, Qijun Gu, Terry Penner, Lavanya Tammineni, Thomas Langford, Agustin Rivera-Longoria, Alison Johnson, Brandon Van Slyke

Erschienen in: Annals of Telecommunications | Ausgabe 3-4/2018

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Transient clouds (TC) are temporal clouds that enable nearby mobile devices to form an ad hoc network and advertise their capabilities as cloud services. Through utilizing the collective power of the group, devices are no longer constrained by their local hardware and software capabilities. TC harness the ubiquitous nature of mobile devices along with their ever-increasing sets of capabilities in providing a rich computing platform. In this paper, we present two instantiations of task assignment algorithms that achieve various goals such as balancing the load on devices and minimizing the cost of communication. In the first instantiation, we consider a centralized approach in which a cluster head is responsible for maintaining the list of capabilities and assigning tasks to devices based on their capabilities. We present a modified version of the Hungarian method that allows for balancing the load on devices. In the second instantiation, we consider a distributed approach in which devices advertise and find capabilities through an overlay network. The overlay is designed to capitalize on locality and thus seeks to minimize the cost in finding devices with certain capabilities. We evaluate the performance of our TC through extensive simulation experiments complemented by a realistic implementation on a set of devices.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Fußnoten
1
Throughout this paper, we consider a Chord network, but our approach would work with any structured peer-to-peer network.
 
Literatur
2.
Zurück zum Zitat Bahl P, Han RY, Li LE, Satyanarayanan Mahadev (2012) Advancing the state of mobile cloud computing. In: Proceedings of the ACM workshop on mobile cloud computing and services, pp 21–28 Bahl P, Han RY, Li LE, Satyanarayanan Mahadev (2012) Advancing the state of mobile cloud computing. In: Proceedings of the ACM workshop on mobile cloud computing and services, pp 21–28
3.
Zurück zum Zitat Bertsekas DP (1988) The auction algorithm: a distributed relaxation method for the assignment problem. Ann Oper Res 14(1):105–123MathSciNetCrossRefMATH Bertsekas DP (1988) The auction algorithm: a distributed relaxation method for the assignment problem. Ann Oper Res 14(1):105–123MathSciNetCrossRefMATH
4.
Zurück zum Zitat Chintalapudi K, Iyer AP, Padmanabhan VN (2010) Indoor localization without the pain. In: Proceedings of the sixteenth annual international conference on mobile computing and networking. ACM, pp 173–184 Chintalapudi K, Iyer AP, Padmanabhan VN (2010) Indoor localization without the pain. In: Proceedings of the sixteenth annual international conference on mobile computing and networking. ACM, pp 173–184
5.
Zurück zum Zitat Chun B-G, Maniatis P (2009) Augmented smartphone applications through clone cloud execution. In: Proceedings of Usenix HotOS Chun B-G, Maniatis P (2009) Augmented smartphone applications through clone cloud execution. In: Proceedings of Usenix HotOS
6.
Zurück zum Zitat Chun B-G, Maniatis P (2010) Dynamically partitioning applications between weak devices and clouds. In: Proceedings of ACM workshop on mobile cloud computing services: social networks and beyond Chun B-G, Maniatis P (2010) Dynamically partitioning applications between weak devices and clouds. In: Proceedings of ACM workshop on mobile cloud computing services: social networks and beyond
7.
Zurück zum Zitat Cohen R, Katzir L, Raz D (2006) An efficient approximation for the generalized assignment problem. Inf Process Lett 100(4): 162–166MathSciNetCrossRefMATH Cohen R, Katzir L, Raz D (2006) An efficient approximation for the generalized assignment problem. Inf Process Lett 100(4): 162–166MathSciNetCrossRefMATH
8.
Zurück zum Zitat Cuervo E, Balasubramanian A, Cho D-K, Wolman A, Saroiu S, Chandra R, Bahl P (2010) MAUI: making smartphones last longer with code offload, pp 49–62 Cuervo E, Balasubramanian A, Cho D-K, Wolman A, Saroiu S, Chandra R, Bahl P (2010) MAUI: making smartphones last longer with code offload, pp 49–62
9.
Zurück zum Zitat Eom H, St Juste P, Figueiredo R, Tickoo O, Illikkal R, Iyer R (2012) SNARF: a social networking-inspired accelerator remoting framework. In: Proceedings of the workshop on mobile cloud computing, pp 29–34 Eom H, St Juste P, Figueiredo R, Tickoo O, Illikkal R, Iyer R (2012) SNARF: a social networking-inspired accelerator remoting framework. In: Proceedings of the workshop on mobile cloud computing, pp 29–34
10.
Zurück zum Zitat Giurgiu I, Riva O, Juric D, Krivulev I, Alonso G (2009) Calling the cloud: enabling mobile phones as interfaces to cloud applications. In: Proceedings of ACM/IFIP/USENIX international conference on middleware, pp 83–102 Giurgiu I, Riva O, Juric D, Krivulev I, Alonso G (2009) Calling the cloud: enabling mobile phones as interfaces to cloud applications. In: Proceedings of ACM/IFIP/USENIX international conference on middleware, pp 83–102
11.
Zurück zum Zitat Gordon M, Jamshidi D, Mahlke S, Mao Z, Chen X (2012) COMET: code offload by migrating execution transparently. In: Proceedings of OSDI, Hollywood, CA Gordon M, Jamshidi D, Mahlke S, Mao Z, Chen X (2012) COMET: code offload by migrating execution transparently. In: Proceedings of OSDI, Hollywood, CA
12.
Zurück zum Zitat Guirguis M, Ogden R, Song Z, Thapa S, Gu Q (2011) Can you help me run these code segments on your mobile device?. In: Proceedings of IEEE Globecom Guirguis M, Ogden R, Song Z, Thapa S, Gu Q (2011) Can you help me run these code segments on your mobile device?. In: Proceedings of IEEE Globecom
13.
Zurück zum Zitat Kemp R, Palmer N, Kielmann T, Bal H (2012) Cuckoo a computation offloading framework for smartphones. In: Gris M, Yang G (eds) Mobile computing, applications, and services, volume 76 of lecture notes of the institute for computer sciences, social informatics and telecommunications engineering , pp 59–79 Kemp R, Palmer N, Kielmann T, Bal H (2012) Cuckoo a computation offloading framework for smartphones. In: Gris M, Yang G (eds) Mobile computing, applications, and services, volume 76 of lecture notes of the institute for computer sciences, social informatics and telecommunications engineering , pp 59–79
14.
15.
Zurück zum Zitat Langford T, Gu Q, Rivera-Longoria A, Guirguis M (2013) Collaborative computing on-demand: harnessing mobile devices in executing on-the-fly jobs. In: Proceedings of the 2013 IEEE 10th international conference on mobile Ad-Hoc and sensor systems (MASS). IEEE, pp 342–350 Langford T, Gu Q, Rivera-Longoria A, Guirguis M (2013) Collaborative computing on-demand: harnessing mobile devices in executing on-the-fly jobs. In: Proceedings of the 2013 IEEE 10th international conference on mobile Ad-Hoc and sensor systems (MASS). IEEE, pp 342–350
16.
Zurück zum Zitat Langford T, Gu Q, Rivera-Longoria A, Mina G (2013) Collaborative computing on-demand: harnessing mobile devices in executing on-the-fly jobs. In: Proceedings of IEEE MASS , pp 342–350 Langford T, Gu Q, Rivera-Longoria A, Mina G (2013) Collaborative computing on-demand: harnessing mobile devices in executing on-the-fly jobs. In: Proceedings of IEEE MASS , pp 342–350
17.
Zurück zum Zitat Leong B, Liskov B, Demaine ED (2006) Epichord: parallelizing the chord lookup algorithm with reactive routing state management. Comput Commun 29(9):1243–1259CrossRef Leong B, Liskov B, Demaine ED (2006) Epichord: parallelizing the chord lookup algorithm with reactive routing state management. Comput Commun 29(9):1243–1259CrossRef
18.
Zurück zum Zitat Loo BT, Huebsch R, Stoica I, Hellerstein JM (2004) The case for a hybrid p2p search infrastructure. In: Proceedings of the peer-to-peer systems III. Springer, pp 141–150 Loo BT, Huebsch R, Stoica I, Hellerstein JM (2004) The case for a hybrid p2p search infrastructure. In: Proceedings of the peer-to-peer systems III. Springer, pp 141–150
19.
Zurück zum Zitat Miluzzo E, Cáceres R, Chen Y-F (2012) Vision: mClouds—computing on clouds of mobile devices. In: Proceedings of the ACM workshop on mobile cloud computing and services, pp 9–14 Miluzzo E, Cáceres R, Chen Y-F (2012) Vision: mClouds—computing on clouds of mobile devices. In: Proceedings of the ACM workshop on mobile cloud computing and services, pp 9–14
21.
Zurück zum Zitat Penner T, Johnson A, Van Slyke B, Guirguis M, Gu Q (2014) Transient clouds: assignment and collaborative execution of tasks on mobile devices. In: Proceedings of the 2014 IEEE global communications conference (GLOBECOM). IEEE, pp 2801–2806 Penner T, Johnson A, Van Slyke B, Guirguis M, Gu Q (2014) Transient clouds: assignment and collaborative execution of tasks on mobile devices. In: Proceedings of the 2014 IEEE global communications conference (GLOBECOM). IEEE, pp 2801–2806
22.
Zurück zum Zitat Pethalakshmi A, Jeyabharathi C (2014) Geo-chord: geographical location based chord protocol in grid computing. Int J Comput Appl 94(3) Pethalakshmi A, Jeyabharathi C (2014) Geo-chord: geographical location based chord protocol in grid computing. Int J Comput Appl 94(3)
23.
Zurück zum Zitat Satyanarayanan M, Bahl P, Caceres R, Davies N (2009) The case for VM-based cloudlets in mobile computing. IEEE Pervasive Comput 8(4):14–23CrossRef Satyanarayanan M, Bahl P, Caceres R, Davies N (2009) The case for VM-based cloudlets in mobile computing. IEEE Pervasive Comput 8(4):14–23CrossRef
24.
Zurück zum Zitat Sciarrone A, Bisio I, Lavagetto F, Penner T, Guirguis M (2015) Context awareness over transient clouds. In: Proceedings of the 2015 IEEE global communications conference (GLOBECOM), pp 1–5 Sciarrone A, Bisio I, Lavagetto F, Penner T, Guirguis M (2015) Context awareness over transient clouds. In: Proceedings of the 2015 IEEE global communications conference (GLOBECOM), pp 1–5
25.
Zurück zum Zitat Shivarudrappa D, Chen M, Bharadwaj S (2011) COFA: automatic and dynamic code offload for android Shivarudrappa D, Chen M, Bharadwaj S (2011) COFA: automatic and dynamic code offload for android
26.
Zurück zum Zitat Stoica I, Morris R, Karger D, Frans Kaashoek M, Balakrishnan H (2001) Chord: a scalable peer-to-peer lookup service for internet applications. ACM SIGCOMM Comput Commun Rev 31(4):149–160CrossRef Stoica I, Morris R, Karger D, Frans Kaashoek M, Balakrishnan H (2001) Chord: a scalable peer-to-peer lookup service for internet applications. ACM SIGCOMM Comput Commun Rev 31(4):149–160CrossRef
27.
Zurück zum Zitat Tammineni L, Mina G (2016) Toward local overlay-based mobile clouds. In: Proceedings of the smart cloud networks and systems confercence (SCNS) Dubai UAE Tammineni L, Mina G (2016) Toward local overlay-based mobile clouds. In: Proceedings of the smart cloud networks and systems confercence (SCNS) Dubai UAE
28.
Zurück zum Zitat Tanenbaum A, Wetherall D (2011) Computer networks Tanenbaum A, Wetherall D (2011) Computer networks
29.
Zurück zum Zitat Zafari F, Papapanagiotou I, Christidis K (2016) Microlocation for internet-of-things-equipped smart buildings. IEEE Internet Things J 3(1):96–112CrossRef Zafari F, Papapanagiotou I, Christidis K (2016) Microlocation for internet-of-things-equipped smart buildings. IEEE Internet Things J 3(1):96–112CrossRef
30.
Zurück zum Zitat Zaharia M, Keshav S (2004) Adaptive peer-to-peer search. University of Waterloo Technical Report 55 Zaharia M, Keshav S (2004) Adaptive peer-to-peer search. University of Waterloo Technical Report 55
31.
Zurück zum Zitat Zaharia M, Keshav S (2008) Gossip-based search selection in hybrid peer-to-peer networks. Concurr Comput: Pract Exper 20(2):139–153CrossRef Zaharia M, Keshav S (2008) Gossip-based search selection in hybrid peer-to-peer networks. Concurr Comput: Pract Exper 20(2):139–153CrossRef
32.
Zurück zum Zitat Zhang X, Kunjithapatham A, Jeong S, Simon G (2011) Towards an elastic application model for augmenting the computing capabilities of mobile devices with cloud computing. J Mob Netw Appl 16(3):270–284CrossRef Zhang X, Kunjithapatham A, Jeong S, Simon G (2011) Towards an elastic application model for augmenting the computing capabilities of mobile devices with cloud computing. J Mob Netw Appl 16(3):270–284CrossRef
33.
Zurück zum Zitat Zhang Y, Huang G, Liu X, Zhang W, Mei H, Yang S (2012) Refactoring android java code for on-demand computation offloading. In: Proceedings of the ACM SIGPLAN notices, vol 47. ACM, pp 233–248 Zhang Y, Huang G, Liu X, Zhang W, Mei H, Yang S (2012) Refactoring android java code for on-demand computation offloading. In: Proceedings of the ACM SIGPLAN notices, vol 47. ACM, pp 233–248
Metadaten
Titel
Assignment and collaborative execution of tasks on transient clouds
verfasst von
Mina Guiguis
Qijun Gu
Terry Penner
Lavanya Tammineni
Thomas Langford
Agustin Rivera-Longoria
Alison Johnson
Brandon Van Slyke
Publikationsdatum
01.04.2018
Verlag
Springer International Publishing
Erschienen in
Annals of Telecommunications / Ausgabe 3-4/2018
Print ISSN: 0003-4347
Elektronische ISSN: 1958-9395
DOI
https://doi.org/10.1007/s12243-017-0601-8

Weitere Artikel der Ausgabe 3-4/2018

Annals of Telecommunications 3-4/2018 Zur Ausgabe

Neuer Inhalt