article

A collusion-resistant routing scheme for noncooperative wireless ad hoc networks

Authors:

Fan WuAuthors Info & Claims

IEEE/ACM Transactions on Networking (TON), Volume 18, Issue 2

Pages 582 - 595

https://doi.org/10.1109/TNET.2009.2030325

Published: 01 April 2010 Publication History

Abstract

In wireless ad hoc networks, routing needs cooperation of nodes. Since nodes often belong to different users, it is highly important to provide incentives for them to cooperate. However, most existing studies of the incentive-compatible routing problem focus on individual nodes' incentives, assuming that no subset of them would collude. Clearly, this assumption is not always valid. In this paper, we present a systematic study of collusion-resistant routing in noncooperative wireless ad hoc networks. In particular, we consider two standard solution concepts for collusion resistance in game theory, namely Group Strategyproofness and Strong Nash Equilibrium. We show that achieving Group Strategyproofness is impossible, while achieving Strong Nash Equilibrium is possible. More specifically, we design a scheme that is guaranteed to converge to a Strong Nash Equilibrium and prove that the total payment needed is bounded. In addition, we propose a cryptographic method that prevents profit transfer among colluding nodes, as long as they do not fully trust each other unconditionally. This method makes our scheme widely applicable in practice. Experiments show that our solution is collusion-resistant and has good performance.

References

[1]

A. Akella, S. Seshan, R. Karp, and S. Shenker, "Selfish behavior and stability of the Internet: Game-theoretic analysis of TCP," in Proc. SIGCOMM, Pittsburgh, PA, Aug. 2002, pp. 117-130.

Digital Library

[2]

L. Anderegg and S. Eidenbenz, "Ad hoc-VCG: A truthful and cost-efficient routing protocol for mobile ad hoc networks with selfish agents," in Proc. MobiCom, San Diego, CA, Sep. 2003, pp. 245-259.

Digital Library

[3]

N. Ben Salem, L. Buttyan, J. P. Hubaux, and M. Jakobsson, "A charging and rewarding scheme for packet forwarding in multi-hop cellular networks," in Proc. MobiHoc, Annapolis, MD, Jun. 2003, pp. 13-24.

Digital Library

[4]

S. Buchegger and J.-Y. Le Boudec, "Nodes bearing grudges: Towards routing security, fairness, and robustness in mobile ad hoc networks," in Proc. EUROMICRO-PDP, Canary Islands, Spain, Jan. 2002, pp. 403-410.

Digital Library

[5]

S. Buchegger and J.-Y. Le Boudec, "Performance analysis of the CONFIDANT protocol (Cooperation of nodes: fairness in dynamic ad-hoc networks)," in Proc. MobiHoc, Lausanne, Switzerland, Jun. 2002, pp. 226-236.

Digital Library

[6]

L. Buttyan and J. P. Hubaux, "Enforcing service availability in mobile ad-hocWANs," in Proc. MobiHoc, Boston, MA, Aug. 2000, pp. 87-96.

Digital Library

[7]

L. Buttyan and J. P. Hubaux, "Stimulating cooperation in self-organizing mobile ad hoc networks," ACM J. Mobile Netw., vol. 8, no. 5, pp. 579-592, 2003, Special Issue on Mobile Ad Hoc Networks.

Digital Library

[8]

D. Couto, D. Aguayo, J. Bicket, and R. Morris, "A high-throughput path metric for multi-hop wireless routing," in Proc. MobiCom, San Diego, CA, Sep. 2003, pp. 134-146.

Digital Library

[9]

S. Eidenbenz, V. S. A. Kumar, and S. Zust, "Equilibria in topology control games for ad hoc networks," in Proc. Joint Workshop Found. Mobile Comput., 2003, pp. 2-11.

Digital Library

[10]

S. Eidenbenz, G. Resta, and P. Santi, "Commit: A sender-centric truthful and energy-efficient routing protocol for ad hoc networks with selfish nodes," presented at the IEEE IPDPS, Apr. 2005.

Digital Library

[11]

L. Feeney and M. Nilsson, "Investigating the energy consumption of a wireless network interface in an ad hoc networking environment," in Proc. IEEE INFOCOM, Anchorage, AK, Apr. 22-26, 2001, vol. 3, pp. 1548-1557.

[12]

J. Feigenbaum, C. Papadimitriou, R. Sami, and S. Shenker, "A BGP-based mechanism for lowest-cost routing," in Proc. 21st Symp. Principles Distrib. Comput., Monterey, CA, Jul. 2002, pp. 173-182.

Digital Library

[13]

J. Feigenbaum and S. Shenker, "Distributed algorithmic mechanism design: Recent results and future directions," in Proc. DIAL-M, Sep. 2002, pp. 1-13.

Digital Library

[14]

M. Felegyhazi and J.-P. Hubaux, "Wireless operators in a shared spectrum," in Proc. IEEE INFOCOM, Barcelona, Spain, Apr. 2006, pp. 1-11.

[15]

O. Goldreich, Foundations of Cryptography. Cambridge, U.K.: Cambridge Univ. Press, 2001, vol. 1, Basic Tools.

Digital Library

[16]

K. Jain and V. V. Vazirani, "Group strategyproofness and no subsidy via lp-duality," 1999.

[17]

M. Jakobsson, J. P. Hubaux, and L. Buttyan, "A micropayment scheme encouraging collaboration in multi-hop cellular networks," in Proc. Financial Crypto, 2003, vol. 2742, pp. 15-33.

[18]

M. Jakobsson, K. Sako, and R. Impagliazzo, "Designated verifier proofs and their applications," in Advances in Cryptology--Eurocrypt '96, Berlin, Germany, 1996, vol. 1070, pp. 143-154.

Digital Library

[19]

J. Jaramillo and R. Srikant, "DARWIN: Distributed and adaptive reputation mechanism for wireless ad-hoc networks," in Proc. MobiCom, Montreal, QC, Canada, Sep. 2007, pp. 87-98.

Digital Library

[20]

H. Lin, M. Chatterjee, S. K. Das, and K. Basu, "ARC: An integrated admission and rate control framework for CDMA data networks based on non-cooperative games," in Proc. MobiCom, San Diego, CA, Sep. 2003, pp. 326-338.

Digital Library

[21]

S. Lindsey, K. Sivalingam, and C. Raghavendra, "Power optimization in routing protocols for wireless and mobile networks," in Handbook of Wireless Networks and Mobile Computing. New York: Wiley, 2002, pp. 407-423.

Digital Library

[22]

S. Marti, T. Giuli, K. Lai, and M. Baker, "Mitigating routing misbehavior in mobile ad hoc networks," in Proc. MobiCom, Boston, MA, Aug. 2000, pp. 255-265.

Digital Library

[23]

A. Mas-Colell, M. D. Whinston, and J. R. Green, Microeconomic Theory. Oxford, U.K.: Oxford Univ. Press, 1995.

[24]

S. Mathur, L. Sankaranarayanan, and N. Mandayam, "Coalitional games in receiver cooperation for spectrum sharing," in Proc. CISS, Princeton, NJ, Mar. 2006, pp. 949-954.

[25]

S. Mathur, L. Sankaranarayanan, and N. Mandayam, "Coalitional games in Gaussian interference channels," in Proc. ISIT, Seattle, WA, Jun. 2006, pp. 2210-2214.

[26]

H. Moulin and S. Shenker, "Strategyproof sharing of submodular costs: Budget balance versus efficiency," J. Econ. Theory, vol. 18, no. 3, pp. 511-533, 2001.

[27]

N. Nisan and A. Ronen, "Algorithmic mechanism design," Games Econ. Behavior, vol. 35, pp. 166-196, 2001.

[28]

C. Papadimitriou, "Algorithms, games, and the Internet," in Proc. 33rd Annu. Symp. Theory Comput., Heraklion, Crete, Greece, Jul. 2001, pp. 749-753.

Digital Library

[29]

C. Schnorr, "Efficient signature generation for smart cards," in Advances in Cryptology--CRYPTO '89. New York: Springer-Verlag, 1990, pp. 239-252.

Digital Library

[30]

V. Srinivasan, P. Nuggehalli, C.-F. Chiasserini, and R. Rao, "Cooperation in wireless ad hoc networks," in Proc. IEEE INFOCOM, San Francisco, CA, Apr. 2003, vol. 2, pp. 808-817.

[31]

H. Varian, "Economic mechanism design for computerized agents," in Proc. USENIX Workshop Electron. Commerce, 1995, vol. 1, p. 2.

Digital Library

[32]

W. Wang, S. Eidenbez, Y. Wang, and X.-Y. Li, "OURS: Optimal unicast routing systems in non-cooperative wireless networks," in Proc. MobiCom, Los Angeles, CA, Sep. 2006, pp. 402-413.

Digital Library

[33]

W. Wang and X.-Y. Li, "Low-cost routing in selfish and rational wireless ad hoc networks," IEEE Trans. Mobile Comput., vol. 5, no. 5, pp. 596-607, May 2006.

Digital Library

[34]

W. Wang, Li X.-Y, and Y. Wang, "Truthful multicast routing in selfish wireless networks," in Proc. MobiCom, New York, Sep. 2004, pp. 245-259.

Digital Library

[35]

J. Zhao and R. Govindan, "Understanding packet delivery performance in dense wireless sensor networks," in Proc. SenSys, Los Angeles, CA, Nov. 5-7, 2003, pp. 1-13.

Digital Library

[36]

S. Zhong, J. Chen, and Y. R. Yang, "Sprite, a simple, cheat-proof, credit-based system for mobile ad-hoc networks," in Proc. IEEE INFOCOM, San Francisco, CA, Apr. 2003, vol. 3, pp. 1987-1997.

[37]

S. Zhong, L. E. Li, Y. G. 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 Proc. MobiCom, Cologne, Germany, Sep. 2005, pp. 117-131.

Digital Library

Cited By

Reddy MBabu M(2019)Implementing self adaptiveness in whale optimization for cluster head section in Internet of ThingsCluster Computing10.1007/s10586-017-1628-322:1(1361-1372)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1007/s10586-017-1628-3
Maddikunta PMadda R(2017)Energy Aware Cluster Head Selection for Maximizing Lifetime Improvement in Internet of ThingsInternational Journal of Grid and High Performance Computing10.4018/IJGHPC.20171001059:4(71-91)Online publication date: 1-Oct-2017
https://dl.acm.org/doi/10.4018/IJGHPC.2017100105
Liao HDing S(2015)Mixed and continuous strategy Monitor-Forward game based selective forwarding solution in WSNInternational Journal of Distributed Sensor Networks10.1155/2015/3597802015(7-7)Online publication date: 1-Jan-2015
https://dl.acm.org/doi/10.1155/2015/359780
Show More Cited By

Index Terms

A collusion-resistant routing scheme for noncooperative wireless ad hoc networks

Recommendations

On designing collusion-resistant routing schemes for non-cooperative wireless ad hoc networks
MobiCom '07: Proceedings of the 13th annual ACM international conference on Mobile computing and networking

In wireless ad hoc networks, routing requires cooperation of nodes. Since nodes often belong to different users, it is highly important to provide incentives for them to cooperate. However, most existing studies of the incentive-compatible routing ...
Routing with load balancing in wireless Ad hoc networks
MSWIM '01: Proceedings of the 4th ACM international workshop on Modeling, analysis and simulation of wireless and mobile systems

An ad hoc wireless mobile network is an infrastructure-less mobile network that has no fixed routers; instead, all nodes are capable of movement and can be connected dynamically in an arbitrary manner. In order to facilitate communication of mobile ...
Truthful multicast routing in selfish wireless networks
MobiCom '04: Proceedings of the 10th annual international conference on Mobile computing and networking

In wireless networks, it is often assumed that each individual wireless terminal will faithfully follow the prescribed protocols without any deviation-- except, perhaps, for a few faulty or malicious ones. Wireless terminals, when owned by individual ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking

IEEE/ACM Transactions on Networking Volume 18, Issue 2

April 2010

339 pages

ISSN:1063-6692

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 April 2010

Revised: 29 April 2008

Received: 03 October 2007

Published in TON Volume 18, Issue 2

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
250
Total Downloads

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

Reflects downloads up to 26 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Reddy MBabu M(2019)Implementing self adaptiveness in whale optimization for cluster head section in Internet of ThingsCluster Computing10.1007/s10586-017-1628-322:1(1361-1372)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1007/s10586-017-1628-3
Maddikunta PMadda R(2017)Energy Aware Cluster Head Selection for Maximizing Lifetime Improvement in Internet of ThingsInternational Journal of Grid and High Performance Computing10.4018/IJGHPC.20171001059:4(71-91)Online publication date: 1-Oct-2017
https://dl.acm.org/doi/10.4018/IJGHPC.2017100105
Liao HDing S(2015)Mixed and continuous strategy Monitor-Forward game based selective forwarding solution in WSNInternational Journal of Distributed Sensor Networks10.1155/2015/3597802015(7-7)Online publication date: 1-Jan-2015
https://dl.acm.org/doi/10.1155/2015/359780
Martignon FParis SFilippini IChen LCapone A(2015)Efficient and truthful bandwidth allocation in wireless mesh community networksIEEE/ACM Transactions on Networking10.1109/TNET.2013.229640123:1(161-174)Online publication date: 1-Feb-2015
https://dl.acm.org/doi/10.1109/TNET.2013.2296401
Shen HLi Z(2015)A hierarchical account-aided reputation management system for MANETsIEEE/ACM Transactions on Networking10.1109/TNET.2013.229073123:1(70-84)Online publication date: 1-Feb-2015
https://dl.acm.org/doi/10.1109/TNET.2013.2290731
Samian NZukarnain ZSeah WAbdullah AHanapi Z(2015)Cooperation stimulation mechanisms for wireless multihop networksJournal of Network and Computer Applications10.1016/j.jnca.2015.04.01254:C(88-106)Online publication date: 1-Aug-2015
https://dl.acm.org/doi/10.1016/j.jnca.2015.04.012
Wang DWang P(2014)On the anonymity of two-factor authentication schemes for wireless sensor networksComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2014.07.01073:C(41-57)Online publication date: 14-Nov-2014
https://dl.acm.org/doi/10.1016/j.comnet.2014.07.010
Chen ZQiao CXu LWu W(2014)Optimizing wireless unicast and multicast sensor networks on the basis of evolutionary game theoryConcurrency and Computation: Practice & Experience10.1002/cpe.306026:5(1130-1141)Online publication date: 10-Apr-2014
https://dl.acm.org/doi/10.1002/cpe.3060
Duan JGao DFoh CZhang H(2013)TC-BACAd Hoc Networks10.1016/j.adhoc.2013.05.00511:8(2675-2692)Online publication date: 1-Nov-2013
https://dl.acm.org/doi/10.1016/j.adhoc.2013.05.005
Igartua Mde la Cruz Llopis LFrías VGargallo E(2011)A game-theoretic multipath routing for video-streaming services over Mobile Ad Hoc NetworksComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2011.06.00755:13(2985-3000)Online publication date: 1-Sep-2011
https://dl.acm.org/doi/10.1016/j.comnet.2011.06.007

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents