# Towards Collaborative and Dynamic Spectrum Sharing via Interpretation of Spectrum Access Policies
## 5 Policies
### Planner
#### 6.4.1 Transmission Opportunities  
While computing opportunities may seem to be a simple issue, the problem is that the number of possible opportunities may be quite large, especially for policies that comprise vast numbers of rules. One simplistic way to solve such a problem would be for the Controller to continuously generate requests (in a loop) in response to denies. This would lead to very many interactions between the Controller and the PE, which means it is clearly not a great solution from the point of view of the efficiency of the CRE. In our approach, the PE provides the Controller with an API for querying about transmission opportunities for any combination of location, time, frequency and power, under the currently active policy. In search for possibly readily available solutions, we reviewed a number of published algorithms. One of the algorithms that relatively well-matched the requirements is called the _BSP--Binary Space Partitions_ (cf. [18; 19]). The research on BSP led us to the concept of a _k-d_ tree (short for k-dimensional tree) [20], which is a space-partitioning data structure for organizing points in a k-dimensional space. The _k-d_ tree data structure is a special case of a binary space partitioning tree that is used for representation and search that use multidimensional search keys (e.g., range searches and nearest neighbor searches). We have also looked at the graph-theoretic concept called _boxicity_. In graph theory, boxicity is a graph invariant. \"The boxicity of a graph is the minimum dimension in which a given graph can be represented as an intersection graph of axis-parallel boxes\". In other words, \"there must exist a one-to-one correspondence between the vertices of the graph and a set of boxes, such that two boxes intersect if and only if there is an edge connecting the corresponding vertices\". Our conclusion here was that this concept is not directly applicable to our problem. Finally, we analyzed the _R-trees_[21] and _R*-trees_[22]. _R-tree_ data structures are used for indexing multi-dimensional information that can be represented in terms of coordinates, e.g., geographical coordinates, rectangles or polygons. _R*-trees_ are a variant of _R-trees_. _R*-trees_ may have a higher computational complexity in the construction step than standard _R-trees_. The additional computational cost is due to the need to reinsert the data. However, this cost is compensated by a better query performance. In our implementation, both policy rules and multi-criteria transmission requests are viewed as hyper-rectangles, which is a simplification assumption for hyperspaces, stemming from the fact that rules approximate geographical areas as rectangles as opposed to arbitrary polygons in a more general case. Edges in each hyper-rectangle dimension correspond to intervals along the geographical dimensions of longitude, latitude, elevation, the time interval, the frequency interval and the maximum transmission power. The problem of finding transmission opportunities for a given transmission request is then decomposed as:  
* Retrieve all rules for the currently active policy. * Discard the rules that representational hyperspaces do not intersect the hyperspace representing the query. * For each remaining rule, determine the rule intersection with the query and insert the resulting hyperspace into either one of two lists, depending on the original rule type:
* the list of \"allow\" rule intersections. * the list of \"deny\" rule intersections. In an effort to remove potential overlapping sections of hyperspaces from the results, if so required, for each new candidate hyperspace intersection with the query, one can also extract the subset of previously inserted hyperspaces that intersect the candidate to insertion, determine the complements of the candidate with the existing ones and insert those complements into the list in lieu of the whole candidate.