Patent ID: 7738402

Claim:
A method for organizing a plurality of communication devices of an ad hoc communication system into a communication network, each device having a transmission range, the method comprising the steps of: organizing the devices into one or more communication graphs, each communication graph comprising one or more nodes, each node representing a device of the system and an edge joining two nodes indicating that the two nodes are in each other's transmission range, wherein at least one of the graphs is a rooted tree, and wherein the devices are organized into a rooted tree in an inductive process comprising: (a) for one or more pairs of nodes consisting of a first node and a second node, the first and second nodes being in each other's transmission range, forming a rooted tree consisting of the first and second nodes, designating one of the first and second nodes as the tree root, and assigning coordinates to the first and second nodes in the rooted tree; and (b) for each pair of a first rooted tree and a second rooted tree, the first rooted tree having a first node and the second rooted tree having a second node, the first and second nodes being in each other's transmission range, merging the first and second trees into a single tree, and reassigning coordinates to one or more nodes in the single tree; and routing a communication session from a calling node to a called node, the calling node and the called node being nodes in a rooted tree of nodes of the system, wherein the session is routed along a route from the calling node to the tree root and from the tree root to the called node, seeking a shortcut in the route, the shortcut being a path from a first node in the route to a second node in the route and consisting of one or more edges not included in the rooted tree, and routing the session from the calling node to the first node of the route along the rooted tree, from the first node of the route to the second node of the route along the shortcut, and from the second node of the route to the called node along the rooted tree.