# Patent

## Title
Efficient channel search with sequential probability ratio testing

## Abstract

Methods and systems for cognitive radio channel searching are shown that include determining an upper threshold and a lower threshold that will find a free channel in a minimum average searching time based on a channel occupancy probability π0 and the number of channels K, constrained by a target acceptable misdetection probability and a target acceptable false alarm probability. The K channels are searched with a signaling device using the determined upper threshold and lower threshold to find a free channel.

## Background
RELATED APPLICATION INFORMATION
This application claims priority to provisional application Ser. No. 61/313,389 filed on Mar. 12, 2010, incorporated herein by reference. This application further claims priority to provisional application Ser. No. 61/313,396 filed on Mar. 12, 2010, incorporated herein by reference. This application is further related to application Ser. No. 13/029,726, filed concurrently herewith, incorporated herein by reference.


BACKGROUND
1. Technical Field
The present invention relates to multichannel systems and, in particular, to systems and methods for efficient channel searching in cognitive radio.
2. Description of the Related Art
In a cognitive radio (CR) network, secondary (unlicensed) users (SUs) are allowed to opportunistically access a licensed spectrum that is not currently being occupied by primary (licensed) users (PUs). Spectrum sensing in a CR network allows a network to protect primary transmissions from interferences due to secondary usage of the spectrum. Extant techniques for spectrum sensing rely on unrealistic assumptions, expensive equipment, and highly complex methods.
SUMMARY
A method for cognitive radio channel searching is shown that includes determining an upper threshold and a lower threshold that will find a free channel in a minimum average searching time based on a channel occupancy probability π0 and the number of channels K, constrained by a target acceptable misdetection probability and a target acceptable false alarm probability. The method also includes searching the K channels with a signaling device using the determined upper threshold and lower threshold to find a free channel.
A method for cognitive radio channel searching is shown that includes determining an upper threshold and a lower threshold that will find a free channel in a minimum average searching time based on a channel occupancy probability π0 and the number of channels K, constrained by a target acceptable misdetection probability and a target acceptable false alarm probability. The determination further includes minimizing an average searching time according to an expected false alarm probability and an expected misdetection probability. The method also searches the K channels with a signaling device by sampling a channel, calculating a log-likelihood ratio (LLR) for the samples for each channel k, and comparing the LLR to the upper and lower thresholds to determine whether the channel is free or busy.
A cognitive radio device is shown that includes a search parameter determination module configured to determine an upper threshold and a lower threshold that will find a free channel in a minimum average searching time based on a channel occupancy probability π0 and the number of channels K, constrained by a target acceptable misdetection probability and a target acceptable false alarm probability. The device further includes a search module configured to search the multiple channels with a signaling device using the determined upper threshold and lower threshold to find a free channel.
These and other features and advantages will become apparent from the following detailed description of illustrative embodiments thereof, which is to be read in connection with the accompanying drawings.



BRIEF DESCRIPTION OF DRAWINGS
The disclosure will provide details in the following description of preferred embodiments with reference to the following figures wherein:
FIG. 1 is a block diagram of a secondary user searching for a free channel.
FIG. 2 is a graph which illustrates a sequential probability ratio test (SPRT).
FIG. 3 is a block/flow diagram of sequential SPRT for multiple channels.
FIG. 4 is a graph which illustrates an energy detection (ED) test.
FIG. 5 is a block/flow diagram of a sequential ED test for multiple channels according to the present principles.
FIG. 6 is a block/flow diagram of an S-SPRT methodology including search design.
FIG. 7 is a block/flow diagram of an S-ED methodology including search design.
FIG. 8 is a diagram of an exemplary cognitive radio transceiver.



DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS
The present principles quickly and accurately locate an unoccupied channel (or determine that there is no unoccupied channel) from a set of multiple candidate channels, for a secondary user (SU) with a single detector. The SU can only observe one channel at a time and needs to switch from one channel to another when necessary. A design criterion is provided that minimizes the average searching time subject to the constraints on the error probabilities. Notably, the design criterion described below does not depend on a cost structure. Using this design criterion, two efficient channel search methods with simple structures are provided. The two methods strike an advantageous tradeoff among detection delay at each channel, switching delays, and the error probabilities in a multichannel setup.
Embodiments described herein may be entirely hardware, entirely software or including both hardware and software elements. In a preferred embodiment, the present invention is implemented in software, which includes but is not limited to firmware, resident software, microcode, etc.
Embodiments may include a computer program product accessible from a computer-usable or computer-readable medium providing program code for use by or in connection with a computer or any instruction execution system. A computer-usable or computer readable medium may include any apparatus that stores, communicates, propagates, or transports the program for use by or in connection with the instruction execution system, apparatus, or device. The medium can be magnetic, optical, electronic, electromagnetic, infrared, or semiconductor system (or apparatus or device) or a propagation medium. The medium may include a computer-readable storage medium such as a semiconductor or solid state memory, magnetic tape, a removable computer diskette, a random access memory (RAM), a read-only memory (ROM), a rigid magnetic disk and an optical disk, etc.
A data processing system suitable for storing and/or executing program code may include at least one processor coupled directly or indirectly to memory elements through a system bus. The memory elements can include local memory employed during actual execution of the program code, bulk storage, and cache memories which provide temporary storage of at least some program code to reduce the number of times code is retrieved from bulk storage during execution. Input/output or I/O devices (including but not limited to keyboards, displays, pointing devices, etc.) may be coupled to the system either directly or through intervening I/O controllers.
Network adapters may also be coupled to the system to enable the data processing system to become coupled to other data processing systems or remote printers or storage devices through intervening private or public networks. Modems, cable modem and Ethernet cards are just a few of the currently available types of network adapters.
Referring now to the drawings in which like numerals represent the same or similar elements and initially to FIG. 1, a narrow-band communication system is shown in which an SU 104 is allowed to opportunistically access a licensed spectrum consisting of K non-overlapping channels 102 with equal bandwidth. It is assumed that the SU 104 has a single detector at its transmitter operating in half-duplex mode. Each channel has two possible states: “free” (e.g., 102-3) or “busy” (e.g., 102-1). A channel is said to be busy if the channel is currently being used by a primary user (PU) or SU. It is assumed herein that only one SU is present, but the present principles may be extended to detect other SUs as long as the average signal power of the SU is known. It may be further assumed that the states of the channels 102 are independent and identically distributed, such that the state of each channel is independent from the state of the others and each channel has the same prior probability π0 of being free. The prior probability π0, may be found by observing PU activity over time, and then used in subsequent channel searches. The SU needs to quickly find a free channel, or determine that there is no free channel, from the K candidate channels with a small chance of error.
For the kth channel 102, where k ε[1,K], let {y1(k),y2(k), . . . } be a set of samples of channel k. For the free and busy states H (denoted as 0 and 1 respectively), the observed signals can be expressed as:

H0(k)(state 0):yn(k)=wn(k), n=1,2,  (1)

H1(k)(state 1):yn(k)=h(k)sn(k)+wn(k), n=1,2,  (2)

where wn(k) is modeled as an additive white Gaussian noise with variance σw2 independent of the channel index (i.e., wn(k) ̃CN(0,σw2)), h(k) is the kth channel coefficient between the PU using the channel and the SU 104, and sn(k) denotes the primary signals transmitted over channel k at time instant n. It may further be assumed that: 1. the state of a channel 102 remains unchanged during the detection process, 2. the primary signal for 2 samples are independent and identically distributed with E(|sn(k)|2)=σs2, a parameter independent of channel index, and 3. the channel gain h(k) is perfectly known at the SU 104. The signal-to-noise ratio (SNR) may be defined as ξ:=|h(k)|2σs2/σw2. The SU 104 performs a detection scheme to test H0(k) against H1(k) until a free channel is located or all the channels 102 are detected as busy.

Two sensing schemes in the single-channel case are relevant to the multi-channel case. The first is the sequential probability ratio test (SPRT) and the second is energy detection (ED). In SPRT, an accumulative log-likelihood ratio (LLR) is compared with two predetermined thresholds to test the null hypothesis H0 against the alternative hypothesis H1. To be more precise, the LLR of N received samples may be expressed as




  
    
      
        
          
            Λ
            N
          
          =
          
            
              ∑
              
                n
                =
                1
              
              N
            
            ⁢
            
              
            
            ⁢
            
              log
              ⁢
              
                
                  
                    p
                    1
                  
                  ⁡
                  
                    (
                    
                      y
                      n
                    
                    )
                  
                
                
                  
                    p
                    0
                  
                  ⁡
                  
                    (
                    
                      y
                      n
                    
                    )
                  
                
              
            
          
        
        ,
      
    
    
      
        (
        3
        )
      
    
  




where yn denotes the received signal at time n, and p0(x) and p1(x) are the probability density functions under H0 and H1 respectively. At the Nth time instant, the SPRT procedure is given as follows:

Reject H0:ΛN≧as  (4)

Accept H0:ΛN≦bs  (5)

Continue Sensing:as<ΛN<bs  (6)

where as and bs are two predetermined thresholds. For given false-alarm and misdetection probabilities α and β, as and bs can be determined as follows:





  
    
      
        
          a
          s
        
        =
        
          
            log
            ⁢
            
              β
              
                1
                -
                α
              
            
            ⁢
            
              
            
            ⁢
            and
            ⁢
            
              
            
            ⁢
            
              b
              s
            
          
          =
          
            log
            ⁢
            
              
                1
                -
                β
              
              α
            
          
        
      
    
    
      
        (
        7
        )
      
    
  




Note that assumption as<bs implies α+β<1.

Referring now to FIG. 2, a graph is shown comparing the test statistic to the thresholds as 204 and bs 202 in the single channel case for an exemplary SPRT embodiment. The vertical axis represents the updated test statistic for each sample yn(k) 206, and the horizontal axis represents a number of samples. As the samples accumulate, the test statistic is updated and progressively compared to the given thresholds. If the test statistic exceeds as 204, the hypothesis H0 (that the channel is free) is rejected. If the test statistic falls below bs 202, the hypothesis H0 is accepted. If a maximum N samples are collected, a final decision is made by comparing the test statistic to a third threshold.
Referring now to FIG. 3, a block/flow diagram is shown using an exemplary sequential SPRT embodiment. A channel is selected at block 302. The signal on the selected channel is sampled at block 303, and an LLR is computed for that received sample at block 304. Block 306 then updates a cumulative LLR ratio for the current channel using the computed LLR. Block 308 determines whether the cumulative LLR has exceeded one of the thresholds. If not, processing returns to block 303 and the signal is sampled further. If so, block 309 determines whether the LLR exceeded the lower threshold. If the lower threshold was exceeded, block 310 determines that the selected channel is free. Otherwise, block 311 determines that the selected channel is busy. Block 312 determines whether the selected channel was the last channel from a set of K channels. If so, block 314 determines that all channels are busy. If not, a new channel is selected at block 302 and processing resumes.
Let Zn, denote log(p1(yn)/p0(yn)). Define μ0=E(Zn|H0) and μ1=E(Zn|H1). Let ts be the number of the samples required to reach a decision. Clearly, ts is a random variable. Under H0, the average sample number (ASN) can be approximated as E(ts|H0)=((1−a)as+abs)/μ0, whereas under H1, the ASN can be approximated as E(ts|H1)=(βas+(1−β)bs)/μ1. The ASN can be approximated as




  
    
      
        
          
            
              
                E
                ⁡
                
                  (
                  
                    t
                    s
                  
                  )
                
              
              =
              
              ⁢
              
                
                  
                    E
                    ⁡
                    
                      (
                      
                        
                          t
                          s
                        
                        ❘
                        
                          H
                          0
                        
                      
                      )
                    
                  
                  ⁢
                  
                    π
                    0
                  
                
                +
                
                  
                    E
                    ⁡
                    
                      (
                      
                        
                          t
                          s
                        
                        ❘
                        
                          H
                          1
                        
                      
                      )
                    
                  
                  ⁢
                  
                    (
                    
                      1
                      -
                      
                        π
                        0
                      
                    
                    )
                  
                
              
            
          
        
        
          
            
              ≈
              
              ⁢
              
                
                  
                    
                      π
                      0
                    
                    
                      μ
                      0
                    
                  
                  ⁡
                  
                    [
                    
                      
                        
                          (
                          
                            1
                            -
                            α
                          
                          )
                        
                        ⁢
                        log
                        ⁢
                        
                          β
                          
                            1
                            -
                            α
                          
                        
                      
                      +
                      
                        α
                        ⁢
                        
                          
                        
                        ⁢
                        log
                        ⁢
                        
                          
                            1
                            -
                            β
                          
                          α
                        
                      
                    
                    ]
                  
                
                +
                
                  
                    1
                    -
                    
                      π
                      0
                    
                  
                  
                    μ
                    0
                  
                
              
            
          
        
        
          
            
              
              ⁢
              
                [
                
                  
                    βlog
                    ⁢
                    
                      β
                      
                        1
                        -
                        α
                      
                    
                  
                  +
                  
                    
                      (
                      
                        1
                        -
                        β
                      
                      )
                    
                    ⁢
                    log
                    ⁢
                    
                      
                        1
                        -
                        β
                      
                      α
                    
                  
                
                ]
              
            
          
        
        
          
            
              =
              
              ⁢
              
                
                  
                    [
                    
                      
                        
                          
                            π
                            0
                          
                          ⁡
                          
                            (
                            
                              1
                              -
                              α
                            
                            )
                          
                        
                        
                          μ
                          0
                        
                      
                      +
                      
                        
                          
                            (
                            
                              1
                              -
                              
                                π
                                0
                              
                            
                            )
                          
                          ⁢
                          β
                        
                        
                          μ
                          1
                        
                      
                    
                    ]
                  
                  ⁢
                  log
                  ⁢
                  
                    β
                    
                      1
                      -
                      α
                    
                  
                
                +
              
            
          
        
        
          
            
              
              ⁢
              
                [
                
                  
                    
                      
                        π
                        0
                      
                      ⁢
                      α
                    
                    
                      μ
                      0
                    
                  
                  +
                  
                    
                      
                        (
                        
                          1
                          -
                          
                            π
                            0
                          
                        
                        )
                      
                      ⁢
                      
                        (
                        
                          1
                          -
                          β
                        
                        )
                      
                    
                    
                      μ
                      1
                    
                  
                
                ]
              
            
          
        
        
          
            
              
              ⁢
              
                log
                ⁢
                
                  
                    1
                    -
                    β
                  
                  α
                
              
            
          
        
      
    
    
      
        (
        8
        )
      
    
  




The approximation of E(ts) in (8) becomes fairly accurate in the following two cases. The first case is when α and β are both very small while the second case is when p1(x) is sufficiently close to p0(x). In a CR network, the SU is required to detect the presence/absence of a PU with small error probabilities at a very low SNR. When the SNR is sufficiently low, p1(x) becomes fairly close to p0(x), and thus the approximation in (8) is highly accurate.
In ED, the energy of the received signal samples is first computed and then is compared to a predetermined threshold. Let te be a fixed sample size and y be a te×1 vector defined as y=(y1,y2, . . . , yt). The test procedure of the energy detection is given as




  
    T
    ⁡
    
      (
      y
      )
    
  
  =
  
    
      
        ∑
        
          i
          =
          1
        
        
          t
          r
        
      
      ⁢
      
        
      
      ⁢
      
        
          
          
            y
            i
          
          
        
        2
      
    
    ⁢
    
      =
      
        ≤
        
          H
          0
        
      
      
        ≥
        
          H
          1
        
      
    
    ⁢
    λ
  




where T(y) denotes the test statistic, and λ denotes the threshold for energy detection.

Unlike in the SPRT, the sample size te in energy detection is a fixed parameter, which is determined by the target false-alarm probability α, the misdetection probability β, and a SNR value. Let temin be the minimum sample number required to achieve the target false-alarm probability α and misdetection probability β when the SNR is ξ. This produces:




  
    
      
        
          t
          e
          min
        
        =
        
          ⌈
          
            (
            
              
                
                  ξ
                  
                    -
                    2
                  
                
                ⁡
                
                  [
                  
                    
                      
                        Q
                        
                          -
                          1
                        
                      
                      ⁡
                      
                        (
                        α
                        )
                      
                    
                    -
                    
                      
                        
                          Q
                          
                            -
                            1
                          
                        
                        ⁡
                        
                          (
                          
                            1
                            -
                            β
                          
                          )
                        
                      
                      ⁢
                      
                        
                          
                            2
                            ⁢
                            
                              
                            
                            ⁢
                            ξ
                          
                          +
                          1
                        
                      
                    
                  
                  ]
                
              
              2
            
            )
          
          ⌉
        
      
    
    
      
        (
        9
        )
      
    
  




where ┌x┐ denotes the smallest integer not less than x, and Q(•) is the complementary cumulative distribution function of the standard normal random variable, i.e.,





  
    
      Q
      ⁡
      
        (
        x
        )
      
    
    :=
    
      
        
          (
          
            2
            ⁢
            π
          
          )
        
        
          
            -
            1
          
          /
          2
        
      
      ⁢
      
        
          ∫
          x
          ∞
        
        ⁢
        
          
            e
            
              
                -
                u
              
              ⁢
              
                2
                2
              
            
          
          ⁢
          
            d
            u
          
        
      
    
  
  ,




while Q−1(•) denotes its inverse function. Note that like the SPRT, (9) holds true only when α+β<1.

Referring now to FIG. 4, a graph is shown comparing the single-channel energy detection test statistic to the threshold λ 402. The vertical axis represents the test statistic for a set of samples 404, and the horizontal axis represents a number of samples. After te samples 406 have been collected, the test statistic T(y) is compared. If the test statistic exceeds the threshold λ 402 the hypothesis H0 (that the channel is free) is rejected. If the test statistic is below λ 402, the hypothesis H0 is accepted.
Referring now to FIG. 5, a block/flow diagram is shown for finding a free channel using an exemplary sequential ED embodiment. At block 502, the SU 104 selects a new channel which has not been tested yet. Changing the central frequency of the observing channel causes a switching delay. Block 503 then collects N samples {y1(k),y2(k), . . . } on the channel. Block 504 squares the magnitude of the received single samples yn(k), allowing block 506 to compute a test statistic




  
    Λ
    N
    
      (
      k
      )
    
  
  =
  
    
      ∑
      
        n
        =
        1
      
      N
    
    ⁢
    
      
    
    ⁢
    
      
        
          
          
            y
            n
            
              (
              k
              )
            
          
          
        
        2
      
      .
    
  




Block 508 determines whether the test statistic is greater than or equal to a threshold γ. If so, the current channel is declared free at block 509 and the SU uses said channel. If not, the current channel is declared busy at block 510. Block 512 determines if there are untested channels remaining. If not, block 514 declares that all channels are busy and processing ends. If so, processing returns to block 502 and a new channel is selected.

When designing a cognitive radio system, two error probabilities play a role: the false alarm probability PFAmc and the misdetection probability PMDmc. Because the states of the K channels are independent and have the same a priori probabilities, it is assumed that each channel has the same target false-alarm probability α and the target same misdetection probability β as defined in the single channel case. From a practical viewpoint, it is assumed that α>0, β>0, and α+β>0. The misdetection probability and the false alarm probability are used to form search parameters in S-ED and S-SPRT, as discussed below in FIGS. 6 and 7.
The false-alarm probability PFAmc is defined as the probability of determining that all channels are busy while in fact there exists at least one free channel. Let Ei denote the event that there exist exactly i free channels for i=1, . . . , K and let D1 denote the event that the SU determines that all channels are busy. The false-alarm probability PFAmc is then P(D1|∪i=1KEi). Mathematically, PFAmc can be computed as follows:




  
    
      
        
          
            
              
                P
                FA
                mc
              
              =
              
                P
                ⁡
                
                  (
                  
                    
                      D
                      1
                    
                    ❘
                    
                      
                        ⋃
                        
                          i
                          =
                          1
                        
                        K
                      
                      ⁢
                      
                        E
                        i
                      
                    
                  
                  )
                
              
            
          
        
        
          
            
              =
              
                
                  P
                  ⁡
                  
                    (
                    
                      
                        D
                        1
                      
                      ⋂
                      
                        
                          ⋃
                          
                            i
                            =
                            1
                          
                          K
                        
                        ⁢
                        
                          E
                          i
                        
                      
                    
                    )
                  
                
                
                  P
                  ⁡
                  
                    (
                    
                      
                        ⋃
                        
                          i
                          =
                          1
                        
                        K
                      
                      ⁢
                      
                        E
                        i
                      
                    
                    )
                  
                
              
            
          
        
        
          
            
              =
              
                
                  P
                  ⁡
                  
                    (
                    
                      
                        ⋃
                        
                          i
                          =
                          1
                        
                        K
                      
                      ⁢
                      
                        (
                        
                          
                            D
                            1
                          
                          ⋂
                          
                            E
                            i
                          
                        
                        )
                      
                    
                    )
                  
                
                
                  P
                  ⁡
                  
                    (
                    
                      
                        ⋃
                        
                          i
                          =
                          1
                        
                        K
                      
                      ⁢
                      
                        E
                        i
                      
                    
                    )
                  
                
              
            
          
        
        
          
            
              =
              
                
                  
                    
                      ∑
                      
                        i
                        =
                        1
                      
                      K
                    
                    ⁢
                    
                      P
                      ⁡
                      
                        (
                        
                          
                            D
                            1
                          
                          ⋂
                          
                            E
                            i
                          
                        
                        )
                      
                    
                  
                  
                    P
                    ⁡
                    
                      (
                      
                        
                          ⋃
                          
                            i
                            =
                            1
                          
                          K
                        
                        ⁢
                        
                          E
                          i
                        
                      
                      )
                    
                  
                
                .
              
            
          
        
      
    
    
      
        (
        11
        )
      
    
  




Using the fact that the events Ei are disjoint, P(∪i=0KEi) is equal to 1, and the states of the channels are independent, one arrives at P(∪i=0KEi)=1−(1−π0)K. P(D1∩Ei) is now computed. For any particular event from Ei, for example Ei0, P(D1∩Ei0) can be rewritten as

P(D1∩Ei0)=P(D1|Ei0)P(Ei0)=[απ0]i[(1−β)(1−π0)]K-i  (12)

Ei includes





  
    (
    
      
        
          K
        
      
      
        
          i
        
      
    
    )
  
   




disjoint such events. Hence,





  
    
      
        
          P
          ⁡
          
            (
            
              
                D
                1
              
              ⋂
              
                E
                i
              
            
            )
          
        
        =
        
          
            (
            
              
                
                  K
                
              
              
                
                  i
                
              
            
            )
          
          ⁢
          
             
            
              
                
                  
                    
                      [
                      
                        α
                        ⁢
                        
                          
                        
                        ⁢
                        
                          π
                          0
                        
                      
                      ]
                    
                    i
                  
                  ⁡
                  
                    [
                    
                      
                        (
                        
                          1
                          -
                          β
                        
                        )
                      
                      ⁢
                      
                        (
                        
                          1
                          -
                          
                            π
                            0
                          
                        
                        )
                      
                    
                    ]
                  
                
                
                  K
                  -
                  i
                
              
              .
            
          
        
      
    
    
      
        (
        13
        )
      
    
  




From (11), (12), and (13),





  
    
      
        
          
            
              
                P
                FA
                mc
              
              =
              
                
                  
                    ∑
                    
                      i
                      =
                      1
                    
                    K
                  
                  ⁢
                  
                    
                      (
                      
                        
                          
                            K
                          
                        
                        
                          
                            i
                          
                        
                      
                      )
                    
                    ⁢
                    
                       
                      
                        
                          
                            
                              [
                              
                                α
                                ⁢
                                
                                  
                                
                                ⁢
                                
                                  π
                                  0
                                
                              
                              ]
                            
                            i
                          
                          ⁡
                          
                            [
                            
                              
                                (
                                
                                  1
                                  -
                                  β
                                
                                )
                              
                              ⁢
                              
                                (
                                
                                  1
                                  -
                                  
                                    π
                                    0
                                  
                                
                                )
                              
                            
                            ]
                          
                        
                        
                          K
                          -
                          i
                        
                      
                    
                  
                
                
                  1
                  -
                  
                    
                      (
                      
                        1
                        -
                        
                          π
                          0
                        
                      
                      )
                    
                    K
                  
                
              
            
          
        
        
          
            
              =
              
                
                  
                    
                      [
                      
                        
                          α
                          ⁢
                          
                            
                          
                          ⁢
                          
                            π
                            0
                          
                        
                        +
                        
                          
                            (
                            
                              1
                              -
                              β
                            
                            )
                          
                          ⁢
                          
                            (
                            
                              1
                              -
                              
                                π
                                0
                              
                            
                            )
                          
                        
                      
                      ]
                    
                    K
                  
                  -
                  
                    
                      [
                      
                        
                          (
                          
                            1
                            -
                            β
                          
                          )
                        
                        ⁢
                        
                          (
                          
                            1
                            -
                            
                              π
                              0
                            
                          
                          )
                        
                      
                      ]
                    
                    K
                  
                
                
                  1
                  -
                  
                    
                      (
                      
                        1
                        -
                        
                          π
                          0
                        
                      
                      )
                    
                    K
                  
                
              
            
          
        
      
    
    
      
        (
        14
        )
      
    
  




Unlike the false-alarm probability in the single channel case, PFAmc depends on π0 in general except that PFAmc reduces to α when K=1. Two monotonic properties of PFAmc are described herein with respect to π0 and β, respectively. First, the false alarm probability PFAmc is a monotonically decreasing function on π0 for given α and β. The least upper bound on PFAmc is given by α(1−β)K-1 for any 0<π0<1, i.e., sup0<π0<1P(D1|∪i=1KEi)=α(1−β)K-1 for 0<π0<1. Second, for any given 0<α<1 and 0<π0<1, the false alarm probability PFAmc is a monotonically decreasing function of β.
The misdetection probability PMDmc is defined as the probability of the event that a channel is determined to be free while it is in fact busy. Again, note that the misdetection probability is used to form search parameters for S-ED and S-SPRT, as shown below in FIGS. 6 and 7. Let τ denote the index of the channel at which the search ends. Let D(τ) denote the event that the SU determines that channels 1 to τ−1 are busy and channel τ is free, where τε{1, . . . , K}. With a slight abuse of notation, H1(τ) is used to denote the event that channel τ is indeed busy. Following the definition of PMDmc and the fact that D(τ)∩H1(τ) for τ=1, . . . , K are disjoint events, the overall misdetection probability of a multichannel system is written as Στ=1KP(D(τ)∩H1(τ)).
For a fixed τ:




  
    
      
        
          P
          ⁡
          
            (
            
              
                D
                
                  (
                  τ
                  )
                
              
              ⋂
              
                H
                1
                
                  (
                  τ
                  )
                
              
            
            )
          
        
        ⁢
        
          =
          
            (
            a
            )
          
        
        ⁢
        
        ⁢
        
          
            P
            ⁡
            
              (
              
                
                  D
                  0
                  
                    (
                    τ
                    )
                  
                
                ⋂
                
                  H
                  1
                  
                    (
                    τ
                    )
                  
                
              
              )
            
          
          ⁢
          
            
              ∏
              
                k
                =
                1
              
              
                τ
                -
                1
              
            
            ⁢
            
              
            
            ⁢
            
              P
              ⁡
              
                (
                
                  D
                  1
                  
                    (
                    k
                    )
                  
                
                )
              
            
          
        
      
    
  
  
    
      
        =
        
        ⁢
        
          
            
              P
              ⁡
              
                (
                
                  
                    D
                    0
                    
                      (
                      τ
                      )
                    
                  
                  ❘
                  
                    H
                    1
                    
                      (
                      τ
                      )
                    
                  
                
                )
              
            
            ⁢
            
              P
              ⁡
              
                (
                
                  H
                  1
                  
                    (
                    τ
                    )
                  
                
                )
              
            
            ⁢
            
              
                ∏
                
                  k
                  =
                  1
                
                
                  τ
                  -
                  1
                
              
              ⁢
              
                
              
              ⁢
              
                
                  P
                  ⁡
                  
                    (
                    
                      
                        D
                        1
                        
                          (
                          k
                          )
                        
                      
                      ❘
                      
                        H
                        1
                        
                          (
                          k
                          )
                        
                      
                    
                    )
                  
                
                ⁢
                
                  P
                  ⁡
                  
                    (
                    
                      H
                      1
                      
                        (
                        k
                        )
                      
                    
                    )
                  
                
              
            
          
          +
        
      
    
  
  
    
      
        
        ⁢
        
          
            P
            ⁡
            
              (
              
                
                  D
                  1
                  
                    (
                    k
                    )
                  
                
                ❘
                
                  H
                  0
                  
                    (
                    k
                    )
                  
                
              
              )
            
          
          ⁢
          
            P
            ⁡
            
              (
              
                H
                0
                
                  (
                  k
                  )
                
              
              )
            
          
        
      
    
  
  
    
      
        =
        
        ⁢
        
          
            
              β
              ⁡
              
                (
                
                  1
                  -
                  
                    π
                    0
                  
                
                )
              
            
            ⁡
            
              [
              
                
                  
                    (
                    
                      1
                      -
                      β
                    
                    )
                  
                  ⁢
                  
                    (
                    
                      1
                      -
                      
                        π
                        0
                      
                    
                    )
                  
                
                +
                
                  α
                  ⁢
                  
                    
                  
                  ⁢
                  
                    π
                    0
                  
                
              
              ]
            
          
          
            τ
            -
            1
          
        
      
    
  
  
    
      
        =
        
        ⁢
        
          
            
              β
              ⁡
              
                (
                
                  1
                  -
                  
                    π
                    0
                  
                
                )
              
            
            ⁡
            
              [
              
                
                  
                    (
                    
                      α
                      +
                      β
                      -
                      1
                    
                    )
                  
                  ⁢
                  
                    π
                    0
                  
                
                +
                
                  (
                  
                    1
                    -
                    β
                  
                  )
                
              
              ]
            
          
          
            τ
            -
            1
          
        
      
    
  




where D1(k) denotes the event that the SU claims channel k as a busy channel for k=1, . . . , τ−1, D1(τ) denotes the event that the SU claims channel τ as a free channel, (a) follows directly from the independence of received signal samples from each channel. Denoting (α+β−1)π0+(1−β) by φ, this produces P(D(τ)∩H1(τ))=β(1−π0)φτ-1. PMDmc can be written as





  
    
      
        
          
            
              
                P
                MD
                mc
              
              =
              
                
                  ∑
                  
                    τ
                    =
                    1
                  
                  K
                
                ⁢
                
                  P
                  ⁡
                  
                    (
                    
                      
                        D
                        
                          (
                          τ
                          )
                        
                      
                      ⋂
                      
                        H
                        1
                        
                          (
                          τ
                          )
                        
                      
                    
                    )
                  
                
              
            
          
        
        
          
            
              =
              
                
                  β
                  ⁡
                  
                    (
                    
                      1
                      -
                      
                        π
                        0
                      
                    
                    )
                  
                
                ⁢
                
                  
                    ∑
                    
                      τ
                      =
                      1
                    
                    K
                  
                  ⁢
                  
                    φ
                    
                      τ
                      -
                      1
                    
                  
                
              
            
          
        
        
          
            
              =
              
                
                  β
                  ⁡
                  
                    (
                    
                      1
                      -
                      
                        π
                        0
                      
                    
                    )
                  
                
                ⁢
                
                  
                    1
                    -
                    
                      φ
                      K
                    
                  
                  
                    1
                    -
                    φ
                  
                
              
            
          
        
      
    
    
      
        (
        15
        )
      
    
  




Unlike the misdetection probability in the single channel case, PMDmc depends on a priori probability π0. It should be noted that when K=1, PMDmc does not reduce to the misdetection probability β in the single channel case. This is because the misdetection probability β in the single channel case is a conditional probability while PMDmc is defined as a joint probability.

Two monotonic properties of the misdetection probability PMDmc are described herein. First, the misdetection probability PMDmc is a monotonically decreasing function of π0. Furthermore, the least upper bound on PMDmc for 0<π0<1 is given by 1−(1−β)K. Second, for any given 0<α<1 and 0<π0<1, the misdetection probability PMDmc is a monotonically increasing function of β.
Another relevant quantity to S-ED and S-SPRT searches, as discussed below in FIGS. 6 and 7, is the average searching time of a channel search scheme. A searching time is a random variable having a value that is the sum of detection time and switching delays. T denotes the channel searching time. Let t(k) be the sensing time spent on channel k and let δ denote one switching delay—the amount of time it takes to tune to a new channel. It may be assumed that the switching delay δ is a constant. Recall that τ is the index of the channel at which a search ends. Using Wald's identity, the average searching time E(T) is written as follows




  
    
      
        
          
            
              
                E
                ⁡
                
                  (
                  T
                  )
                
              
              =
              
                E
                (
                
                  
                    
                      ∑
                      
                        k
                        =
                        1
                      
                      τ
                    
                    ⁢
                    
                      t
                      
                        (
                        k
                        )
                      
                    
                  
                  +
                  
                    
                      (
                      
                        τ
                        -
                        1
                      
                      )
                    
                    ⁢
                    δ
                  
                
                )
              
            
          
        
        
          
            
              =
              
                
                  
                    E
                    ⁡
                    
                      (
                      τ
                      )
                    
                  
                  ⁢
                  
                    (
                    
                      
                        E
                        ⁡
                        
                          (
                          t
                          )
                        
                      
                      +
                      δ
                    
                    )
                  
                
                -
                δ
              
            
          
        
      
    
    
      
        (
        16
        )
      
    
  




where E(t) denotes the expectation value of t(k). Note that in energy detection, t is a deterministic parameter and thus E(t) simply becomes t.

E(τ) may be evaluated now and represents the average number of channels 102 that have been visited by the SU 104. Clearly, τ is a random variable ranging from 1 to K Let P(τ=k) denote the probability of the event that the SU 104 completes the search at channel k. If 1≦k<K, then τ=k implies that the SU claims that the first k−1 channels are busy and that the kth channel is free, while if k=K, τ=K implies that the SU 104 claims the first K−1 channels as busy channels. Based on these observations, P(τ=k) is written as




  
    
      
        
          P
          ⁡
          
            (
            
              τ
              =
              k
            
            )
          
        
        =
        
          {
          
            
              
                
                  
                    
                      
                        P
                        ⁡
                        
                          (
                          
                            D
                            0
                            
                              (
                              k
                              )
                            
                          
                          )
                        
                      
                      ⁢
                      
                        
                          ∏
                          
                            i
                            =
                            1
                          
                          
                            k
                            -
                            1
                          
                        
                        ⁢
                        
                          
                        
                        ⁢
                        
                          P
                          ⁡
                          
                            (
                            
                              D
                              1
                              
                                (
                                l
                                )
                              
                            
                            )
                          
                        
                      
                    
                    =
                    
                      
                        (
                        
                          1
                          -
                          φ
                        
                        )
                      
                      ⁢
                      
                        φ
                        
                          k
                          -
                          1
                        
                      
                    
                  
                  ,
                
              
              
                
                  
                    k
                    =
                    1
                  
                  ,
                  ...
                  ⁢
                  
                    
                  
                  ,
                  
                    K
                    -
                    1
                  
                
              
            
            
              
                
                  
                    
                      ∏
                      
                        i
                        =
                        1
                      
                      
                        K
                        -
                        1
                      
                    
                    ⁢
                    
                      
                    
                    ⁢
                    
                      P
                      ⁡
                      
                        (
                        
                          D
                          1
                          
                            (
                            l
                            )
                          
                        
                        )
                      
                    
                  
                  =
                  
                    φ
                    
                      K
                      -
                      1
                    
                  
                
              
              
                
                  k
                  =
                  
                    K
                    .
                  
                
              
            
          
        
      
    
    
      
        (
        17
        )
      
    
  




Then, the average number of the channels visited by the SU 104 is given by





  
    
      
        
          
            
              
                E
                ⁡
                
                  (
                  τ
                  )
                
              
              =
              
                
                  ∑
                  
                    k
                    =
                    1
                  
                  K
                
                ⁢
                
                  kP
                  ⁡
                  
                    (
                    
                      τ
                      =
                      k
                    
                    )
                  
                
              
            
          
        
        
          
            
              =
              
                
                  
                    (
                    
                      1
                      -
                      φ
                    
                    )
                  
                  ⁢
                  
                    
                      ∑
                      
                        k
                        =
                        1
                      
                      K
                    
                    ⁢
                    
                      k
                      ⁢
                      
                        
                      
                      ⁢
                      
                        φ
                        
                          k
                          -
                          1
                        
                      
                    
                  
                
                +
                
                  K
                  ⁢
                  
                    
                  
                  ⁢
                  
                    φ
                    K
                  
                
              
            
          
        
        
          
            
              =
              
                
                  1
                  -
                  
                    φ
                    K
                  
                
                
                  1
                  -
                  φ
                
              
            
          
        
      
    
    
      
        (
        18
        )
      
    
  




For given 0<α<1 and 0<π0<1, the average number of channels visited by the SU is a monotonically decreasing function of β.

Referring again to FIG. 2, a channel search applies a detection scheme sequentially 212 to each channel 102 and such a detection scheme guarantees the same target α and β for each channel 102. Hence, the design of a channel search includes the design of a detection scheme that is sequentially applied to a candidate channel 102 to minimize the average searching time, subject to constraints on the false-alarm and misdetection probabilities of a multichannel system. Mathematically, this is formulated as the following optimization problem:




  
    
      
        
          minimize
          
            α
            ,
            β
          
        
        ⁢
        
          
        
        ⁢
        
          E
          ⁡
          
            (
            T
            )
          
        
      
    
    
      
        (
        19
        )
      
    
  
  
    
      
        
          
            subject
            ⁢
            
              
            
            ⁢
            to
            ⁢
            
              :
            
            ⁢
            
              
            
            ⁢
            
              P
              FA
              mc
            
          
          ≤
          
            
              P
              _
            
            FA
            mc
          
        
        ,
        
          
            P
            MD
            mc
          
          ≤
          
            
              P
              _
            
            MD
            mc
          
        
        ,
        
          α
          >
          0
        
        ,
        
          
            and
            ⁢
            
              
            
            ⁢
            β
          
          >
          0
        
      
    
    
      
        
      
    
  




where PFAmc and PMDmc represent target false-alarm and misdetection probabilities in a multichannel system. Advantageous characteristics of (19) include the minimization problem (19) being independent of a particular cost structure and taking switching delays into account.

In an SPRT-based channel search algorithm, an SPRT is sequentially applied to the candidate channels to achieve target PFAmc and PMDmc for a multichannel system. The present principles therefore provide a sequential SPRT (S-SPRT) search.
Referring now to FIG. 6, a block/flow diagram of S-SPRT is shown, including the search design. Block 602 incorporates the steps of designing an S-SPRT search, which includes finding an acceptable probability of false alarm at block 604, finding an acceptable probability of misdetection at block 606, setting an acceptable average searching time at block 608, and determining an a priori probability that any given channel is already occupied 609. These quantities are then used to determine an upper and a lower threshold at blocks 610 and 612 respectively. The thresholds are subsequently used in block 614 to locate a free channel, as described in FIG. 3 above.
Recall that the overall false-alarm and misdetection probabilities PFAmc and PMDmc E(T) are functions of α and β, which are false-alarm and misdetection probabilities achieved by a SPRT on a single channel, respectively. Recall that in an SPRT, α and βneed to satisfy α>0, β>0, and α+β<1. Using (8) and (18), (16) is rewritten as




  
    
      
        
          
            
              min
              
                α
                ,
                β
              
            
            ⁢
            
              E
              ⁡
              
                (
                T
                )
              
            
          
          =
          
            
              
                
                  1
                  -
                  
                    
                      (
                      
                        
                          
                            (
                            
                              α
                              +
                              β
                              -
                              1
                            
                            )
                          
                          ⁢
                          
                            π
                            0
                          
                        
                        +
                        
                          (
                          
                            1
                            -
                            β
                          
                          )
                        
                      
                      )
                    
                    K
                  
                
                
                  β
                  -
                  
                    
                      (
                      
                        α
                        +
                        β
                        -
                        1
                      
                      )
                    
                    ⁢
                    
                      π
                      0
                    
                  
                
              
              ⁢
              
                (
                
                  
                    
                      [
                      
                        
                          
                            
                              π
                              0
                            
                            ⁡
                            
                              (
                              
                                1
                                -
                                α
                              
                              )
                            
                          
                          
                            μ
                            0
                          
                        
                        +
                        
                          
                            
                              (
                              
                                1
                                -
                                
                                  π
                                  0
                                
                              
                              )
                            
                            ⁢
                            β
                          
                          
                            μ
                            1
                          
                        
                      
                      ]
                    
                    ×
                    log
                    ⁢
                    
                      β
                      
                        1
                        -
                        α
                      
                    
                  
                  +
                  
                    
                      [
                      
                        
                          
                            
                              π
                              0
                            
                            ⁢
                            α
                          
                          
                            μ
                            0
                          
                        
                        +
                        
                          
                            
                              (
                              
                                1
                                -
                                
                                  π
                                  0
                                
                              
                              )
                            
                            ⁢
                            
                              (
                              
                                1
                                -
                                β
                              
                              )
                            
                          
                          
                            μ
                            1
                          
                        
                      
                      ]
                    
                    ⁢
                    log
                    ⁢
                    
                      
                        1
                        -
                        β
                      
                      a
                    
                  
                  +
                  δ
                
                )
              
            
            -
            δ
          
        
        ⁢
        
          

        
        ⁢
        
          
            subject
            ⁢
            
              
            
            ⁢
            to
            ⁢
            
              :
            
            ⁢
            
              
                
                  
                    [
                    
                      
                        απ
                        0
                      
                      +
                      
                        
                          (
                          
                            1
                            -
                            β
                          
                          )
                        
                        ⁢
                        
                          (
                          
                            1
                            -
                            
                              π
                              0
                            
                          
                          )
                        
                      
                    
                    ]
                  
                  K
                
                -
                
                  
                    [
                    
                      
                        (
                        
                          1
                          -
                          β
                        
                        )
                      
                      ⁢
                      
                        (
                        
                          1
                          -
                          
                            π
                            0
                          
                        
                        )
                      
                    
                    ]
                  
                  K
                
              
              
                1
                -
                
                  
                    (
                    
                      1
                      -
                      
                        π
                        0
                      
                    
                    )
                  
                  K
                
              
            
          
          ≤
          
            
              P
              _
            
            FA
            mc
          
        
        ⁢
        
          

        
        ⁢
        
          
        
        ⁢
        
          
            
              β
              ⁡
              
                (
                
                  1
                  -
                  
                    π
                    0
                  
                
                )
              
            
            ⁢
            
              
                1
                -
                
                  
                    (
                    
                      
                        
                          (
                          
                            α
                            +
                            β
                            -
                            1
                          
                          )
                        
                        ⁢
                        
                          π
                          0
                        
                      
                      +
                      
                        (
                        
                          1
                          -
                          β
                        
                        )
                      
                    
                    )
                  
                  K
                
              
              
                β
                -
                
                  
                    (
                    
                      α
                      +
                      β
                      -
                      1
                    
                    )
                  
                  ⁢
                  
                    π
                    0
                  
                
              
            
          
          ≤
          
            
              P
              _
            
            MD
            mc
          
        
        ⁢
        
          

        
        ⁢
        
          
        
        ⁢
        
          
            α
            +
            β
          
          <
          1
        
        ⁢
        
          

        
        ⁢
        
          
        
        ⁢
        
          α
          >
          0
        
        ⁢
        
          

        
        ⁢
        
          
        
        ⁢
        
          β
          >
          0.
        
      
    
    
      
        (
        20
        )
      
    
  




The objective function in (20), used in blocks 610 and 612, becomes accurate when both α and β are small or p1(x) is fairly close to p0(x). In general, the optimal values of α and β are not necessarily small. However, in a cognitive radio network, the case often arises where ξ is very low. In such a case, p0(x) and p1(x) are quite close and thus the objective function using the Wald's approximation becomes accurate.
In the energy detection based channel search algorithm, energy detection is applied sequentially to each channel. This energy detection based channel search is called a sequential energy detection (S-ED) search.
Referring now to FIG. 7, a block/flow diagram of S-ED is shown, including the search design. Block 702 incorporates the steps of designing an S-ED search, which includes finding an acceptable probability of false alarm at block 704, finding an acceptable probability of misdetection at block 706, setting an acceptable average searching time at block 708, and determining an a priori probability that any given channel is already occupied 709. These quantities are then used to determine a sample number and threshold at blocks 710 and 712 respectively. Detailed explanations and formulas for these quantities are provided above. The sample number and the threshold are subsequently used in block 714 to locate a free channel, as described in FIG. 5 above.
It can be assumed that the sample size in energy detection is chosen by (9) in block 710. According to (19):




  
    
      
        
          
            
              min
              
                α
                ,
                β
              
            
            ⁢
            
              E
              ⁡
              
                (
                T
                )
              
            
          
          =
          
            
              
                
                  1
                  -
                  
                    
                      (
                      
                        
                          
                            (
                            
                              α
                              +
                              β
                              -
                              1
                            
                            )
                          
                          ⁢
                          
                            π
                            0
                          
                        
                        +
                        
                          (
                          
                            1
                            -
                            β
                          
                          )
                        
                      
                      )
                    
                    K
                  
                
                
                  β
                  -
                  
                    
                      (
                      
                        α
                        +
                        β
                        -
                        1
                      
                      )
                    
                    ⁢
                    
                      π
                      0
                    
                  
                
              
              ⁢
              
                (
                
                  
                    ⌈
                    
                      
                        
                          ξ
                          
                            -
                            2
                          
                        
                        ⁡
                        
                          [
                          
                            
                              
                                Q
                                
                                  -
                                  1
                                
                              
                              ⁡
                              
                                (
                                α
                                )
                              
                            
                            -
                            
                              
                                
                                  Q
                                  
                                    -
                                    1
                                  
                                
                                ⁡
                                
                                  (
                                  
                                    1
                                    -
                                    β
                                  
                                  )
                                
                              
                              ⁢
                              
                                
                                  
                                    2
                                    ⁢
                                    ξ
                                  
                                  +
                                  I
                                
                              
                            
                          
                          ]
                        
                      
                      1
                    
                    ⌉
                  
                  +
                  δ
                
                )
              
            
            -
            δ
          
        
        ⁢
        
          

        
        ⁢
        
          
            subject
            ⁢
            
              
            
            ⁢
            to
            ⁢
            
              :
            
            ⁢
            
              
                
                  
                    [
                    
                      
                        απ
                        0
                      
                      +
                      
                        
                          (
                          
                            1
                            -
                            β
                          
                          )
                        
                        ⁢
                        
                          (
                          
                            1
                            -
                            
                              π
                              0
                            
                          
                          )
                        
                      
                    
                    ]
                  
                  K
                
                -
                
                  
                    [
                    
                      
                        (
                        
                          1
                          -
                          β
                        
                        )
                      
                      ⁢
                      
                        (
                        
                          1
                          -
                          
                            π
                            0
                          
                        
                        )
                      
                    
                    ]
                  
                  K
                
              
              
                1
                -
                
                  
                    (
                    
                      1
                      -
                      
                        π
                        0
                      
                    
                    )
                  
                  K
                
              
            
          
          ≤
          
            
              P
              _
            
            FA
            mc
          
        
        ⁢
        
          

        
        ⁢
        
          
        
        ⁢
        
          
            
              β
              ⁡
              
                (
                
                  1
                  -
                  
                    π
                    0
                  
                
                )
              
            
            ⁢
            
              
                1
                -
                
                  
                    (
                    
                      
                        
                          (
                          
                            α
                            +
                            β
                            -
                            1
                          
                          )
                        
                        ⁢
                        
                          π
                          0
                        
                      
                      +
                      
                        (
                        
                          1
                          -
                          β
                        
                        )
                      
                    
                    )
                  
                  K
                
              
              
                β
                -
                
                  
                    (
                    
                      α
                      +
                      β
                      -
                      1
                    
                    )
                  
                  ⁢
                  
                    π
                    0
                  
                
              
            
          
          ≤
          
            
              P
              _
            
            MD
            mc
          
        
        ⁢
        
          

        
        ⁢
        
          
        
        ⁢
        
          
            α
            +
            β
          
          <
          1
        
        ⁢
        
          

        
        ⁢
        
          
        
        ⁢
        
          α
          >
          0
        
        ⁢
        
          

        
        ⁢
        
          
        
        ⁢
        
          β
          >
          0.
        
      
    
    
      
        (
        21
        )
      
    
  




In energy detection, the fixed sample size te in (9) is obtained in block 710 based on the central limit theorem, which assumes that te is sufficiently large. Roughly speaking, the values of te become sufficiently large when the optimal values of α and β are sufficiently small or the SNR value is very low. Similar to the S-SPRT case, the optimal α or β is not necessarily small. However, since the low SNR detection is of practical interest in a CR network, the objective function in (9) is an accurate approximation at a low SNR level.

In order to determine an energy threshold λ in block 712 for S-ED, equation (9) is used to produce te using the same ξ that is shown in the single-channel case. α is acquired from equation (21) and used in the formula:

λ=Q−1(α)σw2/√{square root over (temin)}+σw2 

to find a suitable energy threshold. Problems (20) and (21) are nonlinear optimization problems and are not convex or concave in general. Finding a globally optimal solution is typically difficult. Since the optimization problems (20) and (21) have only two parameters α and β that belong to a finite interval [0,1], one feasible approach to find a good suboptimal solution is an enumerative search solution. Specifically, α and β are first quantized into discrete sets with small and even quantization intervals. Then an exhaustive enumeration of all possible quantized pairs (α,β) is performed to find a solution. The obtained solution may not be the optimal solution. Yet the enumerative search solution normally yields a good suboptimal solution as the quantization interval is sufficiently small. In addition, E(t) in the above two search algorithms is nondecreasing with respect to β. This implies that the optimal α and β should satisfy the constraint on PMDmc with equality, i.e., PMDmc= PMDmc for the optimal α and β. In practice, this observation can be used to reduce the number of possible α and β pair values to be searched.

In simulations, it is assumed that the primary signals are independent and identically distributed complex Gaussian random values with mean zero and variance σs2. Under this assumption, the probability density function (PDF) of yn(k) under H0, can be written as




  
    
      
        
          
            p
            0
          
          ⁡
          
            (
            
              y
              n
              
                (
                k
                )
              
            
            )
          
        
        =
        
          
            1
            
              πσ
              w
              2
            
          
          ⁢
          
            exp
            (
            
              -
              
                
                  
                    
                    
                      y
                      n
                      
                        (
                        k
                        )
                      
                    
                    
                  
                  2
                
                
                  σ
                  w
                  2
                
              
            
            )
          
        
      
    
    
      
        (
        22
        )
      
    
  




whereas the PDF of yn(k) under H1 can be written as





  
    
      
        
          
            p
            1
          
          ⁡
          
            (
            
              y
              n
              
                (
                k
                )
              
            
            )
          
        
        =
        
          
            1
            
              π
              ⁡
              
                (
                
                  
                    σ
                    s
                    2
                  
                  +
                  
                    σ
                    w
                    2
                  
                
                )
              
            
          
          ⁢
          
            
              exp
              (
              
                -
                
                  
                    
                      
                      
                        y
                        n
                        
                          (
                          k
                          )
                        
                      
                      
                    
                    2
                  
                  
                    
                      σ
                      s
                      2
                    
                    +
                    
                      σ
                      w
                      2
                    
                  
                
              
              )
            
            .
          
        
      
    
    
      
        (
        23
        )
      
    
  




The LLR of the received sample from channel k can be written as





  
    Z
    n
    
      (
      k
      )
    
  
  =
  
    
      log
      ⁢
      
        
          
            p
            1
          
          ⁡
          
            (
            
              y
              n
              
                (
                k
                )
              
            
            )
          
        
        
          
            p
            0
          
          ⁡
          
            (
            
              y
              n
              
                (
                k
                )
              
            
            )
          
        
      
    
    =
    
      
        log
        ⁢
        
          
        
        ⁢
        r
      
      +
      
        
          
            
            
              y
              n
              
                (
                k
                )
              
            
            
          
          2
        
        ⁢
        
          (
          
            
              1
              
                σ
                w
                2
              
            
            -
            
              1
              
                
                  σ
                  w
                  2
                
                +
                
                  σ
                  s
                  2
                
              
            
          
          )
        
      
    
  




where r=(1+ξ)−1. Furthermore, μ0=log r+1−r and μ1=log r+r−1.

The above-described embodiments can be better understood in the context of the example scenario described in Table I. Table I lists numerical and simulation results of PFAmc, PMDmc, E(τ) and E(T) for K=8, π0=0.5 and ξ=−5, −10, −15, −20 dB. The numerical results of PFAmc, PMDmc, E(τ) and E(T) are obtained by evaluating (14), (15), (18), and (16) at corresponding α and β, respectively. A few observations can be readily made from Table I. First, the values of the SNR ξ have considerable impact on the average searching time. Second, in both the S-SPRT and S-ED algorithms, the numerical and simulation results match quite well when ξ varies from −5 dB to −20 dB. This is because the SNR levels are fairly low. Particularly, in the S-SPRT search algorithm, the differences in PFAmc and PMDmc between numerical and simulation results become smaller as ξ decreases since p1(x) becomes closer to p0(x) as ξ decreases. Second, when ξ=−10, −15, −20 dB, the obtained α and β remain unchanged, which leads to the same value of E(τ).















TABLE 1





Methods
S-SPRT
S-ED
S-SPRT
S-ED
S-SPRT
S-ED
S-SPRT
S-ED























ξ(dB)
−5
−5
−10
−10
−15
−15
−20
−20


α
0.1706
0.1960
0.5589
0.5589
0.5589
0.5589
0.5589
0.5589


β
0.0929
0.0902
0.0553
0.0553
0.0553
0.0553
0.0553
0.0553


PFAmc
0.0054
0.0069
0.1000
0.0999
0.1000
0.1000
0.1000
0.1000


(Numerical)


PMDmc
0.1000
0.1000
0.1000
0.1000
0.1000
0.1000
0.1000
0.1000


(Numerical)


PFAmc
0.0036
0.0068
0.0724
0.0970
0.0890
0.0993
0.0958
0.0998


(Monte Carlo)


PMDmc
0.0926
0.1001
0.1008
0.0927
0.0995
0.0971
0.1000
0.0996


(Monte Carlo)


E(τ)
2.15
2.22
3.62
3.62
3.62
3.62
3.62
3.62


(Numerical)


E(T)
139.5
207.2
533.8
1056.9
3886.4
8242.1
36833
77589


(Numerical)


E(τ)
2.08
2.21
3.34
3.59
3.51
3.61
3.57
3.62


(Monte Carlo)


E(T)
146.1
206.4
558.2
1048
3998.1
8221.9
37200
77769


(Monte Carlo)









Table II lists numerical and simulation results for PFAmc, PMDmc, E(τ) and E(T) for ξ=0 dB, K=8, PFA= PMD=0.1 and δ=0.1. As can be observed from the table, there exists some inconsistency between numerical results and simulation results. In particular, the constraints on PMDmc are violated to some extent in the S-ED algorithm. This is mainly because the approximation based on the central limit theorem is no longer accurate when the fixed sample size te is relatively small.













TABLE 2





Methods
S-SPRT
S-ED
S-SPRT
S-ED
S-SPRT
S-ED





















π0
0.1
0.1
0.3
0.3
0.5
0.5


α
0.1604
0.1370
0.0500
0.0751
0.0293
0.0442


β
0.0196
0.0197
0.0477
0.0467
0.1081
0.1063


PFAmc (Numerical)
0.1000
0.0845
0.0081
0.0127
0.0005
0.0007


PMDmc (Numerical)
0.1000
0.1000
0.1000
0.1000
0.1000
0.1000


PFAmc (Monte Carlo)
0.0492
0.0967
0.0042
0.0134
0.0003
0.0008


PMDmc (Monte Carlo)
0.0866
0.1077
0.0806
0.1194
0.0820
0.1223


E(τ) (Numerical)
5.67
5.62
2.99
3.06
1.85
1.88


E(T) (Numerical)
269.9
354.6
130.5
161.1
60.7
72.1


E(τ) (Monte Carlo)
5.56
5.64
2.98
3.03
1.86
1.85


E(T) (Monte Carlo)
281.8
350.2
138.7
158.9
65.9
70.5









A third example shows how inaccurate knowledge of a priori probability π0 affects the performance of the search algorithms. Let {circumflex over (π)}0 be the estimate of π0 and let {circumflex over (α)} and {circumflex over (β)} be the optimal parameters corresponding to {circumflex over (π)}0, as calculated in blocks 604, 606, 704, and 706. In the following two cases, K=8, and PMDmc= PFAmc=0.1
The first case is underestimation, wherein ({circumflex over (π)}0<π0). It is assumed that the true value of π0 is 0.8 and ξ=−5 dB. Let Eπ0(T) denote the average searching time obtained by using α and β corresponding to {circumflex over (π)}0 and E{circumflex over (π)}0(T) denote the average searching time obtained in blocks 608 and 708 by using α and β corresponding to π0. PFAmc and PMDmc are monotonically decreasing functions on π0. This implies that α and β obtained from {circumflex over (π)}0 will still meet the constraints on PFAmc and PMDmc as {circumflex over (π)}0<π0. Hence, only the impact of underestimating π0 on E(t) is relevant. To do so, the parameter ΔU is defined as ΔAU:=(Eπ0(T)−E{circumflex over (π)}0(T))/Eπ0(T), which is used to indicate the sensitivity of E(T) to the underestimation of π0. ΔU decreases as the estimate {circumflex over (π)}0 varies from 0.1 to 0.8. It can also be observed from the figure that both algorithms are sensitive to the underestimation of π0 and the S-ED search algorithm is more sensitive than the S-SPRT search algorithm.
In the case of overestimation ({circumflex over (π)}0>π0), it is assumed that the true value of π0 is 0.2 and ξ=−15 dB. In the overestimation case, α and β are obtained by using {circumflex over (π)}0>π0. Unlike the underestimation case, the constraints on PFAmc and PMDmc are not necessarily satisfied in the overestimation case. Recall that the optimal α and β, if any, always satisfy the constraint on PMDmc with equality. Since PMDmc is decreasing on π0 and {circumflex over (π)}0>π0, α and β obtained in blocks 604, 606, 704, and 706 by assuming {circumflex over (π)}0 will result in violation of the constraint on PMDmc. To study how the overestimation of π0 affects the constraint on PMDmc we define the parameter ΔO as ΔO:=( PMDmc−PMDmc)/PMDmc. ΔO increases as the estimate {circumflex over (π)}0 increases from 0.2 to 0.9. It can be also observed that both S-SPRT and S-ED suffer from similar amount of sensitivity to the overestimation of π0.
Referring now to FIG. 8, an exemplary transceiver 802 is shown that implements a search designed according to the present principles. A processor 803 is used to design and implement a search for a free channel. A search design module 804 includes a requirements module 806 which stores or accepts (through user input) search requirements such as an acceptable misdetection probability, an acceptable false alarm probability, and an average search time. A parameter determination module 808 uses a processor to determine a number of samples and a threshold for use in the search. A search module 810 uses these parameters, where a sampling module 812 samples a channel the determined number of times via antenna 818, a test statistic module 814 uses a processor to calculate a test statistic based on the received samples, and a comparator 816 determines whether the test statistic exceeds the determined threshold. If the search module finds a free channel, the transceiver stays tuned to the channel and uses 818 to communicate.
Having described preferred embodiments of a system and method for cognitive radio channel searching with energy detection (which are intended to be illustrative and not limiting), it is noted that modifications and variations can be made by persons skilled in the art in light of the above teachings. It is therefore to be understood that changes may be made in the particular embodiments disclosed which are within the scope of the invention as outlined by the appended claims. Having thus described aspects of the invention, with the details and particularity required by the patent laws, what is claimed and desired protected by Letters Patent is set forth in the appended claims.

## Claims

1. A method for cognitive radio channel searching, the method comprising:
determining an upper threshold and a lower threshold that will find a free channel in a minimum average searching time based on a channel occupancy probability π0 and a number of channels K, constrained by a target acceptable misdetection probability and a target acceptable false alarm probability; and
searching the K channels with a signaling device using the determined upper threshold and lower threshold to find a free channel,
wherein determining comprises calculating an expected false alarm probability α and misdetection probability β based on the channel occupancy probability π0 and the number of channels K, and
wherein the lower threshold a is calculated as





  
    a
    s
  
  =
  
    log
    ⁢
    
      β
      
        1
        -
        α
      
    
  




or the upper threshold b is calculated as




  
    b
    s
  
  =
  
    log
    ⁢
    
      
        
          1
          -
          β
        
        α
      
      .

2. The method of claim 1, wherein determining comprises minimizing an average searching time according to the expected false alarm probability α and an expected misdetection probability β.

3. The method of claim 2, wherein said minimizing accounts for a switching delay that arises from switching between channels.

4. The method of claim 2, wherein said minimizing includes:



  
    
      
        min
        
          α
          ,
          β
        
      
      ⁢
      
        E
        ⁡
        
          (
          T
          )
        
      
    
    =
    
      
        
          
            1
            -
            
              
                (
                
                  
                    
                      (
                      
                        α
                        +
                        β
                        -
                        1
                      
                      )
                    
                    ⁢
                    
                      π
                      0
                    
                  
                  +
                  
                    (
                    
                      1
                      -
                      β
                    
                    )
                  
                
                )
              
              K
            
          
          
            β
            -
            
              
                (
                
                  α
                  +
                  β
                  -
                  1
                
                )
              
              ⁢
              
                π
                0
              
            
          
        
        ⁢
        
          (
          
            
              
                [
                
                  
                    
                      
                        π
                        0
                      
                      ⁡
                      
                        (
                        
                          1
                          -
                          α
                        
                        )
                      
                    
                    
                      μ
                      0
                    
                  
                  +
                  
                    
                      
                        (
                        
                          1
                          -
                          
                            π
                            0
                          
                        
                        )
                      
                      ⁢
                      β
                    
                    
                      μ
                      1
                    
                  
                
                ]
              
              ×
              log
              ⁢
              
                β
                
                  1
                  -
                  α
                
              
            
            +
            
              
                [
                
                  
                    
                      
                        π
                        0
                      
                      ⁢
                      α
                    
                    
                      μ
                      0
                    
                  
                  +
                  
                    
                      
                        (
                        
                          1
                          -
                          
                            π
                            0
                          
                        
                        )
                      
                      ⁢
                      
                        (
                        
                          1
                          -
                          β
                        
                        )
                      
                    
                    
                      μ
                      1
                    
                  
                
                ]
              
              ⁢
              log
              ⁢
              
                
                  1
                  -
                  β
                
                a
              
            
            +
            δ
          
          )
        
      
      -
      δ
    
  




  
    
      
    
    ⁢
    
      subject
      ⁢
      
        
      
      ⁢
      to
      ⁢
      
        :
      
      ⁢
      
        
          
            
              [
              
                
                  απ
                  0
                
                +
                
                  
                    (
                    
                      1
                      -
                      β
                    
                    )
                  
                  ⁢
                  
                    (
                    
                      1
                      -
                      
                        π
                        0
                      
                    
                    )
                  
                
              
              ]
            
            K
          
          -
          
            
              [
              
                
                  (
                  
                    1
                    -
                    β
                  
                  )
                
                ⁢
                
                  (
                  
                    1
                    -
                    
                      π
                      0
                    
                  
                  )
                
              
              ]
            
            K
          
        
        
          1
          -
          
            
              (
              
                1
                -
                
                  π
                  0
                
              
              )
            
            K
          
        
      
    
  



being less than or equal to the target acceptable false alarm probability,




  
    β
    ⁡
    
      (
      
        1
        -
        
          π
          0
        
      
      )
    
  
  ⁢
  
    
      1
      -
      
        
          (
          
            
              
                (
                
                  α
                  +
                  β
                  -
                  1
                
                )
              
              ⁢
              
                π
                0
              
            
            +
            
              (
              
                1
                -
                β
              
              )
            
          
          )
        
        K
      
    
    
      β
      -
      
        
          (
          
            α
            +
            β
            -
            1
          
          )
        
        ⁢
        
          π
          0
        
      
    
  




being less than or equal to the target acceptable misdetection probability, α+β<1, α>0, and β>0, where δ is a constant switching delay.

5. The method of claim 1, wherein searching the K channels comprises collecting samples from each channel k and calculating a log-likelihood ratio (LLR) for the samples for each channel k.

6. The method of claim 5, wherein searching the K channels further comprises comparing the LLR for each channel k to the determined upper and lower threshold to determine whether the channel is free or occupied.

7. The method of claim 5, wherein the LLR ΛN(k) for a channel k is




  
    
      Λ
      N
    
    =
    
      
        ∑
        
          n
          =
          1
        
        N
      
      ⁢
      
        
      
      ⁢
      
        log
        ⁢
        
          
            
              p
              1
            
            ⁡
            
              (
              
                y
                n
              
              )
            
          
          
            
              p
              0
            
            ⁡
            
              (
              
                y
                n
              
              )
            
          
        
      
    
  
  ,




where N is the maximum number of samples, yn(k) is the nth sample on channel k, and p0(x) and p1(x) are probability density functions for a channel being free and occupied, respectively.

8. A method for cognitive radio channel searching, the method comprising:
determining an upper threshold and a lower threshold that will find a free channel in a minimum average searching time based on a channel occupancy probability π0 and a number of channels K, constrained by a target acceptable misdetection probability and a target acceptable false alarm probability, comprising:
minimizing an average searching time according to an expected false alarm probability α and an expected misdetection probability β; and
searching the K channels with a signaling device, wherein searching includes:
sampling a channel;
calculating a log-likelihood ratio (LLR) for the samples for each channel k; and
comparing the LLR to the upper and lower thresholds to determine whether the channel is free or busy,


wherein determining comprises calculating an expected false alarm probability α and misdetection probability β based on the channel occupancy probability π0 and the number of channels K, and
wherein the lower threshold a is calculated as





  
    a
    s
  
  =
  
    log
    ⁢
    
      β
      
        1
        -
        α
      
    
  




or the upper threshold b is calculated as




  
    b
    s
  
  =
  
    log
    ⁢
    
      
        
          1
          -
          β
        
        α
      
      .

9. A cognitive radio device comprising:
a search parameter determination module configured to determine an upper threshold and a lower threshold that will find a free channel in a minimum average searching time based on a channel occupancy probability π0 and a number of channels K, constrained by a target acceptable misdetection probability and a target acceptable false alarm probability; and
a search module configured to search the K channels with a signaling device using the determined upper threshold and lower threshold to find a free channel,
wherein the search parameter determination module is configured to calculate an expected false alarm probability α and misdetection probability β based on the channel occupancy probability π0 and the number of channels K, and
wherein the search parameter determination module is configured to calculate the lower threshold a as





  
    a
    s
  
  =
  
    log
    ⁢
    
      β
      
        1
        -
        α
      
    
  




or the search parameter determination module is configured to calculate the upper threshold b as




  
    b
    s
  
  =
  
    log
    ⁢
    
      
        
          1
          -
          β
        
        α
      
      .

10. The cognitive radio device of claim 9, wherein the search parameter determination module is configured to minimize an average searching time according to an expected false alarm probability α and an expected misdetection probability β.

11. The cognitive radio device of claim 10, wherein the search parameter determination module is configured to minimize the average search time by



  
    
      
        min
        
          α
          ,
          β
        
      
      ⁢
      
        E
        ⁡
        
          (
          T
          )
        
      
    
    =
    
      
        
          
            1
            -
            
              
                (
                
                  
                    
                      (
                      
                        α
                        +
                        β
                        -
                        1
                      
                      )
                    
                    ⁢
                    
                      π
                      0
                    
                  
                  +
                  
                    (
                    
                      1
                      -
                      β
                    
                    )
                  
                
                )
              
              K
            
          
          
            β
            -
            
              
                (
                
                  α
                  +
                  β
                  -
                  1
                
                )
              
              ⁢
              
                π
                0
              
            
          
        
        ⁢
        
          (
          
            
              
                [
                
                  
                    
                      
                        π
                        0
                      
                      ⁡
                      
                        (
                        
                          1
                          -
                          α
                        
                        )
                      
                    
                    
                      μ
                      0
                    
                  
                  +
                  
                    
                      
                        (
                        
                          1
                          -
                          
                            π
                            0
                          
                        
                        )
                      
                      ⁢
                      β
                    
                    
                      μ
                      1
                    
                  
                
                ]
              
              ×
              log
              ⁢
              
                β
                
                  1
                  -
                  α
                
              
            
            +
            
              
                [
                
                  
                    
                      
                        π
                        0
                      
                      ⁢
                      α
                    
                    
                      μ
                      0
                    
                  
                  +
                  
                    
                      
                        (
                        
                          1
                          -
                          
                            π
                            0
                          
                        
                        )
                      
                      ⁢
                      
                        (
                        
                          1
                          -
                          β
                        
                        )
                      
                    
                    
                      μ
                      1
                    
                  
                
                ]
              
              ⁢
              log
              ⁢
              
                
                  1
                  -
                  β
                
                a
              
            
            +
            δ
          
          )
        
      
      -
      δ
    
  




  
    
      
    
    ⁢
    
      subject
      ⁢
      
        
      
      ⁢
      to
      ⁢
      
        :
      
      ⁢
      
        
          
            
              [
              
                
                  απ
                  0
                
                +
                
                  
                    (
                    
                      1
                      -
                      β
                    
                    )
                  
                  ⁢
                  
                    (
                    
                      1
                      -
                      
                        π
                        0
                      
                    
                    )
                  
                
              
              ]
            
            K
          
          -
          
            
              [
              
                
                  (
                  
                    1
                    -
                    β
                  
                  )
                
                ⁢
                
                  (
                  
                    1
                    -
                    
                      π
                      0
                    
                  
                  )
                
              
              ]
            
            K
          
        
        
          1
          -
          
            
              (
              
                1
                -
                
                  π
                  0
                
              
              )
            
            K
          
        
      
    
  



being less than or equal to the target acceptable false alarm probability,




  
    β
    ⁡
    
      (
      
        1
        -
        
          π
          0
        
      
      )
    
  
  ⁢
  
    
      1
      -
      
        
          (
          
            
              
                (
                
                  α
                  +
                  β
                  -
                  1
                
                )
              
              ⁢
              
                π
                0
              
            
            +
            
              (
              
                1
                -
                β
              
              )
            
          
          )
        
        K
      
    
    
      β
      -
      
        
          (
          
            α
            +
            β
            -
            1
          
          )
        
        ⁢
        
          π
          0
        
      
    
  




being less than or equal to the target acceptable misdetection probability, α+β<1, α>0, and β>0, where δ is a constant switching delay.

12. The cognitive radio device of claim 9, wherein the search module is configured to collect samples from each channel k and to calculate a log-likelihood ratio (LLR) for the samples for each channel k.

13. The cognitive radio device of claim 12, wherein the search module is configured to compare the LLR for each channel k to the determined upper and lower threshold to determine whether the channel is free or occupied.

14. The cognitive radio device of claim 12, wherein the LLR ΛN(k) for a channel k is




  
    
      Λ
      N
    
    =
    
      
        ∑
        
          n
          =
          1
        
        N
      
      ⁢
      
        
      
      ⁢
      
        log
        ⁢
        
          
            
              p
              1
            
            ⁡
            
              (
              
                y
                n
              
              )
            
          
          
            
              p
              0
            
            ⁡
            
              (
              
                y
                n
              
              )
            
          
        
      
    
  
  ,




where N is the maximum number of samples, yn(k) is the nth sample on channel k, and nd p0(x) and p1(x) are probability density functions for a channel being free and occupied, respectively.