Hierarchical modile ad-hoc network and methods for route error recovery therein

• US 6,628,620 B1
• Filed: 04/29/2002
• Issued: 09/30/2003
• 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): MARCELO, MELVIN C
• Application Number:
  US10/134,723
• Time in Patent Office: 519 Days
• Field of Search: 370/254, 370/255, 370/256, 370/248, 370/252, 370/345, 455/446, 455/449
• US Class Current: 370/248
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 40/248 Connectivity information update
• CPC Class Codes: H04W 40/30 for proactive 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
• CPC Class Codes: H04W 92/02 Inter-networking arrangements

Abstract

A method for sending data in a mobile ad-hoc network may include 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 through 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, the method may also include determining node-level routes through each cluster along the cluster-level route to a cluster target node in a next cluster along the cluster-level route. Recovery for cluster-level and node-level routing errors/failures is also provided.

Claims

1. A method for sending data in a mobile 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 node 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;

determining node-level routes through each cluster along the cluster-level route to a cluster target node in a next cluster along the cluster-level route;

transferring the data from the source node to the destination node using the node-level routes;

if a node-level route failure occurs along a node-level route, determining a new node-level route therefor; and

if a cluster-level route failure occurs between adjacent clusters along the cluster-level route, sending a cluster-level route error message to the source node and determining new cluster-level and node-level routes responsive thereto and transferring the data using the new node-level routes.

2. The method of claim 1 wherein determining node-level routes comprises determining node-level routes using the dynamic source routing (DSR) protocol.

3. The method of claim 1 wherein determining node-level routes comprises determining node-level routes using the ad-hoc on-demand vector routing (AODV) protocol.

4. The method of claim 1 further comprising sending the cluster-level route error message from a cluster target node immediately upstream from where the cluster-level failure occurred to its respective cluster leader node, and sending the cluster-level route error message to each cluster leader node upstream therefrom.

5. The method of claim 1 wherein determining the cluster-level route comprises storing, at each cluster leader node except the destination cluster leader node, an address of a next cluster leader node along the cluster route;

and further comprising deleting the next cluster leader node address from each cluster leader node upstream from where the cluster-level failure occurred.

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

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

8. The method of claim 6 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.

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

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

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

12. The method of claim 1 wherein at least one of the node-level routes does not include a cluster leader node.

13. A method for sending data in a mobile 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 node 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 designated communication links between the cluster leader nodes;

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;

determining node-level routes through each cluster along the cluster-level route to a cluster target node in a next cluster along the cluster-level route, at least one of the node-level routes not including a cluster leader node;

transferring the data from the source node to the destination node using the node-level routes;

if a node-level route failure occurs along a node level route, determining a new node-level route therefor; and

if a cluster-level route failure occurs between adjacent clusters along the cluster-level route, sending a cluster-level route error message to the source node and determining new cluster-level and node-level routes responsive thereto and transferring the data using the new node-level routes.

14. The method of claim 13 wherein determining node-level routes comprises determining node-level routes using the dynamic source routing (DSR) protocol.

15. The method of claim 13 wherein determining node-level routes comprises determining node-level routes using the ad-hoc on-demand vector routing (AODV) protocol.

16. The method of claim 13 further comprising sending the cluster-level route error message from a cluster target node immediately upstream from where the cluster-level failure occurred to its respective cluster leader node, and sending the cluster-level route error message to each cluster leader node upstream therefrom.

17. The method of claim 13 wherein determining the cluster-level route comprises storing, at each cluster leader node except the destination cluster leader node, an address of a next cluster leader node along the cluster route;

and further comprising deleting the next cluster leader node address from each cluster leader node upstream from where the cluster-level failure occurred.

18. The method of claim 13 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.

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

20. The method of claim 18 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.

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

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

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

24. The method of claim 13 wherein at least one of the node-level routes does not include a cluster leader node.

25. A mobile 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,

determining node-level routes through each cluster along the cluster-level route to a cluster target node in a next cluster along the cluster-level route,

transferring the data from said source node to said destination node using the node-level routes,

if a node-level route failure occurs along a node level route, determining a new node-level route therefor, and

if a cluster-level route failure occurs between adjacent clusters along the cluster-level route, sending a cluster-level route error message to said source node and determining new cluster-level and node-level routes responsive thereto and transferring the data using the new node-level routes.

26. The mobile ad-hoc network of claim 25 wherein the node-level routes are determined using the dynamic source routing (DSR) protocol.

27. The mobile ad-hoc network of claim 25 wherein the node-level routes are determined using the ad-hoc on-demand vector routing (AODV) protocol.

28. The mobile ad-hoc network of claim 25 wherein the cluster-level route error message is also sent from a cluster target node immediately upstream from where the cluster-level failure occurred to its respective cluster leader node, and then sent to each cluster leader node upstream therefrom.

29. The mobile ad-hoc network of claim 25 further comprising designated communication links between 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.

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

31. The mobile ad-hoc network of claim 29 wherein each cluster leader node stores addresses 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.

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

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

34. The mobile ad-hoc network of claim 25 wherein at least one of the node-level routes does not include a cluster leader node.