Coalitional Game Approach for CooperationStrategy in Cognitive Radio NetworksbyZhiyu DaiB.E., Zhejiang University, 2012A THESIS SUBMITTED IN PARTIAL FULFILMENT OFTHE REQUIREMENTS FOR THE DEGREE OFMASTER OF APPLIED SCIENCEinTHE FACULTY OF GRADUATE AND POSTDOCTORAL STUDIES(Electrical and Computer Engineering)THE UNIVERSITY OF BRITISH COLUMBIA(Vancouver)August 2014c© Zhiyu Dai, 2014iiAbstractCognitive radio networks (CRNs) provide an effective solution to address the increasingdemand for spectrum resources. The cooperation among secondary users (SUs) improvesthe sensing performance and spectrum efficiency. In this thesis, we study a traffic-demandbased cooperative spectrum sensing and access strategy in a CRN with multiple SUsand multiple primary users (PUs). In the proposed strategy, each SU makes its owncooperation decision according to its traffic demand. When the SU has a high trafficdemand, it selectively chooses channels to sense and access. When it has no data totransmit, it can choose not to perform sensing and save energy for future transmission.In the first part of the thesis, we study the traffic demand-based cooperation strategyin CRNs, in which each SU senses at most one channel during a time slot. We formulatethis problem as a non-transferable utility (NTU) coalition formation game, in which eachSU receives a coalition value that takes into account the expected throughput and energyefficiency. In order to obtain the final coalition structure, we propose a sequential coali-tion formation (SCF) algorithm. Simulation results show that our proposed algorithmachieves a higher throughput and energy efficiency than a previously proposed coalitionformation algorithm in [1].Abstract iiiIn the second part of this thesis, we extend the cooperation strategy problem in CRNsby enabling each SU to sense multiple channels during the sensing stage. We formulate theproblem as an NTU overlapping coalitional game. We propose an overlapping coalitionformation (OCF) algorithm to obtain a stable coalition structure. The proposed OCFalgorithm is proved to converge after a finite number of iterations. We also modify theSCF algorithm proposed in the first part of this thesis to address the problem in thenew system model. The modified SCF algorithm requires a lower number of iterationsand involves less information exchange among SUs. Moreover, an adaptive transmissionpower control scheme is proposed for SUs to further improve their energy efficiency.Simulation results show that our proposed algorithms achieve a higher throughput thanthe disjoint coalition formation (DCF) algorithm.ivTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiList of Acronyms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Cognitive Radio Network . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Cooperative Spectrum Sensing and Access in CRNs . . . . . . . . . . . . 21.3 Game Theory Applications in CSSA . . . . . . . . . . . . . . . . . . . . 31.4 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.5 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.6 List of Publication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91.7 Structure of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9Table of Contents v2 Traffic Demand-based Cooperation Strategy in CRNs . . . . . . . . . 102.1 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.2 Coalition Formation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142.2.1 NTU Coalitional Game Formulation . . . . . . . . . . . . . . . . 142.2.2 Sequential Coalition Formation (SCF) Algorithm . . . . . . . . . 162.3 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . 192.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253 Overlapping Coalitional Game Approach for Cooperation Strategy inCRNs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263.1 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273.2 Overlapping Coalitional Game for Cooperation Strategy . . . . . . . . . 323.2.1 NTU Overlapping Coalitional Game Formation . . . . . . . . . . 323.2.2 Coalition Formation Algorithms . . . . . . . . . . . . . . . . . . . 37Overlapping Coalition Formation (OCF) Algorithm . . . . . . . . 39Modified Sequential Coalition Formation (SCF) Algorithm . . . . 433.3 Adaptive Transmission Power Control . . . . . . . . . . . . . . . . . . . . 473.4 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . 513.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 584 Conclusions and Future Work . . . . . . . . . . . . . . . . . . . . . . . . . 604.1 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60Table of Contents vi4.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64viiList of Figures2.1 Aggregate throughput versus the number of PUs M for N = 10. . . . . . 212.2 Aggregate throughput versus the number of SUs N for M = 6. . . . . . . 222.3 System energy efficiency versus the number of PUs M for N = 10. . . . . 232.4 Running time of algorithms versus the number of SUs N for M = 6. . . . 243.1 An example of a stable overlapping coalition structure (M = 3, N = 7) byOCF algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 533.2 Aggregate throughput versus the number of SUs (N) in CRN for M = 6. 543.3 Aggregate throughput versus the number of PUs (M) in CRN for N = 10. 553.4 Aggregate throughput versus the average generated packets rate λ. . . . 563.5 Aggregate throughput versus the energy efficiency threshold ηmin. . . . . 573.6 Number of iterations versus the number of SUs N . . . . . . . . . . . . . . 58viiiList of AcronymsCRN Cognitive Radio NetworkCSSA Cooperative Spectrum Sensing and AccessingDCF Disjoint Coalition FormationNTU Non-Transferable UtilityOCF Overlapping Coalition FormationPUs Primary UsersSCF Sequential Coalition FormationSRCF Switch Rule-based Coalition FormationSUs Secondary UsersixAcknowledgementsI would like to express my deepest appreciation to my supervisor, Prof. Vincent Wong,for his invaluable guidance that helped me to shape my research, and for his persistentencouragement and patience that made me fulfill my master program. Without Prof.Wong’s guidance and support, this thesis would not have been possible.I want to thank my senior Zehua Wang, who has given me constructive comments andhelp to my research work. I also would like to thank my colleagues in the CommunicationLab: Bojiang Ma, Binglai Niu, Jun Zhu, Suyang Duan, Enxin Yao, Peiran Wu, BoyaSong and Weiran Shi, who have provided me with generous support and great company.I sincerely offer my best wishes and regards to all those who have helped me during mygraduate study. Finally, I own my heartfelt gratitude to my beloved parents and sister.Without their love, support and understanding, I would not have harvested my invaluablelife experiences at UBC.This research is supported by the Natural Sciences and Engineering Research Council(NSERC) of Canada.1Chapter 1IntroductionThis chapter first introduces the background of cognitive radio network (CRN), coop-erative spectrum sensing and spectrum allocation methods in CRNs, and game theoryapplications in CRNs. Then, we present the motivation and contributions of our work.The list of publication and the structure of the thesis are shown at the end of this chapter.1.1 Cognitive Radio NetworkThere is an increasing demand for spectrum resources due to rapid development of themobile applications. However, spectrum channels are under-utilized by licensed users [2].CRNs provide a promising solution to utilize the spectrum holes and improve spectrumefficiency [3]. In CRNs, secondary users (SUs) are allowed to access the spectrum channelsas long as the transmission of primary users (PUs) is not interfered with. In this way,the spectrum white spaces are filled by SUs’ transmission and spectrum efficiency can beimproved.In CRN, each SU corresponds to a pair of secondary transmitter and secondary re-ceiver with or without a base station. The PUs are authorized to transmit data onChapter 1. Introduction 2licensed channels and their transmission should not be interfered by SUs. CRNs can beclassified to underlay CRN and overlay CRN according to the way that spectrum is uti-lized [4]. In an underlay CRN, SUs can use spectrums only if the interference generatedby SUs’ transmission is below a predefined threshold. While, in an overlay CRN, spec-trums are opportunistically accessed by SUs when they are temporarily not used by PUs.We consider the overlay CRN model in this thesis. To better utilize spectrum resourcesand guarantee the protection for PU’s transmission, SUs have to detect the channel avail-ability before accessing the channel. There are multiple detection techniques for SUs toperform spectrum sensing, such as energy detection, feature detection, matched filteringand coherent detection [5]. When the PUs are detected as idle (i.e., the licensed channelsare available), SUs can transmit on the channel. In order to use the channel with highefficiency, SUs need to consider which channels to choose and how the spectrum resourcesshould be allocated, which is referred to as spectrum access and allocation in CRNs.1.2 Cooperative Spectrum Sensing and Access inCRNsFor spectrum sensing in CRNs, an SU may not be able to detect the channel accuratelydue to the shadowing and path loss. Therefore, SUs work cooperatively to sense thechannel and decide the channel availability based on fusion decision. This is referred toas cooperative spectrum sensing. After spectrum sensing, the use of available channelsChapter 1. Introduction 3is shared among SUs. In the design of cooperative spectrum sensing and access (CSSA)strategy, the throughput and energy efficiency are two important factors that are widelyconsidered. Many studies have been conducted to address the CSSA problem in CRNs.They developed different strategies to improve the throughput or energy efficiency inCRNs.By optimizing the sensing parameters (e.g., detection threshold and sensing duration)in cooperative sensing or developing efficient sensing scheduling methods, better sensingperformance and a higher network throughput can be achieved [6], [7]. When maximizingthe network throughput, the protection for the transmission of PUs needs to be guar-anteed. Therefore, the constraints of power consumption and sensing performance aretaken into account [8], [9]. Some works focus on developing scheduling algorithms toassign available channels to different SUs [10], [11]. In this way, the spectrum resourcesare allocated to SUs according to the channel characteristics and traffic demands, and ahigh system energy efficiency is obtained. In [12], the optimal sensing time, energy de-tection threshold and the number of SUs are determined to maximize the system energyefficiency.1.3 Game Theory Applications in CSSAIn many existing works, the problem of CSSA in CRNs can be formulated as a game,where each SU is modeled as a player. Each player aims to maximize its individualpayoff or improve the social welfare. In [13], the problem of cooperative spectrum sensingChapter 1. Introduction 4scheduling in CRNs with multiple channels is formulated as an evolutionary game, whereeach SU makes its own decision on whether to participate in sensing or not. An entropy-based coalition formation algorithm is developed to help SUs select which channel tosense. In [14], Jiang et al. study the channel access problem in CRNs by proposing aBayesian learning based method to estimate the channel states, and a Markov decisionprocess based approach to make channel access decision for each SU.In order to obtain better cooperative sensing performance or distribute spectrumresources among SUs efficiently, the concept of coalitional game is also applied to thedesign of cooperation strategy in CRNs. The work in [1] investigates the tradeoff betweenspectrum sensing and spectrum access. The problem is formulated as a disjoint coalitionformation game, where each SU aims to maximize its utility. A distributed algorithmis proposed to obtain the Nash-stable coalition structure. In [15], Hao et al. apply thehedonic coalition formation game theory to the cooperative spectrum sensing and accessproblem. The coalition payoff relates to energy efficiency and sensing accuracy. Theypropose a disjoint coalition formation algorithm to find the stable coalition structure. In[16], a coalitional game approach is applied to study the spectrum access of SUs, whereSUs serve as cooperative relays of PUs and obtain channel access as a payment. It isshown that SUs form a grand coalition as the final coalition structure to maximize thesystem utility.Chapter 1. Introduction 51.4 MotivationAlthough several algorithms have been proposed to improve either the energy efficiencyor throughput of SUs in CRNs, most of them do not consider traffic demand of eachSU. In most of the previous works, SUs are assumed to have infinite data to transmitand the spectrum channel can always be fully utilized when it is assigned to SUs, suchas [1] and [15]. This, however, may not be the case in practice. The traffic demandof SUs may change from time to time and vary from one to another. The amountof data that an SU needs to transmit depends on its application, e.g., an SU with avideo streaming application usually requires a higher throughput than an SU running abest-effort application. In addition, the traffic demand of an SU may change over time,e.g., an SU with an environmental monitoring application aims to report the change oftemperature. Therefore, when investigating the problem of the spectrum sensing andaccess in CRNs, it is necessary to take into account the traffic demand of SUs. Althoughin [10] and [17], the traffic demand of SUs is considered when studying the spectrumresource allocation problem, they do not consider spectrum sensing. Moreover, theirobjective is to maximize the aggregate system utility instead of developing a cooperativestrategy from the perspective of individual SUs.Most of the existing works assume that all SUs should participate in cooperativesensing (e.g., [11], [18] and [19]). However, in an energy-constrained CRN, for an SUhaving no data to transmit during a certain time period, it may be better to stay idle toconserve energy for future transmission instead of participating in cooperative sensing.Chapter 1. Introduction 6Thus, it is reasonable to let SU make its own decision on cooperation according to itstraffic demand. The work in [20] uses an evolutionary game approach to determine thecooperative sensing strategy of SUs. However, it does not consider the energy efficiencyand traffic demands of SUs.Although coalitional game theory is widely used in developing spectrum sensing andaccess strategies in CRNs, most of the previous works aim at formulating the problem asa disjoint coalition formation game and finding the non-overlapping coalition structure(e.g., [1] and [15]). They assume that an SU can only join one coalition and performcooperative sensing within that coalition. This assumption restricts the cooperation ofSUs and limits the improvement of system utility. To relax this assumption, overlappingcoalitional game theory can be used. In an overlapping coalitional game, each playercan join multiple coalitions to maximize its payoff. Due to the nature of CRNs, SUscan broadcast their sensing results to other devices. This allows them to participate inmultiple groups at the same time. Therefore, overlapping coalitional game can be appliedto spectrum sensing and access problem in CRNs. For example, the work in [21] studiesthe cooperative sensing of SUs. The problem is formulated as an overlapping coalitionalgame and a distributed algorithm is proposed to find the stable coalition structure. How-ever, this work focuses on improving sensing performance and does not consider spectrumresource allocation. Moreover, it does not take into account the associated cost of joininga coalition.Chapter 1. Introduction 71.5 ContributionsIn this thesis, we study a traffic demand-based joint CSSA strategy in CRNs. We considera CRN with multiple SUs and multiple PUs. Each SU has to perform spectrum sensing ifit wants to access the channel, and one channel can only be assigned to one SU at a timeduring the transmission stage. In the proposed cooperation strategy, each SU makes itsown cooperation decision according to its traffic demand. When an SU has a high trafficdemand, it participates in cooperative sensing and shares the spectrum resources withother SUs. If there is no data to transmit, the SU can choose not to perform sensing andsave energy for future transmission. We apply the coalitional game approach to analyzethe problem, in which each SU is modeled as a player to maximize its individual utility.In Chapter 2, we consider the case that each SU can only sense one channel during thesensing stage. In Chapter 3, we generalize the system model and enable each SU to sensemultiple channels.The main contributions of this thesis are as follows:• In Chapter 2, we study a cooperation strategy in a CRN with multiple channel,where each SU can only sense one channel at a time. We formulate this problemas a non-transferable utility (NTU) coalitional formation game, in which each SUreceives payoff according to its expected throughput and energy efficiency. Wepropose a sequential coalition formation (SCF) algorithm to determine the finalcoalition partition. Simulation results show that our proposed SCF algorithm ob-tain a final partition that has a higher throughput and energy efficiency than theChapter 1. Introduction 8Nash-stable partition obtained by a switch rule-based coalition formation (SRCF)algorithm proposed in [1]. Moreover, our proposed algorithm has a lower complexitythan the SRCF algorithm.• In Chapter 3, we extend the problem by enabling each SU to sense multiple chan-nels during the sensing stage. Each SU makes individual decisions on how manyand which channels to sense and access according to its own traffic demand. Weformulate this problem as an NTU overlapping coalition formation game. To ob-tain the stable overlapping coalition structure, we propose an overlapping coalitionformation (OCF) algorithm. We prove that our proposed algorithm converges to astable coalition structure after a finite number of iterations. Moreover, we modifythe SCF algorithm to address the problem in the new system model. The modifiedSCF algorithm has as good performance as OCF algorithm and requires a lowernumber of iterations and less information exchange among SUs. We also propose anadaptive transmission power control strategy to minimize the energy consumptionspent on transmission while guaranteeing that the maximum expected throughputis obtained. Simulation results show that our proposed OCF and modified SCFalgorithms outperform the disjoint coalition formation (DCF) algorithm in termsof aggregate throughput.Chapter 1. Introduction 91.6 List of PublicationThe following publication has been completed based on the work in this thesis.• Zhiyu Dai and Vincent W.S. Wong, “Traffic demand-based cooperation strategyin cognitive radio networks,” in Proc. of IEEE Wireless Communication and Net-working Conference (WCNC), Istanbul, Turkey, April 2014.1.7 Structure of the ThesisThe rest of this thesis is organized as follows. In Chapter 2, we present the traffic-demandbased cooperation strategy in CRNs with each SU sensing only one channel in a timeslot. In Chapter 3, we extend the CSSA problem by studying the case that each SU isallowed to sense multiple channels. Conclusions and future work are given in Chapter 4.10Chapter 2Traffic Demand-based CooperationStrategy in CRNsIn this chapter, we study a traffic demand-based joint cooperative spectrum sensing andaccess strategy for individual SU in CRNs, where each SU senses at most one channelduring the sensing stage. We present the system model and formulate the problem as acoalitional game. A sequential coalition formation (SCF) algorithm is proposed to obtainthe final coalition structure. Then, we present the performance evaluation by comparingour proposed algorithm with the switch rule-based coalition formation (SRCF) algorithm.The summary is given at the end of this chapter.2.1 System ModelWe consider a CRN with N SUs and M PUs. Each SU corresponds to a transmitter-receiver pair and each PU transmits data via a licensed channel. There are M licensedchannels. Let N = {1, 2, . . . , N} denote the set of SUs and M = {1, 2, . . . ,M} denotethe set of PUs. Assume that the CRN works in a time slotted manner and the slotChapter 2. Traffic Demand-based Cooperation Strategy in CRNs 11duration is T . At the beginning of each time slot, if an SU chooses to participate incooperative spectrum sensing and access, it will perform sensing before accessing theavailable channels and the sensing duration is τ . Each SU has different amount of datain its buffer waiting to be transmitted and only these SUs participating in sensing canobtain access for channel use. Each SU selectively joins in cooperative sensing based onthe knowledge of the traffic demand and channel capacity.We assume that during the sensing stage, each SU can only sense one channel. Thisassumption is also made in [11] and [15]. In order to avoid interference between transmis-sion of different SUs, we assume that a channel can only be accessed by one SU at a time.Let Sj denote the set of SUs choosing to sense and access channel j ∈ M. We use Pf,i,jand Pd,i,j to denote the false alarm probability and detection probability of SU i ∈ Nwhen it detects channel j ∈ M, respectively. The detection probability is the probabilitythat the channel is detected as busy when it is indeed busy. The false alarm probabilityis the probability that the channel is detected as busy when it is idle. Since we use thecooperative sensing method, in each coalition there is a fusion center collecting sensingresults from SUs and making a decision on the channel availability. The fusion centeruses OR rule to decide the availability of channels [22]. The false alarm probability anddetection probability of the set of SUs Sj choosing to detect channel j ∈ M are given asPf,j = 1−∏i∈Sj(1− Pf,i,j), (2.1)Chapter 2. Traffic Demand-based Cooperation Strategy in CRNs 12andPd,j = 1−∏i∈Sj(1− Pd,i,j). (2.2)Let Wt,i denote the transmit power of SU i and Bj denote the bandwidth of channelj. SU i can achieve a transmission rate of Ri,j over the channel j asRi,j = Bj log2(1 + |gi|2Wt,iσ2n), (2.3)where gi denotes the channel gain of transmission link of SU i and σ2n is the noise power.We use PI,j to denote the probability that the channel j is idle. Since the slot durationT is very short, we assume that the information bits in SU i’s buffer are Di, which is aconstant during a time slot. This assumption is also made in [10] and [17]. In order toencourage SUs with high traffic demand to participate in sensing and accessing channels,we give SUs chances to access channel according to their traffic demands. The probabilitythat SU i ∈ Sj can access channel j when this channel is detected as idle can be modeledasPi(Sj) =Di∑k∈SjDk. (2.4)We assume that SUs do not cheat at reporting the information of traffic demand whencooperating with other SUs. The behaviour of dishonest SUs is beyond the scope of thisthesis and may be analyzed in future work using mechanism design.Given that SU i obtains access to an available channel j, since SU i cannot transmitmore than the number of information bits in its buffer, the transmission time for SU i,Chapter 2. Traffic Demand-based Cooperation Strategy in CRNs 13denoted as ti,j , isti,j = min{DiRi,j, T − τ}. (2.5)The probability that channel j is correctly detected as idle is PI,j(1 − Pf,j). Theexpected throughput that SU i can achieve if it chooses to sense and access channel j isUi(Sj) =PI,j(1− Pf,j)Pi(Sj)Ri,jti,jT. (2.6)We also consider the power consumption of SU i, which includes power consumptionof sensing and transmission. There are two cases that SU will perform transmission overchannel j. The first case is that channel j is busy and it is detected as idle, whichhas a probability of (1 − PI,j)(1 − Pd,j). The second case is that channel j is idle andit is detected as idle, which has a probability of PI,j(1 − Pf,j). Therefore, the powerconsumption Ei can be modeled asEi(Sj) =(((1− PI,j)(1− Pd,j) + PI,j(1− Pf,j))Pi(Sj)Wt,iti,j +Ws,iτ) 1T, (2.7)where Ws,i denotes the sensing operation power of SU i.In addition to throughput, we consider energy efficiency as another factor that affectsSUs’ decisions on cooperative sensing. The energy efficiency of SU i in coalition Sj isdefined as throughput over power consumption, which isηi(Sj) =Ui(Sj)Ei(Sj). (2.8)The objective of each SU is to maximize its throughput while keeping its energyefficiency above the threshold value ηmin. That is, during a time slot, each SU aims toChapter 2. Traffic Demand-based Cooperation Strategy in CRNs 14transmit the data in its buffer as much as possible under the condition that its energyefficiency is not smaller than a predefined threshold. When the traffic demand of anenergy-constrained SU is very low, it may have to spend too much energy in order totransmit just several information data bits if it joins in cooperative sensing. In this case,where the cost of cooperation outweighs the payoff, this SU simply chooses not to performsensing and saves energy for transmission next time.2.2 Coalition FormationIn this section, we formulate the individual cooperation strategy problem as an NTUcoalition formation game. We propose a sequential coalition formation algorithm toobtain a final coalition structure.2.2.1 NTU Coalitional Game FormulationAccording to coalitional game terminology, we refer to the set of SUs N as the set ofplayers in this game, and denote the coalition value function as v. Then, this coalitionalgame is described by the pair of (N , v). This is an NTU game, because in this gamethe payoff of a coalition cannot be assigned a real value, instead different players receivedifferent payoffs within each coalition. The value of a coalition S is defined by a |S|-dimensional vector. That is v(S) = (xi(S), ∀ i ∈ S), where xi(S) represents the payoffChapter 2. Traffic Demand-based Cooperation Strategy in CRNs 15that SU i receives in coalition S and is given asxi(S) =⎧⎪⎪⎨⎪⎪⎩Ui(S), if ηi(S) ≥ ηmin,0, otherwise.(2.9)Note that the coalition value of an SU is the expected throughput if its energy effi-ciency is higher than or equal to the threshold ηmin, and is equal to zero otherwise. EachSU can only choose to sense and access one of the M channels. All the SUs that choosethe same channel form a coalition. We denote the coalition sensing and accessing channelj ∈ M as Sj. In addition, we define the set of the SUs that choose to quit sensing asSM+1 and the payoff of each SU in SM+1 is zero.From (2.4) and (2.6), with more SUs joining one coalition, an SU in this coalitiongets less chance to access channel, which may lead to a lower payoff. Therefore, thegrand coalition, which includes all SUs in a coalition, is not the optimal partition forthis coalitional game. In order to study this coalition formation problem, we define thepreference of player i over different coalitions as follows:Definition 1 [23]: SU i ∈ N prefers coalition Sk over Sm, where Sk, Sm ⊆ N , isequivalent to xi(Sk) ≥ xi(Sm). This relation can be represented asSk i Sm ⇔ xi(Sk) ≥ xi(Sm). (2.10)Since the objective of an SU is to obtain a higher payoff by leaving or joining acoalition, the SU would leave its current coalition and join a new coalition if it prefersthe new coalition over its current coalition according to Definition 1. A move of any SUChapter 2. Traffic Demand-based Cooperation Strategy in CRNs 16will result in a new partition. Therefore, we study the stability of coalition partition byintroducing the concept of Nash-stable partition, which is defined as follows:Definition 2 [24]: A coalition partition Π of N is Nash-stable if ∀ i ∈ N SΠ(i) iSk ∪ {i} for all Sk ∈ Π ∪ {∅}, where SΠ(i) denotes the set S ∈ Π such that i ∈ S.According to Definition 2, a coalition partition is Nash-stable if no player has anincentive to leave its current coalition and join a new coalition. Therefore, all playerswill stay in their current coalition in a Nash-stable partition. Since there are (M + 1)Npossible partitions given that the number of SUs and the number of channels are finite,we can use the exhaustive search algorithm to find all possible Nash-stable partitions ofthis coalitional game. However, the exhaustive search algorithm leads to a high compu-tational complexity because the number of possible partitions grows exponentially withthe number of SUs. Thus, we propose an algorithm with low complexity to obtain thefinal partition in the next section.2.2.2 Sequential Coalition Formation (SCF) AlgorithmWe propose the SCF algorithm, which is originated from the concept introduced in [25].The sequential game of coalition formation is defined by the coalition value function vand the rule of order ρ, which means the coalition structure is formed step by step andat each step only one player can propose a coalition structure. Players make moves oneby one according to the rule of order ρ. Once a player has joined a coalition S, it has toremain in this coalition, which means the next active player can only make a coalitionChapter 2. Traffic Demand-based Cooperation Strategy in CRNs 17proposal among the remaining players.In the proposed algorithm, the rule of order ρ is determined by traffic demand of SUs.That means the SU with the highest traffic demand is the first one to make a move.Since SUs act selfishly, we assume that at each step the only active SU simply concernsits own payoff and chooses the best coalition to join. The active SU makes a decisionbased on the current coalition structure and remains in that coalition once it has joined acoalition. The coalition partition is formed step by step by each SU. Thus, the sequentialcoalition formation involves N iterations. Let Π(k) denote the partition formed in the kthiteration. In (k+1)th iteration, SU k+1 becomes active. It can either join any coalitionin Π(k) or form a singleton coalition, which yields the new partition Π(k+1) in (k + 1)thiteration.The proposed SCF algorithm is shown in Algorithm 1. First, SUs communicatethe traffic demand information with each other (lines 1 to 3) and the traffic demandinformation vector D is obtained (line 4). Q(X ) is a sorting function that maps a vectorX to a |X |-dimensional vector. It returns a vector with each element representing thesorted index of each X ’s element in descending order. For example, for Y = Q(X ), whereX = (x1, x2, x3, x4) and x2 ≥ x3 ≥ x1 ≥ x4, Y = (2, 3, 1, 4), which means x2 ranks first, x3ranks second, x1 ranks third, and x4 ranks fourth in the sequence. The rule of order ρ is avector obtained through sorting D by applying function Q(D) (line 5). At the beginningof the sequential coalition formation, we form the initial partition by letting all SUs joinquit sensing set SM+1 (line 6). After that, SUs make coalition formation decision one byChapter 2. Traffic Demand-based Cooperation Strategy in CRNs 18one according to ρ. For example, the SU with the highest traffic demand makes the firstchoice. During each iteration, we first set the payoff of active SU i, which is originallyin quit sensing set, to zero (line 8). We also initialize coalition structure by setting it asthe structure we obtained in last iteration (line 9). We assume that SU i leaves the quitsensing coalition and joins coalition j, which results in a new coalition structure Π(i)∗(line 10). Then SU i calculates its payoff in potential new coalition according to (2.9)(line 12) and compares it with its current payoff (line 13). It leaves its current coalitionand joins a new coalition if it prefers the new coalition. Thus, a new partition is formed(line 14), and its payoff is updated (line 15). After N iterations, the final partition Π(N)and corresponding coalition payoff xi are obtained (line 20).To better explain our proposed SCF algorithm, we have the following example. Con-sider a CRN with N = {1, 2, 3, 4} and M = {1, 2}. We denote S3 as the quit sensingcoalition. Without loss of generality, we assume that D3 ≥ D4 ≥ D2 ≥ D1. Thus, weobtain ρ = (3, 4, 2, 1) by calculating Q(D). According to SCF algorithm, all SUs are inthe quit sensing coalition S3 initially. In the first iteration, SU 3 makes the first choice(i.e., ρ(1) = 3). Assume that SU 3 prefers channel 1 over channel 2, then SU 3 chooseschannel 1 to sense and access. SU 4 ranks second according to ρ. Thus, SU 4 makes thesecond choice. Assume that x4({4}2) ≥ x4({3, 4}1) ≥ x4(S3), SU 4 chooses to join coali-tion S2. For SU 2, which ranks third, assume that x2({3, 2}1) ≥ x2({4, 2}2) ≥ x2(S3).SU 2 joins coalition S1. SU 1 is the last one to make a decision. It can choose to join{3, 2}1 or {4}2 or stay in quit sensing coalition S3. Assume that the energy efficiency ofChapter 2. Traffic Demand-based Cooperation Strategy in CRNs 19Algorithm 1 Sequential Coalition Formation (SCF) Algorithm in CRN1: for each i ∈ N do2: SU i broadcasts its traffic demand Di to other SUs and receives information fromother SUs3: end for4: D := (D1, D2, . . . , DN)5: ρ := Q(D)6: Set Π(0) := {{1, 2, . . . , N}(0)M+1}7: for i = 1 to N do8: Set xρ(i) := 09: Set Π(i) := Π(i−1)10: for j = 1 to M do11: Set Π(i)∗ :={Π(i−1) \ {S(i−1)M+1 , S(i−1)j }}⋃{S(i−1)M+1 \ {ρ(i)}, S(i−1)j⋃{ρ(i)}}12: Calculate xρ(i)(S(i−1)j⋃{ρ(i)}) according to (2.9)13: if xρ(i)(S(i−1)j⋃{i}) ≥ xρ(i) then14: Set Π(i) := Π(i)∗15: Set xρ(i) := xρ(i)(S(i−1)j⋃{i})16: end if17: end for18: end for19: Calculate xi(S), ∀ i ∈ S and S ∈ Π(N)20: Output Π(N) and xi, ∀ i ∈ NSU 1 is lower than the energy efficiency threshold no matter it joins {3, 2}1 or {4}2, SU1 chooses to stay in coalition S3 and quits sensing during this time slot. Therefore, thefinal partition is Π(4) = {{3, 2}1, {4}2, {1}3}.2.3 Performance EvaluationIn this section, we compare the performance between our proposed SCF algorithm andthe switch rule-based coalition formation (SRCF) algorithm [1] from the perspective ofaggregate throughput and energy efficiency, respectively. Moreover, we compare theChapter 2. Traffic Demand-based Cooperation Strategy in CRNs 20Table 2.1: List of Simulation ParametersParameter ValueNumber of SUs N 10Number of PUs (licensed channels) M 6Path loss exponent γ 2Bandwidth of channel j Bj 100 kHzProbability that channel j is being idle PI,j [0.5, 1]False alarm probability of SU i when it detectschannel j Pf,i,j0.1Detection probability of SU i when it detects chan-nel j Pd,i,j0.9Noise power σ2n 0.01 mWTransmission power of SU i Wt,i 100 mWSensing power of SU i Ws,i 50 mWSlot duration T 100 msSensing duration τ 5 msAverage number of packets generated by SU dur-ing a time slot λ0.2 packetThe energy efficiency threshold ηmin 50 kbit/Joulecomputational complexity of these two algorithms by analyzing their running time.Unless stated otherwise, we consider a CRN with ten SUs and six PUs (i.e., sixlicensed channels). The transmitter and receiver of each SU is randomly placed in a 100m × 100 m square region. We model the channel gain of the link of SU i as |gi|2 = 1/dγi ,where di is the distance between the transmitter and receiver of SU i, and γ is the pathloss exponent. We set γ to 2. According to IEEE Standard 802.22, we set the detectionprobability of every SU at each channel as 0.9 and the false alarm probability as 0.1.The probability that the channel is idle is randomly chosen between [0.5, 1]. The numberof packets generated by each SU during a time slot follows Poisson distribution with anaverage rate of λ = 0.2 packet per time slot, and each packet is 20 kb.The list of parameters is shown in Table 2.1. We run the simulation on a computerChapter 2. Traffic Demand-based Cooperation Strategy in CRNs 211 2 3 4 5 6 7 8 9 1050100150200250300350400Number of PUs MAggregate throughput (kbit/s) SCF algorithmSRCF algorithm [1]Figure 2.1: Aggregate throughput versus the number of PUs M for N = 10.that is equipped with Intel(R) Core(TM)2 Duo P7350 CPU 2.00 GHz processor and 2.00GB RAM. We use MATLAB as simulation tool in the Windows 7 operation system. Theperformance of algorithms are compared under the same parameters setting.When we apply the SRCF algorithm [1], different initial partitions may lead todifferent Nash-stable partitions. Therefore, we randomly set the initial partition andrun SRCF algorithm 50 times to obtain 50 Nash-stable partitions. We calculate theaverage payoff of each SU and obtain the average coalition value of these Nash-stablepartitions, which we denote as the average Nash-stable partition. To better compare SCFalgorithm and SRCF algorithm, we analyze the results of average Nash-stable partitionin the following simulation.Figure 2.1 shows the aggregate throughput of SUs when we increase the number ofChapter 2. Traffic Demand-based Cooperation Strategy in CRNs 222 4 6 8 10 12 14 16 18 200100200300400500600700Number of SUs NAggregate throughput (kbit/s) SCF algorithmSRCF algorithm [1]Figure 2.2: Aggregate throughput versus the number of SUs N for M = 6.PUs M (i.e., the number of channels) from 1 to 10. Results show that our proposedSCF algorithm has a better performance than the SRCF algorithm in terms of aggregatethroughput. For both algorithms, the aggregate throughput increases with M at first.This is because the throughput is constrained by channel resources when M is small.Thus, when more channels are available, the traffic demand of SUs is satisfied and a higheraggregate throughput can be obtained. However, when M is large, increasing M furtherdoes not improve aggregate throughput too much, because the aggregate throughput isconstrained by the traffic demand of SUs when channel resources are abundant.Figure 2.2 shows the aggregate throughput of SUs as the number of SUs N increasesfrom 2 to 20. Results show that performance of SCF algorithm is similar to or betterthan that of SRCF algorithm in terms of aggregate throughput. In our proposed SCFChapter 2. Traffic Demand-based Cooperation Strategy in CRNs 231 2 3 4 5 6 7 8 9 100.811.21.41.61.822.22.42.6Number of PUs MEnergy efficiency (kbit/Joule)× 103 SCF algorithmSRCF algorithm [1]Figure 2.3: System energy efficiency versus the number of PUs M for N = 10.algorithm, SUs with high traffic demand are given priority to sense and access goodchannels (i.e., channel with high probability of being idle). Therefore the spectrumresources are utilized with a high efficiency. However, in SRCF algorithm, SUs actselfishly and the channel resources can be occupied by SUs with low traffic demand.Thus, the aggregate throughput of SUs for SRCF algorithm is less than that for SCFalgorithm. Besides, the number of SUs N increases the aggregate throughput when Nvaries from 2 to 20.Figure 2.3 shows the average energy efficiency of SUs when we increase the numberof PUs M from 1 to 10. In SRCF algorithm, all SUs are supposed to participate incooperative sensing. SUs with low traffic demand spend energy on sensing but mayobtain a low throughput. However, in our proposed SCR algorithm, SUs with energyChapter 2. Traffic Demand-based Cooperation Strategy in CRNs 242 4 6 8 10 12 14 16 18 20 22 24 26 28 3000.050.10.150.20.250.30.350.40.45Number of SUs NRunning time of algorithm (s) SRCF algorithm [1]SCF algorithmFigure 2.4: Running time of algorithms versus the number of SUs N for M = 6.efficiency lower than the ηmin choose to quit sensing and save energy for transmissionnext time. Thus, the average energy efficiency for SCF algorithm is higher than that forSRCF algorithm. Besides, for both algorithms, the energy efficiency increases with Mwhen M is small. This is because SUs that participate in sensing obtain a low throughputwhen channel resources are insufficient, which leads to a low energy efficiency. As morechannels become available, SUs achieve higher throughput and thus obtain a higherenergy efficiency.To provide an idea of the complexity of our proposed SCF algorithm compared withSRCF algorithm, we evaluate the running time of these two algorithms as the numberof SUs N increases from 2 to 30. Results in Figure 2.4 show that the running time ofthe SRCF algorithm is almost three times that of our proposed SCF algorithm. OurChapter 2. Traffic Demand-based Cooperation Strategy in CRNs 25proposed SCF algorithm involves only N iterations. During each iteration, the activeSU only has to calculate coalition payoff M times before choosing the best coalition tojoin. However, for SRCF algorithm, in order to reach a Nash-stable partition, each SUhas to calculate and compare its coalition payoff in M different coalitions whenever thereis a change of partition. Thus, the complexity of SRCF algorithm is higher than ourproposed SCF algorithm. Therefore, SRCF algorithm performs worse than our proposedSCF algorithm in terms of running time. When N = 30, our proposed SCF algorithmoutperforms SRCF algorithm by over 60% in terms of running time.2.4 SummaryIn this chapter, we studied the cooperation strategy in CRNs with multiple channelsfrom the perspective of traffic demand of SUs. We proposed a joint cooperative spec-trum sensing and access scheme, which allows energy-constrained SUs work more effi-ciently through selectively participating in cooperation. An NTU coalition formationgame was formulated to study this cooperative sensing problem, in which each SU makesindividual decision on joining in coalition to maximize a payoff that takes into accountthe expected throughput and energy efficiency. Since exhaustive search method leadsto a high computational complexity, we proposed an SCF algorithm. Simulation resultsshowed that our proposed SCF algorithm obtains the final partition that outperforms theNash-stable partition by the SRCF algorithm in [1] in terms of aggregate throughput,energy efficiency, as well as computational complexity.26Chapter 3Overlapping Coalitional GameApproach for Cooperation Strategyin CRNsIn the previous chapter, we study the cooperation strategy in CRNs, where each SU canonly sense one channel at a time. In this chapter, we extend the problem by enablingeach SU to sense multiple channels. We apply the overlapping coalitional game theoryto the design of CSSA strategy in CRNs. We first present the system model, which isdifferent from the system model proposed in Chapter 2. Then, we formulate the problemas an overlapping coalitional game and propose two coalition formation algorithms. Thestability of the algorithms is analyzed and it is followed by the performance evaluation.A summary is provided at the end of this chapter.Chapter 3. Overlapping Coalitional Game Approach for Cooperation Strategy in CRNs 273.1 System ModelIn this chapter, we still consider a CRN with N SUs, M PUs, and a common base station.Each SU corresponds to a transmission link between the transmitter of the SU and thebase station. Each PU transmits data via a licensed channel. Let N = {1, 2, . . . , N}denote the set of SUs and M = {1, 2, . . . ,M} denote the set of PUs. Each SU cansense multiple channels and all the SUs sensing the same channel form a group. Eachchannel is sensed cooperatively by one group of SUs and the channel is assigned to oneof the group members when it is detected as idle. Each SU has different amount ofdata in its buffer waiting to be transmitted and only the SUs participating in sensingcan obtain access for channel use. SUs selectively participate in cooperative sensingbased on the knowledge of the traffic demand and channel capacity. In order to avoidinterference between transmission of different SUs, we assume that an idle channel canonly be accessed by one SU at a time.In Chapter 2, we assign certain values to detection probability and false alarm prob-ability of each SU respectively. In this chapter, we calculate these two parameters basedon specific sensing parameters. The detection probability of SU i at channel j is [22]Pd,i,j(ε, γi,j) = Q((εσ2n− γi,j − 1)√Ns2γi,j + 1), (3.1)where Q(.) is the tail probability for the standard normal distribution, ε is the detectionthreshold, σ2n denotes noise power, γi,j is the received SNR at SU i when it senses channelj, Ns is the number of sensing samples during the sensing stage in a time slot.Chapter 3. Overlapping Coalitional Game Approach for Cooperation Strategy in CRNs 28The false alarm probability of SU i at channel j can be expressed as [22]Pf,i,j(Pd,i,j, γi,j) = Q(√2γi,j + 1Q−1(Pd,i,j) +√Nsγi,j). (3.2)According to (3.2), a high detection probability leads to a high false alarm probability.To protect the transmission of the PU j, we set a desired target value P¯d,j. When SUsperform cooperative sensing at channel j and use the OR rule to make a sensing decision,the cooperative sensing performance needs to satisfy the target value. When the targetdetection probability value at each channel is fixed, we can compute the target detectionprobability of each SU as [26]P¯d,i,j = 1− (1− P¯d,j)1|Sj| , (3.3)where |Sj| denotes the number of SUs sensing channel j.We apply the P¯d,i,j obtained by (3.3) to calculate Pf,i,j in (3.2). According to ORrule, we calculate the false alarm probability at channel j, which is Pf,j, according to(2.1).In this chapter, we assume that each member in the same coalition obtains an equalchance to access channels. The probability that SU i ∈ Sj can access channel j giventhat this channel is detected as idle is 1|Sj| . The probability that channel j is correctlydetected as idle is PI,j(1−Pf,j), where PI,j is the probability that channel j is idle. Thus,the probability that SU i is allowed to perform transmission over channel j withoutinterfering the transmission of PU isPUi,j = PI,j(1− Pf,j)1|Sj|. (3.4)Chapter 3. Overlapping Coalitional Game Approach for Cooperation Strategy in CRNs 29Given that SU i is assigned to transmit data over channel j, the achieved throughputisUi,j =Ri,jti,jT, (3.5)where Ri,j is the transmission rate of SU i on channel j and it can be calculated accordingto (2.3), and ti,j is the transmission time of SU i on channel j according to (2.5).We also consider the power consumption of SU i, which includes power consumptionof sensing and transmission. There are two cases that SU will perform transmission overchannel j. The first case is that channel j is busy and it is detected as idle, which hasa probability of (1 − PI,j)(1 − Pd,j). The second case is that channel j is idle and it isdetected as idle, which has a probability of PI,j(1−Pf,j). Therefore, the probability thatSU i is assigned channel j to transmit data isPEi,j =((1− PI,j)(1− Pd,j) + PI,j(1− Pf,j)) 1|Sj|. (3.6)The energy spent on data transmission isEti,j = Wt,i,jti,j. (3.7)The energy spent on spectrum sensing when SU i senses one channel isEsi,j = Ws,i,jτ. (3.8)In Chapter 2, it is assumed that an SU can only sense one channel in a time slot.However, in practice, SUs are able to sense multiple channels during the sensing stage[1]. We denote the set of channels that SU i chooses as Ai. Now we consider the expectedChapter 3. Overlapping Coalitional Game Approach for Cooperation Strategy in CRNs 30throughput that SU i can obtain by choosing channel set Ai. Let K denote a subset ofAi. All the channels in set K are detected as idle and provide SU i an opportunity toperform transmission over the channel. The probability is∏j∈K(PEi,j)∏j∈Ai\K(1 − PEi,j).Although SU may be provided with multiple channels to access, it can transmit overonly one channel during the transmission stage in a time slot. It will choose the bestone among these |K| channels, which can maximize its throughput (i.e., maxj∈K{Ui,j}).If SU i chooses channel argmaxj∈K{Ui,j} to access among these offered channels, SU imay fail to transmit data due to the mis-detection of the primary user. The probabilitythat SU i can successfully transmit data over this channel isPUi,argmaxj∈K{Ui,j}PEi,argmaxj∈K{Ui,j}. Thus, theexpected throughput that SU i can obtain isUi(Ai) =∑K⊆Ai((∏j∈KPEi,j∏j∈Ai\K(1− PEi,j))PUi,argmaxj∈K{Ui,j}PEi,argmaxj∈K{Ui,j}maxj∈K{Ui,j}). (3.9)As shown in (3.9), the expected throughput of SU i increases with the size of Ai. Thisis because by choosing more channels to sense, SU i obtains more opportunities to ac-cess channel and achieves higher throughput. However, for an energy-constrained SU, itshould limit the energy spent on sensing in order to save enough energy for data transmis-sion. Therefore, we need to consider the expected power consumption when SU i chooseschannel set Ai. The power consumption contains two parts: sensing power consumptionand data transmission power consumption. The power consumption spent on sensingeach channel in Ai is inevitable to SU i. However, the power spent on transmission oc-curs only when SU i is performing data transmission over a specific channel. Thus theChapter 3. Overlapping Coalitional Game Approach for Cooperation Strategy in CRNs 31expected power consumption of SU i isEi(Ai) =(∑K⊆Ai((∏j∈KPEi,j∏j∈Ai\K(1− PEi,j))Eti,argmaxj∈K{Ui,j})+∑j∈AiEsi,j)1T. (3.10)To reach a balance between throughput and power consumption, we propose theenergy efficiency as a criterion to evaluate SUs’ decision on cooperation. We define theexpected energy efficiency of SU i as [27]ηi(Ai) =Ui(Ai)Ei(Ai). (3.11)The objective of each SU is to maximize its throughput subject to energy efficiencyconstraint. That is, during a time slot, each SU aims to transmit the data in its bufferas much as possible under the condition that its energy efficiency is not smaller than apredefined threshold. When the traffic demand of an energy-constrained SU is very lowand SU participates in cooperative sensing, it may have to spend too much energy inorder to transmit just several information data bits. In this case, the cost of cooperationoutweighs the payoff, this SU can simply choose not to perform sensing and save energy fortransmission next time. Moreover, all SUs choosing the same channel perform cooperativesensing and share the access to this channel. Thus, the problem is how each SU shouldcooperate with other SUs and which channel it should choose. We will address thisproblem in the next section.Chapter 3. Overlapping Coalitional Game Approach for Cooperation Strategy in CRNs 323.2 Overlapping Coalitional Game for CooperationStrategyIn this section, we formulate the CSSA problem as an NTU overlapping coalitional game.The payoff value of each SU captures the expected throughput and energy efficiency thatcan be obtained by joining multiple coalitions. For SUs to make distributed decisionon coalition formation, we define three move rules that take into account both socialwelfare and individual payoff. We propose an overlapping coalition formation (OCF)algorithm to enable SUs to form a final stable coalition structure. The convergence ofthis algorithm is analyzed. Moreover, we modify the SCF algorithm proposed in Chapter2 to address the problem in our new system model. The modified SCF algorithm hasa lower computational complexity and requires less information exchange than OCFalgorithm.3.2.1 NTU Overlapping Coalitional Game FormationIn this CSSA strategy, SUs choose different channels to maximize their expected through-put while satisfying the energy efficiency requirement. All SUs choosing the same channelperform spectrum sensing cooperatively to improve the sensing performance, and sharethe spectrum resources based on the channel availability. We assume that all SUs sens-ing the same channel form a coalition. Therefore, we can formulate this problem as acoalitional game. Since in our system model, an SU can choose multiple channels andChapter 3. Overlapping Coalitional Game Approach for Cooperation Strategy in CRNs 33contribute to multiple coalitions, this is an overlapping coalitional game. Different fromtraditional disjoint coalitional game, in an overlapping coalitional game, a player is al-lowed to join more than one coalition. Therefore the coalitions are overlapped, whereeach player contributes to multiple coalitions and obtains higher payoff. In addition, inour system model, the payoff of each SU in one coalition depends on its traffic demand.Thus, the utility obtained by each SU in a coalition may be different and this utilitycannot be transferred among different SUs. Therefore our formulated coalitional game isan NTU game. We first introduce the definition of an NTU overlapping coalitional game:Definition 3 [28]. An NTU overlapping coalitional game G = (N , v) is given by a setof players N = {1, . . . , N} and a function v : S → R|S|, where S ⊆ N denotes a coalitionformed by the players and v(∅) = 0.Corresponding to our system model, the players of this game refer to N SUs. Theycooperate with each other and form different coalitions to sense and access differentchannels. The value function v maps each coalition S ⊆ N to an |S|-dimensional vector.We define the coalition value as the expected payoff that each SU can obtain in thiscoalition: v(Sj) = (xi(Sj), ∀ i ∈ Sj), where xi(Sj) = PUi,jUi,j according to (3.4) and (3.5).However, this is not the total payoff that SU i can obtain in the game, because SU ican join multiple coalitions in an overlapping coalitional game. We will discuss the totalpayoff of SU i in the following context.In a coalitional game, players autonomously form different coalitions to achieve higherpayoff. The collection of these coalitions is referred to as coalition structure. In a disjointChapter 3. Overlapping Coalitional Game Approach for Cooperation Strategy in CRNs 34coalitional game, a coalition structure is a partition ofN [29]. However, in an overlappingcoalitional game, SUs are allowed to join multiple coalitions at the same time. Therefore,the coalitions are overlapped. We define the coalition structure Π as follows:Definition 4 [30]. An overlapping coalition structure Π over a player set N is definedas a set Π = {S1, . . . , SK}, where K is the number of coalitions. ∀ 1 ≤ j ≤ K, Sj ⊆ Nand ∪Kj=1Sj = N . Since coalitions can be overlapping, ∃ Si, Sj ∈ Π, i = j such thatSi ∩ Sj = ∅.Since all the SUs choosing the same channel form a coalition, there are at most Mcoalitions. In addition, some SUs with very low traffic demand may prefer to stay idle tosave energy for future transmission. Thus, they may choose not to perform sensing. Wedenote the set of SUs that quit sensing as SM+1. Therefore, in our system model, thenumber of coalitions K is less than or equal to M + 1.Since an SU can belong to more than one coalition, we consider the payoff that SUi obtains in an overlapping coalition structure. We cannot calculate the payoff of an SUby summing up all the payoff it obtains from all the coalitions it belongs to. Althoughan SU may be chosen by more than one channel at the same time, it can transmit overonly one channel at a time. Therefore, we define the total payoff of SU i as followspi(Π) =⎧⎪⎪⎪⎨⎪⎪⎪⎩Ui(Ai), if ηi(Ai) ≥ ηmin,−∞, otherwise,(3.12)where Ai = {j | SU i ∈ Sj and Sj ∈ Π} is the set of channels that SU i chooses tosense and access. For example, consider an overlapping coalitional game G = (N , v),Chapter 3. Overlapping Coalitional Game Approach for Cooperation Strategy in CRNs 35where N = {1, 2, 3, 4} and M = {1, 2}. SUs form coalitions: S1 = {1, 2}1, S2 = {2, 3}2and S3 = {4}3, where S1 = {1, 2}1 means SUs 1 and 2 form a coalition to sense andaccess channel 1. The collection of these coalitions Π = {{1, 2}1, {2, 3}2, {4}3} is theoverlapping coalition structure of N . The corresponding channel sensing sets for eachSU are A1 = {1}, A2 = {1, 2}, A3 = {2}, and A4 = ∅.When the expected energy efficiency of SU i is greater than the energy efficiencythreshold ηmin, the total coalition value of SU i is equal to the expected throughput itobtains by choosing the channel set Ai. Otherwise, it is equal to negative infinity. Thisdefinition guarantees that the energy efficiency of SUs during the coalition formationprocess will not be lower than the threshold. In addition, we define the payoff of eachSU in set SM+1 as zero. Note that an SU cannot belong to SM+1 and Sj , j ∈ M at thesame time. Once an SU decides to join quit sensing coalition SM+1, it does not sense andaccess any channel. Thus, it does not belong to any other coalitions. Therefore, SM+1 isan isolated coalition and it is not overlapped with any other coalitions.After defining the coalition value of SUs and overlapping coalition structure, we con-sider the preference order of SUs. The preference order helps SUs choose between twocoalitions and select the better channel to sense and access. In some existing works (e.g.,[1] and [15]), the SUs are selfish, which means an SU seeks to maximize its own payoffwithout considering the benefits of other SUs. In this case, the channel may be occupiedby SUs with low traffic demands while SUs with high traffic demands are still in short ofspectrum resources. This leads to a low utilization of the channels. Thus, we introduceChapter 3. Overlapping Coalitional Game Approach for Cooperation Strategy in CRNs 36a preference order that takes into account both social welfare and individual payoff. Wedefine the social welfare as the value of a coalition structure Π and it is calculated asu(Π) =∑i∈Npi(Π). (3.13)The value of a coalition structure is the sum of payoffs of all the players in a coalitionstructure. When considering the preference order of an SU, we take into account bothindividual payoff and coalition structure value as follows:Definition 5 [30]. In an overlapping coalitional game G = (N , v), given two coalitionstructures Πp and Πq over N , Πp is i-preferred over Πq, where i ∈ N , is equivalent topi(Πp) > pi(Πq) and u(Πp) > u(Πq). This relation is represented asΠp i Πq ⇔ pi(Πp) > pi(Πq) and u(Πp) > u(Πq). (3.14)According to Definition 5, a coalition structure is preferred over another only whenthe total payoff of the coalition structure and the individual payoff of an SU are bothincreased from one to the other. This preference order not only guarantees the increase ofsocial payoff during the coalition formation process, but also keeps the spectrum efficiencyabove a certain level. Under this preference order, we show that, during the coalitionformation process, the SUs can reach a stable coalition structure after a finite number ofiterations in the following subsection.Chapter 3. Overlapping Coalitional Game Approach for Cooperation Strategy in CRNs 373.2.2 Coalition Formation AlgorithmsBased on the preference order, we define three move rules. During the process of over-lapping coalition formation, SUs make their own decisions on joining or leaving anycoalitions according to their preference order over different coalitions. There are threepossible moves. First, SU joins a new coalition that it does not belong to. Second, SUleaves one of its current coalitions. Third, SU switches from one of its current coali-tions to a new coalition. To provide a mechanism through which SUs can form differentcoalitions by performing above moves, we define three move rules as follows:Definition 6. Join rule: Consider a coalition structure Πp over a set of players N ,where Sj ∈ Πp and i ∈ N \ Sj . A new coalition structure is defined as Πq = {Πp \ Sj} ∪{Sj ∪ {i}}. If Πq i Πp, then SU i joins Sj and Πp changes into Πq.According to Definition 6, in coalition structure Πp, SU i does not belong to coalitionSj at first. We assume that SU i joins coalition Sj and the current coalition structure Πpchanges into a new coalition structure Πq. If Πq is preferred over Πp by SU i accordingto Definition 5, SU i joins coalition Sj and the current coalition structure Πp is replacedby Πq. Although the decision is made by SU i, it does not mean that SU acts selfishlywithout considering the effect of its move to other SUs. This is because an SU joins a newcoalition only when its own payoff and the coalition structure value are both improvedby this movement. For example, if SU i can increase its payoff by joining coalition Sj,however its movement is detrimental to other SUs in the game and leads to the decrease ofthe total payoff of all SUs, SU i is not allowed to join coalition Sj in this case. Therefore,Chapter 3. Overlapping Coalitional Game Approach for Cooperation Strategy in CRNs 38individual payoff and social welfare are both taken into account in this join rule.Definition 7. Quit rule: Consider a coalition structure Πp over a set of players N ,where Sj ∈ Πp and i ∈ N ∩ Sj. A new coalition structure is defined as Πq = {Πp \ Sj} ∪{Sj \ {i}}. If Πq i Πp, then SU i leaves Sj and Πp changes into Πq.According to quit rule, SU i leaves one of its current coalitions j and Πp changesinto Πq if this newly formed coalition structure is preferred over the current one by SUi. Although SU i can always increase its chance to access channels by joining morecoalitions, it may still perform quit move sometimes. When there are too many otherSUs in one coalition that SU i belongs to, SU i obtains little chance to access channels.Therefore, in this case, SU i may leave this coalition to increase its payoff according toquit rule.Definition 8. Switch rule [15]: Consider a coalition structure Πp over a set of playersN , where Sj , Sk ∈ Πp and i ∈ Sj , i ∈ Sk, and i ∈ N . A new coalition structure is definedas Πq = {Πp \ {Sj , Sk}} ∪ {Sj \ {i}} ∪ {Sk ∪ {i}}. If Πq i Πp, then SU i switches fromSj to Sk and Πp changes into Πq.The switch rule combines the above two rules together. According to its definition,SU i switches from one of its coalitions to a new coalition when the resulted new coalitionstructure is preferred over the current one. The switch rule balances the size of differentcoalitions and improves the spectrum efficiency. During the coalition formation process,some channels may be chosen by many SUs while some other channels are sensed by fewones. When SUs find that their payoff can be improved by switching from the coalitionChapter 3. Overlapping Coalitional Game Approach for Cooperation Strategy in CRNs 39with many members to another coalition with very few members, they perform switchmoves. In this way, SUs autonomously distribute their contribution to different coalitionsand channels are equally utilized.In order to study the stability of the overlapping coalition structure, we define thestability of an overlapping coalition structure as follows:Definition 9. An overlapping coalition structure Π over a set of players N is stable if∀ i ∈ N , such that i ∈ Sj , i /∈ Sk, and Sj , Sk ∈ Π, SU i will not deviate from Sj or joinSk.According to Definition 9, for any SU i in a stable coalition structure, it will not leaveany of its coalitions or join a new coalition. Therefore, all the SUs would stay in theircurrent coalitions and do not make any changes.Overlapping Coalition Formation (OCF) AlgorithmTo reach a stable coalition structure, we propose an OCF algorithm as shown in Algorithm2. This algorithm is a distributed algorithm, which is executed by each SU i, ∀ i ∈ N .Chapter 3. Overlapping Coalitional Game Approach for Cooperation Strategy in CRNs 40Algorithm 2 Overlapping Coalition Formation (OCF) Algorithm in CRN. It is executedby SU i, ∀ i ∈ N .1: Initialization: Initialize coalitions SM+1 := N ; Sj := ∅, ∀j ∈ M. Initialize the coalitionstructure Π := {S1, . . . , SM , SM+1}, and Πk := Π, ∀ k ∈ N .2: SU i broadcasts its traffic demand Di to other SUs and receives information from otherSUs.3: SU i calculates the optimal transmission power W optt,i,j by solving problems (3.15) and (3.18),∀ j ∈ M.4: repeat5: SU i randomly selects k ∈ Ai and j ∈ M \Ai, where Ai = {j | SU i ∈ Sj and Sj ∈ Π}.6: ΠQuit := {Π \ Sk} ∪ {Sk \ {i}}.7: SU i calculates u(ΠQuit) and pi(ΠQuit) according to (3.11), (3.12) and (3.13).8: ΠJoin := {Π \ Sj} ∪ {Sj ∪ {i}}.9: SU i calculates u(ΠJoin) and pi(ΠJoin) according to (3.11), (3.12) and (3.13).10: ΠSwitch := {Π \ {Sj , Sk}} ∪ {Sj ∪ {i}} ∪ {Sk \ {i}}.11: SU i calculates u(ΠSwitch) and pi(ΠSwitch) according to (3.11), (3.12) and (3.13).12: if ΠQuit i Π then13: Π := ΠQuit,14: else if ΠJoin i Π then15: Π := ΠJoin,16: else if ΠSwitch i Π then17: Π := ΠSwitch.18: end if19: Πi := Π.20: u(Πi) := u(Π).21: SU i broadcasts the information of updated coalition structure Πi and its value u(Πi) toother SUs.22: SU i receives the information of Πn and u(Πn) from other SU n, ∀ n ∈ N \ {i}.23: The collection of the updated information of coalition structure Tinfo := {Π1, . . . ,ΠN}.24: Π := argmaxΠn∈Tinfo{u(Πn)}.25: until ∀ i ∈ N , ∀ k ∈ Ai and j ∈ M \ Ai, the resulted ΠQuit, ΠJoin, and ΠSwitch satisfythat ΠQuit i Π, ΠJoin i Π and ΠSwitch i Π, respectively.26: SU i performs cooperative sensing within each coalition that it belongs to based on Π duringsensing stage. When being assigned to channel j, SU i transmits data with the optimaltransmission power W optt,i,j.In Algorithm 2, we initialize the coalitions by letting all SUs join quit sensing coalitionSM+1 (line 1). Then SU i communicates the traffic demand information with other SUs(line 2). SU i calculates its optimal transmission power W optt,i,j (line 3) through solvingChapter 3. Overlapping Coalitional Game Approach for Cooperation Strategy in CRNs 41problems (3.15) and (3.18), which will be discussed in the next section. After that, SU imakes coalition formation moves according to three move rules. At the beginning of eachiteration, SU i randomly selects a coalition that it currently belongs to Sk and a newcoalition it does not belong to Sj (line 5). SU i assumes that it leaves coalition Sk anda new coalition structure is formed (line 6). SU i calculates its resulted payoff and thevalue of this resulted new coalition structure (line 7). Similarly, it considers potential newcoalition structures resulting from join move and switch move (lines 8, 10), and calculatestheir values (lines 9, 11), respectively. If the resulted coalition structure by quit move ispreferred over the current one by SU i, the coalition structure is updated (line 13). If thequit move does not improve the coalition structure, SU i considers join move (line 14) andswitch move (line 16). SU i updates the information of coalition structure and its value(lines 19 - 20) and communicates the updated information with other SUs (lines 21 - 22).All the updated coalition structure information form a set Tinfo (line 23). The coalitionstructure with the greatest value among Tinfo is selected as the new coalition structure(line 24). SUs repeated the coalition formation process until all SUs will not deviate fromtheir current coalitions or join other new coalitions. In other words, the process convergesto a stable coalition structure. After the coalition formation process, SU i cooperativelysenses the channels with other SUs in corresponding coalitions according to Π. Duringthe spectrum access stage, SU i sets its transmission power to the optimal value when itis allocated a channel to transmit data (line 26).The convergence of the proposed OCF algorithm is guaranteed as follows:Chapter 3. Overlapping Coalitional Game Approach for Cooperation Strategy in CRNs 42Theorem 1. The proposed OCF algorithm converges to a stable overlapping coalitionstructure after a finite number of iterations.Proof. Given that the number of channels M and the number of players N are finite,the number of possible overlapping coalition structures is 2M×N . When implementingthe OCF algorithm, the coalition formation process involves a sequence of moves of SUs,which result in a sequence of coalition structure {Π(0)′ ,Π(1)′ , . . . ,Π(r)′}, where r is thetotal number of moves made by SUs. According to Definitions 5 - 8, after each move ofany SU, a new coalition structure with a higher value is formed. In addition, the numberof possible coalition structures is finite. Therefore, r is a finite number. Π(r)′is the finaloverlapping coalition structure resulting from the last move of SUs. Assume that Π(r)′isnot stable, according to Definition 9, there exists i ∈ N such that SU i will deviate fromone of its current coalitions or join a new coalition. Thus, according to the proposedOCF algorithm, SU i will make join, quit or switch moves and Π(r)′will change into anew coalition structure. This contradicts with the fact that Π(r)′is the final coalitionstructure. Thus, Π(r)′is a stable coalition structure. Therefore, after a finite numberof iterations, the proposed OCF algorithm converges to a stable overlapping coalitionstructure.During the process of coalition formation, each SU seeks to improve its individualutility while increasing the total value of the coalition structure. The movement of SUsleads to a new coalition structure after each iteration. Thus, the OCF algorithm convergesto a stable coalition structure. A larger payoff is obtained every time the coalitionChapter 3. Overlapping Coalitional Game Approach for Cooperation Strategy in CRNs 43structure changes. Moreover, our proposed OCF algorithm is adaptive to the changesin network settings. Whenever new SUs join the network or more channels becomeavailable, traffic demand or channel condition changes, SUs can adaptively change theircooperation strategies and form different coalition structures according to Algorithm 2.Therefore, the traffic demand of SUs are still satisfied, network throughput and systemenergy efficiency are guaranteed when there are changes in network settings.Modified Sequential Coalition Formation (SCF) AlgorithmAlthough the convergence of OCF Algorithm is guaranteed, the number of iterationsrequired to reach a final stable coalition structure may grow exponentially with thenumber of SUs. Therefore, we modify the SCF algorithm proposed in Chapter 2 toaddress this issue. The modified SCF algorithm involves a lower number of iterationsand requires less information exchange among SUs than the OCF algorithm.Similarly to the SCF algorithm proposed in Chapter 2, the coalition structure is alsoformed step by step in the modified SCF algorithm. At each step, only one player canpropose a coalition structure. Players make moves one by one according to the rule oforder ρ, which is determined by traffic demand of SUs. Since in our new system modeloverlapping coalition structure is allowed, the active SU can join multiple coalitions basedon the current coalition structure, which is different from the previous SCF algorithm.Chapter 3. Overlapping Coalitional Game Approach for Cooperation Strategy in CRNs 44Algorithm 3 Modified Sequential Coalition Formation (SCF) Algorithm in CRN.1: for each i ∈ N do2: SU i reports its traffic demand Di to the central coordinator.3: SU i calculates the optimal transmission power W optt,i,j by solving problem (3.15) and(3.18), ∀ j ∈ M.4: end for5: D := (D1,D2, . . . ,DN )6: Central coordinator calculates ρ := Q(D) and broadcasts the information of ρ to all SUs.7: for i = 1 to N do8: if i = 1 then9: SU ρ(i) initializes the coalitions SM+1 := N ; Sj := ∅, ∀j ∈ M, and the coalitionstructure Π := {S1, S2, . . . , SM+1}.10: else11: SU ρ(i) receives the information of Π from SU ρ(i− 1).12: end if13: for each j ∈ M do14: ΠJoin := {Π \ Sj} ∪ {Sj ∪ {ρ(i)}}.15: SU ρ(i) calculates u(ΠJoin) and pρ(i)(ΠJoin) according to (3.11), (3.12) and (3.13).16: SU ρ(i) randomly selects k ∈ Aρ(i), where Aρ(i) = {j | SU ρ(i) ∈ Sj and Sj ∈ Π}.17: ΠSwitch := {Π \ {Sj , Sk}} ∪ {Sj ∪ {ρ(i)}} ∪ {Sk \ {ρ(i)}}.18: SU ρ(i) calculates u(ΠSwitch) and pρ(i)(ΠSwitch) according to (3.11), (3.12) and (3.13).19: if ΠJoin ρ(i) Π then20: Π := ΠJoin,21: else if ΠSwitch ρ(i) Π then22: Π := ΠSwitch.23: end if24: end for25: if i = N then26: SU ρ(i) broadcasts the updated information of Π to other SUs.27: else28: SU ρ(i) sends the updated information of Π to SU ρ(i+ 1).29: end if30: end for31: SU i, ∀ i ∈ N \ {ρ(N)}, receives the updated information of Π from SU ρ(N).32: SU i, ∀ i ∈ N , performs cooperative sensing within each coalition that it belongs to basedon Π during sensing stage. When being assigned to a channel, SU i transmits data withthe optimal transmission power W optt,i,j.The modified SCF algorithm is shown in Algorithm 3. In this algorithm, SUs makedistributed coalition formation decision. However, their behaviors are coordinated by acentral coordinator. First, each SU reports its traffic demand information to the centralChapter 3. Overlapping Coalitional Game Approach for Cooperation Strategy in CRNs 45coordinator (line 2) and calculates its optimal transmission power value (line 3). Thetraffic demand information from different SUs forms an information vector D (line 5).Q(X ) is a sorting function, which is defined the same with the sorting function in oldSCF algorithm proposed in Chapter 2. Central coordinator calculates the rule of order ρthrough sorting D with function Q(D). The information of ρ is broadcast to all SUs (line6). Then, SUs make coalition formation decision one by one according to ρ. For example,the SU with the highest traffic demand (e.g., SU ρ(1)) makes the first choice. It initializesthe coalition structure by setting all SUs in quit sensing coalition SM+1 (line 9). For otherSUs, the active SU receives the updated information of Π from previously active SU (line11). During the coalition formation process, each SU checks all the channels one by oneto look for potential new coalition when it is active. For a new channel j, if SU prefersto sense channel j, SU can join coalition j or switch to coalition j, which means quitmove is not considered in this algorithm. Specifically, the active SU first considers thepotential new coalition structure by assuming that it joins coalition Sj (line 14). TheSU calculates its new payoff and the value of the resulted coalition structure (line 15).Moreover, the active SU randomly selects a coalition it belongs to (line 16), and assumesthat it switches from this selected coalition to coalition Sj (line 17). Also, the value ofthe potential new coalition structure resulting from switch move and SU’s new payoff arecalculated (line 18). If the resulted coalition structure by join move ΠJoin is preferredover the current one Π, the coalition structure is updated (line 20). If the join movecannot improve the coalition structure, the resulted structure by switch move ΠSwitchChapter 3. Overlapping Coalitional Game Approach for Cooperation Strategy in CRNs 46is considered (line 21). After checking all the new coalitions, the currently active SUsends the updated information of Π to the next active SU (line 28). For the last activeSU, it broadcasts the final coalition structure to other SUs (line 26). After the coalitionformation process, SUs perform sensing cooperatively within each coalition that theybelong to according to the final coalition structure. During the transmission stage, SUsperform data transmission with the optimal transmission power (line 32).Although this SCF algorithm does not guarantee the stability of the final coalitionstructure, its performance in terms of throughput is as good as OCF algorithm, whichwill be shown by simulation results in the following section. Moreover, SCF algorithm hasa lower computational complexity than OCF algorithm. During the process of coalitionformation in SCF algorithm, each SU makes coalition formation move only when it isactive and it checks each potential sensing channel only once. Therefore, there are atmost M × N iterations when running SCF algorithms. On the other hand, in OCFalgorithm, coalition formation movement takes place every time there is a new coalitionstructure preferred over current one. SUs moves from one coalition to another or joinnew coalitions until the final stable coalition structure is achieved. Since the number ofthe possible overlapping coalition structure is 2M×N , there are at most 2M×N iterations,which is much more than the number of iterations required in SCF algorithm. Besides,SCF algorithm involves much less information exchange than OCF algorithm. In SCFalgorithm, in addition to the exchange of traffic demand information, each SU onlyhas to send the updated coalition structure information to the next active SU. In OCFChapter 3. Overlapping Coalitional Game Approach for Cooperation Strategy in CRNs 47algorithm, each SU has to exchange the information of updated coalition structure withothers after each iteration, which consumes much more time and energy than runningSCF algorithm.3.3 Adaptive Transmission Power ControlIn this section, we analyze the transmission power control strategy given that an SU hasbeen assigned a channel. We prove that this adaptive transmission power control strategyachieves the optimal transmission power value, which minimizes the energy consumptionspent on data transmission under the constraint that the maximum throughput of SU isachieved.From (2.3), (3.5) and (3.7), we notice the transmission power affects the throughputand the energy spent on transmission. On one hand, increasing the transmission powerleads to an increase of transmission rate, thus improve the throughput. On the otherhand, more energy is required for data transmission when transmission power is increased.Therefore, it is reasonable for SU to adaptively change its transmission power to balancethe tradeoff between throughput and energy consumption. Thus, our objective is toobtain the optimal transmission power that minimizes the energy consumption whileachieving the highest throughput.First, we assume that the transmission power of SU i varies from Wmint,i to Wmaxt,i (i.e.,Wmint,i ≤ Wt,i,j ≤ Wmaxt,i ). Consider SU i has been assigned channel j for transmission.Since the bandwidth of channel j is fixed, the transmission rate Ri,j depends on Wt,i,jChapter 3. Overlapping Coalitional Game Approach for Cooperation Strategy in CRNs 48according to (2.3). During one time slot, the value of T , τ and Di are constant. Thus,both the throughput and energy consumption for transmission are functions of Wt,i,j . Wefirst consider the throughput maximization problem as followsmaximizeWt,i,jUi,j(Wt,i,j)subject to Wmint,i ≤ Wt,i,j ≤ Wmaxt,i .(3.15)Note that the objective function in problem (3.15) is a piecewise function. We can rewriteUi,j(Wt,i,j) by substituting (2.3) to (3.5) and obtain the objective function as followsUi,j(Wt,i,j) =⎧⎪⎪⎨⎪⎪⎩Bjlog2(1+|gi|2 Wt,i,jσ2n)(T−τ)T , if Wt,i,j ≤ W ht,i,j ,DiT , otherwise,(3.16)where W ht,i,j > 0 is the threshold and satisfies that Bj log2(1 + |gi|2Wht,i,jσ2n)(T − τ) = Di.Combining problem (3.15) and equation (3.16), different transmission power range leadsto different optimal solution results to problem (3.15). We denote the set of optimalsolutions to problem (3.15) as W∗t,i,j = {Wt,i,j | Wt,i,j is an optimal solution to problem(3.15)}. We haveW∗t,i,j =⎧⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎩{Wmaxt,i }, if Wmaxt,i ≤ W ht,i,j ,{Wt,i,j | W ht,i,j ≤ Wt,i,j ≤ Wmaxt,i }, if Wmint,i ≤ W ht,i,j ≤ Wmaxt,i ,{Wt,i,j | Wmint,i ≤ Wt,i,j ≤ Wmaxt,i }, otherwise.(3.17)According to (3.17), the number of solutions to problem (3.15) depends on the re-lations between W ht,i,j and the range of the transmission power. In other words, SUsChapter 3. Overlapping Coalitional Game Approach for Cooperation Strategy in CRNs 49set their transmission power to a certain value or within a range to obtain the maxi-mum throughput. In order to save energy spent on transmission while guaranteeing themaximum throughput, we consider an optimization problem that minimizes the energyconsumption for data transmission under the constraint that the highest throughput isobtained. This optimization problem is formulated as followsminimizeWt,i,jEti,j(Wt,i,j)subject to Ui,j(Wt,i,j) ≥ Umaxi,j ,(3.18)where Umaxi,j is the maximum value of Ui,j(Wt,i,j), which can be achieved only when thetransmission power Wt,i,j is an optimal solution to problem (3.15) (i.e.,Wt,i,j ∈ W∗t,i,j). Inother words, the solution to problem (3.15) serves as the constraint in problem (3.18). Inthis way, the requirement for throughput can be guaranteed when we minimize the energyconsumption for data transmission. As we discussed above, the number of solutions toproblem (3.15) depends on the range of transmission power. Therefore, for problem(3.18), the optimal solutions are obtained based on the following three cases.In Case 1, where Wmaxt,i ≤ W ht,i,j , the only solution to problem (3.15) is the optimalsolution to problem (3.18), which is Wmaxt,i . It means SU i has to perform data transmis-sion over channel j with its maximum transmission power in order to achieve the highestthroughput. In this case, the energy consumption for transmission during one time slot,which is the objective function value of problem (3.18), is Wmaxt,i (T − τ).In Case 2, we have Wmint,i ≤ W ht,i,j ≤ Wmaxt,i . The optimal solution to problem (3.15)is {Wt,i,j | W ht,i,j ≤ Wt,i,j ≤ Wmaxt,i }, which is a constraint in problem (3.18). We expressChapter 3. Overlapping Coalitional Game Approach for Cooperation Strategy in CRNs 50Eti,j by substituting (2.3) and (2.5) to (3.7) and obtain the objective function as followsEti,j(Wt,i,j) =Wt,i,jDiBj log2(1 + |gi|2Wt,i,jσ2n) . (3.19)Proposition 1. Function Eti,j(Wt,i,j) in (3.19) is a monotonically increasing function.Proof. We take the first derivative of function Eti,j(Wt,i,j) with respect toWt,i,j and obtainEti,j′(Wt,i,j) =ln 2Diσ2nBj|gi|2(ln(1 + |gi|2Wt,i,jσ2n))2(ln(1 + |gi|2Wt,i,jσ2n)−|gi|2Wt,i,jσ2n1 + |gi|2Wt,i,jσ2n). (3.20)Sinceln 2Diσ2nBj|gi|2(ln(1+|gi|2 Wt,i,jσ2n))2 > 0, to prove the monotonicity of function Eti,j(Wt,i,j), we needto show that ln(1 + |gi|2Wt,i,jσ2n) −|gi|2 Wt,i,jσ2n1+|gi|2 Wt,i,jσ2n> 0 for ∀ Wt,i,j > 0. Assume that y =ln(1+ |gi|2Wt,i,jσ2n)−|gi|2 Wt,i,jσ2n1+|gi|2 Wt,i,jσ2n. We calculate the first derivative of y with respect to Wt,i,j,which isy′ =|gi|2σ2n(11 + |gi|2Wt,i,jσ2n− 1(1 + |gi|2Wt,i,jσ2n)2)=|gi|4Wt,i,jσ4n(1 + |gi|2Wt,i,jσ2n)2.We have y′ > 0, ∀ Wt,i,j > 0. Thus, y is monotonically increasing with respect to Wt,i,jand y(Wt,i,j) > y(0) = 0. Therefore, Eti,j′(Wt,i,j) > 0 and Eti,j is monotonically increasingwith Wt,i,j.According to Proposition 1, the value of Eti,j(Wt,i,j) increases with Wt,i,j when Wht,i,j ≤Wt,i,j ≤ Wmaxt,i . Thus, the optimal solution to problem (3.15) is W ht,i,j , which satisfiesBj log2(1 + |gi|2Wht,i,jσ2n)(T − τ) = Di and Wmint,i < W ht,i,j < Wmaxt,i .Chapter 3. Overlapping Coalitional Game Approach for Cooperation Strategy in CRNs 51In Case 3, we have W ht,i,j ≤ Wmint,i , problem (3.15) has multiple solutions in the set{Wt,i,j | Wmint,i ≤ Wt,i,j ≤ Wmaxt,i }. The objective function is the same with that in Case2. According to Proposition 1, the optimal solution to problem (3.18) is Wmint,i .The optimal solution to problem (3.18) changes with the relation between the W ht,i,jand transmission power range. When the range of the transmission power of SU i isfixed, the value of W ht,i,j determines the number of solutions to (3.15), and thus affectsthe solution to problem (3.18). According to the definition of W ht,i,j, the value of Wht,i,jdepends on the traffic demand of SU i. When SU i has very few data bits to transmit(i.e., Di is very small), W ht,i,j is relatively small. In this case,DiT−τ is equal to Ri,j, andRi,j is monotonically increasing with Wt,i,j . Thus, W ht,i,j is smaller than Wmint,i , whichcorresponds to Case 3. Therefore, SU i saves energy by setting its transmission poweras Wmint,i . On the contrary, when Di is very large, Wht,i,j is greater than Wmaxt,i . In orderto obtain the highest throughput, SU i performs transmission with a transmission powerof Wmaxt,i . In this way, the transmission power is adaptively controlled according to thetraffic demand of SU. Also, the energy spent on data transmission is minimized underthe constraint that SU achieves the highest throughput.3.4 Performance EvaluationIn this section, we compare the performance of the OCF algorithm, SCF algorithm, anddisjoint coalition formation (DCF) algorithm from the perspective of aggregate through-put. In DCF algorithm, each SU can only join at most one coalition instead of multipleChapter 3. Overlapping Coalitional Game Approach for Cooperation Strategy in CRNs 52coalitions, and SUs form a disjoint coalition structure by implementing this algorithm.DCF algorithm is similar to the algorithm proposed in [15].Unless stated otherwise, we consider a CRN with N SUs and M PUs (i.e., M licensedchannels). SUs are randomly placed in a 100 m × 100 m square region. The base stationis placed at the center of the square region. Each channel has a bandwidth of 100 kHzand the probability that a channel is idle is randomly chosen between [0.5, 1]. The CRNworks in a time slotted manner. The slot duration T is 100 ms and the sensing durationis 5 ms. We model the channel gain of the link of SU i as |gi|2 = 1/dni , where di is thedistance between SU i and the base station, and n is the path loss exponent. We setn to 2. We set the target detection probability at each channel as 0.99. The receivedPU’s SNR at each SU γi,j is set to −15 dB. The noise power σ2n is set to 0.01 mW. Thethreshold of transmission power of each SUWmint,i is 50 mW and the upper bound Wmaxt,i is150 mW. The sensing power at each SU Ws,i,j is 50 mW. The number of sensing samplesduring the sensing stage in a time slot Ns is 5000, which is similar to the parameterssetting in [31]. The number of packets generated by each SU during a time slot followsPoisson distribution with an average rate of λ = 0.5 packet per time slot, and each packetis 20 kb. The buffer size of each SU is set to 200 kb. The energy efficiency threshold ηminis 500 kb/J.Fig. 3.1 shows a snapshot of a stable overlapping coalition structure obtained byimplementing OCF algorithm. There are seven SUs and three PUs (i.e., three licensedchannels) in the network. The base station (BS) is located in the center of the square area.Chapter 3. Overlapping Coalitional Game Approach for Cooperation Strategy in CRNs 530 20 40 60 80 100020406080100x (m)y (m)SU3 SU5SU1SU4SU7SU2SU6Coalition 1Coalition 4Coalition 2Coalition 3BSFigure 3.1: An example of a stable overlapping coalition structure (M = 3, N = 7) byOCF algorithm.Seven SUs are randomly distributed in the area. All the SUs in the same ellipse form acoalition to sense and access a channel. Results in Fig. 3.1 show that SUs 1, 4 and 7 belongto coalition 1, which corresponds to channel 1. SUs 3, 4, 5 and 7 form a coalition to senseand access channel 2. SU 2 forms a singleton coalition to use channel 3. SU 6 joins thecoalition 4, which is the coalition of quit sensing. Thus, the overlapping coalition structureΠ = {{1, 4, 7}1, {3, 4, 5, 7}2, {2}3, {6}4}. In this stable coalition structure, coalitions 1 and2 are overlapped with each other. SUs 4 and 7 contribute to both coalitions at the sametime. While SU 6 chooses not to cooperate with other SUs due to the fact that it has notraffic demand during the current time slot. Therefore, SU 6 is in quit sensing coalition.Fig. 3.2 shows the aggregate throughput of SUs when the number of SUs N increasesChapter 3. Overlapping Coalitional Game Approach for Cooperation Strategy in CRNs 542 4 6 8 10 12 14 16 18 200200400600800100012001400Number of SUs NAggregate throughput (kbit/s) SCF algorithmOCF algorithmDCF algorithmFigure 3.2: Aggregate throughput versus the number of SUs (N) in CRN for M = 6.from 2 to 20. As it shows in this figure, both OCF and SCF algorithms outperform DCFalgorithm in terms of aggregate throughput. This is because in OCF and SCF algorithms,SUs can join multiple coalitions, which increase their chances to access channels andimprove their throughput. However, in DCF algorithm, an SU can only join one coalitionand share one channel with other SUs, its chance of obtaining the use of channel is limited.This result shows that overlapping coalitional game strategy improves spectrum efficiency.Fig. 3.3 shows the aggregate throughput of SUs when the number of PUs M (i.e, thenumber of channels) increases from 1 to 10. Results show that OCF and SCF algorithmshave similar performance. When M is small, the performance gap between these two al-gorithms and DCF algorithm is small. This is because in OCF and SCF algorithms, SUscan sense very few channels to improve their chance of transmitting data when channelChapter 3. Overlapping Coalitional Game Approach for Cooperation Strategy in CRNs 551 2 3 4 5 6 7 8 9 102003004005006007008009001000Number of PUs MAggregate throughput (kbit/s) SCF algorithmOCF algorithmDCF algorithmFigure 3.3: Aggregate throughput versus the number of PUs (M) in CRN for N = 10.resources are limited. The gap of performance becomes larger when M increases. Whenmore channels become available, SUs in OCF and SCF algorithms obtain higher through-put by joining multiple coalitions. However, SUs in DCF obtain limited improvement ofthroughput due to the constraint that it can choose to sense and access only one channel.Fig. 3.4 shows the aggregate throughput when increasing the average generated packetrate λ. Both OCF and SCF algorithms outperform DCF algorithm in terms of throughputwhen λ changes from 0.1 to 1. The throughput increases with traffic demand when λis small for all algorithms. Larger value of λ means more data information generatedat each SU during each time slot, which encourages SUs to join in coalition and obtainhigher throughput. When λ ≥ 0.7, the throughput does not increase significantly withtraffic demand. This is due to the fact that the increase of throughput is constrained byChapter 3. Overlapping Coalitional Game Approach for Cooperation Strategy in CRNs 560.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1020040060080010001200Average number of packets generated during a time slot λAggregate throughput (kbit/s) SCF algorithmOCF algorithmDCF algorithmFigure 3.4: Aggregate throughput versus the average generated packets rate λ.spectrum resources.In Fig. 3.5, it shows the aggregate throughput for various energy efficiency thresholdηmin. When ηmin is smaller than 1500 kbit/J, the energy efficiency threshold has littleeffect on the number of coalitions that an SU can join. Therefore, SUs are able to joinenough coalitions to satisfy their traffic demand. In this case, the increase of ηmin has littleeffect on SUs’ throughput. However, when ηmin ≥ 1500 kbit/J, the number of coalitionsthat an SU is allowed to join is limited. SUs are refrained from transmitting data in theirbuffer until the expected energy efficiency becomes greater than the threshold. This leadsto the decrease of throughput. Moreover, OCF and SCF algorithms still outperform DCFalgorithm in this scenario.Fig. 3.6 shows the number of iterations when running OCF and SCF algorithms asChapter 3. Overlapping Coalitional Game Approach for Cooperation Strategy in CRNs 570 500 1000 1500 2000 2500 3000 3500100150200250300350400Energy efficiency threshold ηmin (kbit/Joule)Aggregate throughput (kbit/s) OCF algorithmSCF algorithmDCF algorithmFigure 3.5: Aggregate throughput versus the energy efficiency threshold ηmin.the number of SUs in network increases. When N is small, the number of iterations forthese two algorithms are similar. This is because when there are only a few SUs, thecooperation possibilities are limited. The number of iterations that OCF algorithm needsto converge is not very large. However, when N > 10, the performance gap between thesetwo algorithms becomes larger. In SCF algorithm, an SU checks each new coalition onlyonce when it is active. However, in OCF algorithm, all SUs try to form new coalitionswhenever there is a change in coalition structure until the process converges. The numberof possible coalition structures increases exponentially withN . Therefore, OCF algorithmrequires more iterations to reach a stable coalition structure than SCF algorithm whenN is large.Chapter 3. Overlapping Coalitional Game Approach for Cooperation Strategy in CRNs 582 6 10 14 18 22 26 30020406080100120Number of SUs (N)Number of Iterations OCF algorithmSCF algorithmFigure 3.6: Number of iterations versus the number of SUs N .3.5 SummaryIn this chapter, we studied a traffic-demand based cooperation strategy in CRNs withmultiple channels. We proposed a joint cooperative spectrum sensing and access schemeto enable energy-constrained SUs to obtain a high throughput while maintaining a highenergy efficiency. An overlapping coalitional game was formulated to solve this problem,in which each SU makes its own decision to form overlapping coalitions with other SUs tosense and access multiple channels cooperatively. To reach a stable coalition structure, weproposed an OCF algorithm based on three move rules, which captures both individualpayoff and social welfare. We proved that our proposed OCF algorithm converges toa stable coalition structure. We also proposed a modified SCF algorithm, which has alower computational complexity and requires less information exchanges. Moreover, anChapter 3. Overlapping Coalitional Game Approach for Cooperation Strategy in CRNs 59adaptive transmission power control scheme is proposed. Simulation results show thatthe OCF algorithm and modified SCF algorithms have similar performance in terms ofthroughput. Both of these two algorithms outperform the DCF algorithm.60Chapter 4Conclusions and Future WorkIn this chapter, we conclude the thesis by summarizing the research work and contri-butions that we have made. We discuss the limitation of our current work and suggestpossible extensions for future research.4.1 ConclusionsIn the thesis, we developed a traffic demand-based joint cooperative spectrum sensingand access strategy in CRNs. In our proposed strategy, each SU can choose to performcooperative sensing when it has high traffic demand, or simply quit sensing when it hasno data to transmit. In this way, the energy can be conserved for future transmission.We first considered the case that each SU senses at most one channel during sensingstage. Then, we extended the problem by taking into account multiple-channel sensingability of each SU. We applied coalitional game theory to analyze two different situationsrespectively, and proposed several coalitional formation algorithms. Specifically, ourcontributions are as follows:• In Chapter 2, we considered a cooperation strategy in CRNs from the perspec-Chapter 4. Conclusions and Future Work 61tive of individual SU, which can only sense one channel at a time. We formulatedthe problem as a disjoint coalitional game. Each SU serves as a player to im-plement a cooperation strategy that can maximize its own utility, which capturesexpected throughput and traffic demand. We proposed a sequential coalition for-mation (SCF) algorithm to obtain a final coalition structure. For performance eval-uation, we compared our proposed SCF algorithm with switch rule-based coalitionformation (SRCF) algorithm in terms of throughput and algorithm running time.Simulation results show that our proposed algorithm achieves a higher throughputthan SRCF algorithm and requires less running time.• In Chapter 3, we extended the problem by allowing each SU to sense multiplechannels during the sensing stage. It provides SUs more opportunities to utilizespectrum resources. We applied overlapping coalitional game theory to solve ourproblem in the new system model. During the process of coalition formation,each SU not only considers its own individual payoff, but also takes into accountsocial welfare, which is defined as the value of coalition structure. We proposedan overlapping coalition formation (OCF) algorithm to reach a stable coalitionstructure. It is proved that the OCF algorithm converges after a finite numberof iterations. Moreover, a modified SCF algorithm is proposed to reach a finalcoalition structure. The modified SCF algorithm has similar performance with OCFalgorithm, but with lower number of iterations and less information exchange amongSUs. We also proposed an adaptive transmission power control scheme for each SUChapter 4. Conclusions and Future Work 62to minimize the energy consumption spent on transmission while guaranteeing themaximum throughput. For performance evaluation, we analyzed several differentfactors that may affect the performance of the algorithms, such as the number ofSUs and PUs, the traffic demand of SUs and energy efficiency lower bound. We alsopresented the snapshot of overlapping coalition structure and studied the numberof iterations when implementing different algorithms. Simulation results show thatour proposed algorithms outperform disjoint coalition formation (DCF) algorithmin terms of aggregate throughput of SUs.4.2 Future WorkOur current work can be extended in the following directions:• In our system model, we fixed the sensing duration and sensing power during thesensing stage, which can affect the sensing performance and expected throughput ofSUs. Therefore, it would be interesting to explore the relation between the sensingparameters and throughput when we study the CSSA strategy in CRNs. In thiscase, the system model setting would be more general, as each SU will be able toadjust its sensing duration and sensing power to fit its individual traffic demand.However, considering the uncertainty of the sensing parameters will increase thecomputational complexity of the problem. Also, if each SU uses adaptive sensingcontrol when making cooperation decisions, it requires more information exchangeamong SUs, which may increase the overhead. Therefore, developing a cooperationChapter 4. Conclusions and Future Work 63strategy that involves sensing uncertainty, but has relatively low computationalcomplexity is a possible extension to our current work.• In our proposed algorithms, each SU makes the decision of spectrum sensing andaccess jointly. This limits the possible cooperation among SUs and may constrainthe improvement of throughput. Therefore, letting each SU make separate cooper-ation decisions during sensing stage and data transmission stage is another possibleextension to our current work. We can divide the problem into two parts: cooper-ative sensing problem and spectrum allocation problem, which can be formulatedas two different coalitional games, respectively. That is, SUs first perform coop-erative sensing according to a coalition structure that can optimize the sensingperformance. Then, SUs access the channels based on another coalition structurethat makes the most use of spectrum resources. Therefore, it would be interestingto explore the relation between these two games, and study a cooperative strategythat can optimize the decisions of an SU in both games.64Bibliography[1] W. Saad, Z. Han, R. Zheng, A. Hjorungnes, T. Basar, and H. V. Poor, “Coalitionalgames in partition form for joint spectrum sensing and access in cognitive radionetworks,” IEEE Journal of Selected Topics in Signal Processing, vol. 6, no. 2, pp.195–209, Apr. 2012.[2] “Spectrum policy task force,” Federal Communications Commission, Tech. Rep.,2002.[3] E. Hossain and V. Bhargava, Cognitive Wireless Communication Networks. NewYork, NY, USA: Springer, 2007.[4] J. Oh and W. Choi, “A hybrid cognitive radio system: A combination of underlayand overlay approaches,” in Proc. of IEEE Vehicular Technology Conference (VTC),Ottawa, ON, Sept. 2010.[5] B. Wang and K. Liu, “Advances in cognitive radio networks: A survey,” IEEEJournal of Selected Topics in Signal Processing, vol. 5, no. 1, pp. 5–23, Feb 2011.[6] S. Park and D. Hong, “Optimal spectrum access for energy harvesting cognitiveradio networks,” IEEE Trans. on Wireless Communications, vol. 12, no. 12, pp.6166–6179, Dec. 2013.Bibliography 65[7] T. Zhang and D. H. K. Tsang, “Cooperative sensing scheduling for energy-awarecognitive radio networks,” in Proc. of IEEE International Conference on Commu-nications (ICC), Kyoto, Japan, Jun. 2011.[8] L. Zheng and C. W. Tan, “Maximizing sum rates in cognitive radio networks: Convexrelaxation and global optimization algorithms,” IEEE Journal on Selected Areas inCommunications, vol. 32, no. 3, pp. 667–680, Mar. 2014.[9] X. Zhai, L. Zheng, and C. W. Tan, “Energy-infeasibility tradeoff in cognitive ra-dio networks: Price-driven spectrum access algorithms,” IEEE Journal on SelectedAreas in Communications, vol. 32, no. 3, pp. 528–538, March 2014.[10] S. Bayhan and F. Alagoz, “Scheduling in centralized cognitive radio networks forenergy efficiency,” IEEE Trans. on Vehicular Technology, vol. 62, no. 2, pp. 582–595,Feb. 2013.[11] X. Sun and D. Tsang, “Energy-efficient cooperative sensing scheduling for multi-band cognitive radio networks,” IEEE Trans. on Wireless Communications, vol. 12,no. 10, pp. 4943–4955, Oct. 2013.[12] Y. Gao, W. Xu, K. Yang, K. Niu, and J. Lin, “Energy-efficient transmission withcooperative spectrum sensing in cognitive radio networks,” in Proc. of IEEE WirelessCommunications and Networking Conference (WCNC), Shanghai, China, Apr. 2013.Bibliography 66[13] H. Li, X. Cheng, K. Li, X. Xing, and T. Jing, “Utility-based cooperative spectrumsensing scheduling in cognitive radio networks,” in Proc. of IEEE INFOCOM, Turin,Italy, Apr. 2013.[14] C. Jiang, Y. Chen, Y.-H. Yang, C.-Y. Wang, and K. Liu, “Dynamic Chinese restau-rant game in cognitive radio networks,” in Proc. of IEEE INFOCOM, Turin, Italy,Apr. 2013.[15] X. Hao, M. H. Cheung, V. W. S. Wong, and V. Leung, “Hedonic coalition formationgame for cooperative spectrum sensing and channel access in cognitive radio net-works,” IEEE Trans. on Wireless Communications, vol. 11, no. 11, pp. 3968–3979,Nov. 2012.[16] D. Li, Y. Xu, X. Wang, and M. Guizani, “Coalitional game theoretic approach forsecondary spectrum access in cooperative cognitive radio networks,” IEEE Trans.on Wireless Communications, vol. 10, no. 3, pp. 844–856, March 2011.[17] D. Gozupek, B. Eraslan, and F. Alagoz, “Throughput satisfaction-based schedulingfor cognitive radio networks,” IEEE Trans. on Vehicular Technology, vol. 61, no. 9,pp. 4079–4094, Jul. 2012.[18] M.H. Cheung, V.W.S. Wong, and R. Schober, “SINR-based random access for cog-nitive radio: Distributed algorithm and coalitional game,” IEEE Trans. on WirelessCommunications, vol. 10, no. 11, pp. 3877–3897, Nov. 2011.Bibliography 67[19] T. Jing, X. Xing, W. Cheng, Y. Huo, and T. Znati, “Cooperative spectrum predic-tion in multi-PU multi-SU cognitive radio networks,” in Proc. of IEEE InternationalConference on Cognitive Radio Oriented Wireless Networks (CROWNCOM), Wash-ington, D.C., July 2013.[20] B. Wang, K. Liu, and T. Clancy, “Evolutionary cooperative spectrum sensing game:How to collaborate?” IEEE Trans. on Communications, vol. 58, no. 3, pp. 890–900,Mar. 2010.[21] T. Wang, L. Song, Z. Han, and W. Saad, “Overlapping coalitional games for collab-orative sensing in cognitive radio networks,” in Proc. of IEEE Wireless Communi-cation and Networking Conference (WCNC), Shanghai, China, April 2013.[22] Y.-C. Liang, Y. Zeng, E. Peh, and A. T. Hoang, “Sensing-throughput tradeoff forcognitive radio networks,” IEEE Trans. on Wireless Communications, vol. 7, no. 4,pp. 1326–1337, Apr. 2008.[23] K. R. Apt and A. Witzel, “A generic approach to coalition formation,” in Proc. ofInternational Workshop on Computational Social Choice, Amsterdam, Netherlands,Dec. 2006.[24] A. Bogomonlaia and M. Jackson, “The stability of hedonic coalition structures,”Games and Economic Behaviour, vol. 38, no. 2, pp. 201–230, Jan. 2002.Bibliography 68[25] F. Bloch, “Sequential formation of coalitions in games with externalities and fixedpayoff division,” Games and Economic Behavior, vol. 14, no. 1, pp. 90–123, May1996.[26] E. Peh and Y.-C. Liang, “Optimization for cooperative sensing in cognitive radionetworks,” in Proc. of IEEE Wireless Communications and Networking Conference(WCNC), Hong Kong, China, Mar. 2007.[27] G. Miao, N. Himayat, Y. G. Li, and A. Swami, “Cross-layer optimization for energy-efficient wireless communications: A survey,” Wireless Communication and MobileComputing, vol. 9, no. 4, pp. 529–542, Apr. 2009.[28] G. Chalkiadakis, E. Elkind, E. Markakis, M. Polukarov, and N. R. Jennings, “Co-operative games with overlapping coalitions,” Journal of Artificial Intelligence Re-search, vol. 39, no. 1, pp. 179–216, Sept. 2010.[29] Y. Shoham and K. Leyton-Brown, Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations. New York, NY, USA: Cambridge UniversityPress, 2008.[30] Z. Zhang, L. Song, Z. Han, W. Saad, and Z. Lu, “Overlapping coalition formationgames for cooperative interference management in small cell networks,” in Proc. ofIEEE Wireless Communications and Networking Conference (WCNC), Shanghai,China, Apr. 2013.Bibliography 69[31] Z. Khan, J. Lehtomaki, M. Latva-aho, and L. DaSilva, “On selfish and altruisticcoalition formation in cognitive radio networks,” in Proc. of IEEE International Con-ference on Cognitive Radio Oriented Wireless Networks Communications (CROWN-COM), Cannes, France, Jun. 2010.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Coalitional game approach for cooperation strategy...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Coalitional game approach for cooperation strategy in cognitive radio networks Dai, Zhiyu 2014
pdf
Page Metadata
Item Metadata
Title | Coalitional game approach for cooperation strategy in cognitive radio networks |
Creator |
Dai, Zhiyu |
Publisher | University of British Columbia |
Date Issued | 2014 |
Description | Cognitive radio networks (CRNs) provide an effective solution to address the increasing demand for spectrum resources. The cooperation among secondary users (SUs) improves the sensing performance and spectrum efficiency. In this thesis, we study a traffic-demand based cooperative spectrum sensing and access strategy in a CRN with multiple SUs and multiple primary users (PUs). In the proposed strategy, each SU makes its own cooperation decision according to its traffic demand. When the SU has a high traffic demand, it selectively chooses channels to sense and access. When it has no data to transmit, it can choose not to perform sensing and save energy for future transmission. In the first part of the thesis, we study the traffic demand-based cooperation strategy in CRNs, in which each SU senses at most one channel during a time slot. We formulate this problem as a non-transferable utility (NTU) coalition formation game, in which each SU receives a coalition value that takes into account the expected throughput and energy efficiency. In order to obtain the final coalition structure, we propose a sequential coalition formation (SCF) algorithm. Simulation results show that our proposed algorithm achieves a higher throughput and energy efficiency than a previously proposed coalition formation algorithm in [1]. In the second part of this thesis, we extend the cooperation strategy problem in CRNs by enabling each SU to sense multiple channels during the sensing stage. We formulate the problem as an NTU overlapping coalitional game. We propose an overlapping coalition formation (OCF) algorithm to obtain a stable coalition structure. The proposed OCF algorithm is proved to converge after a finite number of iterations. We also modify the SCF algorithm proposed in the first part of this thesis to address the problem in the new system model. The modified SCF algorithm requires a lower number of iterations and involves less information exchange among SUs. Moreover, an adaptive transmission power control scheme is proposed for SUs to further improve their energy efficiency. Simulation results show that our proposed algorithms achieve a higher throughput than the disjoint coalition formation (DCF) algorithm. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2014-08-07 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivs 2.5 Canada |
DOI | 10.14288/1.0165908 |
URI | http://hdl.handle.net/2429/49947 |
Degree |
Master of Applied Science - MASc |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Electrical and Computer Engineering, Department of |
Degree Grantor | University of British Columbia |
Graduation Date | 2014-09 |
Campus |
UBCV |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/2.5/ca/ |
Aggregated Source Repository | DSpace |
Download
- Media
- 24-ubc_2014_fall_dai_zhiyu.pdf [ 323.76kB ]
- Metadata
- JSON: 24-1.0165908.json
- JSON-LD: 24-1.0165908-ld.json
- RDF/XML (Pretty): 24-1.0165908-rdf.xml
- RDF/JSON: 24-1.0165908-rdf.json
- Turtle: 24-1.0165908-turtle.txt
- N-Triples: 24-1.0165908-rdf-ntriples.txt
- Original Record: 24-1.0165908-source.json
- Full Text
- 24-1.0165908-fulltext.txt
- Citation
- 24-1.0165908.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.24.1-0165908/manifest