Stateful scheduling with network coding for roadside-to-vehicle communication

• US 8,687,530 B2
• Filed: 05/09/2008
• Issued: 04/01/2014
• Est. Priority Date: 05/09/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Luo, Chong, Lu, Han Cheng, Pu, Wei, Wu, Feng, Chen, Chang Wen
• Primary Examiner(s): Taha, Shaq
• Application Number:
  US12/117,756
• Publication Number:
  US 20090279462A1
• Time in Patent Office: 2,153 Days
• Field of Search: 370/310
• US Class Current: 370/310
• CPC Class Codes: H04B 7/15521 combining by calculations packets received from different stations before transmitting the combined packets as part of network coding network coding aspects for detection or prevention of errors in the information received H04L1/0076; network traffic management with optimizing of information sizing, e.g. header compression, by using assembly and disassembly of packets H04W28/065
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04W 28/06 Optimizing the usage of the radio link, e.g. header compression, information sizing , discarding information system modifying transmission characteristic according to link quality by modifying frame length H04L1/0007; dynamic adaptation of the packet size for flow control or congestion control H04L47/365

Abstract

Described is a technology by which a roadside-to-vehicle communication system may be implemented, including via a stateful scheduling with network coding scheme that enhances network capacity. Moving vehicles request and receive data from a roadside access points. Each of the access points operate a stateful scheduling algorithm that serves multiple vehicles by integrating network coding within a timeslot. In one aspect, the state of each vehicle'"'"'s previously received and retained data is obtained, and used to enhance network capacity by combining as many packets as possible for multiple recipients in network coding.

Claims

1. In a computing environment, a method comprising:

determining a primary recipient;

determining state data corresponding to data already received at the primary recipient based upon a previous transmission, wherein the state data is determined by an algorithm at a file-level granularity, wherein determining the state data comprises communicating with the primary recipient from an access point, and wherein the access point maintains a reception state table configured to track a current data state of each vehicle within range of the access point;

receiving a second set of data at one other recipient;

combining, using XOR operation, a first set of data intended for the primary recipient and the second set of data intended for the one other recipient, based upon the state data, into encoded data;

transmitting the encoded data to the primary recipient;

receiving an acknowledgement of receipt of the encoded data from the primary recipient, wherein only the primary recipient transmits acknowledgements of receipt;

in response to a determination that the second set of data was not intended for the one other recipient, determining whether the second set of data can be used in a decoding process in conjunction with the first set of data previously received by the primary recipient; and

in response to a determination that the set of data can be used in a decoding process in conjunction with another set of data previously received by the recipient, performing the decoding process.

2. The method of claim 1 further comprising:

sending the previous transmission from another access point.

3. The method of claim 1 further comprising:

receiving information from a server, the information intended for vehicular recipients.

4. The method of claim 1 wherein combining comprises XOR-ing at least two sets of data.

5. The method of claim 1 further comprising:

sending a new packet to a first recipient;

and changing state information associated with that new packet to indicate that the packet was sent.

6. The method of claim 1 further comprising:

detecting a new potential recipient in range of an access point; and

communicating with the new potential recipient to obtain state data of that new potential recipient.

7. The method of claim 1 further comprising:

communicating with the recipient to determine whether the encoded data was received by the recipient.

8. In a networking environment, a system comprising:

an access point, the access point configured to maintain a reception state table to track a current data of a plurality of mobile clients within range of the access point, the access point configured to communicate with the plurality of mobile clients, including to determine a primary mobile client of the plurality of mobile clients, to determine which set or sets of data each mobile client has previously received and which set of data each mobile client is requesting, wherein the sets of data is determined by an algorithm at a file-level granularity, the access point configured to;

combine, using XOR operation, a first set of data requested by the primary mobile client and a second set of data intended for one other mobile client, based upon the state data, into encoded data by which the respective mobile clients are able to decode the requested sets of data by using the sets of data that the respective mobile clients have previously received,

configured to transmit the common set of data to the mobile clients,

configured to receive an acknowledgment of receipt of the common set of data from the primary mobile client, wherein only the primary mobile client transmits acknowledgments or receipt;

in response to a determination that the second set of data was not intended for the one other mobile client, determining whether the second set of data can be used in a decoding process in conjunction with the first set of data previously received by the primary mobile client;

and in response to a determination that the second set of data can be used in a decoding process in conjunction with another set of data previously received by the primary mobile client, performing the decoding process.

9. The system of claim 8 wherein the access point is configured to maintain a data structure for each mobile client, wherein the data structure indicates the set or sets of data needed by each respective mobile client.

10. The system of claim 8 wherein the access point is configured to maintain a data structure for one or more of the plurality of the mobile clients, wherein the data structure tracks the set or sets of data previously received by each respective one or more of the plurality of the mobile clients.

11. The system of claim 8 wherein the access point couples an infrastructure network containing a server having vehicle-related information to a roadside network containing the plurality of mobile clients incorporated into vehicles.

12. The system of claim 8 wherein a mobile client of the plurality of mobile clients receives a given set of data, determines that the given set of data was intended for another mobile client of the mobile clients, and uses the given set of data in a decoding process in conjunction with another set of data previously received.

13. The system of claim 8 wherein the access point sends point coordination function-type message to one or more of the plurality of mobile clients, including a message communication by which the access point determines reception state data corresponding to which set or sets of data a given mobile client of the plurality of mobile clients has previously received.

14. The system of claim 8 wherein the access point communicates the set or sets of data to a particular mobile client of the plurality of mobile clients via a unicast communication and receives an acknowledgement only from the particular mobile client.

15. One or more computer storage devices having computer-executable instructions stored thereon, which in response to execution by a computer, cause the computer to perform steps, comprising:

communicating with a primary mobile client of a plurality of mobile clients that are within range of an access point, including obtaining state information from the primary mobile client that indicates what set or sets of previously-received data that the primary mobile client has retained, wherein the access point maintains a reception state table configured to track a current data state of each of the plurality of mobile clients within range of the access point, wherein the current data is determined by an algorithm at a file-level granularity;

combining, using XOR operation, a first set of data intended for the primary mobile client and the second set of data intended for the one other mobile client, based upon the state data, into encoded data;

communicating the combined set of data to the primary mobile client and to one other mobile client of the plurality of mobile clients, the combined set of data comprising data intended for the primary mobile client and the one other mobile client and being encoded such that the primary mobile client is capable of decoding the combined set of data into the data intended for the primary mobile client by using the set or sets of previously received data that the primary mobile client has retained;

and receiving an acknowledgment receipt of the combined set of data from the primary mobile client, wherein only the primary mobile client transmits acknowledgments of receipt;

in response to a determination that the second set of data was not intended for the one other mobile client, determining whether the second set of data can be used in a decoding process in conjunction with the first set of data previously received by the primary mobile client;

and in response to a determination that the second set of data can be used in a decoding process in conjunction with another set of data previously received by the primary mobile client, performing the decoding process.

16. The one or more computer storage devices of claim 15 having further computer-executable instructions stored thereon, which in response to execution by the computer, cause the computer to perform further steps comprising:

maintaining a data structure for each mobile client of the plurality of mobile clients that indicates the set or sets of data needed by each respective client, and maintaining a data structure for the plurality of clients that tracks the set or sets of data previously received by each respective client.

17. The one or more computer storage devices of claim 15 having further computer-executable instructions stored thereon, which in response to execution by the computer, cause the computer to perform further steps comprising:

receiving information from a server, the information including traffic-related data intended for vehicular recipients.

18. The one or more computer storage devices of claim 15 having further computer-executable instructions stored thereon, which in response to execution by the computer, cause the computer to perform further steps comprising:

tracking state information associated with data packets to determine whether each data packet was previously transmitted or is a new data packet that has not yet been transmitted, including changing the state information associated with a data packet in conjunction with transmitting that data packet.