Andrey Garnaev
email: garnaev@yahoo.comtrappe@winlab.rutgers.edu

Wade Trappe

Athina Petropulu
email: athinap@rutgers.edu

An Anti-jamming Strategy when it is Unknown Which Receivers Will Face with Smart Interference

Keywords: Multicast communication, Jamming, Bayesian game

The paper considers a communication system consisting of a communication node utilizing multiple antennas in order to communicate with a group of receivers, while potentially facing interference from one or more jammers. The jammers impact the scenario by possibly interfering some of the receivers. The objective of the jammers is to reduce the throughput of nearby receivers, while taking into account the cost/risk of jamming. The fact that jammers face a cost implies that they might not choose to interfere, and thus the communication node faces uncertainty about which of its receivers will be jammed. This uncertainty is modeled by the communicator having only a priori probabilities about whether each receiver will face hostile interference or not, and if he does face such jamming, whether the jamming attack is smart or not. The goal of the communication node is to distribute total power resources to maximize the total throughput associated with communicating with all of the receivers. The problem is formulated as a Bayesian game between the communication system and the jammers. A waterfilling equation to find the equilibrium is derived, and its uniqueness is proven. The threshold value on the power budget is established for the receivers to be non-altruistic.

Introduction

Due to the openness of the wireless channel, wireless networks are vulnerable to a variety of physical layer security threats, including interference in the form of jamming attacks. For this reason, wireless security has continued to receive considerable attention by the research community and one can find a comprehensive survey of security threats in cognitive radio networks [START_REF] Sharma | Advances on security threats and countermeasures for cognitive radio networks: A survey[END_REF][START_REF] Zou | A survey on wireless security: Technical challenges, recent advances, and future trends[END_REF], particular, jamming threats, in [START_REF] Grover | Jamming and anti-jamming techniques in wireless networks: a survey[END_REF]. One of the challenges in dealing with interference attacks is to develop a strategy to cope with such interference, i.e. an anti-jamming strategy. A popular tool to design anti-jamming strategies is game theory [START_REF] Han | Game Theory in Wireless and Communication Networks: Theory, Models, and Applications[END_REF] since it gives a framework involving competitive agents from which solutions can be formulated. In game theory, the agents (say, a user and a jammer) are considered as active, i.e., they respond to a variety of environmental parameters as well as to the rival's action. The main aim of such active jammers is to magnify their jamming effect in the network they intend to jam, while also balancing the costs associated with their efforts (e.g. they might aim to conserve their energy).

The term smart jammer is used to label jammers that aim to balance their efforts against costs/risks, while naive jammer is used to for jammers that do not consider their costs/risks. We now provide a quick, and wide sampling of the research literature involving smart jammers. For example, in [START_REF] Yuan | Optimal transmission strategy for sensors to defend against eavesdropping and jamming attack[END_REF], applying a Stackelberg game approach, the problem of maximizing the secure transmission rate between sensors and a controller while in the presence of a malicious eavesdropper and smart jammer was investigated. In [START_REF] Jia | Bayesian stackelberg game for antijamming transmission with incomplete information[END_REF], interactions between the user and a smart jammer with SNR as the user's utility was modeled as an antijamming Bayesian Stackelberg game involving uncertainties for the channel gain and transmission cost, and in which the the user acted as the game's leader. In [START_REF] Slimeni | Learning multichannel power allocation against smart jammer in cognitive radio networks[END_REF], a modified Q-learning algorithm against a user's fixed strategy and a smart jammer for multi-channel transmission was developed and compared with the corresponding Nash equilibrium. In [START_REF] Yang | Coping with a smart jammer in wireless networks: A stackelberg game approach[END_REF], a jamming defense problem, in which the jammer can quickly learn the transmission power for the user and adaptively adjust its transmission power to maximize the damaging effect, was investigated. In [START_REF] Jeung | Adaptive rapid channel-hopping scheme mitigating smart jammer attacks in secure WLAN[END_REF], an adaptive rapid channel-hopping scheme was introduced using the notion of a dwell window and a deception mechanism to mitigate smart jammer attacks. In [START_REF] Lu | GPS smart jammer suppressin algorithm based on spatial APES[END_REF], a smart jammer suppression algorithm for a GPS receiver was designed combining spatial amplitude and phase estimation method and high resolution coherent subspace estimation method. In [START_REF] Xiao | User-centric view of jamming games in cognitive radio networks[END_REF], the interactions between a user and a smart jammer regarding their respective transmit power choices was studied using prospect theory. In [START_REF] Garnaev | The eavesdropping and jamming dilemma in multichannel communications[END_REF], the optimal user's strategy is designed when unknown whether the user faces with jamming or eavesdropping attack. In [START_REF] Aziz | Resilience of LTE networks against smart jamming attacks[END_REF], a jamming attack against an LTE network was modeled by a repeated game where a smart adversary can be a cheater or a saboteur. The cheater intends to gain more resources for itself, and thus the adversary's intent is not to damage the channel resources, but rather jams the network as a side effect of its malicious activity by reducing competition among the other users, while the saboteur intends to cause the most possible damage to the network resources. In [START_REF] Garnaev | Bandwidth scanning when facing interference attacks aimed at reducing spectrum opportunities[END_REF], the optimal bandwidth scanning strategy facing interference attacks aimed at reducing spectrum opportunities is designed. In [START_REF] Oro | Defeating jamming with the power of silence: A game-theoretic analysis[END_REF], the interactions between a jammer and a communication node that exploits a timing channel to improve resilience to jamming attacks is studied in a game-theoretic framework involving a smart jammer who starts transmitting its interference signal only after detecting activity by the node. In [START_REF] Namvar | Jamming in the internet of things: A game-theoretic perspective[END_REF], an evolutionary algorithm is proposed to find the equilibrium strategy of a collection of IoT devices seeking to thwart a jamming attack by distributing power among communication subcarries in a smart way so as to decrease the aggregate bit error rate caused by the jammer. In [START_REF] Cumanan | Secure multicast communications with private jammers[END_REF], the problem of secure multicast communications was formulated as Stackelberg game where smart private jammers were allocated nearby to eavesdroppers to increase the secrecy capacity of multicast communication.

In all of these papers, the players are assumed to be smart, i.e., rational, which is reflected by employing the best response strategy in the actions taken by the rivals. Recently, behavioral economics has challenged such rational and selfish individual behavior [START_REF] Thaler | Misbehaving: The making of behavioral economics[END_REF]. It has suggested that human decisions vary across time and space, and is subject to cognitive biases, emotions, and thus there may actually be uncertainty regarding the motivations of the rivals. Thus, some players, for whatever reason might not apply the best response strategy in response to their rival's strategies, and thus can be considered as non-rational strategies.

In this paper, we explore a complementary aspect of designing anti-jamming strategies for physical layer, multicast communication systems by recognizing a new challenge for such a system that is motivated by the observation, inherited from behavioral economics, that there may be non-rational behavior by the agents. Namely, we investigate the impact that incomplete information regarding a communication node (CN), whether its receivers face jamming attacks, and whether these attacks are smart or not can have on the anti-jamming strategy.

In order to explore this impact, we examine the specific case of a multicast system consisting of a CN employing multiple antennas to communicate with a group of receivers. The communication with some of the receivers might be targeted by jammers, and the CN knows only only a priori probabilities about whether each receiver will face hostile interference or not, and if he does face such jamming, whether the jamming attack is smart or not. We formulate this problem as a Bayesian game between the CN and several jammers that might be allocated near the receivers. Existence and uniqueness of the equilibrium strategies are proven, and a waterfilling equation to find the equilibrium strategies is formulated.

The organization of this paper is as follows: in Section 2, the model is described. In Section 3, auxiliary notation and results are given. In Section 4, uniqueness of the equilibrium is proven, and then the waterfilling equation to find the equilibrium is derived. Finally, in Section 5, conclusions are given.

Communication model

We begin our formulation by considering an operational scenario involving a communication node (CN) that is capable of supporting multiple antenna communication [START_REF] De Lamare | Massive MIMO systems: Signal processing challenges and future trends[END_REF]. The multiple antenna interfaces allow this node to operate in a P2P fashion with many receivers simultaneously. We suppose the CN is equipped with n antennas allowing it to communicate with n receivers. We assume that the signals employed are orthogonal, and, thus, they do not interfere each other [START_REF] Zhao | Intercarrier interference self-cancellation scheme for OFDM mobile communication systems[END_REF][START_REF] Tang | Space-time interference cancellation in MIMO-OFDM systems[END_REF]. There is the possibility that a jammer might be present near each receiver, with the intent to jam the communication. Thus, the number of jammers is at most n. In our scenario, we assume each of the jammers is equipped with a single antenna, and he can jam only its neighboring receiver. We portray this scenario in Fig. 1. In order to maintain the reliable communication with the receivers, the CN has to allocate its total power P across the orthogonal signals so as to maximize the total throughput. Thus, a strategy of the CN is a vector P = (P1, . . . , Pn) with Pi being the power assigned to communicate with receiver i. Let Π be the set of feasible strategies for the CN. The strategy for jammer i is a power J employed to jam communication with receiver i. Let qi be a priori probability that the jammer i is smart. Under the case of a smart jammer, we assume that he employs the best response strategy, i.e. he is focused on getting the best result. Thus, for a smart jammer the set of feasible strategies is R+. In contrast, a naive jammer, which employs a constant jamming strategy, i.e., a constant jammer, will be considered as our non-smart jammer since he does not adapt, and in particular does not use the best response strategy. Thus, for the non-smart jammer the set of feasible strategies is reduced to the single point {J}. Let q i = 1 -qi be the probability that the jammer i is non-smart. Let Gi(J) be the probability distribution function associated with applying jamming power J by the non-smart jammer i. We include here also an important particular case J = 0 which reflects the possibility that the jammer might be missing (or not active), and thus communication with the receiver might not suffer from hostile interference. Let J = (J1, . . . , Jn). Then, the payoff to the CN is the expected total throughput, i.e.,

vCN (P , J ) = n i=1 qi ln 1 + hiPi σ 2 i + giJi + q i R + ln 1 + hiPi σ 2 i + giJ dGi(J) , ( 1
)
where hi and gi are fading channel gains, while σ 2 i is the background noise. For a boundary scenario, where the feasible strategy for each non-smart jammer is J = 0, the a priori probability q i is defined as the probability that the jammer for receiver i is missing. Then, the payoff (1) can be simplified as follows:

vCN (P , J ) = n i=1 qi ln 1 + hiPi/(σ 2 i + giJi) + q i ln 1 + hiPi/σ 2 i . ( 2
)
Since the smart jammer i intends to harm communication with receiver i, this throughput can be considered as the smart jammer's cost utility. Hence, as payoff to the smart jammer i, we consider the difference between his payoff utility (which is his cost utility multiplied by minus one) and the cost of the employed jamming efforts, i.e.,

vi(Pi, Ji) = -ln 1 + hiPi/(σ 2 i + giJi) -CiJi, ( 3
)
where Ci is the jamming cost per power unit. Note that (3) is a classical payoff for the jammer in CDMA-style transmission problems with resource power costs, which has been studied in literature for different scenarios [START_REF] Yang | Coping with a smart jammer in wireless networks: A stackelberg game approach[END_REF][START_REF] Garnaev | To eavesdrop or jam, that is the question[END_REF]. Each of the rivals wants to maximize its payoff, and thus we look for the Nash equilibrium [START_REF] Han | Game Theory in Wireless and Communication Networks: Theory, Models, and Applications[END_REF]. Recall that (P * , J * ) is an equilibrium if and only if, for any (P , J ) , the following inequalities hold:

vCN (P , J * ) ≤ vCN (P * , J * ), (4)
vi(P * i, Ji) ≤ vi(P * i, J * i) for i = 1, . . . , n.

(

) 5
We may consider the smart jammer and non-smart jammer as a single jammer, but able to have different types. From this perspective, the CN knows only a priori probability about type of the jammer it faces with, and this allows us to interpret the game as a Bayesian game between the CN and several jammers [START_REF] Han | Game Theory in Wireless and Communication Networks: Theory, Models, and Applications[END_REF].

Theorem 1

The considered game has at least one equilibrium.

Proof. It is clear that vCN (P , J ) is concave in P , and vi(Pi, Ji) is concave in Ji. Also, the set Π of feasible strategies for the CN is compact. To be in the framework of Nash's theorem for the existence of equilibrium [START_REF] Han | Game Theory in Wireless and Communication Networks: Theory, Models, and Applications[END_REF], the set of feasible strategies for each jammer also has to be compact, while it is R+. Note that

∂vi(Pi, Ji) ∂Ji = hiPi σ 2 i + giJi + hiPi gi σ 2 i + giJi -Ci ≤ gi σ 2 i + giJi -Ci.
Thus, ∂vi(Pi, Ji)/∂Ji < 0 for Ji > 1/Ci -σ 2 i /gi. This means that none of the strategies Ji > 1/Ci -σ 2 i /gi can be an equilibrium strategy. Thus, the set of feasible strategies for the jammer i can be reduced to the compact set [0, max{0, 1/Ciσ 2 i /gi}], and the result follows.

Auxiliary notations and results

Let us introduce auxiliary notations:

Li(Pi, Ji) := qihi σ 2 i + giJi + hiPi + R + q i hi σ 2 i + hiPi + giJ dGi(J), (6)
Mi(Pi, Ji) := higiPi/((σ

2 i + giJi + hiPi)(σ 2 i + giJi)). ( 7
)
In the next two propositions, important properties of these functions Li and Mi, which will be employed further to design the equilibrium strategy, are gathered.

Proposition 1 (a) Li(Pi, Ji) is decreasing in Pi and Ji.

(b) Li(Pi, Ji) tends to zero, while Pi tends to infinity. (c) Let 0 < ω ≤ Li(0, 0). Then

Li(Pi, Ji(Pi)) = ω for Pi ∈ [P i , P i], ( 8
)
where

Ji(x) := hi gi qi ω - R + q i hi/(σ 2 i + hix + giJ) dG(J) - σ 2 i + hix gi , ( 9
)
and P i = P i (ω) and P i = P i(ω) are unique positive roots of the equations:

Li(P i(ω), 0) = ω, Li(P i (ω), ∞) := R + q i hi/(σ 2 i + hiP i (ω) + giJ) dGi(J) = ω. ( 10
)
(d) Ji(Pi) is strictly decreasing from infinity for Pi ↓ P i to zero for Pi = P i.

(e) P i(ω) is continuous and decreasing from infinity for ω ↓ 0 to zero for ω = Li(0, 0).

Proof. (a) and (b) follow directly from [START_REF] Jia | Bayesian stackelberg game for antijamming transmission with incomplete information[END_REF]. (a) and (b) jointly with (8) imply (c). (a), ( 8) and ( 10) yield (d). (a), ( 6) and [START_REF] Lu | GPS smart jammer suppressin algorithm based on spatial APES[END_REF] imply (e), and the result follows.

Proposition 2 (a) Mi(Pi, Ji) is increasing in Pi and decreasing in Ji.

(b) Mi(P i(ω), 0) is decreasing from

g i /σ 2 i for ω ↓ 0 to zero for ω = Li(0, 0). (c) If gi/σ 2 i ≤ Ci then Mi(P i(ω), 0) < Ci for ω < Li(0, 0), while if gi/σ 2 i > Ci
then is a unique ωi ∈ (0, Li(0, 0)) such that

Mi(P i(ω), 0)    > Ci, 0 < ω < ωi, = Ci, ω = ωi, < Ci, ωi < ω < Li(0, 0). ( 11
)
Let Ωi = 0 for gi/σ 2 i ≤ Ci and Ωi = ωi for gi/σ 2 i ≤ Ci.
Proof. (a) follows from [START_REF] Slimeni | Learning multichannel power allocation against smart jammer in cognitive radio networks[END_REF]. Proposition 1, (a) and ( 7) imply (b). (b) yields (c), and the result follows.

Equilibrium strategies

In this section, to find the equilibrium and prove its uniqueness, we employ a constructive approach. We first use a parameter (Lagrange multiplier) to describe the form each equilibrium must have. This allows us to obtain a continuum of candidates for the equilibrium. Then, we prove that only one of them is the equilibrium.

Proposition 3 Each equilibrium has to have the following form (P (ω), J (ω))

where ω > 0 is a parameter:

(a) If

i ∈ Ia(ω) := {i : Li(0, 0) ≤ ω} ( 12
)
then Pi(ω) := 0 and Ji(ω

) := 0, ( 13
) (b) If i ∈ I b (ω) := {i : Ωi ≤ ω < Li(0, 0)} ( 14
)
then Pi(ω) := P i(ω) and Ji(ω

) := 0, ( 15
) (c) If i ∈ Ic(ω) := {i : ω < Ωi} ( 16
)
then Pi(ω) is the unique root in [P i (ω), P i(ω)] of the equation

Fi(Pi(ω)) = Ci ( 17
)
while

Ji(ω) := Ji(Pi(ω)), (18)
with

Fi(x) := Mi(x, Ji(x)). ( 19
)
Moreover, Ji(ω) and Pi(ω) have the following monotonic properties on ω: Property (Π -J) : Ji(ω) is continuous and decreasing to zero ω = Ωi. Property (Π -P ) : Pi(ω) is continuous and decreasing on ω from infinity for ω ↓ 0 to P i(ω) for ω = Ωi.

Proof. By (4) and ( 5), (P , J ) is an equilibrium if and only if these strategies are the best response to each other, i.e., they are solutions of the following best response equations:

P = BRCN (J ) := argmax{vCN (P , J ) : P ∈ Π}, ( 20
)
Ji = BRJ,i(P ) := argmax{vi(Pi, Ji) : Ji ∈ R+} for i = 1, . . . , n. (21)
Since ( 20) is a concave NLP problem, to solve it we have to introduce a Lagrangian depending on a Lagrange multiplier ω as follows: Lω(P ) := vCN (P , J ) +

ω(P - n i=1 Pi).
Then, taking into account notation [START_REF] Yang | Coping with a smart jammer in wireless networks: A stackelberg game approach[END_REF], KKT Theorem implies that P ∈ Π is the best response strategy if and only if the following condition holds:

∂Lω(P ) ∂Pi = Li(Pi, Ji) -ω = 0, Pi > 0, ≤ 0, Pi = 0. ( 22
)
Since ( 21) is an optimization problem involving one real variable Ji and vi is concave in Ji, in notation [START_REF] Slimeni | Learning multichannel power allocation against smart jammer in cognitive radio networks[END_REF], Ji is the best response strategy if and only if the following relations hold:

∂vi(Pi, Ji) ∂Ji = Mi(Pi, Ji) -Ci = 0, Ji > 0, ≤ 0, Ji = 0. (23)
By [START_REF] Garnaev | Equilibrium strategies for an OFDM network that might be under a jamming attack[END_REF], if Pi = 0 then Ji = 0. Substituting both of them into [START_REF] Garnaev | To eavesdrop or jam, that is the question[END_REF] implies that i ∈ I a (ω) given by [START_REF] Garnaev | The eavesdropping and jamming dilemma in multichannel communications[END_REF], and (a) follows. Thus, we have only to consider separately two cases: (A) Pi > 0, Ji = 0 and (B) Pi > 0, Ji > 0.

(A) Let Pi > 0 and Ji = 0. Then, by ( 22) and ( 23),

Li(Pi, 0) = ω, ( 24
)
Mi(Pi, 0) ≤ Ci. ( 25
)
By Proposition 1(d), the equation ( 24) has a positive root if and only if

ω < Li(0, 0), (26)
and, moreover, it is equal to P i(ω). This implies [START_REF] Oro | Defeating jamming with the power of silence: A game-theoretic analysis[END_REF]. Substituting this Pi = P i(ω) into (27) implies that the following inequality must hold:

Mi(P i(ω), 0) ≤ Ci. ( 27
)
By Proposition 2(b) and (c), ( 27) holds if and only if Ωi ≤ ω ≤ Li(0, 0). This and (26) yield that i ∈ I b (ω) given by ( 14), and thus (b) follows.

(B) Let Pi > 0 and Ji > 0. Then, by ( 22) and ( 23),

Li(Pi, Ji) = ω, ( 28
) Mi(Pi, Ji) = Ci. ( 29
)
Solving (28) on Ji implies that Ji = Ji(Pi) with Ji given by [START_REF] Jeung | Adaptive rapid channel-hopping scheme mitigating smart jammer attacks in secure WLAN[END_REF]. By (28), Pi and Ji are functions of ω, i.e., Pi = Pi(ω) and Ji = Ji(ω). By ( 8) and (28),

lim ω↓0 Pi(ω) = ∞. (30)
By Proposition 2(a), the left side of (29) is increasing in Pi and decreasing in Ji. Thus, to be a solution for (29), these Pi(ω) and Ji(ω) have to be either decreasing or increasing simultaneously on ω. This and (30) imply that Pi(ω) and Ji(ω) are decreasing on ω. By ( 8), ( 11), ( 28) and (29), Ji(Ωi) = 0 and Pi(Ωi) = P i(Ωi). This, jointly with (30) yield properties (Π -J) and (Π -P ).

For a fixed ω, by (28), J i is a function on Pi, namely, Ji = Ji(Pi). Substituting this Ji into (28) implies that Pi has to be the root of equation [START_REF] Cumanan | Secure multicast communications with private jammers[END_REF]. By Proposition 1(d), Ji(Pi) is decreasing from infinity for Pi ↓ P i to zero for Pi = P i with P i and small P i given by [START_REF] Lu | GPS smart jammer suppressin algorithm based on spatial APES[END_REF]. Thus, by Proposition 2(a), we have that Fi(Pi) is increasing on Pi. Moreover, since lim J i ↑∞ Mi(Pi, Ji) = 0 for each fixed Pi then

Fi(P i ) = Mi(P i , ∞) = 0, (31)
Fi(P i) = Mi(P i, 0). ( 32
)
Thus, since Fi is increasing, [START_REF] Cumanan | Secure multicast communications with private jammers[END_REF] has root if and only if Mi(P i, 0) > Ci. By [START_REF] Xiao | User-centric view of jamming games in cognitive radio networks[END_REF], this is equivalent to ω < Ωi, i.e., i ∈ Ic(ω) given by ( 16), and (c) follows. Proof. The result follows directly from Proposition 3.

Theorem 2

The game has a unique equilibrium, namely (P , J ) = (P (ω), J (ω)), with P (ω) and J (ω) given by Proposition 3 and ω given by (33).

Proof. Proposition 3 describes such a parameterized set of functions P :

R+ → R n
+ that each CN equilibrium strategy belongs to. To ascertain whether each of them is an equilibrium, we have to verify whether it utilizes all of the power resource, i.e., whether (33) holds. By Proposition 4, (33) has the unique root, and the result follows.

If the total power budget is enough large then the CN can maintain communication with all the receivers, namely, the following result holds.

Corollary 1 Pi > 0 for all i if and only if P ≥ H(L) where L := mini Li(0, 0). Proof. By Proposition 3, Pi(ω) > 0 for any i if and only if ω < L. Then, Theorem 2 straightforward implies the result.

Finally, the two boundary cases of Theorem 2: (a) none of the jammers are smart, and (b) each of the jammers is smart, can be simplified as follows:

Corollary 2 (a) Let qi = 0, ∀i, i.e., none of the jammers is smart. Then, the CN optimal strategy

P = P (ω) is Pi(ω) is    R + hi/(σ 2 i + hiPi(ω) + giJ) dGi(J) = ω, R + hi/(σ 2 i + giJ) dGi(J) > ω, 0, otherwise.
(b) Let qi = 1, ∀i, i.e., each jammer is smart. Then, the equilibrium strategies P = P (ω) and J = J (ω) are:

Pi(ω) =    Cihi/((Cihi + ωgi)ω), ω < hi/σ 2 i -hiCi/gi, 1/ω -σ 2 i /hi, hi/σ 2 i -hiCi/gi ≤ ω < hi/σ 2 i , 0, hi/σ 2 i ≤ ω, Ji(ω) = (hi/gi) 1/ω -(σ 2 i + hiPi(ω))/hi , ω < hi/σ 2 i -hiCi/gi, 0, ω ≥ hi/σ 2 i -hiCi/gi.
In both cases, (a) and (b), ω is given as the unique root of water-filling equation n i=1 Pi(ω) = P .

Discussion of results and conclusions

In this paper, we formulated and solved a Bayesian game between a communicating node and several jammers that might be allocated near several receivers. Our model also allowed for jammers to be smart (i.e. follow equilibrium strategy), or non-smart. The considered game combines two types of strategies: (a) power allocation akin to OFDM style for the CN, and (b) power assigning akin to CDMA style for each jammer. It is interesting that the obtained equilibrium strategies have a hierarchical structure although we look for the Nash equilibrium. Namely, in the first step, the CN equilibrium strategy is found by solving the water-filling equation (33). In the second step, the jamming strategies J are designed as the derivative of P . In particular, it allows to to establish the threshold value on the power budget to maintain non-altruistic communication with all the the receivers. This makes the problem completely different from the OFDM jamming problem in the general SNR regime, where a system of two water-filling equations must be solved simultaneously [START_REF] Garnaev | Equilibrium strategies for an OFDM network that might be under a jamming attack[END_REF], i.e., user and jammer strategies have to be designed simultaneously. The equilibrium strategy of the considered game coincides with the equilibrium in OFDM jamming problem only for a boundary case where all the smart jammers are non-active due to high jamming costs, i.e., when the CN strategy is classical OFDM transmission strategy [START_REF] Altman | Closed form solutions for waterfilling problem in optimization and game frameworks[END_REF]. It is interesting that although in OFDM jamming problem for the low SNR regime the equilibrium jammer's strategy also can be found in one step, multiple user equilibrium strategies might arise [START_REF] Garnaev | An OFDM-based dual radar/communication system facing uncertain jamming power[END_REF], while in the considered game the equilibrium is always unique. Fig. 2(a) and (b) illustrate the dependence of the equilibrium strategies on a priori probabilities for the case when non-smart jammers employ jamming power according to uniform distribution in [0, b] with b = 0.1, and n = 5, P = 1, σ 2 = (1, 1, 1, 1, 1), h = (0.5, 0.9, 0.6, 0.9, 0.7), g = (1, 2, 1.3, 1.8, 0.9), C = (0.1, 0.04, 0.03, 0.05, 0.02), while a priori probabilities are given as follows: q = (Q, Q, Q, Q, Q) with Q ∈ {0.2, 0.4, 0.6, 0.8}. Fig. 2(c) illustrates zone in plane (b, Q) where the total power budget is enough for the CN to maintain communication with all the receivers, i.e., when the CN strategy does not assume altruistic behaviour for none of the receivers. where none of the receivers is altruistic.

Fig. 1 .

 1 Fig. 1. The CN, receivers and jammers.

Proposition 4

 4 (a) The function H(ω) := n i=1 Pi(ω) is continuous and decreasing from infinity for ω ↓ 0 to zero for L := maxi Li(0, 0). (b) The following water-filling equation has the unique root in (0, L): H(ω) = P . (33)

Fig. 2 .

 2 Fig. 2. (a) Equilibrium strategy of the CN, (b) equilibrium strategies of the jammers and (c) zone


Ioanna Karantaidou

Spyros T Halkidis
email: halkidis@uom.edu.gr

Sophia Petridou
email: spetrido@uom.edu.gr

Lefteris Mamatas
email: emamatas@uom.edu.gr

George Stephanides

Pairing-Based Cryptography on the Internet of Things: A Feasibility Study

Keywords: Pairing-based cryptography, Identity-based encryption, short signatures, Internet of Things

Pairing-based cryptography (PBC) has recently received much attention, since the mathematical building block of pairings paved the ground for devising efficient cryptographic protocols exploiting an old inspiration, i.e., to produce the public key of an entity based on its identity. The so-called Identity-Based Cryptography (IBC) simplifies key management procedures, since it does not require certificate-based infrastructures. Moreover, it is an elliptic curve cryptosystem which entails that it offers the same security levels as other public key systems with much smaller key lengths. The above characteristics make it an attractive solution for resource-constrained environments such as the Internet of Things (IoT), where strong confidentiality and signature schemes are necessary. In this article, we conducted feasibility tests of pairing-based cryptography for middle-class IoT devices, such as the Raspberry Pi 3 platform.

Introduction

The Internet of Things (IoT) has overwhelmed the cyber-physical world with billions of interconnected, fixed or mobile, devices ranging form wearables to smartphones [START_REF] Atzori | The Internet of Things: A survey[END_REF]. Providing access anytime, anywhere, anyhow, the IoT has the potential to enable innovative application in many domains such as home or building automation, automotive, transportation surveillance and health-care. However, along with its scale, the IoT augments the security concerns due to the ubiquitous nature of the IP-things which are sending private data to backend systems, e.g., edge or core cloud, and servers [START_REF] Sicari | Security, privacy and trust in the Internet of Things: The road ahead[END_REF].

Let us consider a smart health-care system where patients' wearables can either communicate directly with a hospital's IoT infrastructure or send collected data to intermediate devices, e.g., a Raspberry Pi, which gathers and forwards them to the cloud. In such a scenario, either the links, i.e., Internet connections, or the nodes, i.e., collaborating devices, can be untrusted. Thus, strong cryptography is required to provide efficient confidentiality and authentication solutions.

At the same time, the resource-constrained nature of the IoT environment, both in terms of low rate communication links and hardware-limited devices, strives for lightweight cryptographic protocols.

Recently, pairing-based cryptography (PBC) has received much attention [START_REF] Moody | Report on pairing-based cryptography[END_REF], since pairings are revealed to be the mathematical tool which makes possible the Shamir's inspiration of certificate-less Public Key Cryptography (PKC) [START_REF] Shamir | Identity-based cryptosystems and signature schemes[END_REF]. In 1984, Shamir proposed to authenticate an entity using some form of its identity, e.g., the email address, instead of its certificate. The main advantage of Identity-Based Cryptography (IBC) is that enables message encryption without the need of previously distributed keys. Such a facility is attractive in IoT use-cases where keys' pre-distribution is impractical or raises security concerns. For example, when the same key is shared among all "things", the impairment of a single device exposes the security of the whole network; or when a dedicated key is established for each couple of "things", the solution is not scalable. Moreover, the IBC provides the feature of including date information to the identity which entails revocation support without the use of certificate revocation lists (CRLs) [START_REF] Moody | Report on pairing-based cryptography[END_REF].

Two fundamental protocols, which addressed in 2001 the issue of devising efficient IBC schemes, are the Boneh and Franklin's identity-based encryption (IBE) protocol [START_REF] Boneh | Identity-based encryption from the Weil pairing[END_REF] and the Boneh, Lynn and Shacham's (BLS) short signature scheme [START_REF] Boneh | Short signatures from the Weil pairing[END_REF]. IBC is public key cryptography in the sense that roughly a public key is used for encryption and a private key for decryption. However, instead of producing the public key from the private, IBC defines that public keys are issued upon pre-existing identifiers. This entails no need of Certification Authorities (CAs). Instead, a Private Key Generator (PKG) authenticates the receiver, generates his private key and provides public system parameters to the sender.

Motivated by the general advantage of IBC, i.e., it simplifies key management procedures of certificate-based public key infrastructures, in this paper, we evaluate the feasibility of the aforementioned pairing-based protocols on middleclass IoT devices, such as the Raspberry-Pi 3 platform, through experimentation. More precisely, we present the basic Boneh and Franklin's IBE scheme, namely BasicIdent and we implement its FullIdent version, which is Chosen-Ciphertext Secure, using the Relic-Toolkit library [START_REF] Aranha | RELIC is an Efficient Library for Cryptography[END_REF]. In addition we evaluate the performance of BLS short signature scheme in contrast with the Elliptic Curve Digital Signature Algorithm (ECDSA) [START_REF] Johnson | The elliptic curve digital signature algorithm (ECDSA)[END_REF]. Thus, our work focuses on encryption and decryption for IBE schemes, and on signing and verifying for signatures schemes. Feasibility is expressed in terms of protocols' execution time, memory usage and energy consumption.

Our contribution can be summarized as follows:

1. we conducted real experiments to measure the resource requirements of fundamental pairing-based crytposystems in terms of CPU time, memory and energy; 2. we implement the FullIdent IBE scheme inside the Relic-Toolkit library; 3. we compare the performance of BasicIdent and FullIdent IBE schemes, as well as of BLS and ECDSA signature schemes for different security levels;

4. we tested the feasibility of pairing-based algorithms for middle-class IoT devices, such as the Raspberry-Pi 3 platform.

The rest of the paper is organized as follows. A motivating use-case scenario along with pairings preliminaries are presented in Section 2. Section 3 reveals the algorithms and computational overhead of the Boneh-Franklin's protocols and the BLS signature scheme, while Section 4 provides a discussion over the experimental results. Section 5 is a brief overview of related studies. We conclude the article along with some future work insights in Section 6.

2 Pairing-Based Cryptography

Pairings on the IoT

To demonstrate the features and advantages of PBC in real-world IoT environments, we consider a smart health-care scenario, illustrated in Fig. 1. A patient, Peter, uses his smartphone to send some medical results to doctor David, who is on-call on the hospital Hippocrates during Friday. With traditional public key cryptography, Peter needs to know David's public key. How can Peter be sure that holds the valid David's key, and not some other key substituted by a malicious attacker? So far, certificates are the classical solution to authenticate David's key. In PBC, the string ID = David||Hippocrates||F riday could be a form of doctor's identity for his public key. Thus, without the need of previously distributed keys, Peter can encrypt his private M essage using the ID and public parameters announced by the PKG, which is implemented in a base station of the hospital's infrastructure. Once David received the Ciphertext in his smartphone, he should be firstly authenticated and then proceed to data decryption. His ID can be exploited both by the signature scheme and the decryption function, since it constitutes part of his private key. The interesting feature is that the same doctor cannot access the data from his home or two days later, since his public key can be issued on-the-fly encoding information associated with his status. BLS instead of being able to authenticate a user upon his identity, it produces short signatures, i.e., 100s of bits in length. This is very attractive in low rates communications, since it entails shorter transmission time and fewer energy consumption in transmitters. Moreover, it is important when multiple authentication points exist. To clarify the details behind the IBE and BLS schemes used in this scenario, we provide a brief introduction to pairings.

Preliminaries on Pairings

Pairings are mathematical tools, widely used to implement the Shamir's idea for IBE and signature schemes that replace the public key of an entity with basic information about it, e.g., an identity string [START_REF] Shamir | Identity-based cryptosystems and signature schemes[END_REF]. In Cryptography, a pairing, also called a (nondegenerate or admissible) bilinear pairing, is a bilinear map e : G 1 × G 2 → G T where G 1 , G 2 are additive groups and G T is a multiplicative group, all of prime order p. We use groups in which the discrete logarithm problem is believed to be adequately hard.

A pairing satisfies the following conditions:

1. bilinearity: i.e., ∀P ∈ G 1 , Q ∈ G 2 and a, b ∈ Z p , it holds that e(aP, bQ) = e(P, Q) ab . aP = P + P + • • • + P (a times) and it corresponds to the scalar multiplication in the additive group. 2. non-degeneracy: i.e., ∀P = O G1 and Q = O G2 , e(P, Q) = 1 G T , which expresses the fact that the map does not send all pairs to the neutral (identity) element of G T . O G1 , O G2 and 1 G T correspond to the neutral elements of the groups G 1 , G 2 and G T , respectively.

In addition, pairings should be efficiently computable and are usually constructed on elliptic curves over finite fields. A pairing environment is considered as a tuple (p, G 1 , G 2 , G T , P 1 , P 2 , e), where P i is a generator of the group G i . When G 1 = G 2 , the pairing is called symmetric. This type was well-used at the dawn of PBC, but it has been gradually dismissed, since it mostly uses supersingular curves over small characteristic finite fields, i.e., very large groups for certain security levels. Thus, for efficiency reasons asymmetric pairings (i.e., G 1 = G 2 ) are more attractive in practice [START_REF] Galbraith | Pairings for cryptographers[END_REF].

Confidentiality and Authentication using Pairings

Identity-Based Encryption

An IBE scheme is a group of four algorithms:

-Setup: Run by the PKG. According to a security parameter, computes a master key that is kept secret and a system's public key P pub , published as a parameter. Outputs the system parameters. -Extract: Run by the PKG, takes as input the master key and an entity's identity ID ∈ {0, 1} * , outputs the entity's private key d ID . Private keys are generated using the master key. It is the PKG's role to generate and distribute them to the communicating entities. -Encrypt: Takes as input the system's public key P pub , an identity ID and a message M and outputs the ciphertext C. -Decrypt: Takes as input the system's public key P pub , the entity's private key d ID and a ciphertext C and outputs the message M or a message of failure.

Boneh-Franklin IBE Schemes

3.1.1.1 BasicIdent and CCA security The basic IBE scheme, named Ba-sicIdent proposed by Boneh and Franklin in [START_REF] Boneh | Identity-based encryption from the Weil pairing[END_REF] is secure against eavesdropping, however it is susceptible to Adaptive Chosen Chiphertext Attacks (CCA). In a CCA, an adversary may make adaptively queries and obtain decryptions of ciphertexts different than the target ciphertext. The attack is successful when the adversary manages to obtain some information about the plaintext that corresponds to the target ciphertext.

A ciphertext C produced by the BasicIdent protocol has the following form:

C = (C 1 , C 2 ) = (C 1 , M ⊕ H),
where M is the message and H is the output of a hash function, both in binary format. As we can see, the ciphertext is malleable. The adversary can flip one specific bit of C 2 , make a query with (C 1 , C 2 ) = (C 1 , M ⊕ H) and obtain the decryption of M . By flipping again the same bit, the message M is recovered.

3.1.1.2 FullIdent This scheme, also proposed by Boneh and Franklin in [START_REF] Boneh | Identity-based encryption from the Weil pairing[END_REF], uses the Fujisaki-Okamoto transformation [START_REF] Fujisaki | Secure integration of asymmetric and symmetric encryption schemes[END_REF] which makes any cryptographic scheme CCA-secure. Two more cryptographic hash functions are added, the structure of the encrypted message is altered and one check at the end of the decryption process determines if the decrypted message is accepted or not. The original scheme contains symmetric pairings. In a more recent approach, the scheme is slightly adjusted to make use of asymmetric pairings [START_REF] Galindo | Boneh-Franklin identity based encryption revisited[END_REF].

The FullIdent is the following scheme:

-Setup: The PKG chooses a random s ∈ Z * p and keeps it as a master key. Then computes P pub = sP 1 with P 1 being a generator for G 1 . The system parameters (p, G 1 , G 2 , G T , P 1 , P 2 , e), P pub are published. The following cryptographic hash functions are defined:

H 1 : {0, 1}* → G * 2 , H 2 : G T → {0, 1} l , H 3 : {0, 1} l × {0, 1} l → Z p * and H 4 : {0, 1} l → {0, 1} l . -Extract: For an identity ID, Q ID = H 1 (ID) ∈ G * 2 is computed and d ID = sQ ID ∈ G *
2 is the recipient's private key.

Algorithm 1 The FullIdent encryption algorithm

Input: Message M with length l, system key P pub , identity ID. Output: Ciphertext C = (U, V, W ). -Encrypt and Decrypt: The encryption and decryption algorithms are given by Algorithms 1 and 2, respectively.

Based on the properties of pairings, the protocol is correct since: The performance of the scheme depends on the cost of pairing calculations. One pairing is calculated by the sender in step 4 of Algorithm 1 and one by the recipient in step 1 of Algorithm 2. The exponentiation in step 4 of the encryption algorithm also demands notable calculation. This entails that the encryption is more time demanding compared to the decryption, and the experimental results derived confirm it.

BLS Short Signature Scheme

The BLS signature scheme produces short length signatures and it makes use of pairings only during the verification process. More precisely, this signature scheme is a group of four algorithms:

-Setup: The system parameters (p, G 1 , G 2 , G T , P 1 , P 2 , e) and one cryptographic hash function H : {0, 1} * → G 1 are defined and published. -Key Generation: Run by the signer. A random x ∈ Z * p is picked as the private key. The public key pk is computed as pk = xP 2 ∈ G 2 and published.

-Signing: Takes as input a message M and the private key x and produces a signature σ ∈ G 1 as σ = xH(M ).

-Verification: Takes as input a message M , a public key pk and a signature σ.

Checks the equality e(σ, P 2 ) = e(H(M ), pk). If it holds, it returns a succesful verification message.

In the next section we compare the performance of BasicIdent and FullIdent IBE schemes, and we evaluate BLS in contrast to the ECDSA signature scheme. We tested the feasibility of pairing-based algorithms in terms of CPU time, memory and energy requirements for different security levels.

Experimental Results

We conducted our experiments on the Raspberry Pi 3 platform which has a 4 core ARM-Cortex, 1.2 GHz processor, 1 GB Memory and Raspbian GNU/Linux 8 OS. We use the elliptic curves BN 12 and BLS12 from the Barreto-Naehrig and Barreto-Lynn-Scott family, respectively [START_REF] Barreto | Subgroup security in pairing-based cryptography[END_REF]. The curves are defined over a finite field F q and are of the form E/F q : y 2 = x 3 + b with b ∈ F q , embedding degree k = 12 and a sextic twist for faster computations. We provide results for the security levels 78, 112 and 160-bits which are defined in line with the q length. Pairing-based protocols use the efficient Optimal Ate pairing [START_REF] Moody | Report on pairing-based cryptography[END_REF].

Feasibility in our study is expressed in terms of protocols' execution time, memory usage and energy consumption. The statistical evaluation of our results indicates a small standard deviation in case of IBE schemes. Therefore, the corresponding graphs depict mean values. In case of signature schemes, the standard deviation is non-negligible and, thus, both mean value and standard deviation are calculated over 1000 samples. Fig. 2 compares the encryption and decryption algorithms of the BasicIdent and FullIdent protocols' implementation in Relic-Toolkit library.

-Execution Time: In both protocols, encryption is more demanding than decryption, due to the overhead of the exponentiation g r ID in step 4 of Algorithm 1. The hash function H 1 that maps a value to a curve's element also consumes considerable time. It is interesting that the FullIdent protocol is chosen ciphertext secure with almost non time-overhead. Using hash functions and XOR operations it secures the BasicIdent efficiently. A slight deterioration in decryption is owed to the scalar multiplication rP 1 and an equality check in the additive group G 1 . The parameter that has serious impact on time is the security level. Moving from 112 to 160 bits adds around 550 ms in the encryption process and almost 250 ms in the decryption process. This is because pairing computations and scalar multiplications become time consuming in large groups of elliptic curve elements.

-Energy Consumption: Energy consumption is proportional to the execution time, since E = P × T , where P is the power consumption and T is the algorithm's execution time. To obtain this measurement we put a USB detector between the power supply and the Raspberry Pi, and a constant P = 1702 mW was observed due to the protocols' execution. During encryption, lower security levels demand less than 200 mJ, while 160 bit security level increases the energy demands at 1100 mJ for both BasicIdent and FullIdent protocols. Decryption is more efficient, since it requires less than 100 mJ in low security levels and around 500 -600 mJ for 160 bit security. These levels of energy consumption indicate that the execution of protocols is feasible in our platform. -Memory: The main part of the memory being used is reserved for the integration of the Relic-Toolkit library in Contiki. Thus we measured the memory overhead caused by the protocols themselves. We observe that, during the encryption, the FullIdent protocol is more memory-demanding compared to the BasicIdent especially in higher security levels. Both protocols decrease their requirements in decryption below 5 KB. It can be noted that the memory used in decryption seems quite indifferent of the security level.

Fig. 3 compares the signing and verification algorithms of the BLS and ECDSA protocols' implementation in Relic-Toolkit library. Both protocols use elliptic curves, but only BLS is pairing-based.

-Execution Time: BLS and ECDSA exhibit similar performance in signature production. This is also confirmed from Table 1, where mean values and standard deviations have been recorded (due to space limitations similar statistics for verification process are omitted). Signing includes hash functions' computations and scalar multiplications in both protocols. BLS verification is slower due to the calculation of two pairings. Keeping in mind that this process is typically executed in base stations, BLS is a good candidate given the advantage of short signatures which have impact on time and energy transmission. -Energy Consumption: Both protocols demand lower than 20 mJ during signing for low security levels. This raises to 95 mJ for the BLS protocol and to 80 mJ for the ECDSA when the security level ups to 160 bit. Verification by the BLS is more demanding than ECDSA in every security level, with a noticable difference at high security. -Memory: The BLS protocol seems to be memory efficient, since it requires around 3.5 KB and 1.5 KB during signing and verification process, respectively, irrelevantly to the security level. To summarize, all protocols evaluated through experimentation are shown to be feasible in middle-class IoT devices, such as the Raspberry Pi 3. Moreover, pairing-based protocols have features that make them attractive for such devices, e.g., short signatures.

Related Work

There is a large body of work on security and privacy issues for the IoT environment; we refer to [START_REF] Sicari | Security, privacy and trust in the Internet of Things: The road ahead[END_REF] for a survey. Broadly, the Advanced Encryption Standard (AES) is used in association with public-key cryptosystems to provide confidentiality, while elliptic curves' signing schemes are dominating, since an 160-bit ECC key is roughly equivalent to an 1024-bit RSA key. A step forward, our work is motivated by a recent report of the National Institute of Standards and Technology (NIST) about PBC [START_REF] Moody | Report on pairing-based cryptography[END_REF]. Two seminal cryptographic schemes that use pairings on elliptic curves are introduced in 2001; i.e., the Boneh and Franklin's IBE protocol [START_REF] Boneh | Identity-based encryption from the Weil pairing[END_REF] and the BLS short signature scheme [START_REF] Boneh | Short signatures from the Weil pairing[END_REF]. Our work elaborates on the BasicIdent and FullIdent IBE protocols, and the BLS scheme in an effort to experimentally evaluate them on middle-class IoT devices. To the best of our knowledge, this is the first feasibility test of the aforementioned fundamental protocols on the Raspberry Pi 3 platform.

In [START_REF] Szczechowiak | On the Application of Pairing Based Cryptography to Wireless Sensor Networks[END_REF], Szczechowiak et. al explore the application of PBC on Wireless Sensor Networks (WSNs) and their results show that pairings can be implemented in real motes, although at a high computational cost. In a more theoretical approach [START_REF] Mandal | Feasibility of Public Key Cryptography in Wireless Sensor Networks[END_REF], Mandal et al. discuss decisions regarding pairings, arithmetic field, curves and key-size which influence the feasibility of PBC on WSN. A pairingbased protocol for Home Area Networks was proposed in [START_REF] Jacobsen | Towards the use of Pairing-Based Cryptography for Resource-Constrained Home Area Networks[END_REF], while Oliveira et al. introduced the TinyPBC, a WSN authentication scheme based on pairings [START_REF] Oliveira | TinyPBC: Pairings for Authenticated Identity-Based Non-Interactive Key Distribution in Sensor Networks[END_REF]. Private mutual authentication and private service discovery in mobile IoT are addressed in [START_REF] Wu | Privacy, Discovery and Authentication for the Internet of Things[END_REF] and two new protocols are introduced. This work as well as the study of Attribute-Based Encryption (ABE) for access control in IoT [START_REF] Ambrosin | On the Feasibility of Attribute Based Encryption on Internet of Things Devices[END_REF] use pairings as cryptographic primitives and Raspberry platform, among others, as IoT platform for protocols' evaluation.

Conclusions and Future Work

In this paper we evaluated the feasibility of fundamental PBC schemes and concluded that they can be adopted by the IoT resource-constrained devices. We implemented and evaluated the FullIdent IBE scheme in contrast to the BasicIdent. Results show that the overhead of using the extended CCA-secure is negligible. In addition, we compared the BLS short signature scheme with the well-known ECDSA. The BLS algorithm seems to be approximately equivalent to ECDSA in the signing process, while it is more time and energy consuming in the verification process.

Our future work plans include the feasibility study of pairing-based cryptography on low-class IoT platforms, e.g., Zolertia RE-Mote 2 devices, which are resource-constrained. Challenges derived by devices' communication and messages' exchange worth further research. Finally, we plan to evaluate more pairing-based protocols, which according to the bibliography are more efficient because they require a single pairing evaluation during decryption instead of one for encryption and a second for decryption.

Fig. 1 .

 1 Fig. 1. An abstract view of pairing-based cryptography

1 :Algorithm 2 1 :

 121 Compute QID = H1(ID) 2: Choose a random string σ with length l 3: Set r = H3(σ, M ) 4: C = (rP1, σ ⊕ H2(g r ID ), M ⊕ H4(σ)), where P1 is a generator of G1 and gID = e(P pub , QID) ∈ GT . The FullIdent decryption algorithm Input: Ciphertext C = (U, V, W ), entity's private key dID. Output: Message M or Failure message. Compute σ = V ⊕ H2(e(U, dID)) 2: Compute M = W ⊕ H4(σ) 3: Set r = H3(σ, M ) 4: Check that U = rP1. If not, the ciphertext is rejected. Alternatively, the algorithm outputs the message M .

  e(U, d ID ) = e(rP 1 , sQ ID ) = e(P 1 , Q ID ) sr = e(sP 1 , Q ID ) r = e(P pub , Q ID ) r = g r ID

  (a) BasicIdent and FullIdent encryption protocols (b) BasicIdent and FullIdent decryption protocols (c) BasicIdent and FullIdent encryption protocols (d) BasicIdent and FullIdent decryption protocols (e) BasicIdent and FullIdent encryption protocols (f) BasicIdent and FullIdent decryption protocols

Fig. 2 .

 2 Fig. 2. Execution time, memory usage and energy consumption of pairing-based encryption and decryption on the Raspberry Pi 3 platform

  (a) BLS and ECDSA signing protocols (b) BLS and ECDSA verification protocols (c) BLS and ECDSA signing protocols (d) BLS and ECDSA verification protocols (e) BLS and ECDSA signing protocols (f) BLS and ECDSA verification protocols

Fig. 3 .

 3 Fig. 3. Execution time, memory usage and energy consumption of pairings and notpairings signining and verification on the Raspberry Pi 3 platform

Table 1 .

 1 Mean CPU time and standard deviation for signature schemes (msec)

	Security Level Mean BLS Std. Dev. BLS Mean ECDSA Std. Dev. ECDSA
	78	3.189	0.047	3.036	0.233
	112	10.349	0.742	8.0217	0.341
	160	69.252	4.429	54.681	4.322


Riham Elhabyan
email: riham.elhabyan@carleton.ca

Wei Shi
email: wei.shi@carleton.ca

Marc St-Hilaire
email: marc.sthilaire@carleton.ca

Evolutionary-based Coverage Control Mechanism for Clustered Wireless Sensor Networks

Keywords: Sleep Scheduling, Clustering, WSNs

Many clustering protocols have been proposed for Wireless

Sensor Networks (WSNs). However, most of these protocols focus on selecting the optimal set of Cluster Heads (CHs) in order to reduce or balance the network's energy consumption and unfortunately, how to effectively cover the network area is often overlooked. Coverage optimization in WSNs is a well-known Non-deterministic Polynomial (NP)hard optimization problem. In this paper, we propose a Genetic Algorithm (GA)-based Coverage Control Mechanism (GA-CCM) for clustered WSNs. GA-CCM provides an add-on mechanism that is designed to be integrated with any centralized clustering protocol to enhance its energy efficiency. GA-CCM finds the optimal set of active nodes that provides full area coverage and puts the redundant sensors into sleep mode to save energy. Extensive simulations of GA-CCM on 25 different WSNs topologies are conducted. Performance results are evaluated and compared against several well-known clustering protocols as well as a coverage-aware clustering protocol. Results show that GA-CCM always achieves full area coverage while minimizing the redundancy degree and the number of active nodes. To further evaluate the performance of GA-CCM as an add-on to existing clustering protocols, we integrate it with a Particle Swarm Optimization based CH selection protocol (PSO-CH), a comprehensive clustering protocol that considers many clustering objectives. To the best of our knowledge, PSO-CH has the lowest overall energy consumption among well-known clustering protocols. Experimental results show that this integration of GA-CCM to PSO-CH further improves its performance in terms of energy efficiency and packets delivery rate.

Introduction

Wireless Sensor Networks (WSNs) are frequently used, among other applications, in environmental monitoring, industry and disaster management. In these applications, a large number of sensors with limited battery capacity and communication capabilities are usually deployed randomly and in high density in order to observe/measure a certain phenomenon or to detect the occurrence of an event in the network field. Such random and dense deployment is unavoidable due to the hazardous environment, in which WSN application needs to be implemented. Consequently, maintaining connectivity and coverage ratio while maximizing the network lifetime constitutes the biggest challenge on the wide spread of WSNs usage. This is because due to the random and dense deployment of the sensors, there may exist many redundant sensors covering the same area and therefore causing unnecessary energy consumption. Therefore, the intuitive solution is to have a set of sensors activated while keeping redundant nodes in sleep mode periodically. The Optimal Coverage Problem (OCP) in WSNs is defined as finding the smallest number of sensors to monitor the network area while maintaining the coverage ratio requirement of the application. The main approach to solve such problem is to employ sleep scheduling protocols, in which the redundant sensors are scheduled to be asleep/deactivated alternately to minimize the energy consumption, hence, increase the overall network lifetime while meeting the connectivity and coverage requirement. On the other hand, clustering protocols provide efficient methods to achieve energy-efficient communication, namely, connectivity in WSNs. However, most existing clustering protocols overlook this redundant sensors fact. Despite the close relationship between the clustering problem and the sleep scheduling problem, they are studied separately and very few works consider a joint solution for both problems. To enhance the energy efficiency of WSNs, integrated protocols that solve both of these problems are highly recommended. As both of these problems are well-known Non-deterministic Polynomial (NP)-hard optimization problems, Evolutionary Algorithms (EA) can be used to solve such problems.

Contributions of this Paper

In this paper, we propose a GA-based Coverage Control Mechanism (GA-CCM) for clustered WSNs. We assume that the network operating time is divided into rounds and the network is clustered using [START_REF] Elhabyan | Particle swarm optimization protocol for clustering in wireless sensor networks: A realistic approach[END_REF]. In each round, GA-CCM is executed to find an optimal set of active nodes to provide full area coverage. Redundant sensors are put into sleep mode to save energy. The main contributions are listed below:

-We formulate the OCP in clustered WSNs as an optimization problem. Up to our best knowledge, the proposed formulation is the first to consider the OCP problem in a clustered WSN. The proposed formulation ensures that the network area is fully covered by the least number of sensor nodes. To do so, the sub-objective functions of GA-CCM aim at minimizing the sensors' redundancy while balancing the energy consumption of the active sensors to avoid selecting the same set of active nodes in each round. Most importantly, GA-CCM is designed and developed as an add-on mechanism which can be integrated to any centralized clustering protocol in order to achieve a better energy efficiency. -We introduce new ways to assess the level of coverage in WSNs. Most of the previously proposed protocols assume that the number of active nodes and/or the coverage ratio are useful metrics to assess the coverage performance of their proposed protocols [START_REF] Mostafaei | A sleep scheduling approach based on learning automata for {WSN} partialcoverage[END_REF]. The coverage ratio is defined as the ratio of the covered area to the whole network area [START_REF] Wu | p-Percent Coverage in Wireless Sensor Networks[END_REF]. The covered area is calculated as the product of the number of active nodes and the sensing area of each active node. However, these two metrics ignore the overlaps in the sensing areas, hence, do not reflect the real coverage degree. According to the current definition of coverage ratio, two sets of active nodes may result in the same coverage ratio but not necessarily the same redundancy degree, that is defined as the number of sensors monitoring a Point of Interest (PoI).

In this paper, we redefine a new coverage ratio in order to assess the coverage more accurately. Furthermore, we also measure the redundancy degree using different metrics. -Contrary to other coverage protocols, we test and examine the performance of the proposed protocol against other protocols under a more realistic energy consumption model that is based on the characteristics of the Chipcon CC2420 radio transceiver data sheet.

Extensive simulations of GA-CCM on 25 different WSNs topologies are conducted, evaluated and compared against several well-known clustering protocols as well as a coverage-aware clustering protocol. To further evaluate the performance of GA-CCM as an add-on to the existing clustering protocols, we integrate it with the Particle Swarm Optimization based cluster head selection (PSO-CH) protocol, a comprehensive clustering protocol that considers many clustering objectives. It is also known to have the lowest overall energy consumption among well-known clustering protocols [START_REF] Elhabyan | Two-tier particle swarm optimization protocol for clustering and routing in wireless sensor network[END_REF].

Paper Organization

The remainder of this paper is organized as follows: Section 2 presents the related work on clustering protocols and coverage-aware clustering protocols. Section 3 presents the system model. The general design and the problem formulation are provided in Section 4. A detailed analysis of the simulation results is provided in Section 5. Finally, Section 6 concludes this paper.

Related Work

Many probability-based clustering algorithms have been proposed in the literature. In such algorithms, the Cluster Heads (CHs) are elected based on a probability function in a random fashion. Examples of such algorithms include: Low Energy Adaptive Clustering Hierarchy (LEACH) [START_REF] Heinzelman | An application-specific protocol architecture for wireless microsensor networks[END_REF]; Energy Efficient Heterogeneous Clustered (EEHC) scheme [START_REF] Kumar | Eehc: Energy efficient heterogeneous clustered scheme for wireless sensor networks[END_REF] and Multi-hop Overlapping Clustering Algorithm (MOCA) [START_REF] Youssef | Wsn16-5: Distributed formation of overlapping multi-hop clusters in wireless sensor networks[END_REF]. All these algorithms are distributed, self-organized and have low overhead. However, these algorithms have some problems in terms of the form and distribution of the clusters [START_REF] Afsar | Clustering in sensor networks: A literature survey[END_REF]. These algorithms do not consider the residual energy of the sensors. Moreover, the random mechanism of selecting the CHs does not guarantee the selection of the optimal set of CHs [START_REF] Elhabyan | Two-tier particle swarm optimization protocol for clustering and routing in wireless sensor network[END_REF]. This, in turn, will reduce the reliability of these algorithms [START_REF] Afsar | Clustering in sensor networks: A literature survey[END_REF].

In order to select the optimal set of CHs, many research works propose centralized EA-based clustering algorithms. In these algorithms, the Base Station (BS) adopts an EA to find the optimal set of CHs based on a set of predefined objective functions. An Example of such algorithms is the GA-based Clustering (GA-C) algorithm [START_REF] Rahmanian | A novel genetic algorithm in leach-c routing protocol for sensor networks[END_REF] which define one objective function as the minimization of the total distance from cluster members to their respective CHs in addition to the distance from the CHs to the BS. However, GA-C does not consider the energy efficiency of the selected CHs. A PSO-based Clustering (PSO-C) protocol [START_REF] Latiff | Energy-aware clustering for wireless sensor networks using particle swarm optimization[END_REF] defines two objective functions which consider both the residual energy of the sensor nodes and the physical distances between the CHs and their associated cluster members. However, the objective functions are not scaled, hence the final solution is biased towards one of them. Another PSO-based CH (PSO-CH) selection algorithm is proposed in [START_REF] Elhabyan | Particle swarm optimization protocol for clustering in wireless sensor networks: A realistic approach[END_REF]. PSO-CH considers the following properties: the network's energy efficiency, data transmission reliability, and the protocol's scalability. The objective function is defined as the weighted sum of three sub-objectives, each of which is related to the aforementioned properties. The sub-objectives are scaled to avoid any bias.

All the aforementioned clustering protocols focus only on selecting CHs to reduce or to balance the network's energy consumption, without adopting any sleep scheduling mechanism for the redundant sensors. Only a few integrated protocols consider them in a joint way. An example of such protocols is the Coverage-Preserving Clustering Protocol (CPCP) [START_REF] Soro | Cluster head election techniques for coverage preservation in wireless sensor networks[END_REF]. CPCP is a distributed coverage-aware clustering protocol which defines different cost metrics for each sensor. The minimum-weight coverage cost metric is defined such that sensors deployed in densely populated network areas and that has higher remaining energy are better candidates to act as CHs and/or to stay active. The main operation of CPCP depends mainly on the values of activation timers. Although the authors of CPCP recommend the activation time to be proportional to the coverage cost, no specific recommendation is given on how to set this value. CPCP provides an integrated protocol to solve both the clustering and sleep scheduling problems in WSNs, it lacks a redundancy check mechanism and since it is a distributed protocol, there is no guarantee it will find the optimal status of the nodes. PSO-CH is a comprehensive clustering protocol that adopts a realistic energy consumption model and has well-defined objective functions. Experimental results of PSO-CH have proven that it has higher Packet Delivery Rate (PDR) at the CHs and at the same time has low energy consumption. However, PSO-CH lacks a mechanism for detecting the redundant sensors in the network and no sleep scheduling mechanism is adopted to put the redundant sensors into sleep mode.

In this paper, we address the aforementioned concerns by extending the PSO-CH protocol with a sleep scheduling mechanism.

The System Model

We consider a two-tiered WSNs with N sensors randomly and uniformly deployed. There are K cluster heads and 1 BS among N sensors. Each sensor has a unique ID, and the BS ID is 0. In the cluster formation process, each sensor node (including a CH) belongs to only one cluster. We assume that all nodes are stationary after deployment and that the sensors are aware of their location.

The Boolean sensing model [START_REF] Boudaren | New trends in sensor coverage modeling and related techniques: A brief synthesis[END_REF] is assumed in this paper as it is the most commonly used sensing model. In this model, if a point p in the network field is located within the sensing range r of sensor node n, then it is assumed that p is covered/detected by n. The sensing area of n is defined as a disk centred at n with a radius of the sensing range r. In this model, the coverage function, C(n, p), of sensor node n and point p is given by the following equation, where d(n, p) is the euclidean distance between sensor node n and point p:

C(n, p) = 1, if d(n, p) ≤ r 0, otherwise (1)
For the energy consumption model, a realistic model which is based on the characteristics of the Chipcon CC2420 radio transceiver data sheet [START_REF]Texas Instruments: Chipcon CC2420 radio transceiver data sheet[END_REF] is used. The total energy consumed by sensor node n, E n , is calculated as follows [START_REF] Elhabyan | Particle swarm optimization protocol for clustering in wireless sensor networks: A realistic approach[END_REF]:

En = statej Pstatej × tstatej + tr Etransitions (2)
Where statej refers to the energy states of a sensor: sleep, reception, or transmission. P statej is the power consumed in each statej, t statej is the time spent in the corresponding state, and tr is the number of transitions for S. The energy spent in transitions between states, E transitions , is also added to the node's total energy consumption. The different values of P statej and E transitions can be found in [START_REF]Texas Instruments: Chipcon CC2420 radio transceiver data sheet[END_REF].

General Design and Problem Formulation

First, the optimal set of CHs is determined using the PSO-CH protocol described in [START_REF] Elhabyan | Particle swarm optimization protocol for clustering in wireless sensor networks: A realistic approach[END_REF]. Then, the GA-CCM is adopted to solve the OCP in the clustered network. We choose the PSO-CH protocol as it has high PDR at the CHs and at the same time maintains reasonable energy consumption. We refer to the integrated protocol as EA-based Coverage-aware, Clustering Protocol (EA-CCP). The formulation of the OCP in clustered WSNs is given below.

In this paper, we assume that the network area A is divided into M virtual cells. At the start of EA-CCP, the BS constructs a coverage matrix CM that has N -1 rows and M columns as follows, where CM (n, m) = 1 when sensor n,

1 ≤ n ≤ N -1 covers cell m, 0 ≤ m ≤ M and CM (n, m) = 0 otherwise: CM =     CM (1, 1) CM (1, 2) • • • CM (1, M ) CM (2, 1) CM (2, 2) • • • CM (2, M ) . . . . . . . . . . . . CM (N -1, 1) CM (N -1, 2) • • • CM (N -1, M )    
According to the boolean sensing model 1, sensor n is said to cover cell m if the distance between sensor n and cell m is less than the sensing range of sensor n. Unlike other coverage protocols, we measure the distance from the farthest corner of cell m rather than its center to ensure that cell m is totally covered by sensor n.

In GA-CCM , the dimension of each potential solution is equal to the number of sensor nodes in the network minus the BS (i.e., N -1). Let, C i = [X i,1 , X i,2 , X i,3 , ..., X i,N -1 ] be the i th chromosome of the population where each gene, X i,d , 1 ≤ d ≤ N -1 maps the status of the sensor node with the ID n d . Each gene X i,d of chromosome C i is initialized with either 0 to indicate that sensor n d is in inactive mode, or 1 to indicate that n d is in active mode. Due to this problem formulation, GA is used instead of PSO since the velocity and position updates in PSO result in real values.

Each chromosome C i is evaluated as follows: -Create a new coverage matrix U pdatedCM i as a copy of CM .

-Update U pdatedCM i as follows: if

X i,d = 0 then U pdatedCM i (d, m) = 0 for m, 0 ≤ m ≤ M .
-Based on the updated U pdatedCM i , evaluate C i using the below-mentioned objective functions.

In order to save more energy, fewer sensor nodes need to be active during each round. The main approach of GA-CCM to achieve that is to minimize the average number of redundant nodes per cell, avgRedN odes which is calculated for chromosome C i as follows:

avgRedN odesC i = M m=1 N -1 n=1 U pdatedCMi(n, m) M (3)
Furthermore, sensor nodes with higher level of energy are better candidates for activation during each round. Let the number

K = N -1 n=1 X i,
avgRemEnergyC i = N -1 n=1 E(n d ), if X i,d = 1 K (4)
It should be noted that both avgRedN odes Ci and avgRemainingEnergy Ci are not scaled and may lead to values that are not in the same range. This will cause the final objective function to be biased towards one sub-objective. Moreover, it can be very difficult to precisely and accurately select the final objective function weights, even for domain experts [START_REF] Konak | Multi-objective optimization using genetic algorithms: A tutorial[END_REF]. In order to avoid this drawback, each sub-objective is scaled to result in the scaled values sAvgRedN odes Ci and sAvgRemEnergy Ci , respectivly. Therefore, the final objective function to be minimized, assuming each sub-objective is equally important, is expressed as follows:

F itnessC i = sAvgRedN odesC i + (1 -sAvgRemEnergyC i ) (5)
In the case that a CH is set to inactive in C i or that a covered cell becomes uncovered, the final objective function is assigned a high penalty value to narrow the search to optimal valid solutions only.

Simulations and Results

The performance of EA-CCP is investigated against CPCP in terms of the number of active nodes, the minimum, maximum and average number of sensors monitoring a cell, and the coverage ratio. We choose the CPCP for comparison as it can provide full area coverage. Authors of CPCP claim that the minimumweight coverage cost provides the best results where the sensor network has to provide complete (100%) coverage of the monitored area [START_REF] Soro | Cluster head election techniques for coverage preservation in wireless sensor networks[END_REF]. Moreover, the performance of EA-CCP is investigated against CPCP, LEACH, PSO-C, GA-C, and PSO-CH in terms of the average consumed energy per node and the Packet Delivery Rate (PDR). Although LEACH, PSO-C, GA-C, and PSO-CH do not use any coverage control, we choose them for comparison as they are well-known clustering protocols and experimental results have shown that they have high PDR and low energy consumption due to their adapted cluster-based sleep scheduling mechanism [START_REF] Elhabyan | Particle swarm optimization protocol for clustering in wireless sensor networks: A realistic approach[END_REF].

Simulations are carried on Castalia, which is based on the OMNeT++ platform. The simulations are performed on a group of homogeneous sensor networks consisted of 5 different network sizes ranging from 100 to 500 sensor nodes. Overall, the simulation results are averaged over five simulation runs for a total of 25 different playground topologies. Table 1 summarizes the configuration of the network's simulation environment. The CHs selection problem is solved using PSO while the OCP is solved using GA. Table 2 summarizes the configuration of the different EAs parameters.

Coverage Performance

In this section, we compare between CPCP and EA-CCP in terms of their coverage performance. We choose these two particular protocols since they provide a coverage control mechanism and assume that they can provide full area coverage. The results presented in this section represent the average of 5 different runs for 5 different network sizes and for one round of operation. The coverage ratio for both CPCP and EA-CCP is assessed and the results are shown in Table 3. We define the coverage ratio as the ratio of the number of covered cells to the total number of cells. Column 2 in Table 3 shows the coverage ratio before applying any Coverage Control (CC), i.e. before running any of the protocols. Table 3 shows that EA-CCP achieves higher coverage ratio than CPCP. In most of the cases, EA-CCP achieve full area coverage. In the case of 100 nodes, the network area is not fully covered even before applying any CC, as shown in the second column. That is why EA-CCP did not provide full coverage in that case. Although we are assuming uniform sensors deployment, the cell width determines the granularity of the network area. Choosing smaller cell width may have led to higher coverage ratio for both protocols and full coverage in EA-CCP. To assess the redundancy degree, Table 4 shows the minimum (MIN), maximum (MAX) and average (AVG) number of sensors, including the CHs, monitoring a cell for both EA-CCP and CPCP. In Table 4, columns 2, 3 and 4 show the same values before applying any Coverage Control (CC), i.e. before running any of the protocols. In CPCP, the MIN column shows that, in all the networks, there are cells that are not monitored by any sensor. Hence, CPCP fail to provide full area coverage. Moreover, the MAX column shows that there is a high degree of redundancy in monitoring a cell. This degree of redundancy increases as the network density increases. Therefore, the average number of sensors monitoring a cell increases too. On the other hand, EA-CCP shows more stable and consistent performance, regardless of the network density. EA-CCP always succeeded in providing full area coverage and all the cells has at least 1 sensor monitoring it. The reason for the lower value in case of 100 nodes is justified in the results of Table 3. Furthermore, EA-CCP has much lower redundancy degree. Regardless of the network density, EA-CCP has on average around 1 node monitoring each cell. Table 5 shows the average number of active nodes per round (Ns). This number represents both the CHs and other Active Nodes (ANs) involved in the communication. The main operation of CPCP depends mainly on the values of the activation timers. Hence, it is more likely that more than one sensor with the same timer value will announce themselves as CHs at the same time which will lead to a higher number of CHs. These CHs mark their sensing areas as covered areas. In CPCP, the activation stage occurs after the CH selection which leads to activating less number of sensor nodes.

Clustering Performance

Fig. 1 records the average consumed energy per node for the different protocols.

The results presented here represent the average of 5 different runs, for each network size, with a confidence level of 0.99. It can be clearly shown that EA-CCP protocol outperforms the other protocols in terms of energy efficiency. This is due to minimizing the number of active nodes by minimizing the nodes redundancy as illustrated in Tables 5 and4, respectivly. Although CPCP also minimizes the number of active nodes, a higher number of CHs are selected as shown in Table 5. Higher levels of energy consumptions are recorded in CPCP because the CHs stay active for the whole round. Moreover, the decision of whether a sensor will stay active or not in CPCP is not taken at the beginning of the round. This decision could be taken by the node anytime during the round, depending on its activation time. This will lead to unnecessary consumed energy by the redundant nodes who are waiting for their timer to expire to take the decision to be inactive. In EA-CCP, a centralized approach is adopted so each node knows its status at the start of each round. The clustering process in EA-CCP employs the PSO-CH protocol which leads to less number of CHs (5% of network size) and more scalable clusters [START_REF] Elhabyan | Particle swarm optimization protocol for clustering in wireless sensor networks: A realistic approach[END_REF]. The results obtained in Fig. 1 are also confirmed by Fig. 2 which shows the average consumed energy per node for a different number of rounds in case of a 300 sensors networks. Fig. 2 shows that EA-CCP consistently outperforms the other protocols in terms of energy efficiency for different network operation time. Fig. 3 shows the average PDR for the different protocols. The PDR is calculated as the ratio of the total packets received by all the cluster heads against all the packets sent by all the active nodes. Fig. 3 clearly shows that the EA-CCP protocol significantly outperforms the other protocols in terms of PDR. Minimizing the number of redundant nodes enhances the network topology and minimize the network collisions, which in turn enhances the PDR. Although the CPCP also reduces the number of redundant nodes, there are no link quality measures taken when the clusters are constructed. This is also confirmed by Fig. 4 which shows the average PDR for a different number of rounds, when network size is 300. The results Fig. 4 represent the average of 5 different runs for one round of operation, for each network size. Fig. 4 shows that the EA-CCP protocol consistently outperforms the other protocols in terms of the PDR for different network operation time. Both network clustering and coverage optimization can help to conserve energy. In this paper, we propose GA-CCM as an add-on mechanism that can be adopted by any centralized clustering protocol to solve the OCP. Simulation results show that integrating GA-CCM into PSO-CH results in better energy consumption and PDR comparing to other popular clustering protocols. Moreover, the proposed mechanism greatly enhances the coverage ratio, reduces redundancy degree and the number of active nodes.

Fig. 1 .

 1 Fig. 1. Average consumed energy per node for different network sizes

Fig. 2 .Fig. 3 .Fig. 4 .

 234 Fig. 2. Average consumed energy per node for different number of rounds

  d represents the number of active nodes for chromosome C i . The remaining energy ratio for sensor node n with ID d, is E(n d ) = Remainingenergyof n dInitialenergyof n d . Then, the average remaining energy per an active node in chromosome C i is calculated as follows:

Table 1 .

 1 Summary of the WSNs simulation settings for EA-CCP

	Parameter	Value
	BS location	(0,0)
	Data transmission rate 1 packet/s
	Network Size	(100 -500) sensor nodes
	Field size	100 m ×100 m
	MAC protocol	TMAC
	Simulation time	2500 s
	Round length	500 s
	Slot length	1 s
	Initial energy	18,720 J
	Sensing Range	20 meters
	Cell Width	5 meters

Table 2 .

 2 The EAs parameters settings for EA-CCP

	Parameter	Value
	PSO-CH
	Problem dimension (Number of CHs) [5 -25]
	Population size	50
	Number of iterations	500
	Learning Factor c1	2
	Learning Factor c2	2
	Interia weight w	0.9
	GA-CCM
	Problem dimension (Network Size -1) [99 -455]
	Population size	100
	Number of iterations	25000
	Mutation probability, pm	1 / Problem dimension
	Crossover probability, pc	0.9

Table 3 .

 3 Coverage Ratio

	Network Size No CC CPCP EA-CCP
	100	0.999 0.645	0.999
	200	1	0.7365	1
	300	1	0.803	1
	400	1	0.8375	1
	500	1	0.8495	1

Table 4 .

 4 Average number of sensors monitoring a cell

	Network Size	No CC		CPCP	EA-CCP
		MIN MAX AVG MIN MAX AVG MIN MAX AVG
	100	1.2 15.8 7.406	0	5.4 1.5524 0.8 3.2 1.602
	200	3.8 28	14.76	0 10.6 2.5642 1	3.4 1.6307
	300	6.4 37.4 22.09	0 23.8 3.6861 1	3.6 1.6503
	400	9.2 47 29.417 0	28 5.1626 1	3.4 1.6329
	500	12.4 58 36.6315 0 34.6 6.7182 1	3.8 1.7172

Table 5 .

 5 Average number of active nodes per round

	Network Size	CPCP	EA-CCP
		Ns CHs ANs Ns CHs ANs
	100	21.4 15.8 5.6 25.2 5 20.2
	200	30 24.8 5.2 33 10 23
	300	70.2 64.6 5.6 38.2 15 23.2
	400	80.8 75.6 5.2 41.8 20 21.8
	500	95 90.6 4.4 48.6 25 23.6