Walid Saad
email: saad@unik.no.

Zhu Han

Mérouane Debbah
email: merouane.debbah@supelec.fr.

Are Hjørungnes

A Selfish Approach to Coalition Formation among Unmanned Air Vehicles in Wireless Networks

Autonomous agents such as unmanned aerial vehicles (UAVs) have a great potential for deployment in next generation wireless networks. While current literature has been mainly focused on the use of UAVs for connectivity enhancement and routing in military ad hoc networks, this paper proposes a novel usage model for UAVs in wireless communication networks. In the proposed model, a number of UAVs are required to collect data from a number of randomly located tasks and transmit this data wirelessly to a common receiver (such as the central command). Each task represents a queue of packets that require collection and transmission to the central receiver. The problem is modeled as a hedonic coalition formation game between the UAVs and the tasks that interact in order to form disjoint coalitions. Each formed coalition is modeled as a polling system consisting of a number of UAVs, designated as collectors, which act as a single server that moves between the different tasks present in the coalition, collects and transmits the packets to a common receiver. Within each coalition, some UAVs can also take the role as a relay for improving the packet success rate of the transmission. The proposed coalition formation algorithm allows the tasks and the UAVs to take local selfish decisions to join or leave a coalition, based on the achieved benefit, in terms of effective throughput, and the cost in terms of delay. Simulation results show how the proposed algorithm allows the UAVs and tasks to self-organize into independent coalitions, while improving the performance, in terms of average player (UAV or task) payoff, of at least 61.96% relatively to a scheme that allocates nearby tasks equally among UAVs.

I. INTRODUCTION

Next generation wireless networks will present a highly complex and dynamic environment. This is mainly due to the recent emergence of large-scale, distributed and heterogeneous communication systems which are continuously increasing in size, traffic, applications, services, etc. For maintaining a satisfactory operation of such networks, there is a constant need for dynamically optimizing their performance, monitoring their operation and reconfiguring their topology. Due to the ubiquitous nature of such wireless networks, it is inherent to have selforganizing autonomous nodes (agents), that can service these networks at different levels such as data collection, monitoring, optimization, management, maintenance, among others [START_REF] Debbah | Mobile flexible networks: The challenges ahead[END_REF][START_REF] Niyato | Dynamic spectrum access in cognitive radio networks[END_REF][START_REF] Kauffmann | Measurement-based self organization of interfering 802.11 wireless access networks[END_REF][START_REF] Akella | Self management in chaotic wireless deployments[END_REF]. These nodes belong to the authority maintaining the network, and must be able to survey large scale networks, and perform very specific tasks at different points in time, in a distributed and This work was done during the stay of Walid Saad at the Coordinated Science Laboratory, University of Illinois at Urbana-Champaign and was supported by the Research Council of Norway through projects 183311/S10, 176773/S10, and 18778/V11. autonomous manner, with very little reliance on any centralized authority [START_REF] Debbah | Mobile flexible networks: The challenges ahead[END_REF], [START_REF] Niyato | Dynamic spectrum access in cognitive radio networks[END_REF].

While the use of such autonomous agents has been thoroughly investigated in robotics, control systems or software engineering, research models that tackle the use of such agents in wireless communication networks are rare. However, the need for such nodes in wireless networks has become of noticeable importance as many next generation networks are self-adapting [START_REF] Debbah | Mobile flexible networks: The challenges ahead[END_REF][START_REF] Niyato | Dynamic spectrum access in cognitive radio networks[END_REF][START_REF] Kauffmann | Measurement-based self organization of interfering 802.11 wireless access networks[END_REF][START_REF] Akella | Self management in chaotic wireless deployments[END_REF]. The main existing contributions in this area, within wireless networking, are focused on deploying unmanned aerial vehicles (UAVs) which can act as autonomous agents (nodes) in the network. In fact, in the past decade, UAVs have played a prominent role as self-deploying autonomous nodes that can efficiently perform pre-assigned tasks in numerous applications. With the emergence of small "mini-UAVs" (MUAVs) that offer advantages in flexibility and cost [START_REF] Beard | autonomous vehicle technologies for small fixed wing UAVs[END_REF], the usage scenarios for UAVs have significantly increased. In wireless networks, there has been several contributions that tackle the use of UAVs in connectivity improvement [START_REF] Han | Optimization of MANET connectivity via smart deployment/movement of unmanned air vehicles[END_REF], routing [START_REF] Gu | UAV aided intelligent routing for ad hoc wireless network in single area theater[END_REF], [START_REF] Xu | landmark routing in large wireless battlefield networks using UAVs[END_REF], and medium access control [START_REF] Gu | C-ICAMA, a centralized intelligent channel assigned multiple access for multi-layer ad-hoc wireless networks with UAVs[END_REF].

Mainly, these contributions focus on centralized solutions for specific problems such as finding the optimal locations for the deployment of UAVs or devising efficient routing algorithms in ad hoc networks in the presence of one or more UAVs. Hence, in existing work, the tasks that the UAVs must accomplish are pre-assigned and pre-determined. In contrast, many applications require agents, such as UAVs, to autonomously perform specific tasks that are randomly generated and are not pre-assigned. In such applications, the objective is to provide algorithms that allow the agents to share the tasks among each other with little dependence on centralized entities. Several research activities studied this task allocation problem among autonomous agents, mainly in either robotics control [START_REF] Gerkey | A formal framework for the study of task allocation in multi-robot systems[END_REF][START_REF] Alighanbari | Robust decentralized task assignment for cooperative uavs[END_REF][START_REF] Stipanovic | Cooperative avoidance control for multi-agent systems[END_REF], or software systems [START_REF] Chen | Multi-agent cooperation, dynamic workflow and XML for e-commerce automation[END_REF], [START_REF] Shehory | Methods for task allocation via agent coalition formation[END_REF]. However, most of these models are unsuitable for task allocation problems in the context of wireless networks due to various reasons: (i)-The task allocation problems studied in existing literature are mainly tailored for military operations or software engineering, (ii)-the tasks are generally considered as abstract entities with very simple characteristics, and (iii)-the existing models do not consider any wireless communication networks aspect such as the characteristics of the wireless channel, the presence of data traffic, the need for wireless data transmission, or other wireless-specific aspects.

The main contribution of this paper is to propose a novel wireless communication-oriented model for the problem of task allocation among a number of autonomous agents such as UAVs.

The proposed model considers a number of UAVs that are required to collect data from randomly located tasks. Each task represents a source of data, i.e., a queue with a Poisson arrival of packets, that the UAVs must collect and transmit via a wireless link to a central receiver. This formulation is deemed suitable to model several problems in next generation networks such as video surveillance in wireless networks, selfdeployment of mobile relays in IEEE 802.16j networks, data collection in ad hoc networks, wireless monitoring of randomly located sites, and many other applications. For allocating the tasks, we introduce a novel framework from coalitional game theory, known as hedonic coalition formation. Albeit hedonic games have been widely used in game theory, to the best of our knowledge, no existing work utilized this framework in a communication or wireless environment. Thus, we model the task allocation problem as a hedonic coalition formation game between the UAVs and the tasks, and we propose an algorithm for forming coalitions. Each formed coalition is modeled as a polling system consisting of a number of UAVs, designated as collectors, which act as a single server that moves continuously between the different tasks (queues) present in the coalition, gathering and transmitting the collected packets to a common receiver. Further, within each coalition, some UAVs can act as relays for improving the packet success rate during the wireless transmission. For forming coalitions, the UAVs and tasks can autonomously make a decision to join or leave a coalition based on well defined individual preference relations. These preferences are based on a coalition value function that takes into account the benefits received from servicing a task, in terms of effective throughput (data collected), as well as the cost in terms of the polling system delay incurred from the time needed for servicing all the tasks in a coalition. Simulation results show how the proposed algorithm allows the network to self-organize, while ensuring a performance improvement of at least 61.96%, in terms of average player (task or UAV) payoff, compared to a scheme that assigns nearby tasks equally among the UAVs. The remainder of this paper is organized as follows: Section II presents and motivates the proposed system model. In Section III, we model the task allocation problem as a hedonic coalition formation game, we discuss its key properties and we propose an algorithm for coalition formation. Simulation results are presented, discussed and analyzed in Section IV. Finally, conclusions are drawn in Section V.

II. SYSTEM MODEL

Consider a network consisting of M agents, e.g., UAVs, that belong to a single operator and are controlled by a central base station, e.g., command center. The UAVs are required to service T tasks that are randomly located in the geographic area around the base station (BS). We denote the set of UAVs, and tasks by M = {1, . . . , M }, and T = {1, . . . , T }, respectively. We assume that, in general, the number of tasks is larger than the number of UAVs, hence, M > T . The main motivation behind this assumption is that, for most networks, the number of UAVs is generally small due to cost factors for example. Each task i ∈ T represents an M/D/1 queueing system1 , whereby packets of constant size B are generated using a Poisson arrival with an average arrival rate of λ i . Hence, in the proposed model, we consider different classes of tasks each having its corresponding λ i . These tasks can represent a group of mobile devices that require servicing, data generated from video surveillance, data that must be collected by the UAVs, or any other source of packet data. For servicing a task, each UAV is required to move to the task location, collect the data, and transmit it using a wireless link to the centralized base station. Each UAV i ∈ M offers a link transmission capacity of µ i , in packets/sec, with which the UAV can service the data from any of the tasks. Hence, the quantity 1 µi would represent the well known service time for a single packet that is being serviced by a UAV i. The UAV which is collecting the data from a task is referred to as collector. In addition, each UAV i ∈ M can transmit the data to the receiver with a maximum transmit power of P i = P , assumed the same for all UAVs (without loss of the generality for the analysis in the remainder of this paper).

The proposed model allows each task to be serviced by multiple UAVs, and also, each UAV (or group of UAVs) to service multiple tasks. Whenever a task is serviced by multiple UAVs, each UAV can act as either a collector or a relay. Any group of UAVs that act together for data collection from the same task, can be seen as a single collector with improved link transmission capacity. In this context, given a group of UAVs G ⊆ M that are acting as collectors for a task i ∈ T , the total link transmission capacity with which task i is being serviced with by G can be given by

µ i G = j∈G µ j , (1)
For forming a single collector, multiple UAVs can easily coordinate the data extraction, and then transmission from every task, so as to allow a larger link transmission capacity for the serviced task as per [START_REF] Debbah | Mobile flexible networks: The challenges ahead[END_REF]. Moreover, the transmission of the packets by the UAVs from a task i ∈ T to the central receiver is subject to packet loss due to the fading on the wireless channel. In this regard, in addition to acting as collectors, some UAVs may act as relays for a task. For doing so, we assume that one or more UAVs position themselves at equal distances from the task (given that the task is already being served by at least one collector), and hence, the collectors transmit the data to the receiver through multi-hop UAVs, improving the probability of successful transmission. In this context, in Rayleigh fading, the probability of successful transmission of a packet of size B from the collectors present at a task i ∈ T through a path of m UAVs, Q i = {i 1 , . . . , i m }, where i 1 = i is the task being serviced, i m is the BS, and any other i h ∈ Q i is a relay-UAV, can be given by where P r i h i h+1 is the the probability of successful transmission of a single bit from a UAV i h to a UAV (or the BS) i h+1 and can be given by the probability of maintaining the SNR at the receiver above a target level γ 0 as follows [START_REF] Proakis | Digital Communications[END_REF] P r i,i h+1 = exp -

P r i,BS = m-1 h=1 P r B i h i h+1 (2)
σ 2 γ 0 (D i h ,i h+1 ) α κ P (3)
where σ 2 is the Gaussian noise, κ is a path loss constant, α is the path loss exponent, D i h ,i h+1 is the distance between nodes i h and i h+1 , and P is the maximum transmit power of UAV i h .

For servicing a number of tasks C ⊆ T , a group of UAVs G ⊆ M (collectors and relays) can sequentially move from one task to the other in C with a constant velocity ν. The UAVs stop at each task, with the collectors collecting and transmitting the packets using the relays (if any). The collectors would move from one task to the other, only if all the packets in queue in the current task have been transmitted to the receiver. With this proposed model, the final network will consist of groups of tasks serviced by groups of UAVs, continuously. An illustration of this model is shown in Figure 1.

Consequently, given this proposed model, the main objective is to provide an algorithm for distributing the tasks between the UAVs, given the operation of the UAVs previously described and shown in Figure 1. For this purpose, the following sections formulate a game theoretic approach for autonomously forming a network similar to that of Figure 1.

III. UAVS TASK ALLOCATION AS A HEDONIC COALITION FORMATION GAME

In this section, we formulate the proposed task allocation problem as a hedonic coalition formation game with an underlying transferable utility, and we propose a distributed algorithm for forming the coalition using concepts from hedonic games.

A. Initial Coalitional Game Formulation

By inspecting Figure 1, one can clearly see that the task allocation problem among the UAVs can be mapped into the problem of the formation of coalitions. In this regard, coalitional game theory [16, Ch. 9] provides a suitable analytical tool for studying the formation of cooperative groups, i.e., coalitions, among a number of players. For the proposed model, the coalitional game is played between the UAVs and the tasks. Hence, the players set for the proposed task allocation coalitional game is denoted by N , and contains both UAVs and tasks, i.e., N = M ∪ T . In the remainder of this paper, we use the term player to denote either a task or a UAV.

For any coalition S ⊆ N containing a number of UAVs and a number of tasks, the UAVs belonging to this coalition can structure themselves into collectors and relays. Subsequently, as explained in the previous section, within each coalition, the collector-UAVs will move from one task to the other, stopping at each task, and transmitting all the packets available in the queue to the central receiver, through the relay-UAVs (if any). This proposed task servicing scheme can be mapped to a wellknown concept that is ubiquitous in computer systems, which is the concept of a polling system [START_REF] Takagi | Analysis of Polling Systems[END_REF]. In a polling system, a single server moves between multiple queues in order to extract the packets from each queue, in a sequential manner. Models pertaining to polling systems have been widely developed in various disciplines ranging from computer systems to communication networks, and different strategies for servicing the queues exist [START_REF] Takagi | Analysis of Polling Systems[END_REF][START_REF] Levy | Polling systems: applications, modeling, and optimization[END_REF][START_REF] Li | Performance analysis of a dual round robin matching switch with exhaustive service[END_REF][START_REF] Vishnevsky | The power-series algorithm for twoqueue polling system with impatient customers[END_REF]. For the proposed model, we map every coalition S to a polling system with exhaustive strategy and deterministic switchover times. For instance, the collectors of every coalition in our model can be seen as a server that is servicing the tasks (queues) sequentially, in a cyclic manner, i.e., after servicing the last task in a coalition S ⊆ N , the collectors of S return to the first task in S that they previously visited hence repeating their route continuously. Further, whenever the collectors stop at any task i ∈ S, they collect and transmit the data present at this task until the queue is empty. This method of allowing the server to service a queue until emptying the queue is known as the exhaustive strategy for a polling system, which is applied in every coalition of our model. Moreover, the time for the server to move from one queue to the other is known as the switchover time. In our model, for any coalition S, once the queue at a task i ∈ S is emptied, the collectors and relays in a coalition move from task i to the next task j ∈ S with a constant velocity ν, hence incurring a switchover time θ i,j . The switchover time in our model corresponds to the time it takes for all the UAVs (collectors and relays) to move from one task to the next, which, assuming all UAVs start their mobility at the same time, maps to the time needed for the farthest UAV to move from one task to the next. Hence, given the geometry of Figure 1, it can be easily seen that within a given coalition S, the switchover time between two tasks will correspond to the constant time it takes for one of the collectors to move from one of the tasks to the next.

Having modeled every coalition S ⊆ N as a polling system, we investigate the average delay incurred per coalition. In fact, for polling systems, finding exact expressions for the delay at every queue is a highly complicated task, and hence, no general closed form expressions for the delay at every queue in a polling system can be found [START_REF] Takagi | Analysis of Polling Systems[END_REF], [START_REF] Levy | Polling systems: applications, modeling, and optimization[END_REF] 2 . In this regard, a key criterion used for the analysis of the delay incurred by a polling system is the pseudo-conservation law which provides closed form expressions for weighted sum of the means of the waiting times at the queues [START_REF] Takagi | Analysis of Polling Systems[END_REF], [START_REF] Levy | Polling systems: applications, modeling, and optimization[END_REF]. For providing the pseudo-conservation law for a coalition S ⊆ N composed of a number of UAVs and a number of tasks, we make the following definitions. First, for each task i ∈ S with an average arrival rate of λ i , and served by a number of collectors with a link transmission capacity of µ i S∩M (as given by ( 1)), we define ρ i = λi µ i S∩M . Further, we define ρ S i∈S∩T ρ i . Given these definitions, for a coalition S, the pseudo-conservation law is given by [START_REF] Levy | Polling systems: applications, modeling, and optimization[END_REF] (taking into account that our switchover and service times are deterministic)

i∈S∩T ρ i Wi = ρ S i∈S∩T ρi µ i S∩M 2(1 -ρ S ) + ρ S θ 2 S 2 + θ S 2(1 -ρ S ) ρ 2 S - i∈S∩T ρ 2 i ( 4
)
where Wi is the mean waiting time at task i and θ S =

|S∩T | h=1 θ i h ,i h+1 is the sum of the switchover times given a path of tasks {i 1 , . . . , i |S∩T | } followed by the UAVs, with i h ∈ S ∩ T , ∀ h ∈ {1, . . . , |S ∩ T |} and i |S∩T |+1 = i 1 . Further, for any coalition S that must form in the system, the following condition must hold, ρ S < 1.

(

) 5
This condition is a requirement for the stability of any polling system [START_REF] Takagi | Analysis of Polling Systems[END_REF][START_REF] Levy | Polling systems: applications, modeling, and optimization[END_REF][START_REF] Li | Performance analysis of a dual round robin matching switch with exhaustive service[END_REF][START_REF] Vishnevsky | The power-series algorithm for twoqueue polling system with impatient customers[END_REF] and thus, must be satisfied for any coalition that will form in the proposed model. Otherwise, the system is considered unstable and the delay is considered as infinite (as demonstrated in the next sections, in our case, a coalition where ρ S ≥ 1 will never form). For a coalition S, the UAVs must determine the order in which the tasks in S are visited, i.e., the path {i 1 , . . . , i |S∩T | } which is an ordering over the set of tasks in S given by S ∩ T . Naturally, the UAVs must select the path that minimizes the total switchover time for one round of data collection. This problem is mapped into the traveling salesman problem [START_REF] Applegate | The traveling salesman problem: a computational study[END_REF], where a salesman, i.e., the UAVs, is required to minimize the time of visiting a series of cities, i.e., tasks. It is widely known that the solution for the traveling salesman problem is NP-complete [START_REF] Applegate | The traveling salesman problem: a computational study[END_REF], and hence there has been numerous heuristic algorithms for finding an acceptable near-optimal solution. One of the simplest of such algorithms is the nearest neighbor algorithm (also known as the greedy algorithm) [START_REF] Applegate | The traveling salesman problem: a computational study[END_REF]. In this algorithm, starting from a given city the salesman chooses the closet city as his next visit. Using the nearest neighbor algorithm, the ordering of the cities which minimizes the overall route is selected. The nearest neighbor algorithm is sub-optimal, however, it can quickly find a near-optimal solution (in most cases) and its computational complexity is small (linear in the number of cities) [START_REF] Applegate | The traveling salesman problem: a computational study[END_REF], hence making it suitable for complicated problems such as the task allocation problem we are considering. Therefore, in the proposed model, for every coalition S, the UAVs can easily work out the nearest neighbor route for the tasks, and operate according to it.

Having modeled each coalition as a polling system, the pseudo-conservation law in (4) allows to evaluate the cost, in terms of average waiting time (or delay), from forming a particular coalition. However, for every coalition, there is a benefit, in terms of the average effective throughput that the coalition is able to achieve. The average effective throughput for a coalition S is given by

L S = i∈S∩T λ i • P r i,BS (6)
with P r i,BS given by [START_REF] Niyato | Dynamic spectrum access in cognitive radio networks[END_REF]. Through ( 4) and ( 6), one can easily see that, adding more collectors reduces the delay, while adding more relays improves the effective throughput, hence each UAV role (collector or relay) possesses its own benefit for a coalition.

A suitable criterion for characterizing the utility in networks where there is a trade off between the throughput and the delay is the concept of system power which is defined as the ratio of some power of the throughput and the delay (or a power of the delay) [START_REF] Kleinrock | Power and deterministic rules of thumb for probabilistic problems in computer communications[END_REF]. Hence, the concept of power is an attractive notion that allows to capture the fundamental trade off between throughput and delay in the proposed task allocation model. Power has been used thoroughly in literature in applications that are sensitive to throughput as well as delay [START_REF] Ching | A note on the convegence of asynchronous greedy algorithm with relaxation in a multiclass queueing system[END_REF][START_REF] Altman | Nash equilibria for combined flow control and routing in networks: asymptotic behaviour for a large number of users[END_REF][START_REF] Vukadinovic | Video streaming in 3.5G: On throughputdelay performance of proportional fair scheduling[END_REF]. Mainly, for the proposed game, the utility of every coalition S is evaluated using a coalitional value function based on the power concept from [START_REF] Vukadinovic | Video streaming in 3.5G: On throughputdelay performance of proportional fair scheduling[END_REF] as follows

v(S) =    δ L β S ( i∈S∩T ρi Wi) (1-β) if ρ S < 1 & |S| > 1 0 otherwise (7)
where β ∈ (0, 1) is a throughput-delay trade off parameter. The term δ represents the price per unit power that the network offers to coalition S. In this sense, the utility function in [START_REF] Gu | UAV aided intelligent routing for ad hoc wireless network in single area theater[END_REF] represents the total revenue achieved by a coalition S, given the network power that coalition S generates. For coalitions that consist of a single UAV or a single task, i.e., coalitions of size 1, the utility assigned is 0 due to the fact that such coalitions generate no benefit for their member. Further, any coalition where condition ( 5) is not satisfied is also given a zero utility, since, in this case, the polling system that the coalition represents is unstable, and hence having an infinite delay. Consequently, given the set of players N , and the value function given in [START_REF] Gu | UAV aided intelligent routing for ad hoc wireless network in single area theater[END_REF], we define a coalitional game (N , v) with transferable utility (TU). The utility in [START_REF] Gu | UAV aided intelligent routing for ad hoc wireless network in single area theater[END_REF] represents the amount of money or revenue received by a coalition, and hence, this amount can be arbitrarily apportioned between the coalition members, which justifies the TU nature of the game. For dividing this utility between the players, we adopt the equal fair allocation rule, whereby the payoff of any player i ∈ S, denoted by x S i is simply given by

x S i = v(S) |S| . (8)
The payoff x S i represents the amount of revenue that player i ∈ S receives from the total revenue v(S) that coalition S generates. Although in traditional coalitional games, the allocation rule may have a strong impact on the game's solution, for the proposed game, other allocation rules can be used with little impact on the analysis that is presented in the rest of the paper due to the nature and class of the proposed game which is quite different from traditional coalitional games. In fact, as clearly seen from ( 4) and [START_REF] Gu | UAV aided intelligent routing for ad hoc wireless network in single area theater[END_REF], whenever the number of tasks in a coalition increases, the total delay increases, hence reducing the utility from forming a coalition. Further, in a coalition where the number of tasks is large, the condition of stability for the polling system, as given by ( 5), can be easily violated due to heavy traffic incoming from a large number of tasks, thus, yielding a zero utility as per [START_REF] Gu | UAV aided intelligent routing for ad hoc wireless network in single area theater[END_REF]. Hence, forming coalitions between the tasks and the UAVs entails a cost that can limit the size of a coalition. In this regard, traditional solution concepts for TU games, such as the core [START_REF] Myerson | Game Theory, Analysis of Conflict[END_REF], may not be applicable. In fact, in order for the core to exist, as a solution concept, a TU coalitional game must ensure that the grand coalition, i.e., the coalition of all players will form. However, as seen in Figure 1 and corroborated by the utility in [START_REF] Gu | UAV aided intelligent routing for ad hoc wireless network in single area theater[END_REF], in general, due to the cost for coalition formation, the grand coalition will not form. Instead, independent and disjoint coalitions appear in the network as a result of the task allocation process. In this regard, the proposed game is classified as a coalition formation game [START_REF] Ray | A Game-Theoretic Perspective on Coalition Formation[END_REF][START_REF] Demange | Group Formation in Economics[END_REF][START_REF] Bogomonlaia | The stability of hedonic coalition structures[END_REF][START_REF] Diamantoudi | Farsighted stability in hedonic games[END_REF][START_REF] Drèze | Hedonic coalitions: Optimality and stability[END_REF], and the objective is to find an algorithm that allows to form the coalition structure, instead of finding only a solution concept, such as the core, which aims mainly at stabilizing a grand coalition.

B. Task Allocation as a Hedonic Coalition Formation Game

As already mentioned, the proposed task allocation model entails the formation of disjoint coalitions, and hence the proposed game is classified as a coalition formation game. In fact, coalition formation has been a topic of high interest in game theory [START_REF] Ray | A Game-Theoretic Perspective on Coalition Formation[END_REF][START_REF] Demange | Group Formation in Economics[END_REF][START_REF] Bogomonlaia | The stability of hedonic coalition structures[END_REF][START_REF] Diamantoudi | Farsighted stability in hedonic games[END_REF][START_REF] Drèze | Hedonic coalitions: Optimality and stability[END_REF]. Notably, in [START_REF] Bogomonlaia | The stability of hedonic coalition structures[END_REF][START_REF] Diamantoudi | Farsighted stability in hedonic games[END_REF][START_REF] Drèze | Hedonic coalitions: Optimality and stability[END_REF], a class of coalition formation games known as hedonic coalition formation games is investigated. This class of games entails several interesting properties that can be applied, not only in economics such as in [START_REF] Bogomonlaia | The stability of hedonic coalition structures[END_REF][START_REF] Diamantoudi | Farsighted stability in hedonic games[END_REF][START_REF] Drèze | Hedonic coalitions: Optimality and stability[END_REF], but also in wireless networks as we will demonstrate in this paper. The two key requirements for classifying a coalitional game as a hedonic game are [START_REF] Bogomonlaia | The stability of hedonic coalition structures[END_REF] 1) The payoff of any player depends solely on the members of the coalition to which the player belongs, and 2) the coalitions form as a result of the preferences of the players over their possible coalitions' set. These two conditions characterize the framework of hedonic games. Mainly, the term hedonic pertains to the first condition above, whereby the payoff of any player i, in a hedonic game, must depend only on the identity of the players in the coalition to which player i belongs, with no dependence on the other players. For the second condition, in the remainder of this section, we will formally define how the preferences of the players over the coalitions can be used for the formation process. Hereafter, we refer to the above requirements as the hedonic conditions.

Prior to investigating the application of hedonic games in the proposed model, we introduce some definitions, taken from [START_REF] Bogomonlaia | The stability of hedonic coalition structures[END_REF].

Definition 1: A coalition structure or a coalition partition is defined as the set Π = {S 1 , . . . , S l } which partitions the players set N , i.e., ∀ k , S k ⊆ N are disjoint coalitions such that ∪ l k=1 S k = N (an example of a partition Π is shown in Figure 1).

Definition 2: Given a partition Π of N , for every player i ∈ N we denote by S Π (i), the coalition S k ∈ Π, such that i ∈ S k .

In a hedonic game setting, each player must build preferences over its own set of possible coalitions. In other words, each player must be able to compare the coalitions, and order them based on which coalition the player prefers being a member of. For evaluating these preferences of the players over the coalitions, we define the concept of a preference relation or order as follows [START_REF] Bogomonlaia | The stability of hedonic coalition structures[END_REF] Definition 3: For any player i ∈ N , a preference relation or order i is defined as a complete, reflexive and transitive binary relation over the set of all coalitions that player i can possibly form, i.e., the set {S k ⊆ N : i ∈ S k }. Consequently, for a player i ∈ N , given two coalitions S 1 ⊆ N and, S 2 ⊆ N such that i ∈ S 1 and i ∈ S 2 , S 1 i S 2 indicates that player i prefers to be part of coalition S 1 , over being part of coalition S 2 , or at least, i prefers both coalitions equally. Further, using the asymmetric counterpart of i , denoted by ≻ i , S 1 ≻ i S 2 , indicates that player i strictly prefers being a member of S 1 over being a member of S 2 . For every application, an adequate preference relation i can be defined to allow the players to quantify their preferences. The preference relation can be a function of many parameters, such as the payoffs that the players receive from each coalition, the weight each player gives to other players, and so on. Given the set of players N , and a preference relation i for every player i ∈ N , a hedonic coalition formation game is formally defined as follows [START_REF] Bogomonlaia | The stability of hedonic coalition structures[END_REF].

Definition 4: A hedonic coalition formation game is a coalitional game that satisfies the two hedonic conditions previously prescribed, and is defined by the pair (N , ≻) where N is the set of players, and ≻ is a profile of preferences, i.e., preference relations, ( 1 , . . . , N ) defined for every player in N .

Having laid out and defined the main components of hedonic coalition formation games, we utilize this framework in order to provide a suitable solution for the task allocation problem proposed in Section II. For instance, the proposed task allocation problem is easily modeled as a (N , ≻) hedonic game, where N is the set of UAVs and tasks previously defined, and ≻ is a profile of preferences that we will shortly define. First and foremost, clearly, for the proposed game model, given a network partition Π of N , the payoff of any player i, depends only on the identity of the members of the coalition to which i belongs. In other words, the payoff of any player i depends solely on the players in the coalition S Π (i) (easily seen through the formulation of Section III-A). Hence, our game verifies the first hedonic condition.

Furthermore, for modeling the task allocation problem as a hedonic coalition formation game, the preference relations of the players must be clearly defined. In this regard, we define two types of preference relations, a first type suited for indicating the preferences of the UAVs, and a second type suited for the tasks. Subsequently, for evaluating the preferences of any UAV i ∈ M, we define the following operation (this preference relation is common for all UAVs, hence we denote it by

i = M , ∀i ∈ M) S 2 M S 1 ⇔ u(S 2 ) ≥ u(S 1 ) (9)
where S 1 ⊆ N and S 2 ⊆ N are any two coalitions that contain UAV i, i.e., i ∈ S 1 and i ∈ S 2 and u : 2 N → R is a preference function defined over the real line as follows

u(S) =      ∞, if S = S Π (i) & S \ {i} ⊆ T ; 0, if S ∈ h(i); x S i . otherwise, ( 10
)
where Π is the current coalition partition which is in place in the game, x S i is the payoff received by player i from any division of the value function among the players in coalition S such as the equal fair division given in [START_REF] Xu | landmark routing in large wireless battlefield networks using UAVs[END_REF], and h(i) is the history set of player i. The history set h(i) simply contains coalitions that player i was a part of in past instances, prior to the formation of the current partition Π. Note that, using the defined preference relation, the players can compare any two coalitions S 1 and S 2 independently of whether these two coalitions belong to Π or not.

The main rationale behind the preference function u is as follows. Any UAV i that is the sole UAV servicing tasks in its current coalition S = S Π (i), i.e., S ∩ M = {i}, assigns an infinite preference value to S. This is mainly due to the fact that no UAV has an incentive to leave any group of tasks previously assigned to it unattended, as the presence of this UAV is crucial for the operation of these tasks. Hence, the maximum preference is always given to the current coalition, if this current coalition does not contain other UAVs. Further, no UAV has any incentive to re-visit a coalition that it has left previously, and hence, the UAVs assign a preference value of 0 for any coalition in their history. Finally, for all the other cases, the preference relation is easily generated by the UAVs by comparing the value of the payoffs they receive from the two coalitions S 1 and S 2 . In summary, between two coalitions S 1 and S 2 , a UAV i prefers the coalition that gives the better payoff, given that the UAV is not alone in its current coalition, and the coalition with a better payoff is not in the history of UAV i.

For the preferences of the tasks, an analogous approach can be taken. Formally, for evaluating the preferences of any task j ∈ T , we define the following operation (this preference relation is common for all tasks, hence we denote it by j = T , ∀j ∈ T )

S 2 T S 1 ⇔ w(S 2 ) ≥ w(S 1 ) (11)
with the tasks' preference function w defined as follows

w(S) = 0, if S ∈ h(i); x S i , otherwise. ( 12
)
The preferences of the tasks are easily captured using the function w. Simply, each task prefers the coalition that provides the larger payoff x S i unless this coalition was already visited previously and left. In that case, the preference function of the tasks assigns a preference value of 0 for any coalition that the task visited and left in the past. Using this preference relation, every task can evaluate its preferences over the possible coalitions that the task can form.

Consequently, the proposed task allocation model verifies both hedonic conditions, and hence, the problem is easily mapped into a (N , ≻) hedonic coalition formation game, with the preference relations given by ( 9) and ( 11) which are also dependent on the underlying TU coalitional game described in Section III-A. Having formulated the problem as a hedonic game, the final task is to provide a distributed algorithm, based on the defined preferences, for forming the coalitions.

C. Hedonic Coalition Formation Algorithm

In the previous subsection, we modeled the task allocation problem as a hedonic coalition formation game. Having laid out the main building blocks, the remaining objective is to propose an algorithm for forming the coalitions. While literature that studies the characteristics of existing partitions in hedonic games, such as in [START_REF] Bogomonlaia | The stability of hedonic coalition structures[END_REF][START_REF] Diamantoudi | Farsighted stability in hedonic games[END_REF][START_REF] Drèze | Hedonic coalitions: Optimality and stability[END_REF], is abundant, the problem of forming the coalitions both in the hedonic and non-hedonic setting is a challenging problem [START_REF] Ray | A Game-Theoretic Perspective on Coalition Formation[END_REF]. In this paper, we propose an algorithm for coalition formation that allows the players to make selfish decisions as to which coalitions they decide to join at any point in time. The proposed algorithm will exploit the concepts of the hedonic game model formulated in the previous section.

In this regard, for forming coalitions between the tasks and the UAVs, we propose the following rule for coalition formation Definition 5: Switch Rulegiven a partition Π = {S 1 , . . . , S l } of the set of players (UAVs and tasks) N , a player i decides to leave its current coalition S Π (i) = S m , for some m ∈ {1, . . . , l} and join another coalition

S k ∈ Π ∪ {∅}, S k = S Π (i), if and only if S k ∪ {i} ≻ i S Π (i). Hence, {S m , S k } → {S m \ {i}, S k ∪ {i}}.
Through a single switch rule made by any player i, any current partition Π of N is transformed into Π ′ = Π \ {S m , S k } ∪ {S m \ {i}, S k ∪ {i}}. In simple terms, for every partition Π, the switch rule provides a mechanism through which any player, task or UAV, can leave its current coalition S Π (i), and join another coalition S k ∈ Π, given that the new coalition S k ∪ {i} is strictly preferred over S Π (i) (through any preference relation that i is using). Independent of the preference relations selected, the switch rule can be seen as a selfish decision made by a player, to move from its current coalition to a new coalition, regardless of the effect of this move on the other players. Furthermore, we consider that, whenever a player decides to switch from one coalition to another, the player can maintain a history set h(i), which is the set of coalitions that player i belonged to prior to making a switch decision. Hence, given a partition Π, whenever a player i decides to leave coalition S m ∈ Π to join a different coalition, coalition S m is automatically stored by player i in its history set h(i) (hence the history constitutes the coalitions that a player i left in the past).

Consequently, we propose a coalition formation algorithm composed of three main phases: task discovery, hedonic coalition formation, and data collection. In the first phase, the central command discovers the tasks that require servicing and informs the UAVs of the locations and characteristics of the tasks (e.g. the arrival rates), hence the UAVs have knowledge of the initial partition Π initial . Once the UAVs are aware of the tasks, they can interact with each other (and with the tasks), for performing coalition formation. Hence, the second phase of the algorithm is the hedonic coalition formation phase. In this phase, all the players (tasks and UAVs), investigate the possibility of performing a switch operation. In this context, every player (task or UAV) has a knowledge of the current structure (depending on the nature of the tasks, they may know the structure through the UAVs, without any need to communicate with other tasks). Given the current structure, each player investigates its top preference, and decides to perform a switch operation, if possible through [START_REF] Gu | C-ICAMA, a centralized intelligent channel assigned multiple access for multi-layer ad-hoc wireless networks with UAVs[END_REF] and [START_REF] Alighanbari | Robust decentralized task assignment for cooperative uavs[END_REF] for the UAVs and tasks respectively. We consider that, the order in which the players make their switch operations is random, but sequential. For any UAV, a switch operation is easily performed as the UAV can leave its current coalition and join the new coalition, if ( 9) is satisfied. For the tasks, any task that finds out a possibility to switch, can request the nearest UAV to perform this switch on its behalf (if the nature of the task forbids it to act autonomously). In this regard, through an inter-UAV communication link, the UAV selected by the task requests to exchange the concerned task with the new coalition that the task had selected. Following the formation of the coalitions, the last phase of the algorithm entails the actual data collection by the UAVs. In this phase, the UAVs move from one task to the other, in their respective coalitions, collecting the data and transmitting it to the central receiver, similar to a polling system, as explained in Sections II and III-A. A summary of the proposed algorithm is shown in Table I.

The proposed algorithm can be easily implemented in a distributed way, since, as already explained, the switch operation can be performed by the tasks or the UAVs independently of any centralized entity (although the tasks may require interaction with the closest UAV). The only information required is the location of the tasks, which can be broadcasted by the central command center at the beginning of all time. Further, note that, for determining whether a UAV acts as a collector or relay within any coalition, the players can easily compute the configuration that maximizes the utility in [START_REF] Gu | UAV aided intelligent routing for ad hoc wireless network in single area theater[END_REF]. As the number of UAVs is generally small, this computation is straight forward, and has low complexity.

IV. SIMULATION RESULTS AND ANALYSIS

For simulations, the following network is set up: The central BS (command center) is placed at the origin of a 4 km ×4 km square area with the tasks randomly appearing in the area around the BS. The path loss parameters are set to α = 3 and κ = 1, the target SNR is set to γ 0 = 10 dB, the pricing factor is set to δ = 1, and the noise variance σ 2 = -120 dBm. All packets are considered of size 256 bits (typical IP packet size). The UAVs are considered having a constant velocity of ν = 60 km/h, a transmit power of P = 100 mW, and a transmission link capacity of µ = 768 kbps (assumed the same for all UAVs). Further, we consider two classes of tasks in the network. A first class that can be mapped to voice services having an arrival rate of λ 1 = 32 kbps, and a second class that can be mapped to video services, such as the widely known Quarter Common Intermediate Format (QCIF) format [START_REF] Wainfan | Challenges in Virtual Collaboration: Videoconferencing Audioconferencing and Computer-Mediated Communications[END_REF], having an arrival rate

Initial State

The network is partitioned by Π initial = {S 1 , . . . , S k }. At the beginning of all time Π initial = N = M ∪ T with no tasks being serviced by any UAV. Three phases for the proposed hedonic coalition formation algorithm Phase I -Task Discovery:

The central BS informs the UAVs of the initial network partition Π initial . Phase II -Hedonic Coalition Formation:

In this phase, hedonic coalition formation occurs. repeat For every player i ∈ N , given a current partition Πcurrent (in the first round Πcurrent = Π initial ). a) Player i investigates possible switch operations using the preferences given, respectively, by ( 9) and ( 11) for the UAVs and tasks. b) Player i performs the switch operation that maximizes its payoff as follows: b.1) Player i updates its history h(i) by adding coalition S Πcurrent (i), before leaving it. b.2) Player i leaves its current coalition S Πcurrent (i). b.3) Player i joins the new coalition that maximizes its payoff. until convergence to a final partition Π final .

Phase III -Data collection

a) The network is partitioned using Π final .

b) The UAVs in each coalition S k ∈ Π final continuously perform the following operations, i.e., act as a polling system with exhaustive strategy and switchover times: b.1) Visit a first task in their respective coalitions. b.

2) The collector-UAVs collect the data from the task that is being visited. b.

3) The collector-UAVs transmit the data using wireless links to the BS either directly, or through other relay-UAVs. b.4) Once the queue of the current is empty, visit the next task. The order in which the tasks are visited is determined by the nearest neighbor solution to the traveling salesman problem (Section III-A). The third phase is continuously repeated and performed by all UAVs in Π final . λ 2 = 128 kbps. Tasks belonging to each class are generated with equal probability. The trade off parameter β is set to 0.7, to indicate services that are reasonably delay tolerant.

In Figure 2, we assess the performance of the proposed hedonic coalition formation algorithm, in terms of the average payoff (revenue) per player (UAV or task) for a network having M = 5 UAVs, as the number of tasks increases. The results are averaged over the random positions of the tasks (each task can belong to one of the two classes previously mentioned with equal probability). In this figure, we compare the performance with an algorithm that assigns the tasks equally among the UAVs (i.e. an equal group of neighboring tasks are assigned for every UAV). Figure 2 shows that the performance of both algorithms is apt to decrease as the number of tasks increases. This is mainly due to the fact that, for networks having a larger number of tasks, the delay incurred per coalition, and thus per user increases. This increase in the delay is not only due to the increase in the number of tasks, but also to the increase in the distance that the UAVs need to travel within their corresponding coalitions (increase in switchover times). However, it is clear that the proposed algorithm outperforms the equal allocation at all network sizes. This performance improvement decreases with the increase in the number of tasks, but the improvement, in terms of average payoff, yielded by the proposed algorithm is no less than 61.96% better than the equal allocation (at T = 25). The reduction in the performance gap between the two algorithms stems from the fact that, as more tasks exist in the network, for a fixed number of UAVs, the possibility of forming large coalitions, through the proposed hedonic coalition formation algorithm is reduced, and hence the structure becomes closer to equal allocation.

In Figure 3, we show a snapshot of the final network partition reached through the proposed hedonic coalition formation algorithm for a network of M = 5 UAVs and T = 10 randomly located tasks. In this figure, tasks 1, 3, and 8 belong to the QCIF video class, while the remaining tasks belong to the voice class. Through Figure 3, it is shown how the UAVs and tasks can agree on a partition whereby a number of UAVs service a group of nearby tasks. For the network of Figure 3, the tasks are distributed into three coalitions, two of which (coalitions S 1 and S 3 ) are served by a single collector-UAV. In contrast, coalition S 2 is served by two collectors and one relay. The UAVs in coalition 2 divided their roles depending on the achieved utility. For instance, having two collectors and one relay provides a utility of coalition is S 2 is v(S 2 ) = 51.48 while having three collectors yields a utility of v(S 2 ) = 10.92 , and having one collector and two relays yields a utility of v(S 2 ) = 44.39 . Clearly, the case of two collectors and one relay maximizes the utility and is agreed upon between the players. Finally, it must be noted that, the coalitions in Figure 3 are dynamic, in the sense that, within each coalition, the UAVs move from one task to the other, collecting and transmitting data to the . The order in which the UAVs visit the tasks, as indicated in Figure 3, is generated using a nearest neighbor solution for the traveling salesman problem (see Section III-A).

Finally, in Figure 3, we show the average coalition size resulting from the proposed algorithm as the number of tasks T increases, for a network of M = 5 UAVs and randomly deployed tasks. The results are compared with the equal allocation algorithm. In this figure, we note that, as the number of tasks increases, the average coalition size for both algorithms increases. For the proposed algorithm, this is an immediate result of the fact that, as the number of tasks increases the probability of forming larger coalitions is higher. Further, at all network sizes, the proposed algorithm yields larger coalitions than the equal allocation algorithm. This result implies that, by allowing the players (tasks and UAVs) to selfishly select their coalitions, through the proposed algorithm, the players have an incentive to structure themselves in relatively large coalitions. In a nutshell, through hedonic coalition formation, the resulting topology, generally consists of a small number of large coalitions, rather than a large number of small coalitions.

V. CONCLUSIONS

In this paper, we proposed a novel model for task allocation among a number of agents, such as unmanned aerial vehicles (UAVs) in a wireless communication network. In the proposed model, a number of UAVs are required to service several tasks, randomly located in a given area. Each task represents a queue of packets that require collection and wireless transmission to a centralized receiver by the UAVs. The task allocation problem is modeled as a hedonic coalition formation game between the UAVs and the tasks that interact in order to form disjoint coalitions. Each formed coalition is mapped to a polling system which consists of a number of UAVs continuously collecting packets from a number of tasks. Within a coalition, the UAVs can act either as collectors that move between the different tasks present in the coalition for collecting the packet data, or relays for improving the wireless transmission of the data packets. For forming the coalitions, we propose an algorithm that allows the players (tasks or UAVs) to join or leave the coalitions based on their preferences which capture the trade off between the effective throughput and the delay achieved by the coalition. Simulation results show how the proposed algorithm allows the UAVs and tasks to self-organize into independent coalitions, while improving the performance, in terms of average player (UAV or task) payoff, of at least 61.96% relatively to a scheme that allocates nearby tasks equally among UAVs. In a nutshell, by combining concepts from wireless networks, queueing theory and novel concepts from coalitional game theory, we proposed a new model for task allocation among autonomous agents in communication networks which is well suited for many practical applications such as surveillance, monitoring, or data collection in wireless networks.

Fig. 1 .

 1 Fig. 1. An illustrative example of the proposed model for task allocation in wireless networks.

Fig. 2 .

 2 Fig.2. Performance assessment, in terms of average player (UAV or task) payoff (revenue), of the proposed hedonic coalition formation algorithm compared to an algorithm that allocates the neighboring tasks equally among the UAVs as the number of tasks increases for M = 5 UAVs.

Fig. 3 .

 3 Fig. 3. A snapshot of a final coalition structure resulting from the proposed hedonic coalition formation algorithm for a network of M = 5 UAVs and T = 10 tasks.

Fig. 4 .

 4 Fig.[START_REF] Akella | Self management in chaotic wireless deployments[END_REF]. Average coalition size yielded by the proposed hedonic coalition formation algorithm and an algorithm that allocates the neighboring tasks equally among the UAVs, as a function of the number of tasks T for a network of 5 UAVs.

TABLE I THE

 I PROPOSED HEDONIC COALITION FORMATION ALGORITHM FOR TASK ALLOCATION IN WIRELESS NETWORKS.

Other types of queues, e.g., M/M/1, can also be considered without loss of generality in the coalition formation process proposed in the remainder of this paper.

Note that, some approximations exist for polling systems under heavy traffic or large switchover times[START_REF] Levy | Polling systems: applications, modeling, and optimization[END_REF], but in our problem, they are not suitable as we require a more general delay expression.