Distributed method for minimum delay multi-hop data delivery in vehicular networks

• US 8,761,175 B2
• Filed: 03/20/2009
• Issued: 06/24/2014
• Est. Priority Date: 03/20/2008
• Status: Active Grant

• Current Assignee: Nytell Software LLC (Intellectual Ventures LLC)
• Original Assignee: TTI Inventions D LLC (Intellectual Ventures LLC)
• Inventors: Guha, Ratul K., Chen, Wai, Demers, Stephanie, Chennikara-Varghese, Jasmine
• Primary Examiner(s): PHAN, MAN U
• Application Number:
  US12/408,221
• Publication Number:
  US 20090238187A1
• Time in Patent Office: 1,922 Days
• Field of Search: 370229-465, 340436-463, 340902-916, 709222-241, 701200-533
• US Class Current: 370/392
• CPC Class Codes: G08G 1/161 Decentralised systems, e.g. inter-vehicle communication
• CPC Class Codes: H04L 2012/40273 the transportation system being a vehicle
• CPC Class Codes: H04W 40/20 based on geographic position or location

Abstract

An inventive method for data delivery in a multi-hop vehicular network with multiple vehicles and intersections is presented. The method comprises, at each source vehicle, initiating packet flow, labeling packets with destination coordinates and a current location, and forwarding the packet flow, and at each intersection, selecting a header vehicle, computing a backlog indicator and listening for broadcasts with a matrix and delay information, updating the matrix in accordance with the backlog indicator if the matrix is present, otherwise initializing the matrix, forwarding the packet flow, and broadcasting the matrix from the header vehicle. In one embodiment, selection of the header vehicle is performed based on random countdown and vehicle ID. The method converges to the optimal (lowest latency) state irrespective of the initial starting point of the network and continues to tend towards the optimal state even as the network conditions alter.

Claims

1. A method comprising:

receiving a packet flow from a source vehicle at a header vehicle, wherein the packet flow includes packets that are labeled with destination coordinates and a location of the source vehicle;

computing a backlog indicator at the header vehicle at an intersection, wherein the backlog indicator represents an amount of packet flow backlog at the intersection;

updating network information regarding the intersection with the backlog indicator;

forwarding the packet flow based at least in part on the network information; and

broadcasting the network information from the header vehicle.

2. The method according to claim 1, further comprising selecting the header vehicle based on a random countdown and a vehicle identifier (ID).

3. The method according to claim 1, wherein the packet flow is received at the intersection, and wherein the broadcasting is performed after the header vehicle leaves the intersection.

4. The method according to claim 1, wherein the network information includes the backlog indicator and a forwarding component.

13. The method of claim 1, further comprising listening for a broadcast that includes the network information.

14. The method of claim 1, further comprising listening for a broadcast that includes delay information.

15. The method of claim 1, further comprising determining whether the network information is present.

16. The method of claim 15, further comprising initializing a matrix in accordance with the backlog indicator if the network information is not present.

5. A non-transitory computer-readable medium having computer-instructions stored thereon, the instructions comprising:

instructions to receive, at a header vehicle, a packet flow, wherein the packet flow includes packets that are labeled with destination coordinates and a location of a source vehicle;

instructions to compute a backlog indicator at an intersection, wherein the backlog indicator represents an amount of packet flow backlog at the intersection;

instructions to update network information regarding the intersection with the backlog indicator;

instructions to forward the packet flow based at least in part on the network information; and

instructions to broadcast the network information from the header vehicle.

6. The non-transitory computer-readable medium according to claim 5, further comprising instructions to select the header vehicle based on a random countdown and a vehicle identifier (ID).

7. The non-transitory computer-readable medium according to claim 5, wherein the packet flow is received at the intersection, and wherein the broadcast is performed after the header vehicle leaves the intersection.

8. The non-transitory computer-readable medium according to claim 5, wherein the network information includes the backlog indicator and a forwarding component.

9. The non-transitory computer-readable medium of claim 5, further comprising instructions to listen for a broadcast that includes the network information.

10. The non-transitory computer-readable medium of claim 5, further comprising instructions to listen for a broadcast that includes delay information.

11. The non-transitory computer-readable medium of claim 5, further comprising instructions to determine whether the network information is present.

12. The non-transitory computer-readable medium of claim 11, further comprising instructions to initialize a matrix that includes the network information if the network information is not present.

17. A system comprising:

a memory configured to store a packet flow that is received from a source vehicle, wherein the packet flow includes packets that are labeled with destination coordinates and a location of the source vehicle; and

a processor operatively coupled to the memory and configured to;

compute a backlog indicator at an intersection, wherein the backlog indicator represents an amount of packet flow backlog at the intersection;

update network information regarding the intersection with the backlog indicator;

forward the packet flow based at least in part on the network information; and

broadcast the network information.

18. The system of claim 17, wherein the packet flow is received at the intersection, and wherein the broadcast is performed after a header vehicle that includes the system leaves the intersection.

19. The system of claim 17, wherein the network information includes the backlog indicator and a forwarding component.

20. The system of claim 17, wherein the processor is further configured to:

determine whether the network is present; and

initialize a matrix in accordance with the backlog indicator if the network information is not present.