# Patent

## Title
Method and access point for allocating whitespace spectrum

## Abstract

Disclosed is a method and apparatus for allocating a whitespace spectrum associated with a plurality of access points. The method includes reporting a signal strength associated with each of a plurality of other access points to a central controller. The method includes aggregating a plurality of demands to produce an aggregate demand. Each of the plurality of demands is associated with one of a plurality of users. The method includes reporting the aggregated demand to the central controller. The method includes associating one of the plurality of users with the access point based on a user setting or associating one of the plurality of users based on an allocation by the central controller. The allocation from the central controller is based on the signal strength and the aggregated demand. The allocation indicates a frequency band from the set of frequency bands to be allocated by the access point to the user.

## Background
BACKGROUND OF THE INVENTION
Embodiments relate to systems and methods for Wi-Fi like, unlicensed access in digital television (DTV) whitespaces in an enterprise setting.
Many countries are migrating from analog to digital television broadcasts. For example, in the US, this transition happened on Jun. 12, 2009; while in the UK, this transition is slated to happen in a phased manner from 2008 to 2012. In analog transmission, each TV channel uses a 6 MHz slice of bandwidth, but digital transmissions have the ability to pack four “programs” into one 6 MHz channel. Thus, this analog-to-digital transition frees up a substantial amount of television spectrum that was previously used by analog transmissions.
The newly freed up spectrum (along with other slices of unused spectrum in the 50-700 MHz (channels 2-51) television band is known as DTV whitespace (DTV-WS). Signals in the DTV spectrum propagate over long distances and penetrate through obstacles more easily. According to a recent study, 100 to 250 MHz of DTV-WS will be made available depending on the local market. The large amount of spectrum and its superior propagation characteristics make the DTV-WS a highly attractive proposition for wireless broadband deployment and usage.
In November 2008, the FCC ruled that the digital TV whitespaces may be used for unlicensed access by fixed and portable devices. Fixed devices (e.g., IEEE 802.22 base stations) are used for providing last mile internet access in underserved areas, while portable devices may be used to provide short range wireless connectivity for Internet access (e.g., Wi-Fi like access points). Furthermore, the FCC ruled that portable devices could only transmit in channels 21-51 (i.e., 512-698 MHz) and use a transmit power of 40 mW when adjacent to a TV channel in the frequency band and 100 mW on a non-adjacent channel. Additional restrictions on out-of-band emissions may also apply.
Many experts believe the FCC ruling may cause the next wireless revolution. The short range wireless access in DTV-WS has been referred to as “Wi-Fi on steroids” and “Wi-Fi 2.0” in the media. Indeed, unlicensed access in DTV-WS may decrease congestion on the 2.4 GHz ISM band, and may provide improved data rates and coverage due to the propagation properties of the spectrum.
SUMMARY OF THE INVENTION
The present invention relates to an access point and method for allocating whitespace spectrum.
In one embodiment, the access point includes a first module, a second module and a third module. The first module is configured to report a signal strength associated with each of a plurality of other access points to a central controller. The second module is configured to aggregate a plurality of demands to produce an aggregate demand, each of the plurality of demands associated with one of a plurality of users. The second module is further configured to report the aggregated demand to the central controller. The third module is configured to at least one of associate one of the plurality of users with the access point based on a user setting and associate one of the plurality of users based on allocation by the central controller. The allocation from the central controller is based on the reported signal strength and the aggregated demand. The allocation indicates a frequency band from a set of frequency bands to be allocated by the access point to the user.
In one embodiment, the method includes reporting a signal strength associated with each of a plurality of other access points to a central controller. The method includes aggregating a plurality of demands to produce an aggregate demand. Each of the plurality of demands is associated with one of a plurality of users. The method includes reporting the aggregated demand to the central controller. The method includes associating one of the plurality of users with the access point based on a user setting or associating one of the plurality of users based on an allocation by the central controller. The allocation from the central controller is based on the signal strength and the aggregated demand. The allocation indicates a frequency band from the set of frequency bands to be allocated by the access point to the user.



BRIEF DESCRIPTION OF THE DRAWINGS
The present invention will become more fully understood from the detailed description given herein below and the accompanying drawings, wherein like elements are represented by like reference numerals, which are given by way of illustration only and thus are not limiting of the present invention and wherein:
FIG. 1 illustrates a whitespace frequency spectrum according to example embodiments,
FIG. 2 illustrates a system architecture according to example embodiments,
FIG. 3 illustrates an access point according to example embodiments,
FIG. 4 illustrates a method for reporting signal strength according to example embodiments,
FIG. 5 illustrates a method for demand aggregation according to example embodiments,
FIG. 6 illustrates a method for allocating whitespace spectrum according to example embodiments,
FIG. 7 is a signal flow diagram associated with allocation of whitespace frequency bands according example embodiments.



It should be noted that these Figures are intended to illustrate the general characteristics of methods, structure and/or materials utilized in certain example embodiments and to supplement the written description provided below. These drawings are not, however, to scale and may not precisely reflect the precise structural or performance characteristics of any given embodiment, and should not be interpreted as defining or limiting the range of values or properties encompassed by example embodiments. For example, the relative thicknesses and positioning of molecules, layers, regions and/or structural elements may be reduced or exaggerated for clarity. The use of similar or identical reference numbers in the various drawings is intended to indicate the presence of a similar or identical element or feature.
DETAILED DESCRIPTION OF THE EMBODIMENTS
While example embodiments are capable of various modifications and alternative forms, embodiments thereof are shown by way of example in the drawings and will herein be described in detail. It should be understood, however, that there is no intent to limit example embodiments to the particular forms disclosed, but on the contrary, example embodiments are to cover all modifications, equivalents, and alternatives falling within the scope of the claims. Like numbers refer to like elements throughout the description of the figures.
It will be understood that, although the terms first, second, etc. may be used herein to describe various elements, these elements should not be limited by these terms. These terms are only used to distinguish one element from another. For example, a first element could be termed a second element, and, similarly, a second element could be termed a first element, without departing from the scope of example embodiments. As used herein, the term “and/or” includes any and all combinations of one or more of the associated listed items.
It will be understood that when an element is referred to as being “connected” or “coupled” to another element, it can be directly connected or coupled to the other element or intervening elements may be present. In contrast, when an element is referred to as being “directly connected” or “directly coupled” to another element, there are no intervening elements present. Other words used to describe the relationship between elements should be interpreted in a like fashion (e.g., “between” versus “directly between,” “adjacent” versus “directly adjacent,” etc.).
The terminology used herein is for the purpose of describing particular embodiments only and is not intended to be limiting of example embodiments. As used herein, the singular forms “a,” “an” and “the” are intended to include the plural forms as well, unless the context clearly indicates otherwise. It will be further understood that the terms “comprises,” “comprising,” “includes” and/or “including,” when used herein, specify the presence of stated features, integers, steps, operations, elements and/or components, but do not preclude the presence or addition of one or more other features, integers, steps, operations, elements, components and/or groups thereof.
It should also be noted that in some alternative implementations, the functions/acts noted may occur out of the order noted in the figures. For example, two figures shown in succession may in fact be executed concurrently or may sometimes be executed in the reverse order, depending upon the functionality/acts involved.
Unless otherwise defined, all terms (including technical and scientific terms) used herein have the same meaning as commonly understood by one of ordinary skill in the art to which example embodiments belong. It will be further understood that terms, e.g., those defined in commonly used dictionaries, should be interpreted as having a meaning that is consistent with their meaning in the context of the relevant art and will not be interpreted in an idealized or overly formal sense unless expressly so defined herein.
Portions of the example embodiments and corresponding detailed description are presented in terms of software, or algorithms and symbolic representations of operation on data bits within a computer memory. These descriptions and representations are the ones by which those of ordinary skill in the art effectively convey the substance of their work to others of ordinary skill in the art. An algorithm, as the term is used here, and as it is used generally, is conceived to be a self-consistent sequence of steps leading to a desired result. The steps are those requiring physical manipulations of physical quantities. Usually, though not necessarily, these quantities take the form of optical, electrical, or magnetic signals capable of being stored, transferred, combined, compared, and otherwise manipulated. It has proven convenient at times, principally for reasons of common usage, to refer to these signals as bits, values, elements, symbols, characters, terms, numbers, or the like.
In the following description, illustrative embodiments will be described with reference to acts and symbolic representations of operations (e.g., in the form of flowcharts) that may be implemented as program modules or functional processes include routines, programs, objects, components, data structures, etc., that perform particular tasks or implement particular abstract data types and may be implemented using existing hardware at existing network elements. Such existing hardware may include one or more Central Processing Units (CPUs), digital signal processors (DSPs), application-specific-integrated-circuits, field programmable gate arrays (FPGAs) computers or the like.
It should be borne in mind, however, that all of these and similar terms are to be associated with the appropriate physical quantities and are merely convenient labels applied to these quantities. Unless specifically stated otherwise, or as is apparent from the discussion, terms such as “processing” or “computing” or “calculating” or “determining” of “displaying” or the like, refer to the action and processes of a computer system, or similar electronic computing device, that manipulates and transforms data represented as physical, electronic quantities within the computer system's registers and memories into other data similarly represented as physical quantities within the computer system memories or registers or other such information storage, transmission or display devices.
Note also that the software implemented aspects of the example embodiments are typically encoded on some form of program storage medium or implemented over some type of transmission medium. The program storage medium may be magnetic (e.g., a floppy disk or a hard drive) or optical (e.g., a compact disk read only memory, or “CD ROM”), and may be read only or random access. Similarly, the transmission medium may be twisted wire pairs, coaxial cable, optical fiber, or some other suitable transmission medium known to the art. The example embodiments not limited by these aspects of any given implementation.
As used herein, the term “client” may be considered synonymous to, and may hereafter be occasionally referred to, as a mobile, mobile unit, mobile station, mobile user, user equipment, subscriber, user, remote station, access terminal, receiver, etc., and may describe a remote user of wireless resources in a wireless communication network. The term “access point” may be considered synonymous to and/or referred to as a base station, base transceiver station (BTS), NodeB, extended NodeB, evolved NodeB, femto cell, pico cell, etc. and may describe equipment that provides the radio baseband functions for data and/or voice connectivity between a network and one or more users.
In the following description, the term “Wi-Fi like” system is used to describe a wireless LAN with (i) access points (APs) connected to the Internet, and (ii) clients who associate with the APs. Further, example embodiments may employ enterprise settings to allow a system and architecture for which a central controller may be configured to perform efficient spectrum allocation based on access point demands.
Initially, this disclosure will describe the effect of frequency dependent radio propagation and out of band emissions on an example system. Next, this disclosure will describe algorithms to base an exemplary system on. Next, this disclosure will describe an example embodiment of a multi-radio based architecture taking into consideration the effect of frequency dependent radio propagation, out of band emissions and the aforementioned algorithms. Next, this disclosure will describe algorithms to efficiently allocate variable spectrum to access points based on their demand. Finally, an example embodiment of a method using the architecture and the algorithms will be described.
Those skilled in the art will recognize that spectrum sensing techniques for wireless devices, etc. are available to the example system. Moreover, those skilled in the art will recognize example embodiments use available whitespaces for a given location that may vary slowly over time.
FIG. 1 illustrates a whitespace frequency spectrum according to example embodiments. As shown in FIG. 1, on either end of the spectrum is a DTV channel. The whitespace frequency spectrum includes a channel of bandwidth W. The channel of bandwidth W includes a low guard band x and a high guard band y. The channel of bandwidth W further includes a usable bandwidth or transmission spectrum B.
The following algorithms are algorithms used to base an exemplary system on.
Frequency Dependent Radio Propagation
In free space, the received power at a distance d from a point source radiating at wavelength λ with power Pt and antenna gain G is:

Pr=GPt(λ=4πd)2.  (1)

To account for additional phenomenon that occur in the real-world (e.g., reflection, diffraction and scattering) the following path loss model in the range 900 MHz-100 GHz has been recommended:

PL(d)=10 log10fc2+10η log10d+Lf(n)−28 (dB).  (2)

Where:

PL(d) is the path loss model,

fc is the carrier frequency,

η is the path loss coefficient, and

Lf(n) is the additional loss due to the number of floors n between the transmitter and receiver.

Thus, there is an fc2 dependence of the path-loss on the frequency.
Out of Band Emissions
Signals transmitted by a radio are never entirely confined within the intended bandwidth B. Out-of band emission (OE) is the signal energy that leaks outside the main band. Regulatory authorities and standardization bodies typically prescribe a spectrum mask for any technology in a particular band of operation. The mask specifies the rate at which the power spectral density (PSD) decays relative to the peak power spectral density outside the intended band of transmission. For example, the IEEE 802.11g standard specifies the PSD decay at a rate of 1.1 dB/MHz.
The OE of a transmitter, at a frequency f MHz away from the edge of a B Hz wide transmission spectrum is given by:




  
    
      
        
          OE
          ⁡
          
            (
            f
            )
          
        
        =
        
          
            
              
                P
                t
              
              ⁢
              L
            
            B
          
          ⁢
          
            e
            
              
                -
                α
              
              ⁢
              
                
              
              ⁢
              f
            
          
        
      
    
    
      
        (
        3
        )
      
    
  




Where, L and α are constants that depend on the spectrum mask. For example, L=−20 dBr, α=−1:1 dB/MHz for the IEEE 802.11g spectrum mask. Therefore the measured emissions outside the intended band will be determined by the peak power spectral density, L and a specified by the spectrum mask.
The spectrum mask allows determination of adjacent channel interference (ACI) precisely. For example, if two devices are separated by a distance d in free space, the first device is transmitting at power Pt over a bandwidth B in frequency band fc, the second device is receiving over a bandwidth of W, and there is a guard band of δ between the two bands, then the total adjacent channel interference (ACI) may be computed by integrating the leakage power over the adjacent channel of bandwidth W, using equation 2 and equation 3 with Lf (n)=0 as:




  
    
      
        
          
            
              P
              t
            
            ⁢
            L
            ⁢
            
              
            
            ⁢
            
              10
              2.8
            
          
          
            
              Bd
              η
            
            ⁢
            
              f
              c
              2
            
            ⁢
            α
          
        
        ⁢
        
          
            e
            
              
                -
                α
              
              ⁢
              
                
              
              ⁢
              δ
            
          
          ⁡
          
            (
            
              1
              -
              
                e
                
                  α
                  ⁢
                  
                    
                  
                  ⁢
                  W
                
              
            
            )
          
        
      
    
    
      
        (
        4
        )
      
    
  




System Algorithms

An exemplary system may determine transmit power, determine guard bands between adjacent slices of the spectrum, develop interference graphs in different whitespaces and may rely on a devised metric called aggregate spectral efficiency (units are bits/sec/Hz) that captures the average data rate that each access point may receive from unit bandwidth in different whitespaces.
Equation 2 above may be modified to meet FCC requirements briefly described above for digital television transmission such that:

PLdtv(d)=10 log10fc2+10η log10d+Lf(n)−10 (dB).  (5)

Where:

PLdtv(d) is the path loss model for a digital transmission,

fc is the carrier frequency,

η is the path loss coefficient, and

Lf(n) is the additional loss due to the number of floors n between the transmitter and receiver.

Consider a single transmit-receive pair separated by distance d in a single DTV whitespace of width W MHz. Assume an additive white gaussian noise (AWGN) channel with noise power spectral density No, if the whitespace spans from frequency fl to fh, with fh−fl=W, if there is a guard band of x (y) MHz between the DTV channel on the left (and the right) and the whitespace transmission to avoid ACI to DTV receivers, and if B MHz is used for transmission by the transmit-receive pair, then the path loss between the transmit-receive pair may be given by Equation 2, where Lf(n) is zero.
For example, if the whitespace device has a spectrum mask with parameters L and a as in Equation 3, the path loss to the DTV receiver at distance 10 m is given by PLdtv(10) as in Equation 5, the maximum interference that can leak into the DTV receiver is given by Idtv, and if the system operates in a high SNR regime, i.e., SNR>>1, then maximizing the Shannon capacity may result in an optimal transmit power.
For example to calculate an optimal transmit power, first calculate an optimum bandwidth B as:




  
    
      
        B
        =
        
          min
          ⁡
          
            (
            
              W
              ,
              
                
                  
                    1
                    α
                  
                  ⁢
                  
                    log
                    ⁡
                    
                      (
                      
                        
                          4
                          ⁢
                          γ
                          ⁢
                          
                            
                          
                          ⁢
                          
                            f
                            l
                            2
                          
                        
                        
                          
                            
                              N
                              o
                            
                            ⁡
                            
                              (
                              
                                
                                  2
                                  ⁢
                                  
                                    f
                                    l
                                  
                                
                                +
                                W
                                +
                                z
                              
                              )
                            
                          
                          2
                        
                      
                      )
                    
                  
                
                +
                
                  
                    W
                    +
                    z
                  
                  2
                
              
            
            )
          
        
      
    
    
      
        (
        6
        )
      
    
  




Second, calculate an optimum capacity C using a Shannon capacity formula and based on the calculated optimum bandwidth B as:




  
    
      
        C
        =
        
          B
          ⁡
          
            [
            
              
                
                  log
                  2
                
                ⁡
                
                  (
                  
                    
                      4
                      ⁢
                      γ
                      ⁢
                      
                        
                      
                      ⁢
                      
                        f
                        l
                        2
                      
                    
                    
                      
                        
                          N
                          o
                        
                        ⁡
                        
                          (
                          
                            
                              2
                              ⁢
                              
                                f
                                l
                              
                            
                            +
                            W
                            +
                            z
                          
                          )
                        
                      
                      2
                    
                  
                  )
                
              
              +
              
                α
                ⁢
                
                  
                
                ⁢
                x
                ⁢
                
                  
                
                ⁢
                
                  log
                  2
                
                ⁢
                e
              
            
            ]
          
        
      
    
    
      
        (
        7
        )
      
    
  




Finally, calculate an optimal transmit power P as:

P=γfl2eαx  (8)

Where for each of equations 6, 7 and 8:




  
    z
    =
    
      
        2
        α
      
      ⁢
      
        
          log
          e
        
        ⁡
        
          (
          
            
              f
              h
            
            
              f
              l
            
          
          )
        
      
    
  
  ,
  
    

  
  ⁢
  
    x
    =
    
      
        W
        +
        z
        -
        B
      
      2
    
  
  ,
  
    

  
  ⁢
  
    y
    =
    
      
        W
        -
        z
        -
        B
      
      2
    
  
  ,
  
    

  
  ⁢
  
    γ
    =
    
      
        
          
            I
            dtv
          
          ⁢
          α
        
        
          L
          ⁡
          
            (
            
              1
              -
              
                e
                
                  
                    -
                    6
                  
                  ⁢
                  α
                
              
            
            )
          
        
      
      ⁢
      
        
          (
          
            10
            d
          
          )
        
        η
      
    
  
  ,




W is the available whitespace bandwidth,
L and α are constants that depend on the spectrum mask,
fl is the low frequency value of W,
fh is the high frequency value of W,
Idtv is the maximum interference which can leak into a DTV receiver, and
d is a distance from a point source (e.g. access point antenna).
Preferably, in a whitespace W that is to be shared between several access points, each access point receives at least a bandwidth of 6 MHz and the transmit power for each access point may be set to 40 mW.
If each access point provides coverage up to a distance d, then to compute the worst case adjacent channel interference (ACI), we assume that two clients, A and B are communicating with two radios rA and rB respectively. The two radios rA and rB need not be associated with the same access point. Client A may be located at the edge of the transmission range of radio rA.
If radio rA receives a signal from Client A over bandwidth Bm and radio rB simultaneously transmits a signal to Client B over a bandwidth of 6 MHz, the bandwidths for Client A and Client B may be chosen so as to maximize the ACI as shown by equation 4, then there may be at least two cases for which the guard band may be calculated: (i) the two radios rA and rB belong to the same access point and (ii) if radio rA and radio rB belong to different access points separated by a distance daci.
For both cases, the guard band x may be calculated such that:




  
    
      
        x
        =
        
          
            1
            α
          
          ⁢
          
            
              log
              e
            
            ⁡
            
              (
              
                
                  
                    γ
                    ⁢
                    
                      
                    
                    ⁢
                    
                      PL
                      ⁡
                      
                        (
                        
                          1
                          -
                          
                            e
                            
                              
                                -
                                α
                              
                              ⁢
                              
                                
                              
                              ⁢
                              
                                B
                                m
                              
                            
                          
                        
                        )
                      
                    
                  
                  
                    6
                    ⁢
                    α
                  
                
                
                  
                    
                      P
                      ⁢
                      
                        
                      
                      ⁢
                      
                        10
                        2.8
                      
                    
                    
                      
                        d
                        η
                      
                      ⁢
                      
                        f
                        c
                        2
                      
                    
                  
                  -
                  
                    γ
                    ⁢
                    
                      
                    
                    ⁢
                    
                      N
                      o
                    
                    ⁢
                    
                      B
                      m
                    
                  
                
              
              )
            
          
        
      
    
    
      
        (
        9
        )
      
    
  




Preferably, for the first case successful reception at radio rA requires a minimum SINR threshold of γ where:




  
    
      
        
          
            
              P
              ⁢
              
                
              
              ⁢
              
                10
                2.8
              
            
            
              
                d
                η
              
              ⁢
              
                f
                c
                2
              
            
          
          
            
              
                PL
                ⁢
                
                  
                
                ⁢
                
                  
                    e
                    
                      
                        -
                        α
                      
                      ⁢
                      
                        
                      
                      ⁢
                      x
                    
                  
                  ⁡
                  
                    (
                    
                      1
                      -
                      
                        e
                        
                          α
                          ⁢
                          
                            
                          
                          ⁢
                          
                            B
                            m
                          
                        
                      
                    
                    )
                  
                
              
              
                6
                ⁢
                α
              
            
            +
            
              
                N
                o
              
              ⁢
              
                B
                m
              
            
          
        
        ≥
        γ
      
    
    
      
        (
        10
        )
      
    
  




Preferably, fc=fc(max)=698 MHz, transmit power=40 mW, range=50 m, a worst case η=4.5 and γ=6 dB, results in a maximum possible adjacent channel separation of about 20 MHz for the first case. Further, even with fc as low as 512 MHz, the channel separation decreases only marginally. The corresponding channel separation in the 2.4 GHz ISM band increases to about 25 MHz.
The guard band in the second case, with the same settings as above, and calculations based on equation 9 with daci as small as 2 m, the guard band requirement falls to zero.
A known method to mitigate co-channel interference between two wireless devices (not talking to each other) is to ensure that they are allotted the same channel only if the received power from one device at the other device is less than a certain threshold β. In example embodiments, the path loss depends on frequency. Therefore, two access points that interfere with each other in one part of the spectrum need not do so in another part of the spectrum. Therefore, the interference graph between different access points in the system is a function of the whitespace that is being used. This effect may be much more pronounced if access to portable devices is across DTV Channels 2-51.
In example embodiments, a received power measurement in one part of the spectrum may be used to infer a received power in some other part of the spectrum. Consider two access points AP1 and AP2. If AP1 is transmitting using power P and Pr(f1) is the received power at AP2 when the transmission is performed using carrier frequency f1, and Pr(f2) is defined in the same manner, then using Equation 2, it can be shown that in the absence of ambient interference:




  
    
      
        
          
            
              P
              r
            
            ⁡
            
              (
              
                f
                1
              
              )
            
          
          -
          
            
              P
              r
            
            ⁡
            
              (
              
                f
                2
              
              )
            
          
        
        =
        
          10
          ⁢
          
            
          
          ⁢
          coeff
          ⁢
          
            
          
          ⁢
          
            log
            ⁡
            
              (
              
                
                  f
                  2
                
                
                  f
                  1
                
              
              )
            
          
        
      
    
    
      
        (
        11
        )
      
    
  




where coeff is an environment dependent parameter that may be obtained through system measurements. Preferably, the value of coeff, in a system having ideal conditions, is 2. Further, in the presence of ambient interference, the difference in ambient interferences in f1 and f2 may be added to the right hand side of equation 11.

Equation 11 shows that if either of Pr(f1) or Pr(f2) is known, then the other may be inferred. If each access point experiences a different ambient interference in each whitespace, then a two step process may be followed. In the first step, each access point reports (e.g., via a control channel) the ambient interference the access point experiences in each whitespace to, for example, a central controller. In the second step, measurements in any one frequency band may be used to estimate if the total interference (e.g., ambient plus induced interference) experienced by the access point in the other frequency band exceeds a given threshold. Preferably, the lower frequency bands may be used to estimate interference graphs in the higher frequency bands because for a given receiver sensitivity, control messages in the lower frequency band are more likely to be received by an access point.
Efficiently allocating demand based spectrum to access points may require the knowledge of how much data rate does a given amount of spectrum translate to for each access point in each whitespace. A simple solution is to do a worst case design where the data rate for a given amount of spectrum is achieved using the lowest modulation. This is equivalent to assuming that all users are at the edge of the coverage region which is clearly too conservative. A worst case design is not desirable for obvious reasons.
Example embodiments introduce a metric called aggregate spectral efficiency (ASE). The ASE metric may capture the dependence between a given amount of spectrum and data rate based on (i) the RSSI values of all clients associated with an access point and (ii) the location of the spectrum. By using ASE, worst case design scenarios may be avoided.
To derive the ASE metric (η) determine how the data rate depends on SINR. In the ideal case this is given by Shannon's formula, which essentially shows that the spectral efficiency (bits/sec/Hz) is a constant multiplier of the SINR in dB. For many modern physical layer technologies, for a given bit error rate, the achieved spectral efficiency takes discrete values that depend on SINR thresholds. Moreover, these discrete values vary linearly with the SINR thresholds in dB. If spectral efficiency varies with SINR as a+bSINR(dB) for some constants a and b that depend on the physical. layer technology and a client k perceives SINRk(f1)(dB), then the spectral efficiency for the kth client is ηk(f1)=a+bSINRk(f1). If there are N clients and each client has equal opportunity to communicate with the access point, then the ASE is given by:




  
    
      
        
          
            η
            avg
          
          ⁡
          
            (
            
              f
              1
            
            )
          
        
        =
        
          a
          +
          
            
              b
              N
            
            ⁢
            
              
                ∑
                
                  k
                  =
                  1
                
                N
              
              ⁢
              
                
                  SINR
                  k
                
                ⁡
                
                  (
                  
                    f
                    1
                  
                  )
                
              
            
          
        
      
    
    
      
        (
        12
        )
      
    
  




Equation 12 shows that in a given band, the ASE may be inferred from measurements of SINR. If every client experiences an average interference Ith, then an estimate of ASE across all bands in the spectrum may be computed without having to do measurements in each band. If two carrier frequencies f1 and f2 with f1<f2, and RSSIk(f1) and RSSIk(f2) are the received signal strengths in dB for the kth client, SINRk(fi)=RSSIk(fi)−Ith, then SINRk(f2)−SINRk(f1)=RSSIk(f2)−RSSIk(f1)=20 log10 (f1/f2), from which it follows that:

ηavg(f1)−ηavg(f2)=20 log10(f1/f2)  (13)

Multi-Radio Based Architecture

FIG. 2 illustrates a system architecture 200 according to example embodiments. As shown in FIG. 2, the system architecture 200 may include a central controller 201 communicatively connected to one or more access points 205. The access points 205 may be communicatively connected to one or more clients or users 210. Note, at any given moment in time, an access point 205 may not have a client or user associated with the access point 205.
An access point 205 may be configured to be portable and may be configured to sense wireless microphones/TV signals up to, for example, −114 dBm. Each access point 205 includes multiple transceivers. At least one transceiver may be dedicated for communications over a common control channel. The control channel serves three purposes. First, the control channel is used for client-access point 205 associations. Second, the control channel is used to make measurements to infer interference graphs over the whitespaces. Third, the control channel is used to make measurements to compute the aggregate spectral efficiency (ASE) across all whitespaces. The medium access mechanism used for the control channel may be a design choice and is not discussed for the sake of brevity.
The control channel may operate over a frequency band lower than DTV channel 21. The control channel may operate over a frequency band associated with a lowest operating spectrum in the whitespace. As is discussed above, the interference graph in a higher frequency band may be inferred from measurements over the control channel located at a lower frequency. Preferably, the control channel may be an industrial, scientific and medical (ISM) band channel (e.g., 433 MHz) because the ISM band channel is available at all locations all the time.
All other transceivers may be configured to tune into any set of authorized whitespace frequencies. For example, existing radio technologies allow transceivers to tune across several GHz. However, each radio may tune to only a single contiguous band at any given time. Modifying the bandwidth on demand may be achievable in Orthogonal frequency-division multiplexing (OFDM) based systems as is known and is referred to as channel bonding.
The clients 210 have one or more radios. The clients 210 may be configured as portable devices in a master slave relationship either with a fixed device or another portable device (e.g., an access point 205). If a client has a single radio, then the client first tunes into the control channel and listens for beacon messages from the various access points 205. While several complex client-access point association decisions may be possible, in example embodiments the client sends an association request to the access point 205 from which the beacon message is received with the greatest signal strength. The association request message may contain the MAC ID of the clients 210, desired data rate (demand) and received signal strength indication (RSSI) from the access point 205. If the association request is accepted, then the access point 205 responds with the set of whitespaces, center frequencies and bandwidths over which the client may communicate.
If a client is finished with its session, the client sends a dissociation request to the access point 205. Alternatively, if an access point 205 does not receive transmissions from the client for more than a certain period of time, then the access point 205 assumes that the client is no longer associated with the access point 205.
The central controller 201 may be configured to periodically compute the interference graphs in the different whitespaces. Computing the interference graphs may be performed using measurements over a single control channel. The central controller 201 may be configured to compute the ASE for each access point 205 in the different whitespaces based on control channel aggregate RSSI measurements provided by each access point 205. The central controller 201 may be configured to compute an efficient allocation of the available whitespaces based on interference maps, ASEs, ACI constraints, transmit power constraints, and demands. Example embodiments of the central controller 201 will be described in more detail below.
Algorithms for Whitespace Spectrum Allocation
Next, three algorithms for proportionally fair whitespace spectrum allocation (PF-WSA) will be discussed. The first and second algorithms may be used for spectrum allocation in a single whitespace. The third algorithm may be used for multiple whitespace spectrum allocation.
Algorithm one (PfSpecAllocClique) is based on proportionally fair spectrum allocation of a clique. A clique is a grouping of access points 205. Pseudo-code for algorithm one is as follows:










Algorithm 1 PfSpecAllocClique: Prop. Fair Spectrum Allocation in WSj


when the interference graph is a Clique CG
















 1:
for all nodes y ∈ CG do


 2:
 Define the utility as a function of bandwidth by accounting for







the spectral efficiency. Define









  Uy(b) = dy log(1 + (ηyjb − my)+), b ≧ 6,







and Uy(b) = 0 for b < bm = 6.








 3:
Quantize the utility as follows. Compute the bandwidth required







to get an utility of εq(1 + εq)r, r = 0, 1, 2,, ry,max, where ry,max


depends on the demand dy. In other words, compute









  qy(r) = min {b: Uy(b) ≧ εq(1 + εq)r}.


 4:
end for


 5:
Initialize spectrum given to APy as by := 0 for every y ∈ CG. Also



 denote by ry (valid only when by > 0) the bandwidth offered to



 APy in terms of what quantized level is reached by Uy(·).


 6:
Initialize used bandwidth as UB := 0 and Y := CG. Also, W is the



 width of the WS.


 7:
while UB < W or Y ≠ ∅; do


 8:
 for all y ∈ Y do


 9:
  Compute slope(y) as follows:


 



   



  
    slope
    ⁡
    
      (
      y
      )
    
  
  =
  
    {
    
      
        
          
            
              
                
                  
                    
                      ɛ
                      q
                    
                    ⁡
                    
                      (
                      
                        1
                        +
                        
                          ɛ
                          q
                        
                      
                      )
                    
                  
                  
                    
                      r
                      y
                    
                    +
                    1
                  
                
                -
                
                  
                    
                      ɛ
                      q
                    
                    ⁡
                    
                      (
                      
                        1
                        +
                        
                          ɛ
                          q
                        
                      
                      )
                    
                  
                  
                    r
                    y
                  
                
              
              
                
                  
                    q
                    y
                  
                  ⁡
                  
                    (
                    
                      
                        r
                        y
                      
                      +
                      1
                    
                    )
                  
                
                -
                
                  
                    q
                    y
                  
                  ⁡
                  
                    (
                    
                      r
                      y
                    
                    )
                  
                
              
            
            ;
            
              
                b
                y
              
              ≠
              0
            
          
        
      
      
        
          
            
              
                max
                
                  s
                  ≥
                  0
                
              
              ⁢
              
                
                  
                    
                      ɛ
                      q
                    
                    ⁡
                    
                      (
                      
                        1
                        +
                        
                          ɛ
                          q
                        
                      
                      )
                    
                  
                  s
                
                
                  
                    q
                    y
                  
                  ⁡
                  
                    (
                    s
                    )
                  
                
              
            
            ;
            
              
                b
                y
              
              =
              0
            
          
        
      
    
  






 


10:
  if by = 0 then


 


11: 
   



  
    δ
    y
  
  =
  
    
      arg
      
        max
        
          s
          ≥
          0
        
      
    
    ⁢
    
      
        
          
            ɛ
            q
          
          ⁡
          
            (
            
              1
              +
              
                ɛ
                q
              
            
            )
          
        
        s
      
      
        
          q
          y
        
        ⁡
        
          (
          s
          )
        
      
    
  






 


12:
  else


13:
   δy = 1


14:
  end if


15:
 end for


16:
 Among nodes in y′ ∈ Y, find the node ym such that


 



   



  
    y
    m
  
  =
  
    arg
    ⁢
    
      
        max
        y
      
      ⁢
      
        [
        
          slope
          ⁡
          
            (
            y
            )
          
        
        ]
      
    
  






 



 {ym is the node that best utilizes the spectrum for going to the



 next quanta.}


17:
 UB ← UB + (qym(rym + δym) − qym(rym))


18:
 If bym = 0 , then set rym = δym; else update rym ← rym + δym


19:
 bym ← qym(rym)


20:
 if rym = rym,max then


21:
   Y ← Y − {ym}


22:
 end if


23:
end while


24:
if UB > W then


25:
 rym ← rym − δym


26:
end if


27:
Compute the total utility TU(CG) attainable by the nodes in CG, and



 total bandwidth used TB(CG) by these nodes as


 



   



  
    
      TU
      ⁡
      
        (
        
          C
          G
        
        )
      
    
    =
    
      
        ∑
        
          
            yεC
            G
          
          ,
          
            
              b
              y
            
            >
            0
          
        
      
      ⁢
      
        
      
      ⁢
      
        
          
            ɛ
            q
          
          ⁡
          
            (
            
              1
              +
              
                ɛ
                q
              
            
            )
          
        
        
          r
          y
        
      
    
  
  ,
  
    
  
  ⁢
  
    
      TB
      ⁡
      
        (
        
          C
          G
        
        )
      
    
    =
    
      
        ∑
        
          yεC
          G
        
      
      ⁢
      
        
      
      ⁢
      
        b
        y
      
    
  






 


28
if TU(CG) < Uym(δym) then


29:
 TU(CG) = Uym(δym), and rym = δym and ri = 0 for i ≠ ym.


30:
end if









Algorithm one starts by expressing the achievable log utility of an access point 205 in terms of the bandwidth, and then quantizing the data rates in steps of εq; εq (1+εq); εq (1+εq)2; εq (1+εq)3; : : : . (steps 1-4). Parameter εq may be chosen to balance computational complexity and accuracy of the algorithm. Then the algorithm greedily assigns spectrum to the access point 205 until the total whitespace width is exhausted (step 5-23). At each stage of the greedy allocations, the following two requirements may be met:
If an access point 205 is assigned spectrum in a greedy stage, then assign sufficient spectrum so that the access points' log utility becomes εq (1+εq)r for some r. Also, if an access point 205 has already been allocated some spectrum, then the greedy choice may allocate enough spectrum for the utility to increase by one quantization level, for example, the greedy step increases the log utility from εq(1+εq)r to εq(1+εq)r+1.
The greedy choice may be to assign spectrum to the access point 205 for which allocating spectrum for increasing the log utility to one of the next quantization levels is spectrally most efficient. There are two cases depending on whether an access point 205 had been allocated spectrum until the previous greedy step or not. If access point APy was not allocated any spectrum until the previous greedy step, then we compute slope(y) as:




  
    
      
        
          slope
          ⁡
          
            (
            y
            )
          
        
        =
        
          
            max
            
              s
              ≥
              0
            
          
          ⁢
          
            
              
                
                  ɛ
                  q
                
                ⁡
                
                  (
                  
                    1
                    +
                    
                      ɛ
                      q
                    
                  
                  )
                
              
              s
            
            
              
                q
                y
              
              ⁡
              
                (
                s
                )
              
            
          
        
      
    
    
      
        (
        13
        )
      
    
  




On the other hand, if APy was allocated spectrum until the previous step so that the utility was εq (1+εq)ry, then slope(y) is computed as:




  
    
      
        
          slope
          ⁡
          
            (
            y
            )
          
        
        =
        
          
            
              
                
                  ɛ
                  q
                
                ⁡
                
                  (
                  
                    1
                    +
                    
                      ɛ
                      q
                    
                  
                  )
                
              
              
                
                  r
                  y
                
                +
                1
              
            
            -
            
              
                
                  ɛ
                  q
                
                ⁡
                
                  (
                  
                    1
                    +
                    
                      ɛ
                      q
                    
                  
                  )
                
              
              2
            
          
          
            
              
                q
                y
              
              ⁡
              
                (
                
                  
                    r
                    y
                  
                  +
                  1
                
                )
              
            
            -
            
              
                q
                y
              
              ⁡
              
                (
                
                  r
                  y
                
                )
              
            
          
        
      
    
    
      
        (
        14
        )
      
    
  




The algorithm may compute the total utility achieved by the clique. The updates in the last iteration of the greedy choice may be discarded if the used bandwidth exceeds the available bandwidth of the whitespace (step 24). However, if the last iteration contributes to the utility more than the other iterations combined, then the bandwidth may be allocated to the greedy choice in the last iteration (step 28).
Algorithm two (BestNeighborhoodFirst) is based on spectrum allocation using general interference graphs. Pseudo-code for algorithm two is as follows:










Algorithm 2 BestNeighborhoodfirst: Greedy Algorithm for PF-WSA
















 1:
Let G denote the graph formed by the interference maps of each



 nodes. Initialize Gcand := G as the graph on which we will next



 perform greedy allocation of spectrum. At each step, Gcand only



 consists of AP's that are candidate for allocation.


 2:
while Gcand has at least one node do


 3:
 for all u ∈ Gcand do {Gcand denotes the interference graph in this



 WSj}


 4:
  Initialize TU(u), the total capacity attainable by the nodes



  in the neighborhood of u as TU(u) := 0.


 5:
  Let CNuj be the candidate neighbors for spectrum



  allocation. Initialize CNuj := Nuj ∩ {v:v belongsto Gcand}.


 6:
  while CNuj ≠ ∅ do


 7:
   for all v ∈ CNuj do


 8:
    Find nodes that belong to CNuj ∩ Nvj.


 9:
    Apply PfSpecAllocClique to CNuj ∩ Nvj to



    compute (i) the total capacity TU(u, v)



    attainable by the nodes in CNuj ∩ Nvj, and (ii)



    total bandwidth used TB(u, v) by these nodes.


10:
   end for


11:
   Find vm ∈ CNuj for which TC(u, v) is maximized, and



   assign spectrum according to PfSpecAllocClique.


12:
   Update TU(u) as



    TU(u) ← TU(u) + TU(u, vm).


13:
   Remove from CNuj nodes in CNuj ∩ Nvj, and also



   neighbors of CNuj ∩ Nvj (i.e., nodes that have a



   neighbor in CNuj ∩ Nvj)


14:
  end while


15:
 end for


16:
 Allocate spectrum to the node um in Gcand that has



 maximum TU(u), i.e.,


 



    



  
    u
    m
  
  =
  
    arg
    ⁢
    
      
        max
        
          uεNodesinG
          cand
        
      
      ⁢
      
        TU
        ⁡
        
          (
          u
          )
        
      
    
  






 


17:
 Let V be the set of nodes that get some spectrum in the previous



 step. Now, update Gcand by deleting all nodes in V and their



 neighbors.


18:
end while









Algorithm two has three distinct stages. Stage 1 is computing the total utility in the neighborhoods, stage 2 is allocating spectrum to the best neighborhood, and stage 3 is repetition of the steps associated with stage 1 and stage 2.
Stage 1: Computing the total utility in the neighborhoods: This is shown in one iteration of the for loop (step 3) because this step is repeated. This stage first computes the total system utility TU(u), ∀ u achievable by the neighborhoods of the different nodes. The following two sub-stages illustrate the computation for the neighborhood of u (steps 5-14):
Sub-stage 1A, for every node ν that is a neighbor of u, consider the set of nodes that are neighbors of both ν and u, for example, consider the set Nuj∩Nνj. Next, treat this set Nuj∩Nνj as a clique and use algorithm one (PfSpecAllocClique) to find the total attainable utility TU(u,ν). The algorithm then finds the node νm εNuj for which TU(u,ν) is maximum, and the corresponding TU(u, νm) is added to the existing value of TU(u).
Sub-stage 1B, remove the following nodes from consideration: the node νm, node νm's neighbors (that also belong to Nuj) that were allocated in the previous step, and neighbors of all nodes who were allocated. Step 1 is then repeated within the neighborhood of u, until all neighbors of u are exhausted.
Stage 2: Allocating spectrum to the best neighborhood: (as shown in step 16), find the node u for which TU(u) is maximum, for example, find the node um for which the neighborhood produces the maximum value of total utility. Actual spectrum allocation may then done to the nodes in Nuj in accordance with stage 1.
Stage 3: Repetition of the steps: All the nodes that get an allocation may be removed from consideration, their neighbors may also be removed (step 17). The algorithm repeats the first two stages on the new graph, and enters one more iteration of the for loop (step 3).
Pseudo-code for algorithm three (PfMultWSMultRadio) is as follows:










Algorithm 3 PfMultWSMultRadio: Prop. Fair Spectrum Allocation
















 1:
Initialize the bandwidth allocation. Denote by ril the data rate APi



gets in WSl, and Ri as the total data rate given to APi.


 



  



  
    
      r
      il
    
    :=
    0
  
  ,
  
    
  
  ⁢
  
    
      R
      i
    
    =
    
      
        ∑
        l
      
      ⁢
      
        
      
      ⁢
      
        r
        il
      
    
  






 


 2:
repeat


 3:
 for l = 1 to NWS do


 4:
  Compute, nil, the total data rate to APi in the ACI causing



  whitespaces of WSl as


 



   



  
    
      n
      il
    
    =
    
      
        ∑
        
          
            lsACI
            ≤
            j
            ≤
            rsACI
          
          ,
          
            j
            ≠
            l
          
        
      
      ⁢
      
        
      
      ⁢
      
        r
        ij
      
    
  
  ,






 



  where lsACI (rsACI) is the leftmost (rightmost) ACI causing



  whitespace of WSl.


 5:
  Define mil as the threshold above which data rate to APi is



  useful in WSl as follows:


 



   



  
    m
    il
  
  =
  
    {
    
      
        
          
            n
            il
          
        
        
          
            
              if
              ⁢
              
                
              
              ⁢
              
                n
                il
              
            
            ≠
            0
          
        
      
      
        
          0
        
        
          
            
              elseif
              ⁢
              
                
                
                  {
                  
                    l
                    :
                    
                      
                        r
                        il
                      
                      >
                      0
                    
                  
                  }
                
                
              
            
            <
            
              N
              rad
            
          
        
      
      
        
          
            
              min
              j
            
            
              r
              ij
            
          
        
        
          else
        
      
    
  






 


 6:
  Define the following log-utility for APi



   Ui(l)(xil) = di[log(1 + Ri − ril + (xil − mil)+) −



   log(1 + Ri − ril)] =


 



   



   
  
    
      d
      i
    
    ⁢
    
      
        log
        ⁡
        
          (
          
            1
            +
            
              
                
                  (
                  
                    
                      x
                      i
                    
                    -
                    
                      m
                      il
                    
                  
                  )
                
                +
              
              
                1
                +
                
                  R
                  i
                
                -
                
                  r
                  il
                
              
            
          
          )
        
      
      .
    
  






 


 7:
  Run BestNeighborFirst to maximize ΣiUi(l)(xil). Let TUl be



  the total utility as computed by BestNeighborFirst.


 8:
 end for


 9:
 Find the WS which gives the best improvement, i.e., find l* such



 that


 



   



  
    l
    *
  
  =
  
    arg
    ⁢
    
      
        max
        l
      
      ⁢
      
        
          [
          
            
              TU
              l
            
            +
            
              
                ∑
                i
              
              ⁢
              
                
              
              ⁢
              
                
                  d
                  i
                
                ⁢
                
                  log
                  ⁡
                  
                    (
                    
                      1
                      +
                      
                        R
                        i
                      
                      -
                      
                        r
                        il
                      
                    
                    )
                  
                
              
            
          
          ]
        
        .
      
    
  






 


10:
 Reallocate spectrum to WSl* according to spectrum allocation



 produced by running BestNeighborFirst for maximizing ΣiUi(l).


11:
 Perform the following sub-steps:



  11-1. For every AP, remove spectrum allocation from



     adjacent ACI-causing whitespaces of l*, if any.



  11-2. For every AP, if there was no allocation in the ACI-



     causing whitespaces, then remove spectrum



     allocation from the whitespace that provides Nradth



     least data rate to AP (this could be zero if less than



     Nrad radios have spectrum allocation).









12:
until the loop is executed Θ(NWS log(1/ε)) times










Allocation of spectrum with multiple whitespaces and multiple radios is different from the allocation of spectrum in a single whitespace and a single radio per access point 205 because, unlike in a single whitespace, with multiple whitespaces and multiple radios the access points 205 may be assigned Nrad distinct contiguous whitespaces so long as the spectrum bands allocated to an access point 205 respect an ACI constraint. Nevertheless, the algorithm for single whitespace may be used to develop an algorithm for the allocation of spectrum with multiple whitespaces and multiple radios.
A local search approach may be motivated by a so called generalized assignment problem (GAP). The maximum GAP is as follows: given bins and items, value of packing item-i in bin-j, and a packing constraint for each bin that only allows a certain subset of items for each bin, the GAP problem is to find an assignment that maximizes the total value of the packed items. For ease of explanation, the algorithm for the case when Wj≦Bm will be described, for example, when the whitespace widths are no more than the maximum bandwidth a radio can support. Further whitespace widths are no more than, for example, 30 MHz or 42 MHz for most large cities and Bm may be relatively larger than this (for example, Bm=40 MHz for latest GNU-radios).
If the width of some of the whitespaces is more than Bm, algorithm three first performs a pre-processing step that performs the following: (i) partitions the whitespaces with bandwidth more than Bm into segments of width Bm (except for the last segment) and treats each segment as a whitespace, and (ii) for each segment to be treated as a whitespace, algorithm three, shown above, finds the whitespace properties like center frequency, bandwidth, and data rate for the AP's per unit of bandwidth.
If Wj≦Bm for all j, spectrum allocation within a single whitespace may be no different from spectrum allocation in a single whitespace and single radio per access point 205 allocation as described above. Algorithm three starts by allocating no spectrum to any radio of any of the access points 205. Algorithm three includes three iterative stages. Stage 1 includes steps 3-8, stage 2 includes steps 9-11, and stage 3 includes steps 2-12 (iterative performance of stage 1 and stage 2). Algorithm three performs the following:
Stage 1, for each whitespace, compute the improvement that may result from reallocating spectrum in that whitespace alone. This step may be performed by using the spectrum allocation algorithm for single whitespace. Reallocating spectrum to an access point 205 in a whitespace WSl may result in violation of constraints, for example, ACI and the constraint that no AP can be allocated more than Nrad distinct bands of spectrum. Thus, allocating spectrum to an access point 205 in WSl may be feasible if the constraints are not violated. This may be achieved if spectrum reallocation in WSl is followed by a removal of the allocation, from the whitespaces, any allocations that violate any constraints. To this end, variable mil denoting the amount of data rate that may be deducted from current (e.g., at the end of the previous iteration) data rate to access point APi so that allocation in WSl to APi does not violate any constraints is defined.
The computation of mil is shown in step 4-5 of algorithm three. Essentially, in these steps, the reduction in data rate of APi is reduced so that allocation in WSl does not violate any constraints. Step 6 of algorithm three defines the objective functions that capture the relatively best reallocation to perform in WSl. Note that, if reallocation is performed in WSl, then first removing the current allocation in WSl is performed. If the current data rate to APi in WSl is ril and Ri=Σ1 ril, then an additional xil units of data rate to APi from reallocation in WSl results in a total data rate of Ri−ril+(xi−mil)+ to APi. The term (xil−mil)+ can be explained by the fact that, if xil<mil, then it is better to not perform reallocation in WSl. Therefore, the improvement (as compared to allocation left after removing the allocation in WSl from the previous iteration) in log utility of APi that can be had from the reallocation is:

Ui(l)(xil)=di[ log(1+Ri−ril+(xil−mil)+)−log(1+Ri−ril)]  (15)

Equation 15 may be used to explain step 6 of algorithm three. In the step 7 of algorithm three, use algorithm two to maximize ΣUi(l)(xil). The output of step 7 of algorithm three is the improvement that may result from the reallocation denoted TUl.
Stage 2, steps 9-11 of algorithm three find the whitespace where reallocation results in maximum improvement in the total utility, and then, does the reallocation in that whitespace. For the access points 205 that get this re-allocated spectrum, to prevent the constraints from being violated the data rates may be reduced appropriately (as described in above in step 1).
Stage 3, the iterative steps are repeated Θ(NWS log(1/ε)) times.
Access Point to Allocate Whitespace Spectrum
FIG. 3 illustrates an access point 205 according to example embodiments. Although only one access point 205 is described, it will be understood that each of the access points 205 include the described features. The access point 205 includes a beacon transmission and interference report module 305, an aggregate spectral efficiency report module 310, a client association engine 315 and a medium access control module 320. The general features of the access point 205 are described above. The beacon transmission and interference report module 305 is described in more detail below with regard to FIG. 4. The aggregate spectral efficiency report module 310 is described in more detail below with regard to FIG. 5.
The client association engine 315 and the medium access control module 320 are known to those skilled in the art. For example, the a client association engine 315 and the medium access control module 320 may use the processes described in IEEE 802.11b, IEEE 802.11g and WiMAX specifications to associate clients, grant access to clients and perform medium access functionality.
Methods for Allocating Whitespace Spectrum
FIG. 4 illustrates a method for reporting signal strength according to example embodiments. In step S405, the beacon transmission and interference report module 305 receives a request to make ambient interference measurements. The request may be received from, for example, the central controller 201. The request may include k MHz sub-bands to make ambient interference measurements in. The k MHz sub-bands may be determined by the central controller 201 as follows:

    
    
        1. if there are n frequency bands available, with the ith available spectrum ranging from fli to fhi, for example, the available spectrum bands may be represented by the set S={fli, fh1), (fl2, fh2), . . . , (fln, fhn)};
        2. F MHz is the band within which equation 11 holds with a high degree of accuracy (typically, for example, on the order of a few hundred MHz);
        3. the minimum amount of spectrum allocable to an access point 205 is k MHz, k<<F, k may be as small as, for example, 1 MHz, while F may be, for example, on the order of 100 MHz.
    
    


In step S410, the beacon transmission and interference report module 305 makes the ambient interference measurements. For example, the beacon transmission and interference report module 305 measures ambient interference over every k MHz width (the minimum allocable amount of spectrum to an access point 205). Ambient interference measurements may be, for example, power measurements or received signal strength indication (RSSI) measurements. In step S415, the beacon transmission and interference report module 305 reports the ambient interference measurements to, for example, the central controller 201.
In step S420, the beacon transmission and interference report module 305 receives a request to transmit a beacon signal over a control channel. For example, an access point 205 may be selected by the central controller 210 to transmit a beacon signal. The beacon signal may include a message. The central controller 210 requests the selected access point 205 to transmit the beacon signal. If the selected access point 205 is transmitting at a given time, then all other access points 205 may remain silent at the given time.
In step S425, the beacon transmission and interference report module 305 measures a signal strength of the beacon signal. For instance, continuing the example above, at the given time, all other access points 205 may measure the received signal strength from the selected transmitting access point 205. Measurements of the beacon may be, for example, power measurements or received signal strength indication (RSSI) measurements. The measurements may include average measurements or average interference values.
In step S430, the other access points 205 report the measurements to, for example, the central controller 201. In the alternative, the other access points 205 report the measurements to, for example, the selected access point 205, the selected access point in turn will report the measurements to the central controller 201. The other access points 205 may use the other access points' control channel to report the measurements or the other access points 205 may use a common control channel to report the measurements. The central controller 201 may use the measurements and the ambient interference measurements to generate an interference map as described above.
The aggregate spectral efficiency report module 310 may be configured to provide an aggregate demand which accounts for user demands and locations to the central controller 201. The aggregate spectral efficiency report module 310 may use the aggregate spectral efficiency (ASE) metric and equation 13 as developed above to determine the aggregate demand.
FIG. 5 illustrates a method for demand aggregation according to example embodiments. In step S505, the aggregate spectral efficiency report module 310 determines values associated with signal to interference noise ration (SINR). The SINR values may be determined using known methods and apparatus. For example, the aggregate spectral efficiency report module 310 may perform a regression test for discrete data rates versus SINR for the physical layer technology associated with the access point 205. The physical layer technology may be associated with the medium access control module 320.
In step S510, the aggregate spectral efficiency report module 310 determines technology variables associated with equation 12. For example, the aggregate spectral efficiency report module 310 may use the values associated with SINR determined in step S505 to determine a and b for equation 12. In step S515 the aggregate spectral efficiency report module 310 waits for new clients or users 210 to associate with the access point 205. Client/access point association is performed by the client association engine 315. Client/access point association methods are known to those skilled in the art and will not be discussed further. For example, IEEE 802.11 describes client/access point association methods in a WiFi system.
If in step S515 it is determined that a new client has associated with an access point 205, in step S520, the aggregate spectral efficiency report module 310 calculates ASE at the lowest frequency band f1 using, for example, equation 12. Alternatively, the aggregate spectral efficiency report module 310 may receive an ASE from each of the clients/users associated with the access point 205.
The aggregate spectral efficiency report module 310 may also calculate second ASE values associated with second frequencies for each of the clients/users using, for example, equation 13. The aggregate spectral efficiency report module 310 may also aggregates demands based on the ASE values at f1 and the second ASE values.
In step S525, the aggregate spectral efficiency report module 310 determines if the ASE at f1 has changed significantly. For example, the aggregate spectral efficiency report module 310 may have a stored threshold value associated with ASE change. If ASE at f1 has exceeded this threshold value, then ASE at f1 may be determined to have changed significantly. If ASE at f1 has not changed significantly, then control for the method returns to step S515.
If ASE at f1 has changed significantly, in step S530, the new ASE at f1 is sent to, for example, the central controller 201. The central controller 201 may use the ASE value to calculate an aggregate demand based on an ASE value for each of the access points 205 associated with the central controller 201. Alternatively, the aggregate spectral efficiency report module 310 sends an aggregated demand to, for example, the central controller 201.
FIG. 6 illustrates a method for allocating whitespace spectrum according to example embodiments. In step S605, the beacon transmission and interference report module 305 reports a signal strength of a beacon received by non-transmitting access points 205. For example, the beacon transmission and interference report module 305 may perform the method described above with regard to FIG. 4 to transmit, measure and report beacon signal characteristics.
In step S610, the aggregate spectral efficiency report module 310 aggregates a plurality of demands associated with each of a plurality of clients/users 205 to produce an aggregated demand. For example, the aggregate spectral efficiency report module 310 may perform the method described above with regard to FIG. 5 to aggregate client/user demand.
In step S615, the aggregate spectral efficiency report module 310 reports the aggregated demand to, for example, the central controller 201. For example, the aggregate spectral efficiency report module 310 may perform the method described above with regard to FIG. 5 to report the aggregate demand.
In step S620, the medium access control module 320 determines if the access point is to schedule clients/users based on client/user settings. If, in step S620, the medium access control module 320 determines that scheduling is based on client/user settings, in step S625, the medium access control module 320 schedules the client/user based on the client/user settings.
If, in step S620, the medium access control module 320 determines that scheduling is not based on client/user settings, in step S625, the medium access control module 320 schedules the client/user based on an allocation from the central controller 201.
The allocation from the central controller 201 may be, for example, based on the interference maps generated using the measurements and the ambient interference measurements reported by the beacon transmission and interference report module 305 as described above with regard to FIG. 4. The allocation from the central controller 201 may be, for example, further based on and the ASE value sent to the central controller 201 by the aggregate spectral efficiency report module 310 as described above with regard to FIG. 5.
Concurrently with the filing of the present application, the Applicants have filed A Method and Controller for Allocating Whitespace Spectrum Ser. No. 12/801,365, the entire contents of which is herein incorporated by reference.
The allocation from the central controller 201 may include, for example, a set of spectrum bands allocated to each access point 205 and possibly the set of clients 210 which should associate with each access point 205. The central controller 201 may compute an efficient allocation of the available whitespaces based on interference maps, ASEs, adjacent channel interference constraints, transmit power constraints, and demands.
The central controller 201 may use, for example, algorithm one described above and equations 13 and 14 to allocate whitespace spectrum. Alternatively, the central controller 201 may use, for example, algorithm two described above and equations 13 and 14 to allocate whitespace spectrum. Alternatively, the central controller 201 may use, for example, algorithm three described above and equations 13-15 to allocate whitespace spectrum.
As described above, each of algorithms one, two and three were developed to fairly and efficiently allocate spectrum bands associated with available whitespaces to a combination of access points 205 and clients or users 210. The central controller 201 may use either of the aforementioned algorithms to allocate whitespace spectrum. However, example embodiments are not limited thereto.
FIG. 7 is a signal flow diagram associated with allocation of whitespace frequency bands according example embodiments. Initially, the system is in a static condition, for example, a static number of clients 210 are on the system. During the static condition, access points 205 send beacons to clients 210 and RSSI values for other access points 205 over a control channel. The central controller 201 determines access point 205 neighbors associated with each whitespace.
If, for example, a new client initiates an associated request including a demand value and an RSSI value to at least one of the access points 205, the access points 205 send client demand values and aggregate RSSI values to the central controller 201.
The central controller 201 may then compute ASE values for each whitespace, and the central controller 201 may compute spectrum allocation. The central controller 201 then sends allocation messages to the access points 205. The access points 205 and the clients 210 then communicate data at a determined transmission power until a dissociation request is received by an access point.
While example embodiments have been particularly shown and described, it will be understood by one of ordinary skill in the art that variations in form and detail may be made therein without departing from the spirit and scope of the claims.

## Claims

1. An access point, comprising:
a first module configured to report a signal strength associated with each of a plurality of other access points to a central controller;
a second module configured to aggregate a plurality of demands to produce an aggregate demand, each of the plurality of demands associated with one of a plurality of users, and configured to report the aggregated demand to the central controller;
a third module configured to at least one of associate one of the plurality of users with the access point based on a user setting and associate one of the plurality of users based on allocation by the central controller, the allocation from the central controller being based on the reported signal strength and the aggregated demand, and the allocation indicating a frequency band from a set of frequency bands to be allocated by the access point to the user.

2. The access point of claim 1, comprising:
a plurality of transceivers, wherein
at least one of the plurality of transceivers is a common control channel transceiver,
the first module is configured to transmit a first message to the other access points via the common control channel,
the first module is configured to receive second messages from the other access points via the common control channel,
the first module is configured to report the signal strength via the common control channel,
the second module is configured to report the aggregated demand via the common control channel, and
the third module is configured to communicate access point and user associations via the common control channel.

3. The access point of claim 2, wherein the common control channel transceiver transmits at a frequency associated with the lowest operating spectrum.

4. The access point of claim 1, comprising:
a fourth module configured to grant access to the plurality of users and configured to provide a medium access mechanism between the access point and the plurality of users.

5. The access point of claim 4, wherein the medium access mechanism is one of IEEE 802.11b, IEEE 802.11g and WiMAX.

6. The access point of claim 1, wherein the reported signal strength includes a plurality of ambient interference values associated with a first frequency.

7. The access point of claim 1, wherein
the second module is configured to receive an average interference value from each of the plurality of users;
the second module is configured to receive a first aggregate spectral efficiency value associated with a first frequency from each of the plurality of users;
the second module is configured to calculate a plurality of second aggregate spectral efficiency values associated with a plurality of second frequencies for each of the plurality of users; and
the second module aggregates the plurality of demands based on the first aggregate spectral efficiency values and the second aggregate spectral efficiency values.

8. The access point of claim 7, wherein,
the first frequency is the lowest frequency in a band of the set of frequency bands; and
the first aggregate spectral efficiency values are based on,





  
    
      ASE
      ⁡
      
        (
        
          f
          ⁢
          
            
          
          ⁢
          1
        
        )
      
    
    =
    
      a
      +
      
        
          b
          N
        
        ⁢
        
          
            ∑
            
              k
              =
              1
            
            N
          
          ⁢
          
            
              SINR
              k
            
            ⁡
            
              (
              
                f
                ⁢
                
                  
                
                ⁢
                1
              
              )
            
          
        
      
    
  
  ,




where
ASE(f1) is the aggregate spectral efficiency value associated with the first frequency;
a and b are constants;
N is a number users;
k is the user for which the ASE is being calculated; and
SINR is a Signal to Interference-plus-Noise Ratio.

9. The access point of claim 7, wherein,
the second module calculates the second aggregate spectral efficiency values such that,


ASE(f1)−ASE(f2)=10 coeff log10(f2/f1), where


f1 is the first frequency;
f2 is one of the second frequencies;
coeff is an environment dependent parameter obtained through measurements;
ASE(f1) is the first aggregate spectral efficiency value received from one of the users; and
ASE(f2) is the second aggregate spectral efficiency value for the user at the second frequency f2.

10. A method for allocating a set of frequency bands associated with an access point, the method comprising:
reporting a signal strength associated with each of a plurality of other access points to a central controller;
aggregating a plurality of demands to produce an aggregate demand, each of the plurality of demands associated with one of a plurality of users;
reporting the aggregated demand to the central controller; and
at least one of associating one of the plurality of users with the access point based on a user setting and associating one of the plurality of users based on allocation by the central controller, the allocation from the central controller being based on the signal strength and the aggregated demand, and the allocation indicating a frequency band from the set of frequency bands to be allocated by the access point to the user.

11. The method of claim 10, comprising:
transmitting a first message to the plurality of other access points via a common control channel, the first message including a request for the signal strength; and
receiving a plurality of second messages from the other access points via the common control channel, the second messages including the signal strength; wherein
the signal strength is reported to the central controller via the common control channel.

12. The method of claim 10, comprising:
granting access to the plurality of users; and
providing a medium access mechanism between the access point and the plurality of users.

13. The method of claim 12, wherein the medium access mechanism is one of IEEE 802.11b, IEEE 802.11g and WiMAX.

14. The method of claim 10, wherein the reported signal strength includes a plurality of ambient interference values associated with a first frequency.

15. The method of claim 10, comprising:
receiving an average interference value from each of the plurality of users;
receiving a first aggregate spectral efficiency value associated with a first frequency from each of the plurality of users;
calculating a plurality of second aggregate spectral efficiency values associated with a plurality of second frequencies for each of the plurality of users; and
aggregating the plurality of demands based on the first aggregate spectral efficiency values and the second aggregate spectral efficiency values.

16. The method of claim 15, wherein,
the first frequency is the lowest frequency in a band of the set of frequency bands; and
the first aggregate spectral efficiency values are based on,





  
    
      ASE
      ⁡
      
        (
        
          f
          ⁢
          
            
          
          ⁢
          1
        
        )
      
    
    =
    
      a
      +
      
        
          b
          N
        
        ⁢
        
          
            ∑
            
              k
              =
              1
            
            N
          
          ⁢
          
            
              SINR
              k
            
            ⁡
            
              (
              
                f
                ⁢
                
                  
                
                ⁢
                1
              
              )
            
          
        
      
    
  
  ,




where
ASE(f1) is the aggregate spectral efficiency value associated with the first frequency;
a and b are constants;
N is a number users;
k is the user for which the ASE is being calculated; and
SINR is a Signal to Interference-plus-Noise Ratio.

17. The method of claim 15, wherein,
the second module calculates the second aggregate spectral efficiency values such that,


ASE(f1)−ASE(f2)=10 coeff log10(f2/f1), where


f1 is the first frequency;
f2 is one of the second frequencies;
coeff is an environment dependent parameter obtained through measurements;
ASE(f1) is the first aggregate spectral efficiency value received from one of the users; and
ASE(f2) is the second aggregate spectral efficiency value for the user at the second frequency f2.