Ad hoc communication system and method for routing speech packets therein

• US 20060153099A1
• Filed: 12/21/2005
• Published: 07/13/2006
• Est. Priority Date: 12/23/2004
• Status: Active Grant

• Current Assignee: Carmel-Haifa University Economic corp. Ltd. (University of Haifa)
• Original Assignee: Carmel-Haifa University Economic corp. Ltd. (University of Haifa)
• Inventors: Feldman, Sharoni, Asher, Yosi Ben
• Granted Patent: US 7,738,402 B2
• Time in Patent Office: Days
• US Class Current: 370/254
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/122 by minimising distances, e.g. by selecting a route with minimum of number of hops
• CPC Class Codes: H04L 45/32 Flooding denial of service attacks H04L63/1458
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 40/24 Connectivity information management, e.g. connectivity discovery or connectivity update
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

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.

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 a step 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.

2. The method according to claim 1 further comprising assigning coordinates to one or more nodes in a rooted tree.

3. The method according to claim 2 wherein coordinates are assigned to nodes in a rooted tree in an inductive process comprising:

(a) Assigning coordinates <

0>

to the tree root;

(b) for a node v having coordinates <

x>

, numbering the sons of the node; and

(c) assigning the coordinates <

x,i>

to son i of the node v.

4. The method according to claim 1 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.

5. The method 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 method according to claim 1 further comprising 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.

7. The method according to claim 6 further comprising seeking a shortcut in the route, the short cut 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.

8. The method according to claim 7 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.

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

10. The system according to claim 9 wherein coordinates are assigned to one or more nodes in a rooted tree.

11. The system according to claim 10 wherein coordinates are assigned to nodes in a rooted tree in an inductive process comprising:

(a) Assigning coordinates <

0>

to the tree root;

(b) for a node v having coordinates <

x>

, numbering the sons of the node; and

(c) assigning the coordinates <

x,i>

to son i of the node v.

12. The system according to claim 9 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.

13. The system according to claim 12 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.

14. The system according to claim 12 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.

15. The system according to claim 14 further configured to seek a shortcut in the route, the short cut 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.

16. The system according to claim 15 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.

17. A method for routing a communication session in an ad hoc communication system 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, comprising routing the session from the calling node to the tree root and from the tree root to the called node.

18. The method according to claim 17 further comprising seeking a shortcut in the route, the short cut 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.

19. The method according to claim 18 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.