Eric Petit
email: epetit@irisa.fr

François Bodin
email: bodin@irisa.fr

Extracting Threads Using Traces for System on a Chip

This work addresses the early exploration phase, before the hardware is available, of the design of a System on a Chip. We detect threads in C programs using a software only technique. The computed threads are used as a basis for partitioning the applications. The threads are built using profiling and hot-paths information. We use a speculative model that, contrary to previous approaches, does not assume a shared memory. The speculation is performed on control flow and data structure layout. The output of the proposed method is a set of threads characterized by their execution time, the amount of memory and communication required, etc. Preliminary results show that the approach is able to capture and to characterize the main computation kernels of embedded applications.

Introduction

Most current embedded systems are System on a Chip that integrate multiple components with various memory and computation capabilities. The design of these SoC starts from partitioning the applications that are then mapped onto the computing units of the SoC. The partition process is very close to parallelizing the application; it extracts threads that are distributed on the computing units of the system. One difficulty that the SoC designer faces is to explore the partition possible space to find a tradeoff between performance and system cost. Speeding up the exploration requires to built new automatic tools that computes potential partitions and characterizes them qualitatively and quantitatively. To fully address SoC it is also imperative to deal with non shared memory space. Indeed, distributed memory is often chosen for SoC since shared memory implies more complex design, higher energy consumption and performance penalty.

In many cases, the input of the partition process is a sequential C program. Due to pointer aliasing issues, these programs are difficult to analyse statically. As a consequence, automatic parallelization techniques [START_REF] Zima | Supercompilers for parallel and vector computers[END_REF][START_REF] Allen | Optimizing Compilers for Modern Architectures[END_REF] cannot be used. In practice, the partitioning process is often performed by "hand". This strongly limits the exploration of the design space.

In this paper, we address the issue of detecting threads in C programs that can be used as a startpoint for the partitioning of embedded applications for SoC. Figure 1 illustrates the steps involved in the processing of a sequential application. This work focuses on the exploration phase. The exploration phase is divided in four main steps. The "potential thread detection" step computes the computation intensive phases. The "thread selection and code instrumentation step" selects parts of the code that can be implemented as threads. The code is then instrumented to measure, during the execution step, the communication and precise computation load of the candidate threads. The last step, according to execution results, evaluates the characteristics of the selected threads. A feedback loop helps to refine the selection. Threads considered during this phase are speculative since they are computed based on runtime data.

The implementation phase may be performed with the help of the user. The user can use as a starting point the threads built by the exploration phase. He/she basically has to remove the "speculation".

The proposed method based on run-time data is fully automatic and, contrary to previous works [START_REF] Oplinger | Enhancing software reliability with speculative threads[END_REF][START_REF] Lam | In Search of Speculative Thread-Level Parallelism[END_REF][START_REF] Patel | rePLay: A Hardware Framework for Dynamic Optimization[END_REF][START_REF] Chen | TEST: a tracer for extracting speculative threads[END_REF], consider distributed memory space. We show that the proposed process extracts "interesting" threads having low miss-speculation rate and a small ratio communication over computation.

The paper is organized as follow. In Section 2 we present the underlying assumptions on the target SoC architecture. Section 3 describes the speculative thread model used to evaluate the potential of a program partition solution. Section 4 gives an overview of the thread computation pipeline. Section 5 discusses the thread selection criteria. Section 6 reports the first experiments. In Section 7 we overview the related works. Finally, Section 8 concludes this paper.

Target Execution Model

The target architecture model is described in Figure 2. A main processor runs the application. A coprocessor, having it own local memory, is used to speedup the processing of some parts of the application. Typically, the main processor is a RISC micro-architecture [START_REF] Brash | The ARM Architecture Version 6 (ARMv6)[END_REF][START_REF] Sinharoy | Ibm power5 chip: A dual-core multithreaded processor[END_REF][START_REF] Marinissen | Test infrastructure design for the nexperia home platform pnx8550 system chip[END_REF] while the coprocessor can be a VLIW processor, an FPGA or any specialized computing unit such as a GPU [START_REF] Kilgariff | GPU Gems II[END_REF][START_REF] Marinissen | Test infrastructure design for the nexperia home platform pnx8550 system chip[END_REF][START_REF] Schreiber | PICO-NPA: High-Level Synthesis of Nonprogrammable Hardware Accelerators[END_REF].

A SoC implementing such configuration aims at exploiting each processing unit where it is the most efficient. Typically, the coprocessor runs intensive computation parts of an application.

Exploiting such a device is based on partitioning the application program in two parts and then inserting the communication and synchronization between the two programs. The partitioning must take into account the communication time as well as the type of computation to be performed on the coprocessor. For instance, if a GPU is targeted, it usually does not implement double precision floating point computation [START_REF] Kilgariff | GPU Gems II[END_REF]. Furthermore, if the coprocessor can be shutdown for energy saving, the time distribution of the thread activation on the coprocessor may be a criteria for selecting them.

Speculative Thread Model

To evaluate all the characteristics of the threads implies running efficiently many full tests on as many representative input data sets as possible. In the proposed approach, training data sets are used to compute the threads and an executable thread model is built to efficiently run the full tests. Since the threads are computed based on an execution, there is no warranty that the collected data are valid for all executions; speculation arizes at three levels:

1. At control flow level: A set of paths in the execution of the application program is assumed to be corresponding to the thread. If the execution of the thread leave the assumed set of paths, then the speculation fails. 2. At data dependency level: The data dependency between the threads and the main program must be preserved. In current study, this is not an issue since, as shown in Figure 3, we assume there is no overlap between the execution of the main program and the thread. 3. At data layout level: The data structures used in the application must be mapped in the local memory of the coprocessor. If a data access is made out of the speculated memory space the thread returns with an error code. This one of the key points of this study.

When the speculation fails the computation performed by the thread must be resumed on the main CPU. An example is shown in Figure 3. The thread is composed with basic blocks BB1', BB2', BB3' which are copies of BB1, BB2, BB3 in which the data accesses have been modified according the data mapping in the local memory (see Section 3.3). In the partitioned program, the basic block BB0 branches to a block that creates the thread, if all pre-conditions are satisfied, and copies the data in the coprocessor local memory. If the thread flow of control leaves the speculated path BB1', BB2', BB3', then the thread is stopped and the main program resumes the execution at original block BB1. This also happens if the thread code gets out of the data space it has been allocated. If the thread terminates normally, the non local modified data are copied back to the main memory.

In the remainder of this section we detail the main features of the speculative thread model. To construct the threads we must identify memory segments accessed in the program. First we define the program working sets then we present the abstraction used to describe the data accesses. In Section 3.3 we overview the memory mapping of the data structure in the threads.

Program Working Set Description

A memory block b is defined by a memory address and a size denoted by a pair (@,S). A block is created in the program whenever a new object is allocated.

To identify blocks in the program we use abstract memory set (AMS) that are defined by a program creation point, a content type and a free program point and a set of memory blocks. There is no overlap between memory blocks and a block can only belong to one AMS. This is a pre-condition to the thread launching. The set of blocks of an abstract memory set is updated during the program execution. The content type can be value or address or both.

For global variable, the program creation point is defined as the beginning of the main program, the free program point is the end of the program.

For dynamically allocated memory, the malloc statement is the program creation point if a unique free statement can be identified it is the free program point otherwise the end of the program is used.

For stack variables, the program creation point and a free program point are respectively the function entry and exit points for a given call site. The blocks corresponding to stack variables are also stacked in the abstract memory set.

For the thread construction, only set containing scalar values (i.e. no complex data structures) are considered. Examples are shown, in red, in Figure 4.

The set of abstract memory sets available at a program point during the execution defines a program working set. A abstract memory set which all memory blocks have been freed is removed from the program working set. An example is shown, in black, in Figure 4.

Memory Access Description

An access to memory, denoted (@,R|W, s), is defined by the address (@), the access mode (Read|Write), and the size of the element (s). An abstract reference (AR), for a program expression, is constructed using the real accesses (obtained by instrumentation of the source code). For each access the AMS and corresponding memory block is determined. According to the block, the minimum and maximum offsets are computed. There is a unique abstract reference for each memory access expression in the program. The abstract reference is defined by a tuple (id, {(abstract memory set, block, offset min, offset max, R|W) .... }) where the id is the identifier of the expression. Examples are shown, in blue, in Figure 4.

In the following, we assume that an abstract memory set has a unique memory block at a given time. This current restriction, as shown in Section 6, does not impact heavily for embedded applications which have limited used of dynamically allocated memory.

Thread Memory Mapping

Let assume that a set of basic blocks BB 1 , ..., BB n forms a thread. The memory elements used by the thread must be mapped onto the coprocessor unit. They are defined by the blocks corresponding to the AMS of the abstract references in BB 1 , ..., BB n for a given program execution. Each AMS is allocated in the coprocessor local memory. However, to avoid wasting memory and minimize memory copies, only the subset effectively accessed, given by the (offset min, offset max), of the blocks is allocated. If a thread performs a memory access outside the allocated memory then there is a miss speculation and the thread is aborted. Each abstract memory set, according to the references, is added to the input and/or output sets of the thread. The mapping function is a static function that associate to an abstract memory set an address, an offset and a memory size in coprocessor local memory. The local memory going to hold the data for the thread, the offset indicates the first element to copy from the AMS to the local object. The size is the amount of memory to copy (assuming the local space is large enough). It works as follow for abstract memory sets containing values:

Global Arrays/Scalars: A memory space corresponding to a subset of the global variable is allocated onto the coprocessor memory. Only the subset of elements really accessed by the abstract references are allocated. Local Arrays/Scalars: A corresponding variable is allocated. Dynamically allocated variables: For dynamically allocated variables, a local array is created in the coprocessor memory.

At run time a memory mapping table is filled. The entries of the table are statically computed. However the blocks associated with an abstract memory set are updated during the execution. Figure 6 shows an example of table.

The current scheme assumes all AMS by the thread are of type value. Otherwise it may imply multiple indirections accesses in the threads and that would require 5) and ( 6) are used to build a thread. Statements ( 3) and ( 4) were not executed during the training run. On the right, the data mapping for the thread.

to built a complex memory mapping. For instance, if a list is used by the thread, this would mean remapping all elements and change all pointers in the list data structures. Current scheme is not able to perform such a mapping. However, we do handle the case of scalar pointer variable which is a simple frequent case. This is detailed in the next paragraph.

Scalar Pointer Variable Case Pointer scalar variables are an important special case, that can be easily handle if the following restrictions in the thread code are respected:

1. The arithmetic on the pointers is limited to adding or substracting a constant value to the pointers.

No multiple indirection levels.

To implement an abstract memory set corresponding to a scalar pointer, a change in the address value is performed, so the indirect accessed in thread is translated in the thread memory space. Figure 8 shows an example of such mappings.

Thread Guarded Memory Access Once the thread coprocessor memory space has been created the memory accesses must be guarded to ensure that it only addresses the abstract memory set that has been allocated onto the coprocessor. Miss speculation can happened when there is an:

Out-of-Bound access: This happens when a memory access is done outside the allocated local memory segment. Bad access type: This happens when a read only abstract memory set is modified.

Figure 6 shows an example of guarded memory accesses. If the arrays A, B or C are not accessed within the predicted ranges defined by the abstract memory sets AM S 1 , AM S 2 or AM S 3 , the thread aborts its execution. This also ensure that there is no overflow of the coprocessor local memory. It should be noted here that the bound checking can easily be optimized in this case by moving the test outside the loop. The data speculation for expression idex 2 considers AM S 2 and AM S 3 which implies useless communications between the coprocessor and the main CPU. The calling context can be used to refine the speculation. This is the topic of next section.

Improving Speculation Accuracy Using History

To reduce the communication cost between the coprocessor and the main unit, it is important to distinguish the thread calling context. For such purpose we use a branch history mechanism. It is illustrated in Figure 7. In this example, the history helps distinguishing which data structures are used later in the program. To compute the history, branches are instrumented to build a vector that indicates the last executed statements. This instrumentation is used for computing the threads as well as when running the speculative threads. The history is limited in size and can be tuned for the applications. A too small history will induce more memory allocated on the coprocessor and more communication. A large history generate more execution overheads.

The abstract memory sets are sorted according to the history. The mapping function is also extended to take into account the history. In practice, this means there is one mapping table for each history value at the entry of the threads as shown in Figure 7.

Extracting The Speculative Threads

In this section we overview the successive steps to construct the speculative threads. One of the key point is to obtain a process with an acceptable complexity in terms of computation time and memory space. The approach must be scalable enough to handle large applications. Figure 8 shows the overall process used. It is divided in 7 steps: ),idex2 )); } Fig. 7. Use of the history to limit the data used on the coprocessor. In this case, B and C can share the same space in the coprocessor memory.

1. The first step computes the time consuming parts of the application using tools such as gprof. The complexity of this step is small. 2. The second step instruments the C source program to generate a trace of the execution. The size of the trace is limited by instrumenting only key basic blocks and using a compact trace format [START_REF] Pokam | An Offline Approach for Whole-Program Paths Analysis using Suffix Arrays[END_REF]. 3. The third step, based on previous trace, computes a set of hot paths that will be the basis for choosing the statement to execute on the coprocessor. The algorithm for computing the hot paths, has been proposed in [START_REF] Pokam | An Offline Approach for Whole-Program Paths Analysis using Suffix Arrays[END_REF] and is based on suffix arrays. It complexity is O(m log(n)) where m is the largest size of the thread and n the size of the trace. 4. Based on the computed hot paths, the memory accesses are instrumented to collect the abstract memory sets. For this step, the main cost is CPU time due to the instrumentation. The complexity is O(application code statements) since it is proportional to the number of AMS in the code. If, due to dynamic allocation, the number of memory blocks created, for a given AMS, is too large (i.e. greater than a given constant value), the blocks are collapsed in an abstract block that is a superset of the addresses accessed. 5. From the execution of the instrumented program, the fifth step collects all abstract memory sets and associates them to the memory accesses in the thread. The complexity of this step is also linear in the size of the program. 6. Finally according to the hot paths and the speculative memory layout, the thread is constructed. The complexity of this step is linear in the size of the threads.

All the steps have been implemented using our in-house version of Sage++ [START_REF] Gannon | Sage++: A class library for building Fortran and C++ restructuring tools[END_REF]. In the next Section we show how this process helps application designers to choose threads for a SoC.

Thread Selection

When threads have been identified many parameters may be analyzed. First the qualititative analysis may be performed for ensuring that the threads requirements are available on the coprocessor. The quantitative analysis measure on input data sets the running properties of the threads.

Qualititative Analysis

The qualitative analysis study the kind of computation performed by a thread. For instance, a coprocessor, may not provide floating point computation. This analysis may also be driven by the code generation mechanism available for the coprocessor. If the coprocessor is a GPU, a VLIW or an FPGA, the requirements will not be identical.

Quantitative Analysis

This analysis study the potential speedup the thread may provide and resources consumption for a given input data set. There is a set of overheads to take into account:

Thread initialization: It is the overhead link to start/end thread functions. In both case there is a fixed cost part due to fork/commit function. Communication: Because we assume distributed memory system, a subset of the working set has to be copied in the coprocessor local memory. At the end, if no miss speculation arizes, there is a write back to the CPU main memory. Miss-speculation: This overhead corresponds to restarting the original source code on the main CPU in case of miss-prediction of the thread. Branch history computation: This overhead is due to the history instrumentation of the code.

These overheads are computed based on a target coprocessor architecture that defines the potential gain. An execution time gain is obtained if the speedup provided by a coprocessor on a given thread is such that:

speedup > 1 1 -V C+SC

Texec

Where V C is the variable cost, SC is the static cost and T exec the thread execution time on the main processor. The V C is given by the communication time and the miss-speculation rate. The static cost corresponds to the time to start and exit the thread and the history computation.

The criteria related to the resources consumption are the following:

Code size: The code size is not directly available since it depends on the chosen coprocessor. Because we explicitly construct the code of the thread, it is possible to get an estimation of the amount of instruction memory space using a cross compiler. Data memory size: The thread extraction pipeline computes the amount of data memory needed on the coprocessor to execute the thread. Thread activation pattern: A thread is also characterized by its activation pattern. Because we are using traces, we can compute the delays between the activations of the thread. The delays, if large enough, may be used to turnoff the coprocessor to save energy or to allocate its computing power to another application.

Preliminary Experiments

In this section we present preliminary experiments. These experiments aims at checking that the proposed process can extract "interesting" threads having low miss-speculation rate and a small ratio communication versus computation. Furthermore, we want to check that the computed threads are robust to data input changes.

We use 12 small benchmarks from UTDSP [START_REF] Lee | UTDSP Benchmark. 15. Motorola. Powerstone Benchmark[END_REF] and Powerstone benchmarksuite [15]. Those programs are mainly composed of small multimedia applications that address image encoding, mpeg decoding, signal processing, etc.

Extracting the threads on a PC workstation was performed in the range of 1s to 10 minutes. To evaluate the thread characteristics we proceed as described in Figure 9. We use one execution to evaluate the miss-speculation rate. For this execution, the thread code is instrumented for checking control flow and data accesses as described in Section 3. A second execution is used to estimate the thread CPU time. For this, only the entry and exit points are lightly instrumented based on the processor cycle counter. Performing in two passes avoids time distortion due to instrumentation.

Figure 10 reports the thread coverage of the applications. This coverage is obtained using one up to 5 threads. In average 59,7 % of execution time are cover by threads. The average communication volume at the activation of the thread is 500 bytes. For all the applications the miss-speculation rate is small enough to be ignored.

As it can be seen in Figure 10, the applications exhibit three classes of behavior. The first class is composed by application where the threads cover more than 80% of the total execution time. The second one has a thread coverage in the range of 50% to 70% and the last class contains applications with a coverage inferior to 30%.

Tables 1, 2 and 3 reports detailed data for a representative example of each class. The reported communication time estimation is computed on a 3,00 GHz Pentium 4 architecture. The fixed cost of the considered memcpy C function call is 200 cycles, and the variable cost per byte of 0,6 cycle:

T comm = 2 * #Activations * (Comm. V olume * 0, 6 + 200) P rocessor F req in Hz
The factor 2 is due to the data copy at entry and exit point. Table 1 gives the results of experiments for jpeg from Powerstones. The total execution time coverage for jpeg threads is about 85% for 17,5% of the application Table 2 gives the experiment data for the Powerstones DES benchmark. This example allows us to easily modify the input data size to check the robustness of the computed threads. Experiments show that there is no impact, due to the input data changes, on the data layout speculation computed. This observation meets A. Djabelkhir and A. Seznec [START_REF] Djabelkhir | Characterization of embedded applications for decoupled processor architecture[END_REF] results on the behavior of embedded applications. However, we notice that the larger the data size is, the higher the thread 1 coverage is and the lower the thread 2 coverage is.

Table 3 presents the Powerstones adpcm benchmark. For this program, the average activation distance of the thread is very high. It would allow the system to shutdown the coprocessor between each usage. Table 3. Threads statistics for a poorly covered application.

Related Works

There are two main approaches for TLP. The first one requires a compiler intervention. The second one, is fully managed at hardware level. Due to hardware complexity, this second approach is usually limited to general purpose computing.

In the first approaches, the compiler is in charge of partitioning the application in threads. An hardware mechanism can then be used to deal with speculative data dependences or load balancing. This is for instance the case with the Expendable Split Window Paradigm [START_REF] Franklin | The expandable split window paradigm for exploiting fine-grain parallelsim[END_REF] and Multiscalar [START_REF] Gurindar | Multiscalar processors[END_REF]. These mechanisms are well suited for shared memory systems and require complex runtime hardware mechanisms. Other, more static, approaches, such as PICO-NPA [START_REF] Schreiber | PICO-NPA: High-Level Synthesis of Nonprogrammable Hardware Accelerators[END_REF], SPSM [START_REF] Pradeep | Single-program speculative multithreading (spsm) architecture: compiler-assisted finegrained multithreading[END_REF], SuperThread [START_REF] Tsai | Compiler techniques for the superthreaded architectures[END_REF] focus on loop parallelism without considering speculative execution. All data dependencies have to be resolved at compile-time, which limits the scope of these approaches for the exploration of application partitioning. A few works consider software only speculative thread parallelism [START_REF] Chen | TEST: a tracer for extracting speculative threads[END_REF][START_REF] Cintra | Toward efficient and robust software speculative parallelization on multiprocessors[END_REF]. In this later case, the software is also in charge of checking data dependences at run-time. Some speedup was reported in Cintra's work [START_REF] Cintra | Toward efficient and robust software speculative parallelization on multiprocessors[END_REF]. The implementation of the threads can be improved using helper threads. These threads provide speedup by helping the prefetching of data, checking data dependence on the side, or to compute synchronization [START_REF] Garcia Quinones | Mitosis compiler: an infrastructure for speculative threading based on pre-computation slices[END_REF][START_REF] Oplinger | Enhancing software reliability with speculative threads[END_REF][START_REF] Song | Design and implementation of a compiler framework for helper threading on multi-core processors[END_REF][START_REF] Song | Design and implementation of a compiler framework for helper threading on multi-core processors[END_REF][START_REF] Collins | Dynamic speculative precomputation[END_REF].

The second type of approaches proposed dynamic mechanism to detect and execute threads. No compiler intervention is needed. This is for instance the case for rePLay [START_REF] Patel | rePLay: A Hardware Framework for Dynamic Optimization[END_REF]. Hardware traces are used to compute speculative threads. If a thread is miss-speculated a hardware roll-back mechanism exploiting the underlying superscalar micro-architecture is used to restore a consistent state. Because of the hardware complexity of the approach, detected threads are usually limited in size. These approaches are not well suited for SoC especially with heterogeneous cores.

The approach proposed in this paper mainly focus on the partitioning at compiletime of the application while exploring the design space of a SoC. There is no hardware thread support assumptions.

Conclusion

In this paper we have presented a system able to automatically partition an application for an embedded system composed of a main CPU and a coprocessor. The system is based on speculative threads obtained from sequential C programs.

The proposed technique aims at helping the design exploration phase when decision must be made about which parts of the application to speedup using a coprocessor and what is the benefit and cost from such or such coprocessor. Preliminary experiments have shown that the speculative threads found are pertinent, and offer an interesting computation/communication ratio. Furthermore they are stable across data input sets.

Future work will focus on handling larger applications as well as integrating more static program analysis to reduce the amount of speculation. Reducing the amount of speculation will help the user to derive the effective implementation.

Fig. 1 .

 1 Fig. 1. Partition steps.

Fig. 2 .

 2 Fig. 2. Target Architecture Structure.

Fig. 3 .

 3 Fig. 3. Thread example.

Fig. 4 .

 4 Fig. 4. Abstraction example.

Fig. 5 .

 5 Fig. 5. Statements (5) and (6) are used to build a thread. Statements (3) and (4) were not executed during the training run. On the right, the data mapping for the thread.

Fig. 8 .

 8 Fig. 8. Thread Extraction Overview.

Fig. 9 .

 9 Fig. 9. Experimentation process

Fig. 10 .

 10 Fig. 10. Threads total coverage of execution time for all tested benches

  Guarded memory accesses. Integer scalar variables (i, m, n) are omitted from the table.

		Memory Mapping Table
	expression id	AMS	min offset max offset
	idex1	AM S1 = (A)	1	100
	idex2	AM S2 = (B)	2	101
		AM S3 = (C)	2	101
	Original code			Thread code
	int *pt, A[...], B[...], C[...];
	...
	n = 1;
	m = 100;
	... if (...) pt = B; else pt = C;	for(i=n; i<m;i++){ *((type of A) check(&(A[i]),idex1)) = * ((type of pt) check(&(pt[i+1]),idex2 )); }
	...
	for(i=n; i<m;i++){
	/*idex1*/A[i] = /*idex2*/pt[i+1];
	}
	Fig. 6.

Table 1 .

 1 Threads statistics for a highly covered application.C code. Thread 5 exhibits a large communication/execution time ratio indicating a poor potential benefit. Thread 1 is beneficial if the speedup provided by the coprocessor on the thread code is greater than 1.47. The other threads have an interesting very small communication/execution time ratio. Column Average Activation Distance gives the average time, in nano second, between two activations of the thread.

	jpeg	# Activations Execution Time Cover-	Code age (%)	Cover-	Comm. ume	Vol-	Tcomm Texec	Average Activation
			age (%)						Distance
									(nanosec.)
	Thread 0	600	40,97	12			504		0,02	42
	Thread 1	4800	5,66	0.5			128		0,30	43
	Thread 2	600	7,66	0.5			383		0,09	1300
	Thread 3	600	5,77	1			280		0,14	1300
	Thread 4	3180	9,46	2			17		0,12	438
	Thread 5	19228	15,19	1.5			17		1,02	86
	DES	# Activations Execution Time Cover-	Code age (%)	Cover-	Comm. ume (bytes) Vol-	Tcomm Texec	Average Activation
			age (%)						Distance
									(nanosec.)
	Thread 0	5577	32,68	8			159		0,16	2151
	Thread 1	5577	38,14	9			176		0,19	2355

Table 2 .

 2 Threads statistics for an average coverage of the application.


S Conforti
email: conforti@lal.in2p3.fr

Di Lorenzo

J E Campagne

F Dulucq

C De

La Taille

G Martin-Chassard

M El Berni

W Wei

PARISROC, a Photomultiplier Array Integrated Read Out Chip

PARISROC is a complete read out chip, in AMS SiGe 0.35 m technology [1], for photomultipliers array. It allows triggerless acquisition for next generation neutrino experiments and it belongs to an R&D program funded by the French national agency for research (ANR) called PMm2: "Innovative electronics for photodetectors array used in High Energy Physics and Astroparticles" [2] (ref.ANR-06-BLAN-0186

). The ASIC integrates 16 independent and auto triggered channels with variable gain and provides charge and time measurement by a Wilkinson ADC and a 24-bit Counter. The charge measurement should be performed from 1 up to 300 photo-electrons (p.e.) with a good linearity. The time measurement allowed to a coarse time with a 24-bit counter at 10 MHz and a fine time on a 100ns ramp to achieve a resolution of 1 ns. The ASIC sends out only the relevant data through network cables to the central data storage. This paper describes the front-end electronics ASIC called PARISROC.

I. INTRODUCTION

The PMm 2 project proposes to segment the large surface of photodetection [3] in macro pixel consisting of an array (2*2m) of 16 photomultipliers connected to an autonomous front-end electronics (Figure 1) and powered by a common High Voltage. These large detectors are used in next generation proton decay and neutrino experiment i.e. the post-SuperKamiokande detector as those that will take place in megaton size water Cerenkov or 100kt size liquid scintillator one. These news detectors will require very large surfaces of photo detection at a moderate cost. This R&D [2] involves three French laboratories (LAL Orsay, LAPP Annecy, IPN Orsay) and ULB Brussels for the DAQ.

LAL Orsay is in charge of the design and tests of the readout chip named PARISROC which stands for Photomultiplier ARrray Integrated in Si-Ge Read Out Chip. II. PARISROC ARCHITECURE.

A. Global architecture

The ASIC PARISROC (Figure 2) is composed of 16 analog channels managed by a common digital part. Each analog channel (Figure 3) is made of a voltage preamplifier with variable and adjustable gain. The variable gain is common for all channels and it can change thanks to the input variable capacitance on 3 bits. The gain is also tuneable channel by channel to adjust the input PMTs gain non homogeneity, thanks to the switched feedback capacitance on 8 bits. The preamplifier is followed by a slow channel for the charge measurement in parallel with a fast channel for the trigger output. The slow channel is made by a slow shaper followed by an analog memory with a depth of 2 to provide a linear charge measurement up to 50 pC; this charge is converted by a Wilkinson ADC (8,9 and 12 bits). One follower OTA is added to deliver an analog multiplexed charge measurement. The fast channel consists in a fast shaper followed by 2 low offset discriminators to auto-trig down to 50 fC. The thresholds are loaded by 2 internal 10-bit DACs common for the 16 channels and an individual 4-bit DAC for one discriminator. The 2 discriminator outputs are multiplexed to provide only 16 trigger outputs. Each output trigger is latched to hold the state of the response until the end of the clock cycle. It is also delayed to open the hold switch at the maximum of the slow shaper. An "OR" of the 16 trigger gives a 17th output. For each channel, a fine time measurement is made by an analog memory with depth of 2 which samples a 12-bit TDC ramp of 100 ns, common for all channels, at the same time of the charge. This time is then converted by the Wilkinson ADC. The two ADC discriminators have a common ramp, of 8/10/12 bits, as threshold to convert the charge and the fine time. In addition a bandgap bloc provides all voltage references.

B.

Digital part.

On overview of the digital part is given in figure 4. The digital bloc manages the track and hold system like a FIFO and starts and stops all the counters [4]. All the data are serialized to be sent out. There are two clocks: one at 40 MHz for the analog to digital conversion and for the track and hold management, the second at 10MHz for timestamp and readout.

The readout format is 52 bits: 4 bits for channel number + 24 bits for timestamp + 12 bits for charge conversion + 12 bits for fine time conversion. The readout is selective: only the hit channels are read; so the maximum readout time will be 100s if all channels are hit.

III. MEASUREMENTS AND SIMULATION.

A.

General tests.

A dedicated test board has been designed and realized for test the ASIC (Figure 5). Its aim is to allow the characterization of the chip and the communication between photomultipliers and ASIC. This is possible thanks to a dedicated Labview program that allows sending the ASIC configuration (slow control parameters, ASIC parameters, etc) and receiving the output bits via a USB cable connected to the test board. The Labview is developed by the LAL "Tests group".

1) Input signal.

A signal generator is used to create the input charge injected in the ASIC. The signal injected is similar, as possible, to the PMT signal. In Figure 6 is represented the generator input signal and its characteristics. The input signal, used in measurements and simulation, is a triangle signal with 5 ns rise and fall time and 5 ns of duration. This current signal is sent to an external resistor (50 Ohms) and varies from 0 to 5 mA in order to simulate a PMT charge from 0 to 50 pC which represents 0 to 300 p.e. when the PM gain is 10 6 . Figure 6: Input signal used for measurements and simulations.

2) Analog part tests. There is a good agreement between measurements and simulation in analog part results except for the noise values. To characterize the noise, the Signal to Noise Ratio (SNR) is calculated with reference to the MIP (1 p.e.). The noise differences are immediately evident: an additional low frequency noise is present in measurement (is now under investigation even if it is supposed to be tied to the power supply noise). A small difference has been noticed in measurement without the USB cable that allowed the communication between the test board and the Labwiev program: an rms noise value of 660V (0.132 p.e.) for preamplifier and so a SNR value of 8.

Another important characteristic is the linearity. The preamplifier linearity in function of variable feedback capacitor value with an input charge of 10 p.e. and with residuals from -2.5 to 1.35 % is represented on Figure 7. The gain adjustment linearity is good at 2% on 8 bits. In order to investigate the homogeneity among the whole chip, essential for a multichannel ASIC, for the different preamplifier gains is plotted the maximum voltage value for all channels. On Figure 9 is given the gain uniformity. A good dispersion of 0.5%, 1.4% and 1.2% have respectively been obtained for gain 8, 4 and 2. This represents a goal for the ASIC.



B. DAC Linearity

The DAC linearity has been measured and it consists in measuring the voltage DAC (Vdac) amplitude obtained for different DAC register values. Figure 10 gives the evolution of Vdac as a function of the register for the DAC and the residuals with values from -0.1% to 0.1%.

C. Trigger Output.

The trigger output behaviour was studied scanning the threshold for different injected charges. At first no charge was injected which corresponds to measure the fast shaper pedestal. The result is represented on Figure 11 for each channel. The 16 curves (called s-curves because of their shape) are superimposed that meaning good homogeneity. The spread is of one DAC count (LSB DAC=1.78 mV) equivalent to 0.06 p.e.

Figure 11: Pedestal S-Curves for channel 1 to 16.

The trigger efficiency was then measured for a fixed injected charge of 10 p.e. On Figure 12 are represented the Scurves obtained with 200 measurements of the trigger for all channels varying the threshold. The homogeneity is proved by a spread of 7 DAC units (0.4 p.e).

Figure 12: S-Curve for input of 10 p.e. for channel 1 to 16.

The trigger output is studied also by scanning the threshold for a fixed channel and changing the injected charge. Figure 13 shows the trigger efficiency versus the DAC unit with an injected charge from 0 to 300 p.e. and on Figure 14 is plotted the threshold versus the injected charge but only until 0.5 pC. In Figure 15 are plotted the 50% trigger efficiency values, extracted from the plot in Figure 14, converted in mV versus the injected charges. A noise of 10fC has been extrapolated. Therefore the threshold is limited to 10  noise due to the discriminator coupling.

D. ADC.

The ADC performance has been studied alone and with the whole chain.

Injecting to the ADC input directly DC voltages by the internal DAC (in order to have a voltage level as stable as possible) the ADC values for all channels have been measured. The measurement is repeated 10000 times for each channel and in the first panel of the Labview window (Figure 16) the minimal, maximal and mean values, over all acquisitions, for each channel are plotted. In the second panel there is the rms charge value versus channel number with a value in the range [0.5, 1] ADC unit. Finally the third panel shows an example of charge amplitude distribution for a single channel; a spread of 5 ADC counts is obtained.

Figure 16:

ADC measurements with DC input 1.45V.

The ADC is suited to a multichannel conversion so the uniformity and linearity are studied in order to characterize the ADC behaviour. On Figure 17 This plot shows the good ADC uniformity among the 16 channels. In Figure 18 is shown the 12-bit ADC linearity plots with the 25 measurements made at each input voltage level. The average ADC count value is plotted versus the input signal. The residuals from -1.5 to 0.9 ADC units for the 12-bit ADC; from -0.5 to 0.4 for the 10-bit ADC and from -0.5 to 0.5 for the 8-bit ADC prove the good ADC behavior in terms of Integral non linearity.

Figure 18: 12-bit ADC linearity.

Once the ADC performances have been tested separately, the measurements are performed on the complete chain. The results of the input signal auto triggered, held in the T&H and converted in the ADC are illustrated in Figure 19 where are plotted the 10-bit ADC counts in function of the variable input charge (up to 50 p.e). A nice linearity of 1.4% and a noise of 6 ADC units are obtained.

IV. CONCLUSION

Good overall performances of the chip PARISROC are obtained: auto trigger signal and digitalization of DATA. Good uniformity and linearity although strange noise performance due to 10 MHz clock noise and a low frequency noise under investigation. A second version of the chip will be submitted in November 09 with an increasing of the dynamic range thanks to 2 preamplifier gains: high gain and low gain; 8/9/10 bits ADC to reduce the p.e. loss below 1% level in case of 5 kHz dark current per PMT and a double fine TAC.

V. REFERENCES

Figure 1 :

 1 Figure 1: Principal of PMm2 proposal for megaton scale Cerenkov water tank.

Figure 2 :

 2 Figure 2: PARISROC global schematic.

Figure 3 :

 3 Figure 3: One channel schematic.

Figure 4 :

 4 Figure 4: Digital part overview.

Figure 5 :

 5 Figure 5: Test board.

Figure 7 :

 7 Figure 7: Preamplifier linearity vs feedback capacitor value.

Figure 8 Figure 8 :

 88 Figure 8 represents the slow shaper linearity for a time constant of 50 ns and a preamplifier gain of 8. The slow shaper output voltage in function of the input injected charge is plotted. Good linearity performances are obtained with residuals better than ± 1%.

Figure 9 :

 9 Figure 9: Gain uniformity for Gpa = 8, 4, 2.

  Figure 10: DAC linearity.

Figure 13 :

 13 Figure 13: Trigger efficiency vs DAC count up to 300 p.e.

Figure 14 :

 14 Figure 14: Trigger efficiency vs DAC count until 3 p.e.

Figure 15 :

 15 Figure 15:Threshold vs injected charge until 500 fC.

  is represented the ADC transfer function for the 10-bit ADC versus the input voltage level. All channels are represented and have plots superimposed.

  Figure 17: 10-bit ADC transfer function vs input charge.

  Figure 19: 10-bit ADC linearity.

  [1] http://asic.austriamicrosystems.com/ [2] http://pmm2.in2p3.fr/ [3] B. Genolini et al., PMm2: large photomultipliers and innovative electronics for next generation neutrino experiments, NDIP'08 conference. doi:10.1016/j.nima.2009.05.135. [4] F. Dulucq et al., Digital part of PARISROC: a photomultiplier array readout chip, TWEPP08 conference.

Table 1 :

 1 Table 1 lists the simulation and measurements results for the three main blocks of the analog part: Preamplifier, Slow shaper and Fast shaper. Analog part results.

		Preamplifier	Slow Shaper	Fast Shaper
		Gain PA=8	RC=50ns
		Meas. / Sim.	Meas. / Sim.	Meas. / Sim.
	Voltage	5mV/5.43mV	12mV/19mV	30mV/39mV
	(1 p.e.)
	rms noise/	1mV/468uV	4mV/2.3mV	2.5mV/2.4mV
	Noise p.e.	0.2/0.086	0.3/0.125	0.08/0.06
	(SNR)	5/12	3/8	12/16


Nguyen D H Hai

Lionel Schwartz

Nguyen Dang

Ho Hai

Realizing a complex of unstable modules

Realizing a complex of unstable modules

Introduction

Below H * X, resp. H * X, will denote the singular mod 2 cohomology, resp. homology, of a space or a spectra X. All spaces or spectra will be supposed to be 2-completed and to have finite mod 2 cohomology in each degree. Let A be the mod 2 Steenrod algebra and let U be the category of unstable A-modules.

Let L n be the Steinberg summand in the mod 2 cohomology H * B(Z/2) n , as defined by Mitchell and Priddy [START_REF] Mitchell | Stable splittings derived from the Steinberg module[END_REF]. Let also J(ℓ) be the ℓ-th Brown-Gitler module. These are both injective unstable A-modules as well as their tensor product L k ⊗ J(ℓ) following Lannes and Zarati [START_REF] Lannes | Sur les U-injectifs[END_REF].

The Brown-Gitler modules are the mod 2 cohomology of spectra, even of spaces if ℓ is odd. We will denote these spectra by T(ℓ). If ℓ is odd this is a suspension spectrum.

Let V n = (Z/2) n . Let us denote by L ′ n the unstable module which is obtained as follows. Let e n be the Steinberg idempotent in F 2 [GL n (F 2 )]. Let reg n : V n → O(2 n -1) be the regular reduced representation of V n over the field R.

Let reg

⊕k n = reg n + • • • + reg n , be the direct sum of k copies of this representation. Let BV g reg ⊕k n n
be the Thom space associated to reg ⊕k n , i.e. the Thom space of the vector bundle EV n × Vn R k(2 n -1) → BV n . The Steinberg idempotent determines a map of these Thom spaces after one suspension. Let us denote [START_REF] Takayasu | On stable summands of Thom spectra of B(Z/2) n associated to Steinberg modules[END_REF] by M(n) k the Thom spectrum e n • BV g reg ⊕k n n . In particular if k = 1 it is the spectrum L(n) of Mitchell and 1 Priddy, and we will simply denote it L ′ (n) if k = 2. We will denote by L n (as usual) and by L ′ n their mod 2 cohomology.

Let us now recall: [START_REF] Dang | La fonction génératrice de Minc et une "conjecture de Segal" pour certains spectres de Thom[END_REF][START_REF]Résolution de certains modules instables et fonction de partition de Minc[END_REF]) For all n ≥ 1 there exists an acyclic complex of unstable injective A-modules

Theorem 1.1 ([
0 → L ′ n → L n → L n-1 ⊗ J(1) → L n-2 ⊗ J(3) → • • • → L(1) ⊗ J(2 n-1 -1) → J(2 n -1) → 0. This complex is a minimal injective resolution of L ′ n .
Here is the main result of this article.

Theorem 1.2 The above complexes are realizable in the sense there exists a complex of spectra

T(2 n -1) -→ L(1) ∧ T(2 n-1 -1) -→ . . . -→ L(i) ∧ T(2 n-i -1) -→ . . . -→ L(n) -→ L ′ (n)
so that when applying mod 2 singular cohomolgy one gets the algebraic complexes. The composite of two successive maps is homotopically trivial, moreover all Toda brackets vanish.

The result follows from the following stronger result:

Theorem 1.3 There are cofibrations of spectra, 1 ≤ k ≤ n, C(k -1) -→ L(k) ∧ T(2 n-k -1) -→ C(k) so that
• The induced sequences in mod 2 cohomology are short exact;

• C(n) = L ′ (n); • C(0) = T(2 n -1).
Because of [START_REF] Dang | La fonction génératrice de Minc et une "conjecture de Segal" pour certains spectres de Thom[END_REF][START_REF]Résolution de certains modules instables et fonction de partition de Minc[END_REF], and further applications we are focused on the case of 1.2. However this theorem is quite general. The proof of the general case proceeds exactly as in the particular case. Thus, we will only state:

Theorem 1.4 Let M be the mod 2 cohomology of a spectrum X. Let us assume that M has an injective resolution of finite type in the category of unstable modules U. By finite type one means that any term in the injective resolution is a finite direct sum of indecomposable modules. Then this resolution can be realized topologically by spectra, in the sense described above as soon as the algebraic map from M to its injective hull in U can be realized.

The above theorems are in the category of spectra, however the spectra L(i)∧T(2 n-i -1) are suspension spectra if n > i. In Theorem 1.2 only L(n) and L ′ (n) are not. They are only direct summand of a suspension spectrum (after one suspension). It is thus reasonable to ask whether or not the complex of spectra can be realized as a complex of spaces (in an appropriate sense) after one suspension. The technology to do that is provided by the work of P. Goerss, J. Lannes and F. Morel [START_REF] Goerss | Vecteurs de Witt non commutatifs et représentabilité de l'homologie modulo p[END_REF]. However even if some preliminary computations are positive they are very technical in nature and we have not been able up to now to decide this question. Thus we only propose:

Conjecture 1.5 The preceding cofibrations in 1.2 can be realized as cofibrations of spaces, except for the last one that can be realized after one suspension and which is a retract of the suspension of a cofibration of spaces.

In the general case it does not look plausible to hope for such a result, at least it is necessary to require something on the map realizing the embedding in the injective hull. Next we mentioned applications of 1.2. It is clear that 1.3 leads to the construction of spectral sequences that we will consider either in a later version of this paper or in another one.

2 Spectra satisfying the Brown-Gitler property and related spectra

In this section we recollect some facts from [START_REF] Hunter | Characterizations of spectra with U-injective cohomology which satisfy the Brown-Gitler property[END_REF]. Most (but not all) of the material in this paper comes from earlier work, nicely collected here. Moreover we will need an original result of this paper. We shall say that a spectrum is space-like if it is a wedge summand of a suspension spectrum. For such a spectrum S the evaluation map Σ ∞ Ω ∞ S -→ S has a section and induces a monomorphism in cohomology.

Let now S be a spectrum whose mod 2 singular cohomology is an injective unstable A-module. Following N. Kuhn we shall say that S has the Brown-Gitler property if the natural map

f → f * , [S, X] -→ Hom U (H * X, H * S)
from homotopy classes from S to X to the set of maps of unstable modules Hom U (H * X, H * S) is onto for all space-like spectrum X.

Theorem 2.1 ( [START_REF] Hunter | Characterizations of spectra with U-injective cohomology which satisfy the Brown-Gitler property[END_REF]) Let S be a spectrum whose mod 2 cohomology is an injective unstable A-module. Then S satisfies the Brown-Gitler property if and only if either of the following condition holds:

• the evaluation map induces a monomorphism H * S -→ H * Σ ∞ Ω ∞ S in cohomology,
• the spectrum is space-like,

• there exists a space-like spectrum Z and a map f : S -→ Z which induces an epimorphism in cohomology.

It is clear that a spectrum satisfying the Brown-Gitler property is uniquely defined by its cohomology.

Recall that an unstable module M is reduced, if either it does not contain a non-trivial suspension, or if the map from M into itself, x ∈ M n , Sq 0 : x → Sq n x is injective.

Below are the main examples of interest for us of such spectra.

The Mitchell-Priddy spectra

The standard GL n (F 2 ) action on V n induces one on BV n , on the direct sum of all non-trivial line bundles over BV n , and on the direct sum of k copies of this vector bundle. Thus it acts also on their Thom spaces BV The cohomology of these spectra follows from the Thom isomorphism theorem:

H * M(n) k = ω k n e n F 2 [x 1 , • • • , x n ] = ω k-1 n L n
where ω n is the Euler class of the reduced regular representation reg n , or the top Dickson invariant of GL n (F 2 ): the product of all non-trivial linear forms in

F 2 [x 1 , • • • , x n ].
Theorem 2.2 (Takayasu [START_REF] Takayasu | On stable summands of Thom spectra of B(Z/2) n associated to Steinberg modules[END_REF]) For k ≥ 0, there exist a cofibration sequence

Σ k M(n -1) 2k+1 i n,k --→ M(n) k j n,k --→ M(n) k+1 .
This induces the following short exact sequence in cohomology:

0 → ω k n L n → ω k-1 n L n → Σ k ω 2k n-1 L n-1 → 0.
Splicing the cofibration sequences together yields:

Σ 2 n -1 M(0)2n → • • • → Σ 2 k -1 M(n -k) 2 k → Σ 2 k-1 -1 M(n -k + 1) 2 k-1 → • • • → ΣM(n -1)2 → M(n)1 → M(n)2.
3

The Brown-Gitler spectra

Let J(ℓ) the ℓ-th Brown-Gitler module (cf. [START_REF] Schwartz | Unstable modules over the Steenrod algebra and Sullivan's fixed point set conjecture[END_REF]Chapter 2]). It is characterised by the fact that there is a natural equivalence Hom U (M, J(ℓ)) ∼ = M ℓ * .

The unstable module J(ℓ) is the injective hull of Σ ℓ F 2 in the category U. It is known that there exist spectra T(ℓ) with mod 2 singular cohomology J(ℓ) [START_REF] Goerss | Vecteurs de Witt non commutatifs et représentabilité de l'homologie modulo p[END_REF]. This was originally proved by E. Brown et S. Gitler. If ℓ is odd T(ℓ) is a suspension spectrum. More precisely we have

Theorem 2.3 Let n > 2.
There exists a 1-connected pointed space T 1 (n) (that we are going to call the n-th Brown-Gitler space), unique up to homotopy, such that the following holds:

• There is an isomorphism of unstable modules

H * T 1 (n) ∼ = ΣJ(n).
• The induced map in cohomology by the evaluation

ΣΩT 1 (n) -→ T 1 (n) is a monomorphism. • T 1 (n) is 2-complete.
This space has moreover the following properties:

• It is retract of the suspension of a pointed space.

• For all pointed spaces Y the natural map

[T 1 (n), ΣY ] * -→ Hom U ( H * (ΣY ), ΣJ(n))
is surjective.

Thus the suspension spectrum of T 1 (n) is ΣT(n), and if n is odd T(n) is the suspension spectrum of the space T 1 (n -1).

These were the first known spectra to have the two first conditions of Theorem 2.1.

2.3

The Lannes-Zarati spectra [START_REF] Lannes | Sur les U-injectifs[END_REF] Theorem 2.4 The unstable module

L n ⊗ J(k) is an injective object in U.
This is just a particular case of the Lannes-Zarati theorem. This module is the reduced mod 2 cohomology of L(n) ∧ T(k). If k is odd this is the suspension spectrum of L(n) ∧ T 1 (k -1). This is because T 1 (k -1) has a co-H-space structure.

Proof of theorem 1.3

Let us recall some notations. The morphisms

f n-k,n : L k+1 ⊗ J(2 n-k-1 -1) -→ L k ⊗ J(2 n-k -1)
of the complex of Theorem 1.1 are defined in [START_REF] Dang | La fonction génératrice de Minc et une "conjecture de Segal" pour certains spectres de Thom[END_REF][START_REF]Résolution de certains modules instables et fonction de partition de Minc[END_REF]. Let us denote by C k the image of the map f n-k,n , which is also the kernel of f n-k+1,n . If the spectra C(k) exist one has H * C(k) ∼ = C k .

We are now going to proceed by descending induction. The first step of the proof is done by observing that the cofibration

C(n -1) -→ L(n) -→ C(n)
is nothing else than Takayasu's cofibration

ΣM(n -1) 3 -→ M(n) 1 → M(n) 2 .
However the right map is just the zero section, and the left hand spectrum could be defined as above.

We will assume that we have got a spectrum C(k -1), 2 ≤ k ≤ n, which is the fibre of a map from L(k) ∧ T(2 n-k -1) to C(k) and short exact sequences in cohomology

H * (C(k)) -→ H * (L(k) ∧ T(2 n-k -1)) -→ H * (C(k -1)).
We will make use of the following: Proposition 3.1 ( [START_REF] Hunter | Characterizations of spectra with U-injective cohomology which satisfy the Brown-Gitler property[END_REF]) Let X be a 0-connected spectrum such that H * X is of finite type and let Z be a space. Suppose there exists a map f : X -→ Σ ∞ Z which is an epimorphism in cohomology. Then the evaluation map Σ ∞ Ω ∞ X -→ X induces a monomorphism in cohomology.

One can apply this proposition to the spectrum C(k -1) and the suspension spectrum Σ ∞ Z of which

L(k) ∧ T(2 n-k -1) is a wedge summand. Thus the evaluation map Σ ∞ Ω ∞ C(k -1) -→ C(k -1) induces a monomorphism in cohomology: C k-1 ∼ = H * C(k -1) -→ H * Ω ∞ C(k -1). As a consequence, as L k ⊗J(2 n-k -1) is injective in U, the canonical map C k-1 -→ L k-1 ⊗J(2 n-k+1 -1)
extends to a map of unstable modules

H * Ω ∞ C(k -1) -→ L k-1 ⊗ J(2 n-k+1 -1).
It follows from 2.1 that this map is induced by a map of spectra

γ : L(k -1) ∧ T(2 n-k+1 -1) -→ Σ ∞ Ω ∞ C(k -1). Composing γ with the evaluation ǫ : Σ ∞ Ω ∞ C(k -1) -→ C(k -1) one gets a map ǫγ : L(k -1) ∧ T(2 n-k+1 -1) → C(k -1)
inducing in cohomology the canonical map C k-1 -→ L k-1 ⊗ J(2 n-k+1 -1). One takes the fibre C(k -2) of the map ǫγ to obtain a cofibration of spectra which induces a short exact sequence in cohomology.

The final step of the induction deserves care. One needs to show that the spectrum C(0) is indeed equivalent to T(2 n -1), a priori it has the right cohomology. By construction there is a map C(0) -→ L(1) ∧ T(2 n-1 -1) which induces an epimorphism in cohomology. As L(1) ∧ T(2 n-1 -1) is space-like, it follows from 2.1 that C(0) satisfies the Brown-Gitler property, thus C(0) ≃ T(2 n -1). Remark 3.2

1. One has a fibration of spaces:

Ω ∞ C(k -1) -→ Ω ∞ L(k -1) ∧ T(2 n-k+1 -1) -→ Ω ∞ C(k).
This is even a fibration of H-spaces which allows us to compute H * Ω ∞ C(k -1). In fact the Eilenberg-Moore spectral sequence shows that:

H * Ω ∞ C(k -1) ∼ = H * (Ω ∞ L(k -1) ∧ T(2 n-k+1 -1)) ⊗ H * Ω ∞ C(k) F 2 .
However we don't need this computation in the above proof, thus we don't describe (in terms of Dyer-Lashof operations) the result further.

2. The final step of the proof suggests it is possible to describe the space T 1 (2 n -2) as a sub-complex of (BZ/2) ∧n . We hope to be able to say more about that later.

.

  As a consequence the Steinberg idempotent e n[START_REF] Steinberg | Prime power representations of finite linear groups[END_REF] induces a stable map on BV g reg ⊕k n n , this map is defined after one suspension. Consider the telescope spectrum of this map[START_REF] Takayasu | On stable summands of Thom spectra of B(Z/2) n associated to Steinberg modules[END_REF], this is a stable summand of BV g reg ⊕k n n , denoted by e n • BV g reg ⊕k n n . Following Takayasu we will shorten e n • BV g reg ⊕k n n to M(n) k . In particular M(n) 0 = M(n), M(n) 1 = L(n) are the spectra of Michell and Priddy and by definition M(n) 2 = L ′ (n). The spectra M(n) and L(n) satisfy the Brown-Gitler property.


Michel Kieffer
email: kieffer@lss.supelec.fr

Distributed bounded-error parameter and state estimation in networks of sensors

This paper presents distributed bounded-error parameter and state estimation algorithms suited to measurement processing by a network of sensors. Contrary to centralized estimation, where all data are collected to a central processing unit, here, each data is processed locally by the sensor, the results are broadcasted to the network and taken into account by the other sensors. A first analysis of the conditions under which distributed and centralized estimation provide the same results has been presented. An application to the tracking of a moving source using a network of sensors measuring the strength of the signal emitted by the source is considered.

Introduction

A wireless sensor network (WSN) consists of spatially distributed autonomous devices equipped with sensors and interconnected via wireless links. Sensors may be designed for measuring pressure, temperature, sound, vibration, motion... Initially WSN were developed for military applications (battlefield surveillance). Now, many civilian applications (environment monitoring, home automation, traffic control) may take advantage of WSN, see, e.g., [START_REF] Kay | The design space of wireless sensor networks[END_REF][START_REF] Haenselmann | GFDL Wireless Sensor Network textbook[END_REF].

Applications suggest many research topics, such as the design of protocols for communication between sensors, localization problems, data compression and aggregation, security issues... All these problems are made more complicated by the constraints imposed on each node of the WSN, which usually has limited computing capabilities, communication capacity, and, to increase its autonomy, has strong power consumption constraints.

The application considered here is WSN for source tracking, which may be important when considering mobile phone localization and tracking, computer localization in an ad-hoc network, co-localisation in a team of robots, speaker localization... Figure 1 illustrates a typical localization problem: a source represented by a circle moves in a field of sensors, each of which is represented by a cross. The localization technique used depends on the type of information available to the sensor nodes. Time of arrival (TOA), time difference of arrival (TDOA) and angle of arrival (AOA) usually provide the best results [START_REF] Patwari | Locating the nodes[END_REF], however, these quantities are difficult to obtain, as they require a good synchronization between timers (for TOA), exchanges between sensors (for TDOA) or multiple antennas (for AOA). Contrary to TOA, TDOA or AOA data, readings of signal strength (RSS) at a given sensor are easily obtained, as they only require low-cost sensors or are already available, as in IEEE 802.11 wireless networks, where these data are provided by the MAC layer [START_REF] Sayed | Network-based wireless location[END_REF].

This paper focuses on source localization and tracking from RSS data. Centralized approaches (see Figure 2, left) have been proposed to solve this problem for acoustic sources [START_REF] Sheng | Maximum likelihood multiple-source localization using acoustic energy measurements with wireless sensor networks[END_REF] and for sources emitting electromagnetic waves, see, e.g., [START_REF] Kontkanen | Probabilistic methods for location estimation in wireless networks[END_REF][START_REF] Gustafsson | Mobile positioning using wireless networks[END_REF][START_REF] Gezici | Localization via ultra-wideband radios[END_REF]. In the first case, some knowledge of the decay rate of the RSS (path loss exponent) is needed for efficient nonlinear least squares estimation. In the second case, an off-line training phase is required to allow maximum a posteriori localization. In both cases, a good initial guess of the location of the source facilitates convergence to the global minimum of the cost function. Distributed approaches (see Figure 2, right) have also been employed, e.g., in [START_REF] Rabbat | Decentralized source localization and tracking[END_REF], where a distributed version of a nonlinear least squares solver has been presented. When badly initialized, it suffers from the same convergence problems as the centralized approach, as illustrated in [START_REF] Hero | Sensor network source localization via projection onto convex sets (POCS)[END_REF], which advocates projection on convex sets. Nevertheless, the latter requires an accurate knowledge of the source signal strength and of the path loss exponent. The localization and tracking problems are considered as distributed discretetime state estimation problems involving bounded state perturbations and measurement errors. This problem is addressed with the help of interval analysis [START_REF] Moore | Interval Analysis[END_REF][START_REF] Jaulin | Applied Interval Analysis[END_REF], which will provide at each node of the network and at each time instant a set estimate guaranteed to contain the true location of a moving source, provided that the hypotheses on the model and measurement noise are satisfied. Section 2 describes an idealized and a practical distributed state estimation algorithm able to deal with bounded-error measurements. Section 3 presents the application of the preceding algorithm to source localization and tracking.

Centralized Distributed

2 Distributed state estimation Consider a system described by a discrete-time state equation

x k = f k (x k-1 , w k , u k ) , (1)
where x k is the state vector of the model at time instant k (the sampling period is T ). The state perturbation vector w k accounts for unmodelled parts of the system and is assumed to remain in a known box [w]. The input vector u k is also assumed known. At k = 0, x 0 is only assumed to belong to some (possibly large) known set X 0 . Assume that at time k, each sensor = 1 . . . L of a WSN has access to a noisy measurement vector y k . The measurement process is described by the observation equations

y k = g k x k , v k , (2)
where v k is the measurement noise, assumed bounded in some known box [v]. Usual observation equations are

g k x k , v k = h k (x k ) + v k (3) or g k x k , v k = h k (x k ) • v k , (4)
depending on whether the measurement noise is additive or multiplicative.

Back to centralized discrete-time state estimation

Centralized state estimation is briefly summarized, since it constitutes the reference which distributed algorithms should reach. When all measurements at time k are available at a central processing unit, one gets

x k = f k (x k-1 , w k , u k ) , y k = g k (x k , v k ) , (5)
with

y T k = y 1 k T , . . . , y L k T and v T k = v 1 k T , . . . , v L k T . Determining
an estimate for x k from the measurement y , = 0 . . . k is a classical state

x 1 x 2 X k k -1| -1 x k-1 y 1 y 2 X k k | X k|k-1 y k k , V g k f k x k
Fig. 3. Idealized recursive bounded-error state estimator estimation problem, the solution of which depends on the linearity of ( 1) and ( 2) and on the noise model. For a gaussian noise, with linear state and observation equations, the Kalman filter [START_REF] Kalman | A new approach to linear filtering and prediction problems[END_REF] is the natural solution. When the model is non-linear, one may use an extended Kalman filter [START_REF] Gelb | Applied Optimal Estimation[END_REF], gridding techniques [START_REF] Terwiesch | A discretized non-linear state estimator for batch processes[END_REF], or particle filters [START_REF] Pitt | Filtering via simulation: Auxiliary particle filters[END_REF]. In a bounded-error context, with a linear model, the set of state vectors consistent with the model and noise on the measurements may be evaluated exactly using polytopes [START_REF] Schweppe | Recursive state estimation: unknown but bounded errors and system inputs[END_REF], or outer-approximated using ellipsoids [START_REF] Maksarov | State bounding with ellipsoidal set description of the uncertainty[END_REF]. With a nonlinear model, again, an outer-approximation of the state is possible using subpavings, i.e., unions of non-overlapping boxes [START_REF] Kieffer | Guaranteed recursive nonlinear state bounding using interval analysis[END_REF]. Summarizing the information available at time k, one gets

I k = X 0 , {[w j ]} k j=1 , {[v j ]} k j=1 , {[y j ]} k j=1 . (6)
Centralized bounded-error state estimation at time k aims at characterizing the set X k|k of all values of x k that are consistent with (1), (2), and I k . One may propose an idealized algorithm [START_REF] Kieffer | Guaranteed recursive nonlinear state bounding using interval analysis[END_REF], alternating, as the Kalman filter a prediction step involving (1)

X k|k-1 = f k (x, w, u k ) | x ∈ X k-1|k-1 , w ∈ [w] (7)
and a correction step accounting for the new measurement using (2)

X k|k = x ∈ X k|k-1 | y k = g k (x, v) , v ∈ [v] L . (8)
The two steps of the idealized algorithm are depicted in Figure 3. This idealized algorithm requires the evaluation of the direct image of a set by a function in the prediction step [START_REF] Gustafsson | Mobile positioning using wireless networks[END_REF] and the evaluation of the inverse image in the correction step [START_REF] Gezici | Localization via ultra-wideband radios[END_REF].

Usually, state estimation starts with an observability study to determine whether there is a chance to get an satisfying state estimate [START_REF] Kwakernaak | Linear Optimal Control System[END_REF][START_REF] Hermann | Nonlinear controllability and observability[END_REF]. With set estimators, this study is not required a priori. A lack of observability typically results in the increase of the size of the components of X k|k which are not observable. Alternatively, X k|k may also consist of several disconnected subsets. Lack of observability may thus be detected during the estimation process.

Distributed state estimation

Distributed versions of the Kalman filter have been proposed in [START_REF] Speyer | Computation and transmission requirements for a decentralized linearquadratic-gaussian control problem[END_REF], assuming linear models, gaussian noise, and instantaneous communications. Application to distributed estimation in power systems have been addressed in [START_REF] Lin | An efficient algorithm for solving distributed state estimator and laboratory implementation[END_REF] and to distributed estimation in WSN are considered in [START_REF] Ribeiro | SOI-KF: Distributed Kalman filtering with low-cost communications using the sign of innovations[END_REF]. Nevertheless, to the best of our knowledge, no similar tools have been proposed in a bounded-error context.

Consider a network of L sensors. Ideally, any sensor , = 1 . . . L of the WSN should provide

X k|k = X k|k . ( 9
)
To establish conditions under which ( 9) is satisfied, some notions of graph theory have to be recalled. For more details, the reader is referred to [START_REF] Harary | Graph Theory[END_REF][START_REF] Bollobás | Modern Graph Theory[END_REF]. The network of L sensors is represented by a graph G = (V, E). V is the set of L vertices of the graph, each vertex representing a sensor of the network and E is the set of edges of the graph. An edge {k, } ∈ E connecting two vertices k ∈ V and ∈ V indicates that the two corresponding sensors are able to directly exchange information; the graph is thus undirected. In what follows, it is assumed that G is entirely connected, i.e., that there is always a path from any vertex to any other vertex in G and that each vertex is connected to itself.

The distance between two vertices in G is the number of edges in a shortest path connecting them. Consider a vertex ∈ V, then

C ({ }) = {k ∈ V | (k, ) ∈ E} (10)
denotes the set of all vertices that are directly connected to , i.e., that are at a distance not larger than one of . More generally, for any W ⊂ V, C (W) ⊂ V is the set of all vertices which are at a distance not larger than one from a given vertex of W. The set

C (C ({ })) = C 2 ({ }) (11)
contains thus all vertices that are at a distance not larger than two of . More generally, C n ({ }) contains all vertices that are at a distance not larger than n of . The eccentricity ε of a vertex ∈ V is the largest distance between and any other vertex in G. Finally, the diameter d of G is the maximum eccentricity of any vertex in G.

Hypotheses and idealized algorithm. The following measurement processing and communication will be considered. At time k, each sensor processes its own measurement y k . Between time k and k + 1, a first round trip is considered (r = 1) in which each sensor broadcasts its own estimate X ,r k|k to all the sensors of the network (only those which are directly connected to receive the information). Then each sensor receives and processes X s,1 k|k , s ∈ C ({ }). Depending on the sampling time T , more round trips (r > 1) may be considered. Just before time k + 1, each sensor builds a final estimate X k|k . This way of processing and transmitting information leads to the following idealized distributed algorithm.

For each sensor = 1 . . . L, 1. At time k:

X k|k-1 = f k (x, w, u k ) | x ∈ X k-1|k-1 , w ∈ [w] . (12)
X ,0 k|k = x ∈ X k|k-1 | y k = g k (x, v) , v ∈ [v] . (13)
2. Between k and k + 1, for r = 1 to R max (number of round trips)

X ,r k|k = s∈C({ }) X s,,r-1 k|k (14)
3. Just before k + 1

X k|k = X ,Rmax k|k . ( 15
)
As for the centralized algorithm, the idealized distributed algorithm requires the evaluation of the direct and inverse images of a set by a function. Proposition 1 gives some conditions under which the distributed approach gives results similar to the centralized one.

Proposition 1. Consider a WSN of L nodes represented by an entirely connected graph G = (V, E) of diameter d. Assume that at time k -1, X k-1|k-1 = X k-1|k-1 for all ∈ V. If the number of roundtrips R max satisfies R max d, then one has at time k X k|k = X k|k [START_REF] Pitt | Filtering via simulation: Auxiliary particle filters[END_REF] for all ∈ V. ♦

Proof. Consider a vertex ∈ V. Since X k-1|k-1 = X k-1|k-1 , after the prediction step ( 12), X k|k-1 = X k|k-1 , where X k|k-1 is provided by [START_REF] Gustafsson | Mobile positioning using wireless networks[END_REF]. The first correction step done at involves only the measurement vector y k to get X ,0 k|k . After the first roundtrip, the estimate at becomes

X ,1 k|k = s∈C({ }) X s,0 k|k = s∈C({ }) x ∈ X s k|k-1 | y s k = g s k (x, v) , v ∈ [v] = s∈C({ }) x ∈ X k|k-1 | y s k = g s k (x, v) , v ∈ [v] = x ∈ X k|k-1 | y C({ }) k = g C({ }) k (x, v) , v ∈ [v] ,
where y

C({ }) k and g C({ }) k
(x, v) are the vector and function consisting of the concatenation of all y s k and g s k (x, v), with s ∈ C ({ }). After a second roundtrip, the estimate at becomes

X ,2 k|k = s∈C({ }) X s,1 k|k = s∈C({ }) x ∈ X k|k-1 | y C({s}) k = g C({s}) k (x, v) , v ∈ [v] = x ∈ X k|k-1 | y C(C({ })) k = g C(C({ })) k (x, v) , v ∈ [v] = x ∈ X k|k-1 | y C 2 ({ }) k = g C 2 ({ }) k (x, v) , v ∈ [v] .
Similarly, after R max roundtrips, one gets at

X ,Rmax k|k = x ∈ X k|k-1 | y C Rmax ({ }) k = g C Rmax ({ }) k (x, v) , v ∈ [v] .
It is now enough to show that C Rmax ({ }) = V in order to prove that X ,Rmax k|k = X k|k . First, one has C Rmax ({ }) ⊂ V. Assume now that there exists some k ∈ V such that k / ∈ C Rmax ({ }). This means that k lies at a distance strictly larger than R max from . Since the diameter d of G is lower than R max the distance between two vertices is necessarily lower than d, which contradicts the initial assumption. Thus any

k ∈ V satisfies k ∈ C Rmax ({ }) and C Rmax ({ }) = V.
The result of Proposition 1 is not very surprising. It mainly states that when there are enough information exchanges between sensors, the distributed estimate converges at any sensor to the centralized estimate. What is more interesting is that the number of roundtrips needed for convergence depends only on the diameter of the graph associated with the WSN.

When R max < d, the situation is much more complex, since not all sensors will have access to all measurements (or to their contribution to the estimation of x k ). For the first roundtrips at time k + 1, sensor will have to broadcast information about X ,r k+1|k+1 , but also about X ,r k|k , as long as X ,r k|k has not converged to X k|k . Again, the diameter of the graph plays a crucial role. Further analysis is still required.

Practical algorithm. The implementation of the proposed idealized algorithm is done in a way similar to that of the centralized algorithm presented in [START_REF] Kieffer | Guaranteed recursive nonlinear state bounding using interval analysis[END_REF]. In a most basic version of the algorithm, sets are represented by boxes, basic interval evaluations are performed for the prediction step and interval constraint propagation is done for the correction step. The advantage of this version is that it may readily be implemented on chips with reduced computational capabilities [START_REF] Piskorski | Efficient 16-bit floatingpoint interval processor for embedded systems and applications[END_REF]. A more sophisticated version could involve description of sets using subpavings, a prediction step implemented using ImageSp [START_REF] Kieffer | Guaranteed recursive nonlinear state bounding using interval analysis[END_REF] and Sivia [START_REF] Jaulin | Set inversion via interval analysis for nonlinear boundederror estimation[END_REF] combined with interval constraint propagation for the correction step.

Applications

For the application part, a static localization problem for a single source is considered first. Then, the source will be moving, and the localization problem is cast into a problem of state estimation.

Static source localization

The known location of the sensors is denoted by r ∈ R 2 , = 1 . . . L. The unknown location of the source is θ = (θ 1 , θ 2 ) T ∈ R 2 . The mean power P dB (d ) (in dBm) received by the -th sensor is described by Okumura-Hata model [START_REF] Okumura | Field strength ans its variability in VHF and UHF land-mobile radio service[END_REF]

P dB (d ) = P 0 -10n p log d d 0 , (17)
where n p is the path-loss exponent (unknown, but constant), d = |r -θ|. The received power is assumed to lie within some bounds

P dB (d) ∈ P 0 -10n p log d d 0 -e, P 0 -10n p log d d 0 + e , (18)
where e is assumed known. The RSS by sensor = 1 . . . L may be rewritten as

y = h (θ, A, n p ) v , (19) with h
(θ, A, n p ) = A |r -θ| np , A = 10 P0/10 d np 0 , (20)
and v ∈ [v] = 10 -e/10 , 10 e/10 . The noise is thus multiplicative in the normal domain. The parameter vector to be estimated is then x = (A, n p , θ 1 , θ 2 ) T .

Distributed approach: interval constraint propagation. At sensor , y ∈ [y ] is measured. Some boxes [θ], [A], and [n p ] are assumed to be available, a priori, or as results transmitted by the other sensors to sensor . The parameter vector has to satisfy the constraint provided by the RSS model

y - A |r -θ| np = 0. (21)
Using interval constraint propagation, it is possible to reduce the domains for the variables using [START_REF] Hermann | Nonlinear controllability and observability[END_REF]. The contracted domains may be written as

                           [y ] = [y ] ∩ [A] |r -[θ]| [np] , [A ] = [A] ∩ [y ] |r -[θ]| [np] , n p = [n p ] ∩ (log ([A ]) -log ([y ])) / log (|r -[θ]|) , [θ 1 ] = [θ 1 ] ∩ r ,1 ± ([A ] / [y ]) 2/[n p ] -(r ,2 -[θ 2 ]) 2 , [θ 2 ] = [θ 2 ] ∩ r ,2 ± ([A ] / [y ]) 2/[n p ] -(r ,1 -[θ 1 ]) 2 . ( 22
)
Unknown source amplitude Known source amplitude

µ 1 (m) µ 1 (m) µ 2 (m) µ 2 (m)
Fig. 5. Zoom of the projection of the solution on the (θ1, θ2)-plane Figures 4 and 5 provide typical solutions obtained using a centralized and distributed localization algorithm. The centralized algorithm involves set description using subpavings, whereas the distributed one only uses boxes, to limit the amount of information exchanged between sensors.

Figure 6 presents the histogram of the L 2 norm of the difference between θ * and its estimates ( θ CPA , θ D , and θ C ) provided by the three techniques previously described. The centralized approach performs better than the distributed one, but the distributed approach provides a reasonable estimate at a much lower computation and transmission cost. Both techniques outperform CPA, the performances of which do not depend on whether A is known.

Source tracking

In this part, the source is assumed to be moving. A and n p are now known. The state vector is taken as Interval constraint propagation. Interval constraint propagation is used at the correction step. From ( 21) and [START_REF] Ribeiro | SOI-KF: Distributed Kalman filtering with low-cost communications using the sign of innovations[END_REF], one gets the contracted domains at node

                                           y ,k = [y ,k ] ∩ A |r -[θ k ]| [np] , θ 1,k = [θ 1,k ] ∩ r ,1 ± A/ y ,k 2/np -(r ,2 -[θ 2,k ]) 2 , θ 2,k = [θ 2,k ] ∩ r ,2 ± A/ y ,k 2/np -(r ,1 -[θ 1,k ]) 2 . φ 1,k = [φ 1,k ] ∩   θ 1,k -θ 1,k T + T [w]   , φ 2,k = [φ 2,k ] ∩   θ 2,k -θ 2,k T + T [w]   . (25)
Each sensor will perform this constraint propagation before transmitting its updated estimate to its neighbours. 2 m•s -2 . Figure 7 illustrates the connectivity of the considered regular WSN and a typical trajectory followed by the source.

The simplest algorithm implementation presented in Section 2.2 has been considered: sets are represented by boxes, simple image evaluations using inclusion functions are performed and correction is done by interval constraint propagation. This limits the amount of information to be exchanged between sensors and the computational effort. The localization performance using this algorithm is depicted in Figure 8 for 100 realizations of the source trajectory. The average width of the solution box (left part of Figure 8) provided at each time instant decreases very quickly before reaching a floor slightly higher than the minimum width and increases again after about 18 s. At the beginning, the source is close to the middle of the field and many sensors participate to the localization. When the sensor moves near the limits of the field, the number of involved sensors decreses and as a result the localization accuracy worsens. This effect is even more important when the source moves outside the field. A similar behavior is seen for the average norm of the localization error taking the center of the solution boxes at each time instant as estimate. The convergence is quite fast and the number of round trips has only a very limited impact on the convergence of the algorithm.

Conclusions

In this paper, we have considered distributed bounded-error state estimation applied to the problem of source tracking with a network of wireless sensors. Estimation is performed in a distributed context, i.e., each sensor has only a limited amount of measurements available. A guaranteed set estimator is put at work. There is still large space for improvements in the considered problem. First, convergence properties have to be more carefully studied. In particular, more general conditions under which the distributed solution coincides with the centralized one have to be determined. This type of problem is partly addressed in [START_REF] Yokoo | Distributed Constraint Satisfaction: Foundations of Cooperation in Multi-Agent Systems[END_REF][START_REF] Bejar | Sensor networks and distributed CSP: Communication, computation and complexity[END_REF]. Robustness to outliers and network optimization for optimal estimation have also to be considered. Another challenging application would be the distributed estimation, e.g., in a team of robots.

Fig. 1 .

 1 Fig. 1. Source (o) and sensors (x )

Fig. 2 .

 2 Fig. 2. Centralized (left) and distributed (right) processing of measurements

Fig. 6 .

 6 Fig.6. Histograms of estimation error (in meters) for θ (100 realizations of the sensor field)

Fig. 7 .

 7 Fig. 7. Trajectory of the source (o); each sensor is represented by a cross (x), distances are in meters

Fig. 8 .

 8 Fig. 8. Width of the box [θ 1,k ] × [θ 2,k ], and norm of the localization error when the estimate is taken as the center of the solution box (average over 100 random paths followed by the source)

This work has been partly supported by the NoE NEWCOM++

Sensor 68 741 954 Measurement [9.303, 58.698] [17.856, 112.664] [18.644, 117.640] Table 1. Example of measurements (static localization)

Simulation results. A network of L = 2000 sensors randomly distributed over a field of 100 m×100 m is considered. The source is placed at θ * = (50 m, 50 m) and emits a wave with P 0 = 20 dBm, d 0 = 1 m. The path-loss exponent n p = 2 is assumed to be constant over the field. The measurement noise is such that e = 4 dBm. Table 1 provides some examples of the measurements which are available to the sensors. For 100 realizations of the sensor field, data have been simulated with (18). To limit computational load, only sensors such that y > 10 participate to localization. The initial search box for p is taken as [0, 100]×[0, 100]×[50, 200]× [START_REF] Haenselmann | GFDL Wireless Sensor Network textbook[END_REF][START_REF] Sayed | Network-based wireless location[END_REF] in a first scenario, where A (or P 0 ) is assumed unknown. In a second scenario, A is assumed perfectly known. For the distributed approach, five cycles in the sensor network are performed.

The two proposed techniques are compared to localization by a closest point approach (CPA), which searches for the index of the sensor with the largest RSS CPA = arg max y and uses the location of this sensor θ CPA = r CPA as an estimate for θ * . This technique, albeit it is not the most efficient [START_REF] Sheng | Maximum likelihood multiple-source localization using acoustic energy measurements with wireless sensor networks[END_REF], performs well for dense sensor networks, as here. Point estimates for θ * are evaluated as θ C = mid proj θ P , the midpoint of the smallest box containing the projection of P onto the θ-plane in the centralized approach and as the center of the projection onto the θ-plane of the solution box [p], θ D = mid(proj θ [p]), in the distributed approach.