With significantly growing number of smart low-power devices during recent years, the issue of energy efficiency has taken an increasingly essential role in the communication systems' design. This thesis aims at designing distributed and energy efficient transmission schemes for wireless networks using game theory and instantly decodable network coding (IDNC) which is a promising network coding subclass. We study the cooperative data exchange (CDE) scenario in which all devices cooperate with each other by exchanging network coded packets until all of them receive all the required information. In fact, enabling the IDNC-based CDE setting brings several challenges such us how to extend the network lifetime and how to reduce the number of transmissions in order to satisfy urgent delay requirements. Therefore, unlike most of existing works concerning IDNC, we focus not only on the decoding delay, but also the consumed energy.

First, we investigate the IDNC-based CDE problem within small fully connected networks across energy-constrained devices and model the problem using the cooperative game theory in partition form. We propose a distributed merge-and-split algorithm to allow the wireless nodes to self-organize into independent disjoint coalitions in a distributed manner. The proposed algorithm guarantees reduced energy consumption and minimizes the delay in the resulting clustered network structure. We do not only consider the transmission energy, but also the computational energy consumption. Furthermore, we focus on the mobility issue and we analyse how, in the proposed framework, nodes can adapt to the dynamic topology of the network.

Thereafter, we study the IDNC-based CDE problem within large-scale partially connected networks. We considerate that each player uses no longer his maximum transmission power, rather, he controls his transmission range dynamically. In fact, we investigate multi-hop CDE using the IDNC at decentralized wireless nodes. In such model, we focus on how these wireless nodes can cooperate in limited transmission ranges without increasing the IDNC delay nor their energy consumption. For that purpose, we model the problem using a two-stage game theoretical framework. We first model the power control problem using non-cooperative game theory where users iv Chapter 1

v jointly choose their desired transmission power selfishly in order to reduce their energy consumption and their IDNC delay. The optimal solution of this game allows the players at the next stage to cooperate with each other through limited transmission ranges using cooperative game theory in partition form. Thereafter, a distributed multihop merge-and-split algorithm is defined to form coalitions where players maximize their utilities in terms of decoding delays and energy consumption. The solution of the proposed framework determines a stable feasible partition for the wireless nodes with reduced interference and reasonable complexity. We demonstrate that the cooperation between nodes in the multihop cooperative scheme achieves a significant minimization of the energy consumption with respect to the most stable cooperative scheme in maximum transmission range without hurting the IDNC delay.

Résumé

Au cours ces dernières années, avec le nombre croissant d'appareils intelligents à faible puissance, la question de l'efficacité énergétique a joué un rôle de plus en plus indispensable dans la conception des systèmes de communication. Cette thèse vise à concevoir des schémas de transmission distribués à faible consommation d'énergie pour les réseaux sans fil, utilisant la théorie des jeux et le codage réseau instantanément décodable (IDNC), qui est une sous-classe prometteuse du codage réseau. En outre, nous étudions le modèle de l'échange coopératif de donnée (CDE) dans lequel tous les périphériques coopèrent en échangeant des paquets codés dans le réseau, jusqu'à ce qu'ils récupèrent tous l'ensemble des informations requises. En effet, la mise en oeuvre du CDE basé sur l'IDNC soulève plusieurs défis intéressants, notamment la prolongation de la durée de vie du réseau et la réduction du nombre de transmissions afin de répondre aux besoins des applications temps réel. Par conséquent, contrairement à la plupart des travaux existants concernant l'IDNC, nous nous concentrons non seulement sur le délai, mais également sur l'énergie consommée.

En premier lieu, nous étudions le problème de minimisation de l'énergie consommée et du délai au sein d'un petit réseau IDNC coopératif, entièrement connecté et à faible puissance. Nous modélisons le problème en utilisant la théorie des jeux coopératifs de formation de coalitions. Nous proposons un algorithme distribué (appelé "merge and split") permettant aux noeuds sans fil de s'auto-organiser, de manière distribuée, en coalitions disjointes et indépendantes. L'algorithme proposé garantit une consommation d'énergie réduite et minimise le délai de complétion dans le réseau clustérisé résultant. Par ailleurs, nous ne considérons pas seulement l'énergie de transmission, mais aussi la consommation de l'énergie de calcul des noeuds. De plus, nous nous concentrons sur la question de la mobilité et nous analysons comment, à travers la solution proposée, les noeuds peuvent s'adapter à la topologie dynamique du réseau.

Par la suite, nous étudions le même problème au sein d'un réseau large et partiellement connecté. En effet, nous examinons le modèle de CDE multi-sauts. Dans un tel modèle, nous considérons que les noeuds peuvent choisir la puissance d'émission, et change ainsi de rayon de transmission et le nombre de voisin avec lesquels il peut vi vii entrer en coalition. Pour ce faire, nous modélisons le problème avec un jeu à deux étages ; un jeu non-coopératif de contrôle de puissance et un jeu coopératif de formation de coalitions. La solution optimale du premier jeu permet aux joueurs de coopérer à travers des rayons de transmission limités en utilisant la théorie des jeux coopérative. En outre, nous proposons un algorithme distribué "merge and split" afin de former des coalitions dans lesquelles les joueurs maximisent leurs utilités en termes de délai et de l'énergie consommée. La solution proposée permet la création d'une partition stable avec une interférence réduite et une complexité raisonnable.

Nous démontrons que la coopération entre les noeuds au sein du réseau résultant, permet de réduire considérablement la consommation d'énergie par rapport au modèle coopératif optimal qui maintient le rayon de transmission maximal. viii my research as well as my writing skills. My appreciation for his precious guidance during this thesis is immeasurable. I am also grateful to my supervisors Vahid Meghdadi and Tahar Ezzedine for giving me the chance to do this PhD and offering me the best opportunities and conditions to succeed. I also thank them for their continuous support and encouragement. I would like to thank Professor Jean Pierre cances, head of XLIM-SRI at the university of Limoges, for his great encouragement and support, especially during my conference presentations.

I would like to thank Mr. Thierry Chonavel, professor at Télécom Bretagne, France and Mr. Essaid Sabir, associate professor at Ecole Nationale Supérieure d'Electricité et Mécanique, Morocco, for accepting to evaluate my thesis work and for their insightful comments and encouragement. I also thank Mrs. Atika Rivenq, professor at Université Polytechnique Hauts-de-France, France, Mr. Ammar Bouallegue, professor emeritus at Ecole Nationale d'Ingénieurs de Tunis, Tunisia and Mr. Guillaume Ferré, Associate professor at ENSEIRB-MATMECA, France for accepting being my thesis examiners. I want to deeply thank all my family members for their inexhaustible love, support and encouragement. I cannot finish without expressing my sincere thanks to my special friends. They have ix x been companions on my thesis journey, offering honest feedback and genuine praises, helping me when I need and pushing me to become a highly better version of myself.

Thank you so much... During the last decade, with the proliferation of wireless devices, the diverse range of new applications and services, and the exponential increase of subscriber base, several concepts have emerged, including Internet of Things (IoT) [START_REF] Zanella | Internet of things for smart cities[END_REF][START_REF] Atzori | The internet of things: A survey[END_REF] and smart cities [START_REF] Peris-Ortiz | Sustainable smart cities: creating spaces for technological, social and business development[END_REF] which can be considered as key pillar for the future wireless networks. As a result, machine-to-machine communications (M2M), known also as machine type communications (MTC), have emerged as new communication paradigm refering generally to automated data communications among machines, devices and equipment that may occur directly without any human intervention [4,[START_REF] Verma | Machine-to-machine (m2m) communications: A survey[END_REF]. Indeed, a recent report from Cisco [6] suggests that the number of MTC connections is foreseen to grow from under a billion in 2017 to 3.9 billion in 2022. Hence, innovative solutions at both device and system levels are of prime interest in order to address fast and reliable data exchange along with operational and environmental costs.

In this dissertation, we more specifically address the context of the smart city in which all the city's assets are virtually connected and electronically managed. There is a plenty of smart city applications such as tracking systems in shipping and manufacturing sectors, medical applications gathering patient records and health status transitioning from hospital-centric to patient-centric, online education, e-library, online surveillance and environment monitoring. For such type of applications, a huge number of autonomously operated low-cost devices (i.e. sensors or actuators) need to be connected to physical objects. These devices are generally equipped with limited capacity batteries and are proposed to operate for a long duration without the need to battery charging; hence, very low energy consumption is essential in order to extend the network lifetime. Therefore, such diverse traffic imposes various requirements on the energy-constrained wireless networks in terms of energy efficiency, packet delivery deadline and scalability as well. These requirements, in addition to erasure wireless channels raise a number of challenges for sharing the data among energy-constrained users without degrading the Quality of Service (QoS). In this regard, substantial efforts have been made to integrate the applications requirements into wireless communications and protocols design. Interestingly, in this thesis, we focus on designing novel distributed transmission schemes, mainly aware of the network lifetime along with the QoS for MTC users.

First, we study real-time energy efficient applications having two distinct characteristics: they require quick and reliable decoding of the packets, and they are powered using limited capacity batteries. Besides, the involved agents exchange the transmitted data in a distributed manner without the intervention of any central unit. For example, consider a number of geographically scattered drones that are interested in receiving multiple data broadcasted by a base station (BS), each of which is encapsulated in a packet. In such scenario, communication conditions are unreliable due to the high mobility of nodes. Hence, some packets may be lost during the BS transmission. Indeed, in some practical scenarios, such as VANET and fleets of drones, mobile nodes may be out of the range of the BS when attempting to recover the missing packets. Instead, they tend to cooperate by exchanging network coded packets until recovering all their missing ones. Moreover, we address another challenging issue faced by the UAV network (Unmanned Aerial Vehicle) in the same scenario, which is how to mitigate the effects of frequent topology changes on the network performance.

In other words, how can drones adapt to dynamic topology without degrading the QoS. For example, monitoring applications, such as forest surveillence, require that only some drones move through the target area. As a result, the distribution of drones as well as the area dimension may change, and the designed scheme may be no longer efficient. This is because the prior transmission scheme design accounts for drones positions and topology. Even though this scheme is scalable and can tolerate such situation, this may adversely affect the computational energy consumed by the whole fleet. As we see from the examples above, it is crucial to design dynamic transmission schemes based on smart strategies whereby the MTC network can meet the low energy consumption and decoding delay of packets.

Thereafter, to overcome the problem of short ranges and limited power transmissions, multihop communications represent a promising solution to extend the coverage of the energy constrained network [START_REF] Shaikh | Routing in multi-hop cellular device-to-device (d2d) networks: A survey[END_REF]. Generally, in a multihop network, an intermediate node relays packets either between a central unit and another node or between two nodes. We are interested in the latter case where nodes manage autonomously and cooperatively the data exchange over multihop communications. Specifically, we consider real-time energy efficient applications based on three distinct features.

Transmissions have strict deadline, nodes communicate over short ranges and are powered using limited batteries' capacity. For example, consider a wireless sensor Introduction network (WSN) deployed in hostile environments in which low-power sensors have to accumulate and store the sensed data until the visit of the mobile sink to gather it.

In fact, the scattered surviving sensors should quickly cooperate and retrieve their lost packets to achieve the maximum copies of sensed data at the mobile sink agent.

Therefore, it is crucial to investigate how these wireless nodes can cooperate over short ranges while controling delays and energy consumption in order to simplify the design of efficient multihop transmission schemes.

To this end, having highlighted the meaning of incorporating the application requirements into future technologies and protocols design, this dissertation deals with designing specific solutions for energy constrained communications having hard deadline requirement. In the next section, we present the adopted network configuration, our main challenges in this thesis and the scenarios that motivate our work.

Motivation and problems description

Assume we have a base station (BS) broadcasting a set of packets to a number of wireless nodes that are geographically distributed. All nodes are interested in receiving the same set of packets. We suppose that communication conditions are unreliable or the nodes are highly mobile. In such cases, some packets may be have been lost by some users. It is worth noting that mobile nodes are not necessarly in the range of the BS when trying to recover their missed packets. An interesting strategy to recover them, instead of relying on the BS, is the cooperation among the nodes by exchanging network coded packets until all of them have received all required packets. This configuration is called cooperative data exchange (CDE) [START_REF] Tajbakhsh | Coded cooperative data exchange for multiple unicasts[END_REF]. Indeed, CDE is considered as a future research direction for several applications. The benefits of its use are multifold. First, it reduces the load of the BS which can serve more clients in the system.

Second, it optimizes the use of additional equipements to deal with the demand of network size/throughput growth. Finally, it allows short range links among wireless nodes that ensure cheaper, more reliable and faster information delivery compared to long-range links.

The CDE setting can be enabled either in a fully connected network or in a partially connected network. In the former case, all nodes can reach each others via single hop whatever is the network size. Moreover, one single node should transmit in each time

Motivation and problems description 7 slot to avoid interference induced by simultaneous transmissions. In doing so, each sending node may use its expensive maximum transmission power in order to reach all receivers in the field, which is not suited for battery-powered devices. However, taking advantage from the spatial diversity, it is possible for different nodes to transmit simultaneously using the same wireless resource while being free of interference and guaranteeing less energy consumption. Thus, it seems interesting to create local CDEs by partitioning the network into small, and geographically separated groups for reliable and energy efficient cooperative trasmissions. Indeed, exchanging packets over short ranges may significantly save the nodes' energy. Nonetheless, the transmitting node of such a group may hold a subset of packets which are wanted by some nodes but not required by others. It may also not have enough needed energy to target all receivers even if its packets are quite wanted. Hence, there is a need to efficiently select the local CDE groups, the transmitting devices as well as the transmitted packets.

To this end, the CDE configuration needs to be investigated especially in wireless networks with energy constraint so that to tap into its full advantages.

Interestingly, the aim of this thesis is to investigate cooperation strategies thoroughly focusing on jointly minimizing the energy consumption and the overall completion time. For this purpose, several important concepts are used including game theory and network coding. Indeed, we propose in this dissertation distributed game theoretical frameworks using the network coding that capture main features of energy constrained networks, and can consequently, serve as a basis for promising solutions for more general networks.

Motivations

The need for cooperation within wireless networks arises naturally when improving the network efficiency. In this regard, many practical scenarios that motivate our work in this thesis are illustrated in figure 1.1; the first scenario is when a drone fleet collects information from the sink of wireless sensor network. Indeed, during the last decade, the use of UAVs system to cooperatively monitor a given area has been regularly increased, and has overcome the interest of using a single drone [START_REF] Gupta | Survey of important issues in uav communication networks[END_REF][START_REF] Wang | Taking drones to the next level: Cooperative distributed unmanned-aerial-vehicular networks for small and mini drones[END_REF][START_REF] Hayat | Survey on unmanned aerial vehicle networks for civil applications: A communications viewpoint[END_REF]. In such systems, small UAVs can autonomously cooperate, make decisions and take actions in order to meet the objectives of a particular mission [START_REF] Gupta | Survey of important issues in uav communication networks[END_REF][START_REF] Wang | Taking drones to the next level: Cooperative distributed unmanned-aerial-vehicular networks for small and mini drones[END_REF]. Another important application for WSN, deployed in hostile environments, is called the distributed data storage (DDS) [START_REF] Yang | Energyefficient distributed data storage for wireless sensor networks based on compressed sensing and network coding[END_REF]. In such application, sensors have to accumulate and store the sensed data until the visit of the mobile sink to gather it. Our proposed framework is also interesting for a roadside base station broadcasting data to vehicles that can miss some packets due to their high-speed mobility. Last but not least, the distributed surveillance camera network where a number of cameras are monitoring moving targets into a given area. All cameras are exchanging their own local information about each captured target in order to recover all the scene over the entire network.

Road map

This dissertation contains two parts. In the following two chapters, we provide the necessary theoretical foundations for the understanding of this thesis; In chapter 2, we review the background of game theory which represents our principal tool. We Road map 9 introduce cooperative, as well as non cooperative game theoretic frameworks. The former is particularly important since it sustains the CDE setting by enabling players to form cooperative groups to strengthen their utility. In chapter 3, we provide some insights into the network coding technology that has proved valuable abilities to significantly enhance the network performance. In particular, we introduce its main variants, as well as the interesting instantly decodable network coding (IDNC) which we adopt throughout all this dissertation.

In the second part of this thesis, we propose our game theoretic framework focusing on the joint CDE problem for delay and energy minimization. In chapter 4, we investigate the cooperation among players in the IDNC based CDE within small connected networks where all wireless nodes can reach each others via single hop.

We model the problem using coalitional game theory in partition form. In addition, we address the mobility issue in the UAV networks use-case and we analyse how, in the proposed framework, the nodes can adapt to the dynamics of the network.

In chapter 5, we extend the network model introduced in the previous chapter, to study the cooperation within large-scale energy-constrained networks. In fact, we address the problem of multi-hop CDE through the two-stage game framework in order to extend the cooperation coverage. We conclude this dissertation in chapter 6 by summarizing our contributions and discussing new future research directions.

We provide all publications of this thesis in Appendix A.

Chapter 2

Fundamentals of game theory The key idea of designing a CDE system is to shift from conventional centralized schemes toward self-optimizing and self-organizing approaches. Thus, wireless nodes are allowed to use some intelligence to make the packet recovery operations energyefficient and reliable. Moreover, the dynamic nature of the CDE network arises new challenges regarding the scalability of the system, its stability and computational complexity.

In this regard, game theory is introduced in the literature as an increasingly impactful tool to solve numerous distributed optimization problems in wireless networks [START_REF] Han | Game theory in wireless and communication networks: theory, models, and applications[END_REF]. In this chapter, we review some game theoretic frameworks, taking into account specific characteristics of the CDE-based system.

Game formulation

Game theory is a branch of applied mathematics with a set of frameworks that model, analyse and structure different interactions among rational players. These interactions can be a conflict as it can be a cooperation. It is worth noting that rational player is a player who wants to maximize his own good. Basically, game theory is used to study the behavior of inviduals in economics, and then it has been applied to solve a wide variety of problems in almost all disciplines due to its various games classifications.

First, let us start with a standard representation of a game(normal form or strategic form game):

• A set of players M = {1...m}.

• A set of actions A i for player i.

• A set of action profiles or pure strategies, denoted by

A = A 1 × ... × A m .
Cooperative game theory

13

• An utility function of player i, u i : A -→ R, called also payoff function or value function for cooperative games, which quatifies the degree of preference across a given action. The utility function assigns a certain outcome to each player depending on his strategy and the strategies of other players.

Generally, almost all games consist of the same strategic form game components which we have defined above. However, components may take several forms, even terminologies may be changed, depending on the game classification, aims and applications. In particular, in this dissertation, we are interested in two important categories of games that have been intensively applied in wireless networks and have served in solving numerous challenges. First, the cooperative game theory is used to model how players cooperate and compete as coalitions through unstructured interactions in order to maximize their mutual utilities [START_REF] Bannour | Mimo-ofdm based energy harvesting cooperative communications using coalitional game algorithm[END_REF]. On the other hand, the non-cooperative game theory is used to investigate interactions between competing (self-interested) players, each of which tries to maximize his payoff by acting individually in a defined procedure.

Cooperative game theory

Cooperative game theory [START_REF] Myerson | Game theory[END_REF] includes a set of various analytical frameworks to investigate cooperation behaviors of rational players. Thus, depending on players' interests, there are two main branches of cooperative games: Bargaining theory [START_REF] Muthoo | Bargaining theory with applications[END_REF] and coalitional games [START_REF] Saad | Coalitional game theory for communication networks[END_REF]. The former is applied when players have conflicting interests, seeking to mutually benefit from finding an agreement, while the latter focuses on what coalitions of players, rather than a single player, can achieve. The basis of this theory was firstly conceived by John von Neumann and Oskar Morgenstern in [START_REF] Morgenstern | Theory of games and economic behavior[END_REF] with transferable utility coalitional games. Since then, several interesting subclasses of cooperative games have been proposed and several solution concepts have been introduced.

Specifically, during the past few years, coalitional games have shown their robustness in wireless networks to model cooperation for many scenarios [START_REF] Saad | Coalitional game theory for communication networks[END_REF], especially when several agents must share a common resource among them, such as relay nodes, wireless channel, and mobile nodes. Basically, these games may answer the two following questions:

Fundamentals of game theory

• Which is the suitable coalition that should be formed?

• How should such coalition divide its utility among its members?

The two main classes of cooperative game are: canonical games and coalition formation games [START_REF] Han | Game theory in wireless and communication networks: theory, models, and applications[END_REF]. In the first games class, forming the grand coalition, which is the coalition of all players in the game, is always beneficial. In other words, no group of players has the incentive to cooperate into a smaller coalition since they will receive a worse payoff. This property is referred to as the superadditivity [START_REF] Saad | Coalitional game theory for communication networks[END_REF]. Also, canonical games aim at studying the stability of the grand coalition and the way the players split their received payoff.

The second games class studies how should the players arrange themselves into an optimal structure. Interestingly, several properties of this structure are analysed in this framework, namely its stability, the optimal coalition size, etc. Generally, coalition formation games are not superadditive. In what follows in this section, we focus on a selection of the main properties, basic notions and solution concepts of this class of games.

Coalition-formation games: preliminaries

Coalition-formation games are designed for agents that are willing to cooperate and share their goods in order to achieve a certain purpose that they could not achieve alone. In doing so, in such games, players often attempt to construct an appropriate structure where they maximize their utilities collectively. The unit of this new formed structure is called coalition, corresponding to a group of players. Indeed, cooperating within a small unit rather than a bigger one may be quite interesting for several applications in wireless networks [START_REF] Juan | Data-centric clustering for data gathering in machine-to-machine wireless networks[END_REF][START_REF] Sawyer | Evolutionary coalitional game for correlation-aware clustering in machine-to-machine communications[END_REF][START_REF] Song | Correlation-aware machine selection for m2m data gathering in cellular networks[END_REF].

Generally, the formation process is based on a set of negociations, an information exchange in the context of communications networks, and a set of rules. Interestingly, using coalition-formation game frameworks, players may reach a stable architecture where all entities are not motivated to form further coalitions anymore. To this end, the main challenge of coalition-formation game is to investigate the optimal network structure with respect to a set of network constraints.

To introduce the main components and the basic notions, we consider a finite non-empty set of players M = {1, . . . , m}. Each subset S i ⊂ 2 M represents a coalition1 .

The set M is referred to as the grand coalition and ∅ is referred to as the empty coalition.

Definition

v : S i ∈ 2 M → R |S i | .
Indeed, in NTU-games, the value of each member of S i depends on the actions that all coalition members take jointly.

Moreover, in a given partition of M , the dependence of a given coalition S i outcome on the structure of the remaining coalitions identifies two coalitional formation games forms, defined as follows:

• Characteristic form: It is the most basic form of the coalitional game proposed by [START_REF] Morgenstern | Theory of games and economic behavior[END_REF]. In fact, the characteristic form implies that the outcome of a coalition S i ⊂ M depends only on the members within S i , without focusing on how the rest of coalitions are arranged.

• Partition form: In contrast, a coalitional game in partition form [START_REF] Yi | Stable coalition structures with externalities[END_REF] implies that the outcome of a coalition S i ⊂ M does not depend solely on the members within S i but also on how remaining coalitions are arranged.

Figure 2.1 illustrates the difference between the two forms through a simple coalitional UAVs network game example.

In the following section, we go through the main goal of this game, which is the coalition formation process, and we present different related approaches and solutions concepts.

Coalition-formation games solution concept: Algorithmic approaches

After introducing the general coalition-formation model and its related properties, our goals now are: to discover how can players form an optimal coalitional structure dynamically through algorithmic solutions and to investigate the appropriate solution concepts that can be achieved by an optimal structure.

The key question is why do we use algorithmic solutions? Basically, the coalition formation game determines the optimal coalitional structure that finds a final stable allocation of payoffs to every players. To reach such a result, we have to check all possible partitions of the player set M, which is equal to the M-th Bell number. Note that the Bell number is obtained by the recursion

B n+1 = n k=0 k n B n , B 0 =B 1 =1
. However, this centralized approach is proven to be NP-hard [START_REF] Apt | A generic approach to coalition formation[END_REF]. Moreover, there is a need for many distributed applications to perform the coalition formation process in a distributed manner. Hence, several solutions have been proposed in the literature aiming to design distributed and low complex algorithms for forming coalitions. Merge and split [START_REF] Apt | A generic approach to coalition formation[END_REF] and hedonic games [START_REF] Bogomolnaia | The stability of hedonic coalition structures[END_REF] represent the main algorithms that have been applied in many practical scenarios. In what follows, before moving on to both games definitions, we present first the concept of the preference order, which is a crucial ingredient of coalition formation game.

Preference orders

By means of algorithmic approaches, players can make decisions autonomously throughout the coalition formation process, such as joining or leaving coalitions, breaking or combining them, etc. All decisions are made using preference orders, called also comparison orders, in order to compare different groups in the network. Definition 2.5. Given a partition Π consisting of a set of coalitions in M, a preference order is defined as a monotonic, transitive binary relation that compares any two coalitions of nodes S and T ∈ Π by comparing their utilities.

Generally, a preference order can be either reflexive or irreflexive. Moreover, as stated in [START_REF] Apt | A generic approach to coalition formation[END_REF], there exist two categories of preference orders; coalition-value orders and individual-value orders. The former compares two coalitions using their value (which is a single real number). Indeed, this category is well suitable for TU-games. The latter compares two coalitions using their individual players payoffs. In this regard, utilitarian order and Pareto order make up the most important preference orders, defined as follows:

• The utilitarian order: belongs to coalition-value orders category. It is suitable for TU games where a group of players prefers to organize themselves into a col-

lection A = {A 1 , • • • , A l } instead of B = {B 1 , • • • , B s } if the total social welfare achieved in A is strictly greater than in B, i.e., l i=1 v(A i ) > s i=1 v(B i ).
• The Pareto order: belongs to coalition-value orders category. It is suitable for both TU and NTU games. The comparison is performed using the individual

Merge and split approach

Merge and split procedure is proposed by Aumann and Dreze [START_REF] Aumann | Cooperative games with coalition structures[END_REF] in 1974 and since

then it has been used in various areas of application such as computer science and economics, etc. This approach is quite simple. In fact, it is based mainly on the following two rules.

Definition 2.6. (Split rule) In a given partition Π 1 , a coalition l i=1 S i decides to split when ({S

1 , • • • , S l }, Π 1 ) ( l i=1 S i , Π 2 ). Thus, l i=1 S i → {S 1 , • • • , S l } and Π 1 → Π 2
, where Π 2 is the new formed partition after the operation of split.

Definition 2.7. (Merge rule) In a given partition Π 1 , the set of coalitions {S 1 , • • • , S l } decides to merge when ( l i=1 S i , Π 2 ) ({S 1 , • • • , S l }, Π 1 ). Thus, {S 1 , • • • , S l } → { l i=1 S i } and Π 1 → Π 2
, where Π 2 is the new formed partition after the operation of merge.

Thus, a decision to split (resp. merge) is an agreement among all coalition players to break (resp. form) a coalition. Note that the decision making depends on the preference order. Let us consider a coalitional game (v, M) and two partitions of the

set {s 1 , s 2 , • • • , s r } ⊂ M, denoted by P 1 = {C 1 , C 2 , • • • , C k } and P 2 = { k i=1 C i }.
On the one hand, using utilitarian order ensures that the coalition decision improves the social welfare as the two rules suggest;

• Merge rule

P 1 → P 2 if k i=1 v(C i ) > v( k i=1 C i )
• Split rule

P 2 → P 1 if k i=1 v(C i ) < v( k i=1 C i )
On the other hand, using the Pareto order guarantees that no single player is worse off through split or merge;

• Merge rule

P 1 → P 2 if k i=1 v j (C i ) ≥ v j ( k i=1 C i )∀j ∈ {1, 2, .
..r} with at least one strict inequality for a player s l • Split rule

P 1 → P 2 if k i=1 v j (C i ) ≤ v j ( k i=1 C i )∀j ∈ {1, 2
, ...r} with at least one strict inequality for a player s l It is worth noting that since merge and split algorithm supports partition form, decision to merge or split a given coalition C i should not hurt not only its members but also all remaining coalitions members belonging to M.

Merge and split algrithm can be implemented in a distributed fashion with no reliance on any centralized unit. It consists of a finite number of merge and split iterations that finally converge and result a new stable partition. Besides the adaptation possibility to distributed networks, this algorithm has shown its potential ability to be adapted to environmental changes that may occur in low-power wireless networks such as mobility, dysfunction of some users or deployment of new ones, etc. Figure 2.2 shows the main algorithm stages and how it can be adapted to a mobility scenario in which players should re-organize themselves in order to meet a certain goal.

Stability notions

In the context of coalitional games, stability is referring to the state in which players would not have incentive to quit their current coalitions. Indeed, by achieving a stable partition network, players can obtain the maximum worth by cooperating. Specifically, there are two stability forms whereby we can evaluate the stability of the final network partition obtained through the merge and split algorithm [START_REF] Apt | Stable partitions in coalitional games[END_REF]. Both of thse stability forms are based on the defection function notion, denoted by D, defined as follows: Definition 2.8. A defection function is a mapping that assigns to each partition of M some collections of the grand coalition.

Two defection functions are considered: D h p defection function that allows formation of all possible partitions of the grand coalition by merge and split operations, and D c defection function that allows formation of all possible collections in the grand coalition. Hence, if the final resulting partition is D h p stable, then no player, or

hedonic games

Hedonic games is a specific class of coalition formation games. This class of games consists of several interesting properties and well-defined solutions that can be adopted in the local and distributed ways especially by dynamic environments [START_REF] Wu | Dynamic distributed resource sharing for mobile d2d communications[END_REF]. Formally, a hedonic game is defined as a coalitional game satisfying two conditions:1) The payoff of any player depends uniquely on the coalition members to whom he belongs (characteristic form game), and 2) The coalition formation is performed based on the individual preferences of the players over their possible coalitions set.

Non-cooperative game theory 21

In a hedonic coalition formation algorithm, each player uses the switch rule, introduced as follows: Definition 2.9. Given a partition Π = S 1 , S 2 , ..., S k of M, player j ∈ M, decides to leave its current coalition S h (j) and join another coalition S h ∈ Π where h = h , if and only if S h ∪ {j} > j S h . Therefore, the switch transformation can be expressed as

{S h , S h } → {S h \{j}, S h ∪ {j}}
Each player makes a selfish decision to move from its current coalition to a new one, regardless of the effect of his move on the remaining players. Moreover, the preference order that he uses is individual, it compares only its utility with each other one's utility. After a finite number of iterations, the stability of the final partition can be investigated by numerous stability concepts. As stated in [START_REF] Bogomolnaia | The stability of hedonic coalition structures[END_REF], there exist four forms of stability: core, Nash, contractually individual stability and individual stability. All of them capture the idea that no player or a group of players has an incentive to move from its existing coalition (See [START_REF] Dreze | Hedonic coalitions: Optimality and stability[END_REF] for more details). Specifically, the Nash-stability in hedonic games is the strongest notion of stability. Interestingly, it is similar to the Nash Equilibrium in the noncooperative games ensuring that no player has incentive to leave a coalition.

Non-cooperative game theory

Non-cooperative game naturally captures the interactions among agents, having conflict interests, that are competing against each other, each of which acts alone trying to maximize its own payoff selfishly. In communication networks, such game may model several scenarios. For example, players can be base stations (BSs) or users seeking to allocate the resources in a cellular network in order to ensure a good system throughput. Also, they can be users operating with the same frequency and controlling their transmit power in order to reduce the interference and meet the desired QoS.

The most important property in game theory, specifically in the non-cooperative game category, is the Nash Equilibrium (NE) [START_REF] Nash | Equilibrium points in n-person games[END_REF]. The NE represents the most stable profile of actions in the non-cooperative game in the sense that any player cannot profit from unilateral deviation given the other players actions. Formally, the NE is defined as Fundamentals of game theory follows:

Definition 2.10. Given the set of strategies a * = (a * 1 , a * 2 , . . . , a * M ), a * is a Nash Equilibrium if; ∀j ∈ {1 . . . M }, a * j = argmax a j U j (a j , a * -j ) (2.1)
where U is the utility function and a * -j denotes an individual strategy from the NE of any player who is different from j.

Synthesis and Conclusion

Althought we have not mentioned all aspects of the coalitional-formation games, we denote the richness of these frameworks, the variety of the games forms and how they are enough accurate to deal with many specific scenarios in wireless communication networks. Indeed, in this chapter the focus was mainly on coalitional-formation games since it represents the crucial modeling tool to almost all the proposed solutions in this dissertation.

One of the key ideas in these games is how can we assess the obtained result? In other words, which are the most suitable solution concepts we can adopt for our designed game? Actually, many notions have been proposed as solutions concepts dealing with a wide range of coalition-formation games. Several researches on stable partitions have focused on characteristic form games. Indeed, most popular solutions concepts for coalitional games are designed for characteristic form model [START_REF] Apt | A generic approach to coalition formation[END_REF]. In fact, in addition to those that we have introduced in Section 2.3, there exist also the core [START_REF] Banerjee | Core in a simple coalition formation game[END_REF] and the shapley value [START_REF] Saad | Coalitional game theory for communication networks[END_REF] which are purely dedicated to such games.

The former stands for a set of payoff profiles of all players implying that no coalition tends to deviate and become better off. Note that the existence of the Core is not guaranteed. For many games, it can be empty. The latter represents a unique payoff profile called value as a possible solution concept which is characterized by means of three concepts (See [START_REF] Saad | Coalitional game theory for communication networks[END_REF]).

On the other hand, it is more challenging to solve partition form games for which only few solutions have been proposed. To cope with this problem, it is crucial to devise new algorithms and redefine some existing solution concepts to form the stable coalitional network. For example, it is recommended to redefine merge and split rules

Synthesis and Conclusion

23

within the coalition formation algorithm so that to deal with its respective solutions introduced in Section 2.3. Another example has been introduced in [START_REF] Saad | Coalitional games in partition form for joint spectrum sensing and access in cognitive radio networks[END_REF], where the authors borrowed concepts from the stability notions of hedonic games and extended them to handle the partition form.

Last but not least, given the importance of distributed applications, it is necessary to develop coalition formation algorithms in a distributed fashion. In doing so, there are three steps to be followed. first, choosing the adequate rules for forming coalitions.

Second, fixing the suitable order to compare collections of coalitions. Finally, finding the appropriate solution concepts.

We introduce in the following chapter one of the promising technologies that promotes distributed applications due to its progressive execution, which is the Instantly decodable network coding.

Introduction

In this chapter, we provide some insights into the network coding technology and its main variants, as well as the instantly decodable network coding (IDNC), which represents one of the theoretical foundations of this thesis. Furthermore, we introduce the significant strides that have been made in this particular subclass and we highlight our major related contributions that bridge the gap between IDNC, distributed lowpower networks, game theory and a variety of today's applications requirements.

In the next section, a general overview of the network coding basics is given. The instantly decodable network code is introduced in section 3.3. Some performance aware IDNC works are investigated in section 3.4. We present our contributions in section 3.5 and finally section 3.6 concludes the chapter.

Introduction to network coding

Instead of delivering bits in information flows as commodities, we can significantly improve the efficiency of the bandwidth utilization by mixing them. This new type of information delivery can be performed as long as we make sure that the receiving node has enough "clues" to be able to recover the original packets from the sending node.

Simply, that is the definition of network coding (NC). Indeed, the network coding technology has been pioneered by the seminal work [START_REF] Ahlswede | Network information flow[END_REF] where it was proposed that the source and the intermediate nodes can perform linear functions of the incoming data packets to create the outgoing data packets. In this regard, an important subclass of network coding is the linear network coding [START_REF] Ho | A random linear network coding approach to multicast[END_REF], in which the nodes should solve a set of linear equations over a finite field in order to reconstruct the original packets from the coded ones. In multicast networks, the min-cut capacity can be achieved by network coding to each destination [START_REF] Medard | Network coding: Fundamentals and applications[END_REF].

Actually, tremendous works have appeared, studying the network coding for a variety of wireless networks and demonstrating its benefits to improve throughput, reduce the delay, enhance packet transmission, flexibility as well as network security [START_REF] Medard | Network coding: Fundamentals and applications[END_REF][START_REF] Lima | Random linear network coding: A free cipher?[END_REF].

Let us illustrate the network coding concept through a basic example using XOR operation.

Example 3.1. Figure 3.1 depicts a wireless network that connects three nodes A-R-

The instantly decodable Network codes

Basically, two special subclasses of network coding are identified in the literature: random network coding (RNC) and opportunistic network coding (ONC). Using the RNC, at each transmission, the sender combines all source packets into one coded packet using random coefficients from a given finite field. However, in the ONC, the sender detects coding opportunities such as received and lost packets at receivers and combines only the suitable packets to achieve a certain optimization goal [START_REF] Douik | Instantly decodable network coding: From centralized to device-to-device communications[END_REF].

In broadcast scenarios, RNC is shown to be optimal in minimizing the number of packet transmissions [START_REF] Lucani | Broadcasting in time-division duplexing: A random linear network coding approach[END_REF][START_REF] Eryilmaz | On the delay and throughput gains of coding in unreliable networks[END_REF]. Moreover, it can reach the broadcast capacities for a significant number of source packets and allows packet recovery without any feedback. However, RNC is proven to be beneficial only for delay-tolerant applications as it does not allow progressive decoding of packets, instead it uses a bloc of all packets at once. Futhermore, as mentioned before, it requires random coefficients from a Galois Field to code packets, then a high computational capacity for matrix inversion to decode Network Coding background them, which is not well suited for energy-constrained applications as well as mobile applications. Along with this, RNC cannot be employed either in multicast or unicast scenarios where some nodes in the network require receiving distinct subsets of the frame.

On the other hand, a promising opportunistic subclass of NC, which can be adapted to delay-sensitive applications having low-computation requirement, is the instantly decodable network coding (IDNC) [START_REF] Douik | Instantly decodable network coding: From centralized to device-to-device communications[END_REF][START_REF] Sundararajan | Online network coding for optimal throughput and delay -the three-receiver case[END_REF]. Indeed, IDNC have seen rise of interest as an online network code in the wake of massive enhancements of QoS for users in real-time applications. The key property of IDNC is its simplicity in almost all stages of the encoding/decoding process from the detection of coding opportunities (known as side information) by the sender, to the packet recovery at the receivers. The main IDNC features, therefore, are multifold:

• The flexibility of the packets selection stategy at the sender that reflects the optimization goal of a particular application.

• Encoding is performed using only XOR binary operation.

• Once they are successfully received, the coded packets are instantly decoded using the XOR operation as well, which avoids the expensive computational complexity.

• Decoding is allowed in a progressive manner at receivers which can reduce significantly the decoding delay.

• No need for buffers to store non-instantly decodable packets for future decodings. Instead, they are immediately rejected.

It is worth mentioning that there is generally two configurations in which IDNC can be implemented, including the point-to-multipoint (PMP) network and the cooperative data exchange (CDE) network. In the former setting, a set of nodes receive their required packets exclusively from a central unit such as a BS that is in charge of packet recovery. In the latter setting, a local and cooperative exchange of received packets is allowed at the devices so that all of them receive all the required packet.

The potential of IDNC has been recently identified by numerous studies in both settings. In the next section, we present some of these studies taking into account a QOS aware Instantly Decodable Network Coding 29 variety of performance parameters.

QOS aware Instantly Decodable Network Coding

The mostly considered performance parameters in IDNC are the decoding delay and the completion time. The former refers to the individual delay experienced by each receiver when he cannot recover immediatly one of his missing packets and the latter refers to the overall packet recovery time. Moreover, the mostly proposed solutions were implemented over PMP networks where the BS is responsible for sending and recovering packets. Indeed, minimizing both metrics over centralized schemes have been the subject of intensive works in the past decade [START_REF] Sorour | Completion delay minimization for instantly decodable network codes[END_REF][START_REF] Douik | Decoding-delaycontrolled completion time reduction in instantly decodable network coding[END_REF][START_REF] Karim | Rate-aware network codes for video distortion reduction in point-to-multipoint networks[END_REF][START_REF] Keshtkarjahromi | Content-aware network coding over device-to-device networks[END_REF][START_REF] Douik | A gametheoretic framework for network coding based device-to-device communications[END_REF][START_REF] Douik | Data dissemination using instantly decodable binary codes in fog-radio access networks[END_REF][START_REF] Karim | On using dual interfaces with network coding for delivery delay reduction[END_REF][START_REF] Sorour | Completion delay minimization for instantly decodable network codes[END_REF][START_REF] Douik | Completion time reduction in instantly decodable network coding through decoding delay control[END_REF][START_REF] Douik | Delay reduction in multi-hop device-to-device communication using network coding[END_REF][START_REF] Muhammad | Instantly decodable network coding protocols with unequal error protection[END_REF][START_REF] Rouayheb | On coding for cooperative data exchange[END_REF][START_REF] Aboutorab | Instantly decodable network coding for delay reduction in cooperative data exchange systems[END_REF][START_REF] Esmaeilzadeh | Optimizing completion delay in network coded systems over tdd erasure channels with memory[END_REF][START_REF] Aboutorab | Instantly decodable network coding for completion time or decoding delay reduction in cooperative data exchange systems[END_REF][START_REF] Douik | Delay reduction in multi-hop device-to-device communication using network coding[END_REF][START_REF] Karim | Network coding for video distortion reduction in device-to-device communications[END_REF]. For example, authors in [START_REF] Sorour | Completion delay minimization for instantly decodable network codes[END_REF], addressed the problem of minimizing the completion delay in wireless multicast and broadcast settings in which every receiver demands a different set of packets. For this purpose, the problem has been formulated as a stochastic shortest path and a twostage maximum weight clique selection algorithm was designed. On the other hand, in [START_REF] Douik | Decoding-delaycontrolled completion time reduction in instantly decodable network coding[END_REF], the authors studied the problem of reducing the decoding delay for IDNC. They showed that the minimum decoding delay problem could be formulated as a maximum weight clique problem over a well defined graph. Since finding the maximum weight clique of the graph is intractable, they designed a simple heuristic algorithm. Douik et al. proposed in [START_REF] Douik | Completion time reduction in instantly decodable network coding through decoding delay control[END_REF] to establish a novel relationship between the completion time and the decoding delay. In fact, completion time expression is developed in function of the decoding delay and the expected erasure probabilities. Therefore, this relationship allows minimizing the completion time through the decoding delay control. The solution in [START_REF] Douik | Decoding-delaycontrolled completion time reduction in instantly decodable network coding[END_REF] aimed at minimizing the completion time through the approach of decoding delay in both scenarios: perfect and imperfect feedback over persistent erasure channels. The problem was formulated as a maximum weight clique problem in the IDNC graph and two heuristic algorithms were proposed to solve this problem.

Actually, not only the decoding delay and completion time metrics are studied in IDNC networks, but also some additional performance metrics are considered to fit a specific range of applications. In particular, in a PMP network, authors in [START_REF] Karim | Rate-aware network codes for video distortion reduction in point-to-multipoint networks[END_REF] considered the problem of reducing video distortion of a set of devices using IDNC. All devices are interested in receiving in real time a video sequence broadcasted from a BS. To study order-constrained and time-critical applications, authors in [START_REF] Karim | On using dual interfaces with network coding for delivery delay reduction[END_REF] adressed Network Coding background the problem of minimizing the dual delivery delay in a heterogeneous network architecture. This metric measures the packet order degradation compared to the optimal in-order delivery of packet to the devices. In doing so, a dual interface IDNC graph was constructed in order to catch the suitable coding opportunities.

However, few studies on IDNC were conducted in cooperative data exchange networks. [START_REF] Douik | A gametheoretic framework for network coding based device-to-device communications[END_REF], a non-cooperative game theoretic framework in order to solve the completion delay minimization problem in a fully connected IDNC-based cooperative data exchange. Afterwards, in [START_REF] Douik | Data dissemination using instantly decodable binary codes in fog-radio access networks[END_REF], the authors extended the study of [START_REF] Douik | A gametheoretic framework for network coding based device-to-device communications[END_REF] to deal with D2D enabled systems in imperfect feedback environments. They proposed more games to reduce further delay metrics including the maximum decoding delay and the sum decoding delay. Furthermore, they proposed to employ the reinforcement learning to deal with the imperfect feedback.

Douik et al. introduced, in

For a content-aware IDNC network, in which not all devices are interested in the same content quality, the work in [START_REF] Keshtkarjahromi | Content-aware network coding over device-to-device networks[END_REF] provided a novel content and loss aware IDNC scheme that improves jointly the completion time and content quality. The comprehensive survey [START_REF] Douik | Instantly decodable network coding: From centralized to device-to-device communications[END_REF] discusses different IDNC characteristics and presents recent advances in IDNC application.

As it has been seen in the previous studies, various relevant metrics have been considered in order to meet enough QoS requirements over several interesting real-time IDNC-based applications. However, such metrics are not sufficient for wireless networks with energy constraint. Such networks need to guarantee the energy efficiency as a fundamental requirement in addition to QoS requirements where the energy consumption metric must be highly concerned.

Since IDNC is a lightweight network code that requires low computational energy consumption, this computational of energy cost is not comparable to the expensive wireless communications energy cost that battery-powered devices should also control.

Therefore, IDNC needs to incorporate the energy constrained networks features in order to address such issue and take advantage of its full potential. To the best of our knowledge, there is no prior work that considers the energy efficiency issue in the IDNC literature neither with PMP networks nor with CDE setting. Thus, this thesis aims to optimize the IDNC utilization by focusing on the challenges raised by numerous distributed real time and energy efficient applications. Specifically, we are interested in designing IDNC frameworks accounting for various properties of these applications, such as devices' scarce batteries, hard deadline, mobility, scalability, erasure wireless channels and limited communication ranges.

Joint QoS and energy aware Instantly Decodable Network Coding

In this dissertation, we focus on autonomous wireless networks where devices are battery-powered and have some QoS requirements that must be achieved. We study the cooperative data exchange scheme over erasure channels in which network coded packets are transfered, then decoded in a progressive, distributed and cooperative way. Specifically, we consider the IDNC as a suitable technology for energy-constrained devices that enables progressive decoding, enhances the network throughput, reduces the computational complexity and memory use by preventing receiving devices from storing non-decodable packets. Moreover, to design the distributed solution, we consider game theory as a suited tool for distributed and self-adaptive schemes.

Note that most of the proposed performance aware solutions in the IDNC literature focus on the design of heuristics algorithms affecting coding decisions in order to optimize the desired metric. However, in this thesis, our key strategy is to focus on optimizing the IDNC encoding/decoding process and designing game theoretical frameworks taking into account jointly the completion time and energy consumption.

The first major contribution of this dissertation is the design of coalitional gametheoretic framework for cooperative data exchange using IDNC over a fully connected wireless network. In fact, we introduce a novel framework from coalitional game theory to model the cooperation in the IDNC game among nodes for energy efficient CDE. We consider jointly the completion time and the consumed energy to increase the network lifetime. In particular, we propose a merge-and-split algorithm, which iteratively operates the coalition formation process in a distributed fashion, and we prove that it converges to a stable coalitional network structure. Moreover, we focus on the mobility issue and we analyse how nodes can adapt to the dynamics of the network. We show that the proposed framework is of low complexity compared to the non-coalitional model, especially for high number of nodes, which increases the scalability of the proposed model. Thereafter, we evaluate the proposed framework Network Coding background using two practical scenarios: A wireless sensor network and a network of flying fleet of drones. Finally, we show that we can reduce the completion delay by considering additional constraint, i.e. the energy consumption. Indeed, we illustrate that the proposed framework reduces the energy consumption and the completion delay at the same time.

For a more realistic scenario, we focus on how wireless nodes can cooperate in limited transmission ranges without increasing the IDNC delay nor their energy consumption.

For that purpose, our second contribution consists in designing a game theoretic framework dealing with multihop IDNC-based CDE network. In fact, we model the problem using a two stage game theory framework. Firstly, we consider that each node determines dynamically its transmission power in a decentralized manner using non-cooperative game theory. The optimal solution of this game allows the players in the next step to cooperate with each other through limited transmission ranges using cooperative game theory in partition form framework. In fact, we propose a constrained coalition formation game that forms an appropriate multihop coalitions. Indeed, the defined framework is of low interference and complexity compared to the maximum transmission range model. Moreover, we analyze the stability of the cooperative game, and demonstrate that the algorithm converges to a stable coalition structure, where all the players do not have incentives to change the coalition they are part of. Thereafter, we show that we are able to improve the energy consumption without hurting the IDNC delay compared to the maximum range cooperative model.

Conclusion

Throughout this chapter, we have highlighted some key ideas of this thesis. First, we have introduced the instantly decodable network coding as a useful paradigm for distributed cooperative low-power networks. We have identified its potential benefits and detailed the major existing related works. Second, we have demonstrated the necessity of considering the energy efficiency over IDNC networks. Given this demonstration, we have presented our main challenges as well as our principal contributions in this thesis under the umbrella of delay and energy aware IDNC networks.

In the following part, we study the IDNC-based CDE network focusing on jointly minimizing the energy consumption and the completion time using game theory. In particular, the next chapter investigates the cooperation among players within a small connected MTC network where all wireless nodes can reach each others via single hop.

Part II

A distributed Framework for Cooperative Data Exchange using IDNC

Introduction

The rapid growth of MTC devices using scarce batteries and dealing with a high content quality brings a number of challenges for the communication community to achieve both the energy efficiency and the QoS requirements of MTC users. These devices are supposed to operate in an area of interest in a relatively uncontrolled way, or rather, they are expected to rely on themselves to meet the aforementioned goals. Hence, innovative and scalable solutions at system and device levels are always welcomed in order to address both operational and environmental costs.

One alternative solution is the cooperative data exchange which is considered as a promising approach wherein wireless nodes are allowed to exchange their packets quickly over a short range and reliable communication channels, for example using IEEE 802.11 adhoc mode. Specifically, a significant attention has been recently drawn by the network coded cooperative data exchange to take advantages of both nodes' cooperation and network coding [START_REF] Douik | Instantly decodable network coding: From centralized to device-to-device communications[END_REF][START_REF] Rouayheb | On coding for cooperative data exchange[END_REF][START_REF] Aboutorab | Instantly decodable network coding for delay reduction in cooperative data exchange systems[END_REF]. Such solutions have been shown efficient to increase the throughput and reduce the delay as well as the traffic of wireless networks.

On the other hand, the energy efficiency has received a considerable interest when designing communication protocols. In fact, ecological concerns increasingly attract attention in communication systems [START_REF] Zarifzadeh | Energy-efficient topology control in wireless ad hoc networks with selfish nodes[END_REF]. Furthermore, game theory seems a great tool not only to improve distributed solutions but also to design wireless networks architectures according to the desired system performance.

Interestingly, the present chapter develops a unified game theoretic framework that improves both the completion time and the network lifetime of an MTC network in a distributed fashion. In particular, we maintain the XOR based IDNC technology.

In [START_REF] Douik | Data dissemination using instantly decodable binary codes in fog-radio access networks[END_REF], authors studied an MTC network similar to the one considered in this chapter.

They introduced a noncooperative game theoretic framework in a fully connected (D2D) network in order to solve the IDNC delay minimization problem. For this purpose, they addressed the problem of the selection of the transmiting device in order to serve a maximum number of receivers with a new recovered packet in each transmission. The problem was modeled as a non-cooperative potential game with self-interested players.

In a fully connected multicast IDNC based CDE system, authors in [START_REF] Aboutorab | Instantly decodable network coding for completion time or decoding delay reduction in cooperative data exchange systems[END_REF] focused jointly on reducing the completion time and avarage decoding delay. To do so, they formulated the selection problem of the optimum coded packet and the suitable transmitting sender using maximum clique selection and the stochastic shortest path (SSP) technique. Since finding both respective optimum solutions intractable, they proposed two heuristic algorithms to solve the problem.

According to most of the existing IDNC based CDE schemes, including the aforementioned works in [START_REF] Douik | A gametheoretic framework for network coding based device-to-device communications[END_REF][START_REF] Douik | Data dissemination using instantly decodable binary codes in fog-radio access networks[END_REF][START_REF] Douik | Delay reduction in multi-hop device-to-device communication using network coding[END_REF][START_REF] Aboutorab | Instantly decodable network coding for delay reduction in cooperative data exchange systems[END_REF][START_REF] Aboutorab | Instantly decodable network coding for completion time or decoding delay reduction in cooperative data exchange systems[END_REF][START_REF] Douik | Delay reduction in multi-hop device-to-device communication using network coding[END_REF] that involve battery-powered devices over D2D networks, an optimal IDNC packet combination can target a device that optimizes for example the transmission rate or the decoding delay. However, does the selected sender have enough stored energy to target any decoding receiver in the field ? Can he really reach all interested receivers ? Thus, an ideal energy efficient scheme should address explicitly the energy efficiency as a central issue. Hence, we found a great interest to develop a framework that involves energy-constrained MTC devices in a CDE network using IDNC. Motivated by improving the network efficiency and modelling aspect for a fully autonomous wireless nodes, we design the CDE among wireless nodes using cooperative game theoretical framework in partition form. Moreover, we propose a distributed merge-and-split algorithm that creates appropriate coalition groups accounting for the completion time and the energy efficiency.

The major contributions are summarized as follows:

• We introduce a novel framework from coalitional game theory to model the cooperation in the IDNC game among nodes for energy efficient CDE.

• We focus jointly on the completion time and the consumed energy to increase the network lifetime.

• We propose a merge-and-split algorithm, which iteratively operates the coalition formation process in a distributed fashion, and show that it converges to a stable coalition network structure.

• The proposed framework is of low complexity compared to the non-coalitional model, especially for high number of nodes, which increases the scalability of the proposed model.

• We evaluate the proposed framework using two practical scenarios: A Wireless IDNC sensor network and a network of flying fleet of drones.

• We reduce the completion delay by considering additional constraint, i.e. the energy consumption. Indeed, we illustrate that the proposed framework reduces the energy consumption and the completion delay at the same time.

The remainder of this chapter is organized as follows. In the next section, we describe the system model. Section 4.3 defines all useful parameters related to the new proposed IDNC recovery protocol as well as the IDNC graph. Thereafter, we present in Section 4.4 the coalitional game model and the utility function. The description of the merge-and-split algorithm is provided in section 4.5. Section 4.6 compares and analyzes the performance of the proposed scheme, and Section 4.7 concludes the chapter.

System model

We consider a BS trying to deliver a frame N of N source packets {1, • • • , N } to a group M of M wireless nodes, denoted {1, • • • , M }, each of which requires the reception of all source packets. Note that the wireless nodes can be arranged in a unique cluster or in multiple clusters. The first source sender can be a simple node as it can be a wireless base station. Node k ∈ M may lose a packet from node l ∈ M with a probability q k,l that depends mainly on the distance between them. In this model, we assume that the BPSK modulation is used in the physical layer transmission. The bit error probability is defined using the Q-function

P b = Q( √ δ)
, where δ represents the signal to noise ratio (SNR). δ ∼ = SN R 0 d β , where d is the inter-node transmission distance, and β is the path loss exponent. Thus, the packet erasure probability is given by p = 1 -(1 -P b ) L , where L is the number of data bits per packet.

At the beginning, the BS transmits sequentially the N uncoded packets of the frame.

For each successfully received packet, each user sends an acknowledgement to the BS. The retransmission of the packet is required only if it is not received by no user.

Therefore, when at least each packet is acknowledged once, this initial phase ends.

We assume that all transmission feedbacks are perfect.

For every node k ∈ M, packets from N belong to one of the two following sets :

• The HAS set (H k ): packets successfully received by node k. • The WANTS set (W k ): missed packets for node k.

The feedback matrix L = [l k,j ], k ∈ M, j ∈ N , is expressed as follows:

l kj (t) = 0 if j ∈ H k 1 if j ∈ W k (4.1)
Before starting the recovery phase, nodes may arrange themselves by forming a novel partition Π of collaborating nodes. A partition Π is defined as a set

{S 1 , • • • , S m } of m mutually disjoint clusters such that m i=1 S i = M, with m cluster heads CH = {CH 1 , • • • , CH m }.
Thus, this coalition formation phase is performed under the control of coalition heads CH according to our proposed delay and energy aware IDNC cooperative scheme which will be introduced in the next section. Note that the cluster heads designation is beyond the scope of this chapter. In fact, many works have studied methods of cluster head selection (see [START_REF] Leu | Energy efficient clustering scheme for prolonging the lifetime of wireless sensor network with isolated nodes[END_REF], [START_REF] Khan | Fuzzy logic based cluster head selection for homogeneous wireless sensor networks[END_REF] and [START_REF] Hadzic | Reference node selection for cooperative positioning using coalition formation games[END_REF]). In our proposed solution, the node that has more residual energy is supposed to be elected as a cluster head. Figure 4.1 illustrates clearly the described system model. Subsequently, once the coalitions are formed, the recovery phase begins. It consists A Coalitional Game-theoretic Framework for Cooperative Data Exchange using IDNC of two successive subphases:

1. Intra-cluster recovery phase: In this sub-phase, nodes in the same coalition may cooperate to recover their missing packets. In fact, at every time slot t, one sender is selected to transmit a binary XOR encoded packet by exploiting the diversity of its HAS sets and the received feedbacks from the remaining cluster members. During this phase, since the sender targets only its cluster members, we assume that the same transmission frequency can be reused in different clusters at the same time. Note that spatial frequency reuse have been extensively investigated in [START_REF] Lee | Mobile communications design fundamentals[END_REF]. The process is repeated until all cluster members recover all missing packets. However, it may happen that in a given cluster not all the N packets are available. In such case, the inter-cluster recovery process begins.

2. Inter-cluster recovery phase: Only cluster heads CH perform this phase. After finishing their intra-cluster recovery phase, they cooperate with each other to recover the remaining packets. We assume that CH broadcast immediately the decoded packet to their coalition members. This process is repeated until all cluster heads recover all the packets.

Note that the Inter-cluster recovery phase is required only in the case of the nonavailability of the N packets in at least one coalition.

We assume that single hop transmissions are used within the clusters. Furthermore, the packets sets (feedbacks) of each user are known by all the other cluster members since they can overhear each-other's feedbacks. Indeed, maintaining a feedback matrix of the cluster is of lower complexity and of lower overhead than the non-coalitional model. is trying to recover a set of 3 packets {p 1 , p 2 , p 3 }. In the intra-cluster recovery phase, devices in S 1 receive all their wanted packets after exchanging two network-coded packets p 2 ⊕ p 3 and p 1 . However, since no device in S 2 has the packet p 3 , their intracluster recovery phase is blocked after their first recovery transmission. In that case, the inter-cluster recovery phase is required so that all devices in the second cluster receive p 3 .

At each recovery stage, the suitable decoding packet in the cluster with its corresponding sender is selected by the CH taking into account the completion time and the consumed energy. In this setup, although the same frequency is reused throughout the clusters, the interference between nodes is reduced since the intra-recovery transmissions are made over short ranges. Nevertheless, in some cases where we have some scattered coalitions, collisions may happen during the recovery process. Moreover, executing the intra-cluster recovery phase simultanously in every cluster reduces significantly the duration of recovery process. Note that in the reference paper [START_REF] Douik | Data dissemination using instantly decodable binary codes in fog-radio access networks[END_REF],

the delay-aware decision making of the suitable combined packets and the transmitting device is made by all nodes in the network and the network-coded packets are transmitted for all nodes whatever the network size is.

A packet received by node k can be one of the following:

• Non-innovative if it does not bring new packet to the receiver.

• Instantly Decodable if it contains exactly one source packet from W k .

•

Energy consumption model

We consider that each node k has a battery with a residual energy of Es k , k ∈ M.

The simple energy model, that we have used in this chapter, is introduced in [START_REF] Sengottaiyan | S-seech secured -scalable energy efficient clustering hierarchy protocol for wireless sensor network[END_REF].

It considers the inter-node distance d and the free space f (d 2 power loss) or multi path fading m (d 4 power loss) channel model. Hence, the required energy for node k to send an L-bit coded packet using the electrical energy Eelec per bit and the threshold distance d th is:

Ec k = L × Eelec + L × f d 2 if d ≤ d th L × Eelec + L × m d 4 if d > d th (4.2)

Recovery protocol 4.3.1 Definitions

This subsection presents all the definitions of cluster-IDNC delays. In addition to energy consumption minimization, this chapter aims to minimize the number of required recovery stages in every cluster S i , called the cluster-completion time C S i defined as follows:

Definition 4.1. For node k, the individual completion time C k∈S i is the required number of recovery transmissions to receive all the missing packets. Thus, the clustercompletion time C S i is the total number of needed transmissions by cluster S i so that Recovery protocol all its members recover their packets i.e. C S i = max k∈S i C k .

Inspired by the study in [START_REF] Douik | Decoding-delaycontrolled completion time reduction in instantly decodable network coding[END_REF], we consider the approach of decoding delay control in order to reduce the completion time. To re-express the cluster-completion time, let us first define the decoding delay. Let t denote the time slot index or the recovery stage index when one node in every cluster performs a recovery transmission. For example, t = 2 refers to the second transmission.

Definition 4.2. In each cluster S i , a node k ∈ S i , with non-empty W k , encouters one unit increase of decoding delay, denoted by d t k∈S i , if it receives a non-innovative or non-instantly decodable packet or if it does not receive any decoding packet. This can happen when the recovery process is stopped (due to the non-availability of the N packets in the HAS sets of the cluster members) in that cluster waiting for the execution of the inter-cluster recovery phase. Definition 4.3. In each cluster S i ∈ S, the accumulative decoding delay D t k∈S i is the summation of the decoding delays units experienced by receiver k until the time slot t. Thus, the overall decoding delay D k∈S i , experienced by k, is the summation of the decoding delays units throughout both recovery phases.

Corollary 1. The overall decoding delay experienced by node k ∈ S i is expressed as follows:

D k∈S i =        t S i max s=1 (d s k∈S i ) + C k s=t * (d s k∈S i ) + t * -t S i max -1 if | j∈S i H j | < N ∀j ∈ S i C k s=1 (d s k∈S i ) if | j∈S i H j | = N ∀j ∈ S i (4.3)
where t S i max is the last intra-cluster recovery stage for S i in the case of the nonavailability of the N packets at cluster members and t * is the first recovery stage of the inter-cluster recovery phase.

Proof. To demonstrate the expression of the overall decoding delay of each cluster member k ∈ S i throughout the entire scenario, two cases are analysed in terms of decoding delay: (i) all the N packets are available in the cluster, (ii) not all the N packets are available in the cluster. The complete proof is provided in Appendix A.

A Coalitional Game-theoretic Framework for Cooperative Data Exchange using IDNC Corollary 2. For each cluster member k ∈ S i , the individual completion time experienced throughout both recovery phases can be approximated as follows:

C k∈S i = |W k | + D k∈S i -q k 1 -q k (4.4)
where |W k | is the size of the WANTS set of k and q k is the packet erasure probability, which is the average packet erasure probability linking k to all remaining cluster members.

Proof. The proof of this corollary is inspired by the work in [START_REF] Douik | Decoding-delaycontrolled completion time reduction in instantly decodable network coding[END_REF] that considers a centralized scheme where the BS is the only transmitter of the decoding packets over one single recovery phase for all users. However, in our work since we consider a clustered CDE, multiple devices transmit to each other inside their clusters over both phases. The complete proof is provided in Appendix B.

IDNC packet construction and graph overview

The problem of finding the optimal coded packet was examined in plenty of recent works to optimize IDNC performance metrics [START_REF] Sorour | Completion delay minimization for instantly decodable network codes[END_REF]- [START_REF] Aboutorab | Instantly decodable network coding for completion time or decoding delay reduction in cooperative data exchange systems[END_REF]. In our model, we use the packet combination technique that optimizes the completion time through decoding delay control, proposed in [START_REF] Douik | Decoding-delaycontrolled completion time reduction in instantly decodable network coding[END_REF]. In fact, since this problem is proven to be NPhard, [START_REF] Douik | Decoding-delaycontrolled completion time reduction in instantly decodable network coding[END_REF] proposes a heuristic algorithm that minimizes the probability of increasing the completion time through a layered control of the decoding delay of each transmission. Therefore, the problem is shown to be equivalent to a maximum weight clique problem in which they designed a multi-layered IDNC graph [START_REF] Sorour | Completion delay minimization for instantly decodable network codes[END_REF] where each layer contains vertices that generate the bigger decoding delay values than those generated in the next layer and so on. The solution is the maximum clique composed of a number of vertices from where the suitable packets are extracted, combined and then transmitted. Let us discover the IDNC graph: To construct an IDNC graph

G = (V, E), a vertex v ij ∈ V is created for every receiver i missing packet j ∈ W i .
Two vertices v ij and v lm are connected with an edge e ∈ E if one of the two following conditions is verified:

• The receivers i and l miss the same packet, i.e. j = m

Coalitional game in partition form for IDNC-based CDE network

47

• The coded packet j ⊕ m is instantly decodable by both receivers i and l, that is, j ∈ H l and m ∈ H i

In order to efficiently reduce the complexity, and by the way the completion time, at every recovery transmission only the CH, in a partition Π = {S 1 , S 2 , ..., S m }, construct a local IDNC graph for their cluster members in order to determine the candidate network codes. Consequently, the graph G is a set of disjoint local graphs as follows: The value of each coalition S is a set of |S| utilities, each of which is a function of the range of this coalition, the availability of the packets at members and also the availability of their stored energy. Thus, we propose a value function that takes into account the key metrics as follows:

G =                  {G 1 , G 2 , ..., G m } if the second recovery phase is not required {G 1 , G 2 , ..., G m , G * } if it
Given coalition S ∈ Π, we define the coalition value set (obtained by all the coalitions)

A Coalitional Game-theoretic Framework for Cooperative Data Exchange using IDNC at stage t ≥ 1 by:

ψ(S, Π)(t) = {ψ k (S, Π)(t) = -α × Ec k (t) Es k (t -1) -T S , ∀k ∈ S} (4.5)
where ψ(S, Π) is a |S|-dimensional real vector whose element k represents the utility that player k can obtain within coalition S in partition Π,

T S = C k (t) ∞ + D k (t) -D k (t -1) 1 ∀ k ∈ S,
and α is a coefficient that tunes the weight of the energy consumption in the decision-making.

As one can clearly see, the utility of node k ∈ S in (4.5) includes two main parts: energy consumption and cooperative delay. Both of them indicate the gain of forming coalitions. Indeed, several studies have considered a utility function as a combination of heterogeneous terms, such as energy and throughput in [START_REF] Yang | A non-cooperative game approach for power control MAC in wireless sensor networks[END_REF] and energy and delay in [START_REF] Jamin | A game theoretic routing framework based on energy-delay conservation in wsns[END_REF]. The first term of the proposed utility function, which is the expected energy efficiency Ec k (t) Es k (t-1) ∈ [0, 1], captures the impact of the consumed energy when transmitting the recovery packet by player k at stage t. Ec k (t) is the energy required to broadcast the recovery packet and Es k (t -1) is the stored energy of k in the previous stage. Note that the energy cost increase when the residual energy of the node decreases. On the other hand, T S is the cooperative delay that takes into account the cluster completion time and the increase of the sum decoding delay over all players in the cluster between two consecutive stages. Moreover, in order to minimize both parameters simultaneously, there is a need to weight the terms of the value function.

Therefore, we multiply the energy consumption part by a coefficient α that tunes the weight of the energy consumption in the decision-making.

Note that this utility function is used by CH in order to select the suitable packet combination as well as the sender node. In fact, every CH chooses the best coalition member that sends the decoding packet with less consumed energy and targeting the maximum decoding nodes in the cluster. Proof. As introduced in definition 2.4, the coalition value in an NTU game is a set of payoff vectors. In our game, ψ(S, Π) in (4.5) is a set of utility vectors since the term of the expected energy efficiency is related to each player in the coalition at every packet recovery transmission. Thus, it can be deduced that the proposed game is with NTU. On the other hand, if some packets are not existing in such a cluster S, the cluster head CH k∈{1,••• ,|S|} cooperates with the other CH l∈{1,••• ,|S|}\k to recover the remaining missing packets in the inter-cluster recovery phase. Thus, T S , and consequently ψ(S, Π), does not only depend on players inside S, but also on players outside S ie. Π\S. Hence, we conclude that the proposed coalitional game is in partition form with NTU.

Proposed coalition formation algorithm

According to the considered coalitional game model, we propose a merge-and-split algorithm to ensure the formation of the appropriate coalitional structure based on the nodes' preferences. Note that the proposed decision-making, i.e. two coalitions are merged or one is split is based on a preference order.

Since we have characterized our CDE game as an NTU-game in partition form, we choose an individual-value order called Pareto order , which is adequate for NTUgames. This order is used only to compare partitions of the same set of players.

Let us consider two partitions of the set {s

1 , s 2 , • • • , s r } ⊂ M, denoted by P 1 = {C 1 , C 2 , • • • , C k } and P 2 = {C 1 , C 2 , • • • , C l }. Consider two different partitions of M : Π 1 = {P 1 , S 1 , S 2 . . . S n } and Π 2 = {P 2 , S 1 , S 2 . . . S n } where {S 1 , S 2 . . . S n } is a collection of M.
We say that P 1 is preferred over P 2 by pareto order if and only if:

(P 1 , Π 1 ) (P 2 , Π 2 ) ⇔ ψ(s i , Π 1 ) ≥ ψ(s i , Π 2 ), ∀i ∈ {1, • • • , n} (4.6)
where there exists at least one node s j such that: ψ(s j , Π 1 ) > ψ(s j , Π 2 ).

ψ(s i , Π 1 ) is the utility of the node s i when cooperating in partition Π 1 and ψ(s i , Π 2 ) is the utility of the node s i when cooperating in Π 2 . Note that this preference order can also compare two coalitions in the same partition as well as two different coalitions in two different partitions.

In order to allow the nodes to build their suitable new structure based on the proposed preference order, we have chosen the merge and split algorithm which is mainly based on the merge and split rules, defined in Section 2.3 of Chapter 2. Such algo-IDNC rithm allows the partition of nodes in a distributed fashion. Indeed, it is the most suitable algorithmic solution for our proposed game theoretic solution due to its low complexity, its adaptability for partition form games and the distributed nature of the CDE problem.

The merge and split coalition formation process

Using the preference order, only the CH make the merge and split decisions. Moreover, in order to reduce the complexity of the proposed algorithm, the split as well as the merge investigations are limited to dividing the coalition into two coalitions or merging two coalitions respectively. Consequently, a coalition of players S i ∈ Π 1 can be split, forming a new partition Π 2 where at least one node can enhance strictly its utility without hurting the payoffs of all remaining nodes in the new structure. Similarly, the decision of merging two disjoint coalitions S j and S i is assigned to both cluster heads CH j and CH i .

Remark 1 : In the proposed coalition formation algorithm, it is worth noting that the split and merge investigations depend on the payoffs of all players in the partition, due to the dependence of the game on externalities (partition form game).

In the initial phase, all players broadcast their feedback matrix allowing CH to perform the first split iteration. Subsequently, merge operation begins. In fact, every CH i investigates all merge possibilities seeking the best coalition for merging. This candidate is determined in such a way that merge process improves both: cooperative delay and consumed energy of at least one player without harming any individual payoff. We assume that any CH i can start the merge process. The objective of the CH is to find a coalition structure that guarantees the lowest energy consumption and delay through a repetitive application of the above rules. Hence, when no further split nor merge operations happens, a new final partition is created in which all nodes will perform their clustered IDNC recovery phases. More details about our proposed algorithm are provided in Algorithm 1.

Theorem 4.1. Any network partition resulting from the proposed merge and split algorithm is ID hp stable.

Proof. In our merge and split algorithm, we are using the Pareto order to merge or Proposed coalition formation algorithm 51 split two coalitions. Hence, after a merge or a split operation, the utility of the nodes in the target coalitions is higher or equal to their utility in the current configuration (at least one node should strictly increase its utility without harming other nodes).

Hence, successive merge and split iterations produce a sequence of partitions Π 1 , Π 2 ,

• • • with Π i+1 Π i ∀i ≥ 1.
However, the number of different partitions of a finite set of node is finite. Therefore, by transitivity and irreflexivity of Pareto order, a partition Π cannot be revisited by the merge and split algorithm and the sequence of merge and split is finite. Thus, the termination of the two rules iterations is guaranteed and then we conclude that the proposed merge-and-split algorithm converges to a final partition Π f in . Suppose that this final resulting partition

Π f in = {S 1 , • • • , S l } is not ID hp stable.
Then there exists two coalitions S i , S j ∈ Π that are interested to perform a merge, i.e. (S j ∪S i , Π f in ) ({S j , S i }, Π f in ) with i = j or a coalition S i ∈ Π interested in splitting over two coalitions

S i = S 1 i ∪ S 2 i , i.e. ({S 1 i , S 2 i }, Π f in ) (S i , Π f in ).
Hence, there exists a new partition Π f in resulting from merge or split operations such that Π f in Π f in , which leads to a contradiction since Π f in is preferred over all the possible partitions obtained through merge and split operations. Thus, any obtained partition resulting from the proposed merge-and-split algorithm is ID hp stable.

The complexity of the proposed merge and split algorithm depends on the number of merge-and-split investigations performed in every iteration, which depends on the number of nodes in the network. In fact, each coalition needs to test the merge with all the other coalitions in Π (worst case scenario). Hence, the total number of merge attempts is at most O(|Π| 2 ), which depends on the number of coalitions and not on the number of nodes in the network. However, since the merge operation is executed by coalition heads CH in a distributed manner, the complexity of the merge operation for each coalition is O(|Π|).

Regarding the splitting operation, the total number of attempts in the worst case implies finding all possible partitions of the coalition, which gives a worst case com-

plexity for the coalition S k of O( 2 |S k | ) where 2 |S k |
is the second order Stirling number of the second kind that counts the number of ways to divide the coalition S k into two new coalitions. Therefore, the complexity of the split operation is closely related to the size of the coalition and not on the total number of users in the system.

On the other hand, as mentioned in section III.C, in our proposed scheme, only CH are in charge of executing the heuristic algorithm [START_REF] Douik | Completion time reduction in instantly decodable network coding through decoding delay control[END_REF] for determining the suitable combined packets. Hence, the complexity of cheking the connectivity of each vertex with the other vertices and renewing its corresponding weight and layer is limited to Therefore, the total complexity for all the network is O(|CH||S k |N ). However, for one grand coalition as in the model considered in [START_REF] Douik | A gametheoretic framework for network coding based device-to-device communications[END_REF], only one big graph is constructed by every node in the network which consists at most of M N vertices. Then, the total complexity for determining the suitable packet is O(M 2 N ).

In the next section, we address the topology changes issue across the multi-UAV network enabling the proposed energy and delay aware coalitional scheme and we discuss how to mitigate its effects on the energy efficiency and the overall completion time.

Mobile cooperative UAV network: a case study

As a special form of mobile ad hoc network (MANET) and vehicular ad hoc network (VANET), the network of multi-UAV is classified as flying ad hoc network A Coalitional Game-theoretic Framework for Cooperative Data Exchange using IDNC (FANET) [START_REF] Gupta | Survey of important issues in uav communication networks[END_REF]- [START_REF] Hayat | Survey on unmanned aerial vehicle networks for civil applications: A communications viewpoint[END_REF] since it presents different characteristics such us node density, power consumption, computation power, frequency of topology changes and node mobility compared to other categories of ad hoc network. Indeed, during last decade, the use of a team of small unmanned aerial vehicles to cooperatively monitor a given area, track target or detect events in real time, has been steadily increased, and has overcome the use of sophisticated drones. Hence, in such events, small UAVs need to cooperate timely and reliably despite their limited flight time and their scarce batteries capacity.

Let us focus on topology changes and node mobility. For example, consider a network of drones that are arranging into a random partition of collaborating coalitions. Applications like data-collection from the sink of a sensor network or monitoring an area do not require the drones fleet configuration to change. However, applications like forest surveillance and monitoring require that some drones move across the target area. Consequently, the distribution of some coalitions may change, making its members scattered or the inter-drone distance may increase, and then the recovery phases execution could not be energy-efficient anymore. In such case, they have to execute the proposed coalition formation process to be able to re-arrange themselves into a novel energy-efficient stable partition. When starting, they may use two different configurations:

• They act as a single grand coalition where it exists a cluster head that will start by the split investigation or

• They keep their current clustered partition where every cluster head iteratively applies the merge and split rules.

As small UAVs have limited computational capabilities [START_REF] Gupta | Survey of important issues in uav communication networks[END_REF], deciding how they can be arranged upon starting is crucial. In fact, the more there are drones per coalition, the higher is the number of split investigations and the higher the complexity of the algorithm is.

Simulation results

This section presents a comprehensive Matlab-based simulation of the proposed solution. Simulation results show the average cluster-completion time and the total Simulation results

55

consumed energy, with an energy coefficient α = 10 of M devices until recovering all N packets of the frame over several runs. The packet size is 8 bytes. In each run, all wireless nodes are randomly located in a square field of 150 × 150 m 2 and the node-to-node packet erasure probability is changed for each new run. All simulation parameters are listed in Table 1.

In particular, two applications are considered: a UAV network and a wireless sensor network, each of which is evaluated in a seperate part as follows.

In the first part, the performance of our proposed solution is compared against the two following IDNC-based schemes:

• 'Delay-aware and energy-unaware non-coalitional CDE' which considers a noncooperative game in a D2D configuration to select a single transmitting device among a number of players arranged in a single big cluster in order to reduce only the overall completion time [START_REF] Douik | A gametheoretic framework for network coding based device-to-device communications[END_REF].

• 'Delay and energy-aware non-coalitional CDE' which uses the same model of the previous scheme but with a modified utility function. In fact, in this scheme, our proposed utility function is considered to select the transmitting device in order to reduce both the overall completion time and the total consumed energy.

Note that the total consumed energy consists of the energy consumed when sending the recovery packets in addition to the consumed energy when exchanging feedback messages after every reception of a decoding packet throughout all the scenarios. All results are presented while increasing the packet erasure probability Q from the sender (the BS for example) to all wireless nodes during the initial phase. Moreover, we do the same analysis with respect to the number of devices while the packet erasure probability Q remains constant.

Moreover, a scenario of topology change is considered in a UAV network which is already partitioned, where a number of mobile drones move randomly from their localization. Thus, we analyse and compare the performance of both resulting partitions in the two following cases:

• when they start from the grand coalition,

• when they start from their current clustered partition. IDNC Obviously, in each run, for the same distribution of nodes, we measure the parameters of the two aformentioned resulting partitions using different state matrices and then average them over all runs. In particular, in such analysis, not only the consumed communication energy is considered but also the total computation energy consumed by cluster heads when running the proposed merge-and-split algorithm is also taken into account. Thus, we use the computation energy model introduced in [START_REF] Wang | Energy-efficient dsps for wireless sensor networks[END_REF]. Drones are powered by Intel Atom x7-Z8700 processor [START_REF]Intel Atom R Processor Z[END_REF]. Then, we calculated the number of instructions in our merge-and-split algorithm acccording to the intel Instruction

Set Reference [START_REF]Intel 64 and IA-32 Architectures Software Developer's Manual[END_REF].

In the second part, we assess our proposed scheme in a WSN where the sensors are randomly clustered at the beginning in order to guarantee low complexity processing of the coalition formation algorithm.

Application in a drone fleet network

In this section, we focus on a drone fleet that collects information from the sink of wireless sensor network. Since drones are of high mobility, we investigate the topology changes at the end of this section. Moreover, figure 4.5 illustrates the delay gain and energy-consumption gain per node when using our proposed cooperative scheme. It can be observed that gains on delay Simulation results

57

decrease as Q increases. This can be explained by the fact that when Q increases, the cardinality of the HAS set per drone decreases, and thus the probability that the union of the HAS sets of devices in a smaller coalition is equal to N is low. Hence, the inter-cluster recovery phase is always required for all the clusters which would slow down the recovery phase. Therefore, drones would have less incentive to cooperate. coalitions attempt simultanously to finish earlier their recovery phases compared to the one big coalition. On the other hand, exchanging recovery packets combinations and feedback matrices among a reduced number of drones is performed in a smaller range compared to the grand coalition.

All these figures demonstrate the significant advantage of using our clustered CDE scheme in terms of both delay and energy, which is increasing with the drone fleet size reaching up to 39.75% of improvement in energy consumption and 40% of improvement in completion time compared to the non-coalitional model of the Delay-aware and Energy-unaware non-coalitional CDE when M = 16 drones. The impact of the topology changes on the performance of CDE After an environmental change, the objective is to investigate the adequate starting partition that allows drones to converge to a novel partition where they can reduce not only the communication energy and delay but also the computation energy consumed when running the coalition formation process. In figure 4.9, we can clearly observe that at any size of the fleet, when drones process the coalition formation phase as a single grand coalition, they completely decode their missed packets faster than start-A Coalitional Game-theoretic Framework for Cooperative Data Exchange using IDNC ing with a random clustered structure. As we have detailed in section 5.1, this result is expected since the number of possible partitions that are examined by cluster heads throughout all the phase is significantly high. Hence, finding the lower completion time among all those possibilities is guaranteed. On the other hand, figure 4.10 depicts the total consumed energy taking into account the computation energy of both resulting partitions with respect to the number of drones. It is particularly interesting to observe that when the size of the fleet is less than 12 drones, starting as a single grand coalition allows drones in the resulting structure to further reduce their energy consumption. However, once exceeding 12 drones, starting with grand coalition is not the optimal choice anymore. In fact, it requires processing a very high number of split attempts, then processing a very high number of instructions that causes a substancial increase of the computation energy compared to the clustered starting partition as it is illustrated in figure 4.10. 4.12 illustrates that the benefit of using our cooperative scheme is increasing with the number of users. We can clearly observe that the gap between the total consumed energy of our proposed coalition formation algorithm and the total consumed energy of the initial partition is increasing as M increases, reaching up 33.55% of improvement of energy consumption when we have 60 cooperating sensors. In fact, the more we have sensors in the field, the more they have an incentive to create more clusters in order to exchange the recovery packets combination as well as the feedback matrices among a reduced number of sensors in a smaller range. In figure 4.11, we present an example of a simulated scenario consisting of M = 30 sensor nodes.

At the beginning, sensors are arranged into three large coalitions. Therefore, after the execution of our proposed algorithm, a final resulting ID hp -stable network partition is generated. As we can cleary see, it consists of ten disjoint smaller coalitions each of which is composed at least of two sensors. On the other hand, figure 4.13 illustrates the significant improvement of the completion time in the new structure reaching 29.8% when M = 60 sensors. In fact, the presence of more sensors in the field enhances the incentive to form more cooperating coalitions number attempting to finish earlier their recovery phase.

Conclusion

In this chapter, we have studied the problem of joint-minimization of completion time and energy consumption in the cooperative data exchange using the instantly decodable network coding across wireless nodes having a limited battery capacity.

We modeled the problem using cooperative game theory in partition form in which the players seek to form a disjoint coalitions that reduce both the completion time and energy consumption. To solve the game, we have proposed a distributed merge and split algorithm that is guaranteed to converge to a stable network. Moreover, we addressed the mobility issue through multi-UAVs network. Simulation results have shown that our proposed cooperative game theoretical framework, by considering an additional constraint that is the energy consumption, reduces both average completion A Coalitional Game-theoretic Framework for Cooperative Data Exchange using IDNC time and energy consumption for the resulting clustered network. Note also that using the coalitional game theoretic framework enhances the scalability of the system since Conclusion 65 each cluster head have to maintain a feedback matrix of the cluster's members instead of the global feedback matrix, like the non-cooperative model.

In the next chapter, we extend the network model to study the cooperation within large-scale energy-constrained networks. In such model, we consider that each player uses no longer his maximum transmission power, rather, he adjusts it dynamically.

To do so, we address the problem of multi-hop CDE through the two-stage game framework in order to extend the network coverage.

Introduction

MTC communications represent the next step evolution of our today communications where any device with computation capability can be seamlessly incorporated to the network. Indeed, these communications can involve large scale deployments.

However, energy efficiency is seen one of the major challenges hampering large-scale networks of resource-constrained devices. Therefore, there is a substantial need to design energy efficient MTC communications that can successfully scale to large number of MTC devices, without sacrificing the QoS.

In this chapter, we consider a large scale network and we focus on the CDE scenario using IDNC. Unlike the previous chapter that considers a fully connected network, this chapter deals with a partially connected network in which battery-powered devices cooperate with each other over limited transmission ranges. In fact, in the former network, each node can reach all members of its cluster over a single hop transmission, whatever the size of cluster is. All recovery transmissions and coalition formation operations are permitted without any range limitation constraint. However, the aim of this chapter is to provide a new multihop CDE-based IDNC approach for energy and delay reduction in which every node adjusts dynamically its transmission power.

Several works considered partially connected CDE-based IDNC network [START_REF] Douik | Delay reduction in multi-hop device-to-device communication using network coding[END_REF][START_REF] Douik | Delay reduction in multi-hop device-to-device communication using network coding[END_REF][START_REF] Karim | Network coding for video distortion reduction in device-to-device communications[END_REF][START_REF] Courtade | Coded cooperative data exchange in multihop networks[END_REF]). In [START_REF] Douik | Delay reduction in multi-hop device-to-device communication using network coding[END_REF], authors addressed the problem of reducing the decoding IDNC delay in a partially connected D2D network similar to the one studied in this chapter. To solve this problem, they considered the joint optimization issue of selecting the transmitting user and the packet combination. Using a graph-theoretic approach, they introduced the cooperation graph from which the optimal solution was derived. Afterward, in [START_REF] Douik | Delay reduction in multi-hop device-to-device communication using network coding[END_REF], the authors extended the study of [START_REF] Douik | Delay reduction in multi-hop device-to-device communication using network coding[END_REF] by extending the cooperation graph formulation. They introduced a clustering mechanism for nodes in order to generate non-interfering clusters. Specifically, this mechanism partitions only a fixed set of transmitting devices. There are many differences between this work and ours. First, we consider not only the decoding delay, but also the energy consumption in order to extend the network lifetime. Second, they considered that limited communication ranges are fixed for all nodes. However, we consider that communication ranges are dynamically adjusted to achieve an efficient coalition formation phase, in a distributed way. Furthermore, they suggested that the proposed solution is ensured In addition, we refer to the local state matrix as the state matrix of a particular cluster. Note that since it is reachable by all members, only the cluster head can construct the local state matrix.

Example 5.1. Let us consider the network illustrated in Figure 5.1 that represents our system model at the initial phase. We focus on cluster S 1 = {J 1 , J 2 , J 3 , J 4 , J 5 } consisting of 5 drones, where J 2 is selected as the cluster head. Each node is interested in receiving all the packets of the frame, and may have lost some of them. Consequently, J 2 constructs the following state matrix which will serve, in the next step, as a crucial basis to find the suitable coded packets: Devices in the same coalition may cooperate to recover their missing packets by exchanging binary XOR encoded packets. Since they are partially connected, not all drones within the coalition can overhear the sent feedbacks. As a result, we assume that every cluster head fulfill the following missions:

SM 1 =          0 0 1 1 1 0 0 0 1 1 0 0 0 0 1 1 1 1 1 0          After
• Determining the suitable packet combination,

• Selecting the suitable drone that will broadcast this recovering packet to all cluster members,

• Relaying the packet combination toward all the remaining cluster members if the selected drone connot reach all of them.

In our model, in order to select and combine the suitable packets, we use the packet selection technique that we have used in chapter 4. However, the N packets are not

• Instantly Decodable if it contains only one source packet from W j .

• Non-Instantly Decodable if it contains several source packets from W j .

• Non-innovative if all encoded packets are in H j .

Denote by t the time slot or the recovery stage when drones perform recovery transmissions and by t max the last stage in which all drones in the network obtain the required packets. We define the cluster-IDNC delays as follows: Definition 5.1. At any recovery transmission, in each cluster S k , a node j ∈ S k , with non-empty W j , implies one unit increase of decoding delay denoted d t j∈S k if it receives a non-innovative or non-instantly decodable packet. Thus, the overall clustered decoding delay D j∈S k is the summation of the decoding delays experienced by receiver j throughout both recovery phases, i.e. D j∈S k = tmax s=1 (d s j∈S k ).

Definition 5.2. For node j, the individual completion time C j∈S k is the required number of transmissions so that all its missing packets are recovered. Thus, the cluster-completion time C S k , is the total number of required transmissions by cluster S k so that all cluster members recover their packets i.e. C S k = max j∈S k C j .

Note that we use the following individual completion time expression derived from [START_REF] Douik | A gametheoretic framework for network coding based device-to-device communications[END_REF],

which takes into account the overall decoding delay, Wants set size, and packet erasure probability q j , that is the average packet erasure probability linking player j to all remaining players in the cluster.

C j∈S k = |w j | + D j∈S k -q j 1 -q j (5.2)
As we have already mentioned, in our multi-hop IDNC network, every drone has a battery with a residual energy of Es j , ∀j ∈ M. The simple energy model that we have used considers the inter-drone distance d, the free space f (d 2 power loss) or multi path fading m (d 4 power loss) [START_REF] Sengottaiyan | S-seech secured -scalable energy efficient clustering hierarchy protocol for wireless sensor network[END_REF]. Hence, the required energy for node j to send an L-bit packet including the electronic energy Eelec and the threshold distance d th is computed as follows:

L × Eelec + L × f d 2 if d ≤ d th L × Eelec + L × m d 4 if d > d th (5.3)

A coalition formation game in partition form for a multihop CDE

In this section, we model the multihop CDE as a coalition formation game in partition form with non-transferable utility taking into account energy efficiency and IDNC delay. Thus, we refer to cooperative game theory which provides a theoretical framework for designing distributed algorithms.

Given coalition S ∈ Π, we define the coalition value set (obtained by all the coalitions) at stage t ≥ 1 by:

φ(S, Π)(t) = {φ j (S, Π)(t) = -α * E c j (t) E s j (t -1) -T S , ∀j ∈ S} (5.4)
where

T S = C j (t) ∞ + D j (t) -D j (t -1) 1 ∀ j ∈ S and φ(S, Π) is a |S|-dimensional
real vector, whose element φ j (S, Π) represents a utility that player j can obtain within coalition S in partition Π.

As the energy efficiency and delay minimization are our main purposes, the utility of drone j ∈ S in (5.4) includes two parts: energy consumption and cooperative delay.

Both of them indicate the gains by forming the coalitions. The former is the expected energy efficiency

Ec j (t)

Es j (t-1) ∈ [0, 1] that captures the impact of the consumed energy when transmitting the recovery packet by drone j whether the transmission is direct or through the cluster head. Ec j (t) is the energy required to broadcast the recovering packet and Es j (t -1) is the stored energy of j in the previous stage. The latter is T S the cooperative delay taking into account the cluster completion time and the augmentation of the sum decoding delay between two successive stages. Additionally, in order to minimize both parameters in the same time, there is a need to weight the terms of the value function. Consequently, we multiply the energy consumption part by a coefficient α that tunes the weight of the energy consumption in the decisionmaking.

Proposition 5.1. The proposed clustered CDE is formulated as an (M, φ) coalitional game in partition form with NTU.

Proof. As expressed in (5.4), since the expected energy efficiency term is associated

The proposed coalition formation algorithm 75 to each player in the coalition after the packet recovery transmission, we can deduce that the defined game is with NTU. In other hand, if some packets aren't available in a cluster S, the cluster head CH i∈{1,••• ,|S|} cooperates with the other cluster heads CH j∈{1,••• ,|S|}\i to recover the remaining packets in the inter-cluster recovery phase.

Thus, the dependency of T S , then φ(S, Π), is not only on players inside S, but also on the distribution outside S. Consequently, from Definition 3, we conclude that the proposed coalitional game is in partition form with NTU.

The proposed coalition formation algorithm

In this section, we present how can wireless nodes cope with their limited transmission power in order to create a new optimal structure that jointly reduces the overall completion time and the network lifetime. In doing so, we develop a constrained merge and split algorithm whereby the nodes can achieve a stable architecture and meet the desired optimization.

Our algorithm is based on two simple rules of merge and split that modify a partition Π 1 of M. Note that in our CDE game, we use the Pareto order as a preference order to compare two coalitions of nodes. S 1 ∈ Π 1 , S 2 ∈ Π 2 , as follows:

(S 1 , Π 1 ) (S 2 , Π 2 ) ⇔ φ(S 1 , Π 1 ) ≥ φ(S 2 , Π 2 ) (5.5)
where at least one drone j ∈ S 1 , S 2 such that:

φ j (S 1 , Π 1 ) > φ j (S 2 , Π 2 )
where φ(S i , Π k ) is the payoff of the drones in coalition S 1 and φ(S Similarly, the decision of merging of two independent coalitions S i and S j is affected to both cluster heads CH i and CH j . Specifically, a coalition S i ∈ Π 2 can decide to merge with another coalition S j , forming a new partition Π 1 , as long as in the new structure, both cluster heads verify the two following conditions:

• Moreover, note that the cluster heads can test merge possibilities only with the coalitions that are in mutual transmission range. In the maximum transmission range scheme, all the merge and split operations and tests performed in coalition formation phase, may spread over the entire network. Thus, the more it spreads, the more energy consumption and the higher is the complexity to find a stable solution. However, following the above conditions, the number of split and merge tests decreases and thus the execution time of the coalition formation phase decreases. Hence, we obtain a lower complexity compared to the maximum transmission range model.

In the initial phase, all drones broadcast their feedback matrix to allow cluster heads performing their first split iteration. Subsequently, after verifying CM1 and CM2, every coalition head investigates its coverage zone looking for candidate coalitions for merging. All these candidates are chosen when merge process must improve both: delay and energy consumption of at least one player without hurting any individual payoff. After that, merge operation begins. We assume that any coalition head CH i can start the merge operation. The objective of the coalition head is to find a coalition that guarantees the lowest delay and energy consumption through an iterative application of the above rules. Hence, when no further merge nor split operations occurs, a new final partition is formed where nodes will perform their recovery phases.

A summary of our coalition formation algorithm is given in Algorithm 2. outperforms the maximum transmission range CDE in terms of total consumed energy without decreasing the IDNC completion time as shown in Figure 5.6. Also, this energy consumption gain increases as the erasure probablity increases reaching 62.49% of improvement (Q=0.5). The increasing improvement of total energy consumption illustrated in Figures 5.3 and 5.5 is explained by the fact that the exchanged recovery packets and feedback matrices (due to the increase of the frame size or the erasure probability) are performed over limited ranges compared to the maximum range CDE scheme. Although the partial connectivity of cluster heads and the conditions for the coalition formation limit considerably the number of merge and split investigations, drones achieve the same performance of the average completion time as the maximum transmission range scheme where all merge and split tests are allowed (figures 5.4 and 5.6). This result is due to the first stage of the proposed scheme that allows each node to switch to the suitable power that guarantees the maximization of their payoffs in terms of energy and delay. Of course, if the number of drones in the network increases, the average completion time for the limited range scheme will be higher than CDE with maximum transmission range, however, the consumed energy for this latter will be far higher since not only transmission energy will increase but also computing energy will increase exponentially due to the number of merge and

Conclusion

In this chapter, we considered the CDE using the IDNC in a large scale network. We studied the problem of minimizing completion time and energy consumption across wireless nodes having limited communication ranges. We modeled the problem using a two-stage game theoretical framework; the first stage is the non-cooperative game theory and the second stage is the cooperative game theory in partition form in order to maximize their battery lifetime without increasing the IDNC delay. Moreover, we proposed a merge and split algorithm that deals with limited range constraint. Simulation results have proved that our proposed scheme reduces significantly the energy

Conclusion and perspectives "

In recent years, there has been a growing interest among signal processing and communication communities in energy efficient research. Indeed, a large number of proposals for all communication layers have been proposed, but the system infrastructure has not been clearly defined. This dissertation strives to address the following research question: How to design suitable communication schemes that achieve the energy efficiency along with the QoS improvement across MTC devices? In this thesis, we were motivated by overcoming the need of reliable and energy efficient communications for today's applications in MTC networks. Therefore, we investigated IDNC-based CDE scheme under various applications requirements, considering different network dimensions.

In this manuscript, we presented thoroughly our main contributions in order to respond to the aforementioned question. In the next section of this final chapter, we summarize our contributions and we introduce our future research directions in Section 6.2.

Summary of contributions

Firstly, we have studied the CDE using IDNC in small fully connected networks taking into account the energy consumption constraint in addition to the IDNC delay. In fact, we have introduced a novel framework from coalitional game theory to model the cooperation in the IDNC game among nodes for energy efficient CDE. To solve the game, we have proposed a merge-and-split algorithm, which iteratively operates the coalition formation process in a distributed fashion, and we have shown that 86

Conclusion and perspectives

it converges to a stable coalition network structure. We have demonstrated that the proposed coalitional game theoretical framework is of low complexity compared to the non-coalitional model, especially for high number of nodes. This solution, also enhances the scalability of the system since each cluster head has to maintain a feedback matrix of the cluster's members instead of the global feedback matrix, such as the non-cooperative model. Moreover, we have addressed the mobility issue through multi-UAVs network. We have evaluated the proposed framework using two practical scenarios: a wireless sensor network and a network of flying fleet of drones. Simulation results have proved that our proposed cooperative game theoretical framework, by considering an additional constraint that is the energy consumption, reduces both average completion time and energy consumption.

Thereafter, we have considered the energy and delay aware IDNC based CDE problem in large scale networks in which the wireless nodes have limited communication ranges. We have considered that each node adjusts dynamically its transmission power in a decentralized manner. In fact, we have modeled the problem using a twostage game theoretical framework; the first stage is the non-cooperative game theory and the second stage is the cooperative game theory in partition form in order to maximize their battery lifetime without increasing the IDNC delay. We have proposed a coalition formation game that forms an appropriate multihop coalitions. In doing so, we have proposed a merge and split algorithm that deals with limited range constraint. Furthermore, we have analyzed the stability of the cooperative game, and demonstrated that the algorithm converges to a stable coalition structure, where all the players do not have incentives to change the coalition they are part of. Indeed, the defined framework is of low interference and complexity compared to the maximum We are currently working on extending our contribution introduced in Chapter 5.

Specifically, we are focusing on the first stage of the two-stage game that consists in finding the appropriate transmission powers profile for the wireless nodes in a decentralized way. In fact, this stage relies on the existence of a mixed strategy equilibrium for convergence. However, in this study, we aim to use the reinforcement learning to deal with denser deployments. For that purpose, we are focusing on online learning, more exactly, the Multi-Player Multi-Armed Bandit (MP-MAB) [START_REF] Maghsudi | Channel selection for network-assisted d2d communication via no-regret bandit learning with calibrated forecasting[END_REF].

Indeed, The MP-MAB framework permits to reduce the complexity of distributed problems in wireless environments, since detailed information about the network are learned by players instead of being considered or processed in advance [START_REF] Wilhelmi | Collaborative spatial reuse in wireless networks via selfish multi-armed bandits[END_REF].

Generally, the MP-MAB game represents a class of problems of squential decision making with limited information. At each test t, any player k ∈ {1 . . . M } pulls some arm (action) a ∈ {1 . . . A}. Upon being chosen, the selected action generates some reward which depends not only on the player action but also on the joint actions of the remaining players in the network.

Therefore, for a large and dense network, we model the IDNC based CDE problem as a two-stage game: the first game is MP-MAB game whereby the players learn to select the best transmission power in order to form the suitable coalitions through the second game which is the coalitional formation game. In this model, all players tend to update (through repeated coalition formation trials) their beliefs about the impact of changing their transmission powers on the coalitional payoffs, in order to achieve the most suitable coalitional structure. To do so, we propose a distributed learning algorithm of the -greedy policy, dealing with exploration-exploitation strategy from the MP-MAB game.

Security aware CDE-based IDNC scheme

Security in network coding is an important issue and it is more challenging for cooperative data exchange setting. Actually, network coding has shown its benefits for network robustness by allowing the nodes in a network to mix different packets through various algebraic combinations [START_REF] Agha | Network Coding[END_REF]. Even though all exchanged packets in Proof of Corollary 2 erating cluster head) which is non-innovative or non instantly decodable in the second phase. Therefore, there is no relayed decoded packet for its cluster members.

Consequently, the number of required recovery transmission C k until device k belonging to cluster S i receives all its wanted packets can be expressed as follows:

C k∈S i = |W k (0)| + D C k k + F k (C k -1) (C.1)
Since the C k -th transmission is the last successfull transmission that allows node k to complete the reception of lost packets, F k (C k -1) = F k (C k ), therefore:

C k∈S i = |W k (0)| + D C k k + F k (C k ) (C.2)
Let Y k (t) be a bernoulli random variable that is equal to 0 if the packet is successfully received at time t and 1 if it is erased:

P(Y k (t) = y) = q k if y = 1 1 -q k if y = 0 (C.3)
Let J (t) be a random variable taking the chosen sender index k within the cluster S i . The probability of packet erasure at device k in the transmission t is calculated as:

P(Y k (t) = 1) = k ∈S i P(Y k (t) = 1|J (t) = k )P(J (t) = k ) (C.4)
Note that if the sender is itself the receiver ie. k = k, the coded packet cannot be erased, thus P(Y k (t) = 1|J (t) = k) = 0 otherwise (if k = k ) and according to the system model, the erasure probability between two nodes k and k is equal to:

P(Y k (t) = 1|J (t) = k ) = q k k (C.5)
On the other hand, since all devices start with the same residual energy supply, all devices have the same chance to be selected as a sender in its cluster. Hence:

P(J (t) = k ) = 1 |S i | , ∀k ∈ S i (C.6)
Replacing C.5 and C.6 in C.4, the probability that the coded packet is erased at device k is expressed as follows:

P(Y k (t) = 1) = 1 |S i | k =k∈S i q k k = |S i | -1 |S i | qk (C.7)
where qk = 1

|S i |-1
k =k∈S i q k k is the average packet erasure probability of device k in the cluster S i . Hence, the cumulative number of erased packets at device k until t = C k -1 is the sum of C k -1 bernoulli variable as follows:

F k (C k -1) = C k -1 t=1 Y k (t) (C.8)
For a large number of packets, the individual completion time C k would be automatically large. Using the law of numbers, F k (C k -1) is approximated as follows:

F k (C k -1) = (C k -1) |S i | -1 |S i | qk (C.9)
After substituting C.9 into the completion time expression C.1, the individual completion time for device k can be finally calculated as follows:

C k∈S i = |W k (0)| + D k∈S i -|S i |-1 |S i | qk 1 -|S i |-1 |S i | qk (C.10)

xi 3 . 1 35 A 40 xiiof contents xiii 4 . 3 1 . 1 8 2. 1 16 2. 2 57 4. 4 58 4. 5 59 4. 7 60 4. 8 60 4. 9 63 xviof Figures xvii 4 .

 313540431181162574585597608609634 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.2 Introduction to network coding . . . . . . . . . . . . . . . . . . . . . . 26 3.3 The instantly decodable Network codes . . . . . . . . . . . . . . . . . 27 3.4 QOS aware Instantly Decodable Network Coding . . . . . . . . . . . . 29 3.5 Joint QoS and energy aware Instantly Decodable Network Coding . . 31 3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 II A distributed Framework for Cooperative Data Exchange using IDNC Coalitional Game-theoretic Framework for Cooperative Data Exchange using IDNC 37 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 4.2 System model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Table Recovery protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.2 IDNC packet construction and graph overview . . . . . . . . . 4.4 Coalitional game in partition form for IDNC-based CDE network . . . 4.5 Proposed coalition formation algorithm . . . . . . . . . . . . . . . . . 4.5.1 The merge and split coalition formation process . . . . . . . . . 4.5.2 Complexity analysis . . . . . . . . . . . . . . . . . . . . . . . . 4.5.3 Mobile cooperative UAV network: a case study . . . . . . . . . 4.6 Simulation results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.6.1 Application in a drone fleet network . . . . . . . . . . . . . . . 4.6.2 Application in a wireless sensor network . . . . . . . . . . . . . 4.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Delay and Energy aware Instantly Decodable Network Coding for multi-hop Cooperative Data Exchange 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 System model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 A coalition formation game in partition form for a multihop CDE . . . 5.4 The proposed coalition formation algorithm . . . . . . . . . . . . . . . 5.5 Power control game formulation . . . . . . . . . . . . . . . . . . . . . . 5.6 Simulation results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 Conclusion and perspectives 6.1 Summary of contributions . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2.1 Dense CDE-based IDNC network . . . . . . . . . . . . . . . . . 6.2.2 Security aware CDE-based IDNC scheme . . . . . . . . . . . . 6.2.3 Ultra-dense CDE-based IDNC network . . . . . . . . . . . . . . Four use cases of our framework . . . . . . . . . . . . . . . . . . . . . Example of a coalitional game in a UAV network. The focus is on the utility of coalition S 1 when S 3 and S 4 are disjoint and when they are combined into S 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Merge and split algorithm main stages . . . . . . . . . . . . . . . . . . 20 3.1 A basic network coding example . . . . . . . . . . . . . . . . . . . . . 27 4.1 Representation of the IDNC-based CDE system model . . . . . . . . . 41 4.2 An example of a schedule in an IDNC-based clustered CDE network . 444.3 Average cluster-completion time of the resulting clustered network versus the two non-coalitional models with respect to packet erasure probability Q. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Total energy consumption in the resulting clustered network versus the two non-coalitional models with respect to packet erasure probability Q. Average gains per node achieved by the resulting clustered network with respect to packet erasure probability Q . . . . . . . . . . . . . . . 58 4.6 Total energy consumption of the drones in the resulting clustered network versus the two non-coalitional models with respect to drone fleet size. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Average cluster-completion time achieved by the resulting clustered network versus the two non-coalitional models with respect to drone fleet size. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Average gains per node achieved by the resulting clustered network with respect to drone fleet size . . . . . . . . . . . . . . . . . . . . . . Average cluster-completion time achieved by the resulting clustered network in case of topology changes . . . . . . . . . . . . . . . . . . . 61 4.10 Total energy consumption taking into account the computational energy achieved by the resulting clustered network in case of topology changes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 4.11 Convergence of the algorithm to a final ID hp -stable partition. . . . . . List 12 Total energy consumption of the sensors in the resulting clustered network versus the starting partition with respect to the number of sensors. 4.13 Average cluster-completion time achieved by the resulting clustered network versus the starting partition with respect to the number of sensors. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1 An example of a multihop UAV network enabling the proposed cooperative IDNC scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Representation of the proposed two-stage IDNC game . . . . . . . . . 5.3 Total energy consumption in the resulting multihop clustered network versus one-hop clustered network with respect to number of packets. . 5.4 Average cluster-completion time in the resulting multihop clustered network versus one-hop clustered network with respect to number of packets. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.5 Total energy consumption in the resulting multihop clustered network versus one-hop clustered network with respect to erasure probability. . 5.6 Average cluster-completion time in the resulting multihop clustered network versus one-hop clustered network with respect to erasure probability. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Figure 1 . 1 :

 11 Figure 1.1: Four use cases of our framework: a) A drone fleet collecting information from the sink of a WSN, b) A WSN deployed in a hostile environment, c) A roadside base station broadcasting data to moving vehicles, d) A distributed surveillance camera network

Figure 2 . 1 :

 21 Figure 2.1: Example of a coalitional game in a UAV network. The focus is on the utility of coalition S 1 when S 3 and S 4 are disjoint and when they are combined into S 5 .

Fundamentals of game theory payoffs received by

  the players. A is preferred over B by Pareto order if a ≥ b with at least one element a i of a, such that a i > b i , where a and b are the payoff vectors of A and B.

Figure 2 . 2 :

 22 Figure 2.2: Merge and split algorithm main stages

  Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3. 2

 2 Introduction to network coding . . . . . . . . . . . . . . . . . . . 3.3 The instantly decodable Network codes . . . . . . . . . . . . . . 3.4 QOS aware Instantly Decodable Network Coding . . . . . . . . 3.5 Joint QoS and energy aware Instantly Decodable Network Coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25

 25

Figure 3 . 1 :

 31 Figure 3.1: A basic network coding example

Figure 4 . 1 :

 41 Figure 4.1: Representation of the IDNC-based CDE system model. Each node is interested in receiving a frame of packets, and firstly losts some of them. The lost packets are crossed by an X mark. Afterwards, nodes arrange themselves into a new partition P = {S 1 , S 2 } according to the proposed cooperative scheme. Each cooperates with the appropriate cluster members until all of them recover all requested packets.

Example 4 . 1 .

 41 Let us consider an example of a schedule of a clustered IDNC-network, illustrated in figure 4.2, where 6 devices are arranged into two clusters each of which

Figure 4 . 2 :

 42 Figure 4.2: An example of a schedule in a network composed of 6 devices arranged into two clusters S 1 and S 2where the clustered-CDE using IDNC is enabled; in the first time-slot k1 and k5 transmit at the same time, each of which in its cluster. The intra-cluster recovery phase of S 2 is blocked at t = 2 since packet 3 is unavailable. Members of S 1 finish recovering their missing packets after the second transmission. At t = 3, the inter-cluster recovery phase begins involving only cluster-heads k1 and k4.

  exists a second recovery phase in which CH construct G * 4.4 Coalitional game in partition form for IDNC-based CDE network Our main goal is to provide a distributed framework that can model the collaborations among the wireless nodes of an IDNC-based CDE network. To this end, we use the analytical framework of Cooperative Game Theory which involves a set of players that interact with each other to form a partition. Particularly, in the present section, we model the CDE as a coalition formation game in partition form with non-transferable utility mainly accounting for the energy efficiency and the completion time. Definition 4.4. A coalitional game in partition form with non-transferable utility (NTU) is defined by a pair (M, ψ), where M is the set of players and ψ is a mapping such that for every partition Π, and coalition S ⊆ M, S ∈ Π, ψ(S, Π) is a subset of IR |S| representing the payoff vectors that players in S can receive when cooperating (|S| is the number of players in coalition S).

Proposition 4 . 1 .

 41 The proposed clustered IDNC-based CDE is formulated as an (M, ψ) coalitional game in partition form with non-transferable utility.

  the cluster size. It is equal to O(|S k |N ) where |S k | is the size of a cluster S k and N is the number of packets. The reason is that each vertex can be only connected to vertices in the same local graph G k which is composed of at most |S k |N vertices.

Figures 4 .

 4 3 and 4.4 depict respectively the average completion time per cluster and the consumed energy by all drones in the network depending on the erasure probability Q for a scenario where M = 10 drones and N = 20 packets. From the aformentioned figures, it can be observed that the proposed cooperative framework provides a significant completion time and energy consumption reduction as compared to the two other non-coalitional schemes.

Furthermore, energy gains shown in figure 4 . 5

 45 increase until Q = 0.4 and despite a very high packet erasure probability, the proposed coalition formation algorithm yields a performance improvement on energy consumption of 31.38% (Q = 0.6) against the Delay-aware and Energy-unaware non-coalitional CDE. and Energy-unaware non-coalitional CDE Delay and Energy-aware non-coalitional CDE Delay and Energy-aware coalitional CDE

Figure 4 . 3 :

 43 Figure 4.3: Average cluster-completion time of the resulting clustered network versus the two non-coalitional models with respect to packet erasure probability Q.

Figures 4 .

 4 Figures 4.6 and 4.7 illustrate respectively the total energy consumption in the network and the average completion time per cluster as a function of the drone fleet size, for a scenario of Q = 0.2, N = 20 packets. It can be observed that the proposed scheme outperforms the Delay-aware and Energy-unaware non-coalitional CDE in terms of both: completion time and energy consumption. From figure 4.8, we notice that the benefit of cooperation in terms of energy and delay increases with the number of drones. In other words, the presence of more drones in the field enhances the incentive of cooperation. This is mainly due to two reasons: On one hand, small

Figure 4 . 4 :

 44 Figure 4.4: Total energy consumption in the resulting clustered network versus the two non-coalitional models with respect to packet erasure probability Q.

  on delay % non-coalitional model1 Gain on delay % non-coalitional model2 Gain on energy % non-coalitional model1 Gain on energy % non-coalitional model2

Figure 4 . 5 :

 45 Figure 4.5: Average gains per node achieved by the resulting clustered network with respect to packet erasure probability Q. The non-coalitional model 1 is delayaware and energy-unaware non-coalitional CDE and the non-coalitional model 2 is delay-aware and energy-aware non-coalitional CDE.

  and Energy-unaware non-coalitional CDE Delay and Energy-aware non-coalitional CDE Delay and Energy-aware coalitional CDE

Figure 4 . 6 :

 46 Figure 4.6: Total energy consumption of the drones in the resulting clustered network versus the two non-coalitional models with respect to drone fleet size.

  and Energy-unaware non-coalitional CDE Delay and Energy-aware non-coalitional CDE Delay and Energy-aware coalitional CDE

Figure 4 . 7 :

 47 Figure 4.7: Average cluster-completion time achieved by the resulting clustered network versus the two non-coalitional models with respect to drone fleet size.

  on delay % non-coalitional model1 Gain on delay % non-coalitional model2 Gain on energy % non-coalitional model1 Gain on energy % non-coalitional model2

Figure 4 . 8 :

 48 Figure 4.8: Average gains per node achieved by the resulting clustered network with respect to drone fleet size. The non-coalitional model 1 is delay-aware and energy-unaware non-coalitional CDE and the non-coalitional model 2 is delayaware and energy aware non-coalitional CDE.

  CDE when strating from the grand coalition CDE when starting from a random clustered network

Figure 4 . 9 :

 49 Figure 4.9: Average cluster-completion time achieved by the resulting clustered network when starting from the grand coalition versus the resulting clustered network when starting from a random clustered partition with respect to drone fleet size.

62 A

 62 Coalitional Game-theoretic Framework for Cooperative Data Exchange using IDNC

Figure 4 . 10 :

 410 Figure 4.10: Total energy consumption taking into account the computational energy achieved by the resulting clustered network when starting by the grand coalition versus the resulting clustered network when starting by a random clustered partition with respect to drone fleet size

  and 4.13 depict respectively the total energy consumption in the network and the average completion time per cluster as the number of sensors increases, for a scenario of N = 20 when the packet erasure probability Q = 0.2.

Figure

  Figure 4.12 illustrates that the benefit of using our cooperative scheme is increasing

Figure 4 . 11 :

 411 Figure 4.11: Convergence of the algorithm to a final ID hp -stable partition.

  new formed clustered network CDE in the starting network

Figure 4 . 12 :

 412 Figure 4.12: Total energy consumption of the sensors in the resulting clustered network versus the starting partition with respect to the number of sensors.

  new formed clustered network CDE in the starting network

Figure 4 . 13 :

 413 Figure 4.13: Average cluster-completion time achieved by the resulting clustered network versus the starting partition with respect to the number of sensors.

  the initial transmission, under the control of cluster heads, nodes organize themselves to form a coalitional partition Π of collaborating nodes. A partition Π is defined as a set {S 1 , • • • , S k } of k mutually disjoint clusters of drones such that k i=1 S i = M, with k cluster heads CH, denoted by {CH 1 , • • • , CH k }. Subsequently, once a new partition is formed, nodes start the IDNC intra-cluster recovery phase.

  CM1): At least one drone in the resulting coalition can improve its individual payoff without decreasing the payoff of all the other players • (CM2): Each cluster head should be in mutual coverage with all the other cluster members.

Figure 5 . 3 :

 53 Figure 5.3: Total energy consumption in the resulting multihop clustered network versus one-hop clustered network with respect to number of packets.

  Delay and Energy aware Instantly Decodable Network Coding for multi-hopCooperative

Figure 5 . 4 :

 54 Figure 5.4: Average cluster-completion time in the resulting multihop clustered network versus one-hop clustered network with respect to number of packets.

  consumption without hurting the average completion time achieved by the resulting clustered network with limited transmission range versus the resulting clustered network with maximum transmission range. Transmission Range CDE with maximum Transmission Range

Figure 5 . 5 :

 55 Figure 5.5: Total energy consumption in the resulting multihop clustered network versus one-hop clustered network with respect to erasure probability.

Figure 5 . 6 :

 56 Figure 5.6: Average cluster-completion time in the resulting multihop clustered network versus one-hop clustered network with respect to erasure probability.

  transmission range model. Simulation results have shown that our proposed scheme reduces significantly the energy consumption without hurting the average completion time achieved by the resulting clustered network with limited transmission range versus the resulting clustered network with maximum transmission range. CDE-based IDNC network

Table 4 .

 4

	1: Simulation Parameters
	Parameter	Value
	Area	150 × 150 m 2
	f	10 pJ/bit/m 2
	m	0.0013 pJ/bit/m 4
	Eelec	50 nJ/bit
	d th	25 m
	α	10
	Packet size	64 bits

  2 , Π 2 ) is the payoff of the drones in coalition S 2 . Recall that we use this order because it is the most suitable for NTU games. Since only the cluster head CH i is always in mutual coverage with all coalition members, he makes the decision of split. Therefore, a coalition of nodes S i ∈ Π 1 can be split, forming a new partition Π 2 as long as in the new structure, CH i guarantees twoDelay and Energy aware Instantly Decodable Network Coding for multi-hopCooperative Data Exchange• (CS2): In each resulting cluster, it exists at least one drone is in mutual coverage with all the new cluster members.

conditions:

• (CS1): At least one drone can enhance strictly its utility without hurting the payoffs of all the remaining nodes

Note that

M represents the set of all possible subsets of M .

Acknowledgments " First and foremost, I thank ALLAH subhanahu-wa-taala for giving me opportunity, guidance, motivation and ability to undertake this thesis. Without His mercies, this work would not have been possible.

I would like to express my deepest thanks and gratitude to my supervisor Oussama

Habachi for having faith in me and for the tremendous support, personnally and professionally. His useful suggestions and fruitful ideas have helped me a lot to improve

A Coalitional Game-theoretic Framework for Cooperative Data Exchange using IDNC Algorithm 1: Coalition formation algorithm for CDE

A-Initial phase

We start with a random partition Π 1 of M denoted by {S 1 , S 2 • • • , S m }. B-Split and merge phase repeat a) Based on pareto order in (5.5), CH check the split action:

We obtain a novel partition Π 2 = {S 1 , ..., S p } b) for all CH i , i ∈ {1, • • • , p} do

2. CH i looks for coalition candidates j for performing merge process and add them to its TO MERGE list, each of which with its corresponding gain G {i,j} :

while T O M ERGE LIST i is non-empty do j * = argmax j∈Π2\{i} {G {i,j} } 1. CH i sends REQ TO JOIN to CH j * ;

end while end for until no successive merge and split operations occurs. C-Cooperative data exchange recovery phase All formed clusters in the final formed partition perform their intra-cluster recovery phases simultaneously and the inter-cluster recovery phase if necessary as described in Section 4.2.

Complexity analysis

The merge-and-split algorithm has a complexity far lower than the coalition formation problem in optimal manner which is NP-hard [START_REF] Saad | Coalitional game theory for communication networks[END_REF]- [START_REF] Militano | A constrained coalition formation game for multihop d2d content uploading[END_REF]. In fact, to find the optimal solution of the coalition formation problem, we have to check all the possible partitions, which is equal to the M -th Bell number B M , in order to find the optimal partition of a set of M players. Note that the Bell number is obtained by the recursion Differently, authors of [START_REF] Karim | Network coding for video distortion reduction in device-to-device communications[END_REF] addressed the problem of reducing the average video distortion to deal with real-time distribution of a video sequence to a set of cooperative devices that are partially connected. They started by updating the IDNC scheme to fit the considered video application features. Then, they formulated the problem using finite horizon Markov decision process (MDP). Since finding the optimal solution is intractable, they developed a two-stage algorithm to solve the problem.

It is woth noting that there is no work, to the best of our knowledge, that aims at optimizing both IDNC delays and energy consumption in CDE-enabled systems over limited transmission ranges, which represents a more realistic scenario.

Interestingly, we consider no longer a fixed transmission range for every node. An optimal profile of transmission powers is rather determined, in a decentralized manner, taking into account the delay and the energy efficiency. Furthermore, a new coalition formation algorithm is defined, in order to form clusters executing the multihop energy efficient IDNC-based CDE. In doing so, we establish a two-stage game using two theoretical games concepts; the first is a non-cooperative game theory for choosing the suitable transmission powers, and the second is a cooperative game theory in partition form for modeling the multihop CDE between wireless nodes. Hence, our main contributions in this chapter are summurized as follows:

• We consider that each node adjusts dynamically its transmission power in a decentralized fashion.

• We propose a muti-hop coalition formation game that constructs a suitable multihop coalitions. Indeed, the defined framework is of low complexity and interference compared to the maximum transmission range model.

• We analyze the stability of the cooperative game, and demonstrate that the algorithm converges to a stable coalition structure, where all the players do not have incentives to change the coalition they are part of.

• Our simulation results show that we are able to improve the energy consumption without hurting the IDNC delay compared to the maximum range cooperative model.

Delay and Energy aware Instantly Decodable Network Coding for multi-hop Cooperative Data Exchange

In the following, we start by describing the system model as well as the recovery process under the limited transmission range constraint in Section 5.2. Afterwards, we illustrate our game theoretical approach using cooperative game in Section 5.3.

Section 5.4 proposes the coalition formation process using merge and split algorithm.

Then, we formalise the power control game taking into account energy and delay constraints in Section 5.5. The evaluation of the two-stage game theoretical approach is depicted in Section 5.6.

System model

In this chapter, we consider the same scenario investigated in chapter 4, in a large scale setting, where the BS tends to deliver a frame

The source sender can be a wireless base station as it can be a simple drone. This drone fleet can be arranged in a number of clusters or in one big cluster. Let S k be a cluster consisting of |S k | -1 members and a cluster head CH k . All the drones are interested in receiving all the N source packets. However, node j may miss a packet from the node i with a probability q i,j .

In this model, the BPSK modulation, introduced in chapter 4, is supposed to be used in the physical layer transmission. Moreover, not all the drones can reach each other due to their limited communication ranges. In fact, only those that are in mutual coverage can establish direct links. Hence, in a coalition, we assume that only the cluster head is necessarily in mutual coverage with all cluster members. Moreover, we assume that each drone j has a battery with a residual energy of Es j , j ∈ M.

At the beginning, the BS transmits the N uncoded packets. We assume that every packet is successfully received by at least one drone. Then, each drone j has two feedback sets:

• The Wants set (W j ): missing packets for drone j.

• The Has set (H j ): packets successfully received by j.

Given the feedback sets of all nodes, we define the state matrix S(t) = [s j,i (t)], j ∈ M, i ∈ N as follows:

Delay and Energy aware Instantly Decodable Network Coding for multi-hop Cooperative Data Exchange necessarily available in a given cluster and then the cluster is not able to recover all the packets. Thus, some packets may be still missing after the intra-cluster recovery.

Consequently, the drones retrieve a number of their requested packets as possible as they can in the cluster, and wait for the other clusters finishing their intra-cluster recovery phases. Then, the IDNC inter-cluster recovery phase begins. Only cluster heads CH perform this phase. In fact, since it remains a few uncoded packets, they cooperate with each other using their maximum transmission powers in order to recover the remaining missing packets. Note that the selection of the coalition heads is beyond the scope of this work. We consider that the node that has mutual coverage with all the cluster members and also has more residual energy is elected as a coalition head. Moreover, during the inter-cluster recovery phase, we assume that once a cluster head is able to recover a missing packet, it broadcasts it immediately to its cluster members. All the received packets can be one of the following: Proof. Note that every iteration, i.e. a merge or split, produces a new partition.

Hence, starting from the initial partition Π init , we obtain the following sequence of partitions:

where Π i+1 Π i , and the operator → indicates a merge or split operation. Since the

Delay and Energy aware Instantly Decodable Network Coding for multi-hop Cooperative Data Exchange

Pareto order introduced in (5.5) is irreflexive, transitive and monotonic, a partition cannot be revisited. Given that the number of different partitions of a finite set is finite, the sequence (5.6) will finish after a finite number of iterations and the algorithm converges to Π f . Theorem 5.2. Every network partition resulting from the proposed split and merge algorithm is ID hp stable.

Proof. Let us focus on the final partition resulting from Algorithm 2. From Theorem 5.1, we have that coalitions belonging to this partition have no interest to perform further merge and split operations. Consequently, from the definition of the ID hp stablity concept, we deduce that the final resulting partition is ID hp stable.

Power control game formulation

In the previous section, merge and split decision making throughout the coalition formation phase depends closely on the transmission range of each node. In other words, varying the transmission power may significantly impact the performance of the final structure. For example, one node may choose a large transmission range that can generate uselessly more merge and split investigations. On the other hand, he may use a very short transmission range that prevents him from joining useful coalitions and therefore reducing his energy consumption and completion time as well.

To that end, nodes cannot expect the optimal range to meet such goals, but rather, they can play a power game that allows them to switch to the suitable power that guarantees the maximization of their payoffs in terms of energy and delay. Indeed, in the present section, we establish such non-cooperative power control game. The key idea is to determine what is the well-suited transmission power for each node to perform the best possible coalition formation game that maximizes its battery lifetime and reduce its completion delay. • Payoffs. The payoff for a drone j is the utility gained from using the power transmission p j ∈ IP throughout all phases of the new scheme. It is given as follows:

where the quotient Ec j

Es j represents how much the drone j consumes energy Ec j compared to his starting residual energy Es j when using the transmission power p i . T S and α represent respectively the cooperative delay and the tuning parameter already defined in Section 3. The similarity of the utility function of the non-cooperative game with the value function (5.4) of the cooperative game guarantees the non-deviation of the system from the main purpose of this chapter. Thus, in this non-cooperative game stage, every player aims to choose the transmission power that maximizes his utility as given in (5.7). The stable strategy profile (list of players strategies) with

Delay and Energy aware Instantly Decodable Network Coding for multi-hop

Cooperative Data Exchange the property that no player can increase his payoff by changing his action given other players' actions is defined by the notion of Nash Equilibrium [START_REF] Nash | Equilibrium points in n-person games[END_REF].

Theorem 5.3. A mixed-strategy Nash equilibrium always exists for the proposed non-cooperative game.

Proof. In the proposed game, there is a finite number of players and strategies. Since every finite non-cooperative game in strategic form has a mixed strategy Nash equilibrium [START_REF] Nash | Equilibrium points in n-person games[END_REF], there exists at least one Nash equilibrium for the proposed non-cooperative game.

Simulation results

In this section, we assess the performance of the proposed scheme to efficiently reduce total consumed energy and the average cluster completion time. We compare both metrics of M=8 drones applying the multihop clustered CDE scheme in which each drone uses his optimal transmission power resulting from the non-cooperative game against the clustered CDE system over maximum transmission range introduced in [START_REF] Zayene | Joint delay and energy minimization for instantly decodable network coding[END_REF]. In every iteration, the drones are randomly distributed in a square field of 100 × 100 m 2 . The total consumed energy per network and the average cluster-completion delay are measured by frame, then the average over all iterations is presented. First, we illustrate the aforementioned comparison while increasing the frame size N when the packet erasure probability (between the BS and drones) Q = 0.2. Second, we do the same analysis versus Q while N = 20.

Conclusion and perspectives

CDE are coded, the network is still vulnerable to misuse and attack. For instance, a wiretapper located in the proximity of the nodes that exchange information may intercept some transmitted packets and obtain information about main messages.

Another scenario that may occur when an intermediate attacker modifies arbitrarily a transmitted packet to achieve a certain confusion at the attacked destination.

Furthermore, he may inject corrupted packets that may easily corrupt the whole information flow. Recently, several studies have addressed these problems in order to secure the data against the attackers in the network coding based CDE scheme [START_REF] Sprintson | Cooperative data exchange in broadcast networks[END_REF].

We are currently working on that issue by analysing the robustness of our proposed IDNC-based CDE scheme against the wiretappers.

Ultra-dense CDE-based IDNC network

In ultra-dense cooperative IDNC network, we are going beyond the coalitional game theory for energy and delay aware network formation. Indeed, in our future works, we tackle the problem of delay and energy aware clustering for the CDE-based IDNC network involving an enormous finite number of MTC devices. Specifically, the problem can be modeled using the evolutionary coalitional game (EC). The idea of EC deals with the evolution of coalitions over time, given several factors that may occur such as mobility, depletion of battery life of some devices and joining of some others, etc. Note that this game class needs less exchanged overhead among players. To solve this game, a full distributed clustering algorithm should be proposed in order to find an evolutionary stable coalitional structure.

Appendix A

Publications of the thesis 1. All packets are available in S i ⇔ | m j=1∈S i H j | = N . In that case, nodes in S i do not need to wait for the inter-cluster phase to receive their remaining wanted packets. Note that node k completes receiving all its erased packets in the C k -th transmission. Therefore, according to definition 4.3, the overall decoding delay experienced by k is simply expressed as follows:

2. Not all packets are available in S i ⇔ | m j=1∈S i H j | < N In that case, the overall decoding delay of node k can be divided into three terms D 1 , D 2 and D 3 , each of which expresses the effect of an occuring event on the decoding delay as follows:

• D 1 is the accumulative decoding delay experienced by k during the intracluster recovery phase until all cluster members still miss only the unavailable packets (at t = t S i max ), ie. ∀j ∈ S i , W j = W j∈S i \{j} . Therefore,

• After completing the first recovery phase at t = t S i max , nodes in S i should wait other clusters in the network completing their intra-cluster recovery processes. Since there is no decoding packets, the decoding delay of each device is increased by D 2 units. Therefore, D 2 = (t

where S j is the last finishing cluster. Note by t * the first recovery stage of the second phase, then D 2 = t * -t S i max -1.

• D 3 is the decoding delay experienced by the cluster head CH i in the intercluster recovery phase. In fact, if the received packet is instantly decodable, it will be forwarded by CH i to its cluster members, otherwise, no packet is forwarded. Therefore, in that case, the decoding delay of device k is the same as the cluster head:

Appendix C

Proof of Corollary 2

Let us first examine all possible packet transmissions closely among cluster members that may affect the individual completion time throughout both recovery phases. Let F k (t) be the total number of erased coded packets at receiver k until time slot t. Note that a device k receives its last instantly decodable packet at time t = C k . Thus, until t = C k -1, one of the following cases may happen:

• The coded packet is erased, thus F k (t) = F k (t -1) + 1.

• The coded packet is successfully received. Two cases are possible:

-The combination of packets is instantly decodable for device k so it needs |W k (0)| -1 such coded packets to recover all the remaining missing ones.

-The combination of packets is non-innovative or not instantly decodable for device k. Thus, its accumulative decoding delay D t k∈S i at t <= C k -1 increases by one unit.

• No coded packet is received. One of the two following reasons can be considered for this case:

-The non-availability of a number of packets at any member of the cluster S i of device k. In that case, the decoding delay of k is increasing by one unit at every stage until the beginning of the inter-cluster recovery phase when all remaining clusters finish their intra-cluster recovery exchanges as detailed in Corollary 1.

-The reception of the cluster head of a coded packet (from another coop-