Channel allocation in protected service areas

Abstract

In described embodiments, a channel allocation system, such as a white space (WS) channel allocation system, employs a method to populate a WS database with channel availability information for areas with protected or otherwise registered service user information server. Communication characteristics of incumbent service providers licensed or otherwise registered to operate within certain frequency spectrum are plotted over a geographic area. The channel allocation system then divides the area into tiles, and determines whether each tile can be characterized for channel availability and, for those tiles that are uncharacterized, further divides the tiles into tiles of finer resolution. Based on information in the WS database, availability of channels in areas is pre-computed, and then an iterative search of areas with successively finer resolution identifies white space channels that might be included in the channel list in response to a query from a unlicensed or unregistered user.

I claim: 
     
       1. A method of allocating communication channels within a geographic area having protected classes of service, the method comprising:
 generating, based on communications characteristics from storage, protected service contours over the geographic area for one or more of the protected classes of service; 
 partitioning a region over the geographic area into unclassified tiles at a first level of resolution; 
 classifying, by a processor, each unclassified tile, if able, for availability of channels with respect to each protected service contour of the region associated with the tile at the first level of resolution; and 
 if the corresponding unclassified tile is not classified,
 dividing each unclassified tile into nested tiles of one or more subsequent levels of finer resolution, and 
 forming nested, classified tiles of successive levels of resolution by classifying, if able, each tile at the subsequent level of finer resolution with respect to each protected service contour of the region associated with the corresponding tile at the subsequent level. 
 
 
     
     
       2. The method of allocating communication channels as recited in  claim 1 , wherein, if the corresponding unclassified tile is not classified, comprising:
 for each unclassified tile at a current level of resolution:
 (a) nested partitioning of the unclassified tile at the current level of resolution into tiles at a successive level of finer resolution; 
 (b) classifying, if able, each tile at the successive level of finer resolution based upon availability of channels with respect to each corresponding protected service contour of the region; 
 (c) further classifying, if able, each unclassified tile at the successive level of finer resolution with respect to each corresponding protected service contour of the region and at least one of an exclusive boundary and an inclusive boundary of the unclassified tile at the successive level of finer resolution; and 
 (d) repeating (a) through (c) at successive, finer levels of resolution until specifying channel availability of the region with nested, classified tiles of successive levels of resolution. 
 
 
     
     
       3. The method of  claim 1 , further comprising:
 receiving, from a device, a query having a location and one or more desired channels of operation corresponding to the query location; 
 identifying, beginning with the first level and searching successive levels of the nested, classified tiles of successive levels of resolution, a classified tile classified as available for the query location based on the one or more desired channels of operation; and 
 allocating channels, if available, associated with the identified, classified tile with the query location to a channel list. 
 
     
     
       4. The method of  claim 3 , further comprising transmitting the channel list to the device. 
     
     
       5. The method of  claim 4 , wherein for the transmitting of the channel list to the device, the device belongs to an unprotected class of service. 
     
     
       6. The method of  claim 4 , wherein for the transmitting of the channel list to the device, the device is at least one of i) a television band device (TVBD) of a white space channel allocation system and ii) a wireless handset of a femtocell communication system. 
     
     
       7. The method of  claim 4 , wherein for the transmitting of the channel list to the device, the device is a mobile device and the method further comprises transmitting channel lists for tiles adjacent to the identified, classified tile. 
     
     
       8. The method of  claim 7 , wherein for the transmitting of the channel list to the device, the identified, classified tile is a one arc-second tile and the method comprises transmitting channel lists for one arc-second tiles adjacent to the identified, classified tile. 
     
     
       9. The method of  claim 4 , further comprising registering a new protected service, and updating the nested, classified tiles of successive levels of resolution for one or more contours of the new protected service. 
     
     
       10. The method of  claim 9 , further comprising updating the channel list for the device, and transmitting the updated channel list to the device. 
     
     
       11. The method of  claim 3 , wherein the partitioning the region comprises translating geographic coordinates, and wherein the method further comprises
 forming an addressing scheme for the nested, classified tiles of successive levels of resolution based on the translated geographic coordinates; 
 associating the query location with a corresponding point in the translated geographic coordinates of the addressing scheme; and 
 searching the nested, classified tiles of successive levels of resolution based on the translated geographic coordinates of a point corresponding to the query location. 
 
     
     
       12. The method of  claim 1 , wherein the classifying each tile at a level of resolution comprises:
 verifying protected service requirements for a corresponding protected service contour; and 
 storing data, based on the verifying of the protected service requirements, of whether corresponding channels of the tile are available or unavailable. 
 
     
     
       13. The method of  claim 1 , wherein the classifying, if able, each unclassified tile at the subsequent level of finer resolution comprises:
 forming an exclusive boundary area for each exclusive boundary outside a perimeter of the tile, the exclusive boundary defined by a spacing distance; 
 verifying, for the exclusive boundary area, protected service requirements for each corresponding protected service contour; and 
 storing, based on the verifying of the protected service requirements for the exclusive boundary area, availability of corresponding channels of the tile. 
 
     
     
       14. The invention of  claim 13 , wherein, for the forming of the exclusive boundary area, each spacing distance corresponds to a protected distance from a non-protected service class transmitter. 
     
     
       15. The method of  claim 1 , wherein the classifying, if able, of each unclassified tile at the subsequent level of finer resolution comprises:
 forming an inclusive boundary area for each inclusive boundary inside a perimeter of the tile, the inclusive boundary defined by a corresponding spacing distance; 
 verifying, for the inclusive boundary area, protected service requirements for each corresponding protected service contour; and 
 storing, based on the verifying of the protected service requirements for the inclusive boundary area, availability of corresponding channels of the tile. 
 
     
     
       16. The method of  claim 15 , wherein, for the forming the inclusive boundary area, the corresponding spacing distance is a maximum spacing distance for an exclusive boundary. 
     
     
       17. The method of  claim 1 , wherein the generating the protected service contours comprises forming a protected area with a polygon. 
     
     
       18. The method of  claim 17 , wherein the forming the protected area comprises:
 defining the protected area by N geographic points from 0 to 359 degrees at M azimuths from 0 to 359 degrees from a center emitter, where N and M are positive integers; 
 connecting lines are drawn in a Cartesian plane of latitudes or longitudes between adjacent geographic points; 
 combining sample points with linear interpolation into a contour about the protected area over a surface area on an ellipsoidal (geodetic) model of the Earth's surface. 
 
     
     
       19. The method of  claim 17 , further comprising allocating white space communication channels to one or more unprotected classes of service, wherein the plurality of protected classes of service includes TV broadcast stations, and the one or more unprotected classes of service includes TV band devices (TVBDs). 
     
     
       20. The method of  claim 19 , wherein the allocating of white space communication channels comprises:
 receiving, from a TVBD, a query having a location and one or more desired channels of operation corresponding to the query location; 
 identifying, beginning with the first level and searching successive levels of the nested, classified tiles of successive levels of resolution, a classified tile classified as available with the query location based on the one or more desired channels of operation; 
 allocating, if available, white space channels associated with the identified, classified tile with the query location to channel list; and 
 transmitting the channel list to the TVBD. 
 
     
     
       21. The method of  claim 1 , wherein the partitioning the region comprises translating geographic coordinates, and wherein the method further comprises forming an addressing scheme for the nested, classified tiles of successive levels of resolution based on the translated geographic coordinates. 
     
     
       22. The method of  claim 1 , further comprising:
 receiving a message from a new protected service class device, the message including communication characteristics for the new protected service class device; 
 generating a new protected service contour based on the communication characteristics for the new protected service class device; and 
 updating the nested, classified tiles of successive levels of resolution based on the new protected service contour. 
 
     
     
       23. A machine-readable, non-transitory, storage medium, having encoded thereon program code, wherein, when the program code is executed by a machine, the machine implements a method for allocating communication channels within a geographic area having protected classes of service, comprising the steps of:
 generating, based on communications characteristics from storage, protected service contours over the geographic area for one or more of the protected classes of service; 
 partitioning a region over the geographic area into unclassified tiles at a first level of resolution; 
 classifying each unclassified tile, if able, for availability of channels with respect to each protected service contour of the region associated with the tile at the first level of resolution; and 
 if the corresponding unclassified tile is not classified,
 dividing each unclassified tile into nested tiles of one or more subsequent levels of finer resolution, and 
 forming nested, classified tiles of successive levels of resolution by classifying, if able, each tile at the subsequent level of finer resolution with respect to each protected service contour of the region associated with the corresponding tile at the subsequent level. 
 
 
     
     
       24. The machine-readable, non-transitory, storage medium as recited in  claim 23 , wherein, if the corresponding unclassified tile is not classified, comprising the steps of:
 for each unclassified tile at a current level of resolution:
 (a) nested partitioning of the unclassified tile at the current level of resolution into tiles at a successive level of finer resolution; 
 (b) classifying, if able, each tile at the successive level of finer resolution based upon availability of channels with respect to each corresponding protected service contour of the region; 
 (c) further classifying, if able, each unclassified tile at the successive level of finer resolution with respect to each corresponding protected service contour of the region and at least one of an exclusive boundary and an inclusive boundary of the unclassified tile at the successive level of finer resolution; and 
 (d) repeating (a) through (c) at successive, finer levels of resolution until specifying channel availability of the region with nested, classified tiles of successive levels of resolution. 
 
 
     
     
       25. Apparatus for allocating communication channels within a geographic area having protected classes of service, comprising:
 a database interface configured to retrieve communications characteristics for the plurality of protected classes of service from a database, the database further including i) communications characteristics for a plurality of protected classes of service, and ii) registration information for one or more devices belonging to one or more classes of unprotected service; 
 a processor configured to i) generate, based on communications characteristics from the database, protected service contours over the geographic area for one or more of the protected classes of service, ii) partition a region over the geographic area into unclassified tiles at a first level of resolution, and classify each unclassified tile, if able, for availability of channels with respect to each protected service contour of the region associated with the tile at the first level of resolution, 
 wherein, if the corresponding unclassified tile is not classified, the processor is further configured to:
 i) divide each unclassified tile into nested tiles of one or more subsequent levels of finer resolution, and 
 ii) form nested, classified tiles of successive levels of resolution by classifying, if able, each tile at the subsequent level of finer resolution with respect to each protected service contour of the region associated with the corresponding tile at the subsequent level; and 
 
 wherein the processor stores the nested, classified tiles of successive levels of resolution in the database. 
 
     
     
       26. The apparatus as recited in  claim 25 , wherein, if the corresponding unclassified tile is not classified, the processor, for each unclassified tile at a current level of resolution, is further configured to:
 (a) nested partition the unclassified tile at the current level of resolution into tiles at a successive level of finer resolution; 
 (b) classify, if able, each tile at the successive level of finer resolution based upon availability of channels with respect to each corresponding protected service contour of the region; 
 (c) further classify, if able, each unclassified tile at the successive level of finer resolution with respect to each corresponding protected service contour of the region and at least one of an exclusive boundary and an inclusive boundary of the unclassified tile at the successive level of finer resolution; and 
 (d) repeat (a) through (c) at successive, finer levels of resolution until specifying channel availability of the region with nested, classified tiles of successive levels of resolution.