Incentive-compatible opportunistic routing for wireless networks

ABSTRACT

User-contributed wireless mesh networks are a disruptive technology that may fundamentally change the economics of edge network access and bring the benefits of a computer network infrastructure to local communities at low cost, anywhere in the world. To achieve high throughput despite highly unpredictable and lossy wireless channels, it is essential that such networks take advantage of transmission opportunities wherever they emerge. However, as opportunistic routing departs from the traditional but less effective deterministic, shortest-path based routing, user nodes in such networks may have less incentive to follow protocols and contribute. In this paper, we present the first routing protocols in which it is incentive-compatible for each user node to honestly participate in the routing despite opportunistic transmissions. We not only rigorously prove the properties of our protocols but also thoroughly evaluate a complete implementation of our protocols. Experiments show that there is a 5.8%-58.0% gain in throughput when compared with an opportunistic routing protocol that does not provide incentives and users can act selfishly.

REFERENCES

• 1: E. Adar and B. A. Huberman. Free riding on Gnutella. First Monday, 5(10), Oct. 2000.
• 2: Daniel Aguayo , John Bicket , Sanjit Biswas , Glenn Judd , Robert Morris, Link-level measurements from an 802.11b mesh network, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 3: R. Ahlswede, N. Cai, S. R. Li, and R. W. Yeung. Network information flow. IEEE Transactions on Information Theory, 46(4):1204 -- 1216, 2000.
• 4: I. F. Akyildiz and X. Wang. A survey on wireless mesh networks. IEEE Communications Magazine, 43(9), 2005.
• 5: Luzi Anderegg , Stephan Eidenbenz, Ad hoc-VCG: a truthful and cost-efficient routing protocol for mobile ad hoc networks with selfish agents, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.939011]
• 6: Sanjit Biswas , Robert Morris, ExOR: opportunistic multi-hop routing for wireless networks, Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, August 22-26, 2005, Philadelphia, Pennsylvania, USA
• 7: W. E. Bluhm. Society of Actuaries 50th Anniversary Monograph, chapter V: Cumulative Anti-Selection Theory. 1999.
• 8: S. Buchegger and J.-Y. Le Boudec. Nodes bearing grudges: Towards routing security, fairness, and robustness in mobile ad hoc networks. In Proceedings of the 10th Euromicro Workshop on Parallel, Distributed and Network-based Processing (EUROMICRO-PDP '02), Canary Islands, Spain, Jan. 2002.
• 9: Sonja Buchegger , Jean-Yves Le Boudec, Performance analysis of the CONFIDANT protocol, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513828]
• 10: Levente Buttyán , Jean-Pierre Hubaux, Enforcing service availability in mobile ad-hoc WANs, Proceedings of the 1st ACM international symposium on Mobile ad hoc networking & computing, November 20, 2000, Boston, Massachusetts
• 11: L. Buttyan and J.-P. Hubaux. Security and Cooperation in Wireless Networks. Cambridge University Press, 2007.
• 12: L. Buttyan and J. P. Hubaux. Stimulating cooperation in self-organizing mobile ad hoc networks. ACM Journal for Mobile Networks (MONET), special issue on Mobile Ad Hoc Networks, summer 2002.
• 13: Szymon Chachulski , Michael Jennings , Sachin Katti , Dina Katabi, Trading structure for randomness in wireless opportunistic routing, Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communications, August 27-31, 2007, Kyoto, Japan
• 14: Douglas S. J. De Couto , Daniel Aguayo , John Bicket , Robert Morris, A high-throughput path metric for multi-hop wireless routing, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.939000]
• 15: Ugly truth about mesh networks. http://www.dailywireless.org/2004/06/28/ugly-truth-aboutmeshnetworks.
• 16: S. Jaggi, P. Sanders, P. A. Chou, M. Effros, S. Egner, K. Jain, and L. Tolhuizen. Polynomial time algorithms for multicast network code construction. IEEE Transactions on Information Theory, 51(6):1973 -- 1982, 2005.
• 17: M. Jakobsson, J. P. Hubaux, and L. Buttyan. A micropayment scheme encouraging collaboration in multi-hop cellular networks. In Proceedings of the 7th International Conference on Financial Cryptography (FC'03), Guadeloupe, French West Indies, Jan. 2003.
• 18: Abhinav Kamra , Vishal Misra , Jon Feldman , Dan Rubenstein, Growth codes: maximizing sensor network data persistence, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy
• 19: Sachin Katti , Shyamnath Gollakota , Dina Katabi, Embracing wireless interference: analog network coding, Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communications, August 27-31, 2007, Kyoto, Japan
• 20: S. Katti, D. Katabi, W. Hu, H. S. Rahul, and M. Médard. The importance of being opportunistic: Practical network coding for wireless environments. In Proceedings of the 43rd Annual Allerton Conference on Communication, Control, and Computing, Monticello, IL, Sept. 2005.
• 21: Sachin Katti , Hariharan Rahul , Wenjun Hu , Dina Katabi , Muriel Médard , Jon Crowcroft, XORs in the air: practical wireless network coding, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy
• 22: Ralf Koetter , Muriel Médard, An algebraic approach to network coding, IEEE/ACM Transactions on Networking (TON), v.11 n.5, p.782-795, October 2003 [doi>10.1109/TNET.2003.818197]
• 23: D. Laneman and G. Wornell. Cooperative diversity in wireless networks: Efficient protocols and outage behavior. IEEE Transactions on Information Theory, 50(12):3062 -- 3080, 2004.
• 24: Jinyang Li , Charles Blake , Douglas S.J. De Couto , Hu Imm Lee , Robert Morris, Capacity of Ad Hoc wireless networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.61-69, July 2001, Rome, Italy [doi>10.1145/381677.381684]
• 25: S. R. Li, R. W. Yeung, and N. Cai. Linear network coding. IEEE Transactions on Information Theory, 49(2):371 -- 381, 2003.
• 26: D. S. Lun, N. Ratnakar, R. Koetter, M. Médard, and a. H. L. E. Ahmed. Achieving minimum-cost multicast: A decentralized approach based on network coding. In Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'05), Miami, FL, Mar. 2005.
• 27: Haiyun Luo , Ramachandran Ramjee , Prasun Sinha , Li (Erran) Li , Songwu Lu, UCAN: a unified cellular and ad-hoc network architecture, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.939021]
• 28: MadWifi Project Team. http://madwifi.org.
• 29: Sergio Marti , T. J. Giuli , Kevin Lai , Mary Baker, Mitigating routing misbehavior in mobile ad hoc networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.255-265, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345955]
• 30: Meraki Networks. http://meraki.com.
• 31: Allen Miu , Hari Balakrishnan , Can Emre Koksal, Improving loss resilience with multi-radio diversity in wireless networks, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080832]
• 32: MuniWireless LLC. http://www.muniwireless.com.
• 33: Rutgers ORBIT project team. http://www.orbit-lab.org.
• 34: Naouel Ben Salem , Levente Buttyán , Jean-Pierre Hubaux , Markus Jakobsson, A charging and rewarding scheme for packet forwarding in multi-hop cellular networks, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778418]
• 35: V. Srinivasan, P. Nuggehalli, C.-F. Chiasserini, and R. Rao. Cooperation in wireless ad hoc networks. In Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'03), San Francisco, CA, Apr. 2003.
• 36: The Click Modular Router Project Team. http://www.read.cs.ucla.edu/click/.
• 37: David Tse , Pramod Viswanath, Fundamentals of wireless communication, Cambridge University Press, New York, NY, 2005
• 38: Weizhao Wang , Stephan Eidenbenz , Yu Wang , Xiang-Yang Li, OURS: optimal unicast routing systems in non-cooperative wireless networks, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161134]
• 39: S. Zhong, J. Chen, and Y. R. Yang. Sprite, a simple, cheat-proof, credit-based system for mobile ad-hoc networks. In Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'03), San Francisco, CA, Apr. 2003.
• 40: Sheng Zhong , Li (Erran) Li , Yanbin Grace Liu , Yang (Richard) Yang, On designing incentive-compatible routing and forwarding protocols in wireless ad-hoc networks: an integrated approach using game theoretical and cryptographic techniques, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080841]
• 41: Sheng Zhong , Fan Wu, On designing collusion-resistant routing schemes for non-cooperative wireless ad hoc networks, Proceedings of the 13th annual ACM international conference on Mobile computing and networking, September 09-14, 2007, Montréal, Québec, Canada [doi>10.1145/1287853.1287887]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network communications

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network management

General Terms:
Design, Economics, Management

Keywords:
incentive, wireless