Hierarchical mobile ad-hoc network and methods for performing reactive routing therein

• US 20030204623A1
• Filed: 04/29/2002
• Published: 10/30/2003
• Est. Priority Date: 04/29/2002
• Status: Active Grant

• Current Assignee: Stingray IP Solutions LLC (Acacia Research Corporation)
• Original Assignee: Harris Corporation (L3Harris Technologies, Inc.)
• Inventors: Cain, Joseph Bibb
• Granted Patent: US 7,281,057 B2
• Time in Patent Office: Days
• US Class Current: 709/241
• 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/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04L 45/30 Routing of multiclass traffic
• CPC Class Codes: H04L 45/302 Route determination based on requested QoS
• CPC Class Codes: H04L 45/46 Cluster building
• 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/26 for hybrid routing by combining proactive and reactive routing
• CPC Class Codes: H04W 40/28 for reactive routing
• CPC Class Codes: H04W 40/32 for defining a routing cluster membership
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

A method is provided for sending data in a mobile ad-hoc network including a plurality of nodes and a plurality of wireless links connecting the plurality of nodes. The method may include grouping the plurality of nodes into clusters of nodes and designating a cluster leader node for each cluster. Furthermore, a cluster-level route request may be sent from a source node of a source cluster to a cluster leader node of the source cluster. The method may also include determining a cluster-level route between the source cluster and a destination cluster comprising a destination node responsive to the cluster-level route request and using a plurality of the cluster leader nodes. Additionally, data may be transferred from the source node to the destination node using the cluster-level route.

Claims

1. A method for sending data in a mobile ad-hoc network comprising a plurality of nodes and a plurality of wireless links connecting the plurality of nodes, the method comprising:

grouping the plurality of nodes into clusters of nodes;

designating a cluster leader node for each cluster;

sending a cluster-level route request from a source node of a source cluster to a cluster leader node of the source cluster;

determining a cluster-level route between the source cluster and a destination cluster comprising a destination node responsive to the cluster-level route request and using a plurality of the cluster leader nodes; and

transferring data from the source node to the destination node using the cluster-level route.

2. The method of claim 1 wherein grouping comprises grouping a node into a cluster based upon a number of hops from the node to the respective cluster leader node of the cluster.

3. The method of claim 1 wherein grouping comprises grouping a node into a cluster based upon a path metric associated with a path to at least one node in the cluster.

4. The method of claim 3 wherein the path metric comprises at least one of delay, bandwidth, and availability.

5. The method of claim 1 wherein grouping comprises grouping a node into a cluster based upon a number of nodes of the cluster within a number of hops therefrom.

6. The method of claim 1 wherein designating the cluster leader node for each cluster comprises designating cluster leader nodes based upon a number of nodes within a predetermined number of hops thereof.

7. The method of claim 1 wherein designating the cluster leader node for each cluster comprises designating cluster leader nodes based upon a node metric comprising at least one of link capacity, mobility, and availability.

8. The method of claim 1 further comprising grouping a plurality of the cluster leader nodes comprising at least the source cluster leader node and the destination cluster leader node into a leader node cluster, and determining a high-level route from the cluster leader node of the source cluster to the cluster leader node of the destination cluster within the leader node cluster;

and wherein the cluster-level route comprises at least the clusters having respective cluster leader nodes along the high-level route.

9. The method of claim 8 wherein determining the high-level route comprises determining the high-level route using dynamic source routing (DSR).

10. The method of claim 8 wherein determining the high-level route comprises determining the high-level route using ad-hoc on-demand distance vector (AODV) routing.

11. The method of claim 1 wherein determining the cluster-level route comprises:

determining designated communication links between the cluster leader nodes;

sending a cluster leader node route request from the cluster leader node of the source cluster to the remaining cluster leaders via the designated communication links; and

returning a cluster leader node route reply from the cluster leader node of the destination cluster to the cluster leader node of the source cluster along a delivery route of the cluster leader node route request.

12. The method of claim 11 wherein at least one of the designated communications links comprises a node that is not a cluster leader node.

13. The method of claim 11 wherein each cluster leader node stores addresses of adjacent cluster leader nodes;

and wherein sending the cluster leader node route request comprises sending the cluster leader node route request from each cluster leader node to its adjacent cluster leader nodes.

14. The method of claim 13 further comprising periodically polling the adjacent cluster leader nodes to maintain current addresses therefor.

15. The method of claim 13 wherein the delivery route comprises a least number of cluster leader nodes between the cluster leader nodes of the source and destination clusters.

16. The method of claim 13 further comprising determining the delivery route based upon at least one of delay, link capacity, and availability.

17. The method of claim 1 wherein transferring comprises:

(a) designating a cluster target node in a next cluster along the cluster-level route;

(b) determining a node-level route from a node at which the data is currently located to the cluster target node;

(c) transferring the data from the node at which the data is currently located to the cluster target node via the node-level route;

(d) repeating steps (a) through (c) until the data reaches a destination cluster target node for the destination cluster;

(e) determining a node-level route from the destination cluster target node to the destination node; and

(f) transferring the data from the destination cluster target node to the destination node via the node- level route established in step (e).

18. The method of claim 17 wherein the steps (b) and (e) are performed using dynamic source routing (DSR).

19. The method of claim 17 wherein the steps (b) and (e) are performed using ad-hoc on-demand distance vector (AODV) routing.

20. The method of claim 1 wherein transferring comprises not transferring data through at least one of the cluster leader nodes along the cluster-level route.

21. A method for sending data in a mobile ad- hoc network comprising a plurality of nodes and a plurality of wireless links connecting the plurality of nodes, the method comprising:

grouping the plurality of nodes into clusters of nodes;

designating a cluster leader node for each cluster;

determining designated communication links between the cluster leader nodes;

sending a cluster-level route request from a source node of a source cluster to a cluster leader node of the source cluster;

determining a cluster-level route between the source cluster and a destination cluster comprising a destination node responsive to the cluster-level route request and using a plurality of the cluster leader nodes and the designated communication links therebetween; and

transferring data from the source node to the destination node using the cluster-level route, the data not being transferred through at least one of the cluster leader nodes along the cluster-level route.

22. The method of claim 21 wherein grouping comprises grouping a node into a cluster based upon a number of hops from the node to the respective cluster leader node of the cluster.

23. The method of claim 21 wherein grouping comprises grouping a node into a cluster based upon a path metric associated with a path to at least one node in the cluster.

24. The method of claim 23 wherein the path metric comprises at least one of delay, bandwidth, and availability.

25. The method of claim 21 wherein grouping comprises grouping a node into a cluster based upon a number of nodes of the cluster within a number of hops therefrom.

26. The method of claim 21 wherein designating the cluster leader node for each cluster comprises designating cluster leader nodes based upon a number of nodes within a predetermined number of hops thereof.

27. The method of claim 21 wherein designating the cluster leader node for each cluster comprises designating cluster leader nodes based upon a node metric comprising at least one of link capacity, mobility, and availability.

28. The method of claim 21 further comprising grouping a plurality of the cluster leader nodes comprising at least the source cluster leader node and the destination cluster leader node into a leader node cluster, and determining a high-level route from the cluster leader node of the source cluster to the cluster leader node of the destination cluster within the leader node cluster;

and wherein the cluster-level route comprises at least the clusters having respective cluster leader nodes along the high-level route.

29. The method of claim 28 wherein determining the high-level route comprises determining the high-level route using dynamic source routing (DSR).

30. The method of claim 28 wherein determining the high-level route comprises determining the high-level route using ad-hoc on-demand distance vector (AODV) routing.

31. The method of claim 21 wherein determining the cluster-level route comprises:

sending a cluster leader node route request from the cluster leader node of the source cluster to the remaining cluster leaders via the designated communication links; and

returning a cluster leader node route reply from the cluster leader node of the destination cluster to the cluster leader node of the source cluster along a delivery route of the cluster leader node route request.

32. The method of claim 31 wherein at least one of the designated communications links comprises a node that is not a cluster leader node.

33. The method of claim 31 wherein each cluster leader node stores addresses of adjacent cluster leader nodes;

and wherein sending the cluster leader node route request comprises sending the cluster leader node route request from each cluster leader node to its adjacent cluster leader nodes.

34. The method of claim 33 further comprising periodically polling the adjacent cluster leader nodes to maintain current addresses therefor.

35. The method of claim 31 wherein the delivery route comprises a least number of cluster leader nodes between the cluster leader nodes of the source and destination clusters.

36. The method of claim 31 further comprising determining the delivery route based upon at least one of delay, link capacity, and availability.

37. The method of claim 21 wherein transferring comprises:

(a) designating a cluster target node in a next cluster along the cluster-level route;

(b) determining a node-level route from a node at which the data is currently located to the cluster target node;

(c) transferring the data from the node at which the data is currently located to the cluster target node via the node-level route;

(d) repeating steps (a) through (c) until the data reaches a destination cluster target node for the destination cluster;

(e) determining a node-level route from the destination cluster target node to the destination node; and

(f) transferring the data from the destination cluster target node to the destination node via the node- level route established in step (e).

38. The method of claim 37 wherein the steps (b) and (e) are performed using dynamic source routing (DSR).

39. The method of claim 37 wherein the steps (b) and (e) are performed using ad-hoc on-demand distance vector (AODV) routing.

40. A mobile ad-hoc network comprising:

a plurality of nodes grouped into clusters of nodes, each cluster having a designated cluster leader node; and

a plurality of wireless links connecting said plurality of nodes;

said plurality of nodes sending data therebetween by

sending a cluster-level route request from a source node of a source cluster to a cluster leader node of said source cluster;

determining a cluster-level route between said source cluster and a destination cluster comprising a destination node responsive to the cluster-level route request and using a plurality of said cluster leader nodes, and

transferring data from said source node to said destination node using the cluster-level route.

41. The mobile ad-hoc network of claim 40 further comprising designated communication links connecting said cluster leader nodes;

and wherein the cluster-level route is determined by sending a cluster leader node route request from said cluster leader node of said source cluster to the remaining cluster leaders via said designated communication links, and returning a cluster leader node route reply from said cluster leader node of said destination cluster to said cluster leader node of said source cluster along a delivery route of the cluster leader node route request.

42. The mobile ad-hoc network of claim 41 wherein at least one of said designated communications links comprises a node that is not a cluster leader node.

43. The mobile ad-hoc network of claim 42 wherein each cluster leader node stores addresses of adjacent cluster leader nodes;

and wherein the cluster leader node route request is sent by sending the cluster leader node route request from each cluster leader node to its adjacent cluster leader nodes.

44. The mobile ad-hoc network of claim 43 wherein each cluster leader node periodically polls its adjacent cluster leader nodes to maintain current addresses therefor.

45. The mobile ad-hoc network of claim 41 wherein the delivery route comprises a least number of cluster leader nodes between said cluster leader nodes of said source and destination clusters.