Home
Patent Search
IMT Blog
REGISTER
|
SIGN IN
United States Patent Application
20020116460
Kind Code
A1
Treister, Bijan ; et al.
August 22, 2002
Approach for managing communications channels based on performance and transferring functions between participants in a communications arrangement
Abstract
A novel approach for selecting communications channels and participants with which to communicate based on channel performance and transferring management functions between participants in a communications arrangement is disclosed. According to one aspect of the invention, a particular channel is selected based on channel performance and channel identification data is provided to a participant that sends a response on a channel selected based on the channel identification data. According to another aspect of the invention, a particular participant is selected from a group of participants based on the performance of a particular channel. According to yet another aspect, an associate master participant is selected to assume responsibilities for functions assigned to the master participant if any of a set of handoff criteria are satisfied. For example, the associate master participant may assume the role of the master participant if the master participant can no longer perform the functions.
Inventors:
Treister; Bijan
(Kew, AU)
, Gan; Hongbing
(Carlton North, AU
)
, Skafidas; Efstratios
(Coburg, AU
)
Correspondence Name and Address:
1600 WILLOW STREET
HICKMAN PALERMO TRUONG & BECKER, LLP
SAN JOSE
CA
95125
US
Series Code:
052019
Filed:
January 16, 2002
U.S. Current Class:
709/204;
709/208
U.S. Class at Publication:
709/204;
709/208
Intern'l Class:
G06F 015/16
Claims
What is claimed is:
1. A method for managing a communications arrangement comprising a plurality of participants, the method comprising the computer-implemented steps of: assigning, to a first participant from the plurality of participants, one or more functions to be performed by the first participant; designating a second participant from the plurality of participants to perform the one or more functions if any of one or more handoff criteria are satisfied; in response to any of the one or more handoff criteria being satisfied, assigning the one or more functions to the second participant; and selecting, based upon performance of a plurality of communications channels and at least one performance criterion, a first communications channel from the plurality of communications channels.
2. The method of claim 1, further comprising the computer-implemented steps of: generating channel identification data that identifies the first communications channel; and providing the channel identification data to one or more participants from the plurality of participants.
3. The method of claim 2, further comprising the computer-implemented steps of: receiving at least a first communication from the one or more participants over a second communications channel from the plurality of communications channels, wherein the second communications channel is determined based on the channel identification data.
4. A method for managing, based on performance, a communications arrangement comprising a plurality of participants, the method comprising the computer-implemented steps of: selecting, based upon performance of a plurality of communications channels, a first communications channel from the plurality of communications channels; generating channel identification data that identifies the first communications channel; providing the channel identification data to one or more participants from the plurality of participants; receiving at least a first communication from the one or more participants over a second communications channel from the plurality of communications channels, wherein the second communications channel is determined based on the channel identification data; assigning, to a first participant from the plurality of participants, one or more functions to be performed by the first participant; prior to a failure of the first participant, designating a second participant from the plurality of participants to perform the one or more functions if any of one or more handoff criteria are satisfied.
5. A method for assigning functions between participants and selecting communications channels in a communications arrangement comprising a plurality of participants, the method comprising the computer-implemented steps of: assigning, to a first participant from the plurality of participants, one or more functions to be performed by the first participant; prior to a failure of the first participant, designating a second participant from the plurality of participants to perform the one or more functions if any of one or more criteria are satisfied; in response to any of the one or more criteria being satisfied, assigning the one or more functions to the second participant; selecting, based upon performance of a plurality of communications channels and at least one specified criterion, a first communications channel from the plurality of communications channels; generating channel identification data that identifies the first communications channel; providing the channel identification data to one or more participants from the plurality of participants; and receiving at least a first communication from the one or more participants over a second communications channel from the plurality of communications channels, wherein the second communications channel is determined based on the channel identification data.
6. The method as recited in claim 5, wherein communications between the plurality of participants are made on different frequencies over time.
7. The method as recited in claim 5, wherein the communications arrangement includes a wireless communications arrangement and the plurality of participants includes a plurality of wireless devices.
8. The method of claim 5, wherein the channel identification data is first channel identification data, and wherein the method further comprises the computer-implemented steps of: selecting, based upon the performance of the plurality of communications channels and the at least one specified criterion, a third communications channel from the plurality of communications channels; generating second channel identification data that identifies the third communications channel; providing the second channel identification data to one or more additional participants from the plurality of participants; and receiving at least a second communication from the one or more additional participants over a fourth communications channel from the plurality of communications channels, wherein the fourth communications channel is determined based on the second channel identification data that identifies the third communications channel.
9. The method of claim 5, wherein the step of providing the channel identification data to the one or more participants comprises the computer-implemented step of: providing the channel identification data to the one or more participants over a third communications channel of the plurality of communications channels, wherein the third communications channel is not the first communications channel.
10. The method of claim 9, wherein at least the first communication from the one or more participants includes data that indicates the performance of the third communications channel.
11. The method of claim 5, wherein the step of selecting the first communications channel from the plurality of communications channels comprises the computer-implemented steps of: classifying one or more communications channels of the plurality of communications channels based upon whether the performance of the one or more communications channels satisfies at least one performance criterion; and selecting the first communications channel from the one or more communications channels that are classified as satisfying the at least one performance criterion.
12. The method of claim 11, further comprising the computer-implemented steps of: determining a number of communications channels of the plurality of communications channels that satisfy the at least one performance criterion; and if the number of communications channels that satisfy the at least one performance criterion is less than a specified number, reclassifying one or more communications channels of the plurality of communications channels.
13. The method of claim 5, further comprising the computer-implemented step of: determining the performance of the plurality of communications channels.
14. The method of claim 13, wherein the step of determining the performance of the plurality of communications channels comprises the computer-implemented steps of: sending a request for performance data to at least one participant from the plurality of participants; and in response to the request, receiving performance data from the at least one participant.
15. The method of claim 13, wherein the step of determining the performance of the plurality of communications channels comprises the computer-implemented step of: creating and maintaining performance data that indicates the performance of one or more communications channels of the plurality of communications channels for communications with one or more participants from the plurality of participants.
16. The method as recited in claim 5, wherein the one or more criteria include the failure of the first participant.
17. The method as recited in claim 5, wherein: the first participant is a master participant, the second participant is a slave participant prior to being assigned to perform the one or more functions, the second participant is an associate master participant after being designated to perform the one or more functions if any of the one or more criteria are satisfied, and the one or more participants include one or more slave participants.
18. The method of claim 17, wherein the master participant performs the steps of selecting, generating, providing, and receiving.
19. The method of claim 5, wherein the one or more participants includes the second participant.
20. The method as recited in claim 5, wherein the second participant is designated by the first participant.
21. The method as recited in claim 5, wherein the second participant is designated by one or more participants from the plurality of participants.
22. A method for managing a communications system comprising a plurality of participants, comprising the computer-implemented steps of: determining the performance of a first communications channel between a first participant from the plurality of participants and one or more other participants from the plurality of participants; and selecting, based upon the performance of the first communications channel between the first participant and the one or more other participants, a second participant from the one or more other participants; assigning, to a third participant from the plurality of participants, one or more functions to be performed by the third participant; and designating a fourth participant from the plurality of participants to perform the one or more functions if any of one or more handoff criteria are satisfied.
23. The method of claim 22, further comprising the computer-implemented step of: in response to any of the one or more handoff criteria being satisfied, assigning the one or more functions to the fourth participant.
24. The method of claim 22, wherein the step of designating the fourth participant is performed prior to a condition of the third participant that prevents the third participant from performing the one or more functions.
25. The method of claim 22, wherein the step of designating the fourth participant is performed prior to a failure of the third participant.
26. The method of claim 22, wherein the first participant is the third participant.
27. The method of claim 22, wherein the one or more participants includes the fourth participant.
28. A first communications device comprising: an interface that is configured to receive data from a plurality of communications devices and to transmit data to the plurality of communications devices; and a mechanism that is communicatively coupled to the interface and configured to: perform one or more functions; prior to a failure of the communications device, designate a second communications device from the plurality of communications devices to perform the one or more functions if any of a set of criteria are satisfied; select, based upon performance of a plurality of communications channels, a first communications channel from the plurality of communications channels; generate first channel identification data that identifies the first communications channel; provide the first channel identification data to one or more communications devices from the plurality of communications devices; and receive at least a first communication from the one or more communications devices over a second communications channel from the plurality of communications channels, wherein the second communications channel is determined based on the first channel identification data that identifies the first communications channel.
29. The first communications device as recited in claim 28, wherein the first communications device, the second communications device, and the one or more communications devices are wireless communications devices and the plurality of communications device includes a plurality of wireless communications devices.
30. The first communications device as recited in claim 28, wherein: the first communications device is a master participant; and the second communications device is an associate master participant; and the one or more communications devices are slave participants.
31. The first communications device of claim 28, wherein the one or more communications devices include the second communications device.
32. The first communications device of claim 28, wherein the mechanism is further configured to: select, based upon the performance of the plurality of communications channels and at least one performance criterion, a third communications channel from the plurality of communications channels; generate second channel identification data that identifies the third communications channel; provide the second channel identification data to one or more additional communications devices from the plurality of communications devices; and receive at least a second communication from the one or more additional communications devices over a fourth communications channel from the plurality of communications channels, wherein the fourth communications channel is determined based on the second channel identification data that identifies the third communications channel.
33. The first communications device of claim 28, wherein the mechanism is further configured to: provide the channel identification data to the one or more communications devices over a specified communications channel of the plurality of communications channels, wherein the specified communications channel is not the first communications channel.
34. The first communications device of claim 33, wherein at least the first communication from the one or more communications devices includes performance data that indicates the performance of the specified communications channel.
35. The first communications device of claim 28, wherein the mechanism is further configured to: determine the performance of a plurality of communications channels used by the plurality of communications devices.
36. The first communications device of claim 35, wherein the performance of the plurality of communications channels is determined based on a channel performance testing technique selected from the group consisting of a received signal strength indicator, a header error check, a cyclic redundancy check, and forward error correction.
37. The first communications device of claim 28, wherein the mechanism is further configured to: classify one or more communications channels of the plurality of communications channels based upon whether the performance of the one or more communications channels satisfies at least one performance criterion; and select the first communications channel from the one or more communications channels that are classified as satisfying the at least one performance criterion.
38. A computer-readable medium carrying one or more sequences of instructions for managing a communications arrangement comprising a plurality of participants, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of: assigning, to a first participant from the plurality of participants, one or more functions to be performed by the first participant; designating a second participant from the plurality of participants to perform the one or more functions if any of one or more handoff criteria are satisfied; in response to any of the one or more handoff criteria being satisfied, assigning the one or more functions to the second participant; and selecting, based upon performance of a plurality of communications channels and at least one performance criterion, a first communications channel from the plurality of communications channels.
39. The computer-readable medium of claim 38, further comprising instructions which, when executed by the one or more processors, cause the one or more processors to carry out the steps of: generating channel identification data that identifies the first communications channel; and providing the channel identification data to one or more participants from the plurality of participants.
40. The computer-readable medium of claim 39, further comprising instructions which, when executed by the one or more processors, cause the one or more processors to carry out the steps of: receiving at least a first communication from the one or more participants over a second communications channel from the plurality of communications channels, wherein the second communications channel is determined based on the channel identification data.
41. A computer-readable medium carrying one or more sequences of instructions for managing, based on performance, a communications arrangement comprising a plurality of participants, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of: selecting, based upon performance of a plurality of communications channels, a first communications channel from the plurality of communications channels; generating channel identification data that identifies the first communications channel; providing the channel identification data to a one or more participants from the plurality of participants; receiving at least a first communication from the one or more participant over a second communications channel from the plurality of communications channels, wherein the second communications channel is determined based on the channel identification data; assigning, to a first participant from the plurality of participants, one or more functions to be performed by the first participant; prior to a failure of the first participant, designating a second participant from the plurality of participants to perform the one or more functions if any of one or more handoff criteria are satisfied.
42. A computer-readable medium carrying one or more sequences of instructions for assigning functions between participants and selecting communications channels in a communications arrangement comprising a plurality of participants, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of: assigning, to a first participant from the plurality of participants, one or more functions to be performed by the first participant; prior to a failure of the first participant, designating a second participant from the plurality of participants to perform the one or more functions if any of one or more criteria are satisfied; in response to any of the one or more criteria being satisfied, assigning the one or more functions to the second participant; selecting, based upon performance of a plurality of communications channels and at least one specified criterion, a first communications channel from the plurality of communications channels; generating channel identification data that identifies the first communications channel; providing the channel identification data to a third participant from the plurality of participants; and receiving a first communication from the third participant over a second communications channel from the plurality of communications channels, wherein the second communications channel is determined based on the channel identification data.
43. A computer-readable medium carrying one or more sequences of instructions for managing a communications system comprising a plurality of participants, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of: determining the performance of a first communications channel between a first participant from the plurality of participants and one or more other participants from the plurality of participants; and selecting, based upon the performance of the first communications channel between the first participant and the one or more other participants, a second participant from the one or more other participants; assigning, to a third participant from the plurality of participants, one or more functions to be performed by the third participant; and designating a fourth participant from the plurality of participants to perform the one or more functions if any of one or more handoff criteria are satisfied.
Description
RELATED APPLICATIONS
[0001] This application claims domestic priority from (1) prior U.S. Provisional Patent Application Serial No. 60/264,593, filed on Jan. 25, 2001, titled "A METHOD FOR NETWORK QUASI-ADAPTIVE FREQUENCY HOPPING MULTICHANNEL UTILISATION AND ADAPTIVE NETWORK CONTROL," naming as inventors Bijan Treister, Hongbing Gan, and Efstratios Skafidas, (2) prior U.S. Provisional Patent Application Serial No. 60/264,345, filed on Jan. 25, 2001, titled "A METHOD FOR NETWORK QUASI-ADAPTIVE FREQUENCY HOPPING MULTICHANNEL UTILISATION," naming as inventors Bijan Treister, Hongbing Gan, and Efstratios Skafidas, and (3) prior U.S. Provisional Patent Application Serial No. 60/264,348, filed on Jan. 25, 2001, titled "A METHOD FOR ADAPTIVE NETWORK CONTROL," naming as inventors Bijan Treister, Hongbing Gan, and Efstratios Skafidas, the entire disclosures of which are hereby incorporated by reference for all purposes as if fully set forth herein.
[0002] This application is related to (1) co-pending U.S. patent application Ser. No. 09/948,499 (Attorney Docket No. 52637-0025) entitled "APPROACH FOR MANAGING COMMUNICATIONS CHANNELS BASED ON PERFORMANCE," filed on Sep. 6, 2001, naming as inventors Bijan Treister, Hongbing Gan, and Efstratios Skafidas, and (2) co-pending U.S. patent application Ser. No. 09/939,105 (Attorney Docket No. 52637-0029) entitled "APPROACH FOR TRANSFERRING FUNCTIONS BETWEEN PARTICIPANTS IN A COMMUNICATIONS ARRANGEMENT," filed on Aug. 24, 2001, naming as inventors Bijan Treister, Hongbing Gan, and Efstratios Skafidas.
FIELD OF THE INVENTION
[0003] The present invention relates to communications systems, and more particularly, to selecting communications channels and participants with which to communicate based on channel performance and transferring management functions between participants in a communications arrangement.
BACKGROUND OF THE INVENTION
[0004] A communications network is any system or mechanism that provides for the exchange of information or data between participants. As used herein, the term "participant" refers to any device or mechanism that exchanges data with other devices or mechanisms over a communications medium. In some communications network arrangements, one of the participants is designated as a "master participant." As used herein, the terms "master participant" and "master" are synonymous. The master participant performs one or more functions that are assigned to only the master participant and not to other participants. For example, a master participant may initiate and manage communications with other participants. As another example, the master participant may select a particular frequency hopping scheme to be used in the communications network.
[0005] In communications networks with a master participant, the other participants are conventionally referred to as "slave participants." As used herein, the terms "slave participant" and "slave" are synonymous. Communications networks that use a master participant conventionally use only a single master participant, with any number of slave participants. Master participants are typically elected from available slave participants according to a selection or voting algorithm.
[0006] A frequency hopping (FH) protocol is an approach for wireless communications in a communications network that uses a frequency hopping signal transmission technique in which information or data is transmitted over a set of frequencies in a communications frequency band. A frequency hopping communications system is a system that uses a FH protocol. The order in which the communications network hops among the set of frequencies is known as the hopping sequence.
[0007] In contrast to FH systems, a non-frequency hopping (NFH) system is simply a communications system whose carrier does not hop over a set of frequencies. A typical NFH system may occupy a portion of the communications frequency band corresponding to several frequencies used by an FH system.
[0008] With some communications system approaches, such as the FH approach, the frequency band is broken up into separate frequencies, often referred to as "communications channels." As used herein, the terms "communication channel" and "channel" are synonymous. For example, an FH system transmits data on one channel, hops to another channel in the hopping sequence to transmit more data, and continues by transmitting data on subsequent channels in the hopping sequence. The switching of frequencies may occur many times each second. The use of an FH protocol helps to reduce problems with interference from other communications systems and other interference sources. Frequency hopping also helps with fading of transmissions and power consumption and provides security for the transmission so that others may not intercept the data being transmitted because others do not know the hopping sequence.
[0009] An example of a frequency hopping protocol is the Institute of Electrical and Electronics Engineers (IEEE) 802.15.1 Wireless Personal Area Network Standard, which is based on the Bluetooth.TM. wireless personal area network (WPAN) technology from the Bluetooth Special Interest Group (SIG). The BLUETOOTH trademarks are owned by Bluetooth SIG, Inc., U.S.A. The Bluetooth protocol uses 79 individual randomly chosen frequency channels numbered from 0 to 78 and changes the frequencies 1600 times per second. Examples of NFH systems include the IEEE 802.11b Wireless Local Area Network (WLAN) and the IEEE 802.15.3
next-generation WPAN, both of which operate in the 2.4 GHz Industrial, Scientific, Medical (ISM) band, which is an unlicensed portion of the radio spectrum that may be used in most countries by anyone without a license.
[0010] Typically, the master of an FH communications system transmits at even-numbered timeslots on the hopping sequence and the slaves listen at those regular intervals. The master will address one slave (or all slaves in a "broadcast" mode), and the addressed slave responds back to the master at the next odd-numbered timeslot. A preamble, which is known to all the participants of the FH network, is used to identify the network and for the slaves to synchronize with the master. For example, in Bluetooth and IEEE 802.15.1, the known preamble is called the "channel access code."
[0011] A common problem for communications systems is poor transmission quality of communications channels, also referred to as poor channel performance, which results in data transmission errors. For example, poor channel performance may increase the bit error rate (BER) or result in the loss of packets, leading to reduced transmission quality. As used herein, a "data packet" is a block of data used for transmissions in a packet-switched system, and the terms "data packet" and "packet" are synonymous.
[0012] A common source of poor channel performance is interference from other communications systems or other interference sources. Interference has a dynamic nature due to the use of devices at different times and locations, and as a result, eventually all channels of a communication system that uses multiple channels will experience some degree of interference at some time. Interference may change depending on when the communications systems use the band and the relative locations of the participants of each system to participants of other systems. Because the participants may be mobile, interference may vary depending on the movements of the participants of one system relative to the locations of participants of other systems. In addition, interference may arise from other sources resulting in a degradation of performance.
[0013] Another common source of poor channel performance is the coexistence problem that may arise between the communications systems that operate in the same frequency band. For example, while an FH communications system hops over the entire frequency band, an NFH communications system occupies separate parts of the frequency band. When the FH communications system hops over part of the frequency band occupied by an NFH communications system, there may be interference between the systems. Although the use of a FH protocol helps to lessen the interference problem because not all of the FH channels will interfere with other communications systems, there nevertheless remains interference on those channels that coincide with the NFH communications systems. An example of the interference situation is the coexistence problem between the frequency hopping IEEE 802.15.1 WPAN and the non-frequency hopping IEEE 802.11b Wireless Local Area Network (WLAN) because both share the 2.4 GHz ISM band.
[0014] One approach for managing poor channel performance is to increase the power used in the transmissions such that interference has less of an impact on the system transmitting at the increased power. However, in mobile applications, this increased power approach drains batteries used by the participants, and thus the required power increase may be impractical. Also, the increased power approach only benefits the system using the increased power and results in a bigger interference impact on other systems.
[0015] Other approaches for managing interference include retransmitting data that had errors in an original transmission and incorporating a form of redundancy into the transmission (e.g., by including multiple copies of some or all of the data) so that the participant receiving the data can identify and correct transmission errors. However, such approaches require additional resources to both identify the errors and then to correct the errors, such as by using additional transmissions or by using redundant data transmission approaches that decrease the amount of information that can be transmitted, which reduces the performance of the communications system.
[0016] Furthermore, using only a single master participant can have numerous drawbacks. In particular, if for any reason the master participant cannot perform its assigned functions, then the communications network will not function and the participants will not be able to communicate with each other. The master participant may not be able to perform their assigned functions for a variety of reasons. For example, in a wireless communications network with mobile participants, the master participant may move out of range of one or more slave participants, or vice versa. As another example, the master participant's power supply may drop below a minimum threshold or the master participant may otherwise fail. In any of these situations, the slave participants must first recognize that the master participant can no longer perform its assigned functions. Once the slave participants have made this determination, a new master participant must be selected from the available slave participants. Once the new master participant is selected, the functions assigned to the prior master participant must be assigned to the new master participant. Given that a master participant may fail at any time for a variety of reasons, either or both of these tasks may require a significant amount of time and computational resources and cause a significant disruption to the communications network.
[0017] Based on the need for wireless communications and the limitations in the conventional approaches, an approach for managing poor performance of communications channels and transferring management functions between participants that does not suffer from the limitations of the prior approaches is highly desirable.
SUMMARY OF THE INVENTION
[0018] According to one aspect of the invention, a method is provided for assigning functions between participants and selecting communications channels in a communications arrangement. The method includes assigning, to a first participant from the plurality of participants, one or more functions to be performed by the first participant. The method also includes, prior to a failure of the first participant, designating a second participant from the plurality of participants to perform the one or more functions if any of one or more handoff criteria are satisfied. The method further includes, in response to any of the one or more handoff criteria being satisfied, assigning the one or more functions to the second participant. The method further includes selecting, based upon the performance of a set of communications channels and at least one performance criterion, a communication channel from a plurality of communications channels. The method also includes generating channel identification data that identifies the selected communications channel and providing the channel identification data to a third participant of the plurality of participants. The method further includes receiving a communication from the third participant over another communications channel from the plurality of communications channel, where the other communications channel is selected based on the channel identification data.
[0019] According to another aspect of the invention, a method is provided for selecting participants with which to communicate and assigning functions between participants in a communications system. The method includes determining the performance of a communications channel between a first participant and a one or more other participants. The method also includes selecting, based upon the performance of the communications channel, a second participant from the one or more other participants. The method further includes assigning, to a third participant, one or more functions to be performed by the third participant. The method also includes designating a fourth participant to perform the one or more functions if any of one or more handoff criteria are satisfied.
[0020] According to another aspect of the invention, a communications device is provided that comprises an interface and a mechanism. The interface is configured to receive data from a plurality of communications devices and to transmit data to other communications devices. The mechanism is configured to perform one or more functions, and prior to a failure of the communications device, designate a particular communications device from the plurality of communications devices to perform the one or more functions if any of a set of handover criteria are satisfied. The mechanism is further configured to select, based upon the performance of a plurality of communications channels, a first communications channel, generate channel identification data that identifies the first communications channel, and provide the channel identification data to another communications device. The mechanism is also configured to receive a communication from the other communications device over another communications channel that is determined based on the channel identification data.
[0021] According to other aspects, the invention encompasses a computer-readable medium and a carrier wave configured to carry out the foregoing functions.
BRIEF DESCRIPTION OF THE DRAWINGS
[0022] Embodiments are illustrated by way of example, and not by way of limitation, in the figures of the accompanying drawings and in which like reference numerals refer to similar elements and in which:
[0023] FIG. 1A is a block diagram that depicts a communications arrangement that includes several participants, according to an embodiment of the invention;
[0024] FIG. 1B is a block diagram that depicts a communications arrangement in which an associate master participant assumes the role of master participant, according to an embodiment of the invention;
[0025] FIG. 1C is a block diagram that depicts a communications arrangement in which a slave participant is designated as the new associate master participant, according to an embodiment of the invention;
[0026] FIG. 1D is a flow diagram that depicts an approach for selecting communications channels based on channel performance and transferring management functions between participants, according to an embodiment of the invention;
[0027] FIG. 1E is a flow diagram that depicts an approach for selecting participants based on channel performance, according to an embodiment of the invention;
[0028] FIG. 1F is a flow diagram that depicts an approach for managing performance data for communications channels between participants of a communications system, according to an embodiment of the invention;
[0029] FIG. 2A is a block diagram that depicts a performance lookup table that includes performance data, according to one embodiment of the invention;
[0030] FIG. 2B is a block diagram that depicts a classification lookup table that includes channel classification data, according to one embodiment of the invention;
[0031] FIG. 3A is a block diagram that depicts a master to slave packet that identifies the selected communications channel, according to one embodiment of the invention;
[0032] FIG. 3B is a block diagram that depicts a slave to master packet that includes a performance measurement for a previous communications channel, according to one embodiment of the invention;
[0033] FIG. 4 is a flow diagram that depicts an approach for initializing a communications arrangement having a master participant, according to an embodiment of the invention;
[0034] FIG. 5A is a flow diagram that depicts an approach for a master to send a normal packet to a recipient, according to an embodiment of the invention;
[0035] FIG. 5B is a flow diagram that depicts an approach for a master to send a packet to an associate master requesting the associate master to assume the role of master, according to an embodiment of the invention;
[0036] FIG. 5C is a flow diagram that depicts an approach for a master to send a request table data packet to a recipient, according to an embodiment of the invention;
[0037] FIG. 5D is a flow diagram that depicts an approach for a master to send a packet to a slave requesting the slave to assume the role of associate master, according to an embodiment of the invention;
[0038] FIG. 6A is a flow diagram that depicts how a recipient initially handles packets that the recipient receives from other participants, according to an embodiment of the invention;
[0039] FIG. 6B is a flow diagram that depicts how a recipient handles a packet that is not intended for the recipient, according to an embodiment of the invention;
[0040] FIG. 6C is a flow diagram that depicts how a recipient handles a normal packet from a master, according to an embodiment of the invention;
[0041] FIG. 6D is a flow diagram that depicts how a recipient sends an update table packet to a master in response to a request table packet, according to an embodiment of the invention;
[0042] FIG. 6E is a flow diagram that depicts how an associate master handles a handover request packet from a master, according to an embodiment of the invention;
[0043] FIG. 6F is a flow diagram that depicts how a slave handles a promotion request packet from a master, according to an embodiment of the invention;
[0044] FIG. 7A is a flow diagram that depicts steps performed by an associate master participant using a timer to determine that the master participant has failed according to an embodiment of the invention;
[0045] FIG. 7B is a flow diagram that depicts an approach for using a master to check whether communications channels should be redeemed, according to one embodiment of the invention; and
[0046] FIG. 8 is a block diagram of a computer system on which embodiments of the invention may be implemented.
DETAILED DESCRIPTION OF THE INVENTION
[0047] In the following description, for the purposes of explanation, specific details are set forth in order to provide a thorough understanding of the invention. However, it will be apparent that the invention may be practiced without these specific details. In other instances, well-known structures and devices are depicted in block diagram form in order to avoid unnecessarily obscuring the invention.
[0048] In the following description, various embodiments of the invention are described in the following sections:
[0049] I. OVERVIEW
[0050] A. Example Communications Arrangement
[0051] B. Selecting Channels Based on Performance
[0052] C. Transferring Functions Between Participants
[0053] D. Additional Examples for Selecting Channels
[0054] E. Selecting Participants Based on Performance
[0055] F. Managing Channel Performance Data
[0056] II. MEASURING CHANNEL PERFORMANCE, CLASSIFYING CHANNELS, AND STORING RELATED INFORMATION
[0057] A. Approaches for Channel Performance Measurement
[0058] B. Approaches for Channel Classification
[0059] C. Maintaining Channel Performance and Channel Classification Information
[0060] III. SELECTING CHANNELS AND INFORMING PARTICIPANTS
[0061] IV. NETWORK AND PARTICIPANT INITIALIZATION
[0062] V. MASTER CONNECTION SEQUENCE
[0063] A. Normal Packet
[0064] B. Request Handover Packet
[0065] C. Request Table Data Packet
[0066] D. Request Associate Master Packet
[0067] VI. ASSOCIATE MASTER ASSUMING ROLE AS MASTER
[0068] VII. SLAVE AND ASSOCIATE MASTER CONNECTION SEQUENCE
[0069] A. Initial Handling of Packets
[0070] B. Packet Not Intended for Slave
[0071] C. Normal Packet
[0072] D. Update Table Packet
[0073] E. Handover Request Packet
[0074] F. Promotion Request Packet
[0075] VIII. REDEMPTION OF CHANNELS
[0076] IX. APPROACH FOR MASTER ADAPTIVE SELECTION OF PARTICIPANTS
[0077] X. IMPLEMENTATION MECHANISMS
[0078] I. Overview
[0079] A novel approach for managing communications channels generally involves transferring management functions between participants and measuring, maintaining, and using channel performance data to manage a communications system. The transferring of management functions between participants generally involves the use of an associate master participant that assumes responsibilities for functions assigned to the master participant if the master participant can no longer perform the functions. The approach may be used with any type of functions and the invention is not limited to any particular type of functions. Channel performance data may be used to select one communications channel from a group of communications channels for use in communicating with a participant of the communications system. Also, the channel performance data may be used to select one participant from a group of participants to communicate with over a specified communications channel. The participants of the communications system maintain and share performance data about the communications channels between the participants. The approach allows the communications system to adaptively avoid channels with poor performance and reduces the amount of time required both to determine that the master participant can no longer perform the functions and to assign responsibility for performing the functions to another participant once that determination is made.
[0080] A. Example Communications Arrangement
[0081] FIG. 1A is a block diagram that depicts a communications arrangement 100 that includes participants P1 through P5, according to an embodiment of the invention. In the example depicted in FIG. 1A, participant P4 is designated as the master participant and is responsible for performing one or more functions. An example function is initiating and managing communications with participants P2, P3, P3, and P5. Master participant P4 may be elected from participants P1-P5 by participants P1-P5 or another entity and the invention is not limited to any particular approach for designating one of the participants as the master participant.
[0082] Participants P1 through P5 may be any of a variety of communications devices. Examples of communications devices that may be used in a communications arrangement that uses the channel selection approach described herein include, but are not limited to, wireless devices that are used in wireless local area networks (WLANs) and in wireless personal area networks (WPANs), such as cordless phones, laptop computers, desktop computers, printers, and personal digital assistants (PDAs). Wireless devices may communicate in a variety of ways, including but not limited to, infrared, line of sight, cellular, microwave, satellite, packet radio and spread spectrum technologies. Some communications devices may be characterized as mobile devices based on the relative ease of moving such devices between locations or because the mobile devices may be conveniently carried by a person, such as cordless phones, laptop computers, and PDAs.
[0083] The solid lines connecting master P4 to slaves P1, P2, and P3 and associate master P5 depict the logical connections between the respective participants over which data is communicated between master P4 and a particular participant from slaves P1, P2, and P3 and associate master P5. In addition, when master P4 communicates with a particular participant, the other participants may listen to the communication from master P4 to the particular participant over the logical connections depicted by the solid lines. The dotted lines connecting slaves P1, P2, and P3 and associate master P5 to each other depict the logical connections between the respective participants over which the participants may listen to replies from the other participants to master P4. In some communications system, the slaves and associate master do not communicate with each other but may listen to communications from other participants. In other communications systems, slave and the associate master may communicate directly with each other. The invention is not limited to a particular configuration of which participants may communicate together or which participants may listen to communications from one another.
[0084] B. Selecting Channels Based on Performance
[0085] FIG. 1D is a flow diagram 110 that depicts an approach for selecting communications channels based on channel performance and transferring management functions between participants, according to an embodiment of the invention. Although the flow diagrams described herein provide a particular set of steps in a particular order, other implementations may use more or fewer steps and a different order than those shown in the figures discussed herein.
[0086] In the example depicted by FIG. 1D, a communications channel is selected for use by a participant of a communications arrangement, the participant is told which communications channel to use, and the participant communicates using the selected communications channel. However, in other examples, the participant may be told to not use the selected communications channel, which may be appropriate if the selected communications channel has poor performance. Also, the participant may be told to skip the selected communications channel and use the next communications channel of a specified sequence of communications channels.
[0087] In block 112, the performance of the communications channels of the communication system is determined. For example, for a communications system that uses 90 channels, some or all of the 90 channels may be tested to determine channel performance. The determination of the performance of the communications channels may be performed by a different entity or device than the entity or device that performs the functions described in FIG. 1D. In general, the different functions described herein may be performed by different entities or devices.
[0088] In block 114, a communications channel is selected based on the performance of the communications channels determined in block 112. One or more performance criteria and one or more selection criteria may be used with the performance information to select the communications channel. For example, a communications system may experience interference on channels 3 through 5 from one communications system and on channels 50
through 54 from another communications system, and the channel testing may indicate a high bit error rate (BER) on those channels.
[0089] Channels may be classified by comparing the test results to the performance criteria. For example, the performance criteria may be a specified value, or a specified threshold, that is used to determine whether the channel performance is acceptable or not. As a particular example, if the BER for a channel satisfies (e.g., exceeds) the specified threshold, the channel is classified as "good," whereas a channel with a BER that does not satisfy the specified threshold is classified as "bad." Other classification approaches may be used, and the invention is not limited to a particular classification approach.
[0090] The reason why a bad channel's performance does satisfy the specified threshold may be due to a variety of reasons, including but not limited to, the channel being used by another communications system or noise from other interference sources. For example, in a Bluetooth communications system, microwave ovens are a common source of interference.
[0091] After classifying the performance of the channels, a communications channel is selected based on the selection criteria. For example, the selection criteria may be to select a good channel but not a bad channel. By using good communications channels, a communications system may avoid interference present on bad channels. Other selection criteria may be chosen to select the channel that provides the best performance among the available channels. Yet other selection criteria may be chosen to randomly select a channel from among the good channels.
[0092] Although this example describes the use of a particular type of performance criteria to classify channels and particular selection criteria to select from the classified channels, other approaches may be used to select channels. For example, channels may be selected based on comparing performance results to one or more criteria without first classifying the channels. Also, other criteria may be used, for example, that particular channels are to be selected regardless of the test results because the particular channels are uniformly distributed over the communications band. As another example, a selection criterion may be that particular channels are not to be selected regardless of the test results. Such channels may be previously identified as having a large amount of interference from particular sources, such as another communications system that operates frequently but irregularly. As a result the other system may not be detected during testing and the channels may be selected, although at times there may be significant interference on those channels. Therefore, the selection criteria may specify a list of channels that are not to be selected, even if the channels on the list have satisfactory performance during testing.
[0093] In block 116, channel identification data that identifies the communications channel selected in block 114 is generated and provided to a participant of the communications system. For example, in a Bluetooth or IEEE 802.15.1 FH communications system, the master may provide a slave with data that identifies the communications channel that is selected in block 114. The channel data may be appended to a normal, or standard, data packet sent from the master to the slave. Alternatively the channel data may be incorporated into a special packet, such as by including the channel data in the packet header or payload. The master may send the packet to the slave over a communications channel that is determined according to the frequency hopping sequence.
[0094] In block 118, a communication is received from the participant over the communications channel that is selected in block 114. For example, in a FH communications system, the communication is a packet that is sent from the slave to the master over the selected communication channel in response to the packet sent from the master to the slave in block 116.
[0095] C. Transferring Functions Between Participants
[0096] Continuing with reference to FIG. 1D, in block 120, a master participant is selected. The selection of the master may be performed by a variety of methods, including those discussed above with respect to FIG. 1A.
[0097] In block 122, an associate master participant is selected prior to the failure of the master participant. For example, referring to communications arrangement 100 of FIG. 1A, participant P5 is designated as an associate master participant by master participant P4, slave participants PI-P3, or another mechanism or process. Associate master participant P5 may perform all of the functions of slave participants P1-P3 prior to associate master participant P5 being promoted to the role of master participant, as discussed below.
[0098] In block 124, if the designated handoff criteria are satisfied, the associate master participant assumes the role of the master participant. For example, as depicted in FIG. 1B, associate master participant P5
assumes the role of master participant, i.e., performs the functions previously assigned to master participant P4, if any of a set of handoff criteria are satisfied. The particular handoff criteria used may vary depending upon the requirements of a particular application and the invention is not limited to any particular handoff criteria.
[0099] One example handoff criteria is a request from the current master participant. Master participant P4 may know that it can no longer perform the assigned functions and requests associate master participant P5 to assume the role of the master participant. For example, master participant P4 may be a mobile device whose available power has fallen below a specified threshold. Alternatively, master participant P4 may know that it is moving out of range of one or more of the other participants or is experiencing a poor communications link between itself and one or more of the other participants.
[0100] Another example handoff criteria is a failure of master participant P4. Associate master participant P5 may be notified by other participants or another process or mechanism that master participant P4 has failed. Alternatively, associate master participant P5 may itself detect that master participant P4 has failed and assume responsibility for performing the functions. According to one embodiment of the invention, associate master participant P5 monitors data transmitted by master participant P4
and if master participant P4 has not made any communications within a specified period of time, then associate master participant P5 assumes that master participant P4 can no longer perform the functions of master participant, i.e., has failed, and associate master participant P5
assumes the role of master participant. Additional details of the functions and role of associate master participants are described in more detail hereinafter.
[0101] According to an embodiment of the invention, after the associate master participant assumes the role of the master participant, a new associate master participant is selected. For example, referring to FIGS. 1A and 1B, after associate master participant P5 assumes the role of master participant, a new associate master participant may be designated by the new master participant P5, the remaining slave participants P1-P3, or some other mechanism or process. As depicted in FIG. 1C, participant P2 is designated as the new associate master participant.
[0102] D. Additional Examples for Selecting Channels
[0103] According to one embodiment of the invention, the communication from the participant includes a measurement of the performance of the channel used in sending the packet in block 116. For example, in a FH communications system, the packet from the master to the slave may be used by the slave to measure the performance of the channel used to send the packet to the slave. The performance measurement may be incorporated into the reply packet from the slave to the master. The performance measurement may be stored by the slave, as discussed below.
[0104] According to another embodiment of the invention, the communication from the participant is used to generate a measure of the performance of the channel used in sending the communication. For example, in a FH communications system, the packet from a slave to the master may be used by the master to measure the performance of the channel used to send the reply packet to the master, and the performance measurement may be stored by the master, as discussed below.
[0105] In the example depicted by FIG. 1D, the selected communications channel is used by the slave to respond to the master. By using channels that are selected based on having acceptable performance, the communications system avoids channels with unacceptable performance. However, the opposite approach may be used to select channels with unacceptable performance and inform participants of the communication system not to use such channels. According to another embodiment of the invention, the communications system may be configured to not use the selected communications channel for transmitting the communication from the participant. For example, the communications channel may be selected because the channel has performance that falls below the specified threshold. Informing the participant that the poor performing channel is not to be used helps to avoid the loss of packets over the selected channel.
[0106] Other approaches for using a selected channel may be used. According to yet another embodiment of the invention, the communications system may be configured to skip the selected communications channel and use the next channel in a specified sequence of channels, such as a frequency hopping sequence. Other implementations may combine two or more of the above approaches for using the channel identification data to determine which channel the participant should use. Further, the communications system may be configured to inform a participant of both the selected communications channel and indicate how the selected communications channel is to be used. For example, the channel data may include information indicating whether the selected channel is to be used, not used, or skipped.
[0107] A selected communications channel may be provided to more than one participant in a communications system, and the selected communications channel may be used by the participant for more than one communication. However, the use of a set or group of selected communications channels is typically preferred over the repeated use of a single selected communications channel, such as the best performing channel. For example, the repeated use of the same selected communications channel by multiple participants or by a particular participant for multiple communications may not be desirable due to changes over time in the performance of the selected channel. Also, the repeated use of a channel may be inconsistent with the basic approach of many communications system to use different communications channels.
[0108] According to another embodiment of the invention, prior to each communication with another participant, the channel selection process is repeated, such that a different channel is typically selected for each communication. For example, prior to communicating to a particular participant, a master may select a communications channel based on the approach illustrated in FIG. 1D. Then prior to the master's next communication, which may be to the same participant or a different participant, the master repeats the channel selection process. Different channels may be selected because the channels differ in performance between the master and the different participants, because the transient nature of interference has changed the performance of the channels, or because the master randomly selects a particular channel from among the channels having acceptable performance. As a result, the master may choose a different communications channel than that chosen for the previous communication. In general, different packets from the master to the participants identify different communications channels in the communications system.
[0109] According to other aspects of the invention, the master does not include channel data in every packet sent to each participant. For example, some slaves or associate masters may not support the channel selection approach described herein. Further, the master may not always select a different channel for each participant to use in responding to the master. For example, the communication system may use a specified set of channels, and therefore some channels will be selected more than once.
[0110] The determination of channel performance depicted by block 112 may be repeated or updated. For example, channel performance testing may be performed according to a specified schedule, such as the expiration of specified time period, or as a result of monitoring and detecting new interference among the selected set of channels, such as from another communications system that previously did not cause interference. As another example, normal communications between the participants of the communications system may be monitored to determine channel performance.
[0111] As a result, the method depicted in FIG. 1D may be used by a communications system to avoid poor quality channels in a quasi-adaptive manner by selecting communications channels with acceptable quality. By using this novel approach to quasi-adaptively select communications channels based on channel performance, interference problems are reduced and transmission performance is improved for both the communications system that selects the communications channels to use and other interfering communications systems. Also, by reducing interference, the power level required to achieve a specified transmission quality is decreased, thereby increasing battery life of mobile devices.
[0112] The approach described herein may be characterized as "robust" because interference in a communications system is reduced or eliminated by using channels that have been tested and determined to be "good" because channel performance satisfies a specified threshold. In contrast, channels that have been tested and determined to be "bad" have channel performance that does not satisfy the specified threshold. The approach described herein is a simple scheme that is easy to implement on many devices due to the low computational and memory requirements and is fully interoperable with devices that do not support this novel approach.
[0113] E. Selecting Participants Based on Performance
[0114] FIG. 1E is a flow diagram 130 that depicts an approach for selecting participants with whom to communicate based on channel performance, according to an embodiment of the invention. Blocks 120, 122, and 124 are the same as in FIG. 1D, as described above.
[0115] In block 134, the performance of a communications channel between one participant and one or more of the other participants of the communication system is determined. For example, in a FH communications system, the performance of a particular channel between a master and two or more slaves may be measured.
[0116] In block 138, a particular participant of the one or more other participants is selected based on the performance of the communications channel determined in block 134. For example, in a FH communications system, the master may communicate with a set of two or more participants. The particular communication channel over which the master will communicate with each participant is based on the frequency hopping sequence, and therefore the master is not free to select the communications channel to be used. However, the master may choose which participant of the set of participants to communicate with over the particular channel based on the performance of that channel between the master and the different participants.
[0117] One or more performance criteria and one or more selection criteria may be used with the performance information to select the participant. For example, in FIG. 1A, communications arrangement 100 may experience interference on channel 17 between master P4 and slaves P1 and P3, but channel 17 may not have an interference problem between master P4 and slave P2 and between master P4 and associate master P5. The performance of channel 17 may be different for some participants because interference sources are closer to some slaves than others.
[0118] Channels may be classified by comparing the test results to the performance criteria. For example, the performance criteria may be a specified value, or a specified threshold. As a result of the performance testing, channel 17 may be classified as "bad" between master P4 and slaves P1 and P3 and as "good" between master P4 and slave P2 and associate master P5.
[0119] After classifying the performance of the channels, a communications channel is selected based on the selection criteria. For example, the selection criteria may be to select a particular participant for whom the particular channel is a good channel instead of a participant for whom the particular channel is a bad channel. Thus, by selecting a particular participant for whom the communications channel is good, the communications system performing the channel selection may avoid using bad channels resulting in increased throughput for the communications system by minimizing transmission errors and lost packets.
[0120] Although this example describes the use of a particular type of performance criteria to classify channels and particular type of selection criteria to select particular participants with whom to communicate, other approaches may be used to select a set of channels. For example, participants may be selected based on comparing performance results to one or more criteria without first classifying the channels. Also, other criteria may be used, such as that particular participants are, or are not, to be selected regardless of the test results, or that the participant with the best performance for the particular channel is to be selected.
[0121] In block 142, a communication is sent to the particular participant over the communications channel. For example, in the example above, master P4 may select to send a communication over channel 17 to associate master P5 because channel 17 is classified as a good channel between master P4 and associate master P5. Master P4 could have selected slave P2
because channel 17 is also classified as a good channel between master P4
and slave P2. However, master P4 would not select slaves P1 or P3 because channel 17 is classified as a bad channel between master P4 and slaves P1
and P3.
[0122] F. Managing Channel Performance Data
[0123] FIG. 1F is a flow diagram 160 that depicts an approach for managing performance data for communications channels between participants of a communications system, according to an embodiment of the invention. Blocks 120, 122, and 124 are the same as in FIG. 1E, as described above.
[0124] In block 164, the performance of the communications channels is determined. For example, for a communications system that uses 50
channels, some or all of the 50 channels may be tested to determine channel performance.
[0125] In block 168, performance data is created and maintained for the performance of at least one channel between two participants. For example, in a FH communications system, the master may create and maintain performance data for the set of communications channels used by the FH communication system for communications between the master and the slaves. As a more specific example, the master may store the performance data in a lookup table that includes data for some or all of the communications channels between the master and some or all of the slaves of the communications system. The master's lookup table may also include data for other participants, such as an associate master.
[0126] In block 172, additional performance data is requested and received from another participant. For example, a particular slave may create and maintain performance data for the set of communications channels used by the FH communication system for both the communications between the slave and the master and the communications between the slave and other slaves or the associate master. The master may send a request to the particular slave for the particular slave's performance data. As a more specific example, the particular slave may store the performance data in a lookup table that includes data for some or all of the communications channels between the particular slave and the master, and some or all of the other slaves of the communications system. In response to the request from the master, the particular slave provides the master with some or all of the performance data maintained by the particular slave.
[0127] In block 176, revised performance data is created and maintained. For example, the master may combine the performance data received from the particular slave in block 172 with the performance data determined by the master in block 164. Such combined data may reflect the transmission performance from the master to the slaves and associate master, from the slaves and associate master to the master, and between the slaves and associate master. As another example, the master may maintain the requested performance data from the slave separately from the performance data determined in block 164.
[0128] In other embodiments, performance data is updated based on performance measurements of normal packets used by the participants of the network. For example, as discussed above, communications from participants may include a measurement of the performance of the communications channel used in sending a previous communication to the participant, and the communications from participants may be used to measure performance of communications channels used by the participants to send the communications. Such performance measurements may be used to revise or update performance data, such as by a master that maintains a lookup table of performance data for the communications channels between the master and the slaves of the communications system.
[0129] II. Measuring Channel Performance, Classifying Channels, and Storing Related Information
[0130] According to one embodiment of the invention, channel performance is determined using one or more channel performance measurement techniques. For example, any of the techniques for measuring channel performance that are discussed below may be used alone or in combination. Although testing is normally performed on all available communications channels, it is not necessary to test all channels, nor is it necessary to use the same method for testing performance of different channels.
[0131] According to other aspects of the invention, channel performance may be determined at an initial time for some or all of the channels, or the channel performance may be initially set at a specified initial value. Channel performance may be retested for some or all of the channels of the communications system, such as at periodic intervals or when a particular condition occurs, such as the detection of new interference. In addition, channel performance may be monitored during normal operation, and the results of the monitoring used to update or replace earlier channel performance determinations. Further, channel performance may be represented by quantitative indications, including but not limited to, scores or other values, and/or by qualitative indications, including but not limited to, low, medium, and high, pass and fail, and whether a packet is lost or not.
[0132] According to yet other aspects of the invention, channel performance may be determined both by participants that are the intended recipient of a packet and by participants that "listen" to packets being sent to other participants. For example, in a FH communications system, a master may send a packet to a particular slave, and the particular slave may measure the performance of the channel used by the master to send the packet. However, the other slaves and the associate master in the communications system may also receive the transmission from the master to the particular slave, even if the transmission was only intended for the particular slave, because the other slaves and the associate master are listening to the master at the same time. Each slave and the associate master determines whether it is the intended recipient of the packet, such as by examining the address information in the header of the packet.
[0133] Participants that receive packets intended for another participant may be described as having "listened" to the transmission from the master to the particular slave that is the intended recipient. Only the particular slave or associate master for whom the packet is intended is described as being the "recipient" of the packet. Similarly, when a recipient sends a reply to a master, other slaves and the associate master in the communication system may listen for the transmission, and based on the packet received, determine a measurement of channel performance for the channel used to send the reply.
[0134] As a result, a particular slave may measure the performance of channels between the particular slave and the master based on both packets sent by the master to the particular slave and packets sent by the master to other participants. The particular slave may measure the performance of channels between the particular slave and other participants based on packets that the particular slave listens to and that are sent by the other participants to the master. Further, the master may measure the performance of channels between the master and each slave and the associate master based on packets sent by the slaves and associate master to the master. Finally, as explained below, the participants of the network may request and receive performance measurements from other participants.
[0135] A. Approaches for Channel Performance Measurement
[0136] According to one embodiment of the invention, redundancy can be included in the structure of the packets used in the communications system and then used to determine channel performance. For example, a specified pseudo-random sequence may be appended to the header of some or all of the packets used for communications in the system. Because the participants in the communications system know the pseudo-random sequence, the participants can determine the bit error rate (BER) score, or value, based on detected errors in the pseudo-random sequence. By using a common technique, such as the pseudo-random number sequence and determining the BER, the same performance measurement may be used for some or all of the channels of the communications system, which may help to simplify the tracking and combining of performance data.
[0137] According to other aspects of the invention, other sequences besides a pseudo-random sequence may be used, including but not limited to, a random sequence, a specified sequence, or any other data that is known to the participants of the communications system. This allows the participants to determine if errors occur in the data and in some situations, the extent or number of errors.
[0138] According to another embodiment of the invention, a received signal strength indicator (RSSI) is used to test the performance of communications channels. One approach for determining the RSSI for a channel is to have a master send a NULL packet to a participant. A NULL packet generally includes only an access code and a packet header. NULL packets are often used to ensure that a slave is still synchronized to the communications network.
[0139] When a participant receives a NULL packet, the participant does not send a return packet to the master. By listening to the return channel from the synchronized participant, the signal received by the master represents the noise floor of the channel since the participant is not transmitting on the channel. If there is interference, such as from another communications system, the RSSI will be high. Conversely, if there is no interference, the RSSI will be low. According to another aspect of the invention, channel performance is measured on a scale from very low RSSI values to very high RSSI values corresponding to the noise level measured on the channel, thereby providing a range of channel performance measurements.
[0140] According to another embodiment of the invention, the known preamble at the start of the packet is used to test the performance of communications channels. For example, identification packets, NULL packets, POLL packets, or any other kind of packet may be used to correlate the received preamble against the known preamble. A packet that does not pass the correlation is discarded (e.g., it is a lost packet). Also, the errors that occur may be used to determine a BER score/value.
[0141] According to another embodiment of the invention, a header error check (HEC) is used to test the performance of communications channels. The HEC is a check on the contents of the packet header, such that if an error occurs in the packet header, the packet does not pass the check and the packet is discarded (e.g., it is a lost packet).
[0142] According to another embodiment of the invention, a cyclic redundancy check (CRC) is used to test the performance of communications channels. The CRC may be a check of either the payload of the packet or the complete contents of the packet, depending on the communications system protocol being used. As an example, in Bluetooth and IEEE 802.15.1, the data packet must pass a CRC check, otherwise the packet must be retransmitted. A retransmission request (RR) indicates poor channel performance.
[0143] According to another embodiment of the invention, forward error correction (FEC) is used for channel performance testing of transmissions between participants of a communications system. FEC may be used on either a packet header or on the payload of the packet. FEC is used as a form of redundant data encoding to allow the recipient to ensure the integrity of the received data and to correct any identified errors. As an example, in Bluetooth or IEEE 802.15.1, the packet header is 1/3 FEC coded, and the payload is 2/3 FEC coded. FEC coding may be used for both an NEB calculation and for error correction.
[0144] The descriptions of each channel performance measurement technique above describe the use of the same method for all transmissions, such as master to slave and slave to master transmissions. However, different methods may be used for each direction of transmission, and different methods may be used for different transmissions in the same direction. For example, the RSSI approach may be used for master to slave transmissions while the preamble correlation is used for slave to master transmissions. In addition, different methods may be combined, such that to have a test considered successful, two or more tests must provide an acceptable result. For example, to receive a "pass" indication, a packet may have to pass both the preamble correlation and the HEC tests. Furthermore, the tests used may change over time depending upon the effectiveness of the tests and the requirements of a particular application or implementation. Finally, other approaches that provide an indication of channel performance besides those described herein may be used.
[0145] B. Approaches for Channel Classification
[0146] According to one embodiment of the invention, a channel is classified based on the measured channel performance and one or more classification criteria. For example, a channel may be classified as "good" or "bad" based on the results of the channel performance testing by applying one or more performance measurements to specified performance criteria as discussed above. As used herein, a good channel's performance satisfies a specified criterion, or a specified threshold, whereas a bad channel's performance does not satisfy the specified criterion or threshold. Although this discussion assumes that all available channels, or all channels that could be used by the communications system, are tested and classified, particular implementations may test and classify fewer than all of the channels. Also, multiple tests for channels may be made and combined, such as by averaging results, to determine a particular performance measurement.
[0147] According to another embodiment of the invention, different types of test results may be used and combined. For example, tests that provide NEB results, either numerical or converted to a qualitative scale, may be combined with CRC results of "pass/loss" to arrive at an overall assessment of channel performance. The manner in which such results are combined depends on the particular implementation, and the invention is not limited to any particular approach. For example, different types of test results may be converted to a single type of scale and then combined or averaged to reach a final result. As another example, different test results may be combined using weighting factors that favor some types of tests over others to arrive at a final result.
[0148] The conversion of numerical results to qualitative results and the combining of individual tests results to achieve a classification of each channel depends on how competing tradeoffs are to be weighed for a given implementation. For example, high channel performance may be desired, but setting a standard that is too high (e.g., all test results must be "high") may limit the number of channels classified as "good," resulting in few good channels available for use. This is turn may necessitate frequent retesting of the channels when supposedly poor performance is detected. Conversely, setting a standard that is too low allows for a larger pool of channels to be used, but then channels with significant interference are classified as good when in fact channel performance is low and channels are not retested when new interference occurs.
[0149] According to another embodiment of the invention, the results of channel performance testing are compared to one or more acceptance criteria. For example, if the testing provides NEB results, an average value may be determined and compared to an acceptance criterion, such as a threshold value. If the testing results exceed the threshold, the channel is classified as "bad", but if the testing results do not exceed the threshold, the channel is classified as "good." As another example, the correlation approach, HEC, and CRC may all be used to determine whether a packet is lost or not (e.g., whether an error occurs as a result of the transmission of the packet) and the packet loss ratio determined and compare to a threshold value. For example, assuming that a threshold of 20% is established, the loss of more than 10 packets out of 50 on a particular channel would result in the channel being classified as bad, whereas losing 10 or fewer packets on a particular channel would result in the channel being classified as good.
[0150] C. Maintaining Channel Performance and Channel Classification Information
[0151] According to one embodiment of the invention, channel performance information is maintained by one or more participants of the communications system. For example, in a FH communications system, a master may maintain channel performance data for each channel and for each slave in the system. However, other implementations and communications systems may maintain data on fewer than all of the available channels and for fewer than all of the other participants in the system, and other participants besides a master participant may maintain performance data.
[0152] FIG. 2A is a block diagram that depicts a performance lookup table 200 that includes channel performance data, according to one embodiment of the invention. The example performance lookup table depicted in FIG. 2A includes a row for slaves A, B, C, . . . , nn and column for channels 1, 2, 3, 4, . . . , n, although any number of slaves and channels may be included, along with an associate master or other types of participants. Different organizations of the information may be used besides that depicted in FIG. 2A. In addition, one row in the lookup table of the master may be for the selected associate master, and one row in the lookup table of the associate master may be for the master. The performance data included in performance lookup table 200 is in the form of quantitative measurements that are on a scale of 0 to 10 with 0 being the lowest score (i.e., relatively poor channel performance) and 10 the highest score (i.e., relatively good channel performance). However, other scales for quantitative measurements may be used as well as qualitative measurements.
[0153] Data in a performance lookup table may be missing for a particular channel or slave. For example, performance lookup table 200 does not include data for slave B or for channel 3. Measurements for a particular slave or a particular channel may not be included for a variety of reasons. For example, a particular slave may be omitted or not have any data because the slave does not support the channel selection or participant selection approaches described herein. As another example, a particular channel may be omitted or not have any data because the particular channel was determined to be bad at the initialization of the communication system and therefore is not used by the system. As yet another example, in a FH communications system, the frequency hopping sequence may use fewer than all of potential channels that are potentially available, and the selected frequency hopping sequence may not include the particular channel, such as when the particular channel is not needed or when the particular channel is determined to have unacceptable performance.
[0154] According to another embodiment of the invention, one or more participants of a communications system may maintain a performance lookup table that may include data for some or all of the channels between the participant and some or all of the other participants of the communications system. For example, in a FH communications system, the master and associate master typically each maintain a performance lookup table, and some or all of the slaves may also maintain performance lookup tables.
[0155] According to one embodiment of the invention, channel classification information is maintained by one or more participants of the communications system. For example, in a FH communications system, a master may maintain channel classification data for each channel and for each slave in the system. The master may maintain the data by storing data locally or at a separate location. Similarly, the associate master may maintain channel classification data for each channel and for each slave and the master in the system. However, other implementations and communications systems may maintain data on fewer than all of the available channels and for fewer than all of the other participants in the system, and other participants besides a master participant and an associate master participant may store classification data.
[0156] FIG. 2B is a block diagram that depicts a classification lookup table 250 that includes channel classification data, according to one embodiment of the invention. The example performance lookup table depicted in FIG. 2B includes a row for slaves A, B, C, . . . , nn and column for channels 1, 2, 3, 4, . . . , n, although any number of slaves and channels may be included, along with an associate master or other types of participants. Different organizations of the information may be used besides that depicted in FIG. 2B. The classification data given in performance lookup table 200 is in the form of a usability classification approach in which a useable channel is identified by "YES" and an unusable channel is identified by "NO." Other classification approaches may be used, such as classifying channels as good or bad or as useable and unusable, and the invention is not limited to a particular classification approach.
[0157] Data in a classification lookup table may be missing for a particular channel or slave. For example, classification lookup table 250
does not include data for slave B or for channel 3. Measurements for a particular slave or a particular channel may not be included for a variety of reasons, including those described above with reference to channel performance data and performance lookup table 200 of FIG. 2A.
[0158] According to another embodiment of the invention, one or more participants of a communications system may maintain a classification lookup table that may include data for some or all of the channels between the participant and some or all of the other participants of the communications system. For example, in a FH communications system, the master and associate master typically have classification lookup tables, and some or all of the slaves may have classification lookup tables.
[0159] In a particular communication system, a participant may maintain a performance lookup table, a classification lookup table, both types of lookup tables, or a lookup table that includes both performance and classification data. For example, a particular implementation of a communications network may be configured to use performance lookup tables, and channels are classified as needed based on comparing the performance data to one or more performance criteria. Storing performance data provides more information about the performance of the communications system, but may require additional storage space. Other implementations may be configured to use classification lookup tables, which may minimize storage requirements because the data need only include data indicating the whether a channel is good or bad instead of a variety of potential performance measurements. However, less information is available about the performance of each channel for each participant.
[0160] Although embodiments of the invention are described herein in the context of maintaining channel performance and classification data in lookup tables, channel performance and classification data may be maintained in any form, including but not limited to, other types of tables besides lookup tables or a database.
[0161] III. Selecting Channels and Informing Participants
[0162] According to one embodiment of the invention, a participant selects a communications channel and identifies the selected communications channel to another participant by using channel identification data. For example, the performance data, such as in a performance lookup table, or the classification data, such as in a classification lookup table, may be used to select a communications channel based on one or more selection criteria. As a particular example, the classification lookup table may classify each channel as either good or bad, and the channel is selected from the good channels that are available between the participant making the selection and the other participant that will use the selected channel to determine on which channel to send a reply.
[0163] FIG. 3A is a block diagram that depicts a master to slave packet 300 that identifies the selected communications channel, according to one embodiment of the invention. While the packet example depicted in FIG. 3A is presented as being from a master to a slave, in general such a packet may be transmitted from any participant to another participant, including an associate master participant, and the invention is not limited to a particular manner of making transmissions.
[0164] Master to slave packet 300 is transmitted by the master to a particular slave. Master to slave packet 300 includes a preamble 304, a header 308, a payload 312, and channel data 316. Master to slave packet 300 may be used in a Bluetooth or an IEEE 802.15.1 FH communications system. Preamble 304, header 308, and payload 312 may be the portions of a normal, or standard, packet for the particular communications system, and channel data 316 may be appended, or "piggybacked", onto the normal packet. Therefore, a special packet is not required to provide channel data 316 from the master to a slave. However, in other implementations and other communications systems, channel data 316 may be incorporated into other parts of a normal packet, or a special packet may be used, which incorporates channel data 316.
[0165] Preamble 304 is used to identify the FH communications system and for the slaves to synchronize with the master. Preamble 304 is a binary string whose length depends on the communications protocol. For example, for a Bluetooth based FH communications system, known preamble 304 is 72
bits in length.
[0166] Header 308 includes control information, such as the origination and destination address of the packet, the type of packet, and the priority level for the packet.
[0167] Payload 312 includes the contents or data being carried by master to slave packet 300, as compared to the control information, or overhead, of header 308.
[0168] Channel data 316 identifies the selected communications channel. For example, in a Bluetooth based FH communications system, a master may select channel 42 based on a performance data lookup table, such as by identifying the selected communications channel based on selection criteria and the performance data for the channels between the master and the particular slave to which master to slave packet 300 is to be sent.
[0169] When a slave receives master to slave packet 300 that includes channel data 316, the slave may determine the particular communication channel on which to respond, hereinafter referred to as the response communications channel, by using one or more of a number of approaches. For example, the selected channel that is identified by channel data 316
may be treated by the slave as the communications channel on which the slave is to respond to the master. As another example, the selected channel that is identified by channel data 316 may be treated by the slave as a communications channel that the slave is not to use when responding. As yet another example, the selected channel that is identified by channel data 316 may be treated by the slave as a communications channel that the slave is to skip in a sequence of channels, such as a frequency hopping sequence, and thus the slave moves onto the next channel in the sequence instead of using the selected communications channel.
[0170] According to another aspect of the invention, channel data 316 may include a redundancy technique, such as being 1/3 FEC encoded, to help the slave that receives channel data 316 to properly understand channel data 316 even if errors occur during the transmission.
[0171] According to another embodiment of the invention, a participant responds on a particular communications channel that is determined based on a selected communications channel, and the participant provides as part of the response a measurement of the performance of the previous communications channel used for the previous transmission to the participant, and the transmission is not limited to a particular manner of making transmissions.
[0172] FIG. 3B is a block diagram that depicts a slave to master packet 350 that includes a performance measurement for a previous communications channel, according to one embodiment of the invention. While the packet example depicted in FIG. 3B is presented as being from a slave to a master, in general such a packet may be transmitted from any participant to another participant, including an associate master participant.
[0173] Slave to master packet 350 is transmitted by the slave to the master in response to master to slave packet 300 that the master transmitted to the slave. Slave to master packet 350 includes preamble 304, a header 358, a payload 362, and performance data for last channel 366. Master to slave packet 300 may be for a Bluetooth or an IEEE 802.15.1 FH communications system. Preamble 304, header 318, and payload 362 may be the portions of a normal, or standard, packet for the particular communications system, but with performance data for last channel 366 incorporated into the normal packet after payload 362. However, in other implementations and other communications systems, performance data for last channel 366 may be incorporated into other parts of a normal packet, such as between header 358 and payload 362, or included in a special packet.
[0174] Preamble 304 in slave to master packet 350 is the same as preamble 304 in master to slave packet 300 because in this example, both packets are used in the same communications system and therefore both packets use the same preamble 304 for identification of the communications system.
[0175] Header 358 includes control information, such as the origination and destination address of the packet, the type of packet, and the priority level for the packet. The contents of header 358 are typically different from the contents of header 308 because the control information is different between slave to master packet 350 and master to slave packet 300 (e.g., the origination and destination addresses are different).
[0176] Payload 362 includes the contents or data being carried by slave to master packet 350, as compared to the control information, or overhead, of header 358.
[0177] Performance data for last channel 366 is data that indicates a performance measurement of the channel used by the master to send master to slave packet 300 to the slave. For example, the slave may use one of the channel performance measurement techniques discussed above to determine a score for the transmission of master to slave packet 300, such as a BER score or an RSSI value. By including performance data in the reply packet from the slave to the master, the master may obtain performance data on other channels and on the master to slave transmission direction in addition to performance data on the channels used by slaves to communicate with the master and on communications in the master to slave direction. According to another embodiment of the invention, the slave provides a channel classification instead of a channel performance measurement.
[0178] IV. Network and Participant Initialization
[0179] Communications systems conventionally perform an initialization procedure to identify and/or locate the participants and to elect a master participant. FIG. 4 is a flow diagram 400 that depicts an approach for initializing a communications arrangement having a master participant, according to an embodiment of the invention. For purposes of explanation, embodiments of the invention are described hereinafter in the context of exchanging data between participants using packets. Any type of packet may be used and the invention is not limited to any particular packet. For example, the packets may include a preamble, header, payload and tail, alone or in any combination. Furthermore, embodiments of the invention are described in the context of frequency hopping where successive data packets are transmitted on different frequency channels and each participant transmits in an assigned time slot, although the invention is not limited to the frequency hopping context.
[0180] In block 404, participants are identified, such as participants P1
through P5 in FIG. 1A. For example, in a Bluetooth FH communications system, a connection is established between two participants, and then other participants join the communications system. The first two devices may find each other in a variety of ways. For example, one participant may continually scan one channel for a specified amount of time while the other participant transmits a specified sequence on each available channel. After each transmission on a channel, the other device listens for a specified amount of time for a reply. When both participants are on the same channel, the first device "hears" the other device and replies with a transmission on the same channel. Negotiation for a link between the two participants may then be performed. The additional participants may join the communications system via the same procedure, although the communications system may be put on hold while another participant is added.
[0181] In block 408, a master participant is selected according to a specified selection algorithm. In the present example, participant P4 is selected as the master participant, either by all of participants P1-P5, by the other participants P1-P3 and P5, or by some other mechanism or process involved in the management of communications arrangement 100. For example, in the example above, the participant transmitting the predefined sequence may be specified as the default master, although the default may be changed by the specified selection algorithm.
[0182] In block 412, a frequency hopping sequence is selected, provided that the communications system uses a frequency hopping protocol. The invention is not limited to any particular frequency hopping sequence or approach for selecting the frequency hopping sequence, nor to a communications system that uses a frequency hopping sequence to select which channels to use out of a set of channels.
[0183] In block 414, an associate master participant is selected. The selection of the associate master is made from the other participants in the communications arrangement, such as participants P1-P3 and P5. In the present example, participant P5 is selected as the associate master participant. The selection of an associate master may be made by the participants P1, P2, P3, and P5, or the master participant P4, or any type of selection mechanism that may be integrated into communications arrangement 100, or which may be separate from communications arrangement 100.
[0184] In block 416, a determination is made whether the master supports the enhanced mode of selecting a channel based on channel performance, according to an embodiment of the invention. If not, the approach continues to block 420 that indicates that all the participants of the communications system use the normal, or non-enhanced, mode because the master does not support the enhanced mode (even if some or all the other participants support the enhanced mode). In the non-enhanced mode, channels are not selected based on channel performance as described herein.
[0185] However, if in block 416 the master is determined to be able to support the enhanced mode of selecting a channel based on channel performance, the approach continues to block 424 that indicates that the participants that support the enhanced mode can use the enhanced mode. Note that not all participants are required to support the enhanced mode, so that if some participants, such as some legacy devices acting as slaves or as an associate master, do not support the enhanced mode, communications may continue to be carried out according to the non-enhanced mode for communications with those participants. Once communications arrangement 100 has been initialized, master P4 begins performing its assigned functions. Participants P1, P2, P3, and P5
perform functions as instructed by master P4 and communicate with master P4.
[0186] The order in which the steps described with respect to blocks 412, 414, and 416 are performed may vary depending upon the requirements of a particular application. For example, the associate master participant may be selected before the frequency hopping sequence is selected.
[0187] Once communications arrangement 100 has been initialized, master participant P4 begins performing its assigned functions. Slave participants P1-P3 and associate master participant P5 perform functions as instructed by master participant P4 and also communicate with master participant P4. Associate master participant P5 may also perform periodic checks to determine whether master participant P4 can no longer perform its assigned functions and whether the associate master participant P5 is to assume the role of master participant P4.
[0188] According to one embodiment of the invention, participants that maintain data indicating the performance and/or classification of channels may reset the stored data when the communications system is initialized. For example, if a participant, such as a master, associate master, or a slave, has a classification lookup table that indicates whether each channel between the participant and the other participants is either good or bad, the entries in the lookup table may be reset to good at initialization. Such a resetting approach may be useful in communications systems that are configured to reclassify channels as bad when unacceptable performance measurements are determined. As time passes, more channels are reclassified as bad due to the transient nature of interference and other sources of poor channel performance, which limits the number of good channels that are available. However, some channels that are previously determined to be bad may no longer have poor channel performance, such as when the source of the interference is no longer present or otherwise changes. Therefore, by resetting the lookup tables at initialization, the number of potentially good channels available is increased and previously bad channels that are no longer subject to poor performance may be used again.
[0189] V. Master Connection Sequence
[0190] Example functions performed by a master are now described with reference to flow diagrams 500, 530, 550, and 580 of FIGS. 5A, 5B, 5C, and 5D, respectively. The four example functions described hereinafter are: (1) sending a normal packet to a recipient; (2) requesting an associate master to assume the role of master; (3) requesting that another participant send the participant's lookup table data to the master; and (4) requesting a slave to assume the role of associate master. While the examples below use a master, an associate master, and one or more slaves, a network with any types of participants, including but not limited to masters, associate masters, and slaves, may employ the approaches described therein. Also, while the examples herein include storing classification data in lookup tables, other approaches for maintaining data may be used, and the invention is not limited to a particular approach.
[0191] Note that, in general, an associate master may perform the functions performed by a slave since the associate master is typically a slave that has been designated as the successor to the master. However, a slave generally does not perform the functions of an associate master. For convenience, the term "recipient" is used herein to denote a participant communicating with a master, and the recipient may be any type of participant, including but not limited to, an associate master or a slave. As a result, the following examples are generally described in terms of interactions between a master and a recipient although the examples are equally application to interactions between a master and associate master or slave as well as other types of participants.
[0192] A. Normal Packet
[0193] FIG. 5A is a flow diagram 500 that depicts an approach for a master to send a normal packet to a recipient, according to an embodiment of the invention. While FIG. 5A describes the transmission of a normal packet between a master and a recipient (i.e., a slave or an associate master), other participants may utilize a similar approach for sending and receiving packets. Also, while FIG. 5A and the other figures discussed herein depict a certain set of steps arranged in a particular