Aditya Goenka
email: a.goenka@bham.ac.uk

Lin Liu
email: lin.liu@liverpool.ac.uk

Manh-Hung Nguyen
email: manh-hung.nguyen@tse-fr.eu

Covid-19 and a Green Recovery? *

Keywords: Covid-19, pollution, environmental policy, infectious disease, Green Recovery, dynamic Pigovian taxes. JEL Classification: I15, I16, Q53, H23, E22, C61

Preliminary evidence indicates that pollution increases severity and likelihood of Covid-19 infections as is the case for many other infectious diseases. This paper models the interaction of pollution and preventive actions on transmission of infectious diseases in a neoclassical growth framework where households do not take into account how their actions affects disease transmission and production activity results in pollution which increases likelihood of infections. Household can take private actions for abatement of pollution as for controlling disease transmission. Disease dynamics follow SIS dynamics. We study the difference in health and economic outcomes between the decentralized economy, where households do not internalize the externalities, and the socially optimal outcomes, and characterize the taxes and subsidies that will decentralize the socially optimal outcomes. Thus, we examine the question whether there are sufficient incentives to reduce pollution, both at the private and public levels, once its effects on disease transmission is taken into account.

Introduction

Preliminary evidence from China, Italy, USA and other countries has shown that the presence of pollution, PM (particulate matter), NOx (nitrogen oxides) and ground level ozone increases the severity and likelihood of Covid-19 infections [START_REF] Conticini | Can atmospheric pollution be considered a cofactor in extremely high level of SARS-Cov-2 lethality in Northern Italy?[END_REF], [START_REF] Martelleti | Air pollution and the novel Covid-19 disease: A putative disease risk factor[END_REF], [START_REF] Wu | Exposure to air pollution and Covid-19 mortality in the US: A nationwide cross-sectional study[END_REF], [START_REF] Yongjian | Association between short-term exposure to air pollution and Covid-19 infection: Evidence from China[END_REF]. Some studies also suggest that higher pollution increases aerosol transmission [START_REF] Setti | Airborne transmission route of Covid-19: Why 2 meters/6 feet of inter-personal distance may not be enough[END_REF], [START_REF] Qin | Longitudinal survey of microbiome associated with particulate matter in a megacity[END_REF]). These pollutants are also known to increase other infections especially acute lower respiratory infections including pneumonia, bronchitis, and influenza (Cienciwicki and Jaspers (2007), [START_REF] Horne | Short-term elevation of fine particulate matter air pollution and acute lower respiratory infection[END_REF], [START_REF] Huang | Acute effects of air pollution on influenza-like illness in Nanjing, China: A population-based study[END_REF], [START_REF] Kampa | Human health effects of air pollution[END_REF], [START_REF] Kelly | Air pollution and airway disease[END_REF], Lian, et al. (2014), [START_REF] Mehta | Ambient particulate air pollution and acute lower respiratory infections: a systematic review and implications for estimating global burden of disease, Air Quality[END_REF], [START_REF] Tasci | Relationship of meteorological and air pollution parameters with Pneumonia in elderly patients[END_REF]). 1 Thus, to control Covid-19 or other infectious diseases there are two mechanisms -preventive health expenditures which prevent infections and a pollution abatement policy which by reducing pollution reduces disease transmission. The Covid epidemic has raised expectations of a "Green recovery" where the understanding the role of pollution will increase the impetus for less polluting technologies. This paper adds to the thinking of how likely is it that pollution abatement will result once the additional channel of pollution affecting transmission of Covid-19 and other infectious diseases is taken into account.

This paper studies the interaction of these two instruments in a dynamic general equilibrium analysis by extending the economic epidemiological model of [START_REF] Goenka | Infectious diseases and economic growth[END_REF] and Goenka and Liu (2019) to model the interaction of pollution with health where the disease dynamics are of SIS type used to model Covid-19. Pollution is modeled as a flow (consistent with evidence on PM and NOx ( [START_REF] Varotsos | Scaling properties of air pollution in Athens, Greece and Baltimore, Maryland[END_REF], Windsor and Toumi (2001), [START_REF] Zeka | Short term effects of particulate matter on cause specific mortality: Effects of lags and modification by city characteristics[END_REF])) which increases with productive activity. The contact rate in the SIS model2 is increased by pollution and decreased by preventive health expenditures. The health investment is chosen to maximize discounted welfare along with current consumption and investment in physical capital. Thus, the interaction between pollution and health is endogenized and depends on optimal decisions. In the model, there are two externalities. One is the pollution externality where the pollution resulting from production increases disease transmission. The second is the disease externality, i.e. a household in deciding its optimal plans does not take into account the effect of their decsions on the evolution of the infectious disease (see [START_REF] Geoffard | Rational Epidemics and Their Public Control[END_REF], [START_REF] Gersovitz | The economical control of infectious diseases[END_REF], and Goenka and Liu (2019) for modeling of disease externalities). We study the decentralized dynamic equilibrium and contrast it with the social planner's efficient outcome that internalizes both these externalities.

We show that there can be two steady states: a disease free steady state (which is essentially the neoclassical steady state) and a disease endemic steady state if in equilibrium, the disease is infective enough. As the model is complex to solve analytically we study to what extent the outcomes are affected by the externalities through numerically analyzing the model. Since there is insufficient information so far to calibrate the effect of diseases and preventive health expenditures on disease evolution we fix the other parameters and vary the elasticity of pollution on the contact rate, the elasticity of pollution abatement and the TFP to get a sense of the qualitative properties of the model. We also characterize the dynamic Pigovian taxes that will decentralize the efficient outcomes. Analogous to the first set of numerical exercises we study how the taxes will change as we vary the two elasticities and the TFP. Several interesting results emerge. First, even if there are two externalities, two instruments are insufficient to decentralize the efficient outcome since pollution affects the economy through multiple channels. Second, the subsidy on health expenditure and pollution abatement are the same even though their effects on disease transmission need not be. The intuition is that in equilibrium, the marginal benefit of pollution abatement and health expenditure are equal as they both effect the economy only through the effect on the contact rate. Third, in the efficient outcome even if there is more abatement and health expenditures and better health outcomes, pollution is higher than in the decentralized. While there is more abatement undertaken the effect of the higher output -due to increased labor supply and output mainly due to higher labor -dominates. Thus, there is no "disease dividend" from controlling the disease in controlling pollution. This is consistent with the evidence that emission levels have gone up and even exceeded pre-lockdown levels in many regions that have controlled Covid infections (see [START_REF] Myllyvirta | China's air pollution overshoots pre-crisis levels for the first time[END_REF] for study of emissions in China). Fourth, countries with higher TFP will have higher pollution as the incentive to tax capital reduces. Thus, faster growing economies will have lower incentive to control pollution. The last two implications are consistent with the evidence that the Green Recovery that was hoped after the Covid outbreak may be evanescent (see [START_REF] Harvey | Revealed Covid recovery plans threaten global climate hopes[END_REF]).

The papers most close to this paper are Bosi andDesmarchelier (2018, 2019) and Goenka and Liu (2020). These papers use SIS dynamics in a growth model and model the disease externality. While Bosi and Desmarchelier (2018) has pollution affecting disease transmission directly as the current paper, Goenka and Liu (2019) have health capital (as does Goenka, Liu and Nguyen (2014)) and a negative effect of capital stock which can be interpreted as pollution. [START_REF] Bosi | Pollution and infectious diseases[END_REF] treat pollution as a pure externality, while the Goenka and Liu (2020) also considers health interventions. [START_REF] Bosi | Pollution effects on disease transmission and economic stability[END_REF] extend their earlier paper by making utility depend on pollution and by considering abatement of pollution which is modeled as a stock rather than flow. This paper studies the effect of both pollution and health and includes health responses as well as abatement activity.

The plan of the paper is as follows. Section 2 develops the model, Section 3 analyzes the decentralized equilibria, Section 4 the centralized equilibria where the social planner internalizes the externalities, Section 5 does the numerical analysis of the steady state equilibria, Section 6 the dynamic Pigovian taxes which decentralize the planning outcomes, and Section 7 concludes.

Model

Epidemiology We use the SIS model to study the spread of the disease. While this was the most common modeling choice to model Covid-19 (see [START_REF] Ferguson | Impact of non-pharmaceutical interventions (NPIs) to reduce COVID-19 mortality and healthcare demand[END_REF] it is not well understood for how long is disease related immunity conferred for coronaviruses such as Covid-19. The evidence is preliminary, but there is emerging evidence that subsequent immunity may not be long lasting. [START_REF] Long | Clinical and immunological assessment of asymptomatic SARS-CoV-2 infections[END_REF] 2020) use an SIRS model for medium run projections. As we are concerned about the medium to longer run in this paper we abstract from the temporary immunity phase (i.e. the state R). 3 4 The key epidemiology variables are the contact rate, α, i.e. the average number of adequate contacts of a person to catch the disease per unit time and γ, the recovery rate from the disease. In this paper we endogenize α by making it depend on health expenditures and on pollution. We treat γ as exogenous to keep the model tractable. Antivirals and anti-inflammatory drugs are now known to reduce severity of the Covid illness but these are inexpensive and widely available prior to the outbreak. Goenka, Liu and Nguyen (2014) endogenize the recovery rate in a model without pollution. The proportions of susceptible and infective is given by s t = S t N t , i t = I t N t . The population growth rate is given by

dN t /dt = (b -d)N t , b ≥ 0, d ≥ 0, b -d ≥ 0.
We assume bd ≥ 0 so that the population is not declining. As s + i = 1 and ṡ + i = 0 we can describe the epidemiology dynamics by the following equation, the law of motion of the infectives:

i = αi(1 -i) -(b + γ)i.
There are two steady states in the pure-epidemiology model, the disease free steady state

(s * , i * ) = (1, 0)
and the disease endemic steady state

(s * , i * ) = b + γ α , α -(b + γ) α .
The disease free steady state always exists, and the disease endemic steady state exists only if α > (b + γ). If this inequality is satisfied, then the disease free steady state is unstable and the disease free steady state is stable, otherwise the disease free steady state is stable. There is a trans-critical bifurcation when α = (b + γ). The basic reproduction number, R 0 = α b + γ in this model.

Production and Pollution

There are many perfectly competitive firms that maximize profit by choosing physical capital, k, and labor, l, as inputs taking the real interest rate, R, and the wage rate, W , as given. The assumptions on the production function, f (k, L) are standard and as follows.

Assumption 1. The production function f (k, l) : R 2 + → R + is C 2 , homogeneous of degree one, and

1. f 1 > 0, f 11 < 0, f 2 > 0, f 22 < 0, 2. lim k t →0 f 1 = ∞, lim k t →∞ f 1 = 0 and f (0, l) = f (k, 0) = 0.
Profit maximization implies the following marginal conditions:

R = f 1 (k, 1 -i) (1) W = f 2 (k, 1 -i)
Production also results in a flow of pollution. By pollution we mean primarily PM and NO x which have been shown to affect transmission of Covid-19 (Conticini, et

)). In the decentralized economy, this is treated as an externality. The evolution of pollution is given below.

Assumption 2. The level of pollution is a function of output y and abatement q -that is, P(y, q) where P : R 2 + → R + is C 2 . We assume

• P 1 (y, q) > 0 and P 2 (y, q) < 0.

In the paper we will model both the private choice of abatement as well as the optimal amount of abatement. In the decentralized economy, the pollution level is given as:

P = P( Ȳ , q) = P( f (k, 1 -i), q), (2)
where the Ȳ denotes that the output is taken as given so that pollution is an externality.

Labor supply: We assume that the labor force (l) consists of healthy people: l = s . Then l inherits the dynamics of l = 1i. 5 We are assuming for simplicity that all infected workers do not work (see Goenka and Liu (2020) and Goenka, Liu and Nguyen (2020a) for further discussion of this assumption).

Economic epidemiology model

In this paper we endogenize the contact rate, α. As there are no special therapies for treatment of Covid-19 other than available therapies that reduce severity of the infection, we treat γ as exogenous. 6 The contact rate depends on preventive health expenditure h and pollution P. In this paper we are treating health expenditures as only a flow of expenditures that does not accumulate as opposed to a stock of capital. This is consistent with the modeling in [START_REF] Eichenbaum | The macroeconomics of epidemics[END_REF] where NPIs that reduce infections act as a tax on consumption -what we label as health expenditures or infection preventing acitivities. 7 Thus, the contact rate is the function α(h, P).

Assumption 3. The contact rate function: α(h, P) : R + → R + is a C 2 function with • α 1 (h, P) < 0 and α 2 (h, P) > 0.
Thus, in the model the only role of pollution is to increase the contact rate. Pollution, indeed, has other affects in the economy: it can create production and consumption externalities, and increase the non-infectious mortality rate. We abstract from these effects as these have been modeled in dynamic general equilibrium models and we want to concentrate on the interaction of pollution, infectious disease transmission and preventive health measures. 8Households: We assume the economy is populated by a continuum of non-atomic identical households who are the representative decision-making agents. The size of the population in each household grows over time at the rate of bd ≥ 0, where b is the birth rate and d is the death rate. We treat the demographic parameters, b and d, as exogenous and abstract from the fertility-mortality nexus. Within each household, an individual is either susceptible (healthy and not yet infected by the disease) or infective (infected and capable of transmitting it to others).

Each household is assumed to be sufficiently large so that the proportion of the household in each disease status is identical to the corresponding population proportion. Thus, within a household, the proportion of healthy individuals is s, proportion of infected individuals is i, and proportion of recovered individuals is r. Each household understands and anticipates how the disease evolves and is fully forward-looking with regard to its possible future states as well as its present situation. However, following Gersovitz and Hammer (2004) the household considers itself small relative to the population and believes that the disease status within the household does not affect the proportion of infectives in the entire population. In particular, the household takes as given the proportion of the population that is infected, denoted as Π, and thinks the probability for the healthy individuals to contract disease is αΠ, rather than αi. As a result, the disease transmission dynamics perceived by the households is now given as follows:

i = α(h, P( Ȳ , q))Π(1 -i) -γi -bi. (3)
This captures the idea that the household is small relative to the population and does not take into account the externality on disease transmission. It is competitive "disease taking" looking only at private benefits/costs and not social benefits/costs. This distinguishes the competitive model from the social optimum where this externality is taken into account. Furthermore, the household taking the level of output as given, Ȳ chooses the amount of private abatement.

There is a two-way interaction between the economy and the disease. On the one hand, diseases have direct adverse effects on the economy by reducing the labor force participation. Being infected with a disease affects the productivity of an individual. As make the simplifying assumption that an infected individual is incapacitated by the disease or that the productivity falls to zero, For each household labor supply L is given by the proportion of the healthy individuals, i.e. L = S and dynamics inherits the dynamics of (1i).

The representative household's preferences are given as:

∞ 0 e -ρt u(C)N t dt = ∞ 0 e -(ρ-b+d)t u(C)N 0 dt, (4)
where ρ is the discount factor with ρ > bd, and the initial size of household is assumed to be one. The assumptions on the felicity function are given below. We further assume there is full insurance within each household and all individuals have the same consumption irrespective of their health status. This is indeed optimal, if the household welfare aggregator is concave.

Assumption 4. The household's felicity function, u : R ++ → R is C 2 with u c > 0 and u cc < 0, jointly with the limit conditions: lim c→0 + u c = ∞ and lim c→+∞ u c = 0.

Households take the interest rate R and wage W as given, rent out physical capital K and choose how much to consume, c, how much to invest in capital, v, spend in disease prevention activities, h, and in pollution abatement, q. Thus, the budget constraint is:

C + v + h + q = Rk +W l. ( 5
)
The evolution of the capital stock is given by:

k = v + δ k -k(b -d) (6) (7)
where δ k ∈ (0, 1] is the depreciation rates of physical capital.

The equation ( 6) can be written as

k = Rk +W l -c -h -q -δ k -k(b -d)
Given Π, Ȳ , R,W the representative household maximizes the intertemporal utility. Therefore, each household solves the following maximization problem:

max {c,h,q} ∞ 0 e -(ρ-b+d)t u(C)N 0 dt (8) k = Rk +W (1 -i) -c -h -q -δ k -(b -d)k i = α(h, P( Ȳ , q))Π(1 -i) -γi -bi
The control variables are c, h, q, the state variables are k, i.

Decentralized economy

We define the competitive equilibrium in the decentralized economy. It is a standard definition with the condition that the perceived proportion of infected by households, Π is equal to the actual proportion of infected in the population, i, and Ȳ = Y .

Definition 1. A competitive equilibrium is a feasible allocation {c, k, h, q, i} and given {Π, Ȳ , R,W } 1. Households solve the maximization problem (8).

2. Firms maximize profits, given by equation (1).

3. The capital market, labor market and goods market clear.

Pollution satisfies (2) with

Ȳ = f (k, 1 -i).
5. Since each household is representative of the population, in equilibrium, Π = i.

We now characterize the dynamical system that defines the dynamic general equilibrium of the economy.

The current value Lagrangian for the optimization household problem is:

L = u(c) + λ 1 [Rk +W (1 -i) -c -h -q -δ k -(b -d)k] + λ 2 [α(h, P( Ȳ , q))Π(1 -i) -γi -bi] + µ 1 i + µ 2 h
Incorporating the equilibrium conditions

R = f 1 (k, 1 -i) W = f 2 (k, 1 -i) P = P( Ȳ , q) = P( f (k, 1 -i), q) Π = i
we can write the conditions for an equilibrium in the economy.

The equilibrium in the decentralized economy is determined by the following equations (the first order conditions and the transversality conditions to the household problem incorporating the equilibrium conditions):

k = f (k, 1 -i) -c -h -q -δ k -(b -d)k (9) i = α(h, P( f (k, 1 -i), q))i(1 -i) -γi -bi (10) u (c) = λ 1 ( 11
)
λ 1 = λ 2 α 1 (h, P( f (k, 1 -i), q))i(1 -i) (12)
λ 1 = λ 2 α 2 (h, P( f (k, 1 -i), q))P 2 ( f (k, 1 -i), q)i(1 -i) (13) λ1 = λ 1 [ρ + δ + b -d -f 1 (k, 1 -i)] (14) λ2 = ρλ 2 + λ 1 f 2 (k, 1 -i) + λ 2 [α(h, P( f (k, 1 -i), q))i + γ + b] (15)
µ 1 ≥ 0, i ≥ 0, µ 1 i = 0, µ 2 ≥ 0, h ≥ 0, µ 2 h = 0, lim t→∞ e -θt λ 1 k = lim t→∞ e -θt λ 2 i = 0.
As the economy is a neo-classical economy with a bounded capital stock and i lies in a bounded interval, the transversality conditions are satisfied, and in the subsequent discussion we suppress these.

Note that the optimization problem has non-convex constraints on the state variable i and the usual Arrow and Mangasarian condition do not apply. Goenka, Liu and Nguyen (2014) have however, shown existence and sufficiency for the SIS model and we concentrate on studying the first order conditions which will characterize the dynamical system of the economy. 9

Steady states

We know characterize the steady state competitive equilibria for the decentralized economy. As in the pure epidemiology model there are two equilibria which depend on the basic reproduction number, i.e. determined by the contact rate. However, unlike the pure epidemiology model it is endogenous depending on the abatement and disease preventive activities.

Proposition 1. There always exists a unique disease free steady state with i * = 0, h * = 0 and q * = 0. The economic variables k * and c * are determined by

f 1 (k, 1) = ρ + δ + b -d f (k, 1) = c + δ k + (b -d)k.
In the disease free steady state pollution plays no role in role the determination of equilibrium, and the economy is in the neoclassical steady state. In the disease free steady state, there is no abatement as the only effect of pollution in this model is on disease transmission. As there is no disease prevalence, there is also no health preventive expenditure. Let us call this ᾱ. If ᾱ < b + γ the disease is eradicated and the steady state is locally stable, and if ᾱ. If ᾱ > b + γ the disease free steady state is unstable.

The disease endemic steady state is a solution to the system of equations (9 -15). It will exist if when the contact rate is high enough so that s * < 1, i.e. α(h * , P * ) > b + γ or the equilibrium endogenous contact rate R * 0 > 1.

Proposition 2. There exists a disease endemic steady state where i * , k * , h * , q * and c * are determined by:

i = 1 - b + γ α(h, P( f (k, 1 -i), q)) (16)
α 1 (h, P( f (k, 1 -i), q)) = α 2 (h, P( f (k, 1 -i), q))P 2 ( f (k, 1 -i), q) (17)
f 1 (k, 1 -i) = ρ + δ + b -d (18)
-

f 2 (k, 1 -i)α 1 (h, P( f (k, 1 -i), q))i(1 -i) = ρ + α(h, P( f (k, 1 -i), q)) (19)
f (k, 1 -i) = c + h + q + δ k + (b -d)k (20)
Proof. From equation (10) i = 0, we have either i * = 0 or i * = 1 -b+γ α(h,P) . Note that this implies α(h, P)i = α(h, P) -(b + γ).

From equation ( 12) and ( 13), we have α 1 (h, P) = α 2 (h, P)P 2 (y, q).

In equilibrium the marginal benefit of health expenditure h should be the same as the marginal benefit of pollution abatement q as both health expenditure and pollution abatement only affect the economy through their impact on the contact rate α.

From λ1 = 0, we have

f 1 (k, 1 -i) = ρ + δ + b -d,
which is the standard marginal benefit of physical capital equals to its marginal cost. From λ2 = 0, we have

λ 1 f 2 (k, 1 -i) = -λ 2 ρ -λ 2 [α(h, P)i + γ + b],
which implies the marginal benefit of disease controlling (one unit of reduction in i -the proportion of the infected) equals to its marginal cost. The L.H.S of the above equation is the marginal benefit, as with one unit of reduction in the proportion of the infected i, the labor force increases by one unit and generates the marginal product f 2 (k, 1i). The R.H.S is the marginal cost of disease controlling. Note that the shadow value of the infectedλ 2 is negative. When there is one unit of reduction in the proportion of the infected, the proportion of the susceptible increases by one unit.

As there are more susceptible around, there are more infections.

Then, we substitute into equation ( 12), and we have

-f 2 (k, 1 -i)α 1 (h, P)i(1 -i) = ρ + α(h, P).
Note, that in equilibrium from ( 16) we have R * 0 > 1. Thus, in the competitive equilibrium the disease is endemic. Whether this is the case depends on not only the disease characteristics, i.e. the function α, but also the deeper economic parameters which determine whether it is in the interest of the households to take sufficient actions to bring the contact rate below the threshold. There is a tension on what will happen once the contact rate drops below 1, whether the economy will converge to a disease free steady state. It depends on whether the disease free steady state is stable or not and depends on the bifurcation when the contact rate is 1. In this paper, we focus on the difference between the private and public actions and do not investigate this issue in further depth. The paper Goenka and Liu (2013) and Goenka, Liu and Nguyen (2014) study these issues in further depth in a model without pollution in discrete time and continuous time respectively.

The Centralised Economy

In the centralized economy, the social planner takes into account both pollution externalities and disease externalities, i.e. the true law of motion for the disease and affect of output on pollution are taken into account. Therefore, the social planner solves the following maximization problem:

max {c,h,q} max {c,h,q} ∞ 0 e -(ρ-b+d)t u(C)N 0 dt k = f (k, 1 -i) -c -h -q -δ k -(b -d)k i = α(h, P( f (k, 1 -i), q))i(1 -i) -γi -bi
The equilibrium in the centralized economy is determined by the following equations (suppressing the transversality conditions):

k = f (k, 1 -i) -c -h -q -δ k -(b -d)k (21) i = α(h, P( f (k, 1 -i), q))i(1 -i) -γi -bi (22) u (c) = λ 1 ( 23
)
λ 1 = λ 2 α 1 (h, P( f (k, 1 -i), q))i(1 -i) (24)
λ 1 = λ 2 α 2 (h, P( f (k, 1 -i), q))P 2 ( f (k, 1 -i), q)i(1 -i) (25) λ1 = λ 1 [ρ + δ + b -d -f 1 (k, 1 -i)] + [-λ 2 α 2 (h, P)P 1 (y, q) f 1 (k, 1 -i)(1 -i)i] (26) λ2 = ρλ 2 + λ 1 f 2 (k, 1 -i) + λ 2 [α(h, P( f (k, 1 -i), q))i + γ + b] + +[λ 2 α 2 (h, P)P 1 (y, q) f 2 (k, 1 -i)(1 -i)i] + [-λ 2 α(h, P)(1 -i)] (27)
Note that there is an additional term in ( 26) as compared to [START_REF] Goenka | Infectious diseases and economic growth[END_REF] in the decentralized economy which arises from taking the effect of output on pollution and hence, disease transmission; and two additional terms in ( 27) as compared to (15) that arise from taking into account the effects of infections on labor supply, and hence output, pollution and disease transmission and the second which internalizes the disease externality.

Steady states

There always exists a unique disease free steady state with i * = 0, h * = 0 and q * = 0. This is exactly the same as the one in decentralized economy as it is the neoclassical steady state with h * = q * = 0.

As in the decentralized economy there is also a disease endemic steady state.

Proposition 3. There exists a disease endemic steady state where i * , k * , h * , q * and c * are determined by:

i = 1 - b + γ α(h, P( f (k, 1 -i), q)) (28)
α 1 (h, P( f (k, 1 -i), q)) = α 2 (h, P( f (k, 1 -i), q))P 2 ( f (k, 1 -i), q) (29)
f 1 (k, 1 -i) = ρ + δ + b -d + [- P 1 ( f (k, 1 -i), q) f 1 (k, 1 -i) P 2 ( f (k, 1 -i), q) ] ( 30
) -f 2 (k, 1 -i)α 1 (h, P( f (k, 1 -i), q))i(1 -i) + [α(h, P( f (k, 1 -i), q))(1 -i)] = (31) = ρ + α(h, P( f (k, 1 -i), q)) + [α 2 (h, P( f (k, 1 -i), q))P 1 ( f (k, 1 -i), q) f 2 (k, 1 -i)(1 -i)i] f (k, 1 -i) = c + h + q + δ k + (b -d)k (32)
Proof. The proof is the similar as the one in decentralized economy and thus omitted here.

Compared with the decentralized economy, there are two differences. One difference is equation [START_REF] Qin | Longitudinal survey of microbiome associated with particulate matter in a megacity[END_REF], which says the marginal social benefit of physical capital should equal to the marginal social cost. In the centralized economy, the social planner takes into account the negative externality of pollution on disease transmission, and thus there is an additional cost to physical capital investment. When physical capital increases, output increases, which leads to more pollution and higher contact rate for disease transmission. This is captured by the term [-P 1 ( f (k,1-i),q) f 1 (k,1-i)

P 2 ( f (k,1-i),q)
]. The other difference is equation [START_REF] Ripperger | Orthogonal SARS-CoV-2 serological assays enable surveillance of low-prevalence communities and reveal durable humoral immunity[END_REF], which says the marginal social benefit of disease controlling equals to the marginal social cost. In the centralized economy, there are two additional terms in equation [START_REF] Ripperger | Orthogonal SARS-CoV-2 serological assays enable surveillance of low-prevalence communities and reveal durable humoral immunity[END_REF]. When the social planner takes into account the negative externality of pollution there is additional cost of an increase in labor input or reduction in the proportion of the infected. When the proportion of the infected decreases, the proportion of the susceptible or the labor force increases, which leads to more output and pollution, and then higher contact rate for disease transmission. This is captured by the term [α 2 (h,

P( f (k, 1 -i), q))P 1 ( f (k, 1 -i), q) f 2 (k, 1 -i)(1 -i)i].
Moreover, the social planner takes into account the disease externality. That is, there is additional benefit from controlling disease, as the social planner further takes into account the behavior is going to affect the proportion of the infected. This is captured by the term α(h, P( f (k, 1i), q))(1i). Thus, compared with the decentralized economy, the centralized economy takes into account both negative pollution externalities and positive disease controlling externality. To compare the abatement and health expenditures in the centralized and decentralized economies we have to use numerical methods as the system of non-linear equations are too complex to compare directly.

Model Simulations

As the model is too complex for closed form solutions or doing comparative statics analytically, in this section, we calibrate the model and do comparative statics numerically to understand the interaction of the different components. We focus on examining the parameters where pollution can affect the disease transmission. That is, we vary the elasticity of pollution on the disease contact rate, the elasticity of pollution abatement, and the productivity in the economy. The last is important as it tries to ascertain whether more productive economies will have different responses and outcomes. The analysis here focuses on the equilibrium steady states before and after the change as we want to capture the medium to longer term effects when investment and returns to labor and capital have adjusted.

The following functional forms and parameters are chosen in line with the literature. The production function is assumed to be Cobb Douglas:

y = f (k, 1 -i) = Ak β (1 -i) 1-β with A = 1 and β = 0.36.
Physical capital depreciates at the rate δ = 0.05 and discount rate ρ = 0.055. The utility function is of the CES form U(c) = c 1-σ 1-σ and we choose σ = 1, that is, the utility function is log utility. We set the birth rate b = 3% and death rate d = 1.5%. The recovery rate is γ = 0.2.

We do not have enough empirical evidence in suggesting for functional form for contact rate function α(h, P) and pollution function P(y, q). Therefore, the contact rate function is chosen in line with the assumption on α(h, P) and large enough to generate an endemic steady state in the simulation. We assume contact rate function is a power function:

α(h) = ε 0 (h + ε 1 ) ε 2 (P + ε 3 ) ε 4 with ε 0 = 0.2, ε 1 = 0, ε 2 = -0.2, ε 3 = 0 and ε 4 = 0.2 in
the baseline specification. The pollution function is also chosen in line with the assumptions. We assume P(y, q) = φ 0 f (k, 1i)φ 1 (q + φ 2 ) φ 3 with φ 0 = 1, φ 1 = 1, φ 2 = 0 and φ 3 = 0.5 in the baseline specification.

Figure 1, 2 and 3 are the simulation results for varying the elasticity of pollution on contact rate function (ε 4 ), the elasticity of abatement on pollution (φ 3 ) and the productivity (A), respectively. The parameters are chosen such that disease endemic steady states exist for both the decentralized and centralized economy. So we can focus on how changes in those parameters change economic variables. The solid line is the decentralized economy (where the disease and pollution externalities have not been internalized). The dashed line is the centralized economy (where the disease externality and pollution externalities have been internalized). Across all the three figures, if we compare the decentralized economy with the centralized economy, the pictures are very similar. The social planner when taking the externalities into account is able to achieve lower contact rates in equilibrium with higer health expenditures. As a result, the labor force is larger and output higher. The capital stock is lower in the planning solution. While the abatement is higher in the planning solution, paradoxically pollution is also higher. This is being driven by the fact that in the planning solution, the output is higher and even thought there is greater abatement, the net effect of the higher output dominates and pollution is higher. Thus, even when the planner takes into account the deleterious effect of pollution on health outcomes, the efficient outcome has higher pollution. If an economy has higher TFP or not does not change the qualitative effects, except that a more productive economy will have better economic outcomes as well as higher pollution. The health outcomes and the abatement is not affected by a change in TFP.

In the pure epidemiology model, disease free steady state always exists, and disease endemic steady state only exists when contact rate is high enough, that is, α > b + γ or R 0 = α b+γ > 1. When there is only one disease free steady state, it is stable. When both disease free and disease endemic steady states co-exist, disease free steady state is unstable and disease endemic steady state is stable. The same applies to the economic epidemiological models here for both decentralized economy and centralized economy. The only difference is that the contact rate α or R 0 is endogenous, and thus the cut-off points of the contact rate for the existence of disease endemic steady state are different in the decentralized and centralized economies. Since the social planner takes the externalities into account, and is able to achieve lower contact rates in equilibrium, with the same parameter values it is more likely to have disease eradicated in the centralized economy. That is, the cut-off point of the contact rate parameter for the existence of disease endemic steady state in the centralized economy is higher than the one in the decentralized economy. To show this, we have chosen the recovery rate γ = 0.5 such that when we vary the contact rate parameter ε 0 from 0.01 to 0.3, there are changes in steady states in both decentralized and centralized economy. The simulation results is shown in Figure 4. We can see that the cut-off points to have disease endemic steady state is ε 0 = 0.08 for the decentralized economy and ε 0 = 0.12 for the centralized economy. When the contact rate parameter ε 0 is small enough (below 0.08) such that α < b + γ, we can see there is disease free steady state in both decentralized and centralized economy, The proportion of the infected is zero and all variables are the same in both economies. When ε 0 is between 0.08 and 0.12, that is, the contact rate rises, in the centralized economy, as α < b + γ there is only one disease free steady state, and disease endemic steady state does not exist. In contrast, in the decentralized economy, disease endemic steady state exists. 10 For the disease endemic steady state in the decentralized economy, the fraction of the infected is positive and physical capital, output and consumption are lower, compared with the centralized economy. When ε 0 is above 0.12, for both decentralized and centralized economies, as the contact rate is high enough, disease endemic steady state exists. 11

Public Policy

We study the dynamic Pigovian taxes that will decentralize the efficient competitive equilibrium. Even though there are two externalities: the disease externality and the pollution externality we need four taxes and subsidies to decentralize the efficient outcome. The reason is that these the externalities affect the economy in a complex way: pollution not only affects the contact rate, as the private abatement is not at the efficient level, but also through the change in labor supply through disease incidence the marginal product of labor. Thus, there are two wedges introduced by the pollution externality. The disease externality affects the private health expenditures. A fourth tax is needed to meet the balanced budget or self-financing nature of the tax-subsidy policy.

Thus, we introduce tax policies -capital income tax τ k and labor income tax τ l , and subsidies -health expenditure subsidy τ h and pollution abatement subsidy τ q . The decentralized economy with public polices is as the follows:

max {c,h,q} ∞ 0 e -ρt u(c)dt k = (1 -τ k )Rk + (1 -τ l )W (1 -i) -c -(1 -τ h )h -(1 -τ q )q -δ k -(b -d)k i = α(h, P( Ȳ , q))Π(1 -i) -γi -bi
Then, we incorporate equilibrium conditions, which is the same as those in decentralized economy. Moreover, there is a balance budget constraint:

τ k Rk + τ l W (1 -i) = τ h h + τ q q. ( 33
)
The equilibrium in the decentralized economy with public policies is determined by the following equations:

k = f (k, 1 -i) -c -h -q -δ k -(b -d)k i = α(h, P( f (k, 1 -i), q))i(1 -i) -γi -bi u (c) = λ 1 λ 1 = λ 2 α 1 (h, P( f (k, 1 -i), q))i(1 -i) 1 1 -τ h λ 1 = λ 2 α 2 (h, P( f (k, 1 -i), q))P 2 ( f (k, 1 -i), q)i(1 -i) 1 1 -τ q λ1 = λ 1 [ρ + δ + b -d -(1 -τ k ) f 1 (k, 1 -i)] λ2 = ρλ 2 + λ 1 (1 -τ l ) f 2 (k, 1 -i) + λ 2 [α(h, P( f (k, 1 -i), q))i + γ + b]
Proposition 4. In the decentralized economy with public policies, there exists a disease endemic steady state where i * , k * , h * , q * and c * are determined by: i

= 1 - b + γ α(h, P( f (k, 1 -i), q)) (34)
α 1 (h, P( f (k, 1 -i), q)) 1 1 -τ h = α 2 (h, P( f (k, 1 -i), q))P 2 ( f (k, 1 -i), q) 1 1 -τ q (35) (1 -τ k ) f 1 (k, 1 -i) = ρ + δ + b -d (36) - 1 -τ l 1 -τ h f 2 (k, 1 -i)α 1 (h, P( f (k, 1 -i), q))i(1 -i) = ρ + α(h, P( f (k, 1 -i), q)) (37) f (k, 1 -i) = c + h + q + δ k + (b -d)k (38)
Next, we are going to show how we design tax and subsidy policies, such that the decentralized economy can replicate the allocations from the centralized economy. If we compare equation ( 29) with [START_REF] Varotsos | Scaling properties of air pollution in Athens, Greece and Baltimore, Maryland[END_REF], it is easy to see that the subsidy for health expenditure τ h should be equal to the subsidy for pollution abatement τ q :

τ h = τ q . ( 39
)
Note that this is independent of elasticities of pollution and health expenditures on the contact rate.

Then, by comparing equation ( 30) with [START_REF] Wajnberg | Humoral immune response and prolonged PCR positivity in a cohort of 1343 SARS-CoV 2 patients in the New York City region[END_REF], we can derive capital income tax:

τ k = - P 1 ( f (k, 1 -i), q) P 2 ( f (k, 1 -i), q) . ( 40
)
Since P 1 > 0 and P 2 < 0, the capital income tax τ k > 0. If we compare equation ( 31) with (37), we get τ hτ l 1τ h = α 2 (h, P( f (k, 1i), q))P 1 ( f (k, 1i), q) f 2 (k, 1i)iα(h, P( f (k, 1i), q)) f 2 (k, 1i)α 1 (h, P( f (k, 1i), q))i .

Thus, we have the following proposition.

Proposition 5. The tax and subsidy policies (τ k , τ l , τ h , τ q ) are determined by equation ( 33), ( 39), ( 40) and [START_REF] Yongjian | Association between short-term exposure to air pollution and Covid-19 infection: Evidence from China[END_REF], where the economic variables i, k, h, q and c are the equilibrium allocations from the centralized economy.

To understand the taxes and subsidies we do a similar exercise as in the previous section of varying the elasticity of pollution, the elasticity of abatement and the TFP. Interestingly, for each of the exercises, the subsidy on health and abatement decrease and the primary mechanisms are the direct taxes on labor and capital income. The effect of increasing elasticity of pollution and contact rate and on abatement rate is different. As elasticity of pollution on contact rate increases, the capital income is taxed at a higher rate and labor income at a lower rate. However, when elasticity of abatement increases, i.e. abatement is more effective, capital income is taxed at a lower rate but to maintain budget balance, labor income taxes are increased. As TFP increases,

Conclusion

This paper studies the interaction of pollution with transmission of diseases. In a decentralized economy there is the pollution externality and a disease transmission externality. As one would expect, the level of abatement of pollution and preventive health expenditures are lower than the centralized situation where the externalities are internalized. While the centralized outcomes can be decentralized through dynamic Pigovian taxes, with higher productivity the level of pollution in fact goes up in the efficient outcome. The control of the disease interacts with higher productivity, and even though more is spent on abatement, the net effect is that pollution goes up. This is consistent with the recent evidence where during lockdown as mobility and activity declined, so did pollution levels. However, this was temporary and since then pollution levels have gone up [START_REF] Kumari | Impact of lockdown on air quality over major cities across the globe during COVID-19 pandemic[END_REF]). Thus, expectation of a Green Recovery may be illusory.

  using data from China find evidence consistent with steep decline in 2-3 months. Similar results were found in Ibarrando, et al. (2020), Isho, et al. (2020), Riperger, et al. (2020), Ward, et al. (2020). On the other hand Wajnberg, et al. (2020) and Sekine, et al. (2020) find evidence suggesting longer immunity. As a modeling stategy Kissler, et al. (

  al. (2020), Martelleti and Martelleti (2020), Setti, et al. (2020), Qin, et al. (2020), Wu, et al. (2020), and Yongjian, et al. (2020)) and increase other infections such as acute lower respiratory infections including pneumonia, bronchitis and influenza (Cienciwicki and Jaspers (2007), Horne, et al. (2018), Huang, et al. (2016), Kampa and Castanas (2008), Kelly and Fussell (2011), Lian, et al. (2014), Mehta, et al. (2013), Tasci, et al. (2018)). We treat this as a flow, i.e. it does not accumulate, as evidence suggests that it does not accumulate (Varotsos et al. (2005), Windsor and Toumi (2001), Zeka et al. (

Figure 1 .

 1 Figure 1. The simulation results -varying the elasticity of pollution on contact rate

Figure 2 .

 2 Figure 2. The simulation results -varying the elasticity of abatement on pollution

Figure 3 .

 3 Figure 3. The simulation results -varying productivity

Figure 4 .

 4 Figure 4. The simulation results -disease free and disease endemic steady states

Figure 5 .

 5 Figure 5. Tax and subsidy policies -varying the elasticity of pollution on contact rate

Figure 6 .

 6 Figure 6. Tax and subsidy policies -varying the elasticity of abatement on pollution

Figure 7 .

 7 Figure 7. Tax and subsidy policies -varying productivity

  . The population (N t ) is divided in two classes: susceptible, healthy and who can catch the disease (S t ) and infective, those infected and capable of transmitting the disease (I t ). with S t + I t = N t .dS t /dt = bN t -dS t -αS t I t /N t dI t /dt = αS t I t /N t -γI t -dI t S t , I t , N t ≥ 0, ∀t; S 0 , I 0 , N 0 > 0 with N 0 = S 0 + I 0 ,where b is the exogenous birth rate, d is exogenous death rate, we assume that d ≤ b. One of the features of Covid-19 is disease related mortality. The case fatality rate (CFR) is estimated to be around 1.4%, i.e. the percentage of the individuals who are known to be infected die from the disease. This has deep implications for thinking about the control of Covid-19. Our paper studies the trade-offs between controlling pollution and disease prevention and in this we abstract from it. See Goenka, Liu and Nguyen (2020a) on modeling mortality in a SIS model without pollution.

Pollution also increases incidence non-communicable diseases such as asthma, COPD, and other respiratory diseases as well cardiovascular diseasese. SeeGoenka, et al. (2020) for dynamic models studying nexus of pollution and non-communicable diseases but this is not the focus of this paper.

[START_REF] Bosi | Pollution effects on disease transmission and economic stability[END_REF] This modeling choice is discussed in detail in the following section

This is also consistent with many of the other infectious diseases that are the main sources of disease related mortality, in particular malaria, tuberculosis, dengue, and influenza also do not have disease related immunity. While an individual may have immunity to a particular strain of influenza for a short period, the virus mutates and there is no lasting immunity. HIV/AIDS is a disease of SI class and its epidemiology is not captured by either SIS or SIR models.

Goenka, Liu and Nguyen (2020b) model the effect of disease mortality in a SIR model.

We take labor supply by the healthy workers as inelastic. If labor supply is elastic then under standard assumption of preferences u(c, l) > 0 the qualitative features of the model are not affected. (see[START_REF] Goenka | Infectious diseases and endogenous fluctuations[END_REF] for a SIS model with elastic labor supply. If we drop this assumption then labor supply can be an independent source of non-linear dynamics and cycles.

[START_REF] Goenka | Infectious diseases and economic growth[END_REF] we modelled γ as a function of h.

Bosi and Desmarchellier (2018) have α(P), Goenka, Liu and Nguyen (2014) model this as α(h), Goenka and Liu (2019) have α(h, k, e) where k, h, e are stocks of physical, health and human capital in an endogenous growth model.

[START_REF] Goenka | Pollution, mortality and time consistent abatement taxes[END_REF] study optimal policies when pollution increases mortality through noncommunicable diseases.

The sufficiency conditions have been extended to account for mortality in Goenka, Liu and Nguyen (2020a) and for the SIR model with mortality in Goenka, Liu and Nguyen (2020b).

Note that there is also disease free steady state (not shown in the figure).

Note that there is also disease free steady state (not shown in the figure).

* Manh-Hung Nguyen acknowledges support from ANR under grant ANR-17-EURE-0010 (Investissements d'Avenir program). We thank participants at the Economic Modelling Workshop especially Angus Chu,


Jérémy Begey
email: jeremy.begey@etu.unistra.fr

Marc Vedrines

Pierre Renaud

Nicolas Andreff

Modeling and Control of a Redundant Tensegrity-based Manipulator

Keywords: Tensegrity Mechanisms, Redundant Manipulator, Kinematic Control. Jérémy Begey

Tensegrity-based mechanisms draw attention in particular for their deployability and compliance. However, task-based design and control of such systems are still open topics. In a previous work, a tensegrity-based manipulator was designed to respect the remote center of motion constraint encountered in medical applications. Only the workspace was then analyzed. Here, we develop the kinematic model of this manipulator and then exploit it for the control. Such a manipulator is redundant. The use of redundancy is discussed and evaluated in simulation with two control schemes using Jacobian based controllers.

Introduction

Tensegrities are pre-stressed structures composed of bars and cables, firstly exploited [START_REF] Snelson | Continuous tension, discontinuous compression structures[END_REF] for their high resistance. Several authors focused on actuating these structures to design tensegrity mechanisms. If some structural elements are chosen elastic, these mechanisms can be compliant with controllable stiffness. Therefore, these mechanisms are of high interest when interactions with the environment can occur, particularly when contact management is critical. For instance, it was used for grasping tasks [START_REF] Sumi | Compliant Gripper Based on a Multistable Tensegrity Structure[END_REF], design of flexible mobile robot [START_REF] Bakker | Design of an Environmentally Interactive Continuum Manipulator[END_REF] or to carry out medical procedures [START_REF] Begey | Toward a design method for tensegrity-based medical robots[END_REF]. In [START_REF] Begey | Toward a design method for tensegrity-based medical robots[END_REF], a tensegrity-based manipulator has been proposed to manage a Remote Center of Motion (RCM) constraint often met in medical procedures. It is introduced in Fig. 1, and presented in detail in section 2. The device is built for quasi-static positioning. Only preliminary analysis of the robot workspace was

R 0 ϕ l p ρ c1 ρ c2 ρ b2 ρ b1 A 1 A 2 A 3 A 4 B 4 B 3 B 2 B 1 x 0 y 0 O RCM l p 2l p O 0 O b O m L
Fig. 1 The considered tensegrity-based manipulator composed of two tensegrity mechanisms: a bar-actuated one in green and a cable-actuated one in blue. yet achieved. Further development is hampered by the absence of analytical Forward Kinematic (FK) model and the control strategy. In this paper, kinematics are developed and used to investigate manipulator control.

Solutions to the FK problem correspond to stable configurations of the prestressed mechanism. Amongst others, energetic approaches have been proposed [START_REF] Juan | Tensegrity frameworks: Static analysis review[END_REF]. Depending on the type of elastic elements, solving the FK problem remains complex [START_REF] Bayat | Closed-Form Equilibrium Analysis of Planar Tensegrity Structures[END_REF][START_REF] Wenger | Kinetostatic Analysis and Solution Classification of a Planar Tensegrity Mechanism[END_REF] and it is often treated numerically [START_REF] Bayat | Closed-Form Equilibrium Analysis of Planar Tensegrity Structures[END_REF][START_REF] Begey | Toward a design method for tensegrity-based medical robots[END_REF][START_REF] Boehler | Definition and Computation of Tensegrity Mechanism Workspace[END_REF]. In this paper, we show using an energetic approach that an analytical solution can be determined for the considered manipulator. This constitutes the first contribution of the paper.

The proposed manipulator is considered for providing a RCM in the plane. Therefore, this four actuator mechanism is redundant with respect to this task. Control of redundant tensegrities has been considered to achieve shape control while optimizing a given criterion and get for instance time-optimal or energy-optimal control [START_REF] Aldrich | Time-energy optimal control of hyper-actuated mechanical systems with geometric path constraints[END_REF][START_REF] Sultan | Tensegrity deployment using infinitesimal mechanisms[END_REF]. In conventional robotics, control of redundant systems is making use of the kinematic Jacobian [START_REF] Siciliano | Kinematic control of redundant robot manipulators: A tutorial[END_REF]. We show in this paper that the Jacobian matrix can be derived analytically so such methods are well suited. Control schemes exploiting the redundancy are then proposed and evaluated in simulation as a second contribution.

The manipulator is described and modeled in Section 2. The control schemes and the obtained results in simulation are then discussed in Section 3. Conclusions are finally drawn in Section 4.

Description and modeling of the manipulator

The considered mechanism is planar and composed of two serially assembled Xshaped tensegrities called Snelson Crosses (SC) [START_REF] Snelson | Continuous tension, discontinuous compression structures[END_REF]. A bar-actuated SC, displayed at the bottom of Fig. 1, is mounted on the base. It is actuated by modifying the lengths ρ b1 and ρ b2 of the bars attached to nodes A 1 , B 2 and B 1 , A 2 respectively. The SC on top is cable-actuated with control of the lengths ρ c1 and ρ c2 of nonelastic cables attached to nodes A 3 , A 4 and B 3 , B 4 respectively. The bars of this SC have a length L. Following [START_REF] Begey | Toward a design method for tensegrity-based medical robots[END_REF], analysis is conducted while neglecting gravity forces. Thanks to the intermediate component placed between the SCs, the static models of the SCs are decoupled, and the manipulator can be assessed by independently analyzing each SC. For sake of symmetry, two elementary springs are placed on the top and bottom sides of each SC. Two serially connected springs are then similarly placed between the nodes A 1 , A 2 and B 1 , B 2 , with all springs of stiffness 2K and free-length l 0c /2 (resp. l 0b /2) for the cable-(resp. bar-) actuated SC. We will refer in the following to a spring as the equivalent elastic element of the two serially attached springs on each side. The end-effector of the manipulator is the platform on top of the mechanism (Fig. 1). For given position of the remote center of motion O RCM and orientation ϕ, it is simple to determine the corresponding coordinates of O m . The FK problem consists then to determine from the joint coordinates q = [ρ b1 , ρ b2 , ρ c1 , ρ c2 ] T the end-effector pose x = [x, y, ϕ] T , with (x, y) the position of O m the barycentre of points A 4 and B 4 , and ϕ the orientation. In [START_REF] Begey | Toward a design method for tensegrity-based medical robots[END_REF], it was observed with numerical analysis that the bar-actuated SC shape is a parallelogram for all reachable configurations. We could also observe that these configurations seem diamond-shaped. Thus, all springs would be of same length which would be expressed in Eq. ( 1), with L A i B j the length between nodes A i and B j . In [START_REF] Arsenault | Kinematic and static analysis of a planar modular 2-DoF tensegrity mechanism[END_REF], the stable configuration of a cable-actuated SC was analyzed and Eq. ( 2) was in addition demonstrated for zero free-length springs. Again using numerical analysis, Eq. ( 2) was observed to be valid in [START_REF] Begey | Toward a design method for tensegrity-based medical robots[END_REF] for springs with non-zero free-length.

L A 1 B 1 = 1 2 ρ 2 b1 + ρ 2 b2 (1) L A 3 B 3 = L 2 -ρ c1 ρ c2 (2)
To verify the validity of expressions (1) and ( 2) for springs with non-zero freelength, the conditions of tensegrity mechanism equilibrium configuration [START_REF] Boehler | Definition and Computation of Tensegrity Mechanism Workspace[END_REF] are derived analytically. Let q 1 = [ρ b1 , ρ b2 ] T and q 2 = [ρ c1 , ρ c2 ] T be the sets of joint coordinates of the bar-and the cable-actuated SCs. The SCs are compliant so q ui designates sets of unconstrained joint coordinates. Existence of a stable static equilibrium can then be expressed from the mechanism potential energy U i (q i , q ui ) (Eq. ( 3)), verifying also that the tensions in the elements in traction are positive.

∂U i (q i , q ui ) ∂ q ui = 0 ∂ 2 U i (q i , q ui ) ∂ q 2 ui > 0 i = {1, 2} (3)
For both SC, the potential energy is written with

q u1 = [L A 1 B 1 , L A 1 A 2 , L B 1 B 2 ]
T for the bar-actuated SC and q u2 = L A 3 B 3 for the cable-actuated SC, having respectively three and one unconstrained coordinates [START_REF] Bayat | Closed-Form Equilibrium Analysis of Planar Tensegrity Structures[END_REF]. It gives:

U 1 = 1 2 K (L A 2 B 2 (q 1 , q u1 ) -l 0b ) 2 + j=3 ∑ j=1 (q u1 ( j) -l 0b ) 2 U 2 = 1 2 K (L A 4 B 4 (q 2 , q u2 ) -l 0c ) 2 + (q u2 -l 0c ) 2 (4)
The first and second derivatives are then derived and the lengths in q ui are replaced by their proposed expressions (1) or [START_REF] Arsenault | Kinematic and static analysis of a planar modular 2-DoF tensegrity mechanism[END_REF]. It then leads that all the first derivatives are equal to zero. The expressions of the second derivatives are not detailed here for paper clarity, but are strictly positive if the components of q i , the elongation and the stiffness of the springs are strictly positive, which is always verified. Therefore, these configurations correspond to tensegrity configurations. However, here the springs of the bar-(resp. cable-) actuated SC present a free-length l 0b (resp. l 0c ) and a maximal elongation δ eb (resp. δ ec ). To ensure admissible tensions for springs and cables in a practical implementation, the lengths of the springs must be included in [l 0b , l 0b + δ eb ] (resp. [l 0c , l 0c + δ ec ]) for the bar-(resp. cable-) actuated SC.

Stability analyses showed that the configuration of the mechanism is independent of the spring stiffness and free-length (Eq. ( 1) and ( 2)). Modeling of the manipulator is then reduced to the manipulation of geometrical relationships and the forward static model can be derived analytically. The pose of the end-effector is expressed as:

x = O m ϕ m with O m = O b + 0 2l p + x c y c , O b = O 0 + x b y b (5)
       x b = ρ 2 b1 -ρ 2 b2 4L A 1 B 1 y b = ρ b1 ρ b2 2L A 1 B 1          x c = ρ 2 c1 -ρ 2 c2 4L A 3 B 3 y c = ρ c1 + ρ c2 2 1 + (ρ c1 ρ c2 -ρ 2 c1 ) 2 4ρ 2 c1 (ρ c1 ρ c2 -L 2 ) (6)
and

ϕ m = 2 arccos ρ c1 -ρ c2 2L A 3 B 3 -π (7)
The kinematic Jacobian matrix J of the manipulator maps the Cartesian velocities of the end-effector ẋ with respect to the joint velocities q: ẋ = J q. The pose of the endeffector is defined by three coordinates while four actuators are used. The system is then redundant and J is a 3 × 4 matrix. The kinematic Jacobian matrices J b and J c of the bar-and cable-actuated SC respectively are given in ( 8) and [START_REF] Siciliano | Kinematic control of redundant robot manipulators: A tutorial[END_REF].

J b = ∂ x ∂ q 1 =   ∂ O m ∂ q 1 0   = 1 8L 3 A 1 B 1       ρ b1 ρ 2 b1 + 3ρ 2 b2 2 - ρ b2 3ρ 2 b1 + ρ 2 b2 2 ρ 3 b2 ρ 3 b1 0 0       (8)
J c = ∂ x ∂ q 2 =     ∂ O m ∂ q 2 ∂ ϕ m ∂ q 2     = 1 8L 3 A 3 B 3       E 1 (ρ c1 , ρ c2 ) -E 1 (ρ c2 , ρ c1 ) E 2 (ρ c1 , ρ c2 ) 4L 2 -(ρ c1 + ρ c2 ) 2 E 2 (ρ c2 , ρ c1 ) 4L 2 -(ρ c1 + ρ c2 ) 2 -E 3 (ρ c1 , ρ c2 ) E 3 (ρ c2 , ρ c1 )       (9)
with

E 1 (ρ i , ρ j ) = 4L 2 ρ i -3ρ j ρ 2 i -ρ 3 j E 2 (ρ i , ρ j ) = 8L 4 -4ρ i L 2 (ρ i + 3ρ j ) + ρ j (3ρ i -ρ j )(ρ i + ρ j ) 2 E 3 (ρ i , ρ j ) = 8L 2 A 3 B 3 1 -ρ i (ρ i -ρ j )/2L 2 A 3 B 3 1 -(ρ i -ρ j ) 2 /4L 2 A 3 B 3 -1 (10) which leads to ẋ = J b ρ b1 ρ b2 + J c ρ c1 ρ c2 (11)
and the kinematic Jacobian matrix is finally expressed as

J = [J b , J c ] ( 12
)
3 Control loop and simulation

Thanks to the derivation of the kinematic Jacobian of the manipulator in ( 12), Jacobian based control for redundancy management can be exploited. To carry out a path tracking task in the Cartesian space with a redundant manipulator, the joint velocities are computed as:

q = PJ † (q)(x -x * ) (13)
with J † the Moore-Penrose pseudo-inverse Jacobian and P a negative diagonal matrix. Using Eq. ( 13), the redundancy is not exploited and the pseudo-inverse then minimizes the Euclidean norm of joint velocities. To add secondary tasks, the gradient projection method [START_REF] Siciliano | Kinematic control of redundant robot manipulators: A tutorial[END_REF] can be used to take advantage of the null-space of J and optimize a given cost function h(q). The joint velocities are then expressed as:

q = P J † (q)(x -x * ) + k I -J † (q)J(q) ∂ h(q) ∂ q T ( 14
)
with k a positive scalar. With the control scheme presented in ( 13), the trajectory is controlled in the Cartesian space but not in the joint space. However, if the actuator limit positions are reached, trajectory distortions will be induced. The RCM constraint can thus be violated, which is not acceptable (especially in a medical context). Also, the control of a tensegrity mechanism requires that the cables and springs are in tension at all time. To respect this constraint, actuator strokes are chosen accordingly. Moreover, as shown in Eq. ( 1) and Eq. ( 2), the spring lengths are directly linked to the joint positions. Therefore, maximizing the distance between the joint positions and their limits will also maximize the distance between the spring length and the lengths at rest and at maximal elongation. This approach is then also interesting to avoid situations with low or high tensions in the springs and cables. As a consequence, a cost function h(q) is proposed to minimize the distance between the measured joint positions and the mean value of the reachable positions following [START_REF] Liégeois | Automatic Supervisory Control of the Configuration and Behavior of Multibody Mechanisms[END_REF]. With ρ bmin , ρ bmax and ρ cmin , ρ cmax the actuator limits of the bar-actuated and the cable-actuated SC respectively, the cost function is written as

h a = 1 4 2 ∑ i=1 p 1 ρ bi -α bi ρ bmax -α bi 2
Actuators of the bar-actuated SC

+ p 2 ρ ci -α ci ρ cmax -α ci 2
Actuators of the cable-actuated SC

α bi = (ρ bmax + ρ bmin )/2 α ci = (ρ cmax + ρ cmin )/2 (15)
with p 1 and p 2 some coefficients to be tuned. The obtained control loop is displayed in Fig. 2. A pose feedback x m is considered. It can be implemented by measuring the joint coordinates and using the forward kinematic model or using an exteroceptive measurement. This choice is not discussed in this paper. We also consider that the motions are slow enough to avoid actuator velocity saturation and the transfer function of the actuators is considered to be unitary.

In order to evaluate the proposed control schemes, dynamic simulation is implemented with the Simscape TM Toolbox of Matlab Software (MathWorks, USA). This simulation is thereby independent from the models used for control. Weightless springs and cables are considered while the bars have a mass m b , the end-effector and the decoupling element a mass m p . Parameters are reported in Table 1. In practical implementation there are inevitably dissipative forces. We here simulate the latter with dampers placed in parallel to the springs and in the prismatic joints with a damping coefficient of 20 N.s/m. It is adjusted by a trial-and-error process. A comparison with (k = 0) and without (k = 0) optimization is performed. The end-effector trajectory is displayed in Fig. 3. During the whole process, the manipulator respects the RCM constraint. End-effector path is controlled by modifying the radius value R 0 (Fig. 1). The manipulator end-effector follows the sequence of points ABCDEA. Along CD, R 0 = 200 mm and along BE, R 0 = 235 mm. The angle ϕ varies between -35 and 35 • . The evaluation is carried out with an end-effector velocity of 5 mm/s and P = -diag(2, 2, 0.1). For the cost function minimization we choose p 1 = p 2 = 1 and k = 10 6 . The latter is chosen through a trial-and-error method.

The obtained Cartesian trajectories and errors on the radius and the angle are displayed in Fig 3 . The end-effector follows the desired trajectory with average path tracking errors of 0.88 (resp. 0.28) mm on the radius and 0.22 (resp. 0.19) • on the angle without (resp. with) optimization. In Fig. 3, a distortion of the Cartesian trajectory can be observed when the simple pseudo-inverse is used. It is due to the saturation of the joint positions. More specifically, it is caused by the actuators of the bar-actuated SC which reach their minimal bounds and the ones of the cable-actuated SC which reach their maximal bounds. When the control scheme with optimization is used some errors caused by the dynamics can still be observed. However, joint position saturation and tension limits are avoided.

Conclusions and perspectives

In this paper, the kinematic model of a tensegrity-based manipulator for a medical application was derived. It was then used to develop and achieve early-stage tests of Jacobian-based control schemes. Optimization of the joint positions was proposed to address actuator saturation and tension issues taking advantage of the tensegrity mechanism redundancy. Promising results are obtained even though only local optimization is considered. Implementation of global optimization is a first perspective of this work. The use of redundancy to minimize other criteria such as the potential energy to improve energy consumption and safety will also be considered.

Fig. 2

 2 Fig. 2 Proposed control loop.

Fig. 3

 3 Fig.3Top: Cartesian trajectories without (dotted red line) and with (solid blue line) optimization. Bottom: Errors on the RCM constraint. In dotted red and in solid blue the curves obtained using the control schemes proposed in[START_REF] Wenger | Kinetostatic Analysis and Solution Classification of a Planar Tensegrity Mechanism[END_REF] and in (14) respectively.

Table 1

 1 Parameters for simulation of the proposed manipulator.

	Parameter Value Unit	Parameter	Value	Unit
	L	200 (mm)	O p	[0 500] (mm)
	K	0.25 (N/mm)	m b	0.25	(kg)
	l 0b , δ eb 140 (mm)	m p	0.25	(kg)
	l 0c , δ ec 100 (mm)	[ρ bmin , ρ bmax ] [200, 500] (mm)
	l p	20 (mm)	[ρ cmin , ρ cmax ] [20, 170] (mm)

Acknowledgements This work is supported by the Investissements d'Avenir program (Robotex ANR-10-EQPX-44, Labex CAMI ANR-11-LABX-0004), the French National Research Agency (ANR Multiflag, ANR-16-CE33-0019) and by the Grand Prix Scientifique 2018, Fondation Charles Defforey, Institut de France.


Student Member, IEEE Slimane Charafeddine Benghelima

Lrdsi

Mohamed Ould-Khaoua
email: mouldkhaoua@univ-blida.dz

Ali Benzerbadj
email: ali.benzerbadj@univ-temouchent.edu.dz

Oumaya Baala
email: oumaya.baala@utbm.fr

Multi-objective Optimisation of Wireless Sensor Networks Deployment: Application to fire surveillance in smart car parks

Keywords: Internet of Things, Wireless Sensor Networks, Deterministic Deployment, Multi-objective Combinatorial Optimization, Smart Car Parks, Fire Surveillance

The exponential growth of the Internet-of-Things (IoT) technology paradigm has resulted in new applications and on-line services. Smart car park is one interesting example among others that can take advantage of applications based on wireless sensor networks (WSNs) Which constitute the core of IoT. This paper focuses on the deployment optimization problem of WSNs dedicated to the fire detection in a smart car park. In such networks, the nodes are classified into two categories: Sensor Nodes (SNs) deployed within the smart car park for targets coverage and Relay Nodes (RNs) whose task is to relay alert messages generated by the sensor nodes up to the sink node. In this study, we propose a Multi-Objective Binary Integer Linear Programming (MOBILP) which minimizes simultaneously the number of sensor nodes, relay nodes and the maximum distance from sensor nodes to the sink node, while ensuring coverage and connectivity. We have conducted extensive tests in order to evaluate the performance of our proposal. The results demonstrate that the MOBILP outperforms the existing approaches in terms of quality of solutions compared to a sequential deployment method, which consists to deploy SNs then RNs, and in terms of the ability to find other efficient solutions compared to a simultaneous deployment method using a mono-objective function, which consists to deploy SNs and RNs simultaneously.

I. INTRODUCTION

The deployment of IoT technologies has recently intensified. The IoT paradigm refers to a set of technologies designed to interconnect physical devices with each other and with the Internet [START_REF] Alavi | Internet of Things-enabled smart cities: State-of-the-art and future trends[END_REF]. A key feature of IoT systems is that the network is composed of nodes with constrained resources, i.e., processing, communication, and storage. In this work, we consider WSNs, which are the core of such systems, composed of SNs, RNs, and sink nodes. A SN's primary role is to collect information from the surrounding environment and send them to the sink node directly or through the RNs. As a typical part of a smart city application, a smart car park [START_REF] Lin | A Survey of Smart Parking Solutions[END_REF] is a typical example of how the IoT technology can be broadly applied to deliver various services to different users in our everyday living environments.

Smart park helps drivers quickly find a free space in the nearby parking lot. In various parking lots, to determine the availability or unavailability of a car park spot, sensors are placed on the ground [START_REF]Performance Analysis of Proximity and Light Sensors for Smart Parking[END_REF], demanding installing one sensor at each car parking spot, which could be costly, particularly in large parking lots. Motivated by this observation, various approaches have focused on using a camera-based WSN [START_REF] Idris | Smart Parking System using Image Processing Techniques in Wireless Sensor Network Environment[END_REF] to determine the state of the car park spots and can also be used for other services like surveillance. Such a parking lot is a sensitive area that presents a considerable risk to cars due to, e.g., fire incidents, as seen in table I; some recent car fires, which has caused damage to a massive number of cars, are cited. This has motivated us to design an effective targets (car park spots) surveillance system to avoid such losses, that can be a source of human tragedy and loss of the insurance company's earnings.

In this paper, we are interested in the problem of the deterministic deployment of WSNs [START_REF] Guo | A Deterministic Sensor Node Deployment Method with Target Coverage and Node Connectivity[END_REF]. A number of techniques have been developed to tackle this problem [START_REF] Abdollahzadeh | Deployment strategies in the wireless sensor network: A comprehensive review[END_REF]. Generally, the existing studies have focused on placing the SNs [START_REF] Bredin | Deploying Sensor Networks With Guaranteed Fault Tolerance[END_REF] and then the RNs [START_REF] Sun | A Physarum-Inspired Algorithm for Minimum-Cost Relay Node Placement in Wireless Sensor Networks[END_REF] separately with the aim of reducing deployment cost while maintaining low network delay and energy consumption. In this study, we strongly argue that the This study focuses on the simultaneous placement of SNs and RNs using a multi-objective formulation, where the objectives are the minimization of: the number of SNs, the number of RNs and the diameter 1 of the network, under the coverage and connectivity constraints. It is noteworthy that in our case, the minimization of the diameter is considered in order to enhance the end to end delay of the alert delivery.

The rest of this paper is organized as follows. Section II presents the related works on WSN deployment problem. Sections III and IV provide respectively the network description and assumptions, and the problem formulation. Section V presents the MOBILP formulation. Section VI details the experimental findings. Section VII concludes the paper.

II. RELATED WORKS

In the following, we review some works related to the deterministic deployment problem of WSNs.

The authors in [START_REF] Fellah | Exact and Efficient Heuristic Deployment in WSN under Coverage, Connectivity, and Lifetime Constraints[END_REF] addressed the deployment strategies that consider multi objectives such as cost (number of sensors), coverage, network connectivity and lifetime. To do so, they formulated two variants of a mixed-integer linear program (MILP) model. As a first step, they solve the problem of monitoring targets using a minimum number of connected sensor nodes. Then, the above formulation is extended to another MILP called lifetime-aware model, which considers the requirement that the WSN must remain fully operational for a prescribed time period T.

The authors in [START_REF] Govind | Biogeography-based optimization scheme for solving the coverage and connected node placement problem for wireless sensor networks[END_REF] proposed a Linear program (LP) that considers k targets and a set of candidate positions for sensor nodes. It aims to place an optimal number of sensor nodes while satisfying k-Coverage (each target is covered by at least k sensor nodes) and m-connectivity (each sensor node has at least m-neighbor nodes). The authors proposed a metaheuristic algorithm using the Bio-geography-based optimization to solve the problem. They built a multi-objective function from the weighted sum of the three objective functions: maximize target coverage, maximize the connectivity of each sensor node and minimize the total number of sensor nodes. 1 Represents the length of the longest path among all shortest paths between all the SNs and the sink node

In both the previous cases, the SNs are responsible for sensing real world events and sending them to the sink node, which consume a lot of energy. Furthermore, since SNs have limited battery power and transmission range, the multi-hop communication is required in most situation. Therefore, SNs participate in the data routing to the sink node, which causes the rapid exhaustion of the SNs' batteries and increases the overall packet delivery latency.

To face the problems mentioned above, a new solution is introduced which consists of using RNs instead of SNs to relay data from SNs up to the sink node. The authors in [START_REF] Nguyen | Minimal Node Placement for Ensuring Target Coverage With Network Connectivity and Fault Tolerance Constraints in Wireless Sensor Networks[END_REF] focused on the minimization of the number of SNs and RNs. They used a sequential approach, where the first stage ensures the Target Coverage (TC), and the second stage ensures Network Connectivity (NC) and Fault Tolerance (FT). The TC problem is proved to be an NP-hard problem and consequently a nonexact greedy algorithm is utilized to achieve full coverage. The second stage, known as Minimum RN Placement was reduced to the Minimum Euclidean Steiner Tree problem (MEST). MEST is known to be NP-hard, and thus a new heuristic algorithm based on the traveling salesman Problem is used to find two distinct paths from any SN to the sink node. In [START_REF] Ndam | Hybrid Wireless Sensors Deployment Scheme with Connectivity and Coverage Maintaining in Wireless Sensor Networks[END_REF], in order to cope with the problem of TC and NC, a sequential approach is adopted. First, a greedy coverage algorithm places the sensors to cover all targets by assigning one sensor to each target. Second, a redundancy suppression algorithm removes redundancies resulting from the placement in the first step in order to reduce the number of deployed sensors. The last step is to place RNs to generate a connected graph with a minimum path length that connects the deployed sensors to the receiving node.

It is noteworthy that both works [START_REF] Nguyen | Minimal Node Placement for Ensuring Target Coverage With Network Connectivity and Fault Tolerance Constraints in Wireless Sensor Networks[END_REF][12] rely on the sequential node placement approach where the SNs are deployed first, then the RNs based on the prefixed SNs. This approach does not explore the research space well to find better solutions. Therefore, the authors in [START_REF] Sun | Minimum-Cost Heterogeneous Node Placement in Wireless Sensor Networks[END_REF] formulated the minimum-cost node placement problem as a Steiner Tree Problem (STP) for the simultaneous placement of SNs and RNs. They highlighted the benefits of this approach over the sequential node placement. The STP is further extended to Node Weighted Full Group Steiner Tree Problem and solved using an exact algorithm (for small instances) and a heuristic algorithm (for large instances). Afterwards, the sub-optimal solution obtained from the heuristic algorithm is improved through post-processing algorithms. To the best of our knowledge, the paper [START_REF] Sun | Minimum-Cost Heterogeneous Node Placement in Wireless Sensor Networks[END_REF] is the only existing study on the simultaneous placement of SNs and RNs nodes using a mono-objective function which gets only one solution, whereas the number of SNs and RNs are two conflicting objectives. Hence, the multi-objective optimization is more suitable for such a problem to find all compromises.

In the current work, we are addressing the multi-objective optimization of the simultaneous placement of SNs and RNs.

III. NETWORK DESCRIPTION AND ASSUMPTIONS

As depicted on Figure 1, a WSN is composed of two fundamental sets, namely a set of SN (sensor node with dome camera) and a set of RN. The SNs have the role of capturing images of the spots inside the parking lot, and processing them locally using intelligent algorithms [START_REF] Jadon | Low-Complexity High-Performance Deep Learning Model for Real-Time Low-Cost Embedded Fire Detection Systems[END_REF] to obtain information on the state of car park spots (free or occupied parking places), and whether there is a fire in the cars parked in the spots. The RNs are used to relay data packets (spots status or fire alarm) generated by the SNs, up to the sink node.

IV. PROBLEM FORMULATION

Using a discretization of the area of interest (car park space), we obtain a set of points, denoted P. Let T = {T 1 , T 2 , T 3 , ...., T k } be the set of k targets (car park spots) distributed inside the area of interest, which we want to cover by SNs. Each sensor is characterized by a sensing range R s , assumed to be constants. SNs and RNs can be placed only at specific candidate sensor positions (CSPs), CSP= {sn 1 , sn 2 , sn 3 , ...., sn n } and candidate relay positions (CRPs), CRP= {sr 1 , sr 2 , sr 3 , ...., sr m }, respectively. Sensor sn j covers the target T i if the sensing range of sn j completely covers the target T i . In other words, if the euclidean distance between the sensor sn j and the target T i is no more than R s then the target T i is assumed to be covered by sn j . On the other hand, two nodes are neighbors and can communicate (send/receive information) if the Received Signal Strength Indicator (RSSI) value perceived by a node is greater than or equal to RX T sh 2 which is the sensitivity of the receiving antenna. The radio propagation model used in this paper is Log-normal shadowing model [START_REF] Wang | Connectivity of multihop wireless networks with lognormal shadowing[END_REF].

We consider the problem as a graph consisting of the union of sets of n CSPs, m CRPs and one sink V 1 . Each sensor i has a list s i of targets that can monitor them. The objectives are to minimize: under the two following constraints:

• The union of elements associated with nodes of optimal sensor set covers the set of target T . {s i } = T, ∀i ∈ V opt s • Every sensor not neighbor of the sink must be connected to the sink node using at least one path composed only of RNs (Two-tiered architecture [START_REF] Yang | Two-Tiered Constrained Relay Node Placement in Wireless Sensor Networks: Computational Complexity and Efficient Approximations[END_REF])

V. OPTIMIZATION PROBLEM

In this section, we first give some definitions. Then, we present the MOBILP, and describe the resolution method and how to deal with the objectives.

A. Definitions

Table II summarizes all of our model's related parameters and variables. if there is a path with length k-hop from RN to the sink node.

B. Multi-objective binary integer linear program

Using the above parameters and decision variables, the linear model can be written as follows:

min F 1 = i∈Vs K+1 k=1 x k i min F 2 = i∈Vr K k=1 r k i min F 3 = K k=1 y k Subject to: K+1 k=1 x k i ≤ 1 i ∈ V s (1) K k=1 r k i ≤ 1 i ∈ V r (2) K+1 k=1 i∈V p s x k i ≥ 1 ∀p ∈ P (3)
x k i ≤ j∈V r i r k-1 j ∀i ∈ V s \V 1 , ∀k = 2 . . . K + 1 (4)
r k i ≤ j∈V r i r k-1 j ∀i ∈ V r \V 1 , ∀k = 2 . . . K (5) K+1 k=2 x k i ≤ 0 i ∈ V 1 \V r (6) K k=2 r k i ≤ 0 i ∈ V 1 \V s (7)
x 1 i = 0 i ∈ V s \V 1 (8) r 1 i = 0 i ∈ V r \V 1 (9)
y k ≥ r k i i ∈ V r , k = 1 . . . K (10)
y k ≤ i∈Vr r k i k = 1 . . . K (11)
y k ≤ y k-1 k = 2 . . . K (12)
y k ≤ K+1 l=k+1 i∈Vs x l i k = 1 . . . K (13)
The objective is to minimize simultaneously, F1: number of SNs, F2: number of RNs and F3: diameter of the network. The constraints (1) and (2) ensure that each SN and RN has only one path to the sink node. The constraint (3) ensures that each target p ∈ P is covered by at least one SN which is located at k hops from the sink node. The constraints (4) and [START_REF] Fellah | Exact and Efficient Heuristic Deployment in WSN under Coverage, Connectivity, and Lifetime Constraints[END_REF] guarantees that each SN or RN located at k hops from the sink (k > 1), has at least one neighbor RN located at k-1 hops from the sink node. The constraints ( 6) and [START_REF] Govind | Biogeography-based optimization scheme for solving the coverage and connected node placement problem for wireless sensor networks[END_REF] guarantee that a SN or RN respectively, directly neighbor to the sink node cannot be situated at k > 1 hop. The constraints ( 8) and ( 9) avoid the inconsistency of the model, that is to say that no SN and no RN respectively is neighbor to the sink node unless it is located at 1-hop from it.

The constraint [START_REF] Jadon | Low-Complexity High-Performance Deep Learning Model for Real-Time Low-Cost Embedded Fire Detection Systems[END_REF] determines the length of the paths made up of RNs towards the sink node. If the i th relay located at k hops from the sink then there is a path of length k. The constraint [START_REF] Lin | A Survey of Smart Parking Solutions[END_REF] ensures that if there is a path of length k hops, it means that there is at least one RN located at k hops from the sink node. This is to avoid the inconsistency of the model. The constraint [START_REF] Ndam | Hybrid Wireless Sensors Deployment Scheme with Connectivity and Coverage Maintaining in Wireless Sensor Networks[END_REF] guarantees that the existence of a path of length k hops induces the presence of a path of length k -1 hops. The constraint [START_REF] Gurobi Optimization | Gurobi optimizer reference manual[END_REF] guarantees that if there is a path with k hops length, a SN is necessarily selected at l hops from sink node (l = (k + 1) ∨ l = (k + 2) ∨ . . . ∨ l = (K + 1)).

C. Resolution method

To produce the set of effective solutions, we choose the -constraint approach [START_REF] Becerra | Solving Hard Multiobjective Optimization Problems Using -Constraint with Cultured Differential Evolution[END_REF], which has the advantage of being extremely simple to implement. As shown in algorithm 1, this method consists in transforming the multi-objective problem to a mono-objective problem by considering one objective to optimize among the others and making the remaining objectives as bounded constraints.

We solve the linear program iteratively (line 4), where we minimize the objective function F1 while the objective functions F2 and F3 are considered as constraints delimited respectively by 2 and 3 . For each iteration, we increase the bounds ( 2 or 3 ) to obtain a new solution.

Algorithm 1 ε-constraint method

Input: F 2 and F 2 are respectively the lower and upper bounds of F 2 , F 3 is lower bound of F 3 . Output: P is the set of efficient solutions.

P ← ∅ ε 2 ← F 2 1: while ε 2 ≤ F 2 do 2: ε 3 ← F 3 3:
while No improvement after six successive runs do 4:

X ← M inimize(F 1 , F 2 ≤ ε 2 , F 3 ≤ ε 3 ) 5:
if X ∈ P such that X is better than X then 6:

P ← P {X} 7:
end if 8:

ε 3 ← ε 3 + 1 9:
end while 10: ε 2 ← ε 2 + 1 11: end while 12: return P

VI. EXPERIMENTAL FINDINGS

To evaluate the performance of the proposed MOBILP, we conducted extensive tests built on several scenarios. In this section, we describe the considered testbed, the experiments and discuss their results.

A. TESTBED SETUP

To simulate a test environment corresponding to a car park, we consider a square area of 160m x 160m divided into an equally-sized mesh grid of 20m x 20m. We define the CSPs set as the vertices of the whole meshes, the CRPs set as the center of each mesh, and the sink position is picked from the set of CRPs. All nodes have the same Tx power of -5 dbm and radio sensitivity of -100 dbm, and all SNs have the same sensing range of 25 meters. Three scenarios are studied to show the effectiveness of our model MOBILP denoted Approach 3, compared to research work in [START_REF] Ndam | Hybrid Wireless Sensors Deployment Scheme with Connectivity and Coverage Maintaining in Wireless Sensor Networks[END_REF] and [START_REF] Nguyen | Minimal Node Placement for Ensuring Target Coverage With Network Connectivity and Fault Tolerance Constraints in Wireless Sensor Networks[END_REF] using sequential deployment approach denoted Approach 2, and research work in [START_REF] Sun | Minimum-Cost Heterogeneous Node Placement in Wireless Sensor Networks[END_REF] using mono-objective simultaneously deployment approach denoted Approach 1.

At this stage of research work, and in the absence of real data, we generate the following scenarios: Scenario 1, Random distribution of all targets in the area of interest, Scenario 2, Random distribution of 60% of targets in the left bottom quarter of the grid (near to the car park entrance in bottom left of the grid) and the remaining 40% is distributed randomly on the other three quarters, and Scenario 3, Random distribution of 60% of targets in the three first columns of the grid and the remaining 40% is distributed randomly on the other columns. We vary the sink location for each scenario in the set {top left, center, bottom right}. For each sink location, the number of targets varies and takes the specified values of 50, 100, and 200 targets. Figure 2 depicts a few generated scenarios built from 200 targets and where the sink is located in the top left of the grid. The mathematical model is solved using " -Constraint algorithm" in which we call the solver Gurobi 9.0.3 [START_REF] Gurobi Optimization | Gurobi optimizer reference manual[END_REF], and executed on a PC with a two-core Intel Core Processor (2.50 GHz) and 6 GB RAM.

B. RESULTS AND DISCUSSION

We carried out several tests, the outcomes from program runs are depicted in tables III, IV and V. In comparison to Approach 1, that is the mono-objective optimization with simultaneous placement of SNs and RNs, MOBILP provides a set of alternative solutions which include the solution obtained from the Approach 1. On the other hand, we observe that all the solutions provided by Approach 2 are also included in the set of solutions provided by MOBILP or are dominated by those solutions. Therefore, modelling a simultaneous deployment problem as a multi-objective problem allows the decision-maker more flexibility to choose the optimal trade-off between conflicting objectives according to the context of the problem. Thus, the decision-maker can pick any specific number of relay nodes (#RN) and obtain the minimum associated number of SNs (#SN) and network diameter (D). There is an impact of target density as shown in Tables III, IV and V. We note that when the density of targets increases inside the smart parking, more SNs and RNs are required, and hence the cost of the deployment increases significantly. This can be explained by the limited sensing range of the SNs which reduces the number of SNs that cover the same target and leads to the increase of the number of SNs and RNs to ensure coverage of all targets and connectivity requirements. Furthermore, the variation of the distribution of the target positions according to the three scenarios detailed above has an impact on the WSN deployment as shown in Tables III, IV and V. Indeed, in scenario 2 when all the targets are close as they are concentrated in one area, the #SN has the lowest value. This is because one SN can cover more targets.

In addition, as illustrated in Tables III, IV and V, it appears that the sink position affects only the diameter of the network whatever the scenario. We can notice that the best position of the sink to get the better value of the diameter is in the middle of the area under study, as shown in the Table IV, where all SNs are near the sink node. Finally, we can conclude that MOBILP generally outperforms the other approaches or at least provides the same solutions in all scenarios.

On the other hand, MOBILP takes longer running time compared to the other two approaches. For instance, In scenario 1, when the number of targets is 50 the approaches 1,2 and MOBILP solve the problem in 2.67s, 3.02s and 35.88s respectively. While in scenario 2 they solve the problem in 5.54s, 3.95s and 21.27s. Finally, for scenario 3 they take 2.20s, 2.29s and 15.32s respectively. This can be explained by the simultaneous deployment that increases the research space of the problem and the multi-objective version that makes the problem more complex. On the other side, the running time of the MOBILP increases when the number of targets increases. For example, to solve scenario 1 with 50, 100 and 200 targets the MOBILP takes 35.88s, 117.61s and 598.92s respectively. Nevertheless, we can agree on a reasonable resolution time as we are working offline. Indeed, we have considered the car park spots as the targets, not the vehicles.

VII. CONCLUSIONS AND FUTURE WORK

In this work, we addressed the optimal deployment of WSNs for fire detection in a smart car park by identifying the locations of SNs and RNs simultaneously, minimizing the number of SNs, the number of RNs and the network diameter while satisfying the coverage and connectivity constraints. First, we formulated the problem as a graph, then we solved it using our approach referred to as "MOBILP".

We also performed exhaustive testing on three scenarios. The first one is purely random. The two other scenarios are close to reality, where the first one has 60% of the targets distributed in the lower left quarter near the smart parking entrance and 40% distributed randomly in the three other quarters, and the second one has 60% of the targets in the three first columns near the smart parking entrance and 40% distributed randomly on the other remaining columns. The MO-BILP provides better solutions and more flexibility to choose the optimal compromise between contradictory objectives, in comparison to two existing approaches, a sequential approach which places SNs then RNs, and an approach of simultaneous deployment of SNs and RNs with mono-objective function that provides only one solution.

In our future work, we intend to address a wider car park area and we will move towards the use of heuristics to solve large instances of our problem within a reasonable time.

Fig. 1 .

 1 Fig. 1. Example of WSN deployed inside a smart car park

  Euclidian distance(i, p) ≤ Rs; i ∈ Vs; p ∈ P } is the set of candidate positions of SNs which cover the target p. V r i {j/ ((RSSI(i, j) ≥ RX T sh ) ∧ (RSSI(j, i) ≥ RX T sh ))∧ (j ∈ (Vr ∨ {Sink}))} is the set of candidate positions of RNs or sink position which are neighbors with the candidate position of node i ∈ (Vs ∪ Vr). V 1 {j/ ((RSSI(Sink, j) ≥ RX T sh ) ∧ (RSSI(j, Sink) ≥ RX T sh )) ∧(j ∈ (Vr ∨ Vs)) is the set of candidate positions of SNs and RNs which are neighbors with the sink node. K Maximum number of hop-count allowed Variables x i k if a SN is placed at candidate position of sensor node i, and situated at k-hop from the sink node.r i k if a RN is placed at candidate position of relay node i, and situated at k-hop from the sink node. y k

Fig. 2 .

 2 Fig. 2. The study scenarios: distribution of 200 targets with the sink in top left

•

  The number of sensor nodes, i.e., find |V opt s |

• The number of relay nodes, i.e., find |V opt c | • The Maximum distance of the shortest paths (hop-count) between all SNs to sink node, i.e., max i∈V opt s {dist i,V1 } : 2 Represents the minimum RSSI threshold for communication

TABLE II PARAMETERS

 II

AND VARIABLES Parameter Definition Sink is the index of the sink node Vs is the set of candidate positions of SNs. Vr is the set of candidate positions of RNs. P is the set of targets.

TABLE IV TEST

 IV RESULTS: SINK AT THE CENTRE

		Scenario 1		Scenario 2		Scenario 3
		#SN #RN D #SN #RN D #SN #RN D
					50 targets
	App1	18	11	4	13	7	3	19	12	4
	App2	18	13	4	13	8	3	19 19	12 13	6 4
								19	11	5
		18	11	4				19 20	12 10	4 5
	MOBILP				13	7	3	20	11	4
		19	10	4				20 21	13 10	3 4
								21	12	3
					100 targets
	App1	24	10	4	21	11	4	21	12	4
	App2	23	12	4	21 21	12 13	5 4	21	13	4
	MOBILP	23	11	4	21	11	4	21 22	12 11	4 4
		24	10	4	22	10	5	24	10	4
					200 targets
	App1	32	12	3	26	11	3	31	12	3
	App2	31 31	14 15	5 4	26 26	12 13	4 3	30	14	4
		31	12	5				30	12	5
		31	13	4
					26	11	3	30	13	4
	MOBILP	32	11	6				31	11	4
								31	12	3
		32	12	3
					29	10	7	32	10	5
		33	11	4				32	11	3