Method and apparatus for routing messages in a wireless network

• US 6,822,951 B1
• Filed: 11/01/2000
• Issued: 11/23/2004
• Est. Priority Date: 11/05/1999
• Status: Active Grant

• Current Assignee: Texas Instruments, Inc.
• Original Assignee: Texas Instruments, Inc.
• Inventors: Patton, Charles M.
• Primary Examiner(s): Ho, Duc
• Application Number:
  US09/704,089
• Time in Patent Office: 1,483 Days
• Field of Search: 370/229, 370/310, 370/351, 370/350, 370/328, 370/338, 370/428, 370/401, 370/254, 370/400, 455/445, 455/412.1, 455/466, 375/222, 375/356
• US Class Current: 370/338
• CPC Class Codes: H04W 88/04 adapted for relaying to or from another terminal or user

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.

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.

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.

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.

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.