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, 2011 ii Abstract The concept of cognitive radio aims to increase the eﬃciency 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 ﬁrst 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 ﬁrst 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 ﬁnal 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 Abstract 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 ﬁrst 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 Cheung, Vincent W.S. Wong, and Victor C.M. Leung, “A coalition formation game for energy-eﬃcient 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 cooperative 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 random 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 . . . 9 Table 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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 Table of Contents Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii 74 viii 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 P U1 , and ST3 and ST4 sense the licensed channel of P U2 . . . . . . . . . . . . . . . 2.2 15 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. . . . . . . . . . . . . . . . 2.3 18 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). . . 43 List of Figures 2.8 The average utility of the SUs versus the probability for PUs being active PH1 (M = 5, N = 10). . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.9 ix 44 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). . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1 46 Primary transmission in sub-slot 1 of the proposed CTRA scheme. The primary transmitter P T chooses secondary transmitter ST1 as its cooperative relay and transmits the primary data to both the secondary relay ST1 and the destination P R. . . . . . . . . . . . . . . . . . . . . . . . . . 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. . . . . . . 3.3 52 53 Secondary transmission in sub-slot 3 of the proposed CTRA scheme. The SUs attempt to access the licensed frequency band of P T in a random access manner. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 3.4 Simulation model with one PU and ﬁve SUs. . . . . . . . . . . . . . . . . 64 3.5 The utility of the PU versus the number of SUs N (ωP = 1, ωS = 0.1, cnon = 18). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6 65 The utility of the PU versus the maximum accessing price cnon (ωP = 1, ωS = 0.1, N = 5). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 List of Figures 3.7 x The average utility of the SUs versus the maximum accessing price cnon (ωP = 1, ωS = 0.8, N = 5). . . . . . . . . . . . . . . . . . . . . . . . . . . 67 xi 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 Keying List of Acronyms 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 Utility xii xiii Acknowledgements I owe my deepest gratitude to my reserach supervisors, Dr. Vincent Wong and Dr. Victor Leung, whose encouragement, guidance and support from the initial to the ﬁnal 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 oﬀer 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 ﬁrst 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 increasing in recent years. According to the report released by the Federal Communications Commission [1], ﬁxed spectrum allocation may not always be eﬃcient 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 eﬃciency of spectrum usage can be increased. The CRNs are composed of diﬀerent PUs and SUs. The licensed spectrum is assigned to PUs, and the SUs seek to exploit possible transmission opportunities in the licensed Chapter 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 oﬀset 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 spectrum 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 considered 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 energy Chapter 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 spectrum 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, eﬃcient dynamic spectrum allocation and sharing schemes are also important to achieve high spectrum eﬃciency 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 eﬃciency, 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 ﬁnd the licensed spectrum which is not occupied by the PUs in order to enable dynamic spectrum access in Chapter 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 eﬀective 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 eﬃciency are crucial. The combined decision made by the SUs which perform cooperative spectrum 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 eﬃciency 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 and Chapter 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 ﬁrst 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 interference Chapter 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 suﬀers 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 traﬃc. 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, eﬃcient dynamic spectrum allocation and sharing schemes are also important to achieve high spectrum eﬃciency in CRNs. In the ﬁrst 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. Even Chapter 1. Introduction 7 though both parts of our work use cooperative techniques to enhance the performance of CRNs, they focus on two diﬀerent main functions of cognitive radio: spectrum sensing 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 transmission 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 radio 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-eﬃcient cooperative spectrum sensing in cognitive 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 ﬁrst, 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 ﬁrst 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 cooperative spectrum sensing and accessing (CSSA) scheme. We state the motivations and contributions at ﬁrst, 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. 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 signiﬁcantly if cooperative spectrum sensing is used [21, 22]. In [23], Liang et al. formulated the sensing-throughput tradeoﬀ problem as an optimization problem and proved that there exists an optimal sensing time which yields Chapter 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 tradeoﬀ methodology. 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 cooperative 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 cooperative spectrum sensing method, and investigated how the cooperative sensing aﬀects 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 theoretical improvement made by multi-channel coordination in cooperative spectrum sensing, and proposed practical centralized algorithm and distributed algorithms to ﬁnd 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 usage Chapter 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 ﬁrst 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 which Chapter 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 ﬁrst 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 problem 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 can Chapter 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 noncooperative 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 eﬃciency 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 the Chapter 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 traﬃc requirement is imposed on the STs. In other words, STj transmits data in a best-eﬀort 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 P U2 . 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 1 The duration of the sensing subframe δ is less than 15 ms when the duration of each frame is T = 100 ms [23, 35]. 2 During 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 diﬀerent characteristics, which will cause the violation of interference limit [25]. Furthermore, it requires a high-speed analog-todigital (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 P Ui , i ∈ M is active and inactive, respectively. For j ∈ N , STj performs spectrum sensing in the licensed frequency band of P Ui , ∀ i ∈ M and determines the probabilities of detection and false alarm. The probability 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 2 . Given the identically distributed (iid) random process with zero mean and variance σn,i 2 power spectral density N0 , we have σn,i = N0 Bi . The primary signal of P Ui is an iid 2 . The primary signal is independent random process with zero mean and variance σs,i 2 2 /σn,i as the received of other primary signals and the noise. We denote γi,j = |gi,j |2 σs,i Chapter 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 (ε, δ, 2 σn,i ) = P r(yj,i > ε | H0,i ) = Q ε −1 δfs , 2 σn,i (2.1) where yj,i is the test statistic for energy detector of STj in channel i, and Q is the 2 ) is complementary distribution function of the standard Gaussian. Since Pf,i,j (ε, δ, σn,i deﬁned 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 2 ) are the same for ∀ i ∈ M, ∀ j ∈ N . Besides, bandwidth Bi for all PUs, Pf,i,j (ε, δ, σn,i under hypothesis H1,i , the probability of detection in channel i ∈ M by STj , j ∈ N is δf ε s 2 . (2.2) , γi,j ) = P r(yj,i > ε | H1,i ) = Q − γi,j − 1 Pd,i,j (ε, δ, σn,i 2 σn,i 2γi,j + 1 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 ﬁrst 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 P U1 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 ﬁnal spectrum sensing decision for the licensed channel i ∈ M. We assume that DN decides on the channel status based on a decision fusion rule Chapter 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 2 1 − Pf,i,j (ε, δ, σn,i ) , (2.3) 2 1 − Pd,i,j (ε, δ, σn,i , γi,j ) . (2.4) Pf,i = 1 − j∈Si Pd,i = 1 − j∈Si For the licensed frequency band i ∈ M, we denote PH1,i as the probability that P Ui is active, and PH0,i as the probability that P Ui 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 and Chapter 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 idle 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 P U2 (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 P Ui is actually active, the secondary data transmission in channel i will not be successful because it interferes with the P Ui ’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 to Chapter 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 diﬀerent 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 ﬁrst, 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 2.3.1 22 Value Function and Utility Function Since the SUs try to exploit the possible transmission opportunities in the licensed frequency 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 diﬀerent scenarios related to the activity of the P Ui and the decision of DNi . We present the equivalent data utility, energy consumption, and the probability that each scenario occurs as follows: Scenario 1: P Ui 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 2 noise power σn,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 Pt 1 + |hj,i | 2 σn,i 2 . (2.5) In this scenario, the equivalent data utility of set Si is deﬁned as the expected value Chapter 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 ) = Rj,i (T − δ). |Si | j∈Si (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 ﬁrst 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,i Pf,i . (2.11) Chapter 2. Hedonic Coalition Formation Game for CSSA Scheme in CRNs 24 Scenario 3: P Ui 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 P Ui ’s transmission. 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 transmission. 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: P Ui 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,i Pd,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 1 Rj,i 1 vD (Si ) = Pa|b,i va|b,D (Si ) = P0|0,i a=0 b=0 j∈Si |Si | (T − δ) − P0|1,i D0 (T − δ). (2.18) The expected value of the energy consumption in set Si in each frame of duration T is 1 1 Pa|b,i va|b,E (Si ) = Ps |Si |δ + (P0|0,i + P0|1,i )Pt (T − δ). vE (Si ) = (2.19) a=0 b=0 We deﬁne the value function of set Si as follows, which takes both the sensing accuracy and energy consumption into account: P0|0,i Rj,i (T − δ) − |Si |P0|1,i D0 (T − δ) vD (Si ) j∈Si = . v(Si ) = vE (Si ) |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 eﬃciency 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 xSj i = 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 deﬁned in (2.21). 2.3.2 Hedonic Coalition Formation Analysis Given the value function of set Si deﬁned in (2.20) and the utility function of each SU deﬁned 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). • Payoﬀs (or utilities): The payoﬀ of each SU depends on which coalition it belongs to, and it is deﬁned in (2.21) (i.e., the payoﬀ of STj in coalition Si is xSj i ). 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 transmission 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) can Chapter 2. Hedonic Coalition Formation Game for CSSA Scheme in CRNs 27 be equally apportioned between the coalition members, it justiﬁes the transferable utility (TU) [33] nature of the coalitional game. Moreover, we will show that the coalition formation game is classiﬁed as hedonic [41]. Before presenting its deﬁnition, we ﬁrst introduce some basic deﬁnitions which are commonly used in the coalition formation games. Deﬁnition 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 . Deﬁnition 2 For any player j ∈ N , a preference relation j is deﬁned as a complete, irreﬂexive 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 deﬁnition is used to compare diﬀerent 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 deﬁne the Chapter 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 deﬁned as ⎧ ⎪ ⎪ ⎪ ⎨−∞, if Si ∈ h(j), Uj (Si ) = ⎪ ⎪ ⎪ ⎩xSj i , (2.23) otherwise. xSj i 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 deﬁnition of history set will be presented later. According to the preference function deﬁned in (2.23), the preference over diﬀerent coalitions for STj , ∀ j ∈ N is related to its utility function deﬁned 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 deﬁned as follows: Deﬁnition 3 A hedonic coalition formation game is a coalitional game that satisﬁes 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 deﬁned by the pair (N , ) where N is the set of players and proﬁle of preferences deﬁned for every player in N . is a 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 satisﬁes the ﬁrst 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 satisﬁes the second hedonic condition. Since our formulated problem satisﬁes the above two conditions in Deﬁnition 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 deﬁnitions 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. Deﬁnition 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 over Chapter 2. Hedonic Coalition Formation Game for CSSA Scheme in CRNs 30 the current coalition. Therefore, the switch rule can be viewed as a selﬁsh decision made by a player to move from its current coalition to a new coalition, regardless of the eﬀect 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 deﬁne the initial partition of the hedonic coalition formation game as S (0) = (0) (0) (r) (r) {S1 , . . . , SM }, and the partition at the rth time frame as S (r) = {S1 , . . . , SM }. 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 deﬁnition of history set h(j) of STj , which appeared in (2.23). (0) (r−1) Deﬁnition 5 At the rth time frame, the history set h(j) for STj , ∀ j ∈ N is {Si0 , . . . , Sir−1 }. (z) For any time frame index z ∈ {0, 1, . . . , r − 1}, we have iz ∈ M and j ∈ Siz . At the end (r) of the rth time frame, STj will update its history set h(j) by putting a new element Sir (r) (ir ∈ M and j ∈ Sir ) at the end of h(j). Proposition 1 If STj performs the switch rule in the rth time frame (i.e., leaves its (r−1) previous coalition Si (denoted as Sir−1 ) and joins another coalition Sl where i = l), the newly formed coalition Sl (r) {j} (denoted as Sir ) 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 (r) (z) 31 (z) Proof : Suppose Sir is the same with Siz , where z ∈ {0, 1, . . . , r−1} and Siz ∈ h(j). S (r) S (z) Then, we can have xj ir = xj iz according to (2.21). However, according to the deﬁnition of the switch rule, STj will perform the switch rule if and only if the new coalition is S (r) S (z) strictly preferred by STj over the previous coalition. Therefore, we have xj ir > xj iz , (r) which contradicts with our assumption. Thus, the newly formed coalition Sir cannot be (z) the same with any of the previous coalitions Siz in the history set h(j). Next, we will prove that there exists a stable partition in our hedonic coalition formation game. Before presenting the proof, we ﬁrst deﬁne two types of stable partitions. Deﬁnition 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. Deﬁnition 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 ∗ }, which is both Nash-stable and individually stable. a ﬁnal partition S ∗ = {S1∗ , . . . , SM 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 sequence Chapter 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 Deﬁnition 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 diﬀerent partitions is M N , which is a ﬁnite number [43]. Thus, from any S (0) , given enough time, the switch operations will always terminate at a point after a ﬁnite number of iterations, where the system converges to a ﬁnal partition S ∗ . Suppose S ∗ is not Nash-stable. According to Deﬁnition 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 ﬁnal partition, which contradicts with our assumption. Thus, the ﬁnal 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 ﬁnal 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 2.4 33 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 ﬁrst ﬁnd 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 (0) initial partition to all the SUs. The initial partition is set as S1 (0) = N and Sl = ∅, ∀ l ∈ M\{1}. In stage two, all the SUs will perform the switch operations until the CRN converge to a ﬁnal Nash-stable partition S ∗ . The stage two is composed of a total number of M AX iterations. Since the number of licensed channels M and the number of SUs N are both ﬁnite, if the number of iterations M AX is large, the CRN can always converge to a ﬁnal 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 ﬁnal Nash-stable partition S ∗ , the SUs will stay in Chapter 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 M AX do (r) 2: STj broadcasts its SNR information γi,j to other secondary transmitters STk , ∀ k ∈ (r) Si \{j} (r) (r) 3: STj receives the SNR information γi,k from other STk , ∀ k ∈ Si \{j} (r) (r) q := arg maxp γi,p , ∀ p ∈ Si (r) 5: DNi := STq 6: end for 4: their current coalitions in S ∗ to sense and access the licensed channels according to our proposed CSSA scheme. We ﬁrst 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 deﬁned 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. (r) In the rth iteration, Algorithm 1 is executed by STj , ∀ j ∈ Si in order to select DNi for channel i ∈ M. Since STj determines which licensed channel to sense and access (r) in each frame, therefore STj knows the value of i. In order to select DNi (r) iteration, all SUs in the coalition Si in the rth have to exchange their SNR information. STj Chapter 2. Hedonic Coalition Formation Game for CSSA Scheme in CRNs 35 (r) will broadcast its SNR information γ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 (r) the SNR information of other SUs, and the SU with the highest SNR is chosen as DNi (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 2 , γi,j ) is an as DNi in coalition Si . Therefore, we just need to prove that Pd,i,j (ε, δ, σn,i increasing function of γi,j . We deﬁne 2 g(ε, δ, σn,i , γi,j ) = ε − γi,j − 1 2 σn,i δfs , 2γi,j + 1 (2.24) 2 , γi,j ) with respect to γi,j , which is and take the ﬁrst order derivative of Pd,i,j (ε, δ, σn,i given by 2 2 ∂Pd,i,j (ε, δ, σn,i , γi,j ) , γi,j ) ∂Q g(ε, δ, σn,i =− 2 ∂γi,j ∂g(ε, δ, σn,i , γi,j ) √ δfs (γi,j + ε 2 ) σn,i (2γi,j + 1)1.5 . (2.25) 2 2 , γi,j ) is an decreasing function of g(ε, δ, σn,i , γi,j ), we have Since Q g(ε, δ, σn,i 2 ∂Q(g(ε, δ, σn,i , γi,j )) < 0. 2 ∂g(ε, δ, σn,i , γi,j ) (2.26) 2 are all positive. Therefore, the ﬁrst order derivative in (2.25) is Besides, γi,j , ε and σn,i 2 , γi,j ) is an increasing function of γi,j . always positive, and Pd,i,j (ε, δ, σn,i 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. (0) (0) 1: Initialization: S1 := N ; Sl := ∅, ∀ l ∈ M\{1} 2: for iteration r := 1 to M AX do (r) (r−1) (r) 3: Si := Si , where i ∈ M and j ∈ Si 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 := arg maxw θw , ∀ w ∈ N 9: if STj = STm then 10: 11: 12: 13: 14: 15: 16: 17: 18: S S αj STj computes xj (r) 19: 20: 21: 22: 23: 24: 25: 26: (r) (r) (r) STj computes xj i := v(Si )/|Si | (r) (r) Si := Si \{j} (r) (r) STj requests and obtains the information of Sαj from DNαj (r) (r) Sαj := Sαj {j} (r) if Sαj ∈ h(j) then (r) (r) Sαj := Sαj \{j} (r) (r) Si := Si {j} else (r) Sα S (r) (r) := v(Sαj )/|Sαj | (r) if xj j ≤ xj i then (r) (r) Sαj := Sαj \{j} (r) (r) {j} Si := Si end if end if end if (r) STj adds Si to the end of its history set h(j) 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 is Chapter 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 (r) Si (r) and joining another coalition Sα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 (r) not only try to move from its current coalition Si (r) to another coalition Sαj , but have to check whether the new coalition is strictly preferred over the current coalition as well. S (r) First, STj computes its utility function xj i (r) Si as being a member of its current coalition (r) (line 10), and leaves its current coalition Si (r) (line 11). Then, STj sends DNαj a (r) request in order to obtain the coalition information of Sαj (line 12), and adds itself as (r) a new member of coalition Sαj (line 13). After updating the current partition, STj will (r) (r) check whether the new coalition Sαj is strictly preferred over the previous coalition Si . (r) This check consists of two steps. First, STj will check whether the new coalition Sαj (r) has already appeared in its history set h(j) (line 14). If Sα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 inﬁnity according to (2.23), and the switch operation of STj in this iteration is not valid according to the deﬁnition of the switch rule. Therefore, Chapter 2. Hedonic Coalition Formation Game for CSSA Scheme in CRNs (r) (r) STj should leave the coalition Sαj (line 15) and move back to coalition Si 38 (line 16). (r) Second, if the new coalition Sαj is not in the history set h(j), STj will computes its (r) utility function (r) S αj Sα xj j (r) as being a member of the new coalition Sαj (line 18). If the utility S (r) (r) is greater than xj i , which means the new coalition Sαj is strictly preferred over xj (r) the previous coalition Si , the switch operation of STj in this iteration is successful. (r) Otherwise, STj still have to leave the coalition Sαj (line 20) and move back to coalition (r) Si (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 ﬁnd the new Nashstable 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 ﬁrst present the results for the convergence of our proposed distributed 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 diﬀerent system parameters. In the simulation, we consider that there are one AP, ﬁve PUs Chapter 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 P Ui 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 2 mW/Hz, therefore, the noise power σn,i is 0.1 mW for all i ∈ M. The probability that P Ui , 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 U1 Chapter 2. Hedonic Coalition Formation Game for CSSA Scheme in CRNs 40 100 90 80 SR 2 SR 1 70 S2 ST 3 y 60 50 ST 2 40 P U1 30 20 AP S1 P U2 SR 4 ST 1 ST 4 SR 3 10 0 0 20 40 x 60 80 100 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 P U1 is higher than those of P U2 , 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 a Chapter 2. Hedonic Coalition Formation Game for CSSA Scheme in CRNs 8 CSSA NSSA 7 Average utility of SUs 41 6 5 4 3 2 1 0 1000 2000 3000 r 4000 5000 6000 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 ﬁrst 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 diﬀerent licensed channel. Since there is only one SU in one licensed channel, the Chapter 2. Hedonic Coalition Formation Game for CSSA Scheme in CRNs 42 12 CSSA NSSA Average utility of SUs 10 8 6 4 2 0 2 4 6 8 10 M 12 14 16 18 20 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 diﬀerent 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 the Chapter 2. Hedonic Coalition Formation Game for CSSA Scheme in CRNs 10 CSSA NSSA 9 Average utility of SUs 43 8 7 6 5 4 3 2 1 0 5 10 20 30 40 50 N 60 70 80 90 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 ﬁxed, 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 ﬁrst 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 signiﬁcantly by applying cooperative spectrum sensing. However, when Chapter 2. Hedonic Coalition Formation Game for CSSA Scheme in CRNs 10 CSSA NSSA 9 Average utility of SUs 44 8 7 6 5 4 3 2 1 0.2 0.3 0.4 0.5 P H1 0.6 0.7 0.8 0.9 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 signiﬁcant. 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 sensing Chapter 2. Hedonic Coalition Formation Game for CSSA Scheme in CRNs 7 CSSA NSSA 6.5 Average utility of SUs 45 6 5.5 5 4.5 4 3.5 3 2.5 20 50 100 150 D0 200 250 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 signiﬁcant. When the PUs has a higher traﬃc 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 of Chapter 2. Hedonic Coalition Formation Game for CSSA Scheme in CRNs 7 CSSA NSSA 6 Average utility of SUs 46 5 4 3 2 1 0 10 20 30 40 50 δ (ms) 60 70 80 90 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 signiﬁcant as NSSA when D0 is increased. In Fig. 2.10, we show the average utility of the SUs obtained by the proposed algorithms versus the sensing duration δ. Our results show that the CSSA performs better than the NSSA. Besides, we can see that there is a tradeoﬀ between spectrum sensing and channel accessing. For both the CSSA and the NSSA schemes, the average utility of the SUs ﬁrst 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 2.6 47 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 ﬁnd 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 Nashstable 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 eﬃciency. In this chapter, we present a Stackelberg game for cooperative transmission and random access in CRNs. We ﬁrst 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 a Chapter 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 eﬃciency. 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 opportunities 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, the Chapter 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 ﬁnd 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 beneﬁcial 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 beneﬁcial 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-eﬀort 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 P T is divided into time slots of duration T , and the CTRA Chapter 3. Stackelberg Game for CTRA Scheme in CRNs 52 Figure 3.1: Primary transmission in sub-slot 1 of the proposed CTRA scheme. The primary transmitter P T chooses secondary transmitter ST1 as its cooperative relay and transmits the primary data to both the secondary relay ST1 and the destination P R. scheme is performed in each time slot. As for the CTRA scheme, the primary transmitter P T 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 P T 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 during Chapter 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 ﬁrst 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 cooperative relay, the ﬁrst 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 ﬁrst sub-slot is of duration αt and is dedicated to the transmission from the primary transmitter P T 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 P R, which is shown Chapter 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 P T in a random access manner. in Fig. 3.2. If the primary transmitter P T 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 P T to P R. We denote the second portion with duration T − t as the third sub-slot of P T , 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 diﬀerent 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 deﬁne 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 δ2 δ p(δ) = 2 exp − 2 . σ 2σ (3.2) The following notations are used to denote the complex channel gain of diﬀerent links in each block: hP denotes the channel gain between the primary transmitter P T and the primary receiver P R; hP Sj denotes the channel gain between the primary transmitter P T and the secondary transmitter STj ; hSj P 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 ﬁxed 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 ; RSj P denotes the transmission 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 P T under cooperative transmission with secondary relay STj , where j = 1, 2, . . . , N , is given by Rcoop,j = 1 min{B log2 1 + |hP Sj |2 ΓP , B log2 1 + |hP |2 ΓP + |hSj P |2 ΓS }. 2 (3.4) In (3.4), the ﬁrst 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 3.3 57 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 beneﬁcial to use cooperative transmission and which secondary transmitter should be chosen as the cooperative relay. P T 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 transmitter 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, P T 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 P T chooses no cooperative relay and therefore α = 1. Otherwise, P T chooses STr as its cooperative relay and α = 0.5. For the second strategy, P T determines how to allocate time resources and Chapter 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 simultaneously. 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 corresponds to the transmission probability of STi during the third sub-slot. In order to ﬁnd the Nash equilibrium of this Stackelberg game, backward induction is used. We start by ﬁnding the equilibrium strategies of N SUs given the PU’s decisions on its strategies r, t and α. Then, taking these actions as given, we ﬁnd 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 T −t . n= Δ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, the Chapter 3. Stackelberg Game for CTRA Scheme in CRNs 59 utility function of secondary transmitter STi is deﬁned as USi (p, r) = n Psuc,i (p)Udi − pi Uci (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 P T 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 deﬁned as Udi = ωS RSi Δ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 (1 − pj ). Psuc,i (p) = pi (3.8) j=i If the secondary transmitter STi attempts to access the licensed channel of P T with probability pi , it should make a payment to the primary transmitter P T with probability pi . We deﬁne 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 the Chapter 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 deﬁne the maximum accessing price cmax,i (r) as a function of the secondary relay selection r, which is given by ⎧ ⎪ ⎪ ⎪ ⎨ccoop , if r = i, cmax,i (r) = ⎪ ⎪ ⎪ ⎩cnon , (3.10) if r = i, 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 diﬀerentiate the secondary accessing price. By substituting (3.7)−(3.9) into (3.6), the utility of secondary user STi is given by (1 − pj ) − cmax,i (r)p2i USi (p, r) = nΔt ωS RSi pi . (3.11) j=i 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 satisﬁed. First, the strategy set is nonempty, convex and compact. Second, USi (p, r) is continuous in p and concave in pi . The ﬁrst condition is satisﬁed 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 ﬁrst Chapter 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) = nΔt ωS RSi ∂pi (1 − pj ) − 2cmax,i (r)pi . (3.12) j=i ∂ 2 USi (p, r) = −2nΔtcmax,i (r). ∂pi 2 (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 ﬁnd 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 ﬁnd 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 ﬁrst 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 deﬁne the utility function of P T to be T −t UP (p, r, t) = ωP R(r)t + Δt N pi Uci (pi , r), i=1 (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 deﬁned as ⎧ ⎪ ⎪ ⎪ ⎨R P , if r = 0, R(r) = ⎪ ⎪ ⎪ ⎩Rcoop,j , if r = j where j = 1, 2, . . . , N. (3.15) In order to maximize UP , the PU ﬁrst chooses the value of r, and ﬁnd 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 ﬁnite 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) 0 < trem < Δt, (3.17) Since 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 the Chapter 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 ﬁnite set {Δt, 2Δt, . . . , T }. Based on the results of the secondary users’ game, we can ﬁnd the optimal strategies for the PU according to (3.14) and Proposition 3. The primary transmitter P T ﬁrst 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 ﬁnite 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 transmitter P T and the primary receiver P R is equal to 10 m. The positions of the SUs are Chapter 3. Stackelberg Game for CTRA Scheme in CRNs 64 Figure 3.4: Simulation model with one PU and ﬁve 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 ﬁxed 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 65 CTRA NTRA Utility of primary user 60 55 50 45 40 35 30 2 3 4 5 6 N 7 8 9 10 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 75 CTRA NTRA Utility of primary user 70 65 60 55 50 45 40 35 30 3 5 10 15 cnon 20 25 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 noncooperative 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 cnon Chapter 3. Stackelberg Game for CTRA Scheme in CRNs 67 Average utility of secondary users 35 CTRA NTRA 30 25 20 15 10 5 0 3 5 10 15 cnon 20 25 Figure 3.7: The average utility of the SUs versus the maximum accessing price cnon (ωP = 1, ωS = 0.8, N = 5). signiﬁcantly. 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 3.5 68 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 deﬁned 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 contributions. 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 transmission 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 behaviour 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 ignore the channel accessing of the SUs, we considered both cooperative spectrum sensing Chapter 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 eﬃciency 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 described the implementation details (i.e., proposed distributed algorithms) for our CSSA scheme. We formulated the multi-channel spectrum sensing and channel accessing problem 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 proposed 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 ﬁnal network partition, which is both Nash-stable and individually stable. Besides, the proposed distributed algorithms can adapt the Nash-stable partition 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 beneﬁcial 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 cooperative 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 sensing Chapter 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 tradeoﬀ 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 diﬀerent 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 diﬀerent 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 there Chapter 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. Marić, 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 separation 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 Communications, 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 tradeoﬀ 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 coordination 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-eﬃcient spectrum sensing for cognitive radio networks,” 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, Paciﬁc 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 cognitive 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 Communications, 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 Communications, 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 communicationaware 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: Eﬃcient 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 Computational Science and Its Applications (ICCSA), Perugia, Italy, June 2008.
You may notice some images loading slow across the Open Collections website. Thank you for your patience as we rebuild the cache to make images load faster.
- 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
pdf
Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
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 Issued | 2011 |
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 |
Date Available | 2011-08-22 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivatives 4.0 International |
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 |
GraduationDate | 2011-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/4.0/ |
AggregatedSourceRepository | DSpace |
Download
- Media
- 24-ubc_2011_fall_hao_xiaolei.pdf [ 579.09kB ]
- Metadata
- JSON: 24-1.0105026.json
- JSON-LD: 24-1.0105026-ld.json
- RDF/XML (Pretty): 24-1.0105026-rdf.xml
- RDF/JSON: 24-1.0105026-rdf.json
- Turtle: 24-1.0105026-turtle.txt
- N-Triples: 24-1.0105026-rdf-ntriples.txt
- Original Record: 24-1.0105026-source.json
- Full Text
- 24-1.0105026-fulltext.txt
- Citation
- 24-1.0105026.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
data-media="{[{embed.selectedMedia}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.24.1-0105026/manifest