TY - CONF T1 - Backbone construction in selfish wireless networks T2 - Proceedings of the 2007 ACM SIGMETRICS international conference on Measurement and modeling of computer systems Y1 - 2007 A1 - Lee,Seungjoon A1 - Levin,Dave A1 - Gopalakrishnan,Vijay A1 - Bhattacharjee, Bobby KW - incentives KW - public good KW - selfish network KW - volunteer's dilemma KW - wireless backbone AB - 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. JA - Proceedings of the 2007 ACM SIGMETRICS international conference on Measurement and modeling of computer systems T3 - SIGMETRICS '07 PB - ACM CY - New York, NY, USA SN - 978-1-59593-639-4 UR - http://doi.acm.org/10.1145/1254882.1254896 M3 - 10.1145/1254882.1254896 ER -