Ad hoc communication system and method for routing speech packets therein

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

2. The method according to claim 1 further comprising repeating step (b) until there does not exist 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 with the first and second nodes being in each other's transmission range.

3. The method according to claim 1 , wherein each node maintains a list of its neighbors and a list of its neighbor's neighbors, and a shortcut is introduced into the route between a first node on the root and a second node on the route where the first node is either a neighbor of the second node or a neighbor of a neighbor of the second node.

4. An ad hoc communication system comprising a plurality of communication devices, each device having a transmission range, wherein the devices are organized 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, 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

wherein said system is configured to route 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; and

further configured to seek 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 the session is routed 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.

5. The system according to claim 4 further comprising repeating step (b) until there does not exist 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 with the first and second nodes being in each other's transmission range.

6. The system according to claim 4 , wherein each node maintains a list of its neighbors and a list of its neighbor's neighbors, and a shortcut is introduced into the route between a first node on the root and a second node on the route where the first node is either a neighbor of the second node or a neighbor of a neighbor of the second node.