Database-assisted Distributed Spectrum Sharing Xu Chen and Jianwei Huang Department of Information Engineering, The Chinese University of Hong Kong Email:{cx008,jwhuang}@ie.cuhk.edu.hk 3 1 Abstract 0 2 According to FCC’s ruling for white-space spectrum access, white-space devices are required to query a n a database to determine the spectrum availability. In this paper, we study the database-assisted distributed white- J 4 space access point (AP) network design. We first model the cooperative and non-cooperative channel selection 1 problems among the APs as the system-wide throughput optimization and non-cooperative AP channel selection ] I games, respectively, and design distributed AP channel selection algorithmsthat achieve system optimal point and N . Nash equilibrium,respectively.We then proposea state-based game formulationforthe distributed AP association s c [ problemofthesecondaryusersbytakingthecostofmobility intoaccount.Weshowthatthestate-baseddistributed 1 APassociationgamehasthefiniteimprovementproperty,anddesignadistributedAPassociationalgorithmthatcan v 8 convergeto a state-based Nash equilibrium.Numericalresults show thatthe algorithmis robustto the perturbation 4 8 by secondary users’ dynamical leaving and entering the system. 2 . 1 0 3 I. INTRODUCTION 1 : v The most recent FCC ruling requires that TV white-space devices must rely on a geo-location database i X todeterminethespectrumavailability[2].In suchadatabase-assistedarchitecture, theincumbents(primary r a licensed holders of TV spectrum) providethe database with the up-to-date information includingTV tower transmission parameters and TV receiver protection requirements. Based on this information, the database will be able to tell a white-space device (secondary users (SUs) of TV spectrum) vacant TV channels at a particular location, given the white-space device’s transmission parameters such as the transmission power. Although the database-assisted approach obviates the need of spectrum sensing, the task of developing a comprehensive and reliable database-assisted white-space network system remains challenging [3]. Motivated by the successful deployments of Wi-Fi over the unlicensed ISM bands, in this paper we *Part of the results has been published at IEEE ICDCS 2012 [1]. Fig. 1. Distributed spectrum sharing with geo-location database Fig. 2. System architecture consider an infrastructure-based white-space network (see Figure 1 for an illustration), where there are multiplesecondaryaccesspoints(APs)operatingonwhitespaces.Suchaninfrastructure-basedarchitecture has been adopted in IEEE 802.22 standard [4] and Microsoft Redmond campus white-space networking experiment [3]. More specifically, each AP first sends the required information such as its location and the transmission power to the database via wire-line connections. The database then feeds back the set of vacant TV channels at the location of each AP. Afterwards, an AP chooses one feasible channel to serve the secondary users (i.e., unlicensed white-space user devices) within its transmission range. The key challenges for such an infrastructure-based white-space network design are twofold (see Figure 2 for an illustration). First, in the AP tier, each AP must choose a proper vacant channel to operate in order to avoid severe interference with other APs. Second, in the SU tier, when an AP is overloaded, a secondary user can improve its throughput by moving to and associating with another AP with less contending users. Each secondary user hence needs to decide which AP to associate with. In this paper, for the AP tier, we first consider the scenario that all the APs are owned by one network operator and hence the APs are cooperative. We formulate the cooperative AP channel selection problem as the system-wide throughput optimization problem. We then consider the scenario that the APs are TABLEI SUMMARYOFTHERESULTS Problem Cooperative AP Channel Selection Non-Cooperative AP Channel Selection AP Tier Formulation System-wide ThroughputOptimization Non-Cooperative AP Channel Selection Game Algorithm Cooperative AP Channel Selection Algorithm Non-Cooperative AP Channel Selection Algorithm Problem Distributed AP Association by SUs SU Tier Formulation Distributed AP Association Game Algorithm Distributed AP Association Algorithm owned by different network operators and the interest of APs is not aligned. We model the distributed channel selection problem among the APs as a non-cooperative AP channel selection game. For the SU tier, we propose a state-based game framework to model the distributed AP association problem of the secondary users by taking the cost of mobility into account. The main results and contributions of this paper are as follows (please refer to Table I for a summary): General formulation: We formulate the cooperative and non-cooperative channel selection problems • among the APs as system-wide throughput optimization and non-cooperative AP channel selection game, respectively, based on the physical interference model [5]. We then propose a state-based game framework to formulate the distributed AP association problem of the secondary users and explicitly take the cost of mobility into account. Existence of equilibrium solution and finite improvement property: For the cooperative AP channel • selection problem, the interest of APs is aligned and the system optimal solution that maximizes system-wide throughput always exists. For the non-cooperative AP channel selection game, we show that it is a potential game, and hence it has a Nash equilibrium and the finite improvement property. For the state-based distributed AP association game, we show that it also has a state-based Nash equilibrium and the finite improvement property. Distributed algorithms for achieving equilibrium: For the cooperative AP channel selection problem, • we propose a cooperative channel selection algorithm that maximizes the system-wide throughput. For the non-cooperative AP channel selection game, we propose a non-cooperative AP channel selection algorithm that achieves a Nash equilibrium of the game. For the state-based distributed AP association game, we design a distributed AP association algorithm that converges to a state- based Nash equilibrium. Numerical results show that the algorithm is robust to the perturbation by secondary users’ dynamical leaving and entering the system. The rest of the paper is organized as follows. We introduce the cooperative and non-cooperative AP channel selection problems, and propose the cooperative and non-cooperative AP channel selection algo- rithms in Sections II and III, respectively. We present the distributed AP association game and distributed AP associationalgorithminSection IV.Weillustratetheperformanceoftheproposedmechanismsthrough numerical results in Section V, and finally introduce the related work and conclude in Sections VI and VII, respectively. II. COOPERATIVE AP CHANNEL SELECTION A. System Model We first introduce the system model for the cooperative channel selection problem among the APs in the AP tier. Let M = {1,2,...,M} denote the set of TV channels, and B denote the bandwidth of each channel (e.g., B = 6 MHz in the United States and B = 8 MHz in the European Union). We considera set N = {1,2,...,N} of APs that operate on the white spaces. Each AP n ∈ N has a specified transmission power P based on its coverage and primary user protection requirements. n Each AP n can acquire the information of the vacant channels at its location from the geo-location database. We denote M ⊆ M as the set of feasible channels of AP n, a ∈ M as the channel chosen n n n by AP n1, and a = (a ,...,a ) as the channel selection profile of all APs. Then the worse-case down-link 1 N throughput (i.e., the throughput at the boundary of the coverage area) of AP n can be computed according to the physical interference model [5] as P /dθ U (a) = Blog 1+ n n , (1) n 2 ωn + P /dθ an i∈N/{n}:ai=an i in! where θ is the path loss factor, dn denotes the radiusPof the coverage area of AP n, and din denotes the distance between AP i and the benchmark location at the boundary of the coverage area of AP n. Furthermore, ωn denotes the background noise power including the interference from incumbent users an on the channel a , and P /dθ denotes the accumulated interference from other APs that n i∈N/{n}:ai=an i in choose the same channePl a . Note that we assume that all APs only try to maximize the worse-case n throughputs by proper channel selections, which do not depend on the number of its associated users. However, the secondary users can increase their data rates by moving to and associating with a less congested AP (see Section IV for detailed discussions). Note that our model also applies to the up-link case if the secondary users within an AP transmit with roughly the same power level. 1Following the conventions in IEEE 802.22 standard [4] and Microsoft Redmond campus white-space networking experiment [3], we consider the case that each AP can select one channel to operate on. The case that each AP can select multiplechannels to operate on will be considered in a future work. B. Cooperative AP Channel Selection Algorithm We first consider the case that all the APs try to maximize the system-wide throughput cooperatively. Such a cooperation is feasible when all the APs are owned by the same network operator. For example, the APs that are deployed in a university campus can coordinate to maximize the entire campus network throughput. Formally, the APs need to collectively determine the optimal channel selection profile a such that the system-wide throughput is maximized, i.e., N max U (a). (2) n a∈Θ,ΠNn=1Mn n=1 X The problem (2) is a combinatorial optimization problem of finding the optimal channel selection profile overthediscretesolutionspace Θ.Ingeneral,suchaproblemisverychallengingtosolveexactlyespecially when the size of network is large (i.e., the solution space Θ is large). We next propose a cooperative channel selection algorithm that can approach the optimal system-wide throughput approximatively. To proceed, we first write the problem (2) into the following equivalent problem: N max qa Un(a), (3) (qa:a∈Θ) a∈Θ n=1 X X where qa is the probability that channel selection profile a is adopted. Obviously, the optimal solution to problem (3) is to choose the optimal channel selection profile with probability one. It is known from [6] that problem (3) can be approximated by the following convex optimization problem: N 1 max qa Un(a)− qalogqa, (4) (qa:a∈Θ) γ a∈Θ n=1 a∈Θ X X X where γ is the parameter that controls the approximation ratio. We see that when γ → ∞, the problem (4) becomes exactly the same as problem (3). That is, when γ → ∞, the optimal point a∗ that maximizes the system throughput N U (a) will be selected with probability one. A nice property of such an n=1 n approximation in (4) is tPhat we can obtain the close-form solution, which enables the distributed algorithm design later. More specifically, by the KKT condition [7], we can derive the optimal solution to problem (4) as exp γ N U (a) n=1 n q∗ = . (5) a e(cid:16)xpPγ N U ((cid:17)a′) a′∈Θ n=1 n (cid:16) (cid:17) P P Similarly to the spatial adaptive play in [8] and Gibbs sampling in [9], we then design a cooperative AP channel selection algorithm by carefully coordinating APs’ asynchronous channel selection updates to Fig. 3. System state transition diagram of the cooperative AP channel selection Markov chain by two APs. Figure on the left hand-side details the vacant channels of two APs. For example, AP 1 can choose channels 1 and 2 to transmit. Figure on the right hand-side shows the transition diagram of the Markov chain, and (a1,a2) denotes the system state witha1 and a2 being the channels chosen by APs1 and 2, respectively. The direct transition between two system states is feasible if they are connected by a link. Algorithm 1 Cooperative AP Channel Selection Algorithm 1: initialization: 2: choose an initial channel an ∈ Mn randomly for each AP n ∈ N. 3: acquire the information of initial channel selections, transmission powers, and geo-locations from other APs by each AP n ∈ N. 4: end initialization 5: loop for each iteration: 6: Database selects an AP randomly and informs the selected AP to update its channel selection. 7: for each AP n ∈ N in parallel do 8: if the update command is received from the database then 9: calculate the system throughput Nn=1Un(an,a−n) for each feasible channel selection a ∈ M . n n 10: select a channel an ∈ Mn with a pProbability of Pa′∈exMpn(γexPp(Nnγ=1PUNnn=(1anU,na(−an′,)a)−n)). 11: broadcast the chosen channel an to other APs. 12: else select the original channel. 13: end if 14: end for 15: end loop form a discrete-time Markov chain (with the system state as the channel selection profile a of all APs). As long as the Markov chain converges to the stationary distribution as given in (5), we can approach the optimal channel selection profile that maximizes the system-wide throughput by setting a large enough parameter γ. The details of the algorithm are given in Algorithm 1. Here APs’ asynchronous channel selection updates are scheduled by the database. In each iteration, one AP will be randomly chosen to update its channel selection. In this case, the direct transitions between two system states a and a′ are feasible if these two system states differ by one and only one AP channel selection. As an example, the system state transition diagram of the cooperative AP channel selection Markov chain by two APs is shown in Figure 3. We also denote the set of system states that can be transited directly from the state a as Λa , {a′ ∈ Θ : |{a∪a′}/{a∩a′}| = 2}, where |·| denotes the size of a set. Since each AP will be selected to update with a probability of 1 and the selected AP will randomly N choose a channel with a probability proportional to exp γ Nn=1Un(a) , then if a′ ∈ Λa, the probability that the Markov chain transits from state a to a′ is giv(cid:16)en Pas (cid:17) exp γ N U (a′ ,a ) 1 n=1 n n −n q = . (6) a,a′ N (cid:16)expPγ N U (a′,a(cid:17) ) a′∈Mn n=1 n −n Otherwise, we have qa,a′ = 0. We showPin Theorem(cid:16)1 thPat the cooperative(cid:17)AP channel selection Markov chain is time reversible. Time reversibility means that when tracing the Markov chain backwards, the stochastic behavior of the reverse Markov chain remains the same. A nice property of a time reversible Markov chain is that it always admits a unique stationary distribution, which guarantees the convergence of the cooperative AP channel selection algorithm. Theorem 1. The cooperative AP channel selection algorithm induces a time-reversible Markov chain with the unique stationary distribution as given in (5). Proof: As mentioned, the system state of the cooperative AP channel selection Markov chain is defined as the channel selection profile a ∈ Θ of all APs. Since it is possible to get from any state to any other state within finite steps of transition, the AP channel selection Markov chain is hence irreducible and has a stationary distribution. We then show that the Markov chain is time reversible by showing that the distribution in (5) satisfies the following detailed balance equations: q∗q = q∗ q ,∀a,a′ ∈ Θ. (7) a a,a′ a′ a′,a To see this, we consider the following two cases: 1) If a′ ∈/ Λa, we have qa,a′ = qa,a′ = 0 and the equation (7) holds. 2) If a′ ∈ Λa, according to (5) and (6), we have exp γ N U (a) exp γ N U (a′) n=1 n 1 n=1 n q∗q = a a,a′ e(cid:16)xpPγ N U ((cid:17)a˜) N ex(cid:16)p Pγ N U (a′(cid:17),a ) a˜∈Θ n=1 n a′∈Nn n=1 n −n Pexp γ (cid:16) NPU (a′) (cid:17) P exp γ(cid:16) PN U (a) (cid:17) n=1 n 1 n=1 n = e(cid:16)xpPγ N U ((cid:17)a˜) N exp(cid:16) γP N U (a(cid:17)′,a ) a˜∈Θ n=1 n a′∈Nn n=1 n −n (cid:16) (cid:17) (cid:16) (cid:17) P P P P = q∗ q . a′ a′,a The cooperative AP channel selection Markov chain is hence time-reversible and has the unique stationary distribution as given in (5). According to Theorem 1, we can approach the system optimal point that maximizes the system-wide throughput by setting γ → ∞ in the cooperative AP channel selection algorithm. However, in practice we can only implement a finite value of γ such that exp(γ N U (a)) does not exceed the range of the n=1 n largest predefined real number on a computer. Let S¯ = P q∗ N U (a) be the expected potential a∈Θ a n=1 n by Algorithm 1 and S∗ = max N U (a) be the glPobal optiPmal potential. We show in Theorem 2 a∈Θ n=1 n that, when a large eough γ is adoptPed, the performance gap between S¯ and S∗ is very small. Theorem 2. For the cooperative AP channel selection algorithm, we have that 1 0 ≤ S∗ −S¯ ≤ ln|Θ|, γ where |Θ| denotes the number of feasilbe channel selection profiles of all APs. Proof: First of all, we must have that S∗ ≥ S¯. According to (2), (4), and (5), we then have that n n 1 max q U (a) ≤ max q U (a)− q lnq , (8) a n a n a a (qa:a∈Θ) (qa:a∈Θ) γ a∈Θ n=1 a∈Θ n=1 a∈Θ X X X X X which is due to the fact that 0 ≤ −1 q lnq ≤ 1 ln|Θ|. Since q∗ is the optimal solution to (4) and γ a∈Θ a a γ a S∗ = max(qa:a∈Θ) a∈Θqa nn=1Un(aP), according to (8), we know that n P P S∗≤ q∗ U (a)− 1 q∗lnq∗ a n γ a a a∈Θ n=1 a∈Θ X X X n 1 ≤ q∗ U (a)+ ln|Θ| a n γ a∈Θ n=1 X X 1 ≤S¯+ ln|Θ|, γ which completes the proof. We then analyze the computational complexity of the algorithm. In each iteration, one AP will be chosen for the channel selection update. Line 9 involves the summation of the throughputs of N APs for M channels. Since |M | ≤ M, this step has the complexity of O(NM). Line 10 involves at most n n M summation and division operations and hence has a complexity of O(M). Line 11 has a complexity of M(1). Suppose that it takes C iterations for the algorithm to converge. Then total computational complexity of the algorithm is O(CNM). Similarly, the space complexity of the algorithm is O(N2 + NM). III. NON-COOPERATIVE AP CHANNEL SELECTION We next consider the case that the APs are owned by different network operators. Unlike the previous case where the interest of the APs is aligned in the cooperative channel selection, here each AP is generally selfish and only concerns about its own throughput maximization. Formally, given other APs’ channel selections a , the problem faced by an AP n is to choose a proper channel to maximize its own −n throughput, i.e., max U (a ,a ),∀n ∈ N. n n −n an∈Mn The non-cooperative nature of the channel selection problem naturally leads to a formulation based on game theory, such that each AP can self organize into a mutually acceptable channel selection (Nash equilibrium) a∗ = (a∗,a∗,...,a∗ ) with 1 2 N a∗ = arg max U (a ,a∗ ),∀n ∈ N. n n n −n an∈Mn A. Non-Cooperative AP Channel Selection Game We now formulate the non-cooperative channel selection problem as a strategic game Γ = (N,{M } ,{U } ), where N is the set of APs, M is the set of strategies for AP n, and U n n∈N n n∈N n n is the payoff function of AP n. We refer this as the non-cooperative AP channel selection game in the sequel. We can show that it is a potential game, which is defined as Definition 1 (Potential Game [10]). A game is called a potential game if it admits a potential function Φ(a) such that for every n ∈ N and a ∈ M , −n i6=n i ′ Q ′ sgn Φ(a ,a )−Φ(a ,a ) = sgn U (a ,a )−U (a ,a ) , n −n n −n n n −n n n −n (cid:16) (cid:17) (cid:16) (cid:17) where sgn(·) is the sign function defined as 1 if z > 0,  sgn(z) = 0 if z = 0,     −1 if z < 0.    Definition 2 (Better Response Update [10]). The event where a player n changes to an action a′ from n the action a is a better response update if and only if U (a′ ,a ) > U (a ,a ). n n n −n n n −n An appealing property of the potential game is that it admits the finite improvement property, such that any asynchronous better response update process (i.e., no more than one player updates the strategy at any given time) must be finite and leads to a Nash equilibrium [10]. To show that the non-cooperative AP channel selection game Γ is a potential game, we now consider a closely related game Γ˜ = (N,{M } ,{U˜ } ), where the new payoff functions are n n∈N n n∈N P /dθ U˜ (a) = n n . (9) n ωn + P /dθ an i∈N/{n}:ai=an i in Obviously, the utility function U (a) can be obtPained from the utility function U˜ (a) by the following n n monotone transformation U (a) = Blog 1+U˜ (a) . (10) n 2 n (cid:16) (cid:17) Due to the property of monotone transformation, we have Lemma 1. If the modified game Γ˜ is a potential game, then the original non-cooperative AP channel selection game Γ is also a potential game with the same potential function. Proof: Since f(x) = Blog (1+x) is a monotonically strictly increasing function, we have that 2 ′ ˜ ′ ˜ sgn U (a ,a )−U (a ,a ) = sgn U (a ,a )−U (a ,a ) . n n −n n n −n n n −n n n −n (cid:16) (cid:17) (cid:16) (cid:17) If the modified game Γ˜ is a potential game with a potential function Φ such that sgn Φ(a′ ,a )−Φ(a ,a ) = sgn U˜ (a′ ,a )−U˜ (a ,a ) , n −n n −n n n −n n n −n (cid:16) (cid:17) (cid:16) (cid:17) then we must also have that ′ ′ sgn Φ(a ,a )−Φ(a ,a ) = sgn U (a ,a )−U (a ,a ) , n −n n −n n n −n n n −n (cid:16) (cid:17) (cid:16) (cid:17) which completes the proof. For the modified game Γ˜, we show in Theorem 3 that it is a potential game with the following potential function N P P Φ(a) = − i jI −2 P ωi , (11) dθ {ai=aj} i ai i j6=i ij i=1 XX X where I = 1 if a = a , and I = 0 otherwise. {ai=aj} i j {ai=aj} Theorem 3. The modified game Γ˜ is a potential game with the potential function Φ(a) as given in (11). Proof: Suppose that an AP k changes its channel a to a′ such that the strategy profile changes from k k