Demand-aware traffic cooperation for self-organizing cognitive small-cell networks

Abstract

This article investigates the problem of efficient spectrum access for traffic demands of self-organizing cognitive small-cell networks, using the coalitional game approach. In particular, we propose a novel spectrum and time two-dimensional Traffic Cooperation Coalitional Game model which aims to improve the network throughput. The main motivation is to complete the data traffics of users, and the main idea is to make use of spectrum resource efficiently by reducing mutual interference in the spectrum dimension and considering cooperative data transmission in the time dimension at the same time. With the approach of coalition formation, compared with the traditional binary order in most existing coalition formation algorithms, the proposed functional order indicates a more flexibly preferring action which is a functional value determined by the environment information. To solve the distributed self-organizing traffic cooperation coalition formation problem, we propose three coalition formation algorithms: the first one is the Binary Preferring Traffic Cooperation Coalition Formation Algorithm based on the traditional Binary Preferring order; the second one is the Best Selection Traffic Cooperation Coalition Formation Algorithm based on the functional Best Selection order to improve the converging speed; and the third one is the Probabilistic Decision Traffic Cooperation Coalition Formation Algorithm based on the functional Probabilistic Decision order to improve the performance of the formed coalition. The proposed three algorithms are proved to converge to Nash-stable coalition structure. Simulation results verify the theoretic analysis and the proposed approaches.

Introduction

The evolving 5G networks are expected to be composed of heterogeneous small cells^1–6 (SCs; e.g. femtocells, picocells, and microcells), which have been seen as one of the most promising solutions for boosting the capacity and coverage of wireless networks by spatial reuse of frequency spectrum. SCs serve as offloading spots in the radio access network to offload users (OUs) and their associated traffic from congested macrocells. The SCs are expected to have certain degree of intelligence which can also be defined as cognition. In particular, cognition via spectrum sensing is foreseen as a potential solution for high-efficient spectrum access, which is the technology called cognitive radio.^1,3,5 Darsena et al. ⁷ made significant research on the broadband cognitive radio wireless sensor network operating in a crowded spectrum scenario. Cognitive small cell (CSC) can opportunistically use the free orthogonal channels via spectrum sensing, that is, CSC can opportunistically use the channel which is considered free if the power received on that channel is smaller than the spectrum sensing threshold.^8,9

For the dense and dynamical deployment of SCs, the centralized control in network management will be highly inefficient. Then, the importance of self-organization is highlighted, ¹⁰ and the key technical challenges are efficient distributed access management and distributed resource allocation.^11–15 Under the self-organization mechanism, CSCs can sense and learn from their environment, autonomously tune their strategies for access management toward an optimal performance. In this regard, game theory ¹⁶ is seen as a typical and important mathematical tool that analyzes strategic interactions among CSCs. On one hand, non-cooperative game models have been studied to solve the distributed access management between SCs in the literature,^17–23 where each SC focuses on its own utility while ignoring other SCs. On the other hand, the cooperation games, namely, coalitional games,^24–27 have also begun to draw attentions in the researches on distributed access management between SCs,^28–33 where SCs carry out cooperative access management through proper information exchange. In particular, considering the possible high-speed wired connection between SCs will make the cooperation cost very small, the cooperative access management scheme can obtain better performance. Saad et al. ²⁴ introduced the coalitional game theory into wireless communication networks and proposed many significant fruits of its applications in recently years.^2,33–37 With the user cooperation, authors proposed a selective-relay based cooperative spectrum sensing scheme in Zou et al., ³⁸ and investigated a selective-relay spectrum sensing and best relay data transmission scheme for multiple-relay cognitive radio networks in Zou et al. ³⁹ These works improved the performance of network significantly and also showed the importance of considering cooperation in the network.

Most existing works focus on the spectrum interference management to improve the network performance. However, the ultimate purpose of the access management is to complete the users’ data traffics, not only the interference control. Existing works have not paid enough attention to the users’ demand, that is, actual data traffics, and just assume that the traffics are all countless. In methodology, this assumption simplifies the system and facilitates the mathematical analysis and algorithm design, because the data traffic will have a great influence on the spectrum access decision. Actually, it is certainly not all users have countless packets to transmit all the time in practical scenarios, because the amount of data packets depends on the different applications, for example, video, message, audio, and picture. The traffics are usually limited and heterogeneous. As a result, considering the heterogeneous traffics, only interference management is not enough to obtain optimal performance, the traffic allocation optimization should also be taken into consideration.

With the existing coalitional game approaches on cooperative interference management,^24–29 to the best of our knowledge, most of them focus on the stability of the coalition formation algorithm. The coalition formation speed and the performance of the formed coalition have rarely been paid attention to. However, in wireless networks, only stability is not enough, the efficiency must be considered.

To sum up, the following two aspects are still remained to be solved: in the concept aspect, the two-dimensional optimization needs to be studied to obtain better performance: interference management in the spectrum dimension and traffic cooperation in the time dimension; in the approach aspect, the efficiency of coalition formation need to be studied: the coalition formation speed and the performance of the formed coalition. The challenge is that how to realize efficient and stable coalitions which obtain the two-dimensional optimization in a distributed manner, under the heterogeneous traffics condition.

In this article, we focus on the problem of efficient spectrum access for the CSCs’ traffics, using the coalitional game approach. We propose a spectrum and time two-dimensional Traffic Cooperation Coalitional Game model, and then propose the Binary Preferring Traffic Cooperation Coalition Formation (BPTCCF) Algorithm, the Best Selection Traffic Cooperation Coalition Formation (BSTCCF) Algorithm, and the Probabilistic Decision Traffic Cooperation Coalition Formation (PDTCCF) Algorithm based on the proposed functional-order definition to improve the speed and performance of coalition formation, respectively. The main contributions of this article are summarized as follows:

1. To obtain the efficient spectrum access for CSCs’ traffics, we propose a Traffic Cooperation Coalitional Game model. Compared with the most existing models, the proposed model considers the optimization of the traffic access in spectrum dimension and time dimension at the same time.

2. To obtain the flexibility and generality of coalition formation approach, we propose a functional-order definition in the coalition formation rule. Compared with the traditional binary order which indicates strictly preferring action, the proposed functional order is defined as a functional value determined by the environment information, which indicates a more flexibly preferring action.

3. To improve the speed of coalition formation, we propose BSTCCF Algorithm based on the proposed functional Best Selection order. Compared with the traditional randomly selection in most existing works, the proposed BSTCCF Algorithm can converge to Nash-stable coalition structure rapidly.

4. To improve the performance of the formed coalition, we propose PDTCCF Algorithm based on the proposed functional Probabilistic Decision order. Compared with the traditional binary preferring relation in most existing works, the proposed PDTCCF Algorithm can asymptotically converge to Nash-stable coalition structure with better performance.

The rest of this article is organized as follows: In section “Related work,” we review the related work. In section “System model and problem formulation,” we present the system model and problem formulation. In section “Traffic Cooperation Coalition Game,” we formulate the Traffic Cooperation Coalitional Game model. In section “Traffic Cooperation Coalition Formation Algorithms,” we propose the Traffic Cooperation Coalition Formation Algorithms. In section “Simulation results and discussion,” simulation results and discussion are presented. Finally, we provide conclusions in section “Conclusion.”

Related work

The distributed access management and resource allocation researches for SCs have begun to draw attention,^11–15 and the game theory ¹⁶ is seen as a typical and important mathematical tool that analyzes strategic interactions among CSCs. Non-cooperative game models have been studied to solve the distributed interference management between SCs in the literature.^17–23 Dynamic channel selection, frequency reuse, and power control have been studied for SC networks in the literature^11,17,18,19 In Ladanyi et al., ²⁰ the overall transmit power is minimized by a distributed algorithm. Chandrasekhar and Andrews ¹⁷ investigated the problem of joint throughput optimization, spectrum allocation, and access control. In Sun et al., ²² an auction algorithm was proposed to allocate the subcarriers between macrocell users and femtocell users. Adhikary and Caire ²³ investigated the potential of spatial multiplexing in non-cooperative two-tier networks.

The cooperation game models^24–33 have also begun to draw attention, where SCs carry out cooperative interference management through proper information exchange. Saad et al. ²⁴ introduced the concepts of cooperative game theory and the potential applications in communication and wireless networks. In Lee et al., ²⁸ a cooperative resource allocation algorithm was proposed to investigate the inter-cell fairness in OFDMA femtocell networks. In Urgaonkar and Neely, ²⁹ the femtocell users and macrocell users were allowed to cooperate. In Gharehshiran et al., ³⁰ a game-theoretic approach was proposed to deal with the resource allocation. In Soret et al., ³¹ the spectrum efficiency was improved by a collaborative carrier aggregation mechanism. In Pantisano et al. ³² a partition form cooperative game was proposed for femtocell spectrum sharing.

However, the following points need to be studied further: (1) the actual data traffic determined by practical applications should be taken into consideration, (2) the speed of the coalition formation should be considered, and (3) the performance improvement of formed coalition should be studied further.

Our work differs from existing works in the following key aspects: (1) compared with most existing works, users’ traffics are not countless, but limited and heterogeneous, and the proposed model is a spectrum and time two-dimensional Traffic Cooperation Coalitional Game model; (2) compared with most existing coalitional game approaches,^24–29 we not only pay attention to the stability of the coalition but also focus on the converging speed and the performance improvement of the coalition formation.

System model and problem formulation

System model

We consider a self-organizing CSC (types of SCs include picocells or femtocells that can be installed at home or at the office. ² ) network consisting of N channels and M CSCs. The CSCs work in the opportunistic spectrum access (OSA) manner, that is, CSCs can opportunistically use the Primary User (PU)-licensed channels which are considered free by spectrum sensing.^3,5 For example, in Figure 1, the channel 5 is occupied by PU, thus the CSCs can use channels 1–4. Collision happens if more than two CSCs use the same channel. We assume that CSCs adopt the parallel sensing strategy, ⁴⁰ that is, a CSC only decides to sense and access one channel in a slot (Figure 2).

Figure 1.

The system model.

Figure 2.

The illustrative diagram of traffic cooperation in multi CSCs.

Importantly, we consider the actual demands of CSCs, that is, heterogeneous multimedia traffics, compared to the countless data assumption in existing works. In Figure 1, the current applications of CSCs are different, and the amount of data traffic to transmit is not countless, but limited and heterogeneous. For example, the data amount of $\mathrm{CS}{\mathrm{C}}_1$ generated by Facebook will be obviously different with the data amount of $\mathrm{CS}{\mathrm{C}}_3$ generated by AVI.

There are four idle channels, but seven CSCs, and it is impossible to allocate each CSC one channel even under the ideal interference management in existing works, so the traffic cooperation should be considered to improve the performance furthermore. For example, $\mathrm{CS}{\mathrm{C}}_5$ , $\mathrm{CS}{\mathrm{C}}_6$ , and $\mathrm{CS}{\mathrm{C}}_7$ may form a coalition ${\mathrm{CO}}_3^4=\{\mathrm{CS}{\mathrm{C}}_5,\mathrm{CS}{\mathrm{C}}_6,\mathrm{CS}{\mathrm{C}}_7\}$ to share channel 4 to avoid the competing and collision, because their data amounts are usually small. Also, $\mathrm{CS}{\mathrm{C}}_1$ and $\mathrm{CS}{\mathrm{C}}_2$ could form coalition ${\mathrm{CO}}_1^1=\{\mathrm{CS}{\mathrm{C}}_1,\mathrm{CS}{\mathrm{C}}_2\}$ which works on channel 1. While $\mathrm{CS}{\mathrm{C}}_3$ and $\mathrm{CS}{\mathrm{C}}_4$ should occupy channel 2 and channel 3, respectively, because their data amount generated by FTP and AVI are usually large.

Figure 2 shows an illustrative diagram of time slot in the traffic cooperation spectrum access optimization problem. We assume that the transmission structure follows a synchronous, slotted frame with slot duration T (PU is either absent or present during each frame duration). ³ The slot time T is divided into sensing duration (several ${\tau }_s$ ), local information exchange duration ${\tau }_l$ , and data transmission time. In Figure 2, the CSCs’ actual transmission times depend on the packet queue generated by their applications and the channel capacities they access. For example, the transmission time of $\mathrm{CS}{\mathrm{C}}_1$ in this slot will be $L_1/C_1$ , where $L_1$ is the data amount (bit/s) of $\mathrm{CS}{\mathrm{C}}_1$ and $C_1$ is the channel capacity (bit/s) of channel 1. The proposed traffic cooperation scheme will improve the network performance. For example, if $\mathrm{CS}{\mathrm{C}}_1$ and $\mathrm{CS}{\mathrm{C}}_2$ sense the same channel 1 (this situation is inevitable since the number of CSCs is larger than the number of channels), they will collide in channel 1 and the throughput of both $\mathrm{CS}{\mathrm{C}}_1$ and $\mathrm{CS}{\mathrm{C}}_2$ will be zero, that is, the idle channel 1 will be wasted. However, in the proposed traffic cooperation scheme, $\mathrm{CS}{\mathrm{C}}_1$ and $\mathrm{CS}{\mathrm{C}}_2$ form a coalition and share channel 1 to avoid the collision and take fully use of channel 1. The transmission arrangement in a coalition can be designed as Network Allocation Vector (NAV) scheme in the 802.11 DCF, ³⁰ where each CSC announces a duration before transmission and others wait until the end of the announced duration. We define $S_{\mathrm{CH}}=\{1,2,\dots ,n,\dots ,N\}$ as the set of PU channels and define $S=\{1,2,\dots ,m,\dots ,M\}$ as the set of CSCs. Denote $\mathbf{C}=[C_1,C_2,\dots ,C_N]$ as the capacity vector of channel set $S_{\mathrm{CH}}$ , ${\mathit{P}}^0=[P_1^0,P_2^0,\dots ,P_N^0]$ as the idle probability vector of channel set $S_{\mathrm{CH}}$ , and $\mathbf{L}=[L_1,L_2,\dots ,L_M]$ as the traffic vector of set S. Denote $P=\{\{{\mathrm{CO}}_1^{n_1}\},\{{\mathrm{CO}}_2^{n_2}\},\dots ,\{{\mathrm{CO}}_l^{n_l}\}\}$ as the set of coalitions, where ${\mathrm{CO}}_k^{n_k}$ denotes the coalition k which works on channel $n_k$ . The illustrative diagram of the formed coalitions and the channel allocation is shown in Figure 3.

Figure 3.

The illustrative diagram of the formed coalitions and the channel allocation.

Problem formulation

The main motivation of this article is to optimize the throughput of CSCs’ traffics, so we discard the assumption that CSC has countless data packets to transmit all the time in existing works and focus on the actual throughput obtained by the traffic, which is defined by transmitted data in the actually time spend, that is, if $\mathrm{CS}{\mathrm{C}}_m$ in coalition ${\mathrm{CO}}_k^{n_k}$ transmits data on the idle channel $n_k$ , the obtained throughput of CSC _m ’s traffic in this slot is computed by

$$\begin{array}{c}\multicolumn{1}{c}{R_m=\frac{L\left(\mathrm{transmitted}\mathrm{data}\right)\mathrm{bit}}{t\left(\mathrm{total}\mathrm{time}\mathrm{spend}\right)\mathrm{s}}}\\ \multicolumn{1}{c}{=\{\begin{array}{c}\frac{L_m}{{\tau }_s+{\tau }_{\mathrm{bm}}+L_m/C_{n_k}},L_m<(T-{\tau }_{\mathrm{bm}}-{\tau }_s)C_{n_k}\hfill \\ \multicolumn{1}{c}{\frac{T-{\tau }_{\mathrm{bm}}-{\tau }_s}{T}{C}_{n_k},L_m\ge (T-{\tau }_{\mathrm{bm}}-{\tau }_s)C_{n_k}}\end{array}}\end{array}$$

(1)

where ${\tau }_{\mathrm{bm}}$ is the back-off time in a coalition, for example, in Figure 2, the back-off time of $\mathrm{CS}{\mathrm{C}}_2$ is ${\tau }_{\mathrm{bm}}=L_1/C_1$ , which is the data transmission time of $\mathrm{CS}{\mathrm{C}}_1$ .

The proposed traffic throughput definition is more practical because it is not that CSC has countless packets to transmit all the time in practical scenarios. Usually, in wireless network, the small data amount applications are commonplace, such as Facebook, HTML, QQ, and short message. In addition, the definition is more general by encompassing the large data amount situation as a special case, that is, $L_m\ge (T-{\tau }_{\mathrm{bm}}-{\tau }_s)C_{n_k}$ , which is traditional throughput definition in existing work under the countless data assumption.

In the self-organizing CSC network shown in Figure 1, there may be more than one CSCs in different coalitions attending to access the same channel, then a collision may occur under this situation. For $\mathrm{CS}{\mathrm{C}}_m\in {\mathrm{CO}}_k^{n_k}$ which works on channel $n_k$ , the data transmission on would be successful when the following requirements are met: first, PU is not active on channel $n_k$ ; second, there is no false alarm in channel $n_k$ detection by $\mathrm{CS}{\mathrm{C}}_m$ ; third, no other CSCs of the coalition attend to access this channel $n_k$ , that is, any CSC, for example, $h\in {\Psi }_m^{s_{\mathrm{mk}}}$ does not decide to sense channel $n_k$ , or there is a false alarm when sensing channel $n_k$ . Thus, the probability of successful transmission for $\mathrm{CS}{\mathrm{C}}_m$ on channel $n_k$ is given by

$$p_{s\mathrm{,}m}^{C{O}_k^{n_k}}=p_0^{n_k}\times \left(1-p_{f\mathrm{,}m}^{n_k}\right)\times {\displaystyle \prod _{h\in \left\{{\Psi }^{n_k}\backslash C{O}_k^{n_k}\right\}}}{p}_{f\mathrm{,}h}^{n_k}$$

(2)

where ${\Psi }^{n_k}$ is the set of CSCs which decide to sense channel $n_k$ , $p_{f,m}^{n_k}$ is the probability of false alarm when $\mathrm{CS}{\mathrm{C}}_m$ senses channel $n_k$ , and $p_0^{n_k}$ is the idle probability of channel $n_k$ .

In the coalition ${\mathrm{CO}}_k^{n_k}$ , the back-off time of $\mathrm{CS}{\mathrm{C}}_m$ is determined by the transmission time of other CSCs which transmit data before $\mathrm{CS}{\mathrm{C}}_m$ (we assume that the data transmission order in a coalition is the order which members join the coalition. The transmission mechanism could also be CSMA or ALOHA and so on. In this article, we focus on the coalition formulation, and the transmission mechanism is not the key point. So, we adopt the simple “first come, first serve” mechanism). Assume that coalition ${\mathrm{CO}}_k^{n_k}$ includes j members ${\mathrm{CO}}_k^{n_k}=\{\mathrm{CS}{C}_1,\dots ,\mathrm{CS}{C}_j\}$ , and $\mathrm{CS}{\mathrm{C}}_m$ is its ith member, then the CSC _m ’s back-off time will be

$${\tau }_{\mathrm{bm}}^{{\mathrm{CO}}_k^{n_k}}=\sum _{t=1}^{i-1}({\tau }_s+(1-p_{f,t}^{n_k})(L_t/C_{n_k}))$$

(3)

By combining equations (1)–(3), denoting ${\xi }_m^{{\mathrm{CO}}_k^{n_k}}=L_m/$ $C_n+{\tau }_s+{\tau }_{\mathrm{bm}}^{{\mathrm{CO}}_k^{n_k}}-T$ , $R_m^{C{O}_k^{n_k},1}=L_m/({\tau }_s+{\tau }_{bm}^{C{O}_k^{n_k}}+L_m/C_n)$ , and $R_m^{{\mathrm{CO}}_k^{n_k},2}=((T-{\tau }_{\mathrm{bm}}^{{\mathrm{CO}}_k^{n_k}}-{\tau }_s)/T)C_{n_k}$ for the simplification of presentation, the throughput of $\mathrm{CS}{\mathrm{C}}_m$ in coalition ${\mathrm{CO}}_k^{n_k}$ working on channel $n_k$ is given by equation (4)

$$\begin{array}{c}\multicolumn{1}{c}{R_m^{{\mathrm{CO}}_k^{n_k}}=p_{s,m}^{{\mathrm{CO}}_k^{n_k}}\times (\frac{1-\underset{({\xi }_m^{{\mathrm{CO}}_k^{n_k}})}{\mathrm{sgn}}}{2}{R}_m^{{\mathrm{CO}}_k^{n_k},1}+\frac{1+\underset{({\xi }_m^{{\mathrm{CO}}_k^{n_k}})}{\mathrm{sgn}}}{2}{R}_m^{{\mathrm{CO}}_k^{n_k},2})}\\ \multicolumn{1}{c}{=p_0^{n_k}\times (1-p_{f,m}^{n_k})\times \underset{h\in \{{\Psi }^{n_k}\backslash {\mathrm{CO}}_k^{n_k}\}}{\Pi }{p}_{f,h}^{n_k}}\\ \multicolumn{1}{c}{\times (\frac{1-\underset{({\xi }_m^{{\mathrm{CO}}_k^{n_k}})}{\mathrm{sgn}}}{2}{R}_m^{{\mathrm{CO}}_k^{n_k},1}+\frac{1+\underset{({\xi }_m^{{\mathrm{CO}}_k^{n_k}})}{\mathrm{sgn}}}{2}{R}_m^{{\mathrm{CO}}_k^{n_k},2})}\end{array}$$

(4)

where $\mathrm{sgn}(x)$ is a function which returns 1 if the x is greater than zero and −1 if it is less than zero.

It should be noted that the throughput is determined by the following main factors: the data amount of traffics, the coalition selection, the channel selection, and the other CSCs’ interference. For coalition ${\mathrm{CO}}_k^{n_k}$ , the coalition throughput is given by

$$R^{{\mathrm{CO}}_k^{n_k}}=\sum _{m\in {\mathrm{CO}}_k^{n_k}}{R}_m^{{\mathrm{CO}}_k^{n_k}}$$

(5)

In the perspective of global network, the network throughput is given by

$$R^{\mathrm{net}}=\sum _{m\in S}{R}_m^{{\mathrm{CO}}_k^{n_k}}$$

(6)

The goal is to find the stable coalition structure $P^{*}=\{\{{\mathrm{CO}}_1^{n_1}\},\{{\mathrm{CO}}_2^{n_2}\},\dots ,\{{\mathrm{CO}}_l^{n_l}\}\}$ , where $\forall i,j,{\mathrm{CO}}_i^{n_i}\subseteq S,{\mathrm{CO}}_j^{n_j}\subseteq S$ , ${\mathrm{CO}}_i^{n_i}\cap {\mathrm{CO}}_j^{n_j}=\varnothing$ , and ${\cup }_{i=1}^l{\mathrm{CO}}_i^{n_i}=S$ , to obtain high network performance. However, solving this problem in a centralized manner will lead to extremely high computing complex. The desired method is the one which can provide the stable solution in a distributed manner. In this article, based on coalitional game method, we propose a Traffic Cooperation Coalition Game model and design three coalition formation algorithms to solve this problem in a distributed manner.

Traffic Cooperation Coalition Game

In this section, we propose the Traffic Cooperation Coalition Game model to solve the problem of efficient spectrum access for traffics in distributed self-organization CSC networks.

Definition 1

Define the Traffic Cooperation Coalition Game as $G=(S,v,F,A,P)$ , where S is the set of CSC players, v is the utility function, F is the order function which determine the players’ preferring action, and $A=(a_1,a_2,\dots ,a_m,\dots ,a_M)$ is the action vector of players, that is, for player m, $a_m$ is its action based on the value of preference order function F: joining some coalition, leaving the current coalition, or holding on. P is the coalition structure, $P=\{\{{\mathrm{CO}}_1^{n_1}\},\{{\mathrm{CO}}_2^{n_2}\},\dots ,\{{\mathrm{CO}}_l^{n_l}\}\}$ , where $\forall i,j,{\mathrm{CO}}_i^{n_i}\subseteq S,{\mathrm{CO}}_j^{n_j}\subseteq S$ , ${\mathrm{CO}}_i^{n_i}\cap {\mathrm{CO}}_j^{n_j}=\varnothing$ , and ${\cup }_{i=1}^l{\mathrm{CO}}_i^{n_i}=S$ . Note that there are two main factors of each coalition: the members and the working channel.

Definition 2 (utility function)

For individual player m, we define the utility function as the throughput in coalition ${\mathrm{CO}}_k^{n_k}$ which works on channel $n_k$

$$v_m\left({\mathrm{CO}}_k^{n_k}\right)=R_m^{{\mathrm{CO}}_k^{n_k}}$$

(7)

Denote the current coalition structure as $P_{cu}=\left\{\right\{C{O}_1^{n_1}\left\}\mathrm{,}\right\{C{O}_2^{n_2}\}\mathrm{,}\dots \mathrm{,}\{C{O}_l^{n_l}\left\}\right\}$ which contains l coalitions. For each CSC, for example, $\mathrm{CS}{\mathrm{C}}_m$ , $a_m$ denotes its action. The candidate action set contains the following two types: (1) choosing a current coalition from the current coalitions to join in; (2) choosing the non-cooperative status to form a singleton coalition of itself. Then, the candidate action set is given by

$$\begin{array}{c}S{a}_m=\{a_{m1},a_{m2},\dots ,a_{\mathrm{mt}}\}\hfill \\ =P_{\mathrm{cu}}\cup \{\left\{{\mathrm{CSC}}_m^1\right\},\left\{{\mathrm{CSC}}_m^2\right\},\dots ,\left\{{\mathrm{CSC}}_m^N\right\}\}\hfill \\ =\{\left\{{\mathrm{CO}}_1^{n_1}\right\},\left\{{\mathrm{CO}}_2^{n_2}\right\},\dots ,\left\{{\mathrm{CO}}_l^{n_l}\right\}\}\hfill \\ \multicolumn{1}{c}{\cup \{\left\{{\mathrm{CSC}}_m^1\right\},\left\{{\mathrm{CSC}}_m^2\right\},\dots ,\left\{{\mathrm{CSC}}_m^N\right\}\}}\\ \stackrel{\mathrm{denote}}{\iff }S{a}_m=\{\left\{{\mathrm{CO}}_1^{n_1}\right\},\left\{{\mathrm{CO}}_2^{n_2}\right\},\dots ,\left\{{\mathrm{CO}}_t^{n_t}\right\}\}\hfill \end{array}$$

(8)

where $t=\left|S{a}_m\right|$ is the number of candidate actions.

Definition 3 (Pareto improving utility function)

We assume that any player’s actions need to meet the Pareto improving condition. ²⁰ For any candidate action ${\mathrm{CO}}_k^{n_k}\subseteq S{a}_m$ and any player $m\in {\mathrm{CO}}_k^{n_k}$ , define the Pareto improving utility function of player as

$${\mu }_m\left({\mathrm{CO}}_k^{n_k}\right)=\{\begin{array}{c}{v}_m\left({\mathrm{CO}}_k^{n_k}\right),\mathrm{if}\forall j\in {\mathrm{CO}}_k^{n_k}\backslash \left\{m\right\}\hfill \\ \multicolumn{1}{c}{v_j\left({\mathrm{CO}}_k^{n_k}\right)\ge v_j({\mathrm{CO}}_k^{n_k}\backslash \left\{m\right\})}\\ \multicolumn{1}{c}{0,\mathrm{otherwise}}\end{array}$$

(9)

The Pareto improving condition implies that the player’s action is to improve its individual profit without hurting other players, which has been widely used in coalitional game, such as in the literature.^2,36,37

Definition 4 (traditional Binary Preferring order)

Similar to the previous studies^2,32,40,41 for player $m\in S$ with a current candidate action set $S{a}_m=\{\{{\mathrm{CO}}_1^{n_1}\},\{{\mathrm{CO}}_2^{n_2}\},\dots ,\{{\mathrm{CO}}_t^{n_t}\}\}$ , the action $a_m$ is determined by the binary preference order ${\succ }_m$ , which is a binary relation over coalitions. ${\mathrm{CO}}_1^{n_1}{\succ }_m{\mathrm{CO}}_2^{n_2}$ means player m strictly prefers being a member of coalition ${\mathrm{CO}}_1^{n_1}$ rather than ${\mathrm{CO}}_2^{n_2}$ . In other words, player m’s action $a_m$ is

$$a_m=\{\begin{array}{cc}\mathrm{choose}{\mathrm{CO}}_1^{n_1},\hfill & \mathrm{if}{\mathrm{CO}}_1^{n_1}{\succ }_m{\mathrm{CO}}_2^{n_2}\hfill \\ \multicolumn{1}{c}{\mathrm{choose}{\mathrm{CO}}_2^{n_2},}& \mathrm{if}{\mathrm{CO}}_2^{n_2}{\succ }_m{\mathrm{CO}}_1^{n_1}\hfill \end{array}$$

(10)

Note that, $a_m$ is an absolute strategy and alternatively selection, and the decision is based on ${\mathrm{CO}}_1^{n_1}$ and ${\mathrm{CO}}_2^{n_2}$ . With the traffic cooperation game, we define the binary preference order as

$${\mathrm{CO}}_1^{n_1}{\succ }_m{\mathrm{CO}}_2^{n_2}\iff {\mu }_m\left({\mathrm{CO}}_1^{n_1}\right)\succ {\mu }_m\left({\mathrm{CO}}_2^{n_2}\right)$$

(11)

Then, based on the binary preference order, player m’s action $a_m$ is

$$a_m=\{\begin{array}{cc}\mathrm{choose}{\mathrm{CO}}_1^{n_1},\hfill & \mathrm{if}{\mu }_m\left({\mathrm{CO}}_1^{n_1}\right)\succ {\mu }_m\left({\mathrm{CO}}_2^{n_2}\right)\hfill \\ \multicolumn{1}{c}{\mathrm{choose}{\mathrm{CO}}_2^{n_2},}& \mathrm{if}{\mu }_m\left({\mathrm{CO}}_2^{n_2}\right)\succ {\mu }_m\left({\mathrm{CO}}_1^{n_1}\right)\hfill \end{array}$$

(12)

The action decision means that the play m will strictly select the coalition to obtain better throughput, from the given two candidate coalitions where the Pareto improving condition is met.

Definition 5 (Functional Preference order)

Unlike the traditional binary and strictly preference order in Definition 2, we propose the Functional Preference order to give a more general and flexible preferring action: for player $m\in S$ with a current candidate action set $S{a}_m=\{\{{\mathrm{CO}}_1^{n_1}\},\{{\mathrm{CO}}_2^{n_2}\},\dots ,\{{\mathrm{CO}}_t^{n_t}\}\}$ , the action $a_m$ is determined by the Functional Preference order $F_m$ : $a_{\mathrm{Fm}}=F_m(S{a}_m)=F_m(\{{\mathrm{CO}}_1^{n_1}\},\{{\mathrm{CO}}_2^{n_2}\},\dots ,\{{\mathrm{CO}}_l^{n_l}\})$ .

Remark 1

Note that the action $a_m$ is a function value based on all the coalitions, not only two coalitions ( ${\mathrm{CO}}_1^{n_1}$ and ${\mathrm{CO}}_2^{n_2}$ as traditional Binary Preferring order), and the value is not an absolutely and alternatively selection ( ${\mathrm{CO}}_1^{n_1}$ or ${\mathrm{CO}}_2^{n_2}$ ) any more. The action is determined by the specific function design, which is determined by specific problem and the optimization aim. For example, the action may be a mixed strategy. In particular, the traditional preference order ${\succ }_m$ can be seen as a special case of the functional order $F_m$ , where the function is designed as an absolutely and alternative selection.

Definition 6 (Best Selection order)

Based on the Functional Preference order, we propose the Best Selection order as follows: for player $m\in S$ with a current candidate action set $S{a}_m=\{\{{\mathrm{CO}}_1^{n_1}\},\{{\mathrm{CO}}_2^{n_2}\},\dots ,\{{\mathrm{CO}}_t^{n_t}\}\}$ , The action $a_m$ is determined by the Best Selection order $F_{\mathrm{BSm}}$

$$\begin{array}{c}{a}_{\mathrm{BSm}}=F_{\mathrm{BSm}}(\left\{{\mathrm{CO}}_1^{n_1}\right\},\left\{{\mathrm{CO}}_2^{n_2}\right\},\dots ,\left\{{\mathrm{CO}}_l^{n_l}\right\})\hfill \\ =max(\left\{{\mathrm{CO}}_1^{n_1}\right\},\left\{{\mathrm{CO}}_2^{n_2}\right\},\dots ,\left\{{\mathrm{CO}}_l^{n_l}\right\})\hfill \\ ={\mathrm{CO}}_k^{n_k}\hfill \\ \mathrm{if}\forall {\mathrm{CO}}_i^{n_i}\subseteq P_{\mathrm{cu}}\&{\mu }_m\left({\mathrm{CO}}_i^{n_i}\right)\succ 0,{\mu }_m\left({\mathrm{CO}}_k^{n_k}\right)\hfill \\ \multicolumn{1}{c}{\ge {\mu }_m\left({\mathrm{CO}}_i^{n_i}\right)}\end{array}$$

(13)

The proposed Best Selection preference function design means that the player strictly prefers the best coalition from all the possible coalitions which meet the Pareto improving condition. Note that the preferring action is based on the comparison among all the possible coalitions, not the comparison between two given coalitions in the traditional Binary Preferring order.

Definition 7 (Probabilistic Decision order)

Based on the Functional Preference order, we propose the Probabilistic Decision order as follows: for player $m\in S$ with a current candidate action set $S{a}_m=\{\{{\mathrm{CO}}_1^{n_1}\},\{{\mathrm{CO}}_2^{n_2}\},\dots ,\{{\mathrm{CO}}_t^{n_t}\}\}$ , The action $a_m$ is determined by the Probabilistic Decision order $F_{\mathrm{PDm}}(\{{\mathrm{CO}}_1^{n_1}\},\{{\mathrm{CO}}_2^{n_2}\},\dots ,\{{\mathrm{CO}}_l^{n_l}\})$ , where player m randomly chooses a coalition according to the mixed strategy where the probability is given by

$$\mathrm{Pr}(a_{\mathrm{PDm}}={\mathrm{CO}}_k^{n_k})=\frac{\exp \left\{\beta {\mu }_m\left({\mathrm{CO}}_k^{n_k}\right)\right\}}{\sum _{\genfrac{}{}{0ex}{}{{\mathrm{CO}}_i^{n_i}\subseteq S{a}_m}{\begin{array}{c}{\mu }_m\left({\mathrm{CO}}_i^{n_i}\right)\succ 0\hfill \end{array}}}\exp \left\{\beta {\mu }_m\left({\mathrm{CO}}_i^{n_i}\right)\right\}}$$

(14)

The proposed Probabilistic Decision preference function design means that the player tends to choose the better coalition from the possible candidate coalitions with higher probability. Also, the candidate coalitions need to meet the Pareto improving condition.

Traffic Cooperation Coalition Formation Algorithms

We propose a three distributed coalition formation algorithms based on the above defined orders and investigate their properties.

The BPTCCF Algorithm

1. The procedure of algorithm: the BPTCCF Algorithm is based on the Binary Preferring order in Definition 4. The procedure of the algorithm is shown in Algorithm 1.

2. The stability analysis: the stability is one of the key properties of coalition formation algorithm; we analyze the stability of the proposed BPTCCF Algorithm as follows. The method of analysis follows the way in the literature.^2,34–37

Algorithm 1: BPTCCF Algorithm

Initialization: The network is partitioned by $\left|M\right|$ single coalitions, each of which contains a non-cooperative CSC. The initial coalition set is $P_{\mathrm{int}}=\{\{{\mathrm{CO}}_1^{n_1}\},\{{\mathrm{CO}}_2^{n_2}\},\dots ,\{{\mathrm{CO}}_M^{n_M}\}\}$ , where $\left|M\right|$ is the number of CSCs; One Round: Stage 1: information collection: traffic queues information, potential coalitions information, channel idle probability and capacity information; Stage 2: coalition formation: Repeat: Denote the current coalition structure $P_{\mathrm{cu}}=\{\{{\mathrm{CO}}_1^{n_1}\},\{{\mathrm{CO}}_2^{n_2}\},\dots ,\{{\mathrm{CO}}_l^{n_l}\}\}$ which contains l coalitions. For each CSC, for example, $\mathrm{CS}{\mathrm{C}}_m$ , makes the decision of action according to the following procedures: (a) Forming the candidate action set which containing the following two type actions: (1) choosing a current coalition from the current coalitions to join in; (2) choosing the non-cooperative status to form a singleton coalition of itself. The candidate action set is given by $$\begin{array}{c}S{a}_m=\{a_{m1},a_{m2},\dots ,a_{\mathrm{mt}}\}\hfill \\ \multicolumn{1}{c}{=P_{\mathrm{cu}}\cup \{\left\{{\mathrm{CSC}}_m^1\right\},\left\{{\mathrm{CSC}}_m^2\right\},\dots ,\left\{{\mathrm{CSC}}_m^N\right\}\}}\\ \multicolumn{1}{c}{=\left\{\begin{array}{c}\left\{{\mathrm{CO}}_1^{n_1}\right\},\left\{{\mathrm{CO}}_2^{n_2}\right\},\dots ,\left\{{\mathrm{CO}}_l^{n_l}\right\}\hfill \\ \multicolumn{1}{c}{\cup \left\{{\mathrm{CSC}}_m^1\right\},\left\{{\mathrm{CSC}}_m^2\right\},\dots ,\left\{{\mathrm{CSC}}_m^N\right\}}\end{array}\right\}}\\ \multicolumn{1}{c}{\stackrel{\mathrm{denote}}{\iff }S{a}_m=\{\left\{{\mathrm{CO}}_1^{n_1}\right\},\left\{{\mathrm{CO}}_2^{n_2}\right\},\dots ,\left\{{\mathrm{CO}}_t^{n_t}\right\}\}}\end{array}$$ (15) where $t=\left|S{a}_m\right|$ is the number of candidate actions. (b) Randomly choosing an action $a_m\in S{a}_m$ when the binary preference order condition (Definition 4) is met $$\begin{array}{c}{a}_m=a_{\mathrm{mi}}=\mathrm{choose}\left\{{\mathrm{CO}}_i^{n_i}\right\}\hfill \\ \multicolumn{1}{c}{\mathrm{if}{\mathrm{CO}}_i^{n_i}{\succ }_m{\mathrm{CO}}_k^{n_k}\iff {\mu }_m\left({\mathrm{CO}}_i^{n_i}\right)\succ {\mu }_m\left({\mathrm{CO}}_k^{n_k}\right)}\\ \multicolumn{1}{c}{\forall \left\{{\mathrm{CO}}_i^{n_i}\right\}\subseteq S{a}_m}\end{array}$$ (16) where ${\succ }_m$ is the Binary Preferring order in Definition 4, and ${\mu }_m$ is the Pareto improving utility function in Definition 3. (c) Updating the current coalition structure $P_{\mathrm{cu}}$ based on the CSC m ’s action.Until converges to a stable coalition structure $P_{\mathrm{BP}}^{*}$ . Stage 3: channel sensing and cooperative data transmission: CSCs sense the channels by spectrum sensing and tend to transmit their data cooperatively if the sensing result is channel idle. The data transmission sequence is based on the order that CSCs join the coalition. Once one CSC starts its transmission, it will announce a NAV message which tells other members the time duration it will occupy (as in the 802.11 DCF 41 ). The successive member in the transmission sequence will wait until the previous member completes its transmission.

Definition 8 (Nash-stable structure)

A coalitional structure $P_{\mathrm{BP}}^{*}=\{\{{\mathrm{CO}}_1^{n_1^{*}}\},\{{\mathrm{CO}}_2^{n_2^{*}}\},\dots ,\{{\mathrm{CO}}_t^{n_t^{*}}\}\}$ is Nash-stable if

$$\begin{array}{c}\forall \left\{{\mathrm{CO}}_t^{{n_t}^{*}}\right\}\subseteq P_{\mathrm{BP}}^{*},\forall \left\{{\mathrm{CO}}_i^{{n_i}^{*}}\right\}\subseteq P_{\mathrm{BP}}^{*},\hfill \\ \multicolumn{1}{c}{\mathrm{for}\forall m\in \left\{{\mathrm{CO}}_t^{{n_t}^{*}}\right\},{\mathrm{CO}}_t^{{n_t}^{*}}{\succ }_m{\mathrm{CO}}_i^{{n_i}^{*}}}\\ \multicolumn{1}{c}{\iff a_m=\mathrm{choose}\left\{{\mathrm{CO}}_t^{{n_t}^{*}}\right\}}\end{array}$$

A Nash-stable structure means that no player has an incentive to change the current status: deviating from its current coalition to another coalition or choosing the non-cooperative status to form a singleton coalition of itself.

Theorem 1

Starting from any initial coalition structure $P_{\mathrm{int}}$ , the proposed BPTCCF Algorithm will always converge to a final coalition structure $P_{\mathrm{BP}}^{*}$ .

Proof

Similar to the analysis in the literature,^2,34–37 the coalition structure varies in each CSC’s action in Stage 2 of Algorithm 1. Since the number of CSCs and number of channels are finite, the maximum number of possible coalition structures is the Bell number. ²⁴ Then, the number of structure transformations is finite. In other words, under the binary preferring action rule which is based on the Pareto improving condition, the structure transformation will always terminate. So, the convergence of the algorithm is guaranteed. Thus, the theorem is proved.

Theorem 2

Starting from any initial coalition structure $P_{\mathrm{int}}$ , any final coalition structure $P_{\mathrm{BP}}^{*}$ formed by the proposed BPTCCF Algorithm will be Nash-stable.

Proof

Suppose that the final coalition structure $P_{\mathrm{BP}}^{*}$ is not Nash-stable, then $\exists m\in \{{\mathrm{CO}}_t^{n_t^{*}}\}\subseteq P_{\mathrm{BP}}^{*},a_m\ne \mathrm{choose}\{{\mathrm{CO}}_t^{n_t^{*}}\}$ , and the player m’s action will cause the change of current coalition structure, which contradicts with the fact that $P_{\mathrm{BP}}^{*}$ is the convergence of the BPTCCF Algorithm. Thus, the theorem is proved.

The BSTCCF Algorithm

This BSTCCF Algorithm is based on the Best Selection order in Definition 6. The procedure of the algorithm is shown in Algorithm 2.

Algorithm 2: BSTCCF Algorithm

Initialization: Same with BPTCCF Algorithm (Algorithm 1); One Round:Stage 1: same with BPTCCF Algorithm (Algorithm 1); Stage 2: coalition formation: Repeat: (a) The candidate action set is given by $$\begin{array}{c}\multicolumn{1}{c}{S{a}_m=\{a_{m1},a_{m2},\dots ,a_{\mathrm{mt}}\}}\\ \multicolumn{1}{c}{=\{\left\{{\mathrm{CO}}_1^{n_1}\right\},\left\{{\mathrm{CO}}_2^{n_2}\right\},\dots ,\left\{{\mathrm{CO}}_t^{n_t}\right\}\}}\end{array}$$ (17) (b) Choosing the action $a_m\in S{a}_m$ when according to the Best Selection Order (Definition 6) $$\begin{array}{c}{a}_{\mathrm{BSm}}=F_{\mathrm{BS}}\left(S{a}_m\right)=a_{\mathrm{mi}}=\mathrm{choose}\left\{{\mathrm{CO}}_i^{n_i}\right\}\hfill \\ \multicolumn{1}{c}{\mathrm{if}\forall \left\{{\mathrm{CO}}_j^{n_j}\right\}\subseteq S{a}_m,{\mu }_m\left({\mathrm{CO}}_i^{n_i}\right)\succ {\mu }_m\left({\mathrm{CO}}_j^{n_j}\right)}\end{array}$$ (18) where ${\mu }_m$ is the Pareto improving utility function in Definition 3. (c) Same with BPTCCF Algorithm (Algorithm 1). Until converges to a stable coalition structure $P_{\mathrm{BS}}^{*}$ . Stage 3: same with BPTCCF Algorithm (Algorithm 1).

Similar to Algorithm 1, the proposed BSTCCF Algorithm will always converge to a final coalition structure $P_{\mathrm{BS}}^{*}$ .

Remark 2

Compared with the BPTCCF Algorithm, the main difference is that each player chooses the best action from all the candidate actions, rather than a random good action. The convergence speed of the BSTCCF Algorithm will be much faster than the BPTCCF Algorithm. However, the performance of BSTCCF Algorithm may be worse, because the current best action may deviate from the better coalition structure in the perspective of long term. The details about convergence speed and performance will be discussed in the simulation.

The PDTCCF Algorithm

• 1. The procedure of algorithm: The PDTCCF Algorithm is based on the Probabilistic Decision order in Definition 7. The procedure of the algorithm is shown in Algorithm 3.

Algorithm 3: PDTCCF Algorithm

Initialization: same with BPTCCF Algorithm (Algorithm 1); One Round of Algorithm: Stage 1: same with BPTCCF Algorithm (Algorithm 1); Stage 2: coalition formation: Repeat: (a) The candidate action set is given by $$\begin{array}{c}\multicolumn{1}{c}{S{a}_m=\{a_{m1},a_{m2},\dots ,a_{\mathrm{mt}}\}}\\ \multicolumn{1}{c}{=\{\left\{{\mathrm{CO}}_1^{n_1}\right\},\left\{{\mathrm{CO}}_2^{n_2}\right\},\dots ,\left\{{\mathrm{CO}}_t^{n_t}\right\}\}}\end{array}$$ (19) (b) Choosing the action $a_m\in S{a}_m$ when according to the Probabilistic Decision order (Definition 7), that is, player m randomly an action according to the mixed strategy where the probability is given by $$\mathrm{Pr}(a_m={\mathrm{CO}}_k^{n_k})=\frac{\exp \left\{\beta {\mu }_m\left({\mathrm{CO}}_k^{n_k}\right)\right\}}{\sum _{\genfrac{}{}{0ex}{}{{\mathrm{CO}}_i^{n_i}\subseteq S{a}_m}{\begin{array}{c}{\mu }_m\left({\mathrm{CO}}_i^{n_i}\right)\succ 0\hfill \end{array}}}\exp \left\{\beta {\mu }_m\left({\mathrm{CO}}_i^{n_i}\right)\right\}}$$ (20) where ${\mu }_m$ is the Pareto improving utility function in Definition 3. (c) Same with BPTCCF Algorithm (Algorithm 1); Until converges to a stable coalition structure $P_{\mathrm{PD}}^{*}$ . Stage 3: same with the BPTCCF Algorithm (Algorithm 1).

In Stage 2(b), the probabilistic decision-making rule (Boltzmann exploration strategy ³⁷ ) is introduced in order to escape from local optimal points and finally converge to the Nash-stable coalition structure. The parameter $\beta$ is analogous to the concept of temperature in simulated annealing. There is a trade-off between exploration and exploitation. Smaller $\beta$ implies that SLs tend to choose a suboptimal action, whereas larger $\beta$ implies that players are prone to choose the current best action.

Remark 3

Compared with the BPTCCF Algorithm and the BSTCCF Algorithm, the main difference is that the action choosing is not the absolutely choosing, but a probabilistic choosing according to some probability distribution. The PDTCCF Algorithm actually is a trade-off of speed and performance in coalition formation. The converging speed of PDTCCF Algorithm will be slower than the BSTCCF Algorithm. However, the performance of PDTCCF Algorithm will be better than the BPTCCF Algorithm and the BSTCCF Algorithm, because the current best action may deviate from the better coalition structure in the perspective of long term. Actually, the probabilistic decision gives a chance for the system to stay in some tentative suboptimal states for evolving to the better final solution. The details about convergence speed and performance will be discussed in the simulation.

• 2. The stability analysis:

Theorem 3

With a sufficiently large $\beta$ , starting from any initial coalition structure $P_{\mathrm{int}}$ , the proposed PDTCCF Algorithm will always converge to a Nash-stable coalition structure $P_{\mathrm{PD}}^{*}$ with probability 1.

Proof

Similar to the analysis in the literature,^2,34–37 the coalition structure varies in each CSC’s action in Algorithm 3. Since the number of CSCs and number of channels are finite, the maximum number of possible coalition structures is the Bell number. ²⁴ Suppose player m’s action strategy space is $S{a}_m=\{\{{\mathrm{CO}}_1^{n_1}\},\{{\mathrm{CO}}_2^{n_2}\},\dots ,\{{\mathrm{CO}}_t^{n_t}\}\}$ , and $\{{\mathrm{CO}}_k^{n_k}\}$ is its best selection, that is, $\forall \{{\mathrm{CO}}_i^{n_i}\}\subseteq S{a}_m,i\ne k,{\mu }_m({\mathrm{CO}}_k^{n_k})\succ {\mu }_m({\mathrm{CO}}_i^{n_i})$ . When $\beta$ is sufficiently large, $\forall \{{\mathrm{CO}}_i^{n_i}\}\not\subset {\mathrm{Sa}}_m,i\ne k,\exp \{\beta {\mu }_m({\mathrm{CO}}_k^{n_k})\}>>\exp \{\beta {\mu }_m({\mathrm{CO}}_i^{n_i})\}$ . Then, according to the probabilistic decision rule in equation (20), we have

$$\begin{array}{c}\underset{\beta \to \infty }{lim}\mathrm{Pr}(a_m=\mathrm{choose}\left\{{\mathrm{CO}}_k^{n_k}\right\})\hfill \\ \multicolumn{1}{c}{=\underset{\beta \to \infty }{lim}\frac{\exp \left\{\beta {\mu }_m\left({\mathrm{CO}}_k^{n_k}\right)\right\}}{\sum _{\genfrac{}{}{0ex}{}{{\mathrm{CO}}_i^{n_i}\subseteq S{a}_m,{\mathrm{CO}}_k^{n_k}\subseteq S{a}_m}{\begin{array}{c}{\mu }_m\left({\mathrm{CO}}_i^{n_i}\right)\succ 0,{\mu }_m\left({\mathrm{CO}}_k^{n_k}\right)\succ 0\hfill \end{array}}}\exp \left\{\beta {\mu }_m\left({\mathrm{CO}}_i^{n_i}\right)\right\}}=1}\end{array}$$

(21)

That means the action decision tends to be absolutely choosing rather than probabilistic choosing when $\beta$ is sufficiently large. Thus, the structure transformation will terminate with probability 1, and the system then converges to a coalition structure $P_{\mathrm{PD}}^{*}$ with probability 1. So, the convergence of the algorithm is guaranteed.

Denote the final coalition structure $P_{\mathrm{PD}}^{*}=\{\{{\mathrm{CO}}_1^{n_1^{*}}\},\{{\mathrm{CO}}_2^{n_2^{*}}\},\dots ,\{{\mathrm{CO}}_t^{n_t^{*}}\}\}$ , suppose $P_{\mathrm{PD}}^{*}$ is not Nash-stable, that is, $\exists m\in \{{\mathrm{CO}}_t^{n_t^{*}}\}\subseteq P_{\mathrm{BP}}^{*},\{{\mathrm{CO}}_i^{n_i^{*}}\}\subseteq P_{\mathrm{BP}}^{*},i\ne k,{\mu }_m({\mathrm{CO}}_i^{n_i^{*}})\succ {\mu }_m({\mathrm{CO}}_t^{n_t^{*}})$ , then $\exp \{\beta {\mu }_m({\mathrm{CO}}_i^{n_i^{*}})\}>>\exp \{\beta {\mu }_m({\mathrm{CO}}_t^{n_t^{*}})\}$ when the $\beta$ is sufficiently large; as a result, $\underset{\beta \to \infty }{lim}\mathrm{Pr}(a_{\mathrm{PDm}}=\mathrm{choose}\{{\mathrm{CO}}_i^{n_i^{*}}\})=1$ , which means that player m will choose ${\mathrm{CO}}_i^{{n_i}^{*}}$ rather than its current coalition ${\mathrm{CO}}_t^{{n_t}^{*}}$ with probability 1. Then, the player m’s action will cause the change of current coalition structure, which contradicts with the fact that $P_{\mathrm{PD}}^{*}$ is the convergence of the algorithm. Thus, Theorem 2 is proved.

Theorem 4

Starting from any initial coalition structure $P_{\mathrm{int}}$ , any final coalition structure $P_{\mathrm{BP}}^{*}$ formed by the proposed BPTCCF Algorithm will be Nash-stable.

Proof

Suppose that the final coalition structure $P_{\mathrm{BP}}^{*}$ is not Nash-stable, then $\exists m\in \{{\mathrm{CO}}_t^{n_t^{*}}\}\subseteq P_{\mathrm{BP}}^{*},a_m\ne \mathrm{choose}\{{\mathrm{CO}}_t^{n_t^{*}}\}$ , and the player m’s action will cause the change of current coalition structure, which contradicts with the fact that $P_{\mathrm{BP}}^{*}$ is the convergence of the BPTCCF Algorithm. Thus, the theorem is proved.

Simulation results and discussion

In this section, we evaluate the performance of the proposed algorithms by MATLAB simulations. Without loss of generality, the parameters are set as follows: the fixed frame duration T = 100 ms. The sensing time of each channel ${\tau }_s$ is 5 ms. The PU channel set is $S_{\mathrm{CH}}=\{C{H}_1,C{H}_2,C{H}_3,C{H}_4\}$ , which consists of four PU channels. The PU channels are heterogeneous: the channel capacity vector is $\mathbf{C}=[C_1,C_2,C_3,C_3]=[1000,2000,3000,4000]\mathrm{kbit}/\mathrm{s}$ and the idle probability of channel vector is ${\mathbf{P}}^0=[P_1^0,P_2^0,P_3^0,P_4^0]=[0.9,0.85,0.9,0.85]$ . The probability of false alarm is set to be 0.05. The data queue is limited and heterogeneous: the possible data amount of traffic queue set is $L=[853310,13316,53320,80025,06733,60042,13350,66759,20067,733]\mathrm{bits}$ , which simulates data traffic queue generated by some different typical applications, such as G.711PCM, WMV, AVI/RM, Flash, and H264 (Figure 1) (since we focus on the decision-making based on the traffic queue known by CSC itself, we do not pay more attention to the traffic model which is out the scope of our article. We simulate the heterogeneous traffics by setting different data queue values).

In Figure 4, we consider a four-CSC scenario to evaluate the performance of the proposed approaches. Since there are four channels available for four CSCs, the performance of “No Coalition” is well. This is the typical scenario where the number of CSCs is less than the number of channels, and the interference can be avoided by traditional interference management method.

Figure 4.

The performance of proposed algorithms in a four-CSC scenario: $\mathbf{L}=[853316,53325,06742,133]$ . The stable coalition structure and channel allocation: $\mathrm{Binary}\mathrm{Preferring}:\{1,3{\}}^3,\{2,4{\}}^4$ ; $\mathrm{Best}\mathrm{Selection}:{\{1,3\}}^4,\{2,4{\}}^3$ ; and $\mathrm{Probabilistic}\mathrm{Decision}:\{1{\}}^2,\{2,4{\}}^4,{\{3\}}^3$ .

Even though, the proposed traffic cooperation approaches also get better performances. Under the limited traffic condition, it is not optimal anymore by allocating each channel to each CSC, respectively, as the traditional interference management method. The better approach needs to realize the match between the traffics and channels. For example, in the stable coalition structure of Probabilistic Decision Coalition (PDTCCF Algorithm), CSC₄ would rather choose to share channel 4 with CSC₂, than choose the idle channel 1. Because the capacity of channel is much worse than channel 4, sharing channel 4 with CSC₂ will obtain better throughput.

It can be seen that the proposed algorithms converge to the stable coalition structures. The stable structures are given in the figure. We can see that the converged structures are different because the order functions are different. Note that the stable structure may not be the optimal coalition structure. For example, in the stable structure of Binary Preferring Coalition (BPTCCF Algorithm), compared with the stable coalition structure of Probabilistic Decision Coalition (PDTCCF Algorithm), the CSC₁ should tune to channel 2 in the perspective of network throughput. However, for CSC₁ itself, it would choose channel 3 to obtain better throughput. Then, the coalition structure of BPTCCF Algorithm will never turn into the better structure as the structure of PDTCCF Algorithm since CSC 1 has occupied channel 3 early. The Probabilistic Decision Coalition (PDTCCF Algorithm) can achieve best converged stable coalition structure because the probabilistic decision gives a chance for the system to stay in some tentative suboptimal states for evolving to the better final solution. This analysis also applies to the Best Selection Coalition (BSTCCF Algorithm), which has the worst converged performance and the fastest converging speed.

In Figures 5–7, we simulate 6-CSC, 8-CSC, and 10-CSC scenarios, respectively, to investigate performances of proposed algorithms under the “heavy load” condition, where the number of CSCs is bigger than the number of channels. Note that, in practical applications, the “heavy load” is commonplace, such as Wi-Fi system where multi users share three channels.

Figure 5.

The performance of proposed algorithms in a six-CSC scenario: $L=[42,13333,60025,06716,53320,8008533]$ .

Figure 6.

The performance of proposed algorithms in a eight-CSC scenario: $L=[42,13350,66710,13333,60016,53320,80025,0678533]$ . The stable coalition structure and channel allocation: $\mathrm{Binary}\mathrm{Preferring}:\{6,3,5,1{\}}^4,\{7{\}}^2,\{8,4,2{\}}^3$ ; $\mathrm{Best}\mathrm{Selection}:{\{1,4,7\}}^4,\{2,6{\}}^3,\{3,5{\}}^2$ ; and $\mathrm{Probabilistic}\mathrm{Decision}:\{3{\}}^1,\{4{\}}^2,{\{5,7,1\}}^4,{\{8,6,2\}}^3$ .

Figure 7.

The performance of proposed algorithms in a10-CSC scenario: $L=[42,13350,66720,80010,13333,60016,53320,80033,60025,0678533]$ . The stable coalition structure and channel allocation: $\mathrm{Binary}\mathrm{Preferring}:\{1,2{\}}^3,\{4,3,10{\}}^2,\{5,6,7,8{\}}^4,\{9{\}}^1$ ; $\mathrm{Best}\mathrm{Selection}:{\{1,4,5,8\}}^4,\{2,7,9{\}}^3,\{3,6{\}}^2,\{10{\}}^1$ ; and $\mathrm{Probabilistic}\mathrm{Decision}:\{4,3{\}}^2,\{6,7,5{\}}^3,{\{8\}}^1,{\{9,10,1,2\}}^4$ .

Under this “heavy load” condition, the traditional interference avoid mechanism could not work well, because there are not enough channels. When the number of CSCs increases, the performance of “No Coalition” decreases rapidly for the serious interference.

The proposed traffic cooperation approach shows its advantage by considering both spectrum and time at the same time, based on the actual demands of CSCs’ traffics and channel capacities. The proposed algorithms could also realize the match between the traffics and channels to achieve better throughput. Also, the convergence of the proposed algorithms is verified. Again, the stable coalition structures of different algorithms are different.

The above simulation results are all the one-time experiment results. They show the details of the formulated coalitions as the illustrations. Due to the random result in the experiments, the performance improvement trend is not so clear. To avoid the random result in one-time experiment, we use the average value of 500 independent experiments results to show the average performances of different methods. Figure 8 shows the convergence and performance of the proposed algorithms furthermore. The result shows that the system tends to the converged state as the learning iteration increases. The proposed “Best Selection Coalition” algorithm has the fastest converging speed, and the proposed “Probabilistic Decision Coalition” algorithm has the best system performance and relatively slow converging speed. The traditional “Binary Preferring Coalition” algorithm also converges.

Figure 8.

The average performance of 500 independent experiments. The parameters are same with that in Figure 7.

Figures 9 and 10 show the converged performance of proposed algorithms. In Figure 9, the converging speeds of proposed three algorithms are compared. In Figure 10, the converged stable network throughputs are compared. Among the proposed three coalition algorithms, the Best Selection Coalition (BSTCCF Algorithm) has the fastest converging speed. The Probabilistic Decision Coalition (PDTCCF Algorithm) has the best converged performance. The traditional Binary Preferring Coalition (BPTCCF Algorithm) has the slowest converging speed and just accepted performance.

Figure 9.

The converging speed comparison of the proposed algorithms.

Figure 10.

The stable throughput comparison of the proposed algorithms.

It can be seen that the proposed functional order is more flexible compared with the traditional Binary Preference order. When we focus on the converging speed, we can choose the Best Selection order. When we focus on the converged performance, we can choose the Probabilistic Decision order. Furthermore, we can also design other function orders according to the demands and scenarios. In all, the proposed traffic cooperation approaches could obtain much better performance than the traditional none-coalition interference management method, especially when the number of CSCs is bigger than the number of channels where the interference avoid could not be realized by traditional no-traffic coalition method.

Conclusion

In this article, we investigated the problem of efficient spectrum access for traffic demands of self-organizing CSC networks. We proposed a spectrum and time two-dimensional Traffic Cooperation Coalitional Game model which aims to realize the efficient spectrum access for CSCs’ traffics. With the approach of coalition formation, the proposed functional order indicates a more flexibly preferring action compared with the traditional binary order in most existing works. We proposed three coalition formation algorithms to solve the distributed self-organizing traffic cooperation coalition formation problem, which have been proved to converge to Nash-stable coalition structure. Simulation results verified the theoretic analysis and the proposed approaches.

Footnotes

Handling Editor: Donatella Darsena

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported by China Postdoctoral Science Foundation Project, No. 2018M633684.