François Char Ifsttar-Lma
email: francois.char@ifsttar.fr

Thierry Serre
email: thierry.serre@ifsttar.fr

Analysis of pre-crash characteristics of passenger car to cyclist accidents for the development of Advanced Drivers Assistance Systems

Keywords: ADAS, Autonomous Braking, Collision Warning, Cyclist, Field Of View, range, Safety performance, Accident reconstruction

The purpose of this study was to analyze car-to-cyclist accidents to determine the challenges for an active safety system on car to avoid accidents. Based on 2261 car-to-cyclist accidents provided by in-depth accident databases, accidents are analyzed more specifically from kinematic reconstructions. The main accident scenarios are determined: crossing nearside, crossing farside, longitudinal, turning (right and left) and others. Proportion of brakes activation by the drivers before the impact was also given for those scenarios. The relative positions of the cyclists to the vehicle are analyzed from few seconds before the impact until the crash. It is observed that one second before the impact most of the cyclists were at a lateral distance smaller than 5m to the center line of the car and less than 20m ahead of car front. Finally, the possible detection of the cyclist by implemented sensors in the vehicle and the possible triggering of an active safety system like an Automatic Emergency Braking or a Forward Collision Warning are studied. Required detection sensors parameters, such as Field Of View (FOV) and the detection range, were analyzed relatively to the scenario's characteristics, e.g. remaining time after cyclist appearance and before the collision, differences between scenario types. Different sensor FOVs and detection ranges were analyzed to determine their possible rates of cyclist detection. The study concluded that a FOV of 60° and a range of 35m would detect most of the cyclists in car-to-cyclist accident scenarios. It was also concluded that in about 80% of cases, the last time to trigger brake (tLTTB), i.e. the last moment to brake in order to avoid the accident based on physical and comfort braking limitations by the car, was 1s before the collision. It was also calculated that with a FOV of 60°, 51% of cyclists could be detected up to 4s before tLTTB, and 72% up to 1s before tLTTB. Values found in this paper can be useful to determine some of the specifications of an Advanced Driver Assistance System (ADAS), e.g. detection sensor coverages, available time to trigger an autonomous emergency braking or forward collision warning device. Those values are given for general ADAS sensors specification but also per scenario in the case of sensors that can adapt to a specific scenario.

Introduction

It has been estimated that every year around 1.2 million people in the world die due to accidents on the road [START_REF] Who | Global status report on road safety, on-line[END_REF]. From the previous stated figure, it has also been found that pedestrians, cyclists and motorcyclists account for 49% of all the road traffic deaths [START_REF] Who | Global status report on road safety, on-line[END_REF]. Car manufactures as well as consumer organizations are contributing to the reduction of these type of fatalities by establishing new safety requirements and implementing new active safety systems on vehicles [START_REF] Euro | Test protocol -AEB VRU systems Version 2.0.2, EUROpean New Car Assessement Program. Euro NCAP[END_REF], which support drivers in avoiding or mitigating collisions with vulnerable road users (VRUs). Examples of these active safety systems are the Automatic Emergency Braking (AEB), which is able to trigger an autonomous braking in case of an imminent crash, and the Forward Collision Warning (FCW), which triggers a warning to the driver in the event of a possible collision with a VRU. The European New Car Assessment Program (Euro NCAP) is a safety performance assessment program focused in testing new safety systems to ensure high levels of performance [START_REF] Euro | Test protocol -AEB VRU systems Version 2.0.2, EUROpean New Car Assessement Program. Euro NCAP[END_REF]2018). In 2018, Euro NCAP presented their first protocol to test safety systems focused in car-to-cyclist scenarios [START_REF] Euro | Test protocol -AEB VRU systems Version 2.0.2, EUROpean New Car Assessement Program. Euro NCAP[END_REF]. The development of these safety systems as well as the test scenarios and safety requirements are the results of many research projects focused on analyzing car-to-cyclist accidents.

Several European research projects (e.g. AsPeCSS, CATS or PROSPECT) have focused in analyzing the accident configuration of the most common car-to-cyclist accident scenarios. The results of these projects has helped in developing better active safety systems as well as developing testing scenarios for assessing pedestrian or cyclist active safety systems. [START_REF] Schaller | Report describing the comparative survey of existing test protocols and test facilities[END_REF] used scenarios to develop test procedures for pedestrian safety systems based on GIDAS database analysis of vFFS Group. They found that crossing and turning scenarios represented up to 85% of the accident scenarios. [START_REF] Rodarius | Benefit estimate based on previous studies for pre-crash bicyclist systems and recommendations for necessary changes to pedestrian test and assessment protocol[END_REF] (AsPeCSS) analyzed the difference between pedestrian and cyclist accidents and proposed 4 tests scenarios for cyclist active safety systems. They proposed 1 crossing, 1 longitudinal, 1 turning left and 1 turning right scenarios. Uittenbogaard et al. (2016a, b) (CATS) analyzed car-tocyclist accidents to define accident scenarios for test protocol. They extracted 2 crossing, 2 longitudinal and 1 turning scenarios. [START_REF] Stoll | The addressed VRU scenarios within PROSPECT and associated test catalogue[END_REF] (PROSPECT) also defined test cases to validate active safety system performances which were similar to others previous works. By studying the moments before accidents occurred it is possible to determine the characteristics of active safety devices in terms of detection and trigger timing for passenger cars. The present paper aims at analyzing accident characteristics a few seconds before the crash.

An estimation of effectiveness of Forward Collision Warning (FCW), Automatic Emergency Braking (AEB), lane departure warning or automatic cruise control was determined by several studies [START_REF] Hamdane | Issues and challenges for pedestrian active safety systems based on real world accidents[END_REF][START_REF] Høye | Advanced driver assistance systemsstatus and future potential[END_REF][START_REF] Coelingh | Collision Warning with Full Auto Brake and Pedestrian Detection a practical example of Automatic Emergency Braking[END_REF][START_REF] Forkenbrock | A Forward Collision Warning (FCW) Performance Evaluation[END_REF]. The effect estimation is given in terms of killed or seriously injured people that can be avoided with these systems. According to these studies, from 9 to 16% VRU could be saved [START_REF] Høye | Advanced driver assistance systemsstatus and future potential[END_REF] and in terms of impact speed reduction up to 35 km/h could be gained [START_REF] Coelingh | Collision Warning with Full Auto Brake and Pedestrian Detection a practical example of Automatic Emergency Braking[END_REF]. If the detection range and FOV of these safety systems increased, higher number of VRUs could be saved as well as higher speed reductions could be obtained.

One of the objectives of this study is to determine the critical time to detect the cyclist and to trigger an action from an active safety device, action that potentially may avoid or mitigate the consequences.

Materials and methods

Accident data

Crashes data used in this study come from 2 in-depth accident databases, one from Germany and one from France.

The French accident cases were extracted from the "Etudes Détaillées d'Accidents (EDA)" crash database of IFSTTAR/LMA performed in the surrounding of Salon-de-Provence [START_REF] Ferrandez | L'étude détaillée d'accidents orientée vers la sécurité primaire[END_REF]. Each accident is investigated by a multidisciplinary team composed of a psychologist and a technician directly on the accident scene in real time at the same time of rescue team intervention. As much evidences as possible are gathered on the scene about involved vehicles and the environment, like vehicles final position, impact of vehicles (deformation, location of impact), marks left on the road (tyres, fluids, debris, etc.), weather and visibility conditions. Drivers statements, witnesses and injuries record based on medical reports are also collected. With those data, hypothesis of the accident mechanisms are made: trajectories of the vehicle and the cyclist, travelling speed, emergency manoeuver, etc. Then the scenario which has the best correlation with all the indications produced by the in-depth analysis is chosen.

The database from Germany is Pre-Crash-Matrix (PCM 160818_GIDAS _PCM_4.0_2016_1). In a similar way, the German methodology is described in [START_REF] Gidas | [END_REF]. GIDAS accidents are collected in the areas of Hanover and Dresden. Data concerning the car, the environment and the participants are collected like information relative to the condition of the cars and to the collision partner, the deformation, the general setting of the cars, the condition of safety systems and their function. The environment data are gathered in order to have the geometry of the street, the street's condition or traffic controls. Finally, data about the participants are collected like age, gender, information about driving experience, known disease, stress factors. An interview helps to get information about the progress of the accident from the participants' point of view. Additionally, data about injuries can be obtained to analyze long-term consequences.

Accidents selection criteria and clustering

In this study only accident cases involving one passenger car and one cyclist were considered. 30 cyclist accident cases were extracted from EDA and 2231 from the GIDAS-PCM. All those accidents were clustered into different scenarios based on the trajectories of the car and cyclist. The literature review reported different ways to cluster the cases depending on the view point. As example, [START_REF] Kuehn | Cyclist-car accidents -Their consequences for cyclists and typical accidents scenarios[END_REF] scenarios were based on cyclists' provenance, whereas CATS (Uittenbogaard et al. 2016a) and AsPeCSS project [START_REF] Rodarius | Benefit estimate based on previous studies for pre-crash bicyclist systems and recommendations for necessary changes to pedestrian test and assessment protocol[END_REF] chose to consider the trajectory of the passenger car as the main criterion. The latest was also chosen for this study to have the point of view from a car active safety device. The choice to select the 5 scenarios below was motivated by the fact that those scenarios are common scenarios that can be found in the literature. Thus, it appeared obvious to keep them.

-Crossing Nearside scenario (CN): the vehicle drives straight and a cyclist crosses from the closest side of the road (On a 1 way road, a cyclist crossing from the left or the right is also considered as a CN).

-Crossing Farside scenario (CF): the vehicle drove straight and a cyclist crossed at least one lane of road before being hit by the vehicle.

-Longitudinal scenario (L): the vehicle and the cyclist both travelled in the same direction on the road, and the car hits the cyclist in the rear during the travel or laterally during an overtaking manoeuver.

-Turning Left (TL) or Turning Right scenario (TR): the vehicle was turning left or right at an intersection and hits a cyclist whatever the trajectory of the cyclist. Situations where the vehicle was outside an intersection were excluded from this cluster. Cases where a vehicle followed a curve to the right (or to the left) and a cyclist crossed the road were clustered either in CN or CF scenario. Cases where a vehicle was in a curve and encountered a cyclist travelling in the same direction were clustered in the L scenario.

-Other scenarios: all accidents that could not be clustered in any of above scenarios.

Accidents reconstruction

In order to describe the pre-crash phase of the accident, a kinematic reconstruction was performed on the French accident cases investigated by IFSTTAR-LMA based on [START_REF] Lechner | Analysis and reconstruction of accident sequences[END_REF] methodology. At first the approximate trajectories of the vehicle and the cyclist were extracted and drawn in a reduced scale map using their initial and final positions. Objects in the scene that could occlude the cyclist were also added to the scene when the information was available. Then a temporal reconstruction was performed based on information like involved displacement speed, manoeuver (steering manoeuver or braking). During this temporal reconstruction, some assumptions were made: -The vehicle and the cyclist speeds were constant if there was no brake activation. After brake activation, a constant deceleration speed was considered until the impact.

-A constant deceleration was considered from initial brake trigger.

-The deceleration value was adjusted depending on road conditions, weather and brake conditions defined by experts.

-The cyclist displacement speed was estimated from its path to the point of collision with the car. Car deformation zones and participants' speed declaration may add further information to define cyclist's speed.

GIDAS accident pre-crash phase kinematics and information, readily available in GIDAS-PCM database, were used for this study in addition to French cases. The methodology to create PCM cases is defined in [START_REF] Schubert | Standardized Pre-Crash-Scenarios in digital format on the basis of the VUFO simulation[END_REF].

2.4 Pre-crash phase parameters analysis Several parameters were extracted for each accident case:

-Location of the cyclist relatively to the vehicle at different times (in second) to collision (TTC), -

Relative angular position and distance of the cyclist to the car -Last Time To Brake (LTTB) calculated using equation 1. The LTTB is a measure in distance which corresponds to the last moment to trigger the brakes in order to avoid the collision. LTTB is calculated according to equation ( 1) :

𝐿𝑇𝑇𝐵 = 𝑉² 2 * |𝑎| (eq. 1) [in meter]
Where V is the vehicle traveling speed (m/s), a is the deceleration (m/s²) that depends on road conditions. This formula is similar to the one used in [START_REF] Hamdane | Issues and challenges for pedestrian active safety systems based on real world accidents[END_REF]. It is also close to the one that can be found in [START_REF] Violette | Freinage d'urgence motos vs voitures particulières, Essais sur piste[END_REF] where the coefficient value estimation takes into account the transient state. In the current paper, an ideal braking model is considered excluding transient state and an average deceleration value of -8m/s² has been taken. This value corresponds to ideal conditions like dry surface, efficient braking system, etc., and corresponds to an average deceleration as found in [START_REF] Brach | Vehicle Accident Analysis and Reconstruction Methods[END_REF], [START_REF] Byatt | Manual of Road Accident Investigation[END_REF] and [START_REF] Lechner | Analysis and reconstruction of accident sequences[END_REF]. A comparison of this ideal model has been performed with a more realistic model as it can be found in [START_REF] Saadé | Prospective Evaluation of the Effectiveness of Autonomous Emergency Braking Systems in Increasing Pedestrian Road Safety in France[END_REF] and in [START_REF] Zhao | AEB effective evaluations by accident reconstructions using videos of drive recorders in perpendicular and turning car-to-cyclist collisions[END_REF]. In this more realistic model, the value a linearly increases from the trigger until it reaches the maximum deceleration of -8m/s² and the time needed to reach the maximum value is set to 0.15s. As the deceleration a value varies, the speed also varies accordingly to a. So, the LTTB distance travel is computed using (eq.1) according to the variation of a and the time step (0.01s). Distances are computed until the condition that the speed is equal to zero. The result of this comparison can be found in part 3.2. The analysis of above accident parameters allowed defining required sensor detection range, FOV and triggering time for an active safety device. The sensor was modelled at the geometrical center of the vehicle. Braking was the only avoidance manoeuver considered in this study. -The range detection was defined as a circle with a radius of ρ around the geometric center of the vehicle. It can almost be assimilated to a sensor located in front of the windscreen as a camera. Similarly, if the center of gravity of the cyclist was inside the range detection circle (i.e. 360° FOV), then the cyclist was considered as detected.

Detection rates for values of FOVs between 10° to 70° and ranges from 5m to 45m are computed in this study.

Those values include some values that can be found in [START_REF] Hamdane | Issues and challenges for pedestrian active safety systems based on real world accidents[END_REF] and the FOV is extended to higher value due to a possible effect of cyclist position due to speed. In the current paper, occlusion was considered only for the duration calculation before reaching the LTTB position.

Accident modeling results

After clustering, the proportion of accidents by scenario is given in Figure 2. The Turning scenario accounted for 34% of the cases, followed closely by the CN scenario (33%), the CF scenario (22%) and the L scenario which only represented 5% of the cases. The Turning scenarios consisted of about 12% of turning left cases and about 22% of turning right cases. The remaining scenarios classified as "Others" as they do not enter into one of the previous scenarios account for 6%. In order to better visualize the positions of the cyclists relative to the vehicles, Figure 3 shows cyclists' positions relative to the center of the vehicle for TTC 2s, 1.5s, 1s and 0.5s for all 2261 accidents considered in this study.

Figure 3 shows that cyclists were scattered 2s before the impact but are within 40m ahead from the vehicle front and -/+20m laterally to the car center line.

At TTC 1 second, most of cyclists were at a lateral distance to the car center line smaller than 5m and less than 20m ahead of car front. At TTC 0.5s, cyclists are mostly located in front of the vehicle and within -/+ 5m laterally to the car center. Appendix A shows more details of cyclists' relative positions to the car per scenario.

Figure 3: Cyclists' positions relative to the vehicle 2s, 1.5s, 1s and 0.5s before the impact.

Additionally, the brake trigger by the driver was also extracted from the accident databases. Among all cases (CN, CF, L, TL, TR and Others), only 33% of drivers braked before colliding with the cyclist. The brake trigger took place less than 1s before the impact for 80% of the drivers who had activated the brakes (see Figure 4). This proportion was slightly above 50% of the drivers for brake activation at TTC 0.5s. The cyclists' speed was estimated in 80% of all cases close to or below 20km/h (sees Appendix B). There was only some slight difference for the CN where 90% of the cyclists were estimated as having a speed near or below 20 km/h. Cyclists speed was higher compared to the 5km/h for a walking pedestrian [START_REF] Huang | Evaluation of remote pedestrian sensor system based on the analysis of carpedestrian accident scenarios[END_REF]).

Relevant parameters for ADAS

This part presents different results that can be relevant for the design of ADAS and is independent from results extracted in part 3.1. The range and FOV rate detection rates during accident progresses are computed to indicate sensor detection requirements. The detection rates per FOV are also computed at the last time to brake in second to indicate when to activate brake with the help of which FOV. Finally, the proportion of detected cyclist per FOV in function of the visibility duration before the last time to brake is given in order to indicate the available time for an ADAS to collect and process data and trigger before that critical instant.

Figure 5 shows the detection rate by FOV at different TTCs. It corresponds to the detection rate that can be reached for a given FOV during the progress of an accident. Occlusion of the cyclist by potential obstacles was not considered in figure 5. For values of FOVs lower than 40°, detection rates increased as the kinematic of the accident progresses. Indeed, the closer to the impact, the more cyclists enter the FOV as initially they were not detected. This trend concerns 40° FOV or lower. For value of FOVs higher than 40°, the detection rate increased and then decreased at a TTC of about 0.4s before the collision. The evolution of those curves could be explained by the kinematic progress of the accident with alternation between detected (in the FOV) and not detected phase (out of the FOV). Thus in some situations, where initially the cyclist was in the FOV, this may not be the case anymore when moving closer to the collision time (impact) as the cyclist may be at the vehicle side (outside the detection cone). This last trend concerns FOV values higher than 50°. Additionally, starting from FOV values of 50°, the gain became smaller and smaller when FOV increased. Detection rates went from about 15% for FOV 10° to approximately 90% for FOV of 70° 2s before the impact.

Except for curves that kept increasing, the maximal detection rate lay around a TTC of 0.4s with a little more than 90% of cyclists detected for FOV 70°.

Whatever the scenarios considered, some cyclists remained outside the detection field of view for the highest FOV value of 70°. It could correspond for example to situation where the cyclist collided the car on the side. Results evolved in a similar way for CN and CF, and for TL and TR scenarios. For CN and CF configurations, detection rates for FOV between 10° to 40° seem to be stable and increased from a TTC of 1s. For FOVs from 50° to 70°, the detection rate reached a maximum value of about 90% at a TTC of about 0.5s and decreased to the impact. At TTC 2s, an important gain could be noticed between each FOV with a gain reduction between FOV 60° and 70°.

From a general point of view, the additional gain was small from a FOV above 60°. For L scenario, the detection curves all decreased as the vehicle got closer to the cyclist. This evolution could be easily understood because of cyclist relative position to the car during the accident. If the cyclist was not in front of the car but on the side, the closer the cyclist was to the vehicle's sensor, the higher FOV was needed to detect the cyclist. This phenomenon is particularly visible for L scenario as initially cyclists were already detected. The decrease detection rate was more visible for smaller FOVs than for higher one. Different detection cones in each sub-figure of Annex A have been drawn to help visualizing the decreasing detection rates particularly visible for L scenario. Annex A sub-figures illustrate the results visible in Annex C sub-graphs. TL scenario reached the highest detection rate at 1s TTC while in TR, CN and CF scenarios the highest detection rate was observed at 0.2 TTC. Appendix C shows FOVs detection rates for each scenario.

For L scenario, the highest detection rate was about 80% and was reached between 2 and 1s TTC for FOVs higher than 40°. A decreased was observed from 0.4s TTC. This evolution was due to the scenario configuration as the kinematic progresses. When the cyclist was far away from the car, the cyclist was inside the detection cone in front of the car. When the distance between the car and the cyclist was reduced to a certain point, the cyclist left the field of detection. This was explained by the cyclist position when riding on the road. Indeed, cyclists rarely stayed in the middle of the road and mostly rode on the right side of the road. Thus, when getting closer to the car, cyclists "left" the detection field due to their position on the right side of the road.

Figure 5 shows also the detection rate according to the range (distance between car center and cyclist center). As expected, the higher the range was, the more cyclists could be detected earlier during the kinematic sequence. For detection range above 30m, more than 90% of cyclists could be detected 2s before the impact. This rate nearly reaches 100% if the range is 45m at TTC 2s. Thus 35m appears to be the appropriate detection range as the gain is small between 35 and 45m at TTC 2s and close to 100%. Table 2 shows the detection variation for some ranges at TTC 2s for the different scenarios. Cyclist detection rates are given according to the last time to brake criterion (tLTTB) in second for different FOVs. Each accident where the kinematic is known has a LTTB in meter. tLTTB is the time to travel from the LTTB position (computed using equation 1) to the impact location and corresponds to a duration. Thus, tLTTB gives the same information as the LTTB but instead of a distance in meters the information given is in seconds. From there, figure 6 left part shows the cumulative frequency of detected cyclists per FOV in function of the tLTTB. Little gain can be observed with tLTTB higher than 1s, i.e. more than 1 second before the collision. To be able to detect 50% of the cyclists at a tLTTB of 1s, a FOV of 30° would be needed. With a FOV of 60° at the same tLTTB of 1s, the detection rate is increased up to more than 80%. The higher slope for large value of FOVs shows that this parameter has an essential role when the last time to trigger brake is less than 1s before the collision (i.e. tLTTB < 1s). Additionally, the detection rates reach a maximum value of about 85%. It means that in about 15% cases, the cyclist is not detected when the vehicle is supposed to initiate a braking manoeuver. Figure 6 right part shows the results for the realistic braking model. It can be remark that, no tLTTB value can be found 0.1s before the impact due to the progressive rise of the deceleration value. The maximum detection rate per tLTTB is also affected and is a little lower compared to the ideal model. It is more visible for low FOV values and can be neglected for higher values. An ANOVA test with a 0.05 p-value has been performed in order to determine if a statistical difference appears compared to the ideal braking model. The results of the test can be summarized in table 3. No statistical difference is observed for FOV values 50° and higher per scenario and for all accidents. Also no difference can be observed for the L scenario whatever the FOV due to the trajectories of both car and cyclist. This way, the FOV is not affected even if tLTTB are shifted a little later compared to the ideal braking model. It can be highlight that for FOV values 40° and lower, some statistical difference can be observed. This phenomenon is due to the shift in the tLTTB value. The faraway the car is, the higher detection angle is required. This way, lower values of FOV are affected. Another remark that can be highlight is that even if "small" statistical difference is observed per scenario, these differences are cancelled for FOV higher than 40° when all scenarios are considered. As there is no statistical difference for FOV values higher than 40° for all accidents cases, the ideal braking model has been kept for the analysis in the next part. 3: results of the ANOVA test between the ideal and the realistic braking model Appendix D shows the detection rates at tLTTB for each scenario. Some cyclists are not detected at that critical moment which is the last time to react in order to avoid the accident. Similarities can be observed for CN and CF either for TL and TR. For tLTTB later than 1s for crossing scenarios, the detection gain is small whatever the FOVs whereas for turning scenarios, the gain is small for detection at a tLTTB later than 0.75s. Contrary to crossing and turning scenarios, detection rates keep increasing in L scenario which indicates that the tLTTB could go up to a value of 2.5s. An important point which can be noticed is that detection rates gain for value higher than 50° becomes smaller and smaller.

One important parameter is the available time for the device to detect, analyze and then trigger a FCW or an AEB. The available time for a system to react depends on the visibility of the VRU. Calculus must then take into account occlusion factor in order to assess correctly the available duration for system to collect data, analyze and react in real accident situations. Thus occlusion is taken into account here. Figure 7 shows the rate of detected cyclists per FOVs in function of a duration tvisible-tLTTB. tvisible-tLTTB is the duration from the 1 st time the cyclist is not occluded (tvisible) by the surrounding environment to the tLTTB. It can also indicate a late delay compared to tLTTB. Indeed, if tvisible-tLTTB<0 the cyclist is visible after the tLTTB so the accident could not be avoided by an emergency braking because a safety device (AEB or FCW) would trigger too late but could be perhaps mitigated. When tvisible-tLTTB>0, it signifies that the duration tvisible-tLTTB corresponds to the amount of time available from the first time the cyclist is not occluded to the tLTTB. This means that a safety device (AEB or FCW) will have tvisible-tLTTB time in seconds to trigger if the cyclist is inside the detection field. Each detection values in figure 7 thus indicate the cyclist cumulative detection rate for duration value equal to tvisible-tLTTB or more. For example, if we consider a detection rate for a value of tvisible-tLTTB of 2s, then the detection value corresponds to all cyclists that can be detected at least 2s before the tLTTB. For duration of tvisible-tLTTB of 4 seconds with a FOV 60°, about 51% of cyclists could be detected whereas only 16% could be detected for a FOV 10°. The closer tvisible is to tLTTB, the more cyclists could be detected whatever the FOVs. When tvisible is equal to tLTTB, i.e. for x-axis 0 in figure 7, detection rates reached nearly the maximum value for each curves with 80% detected for FOV 60° and 19% for FOV 10°. One could notice that the curves still slowly increased for negative duration, i.e. for tvisible<tLTTB. This means that there were cases where at the moment when the brakes should be triggered to avoid the collision, the cyclists were not inside sensors' detection field. It concerns only a very few percent of cases but it still indicated for those cases that only mitigation could be possible. Results per scenario had been extracted and had the same evolution as figure 7. Only for L scenarios, FOV variation has no effect on the detection rates due to the scenario configuration as all curves overlap.

Figure 7: Cumulative frequency of detection rates per FOVs in function of the visibility duration. The cyclist is seen (duration in seconds) before the tLTTB when X-axis value is positive whereas when X-axis is negative the cyclist is seen too late after tLTTB.

Discussion

This research aims at understanding and determining the characteristics of accidents prior to collision. To that end, an analysis of 2261 accident cases was performed. Crash scenario reconstructions greatly rely on available data gathered by in-depth investigation teams and on the accuracy of the reconstructions.

A detection estimation of such device is realized through computational calculation of crash scenarios. During those simulations, there is no consideration of weather or illumination conditions which can affect the detection. The detection rates do not take into account the dynamic surrounding of the accident scene to determine global FOV and range characteristics. The changeover between visible, hidden, visible VRU greatly depends on the traffics environment and is rarely known before or at the time of the collision. Thus, detection rates presented in this study are optimistic results. Additionally, some reasonable assumptions are done, as the value of deceleration coefficient applied to determine the LTTB, sensor's position or the brake trigger during the original accident kinematic reconstructions. From a general point of view, the detection rate never reaches 100% since some cyclists can never be detected because they remain outside the detection field even at the moment of the accident leading to a lateral collision. In regard to parameters considered for an ADAS device, only braking manoeuvers were considered. Steering manoeuvers are not considered since this manoeuver needs to take into account many others factors such as traffic situation, opportunity to make this evasive manoeuver [START_REF] Hayashi | Autonomous collision avoidance system by combined control of steering and braking using geometrically optimized vehicular trajectory[END_REF]. [START_REF] Hamdane | Issues and challenges for pedestrian active safety systems based on real world accidents[END_REF] analyzed parameters for an AEB for pedestrian based on real accidents and determined that a FOV of 35° was optimum for pedestrians' detection. Additionally, he shows that the needed AEB trigger time has a great influence on the avoidance rate. Indeed, this rate decreased from more than 80% if the AEB trigger is immediate (0s is needed to trigger the AEB) to 75% (respectively 64%) if the AEB needs 0.5s trigger time (resp. 1s). [START_REF] Welsh | Time-to-collision analysis of pedestrian and pedal-cycle accidents for the development of autonomous emergency braking systems[END_REF] also analyzed parameters for an AEB applied to a British sample of 175 pedestrians and 127 cyclists' cases. Their study showed that with the same FOV definition as the one in this study, an AEB system with a FOV of 80° is enough to detect 90% of cyclists and 20° for pedestrians. Similarly to Lenard et al. study, this research also shows that higher FOVs allow detecting more cyclists. Detection rate values may be of interest for car manufacturers for FOV values higher than 50° for cyclist safety as there is still a detection gain even if it is smaller and smaller. As an AEB should trigger at TTC 1s, a 20m range is sufficient whereas 35m is needed for a FCW trigger at TTC 2s. Thus it appears that a range of 35m appears to be sufficient to nearly detect all cyclists about 2 seconds before the collision. Independent analysis can be performed on range and FOV as during the kinematic, the closer to the collision time, the closer the cyclist are. The range parameter does not influence the detection rates which mostly rely on the FOV. Last but not least, this study gives a first insight of the optimist detection rate a device could achieve before the last moment to trigger brakes. The sample used in this paper is not representative of national accident proportion and is a limitation of this work. Application of weighting factors could allow being representative. Values given are thus indicative of potential detection rates. For a FOV of 60°, about 51% of cyclists can already been detected at least 4s before the tLTTB whereas this rate reaches 72% if the cyclist is detected at least 1s before tLTTB. For a FOV of 40°, the rate reaches 40% and 54% if the cyclist is detected respectively at least 4s or 1s before tLTTB. Those rates could correspond to the amount of accidents that could be potentially avoided. Similar effectiveness value can be found in [START_REF] Ohlin | The combined effect of vehicle frontal design, speed reduction, autonomous emergency braking and helmet use in reducing real life bicycle injuries[END_REF]. They estimated on Swedish data that 70% effectiveness can be obtained for pedestrians and cyclists through the combination of different measures and AEB technology. [START_REF] Rosén | Autonomous Emergency Braking for Vulnerable Road Users[END_REF] worked on AEB effectiveness on GIDAS PCM data. His analysis on 607 accidents revealed that depending on the AEB systems parameters, AEB could be effective on 55% fatal cases and 33% severe injured cases. To be comparable to Rosén work, results in this study have to be adapted to the injury criteria but it shows the potential of such ADAS for cyclist safety. Compared to an AEB, the FCW design has to be taken into account more carefully as another component has to be included: driver's reaction.

In the case of a FCW, results found in this paper can give an indication of the time where the warning can be delivered to driver with consideration of his time reaction. It can also give an indication of the time available for an AEB system to reach full efficiency with consideration of the transient state. The choice of the ADAS trigger timing becomes a crucial parameter due to driver reaction time for the case of a warning device like a Forward Collision Warning. Depending on many criteria like the driving environment and the state of mind of the driver, the driver reaction to a signal can therefore vary as shown in the review of Young and Staton (2007). [START_REF] Warshawsky-Livne | Effects of uncertainty, transmission type, driver age and gender on brake reaction and movement time[END_REF] showed that the brake reaction time of a driver is increased by uncertainty and age. Thus, the perception-reaction time which is the time from the perception of a signal to the first movement of foot on the accelerator is increased from 0.35 to 0.43s with age. Also depending on the driving environment situation, [START_REF] Abe | The influence of alarm timing on braking response and driver trust in low speed driving[END_REF] showed that the braking reaction time can be affected with consideration to an alarm warning timing for a relatively low driving speed. In a situation where a leading vehicle decelerates rapidly, brake response time can be reduced compared to the situations where no alarms are given. Indeed, the mean duration from a leading vehicle braking event to the application of the brake of the participants' vehicle goes from 0.88 to 1.11s depending on the trigger of the alarm and the leading vehicle deceleration. Thus, in this paper, if drivers react in a similar way as those in Abe and Richardson, a FCW should trigger at about a tvisible-tLTTB of about 1s in order for drivers to be able to avoid the accident. Under the condition of Abe and Richardson for example, with a FOV of 60°, 72% of the cyclist accidents could be avoided using a FCW.

Conclusion

Field of detection, range of detection and available time before the tLTTB are keys parameters for car active safety device to reduce the number of cyclist accidents. Through the analysis of 2261 accidents cases (30 from French EDA, 2231 from German GIDAS-PCM) involving one passenger car and one cyclist, reconstructions provide information relative to the accident configurations like trajectories of the vehicle and the cyclist, travelling speed, position in time and space. From this analysis, more than 50% accident cases concern a crossing situation (nearside and farside combined). The FOV and the available time before the tLTTB appear to be the critical parameters to detect the cyclist. Similarly to pedestrian accidentology, the most critical period remains between 0 to 1s before the collision as the cyclist is close or in car's path. Some critical parameters for ADAS were analyzed: the FOV, the range and the tLTTB. A FOV of 60° allows detecting about 80% of cyclists at a tLTTB of 1s. If driver reaction time is considered to be equal to 1s and if a FCW can be triggered 1s before the tLTTB with a FOV 60°, about 72% accident cases could potentially be avoided. A range of 35m appears to be sufficient to nearly detect all cyclists 2s before the collision.

Even if results are optimistic, this study gives indications about the characteristics that active safety device for cyclist ADAS should have. It also gives information of the characteristic ADAS should have if equipped with adaptive sensors. Further work will focus on the FCW effect estimation on cyclist accident.

  Figure 1 illustrates the representation of the FOV and the range of detection of the sensor: -A FOV value Θ corresponded to half of the detection field formed by half straight line [Ox) and [OM). Thus a FOV of 20° corresponded to a total detection field of 40°. If the center of gravity of the cyclist was inside the detection field without consideration of the distance (infinite detection range inside the cone), then the cyclist was considered as detected.

Figure 1 :

 1 Figure 1: FOV and range sensors modeling

Figure 2 :

 2 Figure 2: Description and proportion of the 4 main crash scenarios

Figure 4 :

 4 Figure 4 : Cumulative frequency of brake activation timing (all car-to-cyclist accidents, N=2261, 33% of all cases).

Figure 5 :

 5 Figure 5: Rate of visible cyclists at different TTC for different FOVs (Left) and ranges (Right)

Figure 6 :

 6 Figure 6: Cyclist cumulative detection rates in function of tLTTB for different FOVs with ideal braking model (left) and realistic braking model (right)

Table 1

 1

	Scenario	CN	CF	L	TL	TR
	Brake activation percentage (%) 28.9	37.7	33.3	34.6	31.9
	Total cases in the scenario	744	504	120	280	492

indicates the percentage of brake activation per scenario. The rate reached a minimum of 28.9% for CN up to 37.7% for CF.

Table 1 :

 1 Brake activation percentage per scenario.

Table 2 :

 2 Detection rates per ranges for each scenario.

	TTC 2s	CN	CF	L	TR	TL
	15m	47%	37%	55%	60%	22%
	35m	98%	99%	95%	100%	92%

Acknowledgement

The authors thank Toyota Motor Europe for accessing GIDAS-PCM database and their collaboration to this research.

Funding: This work was supported by Toyota Motor Europe.


Mario D'acunto
email: mario.dacunto@cnr.it

Davide Moroni
email: davide.moroni@cnr.it

Alessandro Puntoni
email: alessandro.puntoni@cnr.it

Ovidio Salvetti
email: ovidio.salvetti@isti.cnr.it

Optimized Dislocation of Mobile Sensor Networks on Large Marine Environments Using Voronoi Partitions

Keywords: Voronoi partition, mobile sensor networks, wireless sensor networks, environmental monitoring, marine environment, oil spills

Introduction

A growing number of applications, such as spatial distribution mapping, dynamic sensors coverage, and environmental extensive area monitoring, have motivated the development of both sensing hardware and algorithms for target-oriented mobile sensor networks [START_REF] Ruiz-Garcia | A review of wireless sensor technologies and applications in agriculture and food industry: state of the art and current trends[END_REF][START_REF] Dargie | Fundamentals Of Wireless Sensor Networks: Theory And Practice[END_REF]. Any such application requires ad hoc customization of hardware and software solutions. Large area monitoring, for example, presents the main problem for biasing certain regions of interest. Indeed, some parts might be prioritized based on prior knowledge and due to an inherent time-constraint that prohibits an exhaustive search of the area; for instance, in the case of emergencies and search and rescue operations. This situation is met during the oil spill monitoring of large marine regions, and in general, in all pollution events involving diffusion [START_REF] Jarnelov | How to defend against future oil spills[END_REF]. The most probable scenario is that areas in which human beings, pollution activities, or hazardous materials are likely to be present should be searched first, while regions with less probability of containing these features are searched later. Consequently, both inferential statistical methods and mobile sensor networks able to navigate from an initial configuration within a region containing shaped obstacles were developed [START_REF] Li | Navigation protocols in sensor networks[END_REF]. In this paper, we focus the attention on coordination algorithms to improve the capability of mobile sensors networks in covering and monitoring relevant portions of larger areas. Our proposed solution to this problem is obtained using centroidal Voronoi partitions.

The centroidal Voronoi partition is a widely used scheme of portioning a given space, and finds applications in many fields, such as image processing, sensor coverage, crystallography, and CAD [START_REF] Cheddad | Exploiting Voronoi diagram properties in face segmentation and feature extraction[END_REF][START_REF] Kalra | Incremental reconstruction of generalized Voronoi diagrams on grids[END_REF][START_REF] Krishnamurthy | Representation of properties of materials by Voronoi polyhedral[END_REF][START_REF] Papadopoulou | Critical area computation via Voronoi diagrams[END_REF]. The basic components of a Voronoi partition are: (i) A space, which is to be partitioned; (ii) A set of sites, or nodes or generators; (iii) A distance measure, such as the Euclidean distance.

In the case of homogeneous sensors with a typical circular sensing area, the sensor located in a Voronoi cell Vi is closest to all the points q  Vi, and hence, by the strictly decreasing variation of sensors effectiveness with distance, the sensor is most effective within Vi, provided the circular area covered by the sensor does not cover the entire cell. Thus, the Voronoi decomposition leads to optimal partitioning of the space, in the sense that each sensor is most effective within its corresponding Voronoi cell. In the heterogeneous case too, it is easy to see that each sensor is most effective in its own generalized Voronoi cell. Since the partitioning is optimal, it is necessary to find the location of each sensor within its generalized Voronoi cell. Voronoi-based approaches have been used in the recent past for optimizing the coverage of mobile sensor networks. For instance, in [START_REF] Mahboubi | Distributed deployment algorithms for improved coverage in a network of wireless mobile sensors[END_REF], the Maxmin-vertex and Maxmin-edge algorithms are proposed to maximize the minimum distance of every sensor form the vertices and edges respectively of its Voronoi cells. In [START_REF] Mahboubi | Toward autonomous mobile sensor networks technology[END_REF], such results are improved by also taking into consideration the adaptive ranges of sensors based on their respective residual energy. In [START_REF] Wang | Bidding protocols for deploying mobile sensors[END_REF], the authors proposed to consider a heterogeneous network made of both static and mobile sensors, and a bidding protocol for the placement of the mobile ones is proposed. Intuitively, mobile sensors are treated as servers to heal possible coverage holes left by the network as a whole. In this framework, optimization is also achieved through the distributed calculation of the Voronoi partition. With respect to these previous works that have shown the powerfulness of the Voronoi-based approaches in coverage improvement, in this paper, a further element is considered which is of relevance when dealing with environmental monitoring; i.e., adaptive prioritizing of areas to be monitored.

In the specific case of marine monitoring, adaptability is necessary to deal with (i) changing conditions in maritime traffic, weather and currents, and (ii) available knowledge of pollution events that have already taken place. This variable information should be put in relation to the variable impacts that events can have on different areas; e.g., due to the existence of marine parks, the presence of endangered animal species and proximity to shores.

Indeed, spills of oil and related petroleum products in marine environments can have a severe biological and economic impact [START_REF] Eide | Intelligent ship traffic monitoring for oil spill prevention: Risk based decision support buildings on AIS[END_REF][START_REF] Cocco | Information Technology Ocean Engineering[END_REF]. With modern remote sensing instrumentation, such pollution events can be monitored on the open ocean around the clock. The monitoring of large marine areas generally involves complex marine information systems [START_REF] Moroni | A proactive system for maritime environment monitoring[END_REF], which act as catalysts to integrate data from multiple and disparate data sources. Each source provides a specific piece of information, and through a suitable fusion and correlation process, they offer as a whole, a comprehensive characterization of the status of a marine area in terms of pollution events, maritime traffic, weather, and oceanic currents. In this process, key sources are SAR and optical satellite imaging to discover and quantify both oil slicks and real vessel traffic; the Automatic Identification System (AIS) for real-time identification and trajectory analysis of vessels passing through an area; and airborne hyperspectral sensors for detection and precise characterization of oil spills.

Sensorized buoys and surface and underwater vehicles can also be used to enforce remote monitoring. Indeed, autonomous underwater vehicles (AUVs) and mobile buoys equipped with different sensor devices are excellent candidates for real-time monitoring of oil spills through areas where the pollution events can take place. A new generation of buoys dedicated to oil spill monitoring is becoming available in a prototypal shape [START_REF] Moroni | Sensorized buoy for oil spill early detection[END_REF] or in their commercial evolution. Other interesting sources of information are based on crowd-sensing methodologies [START_REF] Martinelli | Volunteered geographic information for enhanced marine environment monitoring[END_REF].

Environmental decision support systems (EDSS) are employed to orchestrate and make optimal and sustainable use of available monitoring and interventional resources. According to the survey [START_REF] Moroni | Environmental Decision Support Systems for Monitoring Small Scale Oil Spills: Existing Solutions, Best Practices and Current Challenges[END_REF], routine goals are (i) to actuate policies for confirming partial observations obtained by one source by collecting further information and (ii) to prioritize monitoring according to an adaptive risk map. For instance, if a slick is detected by remote sensing, in situ sensors such as buoys or AUVs can be deployed to assess its presence. Additionally, marine currents and weather conditions can increase the impact and the area affected by the possible pollution events.

The results presented in this paper were obtained having in mind (but are not limited to) the monitoring of large marine areas where oil spill events can take place, and where the diffusion evolution of any oil slick is known a priori. In addition, we consider marine sensors equipped with sensing hardware to consist mainly of an electronic nose, a bathymetric sensor, a GPS device, an anemometer, a motor for self-dislocation depending on a pollution event, and a complete communication set up with a remote station.

Actually, our simulation considers minor influences of weather and low marine waves, and low velocity for pollution event drift, so that the diffusion dynamics can be considered slow with respect to the sensor network's self-dislocation, which can be considered fast. The pollution events have been considered uncorrelated and were simulated with a Poisson distribution. Similar results were obtained with non-Poisson distributions.

The results show the capacity and the limits of event-dependent real-time monitoring of a sensor network. One of the limiting aspects is due to the real hardware facilities, especially for what regards real-time communication between the sensors and a remote station. The communication set up as considered in this paper is rather idealized; nevertheless, it is in line with the recent communication capabilities that will be available on sensorized devices for real-time monitoring of large marine areas.

The paper is organized as follows. In Section 2, we introduce the modeling of pollution events using a Poisson distribution and describe the Voronoi tessellation arising from a number of geolocalized events. In Section 3, details about Voronoi partitions, both classical and generalized, are given. In Section 4, we introduce an objective function to be maximized for optimal monitoring of an area subject to a static risk of pollution events. In this scenario, mobile sensors should follow a certain physical velocity field to move from their initial configurations to the optimal one. In Section 5, we assume that the risk of pollution changes over time in response to external events, diffusion and weathering; in this scenario, an iterative algorithm is proposed for letting the sensor network dislocate itself in an optimal way. Further, experimental simulations are described. Finally, in Section 6 we derive our conclusions.

The main contributions of the paper can be summarized as follows:

-A solution for the optimal displacement of a sensor network is proposed for the monitoring of large areas. The solution is based on formalized geometrical methods using Voronoi centroidal tessellation.

-

The proposed solution is fitted into an iterative algorithm, which can evolve in real-time and continuously, the displacement of the network in response to dynamic events and changes in risk.

-

The results are proven theoretically and with numerical simulations.

Modeling of Pollution Events

The first approach for monitoring a large area is given by the regular and symmetric dislocation of the sensors. Nevertheless, this approach is not practicable if the number of sensors with a finite radius of sensing power is not enough to cover the large area to be monitored. In addition, we have to consider the dislocation as event-dependent; i.e., considering the possible pollution source. An unwanted event is a random variable. Therefore, the immediate suggestion for a suitable event-dependent dislocation of a number of sensor networks is given by the Voronoi tessellations. A great number of natural phenomena are described by Voronoi tessellations; in this section, we try to respond to the main question: why should the optimal dislocations in a large area of a network composed by sensors with circular sensing power follow a centroidal Voronoi tessellation? To give an answer to this question, the starting point is to introduce the probability density function (PDF) for the occurrence of a pollution event, x. The reasonable shape of a PDF for a stochastic event is a Poisson distribution:

    H x λexp -λx dx  (1)
where λ is the hazard rate of the exponential distribution. Let us consider the sum of two uncorrelated events, y, the variable change, y = 2x, and x = 1/λ. The PDF (Equation ( 1)) can be written as:

      H x 2xexp -2x d 2x  (2)
The result in Equation ( 2) can be written using a gamma variate distribution [START_REF] Zaninetti | Poissonian and non-Poissonian Voronoi Diagrams with applications to the aggregations of molecules[END_REF][START_REF] Zachary | The Inverse Poisson Functional for forecasting response time to environmental events and global climate change[END_REF] as a function of the space dimension d; in our case d = 2.

        2d-1 2d H x;d 2dx exp -2dx Γ 2d  (3)
where, now, 0  x < , and (2d) is the gamma function with argument 2d. That PDF (Equation ( 3)) has a mean of μ = 1 and variance σ 2 = 1/d. The gamma PDF can be generalized by introducing new additional parameters that take into account the complexity of the real situation, pollution sources, environmental weather, etc. In this paper, we restrict ourselves to gamma PDF as in Equation ( 3). Figure 1 shows the distribution as given by Equation ( 3) of pair events distance; i.e., the distance between two events close one each other. Let us consider n pollution events, distributed randomly in a square area. The monitoring of such diffusion processes can be made considering the equivalent Voronoi diagram, where the vertexes are coincident with the pollution events coordinates (see Figure 2). Similar results are obtained when the events are located using a Gaussian distribution. This is the case of pollution events with a correlation, anywhere the result does not present a significant difference. The correspondent Voronoi diagram is built considering the pollution events located at the nodes.

Basic Properties for a Voronoi Partition

A standard Voronoi partition can be introduced as follows: A collection {Wi}, i  {1,2,…,N} of subsets of a space X with disjoint interiors is said to be a partition of X if iWi = X. Let Q   d be a convex polytope in d-dimensional Euclidean space. Let P = {p1, p2, …, pN}, pi  Q be the set of nodes of generators in Q. The Voronoi partition generated by P with respect to the Euclidean norm is the collection {Vi(P)}, i  {1, 2, …, N}, and is defined as:

    i i j j V P q Q q p q p , p P        (4)
where    denotes the Euclidean norm. The Voronoi cell Vi is the collection of those points that are closest (with respect to the Euclidean metric) to pi compared to any other point in P. In  2 , the boundary of each bounded Voronoi cell is the union of a finite number of line segments forming a closed °C curve. For example, the intersection of any two Voronoi cells can be null, a line segment, or a point. In d-dimensional space, the boundaries of the Voronoi cells are unions of convex subsets of at most d-1 dimensional hyperplanes in  d , and the intersection of two Voronoi cells can be a convex subset of a hyperplane or a null set. Each of the Voronoi cells is a topologically connected non-null set. Generalizations of the above Voronoi basic partition to suit specific applications can be found in the literature [START_REF] Eide | Intelligent ship traffic monitoring for oil spill prevention: Risk based decision support buildings on AIS[END_REF][START_REF] Cocco | Information Technology Ocean Engineering[END_REF]. A possible generalization of the Voronoi partition can be introduced considering a space Q   d , sand et of points called nodes or generators P = {p1, p2, …, pN}, pi  Q, with pi  pj, whenever i  j, and monotonically decreasing analytic functions fi:  +  , where fi is called a node function for the i-th node. It is possible to define a collection {Vi}, i  {1, 2,…,N}, with mutually disjoint interiors, such that Q = iVi, where Vi is now defined as:

          i i i i j V P q Q f p q f p q , j i, j 1, 2,..., N         (5)
We call {Vi}, i  {1, 2, …, N} a generalized Voronoi partition of Q with nodes P and node functions fi. In this application, it should be noted that Vi can be topologically non-connected and may contain Voronoi cells. In addition, it should be noted that q  Vi means that the i-th sensor is the most effective in sensing at point q. In a standard Voronoi partition used in a homogeneous case, the  sign for distances ensures that i-th sensor is most effective in Vi. Finally, the condition that fi is analytic implies that for every i, j  {1, 2,…, N}, fi-fj is analytic. By the properties of a real analytic function, it derives that the set of intersection points between any two-node functions is a set of measure zero. This ensures that the intersection of any two cells is a set of measure zero; that is, the boundary of a cell is a set is made up of the union of at most d-1 dimensional subsets of  d ; otherwise, the requirements that the cells should have mutually disjoint interiors may be violated. The analyticity of the node functions {fi} is a sufficient condition to avoid this possibility.

Optimization in the Localization of Event-Dependent Mobile Sensors Network

In this Section, a solution to optimal monitoring of an area by means of mobile sensors with limited radial sensing ranges is proposed. Such sensors can either be mounted on buoys with motion capabilities or full-fledged AUVs or unmanned surface vehicles (USVs). As stated in the introduction, it is assumed that sensors can navigate quite fast with respect to the evolution of a pollution event by diffusion, marine currents, and weathering.

Let us consider a large area to be monitored by N sensors; the cost of real-time monitoring is rather high. Unwanted events to be monitored trigger a sensor network to navigate from an initial configuration towards a specific region within the large area where the probability of encountering unwanted events is higher.

Let Q   d be a convex polytope, the space in which the sensors have to be deployed, and Vi  Q be the generalized Voronoi cell corresponding to the i-th node; we introduce a continuous density distribution function φ: Q  [0,1], where the density φ(q) is the probability of an event of interest occurring in q  Q, and P = {p1, p2, …, pN}, pi  Q is the configuration of N sensors [START_REF] Guruprasad | Automated Multi-Agent Search Using Centroidal Voronoi Configuration[END_REF].

It is well known that the generalized Voronoi decomposition splits the objective function into a sum of contributions from each generalized Voronoi cell. As a consequence, the optimization problem can be solved in a spatially distributed manner; i.e., each sensor solving the part of objective function corresponding to its cell using only local information can achieve the optimal configuration.

Besides, another essential characteristic of the sensor network, as considered in this paper, is that any sensor possesses a limited range of action; with the sensing capability that decreases as a logarithm of the distance from the centroid. This limitation must be taken in due consideration. Let Ri be the limit on the range of the sensors and f (pi, Ri) be a closed disk centered at pi with a radius Ri. The i-th sensor has access to information only from points in the set Vi  f (pi, Ri).

Let us consider the following objective function to be maximized:

        i i i i i V f p ,R H P f q p φ q dQ i      (6)
where || . || is the Euclidean distance and fi = 0 if ||q-pi|| > Ri. It is possible to define the derivative of H (P) as follows.

      j i V j i i f q p H P φ q dQ p p i                 (7)
In addition, it is possible to introduce the critical points defined as the points mass and the centroid of the Vi cells.

              j j i j i j i i 2 V V i i i V i i i f q p f r H P φ q dQ p q φ q dQ p p r M p -p j j                               (8)
where i p is the set of centroids where the mobile sensors must be dislocated, defined later. The centroids set has the property i p Q because Q is an invariant set for Equation [START_REF] Papadopoulou | Critical area computation via Voronoi diagrams[END_REF], while on the contrary, it is not guaranteed that i p Vi. The dynamical properties of the mobile sensors network to be dislocated in an optimal configuration make it possible to write the basic control law as

  i i i p k p p     (9)
where the single mobile sensor moves toward i p for k > 0. Using the properties of the gradient with respect to pi as in Equation ( 8), we can write

        i i i i i i i V f p ,R f p ,R i H P M p p p i        (10)
One main problem for the optimal dislocation of the mobile sensors is the convergence to the ideal centroid locations when a pollution event must be monitored. In this case, the uncovered area could generate more difficulties in producing a real convergence, but this problem can be dropped using effective k parameters in Equation [START_REF] Mahboubi | Distributed deployment algorithms for improved coverage in a network of wireless mobile sensors[END_REF]. The problem of an effective convergence of a common radius sensor network that is unable to cover a large area is very close to that of the class of heterogeneous sensor networks [START_REF] Guruprasad | Automated Multi-Agent Search Using Centroidal Voronoi Configuration[END_REF]. In our case, the effective k parameter implies that the mobile sensors have higher dislocating speed with respect to the evolution velocity of a pollution event. The pollution event, for example, an oil spill, modifies its shape on the marine surface due to weather conditions: if the event time-scale, τ, is τ < <1/k, then it is reasonable to expect a fast convergence to the optimal centroids. The control law, Equation ( 9), drives the sensors towards their optimal configurations that correspond to the arrangement that guarantees the maximum sensing power at the lowest cost. This is because the closed-loop system for the sensors networks is modeled using a first-order dynamical system that is globally asymptotically stable for an effective choice of k parameters; this is translated in the time property of H (P), which we supposed to be continuous.

          i i i i i 2 i i i V f p ,R f p ,R i dH P H P 2 α M p p dt p i i i p           (11)
The Equation [START_REF] Wang | Bidding protocols for deploying mobile sensors[END_REF] assures that the initial configurations of localized sensors converge to the optimal centroids i p .

One special problem is the ability of the sensors network to relocate themselves as a function of a pollution event (for example, an oil spill) whose shape changes in time due to diffusion and weathering. If the velocity of the sensor network is faster than the characteristic oil slick time diffusion, the sensing power of the sensors network is hugely enforced. Suppose a diffusion process evolves in the convex polytope space Q: Q  2, where  (x, y): Q  + can be used to represent the pollutant concentration over Q, where the dynamic process is modeled by a partial differential equation (PDE). The possibility to reorganize the sensors, relocating them to enforce their sensing power, is generally energy consuming; for this reason, the control law for the converge of the sensors toward their final centroids location must be constrained to the sensing power, which in this work we consider as Esensing (ri) = ari, for ri < Ri and Esensing (ri) = 0 otherwise, where a is constant and i is referred to the i-th sensor.

If the pollution event velocity in a given direction is vevent; then the control law ( 9) must be written as

    i i i i i i i i p p α if p p μ p p p α p p /μ otherwise i               ( 12
)
where α = vsensor/vevent is a parameter denoting how much faster the mobile sensor must be with respect to pollution velocity vevent; μ is a positive defined value taking into account the distance from the centroids to which converge. The control law (Equation ( 12)) makes the sensors move toward their respective centroids with a constant speed vsensor when they are at a distance further than μ from the corresponding centroids and slow down as they approach them. The control law (Equation ( 12)) is calculated at regular steps using new centroids i p as a function of the event. Suppose that at time t = 0, a pollution event is located at x0, y0: the initial shape 0 is a point. Under the effects of environmental parameters,  changes with time, and then at regular time steps, the centroids set is recalculated and the re-dislocation of mobile sensors occurs, consequently, until the highest sensing activity is made when two centroids set are coincident during two subsequent time steps checks.

Let us consider now, the possibility of a dislocation of the sensors network from an initial set of centroids to a new set of centroids when an unwanted event must be taken into consideration. When the time evolution of pollutant concentration  (x, y, t) is known, it is possible to calculate masses and centroids on region Vi at regular time steps as

  i i V i V M ρ q p dq    and     i i i V i i V qρ q p dq p ρ q p dq      (13)
The masses and centroids are recalculated using a sampling time, generally a fraction of α using an algorithm very close to Lloyd Centroidal algorithm [START_REF] Chao | Consensus of Information in Distributed Control of a Diffusion Process using Centroidal Voronoi Tessellations[END_REF][START_REF] Chao | Cooperative Sensing and Distributed Control of a Diffusion Process Using Centroidal Voronoi Tessellations[END_REF][START_REF] Cortes | Coverage control for mobile sensing networks[END_REF][START_REF] Du | Convergence of the Lloyd algorithm for computing centroidal Voronoi tessellations[END_REF] applied to sensors with a limited sensing radius, as in Figure 3. When possible, the dynamical changes of (|q-pi|,t) are usually modeled by a partial differential equation [START_REF] Cocco | Information Technology Ocean Engineering[END_REF]. Because in many real situations the shape of (|q-pi|,t) is unknown, we advance the idea that (|q-pi|,t) could be substituted by a Poisson distribution of random events, so that (|q-pi|,t) can occur in one point, as described by Figure 2, and evolve with low dynamics. In this manner, the n sensors can dislocate themselves to develop higher sensing power, thereby neutralizing the pollution as quickly as possible without making the area of interest overdosed.

Numerical Results and Discussion

Our method is based on the assumption that the occurrence of a random pollution event is an element of a more general class of events that follows a Poisson distribution, as described in Figures 123. The sensors' capability can be considered more effective if they can be located in a general configuration, where the pollution event occupies one site, and the sensors the other ones. Figure 3 represents both the Voronoi diagram and the corresponding power sensing using sensors with limited sensing radii. As the pollution event, described by (|q-pi|,t), changes due to environmental conditions, the sensors must be re-dislocated on the positions coinciding with the centroids calculated using Equation [START_REF] Cocco | Information Technology Ocean Engineering[END_REF]. Because the shape of (|q-pi|,t) is generally unknown, we can hypothesize that at regular time steps, the new location of (|q-pi|,t) is on a position still described by the same Poisson distribution, that in our model represents a primitive partitions of space, which the Voronoi diagram represents the most effective operability of the sensors networks (Figure 3).

The new algorithm proposed for the control made by a mobile sensors network of a pollutant event occurring in a large environment can be described as follows:

(1) Initial setting of the sensors pi  {p1, …, pn}; response time t = 0, coincident with a Poisson distribution of locations. (2) Computation of the Voronoi region Vi. All the sensors denoted by a standard limit range radius are defined as Ri = A 1/2 /(n + m), where A = [0,1]  [0,1] is the area to be monitored, n is the number of sensors, and m is an entire number taking into account the range of the uncontrolled area. (3) A pollution event takes place at time t = 0, located at a point as described by a Poisson distribution and the diffusion process described by (x, y, t); or equivalently (|q-pi|,t), changes slowly. (4) Computation of centroid set i p using Equation ( 13).

(5) Mobile sensor networks move towards pollution location with a velocity described by α, considering the closer sensors located in the direction of less pollution shape variation using the control law (Equation ( 12)). ( 6) Iterative computations of new centroid sets i j p  are made at regular times j, j < i. At any new estimate, the sensor nearest the slick is fixed and all the other sensors are moved following the new centroids set. [START_REF] Krishnamurthy | Representation of properties of materials by Voronoi polyhedral[END_REF] The optimal final configuration embedding the diffusion pollution event is reached.

The numerical results were obtained using a node function coinciding with power sensing as

    2 i i i f r R r  
for r < Ri, and   i i f r 0  ; otherwise, at any time step when the centroids set is recalculated, all the sensors are denoted by a common limit range radius defined as Ri = A 1/2 /(n + m), where n is the number of sensors and m is an entire number taking in account the uncontrolled area. For example, in Figure 3, we have considered n = 20 sensors distributed following the PDF (3), with m = 1. m being strictly connected to different hardware power sensing, running service, and environmental conditions, other than aging. It can be expressed by the empirical relation:

2 vor diff ω l m d   ( 14
)
where ω is rate of possible pollution event due to ship traffic; for example, ddiff is a diffusion coefficient and describes the mobility of the sensor. 2 vor l denotes the averaged Voronoi cells' area.

The darker areas denote the areas monitored by the sensor network and the brighter regions the portion that is not effectively covered by the sensor monitoring. It is evident that while increasing the number of sensors, the area monitored increases, but this involves significant costs, reducing the benefits due to mobile sensors.

In many real applications, the area to be monitored is more extensive with respect to sensor network power sensing, m > >n. This leads to an initial dislocation that we can consider blind, because in our polytope space, Q   2 , we suppose the equiprobability for the occurrence of a pollution event. For example, in Figure 4 is shown a linear dislocation of seven sensors with a limited sensing radius (gray circles). We want to cover the maximum area with the lowest number of wireless sensors moving in a large area. The general characteristics of the mobility for the wireless sensors should meet this general requirement; nevertheless, large portions of the unchecked areas must be taken into consideration. When a pollution event takes place, the sensors move in the direction of the pollutant slick, redislocating themselves in a Voronoi set centroid given by the knowledge of some environmental information. The environment changes the shape of the slick, expressed by (|q-pi|,t), making it asymmetrical; consequently, the new dislocation implies that the new centroids overlap the individual sensing radii; i.e., Ri -Rj < R, with i, j = 1…n, enforcing their power sensing in one direction rather than another one. The first step is a fast dislocation of a single sensor; for example, the sensor nearest to the pollution event. The control law (Equation ( 12)) is integrated calculating the centroids i p at regular steps, once a pollution event has been located. The convergence is guaranteed by choosing an effective α parameter as  10 and time steps for the calculation of the new centroids set proportional to α/5.

In Figure 5 the main results of our procedure are represented. The blind dislocation is changed as a function of pollutions events. In our case, we limited ourselves to a single pollution event moving but unchanging shape. The two localizations and the correspondent dislocations of sensor networks are displayed in Figure 4A and zoomed-in in Figure 5B. In a first approach, the blind dislocation is changed considering that the pollution event is localized at a point described by a Poisson distribution, where the pollution event and the other ones by the sensors occupy one site, following the Voronoi tessellation. The sensor nearest to the pollution event is locked and the other sensors are moved to be collocated at the positions identified by the centroids set calculated with the Equation [START_REF] Cocco | Information Technology Ocean Engineering[END_REF]. As the slick moves, the configuration of the sensor network is defined by the new centroids set, where at any new calculation, the nearest sensors are locked. The final result is reached when the sensing power is maximal. The sensing power is defined by the functions

    2 i i f r R r i  
for r < Ri, and 5B, the final configuration is obtained by the five sensors forming a pentagon; the blue point denotes the sensors that in the preview centroids set were locked because of being nearest to the slick. The results in Figure 5 were obtained taking the parameter α = 10; i.e., the sensor velocity has been taken to be ten times the slick velocity, a slow diffusion regime. This guarantees the fast converge to the centroids set without complicating the configuration due to the slick shift during the sensor dislocation. It is evident that the parameter α includes the main characteristics of the diffusion process. Fast dynamics of the slick, with fast changes of position and shape of the slick, would be useless without our algorithm. All the numerical results were obtained by writing an original Matlab program. The presented results are rather general and they can be applied to many real situations when a priori knowledge of the environments to be monitored is unavailable. If a priori knowledge on where a pollution event can take place and the diffusion process, expressed by (|q-pi|,t), is not available, the initial configuration of the sensors can be well simulated using the Poisson distribution of the random events for the centroids set. In such situations of real uncertainty, some improvements for our algorithm can be made conjugating the centroidal Voronoi tessellations with an inferential approach, but this is beyond the scope of the present paper.

  i i f r 0  otherwise. In Figure

Conclusions

The real-time surveillance of large areas requires the ability to dislocate sensor networks. Generally, the probability of the occurrence of a diffusion-based pollutant event depends on the burden of possible pollution sources and the spreading of pollution with time. This represents a challenge for devising real-time dislocation of the sensor network.

In this paper, we have presented the oretical and simulated results inherent to a centroidal Voronoi partition for the optimized dislocation of a set of heterogeneous buoys and similar sensor networks in a large area. The optimal deployment was found to be a variation of the generalized centroidal Voronoi configuration, where the sensors are located at the centroids of the corresponding generalized Voronoi cells. In turn, we provided a control law that under some constraints on the sensor velocity guarantees immediate results on stability and convergence of the centroids to the final position where the sensing power is higher. The generality of our findings could improve the possibility to apply our approach to reduce the costs of the real-time surveillance of large areas. The proposed solution has been fitted into an iterative algorithm that allows for evolution constantly, in real-time for the displacement of the network in response to dynamic events and changes in risk. Numerical simulations have been conducted to show the efficacy of the approach, while tests in a realistic scenario, consisting of areas of the Mediterranean Sea, are foreseen in the near future.

Figure 1 .

 1 Figure 1. Distribution of pair events distance as given by a Poisson probability density function (PDF), Equation (3).

Figure 2 .

 2 Figure 2. Example of dislocations of n = 20 pollution event randomly distributed using a Poisson PDF.The correspondent Voronoi diagram is built considering the pollution events located at the nodes.

Figure 3 .

 3 Figure 3. On the left, dislocations of n = 20 sensors, as in Figure 2; on the right, the representation of the power monitoring using the same dislocation configuration, where the sensors having common limited range R are located on the points defined by the Poisson distribution, Equation (3); the pollution event occupies one site. The blue domains represent the highest sensing power, and the black circles denoted the centroid set i p . Note that the area on the right image is slightly larger with

Figure 4 .

 4 Figure 4. Dislocation of initial n = 7 sensors located in a blind linear configuration on a large area. The circle denotes the sensed area, m = 16n. A blind dislocation made by regular and equidistant positions provides equiprobability for the occurrence of a pollution event on the area to be monitored.

Figure 5 .

 5 Figure 5. Evolution of the swarm composed by n = 7 sensors on large area starting from an initial set of blind positions as in Figure 4 and moving around a pollution events located at two different positions between the initial pollution occurrence and the final location when the sensors' power is maximal and real time monitoring is reached (initial and final black slick are indicated by the arrow in (B), and sensors are denoted by blue color in the intermediate configuration and red in the final configuration). The initial configuration changes are re-dislocating themselves in a new set of positions given by the centroids calculated with Equation (13) and using the control law Equation (12), α = 10. (B) is a zoom-in of the (A).

Acknowledgments:

The authors wish to thank the BIO-ICT joint laboratory between the Institute of Biophysics and the Institute of Information Science and Technologies, both of the National Research Council of Italy, in Pisa.

Funding:

The work was partially supported by the Italian National Project PON "Smart Cities and Communities" S4E and by the EU FP7 Project Argomarine (Grant 234096).

Author Contributions: M.D. conceived and developed the theoretical support of the methodology. M.D., D.M., A.P. and O.S. carried out the numerical results. All the authors discussed the results and contributed to the manuscript writing with a major contribution of M.D. and D.M. The overall study was supervised by M.D. All authors have read and agreed to the published version of the manuscript.

Conflicts of Interest:

The authors declare no conflict of interest.