Diego Pacheco-Paramo

Luigi Iannone

Daniel Kofman

Aline C Viana

Adaptation of Topology-Based Routing Protocols for Data Gathering Applications in VANETs

The use of VANETs for data gathering applications imply that vehicles are not only able to generate data but also to forward it from others towards an access point (AP). Given the mobility characteristics of vehicles and the difficult propagation conditions of urban scenarios, it is commonly stated that topology-based routing solutions are less efficient than geographic-based routing solutions. However, these statements refer to generic vehicular communications, ignoring specific characteristics of data gathering scenarios. In this work, two existing routing protocols that prior to forwarding data, set a path from each vehicle towards the AP are adapted for data gathering applications. While the existence of a path reduces the number of ineffective retransmissions and the delay, it also increases the overhead, and therefore the presented protocols were adapted to improve the overall performance. Aiming to correctly evaluate the routing protocols, simulations are launched using a realistic trace from the city of Cologne. The results obtained show that it is possible to limit the overhead associated to topology updates, outperforming geographic-based solutions.

I. INTRODUCTION

Data gathering applications in vehicular networks allows a central node to maintain recent information from several specific locations for storage and/or processing purposes. Typical applications that have received attention in the past are urban monitoring for safety or maintenance uses, or to support intelligent transport systems [START_REF] Lee | Mobeyes: smart mobs for urban monitoring with a vehicular sensor network[END_REF], [START_REF] Eriksson | The pothole patrol: using a mobile sensor network for road surface monitoring[END_REF], [START_REF] Rodrigues | A mobile sensing architecture for massive urban scanning[END_REF]. These applications have unique requirements in terms of data size, sampling frequency or maximum delay, and normally communicate to an Access Point (AP) through multi-hop communications using the free spectrum, especially since the standardization of 802.11p. Sending periodical data from several vehicles towards the same geographical point implies a different type of solution than those proposed for V2V communications applied to safety or infotainment.

In the same way that occurs with wireless sensor networks (WSN), data gathering applications suffer from high interference as a result of having several vehicles transmitting towards the same geographical point. However, the solutions found for WSNs cannot be directly applied to VANETs due to its specific mobility characteristics and urban conditions. In VANETs the most important constraint is the high intermittent connectivity which typically demands high overhead costs for topology-oriented routing protocols. This is the result of a high vehicular mobility, a non-homogeneous distribution that may create gaps, and also of losses caused by physical objects such as trees or buildings.

Corresponding author: diegofelipe.pacheco@gmail.com Based on previous efforts in WSNs, a large portion of the routing protocols use geographic information such as the position and velocity in order to forward data towards the AP. Among them, The greedy perimeter stateless routing protocol (GPSR) [START_REF] Karp | Greedy Perimeter Stateless Routing for Wireless Networks[END_REF] is characterized by forwarding data in the direction of the AP, that is, in a greedy way. The main advantage of this type of protocols is that vehicles do not need to maintain an structure of the network, and therefore no overhead is created to update its own state or that of the others. However, due to the unknown network conditions, it is very likely that packets run into a local optimum, especially when the vehicular density is not high or there are many obstacles, which is common in urban scenarios.

Yet, keeping a path towards the destination is a desirable feature since it avoids the local optimum problem and the delay growth associated to it. With this in mind, the connected aware routing protocol (CAR) [START_REF] Naumov | Connectivity-Aware Routing (CAR) in Vehicular Ad-hoc Networks[END_REF] was proposed for VANETs. This hybrid protocol sets a path from origin to destination just like a topology oriented protocol, but forwards data greedily towards anchors defined by their position, like geographic oriented protocols. However, this protocol cannot be used as it is in data gathering applications due to the high overhead associated to setting end-to-end paths. Therefore, we have adapted a lighter version of the protocol. On the other side of the spectrum are topology-oriented protocols. In particular, our interest lies in RPL [START_REF] Winter | RPL: IPv6 Routing Protocol for Low-Power and Lossy Networks[END_REF], which was originally designed for WSNs. As such, this protocol creates a tree that grows from the AP towards the vehicles, simplifying the path setting process. But as a WSNs protocol, some modifications have to be done in order to make it work in VANETs, in particular in its ability to identify and correct fast topology changes.

Therefore, the main objective of this work is to adapt these two protocols (one hybrid and one topology-oriented) for data gathering applications in VANETs, hence exploiting their ability to have ready paths towards the AP while aiming to reduce their associated overhead, and evaluate their relevance in such scenarios.

A necessary condition for an appropriate evaluation of data gathering applications in VANETs is a correct mobility model. Most simulations use mobility models that underestimate the impact that vehicular mobility and urban scenarios have on the performance. Instead,we use the available dataset of the city of Cologne, Germany [START_REF]Vehicular mobility trace of the city of Cologne, Germany[END_REF], which represents 2 hours of traffic (6 am-8 am). This dataset has a series of characteristics that set it apart from other traces, and add value to our analysis. First, it is not limited to a specific type of vehicles, such as taxis or buses. Second, it is designed to cover an area of approximately 400 km 2 in a period of 24 hours, and therefore although our scope is limited to an area of 4 km 2 , the behaviour of the vehicles is not. Third, the dataset has been modified to respect microscopic characteristics such as the road layer and the traffic signs. Finally, the trace is based in daily activity reports that considered 1.2 million trips in a 24 hours period, and some algorithms were applied to make it consistent from a macroscopic point of view. This last characteristic is important since it shows that previous efforts may have been too optimistic in terms of connectivity, and by extension in crucial parameters such as delay, path length or path duration [START_REF] Uppoor | Generation and Analysis of a Large-scale Urban Vehicular Mobility Dataset[END_REF].

The rest of the document is organized as follows. In section II we present related work. Two routing protocols that maintain an optimal path to the destination are described with their modifications in order to be used in data gathering scenarios in Section III. In section IV, we describe the experimental scenario and the tools used to evaluate the different protocols. In section V, we evaluate the routing protocols with varying conditions in terms of overhead, delay and PDR. Finally, the conclusions of the work are given in Section VI.

II. RELATED WORK

In this section we review some of the relevant work that exists in the area of data gathering and related routing protocols.

In [START_REF] Lee | Mobeyes: smart mobs for urban monitoring with a vehicular sensor network[END_REF], a data gathering system that aims to provide urban monitoring services is presented. Although it defines the similarities to traditional WSNs problems, it also brings into account the fact that traditional broadcasting is not possible due to mobility and paths conditions, and also that data filtering is not feasible since a vehicle cannot know which data will be useful for the application.

Most of the geographic routing protocols are based in GPSR [START_REF] Karp | Greedy Perimeter Stateless Routing for Wireless Networks[END_REF]. As a result of the well known limitations of the perimeter mode in urban scenarios, different protocols have been proposed. The protocol GPCR [START_REF] Lochert | Geographic routing in city scenarios[END_REF] forwards data into junctions, where routing decision are made. If the decision in the junction leads to a local optimum, then the packet is sent back and a new decision is made. In GPSRJ+ [START_REF] Lee | Enhanced perimeter routing for geographic forwarding protocols in urban vehicular networks[END_REF], another GPSR-based protocol, when a local optimum is found the nodes that have a neighbor that lies inside a junction have the ability to decide which route to follow, reducing the traffic in the junctions, and also reducing the number of hops.

In [START_REF] Seet | A-STAR: A mobile ad-hoc routing strategy for metropolis vehicular communications[END_REF] the A-STAR protocol is proposed, where the path is set as a group of anchors and data is forwarded greedily between them. These anchors are street aware, that is, traffic information is considered for their definition. The same anchor principle is followed by CAR [START_REF] Naumov | Connectivity-Aware Routing (CAR) in Vehicular Ad-hoc Networks[END_REF] as mentioned earlier. An improvement of this protocol, ACAR [START_REF] Yang | ACAR:Adaptive Connectivity Aware Routing for Vehicular Ad Hoc Networks in City Scenarios[END_REF], considers the vehicular density in order to define the preferred path. With this tool, the protocol can react to sudden changes in traffic conditions. ECAR [START_REF] Maidorawa | An enhanced connectivity Aware Routing Protocol for Vehicular Ad-hoc Networks[END_REF] defines secondary paths in order to avoid launching correction procedures that increase the overhead.

The MURU [START_REF] Mo | MURU: A multi-hop routing protocol for urban vehicular ad-hoc networks[END_REF], is a topology-oriented protocol for VANETs that considers the disconnection probability is introduced, and this probability is calculated using information about the position and velocity of the nodes. However, unlike RPL, it uses reply messages to set a path, increasing the overhead.

None of the presented protocols fulfil the requirements of data gathering applications. In [START_REF] Aguiar | Supporting Sensing Application in Vehicular Networks[END_REF], a broadcasting method that searches simultaneously through several paths is proposed for an urban sensing scenario. This solution may avoid the delay associated to finding a local optimum and launching a perimeter mode of GPSR, but increases the overhead, reducing the PDR. In [START_REF] He | Density adaptive urban data collection in vehicular sensor networks[END_REF], a routing protocol that uses velocity vectors in order to decide where to forward data is presented. However, it considers that the density of vehicles is very high (high connectivity) while at the same time only a fraction of them can send data towards the AP. In [START_REF] Palazzi | Delay-Bounded data gathering in urban vehicular sensor networks[END_REF] a protocol for delaytolerant networks is proposed. This solution assumes that the solution allows data aggregation for a better use of the resources, and also its delay can be sometimes prohibitive (>1 min).

III. ADAPTATION OF A HYBRID AND A

TOPOLOGY-ORIENTED ROUTING PROTOCOL.

In this section we describe the modifications and implementation of the two path setting routing protocols (RPL and CAR) evaluated in this paper.

A. RPL Implementation

The Routing Protocol for Low Power and Lossy networks (RPL), was originally designed for wireless sensor networks, aiming to be effective with limited resources and high link unreliability. Accordingly, the protocol keeps secondary routes when possible, identifies degrading links and corrects paths, all while controls the associated overhead. Also, many important characteristics are implementation dependant.

In RPL, the root node builds a hierarchical topology, defined as a Destination Oriented Directed Acyclic Graph (DODAG), that specifies a route from each node to itself using one type of message, the DODAG Information Object (DIO). Once a node receives a DIO, it can first, calculate its own rank, then, choose a set of parent nodes and finally, send a new DIO to inform other neighbors. The rank is an integer that grows linearly from the root node, and identifies the position of the node in relation to the root and the rest of the nodes. The parents are a set of candidate nodes where data can be forwarded towards the root node. Accordingly, the parents must have a rank equal or lower than the node. Each node has a preferred parent, that is, a default path, but maintains a list of parents for resilience purposes. Hence, immediately after the reception of a DIO, a node has an optimal path towards the root node.

The optimal path is set according to an optimization function (OF) which indicates the criteria that the nodes must follow in order to choose their preferred parent, and thus affects their rank in the DODAG. In our implementation, the optimization function depends on two parameters: The expected transmission count (ETX) [START_REF] Couto | A high-throughput path metric for multi-hop wireless routing[END_REF], which is the number of necessary retransmissions to succesfully perform a one-hop delivery, and the hop count as follows:

OF (P arent) = ET X P arent + Hops P arent max(Hops) P arents ,

where ET X P arent is calculated through the interaction of hello beacons with its neighbors, Hops P arent is the number of hops from the root to the Parent candidate and max(Hops) P arents is the maximum number of hops from the root to the candidate parents. Hence, by choosing the parent with the lowest OF, the protocol penalizes unreliable links and benefits shorter paths. If the link between a node and its preferred parent degrades, the node can easily choose another parent of its parent list, adding resilience to the network without increasing the overhead. The introduction of the link state in the OF is crucial for the correct performance of RPL in a VANET scenario.

To control the generation of DIO messages, the trickle algorithm [START_REF] Levis | The Trickle Algorithm[END_REF] is used. With this algorithm, the node decides to forward DIO messages if it has received less than R DIO redundant messages about the status of its neighbours in a given initial period of time T DIO . If enough consistent DIO messages are received, then the node doubles the original period to account for consistent DIO messages. If the conditions are met, this process is repeated until a maximum period is reached. However if an inconsistence is detected (e.g. a neighbor changes its rank), a DIO message is sent, and the period is reset to T DIO . In this work we keep this algorithm since it performs better than sending DIO messages with a fixed frequency [START_REF] Lee | A comprehensive Evaluation of RPL under Mobility[END_REF]. However, due to the highly dynamic nature of VANETs, we have identified three inconsistencies on data forwarding: i) A node may receive data when it has no active parents, ii) A node may receive data from a node with lower rank, and iii) A node may receive data originated by itself. These inconsistencies are the result of an outdated DODAG (i,ii) or connectivity issues (iii), and cause an increase of the overhead. The former can be enhanced reducing T DIO , but the latter is caused by loops originated due to isolation from the DODAG, and therefore is mobility dependant. Our implementation can identify this loops by the rapid growth of rank, and force a disconnected state, which can be overcome when normal network condition arise.

The path setting process of our implemetation is explained in Figure 1. First, an AP broadcasts a DIO message (rank=0) that two other vehicles receive. These vehicles can immediately forward data to the AP, and also broadcast a DIO message with the rank updated (rank=1). In 2, a third vehicle receives both DIOs and chooses one of them as the optimal path to the AP, considering both the rank, and the ETX. Finally in 3, one of the vehicles has lost connection to the AP, and therefore its rank, so when it receives a DIO message, it accepts it, and adopts a new rank (rank=3). With this protocol, the nodes have a path to the AP described by a set of nodes.

B. CAR Adaptation

The connectivity-aware routing protocol (CAR) [START_REF] Naumov | Connectivity-Aware Routing (CAR) in Vehicular Ad-hoc Networks[END_REF] is a geographic routing protocol that establishes full paths before data transmission, updates them in order to adapt to dynamic conditions, and given the case, performs error correction procedures. However, it suffers from high overhead in data gathering scenarios, and some adaptations where performed to address this issue.

In order to set paths to the root node, CAR sends Path Discovery (PD) messages including information about its location and velocity vector in dissemination mode. Whenever a node receives a PD message, it compares its position and velocity vector with the ones in the message, and if there are substantial changes, it appends an anchor, that is, its own location and velocity vector to the message. Several PD messages are expected to arrive to the final destination, so it can decide which path is optimal. The destination creates a Route Reply (RR) message, and sends it back to the origin following the optimal path so data transmission can begin. However, for data gathering applications the dissemination of PD messages from each origin node to the destination is detrimental to the overall performance. To address this issue, in our implementation PD messages travel until they find a node that has a working path to the destination node, when a unicast RR message will be sent to the origin. Let us recall that in a scenario where all the nodes transmit data, only onehop PD and RR are necessary. Still, this solution is not enough to reduce the overhead. Once the network overcomes the transient state of disconnected nodes, after a PD broadcast most of the neighbors will reply with an RR message. Therefore, a probability p RR is set, which defines the probability that a RR message is sent after receiving a PD message.

Data is sent to the root node through advanced greedy forwarding (AGF) [START_REF] Naumov | An evaluation of intervehicle ad hoc networks based on realistic vehicular traces[END_REF]. With this method, data is forwarded to the node that is closer to the next anchor, that is, the path describes a set of anchor points instead of a set of nodes. In order to avoid unnecessary efforts to reach the exact location of each anchor, the protocol includes a threshold distance d min . If the distance between the node and the next anchor is lower than d min , then the node forwards towards the following anchor. The protocol suggests to use half of the maximum transmission distance on free-space air as d min , but in dense urban scenarios this value should be smaller and adapted to the structure of the layout. This porves difficult, since the layout is not uniform, and transmission ranges depend on the conditions of the network.

Since nodes tend to distance from the anchors, CAR counts with methods to update the paths and under certain conditions, to correct them. As a source moves away from the location where it started the Path Discovery procedure, new anchors could be added to the path. An anchor is added if any of the following conditions is met: i) The node has moved away from the original position in an angle that is higher than 18 • from the original velocity vector, or ii) The distance between the node and the first anchor of the path is higher than d max . But this procedure alone does not lead to optimal performance, so in order to use the best path to the AP in our implementation the node demands the paths from its neighbors in a periodical basis T U pd . Hence, if a neighbor has a route with less hops or with equal hops but newer, the node replaces its old path. In this way the network prioritizes shorter paths or at least those with active vehicular traffic. Finally, when the node is not able to forward data due to network disconnection it proceeds in two ways: First, it waits a given time before retransmitting hoping that the disconnection time is short and a next hop can be found soon. Then, if after the period expires a next hop is not found, a path discovery path procedure must be launched.

In Figure 2 we describe the path setting process of our adaptation of CAR or as it will be called from now on, CAR ad . First, the vehicles send PD messages that are received by the AP, which replies with two RR messages. Then the vehicles are able to forward data to the AP, or to a node that is closer to it, since the location and the velocity vector of the AP is known. Then in 2, a new vehicle broadcasts a PD message, and the two connected vehicles reply with RR messages. In 3, the vehicle sends data to the node closer to the next anchor point (the green point), and the procedure is repeated with disconnected vehicles. In this case, the path to the AP is described by a set of anchors (the green points in the Figure ) that serve as references for data forwarding.

IV. EVALUATION SCENARIO

In this section, we describe the scenario for data collection and the simulation setup for the evaluation of the two described topology-oriented protocols: RP L and CAR ad , and GP SR [START_REF] Karp | Greedy Perimeter Stateless Routing for Wireless Networks[END_REF], a well-known geographic protocol which is used as a reference and available in the INET Framework [START_REF]INET Framework[END_REF].

We consider an AP placed in a concurred place of the city centre of Cologne, Germany, that collects information from the vehicles that lie inside an Area of Interest (AoI) formed by a circle with radius of 1 km. This is the fourth biggest city in Germany, and a realistic dataset [START_REF]Vehicular mobility trace of the city of Cologne, Germany[END_REF] that represents 2 hours of traffic (6 am-8 am) is available. The simulation of the communication stack was done through OMNET++ [START_REF] Varga | The omnet++ discrete event simulation system[END_REF] in tandem with Veins [START_REF] Sommer | Bidirectionally Coupled Network and Road Traffic Simulation for Improved IVC Analysis[END_REF] and SUMO [START_REF] Krajzewicz | Recent Development and Applications of SUMO -Simulation of Urban Mobility[END_REF] for the realistic mobility of vehicles. The physical and MAC layers follow 802.11p specifications, that is, 10 MHz channels in the 5.9 MHz band, with an alternating access of the control (CCH) and service (SCH) channels. Since 802.11p allows the use of different access categories (AC), we give the highest priority in the SCH to routing messages (DIO messages in RPL, Path Discovery and Route Reply messages in CAR), and the second highest to data. The CCH is used exclusively to send hello beacons. In order to reduce the known congestion issues of 802.11p in high density scenarios [START_REF] Campolo | Modeling Broadcasting in IEEE 802.11p/WAVE Vehicular Networks[END_REF] we increased the minimum size of the contention window. Additionally, we used the two-ray ground model for path loss and accounted the buildings and constructions for shadowing. The parameters of the simulations are included in Table I. On each simulation, users transmit data for 300 seconds, and the simulation ran until no more data was buffered in the vehicles. Although data can only be generated inside the AoI, routing packets can be received (but not forwarded) by nodes outside so paths are available when requested. Data packets have a size of 1 KB and their generation period is uniformly distributed [0.5-2] s, that is, with mean 1.25 s, which are acceptable values for different applications [START_REF] Rodrigues | A mobile sensing architecture for massive urban scanning[END_REF]. It should be noted that vehicles that use RPL can only start generating data once they have a rank and are inside the AoI. When CAR ad is used, vehicles can start forwarding data once an RR message is received and the vehicle lies inside the AoI. On the other hand, when GPSR is used, vehicles only need to be inside the AoI for data forwarding. It is known that MAC layer parameters have an important impact when evaluating routing protocols. In particular, the setting of the maximum number of retries before discarding a packet, Retry M AX , is of crucial importance. Ideally, this parameter should adapt to the conditions of the network in order to transmit data without creating too much interference, but in this work we changed it manually on each scenario with the objective of maximizing the PDR.

V. RESULTS

In this section we evaluate the three protocols at different times from the Cologne trace.

In Figure 3 the packet delivery ratio (PDR) for the three protocols at different times, each with a different mean number of vehicles inside the AoI, N is shown. It can be seen that the PDR increases with N , but for high vehicular density it drops considerably. Also, the PDR is bounded by 90%, which is the result of different conditions such as high mobility, low connection times and interference. Among the protocols, RP L is able to obtain the highest PDR for most scenarios, in fact it is only surpassed for N =114. This is due to the fact that vehicles with RPL only forward data packets if they have a rank, that is if they have an up to date path to the AP. This, however, is not enough to maintain a high PDR for high values of N , and therefore we see a drop of around 20% when N grows from 114 to 139. In high interference scenarios, it is possible that vehicles do have a rank, but they are incapable of successfully forwarding data, even as Retry M AX grows. In fact, if this value is too high, more interference is created, and the PDR drops. This applies for all the tested protocols, but it has a more acute effect in GP SR and CAR ad . In the former, because GP SR has a higher average hop count due to the necessary retransmissions performed when a local optimal is found. In the latter because it is possible that it performs more hops than necessary in a given path since it always tries to forward to the node closest to the next anchor point. Therefore, to enhance the PDR, a higher value of Retry M AX was used for RP L than the other protocols.

A clear indicator of the performance of the protocols is given by the total overhead, shown in Figure 4. Here, the average number of messages per second sent is shown for different values of N . We consider that both, the total number of data retransmissions, and the routing messages contribute to the total overhead. Clearly, the lowest overhead is obtained using RPL which implies that the use of the trickle timer effectively reduces the volume of routing messages (DIO) while maintaining an updated state of the network, which can be seen by the low number of necessary data retransmissions. Only when the overhead is similar to GP SR (N =114), this last protocol obtains a better PDR. In fact, the throughput, measured as the average number of data packets that arrive to the AP per second, is reduced when N grows from 106 to 114, as can be seen in Figure 5. This happens because RP L was not able to find a balance between the generation of DIO messages and Retry M AX in a scenario where different vehicular densities coexist. Therefore, a method that takes into account the vehicular density in the neighborhood for setting both T DIO and Retry M AX is desirable.

In the case of GP SR, no routing messages are added, since the information for routing is appended to each data message. However, the existence of a local optimum in the path forces the performance of an ineffective perimeter mode. Hence, the number of retransmissions is very high, as can be seen in Figure 4, especially for low vehicular density values, when the probability of finding a local optimum is higher. When N =106, there are enough vehicles for connectivity in such a way that the value of Retry M AX that optimized the PDR was reduced. Therefore, a considerable reduction of data retransmissions is achieved. However, RP L continues to be more effective in most cases. Finally, the CAR ad protocol is the less effective. Clearly, the amount of PD and RR messages is very high, and creates too much interference in the system. Also, the definition of d min and d max is tricky, and can have very different effects in different parts of the network. Let us recall that the AoI consists of a typical urban with narrow streets surrounded by buildings, but also bridges that cross the river, and a ringroad that is similar to a highway scenario. Therefore, it is difficult that this parameters are optimal for the whole network, causing two different effects if anchors are too close or too far. In the former case, there might be unnecessary hops and hence too many retransmissions causing interference, and in the latter, local optimums due to the inability of vehicles to find paths in areas with obstacles. To evaluate the critical amount of overhead created by this protocol, it can be seen that in the worst case (N =139), the overhead is around 56 times the amount of data that arrives to the AP. Such a high relation not only affects the performance of the overall system, but also indicates a poor efficiency in terms of bandwidth use.

In Figure 6, we evaluate the delay of the routing protocols for two scenarios. The first scenario was taken at 7:05 am, when N =73. The second scenario is taken at 6:25 am, when N =139. Clearly, RP L has the lowest delay, and although it does not fulfil the strict requirements of real-time applications (delay<100 ms), it is able to transmit 99% and 90% of the data packets in less than 1 s for the low traffic and high traffic scenarios respectively. In the case of GP SR, only 80% and 65% of the traffic arrives with less than 1s of delay, and it should be noted that the amount of data that arrives is less than with RP L. Also, the fact that the delay can be as high as 35 s, is a consequence of the high number of retransmissions associated with this protocol, that make it ineffective as the number of vehicles grows. On the other hand, CAR ad has the highest delay for both scenarios, which is consistent with the amount of overhead that it creates. However, unlike the other protocols, the delay does not improve for the scenario with low traffic. This happens because in the low traffic scenario, in order to enhance the PDR, the vehicles have to wait until they find a neighbor that is closer to the next anchor than themselves. This is effective in terms of PDR, since the performance of CAR ad is better than that of GP SR. As traffic increases, vehicles should have more neighbors available, waiting less to transmit, and thus reducing the delay. However, this is not an improvement by itself if we consider that the PDR of this protocol for the high traffic scenario is the lowest of all.

VI. CONCLUSIONS

In this work we have adapted two routing protocols for data gathering applications. The first routing protocol, RPL, is a well known topology-oriented protocol for WSNs. It has the advantage of creating a tree from the AP towards the vehicles, establishing paths from each node through a single type of message, and also it is able to the overhead through the use of a trickle timer. We set an optimization function based on the quality of links to adapt to dynamic conditions of VANETs and after identifying different types of inconsistencies that may arise in data forwarding, included appropriate correction methods. The second adaptation was done over a hybrid protocol, CAR, which creates paths towards the AP as a group of locations, where data must be forwarded following a greedy fashion. We replaced the path setting process by a one-hop exchange that scales better in data gathering scenarios and controlled the overhead with a probabilistic function. Several simulations using a realistic trace of the city of Cologne were performed to compare the two protocols with a geographicbased protocol (GPSR). Results showed that RPL was able to reduce the overhead associated to topology maintenance while at the same time keeping a low delay. On the other hand, the overhead created by the two step path setting of CAR is difficult to reduce, and also the protocol suffers from excesive retransmissions due to its inability to adapt its location based paths to different coexisting geographic conditions in the area of interest. Finally, results showed that it would be desirable to include some adaptive characteristics to the protocols in order to enhance their resiliency to vehicular density changes.

Fig. 1 .

 1 Fig. 1. Path setting and data forwarding to an AP using RPL. DAO messages are not used.

Fig. 2 .

 2 Fig. 2. Path setting and data forwarding to an AP using CAR ad .

Fig. 3 .

 3 Fig. 3. Packet Delivery Ratio for the three protocols with different vehicular traffic values.

Fig. 4 .

 4 Fig. 4. Total overhead for the three protocols for different vehicular traffic values.

Fig. 5 .

 5 Fig. 5. Average throughput for data received in the AP in packets per second.

Fig. 6 .

 6 Fig. 6. Delay cumulative probability in two different scenarios.

DATA DATA DATA DIO DATA DIO 1 2 3 DATA DATA DATA DATA 3 1


Ph.D Anthony Boscaro
email: anthony.boscaro@u-bourgogne.fr

S Jacquir

K Sanchez

P Perdu

S Binczak

Improvement of signal to noise ratio in Electro Optical Probing technique by wavelets filtering

Electro Optical Probing (EOP) technique is an efficient backside contacless technique to measure waveforms in modern VLSI circuits. The signal related intensity variation of the reflected beam is very weak therefore, to acquire a signal with enough Signal to Noise Ratio, averaging techniques are usually performed. Resulting acquisition time for one waveform are too long to implement point to point probing to image mode. To overcome this limitation, we have developped a new filtering by wavelets approach to keep a good SNR while significantly reducing this acquisition time. It opens the doors to new multipoint probing applications. In this paper, we describe the technique, its efficiency in terms of SNR, execution time and limits.

Introduction

In addition to light emission techniques, methods based on laser exploit optical stimulation or optical properties of reflected beam [START_REF] Jiann | Fault isolation in semiconductor product, process, physical and package failure analysis : Importance and overview[END_REF]. Electro Optical Probing is a popular timing-analysis laser-based technique [START_REF] Kindereit | Fundamentals and Future Applications of Laser Voltage Probing[END_REF], using Franz-Keldysh effects and free carrier absorption. Heinrich was the precursor of EOP approach [START_REF] Heinrich | Picosecond noninvasive optical detection of internal electrical signals in flip-chip-mounted silicon integrated circuits[END_REF] by proposing a noninvasive method which uses an infrared laser measuring the modulation of the free carrier density induced by the variation of electric potentials inside bipolar transistors. At the end of the nineties, a commercial application of the LVP technique was developped by Schlumberger Technologies Inc [START_REF] Paniccia | Optical probing of flip chip packaged microprocessors[END_REF]. The source used was a pulsed laser, wavelength of 1.06 microns, 35 ps pulse duration.

Since its introduction, Electro Optical Probing has become an essential tool to the failure analysis (FA) and design debug communities [START_REF] Kindereit | Fundamentals and Future Applications of Laser Voltage Probing[END_REF]. In backside EOP analysis, pulsed or continuous laser beam is focused on a node of the chip which has been thinned. Thereafter, the reflected beam properties are analyzed.

The reflected signal mostly contains usual optical reflection from metal lines and a very weak signal related to free carrier absorption and bandgap modulation difficult to extract from noise. Techniques such as averaging [START_REF] Kenneth | Dual-laser voltage probing of IC's[END_REF] and frequency-domain measurements [START_REF] Kindereit | Investigation of laser voltage probing signals in CMOS transistors[END_REF] have been implemented in probing and image modes. Averaging process is quite efficient in probing mode but it results at least in seconds duration to probe each node. This single waveform acquisition duration prevents EOP to probe each point of the device to build a waveform database of the full device. It will last from days to weeks to do it. Using frequency analysis in image mode is pretty fast but timing information is lost as a scan gives only amplitude information on one frequency inside the device. Therefore, in order to build a waveform database of the full device or just to reduce acquisition time to acquire thousands of nodes in a batch process (automatically moves to the next node, focus, slightly defocus up and down and each time scans a small area to finally extract the best waveform), it is mandatory to reduce processing time for each waveform while keeping a reasonable SNR. This paper introduces a new processing scheme based on wavelet transform to achieve this goal. We firstly remind some EOP background. The second section is dedicated to the description of EOP acquisition setup. The third section introduces the complete processing sequence. The fourth section exhibits the SNR improvement by wavelets transform. A fith section concerns examples of results. And before a conclusion a sixth section tells about the level of decomposition and the choice of the wavelet used for the filtering.

Electro Optical probing

EOP technique is still based on analysis of the reflected beam properties [START_REF] Harley | Method and means for optical detection of charge density modulation in a semiconductor[END_REF]. Intensity varies with temperature change [START_REF] Quintard | Réflectométrie et interférométrie laser haute résolution. Application à la caractérisation de composants électroniques[END_REF], charge density [START_REF] Paniccia | Optical probing of flip chip packaged microprocessors[END_REF] or electric field [START_REF] Heinrich | Measurement of real-time digital signals in a silicon bipolar junction transistor using a noninvasive optical probe[END_REF]. The analyze of the properties of the reflected laser beam can be traced back to its origin, in order to obtain information on the physical parameter studied. Two wavelengths have been used for EOP, also known as LVP (Laser Voltage Probing, [START_REF] Kolachina | Introduction to Laser Voltage Probing (LVP) of Integrated Circuits[END_REF] [START_REF] Soref | Electro-optical Effects in Silicones[END_REF]) : 1064 and 1340 nm. 1064 gives a better spatial resolution (shorter wavelength) and the laser beam absorption is sensitive to carrier density (free carrier absorption) and to small bandgap (Franz Keldish) variations. Nevertheless, absorption is important (less reflected beam intensity) and it induces slight Optical Beam Induced Current (OBIC) that could bias a little bit the measurements. 1340 nm is less absorbed, is not sensitive to Franz Keldish effect. Considering the free carrier absorption mechanism, EOP is based on the very weak useful part of the reflected signal. It means that noise coming from various sources (thermal, shotky, electronic . . . ) is often order of magnitude higher than this useful part of the signal. During the acquisition, a signal with a weak amplitude drowned in noise is measured. If the waveform is directly acquired without processing, the SNR is extremely low. The absorption coefficient varies according to equation (1) [START_REF] Rebai | Temperature Effect on Reflected Laser Probing Signal of Multiple Elementary Substructures[END_REF]. According to M. Rebai [START_REF] Rebai | Temperature Effect on Reflected Laser Probing Signal of Multiple Elementary Substructures[END_REF], the relative changes are often less than 10 -3 less than those induced by temperature changes.

α f c = A λ 2 q 3 4π 2 c 3 0 0 n 0 [ N e m 2 e µ e + N h m 2 h µ h ], (1)
with α f c = absorption coefficient variation, A = refinement coefficient, λ = wavelength, q = elementary charge, c 0 = celerity of light in vacuum, 0 = permittivity in vacuum, n 0 = refractive index in silicon, [m e , m h ] = concentration of electrons and holes, [µ e , µ h ] = mobility of electrons and holes, [N e , N h ]= number of electrons and holes.

Acquisition setup

To solve this problem and improve the SNR, our existing aquisition setup integrates signals by averaging. Experimentations were done on Tri-Phemos, device designed by HAMAMATSU Photonics.

The signal of the reflected beam is acquired by a photodiode and amplified. The output signal of the amplifier is sent to an oscilloscope which proceeds in 512 averages to improve the SNR in a first time. In a second time, this averaged signal is sent to a computer (with LABVIEW interface) which integrates by averaging severals acquisitions (one acquisition corresponds to 512 oscilloscope averages). Figure 1a shows that the signal is submerged in noise if only one acquisition is taken into account. Our setup needs several averages, by consequences a lot of time is necessary to significantly improve SNR. To illustrate these explanations, an example of probing on a micocontroler STM32 was chosen. After some averages (10 averages in our case), we obtain the waveform in Figure 1b. We can notice that the SNR is very low. The number of averages has been increased to decrease the SNR. Figure 1c is the result after 418 averages.

Considering our hardware, an acquition is achieved in 0.7s. It is very long in some cases as shown with the previous example. An approach with simple filters (Median, FIR, IIR) has been tested to improve the SNR and reduce acquisition time. If this kind of process is applied with a large scale, the signal will be indeed smoothed but short duration signals can be lost because of mandatory sample size (up to tens of samples) to get a reasonable noise re-duction. That is why a process based on filtering by wavelets was implemented to improve both aquisition times and SNR. Example of result is represented in Figure 1. We precise that the aim of this process is to decrease the number of averages in order to reduce aquisition time while having a good SNR. For this example we have taken the same signal as previously but only 10 averages are used. Visually, we can notice the improvement of the SNR. In addition the acquition time is reduced due to the decreasing of averages. For the same acquisition time (7 s here), the SNR is significantly improved. The computing time for wavelet transform can be evaluated in few ms. The filtering process by wavelets transform is explained below.

SNR improvement by wavelets transform

Multiresolution analysis : discrete wavelet transform

Since few years, several approaches have emerged in signal processing in order to remove the noise in signals. In [START_REF] Walker | Tree-adapted wavelet shrinkage[END_REF], it is said that these new methods with wavelets give better results than Wiener filtering. Wavelets transform can be adapted to the discrete set. The size of the information could be reduced by choosing a level of detail. In our case, we use one aspect of wavelets : the multiresolution decomposition, which is very used in image processing because of its performance [START_REF] Sonja | Performance analysis of image compression using wavelets[END_REF]. It is recalled that in failure analysis, wavelets have ever been applied to perform the approach by Time-Resolved Imaging in light emission [START_REF] Chef | Frequency mapping in dynamic light emission with wavelet transform[END_REF]. This reference used the Continous Wavelet Transform to determine a frequency while we use the discrete wavelet transform (DWT) to filter the signal. [START_REF] Stephane | A theory for multiresolution signal decomposition : the wavelet representation[END_REF] and [START_REF] Meyer | Pattern Analysis and Machine Intelligence[END_REF] explain the theory of the DWT. Given a signal s of length N, the DWT consists of log 2 N stages at most. The first step produces, starting from s, two sets of coefficients : approximation coefficients CA i , and details coefficients CD i , with i = [1,....,n]. These vectors are obtained by convoluting s with an expression equivalent to a low-pass filter (l d ) for approximation, and with another equivalent to an highpass filter (h d ) for details, followed by under-sampling [START_REF] Stephane | A theory for multiresolution signal decomposition : the wavelet representation[END_REF]. (l d ) and (h d ) correspond exactly with impulse response of low and high-pass filter respectively. These coefficients are described such as

CD i [n] = ∞ k=-∞ h d [k]s[2n -k], (2)
CA i [n] = ∞ k=-∞ l d [k]s[2n -k], (3)
where n and k denote discrete time coefficient, and i ∈ Z.

In this way, the signal s can be written as

s[n] = ∞ k=-∞ (CD i [k]h r [2k -n] + CA i [k]l r [2k -n]), (4)
where l r and h r are reconstitution filters. Next step splits the approximation coefficient CA 1 in two parts using the same scheme, replacing s by CA 1 , and producing CA 2 and CD 2 , and so on. The wavelet decomposition at level L has the following struture : [CA i , CD i , ..., CD 1 ]. Figure 2, represents this struture with terminal nodes. Now the important step, is to understand how to denoise the signal S . For that purpose, an approach by coefficients thresholding was chosen [START_REF] Walczak | Noise suppression and signal compression using the wavelet packet transform[END_REF] and described in the next section.

Coefficients thresholding

According to the literature, it exists different kinds of thresholding for the wavelets coefficients [START_REF] Walker | Tree-adapted wavelet shrinkage[END_REF] :

• Soft thresholding : The absolute value of all the wavelets coefficients is compared to a threshold T. If this value is greater than T the threshold is subtracted from any coefficient that is greater than the threshold. Others are set to zero. • Hard thresholding : Hard thresholding sets any coefficient less than or equal to the threshold T to zero. Others are preserved. • Universal thresholding : the value called universal, is defined by :

T thresh = σ 2log(N ) ( 5
)
where N is the length of the signal and σ the noise's standard deviation. Here, T thresh is used with hard thresholding. In several applications, noise is most of the time white and gaussian. This kind of white guaussian noise (WGN) is a random signal with constant power spectral density. WGN whose representation is given by ( 6), is independant and identically distributed (i.i.d) and drawn from a zero-mean normal distribution with variance σ 2 .

W GN ∼ N (0, σ 2 ) ( 6
)
According to [START_REF] Kindereit | Investigation of laser voltage probing signals in CMOS transistors[END_REF], only σ 2 is unknown. That is why wavelets are useful in our study. Here, only the standart deviation could be estimated. In rarely cases the noise is assumed but in others, it can be estimated by using the Median Absolute Deviation (MAD). This method has been introduced by Donoho and Johnstone in 1994 [START_REF] Donoho | Ideal spatial adaptation by wavelet shrinkage[END_REF]. MAD is the median absolute deviation of the empirical wavelet coefficients corresponding to the highest level j1. The reason for using these highest level coefficients for the variance estimation, is that they are mostly costitued of noise [START_REF] Härdle | Wavelet thresholding and adapation[END_REF].

By consequences the estimated variance is given by

σ 2 = M AD 0.6745 2 (7)
where 0.6745 is the 0.75-quantile of the standard normal distribution and

M AD((w j )) = M edian((|w j |) j ) (8)
with w j , the wavelets coefficients. Thus, σ 2 is now known and the threshold given in (5) can be computed. For a better understanding, a flowchart of our new process is illustrated in Figure 3.

Application, results and discussion

Results on STM32 microcontroller

The process is applied on digital signal acquired on a 90 nm microcontroller STM32, more precisly on the digital analog converter. The topographic image is reported in Figure 4. On this picture, we can notice a yellow cross which represents the pointer where the probing is applied. Figure 5 illustrates the acquired waveform and its wavelets coefficients decomposition. For this example we have decomposed with four levels with an Haar mother wavelet. On this picture we start by decomposing the original signal with wavelets. The next step consists to apply a threshold for the coefficients. And finally we go back to the time domain. As you can see at the right in Figure 5, we can considerably denoise the signal.

Signal to Noise Ratio

Previously, it has been seen that it was possible to denoise the signal. It could be interesting to compare this new method with available filtering method in the LVP field. Our filtering by wavelets is compared to filtering by

where Var(Signal) and Var(Noise) correspond to the signal and noise variance respectively.

For each values of average, the SNR with filtering by wavelets is always higher than the SNR computed with average and median filter. It proves the efficiency of the filtering to reconstitute the signal with a good SNR. Now we will focus on the other key aspect of this study, more precisly the execution time and the reconstitution error (mean square error).

Acquisition time

After the examination of the SNR, we give some results concerning the acquition time which is not a negligable parameter. In fact, by decreasing the number of averages, the acquisition time decreases. Different acquisitions have been realized on some analogue or digital signals. For a same SNR, we have reported the execution time for all the signals. Results are refered in Table 1. In all cases, the execution time with only average and median filter is always higher than the computing time with wavelets. We notice a gain between 10 and 30 dB, depending on cases.

Reconstitution error : Mean Square Error

In this king of study, it is interresting to compare quantitatively each method. That is reason the Mean Square Error (MSE) is used here. If x is a vector of n predictions, and x is the vector of the true values, then the MSE of the predictor is given by :

M SE = 1 n n i=1 (x -x) 2 (10)
Thus, the MSE evolution is computed for each kind of filter, average, median and wavelets and is represented in Figure 7. We can notice immediately that the MSE is minimized in the case of wavelets filtering for each number of

Other Example

To illustrate graphically our results, Figure 8 represents a comparison between the different kinds of filters used in LVP. This example has been realized on digital signal acquired on a 90 nm microcontroller STM32. In a first time, one acquisition is realized, see Figure 8(a), and then wavelets filtering is applied on 5 averaging, see Figure 8(b). Five averaging are reprensented in Figure 8(c) and finally median filter is applied on 5 averaging Figure 8(d) in order have a comparison. Each signal has been averaged five times in order to reduce the computing time. For a same number of averages, the signal in Figure 8(b) has clearly the best SNR.

Discussion

Decomposition Level

In this paper, prior parameters must be chosen, more precisly the decomposition level (DL) and the mother wa-velet (M W ). In fact the aim is to automate the filtering process. Concerning the decomposition level, it is possible to compute it automaticaly.

In the wavelets theory the DL max is given by the following equation :

DL max = log 2 N (11)
with N the signal length. Thus, if the signal length is known, DL max can be computed easily.

Mother wavelet

Selection of mother wavelet (M W ) could be based on qualitative or quantitative approaches. The chosen database are ten signals (analogue and digital). In this study, different MW with different vanishing moments were used : Symmlet(Sym), Daubechises(Db), Haar, Meyer and Coiflet (Coif). Instead of using qualitive approach such as similarity between signal and MW, this discussion will be based on the MSE value in function of the MW, i.e. the MSE is computed for each mother wavelet and for each vanishing moment. In fact for transcient signals, using Haar wavelet could be pointed because its shape is similar to numeric signal. But it does not prove that it is the good choice, that is the reason a quantitative approach has been chosen. Results are liste in Table 2. In 80% of cases the Sym16 mother wavelet gives the best results. These results give credit to the idea of choosing a mother wavelet to minimize the MSE.

Conclusion and perspectives

Rebuild a weak signal is a real challenge especialy when it is drowned in noise. In this paper, a new method based on compression has been reported. This process could be useful for the FA community because its allows the expert to significaly save time during the acquisition. Therefore it is partially automated, in fact the mother wavelet choice is a key step of the process and the most difficult. If the MW is chosen at the begining, the process is completly automated. In the event of the expert is not satisfied with result, he can manually adjust all the parameters to optimize the final SNR.

In terms of perspectives, this process opens the door to new multipoint probing applications and allows FA community to use signal processing techniques instead of expensive hardware.

Figure 1 :

 1 Figure 1: Probing on Digital/Analog converter STM32 : (a) One acquisition of EOP signal / Computing Time : ≈ 0.7 s / SNR = -19.96 dB. (b) Signal rebuild with 10 averages / Computing Time : ≈ 7 s / SNR = 3.09 dB. (c) Signal rebuild with 418 averages / Computing Time : ≈ 292 s / SNR = 37.39 dB. (d) Signal rebuild with wavelets transform and 1 average / Computing Time : ≈ 0.8 s / SNR = 1.9 dB. (e) Signal rebuild with wavelets transform and 10 averages / Computing Time : ≈ 8 s / SNR = 22.9 dB.

Figure 2 :

 2 Figure 2: Multiresolution decomposition tree for level L = 3.

Figure 3 :

 3 Figure 3: Flowchart of the filtering by wavelets.

Figure 4 :

 4 Figure 4: Pattern of microcontroller Digital/Analog converter (DAC) STM 32 and probing area symbolized by the yellow cross.

Figure 5 :

 5 Figure 5: Wavelets decomposition with four levels. Top left : Noised signal/ Bottom left : Wavelets coefficients/Top right : Denoised signal/Bottom right : Thresholded coefficients.

  Figure 6 represents the evolution of the SNR in function of the number of averages for each case. Here SNR is given by the following equation : SN R (dB) = 10 log 10 Var(Signal) Var(N oise)

Figure 6 :

 6 Figure 6: SNR evolution with wavelets, average and median filtering.

Figure 7 :

 7 Figure 7: Mean Square Error evolution with new filtering process, averaging and median filtering.

Figure 8 :

 8 Figure 8: (a) Signal with one acquisition. (b) Signal with wavelets filtering (c) Signal with averaging filter (d) Signal with median filtering (size 50)

Table 1 :

 1 Results of execution time on seven signals (analogue/digital) with wavelets and averaging, with median filter and with averaging only.

	SNR = 30 db	Signal 1 Signal 2 Signal 3 Signal 4 Signal 5 Signal 6 Signal 7
	Number of acquisitions with wavelets	5	15	10	20	14	25	6
	Time with wavelets and averaging (s)	3.5	10.5	7	14	9.8	17.5	4.2
	Number of acquisitions with averaging	20	70	50	100	40	120	25
	Time with averaging (s)	14	49	35	70	28	84	17.5
	Number of acquisitions with median filter	10	35	34	60	22	80	17
	Time with median filter (s)	8	25	19	42	15	56	12

Table 2 :

 2 Mean Square Error (MSE) in function of the mother wavelet choice.

		Wavelet	MSE
			Sig 1	Sig 2	Sig 3	Sig 4	Sig 5	Sig 6	Sig 7	Sig 8	Sig 9	Sig 10
	1	Sym 2	0.0163 0.0166	0.0143	0.0157	0.0153	0.0148	0.0157	0.0164	0.0131	0.0139
	2	Sym 4	0.0144 0.0149	0.0132	0.0144	0.0149	0.0142	0.0152	0.0161	0.0129	0.0133
	3	Sym 8	0.0155 0.0152	0.0143	0.0167	0.0157	0.0138 0.0148	0.0168	0.0123	0.0128
	4	Sym 16 0.0142 0.0145 0.0131 0.0154 0.0144 0.0153	0.0149 0.0157 0.0117 0.0129
	5	Sym 32 0.0152 0.0153	0.0147	0.0153	0.0162	0.0149	0.0162	0.0159	0.0135	0.0134
	6	Db 2	0.0151 0.0147	0.0152	0.0164	0.0156	0.0154	0.0153	0.0165	0.0141	0.0145
	7	Db 4	0.0162 0.0155	0.0158	0.0163	0.0155	0.0168	0.0172	0.0176	0.0152	0.0148
	8	Db 8	0.0161 0.0164	0.0167	0.0171	0.0166	0.0176	0.0175	0.0181	0.0164	0.0156
	9	Db 16	0.0182 0.0178	0.0169	0.0159	0.0184	0.0194	0.0154	0.0189	0.0172	0.0157
	10 Db 32	0.0193 0.0187	0.0184	0.0198	0.0193	0.0197	0.0156	0.0194	0.0184	0.0161
	11 Coif 1	0.0161 0.0165	0.0162	0.0169	0.0158	0.0168	0.0171	0.0178	0.0154	0.0166
	12 Coif 2	0.0144 0.0152	0.0154	0.0157	0.0152	0.0155	0.0169	0.0159	0.0147	0.0163
	13 Coif 3	0.0155 0.0153	0.0162	0.0162	0.0164	0.0167	0.0173	0.0175	0.0149	0.0159
	14 Coif 4	0.0145 0.0141	0.0144	0.0165	0.0150	0.0153	0.0156	0.0163	0.0137	0.0154
	15 Coif 5	0.0152 0.0159	0.0157	0.0164	0.0163	0.0166	0.0169	0.0168	0.0142	0.0156
	16 Haar	0.0198 0.0196	0.0214	0.0189	0.0221	0.0217	0.0198	0.0243	0.0197	0.0211
	17 Meyer	0.0151 0.0153	0.0164	0.0158	0.0168	0.0174	0.0175	0.0172	0.0156	0.0158
	average. The quantitative analysis with SNR and execu-
	tion time is reinforced by the MSE to prove the efficency
	of our process.

Acknowledgement

Authors would like to thank Hamamatsu Photonics for its technical support (TriPHEMOS) and the council of Burgundy for its financial support.


Ph.D Anthony Boscaro
email: anthony.boscaro@u-bourgogne.fr

Sabir Jacquir

Kevin Melendez

Kevin Sanchez

Philippe Perdu

Stéphane Binczak

Automatic process for time-frequency scan of VLSI

Introduction

In addition to light emission techniques, methods based on laser exploit optical stimulation or optical properties of reflected beam [START_REF] Jiann | Fault isolation in semiconductor product, process, physical and package failure analysis : Importance and overview[END_REF]. Electro Optical Probing is a popular timing-analysis laser-based technique, using Franz-Keldysh effects and free carrier absorption. Heinrich was the precursor of EOP approach [START_REF] Heinrich | Picosecond noninvasive optical detection of internal electrical signals in flip-chip-mounted silicon integrated circuits[END_REF] by proposing a noninvasive method which uses an infrared laser measuring the modulation of the free carrier density induced by the variation of electric potentials inside bipolar transistors. Since its introduction, Electro Optical Probing has become an essential tool to the failure analysis (FA) and design debug communities [START_REF] Kindereit | Fundamentals and Future Applications of Laser Voltage Probing[END_REF]. In backside EOP analysis, pulsed or continuous laser beam is focused on a node of the chip which has been thinned. Thereafter, the reflected beam properties are analyzed [START_REF] Harley | Method and means for optical detection of charge density modulation in a semiconductor[END_REF]. Intensity varies with temperature change [START_REF] Quintard | Réflectométrie et interférométrie laser haute résolution. Application à la caractérisation de composants électroniques[END_REF], charge density [START_REF] Paniccia | Optical probing of flip chip packaged microprocessors[END_REF] or electric field [START_REF] Heinrich | Measurement of real-time digital signals in a silicon bipolar junction transistor using a noninvasive optical probe[END_REF]. The analysis of the properties of the reflected laser beam can be traced back to its origin, in order to obtain information on the physical parameter studied. Two wavelengths have been used for EOP [START_REF] Kolachina | Introduction to Laser Voltage Probing (LVP) of Integrated Circuits[END_REF][START_REF] Soref | Electro-optical Effects in Silicones[END_REF] : 1064 and 1340 nm. The first one gives a better spatial resolution (shorter wavelength) and the laser beam absorption is sensitive to carrier density and to small bandgap variations. Two operation modes can be identified : Point mode, EOP or LVP (Laser Voltage Probing) (Probing on one node), or image mode EOFM (Electro Optical Frequency Mapping) also known as LVI (Laser Voltage Imaging) [START_REF] Perdu | Optical probing (EOFM/TRI) : a large set of complementary applications for ultimate VLSI[END_REF]. Each of them gives different kinds of information : temporal with EOP and frequency with EOFM. EOFM mode needs a preliminary choice of a specific frequency. A map, built point to point with standart EOP could take an incredible amount of time. In addition, it is difficult to compute a database with temporal and frequency information simultaneously. Previous research has already studied this problem. In [START_REF] Melendez | Fast 3D Electro-Optical Frequency Mapping and Probing in frequency[END_REF], a fast probing in frequency is applied and gives good results in terms of speed but post processing are required to recover the temporal waveform : user needs to determine Fourier coefficients on each pixel and compute the inverse fourier transform to re-build the temporal waveform. Recently, a method based on signal processing has been proposed in [START_REF] Vickers | Systems and methods for laser voltage imaging[END_REF]. In this case, the electrical signal is sent to an FPGA whose output act as a spectrum analyser with Fast Fourier Transform (FFT). Before this step, the temporal waveform is integrated by averaging. Once the FFT is computed, the frequency of interest can be found. But the FFT computing as a O(n 2 ) complexity (n being the number of samples), and it could be long for complex signals. In addition, the integration by averaging recquires an important number of waveforms.

In order to address these concerns, this paper introduces a new processing scheme based on EOP mode, Wavelet filtering and Autocorrelation function which has a low computing complexity (O(nlog(n))) [START_REF] Colberg | Highly accelerated simulations of glassy dynamics using GPUs : Caveats on limited floatingpoint precision[END_REF]. Our method is able to retrieve the temporal and frequency information simultaneously in a region of interest of the VLSI with just only one scanning. In a first time, the acquisition setup is described, detailing the two different laser modulation modes. The third section is dedicated to the signal improvement with Wavelets filtering and Autocorrelation function to determine its associated frequency. The fourth section, exhibits results of simultaneous acquisitions on different kind of technologies with asynchronous and synchronous mode. These modulation modes are discussed in the fifth section. Finally, concluding remarks are given in the last section.

Simultaneous acquisition description : setup

Acquisition setup

A complete and detailed description of the EOFM setup has already been given in [START_REF] Perdu | Optical probing (EOFM/TRI) : a large set of complementary applications for ultimate VLSI[END_REF]. Compared to the traditional approach, only two additionnal connections are needed between ATE (Automatic Test Equipment) and LSM. On ATE side X and Y positions are measured through two DPS (Digital Power Supply) channels in measure mode. X and Y connectors are used to follow the ramps coming from the LSM and giving the laser beam position. From the software side, two ATE functions measure and save the data. In addition, one post-processing tool is used to re-build the mapping. The acquisition setup is illustrated in Figure 1.

Laser modulation : synchronous vs asynchronous

An expert begins by choosing a Region of Interest (ROI) of size n × n pixels. He has the possibility to choose the ROI's size from 32 × 32 to 512 × 512 pixels. After this step two ways are open to modulate the laser :

In synchronous mode, an external generator synchronizes the laser beam with a trigger. This generator gives the modulation frequency : for example if the choosen frequency is 1.4Hz, the laser beam stays 0.7s on each pixel. The acquisition is sequential.

One other mode of acquisition can be also implemented : the asynchronous mode. In this mode the data are measured when the system of acquisition is ready and not sequentially pixel by pixel. This kind of acquisition is very interesting when the measure of interest is long to acquire. During this kind of acquisition, the laser scans the device faster than the time of acquisitions, the time of laser illumination for each pixel is shorter than the time required to get the measure of interest. Laser modulation is generally coupled with this kind of acquisition to avoid the illumination of the device under test during the measure and the transfer of the data. In that way, the image is randomly filled and a global view of device sensitivity can be observed with a partial filling of the pixel.

Signal improvement and frequency mapping

The process' flowchart is summarized in Figure 2. It is recalled that another variant of this procces has already been suggested in [START_REF] Chef | Frequency mapping in dynamic light emission with wavelet transform[END_REF] with the light emission. In order to understand the process, next part will describe in detail each step of the flowchart.

Wavelets filtering

EOP acquisitions are not directly workable because several factors impact on the noise. Integration by averaging is necessary to improve the signal's quality. In order to improve the signal to noise ratio (SNR), a filtering based on Wavelets has been proposed in [START_REF] Boscaro | Improvement of signal to noise ratio in electro optical probing technique by wavelets filtering[END_REF]. This process is based on Discret Wavelet Transform and coefficients thresholding. It enables using a weak number of averages and low laser power to recover the EOP signal. Thus, it reduces the invasive effect on the IC. Example of signal improvement is illustrated in this improvement, it is possible to determine the frequency of the EOP acquisition by using Autocorrelation function. This point is detailed in the next part.

Autocorrelation function

In signal processing, the Autoccorelation Function (AF) is a well known tool used to find periodicities in signal [START_REF] Rabiner | A comparative performance study of several pitch detection algorithms[END_REF] and is defined by the following equation :

Γ xx (τ ) = ∞ -∞ x(t)x * (t -τ )dt, (1)
where x(t) is the filtered signal, τ is the lag and x * (t-τ ) represents the conjugate complex of x(t -τ ).

It seems to be important to recall the impact of the filtering for the autocorrelation computing. In fact with a noisy signal, the AF could be corrupted. By consequences with a wavelets filtering, the signal is clearly denoised and the AF can be performed without errors. Figure 4 illustrates this aspect. Once the AF is performed, the periodicity can be computed by researching the second local maximum of the AF (see Figure 4c). Finally with this parameter, the signal's frequency can be deduced with the lag corresponding to the second local maximum, see [START_REF] Heinrich | Picosecond noninvasive optical detection of internal electrical signals in flip-chip-mounted silicon integrated circuits[END_REF].

f = 1/lag (2)
After this step, the operation is reiterate for all the image's pixels to obtain a frequency map with all the present frequencies in the ROI and their corresponding temporal waveforms. To re-build the map, (x,y) coordinates are retrieved for each laser position. By consequences each (x,y) position corresponds to a pixel of the frequency mapping. This new automatic scheme can be applied directly on the acquisition setup or in post-processing. In fact, experts can acquire temporal waveforms in a fist time, stock them in a file and apply the frequency map later.

Application and results

Synchronous mode

This part illustrates the process in synchonous mode applied on a 90 nm microcontroller STM32, more precisly on the digital to analog converter. The topographic image is reported in Figure 5 with a 32 × 32 pixels ROI. This is the case where several frequencies could be met. A zoom is realized to see each pixel of the ROI, see Figure 5b. After this step a frequency mapping using the new process is computed on this area whose outcome is represented by Figure 5c. On each pixel, the expert can see the associated frequency. Once the map is realized, he can choose a pixel in oder to see the associated denoised waveform, see Figure 5d. With this example, it can be noticed that all the pixels are filled, the map is complete in fifteen minutes.

Asynchronous mode

Here, the asynchronous mode was used on ALI LM124. As the previous example, the topographic image is reported in Figure 6a with a 32 × 32 pixels ROI. The result of the mapping is illustrated in Figure 6c. Giving the fact the total acquisition time is undetermined in this mode, the acquisition was stopped after 8 min. Immediately, we can see that all the pixels were not filled. By consequences, the map is incomplete. An example of waveform is also given in Figure 6d.

Discussion

This section deals with the robusteness of this new frequency mapping process and the choice between asynchronous or synchronous laser modulation. In a first time, the aim is to show the capability to detect any frequency in a 512x512 image. With this purpose in mind, synthesis images have created.

Synthesis and theoritical results

In order to have the best evaluation as possible, synthesis images have the same characteristics as real data. They have a size of 512 x 512 pixels as an EOFM image. In this matrix each pixel contains a noisy 1-D signal of 10000 samples such as the inital setup. Furthermore some pixels have the same signal in order to modelize Region of Interest working with the same frequency. Example of 3-D synthesis data of N xN pixels is illustrated in Figure 7a. By simulating this kind of image, all the characteristics are known (working areas positions, number of frequencies and areas sizes). Once the syntesis data performed, the new frequency mapping process is applied on each pixel of the matrix. Example of result on 512 pixels matrix is represented in Figure 7b. In this example, four different frequencies can be met. According to this result 100% of the frequencies are detected and all the temporal denoised waveforms are available. This result proves the efficiency of this new process. Now the question is what is the best way for modulating the laser ?

Laser modulation comparison

To compare characteristics of each mode, these are summarized in Table 1 and are discussed. 1, each mode has its benefits and drawbacks. The aim is to determine which mode is the most optimum for an expertise. The asynchronous mode allows to have a low acquisition time but as mentionned, some pixels are not filled and considering that the expert cannot control the modulation, he is not able to know the end of the acquisition. Consequently, even if the time per pixel is low, the entiere acquisition time could be long. Compared to this mode, the synchronous requires an external generator to modulate the laser. With this one, all the pixel are wandered. Thus, knowing the exact time per pixel, the expert could estimates the total acquisition time.

Execution Time : synchronous vs asynchronous

The acquisition time is a major factor to take into account to compare the two modulation modes. For different ROI sizes, acquition times are reported in Table 2.

In using this criterion, asynchronous mode is clearly the most interesting : for a full image in 512 by 512 pixels only 48 min are required compared to the synchronous mode where two days of acquisition are needful. To conclude this discussion part, these modulation modes present both benefits but also drawbacks. Indeed, the asynchronous mode

Conclusion and perspectives

In this paper, a new process to create a complete database (temporal and frequency) has been introduced. The aim is to draw a map where several working frequencies can be met with the corresponding temporal waveform. It is an automated process which requires only one acquisition to obtain both temporal and frequency information. It is based on a Filtering by Wavelets and Autocorrelation function. In terms of perspectives, this process opens the door to new multipoint probing applications : it is possible to improve the synchronous modulation mode by using the layout the IC. With this diagram, the expert knows the exact positions of the transistors and can only probe on them. This extension would allow to have a major gain of time.

Another extension for this mode is the incorporation of a top pixel signal to improve the SNR of the temporal waveform. This new extension can be automated by choosing a correct SNR and the laser remains on the pixel until the SNR is obtained. Once this step is finished, a top pixel signal is sent to pass to the next pixel. The operation is reiterated until the last pixel of the choosen ROI. This SNR improvement could gives good results concerning the temporal waveform and the frequency mapping but it may take a long time. This challenge could be resolved with high speed acquisition scope. Any frequency information could be extracted from EOP signal, not only the main one but also all the harmonics. It can be used for failure analysis (comparison with a golden device) or for reliability purpose (any difference before / after stress or comparison with simulated stressed device.

A technique currently being patented, improves the process using compressive sensing.

Figure 1 :

 1 Figure 1: Acquisition setup.

Figure 2 :

 2 Figure 2: Flowchart of the frequency mapping process.

Figure 3 .

 3 EOP signals are now more workable and transitions are more visible. Consequently with

Figure 3 :

 3 Figure 3: Probing (laser 1064 nm) on Digital/Analog converter STM32 : (a) One acquisition of EOP signal / Computing Time : ≈ 0.7 s / SNR = -19.96 dB. (b) Signal rebuilt with 10 averages / Computing Time : ≈ 7 s / SNR = 3.09 dB. (c) Signal rebuilt with 418 averages / Computing Time : ≈ 292 s / SNR = 37.39 dB. (d) Signal rebuilt with wavelets transform and 10 averages / Computing Time : ≈ 8 s / SNR = 22.9 dB.

Figure 4 :

 4 Figure 4: (a) Noisy signal acquired on PWM. (b) Signal (a) denoised with Wavelets filtering and its associated autocorrelation (c).

Figure 5 :Figure 6 :

 56 Figure 5: (a) Pattern of Digital/Analog converter (50X) STM 32 and 32 × 32 pixels ROI symbolized by the yellow area. Frequency : 100kHz / (b) Zoom on the ROI 32 × 32 pixels / (c) Frequency map on the ROI / (d) Waveform of the chosen pixel inside the ROI(Fig (c) red cross) / Laser 1064 nm.

Figure 7 :

 7 Figure 7: (a) Synthesis image modeling data with one temporal waveform per pixel. (b) Process result on 512 pixels synthesis image where four different working frequencies can be met : 200, 500, 1000 and 1200 Hz.

Table 1 :

 1 Benefits and drawbacks of each modulation mode.

		Asynchronous	Synchronous
	Benefits	-Acquisition time 10 ms/pixel	-All the pixels are filled
	Drawbacks	-Some pixels are not filled	-Acquisition time 0.7 s/pixel -Need of external generator
	As shown in Table

Table 2 :

 2 Comparision of acquition times between synchronous and asynchronous mode for different Region of Interest sizes.

	ROI size	Asynchronous	Synchronous
	(pixels)	10ms/pixel	0.7s/pixel
	32x32	10 s	12 min
	64x64	40 s	48 min
	128x128	3 min	32 min
	256x256	12 min	12 h
	512x512	48 min	48 h
	is clearly adapted for fast acquition but reveals problems
	in terms of robusteness. On the contrary, the synchronous
	mode is powerful for image reconstitution but not efficient
	in acquisition time. Experts have to find a compromise
	depending on its applicaton.

Acknowledgement

Authors would like to thank Hamamatsu Photonics for its technical support (TriPHEMOS) and the council of Burgundy for its financial support.