Two-Dimensional Route Switching in Cognitive Radio Networks：A Game-Theoretical Framework

Two-Dimensional Route Switching in Cognitive Radio Networks:A Game-Theoretical Framework Qingkai Liang,Xinbing Wang,Xiaohua Tian,Fan Wu,Qian Zhang Abstract-In Cognitive Radio Networks (CRNs).Secondary lays2,spectrum mobility may further cause the break of pre- Users (SUs)can flexibly access Primary Users'(PUs')idle established routes of incoming data flows,since the unavail- spectrum bands but such spectrum opportunities are dynamic ability of PUs'channels disables the transmission over some due to PUs'uncertain activity patterns.In a multi-hop CRN consisting of SUs as relays,such spectrum dynamics will further links on those routes.To avoid conflicts with PUs and resume cause the invalidity of pre-determined routes.In this paper,we routing,each flow initiator can either inform intermediate SU investigate spectrum-mobility-incurred route-switching problems relays of switching their accessing channels or re-select a new in both spatial and frequency domains for CRNs,where spatial spatial route3 where channels are not reclaimed.However, switching determines which relays and links should be re-selected the following tradeoff implies that two-dimensional route and frequency switching decides which channels ought to be re-assigned to the spatial routes.The proposed route-switching switching (i.e.,the combination of both channel switching and scheme not only avoids conflicts with PUs but also mitigates spatial route re-selection)is a better choice. spectrum congestion.Meanwhile,tradeoffs between routing costs The advantage of channel switching is that it maintains and channel switching costs are achieved.We further formulate the original optimal spatial route (e.g.,a route with the the route-switching problem as the Route-Switching Game which is shown to be a potential game and has a pure Nash Equilibrium fewest hops),which efficiently reduces routing costs,including (NE).Accordingly,efficient algorithms for finding the NE and transmission delay,energy consumption,etc.Unfortunately, the e-NE are proposed.Then we extend the proposed game to frequent channel switching may cause significant switching the incomplete-information scenario and provide a method to costs such as switching delay,additional wear and tear,etc.By compute the Bayesian NE.Finally,we prove that the price of comparison,re-selecting a new spatial route can yield fewer stability of the proposed game has a deterministic upper bound. switching costs.For instance,we can re-select a spatial route Keywords-Cognitive Radio Networks,Game Theory,Routing, that only consists of links whose assigned channels are not Spectrum Dynamics reclaimed,which incurs zero switching cost.However,it may lead to additional routing costs at the same time (e.g.,the new spatial route may consist of more hops).Consequently,there's I.INTRODUCTION a tradeoff between the two costs,which must be achieved by Cognitive Radio Networks(CRNs)have been proposed as switching routes in both spatial and frequency domains. Figure 1 shows a simple example that motivates the pro- a promising architecture for relieving spectrum shortages [1 where Secondary Users (SUs)can flexibly access Primary posed two-dimensional route switching.The number next to Users'(PUs')idle channels.Such Dynamic Spectrum Access each edge indicates the corresponding costs.Suppose a certain (DSA)significantly improves spectrum utilization but brings flow has source A and destination D.At the beginning, new challenges to the design of CRNs at the same time,one all channels are available,so the optimal path is obviously of which is spectrum mobility. AED with costs 2 (Figure 1 (a)).Now,suppose the channel used by link (A.E)is reclaimed by PUs (Figure 1 In CRNs.PUs can reclaim their licensed channels at any time due to their high priority in occupying channels,and (b)).Then we can choose to either switch the tuned channel SUs must cease their transmission'on those spectrum bands. on link (A,E)to an idle one (say channel 6)or select a new Hence,from SUs'perspective,spectrum availability is dynam- route A→B→C→D.If channel switching costs are 1 (Figure 1 (c)),then the former choice is preferred since ic due to PUs'uncertain channel reclamation behaviors,which the total costs would be 3 (additional switching cost 1 plus further causes the aforementioned spectrum mobiliry. original routing cost 2).By comparison,the total costs are 4 In the context of multi-hop CRNs where SUs act as re- if we choose the new route A→BC→D.However, if channel switching costs are 3 (Figure 1 (d)),then the total A preliminary version of this work was published in Proceedings of ACM MobiHoc 2013 [4].Q.Liang,X.Wang and X.Tian are with the costs incurred in the former case become 5,which implies Department of Electronic Engineering,Shanghai Jiao Tong University.China that rerouting is a better choice.Hence,depending on specific ({victor856,xwang8,xtian}@sjtu.edu.cn).F.Wu is with the Department of contexts,we should flexibly choose between channel switching Computer Science and Engineering,Shanghai Jiao Tong University,China (fwu@cs.sjtu.edu.cn).Q.Zhang is with the Department of Computer Science and rerouting. and Engineering.Hong Kong University of Science and Technology.Hong Kong (qianzh@cse.ust.hk). 2Since we focus on routing in the secondary network,we will use"CRN ISuch a method is also referred as the spectrum overlay mode.An and"secondary network"interchangeably in this paper. alterative way is to ensure that the amount of generated interference to PUs 3In the following,we will refer the selections of intermediate nodes and is below a certain threshold,namely the spectrum underlay mode [9].In this edges as sparial routes and the choices of channels used on the spatial routes paper,we only consider the overlay mode. as frequency routes

1 Two-Dimensional Route Switching in Cognitive Radio Networks: A Game-Theoretical Framework Qingkai Liang, Xinbing Wang, Xiaohua Tian, Fan Wu, Qian Zhang Abstract—In Cognitive Radio Networks (CRNs), Secondary Users (SUs) can flexibly access Primary Users’ (PUs’) idle spectrum bands but such spectrum opportunities are dynamic due to PUs’ uncertain activity patterns. In a multi-hop CRN consisting of SUs as relays, such spectrum dynamics will further cause the invalidity of pre-determined routes. In this paper, we investigate spectrum-mobility-incurred route-switching problems in both spatial and frequency domains for CRNs, where spatial switching determines which relays and links should be re-selected and frequency switching decides which channels ought to be re-assigned to the spatial routes. The proposed route-switching scheme not only avoids conflicts with PUs but also mitigates spectrum congestion. Meanwhile, tradeoffs between routing costs and channel switching costs are achieved. We further formulate the route-switching problem as the Route-Switching Game which is shown to be a potential game and has a pure Nash Equilibrium (NE). Accordingly, efficient algorithms for finding the NE and the ϵ−NE are proposed. Then we extend the proposed game to the incomplete-information scenario and provide a method to compute the Bayesian NE. Finally, we prove that the price of stability of the proposed game has a deterministic upper bound. Keywords—Cognitive Radio Networks, Game Theory, Routing, Spectrum Dynamics I. INTRODUCTION Cognitive Radio Networks (CRNs) have been proposed as a promising architecture for relieving spectrum shortages [1], where Secondary Users (SUs) can flexibly access Primary Users’ (PUs’) idle channels. Such Dynamic Spectrum Access (DSA) significantly improves spectrum utilization but brings new challenges to the design of CRNs at the same time, one of which is spectrum mobility. In CRNs, PUs can reclaim their licensed channels at any time due to their high priority in occupying channels, and SUs must cease their transmission1 on those spectrum bands. Hence, from SUs’ perspective, spectrum availability is dynam￾ic due to PUs’ uncertain channel reclamation behaviors, which further causes the aforementioned spectrum mobility. In the context of multi-hop CRNs where SUs act as re￾A preliminary version of this work was published in Proceedings of ACM MobiHoc 2013 [4]. Q. Liang, X. Wang and X. Tian are with the Department of Electronic Engineering, Shanghai Jiao Tong University, China ({victor856, xwang8, xtian}@sjtu.edu.cn). F. Wu is with the Department of Computer Science and Engineering, Shanghai Jiao Tong University, China (fwu@cs.sjtu.edu.cn). Q. Zhang is with the Department of Computer Science and Engineering, Hong Kong University of Science and Technology, Hong Kong (qianzh@cse.ust.hk). 1Such a method is also referred as the spectrum overlay mode. An alternative way is to ensure that the amount of generated interference to PUs is below a certain threshold, namely the spectrum underlay mode [9]. In this paper, we only consider the overlay mode. lays2 , spectrum mobility may further cause the break of pre￾established routes of incoming data flows, since the unavail￾ability of PUs’ channels disables the transmission over some links on those routes. To avoid conflicts with PUs and resume routing, each flow initiator can either inform intermediate SU relays of switching their accessing channels or re-select a new spatial route3 where channels are not reclaimed. However, the following tradeoff implies that two-dimensional route switching (i.e., the combination of both channel switching and spatial route re-selection) is a better choice. The advantage of channel switching is that it maintains the original optimal spatial route (e.g., a route with the fewest hops), which efficiently reduces routing costs, including transmission delay, energy consumption, etc. Unfortunately, frequent channel switching may cause significant switching costs such as switching delay, additional wear and tear, etc. By comparison, re-selecting a new spatial route can yield fewer switching costs. For instance, we can re-select a spatial route that only consists of links whose assigned channels are not reclaimed, which incurs zero switching cost. However, it may lead to additional routing costs at the same time (e.g., the new spatial route may consist of more hops). Consequently, there’s a tradeoff between the two costs, which must be achieved by switching routes in both spatial and frequency domains. Figure 1 shows a simple example that motivates the pro￾posed two-dimensional route switching. The number next to each edge indicates the corresponding costs. Suppose a certain flow has source A and destination D. At the beginning, all channels are available, so the optimal path is obviously A → E → D with costs 2 (Figure 1 (a)). Now, suppose the channel used by link (A, E) is reclaimed by PUs (Figure 1 (b)). Then we can choose to either switch the tuned channel on link (A, E) to an idle one (say channel 6) or select a new route A → B → C → D. If channel switching costs are 1 (Figure 1 (c)), then the former choice is preferred since the total costs would be 3 (additional switching cost 1 plus original routing cost 2). By comparison, the total costs are 4 if we choose the new route A → B → C → D. However, if channel switching costs are 3 (Figure 1 (d)), then the total costs incurred in the former case become 5, which implies that rerouting is a better choice. Hence, depending on specific contexts, we should flexibly choose between channel switching and rerouting. 2Since we focus on routing in the secondary network, we will use “CRN” and “secondary network” interchangeably in this paper. 3 In the following, we will refer the selections of intermediate nodes and edges as spatial routes and the choices of channels used on the spatial routes as frequency routes

3 0 A -Data Flow PU Base Statio Data Link SU Router D Flow Initiator Channel4 (a)original route and channel assignment (b)channel I is reclaimed by PUs A 0 A 0 Switch to Channel 6 D B h 3 (c)strategy update when switching costs are 1 (d)strategy undate wben switchin costs are 3 Fig.2.An example of the multi-hop and multi-flow CRN.Note that the Fig.1.An example of two-dimensional route switching. entire secondary network is within the transmission range of the PU base station,so the spectrum opportunities perceived at each SU are identical. In this paper,we propose Route-Switching Games to ad- idle)at each SU are identical in the entire network.This dress the above spectrum-mobility-incurred route-switching problem in CRNs.The contributions of this paper include the assumption is valid for many geographically-centric secondary following aspects. networks coexisting with powerful PU transceivers,like PU To our best knowledge,this paper is the first to investi- base stations in cellular networks,as is shown in Figure 2. Formally,the entire secondary network can be characterized gate spectrum-mobility-incurred route-switching problems in by a topological graph G=(V,E).Here,V is the set CRNs.Accounting for selections in both spatial and frequen- cy domains,our scheme not only avoids the conflicts with of nodes (SUs)and E is the set of edges,where an edge PUs but also mitigates spectrum congestion and achieves the exists between a pair of nodes (u,v)iff they're within the tradeoff between routing and channel switching costs. transmission range of each other,so an edge corresponds with We formulate the proposed problem as the Route- a data link.However,for a link to be able to sustain data Switching Game which is proved be a potential game.Ef- transmission,it must be allocated a certain channel.As our ficient algorithms for finding the Nash Equilibrium(NE)and focus is the route-switching problem,we suppose each link the e-NE are provided in this paper. was formerly assigned a certain licensed channel (but these We further study the game with incomplete information, pre-assigned channels may be reclaimed by PUs and become unavailable now).Here,we denote matrix A the indication of where players'parameters are private.In such a scenario,a Bayesian NE is proved to exist and an algorithm for calculating pre-assigned channels on different links.Specifically,Ae.j=1 the Bayesian NE is provided. implies that channel j was pre-assigned to link e and Ae.j=0 We compare the NE of this game with socially optimal otherwise. results in terms of social costs,namely the price of stability, which is upper-bounded by deterministic factors. B.Flow Model The remainder of this paper is organized as the following. Suppose there're M concurrent data flowss into the sec- We will first introduce the system model in section II.Next, ondary network (each flow is denoted by F,kM in sections III and IV,Route-Switching Games with complete {1,2,...,M)),and denote the source and destination of data and incomplete information will be demonstrated,respectively. flow Fk by a pair(Sk,D).For the efficiency and reliability Then we will analyze the price of stability in section V with of transmission,flow Fk segments its data into many smaller some additional discussions in section VI.Finally,simulation packets,each with size u.We denote the flow rate of F results,related works and conclusions will be given in sections by rk and assume that those data flows are from different VII,VIII and IX,respectively. initiators,each hoping to minimize its own costs.Beside, we suppose that nodes in the secondary network will always II.NETWORK MODEL honestly follow the routing plans developed by flow initiators. A.Architecture of Multi-hop CRNs Cases where "malicious"secondary nodes exist are left for We consider a multi-hop CRN where multiple SUs act as our future works. routers for incoming data flows,and there're C orthogonal and homogeneous channels accessible to SUs when they are C.Spectrum Mobility and Route Switching not occupied by PUs (each channel is denoted by jC= When high-priority PUs reclaim their licensed channels, {1,2,..,C)).For the simplicity of analysis,we assume the SUs must cease their transmission on those spectrum bands, entire secondary network lies in the same"collision domain" which causes spectrum mobility.Here,we denote I the set with PUs4,i.e.,the perceived channel states (either busy or 5We assume those data flows can last for a period of time like minutes or 4Note that our scheme can also be modified to incorporate the spatial hours,which is particularly suitable for characterizing multimedia streaming. diversity of PUs'spectrums in secondary networks. P2P downloading,etc

2 A B C D E 1 2 0 1 Channel 1 Channel 4 Channel 3 Channel 5 A B C D E 1 2 0 1 2 Switch to Channel 6 Channel 4 Channel 3 A B C D E 1 2 0 1 2 Channel 1 Channel 3 Channel 2 Channel 4 hanne A B C D E 1 2 1 2 Channel 4 Channel 3 Channel 1 annel Channel 5 Channel 5 Channel 5 (c) strategy update when switching costs are 1 (d) strategy update when switching costs are 3 0 (a) original route and channel assignment (b) channel 1 is reclaimed by PUs Channel 2 Channel 2 2 Channel 2 Fig. 1. An example of two-dimensional route switching. In this paper, we propose Route-Switching Games to ad￾dress the above spectrum-mobility-incurred route-switching problem in CRNs. The contributions of this paper include the following aspects. • To our best knowledge, this paper is the first to investi￾gate spectrum-mobility-incurred route-switching problems in CRNs. Accounting for selections in both spatial and frequen￾cy domains, our scheme not only avoids the conflicts with PUs but also mitigates spectrum congestion and achieves the tradeoff between routing and channel switching costs. • We formulate the proposed problem as the Route￾Switching Game which is proved be a potential game. Ef- ficient algorithms for finding the Nash Equilibrium (NE) and the ϵ−NE are provided in this paper. • We further study the game with incomplete information, where players’ parameters are private. In such a scenario, a Bayesian NE is proved to exist and an algorithm for calculating the Bayesian NE is provided. • We compare the NE of this game with socially optimal results in terms of social costs, namely the price of stability, which is upper-bounded by deterministic factors. The remainder of this paper is organized as the following. We will first introduce the system model in section II. Next, in sections III and IV, Route-Switching Games with complete and incomplete information will be demonstrated, respectively. Then we will analyze the price of stability in section V with some additional discussions in section VI. Finally, simulation results, related works and conclusions will be given in sections VII, VIII and IX, respectively. II. NETWORK MODEL A. Architecture of Multi-hop CRNs We consider a multi-hop CRN where multiple SUs act as routers for incoming data flows, and there’re C orthogonal and homogeneous channels accessible to SUs when they are not occupied by PUs (each channel is denoted by j ∈ C = {1, 2, · · · , C}). For the simplicity of analysis, we assume the entire secondary network lies in the same “collision domain” with PUs4 , i.e., the perceived channel states (either busy or 4Note that our scheme can also be modified to incorporate the spatial diversity of PUs’ spectrums in secondary networks. PU Base Station SU Router Flow Initiator F1 F2 F3 F4 F5 Data Flow Data Link Fig. 2. An example of the multi-hop and multi-flow CRN. Note that the entire secondary network is within the transmission range of the PU base station, so the spectrum opportunities perceived at each SU are identical. idle) at each SU are identical in the entire network. This assumption is valid for many geographically-centric secondary networks coexisting with powerful PU transceivers, like PU base stations in cellular networks, as is shown in Figure 2. Formally, the entire secondary network can be characterized by a topological graph G = (V, E). Here, V is the set of nodes (SUs) and E is the set of edges, where an edge exists between a pair of nodes (u, v) iff they’re within the transmission range of each other, so an edge corresponds with a data link. However, for a link to be able to sustain data transmission, it must be allocated a certain channel. As our focus is the route-switching problem, we suppose each link was formerly assigned a certain licensed channel (but these pre-assigned channels may be reclaimed by PUs and become unavailable now). Here, we denote matrix A the indication of pre-assigned channels on different links. Specifically, Ae,j = 1 implies that channel j was pre-assigned to link e and Ae,j = 0 otherwise. B. Flow Model Suppose there’re M concurrent data flows5 into the sec￾ondary network (each flow is denoted by Fk, k ∈ M = {1, 2, · · · , M}), and denote the source and destination of data flow Fk by a pair (Sk, Dk). For the efficiency and reliability of transmission, flow Fk segments its data into many smaller packets, each with size µk. We denote the flow rate of Fk by rk and assume that those data flows are from different initiators, each hoping to minimize its own costs. Beside, we suppose that nodes in the secondary network will always honestly follow the routing plans developed by flow initiators. Cases where “malicious” secondary nodes exist are left for our future works. C. Spectrum Mobility and Route Switching When high-priority PUs reclaim their licensed channels, SUs must cease their transmission on those spectrum bands, which causes spectrum mobility. Here, we denote Γ the set 5We assume those data flows can last for a period of time like minutes or hours, which is particularly suitable for characterizing multimedia streaming, P2P downloading, etc

of channels that are currently unavailable to SUs due to E.Cost Model PUs'reclamation.In practice,I can be obtained by flow We model the costs of each data flow by (i)routing costs initiators without incurring significant overhead costs through incurred by relaying packets on the established route,and(ii) our implementation (see section VI-B). switching costs consumed to change the tuned channels over Unlike many earlier works that proposed statistical models certain links. to characterize PUs'reclaiming activities [9].[10],we do not 1)Routing Costs:For fow Fi,its routing costs RCk are predict PUs'behaviors,i.e.,our scheme is reactive,since the modeled by precision of predictions still remains a major problem.Besides, RCk=DCk ECk, route-switching schemes should provide routing reliability as much as possible,instead of probabilistic results,because the where DCk corresponds to the costs incurred by end-to-end focus of the proposed mechanism is exactly to handle the delay from source Sk to destination D,and ECk charac- negatives effects of spectrum uncertainty,which is the other terizes the costs resulting from energy consumption used for reason why we don't choose proactive models. relaying the packets of F. As is mentioned in the introduction part,in face of spectrum We first characterize delay costs.Under the interference mobility,routes must be switched in both spatial and frequency model mentioned above.significant contention delay will be domains so as to avoid conflicts with PUs,mitigate congestion, incurred if channels are congested since SUs must contend and balance routing costs and channel switching costs (see and wait for transmission opportunities.Note that there's no section II-E for the formal definitions).Here,we use a 3-D queuing delay in our model because constraint (2)implies matrix X to characterize the new selection of spatial routes different flows actually use different channels(thus different and channel assignment,which is also the decision variable queues)at the same node.Hence,if we further neglect other in the considered problem.Specifically,its elementX=1 minor delay like propagation delay,then contention delay can when link e is included in the new spatial route of data flow F be regarded as a rough estimation of the overall one-hop delay. and channel j is re-assigned to this link (0otherwise). As is typical of many random access protocols [24].[25]. we make the following assumption:within the contention D.Interference Model and Constraints window,a certain link and all its interfering links have the We use the protocol interference model [7].where the same probability of wining the access to a certain channel transmission in channel j over link e succeeds if all potential jC.Following the methods provided in [29]-[31],we can interferers in the interference neighborhood of link e remain obtain an approximate expression for the expected contention silent in channel j for the transmission duration.Here,the delay within one hop,which characterizes the expected waiting interference neighborhood of link e,i.e.,I(e),is the set of time before flow Fk gets the opportunity to transmit one packet links whose end nodes have interference links or data links in channel j over link e: incident on the end nodes of e.Further,when channel j is perceived idle over link e,the contention window is activated 入e=ie∑∑Xt,wk, (4) and link e will contend for the transmission opportunities with e'∈I(e)keM all interfering links in l(e)(specifically,it's the transmitter on where de.;is a constant related to link e and channel j.Without one end of link e that executes the contention).This model loss of generality,we can let 6e.;-1 in the rest of this resembles CSMA/CA in IEEE 802.11.based on an RTS-CTS- paper,but our analysis carries over arbitrary values of 6e.j. Data-ACK sequence. Besides,in (4),we define wk uk/rk,i.e.,the amount of Then we introduce the set of constraints in our model.First time required by flow F for transmitting one packet.The of all,any reclaimed channels cannot be assigned,i.e., derivation of equation(4)is beyond the scope of this paper, X=0,j∈T,e∈E,k∈M (1) so we omit it for brevity.The intuition behind equation(4) Besides,we assume that any channel can only be assigned to at is explained as the following.in equation (4)represents the traffic demands (for transmission time)in most one flow over the same link,considering the significant channel j over link e'imposed by all passing data flows,and co-channel collisions and interference incurred on the same thus equation (4)corresponds to the aggregate traffic demands link.This yields the constraint in channel j from the entire interference neighborhood of link ∑X≤1，e∈E,jeC, (2) e.Generally speaking,Xe.j reflects the congestion level of kEM channel j perceived over link e,so delay costs can also be Additionally,we also have the following radio constraint: interpreted as the congestion costs in our model.As a result, ∑∑∑x≤au,w∈V although equation (4)is only an approximation to one-hop (3) delay.it precisely reflects the root of delay,namely network e∈E(v)kEM jEC congestion.In this sense,it is as desired as the precise delay where E(v)is the set of edges incident on node v and o is expression which may be difficult to characterize in reality. number of radios that node v equips.This constraint shows For denoting simplicity,we introduce a 0-1 indicator de.e that the number of channels to which a certain node (SU) to imply the interference relationship.Specifically,ee=1 tunes should not exceed its radio limitation.By the above indicates that link e'is in the interference neighborhood of e. three constraints,the feasible set S of this problem is defined Note that 0e.e=0 for any e EE and we consider mutual inter- to be the set of possible solutions that satisfy (1),(2)and(3). ference,which means that 0e.=0e.Besides,interference

3 of channels that are currently unavailable to SUs due to PUs’ reclamation. In practice, Γ can be obtained by flow initiators without incurring significant overhead costs through our implementation (see section VI-B). Unlike many earlier works that proposed statistical models to characterize PUs’ reclaiming activities [9], [10], we do not predict PUs’ behaviors, i.e., our scheme is reactive, since the precision of predictions still remains a major problem. Besides, route-switching schemes should provide routing reliability as much as possible, instead of probabilistic results, because the focus of the proposed mechanism is exactly to handle the negatives effects of spectrum uncertainty, which is the other reason why we don’t choose proactive models. As is mentioned in the introduction part, in face of spectrum mobility, routes must be switched in both spatial and frequency domains so as to avoid conflicts with PUs, mitigate congestion, and balance routing costs and channel switching costs (see section II-E for the formal definitions). Here, we use a 3-D matrix X to characterize the new selection of spatial routes and channel assignment, which is also the decision variable in the considered problem. Specifically, its element Xk e,j = 1 when link e is included in the new spatial route of data flow Fk and channel j is re-assigned to this link (Xk e,j = 0 otherwise). D. Interference Model and Constraints We use the protocol interference model [7], where the transmission in channel j over link e succeeds if all potential interferers in the interference neighborhood of link e remain silent in channel j for the transmission duration. Here, the interference neighborhood of link e, i.e., I(e), is the set of links whose end nodes have interference links or data links incident on the end nodes of e. Further, when channel j is perceived idle over link e, the contention window is activated and link e will contend for the transmission opportunities with all interfering links in I(e) (specifically, it’s the transmitter on one end of link e that executes the contention). This model resembles CSMA/CA in IEEE 802.11, based on an RTS-CTS￾Data-ACK sequence. Then we introduce the set of constraints in our model. First of all, any reclaimed channels cannot be assigned, i.e., Xk e,j = 0, ∀j ∈ Γ, e ∈ E, k ∈ M. (1) Besides, we assume that any channel can only be assigned to at most one flow over the same link, considering the significant co-channel collisions and interference incurred on the same link. This yields the constraint ∑ k∈M Xk e,j ≤ 1, ∀e ∈ E, j ∈ C. (2) Additionally, we also have the following radio constraint: ∑ e∈E(v) ∑ k∈M ∑ j∈C Xk e,j ≤ αv, ∀v ∈ V, (3) where E(v) is the set of edges incident on node v and αv is number of radios that node v equips. This constraint shows that the number of channels to which a certain node (SU) tunes should not exceed its radio limitation. By the above three constraints, the feasible set S of this problem is defined to be the set of possible solutions that satisfy (1), (2) and (3). E. Cost Model We model the costs of each data flow by (i) routing costs incurred by relaying packets on the established route, and (ii) switching costs consumed to change the tuned channels over certain links. 1) Routing Costs: For flow Fk, its routing costs RCk are modeled by RCk = DCk + ECk, where DCk corresponds to the costs incurred by end-to-end delay from source Sk to destination Dk, and ECk charac￾terizes the costs resulting from energy consumption used for relaying the packets of Fk. We first characterize delay costs. Under the interference model mentioned above, significant contention delay will be incurred if channels are congested since SUs must contend and wait for transmission opportunities. Note that there’s no queuing delay in our model because constraint (2) implies different flows actually use different channels (thus different queues) at the same node. Hence, if we further neglect other minor delay like propagation delay, then contention delay can be regarded as a rough estimation of the overall one-hop delay. As is typical of many random access protocols [24], [25], we make the following assumption: within the contention window, a certain link and all its interfering links have the same probability of wining the access to a certain channel j ∈ C. Following the methods provided in [29]–[31], we can obtain an approximate expression for the expected contention delay within one hop, which characterizes the expected waiting time before flow Fk gets the opportunity to transmit one packet in channel j over link e: λe,j = δe,j ∑ e ′∈I(e) ∑ k∈M Xk e ′ ,jωk, (4) where δe,j is a constant related to link e and channel j. Without loss of generality, we can let δe,j = 1 in the rest of this paper, but our analysis carries over arbitrary values of δe,j . Besides, in (4), we define ωk = µk/rk, i.e., the amount of time required by flow Fk for transmitting one packet. The derivation of equation (4) is beyond the scope of this paper, so we omit it for brevity. The intuition behind equation (4) is explained as the following. ∑ k∈M Xk e ′ ,jωk in equation (4) represents the traffic demands (for transmission time) in channel j over link e ′ imposed by all passing data flows, and thus equation (4) corresponds to the aggregate traffic demands in channel j from the entire interference neighborhood of link e. Generally speaking, λe,j reflects the congestion level of channel j perceived over link e, so delay costs can also be interpreted as the congestion costs in our model. As a result, although equation (4) is only an approximation to one-hop delay, it precisely reflects the root of delay, namely network congestion. In this sense, it is as desired as the precise delay expression which may be difficult to characterize in reality. For denoting simplicity, we introduce a 0-1 indicator θe,e′ to imply the interference relationship. Specifically, θe,e′ = 1 indicates that link e ′ is in the interference neighborhood of e. Note that θe,e = 0 for any e ∈ E and we consider mutual inter￾ference, which means that θe,e′ = θe ′ ,e. Besides, interference

￥ caused by one's own transmission over other interfering links Therefore,the total channel switching costs associated with is neglected for the tractability of analysis,since recent liter- F.'s strategy are atures (e.g.,[17,[18)have suggested such interference can be mitigated significantly by exploiting the self-interference SCk=∑∑XtYe (8) cancellation technology in relay systems.Therefore,we can eEE jEC rewrite the expected one-hop delay perceived by Fk when it where we define Ye.i=(1-Ae.j)y.Corresponding to the is transmitting in channel j over link e by: above discussion,equation(8)implies that only when Ae.j= =∑∑Xwee, 0 and=1 (i.e..link e did not use channel j in the (5) past,but now this channel is allocated to e according to F's e'∈Ek'EMk strategy),switching costs are incurred. where Mx=M\k).Further,we can characterize the So far,we have defined two types of major costs in the expected end-to-end delay as the sum of hop-by-hop delay. network:routing costs (i.e.,delay costs plus energy costs) Then the delay costs of flow Fk are given by and switching costs.In reality,the two types of costs conflict with each other and cannot be simultaneously minimized DCk=Pa∑∑X (6) (see section VI-A for the detailed discussion).Hence,when e∈EjEC designing the overall cost function,we aim at achieving the which is proportional to the expected end-to-end delay.Here, tradeoff between the two types of costs.Specifically,we model flow F's overall cost function as: Pa is a constant reflecting the revenue lost per unit of delay. Next,we consider energy costs which characterize power TCk =RRCk +nsSCk (9) consumption used for relaying packets.Under our interference model,when one SU transmits in channel j over link e, Here,and s are two non-negative system parameters characterizing the relative importance of routing costs and other SUs within I(e)must remain silent in channel j,so the SINR perceived at each SU receiver is merely dependent on switching costs,respectively.For example,if nodes in the secondary network are energy-constrained,we tend to set R transmission power,intrinsic channel quality and geographical to be a large value while keeping s small:if the CRN is conditions (e.g.,path loss).Noticing the above fact,we model power consumption as a general function ()(and delay-tolerant and energy-abundant but has a low tolerance for short),which neatly captures the influence of flow rates, for channel switching,we prefer a small R and a large s. channel quality and geographical conditions on power con- In fact,the two parameters provide us with the flexibility of balancing routing costs and switching costs.Particularly,if sumption.Note thatcan be of different forms,depending on the features of wireless networks5.Then,the energy costs R >0 and s =0,routing costs are minimized;if R =0 and s >0,switching costs are minimized;if R >0 and of flow F are shown as: s >0,a tradeoff (of a certain degree)is obtained. EC=P.∑∑XtP (7) Additionally,without loss of generality,we assume that eEE jec Pa=Pe=1 in the rest of this paper.With trivial changes, our analysis can be easily applied to the case where these Similarly,P is a constant reflecting the revenue lost per unit parameters take arbitrarily feasible values. of power consumption. 2)Switching Costs:Different from the above routing costs, III.ROUTE-SWITCHING GAMES WITH COMPLETE switching costs characterize the potential expense used for INFORMATION channel handoff.Here,we use y to indicate the overall revenue lost per channel switching,which may include (i)additional From equation (5),we can obviously observe that a cer- energy consumption used for sensing and establishing new tain flow's delay costs are also dependent on others'route- switching strategies,so we formulate the above problem as connections,(ii)switching delay,(iii)increased wear and tear during channel reconfiguration,etc.For example,in terms of Routing-Switching Games,where players (i.e.,flow initiators) switching delay,many practical mobile systems like Qualcom- distributively and selfishly switch their two-dimensional routes m's MediaFLO,show switching delay around 1.5s [26].Note in face of spectrum mobility,aiming at minimizing their own that y includes the costs of both ON-OFF switching (tearing overall cost functions down the old channel connection)and OFF->ON switching (establishing the new channel connection),so the two types A.Game Formulation of switching costs can be seen as being incurred altogether in Under complete information,each player's information (i.e., either switching scenario.In this paper,we assume the overall data rate rk and packet size uk,Vk EM)is known to others. switching costsy are incurred only in the OFF-ON transition. We can use a tuple g ={G,A,I,r,u,TC,S}to denote the Route-Switching Game with complete information.Here 6For example,a possible expression ofis based on Shannon Formula the meanings of G.A and I have been explained in section in the presence of AWGN.i.e..rk=Wj log(1+d/2),where Wj is the bandwidth of channel j.is the variance of AWGN in channel L.T={r,·,rM}andμ={1，…，4M}are publicly jover link e.d is the distance between the transmitter and the receiver,a is known parameter vectors of flows.TC is the set of players' the attenuation coefficient,and is the corresponding transmission power. cost functions,shown in (9).S={(e,j)le E,jc}is In this case,power consumption can be readily obtained. the two-dimensional strategy space.In this paper,we consider

4 caused by one’s own transmission over other interfering links is neglected for the tractability of analysis, since recent liter￾atures (e.g., [17], [18]) have suggested such interference can be mitigated significantly by exploiting the self-interference cancellation technology in relay systems. Therefore, we can rewrite the expected one-hop delay perceived by Fk when it is transmitting in channel j over link e by: λ k e,j = ∑ e ′∈E ∑ k′∈Mk Xk ′ e ′ ,jωk′θe,e′ , (5) where Mk = M\{k}. Further, we can characterize the expected end-to-end delay as the sum of hop-by-hop delay. Then the delay costs of flow Fk are given by DCk = Pd ∑ e∈E ∑ j∈C Xk e,jλ k e,j , (6) which is proportional to the expected end-to-end delay. Here, Pd is a constant reflecting the revenue lost per unit of delay. Next, we consider energy costs which characterize power consumption used for relaying packets. Under our interference model, when one SU transmits in channel j over link e, other SUs within I(e) must remain silent in channel j, so the SINR perceived at each SU receiver is merely dependent on transmission power, intrinsic channel quality and geographical conditions (e.g., path loss). Noticing the above fact, we model power consumption as a general function φe,j (rk) (and φ k e,j for short), which neatly captures the influence of flow rates, channel quality and geographical conditions on power con￾sumption. Note that φ k e,j can be of different forms, depending on the features of wireless networks6 . Then, the energy costs of flow Fk are shown as: ECk = Pe ∑ e∈E ∑ j∈C Xk e,jφ k e,j . (7) Similarly, Pe is a constant reflecting the revenue lost per unit of power consumption. 2) Switching Costs: Different from the above routing costs, switching costs characterize the potential expense used for channel handoff. Here, we use γ to indicate the overall revenue lost per channel switching, which may include (i) additional energy consumption used for sensing and establishing new connections, (ii) switching delay, (iii) increased wear and tear during channel reconfiguration, etc. For example, in terms of switching delay, many practical mobile systems like Qualcom￾m’s MediaFLO, show switching delay around 1.5s [26]. Note that γ includes the costs of both ON→OFF switching (tearing down the old channel connection) and OFF→ON switching (establishing the new channel connection), so the two types of switching costs can be seen as being incurred altogether in either switching scenario. In this paper, we assume the overall switching costs γ are incurred only in the OFF→ON transition. 6For example, a possible expression of φ k e,j is based on Shannon Formula in the presence of AWGN, i.e., rk = Wj log(1 + φ k e,jd−α/σ2 e,j ), where Wj is the bandwidth of channel j, σ 2 e,j is the variance of AWGN in channel j over link e, d is the distance between the transmitter and the receiver, α is the attenuation coefficient, and φ k e,j is the corresponding transmission power. In this case, power consumption φ k e,j can be readily obtained. Therefore, the total channel switching costs associated with Fk’s strategy are SCk = ∑ e∈E ∑ j∈C Xk e,jγe,j , (8) where we define γe,j = (1 − Ae,j )γ. Corresponding to the above discussion, equation (8) implies that only when Ae,j = 0 and Xk e,j = 1 (i.e., link e did not use channel j in the past, but now this channel is allocated to e according to Fk’s strategy), switching costs are incurred. So far, we have defined two types of major costs in the network: routing costs (i.e., delay costs plus energy costs) and switching costs. In reality, the two types of costs conflict with each other and cannot be simultaneously minimized (see section VI-A for the detailed discussion). Hence, when designing the overall cost function, we aim at achieving the tradeoff between the two types of costs. Specifically, we model flow Fk’s overall cost function as: T Ck = ΩRRCk + ΩSSCk. (9) Here, ΩR and ΩS are two non-negative system parameters characterizing the relative importance of routing costs and switching costs, respectively. For example, if nodes in the secondary network are energy-constrained, we tend to set ΩR to be a large value while keeping ΩS small; if the CRN is delay-tolerant and energy-abundant but has a low tolerance for channel switching, we prefer a small ΩR and a large ΩS. In fact, the two parameters provide us with the flexibility of balancing routing costs and switching costs. Particularly, if ΩR > 0 and ΩS = 0, routing costs are minimized; if ΩR = 0 and ΩS > 0, switching costs are minimized; if ΩR > 0 and ΩS > 0, a tradeoff (of a certain degree) is obtained. Additionally, without loss of generality, we assume that Pd = Pe = 1 in the rest of this paper. With trivial changes, our analysis can be easily applied to the case where these parameters take arbitrarily feasible values. III. ROUTE-SWITCHING GAMES WITH COMPLETE INFORMATION From equation (5), we can obviously observe that a cer￾tain flow’s delay costs are also dependent on others’ route￾switching strategies, so we formulate the above problem as Routing-Switching Games, where players (i.e., flow initiators) distributively and selfishly switch their two-dimensional routes in face of spectrum mobility, aiming at minimizing their own overall cost functions. A. Game Formulation Under complete information, each player’s information (i.e., data rate rk and packet size µk, ∀k ∈ M) is known to others. We can use a tuple G = {G, A, Γ, r, µ, T C, S} to denote the Route-Switching Game with complete information. Here, the meanings of G, A and Γ have been explained in section II. r = {r1, · · · , rM} and µ = {µ1, · · · , µM} are publicly￾known parameter vectors of flows. T C is the set of players’ cost functions, shown in (9). S = {(e, j)|e ∈ E, j ∈ C} is the two-dimensional strategy space. In this paper, we consider

5 the symmetric game where all players have the same strategy Property I:Every finite potential gamell has at least one space.Further,we denote s ={s1,...,sM}the strategy pure Nash Equilibrium. profile,where sk={(e,j)=1}is flow Fk's From the definition of the potential function,we can observe strategy?.Note that the different kinds of costs of flow Fk that the minimum of the potential function corresponds to as well as the value of;depend on the strategy profile s.a pure NE in the minimum game.That is,no player can so we denote them by RCk(s),DCk(s),ECk(s),SCk(s), unilaterally decrease its costs at the minimum of the potential TCk(s)andλ.，(s),respectivelys. function.otherwise the reduction of this player's costs will In addition.it's worthy mentioning that the above formu- also lead to the reduction of the potential function,violating lation does not impose any constraints on the connectivity the definition of the minimum. of switched routes but such an omission won't influence Property 2:Every finite potential game has the Finite any of the following analytical results.Instead,we guarantee Improvement Property (FIP). the connectivity through our algorithm implementation (see Theorem 3 in section III-C). The meaning of FIP is as the following.Initially,each player Finally in this subsection,we give the definition of the Nash can randomly select its own strategy.Then every player rotates Equilibrium,which will be frequently discussed. to improve its strategy by reducing the potential function with Definition I (Nash Equilibrium,NE):A strategy profile others'strategies fixed.After finite improvement steps,the s*=(si,s2,..,si)is a Nash Equilibrium if for any player potential function will reach the minimum,and thus an NE F(Vk E M)and its any strategy sk CS, is derived.FIP actually provides us with a feasible method to compute an NE in the potential game,which will be further TCk(sk;sk)<TCk(sk;sk), utilized in section III-C. Property 3:Every finite potential game has at least one pure where sk is the strategy profile s*excluding s.By def- e-Nash Equilibrium. inition,no player can reduce its own costs by unilaterally changing the strategy at the equilibrium. We temporarily skip the explanation of Property 3.Further discussions will be given in section II-D. Proofs to the three properties can be found in [33]. B.Potential Game The potential game [33]is a relatively new game-theoretical model which can characterize a wide range of games,includ- ing the classical congestion game [32].It has already demon- C.Existence and Computation of the NE strated its importance through many successful applications in practical problems like spatial spectrum access [19][20], In this subsection,we will first show that the proposed gateway selections [21],etc. Route-Switching Game is essentially a potential game.Then In the rest of this subsection,we will briefly introduce the an algorithm for computing the NE will be provided. concept of the potential game and its properties,which will Theorem I:Under complete information,the proposed be further exploited in this paper. Route-Switching Game is a finite potential game which has Definition 2(Potential Game):A game is referred as the the following potential function: potential game if and only if there exists a potential function in the game. Φ(s)= Definition 3 (Potential Function):A function (s)is the >wk[RDCx(s)+2RECk(s)+2sSCk(s)]. kEM potential function for the minimum gamelo g if for any (10) strategy profile s,any player Fk(Vk E M)and its any two Proof:It's obvious that the proposed Route-Switching strategies sk,sS Game is finite,and we only prove that (10)is a potential TCk(sk;s-k)-TCk(sk;s-k)<0 function.Consider an improvement from strategy profile s to →Φ(sk;s-k)-Φ(Sk;s-k)<0. q.The 0-1 strategy indications corresponding to s and q are and respectively.The only difference between s That is,if any player can unilaterally reduce its costs,the value and g is that player Fk improves its strategy from sk to qk, of the potential function will also be reduced.Potential games which implies s_k=q-k and have many ideal properties,and we mainly use three of them. 7In this paper,each player's (say flow F's)strategy can be expressed in TCk(s)>TCk(q). two forms:sk and the corresponding 0-1 indication (eEE,jC).The two forms are equivalent and will be used interchangeably in the following. Note that (e,j)E sk if and only if=1. At the same time,we define: &To be more specific.DCk.RCk and TC are dependent on the entire strategy profile s;is dependent on the entire profile expects EC and SC&are only relevant to flow Fi's own strategy sk.For denoting simplicity, se(s):=wk[ORXcj(s)+2Rpej+20sYejl. they are uniformly expressed as the function of s. 9We only consider the pure NE throughout this paper. 10A game is a minimum game if players tend to minimize their cost 1A game is said to be finite when each player has a finite number of functions. options and the number of players is also finite

5 the symmetric game where all players have the same strategy space. Further, we denote s = {s1, · · · , sM} the strategy profile, where sk = {(e, j) ∈ S|Xk e,j = 1} is flow Fk’s strategy7 . Note that the different kinds of costs of flow Fk as well as the value of λ k e,j depend on the strategy profile s, so we denote them by RCk(s), DCk(s), ECk(s), SCk(s), T Ck(s) and λ k e,j (s), respectively8 . In addition, it’s worthy mentioning that the above formu￾lation does not impose any constraints on the connectivity of switched routes but such an omission won’t influence any of the following analytical results. Instead, we guarantee the connectivity through our algorithm implementation (see Theorem 3 in section III-C). Finally in this subsection, we give the definition of the Nash Equilibrium9 , which will be frequently discussed. Definition 1 (Nash Equilibrium, NE): A strategy profile s ∗ = (s ∗ 1 , s∗ 2 , · · · , s∗ M) is a Nash Equilibrium if for any player Fk (∀k ∈ M) and its any strategy sk ⊆ S, T Ck(s ∗ k ; s ∗ −k ) ≤ T Ck(sk; s ∗ −k ), where s ∗ −k is the strategy profile s ∗ excluding s ∗ k . By def￾inition, no player can reduce its own costs by unilaterally changing the strategy at the equilibrium. B. Potential Game The potential game [33] is a relatively new game-theoretical model which can characterize a wide range of games, includ￾ing the classical congestion game [32]. It has already demon￾strated its importance through many successful applications in practical problems like spatial spectrum access [19] [20], gateway selections [21], etc. In the rest of this subsection, we will briefly introduce the concept of the potential game and its properties, which will be further exploited in this paper. Definition 2 (Potential Game): A game is referred as the potential game if and only if there exists a potential function in the game. Definition 3 (Potential Function): A function Φ(s) is the potential function for the minimum game10 G if for any strategy profile s, any player Fk (∀k ∈ M) and its any two strategies sk, s′ k ⊆ S T Ck(s ′ k ; s−k) − T Ck(sk; s−k) < 0 ⇒ Φ(s ′ k ; s−k) − Φ(sk; s−k) < 0. That is, if any player can unilaterally reduce its costs, the value of the potential function will also be reduced. Potential games have many ideal properties, and we mainly use three of them. 7 In this paper, each player’s (say flow Fk’s) strategy can be expressed in two forms: sk and the corresponding 0-1 indication Xk e,j (e ∈ E, j ∈ C). The two forms are equivalent and will be used interchangeably in the following. Note that (e, j) ∈ sk if and only if Xk e,j = 1. 8To be more specific, DCk, RCk and T Ck are dependent on the entire strategy profile s; λ k e,j is dependent on the entire profile expect sk; ECk and SCk are only relevant to flow Fk’s own strategy sk. For denoting simplicity, they are uniformly expressed as the function of s. 9We only consider the pure NE throughout this paper. 10A game is a minimum game if players tend to minimize their cost functions. Property 1: Every finite potential game11 has at least one pure Nash Equilibrium. From the definition of the potential function, we can observe that the minimum of the potential function corresponds to a pure NE in the minimum game. That is, no player can unilaterally decrease its costs at the minimum of the potential function, otherwise the reduction of this player’s costs will also lead to the reduction of the potential function, violating the definition of the minimum. Property 2: Every finite potential game has the Finite Improvement Property (FIP). The meaning of FIP is as the following. Initially, each player can randomly select its own strategy. Then every player rotates to improve its strategy by reducing the potential function with others’ strategies fixed. After finite improvement steps, the potential function will reach the minimum, and thus an NE is derived. FIP actually provides us with a feasible method to compute an NE in the potential game, which will be further utilized in section III-C. Property 3: Every finite potential game has at least one pure ϵ-Nash Equilibrium. We temporarily skip the explanation of Property 3. Further discussions will be given in section III-D. Proofs to the three properties can be found in [33]. C. Existence and Computation of the NE In this subsection, we will first show that the proposed Route-Switching Game is essentially a potential game. Then an algorithm for computing the NE will be provided. Theorem 1: Under complete information, the proposed Route-Switching Game is a finite potential game which has the following potential function: Φ(s) = ∑ k∈M ωk[ΩRDCk(s) + 2ΩRECk(s) + 2ΩSSCk(s)]. (10) Proof: It’s obvious that the proposed Route-Switching Game is finite, and we only prove that (10) is a potential function. Consider an improvement from strategy profile s to q. The 0-1 strategy indications corresponding to s and q are Xk e,j and X′k e,j , respectively. The only difference between s and q is that player Fk improves its strategy from sk to qk, which implies s−k = q−k and T Ck(s) > T Ck(q). At the same time, we define: ζ k e,j (s) := ωk[ΩRλ k e,j (s) + 2ΩRφ k e,j + 2ΩSγe,j ]. 11A game is said to be finite when each player has a finite number of options and the number of players is also finite