Game Theoretic Approach for Cooperative Sensing and Transmission in Cognitive Radio Networks by Xiaolei Hao B.E., Beijing University of Posts and Telecommunications, 2009 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF APPLIED SCIENCE in THE FACULTY OF GRADUATE STUDIES (Electrical and Computer Engineering) THE UNIVERSITY OF BRITISH COLUMBIA (Vancouver) August 2011 c© Xiaolei Hao, 2011ii Abstract The concept of cognitive radio aims to increase the efficiency of spectrum usage. Besides, cooperation techniques, such as cooperative sensing and cooperative transmission, have been widely used to further enhance the performance of cognitive radio networks (CRNs). In the first part of the thesis, we analyze both cooperative sensing and channel accessing in a CRN with multiple primary users (PUs) and multiple secondary users (SUs). We first propose a cooperative spectrum sensing and accessing (CSSA) scheme for all the SUs. We then formulate the multi-channel spectrum sensing and channel accessing problem as a hedonic coalition formation game. The value function of each coalition takes into account both the sensing accuracy and energy consumption. In order to implement our CSSA scheme, we propose an algorithm for decision node selection. Also, we propose an algorithm based on the switch rule for the SUs to make distributed decisions on whether to join or leave a coalition. We prove analytically that all the SUs will converge to a final network partition, which is both Nash-stable and individually stable. Besides, the proposed distributed algorithms can adapt the Nash-stable partition to environmental changes. Simulation results show that our CSSA scheme achieves a better performance than the noncooperative spectrum sensing and accessing (NSSA) scheme in terms of theAbstract iii average utility of SUs. In the second part of the thesis, we analyze the cooperative transmission in CRNs, where SU can be selected as the cooperative relay to assist PU’s transmission. In order to improve the performance, the PU needs to select the secondary relay and allocate time resources for cooperative transmission. Then, the SUs need to determine their strategies of random access. We first establish a model for cooperative cognitive radio networks. We then propose a cooperative transmission and random access (CTRA) scheme. Based on the sequential structure of the decision-making, we study the cooperative cognitive radio network and determine the equilibrium strategies for both the PU and SUs using the Stackelberg game. Simulation results show that both the PU and SUs achieve better performance compared with the noncooperative transmission and random access (NTRA) scheme.iv Preface A version of Chapter 2 has been accepted for publication. Xiaolei Hao, Man Hon Che- ung, Vincent W.S. Wong, and Victor C.M. Leung, “A coalition formation game for energy-efficient cooperative spectrum sensing in cognitive radio networks with multiple channels,” in Proc. of IEEE Global Communications Conference (Globecom), Houston, Texas, December 2011. I was responsible for designing the system model and the CSSA scheme. Besides, I conducted the game theory analysis and the simulation. Mr. Cheung suggested using hedonic coalition formation game. The paper was originally prepared by me, and further revised by all the co-authors. Chapter 3 is based on another work accepted for publication. Xiaolei Hao, Man Hon Cheung, Vincent W.S. Wong, and Victor C.M. Leung, “A Stackelberg game for coop- erative transmission and random access in cognitive radio networks,” in Proc. of IEEE Personal Indoor Mobile Radio Communications (PIMRC), Toronto, Canada, September 2011. I was responsible for designing the system model and the CTRA scheme. Besides, I conducted the game theory analysis and the simulation. Dr. Wong suggested using ran- dom access in the system model. The paper was originally prepared by me, and further revised by all the co-authors.v Table of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii List of Acronyms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiii 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Cognitive Radio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Cooperative Spectrum Sensing in CRNs . . . . . . . . . . . . . . . . . . 3 1.3 Cooperative Transmission in CRNs . . . . . . . . . . . . . . . . . . . . . 5 1.4 List of Publications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.5 Structure of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2 Hedonic Coalition Formation Game for CSSA Scheme in CRNs . . . 9Table of Contents vi 2.1 Motivations and Contributions . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2 System Model and CSSA Scheme . . . . . . . . . . . . . . . . . . . . . . 14 2.3 Hedonic Coalition Formation Game . . . . . . . . . . . . . . . . . . . . . 21 2.3.1 Value Function and Utility Function . . . . . . . . . . . . . . . . 22 2.3.2 Hedonic Coalition Formation Analysis . . . . . . . . . . . . . . . 26 2.4 Distributed Algorithms and Implementation Details . . . . . . . . . . . . 33 2.5 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 2.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 3 Stackelberg Game for CTRA Scheme in CRNs . . . . . . . . . . . . . . 48 3.1 Motivations and Contributions . . . . . . . . . . . . . . . . . . . . . . . . 48 3.2 System Model and CTRA Scheme . . . . . . . . . . . . . . . . . . . . . . 51 3.3 Stackelberg Game Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 57 3.3.1 Stackelberg Game with Perfect Information . . . . . . . . . . . . 57 3.3.2 Strategies for Secondary Users . . . . . . . . . . . . . . . . . . . . 58 3.3.3 Strategies for Primary User . . . . . . . . . . . . . . . . . . . . . 61 3.4 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 3.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 4 Conclusions and Future Work . . . . . . . . . . . . . . . . . . . . . . . . . 69 4.1 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 4.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71Table of Contents vii Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74viii List of Figures 2.1 Sensing subframe with duration δ of the proposed CSSA scheme with M = 2 and N = 4. Each ST chooses one licensed channel to sense during the sensing subframe. ST1 and ST2 sense the licensed channel of PU1, and ST3 and ST4 sense the licensed channel of PU2. . . . . . . . . . . . . . . 15 2.2 Sensing decision of the proposed CSSA scheme with M = 2 and N = 4. When the sensing time δ expires, each ST sends its sensing result to one of the STs in that channel that acts as a DN. . . . . . . . . . . . . . . . 18 2.3 Data transmission subframe with duration T − δ of the proposed CSSA scheme with M = 2 and N = 4. If the channel is determined to be idle by the DN, one of the STs in that channel can transmit data to the corresponding secondary receiver in the data transmission subframe. . . . 20 2.4 An example of the Nash-stable partition (M = 2, N = 4). . . . . . . . . . 40 2.5 The average utility of the SUs versus iteration index r (M = 5, N = 10). 41 2.6 The average utility of the SUs versus the number of PUs M (N = 10). . 42 2.7 The average utility of the SUs versus the number of SUs N (M = 5). . . 43List of Figures ix 2.8 The average utility of the SUs versus the probability for PUs being active PH1 (M = 5, N = 10). . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 2.9 The average utility of the SUs versus the unit penalty per second D0 (M = 5, N = 10). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 2.10 The average utility of the SUs versus the sensing duration δ (M = 5, N = 10, T = 100 ms). . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.1 Primary transmission in sub-slot 1 of the proposed CTRA scheme. The primary transmitter P T chooses secondary transmitter ST1 as its coop- erative relay and transmits the primary data to both the secondary relay ST1 and the destination PR. . . . . . . . . . . . . . . . . . . . . . . . . . 52 3.2 Primary transmission in sub-slot 2 of the proposed CTRA scheme. The chosen secondary relay ST1 forwards the primary data to P R. . . . . . . 53 3.3 Secondary transmission in sub-slot 3 of the proposed CTRA scheme. The SUs attempt to access the licensed frequency band of PT in a random access manner. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 3.4 Simulation model with one PU and five SUs. . . . . . . . . . . . . . . . . 64 3.5 The utility of the PU versus the number of SUs N (ωP = 1, ωS = 0.1, cnon = 18). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 3.6 The utility of the PU versus the maximum accessing price cnon (ωP = 1, ωS = 0.1, N = 5). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66List of Figures x 3.7 The average utility of the SUs versus the maximum accessing price cnon (ωP = 1, ωS = 0.8, N = 5). . . . . . . . . . . . . . . . . . . . . . . . . . . 67xi List of Acronyms A/D Analog-to-Digital AP Access Point CRNs Cognitive Radio Networks CSCG Circularly Symmetric Complex Gaussian CSSA Cooperative Spectrum Sensing and Accessing CTRA Cooperative Transmission and Random Access DN Decision Node IID Independent and Identically Distributed NSSA Noncooperative Spectrum Sensing and Accessing NTRA Noncooperative Transmission and Random Access PR Primary Receiver PSK Phase Shift KeyingList of Acronyms xii PT Primary Transmitter PUs Primary Users SNR Signal-to-Noise Ratio SR Secondary Receiver ST Secondary Transmitter SUs Secondary Users TDMA Time Division Multiple Access TU Transferable Utilityxiii Acknowledgements I owe my deepest gratitude to my reserach supervisors, Dr. Vincent Wong and Dr. Vic- tor Leung, whose encouragement, guidance and support from the initial to the final level made my graduate study productive and stimulating. I appreciate the time we spent together at UBC. Without their help, this thesis would not have been possible. Special thanks to my senior, Man Hon Cheung, for his expertise in game theory and his precious assistance in my research. My sincere thanks also goes to the other colleagues in the data communications group for having their company and sharing their knowledge. I offer my regards and blessings to all of those who supported me in any respect during the completion of my master program. Finally, I would like to take this opportunity to thank my parents for all their love and encouragement. To them, I dedicate this thesis. This research is supported by the Natural Sciences and Engineering Research Council (NSERC) of Canada and British Columbia Innovation Council (BCIC) Natural Resource and Applied Sciences (NRAS) grant.1 Chapter 1 Introduction This chapter first presents the background of cognitive radio. The concepts of cooperative spectrum sensing and cooperative transmission in cognitive radio networks (CRNs) are also introduced in this chapter. The list of publications and the structure of the thesis are given at the end of this chapter. 1.1 Cognitive Radio Spectrum resources are scarce and the demand for the radio spectrum has been increas- ing in recent years. According to the report released by the Federal Communications Commission [1], fixed spectrum allocation may not always be efficient and the licensed spectrum may remain unoccupied for a long period of time. This motivates the concept of cognitive radio [2], which allows the secondary users (SUs) to dynamically access the licensed spectrum allocated to the primary users (PUs) when the licensed spectrum is not being utilized temporarily. Therefore, the efficiency of spectrum usage can be increased. The CRNs are composed of different PUs and SUs. The licensed spectrum is assigned to PUs, and the SUs seek to exploit possible transmission opportunities in the licensedChapter 1. Introduction 2 frequency bands of the PUs. In general, the CRNs can be divided into three categories, which are underlay, overlay and interweave. In the underlay category [3], the primary data transmission made by PUs and the secondary data transmission made by SUs may occur simultaneously. The SUs can transmit secondary data only if the interference generated by the SUs at the primary receivers is below certain acceptable threshold. As for the overlay category [4], the SUs are also allowed to transmit simultaneously with the PUs. However, the interference to the PUs can be offset by using part of the secondary transmitters’ power to relay the PUs’ data packets. In the interweave category [5], the concurrent primary and secondary transmissions are not allowed, and the SUs will periodically monitor the licensed spectrum and opportunistically communicate over spectrum holes where the PUs are not active. In order to access the licensed frequency bands of the PUs, the SUs have to detect spectrum white space, select the best licensed frequency bands, coordinate licensed spec- trum access with other SUs and vacate the licensed channels when the PUs appear [6]. Therefore, both spectrum sensing [7] and dynamic spectrum sharing [8] have to be con- sidered in CRNs. As the PUs have priority in accessing the licensed spectrum, the SUs have to perform real-time monitoring of the licensed spectrum when the SUs coexist with the PUs. If the SUs are allowed to transmit secondary data simultaneously with the PUs, interference temperature limit [9] should not be violated. Otherwise, if the SUs are only allowed to transmit secondary data when the PUs are not active, the SUs need to be aware of the PUs’ appearance through various detection techniques, such as energyChapter 1. Introduction 3 detection [10], feature detection [11], and coherent detection [12]. Through spectrum sensing, the SUs can detect the spectrum white space (i.e., a portion of licensed spec- trum which is not being occupied by the PUs), and utilize that licensed channel. On the other hand, when the PUs start using the licensed spectrum again, the SUs can detect their activity through spectrum sensing, so that no harmful interference is generated due to the secondary data transmission. Besides the spectrum sensing, efficient dynamic spectrum allocation and sharing schemes are also important to achieve high spectrum efficiency in CRNs. Since the licensed spectrum is assigned to the PUs, novel spectrum access protocols should be designed to accommodate the dynamic spectrum environment while avoid collision between the PUs and the SUs. Moreover, when multiple SUs share a licensed frequency band, their competition for the licensed spectrum resources should be addressed, and their access should be coordinated in order to alleviate collisions and interference as well. 1.2 Cooperative Spectrum Sensing in CRNs In order to realize spectrum reuse and increase the spectrum efficiency, the SUs have to obtain information about the existence of the PUs and the spectrum usage. This information can be obtained either by using geographical locations and database, beacons, or spectrum sensing at cognitive radios [13]. As for spectrum sensing [14], the SUs are required to sense the radio environment within their operating range to find the licensed spectrum which is not occupied by the PUs in order to enable dynamic spectrum access inChapter 1. Introduction 4 CRNs. However, the spectrum sensing performance in practice is often compromised with multipath fading, shadowing and receiver uncertainty issues [13]. In order to mitigate the impact of these issues, cooperative spectrum sensing [15, 16] has been shown to be an effective method to improve the detection performance. The main idea of cooperative spectrum sensing is to enhance the sensing performance by exploiting the spatial diversity in the observations of spatially located SUs. By performing cooperative spectrum sensing, the SUs can share their sensing information for making a combined decision more accurate than the individual decisions used in local spectrum sensing. As for cooperative spectrum sensing, both the sensing accuracy and energy efficiency are crucial. The combined decision made by the SUs which perform cooperative spec- trum sensing should correctly declare that a PU is present when the spectrum is indeed occupied by the PU (i.e., detection), and also avoid making a mistake by declaring that a PU is present when the spectrum is actually free (i.e., false alarm), so that the SUs will not cause the interference with the PUs by the miss detection and not waste the transmission opportunities by the false alarm. Besides, in cooperative spectrum sensing, each SU consumes energy by local sensing and data reporting. Thus, the energy efficien- cy should also be considered in practical implementation, which means each SU would prefer to improve the sensing performance and transmit more secondary data packets while consume less energy. Usually there are multiple licensed channels and multiple SUs in a CRN, therefore, it is important for each SU to make distributed decision on which licensed channel to sense andChapter 1. Introduction 5 access in order to achieve the optimal performance. While the current literature mainly focused on the sensing accuracy and ignored the energy consumption and data throughput of SUs, we analyze the performance of the system by considering cooperative sensing accuracy, energy consumption and channel accessing in our research work. We present a complete framework to study cooperative spectrum sensing and channel accessing in a CRN with multiple PUs and multiple SUs. Besides, we provide the implementation details for our framework by proposing distributed algorithms, so that each SU can make the individual decision on which channel to sense and access in a distributed manner. 1.3 Cooperative Transmission in CRNs Cooperative transmission [17] is a widely considered technique for enhancing wireless network capacity. A coalition of wireless users exploits spatial diversity by exchanging and cooperatively transmitting data packets. There are two types of cooperative transmission in CRNs, which are the cooperative transmission among the SUs [18] and the cooperative transmission between the PUs and the SUs [19]. For the first type, the SUs can perform as cooperative relays and forward the secondary data packets for other SUs. As for the second type, both the PUs and the SUs are involved in the cooperative transmission, where the SUs can be chosen as cooperative relays by the PUs and assist the PUs to forward their primary data packets. In the thesis, we only focus on the second type. Most of the existing works in CRNs assumed that the PUs are unaware of the presence of SUs, and the SUs are allowed to access the licensed channel only if the interferenceChapter 1. Introduction 6 generated by the SUs at the primary receivers is below certain acceptable threshold (i.e., the underlay category). However, it is also possible that the PUs can discover the existence of the SUs which seek to access the licensed spectrum, and therefore leverage those SUs for the primary data transmission (i.e., the overlay category). In CRNs, due to the channel fading, direct transmission from the primary transmitter to the primary receiver is sometimes severely damaged and thus suffers bad performance in terms of data rate and outage probability. Therefore, in overlay category, there is a natural necessary to exploit cooperative diversity in the cognitive radio systems, because the spatial and user diversity provided by the SUs can dramatically enhance the performance of the PUs. By choosing SUs as cooperative relays, the PUs’ data transmission rate will be increased. Thus, time occupied by the primary transmission is decreased for serving certain amount of primary traffic. As a result, the SUs obtain more opportunities to access the licensed channel and transmit more data of the secondary system. Through the cooperative transmission, both the PUs and the SUs can increase their own interest and a win-win situation can be achieved. In order to achieve this win-win situation, it is interesting and also important to analyze the inter-operation between the PUs and the SUs, such as cooperative relay selection and spectrum resource allocation. Besides the spectrum sensing, efficient dynamic spectrum allocation and sharing schemes are also important to achieve high spectrum efficiency in CRNs. In the first part of the thesis, we focus on cooperative spectrum sensing in CRNs. However, in the second part of the thesis, we shift our focus to cooperative transmission in CRNs. EvenChapter 1. Introduction 7 though both parts of our work use cooperative techniques to enhance the performance of CRNs, they focus on two different main functions of cognitive radio: spectrum sens- ing and spectrum sharing. Current literature about cooperative transmission scheme in CRNs mainly focused on the cooperative transmission among SUs. The cooperative transmission between the PUs and the SUs has not been fully addressed, and all related research assumed the SUs access the licensed spectrum in a time division multiple access (TDMA) mode. In general, when the licensed spectrum is idle, all SUs should have the opportunities to access the spectrum. Therefore, we consider both cooperative transmis- sion and random access in the second part of the thesis, and derive the optimal strategies for both the PU and the SUs in the CRN. 1.4 List of Publications The following publications have been completed based on the work in this thesis. • Xiaolei Hao, Man Hon Cheung, Vincent W.S. Wong, and Victor C.M. Leung, “A Stackelberg game for cooperative transmission and random access in cognitive ra- dio networks,” in Proc. of IEEE Personal Indoor Mobile Radio Communications (PIMRC), Toronto, Canada, September 2011. • Xiaolei Hao, Man Hon Cheung, Vincent W.S. Wong, and Victor C.M. Leung, “A coalition formation game for energy-efficient cooperative spectrum sensing in cog- nitive radio networks with multiple channels,” in Proc. of IEEE Global Communi-Chapter 1. Introduction 8 cations Conference (Globecom), Houston, Texas, December 2011. 1.5 Structure of the Thesis The rest of the thesis is organized as follows. In Chapter 2, we present our hedonic coalition formation game analysis of our proposed cooperative spectrum sensing and accessing (CSSA) scheme. The motivations and contributions are stated at first, followed by the system model and our proposed CSSA scheme. The game theory analysis and the distributed algorithms for coalition formation are described, and the performance evaluation results are provided. In Chapter 3, we present our Stackelberg game analysis of our proposed cooperative transmission and random access (CTRA) scheme in CRNs. We first give the motivations and contributions. We then describe the system model and the CTRA scheme in details. The Stackelberg game model and equilibrium analysis comes after and we present the performance evaluation results in the end. Conclusions and future work are given in Chapter 4.9 Chapter 2 Hedonic Coalition Formation Game for CSSA Scheme in CRNs In this chapter, we present the hedonic coalition formation game of our proposed coop- erative spectrum sensing and accessing (CSSA) scheme. We state the motivations and contributions at first, followed by the system model and our proposed CSSA scheme. The game theory analysis and the distributed algorithms for coalition formation are de- scribed, and the performance evaluation results are provided. A summary is given at the end of this chapter. 2.1 Motivations and Contributions Compared with local spectrum sensing [20], which is susceptible to sensing problems due to noise uncertainty, fading, shadowing, and hidden PUs [13], it has been shown that the sensing performance can be improved significantly if cooperative spectrum sensing is used [21, 22]. In [23], Liang et al. formulated the sensing-throughput tradeoff problem as an optimization problem and proved that there exists an optimal sensing time which yieldsChapter 2. Hedonic Coalition Formation Game for CSSA Scheme in CRNs 10 the highest throughput for the secondary network under the constraint of the probability of detection. Cooperative sensing was studied based on their proposed tradeoff method- ology. In [24], Saad et al. introduced a distributed model for performing cooperative spectrum sensing in CRNs. In their proposed model, a network of SUs can interact and form cooperating coalitions for improving their spectrum sensing performance. The co- operative sensing problem was modeled as a coalitional game, and distributed algorithms were proposed for coalition formation. In [25], Lee et al. proposed an adaptive and co- operative spectrum sensing method, and investigated how the cooperative sensing affects the performance of the proposed optimal spectrum sensing framework. In [26], Wang et al. proposed a distributed scheme for cooperative multi-channel spectrum sensing based on coalitional game theory. Besides, a coalition selection scheme was designed to ensure each licensed channel is sensed by one coalition. In [27], Song et al. studied the theoret- ical improvement made by multi-channel coordination in cooperative spectrum sensing, and proposed practical centralized algorithm and distributed algorithms to find solutions of the formulated integer programming problem. Except for the sensing performance, channel utilization and energy consumption are also studied in spectrum sensing. In [28], Zhao et al. proposed a periodic sensing opportunistic spectrum access scheme. Besides, the constrained Markov decision processes were used to maximize channel utilization while limiting the interference to the PUs. In [29], Su et al. proposed a spectrum sensing scheme for CRNs to save the sensing energy consumption, and guarantee the priority of the PUs and the spectrum opportunity for SUs in terms of available spectrum usageChapter 2. Hedonic Coalition Formation Game for CSSA Scheme in CRNs 11 time. In general, there are multiple PUs (i.e., multiple licensed channels) and multiple SUs in CRNs. Given a CRN with multiple PUs and multiple SUs, it is important to determine which licensed channel should each SU choose to sense and access in order to achieve the optimal performance. In the design of spectrum sensing schemes, both sensing accuracy [30, 31] and energy consumption [32] are important design criteria. Moreover, the model will be more complete if we also consider the channel accessing after the spectrum sensing. Therefore, we consider a framework in CRNs that considers spectrum sensing accuracy, energy consumption and channel accessing for the SUs, and allow each SU to make its own decision on which licensed channel to sense and access. In order to allow the SUs to make distributed decisions, it is also essential to propose distributed algorithms for the SUs. Furthermore, the proposed distributed algorithms should guarantee that the optimal decisions of the SUs can self-adapt to environmental changes such as the deployment of new PUs and SUs, the removal of existing PUs and SUs, and the change in wireless channel conditions. To the best of our knowledge, no existing work has considered this kind of framework in CRNs. In this chapter, we study cooperative multi-channel spectrum sensing and channel accessing in CRNs. We consider the setting with multiple licensed frequency channels and multiple SUs. We assume that each SU first chooses one licensed channel to sense in the sensing subframe. Then, all the SUs that choose to sense the same channel cooperatively determine if the channel is busy or idle. If it is determined to be idle, one of the SUs whichChapter 2. Hedonic Coalition Formation Game for CSSA Scheme in CRNs 12 has sensed that channel can access it during the data transmission subframe. We consider both the spectrum sensing accuracy and energy consumption in our model, and analyze the behavior of the SUs by using hedonic coalition formation game [33, 34]. To the best of our knowledge, this work is the first one that applies hedonic coalition formation game to study cooperative multi-channel spectrum sensing and channel accessing in CRNs. The main contributions of this chapter are summarized as follows: • We study cooperative spectrum sensing and channel accessing for the SUs in a CRN, where there are multiple licensed frequency channels. We propose a cooperative spectrum sensing and accessing (CSSA) scheme for the SUs. • We formulate the cooperative multi-channel spectrum sensing and accessing prob- lem as a hedonic coalition formation game, where the value function of each coalition and the utility function of each SU take into account both the sensing accuracy and energy consumption. • In order for the SUs to make distributed decisions to join or leave a coalition, we propose distributed algorithms for the CSSA scheme. We prove analytically that they terminate at a Nash-stable partition where no SU has an incentive to move from its current coalition to another coalition. • Simulation results show that the SUs can make distributed decisions in order to increase their own utilities according to our proposed distributed algorithms and reach a Nash-stable partition. Besides, the proposed distributed algorithms canChapter 2. Hedonic Coalition Formation Game for CSSA Scheme in CRNs 13 adapt the Nash-stable partition to environmental changes. The results also show that our proposed CSSA scheme achieves a better performance than the nonco- operative spectrum sensing and accessing (NSSA) scheme in terms of the average utility of the SUs. The framework that we present in this chapter is unique compared to others’ work in spectrum sensing. In terms of the system model, we consider the general case where there are multiple primary licensed channels and multiple SUs in the CRN, while the works in [23, 24, 29] only analyzed the simple situation where there is one licensed channel in the network. Besides, the energy efficiency is always a concern for practical implementation. Therefore, we take energy consumption into consideration for spectrum sensing and channel accessing in the CRNs, and consider energy consumption as an important metric for evaluating the performance of the system. However, the works in [23, 24, 25, 26, 27, 28] did not consider energy consumption in their analysis. In terms of spectrum sensing accuracy, we apply cooperative spectrum sensing in our proposed CSSA scheme. Compared to the work in [28, 29] which only considered local spectrum sensing, our CSSA scheme can further improve the sensing performance. Moreover, while others’ work only focused on spectrum sensing and ignored channel accessing (e.g., [24, 26]), we consider both spectrum sensing and channel accessing in our proposed CSSA scheme, and analyze the performance of the system by using hedonic coalition formation game, which has never been applied to study the cooperative multi-channel spectrum sensing and channel accessing in CRNs. Therefore, we can present a complete framework for theChapter 2. Hedonic Coalition Formation Game for CSSA Scheme in CRNs 14 CRN, and provide the implementation details (i.e., propose distributed algorithms) for our CSSA scheme. The remainder of this chapter is organized as follows. Section 2.2 describes the system model and the CSSA scheme. The proposed cooperative multi-channel spectrum sensing and channel accessing problem is modeled as a hedonic coalition formation game in Section 2.3. In Section 2.4, we present the distributed algorithms for coalition formation. Section 2.5 presents the simulation results. Finally, a summary of this chapter is given in Section 2.6. 2.2 System Model and CSSA Scheme As shown in Fig. 2.1, we consider a CRN with one access point (AP), M PUs, and N secondary transmitter-receiver (ST-SR) pairs. In this chapter, since the secondary transmitter (ST) is responsible for spectrum sensing and data transmission, we use the term ST and SU interchangeably. Let M = {1, . . . , M} denote the set of PUs and N = {1, . . . , N} denote the set of STs. Each P Ui, ∀ i ∈ M has its own licensed channel with bandwidth Bi. Thus, there are M non-overlapped licensed frequency bands in total. The M PUs are sending primary data to the AP. The N ST-SR pairs are located in the same area as the PUs, where STj, ∀ j ∈ N seeks to exploit possible transmission opportunities in the M licensed frequency bands of the PUs. We assume that each STj always has data to send and no traffic requirement is imposed on the STs. In other words, STj transmits data in a best-effort manner.Chapter 2. Hedonic Coalition Formation Game for CSSA Scheme in CRNs 15 Figure 2.1: Sensing subframe with duration δ of the proposed CSSA scheme with M = 2 and N = 4. Each ST chooses one licensed channel to sense during the sensing subframe. ST1 and ST2 sense the licensed channel of P U1, and ST3 and ST4 sense the licensed channel of PU2. We consider a frame structure for periodic spectrum sensing, where each time frame consists of one sensing subframe1 and one data transmission subframe2 as shown in the bottom part in Fig. 2.1. We use T to denote the frame duration. We assume that all SUs have the same spectrum sensing duration, and we use δ (0 < δ ≤ T ) to denote the spectrum sensing time of the SUs. Therefore, the data transmission duration is T − δ. We assume that the received signal of the PUs is sampled at sampling frequency fs at 1The duration of the sensing subframe δ is less than 15 ms when the duration of each frame is T = 100 ms [23, 35]. 2During the data transmission subframe, the SU can transmit multiple packets. When T = 100 ms and δ = 2.5 ms, the data transmitted in the data transmission subframe is almost 600 kbits [23].Chapter 2. Hedonic Coalition Formation Game for CSSA Scheme in CRNs 16 STj, ∀ j ∈ N . In addition, δ is a multiple of 1/fs. Thus, the number of samples is δfs, which is an integer. We also assume that T is a multiple of 1/fs. As one of the most popular sensing techniques in cooperative spectrum sensing, energy detection is mainly for narrow band sensing [13]. However, if we assume one SU can sense multiple channels in one sensing subframe (i.e., wide band sensing), the SU uses identical observation over multiple channels without considering their different characteristics, which will cause the violation of interference limit [25]. Furthermore, it requires a high-speed analog-to- digital (A/D) converter [36]. Therefore, it is more practical for us to assume that each SU chooses one licensed channel to sense in each time frame. Let H1,i and H0,i be the hypothesis that PUi, i ∈ M is active and inactive, respec- tively. For j ∈ N , STj performs spectrum sensing in the licensed frequency band of PUi, ∀ i ∈ M and determines the probabilities of detection and false alarm. The proba- bility of detection is the probability of correctly detecting the appearance of P Ui under hypothesis H1,i (i.e., a busy channel is determined to be busy correctly). The probability of false alarm is the probability of falsely declaring the appearance of the primary signal under hypothesis H0,i (i.e., an idle channel is determined to be busy). We assume the noise in the licensed channel of P Ui, ∀ i ∈ M is an independent and identically distributed (iid) random process with zero mean and variance σ2n,i. Given the power spectral density N0, we have σ2n,i = N0Bi. The primary signal of PUi is an iid random process with zero mean and variance σ2s,i. The primary signal is independent of other primary signals and the noise. We denote γi,j = |gi,j|2σ2s,i/σ2n,i as the receivedChapter 2. Hedonic Coalition Formation Game for CSSA Scheme in CRNs 17 signal-to-noise ratio (SNR) of P Ui, i ∈M measured at STj, j ∈ N under the hypothesis H1,i, where |gi,j| is the average channel gain of the link between P Ui and STj in channel i. We use ε to denote the detection threshold for all the STs. We consider the circularly symmetric complex Gaussian (CSCG) noise case. We also assume that the primary signal is complex phase shift keying (PSK) modulated signal. With the use of energy detection [13, 37], under hypothesis H0,i, the probability of false alarm [23] in channel i ∈ M by STj is Pf,i,j(ε, δ, σ2n,i) = Pr(yj,i > ε |H0,i) = Q ( ( ε σ2n,i − 1 ) √ δfs ) , (2.1) where yj,i is the test statistic for energy detector of STj in channel i, and Q is the complementary distribution function of the standard Gaussian. Since Pf,i,j(ε, δ, σ2n,i) is defined under hypothesis H0,i, this probability is related to the noise signal. Therefore, given the same detection threshold ε and sensing duration δ for all SUs, and the same bandwidth Bi for all PUs, Pf,i,j(ε, δ, σ2n,i) are the same for ∀ i ∈ M, ∀ j ∈ N . Besides, under hypothesis H1,i, the probability of detection in channel i ∈M by STj, j ∈ N is Pd,i,j(ε, δ, σ2n,i, γi,j) = P r(yj,i > ε |H1,i) = Q ( ( ε σ2n,i − γi,j − 1 ) √ δfs 2γi,j + 1 ) . (2.2) It has been reported that the hidden node problem, deep fading and shadowing can degrade the performance of local spectrum sensing of individual SU [13, 38]. To overcome this problem, cooperative spectrum sensing was proposed, where SUs share information and combine results from independent measurements. In our system model, each SU first chooses to sense a licensed frequency band independently, and then sends its spectrum sensing result to a decision node (DN) for that channel when the sensing time δ expires.Chapter 2. Hedonic Coalition Formation Game for CSSA Scheme in CRNs 18 Figure 2.2: Sensing decision of the proposed CSSA scheme with M = 2 and N = 4. When the sensing time δ expires, each ST sends its sensing result to one of the STs in that channel that acts as a DN. Among those STj, j ∈ N which choose to sense channel i ∈M, DNi is selected according to Algorithm 1, which is presented in Section 2.4. The DNi will combine the sensing results of the SUs which choose to sense channel i and determine the status (i.e., busy or idle) of channel i. We consider an example shown in Fig. 2.1, where there are two licensed channels and four ST-SR pairs. At the beginning of each frame, as shown in Fig. 2.1, ST1 and ST2 start sensing the licensed channel of PU1 in channel 1, ST3 and ST4 start sensing the licensed channel of P U2 in channel 2. In Fig. 2.2, ST1 and ST3 serve as the DN1 and DN2, respectively. Each SU will send its spectrum sensing decision to the corresponding DNi when its sensing time δ expires. The DNi will make the final spectrum sensing decision for the licensed channel i ∈M. We assume that DN decides on the channel status based on a decision fusion ruleChapter 2. Hedonic Coalition Formation Game for CSSA Scheme in CRNs 19 to combine the sensing results of the SUs [23]. We assume that k-out-of-n rule [39] is used, where DN decides the presence of primary activity if there are k or more SUs that individually detect the presence of primary activity. In particular, we choose k = 1 so that the k-out-of-n rule is simply the OR rule. That is, if one of the STs reports that there is an active PU, then DN declares that the channel is busy. For other values of k, our scheme still works. We assume that the local decisions made by each ST in the same channel are independent. Let Si be the set of STs that choose to sense and access channel i. We have Si ⊆ N , ∀ i ∈M and ⋃ i∈M Si = N . Since we assume that STj, ∀ j ∈ N can choose to sense only one channel in each frame, we have Si∩Sl = ∅, ∀ i, l ∈M, i = l. The probability of false alarm Pf,i under the hypothesis H0,i, and the probability of detection Pd,i under the hypothesis H1,i in channel i ∈M are given by Pf,i = 1− ∏ j∈Si ( 1− Pf,i,j(ε, δ, σ2n,i) ) , (2.3) Pd,i = 1− ∏ j∈Si ( 1− Pd,i,j(ε, δ, σ2n,i, γi,j) ) . (2.4) For the licensed frequency band i ∈M, we denote PH1,i as the probability that PUi is active, and PH0,i as the probability that PUi is silent. Therefore, we have PH1,i+PH0,i = 1. If DNi declares that P Ui is active, then STj, ∀ j ∈ Si cannot transmit data during the data transmission subframe. However, if DNi declares that channel i is idle, then each STj, j ∈ Si has a chance to access the licensed channel i with equal probability. Therefore, under the decision that channel i is idle, the transmission probability of STj, j ∈ Si is 1/|Si|, and the transmission time is T − δ. As an example shown in Fig. 2.3, ST1 andChapter 2. Hedonic Coalition Formation Game for CSSA Scheme in CRNs 20 Figure 2.3: Data transmission subframe with duration T − δ of the proposed CSSA scheme with M = 2 and N = 4. If the channel is determined to be i- dle by the DN, one of the STs in that channel can transmit data to the corresponding secondary receiver in the data transmission subframe. ST2 seek to access the licensed channel of P U1 (solid arrows), and ST3 and ST4 seek to access the licensed channel of PU2 (dash arrows). Moreover, if DNi declares that channel i is idle and P Ui is actually silent, the secondary data transmission in channel i will be successful. However, if DNi determines that channel i is idle but PUi is actually active, the secondary data transmission in channel i will not be successful because it interferes with the PUi’s transmission, and the SUs will be charged a penalty by P Ui for interfering the primary data transmission. Given the system model and the CSSA scheme described above, it is important to determine which licensed channel should each SU choose to sense and access in order toChapter 2. Hedonic Coalition Formation Game for CSSA Scheme in CRNs 21 achieve the optimal performance. In other words, the objective is to allow the SUs to autonomously form the coalitional structure, as the example shown in Figs. 2.1−2.3, and adapt the coalitional structure to environmental changes. In the following sections, we will propose distributed algorithms to solve this spectrum sensing and accessing problem using coalitional game theory. 2.3 Hedonic Coalition Formation Game From our system model, there are M non-overlapped frequency bands and N SUs in the CRN. In order to exploit the possible transmission opportunities in the M licensed frequency bands with different channel conditions, each SU should carefully make its own decision on which channel to sense and access during each time frame so that it can achieve the best performance. Based on our proposed CSSA scheme, the performance of STj, ∀ j ∈ N does not only depend on the licensed channel ∀ i ∈ M it chooses to sense and access, but depend on the other SUs (STk, k ∈ Si, k = j) in the same licensed band as well. Therefore, in this section, we will formulate the problem of multi-channel cooperative spectrum sensing and accessing as a hedonic coalition formation game, and apply the switch rule for the SUs to make distributed decisions on whether to join or leave a coalition. But first, in order to evaluate the performance of the SUs, we design the value function of the set Si, ∀ i ∈M and the utility function of STj, ∀ j ∈ N .Chapter 2. Hedonic Coalition Formation Game for CSSA Scheme in CRNs 22 2.3.1 Value Function and Utility Function Since the SUs try to exploit the possible transmission opportunities in the licensed fre- quency bands, it is obvious that the performance of each SU should take the amount of transmitted data into consideration. The amount of transmitted data is related to the spectrum sensing accuracy. Besides, the penalty charged by the PUs for interfering the primary data transmission is also related to the spectrum sensing accuracy. Moreover, energy consumption of the SUs for spectrum sensing and data transmitting is always a concern for practical implementation. Therefore, we introduce the value function for the set of users Si and the utility function for each STj ∈ Si, which are both related to the sensing accuracy and energy consumption. According to the CSSA scheme presented in the Section 2.2, there can be four different scenarios related to the activity of the PUi and the decision of DNi. We present the equivalent data utility, energy consumption, and the probability that each scenario occurs as follows: Scenario 1: PUi is silent and the decision made by DNi is not a false alarm. In this scenario, STj, ∀ j ∈ Si transmits data during the data transmission subframe, and the secondary data transmission will be successful. Given the signal transmit power Pt, the noise power σ2n,i in channel i, and the average channel gain |hj,i| of the link between the ST-SR pair j in channel i, the transmission rate Rj,i of STj can be modeled as [40]: Rj,i = Bi log2 ( 1 + |hj,i|2 Pt σ2n,i ) . (2.5) In this scenario, the equivalent data utility of set Si is defined as the expected valueChapter 2. Hedonic Coalition Formation Game for CSSA Scheme in CRNs 23 of the data transmitted by the users in Si, which is given by v0|0,D(Si) = ∑ j∈Si Rj,i |Si| (T − δ). (2.6) The energy consumption of set Si is given by v0|0,E(Si) = Ps|Si|δ + Pt(T − δ), (2.7) where Ps is the sensing power of STj, ∀ j ∈ N . The first term represents the energy consumption of spectrum sensing, and the second term represents the energy consumption of the data transmission. We use P0|0,i to denote the probability of this scenario, which is given by P0|0,i = PH0,i(1− Pf,i). (2.8) Scenario 2: P Ui is silent and the decision made by DNi is a false alarm. In this scenario, STj, ∀ j ∈ Si does not transmit during the data transmission subframe, and the data transmission subframe is wasted. Therefore, the equivalent data utility of set Si is v1|0,D(Si) = 0, (2.9) and the energy consumption of set Si is v1|0,E(Si) = Ps|Si|δ. (2.10) We use P1|0,i to denote the probability of this scenario, which is given by P1|0,i = PH0,iPf,i. (2.11)Chapter 2. Hedonic Coalition Formation Game for CSSA Scheme in CRNs 24 Scenario 3: PUi is active and DNi fails to detect the presence of the primary signal. In this scenario, STj, ∀ j ∈ Si transmits data during the data transmission subframe. However, the secondary data transmission fails because it interferes with the PUi’s trans- mission. We set the equivalent data utility of set Si to be v0|1,D(Si) = −D0(T − δ), (2.12) where D0 > 0 is the unit penalty per second for interfering with the PU’s data trans- mission. Notice that the penalty term D0(T − δ) is decreasing with the duration of the sensing subframe δ. Besides, the energy consumption of set Si is v0|1,E(Si) = Ps|Si|δ + Pt(T − δ), (2.13) which is the same as in (2.7). We use P0|1,i to denote the probability of this scenario, which is given by P0|1,i = PH1,i(1− Pd,i). (2.14) Scenario 4: PUi is active and DNi detects the presence of the primary signal. In this scenario, STj, ∀ j ∈ Si does not transmit data during the data transmission subframe. The equivalent data utility of set Si is v1|1,D(Si) = 0, (2.15) and the energy consumption of set Si is v1|1,E(Si) = Ps|Si|δ. (2.16)Chapter 2. Hedonic Coalition Formation Game for CSSA Scheme in CRNs 25 We use P1|1,i to denote the probability of this scenario, which is given by P1|1,i = PH1,iPd,i. (2.17) According to the above analysis, the expected value of the equivalent data utility for set Si in each frame of duration T is vD(Si) = 1∑ a=0 1∑ b=0 Pa|b,iva|b,D(Si) = P0|0,i ∑ j∈Si Rj,i |Si| (T − δ)− P0|1,iD0(T − δ). (2.18) The expected value of the energy consumption in set Si in each frame of duration T is vE(Si) = 1∑ a=0 1∑ b=0 Pa|b,iva|b,E(Si) = Ps|Si|δ + (P0|0,i + P0|1,i)Pt(T − δ). (2.19) We define the value function of set Si as follows, which takes both the sensing accuracy and energy consumption into account: v(Si) = vD(Si) vE(Si) = P0|0,i ∑ j∈Si Rj,i(T − δ)− |Si|P0|1,iD0(T − δ) |Si|(Ps|Si|δ + (P0|0,i + P0|1,i)Pt(T − δ)) . (2.20) It represents the equivalent data utility per unit of energy consumed in set Si. In other words, it is related to the energy efficiency of the secondary data transmission (i.e., v(Si) increases if the set Si can obtain a higher equivalent data utility while consuming less energy). Moreover, from (2.20), the value function takes the sensing accuracy into account by considering the sensing results related to false alarm (i.e., P0|0,i is related to Pf,i) and primary signal detection (i.e., P0|1,i is related to Pd,i). The value of v(∅) is chosen such that v(Si) > v(∅), ∀Si ⊆ N and Si = ∅. By equally dividing v(Si) among the players, the utility function of STj, ∀ j ∈ Si is given by xSij = v(Si) |Si| . (2.21)Chapter 2. Hedonic Coalition Formation Game for CSSA Scheme in CRNs 26 Given the M non-overlapped frequency bands and N SUs in our system model, each SU will make its own decision on which channel it should sense and access during each time frame so that it can achieve the best performance in terms of the utility defined in (2.21). 2.3.2 Hedonic Coalition Formation Analysis Given the value function of set Si defined in (2.20) and the utility function of each SU defined in (2.21), we formulate the problem of multi-channel cooperative spectrum sensing and channel accessing as a coalition formation game with the following basic elements: • Players: The players of the coalition formation game are the N SUs (i.e., STj, ∀ j ∈ N ). • Strategies: The strategy of each SU is the licensed channel it chooses to sense and access (i.e., STj chooses a licensed channel i ∈M). • Payoffs (or utilities): The payoff of each SU depends on which coalition it belongs to, and it is defined in (2.21) (i.e., the payoff of STj in coalition Si is xSij ). Using the terminology of coalitional game theory, we refer to set Si as coalition i. Since there are M licensed channels in the CRN, there are M coalitions in the system, and each SU joins one of the M coalitions. All STj, j ∈ Si would perform cooperative spectrum sensing and accessing in channel i ∈M in order to seek the possible transmis- sion opportunities. The SUs are allowed to autonomously form the coalitions in the M licensed frequency bands in order to achieve higher utilities. Since v(Si) in (2.20) canChapter 2. Hedonic Coalition Formation Game for CSSA Scheme in CRNs 27 be equally apportioned between the coalition members, it justifies the transferable utility (TU) [33] nature of the coalitional game. Moreover, we will show that the coalition forma- tion game is classified as hedonic [41]. Before presenting its definition, we first introduce some basic definitions which are commonly used in the coalition formation games. Definition 1 The set S = {S1, . . . ,SM} is a partition of N if Si∩Sl = ∅, ∀ i, l ∈M, i = l and ⋃ i∈M Si = N . A partition is also referred to as a coalition structure in [33]. An example of a partition S is shown in Fig. 2.1, where N = {1, 2, 3, 4}, S1 = {1, 2}, and S2 = {3, 4}. Therefore, the set S = {{1, 2}, {3, 4}} is a partition of N . Definition 2 For any player j ∈ N , a preference relation j is defined as a complete, irreflexive and transitive binary relation [42] over the set of all coalitions that player j can possibly form [41]. Since the SUs are allowed to autonomously form the coalitions in the M licensed frequency bands, the above definition is used to compare different coalitions where player j is a member. Consequently, for player j ∈ N , given two coalitions S1 ⊆ N and S2 ⊆ N , S1 j S2 indicates that player j prefers to be a member of coalition S1 over to be a member of coalition S2, or at least, player j prefers both coalitions equally. Furthermore, S1 j S2 indicates that player j strictly prefers being a member of coalition S1 over being a member of coalition S2. For evaluating the preferences of STj, ∀ j ∈ N , we define theChapter 2. Hedonic Coalition Formation Game for CSSA Scheme in CRNs 28 following operation S1 j S2 ⇔ Uj(S1) > Uj(S2), (2.22) where S1 ⊆ N and S2 ⊆ N are any two coalitions that contains STj. The preference function Uj(Si), j ∈ Si is defined as Uj(Si) = −∞, if Si ∈ h(j), xSij , otherwise. (2.23) xSij is the utility received by STj from the equal fair division of the value function of Si (j ∈ Si), which is given in (2.21). h(j) is the history set of STj, and the definition of history set will be presented later. According to the preference function defined in (2.23), the preference over different coalitions for STj, ∀ j ∈ N is related to its utility function defined in (2.21). Given the set of players N and a preference relation j for every player j ∈ N , a hedonic coalition formation game is defined as follows: Definition 3 A hedonic coalition formation game is a coalitional game that satisfies the following two conditions: 1) The utility of any player depends solely on the members of the coalition to which the player belongs; 2) The coalitions form as a result of the preferences of the players over their possible coalition set. Therefore, a hedonic coalition formation game is defined by the pair (N ,) where N is the set of players and is a profile of preferences defined for every player in N .Chapter 2. Hedonic Coalition Formation Game for CSSA Scheme in CRNs 29 According to our problem formulation, the players of the game are the N SUs. From (2.21), the utility function of STj, ∀ j ∈ Si depends only on the the SUs in coalition Si, i ∈ M. Hence, our coalitional game satisfies the first hedonic condition. Besides, given the preference relations from (2.23), the coalitions will be formed according to the preferences of the SUs over their possible coalition set. Therefore, our coalitional game satisfies the second hedonic condition. Since our formulated problem satisfies the above two conditions in Definition 3, the formulated problem can be modeled as a hedonic coalition formation game. Property 1 The problem of multi-channel cooperative spectrum sensing and accessing can be modeled as a (N ,) hedonic coalition formation game, with the preference relation given by (2.22) and (2.23). From the definitions of the preference relations of the SUs in (2.22) and the preference function in (2.23), it is clear that STj, ∀ j ∈ N would like to join a new coalition, which STj has never been a member of, if and only if STj can obtain a higher utility in this new coalition than ever before. Therefore, we present the switch rule for coalition formation. Definition 4 Given a partition S = {S1, . . . ,SM}, STj, j ∈ Si decides to leave its current coalition Si and join another coalition Sl where i = l, if and only if Sl ⋃ {j} j Si. The switch rule provides a mechanism through which a SU can leave its current coalition and join another coalition, given that the new coalition is strictly preferred overChapter 2. Hedonic Coalition Formation Game for CSSA Scheme in CRNs 30 the current coalition. Therefore, the switch rule can be viewed as a selfish decision made by a player to move from its current coalition to a new coalition, regardless of the effect of its move on the other players. According to the switch rule, all the N SUs can make distributed decisions to automatically form coalitions in the system. The partition of the (N ,) hedonic coalition formation game may change after each time frame. We define the initial partition of the hedonic coalition formation game as S(0) = {S(0)1 , . . . ,S(0)M }, and the partition at the rth time frame as S(r) = {S(r)1 , . . . ,S(r)M }. After each time frame of duration T , the partition may change according to our proposed switch rule. If S(r) = S(r−1), then there is no switch operation during the rth time frame. Otherwise, there must exists one SU which moves from its current coalition to another coalition in the rth time frame. Now, we present the definition of history set h(j) of STj, which appeared in (2.23). Definition 5 At the rth time frame, the history set h(j) for STj, ∀ j ∈ N is {S(0)i0 , . . . ,S(r−1)ir−1 }. For any time frame index z ∈ {0, 1, . . . , r− 1}, we have iz ∈M and j ∈ S(z)iz . At the end of the rth time frame, STj will update its history set h(j) by putting a new element S(r)ir (ir ∈M and j ∈ S(r)ir ) at the end of h(j). Proposition 1 If STj performs the switch rule in the rth time frame (i.e., leaves its previous coalition Si (denoted as S(r−1)ir−1 ) and joins another coalition Sl where i = l), the newly formed coalition Sl ⋃ {j} (denoted as S(r)ir ) cannot be the same with the previous coalition members in the history set h(j).Chapter 2. Hedonic Coalition Formation Game for CSSA Scheme in CRNs 31 Proof : Suppose S(r)ir is the same with S(z)iz , where z ∈ {0, 1, . . . , r−1} and S(z)iz ∈ h(j). Then, we can have xS (r) ir j = x S(z)iz j according to (2.21). However, according to the definition of the switch rule, STj will perform the switch rule if and only if the new coalition is strictly preferred by STj over the previous coalition. Therefore, we have x S(r)ir j > x S(z)iz j , which contradicts with our assumption. Thus, the newly formed coalition S(r)ir cannot be the same with any of the previous coalitions S(z)iz in the history set h(j). Next, we will prove that there exists a stable partition in our hedonic coalition for- mation game. Before presenting the proof, we first define two types of stable partitions. Definition 6 A partition S = {S1, . . . ,SM} is Nash-stable if ∀ j ∈ Si and ∀ i ∈ M, Si j Sl ⋃ {j}, ∀ l ∈M. In other words, a coalition partition S is Nash-stable if no player has an incentive to move from its current coalition to another coalition. Therefore, no player can obtain a higher utility by performing the switch rule when the current partition is Nash-stable. Definition 7 A partition S = {S1, . . . ,SM} is individually stable if there does not exist j ∈ N , and a coalition Sl (l = i) such that Sl ⋃ {j} j Si, where j ∈ Si, and Sl ⋃ {j} k Sl for all k ∈ Sl. Theorem 1 Starting from any initial partition S(0), all the SUs will always converge to a final partition S∗ = {S∗1 , . . . ,S∗M}, which is both Nash-stable and individually stable. Proof : Given any initial partition S(0) of our hedonic game, the hedonic coalition formation consists of a sequence of switch operations. Therefore, there is a sequenceChapter 2. Hedonic Coalition Formation Game for CSSA Scheme in CRNs 32 of network partitions {S(0),S(1),S(2), . . . ,S(r)} after r frames. According to Definition 4, each switch operation transforms the current partition into another partition, where one SU achieves a higher utility in its new coalition. From Proposition 1, we know that each switch operation leads to a partition which has not been visited before. Given the number of licensed channels M and the number of SUs N in the CRN, the total number of different partitions is MN , which is a finite number [43]. Thus, from any S(0), given enough time, the switch operations will always terminate at a point after a finite number of iterations, where the system converges to a final partition S∗. Suppose S∗ is not Nash-stable. According to Definition 6, there exist some switch operations which can increase the utility of one SU by moving this SU from its current coalition to another coalition. The partition will update and S∗ is not the final partition, which contradicts with our assumption. Thus, the final partition S∗ must be Nash-stable. According to [34], a Nash-stable partition is individually stable. By now, we have applied the switch rule which allows the SUs to autonomously organize into a final partition, which is both Nash-stable and individually stable. In the next section, we will present the distributed algorithms for our hedonic coalition formation game.Chapter 2. Hedonic Coalition Formation Game for CSSA Scheme in CRNs 33 2.4 Distributed Algorithms and Implementation Details In this section, we describe the implementation of the CSSA scheme and the hedonic coalition formation game in a distributed setting. Distributed algorithms are proposed for the selection of DN and the implementation of the switch operation. In order for the N SUs to play the hedonic coalition formation game distributively, two stages are involved. In stage one, the AP will first find out how many PUs are there in the CRN, and also gather the information of the center frequency and bandwidth Bi of P Ui, ∀ i ∈ M. Then, all the SUs will communicate with the AP in order to obtain the information of the PUs. The AP will set the initial partition S(0) and convey this initial partition to all the SUs. The initial partition is set as S(0)1 = N and S(0)l = ∅, ∀ l ∈M\{1}. In stage two, all the SUs will perform the switch operations until the CRN converge to a final Nash-stable partition S∗. The stage two is composed of a total number of MAX iterations. Since the number of licensed channels M and the number of SUs N are both finite, if the number of iterations MAX is large, the CRN can always converge to a final Nash-stable partition S∗ according to Theorem 1. At each time frame, only one SU could leave its current coalition and move to another coalition in order to obtain a higher utility. In this stage, Algorithm 1 is used for the selection of DNi, ∀ i ∈M, and Algorithm 2 is used for the switch operations. They will be presented later. After the coalition structure converges to the final Nash-stable partition S∗, the SUs will stay inChapter 2. Hedonic Coalition Formation Game for CSSA Scheme in CRNs 34 Algorithm 1 Distributed algorithm to select decision node DNi, for channel i ∈ M. The algorithm is executed by STj, ∀ j ∈ Si. 1: for iteration r := 1 to MAX do 2: STj broadcasts its SNR information γ(r)i,j to other secondary transmitters STk, ∀ k ∈ S(r)i \{j} 3: STj receives the SNR information γ(r)i,k from other STk, ∀ k ∈ S (r) i \{j} 4: q := argmaxp γ (r) i,p , ∀ p ∈ S (r) i 5: DN (r)i := STq 6: end for their current coalitions in S∗ to sense and access the licensed channels according to our proposed CSSA scheme. We first present a distributed algorithm for the DN selection in each coalition in Algorithm 1. We propose to choose the SU with the highest detection probability, which is defined in (2.2), in coalition Si as DNi. The reason is that the sensing results can be corrupted due to transmission error when they are sent by STj, j ∈ Si to DNi. If the SU with the highest detection probability is chosen as the DN, the most reliable sensing result from that SU is not required to be sent in the wireless channel for reporting, and it can thus be used in the decision fusion without experiencing any corruption. Since DNi decides the status of licensed channel i based on the OR rule, if P Ui is active, the primary data transmission can be protected by guaranteeing the most reliable sensing result is not corrupted. In the rth iteration, Algorithm 1 is executed by STj, ∀ j ∈ Si in order to select DN (r)i for channel i ∈ M. Since STj determines which licensed channel to sense and access in each frame, therefore STj knows the value of i. In order to select DN (r)i in the rth iteration, all SUs in the coalition S(r)i have to exchange their SNR information. STjChapter 2. Hedonic Coalition Formation Game for CSSA Scheme in CRNs 35 will broadcast its SNR information γ(r)i,j over a control channel to other SUs in the same licensed channel i (line 2). Besides, STj will also receive the SNR information from other SUs in the same licensed channel (line 3). Then, STj will compare its own SNR with the SNR information of other SUs, and the SU with the highest SNR is chosen as DN (r)i (lines 4-5). Proposition 2 The DNi selected by Algorithm 1 has the highest detection probability in Si. Proof : According to Algorithm 1, the SU with the highest SNR (line 5) is chosen as DNi in coalition Si. Therefore, we just need to prove that Pd,i,j(ε, δ, σ2n,i, γi,j) is an increasing function of γi,j. We define g(ε, δ, σ2n,i, γi,j) = ( ε σ2n,i − γi,j − 1 ) √ δfs 2γi,j + 1 , (2.24) and take the first order derivative of Pd,i,j(ε, δ, σ2n,i, γi,j) with respect to γi,j, which is given by ∂Pd,i,j(ε, δ, σ2n,i, γi,j) ∂γi,j = − ∂Q(g(ε, δ, σ2n,i, γi,j)) ∂g(ε, δ, σ2n,i, γi,j) √ δfs(γi,j + εσ2n,i ) (2γi,j + 1)1.5 . (2.25) Since Q(g(ε, δ, σ2n,i, γi,j)) is an decreasing function of g(ε, δ, σ2n,i, γi,j), we have ∂Q(g(ε, δ, σ2n,i, γi,j)) ∂g(ε, δ, σ2n,i, γi,j) < 0. (2.26) Besides, γi,j, ε and σ2n,i are all positive. Therefore, the first order derivative in (2.25) is always positive, and Pd,i,j(ε, δ, σ2n,i, γi,j) is an increasing function of γi,j.Chapter 2. Hedonic Coalition Formation Game for CSSA Scheme in CRNs 36 Algorithm 2 Distributed algorithm for the switch operation. It is executed by STj, ∀ j ∈ N . 1: Initialization: S(0)1 := N ; S(0)l := ∅, ∀ l ∈M\{1} 2: for iteration r := 1 to MAX do 3: S(r)i := S (r−1) i , where i ∈M and j ∈ S(r)i 4: STj generates θj, which is a Gaussian random variable with mean 0 and variance 1 5: STj randomly selects another licensed channel αj such that αj ∈M, αj = i 6: STj broadcasts the information of θj to other STk, ∀ k ∈ N , k = j 7: STj receives the information of θk from other STk, ∀ k ∈ N , k = j 8: m := argmaxw θw, ∀w ∈ N 9: if STj = STm then 10: STj computes xS (r) i j := v(S(r)i )/|S(r)i | 11: S(r)i := S (r) i \{j} 12: STj requests and obtains the information of S(r)αj from DN (r)αj 13: S(r)αj := S(r)αj ⋃{j} 14: if S(r)αj ∈ h(j) then 15: S(r)αj := S(r)αj \{j} 16: S(r)i := S (r) i ⋃{j} 17: else 18: STj computes x S(r)αj j := v(S(r)αj )/|S(r)αj | 19: if x S(r)αj j ≤ x S(r)i j then 20: S(r)αj := S(r)αj \{j} 21: S(r)i := S (r) i ⋃{j} 22: end if 23: end if 24: end if 25: STj adds S(r)i to the end of its history set h(j) 26: end for Next, we discuss Algorithm 2 for the implementation of the switch rule. In the rth iteration, Algorithm 2 is executed by STj, ∀ j ∈ N so that the switch operation is executed and the current partition S(r) is updated for the (N ,) hedonic coalition formation game according to the switch rule. At the rth iteration, all the STj, ∀ j ∈ N communicate with each other in order to select one SU to perform switch operation in this iteration. This selection process isChapter 2. Hedonic Coalition Formation Game for CSSA Scheme in CRNs 37 described in lines 4-8. First, STj generates a random number θj (line 4), and broadcasts its own random number θj to other SUs in the CRN (line 6). Besides, STj also receives the random numbers θk, ∀ k ∈ N , k = j from other SUs (line 7). Then, STj will compare the values of random numbers generated by the N SUs and pick the largest random number θm (line 8). If the random variable θj generated by STj is the largest (i.e., j = m), STj will try to perform the switch operation in this iteration by leaving its current coalition S(r)i and joining another coalition S(r)αj , where αj = i is randomly selected by STj (line 5). If STj has the chance to perform switch operation in the current iteration, STj will not only try to move from its current coalition S(r)i to another coalition S (r) αj , but have to check whether the new coalition is strictly preferred over the current coalition as well. First, STj computes its utility function xS (r) i j as being a member of its current coalition S(r)i (line 10), and leaves its current coalition S(r)i (line 11). Then, STj sends DN (r)αj a request in order to obtain the coalition information of S(r)αj (line 12), and adds itself as a new member of coalition S(r)αj (line 13). After updating the current partition, STj will check whether the new coalition S(r)αj is strictly preferred over the previous coalition S(r)i . This check consists of two steps. First, STj will check whether the new coalition S(r)αj has already appeared in its history set h(j) (line 14). If S(r)αj is identical to any member of h(j), which means STj has already been in the same coalition before, the preference function of STj is minus infinity according to (2.23), and the switch operation of STj in this iteration is not valid according to the definition of the switch rule. Therefore,Chapter 2. Hedonic Coalition Formation Game for CSSA Scheme in CRNs 38 STj should leave the coalition S(r)αj (line 15) and move back to coalition S(r)i (line 16). Second, if the new coalition S(r)αj is not in the history set h(j), STj will computes its utility function x S(r)αj j as being a member of the new coalition S (r) αj (line 18). If the utility x S(r)αj j is greater than x S(r)i j , which means the new coalition S (r) αj is strictly preferred over the previous coalition S(r)i , the switch operation of STj in this iteration is successful. Otherwise, STj still have to leave the coalition S(r)αj (line 20) and move back to coalition S(r)i (line 21). Furthermore, at the end of the rth iteration, STj has to update its history set h(j) (line 25). Our proposed algorithms can adapt the Nash-stable partition S∗ to environmental changes. In the presence of environmental changes, such as the deployment of new PUs and SUs, the removal of existing PUs and SUs, or any changes of the wireless channel states, both stages one and two will be performed again in order to find the new Nash- stable partition. In practice, these two stages will be performed periodically for the CRN, where environmental changes may occur. 2.5 Performance Evaluation In this section, we first present the results for the convergence of our proposed distribut- ed algorithms. We then evaluate the performance gain of our proposed CSSA scheme over the noncooperative spectrum sensing and accessing (NSSA) scheme, where the SUs perform local spectrum sensing instead of cooperative spectrum sensing, under different system parameters. In the simulation, we consider that there are one AP, five PUsChapter 2. Hedonic Coalition Formation Game for CSSA Scheme in CRNs 39 (M = 5) and ten ST-SR pairs (N = 10). The positions of each node are randomly placed in a 100 m×100 m square region. The bandwidth of the primary licensed channel Bi is 10 MHz, ∀ i ∈ M. For all i ∈ M and j ∈ N , we model the average channel gain of the link between PUi and STj as |gi,j|2 = 1/dγi,j, where di,j is the distance between P Ui and STj, and γ is the path loss exponent. Also, we model the average channel gain of the link between STj and SRj as |hj,i|2 = 1/dγj,i, where dj,i is the distance between STj and SRj. We adopt γ to be equal to 2. Other parameters used in our simulation are set as follows: the length of each time frame T is 100 ms; the sampling frequency fs is 1 kHz; the transmit power of each ST Pt is 10 mW; the sensing power of each ST Ps is 10 mW; the detection threshold ε is 0.2 mW; the noise power spectral density N0 is 1×10−8 mW/Hz, therefore, the noise power σ2n,i is 0.1 mW for all i ∈ M. The probability that PUi, i ∈M is active is PH1,i = PH1 = 0.8, ∀ i ∈M. We choose the sensing duration δ to be 5 ms and the unit penalty per second D0 to be 100. Each point is averaged over 100 independent simulation runs. Fig. 2.4 shows an example of the Nash-stable partition. The AP is deployed at the central point of the square region, and two PUs and four ST-SR pairs are randomly placed in the same region. The nodes in the same rectangle means that those users are in the same coalition. From Fig. 2.4, we can see that ST1 and ST2 form a coalition and perform our proposed CSSA scheme in the licensed channel of P U1, ST3 and ST4 form another coalition in the licensed channel of P U2. Therefore, the Nash-stable partition is {{1, 2}, {3, 4}}. In this Nash-stable partition, ST1 and ST2 is relatively closer to P U1Chapter 2. Hedonic Coalition Formation Game for CSSA Scheme in CRNs 40 0 20 40 60 80 100 0 10 20 30 40 50 60 70 80 90 100 P U1 P U2 AP ST1 SR1 x y ST2 SR2 ST3 SR3 ST4 SR4 S1 S2 Figure 2.4: An example of the Nash-stable partition (M = 2, N = 4). compared with P U2. Their probabilities of detecting the activity of PU1 is higher than those of PU2, therefore, they choose to sense and access the licensed channel of P U1 in the Nash-stable partition. Fig. 2.5 shows the average utility of the SUs in each iteration using our proposed algorithms for the CRN. We can see that the average utility of the SUs achieved under the CSSA scheme is higher than that under the NSSA scheme. Our proposed algorithms result in the self-organization of the SUs that achieves a higher average utility of SUs after each iteration, and eventually reaches a Nash-stable partition. Besides, there is a new PU deployed in the CRN when r = 2000 and there are another four SUs deployed in the CRN when r = 4000, therefore, the SUs will start from the initial partition and converge to a Nash-stable partition again. We can see that Algorithm 2 converges to aChapter 2. Hedonic Coalition Formation Game for CSSA Scheme in CRNs 41 1000 2000 3000 4000 5000 6000 0 1 2 3 4 5 6 7 8 r Average utility of SU s CSSA NSSA Figure 2.5: The average utility of the SUs versus iteration index r (M = 5, N = 10). stable partition again after those environmental changes. Moreover, we can see that the average utility of the SUs is increased when a new PU joins the CRN, and the average utility of the SUs is decreased when four SUs join the CRN. In Fig. 2.6, we show the average utility of the SUs obtained by the proposed algorithms versus the number of PUs M in the CRN when N is equal to 10. Our results show that the performance of CSSA is better than NSSA. For both schemes, the average utility of the SUs first increases with M , because the SUs can achieve higher utilities by utilizing the licensed spectrum when the spectrum resources are increased. When M < 10 and N > M , the performance of CSSA is better than that of NSSA due to the cooperative gain [13] of cooperative spectrum sensing. When M ≥ 10, each SU will choose to sense and access a different licensed channel. Since there is only one SU in one licensed channel, theChapter 2. Hedonic Coalition Formation Game for CSSA Scheme in CRNs 42 2 4 6 8 10 12 14 16 18 20 0 2 4 6 8 10 12 M Average utility of SU s CSSA NSSA Figure 2.6: The average utility of the SUs versus the number of PUs M (N = 10). average utilities of the SUs for both the CSSA scheme and the NSSA scheme are the same. Beside, when M ≥ 10, the average utility of the SUs can still keep increasing because each SU may have a better choice of licensed channels when there are more available channels in the CRN. Even though each SU chooses to sense and access a different channel when M ≥ 10, increasing M will increase the probability that each SU can occupy a better channel, therefore, the average utility of the SUs can still keep increasing. When M is large, increasing M further will not improve the spectrum utilization too much, because the number of SUs is limited and the additional licensed spectrum cannot be utilized by the SUs. In Fig. 2.7, we show the average utility of the SUs obtained by the proposed algorithms versus the number of SUs N in the CRN when M is equal to 5. Our results show that theChapter 2. Hedonic Coalition Formation Game for CSSA Scheme in CRNs 43 5 10 20 30 40 50 60 70 80 90 0 1 2 3 4 5 6 7 8 9 10 N Average utility of SU s CSSA NSSA Figure 2.7: The average utility of the SUs versus the number of SUs N (M = 5). performance of CSSA is better than NSSA. When N = M = 5, both the CSSA scheme and the NSSA scheme results in the same channel selection that there is only one SU in each licensed channel. Thus, the average utilities of the SUs under both schemes are the same. When N > 5 and N > M , the average utilities of the SUs for CSSA is higher than that for NSSA due to the cooperative gain of cooperative spectrum sensing. For both schemes, the average utility of the SUs decreases with N . Since the number of licensed channels M is fixed, increasing N will increase the size of each coalition, therefore, the utility of each SU will be decreased. Besides, we can see that the performance gap between CSSA and NSSA first increases with N and then decreases with N . When N is relatively small, the size of each coalition is not large and the performance of the SUs can be improved significantly by applying cooperative spectrum sensing. However, whenChapter 2. Hedonic Coalition Formation Game for CSSA Scheme in CRNs 44 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 2 3 4 5 6 7 8 9 10 PH1 Average utility of SU s CSSA NSSA Figure 2.8: The average utility of the SUs versus the probability for PUs being active PH1 (M = 5, N = 10). N is large, there are too many SUs in the CRN, therefore, the performance gap between CSSA and NSSA in terms of the average utility of the SUs is not significant. In Fig. 2.8, we show the average utility of the SUs obtained by the proposed algorithms versus the probability that PUs being active PH1 . Our results show that the performance of CSSA is better than NSSA. We can see that the performance gap between the CSSA scheme and the NSSA scheme increases with PH1 . When PH1 is small, which means the licensed channels are not heavily occupied by the PUs, the sensing accuracy improved by applying cooperative spectrum sensing is not essential for improving the performance of the SUs because the licensed channels are vacant for most of time. When PH1 increases, the appearance of the PUs becomes more frequent, therefore the improvement of sensingChapter 2. Hedonic Coalition Formation Game for CSSA Scheme in CRNs 45 20 50 100 150 200 250 2.5 3 3.5 4 4.5 5 5.5 6 6.5 7 D0 Average utility of SU s CSSA NSSA Figure 2.9: The average utility of the SUs versus the unit penalty per second D0 (M = 5, N = 10). accuracy with CSSA over NSSA is more significant. When the PUs has a higher traffic load, the sensing accuracy improved by applying cooperative spectrum sensing will help the SUs detect the activities of the PUs correctly, so that the SUs will pay less penalty for interfering the PUs’ transmission and avoid the waste of energy. In Fig. 2.9, we show the average utility of the SUs obtained by the proposed algorithms versus the unit penalty D0. Our results show that the performance of CSSA is better than NSSA. When D0 is increased, the average utility of the SUs is decreased under both the CSSA scheme and the NSSA scheme. However, the slope of decreasing for CSSA is much smaller, and the performance gap increases with D0. When D0 is large, each SU is incurred with a larger penalty if there is a miss detection. Since the probability ofChapter 2. Hedonic Coalition Formation Game for CSSA Scheme in CRNs 46 10 20 30 40 50 60 70 80 90 0 1 2 3 4 5 6 7 δ (ms) Average utility of SU s CSSA NSSA Figure 2.10: The average utility of the SUs versus the sensing duration δ (M = 5, N = 10, T = 100 ms). detection of the CSSA is higher than that of the NSSA, therefore, the average utility of the SUs for CSSA will not decrease as significant as NSSA when D0 is increased. In Fig. 2.10, we show the average utility of the SUs obtained by the proposed algo- rithms versus the sensing duration δ. Our results show that the CSSA performs better than the NSSA. Besides, we can see that there is a tradeoff between spectrum sensing and channel accessing. For both the CSSA and the NSSA schemes, the average utility of the SUs first increases with δ, and then decreases with δ after reaching the optimum point. Therefore, there exists an optimal sensing duration for our proposed CSSA scheme, which corresponds to the analysis in [23].Chapter 2. Hedonic Coalition Formation Game for CSSA Scheme in CRNs 47 2.6 Summary In this chapter, we studied cooperative spectrum sensing and channel accessing in a CRN with multiple licensed channels and multiple SUs. We proposed a CSSA scheme and formulated the multi-channel spectrum sensing and channel accessing problem as a hedonic coalition formation game. The value function of each coalition and the utility function of each SU take into account both the sensing accuracy and energy consumption. Since all the SUs that choose to sense the same channel belong to the same coalition, the commonly used merge-and-split rule [33] cannot be applied in our hedonic coalition formation game. Therefore, we proposed distributed algorithms to find a Nash-stable partition where no SU has the incentive to perform the switch operation in order to achieve a higher utility. Simulation results showed that the performance of our proposed CSSA scheme is better than that of the NSSA scheme. Besides, the results showed that our proposed distributed algorithms result in the self-organization of the SUs that achieves a higher average utility of the SUs after every iteration, and that there is a Nash- stable partition for our formulated hedonic coalition formation game. Furthermore, our proposed distributed algorithms can adapt the Nash-stable partition to environmental changes.48 Chapter 3 Stackelberg Game for CTRA Scheme in CRNs In the previous chapter, we study cooperative spectrum sensing in CRNs and present a hedonic coalition formation game for our proposed CSSA scheme. Now, we shift our focus from spectrum sensing to spectrum sharing, which is another important function in CRNs to improve spectrum efficiency. In this chapter, we present a Stackelberg game for cooperative transmission and random access in CRNs. We first present our motivations. We then describe the system model and our proposed CTRA scheme in details. The Stackelberg game model and equilibrium analysis for both the PU and the SUs comes after, followed by the performance evaluation results. A summary is given at the end of this chapter. 3.1 Motivations and Contributions Motivated by the physical layer cooperative communication technique [44], cooperative cognitive radio networks are new cognitive radio paradigm. In [45], Jia et al. exploited aChapter 3. Stackelberg Game for CTRA Scheme in CRNs 49 new research direction for CRNs by utilizing cooperative relay to assist the transmission and improve spectrum efficiency. In [46], the system enables cooperation between a primary cluster and a cognitive cluster in order to maintain the target primary throughput and provide more transmission opportunities to the SUs. In [40], Simeone et al. proposed and analyzed a framework, where a PU can lease its spectrum to an ad hoc network of secondary nodes in exchange for cooperation in the form of distributed space-time coding. The framework is modeled as a Stackelberg game [47]. In [48], Zhang et al. proposed a cooperative cognitive radio framework. Both the PU and the SUs target at maximizing their utilities in terms of their transmission rate and revenue. This model is formulated as a Stackelberg game and a unique Nash equilibrium is characterized. In [49]. Yi et al. considered multiple PUs and SUs in the system model, and analyzed the optimal strategies on the relay selection and the price for spectrum leasing by a Stackelberg game. In [50], Kasbekar et al. formulated the price competition in a CRN as a game by taking into account both bandwidth uncertainty and spatial reuse. Niyato et al. studied the problem of spectrum trading with multiple PUs selling spectrum opportunities to multiple SUs in [51]. They modeled the dynamic behavior of the SUs using the theory of evolutionary game [52]. An algorithm of the evolution process implementation for the SUs was proposed. In general, when the licensed spectrum is idle, all the SUs should have the opportu- nities to access the spectrum. The system models in [40, 48, 49] assumed the SUs access the licensed spectrum in a time division multiple access (TDMA) mode. Moreover, theChapter 3. Stackelberg Game for CTRA Scheme in CRNs 50 system model in [50] assumed the PU who has unused bandwidth in a time slot can lease it to a SU for the duration of the whole slot. Therefore, the results of [40, 48, 49, 50] cannot be extended to the situation where the SUs can access the licensed spectrum in a random access manner. In this chapter, we consider both cooperative transmission and random access in CRNs. The problem is to find the optimal strategies for both the PU and the SUs in order to maximize their own utilities. The PU needs to determine whether it is beneficial to use cooperative transmission and which SU should be chosen as the cooperative relay. If the PU selects a secondary relay, it also needs to determine its strategy on time resource allocation for cooperative transmission. The SUs need to decide the transmission probability in random access. In this chapter, we establish a model for cooperative cognitive radio networks and analyze the behaviour of the PU and the SUs using game theory. The contributions of this work are summarized as follows: • We propose a cooperative transmission and random access (CTRA) scheme for CRNs. The PU is responsible for relay selection and resource allocation. The SUs serve as relays and transmit their own data using random access. • We propose a game-theoretic model to study the proposed cooperative cognitive radio system. We describe the strategies available for both the PU and the SUs. In order to maximize their own utilities, we analyze the equilibrium strategies of both the PU and the SUs through a Stackelberg game.Chapter 3. Stackelberg Game for CTRA Scheme in CRNs 51 • Simulation results show that both the PU and the SUs achieve better performance in our proposed CTRA scheme than in the noncooperative transmission and random access (NTRA) scheme. It is beneficial to exploit cooperative diversity in cognitive radio networks. The rest of this chapter is organized as follows. Section 3.2 describes the system model and the CTRA scheme. The Stackelberg game model and equilibrium analysis are presented in Section 3.3. Section 3.4 presents the performance evaluation results. A summary of this chapter is given in Section 3.5. 3.2 System Model and CTRA Scheme In our system model, there are one primary transmitter-receiver pair and N secondary transmitter-receiver pairs. The primary transmitter P T communicates with the intended receiver P R, and this primary transmitter-receiver pair is assigned a licensed frequency band with bandwidth B. Each secondary transmitter STj, where j = 1, 2, . . . , N , seeks to exploit possible transmission opportunities in the licensed frequency band of the primary transmitter-receiver pair. We assume that each secondary transmitter STj always has data to send and it transmits data in a best-effort manner. In this chapter, since the primary transmitter and secondary transmitters are responsible for data transmission, we consider the primary transmitter as the PU, and consider the secondary transmitters as the SUs. The data transmission of PT is divided into time slots of duration T , and the CTRAChapter 3. Stackelberg Game for CTRA Scheme in CRNs 52 Figure 3.1: Primary transmission in sub-slot 1 of the proposed CTRA scheme. The pri- mary transmitter PT chooses secondary transmitter ST1 as its cooperative relay and transmits the primary data to both the secondary relay ST1 and the destination PR. scheme is performed in each time slot. As for the CTRA scheme, the primary transmitter PT either selects one secondary transmitter as its cooperative relay, or chooses not to have any cooperative relay. After that, all N SUs access the licensed spectrum in a random access manner. As an example, consider the network shown in Fig. 3.1, where there are one primary transmitter-receiver pair and two secondary transmitter-receiver pairs (N = 2) in the system. Primary transmitter PT selects secondary transmitter ST1 as its cooperative relay. For the primary transmitter P T , one time slot can be divided into two portions, t and T − t (0 < t ≤ T ), where t is for the primary transmission and T − t is for the secondary transmission. No matter P T selects secondary relay or not duringChapter 3. Stackelberg Game for CTRA Scheme in CRNs 53 Figure 3.2: Primary transmission in sub-slot 2 of the proposed CTRA scheme. The chosen secondary relay ST1 forwards the primary data to P R. the first portion, it will provide its spectrum to all the SUs during the second portion. As primary transmitter P T owns the spectrum and provides its licensed spectrum to all SUs during the second portion, P T loses the opportunity of transmitting its own primary data during the second portion T − t. Therefore, it is reasonable for the PU to charge the SUs for accessing its licensed spectrum. If the primary transmitter P T chooses the secondary transmitter STj as its cooper- ative relay, the first portion t can further be divided into two sub-slots according to a parameter α, where α ∈ {0.5, 1}. As shown in Fig. 3.1, the first sub-slot is of duration αt and is dedicated to the transmission from the primary transmitter PT to the secondary relay ST1 and the destination P R. The second sub-slot is of duration (1 − α)t and is dedicated to the transmission from the chosen secondary relay ST1 to PR, which is shownChapter 3. Stackelberg Game for CTRA Scheme in CRNs 54 Figure 3.3: Secondary transmission in sub-slot 3 of the proposed CTRA scheme. The SUs attempt to access the licensed frequency band of PT in a random access manner. in Fig. 3.2. If the primary transmitter PT does not select any SU as its cooperative relay, then α = 1 and the duration of the sub-slot 1 is t, which is dedicated to the transmission from PT to PR. We denote the second portion with duration T − t as the third sub-slot of PT , which is dedicated to the secondary transmission. As shown in Fig. 3.3, we assume that all the SUs access the licensed spectrum during the third sub-slot by using slotted Aloha, and each time slot for the slotted Aloha is of duration ∆t. For simplicity, we assume that T is a multiple of ∆t. The channels between different users are modeled as independent complex Gaussian random variables, invariant within each time slot, but varying over time slots (block-Chapter 3. Stackelberg Game for CTRA Scheme in CRNs 55 fading channels). For convenience, we define the ratio of the transmitting power to the noise power as the signal-to-noise ratio (SNR) of the transmitter. Given the transmit SNR Γ and the complex channel gain h of the link, the transmission rate R over that link can be modeled as [40]: R = B log2 ( 1 + |h|2Γ) . (3.1) We consider both path loss and channel fading in the system model. Given the distance d between any two nodes in our model, the channel gain between these two nodes can be given as |h|2 = δ2/dη, where η is the path loss exponent and δ is a Rayleigh distributed random variable. The probability density function of δ (δ ≥ 0) for parameter σ > 0 is p(δ) = δ σ2 exp ( − δ2 2σ2 ) . (3.2) The following notations are used to denote the complex channel gain of different links in each block: hP denotes the channel gain between the primary transmitter PT and the primary receiver PR; hP Sj denotes the channel gain between the primary transmitter PT and the secondary transmitter STj; hSjP denotes the channel gain between the secondary transmitter STj and the primary receiver P R; hSj denotes the channel gain between the secondary transmitter STj and the secondary receiver SRj. Moreover, we assume that there is no power control. That is, both the primary transmitter and the secondary transmitters are transmitting data at a fixed power level. We use ΓP to denote the transmit SNR at the primary transmitter P T and use ΓS to denote the transmit SNR at the secondary transmitter STj, where j = 1, 2, . . . , N .Chapter 3. Stackelberg Game for CTRA Scheme in CRNs 56 Given the above notations, we can model the transmission rate of any link similar to (3.1). For example, for the transmission rate of the primary link between P T and P R, denoted as RP , it is given by RP = B log2 ( 1 + |hP |2ΓP ) . (3.3) We use the following notations to denote the transmission rate of other links: RP Sj denotes the transmission rate of the link between P T and STj; RSjP denotes the transmis- sion rate of the link between STj and P R; RSj denotes the transmission rate of secondary link between STj and SRj. We assume that the secondary relay node uses decode-and-forward as its cooperation strategy [53], [54]. According to the analysis in [55], the achievable cooperative data rate of the primary transmitter PT under cooperative transmission with secondary relay STj, where j = 1, 2, . . . , N , is given by Rcoop,j = 1 2 min{B log2 ( 1 + |hP Sj |2ΓP ) , B log2 ( 1 + |hP |2ΓP + |hSjP |2ΓS )}. (3.4) In (3.4), the first term represents the maximum rate at which the secondary relay STj can reliably decode the source message from the primary transmitter P T . The second term represents the maximum rate at which the destination P R can reliably decode the source message given the repeated transmission from the source P T and the secondary relay STj. Requiring both the secondary relay STj and the destination P R to decode the entire codeword without error results in the minimum of the two data rates in (3.4).Chapter 3. Stackelberg Game for CTRA Scheme in CRNs 57 3.3 Stackelberg Game Analysis According to the system model presented in Section 3.2, there is a sequential structure of decision-making. First, P T determines whether it is beneficial to use cooperative trans- mission and which secondary transmitter should be chosen as the cooperative relay. PT also determines its optimal value t∗ and the corresponding value of α. Then, all the SUs determine how to access the available licensed spectrum for the secondary transmission given the decisions made by the PU. Therefore, this cooperative cognitive radio network can be analyzed by a Stackelberg game. Suppose all the SUs are fully informed about the decisions made by the PU, our Stackelberg game has perfect information, and the decisions of the PU can be transmitted to the SUs through the control channel. 3.3.1 Stackelberg Game with Perfect Information The set of players in this Stackelberg game are the PU and N SUs. The primary trans- mitter P T , which owns the licensed spectrum, plays the role of the leader. Each STj, where j = 1, 2, . . . , N , which seeks to exploit possible transmission opportunities in the licensed frequency band of P T , plays the role of the follower. There are two kinds of strategies available to the PU. First, PT may have N +1 pure strategies for the relay selection and we use r ∈ {0, 1, 2, . . . , N} to denote which SU is chosen by P T as cooperative relay. If r = 0, it means that PT chooses no cooperative relay and therefore α = 1. Otherwise, PT chooses STr as its cooperative relay and α = 0.5. For the second strategy, PT determines how to allocate time resources andChapter 3. Stackelberg Game for CTRA Scheme in CRNs 58 chooses the value of t in the interval (0, T ]. After P T chooses its strategies r, t and α, all the SUs choose their strategies simultane- ously. The strategies available to these SUs are denoted by a vector p = (p1, p2, . . . , pN). The value of element pi, where i = 1, 2, . . . , N , is chosen in the interval [0, 1] and it cor- responds to the transmission probability of STi during the third sub-slot. In order to find the Nash equilibrium of this Stackelberg game, backward induction is used. We start by finding the equilibrium strategies of N SUs given the PU’s decisions on its strategies r, t and α. Then, taking these actions as given, we find the optimal strategies of the PU who makes the decisions before all the SUs. 3.3.2 Strategies for Secondary Users Given the time allocation t determined by the PU, we can calculate the number of slots for the slotted Aloha as n = ⌊ T − t ∆t ⌋ . (3.5) In each slot, each secondary transmitter STi, where i = 1, 2, . . . , N , determines its own transmission probability pi. STi may transmit data (i.e., 0 < pi ≤ 1) or not (i.e., pi = 0). If STi transmits data in one slot, the transmission may either be a success or a failure due to packet collisions with other secondary transmissions. Besides, STi should pay for accessing the licensed spectrum with probability pi. STi wants to achieve better performance in terms of transmitting more data and paying less money. Therefore, theChapter 3. Stackelberg Game for CTRA Scheme in CRNs 59 utility function of secondary transmitter STi is defined as USi(p, r) = n ( Psuc,i(p)Udi − piUci(pi, r) ) , (3.6) where Udi denotes the successful data transmission utility of STi in each slot, Uci(pi, r) denotes the licensed spectrum accessing payment from STi to the primary transmitter PT in each slot, and Psuc,i(p) is the successful transmission probability of STi. The utility function in (3.6) means that, in each slot of slotted Aloha, STi can get the successful data transmission utility Udi with probability Psuc,i(p) and has to make the payment Uci(pi, r) with probability pi. The successful data transmission utility Udi of STi is defined as Udi = ωSRSi∆t, (3.7) where ωS is the equivalent utility per unit secondary data transmission, and RSi is the secondary data rate of STi. The successful transmission probability Psuc,i(p) of STi is given by Psuc,i(p) = pi ∏ j =i (1− pj). (3.8) If the secondary transmitter STi attempts to access the licensed channel of PT with probability pi, it should make a payment to the primary transmitter PT with probability pi. We define the accessing payment Uci(pi, r) as Uci(pi, r) = ci(pi, r)∆t = cmax,i(r)pi∆t, (3.9) where ci(pi, r) is the secondary accessing price for the STi per unit access time. We choose a linear pricing function [56] so that the accessing price ci(pi, r) increases with theChapter 3. Stackelberg Game for CTRA Scheme in CRNs 60 transmission probability pi. It means that STi should pay more if it attempts to access the licensed spectrum aggressively. Moreover, we define the maximum accessing price cmax,i(r) as a function of the secondary relay selection r, which is given by cmax,i(r) = ccoop, if r = i, cnon, if r = i, (3.10) where ccoop stands for the maximum accessing price when STi is selected as the cooperative relay by the PU (i.e., r = i), and cnon stands for the maximum accessing price when STi is not selected as the cooperative relay (i.e., r = i). Since the secondary relay consumes energy to forward the primary data during sub-slot 2, it is reasonable for the chosen secondary relay STr to pay less than the other SUs. Therefore, we have cnon > ccoop > 0 in order to differentiate the secondary accessing price. By substituting (3.7)−(3.9) into (3.6), the utility of secondary user STi is given by USi(p, r) = n∆t ( ωSRSipi ∏ j =i (1− pj)− cmax,i(r)p2i ) . (3.11) Theorem 2 There exists a Nash equilibrium in the secondary users’ game. Proof : According to [57], a Nash equilibrium exists in the secondary users’ game if two conditions are satisfied. First, the strategy set is nonempty, convex and compact. Second, USi(p, r) is continuous in p and concave in pi. The first condition is satisfied because 0 ≤ pi ≤ 1, for all i = 1, 2, . . . , N . For the second condition, since USi(p, r) is continuous in p, we only need to prove USi(p, r) is concave in pi. We take the firstChapter 3. Stackelberg Game for CTRA Scheme in CRNs 61 and second order derivative of USi(p, r) with respect to pi to show its concavity. The derivatives are given as follows: ∂USi(p, r) ∂pi = n∆t ( ωSRSi ∏ j =i (1− pj)− 2cmax,i(r)pi ) . (3.12) ∂2USi(p, r) ∂pi2 = −2n∆tcmax,i(r). (3.13) In (3.13), we have n > 0 because there is no secondary users’ game if n = 0. Besides, we notice that ∆t and cmax,i(r) are positive. The second order derivative in (3.13) is always negative, which means USi(p, r) is concave in pi. Thus, there exists at least one Nash equilibrium in the secondary users’ game. In order to find the Nash equilibrium, an evolutionary algorithm [58] can be used. By using the evolutionary algorithm as a tool to determine the Nash equilibrium, we can find the equilibrium strategy p∗ for the SUs. 3.3.3 Strategies for Primary User Based on the results of the secondary users’ game, the leader of the Stackelberg game (i.e., the PU), can determine its strategies (r, t, α) in order to maximize its own utility. The utility of the PU is composed of two parts. The first part is the equivalent revenue of primary data transmission, and the second part is the payment made by the SUs for accessing the licensed spectrum. Therefore, we define the utility function of P T to be UP (p, r, t) = ωP R(r)t + ⌊ T − t ∆t ⌋ N∑ i=1 piUci(pi, r), (3.14)Chapter 3. Stackelberg Game for CTRA Scheme in CRNs 62 where ωP is the equivalent revenue per unit primary data transmission utility. R(r) is the primary transmission rate, which is defined as R(r) = RP , if r = 0, Rcoop,j, if r = j where j = 1, 2, . . . , N. (3.15) In order to maximize UP , the PU first chooses the value of r, and find the optimal value of t according to (3.14). For each value of r, the one that maximizes PU’s utility function is chosen as the cooperative relay, and the corresponding values of α and t∗ can then be determined. Proposition 3 For each possible value of r, the corresponding value of t∗ is a multiple of ∆t, and the optimal value t∗ can only be chosen from a finite set {∆t, 2∆t, . . . , T}. Proof : Suppose t is not a multiple of ∆t. From (3.5), we can calculate the remaining time in each time slot T as trem = T − t− n∆t. (3.16) Since 0 < trem < ∆t, (3.17) it implies that the remaining time in each time slot T is greater than zero and less than the duration of slot ∆t. If t is not a multiple of ∆t, then the remaining time trem in each time slot T is wasted. From (3.14), the equivalent revenue of primary data transmission is an increasing function of t. If the remaining time trem is used for primary data transmission, the utility of P T will be increased. From (3.16), t + rrem is a multiple of ∆t. From theChapter 3. Stackelberg Game for CTRA Scheme in CRNs 63 above, the optimal value t∗ must be a multiple of ∆t. Since we assume T is a multiple of ∆t, t∗ can only be chosen from the finite set {∆t, 2∆t, . . . , T}. Based on the results of the secondary users’ game, we can find the optimal strategies for the PU according to (3.14) and Proposition 3. The primary transmitter PT first chooses the value of r, and for each value of r, the corresponding value of t∗ which maximizes UP in (3.14) can only be chosen from a finite set {∆t, 2∆t, . . . , T}. Once the optimal strategies r∗ and t∗ have been found, the corresponding value of α can be determined by the cooperative transmission scheme, which is α = 1, if r∗ = 0, 0.5, if r∗ = j where j = 1, 2, . . . , N. (3.18) From the above analysis, we can determine the equilibrium strategies for both the PU and the SUs. The equilibrium strategy for the PU is (r∗, t∗, α), and the equilibrium strategies for the N SUs are given by the vector p∗. 3.4 Performance Evaluation In this section, we evaluate the performance of our proposed CTRA scheme with the NTRA scheme, where the PU will not select any SU as its cooperative relay. In the simulation model, we consider there are one primary transmitter-receiver pair and N (N > 1) secondary transmitter-receiver pairs. The distance between the primary trans- mitter PT and the primary receiver P R is equal to 10 m. The positions of the SUs areChapter 3. Stackelberg Game for CTRA Scheme in CRNs 64 Figure 3.4: Simulation model with one PU and five SUs. randomly placed in a 10 m×10 m square region. An example of simulation model with N = 5 is given in Fig. 3.4. For the path loss and channel fading, we choose η = 2 and σ = 0.15. We assume that both the primary transmitter and secondary transmitters transmit at a fixed power level without power control, and we choose P = 10 mW for both the primary and secondary transmitters. The noise power is N0 = 0.1 mW, therefore, the transmit SNRs of both the primary transmitter and the secondary transmitters are ΓP = ΓS = P/N0 = 100. Other parameters used in our simulation are as follows: the bandwidth of the primary licensed frequency band is B = 500 kHz; the length of the whole time slot T = 1 s; the duration of each slot for random access ∆t = 0.1 s; the maximum accessing price for cooperative relay ccoop = 1. The simulation results are averaged over 10000 simulation runs.Chapter 3. Stackelberg Game for CTRA Scheme in CRNs 65 2 3 4 5 6 7 8 9 10 30 35 40 45 50 55 60 65 N Utility of primary use r CTRA NTRA Figure 3.5: The utility of the PU versus the number of SUs N (ωP = 1, ωS = 0.1, cnon = 18). Fig. 3.5 shows the utility of the PU versus the number of SUs N when the equivalent revenue per unit primary data transmission utility ωP = 1, the equivalent revenue per unit secondary data transmission utility ωS = 0.1 and the maximum accessing price for noncooperative relay cnon = 18. Since cooperative diversity is exploited in CTRA, we can see that the utility of the PU under CTRA is higher than that under NTRA. When the number of SUs N increases, the PU has more options for cooperative relay selection and there is a better chance for the PU to select a secondary relay which gives a higher cooperative transmission rate. Therefore, the utility of the PU increases with N under the CTRA scheme. As for the NTRA scheme, the utility of the PU increases with N moderately because cooperative transmission is not used in the NTRA scheme.Chapter 3. Stackelberg Game for CTRA Scheme in CRNs 66 3 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 cnon Utility of primary use r CTRA NTRA Figure 3.6: The utility of the PU versus the maximum accessing price cnon (ωP = 1, ωS = 0.1, N = 5). Fig. 3.6 shows the utility of the PU versus the maximum accessing price for nonco- operative relay cnon when ωP = 1, ωS = 0.1 and N = 5. We can see that the utility of the PU under CTRA is higher than that under NTRA, because cooperative transmission is used and cooperative diversity is exploited in CTRA. The utility of the PU increases with cnon under both the CTRA and NTRA schemes. When the maximum accessing price cnon is low, the equivalent revenue of primary data transmission is much greater than the payment from secondary random accessing, therefore, the utility of PU does not increase too much. When the maximum accessing price cnon increases, the payment from the secondary random accessing increases and a majority of PU’s utility comes from the payment of random accessing, therefore, t∗ decreases and UP increases with cnonChapter 3. Stackelberg Game for CTRA Scheme in CRNs 67 3 5 10 15 20 25 0 5 10 15 20 25 30 35 cnon Average utility of secondary user s CTRA NTRA Figure 3.7: The average utility of the SUs versus the maximum accessing price cnon (ωP = 1, ωS = 0.8, N = 5). significantly. Fig. 3.7 shows the average utility of the SUs versus the maximum accessing price cnon when ωP = 1, ωS = 0.8 and N = 5. We can see that the average utility of the SUs under CTRA is larger than that under NTRA. Also, the average utility of the SUs increases with cnon under both the CTRA scheme and NTRA scheme. As the maximum accessing price cnon increases, the PU decreases the value of t∗ in order to obtain more revenue from secondary random accessing. Therefore, the number of slots for the slotted Aloha will increase and the average utility of SUs will increase as well. In summary, Figs. 3.5−3.7 show that both the PU and the SUs can obtain higher utilities under CTRA scheme, and they have the incentive to engage in cooperative transmission.Chapter 3. Stackelberg Game for CTRA Scheme in CRNs 68 3.5 Summary In this chapter, we investigated the behaviour of the PU and the SUs under our proposed CTRA scheme in a cooperative cognitive radio network. According to the sequential structure of decision making, we analyzed the established cooperative cognitive radio network using a Stackelberg game with perfect information. Given the decisions made by the PU and the utility function we defined for the SUs, we showed that there exists a Nash equilibrium in the secondary users’ game. We determined the optimal strategies of the PU by using backward induction. Simulation results showed that both the utility of the PU and the average utility of the SUs under our proposed CTRA scheme are higher than those under the NTRA scheme. Thus, a win-win situation can be achieved by exploiting cooperative diversity in our proposed CTRA scheme.69 Chapter 4 Conclusions and Future Work In this chapter, we conclude this thesis by summarizing the research results and con- tributions. We discuss the strengths and limitations of the thesis research and suggest directions for future work as well. 4.1 Conclusions In the thesis, we focused on the cooperative spectrum sensing and cooperative transmis- sion in CRNs and used game theory to analyze the optimal strategies for both the PUs and SUs. A hedonic coalition formation game model was proposed to analyze cooperative spectrum sensing and channel accessing in Chapter 2, and a Stackelberg game model was proposed to analyze cooperative transmission and random access in Chapter 3. In Chapter 2, we studied cooperative spectrum sensing in CRNs and analyzed the be- haviour of the SUs. We proposed a cooperative spectrum sensing and accessing (CSSA) scheme for all the SUs. While most of the current literature only focused on the sensing performance (i.e., the probability of detection and the probability of false alarm) and ig- nore the channel accessing of the SUs, we considered both cooperative spectrum sensingChapter 4. Conclusions and Future Work 70 and channel accessing in our proposed CSSA scheme. As for evaluating the performance of the SUs, besides the data throughput, we took energy consumption of the SUs into consideration because energy efficiency is always a concern for practical implementation. We presented a complete framework to study the multi-channel spectrum sensing and channel accessing problem for the CRNs with multiple PUs and multiple SUs, and de- scribed the implementation details (i.e., proposed distributed algorithms) for our CSSA scheme. We formulated the multi-channel spectrum sensing and channel accessing prob- lem as a hedonic coalition formation game, where a coalition corresponds to the SUs that have chosen to sense and access a particular channel. The value function of each coalition and the utility function of each SU took into account both the sensing accuracy and energy consumption. In order to implement our CSSA scheme distributively, we pro- posed an algorithm for the selection of decision node in a coalition. Also, we proposed an algorithm based on the switch rule for the SUs to make distributed decisions on whether to join or leave a coalition. Simulation results show that the set with all the SUs will always converge to a final network partition, which is both Nash-stable and individually stable. Besides, the proposed distributed algorithms can adapt the Nash-stable parti- tion to environmental changes. Moreover, our proposed CSSA scheme achieves a better performance than the noncooperative spectrum sensing and accessing (NSSA) scheme in terms of the average utility of the SUs. In Chapter 3, we focused on cooperative transmission in CRNs, where the SU can be selected as cooperative relay and thus forward the data packets for the PU. We pro-Chapter 4. Conclusions and Future Work 71 posed a cooperative transmission and random access (CTRA) scheme, and allow both the PU and the SUs to have the incentive to engage in cooperative transmission under the CTRA scheme, in order to improve their own performance. While current research assume the SUs access the licensed frequency band in a TDMA manner, we considered the random access scheme for the SUs so that all SUs have the opportunities to access the licensed spectrum when the spectrum is idle. In order to improve the performance in our proposed CTRA scheme, the PU needs to consider whether it is beneficial to use cooperative transmission and which SU should be chosen as the cooperative relay. In addition, if the PU selects a secondary relay, it needs to allocate time resources for coop- erative transmission. Then, the SUs need to determine their strategies of random access when the licensed spectrum of the PU is available. Based on the sequential structure of the decision-making, we studied the cooperative cognitive radio network and determine the equilibrium strategies for both the PU and the SUs using the Stackelberg game. Simulation results show that both the PU and the SUs achieve better performance when compared with the noncooperative transmission and random access (NTRA) scheme. 4.2 Future Work In our proposed CSSA scheme, we assumed that all SUs have the same spectrum sensing duration δ and the same energy detection threshold ε. Therefore, in our hedonic coalition formation game model, the only kind of strategy for each SU is which licensed channel it chooses to sense and access. It would be interesting if we also consider the sensingChapter 4. Conclusions and Future Work 72 duration and the detection threshold as available strategies for the SUs, which means each SU can choose its own value of δ and ε. In this case, the system model would be more general, but we need to come up with new rules so that the SUs can adjust the sensing duration and the detection threshold distributively in order to achieve better performance in the CRN. Besides, the complexity analysis is also important in practical implementation. If we consider sensing duration and detection threshold as new strategies for the SUs, there would be more information exchange between the SUs, which will increase the cooperation overhead. There is a tradeoff between cooperation gain and cooperation overhead, and it is crucial to improve the cooperation gain as much as possible while limit the cooperation overhead to a considerable level. As for the research of cooperative transmission and random access in CRNs, we considered a system model where there is one PU and multiple SUs and chose Stackelberg game to analyze the optimal strategies for both the PU and the SUs. In the future work for the CTRA scheme, we can consider a more general system model where there are multiple PUs and multiple SUs. In our work, the Stackelberg game model characterized the cooperative relationship between the PU and the SU, and the competitive relationship between different SUs. However, if we consider there are multiple SUs in the system, there will be a third kind of relationship in the CRN, which is the competitive relationship between different PUs. If there are multiple PUs in the CRN, each PU is going to compete with the other PUs in order to get the best secondary relay for itself. In this case, a more general game framework called extensive game can be applied. Since thereChapter 4. Conclusions and Future Work 73 are multiple licensed channels in the network, the SUs are given more options for channel accessing. Therefore, it is also interesting to analyze which licensed channel will be chosen to access by the SUs.74 Bibliography [1] “Spectrum policy task force,” Federal Communications Commission, Tech. Rep., 2002. [2] J. Mitola III and G. Q. Maguire Jr., “Cognitive radio: Making software radios more personal,” IEEE Personal Communications, vol. 6, no. 4, pp. 13–18, Aug. 1999. [3] L. B. Le and E. Hossain, “Resource allocation for spectrum underlay in cognitive radio networks,” IEEE Trans. on Wireless Communications, vol. 7, no. 12, pp. 5306– 5315, Dec. 2008. [4] I. Maric´, R. D. Yates, and G. Kramer, “Capacity of interference channels with partial transmitter cooperation,” IEEE Trans. on Information Theory, vol. 53, no. 10, pp. 3536–3548, Oct. 2007. [5] M. Sanna and M. Murroni, “Opportunistic wideband spectrum sensing for cognitive radios with genetic optimization,” in Proc. of IEEE ICC, Cape Town, South Africa, May 2010. [6] B. Wang and K. J. R. Liu, “Advances in cognitive radio networks: A survey,” IEEE Journal on Selected Topics in Signal Processing, vol. 5, no. 1, pp. 5–23, Feb. 2011.Bibliography 75 [7] K. Haghighi, A. Svensson, and E. Agrell, “Wideband sequential spectrum sensing with varying thresholds,” in Proc. of IEEE Globecom, Miami, FL, Dec. 2010. [8] P. Lin, J. Jia, Q. Zhang, and M. Hamdi, “Dynamic spectrum sharing with multiple primary and secondary users,” IEEE Trans. on Vehicular Technology, vol. 60, no. 4, pp. 1756–1765, May 2011. [9] T. C. Clancy, “Achievable capacity under the interference temperature model,” in Proc. of IEEE INFOCOM, Anchorage, AK, May 2007. [10] A. C. Bovik, P. Maragos, and T. F. Quatieri, “AM-FM energy detection and separa- tion in noise using multiband energy operators,” IEEE Trans. on Signal Processing, vol. 41, no. 12, pp. 3245–3265, Dec. 1993. [11] W. A. Gardner, “Signal interception: A unifying theoretical framework for feature detection,” IEEE Trans. on Communications, vol. 36, no. 8, pp. 897–906, Aug. 1988. [12] H. Tang, “Some physical layer issues of wide-band cognitive radio systems,” in Proc. of IEEE Symposium on New Frontiers in Dynamic Spectrum (DySPAN), Baltimore, MD, Nov. 2005. [13] I. F. Akyildiz, B. F. Lo, and R. Balakrishnan, “Cooperative spectrum sensing in cognitive radio networks: A survey,” Elsevier Physical Communication, vol. 4, no. 1, pp. 40–62, March 2011.Bibliography 76 [14] K. W. Choi, E. Hossain, and D. I. Kim, “Cooperative spectrum sensing under a random geometric primary user network model,” IEEE Trans. on Wireless Commu- nications, vol. 10, no. 6, pp. 1932–1944, June 2011. [15] A. Ghasemi and E. S. Sousa, “Collaborative spectrum sensing for opportunistic access in fading environments,” in Proc. of IEEE Symposium on New Frontiers in Dynamic Spectrum (DySPAN), Baltimore, MD, Nov. 2005. [16] S. M. Mishra, A. Sahai, and R. W. Brodersen, “Cooperative sensing among cognitive radios,” in Proc. of IEEE ICC, Istanbul, Turkey, June 2006. [17] F. M. Willems, “The discrete memoryless multiple access channel with partially cooperating encoders,” IEEE Trans. on Information Theory, vol. IT-29, no. 3, pp. 441–445, May 1983. [18] G. Zhao, C. Yang, G. Y. Li, D. Li, and A. C. K. Soong, “Power and channel allocation for cooperative relay in cognitive radio networks,” IEEE Journal on Selected Topics in Signal Processing, vol. 5, no. 1, pp. 151–159, Feb. 2011. [19] D. Li, Y. Xu, X. Wang, and M. Guizani, “Coalitional game theoretic approach for secondary spectrum access in cooperative cognitive radio networks,” IEEE Trans. on Wireless Communications, vol. 10, no. 3, pp. 844–856, March 2011. [20] C. Santivanez, R. Ramanathan, C. Partridge, R. Krishnan, M. Condell, and S. Polit, “Opportunistic spectrum access: Challenges, architecture, protocols,” in Proc. of ACM WICON, Boston, MA, Aug. 2006.Bibliography 77 [21] M. Gandetto and C. Regazzoni, “Spectrum sensing: A distributed approach for cognitive terminals,” IEEE Journal on Selected Areas in Communications, vol. 25, no. 3, pp. 546–557, April 2007. [22] T. C. Aysal, S. Kandeepan, and R. Piesiewicz, “Cooperative spectrum sensing with noisy hard decision transmissions,” in Proc. of IEEE ICC, Dresden, Germany, June 2009. [23] Y.-C. Liang, Y. Zeng, E. C. Peh, and A. T. Hoang, “Sensing-throughput tradeoff for cognitive radio networks,” IEEE Trans. on Wireless Communications, vol. 7, no. 4, pp. 1326–1337, April 2008. [24] W. Saad, Z. Han, T. Basar, M. Debbah, and A. Hjorungnes, “Coalition formation games for collaborative spectrum sensing,” IEEE Trans. on Vehicular Technology, vol. 60, no. 1, pp. 276–297, Jan. 2011. [25] W.-Y. Lee and I. F. Akyildiz, “Optimal spectrum sensing framework for cognitive radio networks,” IEEE Trans. on Wireless Communications, vol. 7, no. 10, pp. 3845– 3857, Oct. 2008. [26] W. Wang, B. Kasiri, J. Cai, and A. S. Alfa, “Distributed cooperative multi-channel spectrum sensing based on dynamic coalitional game,” in Proc. of IEEE Globecom, Miami, FL, Dec. 2010.Bibliography 78 [27] C. Song and Q. Zhang, “Cooperative spectrum sensing with multi-channel coordina- tion in cognitive radio networks,” in Proc. of IEEE ICC, Cape Town, South Africa, May 2010. [28] Q. Zhao, S. Geirhofer, L. Tong, and B. M. Sadler, “Opportunistic spectrum access via periodic channel sensing,” IEEE Trans. on Signal Processing, vol. 56, no. 2, pp. 785–796, Feb. 2008. [29] H. Su and X. Zhang, “Energy-efficient spectrum sensing for cognitive radio network- s,” in Proc. of IEEE ICC, Cape Town, South Africa, May 2010. [30] L. Lu, H.-C. Wu, and S. Iyengar, “A novel robust detection algorithm for spectrum sensing,” IEEE Journal on Selected Areas in Communications, vol. 29, no. 2, pp. 305–315, Feb. 2011. [31] J. Meng, W. Yin, H. Li, E. Hossain, and Z. Han, “Collaborative spectrum sensing from sparse observations in cognitive radio networks,” IEEE Journal on Selected Areas in Communications, vol. 29, no. 2, pp. 327–337, Feb. 2011. [32] K. Koufos, K. Ruttik, and R. Jantti, “Distributed sensing in multiband cognitive networks,” IEEE Trans. on Wireless Communications, vol. 10, no. 5, pp. 1667–1677, May 2011. [33] W. Saad, Z. Han, M. Debbah, A. Hjorungnes, and T. Basar, “Coalitional game theory for communication networks,” IEEE Signal Processing Magazine, vol. 26, no. 5, pp. 77–97, Sept. 2009.Bibliography 79 [34] A. Bogomolnaia and M. O. Jackson, “The stability of hedonic coalition structures,” Games and Economic Behavior, vol. 38, pp. 201–230, Feb. 2002. [35] IEEE 802.22 working group on wireless regional area networks. [Online]. Available: http://www.ieee802.org/22/ [36] D. Cabric, S. M. Mishra, and R. W. Brodersen, “Implementation issues in spectrum sensing for cognitive radios,” in Proc. of IEEE Asilomar Conference on Signals, Systems and Computers, Pacific Grove, CA, Nov. 2004. [37] W. Zhang and K. B. Letaief, “Cooperative spectrum sensing with transmit and relay diversity in cognitive radio networks,” IEEE Trans. on Wireless Communications, vol. 7, no. 12, pp. 4761–4766, Dec. 2008. [38] G. Ganesan and Y. Li, “Agility improvement through cooperative diversity in cog- nitive radio,” in Proc. of IEEE Globecom, St. Louis, MO, Dec. 2005. [39] S. Atapattu, C. Tellambura, and H. Jiang, “Energy detection based cooperative spectrum sensing in cognitive radio networks,” IEEE Trans. on Wireless Communi- cations, vol. 10, no. 4, pp. 1232–1241, April 2011. [40] O. Simeone, I. Stanojev, S. Savazzi, Y. Bar-Ness, U. Spagnolini, and R. Pickholtz, “Spectrum leasing to cooperating secondary ad hoc networks,” IEEE Journal on Selected Areas in Communications, vol. 26, no. 1, pp. 203–213, Jan. 2008.Bibliography 80 [41] D. Ray, A Game-Theoretic Perspective on Coalition Formation. Oxford University Press, 2007. [42] T. Jech, Set Theory: The Third Millennium Edition, Revised and Expanded. Springer, 2006. [43] W. Saad, Z. Han, T. Basar, M. Debbah, and A. Hjorungnes, “Hedonic coalition formation for distributed task allocation among wireless agents,” IEEE Trans. on Mobile Computing (accepted), 2011. [44] M. O. Hasna and M.-S. Alouini, “End-to-end performance of transmission systems with relays over Rayleigh-fading channels,” IEEE Trans. on Wireless Communica- tions, vol. 2, no. 6, pp. 1126–1131, Nov. 2003. [45] J. Jia, J. Zhang, and Q. Zhang, “Cooperative relay for cognitive radio networks,” in Proc. of IEEE INFOCOM, Rio de Janeiro, Brazil, April 2009. [46] I. Krikidis, J. N. Laneman, J. S. Thompson, and S. McLaughlin, “Protocol design and throughput analysis for multi-user cognitive cooperative systems,” IEEE Trans. on Wireless Communications, vol. 8, no. 9, pp. 4740–4751, Sept. 2009. [47] H. von Stackelberg, Market Structure and Equilibrium. Springer, 2011. [48] J. Zhang and Q. Zhang, “Stackelberg game for utility-based cooperative cognitive radio networks,” in Proc. of ACM MobiHoc, New Orleans, LA, May 2009.Bibliography 81 [49] Y. Yi, J. Zhang, Q. Zhang, T. Jiang, and J. Zhang, “Cooperative communication- aware spectrum leasing in cognitive radio networks,” in Proc. of IEEE Symposium on New Frontiers in Dynamic Spectrum (DySPAN), Singapore, April 2010. [50] G. S. Kasbekar and S. Sarkar, “Spectrum pricing games with bandwidth uncertainty and spatial reuse in cognitive radio networks,” in Proc. of ACM MobiHoc, Chicago, IL, Sept. 2010. [51] D. Niyato, E. Hossain, and Z. Han, “Dynamics of multiple-seller and multiple-buyer spectrum trading in cognitive radio networks: A game-theoretic modeling approach,” IEEE Trans. on Mobile Computing, vol. 8, no. 8, pp. 1009–1022, Aug. 2009. [52] M. J. Osborne, An Introduction to Game Theory. Oxford University Press, 2003. [53] J. N. Laneman and G. W. Wornell, “Distributed space-time-coded protocols for exploiting cooperative diversity in wireless networks,” IEEE Trans. on Information Theory, vol. 49, no. 10, pp. 2415–2425, Oct. 2003. [54] A. Host-Madsen and J. Zhang, “Capacity bounds and power allocation for wireless relay channels,” IEEE Trans. on Information Theory, vol. 51, no. 6, pp. 2020–2040, June 2005. [55] J. N. Laneman, D. N. C. Tse, and G. W. Wornell, “Cooperative diversity in wireless networks: Efficient protocols and outage behavior,” IEEE Trans. on Information Theory, vol. 50, no. 12, pp. 3062–3080, Dec. 2004.Bibliography 82 [56] Y. Tan, S. Sengupta, and K. P. Subbalakshmi, “Competitive spectrum trading in dynamic spectrum access markets: A price war,” in Proc. of IEEE Globecom, Miami, FL, Dec. 2010. [57] G. Debreu, “A social equilibrium existence theorem,” in Proc. of the National Academy of Sciences (PNAS), vol. 38, no. 10, Oct. 1952. [58] R. Rajabioun, E. Atashpaz-Gargari, and C. Lucas, “Colonial competitive algorithm as a tool for Nash equilibrium point achievement,” in Proc. of Int’l Conf. on Com- putational Science and Its Applications (ICCSA), Perugia, Italy, June 2008.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Game theoretic approach for cooperative sensing and...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Game theoretic approach for cooperative sensing and transmission in cognitive radio networks Hao, Xiaolei 2011-12-31
pdf
Page Metadata
Item Metadata
Title | Game theoretic approach for cooperative sensing and transmission in cognitive radio networks |
Creator |
Hao, Xiaolei |
Publisher | University of British Columbia |
Date | 2011 |
Date Issued | 2011-08-22 |
Description | The concept of cognitive radio aims to increase the efficiency of spectrum usage. Besides, cooperation techniques, such as cooperative sensing and cooperative transmission, have been widely used to further enhance the performance of cognitive radio networks (CRNs). In the first part of the thesis, we analyze both cooperative sensing and channel accessing in a CRN with multiple primary users (PUs) and multiple secondary users (SUs). We first propose a cooperative spectrum sensing and accessing (CSSA) scheme for all the SUs. We then formulate the multi-channel spectrum sensing and channel accessing problem as a hedonic coalition formation game. The value function of each coalition takes into account both the sensing accuracy and energy consumption. In order to implement our CSSA scheme, we propose an algorithm for decision node selection. Also, we propose an algorithm based on the switch rule for the SUs to make distributed decisions on whether to join or leave a coalition. We prove analytically that all the SUs will converge to a final network partition, which is both Nash-stable and individually stable. Besides, the proposed distributed algorithms can adapt the Nash-stable partition to environmental changes. Simulation results show that our CSSA scheme achieves a better performance than the noncooperative spectrum sensing and accessing (NSSA) scheme in terms of the average utility of SUs. In the second part of the thesis, we analyze the cooperative transmission in CRNs, where SU can be selected as the cooperative relay to assist PU’s transmission. In order to improve the performance, the PU needs to select the secondary relay and allocate time resources for cooperative transmission. Then, the SUs need to determine their strategies of random access. We first establish a model for cooperative cognitive radio networks. We then propose a cooperative transmission and random access (CTRA) scheme. Based on the sequential structure of the decision-making, we study the cooperative cognitive radio network and determine the equilibrium strategies for both the PU and SUs using the Stackelberg game. Simulation results show that both the PU and SUs achieve better performance compared with the noncooperative transmission and random access (NTRA) scheme. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Collection |
Electronic Theses and Dissertations (ETDs) 2008+ |
Date Available | 2011-08-22 |
Provider | Vancouver : University of British Columbia Library |
DOI | 10.14288/1.0105026 |
URI | http://hdl.handle.net/2429/36840 |
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 | 2011-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | DSpace |
Download
- Media
- ubc_2011_fall_hao_xiaolei.pdf [ 579.09kB ]
- Metadata
- JSON: 1.0105026.json
- JSON-LD: 1.0105026+ld.json
- RDF/XML (Pretty): 1.0105026.xml
- RDF/JSON: 1.0105026+rdf.json
- Turtle: 1.0105026+rdf-turtle.txt
- N-Triples: 1.0105026+rdf-ntriples.txt
- Original Record: 1.0105026 +original-record.json
- Full Text
- 1.0105026.txt
- Citation
- 1.0105026.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Country | Views | Downloads |
---|---|---|
United States | 10 | 5 |
Canada | 8 | 0 |
India | 8 | 2 |
China | 5 | 10 |
France | 3 | 0 |
Germany | 3 | 6 |
Sweden | 3 | 0 |
Vietnam | 2 | 0 |
Japan | 2 | 0 |
Indonesia | 1 | 0 |
City | Views | Downloads |
---|---|---|
Ashburn | 9 | 0 |
Unknown | 9 | 9 |
Shenzhen | 5 | 10 |
Vancouver | 3 | 0 |
Saint-Quentin | 3 | 0 |
Puducherry | 3 | 2 |
Stockholm | 3 | 0 |
Tokyo | 2 | 0 |
Québec | 2 | 0 |
Hanoi | 2 | 0 |
Mumbai | 2 | 0 |
Seattle | 1 | 0 |
Patna | 1 | 0 |
{[{ mDataHeader[type] }]} | {[{ month[type] }]} | {[{ tData[type] }]} |
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-0105026/manifest