Scalable unidirectional routing with zone routing protocol extensions for mobile AD-HOC networks

• US 6,990,075 B2
• Filed: 01/18/2001
• Issued: 01/24/2006
• Est. Priority Date: 02/12/2000
• Status: Expired due to Fees

• Current Assignee: HRL Laboratories LLC (The Boeing Co.)
• Original Assignee: HRL Laboratories LLC (The Boeing Co.)
• Inventors: Krishnamurthy, Srikanth, Dao, Son K., Sinha, Prasun
• Primary Examiner(s): Ngo, Ricky
• Assistant Examiner(s): CHANG, RICHARD K
• Application Number:
  US09/764,668
• Publication Number:
  US 20010033556A1
• Time in Patent Office: 1,832 Days
• Field of Search: 370/236, 370/238, 370/329, 370/400, 370/408
• US Class Current: 370/236
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/20 Hop count for routing purposes, e.g. TTL
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/484 using multiple routing trees
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 40/248 Connectivity information update
• CPC Class Codes: H04W 40/26 for hybrid routing by combining proactive and reactive routing
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

The present invention provides a method and apparatus for extending a zone routing protocol. The invention is configured to provide a robust scalable framework for routing data in wireless ad-hoc networks when unidirectional links 210 are present. When the reverse path from a destination node (the tail) of a unidirectional link 210 to the originating node (the head) of the link is beyond a designated length, the invention is configured to revert to an on-demand search mechanism. The on-demand search mechanism recursively attempts to build a path to the destination 206 by recognizing nodes that have a route to the destination.

Claims

1. A method for routing data in wireless ad-hoc networks comprising the steps of:

providing a proactive component;

configured to route messages utilizing an intra zone routing protocol and

providing a reactive component;

configured to route messages utilizing a inter zone routing protocol and

providing a bordercast tree, configured to bordercast to a plurality of border nodes; and

providing at least one query packet comprising data, wherein nodes receiving one or more query packets are configured to provide at least one query response or discard query packet;

wherein the method follows the following additional steps;

i. a first route query is initiated by a first node or a source node and has one destination node;

ii. if there is a path to a destination node in an outbound tree as computed by the proactive component, then that path is the desired path and the intra-zone routing protocol terminates, otherwise;

iii. the source node checks if its bordercast tree is empty;

a. if the bordercast tree is empty go to step viii;

b. if the bordercast tree is not empty go to step iv;

iv. the bordercast tree is stored in the query packet, and is forwarded along the bordercast tree, and at least one intermediate nodes of the bordercast tree (non- border nodes), forward the query packet until it reaches a border node, wherein a plurality of processing steps occur culminating in the sending of a bordercast;

a. after sending the bordercast, there is a pause for a predetermined period of time equal to ENHANCEMENT_—

INTERVAL, during which the source node awaits either a query response or one or more enhancement messages;

v. if a query response to the route query is received, then the route query step is termed complete and the computed route is returned to the first node;

vi. if a query response is not received, then the source node checks if an enhancement message has been received, the ENHANCEMENT_—

INTERVAL having passed since the initiation of the bordercast;

if one or more query enhancement messages were received during the ENHANCEMENT_—

INTERVAL, then one or more alternate destination nodes indicated in the query enhancement message, or messages, are utilized to create an enhanced route query with a alternative set of destinations, wherein other nodes have reported that the alternative destination nodes have routes to the destination node;

the enhanced route query is processed like a first route query;

go to step ii;

vii. if the bordercasting did not result in any enhancement of the route query or in a route, the bordercast tree is presumed incapable of reaching nodes that can enhance the query;

this state is also reached from step ii when the bordercast tree is empty;

in this situation a two-way tree is used to send a request to enhance the query, the source node and the border nodes forward this Query Enhancement Request using the two-way tree just as they would forward a regular query, except that the two-way tree is used for bordercasting, instead of the bordercast tree;

wherein nodes are discovered

viii. after waiting for ENHANCEMENT_—

INTERVAL, the source node checks to see if any responses to the query enhancement request using the two way tree exist, if one or more query enhancement responses are received during the ENHANCEMENT_—

INTERVAL, the resulting one or more destinations indicated in the query enhancement response can be queried for routes to the desired destination, if there is a path to a desired destination node in an outbound tree as computed by the proactive component, then that path is the desired path; and

the protocol terminates;

ix. if there are any responses to the query enhancement request but there is not a path to the desired destination in an outbound tree as computed by the proactive component then go to step iii;

x. if no enhancement message was received then the destination is assumed to be unreachable and the protocol terminates.

2. The method for routing data in wireless ad-hoc networks as set forth in claim 1, wherein in step iv the plurality of processing steps include:

a. receiving incoming query from step iv above;

b. applying at least one query control mechanism to the query;

c. using the criteria from the at least one Query Control Mechanism to drop unnecessary query threads,

i. if all threads are dropped, then go to step viii of claim 1;

d. determining if a path is known to at least one destination and

i. if a path is known notify the sender of the path and route query is complete;

ii. if a path is not known;

e. checking if a path is known from other nodes to at least one destination node;

i. if yes inform sender of alternative destinations;

ii. if not go to step f;

f. bordercasting query

g. returning to step iv a of claim 1.

3. The method as set forth in claim 2 wherein the at least one query control mechanism of step b includes a Query Detection (QD) and an Early Termination (ET) mechanism;

these mechanisms are configured to extract a query identifier and match it with recently cached query identifiers seen by the node;

if the query identifier has been seen before, then the query can be dropped.

4. The method as set forth in claim 2 wherein the notification of a path, to the sender, of step d i is a accomplished by:

a. initiating a response to the query that contains the computed path, only the border nodes, (also referred to as center nodes), traversed by the route query packet are recorded;

the response is sent along a path that traverses the same center nodes;

where each center node has a path to the previous center node, wherein the response is forwarded from one center node to another center node until it reaches the source node, that initiated the query.

5. The method as set forth in claim 2 wherein the checking if a path is known from other nodes to at least one destination node of step e is accomplished by:

a. discovering links using the Intra Zone Routing Protocol;

b. computing inbound trees for each of the destinations being queried;

i. if any such trees exist and can be computed, then the nodes (other than the destination nodes) in these inbound trees denote the alternate destinations.

6. The method as set forth in claim 5 wherein the inbound trees are computed using a mechanism wherein a plurality of node neighbors having a link to the transmitting node are used to construct a graph of destinations;

and for each destination, a shortest path protocol is executed on the graph by considering each destination as a sink node, any shortest path protocol can be used to compute these inbound trees.

7. The method as set forth in claim 6 wherein the shortest path protocol is Dijkstra'"'"'s algorithm.

8. The method for routing data in wireless ad-hoc networks as set forth in claim 1, wherein the maximum number of hops between the first node and the border node is 3.

9. The method for routing data in wireless ad-hoc networks as set forth in claim 1, wherein the number of hops between the first node and the border node is periodically reset.

10. The method for routing data in wireless ad-hoc networks as set forth in claim 1, wherein the number of hops between the first node and the border node is dynamically updated based on a situational awareness protocol.

11. The method for routing data in wireless ad-hoc networks as set forth in claim 1, wherein there is a counter that limits the number of enhancements.

12. The method for routing data in wireless ad-hoc networks as set forth in claim 11, wherein the limit on the counter that limits the number of enhancements is determined by the method for routing data.

13. The method for routing data in wireless ad-hoc networks as set forth in claim 11, wherein there is a counter that limits the number of enhancements to a predetermined number is selected based on memory resources allocated to the method for routing data.

14. The method for routing data in wireless ad-hoc networks as set forth in claim 1, wherein the ENHANCEMENT_—

INTERVAL is variable.

15. The method for routing data in wireless ad-hoc networks as set forth in claim 1, wherein the ENHANCEMENT_—

INTERVAL is varied and the variation is based on the number of nodes adjacent to the source node.

16. The method for routing data in wireless ad-hoc networks as set forth in claim 1, wherein a transmission path is not the same as a return path.

17. The method for routing data in wireless ad-hoc networks as set forth in claim 1, wherein the data packet includes at least one of the following:

a. a set of node neighbors which have a link to the transmitting node;

b. a set of node neighbors with which the transmitting node has a link;

c. any nodes on the outbound tree of the transmitting node;

d. a sequence number;

e. an urgent flag, which provides data concerning link status;

f. a time to live counter which tracks the number of hops up to which the data packet can be forwarded, the time to live counter is initialized to the ZONE_—

RADIUS, and is incremented as the data packet traverses a path.

18. The method for routing data in wireless ad-hoc networks as set forth in claim 17, wherein the nodes on the outbound tree of the transmitting node are computed from the units obtained from other nodes.

19. An apparatus for routing data in wireless ad-hoc networks comprising:

a proactive element, configured to route messages utilizing an intra zone routing protocol; and

a reactive element, configured to route messages utilizing a inter zone routing protocol; and

a bordercast tree element, configured to bordercast to a plurality of border nodes; and

at least one query packet memory element comprising data, wherein nodes receiving one or more query packets are configured to provide at least one query response or discard the query packet;

wherein the apparatus includes;

i. a first means for initiating a route query from a first node or a source node and wherein the route query concerns a route to a destination node;

ii. a central means determines if there is a path to a destination node in an outbound tree, as computed by the proactive element, and, if such a path is found, that path is the desired path; and

the apparatus transmits its message;

otherwise

iii. the source node checks if its bordercast tree is empty;

a. if the bordercast tree is empty go to step viii;

b. if the bordercast tree is not empty go to step iv;

iv. the bordercast tree is stored in the query packet, and is forwarded along the bordercast tree, one or more intermediate nodes of the bordercast tree (non-border nodes), forward the query packet until it reaches a border node, wherein a plurality of processing steps occur culminating in the sending of a bordercast;

a. after sending the bordercast, there is a pause for a predetermined period of time equal to ENHANCEMENT_—

INTERVAL, during which the source node awaits either a query response or one or more enhancement messages;

v. if a query response to the route query is received, then the route query step is termed complete and the computed route is returned to the first node;

vi. if a query response is not received, then the source node checks if an enhancement message has been received, the ENHANCEMENT_—

INTERVAL having passed since the initiation of the bordercast;

if one or more query enhancement messages were received during the ENHANCEMENT_—

INTERVAL, then one or more alternate destination nodes indicated in the query enhancement message, or messages, are utilized to create an enhanced route query with an alternative set of destinations, wherein other nodes have reported that the alternative destination nodes have routes to the destination node;

the enhanced route query is processed like the route query;

by returning to step ii;

vii. if the bordercasting did not result in any enhancement of the route query or in a route, the bordercast tree is incapable of reaching nodes that can enhance the query (assuming no message losses);

this state is also reached from step ii, when the bordercast tree is empty;

in this situation a two-way tree is used to send a request to enhance the query and the source node and the border nodes forward this Query Enhancement Request using the two-way tree just as they would forward a regular query, except that the two-way tree is used for bordercasting, instead of the bordercast tree;

the objective here is to try to discover nodes, which know of paths to the destination node;

viii. after waiting for ENHANCEMENT_—

INTERVAL, the source node checks to see if any responses to the query enhancement request using the two way tree exist;

if one or more query enhancement responses are received during the ENHANCEMENT_—

INTERVAL, the resulting one or more destinations indicated in the query enhancement response can be queried for routes to the desired destination, if there is a path to a desired destination node in an outbound tree as computed by the proactive component then that path is the desired path and the protocol terminates;

ix. if there are any responses to the query enhancement request but there is not a path to the desired destination in an outbound tree as computed by the proactive component then go to step iii;

x. if no enhancement message was received then the destination is assumed to be unreachable and the protocol terminates.

20. The apparatus for routing data in wireless ad-hoc networks as set forth in claim 19, wherein in step iv the plurality of processing steps include:

a. receiving incoming query from step iv above;

b. applying at least one query control mechanism to the query;

c. using the criteria from the at least one Query Control Mechanism to drop unnecessary query threads,

i. if all threads are dropped, then go to step viii of claim 19;

d. determining if a path is known to at least one destination and

i. if a path is known, notify sender of the path and route discovery is complete;

ii. if a path is not known then go to the next step;

e. checking if a path is known from other nodes to at least one destination node;

i. if yes, inform sender of alternative destinations;

ii. if not;

f. bordercasting query

g. returning to step iv a of claim 19.

21. The apparatus as set forth in claim 20 wherein the at least one query control mechanism of step b includes a Query Detection (QD) and an Early Termination (ET) mechanism;

these mechanisms are configured to extract a query identifier and match it with recently cached query identifiers seen by the node;

if the query identifier has been seen before, then the query can be dropped.

22. The apparatus as set forth in claim 20 wherein the notification of a path to the sender, of step d i is accomplished by:

a. initiating a response to the query that contains the computed path, only the border nodes, (also referred to as center nodes), traversed by the route query packet are recorded;

the response is sent along a path that traverses the same center nodes;

where each center node has a path to the previous center node, wherein the response is forwarded from one center node to another center node until it reaches the source node, that initiated the query.

23. The apparatus as set forth in claim 20 wherein the checking if a path is known from other nodes to at least one destination node of step e is accomplished by:

a. discovering links using the Intra Zone Routing Protocol;

b. computing inbound trees for each of the destinations being queried;

i. if any such trees exist and can be computed, then the nodes (other than the destination nodes) in these inbound trees denote the alternate destinations.

24. The apparatus as set forth in claim 23 wherein the inbound trees are computed using a mechanism wherein a plurality of node neighbors having a link to the transmitting node are used to construct a graph of destinations;

and for each destination, a shortest path protocol is executed on the graph by considering each destination as a sink node, any shortest path protocol can be used to compute these inbound trees.

25. The apparatus as set forth in claim 24 wherein the shortest path protocol is Dijkstra'"'"'s algorithm.

26. The apparatus for routing data in wireless ad-hoc networks as set forth in claim 19, wherein the maximum number of hops between the first node and the border node is 3.

27. The apparatus for routing data in wireless ad-hoc networks as set forth in claim 19, wherein the maximum number of hops between the first node and the border node is periodically reset.

28. The apparatus for routing data in wireless ad-hoc networks as set forth in claim 19, wherein the maximum number of hops between the first node and the border node is dynamically updated based on a situational awareness protocol.

29. The apparatus for routing data in wireless ad-hoc networks as set forth in claim 19, wherein there is a limiting counter configured to terminate the protocol after a predetermined number of enhancements.

30. The apparatus for routing data in wireless ad-hoc networks as set forth in claim 29, wherein the counter that limits the number of enhancements is determined by the method for routing data.

31. The apparatus for routing data in wireless ad-hoc networks as set forth in claim 29, wherein there is a counter that limits the number of enhancements to a predetermined number is selected based on memory resources allocated to the method for routing data.

32. The apparatus for routing data in wireless ad-hoc networks as set forth in claim 19, wherein the ENHANCEMENT_—

INTERVAL is varied.

33. The apparatus for routing data in wireless ad-hoc networks as set forth in claim 19, wherein the ENHANCEMENT_—

INTERVAL is varied and the variation is based on the number of nodes adjacent to the source node.

34. The apparatus for routing data in wireless ad-hoc networks as set forth in claim 19, wherein a transmission path is not the same as a return path.

35. The apparatus for routing data in wireless ad-hoc networks as set forth in claim 19, wherein the data packet includes at least one of the following:

a. a set of node neighbors which have a link to the transmitting node;

b. a set of node neighbors with which the transmitting node has a link;

c. any nodes on the outbound tree of the transmitting node;

d. a sequence number;

e. an urgent flag, which provides data concerning link status;

f. a time to live counter which tracks the number of hops up to which the data packet can be forwarded, the time to live counter is initialized to the ZONE_—

RADIUS and is incremented as the data packet traverses a path.

36. The apparatus for routing data in wireless ad-hoc networks as set forth in claim 35, wherein the nodes on the outbound tree of the transmitting node are computed from the units obtained from other nodes.