A Bilateral Bargaining Scheme under Incomplete Information for Dynamic Spectrum Access

INTRODUCTION

Over last few years, the use of radio spectrum has increased dramatically in wireless communications. As the fundamental and most important resource, the radio spectrum is shared among a variety of services temporally for a vast array of different purposes (Leaves et al., 2004; Yan et al., 2012; Giacomazzi et al., 2012; Xu et al., 2012). Due to the nature of beyond 3G or 4G mobile systems, such as distribution, reconfiguration, diversity etc., to utilize efficiently the precious radio spectrum, to accommodate as many services as possible and provide operators maximal profits is an issue (Maharjan et al., 2011).

Traditionally, spectrum is licensed with a particular radio standard and spatially managed by different operators to deliver their services, called Fixed Spectrum Management (FSM). Interference between different RANs (Radio Access Networks) have been avoided successfully in the current FSM policy. However, FSM adopted can not cope with the progress of future heterogeneous networks. Simultaneously, traditional FSM results in low utilization efficiency and spectrum holes because of dynamic demands for spectrum (McHenry, 2003). Throughout the last decade, considering the scarcity and high economic value of spectrum, worldwide research efforts have been made in Dynamic Spectrum Management (DSM) (Leaves et al., 2001, 2002, 2004; Dimitrakopoulos et al., 2004). Several mechanisms have been proposed to enhance the efficiency of spectrum utilization, e.g. European research project DRiVE and OverDRiVE (Leaves et al., 2001, 2002, 2004). With the rapid development of SDR and the introduction of reconfiguration concepts (Dimitrakopoulos et al., 2004), DSM no longer remains a utopia but becomes a reality. Howevery, aforementioned works have shown that win-win strategy for DSM and operators is still in the air.

In this study, efforts are dedicated to designing a reasonable DSM scheme to give a comprehensive attention to enhance the spectrum efficiency and maximize the operator’s profits. Three contributions are made in this study. First, a bilateral bargaining based DSM architecture and some necessary concepts are described to make the spectrum trading applicable. Second, the bilateral bargaining DSM (BBDSM) algorithm and its implementation procedure are proposed. This BBDSM takes advantage of Chatterjee and Samuelson (1983) (C and S) bilateral bargaining model in game theory to explicitly address the profit improvement of the RANs. Finally, the proposed BBDSM is compared with existing FSM based on two imperfect load prediction methods, history value prediction and current value prediction, using extensive simulations. Results show that BBDSM is definitely effective in improving the spectrum utilization and increasing the operator’s profits.

SYSTEM MODEL

In this section, the basic BBDSM architecture is introduced as shown in Fig. 1. Specifically, some new defined concepts supporting the proposed BBDSM scheme are emphasized.

BBDSM architecture: Spectrum market which originates from the definition of spectrum pool (Dimitrakopoulos et al., 2004), is a logical spot where distributed RANs could do spectrum transactions. In the spectrum market, if some RAN can satisfies its own service requirements and have spare spectrum as well it can lease his extra spectrum out to maximize spectrum efficiency and his profits. On the other hand, if some RAN lacks of spectrum owing to increasing services it becomes a consumer of the spectrum market. In order to make more profits and satisfy as many service demands as possible, the RAN will try to rent spectrum from others to proceed with his service provisioning. Once there is a market, there should be policies to regulate the operation of trading behaviors. Regulator is a repository of these principles, e.g., trading regulations, greedy behavior bans and so on. To fulfill the spectrum transactions, each RAN is attached to an intelligent Trading Agent (TA). Similar to agents in real business, TAs take charge of the transactions and make a series of important decisions, e.g., when to lease/rent the spectrum, how much spectrum to lease/rent, at what price to lease/rent the spectrum et al.

Furthermore, to facilitate the spectrum trading, the entire spectrum block is divided into Spectrum Trading Units (STU) in a size of the smallest channel in a fixed service channel raster for a given band. The trouble in controlling and managing the interferences between RANs (Leaves et al., 2004) is ignored in the proposed BBDSM.

As mentioned in previous works Leaves et al. (2001, 2002), DSM is periodical and proactive operation and typical period is 0.5 h, i.e., for the set T = {1, 2,…}, the DSM interval between t and t+1 is half an hour. This feature is important for the spectrum trading because spectrum leasing or renting will expire automatically after the specified interval of time. Moreover, DSM at t is essential for providing services and profit earning at t+1, whose payoff function depends on the results of BBDSM at t and the practical load at t+1.

RAN’s profits: The total profits of each RAN in BBDSM can be divided into two parts: One is the profits of service provision utilizing his original spectrum (i.e., spectrum pre-assigned to that RAN); the other is profits from spectrum trading.

Service providing profits: If TA of the RAN utilizes a STU to provide services for one period it will obtain payoff:

(1)

where, P_sprov is the earned income of services and P_cost is his own basic cost of the spectrum.

Spectrum trading profits: In view of the proactive features of BBDSM, practical traffic demands may present some deviations from predicting traffic demands.

Fig. 1:	Architecture for BBDSM in reconfigurable systems

If actual load is less than the predicting value, investment made by renting TA on trading spectrum at period t may bring no profits at period t+1; on the contrary, investment made by renting TA may pose deficient which lower profits and lead to the denial of service at period t+1.To guarantee the income of leasing TAs, like in the real market, a simple risk capital mechanism is embodied in BBDSM and the spectrum trading profits allocating can be fulfilled in two steps: Advance payment at t and profit settlement in t+1. With the premise that renting TA comes into terms with leasing TA and decides to choose this TA to trade with it should deliver advance payment to leasing TA beforehand. Regarding the risks of imperfection of load prediction, this payment is nonrefundable. Renting TA bargains with leasing TA at t over the amount of advance payment per STU with the assumption that this STU of spectrum is used to satisfy the service requirements and make profits. Advance payment per STU is defined as P advance which is in accord with the bilateral bargaining results between renting TA and leasing TA. Hence, the profit of leasing TA from spectrum trading can be denoted as follows:

(2)

After the practical service demands are satisfied at t+1, profit settlement stage takes on. Renting TA’s profits per STU earned by the trading spectrum is:

(3)

BBDSM SCHEME

Based on the architecture and definitions above, BBDSM scheme is elaborated in this section. Due to the decentralized properties of RANs, TAs can’t collect all the necessary trading information, thus the negotiations between renting TA and leasing TA can be considered as a Bayesian game with incomplete information. As one of the most classic models in that game, C and S bargaining model by Chatterjee and Samuelson (1983) is adopted for the profit allocation in BBDSM. The Bayesian equilibrium and related implementation procedures are investigated in this part as well.

BDSM algorithm under incomplete information general description: Chatterjee and Samuelson (1983) studied a bilateral bargaining under incomplete information in 1983. Two players, a buyer and a seller, are trying to transact a good. The buyer and seller name a price; if the bid price is above the ask price, the good is sold for the average of the two prices and if the ask price is above the bid price, the seller retains the good. Each trader knows his own valuation for the good. However, there is incomplete information on each side concerning the side’s valuation.

In the case of BBDSM, since renting TAs’ and leasing TAs’ profits depend on the earning of spectrum trading, they can be also regarded as two players bargaining to transact spectrum. The bilateral bargaining between them can be abstracted into a Bayesian game model as follows:

(4)

(5)

Bargaining strategies: Now, the key problem for both renting TA and leasing TA is how to design the optimal bids or asks to achieve maximum benefit, relying on incomplete information about the opponent. Starting with the basic concepts presented in Chatterjee and Samuelson (1983), a novel approach for spectrum bargaining analysis is developed here.

Suppose the leasing TA estimates the renting TA will use a linear bargaining strategy:

(6)

where, S_bid^(lease)(v) is the estimation made by the leasing TA of what the renting TA’s offer will be.

Correspondingly, the renting TA estimates that the leasing TA will use a linear bargaining strategy:

(7)

where, S_ask^(rent)(c) is the renting TA’s estimate of the leasing TA’s offer.

It should be noted that the leasing TA have no information about the value of v and the renting TA does not know c. Coefficient α_bid and β_bid are the estimation of leasing TA (α_bid≥0, β_bid≥0) and coefficient α_ask and β_ask are estimated by the renting TA (α_ask≥0, β_ask≥0). As mentioned above, leasing TA and renting TA develop their bargaining strategies to expand their own benefits:

(8)

where, S_ask is the asking price of the seller to be determined, E [S_bid^(lease)(v)|S_bid^(lease)(v)≥S_ask] is the expectation (mean) of the estimated bid price of the renting TA when this estimated bid price is larger than or equal to the ask price of the leasing TA and Prob [S_bid^(lease)(v)≥S_ask] is the probability that the estimated bid of the renting TA is larger than or equal to the ask of the leasing TA.

In consistent with renting TA, the leasing TA’s profit maximizing objective can be illustrated as:

(9)

Bayesian equilibrium of the game is supposed as (S_bid^*, S_ask^*) which represent the optimal strategies maximizing the profits of renting RAN and leasing RAN, respectively. It can be obtained from:

(10)

(11)

In the effort to receive more profits and deduce the optimal strategies S_bid* and S_ask* from Eq. 10, 11, E [S_bid^(lease)(v)| S_bid^(lease)(v)≥S_ask], Prob [S_bid^(lease)(v)≥S_ask], E[S_ask^(rent) (c)| S_bid≥S_ask^(rent)(c)] and Prob [S_bid≥S_ask^(rent)(c)] must be satisfied. With the valuation of c and v based on load prediction, leasing TA can have an estimate of S_bid^(lease) (v) and renting TA can have an estimate of S_ask^(rent) (c). When this estimations are embodied into the functions, E [S_bid^(lease) (v)| S_bid^(lease) (v)≥S_ask], Prob [S_bid^(lease) (v)≥S_ask], E [S_ask^(rent) (c)| S_bid≥S_ask^(rent) (c)] and Prob [S_bid≥S_ask^(rent) (c)] can be calculated and consequently the Bayesian equilibrium can be developed from Eq. 10, 11.

TA’s valuation of c and v should be dynamically adapted in consistent with the supply demand relation of the market in near future. To be specific, spectrum will appreciate provided that demand exceeds supply in the market and prospective spectrum demand is optimistic. On the other hand, spectrum will depreciate provided that supply exceeds demand in the market and prospective spectrum demand is pessimistic. However, it is almost impossible for the individual TA to predict and assemble all the necessary information of the whole market accurately. Instead, either renting or leasing TA adapts its own estimate of v or c according to the spectrum load prediction, i.e., with current time t, if renting TA predicts that its loads increase at t+1 which means this TA is in more urgent need of the spectrum, v is supposed to be in higher price. On the contrary, if renting TA predicts its loads decrease at t+1 it will lower v. Correspondingly, if leasing TA predicts that its loads increase at t+1 which means the spare spectrum is shrinking, c will be in higher price. And if this TA predicts its loads decrease at t+1 which means the TA have more available spectrum to lease and it is eager to trade, estimation of spectrum descend. Meanwhile, massive v can be statistically taken by renting TA as variable with a certain probability distribution (e.g., uniform distribution, triangular distribution) and so it does with c by the leasing TA. To be simple, in the following part, the bargaining strategies of both parties are investigated in the scenario of c and v with a uniform distribution.

Optimal bilateral bargaining strategies under a uniform distribution: If TA of the RAN utilizes a STU to provide services for one period it will obtain payoff.

The renting TA assumes c to be a variable uniformly distributed in [c₁, c₂] and the leasing TA assumes v to be a variable uniformly distributed in [v₁, v₂]. As defined in Eq. 6-7, S_bid^(lease) (v) and S_ask^(rent) (c) are variables uniformly distributed in [α_bid+β_bid*v₁, α_bid+β_bid*v₂] and [α_ask+β_ask*c₁, α_ask+β_ask*c₂], respectively. It is obvious that the probability density for c is 1/(c₂-c₁) and for v is 1/(v₂ – v₁). Similar probability density can also be found for S_bid^(lease) (v) and S_ask^(rent) (c).

With the assumption of a uniform distribution for v, Prob [S_bid^(lease) (v)≥S_ask] can be obtained through simple mathematical manipulation:

(12)

For S_bid^(lease)(v) is uniformly distributed in [α_bid+β_bid*v₁, α_bid+β_bid*v₂], E[S_bid^(lease)(v)| S_bid^(lease)(v)≥S_ask] can be easily deduced as:

(13)

Correspondingly, formulations can be established for Prob[S_bid≥S_ask^(rent)(c)] and E[S_ask^(rent)(c)| S_bid≥S_ask^(rent)(c)] under the assumption of a uniform distribution for c, i.e.:

(14)

(15)

In terms of Bayesian equilibrium, Eq. 12 and 13 are substituted into Eq. 8 and then from Eq. 10, the optimal strategy of the leasing TA can be given as:

(16)

Therefore, when there is equilibrium, the optimal strategy for the leasing TA is to offer an asking price which is the sum of 1/3 the upper limit of his estimation of the buyer’s bid and 2/3 his own lowest valuation of the trading spectrum.

Similarly, taking Eq. 14 and 15 into Eq. 9 and then from Eq. 11, when the game reaches the equilibrium, the optimal bidding strategy of the renting TA would be:

(17)

Hence, the optimal strategy for the renting TA is to ask in a price which is the sum of 1/3 the lower limit of his estimation of the leasing TA’s ask and 2/3 his own highest valuation.

BBDSM IMPLEMENTATION

BBDSM runs periodically. In each period, TAs takes five main steps: profit settlement, self-checking, spectrum value estimation, bilateral bargaining and decision making as depicted in Fig. 2.

Profit settlement: If current TA was renting TA in period (t-1) and spectrum trading has made profits in terms of practical load during period t, profits earned by service will be received the providing conforming to the agreement reached in the last period. Considering the imperfect load prediction and risk of the advance payment, there may be surplus or deficit for current TA.

Self-checking: TA checks his predicting status of spectrum usage and compares it with T_h which is defined as the trading threshold to classify all the RANs into two categories with respect to the predicting spectrum using ratio r_p:

(18)

where, S_p is the forecasting load and S_a is the number of total STUs originally assigned to that RAN.

Spectrum value estimation: The spectrum value estimation of the renting TA (c) and the leasing TA (v) will change independently in accordance with the variations in load prediction as mentioned above.

Bilateral bargaining: Each renting TA will negotiate with each leasing TA. With the premise that all the TAs are endowed with high intelligence, each pair of renting TA and leasing TA can find their optimal strategies quickly to equilibrate the bilateral bargaining game of spectrum trading and come to terms with each other in a short time (i.e. for only a few seconds) which is negligible compared with BBDSM period.

Decision making: As shown in Fig. 2, renting TA will weigh all potential bilateral bargaining contracts and apply for the spectrum trading with most profitable leasing TA. With respect to the leasing TA, if there is more than one trading candidates (e.g., m candidate renting TAs) it will choose the most profitable renting TA to lease the spectrum out.

The overall algorithm of BBDSM can be illustrated in Fig. 2.

SIMULATION AND ANALYSIS

Simulation model: A simulation was created to model three overlaid RANs, UMTS, GSM and DVB-T and assess their profits as well as other performances with and without BBDSM, over a span of 24 h.

For illustrative purpose, various service demands for spectrum (e.g., voice load, video load, data load and et al.) across different RANs are abstracted in STUs. Providing in the market, the whole block of spectrum is in the size of 190 STUs, where UMTS, GSM and DVB-T own 50, 40 and 100 STUs, respectively. As for BBDSM, the income of services per STU P_sprov is defined as 1, the basic cost of the spectrum belonging to current TA P_cost is 0.4 and T_h is set to 1 To be simple, given c₁ = v₁ = 0 and c₂ = v₂ = 1 i.e., c and v are uniformly distributed in [0, 1]. When the bilateral bargaining game arrives at equilibrium, there would be:

(19)

(20)

Given c₁ = v₁ = 0 and c₂ = v₂ = 1 and substitute them into Eq. 16-17 and from Eq. 19-20, there would be α_bid = 1/12, β_bid = 2/3, α_ask = 1/4 and β_ask = 2/3.

Fig. 2:	Proposed BBDSM algorithm

Table 1:	Simulation parameters

Meanwhile, similar to Leaves et al. (2002), BBDSM is executed every 0.5 h in the simulations. The main parameters for simulation are summarized in Table 1.

Moreover, two simple imperfect prediction schemes are employed to estimate the future load in the proposed BBDSM:

Fig. 3(a-c):	Time varying normalised traffic demands of a day (predicting load vs practical load), (a) DVB-T, (b) UMTS and (c) GSM

Current value scheme takes the value of the current load at t measured as an estimate of the load of t+1; history value scheme refers to load distribution models by Leaves et al. (2001) and Almeida et al. (1999). Double-gaussian and trapezoidal functions are adopted to simulate UMTS and GSM historical statistical load pattern correspondingly.

Since, UMTS, GSM and DVB-T have different time-varying loads as shown in Fig. 3, BBDSM is embodied to dynamically trade the spectrum in STUs among the three RANs on a temporal basis.

As shown in Fig. 3, practical load always deviates from the predicted value when model DVB-T, UMTS and \GSM are applied. This is because that the prediction value is estimated based on load distribution. Therefore, unexpected load peaks or slopes may be caused by certain events, e.g., traffic jam, important sports events or a public holiday. On the other hand, BBDSM scheme takes practical load into account and can avoid this kind of deviation.