Method and apparatus for a communication network with nodes capable of selective cluster head operation

• US 7,203,729 B2
• Filed: 03/27/2002
• Issued: 04/10/2007
• Est. Priority Date: 04/20/2001
• Status: Active Grant

• Current Assignee: ARRIS Enterprises LLC (CommScope Holding Company, Inc.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Chen, Priscilla L., Huang, Yan, Hester, Lance E.
• Primary Examiner(s): Dharia, Rupal
• Assistant Examiner(s): Taylor, Nicholas R
• Application Number:
  US10/108,109
• Publication Number:
  US 20020169846A1
• Time in Patent Office: 1,840 Days
• Field of Search: 709/209
• US Class Current: 709/209
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/46 Cluster building
• CPC Class Codes: H04W 40/10 based on available power or energy
• CPC Class Codes: H04W 40/32 for defining a routing cluster membership
• CPC Class Codes: H04W 84/20 Master-slave selection or change arrangements
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

A communication device (111) determines whether to operate as a cluster head in a network of communication devices (100). The device performs a self-assessment regarding its ability to operate as a cluster head based on a formula that assigns weights to factors related to its capabilities and preferably its environment (410, 420, 430). The ability of the device is combined with a random value component in determining whether to operate as a cluster head (440). In the preferred embodiment, upon assumption of cluster head status, the device communicates with neighboring devices to signal its cluster head status, and to invite others to participate in the formation of a cluster.

Claims

1. A method for selecting a cluster head from among a plurality of communication nodes, the method comprising the steps of, at each of the plurality of communication nodes:

self-initiating a self-assessment of an ability level to operate as a cluster head;

obtaining at least two factors representative of a characteristic of at least one of the plurality communication nodes; and

operating as a cluster head based on an assessment of ability level derived using a formula that assigns weights to each of the at least two factors, and based on use of a random value component.

2. The method of claim 1, wherein the at least two factors are selected from the set of available energy, available processing capacity, and state of connectivity of a particular communication node.

3. The method of claim 2, wherein the at least two factors further comprise a factor related to energy availability of one or more neighboring communication nodes.

4. The method of claim 2, wherein the at least two factors further comprise a factor related to waiting time for establishing a connection with a cluster head.

5. The method of claim 2, wherein the at least two factors comprise at least two values related to available energy, available processing capacity, and state of connectivity for a particular communication node.

6. The method of claim 1, wherein the step of operating as a cluster head comprises the step of communicating to neighboring devices with a signal identifying the particular node as a cluster head.

7. The method of claim 6, wherein the step of operating as a cluster head further comprises the step of forming a cluster comprising neighboring nodes.

8. A communication device for selective operation as a cluster head in a communication network, comprising:

a transmitter;

a memory, comprising;

at least two factors representative of operational characteristics of the communication device;

operating instructions for self-initiating a self-assessment of ability level based on a formula that assigns different weights to each of the at least two factors in the communication device, and for determining cluster head status based on the ability level assessed; and

a controller operable to execute the operating instructions in the memory and to cause the transmitter to transmit a signal identifying the communication device as a cluster head in response to a determination of cluster head status.

9. The communication device of claim 8, further comprising a random value generator that operates to output a random value, wherein the controller is operable to execute the operating instructions in a manner that utilizes the random value in determining cluster head status.

10. The communication device of claim 9, wherein the memory farther comprises operating instructions for forming a cluster containing neighboring communication devices.

11. A method for selecting cluster heads from among a plurality of communication devices operating as potential nodes in an asynchronous network, the method comprising the steps of:

at each potential node of a plurality of potential nodes;

self-obtaining a set of capability values representing capabilities of the potential node;

obtaining a set of weight assignments corresponding to the set of capability values;

obtaining an ability level cite potential node by combining the set of capability values according to the set weight assignments;

determining cluster head status of the potential node based at least in part on a formula having inputs related to the ability level, a total number of potential nodes, and a total number of desired cluster heads; and

operating as a cluster head according to the cluster head status.

12. The method of claim 11, wherein the step of obtaining a set of capability values comprises the step of utilizing at least two of available energy, processing capacity, state of connectivity for the potential node, energy availability of one or more neighboring communication nodes, and waiting time for establishing a connection with a cluster head.

13. The method of claim 12, wherein the step of operating as a cluster head comprises the step of communicating to neighboring devices with a signal identifying the potential node as a cluster head.

14. The method of claim 13, wherein the step of operating as a cluster head further comprises the step of fanning a cluster comprising neighboring nodes.

15. The method of claim 14, further comprising the step of utilizing a random value in determining cluster head status.