Keywords: VANET, Routing, Prediction, Malicious, Kalman Filter, DoS

Vehicular environments are vulnerable to attacks because of the continuous interactions between vehicles despite authentication techniques deployed by communication standards. In fact, an authenticated node with a certificate could initiate an attack while complying with implemented protocols if it has malicious intentions and benefit from this always on connection to threaten the network accuracy. Several mechanisms to counter these attacks were proposed but none of them is able to anticipate the behavior of nodes. In the present work, we target this problem by proposing a preventive mechanism able to predict the behavior of vehicles and prevent from attacks. We use Kalman filter to predict the future behavior of vehicles and classify them into three categories (white, gray and black) based on their expected trustworthiness. The main concern of this work is to prevent from the denial of service (DoS) attack. Results, given by the implementation of the proposed mechanism over an intersectionbased routing protocol using ns3 simulator, prove its accuracy regarding the detection rate and a good impact on packets delivery ratio and end-to-end delay.

I. INTRODUCTION

Thanks to the increasing progress of deployed information and communication technologies (ICT) and embedded systems in the automotive sector, a vehicle is being an intelligent mobile agent capable to communicate, sense and autonomously react. This has led to the appearance of the concept of Cooperative Intelligent Transportation Systems (C-ITS) offering several types of services such as safety applications, infotainment and traffic efficiency. Most of these services are based on data collected by vehicles. In fact, each vehicle in the network is able to collect and manage a huge amount of data based on different kinds of embedded sensors. The collected data is of high importance that should be communicated to a remote server in the infrastructure. As a carrier of such relevant data, a vehicle is always attracting the attention and may be exposed to potential attacks [START_REF] Raya | Securing vehicular ad hoc networks[END_REF] that the standardized communications technologies used in cars such as IEEE 1609.2 has left unstudied [START_REF] Lin | Security in vehicular ad hoc networks[END_REF] while proposing their authentication policies.

Although it carry a legal certificate, an authenticated node can threaten the network applications security and initiate attacks with respect to used protocol rules. Several kinds of techniques are proposed to enhance the security aspect of communication technologies and protect the vehicular environment from malicious behaviors and internal attacks. They could be categorized into two types. The first is based on the continuous control of distributed certificates [START_REF] Van Der Merwe | A survey on peer-to-peer key management for mobile ad hoc networks[END_REF] where a Central Authority (CA) uses a so called Certificate Revocation List (CRL) to detect and evict nodes with compromised certificates. These policies are able to detect several kinds of attacks but they need a very high capacity of storage and calculation because the size of a CRL keeps always increasing with the network size which may also lead to additional delays. They were enhanced by the use of some delegated connected road side units (RSU) to manage CRLs and distribute calculation. However, they are still inefficient in intermittent networks lacking connected infrastructures [START_REF] Raya | Securing vehicular ad hoc networks[END_REF]. The second investigated policy is the Intrusion Detection System (IDS) [START_REF] Bhattasali | A survey of recent intrusion detection systems for wireless sensor network[END_REF], which has proven its capability to detect internal and external attacks with a high accuracy while distributing the calculation charge between network nodes. However, all of the proposed policies are reactive techniques based on the actual behavior of the vehicle to decide whether to consider it as malicious or normal and none of them is able to predict its malicious behavior before it attacks. Therefore, we consider, in our actual work, to develop an intrusion prevention and detection approach to predict and detect with high accuracy the malicious behavior of an attacker before the attack. So, we propose a new completely distributed proactive Intrusion Detection System based on Kalman filter [START_REF] Kalman | A New Approach to Linear Filtering and Prediction Problems[END_REF] to predict the trustworthiness of network members, detect suspected attackers using a classification process and inform the rest of the network about that. In fact, we have chosen to consider a decentralized architecture because the availability of infrastructure is not always guaranteed especially in an emergency case which is the aim of the ongoing European project CarCoDe [START_REF]ITEA3-CarCoDe[END_REF]. Therefore, the proposed technique is based on a clustered architecture where a cluster-head (CH) is in charge of the monitoring and classification of vehicles in the appropriate lists (White, Gray and Black). The CH continuously monitors its members, calculates their trust-levels based on its experience with them and received recommendations from other nodes that are carefully chosen and activated to be monitoring agents. Afterward, it estimates the future behavior of each member based on a Kalman filtering process to give three types of lists: White, Gray and Black. We implement our trust-based behavior prediction technique on top of a routing protocol [START_REF] Jerbi | Towards efficient geographic routing in urban vehicular networks[END_REF] using the network simulator NS3.17 and simulation results prove the effectiveness and accuracy of our mechanism regarding its detection rate, packet delivery ratio and end-to-end delay.

The remainder of this paper is structured as follows: Sec- II. RELATED WORK This section is organized into three subsections. In the first one, we summarize some techniques designed to model the trustworthiness of nodes in a vehicular environment. In the second subsection, we present various techniques proposed in the literature for different types of prediction. In the last one, we give an overview about the Kalman filter and its use.

A. Trustworthiness Modeling

Routing protocols are exposed to several kinds of attacks from which DoS (Denial of Service) is the most dangerous one. This type of attack degrades the performances of a protocol by decreasing its packet delivery ratio, increasing the delay of delivery and causes an unfairly use of bandwidth. DoS attack is classified as an internal attack initiated by authenticated vehicles, which makes it very difficult to detect using the most famous techniques based on keys' management and mutual authentications. Other different techniques based on the evaluation of trustworthiness dedicated to the detection of an authenticated attacker are proposed and several trust models have seen light [START_REF] Chen | A trust modeling framework for message propagation and evaluation in vanets[END_REF][9] [START_REF] Chen | Trust management for encounter-based routing in delay tolerant networks[END_REF].

In [START_REF] Chen | A trust modeling framework for message propagation and evaluation in vanets[END_REF] and [START_REF] Zhang | Trust modeling for message relay control and local action decision making in vanets[END_REF], authors propose a trust modeling technique for message relay control and local action decision-making. In this work, they aim to establish a cooperation between vehicles to gather opinions about generated messages for decision making. The collection of opinions from network members is made based on a clustered architecture and two types of decisions are made in the cluster-head: one is based on its own experience with the monitored node and the other is based on aggregated opinions in the received message. The two decisions are later combined to define the behavior of the message generator. In [START_REF] Sedjelmaci | A new intrusion detection framework for vehicular networks[END_REF], a new Intrusion Detection System (IDS) is proposed in which authors introduce a new reputationbased technique to face some types of attacks such as blackhole, warm-hole and resource exhaustion attacks based on the cooperation between different network members. In fact, malicious vehicles are detected and sent to RSUs and then to a central third party to be treated where a decision is made and an information is diffused in the network to eject attackers.

Most of the proposed techniques in the literature are based on trustworthiness evaluation. Although they show good performances in the detection of malicious vehicles, they are still unable to protect network applications because they detect attacks after they happen. Therefore, these studies keep some open issues we aim to face in our ongoing work.

B. Trust Prediction in the literature

Despite the variety of available trust-based techniques, all of them are similar in the fact that they are all reactive mechanisms able to detect an attack after it happens and none of them has the ability to prevent from malicious attacks. So as far as we know, we are among the first to propose a proactive technique in the VANET field able to identify attackers before behaving.

Some proactive mechanisms based on trust modeling are proposed in the literature and are essentially based on either a Hidden Markov Model (HMM) or Kalman filter. In [START_REF] Liu | Modeling context aware dynamic trust using hidden markov model[END_REF], authors consider to treat the problem of trust between agents based on the context of information exchanged between them while proposing an HMM for trust prediction. They based their work on the property characterizing an HMM and consisting on its capability to find the optimal state sequence for a Markov process given the past states/observations. For the definition of the context to consider, they extract a set of features depending on the application type, calculate their entropy and gain and combine them using multiple discriminant analysis. Then, they derive an observation probability based on outcomes of past transactions and their associated transformed feature sets. The work [START_REF] Capra | Autonomic trust prediction for pervasive systems[END_REF] introduces the use of Kalman filtering technique in pervasive systems to autonomously predict trustworthiness of a service provider by a client. The idea is that each client stores services proposed by a provider with their values of quality, then, based on its previous experience it compares the difference between what is promised and what is really provided and assigns a trust value for each provider to be used later for the prediction of its behavior in the next transaction.

In our actual work, we aim to explore the idea of using Kalman filter because it is a lightweight mechanism which doesn't need a big processing power and it offers the possibility of parameters regulation based on the given outputs.

C. Kalman Filter overview

The Kalman filter is essentially based on a set of recursive mathematical functions able to provide an optimal way to estimate the current state of a dynamic system starting from observations that may contain some errors due to the lack of accuracy in the measures provided by connected sensors [START_REF] Capra | Autonomic trust prediction for pervasive systems[END_REF]. Kalman filter is the best linear estimator especially in the case of a Gaussian noise because it minimizes the mean square error of the estimated parameters. To simplify the understanding of Kalman filter, we consider a mono-dimensional system with a state x ∈ IR n (n = 1) and governed by Eq. 1.

x t+1 = x t +V t ,t = 1, 2, 3... (1)
Where x t+1 is the state of the system at time t+1 and it is get by introducing a random Gaussian noise V t to the previously calculated state of the system at time t.

To calculate the state of the system at time t+1, we need to introduce a kind of observations y t that will be periodically made by the system at each time t. But these observations are also subject to a Gaussian noise and depends on the actual state of the system (Eq. 2).

y t = x t +W t ,t = 1, 2, 3... (2)
To determine the best estimate of the next system state, Kalman filter combines the actual known state with the noisy measured observations under the assumptions that noises are Gaussian with covariances Q t and G t consecutively to result these equations(Eq.3 and 4).

x t+1 = x t + ω t /(ω t + G t ) * (y t -x t ) (3)
ω t+1 = ω t + Q t -ω 2 t /(ω t + G t ) (4)
By looking at Eq.3, we can notice that a prediction for the state of the system at t+1 is given by the previously predicted value x t at t augmented by a term proportional to the difference between the prediction and its relative observation given that ω 0 = E[(y 0x 0 ) 2 ]). We can, also, guess from Eq.3 and Eq.4 that the impact of noise on the weight of each term in the estimated value is crucial. If the signal of the noise imposed to the observation (G t ) is high, the impact of this latter is lower than previous estimations and its impact increases when the noise decreases. The same impact could be seen for the noise imposed to the estimate which either increases its impact (low Q t ) or decreases it (high Q t ).

III. NETWORK MONITORING & BEHAVIOR PREDICTION

Various kinds of attacks are identified in the vehicular environment which are either external or internal. The most dangerous attacks are internal because they come from authenticated nodes and could be classified as follows: Resource exhaustion, Packet Alteration, Packet dropping, Denial of Service (DoS)... The main concern of this work is to secure data exchange between moving nodes and prevent from DoS attacks and selfish behaviors. Therefore, a new distributed technique able to monitor network members and predict their trustworthiness and behaviors periodically is proposed. It is based on a clustered hierarchy where a cluster-head observes its neighbor's behaviors based on a Kalman filtering prediction, identifies future attackers and alerts other nodes in the network. However, to make a Kalman filter-based prediction operational, we need two kinds of inputs to have good predictions at the output: The first is a kind of observations made periodically by the system and which will be the trust level calculated by monitoring agents and the second is the previously predicted information. In the following we detail the monitoring architecture with the proposed trust model and used technique for behavior prediction.

A. Monitoring Architecture

Regarding the dynamicity of a vehicular environment, its unique characteristics via the frequently changing topology and lack of deployed infrastructure, it is highly recommended to imagine the worst case where interactions and information exchange between vehicles and central units is not always guaranteed. For this reason, we propose a new completely distributed Intrusion Prevention and Detection System (IPDS) able to monitor the network periodically and continuously, predict the vehicles' behavior and detect malicious ones. The Organization of this architecture passes through three different steps: (i)Bootstrapping phase: At the beginning of the network organization and vehicles categorization, we assume that nodes are authenticated and certificates are distributed. Nevertheless, the possession of a certificate does not guarantee that its holder will not misbehave as indicated before. Therefore, each node in the network has to keep listening to the traffic of its neighbors and gather information to get initial knowledge about them and evaluate their trust levels. So, at the issue of this phase, a trust value is assigned to each node by its neighbors. The bootstrapping phase lasts for a predefined period of time which we fixe in this work and its optimal value will be the aim of a new study. (ii) CH election phase: After the bootstrapping phase, each vehicle knows about the trust levels of others in its vicinity. Therefore, a CH election process is initiated and each node builds a message (CHEAD_MESSAGE(Ip Address, Trust Value)) in which it introduces the address of the neighbor who has the highest trust value with its trust level and diffuses it in its radio range. At the reception of a CHEAD_MESSAGE, one node compares the received trust with the value it has and changes its previous address and the trust value of CH to the new received ones if the newly received trust is greater than the local one and ignores the message if it is not the case. (iii) CH maintenance: The cluster-heads maintenance process is assessed by the CH before getting out from the cluster. In fact, the CH periodically calculates distances separating it from its cluster members, when these distances are higher than a threshold (variable parameter) it has to designate a new CH. The CH, thereafter, sends the address and trust value of the most trustworthy vehicle it has monitored along its leading period to every cluster member. Cluster members update and store the new cluster-head address with its trust level.

As defined above, a Kalman filter is based on previous estimations and periodic observations made by the system. In our case, we are interested to predict the trust level of a neighbor vehicle. So, the monitor node should get observations from its environment about all trust levels of vehicles in its vicinity. In fact, in the network, vehicles are classified into three categories : the first is the cluster-head responsible of the monitoring of all its one-hop neighbors where the prediction and classification mechanisms are activated; it is the decision maker node. The second type of vehicles which could be called "recommenders" are those who are chosen to only monitor their neighbors including the CH, collect their trust information and send recommendations to the decision maker (CH) without making any classification or decision. The remaining nodes are normal vehicles or monitored nodes.

We present here the observations a vehicle has to make to assess a good prediction. These observations could be of two types: (i) the first is the experience-based trust defined in the first subsection and is the only type collected by a recommender and (ii) the second represents recommendations received from other neighbors. Unlike recommenders, a CH has to combine these two types of trusts to make decisions. The total trust T i j defined to be used as an observation for a cluster-head is given by Eq.5 where T R i j is the recommended trust received from recommenders, T P i j represents the experience-based trust and α is a weighting factor.

T i j = α * T P i j + (1 -α) * T R i j (5)
1) Experience-Based Trust: While moving in a network, a vehicle has the possibility to interact and exchange information with every neighbor it has. Therefore, it is able to build a local knowledge about its one-hop neighbors by monitoring their links in a promiscuous mode. This latter allows a node to hear continuously all generated traffic by each neighbor. In our actual work, we are interested to DoS attacks and node selfishness where a vehicle acts selfishly while trying to increase its delivery ratio of data and does not cooperate with others in the forwarding process. So, the monitoring criterion we are using is the traffic generated by each node. In fact, the CH/Recommender analyzes every communication in its vicinity, captures and keeps tracks of all received and sent packets to see if the monitored nodes are not maliciously behaving (cooperating or not). In the experience-based trust calculation, the monitor node periodically evaluates the tracked neighbors' communications and assigns a reputation for each of them, then calculates their trust levels. It verifies if the selected next hop has successively forwarded packets or not and also calculates the number of times the same packet is sent to update trust levels based on Eq.6.

T p i j = Max{R n i j /n, 0} (6)
where R n i j is a reputation value associated to node j by i after n evaluations and calculated as follows:

R n i j = λ * R n-1 i j + (1 -λ) * r n i, j if n > 1 r n i, j if n = 1 (7)
with a r n i, j that could take one of these two values: 1 if the evaluated node is cooperating and -1 in the opposite case based on Eq.9. pdr moy , pdr th and m consecutively represents the average packet delivery ratio, a threshold and the number of neighbors. λ is a weighting factor used to weight the impact of previous calculated reputation on the actual one.

pdr moy = m ∑ k=1 pdr k /m (8) r n i, j = 1 if |pdr moy -pdr j | < pdr th -1 else (9)
Trusts calculated by each recommender are sent periodically to the cluster-head where decisions about vehicles' behaviors are made.

2) Recommendation-Based Trust: To make a wide observation and increase the accuracy of the vehicle's behavior estimation, a CH should collect information about its neighbors and calculate their trusts using the experience-based model if it has direct interactions with them and gather their related trusts from recommenders. The CH calculates, afterward, the average of recommendations (T R ik ) based on Eq.10 to be combined with the local observed trust before triggering the prediction and classification process.

T R ik = ( m ∑ j=1 T i j * T R jk )/m (10)
Where T R jk is the received recommendation for node k from node j, T i j is the total trust calculated by the i th CH to the j th recommender and m is the number of recommenders.

To designate recommenders, two main architectures could be used: the first one is to enable monitoring in all cluster members and make them monitor each others and send recommendations to their relative cluster-heads and the second one is to let the CH choose a limited number of neighbors to be its recommenders. The first technique may generate higher overhead however it is able to increase the decision accuracy about misbehaving nodes because there are more opinions about each node and is also easy to implement. The second architecture needs a good mechanism to choose recommenders and more criteria. Therefore We opt in the actual work for the first technique to collect recommendations about neighbors and we will keep the second technique for a future work.

B. Trust Level Prediction & Classification

A cluster-head is responsible of the estimation of future behavior of its neighbors and the information of other nodes in the network about suspected attacks. The prediction process is based on the Kalman filter described above. To adapt our problem to the basic Kalman filtering technique, let's consider P i j the predicted trust of node j made by the cluster-head CH i , and for an observation we introduce the trust level values T i j gathered by the same CH using the two previously described trust models. So, if we introduce our defined parameters for the trust prediction problem in Eq.3, we get Eq.11 that defines the whole problem. P i j (t + 1) = P i j (t) + (ω(t)/(ω(t) + G(t))) * (T i j (t) -P i j (t))

(11) To increase the accuracy of predicted trusts and face a specific kind of maliciousness where a node behaves normally to win the confidence of its neighbors then switch to malicious mode, we used to make a periodic update of the noise parameters introduced to the prediction and observation G(t) and Q(t). This update is made after a comparison between the prediction and real behavior of the vehicle to either increase the impact of the last observation by decreasing G(t) value or increasing the impact of the previous predictions by decreasing

Q(t) value.
At the end of the prediction process, a CH proceeds for a vehicles' classification according to their trust levels. So, a behavior is associated to each trust value and vehicles are being classified into three different classes using three predefined lists and two thresholds as described below: White list: If a vehicle has P i j ∈]µ, 1], it is considered highly trusted and could be safely used to support VANET applications. Gray list: If the vehicle has P i j ∈]δ, µ], it is considered weekly trusted and used by a VANET application only if there is no white node in the routing table. Gray vehicles may change their behavior in the future. Black list: Contains all vehicles with P i j ∈ [0, δ], which means that they are considered malicious and shouldn't be used in application scenarios.

After the categorization of its neighbors, a CH has to inform other nodes in the network about the suspected behavior of blacklisted nodes. So it builds a so called CDP (Cells Density Packet) packet [START_REF] Jerbi | Towards efficient geographic routing in urban vehicular networks[END_REF] in which it introduces black and gray lists and configures the size of the region to inform. A CDP is forwarded cluster by cluster until reaching the end of the configured region. Each time a vehicle receives a CDP, it updates its black and gray lists and routing table. If this message arrives to a CH, this latter should also add its black and gray nodes into the CDP, informs its neighbors and resends it to the next CH. The whole process is described by Fig. 1.

IV. EXPERIMENTAL RESULTS

We implement our approach using NS3.17 simulator [14] and we conduct simulations (10 times for each value) in a Manhattan Grid area of size 3000*3000m 2 generated using Simulation of Urban Mobility (SUMO) simulator. The main simulations' parameters are summarized in table I. Concerning thresholds for vehicles classification, they can vary and chosen depending on the needed trustworthiness and reliability of the network. If information to be transmitted need a secure and highly trusted environment, their values are increased and vice versa. In our simulations, we set µ = 0.5 and δ = 0.4 after a series of test made by as in different maliciousness degrees which give these values as the most efficient ones. But, we are actually working to design a learning machine to make them more realistic and accurate. For α, we experience various values in our simulations and we find that the value which increases the performances of our prediction mechanism and maintains a good tradeoff between the detection rate and false positives is 0.7. We, firstly, analyze the capability of our proposed mechanism to detect malicious nodes, then, we highlight its impact on the end-to-end delay, delivery ratio and generated overhead in a malicious environment. We highlight, in Fig. 2, the capability of our proposed mechanism to detect malicious vehicles in different maliciousness degrees and various densities in the network (between 10% and 40% of vehicles are malicious for each given density from 100 to 400 nodes). Given results show that the prediction mechanism is able to detect all malicious vehicles independently from the network density in a weakly malicious environment (10% to 20%). However, its detection rate decreases slowly when the number of vehicles increases and the network becomes highly malicious (40% of nodes are malicious). The decrease of detection rate is due to the tendency of malicious vehicles to build false information as they are an important community in the network which make it difficult for a CH to categorize them. But, despite this degradation the number of detected malicious vehicles remains very reasonable even in a high density (above 80% with 40% of malicious nodes in a density of 400 vehicles). This result is achieved thanks to the cooperative detection and prevention between monitoring vehicles. The prediction mechanism shows, also, a good impact on the packet delivery ratio and end-to-end delay. Fig. 3 and4 demonstrate the difference between the basic routing protocol and the one enhanced with a prediction mechanism in the presence of 20 % of malicious vehicles. As we can see, the basic protocol suffers from a higher delay and low delivery ratio in a malicious environment as vehicles do not cooperate to forward data and behave selfishly to only forward their own needed information. However, the proposed prediction technique is able to enhance the performances of the protocol while increasing the delivery ratio and decreasing the endto-end communication delay. Therefore, the proposed schema target to firstly, evict malicious vehicles from the routing tables of data carriers which limit possibilities to be used as packet forwarders and hence minimize dropped packets. Furthermore, the proposed architecture limits the forwarding of packets issued from blacklisted nodes which avoid the bandwidth overload and ease the access to channels and by consequence decrease the end-to-end delay.

The overhead generated by our prediction technique is studied to confirm its higher performance and scalability. Fig. 5 highlights the difference of overhead variation between the basic routing protocol and the secured one. It is clear from plots that the prediction mechanism we have integrated to the protocol does not add a huge amount overhead compared to the basic routing because it uses the same messages to inform network members about malicious behaviors. So, the informing process is the only source of overhead as the black and gray lists are sent and updated from CH to CH and the monitoring process doesn't engender any packet exchange because it relies on a promiscuous mode where one node is only listening to the channel.

V. CONCLUSION

The Vehicular environment is a very active area where a high rate of data is flowing and an important number of transactions between nodes and activities in the road are happening every second. So, a big amount of data is being carried by vehicles which expose them to various attackers aiming to disrupt the network performances despite authentication and certificate distribution techniques proposed by the standard IEEE 1609.2. Several techniques are proposed to detect malicious vehicles and protect the network. But all of them suffer from the same problem that they are not able to detect an attack before it happens. In this paper, we are being the first to propose a new preventive technique able to survey the network and detect malicious nodes before they attack based on their trust levels prediction. For this reason, we deploy the Kalman filter technique together with two trust models to estimate the behavior of vehicles, classify them and evict the malicious and selfish ones. According to our simulation results, we prove that our Intrusion Prevention and Detection mechanism exhibits a high detection rate, low endto-end delay and high delivery ratio. As future work, we aim to enhance our prediction mechanism to detect other types of attacks and design a mathematic model to determine the needed preprocessing period.

Fig. 1 :

 1 Fig. 1: The monitoring architecture

Fig. 2 :

 2 Fig. 2: The Detection rate

Fig. 3 :Fig. 4 :Fig. 5 :

 345 Fig. 3: End-to-end communication delay

  A Distributed Prevention Scheme from MaliciousNodes in VANETs' Routing Protocols Tarek Bouali, Hichem Sedjelmaci and Sidi-Mohammed Senouci tion II gives an overview about the techniques used for trustworthiness modeling in VANETs and some prediction techniques proposed in the literature. Section III presents the monitoring techniques and prediction of nodes' behaviors for classification. Section IV gives a case study to evaluate the performance of the protocol with some discussions. Section V concludes the paper.

TABLE I :

 I Simulation parameters

ACKNOWLEDGMENT

This work has been funded by the European project CarCoDe [6].


Mohamed-Ayoub Messous

Sidi-Mohammed Senouci
email: sidi-mohammed.senouci@u-bourgogne.fr.

Hichem Sedjelmaci
email: hichem.sedjelmaci@orange.com

Soumaya Cherkaoui
email: soumaya.cherkaoui@usherbrooke.ca

A Game Theory Based Efficient Computation Offloading in an UAV Network

Keywords: Mobile Edge Computing, Computation Offloading Problem, Non-Cooperative Game, Pure-Strategies, Unmanned Areal Vehicles (UAVs)

Recently, solutions based on Mobile Edge Computing (MEC) paradigm have been widely discussed in academia and industry. This paradigm offers solutions to address limitations, in terms of battery lifetime and processing power, of mobile and constrained devices. Despite the ever-increasing capabilities of these devices, resource requirements of applications can often transcend what is available within a single device. Offloading intensive computation tasks to a distant server can help applications reach their desired performances. In this work, we tackle the problem of offloading heavy computation tasks of Unmanned Aerial Vehicles (UAVs) while achieving the best possible tradeoff between energy consumption, time delay and computation cost. We focus on a scenario of a fleet of small UAVs performing an exploration mission. During their mission, these constrained devices have to carry-out highly intensive computation tasks such as pattern recognition and video preprocessing. We formulate the problem using a non-cooperative theoretical game with N players and three pure strategies. We provide a comprehensive proof for the existence of a Nash Equilibrium and implement accordingly a distributed algorithm that converges to such an equilibrium. Extensive simulations are performed in order to provide thorough results and assess the performances of the approach compared to three other models. Results show that our algorithm outperforms all the three approaches. Our approach achieved in average about 19%, 58% and 55% better results compared to local computing, offloading to the Edge Server (ES) and offloading to Base Station (BS) respectively.

INTRODUCTION

AVs (Unmanned Aerial Vehicles), aka drones, continue to attract much attention. Initially, relatively demanding calculations, which can be computation-intensive and call for dedicated and powerful processors. At the same time, limited computational power and energy supply present a major challenge for real-time data processing, networking and decision-making; all requirements of vital importance to many applications. Despite the ever-increasing capabilities of UAVs, resource requirements for applications can often transcend what is available within a single UAV. Moreover, performing intensive computation onboard an UAV may result in slow response times, can be detrimental to its battery lifetime, and ultimately can compromise mission success. In order to address issues caused by the limited resources and the intermittent connectivity in UAVs, a cloud-based solution can be adopted [START_REF] Luo | A UAV-Cloud System for Disaster Sensing Applications[END_REF].

Several studies recommend offloading from constrained devices to remote cloud/edge servers [START_REF] Mtibaa | Towards Mobile Opportunistic Computing[END_REF][START_REF] Cuervo | MAUI: Making Smartphones Last Longer with Code Offload[END_REF][START_REF] Guo | Efficient Computation Offloading for Multi-Access Edge Computing in 5G HetNets[END_REF]. In particular, the ability of providing unrestricted computing capabilities at the edge of the access networks for mobile devices, aka Mobile Edge Computing (MEC), is a paradigm that has received increasing attention in academic and industrial communities. Indeed, MEC was revealed as a very promising concept in order to improve network performance as well as user experience. When intensive computation tasks are offloaded to an ES significant performance enhancement can be achieved [START_REF] Ahmed | A Survey on Mobile Edge Computing[END_REF][START_REF] Beck | Mobile Edge Computing: A Taxonomy[END_REF][START_REF] Jararweh | Resource Efficient Mobile Computing Using Cloudlet Infrastructure[END_REF][START_REF] Messous | A Sequential Game Approach for Computation-Offloading in an UAV Network[END_REF]. Existing research works [START_REF] Ahmed | A Survey on Mobile Edge Computing[END_REF][START_REF] Beck | Mobile Edge Computing: A Taxonomy[END_REF][START_REF] Jararweh | Resource Efficient Mobile Computing Using Cloudlet Infrastructure[END_REF][START_REF] Messous | A Sequential Game Approach for Computation-Offloading in an UAV Network[END_REF] considered computation offloading to servers located either in the cloud or at the edge of the access network. The work presented in [START_REF] Jararweh | Resource Efficient Mobile Computing Using Cloudlet Infrastructure[END_REF] suggested using a cloudlet-based infrastructure in order to reduce power consumption and network delay when using mobile cloud computing. Most of the previous studies only consider two choices for the offloading decision: either perform the computation locally or offload it to a distance server. Since computation services can be performed within different U large drone platforms played a prominent role in strategic and defense programs. Recent technological advances have led to the emergence of smaller significantly cheaper UAVs which made them easier to acquire, maintain and handle, thus significantly increasing their usage in civilian applications. Indeed, UAVs proved to be useful in application like rescue missions, target detection, remote sensing, surveillance, service delivery, pollution detection and farming [START_REF] Pajares | Overview and Current Status of Remote Sensing Applications Based on Unmanned Aerial Vehicles (UAVs)[END_REF][START_REF] Ma | Using unmanned aerial vehicle for remote sensing application[END_REF][START_REF] Mozaffari | Mobile Unmanned Aerial Vehicles (UAVs) for Energy-Efficient Internet of Things Communications[END_REF][START_REF] Hossein Motlagh | Low-Altitude Unmanned Aerial Vehicles-Based Internet of Things Services: Comprehensive Survey and Future Perspectives[END_REF][START_REF] Messous | Network connectivity and area coverage for UAV fleet mobility model with energy constraint[END_REF][START_REF] Messous | Implementing an emerging mobility model for a fleet of UAVs based on a fuzzy logic inference system[END_REF][START_REF] Kerrache | UAV-assisted technique for the detection of malicious and selfish nodes in VANETs[END_REF][START_REF] Oubbati | A survey on position-based routing protocols for Flying Ad hoc Networks (FANETs)[END_REF][START_REF] Liu | Space-Air-Ground Integrated Network: A Survey[END_REF]. Drones can carry out exploration missions to replace human presence in areas which are inaccessible or hazardous. They can also deliver data to and from areas with no infrastructure [START_REF] Ma | Using unmanned aerial vehicle for remote sensing application[END_REF]. In fact, thanks to the maturity of their underlying technology, along with their three-dimensional aerial mobility, drones are expected to play an enabler role in emerging networks of the future as aerial base stations to collect/deliver data from/to ground devices [START_REF] Mozaffari | Mobile Unmanned Aerial Vehicles (UAVs) for Energy-Efficient Internet of Things Communications[END_REF].

Even with current advances, research activities are yet to overcome some challenging issues. For instance, UAVs need to detect, classify and identify objects or situations on the spot, in order to be fully operational in surveillance applications. Besides, UAVs are brought to deal with some intensive computation tasks such as video preprocessing, pattern recognition and feature extraction. These kinds of tasks typically require executing complex algorithms and distant sureggate devices (servers), in this work, we intreduce a third choice for addressing the computation-offloading problem. Besides the obvious choice of locally executing a computation task, UAVs in our approach have two possible offloading choices: (i) they can send their tasks to a powerful nearby BS through a wireless local access network (WLAN), or (ii) they can send them to a more powerful server at the edge of the cellular access network (called an ES). The processing of intensive tasks will take place in one of these two remote servers and the execution results are transmitted eventually to their initiator device (UAV). We formulate this kind of decision problem using Game Theory (GT). This analytical tool has been widely used by the wireless networking community for modeling different types of problems [START_REF] Felegyhazi | Game theory in wireless networks: A tutorial[END_REF]. Our objective is to optimize a global utility function, which takes into account a combination of energy consumption, delay and communication cost. We design therefore a solution that achieves the best possible tradeoff between execution time and energy overhead while taking communication cost into account. In a previous work [START_REF] Messous | Computation Offloading Game for an UAV Network in Mobile Edge Computing[END_REF], we proposed a computation offloading game for an UAV network in a mobile edge computing environment. This manuscript presents an extension of our previous paper. In contrast to the previous work, we provide an all-new design for the system model and the problem formulation. We further extend our study to cover a much generic use-case. Furthermore, a non-cooperative game with N players and 3 pure strategies is adopted to model the computation offloading problem. We also give a more comprehensive proof for the existence of equilibrium and the convergence of our distributed algorithm. We performed extensive simulation work, which provided comprehensive results to assess the performances of our approach.

This work addresses the challenges related to real-time applications where the drones are required to do computation-intensive tasks in a short amount of time. We tackle the problem of computation offloading and adopt a decentralized mechanism in which each drone makes the computation offloading decision locally. This can naturally overcome the need to implement a centralized scheme with much overhead compared to a distributed scheme. The main contributions of the present paper are as follow:

•Present a new generic approach for the computationoffloading problem using UAVs in a MEC environment.

•Conceive a non-cooperative game with N players and 3 pure strategies to model this decision problem.

•Design and implement a distributed algorithm, where decisions are made locally without a centralized entity.

The rest of the paper is organized as follows: we first summarize in Section II, research works that influenced our study. We present in Section III the system model and the formulation of our problem. Section IV gives the details of the major contributions of this paper. The simulation work and the results obtained are presented and discussed in Section V. Finally, Section VI concludes the paper and gives some future directions.

GT BASED COMPUTATION OFFLOADING

Mobile and distributed applications are facing a rapid growth in demand on computational and storage resources. Even though, recent technological advances have considerably improved the available resources in mobile devices, they are still not sufficient to meet the ever-growing applications demands. The most important challenges are closely related to energy management and delay minimization. On the first hand, since the energy resource is crucial for mobile devices, its optimal management is vital for network lifetime and to missions' success. On the other hand, the time required to achieve a given task is often very important. This motivated many previous studies to focus primarily on minimizing delay while optimizing energy [START_REF] Rahimi | Mobile cloud computing: A survey, state of art and future directions[END_REF]. The proposed solutions often offload computational demands to more powerful surrogate machines. The most common choice is offloading computation to a neighboring server or even to a distant cloud server through a dedicated communication interface. Such solutions have significantly succeeded in increasing computational capabilities of constrained devices. Nevertheless, overall response times may suffer considerably when many devices attempt to offload their computation tasks simultaneously. This may be primarily due to concurrent access to constrained network resources [START_REF] Hassan | Help your mobile applications with fog computing[END_REF]. The other reason would be the size of data that needs to be offloaded, which can greatly affect transmission time as well as energy, especially for lesser complex computation tasks where it is more efficient to execute locally.

In the following, we gather a set of prominent recent works that used theoretical game methodology to tackle computation offloading problems. [START_REF] Guo | Collaborative Mobile-Edge Computation Offloading for IoT over Fiber-Wireless Networks[END_REF] presented a generic hybrid architecture containing a centralized cloud and a distributed MEC for an IoT environment. The authors defined a computation offloading problem and formulated their solution as collaborative game between mobile IoT devices. Authors in [START_REF] Chen | Decentralized computation offloading game for mobile cloud computing[END_REF] proposed a single wireless channel to access an all-powerful cloud. They used a non-cooperative game model to implement a decentralized algorithm for offloading heavily intensive computation tasks to the cloud servers. The players of this game are all the mobile devices that have a computation task. Each player has two possible strategies: (i) local computing or (ii) offloading to the server. The authors proved the game to be a potential game and proved its convergence. Then, they extended their model in [START_REF] Chen | Efficient Multi-User Computation Of-floading for Mobile-Edge Cloud Computing[END_REF] to a more general use-case scenario with multiple wireless channels and showed that the game remains a potential game.

More recently, other noteworthy ideas were presented in [START_REF] Yu | Optimal Resource Sharing in 5G-enabled Vehicular Networks: A Matrix Game Ap-proach[END_REF], where the authors proposed a new paradigm for vehicular networks in 5G communications environment. The objective was to support data-heavy applications through a mixed-network deployment of small-cells, device-to device (D2D) and heterogeneous networks combined with cloud computing capabilities. Taking advantage of graph theory modeling, the authors demonstrate the distributed nature of their model and the relationship between cloudlets. Furthermore, they formulated a resource allocation problem via a non-cooperation matrix game and solved it though a non-linear concave optimization approach. Authors in [START_REF] Josilo | Selfish Computation Offloading for Mobile Cloud Computing in Dense Wireless Networks[END_REF] consider a dense wireless network where each individual device can offload computations via multiple access points to a mobile cloud in order to minimize their computation costs. The authors provided a game theoretical analysis of this problem while considering the set of players to be selfish. They proved the existence of a pure strategy Nash equilibrium and provided an efficient algorithm for computing an equilibrium point. The obtained simulation results showed that the equilibrium cost was close to optimal. Likewise, authors in [START_REF] Chen | Multi-user Mobile Cloud Offloading Game with Computing Access Point[END_REF] considered a multi-user mobile cloud computing system with a computing access point where each user has multiple dependent tasks to process. Since a centralized optimization solution is non-convex for the problem at hand, the authors formulated the problem as an offloading game in order to minimize the overall energy cost, computation, and the maximum delay among all users. Additionally, they showed the existence of a Nash equilibrium and proposed an algorithm to attain an equilibrium point. Finally, Yu et al. [START_REF] Yu | A D2D-Multicast Based Computation Offloading Framework for Interactive Applications[END_REF] considered a scenario where much duplicated computation tasks are processed on specific mobile users and computation results are shared through D2D multicast channels. The objective was to find an optimal network partition in order to minimize the overall energy consumption for the mobile devices. Consequently, the problem was modeled as a combinatorial optimization problem. Unlike the works mentioned previously, the authors in [START_REF] Yu | A D2D-Multicast Based Computation Offloading Framework for Interactive Applications[END_REF] used a different game theoretic methodology. The proposed solution was implemented using the concepts of coalitional games in order to find a maximum weighted bipartite matching. Simulation results showed a significant decrease in energy consumption while granting fairness among multiple users simultaneously.

In the same context as the related works summarized above, we tackle in our study the problem of offloading highly intensive computation tasks in mobile devices. Furthermore, we take as use-case of a fleet of small UAVs performing an exploration operation. In order to fulfill their missions, the drones are required to compute very intensive computation tasks, such as image processing, feature extraction and pattern recognition algorithms. Since, the small drones have limited computation capabilities and are powered through an onboard battery, offloading their computation tasks to a more powerful distant device would be very interesting. Nevertheless, this solution is not viable for all the possible cases, because transmission delays and the energy required to send data through the wireless medium can hinder performances. Therefore, finding the right tradeoff between energy consumption and delay is very tricky, especially in scenarios with multiple users in which the solution space can increase exponentially. To this extent, we formulate this challenging decision problem using a GT methodology as a dilemma between energy and delay. Besides, we also consider the communication cost as a third decision parameter.

As far as we know, we are the first to incorporate a combination of these three previous decision metrics, namely: energy, delay and cost, within the same utility function while also considering three different strategies rather than just two in solving the computation-offloading problem. In the following sections, we provide the details of our system model. After that, we describe a non-cooperative theoretical game where the fleet of UAVs represents the N players and each of which has three possible different strategies: (i) local computing, (ii) offload to server, and (iii) offload to BS. We prove also the existence of a Nash equilibrium where no player has the incentive to deviate from. Moreover, we design a distributed algorithm with an emerging behavior in order to reach equilibrium.

SYSTEM MODEL AND PROBLEM FORMULATION

All mobile devices use an onboard battery with limited power. Therefore, an efficient management of the available energy supply is vital for the device's lifetime and consequently to the success of its mission. Indeed, these constrained devices are required to make the most of their available resources through their optimal usage. Energy consumption is an even more critical issue when mobile communication is required, where mobile devices need to exchange messages via a wireless channel. In this context, authors in [START_REF] Lee | Mobile Data Offloading: How Much Can WiFi Deliver?[END_REF] have shown that a considerable amount of energy can be saved through the usage of the right communication medium. Subsequently, they argued that since Wi-Fi technology can provide a higher data transmission rate than traditional cellular networks, Wi-Fi would yield a shorter data transmission time and therefore lower energy consumption. However, as recent LTE technology can offer a higher or comparable data rate to Wi-Fi, the energy efficient offloading problem attracts even more research interest, which is particularly true for scenarios with two possible interfaces: LTE and Wi-Fi. Many offloading schemes aiming to improve the mobile devices' energy efficiency are summarized in [START_REF] Cheng | Vehicular WiFi offloading: Challenges and solutions[END_REF]. The most basic idea is to reduce energy consumption used in transmission while granting a bearable average transfer delay. Furthermore, the data traffic would be offloaded through a Wi-Fi access point rather than the cellular network if the difference in transmission energy exceeds a predefined threshold. In a similar context, authors in [START_REF] Wang | Opportunistic WiFi offloading in a vehicular environ-ment: Waiting or downloading now?[END_REF] considered using Wi-Fi to handle the traffic explosion problem in a vehicular net- System architecture work environment. They also consider reducing communication cost using roadside units to convey or download data freely rather than more expensive cellular links. Indeed, the problem of computation offloading is very different from the data-offloading problem. In the latter, the emphasis is on data forwarding towards a distant device, as in [START_REF] Cheng | Vehicular WiFi offloading: Challenges and solutions[END_REF] and [START_REF] Wang | Opportunistic WiFi offloading in a vehicular environ-ment: Waiting or downloading now?[END_REF], while reducing overhead. Whereas offloading computational tasks focus more on the computation and communication delay. However, both approaches try to optimize energy consumption since it is a critical resource for all mobile devices. In this context, our aim in this work is to design an optimal approach for offloading heavy computation tasks to a less constrained device. We consider both energy consumption and time delay in order to provide a comprehensive approach to solve the dilemma of jointly addressing these two criteria.

This section provides the problem formulation and highlights the system model that we have used to implement our computation offloading approach. We consider a set of drones N = {1, 2, ..., n} collocated in the same area of interest (see Figure 1). In order to achieve its mission, each UAV is required to execute a highly intensive and delay sensitive computation task, while preserving its available energy. Different choices are available for these constrained mobile devices. They can either: (i) perform their tasks locally, (ii) offload them via a local wireless connection to a neighboring BS, or finally (iii) through a cellular connection to an ES. The computational tasks that need to be executed are characterized by the number of CPU cycles Ci required to perform the calculation and the size of necessary data Di. Besides the input parameters necessary for the computation, the data to be sent can even include the program code if it needs to be executed remotely.

In the following subsections, we start by presenting the utility function and the different inputs required to compute its values. Then, we show the communication model used by the drones in order to communicate. Finally, we give the details related to the three possible computation models.

Utility Funtion

We defined our payoff function as the combination of energy consumption, delay time and communication cost. Since the vast majority of mobile devices have limited energy resources, the optimal management of this critical asset is quite beneficial for the onboard battery lifetime. Moreover, intensive computation tasks are known to necessitate a considerable amount of time to complete their execution, even with slightly powerful processors. The third entry for our performance metric is the communication cost, which would play a decisive role in choosing a suitable communication interface, because cellular networks are never freely available. Furthermore, cellular operators often charge according to the amount of data transmitted, while Wi-Fi access is perceived as a local network and are mostly free of charge. For these reasons, we implement a global payoff function as a joint equation of: (i) delay overhead, (ii) energy overhead and (iii) communication cost overhead. The resulting function for all the users is given as:

𝑼𝒕𝒊𝒍𝒊𝒕𝒚 = 𝜶 ∑ 𝑻 𝒊 𝑵 𝒊 𝟏 + 𝜷 ∑ 𝑬 𝒊 𝑵 𝒊 𝟏 + 𝜸 ∑ 𝑪 𝒊 𝑵 𝒊 𝟏
(1) Where: N is the number of tasks, T represents Time, E stands for Energy overhead and C is the communication Cost. Additionally, α, β and γ represent respectively the weighting parameters of delay, energy consumption and communication cost, and α+β+γ=1. Moreover, in order to form this global overhead metric, a specific normalization method was adopted in order to be able to add these different measures together. Furthermore, using a weighted function provide a much higher flexibility and answer a wide range of applications with specific requirements. Accordingly, depending on the envisioned application or even the current system status, different tasks can have different weighting parameters. For instance, if the device battery is running low, the value of the weight β should be increased in order to save more energy. Whereas, for a delay sensitive task, the weight α is increased in order to reduce the delay. Finally, the weight γ would to be increased or decreased according to the availability cellular communication offer.

Communication Models

Wi-Fi is the most recognized wireless technology that uses a set of standards for implementing a WLAN communication. It allows an interface between a wireless client and a BS or between two wireless clients. This technology has been widely used in UAV related applications [START_REF] Hossein Motlagh | Low-Altitude Unmanned Aerial Vehicles-Based Internet of Things Services: Comprehensive Survey and Future Perspectives[END_REF] [START_REF] Zhu | Commercial UAV Positioning Use Case[END_REF][START_REF] Fu | Spotlight: UAVs for Disaster Area Communication[END_REF][START_REF] Chen | A triple band arc-shaped slot patch antenna for UAV GPS/Wi-Fi applications[END_REF][START_REF] Cheng | Performance Measurement of 802.11a Wireless Links from UAV to Ground Nodes with Various Antenna Orientations[END_REF]. For instance, [START_REF] Zhu | Commercial UAV Positioning Use Case[END_REF] used Wi-Fi for achieving a flight control with a real-time data such as photo and video transmission between UAVs and devices on the ground. Moreover, authors in [START_REF] Fu | Spotlight: UAVs for Disaster Area Communication[END_REF] have developed an UAV-carried, ondemand Wi-Fi prototype system where the UAV carries the Wi-Fi signal to the emergency areas. While traditional Wi-Fi signal is transmitted around 100 meters, this new prototype for a UAV-carried system can extend the signal up to 25 kilometers using special directional antennas. This line of work supports the feasibility of offering Wi-Fi services through flexible UAV platforms. Another study, presented in [START_REF] Chen | A triple band arc-shaped slot patch antenna for UAV GPS/Wi-Fi applications[END_REF], focused on enhancing Wi-Fi bandwidth for communications between UAV and ground stations. Furthermore, the results of the experimental work in [START_REF] Cheng | Performance Measurement of 802.11a Wireless Links from UAV to Ground Nodes with Various Antenna Orientations[END_REF] showed the viability of using 802.11 interfaces for UAVbased networking.

Since cellular access is widely spread, the small drones shown in Figure 1 are considered to have a cellular network access along with a second 802.11 wireless interface. This latter is used to access the BS while the connection to the ES is achieved through a cellular network (3G/LTE). We denote di∈ {0, 1, 2} as the computation offloading decision for node i. Explicitly, we have di=0 if n chooses to compute its task locally. Otherwise, we would have di=1 or di=2 if it chooses to offload the computation, respectively, to the ES via the cellular network or to the BS via Wi-Fi connectivity. It worth mentioning that if too many devices choose to offload their computation tasks simultaneously, via the same medium, some severe interference may incur. It leads subsequently to low data rates, which would neg-atively affect the overall network performances. In a controlled environment and knowing the decisions of all the mobile devices (d1, d2, ..., dN), it is eventually possible to compute the conceivable data rates for each node. Moreover, communication delay contains the network propagation delay and the data transmission delay. In our case, P, the network propagation delay, is determined by transmission distance, while the data transmission delay is jointly determined by Di, the amount of data being trnsfered, and Ri, the link badwidth.

Computation Model

For the computation aspects of the proposed approach, we consider that each device has one or more computation intensive tasks. Each task Ti is defined through (Ci, Di) which are respectively the number of computation cycles required to achieve a result and the size of data that needs to be forwarded. Data can include the input parameters necessary for the computation and the program code to be executed. The devices have to decide whether to execute their computation tasks either locally or offload them to a remote station. Three possible choices are available and for each of which a different value for the utility function is assumed. The details related to how to compute these values are given in the following paragraphs.

1) Local Computing

Since computation tasks in the "local computing" are executed locally, no actual data ought to be sent via wireless interfaces. Therefore, the utility function would only be impacted by the computation power available in the device, i.e. the CPU frequency which is the number of computation cycles per a time unit. Subsequently, the execution time for a task Ti= (Ci, Di) if the local CPU frequency is F Local CPU is given as:

TLocal=Ci/F Local CPU (2) And as for the expected energy consumption, we would have:

ELocal=Ci*e Local CPU (3) Where e Local CPU is the coefficient value representing the energy consumed per CPU cycle.

2) Offloading to the ES

The first possible offloading approach is to send the computation task via a compatible cellular access network to the ES. This latter will compute the received task instead of the mobile node. Compared to the previous option, the delay or time required to obtain results for the task being executed, in addition to the computation time, will incur an extra overhead. This is due to the additional time necessary to transmit data up to the ES. Therefore, the equation for the time function would be written as:

TServer=Ci/F Server CPU+Di/RCellular (4) Where F Server CPU represents the frequency of the server CPU, which in practice is very big compared to the running frequency for the mobile devices' CPUs. RCellular is the effective data rate achieved through the cellular network as given in section III.A.

When compared to mobile devices, energy resource is abundantly available for the server. So, for the energy cost required to achieve a computation task we only consider the energy required for its transmission to the ES. Thus, the energy function is given as:

EServer=Di*e Server Cellular ( 5) Where e Server Cellular denotes the consumption coefficient required to send one unit of data through the cellular network to the ES.

CServer=Di*c Server Cellular (6) Where c Server Cellular represents the communication cost required to send one unit of data through the cellular network to the ES.

3) Offloading to the BS

The third possible choice and the second offloading approach considered in this work is to offload the computation task through a wireless access point to a nearby BS. This latter would compute the received task on behalf of the mobile node. In this case, the time delay and energy cost are given respectively as:

TBS=Ci/F BS CPU+Di/RWi-Fi (7) and : EBS=Ci*e BS CPU+Di*e BS Wi-Fi (8) Where F BS CPU denotes the CPU's frequency of the BS, RWi-Fi is the effective data rate achieved through the WLAN and e BS CPU measures the energy required to execute one CPU cycle. Finally, e BS Wi-Fi represents the coefficient measuring the energy needed to send one data unit through the available access point network to the BS.

As many previous studies [START_REF] Chen | Decentralized computation offloading game for mobile cloud computing[END_REF][START_REF] Chen | Efficient Multi-User Computation Of-floading for Mobile-Edge Cloud Computing[END_REF][26], we neglect the delay overhead required to send back the computation result to its respective initiator. This is due to the fact that the size of data resulting from an intensive computation task is considered very small and eventually insignificant compared to the size of the input data. This assumption holds for many scenarios such as video processing, feature extraction and pattern recognition algorithms, where the program codes and input parameters size are much bigger than the input data.

In the following sections and using the system model presented above as a guideline, we will develop a decentralized algorithm based on a GT approach for offloading highly intensive computation tasks to more powerful and less constrained network nodes.

GT BASED DISTRIBUTED COMPUTATION OFFLOADING STRATEGY

We tackle throughout our study the issue of implementing an efficient decentralized algorithm for the offloading of heavy computation tasks either to an ES or to a neighboring BS. From the computation and communication models presented in the previous section, it is clear that the decisions made by the drones are highly coupled. This means that each locally made decision will have a direct impact on the other devices evolving in the same system. Furthermore, if a significant number of drones choose simultaneously the same offloading strategy through the same access network, it would have a direct impact on the network performances, which would subsequently affect transmission data rate. Low network throughput would lead to higher transmission delay. Moreover, when the data rate is low, much more energy would be consumed to offload data. In order to get around this issue, it would be more profitable to use another offloading strategy or even choose a local computation. In the aim of achieving the best possible computation offloading decision, we design and implement a decentralized algorithm based on a non-cooperative theoretical game model.

Computation Offloading Game

GT is a powerful tool to analyze the interactions between multiple independent entities that are required to work together in order to achieve their own goals. Using practical examples, authors in [START_REF] Felegyhazi | Game theory in wireless networks: A tutorial[END_REF] have shown how GT can be used as an enabling tool in resolving wireless networking problems. They also summarized the basic notions of non-cooperative games, where the players are the devices in the network. The first reason for choosing GT as an enabling framework for our approach is the decentralized nature of the decision-making process achieved by the network nodes. Since each entity may have different requirements and eventually does not pursue the same interest, a decentralized scheme is required where each player chooses the best possible strategy to achieve its own goals. Thus, decentralized schemes are formulated with low complexity by leveraging the intelligence of each individual device. The other reason is the complexity and viability of implementing a centralized approach. The optimization problem that we are facing is fundamentally difficult. The authors in [START_REF] Chen | Efficient Multi-User Computation Of-floading for Mobile-Edge Cloud Computing[END_REF] proved that the cardinality for this resource allocation problem is similar to the bin-packing problem, which is known to be NP-hard [START_REF] Loh | Solving the maximum cardinality bin packing problem with a weight annealing-based algorithm[END_REF].

In GT, players ought to self-organize into a mutually satisfactory solution such that no player has the incentive to deviate unilaterally. Therefore, it would ease the burden of implementing a more complex centralized system. This mutually satisfactory solution where no player has the incentive to unilaterally change its strategy is called a Nash Equilibrium [START_REF] Li | Computing nash equilibria and evolutionarily stable states of evolutionary games[END_REF]. In order to obtain meaningful insights from our analysis study, we make the common assumption that the number of drones does not change during a mission [START_REF] Jošilo | Selfish Computation Offloading for Mobile Cloud Computing in Dense Wireless Networks[END_REF][START_REF] Sardellitti | Joint optimization of radio and computational resources for multicell mobile-edge computing[END_REF]. Similar to many previous studies dealing with mobile cloud computing [START_REF] Ma | Game-theoretic Analysis of Computation Offloading for Cloudlet-based Mobile Cloud Computing[END_REF] and mobile edge computing [START_REF] Chen | Decentralized computation offloading game for mobile cloud computing[END_REF][START_REF] Chen | Efficient Multi-User Computation Of-floading for Mobile-Edge Cloud Computing[END_REF], we consider a quasi-static scenario where the nodes positions remain unchanged, during a period of time, while they may move throughout different periods.

In this study, we use a strategic form non-cooperative game denoted as µ(N,S,U), which consists of: (i) a finite set of players representing the set N = {1,... N}, where N is the number of drones in the fleet, (ii) Strategy space S, representing the set of actions that each player can take. S= {s1, s2, s3}, (iii) Utility function Ui for each player i. The strategy selected by the UAVj could be either local computing, offload to the ES or offload to the BS. Therefore, Si can be defined as Si= {sj; ∀ j ∈ (0≜ Local computing, 1≜ Offload to server, 2≜Offload to BS)}. The strategies of all the other players excluding UAVi are denoted S-j. The utility function of UAVi represents the overhead generated through one of the previous strategies while taking into account the strategies of all the other players. This is called a strategy profile and is denoted (Sj, S-j). Details about the possible values of Ui are shown in Eq. [START_REF] Liu | Space-Air-Ground Integrated Network: A Survey[END_REF].

In this type of strategic form games, the underlying assumption is that preferences of players are captured through the utility functions, i.e. the strategy profile (s'j, S'j) is more profitable than the strategy profile (sj", S-j") for the player i if and only if Ui'(sj', S-j')>Ui"(sj", S-j"). Moreover, players in our game are assumed to be non-cooperative, such that each player acts independently to improve its own utility function. They are also considered to be rational in the sense that they utilize strategies with better utility. These three assumptions lead eventually to an equilibrium state for all the players called the Nash Equilibrium (NE), where no player has the incentive to deviate unilaterally [START_REF] Abdulla | Toward Fair Maximization of Energy Efficiency in Multiple UAS-Aided Networks: A Game-Theoretic Methodology[END_REF][START_REF] Kumar | Bayesian Coalition Negotiation Game as a Utility for Secure Energy Management in a Vehicles-to-Grid Environment[END_REF].

Nash Equilibrium

In order to achieve a stable convergence state in a noncooperative game, all the players need to reach a common consensus status, namely a Nash Equilibrium. This optimal state represents a stable point where no player has the incentive to deviate from. This means that no player can further improve his utility function by unilaterally changing his strategy. Furthermore, a NE is a strategy profile from which no player can unilaterally deviate and improve its payoff [START_REF] Abdulla | Toward Fair Maximization of Energy Efficiency in Multiple UAS-Aided Networks: A Game-Theoretic Methodology[END_REF][START_REF] Kumar | Bayesian Coalition Negotiation Game as a Utility for Secure Energy Management in a Vehicles-to-Grid Environment[END_REF]. NE represents a stable outcome for a strategic form game. When equilibrium is reached, rational players cannot deviate from this strategy profile. This makes NE one of the most frequently used solution concepts for games. A formal definition is provided below.

Definition 1 (Nash Equilibrium): 𝐴 𝑠𝑡𝑟𝑎𝑡𝑒𝑔𝑦 𝑝𝑟𝑜𝑓𝑖𝑙𝑒 𝑆 * : (𝑠 * , … 𝑠 * )𝑖𝑠 𝑎 𝑁𝑎𝑠ℎ 𝑒𝑞𝑢𝑖𝑙𝑖𝑏𝑟𝑖𝑢𝑚 ⇔ 𝑈 * 𝑠 * , 𝑆 * ≤ 𝑈 𝑠 , 𝑆 * ∀ 𝑖 ∈ 𝑁, ∀ 𝑠 ∈ 𝑆 Where N is the number of players participating in the game, S is the set of the strategies of each player and Ui is the value of the utility function defined in eq. [START_REF] Liu | Space-Air-Ground Integrated Network: A Survey[END_REF].

In order to proof the existence of a NE and eventually the convergence of our game, we resort to the concept of potential games, presented for the first time in [START_REF] Huertacanepa | An adaptable application offloading scheme based on application behavior[END_REF]. Since a potential game has at least one NE solution [START_REF] Chen | Decentralized computation offloading game for mobile cloud computing[END_REF][START_REF] Chen | Efficient Multi-User Computation Of-floading for Mobile-Edge Cloud Computing[END_REF], we can prove whether our offloading game may achieve a NE. Potential games are defined as non-zero-sum games in which the determination of a NE can be equivalently posed as the optimization by all the players of a single function, called a potential function. This latter is used for analyzing equilibrium properties of games because all players' objectives are aligned with a global objective. Furthermore, potential games are special class of theoretical games in which all players' preferences are coupled into the same function. This feature is profitable since it makes potential games easier to analyze and it also ensures the convergence of the game to an equilibrium through simple dynamics. A formal definition for a potential game is given in the following.

Definition 2 (Potential Game): A game µ(N,S,U) is a potential game if there exist a potential function P:S→R such that, for all i∈N, all s-j ϵS-j and sj, s'j ϵSj, Ui (sj, S-j)-Ui (s'j, S-j)) =P (sj, S-j)-P (s'j, S-j) 𝑼 𝒊 𝒔 𝒋 , 𝑺 -𝒋 = 𝑼 𝑳𝒐𝒄𝒂𝒍 = 𝜶 𝑬 𝑳𝒐𝒄𝒂𝒍 + 𝜷 𝑻 𝑳𝒐𝒄𝒂𝒍 + 𝜸 𝑪 𝑳𝒐𝒄𝒂𝒍 , 𝒊𝒇 𝒔 𝒊 = 𝟎 𝑼 𝑺𝒆𝒓𝒗𝒆𝒓 = 𝜶 𝑬 𝑺𝒆𝒓𝒗𝒆𝒓 + 𝜷 𝑻 𝑺𝒆𝒓𝒗𝒆𝒓 + 𝜸 𝑪 𝑺𝒆𝒓𝒗𝒆𝒓 , 𝒊𝒇 𝒔 𝒊 = 𝟏 𝑼 𝑩𝒂𝒔𝒆𝑺𝒕𝒂𝒕𝒊𝒐𝒏 = 𝜶 𝑬 𝑩𝑺 + 𝜷 𝑻 𝑩𝑺 + 𝜸 𝑪 𝑩𝑺 , 𝒊𝒇 𝒔 𝒊 = 𝟐

Now, in order to proof the convergence of our approach, we need to proof the existence of a NE. Since, it has been already proven that every potential game has a NE [START_REF] Chen | Decentralized computation offloading game for mobile cloud computing[END_REF][START_REF] Chen | Efficient Multi-User Computation Of-floading for Mobile-Edge Cloud Computing[END_REF][44], we only need to prove that our game µ(N,A,G) is a potential game.

Proof.

A game G is a potential game if its utility function U can be expressed as a Potential function 𝑃(sj, S-j). This latter is defined as. 𝑃(𝑠 , 𝑆 )-𝑃(𝑠′ , 𝑆′ ) = 𝑈 (𝑠 , 𝑆 )-𝑈 (𝑠′ , 𝑆′ ) 𝑃(𝑠 , 𝑆 ) = 𝑎𝑟𝑔 𝑚𝑖𝑛 ∈ 𝑈 (𝑠 , 𝑆 ) = 𝜓 (𝑆 ); 𝑃(𝑠′ , 𝑆′ ) = 𝜓 (𝑆′ ); Where 𝜓 (𝑆 ) is the best possible payoff for a player i given the strategy profile 𝑆 . It is also defined as a best-response potential game [START_REF] Monderer | Potential games[END_REF], which is equal to Eq. [START_REF] Luo | A UAV-Cloud System for Disaster Sensing Applications[END_REF].

𝝍 𝒊 (𝑺 𝒋 )= ⎩ ⎪ ⎨ ⎪ ⎧ 𝒂𝒓𝒈 𝒎𝒊𝒏 𝒔 𝒋 ∈𝑺 𝒊 𝑼 𝑳𝒐𝒄𝒂𝒍 , 𝒊𝒇 𝒔 𝒊 = 𝟎 𝒂𝒓𝒈 𝒎𝒊𝒏 𝒔 𝒋 ∈𝑺 𝒊 𝑼 𝑺𝒆𝒓𝒗𝒆𝒓 , 𝒊𝒇 𝒔 𝒊 = 𝟏 𝒂𝒓𝒈 𝒎𝒊𝒏 𝒔 𝒋 ∈𝑺 𝒊 𝑼 𝑩𝒂𝒔𝒆𝑺𝒕𝒂𝒕𝒊𝒐𝒏 , 𝒊𝒇 𝒔 𝒊 = 𝟐 (10)
µ(N,S,U) is a potential game since Eq.( 10) satisfies the definition of a potential function and it provides an optimal solution that ensures the best tradeoff between a low overhead and achieving the requested task. Therefore, the NE solution is unique and it is equal to 𝜓 (𝑆 ). In the real experiment, the players choose the strategy that corresponds to the minimum from the three possible values of U:

𝑎𝑟𝑔 𝑚𝑖𝑛 ∈ 𝑈 , 𝑎𝑟𝑔 𝑚𝑖𝑛 ∈ 𝑈
and 𝑎𝑟𝑔 𝑚𝑖𝑛 ∈ 𝑈 .

Decentrelized Offloading Algorithm

The analysis study provided above shows the stable profile for the player's decisions when the equilibrium is reached. Nevertheless, a decentralized algorithm is required to implement our distributed computation-offload-ing scheme and eventually enable the UAVs to attain a mutually satisfactory goal. The main idea behind our algorithm is to use the convergence property reached thanks to the NE theorem presented in the previous section. Since, a finite number of iterations is needed to achieve this plateau status. The decision-making process is executed simultaneously all over the network devices before launching the computation tasks. Similar algorithms have been proposed for cloudlet-based [START_REF] Jararweh | Resource Efficient Mobile Computing Using Cloudlet Infrastructure[END_REF] and mobile cloud computing [START_REF] Chen | Decentralized computation offloading game for mobile cloud computing[END_REF][START_REF] Chen | Efficient Multi-User Computation Of-floading for Mobile-Edge Cloud Computing[END_REF]. To implement the concurrently selfish behavior of the different players, we proposed in our case a simple message exchange protocol. In the latter, each drone initiates a request message to update its status if a better strategy is attainable. Nonetheless, at each iteration, one single update request is approved via an acknowledgment message, so that only one decision is made at a time. The flowchart in Figure 2 summarizes the main steps of the proposed algorithm.

For higher number of nodes, the concurrent nature of our scheme and the number of iterations required to reach the equilibrium might eventually rise a scaling problem, especially in very dense networks. This issue can be handled by adopting a hierarchical multi-tier scheme in order to resolve the contention [START_REF] Rahimi | Mapcloud: mobile applications on an elastic and scalable 2-tier cloud architecture[END_REF]. However, it should be noted that, based on the hypothesis initially presented in the system model section, the proposed scheme as it is currently presented does not suffer from this scaling issue for the following reasons: (i) Only a limited number of UAVs can be used at the same time in the same exploration mission. (ii) In order to offload tasks to the BS, we only consider one wireless access point serving a predetermined number of users in the same region (as shown in figure 1).

EXPERIMENTAL RESULTS AND DISCUSSIONS

We evaluate, in this section, the performances of the approach based on a theoretic game compared to three other strategies: (i) Local Computing, (ii) Offloading to Server, and (iii) Offloading to BS. In the first model, all the computation tasks are executed locally. However, they are offloaded to ES via a cellular access network in the second approach and to the BS via a WLAN in the third approach. We evaluated the system-wide overhead, which is defined in the previous sections as a combination of delay overhead, energy overhead and communication cost. Different scenarios are considered in our simulation while varying each time the possible entries. Specifically, we evaluate the impact of the size of the UAV network on the performances (2, 0, 1) units (RCellular; RWi-Fi) (1; 10) Mbps (eCellular, eWi-Fi) (1200; 1000) units (CostCellular, CostWi-Fi)

(1; 0) unit by changing the number of drones. Furthermore, since the global overhead is directly affected by the size of data that need to be transmitted and the CPU cycles required of computing a task, these two parameters need to be taken into consideration. Therefore, we study also the impact that data sizes and computation cycles may have on the overall overhead. The set of simulation scenarios and the main simulation parameters are summarized respectively in Table I and Table II.

We consider the CPU capability of the ES F Server CPU to be six times more powerful than BS frequency F BS CPU, which is five time more powerful than the local processing frequency F Local CPU available within the drone. As for energy coefficients, we selected realistic parameters similar to those used in the literature [START_REF] Hyytiä | Offload (only) the right jobs: Robust offloading using the Markov decision processes[END_REF][START_REF] Zafari | Optimal Energy Consumption with Communication, Computation, Caching and QoI-Guarantee[END_REF][START_REF] Nazemi | QoI-aware tradeoff between communication and computation in wireless ad-hoc networks[END_REF][START_REF] Balasubramanian | Energy[END_REF]. We consider that sending one data unit to the BS through the WLAN interface eWi-Fi consumes more than computing one CPU cycle locally e Local CPU [START_REF] Nazemi | QoI-aware tradeoff between communication and computation in wireless ad-hoc networks[END_REF]. This latter is twice the energy consumed if the calculation is executed in the BS e BS CPU. As for the energy coefficient of the server, we consider it unlimited, thus e Server CPU= 0. Furthermore, we consider that the use of cellular network to offload data consume 20% more energy than Wi-Fi, therefore, eCellular and eWi-Fi needs 1200 and 1000 units respectively to send a single packet of data [START_REF] Hyytiä | Offload (only) the right jobs: Robust offloading using the Markov decision processes[END_REF] [START_REF] Balasubramanian | Energy[END_REF]. Finally, to introduce the communication cost in our simulation, we consider that Wi-Fi is free (CostWi-Fi=0) whereas cellular network is not (Cost Cellular=1 unit).

The diagram shown in Figure 3 represents the average system wide overhead. It reveals that our approach outperforms the three models in terms of global overhead. This is due to the fact that our model always chooses the most efficient strategy while taking time overhead, energy consumption and communication cost into consideration.

Moreover, in order to investigate the impact of the network size on the model performances, we evaluate scenarios with different number of UAV. The results shown in Figure 4.(a) represent the system-wide overhead achieved, when we vary the network size, through our model compared to the three different strategies. We can notice the continuous growth in the values of global overhead at the same time with the size of the network. This is quite normal, since with the increase of the number of drones, the number of computation tasks increases accordingly, therefore, much more resources are needed which would translate in greater values for the system-wide overhead. Nevertheless, within the same graph, the values achieved through the theoretical game approach were always better than the three other models. We also considered, in our evaluation study, the impact that different computation cycles have on our approach. Thus, we performed new simulations while fixing the number of CPU cycles Ci for each scenario and changing the size of data and the number of drones. We than calculated the average values for the system-wide overhead that correspond to each computation cycles. Results are shown in Figure 4.(b). We can see that the average system overhead achieved through our theoretical game approach outperforms the three other models in all the considered scenarios. The achieved results were even better for highly intensive computation for values that are less than 5x106 CPU cycles. Inversely, offloading to server is more appropriate for highly intensive tasks with more than 10x106 CPU cycles. Between these two intervals, local computing and both offloading strategies achieved closer performances. Furthermore, to evaluate the impact of data sizes that computation tasks need to send, we finally run different simulations with the same data sizes while changing each time the computation cycles and the number of UAVs. Figure 4.(c) shows that the system-wide overhead increases as the data size increases in the two offloading approaches, due to the fact that big data induce high transmission overhead. Nevertheless, system overhead in the theoretical game approach increases slowly when data size increases. This is because more UAVs choose to avoid the heavy cost of offloading via wireless interfaces and compute their tasks locally. In this last case, the size of data has a direct impact on communication cost, communication delay and even the amount of energy required for packet's transmission using the cellular link. Moreover, the local computing approach delivers much better results compared to the offloading strategies for computation task that require transmitting more than 50x103 packets. Whereas, offloading approaches always outperform the local approach when the size of data is less than 25x103packets.

The results shown in the previous figures only provide a unique angle each time. For a more comprehensive analysis of our simulation results, we consider the impact that changing data sizes and computation cycles at the same time may have. This duality is thoroughly examined in Figure 5 and6, where we evaluate respectively the average values of overhead for the different approaches than delay and energy for GT model. Figure 5 confirms that the GT based approach (Figure 5.(d)) clearly outperforms the three other models in terms of average overhead. Furthermore, we notice that values of average overhead in the local computing approach (Figure 5.(a)) are more correlated with the computation intensity of tasks. Consequently, this means that the data size does not have any impact of the overall overhead since tasks do not require to be transferred to a distant device. Whereas, both of the offloading strategies in Figure 5.(b) and Figure 5.(c) are more affected by data sizes rather than the required computation cycles. Nevertheless, since ES has more computation power than BS, CPU cycles have less impact on the overhead when offloading to ES compared to offloading to BS. Whereas, inversely data size influences more transmitting tasks to ES rather than sending data to BS. This is because cellular network consumes more energy compared to Wi-Fi while providing less data rate.

Since the overhead function comprises disjoint parameters, a global overview is still missing. In order to fully examine the performances of the proposed model, we provide even more comprehensive analysis in Figure 6. Specifically, we assess the impact of the GT based approach on the communication and computation time in Figure 6.(a) and its impact on energy consumption in Figure 6.(b). It can be seen that a stronger correlation between computation complexity, expressed in CPU cycles, with average energy consumption and delay compared to data sizes. However, the size of data still has an important impact of the offloading decision. As a summery, we can say that the GT based approach made its offloading decisions based on the

CONCLUSION

Thanks to the recent technological advances, UAVs are currently emerging as versatile nascent paradigm that can be used in exploration and surveillance missions. However, the corresponding span of applications requires very often complex computing in a limited amount of time. Nonetheless, on the one hand, due to the limited computation and energy resources available within UAVs, time delay and energy consumption for these constrained devices are still a major challenge. On the other hand, services and functionalities offered through the concept of mobile edge computing (MEC) provide feasible alternatives to mitigate the issues facing these constrained and mobile devices. In this paper, we consider the problem of offloading highly intensive computation tasks in a fleet of small UAVs to decrease the execution delay while optimizing the energy overhead. We formulate the problem using a non-cooperative theoretical game with N players and three pure strategies, which are: (i) local computing, (ii) offload to an ES, or (iii) offload to a powerful BS. Additionally, we define an all-new utility function that combines energy overhead, computation and communication delays while taking the communication cost into account. We also provide a comprehensive proof for the existence of a NE and implement accordingly a distributed algorithm that converges to such an equilibrium. To gauge the effectiveness of our proposal, extensive experimental work was achieved. Simulation results show that our model outperforms other approaches, provides better performances and significantly reduces the average system-wide overhead.

As future direction to our work, we intend to implement and assess the performances of our computation-offloading approach through a cooperative game. We plan also to further evaluate the impact that the weighting parameters used in our utility function may have on the overall overhead. In the same context, considering a dynamic selection of the weighting parameters, depending on the requirements of each computation task, would make our scheme even more generic and provide additional setting for the final user.

Fig. 1 .

 1 Fig. 1.System architecture

Fig. 2 .

 2 Fig. 2.Computation offloading algorithm

FigFig. 4 .

 4 Fig. 3.Average system-wide overhead

Fig. 5 .

 5 Fig. 5.Systemwide Average Overhead

Fig. 6 .Fig. 6 .

 66 Fig. 6. Evaluation of Average Delay and Average Energy achieved by GT based apporach Fig. 6. Evaluation of Average Delay and Average Energy achieved by GT based apporach

TABLE 1 .

 1 SIMULATION SCENARIOS

	Scenarios UAVs # Tasks Ci Di (α , β, 𝛾)	Inputs [5, ... 50] [5, … 100] (x105) [10, … 200] (x103) (2/5, 2/5, 1/5)

TABLE 2 .

 2 SIMULATION PARAMETERS

	Parameters (F Local CPU, F Server CPU, F BS CPU)	Values (1, 30, 5) GHz

(e Local CPU; e Server CPU; e BS CPU)