Ad hoc communication system and method for routing speech packets therein
First Claim
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 Assignments
0 Petitions
Accused Products
Abstract
A method for organizing a plurality of communication devices of an ad hoc communication system into a communication network. The devices are organized into one or more communication graphs where at least one of the graphs is a rooted tree. The invention also provides an ad hoc communication system wherein the devices are organized into one or more communication graphs, where at least one of the graphs is a rooted tree. A method for routing a communication session in the system is also provided where a session is routed from the calling node to the tree root and from the tree root to the called node. In a preferred embodiment, shortcuts are sought in the session route.
22 Citations
6 Claims
-
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. - View Dependent Claims (2, 3)
-
-
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. - View Dependent Claims (5, 6)
-
Specification