Patent ID: 7366113

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