Protocol and structure for self-organizing network

• US 20040003111A1
• Filed: 04/19/2002
• Published: 01/01/2004
• 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: Huang, Jian, Maeda, Masahiro, Callaway, Edgar H. Jr., Shi, Qicai, Huang, Yan, Bourgeois, Monique, Chen, Priscilla
• Granted Patent: US 7,171,476 B2
• Time in Patent Office: Days
• US Class Current: 709/237
• CPC Class Codes: H04L 1/1607 Details of the supervisory signal
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/026 Details of "hello" or keep-alive messages
• CPC Class Codes: H04L 45/03 by updating link state protocols
• CPC Class Codes: H04L 45/46 Cluster building
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 76/10 Connection setup
• 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

Abstract

A cluster tree network formed by self-organization of a number of nodes. The method of self-organization includes processes for cluster formation, cluster network maintenance, intra-cluster communication. In the cluster formation process, each node discovers if any neighboring node is a cluster head or if any node is already a member of a cluster (thus making it a networked node), and if a cluster head or a networked node is discovered, each node establishes a communication link with the cluster head or the networked node. If no cluster head or networked node is discovered, the node itself becomes a cluster head. The network is maintained by each node periodically broadcasting a HELLO message to neighboring nodes, receiving responses to the HELLO message and updating a neighbor list in accordance with responses to the HELLO message. Multi-cluster networks are also provided using the processes of inter-cluster network formation, inter-cluster network maintenance, and inter-cluster communication. The resulting network has one or more clusters of nodes, each with a cluster head and a number of member nodes, each assigned a node identifier by the cluster head. In a multi-cluster network, a designated device assigns identifies to each cluster head in the network. Border nodes, which are members of at least two clusters, act as routers connecting the clusters and relaying information packets between the clusters.

Claims

1. A node structure comprising a plurality of nodes, wherein a first node of the plurality of nodes is directed by a computer program to associate with a cluster of nodes in order to form a network by:

discovering if any neighboring node is a cluster head;

if a cluster head is discovered, establishing a communication link with the cluster head; and

if no cluster head is discovered, directing the node to become a cluster head.

2. A structure in accordance with claim 1, wherein the discovering comprises listening for a HELLO message for a predetermined period of time.

3. A structure in accordance with claim 1, wherein the plurality of nodes includes a cluster head and the first node of the plurality of nodes contains a link-state list in a memory and wherein the establishing a communication link with the cluster head comprises:

obtaining an identifier of the cluster head; and

updating the link state list with the identifier of the cluster head.

4. A structure in accordance with claim 1, wherein, if no neighboring node is a cluster head, the computer program is further operable to direct the first node to broadcast a HELLO message to neighboring nodes.

5. A structure in accordance with claim 4, wherein if a neighboring node responds to the HELLO message, the computer program is operable to direct the node in establishing communication with the neighboring node.

6. A structure in accordance with claim 5, wherein the cluster head has a cluster head identifier and a link state list stored in a memory and wherein the establishing communication with the neighboring node comprises:

providing the neighboring node with a node identifier;

providing the neighboring node with the cluster head identifier; and

updating the link-state list with the node identifier.

7. A structure in accordance with claim 6, wherein, if the size of the cluster has reached a defined limit, the node identifier is a predetermined temporary node identifier that directs the neighboring node to stop responding to HELLO messages from the cluster head.

8. A structure in accordance with claim 1, wherein the plurality of nodes includes a cluster head and the computer program is further operable to direct the first node to link with a second node by:

receiving a HELLO message broadcast by the cluster head;

transmitting the HELLO message to neighboring nodes;

receiving a CONNECTION REQUEST message from the second node;

transmitting a NODE IDENTIFIER REQUEST to the cluster head;

receiving a NODE IDENTIFIER RESPONSE from the cluster head; and

transmitting a CONNECTION RESPONSE message to the second node.

9. A structure in accordance with claim 8, wherein if the cluster has reached a defined limit the node identifier response from the cluster head includes a predetermined temporary node identifier that directs the second node to stop sending CONNECTION REQUEST messages to the first node.

10. A structure in accordance with claim 1, wherein the computer program is further operable to direct the first node periodically to broadcast a HELLO message to neighboring nodes and to update a neighbor list stored in memory according to any responses to the HELLO message.

11. A structure in accordance with claim 10, wherein a node is removed from the neighbor list if it does not respond to the HELLO message within a specified time.

12. A structure in accordance with claim 10, wherein if a response to the HELLO message is received from a node in a different cluster, the cluster identifier of the responding node is add to the neighbor list.

13. A structure in accordance with claim 10, wherein the first node is not a cluster head and the computer program is further operable to direct the first node to broadcast the HELLO message to neighboring nodes in response to a HELLO message from the cluster head.

14. A structure in accordance with claim 1, wherein the plurality of nodes includes a cluster head, the first node has a neighbor list stored in memory and the computer program is further operable to direct the first node periodically to send a link-state report that contains its neighbor list to the cluster head.

15. A structure in accordance with claim 14, wherein, based upon one or more link-state reports received from neighboring nodes, the computer program is further operable to direct the cluster head to generate a topology list stored in memory and to send a TOPOLOGY UPDATE message to neighboring nodes.

16. A structure in accordance with claim 15, wherein the topology list is generated by selecting the route between the cluster head and a neighboring node that uses the smallest number of nodes.

17. A structure in accordance with claim 15, wherein the topology list is updated if a node fails to send a link-state report.

18. A structure in accordance with claim 1, wherein the computer program is operable to direct the first node to send data in a frame comprising:

the data;

a cluster head device identifier;

a frame type indicator;

a receiving node identifier;

a destination node identifier; and

a source node identifier.

19. A structure in accordance with claim 18, wherein the data is sent to a node in a different cluster and wherein the frame further comprises:

a transmitting node identifier;

a destination cluster head identifier; and

a source cluster head identifier.

20. A structure in accordance with claim 1, wherein the computer program is operable to direct the first node to process a received information packet having a Cluster Head Identifier, a Frame Type, a Receiving Node Identifier and a Destination Node Identifier, by:

checking the Cluster Head Identifier;

checking the Frame Type;

checking the Receiving Node Identifier; and

checking the Destination Node Identifier;

wherein the packet is accepted if the Cluster Head Identifier, the Receiving Node Identifier and the Destination Node Identifier match those of the first node and the Frame Type indicates that the packet contains a data message.

21. A structure in accordance with claim 20, wherein if the Cluster Head Identifier and the Receiving Node Identifier match those of the first node and the Frame Type indicates that the packet contains a data message, but the Destination Node Identifier is that of a different node, the Receiving Node Identifier of the packet is updated with the identifier of the first node, the packet is forwarded on the structure and an acknowledgement message is sent.

22. A structure in accordance with claim 20, wherein the packet is accepted if the Cluster Head Identifier matches that of the first node, the Frame Type indicates that the packet contains a data message and the Receiving Node Identifier indicates that the packet contains a broadcast message.

23. A structure in accordance with claim 22, wherein the information packet includes a Source Node Identifier, and the accepted broadcast message is forwarded to the structure if the Source Node Identifier is that of the parent node of the first node.

24. A structure in accordance with claim 1, wherein the plurality of nodes includes one or more clusters, each cluster comprising a node that is a cluster head and one or more member nodes linked to the cluster head.

25. A structure in accordance with claim 24, wherein the plurality of nodes further comprises a designated device directed by a computer program that is operable to direct the designated device to assign a cluster identifiers to the cluster heads of the one or more clusters.

26. A structure in accordance with claim 24, wherein the plurality of nodes includes a border node that is a member of at least two clusters, and wherein the border node act as router connecting the clusters and relaying information packets between the clusters.

27. A method for self-organization of a plurality of nodes to form a network comprising a cluster, the method comprising one or more of the processes of cluster formation, cluster network maintenance, intra-cluster communication, wherein, for a node of the plurality of nodes:

the process of cluster formation comprises;

discovering if any neighboring node is a cluster head;

if the cluster head is discovered, establishing a communication link with the cluster head; and

if no cluster head is discovered, directing the node of the plurality of nodes to become the cluster head,

the process of cluster network maintenance comprises;

periodically broadcasting a HELLO message to neighboring nodes;

receiving responses to the HELLO message; and

updating a neighbor list in accordance with responses to the HELLO message

and the process of intra-cluster communication comprises;

receiving an information packet having a Cluster Head Identifier, a Frame Type, a Receiving Node Identifier and a Destination Node Identifier;

checking the Cluster Head Identifier;

checking the Frame Type;

checking the Receiving Node Identifier;

checking the Destination Node Identifier;

accepting the packet if the Cluster Head Identifier, the Receiving Node Identifier and the Destination Node Identifier match those of the node and the Frame Type indicates that the packet contains a data message.

28. A method in accordance with claim 27, wherein the discovering in the process of cluster formation comprises listening for a HELLO message for a predetermined period of time.

29. A method in accordance with claim 27, wherein the establishing a communication link with the cluster head in the cluster formation process comprises:

obtaining an identifier of the cluster head; and

updating a link-state list with the identifier of the cluster head.

30. A method in accordance with claim 27, wherein the cluster formation process further comprises broadcasting a HELLO message to neighboring nodes from the cluster head.

31. A method in accordance with claim 30, wherein the cluster formation process further comprises establishing communication between the cluster head and a neighboring node if the neighboring node responds to the HELLO message.

32. A method in accordance with claim 31, wherein the cluster head has a cluster head identifier and a link-state list and wherein the establishing communication with the neighboring node in the cluster formation process comprises:

providing the neighboring node with a node identifier;

providing the neighboring node with the cluster head identifier; and

updating the link state list with the node identifier.

33. A method in accordance with claim 32, wherein, if the size of the cluster has reached a defined limit, the node identifier is a predetermined temporary node identifier that directs the neighboring node to stop responding to HELLO messages from the cluster head.

34. A method in accordance with claim 27, wherein the plurality of nodes includes a cluster head and the cluster formation process further comprises establishing a link between a first node and a second node by:

receiving a HELLO message broadcast by the cluster head;

transmitting the HELLO message to neighboring nodes;

receiving a CONNECTION REQUEST message from the second node;

transmitting a NODE IDENTIFIER REQUEST to the cluster head;

receiving a NODE IDENTIFIER RESPONSE from the cluster head; and

transmitting a CONNECTION RESPONSE message to the second node.

35. A method in accordance with claim 34, wherein, if the cluster has reached a defined limit, the node identifier response from the cluster head includes a predetermined temporary node identifier that directs the second node to stop sending CONNECTION REQUEST messages to the first node.

36. A method in accordance with claim 27, wherein the process of cluster network maintenance further comprises a node of the plurality of nodes:

periodically broadcasting a HELLO message to neighboring nodes;

receiving responses to the HELLO message; and

updating a neighbor list in accordance with the responses to the HELLO message.

37. A method in accordance with claim 36, further comprising removing a node from the neighbor list if it does not respond to the HELLO message within a specified time.

38. A method in accordance with claim 36, further comprising adding the cluster identifier of the responding node to the neighbor list if a response to the HELLO message is received from a node in a different cluster.

39. A method in accordance with claim 38, wherein the node of the plurality of nodes is not a cluster head and the node broadcasts the HELLO message to neighboring nodes in response to a HELLO message from the cluster head.

40. A method in accordance with claim 27, wherein the plurality of nodes includes a cluster head and the process of cluster network maintenance further comprises a node of the plurality of nodes periodically sending a link-state report that contains its neighbor list to the cluster head.

41. A method in accordance with claim 40, wherein the process of cluster maintenance further comprises:

the cluster head generating a topology list based upon one or more link-state reports received from neighboring nodes; and

the cluster head sending a TOPOLOGY UPDATE message to neighboring nodes.

42. A method in accordance with claim 40, wherein the topology list is generated by selecting the route between the cluster head and a neighboring node that uses the smallest number of nodes.

43. A method in accordance with claim 41, wherein the process of cluster maintenance further comprises updating the topology list if the node fails to send a link-state report within a specified time.

44. A method in accordance with claim 27, wherein the process of intra-cluster communication further comprises:

updating the Receiving Node Identifier of a packet with the identifier of the node;

forwarding the packet on the network; and

sending an acknowledgement message;

if the Cluster Head Identifier and the Receiving Node Identifier match those of the node and the Frame Type indicates that the packet contains a data message, but the Destination Node Identifier is that of a different node.

45. A network in accordance with claim 27, wherein the process of intra-cluster communication further comprises accepting a packet if the Cluster Head Identifier matches that of the node, the Frame Type indicates that the packet contains a data message and the Receiving Node Identifier indicates that the packet contains a broadcast message,

46. A method in accordance with claim 45, wherein the information packet includes a Source Node Identifier, and the process of intra-cluster communication further comprises forwarding the accepted broadcast message to the network if the Source Node Identifier is that of the parent node of the node.

47. A method in accordance with claim 27, wherein the network comprises a plurality of clusters and a plurality of cluster heads and wherein the method further comprising one or more of the processes of inter-cluster network formation, inter-cluster network maintenance, and inter-cluster communication.

48. A method as in claim 47, wherein the network further comprises a designated device and the process of inter-cluster network formation comprises:

the designated device sending a HELLO message to neighboring nodes;

if a cluster head of the plurality of cluster heads receives the HELLO message;

the designated device assigning a cluster identifier to the cluster head; and

the cluster head informing its member nodes of the cluster identifier; and

if a member node receives the HELLO message;

the member node adding the cluster identifier of the neighboring node from the parent cluster to its neighbor list;

the member node reporting the neighbor list to the cluster head;

the cluster head designating the member node as a border node; and

the designated device assigning a cluster identifier to the cluster head via the border node.

49. A method as in claim 48, wherein the designated device assigning a cluster identifier to the cluster head comprises:

the cluster head sending a CONNECTION REQUEST message to the designated device;

the designated device sending a CONNECTION RESPONSE message to the cluster head;

the cluster head sending an ACK message to the designated device;

the cluster head sending an CLUSTER IDENTIFIER REQUEST message to the designated device; and

the designated device sending a CLUSTER IDENTIFIER RESPONSE message to the cluster head.

50. A method as in claim 48, wherein the designated device assigning a cluster identifier to the cluster head via the border node comprises:

the cluster head sending a NETWORK CONNECTION REQUEST message to the border node;

the border node sending a CONNECTION REQUEST message to the designated device, or to its parent node that belongs to the parent cluster;

the designated device, or the parent node from the parent cluster, sending a CONNECTION RESPONSE message to the border node;

the border node sending an ACK message to the designated device, or to the parent node from the parent cluster;

the border node sending an CLUSTER IDENTIFIER REQUEST message to the designated device;

the designated device sending a CLUSTER IDENTIFIER RESPONSE message to the border node; and

the border node sending a NETWORK CONNECTION RESPONSE message to the cluster head.

51. A method as in claim 47, wherein a node of the plurality of nodes is a designated device and the process of inter-cluster network formation comprises:

each cluster head in the plurality of nodes periodically sending a LINK STATE REPORT to the designated device;

the designated device calculating a tree route for the network; and

the designated device sending a NETWORK TOPOLOGY UPDATE message to each cluster head;

52. A method as in claim 51, wherein the process of inter-cluster network formation further comprises each cluster head updating a list of identifiers of parent clusters, child/lower clusters and border nodes when a NETWORK TOPOLOGY UPDATE message is received.

53. A method as in claim 48, wherein the cluster head requests a cluster identifier from the designated device via at least one of an intermediate cluster head and a border node.

54. A method as in claim 48, wherein the designated device assigns a cluster identifier to a cluster head via at least one of an intermediate cluster head and a border node.

55. A method as in claim 51, wherein a node of the plurality of nodes is a backup designated device and the process of inter-cluster network maintenance further comprises the backup designated device periodically duplicating the list of cluster ID and network link-state information of the designated device.