Multiplex communications – Communication over free space – Having a plurality of contiguous regions served by...
Reexamination Certificate
1999-12-06
2003-03-18
Maung, Nay (Department: 2681)
Multiplex communications
Communication over free space
Having a plurality of contiguous regions served by...
C370S254000, C370S351000
Reexamination Certificate
active
06535498
ABSTRACT:
BACKGROUND
The present invention relates to routing in ad hoc networks. More particularly, the present invention relates to route updating in ad hoc networks.
Conventional networking protocols are based on the characteristics and/or features of fixed networks. In fixed networks, the network configuration typically does not change. Although nodes can be added and removed in fixed networks, the route traveled by data packets between two nodes typically does not change. The disadvantage is that fixed networks cannot be easily reconfigured to account for increases in data traffic, also called system loading. Accordingly, when system loading increases for one node, the surrounding nodes are likely to experience increased delays in the transmission and reception of data.
In contrast to fixed networks, ad-hoc networks are dynamic. An ad-hoc network is formed when a number of nodes decide to join together to form a network. Since nodes in ad-hoc networks operate as both hosts and routers, ad-hoc networks do not require the infrastructure required by fixed networks. Accordingly, ad-hoc networking protocols are based upon the assumption that nodes may not always be located at the same physical location.
Bluetooth is an exemplary ad-hoc networking technology. Bluetooth is an open specification for wireless communication of both voice and data. It is based on a short-range, universal radio link, and it provides a mechanism to form small ad-hoc groupings of connected devices, without a fixed network infrastructure, including such devices as printers, PDAs, desktop computers, FAX machines, keyboards, joysticks, telephones or virtually any digital device. Bluetooth operates in the unlicenced 2.4 GHz Industrial-Scientific-Medical (ISM) band.
FIG. 1
illustrates a Bluetooth piconet. A piconet is a collection of digital devices, such as any of those mentioned above, connected using Bluetooth technology in an ad-hoc fashion. A piconet is initially formed with two connected devices, herein referred to as Bluetooth devices. A piconet can include up to eight Bluetooth devices. In each piconet, for example piconet
100
, there exists one master Bluetooth unit and one or more slave Bluetooth units. In
FIG. 1
Bluetooth unit
101
is a master unit and unit
102
is a Bluetooth slave unit.
According to Bluetooth technology a slave unit can only communicate directly with a master unit.
FIG. 2
illustrates a piconet with a master unit
201
and a plurality of slave units
202
-
208
arranged in a star network topology. If slave unit
202
wishes to communicate with slave unit
206
, slave unit
202
would have to transmit the information it wished to communicate to master unit
201
. Master unit
201
would then transmit the information to slave unit
206
.
A scatternet is formed by multiple independent and unsynchronized piconets.
FIG. 3
illustrates an exemplary scatternet
300
. In
FIG. 3
, piconet
1
includes a master node
303
and the slave nodes
301
,
302
and
304
; piconet
2
includes the master node
305
and the slave nodes
304
,
306
,
307
and
308
; and piconet
3
includes the master node
309
and the slave nodes
308
,
310
and
311
. To implement a scatternet it is necessary to use nodes which are members of more than one piconet. Such nodes are herein referred to as forwarding nodes. If, for example, node
301
wishes to communicate with node
310
, then nodes
304
and
308
might act as forwarding nodes by forwarding the packets between the two piconets and in particular between nodes
301
and
310
. For example, node
301
transfers the information to the master node of piconet
1
, node
303
. Master node
303
transmits the information to forwarding node
304
. Forwarding node
304
then forwards the information to master node
305
, which in turn, transmits the information to forwarding node
308
. Forwarding node
308
forwards the information to master node
309
which transmits the information to the destination node
310
.
In general, the protocols which govern the formation and/or updating of routes in an ad-hoc network may be classified as either proactive or reactive. Proactive routing protocols attempt to update and maintain routes between nodes, including routes which are not currently in use. Typically, proactive routing protocols react to network topology changes, even if there is no current traffic which is affected by the topology change. To update and maintain the routes between nodes in an ad-hoc network employing proactive routing, each node periodically transmits control information to other nodes in the network. However, this requires a large amount of signaling, which consumes precious bandwidth and leads to network congestion. The network congestion, in turn, results in greater transmission delays for packets traveling through the network.
In contrast to proactive routing protocols, reactive routing protocols establish routes only when there is an immediate need to transmit packets. Moreover, reactive routing protocols only maintain information about routes which are currently being used for transmitting data packets. Accordingly, reactive protocols result in less network signaling, and hence, less network congestion and less delay due to the congestion as compared to proactive routing protocols.
To establish a route from a source node to a destination node using reactive protocols, a request message is transmitted from the source node to the destination node. Initially, the source broadcasts the request message to all neighboring nodes, i.e., all nodes adjacent to the source node. If a neighbor node receiving the request message is neither the destination node nor has a valid route to the destination node, the neighbor node rebroadcasts the request message to all of its neighbor nodes, excluding the node from which it received the request message. In a network which operates using reactive routing protocols, a neighbor node may have a valid route to the destination cached in a routing table if the neighbor node is routing data packets to the destination node for another source node.
The destination node, or a node with a valid cached route to the destination node upon receiving the request message, does not rebroadcast the request message. This limits the amount of network flooding caused by the rebroadcasting of the request message. Additionally, the destination node generates a unicast reply message and transmits the reply message back to the source node. Although the source node may receive more than one reply message, the source node uses the first reply message received to begin transmitting data packets to the destination node. In accordance with reactive routing, the source node will only request a new route when the actual route being used is broken.
Routing in ad-hoc networks can be performed as either source routing or distance vector routing. In source routing an entire route from the source node to the destination node is received in the reply message. Accordingly, only the source needs to keep track of the route between the source node and the destination node. When packets are sent from the source node to the destination node the entire route is specified in every packet.
In distance vector routing as the reply message is sent from the destination node to the source node each intermediate node stores route information in routing tables. Accordingly, the source node will only need to place the destination node address in each packet for the packet to reach the destination node.
There are several drawbacks of conventional reactive ad-hoc routing protocols, especially in regard to wireless ad-hoc networks such as Bluetooth networks. Typically, once a source node has established a route to a destination node the source node will continue to use the same route until node movement causes changes in the network topology that cause the route between the source node and the destination node to break. Accordingly, the conventional reactive ad-hoc routing protocols do not adjust to topology changes which do not lead to an actual link breakage.
Johansson Per
Larsson Tony
Sörensen Johan
Burns Doane Swecker & Mathis L.L.P.
Gelin Jean A
Maung Nay
Telefonaktiebolaget LM Ericsson (publ)
LandOfFree
Route updating in ad-hoc networks does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Route updating in ad-hoc networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Route updating in ad-hoc networks will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3052722