R Ravaud

G Lemarquand
email: guy.lemarquand@univ-lemans.fr

MAGNETIC FIELD PRODUCED BY A PARALLELEPI-PEDIC MAGNET OF VARIOUS AND UNIFORM POLAR-IZATION

This paper deals with the modeling of parallelepipedic magnets of various polarization directions. For this purpose, we use the coulombian model of a magnet for calculating the magnetic potential in all points in space. Then, we determine the three components of the magnetic field created by a parallepiped magnet of various polarization direction. These three components and the scalar magnetic potential are also expressed in terms of fully analytical terms. It is to be noted that the formulas determined in this paper are more general that the ones established in the literature and can be used for optimization purposes. Moreover, our study is carried out without using any simplifying assumptions. Consequently, these expressions are accurate whatever the magnet dimensions. This analytical formulation is suitable for the design of unconventional magnetic couplings, electric machines and wigglers.

INTRODUCTION

Permanent magnets are widely used in many engineering and industrial applications. Their utilization requires calculation methods based on the fundamental laws of the magnetostatics [START_REF] Babic | Calculation improvement of 3D linear magnetostatic field based on fictitious magnetic surface charge[END_REF][START_REF] Babic | Improvement in the analytical calculation of the magnetic field produced by permanent magnet rings[END_REF]. Two great kinds of applications can be identified. The first ones use parallelepipedic permanent magnets while the second ones use arc-shaped permanent magnets. This paper deals only with parallelepipedic permanent magnets. However, this study can also be extended to the case of cylindrical permanent magnet topologies.

The first analytical studies dealing with the modeling of parallelepiped magnets were studied by Akoun [START_REF] Akoun | 3D analytical calculation of the forces exerted between two cuboidal magnets[END_REF] and Yonnet [START_REF] Yonnet | Rare-earth Iron Permanent Magnets, Ch. Magnetomechanical devices[END_REF].

Then, several analytical studies were carried out by using the coulombian model of a magnet [START_REF] Ravaud | Discussion about the analytical calculation of the magnetic field created by permanent magnets[END_REF][START_REF] Furlani | Field analysis and optimization of ndfeb axial field permanent magnet motors[END_REF]. The interest of using fully analytical approaches lies in the fact that they have generally a lower computational cost than finite element methods [START_REF] Furlani | Permanent Magnet and Electromechanical Devices: Materials, Analysis and Applications[END_REF][START_REF] Furlani | A three-dimensional field solution for permanent-magnet axial-field motors[END_REF][START_REF] Furlani | A three-dimensonal field solution for radially polarized cylinders[END_REF][START_REF] Jian | Analytical calculation of magnetic field distribution in coaxial magnetic gears[END_REF]. Moreover, analytical approaches are suitable for parametric optimizations using permanent magnets [START_REF] Jian | Analytical calculation of magnetic field distribution in coaxial magnetic gears[END_REF], or coils carrying producing magnetic fields [START_REF] Blache | New structures for linear displacement sensor with hight magnetic field gradient[END_REF][START_REF] Conway | Noncoaxial inductance calculations without the vector potential for axisymmetric coils and planar coils[END_REF]. The magnetic field created by parallelepipedic magnets can be expressed in fully analytical parts whereas the magnetic field produced by arc-shaped permanent magnets is generally based on special functions [START_REF] Babic | Validity check of mutual inductance formulas for circular filaments with lateral and angular misalignments[END_REF][START_REF] Ravaud | The three exact components of the magnetic field created by a radially magnetized tile permanent magnet[END_REF][START_REF] Perigo | General expressions for the magnetic flux density produced by axially magnetized toroidal permanent magnets[END_REF][START_REF] Rakotoarison | Using coulombian approach for modeling scalar potential and magnetic field of a permanent magnet with radial polarization[END_REF][START_REF] Varga | Magnetic field of a uniformly magnetized hollow cylinder[END_REF][START_REF] Zhilichev | Calculation of magnetic field of tubular permanent magnet assemblies in cylindrical bipolar coordinates[END_REF][START_REF] Selvaggi | Computation of the three-dimensional magnetic field from solid permanent-magnet bipolar cylinders by employing toroidal harmonics[END_REF][START_REF] Selvaggi | Calculating the external magnetic field from permanent magnets in permanent-magnet motors -An alternative method[END_REF][START_REF] Selvaggi | Computation of the external magnetic field, near-field or far-field from a circular cylindrical magnetic source using toroidal functions[END_REF][START_REF] Ravaud | Comparison of the coulombian and amperian current models for calculating the magnetic field produced by arc-shaped permanent magnets radially magnetized[END_REF].

This paper presents 3D analytical expressions of the magnetic field created by a parallelepipedic permanent magnet of various polarization direction. Indeed, its polarization can be along the x, y and z direction, in the (x-y), (x-z) and (y-z) planes but also in any direction in the coordinate system. Such a study is clearly justified by the progress in manufacturing permanent magnets with more complicated magnetizations. Moreover, permanent magnets with various polarization directions allow us to confine the magnetic flux in ironless structures [START_REF] Xia | Analytical magnetic field analysis of Halbach magnetized permanent-magnet machines[END_REF][START_REF] Wang | Design optimisation and comparison of permanent magnet machines topologies[END_REF] and to optimize the magnetic field shape in electric machines [START_REF] Ravaud | Discussion about the magnetic field produced by cylindrical Halbach structures[END_REF].

We present first the 3D analytical expression of the magnetic scalar potential created by a paralellepipedic magnet of various polarization direction: Such an expression is useful for the study of ferrofluids used with permanent magnets [START_REF] Ravaud | Mechanical properties of a ferrofluid seal: Three-dimensional analytical study based on the coulombian model[END_REF][START_REF] Ravaud | Design of ironless loudspeakers with ferrofluid seals: Analytical study based on the coulombian model[END_REF]. Indeed, the magnetic pressure of the ferrofluid seal requires the accurate knowledge of the magnetic potential in all points in space.

The second part of this paper presents the analytical expressions of the three components of the magnetic field created by a parallelepipedic magnet of various polarization direction.

ANALYTICAL EXPRESSION OF THE MAGNETIC POTENTIAL PRODUCED BY A PARALLELEPIPED MAGNET WITH A UNIFORM AND ARBITRARY POLARIZATION

Notation and Geometry

We present in this section the 3D analytical expression of the magnetic potential created by a parallelepiped magnet of various polarization direction. To do so, let us first consider the representation shown in Fig. 1.

Its dimensions are given by (x 2 -x 1 ), (y 2 -y 1 ), (z 2 -z 1 ) and its polarization is denoted J. By using the notations shown in Fig. 1

, this J 0 X Y x 1 x 2 z 1 z 2 y 1 y 2 Z Figure 1.
Representation of a parallelepiped magnet of various polarization direction.

polarization vector is expressed as follows:

J = J cos(θ) sin(φ) u x + J sin(θ) sin(φ) u y + J cos(φ) u z (1)
We define the permanent magnet surface as follows:

dS 1 = +dydz u x dS 2 = -dxdz u y dS 3 = -dydz u x dS 4 = +dxdz u y dS 5 = -dxdy u z dS 6 = +dxdy u z (2)

Analytical Formulation

In the coulombian approach, the magnetic potential created by the parallelepipedic magnet is given by:

Φ(x, y, z) = 6 i=1 1 4πµ 0 S i J • dS i | r -r i | (3)
For the rest of this paper, we adopt the following notation:

ϑ (ijk) {•} = 2 i=1 2 j=1 2 k=1 (-1) i+j+k (•) (4)
By using the egality

ξ ijk = (x -x i ) 2 + (y -y j ) 2 + (z -z k ) 2
, the magnetic potential created by a parallelepiped magnet of various polarization direction is expressed as follows:

Φ(x, y, z) = J 4πµ 0 ϑ (ijk) {(sin(φ) cos(θ)Φ 1 + sin(φ) sin(θ)Φ 2 + cos(φ)Φ 3 } (5) with Φ 1 =z k + (x -x i ) arctan z -z k x -x i + (y -y j ) log [z -z k + ξ ijk ] -(x-x i ) arctan (y-y j )(z-z k ) (x-x i )ξ i,j,k +(z-z k ) log [y-y j +ξ ijk ] Φ 2 =z k + (y -y j ) arctan z -z k y -y j + (x -x i ) log [z -z k + ξ ijk ] -(y-y j ) arctan (x-x i )(z-z k ) (y-y j )ξ ijk +(z-z k ) log [x-x i +ξ ijk ] Φ 3 =y j + (z -z k ) arctan y -y j z -z k + (x -x i ) log [y -y j + ξ ijk ] -(z-z k ) arctan (x-x i )(y-y j ) (z-z k )ξ ijk +(y-y j ) log [x-x i +ξ ijk ] (6)
As stated previously, the magnetic scalar potential Φ(x, y, z) is fully analytical and does not require any numerical treatment for its determination. Its expression is suitable for representing its isopotentials inside the magnet as well as outside it.

Representation of the Magnetic Scalar Potential

We illustrate our previous analytical expression with two configurations. The first one allows us to verify the accuracy of our expression and allows us to compare it with the ones published in the literature.

The second configuration is less usual as the first one: It is an academic illustration of the usefulness of our 3D analytical expression.

Case of a Parallelepipedic Magnet Whose Polarization Is Directed along the z Direction

The first configuration is well known and corresponds to the case when the polarization is directed along the z-direction. We take the following dimensions: x 2 -x 1 = 0.005 m, y 2 -y 1 = 0.01 m, z 2 -z 1 = 0.02 m, J = 1 T. We represent in Fig. 2 three 2D cross-sections of the isopotentials created by the parallelepipedic magnet whose polarization is directed along the z direction. Figures 2 show that the iso-potentials are circles in the (xy) plane, which is consistent with the polarization direction of the parallelepipedic permanent magnet. Moreover, we see the isopotentials in the (x-y) and (y-z) planes are the same: It is still consistent with the polarization direction of the parallelepipedic permanent magnet.

Case of a Parallelepipedic Magnet of Various Polarization Direction

The second configuration we consider is a parallelepipedic permanent magnet with the polarization shown in Fig. 3: This polarization is expressed as follows:

J = J √ 2 u y + J √ 2 u z (7)
We take the following dimensions: x 2 -x 1 = 0.005 m, y 2 -y 1 = 0.01 m, z 2 -z 1 = 0.02 m, J = 1 T. We represent in Fig. 4 three 2D crosssections of the iso-potentials created by the parallelepiped magnet with the polarization J = J √ 2 u y + J √ 2 u z . In this configuration, we take θ = π 2 rad and φ = π 4 rad. The computational cost is 1 s for representing the magnetic potential in the three previous illustrations.

ANALYTICAL EXPRESSION OF THE MAGNETIC FIELD PRODUCED BY A PARALLELEPIPED MAGNET WITH A UNIFORM AND ARBITRARY POLARIZATION

The three components of the magnetic field created by one parallelepipedic magnet of various polarization direction can be determined by using the following expression:

H x (x, y, z) = -∇ (φ(x, y, z)) • u x H y (x, y, z) = -∇ (φ(x, y, z)) • u y H z (x, y, z) = -∇ (φ(x, y, z)) • u z (8)
After mathematical manipulations, we obtain the three components H x (x, y, z), H y (x, y, z) and H z (x, y, z) that are expressed as fol-lows:

H x (x, y, z) = J sin(φ) cos(θ) 4πµ 0 ϑ (ijk) arctan (y -y j )(z -z k ) (x -x i )ξ ijk + J sin(φ) sin(θ) 4πµ 0 ϑ (ijk) {-log [z -z k + ξ ijk ]} + J cos(φ) 4πµ 0 ϑ (ijk) {-log [y -y j + ξ ijk ]} H y (x, y, z) = J sin(φ) cos(θ) 4πµ 0 ϑ (ijk) {-log [z -z k + ξ ijk ]} + J sin(φ) sin(θ) 4πµ 0 ϑ (ijk) arctan (x -x i )(z -z k ) (y -y j )ξ ijk + J cos(φ) 4πµ 0 ϑ (ijk) {-log [x -x i + ξ ijk ]} H z (x, y, z) = J sin(φ) cos(θ) 4πµ 0 ϑ (ijk) {-log [y -y j + ξ ijk ]} + J sin(φ) sin(θ) 4πµ 0 ϑ (ijk) {-log [x -x i + ξ ijk ]} + J cos(φ) 4πµ 0 ϑ (ijk) arctan (x -x i )(y -y j ) (z -z k )ξ ijk (9)
If we take θ = 0 and φ = 0, we obtain the same expression as Bancel [START_REF] Ravaud | Discussion about the analytical calculation of the magnetic field created by permanent magnets[END_REF].

Representation of the Magnetic Field

We illustrate now the use of our three-dimensional analytical expression by calculating the magnetic field modulus H. Then, we represent the iso-lines in two configurations corresponding to the previous ones.

Case of a Parallelepipedic Magnet Whose Polarization Is Directed along the z Direction

We take the following dimensions: x 2 -x 1 = 0.005 m, y 2 -y 1 = 0.01 m, z 2 -z 1 = 0.02 m, J = 1 T. We represent in Fig. 5 three 2D crosssections of the iso-lines created by the parallelepiped magnet whose polarization is directed along the axial direction. In this configuration, we take θ = 0 rad and 0 rad.

The computational cost for representing the iso-lines is lower than 1 s: This shows the interest of using a fully analytical approach for calculating the magnetic field produced by a parallelepipedic magnet of various and uniform polarization.

Case of a Parallelepipedic Magnet of Various Polarization Direction

We take the following dimensions: x 2 -x 1 = 0.005 m, y 2 -y 1 = 0.01 m, z 2 -z 1 = 0.02 m, J = 1 T. We represent in Fig. 6 three 2D crosssections of the iso-lines created by the parallelepiped magnet with the polarization J = J √ 2 u y + J √ 2 u z . In this configuration, we take θ = π 2 rad and φ = π 4 rad.

CONCLUSION

This paper has presented three-dimensional analytical expressions for calculating the magnetic scalar potential and the magnetic field produced by a parallelepiped magnet of various polarization direction. In particular, the polarizations considered are entirely uniform, as it is generally the case in practice. By using the coulombian model of a magnet, we have expressed the the three components of the magnetic field in terms of fully analytical parts whose computational cost is very low. Such expressions have been compared to the ones published in the literature when the magnet polarization is directed along the axial direction. From an academic point of view, these expressions are an extension to the case of parallelepiped permanent magnet whose polarizations are directed along the x, y or z directions.

Figure 2 .

 2 Figure 2. 2D representation of the iso-potentials created by a parallelepiped magnet whose polarization is directed along the z direction; (x-y)-plane: z = 15 mm, (x-z)-plane: y = 5 mm, (y-z)-plane: x = 5 mm.

Figure 3 .

 3 Figure 3. Representation of a parallelepiped magnet with the following polarization vector: J = J √ 2 u y + J √ 2 u z .

Figure 4 .

 4 Figure 4. 2D representation of the iso-potentials created by a parallelepiped magnet whose polarization is J = J √ 2 u y + J √ 2 u z ; (xy)-plane: z = 19 mm, (x-z)-plane: y = 10 mm, (y-z)-plane: x = 5 mm.

Figure 5 .Figure 6 .

 56 Figure 5. 2D representation of the iso-lines created by a parallelepiped magnet whose polarization is directed along the z direction; (x-y)plane: z = 19.9 mm, (x-z)-plane: y = 5 mm, (y-z)-plane: x = 4.5 mm.


Bart Lamiroy
email: bart.lamiroy@loria.fr

Jean-Philippe Ropers

Inductive Logic Programming for Symbol Recognition

In this paper, we make an attempt to use Inductive Logic Programming (ILP) to automatically learn non trivial descriptions of symbols, based on a formal description. This work is a first step in this direction and is rather a proof of concept, rather than a fully operational and robust framework.

The overall goal of our approach is to express graphic symbols by a number of primitives that may be of any complexity (i.e. not necessarily just lines or points) and connecting relationships that can be deduced from straightforward state-of-the art image treatment and analysis tools. This representation is then used as an input to an ILP solver, in order to deduce non obvious characteristics that may lead to a more semantic related recognition process.

Introduction

The main and primary goal of image analysis is to eventually find the means of bridging the semantic gap between low level descriptions of an image and the concepts of what is presented within it. The global state of the art assumption is that this may be obtained through an adequately conceived interaction between shape descriptions and the comparison or distance measurements between them on the one hand, and classification or grouping techniques to associate these descriptions to higher level concepts on the other hand.

Trying to express visual information using "natural" descriptions has actually been the original underpinning drive behind structural pattern analysis. Most often, this is done by first extracting low level visual cues that form the basic lexical data, and by proceeding by some grouping algorithm in order to express relationships or properties that are then translated into more and more complex "vocabulary" that triggers higher level rules, eventually expressing terminal concepts [START_REF] Mas Romeu | An Incremental On-line Parsing Algorithm for Recognizing Sketching Diagrams[END_REF].

Our approach is slightly different in the way that we don't try to construct a chain of syntactic rule triggering, but rather build our vocabulary on direct extraction of (more or less) complex structures in the images. This vocabulary is based on currently unpublished work [START_REF] Fresh | Final report on symbol recognition with evaluation of performances[END_REF] that characterises symbols by a set of very robust, local structures. These structures need not necessarily be extracted by a structural or syntactic methods. In our case, for instance, we have developed specific and specialised detectors for circles [START_REF] Lamiroy | Robust Circle Detection[END_REF], oriented corners, loose endpoints, rectangles, etc. Once a symbol is expressed as a set of elementary items, we use a reduced version of the force histogram based approach [START_REF] Matsakis | The Use of Force Histograms for Affine-Invariant Relative Position Description[END_REF] to position all items relatively one to another by using a quantitative assessment of directional spatial relationships (such as "to the right of", "above", "south of". . . ) between two items in a way that corresponds quite closely to natural language and perceptional coherent relative positioning.

This allows us to express symbol descriptions with firstorder logic predicates, expressing their type as per the vocabulary previously described and expressing the relative positioning one to another. Examples of the exact representation is given in section 4 and subsequent ones, where the experiments are described.

This framework gives us a straightforward way of describing the image that combines both expressiveness and very high flexibility. On the one hand, one can reduce or extend the size of the vocabulary in function of what robust descriptors are available. They may even be obtained using statistical or signal based extractions [START_REF] Nguyen | Symbol descriptor based on shape context and vector model of information retrieval[END_REF]. Furthermore the relations that express the relative positioning need not only by as simple as those represented, and can even include more quantitative information (e.g. [START_REF] Bloch | Fuzzy Spatial Relationships for Image Processing and Interpretation: a Review[END_REF][START_REF] Bennett | Semantic categories underlying the meaning of 'place[END_REF][START_REF] Wendling | Dynamic angle based theory in learning relative directional spatial relationship on components of raster symbols[END_REF]).

The remaining problem is how to explore what this new representation can offer in terms of recognition, classification of learning of concepts. We are going to do this in the next sections, by feeding these data to a Inductive Logic Programming process. We first give a very brief introduction to Inductive Logic Programming and how it can contribute to learning visual classes for symbol recognition in section 2. We then show how this behaves on real data in section 4.

Inductive Logic Programming

Inductive Logic Programming (ILP) [START_REF] Muggleton | Inductive logic programming: Theory and methods[END_REF] combines automatic learning and first order logic programming. It requires three main sets of information, the automatic solving and deduction theory set aside:

1. a set of known vocabulary, rules, axioms or predicates, describing the domain knowledge base K;

2. a set of positive examples E + the system is supposed to describe or characterise with the set of predicates of K ;

3. a set of negative examples E -that should be excluded from the deducted description or characterisation.

Given these data, the ILP solver is then able to find the set of properties P, expressed with the predicates and terminal vocabulary of K such that the largest possible subset of E + verifies P, and such that the largest possible subset of E - does not verify P. This approach has already been successfully used for extraction of semantics from written text [START_REF] Claveau | From Efficiency to Portability: Acquisition of Semantic Relations by Semi-Supervised Machine Learning[END_REF] or in document and image analysis structures [START_REF] Amin | Learning to recognize hand-printed Chinese characters using Inductive Logic Programming[END_REF][START_REF] Ceci | Relational data mining and ilp for document image processing[END_REF]. This approach allows for learning common properties within classes of symbols such as to express non-trivial knowledge of visual representation of more semantic concepts. We illustrate this in the next section. This work currently only concentrates on the Image Analysis part of the problem, and uses ILP as a black-box framework. The Inductive Learning Programming solver used in our experiments -Aleph -is freely available from the Oxford University Computing Lab1 .

In the following sections we will be using datasets of electrical graphical symbols, expressed using our first order logic vocabulary, and coming from an electric wiring component database [8]2 .

Data Representation

In order to show what kind of data we actually manipulate, we have selected symbols 225_2 and 226_2 from Figure 1 as positive examples. All others as considered as counter-examples. Expressed in our visual vocabulary, symbol 225_2, for instance, is described as: type(prim_172,cornerse). type(prim_173,extremity). has_element(img_225_2,prim_170). has_element(img_225_2,prim_171). has_element(img_225_2,prim_172). has_element(img_225_2,prim_173). nw(prim_170,prim_171). n(prim_170,prim_172). nw(prim_170,prim_173). se(prim_171,prim_170). ne(prim_171,prim_172). n(prim_171,prim_173). s(prim_172,prim_170). sw(prim_172,prim_171). w(prim_172,prim_173). se(prim_173,prim_170). s(prim_173,prim_171). e(prim_173,prim_172). The output of the ILP solver consists of à[theory] section, containing the rules that define the positive example set. For each rule of the theory, the solver gives matching statistics, indicating the precision of the rules (how many positive examples covered, and how many negative examples). For a perfect match, the theory section should consist of one single rule covering all positive examples and no negative examples. Further experiments will show that this is not always attainable. Sometimes the theory is composed of multiple rules, each of which covering a subset of the positive examples. Sometimes negative examples are covered by the theory as well. In our example, this gives: This experiment, translated into natural language, means that the chosen examples all have circles containing a northwest corner element ( ). With this rule, all positive examples are perfectly classified with respect to the negative ones. However, when selecting another set of symbols, like {180_1, 180_3, 184_1, 185_1, 185_3, 186_2}, the system is not able to reduce the set to a single predicate: and corner , but, more interestingly, that it contains a third, unspecified -any -, primitive at a north-east position of the corner. The fact that it is possible to express these very generic relationships (regardless of the underlying shape !) is something numeric learning or classification techniques [START_REF] Malon | Mathematical symbol recognition with support vector machines[END_REF][START_REF] Kuncheva | Diversity in multiple classifier systems[END_REF] cannot achieve. The developed rule covers all the examples in a single predicate and only a primitive is needed to describe the set. It is thus very important to try and characterise both positive and negative example sets.

Choosing a Side

179_003_2 179_004_2 179_005_2 179_006_2 179_007_2 179_008_2 179_009_2 179_010_2 179_011_2 193_2 194_2 195_2 196_2 197_2 198_2 199_2 200_2 201_2
Another point of interest with this experiment is that the generated rule might seem "visually" weird with respect to human interpretation. Indeed, one would naturally describe the example set as "circles containing stuff". Although this rule is perfectly acceptable in our framework, giving something like:

symbol(A):-has_element(A,B), type(B,circle), has_element(A,C), inside(B,C).
it is, unfortunately, more complex than the rule the automatic solver found. This is due to the fact that the ILP solver works in a "closed world" of predicates, vocabulary and examples and cannot infer that a given solution might be "more generic" than another with respect to human interpretation standards.

Learning Set Induced Limits

In the prevous sections we addressed the question on how the predefined vocabulary affects the learning process. In this section we address the influence of the learning samples. Let us consider the case of a specific semantic concept: a diode. The positive and negative learning examples are taken from Figure 3.

First, let the set of positive samples be {180_1, 180_3, 184_1, 185_1, 185_3,186_2}. The negative ones are {194_2, 198_2, 210_2}. The produced theory is:

symbol(A):- has_element(A,B), type(B,blackthick).
This theory thus implies that every symbol which contains a black thick object is a diode. This rule, of course, is too "simple", due to the fact that the learning set was too limited (it is, however, quite correct in the context of the closed learning set world). Let's add a negative example which contains black thick objects: the negative sample set becoming {194_2, 198_2, 210_2, 195_2}. At this stage, the spatial relations become the important criterion. The interpretation of the rule is "having a SouthEastcorner which is on the right of another object which contains the black thick object". This is not exactly the rule that we might be expecting, but we have to be aware that it is a rule based on only 6 negative examples and that the primitive detection is not perfect. By extending to the full set of 19 positive examples and the 6 negative examples previously used, the system obtains: What is interesting to note here, is that, compared to statistical learning models, the system adapts the complexity of the classification with respect to the learning data, without need for any parametrization of any sorts. On the other side, however, it is also quite straightforward to see that, if the learning set is contradictory with respect to the available vocabulary, it cannot deduce any classification rule.

180_1 180_3 184_1 184_3 185_1 185_3 186_2 187_3 188_2 189_2 190_2 191_2 192_2 194_2 195_2 196_2 198_2 202_2 203_2 207_2 208_2 210_2

Conclusion and Further Work

This paper presents the first step towards another approach of symbol recognition and representation, by combining robust elementary form detectors that compose a predefined, but extensible vocabulary. This vocabulary is combined with relative positioning in order to obtain a first order logic based description of the symbols, on which ILP can be used to extract "semantic" contexts or concepts. The interesting part of this is that the description of the symbols can now be easily mixed with other, more context related information. The main advantage of this approach is, that information need not necessarily be visually represented (for example, from surrounding text), and it thus opens a new scope of possible combined text/image concept characterisation and learning. It is even possible to expand the framework to generate symbols from the obtained descriptions (either for visual validation of classification results or for automatic illustration generation), as shown in [START_REF] Lamiroy | Assessing classification quality by image synthesis[END_REF].

However, the method, as it currently stands, is limited by the expressive power of the used vocabulary. Further work is therefore consisting of extending the initial vocabulary, by introducing the notion of connexity, refining the inclusion predicate and using relative distance and size (close, far, large, small ...). These are all straightforward extensions that are readily available from an image analysis standpoint. Further, less straightforward, work will concern inclusion of more numerical or statistical form descriptions that might be able to better quantify differences between the shapes and will need to rely on Markov Logic [START_REF] Richardson | Markov logic networks[END_REF][START_REF] Domingos | Markov logic[END_REF] to handle the numerical part. More prospective work will be to connect this to Formal Concept Analysis [START_REF]Formal Concept Analysis: Foundations and Applications[END_REF] and Galois Lattices to achieve unsupervised learning of visual concepts.

%

  225_2 ***************************** type(prim_170,cornerne). type(prim_171,cornernw).

  %fin 225_2 *****************************

  [theory] [Rule 1] [Pos cover = 2 Neg cover = 0] symbol(A):-has_element(A,B), type(B,cornerne), has_element(A,C), n(B,C), type(C,cornerse). [positive examples covered] symbol(img_225_2). symbol(img_226_2). [negative examples covered] test [covered] symbol(img_225_2):-has_element(img_225_2,prim_170), type(prim_170,cornerne), has_element(img_225_2,prim_172), n(prim_170,prim_172),type(prim_172,cornerse).

FollowingFigure 1 .

 1 Figure 1. First image set for ILP experimentation.

[

  Rule 1] [Pos cover = 1 Neg cover = 0] symbol(img_180_1).

[

  Rule 2] [Pos cover = 2 Neg cover = 0] symbol(A):-has_element(A,B), type(B,circle), has_element(A,C), e(B,C), type(C,cornernw). [Rule 3] [Pos cover = 3 Neg cover = 0] symbol(A):-has_element(A,B), type(B,blackthick), has_element(A,C), type(C,cornersw), has_element(A,D), ne(C,D). Image 180_1 is not covered by the predicates, and the remaining, positive examples, are split up into two distinct sub-classes, each of them covered by a separate rule. The first one, describing the symbols as containing a circle and a corner , placed to the east of it. The second one is far more interesting, and gives an outstanding reason of using ILP solving. [Rule 3] indeed mentions that the corresponding symbols contain a black thick component

Figure 2 .

 2 Figure 2. Second image set for ILP experimentation.

Figure 3 .

 3 Figure 3. Third image set for ILP experimentation.

  symbol(A):-has_element(A,B), type(B,blackthick), has_element(A,C), type(C,cornernw), has_element(A,D), e(C,D), type(D,cornerse).

978-0-7695-3725-2/09 $25.00 © 2009 IEEE DOI 10.1109/ICDAR.2009.166

http://web2.comlab.ox.ac.uk/oucl/research/areas/ machlearn/Aleph/aleph.html.

The full experimental data file can be obtained on demand by contacting the authors.

Acknowledgements

This work contains experiments and is partially based on software developed by F. Meghenem and L. Hao, during their Master Thesis at the École des Mines de Nancy. Part of the unpublished work related in [8] was conducted jointly with J.P. Salmon and L. Fritz under funding by the EC FP6 Strep Project "Fresh" FP6-516059.


Shahram Nourizadeh
email: shahram.nourizadeh@loria.fr

Y Q Song
email: song@loria.fr

J P Thomesse
email: thomesse@loria.fr

An Adaptive Hierarchical Routing Protocol for Wireless Ad-hoc Sensor Networks

Keywords: Adaptive routing, Dynamic Clustering, Mobility management, Failure management, Load balancing, Fuzzy Logic I

This paper presents a cluster based, adaptive routing protocol that dynamically adapts to node's failure and mobility. Cluster head election, Mobility management, Failure management and Load balancing are the main parts of the protocol which are controlled by a Fuzzy decision making function. A new load balancing method by using Load tree is presented in this approach. The simulations results show the efficiency of this algorithm to manage the mobility and failure of the nodes and also to balance the load in the network.

INTRODUCTION

Nowadays, ad-hoc wireless sensor networks have many applications in the entire world and have recently emerged as a premier research topic. Intelligent homes, smart rooms, interactive virtual worlds are only a few examples. A famous example of these networks is healthcare network. These systems present important research and technical challenges. In a healthcare network, because of mobility of the patients, all the sensors attached to them, are mobile, therefore the mobility management and localization are important points in these networks.

Figure 1, shows a typical architecture of a healthcare system. In this example, the Communication backbone consists of the mobile or fixed sensors and also the sensors attached to the other persons, like doctors and nurses. This system needs an adaptive routing and localization protocol that can support mobility of the sensors and changes of network topology when patients moving.

Dynamic cluster-based routing is one of existing techniques for routing in ad hoc networks. As the membership in each cluster changes over time in response to node mobility and so it can be used to mobility management in mobile networks, and also cluster based routing in ad hoc networks can also make a large network appear smaller, but most importantly it can make a highly dynamic topology appear much less dynamic.

Several dynamic clustering strategies have been proposed in the literature. In [START_REF] Haas | The zone routing protocol (ZRP) for ad hoc networks[END_REF], the zone routing protocol (ZRP) a hybrid strategy, is proposed by Haas and Pearlman which attempts to balance the trade-off between proactive and reactive routing. The objective of ZRP is to maintain proactive routing within a zone and to use a query-response mechanism to achieve inter-zone routing. In ZRP, each node maintains its own hop-count constrained routing zone; consequently, zones do not reflect a quantitative measure of stability, and the zone topology overlaps arbitrarily.

LEACH [START_REF] Heinzelman | An Application-Specific Protocol Architecture for Wireless Microsensor Networks[END_REF] is an application-specific data dissemination protocol that uses clustering to prolong the network lifetime. LEACH clustering terminates in a constant number of iterations (like HEED [START_REF] Younis | HEED: A Hybrid, Energy-Efficient, Distributed Clustering Approach for Ad Hoc Sensor Networks[END_REF]), but it does not guarantee good cluster head distribution and assumes uniform energy consumption for cluster heads. In contrast, HEED makes no assumptions on energy consumption and selects well distributed cluster heads but HEED assumes quasi-stationary nodes.

In [START_REF] Gupta | Cluster-head Election using Fuzzy Logic for Wireless Sensor Networks[END_REF], a fuzzy logic approach to cluster-head election is proposed based on three descriptors -energy, concentration and centrality. In this approach the cluster-heads are elected by the base station in each round by calculating the chance each node has to become the cluster-head by considering three fuzzy descriptorsnode concentration, energy level in each node and its centrality with respect to the entire cluster. This technique is proposed to use in LEACH [START_REF] Heinzelman | An Application-Specific Protocol Architecture for Wireless Microsensor Networks[END_REF], but it cannot support the mobility of the node and in addition it is centralized algorithm and therefore it cannot be scalable. Another problem in these networks is failure of the nodes. Generally, the communication in sensor networks, with battery powered nodes, suffers from failure, low transmission power even more so than in regular wireless networks. Despite of many research projects, failure management in sensor networks is an open research challenge. Nodes' mobility, communication problem and link failure may be detected as a failure, on the other hand, in some networks, like healthcare networks, failure of a sensor can be detected as a health anomaly. These 2 cases can cause false alarms. Any failure in a healthcare system can lead patient situation to a critical level. This failure may be occurs in a sensor, computer, router or in the communication link.

Servers' platform

Fault tolerance in measurements by a group of sensors, was first studied by Marzullo [START_REF] Marzullo | Tolerating failures of continuousvalued sensors[END_REF]. Marzullo proposed a flexible control process program that tolerates individual sensor failures. Issues addressed include modifying specifications in order to accommodate uncertainty in sensor values and averaging sensor values in a fault-tolerant way. The authors in [START_REF] Jayasimha | Fault tolerance in multi-sensor networks[END_REF] developed an algorithm that guarantees reliable and fairly accurate output from a number of different types of sensors when at most k out of n sensors are faulty. The results of the scheme are applicable only to certain individual sensor faults and traditional networks. They are not extendable to the reliability needs in complex network levels and most importantly; they do not address the reliability issues that are induced by the ad-hoc nature of the wireless sensor networks. Multi-sensor data fusion is a problem that recently has attracted a great deal of attention in a number of scientific and engineering communities [START_REF] Brooks | Multi-Sensor Fusion: Fundamentals and Applications With Software[END_REF][9] [START_REF] Hager | Task-Directed Sensor Fusion and Planning -A Computational Approach[END_REF]. Majority of these works are restricted to sensor fusion of the same modality.

One of limits of wireless sensor nodes is their inherent limited energy resource. To maximize the lifetime of the sensor node, it is necessary to distribute the load throughout the wireless sensor network in order to minimize maintenance and message number and maximize system performance. The load balancing averages the energy consumption and this extends the lifetime of the whole sensor network by extending the time until the first node is out of energy. Load balancing is also useful for reducing maintenance time and also message exchange traffic.

In the mobile sensor networks, managing the distribution of the network and also the load balancing is a complex problem, because of large number of the sensors and particularly because of the mobility of the modes. We can reduce this complexity by separating the network in different small parts. Clustering may be one of existing techniques to reduce this complexity, but none of the published clustering protocols consider any load balancing method in their clustering process.

To balance the load in the network, most of the clustering protocols use different parameters to choose cluster-heads. Cluster ID [START_REF] Baker | A Distributed algorithm for Organizing Mobile Radio Telecommunication Networks[END_REF], connectivity degree [START_REF] Gerla | Multicluster, mobile, multimedia radio network[END_REF][START_REF] Parekh | Selecting Routers in Ad-Hoc Wireless Networks[END_REF] and periodical cluster heads election [START_REF] Heinzelman | An Application-Specific Protocol Architecture for Wireless Microsensor Networks[END_REF] are used in order to share the load among all the nodes of the network. By applying cluster ID or highest connectivity methods, the same node may be chose as cluster-head every time, and that will result resulting in this sensor to drain its energy very fast. Changing the cluster head in the cluster, connectivity degree or periodical choosing, changes the topology of clusters frequently and this will impose huge overhead since all other cluster-heads have to be notified about the change.

The remainder of this paper is structured as follows: section II discusses some challenges in detail. Our proposal, its load balancing, failure management, clustering and decision making methods are described in section III, while section IV describes its functionality with some examples. Our simulations are resented in section V and section VI provides concluding remarks.

II. CHALLENGES

As we described, in an ad-hoc wireless network with mobile nodes and therefore dynamic topology, mobility, failure and load balancing are important challenges.

One of the suitable solutions to manage the mobility of the nodes is dynamic clustering, but the existing clustering protocols use many assumptions which make them not able to address the needs of real application. Some algorithms are based on centralized control that makes them not to be scalable. Some algorithms use periodic rounds to change cluster head and elect a new one. The new cluster head will be fixed for one round, but in an ad-hoc network with dynamic topology, cluster topology may change during this period, and in this case a new cluster head must be elected. Therefore this type of algorithms will be good for networks with fixed or very low mobility nodes.

In addition, network dynamics resulted by node mobility and node state transitions due to the use of power management or energy efficient schemes may be detected as node failures or wireless link failures. Such a highly dynamic network greatly increases the complexity of failure management. Also, with bandwidth limitation in a sensor network the failure detector must generate a minimum number of control messages. However, the traditional failure detectors and management systems assume that all of the nodes of the network are synonymous, that means there is no difference between a node that was crashed n times in t hours, with a node that was crashed m times (m>n) in the same period of time. That will cause an unclear decision making and electing between different nodes. In the traditional failure detectors, when a node fails, it will be assumed as a dead node and we don't have a return of the node. That will be a restriction, for example, when a node is in maintenance.

Finally, as we said, none of the published clustering protocols consider any load balancing method in their clustering process. This can cause some clusters with high node density and other clusters with low node density. It is clear that in a cluster with a high node density, energy consumption will be very high and the cluster head will dead rapidly, this can cause network partitioning.

In order to solve these problems we proposed a new cluster based routing which can manage the mobility and failure of the nodes. To make it scalable the protocol is totally distributed, it has also a load balancing part. All event-processing and decision-making processes of this proposal use fuzzy logic. In the next sections we explain how our solution addresses these challenges.

III. OUR PROPOSAL

As a result of our discussions in the last sections, Mobility and Failure management and Load balancing are main important problems to be addressed in ad-hoc sensor networks. To address these problems, our approach has 5 main parts: Fuzzy logic decision making, Clustering (Cluster-head election), Mobility management, Load balancing and Failure management. Figure 2 shows the main parts of the protocol. As we see in this figure, fuzzy decision making is the basic part of our proposal. That means, the 4 other parts of the protocol, use fuzzy logic to make decision or to process an event.

A. Some descriptions:

Before explain our proposal, in this section we present some definition that we use in our protocol:

 {ALL}: Set of all sensors of the network. 3):

∀ n ∈ {ALL}, ∄ m ∈ {ALL} -n | m→ n ⇒ n is a LN
∀ n∈ {ALL}, ∃ m∈ {ALL} -n | n → m
and also:

∀ n,m ∈ {ALL} : ( n → m) ⇒ m ∈ {ZH } ∪ {CH }
 Invite: it is a message, between the nodes to exchange the information. This message is used by a ZH or CH to invite the other nodes to join them. (See III.F)  Hello: is used by a node to announce a change or event to its neighbors.  Find: it will be used by nodes to find a new parent.  Join: this message is used by a node to answer an Invite message. If the node has just one possible candidate to choose as its parent, it will indicate that, in this message.  Quit: a node sends this message to its parent node to advertize leaving it.  Join_Other: It is a message that a ZH or a CH sends to one of its child to ask him to find another parent. This will be when the ZH or CH: o received a new request of join from a node with no other possible parent, and the admission condition is not satisfied. Therefore it must reduce its load by reducing number of its child. o is in a low level energy state,

B. Fuzzy decision making

In our proposal, we use fuzzy logic because it is capable of making real time decisions, even with incomplete information. Conventional control systems rely on an accurate representation of the environment, which generally does not exist in reality. Fuzzy logic systems, which can manipulate the linguistic rules in a natural way, are hence suitable in this respect. Moreover fuzzy logic can be used for context by blending different parametersrules combined together to produce the suitable result. In the next sections we will explain role of fuzzy decision making in different parts of our protocols.

Load balancing

Cluster head election Mobility management Failure management

Fuzzy decision making

In [START_REF] Gupta | Cluster-head Election using Fuzzy Logic for Wireless Sensor Networks[END_REF], a fuzzy logic approach to cluster-head election is proposed based on three descriptors -energy, concentration and centrality. They improved LEACH routing algorithm [START_REF] Heinzelman | An Application-Specific Protocol Architecture for Wireless Microsensor Networks[END_REF] by using Fuzzy Logic and the cluster-heads are elected by the base station in each round by calculating the chance each node has to become the cluster-head by considering three fuzzy descriptorsnode concentration (Number of neighbors), energy level in each node and its centrality with respect to the entire cluster. As we said, the proposed algorithm in [START_REF] Gupta | Cluster-head Election using Fuzzy Logic for Wireless Sensor Networks[END_REF] is centralized and therefore is not scalable and also cannot support the mobility of the nodes.

But, which descriptors we can choose in a mobile network? In a dynamic network with mobile nodes, can we use concentration and centrality as factors to decision making in a distributed approach? The answer is that in a distributed approach each node chooses its parent by processing its local information therefore centrality of a node cannot be suitable to its decision, this parameter will be good for a centralized algorithm to reduce the routing hops between CH and nodes in the same cluster, but a node cannot have a general view of network and thus cannot evaluate this parameter for a CH. In addition, in a dynamic network with mobile nodes the number of neighbors is not a good descriptor, because location of the node is not fixed and we cannot be sure about number of neighbors at each moment. In the next sections we explain the main parts of our proposal with more details.

C. Mobility management

In an ad-hoc sensor network with mobile nodes, we must be able to detect the movement of the nodes in order to have a correct image of network in each time. We know that the nodes, in these networks, are not integrated with systems like GPS, but without GPS how can we detect the movement of a node? Assume that distance between two nodes A and B in time t is X, and in time t+1 the distance is Y where Y>X. By using this information we cannot say which one moved? A, B or both of them? Without a lot of calculations or a GPS system, we cannot answer this question. To solve this problem we proposed a new parameter named Mobility. This parameter shows frequency of parent, level or zone change of a node. (Number of CH or level change of a node in his life time). Therefore each time that the node changes its CH or his level, it must increment value of a variable named Change and divide it to his lifetime to find the Mobility. It is clear that the mobility of a fix node can be greater than zero, because of the mobility of his parent.

D. Load Balancing

Our load balancing strategy considers the cumulative load of data traffic from child nodes in a load tree on their parent nodes. We use Load tree and admission condition for load balancing.

1) Load tree

Figure 4 shows a sample load tree. The load tree is rooted in the base station. The load of child sensor nodes adds to the load of each upstream parent in the tree. Hence, the sensor nodes nearest the base station will be the most heavily loaded. The goal of this load balancing technique is to evenly distribute packet traffic generated by sensor nodes across the different branches of the Load tree. But here Load has a special definition. Load is the sum of the QoL (see next section) between a node and his children. It is a new definition that can be used as a new parameter in QoS. In a load tree, the weight of each link, in load tree is QoL between each node and his parent, and load of each node is the sum of the QoLs between the node and his child.

2) admission condition

In order to balance the load between nodes of the network, we use admission condition, which is the condition of accepting a new child node in node n:

(n.Load + NewChild.QoL)/ n.numberLowLevelNodes + 1 ≤ n.QoL
In this formula the number of low level nodes means the number of all the nodes that are connected to this node directly or indirectly.

E. Failure management

In this approach we have a parameter named failure shows the failure history of a sensor. This parameter will be computed by using the number of sensor's failures during its lifetime. Like the other used parameters, it is also a Fuzzy variable that has 3 levels: High, Medium and Low. That is not a static parameter, that means, for each node it can change from Low to High and also High to Low. To manage the failure of nodes or links, each time that the node detects a failure in a neighbor, it updates failure parameter for this node:

failure = fuzzy (n / L);
where fuzzy is a function to convert decimal value to fuzzy value, n is number of neighbor's failures and L is our life time, therefore the failure parameter has different value for each node in the other nodes. In each network, due to the mobility or failure frequency of the nodes, BS will defines a update period, in which each node will update the failure table, therefore failure and Reliability parameters are really dynamic parameters that can change not only from Low to High but also from High to Low.

F. Cluster head election

We use four parameters: Energy level of the node (Battery charge), Mobility, Quality of Link -QoL (Reliability between a node and his parent) and the failure, to evaluate a node that is candidate to be a ZH or CH. These parameters will be the Fuzzy Logic Descriptors and each of them has three possible values: low, medium, high.

Therefore we have 81 rules to evaluate a node. The result of the rules will be Reliability with five possible levels: Very Low, Low, Medium, High and Very High (See figure 5). In each Invite message the node will send necessary information to be evaluated by the other nodes, as like as: Energy level and QoL, and the node will compute the QoL of the connection between candidate and itself. The QoL of a node is Reliability parameter that he was calculated for his parent. This parameter helps us to choose the best parent node, a node with maximum energy, maximum stability, and higher reliability of connection. By finding the Reliability of a candidate we must evaluate the chance of the candidate to be a parent. To restrict depth of network's tree when a node receives more than one Advertisement, it will choose the node with smaller level, therefore we use:

Chance = Reliability / Level G.

Different processes in the nodes

This section presents the process in the nodes to answer different messages on them. In Table I, we find action of a ZH or a CH to answer Join message from a node. First, the ZH (or CH) will check if n is in the {Unknown} or not, if n is in this set, it will remove n from the set, also if n is not his neighbour, n will be added into {myNeighbours}. Then the ZH will verify admission condition: If OK, it will accept n as a new member; If KO, and n hasn't any other choice, ZH sends a OK message to n and chooses one of his actual members with smallest QoL than n and will send a request the join another one and will wait to a response, if the answer is KO it will choose another child node to send Join_Other.

Table II shows that when a node revives Invite from a CH or a ZH, c, it will add the node in its {myNeighbours} set and then if it has not a parent, it will send a Join message to c. If the node has already a parent, it will run the Fuzzy decision making function to know if c is better than its current parent or not: If c is better it will choose it by sending a Join message to it and by receiving OK from c, it sends also a Quit message to its current parent. Table III shows that in a node, by receiving Join-Other message, the Node will send Join message to its neighbours and if it receives OK, from one of them, it will send OK to its parent node, if no, it will send KO.

Receive (Join from n) accepted = False;

IV. SOME EXAMPLES

In this section we will present our protocol with some examples. Let's start with a simple example. Let's take a parent selection scenario in the network presented in figure 3. Figure 5 shows the different state of the scenario. In this network node n searches a parent's node. Here are the different steps of the procedure: a. n diffuses Find message. b. Its neighbors, y (a leaf node), C2 and C3 (Cluster heads) who have received the Find message send a

Invite message as answer. By the Invite message, they send their Energy, QoL. Node n then will search their Failure and Mobility in its neighbor table. If there is no value the default value for Failure and Mobility is Low.

c. By using four parameters, Energy, QoL, Failure and Mobility, n will run a Fuzzy function to evaluate the candidates. d. In this example y was the best node to be parent of n.

therefore, n send a Join message to y. e. By receiving Join message, y verifies Admission condition. f. Admission condition was ok, therefore y send a OK message to n. g. n joins y, and the state of y will be changed to a Zone head (Z3) h. As state of the y is changed (Z3), it diffuses a Hello message to announce this change.

6.a 6.b 6.c 6.d

6.e 6.f 6.g 6.h As second example figure 7 shows a scenario with a node that has one possible choice: a. n diffuses Find message. b. Its neighbor, Z1 (a zone head) receives the Find message send an invite message as answer. V. EVALUATION

In this section evaluated performance of our proposition will be presented and will be compared with ZRP routing protocol. We integrated OPNET simulators to implement the physical and MAC layers, with an application developed in C# to implement Fuzzy rules.

In our simulation we focus in load of the zone heads and average QoL in each zone and network's data delivery ratio as performance metrics. Table IV, shows our simulation parameters.

A. Some assumptions To evaluate our protocol, and to reduce simulation complexity, we have these assumptions:

 We used random waypoint model [START_REF] Lin | Mobility Models for Ad hoc Network Simulation[END_REF] in our simulations. The Network consists of several low mobility wireless nodes, just 20% of the nodes are mobile and their speed is 0.5 m/s.

 Each node is initially placed at a random position within in the simulation area.

 Round: the period of time in which all the mobile nodes change their zone.

 To focus on the assessment of the performance of the proposed algorithm, we do not generate any user data traffic during a simulation.

 All the nodes are able to detect correctly the failure of the other nodes.

 When a node failed or crashed, it is not dead, it will be return to the network after a variable time, t≠∞.

B. Simulation results

1) ZHs' load

Figure 8 shows load in ZHs of the simulated network. We find in this figure that after 10 rounds, network has 6 zones and load of 4 ZHs are medium, one between medium and high, and one between medium and low.

After 100 rounds network has 7 zones and 6 ZHs have a load between medium and low and load of one of them is medium. The average of load in ZHs after 10 rounds is medium and after 100 rounds is between medium and low. These results show that our protocol can balance correctly the load between ZHs and CHs.

2) Average QoL in the zones

As we explained before, QoL in a zone shows the connectivity of the nodes. A QoL with value of high shows a good connectivity between the nodes and a low QoL shows unstable connection between the nodes. Figure 9 shows average QoL in the zones of the simulated network. We find in this figure that after 10 rounds, network has 6 zones and average QoL in the zones in between medium and high, and after 100 rounds network has 7 zones with average QoL near to high. These results show the efficiency of our protocol to establish reliable and stable connections between the nodes.

3) Data delivery ratio

In this step of simulation, we focus on the network delivery ratio. Network delivery ratio defines as the total received packets to the total sent packets in the sensor network. We compared this metrics in ZRP routing protocol and our protocol.

As we said 20% of the nodes of the network are mobile and for the simulation, in each step, we change the number of faulty nodes from 5 to 50 percent. We can find the simulation results in figure 10. The simulation shows that our protocol increases the data delivery in the network and greatly adapts mobility and failure of the nodes.

VI. CONCLUSION

A fuzzy logic based routing protocol is proposed in this paper. Stable route recovery, high data delivery ratio and good load balancing are the main characteristics that the proposed protocol adds to the ad-hoc sensor networks.

The performance of the protocol can be optimized through finding the best values for the used factors in neighbors table for different network topologies and sizes and it adapts also with mobility and failure of the nodes. This protocol is especially effective in networks that use sensor nodes to data aggregation and in which the data delivery ratio is important and the nodes are mobile, like health monitoring sensor networks. In such networks health events and information is sensed by several nodes and therefore, this protocol can help the network to deliver sensed events and avoid of data loss in the network.

In all of the data acquisition networks, like health monitoring systems, either the data is collected from the network periodically or on an occurrence of an event, in such systems, the data are highly vital to have a stable monitoring and have a minimum number of faulty alerts.

Hence, none of them adapts completely themselves to the failure of the nodes and the temporal variations in data delivered by the sensor network. This necessitates the use of a routing protocol that readily adapts to the failures of the nodes and changes in the data delivery rate. The simulation results show that the proposed protocol is well suited for such applications.

Figure 1 .

 1 Figure 1. An example of mobile network



  {Unknown}: the set of the nodes with unknown situation.  {myNeighbours}: Neighbours of a node.  {myChild}: Chile nodes of a parent node.  A→B: Direct communication between A and B  Base-Station (BS): Central computer that monitor the network or gather the information generated by sensors. (BS in figure 3)  Zone-Head (ZH): Node (mobile or stationary) that communicate directly with BS (Z1 and Z2 in figure3): ∀ n ∈ {ALL} | n→BS ⇒ n is a ZH  Zone: set of one or more cluster. Each ZH constructs a Zone.

Figure 2 .

 2 Figure 2. Building blocks of the protocol



  {Unknown}: the set of the nodes with unknown situation.  Level: Level of a node is the number of hops between the node and BS.  Mobility: This is a parameter to evaluate the movement of a node. You can find the complete description of this parameter in III.C.  Quality of Link (QoL): this parameter shows the Reliability of the connection between a node and his parent. (See III.F)  Successful clustering: In this algorithm, we have a successful clustering if and only if:

Figure 4 .

 4 Figure 4. A load tree

Figure 5 .

 5 Figure 5. Cluster head election

Figure 6 .

 6 Figure 6. Example 3

Figure 10 .

 10 Figure 10. Delivery ratio

  c. n received just one invite message, that means it has no other choice. It runs the fuzzy function to compute QoL. Therefore it sends a join message to Z1.

	Node Number	50	f. As n hasn't any other choice, Z1 send a OK message to n and a Join_Other message to C2, one its child.
	Surface	100m x 100m	g. n joins Z1, and C2 sends a Join message to Z2.
	Transmission range	15m	h. Z2 verifies Admission condition which is OK in this
	Data transmission rate	15 packet/sec	example.
	Failure model	Random	i. Z2 sends a OK message to C2.
	Packet size	128 bytes	j. C2 joins Z2 and sends a Quit message to Z1. By
	d. n sends a Join message to Z1. Initial Energy	5J	receiving Quit message, Z1 delete C2 from its Child set.
	e. By receiving Join message, Z1 verifies Admission condition. But it is not OK. Energy consumption (Calculation, receive and send) 10 nJ/bit	k. This figure shows final cluster of the network.
	7.a	7.b	7.c
	7.d	7.e	7.f
	7.g	7.h	7.i
		7.j	7.k
		Figure 7. Example 2