Yasir Zaki
email: yzaki@comnets.uni-bremen.de

Manzoor Ahmed Khan
email: manzoor-ahmed.khan@dai-labor.de

Liang Zhao
email: zhaol@comnets.uni-bremen.de

Carmelita Görg

Realizing the Broker based Dynamic Spectrum Allocation through LTE Virtualization and Uniform Auctioning

Keywords: LTE, Wireless virtualization, Spectrum sharing, Uniform auctioning format

The next generation wireless networks are envisioned to follow the philosophy of buy when required, when it comes to the CApital EXpenditure(CAPEX) of operators over the infrastructure installation or extending new and dynamic resources. The dream of open market for new entrants and their coexistence with giant operators can be realized by the fancy concept of virtualization, which will be one of the key technologies in the future networks specially in the wireless part. Future virtualized mobile networks will comprise of a large number of (small) operators all competing for the spectrum resources. Such a scenario motivates and provisions the dynamic resource trading framework. This paper aims at presenting the realization concept of a dynamic spectrum trade market of future. We use the virtualized Long Term Evolution (LTE) as a realization framework for the proposed auctioned based dynamic spectrum sharing. We also investigate the profit function of spectrum broker and operators. We also study the realization of dynamic spectrum allocation on very small time instances (seconds) and investigate how the reservation price tunes the stake-holders' profit and resource allocation efficiency. The spectrum trade is based on the single auction multi-bid format and the paper further studies the impact of false bidding on the profit of spectrum broker (or network infrastructure provider).

Introduction

The scarce radio spectrum turns out to be the main pillar of the future wireless communications and spectrum management in any country is regulated by the a governmental body (e.g., FCC in USA or ECC in Europe). The current trend of spectrum allocation is derived by the concept of rigid frequency distribution through auctioning. Such allocations are static and specific to usage parameters (i.e., power, geographical scope etc.) and usage purposes (i.e., cellular communication, TV broadcasting, radio broadcasting etc.). Although auctions have been a success in this regard by putting essential spectrum in the hands of those who best value it and generating competition among the operators, such spectrum management may not cope up with the growing needs of spectrum with the user-centric network selection approach in place and the presence of various small scale new entrants e.g, MVNOs in the wireless market. We now briefly discuss the inefficiency introduced by the current fixed spectrum allocation market trends. The telecommunication operators bid for the amount of frequencies they are interested in, if declared winner, the bidding operators are allocated with some amount of frequencies for the periods spanning over years. This fact dictates that the operators frequency demands are the result of their peak traffic planning i.e., busy hour, which represents the peak network usage time. It should be noted that bandwidth demands are exposed to variation not only with respect to time (temporal variation) but also depends on the location (spatial variation). This, in a way addresses the issue of satisfying the operators' demands and reducing the call blocking at the operator end, however it causes temporal under-utilization in less busy periods. Hence the static spectrum allocation often leads to low spectrum utilization and results in fragmentation of the spectrum creating "white space" that cannot be used for either licensed or unlicensed services. The objective of improving spectrum utilization and providing more flexible spectrum management methods can be achieved by the currently well known concept, Dynamic Spectrum Allocation (DSA). DSA can significantly improve the spectrum utilization and provides a more flexible spectrum management method and promises much higher spectrum utilization efficiency. DSA concept brings a good news for the wireless service providers, as the flexible spectrum acquisition gives a particular provider the chance to easily adapt its system capacity to fit end users demand. In this paper, we confine our discussion more on dynamic spectrum allocation in user-centric paradigm, the interaction of stake-holders in the mentioned paradigm, and the technical realization framework for DSA. Obviously the operators' spectrum demand estimation turns out to be more more complicated in the mentioned configuration, we take care of this issue by carrying out number of simulations.

We take an opportunity here to justify the feasibility of dynamic spectrum allocation concept i.e., new generation radio interfaces support flexible transmission frequencies. The trend of future wireless technologies promises to ensure the user satisfaction for the envisioned dynamic bandwidth hungry service. e.g, Long Term Evolution (LTE) is expected to deliver five to ten times greater capacity than most current 3G networks with lower cost per bit. LTE also promises the flexible operational frequencies. Future wireless network communication is boosted by the concept of technology virtualization. When it comes to technical realization of the dynamic spectrum allocation concept, one of the attractive solutions is virtualization. Our choice of Virtualization as a technical solution is driven by the widespread and yet growing presence of this concept in the research literature e.g., many research projects including PlanetLab and GENI [START_REF] Bavier | Operating system support for planetary-scale network services[END_REF] [2] in the United States, AKARI [START_REF]AKARI architecture conceptual design for new generation network[END_REF] in Asia and 4WARD [START_REF] Bauck | Virtualisation as a co-existence tool in a future internet[END_REF] in Europe. We now briefly comment on the proposed realization concept i.e., virtualization framework. There is a number of research activities in virtualization as well as a number of commercial solutions using virtualization: e.g., Server Virtualization, Router Virtualization, XEN, Cloud Computing etc. It was evidently obvious that the next step is to try bringing virtualization into the network as a whole and to combine all of the different virtualization research activities into forming what is known as "Virtual Networks" or "VNets".

Wireless virtualization is yet another very important aspect specially for the future. The best candidate for applying virtualization in the wireless domain is mobile networks. Mobile networks are the fastest growing networks globally and one of the biggest players in the future. In [START_REF] Zaki | A Novel LTE Wireless Virtualization Framework[END_REF] it was shown that virtualization in mobile networks (represented by the Long Term Evolution (LTE)) has a number of advantages. Multiplexing gain as well as better overall resource utilization were the key gains achieved. In [START_REF] Zaki | LTE Wireless Virtualization and Spectrum Management[END_REF], a more practical framework was investigated for LTE virtualization and spectrum sharing among multiple virtual network operators. The framework focused on a contract based algorithm to share the spectrum between the operators.

Related Work

The concept of DSA first came up in the DARPA XG program [START_REF]DARPA Next Generation Communication Program[END_REF], the project aims to develop, integrate, and evaluate the technology. The emphasis is on the enabling the user equipment that automatically selects spectrum and operating modes to both minimize distruption of existing users, and to ensure operation of U.S. systems. In [START_REF] Milind | Dimsumnet: New directions in wireless networking using coordinated dynamic spectrum access[END_REF], the authors propose a spectrum broker model that controls and provides operators the time bound access to a spectrum band. The authors investigated spectrum allocation algorithms for spectrum allocation in homogeneous CDMA networks and executed spectrum measurements in order to study the realizable spectrum gain that can be achieved using DSA.

The authors in [START_REF] Rodriguez | Market-driven dynamic spectrum allocation: Optimal end-user pricing and admission control for cdma[END_REF] propose a scheme where the spectrum manager periodically allocates shortterm spectrum licenses. The spectrum rights are traded amongs the operators for a fixed amount of time, the license for the allocated spectrum automatically expires after the predefined time period. However, [START_REF] Rodriguez | Auction driven dynamic spectrum allocation: optimal bidding, pricing and service priorities for multi-rate, multi-class cdma[END_REF] assumes that the operators follow the multi-unit auction format for the spectrum trade, where the sealed bids are submitted for the spectrum resources and the winner operator pays the second highest price (the price of resource is assumed to be charged on per unit basis). In [START_REF] Subramanian | Near-optimal dynamic spectrum allocation in cellular networks[END_REF], the authors present bidding framework, where the spectrum manager / broker tries to maximize its revenue, moreover, the authors claim that the proposed bidding framework is equally suitable fro heterogeneous channel and general complementary bidding function. The paper also presents greedy algorithms with the approximation bounds to solve the NP-hard allocation problems. The authors in [START_REF] Yang | Physical interference driven dynamic spectrum management[END_REF] argue that the widely employed interference modeling (pairwise conflict graph) is weak and suggest the methods as to how to drive the interference model from the physical interference models so that it produces near-optimal allocation. Zheng et al. [START_REF] Zhou | ebay in the sky: strategy-proof wireless spectrum auctions[END_REF] use Vickery Clark Groves (VCG) format of auction to model the spectrum allocation problem. A deviation from the use of distributed approaches is observed in authors centralized auction based approach [START_REF] Sorabh | An economic framework for spectrum allocation and service pricing with competitive wireless service providers[END_REF], where authors assume pairwise interference conflict graph, piece-wise linear bidding functions, and homogeneous non-overlapping channels. Given these assumptions the authors authors formulate the allocation and pricing using the linear programming approach. Authors give the approximation bounds of the proposed heuristics and discuss the trade-off between revenue and fairness. They also argue on the difference between global market-clearing price and discriminatory pricing schemes. [15] relies on the VCG mechanism in a sealed-bid knapsack auction when determining spectrum allocation, but in the presented economic model the authors also account for the interaction between wireless service providers and users, and determine dynamic pricing rules to capture their conflict of interest. On the other hand they do not discuss interference issues.

Contribution

This work concentrates on analyzing more realistic dynamic spectrum resource trade in future market. We focus on technical realization of the mentioned market and investigate market efficiency for different strategies of operators and network infrastructure provider. We explicitly model the operator, network infrastructure provider utility functions, operators valuation function and discuss the market behavior for scenarios with varying reservation values and bidding strategies.We thoroughly study and implement the technical framework based on virtualization of LTE access networks.

Assumption

We assume that the environment consists of an infrastructure or spectrum broker and various mobile network operators. We further assume that network operators do not own their own infrastructure, rather the infrastructure is traded between network operators and network infrastructure provider on a need basis. The payment made against the traded resources are based on the "pay-as-you-go" format. In order to capture the demand specific to different services, we differentiate the network operators with respect to service types i.e., each is characterized by mutually exclusive service types. The network operators assess their demands and periodically acquire the resource from the resource providers. Upon the demand realization, the resource providers take decision over resource allocation and the price per unit resource that it charges for the extended or rented resource.

Spectrum (infrastructure) Resource Trading

We choose the uniform pricing auction to model the interaction at this stage, the motivation for choosing the mentioned auction format is the common use of this auctioning format in financial and other markets, which is evident by a large economic literature devoted to its study1 . It is also argued that to a large extent, the FCC spectrum auctions can be viewed as a uniform-price auction [START_REF] Cramton | The efficiency of the fcc spectrum auctions[END_REF]. In a uniform-price auction, small bidders can simply bid their valuations and be assured of paying only the market-clearing price [START_REF]Auction design issues for spectrum awards market analysis ltd[END_REF]. The fact highlighed in [START_REF] French | Spectrum auctions 101[END_REF] that in uniform price auctions the downstream playing field is level, in the sense that each licensee begins with the same foundational asset at the same price is also one of the motivating force to user the uniform price auctioning for spectrum trade. More on acution clearing algorithms can be found in [START_REF] Sandholm | Market clearability[END_REF]. In our formulation, the spectrum broker (virtualized LTE framework) is analogous to auctioneer, network operators are analogous to bidders, and the resource to be auctioned is analogous to auctioned-item. We assume that the auctioned-items are homogeneous and perfectly divisible. This assumption is strengthen by the fact that current trend of introducing flexibility in frequencies licensing i.e., providing operators with the technology neutral spectrum allocation. Let the distribution of auctioned item size has support in the range [X min , X max ], which defines the resource limits, where X min is a single PRB (Physical Resource Block) size and X max is the total capacity of the spectrum resource, hereafter we use C to represent the total resource capacity of the infrastructure provider. Let there are N symmetric risk-neutral bidders (operators) who compete by simultaneously submitting their non-increasing demand functions x i,k ∀i ∈ N , whereas the index k is illustrated later in this section. These bidders have independent private valuation function of the auctioned item, which is driven by the bidders' demand and the service types. Although the resource is homogeneous, the bidders have different valuations for different amount of the resource. Such valuation is strictly influenced and is the consequence of the service types for which the resource is required. We assume that the market comprises of demands of two service types namely Guaranteed service and Nonguaranteed, intuitively the former has more strict resource requirements when compared with the later. Let the ν i be the bidder private valuation of the auctioned item. Influenced by the comment given in the preceding sentence, the bidder valuation varies for demands of different service types, this is captured by the index k, thus the bidder valuation now can be represented by ν i,k such that ν i,k = ν i, k∀k = k. To illustrate this one has to consider the service demand patterns of the operators or putting it the other way operators spectrum valuation is driven by the operators' target market segment e.g., an operator targeting the fair users values the amount of spectrum demands for fair users more than the amount of spectrum for other user (service) types, the similar argument holds for vice versa. Thus the strategy for bidder i ∈ N is non-increasing function X i : [0, ∞) → [0, X max ], and the his private valuation ν i,k , which is the evaluated spectrum price by the operator, the details of computing such valuation is given later in this section. Thus the operator bid is given by b i,k,t = {x i,k , ν i,k }. It should be noted that the valuation is computed as price per unit of the spectrum. We assume that the market behavior is represented by equation-1, and we term this market as spectrum trade market hereafter. As can be see that the demand curve is linear that expresses the demand as a linear function of the unit price. The choice of this market behavior is influence by its simplicity and wide presence in the literature.

π(x) := -ζx + β, (1)
where ζ and β are positives, the negative gradient represents the sensitivity of market towards the price, and β represents the bound on price. π represents the price. We know that the gradient introduces the ealsticity in the curve. However, the proposed problem formulation dictates an inelastic spectrum demand behavior i.e., irrespective of how price may change the demand remains the same. This is represented by a perpendicular to the quantity axis in Fig 1 . Given such inelastic scenario, what about the operators' valuation computation? So far the valuation is the price value at the intersection of the demand perpendicular and normal negatively sloped (going down from left to right) linear demand curve. However, this does not capture the operator preference for different services.

To address this issue, we introduce the operator valuation function. Thus now the operator valuation corresponds to the intersection of operator valuation function slope and the demand perpendicular.

As depicted in Fig 1 , we map the operator demands over the spectrum trade market. The operator's the valuation function, given by Equation 2.

π i,k (x) = x i,k µ k (2)
where µ k tunes the operators' valuation for the given demand and the service type such that; if the service type is of higher importance to the operator µ k takes comparatively lower value than that of lower importance service. µ k further can be translated as the function of number of operators in the spectrum competition and demands of service type i.e., real time service has higher value than that of background or non-real-time values i.e., µ(k, N -1). Although one may come up with any suitable µ(.) function, in this work, we simply represent it by a real-value exposed to simple constraint of µ k,i = µ k,i ∀k = k and µ k,i = µ k, ĩ∀i = ĩ. Furthermore, it should be noted from the Fig 1 that the price given by the intersection of the deman perpendicular and the negative slope of market curve is the upper bound on the prices set by the regulatory body.

Observation In the problem under consideration, there are two interdependent markets; i) between operators and network infrastructure providers, termed as upstream market hereafter and ii) between operators and users, termed as downstream market hereafter. It should further be noted that downstream market demands (user service demands) influences the operator demands (operator resource demands). In this paper, the adopted methodology for estimating the downstream demands is based on the carried out simulation runs for all the virtual operators. In this connection we use the Exponential Moving Average (EMA) function to compute the estimated demands based on 20 seconds time intervals. Given the downstream demand, the upstream demand function can be computed.

Definition-1 -The operator valuation ν i,k is directly translated in to π i,k i.e., based on service types and downstream market demands the operator reflects its valuation as π i,k such that ν k,u = π i,k . Intuitively the false valuation πi,k is given by ν k,u = πi,k .

Let f be the mapping function that maps the downstream demands Y over the upstream demand function X, such that f (Y ) → X. For simplicity we assume that the mapping is bijective. Given the upstream demand function an operator computes its valuation of resource using Equation-2. Realizing the upstream demand and by Definition-1 the operator formulates its bid for the resource, which is given by b i (X, π).

Allocation Rule Given the uniform price auctioning format, let b represents the highest bid, and p represents the stop out price, then the allocation rule is given by:

a i (X i , b i ) :=      X i if b i,k = b ∧ X i ≤ C ∧ b i,k > p min{X i , C - b-i∈B, b-i\bi X b-i } otherwise (3)
As can be seen from Equation 3, the operator which is declared as the highest bidder gets the resources equivalent to its demands. In case the operator does not occupy the highest bidder position and resides in the winner list then it is allocated the residual resources not necessarily equivalent to its demands. The operator gets the residual demand when the infrastructure resource capacity is less than the operator demands(lower part of Equation-3). The resource allocated to each operator is independent of the auctioning format, however the payments do depend on the auction format.

Operator Utility Function As we know that operators have different valuation of different amounts (i.e., spectrum for k and k type services) of spectrum. However, the allocation rule dictates that operators are allocated according to their aggregated demand request. Thus the operator profit function involves both spectrum amounts of different operator valuation values. We define the operator utility function for resource allocation a i to operator i ∈ N and the stop-out price be p as:

u i (a, p) := (ν k -p)x k + (ν k -p)x k (4)
As can be seen that operator utility increases in its valuation and demands and decreases in stop-out price.

Auctioneer utility function

The profit function or utility function of auctioneer (LTE virtualition framework) is the function of bidder demands and stop-out price and is given by: u(

i∈N X i , p) := b∈B a b × (p - √ x λ
) where √ x λ represents the incurring cost of auctioneer, λ is the controller that enables the auctioneer to scale the cost that follows the operator specific deployment pattern (i.e., co-location, site rentals, tower rental etc.), the detail modeling of cost function (modeling operational and maintenance, deployment costs etc.) is out of the scope of this paper. However, the choice of square-root function to capture the operator cost function is influenced by the continuous nature of the function for all non-negative numbers and differentiable for all positive numbers, the function also capture the realistic nature of the operator cost i.e., the operator initially incure more cost on improving service and such cost decreases with increase in demands. Spectrum broker maximizes its utility i.e., max p u j ( i∈N X i , p), which increases in p and allocated resources and constrained by the operators' capacities. Thus the problem that the auctioneer solves is to decide the auction clearing or stop-out price and resource allocation (for allocation rule see Equation-3) i.e., p = sup p| i∈N

X i ≥ K (5)
We also present the algorithm that is implemented by the auctioneer to take the decision over resource allocation and stop-out price as follows: The proof is omitted due to space limitation.

Sequence of Actions

i) Each bidder observes the demands (based on EMA, mentioned earlier), ii) Infrastructure provider announces the start of auction time t init and duration of bid submission i.e., t init -t max , iii) Bidders submit their demands to the auctioneer at each per-unit price, which is the valuation of the bidder and attained from the Equation-2, iv) After the elapse of the submission time, the infrastructure provider observes the aggregated demand and sets the stop out price, which is equal or greater than the incurring cost over the unit resource. The auctioneer also decides each bidder's allocation, v)

The allocation is executed through the hypervisor, vi) The process iterates over i -iv, after the inter-auction time δt expires.

Dynamic Spectrum Trade Realization Framework

In this section, we present the LTE virtualization framework that we implement extensively to realize the proposed dynamic spectrum allocation concept. We virtualize the LTE network infrastructure (i.e., eNodeB, routers, ethernet links, and aGW etc.) so that multiple mobile network operators can create their own virtual network (depending on their requirements) on a common infrastructure. In the proposed virtualized network, we mainly foresee two different aspects; i) Physical infrastructure virtualization: virtualizing the LTE nodes and links and ii) Air interface virtualization: being able to virtualize the LTE spectrum. However, we in this paper focus on the later aspect, since virtualizing the air interface of the LTE system is a completely new concept and also the earlier aspect is extensively investigated in the research literature.

Air Interface Virtualization

The eNodeB is the entity responsible for accessing the radio channel and scheduling the air interface resources between the users. The eNodeB has to be virtualized so as to virtualize the LTE air interface. Virtualizing the eNodeB is similar to node virtualization. The physical resource of the node (e.g., CPU, memory, I/O devices ... etc.) are shared between multiple virtual instances. XEN [START_REF] Williams | Virtualization with Xen TM : Including XenEnterprise TM , XenServer TM , and XenExpress TM[END_REF] is a well known PC virtualization solution that insert a layer called "Hypervisor" on top of the physical hardware to schedule the resources. From that, our LTE virtualization framework follows the same principle. A hypervisor is added on top of the PHY layer of the eNodeB, it is responsible for virtualizing the eNodeB node as well as the spectrum. The proposed framework can be seen in Figure -2.

& BW estimation

Spectrum allocation Unit

Fig. 2: LTE eNodeB virtualization framework architecture

The architecture shows the physical eN-odeB virtualized into a number of virtual eN-odeBs. This is achieved by the hypervisor that sits on top of the physical resources of the eN-odeB. In addition, the hypervisor is responsible for scheduling the spectrum, i.e., scheduling the air interface resources (OFDMA sub-carriers) between the virtual eNodeBs running on top. In the framework architecture two new entities should be highlighted: the "Spectrum configuration and Bandwidth estimation" which is responsible for setting the spectrum the virtual eNodeB is supposed to operate in as well as estimating the required bandwidth of the operator. And the "Spectrum allocation unit" which is responsible for scheduling the spectrum among the different virtual eNodeBs. LTE uses OFDMA in the downlink, which means that the frequency band is divided into a number of sub-bands that are called Physical Resource Blocks (PRBs). A PRB is the smallest unit the LTE MAC scheduler can assign to a user. The Hypervisor schedule the PRBs between the different virtual operators, this process could be done by different mechanisms. In this paper, an auction based mechanism is used in the "Spectrum allocation unit" to auction the PRBs to the different virtual operators that bid for them.

Simulation Model and Results Analysis

The LTE virtualization simulation model is developed using OPNET [START_REF]OPNET website[END_REF] based on the 3GPP specifications. As explained earlier, the focus of the model is on the air interface virtualization and spectrum sharing between multiple virtual operators (all sharing the same eNodeB). Two scenarios are investigated based on the Auctioneer's (Infrastructure Provider) reserved price "'R". The reserved price is the minimum price the Auctioneer is willing to sell the resources with, and any bid with a price lower than the reserved one will be rejected. The first scenario is configured no reserved price (i.e., R = 0). The second scenario is configured with a dynamic reserved price that is a function of the total resources demand, this is calculated as follows: R = γ

• 3 i k x i,k
The rest of the configurations can be seen in Table 1.

Results and Analysis

The idea behind the simulations is to show how the uniform auctioning framework performs in a practical scenario, highlight some of the foreseen problems and how it can be solved. First, what happens if the infrastructure provider does not set any reserved price. Since the resources are homogeneous (in the perspective of the infrastructure provider) and they are soled by a uniform price determined by the lowest winner price, there is a possibility that the virtual operators try to exploit this by reducing their bidding prices in order to maximize their profit. This could be seen in Figure 3, where virtual operator 1 manipulates the price and maximizes his profit (blue curve of the figure). Since the infrastructure provider has no reserved price set in that scenario, the virtual operator succeeds in reducing the resource price and thus increasing his profit. On the other hand, in the 2nd Relative VO1 Profit Gain compared to VO1 2=2

Without R With R Fig. 3: Virtual Operator 1 profit and relative profit gain scenario (red curve of the figure) even though the virtual operator tries to manipulate his bidding price he is unable to increase his profit. This is because the infrastructure provider sets a reserved price that the operator can not bid below. Figure 4a shows the infrastructure provider profit. The profit decreases in the case with no reserved price due to the virtual operator's price manipulation, but when the infrastructure provider sets a reserved price he can stop the operator manipulation. Figure 4b and4c show the average profit of virtual operator 2 and 3. The results are similar to virtual operator 1 results. The average number of PRBs (spectrum utilization) for both the infrastructure provider as well as virtual operator 1 can be seen in Figure 4d. Similar trend as before can be observed, in the scenario with no reserved price the amount of resources is the same in all cases because the virtual operator gets all of his demand but with different prices. In the scenario with a reserved price it can be seen that the overall resources granted to the virtual operator starts decreasing, this is because when the virtual operator starts manipulating the bidding price he will not be granted his demand if the price is lower than the reserved one.

Conclusion

In this paper we discussed dynamic infrastructure resource auctioning in future wireless paradigm by focusing on both technical and theoretical aspects. We provide the technical realization of the proposed future market behaviour with the state-of-the-art technical solution on the granule level.

We have investigated how the uniform auctioning format performs when used to trade the spectrum between different virtual operators in a virtualized LTE system environment. Different scenarios were investigated, mainly what happens if the infrastructure provider does not set any reserved price and how the virtual operators can be stopped from manipulating the bids to maximize his profit. We tend to extend this work and investigate more on the potential economical and technical issues.

Fig. 1 :

 1 Fig. 1: figure representing the valuation of the operators for different services

Algorithm 1 Lemma 1 :

 11 Calculate p and a i Set t = 0 // Bids submissions start Ensure: bi ≥ R // Ensure that bids are equal or above the Reserve price (R) while t = tmax do B ← bi∀i ∈ N // Update the bid vector B for every income bid bi end while Determine the set of winning bids LIST B ← bi // The set of highest bids of B that do not violate the capacity constraint i∈N ai ≤ C SORT LIST B in ascending order. p← LIST B.bi(π) // select the price of lowest winning bidder as stop-out price. while C = 0 &&LIST B = empty do Ensure: bi ∈ B if C > bi(X) then B.Bi(a) = Xi else B.Bi(a) = Cr // Cr is the residual capacity end if end while In an homogeneous item uniform price auctions, the operators with multiple bids have a unique dominant strategy for each bid in different instances i.e., b i,t1 := ν i,t1,k and b i,t2 := min{R, ν i,t2, k}

  (non-GBR price valuation)

Fig. 4 :

 4 Fig. 4: Figure presenting the profit and relative profit results and virtual operator resources

Table 1 :

 1 Simulation configurations

	Parameter	Assumption
	Number of virtual operators	4 virtual operators with circular cells of 375 meters radius
	Total Number of PRBs (Spectrum) 75 PRBs, i.e., about 15 MHz
	Mobility model	Random Way Point (RWP) with vehicular speed (120 Km/h)
	Number of active users	VO1: 16 GBR (video users) and 4 non-GBR (FTP users)
	per virtual operator	VO2: 10 GBR (video users) and 10 non-GBR (FTP users)
		VO3: 4 GBR (video users) and 16 non-GBR (FTP users)
	VO1 price valuation	γ1=2 and γ2=(2, 4, 6, 8, 10 and 20)
	VO2 price valuation	γ1=2 and γ2=4
	VO3 price valuation	γ1=2 and γ2=2
	Video traffic model	24 frames per second with frame size = 1562 Bytes
		Video call duration = Exponential with 60 seconds mean
		Inter video call time = Poison with 30 seconds mean
	FTP traffic model	FTP file size = 8M bytes
		Inter request time = uniform between 50 and 75 seconds
	Auctioning parameters	Auction done every 20 seconds with γ = 0.25
	Simulation runtime	1000 seconds

Ofcom, Award of available spectrum: 1781.7-1785 MHz paired with 1876.7-1880 MHz: A Consultation, 16 September


Miguel López-Benítez

Fernando Casadevall

An Overview of Spectrum Occupancy Models for Cognitive Radio Networks

Keywords: cognitive radio, dynamic spectrum access, spectrum characterization, spectrum occupancy modeling

The Dynamic Spectrum Access (DSA) paradigm based on the Cognitive Radio (CR) technology has emerged as a promising solution to conciliate the existing conflicts between spectrum demand growth and current spectrum underutilization without changes to the existing legacy wireless systems. The basic underlying idea of DSA/CR is to allow unlicensed users to access in an opportunistic and non-interfering manner some licensed bands temporarily unused by the licensed users. Due to the opportunistic nature of the DSA/CR paradigm, a realistic and accurate modeling of spectrum occupancy patterns becomes essential in the domain of DSA/CR research. In this context, this paper provides an overview of the existing spectrum occupancy models recently proposed in the literature to characterize the spectrum usage patterns of licensed systems in the time, frequency and space dimensions.

Introduction

Wireless communication systems have been exploited since the early days of radio communications under a fixed spectrum management policy. Portions of the spectrum separated by guard bands have been allocated to particular licensees over large geographical regions, on a long term basis, and under exclusive exploitation licenses. Under this static regulatory regime, the overwhelming proliferation of new operators, services and wireless technologies has resulted in the depletion of spectrum bands with commercially attractive radio propagation characteristics. As a result, the Dynamic Spectrum Access (DSA) paradigm based on the Cognitive Radio (CR) technology [START_REF] Akyildiz | NeXt generation/dynamic spectrum access/cognitive radio wireless networks: a survey[END_REF] has gained popularity, motivated by the currently inefficient utilization of spectrum already demonstrated by many spectrum measurement campaigns performed all around the world [START_REF] Chiang | A quantitative analysis of spectral occupancy measurements for cognitive radio[END_REF][START_REF] Islam | Spectrum survey in Singapore: Occupancy measurements and analyses[END_REF][START_REF] López-Benítez | Spectral occupation measurements and blind standard recognition sensor for cognitive radio networks[END_REF][START_REF] Mchenry | Spectrum occupancy measurements[END_REF][START_REF] Petrin | Analysis and comparison of spectrum measurements performed in urban and rural areas to determine the total amount of spectrum usage[END_REF][START_REF] Schiphorst | Evaluation of spectrum occupancy in Amsterdam using mobile monitoring vehicles[END_REF][START_REF] Wellens | Evaluation of spectrum occupancy in indoor and outdoor scenario in the context of cognitive radio[END_REF]. The basic underlying principle of DSA/CR is to allow unlicensed users to access in an opportunistic and non-interfering manner some licensed bands temporarily unoccupied by licensed users. Unlicensed (secondary) DSA/CR terminals monitor the spectrum in order to detect spectrum gaps left unused by licensed (primary) users and opportunistically transmit. Secondary unlicensed transmissions are allowed according to this operating principle as long as they do not result in harmful interference to the licensees.

As a result of the opportunistic nature of the DSA/CR principle, the behavior and performance of a network of DSA/CR nodes depends on the primary spectrum occupancy pattern. Realistically and accurately modeling such patterns becomes therefore essential and extremely useful in the domain of DSA/CR research. Models of spectrum use can find applications in a wide variety of fields, ranging from analytical studies to the design, dimensioning and performance evaluation of secondary networks, including the development of innovative simulation tools as well as novel DSA/CR techniques. This paper provides a brief overview of some spectrum occupancy models recently proposed in the literature in the context of DSA/CR research in order to capture and reproduce the statistical properties of spectrum usage. The existing models can be categorized into time-, frequency-and space-dimension models, each of which describe the statistical properties of spectrum usage in the corresponding domain. Based on this classification, this paper reviews some existing modeling approaches and analyzes their merits and limitations.

Time-dimension models

From the point of view of DSA/CR, spectrum usage can adequately be modeled by means of a two-state Markov chain, with one state indicating that the channel is busy and therefore not available for opportunistic access and the other one indicating that the channel is idle and thus available for secondary use. Although some alternative modeling approaches have been proposed in the literature [START_REF] Ghosh | A framework for statistical wireless spectrum occupancy modeling[END_REF], the two-state Markov chain is the most widely employed time-dimension model in DSA/CR research. This binary channel model can be employed to describe the occupancy pattern of a licensed channel in discrete and continuous time.

Discrete-time models

In the two-state Discrete-Time Markov Chain (DTMC) model the time index set is discrete. According to this, the channel remains in a given state at each step, with the state changing randomly between steps. The behavior of the DTMC channel model can be described by means of the set of transition probabilities between states (see Figure 1), which can be expressed in matrix form as:

P = p 00 p 01 p 10 p 11 (1)
where p ij represents the probability that the system transitions from state s i to state s j . Note that the DTMC channel model in [START_REF] Akyildiz | NeXt generation/dynamic spectrum access/cognitive radio wireless networks: a survey[END_REF], commonly used in the literature, assumes a stationary (time-homogeneous) DTMC, where the transition matrix P is constant and independent of the time instant. The mean occupancy level of a channel is certainly a straightforward metric and an accurate reproduction is a minimum requisite for any time-dimension spectrum occupancy model. The average occupancy of a channel can be expressed in terms of the Duty Cycle (DC), henceforth denoted as Ψ . The DC of a channel can be defined as the probability (or fraction of time) that the channel is busy (i.e., resides in the busy state in the long term), which for the DTMC model of Figure 1 is given by Ψ = p 01 /(p 01 + p 10 ). The stationary DTMC model of (1) can therefore be configured to reproduce any arbitrary Ψ by selecting the transition probabilities as p 01 = p 11 = Ψ and p 10 = p 00 = 1 -Ψ , which yields:

P = 1 -Ψ Ψ 1 -Ψ Ψ (2)
Nevertheless, reproducing not only the mean DC but also the lengths of the busy and idle periods is an important feature of a realistic time-domain model for spectrum use. The stationary DTMC model has been proven to not be able to reproduce the statistical properties of busy and idle period lengths of real channels [START_REF] López-Benítez | Discrete-time spectrum occupancy model based on markov chain and duty cycle models[END_REF]. This limitation, however, can be overcome by means of a nonstationary (time-inhomogeneous) DTMC channel model with a time-dependent transition matrix:

P(t) = 1 -Ψ (t) Ψ (t) 1 -Ψ (t) Ψ (t) (3)
In the stationary case of (2), Ψ represents a constant parameter. However, in the non-stationary case of (3), Ψ (t) represents a time-dependent function that needs to be characterized in order to characterize the DTMC channel model in the time domain. The development of mathematical models for Ψ (t) may be relatively simple for primary systems where occupancy patterns are characterized by a strong deterministic component. This is for example the case of cellular mobile communication systems, which exhibit a periodic load variation pattern on a daily basis (see Figure 2). Adequate models for such deterministic patterns have been developed in [START_REF] López-Benítez | Discrete-time spectrum occupancy model based on markov chain and duty cycle models[END_REF]. In general, however, the traffic load supported by a radio channel is normally the consequence of a significant number of random factors such as the number of incoming and outgoing users and the resource management policies employed in the system. As a result, the channel usage level is itself a random variable that may more appropriately be characterized from a stochastic modeling perspective, which still constitutes an open issue.

Continuous-time models

Another popular model in the DSA/CR literature is the two-state Continuous-Time Markov Chain (CTMC) model, where the channel remains in one state for a random time period before switching to the other state. The state holding time or sojourn time is modeled as an exponentially distributed random variable. Some works based on empirical measurements [START_REF] Geirhofer | Dynamic spectrum access in WLAN channels: Empirical model and its stochastic analysis[END_REF][START_REF] Geirhofer | Dynamic spectrum access in the time domain: Modeling and exploiting white space[END_REF][START_REF] Stabellini | Quantifying and modeling spectrum opportunities in a real wireless environment[END_REF][START_REF] Wellens | Empirical time and frequency domain models of spectrum use[END_REF] have demonstrated, however, that state holding times do not follow exponential distributions in practice. In particular, it has been found that state holding times are more adequately described by means of generalized Pareto [START_REF] Geirhofer | A measurement-based model for dynamic spectrum access in WLAN channels[END_REF], a mixture of uniform and generalized Pareto [START_REF] Geirhofer | Dynamic spectrum access in WLAN channels: Empirical model and its stochastic analysis[END_REF][START_REF] Geirhofer | Dynamic spectrum access in the time domain: Modeling and exploiting white space[END_REF], hyper-Erlang [START_REF] Geirhofer | Dynamic spectrum access in WLAN channels: Empirical model and its stochastic analysis[END_REF][START_REF] Geirhofer | Dynamic spectrum access in the time domain: Modeling and exploiting white space[END_REF], generalized Pareto and hyperexponential [START_REF] Stabellini | Quantifying and modeling spectrum opportunities in a real wireless environment[END_REF], as well as geometric and log-normal [START_REF] Wellens | Empirical time and frequency domain models of spectrum use[END_REF] distributions. Based on these results, a more convenient model is therefore the Continuous-Time Semi-Markov Chain (CTSMC) model, where the state holding times can follow any arbitrary distributions. Appropriate parameters for the aforementioned distributions have been derived from field measurements performed with high time-resolution [START_REF] Geirhofer | Dynamic spectrum access in WLAN channels: Empirical model and its stochastic analysis[END_REF][START_REF] Geirhofer | Dynamic spectrum access in the time domain: Modeling and exploiting white space[END_REF][START_REF] Stabellini | Quantifying and modeling spectrum opportunities in a real wireless environment[END_REF] and low time-resolution [START_REF] Wellens | Empirical time and frequency domain models of spectrum use[END_REF] measurement equipment, and for various radio technologies of practical relevance.

It is worth noting that the CTSMC channel model provides an explicit means to characterize and reproduce the lengths of the busy and idle periods, which implicitly offers the possibility to reproduce any arbitrary DC by appropriately selecting the parameters of the sojourn time distributions in order to provide mean values E{T i } such that:

Ψ = E{T 1 } E{T 0 } + E{T 1 } ( 4
)
where E{T 0 } and E{T 1 } represent the mean sojourn times in the idle and busy states (i.e., mean idle and busy period duration), respectively.

Time-correlation models

The DTMC (with appropriate DC models) and CTSMC channel models are capable to capture and reproduce the mean channel occupancy and the statistical distributions of busy and idle periods observed in real channels. Nevertheless, previous studies [START_REF] López-Benítez | Modeling and simulation of time-correlation properties of spectrum use in cognitive radio[END_REF][START_REF] Wellens | Empirical time and frequency domain models of spectrum use[END_REF] have indicated that in some cases the lengths of the busy and idle periods can be correlated, a feature that the DTMC and CTSMC models cannot reproduce. Although in general high correlation levels are not observed in practice, an accurate and realistic model of spectrum usage should take this feature into account.

Experimental studies [START_REF] López-Benítez | Modeling and simulation of time-correlation properties of spectrum use in cognitive radio[END_REF] have shown that the lengths of busy and idle periods exhibit negative correlation coefficients, meaning that when the length of a busy period increases, the length of the next idle period tends to decrease and vice versa. This can be explained by the fact that when the channel load increases, then the fraction of time that it remains in use increases and, as a result, the duration of busy periods increases while idle periods become shorter. On the other hand, the opposite behavior is observed when the channel load decreases (i.e., the length of busy periods decreases and idle periods become longer). The correlation between the sequence of periods of the same type (either busy or idle) of a channel and a shifted version of itself (i.e., the autocorrelation) has experimentally been observed to exhibit two different behaviors, namely one periodic and another non-periodic. This is illustrated in Figure 3, which shows some examples of the autocorrelation function of idle periods as a function of the lag number, m, based on the Spearman's rank correlation coefficient, which is denoted as ρ s (T 0 , T 0 ; m).

For channels with periodic autocorrelation functions (see Figure 3(a)) with period M , the correlation coefficient can be expressed as the summation of two bell-shaped exponential terms centered at lags m = 1 and m = M + 1, with amplitudes A and widths σ:

ρ s (T i , T i ; m) = 1, m = 0 ρ min s + Ae -( m-1 σ ) 2 + Ae m-M -1 σ ) 2 , 1 ≤ m ≤ M (5)
where ρ min s is the minimum correlation. Based on field measurements, it has empirically been observed that ρ min s ≈ -0.1 in most cases, A ∈ [0.2, 0.5], M corresponds to the average number of lags equivalent to 24 hours, and σ ≈ M/4.

For channels with non-periodic autocorrelation functions (see Figure 3(b)), the correlation coefficient takes its maximum value ρ max s at m = 1 and decreases linearly with m until m = M , beyond which the correlation is approximately zero. This behavior can adequately be modeled as:

ρ s (T i , T i ; m) = ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ 1, m = 0 ρ max s M -m M -1 , 1 ≤ m ≤ M 0, m > M (6)
In this case, it has been observed that ρ max s ∈ [0.1, 0.4] and M ∈ [2000, 8000]. As it can clearly be appreciated in Figure 3, the models of ( 5) and ( 6) are able to accurately describe the time-domain autocorrelation properties of spectrum usage empirically observed in real systems. To reproduce time correlations, a simulation approach based on the aggregation and superposition of the realizations of several CTSMC processes has been proposed in [START_REF] Wellens | Modelling primary system activity in dynamic spectrum access networks by aggregated ON/OFF-processes[END_REF]. The main limitation of such proposal is that the resulting correlations depend on the number of aggregated processes as well as their distributions, and the distribution parameters as well as the number of processes to be aggregated in order to reproduce a particular correlation level cannot easily be determined, making necessary the use of simulations to this end, which complicates the configuration of the model and hence its application. An alternative approach based on random variate generation principles has been proposed in [START_REF] López-Benítez | Modeling and simulation of time-correlation properties of spectrum use in cognitive radio[END_REF]. Such another proposal requires as input information the particular distributions of idle and busy periods to be reproduced, the desired correlation coefficient between busy/idle periods as well as the desired autocorrelation function (periodic or non-periodic) of idle or busy periods. The algorithm outputs sequences of busy/idle period durations satisfying the desired specifications.

Frequency-dimension models

The previous section has reviewed existing models to describe the statistical properties of spectrum occupancy patterns on individual channels. Such modeling approaches can be extended by considering as a whole the channels belonging to the same allocated band and introducing additional models to describe the statistical properties of spectrum usage in the frequency dimension.

In the spectral domain, one of the simplest but probably most relevant aspects to be captured and reproduced is the statistical distribution of the channel occupancy levels. The DCs of individual channels belonging to the same band have been shown to follow a beta distribution [START_REF] Wellens | Lessons learned from an extensive spectrum occupancy measurement campaign and a stochastic duty cycle model[END_REF], whose density function is:

f B x (x; α, β) = 1 B(α, β) x α-1 (1 -x) β-1 , x ∈ (0, 1) (7)
where α > 0 and β > 0 are shape parameters and B(α, β) is the beta function.

Alternatively, the Kumaraswamy distribution can be used as well: where a > 0 and b > 0 are shape parameters. The Kumaraswamy distribution is similar to the beta distribution, but easier to use in analytical studies due to the simpler form of its density function. Figure 4 shows some examples of empirical DC distributions and their corresponding beta and Kumaraswamy fits.

f K x (x; a, b) = abx a-1 (1 -x a ) b-1 , x ∈ (0, 1) (8)
Both distributions can be configured to reproduce any arbitrary mean DC over the whole band, Ψ , by properly selecting the shape parameters:

Ψ = α α + β = bB 1 + 1 a , b (9)

Space-dimension models

While time-and frequency-dimension models are intended to reproduce the statistical properties of real spectrum occupancy patterns of primary transmitters, space-dimension models in general deal with the characterization of spectrum occupancy patterns as perceived by the DSA/CR users at various locations. Spectrum occupancy in the space domain is analyzed and characterized in [START_REF] Wellens | Spatial statistics and models of spectrum use[END_REF] in terms of the spatial distribution of the Power Spectral Density (PSD) by means of spatial statistics and random fields. Concretely, a semivariogram analytical model is fitted to average PSD values obtained at various locations by means of field measurements (empirical model) and simulation tools (deterministic model). The resulting PSD values can be mapped to binary busy/idle perceptions at various locations by means of a thresholding technique.

An alternative probabilistic modeling approach has been developed in [START_REF] López-Benítez | Spatial duty cycle model for cognitive radio[END_REF][START_REF] López-Benítez | Statistical prediction of spectrum occupancy perception in dynamic spectrum access networks[END_REF], which is illustrated in Figure 5. In the first step, a radio propagation model is used to estimate, based on a set of input parameters p = (p 1 , p 2 , . . . , p M ) such as operating frequency, distance, etc., the radio propagation loss L between the primary transmitter and the DSA/CR user. Based on the primary transmission power P T , the computed losses L are then employed to compute the primary power P S that would be observed by DSA/CR nodes at various locations, which are translated to SNR values γ based on the receiver's noise power P N . The resulting SNR values are then fed, along with an additional set of input parameters p = (p 1 , p 2 , . . . , p N ), to a DC model, which outputs an estimation Ψ of the DC that would be perceived at the considered geographical locations [START_REF] López-Benítez | Spatial duty cycle model for cognitive radio[END_REF]:

Ψ = 1 - K k=1 α k P fa + K k=1 α k Q Q -1 (P fa ) σ N -γ k σ S k ( 10
)
where K > 0 represents the number of transmission power levels that may be present in the channel, 0 < α k ≤ 1 is the activity factor of the k-th power level, P fa is the target probability of false alarm of the DSA/CR network, γ k (dB) = P S k (dBm) -P N (dBm) is the SNR resulting from the k-th average transmission power level, and σ S k , σ N are the standard deviation of the k-th signal and noise power levels respectively. These parameters constitute the input vector p . Figure 6 shows an example of the spectrum occupancy perceived by DSA/CR users at various locations in a realistic urban environment at the ground level between buildings, inside buildings and at rooftops [START_REF] López-Benítez | Statistical prediction of spectrum occupancy perception in dynamic spectrum access networks[END_REF]. While PSD/power modeling methods combined with thresholding techniques provide a simple binary characterization of the spatial spectrum occupancy perception (Figure 6(a)), the approach depicted in Figure 5 provides a more sophisticated characterization (Figure 6(b)) by means of the probability that the spectrum is observed as busy depending on the specific DSA/CR user location, the considered scenario and the surrounding radio propagation environment.

Conclusions

The development of the DSA/CR technology can significantly benefit from accurate and practical spectrum usage models. The purpose of such models is to provide a tractable, yet realistic representation of the statistical properties of spectrum usage in real systems that can adequately be employed in analytical studies or implemented in simulation tools for the performance evaluation of DSA/CR techniques. In this context, this paper has provided an overview of spectrum occupancy models recently proposed in the literature in the context of DSA/CR. The existing models can be broadly categorized into time-, frequencyand space-dimension models. Based on this classification, this paper has reviewed various modeling approaches, pointing out their advantages and shortcomings.

10 Fig. 1 .

 101 Fig. 1. Discrete-Time Markov Chain (DTMC) model.

Fig. 2 .

 2 Fig. 2. Empirical DC time evolution and corresponding deterministic model for: (a) DCS 1800 low/medium-load channel, (b) E-GSM 900 medium/high-load channel.

Fig. 3 .

 3 Fig. 3. Spearman's rank autocorrelation function of idle periods for: (a) periodic pattern, (b) non-periodic pattern.

Fig. 4 .

 4 Fig. 4. Empirical DC distributions and corresponding beta and Kumaraswamy fits.

Fig. 5 .

 5 Fig.5. Spatial spectrum occupancy modeling approach[START_REF] López-Benítez | Spatial duty cycle model for cognitive radio[END_REF][START_REF] López-Benítez | Statistical prediction of spectrum occupancy perception in dynamic spectrum access networks[END_REF].

Fig. 6 .

 6 Fig.6. Characterization of spatial spectrum occupancy perception at various locations in a realistic urban environment: (a) in terms of binary busy (white)/idle (gray) observations, (b) in terms of the probability to observe spectrum as busy.

Acknowledgments

This work was supported by the European Commission in the framework of the FP7 FARAMIR Project (Ref. ICT-248351) and the Spanish Research Council under research project ARCO (Ref. TEC2010-15198). The support from the Spanish Ministry of Science and Innovation (MICINN) under FPU grant AP2006-848 is hereby acknowledged.


Boris Oklander
email: oklander@tx.technion.ac.il

Moshe Sidi

Cross-Entropy Optimized Cognitive Radio Policies 1

Keywords: cognitive radio networks, dynamic spectrum access, state estimation, queueing analysis, cross-entropy

In this paper we consider cognitive processes and their impact on the performance of cognitive radio networks (CRN). We model the cognition cycle, during which cognitive radio (CR) sequentially senses and estimates the environment state, makes decisions in order to optimize certain objectives and then acts. Model-based analysis of CRN is used to solve control and decision making tasks, which actually gives the radio its "cognitive" ability. Particularly, we design an efficient strategy for accessing the vacant spectrum bands and managing the transmission-sampling trade-off. In order to cope with the high complexity of this problem the policy search uses the stochastic optimization method of cross-entropy. The developed model represents CRN ability to intelligently react to the network's state changes and gives a good understanding of the cross-entropy optimized policies.

Introduction

CRN are expected to cope with a wide spectrum of challenges arising in the face of the growing demand for wireless access in voice, video, multi-media and other high rate data applications. Although researchers and standardization bodies agree that CR should sense the environment and autonomously adapt to changing operating conditions, there are different views concerning the levels of cognitive functionality [START_REF] Zhao | Performance Evaluation of Cognitive Radios: Metrics, Utility Functions and Methodologies[END_REF]. This functionality of CRN can be represented by the cognition cycle [START_REF] Mitola | Cognitive radio: Making software radios more personal[END_REF].

Cognition cycle is the main control process that enables CR to stay aware of its communication environment and to adapt to its changing conditions. There are different views of what phases the cognition cycle consists [START_REF] Mitola | Cognitive radio: Making software radios more personal[END_REF], [START_REF] Haykin | Cognitive radio: brain-empowered wireless communications[END_REF], but basically all the versions share the observation, orientation, decision and action (OODA) phases. During the observation phase, CR continuously senses the environment in order to collect the input information for the cognition cycle. During the orientation phase, CR uses the gathered information to estimate the current network state. Next, CR enters the decision-making phase, in which it applies some policy to decide on the course of action. Finally, CR completes the cognition cycle by carrying out the chosen actions.

It is not common to find studies that directly address the interdependent processes composing the cognition cycle. The main reason for this is the difficulty to design analytically tractable models for systems characterized by cognitive behavior. Different studies have addressed CRNs capability of opportunistic spectrum access [START_REF] Haykin | Cognitive radio: brain-empowered wireless communications[END_REF], [START_REF] Akyildiz | A survey on spectrum management in cognitive radio networks[END_REF], in which spectrum bands licensed to primary users (PU) are shared with the cognitive users called secondary users (SU). It is well known that a significant part of the allocated spectrum is vastly underutilized and the CRN goal in this scheme is to improve spectrum utilization while avoiding interference with the PUs [START_REF] Akyildiz | NeXt generation/dynamic spectrum access/cognitive radio wireless networks: a survey[END_REF]. In [START_REF] Cormio | A survey on MAC protocols for cognitive radio networks[END_REF] state of the art protocols for medium access in cognitive radio networks are overviewed. The authors point out that the existing works do not fully integrate both the spectrum sensing and access in one framework which is required in order to maintain the capability of adaptation to the environment changes [START_REF] Maldonado | Cognitive radio applications to dynamic spectrum allocation: a discussion and an illustrative example[END_REF]. The authors of [START_REF] Rashid | Opportunistic spectrum scheduling for multiuser cognitive radio: a queueing analysis[END_REF] derive a queueing framework to study the performance of CRN. Although this model allows an analytic study of CRN performance, it lacks the modeling of the cognition cycle. A basic version of cognition cycle model is given in our previous work [START_REF] Oklander | Modeling and Analysis of System Dynamics and State Estimation in Cognitive Radio Networks[END_REF]. This paper presents three significant contributions to the problem of modeling the CRN. Firstly, we enhance the model of [START_REF] Oklander | Modeling and Analysis of System Dynamics and State Estimation in Cognitive Radio Networks[END_REF] by introducing CRN with penalty for interfering PU. The penalty provides an incentive for CRN to enhance its perception level in order to avoid interference with PU, which is an essential requirement in any realistic scenario. Next, we introduce a decision-making process, which is responsible both for selecting the channels to be accessed and for managing the samplingtransmission tradeoff [START_REF] Hoang | Adaptive Scheduling of Spectrum Sensing Periods in Cognitive Radio Networks[END_REF]- [START_REF] Ghasemi | Optimization of spectrum sensing for opportunistic spectrum access in cognitive radio networks[END_REF]. The third contribution of this paper is the introduction of cross-entropy optimized policy for controlling the CRN. The task of policy optimization is rather hard due to the high complexity of the model. To overcome this problem we use the method of stochastic optimization of cross-entropy, which is an efficient tool at hand for the task of policy optimization [START_REF] Oklander | Cross-Entropy Optimized Cognitive Radio Policies[END_REF]- [START_REF] Mannor | The cross-entropy method for fast policy search[END_REF]. The resulting policies reflect the intelligent behavior induced by the described above cognition cycle.

In sections 2, we present our model of cognition cycle. Then in section 3, we use cross-entropy method to optimize the control policy and we evaluate its performance. Section 4 summarizes.

Cognition Cycle Model

We start here with modeling the environment's dynamics, the cognition cycle and the CRN transmission process. Then, we close the loop by unifying these models under the entire system framework. The resulting system model makes it possible to analyze the cognition cycle and to evaluate the performance of the CRN.

Environment Model

We consider a general scenario of wireless communication system which consists of M channels. Every channel alternates between transmitting and idle states. The ON (OFF) period of a channel corresponds to the time interval T ON (T OFF ) during which PU transmits (is idle). We assume that T ON and T OFF intervals are exponentially distributed with parameters α and β, respectively. Since the channels are statistically independent, the number of channels available for SU S t (S t {0,1,…,M}) at time t is a birth-death process with birth-rate (M-m) and death-rate m when S t =m, m{0,1,…,M}.

Perception Model

Next, we model the perception process, which aggregates the observation and the orientation phases of OODA. CRN generates the estimation Ŝ t of the environment state S t through sensing. We assume that the time it takes to update the estimation Ŝ t is exponentially distributed. CRN adaptively tunes the sampling rate δ according to its current estimate Ŝ t , we denote this by δ Ŝ . For example, CRN could increase the sample rate δ Ŝ in order to keep track of rapidly changing network states characterized by high throughput potential, while decreasing it for slowly changing states. The compound process {S t ,Ŝ t } describes the mutual evolvement of both the environment and the estimation and is actually a continuous time Markov chain (CTMC) (see Fig. 1). Fig. 1. CTMC of the {S t ,Ŝ t } process for M=3. The horizontal transitions describe the changes of environment state S t . The vertical transitions describe the updates of the estimator Ŝ t .

Decision Making

The decision-making phase of the cognition cycle employs some policy P for both transmission-sampling tradeoff management and for channels allocation. The transmission rate of SU over a single channel is  [bit/sec]. We introduce the tradeoff parameter θ (0≤θ≤1) which divides the available bandwidth between the transmissions and sampling, where the portion θ of the channel is assigned for transmission and the remaining part (1-θ) is assigned for sampling. The effective transmission rate over a single channel is therefore θ [bit/sec] and the resulting update rate of the estimations is (1-θ)B [1/sec]. The constant 1/B [bit] is the number of bits required for updating the estimation Ŝ t and it is subject to the physical layer issues. The other responsibility of the policy P is the channel allocation C t , which is the number of channels over which CR tries to transmit at time t.

We consider state-dependent policies, meaning that the decisions are made based on the estimation of the network state Ŝ t and the internal buffer state X t . The internal buffer state X t is the number of SU packets waiting for transmission at time t. For the sake of simplicity, in the following modeling we assume that CRN makes decisions based on a greedy policy P G :

(1)

The greedy policy aims to increase the throughput by scheduling transmissions over all the channels that are estimated as unoccupied by PU. This assumption of greedy policy is removed later in section 3 when we optimize the control policies.

Transmission Process

The arrivals generated by SU are modeled as a Poisson process with rate  [bit/sec] and service time exponentially distributed with rate  t [bit/sec], which changes with time, dependent on a few factors. These factors include the number of accessed channels C t , the proportion of the bandwidth allocated for transmission θ, the environment state S t and the penalty for interfering with PU. The combination of these factors results in:

(2)

It can be seen from ( 1) that when for the greedy policy P G , we may substitute Ŝ t for C t since transmissions occur only for X t >0. From (2), our model introduces penalty for CRN when it accesses channels that are in use of PU (C t >S t ). This means that when CRN tries to access channels erroneously estimated as vacant, the transmissions fail. This type of service models CRN, giving the highest priority to PU transmissions. are omitted here in sake of keeping the clarity. ˆ0 ( , ) 0 0

t t t G t t t S X C P S X X          0 t t t t t t C C S CS        

System Process

Finally, we aggregate the environment dynamics, the cognition cycle and the transmission process into a unified system model. We define {X t ,S t ,Ŝ t } to be the process of the entire system for which at time t there are X t (X t {0,1,2,…}) queued packets of the SU. This process forms a three dimensional CTMC illustrated in Fig. 2, which is homogeneous, irreducible and stationary. The exact structure of transitions within the CTMC is constructed in the same manner as in [START_REF] Oklander | Modeling and Analysis of System Dynamics and State Estimation in Cognitive Radio Networks[END_REF], [START_REF] Oklander | Cross-Entropy Optimized Cognitive Radio Policies[END_REF]. Next, matrixgeometric approach is applied to calculate the steady state probabilities of CTMC. Then, the average number of queued packets of SU can be calculated and by using the Little's law one can obtain the waiting time W of the SU.

CRN Policy Optimization

In previous sections we modeled the cognition cycle, in which the decisions were made based on some arbitrarily chosen greedy policy P G . In this section, we aim to improve the performance of the cognition cycle and the CRN by optimizing the decision making process, i.e., by optimizing the policy.

Problem formulation

In our framework, a policy P governs the decision-making phase of the cognition cycle. This policy is responsible for managing the sampling-transmission tradeoff by tuning the parameter θ t , and for allocation of the number of channels, C t . The values of C t and θ t are determined dependently on the network's state estimation Ŝ t , current CRN buffer state X t , entire system model and its parameters, which we denote by Ω:

(C t ,θ t )=P(Ŝ t ,X t ;Ω) (3)
We aim to optimize CRN performance by minimizing the average waiting time W of SU. In the previous section, we calculated W by applying the matrix geometric analysis to the 3-D CTMC and the Little's law. The 3-D CTMC structure embeds the policy P as follows: the levels transitions (X t ) are affected by the service rate  t (eq. 2)

and the state transitions {S t ,Ŝ t }within the level are affected by the estimation update rate δ t given by δ t =(1-θ t )B. Therefore, given the system structure and its parameters Ω, we regard the average waiting time W of SU as a function of the policy P, W=W(P;Ω). The resulting optimization problem is given by: [START_REF] Akyildiz | A survey on spectrum management in cognitive radio networks[END_REF] where Π is the set of all the feasible policies, i.e., policies which for valid inputs Ŝ t {0,…,M} and X t {0,1,2,…} decide on valid values for θ[0,1] and C t {0,1,2,…,M}. Our optimization problem (4) is complicated. First, it can be shown that the problem is not convex, and the gradient-based techniques are not applicable since it is difficult to obtain a gradient for W. Next, the set Π consists of policies comprising both continuous (θ) and discrete (C t ) action spaces, which requires special approach for optimization. Additionally, the problem exhibits a high computational complexity, due to the rapidly growing (with M) set Π. * argmin ( ; )

P P W P   
We solve this problem by applying the cross-entropy (CE) method of stochastic optimization. CE method is a state-of-the-art method for solving combinatorial and multi-extremal optimization problems. In the following subsection, we review briefly the CE method and demonstrate its application for our optimization problem. The readers interested in further details are referred to [START_REF] Oklander | Cross-Entropy Optimized Cognitive Radio Policies[END_REF].

Cross-Entropy based Stochastic Optimization

The main idea behind the CE method is to define for the original optimization problem an associated stochastic problem (ASP) and then to solve efficiently the ASP by an adaptive scheme. The described below procedure sequentially generates random solutions which converge stochastically to the optimal or near-optimal one. We define a stochastic policy P((C t ,θ t )|(Ŝ t ,X t )) as the ASP for (4). P((C t ,θ t )|(Ŝ t ,X t )) is the probability of choosing action (C t ,θ t ) when CRN's state is (Ŝ t ,X t ) according to the parameter (Ŝ t ,X t ). In the following we use shorthand notation of  for (Ŝ t ,X t ). For the defined ASP, the CE method iteratively draws sample policies P (k) (k=1,2,…,K) from the defined above probability and calculates the average waiting time W(P (k) ;Ω) for each sample. Then, N (N<K) best samples graded by their related average waiting time, are used to update the parameters , in order to produce better samples in the next iteration. The algorithm stops when the score of the worst selected sample no longer improves significantly.

Cross-Entropy Optimized Policies

We present here policies obtained from CE optimization and examine them in order to get insights concerning the optimal decision-making process in CRN. As in the previous sections we are interested to reveal the impact of the cognition cycle and the dynamics of the environment on the optimal policy. We set the parameters of the environment (Ω): the number of PU channels is M=6, and the transmission rate over every channel is μ=1, the constant B is set to unity, the parameters responsible for the environment dynamics are set to α=β=kas before we will check the performance for different values of k={0.001, 1,1000}, the arrival rate of CRN traffic is λ=4. In our ASP the policy chooses action (C t ,θ t ) when CRN is in state (Ŝ t ,X t ). We assume that, C t is a discrete random variable that takes integer values {0,1,…,M}, while the tradeoff parameter θ t is normally distributed according to a truncated normal distribution in the range [0,1]. Recall, that our policy is state dependent. We distinguish between the cases X t =0 and X t >0. Obviously, for X t =0 CRN has no packets to transmit and in this case it is reasonable to allocate the bandwidth resources to the sensing process (θ t = 1). The CE algorithm optimizes the policy for X t >0.

The resulting CE optimized policies are presented in Fig. 3. For the case k=1000, CRN fails to keep track of the rapidly changing network state. This can be seen through the channel allocation C= [START_REF] Haykin | Cognitive radio: brain-empowered wireless communications[END_REF][START_REF] Haykin | Cognitive radio: brain-empowered wireless communications[END_REF][START_REF] Haykin | Cognitive radio: brain-empowered wireless communications[END_REF][START_REF] Haykin | Cognitive radio: brain-empowered wireless communications[END_REF][START_REF] Haykin | Cognitive radio: brain-empowered wireless communications[END_REF][START_REF] Haykin | Cognitive radio: brain-empowered wireless communications[END_REF][START_REF] Akyildiz | A survey on spectrum management in cognitive radio networks[END_REF], which is insensitive to the estimation Ŝ t , and the number of accessed channels is approximately the average number of unoccupied channels E[S t ]. Nevertheless, the tradeoff parameter θ=(0.57,0.91,0.93,0.99,0.72,0.59,0.37) shows that CRN tries to avoid collisions with PU; a simple analysis of the CTMC (in Fig. 2) shows that for =, S t resides only a small portion of time in the states 0 and M while it spends more time in the inner states. This fact is reflected in the low values of θ when Ŝ t is 0 or M. In order to better react to the fast network changes, CRN accelerates the sampling rate δ=(1-θ)B in these states.

For the case k=1, the resulting policy is more sensitive to the estimation of the environment state Ŝ t , and the number of accessed channels C= [START_REF] Zhao | Performance Evaluation of Cognitive Radios: Metrics, Utility Functions and Methodologies[END_REF][START_REF] Zhao | Performance Evaluation of Cognitive Radios: Metrics, Utility Functions and Methodologies[END_REF][START_REF] Mitola | Cognitive radio: Making software radios more personal[END_REF][START_REF] Haykin | Cognitive radio: brain-empowered wireless communications[END_REF][START_REF] Akyildiz | A survey on spectrum management in cognitive radio networks[END_REF][START_REF] Akyildiz | NeXt generation/dynamic spectrum access/cognitive radio wireless networks: a survey[END_REF][START_REF] Akyildiz | NeXt generation/dynamic spectrum access/cognitive radio wireless networks: a survey[END_REF] is approximately Ŝ t except for the rapidly switching states 0 and M. As in the previous case, the tradeoff parameter θ=(0.33,0.71,0.78,0.92,0.92,0.87,0.69), allocates more bandwidth for transmissions when Ŝ t indicates that the network state is a persistent one. When the environment changes occur in a significantly slower manner compared to the rate of the perception process k=0.001, the tradeoff parameter θ=(0.99,0.99,0.99,0.99,0.99,0.98,0.98) takes very high values independently of the estimation Ŝ t . The allocation of the channels C= [START_REF] Zhao | Performance Evaluation of Cognitive Radios: Metrics, Utility Functions and Methodologies[END_REF][START_REF] Zhao | Performance Evaluation of Cognitive Radios: Metrics, Utility Functions and Methodologies[END_REF][START_REF] Mitola | Cognitive radio: Making software radios more personal[END_REF][START_REF] Haykin | Cognitive radio: brain-empowered wireless communications[END_REF][START_REF] Akyildiz | A survey on spectrum management in cognitive radio networks[END_REF][START_REF] Akyildiz | NeXt generation/dynamic spectrum access/cognitive radio wireless networks: a survey[END_REF][START_REF] Cormio | A survey on MAC protocols for cognitive radio networks[END_REF] is equal to Ŝ t even for the rapidly switching state M. In Fig. 4, we compare the performance of the CRN under greedy and CE optimized policies. Under the greedy policy, the waiting time W decreases when the network transitions accelerate (k<0.1). This happens since CRN tracks well the channels and efficiently utilizes the vacant ones. For k>0.1, W grows since CRN fails to track the fluctuating state of the network. When comparing the two policies, it can be seen that the waiting time, under CE optimized policy, does better in orders of magnitude for the entire range of network dynamics (k[10 -3 ,10 4 ]).

Summary

In this paper, a three-dimensional CTMC process has been introduced to model the operation of CRN where PU form a birth-death process and SU can queue. The analytical framework combines the environment dynamics, perception and decision making components of the cognition cycle and the spectrum access processes. The cognition cycle is treated as an integral part of the system's overall behavior, and we optimize policies controlling simultaneously the interdependent perception and transmission processes. In this way, the resources are allocated according to the needs of the overall task. The CE optimized policies demonstrate adaptive behavior in which the resources are intelligently allocated to the perception and the transmission processes in a task-relevant manner.

Fig. 2 .

 2 Fig. 2. Illustration of the CTMC of the CRN model. The transitions in the (S t ,Ŝ t ) plane are identical to those in Fig. 1. The transitions between the levels of the process (along the X t axis)are omitted here in sake of keeping the clarity.

Fig. 3 .

 3 Fig. 3. The CE optimized policy for parameters M=6,=1,=4, ==k={1000,1,0.001}.

Fig. 4 .

 4 Fig. 4. CRN waiting time under greedy and CE optimized policies for parameters M=4,B=1,=1,=0.5, ==k[10 -3 ,10 4 ].

This research has been partially supported by the CorNet consortium funded by the chief scientist in the Israeli Ministry of Industry, Trade and Labor.