Backbone construction in selfish wireless networks

TitleBackbone construction in selfish wireless networks
Publication TypeConference Papers
Year of Publication2007
AuthorsLee S, Levin D, Gopalakrishnan V, Bhattacharjee B
Conference NameProceedings of the 2007 ACM SIGMETRICS international conference on Measurement and modeling of computer systems
Date Published2007///
Conference LocationNew York, NY, USA
ISBN Number978-1-59593-639-4
Keywordsincentives, public good, selfish network, volunteer's dilemma, wireless backbone

We present a protocol to construct routing backbones in wireless networks composed of selfish participants. Backbones are inherently cooperative, so constructing them in selfish environments is particularly difficult; participants want a backbone to exist (soothers relay their packets) but do not want to join the backbone (so they do not have to relay packets for others). We model the wireless backbone as a public good and use impatience as an incentive for cooperation. To determine if and when to donate to this public good, each participant calculates how patient it should be in obtaining the public good. We quantify patience using the Volunteer's Timing Dilemma (VTD), which we extend to general multihop network settings. Using our generalized VTD analysis, each node individually computes as its dominant strategy the amount of time to wait before joining the backbone. We evaluate our protocol using both simulations and an implementation. Our results show that, even though participants in our system deliberately wait before volunteering, a backbone is formed quickly. Further, the quality of the backbone (such as the size and resulting network lifetime) is comparable to that of existing backbone protocols that assume altruistic behavior.