Clusterhead selection in wireless ad hoc networks

• US 6,829,222 B2
• Filed: 04/24/2001
• Issued: 12/07/2004
• Est. Priority Date: 04/25/2000
• Status: Expired due to Fees

• Current Assignee: Board of Regents of the University of Texas System (University of Texas System)
• Original Assignee: Board of Regents of the University of Texas System (University of Texas System)
• Inventors: Prakash, Ravi, Amis, Alan Dewayne
• Primary Examiner(s): Ho, Duc
• Assistant Examiner(s): Nguyen, Phuongchau Ba
• Application Number:
  US09/841,746
• Publication Number:
  US 20020018448A1
• Time in Patent Office: 1,323 Days
• Field of Search: 370/242, 370/221, 370/254, 370/256, 370/245, 370/258, 370/238, 370/331, 370/335, 370/338, 370/351, 370/400, 370/409, 370/522, 370/396, 370/390, 370/404, 455/445, 455/519, 455/571, 455/7, 455/11.1, 455/13.1, 709/218, 709/241, 709/245, 340/825.02
• US Class Current: 370/238
• CPC Class Codes: H04L 41/0893 Assignment of logical groups to network elements
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/46 Cluster building
• CPC Class Codes: H04L 61/5038 for local use, e.g. in LAN or USB networks, or in a controller area network [CAN]
• 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 48/20 Selecting an access point
• CPC Class Codes: H04W 8/26 Network addressing or numbering for mobility support
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

A system and method is disclosed wherein a plurality of nodes within an ad hoc wireless network are able to wirelessly communicate with each other. Each node includes a first data array for storing a node identifier used in selecting a clusterhead and a second data array for storing information relating to the node providing the node identifier for selecting the clusterhead to the node. Control logic of each node is configured according to a heuristic wherein the node initially determines a largest and smallest node identifier for each node. The node selects a clusterhead for the node responsive to the largest node identifier and the smallest node identifier using a set of predefined rules. The nodes within the area are then linked with the selected clusterhead.

Claims

1. A method for selecting a clusterhead not greater than d hops from any node in a cluster within an ad hoc network, wherein d>

1, comprising the steps of;

determining at least one largest node identifier for each node within a d-neighborhood of at least one node;

determining at least one smallest node identifier from the at least one largest node identifier;

selecting a clusterhead for the d-neighborhood of at least one node responsive to the determined at least one largest identifier for each node of the d-neighborhood of at least one node and the determined at least one smallest identifier for each node of the d-neighborhood of at least one node; and

linking each node of the d-neighborhood of at least one node to the selected clusterhead, wherein the step of selecting the clusterhead further comprises the steps of;

determining the smallest node identifier for a node is not an original node identifier of the node;

identifying all node duplicates for the node;

if node duplicates exist for the node, selecting a node associated with a smallest node duplicate as the clusterhead; and

performing the above steps for each node in the d-neighborhood at least one node.

2. The method of claim 1, further comprising the step of linking the selected clusterhead with other clusters of the ad hoc network.

3. The method of claim 1, wherein the step of determining at least one largest node identifier further comprises the steps of:

setting the largest node identifier for each node of the d-neighborhood of at least one node initially equal to an identifier of each node;

receiving a plurality of largest node identifiers from each neighboring node at each node of the d-neighborhood of at least one node; and

selecting a largest one of the plurality of largest node identifiers as the largest node identifier at each node of the d-neighborhood of at least one node.

4. The method of claim 1, wherein the step of determining at least one smallest node identifier further comprises the steps of:

setting the smallest node identifier for each node associated with the at least one largest node identifier initially equal to an identifier of each node;

receiving a plurality of smallest node identifiers from each neighboring node at each node associated with the at least one largest node identifier; and

selecting a smallest one of the plurality of smallest node identifiers as the smallest node identifier at each node associated with the at least one largest node identifier.

5. The method of claim 1, wherein the step of selecting a clusterhead further comprises the step of selecting a node as its own clusterhead if the smallest node identifier for the node is an original node identifier of the node for each node in the d-neighborhood of at least one node.

6. The method of claim 1, wherein the step of selecting the clusterhead further comprises the steps of:

determining duplicates do not exist for a node;

selecting a node associated with the largest node identifier as the clusterhead for the node; and

performing the above steps for each node in the d-neighborhood of at least one node.

7. The method of claim 1, wherein the step of selecting further comprises the step of transferring a node to a cluster served by a second clusterhead if a pathway between the node and the selected clusterhead passes through another cluster.

8. The method of claim 1, wherein the step of linking further comprises the step of transmitting the selected clusterhead for each node to the selected clusterhead.

9. The method of claim 8, wherein the step of transmitting further comprises the step of transmitting the selected clusterhead from each node to the selected clusterhead occurs from a node furthest away from the selected clusterhead to each neighbor of the node furthest away from the selected clusterhead until reaching the clusterhead.

10. The method of claim 1, wherein the step of selecting is further responsive to a number of contiguous times a node has been a clusterhead.

11. The method of claim 1, wherein the step of selecting is further responsive to an amount of work performed by a clusterhead.

12. The method of claim 1, wherein the d-neighborhood comprises a number of nodes a selected distance from a node.

18. The method of claim 1, wherein the cluster of nodes comprises a number of nodes a selected distance from a node.

13. A method for selecting a clusterhead for a cluster of nodes within a packet radio network, comprising the steps of:

setting a largest node identifier for each node of the cluster of nodes initially equal to an identifier of each node;

receiving a plurality of largest node identifiers from each neighboring node at each node of the cluster of nodes;

selecting a largest one of the plurality of largest node identifiers as the largest node identifier at each node of the cluster of nodes;

setting a smallest node identifier for each node associated with the at least one largest node identifier initially equal to an identifier of each node;

receiving a plurality of smallest node identifiers from each neighboring node at each node associated with the at least one largest node identifier;

selecting a smallest one of the plurality of smallest node identifiers as the smallest node identifier at each node associated with the at least one largest node identifier;

determining if a smallest node identifier for a node equals an original node identifier for the node for each node of the cluster of nodes;

selecting the node as its own clusterhead if the smallest node identifier for the node equals the original node identifier of the node for each node of the cluster of nodes;

identifying all node duplicates for the node if the smallest node identifier for the node does not equal the original node identifier of the node for each node of the cluster of nodes;

if node duplicates exist for the node, selecting a node associated with a smallest node duplicate as the clusterhead for each node of the cluster of nodes;

if node duplicates do not exist for a node, selecting a node associated with the largest node identifier for the node as the clusterhead for each node of the cluster of nodes;

transferring the node to a cluster served by a second clusterhead if a pathway between the node and the selected clusterhead passes through another cluster for each node of the plurality of nodes; and

linking each node of the cluster of nodes to the selected clusterhead.

14. The method of claim 13, wherein the step of linking further comprises the step of transmitting the selected clusterhead for each node of the cluster of nodes to the selected clusterhead.

15. The method of claim 14, wherein the step of transmitting further comprises the step of transmitting the selected clusterhead from each node to the selected clusterhead occurs from a node furthest away from the selected clusterhead to each neighbor of the node furthest away until reaching the clusterhead.

16. The method of claim 13, further including the step of limiting a number of contiguous times a node has been a clusterhead.

17. The method of claim 13, further including the step of selecting a clusterhead responsive to an amount of work performed by a clusterhead.

19. A communications network comprising:

a plurality of nodes capable of wirelessly communicating with each other, each of the nodes further comprising;

a first data array for storing a winning node identifier for selecting a clusterhead;

a second data array for storing an identity of a node transmitting the winning node identifier to the node; and

a set of rules for selecting a clusterhead for the node no more that d-hops from any node in a cluster of the node, where d>

1, from the winning node identifier in the first data array, wherein the set of rules comprise least the following rules;

1) if the winning node identifier node identifier is a node identifier of node, the node is the clusterhead for the node, otherwise proceed to Rule 2;

2) if node duplicates exist for the node, select a second node associated with a node duplicate having a smallest winning node identifier as the clusterhead for the node, otherwise proceed to Rule 3;

3) selected a third node having a largest winning node identifier as clusterhead for the node;

4) if a cluster is between the node and the selected clusterhead, the node joins another cluster.

20. The telecommunications network of claim 19, further including control logic configured to perform the steps of:

determining at least one largest node identifier for each node within a d-neighborhood of at least one node;

determining at least one smallest node identifier from the at least one largest node identifier;

selecting a clusterhead for the d-neighborhood of at least one node responsive to the determined at least one largest identifier for each node of the d-neighborhood of at least one node and the determined at least one smallest identifier for each node of the d-neighborhood of at least one node; and

linking each node of the d-neighborhood of at least one node to the selected clusterhead.

21. The telecommunications network of claim 20, wherein the control logic is further configured to perform the steps of:

setting the largest node identifier for each node of the d-neighborhood of at least one node initially equal to an identifier of each node;

receiving a plurality of largest node identifiers from each neighboring node at each node of the d-neighborhood of at least one node; and

selecting a largest one of the plurality of largest node identifiers as the largest node identifier at each node of the d-neighborhood of at least one node.

22. The telecommunications network of claim 20, wherein the control logic is further configured to perform the steps of:

setting the smallest node identifier for each node associated with the at least one largest node identifier initially equal to an identifier of each node;

receiving a plurality of smallest node identifiers from each neighboring node at each node associated with the at least one largest node; and

selecting a smallest one of the plurality of smallest node identifiers as the smallest node identifier at each node associated with the at least one largest node.

23. The telecommunications network of claim 20, wherein the control logic is further configured to perform the step of selecting a node as its own clusterhead if the smallest node identifier for the node is an original node identifier of the node for each node in the d-neighborhood of at least one node.

24. The telecommunications network of claim 20, wherein the control logic is further configured to perform the steps of:

determining the smallest node identifier for a node is not an original node identifier of the node;

identifying all node duplicates for the node;

if node duplicates exist for the node, selecting a node associated with a smallest node duplicate as the clusterhead; and

performing the above steps for each node in the d-neighborhood of at least one node.

25. The telecommunications network of claim 20, wherein the control logic is further configured to perform the steps of:

determining duplicates do not exist for a node;

selecting the largest node identifier as the clusterhead for the node; and

performing the above steps for each node in the d-neighborhood of at least one node.

26. The telecommunications network of claim 20, wherein the control logic is further configured to perform the steps of transferring a node to a cluster served by a second clusterhead if a pathway between the node and the selected clusterhead passes through another cluster.