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

• US 20030235158A1
• Filed: 03/09/2001
• Published: 12/25/2003
• Est. Priority Date: 03/09/2001
• Status: Active Grant

• Current Assignee: ARRIS Enterprises LLC (CommScope Holding Company, Inc.), Northwestern University
• Original Assignee: Northwestern University
• Inventors: OʼDea, Robert J., Lee, Chung-Chieh, Hester, Lance E., Allen, Vernon A., Bourgeois, Monique J., Chen, Priscilla
• Granted Patent: US 6,982,960 B2
• Time in Patent Office: Days
• US Class Current: 370/256
• 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 expanding a logical topology representative of a network having a plurality of network nodes to include a node added to the network, comprising:

identifying one or more neighboring nodes of the plurality of network nodes that are within communication range of the node;

obtaining network topology information of the one or more neighboring nodes;

from the network topology information of the one or more neighboring nodes identifying a neighboring node of the one or more neighboring nodes having a minimum depth from a root node of the network and assigning the neighboring node having the minimum depth from the root node as a parent node of the node; and

the node transmitting a broadcast confirmation message that informs the one or more neighboring nodes of an identifier of the parent node and a depth of the node from the root node.

2. The method of claim 1, wherein identifying the one or more neighboring nodes within communication range of the node comprises:

the node sending a hello message to the plurality of network nodes of the network;

upon receiving the hello message, the one or more neighboring nodes transmitting one or more corresponding reply messages to the node;

in response to receiving the one or more reply messages sent by the one or more neighboring nodes, the node adding the one or more neighboring nodes to a range list of the node;

3. The method of claim 1, further comprising:

in response to receiving the broadcast confirmation message, the one or more neighboring nodes adding the node to one or more corresponding range lists of the one or more neighboring nodes.

4. The method of claim 1, wherein identifying the one or more neighboring nodes within communication range of the node comprises:

the node transmitting a hello message to the plurality of network nodes of the network;

after a time-out period, determining whether the one or more neighboring nodes have transmitted one or more corresponding reply messages to the node;

if the one or more neighboring nodes have transmitted the one or more corresponding reply messages, the node adding the one or more neighboring nodes to a range list of the node; and

if the one or more neighboring nodes have not transmitted the one or more corresponding reply messages, activating a disconnect indicator of the node.

5. The method of claim 4, further comprising after activating the disconnect indicator:

re-positioning the node within the network and re-transmitting the hello message to the plurality of network nodes of the network.

6. The method of claim 4, wherein if the hello message is not received by the one or more neighboring nodes, repositioning the node within the network and re-transmitting the hello message.

7. The method of claim 1, wherein the network topology information comprises one or more of depth, loading, and identifier information.

8. The method of claim 1, wherein the depth of the node from the root node is one greater than the minimum depth of the parent node.

9. The method of claim 1, wherein if two or more of the neighboring nodes have the minimum depth from the root node, assigning a neighboring node of the two or more neighboring nodes having a least number of children nodes as the parent node of the node.

10. 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; 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.

11. The method of claim 10, 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 the first network node.

12. The method of claim 11, 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 the 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; and

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; and

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 message within a first time-out period, the second network node restoring the old parent node as parent of the second network node;

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.

13. 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; and

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

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 in 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.

14. The method of claim 13, 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.

15. The method of claim 14, 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 first 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.

16. The method of claim 15, 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.

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

18. 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 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; and

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

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 in 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.

19. 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 hello message from a second network node of the plurality of network nodes within communication range of the first network node, the hello message containing network topology information about the second network node; and

in response to receiving the hello message, the first network node transmitting a reply message containing network topology information about the first network node; and

the first network node updating a range list of the first network node to include the network topology information about the second network node and the second network node updating a range list of the second network node to include the network topology information about the first network node.

20. The method of claim 19, further comprising:

In response to receiving the reply message from the first network node, the second network node transmitting a broadcast confirmation message.

21. The method of claim 20, wherein upon receiving the broadcast confirmation message, the first network node updating a child list of the range list of the first network node.

22. 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.

23. The method of claim 22, further comprising:

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 depth 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.

24. 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 confirmation 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 updating a range list of the first network node to include network topology information about the second network node contained in the confirmation message.

25. The method of claim 24, wherein prior to the first network node updating the range list of the first network node to include network topology information about the second network node contained in the confirmation message, further comprising:

if the first network node determines from the confirmation message that the first network node has been picked as a parent node of the second network node, verifying that the second network node has selected a valid logical address of the second network node.

26. The method of claim 25, wherein if the second network node has not selected a valid logical address, the first network node choosing a new logical address of the second network node;

and

the first network node transmitting a reply message to the second network node containing the new logical address of the second network node.

27. The method of claim 25, further comprising:

the first network node updating the range list of the first network node to include the new logical address of the second network node after receiving a second confirmation message from the second network node.

28. The method of claim 25, further comprising:

the second network node updating a range list of the second network node to include the new logical address transmitted from the first network node.

29. The method of claim 24, wherein prior to the first network node updating the range list of the first network node to include network topology information about the second network node contained in the confirmation message, further comprising:

if the first network node determines from the confirmation message that the first network node has been picked as a parent node of the second network node and that the confirmation message is not a broadcast confirmation message, verifying that the second network node has selected a valid logical address of the second network node;

if the second network node has not selected a valid logical address, the first network node choosing a new logical address of the second network node;

the first network node transmitting a reply message to the second network node containing the new logical address of the second network node.

30. 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:

examining a range list of a first network node of the plurality of network nodes, having one or more entries that correspond to one or more network nodes of the plurality of network nodes, to determine which of the one or more network nodes that the network node has not heard from for a period of time;

deleting from the range list each network node of the one or more network nodes that the network node has not heard from for the period of time to generate an updated range list of the first network node.

31. The method of claim 30, further comprising:

transmitting an update message containing information about the updated range list of the first network node.

32. The method of claim 30, further comprising:

if a parent node of the first network node was deleted from the range list, selecting a new parent node of the first network node from the plurality of network nodes having a minimum depth to a root node of the network.

33. The method of claim 32, wherein the new parent node of the first network node has the minimum depth to the root node and a minimum load value of the plurality of network nodes.

34. The method of claim 30, further comprising:

activating a disconnect LED of the first network node if the range list is empty after deleting from the range list each network node of the one or more network nodes which the network node has not heard from for the period of time.

35. The method of claim 30, if a parent node of the first network node was not deleted from the range list and there is a vacancy in a child address list of one or more children of the first network node, further comprising:

reassigning the logical addresses of the one or more children in the child address list.

36. The method of claim 35, further comprising the first network node sending to the one or more children one or more corresponding reply messages informing the one or more children of the reassigned logical addresses.

37. A method of adding a node, having an activated proximity indicator and placed within proximate communication range of one or more of a plurality of network nodes of a network, to a physical topology of the network and a logical topology representative of the physical topology, comprising:

receiving a first message containing network topology information of one or more neighboring nodes of the plurality of network nodes within communication range of the node;

from the network topology information, identifying a parent node of the one or more neighboring nodes having a minimum depth from a root node of the network, wherein if more than one node of the one or more neighboring nodes has the minimum depth the parent node has a minimum load of the one or more neighboring nodes; and

updating a range list of the node to include the identified parent node.

38. The method of claim 37, further comprising:

transmitting a second message identifying the parent node.

39. The method of 37, wherein prior to receiving the first message, further comprising:

the node sending a message to inform the one or more neighboring nodes of the presence of the node in the network.

40. A method of expanding a logical topology representative of a network having a plurality of network nodes to include a node added to the network, comprising:

transmitting a hello message to a plurality of neighboring nodes of the plurality of network nodes that are within communication range of the node;

receiving a plurality of reply messages from the plurality of neighboring nodes containing network topology information about the plurality of neighboring nodes; and

updating a range list of the node to include the network topology information about the plurality of neighboring nodes.

41. The method of claim 40, further comprising:

transmitting a broadcast confirmation message confirming that the network topology information about the plurality of neighboring nodes has been updated in the range list of the node.

42. A node operable to be placed within proximate communication range of a network node of a plurality of network nodes of a network and added to a physical topology and a logical topology of the network, comprising:

a receiver of the node operable to receive a first message from the network node containing network topology information of the network node; and

a processing element of the node, coupled to the receiver, operable to identify a parent node of the plurality of network nodes having a minimum depth from a root node of the network and within communication range of the node and operable to update a range list of the node to include the parent node and the network topology information of the network node.

43. The node of claim 42, further comprising:

a transmitter of the node, coupled to the processing element, operable to transmit a second message identifying the parent node.

45. The node of claim 42, further comprising:

a proximity indicator coupled to the processing element of the node operable to indicate when the node is within communication range of a network node.

44. The node of 43, wherein prior to the receiver receiving the first message, the transmitter sends a message to inform one or more neighboring nodes of the plurality of network nodes within communication range of the node of the presence of the node in the network.

46. 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:

in response to receiving a hello message from a new node wishing to join the network, a network node of the plurality of network nodes transmitting a reply message to the new node;

in response to the network node receiving a broadcast confirmation message from the new node, the network node adding the new node to a range list of the network node.

47. The method of claim 46, wherein in response to the network node receiving the broadcast confirmation message from the new node, further comprising:

updating a child list of the range list.

48. A network node of a plurality of network nodes of a network, comprising:

a receiver of the network node operable to receive from a second network node of the plurality of network nodes within communication range of the node a incoming message containing network topology information of the second network node; and

a processing element of the network node, coupled to the receiver, operable to update a range list of the network node to include the network topology information of the second network node, determine a parent node of the network node having a minimum depth from a root node of the network, and generate one or more out-going messages containing network topology information of the network node.

49. The network node of claim 48, further comprising:

a transmitter of the network node, coupled to the processing element, operable to transmit the one or more out-going message to the plurality of network nodes of the network.

50. The network node of claim 48, further comprising:

a proximity indicator, coupled to the processing element of the network node, operable to indicate when the network node is within communication range of the plurality of network nodes.

51. 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.

52. The method of claim 51, further comprising:

if the first network node has not received the update message from the second network node within a predetermined period of time, comprising;

deleting the network topology information of the second network node from the range list;

determining whether the second network node was the parent of the first network node; and

if the second network node was the parent of the first network node, selecting a new parent of the first network node having a minimal depth to the root node, from the plurality of network nodes.

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