{'fraction_non_alphanumeric': 0.03362305580969808, 'fraction_numerical': 0.013437785910338517, 'mean_word_length': 4.484164314832236, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Game Theoretic Network Coding-aided MAC for Data Dissemination towards Energy Efficiency

In this paper we propose game theoretic Medium Access Control (MAC) strategies for data dissemination scenarios. In particular, we use energy-based utility functions that inherently imply power-awareness, while we consider network coding techniques to eliminate the necessity of exchanging acknowledgement control packets. Simulation results show that our proposed strategies enhance the energy efficiency of the system and reduce the dissemination completion time compared to an optimized standard protocol.

protocol nor specified which node transmits when more than one node has the greatest impact in the network.
The work of [5] has motivated us to design medium access strategies for data dissemination scenarios. Let us recall that the upper goal of data dissemination is to share a number of packets among a set of sink nodes. Specifically, the goal of all nodes is twofold: i) to complete the dissemination in a reasonable time and ii) to maximize their lifetime. Therefore, during the dissemination process, the source nodes have to balance a trade-off between transmitting data and saving energy. This fact, along with the selfish nature of the nodes, has inspired us to consider game theory [6] as an appropriate tool in order to provide this problem with a reliable solution.
In this paper, we present energy efficient game theoretic medium access strategies for data dissemination. We introduce a Dissemination Access Game (DAG) to identify a state of balance (equilibrium) of the network nodes between saving energy and proceeding the dissemination procedure. The contribution of our proposed scheme lies on the following: 1) We use energy-based game theoretic techniques to improve the energy efficiency of the system without compromising the offered QoS. 2) We propose a general access scheme that can be applied in several wireless Standards. The rest of the paper is organized as follows. In Section II we introduce the two versions of our proposed Dissemination Access Game (simple access and delay-bounded access strategy), along with the game theoretic framework of the problem. The performance evaluation of our protocols is provided in Section III, while Section IV concludes the paper.

A. System Model
We consider a network topology with a base station that holds the total amount of information and a set of nodes that desire the disseminating data. The dissemination takes place in two phases: i) in the first phase the base station broadcasts the information to the nodes that are placed inside its transmission range, and ii) in the second phase the nodes that have already received the information (so called source nodes) are enabled to forward the data to the rest interested nodes (so called sink nodes). We focus on the second phase of the problem, where we consider that there are two sources that have already obtained the total amount of information and a set of L sink nodes that are interested in the disseminating data ( Fig. 1). Furthermore, the transmission ranges of the sources are partially overlapped, while both sources affect the same number of sink nodes, thus having the same impact in the network. We further assume a slotted system, where the node with the maximum impact on the network gets the access to the channel in order to transmit in each slot. Apparently, the existence of more than one source in the network generates conflicting situations that need to be solved by specific medium access control mechanisms.
Regarding the data transmissions, random linear network coding techniques are adopted to facilitate the data dissemination. In particular, the nodes transmit linear combinations of the packets, thus eliminating the need of control packets (i.e. acknowledgements). However, an extra overhead is added to the packets, since the network coding header includes information which is necessary for the decoding of the packets, such as the coding vector, the generation size and the generation identifier.

B. Game Model
In order to focus on the energy aspect of the problem, we choose the utility function such that to quantify the lifetime of the nodes. Defining E T OT AL as the total energy amount available to each node and E[E] as the average amount of energy that is consumed by the wireless interface in each slot due to transmissions, the utility function of client i is given by . An ideal scenario would be a round robin scheduling among the source nodes coordinated by a central controller or explicit information exchange between the nodes. However, this would induce more interference and require extra energy consumption, while it is applicable only in infrastructure networks.
Since the global goal is the completion of the dissemination, all nodes have profit of transmitting data. However, the sender's role implies energy wasting, hence no client would take up this role, unless particular incentives would be provided. On the other hand, if no one transmits, the nodes will end up with spending all their energy in waiting. To analyze this conflicting situation, we model the access scenario as a static non-cooperative game with complete information, where each node maximizes its own utility.
In order to be compatible with the notations of game theory, let us start by generally denoting the set of the players 3 as N = {1, 2}. The action set includes two feasible actions, i.e. A = {transmit(T ), wait(W )}. However, in order to deal with mixed strategies, we define as actions the transmit probabilities of the players, i.e. s i = α i (T ), ∀i ∈ N . Therefore, the extended strategy space of player i is given by The strategy combination is denoted as s = (s 1 , s 2 ) ∈ S, where S is the Cartesian product of the two players' strategy spaces. Furthermore, we define as: the strategy combination of all players except i. Moreover, we extend the definition of the utility function and we use U i (s) to denote the utility of player i when the strategy combination is s. Finally, since we deal with mixed strategies, a strategy combination s * is said to achieve the Nash Equilibrium Point (N EP ) [7] when:

C. Dissemination Access Game
In the following subsections we introduce two versions of our proposed Dissemination Access Game: i) a simple access strategy, where the players estimate the N EP according to energy-based utility functions and ii) a delay-bounded access strategy, where the players act in a way similar to the simple access scheme, while a central controller is occasionally used to reduce for the completion time of the dissemination.
1) Simple Access Scheme: The straight-forward representation of the game in its strategic form is presented in Fig. 2. The set of the feasible pure actions is A = {transmit(T ), wait(W )}, while the contents of the table are energy costs that each node wishes to minimize. an extra cost, E COST , since the dissemination does not proceed. 2) One node transmits -One node waits: The transmitting node wastes energy for the transmission (E S ), while the backoff node has a zero-consumption since the data dissemination proceeds normally. 3) Both nodes wait: The nodes do not spend energy on transmissions but they do have an extra cost, E W , since they expend energy while the dissemination does not proceed. Since there is no efficient equilibrium in pure strategies, each node selects a transmit probability, s i , independently of the others. Therefore, the expected energy wasted for the two nodes is given by 3 : where the symmetry of the equations motivates us to search for symmetrical strategies.
Furthermore, the indifference principle defines that the mixed strategy N EP of a game can be simply computed by making each player indifferent among his strategy choices and, hence, we have to estimate the roots of the partial derivative of the expected cost of player 1 with respect to s 2 , i.e. ∂E[E1] ∂s2 = 0. For simplicity reasons and without loss of generality, let us assume that E W = a · E S and E COST = b · E S . Consequently: Given that the power level of the idle state in IEEE 802.11 is the 70% of the transmission state [8], we set a = 0.7, while we assume that b = 1. Fig. 3 shows a plot of client 1's utility for various values of s 2 , using numerical values: E T OT AL = 100J, E S = 9.5 · 10 −4 J, E COST = 9.5 · 10 −4 J and E W = 6.7 · 10 −4 J.
In this figure we can do the following observations: • The maximum utility of node 1 increases with s 2 .
• For large values of s 2 , the optimal strategy for node 1 is to wait. • If node 1 transmits with s 1 0.412, its utility is independent of node's 2 strategy, s 2 . Since the game is symmetric, the same holds for player 2. This value verifies our analysis (Eq. (5)) for a = 0.7 and b = 1. Hence, considering the symmetry of the game, we conclude that the strategy s = (s 1 0.412, s 2 0.412) is the N EP of our game, since any other strategy would violate the indifference principle.
2) Delay-bounded Access Scheme: Applying the proposed simple access scheme to the network, it is possible to have unsuccessful/empty slots in the network either due to collisions or idle slots when the nodes mutually transmit or wait, respectively. Hence, in order to bound the time that is needed to complete the data dissemination, we adopt the use of a 3 We use the notations i to denote the complementary probability of s i , i.e. s i = 1 − s i . central controller that defines which node is going to transmit, when we have two consecutive slots without any successful transmission. However, it is worth noticing that the controller only senses the channel and intervenes occasionally by polling one station, hence eliminating the necessity of control packets and extra overhead.
In this case, we have the following contingent before having a successful transmission of a packet: i) 1 st slot: either successful or unsuccessful transmission. ii) 2 nd slot: unsuccessful transmission in the first slot followed by either successful or unsuccessful transmission. iii) 3 rd slot: unsuccessful transmissions in the first two slots and the central controller defines which node is going to transmit. Therefore, the expected energy cost for the node 1 is given by: where the three terms in brackets represent the expected value of energy consumption with regard to the three aforementioned cases, respectively. In order to search for equilibrium strategies, let us assume again that E W = a·E S and E COST = b·E S , while the probability p poll is constant, due to the fairness of the scheduler. Differentiating the utility function with respect to s 1 gives: The best response of s 1 to the strategy s 2 is given by setting ∂U 1 ∂s1 = 0 or equivalently (from Eq. (7)) = 0. Therefore s 1 ·s 2 2 · b+ + 2 ·s 1 ·s 2 · s 2 · b − 2 ·s 1 ·s 2 2 · a · b + 6 · s 1 · s 2 2 · b+ + s 2 ·s 1 ·s 2 · a · b − s 1 · s 2 ·s 2 · a · b = 0 (8) Figure 4 shows a plot of Eq. (8) when a = 0.7 and b = 1. It can be observed that there is only one fixed-point solution in the strategy space (s 1 , s 2 ∈ [0, 1]), i.e. s * 1 = s * 2 0.25, which is the unique equilibrium of the game. In order to justify this, we use the definition of the N EP . Specifically, since the N EP is defined as the mutual best response, we conclude that any fixed point in mixed strategies constitutes a N EP [9].

III. PERFORMANCE EVALUATION
We have developed a time-driven C++ simulator that implements the rules of the proposed DAG schemes and we have carried out Monte Carlo simulations to evaluate the performance of the protocols. In this section, we present the simulation set up along with the results of our experiments.

A. Simulation Scenario
The network under simulation consists of eight nodes in total, where two of them have already obtained the total amount of information broadcasted by the base station, while the rest six are sink nodes (Fig. 5). During the dissemination, the two source nodes have the same impact on the network, since they affect the same number of sink nodes (four sink nodes in the range of each source). Additionally, the nodes are capable of performing network coding techniques to their buffer packets before forwarding them. Hence, the necessity of exchanging acknowledgements is eliminated, since it is sufficient for each node to receive a specific number of independent linear combined packets. In our simulations we assume that the nodes need to obtain 192 linearly independent packet combinations to extract the total information. The coding of the packets is performed over a finite Galois Field -GF (2 8 ), since it has been proven to be sufficient for linear independence among the packets. The specific field implies that the number of the encoding packets represents the number of the bytes in the encoding vector. If we use one generation of 192 packets, the extra overhead in each packet will be 192 bytes, which is huge especially for small size payloads. Therefore, we have chosen to create 16 generations of 12 packets each, which results in a network coding header of 13 bytes in total (12 bytes for the encoding vector, 4 bits for the generation size and 4 bits for the generation identifier).

Fig. 5. Simulation Scenario
The time slot has been selected equal to 20µsec according to the IEEE 802.11g physical layer [10], while we consider two different transmission rates with regard to the Signal-to-Interference-plus-Noise-Ratio (SINR) values: i) 54 Mb/s for high SINR conditions and ii) 24 Mb/s for low SINR conditions. Regarding the power, Ebert et al. [8] have measured the power consumption of a wireless interface during the transmission and reception phase. Based on their work, we have chosen the following power levels for our scenarios: P T = 1900mW (power consumed in Transmission Mode), P R = P I = 1340mW (power consumed in Reception and Idle Mode, respectively). The value of P T has been selected as an average value of transmission consumed power, since it varies according to the Radio Frequency (RF) power level.
In our experiments, we compare the proposed strategies with a IEEE 802.11-like protocol, where the conflicts are resolved by using backoff mechanisms. We call this scheme Backoff-MAC (BO-MAC) and the main assumption is that each source node maintains a Congestion Window (CW) equal to 32, which doubles after collisions. However, BO-MAC achieves better performance comparing to the legacy IEEE 802.11 Standard since the Inter Frame Space (IFS) times are omitted, while the backoff mechanisms are used only in particular cases, i.e. when more than one node has the greatest impact in the network. Figure 6 depicts the completion time of the data dissemination under both the proposed game theoretic schemes and the Backoff-MAC. The experiments have been conducted considering packets of various lengths (100-1500 bytes) for both low and high SINR conditions. First, we can see that our strategies outperform BO-MAC in all cases. However, it is worth noticing that game theoretic approaches achieve better performance even for worse SINR conditions for small data packets (<500 bytes). Furthermore, we observe that applying the delay-bounded strategy we are able to reduce the completion time up to 30% (packet length of 1500 bytes in low SINR conditions) compared to the simple access strategy. On the other hand, using high transmission data rates the gain is less significant, while for small packets (<250 bytes) the simple access scheme achieves better performance than the delay-bounded access strategy. This can be explained by the fact that the high transmission probabilities in the simple access scheme lead to an increased number of collisions. However, the small packet length implies small transmission time and, therefore, the collisions do not significantly affect the total completion time of the dissemination.  Figure 7 presents the simulation results with regard to the energy efficiency [11] of both versions of the Dissemination Access Game along with the Backoff-MAC. Several worthwhile observations are derived by this figure. First, although the completion time increases by using packets of big size, the energy efficient increases as well, since the amount of data delivered is beneficial for the network. Second, using the delay-bounded strategy in high SINR conditions, we have a great enhancement up to 100% compared to the BO-MAC scheme. In general, the two game theoretic schemes are proven to be more energy efficient than the optimized 802.11like protocol. However, in the low SINR scenario, BO-MAC slightly outperforms the simple access strategy for packets of 1500 bytes. This is the only case where it is more efficient to resolve the conflicts using congestion windows instead of applying game theoretic techniques. Nevertheless, in this case the delay-bounded strategy could provide an enhancement up to 50% in terms of energy efficiency comparing to the other two methods.

IV. CONCLUDING REMARKS
In this paper we proposed two game theoretic medium access strategies for data dissemination scenarios. Compared to an optimized IEEE 802.11-like scheme (BO-MAC), our approaches achieved up to 100% enhancement in energy efficiency of the system, without degrading the offered Quality of Service. In our future work we are planning to elaborate on conflicts between more than two players in order to generalize our schemes, while we aim at the validation of our results by using analytical tools and methods.