Inspired by the One Laptop Per Child project, we consider mesh networks that connect devices that cannot recharge their batteries easily. We study how the mesh should retransmit information to make use of the energy stored in each of the nodes effectively. The solution that minimizes the total energy spent by the whole network may be very unfair to some nodes because they bear a disproportionate burden of the traffic. A Nash equilibrium—achieved when nodes minimize the energy they spend—does not model the situation well because, as retransmissions consume battery without increasing the node’s utility, it predicts that nodes refuse to participate. Actually, there are wireless communication protocols, peer-to-peer networks and other systems that provide incentives or impose penalties to encourage nodes to be active and to participate. We explicitly aim at the solution that minimizes the total energy spent by nodes among those that satisfy a fairness constraint. Although this does not guarantee that the solution is at equilibrium, nodes do not have a big incentive to deviate from the proposed solution since they do not view the situation as extremely unfair to them. This is consistent with the recommendation of Beccaria and Bolelli (1992) who proposed to optimize social welfare keeping user needs as constraints. We propose a distributed and online routing algorithm and compare it to an offline, centralized approach. The centralized approach, besides being unrealistic in terms of information requirements, is also NP-hard to solve. For both reasons, we focus on the former and evaluate it by conducting an extensive set of computational experiments that evaluate the efficiency and fairness achieved by our algorithm.
Citation
Forthcoming on Mathematical Programming, Series B, special issue on Combinatorial Optimization and Integer Programming (2010)