A light-weight scalable truthful routing protocol in MANETs with selfish nodes
Pages 210 - 222
Abstract
We introduce a Light-weight Scalable Truthful rOuting Protocol (LSTOP) for selfish nodes problem in mobile ad hoc networks where a node may use different cost to send packets to different neighbours. LSTOP encourages nodes' cooperation by rewarding nodes for their forwarding service according to their cost. It incurs a low overhead of O(n2) in the worst case and only O(n) on the average. We show the truthfulness of LSTOP and present the result of an extensive simulation study to show that LSTOP approaches optimal (cost) routing and achieves significant better network performance compared to ad hoc-VCG.
References
[1]
Anderegg, L. and Eidenbenz, S. (2003) 'Ad hoc-vcg: a truthful and cost-efficient routing protocol for mobile ad hoc networks with selfish agents', Mobicom '03: Proceedings of the 9th Annual International Conference on Mobile Computing and Networking, September, pp.245-259.
[2]
Broch, J., Maltz, D.A., Johnson, D.B., Hu, Y-C. and Jetcheva, J. (1998) 'A performance comparison of multi-hop wireless ad hoc network routing protocols', Mobicom'98: Proceedings of the 4th Annual ACM/IEEE International Conference on Mobile Computing and Networking, October, pp.85-97.
[3]
Buchegger, S. and Le-Boudec, J.Y. (2002a) 'Nodes bearing grudges: towards routing security, fairness, and robustness in mobile ad hoc networks', Proceedings of EUROMICROPDP'02 , January, pp.403-410.
[4]
Buchegger, S. and Le Boudec, J-Y. (2002b) 'Performance analysis of the confidant protocol', Mobihoc'02: Proceedings of the 3rd ACM International Symposium on Mobile Ad Hoc Networking and Computing, June, pp.226-236. 513828
[5]
Buttyan, L. and Hubaux, J. (2003) 'Stimulating cooperation in self-organizing mobile ad hoc networks', ACM/Kluwer Mobile Networks and Applications, Vol. 8, No. 5, pp.579-592.
[6]
Buttyan, L. and Hubaux, J-P. (2000) 'Enforcing service availability in mobile ad-hoc wans', Mobihoc '00: Proceedings of the 1st ACM International Symposium on Mobile Ad Hoc Networking and Computing, August, pp.87-96.
[7]
Cai, J. and Pooch, U. (2004) 'Play alone or together-truthful and efficient routing in wireless ad hoc networks with selfish nodes', Proceeding of 1st Ieee International Conference on Mobile Ad-Hoc and Sensor Systems (MASS'04), October, pp.457-465.
[8]
Camp, T., Boleng, J. and Davies, V. (2002) 'A survey of mobility models for ad hoc network research', Wireless Communication and Mobile Computing (WCMC): Special Issue on Mobile Ad Hoc Networking: Research, Trends and Applications, Vol. 2, No. 5, pp.483-502.
[9]
Chen, K. and Nahrstedt, K. (2004) 'ipass: and incentive compatible auction scheme to enable packet forwarding service in manet', Proceedings of the 24th International Conference on Distributed Computing Systems (ICDCS'04), March, pp.534-542.
[10]
Clarke, E. (1971) 'Multipart pricing of public goods', Public Choice, Vol. 11, pp.17-33.
[11]
Feigenbaum, J., Papadimitriou, C., Sami, R. and Shenker, S. (2002) 'A bgp-based mechanism for lowest cost routing', Proceedings of the 2002 ACM Symposium on Principles of Distributed Computing, July, pp.173-182.
[12]
Groves, T. (1973) 'Incentives in teams', Econometrica, Vol. 41, pp.617-663.
[13]
Johansson, P., Larsson, T., Hedman, N., Mielczarek, B. and Degermark, M. (1999) 'Scenario-based performance analysis of routing protocols for mobile ad-hoc networks', Mobicom '99: Proceedings of the 5th Annual ACM/IEEE International Conference on Mobile Computing and Networking, August, pp.195-206.
[14]
Johnson, D.B. and Maltz, D.A. (1996) 'Dynamic source routing in ad hoc wireless networks', Mobile Computing, Vol. 353, pp.153-181.
[15]
Marti, S., Giuli, T.J., Lai, K. and Baker, M. (2000) 'Mitigating routing misbehavior in mobile ad hoc networks', Mobicom '00: Proceedings of the 6th Annual International Conference on Mobile Computing and Networking, August, pp.255-265.
[16]
Michiardi, P. and Molva, R. (2002) 'Core: a collaborative reputation mechanism to enforce node cooperation in mobile ad hoc networks', Proceedings of the IFIP TC6/TCLL Sixth 18 Joint Working Conference on Communications and Multimedia Security: Advanced Communications and Multimedia Security, September, pp.107-121.
[17]
Miranda, H. and Rodrigues, L. (2002) 'Preventing selfishness in open mobile ad hoc networks', Proceedings of 7th CaberNet Radicals Workshop, October.
[18]
Nisan, N. and Ronen, A. (2001) 'Algorithmic mechanism design', Games and Economic Behavior, Vol. 35, pp.166-196.
[19]
Paul, K. and Westhoft, D. 'Context aware detection of selfish nodes in dsr based ad-hoc networks', Proceedings of IEEE Vehicular Technology Conference'02, September, pp.2424-2429.
[20]
Perkins, C. (1997) 'Ad-hoc on-demand distance vector routing', Internet draft RFC 3561, Novomber.
[21]
Salem, N.B., Buttyan, L., Hubaux, J-P. and Jakobsson, M. (2003) 'A charging and rewarding scheme for packet forwarding in multi-hop cellular networks', Mobihoc '03: Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking and Computing, June, pp.13-24.
[22]
Srinivasan, V., Nuggehalli, P., Chiasserini, C. and Rao, R. (2003) 'Cooperation in wireless ad hoc networks', Proceedings of 22th Annual IEEE Conference on Computer Communications (Infocom'03), April, pp.808-817.
[23]
Takai, M., Martin, J. and Bagrodia, R. (2001) 'Effects of wireless physical layer modeling in mobile ad hoc networks', Mobihoc '01: Proceedings of the 2nd ACM International Symposium on Mobile Ad Hoc Networking and Computing, October, pp.87-94.
[24]
Vickrey, W. (1960) 'Counterspeculation, auctions and competitive sealed tenders', Journal of Finance, Vol. 16, pp.8-37.
[25]
Wang, W. and Li, X-Y. (2004) 'Truthful low cost unicast in selfish wireless networks', Proceedings of 18th International Parallel and Distributed Processing Symposium (IPDPS'04) - Workshop 12, April, p.219b.
[26]
Wang, Y., Venkata, C.G. and Singhal, M. (2004) 'A fair distributed solution for selfish node problem in mobile ad hoc networks', Proceedings of 3rd International Conference on Ad-Hoc Networks and Wireless (ADHOCNOW'04), July, pp.211-224.
[27]
Zhong, S., Yang, Y.R. and Chen, J. (2003) 'Sprite: a simple, cheat-proof, credit-based system for mobile ad-hoc networks', Proceedings of 22th Annual IEEE Conference on Computer Communications (Infocom'03), pp.1987-1997.
[28]
Zhong, S., Li, L.E., Liu, Y.G. and Yang, Y.R. (2005) 'On designing incentive-compatible routing and forwarding protocols in wireless ad-hoc networks: an integrated approach using game theoretical and cryptographic techniques', Mobicom '05: Proceedings of the 11th Annual International Conference on Mobile Computing and Networking, August, pp.117-131.
- A light-weight scalable truthful routing protocol in MANETs with selfish nodes
Recommendations
Truthful multipath routing for ad hoc networks with selfish nodes
Multiple path routing protocols are shown to be performance-effective alternatives over single-path routing for ad hoc networks. They provide better resistance to link breakage and load balancing. However, these protocols typically assume a cooperative ...
On improving the efficiency of truthful routing in MANETs with selfish nodes
In Mobile Ad Hoc Networks (MANETs), nodes depend upon each other for routing and forwarding packets. However, nodes belonging to independent authorities in MANETs may behave selfishly and may not forward packets to save battery and other resources. To ...
A gradual solution to detect selfish nodes in mobile ad hoc networks
The resource limitation of nodes forming ad hoc networks along with the multi-hop nature of these networks rise a new problem. To preserve its energy a node may behave selfishly and would not forward packets for others, while using their services and ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Publisher
Inderscience Publishers
Geneva 15, Switzerland
Publication History
Published: 01 April 2009
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 14 Dec 2024