AD-HOC NETWORK ROUTING PROTOCOL INCLUDING THE USE OF FORWARD AND REVERSE MULTI-POINT RELAY (MPR) SPANNING TREE ROUTES

• US 20080247335A1
• Filed: 04/05/2007
• Published: 10/09/2008
• Est. Priority Date: 04/05/2007
• Status: Active Grant

• Current Assignee: Stingray IP Solutions LLC (Acacia Research Corporation)
• Original Assignee: Harris Corporation (L3Harris Technologies, Inc.)
• Inventors: Rudnick, William Michael
• Granted Patent: US 7,561,024 B2
• Time in Patent Office: Days
• US Class Current: 370/256
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04W 40/30 for proactive routing

Abstract

A method of operating an ad-hoc network having a plurality of wireless nodes includes operating the wireless nodes using a routing protocol, such as OLSR, so that the wireless nodes store forward multi-point relay (MPR) spanning tree routes and reverse MPR spanning tree routes. A first wireless node communicates with a second wireless node using a reverse MPR spanning tree route. The method further includes determining whether the reverse MPR spanning tree route has become unavailable between the first and second wireless nodes and that no other reverse MPR spanning tree route has yet become available, and, if so, using at least portions of a forward MPR spanning tree route for communication between the first and second wireless nodes. The symmetric OLSR approach may be effective in avoiding unnecessary route drops caused by the interaction between distribution-of-topology-change-information conditions and exclusively routing via the destination node'"'"'s reverse-MPR-spanning tree.

Claims

1. A method of operating an ad-hoc network including a plurality of wireless nodes, the method comprising:

operating the wireless nodes using a routing protocol wherein the wireless nodes store forward multi-point relay (MPR) spanning tree routes and reverse MPR spanning tree routes, and wherein a first wireless node communicates with a second wireless node using a reverse MPR spanning tree route; and

determining whether the reverse MPR spanning tree route has become unavailable between the first and second wireless nodes and that no other reverse MPR spanning tree route has yet become available, and, if so, using at least portions of a forward MPR spanning tree route for communication between the first and second wireless nodes.

2. The method according to claim 1 wherein storing forward MPR spanning tree routes and reverse MPR spanning tree routes comprises adding routes to one-hop neighbor nodes to a route table.

3. The method according to claim 2 wherein storing forward MPR spanning tree routes and reverse MPR spanning tree routes further comprises selecting one-hop neighbor nodes as MPRs to retransmit messages to two-hop neighbor nodes.

4. The method according to claim 3 wherein storing forward MPR spanning tree routes and reverse MPR spanning tree routes further comprises adding new routes to the route table based upon symmetric use of MPR-to-new-destination-node links.

5. The method according to claim 1 wherein the wireless routing protocol comprises an optimized link state routing (OLSR) protocol.

6. A method of operating an ad-hoc network including a plurality of wireless nodes, the method comprising:

operating the wireless nodes using an optimized link state routing (OLSR) protocol wherein the wireless nodes store forward multi-point relay (MPR) spanning tree routes and reverse MPR spanning tree routes by adding new routes to a route table based upon symmetric use of MPR-to-new-destination-node links, and wherein a first wireless node communicates with a second wireless node using a reverse MPR spanning tree route; and

determining whether the reverse MPR spanning tree route has become unavailable between the first and second wireless nodes, and, if so, using at least portions of a forward MPR spanning tree route for communication between the first and second wireless nodes.

7. The method according to claim 6 wherein adding new routes comprises each wireless node adding routes to one-hop neighbor nodes to the route table.

8. The method according to claim 7 wherein adding new routes further comprises each wireless node selecting one-hop neighbor nodes as MPRs to retransmit messages to two-hop neighbor nodes.

9. An ad-hoc network comprising:

a plurality of wireless nodes, each wireless node comprising a controller and a wireless communications device cooperating therewith to

operate the wireless node using a routing protocol including storing forward multi-point relay (MPR) spanning tree routes and reverse MPR spanning tree routes, and to communicate with the other wireless nodes using reverse MPR spanning tree routes, and

determine whether a respective reverse MPR spanning tree route to another one of the plurality of wireless nodes has become unavailable, and, if so, using at least portions of a forward MPR spanning tree route for communication to such wireless node.

10. The ad-hoc network according to claim 9 wherein the controller and wireless communications device cooperate to add routes to one-hop neighbor nodes to a route table.

11. The ad-hoc network according to claim 10 wherein the controller and wireless communications device further cooperate to select one-hop neighbor nodes as MPRs to retransmit messages to two-hop neighbor nodes.

12. The ad-hoc network according to claim 11 wherein the controller and wireless communications device further cooperate to add new routes to the route table based upon symmetric use of MPR-to-new-destination-node links.

13. The ad-hoc network according to claim 9 wherein the wireless routing protocol comprises an optimized link state routing (OLSR) protocol.

14. A wireless node for operation in a plurality of mobile nodes within an ad-hoc network, the wireless node comprising:

a controller and a wireless communications device cooperating therewith to

operate the wireless node using a routing protocol including storing forward multi-point relay (MPR) spanning tree routes and reverse MPR spanning tree routes, and to communicate with the other wireless nodes using reverse MPR spanning tree routes, and

determining whether a respective reverse MPR spanning tree route to another one of the plurality of wireless nodes has become unavailable, and, if so, using at least portions of a forward MPR spanning tree route for communication to such wireless node.

15. The wireless node according to claim 14 wherein the controller and wireless communications device cooperate to add routes to one-hop neighbor nodes to a route table.

16. The wireless node according to claim 15 wherein the controller and wireless communications device further cooperate to select one-hop neighbor nodes as MPRs to retransmit messages to two-hop neighbor nodes.

17. The wireless node according to claim 16 wherein the controller and wireless communications device further cooperate to add new routes to the route table based upon symmetric use of MPR-to-new-destination-node links.

18. The wireless node according to claim 14 wherein the wireless routing protocol comprises an optimized link state routing (OLSR) protocol.