A charging and rewarding scheme for packet forwarding in multi-hop cellular networks

ABSTRACT

In multi-hop cellular networks, data packets have to be relayed hop by hop from a given mobile station to a base station and vice-versa. This means that the mobile stations must accept to forward information for the benefit of other stations. In this paper, we propose an incentive mechanism that is based on a charging/rewarding scheme and that makes collaboration rational for selfish nodes. We base our solution on symmetric cryptography to cope with the limited resources of the mobile stations. We provide a set of protocols and study their robustness with respect to various attacks. By leveraging on the relative stability of the routes, our solution leads to a very moderate overhead.

REFERENCES

• 1: G. N. Aggélou and R. Tafazolli. On the Relaying Capacity of Next-Generation GSM Cellular Networks. IEEE Personal Communications, February 2001.
• 2: Yigal Bejerano, Efficient integration of multi-hop wireless and wired networks with QoS constraints, Proceedings of the 8th annual international conference on Mobile computing and networking, September 23-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570645.570672]
• 3: L. Blazevic, L. Buttyán, S. Capkun, S. Giordano, J.-P. Hubaux, and J.-Y. Le Boudec. Self Organization in Mobile Ad-Hoc Networks: the Approach of Terminodes. IEEE Communications Magazine, 39(6), June 2001.
• 4: Josh Broch , David A. Maltz , David B. Johnson , Yih-Chun Hu , Jorjeta Jetcheva, A performance comparison of multi-hop wireless ad hoc network routing protocols, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.85-97, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288256]
• 5: 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]
• 6: 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
• 7: L. Buttyán and J.-P. Hubaux. Report on a Working Session on Security in Wireless Ad Hoc Networks. ACM Mobile Computing and Communications Review (MC2R), October 2002.
• 8: Levente Buttyán , Jean-Pierre Hubaux, Stimulating cooperation in self-organizing mobile ad hoc networks, Mobile Networks and Applications, v.8 n.5, p.579-592, October 2003 [doi>10.1023/A:1025146013151]
• 9: T. Camp, J. Boleng, and V. Davies. 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, 2(5):483--502, 2002.
• 10: B. Goode. Voice Over Internet Protocol (VoIP). Proceedings of the IEEE, 90:1495--1517, September 2002.
• 11: V. Gupta, S. Krishnamurthy, and M. Faloutsos. Denial of Service Attacks at the MAC Layer in Wireless Ad Hoc Networks. In Proceedings of Milcom, 2002.
• 12: Harri Holma , Antti Toskala, WCDMA for UMTS: Radio Access for Third Generation Mobile Communications, John Wiley & Sons, Inc., New York, NY, 2000
• 13: Hung-Yun Hsieh , Raghupathy Sivakumar, Towards a Hybrid Network Model for Wireless Packet Data Networks, Proceedings of the Seventh International Symposium on Computers and Communications (ISCC'02), p.264, July 01-04, 2002
• 14: http://www.eskimo.com/\verb+ +weidai/benchmarks.html.
• 15: http://www.terminodes.org.
• 16: Yih-Chun Hu , Adrian Perrig , David B. Johnson, Ariadne:: a secure on-demand routing protocol for ad hoc networks, Proceedings of the 8th annual international conference on Mobile computing and networking, September 23-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570645.570648]
• 17: Y.-C. Hu, A. Perrig, and D. B. Johnson. Packet Leashes: A Defense against Wormhole Attacks in Wireless Ad Hoc Networks. In Proceedings of INFOCOM. IEEE, 2003.
• 18: J.-P. Hubaux, T. Gross, J.-Y. Le Boudec, and M. Vetterli. Towards Self-Organizing Mobile Ad Hoc Networks: the Terminodes Project. IEEE Communications Magazine, 39(1):118 --124, January 2001.
• 19: M. Jakobsson, J.-P. Hubaux, and L. Buttyán. A Micro-Payment Scheme Encouraging Collaboration in Multi-Hop Cellular Networks. In Proceedings of Financial Cryptography, 2003.
• 20: D. B. Johnson and D. A. Maltz. Dynamic Source Routing in Ad Hoc Wireless Networks. In Mobile Computing edited by Tomasz Imielinski and Hank Korth, chapter 5, pages 153--181. Kluwer Academic Publishers, 1996.
• 21: M. Kubisch, S. Mengesha, D. Hollos, H. Karl, and A. Wolisz. Applying ad-hoc relaying to improve capacity, energy efficiency, and immission in infrastructure-based WLANs. In Proceedings of Kommunikation in Verteilten Systemen (KiVS 2003), Leipzig, Germany, February 2003.
• 22: B. Lamparter, K. Paul, and D. Westhoff. Charging Support for Ad Hoc Stub Networks. Journal of Computer Communication, Special Issue on 'Internet Pricing and Charging: Algorithms, Technology and Applications', Elsevier Science, Summer 2003.
• 23: Y.-D. Lin and Y.-C. Hsu. Multihop Cellular: A New Architecture for Wireless Communications. In Proceedings of INFOCOM. IEEE, 2000.
• 24: O. C. Mantel, N. Scully, and A. Mawira. Radio Aspects of Hybrid Wireless Ad Hoc Networks. In Proceedings of VTC. IEEE, 2001.
• 25: 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]
• 26: Silvio Micali , Ronald L. Rivest, Micropayments Revisited, Proceedings of the The Cryptographer's Track at the RSA Conference on Topics in Cryptology, p.149-163, February 18-22, 2002
• 27: Pietro Michiardi , Refik Molva, Core: a collaborative reputation mechanism to enforce node cooperation in mobile ad hoc networks, Proceedings of the IFIP TC6/TC11 Sixth Joint Working Conference on Communications and Multimedia Security: Advanced Communications and Multimedia Security, p.107-121, September 26-27, 2002
• 28: P. Papadimitratos and Z. J. Haas. Secure Routing for Mobile Ad Hoc Networks. In Proceedings of CNDS, January 2002.
• 29: K. Paul and D. Westhoff. Context Aware Inferencing to Rate a Selfish Node in DSR based Ad-hoc Network. In Proceedings of GLOBECOM, November 2002.
• 30: Adrian Perrig , Robert Szewczyk , Victor Wen , David Culler , J. D. Tygar, SPINS: security protocols for sensor netowrks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.189-199, July 2001, Rome, Italy [doi>10.1145/381677.381696]
• 31: H. Wu, C. Qios, S. De, and O. Tonguz. Integrated Cellular and Ad Hoc Relaying Systems: iCAR. IEEE Journal on Selected Areas in Communications, 19(10), October 2001.
• 32: J. Yoon, M. Liu, and B. Noble. Random Waypoint Considered Harmful. In Proceedings of INFOCOM. IEEE, 2003.
• 33: A. N. Zadeh, B. Jabbari, R. Pickholtz, and B. Vojcic. Self-Organizing Packet Radio Ad Hoc Networks with Overlay (SOPRANO). IEEE Communications Magazine, June 2002.
• 34: S. Zhong, Y. R. Yang, and J. Chen. Sprite: A Simple, Cheat-Proof, Credit-Based System for Mobile Ad Hoc Networks. In Proceedings of INFOCOM. IEEE, 2003.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

General Terms:
Algorithms, Design, Security

Keywords:
ad hoc networks, billing, charging, cooperation, hybrid cellular networks, multi-hop cellular networks, packet forwarding, pricing, security