Ad hoc communication system

• US 8,462,691 B2
• Filed: 03/28/2008
• Issued: 06/11/2013
• Est. Priority Date: 03/30/2007
• Status: Active Grant

• Current Assignee: British Telecommunications PLC (BT Group PLC)
• Original Assignee: British Telecommunications PLC (BT Group PLC)
• Inventors: Tateson, Jane E
• Primary Examiner(s): ABELSON, RONALD B
• Application Number:
  US12/594,013
• Publication Number:
  US 20100128653A1
• Time in Patent Office: 1,901 Days
• Field of Search: 370230-231, 370/235, 370/236, 370/238, 370/315, 370/328, 370/389, 370/392
• 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)=4/5 RFS(t−1)+1/5 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:

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 device-related 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 retransmission 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 retransmission timer; and

(g) upon expiry of the retransmission timer period,

repeating steps (a) to (f) in respect of any transmitted payload data for which acknowledgment generated by a network access point has not been received.

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

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

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

2. 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:

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 retransmission timer to be a minimum value multiplied by an inverse function of the buffer vacancy of the selected device, wherein the inverse function includes the ratio of the buffer occupancy of the source device to the buffer vacancy of the selected device;

(e) transmitting payload data to the selected device;

(f) triggering, upon that transmission, a retransmission timer; and

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

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.

19. A method as claimed in claim 2, 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 acknowledgment includes the identifiers of received payload data.

20. A method as claimed in claim 2, wherein the devices send received acknowledgments when responding to a received RTS.

21. A method as claimed in claim 2, wherein the devices send received acknowledgments in response to receipt of payload data.

10. A data relay device having:

a buffer for storing payload data for subsequent transmission;

a transmitter;

a receiver;

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

a retransmission timer having a minimum timer period;

processing means, responsive to respective device-related 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 payload data for the selected device and to trigger the retransmission timer, and responsive to receipt of an RTS from another device to generate its device-related status data including an indication of its buffer vacancy and to send that generated device-related status data to the transmitter;

setting means responsive to an indication of buffer vacancy included in received device status data to set the period of the retransmission timer 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 retransmission timer period, of acknowledgment in respect of transmitted payload data to cause the requesting means 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.

16. A device as claimed in claim 10, wherein the processing means is arranged to transmit the payload data in the form of messages together with associated message identifiers.

17. A device as claimed in claim 10, wherein the processing means is arranged to send received acknowledgments when responding to a received RTS.

18. A device as claimed in claim 10, wherein the processing means is arranged to send received acknowledgments in response to receipt of payload data.

11. A data relay device having:

a buffer for storing payload data for subsequent transmission;

a transmitter;

a receiver;

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

a retransmission timer having a minimum timer period;

processing means, 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 payload data for the selected device and to trigger the retransmission timer, 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;

setting means responsive to an indication of buffer vacancy included in received status data to set the period of the retransmission timer to be the minimum period multiplied by an inverse function of the buffer vacancy of the selected device, wherein the inverse function includes the ratio of the buffer occupancy of the source device to the buffer vacancy of the selected device; and

means responsive to the absence, at the expiry of the retransmission timer period, of acknowledgment in respect of transmitted payload data to cause the requesting means 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.

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.

22. A device as claimed in claim 11, wherein the processing means is arranged to transmit the payload data together with associated identifiers.

23. A device as claimed in claim 11, wherein the processing means is arranged to send received acknowledgments when responding to a received RTS.

24. A device as claimed in claim 11, wherein the processing means is arranged to send received acknowledgments in response to receipt of payload data.