CLUSTERHEAD SELECTION IN A COMMUNICATION NETWORK

• US 20120030342A1
• Filed: 07/28/2010
• Published: 02/02/2012
• Est. Priority Date: 07/28/2010
• Status: Active Grant

• 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: Willink, Patricia Janet, Baddour, Kareem Emile, Ureten, Oktay
• Granted Patent: US 9,288,126 B2
• Time in Patent Office: Days
• US Class Current: 709/224
• 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 availability indicates an availability of the first node to be the clusterhead for the second node;

receiving from a second node a second responsibility and a second availability at the first node, wherein the second responsibility indicates a responsibility attributed to the first node to be the clusterhead for the second node, wherein the second availability indicates an availability of the second node to be the clusterhead for the first node; and

determining, by the first node, the clusterhead based on the first responsibility, second responsibility, first availability and second availability.

2. The method as recited in claim 1, wherein the first and second responsibilities are based on a similarity between the first and the second node.

3. The method as recited in claim 2, wherein the similarity is based on shared communication frequencies between the first and the second node.

4. The method as recited in claim 2, wherein the similarity is based on a strength of a communication link between the first and the second node.

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

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

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

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

7. The method as recited in claim 6, further comprising adding a damping factor to the first responsibility, the second responsibility, the first availability and the second availability.

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

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

determining the clusterhead based on the self-similarity value.

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

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

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

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

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

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

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

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

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

13. 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 availability indicates an availability of the first node to be the clusterhead for the second node;

receive from a second node a second responsibility and a second availability at the first node, wherein the second responsibility indicates a responsibility attributed to the first node to be the clusterhead for the second node, wherein the second availability indicates an availability of the second node to be the clusterhead for the first node;

determine the clusterhead based on the first responsibility, second responsibility, first availability and second availability; and

store an indication of the clusterhead in the memory.

14. The node as recited in claim 13,

wherein the first and second responsibilities are based on a similarity between the first and the second node;

and

the similarity is based on shared communication frequencies between the first and the second node.

15. The node as recited in claim 13,

wherein the first and second responsibilities are based on a similarity between the first and the second node;

and

wherein the similarity is based on a strength of a communication link between the first and the second node.

16. The node as recited in claim 13, wherein the processor is further effective to:

determine a self-similarity value for the first node;

determine the clusterhead based on the self-similarity value.

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

18. The node as recited in claim 13, wherein the processor is further effective to:

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

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

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

19. 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;

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 second availability indicates an availability of the first node to be the clusterhead for the second node;

wherein the second processor is effective to

receive the first responsibility and the first availability; and

send a second responsibility and a second availability to the first node, wherein the second responsibility indicates a responsibility attributed to the first node to be the clusterhead for the second node, wherein the second 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 second responsibility and the second availability;

determine the clusterhead based on the first responsibility, second responsibility, first availability and second availability; and

store an indication of the clusterhead in the first memory.

20. The system as recited in claim 19,

wherein the first processor is effective to

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

wherein the second processor is effective to

receive the third responsibility and the third availability; and

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 second node, wherein the fourth 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 fourth responsibility and the fourth availability; and

determine the clusterhead based on the third responsibility, the third availability, the fourth responsibility and the fourth availability.