Adaptive topology discovery in communication networks
First Claim
1. A method carried out by a plurality of nodes of a communication network at least a portion of which is an ad hoc network in which at least some messages are communicated between originating nodes and destination nodes without being routed via any intermediate nodes, the method comprising carrying out an exhaustive topology discovery of at least a portion of said ad hoc network,wherein said exhaustive topology discovery comprises discovering all of the nodes of at least said portion of said ad hoc network, and all of the links between each pair of such nodes,wherein information identifying all of the discovered nodes and all of the discovered links is collected by an individual one of the nodes of the communication network,wherein two or more of said discovered links are wireless links,wherein said discovering comprises a diffusion phase and a subsequent gathering phase,wherein said diffusion phase comprisesa) a first one of the nodes of said communication network broadcasting a topology discovery request,b) each of second nodes that receive said topology discovery request recording said first node as its parent and broadcasting said topology discovery request modified to identify said first node as its parent,c) each of third nodes that did not receive the topology discovery request broadcasted by the first node but did receive a modified version thereof broadcasted by one of said second nodes,i) recording that one of said second nodes as its parent andii) broadcasting said topology discovery request modified to identify said one of said second nodes as its parent,and wherein said diffusion phase further comprises each node that had broadcasted a modified version of said topology discovery request rebroadcasting said modified version if that node has not received an acknowledgment message within a predetermined time after having broadcast said modified version.
1 Assignment
0 Petitions
Accused Products
Abstract
A topology discovery process is used to discover all of the links in an ad hoc network and thereby ascertain the topology of the entire network. One of the nodes of the network, referred to as the coordinator, receives the topology information which can then be used to, for example, distribute a routing table to each other node of the network. The process has a Diffusion phase in which a k-resilient mesh, k>1, is created by propagating a topology request message through the network. Through this process, the nodes obtain information from which they are able to discern their local neighbor information. In a subsequent, Gathering phase, the local neighbor information is reported upstream from a node to its parents in the mesh and thence to the parents'"'"' parents and so forth back to the coordinator. The robustness of the Diffusion phase is enhanced by allowing a node to have more than one parent as well as by a number of techniques, including use of a so-called diffusion acknowledgement message. The robustness of the Gathering phase is enhanced by a number of techniques including the use of timeouts that ensure that a node will report its neighbor information upstream even if it never receives neighbor information from one or more downstream neighbors and the use of a panic mode that enhances the probability that a node will get its neighbor information, and its descendents'"'"' neighbor information, reported upstream even if that node has lost connectivity with all of its parents.
-
Citations
23 Claims
-
1. A method carried out by a plurality of nodes of a communication network at least a portion of which is an ad hoc network in which at least some messages are communicated between originating nodes and destination nodes without being routed via any intermediate nodes, the method comprising carrying out an exhaustive topology discovery of at least a portion of said ad hoc network,
wherein said exhaustive topology discovery comprises discovering all of the nodes of at least said portion of said ad hoc network, and all of the links between each pair of such nodes, wherein information identifying all of the discovered nodes and all of the discovered links is collected by an individual one of the nodes of the communication network, wherein two or more of said discovered links are wireless links, wherein said discovering comprises a diffusion phase and a subsequent gathering phase, wherein said diffusion phase comprises a) a first one of the nodes of said communication network broadcasting a topology discovery request, b) each of second nodes that receive said topology discovery request recording said first node as its parent and broadcasting said topology discovery request modified to identify said first node as its parent, c) each of third nodes that did not receive the topology discovery request broadcasted by the first node but did receive a modified version thereof broadcasted by one of said second nodes, i) recording that one of said second nodes as its parent and ii) broadcasting said topology discovery request modified to identify said one of said second nodes as its parent, and wherein said diffusion phase further comprises each node that had broadcasted a modified version of said topology discovery request rebroadcasting said modified version if that node has not received an acknowledgment message within a predetermined time after having broadcast said modified version.
-
3. A method carried out by a plurality of nodes of a communication network at least a portion of which is an ad hoc network in which at least some messages are communicated between originating nodes and destination nodes without being routed via any intermediate nodes, the method comprising carrying out an exhaustive topology discovery of at least a portion of said ad hoc network,
wherein said exhaustive topology discovery comprises discovering all of the nodes of at least said portion of said ad hoc network, and all of the links between each pair of such nodes, wherein information identifying all of the discovered nodes and all of the discovered links is collected by an individual one of the nodes of the communication network, wherein two or more of said discovered links are wireless links, wherein said discovering comprises a diffusion phase and a subsequent gathering phase, wherein said diffusion phase comprises a) first ones of said nodes of said communication network broadcasting respective topology discovery requests, b) at least a second node that receives said topology discovery requests recording each of said first nodes as its parents and broadcasting the topology discovery request received from each said first node modified to identify that node as its parent, c) each of third nodes that did not receive the topology discovery requests broadcasted by the first nodes but did receive a modified version thereof broadcasted by said second node, i) recording said second node as its parent and ii) broadcasting said topology discovery request modified to identify said second node as its parent, wherein said diffusion phase further comprises each of the nodes of the communication network that receive a version of said topology discovery request identifying itself as the parent of the sending node recording that sending node as its child, and wherein said gathering phase comprises a) each of said third nodes that did not receive the topology discovery request transmitting to each of its parents a gathering response that at least includes that third node'"'"'s neighbor information, and b) said second node transmitting to at least one of said first ones of said nodes a gathering response that includes that second node'"'"'s neighbor information and further includes all of its children'"'"'s neighbor information received by said second node in a gathering response from those children, c) the neighbor information of a node including an identification of that node'"'"'s parents and children, if any, and further includes identification of other nodes with which that node is linked.
-
7. A method carried out by a plurality of nodes of a communication network at least a portion of which is an ad hoc network in which at least some messages are communicated between originating nodes and destination nodes without being routed via any intermediate nodes, the method comprising carrying out an exhaustive topology discovery of at least a portion of said ad hoc network,
wherein said exhaustive topology discovery comprises discovering all of the nodes of at least said portion of said ad hoc network, and all of the links between each pair of such nodes, wherein information identifying all of the discovered nodes and all of the discovered links is collected by an individual one of the nodes of the communication network, wherein two or more of said discovered links are wireless links, wherein said discovering comprises a diffusion phase and a subsequent gathering phase, wherein said diffusion phase comprises a) a first one of the nodes of said communication network broadcasting a topology discovery request, b) each of second nodes that receive said topology discovery request recording said first node as its parent and broadcasting said topology discovery request modified to identify said first node as its parent, c) each of third nodes that did not receive the topology discovery request broadcasted by the first node but did receive a modified version thereof broadcasted by one of said second nodes, i) recording that one of said second nodes as its parent and ii) broadcasting said topology discovery request modified to identify said one of said second nodes as its parent, wherein said diffusion phase further comprises each of the nodes of the communication network that receive a version of said topology discovery request identifying itself as the parent of the sending node recording that sending node as its child, and wherein said gathering phase comprises a) at least individual ones of the nodes of the communication network transmitting to each of their parents a gathering response that identifies those individual nodes'"'"' neighbor information and further identifies any other nodes'"'"' neighbor information that those individual nodes receive in gathering responses from their children, b) the neighbor information of a node including an identification of that node'"'"'s parents and of its children, if any, and further includes identification of other nodes with which that node is linked.
-
11. A method carried out by a plurality of nodes of a communication network at least a portion of which is an ad hoc network in which at least some messages are communicated between originating nodes and destination nodes without being routed via any intermediate nodes, the method comprising carrying out an exhaustive topology discovery of at least a portion of said ad hoc network,
wherein said exhaustive topology discovery comprises discovering all of the nodes of at least said portion of said ad hoc network and all of the links between each pair of such nodes, wherein information identifying all of the discovered nodes and all of the discovered links is collected by an individual one of the nodes of the communication network, wherein two or more of said discovered links are wireless links, wherein said discovering comprises a diffusion phase and a subsequent gathering phase, wherein said diffusion phase comprises a) a first one of the nodes of said communication network broadcasting a topology discovery request, b) each of second nodes that receive said topology discovery request recording said first node as its parent and broadcasting said topology discovery request modified to identify said first node as its parent, c) each of third nodes that did not receive the topology discovery request broadcasted by the first node but did receive a modified version thereof broadcasted by one of said second nodes, i) recording that one of said second nodes as its parent and ii) broadcasting said topology discovery request modified to identify said one of said second nodes as its parent, and wherein each of the nodes of the communication network that receives a modified version of a topology discovery request that that node had itself sent broadcasts an acknowledgment message upon receipt of said modified version from another node and wherein each of the nodes of the communication network that broadcasts a topology discovery request retransmits it if does not receive an acknowledgment message in response.
-
12. A method for use by a first node of a communication network comprising a plurality of nodes, said first node being a wireless node and at least a portion of said communication network being an ad hoc network in which at least some originating and destination nodes communicate messages between one another that are not routed via any intermediate nodes, the method comprising
receiving a request message from at least two other nodes in said network, recording each said other node as concurrently being parents of said first node, broadcasting a modified version of each received request message, said modified version identifying a respective one of said other nodes as a parent of said first node and identifying said first node as the node sending said modified version, receiving a version of each said request message in which said first node is identified as the parent of the node sending that version of that request message, recording the sending node as a child of said first node, receiving individual response messages from respective children of said first node, each response message including neighbor information of the respective child, and transmitting to each said other node a response message that includes the neighbor information of all of said children and the neighbor information of said first node, the neighbor information of a node including an identification of that node'"'"'s parents and of its children, if any, and further includes identification of other nodes with which that node is linked.
-
16. A wireless node for operating within a communication network, at least a portion of said communication network being an ad hoc network in which at least some originating and destination nodes communicate messages between one another that are not routed via any intermediate nodes, the wireless node including a processor and said wireless node having stored therein instructions that, when executed by the processor, cause the wireless node to respond to receipt of a request message from at least two other nodes in said network by
recording each said other node as concurrently being parents of said wireless node, and broadcasting a modified version of each received request message, said modified version identifying a respective one of said other nodes as a parent of said wireless node and identifying said wireless node as the node sending said modified version wherein said instructions further cause said wireless node to respond to receipt of a version of each said request message in which said wireless node is identified as the parent of the node sending that version of that request message by recording the sending node as a child of said wireless node, and wherein said instructions further cause said wireless node to respond to receipt of individual response messages from respective children of said wireless node, each response message including neighbor information of the respective child, by transmitting to each said other node a response message that includes the neighbor information of all of said children and the neighbor information of said wireless node, the neighbor information of a node including an identification of that node'"'"'s parents and of its children, if any, and further includes identification of other nodes with which that node is linked.
-
20. A computer-readable medium containing computer-readable instructions to perform a method within a wireless node operating within an ad hoc network in which at least some originating and destination nodes communicate messages between one another that are not routed via any intermediate nodes, the method comprising
receiving a request message from at least two other nodes in said network, recording each said other node as concurrently being parents of said wireless node, and broadcasting a modified version of each received request message, said modified version identifying a respective one of said other nodes as the parent of said wireless node and identifying said wireless node as the node sending said modified version, wherein said method further comprises responding to receipt of a version of each said request message in which said wireless node is identified as the parent of the node sending that version of that request message by recording the sending node as a child of said wireless node, and wherein said method further comprises causing said wireless node to respond to receipt of individual response messages from respective children of said wireless node, each response message including neighbor information of the respective child, by transmitting to each said other node a response message that includes the neighbor information of all of said children and the neighbor information of said wireless node, the neighbor information of a node including an identification of that node'"'"'s parents and of its children, if any, and further includes identification of other nodes with which that node is linked.
Specification