US 7,171,476 B2 · Protocol and structure for self-organizing network

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.

Claims51

Dependent claims

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 within communication range of the first node 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 during association of the first node with the cluster of nodes to form the network;
and
if no cluster head is discovered, directing the first node itself to become a cluster head during association of the first node with the cluster of nodes to form the network.

1 more element

A method for self-organization of a plurality of nodes to form a network comprising a cluster, the method comprising the processes of cluster formation, cluster network maintenance and 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.

14 more elements

Dependencies are inferred from the claim text.

Protocol and structure for self-organizing network

Life of this patent

Protocol and structure for self-organizing network

Life of this patent

Abstract

Claims51