Method for clustering devices in machine-to-machine networks to minimize collisions

• US 9,225,606 B2
• Filed: 04/03/2013
• Issued: 12/29/2015
• Est. Priority Date: 04/03/2013
• Status: Active Grant

• Current Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Original Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Inventors: Guo, Jianlin, Orlik, Philip, Parsons, Kieran
• Primary Examiner(s): Nguyen, Phuoc
• Assistant Examiner(s): ZAND, DAVOUD AMAN
• Application Number:
  US13/855,825
• Publication Number:
  US 20140304383A1
• Time in Patent Office: 1,000 Days
• Field of Search: 709/208, 709/209, 709/223, 709/226, 709/238, 709/240, 709/248
• US Class Current: 1/1
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04W 4/70 Services for machine-to-machine communication [M2M] or machine type communication [MTC]
• CPC Class Codes: H04W 84/20 Master-slave selection or change arrangements
• CPC Class Codes: Y04S 40/00 Systems for electrical power generation, transmission, distribution or end-user application management characterised by the use of communication or information technologies, or communication or information technology specific aspects supporting them

Abstract

Nodes in a network are clustered by first determining, in each node, a cluster head capability (CHC). The CHC is broadcasting, directly or indirectly, until all nodes have received the CHCs. Each node nominates, one or more candidate cluster heads based on the CHCs, and then, in each node, at least one cluster head is selected from the candidate cluster head nodes based on maximal CHCs.

Claims

1. A method clustering nodes in a network, comprising the steps of:

determining, in each node, a cluster head capability (CHC);

broadcasting, directly or indirectly by each node, the CHC until all nodes have received the CHCs;

maintaining, in each node, a set (NB) that includes neighboring nodes j of the node i, wherein each entry in the set NB(i) has a format (ID, D, CHC), where ID represents an identifier of the neighboring node j, D represents a distance between the node i and the neighboring node j, and the CHC represents the cluster head capability of node j and wherein the CHC is CHCi=C(i)/Cmax*Ei*ERi, where C(i) is a capability classification of node i, Cmax is a maximal classification index, E(i) is a percentage of remaining energy of node i, and ER(i) is an expected reliability of node i when the node i is the cluster head;

nominating, in each node, one or more candidate cluster heads based on the CHCs; and

selecting, in each node, at least one cluster head from the one or more candidate cluster head nodes, wherein the at least one cluster head has a maximal CHCs for the one or more candidate cluster head nodes.

2. The method of claim 1, wherein the nodes are heterogeneous.

3. The method of claim 1, wherein the distance D is

4. The method of claim 1, further comprising:

broadcasting a cluster formation (CF) to initiate the clustering by a cluster manager node.

5. The method of claim 4, wherein the cluster manger is a gateway node.

6. The method of claim 5, wherein the cluster manager has a highest capability classification.

7. The method of claim 1, wherein a distance between any two cluster heads is greater than half a transmission range.

8. The method of claim 1, wherein the one or more cluster heads include one primary cluster head and one or more secondary cluster heads.

9. The method of claim 1, wherein the selecting is distributed over all nodes in the network.

10. The method of claim 1, wherein a distance between the node and the cluster head is less than half the transmission range.

11. The method of claim 10, wherein none of the cluster heads is within half the transmission range of the node, the node requests one of the candidate cluster heads to be the cluster head for that node.

12. The method of claim 1, wherein all nodes with the same cluster head can receive data form each other.

13. The method of claim 1, wherein the cluster head reserves a time slot to communicate with the nodes that selected the cluster head.

14. The method of claim 7, wherein any two nodes that at a distance greater than ˜

3R/2, wherein R is a transmission range, can communicate concurrently.

15. The method of claim 1, wherein a probability of selecting the cluster head is based on the capability classification.

16. The method of claim 1, wherein the classes in a high to low order are associated with a gateway, a smart meter data concentrator or factory machine controller, factory machines, smart meters, large scale sensors, and small scale sensors.

17. The method of claim 1, wherein a particular node rejects being the candidate cluster head.