Method and apparatus for routing messages in a wireless network

ABSTRACT

A method and apparatus for routing messages in a wireless network. Transmissions from all devices are synchronized. Each device is equipped with a routing unit that checks incoming messages for integrity, discards “corrupt” messages, compares non-corrupt messages to the last transmitted message, and applies a set of rules to determine when and what the device should next receive or transmit. The synchronized transmissions and integrity checking process detect true collisions, which occur when multiple transmitters have attempted to send different messages to the same receiver. The comparing process ensures that messages are transmitted only if not previously transmitted, thereby avoiding loop problems.

INFORMATION

DETAILED DESCRIPTION OF THE INVENTION

This application claims priority under 35 USC § 119(e)(1) of provisional application No. 60/163,899 filed Nov. 5, 1999.

DETAILED DESCRIPTION OF THE INVENTION

The following description is in terms of a wireless LAN (local area network) having radio frequency transmissions. However, the same concepts could be extended to any wireless network.

FIG. 1 illustrates a wireless LAN , comprised of a number of wireless communications devices . All devices are equipped with a routing unit, discussed below in connection with FIG. 4, that implements the routing method described herein. This method may be generally characterized as link level routing. Any device may be designated as a root device, with additional functionality for performing additional routing tasks, which may be consistent with known routing protocols above the link level.

Transmissions within network are assumed to be RF (radio frequency) transmissions, or IR (infrared), and messages are transmitted as packets. Upon receiving a packet, each device demodulates and decodes the packet and performs store and forward processing. The packet address is used to determine which device is the destination for the packet.

An example of such a network is a network in which devices are personal computers, each equipped with a radio modem, in an office environment. However, devices may be any device capable of sending and receiving wireless packet data, and are assumed to have “computation resources” that may interpret and respond to messages transported in the packets.

Network is a multi-hop network, as indicated by the range of each device being shorter than the maximum pairwise distance between devices. Thus, each packet typically undergoes multiple hops before reaching a destination device.

FIG. 2 illustrates a link-determined topology of network . Unlike wired LANs, network does not have a physical topology. Rather, links are set up for a particular transmission, and define a topology for that connection.

As discussed in the Background, in a link-determined topology, it is desirable to avoid loops. This is especially true when the communication range of the communicating devices is short relative to the maximum pairwise distance between devices. If messages are simply retransmitted from device to device, loops can cause messages to be cycled endlessly through the network, causing problems. The potential for loops exists in network , as illustrated by FIGS. 1 and 2.

In the past, to avoid loops and other problematic routing structures, routing tables and other computationally-intensive mechanisms have been used to create an effective star or star/tree topology from the link topology. The following description sets out an alternative method, which creates a tree-like topology, independent of the link-topology, with any device designated as the root.

FIG. 3 illustrates the structure of a packet , which carries one or more messages to be communicated within network . Each packet has a predetermined temporal duration, T4, and is comprised of a predetermined number of submessages. Each submessage has a predetermined temporal duration, T1, T2, . . . A predetermined interval, T3, between messages permits computational resources of a receiving device to affect the content of the message, such as by adding content to a previously silent submessage.

The first submessage in a packet is a control message, generated by the root device of network . The control submessage contains the address of the destination device , as well as other control data, such as that used for error checking.

The other submessages in a packet are assigned to non-root devices as “slots” in a manner determined by the contents of the control submessage and the configuration of network . No more than one device is assigned to a submessage slot at any given time.

FIG. 4 illustrates a routing unit , implemented in each device . Routing unit is comprised of a check process, a compare process, a message store, and a rules engine, each of which may be implemented with conventional computer programming techniques and hardware. Additionally, a timer synchronizes transmission cycles. A receiver (RX) receives signals representing incoming packets, and as is inherent in wireless networks, may receive signals representing packets from more than one transmitter. This situation, where more than one transmitter is contending for the same receiver is referred to as “collision”. Check process checks the integrity of the message data. As explained below, if a receiving device's check process determines the message data to be “corrupt”, the receiving device ignores the received data.

Non-corrupt messages are delivered to the computational resources of device , which determine whether the message is one to which device may respond, and which may or may not add a response. The computational resources deliver a potential outgoing message (which is the same as the incoming message if no response is added) to compare process .

A message store unit stores each last transmitted message, and is updated every transmission. For each potential outgoing message, message store unit delivers the last transmitted message to the compare process . The compare process compares the potential outgoing message to the previously transmitted message. A rules engine uses the results of the comparison, and other conditions, to apply various rules that determine whether the message is to be transmitted.

Rules engine can be summarized as storing and applying the following set of rules on behalf of its associated device .

Rule 1: Unless you are the root device, speak only when spoken to.

Rule 2: If you have just spoken, be quiet and listen.

Rule 3: If you have nothing to add, repeat exactly what you heard.

Rule 4: If you are about to repeat yourself, be quiet.

Rules engine may be implemented as a state machine.

A timer is triggered by each incoming message at the receiver (RX) and has a period of T4. At time T4, transmitter (TX) transmits the message out of device . Thus, as indicated in FIG. 4, timer is enabled (triggered) by an incoming message to the receiver (R. After T4, a message may be transmitted by transmitter (TX) if (1) it has received an enable signal from timer. (meaning that T4 has elapsed), and (2) it has received a dsr (data set ready) signal from rules engine (meaning that there is a message to send). If device has a suitable time base, timer may be implemented with timing signals derived from device external to routing unit .

The transmission of each message from device is synchronized with that of other devices in network .

Thus, all timers begin and end their count of T4 at the same time. Re-synchronization occurs every other clock cycle (every time a message is received), and various known clock recovery techniques may be used to maintain synchronization in the interim. Furthermore, some inaccuracy is acceptable.

Because transmissions are synchronized, all transmitting devices transmit their respective packets at the same time. In accordance with Rule 2, each device listens for a cycle after transmitting, and thus operates on alternating send-receive cycles, each having a period of T4. Expressed in common communications parlance, messages are allowed to “collide”. However, routing unit distinguishes acceptable (non-corrupt) from unacceptable (corrupt) collisions. More specifically, as stated above, at the receiving device, the check process of the routing unit checks each incoming transmission (which may be a combination of messages) for integrity.

When two transmitting devices have transmitted to it at the same time, there are a number of possible scenarios. For purposes of simplicity, the non-control submessages in each packet are collectively referred to as the “Message”. At a given time, any two devices may transmit one of the following: Message A, Message B, or Silence. Silence is an acceptable (non-corrupt) message. The following possibilities exist:

Message A+Message A=>Message A

Message B+Message B=>Message B

Message A+Silence =>Message A

Message B+Silence =>Message B

Silence+Silence =>Silence

Message A+Message B=>Corrupt

Thus, in all but one case, the integrity of the combined message is preserved.

As explained in further detail below, in a given message, if any submessages are corrupt, the entire message is discarded, effectively deemed to be silence. Thus, for purposes of the invention, unless Message A and Message B are the same:

Message A+Message B=>Silence

As explained below, a corrupt message is discarded. The determination of whether subsequent transmissions are to occur to ensure that messages are eventually received at the intended destination is a matter to be resolved by the root device and the particular protocol of network .

A first example of the operation of routing unit is in the case of an incoming message that is Message A. After triggering timer , the message is checked for integrity by check process . Being non-corrupt, the message is passed to the computation resources of device . The resulting message is passed to compare unit . In accordance with Rule 4, if the message is not the same as the last transmitted message, it is passed to the transmitter, which is triggered by the expiration of timer .

As a second example, routing unit receives Message A and Message B at the same time. Check process determines the message to be corrupt and discards the message. Thus, the message is effectively a Silence message. In accordance with Rule 1, no message is transmitted.

As a third example, check process might determine the incoming message to be non-corrupt, but compare process might determine that an incoming message matches the previous transmission. In accordance with Rule 4, no message is transmitted.

FIGS. 5A-5G and FIGS. 6A-6G each illustrate how the invention operates so as to propagate multi-hop transmissions from a root node (or a node connected to the root node). Each set of figures illustrates the cycle-by-cycle propagation of messages. In accordance with Rule 1, each device other than the root device transmits only in response to receiving a message. In accordance with Rule 2, after transmitting a message, on the next T4 cycle, each device waits to receive a message rather than sending another message. Rules and are also illustrated as explained below.

FIGS. 5A-5G illustrate the operation of the invention in a network having six devices . Only the compare process of the routing unit of each device is illustrated. At each device , the state of the last message and the state of the current message are shown.

In this example, each device is a “node” of the link-determined topology. The topmost device (Node ) is the root device (or connected to the root). Node is configured to respond to an incoming Control Message X with a Response Message Y. The computation resources of each device are not shown, and communication with them is illustrated only for Nodes and .

In FIG. 5A, Node delivers Control Message X to Node . In FIG. 5B, in accordance with Rule 2, Node has transmitted Control Message X, which is received at Nodes and . At Node , its compare process determines that the received message is the same as the last message, and its rules engine applies Rule 4.

In FIG. 5C, Node has transmitted Message X in accordance with Rule 3. The message from Node is received at the Nodes and . Node applies Rule 4. Node , whose computation resources are configured to respond to Control Message X, delivers the message to its computational resources. In FIG. 5D, the computation resources of Node have added Response Message Y, and Node transmits Message XY to Nodes and .

In FIG. 5E, Nodes and transmit Message XY to Nodes and and to Nodes and , respectively. Node applies Rule 4. In FIG. 5F, Nodes and transmit Message XY to Nodes and and to Node , respectively. Nodes and apply Rule 4. In FIG. 5G, Node (the root node) transmits Message Y to another destination.

In FIGS. 5A-5G, the routing units operate so as to create a tree-like topology that is a straight line. In other words, messages propagate unidirectionally because of Rule 3 (if nothing to add, repeat what you heard) and Rule 4 (don't repeat yourself).

FIGS. 6A-6G illustrate another network having six nodes (devices ). As in the case of FIGS. 5A-5G, only the compare process is explicitly illustrated. The computation resources of Node are assumed to be configured to respond to Message X.

In FIG. 6A, Node (the root node or a node connected to the root node) has transmitted Message X to Nodes and . In FIG. 6B, in accordance with Rule 3, Nodes and have retransmitted to Nodes and and Nodes and , respectively.

In FIG. 6C, Node has applied Rule 4 and has not re-transmitted. Nodes and have retransmitted. The transmissions from Node reach Nodes , , and . The transmissions from Node reach Nodes and .

In FIG. 6D, all Nodes except Node have applied Rule 4 and do not retransmit. The computation resources of Node are configured to respond to Message X with by adding. Submessage Y, and it transmits Message XY in accordance with Rule 3. Its transmission reaches Node .

In FIG. 6E, Node transmits Message XY, which reaches Nodes , , and . In FIG. 6F, Nodes and apply Rule 3 and transmit Message XY to Nodes and and Nodes and , respectively. In FIG. 6G, Node has applied Rule 4 and not retransmitted. Node applies Rule 3 and transmits Message XY to Nodes and .

In FIGS. 6A-6G, the link-determined topology is a tree like structure in which potential loops are avoided. As a result of the routing units of each device in network , messages and responses pass through loops; the loops do not cause messages to cycle endlessly. Multiple paths do not disrupt operation even if there are differing numbers of hops.

The method described above operates on the entire packet, at the message level. However, the method could be adapted to operate at the submessage level, in which case this description would be in terms of “submessages” rather than “messages”. If any submessage in an incoming message did not pass the “integrity” test performed by check process , only that part of the submessage would be treated as silence. In other words:

Submessage A+Submessage B=>Silence

Submessages of the same message that were the same would continue through routing unit . In other words,

Submessage A+Submessage A=>Submessage A

Other Embodiments

Although the present invention has been described in detail it should be understood that various changes, substitutions, and alterations can be made hereto without departing from the spirit and scope of the invention as defined by the appended claims.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 illustrates a wireless network comprised of a number of wireless communications devices.

FIG. 2 illustrates a link-determined topology of the network of FIG. .

FIG. 3 illustrates the structure and timing of packets transmitted within the network of FIG. .

FIG. 4 illustrates the routing unit of each of the communications devices.

FIGS. 5A-5G illustrate the operation of the invention in a wireless network, such that the link-determined topology is a straight line.

FIGS. 6A-6G illustrate the operation of the invention in a wireless network, such that the link-determined topology is a tree-like structure.

CLAIMS

1. A method of routing messages in a wireless communications network having a number of wireless communications devices, comprising: synchronizing transmissions from each device, such that all transmissions occur simultaneously; and at each receiving device performing 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; comparing each non-corrupt incoming message with the last transmitted message; using a rules engine to determine whether the incoming message should be transmitted as an outgoing message using the following rules: Rule 1: Unless you are the root device, speak only when spoken to; Rule 2: If you have just spoken, be quiet and listen; Rule 3: If you have nothing to add, repeat exactly what you heard; and Rule 4: If you are about to repeat yourself, be quiet.

2. The method of claim 1, wherein at least some of the devices have computational resources, and further comprising the steps of delivering the non-corrupt incoming message to the computational resources and receiving a potential outgoing message from the computational resources, wherein the comparing step further compares the potential outgoing message with the last transmitted message, and wherein the rules engine determines whether the potential outgoing message is to be transmitted.

3. The method of claim 1, wherein the rules engine applies a rule such that an outgoing message is transmitted only if the comparing step does not determine a match.

4. The method of claim 1, wherein the rules engine is implemented as a state machine.

5. A routing unit for a wireless communications device having at least a receiver, a transmitter, and computation resources, comprising: a timer for providing transmissions synchronized with transmissions of other devices; a check process programmed to determine the integrity of each incoming message and to deliver non-corrupt messages to the computation resources; a compare process programmed to receive potential outgoing messages from the computation resources and to compare each potential outgoing message with the last transmitted message; and a rules engine programmed to apply a set of rules that determine whether the potential outgoing message is to be transmitted from the device; wherein the rules engine is programmed such that it permits the device to transmit the potential outgoing message only in response to receiving a transmission of the last transmitted message.

6. The routing unit of claim 5, wherein the rules engine is programmed such that it requires the device to only receive after transmitting.

7. The routing unit of claim 5, wherein the rules engine is programmed such that it requires the device to repeat a received transmission unless the devices are computation resources configured to respond to the transmission.

8. The routing unit of claim 5, wherein the rules engine is programmed such that it prevents the device from repeating a transmission.

9. 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, comprising: synchronizing transmissions from each device, such that all transmissions occur simultaneously; and at each receiving device performing 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; wherein the rules engine is programmed such that it requires the device to only receive incoming messages after transmitting the potential outgoing message.

10. The method of claim 9, wherein the potential outgoing message is the same as the incoming message.

11. The method of claim 9, wherein the rules engine is programmed such that it permits the device to transmit only in response to receiving a transmission.

12. The method of claim 1 wherein the rules engine is programmed such that it requires the device to repeat a received transmission unless the device is configured to respond to the transmission.

13. The method of claim 9, wherein the rules engine is programmed such that it uses the results of the comparing step to prevent the device from repeating a transmission.

14. A routing unit for a wireless communications device having at least a receiver, a transmitter, and computation resources, comprising: a timer for providing transmissions synchronized with transmissions of other devices; a check process programmed to determine the integrity of each incoming message and to deliver non-corrupt messages to the computation resources; a compare process programmed to receive potential outgoing messages from the computational resources and to compare each potential outgoing message with the last transmitted message; and a rules engine programmed to apply a set of rules that determine whether potential outgoing message is to be transmitted from the device; wherein the rules engine is programmed to implement the following rules: Rule 1: Unless you are the root device, speak only when spoken to; Rule 2: If you have just spoken, be quiet and listen; Rule 3: If you have nothing to add, repeat exactly what you heard; and Rule 4: If you are about to repeat yourself, be quiet.

COPYRIGHT

User acknowledges that Fairview Research and its third party providers retain all right, title and interest in and to this xml under applicable copyright laws. User acquires no ownership rights to this xml including but not limited to its format. User hereby accepts the terms and conditions of the License Agreement.