Hierarchical mobile ad-hoc network and methods for performing reactive routing therein using dynamic source routing (DSR)

• US 6,870,846 B2
• Filed: 04/29/2002
• Issued: 03/22/2005
• Est. Priority Date: 04/29/2002
• Status: Expired due to Term

• Current Assignee: Stingray IP Solutions LLC (Acacia Research Corporation)
• Original Assignee: Harris Corporation (L3Harris Technologies, Inc.)
• Inventors: Cain, Joseph Bibb
• Primary Examiner(s): Pham, Chi
• Assistant Examiner(s): Ferris, Derrick W
• Application Number:
  US10/134,859
• Publication Number:
  US 20030202465A1
• Time in Patent Office: 1,058 Days
• Field of Search: 370/254, 370/310, 370/338, 370/392, 370/351, 370/389, 709/238, 709/239, 709/242, 709/243
• US Class Current: 370/392
• 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/34 Source routing
• 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

Abstract

A method is provided for sending data in a wireless ad-hoc network including a plurality of nodes grouped into clusters of nodes and a plurality of wireless links connecting the plurality of nodes, where each cluster node has a designated cluster leader node. The method may include sending a cluster-level route request from a source node of a source cluster to a cluster leader node of the source cluster, and determining a cluster-level route between the source cluster and a destination cluster including a destination node responsive to the cluster-level route request and using a plurality of the cluster leader nodes. Furthermore, at least one cluster target node may be designated in a cluster along the cluster-level route, and a node-level route determined from the source node to the destination node including the at least one cluster target node. In addition, the method may also include generating a mission data packet for transferring the data.

Claims

1. A method for sending data in a wireless ad-hoc network comprising a plurality of nodes grouped into clusters of nodes and a plurality of wireless links connecting the plurality of nodes, each cluster having a designated cluster leader node, the method comprising:

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;

designating at least one cluster target node in a cluster along the cluster-level route;

determining a node-level route from the source node to the destination node including the at least one cluster target node;

generating a mission data packet comprising an address of the destination node, an address of the at least one cluster target node, the node-level route, and the cluster-level route; and

transferring data from the source node to the destination node via the node-level route based upon the mission data packet.

2. The method of claim 1 wherein determining the at least one cluster target node comprises determining a respective cluster target node for each cluster along the cluster-level route.

3. The method of claim 2 wherein determining the node-level route comprises determining the node-level route from the source node to a cluster target node for a next adjacent cluster along the cluster-level route;

and further comprising determining a node-level route from each cluster target node to a next cluster target node along the cluster-level route.

4. The method of claim 3 wherein generating the mission data packet further comprises updating the mission data packet at each cluster target node along the cluster-level route to comprise an address of the next cluster target node and the node-level route thereto.

5. The method of claim 1 wherein the address of the at least one cluster target node and the cluster-level route are equal to a predetermined value if the source cluster and the destination cluster are the same cluster.

6. The method of claim 1 further comprising storing the address of the destination node along with an address of the respective cluster leader node therefor at the cluster leader node for the source cluster.

7. The method of claim 1 further comprising storing, at the source node, a hierarchical source route to the destination node comprising the cluster-level route, the address of the at least one cluster target node, and the node-level route.

8. The method of claim 1 further comprising storing the cluster-level route at the cluster leader node for the source cluster.

9. 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.

10. 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.

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

12. The method of claim 10 wherein each cluster leader node stores identities 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.

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

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

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

16. A method for sending data in a wireless ad-hoc network comprising a plurality of nodes grouped into clusters of nodes and a plurality of wireless links connecting the plurality of nodes, each cluster having a designated cluster leader node, the method comprising:

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;

designating at least one cluster target node in a cluster along the cluster-level route;

determining a node-level route from the source node to the destination node including the at least one cluster target node;

generating a mission data packet comprising an address of the destination node, an address of the at least one cluster target node, the node-level route, and the cluster-level route, the address of the at least one cluster target node and the cluster-level route being equal to a predetermined value if the source cluster and the destination cluster are the same cluster;

transferring data from the source node to the destination node via the node-level route based upon the mission data packet; and

storing, at the source node, a hierarchical source route to the destination node comprising the cluster-level route, the address of the at least one cluster target node, and the node-level route.

17. The method of claim 16 wherein determining the at least one cluster target node comprises determining a respective cluster target node for each cluster along the cluster-level route.

18. The method of claim 17 wherein determining the node-level route comprises determining the node-level route from the source node to a cluster target node for a next adjacent cluster along the cluster-level route;

and further comprising determining a node-level route from each cluster target node to a next cluster target node along the cluster-level route.

19. The method of claim 18 wherein generating the mission data packet further comprises updating the mission data packet at each cluster target node along the cluster-level route to comprise an address of the next cluster target node and the node-level route thereto.

20. The method of claim 16 further comprising storing the address of the destination node along with an address of the respective cluster leader node therefor at the cluster leader node for the source cluster.

21. The method of claim 16 further comprising storing the cluster-level route at the cluster leader node for the source cluster.

22. The method of claim 16 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.

23. The method of claim 16 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.

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

25. The method of claim 23 wherein each cluster leader node stores identities 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.

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

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

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

29. A wireless ad-hoc network comprising:

a plurality of nodes grouped into clusters of nodes, each cluster node 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;

designating at least one cluster target node in a cluster along the cluster-level route;

determining a node-level route from said source node to said destination node including said at least one cluster target node;

generating a mission data packet comprising an address of said destination node, an address of said at least one cluster target node, the node-level route, and the cluster-level route; and

transferring data from said source node to said destination node via the node-level route based upon the mission data packet.

30. The mobile ad-hoc network of claim 29 wherein said at least one cluster target node comprises a respective cluster target node for each cluster along the cluster-level route.

31. The mobile ad-hoc network of claim 30 wherein the node-level route comprises a node-level route from the source node to a cluster target node for a next adjacent cluster along the cluster-level route and a node-level route from each cluster target node to a next cluster target node along the cluster-level route.

32. The mobile ad-hoc network of claim 31 wherein the mission data packet is updated at each cluster target node along the cluster-level route to comprise an address of the next cluster target node and the node-level route thereto.

33. The mobile ad-hoc network of claim 29 wherein the address of the at least one cluster target node and the cluster-level route are equal to a predetermined value if the source cluster and the destination cluster are the same cluster.

34. The mobile ad-hoc network of claim 29 wherein the address of the destination node is stored along with an address of the respective cluster leader node therefor at the cluster leader node for the source cluster.

35. The mobile ad-hoc network of claim 29 wherein, at the source node, a hierarchical source route to the destination node is stored comprising the cluster-level route, the address of the at least one cluster target node, and the node-level route.

36. The mobile ad-hoc network of claim 29 wherein the cluster-level route is stored at the cluster leader node for the source cluster.

37. The mobile ad-hoc network of claim 29 further comprising designated communication links connecting the 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 said 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.

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

39. The mobile ad-hoc network of claim 37 wherein each cluster leader node stores identities of adjacent cluster leader nodes;

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

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

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