Micro-payment scheme encouraging collaboration in multi-hop cellular networks

• US 10,171,965 B2
• Filed: 11/24/2004
• Issued: 01/01/2019
• Est. Priority Date: 11/25/2003
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Inventors: Jakobsson, Bjorn Markus, Hubaux, Jean-Pierre, Buttyan, Levente
• Primary Examiner(s): Coppola, Jacob C.
• Application Number:
  US10/996,997
• Publication Number:
  US 20050165696A1
• Time in Patent Office: 5,151 Days
• CPC Class Codes: G06Q 20/06 Private payment circuits, e.g. involving electronic currency used among participants of a common payment scheme
• CPC Class Codes: G06Q 20/29 characterised by micropayments
• CPC Class Codes: G06Q 20/326 Payment applications installed on the mobile devices
• CPC Class Codes: G06Q 20/367 involving electronic purses or money safes
• CPC Class Codes: G06Q 20/38215 Use of certificates or encrypted proofs of transaction rights
• CPC Class Codes: G06Q 20/3823 combining multiple encryption tools for a transaction
• CPC Class Codes: H04L 2209/56 Financial cryptography, e.g. electronic payment or e-cash
• CPC Class Codes: H04L 2209/80 Wireless network architectures or network communication protocols for wireless network security H04W12/00
• CPC Class Codes: H04L 9/3236 using cryptographic hash functions
• CPC Class Codes: H04M 15/68 Payment of value-added services
• CPC Class Codes: H04M 2215/0196 Payment of value-added services, mainly when their charges are added on the telephone bill, e.g. payment of non-telecom services, e-commerce, on-line banking
• CPC Class Codes: H04M 2215/2026 Wireless network, e.g. GSM, PCS, TACS
• CPC Class Codes: H04M 2215/32 Involving wireless systems
• CPC Class Codes: H04W 4/24 Accounting or billing
• CPC Class Codes: H04W 88/04 adapted for relaying to or from another terminal or user

Abstract

In a communication system having a number of base stations and user devices, a sending user device comprising a processor and a memory is configured to generate a packet or other communication for forwarding to a receiving user device via one or more intermediary user devices of the system. The forwarding path of the communication may involve one or more of the base stations. A payment token is associated with the communication, such that at least one of the intermediary user devices can generate a payment claim based on the payment token. The payment token is independent of the particular identities of the one or more intermediary user devices of the system.

Claims

1. A method for use in a communication system having a plurality of user devices configured to communicate with one or more base stations, the method comprising:

generating in a sending user device of the system a communication for forwarding to a receiving user device of the system via one or more intermediary user devices of the system; and

associating a payment token with the communication, such that at least one of the intermediary user devices can generate a payment claim based on the payment token;

wherein the payment token is independent of identities of the one or more intermediary user devices of the system, in that the payment token does not identify or otherwise make reference to any of the one or more intermediary user devices;

wherein the payment token comprises information identifying a payment that is obtainable by a given one of the intermediary user devices as its compensation for forwarding the communication to another user device;

wherein the payment token is generated using a message authentication code function which takes as one of its inputs at least a portion of the communication and as another of its inputs information indicative of a payment level that would be available if a forwarding intermediary user device is entitled to a payment claim; and

wherein the sending user device comprises a processor coupled to a memory, and the generating and associating steps are carried out under control of the processor.

2. The method of claim 1 wherein the communication comprises a packet.

3. The method of claim 1 wherein the payment token is independent of a total number of the one or more intermediary user devices of the system.

4. The method of claim 1 wherein the sending user device is unaware of the identities and total number of the one or more intermediary user devices involved in forwarding the communication from the sending user device to the receiving user device.

5. The method of claim 1 wherein the payment token is given by

6. The method of claim 1 further comprising the sending user device maintaining a connectivity graph comprising a list λ

_u of triples (u_i, d_i, L_i), where u_i is an identity of a given one of the intermediary user devices with a path of length d_i hops to a closest base station, and where L_i is a reward threshold of the given intermediary device for forwarding packets.

7. The method of claim 6 wherein the list λ

_u of triples (u_i, d_i, L_i) is sorted in terms of increasing values of d_i with entries having a same value of d_i sorted in terms of increasing values of L_i.

8. The method of claim 7 wherein the communication comprises a packet p, and further comprising:

the sending user device selecting a reward level L for the packet p, the reward level L comprising said information indicative of a payment level that would be available if a forwarding intermediary user device is entitled to a payment claim; and

the sending user device computing

9. The method of claim 8 wherein associating the payment token with the communication comprises assembling a tuple P=(L, p, u_o, μ

).

10. The method of claim 9 further comprising the sending user device selecting one of the intermediary devices for forwarding the communication to, wherein selecting the intermediary user device comprises:

(i) selecting a first entry from the list λ

_u of triples (u_i, d_i, L_i) for which L_i≤

L;

(ii) sending a forwarding request to a given intermediary device having the identity u_i in the selected first entry;

(iii) waiting a pre-set time period δ

to receive an acknowledgement from the given intermediary device;

(iv) responsive to receiving the acknowledgement from the given intermediary device within the pre-set time period δ

, forwarding P to the given intermediary device; and

(v) responsive to not receiving the acknowledgment from the given intermediary device within the pre-set time period δ

, incrementing i by one and repeating (i)-(v).

11. A computer program product comprising a non-transitory processor-readable storage medium having stored therein program code of one or more software programs, wherein the program code when executed by at least one processing device causes said at least one processing device to perform a method comprising:

generating, in a sending user device of a communication system having a plurality of user devices configured to communicate with one or more base stations, a communication for forwarding to a receiving user device of the system via one or more intermediary user devices of the system; and

associating a payment token with the communication, such that at least one of the intermediary user devices can generate a payment claim based on the payment token;

wherein the payment token is independent of identities of the one or more intermediary user devices of the system, in that the payment token does not identify or otherwise make reference to any of the one or more intermediary user devices;

wherein the payment token comprises information identifying a payment that is obtainable by a given one of the intermediary user devices as its compensation for forwarding the communication to another user device; and

wherein the payment token is generated using a message authentication code function which takes as one of its inputs at least a portion of the communication and as another of its inputs information indicative of a payment level that would be available if a forwarding intermediary user device is entitled to a payment claim.

12. The computer program product of claim 11 wherein the communication comprises a packet.

13. The computer program product of claim 11 wherein the payment token is independent of a total number of the one or more intermediary user devices of the system.

14. The computer program product of claim 11 wherein the sending user device is unaware of the identities and total number of the one or more intermediary user devices involved in forwarding the communication from the sending user device to the receiving user device.

15. The computer program product of claim 11 wherein the payment token is given by

16. The computer program product of claim 11 wherein the method further comprises maintaining a connectivity graph comprising a list λ

_u of triples (u_i, d_i, L_i), where u_i is an identity of a given one of the intermediary user devices with a path of length d_i hops to a closest base station, and where L_i is a reward threshold of the given intermediary device for forwarding packets.

17. The computer program product of claim 16 wherein the list λ

_u of triples (u_i, d_i, L_i) is sorted in terms of increasing values of d_i with entries having a same value of d_i sorted in terms of increasing values of L_i.

18. The computer program product of claim 17 wherein the communication comprises a packet p, and wherein the method further comprises:

selecting a reward level L for the packet p, the reward level L comprising said information indicative of a payment level that would be available if a forwarding intermediary user device is entitled to a payment claim; and

computing

19. The computer program product of claim 18 wherein associating the payment token with the communication comprises assembling a tuple P=(L, p, u_o, μ

).

20. The computer program product of claim 19 wherein the method further comprises selecting one of the intermediary devices for forwarding the communication to, wherein selecting the intermediary user device comprises:

(i) selecting a first entry from the list λ

_u of triples (u_i, d_i, L_i) for which L_i≤

L;

(ii) sending a forwarding request to a given intermediary device having the identity u_i in the selected first entry;

(iii) waiting a pre-set time period δ

to receive an acknowledgement from the given intermediary device;

(iv) responsive to receiving the acknowledgement from the given intermediary device within the pre-set time period δ

, forwarding P to the given intermediary device; and

(v) responsive to not receiving the acknowledgment from the given intermediary device within the pre-set time period δ

, incrementing i by one and repeating (i)-(v).