Efficient Transmission Of Information To Multiple Nodes Using Cooperative Feedback Requests

Abstract

A system and method to reduce the number of data transmissions between nodes in a network is described. In one embodiment, a system and method for reducing the amount of ACK and NAK traffic in a network is described.

What is claimed is: 
     
         1 . In a network comprising a plurality of nodes, a method of transmitting information from a source node to one or more other nodes in the network, the one or more other nodes comprising at least one destination node, wherein the information is in the form of a plurality of coded packets, the method comprising:
 transmitting coded packets from the source node to the one or more other nodes in the network;   receiving a number of coded packets sufficient to decode the information at one or more of the other nodes;   at a first one of the other nodes, determining with a desired degree of probability if each of the destination nodes has received a sufficient number of coded packets to decode the information based upon one or more of a probabilistic channel model, locations of the destination nodes, transmissions heard by the first one of the other nodes or knowledge of coded packets transmitted by the first one of the other nodes to nodes other than the first one of the other nodes; and   sending a cooperative feedback request from the first one of the other nodes to one or more of the nodes other than the first one of the other nodes based upon the determining at the first one of other nodes.   
     
     
         2 . The method of  claim 1  further comprising:
 in response to one or more of the nodes other than the first one of the other nodes receiving the cooperative feedback request from the first one of the other nodes and determining with the desired degree of probability that itself and/or some other node did not receive a sufficient number of coded packets, sending, from a second one of the other nodes to one or more of the other nodes in the network, a negative acknowledgement (NAK) on behalf of the node or nodes believed to have not received a sufficient number of coded packets. 
 
     
     
         3 . The method of  claim 2  wherein the determining with the desired degree of probability that itself and/or some other node did not receive a sufficient number of coded packets is based upon explicit and implicit knowledge within the node sending the NAK. 
     
     
         4 . The method of  claim 2  further comprising: in response to one or more of the other nodes receiving the NAK, retransmitting the coded packets from a first one of the one or more other nodes receiving the NAK to one or more of the nodes other than the first one of the other nodes;
 or transmitting newly coded packets from the first one of the one or more other nodes receiving the NAK to one or more of the nodes other than the first one of the other nodes. 
 
     
     
         5 . The method of  claim 4  wherein the first one of the one or more other nodes receiving the NAK is not the source node and is not a last hop node that transmitted the coded packets to the node or nodes believed to have not received a sufficient number of coded packets. 
     
     
         6 . The method of  claim 1  further comprising:
 in response to one or more of the nodes other than the first one of the other nodes receiving the cooperative feedback request from the first one of the other nodes and determining with the desired degree of probability that itself and/or some other node has received a sufficient number of coded packets, sending, from a second one of the other nodes to one or more of the other nodes in the network, an acknowledgement message (ACK) on behalf of the node or nodes believed to have received the sufficient number of coded packets, wherein sending, from the second one of the other nodes to one or more of the other nodes in the network, an acknowledgement message (ACK) on behalf of the node or nodes believed to have received the sufficient number of coded packets, comprises: 
 determining, in the second one of the other nodes, whether to send the ACK based upon at least location of the other nodes; and 
 sending, from the second one of the other nodes to one or more of the other nodes in the network, the ACK on behalf of the node or nodes believed to have not received a sufficient number of coded packets based upon the determining in the second one of the other nodes. 
 
     
     
         7 . The method of  claim 2  wherein sending, from the second one of the other nodes to one or more of the other nodes in the network, a negative acknowledgement (NAK) on behalf of the node or nodes believed to have not received a sufficient number of coded packets, comprises:
 determining, in the second one of the other nodes, whether to send the NAK based upon at least location of the other nodes; and 
 sending, from the second one of the other nodes to one or more of the other nodes in the network, the NAK on behalf of the node or nodes believed to have not received a sufficient number of coded packets based upon the determining in the second one of the other nodes. 
 
     
     
         8 . The method of  claim 7  wherein determining, in the second one of the other nodes, whether to send the NAK based upon at least location of nodes, further comprises:
 determining which node of the other nodes should transmit newly coded packets or re-transmit coded packets. 
 
     
     
         9 . The method of  claim 8  wherein determining which node of the other nodes should transmit newly coded packets comprises using node locations to determine which node of the other nodes should transmit the newly coded packets. 
     
     
         10 . A method of determining when to send a cooperative feedback request in a network comprising a plurality of nodes, the plurality of nodes including a source node and one or more other nodes, the one or more other nodes including at least one destination node, the source node transmitting a message in a form of a plurality of coded packets to the one or more other nodes in the network, the method comprising:
 at a first one of the other nodes, determining with a desired degree of probability if each of the destination nodes has received a sufficient number of coded packets to decode the message using information which has been overheard from other nodes;   using information which has been overheard from other nodes in combination with node location information; and using probabilistic channel knowledge including using a probability channel model; and   determining when to send a cooperative feedback request from the first one of the other nodes to one or more of the nodes other than the first one of the other nodes based upon the determining at the first one of the other nodes.   
     
     
         11 . The method of  claim 10  further comprising using piggybacked ACKs or NAKs. 
     
     
         12 . In a network having a source node and one or more other nodes, the one or more other nodes including a plurality of destination nodes, a method for acknowledging a broadcast message, the method comprising:
 for a broadcast message including M information packets, generating a corresponding number of linear coded packets;   transmitting from the source node, the linear coded packets ; and   upon reception of the linear coded packets at one or more of the destination nodes, determining with a desired degree of probability if one of the destination nodes should send one of an ACK or a NAK for at least one other destination node based upon one or more of information which has been overheard from other nodes, information which has been overheard from other nodes in combination with node location information, and probabilistic channel knowledge in each of the nodes.   
     
     
         13 . The method of  claim 12  further comprising, determining in a first one of the destination nodes how many degrees of freedom are needed to decode the broadcast message. 
     
     
         14 . The method of  claim 13  further comprising:
 transmitting an acknowledgment packet from the first one of the destination nodes to one or more other nodes in the network to convey remaining number of degrees of freedom required at the first one of the destination nodes or at one or more destination nodes other than the first one of the destination nodes to decode all M information packets. 
 
     
     
         15 . The method of  claim 14  further comprising determining a number of linear coded packets needed at the first one of the destination nodes or at one or more destination nodes other than the first one of the destinations nodes based upon one or more channel characteristics and information in the acknowledgement packet. 
     
     
         16 . The method of  claim 13  further comprising:
 transmitting a NAK packet from the first one of the destination nodes to other nodes in the network to indicate that at least one destination node other than the first one of the destination nodes did not receive a sufficient number of linear coded packets to decode the broadcast message.