Clusterhead selection in a communication network

• US 9,762,467 B2
• Filed: 02/24/2016
• Issued: 09/12/2017
• Est. Priority Date: 07/28/2010
• Status: Expired due to Fees

• Current Assignee: Her Majesty The Queen In Right of Canada As Represented By The Minister of National Defence
• Original Assignee: Communications Research Centre Canada (Government of Canada)
• Inventors: Willink, Patricia Janet, Baddour, Kareem Emile, Ureten, Oktay
• Primary Examiner(s): LEE, BRYAN Y
• Application Number:
  US15/052,345
• Publication Number:
  US 20160197806A1
• Time in Patent Office: 566 Days
• CPC Class Codes: H04L 43/0805 by checking availability
• CPC Class Codes: H04L 43/16 Threshold monitoring
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes

Abstract

Technologies are generally described for clusterhead selection in a communication network. In an example, a first node may be configured to send a first responsibility and availability. In some examples, the first responsibility indicates a responsibility attributed to the second node to be the clusterhead for the first node. In some examples, the first availability indicates an availability of the first node to be the clusterhead for the second node. In some examples, the first node is effective to receive a second responsibility and availability; the second responsibility indicating a responsibility attributed to the first node to be the clusterhead for a second node; the second availability indicating an availability of the second node to be the clusterhead for the first node. In some examples, the first node is effective to determine the clusterhead based on the first and second responsibility and the first and second availability.

Claims

1. A method to select a clusterhead in a network comprising two or more nodes, the method comprising:

determining, by a first node, a first similarity based on first topology data, wherein the first similarity relates to similarities between the first node and a second node, and wherein the first topology data includes at least an indication of a shared communication frequency between the first node and the second node;

determining, by the first node, a second similarity based on second topology data, wherein the second similarity relates to similarities between the first node and a third node, and wherein the second topology data includes at least an indication of a shared communication frequency between the first node and the third node;

receiving, by the first node, a first availability from the second node, wherein the first availability indicates an availability of the second node to be a clusterhead for the first node;

receiving, by the first node, a second availability from the third node, wherein the second availability indicates an availability of the third node to be the clusterhead for the first node;

updating, by the first node, the first similarity based on the first availability and based on a first responsibility, wherein the first responsibility indicates a responsibility attributed to the second node to be the clusterhead for the first node;

updating, by the first node, the second similarity based on the second availability and based on a second responsibility, wherein the second responsibility indicates a responsibility attributed to the third node to be the clusterhead for the first node;

determining, by the first node, that the updated first similarity is greater than the updated second similarity;

in response to the determination that the updated first similarity is greater than the updated second similarity, selecting, by the first node, the second node to be the clusterhead for the first node such that the second node is to be configured to communicate on behalf of the first node; and

receiving, by the first node, a message from the third node, wherein the message indicates a selection of the first node to be a clusterhead for the third node such that the first node is to be configured to communicate on behalf of the third node.

2. The method of claim 1, wherein:

the first responsibility is based on the first availability, and

the second responsibility is based on the second availability.

3. The method of claim 1, further comprising:

sending, by the first node, the first responsibility to the second node; and

sending, by the first node, the second responsibility to the third node, wherein the selection of the first node to be the clusterhead for the third node is based on the second responsibility.

4. The method of claim 1, wherein selecting the second node to be the clusterhead for the first node further comprises determining a number of neighboring nodes to the second node.

5. The method of claim 1, further comprising:

determining, by the first node, that the second node has been selected as the clusterhead for the first node for a period of time; and

in response to the determination that the second node has been selected as the clusterhead for the first node for the period of time, terminating, by the first node, an exchange of further responsibility and availability among the first node, the second node, and the third node.

6. The method of claim 1, further comprising:

receiving, by the first node, a third availability from the second node, wherein the third availability represents an update to the first availability;

receiving, by the first node, a fourth availability from the third node, wherein the fourth availability represents an update to the second availability;

modifying, by the first node, the updated first similarity to determine a third similarity, wherein modifying the updated first similarity is based on the third availability and based on a third responsibility, wherein the third responsibility represents an update to the first responsibility; and

modifying, by the first node, the updated second similarity to determine a fourth similarity, wherein modifying the updated second similarity is based on the fourth availability and based on a fourth responsibility, wherein the fourth responsibility represents an update to the second responsibility;

determining, by the first node, that the third similarity is greater than the fourth similarity; and

in response to the determination that the third similarity is greater than the fourth similarity, selecting, by the first node, the second node to be the clusterhead for the first node.

7. The method of claim 6, further comprising:

detecting, by the first node, a convergence associated with the first availability, the second availability, the third availability, and the fourth availability, and associated with the first responsibility, the second responsibility, the third responsibility, and the fourth responsibility; and

in response to the detection of the convergence, terminating, by the first node, an exchange of further responsibility and availability among the first node, the second node, and the third node.

8. The method of claim 7, wherein detecting the convergence comprises:

determining, by the first node, a first difference between the first availability and the third availability,

determining, by the first node, a second difference between the second availability and the fourth availability,

determining, by the first node, a third difference between the first responsibility and the third responsibility,

determining, by the first node, a fourth difference between the second responsibility and the fourth responsibility,

determining, by the first node, that the first difference and the second difference are below a first threshold, and

determining, by the first node, that the third difference and the fourth difference are below a second threshold.

9. A system effective to select a clusterhead in a network that comprises two or more nodes, the system comprising:

a first node that includes a first processor and a first memory, wherein the first processor is configured to be in communication with the first memory;

a second node that includes a second processor and a second memory, wherein the second processor is configured to be in communication with the second memory; and

a third node that includes a third processor and a third memory, wherein the third processor is configured to be in communication with the third memory,

wherein;

the first memory is configured to store first topology data and second topology data,

the first topology data includes at least an indication of a shared communication frequency between the first node and the second node, and

the second topology data includes at least an indication of a shared communication frequency between the first node and the third node,

wherein the first processor is configured to;

determine a first similarity based on the first topology data, the first similarity relates to similarities between the first node and the second node, and

determine a second similarity based on the second topology data, the second similarity relates to similarities between the first node and the third node,

wherein the second processor is configured to;

send a first availability to the first processor, the first availability indicates an availability of the second node to be a clusterhead for the first node,

wherein the third processor is configured to;

send a second availability to the first processor, wherein the second availability indicates an availability of the third node to be the clusterhead for the first node,

wherein the first processor is further configured to;

in response to reception of the first availability from the second processor, update the first similarity based on the first availability and based on a first responsibility, wherein the first responsibility indicates a responsibility attributed to the second node to be the clusterhead for the first node,

in response to reception of the second availability from the third processor, update the second similarity based on the second availability and based on a second responsibility, wherein the second responsibility indicates a responsibility attributed to the third node to be the clusterhead for the first node,

determine that the updated first similarity is greater than the updated second similarity, and

in response to the determination that the updated first similarity is greater than the updated second similarity, select the second node to the clusterhead for the first node such that the second node is to be configured to communicate on behalf of the first node, and

wherein the third processor is further configured to send a message to the first processor, wherein the message indicates a selection of the first node to be a clusterhead for the third node such that the first node is to be configured to communicate on behalf of the third node.

10. The system of claim 9, wherein:

the first responsibility is based on the first availability, and

the second responsibility is based on the second availability.

11. The system of claim 9, wherein the first processor is further configured to:

send the first responsibility to the second processor, and

send the second responsibility to the third processor, wherein the selection of the first node to be the clusterhead for the third node is based on the second responsibility.

12. The system of claim 9, wherein the first processor is further configured to select the second node to be the clusterhead for the first node based on a determination of a number of neighboring nodes to the second node.

13. The system of claim 9, wherein the first processor is further configured to:

determine that the second node has been selected as the clusterhead for the first node for a period of time, and

in response to the determination that that the second node has been selected as the clusterhead for the first node for the period of time, terminate an exchange of further responsibility and availability among the first processor, the second processor, and the third processor.

14. The system of claim 9, wherein:

the second processor is further configured to;

send a third availability to the first processor, wherein the third availability represents an update to the first availability,

the third processor is further configured to;

send a fourth availability to the first processor, wherein the fourth availability represents an update to the second availability, and

the first processor is further configured to;

modify the updated first similarity to determine a third similarity, wherein modifying the updated first similarity is based on the third availability and based on a third responsibility, wherein the third responsibility represents an update to the first responsibility,

modify the updated second similarity to determine a fourth similarity, wherein modifying the updated second similarity is based on the fourth availability and based on a fourth responsibility, wherein the fourth responsibility represents an update to the second responsibility,

determine that the third similarity is greater than the fourth similarity, and

in response to the third similarity being greater than the fourth similarity, select the second node to be the clusterhead for the first node.

15. The system of claim 14, wherein the first processor is further configured to:

detect a convergence associated with the first availability, the second availability, the third availability, and the fourth availability, and associated with the first responsibility, the second responsibility, the third responsibility, and the fourth responsibility, and

in response to the detection of the convergence, terminate an exchange of further responsibility and availability among the first processor, the second processor, and the third processor.