research-article

Hidden information and actions in multi-hop wireless ad hoc networks

Authors:

Mo LiAuthors Info & Claims

MobiHoc '08: Proceedings of the 9th ACM international symposium on Mobile ad hoc networking and computing

Pages 283 - 292

https://doi.org/10.1145/1374618.1374657

Published: 26 May 2008 Publication History

Abstract

For multi-hop ad hoc networks formed by individually owned nodes, the endpoints can only observe whether or not the end-to-end transaction was successful or not, but not the individual actions of intermediate nodes. Consequently, in the absence of properly designed incentive schemes, rational (i.e., selfish) intermediate nodes may choose to forward data packets at a very low priority or simply drop the packets at all, and it could put the blame on the unreliable wireless channel. Using a principal-agent model, we propose several efficient methods that can eliminate the hidden actions under hidden information in multi-hop wireless networks with high probability. We design several algorithmic mechanisms for a number of routing scenarios such that each selfish agent will maximize its utility (i.e., profit) when it truthfully declares its type (i.e., cost and its actions) and it truthfully follows its declared actions. Our simulations show that the payment by our mechanisms is only slightly larger than the actual cost incurred by all intermediate nodes.

References

[1]

Alicherry, M., Bhatia, R., and Li, L. E. Joint channel assignment and routing for throughput optimization in multi-radio wireless mesh networks. In MobiCom '05 (2005), pp. 58--72.

Digital Library

[2]

Anderegg, L., and Eidenbenz, S. Ad hoc-vcg: a truthful and cost-efficient routing protocol for mobile ad hoc networks with selfish agents. In MobiCom '03 (2003), ACM Press, pp. 245--259.

Digital Library

[3]

Archer, A., and l. Tardos. Frugal path mechanisms. In SODA (2002), pp. 991--998.

Digital Library

[4]

Banerjee, S., and Misra, A. Minimum energy paths for reliable communication in multi-hop wireless networks. In the 3rd ACM MobiHoc'02 (2002), pp. 146--156.

Digital Library

[5]

Blazevic, L., Buttyan, L., Capkun, S., Giordano, S., Hubaux, J. P., and Boudec, J. Y. L. Self-organization in mobile ad-hoc networks: the approach of terminodes. IEEE Communications Magazine 39, 6 (June 2001).

Digital Library

[6]

Buchegger, S., and Boudec, J.-Y. L. A robust reputation system for p2p and mobile ad-hoc networks. In Second Workshop on the Economics of Peer-to-Peer Systems, with ACM Sigcomm (2004).

[7]

Buttyan, L., and Hubaux, J. Stimulating cooperation in self-organizing mobile ad hoc networks. ACM/Kluwer Mobile Networks and Applications 5, 8 (October 2003).

Digital Library

[8]

Buttyan, L., and Hubaux, J. P. Enforcing service availability in mobile ad-hoc wans. In ACM MobiHoc (2000), pp. 87--96.

Digital Library

[9]

Calinescu, G. Bounding the payment of approximate truthful mechanisms. In ISAAC (2004), pp. 221--233.

Digital Library

[10]

Chen, B., Jamieson, K., Balakrishnan, H., and Morris, R. Span: An energy-efficient coordination algorithm for topology maintenance in ad hoc wireless networks. In Mobile Computing and Networking (2001), pp. 85--96.

Digital Library

[11]

Clarke, E. H. Multipart pricing of public goods. Public Choice (1971), 17--33.

[12]

Dong, Q., Banerjee, S., Adler, M., and Misra, A. Minimum energy reliable paths using unreliable wireless links. In ACM MobiHoc (2005).

Digital Library

[13]

Elkind, E., Sahai, A., and Steiglitz, K. Frugality in path auctions. In Proceedings of the fifteenth annual ACM-SIAM SODA (2004), pp. 701--709.

Digital Library

[14]

Feigenbaum, J., Papadimitriou, C., Sami, R., and Shenker, S. A BGP-based mechanism for lowest-cost routing. In Proceedings of the 2002 ACM Symposium on Principles of Distributed Computing. (2002), pp. 173--182.

Digital Library

[15]

Feldman, M., and Chuang, J. Hidden-action in multi-hop routing. In Second Workshop on the Economics of Peer-to-Peer Systems, in conjunction with ACM Sigcomm (2004).

[16]

Feldman, M., Chuang, J., Stoica, I., and Shenker, S. Hidden-action in multi-hop routing. In ACM E-Commerce Conf. (2005).

Digital Library

[17]

Felegyhazi, M., Buttyan, L., and Hubaux, J. Equilibrium analysis of packet forwarding strategies in wireless ad hoc networks - the static case. In Personal Wireless Communications, (2003).

[18]

Groves, T. Incentives in teams. Econometrica (1973), 617--631.

[19]

Hershberger, J., and Suri, S. Vickrey pricing in network routing: Fast payment computation. In IEEE Symp. on Foundations of Computer Science (FOCS) (2001), pp. 252--259.

Digital Library

[20]

Jain, K., Padhye, J., Padmanabhan, V. N., and Qiu, L. Impact of interference on multi-hop wireless network performance. In MobiCom '03 (2003), ACM Press, pp. 66--80.

Digital Library

[21]

Jakobsson, M., Hubaux, J.-P., and Buttyan, L. A micro-payment scheme encouraging collaboration in multi-hop cellular networks. In Proceedings of Financial Cryptography (2003).

[22]

Karlin, A., Kempe, D., and Tamir, T. Beyond vcg: Frugality of truthful mechanisms. In To appear in FOCS (2005).

Digital Library

[23]

Kodialam, M., and Nandagopal, T. Characterizing achievable rates in multi-hop wireless networks: the joint routing and scheduling problem. In MobiCom '03 (2003), ACM Press, pp. 42--54.

Digital Library

[24]

Kumar, V. S. A., Marathe, M. V., Parthasarathy, S., and Srinivasan, A. Algorithmic aspects of capacity in wireless networks. SIGMETRICS Perform. Eval. Rev. 33, 1 (2005), 133--144.

Digital Library

[25]

Lazar, A. A., Orda, A., and Pendarakis, D. E. Virtual path bandwidth allocation in multiuser networks. IEEE/ACM Trans. Netw. 5, 6 (1997), 861--871.

Digital Library

[26]

Liang, B., and Haas, Z. J. Virtual backbone generation and maintenance in ad hoc network mobility management. In Proc. of IEEE INFOCOM (2000), vol. 3, pp. 1293--1302.

[27]

Marti, S., Giuli, T. J., Lai, K., and Baker, M. Mitigating routing misbe-havior in mobile ad hoc networks. In ACM MobiCom (2000).

Digital Library

[28]

N. Immorlica, D. Karger, E. N., and Sami, R. First-price path auctions. In 6th ACM E-Commerce Conf. (2005).

Digital Library

[29]

Nisan, N., and Ronen, A. Algorithmic mechanism design. In ACM Sympo. on Theory of Computing (STOC) (1999), pp. 129--140.

Digital Library

[30]

Orda, A., Rom, R., and Shimkin, N. Competitive routing in multiuser communication networks. IEEE/ACM Trans. Netw. 1, 5 (1993), 510--521.

Digital Library

[31]

Orda, A., and Shimkin, N. Incentive pricing in multi-class communication networks. In IEEE INFOCOM (2) (1997), pp. 659--666.

Digital Library

[32]

Osborne, M. J., and Rubinstein, A. A course in game theory. The MIT Press, 2002.

[33]

Qiu, L., Yang, Y. R., Zhang, Y., and Shenker, S. On selfish routing in internet-like environments. In ACM SIGCOMM (2003), pp. 151--162.

Digital Library

[34]

Salem, N. B., Buttyan, L., Hubaux, J.-P., and Kakobsson, M. A charging and rewarding scheme for packet forwarding in multi-hop cellular networks. In ACM MobiHoc (2003).

Digital Library

[35]

Sinha, P., Sivakumar, R., and Bharghavan, V. Cedar: Core extraction distributed ad hoc routing algorithm. IEEE Journal on Selected Areas in Communications 17, 8 (August 1999), 1454--1465.

Digital Library

[36]

Srinivasan, V., Nuggehalli, P., Chiasserini, C. F., and Rao, R. R. Energy efficiency of ad hoc wireless networks with selfish users. In European Wireless Conference (2002).

[37]

Srinivasan, V., Nuggehalli, P., Chiasserini, C. F., and Rao, R. R. Cooperation in wireless ad hoc wireless networks. In IEEE INFOCOM (2003).

[38]

Talwar, K. The price of truth: Frugality in truthful mechanisms. In Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science (2003), Springer-Verlag, pp. 608--619.

Digital Library

[39]

Vickrey, W. Counterspeculation, auctions and competitive sealed tenders. Journal of Finance (1961), 8--37.

[40]

Wang, W., and Li, X.-Y. Low-cost routing in selfish and rational wireless ad hoc networks. IEEE Tran. on Mobile Computing (2005).

Digital Library

[41]

Wang, W., and Li, X.-Y. Nash equilibrium, dominant strategies in routing. In Workshop for Internet and Network Economics (2005).

Digital Library

[42]

Wang, W., Li, X.-Y., and Wang, Y. Truthful mutlicast in selfish wireless networks. In ACM MobiCom (2004).

Digital Library

[43]

Yi, C.-W. Probabilistic Aspects of Wireless Ad Hoc Networks. PhD thesis, Illinois Institute of Technology, 2005.

Digital Library

[44]

Zhong, S., Chen, J., and Yang, Y. SPRITE: A simple, cheat-proof, credit-based system for mobile ad hoc networks. In IEEE INFOCOM (2003).

[45]

Zhong, S., Li, L., Liu, Y., and Yang, Y. R. On designing incentive-compatible routing and forwarding protocols in wireless ad-hoc networks. In ACM Mobicom (2005).

Digital Library

Cited By

Shan AFan XChen XJi YWu C(2024)A Reinforcement Learning-Based Incentive Scheme for Multi-Hop Communications in Vehicular NetworksIEEE Transactions on Cognitive Communications and Networking10.1109/TCCN.2023.331664410:1(335-347)Online publication date: Feb-2024
https://doi.org/10.1109/TCCN.2023.3316644
Srikaanth PNagarajan V(2021)Fuzzy Rough Set Derived Probabilistic Variable Precision-Based Mitigation Technique for Vampire Attack in MANETsWireless Personal Communications10.1007/s11277-021-08673-zOnline publication date: 9-Jul-2021
https://doi.org/10.1007/s11277-021-08673-z
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
Show More Cited By

Index Terms

Hidden information and actions in multi-hop wireless ad hoc networks

Recommendations

A Simulation Analysis of Routing Misbehaviour in Mobile Ad Hoc Networks
NGMAST '08: Proceedings of the 2008 The Second International Conference on Next Generation Mobile Applications, Services, and Technologies

Mobile Ad hoc Networks (MANETs) rely on the cooperation of all participating nodes to provide the fundamental operations such as routing and data forwarding. However, misbehaving nodes may not follow the cooperation paradigm and cause a serious affect ...
Fighting against packet dropping misbehavior in multi-hop wireless ad hoc networks

In multi-hop wireless ad hoc networks, the packets are forwarded through intermediate nodes along the source-destination path. Without having any control on packets forwarding, an intermediate node can behave selfishly or maliciously to drop packets ...
Flooding in wireless ad hoc networks

In an ad hoc network, each host assumes the role of a router and relays packets toward final destinations. This paper studies efficient routing mechanisms for packet flooding in ad hoc wireless networks. Because a packet is broadcast to all neighboring ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

MobiHoc '08: Proceedings of the 9th ACM international symposium on Mobile ad hoc networking and computing

May 2008

474 pages

ISBN:9781605580739

DOI:10.1145/1374618

General Chair:
Xiaohua Jia
City University of Hong Kong, Hong Kong
,
Program Chairs:
Ness B. Shroff
Ohio State University, USA
,
Peng-Jun Wan
Illinois Institute of Technology, USA

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 May 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

MobiHoc08

Sponsor:

MobiHoc08: The Ninth ACM International Symposium on Mobile Ad Hoc Networking and Computing

May 26 - 30, 2008

Hong Kong, Hong Kong, China

Acceptance Rates

Overall Acceptance Rate 296 of 1,843 submissions, 16%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

29
Total Citations
View Citations
598
Total Downloads

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

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Shan AFan XChen XJi YWu C(2024)A Reinforcement Learning-Based Incentive Scheme for Multi-Hop Communications in Vehicular NetworksIEEE Transactions on Cognitive Communications and Networking10.1109/TCCN.2023.331664410:1(335-347)Online publication date: Feb-2024
https://doi.org/10.1109/TCCN.2023.3316644
Srikaanth PNagarajan V(2021)Fuzzy Rough Set Derived Probabilistic Variable Precision-Based Mitigation Technique for Vampire Attack in MANETsWireless Personal Communications10.1007/s11277-021-08673-zOnline publication date: 9-Jul-2021
https://doi.org/10.1007/s11277-021-08673-z
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
Balaji Srikaanth PNagarajan V(2018)A Fuzzy Trust Relationship Perspective-Based Prevention Mechanism for Vampire Attack in MANETsWireless Personal Communications: An International Journal10.1007/s11277-018-5691-8101:1(339-357)Online publication date: 1-Jul-2018
https://dl.acm.org/doi/10.1007/s11277-018-5691-8
Chen HLou WWang ZWang Q(2016)A Secure Credit-Based Incentive Mechanism for Message Forwarding in Noncooperative DTNsIEEE Transactions on Vehicular Technology10.1109/TVT.2015.247716465:8(6377-6388)Online publication date: Aug-2016
https://doi.org/10.1109/TVT.2015.2477164
Calinescu G(2015)Bounding the payment of approximate truthful mechanismsTheoretical Computer Science10.1016/j.tcs.2014.10.019562:C(419-435)Online publication date: 11-Jan-2015
https://dl.acm.org/doi/10.1016/j.tcs.2014.10.019
Chen TZhong S(2014)An Enforceable Scheme for Packet Forwarding Cooperation in Network-Coding Wireless Networks With Opportunistic RoutingIEEE Transactions on Vehicular Technology10.1109/TVT.2014.231217163:9(4476-4491)Online publication date: Nov-2014
https://doi.org/10.1109/TVT.2014.2312171
Alsarhan AAl-Khasawneh AItradat AObeidat IBsoul M(2013)Spectrum trading for routing in a multi service cognitive mesh networkInternational Journal of Mobile Network Design and Innovation10.1504/IJMNDI.2013.0602265:2(85-96)Online publication date: 1-Mar-2013
https://dl.acm.org/doi/10.1504/IJMNDI.2013.060226
Chen HLou W(2013)Making Nodes Cooperative: A Secure Incentive Mechanism for Message Forwarding in DTNs2013 22nd International Conference on Computer Communication and Networks (ICCCN)10.1109/ICCCN.2013.6614150(1-7)Online publication date: Jul-2013
https://doi.org/10.1109/ICCCN.2013.6614150
Brahma SChatterjee M(2013)Multi-path routing in dynamic spectrum access networks: A mechanism design approach2013 IEEE International Conference on Communications (ICC)10.1109/ICC.2013.6654983(2905-2909)Online publication date: Jun-2013
https://doi.org/10.1109/ICC.2013.6654983
Show More Cited By

View Options

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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents