Yu Wu
email: yu.wu@utbm.fr

Alexandre Ravey
email: alexandre.ravey@utbm.fr

Daniela Chrenko
email: daniela.chrenko@utbm.fr

Abdellatif Miraoui
email: abdellatif.miraoui@utbm.fr

Demand Side Energy Management of EV Charging Stations by Approximate Dynamic Programming

Keywords: EV charging station, Demand side energy management, Approximate dynamic programming, flexible charging pattern, Multiple types of EV charger

The high operation cost of the EV charging station (EVCS) is a severe challenge for the development of electric vehicles, which lead to the general shortage of the EVCS. In order to reduce the operation costs of the EVCS, an approximate dynamic programming (ADP) based energy management system (EMS) is proposed for the EVCS equipped with multiple types of chargers (EVCS-MTC). A fuzzy logic guiding system has been designed to allocate each vehicle an appropriate charging spot based on its charging urgency. Multiple EVs can acquire the charging service through a common charger in the EVCS-MTC. In the proposed EMS, the approximate dynamic programming (ADP) and the evolution algorithm (EA) are combined to determine the optimal charging start time for each EV. This characteristic provides the charging device with the maximum autonomy to select the preferred flexible charging pattern, which can prolong the battery lifetime and reduce the communication requirements of the control system. With taking the dynamic electricity price and uncertain future charging demand into account, the proposed EMS can achieve a total cost reduction of over 50% compared with the conventional charging scheme in the numerical studies.

the set of the discrete charging cost Cj adp in ADP

Introduction

In the past decade, electrical vehicles (EV) have acquired vast attention as a promising solution to decrease the greenhouse gas emissions incurred by internal combustion engine (ICE) vehicles [START_REF] Pearre | Electric vehicle charging to support renewable energy integration in a capacity constrained electricity grid[END_REF]. With the rapid development of battery technology and electrical powertrain technology, EVs are expected to play a dominant role in the future vehicle market. According to recent market reports of vehicle sales, EV sales around the world have maintained a growth rate of 42% since 2013 [START_REF] Hall | Electric vehicle capitals of the world: Demonstrating the path to electric drive[END_REF]. In the meantime, the battery manufacturing costs have been reduced by 50% over the past 3 years [START_REF] Curry | Lithium-ion Battery Costs and Market[END_REF]. However, the charging infrastructure is still a challenge to the expansion of the EV market. On one side, the shortage of charging facilities is an important factor that restrains the purchase interests of prospective customers. Those EV users without private chargers have to worry about the nearest EV charging facility. On the other side, the construction of tremendous charging facilities requires a large amount of investment costs and daily maintenances [START_REF] Yilmaz | Review of battery charger topologies, charging power levels, and infrastructure for plug-in electric and hybrid vehicles[END_REF][START_REF] Rubino | Review on plug-in electric vehicle charging architectures integrated with distributed energy sources for sustainable mobility[END_REF]. Due to the large investments and blurred expected revenue, the present charging infrastructures are still far from enough [START_REF] Guo | Analysis method and utilization mechanism of the overall value of EV charging[END_REF][START_REF] Godina | Innovative impact assessment of electric vehicles charging loads on distribution transformers using real data[END_REF]. Thus, more EV charging stations (EVCSs) are still needed to provide charging services for the increasing number of EVs. Lots of research has been devoted to reducing the investments and daily operation costs through optimal planning [START_REF] Quoc | Determining the size of PHEV charging stations powered by commercial grid-integrated PV systems considering reactive power support[END_REF][START_REF] Fathabadi | Novel wind powered electric vehicle charging station with vehicle-to-grid (V2G) connection capability[END_REF][START_REF] Xiang | Economic planning of electric vehicle charging stations considering traffic constraints and load profile templates[END_REF] and energy management strategies [START_REF] Fazelpour | Intelligent optimization to integrate a plug-in hybrid electric vehicle smart parking lot with renewable energy resources and enhance grid characteristics[END_REF][START_REF] El-Zonkoly | Intelligent energy management of optimally located renewable energy systems incorporating PHEV[END_REF][START_REF] Shafie-Khah | Optimised performance of a plug-in electric vehicle aggregator in energy and reserve markets[END_REF][START_REF] Panwar | Strategic Energy Management (SEM) in a micro grid with modern grid interactive electric vehicle[END_REF].

The demand-side energy management strategies can be generally classified into two categories: 1) pricing approaches and 2) direct load control approaches. The pricing approaches aim to optimize the energy consumption of multiple demand-side consumers through time-variant electricity pricing. Specifically, the aggregators or EV owners can shift their load according to the announced electricity price mechanism designed by the utility grid, and the total load curves can then be regulated accordingly [START_REF] Hu | Pricing mechanisms design for guiding electric vehicle charging to fill load valley[END_REF][START_REF] Dong | A charging pricing strategy of electric vehicle fast charging stations for the voltage control of electricity distribution networks[END_REF]. However, the pricing strategies usually heavily rely on the communication between the utility grid and the EV users.

Another challenge is the acceptance level of the designed dynamic electricity prices for EV users, who are supposed to cooperate with the time-variant dynamic price signals. This certainly requires self-discipline from the EV users. Meanwhile, the direct load control strategies coordinate the energy consumption by directly modulating the EV charging power. Many studies have been conducted with the aim of reducing the operation costs and satisfying the charging demand of EV users.

Linear programming is a widely used optimization technique for the scheduling problem of EV charging.

In [START_REF] Jin | Optimizing electric vehicle charging: A customer's perspective[END_REF], an linear programming based charging scheme was proposed to minimize the total charging cost of EVs, while a fuzzy linear programming based bidding scheme was used in [START_REF] Ansari | Coordinated bidding of ancillary services for vehicle-to-grid using fuzzy optimization[END_REF] to maximize the ancillary service revenue of EV aggregators. In [START_REF] Xu | Coordination of PEVs charging across multiple aggregators[END_REF], Xu et al. proposed a hierarchical control strategy for multiple EV aggregators in a time of use (TOU) price market. Here, linear programming was used to minimize the total electricity cost and reduce the power peak, and then the charging power of each EV was decided by a heuristic algorithm.

As an extension of linear programming, a mixed integer linear programming model was developed for the charging and reserve scheduling of an EV parking lot with renewable generations in [START_REF] Honarmand | Integrated scheduling of renewable generation and electric vehicles parking lot in a smart microgrid[END_REF][START_REF] Thomas | Optimal operation of an energy management system for a grid-connected smart building considering photovoltaics' uncertainty and stochastic electric vehicles' driving schedule[END_REF], while a day-ahead bidding and scheduling of EV fleets was proposed in [START_REF] Deforest | Day ahead optimization of an electric vehicle fleet providing ancillary services in the Los Angeles Air Force Base vehicle-to-grid demonstration[END_REF]. In order to deal with the uncertainties of EV behaviors, and the electricity price market, some stochastic linear programming based models were developed in [START_REF] Shafie-Khah | Optimal trading of plug-in electric vehicle aggregation agents in a market environment for sustainability[END_REF][START_REF] Guo | Two-Stage Economic Operation of Microgrid-Like Electric Vehicle Parking Deck[END_REF]. However, this kind of stochastic linear programming models depend on sufficient application scenarios to improve the optimization precisions, which significantly increases the computation burden and limits their applications. Furthermore, in order to achieve a faster charging speed and maintain a constant charging power for the EV batteries, in [START_REF] Yao | A Real-Time Charging Scheme for Demand Response in Electric Vehicle Parking Station[END_REF] Yao et al. proposed a binary optimization model to obtain a near-optimal on-off charging strategy in which the linear programming based model was solved through a convex relaxation method. Here, the on-off charging of EV batteries was enabled, since it was suggested in [START_REF] Huang | Matching EV Charging Load with Uncertain Wind: A Simulation-Based Policy Improvement Approach[END_REF][START_REF] Tushar | Smart microgrids: Optimal joint scheduling for electric vehicles and home appliances[END_REF] that constant charging power can prolong the batteries' service time and achieve a faster charging rate. Quadratic programming (QP) was used to minimize the overall load variance in a regional micro-grid in [START_REF] Jian | A scenario of vehicle-to-grid implementation and its double-layer optimal charging strategy for minimizing load variance within regional smart grids[END_REF], while a decentralized charging protocol based on QP was used to achieve the valley filling for the grid operators in [START_REF] Zhang | Coordinating plug-in electric vehicle charging with electric grid: Valley filling and target load following[END_REF]. A real time energy management of EV charging station equipped with local generations was proposed in [START_REF] Wu | A Real Time Energy Management for EV Charging Station Integrated with Local Generations and Energy Storage System[END_REF], where the energy gap between EV power demand and the local generations was minimized through QP.

To obtain more flexibility in the control strategies (multiple platform support, solving some non-linear formulations), some heuristic optimization models were investigated in studies [START_REF] Hansen | Heuristic Optimization for an Aggregator-Based Resource Allocation in the Smart Grid[END_REF][START_REF] Liu | A Heuristic Operation Strategy for Commercial Building Microgrids Containing EVs and PV System[END_REF][START_REF] Jian | High efficient valley-filling strategy for centralized coordinated charging of large-scale electric vehicles[END_REF]. In [START_REF] Liu | A Heuristic Operation Strategy for Commercial Building Microgrids Containing EVs and PV System[END_REF], a heuristic charging strategy for commercial buildings containing photovoltaic (PV) and EV system was proposed, where the EV charging rate was adjusted according to the variation of PV generation and the charging priority of each EV. Similarly, in [START_REF] Jian | High efficient valley-filling strategy for centralized coordinated charging of large-scale electric vehicles[END_REF], a centralized heuristic charging strategy was proposed to achieve the valley-filling for large-scale EVs. Meanwhile, some meta-heuristic based optimization methods were investigated in [START_REF] Yang | An improved PSO-based charging strategy of electric vehicles in electrical distribution grid[END_REF][START_REF] Su | Computational intelligence-based energy management for a large-scale PHEV/PEV enabled municipal parking deck[END_REF][START_REF] Ghofrani | Optimal charging/discharging of grid-enabled electric vehicles for predictability enhancement of PV generation[END_REF][START_REF] Tan | Integration of plug-in hybrid electric vehicles into residential distribution grid based on two-layer intelligent optimization[END_REF][START_REF] Lausenhammer | Utilizing capabilities of plug in electric vehicles with a new demand response optimization software framework: Okeanos[END_REF]. Particle swarm optimization (PSO) is used to minimize the power grid cost and maximize the EV users' satisfactions in [START_REF] Yang | An improved PSO-based charging strategy of electric vehicles in electrical distribution grid[END_REF], while a PSO-based EMS was developed to determine the optimal charging power in [START_REF] Su | Computational intelligence-based energy management for a large-scale PHEV/PEV enabled municipal parking deck[END_REF]. In [START_REF] Ghofrani | Optimal charging/discharging of grid-enabled electric vehicles for predictability enhancement of PV generation[END_REF], a Monte Carlo simulation based PSO was used to optimize the V2G capacities of EVs. In [START_REF] Tan | Integration of plug-in hybrid electric vehicles into residential distribution grid based on two-layer intelligent optimization[END_REF], a two-layer evolution strategy PSO was developed to reduce the power peak and provide frequency regulation services. Elsewhere, a game-theoretic based framework was designed for multiple agents of EVs, in which the PSO technique was used to reach the game equilibrium [START_REF] Lausenhammer | Utilizing capabilities of plug in electric vehicles with a new demand response optimization software framework: Okeanos[END_REF]. However, while the heuristic control strategies have the advantages of more flexibilities and easier implementation, they are generally designed for specific applications, and thus their versatility has been weakened to some extent. Dynamic programming (DP) is notable for its global optimality, despite the rapidly growing computation burden with the number of system state variables. In [START_REF] Škugor | Dynamic programming-based optimisation of charging an electric vehicle fleet system represented by an aggregate battery model[END_REF], a DP optimization method was proposed for the EV fleet charging, where the computation burden was reduced through the designed aggregate battery model. In [START_REF] Škugor | A bi-level optimisation framework for electric vehicle fleet charging management[END_REF], a bi-level optimization framework was proposed for an EV fleet, where the inner loop calculated the optimal charging power based on DP, and the outer loop utilized a multi-objective GA to decide the final SOC. In order to effectively relieve the high computation issue of the conventional DP, approximate dynamic programming (ADP) was developed to overcome the "dimension curse" issue of DP, and the system uncertainties can be also addressed through the approximation modelling [START_REF] Powell | Approximate Dynamic Programming I: Modeling[END_REF]. In [START_REF] Zhang | Optimal Management for Parking-Lot Electric Vehicle Charging by Two-Stage Approximate Dynamic Programming[END_REF],

a two-stage ADP framework based charging strategy was proposed to determine the optimal charging energy amount for each EV at each time slot. Elsewhere in [START_REF] Keerthisinghe | Energy management of PV-storage systems: ADP approach with temporal difference learning[END_REF], an ADP based home energy management system was proposed to achieve the optimal scheduling and the demand response of the house energy consumption and the local PV generations.

Although many of the previous studies successfully managed the charging scheduling problem incorporating different scenarios, an important fundamental issue still arises from the deficiency of EV chargers versus the rapidly growing number of EVs. However, the aforementioned studies generally assumed that the installed EV chargers would be sufficient for the incoming EVs, and the proposed EV charging scheduling strategies were designed for the single charger single cable charging spot (SSC). In this paper, the authors have developed an ADP based EV charging strategy for the intelligent parking lots with multiple types of EV chargers, including the SSC and the shared chargers (i.e. single charger with multiple cables, SMC [START_REF] Zhang | Optimal Planning of PEV Charging Station with Single Output Multiple Cables Charging Spots[END_REF][START_REF] Mouli | Comparison of system architecture and converter topology for a solar powered electric vehicle charging station[END_REF]). Compared to the widely used single charger single cable charging spot (SSC), the shared charger includes one charger with multiple cables which can be accessed by multiple EVs. From the view of investment efficiency, shared chargers have a higher utilization rate and lower initial investment cost, which can make them advantageous to install in official or residential parking lots. In [START_REF] Van Der Meer | Energy Management System With PV Power Forecast to Optimally Charge EVs at the Workplace[END_REF][START_REF] Mouli | Integrated PV Charging of EV Fleet Based on Energy Prices, V2G and Offer of Reserves[END_REF], mixed integer linear programming based EMSs were investigated for the parking lots equipped with shared chargers and PV panels, where two shared chargers with six EVs were studied. However, the limited scalability and the interruptible charging process could become barriers to their engineering application.

Another aspect that is seldom mentioned in the related existing research is the charging autonomy at the device level. Specifically, a constant power charging pattern was suggested to prolong the batteries' lifetime in [START_REF] Yao | A Real-Time Charging Scheme for Demand Response in Electric Vehicle Parking Station[END_REF][START_REF] Huang | Matching EV Charging Load with Uncertain Wind: A Simulation-Based Policy Improvement Approach[END_REF][START_REF] Tushar | Smart microgrids: Optimal joint scheduling for electric vehicles and home appliances[END_REF], whereas in [START_REF] Rahimian | Maximizing the Life of a Lithium-Ion Cell by Optimization of Charging Rates[END_REF][START_REF] Rahimian | Optimal charge rates for a lithium ion cell[END_REF], the charging current was designed as a function of cycle number to maximize the lifetime of lithium battery. In [START_REF] Sikha | Comparison of the capacity fade of Sony US 18650 cells charged with different protocols[END_REF], a varying current decay charging pattern was developed to obtain a faster charging speed and lower capacity fades of lithium batteries. In [START_REF] Liu | Multi-objective optimization of charging patterns for lithium-ion battery management[END_REF], a multi-objective optimization approach was developed to obtain the feasible charging pattern with considering the temperature variations.

Though different charging patterns were developed to enhance the battery performance and the lifetime in the abovementioned studies, the common point is that they all require the charging autonomy at the device level [START_REF] Zhang | Optimal decentralized valley-filling charging strategy for electric vehicles[END_REF]. This means that it is preferable that the instantaneous charging power of EV is determined by the battery management system (BMS) of EVs (or the local charging device) rather than the upper level EMS.

However, most of the direct load control strategies introduced in the aforementioned studies require controlling the charging rates or the on/off charging states of each EV directly, which could not guarantee the charging autonomy at the device level.

In this work, an ADP based EMS is developed for the EV charging station with multiple types of chargers (EVCS-MTC). The constraints of shared chargers and the stochastic nature of EV behaviors will be also considered. The proposed EMS only determines the optimal charging start time of each EV rather than controlling the on-off charging states or the charging rates. This characteristic provides the maximum charging autonomy at the device level. One obvious advantage over some other studies is that, it can avoid the significant fade of battery capacity due to the intermittent charging/discharging process [START_REF] Peterson | Lithium-ion battery cell degradation resulting from realistic vehicle and vehicleto-grid utilization[END_REF]. Another merit of this strategy is that, it appears more practical to be implemented in smart charging applications, where the instructions of the charging power amount are generally obtained from the BMS of EV (or the local charging device) instead of the charging station [START_REF] Hannan | State-of-the-Art and Energy Management System of Lithium-Ion Batteries in Electric Vehicle Applications: Issues and Recommendations[END_REF]. Moreover, since only the charging start signal is required during the charging process, the communication burden of the control system can be vastly reduced.

This paper is organized as follows. Section II introduces the EV charging station equipped with multiple types of charges (EVCS-MTC). Section III introduces the overall energy management system (EMS) framework and the designed fuzzy logic guiding system. In Section IV, a myopic charging scheme is developed to deal with the optimal scheduling of current EVs, and then the ADP-based EMS is proposed to obtain the global optimal charging policy in consideration of the future charging demand. Finally, in Section V, numerical case studies of the EVCS in residential and workplace parking lots are conducted. The uncoordinated immediate charging scheme is used as the benchmark to prove the effectiveness of the proposed EMS. Besides, comparative studies between the EVCS with pure SSC systems (EVCS-SSC) and the EVCS-MTC are conducted. In Section V, the conclusions of this paper are drawn, as well.

EV Charging Stations with Multiple Types of Chargers

Different types of charging facilities are reviewed in this section, including the single charger single cable system (SSC), the multiple charger multiple cables system (MMC), and the single charger multiple cables system (SMC), as shown in Figure 1. Then, the scheduling problem of the EVCS-MTC is presented.

Comparison of Different Types of Charging Spots

An EV charger is usually comprised of three parts: a power converter, a cable, and a socket-outlet. Among these components, the power converter is the most expensive, due to its complicated structure and numerous semiconductor devices [START_REF] Yilmaz | Review of battery charger topologies, charging power levels, and infrastructure for plug-in electric and hybrid vehicles[END_REF]. Generally, three types of charging systems can be found in the EV parking lots, including the single charger single cable system (SSC), the multiple chargers multiple cables system (MMC), and the single charger multiple cables system (SMC), as shown in Fig 1 . The SSC system is designed to charge an EV individually, whereas the MMC system can charge several EVs simultaneously. Since the MMC utilizes multiple power converters and cables to achieve multiple EV charging (Fig. 1b), it can be regarded as a combination of several SSC. Thus, their investment costs are approximately the same. Different from the SSC or the MMC, the SMC achieves multiple EV charging through a single power converter and multiple cables (Fig. 1c), which means that multiple EVs can share one power converter during their parking time in sequence [START_REF] Zhang | Optimal Planning of PEV Charging Station with Single Output Multiple Cables Charging Spots[END_REF][START_REF] Mouli | Comparison of system architecture and converter topology for a solar powered electric vehicle charging station[END_REF].

Problem Statement

In this paper, the authors consider an EV charging station incorporating both SSC and SMC, which is suitable to be installed near residential communities or work sites. The EVs with relative short parking time can be charged at SSC, while the EVs with relative long parking time can be charged at SMC. While the SMC system (the shared charging spot) takes the advantage of low initial investment, it suffers from the issue of charging time conflict [START_REF] Zhang | Optimal Planning of PEV Charging Station with Single Output Multiple Cables Charging Spots[END_REF]. When multiple EVs share one charger in sequence, the total charging time can occasionally exceed the total parking time. This will lead to inevitable charging time conflicts. The operation cost of an EVCS can be formulated as follows:

𝐶𝑜𝑠𝑡(𝒙 𝒊 )= 𝑃 • 𝑎 • ∆𝑡 ∆ + 𝑒 (𝑥 ) • 𝑎 (1) ∆𝑥 ≈ (𝑆𝑂𝐶 -𝑆𝑂𝐶 ) • 𝐶 𝜂 • 𝑃 (2)
where xi is the charging start time of EVi, n ev is the total EV number, Δxi is the estimated charging time of EVi, at is the real time electricity price, 𝑒 (𝑥 ) is the unsatisfied energy of EVi, a p is the penalty price of the unsatisfied energy demand. SOC f is the target SOC value set by the EV owner, SOCi is the initial SOC value of EVi, 𝐶 is the EV battery capacity, P ev is the average charging power of EV , 𝜂 is the charging efficiency.

Here, the average charging power 𝑃 is used to estimate the required charging time, while the real time charging power pattern is decided by the EV battery management system (BMS) or the local charging device.

Thus, the following aspects are considered in the formulated scheduling problem of EV charging: 1) The physical constraints of EV chargers (e.g. multiple EVs share an SMC in sequence). 2) Continuous charging process of each EV (to ensure the charging pattern autonomy at the device level). 3) Minimizing the total operation cost of the EVCS.

System Framework

Overview of the Energy Management System

In order to reduce the operation costs of the EV charging station, an ADP based energy management system is proposed for the EVCS-MTC, as shown in Fig. 2. Firstly, a fuzzy logic based guiding system has been designed to allocate the EV to its specific charging spot. With the designed fuzzy logic controller, each EV can be coordinately allocated to the corresponding charging spot according to its urgency levels.

Secondly, after connecting to the corresponding charger, the EV will be controlled to charge from the optimal start time based on the designed EMS. Fig. 2. The proposed control system of EV charging stations

Fuzzy Logic Allocation System

The charging station has different types of charging spots, while the EVs have different levels of charging urgencies (different parking time and charging demand). In this section, a fuzzy logic based guiding system has been designed to lead the EV to the appropriate charging spot. Firstly, the authors design a laxity index 𝐿 to represent the charging urgencies of different EVs in (3):

𝐿 = 𝑡 -∆𝑥 ∆𝑥 , 𝑡 = 𝑡 -𝑡 ( 3
)
where 𝑡 is the parking time of EVi, 𝑡 is the departure time, and 𝑡 is the arrival time EVi. The laxity index 𝐿 is defined as the ratio of the estimated charging time ∆𝑥 and the "laxity time" (𝑡 -∆𝑥 ). The larger value of Li means that the EVi has more flexibility to be controlled by the EMS. The membership functions of laxity index Li, SOC, and the charging priority index are defined in Figure .3, where the membership functions of each variable are classified into three groups (L, M, and H) respectively.

The corresponding fuzzy rules are depicted in Table I. With the designed fuzzy logic controller, the priority index 𝜌 of EVi can be obtained accordingly, which has been finally normalized to [0, 1]. Further, in order to evaluate the charging speed capability of different chargers in a quantitative way, a speed index 𝑆 is defined in (4~5). The index has a negative correlation with the cable number 𝑁 and the charging demand index 𝑀 .

𝑆 = 1 + 𝑒 𝑁 (4) 𝑀 = ∆𝑥 𝑡 (5)
where the 𝑆 is the charging speed index of the charger j, 𝑁 is the cable number of jth charger, Mj is the demand index which is used to represent the current charging demand amount. The defined index 𝑆 ensures that, an EV charger with fewer cables and less charging demand will have a higher value of 𝑆 .

𝛺 = {𝑐ℎ𝑎𝑟𝑔𝑒𝑟[1], … , 𝑐ℎ𝑎𝑟𝑔𝑒𝑟[𝑛 ]} (6) 𝑁 = [𝜌 • 𝑛 ] (7)
Finally, all the available chargers can be ranked from small to large according to the index 𝑆 , forming a set Ωch of quantity nt c in [START_REF] Guo | Analysis method and utilization mechanism of the overall value of EV charging[END_REF]. The new EV arrival will be allocated to the 𝑁 𝑡ℎ charging spot [START_REF] Godina | Innovative impact assessment of electric vehicles charging loads on distribution transformers using real data[END_REF]. The allocation process is illustrated with details in Algorithm 1.

Algorithm 1 Fuzzy-logic Allocation Algorithm

Step 1. Detecting new EV arrivals 1a. Collect information of new EV arrivals, record the SOC state and calculate the laxity index according to (3).

Step 2. Obtain the priority index of each EV 2a. Input the laxity value Li and the battery status SOCi of EVi into the fuzzy logic controller.

2b. Obtain the priority index value ρi of EVi from the fuzzy logic controller.

Step 3. Collect information of the available chargers with idle cables. Rank all the chargers based on speed index from small to large according to (4~6), and finally constitute the set Ωch of quantity nt c .

Step 4. Dispatch the new EV arrival to the corresponding charger. Specifically, the EV will be allocated to [ρi*nt c ]th charger.

Optimal Charging Strategy

In this part, a myopic charging scheme is firstly designed to achieve the optimal economic charging with the information of current EVs. In order to decrease the time conflicts of SMC and take the future charging demand into account, an approximate dynamic programming (ADP) based charging scheme is further developed.

Myopic charging scheme

The myopic charging scheme is a kind of greedy strategy based on the current information, which is referred to the here-and-now decisions. In this scheme, the optimal charging start time of the EV depends on the lowest electricity price intervals within the scheduling horizon, neglecting the impact of these decisions on the future. Specifically, the EVs are controlled to be charged during the lowest electricity price intervals with the corresponding constraints (8b~8d). A minimization problem is formulated for a single charging spot in formula (8a):

min 𝐶 (𝑥 ) = 𝑃 • 𝑎 • ∆𝑡 ∆ (8𝑎) s. t. 𝑥 ≥ 𝑡 , ∀𝑖 = 1 … 𝑛 (8b) 𝑥 + ∆𝑥 ≤ 𝑡 , ∀𝑖 = 1 … 𝑛 (8c) 𝑥 + ∆𝑥 ≤ 𝑥 , ∀𝑖 = 1 … 𝑛 -1 (8d)
where Cj(xi) is the cost function of charger j during the current scheduling horizon, xi is the charging start time of EVi, nj is the current number of EVs need to be charged at charger j, ti ar is the arrival time of EVi, ti dp is the departure time of EVi.

Formula (8b) ensures that the charging start time later than the EV arrival time, and formula (8c) ensures that the charging demand can be satisfied before the EV departure. The formula (8d) ensures that the charging process of each EV is continuous, and only one EV can be charged at the same time.

The authors note that the minimization problem (8a) is a typical nonlinear problem (𝑘 • 𝐶 (𝑥 ) ≠ 𝐶 (𝑘 • 𝑥 ), 𝑘 ∈ 𝑅 ), thus the authors adopted a hybrid evolution algorithm to solve it [START_REF] Costa | Evolutionary algorithms approach to the solution of mixed integer non-linear programming problems[END_REF], as shown in Fig. 4.

In Figure .4, the initial population is the random feasible solution of the charging start time for the EVs at charger j, M is the iteration number, N is the parent population number. The fitness value is calculated through the cost function in (8a).

Regarding the charging time conflict issue of the shared charging spot, the problem (8a) is firstly checked for its feasibility according to the constraints (8b~8d) in the algorithm flowchart (Figure .4). If the constraints are satisfied, the hybrid evolution algorithm can output the optimal charging start time vector x for the EVs after iterations. The EVs at the same charger spot follow the earliest deadline first charging principle [START_REF] Kuran | A smart parking lot management system for scheduling the recharging of electric vehicles[END_REF]. The earliest departure EV will be charged firstly according to the obtained results x. On the contrary, if the charging time conflict occurs, which means the constraints (8b~8d) are not satisfied, the EVs will be charged immediately to avoid further penalties.

Approximate Dynamic Programming

Since the myopic optimal strategy only involves the information of current EVs, it cannot provide a global optimal policy. In this section, an approximate dynamic programming (ADP) framework combined with the EA algorithm is developed to solve the charging optimization problem of EVs. Considering the uncertain future charging demand, the global optimal charging policy can increase the charging demand satisfaction rate compared to the myopic policy.

A dynamic programming (DP) for the EV charging optimization problem can be formulated in a

Bellman's optimality equation form:

𝑉(𝑆 ) = min 𝐶(𝑆 , 𝑥) + 𝛾 𝑃(𝑠 |𝑆 , 𝑥) • 𝑉 (𝑠 ) (9)
where St represents the current charger state (the EV number, scheduling horizon, electricity price, etc. ), executing the action x. The optimal solution can be obtained by solving the Bellman optimality equation ( 9).

Vt
However, finding an exact solution is computationally infeasible in most of the practical problems due to the massive dimensions of the state and action spaces [START_REF] Powell | Tutorial on Stochastic Optimization in Energy-Part II: An Energy Storage Illustration[END_REF]. The exact transition probability matrix of the system states is also difficult to define in the practical projects due to the lack of sufficient information. The approximate dynamic programming (ADP) provides an efficient solution to alleviate the computational bottleneck in DP by replacing the exact value function with an approximation of some sort of form. With the approximation of the value function, ADP can solve the optimization problem in a forward manner as opposed to the backward computations in DP. The optimal policy of ADP can be obtained as in formula [START_REF] Xiang | Economic planning of electric vehicle charging stations considering traffic constraints and load profile templates[END_REF]:

𝑋 * = 𝑎𝑟𝑔 𝑚𝑖𝑛 𝐶(𝑆 , 𝑥) + 𝛾𝑉(𝑆 , 𝑥) (10)
where C(St,x) is the cost function of the current scheduling horizon, and 𝑉(𝑆 , 𝑥) is the approximate cost function of the future demand. In Figure .6, t c is the current time slot, t A is the end time slot of the scheduling horizon Hj, Tsj is the time range reserved for the current charging demand, and Taj is the time range reserved for the future charging demand. Hj is the scheduling horizon of charger j, and it is equal to the longest parking time of the EV at charger j, as in formula [START_REF] Fazelpour | Intelligent optimization to integrate a plug-in hybrid electric vehicle smart parking lot with renewable energy resources and enhance grid characteristics[END_REF].

𝐻 = 𝑚𝑎𝑥 𝑡 , … , 𝑡 , 𝐻 = 𝑇𝑠 + 𝑇𝑎 (11)

The lower boundary of Tsj can be obtained by summing up each vehicle's charging demand time at charger j, and the upper boundary of Tsj is equal to the horizon Hj, as demonstrated in formula [START_REF] El-Zonkoly | Intelligent energy management of optimally located renewable energy systems incorporating PHEV[END_REF].

𝑇𝑠 = ∆𝑥 , 𝑇𝑠 = 𝐻 (12)

where Tsj min is the lower boundary of Tsj. It is the minimum charging time to satisfy the current charging demand. The upper boundary Tsj max equals to the longest parking time of EV at charger j.

Since it is impossible to enumerate every possible value in the continuous set of Tsj, a finite number of discrete Tsj are evaluated here. With the boundaries of Tsj and the decision time step Δt, the finite sets of Tsj and Taj can be obtained in (13~14).

Ω = 𝑇𝑠 [1], … , 𝑇𝑠 [𝑛 ] , 𝑛 = 𝑇𝑠 -𝑇𝑠 𝛥𝑡 ( 13
) Ω = 𝑇𝑎 [1], … , 𝑇𝑎 [𝑛 ] , 𝑇𝑎 [𝑛 ] = 𝐻 -𝑇𝑠 [𝑛 ] (14)
Thus, the total cost 𝐶 of ADP can be obtained by summing up the costs of the optimization stage and the approximation stage:

𝐶 (𝑆 ) = 𝐶 𝑆 (𝑇𝑠 ), 𝑥 + 𝛾𝑉 𝑆 (𝑇𝑎 ) (15)
For each state St of charger j, there is a corresponding total cost Cj adp . Ωc-adp is used to denote the set of all the possible cost Cj adp .

𝛺 _ = 𝐶 [1], … , 𝐶 [𝑛 ] (16)
In the solution set of Ωc-adp, the global optimal cost and the corresponding optimal policy 𝑋 * can be found in [START_REF] Jin | Optimizing electric vehicle charging: A customer's perspective[END_REF].

𝐶 * = 𝑚𝑖𝑛 𝛺 _ , 𝑋 * = 𝑎𝑟𝑔 𝑚𝑖𝑛 {𝛺 _ } (17)

1) Optimization Stage

In the optimization stage, the cost 𝐶 of charger j in ( 15) can be obtained by solving the following problem with Algorithm 2 (Figure. Here, the optimization process is similar to the myopic optimal strategy with an extra constraint (18e).

The constraint (18e) ensures that the charging demands of current EVs can be satisfied within the time range Tsj. Thus, the hybrid EA designed in the previous section is used to solve it.

2) Approximation stage

In the approximation stage, the approximated value function 𝑉 is necessary to be well designed to avoid the dimensionality issue of DP. For the vehicle parking lots in the work sites and residential communities, the statistics of vehicle staying patterns follow the time-dependent distributions. A fixed parametric model appears to have difficulty specifying and characterizing all day's charging demand, while the simulation based methods are well adapted to reveal the dependency between the future charging demand and the electricity cost [START_REF] Zhang | Optimal Management for Parking-Lot Electric Vehicle Charging by Two-Stage Approximate Dynamic Programming[END_REF]. Thus, in this study, a Monte Carlo simulation based nonparametric cost function is developed to approximate the future charging demand at different time intervals over one day.

Firstly, the average power demand 𝑃 of a single EV over its parking time can be calculated in formula [START_REF] Xu | Coordination of PEVs charging across multiple aggregators[END_REF]. Similarly, for the charging station at time slot t, the power demand density can be obtained through calculating formula [START_REF] Honarmand | Integrated scheduling of renewable generation and electric vehicles parking lot in a smart microgrid[END_REF].

𝑃 = ∆𝑥 • 𝑃 𝑡 (19) 𝑃 = 𝑃 ( 20
)
where nt ev is the number of the current vehicles parked in the charging station. For a period of time 𝐻 , the demand estimation of the charging station can be formulated in [START_REF] Thomas | Optimal operation of an energy management system for a grid-connected smart building considering photovoltaics' uncertainty and stochastic electric vehicles' driving schedule[END_REF]. Thus, the demand estimation of charger j during its scheduling horizon 𝐻 can be approximately obtained with formulas (21~23). The future charging demand of charger j can be divided into two parts: the satisfied demand 𝑒 , and the unsatisfied part 𝑒 . In [START_REF] Shafie-Khah | Optimal trading of plug-in electric vehicle aggregation agents in a market environment for sustainability[END_REF], ∆𝑥 is the charging duration time of the satisfied part, 𝑥 is the virtual charging start time of the future charging demand, and 𝑡 is the end time slot of 𝐻 (Fig. 6).

𝐸 = 𝑃 • ∆𝑡 (21) 𝑒 = 𝐸 𝑁 = 𝑒 + 𝑒 (22) ∆𝑥 = 𝑡 -𝑥′ = 𝑒 𝑃 ( 23
)
Then the approximated cost function in (24a) can be obtained by summing up the electricity costs and the penalty costs.

𝑉 = min 𝐸 𝑎 • 𝑃 • ∆𝑡 + 𝑒 • 𝑎 ∆ (24𝑎) 𝑆. 𝑡. 𝑡 + 𝑇𝑠 ≤ 𝑥 ≤ 𝑡 + 𝐻 (24𝑏) 𝑒 = 𝑒 -𝑒 = 𝑒 -𝑃 • ∆𝑥 (24𝑐)
The value space of 𝑥 is limited in (24b), thus the value function (24a) can be effectively solved by line search methods [START_REF] Zhang | Coordinating plug-in electric vehicle charging with electric grid: Valley filling and target load following[END_REF]. Consequently, with the optimization stage cost Cj(St,x) in (18a) and the approximated future cost 𝑉 in (24a), the global optimal policy can be obtained through formula [START_REF] Jin | Optimizing electric vehicle charging: A customer's perspective[END_REF]. To demonstrate the ADP charging scheme clearly, the flowchart is presented in Figure .7, and the pseudo code of the ADP is briefly presented in Algorithm 3.

Benchmark charging schemes

The uncoordinated immediate charging scheme (UNC) is used as the benchmark in this paper, because it is widely applied in current EVCSs. With this charging scheme, the EV user randomly selects an EV charging spot for charging, and the EV can be charged immediately if the charging spot is available. The immediate charging scheme has also been combined with the fuzzy logic guiding system to verify the improvement of the charger utilization rate. Moreover, the comparative studies between the EVCS with pure SSC systems (EVCS-SSC) and the EVCS-MTC are conducted to highlight the advantages of the proposed ADP-based EMS.

Case Study

Case overview and parameter settings

The simulations are implemented in a real time horrizon-rolling maner. The future EV arrivals are unkown at the current decision time slot. The case studies of this paper will be based on the residential and the official parking lots, where the parking pattern generally follows a time-varying distribution. (e.g. the residential parking lots have a high arrival rate in the evening and a high departure rate in the morning).

Since the Poisson distribution is well adapted for traffic flow analysis, the vehicle arrival distribution is modeled as a Poisson process based on the historical data in the National Household Travel Survey (NHTS)

2009 [START_REF]National Household Travel Survey[END_REF]. The dynamic electricity price market of France is used as the price signal here [START_REF]Réseau de Transport D'électricité[END_REF]. A classical ARMA forecasting method is adopted to predict the electricity price [START_REF] Ziel | Forecasting Electricity Spot Prices Using Lasso: On Capturing the Autoregressive Intraday Structure[END_REF], and the prediction results are shown in Figure .8 (unit: cents €/kWh). As the authors focus on the energy management of EV charging in this paper, the details of electricity price forecasting are not introduced here. Some electricity markets can also provide a price forecasting service or a day-ahead price, such as ComEd, ERCOT day-ahead market [START_REF] Mouli | Comparison of system architecture and converter topology for a solar powered electric vehicle charging station[END_REF][START_REF] Hansen | A partially observable markov decision process approach to residential home energy management[END_REF]. In order to reduce the unsatisfied energy demand, the penalty price is set as 15 cents €/kWh, about 3 times of the normal price. In the EMS, the decision time step Δt is 15 min, the iteration number M of EA is 50, the parent population number N of EA is 30, and the discount factor γ of ADP is 0.8. The charging efficiency η is 0.9. The average charging power 𝑃 is 8kW, which belongs to a Level 2 charging station [START_REF] Yilmaz | Review of battery charger topologies, charging power levels, and infrastructure for plug-in electric and hybrid vehicles[END_REF]. The battery capacity of EV is assumed to be 50kWh, and the final target SOC of EV is set as 100%. The vehicle capacity of the parking lots is set as 115 vehicles, which allows maximum 115 EVs to be charged. Specifically, the settings of the two types of EVCS are shown in Table II, where there are total 40 chargers with 115 cables in the EV charging station equipped with multiple chargers (EVCS-MTC) and 115 chargers in the EV charging stations equipped with SSC (EVCS-SSC).

Application scenario A (residential parking lots)

In this section, numerical case studies with 143 EVs in a residential parking lot are conducted. The EV arrivals are divided into two groups: the arrivals during the daytime (between 9.am and 4.pm) are assumed to be the short stays, and the arrivals after 4.pm are assumed to be long stays for overnight charging. The parking time of the short stays is assumed to follow a Gaussian distribution N(3h,0.5h In Figure .10, the operation profiles of different chargers in EVCS-MTC are presented (controlled by FL-ADP). It is clear that multiple EVs can share one SMC system, and the SMC system has a higher utilization rate than the SSC system. With its single charging cable, the SSC system provides charging services for less EVs. The charging costs of the different charging schemes in Case A are listed in Table III. Since the uncoordinated immediate charging (UNC) and fuzzy logic-immediate charging (FL-IMC) satisfy the EVs as soon as possible, their electricity costs are higher than the other two charging schemes. On the other side, the FL-myopic charging scheme always charges the EV during the lowest electricity price intervals, so its electricity costs are the lowest among the charging schemes. However, due to its negligence of future charging demand, the myopic charging scheme has a relatively high penalty cost caused by the unsatisfied energy. Thus, the FL-ADP charging scheme displays a balanced performance over the other charging schemes (lower electricity costs than the immediate charging schemes, lower penalty costs than the myopic charging scheme), and has the lowest total charging costs.

Meanwhile, in Table III, it is clear that FL-IMC has a higher satisfied energy rate than the UNC scheme.

With the designed fuzzy logic controller, the EVs can be coordinately dispatched to their proper charging spots, which could help reduce the unsatisfied charging demand. In Figure .12, the charging profiles of 10 EVs are clearly illustrated. It can be seen that the charging process of each EV is continuous. Therefore, the obtained uninterruptible charging process can provide the BMS (or the local charging device) with the maximum autonomy to select the preferred flexible charging pattern, which can be used to prolong the battery lifetime or accelerate the EV charging.

EV1 EV16 EV31 EV46 EV61 EV76 EV91 EV106 EV121 EV136
2) Comparative study between the EVCS-SSC and the EVCS-MTC controlled by ADP(Case A2) The daily total costs comparison has been calculated in Table IV, including the electricity consumption costs, daily investment costs, and the unsatisfied energy penalties. Here, the hardware cost of each charging spot is 4000€, and the maintenance and repair cost rate is 400€/year (about 10% of the material cost) [START_REF] Schroeder | The economics of fast charging infrastructure for electric vehicles[END_REF].

The service life of each charging spot is assumed to be 15 years [START_REF] Schroeder | The economics of fast charging infrastructure for electric vehicles[END_REF][START_REF] Michelbacher | Enabling fast charging -Infrastructure and economic considerations[END_REF]. The extra cable cost for the SMC is set as 50€/per cable (the material cost is about 5 €/m), and the cost of a load switch is assumed to be 20€ [START_REF] Zhang | Optimal Planning of PEV Charging Station with Single Output Multiple Cables Charging Spots[END_REF]. For simplicity, the installation costs of the chargers are neglected here. The material costs and the maintenance costs are necessary for the daily operation of an EVCS, which are calculated as the daily investment item in Table IV.

In Table IV, it is clear that the electricity costs of the coordinated SSC charging scheme are the lowest.

However, the power peak load of the coordinated SSC charging scheme is much higher than that of the other Total charging power/kW Price(cents/kwh) schemes, which could be another concern for the local grid operator. Besides, it is also clear that the daily total costs of the proposed ADP charging scheme is the lowest. A cost reduction of about 56% can be achieved compared to the uncoordinated SSC charging. In this section, the optimal charging schemes of the EVCS-MTC in an office building district is studied.

Similar to the previous section, the EV arrival is modeled as a Poisson process. The departure time of EVs is assumed to follow a Gaussian distribution N(18:00,1hour 2 ). The total number of EV is 119, and the vehicle stay pattern of the office district is presented in Figure .14. As show in Figure .15, the operation profiles of EVCS-MTC are presented. It is clear that the SMC has a higher utilization rate than the SSC. With the designed the fuzzy guiding system, the EVs are coordinately dispatched to the corresponding charging spot. More EVs can be charged through the multi-cables of the SMC, while the "urgent" EVs can be charged at SSC. V. Similar to the previous section, the immediate charging schemes (UNC and FL-IMC) have higher electricity costs. Without the designed fuzzy logic guiding system, the penalty costs of UNC scheme are the highest. This illustrates the effectiveness of the designed guiding system. Meanwhile, considering both the dynamic price and the future charging demand, the proposed ADP charging scheme has the lowest charging costs. 2) Comparative study between the EVCS-SSC and the EVCS-MTC controlled by ADP (Case B2) the corresponding hardware material costs and the maintenance costs, the total operation costs are calculated in Table VI. Similar to the previous section, the installation costs are neglected here. Although the electricity costs of the coordinated charging with EVCS-SSC are lower than the proposed ADP charging scheme, the induced peak load power is much higher. Besides, it is clear that the daily costs of ADP are the lowest among the charging schemes. A cost reduction of about 61.90% can be achieved compared to the uncoordinated charging scheme.

Conclusions

This paper explores the energy management strategies for the EV charging stations with multiple types of chargers (EVCS-MTC). An ADP based charging scheme is proposed for this type of EVCS, which determines the optimal charging start time of each EV in consideration of both the real time electricity price and uncertain future charging demand. A fuzzy logic guiding system is also designed to allocate the EVs to the proper charging spots according to their charging urgency levels. Compared to the related existing researches of energy management for EVCSs, the proposed energy management strategy is suitable for multiple types of charging spots (i.e. SSC and SMC). The operation costs can be reduced by over 50% compared to the immediate charging scheme in EVCS-SSC. Moreover, since only the charging start time of each EV is determined by the EMS, this provides the local charger (or the BMS) with the maximum autonomy to select the preferred flexible charging pattern to prolong the battery lifetime, and the communication burden of the control system can be reduced as well.

Fig. 1 .

 1 Fig. 1. Different types of charging spots

Fig. 3 .

 3 Fig. 3. Membership functions of fuzzy logic controller

Fig. 4 .

 4 Fig. 4. The hybrid evolution algorithm (Algorithm 2)

Fig. 5 .Fig. 6 .

 56 Fig. 5. The proposed ADP framework for the EV charging spot

  Fig. 7. The flowchart of the ADP charging scheme

Fig. 8 .

 8 Fig. 8. Electricity price prediction of Oct.19, 2017

Fig. 9 . 1 )Fig. 10 .

 9110 Fig. 9. EV number in the residential parking lot (EV stay pattern)

Fig. 11 .

 11 Fig. 11. Total charging power profile in case A1

Fig. 12 .

 12 Fig. 12. Charging profiles of EVs in Case A with ADP control

Fig. 13 .

 13 Fig. 13. Charging power comparisions between the EVCS-SSC and the EVCS-MTC in Case A2

Fig. 14 .Fig. 15 .

 1415 Fig. 14. EV number in office building parking lot(vehicle stay pattern)

Fig. 16 .

 16 Fig. 16. Total charging power profile in case B1

Fig. 17 .

 17 Fig. 17. Charging profiles of EVs in Case B with ADP control The charging profiles of 10 EVs are presented in Figure.17. It can be observed that the charging process

Fig. 18 .

 18 Fig. 18. Charging power comparisions between the EVCS-SSC and the EVCS-MTC in Case B2 With the same 119 EVs' profiles in the office building parking lot, a comparative study between the

TABLE I

 I

		. Fuzzy Rules of Charging Priority
	L (laxity)	SOC	Charging priority
	L	L,M,H	H
	M	L,M,H	M
	H	L,M	M
	H	H	L

  is the value function of state St, and 𝛾 is the discount factor. C(St, xt) is the reward if the action xt is executed in state St , 𝑃(𝑠 |𝑆 , 𝑥 ) is the transition probability matrix, and 𝑠 is the next possible state after

  The flowchart of the ADP charging scheme Algorithm 3 Approximate Dynamic Programming Step 1. Fuzzy logic allocation of EV arrivals 1a. Evaluate the charging priorities of new arriving EVs 1b. Rank the available charging spots according to the speed index 1c. Allocate the EV to the corresponding charging spot Step 2. Initialization of ADP 2a. update the status of charger j (EV number, initial SOC, arrival time, departure time) 2b. Collect the predictions of the dynamic electricity price Step 3. Optimization and approximation of ADP 3a. Calculate the feasible time range of optimization stage: Ts (ΩTs ={Ts[1],…, Ts[k],…Ts[n s ]}), obtain the state set of charger j: St(Ts) ={St(Ts[1]),…, St(Ts[k],…, St(Ts[n s ]}. 3b. For each state St(Ts[k]) do : 3c. (Optimization stage) Go to Algorithm 2. Calculate the minimal cost Cj(St,x) in (18) and obtain the corresponding policy xj[k]. 3d. (Approximation stage) Calculate the future approximate cost 𝑉 [𝑆 , 𝑥′] with formula (24). 3e. Calculate the total cost Cj adp [k] according to formula (15) with the minimal cost Cj(St,x) from 3c, and the approximate future cost 𝑉 [𝑆 , 𝑥′] from 3d. 3f. Store the total cost Cj adp [k] and the corresponding policy xj[k] at state St(Ts[k]). 3g. k=k+1. If k>n s , End for. Step 4. Policy evaluation and execution 4a. Search for the optimal policy xj*= arg min{ Cj adp [1],…, Cj adp [k] …Cj adp [n s ]} from the stored results in Step 3f. 4b. Execute the policy xj*, and update the status of charger j and the EVs. 4c. Set tc=tc+1, go to step 1.

TABLE II .

 II Charger Settings of EVCS-MTC and EVCS-SSC

	EV Charging	Settings of		Charger Type		Total spot
	Station Type	Cable	SSC	SMC(a)	SMC(b)	SMC(c)	number
		Cable quantity	1	2	3	4
	EVCS-MTC	Charger quantity	5	5	20	10	115
	EVCS-SSC	Charger quantity	115	0	0	0	115

  2 ). The departure time of the long stay EVs are assumed to follow a Gaussian distribution N(8:00 a.m,1h 2 ). Their initial SOC are assumed to follow the Gaussian distributions (i.e. SOCi ~N(0.7, 0.08 2 ) for the short stay charging, SOCi~N(0.4,0.15 2 ) for the overnight charging). The vehicle stay pattern of the residential parking lots is shown in Figure.9.

TABLE III .

 III Charging Costs of Case A1

			Charging Costs(€)
	Charging Schemes	Electricity costs	Penalty	Satisfied energy (%)	Costs/€
	UNC	216.42	33.90	94.40	250.32
	FL-IMC	217.10	10.50	98.27	227.60
	FL-Myopic	189.87	39.60	93.46	229.47
	FL-ADP	198.66	18.90	96.88	217.56

TABLE IV .

 IV Cost Comparisons of the EVCS-SSC and the EVCS-MTC Controlled by ADP

			Spot	Power	Daily	Electricity	Penalty	Satisfied	Daily
	Spot Type	Control strategy	number	peak (kW)	Investment (€)	costs (€)	(€)	energy (%)	total costs(€)
	SSC	Uncoordinated	115	476	210.05	245.68	0	100	455.73
	SSC	Coordinated	115	887	210.05	148.15	0	100	358.20
	MTC	ADP	40	310	74.16	198.66	18.90	96.88	291.72
	5.3. Application scenario B (office building parking lots)

TABLE V .

 V Charging Costs of Case B1

	Charging Schemes	Electricity costs	Charging Costs(€) Penalty Satisfied energy (%)	Costs/ €
	UNC	134.58	15.60	95.45	150.18
	FL-IMC	144.75	0.60	99.83	145.35
	FL-Myopic	132.85	8.40	97.55	141.25
	FL-ADP	132.06	8.10	97.64	140.16

TABLE VI .

 VI Cost Comparisons of the Uncoordinated SSC charging scheme and the ADP charging scheme

			Spot	Power	Daily	Electricity	Penalty	Satisfied	Daily
	Spot Type	Control strategy
			number	peak (kW)	investment (€)	costs (€)	(€)	energy (%)	total costs(€)
	SSC	Uncoordinated	115	640	210.05	136.94	0	100	346.99
	SSC	Coordinated	115	488	210.05	127.81	0	100	337.86
	MTC	ADP	40	312	74.16	132.06	8.10	97.64	214.32


Sara Kassan
email: sara.kassan@uha.fr

Jaafar Gaber
email: jaafar.gaber@utbm.fr

Pascal Lorenz
email: pascal.lorenz@uha.fr

Game Theory based distributed clustering approach to maximize Wireless Sensors Network lifetime

Keywords: WSN, sensor lifetime, energy harvesting, clustering protocols, game theory, equilibrium

One of the most significant difficulty in Wireless Sensors Network (WSN) is the development of an effective topology control method that can support the quality of the network, respect the limited memory and at the same time increase the lifetime of the network. This paper introduces a new approach by mixing a non-cooperative Game Theory technique with a decentralized clustering algorithm to address the problem of maximizing the network lifetime. More precisely, this approach uses Game Theory techniques to control the activities of a sensor node and its neighbors to limit the number of the forwarding messages and to maximize the lifetime of the sensor's battery. In other words, the approach will decrease the energy consumed by the WSN by decreasing the number of forwarded packets and improve the network lifetime by harvesting energy from the environment. The simulations results show that the performances in terms of energy saving and increasing the number of data packets received by base station outperforms those with distributed based clustering algorithms without GT, such as low energy and location based clustering LELC and LEACH algorithms.

INTRODUCTION

The WSN has required an important attentiveness in these years. It is implicated widely in different domains, such as health care, ecosystem monitoring, environmental assessing, target tracking, maintaining control, and urban areas applications [START_REF] Alemdar | Wireless sensor networks for healthcare: A survey[END_REF] [2] [START_REF] Muduli | Application of wireless sensor network for environmental monitoring in underground coal mines: A systematic review[END_REF]. The major activities of a sensor node are capturing the data information in its urban environment, aggregate it and forward it to reach the sink using routing protocols. Moreover, the finite batteries capacity implies a limited lifetime of the sensor nodes and their applications. For this problem, several solution techniques have been proposed to prolong the network lifetime. Some of these solutions are based on topology control, routing protocols, data aggregation, forecasting approaches and others [START_REF] Yalgashev | Wireless sensors networks: basics and fundamentals[END_REF] [START_REF] Atto | Routing Protocols for Structural Health Monitoring of Bridges Using Wireless Sensor Networks[END_REF] [6] [START_REF] Syarif | Operator calculus approach for route optimizing and enhancing wireless sensor network[END_REF] [START_REF] Fasolo | In-network aggregation techniques for wireless sensor networks: a survey[END_REF]. The main tasks of our study is to extend the network lifetime by decreasing the wasted energy during the sensor node activities, and compensate the loss of energy by harvesting environmental energy in the sleeping mode. Our proposed method is based on a non-cooperative MGET in a clustering hierarchical structure. This approach is divided in two phases. The first one consists to select dynamically the clusters and their clusters heads based on sensors energy and location [START_REF] Ullah | A Prediction Mechanism of Energy Consumption in Residential Buildings Using Hidden Markov Model[END_REF]. In the second phase, the sensor node aggregates the sensing messages by a compression method to save sensor's energy and memory and decided to stay out of the communication to charge its battery in the sleeping mode or to enter the market game and send the message to its neighbors. The suitable decision of the sensor node depends on the probability obtained by maximizing its utility.

In this paper, the rest main contributions are structured as follows:

Section Ⅱ presents the categories of clustering protocols. In addition, it shows the different types of the GTs, their applications in WSN and the GT principle. In section Ⅲ, we explain the energy consumed by the different activities of an arbitrary sensor node and the model of sensor's rechargeable battery. In section Ⅳ, we adapt a non-cooperative game theory in a decentralized clustering protocol to prolong the WSN lifetime, decrease the wasted energy in the network and increase the number of data information arrived to the BS. The simulation results are presented and investigated in Ⅴ. Finally, we conclude the paper in section Ⅵ.

Related work

Clustering

Clustering protocols are one of the effective techniques of broadcasting for organizing the network and improving its lifetime and . Election of cluster heads (CHs) play a significant role in energy consumption management [START_REF] Lloret | A cluster-based architecture to structure the topology of parallel wireless sensor networks[END_REF]. Clustering protocols can be categorized in two classes: Centralized [START_REF] Muruganathan | A centralized energyefficient routing protocol for wireless sensor networks[END_REF] and distributed clustering algorithms [START_REF] Bukhari | Optimum Benefit Protocol: A fast converging, bandwidth-efficient decentralized similarity overlay[END_REF].

Centralized clustering

In centralized clustering, the BS is the organizer to form clusters. At the start of each round, sensors nodes have to transmit their location information and energy status to the BS. The BS will collect all information from all the sensors nodes in the network, select Cluster Heads (CH), and form clusters. This type of clustering is not a very suitable way to do clustering for a large number of sensors or large network wide.

For example, BCDCP (Base-Station Controlled Dynamic Clustering Protocol) is a centralized clustering protocol with a unique BS that is capable of complex computation, the CHs are selected by the BS randomly and all the routes and paths for transmission and reception of data information are selected by the BS [START_REF] Mehta | Comparative Study of BCDCP protocols in Wireless sensor network[END_REF]. Each node needs to transmit data messages regarding its location and residual energy to the BS during the formation of clusters. Therefore, BCDCP increases the design complexity and the energy consumption of the nodes in the large-range networks. BCSP (Base station Centralized Simple Clustering Protocol) is a protocol where in the BS does not collect any information about location of the sensor nods but utilizes information about remaining energy of each sensor node and the number of CHs depending on the circumstance of the sensor network [START_REF] Jan | Energy Evaluation Model for an Improved Centralized Clustering Hierarchical Algorithm in WSN[END_REF]. Each node should send its current energy information along with the sensing information, increasing the overhead. The drawback of this protocol is that due to its centralized implementation, it is not so appropriate for sensor networks with a large number of nodes. In addition, without any location information, BCSP cannot guarantee a uniform distribution of CHs nodes and their clusters.

Distributed clustering

Distributed clustering techniques eliminate the need of a centralized station to create CHs and clusters. The low energy and hierarchical structure models are generally used to create clusters and select CHs in two levels. At the first level, there is a selection of CHs and at the second level, the data messages are transferred by sensor nodes to BS via CHs. BS just receives messages and does not control the creation of clusters. EEMDC (Energy Efficient Multi level and Distance aware Clustering) is that extends the WSN lifetime while providing more stability and reliability to the network [START_REF] Mehmood | Energy-efficient multilevel and distance-aware clustering mechanism for WSNs[END_REF]. This routing protocol splits the network area into three logical layers. After the partition of the network area, the hotspot problem is fixed, the distance between the nodes and the CH and between the CH and the BS are taken into account when considering the hop-count value of the nodes. In addition, CHs are elected by acquiring the average leftover energy of the nodes, and the data messages are delivered to the BS using the shortest distance path to the BS. ICCBP (Inter Cluster Chain Based Protocol) is a new clustering algorithm that uses multi-hop and intra-cluster communication with updating CHs when the existing CHs dissipate their energy [START_REF] Rani | ICCBP: Inter Cluster Chain Based Protocol with Cross Layer Interaction for Randomly Deployed Wireless Sensor Networks[END_REF]. In [START_REF] Mittal | Harmony Search Algorithm Based Threshold-sensitive Energy-Efficient Clustering Protocols for WSNs[END_REF], a new structure to construct clusters and establish connections between sensors is proposed. In this protocol, the distance between CHs depends on a threshold calculated by the signal message transmission to insure the connections between clusters. In addition, this protocol creates a virtual wireless sensor networks. LEACH (Low-Energy Adaptive Clustering Hierarchy) protocol is one of the most popular decentralized clustering protocol based on the homogeneous WSNs [START_REF] Xiangning | Improvement on LEACH Protocol of Wireless Sensor Network[END_REF]. LEACH is a dynamic clustering method that update clusters and head clusters (CH) each round. Each round starts with a setup phase and finishes with steady state. In the setup phase, it rotates the CHs role among all sensor nodes to expend energy uniformly. Each sensor will pick a random number between 0 and 1. If this number is less than a threshold, 𝑇(𝑛) that will be defined, the sensor node becomes a CH for the current round. The threshold is set as follows:

𝑇(𝑛) = { 𝑝 1 -𝑝 (𝑟 × 𝑚𝑜𝑑 1 𝑝 ) 𝑓𝑜𝑟 𝑛 Є 𝐺 0 𝑂𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒 (1)
where 𝑝 is the cluster head probability in the network, 𝑟 is the current round of election and 𝐺 is the set of nodes that were not cluster head in the last round. In this paper, we use the clustering approach based on LEACH protocol with strategy based on location and residual energy of a sensor node to select the CHs [START_REF] Kassan | Low energy and location based clustering protocol for Wireless Sensor Network[END_REF].

Game Theory

The Game Theory (GT) is extensively applied in economics to maximize the outcomes by using the mathematical models such as the strategic game theory for the differential information economy which players suggest net trades and prices [START_REF] Fugarolas-Alvarez-Ude | A market game approach to differential information economies[END_REF]. In the recent years, GT is increasingly applied in WSN for different objectives, such as communication security, energy efficiency, control power transmission, data collection and pursuit evasion [START_REF] Shen | A noncooperative non-zero-sum game-based dependability assessment of heterogeneous WSNs with malware diffusion[END_REF] [22] [START_REF] Shi | Game Theory for Wireless Sensor Networks: A Survey[END_REF]. In this section, we review the GT used to enhance the energy conservation and extend the network lifetime. The GT can be classified in two top main categories: cooperative and non-cooperative games.

Cooperative Game Theory based approach

To decrease the energy consumed in the network, some sensor nodes cooperate to form coalitions. The coalitional game is considered as one of the most significant type of cooperative game theory. In [START_REF] Wu | A Cooperative Communication Scheme Based on Coalition Formation Game in Clustered Wireless Sensor Networks[END_REF], a power control game theoretic model is proposed to optimize the trade-off between energy consumption, and data packets transmission performance. It takes in consideration the individual utility of each sensor player. A novel approach is proposed in [START_REF] Jonnalagadda | A cooperative game framework for detecting overlapping communities in social networks[END_REF] to identify the overlapping community form in social networks. This approach is based on the shapely values mechanism. It activates with a weight function to find the stable coalitions of underlying community form of the network. The shapely values and the weight function are updated by the community detection algorithm using the local information. Another type of cooperative game is the bargaining game theory. To achieve the two opposite objectives, which are prolonging the WSN lifetime and maintaining the quality of the sensors activities in parallel, a Kalai-Smordinsky Bargaining Solution is used to find the best distribution among coalition members in [START_REF] Truong | Cooperative game theoretic approach to energy-efficient coverage in wireless sensor networks[END_REF].

Non-Cooperative Game Theory based approach

For the non-cooperative game theory, sensor nodes react selfishly to preserve their residual energy by refusing to receipt a data information and forward it in multi-hop network. The optimal responses for energy efficient non-cooperative game theoretic are obtained when each sensor player improves its strategy to maximize its utility, given the strategies of other sensors players. In [START_REF] Sengupta | A Game Theoretic Framework for Power Control in Wireless Sensor Networks[END_REF], a non-cooperative game theory model is proposed to control the transmit power levels and the Nash Equilibrium solution exists and attained according to the channel condition and power level. In addition, a non-cooperative game theory is used in the election of the CHs for the clustering model in [START_REF] Yang | A Game Theoretic Approach for Balancing Energy Consumption in Clustered Wireless Sensor Networks[END_REF]. In this game model, the sensor node decides to declare itself as a CH or not by calculating the optimal probability in the mixed strategy that depends on the maximizing of its payoff.

In addition to the non-cooperative and cooperative game theories, the repeated game theory is involved with a class of active games, in which a game is played for several times and the players have the ability to spot the result of the preceding game before attending the upcoming repetition [START_REF] Hoang | Applications of Repeated Games in Wireless Networks: A Survey[END_REF]. In [START_REF] Kim | A better-performing Q-learning game-theoretic distributed routing for underwater wireless sensor networks[END_REF], a control scheme based on reinforcement learning and game theory is proposed as a routing game model to provide a packetforwarding mechanism for underwater wireless sensors network and reduces the energy consumption.

In this paper, we propose a non-cooperative repeated game theory. Mostly, a game theory consists of a set of players, a set of strategies for each player and a set of corresponding utility functions. For a WSN, the sensors are the players, G is a particular game, where N = {S(1), S(2), . . . , S(P)} is a finite set of the sensor nodes. X = {x(1), x(2), . . . , x(P)} is the vector representation of the strategies taken by the sensors. U = {U(x(1), U(x(2), . . . , U(x(P)} is the corresponding utility function of node j represented by Uj, Uj (j = 1, 2, . . . , P), corresponds to the utility value of each node. This value is obtained at the end of the decision taken by the sensor node 𝑆(j). A strategy for a player is a whole organization of decisions in all possible states in the game. The players; sensors effort to act selfishly to maximize their consequences agreeing to their preferences. We have to formulate the utility functions in a way that will help node 𝑆(j) to select a strategy that characterizes the best response to its strategies. Every different mixture of individual decisions of strategies can produce a different strategy profile. For a non-cooperative repeated game theory, the solution concept involving N players is obtained when each player has made the best response against the others players decision of probabilities. This solution is named mixed strategy Nash Equilibrium.

ENERGY MODEL

Energy consumption model for a sensor

The energy cost for a sensor depends on the energy consumed to achieve its activities. In this section, we present the different factors that play a main role in the consumption of energy. To determinate the residual energy of a node, it is required to find the total energy consumption of a node in the operating of one data packet information. The notations utilized for the factors causing energy consumption by a sensor node are described in Table 1.

 Sensing energy consumption

The sensing energy cost depends on the type of sensors. For example, the temperature sensors consumed less important energy than gas sensors. The sensor node can contain diverse sensors, and each one has its individual energy consumption attributes. Generally, the sensing energy consumption for a 𝑆 𝑖 can be expressed as follows:

𝐸 𝑆 = 𝐿(𝑆 𝑖 ) × 𝑉 𝑑𝑐 × 𝐼(𝑆 𝑖 ) × 𝑇(𝑆 𝑖 ) (2)
where 𝐼(𝑆 𝑖 ) is the needed amount of current, and 𝑇(𝑆 𝑖 ) is the duration to detect and collect 𝐿(𝑆 𝑖 ) bits data information.

 Processing energy consumption

The sensor consumes energy to read the data message and to write it in its memory. The processing energy consumption could be calculated by [START_REF] Pati | An Energy-Efficient Approach to Select Cluster-Head in Wireless Sensor Networks[END_REF]:

𝐸 𝑃 = 𝐿(𝑆 𝑖 ) × 𝑉 𝑑𝑐 8 × (𝐼 𝑊𝑟𝑖𝑡𝑒 × 𝑇 𝑊𝑟𝑖𝑡𝑒 + 𝐼 𝑅𝑒𝑎𝑑 × 𝑇 𝑅𝑒𝑎𝑑 ) (3)
where 𝐼 𝑊𝑟𝑖𝑡𝑒 and 𝐼 𝑅𝑒𝑎𝑑 are the necessary amount current to write and read one byte data. 𝑇 𝑊𝑟𝑖𝑡𝑒 and 𝑇 𝑅𝑒𝑎𝑑 are the necessary duration to treat the 𝐿(𝑆 𝑖 ) data information.

 Communicating energy consumption

The energy consumed to transmit and receive 𝐿(𝑆 𝑖 ) is computed following the first-order wireless communication model for the radio hardware illustrated in fig. 1 [START_REF] Heinzelman | Energy-Efficient Communication Protocol for Wireless Microsensor Networks[END_REF].

Figure 1. First order radio energy model

Transmitter expends energy to run the radio electronics and the power amplifier. The necessary energy required to transmit 𝐿(𝑆 𝑖 ) bits data message is: 4 𝑤ℎ𝑒𝑛 𝑑 > 𝑑 0 [START_REF] Yalgashev | Wireless sensors networks: basics and fundamentals[END_REF] where 𝐸 𝑒𝑙𝑒𝑐 represents the energy consumed to transmit or receive 1 bit messag, the constants 𝐸 𝑓𝑠 and 𝐸 𝑚𝑝 depend on the transmitter amplifier model. is for multipath model, 𝑑 is the transmitter receiver distance and 𝑑 0 is a threshold distance calculated as follows:

𝐸 𝑇 𝑖 = { 𝐿(𝑆 𝑖 ) × 𝐸 𝑒𝑙𝑒𝑐 + 𝐿(𝑆 𝑖 ) × 𝐸 𝑓𝑠 × 𝑑 2 𝑤ℎ𝑒𝑛 𝑑 < 𝑑 0 𝐿(𝑆 𝑖 ) × 𝐸 𝑒𝑙𝑒𝑐 + 𝐿(𝑆 𝑖 ) × 𝐸 𝑚𝑝 × 𝑑
𝑑 0 = √ 𝐸 𝑓𝑠 𝐸 𝑚𝑝 ⁄ (5)
And the energy consumed by the radio to receive 𝐿(𝑆 𝑖 ) bits data information is defined by:

𝐸 𝑅 𝑖 = 𝐿(𝑆 𝑖 ) × 𝐸 𝑒𝑙𝑒𝑐 (6)
 Switching Radio sensor state energy consumption

The sensor dissipates a significant amount of energy to change from a state (i.e., sensing, processing, transmitting and receiving) 𝑖 to another 𝑗. For the switching states in the radio, the wasted energy can be determined as:

𝐸 𝑆𝑤𝑖𝑡𝑐ℎ-𝑅𝑎𝑑𝑖𝑜 = 𝑉 𝑑𝑐 2 × (𝐼 𝑠𝑡 𝑗 -𝐼 𝑠𝑡 𝑖 ) × 𝑇 𝑠𝑡 𝑖,𝑗 (7)
where 𝐼 𝑠𝑡 𝑗 is the current draw of the radio in the state switched to, and 𝐼 𝑠𝑡 𝑖 is the current draw of the radio in the current state and 𝑇 𝑠𝑡 𝑖,𝑗 is the necessary time for the radio to switch from state 𝑖 to 𝑗.

 Switching the microcontroller (MCU) mode energy consumption

The sensor wastes energy by switching between the MCU modes. In this paper, we just take in consideration the active mode and the sleeoing mode. This wasted energy is negligible compared to switching radio energy consumption. The energy cost for the computational MCU mode can be expressed as:

𝐸 𝑆𝑤𝑖𝑡𝑐ℎ-𝑀𝐶𝑈 = 𝑉 𝑑𝑐 × (𝐼 𝐴𝑐𝑡𝑖𝑣𝑒 × 𝑇 𝐴𝑐𝑡𝑖𝑣𝑒 + 𝐼 𝑆𝑙𝑒𝑒𝑝 × 𝑇 𝑆𝑙𝑒𝑒𝑝 ) (8)
The total energy consumed by each sensor 𝐶 is defined as follows: 𝐶 = 𝐸 𝑆 + 𝐸 𝑃 + 𝐸 𝑇 𝑖 + 𝐸 𝑅 𝑖 + 𝐸 𝑆𝑤𝑖𝑡𝑐ℎ-𝑅𝑎𝑑𝑖𝑜 + 𝐸 𝑆𝑤𝑖𝑡𝑐ℎ-𝑀𝐶𝑈 (9)

Rechargeable battery model

The applications of the sensor node are limited by the availability of the power stored in its battery. If the sensor node expends all its energy, it is considered as dead. Moreover, it disturbs the dispatching of the information data to reach the sink. In view of the fact that the replacing of the sensor's battery by a new one and the redeployment of the sensors are very costly, it is not appropriate to change the sensor's battery. To overcome these problems, the sensors nodes can use energy harvesting supplies to recharge their batteries. However, the utilization of renewable energy depends on the network environmental conditions as solar, wind, hydrogen, and hybrid sources [START_REF] Knight | Energy Options for Wireless Sensor Nodes[END_REF]. In this article, we considered that the sensor's battery can be recharged from the environment (see Fig. 2). The distributed clustering algorithm uses round as unit, each round is made up of set-up phase and steady phase for the purpose of reducing unnecessary energy costs. Set-up phase is for the building of the clusters and the election of the CHs and steady phase is for the sensor's states (see Fig. 3).

Figure 3. Set-up and steady phases 4.1. Set-up phase

It concerns the formation of the clusters and their heads for each round using sensor location and individual energy consumption [START_REF] Kassan | Low energy and location based clustering protocol for Wireless Sensor Network[END_REF]. Two CHs cannot be in the same cluster. For this reason, the distance between CHs should be bigger than a threshold distance. The remaining energy level in each sensor node plays an important role in increasing the lifetime of the network. CHs can ensure the link between sensors and the Base Station (BS). For a round, if a CHs is dead, the communications between the sensor nodes in its cluster and the BS are interrupted and no data information from this cluster can reach the BS. A sensor node that has a residual energy bigger than a threshold energy could become a CH for the actual round.

𝐸(𝑆 𝑖 ) > 𝛽 𝑜𝑝𝑡 × 𝐸 𝑡𝑜𝑆𝑖𝑛𝑘 [START_REF] Lloret | A cluster-based architecture to structure the topology of parallel wireless sensor networks[END_REF] where

𝛽 𝑜𝑝𝑡 = ((𝑟 𝑚𝑎𝑥 -𝑟)|(𝑟 𝑚𝑎𝑥 × (𝐸 𝑡𝑜𝑆𝑖𝑛𝑘 |𝐸 0 (𝑆 𝑖 ))) (11)
where 𝐸(𝑆 𝑖 ) is the residual energy of the sensor 𝑆 𝑖 , 𝐸 𝑡𝑜𝑆𝑖𝑛𝑘 is the necessary energy for a sensor to transmit a data information to the BS, 𝛽 𝑜𝑝𝑡 is the maximum number of data messages that the sensor 𝑆 𝑖 can send to the BS, 𝑟 𝑚𝑎𝑥 is the maximum number of rounds (that corresponds to the network lifetime) and 𝑟 is the actual round. The proposed set-up phase is illustrated by a flowchart scheme in Fig. 4.

For each round, the selection of the CHs is based on the location and residual energy and each non-CH sensor decides to belong the cluster that corresponds to the minimum distance between its location and the CH location. Each cluster has its unique CH that can be updated after each round epochs.

Steady phase

It corresponds to the data processing, transmitting and receiving between the sensors in the same cluster. This phase is divided in two stages: Data information aggregation and entry market game theory for the communication between neighbors' nodes in the same cluster.

 Data information aggregation

To save the maximum amount of energy consuming during sensors communications and to increase the limited available space in the memory, the data messages are compressed before their registration in the sensor's memory.

If we compress a message of 𝐿(𝑆 𝑖 ) bits to a message of 𝐿(𝑆 𝑖 )/𝑎, the saving energy obtained by compressing the data information can be expressed as follows:

𝐸 𝑠𝑎𝑣𝑖𝑛𝑔 𝑖 = [1 -1 𝑎 ⁄ ]. [𝐸 𝑃 + 𝐸 𝑇 + 𝐸 𝑅 ] -𝐸 𝑐𝑜𝑚𝑝𝑟𝑒𝑠𝑠 ( 12
)
where 𝐸 𝐶𝑜𝑚𝑝𝑟𝑒𝑠𝑠 is the energy cost to compress 𝐿(𝑆 𝑖 ) bits data packet message. At this stage, we propose a non-cooperative game theory based algorithm to control the energy consumed by the sensors in the network. This algorithm is called the Profitable Energy Market Game (PEMG) wherein each player has to decide if he wants to participate or to stay out of the market at each round. The market defines trading rules according to a strategy. In this work, the strategy has two actions: to enter the game or to stay out the game. Each player (i.e. sensor) calculates a payoff that can affect or be affected by the payoffs of other players (i.e. its neighbors). The payoff is a function of the sensor's residual energy. More precisely, the payoffs depend on the players' strategies that stay in the sleeping mode to charge their batteries or enter the game to transmit the sensing data messages.

In what follows, a PEMG is deployed within each cluster. The players in each cluster 𝑖 are 𝑆 𝑖 (𝑗) where 𝑗 = {1,2 ⋯ 𝑁 𝑖 } is the current number of sensors in the cluster for the round 𝑟, 𝑚 𝑖 (𝑘) denotes the number of messages sent by a given player 𝑆 𝑖 (𝑘), 𝑀 𝑗 is the number of 𝑆 𝑖 (𝑗) neighbors and 𝑈 𝑖 (𝑗) is the individual utility function that will be presented later.

The player 𝑆 𝑖 (𝑗) can take one of two decisions denoted by 𝑥 𝑖 (𝑗) set to 0 or 1: Entering the game with 𝑥 𝑖 (𝑗) = 1 and participate by sending messages or staying out of the game and harvesting energy to charge its battery with 𝑥 𝑖 (𝑗) = 0. The sensor's decisions can be expressed as follows:

𝑥 𝑖 (𝑗) = { 1, 𝑆 𝑖 (𝑗) 𝑒𝑛𝑡𝑒𝑟𝑠 𝑡ℎ𝑒 𝑔𝑎𝑚𝑒 0, 𝑆 𝑖 (𝑗) 𝑠𝑡𝑎𝑦𝑠 𝑜𝑢𝑡 𝑡ℎ𝑒 𝑔𝑎𝑚𝑒 ( 13
)
In this paper, our game model in each cluster is defined by: 𝐺 𝑖 = {𝑁 𝑖 , 𝑀 𝑗 , 𝑋 𝑖 (𝑗) 𝑗𝜖𝑁 𝑖 , 𝑈 𝑖 (𝑗) 𝑗𝜖𝑁 𝑖 } ( 14)

The utility function for a sensor node depends on the cost of the strategy decision taken and it can be expressed by: 𝑈 𝑖 (𝑥 𝑖 (𝑗)) = { 𝑔 𝑖 (𝑗) -𝐶 𝑖 (𝑗), i𝑓 𝑥 𝑖 (𝑗) = 0 and ∃ 𝑥 𝑖 (𝑘) = 1 𝑔 𝑖 (𝑗) + 𝑓 𝑖 (𝑗), 𝑖𝑓 𝑥 𝑖 (𝑗) = 0 for all j ∈ 𝑀 𝑗 0, i𝑓 𝑥 𝑖 (𝑗) = 1 [START_REF] Mehmood | Energy-efficient multilevel and distance-aware clustering mechanism for WSNs[END_REF] where 𝑖 ≠ 𝑗 , the cost function 𝐶 𝑖 (𝑗) is the total energy consumed by 𝑆 𝑖 (𝑗) to send a message, the gain function 𝑔 𝑖 (𝑗) is its residual energy and 𝑓 𝑖 (𝑗) is the energy harvested to recharge the sensor's battery.

When a sensor player 𝑗 selects the action to enter the game to transmit messages and its neighbors sensors not then the utility is 𝑔 𝑖 (𝑗) -𝐶 𝑖 (𝑗). The utility is 𝑔 𝑖 (𝑗) + 𝑓 𝑖 (𝑗), if the sensor player 𝑗decides not to enter the game to harvest and charge its battery and that, one of its neighbors enters the game.

In our proposed non-cooperative market entry game, the best response dynamics for the sensors players can be acquired in the context that each sensor node updates its strategy in order to maximize its utility, given the strategy of its neighbors (i.e., a mixed strategy).

To determine a mixed strategy equilibrium, we need to consider the expected utility of each player. If a randomly node j in the cluster 𝑖 enters the market with a probability 𝑃 𝑖 (𝑗), the expected utility of the node 𝑗 can be expressed as follows:

𝐸[𝑈 𝑖 (𝑥 𝑖 (𝑗))] = 𝑃 𝑖 (𝑗) × (𝑔 𝑖 (𝑗) -𝐶 𝑖 (𝑗)) + (1 -𝑃 𝑖 (𝑗)) × (𝑔 𝑖 (𝑗) + 𝑓 𝑖 (𝑗)) × (1 -∏(1 -𝑃 𝑖 (𝑘)) 𝑀 𝑗 𝑘≠𝑗 ) (16)
It should be noted this expected utility of node 𝑗 reaches its maximum when the battery of the sensor is full (i.e., the residual energy 𝑔 𝑖 (𝑗)is at its maximum) and the energy consumption 𝐶 𝑖 (𝑗) is 0.

The Figure fig. 4 shows the variation of the expected utility function for a given sensor 𝑗, with the variation of the number of neighbors between 1 and 30 and the variation of the probability to enter the game, e.g., 𝑃 𝑖 (𝑗) is between 0.1 and 1. We consider that the neighbors have the same probability to enter the game 𝑃 𝑖 (𝑘) = 0.3, 𝑘 ≠ 𝑗. Assuming in the simulation that the maximum energy capacity available is 0.5 j, the result shown in fig. 4 shows that the expected utility function has a maximum which is the maximum energy in the sensor's battery. Since the best response for a sensor node is when its utility reaches its maximum, we derive the expected utility function and the derivation is obtained by:

𝜕𝐸[𝑈 𝑖 (𝑥 𝑖 (𝑗)𝑗)] 𝜕𝑃 𝑖 (𝑗) = -(𝐶 𝑖 (𝑗) + 𝑓 𝑖 (𝑗)) + (𝑔 𝑖 (𝑗) + 𝑓 𝑖 (𝑗)) × ∏(1 -𝑃 𝑖 (𝑘))
𝑀 𝑗 𝑘≠𝑗 [START_REF] Mittal | Harmony Search Algorithm Based Threshold-sensitive Energy-Efficient Clustering Protocols for WSNs[END_REF] Setting the derivation to zero, we get the maximum as follows:

(𝐶 𝑖 (𝑗) + 𝑓 𝑖 (𝑗)) (𝑔 𝑖 (𝑗) + 𝑓 𝑖 (𝑗)) = ∏ (1 -𝑃 𝑖 (𝑘)) 𝑀 𝑗 𝑘≠𝑗 (18)
Letting 𝛼 𝑖 (𝑗) = (𝐶 𝑖 (𝑗)+𝑓 𝑖 (𝑗))

(𝑔 𝑖 (𝑗)+𝑓 𝑖 (𝑗))

) and 𝑞 𝑖 (𝑘) = (1 -𝑃 𝑖 (𝑘)), we obtain a system of 𝑀 𝑗 equations from eq. 18 that can be written as:

{ 𝛼 𝑖 (1) = 𝑞 𝑖 (2) × 𝑞 𝑖 (3) × … × 𝑞 𝑖 (𝑀 𝑗 ) 𝛼 𝑖 (2) = 𝑞 𝑖 (1) × 𝑞 𝑖 (3) × … × 𝑞 𝑖 (𝑀 𝑗 ) ⋮ 𝛼 𝑖 (𝑀 𝑗 -1) = 𝑞 𝑖 (1) × … × 𝑞 𝑖 (𝑀 𝑗 -2) × 𝑞 𝑖 (𝑀 𝑗 ) 𝛼 𝑖 (𝑀 𝑗 ) = 𝑞 𝑖 (1) × … × 𝑞 𝑖 (𝑀 𝑗 -2) × 𝑞 𝑖 (𝑀 𝑗 -1) (19)
which can be rewritten as:

(∏(𝑞 𝑖 (𝑘)) 𝑀 𝑗 𝑗=1 ) 𝑀 𝑗 -1 = ∏(𝛼 𝑖 (𝑗))
𝑀 𝑗 𝑗=1 [START_REF] Fugarolas-Alvarez-Ude | A market game approach to differential information economies[END_REF] since 𝑞 𝑖 (𝑘) = (1 -𝑃 𝑖 (𝑘)), the eq. 20 becomes :

(∏(1 -𝑝 𝑖 (𝑘)) 𝑀 𝑗 𝑗=1 𝑀 𝑗 -1 = ∏(𝛼 𝑖 (𝑗)) 𝑀 𝑗 𝑗=1 (21)
The optimal probability for a given sensor node 𝑗 in the cluster 𝑖 to enter the market game can be then expressed as follows:

𝑃 𝑖 (𝑗) = 1 - √∏ (𝛼 𝑖 (𝑘)) 𝑀 𝑗 𝑘=1 𝑀 𝑗 -1 𝛼 𝑖 (𝑗) (22)
The maximum utility for a sensor player depends on its strategy and also on the combination decisions of all other neighbors players.

The utility matrix for sensor player 𝑆 𝑖 (𝑗) is shown in Table 2.

For the calculation of the utility matrix for each cluster game, the resulting utility coming from the combination of the actions taken by the players (to enter the market game or not to enter the market game) are taken into consideration as indicated by eq.15. If a node player 𝑗 in the cluster 𝑖 enters the market, its utility will be (𝑔 𝑖 (𝑗) -𝐶 𝑖 (𝑗)) regardless of the action of its neighbors in this cluster. If none of the nodes in the same cluster enters the market, this means that all the nodes 𝑗 and their neighbors' nodes are out of energy and cannot find any available energy sources to harvest and charge their batteries.

For this reason, these sensors receive a payoff equal to 0. It is assumed that (𝐶 𝑖 (𝑗) < 𝑔 𝑖 (𝑗)), so that at least a node would enter the market if no other sensor node does. However, if one node enters the market, then each of its neighbors would prefer to be selfish and would maximize its residual energy by charging its battery.

In a symmetrical market game, the strategy that a sensor player and its neighbors decide to enter the game market, i.e., 𝑋 = {1 … 1}, or the strategy that a sensor player and its neighbors decide to charge their battery in the sleeping mode, i.e., 𝑋 = {0 … 0}, are not Nash equilibria. Indeed, it is impossible for each node to find out a best response to the strategy decisions. Namely, no pure-strategy Nash Equilibrium exists in our game. However, to permit the entry market game to have symmetrical Nash equilibria, the players can adopt mixed strategies. For any node, as (𝑔 𝑖 (𝑗) -𝐶 𝑖 (𝑗)) > 0, the sensors players do not have a dominant strategy. We assumed that each sensor player is allowed to choose its strategy decisions randomly following a probability distribution. In other words, there are 𝑀 𝑗 mixed strategies Nash equilibria in the game and the best responses are obtained when the utility of a node 𝑗 to enter the market is equal to the utility of the node 𝑗 to stay out of the market and thus we can compute the equilibrium probability from the table 2 by:

𝑈 𝑖 (𝑥 𝑖 (𝑗) = 0) = 𝑈 𝑖 (𝑥 𝑖 (𝑗) = 1) (24)
(𝑔 𝑖 (𝑗) -𝐶 𝑖 (𝑗)) × 𝑝 = (𝑔 𝑖 (𝑗) + 𝑓 𝑖 (𝑗)) × (1 -(1 -𝑝) 𝑀 𝑗 -1 ) (25)

Therefore, from the above eq. 25, we can calculate the equilibrium probability 𝑃 𝐸 to enter the game for a 𝑀 𝑗 Nash equilibrium with a mixed strategies as follows:

𝑃 𝐸 𝑖 (𝑗) = 1 -(1 - (𝑔 𝑖 (𝑗) -𝐶 𝑖 (𝑗)) (𝑔 𝑖 (𝑗) + 𝑓 𝑖 (𝑗)) ) 1 𝑀 𝑗 -1 (26)
since we have 0 < (𝑔 𝑖 (𝑗)-𝐶 𝑖 (𝑗)) (𝑔 𝑖 (𝑗)+𝑓 𝑖 (𝑗)) < 1. Subsequently, from the eq. 26, we can notice that the probability decreases when the number of neighbors players increases. For example, in the limiting cases, while (𝑀 𝑗 -1) is varying from 1 to infinity, the probability of entering the market game will be changing from 1 to 0. When the number of neighbors decreases (from 30 to 1) when some neighbors nodes dead, the forwarding entering game increases.

SIMULATION RESULTS

For our experiments, we used 200 sensor nodes in our network, where nodes are randomly distributed in 1000x1000 m2 area. The BS is deployed at the center of the area. For the simulations, a sensor node considers another sensor as a neighbor if the distance that separate them is lower than a threshold D. This threshold D is the maximum radius with which a sensor can receive a fixed number of bits for a fixed power transmission. In Fig. 6, we compare the energy consumed by the network for 7000 rounds by comparing our proposed approach with other protocols from the literature: the LEACH clustering protocol [START_REF] Xiangning | Improvement on LEACH Protocol of Wireless Sensor Network[END_REF] and a clustering based protocol [START_REF] Kassan | Low energy and location based clustering protocol for Wireless Sensor Network[END_REF]. The results show that these Leach protocol consumes all its energy after 2000 rounds. An improved version of Leach via a low energy and location based clustering approach (LELC) presented in [START_REF] Kassan | Low energy and location based clustering protocol for Wireless Sensor Network[END_REF] stills have energy for 5000 rounds. Fig. 6 shows also the results of the two versions of the proposed PEMG with Game Theory (GT), Popt GT and Pnash GT, according respectively to Eq.22 (optimal probability) and Eq.26 (Nash equilibrium probability). The either PEMG versions extend the lifetime of the network beyond 7000 rounds. The results show also that Popt GT consumes less energy than the PEMG with Nash probability Pnash GT.

Figure 6. Energy Consumption by the network

The figure fig. 7 shows the evolution of number of dead sensors. For Leach clustering protocol, the majority of sensor nodes are died before 2000 rounds of time. At the same time, with LELC clustering protocol, the number of dead sensors is less than the half of the number of dead sensor nodes in Leach protocol. Moreover, when the WSN is dead, after 5000 rounds, the number of dead nodes is 120. It stills less than the dead nodes in Leach protocol after 2000 rounds.

In the case of Pnash GT, the number of dead nodes is the half of the total number after 7000 rounds (i.e., 50%), while in the case of Popt GT and LELC without GT, 60% of the initial number of sensors are dead. This is mainly because of our GT based protocols provide the harvesting option to the sensors. Moreover, with Popt GT, the strategy taken by a sensor privilege the action to enter the market and thus sending messages, i.e., maximizing the strategy of communicating messages via Popt maximization. However, for Pnash GT, all the strategies taken by the sensor are equally probable.

Figure 7. Dead Nodes in the network

The simulation results reported in Fig. 8 show that the number of packets received by the BS for PEMGT with Pnash in our clustering protocol is more important than all the other approaches and that the network is still active after 7000 rounds. However, in the case of clustering without any GT, the network lifetime is limited to 5000 rounds. In addition, the small difference in energy consumed by the network between Pnash and Popt in PEMGT is justified by the number of packets information that reach the BS and the extension of the network lifetime.

CONCLUSION

In this paper, a clustering based protocol using a noncooperative game theory (GT) approach is proposed with the aims to prolong WSN lifetime. The GT permits to a sensor to decide between two actions: to enter the game and transmit a message or to stay out the game and harvest to charge its battery. For the network organization, a clustering protocol based on sensors locations and energy consumptions is used and a GT based algorithm is deployed within each cluster. The objective is to find out the Nash Equilibrium (NE) solution for mixed strategies. The simulation results show that the proposed approaches outperforms those without GT in terms of energy consumption, nodes and network lifetimes. In other words, combining a GT based approach with a clustering protocol provides an efficient solution for energy harvesting to prolong WSNs lifetime. The future work will focus on the control of the energy harvesting process in the sensors.

  𝐸 𝑓𝑠 is for the free space model, 𝐸 𝑚𝑝 𝐿(𝑆 𝑖) × 𝐸 𝑒𝑙𝑒𝑐 𝐸 𝑇 (𝑑) 𝐸 𝑅 (𝑑) 𝐿(𝑆 𝑖) × 𝐸 𝑒𝑙𝑒𝑐 d

Figure 2 .

 2 Figure 2. Energy harvesting for WSN model 4. THE PROPOSED APPROACH: GAME THEORY WITHIN CLUSTERING ALGORITHM FOR WSNThe distributed clustering algorithm uses round as unit, each round is made up of set-up phase and steady phase for the purpose of reducing unnecessary energy costs. Set-up phase is for the building of the clusters and the election of the CHs and steady phase is for the sensor's states (see Fig.3).

Figure 4 .

 4 Figure 4. Flowchart for the set-up phase

Figure 4 .

 4 Figure 4. The expected utility function varies with the number of nodes neighbors and the probability 𝑃 𝑖 (𝑗) and has a maximum that corresponds to the maximum battery capacity.

Figure 5 .

 5 Figure 5. Entering game probability varies with the number of nodes neighbors for a Nash Equilibrium mixed strategies Fig. 5 depicts the entering game probability that is given in Eq. 26 with increasing number of neighbors of the source, from 1 to 30, for different values of actual energy in the battery 𝑔 𝑖 (𝑗).When the number of neighbors decreases (from 30 to 1) when some neighbors nodes dead, the forwarding entering game increases.

Figure 8 .

 8 Figure 8. Number of Data Packets received by the BS. With Pnash GT, the network is still active as the packets continue to be received by BS beyond the other protocols.

Table 1 : Notations definition

 1

	Notations	Definition
	𝑛	Number of sensor nodes in the network
	𝑆 𝑖	Sensor node where 𝑖 = {1, 2, … , 𝑛}
	𝐸 𝑆	Sensing energy cost
	𝐸 𝑃	Processing energy cost
	𝐸 𝑇	Transmitting energy cost
	𝐸 𝑅	Receiving energy cost
	𝐸 𝑆𝑤𝑖𝑡𝑐ℎ-𝑅𝑎𝑑𝑖𝑜 Switching state energy cost in the radio
	𝐸 𝑆𝑤𝑖𝑡𝑐ℎ-𝑀𝐶𝑈	Switching mode energy cost in the
		MicroController Unit (MCU)
	𝑉 𝑑𝑐	Voltage supply

Table 2 : Symmetric entering market game matrix

 2 Let 𝑋 = {𝑥 𝑖[START_REF] Alemdar | Wireless sensor networks for healthcare: A survey[END_REF], … 𝑥 𝑖 (𝑀 𝑗 )} be the vector representation of the strategies played by the sensors. The utility matrix for 𝑆 𝑖 (𝑗) can be written as follows:

			All 𝑆 𝑖 (𝑘) do not	At least one
			enter the market	enters the market
	𝑆 𝑖 (𝑗) enters the	𝑔 𝑖 (𝑗) -𝐶 𝑖 (𝑗)	𝑔 𝑖 (𝑗) -𝐶 𝑖 (𝑗)
	market
	𝑆 𝑖 (𝑗) doesn't		0	𝑔 𝑖 (𝑗) + 𝑓 𝑖 (𝑗)
	enter the market
	𝑈 𝑖 (𝑗) = [	(𝑔 𝑖 (𝑗) -𝐶 𝑖 (𝑗)) (𝑔 𝑖 (𝑗) -𝐶 𝑖 (𝑗)) 0 (𝑔 𝑖 (𝑗) + 𝑓 𝑖 (𝑗))	]

Table 3 : Simulation parameters Parameter value

 3

	Network area (m2)	100×100
	BS location	(50, 50)
	Number of sensor nodes 𝑛	200
	Initial energy (J) 𝐸 0	0.5
	𝐸 𝑒𝑙𝑒𝑐 (nJ/bit)	50
	parameters of amplifier energy consumption 𝐸𝑚𝑝 (pJ/bit/m4) and 𝐸𝑓𝑠 (pJ/bit/m2)	0.0013 and 10
	Data aggregation energy (J)	5×10 -12
	Size of data packet (bits) 𝐹	4000
	Number of bits transmitted by sensor (bits) L	2500
	Compression percentage (%)	20

ACKNOWLEDGMENT

The authors would like to thank the editors and reviewers for their valuable comments on earlier versions of this paper.