Protocol for self-organizing network using a logical spanning tree backbone

• US 6,982,960 B2
• Filed: 03/09/2001
• Issued: 01/03/2006
• Est. Priority Date: 03/09/2001
• Status: Expired due to Term

• Current Assignee: ARRIS Enterprises LLC (CommScope Holding Company, Inc.), Northwestern University
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Bourgeois, Monique J., Allen, Vernon A., Chen, Priscilla, O'Dea, Robert J., Hester, Lance E., Lee, Chung-Chieh
• Primary Examiner(s): NGUYEN, HANH N
• Application Number:
  US09/803,259
• Publication Number:
  US 20030235158A1
• Time in Patent Office: 1,761 Days
• Field of Search: 370/331, 370/332, 370/333, 370/328, 370/329, 370/255, 370/254, 370/256, 370/390, 370/392, 370/426, 370/389, 455/404.2, 455/421, 455/436
• US Class Current: 370/254
• CPC Class Codes: H04L 2001/0093 Point-to-multipoint
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 40/248 Connectivity information update
• CPC Class Codes: H04W 40/32 for defining a routing cluster membership
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

A network protocol for low-cost, low-power devices coupled to a self-organizing wireless network using a spanning tree backbone architecture is described. In this protocol, physical and logical network construction and maintenance operations, which supports efficient data routing in the network, are performed. The construction phase in conjunction with the maintenance phase insures the self-organizing capability of the network. At the same time, the maintenance operations provide a self-healing mechanism so that the network can recover from node failures and a self-updating mechanism so that the network can expand as more nodes enter the system. Also, the logical backbone hierarchy will facilitate multi-hop communication. The construction of a logical layered spanning tree backbone architecture from an underlying physical topology allows seamless data communication routing between all nodes in the network.

Claims

1. A method of maintaining a physical topology of a network, having a plurality of network nodes, and a logical topology representative of the physical topology, comprising:

a first network node receiving a first update message from a second network node of the plurality of network nodes within one hop of the first network node; and

if the second network node is not in a range list of the first network node and therefore a new neighbor of the first network node, updating the range list of the first network node to include the second network node;

wherein updating the range list of the first network node to include the second network node comprises;

the first network node transmitting a first reply message to the second network node;

the second network node receiving the first reply message from the first network node and adding the first network node to the range list of the second network node;

the second network node transmitting a first confirmation message to the first network node containing network topology information about the second network node; and

the first network node receiving the first confirmation message from the second network node and adding the second network node to the range list of first network node wherein in response to the second network node receiving the first reply message and prior to the second network node transmitting the first confirmation message, further comprising;

determining if a depth of the first network node from the root node is less than a minimum depth of an existing parent node of the second network node;

if the depth of the first network node from the root node is less than the minimum depth of the existing parent node of the second network node, further comprising;

determining if logical addressing is used in the network;

if logical addressing is not used further comprising;

assigning die first network node as a new parent node of the second network node;

the second network node transmitting a second confirmation message to the first network node;

the second network node transmitting a second update message to the plurality of network nodes containing information about the new parent node of the second network node;

if logical addressing is used, further comprising;

storing a logical address and an identifier of an old parent node of the second network node;

assigning the first network node as the new parent node of the second network node;

the second network node transmitting a second confirmation message to the first network node;

if the second network node receives a second reply message from the first network node in response to the second confirmation message, comprising;

the second network node updating a logical address of the second network node;

the second network node transmitting a third confirmation message to the first network node;

the second network node transmitting a second update message;

if the second network node does not receive the second reply message from the first network node in response to the second confirmation on message within a first time-out period, the second network node restoring the old parent node as parent of the second network node; and

if the depth of the first network node from the root node is not less than the minimum depth of the parent node of the second network node, the second network node transmitting the confirmation message.

2. A method of maintaining a physical topology of a network, having a plurality of network nodes, and a logical topology representative of the physical topology, comprising:

a first network node receiving a first update message from a second network node of the plurality of network nodes within communication range of the first network node;

if the second network node is contained within the range list of the first network node, then;

determining whether information contained in the first update message about the second network node matches information contained in the range list of the first network node about the second network node;

if the information contained in the first update message about the second network node does not match information contained in the range list of the first network node about the second network node, using the information contained the first update message about the second network node and the range list of the first network node to determine if an old parent node of the first network node provides the first network node with a minimum depth from a root node of the network and updating the first network node to have a new parent node if the old parent node does not provide the minimum depth from the root node; and

wherein the range list comprises routing information for only those nodes that are within one hop of the node;

wherein if the information contained in the first update message about the second network node does not match information contained in the range list of the first network node about the second network node, further comprising;

using the information contained in the first update message about the second network node and information contained in the range list of the first network node to determine a new minimum distance of the plurality of network nodes from the root node;

if the new minimum distance is less than an old minimum distance of the plurality of network nodes from the root node, further comprising;

assigning the second network node as a new parent node of the first network node;

the first network node transmitting a first confirmation message to the second network node containing a new depth of the first network node from the root node with the second network node as the new parent node;

determining if logical addressing is used in the network;

if logical addressing is not used, further comprising;

the first network node transmitting a second update message to the plurality of network nodes containing information about the new parent node of the first network node;

if logical addressing is used, further comprising;

determining whether the first network node has received a first reply message from the second network node;

if the first network node has not received the first reply message from the second network node, restoring a logical address and an identifier of the old parent node to the range list of the first network node; and

if the first network node has received the first reply message from the second network node, the first network node updating a logical address of the first network node, transmitting a second confirmation message to the second network node;

if the new minimum distance is greater than the old minimum distance from the root node, entering a recovery mode to assign the new parent node of the first network node.

3. The method of claim 2, wherein the recovery mode further comprises:

determining whether the new minimum distance of the plurality of network nodes from the root node is less than a depth of the first network node from the root node;

if the new minimum distance from the root node is less than a depth of the first network node from the root node, further comprising;

identifying a network node of the plurality of network nodes having the new minimum distance;

assigning the network node as the new parent node of the first network node;

the first network node transmitting a first confirmation message to the new parent node;

determining whether the network uses logical addressing;

if the network uses logical addressing, further comprising;

if the first network node has received a first reply message from the new parent node in response to the first confirmation message, the first network node updating a logical address of the first network node and transmitting a second confirmation message to the new parent node;

if the first network node has not received the first reply message from the new parent node, further comprising;

deleting the new parent node from the range list of the first network node;

determining whether the range list of the first network node is empty;

if the range list of the first network node is not empty, determining a second new parent node for the first network node based upon the minimum depth of the plurality of network nodes;

the first network node transmitting a second update message containing information about the new parent node of the first network node;

if the new minimum distance from the root node is not less than a depth of the lint network node from the root node or if the range list of the first network node is empty, further comprising;

setting the new parent node of the first network node to nil, the minimum depth of the plurality of network nodes to infinity, and the depth of the first network node from the root node to infinity;

the first network node transmitting a second update message containing information about the settings of the new parent node, the minimum depth, and the depth of the first network node;

if a third update message or a third reply message is received by the first network node from a third network node during a third time-out period, the first network node updating the range list of the first network node to include the third network node;

determining a new minimum depth of the plurality of network nodes;

if the new minimum depth is equal to infinity, activating a disconnect indicator of the first network node; and

if the new minimum depth is not equal to infinity, determining the new parent of the first network node.

4. The method of claim 3, wherein if the new minimum distance from the root node is less than the depth of the first network node, identifying the network node having the new minimum distance and having a minimum load value of the plurality of network nodes.

5. The method of claim 3, wherein deleting the new parent node from the range list of the first network node occurs after a second time-out period.

6. A method of maintaining a physical topology of a network, having a plurality of network nodes, and a logical topology representative of the physical topology, comprising:

a first network node of the plurality of network nodes receiving a reply message from a second network node of the plurality of network nodes that is within communication range of the first network node; and

the first network node adding network topology information of the second network node to a range list of the first network node, wherein the range list comprises routing and topological information for only those nodes that are within one hop of the node;

if a depth of the first network node from a root node of the network is greater than or equal to a minimum depth of the plurality of network nodes from the root node, the first network node transmitting a confirmation message to inform the second network node;

if the the of the first network node from the root node of the network is less than the minimum depth of the plurality of network nodes from the root node, further comprising;

if the network does not use logical addressing, comprising;

assigning the second network node as a new parent node of the first network node;

the first network node transmitting a second confirmation message to the second network node; and

the first network node transmitting a second update message to the plurality of network nodes containing information about the new parent node of the first network node;

if the network does use logical addressing, further comprising;

storing a logical address and an identifier of an old parent node of the first network node;

assigning the second network node as the new parent node of the first network node;

the first network node transmitting a second confirmation message to the second network node;

if the first network node receives a second reply message from the second network node in response to the second confirmation message comprising;

the first network node updating a logical address of the first network node;

the first network node transmitting a third confirmation message to the second network node; and

the first network node transmitting a second update message;

if the first network node does not receive the second reply message from the second network node in response to the second confirmation message within a first time-out period, the first network node restoring the old parent node as parent of the first network node and transmitting a second update message.

7. A method of maintaining a physical topology of a network, having a plurality of network nodes, and a logical topology representative of the physical topology, comprising:

a first network node of the plurality of network nodes receiving an update message containing network topology information of a second network node of the plurality of network nodes within communication range of the first network node;

adding the network topology information of the second network node to a range list if the network topology information is not contained within the range list;

if a depth of the second network node is different from the stored value in the first network node'"'"'s range list, the depth value of the second network node in the first network node'"'"'s range list is updated;

further comprising;

re-computing the minimum depth of the first network node, taken into account the new depth value of the second network node, to create a new minimum depth of the first network node;

if the new minimum depth is less than the original minimum depth, selecting the second network node as a parent of the first network node and updating network topology information of the first network node;

if the new minimum depth of the first node is greater than its original minimum depth, entering a recovery mode, wherein the recovery mode further comprises;

if an attempt to identify a third network node having a minimum depth to a root node of the network is successful, assigning the third network node as the parent of the first network node and updating network topology information of the second network node; and

if the third network node cannot be identified, activating a failure indicator of the first network node.

8. The method of claim 7, wherein the network topology information comprises depth, loading, and identifier information.