Sandrine Aubert

Francesca Bonini

Jonathan Curot

Luc Valton

William Szurhaj

Philippe Derambure

Sylvain Rheims

Philippe Ryvlin

Fabrice Wendling

Aileen Mcgonigal

Agnes Trébuchon

Fabrice Bartolomei

Fabrice Pr

MD Bartolomei

The role of sub-hippocampal versus hippocampal regions in bitemporal lobe epilepsies

Keywords: Entorhinal cortex, Bilateral Temporal epilepsy, SEEG, Surgery, Epileptogenicity Index. Highlights

Objective: We aimed at better delineating the functional anatomical organization of bitemporal lobe epilepsy. Methods: We studied the epileptogenic zone (EZ) by quantifying the epileptogenicity of brain structures explored by depth electrodes in patients investigated by stereoelectroencephalography (SEEG). We compared 15 patients with bilateral mesial temporal lobe epilepsy (BTLE) and 15 patients with unilateral mesial temporal lobe epilepsy (UTLE). This quantification was performed using the 'Epileptogenicity Index' (EI) Results: Age at epilepsy onset, and epilepsy duration, were not statistically different in both groups. UTLE patients more frequently displayed maximal epileptogenicity in hippocampal structures, whereas BTLE patients had maximal values in subhippocampal areas (entorhinal cortex, temporal pole, parahippocampal cortex). Conclusions: Our results suggest different organization of the EZ in the two groups Significance: BTLE was associated with more involvement of subhippocampal regions, a result in agreement with known anatomical connections between the two temporal lobes.

Introduction

Bitemporal lobe epilepsies (BTLE) are characterized by seizures arising independently or starting simultaneously from the two temporal lobes [START_REF] So | Results of surgical treatment in patients with bitemporal epileptiform abnormalities[END_REF] and are a major source of concern in the context of epilepsy surgery. The suspicion of BTLE is a usual indication for depth electrode exploration in temporal lobe epilepsy (TLE) [START_REF] Diehl | Temporal lobe epilepsy: when are invasive recordings needed?[END_REF]. Previous studies have shown that BTLE may account for ~ 20% of TLE patients explored by depth EEG [START_REF] Hirsch | Comparison of bitemporal and unitemporal epilepsy defined by depth electroencephalography[END_REF]. Anterior temporal lobectomy is often proposed when a majority of seizures arise from one side [START_REF] So | Results of surgical treatment in patients with bitemporal epileptiform abnormalities[END_REF][START_REF] Hirsch | Comparison of bitemporal and unitemporal epilepsy defined by depth electroencephalography[END_REF] but cognitive risks are significant and outcome is generally less favorable. Factors contributing to bilaterality in TLEs are unclear. No specific etiological factors have been significantly correlated to BTLE [START_REF] So | Results of surgical treatment in patients with bitemporal epileptiform abnormalities[END_REF][START_REF] Hirsch | Comparison of bitemporal and unitemporal epilepsy defined by depth electroencephalography[END_REF][START_REF] Lim | Etiologic factors for unitemporal vs bitemporal epileptiform discharges[END_REF][START_REF] Sirven | Outcome after temporal lobectomy in bilateral temporal lobe epilepsy[END_REF]. From experimental models of mirror foci, it has been suggested that bilaterality could be due to a secondary epileptogenesis process [START_REF] Morrell | The role of secondary epileptogenesis in human epilepsy[END_REF]. However, somewhat against this hypothesis is the observation that bilaterality has not been clearly correlated with epilepsy duration or age at onset [START_REF] Steinhoff | Ictal scalp EEG in temporal lobe epilepsy with unitemporal versus bitemporal interictal epileptiform discharges[END_REF].

In the present work we aimed at studying the functional anatomy of the epileptogenic zone (EZ) in patients undergoing bilateral SEEG exploration for mesial TLE. We particularly wished to establish whether the anatomo-functional structure of the EZ is different in patients presenting unilateral versus bilateral TLE. In particular, it has been suggested that some structural factors (notably hippocampal sclerosis) may influence bilaterality [START_REF] Duckrow | Regional coherence and the transfer of ictal activity during seizure onset in the medial temporal lobe[END_REF]. In addition, interhemispheric connectivity linking subhippocampal regions (rhinal cortices including entorhinal cortex, perirhinal cortex and parahippocampal cortex) appear to be stronger than connections between the two hippocampi in humans [START_REF] Gloor | The Temporal lobe and Limbic system[END_REF][START_REF] Adam | How do the temporal lobes communicate in medial temporal lobe seizures?[END_REF]. It is not known however if the pathophysiology of BTLE affects the subhippocampal regions more than the hippocampus.

To gain insight into this question, we analyzed data obtained in patients explored by SEEG and presenting either BTLE or unilateral TLE (UTLE). The epileptogenicity of mesiotemporal brain structures was estimated using the Epileptogenicity Index (EI), a method previously described to quantify the epileptogenic zone networks [START_REF] Bartolomei | Epileptogenicity of brain structures in human temporal lobe epilepsy: a quantified study from intracerebral EEG[END_REF][START_REF] Bartolomei | From mesial temporal lobe to temporoperisylvian seizures: a quantified study of temporal lobe seizure networks[END_REF]

Methods

Patient selection and SEEG recordings

Patients with either BTLE or UTLE explored by SEEG were selected for this study. BTLE were defined as patients whose habitual seizures were characterised by independent mesial temporal onset from each side (more than 20% of seizures) or bilateral onset (discharge affecting both mesial temporal structures with latency of less than one second). UTLE were defined as patients whose seizures started from a unilateral mesial temporal region during the SEEG video recordings. We retained for this study only patients having undergone bilateral exploration with at least one contralateral mesiotemporal electrode. Since BTLE is relatively less prevalent than UTLE, we collected data from 15 consecutive patients with BTLE recorded in four French epilepsy centers (Marseille, Lyon, Lille, Toulouse). These patients were compared with 15 UTLE patients investigated in the presurgical epilepsy unit at the Timone hospital in Marseille during the same period. These patients had strictly unilateral onset of temporal lobe seizures during SEEG recordings. After surgical procedures most of the patients with UTLE were seizures free (table 1). In case of seizure relapse after surgery, residual seizures were recorded and were located in the same side, thus excluding an unsuspected BTLE revealed in these cases.

All patients had SEEG implantation including exploration of the hippocampal region (anterior hippocampus , aHip and/or posterior hippocampus, pHip), sub-hippocampal regions (entorhinal cortex, EC), posterior part of the para-hippocampal gyrus (pPHG), amygdala (Amy) and temporal pole (TP).

All patients had SEEG after a comprehensive evaluation including detailed history and neurological examination, routine brain MRI, video-EEG recordings. Most of them also had positron emission tomography (FDG-PET), ictal and/or interictal single-photon emission computed tomography (SPECT) imaging, and neuropsychological testing.

SEEG exploration was carried out during long-term video-EEG monitoring, as part of our patients' normal clinical care. Recordings were performed using intracerebral multiple contact electrodes (5 to 15 contacts, length: 2 mm, diameter: 0.8 mm, 1.5 mm apart) placed intracranially according to Talairach's stereotactic method [START_REF] Bancaud | La stéréoélectroencéphalographie dans l'épilepsie: informations neurophysiopathologiques apportées par l'investigation fonctionnelle stereotaxique[END_REF][START_REF] Guenot | Neurophysiological monitoring for epilepsy surgery: the Talairach SEEG method. StereoElectroEncephaloGraphy. Indications, results, complications and therapeutic applications in a series of 100 consecutive cases[END_REF]. The targeting of electrodes was established in each patient based upon available noninvasive information and hypotheses about the localization of the epileptogenic zone. Video-EEG recording was prolonged as long as necessary for the recording of several habitual seizures.

SEEG signals were sampled at 256 Hz or 512 and recorded on a hard disk using no digital filter. Habitual spontaneous seizures or seizures induced by low frequency (bipolar stimulation, 1Hz, 2ms pulse width, intensity range: 0.3-1.5 mA) electrical stimulation were analyzed. All available seizures (mean 5.2, range 2-11) were analysed in the BTLE group (as seizure patterns greatly varied from one seizure to another), and a minimum of 2 seizures (mean: 3.13, range 2-7) analysed in the UTLE group.

Signal analysis: definition and computation of the Epileptogenicity Index (EI)

Our study was based on the determination of the "Epileptogenicity Index" (EI). This quantification has been proposed in order to characterise the propensity of a given brain structure to generate a 'rapid discharge' (the high frequency oscillations observed during the transition between ictal and interictal activity) and takes into account the delay of appearance of this discharge with respect to seizure onset [START_REF] Bartolomei | Epileptogenicity of brain structures in human temporal lobe epilepsy: a quantified study from intracerebral EEG[END_REF][START_REF] Bartolomei | From mesial temporal lobe to temporoperisylvian seizures: a quantified study of temporal lobe seizure networks[END_REF][START_REF] Bartolomei | Neural networks underlying parietal lobe seizures: a quantified study from intracerebral recordings[END_REF] (for details see Supplementary Material). The purpose of this index is to provide quantified information about the behaviour of brain structures recorded from signals they generate during the seizure process. This index summarises two pieces of information into a single quantity: 1) whether or not the recorded brain structure is involved in the generation of a high frequency discharge (beta and gamma range) and 2) when involved, whether or not this rapid discharge is delayed with respect to rapid discharges generated by other structures. A normalised value is used ranging from 0 to 1. If there is no involvement of the brain structure, the EI = 0 whereas if the brain structure generates a rapid discharge and the time to seizure onset is minimal, the EI = 1. An EI between 0 and 1 corresponds to secondary involvement of the brain structure concerned (for detailed methodology see [START_REF] Bartolomei | Epileptogenicity of brain structures in human temporal lobe epilepsy: a quantified study from intracerebral EEG[END_REF])

In practice, we use a semi-automatic approach: using a handy graphical user interface, the user can easily inspect and validate automatically detected change points indicating the accurate onset of rapid discharges. From this validation performed on a "structure-bystructure" basis, the EI is then computed.

We determined the EI values from signals recorded in distinct structures (7 or 8 in each patient) including all mesial temporal regions available in our patients. A structure was considered as being highly epileptogenic when its EI value was 0.4, according to previous reports [START_REF] Bartolomei | From mesial temporal lobe to temporoperisylvian seizures: a quantified study of temporal lobe seizure networks[END_REF]. Generally, the implantation strategy favored one side with a complete set of explored regions. We therefore quantified the EZ from the predominantly explored side.

The SEEG signals from the following regions were analyzed in each selected patient:

anterior hippocampus (aHip), posterior hippocampus (pHip); entorhinal cortex (EC); internal part of the temporal pole (iTP); parahippocampal cortex (pPHG) and amygdala (A).

Statistical analysis

Statistical analysis was performed to assess potential links between the bilateral or unilateral nature of the related epilepsy and EZ location / organization, as well as several clinical and imaging data. Qualitative clinical data between the two groups (UTLE and BTLE) were compared using chi square or Fisher exact tests. EI values computed from mesiotemporal regions were compared between the two groups (BTLE, UTLE). All statistical tests were performed on mean EI values calculated from all available seizures for each patient. A total of 116 seizures were analyzed (~ 3.8 seizures / patient). EI values were averaged over different subgroups of structures (hippocampal structures including aHip and pHip; subhippocampal structures including EC, pPHG and iTP; amygdala). They were then compared using non-parametric tests (Mann-Whitney) because values did not follow normal distribution. A p-value smaller than or equal to 0.05 was considered to be statistically significant. Statistical tests were performed with the software SPSS for Windows, version 13.1.

Results

Clinical data

The main characteristics of the two studied populations are summarized in table 1. Comparing BTLE and UTLE, we did not find significant differences in sex ratio, even if we found a slight female predominance in BTLE (p=0.14). Age at epilepsy onset, and epilepsy duration, were not statistically different in the two groups (15.8 years (+/-8.8) vs 15.6 years (+/-11.9), p=0.61) and 23.2 years (+/-10.8) vs 20.9 years (+/-14.8) (p=0.42). Past history of febrile seizures was less frequently reported in the BTLE group than in the UTLE group, without reaching a significant level (2/15 vs 5/15, p=0.19). Three patients in the BTLE group and one in the UTLE group had a past history of post-ictal psychosis. BTLE patients more frequently displayed bilateral interictal spikes than UTLE patients (73% vs 46%, p=0,036). Bilateral temporal hypometabolism on FDG PET was more frequently present in the BTLE group (33% vs 7%, p<0,0001). False-lateralizations were observed, when comparing FDG PET results with SEEG findings (predominant side for BTLE patients, definite side for UTLE patients): 33% in the BTLE group, vs 0% in the UTLE group.

Global IQ was slightly lower in the BTLE group (75.8 +/-20.6 (range 46-116); UTLE: 81.4 +/-10.3 (72-100); p=0.047), but visuo-verbal discrepancy was represented equally in both groups (BTLE 3/15, 20%; UTLE patients (6/15, 40%), p=0.20). No significant differences were found in the etiology of epilepsy (p=0.52) but HS was slightly more frequent in the UTLE group (7 patients vs 4 in the BTLE group).

Only one patient in the BTLE group has been operated (anterior temporal lobectomy (ATL) leading to a class III outcome). In the UTLE group, 13 patients benefited from ATL (among whom, 10 (76%) have Engel Class I outcome,) and one had Gamma knife radiosurgery targeting the mesial temporal lobe (Class I Engel at the last follow up, 3y).

SEEG data: Epileptogenicity index analysis

Table 2 summarizes the SEEG findings in both groups. Figures 1 and2 show examples of BTL seizures. The epileptogenicity profiles as determined by EI computation of the signal from different mesio-temporal sub-regions were found to be different in the two groups. We indeed found a trend in the BTLE group for higher EI values in the posterior part of the parahippocampal gyrus (pPHG) (p=0.05) and a significant difference for the anterior hippocampus (aHip), with a higher epileptogenicity of this structure in UTLE patients (p=0.005) (Fig 3). Results therefore suggest that BTLE patients tended to have a subhippocampal epileptogenic zone, whereas the EZ in UTLE patients predominantly involved hippocampus. This tendency was confirmed when we studied averaged values obtained from amygdala, hippocampal region (regrouping aHip and pHip), and subhippocampal regions (including EC, pPHG and iTP values). The two groups were significantly different for hippocampal values, these being higher in the UTLE patients than in BTLE patients (p=0.01).

Among BTLE patients, 11 had a bilateral TL seizure onset (bilateral subtype) with an over-representation of subhippocampal EZ (n=7), whereas only half of the remaining 4 with right and left TL seizures (independent subtype) had a subhippocampal EZ.

The mean total number of epileptogenic structures was calculated by considering EI values above a heuristic threshold (0.4) and including the explored mesiotemporal region. The number of regions disclosing EI>0.4 was similar in both groups: 2.13 +/-0.64 in BTLE patients vs 2.2 +/-1.15 than in the UTLE group (p>0.05).

Discussion

This study aimed at determining the functional anatomy of the EZ in bilateral temporal lobe epilepsies in comparison with unilateral temporal lobe epilepsies. Results are in favor of more marked subhippocampal epileptogenicity in patients with BTLE, while epileptogenicity predominated in the hippocampus in patients with UTLE. These results were obtained by using a quantification of the seizure onset zone by the mean of the epileptogenicity index, a semi-automated method aimed at quantifying the seizure onset zone from depth EEG recordings [START_REF] Bartolomei | Epileptogenicity of brain structures in human temporal lobe epilepsy: a quantified study from intracerebral EEG[END_REF][START_REF] Bartolomei | From mesial temporal lobe to temporoperisylvian seizures: a quantified study of temporal lobe seizure networks[END_REF][START_REF] Bartolomei | Neural networks underlying parietal lobe seizures: a quantified study from intracerebral recordings[END_REF].

The included BTLE patients had characteristics in agreement with previous studies. In particular no specific etiological factors were found to differentiate the two populations, although HS was slightly more frequent in the UTLE patients [START_REF] Hirsch | Comparison of bitemporal and unitemporal epilepsy defined by depth electroencephalography[END_REF][START_REF] Lim | Etiologic factors for unitemporal vs bitemporal epileptiform discharges[END_REF][START_REF] Janszky | Clinical differences in patients with unilateral hippocampal sclerosis and unitemporal or bitemporal epileptiform discharges[END_REF]. Bilaterality was also not linked to the epilepsy duration, a finding previously reported [START_REF] Napolitano | Two types of remote propagation in mesial temporal epilepsy: analysis with scalp ictal EEG[END_REF][START_REF] Boling | Surgical treatment of independent bitemporal lobe epilepsy defined by invasive recordings[END_REF].

Our findings rather suggest that bilaterality is associated with particular anatomical and functional pathways. We indeed found that, within mesial networks, sub-hippocampal regions may be prominently epileptogenic in BTLE. These regions include the entorhinal and perirhinal cortices anteriorly and the parahippocampal cortex posteriorly [START_REF] Amaral | Hippocampal formation[END_REF][START_REF] Insausti | The human entorhinal cortex: a cytoarchitectonic analysis[END_REF]. Clinical and experimental evidence have demonstrated that that the EC is a key structure participating in epileptogenic networks in MTLE [START_REF] Spencer | Entorhinal-hippocampal interactions in medial temporal lobe epilepsy[END_REF][START_REF] Bartolomei | Pre-ictal synchronicity in limbic networks of mesial temporal lobe epilepsy[END_REF][START_REF] Bartolomei | Entorhinal cortex involvement in human mesial temporal lobe epilepsy: an electrophysiologic and volumetric study[END_REF]. Using a nonlinear measure of SEEG signal interdependencies the EC was found to be the leader structure in almost half of the patients' seizures and a correlation was found between EC atrophy and its leadership during seizures [START_REF] Bartolomei | Pre-ictal synchronicity in limbic networks of mesial temporal lobe epilepsy[END_REF][START_REF] Bartolomei | Entorhinal cortex involvement in human mesial temporal lobe epilepsy: an electrophysiologic and volumetric study[END_REF]. Some experimental studies also suggested that the EC may have a lower seizure threshold than the hippocampus [START_REF] Wilson | Seizure activity in vitro: a dual focus model[END_REF][START_REF] Bragdon | Suppression of interictal bursting in hippocampus unleashes seizures in entorhinal cortex: a proepileptic effect of lowering [K+]o and raising [Ca2+]o[END_REF][START_REF] Heinemann | Entorhinal cortex-hippocampal interactions in normal and epileptic temporal lobe[END_REF]. The fact that subhippocampal regions including the EC are more epileptogenic in bitemporal epilepsies is however a novel finding.

The specific role of these subhippocampal regions in bitemporal epilepsies could be linked to their dense connections in human with the contralateral temporal regions, in contrast with the hippocampal formation [START_REF] Adam | How do the temporal lobes communicate in medial temporal lobe seizures?[END_REF]. Three commissures connect the temporal lobes: the anterior commissure (AC), the ventral hippocampal commissure (VHC) and the dorsal hippocampal commissure (DHC). Compared to lower mammals, inter-hippocampal connections are less developed in human. Indeed, the VHC (connecting the hippocampi in lower mammals like rats) is almost absent in primates. The DHC connects the entorhinal cortex to presubiculum [START_REF] Amaral | The commissural connections of the monkey hippocampal formation[END_REF] and the homologous parahippocampal gyri [START_REF] Demeter | Interhemispheric pathways of the hippocampal formation, presubiculum, and entorhinal and posterior parahippocampal cortices in the rhesus monkey: the structure and organization of the hippocampal commissures[END_REF]. This phylogenic trend (quasi-disappearance of the VHC) has been confirmed in humans by an autopsy study [START_REF] Gloor | The human dorsal hippocampal commissure. An anatomically identifiable and functional pathway[END_REF]. Inter-amygdalar connections have also decreased in human brains [START_REF] Demeter | Fields of origin and pathways of the interhemispheric commissures in the temporal lobe of macaques[END_REF]. In humans, the anterior commissure (AC) appears as a major source of bitemporal connexions from the subhippocampal regions. The AC forms an important fiber bundle ensuring the bidirectional connexion of the anterior part of the temporal lobes, including temporal pole and parahippocampal regions. The AC could be further developed in humans compared to those of non-human primates [START_REF] Virgilio | Cortical regions contributing to the anterior commissure in man[END_REF].

Adam et al described a case with a fast (~100 milliseconds) contralateral propagation of after-discharges induced by trains of 50 Hz stimulations, only when they were applied in the perirhinal cortex, and hypothesized that this "direct transcommissural transfer" was achieved through the anterior commissure [START_REF] Adam | Fast contralateral propagation of after-discharges induced by stimulation of medial temporal lobe[END_REF]. Two recent studies have investigated connections between human temporal (and frontal) cortices by intracranial electroencephalographic responses to 1-ms single pulses electrical stimulations. Contralateral temporal connections were rare but more frequent between entorhinal cortices or fusiform cortices [START_REF] Lacruz | Frontal and temporal functional connections of the living human brain[END_REF][START_REF] Jimenez-Jimenez | Incidence of functional bi-temporal connections in the human brain in vivo and their relevance to epilepsy surgery[END_REF]. More recently, the DHC (but not the VHC) was found in the brains of healthy subject using MRI tractography [START_REF] Colnat-Coulbois | Tractography of the amygdala and hippocampus: anatomical study and application to selective amygdalohippocampectomy[END_REF]. It has been already shown that short (<5 sec) or very short (<0.5 sec) interhemispheric propagation times are negative prognostic factors for post-surgical outcome in TLE [START_REF] Lieb | Interhemispheric propagation time of human hippocampal seizures. I. Relationship to surgical outcome[END_REF].

Our findings are in keeping with these anatomical findings, as our BTLE patients displayed a subhippocampal EZ (located in EC and/or pPHG) and we can postulate that this bilateral condition is sustained by its specific anatomic connections.

The treatment of BTLE is particularly problematic and disappointing. Surgery can be considered in cases with a predominant side, but the often disappointing results of this approach indicate that other therapeutic options should be developed. Among these, chronic stimulations of the hippocampus have been proposed, with variable long-term results [START_REF] Mclachlan | Bilateral hippocampal stimulation for intractable temporal lobe epilepsy: impact on seizures and memory[END_REF][START_REF] Vonck | A decade of experience with deep brain stimulation for patients with refractory medial temporal lobe epilepsy[END_REF]. However, our findings suggest that targeting the entorhinal/parahippocampal cortex could be an interesting alternative in this perspective.

Legends of Figure and Tables

Figure 1 :

 1 Figure 1: Example of a BTLE patient with bilateral synchronous TL seizures (patient #5) ; A:

Figure 2 :

 2 Figure 2: Example of a BTLE patient with right and left independent TL seizures (patient

Figure 3 :

 3 Figure 3: EI values, ranging from 0 (no epileptogenicity) to 1 (maximal epileptogenicity) in

Table 1 :

 1 Demographic, clinical and neuroimaging findings in both groups of patients.

	Abbreviations: BTLE: bilateral temporal epilepsy, UTLE unilateral temporal epilepsy, R;
	right, L: left, FCD: focal cortical dysplasia, HS: hippocampal sclerosis, DNET:
	dysembryoplasic neuroepthelial tumour, VNS: vagal nerve stimulation, ATL: anterior
	temporal lobectomy, GK: gamma knife.

Table 2 :

 2 SEEG and anatomical data including the different explored regions, the number of recorded seizures, the EZ and the number of epileptogenic structures (regions disclosing EI>0.4) for each patient in both groups. Abbreviations: L: left, R: right; iTP: internal temporal pole, eTP: external temporal pole, A: amygdala, EC: entorhinal cortex, aHip: anterior hippocampus, pHip: posterior hippocampus, pPHG: posterior part of the parahippocampal gyrus, STG: superior temporal gyrus, MTG: middle temporal gyrus, ITG: inferior temporal gyrus;O-T: occipito-temporal cortex.

			Age at
	B-MTLE	Gro	epilepsy	Epilepsy			Therapeutic	Surg
	patients	up	onset	duration	MRI	FDG PET	actions	ery
		BTL
	1	E	15	44	normal	*	medical treatment	*
		BTL
	2	E	8	33	R temporal FCD	R temporal hypometabolism	VNS (12/2012)	*
		BTL
	3	E	9	24	R HS	L temporal hypometabolism medical treatment	*
		BTL
	4	E	18	19	normal	*	medical treatment	*
						L post temporal
		BTL			L temporal periventricular	hypermetabolism
	5	E	16	23	heterotopia	(heterotopia)	VNS (03/2012)	*
		BTL				L ant/int temporal
	6	E	15	22	hypothalamic hamartoma	hypometabolism	VNS (01/2012)	*
		BTL				bilateral prefrontal
	7	E	35	12	R subhippocampal FCD	hypometabolism	medical treatment	*
		BTL
	8	E	2	36	R HS	L temporal hypometabolism	VNS (05/2012)	*
		BTL
	9	E	25	22	bilateral HS (L>R)	L temporal hypometabolism medical treatment	*
		BTL
	10	E	7	36	normal	L temporal hypometabolism medical treatment	*
		BTL
	11	E	11	6	L HS	L temporal hypometabolism	left ATL (2012)	III
		BTL
	12	E	13	19	normal	normal	medical treatment	*
		BTL				bilateral hypometabolism
	13	E	24	7	L hippocampal atrophy	(L>R)	medical treatment	*
		BTL
	14	E	28	17	normal	R temporal hypometabolism	VNS (03/2014)	*
		BTL				bilateral hypometabolism
	15	E	12	28	R hippocampal and amygdalar FCD	(R>L)	VNS (12/2013)	*
		UT
	16	LE	6	9	L TL ganglioglioma	*	left ATL (2002)	III
		UT
	17	LE	8	30	normal	*	left ATL (2003)	III
		UT					left AH (2002); left
	18	LE	17	14	L HS	*	ATL (2004)	II
		UT					left GK (1993); left
	19	LE	1	54	L HS	*	ATL (2003)	I
		UT
	20	LE	11	2	R DNET	R temporal hypometabolism	ATL (2009)	I
		UT
	21	LE	10	20	R HS	*	right ATL (2000)	I
		UT
	22	LE	25	13	L HS	*	left ATL (2001)	I
		UT
	23	LE	42	10	normal	L temporal hypometabolism	left ATL (2013)	II
		UT					left temporal
	24	LE	6	38	bilateral HS	L temporal hypometabolism	cortectomy (2013)	I
		UT
	25	LE	8	19	L HS	L temporal hypometabolism	left ATL (2009)	I
		UT
	26	LE	37	4	bilateral oligodendroglioma (R>L)	R temporal hypometabolism	right ATL (2010)	II
		UT				bilateral hypometabolism
	27	LE	15	18	normal	(L>R)	surgery refused	*
		UT
	28	LE	17	10	R hippocampal atrophy	R temporal hypometabolism	right GK (2011)	I
		UT				R temporo-perisylvian
	29	LE	6	36	R HS	hypometabolism	right ATL (2007)	I
		UT			R temporal lateral and polar (+
	30	LE	25	36	frontal) post-traumatic lesion	R temporal hypometabolism	Right ATL (2013)	I

Acknowledgements

We thank Prof Jean Regis and Dr Romain Carron (Functional Neurosurgery department, Marseille), Prof Jean-Christophe Sol (Neurosurgery department, Toulouse), Dr Nicolas Reyns (Neurosurgery department, Lille), and Prof Marc Guenot (Neurosurgery department, Lyon) for SEEG and surgical procedures. We thank Virginie Laguitton for neuropsychological examination.

Conflict of interest

None of the authors has any conflict of interest to disclose.


Ines Khoufi
email: ines.khoufi@inria.fr

Pascale Minet
email: pascale.minet@inria.fr

Anis Laouiti
email: anis.laouiti@telecom-sudparis.eu

Fault-Tolerant and Constrained Relay Node Placement in Wireless Sensor Networks

In this paper we focus on wireless sensor networks deployed to cover some given Points of Interest (PoIs), achieve connectivity with the sink and be robust against link and node failures. The Relay Node Placement problem (RNP) consists in minimizing the number of relays needed and the maximum length of the paths connecting each PoI with the sink. We propose a solution that determines the positions of relay nodes based on the virtual grid computed by the optimal deployment for full area coverage. We compare our solution with two different solutions based respectively on 1) the straight line that builds the shortest path between each PoI and the sink, 2) the Steiner point that connects PoIs together. We then extend these algorithms to achieve k-connectivity. Our solution outperforms the Steiner points solution in terms of maximum path length on the one hand, and the straight line solution in terms of total number of relay nodes deployed on the other hand. We also apply our solution in an area containing obstacles and show that it provides very good performances.

I. CONTEXT AND MOTIVATIONS

Since the deployment cost of wired networks in industrial environments is very high, not all sources of potential information related to the industrial process have been connected to the wired network even though they would provide very useful information for analyzing and improving the industrial process. That is why a wireless sensor network (WSN) is used to cover some given points of interest (e.g. a leaking valve). The sensor nodes are responsible for sensing their environment (e.g. a flowmeter for a pipe) and transmitting useful data usually in multi-hop manner to a sink for their analysis. It is often necessary to deploy additional wireless nodes to act as relays to ensure connectivity with the sink. Network connectivity is an important challenge in WSNs since several factors may cause the failure of wireless transmissions. On the one hand, wireless communication links may be unstable for many reasons: interferences, multipath propagation and fading to name but a few. On the other hand, sensor nodes may exhaust their source of energy, usually a battery. As a consequence, the wireless sensor network must be able to tolerate link and node failures.

In this paper we focus on wireless sensor networks deployed to cover some given points of interest, achieve connectivity with the sink and be robust against link and node failures. More precisely, we want to minimize the number of relays deployed as well as the maximum length of paths connecting each PoI with the sink. The reason is that the transfer of any message on a longer path consumes more bandwidth and more energy. These resources are limited in a wireless sensor network. Since the reliability of a path is equal to the product of the reliability of each link composing it, a long path is less reliable than a short one, assuming that all links have a similar reliability and links of poor quality are not selected in path building. Hence, to maximize robustness, we will favor short paths from any PoI to the sink. In addition, the end-to-end delivery delay depends on the number of hops involved. That is why short paths are favored, provided that they are able to ensure the quality of service (QoS) required by the application.

This paper is organized as follows. In Section II, we give a brief state of the art related to the coverage of points of interest and connectivity including methods based on Steiner points. We then see how to improve robustness with k-connected networks. In Section III, we formally define the relay node placement problems we study and list our assumptions. In Section IV, assuming no link/node failure, we study three solutions based on heuristics: the Straight Line, the Steiner Point and the Triangular Grid based solutions. We compare them in terms of the number of relay nodes needed, the path length to the sink and the average node degree. In Section V we then improve these solutions to achieve robustness with regard to link and node failures and evaluate their performance. In Section VI, we show how to extend our solution to cope with obstacles. Finally, we conclude in Section VII.

II. STATE OF THE ART

The first coverage problem that has been studied in WSNs deals with full area coverage [START_REF] Khoufi | Survey of deployment algorithms in wireless sensor networks: coverage and connectivity issues and challenges[END_REF]. When the sens-ing range r and the communication range R of sensor nodes satisfy the following inequation R ≥ r √ 3, full coverage implies connectivity. The optimal deployment (i.e., the deployment that ensures full area coverage with the minimum number of sensor nodes) is given by an equilateral placement of sensor nodes in the area considered, as proved in [START_REF] Kershner | The number of circles covering a set[END_REF]. This deployment is optimal under the assumption of a disk based model for radio communication and sensing range. Although this deployment ensures that all the points of interest are covered and guarantees that they are connected to the sink, the number of sensor nodes required may result in a prohibitively high cost. That is why other strategies are preferred to cover PoIs.

To minimize the number of relay nodes (i.e, additional wireless nodes deployed to ensure connectivity with the sink), one strategy consists in using the property of the Steiner point in a triangle. For instance, the algorithm given in [START_REF] Lee | Optimized relay node placement for connecting disjoint wireless sensor networks[END_REF] builds the minimum Steiner tree on the convex hull of the points of interest. It proceeds iteratively. At each iteration, the algorithm selects the points of interest that have not yet been considered and the Steiner point of the previous iteration (if any), all these points belonging to the outermost convex hull not yet considered. The Steiner point of every three consecutive points of the convex hull is computed. The Steiner points are the optimized locations of the relay nodes. The algorithm stops when all PoIs have been selected. Additional relay nodes are added if necessary (i.e. when the distance is greater than the communication range) on each straight line connecting each PoI to its Steiner point as well as between any Steiner point obtained at iteration i and its Steiner point obtained at iteration i + 1. Many other algorithms based on the Steiner points principle exist in the literature [START_REF] Senel | Optimized relay node placement for establishing connectivity in sensor networks[END_REF].

To tolerate k -1 failures of wireless links or nodes, k-connectivity has been introduced. The authors of [START_REF] Almasaeid | On the minimum kconnectivity repair in wireless sensor networks[END_REF] focus on k-connectivity in a WSN while minimizing the number of relay nodes. The solution proposed takes benefit of overlapping node communication areas to place a relay node at the intersection of overlapping communication areas to achieve connectivity. Hence, this relay node is within transmission range of at least two other nodes. We will see in Section VI how this principle is adapted to cope with obstacles.

Another study [START_REF] Han | Fault-tolerant relay node placement in heterogeneous wireless sensor networks[END_REF] focuses on the problem of fault tolerant relay nodes placement in heterogeneous wireless sensor networks where sensor nodes and relay nodes have different communication ranges. The authors use the steinerization of edges to create a path between two sensor nodes. The idea is to start by deploying two relay nodes: each relay node is placed at a distance equal to the minimum communication range between sensor nodes and relay nodes, from each path extremity. Then, additional equidistant relays are added on the remaining path between the two relays deployed. Han et al. [START_REF] Han | Fault-tolerant relay node placement in heterogeneous wireless sensor networks[END_REF] formalized the relay node placement problem that minimizes the number of relay nodes deployed to ensure that there exists k ≥ 1 node-disjoint paths between every pair of nodes, a node being a sensor node or the base station. If k > 1, node placement is said fault-tolerant. The authors proposed approximation algorithms to solve these NP-hard problems.

Misra et al. [START_REF] Misra | Constrained relay node placement in wireless sensor networks to meet connectivity and survivability requirements[END_REF] studied the constrained relay node placement, where the relay nodes can only occupy a set of candidate locations and the number of relay nodes needed to connect each sensor node with k = 1 or 2 base station(s) through k node-disjoint paths. If k = 2 the relay node placement is said survivable. Misra et al. [START_REF] Misra | Constrained relay node placement in wireless sensor networks to meet connectivity and survivability requirements[END_REF] propose approximation algorithms to solve these problems.

However, our problem is different: we are interested in ensuring an efficient connectivity between each PoI and the sink. We do not focus on the connectivity between PoIs but want to minimize the length of the paths connecting each PoI with the sink, for efficiency reasons. Misra [START_REF] Misra | Constrained relay node placement in wireless sensor networks to meet connectivity and survivability requirements[END_REF] and Han [START_REF] Han | Fault-tolerant relay node placement in heterogeneous wireless sensor networks[END_REF] do not minimize the length of the path of each PoI to the sink, but the total weight of the tree including all PoIs, where the weight between two nodes is equal to the number of relays needed to ensure connectivity between them.

Another strategy comes from bio-inspired networks, where the evolution process of real organisms has naturally selected the most robust ones. The idea developed in [START_REF] Nazi | Deployment of robust wireless sensor networks using gene regulatory networks: An isomorphism-based approach[END_REF] is to extract from the Gene Regulatory Network (GRN) of living organisms (e.g., yeast and the E. coli bacterium) a subnetwork with the same number of nodes as the number of sensor nodes to deploy and finally to place sensor nodes in a grid such that there is an isomorphism between the edges in the GRN subnetwork and their counterparts in the WSN. The authors show that these bio-inspired networks have very interesting structural properties such as a shorter average path length, a smaller average network diameter and fewer disconnected components to the sink after a random removal of edges, etc. We adopt these metrics for the performance evaluation of our solution. Our solution has structural properties inherited from the grid (i.e. triangular tesselation) providing the optimal deployment [START_REF] Mahfoudh | GDVFA: A distributed algorithm based on grid and virtual forces for the redeployment of wsns[END_REF].

In this paper, we are interested in monitoring PoIs by deploying relay nodes to ensure connectivity between each PoI and the sink. To do so, we propose an algorithm based on the deployment that has been proved optimal for full area coverage and compare its performance with these of Straight-Line and Steiner-Point based algorithms. We also focus on increasing robustness by ensuring k node-disjoint paths from each PoI to the sink and study how obstacles can be tackled. The presence of obstacles implies that some places are forbidden for the placement of relays. However, this is not the only constraint: two nodes at a distance less than R may be unable to communicate because of the presence of an obstacle between them.

III. RELAY NODE PLACEMENT PROBLEMS

A. Problem definitions

Before defining the Relay Node Placement problems (RNP), we first define our notations. Let P denote the set of PoIs that must be covered. We have P = {P 1 , P 2 , . . . , P n }, with n ≥ 1. Let P 0 be the sink. Let R be the communication range of relays and sensor nodes. Let L(i) be the length of the path of any PoI P i to the sink, with i ∈ [1, n]. Let N r be the number of relay nodes deployed to ensure connectivity of each PoI with the sink.

With regard to relay node placement, we distinguish two types of problems:

• The relay node placement, called RNP problem:

to minimize the number of relay nodes deployed as well as the maximum length of the paths connecting each PoI to the sink:

min{N r • max i∈[1,n] L(i)}. (1)
We define a variant of this problem where relay nodes cannot be placed anywhere: relay node placement is constrained by the presence of obstacles and the border of the area considered. On the one hand, the presence of obstacles constrains the placement of relay nodes: places within an obstacle are forbidden. On the other hand, the presence of obstacles may cause hidden nodes that may break connectivity. The constrained relay node placement, called C-RNP problem: to minimize the number of relay nodes deployed in an area with obstacles as well as the maximum length of paths connecting each PoI to the sink:

min obstacle {N r • max i∈[1,n] L(i)}. ( 2
)
where obstacles are taken into account (e.g. forbidden places and connectivity loss).

• The fault-tolerant relay node placement, called FT-RNP problem: to minimize the total number of relay nodes deployed as well as the maximum lengths of primary paths and secondary paths connecting each PoI to the sink, respectively:

Each PoI is connected to the sink via k node- disjoint paths. min{N r • max i∈[1,n] Lp(i) • max i∈[1,n] Ls(i)}. (3)
where Lp(i) is the length of the primary path of PoI P i to the sink, Ls(i) is the length of the secondary path of PoI P i to the sink and N r the total number of relay nodes deployed to ensure k-connectivity of each PoI with the sink.

Similarly, we can define a variant, where the faulttolerant relay node placement is constrained by obstacles. The constrained fault-tolerant relay node placement, C-FT-RNP problem: to minimize the number of relay nodes deployed in an area with obstacles as well as the maximum length of primary paths and secondary paths connecting of each PoI to the sink, respectively:

min obstacle {N r • max i∈[1,n] Lp(i) • max i∈[1,n] Ls(i)}.
(4) where obstacles are taken into account(e.g. forbidden places and connectivity loss).

B. Network model

We assume a disk-based model for radio communication. All nodes, (i.e. relay nodes and sensor nodes) have the same communication range R. Two nodes at a distance less than or equal to R are able to communicate with each other in the absence of obstacles. Obstacles prohibit the presence of sensor nodes in certain locations and may prevent direct communication between sensor nodes. We distinguish two types of obstacles: opaque and transparent.

• Transparent obstacles, have no impact on both the sensing range and the communication range of nodes. They only prohibit the presence of nodes.

• Opaque obstacles, like transparent obstacles prohibit the presence of nodes. However, they may prevent the communication between nodes at a distance < R, as seen in Section VI.

IV. RELAY NODE PLACEMENT: RNP

In this section, we assume there is neither link/node failure, nor obstacles. We will see later how to relax these assumptions. We present three solutions based on heuristics: an intuitive solution based on the straight line, a solution based on the Steiner point and finally our proposed solution based on the triangular grid.

A. An intuitive solution: The Straight-Line heuristic

The straight-line-based algorithm is the simplest solution and the most intuitive one that we propose as a baseline for comparison. It is inspired from a wired classical deployment where each PoI is linked to the sink with a straight line cable. Here we simply propose to cut the wires and deploy a set of relay nodes along that path between each PoI and the sink. This algorithm deploys a relay node every R meters on the straight line binding a PoI to the sink. Hence, each PoI is connected to the sink by the shortest path, as illustrated in Figure 1 where 14 PoIs are connected to the sink. However, this solution has two main drawbacks. First, it is not robust: on any path to a PoI, the failure of a single node or link disconnects the PoI concerned if there is no neighboring node to bypass the failed node or link. Second, no relay node is shared between PoIs. Hence, the number of relays deployed may be very high. The Steiner-Point-based algorithm builds a path from each PoI represented in red to the sink in green using the closest neighbor which may be another PoI, a Steiner Point in blue or simply a relay node, as illustrated in Figure 3 where 14 PoIs in red are connected to the sink in green. An initial consequence is that this algorithm enables PoIs to share some relay nodes, thereby reducing the total number of relay nodes needed, as we will see in Section IV-D2. The second consequence is that the path from a PoI to the sink may lead further away from the sink before getting closer to the sink, like for instance the path originated at node 78 in Figure 3. This phenomenon is evaluated by the path length from each PoI to the sink in Section IV-D3.

C. Our solution: the Triangular-Grid-Based Algorithm

The solution we propose, uses the virtual grid of the deployment proved optimal in [START_REF] Kershner | The number of circles covering a set[END_REF] and defined in the circumscribing rectangle which includes all the PoIs. In this deployment, nodes are placed according to a triangular lattice. We propose to build the shortest path from each PoI to the sink using only relay nodes belonging to the optimal deployment grid. In the final deployment, only relay nodes that are used by at least one PoI are kept. This solution favors both the sharing of relay nodes between PoIs in red and short paths to the sink in green where relay nodes are represented in blue, as illustrated in Figure 4 where 14 PoIs are connected to the sink. This solution is called Triangular-Grid-Based algorithm. We do not claim that this algorithm provides an optimal deployment but only that it tends to minimize the number of relays deployed as well as the length of the path from any PoI to the sink.

D. Performance Evaluation

For the performance evaluation of the three solutions previously described, we developed our own simulation tool in Java and implemented the three solutions. The choice of a Java simulation tool is motivated by the need to obtain fast performance results, noticing that these results do not depend on the network communication protocols used by the WSN in question. We consider different configurations where the number of PoIs varies from 15, 30 to 45. For each configuration characterized by a given number of PoIs, we randomly select the position of each PoI (at a distance higher than 2R from the sink) in the area considered which corresponds to a square of size L = 25r, where r is the sensing range of the nodes. The communication range R meets R = √ 3r. In our simulations, r = 20m and R = 34.64m. The results depicted in the figures correspond to the average of 20 simulations per configuration. In this performance evaluation, the sink is assumed to be at the area center.

1) Performance metrics: More precisely, we compare the three solutions using the following metrics:

• Total number of nodes deployed: we want to know the number of additional relays deployed to ensure connectivity of each PoI with the sink.

• Number of shared nodes: if a node belongs to at least two paths originating from different PoIs, it is considered to be shared. • Path length to the sink: we measure the average and maximum length of the paths connecting each PoI to the sink. • Average node degree: we evaluate the average number of one-hop neighbor nodes per node (i.e. the average number of nodes located in the transmission range of the node considered).

• RNP index: we define the RNP index of a relay node placement as With regard to this metric, the Triangular-Grid-based algorithm minimizes the total number of nodes deployed. Unlike the Steiner-Point and the Triangular-Grid based algorithms, the Straight-Line based algorithm does not share any relay nodes between paths connecting different PoIs to the sink. As a consequence, the total number of nodes deployed is higher. See Figure 6. I shows that the RNP index strongly increases with the number of PoIs for the straight line solution. Its increase is less strong with the Steiner point solution, whereas it is moderate for the triangular grid based solution. In all configurations tested, the triangular grid based solution provides the smallest RNP index. For instance, for 45 PoIs it is 2.8 times less than the straight line.

RN P index = N r • max i∈[1,n] L(i).

V. FAULT-TOLERANT RNP

Assuming that link and/or node failures may occur, we now show how to improve the robustness of the three algorithms described in Section IV. To cope with node and/or link failures, an additional path is built from each PoI to the sink. For any PoI and for any algorithm considered, the first path to the sink obtained by the algorithm is called the primary path, whereas the others, obtained as explained in this section, are called secondary paths. The robustness of the Straight-Line algorithm is ensured by providing k-connectivity. This algorithm replicates each shortest path k -1 times. Each PoI appears to be at the end of a petal, whose other end is the sink, as depicted in Figure 8a, where 2-connectivity is provided. This algorithm remains very simple but no relay node is shared by the PoIs to reach the sink.

A. The Straight-Line Algorithm

Furthermore, we observe a high concentration of nodes around the sink when the number of PoIs increases. This may induce high interference.

B. The Steiner-Point-Based Algorithm

Since in the basic version presented in Section IV, no redundancy is provided, there is no robustness: the failure of a link or node prevents data from at least one PoI reaching the sink. To achieve 2-connectivity, the straight line path from each PoI to the sink is added (see Figure 8b). Hence, there are no additional shared nodes compared with the basic version with only one path per PoI.

C. The Triangular-Grid-Based Algorithm

This solution is made robust by adding one nodedisjoint shortest path for each PoI to the sink. This new path shares no nodes with the primary path of the PoI in question, as depicted in Figure 9a. However it may share nodes or links with the primary or secondary path of another PoI, thus reducing the total number of nodes deployed. Figure 9b depicts shared nodes with black circle: at least two paths originating from different PoIs use a shared node to reach the sink. In the triangular lattice of the optimal deployment, each non-border node has 6 neighbor nodes. Consequently, we can obtain any k-connectivity with k ≤ 6. If a higher connectivity is required, another grid structure must be used.

D. Performance Evaluation

These three solutions being enhanced to achieve 2connectivity, we now compare their performances for various configurations. In addition to the metrics given in Section IV-D1, we add a new metric: the node degree. The RNP index is modified to take into account fault-tolerance. By definition, a fault-tolerant relay node Simulation results depicted in Figure 11 show that for both the Steiner-Point and the Triangular-Grid based algorithms, the number of shared nodes increases with the number of PoIs. Moreover, with the Triangular-Grid based algorithm, the deployment around the sink becomes very close to the optimal one defined in [START_REF] Kershner | The number of circles covering a set[END_REF].

2) Path Length to the Sink: Figure 12 shows that for each algorithm considered, the maximum path length is identical when maintaining one path or two-paths with either the Steiner-Point or the Straight-Line algorithm. For the Triangular-Grid algorithm, the secondary path has a length that is either equal to that of the primary path or greater by one hop. To reduce the data gathering delays in a WSN deployed according to the Steiner-Point algorithm, we recommend exchanging the role of primary and secondary paths by using the Straight-Line path as the primary path. 3) Node Degree: In the optimal deployment based on a triangular lattice, each non-border node has exactly 6 neighbor nodes. As a consequence, the degree of any node is upper bounded by 6 for any number of paths k ≤ 6. Simulation results depicted in Figure 13 show that for one path, the average node degree remains in the interval [START_REF] Kershner | The number of circles covering a set[END_REF][START_REF] Senel | Optimized relay node placement for establishing connectivity in sensor networks[END_REF] for all the numbers of PoIs tested, whereas for two paths, it remains in the interval [START_REF] Senel | Optimized relay node placement for establishing connectivity in sensor networks[END_REF][START_REF] Han | Fault-tolerant relay node placement in heterogeneous wireless sensor networks[END_REF]. However, with the Straight-Line algorithm, the node degree strongly increases with the number of PoIs, even for a single path. This is due to the very high density of nodes close to the sink and the non-sharing of nodes between the paths. Furthermore, the Steiner-Point algorithm provides the smallest average node degree, because paths are not built toward the sink but between PoIs and relay nodes. More precisely, the sink is considered as a PoI and not as the target destination of any path originating at a PoI. For this reason, with the Steiner-Point algorithm, there is no concentration of nodes around the sink, unlike with the Straight-Line and the Triangular-Grid algorithms as depicted in Figures 3, 1 and4 respectively.

4) Computation of the FT-RNP index: Table II shows that the triangular grid based solution provides the smallest FT-RNP index in fault-tolerant RNP. This is due to

VI. CONSTRAINED FAULT-TOLERANT RNP

In the previous sections, the PoIs and the sink are located in an area that does not contain any obstacles. However, in some applications, this assumption should be relaxed since obstacles may exist. In this section, we focus on ensuring k-connectivity between PoIs and the sink in an environment where obstacles are present.

A. The Straight-Line Algorithm

The Straight-Line algorithm that provides the minimum number of relay nodes cannot be applied to ensure network connectivity in the presence of obstacles since obstacles may exist on the straight line between the PoI and the sink. However, this solution can be enhanced to cope with obstacles. To keep the characteristic of this method, the relay nodes are deployed along a straight line between the PoI and the sink. The presence of an obstacle on this line is analog to the problem of void handling in geographic routing [START_REF] Chen | Geographic routing in wireless ad hoc networks[END_REF]. One possible solution could be to follow the left-hand rule to bypass the obstacle. However, this solution is not optimal in terms of path length and the number of additional nodes deployed.

B. The Steiner-Point based Algorithm

The Steiner-Point based algorithm cannot cope with the presence of obstacles. Since the computation of the Steiner Point position depends neither on the shape of the area nor on the presence of obstacles, the Steiner Point position could be inside an obstacle. If this position is moved, the mathematical property is lost. Therefore, we do not consider any enhancement of this solution to cope with obstacles.

C. The Triangular-Grid based algorithm

When there is no obstacle in the area considered, the virtual grid of the optimal deployment ensures full area coverage and network connectivity. In this case, at least one path to the sink can be ensured. On the other hand, in the presence of obstacles, not only coverage holes may occur but also isolated PoIs may exist. In fact, when we apply the optimal deployment in an area containing obstacles, nodes that belong to the virtual grid and whose location is inside obstacles are removed, which may result in coverage holes occurring around obstacles. Depending on the PoI position and the sink position, these coverage holes may cause isolated PoIs, particularly if the PoI is surrounded by obstacles.

In a previous study [START_REF] Khoufi | A simple method for the deployment of wireless sensors to ensure full coverage of an irregular area with obstacles[END_REF], we proposed a solution based on the optimal deployment to ensure full area coverage and network connectivity in the presence of opaque obstacles. We healed coverage holes caused by obstacles by deploying additional nodes in these coverage holes. This final deployment which can cope with obstacles is used as our new virtual grid. Using this virtual grid and the principle of the Triangular-Grid based algorithm, network connectivity can be ensured between each PoI and the sink, as depicted in Figure 14. If now we want to Fig. 14: Connectivity between each PoI and the sink in the presence of obstacles. support k-connectivity in the presence of obstacles, we may obtain a network like that depicted in Figure 15 for 2-connectivity. There are two paths with disjoint nodes to connect each PoI to the sink. Hence, the failure of nodes on a single path does not disconnect a PoI. However, we observe two problems: bypassing the obstacle leads to a secondary path that is much longer than the primary path (see, for instance, PoI 5 at the bottom right in Figure 15).

there is a gap between the primary and the secondary paths preventing any node on the primary path from communicating with a node on the secondary path. In Figure 15 we can see a relay node on the primary path of PoI 4 that has no neighbor on the secondary path due to the gap between the two paths.

For each relay node on the secondary path we need to have at least one neighbor on the primary path. As a consequence, any node on the primary path can bypass its successor using a node on the secondary path. To cope with the gap problem, the secondary path should be built using the neighbors of all relay nodes on the primary path instead of all the deployed nodes. Due to the presence of obstacles, some neighbors of the virtual grid may not exist or may not be able to communicate with each other. That is why we propose the rule depicted in Figure 16 where a relay node is added to build the secondary path. The location of this node is critical. First, it should communicate with its downstream neighbor on the secondary path. Second, it should communicate with a relay node of the primary path. Finally, it should communicate with:

• either its upstream neighbor on the secondary path if one exists as depicted in Figure 16 case 2, • or the upstream neighbor of the relay node in the primary path as illustrated in Figure 16 case 3. Figure 17 shows the final deployment of relay nodes after applying this rule. We can observe that for all the PoIs, any node on the primary path can communicate with a node on the secondary path. Also, we can see the relay node added in pink on the secondary path of PoI 5 which solves two problems: bypassing the obstacle and overcoming the gap between the two paths.

D. Performance Evaluation

In this section, we evaluate the impact of the presence of obstacles in the area depicted in Figure 14, using two configurations: 6 PoIs and 15 PoIs. Results are averaged over several simulations for each configuration (6 and 15 PoIs). The performance evaluation metrics are the total number of relay nodes deployed, the number of shared nodes, the average path length, the maximum path length and the RNP index. In Figure 18, the total number of relay nodes deployed when two paths are needed is less than twice the total number of relay nodes when one path is needed. This is true both with and without obstacles, and is due to the high number of nodes that are shared between paths from different PoIs. For instance, this number reaches 43% of the total number of nodes deployed for 15 PoIs when obstacles exist and two paths are required. The presence of obstacles tends to increase the number of shared nodes in narrow lanes.

The average path length value in the presence of obstacles is close to the average path length value when obstacles do not exist. This is due to the fact that our solution favors a secondary path which is close to the primary one.

The maximum path length depends on the shape of the obstacles. Although the primary and secondary paths are close, the secondary path may be longer than the primary path. This is due to the number and location of the neighbors of all the relay nodes of the primary path. Table III shows the strong impact of the presence

Fig. 1 :

 1 Fig. 1: The Straight-Line Algorithm for 14 PoIs. B. A solution based on relay sharing: the Steiner-Point By definition, the Steiner point S of three points A, B and C is the point that minimizes the sum of the distance to the three vertices of the triangle ABC. Hence, by definition of S, we have for any point P , d(A, S) + d(B, S)+d(C, S) ≤ d(A, P )+d(B, P )+d(C, P ), where d(A, B) denotes the euclidean distance between A and B. See Figure 2 for an illustration. Notice that the Steiner point of the three points A, B and C is B itself if the angle (A,B,C) is higher than or equal to 120 degrees.

Fig. 2 :

 2 Fig. 2: The Steiner point S of A, B and C.The Steiner-Point-based algorithm builds a path from each PoI represented in red to the sink in green using the closest neighbor which may be another PoI, a Steiner Point in blue or simply a relay node, as illustrated in Figure3where 14 PoIs in red are connected to the sink in green. An initial consequence is that this algorithm enables PoIs to share some relay nodes, thereby reducing the total number of relay nodes needed, as we will see in Section IV-D2. The second consequence is that the path from a PoI to the sink may lead further away from the sink before getting closer to the sink, like for instance the path originated at node 78 in Figure3. This phenomenon is evaluated by the path length from each PoI to the sink in Section IV-D3. C. Our solution: the Triangular-Grid-Based Algorithm

Fig. 3 :

 3 Fig. 3: The Steiner-Points-Based Algorithm for 14 PoIs.

Fig. 4 :

 4 Fig. 4: The Triangular-Grid-Based Algorithm.

2 )

 2 Number of Sensor Nodes Needed: Figure 5 depicts the total number of nodes deployed for each configuration, highlighting the number of additional nodes, also called relay nodes because they are deployed only to provide connectivity with the sink. Simulation results show that the Straight-Line-based algorithm deploys the highest number of relay nodes, whatever the number of PoIs. The total number of nodes is roughly proportional to the number of PoIs. The other two algorithms are less sensitive to the number of PoIs. For instance, for 45 PoIs, the number of additional nodes deployed by the Straight-Line-based algorithm is 3.7 times higher than that needed by the Triangular-Grid-based algorithm.

Fig. 5 :

 5 Fig. 5: Total and additional nodes deployed.

3 )Fig. 6 :

 36 Fig. 6: Total and shared nodes deployed.

Fig. 7 :

 7 Fig. 7: Maximum and average path length to the sink.

a

  Straight-Line. b Steiner-Point.

Fig. 8 :

 8 Fig. 8: 2-connectivity.

a

  Two paths. b Shared nodes.

Fig. 9 :

 9 Fig. 9: 2-connectivity with the Triangular-Grid.

Fig. 10 :

 10 Fig. 10: Total and additional nodes for 2-connectivity.

Fig. 11 :

 11 Fig. 11: Total and shared nodes for 2-connectivity.

Fig. 12 :

 12 Fig. 12: Maximum and average path length to the sink for 1 and 2-connectivity.

Fig. 13 :

 13 Fig. 13: Node Degree.

Fig. 15: 2 -

 2 Fig. 15: 2-Connectivity between each PoI and the sink in the presence of obstacles with problems.

Fig. 16 :

 16 Fig. 16: Rule to cope with missing relay nodes when obstacles exist.

Fig. 17

 17 Fig. 17: 2-Connectivity between each PoI and the sink in the presence of obstacles.

: 2 -

 2 Fig. 17: 2-Connectivity between each PoI and the sink in the presence of obstacles.

Fig. 18 :

 18 Fig. 18: Evaluation of the impact of obstacles.

  paths. In addition, it minimizes the total number of deployed nodes by sharing nodes between paths originating from different PoIs, like the Steiner-Point algorithm. Hence, the Triangular-Grid algorithm minimizes data gathering delays and improves the reliability of each path linking a PoI to the sink and reduces the energy consumed to collect data from PoIs. By limiting the degree of any node, it reduces interferences. In a real environment, obstacles are likely to be present. In such a situation, the Steiner Point-based solution fails to provide a valid deployment, and the Straight Line-based solution may lead to an expensive deployment in terms of the number of relay nodes. In contrast, our solution is able to cope with obstacles while providing robustness by means of disjoint-node paths.

TABLE I :

 I RNP index for RNP solutions

			RNP index
	Number	Straight-Line Steiner point	Triangular grid
	of nodes	based	based	based
	15	675.27	689.5	452.43
	30	1439.64	1440	680.92
	45	2193.34	1515.1	784.39

TABLE II :

 II FT-RNP index for fault-tolerant RNP solutions.

			FT-RNP index
	Number Straight-Line	Steiner point	Opt deployment
	15	12087.46	17988.38	7964.12
	30	26777.30	54853.63	11427.41
	45	41454.22	75292	12143.10

TABLE III :

 III Comparison of RNP index for constrained and unconstrained FT-RNP solution RNP index: triangular grid based method

	Number	One path	Two paths
	of nodes	Without	With	Without	With
		obstacles obstacles obstacles	obstacles
	6	135,93	183,69	1475,02	3463,68
	15	262,99	309	2652,22	5634,36