Michel Vasquez
email: miche!.vasquez@site-eerie.ema.fr

A Heuristic Approach for Antenna Positioning in Cellular Networks*

Keywords: large scale combinatorial optimîzatîon, tabu search, radio network planning

The antenna-positioning problem concerns finding a set of sites for antennas from a set of pre-defined candidate sites, and for each se\ected site, to dctermine the number and types of antennas, as well as the associated values for each of the antenna parameters. Ail these choiccs must satisfy a set of imperative constraints and optîmize a set of objectives. This paper presents a hcuristic approach for tackling this complex and highly combinatorial problem. The proposed approach is cornposed of three phases: a constraint-based pre-processing phase to fil ter out bad configurations, an optimization phase using tabu search, and a post-optimization phase to improve solutions given by tabu search. To validate the approach, computational results arè prcsented using large and realistîc data sets.

Introdnction

The planning process of mobile radio networks may be roughly divided into two different problems: the Antenna Positioning Problem (APP) and the Frequency Assignment Problem (FAP). The basic APP is concerned with a series of decisions, such as the site locations for the antennas, the number and types of antennas for each site, and the associated values for the antenna parameters. The FAP has to do with the assignment of a set of available frequencies to the antennas of the network. Both problems involve a great deal of constraints, and they are closely related, because a good (bad) antenna positioning may make frequency assignment easier (harder).

Until now, many studies have been carried out for the FAP and highly effective optirnization algorithms have been developed; see for instance, [START_REF] Box | A Heuristic Technique for Assigning Frequency to Mobile Radio Nets[END_REF][START_REF] Crampton | A Para!lel Genetie Algorithm for Frequency Assignment Problems[END_REF][START_REF] Duque-Anton | Channel Assignment for Cellular Radio Using Sîmulated Annealing[END_REF]Funabiki and Takefuji, 199 2 ;Hao and Dorne, 1995;Hao, Dorne and Galinier, 1998;[START_REF] Hurley | A Comparison of Local Search Algorithms for Radio Link Fre quency Assignment Problems[END_REF]Lai and Coghill, Jaumard et al., 2000). Many network operators now routinely use frequency-planning tools integrating such algorithms.

On the contrary, studies on optimization algorithms for the antenna-positioning problem seem much more limited. Indeed, most existing studies are oriented towards small-scale micro-cellular or indoor systems involving only several antennas [START_REF] Fortune | WISE De sign of Indoor Wireless Systems: Practical Computation and Optimization[END_REF][START_REF] Mcgeehan | Optîmizing Microcell Base Station Locations Using Simulated Annealing Techniques[END_REF][START_REF] Sherali | Optimal Location ofTransmitters for Micro-Cellular Radio Communication System Design[END_REF]. Other studies fo cus on optimizing some antenna parameters or some specific objective such as the coverage of a (relatively small) area [START_REF] Calégari | Radio Network Planning with Combinatorial Optimisation Algorithms[END_REF][START_REF] Molina | The Automatîc Location of Base-Stations for Optimised Ce!lularCoverage: A newCombinatorial Approach[END_REF]. No real optimization algorithm is available yet for antenna positioning and optimization of large-scale radio networks. Tasks related to antenna positioning are essentially carried out with the help of engineering tools integrating some simulation functions, which leads to largely sub-optimal solutions.

With the continuous and rapid growth of communication traffic, large scale planning becomes more and more diffi cult and cannot be realized in an optimal or near optimal manner. Automatic or interactive optimization algorithms and tools would be very useful and helpful. Advances in this area will certainly lead to important improvements concerning the service quality in tenus of coverage and interference and allowing the decrease of the installation cost. The APP thus constitutes a signifi cant stage in the process of cellular network planning.

The general antenna-positioning problem can be informally described as follows. Given a list of candidate sites for antennas, several types of antennas, and a discretized geographical working area characterized by a set of points with information related to traffi c estimation and the radio threshold, the aim is to select some sites among the candidate sites, and for each selected site determine the nurnber and types of antennas, as well as the associated values for each of the antenna parameters. All these decisions must satisfy a set of irnperative constraints ( cover, handover, one connected-component cell) and optimize a set of objectives (number of sites used, amount of traffic that can be handled, level of potential interference, efficiency of transmitters). It is easy to see that the problem is highly combinatorial. The number of possible combinations is enormous for realistic networks, leading to search spaces as large as 2 4•000,000.

The heuristic approach we develop is composed of three sequential phases: a constraint based pre-processing phase to eliminate a large number of "bad" combinations, an opti mization phase by tabu search working in a reduced search space, and a post optimization phase by fine tuning of antenna parameters.

This approach is applied to two large and realistic test data sets corresponding respectively to an urban network and a highway network in a GSM system. Experimentation shows that the proposed approach is highly effective, robust, and fl exible.

2, Problem description

In this section, we give the basic elements necessary for the general understanding of the antenna-positioning problem. A more detailed presentation of the APP can be found in Reininger (1997) and Reininger and Caminada ( 1998a). A cellular network is composed of three entities: a discretized geographical working area, where signals and traffic are measured, mobile ( cellular) stations (MS), which defi ne the services, and antennas, which can be placed on some pre-defi ned sites within the geographical area.

Working area

The geographical working area on which a network is deployed is discretized into a fi nite number of points called reception test points (RTP). For each RTP, a radio signal is tested.

From the set of RTP, two other sets are defined:

• the set of service test points (STP), where the radio signal must be higher than a threshold Sq to allow the establishment of communications (Section 2.2), • the set of traffic test points (TTP), for each of which the traffic of communication measured in Erlang is estimated.

The traffic implies the communication, a TTP is thus necessarily a STP and the following relation is always verified:

{TTP} C {STP} c {RTP}
The working area is also described by a list of pre-defi ned candidate sites on which antennas may be placed. Table 1 and fi gure 1 summarize ail these concepts. This example corresponds to an urban area of 49.6 km x 45.8 km.

The mesh step for the discretization is 200 meters. We thus have 248 x 229 = 56792 RTP.

Mobile station (MS)

A network provides a service for a category of mobile stations. A quality threshold, noted Sq hereafter, defines this service. A network may provide different services, thus different quality threshold. If the radio signal al a given point of the working area is higher than the required Sq, then the cellular phones that are al this point can communicate. The value of the threshold Sq is dependent on the MS considered and expressed in decibel ( dBm) (Table 2). STP : points where radio signais must be;, Sq TTP : points where traffic is estimated An MS has another specific characteristic that must be considered: the reception sensitiv ity of the MS, or mobile sensitivity (Sm). Sm has an average value of -99 dBm, however, a signal ofthis value is not sufficient for an MS to establish communication with an antenna, but it does scramble an already-established communication. This point wiH be re-examined later when we evoke the noise level of a network.

RTP : points where radio signals is computed

Candidate sites

Antennas

In general, there are several types of antennas available in a network, characterized primarily by their transmission gain (Gs) and their propagation diagrams (fi gure 2). In this work, we consider 3 types of antennas: omnidirectional (OMNI), large directional (LD), and small directional (SD).

The principal parameters of these antennas are:

• the power, PS, which can vary frorn 26 to 55 dBm,

• the azimuth (for a directional antenna) between 0 ° and 360 °,

• the tilt (for a directional antenna) between -15 ° and O', . Gs=ll.15dBm

• the number of transmitters (TRX) assigned to the antenna for a given traffic. In a GSM system, a conversion table determines this number according to the material used. Table 3 shows such an example where an antenna may require I to 7 TRX (thus I to 7 channels).

Note that the number of TRX is directly determined by the traffic and does not need to be tuned by the optimization algorithm.

These antennas can be placed on pre-defined candidate sites in the working area. In our case, a site can host either one OMNI antenna or one to three LD or SD antennas.

Base station and cell

A base station, BS b, is defined by a quintuplet b = (site, antenna, tilt, azimuth, power). It corresponds thus to the choice of a site, an antenna on this site and the parameter values of the antenna. For example, for the above network, the BS b = (356, LD, 0, 30, 38) corresponds to the placement of a LD antenna on the site numbered 356. This antenna has a tilt of 0', an azimuth of 30 °, and a power of 38 dBm.

Other components are also involved in the definition of a BS, such as BS transmitter loss and BS receiver sensibility (Reininger, 1997;Reininger and Caminada, 1998a), and the same applies to the MS (Section 2.2). Since these values are constant for a given situation, they will not be further discussed in this paper.

In order to assess the signal quality at each point, a radio wave propagation model is needed. Such a mode! is able to predict the propagation loss of an electromagnetic fi eld between a site and each RTP of the working area. To compute the prediction, the mode! takes into account the site coordinates, its height, the RTP coordinates, the set of obstacles between the site and the RTP (buildings, mountains ... ), and the angle of incidence between the site and the RTP. We evoked above only downlink signais emitted by base stations towards cellular phones. Infact, il is also necessary to take into account signais from MS towards BS (uplink signais). It is, however, shown in Reininger and Caminada (1998a) that if the downlink signal, coming from a BS, is higher than the quality threshold Sq and the uplink signal is stronger than the downlink signal (which is indeed the case in GSM systems), then it is not necessary to be concerned with uplink signais.

Thus, starting from the data of a BS in a network we will be able to calculate, for each point of the geographical area, a radio signal, noted hereafter as Cd. The cell of a BS corresponds thus to the set of STP covered by the BS, i.e. for which the signal received from this BS is the best one and higher than the quality threshold Sq. Figure 3 illustrates the link between an isolated BS and its cell.

Since radio wave propagation is never homogeneous and isotropie, the cell of a BS is always irregularly bounded, depending on the topography and the transmitting power. Moreover, the cell of a BS is dependant on other BS emitting from overlapping areas. 1

Constraints

Each STP must be served by at least one BS. Therefore, the union of the cells in a given network must be equal to the set of all the STP located in the working area. This necessity constitutes the global coverage constraint for a network.

When an MS moves from one cell to another, the network must be able to guaran tee the continuity of the communication. To accomplish this, it is essential that each cell has a nonempty intersection (handover area) with ils neighboring cells. This require ment constitutes the handover constraint, which must be respected by all the cells of the network.

The STP contained in a cell may constitute several connected components. Connected components play a signifi cant (and negative) role in the quality of a network (Reininger and Caminada, 1998b): the more connected components there are for a cell, the more in terference there may be, Also, cells having more connected components make it difficult to manager the handover. Therefore, one of the constraints of the APP is that each cell of the network constitutes only one connected component. This local constraint is called one connected component (OCC) constraint, for which in this paper, on1y components containing more than 8 STP are taken into account (see Section 3.3). For example, the cell in figure 3 satisfi es the OCC constraint, even if, in addition to the main connected cornponent, the cell has one component of 2 STP and six other components of lSTP.

Objectives

The installation of a new site is usually very expensive for the network operator. For this reason, a major objective of APP is to minimize the number of sites used.

A cornplete network is made up of a certain number of ce lis (typically one hundred forthe networks we studied). Each STP receives signals coming from several BS. These overlap ping signals are necessary for the purpose of handover, but at the same time generate interfer ing noise. Therefore, a second important objective is to minimize the level of noise within the network.

A cell covers a certain number of traffic test point TTP. However, given that the total traffic served by a cell cannot exceed 43 Erlang (see Ta ble 3), it is possible that the traffic of some TTP within a cell may not be totally served. Therefore, a third objective is to maximize the total traffic supported by the network.

One notices from Table 3 that the closer the traffic of a cell is to the maximum accepted by a given number of TRX, the better the output of these TRX will be. This leads to a fourth objective, which is to maximize the traffic yield of the BS transmitters in the network.

The preceding classifi cation of constraints and objectives corresponds to a particular scenario that was used within the framework of this study. Of course a network operator can interpret ail these concepts differently and exchange some constraints and objectives. Moreover, other constraints and objectives may be introduced.

The above constraints and objectives are rather interdependent of each other, and often have conft icting natures. First, the coverage constraint is opposed to the objective of min imizing the number of sites used. Second, the handover constraint implies the existence of several signals at one same point, and can increase the level of noise which one wants to minimize. Third, in order to maximize the amount of traffic the network can handle, one needs to limit the size of each cell. Now in order to guarantee coverage, one need to increase the size or the number of cells. In both cases, the increase îs accompanied by an increase in the level of noise, as well as an increase in difficulty of managing the OCC constraint. Finally, one notices also that it is not easy to jointly satisfy the OCC constraint and the coverage constraint. This last observation is important, since it irnplies the difficulty of producing feasible solutions for the APP.

In the previous discussion, we have presented in the most general way the concepts that highlight the antenna-positioning problem. The problem thus consists in choosing, among all the possible BS, a set ofBS which satisfies the coverage, handover, and OCC constraints, while minimizing the number of sites used, maximizing the ensured traffic and yield of the transmitters, and minimizing the noise level. Now, if one considers cells rather than BS, the APP can also be seen as a cover age problem of a plane surface: one wishes to cover the surface (working area) with various forms of cells with multiple constraints between these forms, while optimizing the objectives.

Formulation of problem

ln this part, the mathematical mode! for the APP used in this work is presented. The details of this mode! can be found in Reininger ( 1997), [START_REF] Reininger | Mode] for GSM Radio Network Optimisation[END_REF]Caminada ( 1998a, 1998b ). The model shown here reflects only a pmticular scenario. Other models are surely possible. However, the basic idea of the heuristic approach presented in this paper may be applied to other scenarios.

3./. Basic notations

• ST • Sq • Sm • TT • Ps • BS • BS/ • Cdb,p
•L set of ail the service test points STP in the working area, service threshold defi ned by a power value for a given station (Table 2), cellular phone station receiver sensitivity defined by a power value, set of the traffic test points TTP of the working area: TT c ST, antenna power, quintuplet (site, antenna, tilt, azimuth, Ps), set of selected BS that correspond to a network design, field strength received al a STT p E STP from a BS b E B S l, set of the candidate sites for a given network, The positioning of an antenna corresponds to the choice of a finite number of BS, denoted by B S 1, chosen among ail possible ones.

For each b belonging to BS1 we define ils cell Cell(b) as follows:

Cell(b) = {p E ST/Cdb,p 2: Sq and 1/b' E BSI b' cfabCd b .p > Cd b ,,p)
The second part of this de finition is important. lt indicates that the cell of a BS de pends not only on this BS but also on the other BS in the network.

Coverage constraint

Ali the STP of the working area must be covered by an antenna. This constraint is formally expressed by the following formula: In this work, we do not take into account cornponents containing fewer than MINC STP.

ST= U Ce/l(b) bEBSl

One connected compfment (OCC) constraint

MINC is an integer parameter to be fixed. In this study, MINC = 9 is used. 2 Figure 4 illustrates this principle.

One notices that the OCC constraint would be difficult to satisfy if the coverage constraint is taken into account at the same time. Indeed, when one adds a BS or increases the size of a cell to get a larger cover, one may "eut" a one CC cell into two cells or create a cell of multiple components.

Handover constraint

The handover area of a cell is defined by the set of STP p covered by the BS b, such that there is at least one other BS b', from which the field strength Cd b :p on pis greater than the threshold Sq, and at most 7 dBm above or below the fi eld strength Cd b ,p received from the BS b, or, handCell(b) = (p E Cell(b)/3 b' E BSJ and Cdb:p è" Sq and ICdb,,-Cdb:pl s 7dBm}

The handover constraint, which requires a non-empty handover area for each cell, is expressed by the following formula,

\lb E BSJ handCell(b) ')', 0 (3)
One notices that the model does not take into account the location and the number of handover points (Reininger and Caminada, 1998a). This definition corresponds in fact to a weak form of the handover requirement (number of minimal handover point= 1 per cell) and may be easily extended to include more than one minimal handover points. Computational simulations show that this weak form of handover is sufficient to ensure good handover in a network when the coverage constraint is satisfied. This observation may be interpreted as an indicator that the coverage constraint implies somewhat handover. We observe also that the handover constraint defined by ( 3) is satisfied as soon as there are a sufficient number of cells in the network.

Minimize the number of sites used

This objective is defined by:

min Le; x Yi, iEL { 1 , Y; = O,
if site i is selected otherwise ci is the cost of site i. In this paper, we suppose all the sites have a unit cost:

3 Vi E L, c; = 1 (4)
This restriction corresponds to networks in construction. There are, however, networks in extension for which the cost of a site depends on the operation that one carries out: creation of a new site, rnodific8.tion or suppression of an existing site in the initial network. We will discuss this point in the conclusion section and show that the resolution approach presented in the paper remains valid in this situation.

Minimize the noise level

Noise level estimation is not straightforward. If there is too rmicL overlap between cells, noise level will be very high, We have defined a cell as the set of ST? wîth the best signal corning from the same BS b. So Cdb,p is the best signal reccived st a given point p of the cell Cell(b). Ideally, each STP ofCell(b) should not reoeive more than h signais lower than Cd b .p and greater than the required sensitivity threshotcl Srn (.Section 2.2.). These h signais are used for handover. In our work, h value is fixed at :1, , bt!t lt i;; a pararneter that can be varied according to the model used. Signais after the hth �tnd greater than Sm are considered as noise. For each point p of Cell(b ), consider rhe sorted hst of signais greater than Sm:

Cdb.p :,: Cdhl.p :,:

• • • Cdbh.p :,: • • • Cdbk.p > Sm
Hence the noise level at point pis given by:

Y (p) = L Cdbj, P -Sm (k is dependent on p) h<j�k
The objective of minimizing the total amount of noise is expressed as follows:

min L ,(p) pEST

Maximize the amount oftraffic of the network

The total traffic a BS b can handle is given by the following formula:

traffic_BS (b) = trafficpoint(p) pETTnCell(h) (5)
According to this value, one will assign a number of transmitters TRX to this station by using the conversion Table 3. If the total traffic required by the TTP of a BS exceeds 43 Erlang, then the exceeding traffic may be lost It is for this reason that we introduce the concept of the traffic hold of a cell: This section presents the main characteristics of the APP, allowing us to have an idea about the difficulty of the problem. These characteristics are: a very high number of search combinations, a high complexity of computation, and a high requirement of memory.

Large number ofcombinations

The values of the parameters of antennas were discretîzed as follows:

• Ps E [26 .

. 55] and oPs = 2 dBm -+ IPsl = 15, • azimuth E [0 . .359] and oazimuth = 10' -+ jazimuthl = 36,

• tilt E [-15 .. 0] and otilt = 3 ° -+ ltiltl = 6.

These values were considered to be sufficient for the precision of cakulations and the resolution of the problems. This quantification is a first step towards reducing the number of search combinations.

Thus, an omnidirectional antenna has IPsl = 15 possible settings, and a directional one has IPsl x lazimuthl x ltiltl = 3240 possible settings. Thus, to put a BS at a site, we have 15 + 3240 + 3240 = 6495 possible choices (denoted by IBS,;,el). If ILI represents the number of candidate sites of a network number of candidate sites, we get Ill x IBS site l possible choices for a BS in the network.

To build a network is to find a combination of base stations, among the possible ILI x IBS s itel ones, which satisfies all the constraints and optimizes the objectives. We thus have 2ILI x IBSsitel potential cboices of confi gurations, even if a large number of them are not feasible.

For example, the network of figure l bas 568 candidate sites, and thus a search space of 2 s6s x 6 495 = iL689. 160 combinations.

Computational complexity

For the purpose of clarity and conciseness, we did not evoke all the computation rules for calculating electromagnetic fi elds. These rules, given in Reininger ( 1997), are primarily trigonometrical formulas of angles between STP and sites. A priori, an optimization process has to check at each stage that ail the constraints involved are satisfied, and to count those that are violated. For the OCC and handover constraints, the computing complexity gener ated by this task is about IBSll x ISTI, where IBSll represents the number of BS selected at a given stage of the optimization process.

Cell management, which is essential for the representation of most of the constraints and certain objectives, is very expensive to compute. Indeed, on the one hand, it is necessary to calculate the signais emitted by al! the selected BS on all the STP, and to sort these values for each STP, in order to determine the cells associated with the best fields, and, on the other band, to calculate the noise level and indicate the other fields higher than Sm.

For an average of 100 selected BS, the network of figure I requires about 100 x 17393 non-trivial calculations (arctang, real divisions, sorting of Cd, calculation of connected com ponents) to evaluate a configuration. This requires more than one million non-elementary operations. Computing the signals dynamically using a radio propagation modcl is very time consuming, and, therefore, cannot be used during an optimization process. Propagation loss data are thus pre-computed and stored in a propagation loss matrix where propagation loss has been prcdicted from each site to each RTP. Associated to these values we have an incidence matrix that gives the incidence angle for each couple (site, RTP). For each type of antenna, we also have the horizontal and vertical diagrams. Using this data, one can compute the fi eld strength Cd b .p by using the f ormulas detailed in Reininger (1997). Table 4 gives an idea about the quantity of data necessary for the problems that we solved.

Memory consumption

Typically, the data concerning the radio signal, the values of traftic, the coordinates of the sites, and the points of a network require more than 200 MB of memory.

General heuristic approach for the APP

The APPis thus highly combinatorial and very difficult to resolve. This remains true even for fi nding feasible solutions satisfying all the constraints. In particular, it is not at ail obvious how the OCC and coverage constraints can be satisfi ed simultaneously.

To tackle the APP, we have developed a heuristic approach, which is composed of three sequential phases: a pre-processing phase based on a fi.ltering principle, an optimization phase based on tabu search, and a post-optimization phase by fi ne tuning antenna para meters.

The pre-processing phase uses some .filtering criteria to eliminate or filter out many undesirable base stations (or cells) that cannot contribute to a good solution. We calculate, site by site and antenna by antenna, all the possible cells generated by each BS (site, antenna, power, tilt, azimuth). According to the filtering criteria, we decide for each cell whether the cell is kept or rejected. For example, if the filtering criterion used is the OCC constraint, then any cell violating this constraint will be definitively eliminated. Sirnilarly, if we want to limit the size of the cells, we may use this criterion to filter out the cells exceeding the desired size. Therefore, this pre-processing step allows us to greatly reduce the number of combinations of the search space. For network such as the one we used, this step retains typically 200,000 to 400,000 BS, from some 4,000,000 possible ones. Let us notice another important point: Computations of field strengths for each point in the working area are carried out at this phase and are no longer necessary during the optimization phase which is carried out by tabu search.

From the set of BS produced by the pre-processing phase, the optimization phase by tabu search will construct solutions by choosing a subset of BS that satisfy ail the constraints of the problem and optimize the objectives. To do this, the tabu algorithm, starting with an empty solution, tries to extend at each iteration its current solution by adding a BS and dropping some existing BS, if necessary, (for instance, to continue satisfying the OCC con straint). The choice of which BS is added at each iteration takes into account the objectives, and checks that the coverage constraint is satisfied.

Finally, the post-optimization phase is applied to improve the solution produced by the tabu algorithm. This phase can be used to optimize objectives or repair the rare con straints that remain unsatisfied. Post-optimization is realized by the fine-tuning of antenna parameters.

Pre-processing

Constraint based pre-processing

As previously mentioned, one of the main difficulties of the APP concerns the management of the OCC and coverage constraints. One well-known technique for constraint handling in general is the penalty-based approach. In this approach, constraints are considered as objectives and integrated into a weighted evaluation function:

i=m i=n f' = Lf; + LPj x cJ)(ci)
where:

i=l j= l

• f represents one initial objective,

• p; is a penalty to be defined for constraint c j ,

• cJ)(cj) equals l if ci is satisfied, equals 0 otherwise.

An advantage of this approach lies its flexibility, while its main drawback is the difficulty in fine tuning the penalties. Indeed, if some constraints are incompatible and bard to satisfy, these constraints may never be satisfied. This is precisely the case for the OCC and coverage constraints.

To cope with this difficulty, we introduce a special technique for handling the OCC con straint (the global coverage constraint is handled with the penalty approach, see Section 7.2). The basic idea is to use the OCC constraint in an active way to filter out "bad" BS which violate this constraint, and which consequently cannot contribute to a good solution. Only "good" BS are retained.

Recall that a candidate site can hast one omnidirectional (OMNI) antenna or one to three directional (LD or SD) antennas, which results in 6495 potential base stations. For a given site, all its BS confi gurations are not of equal interest. ln particular, a BS whose cell has many connected components can in no way be useful for a final solution due to the OCC constraint. Therefore, it would be beneticial to eliminate such ES from the search space from the beginning. Thal is what we do during the pre-processing phase. For every possible BS b = (site, antenna, power, tilt, azimuth) of every candidate site, we carry out all the necessary computations of field strengths to calculate the corresponding cell of the BS, and then count the number of its connected components having more than 9 STP (see Section 3.3). If the number of connected components is greater than one, i.e. the OCC constraint is violated, then the cell is not counted. Otherwise, the cell is recorded in a data structure together with all related information. Therefore, the left cell in figure 4 (Section 3.3) is kept, while the right one is rejected.

To calculate the connected components, we use the "scan line blob coloring algorithm", which is well known in the field of computer vision [START_REF] Ballard | Computer Vision[END_REF]. This algorithm scans the working area from top left to bottom right and labels STP belonging to the same cell with the same color. To accomplish this, it considers four points around the cun-ent one: the three neighboring points on top and the left neighboring point in an 8-neighborhood. For a single BS, this algorithm has a time complexity of O (1 Cell(b) 1).

This OCC constraint-based pre-processing phase allows one to significantly reduce the size of the search space, especially in the situations where many irregular obstacles are present in the terrain. Indeed forthe network of figure l, this filtering step retains only 294000 BS. The combinations in our search space are thus reduced from 2 3689160 (intractable) to 2 294000 (tractable).

The idea behind the pre-processing is very general and other criteria, like the noise level and the traffic, can be easily used separately or conjointly for this pre-processing phase. Such pre-processing techniques were implemented and experirnented upon in our study. However, we are unable to describe them further within the framework of this paper.

Therefore, the pre-processing phase offers great flexibility, allowing us to generate many different search spaces with different characteristics, which can then be used by the opti mization phase to produce various solutions. This flexibility represents a nice feature for multi-objective optirnization problems such as the APP.

Connectivity con.'itraint transformation

After this filtering stage, we have cells which satisfy the OCC constraint individually, and which have additional proprieties when other filterîng criteria are applied. Since the OCC is difficult to handle, this constraint must remain satisfied during the tabu optirnization phase, which consists in adding and dropping BS. For this purpose, we divide each cell into two parts, called the "kernel" and "border," and introduce a new constraint called the "kernel constraint."

Let 8Sq be a dBm value greater than 0: 8Sq > 0 dB m. For each cell, one considers the 2 following sets: Border:

kernel(b) = {p E Cell(b)/Sq + 8Sq S Cd1,.p) border(b) = {p E Cell(b)/Sq S Cd1,.p < Sq + 8Sq)

Cd�Sq

Then the kernel constraint states that the kernels of two different cells do not overlap:

V(b, b') E BSJ x BSI, b ,é b' ⇒ kernel(b) n kernel(h') = Z
Notice that the partition of a cell into kernel and border may be adjusted by the value given to ôSq. By varying the value of OSq, we can make the kernel constraint stronger or weaker. Now, during the tabu optimization phase, this kernel constraint is used so that the OCC constraint will remain satisfied. Therefore, the management of the OCC is replaced by handling this simpler kernel constraint.

The kernel constraint does not forbid the overlapping of the border zone of one cell with that of another celL Such an overlapping zone is typically used to ensure the handover constraint.

Let us now consider a more detailed example. Table 5 shows a partial solution involvîng 4 BS. Figure 6 gives the cells of these BS (left) togetherwith their kernel and borders (right).

In this example, ôSq = 4 dBm is used to defined the border areas. One notices that the overlap of the two adjacent cells concerns only their borders.

In summary, the pre-processing step generates, from the raw data of the problem, a reduced set of BS, as well as their representation in terms of kernel and border. The next step consists in constructing a solution from these BS. cell ➔ border u kernel A solution will be designed by putting together some BS in such way that all the STP of the working area are covered, the kemel constraint is respected, each cell shares a han dover area with some other cells, and the objectives are optimized. In practice, the handover constraint is automatically satisfied if a sufficiently large number of BS is present in a solution and if all STP are covered. The remaining task is essentially to satisfy the caver age constraint while optimizing the objectives, which is accomplished with a tabu search algorithm.

Optimization by tabu search

We now present the main ingredients of our optimization algorithm based on tabu search. For a cornplcte presentation of TS, the reader is invited to consult the comprehensive book by [START_REF] Glover | Tabu Search[END_REF].

1. Configuration

Let S be the set of BS selected by the pre-processing step. We define a first search space S to be the set of all possible binary vectors with IBI component:

Lets = (b 1 , ••• , b 1 g 1 )
be such a vector of S. Each component bi identifies a particular BS in B. If b i equals 1 then the corresponding BS is retained in the partial solution, otherwise, the BS is re_jected. The space S thus represents all the possible networks that can be built starting from B.

However, one notices that many configurations of S are not of interest, since they do not even verify the rule of antenna placement on a site ( one OMNI or 1 to 3 LD or SD per site, see Section 2.3). To translate this irnplicit constraint of the model we associate with each type of antenna a weight p: We now define the subspace Tc S verifying the rule of antenna placement on a site:

I p(OMNI) = 3, p : p(LD) = 1, p(SD) = L
T = {s ES/VIEL As(s,l) :C: 3)
It is clear that this reduced search space is of greater interest than the initial space S.

From T we now define a last search space X c T that respects the kernel constraint (Section 6,2): X= ((b,, ,,,,h 1 B1) ET/V;, V j ,i #} and b; = 1 and b j = 1 =; kernel(b,) nkernel(b j ) =0}

Therefore, the search space X includes al! the confi gurations that satisfy both the rule of an tenna positioning on a site and the kernel constraint. Since many non feasible configurations are excluded from X compared with the initial search space, we have IXI « ISI,

Configuration evaluation

In order to guide the tabu algorithm to visit the search space, one needs a function for evaluating the configurations. Since the APP involves multiple objectives and multiple constraints, the evaluation is somewhat complicated. In this work, we took a hierarchical approach to evaluate the configurations. Formally, for a given configuration s of X, it is evaluated by the fol!owing vector function. l; ( s ) = ( c 0( s) , f, (s ), fz(s), fs(s), f4(s)) where:

• co(s) = coverage(s) = number of STP covered by the cells of s,

• f 1 (s) = trafficHold(s) = sum of traffic held by ail the cel!s of s,

• f 2 (s) = noise(s) = sum of noise generated by each selected BS of s,

• f 3 (s) = number of sites where BS are installed,

• f4(s) = traffic Yield(s),

The first component c 0 of this evaluation function corresponds to the coverage constraint. This component takes priority over the other components (f 1 , f2, f 3 and f 4 ) that are related to the different objectives of the problem. A higher priority for the component c 0 helps to guide the search to find first feasible solutions. Another possibility would consider the component c 0 at the same level as the other objectives at the risk of never finding a feasible solution.

For the components f t, f2 , (1 and f4, any priority order may be used according to the im portance we give to each objective. For our presentation, we chose arbitrarily the following priority order P:

Given two configurations s1 and s2, si is said to be betterthan s2, denoted by ç(s 1) > ç(s2), if the following condition is verified: l'-ç(s1,s2) = (t.c0 (sl,s2), M 1 (sl,s2), M2(sl,s2), M3(sl,s2), M4(sl,s2)) denotes the vector variation of�.

We also use another fonction of evaluation: ç' (s) = (cS(s), f, (s), f,(s), f 3 (s), f4(s)) where: cS(s) = L w(p) where w(p) is a weight value greater than 0, and

pcovered n s ) {} ç(s) if w(p) = 1 V p EST.
We will see the usefulness of this evaluation fonction in Section 7 .5.

Neighborhood and move

We now introduce the neighborhood function Nover the search space X. More precisely, this fonction N : X ➔ 2 x is defined as follows.

Let s= (b 1 , b2, ... , b 1 8 1 ) E X and s' = (b;, b\, b 1 1l 1 ) E X then s' is a neighbor of s, i.e.

s' E N(s), if and only if the following conditions are met:

1) 3 1 i such that b, = 0 and b, = 1 (1 :" i :" IBI) 2) for the above i, V j #i E { 1 ... IBI} kernel (b,) n kernel (b j ) # 0 =;. b 5 = 0 Thus, a neighbor of s can be obtained by adding a BS (flipping a variable b, from O to l) in the current configuration and then dropping some other BS (flipping some b j from 1 to 0) to repair the kernel constraint violation. Consequently, a move mv to obtain a neighbor s' from where bi 1 ••• bin are variables linked to b i by the kernel constraint. That means that there is at least one same element (i.e. STP) in bath kernel (b;) and kernel(b j ) for j E J, = {i 1 .. ..• i,}. Such a moved is denoted by mv(i) = (b; : Ü➔ 1, b j 1 .. . b;,: 1 ➔Ü). Use s' = s + mv(i) to denote the neighbor of s obtained by applying mv(i) to s.

lt should be clear that from a configuration s = (b1, b 2 , ... , b 1 11 1 ), there are as many possible moves as the nurnber of variables in s having a value of O.

L et l s l = Lusllll b,, thens bas exactly IBI -lsl neighboringconfigurations (i.e. IN(s)j = lfl l-1 s 1 ).

Tahu List management and aspiration criteria

The main role of a tabu list is to prevent the search from shmi-term cycling (b j : I ----+ 0 ➔ l ➔ 0 ... ). Given the considerable quantity of calculations to be carried out for a move, we avoid imrnediately dropping a BS that has just been selected. To do this, a simple frequency-based mechanism is used:

Let Freq(i) be the frequency ofa move mv(i) (i.e. the number of times the BS b; is selected in the partial solution), then the number of iterations during which an element b i should not be resct to Ois equal to Freq(i). The number is called tabu tenure of the move mv(i).

In order to implernent the tabu list, a vector Tabu of IBI elements is used. As suggested in Glover and Lugana (! 997), each element Tabu(i), i.e. the tabu tenure of mv(i) ( 1 S i S IBI) records Freq(i) + t where t is the number of iterations when mv(i) is carried out. In this way, it is quite easy to know, at a later iteration t', if a mv(i) is allowed or not: if there exists j E J, = {i1 ... i,} such that TabuU) > t' then mv(i) is a forbidden move, otherwise, mv(i) is a possible move.

The tabu status of a move mv(i), such that s 1 = s + mv(i), is canceled if s' bas a bet ter quality than s, i.e. ç(s') > ç(s). This condition corresponds to a simple, yet important technique called "aspiration criteria."

Divers(fication

During the normal search process, the tabu algorithm chooses, at each iteration, one best move among all possible moves. This process is stopped and a diversification phase is triggered if no improved configuration is found during a fixed number of iterations. To do this, we re-calculate the weight of each STP in the following way:

If the STP is already covered by a BS, its weight equals 1, otherwise, the weight equals 1 + ISTj. One then replaces the evaluation fonction� by ç' (Section 7.2.). The evaluation fonction is changed in order to focus the search on the uncovered STP. This mechanism al\ows the search process to escape from a local optimum.

The number of iterations that trigger a diversification is relatively small, because one does not want to carry out too many non-improving moves, which require many calculations. This number is determined automatically using a simple idea. When our algorithm arrived at a local optimum, it selected ls'I BS, ls'"I being the number of elements with 1 in s'", We consider that if it carries out, from this point, ls"'I moves without improvement then it is ncccssary to diversify the search.

Let us notice that during diversification, the value of c; i (s) does not represent the real coverage ensured by the configurations. The real coverage c 0 (s) is kept up to date during the diversification.

General aff{orithm

The TS algorithm is composed of two iterative phases: search by exploitation and diversi fication. The algorithm's skeleton is shown below: The tabu algorithm stops when a diversification is not able to improve the solution with which the diversification starts. The algorithm returns the best solution s* found during the search. This TS algorithm requires no parameter to tune. Note that, ifwe are only interested in satisfying constraints, a stop condition may be added when the value of the!; component Co (i.e. coverage) is equal to 1sn.

Post optimization

Generally speaking, the post-optimization phase can be used to optimize any objective (the noise level, the total traffic supported ... ) or to enhance constraint satisfaction in case of constraint violation. The basic idea of the post-optimization phase is to improve a solution by fine tuning some antenna parameters.

As discussed in this paper, it is very difficult to satisfy the coverage and OCC constraints simultaneously. The proposed approach satisfies the OCC first and tries to satisfy the cov erage constraint during tabu optimization. Typically, tabu optimization alone can result in coverage greater than 99%. If a l 00% coverage is not reached, we use the following post optimization technique to cover the remaining 1 % of STP.

The principle of this post optimization process is simple: if one slightly increases the power of some BS selected in such a solution s*-to almost the feasibility level-we should be able to obtain the total coverage of the STP, without violating the other constraints. For this purpose, we seek the closest BS bmin of the uncovered STP (in terms of signal power): 8Cdb.p = Sq -Cd 6 _,(p is not covered so 8Cd > 0) bmin = b E B S 1 / 8Cd is minimum If the power (Ps) of bmin verifies the relation. Ps + 8Cd :s 55 dBm, then one can increase the power of this BS and repeat the operation. This simple process allows us to satisfy the coverage constraint in most cases.

Let us notice that for the post optimization phase, one may use other antenna parameters instead of power. Moreover, this kind of tuning may be easily applied to improve an existing network.

We have developed other techniques for improving objectives, such as traffic hold and noise level. For the purpose of simplification, these techniques are not presented here.

Experimentation and numerical results

Datasets

Computational experiments are carried out on two large and realistic data sets corresponding to two different types of networks: an urban network and a highway network. These test sets were generated by the CNET. which is France Telecom•s research laboratory. by using a very The main characteristics of these data are given in Table 6. We notice that the urban network bas fewer STP and more candidate sites than the highway network. In addition, the urban network bas a more homogeneous distribution of traffic, A priori this first problem would be thus less difficult than the highway network in terms of satisfying the coverage constraints and optimizing the ability to handle traffic. Of course this analysis does not take into account the propagation loss matrix, which is determining for resolving the APP, however, it does give a first classification of these problems,

Computational results

To salve these two problems, we followed the previously presented resolution proce dure, First, the pre-processing algorithm is run ta obtain the set B of BS satisfying the OCC constraints, This phase gives us typically 200,000 to 400,000 BS and takes about 4 hours on an ULTRA SPARC 30 with 512 MB of RAM, Then, the tabu optimization algorithm is executed to find feasible solutions satisfying the handover and coverage con straints. This phase is the most time consuming and takes about 24 to 48 hours to carry out 2,000 to 4,000 iterations, Finally, a post optimization algorithm is used ta further improve the solution found in the second phase or to enhance the coverage constraint if needed. This last step takes about 10 minutes, and thus is very fast compared with the fi r st two steps, There are several ways to obtain different solutions for a network. For example, one may run the tabu algorithm several times with the same B set . One may also use the pre-processing algorithm ta produce different B sets by varying the filtering criteria used, Table 7 shows three feasible, non-dominate solutions for each network, which are obtained with different .B sets.

Table 7 shows the values of the four objectives, Columns 3 ta 6 represent the number of omni-directional, large directional, and small directional antennas, and the number of base stations.

Appendixes 1 and 2 offer graphie representations of two solutions in Table 7, with each color representing a cell of a BS. These figures allow us to have a rough idea about the topology of the solutions found. For example, we observe that the cells are quite homogeneous, which is considered to be a desirable property of a network. Ap pendixes 3 and 4 give the two corresponding solutions in detail. From these detailed ta bles, we observe that the values of the "power" of antennas are rather close to the high value part. The repartitioning of lhe "tilt" values is almost homogencous. We also ob serve that there are very few omnidirectional antennas. This may be explained by the fact that there is neither constraint nor objective on the nurnber of BS, and several directional antenas can ensure the coverage of an omnidirectional antenna, with much better tuning possibilities.

In a similar way, for each network Table 8 presents two unfeasible solutions, where the OCC constraint is relaxed (number of OCC indicated in the second column), The main purpose of these results is to show the flexibility of the proposed approach, By comparing the results of Tables 7 and8, we observe that the violation of the OCC constraint increases the noise level. This observation constitutes an empirical justification of the importance of the OCC constraint

Comment.\' and discussions

Let us now make some cornments about these results and the proposed approach. The first comment concerns the feasibility of solutions for these networks. Given the high complexity of the data used and the way the data has been generated, it was unknown whether any feasible solution existed satisfying all the constraints of the model defi ned in section 3. It should be noted that among the three constraints, the OCC proved to be particularly difficult to manage. lndeed, we failed to satisfy this constraint with penalty-based approaches. The technique presented in section 6 for handling the OCC constraint proved to be much more powerful.

The second comment concerns the diversity of the solutions found. It is well known that for a multi-objective optimization problem, it is important to have a large number of diversifying or different non-dominate solutions. The experimentation shows that the proposed approach can produce many non-dominate solutions, thanks toits different solving phases.

The third comment concerns the quahty of the solutions found. This is a difficult issue, because there is no reference available concerning this matter. However, we know that radio engineers even with the help of the above-mentioned engineering tool, Parcell, found no feasible solution. Compared with such solutions, even without taking into account the factor of feasibility, the results produced by the approach presented in this paper are much better in tenns of service quality. Indeed, the noise level is much lower than in band-made solutions.

Finally, we would like to insist upon the flexibility of the proposed approach. The pro posed approach can be used naturally in an interactive environment, which is often nec essary for network design. In addition, it can be easily adapted to other models of the APP. Indeed, the mode( used in this work corresponds to a particular scenario; the con straints and objectives may be exchanged in other models. For example, the coverage constraint may be considered instead as an objective to be maximized. Similarly, the OCC constraint can also be bracketed in order to minimize the extra-connected com ponents. It is easy to see that the proposed approach can be applied directly in these situations.

Conclnsion

The heuristic aproach we propose in this paper constitutes one of the first studies dealing with antenna positioning and optimization of large and real size networks.

The proposed approach is composed of three sequential phases: a pre-processing phase based on a filtering principle, an optimization phase using tabu search, and a post optimiza tion phase based on fi. ne tuning. The pre-processing phase is parameterized allowing us to generate a variety of reduced sets of BS, of interest for devising an ultimate solution. The tabu algorithm is based on a binary representation of the search space, and integrates tech niques such as frequency-based tabu list management, and penalty-based diversification. Various techniques are available for post optimization, either to improve the objectives or to enhance constraint satisfaction.

This approach was applied to two large and realistic test data sets, corresponding to an urban network and a highway network. Results obtained on these data sets show that the proposed approach is very promising for antenna positioning and optimization of large networks. This approach proves to be flexible, robust and effective.

This work deals with the construction of networks from the ground up. Another very important and closely related problem concerns the optimization of networks already in place. The simplest from of optimization concerns only fi ne-tuning of antenna parameters: powers, tilt, and azimuth ... In addition to such tunings, one may also need to add new BS or new sites, deleting existing BS or sites. Bach ofthese operations has a possibly different cost.

A mode] of this evolution version of the APP is proposed in Reininger ( 1997). Adaptations of the approach presented in this paper to this model have been carried out and evaluated on large data sets. Once again, computational results show the effectiveness of the approach for dealing with this kind of network.

From this study, we may conclude that although the general APP is a highly combina torial and complex application, the problem can be resolved using a heuristic approach. Consequently, it must surely be possible to integrate such optimization approaches into engineering tools for radio network planning. We expect such industrial tools to be built and used by network operators in the near future.

Figure 3 .

 3 Figure 3. Cell corresponding to b = (356, LD, 0, 30, 38).

Figure 4 .

 4 Figure 4. Connected components of a single ce!!.

  (b) :o 43), otherwise. The objective of maximizing the arnount of traffic hold of a network is expressed by: max L trafficHold(b) bEBSJ 3.8. Maximize trqffic yield (6) Given the traffic hold of a BS b and the traffic capacity of b (see Section 2.3 and Table 3), we define the traffic yield for a cell by: trafficHold(b) trafficYield(b) = -----trafficCapacity(b) Hence, the objective of maximizing the traffic yield is expressed by the following formula: max L traffic Yield(b)

FigureFigure 5 .

 5 Figure 5 illustrates this partition.

Figure 6 .

 6 Figure 6. Four ccl!s (left) and thcir kerne\-bordcr representation.

  For a BS b we use p(b) to denote the value p (b antenna type) and define the following fonction: As: S x L r+ {0, 1, ,,,} As(s,l) = b=l andhon site l p(b)

a

  configuration s= (b1, b2, b:; ... b 1 r. i1) is characterized by a series of flipping operations: b; frorn O to 1 b,, from I to 0 bin from l to 0

Table 1 .

 1 Characteristics of a real network data set.

		Area width Area length	RTP	STP	TTP	Sum of traffic	Candidate sites
	Urban network	46.5 km	45.8 km	56792	17393 6652 2988,08 Erlangs	568

Table 2 .

 2 Examplcs of thresholds per service.

	Mobile station	Sq in dBm
	2 Watt incar	-78
	2 Watt outdoor	-8 4
	8 Watt outdoor

-90 Fiiure l. A real network working arca and its candidate sites.

Table 3 .

 3 Number of transmitters and traffic capacities.

Table 4 .

 4 Data for the APP.

	Set of candidate sites: L
	Set of RTP: R
	Sc! or STP
	Set of TTP
	Propagation !oss matrix
	Angle of incidence matrix

Table 5 .

 5 A partial configuration for the urban network.

	Site	Antcnna	Tilt	Azimut	Ps
	13!	LD	()	90	46
	356	LD	()	30	38
	397	LD	-6	300	46
	493	SD	-6	90

Table 6 .

 6 Characteristics of the 2 data sets. ParcelL Each data set is described by a file containing the coordinates of the candidate sites, a huge propagation Joss matrix calculated using a radio propagation model, and other relevant information concerning the working area, antennas, etc. The data sets are quite large, since each one requires more than 200 MB of memory.

				Area
					Mech		Trafic
		Service	width	length	size	RTP	STP TTP (Erlang) sites
	Unban Network	8 watt outdoor 46,5 km 45,8 km 200m 56792 17393 6652 2988,20 568
	Highway Network 8 watt outdoor 39 km	168,8 km 200m 164580 29954 4967 32l0,94 250
	powerful engineering tool called

Table 7 .

 7 Fcasiblc solutions for an urban nctwork and a highway network.

		Sites	OMNJ	LD	SD	BS	Noise	Traf1ic hold	Trafl-ic ycild
	Urban network	60	0	29	41	70 215135,10 2239,96	750{	62%.
		63	0	41	44	85	274504,5	2339,14	78%	86%
		94	0	0	154	154 216460,3	2988, 12	100%•	789i.
	Highway nctwork	58		35	67	103	331227,7	2251,50	70%	72o/r.
		78	0	28	128	156 385918,8	2889,55	90%	727,;
		86	0	39	78	117	278481,4	2797,75	87%	79<; {

Table 8 .

 8 Unfeasiblc configurations for an urban network and a hîghway network.occ Sites OMNI LD SD BS

	Noise	Traffic hold	Traffic yci!d

35.5

Acknowledgments

This work bas been carried out with the support of the European lT project ARNO (Al gorithms for Radio Networks Optimisation, Esprit No. 23243). The ARNO consortium is composed of the following partners: CNET-France Telecom (Prime Contractor), University of Cardiff (UK), GMD (D), ECTIA (F) and the Ecole des Mines d'Alès (F). We would like to thank gratefully A. Caminada and P. Reininger from the CNET for their work on the mode], and the other members of the project: S. Hurley, S.J. Chapman, O. Sarzeaud, A. Berry, J. Bendisch, H. Mühlenbein, R. Homs, and J. Zimmermann for many useful dis cussions. Thanks also go to the reviewers of the paper for their careful reading and helpful comments.

Appendix 1: Urban network cells

*This work is supported by the European ESPRIT IV projectARNO (Algorithms for Radio Network Optimisation, ESPRIT IV, No. 23243).

Notes

l. The formai definition of the notion of cell is given later in Section 3. t. 2. The choice, done in Reininger (1997) and Reininger and Camînada ( 1998a), is based on the fact that each point STP bas 8 neighboring STP. 3. Notice that non-uniformed costs have no incidence for the heuristic approach presented in this paper.


Angela Tursi
email: angela.tursi@cran.uhp-nancy.fr

Hervé Panetto
email: herve.panetto@cran.uhp-nancy.fr

Gérard Morel
email: gerard.morel@cran.uhp-nancy.fr

Michele Dassisti
email: m.dassisti@poliba.it

ONTOLOGICAL APPROACH FOR PRODUCTS-CENTRIC INFORMATION SYSTEM INTEROPERABILITY IN NETWORKED MANUFACTURING ENTERPRISES

Keywords: Enterprise Integration and Networking, Interoperability, Product Data Management, Ontology, IEC 62264, ISO 10303, 

published or not. The documents may come

Ontological approach for product-centric information system interoperability in networked manufacturing enterprises

INTRODUCTION

 Nowadays, information management is considered as a main requirement for products development in a networked environment. The new communication technologies, such as wireless technologies, RFID (Radio Frequency IDentification), etc., allow, from a technological point of view, to consider products as active mobile objects, embedding their own information structure, used and updated by the various actors during the product lifecycle. By this way, these products may be considered as systems, like other classical systems, that collaborate for a common objective (development, traceability, etc.). However, it is possible to demonstrate that the properties of such a system are in line with the so-called System of Systems concept (Maier, 1998), in which interoperability is a major concern. Indeed, a System of Systems (SoS) is a system arising from collaborative functioning of unit systems, each of them being able to work alone in order to perform its own operational mission (INCOSE 1 ). A SoS is such if it satisfies the following criteria (Maier, 1998):

1. Operational Independence of Elements 2. Managerial Independence of Elements 3. Evolutionary Development 4. Emergent Behaviour 5. Geographical Distribution Based on these characteristics, studies (Morel et al., 2007) try to demonstrate that, in some extent, an enterprise may be considered as a SoS, because it is recursively composed of systems (its elements), and has a particular finality, related to its skill domain, resulting from the execution of enterprise applications. In this paper, we postulate that a product embedding its own knowledge (information) and equipped with communication facilities can be considered as a component element (an active object) of such a SoS. Indeed a product is able to "act independently" (criteria 1, 2) during its lifecycle if it embeds an information model that gives it the possibility to store data necessary to ensure its existence. The other SoS criteria, related to the enterprise, are not put at fault when one SoS element is an active object. The main objective of our research activities is then to define the information model necessary to the product to become an active object. With such information, it may be interoperable per se with the many applications involved in manufacturing enterprises and, as far as it embeds knowledge about itself, storing all its technical data, it will be able to act as a common source of understanding between enterprises applications (Tursi et al, 2007). The paper puts a first step in this direction by endeavouring existing standards related to product technical data modelling for the definition of products information, allowing a non ambiguous model to represent knowledge and concepts, processable by the many enterprise applications adopted in manufacturing environment. A second step will be to formalise this information model as a Product Ontology, thus including domain rules, able to express and share product knowledge among systems. An ontology is an explicit specification of a shared conceptualization (Gruber, 1993), which allows the representation of domain's knowledge. It allows the formalization of the semantics of objects, and then it allows to formalize and to identify the modelling concepts and their dynamic behaviour, in order to express and to share this knowledge. The shape of the paper is as following: after introducing the concept of active mobile object in section 2, section 3 introduces standards concerned on information interoperability that are used as a base for defining the product ontology; section 4 presents a case study of instantiation of the standards models defining, by a bottom-up approach, the common concepts that will be a base for our product ontology, and finally in section 5 future research activities and conclusions are presented.  

PRODUCT AS AN ACTIVE MOBILE OBJECT



In order to better optimise its performance, heterogeneous enterprise applications, either at business or at manufacturing levels, either inside a single enterprise or among networked enterprises, need to share information and to cooperate. This information may be stored, processed and communicated in different ways by different applications, according to the scopes for which these have been collected and they will be used. Each enterprise application, in fact, uses an information repository, which refers to a Reference Information Model (RIM). A RIM specifies the structure and embeds the semantics of the information treated, in relation to the scope of the application to which it is devoted (Dassisti et al., 2006). However, a problem of misunderstanding when information is exchanged between enterprise applications can occur, due to different view points, for which they have been developed and, consequently, a risk of loss of information semantics may arise when exchanging between heterogeneous systems. This "Babel tower effect", induced by the heterogeneity of applications, of users and of domains may cause information understanding problems, leading systems to fail at collecting information from different and heterogeneous sources to effectively ensure their local objective. This problem of managing heterogeneous information coming from different systems, in order to achieve a unique comprehension, falls within the umbrella of interoperability problems. Generally speaking, interoperability can be defined as that intrinsic characteristic of a generic entity (organization, system, process, model, …) allowing its interaction with other entities -to a different extent of simplicity -to cooperate for achieving a common goal within a definite interval of time, while pursuing its own specific goal. Interoperability can defined as the ability of two or more systems or components to exchange information and to use the information that has been exchanged (IEEE, 1990).

In order to manage heterogeneous information, it is mandatory to develop models able to trace all relevant information related to the product lifecycle (design, manufacturing, sales, use and disposal). This information is, in fact, quite often scattered within organizations: it is a matter of the materials adopted, of the applications used to manage technical data (e.g: Product Data Management systems (PDM)), of the applications that manage business data (e.g.: Enterprise Resource Planning (ERP)) and, finally, of the applications that manage manufacturing data (e.g.: Manufacturing Execution Systems (MES)). Standardisation initiatives, for instance in the frame of ISO (ISO 10303) and IEC (IEC 62264), try to answer this problem by formalising the knowledge related to products technical data: nevertheless this approach is rather prescriptive, because it forces users to translate information from generic concepts to more practical and ad-hoc ones. This paper postulates that, the product, along its life cycle, is the centred object from which all applications have a specific view. It could then be possible to define a common information model, to support information exchange between the product views and the many applications that interact with them. This model intends to specify an embedded Product Ontology that may be formed during the product lifecycle by the force of necessity of using it to communicate with the applications. The concept of embedding is related to the "pertinence" of the information structure: whenever related to the product information (technical, managerial, operational …) assumes a local (say embedded) meanly independently of the specific IT application requiring it (ERP, MES, PDM …). In order to overcome questions pertinent to information exchange and its support, such as loss of information, problems of misunderstanding as well as redundant activities, it is necessary to define an ontology-based information model, to support information exchange between IT applications adopted to control different manufacturing processes and systems.

An ontology provides formal definitions of basic concepts in a domain and the relationships among them in a usually logic-based language (Gruninger and Lee, 2002). It is a specification of a conceptualization of an application domain of interest together with axioms that do constrain the possible interpretations for the defined concepts.There have been, in many different sectors, some efforts examining the use of ontologies in supporting the semantic integration task (e.g. Guo et al., 2003;Katranuschkov et al. 2003;Gehre et al., 2005;Lima et al. 2005;Patil et al., 2005;Terzi, 2005;Terzi, et al. 2007). (Patil et al., 2005) is related to the NIST initiative2 on Product Engineering. (Terzi, 2005) has also been implemented in the frame of the PROMISE-PLM European project3 . However, all these works have been either related to geometry data or have focused their study in the technology rather than to the conceptual view of product data exchange. Aware of the efforts demonstrating the integration of models using ontologies, the matter of the approach, discussed here, is how to formalise such Product Ontology, so it is feasible to embed information into the product and bringing and using them without further misunderstanding. Formalization means to provide a structured model of the information concepts and their semantics. Once the ontology is embedded, it represents a comprehensive structure of all the possible information pertinent to the product and genealogy. As far as the product is processed, the related information can be "engraved" on it, with regards to the embedded ontology. This represents a significant advantage in terms of information retrieval and future use.

In this sense, standards efforts can be taken into account, in term of useful bases for the ontology of the domain. The product may then be considered as active, as far as it participates to the decisions making, providing knowledge about itself.

Through the formalization of this model, the product may be considered as interoperable per se as far as it embeds local information (knowledge about itself), as it stores all its technical data, provided that these are embedded on a common model, providing mappings from and to the enterprise applications (either inside a single enterprise or between networked enterprises) with respect to its life cycle.

This paper discusses these ideas and traces a research roadmap on this topic, to explore the possibility to make enterprise interoperable on the basis of productcentred information view.

STANDARDS FOR PRODUCT DATA REPRESENTATION AND EXCHANGE



The integrated management of all the information regarding the product and its manufacturing is one of the more complex questions that characterize today's environment, defining a sort of "product-centric" or "product-driven" paradigm (Morel et al., 2003). We have studied a comprehensive set of standards related to product data and product lifecycle management (Terzi, 2005) and we have then demonstrated that information interoperability asks for common shared approaches: in fact, interesting standardisation initiatives already exist, such as the IEC 62264 set of standards (IEC 62264, 2002) and the ISO 10303 technical specifications (ISO/TS 10303, 2004. They try to solve the problem of managing heterogeneous information coming from different systems by formalising the knowledge related to products technical data. Both these standards will be here addressed because they are related to Product Data Management at the business and the manufacturing levels of enterprises (B2M, Business to Manufacturing). In the following sub-paragraph a short review will be done of these two standards. The IEC 62264 set of standards specify a set of reference models for information exchange to facilitate the integration of business applications and manufacturing control applications, within an enterprise. The full standard is composed by six different parts designed for defining the interfaces between enterprise activities and control activities. Among all its parts, the part 1 specifies the relevant functions within an enterprise and within the control domain of an enterprise, stating which objects are normally exchanged between these domains. The key aspects for integrating the business applications and the manufacturing operations and control applications are the information structures and exchanges, related to the products, managed by activities, applications, processes, resources, and functions. The boundary between the enterprise manufacturing operations and control domains are signed by models: hierarchy model that describes the levels of functions and domains of control associated within manufacturing organizations; data flow model that describes the functional and data flows within manufacturing organizations; object model that describes the information that may cross the enterprise and control system boundary.

There is a set of eight object models that specifies all concepts for enterprise-control integration: three are related to the resource hierarchy (Personnel, Equipment, Material), the process hierarchy (Process Segments, Product Definition), and to the production (Production Schedule, Production Performance, Capability Definition). B2MML4 (Business to Manufacturing Markup Language) is an XML (eXtensible Markup Language) implementation of the IEC 62264 part 1. It consists of a set of XML schemas, developed by the World Batch Forum, written using the World Wide Web Consortium's XML Schema language (XSD) that implements the standardised data models. B2MML is meant to be a common data format to link business enterprise applications (such as ERP systems) with manufacturing enterprise applications (such as MES).

In particular, MES functions relate to production monitoring including materials (raw and finished) and resources (equipment and personnel) traceability information.

This standard shows a first effort in determining a model that intends facilitate enterprise applications interoperability.

In order to adopt a common understanding for the manipulation of models, we choose the UML (Unified Modeling Language), and more especially the class diagram formalism, as a common conceptual language for representing the concepts specified in the standard.

ISO 10303 Technical specifications

 ISO has been pushing forward the development of standards and models to foster the exchange of information related to goods and services (ISO, 2004).

Efforts like ISO 10303 STEP -STandard for the Exchange of Product model data -have tried to deal with the issues of integration and interoperability problem. STEP represents the standard for the computer-interpretable representation of product information and for the exchange of product data. It aims to provide a neutral mechanism capable of describing products throughout their lifecycle. Nowadays, STEP has been recognized as appropriate to help in the integration of manufacturing systems in industries such as automotive, aircraft, shipbuilding, furniture, building and construction, gas and oil. A significant solution for PDM (Product Data Management) data exchange is the Unified PDM Schema, which is a basic specification for the exchange of administrative product definition data. It has been created by unifying all PDM data between all existing STEP Application Protocols, and allows the exchange of information that is stored in PDM systems. This information typically forms the metadata for any product. In order to deal with the increasing demands on product models exchange, the standard has specified a set of STEP reusable modules related to PDM. These modules are now published as technical specifications (TS) and concern all related information attached or describing products technical data such as product structure, configuration control, persons and organisations, etc. PDM systems maintain a single copy of the product master data in a secure vault; the data are then distributed to those departments requiring them: modified, updated design data are then resaved in the vault. Data integration ensures that the information describing product design, manufacturing and life cycle support is defined only once; STEP data integration eliminates redundancy and the problems caused by redundant information. STEP uses the EXPRESS language for describing data type, constraints on data type and relationship between data type. However, Application Protocols are required to contain a representation of the information in both EXPRESS and EXPRESS-G. EXPRESS-G is a diagramming technique supporting a subset of the EXPRESS language.

In this case, we also use the UML Class Diagram formalism as a common conceptual language for specifying the concepts specified in STEP PDM.

A CASE STUDY

The STEP PDM Schema is a reference information model for the exchange of a central, common subset of the data being managed within a PDM system. A PDM system is able to integrate and manage all applications, information and processes that define a product during its lifecycle, from design to manufacture, and to enduser support (Liu and Xu, 2001). This means that typical product-related information includes geometry, engineering drawings, project plans, part files, assembly diagrams, product specifications, numerical control machine-tool programs, analysis results, correspondence, bills of material, engineering change orders, and many more. However, it is possible to find some of these information scattered also in the IEC 62264 models.

For the sake of simplicity, we will now demonstrate this only by defining some mappings between the PDM schemas and the IEC 62264 material model. Of course, the current work is ongoing taking into account all models.

The IEC 62264 Material Model defines the actual materials, material definitions, and information about classes of material. In this model, material means not only raw materials but also consumables, parts and all other products needed for the production. Material information includes the inventory of raw, finished, and intermediate materials. Material classes are defined to organise materials. A Material definition is a means to describe goods with similar characteristics. A Material Lot object identifies a specific amount of material, countable or weighable, and it has specific properties (Fig. 1).

In order to verify that the same information is modelled in different way by the two standards, we have denormalised and conceptualised PDM STEP Schema and IEC 62264 models and represented them using the UML class diagram notation. In this way, it is possible to have a common minimum denominator which allows the matching and the mapping between the two standards.

Fig. 1 The conceptualised IEC 62264 Material Model

The following step has been the instantiation of the standards models based on a real production system. Just to provide a more familiar example of real production system, we refer to a simple test case made between two facilities. The proposed case study concerns the design and the production of a product. It is based on a set of enterprise systems, distributed on two production sites, one in Italy and one in France.

The product is conceived and designed in the Department of Mechanical and Management

Engineering of the Politecnico di Bari, in Bari, Italy.

The definition of product is driven by market or by customer requirements and forecasting. Technical and geometrical information, joined to business information, such as the required quantity of pieces, are stored in a memory chip (a RFID), and structured in the information model that implements the Product Ontology. This digital product is sent to the Atelier Inter-Établissements de Productique Lorrain (AIPL-PRIMECA) of the Nancy-University, France. AIPL has to manufacture the product on the base of information drawn from the Product Ontology, retrieved from the chip. In this industrial production system, it is possible to manufacture 4 types of base part from a product family and then assemble them in order to compose 6 types of product (Fig. 2).

At the end of production process, the manufactured product will be sent to DIMeG in oder to be delivered to the customer. In this product-centric information system, these heterogeneous applications have to interoperate with the product, in order to store and to draw the pertinent product information.

As previously mentioned, to support information exchange between the product and the many applications that interact with him, it is necessary to define a common information model, which intends to specify an embedded Product Ontology. This common information model can be defined starting from IEC 62264 models and the ISO 10303 technical specifications ones. Both these standards are related to product data management at the business and the manufacturing levels of enterprises (B2M).

From the standards analysis, it's possible to state that Material Model, Process Segments Model and Production Schedule Model epitomize the product information during the first steps of the process, during the product definition and production planning phases, carried out at the DIMeG. Some ISO 10303 TS standard concepts will be integrated in this stage. Material, Equipment and Personnel Model, Production Schedule Model, Capability Definition Model, instead, epitomize the product information during the product manufacturing phase carried out at the AIPL.

The bill of material (BOM) is one of the crucial product technical data in the production management domain as well as in the information technology that supports it (Xu et al, 2008): the BOM represents the base issue of integrating product design system with production planning system. The STEP PDM Schema supports hierarchical product structures representing assemblies and the constituents of those assemblies, as shown in figure 3: this product structure corresponds to the traditional engineering and manufacturing bill of material indentured parts list.

The Assembly_component_relationship class represents the general relationship between two parts, one a definition of a component and the other a definition of the parent assembly. This entity is typically instantiated as the subtype Next_assembly_usage, which represents an unique individual occurrence of the component as used within the parent assembly. The subtype Promissory_usage, instead, represents the usage occurrence of a component within a higher-level assembly that is not the immediate parent. The subtype Component_upper_level_identification identifies a component of an assembly with respect to an upper level in the assembly structure.

The Assembly_component_relationship is established between two instances of Product_view_definition: the relating view of Product_version of assembly and the related one of the Product_version which plays the role of component. A Product_view_definition is a collector of the properties that characterize the Product_version in the initial_context and possibly additional_contexts.

A Product_version is a revision or a collector of the definitions of the revision of Product.

An Assembly_component_relationship defines the quantity of the usage of the component in an assembly. This part of STEP PDM represents the so called Engineering BOM (EBOM). The EBOM lists items according to their relationships with parent products as represented on assembly drawings. Thus, EBOM just represents the product structure from the engineering point of view, not from the manufacturing viewpoint, and it cannot be directly used in the material requirements planning (MRP) system, generally a component of an Enterprise Resource Planning system (ERP). From a B2M interoperability point of view, the MES needs a manufacturing BOM (MBOM) to schedule, in real time, the different work in progress (WIP) orders. The MBOM represents the assembly building-up the way a product is manufactured. The MBOM is generally generated with human intervention based on EBOM and complementing some manufacturing information from the bill of process (BOP).

Thus, one of the key problem of integrating product design system with production planning system is the transformation of engineering BOM into manufacturing BOM (Xu et al, 2008). These considerations allow understanding why and how the Product Ontology can be useful for making interoperable enterprise applications: through a common information model embedded on the product, which stores product data and information, engineering and manufacturing ones, it will be possible to support information exchange between the many applications that interact with the different product views. In this paper we focus mainly on the proof of concepts regarding the definition of mappings between both standards by instantiating the IEC 62264 Material Model and the corresponding STEP PDM modules models on a few parts. (Fig. 4,5). The figures 4 and 5 show how information related to product properties, such as diameter for example, is defined in both models, even if they are represented in a different way. Indeed, in STEP PDM modules (Fig. 4), the P09 is a product, which is member of Pxx family. It is possible to assign diameter property to P09 through the class-relationship assigned_diameter, which is linked to the numerical value through the representation concept. However, we observe that it is not possible to distinguish the definition of a concept for an entity from the value that it assumes. In the same way, in the IEC 62264 (Fig. 5), we note that the diameter concept is defined for Pxx class: P09 part belongs to Pxx class, consequently it has a diameter, but it may have also other specific characteristics. Finally, the value of P09 diameter is specified as property of a precise P09 lot.

In order to demonstrate that the models describe the same information, our approach is based, firstly, on a syntactical analysis whose aim is to compare the instances defined in both models and then based on semantics analysis, studying properties of the shared objects. The result of the syntactical analysis is presented in the Table 1. Finally, the semantics analysis suggests the possibility to do a mapping between the instantiated concepts. However each relation between different concepts can be studied and it is possible to try semantic correspondences between them (Baïna, 2006) in order to compare the contained information. Different cases can occur: equivalence, represented by  symbol (same definition for concepts semantics in the two standards), inclusion, represented by  symbol (a semantic concept includes the other one), and intersection, represented by ∩ symbol, (the concepts intersection defines the common sense of the two concepts). This will be the next step in our approach towards a common model, embedded into the products, which store all technical data along its life cycle: this represents the starting point for the development of our Product Ontology. This case study then shows how ISO 10303 and IEC 62264 initiatives formalise the knowledge related to products technical data and, thus, they are useful to define the information model that can allow to consider the product as an active object: other standardisation initiatives may be considered in order to have a full model that stores all technical data along the product lifecycle. For analysing the semantics relationships between both concepts, we choose the First Order Logic (FOL) to express predicates formalising concepts of models in order to define, precisely, the mapping between them.

From the syntactical analysis (Table 1), we deduce one or more FOL predicates (1), ( 2), (3), (4) (Table 2). Each of them formalises mapping between STEP PDM concepts and IEC 62264 ones represented by a DLite description logic (Calvanese et al, 2002). Finally, we have started the formal verification of these mapping rules through Protégé 5 , a suite of tools to construct domain ontology, by applying skill-based axioms through an inference engine and using it with knowledge-based applications.

CONCLUSIONS AND FUTURE RESEARCH



Starting from the consideration that the product is the common added value, for which each part of the organization works, and it is the common element perceived in the same way by all manufacturing operators, we have postulate that it is possible to consider the product as an interoperable system per se, as far as it embeds knowledge about itself as it stores all its technical data. This information can be structured in a common formal model, including domain rules, which is able to provide mappings from and to the enterprise applications information, either inside a 5 protege.stanford.edu single enterprise or between networked enterprises, with respect to its life cycle. The matter of the proposed bottom-up approach is then the formalisation of knowledge and skill around products and semantics of standard modelling concepts, for making interoperable enterprise applications related to products views. Our current work is, based on these concepts mapping coming from standards, the definition of a Product Ontology to contribute to an interoperability solution between active mobile objects and enterprise applications that will manage them.



  3.1. IEC 62264 set of standards.

Fig. 2 .

 2 Fig.2. Parts and some products produced at the AIPL Each enterprise of this case study is equipped with its enterprise systems (i.e. Windchill PDM and SAP R/3 for DIMeG or DS SmarTeam and Sage X3 for AIPL), dedicated to specific tasks (engineering tasks or manufacturing ones) and provided by a particular vendor. In this product-centric information system, these heterogeneous applications have to interoperate with the product, in order to store and to draw the pertinent product information. As previously mentioned, to support information exchange between the product and the many applications that interact with him, it is necessary to define a common information model, which intends to specify an embedded Product Ontology. This common information model can be defined starting from IEC 62264 models and the ISO 10303 technical specifications ones. Both these standards are related to product data management at the business and the manufacturing levels of enterprises (B2M). From the standards analysis, it's possible to state that Material Model, Process Segments Model and Production Schedule Model epitomize the product information during the first steps of the process, during the product definition and production planning phases, carried out at the DIMeG. Some ISO 10303 TS standard concepts will be integrated in this stage. Material, Equipment and Personnel Model, Production Schedule Model, Capability Definition Model, instead,

Fig. 3 .

 3 Fig. 3. A conceptualized model of the BOM as based on STEP PDM

Fig. 4

 4 Fig. 4 An extract of the instantiated STEP PDM modules.

Fig. 5

 5 Fig. 5 An extract of the instantiated IEC 62264 Material Model.

Table 1

 1 Syntactical Analysis of concepts

	AIPL objects	STEP PDM modules concepts	IEC 62264 concepts
	Pxx	Pxx: Product	Pxx: MaterialClassType
	P09	P09: Product	P09: MaterialDefinitionType
			P09_Lot: MaterialLotType
	Diameter	Diameter: Independent_property	Diameter: MaterialClassPropertyType
	Diameter_value_with_unit	Diameter_value_with_unit:	Diameter_value_with_unit:
		Numerical_item_with_unit	MaterialLotPropertyType

Table 2

 2

	defining_a_grouping
	value_of
	value
	FOL Predicates
	Product(Pxx)  Product(P09)  Product_relationship(Member_of) 
	Member_of(Pxx, P09)   MaterialClassType(Pxx)  MaterialDefinitionType(P09) Member_of.relation_type="Membership"	(1)
	 defines_a_grouping(Pxx, P09)
	Product  MaterialClassType
	Product  MaterialDefinitionType
	Independent_property(Diameter)  Product(P09)  Assigned_property(Assigned_diameter) 
	Assigned_diameter(Diameter, P09)
	 defines_a_grouping(Pxx, P09)   MaterialClassType(Pxx)  MaterialDefinitionType(P09)	(2)
	MaterialClassPropertyType(Diameter) 
	MaterialClassProperty(Pxx, Diameter)
	Independent_property  MaterialClassPropertyType
	Numerical_item_with_unit  MaterialLotPropertyType

INCOSE (International Council on Systems Engineering), http://www.incose.org

http://www.mel.nist.gov/msid/pe.htm

http://www.promise-plm.com

B2MML (Business to Manufacturing Markup Language), http://www.wbf.org