Packet forwarding in multi-radio multi-hop wireless networks

• US 8,077,658 B2
• Filed: 10/01/2007
• Issued: 12/13/2011
• Est. Priority Date: 10/01/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Wu, Yunnan
• Primary Examiner(s): ABELSON, RONALD B
• Application Number:
  US11/906,297
• Publication Number:
  US 20090086664A1
• Time in Patent Office: 1,534 Days
• Field of Search: 370/328, 370/389, 370/392, 370412-418
• US Class Current: 370/328
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 72/569 of the traffic information
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

A packet forwarding technique is presented that forwards data packets through a multi-hop wireless network employing multi-radio nodes. In each multi-radio node, an output buffer is shared among the radios. Outgoing packets are stored in this buffer. Whenever there is a transmission opportunity on the radios sharing the output buffer, the node examines the buffer and searches for packets that are scheduled to be transmitted to a neighboring node having an open communication link with the transmitting node. The packet in the discovered group that has the highest transmission priority is then transmitted to its next scheduled node.

Claims

1. A computer-implemented process for transmitting a combined data packet from a multi-radio node to another node in a multi-hop wireless network, comprising using a computer to perform the following process actions for each multi-radio node in the network:

storing data packets in a buffer shared by at least two radios of the multi-radio node, wherein each data packet is being forwarded from the multi-radio node to one of a plurality of neighboring nodes of the wireless network that are within communication range of the multi-radio node, and wherein each data packet has a prescribed transmission priority;

identifying communication links that are available to transmit a data packet between a radio of the multi-radio node sharing said buffer and at least some of said neighboring nodes;

identifying a data packet stored in the shared buffer that is scheduled for transmission to a neighboring node associated with one of the identified communication links and which has the highest priority among the data packets scheduled for transmission to a neighboring node associated with the identified communication links;

mixing the identified data packet with at least one other data packet stored in the shared buffer to create the combined data packet, wherein each of the at least one other data packets is a packet scheduled for forwarding to a neighboring node associated with the identified communication links, and wherein said mixing is performed whenever a neighboring node associated with the identified communication links that is to receive the combined data packet has information necessary to extract the data packet or packets mixed into the combined data packet, or will eventually also receive the information necessary to extract the data packet or packets mixed into the combined data packet; and

transmitting the combined data packet to said neighboring network nodes associated with the identified communication links.

2. The process of claim 1, wherein the process action of mixing the identified data packet with at least one other data packet stored in the shared buffer to create the combined data packet, comprises combining the data packets using an exclusive OR (XOR) method.

3. The process of claim 1, wherein the process action of transmitting the combined data packet to said neighboring network nodes associated with the identified communication links, comprises an action of broadcasting the combined data packet to all neighboring network nodes within range.

4. The process of claim 1, wherein the process action of transmitting the combined data packet to said neighboring network nodes associated with the identified communication links, comprises an action of unicasting the combined data packet to said nodes via the identified communication links.

5. A computer-readable storage medium having computer-executable instructions stored thereon for transmitting a combined data packet from a multi-radio node to another node in a multi-hop wireless network, said computer-executable instructions comprising for each multi-radio node in the network:

storing data packets in a buffer shared by at least two radios of the multi-radio node, wherein each data packet is being forwarded from the multi-radio node to one of a plurality of neighboring nodes of the wireless network that are within communication range of the multi-radio node, and wherein each data packet has a prescribed transmission priority;

identifying communication links that are available to transmit a data packet between a radio of the multi-radio node sharing said buffer and at least some of said neighboring nodes;

identifying a data packet stored in the shared buffer that is scheduled for transmission to a neighboring node associated with one of the identified communication links and which has the highest priority among the data packets scheduled for transmission to a neighboring node associated with the identified communication links;

mixing the identified data packet with at least one other data packet stored in the shared buffer to create the combined data packet, wherein each of the at least one other data packets is a packet scheduled for forwarding to a neighboring node associated with the identified communication links, and wherein said mixing is performed whenever a neighboring node associated with the identified communication links that is to receive the combined data packet has information necessary to extract the data packet or packets mixed into the combined data packet, or will eventually also receive the information necessary to extract the data packet or packets mixed into the combined data packet; and

transmitting the combined data packet to said neighboring network nodes associated with the identified communication links.