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)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)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) 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

6 Thus we can derive By summing(12)and(15),we finally obtain that Φ(s)-Φ(q) (s)-Φ(q) =∑(s)-∑∑c() =∑∑X,20RX(s)+20rp+22sel k'∈M(e,j)es k'∈M(e,)eq eEE jEC =(∑()-∑c点g)） ∑∑Xwk22r(q)+22r9,+22sel (e.j)Esk (e.j)Eqk eEE jEC +(∑∑)-∑ ∑c(g) =2wk[TCk(s)-TCk(q)]>0. (16) K'EMk (e.j)Esk K'EMk (e.j)Eqk (11)Hence,we have proved that(10)is a potential function of the proposed game. ■ For the first term in the above equation,we can further write According to Theorem 1 and Property 1 of general potential out its explicit expression games,we can immediately conclude the following result. ∑c,(s)-∑c,g Theorem 2:There exists a Nash Equilibrium in the Route- Switching Game with complete information,and this NE (e.j)Esk (e,j)Eqk minimizes the potential function in(10). =∑∑xtjwk[SRX()+20rp+22sel Next,we design an algorithm to reach the NE in Theorem eEEjEC 2,shown as Algorithm 1.Note that each player locally runs -∑∑Xwk2RX(q)+22r+22s7e1 this algorithm to determine its own best strategy at the NE,by eEE jEC simulating other players'possible actions(step 3 to step 18). (12) This is also referred as the Fictitious Play Process in game theory [33].The accuracy of Fictitious Play is dependent on For the second term in (11),we first notice that sk=qk the degree of known information about other players.Under for anyk'∈Mk,i.e., complete information,every player's parameters are precisely known by others,so the Fictitious Play Process will converge X=X,K∈Mk,e∈E,jeC. (13) to the real play process.However,Fictitious Play will deviate from the reality under incomplete information (but it still Then the second term can be equivalently written as converges),as will be further demonstrated in section IV. ∑∑∑xco)-∑∑∑Xsc点(g) Essentially,Algorithm I is an iterative algorithm following k'∈Mee∈EjeC k'EMke∈EjEC FIP.Its major part is the strategy improvement (or update), which is done by first converting the reduction of the potential =∑∑∑xc()- function into finding the shortest path in an undirected graph k'∈keEE jEc and then applying the well-known Dijsktra Algorithm to find =∑∑∑xePr,(s)-Aql such a path.Step 9 in Algorithm 1 handles the three constraints k'EMke∈EjEC mentioned in section II-D,where (e,j)A if letting1 =∑∑∑∑X)wkw0e,e2r(X态，-X5,): will violate any of the three constraints under the strategy K'EMk jEC eEEe'EE profile in that loop.Variable m in the algorithm acts like (14) a counter recording the consecutive times for which players cannot reduce the value of the potential function,and the Note that the derivation of(14)exploits the fact that stop condition (step 18)indicates that all M players cannot reduce the potential function anymore,where the minimum A(s)-X(q)=>wx0c.e(X-x). point (i.e.,the NE)is reached.Note that a player's strategy is e'∈E updated only when it can reduce the potential function(steps k'∈Mk,e∈E,j∈C, 12 and 13)otherwise its previous strategy remains.Besides, since only F's strategy changes while others'strategies the expression of W(e.)in step 7 when Fk is improving its strategy is given by remain the same in the strategy profiles s and q. Interchanging the role of e and e'together with (13)and W(e.J)2wL[RXEj(s-k)+Rpj+sYe.jl,(17) the assumption be.e=e.e,we can rewrite equation (14)as where sk is the strategy profile of other flows obtained Dr(∑∑Xm∑∑xg,ee after the previous iteration.Note that althoughis usually eEE jEc k'EMke'∈E written as a function the entire strategy profile s but it actually -∑∑Xs∑∑X,wee) only depends on s-k.Here,we explicitly write as a function of s_k to emphasize that only flow Fk is updating eEE jEC KEMk e'EE its strategy while others'actions are fixed.The correctness of =Dr(∑∑XukA(s)-∑∑Xwk(g) (17)and Algorithm 1 is shown in the proof to Theorem 3. e∈EjEC eEE jEC Theorem 3:Each improvement step (i.e.,each iteration)in (15) Algorithm 1 can reduce the potential function to the maximum

6 Thus we can derive Φ(s) − Φ(q) = ∑ k′∈M ∑ (e,j)∈sk′ ζ k ′ e,j (s) − ∑ k′∈M ∑ (e,j)∈qk′ ζ k ′ e,j (q) = ( ∑ (e,j)∈sk ζ k e,j (s) − ∑ (e,j)∈qk ζ k e,j (q) ) + ( ∑ k′∈Mk ∑ (e,j)∈sk′ ζ k ′ e,j (s) − ∑ k′∈Mk ∑ (e,j)∈qk′ ζ k ′ e,j (q) ) . (11) For the first term in the above equation, we can further write out its explicit expression ∑ (e,j)∈sk ζ k e,j (s) − ∑ (e,j)∈qk ζ k e,j (q) = ∑ e∈E ∑ j∈C Xk e,jωk[ΩRλ k e,j (s) + 2ΩRφ k e,j + 2ΩSγe,j ] − ∑ e∈E ∑ j∈C X′k e,jωk[ΩRλ k e,j (q) + 2ΩRφ k e,j + 2ΩSγe,j ]. (12) For the second term in (11), we first notice that sk′ = qk′ for any k ′ ∈ Mk, i.e., Xk ′ e,j = X′k ′ e,j , ∀k ′ ∈ Mk, e ∈ E, j ∈ C. (13) Then the second term can be equivalently written as ∑ k′∈Mk ∑ e∈E ∑ j∈C Xk ′ e,j ζ k ′ e,j (s) − ∑ k′∈Mk ∑ e∈E ∑ j∈C X ′k ′ e,j ζ k ′ e,j (q) = ∑ k′∈Mk ∑ e∈E ∑ j∈C Xk ′ e,j [ζ k ′ e,j (s) − ζ k ′ e,j (q)] = ∑ k′∈Mk ∑ e∈E ∑ j∈C Xk ′ e,jωk′ΩR[λ k ′ e,j (s) − λ k ′ e,j (q)] = ∑ k′∈Mk ∑ j∈C ∑ e∈E ∑ e ′∈E Xk ′ e,jωk′ωkθe,e′ΩR(Xk e ′ ,j − X′k e ′ ,j ). (14) Note that the derivation of (14) exploits the fact that λ k ′ e,j (s) − λ k ′ e,j (q) = ∑ e ′∈E ωkθe,e′ (Xk e ′ ,j − X ′k e ′ ,j ), ∀k ′ ∈ Mk, e ∈ E, j ∈ C, since only Fk’s strategy changes while others’ strategies remain the same in the strategy profiles s and q. Interchanging the role of e and e ′ together with (13) and the assumption θe,e′ = θe ′ ,e, we can rewrite equation (14) as ΩR (∑ e∈E ∑ j∈C Xk e,jωk ∑ k′∈Mk ∑ e ′∈E Xk ′ e ′ ,jωk′θe,e′ − ∑ e∈E ∑ j∈C X′k e,jωk ∑ k′∈Mk ∑ e ′∈E X ′k ′ e ′ ,jωk′θe,e′ ) =ΩR (∑ e∈E ∑ j∈C Xk e,jωkλ k e,j (s) − ∑ e∈E ∑ j∈C X′k e,jωkλ k e,j (q) ) . (15) By summing (12) and (15), we finally obtain that Φ(s) − Φ(q) = ∑ e∈E ∑ j∈C Xk e,jωk[2ΩRλ k e,j (s) + 2ΩRφ k e,j + 2ΩSγe,j ] − ∑ e∈E ∑ j∈C X′k e,jωk[2ΩRλ k e,j (q) + 2ΩRφ k e,j + 2ΩSγe,j ] =2ωk[T Ck(s) − T Ck(q)] > 0. (16) Hence, we have proved that (10) is a potential function of the proposed game. According to Theorem 1 and Property 1 of general potential games, we can immediately conclude the following result. Theorem 2: There exists a Nash Equilibrium in the Route￾Switching Game with complete information, and this NE minimizes the potential function in (10). Next, we design an algorithm to reach the NE in Theorem 2, shown as Algorithm 1. Note that each player locally runs this algorithm to determine its own best strategy at the NE, by simulating other players’ possible actions (step 3 to step 18). This is also referred as the Fictitious Play Process in game theory [33]. The accuracy of Fictitious Play is dependent on the degree of known information about other players. Under complete information, every player’s parameters are precisely known by others, so the Fictitious Play Process will converge to the real play process. However, Fictitious Play will deviate from the reality under incomplete information (but it still converges), as will be further demonstrated in section IV. Essentially, Algorithm 1 is an iterative algorithm following FIP. Its major part is the strategy improvement (or update), which is done by first converting the reduction of the potential function into finding the shortest path in an undirected graph and then applying the well-known Dijsktra Algorithm to find such a path. Step 9 in Algorithm 1 handles the three constraints mentioned in section II-D, where (e, j) ∈ Λ if letting Xk e,j = 1 will violate any of the three constraints under the strategy profile in that loop. Variable m in the algorithm acts like a counter recording the consecutive times for which players cannot reduce the value of the potential function, and the stop condition (step 18) indicates that all M players cannot reduce the potential function anymore, where the minimum point (i.e., the NE) is reached. Note that a player’s strategy is updated only when it can reduce the potential function (steps 12 and 13) otherwise its previous strategy remains. Besides, the expression of W(e,j) in step 7 when Fk is improving its strategy is given by W(e,j) = 2ωk[ΩRλ k e,j (s−k) + ΩRφ k e,j + ΩSγe,j ], (17) where s−k is the strategy profile of other flows obtained after the previous iteration. Note that although λ k e,j is usually written as a function the entire strategy profile s but it actually only depends on s−k. Here, we explicitly write λ k e,j as a function of s−k to emphasize that only flow Fk is updating its strategy while others’ actions are fixed. The correctness of (17) and Algorithm 1 is shown in the proof to Theorem 3. Theorem 3: Each improvement step (i.e., each iteration) in Algorithm 1 can reduce the potential function to the maximum

Algorithm 1 Compute the best strategy s;of flow Fi at the Note that we interchange the role of e and e'and exploit the Nash Equilibrium under complete information (executed by fact that be.e=bee in the second equation.Hence,'(s) the initiator of flow Fi,ViEM) can be written as 上InitializeX,=0,∀k∈M,e∈E,j∈C Φ0=+o,n=0,k=0,m=0: Φ'(s)=∑∑X2wr[2R(s-k)+2rp+2sel. 2:For any eEE,extend edge e to C parallel edges eEE jEC (each extended edge is denoted by (e,j),Vj C); Therefore,when Fk is updating its strategy,if we set the 3:repeat weight of edge (e,j)in the extended graph to be 4: Update the iteration counter:n =n+1; 5: Update the index of flow:k =(k mod M)+1; W(e.j)2wk[SRXej(s-k)+SRei+sYe.jl, for each e∈E,j∈Cdo 个 Update edge weight W(e.j)according to (17); then finding the shortest path in the extended graph will be end for equivalent to reducing '(s)to the maximum extent,which 9: Set W(e,)=+o,V(e,j)∈ further reduces the potential function (s)to the maximum 10: Call Dijsktra Algorithm to find the shortest path from extent.Since weight W(e.)>0,then Dijsktra Algorithm can Sk to D&in the extended graph: be applied to find the shortest path in the extended graph. 11: Compute n according the shortest path; Besides,route connectivity is guaranteed by the property of 12: ifΦnx5 jwk0e.e (si,s2,.,s)is an e-Nash Equilibrium if for any player k'EMkeEE jEC e'∈E Fk(Vk E M)and its any strategy skC S. +∑∑X,,(s) TCk(sk;sk)<TCk(sk;sk)+E. eEE jEc For the first term in (s). The above definition implies that no player can reduce its costs by e if it unilaterally violates the e-NE.Particularly,when ∑∑∑Xww2r∑Xjwk0e,e] e=0,the e-NE becomes the exact NE. k'EMk EEE jEC e'EE As a corollary of Property 3 of general potential games,we =Pr∑∑∑X5,∑Xkjwwwk9ee have the following theorem. Theorem 4:Under complete information,every Route- eEE jEc e'EE k'EMk =r∑∑X∑∑X5,wx0e. Switching Game has a unique e-Nash Equilibrium. To compute the e-Nash Equilibrium,we only need to EEE jEC e'EEK'EMk slightly modify Algorithm 1 by setting the condition in step =∑∑XDR(s-k l2tobe“Φn<Φn-1-e”.By such modification,we can eEE jEc conclude Theorem 5

7 Algorithm 1 Compute the best strategy s ∗ i of flow Fi at the Nash Equilibrium under complete information (executed by the initiator of flow Fi , ∀i ∈ M) 1: Initialize Xk e,j = 0, ∀k ∈ M, e ∈ E, j ∈ C; Φ0 = +∞, n = 0, k = 0, m = 0; 2: For any e ∈ E, extend edge e to C parallel edges (each extended edge is denoted by (e, j), ∀j ∈ C); 3: repeat 4: Update the iteration counter: n = n + 1; 5: Update the index of flow: k = (k mod M) + 1; 6: for each e ∈ E, j ∈ C do 7: Update edge weight W(e,j) according to (17); 8: end for 9: Set W(e,j) = +∞, ∀(e, j) ∈ Λ; 10: Call Dijsktra Algorithm to find the shortest path from Sk to Dk in the extended graph; 11: Compute Φn according the shortest path; 12: if Φn < Φn−1 then 13: Update the action of flow Fk accordingly; 14: Reset m = 0; 15: else 16: m = m + 1, Φn = Φn−1; 17: end if 18: until m = M 19: s ∗ i = {(e, j)|Xi e,j = 1, e ∈ E, j ∈ C}; extent and guarantee route connectivity in polynomial time with the time complexity O(|E|M + |V | 2 ). Proof: Suppose Fk is updating its strategy in the Ficti￾tious Play Process shown in Algorithm 1. Then we have Φ(s) = ∑ k′∈Mk ∑ e∈E ∑ j∈C Xk ′ e,j ζ k ′ e,j (s) + ∑ e∈E ∑ j∈C Xk e,j ζ k e,j (s), where ζ k e,j (s) := ωk[ΩRλ k e,j (s−k) + 2ΩRφ k e,j + 2ΩSγe,j ]. Here, s−k (or equivalently, Xk ′ e,j , ∀k ′ ∈ Mk, e ∈ E, j ∈ C) is the strategy profile of other flows obtained in the previous iteration, which is fixed when player Fk is updating its strategy. Hence reducing Φ(s) is equivalent to reducing Φ ′ (s) = ∑ k′∈Mk ∑ e∈E ∑ j∈C Xk ′ e,jωk′ [ΩR ∑ e ′∈E Xk e ′ ,jωkθe,e′ ] + ∑ e∈E ∑ j∈C Xk e,j ζ k e,j (s) For the first term in Φ ′ (s), ∑ k′∈Mk ∑ e∈E ∑ j∈C Xk ′ e,jωk′ [ΩR ∑ e ′∈E Xk e ′ ,jωkθe,e′ ] =ΩR ∑ e∈E ∑ j∈C ∑ e ′∈E Xk e ′ ,j ∑ k′∈Mk Xk ′ e,jωk′ωkθe,e′ =ΩR ∑ e∈E ∑ j∈C Xk e,j ∑ e ′∈E ∑ k′∈Mk Xk ′ e ′ ,jωk′ωkθe,e′ = ∑ e∈E ∑ j∈C Xk e,jωkΩRλ k e,j (s−k), Note that we interchange the role of e and e ′ and exploit the fact that θe,e′ = θe ′ ,e in the second equation. Hence, Φ ′ (s) can be written as Φ ′ (s) = ∑ e∈E ∑ j∈C Xk e,j2ωk[ΩRλ k e,j (s−k) + ΩRφ k e,j + ΩSγe,j ]. Therefore, when Fk is updating its strategy, if we set the weight of edge (e, j) in the extended graph to be W(e,j) = 2ωk[ΩRλ k e,j (s−k) + ΩRφ k e,j + ΩSγe,j ], then finding the shortest path in the extended graph will be equivalent to reducing Φ ′ (s) to the maximum extent, which further reduces the potential function Φ(s) to the maximum extent. Since weight W(e,j) ≥ 0, then Dijsktra Algorithm can be applied to find the shortest path in the extended graph. Besides, route connectivity is guaranteed by the property of Dijsktra Algorithm. In terms of the time complexity, we investigate how it scales with the number of players (M) and the network scale (|E| and |V |). To compute W(e,j) , we can first calculate and store the value of λ k e,j at the end of the current iteration such that it can be readily used in the next iteration, which amounts to O(|E|M) time in each iteration. With the value of λ k e,j , computing W(e,j) only needs O(1) time for every e ∈ E and j ∈ C. Thus, setting weight W(e,j) on the extended graph will consume O(|E|) time (note that C can be regarded as a constant here) in each iteration and Dijsktra Algorithm is of O(|V | 2 ). Then the overall time complexity of each iteration is O(|E|M + |V | 2 ). D. ϵ-Nash Equilibrium Algorithm 1 provides us with a method to compute the exact NE, where no players can reduce their own costs by unilaterally deviating from the NE. Unfortunately, Algorithm 1 is not guaranteed to reach the minimum of the potential function in polynomial time, even though simulation results show that the convergence is very fast (see section VII). Alternatively, we can obtain an approximate NE or ϵ-NE in polynomial time, by modifying Algorithm 1. Firstly, we give the formal definition of the ϵ-Nash Equilibrium. Definition 4 (ϵ-Nash Equilibrium): A strategy profile s ∗ = (s ∗ 1 , s∗ 2 , · · · , s∗ M) is an ϵ-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 ) + ϵ. The above definition implies that no player can reduce its costs by ϵ if it unilaterally violates the ϵ-NE. Particularly, when ϵ = 0, the ϵ-NE becomes the exact NE. As a corollary of Property 3 of general potential games, we have the following theorem. Theorem 4: Under complete information, every Route￾Switching Game has a unique ϵ-Nash Equilibrium. To compute the ϵ-Nash Equilibrium, we only need to slightly modify Algorithm 1 by setting the condition in step 12 to be “Φn < Φn−1 − ϵ”. By such modification, we can conclude Theorem 5

Theorem 5:The computation of the e-Nash Equilibrium can where p&(k)is the probability that data flow Fk is of type terminate in O()iterations. tk,shown by Proof:It's obvious that pk(ix)= p(t,t2,…,tM) (18) ,(s)=∑∑Xwk,0e,e≤EM max wg. T∈T:tk= k∈M e'∈Ek'∈Mk Then we define the concept of equilibria in incomplete- Define U:=maxe w,Q:=maxe.e and W= information games,referred as the Bayesian Nash Equilibrium maxav,where o is the number of radios equipped by node (BNE). v.Then we have Definition 5 (Bayesian Nash Equilibrium,BNE):A s- ④(s)=∑∑wkI0r(s)+22r+2s7el trategy profile s*=(si,s2,...,s)is a Bayesian Nash Equilibrium if for any data flow F(vk E M)and its any kEM (e.j)Esk type t E Tk,sk(t)satisfies: ≤U(@REMU+22rQ+22s)∑∑∑X eEE jEC kEM st(t)=arg mi迎。E{TCk(sk(t);sk(t-k)ltk=t}, Sk(t)CS <UWIV|(OR|E MU +20RQ+20sy), where EITCk(sk(t);s(t_k))tk =t}is Fk's expected costs where the last inequality is according to (3).In the modified when it is of type t and adopts strategy sk(t)(note that tk version of Algorithm 1,the value of (s)will be reduced is a random vector). by at least e after every M improvement steps otherwise the Unlike Theorem 2 in the complete-information scenario,we algorithm will stop.Hence,.noticing thatΦ(s)≥0，we can skip the direct proof to the existence of BNE.Instead,we'll conclude that the maximum number of improvement steps will first provide an algorithm to compute BNE and then prove its be upper-bounded by correctness,shown in Algorithm 2 and Theorem 6. M(s)MUWIVI(SRIE]MU +29RQ+29sY) Algorithm 2 Compute the best strategy s;(Ti S)of E flow Fi at the Bayesian Nash Equilibrium under incomplete That is,the computation of the e-Nash Equilibrium can termi- nate in O(MEV1)iterations. information (executed by the initiator of flow Fi,Vi EM) ◆ 1:for each k∈Mdo 2 IV.ROUTE-SWITCHING GAMES WITH INCOMPLETE Compute Ew]=teT PA(t)wk(t): 3: INFORMATION Compute E[pe,l(e∈E,j∈C)similarly: 4: end for In the above sections,we assume that all players have the 5:Compute the best strategy s using Algorithm I by re- exact information about others.However,obtaining exact pa- placing wk and with Elwk]and El】(k∈M, rameters about other concurrent flows could be very difficult in e∈E,j∈C),respectively: practice.As is often the case,obtaining statistical information 6:Sets(t)=s酵t∈Tii is much easier.In this section,we will extend our scheme to the incomplete-information scenario,where players'exact information is hidden while their statistics is known. The idea behind Algorithm 2 is simple:each player first The proposed game with incomplete information can be computes the expectations of parameters related to other indicated by the tuple g={G,A,I,S,TC,T,p).The slight players (as a belief or prediction about them);then each player differences between this definition and that of the complete- calls Algorithm 1 by taking in such a belief and derives information game lie in two aspects.Firstly,we introduce a an equilibrium.Theorem 6 demonstrates that the derived type space T=T1 x...x TM to indicate the possible rates equilibrium is a legitimate BNE. and packet sizes of data flows in the incomplete-information Theorem 6:Algorithm 2 yields a Bayesian Nash Equilib- game,where Tk is the type space of data flow F.Then rium of the Routing-Switching Game with incomplete infor- flow F's strategy sk is a mapping from Tk to the strategy mation. space S.i.e..s:TkS.Besides,the flow rate would Proof:Without loss of generality,we assume R be rk(t),the packet size would be (t),and the energy s =1 here.We consider the contradiction and suppose there costs in channel j over link e would be(t)if data exists a data fow Fk(of type t)whose strategy obtained by flow Fk is of type t.Similarly,we define wk(t)=x Algorithm 2 (i.e..s(t)=s)is not its best response at the TL(E) Bayesian NE.Then according to the definition of the Bayesian and denote T =[t1,...,ta}the type profile,where tk is NE,Fk can change its strategy to s (so that the type of F.Secondly,each player only knows the type distribution p of other data flows over the type space T. E(TCk(sk;sk(tk))tk=t) (19) where p=(p(t1,t2,...,tM))rer.Note that the Probability <ETCk(sk;s_k(t_k))tk =t). Density Function will be used when the type distribution is continuous.We assume the type distribution of each data flow Fi's expected costs when it is of type t under sk(t)are is independent: E(TCk(sk(t);s_k(t_k))tk=t} p6,2,…,iw)=Πpk(i), =E(X(s-k(t_k))}+(t)+7ej]. (20) k∈M (e.j)Esk(t)

8 Theorem 5: The computation of the ϵ-Nash Equilibrium can terminate in O( M2 |E||V | ϵ ) iterations. Proof: It’s obvious that λ k e,j (s) = ∑ e ′∈E ∑ k′∈Mk Xk ′ e ′ ,jωk′θe,e′ ≤ |E|M max k′∈M ωk′ . Define U := maxk′ ωk′ , Q := maxk′ ,e,j φ k ′ e,j , and W := maxv αv, where αv is the number of radios equipped by node v. Then we have Φ(s) = ∑ k∈M ∑ (e,j)∈sk ωk[ΩRλ k e,j (s) + 2ΩRφ k e,j + 2ΩSγe,j ] ≤ U(ΩR|E|MU + 2ΩRQ + 2ΩSγ) ∑ e∈E ∑ j∈C ∑ k∈M Xk e,j ≤ UW|V |(ΩR|E|MU + 2ΩRQ + 2ΩSγ), where the last inequality is according to (3). In the modified version of Algorithm 1, the value of Φ(s) will be reduced by at least ϵ after every M improvement steps otherwise the algorithm will stop. Hence, noticing that Φ(s) ≥ 0, we can conclude that the maximum number of improvement steps will be upper-bounded by MΦ(s) ϵ ≤ MUW|V |(ΩR|E|MU + 2ΩRQ + 2ΩSγ) ϵ That is, the computation of the ϵ-Nash Equilibrium can termi￾nate in O( M2 |E||V | ϵ ) iterations. IV. ROUTE-SWITCHING GAMES WITH INCOMPLETE INFORMATION In the above sections, we assume that all players have the exact information about others. However, obtaining exact pa￾rameters about other concurrent flows could be very difficult in practice. As is often the case, obtaining statistical information is much easier. In this section, we will extend our scheme to the incomplete-information scenario, where players’ exact information is hidden while their statistics is known. The proposed game with incomplete information can be indicated by the tuple G = {G, A, Γ, S, T C, T, p}. The slight differences between this definition and that of the complete￾information game lie in two aspects. Firstly, we introduce a type space T = T1 × · · · × TM to indicate the possible rates and packet sizes of data flows in the incomplete-information game, where Tk is the type space of data flow Fk. Then flow Fk’s strategy sk is a mapping from Tk to the strategy space S, i.e., s ∗ k : Tk 7→ S. Besides, the flow rate would be rk(t), the packet size would be µk(t), and the energy costs in channel j over link e would be φ k e,j (t) if data flow Fk is of type t. Similarly, we define ωk(t) = µk(t) rk(t) and denote T = {t1, · · · , tM} the type profile, where tk is the type of Fk. Secondly, each player only knows the type distribution p of other data flows over the type space T, where p = (p(t1, t2, · · · , tM))T ∈T. Note that the Probability Density Function will be used when the type distribution is continuous. We assume the type distribution of each data flow is independent: p(tˆ1,tˆ2, · · · ,tˆM) = ∏ k∈M pk(tˆk), where pk(tˆk) is the probability that data flow Fk is of type tˆk, shown by pk(tˆk) = ∑ T ∈T:tk=tˆk p(t1, t2, · · · , tM). (18) Then we define the concept of equilibria in incomplete￾information games, referred as the Bayesian Nash Equilibrium (BNE). Definition 5 (Bayesian Nash Equilibrium, BNE): A s￾trategy profile s ∗ = (s ∗ 1 , s∗ 2 , · · · , s∗ M) is a Bayesian Nash Equilibrium if for any data flow Fk (∀k ∈ M) and its any type t ∈ Tk, s ∗ k (t) satisfies: s ∗ k (t) = arg min sk(t)⊆S E{T Ck(sk(t); s ∗ −k (t−k))|tk = t}, where E{T Ck(sk(t); s ∗ −k (t−k))|tk = t} is Fk’s expected costs when it is of type t and adopts strategy sk(t) (note that t−k is a random vector). Unlike Theorem 2 in the complete-information scenario, we skip the direct proof to the existence of BNE. Instead, we’ll first provide an algorithm to compute BNE and then prove its correctness, shown in Algorithm 2 and Theorem 6. Algorithm 2 Compute the best strategy s ∗ i (Ti 7→ S) of flow Fi at the Bayesian Nash Equilibrium under incomplete information (executed by the initiator of flow Fi , ∀i ∈ M) 1: for each k ∈ M do 2: Compute E[ωk] = ∑ t∈Tk pk(t)ωk(t); 3: Compute E[φ k e,j ] (∀e ∈ E, j ∈ C) similarly; 4: end for 5: Compute the best strategy s¯ ∗ i using Algorithm 1 by re￾placing ωk and φ k e,j with E[ωk] and E[φ k e,j ] (∀k ∈ M, e ∈ E, j ∈ C), respectively; 6: Set s ∗ i (t) = ¯s ∗ i (∀t ∈ Ti); The idea behind Algorithm 2 is simple: each player first computes the expectations of parameters related to other players (as a belief or prediction about them); then each player calls Algorithm 1 by taking in such a belief and derives an equilibrium. Theorem 6 demonstrates that the derived equilibrium is a legitimate BNE. Theorem 6: Algorithm 2 yields a Bayesian Nash Equilib￾rium of the Routing-Switching Game with incomplete infor￾mation. Proof: Without loss of generality, we assume ΩR = ΩS = 1 here. We consider the contradiction and suppose there exists a data flow Fk (of type t) whose strategy obtained by Algorithm 2 (i.e., s ∗ k (t) = ¯s ∗ k ) is not its best response at the Bayesian NE. Then according to the definition of the Bayesian NE, Fk can change its strategy to s¯ ′ k (s¯ ′ k ̸= ¯s ∗ k ) so that E{T Ck(¯s ′ k ; s ∗ −k (t−k))|tk = t} <E{T Ck(¯s ∗ k ; s ∗ −k (t−k))|tk = t}. (19) Fk’s expected costs when it is of type t under sk(t) are E{T Ck(sk(t); s−k(t−k))|tk = t} = ∑ (e,j)∈sk(t) [E{λ k e,j (s−k(t−k))} + φ k e,j (t) + γe,j ]. (20)

9 Note that equation (20)is established on the fact that that in the new complete-information game formed in step 5 E;(sk(t);s_k(t_))ltk =t)=Exe;(s_k(t_k))}since of Algorithm 2: Ae(s)only depends on others'strategies s-k(t)and the type distribution of each data flow is statistically independent. TCk(5k;3k)<TCk(5k;5_k), Taking (20)to (19),we derive which means that s*is not the NE in the corresponding E(XE;(s(t-))}+p(t)+ejl complete-information game,contradicting to the correctness of Algorithm 1.Hence Theorem 6 has been proved. ■ (e.j)E (21) It should be mentioned that when the Bayesian e-Nash <∑E{A,(s之kt-k》+,)+e Equilibrium is calculated,similar modification (see section (e.j) III-D)should be made to Algorithm 1.Besides,since statistical Step 5 in Algorithm 2 corresponds to a new complete- information is used in the Fictitious Play Process,each player information game.To avoid the confusion of denotations, cannot precisely simulate others'actions,which implies that we will denote s an arbitrary strategy profile in the new there are certain performance gaps between the BNE and the NE(see section VII for numerical demonstrations). complete-information game and the corresponding 0-1 strategy indication is,K∈M,e∈E,j∈C).By compar-- ison,the corresponding strategy profile in the incomplete- V.PRICE OF STABILITY information game is s which is a mapping from the type In this section,we will compare the performance of the space to the strategy space,and the -1 indication is(t) proposed game with the socially optimal results obtained in keM,e∈E,j∈C,t∈Tkx).By this definition,.in the centralized schemes.As for the complete-information game, new complete-information game, Price of Stability (PoS)in terms of social costs will be TCx(⑤)=∑[（⑤）+)+el analyzed.In terms of the incomplete-information scenario, expected social costs as well as Bayesian Price of Stability (e.j)E3k (BPoS)will be discussed. Here, (同=∑∑形，m8 A.Complete-Information Game e'∈Ek'∈Mk In the route-switching game with complete information,the w=ELwd]=∑Pw(代)k(代) metric of our interests is social costs,defined as the following. tETk! Definition 6 (Social Costs):Social costs are the sum of all players'overall costs,i.e., The above equation is actually derived from step 2 of Algo- rithm 2.By equation(18),we know that SoC(s)= ∑TCx(s), kEM ⑦k= ∑pk(t)wk(t Then we introduce the definition of Price of Stability in the t'∈Tk complete-information game. = ∑p,…,t)e(e) Definition 7(Price of Stability):Price of Stability is the t'eTk,T∈T:ty=t" ratio of social costs between the best NE and the optimality =∑pt,…,tnwr(th in centralized schemes,i.e., TeT PoS= SoC(s*) Then()can be rewritten as mins SoC(s)' ,(同=∑∑5，ee∑p,…,twt) where s*is the best NE point of the proposed game. The following theorem shows that PoS of the proposed e'∈Ek'∈Mk T∈T game has an upper bound. =∑p61,…,tan)∑∑Xg,(t)0e.ewp(t)Theorem7:The upper bound of Price of Stability in the TeT e'EEk'EM proposed game is p,where p-2 maxk =E{A(s-k(t-k)}, Proof:With loss of generality,we set R=s =1.Let where the second equality holds because any other flows s*be the best Nash Equilibrium of the game and s'be the NE that globally minimizes the potential function.Besides,let q follow Algorithm 2 and step6 shows that )(i be the strategy profile which can minimize the social costs.At X,-X花，t》for every∈Ms and t Tk in the the same time,we define 21:=maxk wk and 22 :mink wk. new complete-information game.This further implies that Thusp.We can rewrite the potential function as TCx(=∑E(A,(s-k(t-k)》+p)+e: (e.j)ESk (s)=2∑w[DCk(s)+EC(s)+SCk(s】-∑wkDC(s) k∈M C八M Taking the above equation to (21)and noticing that ≤2ZSoC(s)-∑WkDCk(s) s(t_k)=sk for every t_kE T_k,we can conclude k∈M

9 Note that equation (20) is established on the fact that E{λ k e,j (sk(t); s−k(t−k))|tk = t} = E{λ k e,j (s−k(t−k))} since λ k e,j (s) only depends on others’ strategies s−k(t−k) and the type distribution of each data flow is statistically independent. Taking (20) to (19), we derive ∑ (e,j)∈s¯ ′ k [E{λ k e,j (s ∗ −k (t−k))} + φ k e,j (t) + γe,j ] < ∑ (e,j)∈s¯ ∗ k [E{λ k e,j (s ∗ −k (t−k))} + φ k e,j (t) + γe,j ]. (21) Step 5 in Algorithm 2 corresponds to a new complete￾information game. To avoid the confusion of denotations, we will denote s¯ an arbitrary strategy profile in the new complete-information game and the corresponding 0-1 strategy indication is X¯ k ′ e,j (∀k ′ ∈ M, e ∈ E, j ∈ C). By compar￾ison, the corresponding strategy profile in the incomplete￾information game is s which is a mapping from the type space to the strategy space, and the 0-1 indication is Xk ′ e,j (t) (∀k ′ ∈ M, e ∈ E, j ∈ C, t ∈ Tk′ ). By this definition, in the new complete-information game, T Ck(¯s) = ∑ (e,j)∈s¯k [λ¯k e,j (¯s) + φ k e,j (t) + γe,j ]. Here, λ¯k e,j (¯s) = ∑ e ′∈E ∑ k′∈Mk X¯ k ′ e ′ ,jω¯k′θe,e′ , ω¯k′ = E[ωk′ ] = ∑ t ′∈Tk′ pk′ (t ′ )ωk′ (t ′ ). The above equation is actually derived from step 2 of Algo￾rithm 2. By equation (18), we know that ω¯k′ = ∑ t ′∈Tk′ pk′ (t ′ )ωk′ (t ′ ) = ∑ t ′∈Tk′ ∑ T ∈T:tk′=t ′ p(t1, · · · , tM)ωk′ (t ′ ) = ∑ T ∈T p(t1, · · · , tM)ωk′ (tk′ ). Then λ¯k e,j (¯s) can be rewritten as λ¯k e,j (¯s) = ∑ e ′∈E ∑ k′∈Mk X¯ k ′ e ′ ,j θe,e′ ∑ T ∈T p(t1, · · · , tM)ωk′ (tk′ ) = ∑ T ∈T p(t1, · · · , tM) ∑ e ′∈E ∑ k′∈Mk Xk ′ e ′ ,j (tk′ )θe,e′ωk′ (tk′ ) = E{λ k e,j (s−k(t−k))}, where the second equality holds because any other flows follow Algorithm 2 and step 6 shows that s¯k′ = sk′ (tk′ ) (i.e., X¯ k ′ e ′ ,j = Xk ′ e ′ ,j (tk′ )) for every k ′ ∈ Mk and tk′ ∈ Tk′ in the new complete-information game. This further implies that T Ck(¯s) = ∑ (e,j)∈s¯k [E{λ k e,j (s−k(t−k))} + φ k e,j (t) + γe,j ]. Taking the above equation to (21) and noticing that s ∗ −k (t−k) = ¯s ∗ −k for every t−k ∈ T−k, we can conclude that in the new complete-information game formed in step 5 of Algorithm 2: T Ck(¯s ′ k ; ¯s ∗ −k ) < T Ck(¯s ∗ k ; ¯s ∗ −k ), which means that s¯ ∗ is not the NE in the corresponding complete-information game, contradicting to the correctness of Algorithm 1. Hence Theorem 6 has been proved. It should be mentioned that when the Bayesian ϵ-Nash Equilibrium is calculated, similar modification (see section III-D) should be made to Algorithm 1. Besides, since statistical information is used in the Fictitious Play Process, each player cannot precisely simulate others’ actions, which implies that there are certain performance gaps between the BNE and the NE (see section VII for numerical demonstrations). V. PRICE OF STABILITY In this section, we will compare the performance of the proposed game with the socially optimal results obtained in centralized schemes. As for the complete-information game, Price of Stability (PoS) in terms of social costs will be analyzed. In terms of the incomplete-information scenario, expected social costs as well as Bayesian Price of Stability (BPoS) will be discussed. A. Complete-Information Game In the route-switching game with complete information, the metric of our interests is social costs, defined as the following. Definition 6 (Social Costs): Social costs are the sum of all players’ overall costs, i.e., SoC(s) = ∑ k∈M T Ck(s). Then we introduce the definition of Price of Stability in the complete-information game. Definition 7 (Price of Stability): Price of Stability is the ratio of social costs between the best NE and the optimality in centralized schemes, i.e., P oS = SoC(s ∗ ) mins SoC(s) , where s ∗ is the best NE point of the proposed game. The following theorem shows that PoS of the proposed game has an upper bound. Theorem 7: The upper bound of Price of Stability in the proposed game is ρ, where ρ = 2 maxk,l∈M ωk ωl . Proof: With loss of generality, we set ΩR = ΩS = 1. Let s ∗ be the best Nash Equilibrium of the game and s ′ be the NE that globally minimizes the potential function. Besides, let q be the strategy profile which can minimize the social costs. At the same time, we define Z1 := maxk ωk and Z2 := mink ωk. Thus ρ = 2Z1 Z2 . We can rewrite the potential function as Φ(s) =2 ∑ k∈M ωk[DCk(s) + ECk(s) + SCk(s)] − ∑ k∈M ωkDCk(s) ≤2Z1SoC(s) − ∑ k∈M ωkDCk(s)

10 Similarly,we have limited space,we omit the proof here.Theorem 8 implies that Φ(s)≥Z2SoC(s)+∑wk[ECk(s)+SC(sl BPoS in the proposed game is also related to the (statistical) heterogeneity of incoming data flows.Besides,similar to the k∈M discussion of PoS,the real BPoS is not significant in practical Since (s')reaches the global minimum,we have systems Z2SoC(s)+∑wk[ECx(s)+SCx(s】≤Φ(s) VI.DISCUSSION k∈M ≤Φ(g)≤2Z5oC(q)-∑ WkDCk(q). A.Tradeoff between Routing Costs and Switching Costs ∈M In this subsection,we discuss the tradeoff between routing and switching costs.Due to the limited space,a brief heuristic For the simplicity of denotations.we define demonstration is provided instead of a formal mathematical a :=Ekwk[DCk(q)+ECk(s)+SCk(s) analysis. SoC(q) Suppose the flow of our interests is Fk.For simplicity, Then we can derive that we assume each link only sustains one channel such that the maximum number of channel switching is E.Denote Z2SoC(s')<SoC(q)(2Z1-a) Z the allowable number of channel switching in F's route (Z =0,1,...,ED).Then Zy roughly reflects the total Since s*is the best Nash Equilibrium,then SoC(s*)< switching costs incurred to flow F.Besides,suppose the set of SoC(s').Thus,we finally have channels reclaimed by PUs is I and the set of invalid links due ps=需sC瑞-a≤P to such spectrum mobility is￡={e∈E曰j∈T,Ae,=1} When Z=0,i.e.,switching costs achieve the minimum (zero),the initiator of F has to select a new spatial route in the new graph Go =(V,E\E).We denote the optimal routing Theorem 7 implies that social costs under the best NE costs in Go as RC) won't exceed p times of the minimum social costs.Here, When Z=1,switching costs increase,but the initiator p characterizes the heterogeneity of traffic demands from of F has the flexibility of switching one channel,where incoming data flows.In practical communications systems, the resulting new graph Gi has two possibilities.In the first such heterogeneity is not significant considering transmission case,the initiator of F switches the channel over a certain efficiency [31].In a special case when flows are homogeneous edge e1 EE,and thus link e is available again,which (wk is identical,Vk EM),the best NE yields less than twice implies G1 (V,(E\E)Ufe))and Go C G1.Hence, of the minimum social costs (p =2).Besides,it should be denoting the optimal routing costs inGas RC),we obtain mentioned that p is a relatively loose bound,which means that the real PoS could be much less than p.The above two RCfo)≥RC）,where“=”only happens when resources remarks of p imply that the obtained NE is actually close to (e.g.,available channels and links)are abundant.In the second the optimality in practice (PoS is usually below 1.5 in our case,the initiator of F switches the channel over a certain simulation,see section VID). edge e1EE\E.This happens when this channel is perceived to be overly congested over e1 and routing costs can be significantly reduced if we switch the assigned channel of el B.Incomplete-Information Game to a less congested one.where RC)RC)also holds. As for the incomplete-information scenario,the correspond- Therefore,regardless of the switching choice,we always have ing concept is referred as the Bayesian Price of Stability RC)RC)when network resources are limited. (BPoS),which is defined as the following. Similar argument holds when we raise Z until Z=El. Definition 8(Bayesian Price of Stability):Bayesian price of Then we can conclude that the increase of switching costs can Stability is the ratio of expected social costs between the best reduce routing costs.Conversely,we can similarly show that Bayesian NE and the optimal results obtained by centralized the increase of routing costs also contributes to the reduction of schemes,i.e., switching costs.Therefore,routing costs and switching costs cannot be simultaneously minimized and tradeoffs exists be- BPoS= E{SoC(s*)} tween them.In section VII,we will further provide numerical min,E{SoC(s)月 results to illustrate such tradeoffs adjusted by parameters where the expectations are over the entire type space T.A and s. deterministic upper bound of Bayesian Price of Stability is given in Theorem 8. B.Implementation of the Game Theorem 8:The upper bound of Bayesian Price of Stability in the proposed game is e,where o =2 maxk.IEM We briefly discuss the implementation of the proposed where the expectations are over the type space of flowsF game.Before flow transmission,nodes (i.e.,SUs)will first and Fi,respectively. perform spectrum sensing to obtain the states of channels12 The proof to Theorem 8 is similar to that of Theorem 7 except some lengthy probabilistic calculations.Due to the 12To reduce sensing overheads.efficient sensing schemes like cooperative sensing [13]and compressive sensing [14]can be adopted here

10 Similarly, we have Φ(s) ≥ Z2SoC(s) + ∑ k∈M ωk[ECk(s) + SCk(s)]. Since Φ(s ′ ) reaches the global minimum, we have Z2SoC(s ′ ) + ∑ k∈M ωk[ECk(s ′ ) + SCk(s ′ )] ≤ Φ(s ′ ) ≤ Φ(q) ≤ 2Z1SoC(q) − ∑ k∈M ωkDCk(q). For the simplicity of denotations, we define α := ∑ kωk[DCk(q) + ECk(s ′ ) + SCk(s ′ )] SoC(q) Then we can derive that Z2SoC(s ′ ) ≤ SoC(q)(2Z1 − α) Since s ∗ is the best Nash Equilibrium, then SoC(s ∗ ) ≤ SoC(s ′ ). Thus, we finally have P oS = SoC(s ∗ ) SoC(q) ≤ SoC(s ′ ) SoC(q) ≤ 2Z1 Z2 − α Z2 ≤ ρ Theorem 7 implies that social costs under the best NE won’t exceed ρ times of the minimum social costs. Here, ρ characterizes the heterogeneity of traffic demands from incoming data flows. In practical communications systems, such heterogeneity is not significant considering transmission efficiency [31]. In a special case when flows are homogeneous (ωk is identical, ∀k ∈ M), the best NE yields less than twice of the minimum social costs (ρ = 2). Besides, it should be mentioned that ρ is a relatively loose bound, which means that the real PoS could be much less than ρ. The above two remarks of ρ imply that the obtained NE is actually close to the optimality in practice (PoS is usually below 1.5 in our simulation, see section VII). B. Incomplete-Information Game As for the incomplete-information scenario, the correspond￾ing concept is referred as the Bayesian Price of Stability (BPoS), which is defined as the following. Definition 8 (Bayesian Price of Stability): Bayesian price of Stability is the ratio of expected social costs between the best Bayesian NE and the optimal results obtained by centralized schemes, i.e., BP oS = E{SoC(s ∗ )} mins E{SoC(s)} , where the expectations are over the entire type space T. A deterministic upper bound of Bayesian Price of Stability is given in Theorem 8. Theorem 8: The upper bound of Bayesian Price of Stability in the proposed game is ϱ, where ϱ = 2 maxk,l∈M E[ωk] E[ωl] , where the expectations are over the type space of flows Fk and Fl , respectively. The proof to Theorem 8 is similar to that of Theorem 7 except some lengthy probabilistic calculations. Due to the limited space, we omit the proof here. Theorem 8 implies that BPoS in the proposed game is also related to the (statistical) heterogeneity of incoming data flows. Besides, similar to the discussion of PoS, the real BPoS is not significant in practical systems. VI. DISCUSSION A. Tradeoff between Routing Costs and Switching Costs In this subsection, we discuss the tradeoff between routing and switching costs. Due to the limited space, a brief heuristic demonstration is provided instead of a formal mathematical analysis. Suppose the flow of our interests is Fk. For simplicity, we assume each link only sustains one channel such that the maximum number of channel switching is |E|. Denote Z the allowable number of channel switching in Fk’s route (Z = 0, 1, · · · , |E|). Then Zγ roughly reflects the total switching costs incurred to flow Fk. Besides, suppose the set of channels reclaimed by PUs is Γ and the set of invalid links due to such spectrum mobility is E = {e ∈ E|∃j ∈ Γ, Ae,j = 1}. When Z = 0, i.e., switching costs achieve the minimum (zero), the initiator of Fk has to select a new spatial route in the new graph G0 = (V, E\E). We denote the optimal routing costs in G0 as RC(0) k . When Z = 1, switching costs increase, but the initiator of Fk has the flexibility of switching one channel, where the resulting new graph G1 has two possibilities. In the first case, the initiator of Fk switches the channel over a certain edge e1 ∈ E, and thus link e1 is available again, which implies G1 = (V,(E\E) ∪ {e1}) and G0 ⊂ G1. Hence, denoting the optimal routing costs in G1 as RC(1) k , we obtain RC(0) k ≥ RC(1) k , where “=” only happens when resources (e.g., available channels and links) are abundant. In the second case, the initiator of Fk switches the channel over a certain edge e1 ∈ E\E. This happens when this channel is perceived to be overly congested over e1 and routing costs can be significantly reduced if we switch the assigned channel of e1 to a less congested one, where RC(0) k > RC(1) k also holds. Therefore, regardless of the switching choice, we always have RC(0) k > RC(1) k when network resources are limited. Similar argument holds when we raise Z until Z = |E|. Then we can conclude that the increase of switching costs can reduce routing costs. Conversely, we can similarly show that the increase of routing costs also contributes to the reduction of switching costs. Therefore, routing costs and switching costs cannot be simultaneously minimized and tradeoffs exists be￾tween them. In section VII, we will further provide numerical results to illustrate such tradeoffs adjusted by parameters ΩR and ΩS. B. Implementation of the Game We briefly discuss the implementation of the proposed game. Before flow transmission, nodes (i.e., SUs) will first perform spectrum sensing to obtain the states of channels12 . 12To reduce sensing overheads, efficient sensing schemes like cooperative sensing [13] and compressive sensing [14] can be adopted here