Multiplex communications – Communication over free space – Having a plurality of contiguous regions served by...
Reexamination Certificate
2000-11-01
2004-11-23
Ho, Duc (Department: 2665)
Multiplex communications
Communication over free space
Having a plurality of contiguous regions served by...
C370S401000, C370S428000
Reexamination Certificate
active
06822951
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
This invention relates to wireless networks, and more particularly to a routing method and apparatus for avoiding unnecessary retransmissions, such as those caused by loops, in a link-determined topology.
BACKGROUND OF THE INVENTION
Wireless networks include a vast variety of network configurations, all characterized by the transmission of data through the air rather than through a cable. Wireless networks may include LANs (local area networks) as well as WANs (wide area networks) or the upcoming versions of LANs known as PANs (personal area networks).
Much of today's wireless networking technology is directed to radio frequency (RF) signals, but microwave and infrared signals may also be used. Wireless communications can be passed with either analog or digital signaling.
“Packet radio” has been in use for many years, with packet radio networks comprised of conventional radios, each in communication with a computer and a modem. Messages are carried in packets and the radios forward each packet separately.
More recently, the transmission of packet data by radio has been accomplished with all kinds of radio-equipped computing equipment. Wireless network access is used by equipment such as 2-way data devices (messaging devices and personal digital assistants), data capable phones, and laptops and palmtops. Although each device may be mobile or stationary, by convention, they are often referred to as “stations”.
In a multi-hop network, each station participates in forwarding messages to other stations, thereby extending the communication range of each station.
For wireless packet networks, routing protocols designed for wired networks are not generally satisfactory. Various methods may be used to determine the best path between two wireless devices. One approach to routing is source routing, where the sender of a message includes the routing with the message. Another approach is referred to as link-state or link-determined routing, in which the best path is determined by a router that executes some sort of routing algorithm.
An example of a link-determined routing method, first applied for packet radio networks, is known as Radio Shortest Path First (RSPF) routing. Roughly described, the RSPF protocol is designed for use by Internet layer routing nodes in a packet radio network using the Internet Protocol (IP). It is a way to make IP work with packet radio.
The result of link-determined routing is a link topology, which may have loops and other problematic structures. The problems associated with such structures are manifested in situations such as contention control, when messages are to be retransmitted. If messages are simply retransmitted from device to device, loops can cause messages to be cycled endlessly through the network, causing problems. This is especially true when the communication range of the communicating devices is short relative to the maximum pairwise distance between devices.
SUMMARY OF THE INVENTION
One aspect of the invention is a method of routing messages in a wireless communications network having a number of wireless communications devices. At least some of the devices having computation resources, which permit the device to interpret and respond to messages. Transmissions from each device are synchronized, such that all transmissions occur simultaneously. At each receiving device, a routing unit performs the following operations: storing each last transmitted message; checking incoming messages for integrity, such that any message comprised of different transmissions is designated as a corrupt message; discarding any corrupt messages; delivering each non-corrupt incoming message to the computation resources; receiving a potential outgoing message from the computation resources, comparing each potential outgoing message with the last transmitted message; using a rules engine to determine whether the potential outgoing message should be transmitted.
It may be that the computation resources do not modify the message, such that the potential outgoing message is the same as the incoming message. The rules engine is programmed to apply the following rules: the device may transmit only in response to receiving a transmission; the device may only receive after transmitting; the device repeats a received transmission unless it is configured to respond to the transmission; and the results of the comparing step are used to prevent the device from repeating a transmission.
In accordance with the invention, each device in the network performs routing tasks at the link level. A designated root device performs additional routing tasks. Specifically, transmissions are synchronized among all devices. Each device follows a set of rules that result in alternating send-listen cycles, permit collisions to be detected, and avoid unnecessary retransmissions.
As a result of the synchronized device-based routing control, collisions are allowed to occur. This is in contrast to other “collision avoiding” routing methods. Unacceptable (corrupt) collisions (receiving different messages from multiple transmitters) are distinguished from acceptable collisions (receiving the same message from multiple transmitters). Unacceptable collisions may then be discarded, and acceptable collisions handled in a manner that avoids repeat transmissions.
An advantage of the invention is that it creates a tree-like topology and avoids loops associated with link-determined topologies. Routing is automatic; there is no need for routing tables. The computational cost at each device is low, and thus the invention may be inexpensively implemented.
REFERENCES:
patent: 5473612 (1995-12-01), Dehner et al.
patent: 5682382 (1997-10-01), Shepard
patent: 5926101 (1999-07-01), Dasgupta
patent: 6201811 (2001-03-01), Larsson et al.
patent: 6553020 (2003-04-01), Hughes et al.
Brady III W. James
Ho Duc
Moore J. Dennis
Telecky , Jr. Frederick J.
Texas Instruments Incorporated
LandOfFree
Method and apparatus for routing messages in a wireless network does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for routing messages in a wireless network, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for routing messages in a wireless network will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3300927