Method for low-energy adaptive clustering hierarchy

• US 7,035,240 B1
• Filed: 12/27/2000
• Issued: 04/25/2006
• Est. Priority Date: 12/27/2000
• Status: Expired due to Fees

• Current Assignee: Massachusetts Institute of Technology
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Chandrakasan, Anantha P., Balakrishnan, Hari, Heinzelman, Wendi B.
• Primary Examiner(s): Rao, Seema S.
• Assistant Examiner(s): MOORE JR, MICHAEL J
• Application Number:
  US09/749,332
• Time in Patent Office: 1,945 Days
• Field of Search: 370/338
• US Class Current: 370/338
• CPC Class Codes: H04W 48/08 Access restriction or access information delivery, e.g. discovery data delivery signalling during connection H04W76/00
• CPC Class Codes: H04W 52/0219 where the power saving management affects multiple terminals
• CPC Class Codes: H04W 52/0245 according to signal strength
• CPC Class Codes: H04W 52/0261 managing power supply demand, e.g. depending on battery level
• CPC Class Codes: H04W 74/04 Scheduled access hybrid access H04W74/02
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks
• CPC Class Codes: H04W 84/20 Master-slave selection or change arrangements
• CPC Class Codes: H04W 84/22 with access to wired networks
• CPC Class Codes: H04W 92/10 between terminal device and access point, i.e. wireless air interface
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

A method and network architecture for implementing an energy efficient network. The network includes a plurality of nodes that collect and transmit data that are ultimately routed to a base station. The network nodes form a set of clusters with a single node acting as a cluster-head. The cluster-head advertises for nodes to join its cluster, schedules the collection of data within a cluster, and then transmits the data to the base station. A cluster can intelligently combine data from individual nodes. After a period of operation, the clusters are reformed with a different set of nodes acting as cluster-heads. The network provides an increased system lifetime by balancing the energy use of individual nodes.

Claims

1. A method of forming a network from a plurality of nodes and a base station, the method comprising the steps of:

(a) identifying at least one node of the plurality of nodes to operate as a cluster-head including randomly selecting one of the plurality of nodes to be a cluster-head;

(b) forming a plurality of clusters from the plurality of nodes, each of the clusters having at least one cluster-head;

(c) transmitting data from at least one node in at least one of the plurality of clusters to the cluster-head in that cluster;

(d) transmitting data from at least one cluster-head to the base station; and

(e) identifying a different one of the plurality of nodes to operate as a cluster-head;

wherein the step of randomly selecting one of the plurality of nodes to be a cluster-head is based on a probabilistic function of an amount of energy remaining in each of the plurality of nodes.

2. The method of claim 1, wherein the step of forming a plurality of clusters further comprises the steps of:

advertising an availability of each of said plurality of cluster-heads; and

establishing a communication path between each of said plurality of cluster-heads and at least one of the plurality of nodes, not operating as a cluster-head, to form a cluster.

3. The method of claim 2 wherein the step of establishing a communication path between the cluster-head and each of the at least one of the plurality of nodes comprises the steps of:

transmitting a status signal from each one of said plurality of cluster-heads;

receiving at each of the plurality of nodes one or more of the status signals;

comparing, at each of the plurality of nodes, not operating as a cluster-head, signal strengths of the received one or more status signals; and

joining a particular one of the cluster-head'"'"'s cluster as a result of the comparison.

4. The method of claim 3, wherein the step of joining a particular cluster is based on a determination, by at least one of the plurality of nodes, of the cluster-head transmitting the status signal having a highest received signal strength.

5. The method of claim 2 further comprising the steps of:

generating at the cluster-head, a schedule having allotted slots for transmission;

transmitting data from at least one node to the cluster-head during the allotted slots;

receiving data in the cluster-head that are transmitted from at least one node; and

transmitting data from the cluster-head to the base station.

6. The method of claim 5, wherein the step of receiving data in the cluster-head further comprises the step of reducing data transmission latency by using application-specific data aggregation to reduce the amount of redundant data sent to the base station.

7. The method of claim 5, wherein the step of receiving data in the cluster-head further comprises the step of increasing the signal to noise ratio of the data sent to the base station by using application-specific data aggregation.

8. The method of claim 5, wherein the step of generating a schedule uses a time division multiplexing protocol.

9. The method of claim 5, further comprising the step of beamforming the data received from the plurality of nodes in the cluster.

10. The method of claim 1, wherein the step of forming a plurality of clusters further comprises the steps of:

collecting data on a status of each of the plurality of nodes;

assigning each of the plurality of nodes to a particular one of a plurality of clusters.

11. A method for forming a network from a base station and a plurality of nodes, the method comprising the steps of:

electing a cluster-head from the plurality of nodes;

establishing a communication path between first ones of the plurality of nodes and the cluster-head to form a cluster;

establishing a first round of data transmission;

transmitting from the first ones of the plurality of nodes to the cluster-head during the first data transmission round; and

transmitting data from the cluster-head to the base station during the first data transmission round;

establishing a second round of data transmission;

determining whether each node of the plurality of nodes has operated as a cluster-head;

electing a second set of cluster-heads wherein each node in the second set of cluster-heads has never before been a cluster-head;

forming a second set of clusters about the second set of cluster-heads;

electing a plurality of cluster-heads corresponding to a first set of cluster-heads for use during the first round of data transmission; and

establishing a communication path between each of the plurality of cluster-heads and at least one node of the plurality of nodes to form a first plurality of clusters.

12. The method of claim 11 wherein the step of electing a plurality of cluster-heads is performed by the base station.

13. The method of claim 12 wherein the base station elects cluster-heads by minimizing an energy required during the first round of data transmission.

14. The method of claim 11 wherein:

during the first round of data transmission, each of the at least one node in each cluster transmits data to the cluster-head of that cluster; and

each cluster-head transmits data to the base station during the first transmission round.

15. The method of claim 11 further comprising the steps of:

in each of a second set of clusters;

transmitting data from each node in the second set of clusters to the respective cluster heads; and

transmitting data from each of the second set of cluster-heads to the base station.

16. A method for forming a network from a base station and a plurality of nodes, the method comprising the steps of:

electing a cluster-head from the plurality of nodes;

establishing a communication path between first ones of the plurality of nodes and the cluster-head to form a cluster;

establishing a first round of data transmission;

transmitting from the first ones of the plurality of nodes to the cluster-head during the first data transmission round;

transmitting data from the cluster-head to the base station during the first data transmission round;

establishing a second round of data transmission;

determining an amount of energy remaining in each node of the plurality of nodes;

electing a second set of cluster-heads, wherein the election is based on the amount of energy remaining in each node of the plurality of nodes;

forming a second set of clusters about the second set of cluster-heads;

electing a plurality of cluster-heads corresponding to a first set of cluster-heads for use during the first round of data transmission; and

establishing a communication path between each of the plurality of cluster-heads and at least one node of the plurality of nodes to form a first plurality of clusters.

17. A network comprising:

a base station; and

a plurality of nodes comprising;

a cluster-head selector processor; and

a cluster selector processor, each cluster comprised of a subset of said plurality of nodes, and one of each of said subset of said plurality of nodes temporarily acting as a cluster-head, wherein each of said plurality of nodes has a limited amount of remaining energy; and

wherein the cluster-head selector processor selects each of said plurality of nodes as a cluster-head based on the limited amount of remaining energy in each of said plurality of nodes and a number of times each of said plurality of nodes has operated as a cluster head.

18. The network according to claim 17, wherein each of the plurality of nodes is in electrical communication with a sensor.

19. The network according to claim 17, wherein each of said plurality of nodes further comprises a sleep mode.

20. The network according to claim 17, wherein each of said plurality of nodes further comprises an adjustable transmission energy level.

21. The network according to claim 17, wherein each of said plurality of nodes further comprises a low energy mode, and a high energy mode.

22. The network according to claim 17, wherein each of said plurality of nodes further comprises a signal strength processor.

23. The network according to claim 22, wherein the cluster selector processor determines the cluster selection in response to a signal from the signal strength processor.

24. The network according to claim 17, wherein the base station selects each of said plurality of nodes to temporarily act as a cluster-head.

25. The network according to claim 17, wherein the base station determines which of each of said plurality of nodes is included in each temporary cluster.