research-article

Sharing the Cost of Lunch: Energy Apportionment Policies

Authors:

Ekhiotz Jon Vergara,

Simin Nadjm-Tehrani,

Mikael AsplundAuthors Info & Claims

Q2SWinet '15: Proceedings of the 11th ACM Symposium on QoS and Security for Wireless and Mobile Networks

Pages 91 - 97

https://doi.org/10.1145/2815317.2815338

Published: 02 November 2015 Publication History

Abstract

Energy consumption has become a hot topic in computer and communication technologies pinpointing the need to carefully analyse system efficiency. The energy consumption of a system is determined by the usage patterns of system components and complex interactions between the coexisting entities and resources. Providing transparency of a system's consumption by breaking down the total consumption is vital to evaluate and provide energy-efficient design and operation.

In this paper we survey the apportionment problem in different fields such as computer systems, wireless sensor networks, mobile devices and energy-efficient buildings. The challenge lies in how to attribute a share of the total energy consumption to the responsible entities (e.g., applications, processes or users of the system). Our analysis identifies that energy apportionment is a common problem in different fields and reviews five previously applied energy apportionment policies. Also, the work identifies relevant further research.

References

[1]

M. Alam, S. D. Ramchurn, and A. Rogers. Cooperative energy exchange for the efficient use of energy and resources in remote communities. In Proceedings of the 2013 International Conference on Autonomous Agents and Multi-agent Systems, AAMAS '13, pages 731--738, Richland, SC, 2013. International Foundation for Autonomous Agents and Multiagent Systems.

Digital Library

[2]

K. Athukorala, E. Lagerspetz, M. von Kügelgen, A. Jylhä, A. J. Oliner, S. Tarkoma, and G. Jacucci. How carat affects user behavior: Implications for mobile battery awareness applications. In Proceedings of the 32Nd Annual ACM Conference on Human Factors in Computing Systems, CHI '14, pages 1029--1038, New York, NY, USA, 2014. ACM.

Digital Library

[3]

N. Balasubramanian, A. Balasubramanian, and A. Venkataramani. Energy consumption in mobile phones: A measurement study and implications for network applications. In Proceedings of the 9th ACM SIGCOMM Conference on Internet Measurement Conference, IMC '09, pages 280--293, New York, NY, USA, 2009. ACM.

Digital Library

[4]

R. Bertran, Y. Becerra, D. Carrera, V. Beltran, M. Gonzalez Tallada, X. Martorell, J. Torres, and E. Ayguade. Accurate energy accounting for shared virtualized environments using pmc-based power modeling techniques. In Grid Computing (GRID), 2010 11th IEEE/ACM International Conference on, pages 1--8, Oct 2010.

[5]

J. Castro, D. Gómez, and J. Tejada. Polynomial calculation of the shapley value based on sampling. Comput. Oper. Res., 36(5):1726--1730, May 2009.

Digital Library

[6]

Y. Cheng, K. Chen, B. Zhang, C.-J. M. Liang, X. Jiang, and F. Zhao. Accurate real-time occupant energy-footprinting in commercial buildings. In Proceedings of the Fourth ACM Workshop on Embedded Sensing Systems for Energy-Efficiency in Buildings, BuildSys '12, pages 115--122, New York, NY, USA, 2012. ACM.

Digital Library

[7]

S. Darby. The effectiveness of feedback on energy consumption: a review for DEFRA of the literature on metering, billing and direct displays. Technical report, Environmental Change Institute, University of Oxford, 2006.

[8]

X. Deng and C. H. Papadimitriou. On the complexity of cooperative solution concepts. Math. Oper. Res., 19(2):257--266, May 1994.

Digital Library

[9]

M. Dong, T. Lan, and L. Zhong. Rethink energy accounting with cooperative game theory. In Proceedings of the 20th Annual International Conference on Mobile Computing and Networking, MobiCom '14, pages 531--542, New York, NY, USA, 2014. ACM.

Digital Library

[10]

J. Drechsel. Selected topics in cooperative game theory. In Cooperative Lot Sizing Games in Supply Chains, volume 644 of Lecture Notes in Economics and Mathematical Systems, pages 5--39. Springer Berlin Heidelberg, 2010.

[11]

J. Drechsel and A. Kimms. Computing core allocations in cooperative games with an application to cooperative procurement. International Journal of Production Economics, 128(1):310 -- 321, 2010. Integrating the Global Supply Chain.

[12]

U. Faigle, W. Kern, and J. Kuipers. Computing the nucleolus of min-cost spanning tree games is np-hard. Int. J. Game Theory, 27(3):443--450, Dec. 1998.

Digital Library

[13]

S. S. Fatima, M. Wooldridge, and N. R. Jennings. A linear approximation method for the shapley value. Artif. Intell., 172(14):1673--1699, Sept. 2008.

Digital Library

[14]

M. Fiestras-Janeiro, I. García-Jurado, and M. Mosquera. Cooperative games and cost allocation problems. TOP, 19(1):1--22, 2011.

[15]

J. Flinn and M. Satyanarayanan. Powerscope: A tool for profiling the energy usage of mobile applications. In Proceedings of the Second IEEE Workshop on Mobile Computer Systems and Applications, WMCSA '99, pages 2--, Washington, DC, USA, 1999. IEEE Computer Society.

Digital Library

[16]

B. Fromen. Reducing the number of linear programs needed for solving the nucleolus problem of n-person game theory. European Journal of Operational Research, 98(3):626 -- 636, 1997.

[17]

J. González-Díaz and E. Sánchez-Rodríguez. Understanding the coincidence of allocation rules: symmetry and orthogonality in tu-games. International Journal of Game Theory, 43(4):821--843, 2014.

[18]

S. Guiasu. Three ancient problems solved by using the game theory logic based on the shapley value. Synthese, 181(1):65--79, 2011.

[19]

J. C. Harsanyi and R. Selten. A general theory of equilibrium selection in games. cambridge, ma: The MIT Press, 1988, 378pp. Behavioral Science, 34(2):154--158, 1989.

[20]

S. Hay and A. Rice. The case for apportionment. In Proceedings of the First ACM Workshop on Embedded Sensing Systems for Energy-Efficiency in Buildings, BuildSys '09, pages 13--18, New York, NY, USA, 2009. ACM.

Digital Library

[21]

S. Kellner. Flexible online energy accounting in tinyos. In P. Marron, T. Voigt, P. Corke, and L. Mottola, editors, Proceedings of the 4th International Workshop on Real-World Wireless Sensor Networks (RealWSN'10), volume 6511 of Lecture Notes in Computer Science, pages 62--73. Springer Berlin / Heidelberg, Dec. 2010.

Digital Library

[22]

E. A. Lee. Modeling concurrent real-time processes using discrete events. Ann. Softw. Eng., 7(1--4):25--45, June 1999.

Digital Library

[23]

J. Lemaire. An application of game theory: Cost allocation. ASTIN Bulletin, 14:61--81, 4 1984.

[24]

R. T. B. Ma, V. Misra, D. ming Chiu, D. Rubenstein, and J. C. S. Lui. Internet economics: The use of shapley value for isp settlement. In Proceedings of 2007 ACM Conference on Emerging network experiment and technology (CoNEXT), 2007.

Digital Library

[25]

M. Maschler, B. Peleg, and L. S. Shapley. Geometric properties of the kernel, nucleolus, and related solution concepts. Mathematics of Operations Research, 4(4):303--338, 1979.

Digital Library

[26]

M. Maschler, J. Potters, and S. Tijs. The general nucleolus and the reduced game property. International Journal of Game Theory, 21(1):85--106, 1992.

Digital Library

[27]

S. Masuya and M. Inuiguchi. Toward the theory of cooperative games under incomplete information. In Proceedings of the 6th International Conference on Modeling Decisions for Artificial Intelligence, MDAI '09, pages 102--113, Berlin, Heidelberg, 2009. Springer-Verlag.

Digital Library

[28]

N. Megiddo. Computational complexity of the game theory approach to cost allocation for a tree. Mathematics of Operations Research, 3(3):189--196, 1978.

Digital Library

[29]

V. Misra, S. Ioannidis, A. Chaintreau, and L. Massoulié. Incentivizing peer-assisted services: A fluid shapley value approach. In Proceedings of the ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS '10, pages 215--226, New York, NY, USA, 2010. ACM.

Digital Library

[30]

R. Mittal, A. Kansal, and R. Chandra. Empowering developers to estimate app energy consumption. In Proceedings of the 18th Annual International Conference on Mobile Computing and Networking, Mobicom '12, pages 317--328, New York, NY, USA, 2012. ACM.

Digital Library

[31]

E. Molina and J. Tejada. The least square nucleolus is a general nucleolus. International Journal of Game Theory, 29(1):139--142, 2000.

[32]

S. Moretti and F. Patrone. Transversality of the shapley value. TOP, 16(1):1--41, 2008.

[33]

R. Neugebauer and D. McAuley. Energy is just another resource: Energy accounting and energy pricing in the nemesis os. In Proceedings of the Eighth Workshop on Hot Topics in Operating Systems, HOTOS '01, pages 67--, Washington, DC, USA, 2001. IEEE Computer Society.

Digital Library

[34]

O. Ö. Özener and O. Ergun. Allocating costs in a collaborative transportation procurement network. Transportation Science, 42(2):146--165, May 2008.

Digital Library

[35]

A. Papathanasiou and M. Scott. Energy efficiency through burstiness. In Mobile Computing Systems and Applications, 2003. Proceedings. Fifth IEEE Workshop on, pages 44--53, Oct 2003.

[36]

A. Pathak, Y. C. Hu, and M. Zhang. Where is the energy spent inside my app?: Fine grained energy accounting on smartphones with eprof. In Proceedings of the 7th ACM European Conference on Computer Systems, EuroSys '12, pages 29--42, New York, NY, USA, 2012. ACM.

Digital Library

[37]

J. E. Petersen, V. Shunturov, K. Janda, G. Platt, and K. Weinberger. Dormitory residents reduce electricity consumption when exposed to real-time visual feedback and incentives. International Journal of Sustainability in Higher Education, 8:16--33, 2007.

[38]

L. Polkowski and B. Araszkiewicz. A rough set approach to estimating the game value and the shapley value from data. Electronic Notes in Theoretical Computer Science, 82(4):219 -- 227, 2003. International Workshop on Rough Sets in Knowledge Discovery and Soft Computing (Satellite Event for ETAPS 2003).

[39]

J. Puerto and F. Perea. Finding the nucleolus of any n-person cooperative game by a single linear program. Computers and Operations Research, 40(10):2308 -- 2313, 2013.

[40]

A. Reinhardt, P. Baumann, D. Burgstahler, M. Hollick, H. Chonov, M. Werner, and R. Steinmetz. On the accuracy of appliance identification based on distributed load metering data. In Sustainable Internet and ICT for Sustainability (SustainIT), 2012, pages 1--9, Oct 2012.

[41]

A. P. Rosenbusch. Fairness Considerations in Cooperative Games. PhD thesis, TU Darmstadt / Mathematik, May 2011.

[42]

A. Roy, S. M. Rumble, R. Stutsman, P. Levis, D. Mazières, and N. Zeldovich. Energy management in mobile devices with the cinder operating system. In Proceedings of the Sixth Conference on Computer Systems, EuroSys '11, pages 139--152, New York, NY, USA, 2011. ACM.

Digital Library

[43]

L. M. Ruiz, F. Valenciano, and J. M. Zarzuelo. The Least Square Prenucleolus and the Least Square Nucleolus. Two values for TU Games based on the excess vector. International Journal of Game theory, 25:113--134, 1996.

[44]

S. Ryffel. LEA2P the linux energy attribution and accounting platform. Master's thesis, Swiss Federal Institute of Technology, Master thesis, 2009.

[45]

S. Ryffel, T. Stathopoulos, D. McIntire, W. Kaiser, and L. Thiele. Accurate energy attribution and accounting for multi-core systems. Technical report, Center for Embedded Network Sensing, University of California, Los Angeles, September 2009.

[46]

M. Saha, S. Thakur, A. Singh, and Y. Agarwal. Energylens: Combining smartphones with electricity meter for accurate activity detection and user annotation. In Proceedings of the 5th International Conference on Future Energy Systems, e-Energy '14, pages 289--300, New York, NY, USA, 2014. ACM.

Digital Library

[47]

M. Sakawa and I. Nishizaki. A lexicographical solution concept in an n-person cooperative fuzzy game. Fuzzy Sets Syst., 61(3):265--275, Feb. 1994.

Digital Library

[48]

D. Schmeidler. The nucleolus of a characteristic function game. SIAM Journal of Applied Mathematics, pages 1163--1170, 1969.

[49]

M. Sereno. Cooperative game theory framework for energy efficient policies in wireless networks. In Proceedings of the 3rd International Conference on Future Energy Systems: Where Energy, Computing and Communication Meet, e-Energy '12, pages 17:1--17:9, New York, NY, USA, 2012. ACM.

Digital Library

[50]

L. S. Shapley. A value for n-person games. Contributions to the theory of games, 2:307--317, 1953.

[51]

A. Sieber and J. Nolte. Online device-level energy accounting for wireless sensor nodes. In Proceedings of the 10th European Conference on Wireless Sensor Networks, EWSN'13, pages 149--164, Berlin, Heidelberg, 2013. Springer-Verlag.

Digital Library

[52]

S. Thakur, M. Saha, A. Singh, and Y. Agarwal. Wattshare: Detailed energy apportionment in shared living spaces within commercial buildings. In Proceedings of the 1st ACM Conference on Embedded Systems for Energy-Efficient Buildings, BuildSys '14, pages 30--39, New York, NY, USA, 2014. ACM.

Digital Library

[53]

Y.-t. Tsao, C.-C. Huang, and J. Y.-j. Hsu. Demand-based apportionment on electricity payment of hvac systems. In Proceedings of the 2014 International Conference on Autonomous Agents and Multi-agent Systems, AAMAS '14, pages 1601--1602, Richland, SC, 2014. International Foundation for Autonomous Agents and Multiagent Systems.

Digital Library

[54]

E. J. Vergara, S. Nadjm-Tehrani, and M. Prihodko. Energybox: Disclosing the wireless transmission energy cost for mobile devices. Sustainable Computing: Informatics and Systems, 4(2):118 -- 135, 2014.

[55]

S. J. Willson. A value for partially defined cooperative games. International Journal of Game Theory, 21(4):371--384, 1993.

[56]

H. Zeng, C. S. Ellis, A. R. Lebeck, and A. Vahdat. Ecosystem: Managing energy as a first class operating system resource. SIGOPS Oper. Syst. Rev., 36(5):123--132, Oct. 2002.

Digital Library

[57]

L. Zhong and N. K. Jha. Graphical user interface energy characterization for handheld computers. In Proceedings of the 2003 International Conference on Compilers, Architecture and Synthesis for Embedded Systems, CASES '03, pages 232--242, New York, NY, USA, 2003. ACM.

Digital Library

Cited By

Sharma PFuerst A(2024)Accountable Carbon Footprints and Energy Profiling For Serverless FunctionsProceedings of the 2024 ACM Symposium on Cloud Computing10.1145/3698038.3698531(522-541)Online publication date: 20-Nov-2024
https://dl.acm.org/doi/10.1145/3698038.3698531
Alsughayyir AErlebach T(2017)A Bi-objective Scheduling Approach for Energy Optimisation of Executing and Transmitting HPC Applications in Decentralised Multi-cloud Systems2017 16th International Symposium on Parallel and Distributed Computing (ISPDC)10.1109/ISPDC.2017.27(44-53)Online publication date: Jul-2017
https://doi.org/10.1109/ISPDC.2017.27
Jee JDas APathak PMohapatra P(2016)MotionSyncProceedings of the 3rd ACM International Conference on Systems for Energy-Efficient Built Environments10.1145/2993422.2993572(65-74)Online publication date: 16-Nov-2016
https://dl.acm.org/doi/10.1145/2993422.2993572

Index Terms

Sharing the Cost of Lunch: Energy Apportionment Policies
1. Computing methodologies
  1. Modeling and simulation
    1. Model development and analysis
      1. Modeling methodologies

Recommendations

Rethink energy accounting with cooperative game theory
MobiCom '14: Proceedings of the 20th annual international conference on Mobile computing and networking

Energy accounting determines how much a software principal contributes to the total system energy consumption. It is the foundation for evaluating software and for operating system based energy management. While various energy accounting policies have ...
Fairness and Incentive Considerations in Energy Apportionment Policies

The energy consumption of a system is determined by the system component usage patterns and interactions between the coexisting entities and resources. Energy accounting plays an essential role in revealing the contribution of each entity to the total ...
Low-Cost Hardware Infrastructure for Runtime Thread Level Energy Accounting
Proceedings of the 29th International Conference on Architecture of Computing Systems -- ARCS 2016 - Volume 9637

The ever-growing need for energy efficient computation requires adequate support for energy-aware thread scheduling that offers insight into a systems behavior for improved application energy/performance optimizations. Runtime accurate monitoring of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

Q2SWinet '15: Proceedings of the 11th ACM Symposium on QoS and Security for Wireless and Mobile Networks

November 2015

184 pages

ISBN:9781450337571

DOI:10.1145/2815317

General Chair:
Peter Mueller
IBM Zurich Research Laboratory, Switzerland
,
Program Chairs:
Luca Foschini
University of Bologna, Italy
,
Richard Yu
Carleton University, Ottawa -- Canada
,
Graciela Román Alonso
Universidad Autónoma Metropolitana, Mexico

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGSIM: ACM Special Interest Group on Simulation and Modeling

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 November 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

MSWiM'15

Sponsor:

SIGSIM

MSWiM'15: 18th ACM International Conference on Modeling, Analysis and Simulation of Wireless and Mobile Systems

November 2 - 6, 2015

Cancun, Mexico

Acceptance Rates

Overall Acceptance Rate 46 of 131 submissions, 35%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
134
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Sharma PFuerst A(2024)Accountable Carbon Footprints and Energy Profiling For Serverless FunctionsProceedings of the 2024 ACM Symposium on Cloud Computing10.1145/3698038.3698531(522-541)Online publication date: 20-Nov-2024
https://dl.acm.org/doi/10.1145/3698038.3698531
Alsughayyir AErlebach T(2017)A Bi-objective Scheduling Approach for Energy Optimisation of Executing and Transmitting HPC Applications in Decentralised Multi-cloud Systems2017 16th International Symposium on Parallel and Distributed Computing (ISPDC)10.1109/ISPDC.2017.27(44-53)Online publication date: Jul-2017
https://doi.org/10.1109/ISPDC.2017.27
Jee JDas APathak PMohapatra P(2016)MotionSyncProceedings of the 3rd ACM International Conference on Systems for Energy-Efficient Built Environments10.1145/2993422.2993572(65-74)Online publication date: 16-Nov-2016
https://dl.acm.org/doi/10.1145/2993422.2993572

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents