Main content

Alert message

Project Name: Ad hoc communication system and method for routing speech packets

 

Inventors: Dr. Sharoni Feldman, Dr. Yosi Be-Asher

 

FIELD OF THE INVENTION

This invention generally relates to communication networks, and more specifically to ad hoc communication networks.

 

Description 

 

This is 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.

 

BACKGROUND OF THE INVENTION

An ad hoc communication system consists of a plurality of mobile wireless communication devices, also referred to herein simply as "devices", "users" or "nodes". Unlike a cellular telephone network, an ad hoc network does not rely on a set of fixed base stations to follow the movement of the devices or to route a connection between two devices. Since the transmission range of each device is limited, a device in the network can communicate directly only with other devices that are within its transmission range. Since the devices are mobile, the set of devices within the transmission range of a given device changes dynamically over time. Typically, devices continually enter and leave a given device's transmission range. Thus, as a device moves it may break communication with some devices while creating new connections with other devices. Every device periodically sends a "hello" message that is received by all devices within its transmission range. Every node receives hello messages from the nodes within its transmission range so that every node is periodically updated of the nodes within its transmission range.

The basic communication structure is therefore a dynamic graph in which each communication device is a node and an edge between two nodes indicates that the two nodes are in each other's transmission range. Each device can also act as a router by transferring speech or data packets from a first device in its range to a second device in its range when the first and second devices are not within each other's range. Thus, two devices can exchange speech packets only if there is a path of edges in the graph joining the two devices. Since new edges constantly emerge in the graph while other edges are deleted, a routing protocol is required that can cope with this dynamic situation, while attempting to optimize the allocation of device resources in order to maximize the amount and length of communication sessions available to the devices.

Ad hoc communication systems are classified according to the routing protocol that is used. In a table-driven routing protocol, each node maintains a table specifying a route to every other node in the network. When a first node (referred to herein as the "calling node") initiates a session to a second node (referred to herein as the "called node"), the route from the calling node to the called node specified in the calling node's table is invoked.

In a search-driven routing protocol, for each communication session requested by a calling node, a search is performed to locate a path from the calling to the called node. The calling node broadcasts a route request packet to its neighbors. Every node receiving this request that is not the called node adds its own identity to the request and re-broadcasts the message to its neighbors. When the request reaches the called node, the full route appears in the message. Typically, each search requires flooding the network with search messages until the called node is reached and a routing path has been found. The algorithms in this class may need a quadratic number of messages (in the number of nodes) to perform a search for a route. The drawback of search driven protocols lies in the delay that occurs before a call session can start while the path search is being conducted.

The AODV (On-demand Distance Vector) routing algorithm (C. E. Perkins, and E. M. Royer. "Ad-hoc On-Demand Distance Vector Routing," Second IEEE Workshop on Mobile Computing Systems and Applications, pp. 90-100, February 1999.) combines on demand search with recent destination routing information. A search for a route to a given called node is performed by flooding, but each node maintains a list of all its recent routings, so that the flooding can be reduced when it reaches an intermediate node that has the destination in its recent routing list. However, a burst of route request messages may flood the system especially in large condensed networks when many nodes try to create sessions simultaneously.

Another type of ad-hoc algorithm uses the GPS coordinates of each node to forward packets from one node to the neighboring node having the shortest Euclidian distance to the destination. The routing is oblivious and thus potentially more efficient than the one used in the AODV type of algorithm. Using GPS can be regarded as a way of assigning grid coordinates in the field to every node and using the grid metric to select the shortest routing paths.

Rao et al. (A. Rao, S. Ratnasamy, C. Papadimitrou, S. Shenker, I. Stoica, "Geographic Routing withhout Location Information", ACM MobiCom 2003.) discloses use of virtual coordinates that approximate geographical coordinates without using GPS. The nodes are embedded in a grid wherein Euclidian distances in the plane are replaced by connectivity distances in the dynamic communication graph. The algorithm has three stages: 1) the nodes on the perimeter are identified, 2) the virtual coordinates of the perimeter are computed, and 3) based on the perimeter, virtual coordinates of internal nodes are computed. Virtual coordinates are computed using a relaxation method wherein each node updates its coordinates based on the coordinates of its neighbors.

SUMMARY OF THE INVENTION

As used in the following description and set of claims, the term "ad hoc communication system" refers to a communication system comprising a plurality of mobile wireless communication devices where the system does not comprise any fixed base stations that follow the movement of the devices or that route a connection between two devices in the system.

In one of its aspects, the present invention provides a method for organizing communication devices of an ad hoc communication system into one or more communication graphs. In accordance with the invention, the devices are organized into one or more graphs, where at least one of the graphs is a rooted tree. An edge in a rooted tree between two nodes indicates that the two nodes are within each other's transmission range. In general however, a rooted tree will not contain all possible direct communication links between a node and its neighbors. In a preferred embodiment of the invention, the devices are organized into one or more graphs, all of which are rooted trees.

In another of its aspects, the invention provides an ad hoc communication system, in which the communication devices are organized into one or more graphs, with at least one of the graphs being a rooted tree.

In another of its aspects, the present invention provides a method for routing a communication session between a calling node and a called node in an ad hoc communication system. In a rooted tree, a unique path exists joining each node to the tree root, and, each node can be assigned a unique set of coordinates specifying the path from the tree root to the node. Thus, in one embodiment of this aspect of the invention, the communication devices are organized into one or more rooted trees and a communication session between a calling node and a called node in the same rooted tree is routed from the calling node to the tree root along the unique path joining them, and then from the root to the called node along the unique root joining them. In a preferred embodiment, one or more short cuts in this route are sought. A short cut is a path joining a first node in the tree to a second node in the tree, where edges in the path join devises in each other's transmission range but are not edges in the rooted tree. The communication session is then routed from the calling node to the first node in the shortcut along the tree, then to the last node in the short cut along the short cut, and from there to the called node along the tree.

A rooted tree with shortcuts is better suited to handle the dynamic case of ad hoc networks than a grid metric. In particular, adding a new node to an existing rooted tree requires only changing the coordinates of that node alone while adding a new node to an existing grid may require changing the coordinates of most of the grid nodes. When a node leaves a tree, it will be necessary to update the coordinates of every node in that node's sub-tree, however, usually the number of updates required for this is significantly less than that needed in the case of a grid metric. In particular adding and deleting several nodes at the same time is more complex in grids than in trees as the coordinates of most of the nodes in the grid are affected by all changes in the grid structure, while in trees the changes in two disjoint sub-trees do not affect one another.

Only nodes that belong to the same tree can create communication sessions among themselves. Complete connectivity is achieved when a session can be created between any two nodes in the field, and this is possible only when all of the nodes are organized into a single tree. Since a node may break away from a tree or fuse with a tree, the connectivity of the nodes changes dynamically. Thus, in a preferred embodiment of the invention, two separate trees fuse together into a single tree whenever possible in order to organize the nodes into a minimal number of rooted trees so as to ensure maximal connectivity. Every node that receives a hello message checks to which tree the node that sent the message belongs. If the nodes belong to different trees, they will initiate a fusion process that fuses the two trees into a single tree.

A simulator was developed and used to compare the performance of the algorithm of the invention with that of the AODV algorithm. As demonstrated below, results obtained using the simulator show that the method of the invention for ad hoc routing provided a larger number and duration of communication sessions available to the nodes in comparison to AODV under the same conditions.

Thus, in one of its aspects, the present invention provides 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.

In another of its aspects, the invention provides 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.

In yet another of its aspects, the invention provides 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.