More Web Proxy on the site http://driver.im/

Article

INPAC: an enforceable incentive scheme for wireless networks using network coding

Authors:

Sheng ZhongAuthors Info & Claims

INFOCOM'10: Proceedings of the 29th conference on Information communications

Pages 1828 - 1836

Published: 14 March 2010 Publication History

Abstract

Wireless mesh networks have been widely deployed to provide broadband network access, and their performance can be significantly improved by using a new technology called network coding. In a wireless mesh network using network coding, selfish nodes may deviate from the protocol when they are supposed to forward packets. This fundamental problem of packet forwarding incentives is closely related to the incentive compatible routing problem in wireless mesh networks using network coding, and to the incentive compatible packet forwarding problem in conventional wireless networks, but different from both of them. In this paper, we propose INPAC, the first incentive scheme for this fundamental problem, which uses a combination of game theoretic and cryptographic techniques to solve it. We formally prove that, if INPAC is used, then following the protocol faithfully is a subgame perfect equilibrium. To make INPAC more practical, we also provide an extension that achieves two improvements: (a) an online authority is no longer needed; (b) the computation and communication overheads are reduced. We have implemented and evaluated INPAC on the Orbit Lab testbed. Our evaluation results verify the incentive compatibility of INPAC and demonstrate that it is efficient.

References

[1]

S. Akl and P. Taylor. Cryptographic solution to a problem of access control in a hierarchy. ACM Trans. Computer Systems, 1(3):239-248, 1983.

Digital Library

[2]

I. F. Akyildiz and X. Wang. A survey on wireless mesh networks. IEEE Communications Magazine, 43(9), 2005.

Digital Library

[3]

L. Anderegg and S. Eidenbenz. Ad hoc-VCG: a truthful and cost-efficient routing protocol for mobile ad hoc networks with selfish agents. In Proceedings of ACM MOBICOM, 2003.

Digital Library

[4]

M. Bellare and P. Rogaway. Random oracles are practical: A paradigm for designing efficient protocols. In Proceedings of ACM CCS 1993, pages 62-73, 1993.

Digital Library

[5]

L. Buttyan and J. P. Hubaux. Enforcing service availability in mobile ad-hoc WANs. In Proceedings of ACM MOBIHOC, 2000.

Digital Library

[6]

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.

Digital Library

[7]

S. Chachulski, M. Jennings, S. Katti, and D. Katabi. Trading structure for randomness in wireless opportunistic routing. In Proceedings of ACM SIGCOMM, 2007.

Digital Library

[8]

S. Chen, P. Lin, D. Huang, and S. R. Yang. A study on distributed/ centralized scheduling for wireless mesh network. In Proceedings of the 2006 International Conference on Wireless Communications and Mobile Computing, pages 599-604, 2006.

Digital Library

[9]

T. Chen and S. Zhong. Inpac: An enforceable incentive scheme for wireless networks using network coding. Technical report, SUNY Buffalo, Available: http://www.cse.buffalo.edu/tech-reports/2009-04.pdf, 2009.

[10]

W. Dai. Crypto++5.5.2. Available at http://www.eskimo.com/weidai/cryptlib.html.

[11]

D. De Couto, D. Aguayo, J. Bicket, and R. Morris. A high-throughput path metric for multi-hop wireless routing. In Proceedings of ACM MOBICOM, 2003.

Digital Library

[12]

S. Jaggi, M. Langberg, S. Katti, T. Ho, D. Katabi, and M. Medard. Resilient network coding in the presence of byzantine adversaries. In Proceedings of IEEE INFOCOM, 2007.

Digital Library

[13]

M. Jakobsson, J. P. Hubaux, and L. Buttyan. A micropayment scheme encouraging collaboration in multi-hop cellular networks. In Proceedings of Financial Crypto 2003, La Guadeloupe, Jan. 2003.

[14]

J. J. Jaramillo and R. Srikant. Darwin: Distributed and adaptive reputation mechanism for wireless ad-hoc networks. In Proceedings of ACM MOBICOM, 2007.

Digital Library

[15]

S. Katti, S. Gollakota, and D. Katabi. Embracing wireless interference: Analog network coding. In Proceedings of ACM SIGCOMM, 2007.

Digital Library

[16]

S. Katti, D. Katabi, H. Balakrishnan, and M. Medard. Symbol-level network coding for wireless mesh networks. In Proceedings of ACM SIGCOMM, 2008.

Digital Library

[17]

S. Katti, H. Rahul, W. Hu, D. Katabi, M. Medard, and J. Crowcroft. XORs in the air: Practical wireless network coding. In Proceedings of ACM SIGCOMM '06, Pisa, Italy, Sept. 2006.

Digital Library

[18]

X.-Y. Li, Y. Wu, P. Xu, G. Chen, and M. Li. Hidden information and actions in multi-hop wireless ad hoc networks. In Proceedings of ACM MOBIHOC, 2008.

Digital Library

[19]

http://madwifi.org.

[20]

S. Marti, T. Giuli, K. Lai, and M. Baker. Mitigating routing misbehavior in mobile ad hoc networks. In Proceedings of ACM MOBICOM, 2000.

Digital Library

[21]

Meraki Networks. http://meraki.com.

[22]

MuniWireless LLC. http://www.muniwireless.com.

[23]

M. J. Osborne and A. Rubenstein. A Course in Game Theory. The MIT Press, 1994.

[24]

Rutgers ORBIT project team. http://www.orbit-lab.org.

[25]

N. B. Salem, L. Buttyan, J. P. Hubaux, and M. Jakobsson. A charging and rewarding scheme for packet forwarding in multi-hop cellular networks. In Proceedings of ACM MOBIHOC, 2003.

Digital Library

[26]

http://www.read.cs.ucla.edu/click/.

[27]

W. Wan, X.-Y. Li, and Y. Wang. Truthful multicast in selfish wireless networks. In Proceedings of ACM MOBICOM, 2004.

Digital Library

[28]

W. Wang, S. Eidenbez, Y. Wang, and X.-Y. Li. OURS-optimal unicast routing systems in non-cooperative wireless networks multihop routing in sensor networks. In Proceedings of ACM MOBICOM.

Digital Library

[29]

F. Wu, T. Chen, S. Zhong, L. E. Li, and Y. R. Yang. Incentive compatible opportunistic routing for wireless networks. In Proceedings of ACM MOBICOM, 2008.

Digital Library

[30]

Z. Yu, Y. Wei, B. Ramkumar, and Y. Guan. An efficient signature-based scheme for securing network coding against pollution attacks. In Proceedings of IEEE INFOCOM, 2008.

[31]

S. Zhong, J. Chen, and Y. R. Yang. Sprite, a simple, cheat-proof, credit-based system for mobile ad-hoc networks. In Proceedings of IEEE INFOCOM '03, San Francisco, CA, Apr. 2003.

[32]

S. Zhong, L. Li, Y. Liu, and Y. R. Yang. On designing incentive-compatible routing and forwarding protocols in wireless ad-hoc networks -- an integrated approach using game theoretical and cryptographic techniques. In Proceedings of ACM MOBICOM, 2005.

Digital Library

[33]

S. Zhong and F. Wu. On designing collusion-resistant routing schemes for non-cooperative wireless ad hoc networks. In Proceedings of ACM MOBICOM, 2007.

Digital Library

Cited By

Nguyen TBrun OPrabhu B(2019)Performance of a Fixed Reward Incentive Scheme for Two-hop DTNs with Competing RelaysACM Transactions on Modeling and Performance Evaluation of Computing Systems10.1145/33252884:2(1-19)Online publication date: 13-Jun-2019
https://dl.acm.org/doi/10.1145/3325288
Liu HLee PLui J(2013)On the credit evolution of credit-based incentive protocols in wireless mesh networksComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2013.07.02157:17(3327-3343)Online publication date: 1-Dec-2013
https://dl.acm.org/doi/10.1016/j.comnet.2013.07.021
Sadiq UKumar MWright MZomaya ALandfeldt BPrakash R(2012)CRISPProceedings of the 15th ACM international conference on Modeling, analysis and simulation of wireless and mobile systems10.1145/2387238.2387253(69-78)Online publication date: 21-Oct-2012
https://dl.acm.org/doi/10.1145/2387238.2387253
Show More Cited By

INPAC: an enforceable incentive scheme for wireless networks using network coding
1. Networks
  1. Network types

Recommendations

INPAC: INdependent PAss Coding algorithm for robust image data transmission through low SNR channels

A new strategy of data representation called INdependent PAss Coding (INPAC) is proposed in this paper for robust and reliable transmission of embedded zero wavelet (EZW) bit stream through noisy channels. Error handling capacity of the EZW is improved ...
Implications of a Reserve Price in an Agent-Based Common-Value Auction

Auction sellers can use a reserve price to require a minimum bid before items are sold. Theoretical and experimental research has tested the influence of a reserve price in an independent private values auction, but little focus has been given to the ...
Sequential auctions and externalities
SODA '12: Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete algorithms

In many settings agents participate in multiple different auctions that are not necessarily implemented simultaneously. Future opportunities affect strategic considerations of the players in each auction, introducing externalities. Motivated by this ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

INFOCOM'10: Proceedings of the 29th conference on Information communications

March 2010

2990 pages

ISBN:9781424458363

Publisher

IEEE Press

Publication History

Published: 14 March 2010

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Nguyen TBrun OPrabhu B(2019)Performance of a Fixed Reward Incentive Scheme for Two-hop DTNs with Competing RelaysACM Transactions on Modeling and Performance Evaluation of Computing Systems10.1145/33252884:2(1-19)Online publication date: 13-Jun-2019
https://dl.acm.org/doi/10.1145/3325288
Liu HLee PLui J(2013)On the credit evolution of credit-based incentive protocols in wireless mesh networksComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2013.07.02157:17(3327-3343)Online publication date: 1-Dec-2013
https://dl.acm.org/doi/10.1016/j.comnet.2013.07.021
Sadiq UKumar MWright MZomaya ALandfeldt BPrakash R(2012)CRISPProceedings of the 15th ACM international conference on Modeling, analysis and simulation of wireless and mobile systems10.1145/2387238.2387253(69-78)Online publication date: 21-Oct-2012
https://dl.acm.org/doi/10.1145/2387238.2387253
Xu YSakurai KLee SHanzo LIsmail RKim DChung MLee S(2012)Cooperatively securing network coding against pollution attacks with incentive mechanismProceedings of the 6th International Conference on Ubiquitous Information Management and Communication10.1145/2184751.2184815(1-10)Online publication date: 20-Feb-2012
https://dl.acm.org/doi/10.1145/2184751.2184815
Zhao HYang XLi X(2012)An incentive mechanism to reinforce truthful reports in reputation systemsJournal of Network and Computer Applications10.1016/j.jnca.2011.03.01135:3(951-961)Online publication date: 1-May-2012
https://dl.acm.org/doi/10.1016/j.jnca.2011.03.011
Yao HZhong S(2011)Towards cheat-proof cooperative relay for cognitive radio networksProceedings of the Twelfth ACM International Symposium on Mobile Ad Hoc Networking and Computing10.1145/2107502.2107523(1-11)Online publication date: 17-May-2011
https://dl.acm.org/doi/10.1145/2107502.2107523

View Options

View options

Media

Figures

Other

Tables

View Table of Contents