Jean-Thomas Camino

Stéphane Mourgues

Christian Artigues

Laurent Houssin

A Greedy Approach Combined with Graph Coloring for Non-Uniform Beam Layouts Under Antenna Constraints in Multibeam Satellite Systems

Because of the ever-increasing traffic and quality demands for both internet and television, satellite systems must aim at designs that use the satellite resources in the most efficient way possible. In the case of multibeam satellite systems, this is achieved by making optimal use of the plurality of beams in terms of frequency reuse, power allocation, and quality of the layout. That last point is the one addressed in this paper, the optimisation of the beam layout being a complex but crucial task for the resulting telecommunication system since it directly affects its performances and cost. In the case of broadband systems, the key data is the repartition of the traffic demand over the zone to be covered which is never rigorously uniform. Though, it is common for satellite system design tools to rely on this fairly unrealistic assumption to provide regular coverage which is therefore often suboptimal : inappropriate beamwidths, overprovisioned or unsatisfied user stations, unprofitable beams. Nonetheless, one strong advantage of the regular scheme is that it is known to be compatible with the single feed per beam antenna constraint of minimum angular distance for all the couples of beams coming from the same reflector. The aim of this paper is to present a randomized multi-start heuristic to build a non-uniform layout, driven by the different telecommunication mission criteria and by the aforementioned antenna constraint that is dealt with by a graph recoloring procedure via local search and simulated annealing.

I. INTRODUCTION

The optimization of the design of multibeam satellite systems has received great attention in the past few years, the efficient exploitation of the resources becoming more and more determining to comply with a consistently growing need for better cost/bit ratios in satellite systems. Along with nonuniform frequency and power allocation that are not treated herein, one of the necessary steps for approaching the best possible profitability for the space segment is the optimization of the beam layout. Independently of these subsequent allocations, the performances and cost of a broadband satellite system are expected to differ notably from one beam layout to another according to how the heterogeneity of the traffic demand over the coverable region is handled. Indeed, an efficient algorithm should tend to a layout with an optimal number of beams and perfectly appropriate beamwidths and antenna gains (see Fig. 1 for a simple representation of the problem). This is the main flaw of the common technique that Fig. 1: Problem representation uses a single beamwidth and the hexagonal lattice to cover the entire region (Fig. 2). That pattern is known to maximize the density of circle packing (see [START_REF] Chang | A Simple Proof of Thue's Theorem on Circle Packing[END_REF] for instance), but it would only be optimal for a traffic demand perfectly homogeneous in space and in intensity. On the other hand, technological feasibility has been proven for these layouts for a spacecraft equipped with 3 or 4 reflectors which is a strong enough reason to continue to rely on them regularly. Under the assumption adopted throughout this study that single feed per beam (SFB) antennas are used, the main technological constraint is that for each layout considered there must exist a mapping of the beams to the different reflector antennas for which the feeds do not overlap in the corresponding blocks of sources. In other words, an acceptable beam layout has corresponding source layouts that are feasible. This leads to a minimum angular distance from the satellite point of view between two beams associated to the same reflector antenna, that distance being a function of the size of the sources and therefore of the beamwidths at stake.

In the end, the real challenge here for any algorithmic procedure is to pertinently choose the beamwidths according to the density of the traffic demands, to place the beam centres with an antenna gain criterion while ensuring that the antenna constraint described above can be satisfied with an appropriate reflector to beam allocation. To that end, this paper aims at proposing a mathematical model for this constrained optimization problem, and a first algorithmic solution based on a randomized greedy approach to place the beams and graph coloring for the mapping between beams and reflectors. Concerning the interpretation of the traffic demand density to determine the beam diameters to use, the authors of [START_REF] Angeletti | Non-regular Multibeam Coverage Payloads for Non-Uniform Traffic Demand[END_REF] suggest to aim at a load-balanced distribution of these demands within the different beams through an adjustment of their widths, the main idea being that imbalances of traffic demands inside the beams can lead to user stations being in the end either overloaded or underloaded in terms of offered capacity. The method proposed uses a partitionning of the region into evenly loaded polygonal subparts, each one of these being then treated individually to determine what beamwidth should be used in it and where the corresponding beam should be placed through an analysis of its shape and surface, thus defining the full layout. In that work, the question of the mapping of the beams to the antenna reflectors is not addressed. Furthermore, in [START_REF] Kyrgiazos | Irregular beam sizes and non-uniform bandwidth allocation in HTS multibeam satellite systems[END_REF] the authors observed that a drawback of this last method is that several zones remain uncovered or poorly covered. To overcome this issue, artificial neural networks are used and more precisely self-organizing maps that treat all the traffic demands in order to define sub-areas, each sub-area corresponding to one of the available beamwidths. The reasoning behind this method is that using narrow beams on the densest zone is a way to increase the antenna gains and the frequency reuse where it is the most needed, while using larger beams in the least dense areas can be sufficient to reach compliance. Beams are then placed in each sub-area in such a way as to minimize the uncovered areas, the regular lattice being used locally. Once the beams are placed over the service zone, the authors tackle the issue of the antenna configuration with a reflector allocation to the beams that includes a maximization of the angular distances between the beams coming from the same antenna, that NP-hard problem being solved heuristically. But the major drawback of treating the placement of the beams and their allocation to the antenna reflectors sequentially is that one is very likely to discover that, with a layout built regardless of the antenna constraint, even the optimal mapping of the beams to the reflectors that maximizes the minimum angular distance between each couple of beams belonging to the same reflector can turn out to be technologically infeasible with SFB antennas. In that case, forcing such an implementation would require to use smaller sources than advised thus leading to a deterioration of the antenna performances through spill-over losses and important side lobes.

For the work presented here, particular attention has been paid to feasibility through a SFB technology and therefore to the satisfaction of these antenna constraints (see III for details) which are taken into account dynamically in the layout building procedure. Concerning the choice of the beamwidths, the idea of [START_REF] Kyrgiazos | Irregular beam sizes and non-uniform bandwidth allocation in HTS multibeam satellite systems[END_REF] of treating the input traffic demands is revisited but adapted to the mathematical model described further in the article. In practice, statistical discretization is operated on a set of data representing the density of traffic in the neighborhood of each possible centre for the beams to define in advance the beamwidths to use on these positions : narrow beams where the demand is dense, larger beams elsewhere. Guided by the combinatorial model of the problem, a heuristic procedure combining a randomized multi-start greedy approach and graph coloring is applied to find jointly interesting positions for the beams and an acceptable beam mapping to the reflectors with the additional constraint that the number of beams can be bounded.

III. THE ANTENNA CONSTRAINT

When designing a layout with single feed per beam antennas, the angular distance between two beam centres of two beams generated by the same reflector cannot be lower than a value determined by the size of the two corresponding feeds. Indeed, having close beam centres implies having close corresponding sources in the block of sources of the reflector in question. When two sources of two given sizes become tangent, the minimum possible distance between the two horn centres is reached, situation that leads through the reflection by the parabola to the minimum angular distance between the two emitted beams. This optical property is known under the name "beam deviation" and has led to the definition of the "beam deviation factor", denoted here by Γ. The simple offset reflector system presented in Fig. 3 illustrates the phenomenon.

Here is some notation used in the equations that follow : Furthermore, since Fs D > 1, 5 in satellite architectures, the approximation Γ ≈ 1 is known to be legitimate which leads to the following formula for the angular deviation :

∆ θ = arctan ∆ i,j F s
The next step would be to derive ∆ i,j according to the widths of the beams i and j, which is not done here. On that regard, the important property is that using larger beamwidths requires larger sources to concentrate the illumination on a reduced reflector surface, which leads to greater minimum inter-sources distances. Finally, note that since the problem is solved with a finite number of possible beamwidths fixed in advance, all the minimum angular separation values can be computed in preprocessing.

IV. THE PROBLEM MODEL USED

A. Input data

As already discussed, in broadband satellites the telecommunication mission is defined by the traffic requests over the geographic area treated. The corresponding users are aggregated in what will be called stations to be in the end represented by a reasonably large number of points at the surface of the Earth. Each station can be identified for instance with its true view angles (θ x , θ y ) ∈ Θ x × Θ y . One can therefore define a discrete and finite set S ⊂ Θ x × Θ y that contains all these station coordinates. We can then define a function T as follows : The choice of the set of potential beam centres is of high importance since it determines the type of optimization procedures that will be usable. The main choice is whether to use a discrete or a continuous set. As discussed in the last paragraph, the nature of the traffic demands which are represented by a finite number of stations on the Earth's surface is the source of two determining properties for any function that returns a value linked to the overall traffic demand inside the coverable region : it is non-differentiable in most cases and always non-convex. The discontinuity property is what makes it impossible to rely on all the non-linear optimization techniques and the convexity would have been needed to use convex optimization methods that can deal with such non-differentiable objective functions. Smoothing the objective function with an accurate model of antenna gains could solve the non-differentiability, but then one would have to treat a highly multi-dimensionnal continuous problem. In the end, the choice of the discretization of the beam centres set was probably the most appropriate one. To do so, the idea is to analyze the S set of all the (θ x , θ y ) station coordinates in order to define a meshing area. To do so, a margin is taken on the boundary of that set and a uniform grid is generated with two tunable space steps in the θ x and θ y directions. Let C ⊂ Θ x × Θ y be the discrete and finite resulting set of potential centres for the beams that will be used throughout this study.

T : S → R + s → T (s) =

C. Combinatorial model

Because of this discretization of the possible positions for the beams (corresponding set denoted by C), along with the finite number of reflectors and beamwidths (corresponding sets R and W respectively), the problem belongs to the class of combinatorial optimization problems. A modelling phase lead to a representation where each possible position for the beam centres is seen as a vertex of a graph in which there is an edge between each couple of vertices considered to be too close to be the two centres of two beams assigned to the same antenna reflector. On that matter, note that the beamwidths to use in each centre and therefore the minimum angular distances to be satisfied are preprocessed (see V) for all the couple of beams. Let k be the number of available reflector antennas on the satellite, each one of them can be seen as a different "color" in the graph terminology. Then, extracting from the graph of the possible positions for the beams a subgraph legally colored with k colors (assignment of colors to the vertices in such a way that no adjacent vertices use the same color) is equivalent to finding an acceptable layout with respect to the antenna constraints. Note that the cardinality of this subgraph is also limited by the number maximum of beams than can be used. Then, one has to define an objective function that can be computed for each acceptable set of beam positions to define the optimization problem as follows : find the k-colorable subgraph that is optimal according to the telecommunication criteria. On that regard, many different approaches can be considered, ours being detailed in IV-D. Whatever the objective function, Fig. 4 provides a visual representation of the decision variables, of the constraints, and of the criteria. There is not, to our knowledge, literature that directly addresses a problem strictly similar to the one described in this article. The closest we could find were the k-centre problem [START_REF] Brandenberg | New Algorithms for k-center and Extensions[END_REF] and the max k-cut problem [START_REF] Coja-Oghlan | MAX k-cut and Approximating the Chromatic Number of Random Graphs[END_REF]. The former tries to find locations among a finite number of possibilities for a limited number of warehouses with an objective linked to the distances to the cities they have to serve. The warehouses can be seen as the equivalent of our beams, but their positions do not have to satisfy any kind of separation constraint comparable to the antenna constraint.

Concerning the k-cut problem, the goal is to partition the set of vertices of a given graph in such a way that a maximum number of edges are cut i.e. with corresponding vertices that belong to two different subsets of the partition. The main flaw of this approach for our problem is that the resulting coloring is not legal i.e. adjacent vertices might use the same color and therefore one would have to treat each output to reach an acceptable set of beams according to the antenna constraint, so that option is not entirely satisfactory. In the end, it has been chosen to turn to an ad hoc heuristic described and analyzed in the remainder of the article.

D. Objective function considered

The role of the objective function is to translate the needs into a real-valued function whose minimization (it could have been a maximization) brings us closer to their satisfaction. The variables of that function are all the system parameters that have to be optimally determined. More precisely, with n max ∈ N the maximum number of usable beams ∀i ∈ 1, n max , c i ∈ C the position of the centre of the i th beam ∀i ∈ 1, n max , w i ∈ W the beamwidth of the i th beam ∀i ∈ 1, n max , r i ∈ R the index of the reflector from which is generated the i th beam (only involved in the constraints, not the cost function) ∀i ∈ 1, n max , b i ∈ B = {0, 1} the boolean variable that indicates whether the i th beam is actually used or not we can define the global variable of our problem as follows:

X =                c 1 w 1 r 1 b 1 c 2 . . . c nmax w nmax r nmax b nmax                ∈ (C × W × R × B) nmax
As it has been already said before, choices on the criteria to consider had to be made to address the problem. Here is the list of the properties sought for the minimized functional, followed by details on their relevance :

1) A functional that decreases when the traffic demands inside the beams increase.

2) A functional that is additive with respect to the different beams, i.e. that computes a certain value for each beam (linked to the traffic demand inside the beam) and sums them all up.

3) A functional in which the impact of the traffic of a given station in a beam decreases with the distance of that station to the beam centre.

4)

A functional in which stations that are covered by more than one beam at the same time only contribute to the overall traffic demand (and thus to the corresponding functional decrement) of one of these beams.

The first property is the most obvious one since it is what will directly lead to a maximization of the traffic coverable by the beam layout. An additive functional leaves the door open to easy implementations of greedy type algorithms on which interesting literature has been found (see [START_REF] Keil | Greedy and Other Efficient Optimization Algorithms[END_REF] and [START_REF] Marti | Multi-start Methods for Combinatorial Optimization[END_REF]).

The reduced impact of the stations far from their beam centre is a way to take into consideration the decrease of capacity resulting from the loss of antenna gain. The last criterion used is probably the most questionable one : it presupposes that the traffic demand of a station cannot be dealt with by more than one beam. Therefore, potentially interesting overlapping situations are not handled in that first approach and some station requests might remain partially unsatisfied for that reason. But this property for the functional is necessary to avoid an agglomeration of all the beams in the densest area with a greedy approach. Therefore, for a station covered by more than one beam, the choice here has been to affect the corresponding traffic to the lowest-indexed of these beams (which is adapted to any heuristic that treats the variables in the order defined by the index i ∈ 1, n max , the greedy type algorithms being good compatible examples once again). To explicitly include this choice in the functional expression, let us denote for all i ∈ 1, n max :

S i = s ∈ S | s -c i 2 < w i 2 ∧ ∀j < i, s -c j 2 ≥ w j 2
Therefore, to be in S i , a station must be in the zone covered by the i th beam, but not in any of the zones covered by the beams whose indices are less than i. Since it has been chosen to minimize a functional, one last notation is needed. Thus, let

T = s∈S T (s)
be the total traffic request over the studied area. Finally, let

F : (C × W × R × B) nmax -→ R +
be the minimized objective function, defined as follows for all

X ∈ (C × W × R × B) nmax : F(X) = 1 T nmax i=1 T -b i s∈Si T (s) 1 -2 s -c i w i
In F, the traffic coverable by each beam is computed, with a first linear model of attenuation of the contribution of the stations far from the center. The global traffic T is used for two reasons : to transform the maximization of the traffic into a minimization problem, and to make sure that only positive values are computed and summed up. One can notice that the more active beams (i.e. b i = 1 for many i), the lower the functional, but the constraints will be limiting on that regard.

V. PREPROCESSING FOR THE BEAMWIDTHS

Let us remind that the width of the beams is an important parameter to determine to use efficiently the satellite resources. Indeed, using narrow beams in high traffic demand zones results in interesting antenna gains and frequency reuse schemes that are needed to comply with the capacity requests. Larger beams are expected to offer satisfying traffic in less dense zones. Therefore, the challenge is to be able to pertinently fit the repartition of traffic demand over the treated zone. The goal is to divide the entire region into subareas, each one corresponding to a possible beamwidths, that information being used afterwards when the beams are placed. Thus, we are following the idea of the authors of [START_REF] Kyrgiazos | Irregular beam sizes and non-uniform bandwidth allocation in HTS multibeam satellite systems[END_REF] but with the difference that the data sorting is applied to all the possible positions for the beam centres that are weighted according to the demand density in their vicinity, and not on the demanding user stations themselves. Furthermore, instead of turning to neural network, simple statistical discretization has been selected for its ease of implementation and its satisfying results. This technique that is often used by statisticians to create population density maps consists in partitioning the set of encountered density values into as many intervals as there are categories available for the data sorting, each subset of values being associated to one of these. In our case for instance, the lowest values of density will be associated to the largest beams. Concerning the size of the intervals, two techniques were examined :

-regular discretization : same size for all the intervals of the partition.

-arithmetic discretization : these sizes follow an arithmetic progression.

Given that the highest traffic demands are often concentrated in small areas, we often have to deal with a distribution of density values that is skewed to the right, so the arithmetic approach is a better fit in that case to reach a more or less balanced repartition of the different beam diameters over the zone. Yet, to make this directly usable, we had to compute a value representative of the density in the vicinity of every possible position for the beam centres. That is the role of the density function D : C → R + defined as follows for all the possible centres c ∈ C, where ω max is the largest beamwidth envisaged and D c = {s ∈ S| s -c < 1 2 ω max } is the set of user stations in a beam of diameter ω max placed in c :

D(c) = 4 πω 2 max s∈Dc T (s) 1 -2 s -c ω max
In the end, D has the following interesting properties :

-when the traffic demand is high in the vicinity of a given centre, D is also high. These high values can be due to a multiplicity of stations of low demands or to a few high demanding stations.

-when a demanding station is far from the centre, its influence on the density computed is smaller. This property was needed to choose adapted diameters, since without it, one could have to place narrow beams on centres considered as dense only because of stations on the periphery of the 1 2 ω max radius disk, none of which being actually coverable by such small beams.

The results presented all along this article have been obtained on a realistic but fictitious broadband scenario over Africa. In Fig. 5, this statistical discretization has been applied on Africa and Eastern Africa with respectively 2 and 4 available beamwidths. Let us remind that building algorithmically a layout implies solving jointly the following subproblems :

-The choice in advance of the beamwidths to use on each potential position for the beams already detailed in the last section.

-The progressive positioning of the beams on the possible centres.

-The allocation of a reflector to each beam, without violating the constraints.

In the approach proposed, they are tackled more or less independently with a multi-start greedy algorithm to position the beams, statistical discretization to choose appropriate diameters, and a graph coloring algorithm for the reflector allocation.

A. Randomized multi-start greedy algorithm

One big challenge of the beam layout problem is to define procedures that allow to efficiently position numerous beams from scratch. Different strategies can come to mind :

-defining the layout beam by beam.

-defining the whole layout with predefined patterns and blocks of beams.

The second option is exactly what is done today with the regular patterns whose suboptimality has already been discussed. The strategy here will therefore be to try to define a layout beam by beam. An exhaustive tree search was clearly not an option given the size of the search space after a sufficiently refined meshing of the zone, a greedy approach being preferred to create acceptable layouts in a reasonable amount of time. However, constraint programming and more precisely constraint propagation were inspirational for the definition of our constructive heuristic. Indeed, to deal with the minimum angular distance constraint, our choice has been to propagate it through an update of the non-usable values for the reflector variable each time a beam is positioned. That way, we cannot use any value that would lead to a violation of the constraints. In practice, to apply the greedy approach (optimal local choice without questioning the previous ones, see [START_REF] Keil | Greedy and Other Efficient Optimization Algorithms[END_REF]), the increment of the new beam for F is computed for all the possible centres, which is immediate since the functional is additive, and a list of the better possibilities is drawn up. Instead of using a standard greedy approach, randomization is operated like in [START_REF] Marti | Multi-start Methods for Combinatorial Optimization[END_REF] through a random choice of the next beam positioned in a list of the best potential beams. With a "multistart"-like approach, each run produces rapidly a new solution that is different than the previous one, these solutions thus exploring zones of the search space that the standard greedy approach could not have seen, the goal being to do better than the latter. An overall view of the algorithm steps could be :

-Determination of the beamwidths to use in each possible beam centre -Random choice of the position of the first beam in a list of best possibilities -Reflector assignment to the first beam -Random choice of the next beam, reflector assignment to that beam -And so on until it is not possible to place another beam (impossible reflector assignment even with recoloring, or no interesting positions left)

In the end, the algorithm used is the one described in pseudocode in Fig. 6.

B. First-fit like graph coloring with simulated annealing for reflector allocation

The strength of the algorithm proposed is to take into account the antenna constraint dynamically which is a way to ensure that the layouts obtained are feasible. To build such an algorithm, it has been decided to define for each possible centre c ∈ C a matrix of ones and zeroes M c ∈ M card(R),card(W) ({0, 1}) in which the impact of the already positioned beams in terms of usable reflectors for the potential beam centre c can be stored and read. All these matrices are updated each time a beam is added. Thus, at any moment during the algorithm, for a given centre c and for the j th beamwidth, M c i,j indicates whether the i th reflector can be used to place a new beam without violating a minimum angular distance constraint. When positioning a new beam at c, the subgraph described in IV-C evolves, and when at least a reflector is naturally available for this new node according to the M c matrix, the less used by the already placed beams is picked (random choice when there are ties none of the satellite reflectors is usable. The natural reflex would be to forbid such centres and try those where there are available reflectors. However, it is important to notice that there is absolutely no reason that the way the graph has been colored until that moment should be optimal (in terms of minimum number of colors used), and even if it was, the newly added node and the corresponding edges have every chance to modify completely the structure of the optimal coloring. Therefore, trying to recolor the already existing beams may be a way to find a correct reflector allocation that includes the new beam. To do so, one has to decide which nodes have to be discolored. The choice here has been to define a tunable complexity h ∈ N + * for the heuristic :

-For h = 1, the direct neighbors of the problematic node are discolored.

-For h = 2, the direct neighbors of the problematic node, as well as the direct neighbors of each one of them are discolored.

-etc... This is illustrated in Fig. 7 where it is assumed that four reflector antennas are available.

As far as what concerns the graph recoloring algorithms themselves, each time a problematic node is found, it has been decided to use the first-fit algorithm and the simulated annealing algorithm on the subgraph constituted of all the discolored nodes and their direct neighbors (some of them being possibly already colored). The principle of the first-fit algorithm is to follow an ordered list of nodes that have to be colored, treat them one by one by assigning the first color available among an unlimited number of ordered colors. The order in which the nodes are colored is determining for the number of colors that will ultimately be needed (see Fig. 8 with the order red<blue<yellow<green). The simulated annealing algorithm is only used with a local search on the order of the nodes when the first-fit algorithm did not provide a satisfying coloring of the graph.

A. The antenna constraint and its corresponding graph coloring problem

As it was already said, a first-fit algorithm was used for the recoloring and when it was not enough to free space in the reflectors source blocks it was combined with a simulated annealing procedure. The first thing to do was to calibrate empirically the heuristic complexity h presented above in order to optimally use the program during the campaign of tests on typical scenarios that followed. On figure 9, the evolution of the mean number of situations resolved by the graph coloring problem with the complexity h is visible. The conclusion is immediate : h = 3 should be used. It seems indeed to be a good tradeoff between situations where too few beams are discolored leaving not many options to try to find a valid recoloring and situations where too many nodes are discolored making the recoloring problem bigger and therefore harder to solve, at least with our first-fit like algorithm. A campaign of 1000 runs on a broadband scenario over Africa where 150 beams could be placed at most allowed to obtain the following results for the recoloring procedure with a complexity h = 3 : in average, 42% situations where no reflectors were available were solved by the first-fit recoloring, and 44% of those it did not solve were then solved by the simulated annealing recoloring. In the end, the results are encouraging and strengthen the idea that finding good recoloring algorithms can lead to layouts where interesting beams are less rejected.

B. Results on the randomized multi-start approach

The multi-start approach was the one chosen to try to improve the performances of the standard greedy algorithm. To measure the added value of that algorithm, we asked for 200 different greedy solutions on the same scenario and we compared all the resulting objective function values to the one we get after applying a standard greedy algorithm. The results are shown in figure 10. We observe that only 3 greedy so-Fig. 10: Multi-start results compared to the standard greedy algorithm lutions produced by the multi-start randomized approach beat the performances of the standard greedy algorithm, and the difference isn't really pronounced. At that point of the study, it is premature to conclude whether this slight improvement is significant for the telecommunication system, complete system designs using the greedy layout and its improved versions needing be compared.

C. Global results on typical scenarios

Several scenarios were tested : North Africa, Austral Africa, Eastern Africa and Africa (whole continent). The corresponding solutions returned by the algorithm can be seen on the figures that follow. The North and Eastern Africa For Austral Africa and the entire continent, two beamwidths were used. More precisely, we had :

• inhomogeneous traffic demand over the region (the colored background map in the figures)

• 4 reflector antennas available

• the maximum number of beams equal to 175

• 0, 5 • and 1, 08 • as available beamwidths

• the minimum angular distances of Table I In all the scenarios presented, the coloring constraint (combined with the obvious constraint to not position beams that do not cover any station) is the one that ends the generation procedure. As a consequence, we can observe that some dense zones remain uncovered (see Fig. 12), and a finer analysis showed that the algorithm tried to place beams but failed because of the antenna constraints. Once again, the conclusion is that trying to implement better recoloring algorithm would have a direct impact on the quality of the layout. Fig. 13 provides the layout returned by the program when the constraint isn't taken into account : one can notice that the greedy algorithm is indeed attracted by these zones but with the minimum angular distance constraint, most of these beams have to be rejected. In the end, this paper provides an alternate option for building non-uniform layouts with a dynamic consideration of the single feed per beam antennas constraints, the good RF performances of this technology making it an interesting solution for the multibeam systems. What has been presented here is the first step of a work that will include frequency and power allocation to the beams, link budget assessments and capacity computations to finalize this system optimization but even without that level of accuracy regarding the system performances, this work provides a tool to build irregular layouts algorithmically with a guarantee of feasibility for an implementation with SFB antennas. Also, the difficulties of satisfying predefined angular separation constraints for the beams of the same antenna while simultaneously trying to ensure the contiguity of coverage have been highlighted. At that point, layouts that use beam diameters adapted to the density of the zones covered and that optimize the antenna gains for the user stations can be reached but they might have the main flaw of leaving some economically important regions or cities uncovered. Though, improvements on the graph coloring procedure might solve some of these unacceptable situations making this approach more efficient.

Fig. 2 :

 2 Fig. 2: Regular layout

Fig. 3 :

 3 Fig. 3: Simple offset reflector system and beam deviation

  Traffic of the station at s B. Set of the possible positions for the beams

Fig. 4 :

 4 Fig. 4: (a) Too many beams (b) Impossible assignment to k reflector antennas (c) Non-optimal acceptable solution (d) Optimal solution

Fig. 5 :

 5 Fig. 5: (a) 4 diameters over Eastern Africa (b) 2 diameters over Africa

Fig. 6 :

 6 Fig. 6: Multi-start randomized greedy layout generation

Fig. 7 :Fig. 8 :

 78 Fig. 7: (a) No reflector available (b) h = 1 (c) h = 2 (d) h → +∞

Fig. 9 :

 9 Fig. 9: Mean percentages of resolved situations with the graph coloring procedure for different h values

  Angular constraints for the tested scenarios scenario have been treated with only one possible beamwidth.

Fig. 11 :

 11 Fig. 11: Beam layout with one beamwidth generated over North-Africa

Fig. 13 :

 13 Fig. 13: Beam layout over Africa returned by the unconstrained algorithm

  ). At that point, we had to decide what to do when facing a situation where nb of greedy layouts= 0 while nb of greedy layouts<nb of greedy layouts wanted do nb of beams placed= 0 while nb of beams placed< n max do if ∃beam positions with non-zero traffic demand then Greedy establishment of the list of best candidates

	Random choice among this list
	Allocation of reflector (potential recoloring)
	if Beam not rejected then
	nb of beams placed++
	traffic covered+=traffic covered by new beam
	end if
	else
	Break while loop
	end if
	end while
	nb of greedy layouts++
	end while


Juan Antonio Lossio-Ventura

Mathieu Roche
email: mathieu.roche@cirad.fr

Yet Another Ranking Function for Automatic Multiword Term Extraction

Term extraction is an essential task in domain knowledge acquisition. We propose two new measures to extract multiword terms from a domain-specific text. The first measure is both linguistic and statistical based. The second measure is graph-based, allowing assessment of the importance of a multiword term of a domain. Existing measures often solve some problems related (but not completely) to term extraction, e.g., noise, silence, low frequency, large-corpora, complexity of the multiword term extraction process. Instead, we focus on managing the entire set of problems, e.g., detecting rare terms and overcoming the low frequency issue. We show that the two proposed measures outperform precision results previously reported for automatic multiword extraction by comparing them with the state-of-the-art reference measures.

1I n t r o d u c t i o n

The huge amount of data available online today is often composed of plain text fields, e.g., clinical trial descriptions, adverse event reports, electronic health records [START_REF] Lossio-Ventura | Combining C-value, Keyword Extraction Methods for Biomedical Terms Extraction[END_REF], customer complaint emails or engineers' repair notes [START_REF] Ittoo | Term Extraction from Sparse, Ungrammatical Domainspecific Documents[END_REF]. These texts are often written with a specific language (expressions and terms) used by the associated community. There is thus a need for formalization and cataloguing of these technical terms or concepts. But this task is very time consuming.

Automatic Term Extraction (ATE) or Automatic Term Recognition aim to automatically extract technical terminology from a given corpus. Technical terminology is a set of terms used in a domain. Therefore term extraction is an essential task in domain knowledge acquisition, because the technical terminology can be used for lexicon update, domain ontology construction, summarization, named entity recognition, information retrieval. Technical terms are useful to gain further insight into the conceptual structure of a domain. These may be: (i) single-word terms (simple), or (ii) multiword terms (complex). The proposed work focuses on mutliword term extraction.

Term extraction metho ds usually involve two main steps. The first step extracts candidates by unithood calculation to qualify a string as a valid term.

The second step verifies them through termhood measures to validate their domain specificity. Formally, unithood refers to the degree of strength or stability of syntagmatic combinations and collocations, and termhood is defined as the degree to which a linguistic unit is related to domain-specific concepts [START_REF] Kageura | Methods of automatic term recognition: A review[END_REF]. ATR has been applied to several domains, e.g., biomedical [START_REF] Lossio-Ventura | Biomedical Terminology Extraction: A new combination of Statistical, Web Mining Approaches[END_REF] [START_REF] Lossio-Ventura | Combining C-value, Keyword Extraction Methods for Biomedical Terms Extraction[END_REF] [6] [START_REF] Zhang | A Comparative Evaluation of Term Recognition Algorithms[END_REF] [START_REF] Newman | Bayesian Text Segmentation for Index Term Identification, Keyphrase Extraction[END_REF], ecological [START_REF] Conrado | Exploration of a Rich Feature Set for Automatic Term Extraction[END_REF], mathematical [START_REF] Stoykova | Automatic extraction of mathematical terms for precalculus[END_REF], social networks [START_REF] Lossio-Ventura | Conversations reconstruction in the social web[END_REF], banking [START_REF] Dobrov | Multiple Evidence for Term Extraction in Broad Domains[END_REF], natural sciences [START_REF] Dobrov | Multiple Evidence for Term Extraction in Broad Domains[END_REF], information technology [START_REF] Newman | Bayesian Text Segmentation for Index Term Identification, Keyphrase Extraction[END_REF], and legal.

There are some well-known ATE issues such as: (i) extraction of non-valid terms (noise) or omission of terms with low frequency (silence), (ii) extraction of multiword terms having complex and various structures, (iii) manual validation efforts of the candidate terms [START_REF] Conrado | Exploration of a Rich Feature Set for Automatic Term Extraction[END_REF], and (iv) management of large-scale corpora.

In response to the above problems, two new measures are proposed in this paper. The first one, called LIDF-value, is a statistical-and linguistic-based measure and addresses issues i), ii) and iv). The second one, called TeRGraph, is a graph-based measure and deals with issues i), ii) and iii). The main contributions are: (1) enhanced consideration of the term unithood, by computing a degree of quality for the term unithood, and, (2) the consideration of the term dependence in the ATE process. The quality of the proposed method is underlined by comparing the results obtained with the most commonly used baseline measures. The experiments were conducted despite difficulties in comparing ATE measures, mainly because of the size of the corpora used, and the lack of available libraries associated with previous works. Our two measures improve the process of automatic extraction of domain-specific terms from text collections that do not offer reliable statistical evidence.

The paper is organized as follows. We first discuss related work in Sect. 2. Then, the two new term extraction measures are detailed in Sect. 3. Precision evaluation is presented in Sect. 4 followed by the conclusions in Sect. 5.

2R e l a t e d W o r k

Recent studies have focused on multiword (n-grams) and single-word (unigrams) term extraction. Term extraction techniques can be divided into four broad categories: (i) Linguistic, (ii) Statistical, (iii) Machine Learning, and (iv) Hybrid. All of these techniques are encompassed in Text Mining approaches. Graphbased approaches have not yet been applied to ATE, although they have been successively adopted in other Information Retrieval fields and they could be suitable for our purpose.

Text Mining Approaches

Linguistic Approaches. These techniques attempt to recover terms via pattern formation. This involves building rules to describe naming structures for different classes by using orthographic, lexical, or morphosyntacticc h a r a c t e r i s t i c s , e.g., [START_REF] Gaizauskas | Term recognition, classification in biological science journal articles[END_REF]. The main approach is to (typically manually) develop rules describing common naming structures for certain term classes using orthographic or lexical clues, or more complex morpho-syntactic features.

Statistical Methods. Statistical techniques chiefly rely on external evidence presented through surrounding (contextual) information. Such approaches are mainly focused on the recognition of general terms [START_REF] Van Eck | Automatic term identification for bibliometric mapping[END_REF]. The most basic measures are based on frequency. For instance: term frequency (tf) counts the frequency of a term in the corpus; document frequency (df ) counts the number of documents where a term occurs. A similar research topic, called Automatic Keyword Extraction (AKE), proposes to extract the most relevant words or phrases in a document using automatic indexation. Keywords, which we define as a sequence of one or more words, provide a compact representation of the document's content. Such measures can be adapted to extract terms from a corpus as well as ATE measures. In [START_REF] Lossio-Ventura | Combining C-value, Keyword Extraction Methods for Biomedical Terms Extraction[END_REF] [START_REF] Lossio-Ventura | Biomedical Terminology Extraction: A new combination of Statistical, Web Mining Approaches[END_REF], two popular AKE measures, Okapi BM25 and TF-IDF (also called weighting measures), are used to automatically extract biomedical terms; residual inverse document frequency (RIDF) compares the document frequency to another chance model where terms with a particular term frequency are distributed randomly throughout the collection; Chi-square [START_REF] Matsuo | Keyword extraction from a single document using word co-occurrence statistical information[END_REF] assesses how selectively words and phrases co-occur within the same sentences as a particular subset of frequent terms in the document text. This is applied to determine the bias of word co-occurrences in the document text, which is then used to rank words and phrases as keywords of the document; RAKE [START_REF] Rose | Automatic keyword extraction from individual documents[END_REF] hypothesised that keywords usually consist of multiple words and do not contain punctuation or stop words. It uses word co-occurrence information to determine the keywords.

Machine Learning. Machine Learning (ML) systems are often designed for specific entity classes and thus integrate term extraction and term classification. Machine Learning systems use training data to learn features useful for term extraction and classification. But the avaibility of reliable training resources is one of the main problems. Some proposed ATE approaches use machine learning (ML) [START_REF] Conrado | Exploration of a Rich Feature Set for Automatic Term Extraction[END_REF] [24] [START_REF] Newman | Bayesian Text Segmentation for Index Term Identification, Keyphrase Extraction[END_REF]. Although ML may also generate noise and silence. The main challenge is how to select a set of discriminating features that can be used for accurate recognition (and classification) of term instances.

Hybrid Methods. Most approaches combine several methods (typically linguistic and statistically based) for the term extraction task. GlossEx [START_REF] Kozakov | Glossary extraction, knowledge in large organisations via semantic web technologies[END_REF] considers the probability of a word in the domain corpus divided by the probability of the appearance of the same word in a general corpus. Moreover, the importance of the word is increased according to its frequency in the domain corpus. Weirdness [START_REF] Ahmad | University of Surrey Participation in TREC8: Weirdness Indexing for Logical Do cument Extrap olation, Retrieval (WILDER)[END_REF] considers that the distribution of words in a specific domain corpus differs from that in a general corpus. C/NC-value [START_REF] Frantzi | Automatic recognition of multiword terms: the C-value/NC-value Method[END_REF] combines statistical and linguistic information for the extraction of multiword and nested terms. This is the most well-known measure in the literature. While most studies address specific types of entities, C/NC-value is a domain-independent method. It has also been used for recognizing terms in the biomedical literature [8] [14]. In [START_REF] Zhang | A Comparative Evaluation of Term Recognition Algorithms[END_REF], the authors showed that C-value obtains the best results compared to the other measures cited above. Another measure is F-TFIDF-C [START_REF] Lossio-Ventura | Biomedical Terminology Extraction: A new combination of Statistical, Web Mining Approaches[END_REF], which combines an ATE measure (C-value) and an AKE measure (TF-IDF) to extract terms, thus obtaining better results than C-value.M o r e o v e r ,C-value has also been applied to different languages other than English, e.g., Japanese, Serbian, Slovenian, Polish, Chinese [START_REF] Ji | Chinese Terminology Extraction Using Window-Based Contextual Information[END_REF], Spanish [START_REF] Barrón-Cedeño | An improved automatic term recognition method for Spanish[END_REF], Arabic, and French [START_REF] Lossio-Ventura | Combining C-value, Keyword Extraction Methods for Biomedical Terms Extraction[END_REF]. That is why we have chosen C-value and F-TFIDF-C as baselines for the proposed experiments.

Graph-Based Approaches

Graph modeling is an alternative for modeling information, which clearly highlights relationships of nodes among vertices. It also groups related information in a specific way, and a centrality algorithm can be applied to enhance their efficiency. An increasingly popular recent application of graph approaches to Information Retrieval (IR) concerns social or collaborative networks and recommender systems [START_REF] Noh | An Automatic Translation of Tags for Multimedia Contents Using Folksonomy Networks[END_REF]. Graph representations of text and scoring function definition are two widely explored research topics, but few studies have been focused on graph-based IR in terms of both document representation and weighting models [START_REF] Rousseau | Graph-of-word, TW-IDF: New Approach to Ad Hoc IR[END_REF]. First, text is modeled as a graph where nodes represent words and edges represent relations between words, defined on the basis of any meaningful statistical or linguistic relation [START_REF] Blanco | Graph-based term weighting for information retrieval[END_REF]. In [START_REF] Blanco | Graph-based term weighting for information retrieval[END_REF], the authors developed a graph-based word weighting model that represents each document as a graph. The importance of aw o r dw i t h i nad o c u m e n ti se s t i m a t e db yt h en u m b e ro fr e l a t e dw o r d sa n d their importance, in the same way that PageRank [START_REF] Page | The PageRank citation ranking: Bringing order to the web[END_REF] estimates the importance of a page via the pages that are linked to it. Another study, [START_REF] Rousseau | Graph-of-word, TW-IDF: New Approach to Ad Hoc IR[END_REF], introduces a different representation of document that captures relationships between words by using an unweighted directed graph of words with a novel scoring function.

In the above approaches, graphs are used to measure the influence of words in documents like automatic keyword extraction methods (AKE) while ranking documents against queries. These approaches differ from ours as they use graphs that are focused on the extraction of relevant words in a document and computing relations between words. In our proposal, a graph is built such that the vertices are multiword terms and the edges are relations between multiword terms. Moreover, we focus especially on a scoring function of relevant multiword terms in a domain rather than in a document. Three steps are involved in computing the LIDF-value:

3T w o M e a s u r e s f o r M u l t i w o r d T e r m E x t r a c t i o n

(1) Part-of-Speech tagging: a part-of-speech is applied to the whole corpus to obtain the lemma of words and to extract linguistic patterns. Part-of-Speech (POS) tagging is the process of assigning each word in a text to its grammatical category (e.g., noun, adjective). This process is performed based on the definition of the word or on the context in which it appears.

(2) Candidate term extraction: before applying any measures, we select terms having a syntactic structure appearing in the pattern list. (3) Ranking of candidate terms: finally the LIDF-value is computed for each term. These steps are explained in the next subsections and detailed in Algorithm 1.

From the Linguistic-Based Approach. The objective is to give greater importance to the term unithood in order to detect low frequency terms.

As in related work, we supposed that terms of a domain have a similar syntactic structure. Therefore, we build a list of the most common linguistic patterns according the syntactic structure of technical terms present inad i c t i o n a r y .I n our work, we chose UMLS1 which is a biomedical dictionary. We conduct partof-speech tagging of the domain dictionary using the Stanford CoreNLP API (POS tagging)2 ,a n dt h e nc o m p u t et h ef r e q u e n c yo fs y n t a c t i cs t r u c t u r e s .P a tterns among the 200 highest frequencies are selected to build the list. From this list, we compute the weight associated with the probability that a candidate term could be a domain term if its syntactic structure appears in the linguistic pattern list. In our experiments, 2 300 000 terms were used to build the list of patterns. Table 1 illustrates the computation of the linguistic pattern probability. To t h e S t at i s t i cal -B as ed Ap p r o ach . Our method LIDF-value is aimed at computing the termhood for each term, using the probability calculated as defined above, the idf,a n dt h eC-value of each term. The inverse document frequency (idf ) is a measure indicating the extent to which a term is common or rare across all documents. It is obtained by dividing the total number of documents by the number of documents containing the term, and then taking the logarithm of that quotient.

The probability and the idf improve the extraction of low frequency terms. The C-value measure is based on the term frequency. The aim of the C-value (see [START_REF] Ahmad | University of Surrey Participation in TREC8: Weirdness Indexing for Logical Do cument Extrap olation, Retrieval (WILDER)[END_REF]) is to improve the extraction of nested terms, i.e., this criteria favors a candidate term that does not often appear in a longer term. For instance, in a specialized corpus (Ophthalmology), the authors of [START_REF] Frantzi | Automatic recognition of multiword terms: the C-value/NC-value Method[END_REF] found the irrelevant term "soft contact" while the frequent and longer term "soft contact lens" is relevant.

C-value(

A)= ⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎩ log 2 (|A|) × f (A) if A/ ∈ nested log 2 (|A|) × f (A) -1 |S A | × b∈S A f (b) otherwise (1)
Where A represents multiword terms, |A| the number of words in A, f (A)the frequency of A in the documents, S A the set of terms that contain A and |S A | the number of terms in S A .Inan utshell,C-value uses the frequency of the term if the term is not included in other terms (first line), or decreases this frequency if the term appears in other terms, by using the frequency of those other terms (second line). The algorithm 1 describes the applied process.

These different statistical information items (i.e., probability of linguisitic patterns, C-value, idf )a r ec o m b i n e dt od e fi n et h eg l o b a lr a n k i n gm e a s u r eLIDFvalue (see ( 2)); where P(A LP ) is the probability of a multiword term A which has the same linguistic structure pattern LP ,i . e . ,t h ew e i g h to ft h el i n g u i s t i c pattern LP computed in Sect. 3.1. As an improvement, we propose to take into account graph-theoretic information to highlight relevant terms, as explained in the following subsection. This approach aims to improve the precision of the top k extracted terms. As mentioned above, in contrast to the work cited before, the graph is built with al i s to ft e r m so b t a i n e da c c o r d i n gt ot he steps described in Sect. 3.1, where vertices denote multiword terms linked by their co-occurrence in the sentences in the corpus. Moreover, we apply the hypothesis that the term representativeness in a graph, for a specific-domain, depends on the number of neighbors that it has, and the number of neighbors of its neighbors. We assume that a term with more neighbors is less representative of the specific-domain. This means that this term is used in the general domain. Figure 1 illustrates our hypothesis. The graph-based approach is divided into two steps: (1) Graph construction: ag r a p h( s e eF i g .2 )i sb u i l tw h e r ev e r t i c e sd enote terms, and edges denote co-occurrence relations between terms, cooccurrences between terms are measured as the weight of the relation in the initial corpus. This approach is statistical because it links all co-occurring terms without considering their meaning or function in the text. This graph is undirected as the edges imply that terms simply co-occur, without any further distinction regarding their role. We take Dice coefficient, a basic measure to compute the co-occurrence between two terms x and y,d e fi n e d by the following formula:

LIDF -value(A)=P(A

LP ) × idf (A) × C-value(A)( 2 )
D(x, y)= 2 × P (x, y) P (x)+P (y) (3)
(2) Representativeness computations on the term graph: a principled graph-based measure to compute term weights (representativeness) is defined. The aim of this new graph ranking measure, TeRGraph,s e e( 4 ) ,i st o derive these weights for each vertex, (i.e., multiword term weight), in order to re-rank the list of extracted terms.

TeRGraph(A) = log 2 ⎛ ⎜ ⎜ ⎜ ⎝ 1.5+ 1 |N(A)| + T i ∈N(A) |N(T i )| ⎞ ⎟ ⎟ ⎟ ⎠ (4)
Where A represents a vertex (multiword term), N(A)t h en e i g h b o r h o o do f A, |N(A)| the number of neighbors of A, T i the neighbor i of A.T h ei n t u i t i o n for ( 4) is as follows: the more a term A has neighbors (directly with N(A)o rb y transitivity with N(T i )), the more the weight decreases. Indeed, a term A having a lot of neighbors is considered too general for the domain (i.e., this term is not salient), then it has to be penalized via the associated score. Figure 2 shows an example to calculate the value of TeRGraph for a term in different graphs. These graphs are built with different co-occurrence thresholds (i.e., Dice's value between two terms). In this example, A 1 and A 2 represent the term chloramphenicol acetyltransferase reporter in Graphs 1 and 2 respectively. In our experiments, the standard GENIA3 corpus was used, which is made up of 2 000 titles and abstracts of journal articles derived from the Medline database, with more than 400 000 words. GENIA corpus contains linguistic expressions referring to entities of interest in molecular biology, such as proteins, genes and cells. The GENIA technical term annotation covers the identification of physical biological entities as well aso t h e ri m p o r t a n tt e r m s .

Results

The results are evaluated in terms of precision obtained over the top k extracted terms (P@k ) for the two proposed measures and baseline measures for multiword terms. In the following subsections, we narrow down the presented results by keepingfor the graph-based measureonly the first 8 000 extracted terms.

Linguistic and Statistical Results. Table 2 presents and compares the results of multiword term extraction with the best baseline measures, such as, C-value, F-TFIDF-C,a n do u rm e a s u r eLIDF-value.T h eb e s tr e s u l t sw e r eo btained with LIDF-value with an improvement in precision of 11% for the first hundred extracted multiword terms. The precision of LIDF-value will be further improved with TeRGraph. We evaluated LIDF-value and baseline measureswithinasequenceofn-gram terms (i.e., n-gram term is a multiword term of n words), for this we require an index term to be a n-gram terms of length n ≥ 2. Table 3 shows the ranking of 3-gram terms with the baseline measures and LIDF-value.F o r3 -g r a mt e r m s C-value obtains 2 irrelevant terms, F-TFIDF-C obtains 3 irrelevant terms while LIDF-value obtains only 1 irrelevant term.

Graph Results. Our graph-based approach is applied to the first 8 000 terms extracted by the Linguistic and Statistical approach. The objective is to rerank the 8 000 terms while trying to improve the precision by intervals. One parameter is involved in the computation of graph-based term weights, namely the threshold of Dice value which represents the relation when building the term graph. This involves linking terms whose Dice value of the relation is higher than threshold.W ev arythreshold (δ)withinδ = [0.25, 0.35, 0.50, 0.60, 0.70] and report the precision performance for each of these values. Table 4 gives the precision performance obtained by TeRGraph and shows that it is well adapted for ATE.

Summary. Table 5 presents a precision comparison of our two measures. In terms of overall precision, our experiments produce consistent results from the GENIA corpus. In most cases, TeRGraph obtains better precision with a threshold of 0.60 and 0.70 (i.e., better precision in most P@k intervals), which is very good because it helps alleviate the problem of manual validation of candidate terms. The performance of our graph-based measure depends somewhat on the value of the co-occurrence relation between terms. Specifically, the value of the co-occurrence relation affects how the graph is built (whose edges are taken), and hence it is critical for computation of the graph-based term weight. Another performance factor of our graph-based measure is the quality of the results obtained with LIDF-value due to the fact that to re-rank TeRGraph the list of terms extracted with LIDF-value is required as input, in order to construct the graph, where nodes denote terms, and edges denote co-occurrence relations.

5C o n c l u s i o n s a n d F u t u r e W o r k

This paper defines and evaluates two measures for automatic multiword term extraction. The first one, LIDF-value,al i n gu i s t i can ds t at i s t i c al -b as e dm e as u re , improves the precision of automatic term extraction in comparison with the most popular term extraction measure. This measure overcomes the lack of frequency information with the values of linguistic pattern probability and idf. We experimentally show that LIDF-value applied in the biomedical domain outperformed as t a t e -o f -t h e -a r tb a s e l i n ef o re x t r a c t i n gt e r m s( i . e . ,C-value and F-TFIDF-C ), while obtaining the best precision results in all intervals (i.e., P@k ).

The second one, TeRGraph, is a graph-based measure. It enables a reduction in the huge human effort required to validate candidate terms. The graphbased measure has never been applied for automatic term extraction. TeRGraph takes into account the neighborhood to compute the term representativeness in a specific domain. Our experimental evaluations reveal that TeRGraph has better precision than LIDF-value for all intervals.

As a future extension of this work, we intend to use the relation value within TeRGraph. Moreover, we plan to test this general approach in other domains, such as ecology and agronomy. Finally, future work includes the use of other graph ranking computations, e.g., PageRank, adapted for automatic term extraction.

3. 1 A

 1 New Ranking Measure Based on Linguistic and Statistical Information: LIDF-value (Linguisitic Patterns, IDF, and C-value Information)

Algorithm 1 .

 1 ComputeLIDF-value (Corpus, Patterns, min freq , num terms ) Data: Corpus =s e to fd o c u m e n t so fas p e c i fi c -d o m a i n ; Patterns = HT patterns (pattern, probability ) //Hashtable of linguistic patterns with its probability; min freq =f r e q u e n c yt h r e s h o l df o rc a n d i d a t et e r m s ; num terms =n u m b e ro ft e r m st ot a k ea so u t p u t Result: L terms =L i s to fr a n k e dt e r m s begin Tag the Corpus; Take the lemma of each tagged word; Extract candidate terms A by filtering with Patterns; Remove candidate terms A below min freq ; for each candidate term A ∈ Corpus do LIDF -value(A)=P(A LP ) × idf (A) × C-value(A); add A to L terms ; end Rank the L terms by the value obtained with LIDF -value; Select the first num terms terms of L terms ; end

3. 2 A

 2 New Graph-Based Ranking Measure: TeRGraph (Terminology Ranking Based on Graph Information)

Fig. 1 .

 1 Fig. 1. Importance of a term in a domain

Fig. 2 .

 2 Fig. 2. TeRGraph 's value for chloramphenicol acetyltransferase reporter

Table 1 .

 1 Example of pattern construction (where NN is a noun, IN ap r e p o s i t i o no r subordinating conjunction, JJ an adjective, and CD ac a r d i n a ln u m b e r )

	Pattern	Frequency Probability
	NN IN JJ NN IN JJ NN	3006	3006/4113 = 0.73
	NN CD NN NN NN	1107	1107/4113 = 0.27
		4113	1.00

Table 2 .

 2 Precision comparison of LIDF-value with baseline measures

		C-value F-TFIDF-C LIDF-value
	P@100	0.690	0.715	0.820
	P@200	0.690	0.715	0.770
	P@300	0.697	0.710	0.750
	P@400	0.665	0.690	0.738
	P@500	0.642	0.678	0.718
	P@600	0.638	0.668	0.723
	P@700	0.627	0.669	0.717
	P@800	0.611	0.650	0.710
	P@900	0.612	0.629	0.714
	P@1000	0.605	0.618	0.697
	P@2000	0.570	0.557	0.662
	P@5000	0.498	0.482	0.575
	P@10000 0.428	0.412	0.526
	P@20000 0.353	0.314	0.377

Table 3 .

 3 Comparison of top-10 ranked 3 gram terms (irrelevant terms are italicized and marked with *)

	C-value	F-TFIDF-C
	human immunodeficiency virus	kappa b alpha*
	kappa b alpha*	nf kappa b
	tumor necrosis factor	jurkat t cell
	electrophoretic mobility shift	human t cell
	nf-kappa b activation	mhc class ii
	virus type 1 *	cd4+ t cell
	protein kinase c	c-fos and c-jun*
	long terminal repeat	peripheral blood monocyte
	nf kappa b	tc e l lp r o l i f e r a t i o n
	jurkat t cell	transcription factor nf-kappa*
	LIDF-value
	ik a p p ab
	human immunodeficiency virus
	electrophoretic mobility shift
	human t cell
	mobility shift assay
	kappa b alpha*
	tumor necrosis factor
	nf-kappa b activation
	protein kinase c
	jurkat t cell

Table 4 .

 4 Precision performance of TeRGraph when varying δ parameter

		δ ≥ 0.25 δ ≥ 0.35 δ ≥ 0.50 δ ≥ 0.60 δ ≥ 0.70
	P@100	0.840	0.860	0.910	0.930	0.900
	P@200	0.800	0.790	0.850	0.855 0.855
	P@300	0.803	0.773	0.833	0.830	0.820
	P@400	0.780	0.732	0.820 0.820	0.815
	P@500	0.774	0.712	0.798	0.810	0.806
	P@600	0.773	0.675	0.797	0.807	0.792
	P@700	0.760	0.647	0.769	0.796	0.787
	P@800	0.756	0.619	0.748	0.784	0.779
	P@900	0.748	0.584	0.724	0.773	0.777
	P@1000 0.751	0.578	0.720	0.766	0.769
	P@2000 0.689	0.476	0.601	0.657	0.694
	P@3000 0.642	0.522	0.535	0.605	0.644
	P@4000 0.612	0.540	0.543	0.559	0.593
	P@5000 0.574	0.546	0.544	0.554	0.562
	P@6000 0.558	0.539	0.540	0.549	0.561
	P@7000 0.556	0.540	0.540	0.545	0.552
	P@8000 0.546 0.546 0.546 0.546 0.546

Table 5 .

 5 Precision comparison of LIDF-value and TeRGraph

		LIDF-value TeRGraph TeRGraph
			(δ ≥ 0.60) (δ ≥ 0.70)
	P@100	0.820	0.930	0.900
	P@200	0.770	0.855	0.855
	P@300	0.750	0.830	0.820
	P@400	0.738	0.820	0.815
	P@500	0.718	0.810	0.806
	P@600	0.723	0.807	0.792
	P@700	0.717	0.796	0.787
	P@800	0.710	0.784	0.779
	P@900	0.714	0.773	0.777
	P@1000	0.697	0.766	0.769
	P@2000	0.662	0.657	0.694
	P@3000	0.627	0.605	0.644
	P@4000	0.608	0.5585	0.593
	P@5000	0.575	0.5538	0.562
	P@6000	0.550	0.549	0.561
	P@7000	0.547	0.545	0.552
	P@8000	0.546	0.546	0.546

http://www.nlm.nih.gov/research/umls

http://nlp.stanford.edu/software/corenlp.shtml

http://www.nactem.ac.uk/genia/genia-corpus/term-corpus

Acknowledgments. This work was supported in part by the French National Research Agency under JCJC program,grantANR-12-JS02-01001,aswellasby University of Montpellier 2 and CNRS.


François Garde

Alain Bastide

Dalila Bentaleb

Alihamada Fakra

Eric Ottenwelter

Eric Pothin

Nejia Ferjani

THE CONSTRUCTION OF A ZERO ENERGY BUILDING IN REUNION ISLAND. PRESENTATION OF A NEW APPROACH TO THE DESIGN STUDIES

This paper presents a zero energy project applied to a university building in Reunion Island. The aim is to create a building which uses half the energy of a standard building. The methodology was conceived to meet requirements defined during the thermal design and building systems planning stage. Innovations relating to architectural design, building systems performance and numerical simulation are presented. Solar panels integrated into the roofing provide sufficient electrical energy for the building to produce more energy than it uses.

INTRODUCTION

The energy situation in Reunion Island Reunion Island, like other insular regions, has difficulty matching its energy supply to the demand, 87% of which comes from buildings. The growth in demand for power and energy is about 7% per year, and currently, the absence of any thermal regulations allows the construction of buildings such as the one shown in Figure 1. Fortunately, the authorities such as the Regional Council (Conseil Régional) encourage the construction of 'green' buildings; indeed, the Council has funded an energy plan for the entire island named PRERURE, the objective of which is to make Reunion energy self-sufficient by 2025 [START_REF] Lopez | ICE, INSET[END_REF]. Among other things, the study's conclusions relate to managing energy use and planning the use of various renewable energy sources.

The University of Reunion and energy management

The University of Reunion has the same problem, on a different scale, as the rest of the island, in having growing energy needs, recurring energy management problems and buildings which devour energy. The energy consumption rate is 165 kWh per year per square metre of useful area (kWh/yr/m²UA). This rate includes the air conditioning, its auxiliaries and all other uses (principally computing and lighting). The electricity bill in 2004 was about 560 thousand euros, 40% of which was for air conditioning. Five years ago the university introduced an energy management policy, and in this paper we intend to present the methodology adopted for new buildings, using as illustration a zero energy building project.

METHODOLOGY AND OBJECTIVES

The energy use objectives which we have for 2020 are those fixed by the Kyoto protocol, and involve reducing greenhouse gas emissions fourfold. This will lead to less energy use in buildings. Figure 2 shows the current energy use, that intended for the new, optimised university buildings, and that of a zero energy building, the objective for 2002 being a rate of 40 kWh/yr/m² UA. The basic aim of our methodology is to try and achieve a state of thermal and visual comfort with passive means. Air conditioning and artificial lighting must be used as a last resort. To do this, new university buildings must respect a number of building quality criteria, relating to :

The surrounding environment ;

The thermal and airflow design;

The technical systems and facilities;

The control and monitoring of energy use. These quality criteria are laid out in a note about energy management which is part of the building construction programme. Buildings should also respect the guidelines given recently by the PERENE programme [START_REF] Garde | Elaboration of Thermal Standards for French Tropical Islands : Presentation of The PERENE Project[END_REF]. The PERENE programme (a French acronym for Energy PERformance in Buildings) prefigures a project relating to thermal regulations in the French overseas departments for businesses. In the face of the tardiness of the authorities in setting up even minimal regulations for the building sector, local professionals in the industry decided to put together a design aid which could be applied to both residential and business buildings, allowing good design for a building in any of the island's climatic zones. Objectives for the power of installations and energy consumption are given. This design tool has been in use since 2004 and is currently being tested.

Zero energy building

Objective 2020

Air conditioning

Other uses

Figure 2 : Energy use objectives The zero energy building project was among the buildings chosen during this test period. It is also the hope that the project will be awarded the 'Greenlight' label for lighting; this European label is a reward for buildings which are well-designed with regard to the use of artificial and natural lighting. The clearly stated objective is to make this building the reference in the French overseas departments for energy optimisation.

THE ZERO ENERGY BUILDING PROJECT

The project is composed of four small, parallel buildings. The main facades face north and south (see Figure 3). The two buildings to the north will house a degree level course in Communication Services and Networks, while the southerly buildings will be for an M.Sc. in Civil Engineering (to chartership level). The room types are as follows:

-offices for the two departments on the ground floors of the lateral buildings; -classrooms for teaching practical work; -computing rooms. The classification of useful area by room type is given in Table 1. We note that 47% of the useful area is air conditioned. A requirement of the programme is that the classrooms should not be air conditioned, and so it is up to the designers to find passive ways of ensuring an acceptable comfort level in these rooms.

Objectives :

As mentioned above, the objective is to reduce, if possible completely the period with air conditioning. Standard buildings sometimes need air conditioning all year long, but the average use is seven months (from the start of October to mid May). To achieve the objective, the environment surrounding the building and the airflow and thermal designs are paramount.

The surrounding environment

Both the construction programme and PERENE require peripheral vegetation at least three metres wide around the building, in order to avoid letting the air heat up and penetrate the buildings when in natural ventilation mode. Figures 3 and4 show that this point has been respected. Further, the orientations of the main facades north-south limit the amount of sunlight falling on easterly and westerly gables, and these are perpendicular to the thermal breezes which blow during the hot season. The ventilation of the rooms is thus optimised.

NG

Thermal design of the building envelope PERENE and the building programme give values of a solar factor for the opaque walls and windows, and the project has respected these solar factor values which must not be exceeded. The technical solutions to keep within the PERENE values are the following:

-Roofing : insulation using 9 cm of polystyrene on suspended slabs with a ventilated over-roof.

-Wall and windows north and south : overhanging roof, passageways and brise-soleils made of wooden strips fixed to oblique galvanised steel supports.

With regard to optimising the brise-soleils, it is impracticable to model them using the usual thermal simulation codes. For each façade, the number of strips, their spacing and their angle was therefore calculated using a 3D reconstitution of the building in Autocad. Figure 6 demonstrates the efficiency of the solar protection on a northerly façade during an April day. The ultimate objective is to have full protection during the teaching hours (from 8am to 5pm) for the northerly facades until the end of April and for the southerly facades during December.

Airflow design

The basic principle in a tropical climate is to have rooms allowing air to blow through, by having opposite exterior facades with a porosity higher than 20%. This principle is applied in the building programme. Thus, all the classrooms exhibit this property, with a porosity level above 30% due to louvre blind-like constructions which have the advantage of allowing regulation of the airflow, while also providing protection against cyclones and break-ins. Because of this, the rooms are usable with natural ventilation at night, being cooled by night breezes. Thanks to this principle, it is possible to recycle the air at a rate of 40 to 100 vol/h with interior speeds of 1 m.s -1 for wind speeds of about 2 m.s -1 . The design of the offices is more difficult because, as one can see in Figure 5, the configuration is a standard one of offices off a central corridor. The original feature of the project is to have interior louvre blinds made of frosted glass which ensure that the interior air flow is well spread, providing an interior porosity of 30%. Lastly, another innovation is to have planned for large fans in all the rooms, including those with air conditioning. These guarantee additional air speed on windless days and allow a transitional period before turning on the active cooling (see Figures 5,11 and 12).

Dynamic simulations

The dynamic simulations were intended to predict the different operational periods : natural ventilation, air fans or air conditioning. These simulations were carried out by researchers at the university working with the thermal design office. A thermal and air flow simulation program was used, which, in conjunction with a model of large openings under pressure, modelled the impact of natural ventilation on the thermal comfort. Roldan's mass transfer model, detailed in [START_REF] Boyer | A multi model approach of thermal building simulation for design and research purposes[END_REF], was used. The model takes into account one air pocket per room, and stratification is neglected. The comfort indices chosen were Givoni's comfort diagram and the resultant temperature T res . The formula for T res combines the air temperature T a and the average wall temperature T rm for a naturally ventilated room (T res = 2/3.T a + 1/3 T rm ). The comfort zones allow us to find the percentage of points within each comfort zone (0 m.s - 1 , 0.5 m.s -1 and 1 m.s -1 ) as well as the number of hours of discomfort. The resultant temperature gives us an idea of the different operational periods. The weather record used was for a year with hourly increments. This was extrapolated using an incomplete database of site measurements; the extrapolation method used is given in (David 2005).

The average interior air speed was estimated using a correlation coefficient between the porosity and the exterior air speed given by (Allard 02). Thus, for a porosity of 30% and a wind speed of 1.5 m.s -1 , we find average speeds of 0.5 m.s -1 . As for the air speed with the large air fans, measurements on site have given speeds above 1m.s -1 .

Figure 7 : Simulation results for an office during the hot season (1 st October to 31 st April)

Figures 7 and8 show simulation results for a three person office. For the interior loads, we supposed that natural lighting would be sufficient, while the computers used 200W, a slight over-estimation compared with recent flat screen computers which use on average only 120W. Figure 7 and Table 2 show that 89% of the pairs of resultant temperature/humidity values are within the comfort zones for the period from 1 st October to 31 st April, the hot season. The occupants will thus experience discomfort 11% of the time, principally at the beginning of the afternoon, for a total of 160 hours. A possibility therefore would be to use natural ventilation in the morning and active cooling in the afternoon. The same simulations were carried out for a classroom of 60 m² with 40 students and a computing room containing 20 students and 20 PCs. In each case, natural lighting is assumed sufficient; Table 2 gives the results. Naturally, the discomfort level is higher in the computing room, with twice as many discomfort hours (i.e. twice as many points outside the comfort zone) as in the office. This number of hours corresponds to the time of active cooling. Using Figure 8, it is possible to predict the different operational periods -natural ventilation, air fans or air conditioning -by using the change in resultant temperature through the year. The transition from natural ventilation to air fans to is made partly using our experience and knowledge of the site and climate, but also on the basis of a maximum average resultant temperature above 28°C, and using a study of the transition from Trade Winds to thermal breezes. The transition from air fans to air conditioning was made when the resultant temperature exceeded 30°C. This is because an office worker dressed in summer clothes begins to feel the heat above 30°C with an air speed of 1 m.s -1 . We recall that the temperature experienced at this speed is 4°C below the actual resultant temperature. We see therefore that an office only requires active cooling from January, and that air fans are sufficient until the end of the calendar year. Figure 9 shows the different operational periods defined using dynamic simulations. We see that the office spaces are air conditioned for 1.5 months and the computing rooms for 3 months (15 days in December and from the start of February to mid April). It was thus possible to calculate the annual energy consumption of the air conditioning and the air fans. We found that the zero energy building consumed four times less electrical energy than a standard building with a rate of 17 kWh/yr/m²UA for the air conditioning. This includes the refrigeration, auxiliaries and the air fans.

RESULTS AND DISCUSSION : VISUAL COMFORT

Context and objectives

Just as for the thermal comfort, adequate lighting must be provided by passive means, in other words by natural lighting. In the case of artificial lighting, French standards relating to lighting at work tend to lead to unnecessarily large installations. As an example, a typical figure is 17W/m² giving 700 lux of illumination, whereas 300 lux would be more than enough; this results in buildings which consume twice as much energy as necessary. The building programme and the energy management note require the electrical installations to use less than 7 W/m². We will see that this condition can easily be satisfied with no significant extra cost.

Natural lighting

All the rooms were classed by type and were modelled using software capable of simulating the level of natural lighting. This software is widely available in design offices (DIAL). As an example, Figure 10 shows the change in the daylight factor on a cloudy day for a first floor classroom. This factor must be higher than 1.5% to provide acceptable lighting. This type of figure combined with the results in Table 3 reveal that throughout the first floor rooms, artificial lighting is never necessary at teaching times (8am to 5pm), throughout the year. The only rooms which pose a problem are two ground floor classrooms in the central buildings. We are currently investigating ways of improving the natural lighting, in particular by reducing or piercing the terrace slabs (see Figure 3). A technical solution is provided by the interior blinds in the offices which are used for natural ventilation but also allow extra daylight into the corridor (see Figures 5 and11). The simulations have therefore shown that the corridor does not need artificial lighting.

Artificial lighting

To attain the objective of 7 W/m², the layouts of the office and the classrooms were rethought to take into account the presence of air fans and to avoid any stroboscopic effects interfering with work. French legislation requires an average of 425 lux in an office and 325 lux in a classroom. Our approach was to respect 400 lux over the desks, but we considered that 100 lux elsewhere would be quite sufficient. Therefore, as shown in Figure 11, the artificial lighting in the office is given by three low energy 15W wall lights made of frosted glass, and three low energy office lamps. The power of the installations is 90 W/20 m², or a rate of 4.5 W/m². A standard building would have had lighting from three 4x18W installations, giving a total power of 216 W and a rate of 11W/m². Turning to the classrooms, the level of lighting required by the programme is 250 lux, i.e. 100 lux less than required by law. Natural lighting will make up the difference. As a result, in technical terms, the 4x18W installations normally used have been replaced by 2x24W installations with electronic components. The power of the installations in a room like the one shown in Figure 12 is thus 8.4 W/m², whereas it would have been 14 W/m² in a standard building. The room in Figure 12, in common with the others, features double lighting so that the central part can be used alone, should the daylight factor be too low. Of course, the solutions put forward have been studied using simulations to check that the necessary levels of illumination with artificial lighting were achieved. The average power of the installations throughout the building is 7 W/m², and the energy use rate is 5.5 kWh/yr/m², compared with 9.4kWh/yr/m² for a standard building. RESULTS AND DISCUSSION : TECHNICAL EQUIPMENT

Overview of technical equipment

The construction programme imposes a minimum performance level on certain technical equipment. Thus, the refrigeration will be provided by two different types of single unit scroll compression devices placed on the terrace roofing. Having two types of device will allow their performances to be compared; the types are:

-a chiller for the SRC department; -a VRV device -i.e. variable refrigerant volume, for the Civil Engineering department. The VRV device uses a cooling fluid between the device and the end units. This technology is widely used in Reunion and exhibits very good refrigerating efficiency, of about 10, where the refrigerating efficiency is defined here as the refrigerating power delivered divided by the device's electrical power. The programme requires this efficiency to be higher than 3, for any load. The electrical power of these devices is 30 kW, but would have been 78 kW for a standard building. Turning now to the artificial lighting, all the lights used are fluorescent with low luminance. The exterior lighting will be provided by high pressure sodium lamps; halogen lights are forbidden. The offices are equipped with movement detectors which increase the thermostat to 27°C and turn off the lighting if the room remains unoccupied

Wall lights 15 W

Interior blinds giving extra daylight for a while. A centralised management system (CMS) controls and monitors the energy use. The CMS gives the energy consumption for each type of usage and calculates the load on the building in real time. The high performance technical solutions combined with the high thermal quality of the building have allowed us to greatly reduce the power demands of the building. By taking into account profusion effects and simultaneity factors, we find a maximum electrical power demand of 51 kW. It would have been 94 kW for the same building without energy management. Figure 13 gives the overall consumption rates by type of usage. We see that the building will use a third of the energy used in a standard building, with a total rate of 50 kWh/yr/m². The annual consumption is about 87 MWh/yr.

Renewable energy

The four mono-inclined over-roofs north and south are made of poly-crystalline PV panels fixed directly to the metal structure, in place of the normal sheet metal. Roofs 1 and 3 have a northerly slope of 9°, while roofs 2 and 4 have southerly slopes of 9° (see Figures 3 and5). Simulations carried out using PVSYST (PVSYST 3.4) showed that the southerly roofing produced only 5% less energy over the year than the northerly ones. The productivity is about 1500 kWh/kWp/yr (see Table 4). The nominal power is 149 kWp. The annual production is estimated as 226 MWh, which is 2.5 times the provisional consumption by the building. We can see that roofs 1 and 3 could meet the consumption and power needs of the building on their own. All the solar panels are connected to the grid, and the financial arrangement for their installation involves renting them and is tax-free. The university rents the roofs and as it does not own the solar panels, it is not responsible for their maintenance.

CONCLUSION

The energy use objectives have been met. This was thanks to excellent collaboration between the contractors and the university researchers, who pooled not only their dimensioning aids and expertise, but also their design approaches. Thus, by using a few architectural innovations such as interior blinds, wall lights, using air fans, improved management and intelligent dimensioning of the building systems, it is possible to create a building which uses a third of the energy of a standard building with an additional cost of 2%, due mainly to the optimised CMS. Further, the solar panels will produce the equivalent of 2.5 times the building's energy use.

Energy ratio by type of usage (kWh/an/m²SU)

Figure 1 :

 1 Figure 1: A perfect counter-example in thermal design for tropical climate building. The unprotected glass frontage faces east.

Figure 3 :

 3 Figure 3 : 3D view of the building. The azimuth of the northerly facades is -14° East/North

Figure 4 :

 4 Figure 4 : View of the northerly facades (solar protection with wooden strips) and the westerly ones (sheet metal and wood cladding).

Figure 1 :Figure 2 :

 12 Figure 1 : The technical solutions chosen for the thermal and airflow design of the building.

Figure 8 :

 8 Figure 8 : Change in resultant temperature in an office during a typical year.

Figure 9 :

 9 Figure 9 : Operational periods of the air conditioning and the air fans defined using dynamic simulations

Figure 10 :

 10 Figure 10 : Change in the daylight factor along a section through a first floor classroom

Figure 11 :

 11 Figure 11 : Methods of natural lighting (interior blinds giving extra daylight) and artificial lighting (wall lights) in an office.

Figure 12 :

 12 Figure 12 : Methods of artificial lighting and positioning of lights and air fans for a classroom of 60 m².

Figure 8 :

 8 Figure 8 : Summary of energy use by type of usage for the zero energy building and the same building with standard design.

Table 1 : Classification of useful area by room type Rooms Air conditioned areas Areas without air conditioning

 1

	Department offices	401 m²
	Computing rooms	423 m²
	Classrooms	401 m²
	Others	512 m²
	Sub

Total 824 m² (47%) 913 m²(53%) Total useful area 1737 m²

Table 2 :

 2 Percentage of points within the comfort zones and number of hours of discomfort

		Office	Classroom Computing
				room
	0 m.s -1	24%	26%	23%
	0.5 m.s -1	38%	38%	36%
	1 m.s -1	27%	22%	23%
	Total %	89%	86%	82%
	Hours of discomfort	160 h	270 h	335 h

Table 3 :

 3 Percentage of daylight factor higher than 1.5% by room type

	Room	% of room's area with factor ≥ 1.5%	Daylight factor minimum (%)
	Ground floor office beside inner court	60%	1.0%
	Ground floor classroom beside inner court	Between 40 and 82%	1.2%
	First floor classrooms	100%	1.6%

Table 4 :

 4 Nominal power, energy produced and productivity for the four roofs.

		Area	Nominal power kWc	Production MWh/yr	Productivity kWh/kWp/yr
	Roof 1	360m²	46	71.1	1553
	Roof 2	252m²	32	47.5	1484
	Roof 3	242m²	31	47.9	1558
	Roof 4	317m²	40	59.9	1485
	Total	1171m²	149 kWp	226.4

ACKNOWLEDGEMENTS

The authors wish to thank the project's architect, Thierry Faessel-Bohe, for the 3D views of the building and the 'BET Tribu' for the DIAL simulations.