AD HOC COMMUNICATION SYSTEM

• US 20100128653A1
• Filed: 03/28/2008
• Published: 05/27/2010
• Est. Priority Date: 03/30/2007
• Status: Active Grant

• Current Assignee: British Telecommunications PLC (BT Group PLC)
• Original Assignee: British Telecommunications Public Limited Company
• Inventors: Tateson, Jane E.
• Granted Patent: US 8,462,691 B2
• Time in Patent Office: Days
• US Class Current: 370/315
• CPC Class Codes: H04L 1/188 Time-out mechanisms
• CPC Class Codes: H04L 2001/0097 Relays
• CPC Class Codes: H04L 45/124 using a combination of metrics
• CPC Class Codes: H04L 47/30 in combination with information about buffer occupancy at either end or at transit nodes
• CPC Class Codes: H04L 69/28 Timers or timing mechanisms used in protocols
• CPC Class Codes: H04W 28/10 Flow control between communication endpoints
• CPC Class Codes: H04W 28/14 using intermediate storage
• CPC Class Codes: H04W 40/04 based on wireless node resources
• CPC Class Codes: H04W 40/18 based on predicted events
• CPC Class Codes: H04W 40/20 based on geographic position or location
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

A number of data relay devices, e.g. mobile telephones, (10, 20, 30, 40, 50, 60, 70, 80), are conveyed by vehicles and move relative to each other. They form a vehicular ad hoc wireless network (19, 29, 39, 49), etc in which data stored by a device (20) (either own-generated or relayed from another device (10) is transmitted either directly or by means of one or more other devices (30) to a network access point (90) which interfaces with a cellular network. When two devices (20, 30) come into proximity to each other, they use an opportunistic routing algorithm to determine a forwarding direction for the data. A retransmit timer is triggered on transmission of data, and messages which are unacknowledged at the expiry of the timer period are retransmitted. The timer period dynamically follows local congestion conditions and is recalculated at each transmission by the expression, timer minimum period/recent forwarding success(t). The current recent forwarding success at time t, RFS(t), is calculated from the RFS(t−1) calculated for the immediately preceding transmission and from the current forwarding success, CFS, by the expression RFS(t)=⅘ RFS(t−1)+⅕ CFS(t) where CFS is the square of the ratio of the available buffer space in the target device to the size of the payload in the source device.

Claims

1. A method of operating an opportunistic relaying network comprising at least one network access point, and a plurality of mobile wireless data relay devices each having a buffer for storing data messages, whether own-generated or received, such stored data messages being referred to hereafter as payload data, the method comprising the steps of:

at a source one of said devices having payload data to be relayed to a network access point, the network access point being out of range of the source device, (a) transmitting a request to transmit, RTS, in respect of payload data;

(b) receiving, from each said device within range of the source device and responding to the transmitted RTS, respective status data comprising an indication of its buffer vacancy;

(c) selecting in accordance with an opportunistic routing algorithm, a responding device to receive payload data;

(d) setting the period of a retransmit timer to be a minimum value multiplied by an inverse function of the buffer vacancy of the selected device;

(e) transmitting payload data to the selected device;

(f) triggering, upon that transmission, the retransmit timer; and

(g) upon expiry of the retransmit timer period, repeating steps (a) to (f) in respect of any transmitted payload data for which acknowledgement generated by a network access point has not been received.

2. A method as claimed in claim 1, wherein the inverse function includes the ratio of the buffer occupancy of the source device to the buffer vacancy of the selected device.

3. A method as claimed in claim 2, wherein the inverse function includes the square of that ratio.

4. A method as claimed in claim 3, wherein the inverse function is the summation of two terms, the first term being a fraction k of the square of that ratio, and the second term being a fraction j of the value of the inverse function for the immediately preceding transmission from that source device.

5. A method as claimed in claim 4, wherein the fraction j is equal to 1−

k.

6. A method as claimed in claim 5, wherein the fraction k is one fifth.

7. A method as claimed in claim 1, wherein the source device transmits the payload data together with associated identifiers, and the or each network access point is arranged such that the generated acknowledgement includes the identifiers of received payload data.

8. A method as claimed in claim 1, wherein the devices send received acknowledgements when responding to a received RTS.

9. A method as claimed in claim 1, wherein the devices send received acknowledgements in response to receipt of payload data.

10. A data relay device (20) having:

a buffer (24) for storing payload data for subsequent transmission;

a transmitter (21);

a receiver (22);

requesting means (26, 27) for sending to the transmitter a request to transmit, RTS, in respect of payload data;

a retransmit timer (28) having a minimum timer period;

processing means (26, 27), responsive to status data received from other devices responding to a transmitted RTS, to select, in accordance with an opportunistic routing algorithm, a responding device, to send to the transmitter (21) payload data for the selected device and to trigger the retransmit timer (28), and responsive to receipt of an RTS from another device to generate status data including an indication of its buffer vacancy and to send that generated status data to the transmitter (21);

setting means (26) responsive to an indication of buffer vacancy included in received status data to set the period of the retransmit timer (28) to be the minimum period multiplied by an inverse function of the buffer vacancy of the selected device; and

means responsive to the absence, at the expiry of the retransmit timer period, of acknowledgement in respect of transmitted payload data to cause the requesting means (26, 27) to send a further request to the transmitter, and to cause the processing means to

repeat in respect of unacknowledged transmitted payload data, its functions of selecting, sending and triggering.

11. A device as claimed in claim 10, wherein the inverse function includes the ratio of the buffer occupancy of the source device to the buffer vacancy of the selected device.

12. A device as claimed in claim 11, wherein the inverse function includes the square of that ratio.

13. A device as claimed in claim 12, wherein the inverse function includes a fraction k of the square of that ratio added to a fraction j of the inverse function for the immediately preceding transmission from that source device.

14. A device as claimed in claim 13, wherein the fraction j is equal to 1−

k.

15. A device as claimed in claim 14, wherein the fraction k is one fifth.

16. A device as claimed in claim 10, wherein the processing means (26, 27) is arranged to transmit the payload data together with associated identifiers.

17. A device as claimed in claim 10, the processing means (26, 27) is arranged to send received acknowledgements when responding to a received RTS.

18. A device as claimed in claim 10, the processing means (26, 27) is arranged to send received acknowledgements in response to receipt of payload data.