Abstract:
An inquiry message is transmitted successively on each of a first plurality of transmit frequencies ( 44 - 48 ) and thereafter successively on each of a second plurality of transmit frequencies ( 51 ), in order to ensure that a first wireless communication apparatus that listens on one of the transmit frequencies will receive the inquiry message. The first plurality of transmit frequencies can also be ensured ( 25 - 28 ) to include a frequency on which a second wireless communication apparatus is listening for the inquiry message. With respect to reception of an inquiry message that is transmitted successively on each of first and thereafter second pluralities of transmit frequencies, after receipt ( 61 ) of the initial inquiry message and subsequent expiration of a corresponding backoff period ( 62 ), the inquiry message is first listened for on a first frequency of the first plurality of transmit frequencies for a predetermined time ( 63 ). If the inquiry message is not received on the first frequency during the first listening operation, the inquiry message is then listened for on a second frequency of the second plurality of transmit frequencies for a predetermined time ( 64 ).

Description:
[0001]    This application claims the priority under 35 USC 119(e)(1) of copending U.S. Provisional Application Nos. 60/270,077 and 60/270,064, both filed on Feb. 20, 2001. 
     
    
     
       FIELD OF THE INVENTION  
         [0002]    The invention relates generally to wireless communications and, more particularly, to frequency hopping wireless communications.  
         BACKGROUND OF THE INVENTION  
         [0003]    In the Bluetooth system, when a device wants to determine what other Bluetooth devices are within range, it can perform an inquiry. The conventional inquiry operation is described in “Specification of the Bluetooth System,” v1.0A, Jul. 26, 1999 (incorporated herein by reference). A device that performs the inquiry is called the master, and a device which periodically scans for inquiries with inquiry scans is called the slave. The slave wakes up every 2.56 s (or a shorter interval) to perform an inquiry scan for 18 time slots (there are 1600 time slots per second). The slave monitors a single frequency out of 32 possible frequencies. During the inquiry, the master transmits on two frequencies on one time slot and then listens on two frequencies during the next time slot. Thus, on an average, the master can transmit on 16 different frequencies during 16 time slots. The master continues to repeat the inquiry messages using the 16 frequencies for 2.56 s. There are a total of 32 possible frequencies used during inquiry, and the master splits the frequencies into two 16-hop parts, called trains. After transmitting on train A for 2.56 s, the master switches to train B. Currently, at least 3 train switches occur during inquiry, so the inquiry substate lasts at least 10.24 s.  
           [0004]    A slave performing an inquiry scan determines a frequency to monitor based on the general inquiry access code (GIAC) and some of the bits from its native clock. The X input value into the frequency selector of the slave is given by:  
           X S =CLKN 16-12    
           [0005]    Bit  12  of the clock changes every 1.28 s. The 5 bits from the clock (bits  16 ,  15 ,  14 ,  13 ,  12 ) map to the 32 frequencies that are to be monitored. If the slave wakes up every 2.56 s, then it will only end up monitoring 16 frequencies since bit  13  changes every 2.56 s.  
           [0006]    The 16 frequencies for train A or train B are determined by the GIAC and the native clock of the master. The X input value into the frequency selector of the master is given by:  
             X   M   =└CLKN   16-12   +κ   offset +( CLKN   4-2,0   −CLKN   16-12 ) mod 16┘ mod 32  (1)  
           [0007]    where κ offset =24 gives the train A and κ offset =8 gives the train B.  
           [0008]    One disadvantage of the conventional Bluetooth inquiry operation is that there are 32 frequencies used in the inquiry, but the master can only transmit on 16 frequencies during the 18 time slot window in which the slave scans. Because of the uncertainty of which of the 32 frequencies each slave will monitor upon wakeup, the master must spend 2.56 s on one train and 2.56 s on the second train (total of 5.12 s) before it can be sure that the slave hears its inquiry message (assuming an error-free environment). In environments where there are channel errors, the inquiry substate may need to last even longer.  
           [0009]    It is therefore desirable to reduce the amount of time required for assurance that a slave has heard the master&#39;s inquiry.  
           [0010]    The invention provides a technique for ensuring that the slave will be listening at a frequency contained in the frequency train that the master uses first during inquiry transmission. This can advantageously reduce the time needed for inquiry.  
           [0011]    In conventional Bluetooth inquiry operation, when the slave hears the master&#39;s inquiry message, it does not respond immediately. To avoid collisions in the case that several slaves wake up at the same time, a random backoff procedure is employed. The slave stores the current value of the frequency at which it heard the master&#39;s inquiry message, and generates a random number between 0 and 1023. The slave then waits this random number of time slots, which corresponds to 0 to 1023/1600 s. Upon waking up, the slave listens again at the stored frequency for the master&#39;s inquiry message. If the slave receives another inquiry message from the master, then the slave immediately returns an FHS packet, which is a special control packet containing the Bluetooth device address and the clock of the sender (the slave in this case). The slave then adds an offset of 1 to (i.e., increments) the phase of the inquiry hop sequence and performs an inquiry scan on this next frequency. If the slave is triggered (i.e., hears the inquiry message) again, then it repeats the above procedure with a new random number.  
           [0012]    During a 1.28 s probing window, a slave on average will return 4 FHS packets on different frequencies and at different times. However, if during the inquiry scan, the slave does not receive another inquiry message from the master within a time-out period, the slave returns to the standby or connection state.  
           [0013]    Due to the backoff period, another disadvantage of the conventional Bluetooth inquiry operation is that the master may have switched trains during the backoff period. The probability of this happening is 512 time slots (the average backoff time)/4096 time slots (the time between train switches)=0.125. This is the probability for each slave, so with many slaves there is a large probability that a train switch will occur before at least one of them can respond. This is the reason that the master needs to perform the inquiry for at least 10.24 s. FIG. 5 illustrates this situation. A slave may be listening on train B while the master starts transmitting on train A for 2.56 s. Therefore, the slave does not hear the master at  52  during train A. When the master switches to train B, the slave will wake up and hear the master at  53 , but if it wakes up too near the end of train B, then it may not be able to respond (which includes time to back off and then re-trigger) before the master switches back to train A, resulting in a time out at  54 . The slave is finally able to respond (i.e., back off, then re-trigger, then respond) when it is triggered at  55  after the master has returned to train B. This procedure is inefficient and disadvantageously extends the inquiry time.  
           [0014]    It is therefore desirable to avoid the inquiry time extension that can occur due to the combination of slave backoff time and train switches by the master.  
           [0015]    The invention permits a slave to listen on frequencies which alternate from one to the other of the master&#39;s trains in correspondence with each new slave inquiry scan window. This advantageously permits avoidance of the aforementioned inquiry time extension.  
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0016]    [0016]FIG. 1 diagrammatically illustrates pertinent portions of exemplary embodiments of a slave device according to the invention.  
         [0017]    [0017]FIG. 2 diagrammatically illustrates pertinent portions of exemplary embodiments of a master device according to the invention.  
         [0018]    [0018]FIG. 3 diagrammatically illustrates pertinent portions of exemplary embodiments of a device which can function as either a master device or a slave device according to the invention.  
         [0019]    [0019]FIG. 4 illustrates exemplary operations which can be performed by the embodiments of FIGS. 2 and 3.  
         [0020]    [0020]FIG. 5 is a timing diagram which illustrates a problem that can arise during conventional Bluetooth inquiry operations.  
         [0021]    [0021]FIG. 6 illustrates exemplary operations according to the present invention.  
         [0022]    [0022]FIG. 7 diagrammatically illustrates pertinent portions of exemplary embodiments of a slave device according to the invention.  
     
    
     DETAILED DESCRIPTION  
       [0023]    According to exemplary embodiments of the invention, instead of scanning over the 32 possible frequencies, the slave scans over 16 possible frequencies. By ensuring that the master starts its inquiry with those 16 frequencies, the inquiry process can be accelerated. According to exemplary embodiments of the invention, the slave only scans over frequencies with an X input of 0 to 15, so the X input value into the frequency selector of the slave is given, for example, by:  
         X S =CLKN 15-12   (2)  
         [0024]    Also according to exemplary embodiments of the invention, the master starts its inquiry using the frequencies given by X input values of 0 to 15. To ensure that this occurs, the value of κ offset  (see Equation (1) above) is defined, for example, as:  
         κ offset =32 −CLKN   16-12 * for train A  (3)  
         κ offset =16 −CLKN   16-12 * for train B  (4)  
         [0025]    where CLKN 16-12  *is the value of the clock at the start of the inquiry substate. Thus κ offset  for train A and κ offset  for train B are constants once the inquiry substate has begun.  
         [0026]    When the master enters the inquiry substate, it will begin with train A and will send inquiry messages on the frequencies corresponding to X=0, 1, 2, . . . , 15. Each slave will be monitoring one of these 16 frequencies and will be able to hear the master&#39;s inquiry within, in some embodiments, 2.56 seconds. This represents a reduction of about a factor of 2 in the required inquiry time, as compared to the prior art. There may also be other slaves that are legacy slaves that use the conventional inquiry scan frequencies. In some embodiments, the master can switch between trains in order to ensure that legacy slaves can hear its inquiry messages.  
         [0027]    Other embodiments can use mappings other than the example given above, so long as the slaves can use a subset of the 32 frequencies for inquiry scan, and the master can start its inquiry with that subset of frequencies to minimize the time needed for inquiry.  
         [0028]    [0028]FIG. 1 diagrammatically illustrates pertinent portions of exemplary embodiments of a slave device according to the invention. The slave device of FIG. 1 can be, for example, any Bluetooth device. As shown in FIG. 1, the native clock bits of Equation (2) are applied to the X input of a conventional Bluetooth frequency selector  14 . The frequency selector  14  is responsive to the X input and the GIAC for selecting a scan frequency and indicating the selection to a wireless communication interface  11 . The wireless interface  11  is cooperable with the frequency selector  14 , a conventional inquiry scan controller  13  and an antenna  12  for performing slave inquiry scan operations in conventional fashion. The antenna  12  receives the master&#39;s inquiry message via a wireless communication channel.  
         [0029]    [0029]FIG. 2 diagrammatically illustrates pertinent portions of exemplary embodiments of a master device according to the invention. The master device of FIG. 2 can be, for example, any Bluetooth device. In the device of FIG. 2, an inquiry controller  23  controls the master&#39;s inquiry operations. When the inquiry operations begin, the inquiry controller  23  produces a start signal which is used to clock a latch  25  to latch bits  12 - 16  of the native clock (CLKN)  15 . Thus, at the beginning of inquiry operations, the current state of bits  12 - 16  of the native clock is stored at the output of latch  25 .  
         [0030]    The inquiry controller  23  also produces a train select signal which controls a selector  26  to select a train A parameter or a train B parameter. In the examples of Equations (3) and (4) above, the train A parameter has a value of 32 and the train B parameter has a value of 16. The selector  26  permits accommodation of legacy slaves in the manner generally described above (i.e., switching between trains). Either the train A parameter or the train B parameter is combined at  27  (by an adder in this example) with the output of latch  25  to thereby realize either Equation (3) or Equation (4) above. The resulting κ offset  value is applied to an X M  generator  28  which implements Equation (1) above to produce X M . The value of X M  is input to a conventional frequency selector  14  which selects an inquiry frequency in response to X M  and the GIAC. The selected inquiry frequency is indicated to a wireless communication interface  21  which is cooperable in conventional fashion with the frequency selector  14 , the inquiry controller  23  and an antenna  12  for performing the desired master inquiry operations. The antenna  12  transmits the master&#39;s inquiry message to a slave via a wireless communication channel.  
         [0031]    [0031]FIG. 3, taken in conjunction with FIGS.  1  AND  2 , diagrammatically illustrates pertinent portions of exemplary embodiments of a device which can perform as either a master device or a slave device according to the invention. The device of FIG. 3 can be, for example, any Bluetooth device. As shown in FIG. 3, a configuration signal  30  determines whether the device is configured for operation as a master device or a slave device. If the device is configured as a master device, then the value of X input to the frequency selector  14  is the master value X M  produced by the generator  28  of FIG. 2. If the device is configured as a slave device, then the value of X input to the frequency selector  14  is provided as the slave value X S  selected from the native clock  15  in FIG. 1.  
         [0032]    The configuration signal  30  is also input to an inquiry/scan controller  35  which can operate either in generally the same fashion as the inquiry controller  23  of FIG. 2 or the inquiry scan controller  13  of FIG. 1, depending on whether the configuration signal  30  indicates master or slave operation, respectively. The frequency selector  14  is responsive to the input value of X and the GIAC for selecting an inquiry/scan frequency which indicates either the master&#39;s inquiry frequency or the slave&#39;s scan frequency (depending on whether master or slave operation is selected). A wireless communication interface  31  is also connected to receive the configuration signal  30 . If the configuration signal  30  indicates master operation, then the wireless communication interface  31  cooperates with the controller  35 , the frequency selector  14  and the antenna  12  in the same general fashion described above with respect to the wireless communication interface  21  of FIG. 2. If the configuration signal  30  indicates slave operation, then the wireless communication interface  31  cooperates with the controller  35 , the frequency selector  14  and the antenna  12  in the same general fashion described above with respect to the wireless communication interface  11  of FIG. 1.  
         [0033]    [0033]FIG. 4 illustrates exemplary operations which can be performed by the embodiments of FIGS. 2 and 3. An initial frequency train is selected at  41 . Upon entry into the inquiry substate at  42 , bits  12 - 16  of the native clock are latched at  43 . Thereafter, the value of κ offset  corresponding to the initial frequency train is determined at  44 , and the value of X M  is determined at  45 . At  46 , the inquiry frequency is selected and the inquiry is transmitted on the selected frequency. Thereafter, if the current frequency train is not completed at  47 , then the time for the next inquiry transmission is awaited at  48 . At the time for the next inquiry transmission, the operations described above at  45 - 48  are repeated until the current frequency train is completed at  47 .  
         [0034]    If the current frequency train is completed at  47 , and if the inquiry substate is still in effect at  49 , then the other train is switched to at  51 , after which the operations described above at  44 - 49  can be repeated for the new frequency train. When it is determined at  49  that the inquiry substate is no longer in effect, then the next inquiry substate is awaited at  42 .  
         [0035]    Exemplary embodiments of the invention permit the slave to avoid the aforementioned problem wherein the master changes trains before the slave can backoff and respond. In the prior art, when the slave wakes up after the random backoff time, the slave listens on the frequency corresponding to an X input value at the slave frequency selector given by:  
         X S =CLKN 16-12   (5)  
         [0036]    where CLKN 16-12  is the value of the clock when the slave was first triggered. According to exemplary embodiments of the invention, the slave listens on the frequency associated with Equation (5) for 18 time slots. If no trigger occurs during this 18 time slot inquiry scan window, then the slave switches to a new frequency corresponding to an X input value at the slave frequency selector given by:  
         X′ S =( CLKN   16-12 *+16) mod 32  (6)  
         [0037]    which gives the corresponding frequency of the alternate train. This will allow the slave to respond to the master even if the master switches trains during the backoff time. If the slave is not triggered with the new inquiry scan frequency (corresponding to X′ S ) after 18 time slots, then it returns to the original frequency (corresponding to X S ), and cycles between the two frequencies until the time-out period expires.  
         [0038]    If the slave is triggered, then it returns an FHS packet and increments the phase of the inquiry hopping sequence. When the slave enters the inquiry hop substate again, it performs the inquiry scan on the train where it was triggered.  
         [0039]    If the slave was triggered on X S =CLKN 16-12 , then it begins the inquiry scan on X S =(CLKN 16-12 *+1)mod32.  
         [0040]    If the slave was triggered on X′ S =(CLKN 16-12 *+16)mod32, then it begins the inquiry scan X′ S =(CLKN 16-12 *+17)mod32.  
         [0041]    After each FHS packet is sent, the inquiry scan frequencies are incremented.  
         [0042]    The exemplary alternating train switching operations described above are illustrated diagrammatically in FIG. 6. After the random backoff time at  62 , if the slave is not triggered during its  18  time slot inquiry scan window (see  63  and  64 ), the slave switches to a frequency of the other train, and continues alternating between trains until either the slave is triggered or a timeout occurs. After the slave is triggered and an FHS packet is sent at  65  or  66 , the slave increments the phase of the inquiry hopping sequence at  67  or  68 . If the slave triggered on the train corresponding to X′ S , then the values of X S  and X′ S  are swapped at  69  to ensure that the next inquiry scan (after another random backoff time) is performed on the train where the slave was last triggered. The exemplary operation shown in FIG. 6 can reduce the amount of time needed for inquiry by almost a factor of 2. The slave will be triggered, in some embodiments, in the first 5.12 seconds on either train A or train B. Allowing, for example, 1.28 seconds for the slave to respond, the inquiry time can be reduced from 10.24 seconds to 6.40 seconds.  
         [0043]    [0043]FIG. 7 diagrammatically illustrates pertinent portions of exemplary embodiments of a slave device according to the invention. The device of FIG. 7, which can be, for example, any Bluetooth device, is capable of performing the exemplary operations illustrated in FIG. 6. Before the slave is initially triggered (see  61  in FIG. 6), the inquiry scan controller  75  controls a selector  74  such that the frequency selector  14  receives an X input value defined by bits  12 - 16  of the native clock, as is conventional. Thus, prior to initial triggering, the inquiry scan controller  75 , frequency selector  14 , wireless communication interface  11  and antenna  12  cooperate in conventional fashion to perform the conventional slave inquiry scan operation.  
         [0044]    After initial triggering of the slave device (see  61  in FIG. 6), the inquiry scan controller  75  determines and implements the random backoff time (see  62  in FIG. 6). After expiration of this first random backoff time, the inquiry scan controller  75  outputs a first trigger signal which drives the clock input of a latch  79 . In response to the first trigger signal, the latch  79  latches bits  12 - 16  of the native clock  15 , thereby storing those bits. These latched native clock bits are loaded into an X S  register  76  under control of a load signal from the controller  75 . The output of the latch  79  is also applied to an X′ S  generator  78  which implements Equation ( 6 ) above to produce X′ S , which is in turn loaded into an x′ S  register  77  under control of the load signal from the controller  75 . The controller  75  then uses control signal  80  to select at  74  one of the registers  76  and  77  to provide the next X value to the input of the frequency selector  14 .  
         [0045]    The frequency selector  14  is responsive to the X input value and the GIAC to select the scan frequency to be used for the next  18  time slots and indicate this frequency to the wireless interface  11 . If the slave is not triggered during those  18  time slots, then the controller  75  controls the selector  74  such that x′ S , as stored in register  77 , is applied as the next X input value to the frequency selector  14  for the next 18 time slots. Until the slave triggers or a timeout (implemented and detected, for example, by the controller  75 ) occurs, the controller  75  continues to control selector  74  to switch between applying X S  and x′ S  (for 18 time slots each) as the X input of the frequency selector  14 .  
         [0046]    Once the slave triggers, it sends an FHS packet in conventional fashion (see  65  or  66  in FIG. 6), and the controller  75  then uses control signal  81  to increment the contents of the registers  76  and  77 . After the next random backoff time has expired, the controller  75  controls selector  74  such that the contents of register  76  are applied as the X input to frequency selector  14  if X S  caused the last triggering of the slave, or such that the contents of register  77  are applied as the X input to frequency selector  14  if x′ S  caused the last triggering of the slave.  
         [0047]    It will be evident to workers in the art that the embodiments described above with respect to FIGS.  1 - 7  can be readily implemented by suitable modifications in software, hardware or a combination of software and hardware in conventional Bluetooth devices.  
         [0048]    Although exemplary embodiments of the invention are described above in detail, this does not limit the scope of the invention, which can be practiced in a variety of embodiments.