Method and system for establishing cooperative routing in wireless networks

• US 8,964,773 B2
• Filed: 05/17/2013
• Issued: 02/24/2015
• Est. Priority Date: 11/08/2006
• Status: Active Grant

• Current Assignee: Trellisware Technologies, Inc. (ViaSat Incorporated)
• Original Assignee: Trellisware Technologies, Inc. (ViaSat Incorporated)
• Inventors: Brown, Thomas A. III, Blair, Adam M., Johnson, Mark L., Halford, Thomas R.
• Primary Examiner(s): PASIA, REDENTOR M
• Application Number:
  US13/896,763
• Publication Number:
  US 20140161015A1
• Time in Patent Office: 648 Days
• Field of Search: 370/229, 370/235, 370248-249, 370/252, 370/312, 370/366, 370/389, 370/390, 370/392, 370/428, 370/432, 370/471, 709227-228, 709237-239
• US Class Current: 370/432
• CPC Class Codes: H04B 7/2606 Arrangements for base station coverage control, e.g. by using relays in tunnels
• CPC Class Codes: H04L 45/10 Routing in connection-oriented networks, e.g. X.25 or ATM
• CPC Class Codes: H04L 45/122 by minimising distances, e.g. by selecting a route with minimum of number of hops
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04W 16/26 Cell enhancers or enhancement, e.g. for tunnels, building shadow
• CPC Class Codes: H04W 40/22 using selective relaying for reaching a BTS [Base Transceiver Station] or an access point
• CPC Class Codes: H04W 40/28 for reactive routing
• CPC Class Codes: H04W 76/12 Setup of transport tunnels
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks
• CPC Class Codes: H04W 88/04 adapted for relaying to or from another terminal or user

Abstract

A system and method is presented for establishing relayed communications involving (1) sending a request message from a source node to a destination node through a plurality of intermediate nodes, (2) receiving the request message at the destination node, and (3) sending an acceptance message from the destination node to the source node through at least a subset of the intermediate nodes, wherein an intermediate node relays the request or acceptance message by receiving the message and re-transmitting the message, and wherein the intermediate node is capable of receiving the message from more than one other intermediate node.

Claims

1. A method for establishing a barrage relayed communication between a source node and a destination node via a plurality of intermediate nodes, the method comprising:

broadcasting a request message from the source node, wherein the request message comprises a first hop counter;

thereafter

receiving the request message at each of a first subset of the plurality of intermediate nodes;

incrementing the first hop counter at each of the first subset of the plurality of intermediate nodes;

broadcasting the request message from the each of the first subset of the plurality of intermediate nodes;

thereafter

receiving at least one instance of the request message at each of a second subset of the plurality of intermediate nodes;

incrementing the first hop counter at each of the second subset of the plurality of intermediate nodes;

broadcasting the request message from each of the second subset of the plurality of intermediate nodes;

thereafter

receiving at least one instance of the request message at the destination node;

thereafter

broadcasting an acceptance message from the destination node, wherein the acceptance message comprises a second hop counter;

thereafter

receiving the acceptance message at each of a third subset of the plurality of intermediate nodes;

performing a logical operation at each of the third subset of the plurality of intermediate nodes based on the first hop counter and the second hop counter;

incrementing the second hop counter at each of a fourth subset of the plurality of intermediate nodes, the fourth subset of the plurality of intermediate nodes being that portion of the third subset of the plurality of intermediate nodes for which the logical operation is satisfied;

broadcasting the acceptance message from the each of the fourth subset of the plurality of intermediate nodes;

thereafter

receiving at least one instance of the acceptance message at each of a fifth subset of the plurality of intermediate nodes;

performing the logical operation at each of the fifth subset of the plurality of intermediate nodes based on the first hop counter and the second hop counter;

incrementing the second hop counter at each of a sixth subset of the plurality of intermediate nodes, the sixth subset of the plurality of intermediate nodes being that portion of the fifth subset of the plurality of intermediate nodes for which the logical operation is satisfied;

broadcasting the acceptance message from the each of the sixth subset of the plurality of intermediate nodes;

thereafter

receiving at least one instance of the acceptance message at the source node;

thereafter

transmitting a data message between the source node and the destination node via the fourth and sixth subsets of the plurality of intermediate nodes, wherein each of the fourth and sixth subsets of the plurality of intermediate nodes participates in relaying the data message.

2. The method of claim 1, wherein receiving at least one instance of the request message at each of a second subset of the plurality of intermediate nodes comprises:

receiving the at least one instance of the request message at each of one or more subsets of the plurality of intermediate nodes,

incrementing the first hop counter at each of the one or more subsets of the plurality of intermediate nodes, and

broadcasting the request message from each of the one or more subsets of the plurality of intermediate nodes;

wherein receiving at least one instance of the acceptance message at each of a fifth subset of the plurality of intermediate nodes comprises;

receiving the acceptance message at each of the one or more subsets of the plurality of intermediate nodes,

performing the logical operation at each of the one or more subsets of the plurality of intermediate nodes based on the first hop counter and the second hop counter,

incrementing the second hop counter at each of a subset of the one or more subsets of the plurality of intermediate nodes, the subset being that portion of the one or more subsets of the plurality of intermediate nodes for which the logical operation is satisfied, and

broadcasting the acceptance message from the each of the subset of the one or more subsets of the plurality of intermediate nodes.

3. The method of claim 1, wherein the at least one instance of the request message received at the destination node is free of identifying parameters associated with any of the first and second subsets of the plurality of intermediate nodes, and wherein the at least one instance of the acceptance message received at the source node is free of identifying parameters associated with any of the fourth and sixth subsets of the plurality of intermediate nodes.

4. The method of claim 1, wherein the request message and the acceptance message further comprise a route width parameter N that is a non-negative integer.

5. The method of claim 4, wherein the acceptance message further comprises a total hop count.

6. The method of claim 5, wherein increasing the route width parameter N increases a number of nodes of the plurality of intermediate nodes in the fourth and sixth subsets of the plurality of intermediate nodes.

7. The method of claim 5, wherein the logical operation comprises comparing a first sum of the first hop counter and the second hop counter to a second sum of the total hop count and the route width parameter N.

8. The method of claim 7, wherein the first sum does not exceed the second sum for each of the fourth and sixth subsets of the plurality of intermediate nodes that participate in the relaying of the data message between the source node and the destination node.

9. The method of claim 4, wherein the route width parameter N is known by each of the plurality of intermediate nodes prior to the broadcasting of either the request message or the acceptance message.

10. The method of claim 1, wherein the portion of the third and fifth subsets of the plurality of intermediate nodes for which the logical operation is not satisfied comprise buffer nodes.

11. A system for establishing a barrage relayed communication in a network of nodes, the system comprising:

a source node;

a destination node; and

a plurality of intermediate nodes,

wherein the source node is capable of broadcasting a request message that comprises a first hop counter,

wherein a first subset of the plurality of intermediate nodes is capable of receiving the request message, incrementing the first hop counter, and broadcasting the request message,

wherein a second subset of the plurality of intermediate nodes is capable of receiving at least one instance of the request message, incrementing the first hop counter, and broadcasting the request message,

wherein the destination node is capable of receiving the at least one instance of the request message and broadcasting an acceptance message that comprises a second hop counter in response to receiving the at least one instance of the request message,

wherein a third subset of the plurality of intermediate nodes is capable of receiving the acceptance message and performing a logical operation based on the first hop counter and the second hop counter,

wherein a fourth subset of the plurality of intermediate nodes is capable of incrementing the second hop counter and broadcasting the acceptance message, the fourth subset of the plurality of intermediate nodes being that portion of the third subset of the plurality of intermediate nodes for which the logical operation is satisfied,

wherein a fifth subset of the plurality of intermediate nodes is capable of receiving at least one instance of the acceptance message and performing a logical operation based on the first hop counter and the second hop counter,

wherein a sixth subset of the plurality of intermediate nodes is capable of incrementing the second hop counter and broadcasting the acceptance message, the sixth subset of the plurality of intermediate nodes being that portion of the fifth subset of the plurality of intermediate nodes for which the logical operation is satisfied,

wherein the source node is further capable of receiving the at least one instance of the acceptance message and transmitting a data message between the source node and the destination node via the fourth and sixth subsets of the plurality of intermediate nodes after the at least one instance of the acceptance message is received, and wherein each of the fourth and sixth subsets of the plurality of intermediate nodes participates in relaying the data message.

12. The system of claim 11, wherein the at least one instance of the request message received at the destination node is free of identifying parameters associated with any of the first and second subsets of the plurality of intermediate nodes, and wherein the at least one instance of the acceptance message received at the source node is free of identifying parameters associated with any of the fourth and sixth subsets of the plurality of intermediate nodes.

13. The system of claim 11, wherein the request message and the acceptance message further comprise a route width parameter N that is a non-negative integer.

14. The system of claim 13, wherein the acceptance message further comprises a total hop count.

15. The system of claim 14, wherein the logical operation comprises comparing a first sum of the first hop counter and the second hop counter to a second sum of the total hop count and the route width parameter N.

16. The system of claim 15, wherein the first sum does not exceed the second sum for each of the fourth and sixth subsets of the plurality of intermediate nodes that participate in the relaying of the data message between the source node and the destination node.

17. The system of claim 13, wherein increasing the route width parameter N increases a number of the plurality of intermediate nodes in the fourth and sixth subsets of the plurality of intermediate nodes.

18. The system of claim 13, wherein the route width parameter N is known by each of the plurality of intermediate nodes prior to the broadcasting of either the request message or the acceptance message.

19. The system of claim 11, wherein the request message, the acceptance message, and the data message comprise an identifier for the source node and an identifier for the destination node.

20. A system for establishing a barrage relayed communication in a network of nodes, the system comprising:

a source node;

a destination node; and

a plurality of intermediate nodes,

wherein the source node is capable of broadcasting a request message that comprises a first hop counter,

wherein a first subset of the plurality of intermediate nodes is capable of receiving the request message, incrementing the first hop counter, and broadcasting the request message,

wherein the destination node is capable of receiving at least one instance of the request message and broadcasting an acceptance message that comprises a second hop counter in response to receiving the at least one instance of the request message,

wherein a second subset of the plurality of intermediate nodes is capable of receiving the acceptance message and performing a logical operation based on the first hop counter and the second hop counter,

wherein a third subset of the plurality of intermediate nodes is capable of incrementing the second hop counter and broadcasting the acceptance message, the third subset of the plurality of intermediate nodes being that portion of the second subset of the plurality of intermediate nodes for which the logical operation is satisfied,

wherein the source node is further capable of receiving the at least one instance of the acceptance message and transmitting a data message between the source node and the destination node via the third subset of the plurality of intermediate nodes after the at least one instance of the acceptance message is received, and wherein each of the third subset of the plurality of intermediate nodes participates in relaying the data message.