Hybrid ARQ for a wireless Ad-Hoc network and a method for using the same

• US 6,744,766 B2
• Filed: 01/21/2003
• Issued: 06/01/2004
• Est. Priority Date: 06/05/2002
• Status: Active Grant

• Current Assignee: Google Technology Holdings LLC (Alphabet Inc.)
• Original Assignee: MeshNetworks, Inc. (Motorola Solutions, Inc.)
• Inventors: Alapuranen, Pertti O.
• Primary Examiner(s): Patel, Ajit
• Application Number:
  US10/347,403
• Publication Number:
  US 20040010736A1
• Time in Patent Office: 497 Days
• Field of Search: 370/351-356, 370/389, 370/392, 370/394, 370/400, 370/401, 370/465, 370/471, 370/474, 370/338, 370/349, 370/328, 714/748, 714/749, 714/758, 714/751
• US Class Current: 370/394
• CPC Class Codes: H04L 1/1628 List acknowledgements, i.e. the acknowledgement message consisting of a list of identifiers, e.g. of sequence numbers H04L1/1614 takes precedence
• CPC Class Codes: H04L 1/1816 with retransmission of the same, encoded, message
• CPC Class Codes: H04L 1/1819 with retransmission of additional or different redundancy
• CPC Class Codes: H04L 1/1867 Arrangements specially adapted for the transmitter end
• CPC Class Codes: H04L 1/189 Transmission or retransmission of more than one copy of a message

Abstract

A system and method for data transmission incorporating a hybrid automatic repeat request (ARQ) function at each node in an ad-hoc network. Each node is configured to calculate an optimum segment size for transmission and thereafter executes the ARQ function to transmit and receive data segments with forward error correction and error detection coding. The coding allows the node to detect and locate errors within received segments and to provide an acknowledgement only after all segments are correctly received. A negative acknowledgement from the receiving node states the location of failed segments, and only failed segments are then retransmitted. The failed segments can be retransmitted in their original location and in other segment locations which contained segments that did not fail, thus reducing maximum time to successfully deliver the segments.

Claims

1. A method for data transmission using a hybrid automatic repeat request (ARQ) function for identifying and requesting retransmission of data frames received with a detected error in an ad-hoc communications network, said network including a plurality of nodes being adapted to transmit and receive signals to and from other nodes in said network, the method comprising:

dividing transmission data into a first number of segments and attaching a forward error correction and error detection code to each segment;

transmitting said first number of segments sequentially from a first node of said plurality to at least a second node of said plurality;

evaluating said first number of segments to detect and locate up to all errors present in each segment of said first number of segments, and when at least one error is detected and located, to return a negative acknowledgement (NACK) and retransmission request signal to said first node, said negative acknowledgement including said location of said at least one error;

creating a second number of segments in response to said retransmission request signal including said each segment of said first number of segments having said at least one error detected and located at said second node, and attaching at least one forward error correction and error detection code to each said segment; and

transmitting said second number of segments sequentially from said first node to said second node multiple times per media access control (MAC) transaction.

2. A method as claimed in claim 1, further comprising:

returning an acknowledgement (ACK) signal to said first node when during said evaluating, no error is detected and located.

3. A method as claimed in claim 1, wherein:

said transmission data includes a media access control protocol data unit (MPDU).

4. A method as claimed in claim 3, wherein said dividing includes:

dividing a length of said media access control protocol data unit by a system constant to produce a maximum segment size; and

calculating said first number of segments based on said maximum segment size.

5. A method as claimed in claim 4, wherein:

said dividing is based on said network specific constant that is known by each node of said plurality.

6. A method as claimed in claim 4, wherein:

said calculating said first number of segments establishes segments of equal size.

7. A method as claimed in claim 4, wherein:

said calculating said first number of segments establishes at least one segment that is shorter than a remaining number of segments.

8. A method as claimed in claim 3, wherein each segment of said first number of segments includes a segment number that is sequential within said media access control protocol data unit.

9. A method as claimed in claim 1, further comprising:

attaching a parity code to each segment of said first number of segments before transmitting said first number of segments; and

wherein said evaluating includes;

verifying the accuracy of said each segment based on said parity code; and

discarding segments which fail said accuracy verification at said second node.

10. A method as claimed in claim 1, wherein said transmitting said first number of segments comprises:

transmitting said first number of segments as a physical layer packet from said first node to said second node of said plurality, said packet information identifying a length of said packet.

11. A method as claimed in claim 1, wherein said transmitting said second number of segments comprises:

transmitting said second number of segments wherein at least one segment is located in a sequential position equal to a sequential position that said at least one segment occupied in said first number of segments.

12. A method as claimed in claim 1, wherein said transmitting said second number of segments comprises:

transmitting said second number of segments wherein at least one segment is located in a sequential position equal to a position that a segment not requiring retransmission occupied in said first number of segments.

13. A method as claimed in claim 1, wherein said forward error correction includes Viterbi encoding.

14. A method as claimed in claim 1, wherein said error detection code includes a cyclic redundancy check (CRC).

15. A system for data transmission using a hybrid automatic repeat request (ARQ) function for identifying and requesting retransmission of data frames received with a detected error in an ad-hoc communications network, said network including a plurality of nodes being adapted to transmit and receive signals to and from other nodes in said network, the system comprising:

a first node, adapted to divide transmission data into a first number of segments and to attach a forward error correction and error detection code to each segment;

said first node being further adapted to transmit said first number of segments sequentially from said first node of said plurality to at least a second node of said plurality;

a second node, adapted to evaluate said first number of segments to detect and locate up to all errors present in each segment of said first number of segments, and when at least one error is detected and located, to return a negative acknowledgement (NACK) and retransmission request signal to said first node, said negative acknowledgement including said location of said at least one error;

said first node being further adapted to create a second number of segments in response to said retransmission request signal including said each segment of said first number of segments having said at least one error detected and located at said second node, and to attach at least one forward error correction and error detection code to each said segment; and

said first node being further adapted to transmit said second number of segments sequentially from said first node to said second node multiple times per media access control (MAC) transaction.

16. A system as claimed in claim 15, wherein:

said second node is adapted to return an acknowledgement (ACK) signal to said first node when during said evaluating, no error is detected and located.

17. A system as claimed in claim 15, wherein:

said transmission data includes a media access control protocol data unit (MPDU).

18. A system as claimed in claim 17, wherein:

said first node is adapted to divide a length of said media access control protocol data unit by a system constant to produce a maximum segment size; and

said first node being further adapted to calculate said first number of segments based on said maximum segment size.

19. A system as claimed in claim 18, wherein:

said network specific constant is known by each node of said plurality.

20. A system as claimed in claim 18, wherein:

said first number of segments includes segments of equal size.

21. A system as claimed in claim 18, wherein:

said first number of segments includes at least one segment that is shorter than a remaining number of segments.

22. A system as claimed in claim 17, wherein:

each segment of said first number of segments includes a segment number that is sequential within said media access control protocol data unit.

23. A system as claimed in claim 15, wherein:

said first node is adapted to attach a parity code to each segment of said first number of segments before transmitting said first number of segments;

said second node is adapted to evaluate said first number of segments by verifying the accuracy of said each segment based on said parity code; and

said second node being further adapted to discard segments which fail said accuracy verification.

24. A system as claimed in claim 15, wherein:

said first node is adapted to transmit said first number of segments as a physical layer packet from said first node to said second node of said plurality, said packet information identifying a length of said packet.

25. A system as claimed in claim 15, wherein:

said first node is adapted to transmit said second number of segments wherein at least one segment is located in a sequential position equal to a sequential position that said at least one segment occupied in said first number of segments.

26. A system as claimed in claim 15, wherein:

said first node is adapted to transmit said second number of segments wherein at least one segment is located in a sequential position equal to a position that a segment not requiring retransmission occupied in said first number of segments.

27. A system as claimed in claim 15, wherein said forward error correction includes Viterbi encoding.

28. A system as claimed in claim 15, wherein said error detection code includes a cyclic redundancy check (CRC).

29. A computer-readable medium of instructions, adapted to control data transmission using a hybrid automatic repeat request (ARQ) function for identifying and requesting retransmission of data frames received with a detected error in an ad-hoc communications network, said network including a plurality of nodes being adapted to transmit and receive signals to and from other nodes in said network, the instructions comprising:

a first set of instructions, adapted to control a first node of said plurality to divide transmission data into a first number of segments, and attach a forward error correction and error detection code to each segment and to transmit said first number of segments sequentially to at least a second node of said plurality;

a second set of instructions, adapted to control said second node to evaluate said first number of segments to detect and locate up to all errors present in each segment of said first number of segments, and when at least one error is detected and located, to return a negative acknowledgement (NACK) and retransmission request signal to said first node, said negative acknowledgement including said location of said at least one error;

a third set of instructions, adapted to control said first node to create a second number of segments in response to said retransmission request signal including said each segment of said first number of segments having said at least one error detected and located at said second node, and attach at least one forward error correction and error detection code to each said segment, and to transmit said second number of segments sequentially from said first node to said second node multiple times per media access control (MAC) transaction.

30. A computer-readable medium of instructions as claimed in claim 29, wherein:

said second set of instructions is adapted to return an acknowledgement (ACK) signal to said first node when during said evaluating, no error is detected and located.

31. A computer-readable medium of instructions as claimed in claim 29, wherein:

said transmission data includes a media access control protocol data unit (MPDU).

32. A computer-readable medium of instructions as claimed in claim 31, wherein:

said first set of instructions is adapted to divide a length of said media access control protocol data unit by a system constant to produce a maximum segment size and calculate said first number of segments based on said maximum segment size.

33. A computer-readable medium of instructions as claimed in claim 32, wherein:

said first set of instructions is adapted to divide said media access control protocol data unit based on said network specific constant that is known by each node of said plurality.

34. A computer-readable medium of instructions as claimed in claim 32, wherein:

said first set of instructions is adapted to calculate said first number of segments of equal size.

35. A computer-readable medium of instructions as claimed in claim 32, wherein:

said first set of instructions is adapted to calculate at least one segment that is shorter than a remaining number of segments.

36. A computer-readable medium of instructions as claimed in claim 31, wherein:

said first set of instructions is adapted to assign each segment of said first number of segments a segment number that is sequential within said media access control protocol data unit.

37. A computer-readable medium of instructions as claimed in claim 29, further comprising:

said first set of instructions adapted to attach a parity code to each segment of said first number of segments before transmitting said first number of segments;

said second set of instruction adapted to evaluate said first number of segments by verifying the accuracy of said each segment based on said parity code; and

said second set of instruction being further adapted to discard segments which fail said accuracy verification at said second node.

38. A computer-readable medium of instructions as claimed in claim 29, wherein:

said first set of instructions is adapted to transmit said first number of segments as a physical layer packet from said first node to said second node of said plurality, said packet information identifying a length of said packet.

39. A computer-readable medium of instructions as claimed in claim 29, wherein:

said third set of instructions is adapted to transmit said second number of segments wherein at least one segment is located in a sequential position equal to a sequential position that said at least one segment occupied in said first number of segments.

40. A computer-readable medium of instructions as claimed in claim 29, wherein:

said third set of instructions is adapted to transmit said second number of segments wherein at least one segment is located in a sequential position equal to a position that a segment not requiring retransmission occupied in said first number of segments.