초록 ▼

Network coding and multiple packet reception (MPR) are used together to improve message dissemination speed in a wireless network using half duplex communication. In at least one embodiment, MPR is used to initially distribute data packets from a number of source nodes in the network to the other no

Network coding and multiple packet reception (MPR) are used together to improve message dissemination speed in a wireless network using half duplex communication. In at least one embodiment, MPR is used to initially distribute data packets from a number of source nodes in the network to the other nodes of the network. Network coding techniques may then be used to perform backfilling within the network to supply data packets to the source nodes that were originally missed due to the half duplex constraint.

대표청구항 ▼

1. A method for distributing a plurality of data packets to nodes in a half duplex wireless network from source nodes within the wireless network, wherein the data packets are transmitted in time slots within the wireless network, the method comprising: selecting a group of m or fewer nodes in each

1. A method for distributing a plurality of data packets to nodes in a half duplex wireless network from source nodes within the wireless network, wherein the data packets are transmitted in time slots within the wireless network, the method comprising: selecting a group of m or fewer nodes in each time slot, wherein m is a multi-packet reception (MPR) capability of the wireless network, to act as source nodes during that time slot;transmitting original data packets from the source nodes during first time slots until all of the data packets in the plurality of data packets have been transmitted, wherein transmitting the original data packets includes transmitting the data packets for one group per time slot and in an uncoded or coded form;transmitting one or more coded packets from one or more non-source nodes in the wireless network during at least one second time slot, the one or more coded packets each including a linear combination of the original data packets transmitted by the source nodes during the first time slots; andreceiving at least one coded packet of the one or more coded packets transmitted from the one or more non-source nodes during the at least one second time slot at a first source node and using the at least one coded packet to recover at least one of the original data packets at the first source node that previously went unreceived because the first source node was transmitting when the at least one original data packet was originally transmitted by another source node of the source nodes during one of the first time slots. 2. The method of claim 1, wherein: the one or more coded packets transmitted from non-source nodes each include a linear combination of all of the original data packets transmitted during the first time slots. 3. The method of claim 2, wherein: the one or more coded packets transmitted from non-source nodes each include a linear combination of all of the original data packets transmitted during the first time slots, weighted with a plurality of randomly generated coefficients. 4. The method of claim 1, wherein: selecting a group of nodes at each time slot includes dividing the source nodes into groups of m nodes by dividing the source nodes into (Jm)  distinct groups, where J is a quantity of the source nodes and (xy)  is the combination function, where x is a total number of the source nodes and y is a number of the source nodes in each of the (Jm)  distinct groups. 5. The method of claim 4, wherein: transmitting the original data packets from the source nodes during first time slots includes transmitting the original data packets by cycling through the (Jm)  distinct groups until all of the data packets in the plurality of data packets have been transmitted. 6. The method of claim 1, wherein: selecting a group of source nodes includes dividing the source nodes into groups based, at least in part, on priority. 7. The method of claim 1, wherein; selecting a group of source nodes includes dividing the source nodes into groups based, at least in part, on a number of data packets to be transmitted from each source node. 8. The method of claim 1, wherein: each source node within the wireless network includes an equal number of data packets to be transmitted. 9. The method of claim 1, wherein: transmitting the one or more coded packets from the one or more non-source nodes in the wireless network during the at least one second time slot includes transmitting one coded packet from each of multiple non-source nodes during a single time slot of the at least one second time slot. 10. The method of claim 1, wherein: transmitting the one or more coded packets from the one or more non-source nodes in the wireless network during the at least one second time slot includes transmitting one coded packet from each of m or fewer non-source nodes during a single time slot of the at least one second time slot. 11. The method of claim 1, wherein: transmitting the one or more coded packets from the one or more non-source nodes in the wireless network during the at least one second time slot includes transmitting a total number of coded packets that is at least as large as a maximum number of missing data packets required by a selected source node of the source nodes. 12. The method of claim 1, wherein: the wireless network is a wireless mesh network. 13. The method of claim 1, wherein the groups of nodes selected as the source nodes in each time slot can include the same node in more than one group. 14. The method of claim 1, wherein the wireless network includes a plurality of non-source nodes and receiving at least one coded packet includes receiving a plurality of coded packets from two or more of the plurality of the non-source nodes during a single time slot of the second time slot. 15. A wireless network comprising: a plurality of wireless nodes, each node in the plurality of wireless nodes including at least one wireless transceiver to support half duplex wireless communication with other wireless nodes in the plurality of nodes, wherein, at a particular point in time, some of the plurality of wireless nodes may be source nodes having data packets ready for distribution to the other nodes in the wireless network and the remainder of the plurality of wireless nodes may be non-source nodes; andone or more processors to: select a group of m or fewer source nodes at each time slot, wherein m is a multi-packet reception (MPR) capability of the wireless network;cause data packets to be transmitted from the source nodes during first time slots until all data packets have been transmitted, wherein the data packets are transmitted one group per time slot; andcause one or more coded packets to be transmitted from one or more of the non-source nodes in the wireless network during at least one second time slot, the one or more coded packets each including a linear combination of data packets transmitted during the first time slots;wherein a first source node in the plurality of wireless nodes is configured to receive at least one coded packet of the one or more coded packets transmitted from the one or more non-source nodes during the at least one second time slot and use the at least one coded packet to recover at least one original data packet at the first source node that previously went unreceived because the first source node was transmitting when the at least one original data packet was originally transmitted by another source node of the source nodes during one of the first time slots. 16. The wireless network of claim 15, wherein: the one or more coded packets each include a linear combination of all of the data packets transmitted during the first time slots. 17. The wireless network of claim 15, wherein: the one or more coded packets each include a linear combination of all of the data packets transmitted during the first time slots weighted with a plurality of randomly generated coefficients. 18. The wireless network of claim 15, wherein: the one or more processors are configured to divide the source nodes into (Jm)  distinct groups, where J is a quantity of the source nodes and (xy)  is the combination function, where x is a total number of the source nodes and y is a number of the source nodes in each of the (Jm)  distinct groups. 19. The wireless network of claim 18, wherein: the one or more processors are configured to cause the data packets to be transmitted from the source nodes during the first time slots by cycling though the (Jm)  distinct groups until all of the data packets in the plurality of data packets have been transmitted. 20. The wireless network of claim 15, wherein: the one or more processors are configured to select each group of source nodes based, at least in part, on priority. 21. The wireless network of claim 15, wherein: the one or more processors are configured to select each group of source nodes based, at least in part, on a number of the data packets to be transmitted from each source node. 22. The wireless network of claim 15, wherein: the one or more processors are configured to cause one coded packet to be transmitted from each of multiple non-source nodes during the at least one second time slot. 23. The wireless network of claim 15, wherein: the one or more processors are configured to cause one coded packet to be transmitted from each of m or fewer non-source nodes during the at least one second time slot. 24. The wireless network of claim 15, wherein: the one or more processors are configured to cause a total number of coded packets to he transmitted from the non-source nodes that is at least as large as a highest number of missing data packets required by a selected source node of the source nodes. 25. The wireless network of claim 15, wherein: the wireless network is a wireless mesh network. 26. The wireless network of claim 15, wherein: the one or more processors are located at a single network location. 27. The wireless network of claim 15, wherein: the one or more processors include multiple processors distributed across multiple network locations. 28. A method for use in a wireless network that supports multi-packet reception (MPR), network coding, and half duplex communication, the method comprising: transmitting a data packet from a first source node of a plurality of source nodes during a time slot within which at least one other source node of the plurality of source nodes transmits at least one other data packet, wherein the at least one other data packet is not received at the first source node because of the half duplex constraint and the source nodes are divided into groups based on priority;receiving at least one coded packet transmitted by at least one non-source node, which is a linear combination of data packets previously transmitted by one or more of the source nodes, during one or more later time slots at the first source node; andusing the at least one coded packet and previously received original data packets at the first source node to recover the at least one other data packet that previously went unreceived due to the half duplex constraint. 29. The method of claim 28, wherein: the at least one coded packet includes a first coded packet comprising a linear combination of the original data packets previously transmitted by one or more of the source nodes during a common data distribution operation. 30. The method of claim 28, wherein: receiving at least one coded packet includes receiving m coded packets during a time slot, where m is the MPR capability of the wireless network. 31. A device for use in a wireless network that supports network coding and multi-packet reception (MPR), wherein data is transmitted in time slots within the wireless network, the device comprising: at least one wireless transceiver having MPR capability, the at least one wireless transceiver supporting half-duplex wireless communication;a network coding module to perform network coding and/or network decoding for the wireless node device; anda controller:to receive, via the at least one wireless transceiver, at least one coded packet from one or more non-source nodes in the wireless network during a data distribution operation and to use the at least one coded packet, along with original data packets that were transmitted by at least one source node of a group of source nodes in the wireless network and previously received during the data distribution operation; and to recover one or more data packets that previously went unreceived because the at least one wireless transceiver was transmitting during a time slot when another source node of the source nodes was transmitting the one or more data packets; wherein the data distribution operation includes a number of the source nodes transmitting the original data packets according to the source node groups during first time slots and at least one of the one or more non-source node transmitting the at least one coded packet during at least one second time slot after the first time slots, the at least one coded packet including a linear combination of the original data packets transmitted during the first time slots. 32. The device of claim 31, wherein: the at least one wireless transceiver includes an MPR module that is configured to support heterogeneous MPR, the at least one wireless transceiver having at least two wireless receivers following different wireless standards. 33. The device of claim 31, wherein: the at least one coded packet includes a linear combination of all of the original data packets transmitted by the source nodes during the data distribution operation.