Clusterhead selection in a communication network

• US 9,288,126 B2
• Filed: 07/28/2010
• Issued: 03/15/2016
• 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: Her Majesty The Queen In Right of Canada As Represented By The Minister of National Defence
• Inventors: Baddour, Kareem Emile, Willink, Patricia Janet, Ureten, Oktay
• Primary Examiner(s): LEE, BRYAN Y
• Application Number:
  US12/845,360
• Publication Number:
  US 20120030342A1
• Time in Patent Office: 2,057 Days
• Field of Search: 709/224
• US Class Current: 1/1
• 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 for selecting a clusterhead in a network comprising a plurality of nodes, the method comprising:

sending from a first node a first responsibility and a first availability to a second node, wherein the first responsibility indicates a responsibility attributed to the second node to be the clusterhead for the first node, wherein the first responsibility is based on a similarity between the first node and the second node, and wherein the first availability indicates an availability of the first node to be the clusterhead for the second node and the similarity between the first node and the second node is based on shared communication frequencies or a strength of a communication link between the first node and the second node;

sending from the first node a second responsibility and a second availability to a third node, wherein the second responsibility indicates a responsibility attributed to the third node to be the clusterhead for the first node, wherein the second responsibility is based on a similarity between the third node and the first node, the similarity between the first node and the third node is based on shared communication frequencies between the first and third nodes, or a strength of a communication link between the first node and the third node, and the second availability indicates an availability of the first node to be the clusterhead for the third node;

receiving from the second node a third responsibility and a third availability at the first node, wherein the third responsibility indicates a responsibility attributed to the first node to be the clusterhead for the second node, wherein the third responsibility is based on the similarity between the second node and the first node, and wherein the third availability indicates an availability of the second node to be the clusterhead for the first node;

receiving from the third node a fourth responsibility and a fourth availability at the first node, wherein the fourth responsibility indicates a responsibility attributed to the first node to be the clusterhead for the third node, wherein the fourth responsibility is based on the similarity between the first node and the third node, wherein the fourth availability indicates an availability of the third node to be the clusterhead for the first node;

determining, by the first node, that the second node is a first clusterhead for the first node based on the first responsibility, third responsibility, first availability and third availability, wherein the first clusterhead is configured to communicate on behalf of the first node; and

receiving a message from the third node at the first node, wherein the message is effective to indicate a selection of the first node to be a second clusterhead for the third node, and the selection of the first node to be the second clusterhead is based on the second responsibility, fourth responsibility, second availability and fourth availability, wherein the second clusterhead is configured to communicate on behalf of the third node.

2. The method as recited in claim 1, wherein the first responsibility is based on the first availability.

3. The method as recited in claim 1, further comprising:

sending the third responsibility and the third availability from the second node; and

repeating, sending from the first node the first responsibility and first availability and sending the third responsibility and the third availability from the second node.

4. The method as recited in claim 3, further comprising adding a damping factor to the first responsibility, the second responsibility, the first availability, the second availability, the third responsibility, the third availability, the fourth responsibility, and the fourth availability.

5. The method as recited in claim 1, further comprising:

determining a self-similarity value for the first node; and

determining the first clusterhead for the first node based on the self-similarity value.

6. The method as recited in claim 1, wherein determining that the second node is the first clusterhead for the first node includes:

determining, by the first node, that the second node is the first clusterhead for the first node based on a number of neighbors to the second node.

7. The method as recited in claim 1, further comprising:

determining, by the first node, that the first node is the first clusterhead for the first node when no other neighbor to the first node is the clusterhead.

8. The method as recited in claim 1, wherein the first and second nodes are one communication hop from each other.

9. The method as recited in claim 1, further comprising:

determining, by the first node, that the first node is the first clusterhead for the first node when a fifth responsibility plus a fifth availability is greater than a threshold;

wherein the fifth responsibility indicates a responsibility attributed to the first node to be the first clusterhead for the first node; and

the fifth availability indicates an availability of the first node to be the first clusterhead for the first node.

10. The method of claim 1 further comprising, prior to determining the first clusterhead for the first node:

updating, by the first node, the similarity between the first and second nodes based on the third responsibility and the third availability received from the second node;

updating, by the first node, the first responsibility based on the updated similarity;

detecting a convergence associated with the first responsibility, the third responsibility, the first availability, and the third availability, wherein determining that the second node is the first clusterhead for the first node is performed in response to the detection of the convergence.

11. A first node effective to select a clusterhead in a network comprising a plurality of nodes, the first node comprising:

a memory;

a processor in communication with the memory,

wherein the processor is effective to;

send a first responsibility and a first availability to a second node, wherein the first responsibility indicates a responsibility attributed to the second node to be the clusterhead for the first node, wherein the first responsibility is based on a similarity between the first node and the second node, wherein the first availability indicates an availability of the first node to be the clusterhead for the second node and the similarity between the first node and the second node is based on shared communication frequencies or a strength of a communication link between the first node and the second node;

send a second responsibility and a second availability to a third node, wherein the second responsibility indicates a responsibility attributed to the third node to be the clusterhead for the first node, wherein the second responsibility is based on a similarity between the third node and the first node, the similarity between the first node and the third node is based on shared communication frequencies between the first and third nodes, or a strength of a communication link between the first node and the third node, and the second availability indicates an availability of the first node to be the clusterhead for the third node;

receive from the second node a third responsibility and a third availability at the first node, wherein the third responsibility indicates a responsibility attributed to the first node to be the clusterhead for the second node, wherein the third responsibility is based on the similarity between the second node and the first node, and wherein the third availability indicates an availability of the second node to be the clusterhead for the first node;

receive from the third node a fourth responsibility and a fourth availability, wherein the fourth responsibility indicates a responsibility attributed to the first node to be the clusterhead for the third node, wherein the fourth responsibility is based on the similarity between the first node and the third node, wherein the fourth availability indicates an availability of the third node to be the clusterhead for the first node;

determine that the second node is a first clusterhead for the first node based on the first responsibility, third responsibility, first availability and third availability, wherein the first clusterhead is configured to communicate on behalf of the first node;

receive a message from the third node, wherein the message is effective to indicate a selection of the first node to be a second clusterhead for the third node, and the selection of the first node to be the second clusterhead is based on the second responsibility, fourth responsibility, second availability and fourth availability, wherein the second clusterhead is configured to communicate on behalf of the third node;

store an indication of the first clusterhead in the memory.

12. The first node as recited in claim 11, wherein the processor is further effective to:

determine a self-similarity value for the first node;

determine the first clusterhead for the first node based on the self-similarity value.

13. The first node as recited in claim 11, wherein the processor is effective to determine that the first node is the first clusterhead for the first node when no other neighbor to the first node is the first clusterhead.

14. The first node as recited in claim 11, wherein the processor is further effective to:

determine that the first node is the first clusterhead for the first node when a fifth responsibility plus a fifth availability is greater than a threshold;

wherein the fifth responsibility indicates a responsibility attributed to the first node to be the first clusterhead for the first node; and

the fifth availability indicates an availability of the first node to be the first clusterhead for the first node.

15. The first node of claim 11, wherein the processor is further effective to:

update the similarity between the first and second nodes based on the third responsibility and the third availability received from the second node;

update the first responsibility based on the updated similarity;

detect a convergence associated with the first responsibility, the third responsibility, the first availability, and the third availability, wherein the determination that the second node is the first clusterhead for the first node is performed in response to the detection of the convergence.

16. A system effective to select a clusterhead in a network comprising a plurality of nodes, the system comprising:

a first node including a first memory and a first processor;

a second node in communication with the first node, the second node including a second memory and a second processor;

a third node in communication with the first node and the second node, the third node including a third memory and a third processor;

wherein the first processor is effective to;

send a first responsibility and a first availability to the second node, wherein the first responsibility indicates a responsibility attributed to the second node to be the clusterhead for the first node, wherein the first responsibility is based on a similarity between the first node and the second node, and wherein the second availability indicates an availability of the first node to be the clusterhead for the second node and the similarity between the first node and the second node is based on shared communication frequencies between the first and second nodes, shared communication frequencies or a strength of a communication link between the first node and the second node;

send a second responsibility and a second availability to the third node, wherein the second responsibility indicates a responsibility attributed to the third node to be the clusterhead for the first node, wherein the second responsibility is based on a similarity between the third node and the first node, the similarity between the first node and the third node is based on shared communication frequencies between the first and third nodes, or a strength of a communication link between the first node and the third node, and the second availability indicates an availability of the first node to be the clusterhead for the third node;

wherein the second processor is effective to;

receive the first responsibility and the first availability from the first processor; and

send a third responsibility and a third availability to the first node, wherein the third responsibility indicates a responsibility attributed to the first node to be the clusterhead for the second node, wherein the third responsibility is based on the similarity between the second node and the first node, and wherein the third availability indicates an availability of the second node to be the clusterhead for the first node;

wherein the third processor is effective to;

send a fourth responsibility and a fourth availability to the first node, wherein the fourth responsibility indicates a responsibility attributed to the first node to be the clusterhead for the third node, wherein the fourth responsibility is based on the similarity between the first node and the third node, and wherein the fourth availability indicates an availability of the third node to be the clusterhead for the first node;

wherein the first processor is further effective to;

receive the third responsibility and the third availability from the second processor;

determine that the second node is a first clusterhead for the first node based on the first responsibility, third responsibility, first availability and third availability, wherein the first clusterhead is configured to communicate on behalf of the first node; and

store an indication of the first clusterhead in the first memory;

wherein the third processor is further effective to;

receive the second responsibility and the second availability from the first processor;

determine that the first node is a second clusterhead for the third node based on the second responsibility, fourth responsibility, second availability and fourth availability, wherein the second clusterhead is configured to communicate on behalf of the third node; and

send a message to the first node, wherein the message is effective to indicate a selection of the first node to be a second clusterhead for the third node.

17. The system as recited in claim 16, wherein the first processor is effective to, after the second processor receives the first responsibility and the first availability:

send a fifth responsibility and a fifth availability to the second node, wherein the fifth responsibility indicates a responsibility attributed to the second node to be the clusterhead for the first node, wherein the fourth availability indicates an availability of the first node to be the clusterhead for the second node;

wherein the second processor is effective to, after the first processor receives the third responsibility and the third availability;

receive the fifth responsibility and the fifth availability; and

send a sixth responsibility and a sixth availability to the first node,

wherein the sixth responsibility indicates a responsibility attributed to the first node to be the clusterhead for the second node, wherein the sixth availability indicates an availability of the second node to be the clusterhead for the first node;

wherein the first processor is effective to;

receive the sixth responsibility and the sixth availability; and

determine the first clusterhead for the first node based on the fifth responsibility, the fifth availability, the sixth responsibility and the sixth availability.

18. The system of claim 16, wherein the first processor of the first node is further effective to:

update the similarity between the first and second nodes based on the third responsibility and the third availability received from the second node;

update the first responsibility based on the updated similarity;

detect a convergence associated with the first responsibility, the third responsibility, the first availability, and the third availability, wherein the determination that the second node is the first clusterhead for the first node is performed in response to the detection of the convergence.