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

Patent metadata

Field	Value
Publication number	US-10171965-B2
Application number	US-99699704-A
Country	US
Kind code	B2
Filing date	Nov 24, 2004
Priority date	Nov 25, 2003
Publication date	Jan 1, 2019
Grant date	Jan 1, 2019

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.

First claim

What is claimed is:

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

μ
=

MAC

K

u
o

⁡

(

p
,
L

)

,

where p denotes said at least a portion of the communication, L denotes said information indicative of a payment level that would be available if a forwarding intermediary user device is entitled to a payment claim, MAC denotes said message authentication code function, and K u o is a secret key associated with the sending user device.

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

Φ
=

MAC

K

u
o

⁡

(

p
,
L

)

,

where MAC denotes said message authentication code function and K u o is a secret key associated with the sending user device.

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 pro

Assignees

• Jakobsson Bjorn Markus
• Hubaux Jean Pierre
• Buttyan Levente
• Emc Ip Holding Co Llc

Inventors

• Jakobsson Bjorn Markus
• Hubaux Jean-Pierre
• Buttyán Levente

Classifications

• H04L9/3236

  using cryptographic hash functions · CPC title

• G06Q20/32

  using wireless devices · CPC title

• H04M2215/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 title

• H04M2215/32

  Involving wireless systems · CPC title

• H04W88/04

  adapted for relaying to or from another terminal or user · CPC title