1 Introduction

Next generation (xG) wireless networks are envisioned to operate in a highly dynamic environment. The ubiquitous nature of xG networks requires them to have self-organizing autonomous nodes/agents, that can dynamically optimize their performance in a distributed manner without relying on any centralized authority. In this regard, ad hoc radio networks, comprising of self-adapting transceivers (radios/nodes) which can communicate with each other without pre-existing infrastructure, are important enablers for xG networks.

In ad hoc radio networks, achievable throughput (transmission rate) strongly depends on how the distributed nodes decide to cooperate and use the available radio resources. In particular, nodes may cooperate to increase their individual rate, leading to selfish cooperation, or they may cooperate to maximize the group sum-rate, which is called altruistic cooperation. The interactions between the distributed nodes in an ad hoc network can be well modeled as a game, in which network nodes are players that form cooperative groups; i.e. coalitions, to improve individual/group quality of service; i.e. rate in our case [2]. Hence, in this paper, we introduce a game-theoretic framework to dynamically share the common spectral resources among competing distributed nodes. We study both selfish and altruistic cooperation schemes and propose to model the throughput-efficient distributed network partitioning problem as a hedonic CF game with three different classes of CF rules. The proposed hedonic CF game is solved such that each member of a coalition gets an optimal share of the total available bandwidth (BW).

1.1 Related work and our contributions

Game theory (GT) [3] has recently gain noticeable popularity in modeling and solving the problem of distributed resource allocation in wireless networks. This is evident from plethora of research activities exploring cooperative GT for performance improvement in various types of ad hoc radio networks [4, 5]. In particular, coalitional game-theoretic framework [6] has extensively been applied in this regard. For example, the authors in [7] propose to solve the intermittent connectivity problem in vehicular ad hoc networks (VANETs) by using coalitional GT to organize distributed nodes (vehicles and/or roadside units), accessing the same service, into disjoint coalitions, and selecting a cooperative relay in each coalition for enhanced network efficiency in terms of improved packet success rate. In [8] and [9], CF games are used to improve the overall network throughput via device-to-device (D2D) underlay communications with uplink resource sharing. The authors propose to divide the total system bandwidth B into K orthogonal resource blocks (RBs), and define two modes of operation: (1) traditional cellular mode; in which D2D users communicate via evolved NodeBs (eNBs), and (2) D2D mode; through which D2D pair reuses the RB of cellular user (CU). The authors in [8] consider the coalition sum-rate as the coalition value and play a transferable utility (TU) CF game in characteristic form, which implies that the coalition value depends solely on the members of that coalition, and the total value of the coalition can be arbitrarily divided among the coalition members. In comparison to [8], in which D2D pairs are chosen randomly to select the proper modes and spectrum reusing partners through best-reply rule which provides them with the highest utility, the authors in [9] devise a switch-rule based hedonic CF game with non-transferable utility (NTU) to address the same problem of mode selection and resource allocation.

Hedonic games belong to a special class of CF games in characteristic form in which the coalitions are formed based on the preferences of the players over their possible coalition set. Hedonic games have been applied to multi-channel cooperative spectrum sensing and access (CSSA) problem in cognitive radio ad hoc networks (CRAHNs) in [10], where the authors avoid interference among the secondary users (SUs) by allowing only one SU (among the group of SUs that cooperatively determine the status of sensed channel) to access the channel. In [11], authors have proposed a hedonic CF game to be played at secondary base stations for sharing the availability of licensed channels. In contrast to pure selfish CF rule proposed in [9] and [10, 11] allows a player to switch to a new coalition if it can improve its payoff, without decreasing the payoff of any member of the new coalition. In a more generic multi-agent network consisting of wireless agents/nodes, hedonic CF game is played to collect/relay data from arbitrarily located data sources and pass it to the central receiver [12]. An interesting aspect of the proposed switch-rule in [12] is that although the agents prefer the coalition that offers better payoff, agents only switch to the coalition offering better payoff provided that the agent is not alone in its current coalition. In this way, the preference relation of agents is designed to improve the overall throughput from network point of view.

A careful review of the literature [7,8,9,10,11,12] identifies throughput-efficient network partitioning as the key problem in ad hoc radio networks. In particular, how the spectral resources are shared among the competing nodes, how the interference is handled, and how the competing nodes interact to achieve their goals, determine the achievable performance bounds. In this regard, our previous work [1] focuses on the selfish nature of cooperating nodes. In particular, grouping of secondary users in CRAHNs is studied and means are proposed to achieve Nash stability. However, our earlier work does not provide any clue on the degree of fairness, computational complexity and implementation details of CF algorithm. Furthermore, the nature of initial network partition is not considered while deriving the achievable rate or studying the convergence properties of proposed algorithm. In comparison to our earlier work [1], this paper proposes three different classes of CF rules to compare the selfish and altruistic behavior of cooperating agents, and provides the implementation details and stability analysis of the proposed CF algorithm over a generalized ad hoc radio network. Furthermore, our current work not only investigates the effect of initial network partition on achievable rate under different proposed CF rules, but it also compares these rules in terms of fairness, computational complexity and properties of the evolved coalition structure. In particular, the main contributions of this paper against the existing work are summarized below:

  • Interference management in ad hoc radio networks is a critical task. Existing work either attempts to avoid interference through exclusive use of available radio resources [10], or reuse the available spectrum in terms of channels (RBs) of pre-fixed or equal BW [8] and [9]. In contrast, in this paper, distributed nodes are self-organized into disjoint coalitions such that the total available transmission BW is made available to each coalition, while this BW is optimally sub-divided into orthogonal bands within each coalition. We also derive a closed form expression of the rate-optimal BW allocation among coalition members.

  • Earlier works [1, 9, 10] on coalition formation consider selfish nature of distributed nodes, with a few schemes introducing the switching based on individual approval of the members of new coalition [11, 13, 14]. In contrast, we consider the effect of switching of one node from one (old) coalition to another (new) coalition, on other nodes in the network, and design five switching/CF rules based on whether a switching node needs approvals from the new and/or old coalition, and if needed, whether these approvals are individual or group approvals. In this way, we compare the selfish and altruistic nature of distributed nodes to quantify if it has any significant effect on the achievable average payoff per node. In addition, we also compare the proposed CF rules in terms of their convergence properties.

  • Convergence is another parameter of great interest in distributed CF [15]. Majority of the distributed CF algorithms guarantee convergence by introducing a history condition in the proposed CF rules [9, 10], which does not allow a distributed node to rejoin a coalition which it has left in the past, while other works, such as [11], limit the maximum number of revisits to same coalition to avoid cycles in CF process. Some CF rules restrict the action space of distributed nodes from merge-split [14] to merge only [13]. In contrast, we not only analyze the effect of using history condition in the CF algorithm to guarantee Nash-stability, but also describe different exit procedures when a CF cycle is inevitable.

  • Typically, the probabilistic analysis of CF is done by using Markov chain [16]. However, in this paper, we devise a method based on modeling the proposed hedonic CF algorithm to evaluate the probabilities of GC and SS being stable, and use them to derive a lower bound on the probability that the resulting stable coalition is neither GC nor SS. We verify our derived analytical expressions through simulations for selfish nodes, and assert the effectiveness of the proposed algorithm over wide SNR range.

The rest of the paper is organized as follows. Section 2 introduces the network model. The optimal BW allocation for a given network partition is presented in Sect. 3, while hedonic coalition formation game based on selfish and altruistic preference relations for reaching a throughput-efficient network partition is introduced in Sect. 4. The hedonic CF algorithm and its implementation in an ad hoc network is discussed in Sect. 5 and its convergence properties are highlighted. Probabilistic analysis of the proposed hedonic CF algorithm is presented in Sect. 6, and some key simulation results are provided in Sect. 7. Finally, the paper is concluded in Sect. 8.

2 Network model

We consider an ad hoc radio network with N distributed links (transmitter–receiver pairs). It is noteworthy that these links might represent randomly/planned deployed sensors in a wireless sensor network (WSN), autonomous agents in a wireless network, nodes in a mobile ad hoc network (MANET), vehicles or/and road side units (RSUs) in a VANET, D2D transmitter–receiver pairs in a cellular network, or secondary transmitter–receiver pairs in a CRAHN, as few examples. Hence, our network model is general, and the developed theory is applicable to a wide range of applications in a variety of ad hoc radio networks with distributed nodes/agents. For sake of generality, we assume that the total BW available for access is W Hz, and the channel between any of the transmitters and any of the receivers over this BW follows a quasi-static flat fading model. A representative network model is illustrated in Fig. 1.

Fig. 1
figure 1

A representative network model with 6 links, partitioned into 3 coalitions

Full size image

The throughput-efficient network partitioning problem is addressed from two perspectives. First, we propose frequency reuse of the available BW through the self-organization of N distributed links into non-overlapping coalitions such that each coalition will be using the total available BW. Such partitioning would, on one hand, have the potential to increase the network rate because of reusing the BW, but on the other hand would cause interference between the different coalitions. Therefore, the preference of a link towards a certain coalition, under a certain partitioning structure, would substantially affect its individual as well as the total achievable network rate. Hence, in this paper, we propose an efficient distributed CF algorithm, based on variety of CF rules, that can be used by distributed links to organize themselves into non-overlapping coalitions. Second, since each coalition in the network partition will be using the total available BW (W Hz), we propose to optimally allocate this BW among the coalition members based on the available channel state information (CSI) with the objective of maximizing the coalition sum-rate.

Figure 1 shows a snapshot of a network partition resulting from the proposed CF algorithm with \(N=6\) distributed links arranged in 3 disjoint groups, called coalitions. Mathematically, a network partition is indicated by \(\Pi \), while \(|\Pi |\) represents the cardinality of \(\Pi \). Each link in the network is identified by a unique global index g, \(g\in \{1,2,\ldots ,N\}\), while each coalition \(S_k\), \(k\in \{1,2,\ldots ,|\Pi |\}\), has a representative member, designated as coalition head \(H^k\), which acts as a gateway for its coalition. A coalition head \(H^k\) is aware of all the members of \(S_k\) such that every member of \(S_k\) who decides to leave or join \(S_k\), informs \(H^k\). Furthermore, \(H^k\) is responsible for optimally allocating the total available BW among the members of \(S_k\), and calculating the current rate for all of its members. A Member i of Coalition \(S_k\) is referred to as \(m_i^{k}\), \(i\in \{1,2,\ldots ,|S_k|\}\), where \(|S_k|\) represents the cardinality of \(S_k\). Any member \(m_i^{k}\) of Coalition \(S_k\) can act as coalition head \(H^k\). However, without loss of generality, we propose to consider a coalition member with largest global index, g, to act as \(H^k\). The motivation behind the selection convention of \(H^k\) is discussed in Sect. 5.

It is important to highlight here that CF and optimal BW allocation problems are coupled, which means that none of them can be solved without solving the other. This is because we can not form the coalitions without knowing the optimal rate of each coalition, and at the same time the optimal rate of each coalition depends on which links are inside this coalition and which ones are outside it. This renders the problem hard, but interesting. We start our analysis by solving the optimal BW allocation problem for a given coalition structure, and then we discuss how to exploit this optimal bandwidth allocation in the proposed coalition formation algorithm.

3 Optimal bandwidth allocation

In this section we discuss the optimal bandwidth allocation among the members of a coalition for a given coalition structure. Let the network partition at a certain time instant be: \(\Pi =\left\{ S_1,S_2,\ldots ,S_{|\Pi |}\right\} \), with \(|\Pi |\) disjoint coalitions. In the system model under consideration, each of the \(|\Pi |\) coalitions will use the total available bandwidth W. Consider Coalition \(S_k\in \Pi \), with members \(m_i^{k}\), \(i\in \{1,2,\ldots ,|S_k|\}\), where \(|S_k|\) represents the number of members (links) in \(S_k\). We will use \(P_i^k\) to represent the transmission power of Member i of Coalition \(S_k\), \(m_i^{k}\). Each member \(m_i^{k}\) of \(S_k\) will be allocated a fraction \(\mu _i^{S_k}\) of the total bandwidth, where \(\sum _{i=1}^{|S_k|}\mu _i^{S_k}=1\). The total interference power affecting the bandwidth W being used by Coalition \(S_k\) is the sum of all received power from all members in all other coalitions. For simplicity of the analysis, we approximate the interference affecting the band \(\mu _i^{S_k}W\) being used by Member \(m_i^{k}\) to be the average interference affecting this band which is a fraction \(\mu _i^{S_k}\) of the total interference power affecting the total bandwidth at the receiver of Link \(m_i^{k}\); i.e.,

$$\begin{aligned} \bar{I}_i^{S_k}&=\mu _i^{S_k}\sum _{l=1,l\ne k}^{l=|\Pi |}\sum _{j=1}^{|S_l|}P_j^l |h_{ji}^{lk}|^2\nonumber \\&=\mu _i^{S_k}\sum _{l=1,l\ne k}^{l=|\Pi |}I_i^{S_k,S_l}=\mu _i^{S_k}I_i^{S_k}. \end{aligned}$$
(1)

where \(h_{ji}^{lk}\) represents the channel between the transmitter of Link \(m_j^{l}\) and the receiver of Link \(m_i^{k}\). \(I_i^{S_k,S_l}=\sum _{j=1}^{|S_l|}P_j^l |h_{ji}^{lk}|^2\) is the interference experienced by the receiver of Link \(m_i^{k}\) from transmitters of all Links in Coalition \(S_l\), and \(I_i^{S_k}=\sum _{l=1,l\ne k}^{l=|\Pi |}I_i^{S_k,S_l}\) represents the total interference from all other coalitions in the network affecting the total bandwidth W. The total rate of Coalition \(S_k\) can be written as

$$\begin{aligned} \begin{aligned} \mathcal {R}^{S_k}&=\sum _{i=1}^{|S_k|} R_i^{S_k} {=}\sum _{i=1}^{|S_k|}\mu _i^{S_k} W\log \left( 1+\frac{P_i^k|h_{ii}^{kk}|^2}{\mu _i^{S_k} (N_0W+I_i^{S_k})}\right) . \end{aligned} \end{aligned}$$
(2)

In order to maximize the rate achieved by this coalition, the problem can be formulated as

$$\begin{aligned} \begin{aligned}&\underset{\mu _i^{S_k}}{\text {max}}\displaystyle \sum _{i=1}^{|S_k|} \mu _i^{S_k} W \log \left( 1+\frac{P_i^k|h_{ii}^{kk}|^2}{\mu _i^{S_k} (N_0W+I_i^{S_k})}\right) , \\&\quad \text {subject to} \displaystyle \sum _{i=1}^{|S_k|} \mu _i^{S_k} = 1 \text { and } 0 \le \mu _i^{S_k} \le 1. \end{aligned} \end{aligned}$$
(3)

It can be shown that this problem is concave, and hence the globally optimal solution is guaranteed to be obtained numerically. However, here we provide a closed form expression for the optimal solution as following:

The objective function of (3) can be written as

$$\begin{aligned} W \sum _{i=1}^{|S_k|} \mu _i^{S_k} \log \left( 1+\frac{x_i^k}{\mu _i^{S_k}}\right) , \end{aligned}$$
(4)

where \(x_i^k=\frac{P_i^k|h_{ii}^{kk}|^2}{N_0W+I_i^{S_k}}\). Since the \(\log \) function is concave, and since \(\sum _{i=1}^{|S_k|} \mu _i^{S_k} = 1\) and \(0 \le \mu _i^{S_k} \le 1\), hence the objective function can be upper bounded by

$$\begin{aligned} W \sum _{i=1}^{|S_k|} \mu _i^{S_k} \log \left( 1+\frac{x_i^k}{\mu _i^{S_k}}\right)&\leqslant W\log \left( 1+\sum _{i=1}^{|S_k|}\mu _i^{S_k}\frac{x_i^k}{\mu _i^{S_k}}\right) ,\nonumber \\&=W\log \left( 1+\sum _{i=1}^{|S_k|}x_i^k\right) . \end{aligned}$$
(5)

It can be shown that this upper bound can be achieved by choosing

$$\begin{aligned} \mu _{i,\text {opt}}^{S_k}=\frac{x_i^k}{\sum _{m=1}^{|S_k|}x_m^k}, \end{aligned}$$
(6)

Hence, the closed form expression of optimal rate \(R_{i,\text {opt}}^{S_k}\) for any \(i\in S_k\) is given by:

$$\begin{aligned} R_{i,\text {opt}}^{S_k}=\mu _{i,\text {opt}}^{S_k} W \log \left( 1+\sum _{m=1}^{|S_k|}x_m^k\right) . \end{aligned}$$
(7)

4 Problem formulation: hedonic coalition formation game

In the previous section, we derived a closed form expression of the rate-optimal BW allocation among coalition members under the assumption that a network partition is known apriori. In this section, we address the problem of finding an appropriate network partition in ad hoc radio networks wherein individual nodes interact with each other (without relying on a centralized entity) to achieve their goals (rate improvement, in our case) by forming non-overlapping coalitions. In this regard, we analyze how distributed nodes may reach a self-organizing coalition structure by evaluating whether a node should act in a non-cooperative manner and utilize the total available bandwidth W to maximize its rate, or it should make a coalition with other player(s) and divide W among the coalition members. Since the coalitional game theory provides useful tools to decide which players will cooperate with each other to efficiently achieve their goals, we model the node cooperation problem as a coalition formation game.

4.1 Preliminaries

4.1.1 Player, coalition and network partition

In the proposed CF game, the N nodes (distributed links) act as the players of the game constituting the set \(\mathcal N=\left\{ 1,2,\ldots ,N\right\} \) with each player identified by its global index g, \(g\in \left\{ 1,2,\ldots ,N\right\} \). We consider all players of the game to be truthful and myopic.

A coalition, S, is defined as a subset of \(\mathcal N\), \(S \subseteq \mathcal N\), while the set of coalitions \(\Pi =\left\{ S_1,S_2,\ldots ,S_{|\Pi |}\right\} \) is a network partition if all the coalitions in \(\Pi \) are mutually disjoint (\(S_k\bigcap S_l =\emptyset ~\forall ~k,l \in \left\{ 1,2,\ldots ,|\Pi |\right\} ,k\ne l\)) and span all the players of \(\mathcal N\); i.e., \(\bigcup _{k=1}^{|\Pi |} S_k=\mathcal N\). A network partition is also referred to as a coalition structure [6], and in this paper, we use the two terms interchangeably. The set of all possible partitions of \(\mathcal N\) is denoted by \(\mathcal P\), and the number of possible partitions \(|\mathcal P|\) is given by the Bell number [17].

4.1.2 Utility and value functions

Utility function \(\psi _g=\phi _i(S_k)\) describes the payoff/utility of the Player with global index \(g\in \left\{ 1,2,\ldots ,N\right\} \) which it receives being the Member i of coalition \(S_k\). For the proposed joint coalition formation and bandwidth allocation problem, the payoff of the player is determined in terms of the rate it achieves under the current coalition. Mathematically,

$$\begin{aligned} \psi _g=\phi _i(S_k)=R_{i,\text {opt}}^{S_k}, \end{aligned}$$
(8)

where \(R_{i,\text {opt}}^{S_k}\) is given by (7). The payoff vector \(\varvec{\psi } \in \mathbb R^N\) is evaluated as: \(\varvec{\psi }=[\psi _1,\psi _2,\ldots ,\psi _N]\).

In contrast, for a coalition \(S_k \subseteq \mathcal N\), the Value function \(\mathcal V(S_k)\) is defined as a mapping given by a vector \(\mathbf v(S_k)\in \mathbb R^{|S_k|}\), where each element \(v_i \in \mathbf v(S_k)\) represents the payoff \(\phi _i(S_k)\) of player \(i\in S_k\); i.e.,

$$\begin{aligned} \mathcal V(S_k)=\left\{ \mathbf v(S_k)\in \mathbb R^{|S_k|} | \,v_i(S_k)=\phi _i(S_k)\right\} , \end{aligned}$$
(9)

where \(\phi _i(S_k)=R_{i,\text {opt}}^{S_k}\) is evaluated using (7).

4.1.3 Outcome of the game

The outcome of the game is given by the pair \((\varvec{\psi },\Pi )\), where \(\varvec{\psi } \in \mathbb R^{N}\) represents the payoff vector of all players in the network under partition \(\Pi \).

4.2 Game model

4.2.1 A non-transferable utility (NTU) game

A NTU game is a coalition formation game in which the value \(\mathcal V(S)\) of a coalition S cannot be expressed as a scalar that can be arbitrarily divided among the coalition members. In such games, each player \(g\in \mathcal N\) will have its own payoff which it receives being the Member i of coalition S. Mathematically, a coalitional game with NTU is defined by a pair\((\mathcal N,\mathcal V)\) where \(\mathcal N\) is the set of players and \(\mathcal V\) is the coalition value function such that for every \(S \subseteq \mathcal N\), \(\mathcal V(S)\) is a closed convex subset of \(R^{|S|}\) that contains the payoff vectors that players in S can achieve.

The proposed CF game has a non-transferable utility since the coalition value function \(\mathcal V\), as per (7) and (9), is a vector with element i representing the payoff received by a coalition member i resulting from rate optimal BW allocation. Furthermore, the proposed game is classified as a hedonic coalition formation game. Before, presenting its definition, we introduce the concept of preference relation as follows [15]:

4.2.2 Preference relation

For any player \(g \in \mathcal N\), a preference relation \(\succeq _g\) is a complete, reflexive and transitive binary relation over the set of all possible coalitions that player g can form [15].

Since the distributed nodes are allowed to autonomously form the coalitions, the above definition is used to compare the preferences of player g over differ coalitions that it can join. Consequently, for any player \(g \in \mathcal N\), given two coalitions, \(S_1\subset \mathcal N\) and \(S_2\subset \mathcal N\), the notation \((S_1)\succeq _g (S_2)\) indicates that Player g prefers to be a member of Coalition \(S_1\) over to be a member of Coalition \(S_2\), or Player g is indifferent between \(S_1\) and \(S_2\). Furthermore, \((S_1)\succ _g (S_2)\), indicates that Player g strictly prefers \(S_1\) over \(S_2\).

4.2.3 Hedonic coalition formation game

Given the set of players \(\mathcal N\) and a profile of preferences \(\succ \); i.e., preference relations, \((\succeq _1,\succeq _2,\ldots ,\succeq _N)\) for every player \(g \in \mathcal N\), a CF game is said to be a hedonic game \((\mathcal N,\succ )\) if it satisfies the following two conditions [15]: (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 set of coalitions.

Having defined the main components of hedonic CF game, we utilize this framework to find an appropriate network partition. We model the node cooperation problem, formulated in the beginning of this section, as a \((\mathcal N,\succ )\) hedonic game, where \(\mathcal N\) is the set of distributed nodes, and \((\succ )\) is a profile of preferences that we will shortly elaborate. First and foremost, from (7) and (8), the utility of any player \(g\in \mathcal N\) which it receives being the Member i of Coalition \(S_k\), depends only on the players in Coalition \(S_k\). It is important to point out here that, as shown in (1), the utility of Player \(i \in S_k\) is independent of how the players outside \(S_k\) are grouped, and hence, the first hedonic condition holds.

Furthermore, for modeling the node cooperation problem as a hedonic CF game, the preference relations of the players must be clearly defined. In fact, for every application, a preference relation \(\succ _g\) can be evaluated in a different way to allow the players to quantify their preferences based on their observations, leading to different CF rules. In this regard, we first identify the action space of players that provides a mechanism through which a player can leave its current coalition and join another coalition based on the preference relation. Then we present a generalized CF rule followed by a proposed evaluation criteria for variety of CF rules.

4.2.4 Action space

The action space of Player g is defined as: \(A_g{=}\{\text {stay},\text {switch}\}, \forall g\in \mathcal N\). Thus, a player g stays in its current coalition with associated partition \(\Pi \) or switches to another coalition (which might even be an empty coalition \(\{~\}\); i.e., a player may decide to split from its current coalition and act alone non-cooperatively as a singleton) leading to a new network partition \(\acute{\Pi }\).

The action taken by a player relies on its evaluated preference relation. Hence, it is important to investigate how the achievable utility per player will change if the preference relation considers the effect of the switching action on other players as well. This requires acquiring the approval from the players whose utilities are affected by the proposed switching action.

Remark 1

In the proposed joint BW allocation and hedonic CF game, since the utility of player in a coalition does not depend on how the players outside its coalition are organized [as evident from (1) and (8)], therefore when a player switches, only the payoff of players in its old coalition and its new coalition are updated.

4.2.5 Generalized CF rule

In the light of above discussion, a variety of CF rules can be derived by defining the following generalized triplet:

$$\begin{aligned} CF Rule\triangleq & {} (selfish,approval(new),approval(old))\nonumber \\\equiv & {} (s,a_n,a_o) \end{aligned}$$
(10)

The first parameter selfish, s, emphasizes the individual rationality of the player. The other two parameters: approval from new and old coalition: \(a_n,a_o~\in \{no,indv,altru\}\) indicates the three possible approval alternatives: (1) (no): approval not required (2) (indv): individual approval is required from each player in the new/old coalition and (3) (altru): altruistic approval is required from the coalition as a whole which is granted based on the sum-rate achieved by the new/old coalition, and hence, it can be viewed as a much relaxed form of approval. In general, a player \(g \in \mathcal N\) decides to leave its current Coalition \(S_k \in \Pi \) and join another Coalition \(S_l \in \Pi \cup \{~\},~l\ne k\), and hence making a transition from \(\Pi \) to \(\acute{\Pi }=\left\{ \Pi \backslash \{S_k,S_l\}\right\} \cup \left\{ S_k\backslash \{g\},S_l\cup \{g\}\right\} \), if and only if \((S_l\cup \{g\})\succ _{g,(s,a_n,a_o)} (S_k)\), where \(\succ _{g,(s,a_n,a_o)}\) indicates a strict preference relation that is based on the underlying CF rule specified by the triplet \((s,a_n,a_o)\). A variety of CF rules can be derived based on the generalized CF rule triplet (10).

Table 1 Proposed CF rules and corresponding definitions of preference relation \((S_l\cup \{g\})\succ _{g,(s,a_n,a_o)} (S_k)\), where the Player g is locally indexed by i in Coalition \(S_k\), and by p in Coalition \(S_l\cup \{g\}\)
Full size table

4.2.6 Proposed CF rules

The proposed CF rule triplet \((s,a_n,a_o)\) leads to three classes of CF rules: (1) selfish class consisting of a single CF rule; (s,no,no), in which switching is decided solely by the switching player based on its own utility improvement, (2) selfish with new coalition approval; (s,indv,no) and (s,altru,no), which requires not only the utility improvement of the switching player but also seeks rate enhancement (individual or altruistic) from the new coalition to take the proposed switching action, and (3) selfish with approval from both the new and old coalition. Switching under this class of CF rules takes place not only when the moving player improves its own utility but also when it is welcomed (individually or altruistically) by the new coalition as well as when it is allowed (individually or altruistically) by the old coalition. In this class, we analyze two CF rules: (s,indv,indv) and (s,altru,altru) based on the rationale that it is more realistic to seek approval in the same form (indv,indv) or (altru,altru), from the new and old coalition.

It is noteworthy that we have considered five different CF rules to study and compare their performance and convergence properties. The proposed hedonic CF algorithm and the implementation protocol comprehensively covers all the rules, however, for the probabilistic analysis (Sect. 6), we focus on the (s,no,no) rule being the most suitable preference relation for majority of the applications. The full set of proposed CF rules along with the definitions of underlying preference relation are illustrated in Table 1. Based on these preference relations, every player can evaluate its preferences over the possible coalitions that it can form. Consequently, the proposed node cooperation model satisfies both hedonic conditions, and hence, the problem is well mapped into a \((\mathcal N, \mathcal \succ )\) hedonic CF game, with the preference relations defined in Table 1.

Having formulated the joint BW allocation and coalition formation problem as a hedonic game, the final task is to provide a distributed algorithm, based on the defined preferences, for forming throughput-efficient coalitions. The following section discusses the proposed CF algorithm and its convergence properties along with a detailed protocol to practically implement the distributed CF process according to the proposed algorithm.

5 Hedonic coalition formation algorithm

In order to reach a throughput-efficient coalition structure, a delicate balance between the spectrum re-use and interference avoidance needs to be maintained and hence, final coalition structure might neither be SS nor GC [17]. As a result, there is a need to develop an efficient algorithm to organize distributed nodes into non-overlapping coalitions, and to compare the achievable rates, the convergence and the stability properties of the algorithm under both selfish and altruistic cooperation strategies. Furthermore, since ad hoc radio networks do not have any backbone infrastructure, the hedonic CF algorithm is proposed to be executed at each node.

5.1 Proposed CF Algorithm

The CF algorithm can be initialized either in a singleton structure, with the initial network partition: \(\Pi _0=\left\{ \{1\},\{2\},\ldots , \{N\}\right\} \) or in a grand coalition: \(\Pi _0=\mathcal N=\left\{ 1,2,\ldots , N\right\} \). We propose to initialize the hedonic CF algorithm in a grand coalition based on the rationale that the random locations of nodes in ad hoc networks usually result in high interference among the communication links, and a network partition comprised of large size coalitions (coalitions with large number of players) are highly probable to emerge as a final stable network partition \(\Pi _f\). It is assumed that each player in the network is aware of the average external interference it experiences through measurements fed back from its receiver over a control channel.

The proposed CF algorithm is invoked by distributed players in the ascending order of their global index g. The algorithm completes one CF round when all the N players in the network have taken action (stay or switch) based on the underlying CF rule. Hence, one CF round consists of N iterations, where at each iteration, only one player can move from its current coalition to a new coalition. In this way, a CF round offers a sequence of network partition transitions as:

$$\begin{aligned} \Pi _{r-1,N}\rightarrow \Pi _{r,1}\rightarrow \Pi _{r,2}\rightarrow \cdots \rightarrow \Pi _{r,N}, \end{aligned}$$
(11)

where \(\Pi _{r,g}\) represents the partition formed after Player g takes action in its turn during CF Round r, and hence, \(\Pi _{r,N}\) indicates the network partition at the end of CF Round r.

In each partition transition, we assume the player to be opportunistic; i.e., a player g switches to the first coalition; \(S_l \in \Pi \cup \{~\}\), which it finds to be satisfying the underlying CF rule, while first checking \(S_l=\{~\}\) followed by all the coalitions \(S_l \in \Pi ,~\forall ~ l=1,2,\ldots ,|\Pi |\), and \(l\ne k\), in a round-robin fashion. Hence, the CF algorithm completes its iteration for player \(g \in \mathcal N\) when it finds a suitable coalition; \(S_l \in \Pi \cup \{~\}\), to switch to, or when after checking all switching possibilities, it prefers to stay in its current coalition; \(S_k \in \Pi \).

After iterating over all the players in the network, one round of the proposed CF algorithm concludes. The algorithm keeps on iterating over all the players in the network until all players decide to stay in their current coalition; i.e., \(\Pi _{r,g}=\Pi _{r-1,N},~\forall ~ g\in \mathcal N\) (which indicates that the algorithm has converged to a final stable network partition \(\Pi _f\)), or the CF process leads to a cycle (non-convergent state), in which case the distributed players at the end of certain CF round r, are self-organized into an already witnessed network partition at the end of some previous CF round \(r-s\); i.e., \(\Pi _{r,N}=\Pi _{r-s,N},~s=\{1,2,\ldots \,r\}\), where \(\Pi _{0,N}=\Pi _0\) specifies the initial network partition. For practical implementation of the proposed distributed CF algorithm and to determine the convergent/non-convergent final state of the algorithm with minimum computation and memory overhead, we propose the following CF protocol:

5.2 Implementation protocol

The coalition formation process starts from an initial network partition \(\Pi _0\), known to all players in the network such that each player \(g\in \mathcal N\) is aware of all the coalitions heads in \(\Pi _0\). During a CF Round r, Player \(g\in \mathcal N\) takes an appropriate action \(a_g\in A_g\) in Iteration g according to the underlying CF rule. The player informs other players about its action by broadcasting an action code through which each player in the network is informed of the resulting network partition \(\Pi _{r,g}\) and all the coalition heads therein. The action codes are pre-fixed bit sequences, that represent the index of the new coalition for switch, or all zeros for stay. Since, a player can switch to any one of the maximum \(N-1\) non-empty coalitions or it may prefer to stay in its current coalition, it is clear that log(N) bits are sufficient to encode the action of any player.

We illustrate the mechanism through which a player \(g\in \mathcal N\) decides to stay in its current coalition \(S_k\) under Partition \(\Pi \) or switch to \(S_l \in \Pi \cup \{~\},~l\ne k\) by defining the following 3-step protocol:

Step 1 Making the switching request Player \(g\in \mathcal N\) being Member \(i \in S_k\), \(S_k\in \Pi \) sends a switch-to request to the Head \(H^l\) of Coalition \(S_l \in \Pi \cup \{~\},~l\ne k\) by sharing its link-specific information over a dedicated control channel. For \(S_l=\{~\}\), Player g itself acts as the head of the proposed new singleton Coalition \(\{g\}\), and hence, no information exchange is required. For the proposed non-singleton new coalition \(\grave{S_l}=S_l\cup \{g\}\), the shared information includes: (a) the direct channel \(h_{ii}^{ll}=h_{ii}^{kk}\), (b) the interference \(I_g^{\{g\}}\) which is used later by the Head \(H^l\) to calculate the interference experienced by Player g as a Member of Coalition \(\grave{S_l}\), and (c) the current rate achieved by Player g being Member \(i \in S_k\), \(S_k\in \Pi \) as given by \(R_{i,\text {opt}}^{S_k}\).

If the underlying CF rule requires the approval from old coalition, Player \(g\in \mathcal N\) sends a switch-from request to its current Coalition Head \(H^k\) by indicating its local index i.

Step 2 Switching request evaluation Having received the switch-to request along with the required information from Player \(g\in \mathcal N\), Coalition Head \(H^l\) evaluates the feasibility of Player g switching from Coalition \(S_k\in \Pi \) to the proposed new Coalition \(\grave{S_l}=S_l\cup \{g\}\) under the proposed new network Partition \(\acute{\Pi }\!=\!\left\{ S_1,S_2,\cdots ,S_k\backslash \{g\},\cdots ,S_l\!\cup \!\{g\} ,\cdots ,S_{|\acute{\Pi }|}\right\} \). In this regard, \(H^l\) evaluates the interference experienced by all members of \(\grave{S_l}\in \acute{\Pi }\) which is used to determine the optimal BW fraction \(\mu _j^{\grave{S_l}}\) and ultimately the rate \(R_{j,opt}^{\grave{S_l}}\) for all the members \(j\in \grave{S_l}\), as required by the underlying CF rule. \(H^l\) approves/disapproves the switch-to request based on the individual preference of Player g, and if required, taking into consideration the effect of proposed switch action on the members of \(S_l\) according to the underlying CF rule.

Similarly, the switch-from request is handled by the Head \(H^k\) of old Coalition \(S_k\) by analyzing the effect of proposed switch action on the members of \(\acute{S_k}=S_k\backslash \{g\}\).

Step 3 Indicating the switching decision If the Player \(g \in \mathcal N\) switches from \(S_k\) to \(S_l\) , its entry is removed from the member list maintained by the head \(H^k\), added to the list maintained by \(H^l\) and both the Coalition Heads update the rates of each of their coalition members under the new partition. In this case, Player g broadcasts the action code indicating the index of Coalition \(S_l\), and the algorithm completes its CF-iteration for Player \(g \in \mathcal N\). The CF algorithm proceeds with the next player in the network, following the same 3-step protocol. On the other hand, if the switching action is not approved by the Head(s), the above protocol is repeated for the same Player g until it finds a suitable coalition \(S_l \in \Pi \) to switch to, or after checking all coalitions \(S_l \in \Pi \cup \{~\},~l\ne k\), it prefers to stay in its current Coalition \(S_k \in \Pi \), in which case, Player g broadcasts the action code consisting of all zeros, and the Player with the highest global index; i.e. Player N, responds by incrementing the locally maintained stay-counter by one.

At the end of CF round r; i.e., after iterating over all the players in the network, all players are aware of the current network Partition \(\Pi _{r,N}\). In addition, Player N knows (from stay-counter) the number of players that decide to stay in their coalition during the CF round r. If the stay-counter reads N, this indicates the end of CF game in a stable outcome where all the players prefer to stay in their coalition, converging to a final network partition \(\Pi _f=\Pi _{r,N}\).

To identify a CF cycle, a round-level partition history set; \(\mathcal P_{r^-}=\{\Pi _{0,N},\Pi _{1,N},\ldots ,\Pi _{r-1,N}\}\), containing all the network partitions before CF Round r, is maintained locally by the heads of all the coalitions, at the end of each CF round. In the beginning of the CF process, each coalition head saves \(\Pi _0\) in its round-level partition history set. At the end of CF Round r, all the coalition heads in \(\Pi _{r,N}\) check if \(\Pi _{r,N} \in \mathcal P_{r^-}\). The case \(\Pi _{r,N} \notin \mathcal P_{r^-}\) implies that \(\Pi _{r,N}\) is not an already witnessed network partition and hence the CF game continues to the next round with each coalition head saving \(\Pi _{r,N}\) in its round-level partition history set. On the other hand, if the coalition heads find \(\Pi _{r,N}\in \mathcal P_{r^-}\), the game ends in a CF cycle. Section 5.4 presents the proposed solutions for dealing with CF cycles.

The convergence of the proposed distributed CF algorithm strongly depends on the underlying CF rule. The following section discusses the convergence/stability properties of the proposed CF algorithm by analyzing the underlying CF rules according to their classes.

5.3 Convergence/stability properties

Theorem 1

Starting from any initial network partition \(\Pi _0\), the hedonic CF algorithm based on (s, indv, indv), and (s, altru, altru) preference relations always converges to a final network partition, \(\Pi _f\), which is stable and throughput efficient.

Proof

Given any initial starting partition \(\Pi _0\) and considering the CF algorithm based on (s, indv, indv), and (s, altru, altru) rules, the CF process consists of a sequence of network partition transitions:

$$\begin{aligned} \Pi _0\rightarrow \Pi _{1,N}\rightarrow \cdots \rightarrow \Pi _{r,N}\rightarrow \cdots ,\Pi _f, \end{aligned}$$
(12)

where \(\Pi _{r,N}\) represents the partition formed at the end of CF Round r such that during this round, at least one player \(g\in \mathcal N\) switches from its current coalition to a new coalition. Based on the definition of (s,indv,indv) and (s,altru,altru) CF rules (as given in Table 1), the switching action does not allow the distributed players to organize in a partition (in round-level partition history set) offering lower network rate as compared to the current network rate. As a result, (s,indv,indv) and (s,altru,altru) CF rules always result in a new network partition with improved network throughput. Since, the number of partitions of a set is finite (given by Bell number [17]), therefore the sequence of network partition transitions in (12) terminates after finite number of CF rounds. Hence, the proposed CF algorithms in this class always converge to a final network partition \(\Pi _f\).

Furthermore, both (s,indv,indv) and (s,altru,altru) rules provide a transition from \(\Pi \) to \(\acute{\Pi }\) such that the new network partition \(\acute{\Pi }\) always offers improved network throughput; i.e., \(\sum _k^{|\acute{\Pi }|}\mathcal {R}^{S_k} > \sum _k^{|\Pi |}\mathcal {R}^{S_k}\). Hence, the proposed CF algorithm based on these rules always yield a network-throughput efficient final partition; i.e., the distributed nodes in the ad hoc radio network converge to a stable network partition that offers the maximum network sum-rate, for the given sequence of network partition transitions based on (s,indv,indv) and (s,altru,altru) preference relations. \(\square \)

It is important to point out here that the CF algorithm based on (s,indv,indv) and (s,altru,altru) rules leads to contractual individual stability (CIS) [15], which is the most restrictive form of stability in CF games under consideration.

Remark 2

The algorithms based on CF rules in which the switching action does not guarantee a new network partition with improved network throughput (or any other network metric), may lead to a cycle, since a player \(g\in \mathcal N\) may find incentive to revisit a coalition in its coalition history set (set of all coalitions, that player g was a member of in the past but did not remain as its member because it, or some other coalition member, left the coalition) such that all the players get organized in an already encountered network partition at the end of some previous CF round.

Corollary 1

Starting from any initial network partition \(\Pi _0\), the hedonic CF algorithm based on (s, no, no), (s, indv, no) and (s, altru, no) rules is vulnerable to a CF cycle.

Illustration Consider a hedonic CF game with two players and the initial network partition \(\Pi _0=\{S_1,S_2\}=\{\{1\},\{2\}\}\) with the payoff vector \(\varvec{\psi }=[10,20]\). Furthermore, consider a possible transition to the network partition; \(\Pi _1=S_1=\{1,2\}\), with the payoff vector \(\varvec{\psi }=[11,19]\). For the considered game, the following preference relations exist:

$$\begin{aligned} \begin{aligned}&\{1,2\}\succ _{1,(s,no,no)}\{1\}\\&\{2\}\succ _{2,(s,no,no)}\{1,2\}\\ \end{aligned} \end{aligned}$$
(13)

It is conceivable that a CF cycle: \(\Pi _0\rightarrow \Pi _1\rightarrow \Pi _0\) exists in this game with length 2. In a similar manner, we can prove the existence of cycle (with minimum length 3) for CF algorithm based on (s, indv, no) and (s, altru, no) rules.

It is evident from the above discussion that the stability of hedonic CF algorithm based on (s, no, no), (s, indv, no) and (s, altru, no) rules cannot be guaranteed. However, if the distributed players converge to \(\Pi _f\) under (s, no, no) rule, the final network partition \(\Pi _f\) is said to be Nash stable (NS) [15], while the final network partition \(\Pi _f\) is said to be individual stable (IS) [15], if the distributed players converge to \(\Pi _f\) under (s, indv, no) or (s, altru, no) CF rule.

Based on the above discussion, CF rules that do not consider the effect of the movement of switching player, on both new and old coalition, are vulnerable to a cycle in the hedonic CF process which leads to instability. The following section presents two solutions to deal with CF cycle.

5.4 Dealing with CF cycle

A CF cycle indicates the non-convergent behavior of hedonic CF process in the sense that, instead of a single final network partition \(\Pi _f\), it offers multiple operating points in the form of a collection of network partitions \(\Pi _{cycle}\). For example, when \(\Pi _{r,N}=\Pi _{r-2,N}\), we get a CF cycle with length 2N, indicated as:

$$\begin{aligned} \begin{aligned} \Pi _{cycle}&=\Big \{\Pi _{r-2,N},\Pi _{r-1,1},\Pi _{r-1,2},\ldots ,\\&\quad \Pi _{r-1,N},\Pi _{r,1},\Pi _{r,2},\ldots \,\Pi _{r,N}=\Pi _{r-2,N}\Big \} \end{aligned} \end{aligned}$$
(14)

Typically, the existence of a CF cycle is attributed to the instability of the CF algorithm. The conventional approach to avoid cycles in the CF process is to modify the CF rules. In the following, we discuss such modifications in the proposed CF rules, to guarantee stability. Furthermore, we consider the case in which no variations are possible in the proposed rules, and describe different exit procedures from possible cycles by defining how to select \(\Pi _f\) from \(\Pi _{cycle}\) or how to operate over multiple points in \(\Pi _{cycle}\) if a CF cycle is inevitable.

5.4.1 Avoiding cycles in the CF process

Remark 2 identifies the visit to coalition history set h(g) by at least one player \(g \in \mathcal N\) as the necessary condition for the occurrence of CF cycle. Therefore, cycles can be avoided in the proposed hedonic coalition formation algorithm by incorporating the history condition [9, 10] in the generalized CF rule (given under Sect. 4.2.5). History condition implies that a player \(g \in \mathcal N\) under network partition \(\Pi \) can only propose to switch from its current Coalition \(S_k \in \Pi \) to another coalition \(S_l \in \Pi \cup \{~\},~l\ne k\) provided \(S_l\notin h(g)\). This can be accomplished by maintaining coalition history set at each player \(g\in \mathcal N\), which must be updated whenever a player switches from its current coalition to another coalition.

It is important to point out here that some prior works such as [11], limit the maximum number of revisits to same coalition, while others like [13], restrict the action space of players from merge-split to merge-only to avoid cycles in the CF process. However, we argue that using a history condition or restricting the action space of players, achieves stability at the cost of limited freedom of players in the network, and such approaches are not justified specially when players may find incentive to revisit a coalition in their coalition history set or prefer to split/switch from their current coalitions but are not allowed to. Therefore, it is interesting to analyze the behavior of players when no stability-forcing condition is imposed in the CF rules and discuss different exit procedures when the hedonic CF process leads to a cycle.

5.4.2 Exiting from cycles in the CF process

In the following, we present two fundamental approaches to deal with CF cycles: (1) operate over multiple network partitions through time-sharing or (2) select an appropriate operating point from the pool of multiple network partitions given by the hedonic CF algorithm.

The number of partitions in a CF cycle is an integer multiple of N, say kN. If \(\tau \) represents the total available transmission time, after which the CF process is invoked again to incorporate any change in the network conditions, we propose to divide \(\tau \) in kN equal duration transmission slots during which the network operates over kN network partitions. The main rationale behind operating over multiple network partitions through time-sharing is to provide fair chance to each player in the network to transmit when its preferred network partition is in place. This can be accomplished based on a predetermined time-sharing policy while the duration of each time slot can be readily calculated as \(\tau /(kN)\). However, it is important to point out here that network partition after each iteration, \(\Pi _{r,g}\), must be stored in the iteration-level partition history set to be maintained by all the players in the network, in order to know the multiple operating points when the CF process leads to a cycle. Furthermore, in order to operate over multiple network partitions, coalition heads in these partitions must save the optimal BW allocation for their members so that all the coalitions operate at maximum rate during their allocated time slot.

Alternatively, an appropriate operating point may be selected from \(\Pi _{cycle}\) to exit from the CF cycle. This would relief the players from saving/maintaining iteration-level partition history set, and the coalition heads from saving the optimal BW allocation for its members under all network partitions in \(\Pi _{cycle}\). However, an appropriate network partition can only be found after comparing all partitions in \(\Pi _{cycle}\) which requires all players to save their individual payoff (transmission rate) under all network partitions in \(\Pi _{cycle}\). Any randomly chosen player can take the responsibility to acquire the individual payoffs of all players under all network partitions and making the comparisons to identify an appropriate network partition. Furthermore, once the appropriate network partition is selected, coalition heads in this partition would have to optimally allocate the BW to their members to maximize their coalition sum-rate. The appropriate network partition may be selected from \(\Pi _{cycle}\) to satisfy any optimality criterion suitable for application at hand [15].

6 Probabilistic analysis of coalition formation

In this section, we present the probabilistic analysis of the stability of grand coalition and singleton structure. These probabilities will be used to evaluate a lower bound on the probability that a network partition, obtained through the proposed CF algorithm, that is neither GC nor SS, is stable. The probabilistic analysis shown in the following subsections considers the (s,no,no) CF rule. However, similar lines of derivations can be adopted for other CF rules.

6.1 Probability of GC being stable

Consider a network with N links operating in a grand coalition; i.e., \(\Pi _0=\mathcal N=\left\{ 1,2,\ldots ,N\right\} \) such that the global index g of each player/link in the network becomes same as its local index i in GC. This GC would be stable if each player \(g=i\in \mathcal N\) in the network prefers to stay in GC. Mathematically, this requires that no member of GC is capable of improving its rate by splitting from GC to act as a singleton Coalition \(\{i\} \in \dot{\Pi }_0,~\dot{\Pi }_0=\{\{i\},\mathcal N\backslash \{i\}\}\); i.e.,

$$\begin{aligned} P{(\text {GC is stable})}=P{\left( R_{i}^{\{i\}} < R_{i}^{\mathcal N}\right) } ~~~\forall ~ i\in \mathcal N, \end{aligned}$$
(15)

where the two rate equations to compare are given by:

$$\begin{aligned} R_{i}^{\{i\}}= & {} 1\times W \log \left( 1+\frac{P_i|h_{ii}|^2}{(N_0W+\sum _{j=1,j\ne i}^{N}P_j |h_{ji}|^2)}\right) ,\nonumber \\ R_{i}^{\mathcal N}= & {} \frac{1}{N}\times W \log \left( 1+\frac{P_i|h_{ii}|^2}{\frac{1}{N}\times (N_0W+0)}\right) , \end{aligned}$$
(16)

with \(P_i\) representing the transmission power of player \(g\in \mathcal N\) having local index i, and \(h_{ji}\) representing the channel between the transmitter of player j and the receiver of player i.

It is important to point out here that for simplicity of the analysis, we consider equal BW allocation among coalition members, while the total available bandwidth (W) is re-used by each coalition in the existing network partition.

These rate equations can be expressed in terms of random variables (RVs) by taking into consideration that all channels follow a quasi-static Rayleigh flat fading model and the transmitted power \(P_i\) is normalized to 1, while the channel coefficients are normalized by noise power \(N_0W\). Therefore, the rate equations can be expressed in a simplified form as:

$$\begin{aligned} R_{i}^{\{i\}}= & {} W \log \left( 1+\frac{X_i}{1+Y_i^{\{i\}}}\right) ,\nonumber \\ R_{i}^{\mathcal N}= & {} \frac{1}{N}W \log \left( 1+NX_i\right) , \end{aligned}$$
(17)

where, \(X_i\sim \alpha _i\exp (-\alpha _i x_i)\) is an exponentially distributed random variable, with \(1/\alpha _i\) representing the mean direct link SNR for player \(i\in \mathcal N\) and \(Y_i^{\{i\}}\) is the total interference observed at the receiver of link \(i\in \{i\}\) given by \(\sum _{j=1,j\ne i}^{N}Y_{ji}\) with \(Y_{ji}\sim \beta _{ji}\exp (-\beta _{ji} y_{ji})\), where \(1/\beta _{ji}\) represents the mean SNR observed at the receiver of link i due to the interference caused from link \(j\in \mathcal N, j\ne i\).

Since, all players decide, independently from each other, to stay/split from GC, the probability that GC is stable can be evaluated as the product, over all players \(i\in \mathcal N\), of the probability that a player i stays in GC, which can be obtained from (15) and (17). This can be written as:

$$\begin{aligned} \begin{aligned} P{(\text {GC is stable})}&=\prod _{i=1}^NP{(\text {player } i \text { stays in GC})}\\&=\prod _{i=1}^NP{\left( \left( 1\!+\frac{X_i}{1{+}Y_i^{\{i\}}}\right) < \left( 1{+}NX_i\right) ^\frac{1}{N}\right) .} \end{aligned} \end{aligned}$$
(18)

Probability that a player i prefers to stay in GC can be further simplified by using the total probability theorem [18] and exploiting the statistical independence between the RVs \(X_i\) and \(Y_i^{\{i\}}\) as:

$$\begin{aligned}&P{(\text {player } i \text { stays in GC})}\nonumber \\&=\int _{0}^{\infty }P{\left( \left( \left( 1+\frac{X_i}{1+Y_i^{\{i\}}}\right) < (1+NX_i)^\frac{1}{N}\right) \mid X_i=x_i\right) }\nonumber \\&\quad \times ~f_{X_i}(x_i)dx_i\nonumber \\&=\int _{0}^{\infty }\left( 1-F_{Y_i^{\{i\}}}\left( \frac{x_i}{(1+Nx_i)^\frac{1}{N}-1}-1\right) \right) \nonumber \\&\quad \times ~\alpha _i\exp (-\alpha _i x_i)dx_i, \end{aligned}$$
(19)

where \(F_{Y_i^{\{i\}}}(y_i)=\int _0^{y_i} f_{Y_i^{\{i\}}}(\xi )d\xi \) is the probability distribution function of the sum of exponentials, \(Y_i^{\{i\}}=\sum _{j=1,j\ne i}^{N-1}Y_{ji}\). We can evaluate (see “Appendix”) this distribution function for the general case of distinct \(\beta _{ji}~\forall ~ i,j\) to be:

$$\begin{aligned}&F_{Y_i^{\{i\}}}(y_i)\nonumber \\&=\left( \prod _{j=1,j\ne i}^{N}\beta _{ji}\right) \left( \sum _{j=1,j\ne i}^{N}\frac{1-exp(-\beta _{ji}y_{i})}{\beta _{ji}\prod _{l=1,l\ne i,j}^{N}\left( \beta _{li}-\beta _{ji}\right) }\right) ,\nonumber \\ \end{aligned}$$
(20)

and for the simple case of IID interferers where, \(\beta _{ji}=\beta ~\forall ~ i,j\) as:

$$\begin{aligned} F_{Y_i^{\{i\}}}(y_i)=1-\frac{\Gamma (N-1,\beta y_i)}{\Gamma (N-1)}. \end{aligned}$$
(21)

Using these distribution functions, (18), and (19), the probability of GC is stable, for the most general case of different \(\alpha _i,~\forall ~i\in \mathcal N\) and different \(\beta _{ji},~\forall ~i,j\in \mathcal N\), is given by:

$$\begin{aligned}&P{(\text {GC is stable})}=\prod _{i=1}^N\int _{0}^{\infty }\left( 1-\left( \prod _{j=1,j\ne i}^{N}\beta _{ji}\right) \right. \nonumber \\&\left. \quad \times ~\left( \sum _{j=1,j\ne i}^{N}\frac{1-exp\left( -\beta _{ji}\left( \frac{x_i}{(1+Nx_i)^\frac{1}{N}-1}-1\right) \right) }{\beta _{ji}\prod _{l=1,l\ne i,j}^{N}\left( \beta _{li}-\beta _{ji}\right) }\right) \right) \nonumber \\&\quad \times ~\alpha _i\exp (-\alpha _i x_i)dx_i. \end{aligned}$$
(22)

while, if we consider \(\alpha _i=\alpha ,~\forall ~i\in \mathcal N\) and \(\beta _{ji}=\beta ,~\forall ~i,j\in \mathcal N\), the probability that GC is stable can be evaluated as:

$$\begin{aligned}&P{(\text {GC is stable})}\nonumber \\&=\left[ \displaystyle \int _{0}^{\infty }\left( \frac{\Gamma \left( N-1,\beta \left( \frac{x}{(1+Nx)^\frac{1}{N}-1}-1\right) \right) }{\Gamma (N-1)}\right) \alpha \exp (-\alpha x)dx\right] ^N.\nonumber \\ \end{aligned}$$
(23)

6.2 Probability of SS being stable

Proceeding on similar lines to Sect. 6.1, the network partition \(\Pi _1=\left\{ {S_1},{S_2},\ldots ,{S_N}\right\} \), with \(S_i=\{i\}\), would be stable if each player in the network prefers to stay singleton. Mathematically, this requires that no player \(i\in S_i, S_i \in \Pi _1\) is capable of improving its rate by merging with any other coalition \(S_k\in \Pi _1, k\ne i\) to make a new coalition \(S_{(ik)}=S_i\cup S_k=\{i,k\} \in \ddot{\Pi }_1\) where \(\ddot{\Pi }_1=\left\{ \bar{S}_{(ik)},\{i,k\}\right\} , \bar{S}_{(ik)}=\Pi _1\backslash \{i\}\backslash \{k\}\); i.e.,

$$\begin{aligned} \begin{aligned}&P{(\text {SS is stable})}\\&=\prod _{i=1}^N\prod _{k=1,k\ne i}^N P{\left( R_{i}^{\{i,k\}}< R_{i}^{\{i\}}\right) }\\&=\prod _{i=1}^N\prod _{k=1,k\ne i}^N\\&\quad P{\left( \left( 1+\frac{2X_i}{1+Y_i^{\{i,k\}}}\right) ^{0.5} < \left( 1+\frac{X_i}{1+Y_i^{\{i,k\}}+Y_{ki}}\right) \right) . } \end{aligned} \end{aligned}$$
(24)

where \(X_i\sim \alpha _i\exp (-\alpha _i x_i)\) and \(Y_i^{\{i\}}\), are the same RVs that were used in Sect. 6.1, along with an additional RV \(Y_i^{\{i,k\}}=\sum _{j=1,j\ne i,k}^{N}Y_{ji}\) with \(Y_{ji}\sim \beta _{ji}\exp (-\beta _{ji} y_{ji})\) which can be derived from \(Y_i^{\{i\}}\) as: \(Y_i^{\{i,k\}}=Y_i^{\{i\}}-Y_{ki}\).

Similar to Sect. 6.1, we can evaluate the probability that SS is stable, for the most general case of different \(\alpha _i,~\forall ~i\in \mathcal N\) and different \(\beta _{ji},~\forall ~i,j\in \mathcal N\), as:

$$\begin{aligned} \begin{aligned}&P{(\text {SS is stable})}\\&=\prod _{i=1}^N\prod _{k=1,k\ne i}^N\int _{\acute{y}_i=0}^{\infty }\int _{x_i=0}^{\infty }\\&\quad \left( 1-\exp \left( \beta _{ki}\left( \frac{x_i}{\left( 1+\frac{2x_i}{1+\acute{y}_i}\right) ^{0.5}-1}-1-\acute{y}_i\right) \right) \right) \\&\quad \times ~\alpha _i\exp (-\alpha _i x_i)\left( \prod _{j=1,j\ne i,k}^{N}\beta _{ji}\right) \\&\quad \times ~\left( \sum _{j=1,j\ne i,k}^{N}\frac{\exp (-\beta _{ji}\acute{y}_{i})}{\prod _{l=1,l\ne i,j,k}^{N}\left( \beta _{li}-\beta _{ji}\right) }\right) dx_id\acute{y}_i, \end{aligned} \end{aligned}$$
(25)

while, if we consider \(\alpha _i=\alpha ~\forall ~i\in \mathcal N\) and \(\beta _{ji}=\beta ,~\forall ~i,j\in \mathcal N\), the probability that SS is stable is given by:

$$\begin{aligned}&P{(\text {SS is stable})}\nonumber \\&=\left[ \int _{\acute{y}_i=0}^{\infty }\int _{x_i=0}^{\infty }\right. \nonumber \\&\quad \left( 1-\exp \left( \beta \left( \frac{x_i}{\left( 1+\frac{2x_i}{1+\acute{y}_i}\right) ^{0.5}-1}-1-\acute{y}_i\right) \right) \right) \alpha \exp (-\alpha x_i)\nonumber \\&\left. \quad \times ~\left( \frac{\beta ^{N-2}}{\Gamma (N-2)}(\acute{y}_i)^{N-3}\exp {(-\beta \acute{y}_i)}\right) dx_id\acute{y}_i\right] ^{N(N-1)}.\nonumber \\ \end{aligned}$$
(26)

Proof is omitted due to space limitation. However, the probability density function \(f_{Y_i^{\{i,k\}}}(\acute{y}_i)\) for the general case of distinct \(\beta _{ji}~\forall ~ i,j\), is evaluated in “Appendix”.

6.3 Probability of a general network partition being stable

The probabilities of GC and SS being stable can be used to derive a lower bound on the probability that the resulting stable coalition is neither GC nor SS. Mathematically;

$$\begin{aligned} \begin{aligned}&P{(\text {resulting stable coalition is neither GC nor SS})}\\&> 1- P{(\text {GC is stable})} -P{(\text {SS is stable})}. \end{aligned} \end{aligned}$$
(27)

where \(P{(\text {GC is stable})}\) and P(SS is stable) are given by (22), (25), respectively, for the case of different \(\alpha _i~\forall ~i\in \mathcal N\) and different \(\beta _{ji},~\forall ~i,j\in \mathcal N\), and by (23), (26), respectively, for the case of \(\alpha _i=\alpha ,~\forall ~i\in \mathcal N\) and \(\beta _{ji}=\beta ,~\forall ~i,j\in \mathcal N\).

7 Performance evaluation

In this section, we evaluate the performance of the proposed CF algorithm by examining the average payoff (rate in Mbps) per link and analyzing the effect of different proposed CF rules on the algorithm convergence properties. We assume that the total bandwidth W available for access is 5 MHz. All the channels are assumed to follow a quasi-static Rayleigh flat fading model, and hence the received signal power, interference power and signal to noise ratio (SNR) are exponentially distributed. The presented simulation results are obtained using MATLAB R2013a and averaged over 100,000 channel realizations to analyze the average achievable rate per link. The transmit power \(P_i\) and noise power spectral density (\(N_0\)) are normalized to 1, and their effects are included in the channel coefficients. We analyze the performance for \(N=10\) randomly distributed links over a wide range of average direct link SNR with the mean of the interference power among the links to be uniformly distributed between \([-10,0]\) dB.

Fig. 2
figure 2

Average payoff per link: GC initialization

Full size image
Fig. 3
figure 3

Average payoff per link: SS initialization

Full size image

7.1 Average payoff per link under different CF rules

Figures 2 and 3 show the average payoff (rate in Mbps) per link offered by the proposed CF algorithm with optimal BW allocation under different CF rules, when the CF process is initialized in a grand coalition (GC) and in a singleton structure (SS), respectively. The achievable rate is compared with three benchmark cases: (1) equivalent distributed implementation of globally optimal centralized solution, which we call global altruistic (GlobAltru) CF rule, where, players switch from one coalition to another coalition with the objective of maximizing the network sum-rate, irrespective of the effect on their individual rates, (2) always GC/SS, and (3) CF with equal BW allocation. Furthermore, (s,indv,no) rule mimics the CF philosophy of famous merge-split process for single player movement [13, 14], and hence provides an important comparison with an existing CF approach applied to our settings.

Our results indicate that, in general, the average payoff/rate per link increases with increasing the average direct link SNR. However, the initial network partition and the switching degree of freedom offered by the underlying CF rule, determine the size and number of coalitions in the final network partition and ultimately the actual rate achieved per link, specially at low SNR. Typically, the distributed players experience high interference when the average direct link SNR is low, and hence they prefer to stay together, while interference is low at high SNR, and hence players gain more if they separate from large coalitions. This is evident from Figs. 2 and 3, which show that distributed players prefer to make a GC for \(SNR\le -5\) dB, while the players tend to arrange themselves in small coalitions over high SNR regime (\(SNR\ge 5\) dB), providing \(92\%\) of the maximum achievable rate (given by GlobAltru rule) at \(SNR=5\) dB, which increases further with direct link SNR improvement. This is true for all CF rules with the exception of (s,indv,indv) rule initialized in GC, which seldom allows players to leave their initial coalition (GC), and hence, for \(SNR>0\) dB, this rule offers a degraded average rate per link compared to other CF rules. On the other hand, when the CF algorithm is initialized in SS, different CF rules offer lower average rates (at low SNR) than the achievable maximum rate. This indicates that, starting from SS (Fig. 3), distributed players do not reach the rate-maximizing GC under any of the CF rules even at \(SNR\le -5\) dB. In fact, (s,altru,no) performs best among all proposed CF rules in low SNR regime by providing \(89\%\) of the maximum achievable rate at \(SNR=-5\) dB, but the rate drops to \(81\%\) of the maximum achievable value at \(SNR=0\) dB.

It is important to highlight that GlobAltru rule which is the equivalent distributed implementation of globally optimal centralized sum-rate maximizing rule, when the proposed distributed CF algorithm is initialized in GC (Fig. 2), does not provide the maximum rate at low SNR (\(SNR\le 0\) dB) in case of SS initialization (Fig. 3). This means that starting from SS, distributed players fail to make a sum-rate maximizing GC at low SNR. This can be explained based on the fact that since the distributed implementation of proposed hedonic CF algorithm allows only a single player movement at a time to improve the network sum-rate, the distributed players are vulnerable to fall in a local maximum while trying to reach the global maximum sum-rate. As a result, GC might not be reachable starting from SS by increasing the coalition size by maximum one player in each iteration of the CF algorithm. In fact, a closer look at Fig. 3 shows that starting from SS, (s,indv,indv), (s,altru,altru) and (s,indv,no) CF rules seldom allow the distributed players to merge together into large coalitions and hence achieve approximately the same average rate per link as in the initial SS.

Furthermore, our results show that optimal BW allocation offers higher average rate per link as compared to equal BW allocation among the coalition members. The performance gain is depicted in Figs. 2 and 3 by comparing average rate per link in always-grand coalition under optimal and equal BW allocation. It can be seen that optimal BW allocation provides \(12\%\) more average rate per link as compared to equal BW allocation for \(SNR\ge 0\) dB. However, the rate improvement diminishes as the average direct link SNR falls below 0 dB. This can be explained by arguing that at low SNR (<0 dB), all the distributed players in GC observe very similar channel conditions which results in optimal BW allocation to be approximately same as equal BW allocation.

Since, initialization of the proposed hedonic CF algorithm in GC offers more flexibility to distributed players to form rate-improving coalitions over a wide SNR range, as compared to initialization in SS, the following results assume GC initialization, unless otherwise stated.

Fig. 4
figure 4

Useful operating SNR range of the proposed CF algorithm based on (s,no,no) CF rule

Full size image

7.2 Effectiveness of the proposed CF algorithm

Under the assumption that a stable network partition exists, Fig. 4 shows the probability of GC and SS being stable and use these probabilities to evaluate a lower bound on the probability that a general network partition, other than GC and SS, is stable against a wide range of average direct link SNR. Our results indicate that, with probability approaching 1, GC is stable at reasonably low SNR (\(\le -10\) dB), while SS becomes stable at quite high SNR (\(\ge \)50 dB). However, over (−2.5 dB\(\le SNR\le \) 23 dB), both GC and SS do not remain stable and a general network partition emerges with the probability >0.5, which shows the effectiveness of proposed CF algorithm for moderate operating SNR.

Fig. 5
figure 5

Fairness comparison among different CF rules

Full size image

7.3 Fairness

Figure 5 shows the average variance among the payoffs of distributed players under different CF rules. In general, variance among the payoffs increases with increasing the SNR. Our results show that the proposed CF rules offer fair distribution of payoffs among players at low SNR when the final network partition consists of coalitions of large sizes, while large variance among the payoffs is observed at high SNR, as the distributed players prefer to operate in small coalitions. The uniform and relatively fair behavior of all CF rules in low SNR regime stems from the fact that distributed players under all CF rules achieve almost the same payoff (as evident from Fig. 2) with low variance by staying in their initial GC for \(SNR\le -5\) dB where the optimal BW allocation numerically approaches the equal BW allocation. However, at high SNR, the difference in fairness offered by different proposed CF rules becomes evident when distributed players tend to operate in small coalitions wherein the achievable payoff strongly depends on the size and number of coalitions in the network. As expected, CF rules that care about the altruistic payoff are found to be unfair with high variance, while rules with individual preferences happen to be more fair and with a lower variance among payoffs of different players. This indicates that CF rules based on altruistic approvals sacrifice fairness to achieve higher network rate.

Fig. 6
figure 6

Computational complexity comparison among different CF rules

Full size image

7.4 Computational complexity

The computational complexity of the proposed CF algorithm under different CF rules is depicted in Fig. 6 in terms of average number of CF proposals evaluated per link before exiting the CF process. It is evident that at low SNR, CF algorithm initialized in GC evaluates small number of CF proposals to reach the final network partition, since distributed players prefer to make large coalitions, while at high SNR, distributed players tend to organize in small coalitions, and hence small number of proposals are evaluated per link with SS initialization. Furthermore, Fig. 6 shows that strict CF rules (s,indv,indv) and (s,altru,altru), that require the approval of both new and old coalition before switching, are computationally less expensive than relaxed CF rules (s,altru,no), and (s,indv,no) that rely on the approval of new coalition only. This holds true over a wide SNR range for both GC and SS initializations. This can be explained based on the fact that strict CF rules reach equilibrium faster than relaxed rules since switching is expected to occur with low probability due to the strong restrictions.

Fig. 7
figure 7

Average payoff per link comparisons when operating over single/multiple operating points

Full size image

7.5 Achieving stability through history condition

Figure 7 focuses on CF algorithm (initialized in SS) based on (s,no,no) rule, and highlights the effect of history condition (resulting in a single stable operating point) on the average achievable payoff per link. Three exit strategies are compared for the case when CF process ends up in a cycle. The three exit options considered are: (1) operating over multiple operating points through time sharing (TS), (2) operating over a network partition offering maximum sum-rate (MAX), and (3) operating over the first network partition (FP) in the cycle.

Our results show that the three proposed exit options, with different degrees of computational complexity, result in very close average payoff per link over a wide range of SNR. However, in comparison to different exit procedures, CF algorithm incorporating history condition provides an improved average payoff per link for \(SNR<3\) dB after which its performance starts degrading. This can be explained based on the fact that history condition prohibits a player (initially operating singleton under (s,no,no) CF rule) to remain singleton if any other player finds incentive to merge with it. As a result, CF process incorporating history condition yields relatively big coalitions in the network. This goes in favor at low SNR (<3 dB), where distributed players achieve higher average payoff in big coalitions. However, at high SNR (>3 dB), average payoff per link is reduced when the distributed players are forced to share BW with other coalition members against their preference. In this way, the history condition offers stability at high SNR at the cost of reduced average payoff per link.

8 Conclusions

In this paper, the problem of joint coalition formation and bandwidth allocation in ad hoc radio networks was modeled as a hedonic CF game with non-transferable utility. An efficient CF algorithm was devised through which distributed nodes are self-organized based on individual/group rate improvement. A closed form expression for the optimal bandwidth allocation was derived for the proposed CF algorithm which was shown to provide substantial payoff gains for moderate operating SNR. Different preference relations/rules for the hedonic game were proposed with varying degrees of strictness and computational complexity. The convergence/stability properties of the proposed rules were studied. For the relaxed CF rules that may lead to cycles during CF process, the history condition was introduced in hedonic CF algorithm to guarantee Nash-stability, and different exit procedures were described when a CF cycle is inevitable. Furthermore, a probabilistic analysis of the stability of GC and SS was provided to prove the effectiveness of the proposed CF algorithm.