Protocol for a self-organizing network using a logical spanning tree backbone
First Claim
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.
8 Assignments
0 Petitions
Accused Products
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.
-
Citations
53 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
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. - View Dependent Claims (11, 12)
-
-
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. - View Dependent Claims (14, 15, 16, 17)
-
-
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. - View Dependent Claims (20, 21)
-
-
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. - View Dependent Claims (23)
-
-
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. - View Dependent Claims (25, 26, 27, 28, 29)
-
-
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. - View Dependent Claims (31, 32, 33, 34, 35, 36)
-
-
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. - View Dependent Claims (38)
-
-
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. - View Dependent Claims (41)
-
-
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. - View Dependent Claims (43, 45)
-
-
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. - View Dependent Claims (47)
-
-
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. - View Dependent Claims (49, 50)
-
-
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. - View Dependent Claims (52, 53)
-
Specification