D V Christensen

K K Nielsen

R H Bahl

Agnès Smith

C R H Bahl

Demagnetizing effects in stacked rectangular prisms

Keywords: numbers: 75.30.Sg, 75.30.-m, 75.60.Ej, 41.20.Gz

  L'archive ouverte pluridisciplinaire

Introduction

The total magnetic field, H, in the vicinity of one or several magnetized bodies is of general interest. In particular, when concerned with, e.g., magnetic refrigeration the local magnetic field of the magnetic material is of great importance [START_REF] Peksoy | Demagnetizing effects in active magnetic regenerators[END_REF][START_REF] Bjørk | The influence of the magnetic field on the performance of an active magnetic regenerator (AMR)[END_REF]. The magnetostatic calculation of H is in principle straightforward and can in certain cases, e.g. ellipsoids, be found analytically [START_REF] Osborn | Demagnetizing factors of the general ellipsoid[END_REF][START_REF] Joseph | Demagnetizing field in nonellipsoidal bodies[END_REF][START_REF] Aharoni | Demagnetizing factors for rectangular ferromagnetic prisms[END_REF]. However, this is only true for homogeneously magnetized bodies. When the magnetization of the body is varying spatially, numerical methods are usually required [START_REF] Peksoy | Demagnetizing effects in active magnetic regenerators[END_REF][START_REF] Brug | Demagnetizing fields in magnetic measurements I. Thin discs[END_REF][START_REF] Beleggia | On the computation of the demagnetization tensor field for an arbitrary particle shape using a fourier space approach[END_REF][START_REF] Smith | The demagnetizing field of a non-uniform rectangular prism[END_REF].

In the presence of magnetized bodies the total magnetic field at a certain point in space, r, can be found as the superposition of the applied magnetic field, H appl , and the magnetic field created by the magnetized bodies. The magnetic field from a single, magnetic body is typically called the demagnetizing field inside the body and the stray or interaction field outside. Since the source of these fields is the same, the remainder of this paper will adopt the concept of the magnetic field of the body, H body (r), at any given point in space. The resulting total magnetic field may thus be written as

H(r) = H appl (r) + N i=1 H body,i (r), (1)
where the index i represents the ith body out of a total of N bodies. Usually, the solution to the magnetic field from a single, homogeneously magnetized body with magnetization M is written as

H body (r) = -N(r) • M, (2)
where the demagnetizing tensor field, N(r), only depends on the geometry of the body. Under inhomogeneous conditions iterative methods are typically required to determine the internal magnetic field of a magnetized body [START_REF] Joseph | Demagnetizing field in nonellipsoidal bodies[END_REF][START_REF] Brug | Demagnetizing fields in magnetic measurements I. Thin discs[END_REF]. Furthermore, even in a homogeneous applied magnetic field, the field of a magnetized body is generally inhomogeneous. In non-saturated conditions the magnetization thus becomes a nontrivial function of position thereby making evaluation of the magnetic field due to the magnetization of the body possible only using numerical methods.

Here, the numerical solution to the total magnetic field of a configuration of multiple bodies with inhomogeneous and field-dependent magnetization is reported. The numerical model is applied to a stack of rectangular prisms as this configuration is important in, e.g., magnetic refrigeration [START_REF] Bahl | A versatile magnetic refrigeration test device[END_REF]. However, the discretization underpinning the model can in principle be applied to any shape. The implementation is described in Sec. 2 and the results of different stack configurations are presented and discussed in Sec. 3. In Sec. 4 the implications of the model are considered. Finally, in Sec. 5, the conclusions are provided.

Magnetostatic model of stacked rectangular prisms

In the following a numerical model capable of calculating the total magnetic field in a configuration of N stacked rectangular prisms, as depicted in Fig. 1, is presented. The model is an extension of the single prism solution, which was presented in Ref. [START_REF] Smith | The demagnetizing field of a non-uniform rectangular prism[END_REF] and experimentally verified in Ref. [START_REF] Christensen | Spatially resolved measurement of the magnetocaloric effect and the local magnetic field using thermography[END_REF]. The single prism model uses iteration to solve the two coupled equations

M(r) =      f (T (r), H(r)) H(r) H(r) inside the prism 0 o u t s i d e t h e p r i s m (3)
and

H(r) = H appl (r) + H body (r). ( 4
)
Here f gives the magnitude of the local magnetization of the prism as a function of the (spatially dependent) temperature, T , and internal field strength, H; f is determined by the magnetic equation of state. Note that the magnetization is taken to be along the direction of the internal magnetic field thereby assuming the material to be isotropic. To solve Eqs. 3-4 iteratively, expressions for f and the magnetic field produced by the magnetic body, H body , need to be established. The magnetic equation of state is chosen to be the mean field equation of state [START_REF] Morrish | The Physical Priciples of Magnetism[END_REF] with parameters appropriate for the rare earth metal gadolinium (see Ref. [START_REF] Smith | The demagnetizing field of a non-uniform rectangular prism[END_REF]) frequently used in magnetic refrigeration. The temperature is chosen to be 293 K, which is also the Curie temperature of gadolinium. The model may straightforwardly be extended to handle temperature and material variations across the prisms, however, for simplicity this is not done in the present study; see Ref. [START_REF] Smith | The demagnetizing field of a non-uniform rectangular prism[END_REF] for further details.

The magnetic field of a single magnetized rectangular prism is found by dividing the prism into k cells each shaped as a rectangular prism small enough to be approximately homogeneously magnetized, whereas both the magnitude and direction of the magnetization may vary from cell to cell. The magnetic field of each homogeneously magnetized cell can be expressed analytically [START_REF] Joseph | Demagnetizing field in nonellipsoidal bodies[END_REF] and hence the total magnetic field due to the magnetization can be obtained by superimposing the contributions from each cell

H body (r) ≈ - k j=1 N(r -r j ) • M j ( 5
)
where r j denotes the center of the jth cell, M j is the magnetization of the jth cell and N is the symmetric 3 × 3 tensor field with components given in Ref. [START_REF] Smith | The demagnetizing field of a non-uniform rectangular prism[END_REF]. Note that the expression given in Eq. 5 is an approximation that relies on the discretization of the rectangular prism into small cells; see Ref. [START_REF] Smith | The demagnetizing field of a non-uniform rectangular prism[END_REF] for details on sufficient grid size and the numerical implementation. The extension to a configuration of multiple prisms is done by extending the sum in Eq. 5 to include each individual prism, i.e. by combining Eqs. 1 and 5. The total magnetic field therefore becomes

H(r) ≈ H appl (r) - N i=1 k j=1 N(r -r i,j ) • M i,j , (6)
where N is the number of prisms and i is used to index the prisms. Thus, the extension to multiple prisms is obtained by dividing each prism into a set of cells and superimposing the contributions from all cells. Note that each step of the iteration ranges over the entire array, not just over a single prism. The present approach can readily be extended to cover the case of a two-or three-dimensional array of rectangular prisms. In addition, any other collection of arbitrarily shaped bodies can be divided into cells and solved using the method described here.

Results and discussion

The model is applied to the case of N prisms equally spaced with a distance d between adjacent prisms resulting in a spatial extent L = N 2c + (N -1)d of the stack in the z-direction as seen in Fig. 1. Following Ref. [START_REF] Smith | The demagnetizing field of a non-uniform rectangular prism[END_REF] the dimensions of each prism have been chosen to be 2a × 2b × 2c = 20 × 20 × 1 mm 3 and an applied magnetic field of 1 T is oriented along either the xor the z-direction. Three sets of parameter variations are considered. Firstly, the number of prisms in the stack is varied while the distance between two adjacent prisms is kept constant. Secondly, a stack of a fixed number of prisms is considered in which the distance between the prisms is varied. Thirdly, the overall spatial extent of the stack in the direction of the stacking is kept constant (i.e. L is kept fixed). The number of prisms, the distance and the thickness of the prisms are then varied within this space in order to probe the effect of the packing density of the stack on the internal magnetic field of the stack.

Varying the number of prisms

The number of prisms in the stack, N , is varied from 1 to 99 and the spacing between two adjacent prisms is kept fixed at d = c or d = 4c. In the former case the spacing between two adjacent prisms is equal to half the thickness of a single prism whereas in the latter it is equal to the thickness of two prisms. These two cases result in packing densities of 2/3 and 1/3, respectively, where the packing density, α, is given by

α = 2c d + 2c . ( 7
)
The volume average of the internal magnetic field strength in all the prisms is given in Fig. 2 for an applied magnetic field oriented along either the xor z-direction. For a single prism the volume average of the internal magnetic field strength attains its lowest value when the applied field is along the z-direction as the demagnetizing field is maximized for this orientation. The opposite is true when the applied field is in the x-direction. These results follow from the well-known single prism solution that may be found in, e.g., Ref. [START_REF] Aharoni | Demagnetizing factors for rectangular ferromagnetic prisms[END_REF].

Increasing the number of prisms when the applied magnetic field is perpendicular to the direction of the stacking (i.e. H appl x) reduces the total average internal field of the stack. Conversely, the total average internal field increases when the applied field is along the stacking direction (H appl z). This is to be expected and simply explained by considering Fig. 3. When the stacking direction is parallel with the applied field the stray field due to the magnetization of each individual magnetized body will tend to enhance the applied field in neighboring prisms, whereas the stray field tends to reduce it when the stacking is perpendicular to the applied field. Note that this entails that the largest internal field is experienced by the center prism for H appl z and the outermost In both cases the magnetic field from the prism opposes the applied field inside the prism as seen by the white field lines. Stacking the prisms perpendicular to the magnetization direction results in a decrease in the internal magnetic field, whereas parallel stacking enhances the internal field. The trends are similar for both a homogeneously magnetized prism and the inhomogeneously magnetized prism considered here. Note that the internal magnetic field is discontinuous across the surfaces containing effective magnetic charges as expected from the boundary conditions of the H-field.

prisms for H appl x, whereas the minimum internal field is found at the outer prisms and the center prism for H appl z and H appl x, respectively. The minimum and maximum values for the individual prisms are represented by the shaded areas in Fig.

2.

As the number of magnetized bodies increases, the field enhancing or reducing effect is enlarged steadily, reaching a level where the stack of prisms behaves as an infinite stack. In this case the outer boundaries become virtually negligible. This is clearly apparent from Fig. 2 for d = 4c where increasing the number of prisms from N = 49 to 99 only changes the average internal field by 0.3% and 0.6% when the applied field is along the xand z-direction, respectively. In addition the average internal field of the whole stack almost coincides with the average internal field of the center prism thereby indicating that the boundaries are indeed of minor importance. In the case where d = c the average of the total internal field in the stack is also seen to behave asymptotically, however, the convergence is less pronounced. A better description of the infinite stack is found by only considering the center prism instead as convergence is essentially reached at N = 99 and consequently the influence of the boundaries are negligible. In the remainder of this paper the internal field of the center prism in a stack of 99 prisms will therefore be used when referring to an infinite stack. Note that this assumption improves with increasing distance between the prisms. Figure 4 shows an example of the spatial variations in the magnitude of the internal field in a single prism and a stack of five prisms spaced with d = 4c. It is observed that the internal field is significantly affected when the number of prisms in the stack is greater than one. The difference between a single prism and the stack of five prisms is most pronounced in the case where the applied field is along the z-direction. In addition, the internal field in the middle prism is seen to differ from that of the surrounding prisms. This implies that the magnetization also differs and consequently all prisms must be included in the iteration performed in Eqs. 3-4 rather than using a sum of single-prism solutions.

Varying the distance between the prisms

For an infinite stack and a stack containing 19 prisms the average internal magnetic field strength is plotted in Fig. 5 as a function of the distance between the prisms given in units of the prism thickness, d/2c. As in the previous section the shaded areas in Fig. 5 mark the maximum and minimum values of the average internal field strength in the individual prisms for a given stack configuration. An increase in the distance is observed to result in an asymptotical approach towards a value of 0.96 and 0.57 T for an applied field along the xand z-direction, respectively. This behavior is almost identical for the two stacks considered. When the distance between adjacent prisms increases the stray field from each magnetized prism has less influence on neighboring prisms and the number of prisms in the individual stacks becomes less important. The asymptotic values are therefore equal to the single prism solutions seen in Fig. 2.

Interestingly, the results from the two stack configurations differ considerably at low values of the ratio d/2c. Here, the stray fields from the magnetized prisms have a much larger influence on neighboring prisms, as expected, which is also clearly manifested in a great response of the internal magnetic field strength when varying the distance. In The average internal field strength in stacks composed of rectangular prisms as a function of the distance between two adjacent prisms normalized to the thickness of a single prism. Two orientations of the applied field are provided (along the xand the z-direction). Furthermore, an infinite stack and a stack composed of 19 prisms are considered. As in Fig. 2 the shaded areas mark the maximum and minimum average internal field strengths of the individual prisms in the given configuration.

addition, when the applied magnetic field is along the z-axis and d/2c is close to zero the average internal field strength is actually significantly larger than in the case where the applied field is along the x-direction. This is not surprising considering the limit where d/2c is zero since the stack is then effectively a single prism with dimensions 2a × 2b × 2cN; here, the single prism solution dictates that the average internal field should be greater when applying the external magnetic field along the direction where the prism is thickest [START_REF] Aharoni | Demagnetizing factors for rectangular ferromagnetic prisms[END_REF]. In particular for the infinite stack the magnetic field from the magnetization vanishes if d/2c = 0 and the applied field is oriented along the direction of stacking. This is observed in Fig. 2 by the strength of the internal magnetic field almost being equal to the applied field (1 T). The small discrepancy is solely due to the fact that the infinite stack is represented by a prism surrounded by a large, albeit finite number of prisms.

Varying the packing density

Recalling the definition of the packing density, Eq. 7, maintaining a constant total stack height, L, and adding prisms such that the distance between adjacent prisms for a given number of prisms is constant, the packing density of the stack may varied consistently. In addition the packing density can be varied by changing the thickness of the prisms along the direction of stacking.

In Fig. 6a the average internal field strength of the stack is given as a function of the packing density for four different prism thicknesses. For all thicknesses it is observed that values of the packing density greater than about 90% yield the largest average internal field when the applied field is along the z-direction, whereas applying the field

µ 0 <H> [T] L = a L = 2a L = 3a L = 5a L = 7a L = 9a H appl || z H appl || x (b)
Figure 6. The average internal field strength in stacks composed of rectangular prisms as a function of the packing density. a) The packing density is varied by changing the number of equally spaced prisms while keeping the total height of the stack fixed at L = 3.2a = 32 mm. Furthermore, four different prism thicknesses are provided, c = 0.05a, c = 0.1a, c = 0.2a and c = 0.4a, and the applied field is oriented along either the xor the z-direction. b) The thickness of the prisms is kept fixed at c = 0.05a whereas the total height of the stack is varied from L = a to L = 7a. Note that for a packing density of one the stack becomes a single prism; in particular, when L = 2a the stack is a cube. in the x-direction results in the maximum average internal field of the stack for packing densities less than 90%. As the packing density increases the stack approaches a single prism with dimensions 2a × 2b × L = 20 × 20 × 32 mm 3 . Applying the field along the z-direction thus yields the strongest internal magnetic field in agreement with the single prism solution from Ref. [START_REF] Aharoni | Demagnetizing factors for rectangular ferromagnetic prisms[END_REF]. On the other hand thin prisms located in a stack with a low packing density are almost isolated and the strongest internal field is therefore found when applying the external field along the x-direction in agreement with the results of, e.g., Fig. 2.

By comparing the results from different prism thicknesses the same trends are seen. When the packing density for a given prism thickness is increased the internal field of the stack is decreased for an applied field along the x-direction and increased when applying the field in the z-direction. The trends are due to the field reducing (H appl x) or enhancing (H appl z) effects of both adding more prisms and decreasing the distance between adjacent prisms. At any packing density the strongest internal field is found when the stack is composed of thin prisms for the case of an external magnetic field applied parallel to the x-direction, whereas thicker prisms result in the highest internal field when the applied field is along the z-direction.

The effect of varying the total height of the stack while maintaining a fixed thickness of the prisms is shown in Fig. 6b. Consistent with the single prism solution increasing the height of the stack for a packing density of one increases the internal magnetic if the applied magnetic field is along the z-direction and decreases the field for the applied field oriented along the x-direction. For a packing density of one and a stack height of L = 2a, the stack is a cube in which case applying the external field along any of the principal axes results in identical average internal fields. For smaller stack heights the largest internal field is obtained by applying the external magnetic field along the x-direction for all packing densities. At greater stack heights the optimal orientation of the applied field is less trivial as it is dependent on the actual stack configuration. For a stack height of, e.g., L = 3.2a a value of around 90% was observed at which the applied field orientation that optimizes the internal field is changed. This value decreases non-linearly as the stack height is increased seemingly reaching a packing density of around 70% asymptotically. This limit can be deduced by noting that the stack in this case effectively becomes an infinite stack with an a priori unknown distance d between neighboring prisms. Varying the packing density is thus equivalent to varying the distance between the prisms in an infinite stack. The distance d ≈ c can therefore be determined by reference to Fig. 5. Recalling the definition of the packing density, Eq. 7, the packing density at which the optimal direction of the applied field changes is approximately 2/3.

Implications of the model

As we have seen, the magnetic field of the stack can differ significantly from the magnetic field of a single prism. This makes the optimization of the internal magnetic field nontrivial even for the simple stack configurations considered here. A direct implication of this is seen when considering magnetic refrigeration. Typically, stacks of parallel, ferromagnetic plates are used with the extent of the stack often determined by the spatial extent of the applied magnetic field. To increase heat transfer between the magnetic plates and the heat transfer fluid the plates are generally thin, whereas the number of plates is high in order to increase the volume of the active material. An important factor in determining the exact stack configuration and the orientation of the applied magnetic field is optimizing the internal magnetic field in the entire stack. However, considering Fig. 6a a large number of closely spaced, thin prisms results in significant magnetostatic interactions between the plates, making a numerical model a valuable tool for predicting and maximizing the internal magnetic field. In addition Fig. 6b reveals that especially the packing density and the total height of the stack can highly influence the optimal orientation of the applied magnetic field. Extending the presented model to cover conditions relevant for magnetic refrigeration, such as a temperature gradient along the plates, which may be comprised of several materials, can readily be implemented by allowing temperature and material variations in the magnetic equation of state. For a single prism the implementation of these conditions has been reported previously [START_REF] Smith | The demagnetizing field of a non-uniform rectangular prism[END_REF], but in the light of the results presented here extending this to a stack of plates may yield an internal magnetic field significantly different from that of a single plate. In addition, applying the model to two-and three-dimensional arrays of rectangular prisms is likewise of great interest.

Application of the presented model will also be relevant when considering electronic circuits where the local magnetic field play a significant role in certain cases [START_REF] Andra | Model for perpendicular hysteresis of thin magnetic films[END_REF][START_REF] Bogdanov | Reorientation, multidomain states and domain walls in diluted magnetic semiconductors[END_REF].

Conclusion

A numerical model capable of determining the spatially resolved, three-dimensional internal magnetic field in a configuration of multiple bodies with inhomogeneous and field-dependent magnetization was presented. The model was applied to a stack of equally spaced, rectangular prisms. The number of prisms, the separation between the prisms and the packing density were varied and the features of the resulting internal magnetic field explained qualitatively.

Generally, it is found that the stray field created by the magnetization of each prism can have a significant impact on the resulting internal magnetic field thus making it important to consider the full geometry of all magnetic bodies present to accurately describe the internal field. In particular it is concluded that the orientation of the applied field, which optimizes the internal field in the stack, may differ considerably from the optimal direction of the applied field for a single prism.

Figure 1 .

 1 Figure 1. The coordinate system of a stack composed of rectangular prisms each with dimensions 2a × 2b × 2c. The stacking of the prisms is in the z-direction where the prisms are thinnest. The total height of the stack is denoted L and the distance between two adjacent prisms is d.

Figure 2 .

 2 Figure 2. The average internal magnetic field strength in stacks composed of N prisms. The prisms are stacked with a distance of d = c or d = 4c and subjected to two orientations of the applied magnetic field. The shaded areas cover the area between the lowest and highest values of the average internal field in the individual prisms.

Figure 3 .

 3 Figure 3. Schematic illustration of the magnetic field from a single rectangular prism positioned in a stack. The prism is magnetized either perpendicular to the stacking direction (a) or parallel (b). In both cases the magnetic field from the prism opposes the applied field inside the prism as seen by the white field lines. Stacking the prisms perpendicular to the magnetization direction results in a decrease in the internal magnetic field, whereas parallel stacking enhances the internal field. The trends are similar for both a homogeneously magnetized prism and the inhomogeneously magnetized prism considered here. Note that the internal magnetic field is discontinuous across the surfaces containing effective magnetic charges as expected from the boundary conditions of the H-field.

Figure 4 .

 4 Figure 4. The internal magnetic field strength of a single rectangular prism (top) and a configuration of 5 prisms displaced with d = 4c (bottom; not drawn to scale) for two different orientations of the applied magnetic field. The internal magnetic field strength is averaged in the y-direction.

Figure 5 .

 5 Figure5. The average internal field strength in stacks composed of rectangular prisms as a function of the distance between two adjacent prisms normalized to the thickness of a single prism. Two orientations of the applied field are provided (along the xand the z-direction). Furthermore, an infinite stack and a stack composed of 19 prisms are considered. As in Fig.2the shaded areas mark the maximum and minimum average internal field strengths of the individual prisms in the given configuration.

Acknowledgements

The authors thank the support of the Programme Commission on Energy and Environment (EnMi) (Contract no. 2104-06-0032), which is part of the Danish Council for Strategic Research.


Fabrice Theoleyre
email: theoleyr@imag.fr

Benoit Darties
email: darties@imag.fr

Andrzej Duda
email: duda@imag.fr

Assignment of Roles and Channels for a Multichannel MAC in Wireless Mesh Networks

A multichannel MAC improves throughput in wireless mesh networks by multiplexing transmissions across orthogonal channels. In this paper, we propose an efficient way for constructing the wireless mesh structure associated with Molecular MAC, a multichannel MAC layer for efficient packet forwarding. Molecular MAC outperforms other classical approaches, but requires a specific structure for efficient operation. First, we propose a centralized protocol that provides an upper bound for constructing such a molecular structure through a MILP (Mixed Integer Linear Programming) formulation that maximizes network capacity. Then, we present two distributed self-stabilizing heuristic protocols derived from the protocols for constructing respectively a Maximum Independent Set and a Spanning Tree. We compare the performance of the proposed protocols in terms of network capacity and route length.

I. INTRODUCTION

We consider wireless mesh networks that use IEEE 802.11 wireless LANs for interconnecting mesh routers. When mesh routers use the legacy IEEE 802.11 networks with a single interface, performance of packet forwarding quickly degrades with the number of hops due to channel contention and spatial problems such as hidden, exposed, masked, and blocked nodes [START_REF] Chaudet | Performance issues with IEEE 802.11 in ad hoc networking[END_REF]. We can observe that the capacity of a wireless mesh network strongly depends on the ability of nearby mesh routers to communicate in parallel, which is only possible if neighbor routers, which may interfere, use different channels.

One way of improving performance is to use multiple non-overlapping channels. When a mesh router has several radio interfaces, it can tune them to different channels and simultaneously communicate without interference. The main problem is thus to assign channels to interfaces in a way that maximizes network capacity. If the mesh network is relatively small, we can use a global optimization approach [START_REF] Ramachandran | Interference-aware channel assignment in multi-radio wireless mesh networks[END_REF], [START_REF] Nguyen | Channel assignment for multicast in multi-channel multi-radio wireless mesh networks[END_REF]. However, for networks with an increasing number of mesh routers, distributed approaches fit better [START_REF] Avallone | A channel assignment algorithm for multi-radio wireless mesh networks[END_REF], [START_REF] Naveed | Topology control and channel assignment in multi-radio multi-channel wireless mesh networks[END_REF], [START_REF] Marina | A topology control approach for utilizing multiple channels in multi-radio wireless mesh networks[END_REF]. Hierarchical clustered networks can use one radio interface for intra-cluster communications and another one for intercluster transmissions [START_REF] Zhu | Maximizing Aggregate Throughput in 802.11 Mesh Networks with Physical Carrier Sensing and Two-Radio Multi-Channel Clustering[END_REF]. At the same time, spontaneous mesh networks may include nodes with only one single interface. In this case, nodes can dynamically switch channels so that interfering neighbor nodes simultaneously transmit on orthogonal channels. Molecular MAC proposes to organize the mesh network according to the molecular analogy [START_REF] Nassiri | Molecular architecture for autonomic wireless mesh networks[END_REF]: it divides the network into atoms with nucleus nodes operating on fixed channels and electrons that dynamically switch channels between neighbor nuclei. Recent work [START_REF]Molecular architecture for autonomic wireless mesh networks[END_REF] has shown that Molecular MAC largely outperforms standard IEEE 802.11 networks and other approaches such as MMAC (Multi-Channel MAC) [START_REF] So | Multi-channel mac for ad hoc networks: handling multi-channel hidden terminals using a single transceiver[END_REF]. However, the Molecular MAC proposal did not deal with the construction of a molecular structure: the authors left the problem to a future work. In this paper, we address the problem of constructing such a molecular structure, e.g. electing nucleus nodes and assigning channels to interfaces.

The contribution of this paper is twofold. First, we formulate the problem of electing nucleus nodes and assigning channels as a generic MILP (Mixed Integer Linear Programming) problem. Its solution leads to the optimal assignment of roles (nucleus or electron) and channels in a spontaneous mesh network. Second, we propose two distributed protocols to solve the problem in a large mesh network and evaluate their performance through simulations. We show that MILP formulation and its optimal solution provide a suitable metric to compare the performance of different heuristics. Finally, our approach and problem formulation represent a solid basis for addressing many multichannel MAC problems.

After briefly presenting Molecular MAC, we will formulate the assignment problem. Then, Section IV concerns finding the optimal solution and Section V describes two proposed distributed protocols. We evaluate their performance and conclude after discussing the related work.

II. MOLECULAR MAC OVERVIEW & MOTIVATIONS

The present paper aims at defining distributed protocols for constructing the molecular architecture required by Molecular MAC. Thus, we propose to start with a brief overview of Molecular MAC and its operation. Molecular MAC achieves efficient packet forwarding over multiple hops through multiplexing parallel transmissions over multiple channels. It solves the deafness problem without using a fixed signaling channel (if an access method reserves a channel for signaling, there are less resources available for data transmission) nor periodical rendezvous (a rendezvous increases overhead and requires one form of temporal synchronization between mesh routers).

IEEE 802.11 wireless networks work fairly well in the infrastructure mode and with small modifications to their access method, they can achieve fair distribution of bandwidth to each client [START_REF] Heusse | Idle sense: An optimal access method for high throughput and fairness in rate diverse wireless lans[END_REF]. However, several key problems arise in multihop networks, as highlighted by Chaudet et al. [START_REF] Chaudet | Performance issues with IEEE 802.11 in ad hoc networking[END_REF]. Molecular MAC proposes to extend IEEE 802.11 to efficiently deal with packet forwarding in multihop networks.

Since IEEE 802.11 access method works well in single-hop networks, Molecular MAC divides a wireless mesh network into spatially distributed atoms so that each atom uses a fixed channel different from its neighbors. An atom is composed of a nucleus and electrons. A nucleus chooses a channel for its atom and sticks to the channel all the time. Nodes at the border of atoms have the role of electrons bonding neighboring atoms: they forward traffic between atoms by dynamically switching their channels to communicate with neighboring nuclei. Two electrons do not directly communicate, because otherwise they may experience deafness when an electron tries to send a frame to another electron that is listening to another channel. There is no deafness related to a nucleus-it operates all the time on the same channel. Nodes participate in neighborhood discovery to detect new nodes and integrate them into the molecular structure with a suitable role, either nucleus or electron. Figure 1 An electron must be able to receive packets from its neighboring nuclei. To achieve this, an electron has to explicitly request a data frame from its nucleus with a special control frame, a pull that acts a little bit like a Clear To Send (CTS) frame, but the CTS reservation is only reception oriented. Finally, each nucleus piggybacks the list of pending destinations in each data frame so that the electrons know when they need to request a frame through sending a pull. A nucleus maintains this activity by sending an empty data frame fast notification.

The molecular architecture is similar to clustering, each nucleus being a clusterhead and each electron being agateway. However, we can highlight the following key differences:

1) communication only takes place over nucleus-electron or electron-nucleus links. However, the network must stay connected; 2) the molecular structure aims at minimizing interference while clustering minimizes the number of clusters; 3) each nucleus uses a static channel for its transmissions.

It should maximize network capacity. Molecular MAC reduces the number of links in the mesh, however it improves network throughput in a significant way and results in using almost the shortest routes in practice [START_REF]Molecular architecture for autonomic wireless mesh networks[END_REF].

In this paper, we propose protocols for constructing an efficient mesh molecule. Previously, our simulations have shown that Molecular MAC results in efficient packet forwarding. Our objective here is to only deal with the problem of mesh construction through role assignment and channel selection and not with more MAC oriented aspects already studied elsewhere [START_REF]Molecular architecture for autonomic wireless mesh networks[END_REF]. We present below the optimal LP formulation of the problem and heuristics for distributively assigning roles.

III. PROBLEM FORMULATION AND NOTATION

We consider the problem of constructing a wireless mesh network that follows the molecule approach. First, we introduce notation-we model the network as an undirected graph G = (V, E), where V is the set of nodes and E the set of edges corresponding to two nodes able to directly communicate. We adopt the following notation:

• n = |V| defines the number of nodes in the mesh network,

• N (u) is the set of neighbor nodes of u with cardinality

∆(u) = |N (u)|,
• {u, v} denotes the edge between vertices u and v, i.e. {u, v} ∈ E,

• BW denotes the radio bandwidth,

• CH is the set of all available channels and nbCH = |CH| their number (IEEE 802.11a has for instance 12 orthogonal channels). We need to assign a role to each node (a nucleus or an electron) so that the resulting molecule has the following properties:

1) a node can communicate with any other node via multihop forwarding, 2) only nuclei and electrons can communicate with each other, i.e. we exclude communications between two electrons or two nuclei, 3) the capacity of the network should be maximal. In particular, two neighboring atoms, which can interfere, need to use different channels. The construction of the mesh molecule is closely related to a well-known graph structure problem-a Weakly Connected Dominating Set (WCDS) [START_REF] Dunbar | On weakly connected domination in graphs[END_REF] formally defined by a set D ⊆ V such as :

∀u ∈ {V -D}, ∃v ∈ D/v ∈ N (u) (1) G(V, E ′ ) connected/ E ′ = {(u, v)/u ∈ D, v ∈ V} (2)
The set of nuclei form a restricted WCDS, i.e. a WCDS in which the graph weakly induced by the edges (nucleus,electron) forms a connected set. Formally, we transform the second property of Eq. 2 into:

G(V, E ′ ) connected/E ′ = {(u, v)/u ∈ D, v ∈ {V -D}} (3)
In other words, we remove radio links between two nuclei, because they operate in a molecular mesh at different channels. Thus, they may only communicate through neighboring electrons. In addition, we aim at constructing a restricted WCDS that maximizes network throughput multiplexing transmissions across different channels.

IV. OPTIMAL MOLECULE CONSTRUCTION AND CHANNEL

ASSIGNMENT

We start with a MILP formulation of the problem that will give us an upper bound for comparing performance of proposed distributed protocols.

Our objective is to find a suitable role for each node (nucleus or electron) and assign channels to nuclei. Since many assignments are possible, we aim at finding the allocation that maximizes network throughput. Alazemi et al. proposes to define the objective as a sum of radio transmissions [START_REF] Alazemi | Fixed channel assignment algorithm for multi-radio multi-channel mesh networks[END_REF]. As the authors state, this privileges single hop flows thus leading to a suboptimal allocation for many applications. They also propose to maximize the minimum utilization of one particular channel. Since such a macroscopic metric does not capture bottlenecks and different route lengths, it does not correspond to real network capacity. Thus, we maximize the guaranteed network throughput: we assume that all possible flows are simultaneously active and we maximize the minimum throughput allocated to each flow. This metric clearly reflects the capacity of the network to forward high load.

MILP Formulation

We assign a role to each node u ∈ V represented by variable r(u) ∈ {0, 1} with value 1 if u is a nucleus and 0 otherwise. For each pair (u, c), where u ∈ V and c ∈

[1, nbCH], variable CH(u, c) ∈ {0, 1} indicates if node u uses channel c (CH(u, c) = 1)
or not (CH(u, c) = 0). Our performance objective is to maximize T min , the minimum throughput allocated to each flow. Since all the nodes communicate with each other, there are n(n -1) flows in the network.

MILP formulation requires to define a set of variables T (u, v, d) that correspond to traffic transmitted by u through radio link {u, v} to destination d for each triplet (u, v, d)|{u, v} ∈ E, d ∈ V . As our formulation also requires traffic decomposition into different channels, we need to introduce additional variables T ch (u, v, c, d) that represent the portion of traffic going through link (u, v) to d on channel c.

1) One channel per nucleus: First, we assign exactly one channel to a nucleus and none to an electron:

∀u ∈ V, nbCH c=0 CH(u, c) ≤ r(u) (4)
2) A link between an electron and a nucleus: We can only use a link if and only if its endpoints have different roles. Its capacity (the sum of T (u, v, d) over all destinations d) is zero if both endpoints are nuclei (Eq.5) or electrons (Eq.6):

∀{u, v} ∈ E, r(u) + r(v) + 1 BW d∈V T (u, v, d) + T (v, u, d) ≤ 2 (5) 1 BW d∈V T (u, v, d) + T (v, u, d) ≤ r(u) + r(v) (6)
3) Flow conservation: Eq. 7 and 8 express the flow conservation law: traffic for d coming from u = d is equal to the sum of traffic for d forwarded by u and traffic generated by u to d (= T min ). A destination node must receive exactly (n -1).T min total traffic units sent by (n -1) other nodes:

∀u, d ∈ V, d = u, v∈N (u) T (u, v, d) = T min + v∈N (u) T (v, u, d) (7)
∀u ∈ V, (n -1).T min = v∈N (u)

T (v, u, u) (8)
4) Radio capacity: All interfering radio links need to share radio bandwidth. Obviously, the sum of traffic over all channels corresponds to the whole traffic (Eq. 9). Besides, all radio links that use the same channel must share channel capacity (Eq. 10). I(e) represents the list of links interfering with e that can be directly extracted from the conflict graph (cf. [START_REF] Jain | Impact of interference on multi-hop wireless network performance[END_REF], we associate one vertex to each radio link in the conflict graph; an edge exists in the conflict graph if two corresponding radio links interfere in the original network):

∀u ∈ V, c∈Channels T ch (u, v, c, d) ≤ T (u, v, d) (9)
∀e ∈ E, ∀c ∈ CH,

(u,v)∈I(e) d∈V T ch (u, v, c, d) ≤ BW (10
) 5) Optimizing atom capacity: All links belonging to an atom share its bandwidth BW (Eq. 11). The constraints are obvious if u is a nucleus. If u is an electron, it cannot receive more than BW, even if it is adjacent to several nuclei because of time sharing mechanisms to switch between frequencies.

∀u ∈ V, v∈N (u) d∈V T (u, v, d) + T (v, u, d) ≤ BW (11)
6) Improvement: Optional inequalities (Eq. 12) accelerate the MILP resolution by stating that each nucleus is adjacent to at least one electron and reciprocally:

∀u ∈ V, 1 ≤ r(u) + v∈N (u) r(v) ≤ ∆(u) (12)
7) MILP Objective: We aim at maximizing the minimum throughput, i.e. max T min .

V. DISTRIBUTED PROTOCOLS FOR ROLE AND CHANNEL

ASSIGNMENT

In this section, we propose two distributed protocols for constructing a molecule. In the first strategy, we adopt a pure localized approach: a node decides to become a nucleus when no other neighbors become nuclei. Thus, the first approach builds on the construction of a Maximum Independent Set (MIS). In the second strategy, we propose to construct a self-stabilizing spanning tree. By coloring appropriate nodes, we consequently construct a WCDS that achieves desired properties.

A. Maximum Independent Set

The simplest localized protocol consists of assigning the nucleus role to the nodes that do not have any neighboring nodes that become nuclei. To avoid making decisions synchronously, we force each node to start a timer for a random duration. After a timeout, a node becomes nucleus if none of its neighbors has become a nucleus. Symmetrically, the neighbors of a nucleus automatically become electrons. The resulting graph forms a Maximum Independent Set by definition: no pair of neighboring nuclei exists, each electron is a neighbor of at least one nucleus, and a node is either an electron or a nucleus. Nuclei are dominating nodes in the MIS terminology.

The first advantage of this approach is its locality property: the protocol quickly converges in finite time (more precisely, it is bounded by the timeout value). Thus, nodes can construct a MIS only with one hello packet transmitted as a broadcast.

In addition to obtaining the right role assignment, we need to minimize the number of nuclei to reduce interference between neighboring nuclei: a graph containing a smaller number of nuclei reduces the probability that two atoms use the same channel, which may result in interference. Thus, we improve the network capacity by limiting interference.

However, the main drawback of this approach relates to connectivity: a MIS does not lead to a connected graph in all cases. Consider for example a chain of four nodes: the two extremity nodes become nuclei and the other nodes are electrons-we obtain two disconnected atoms. This structure forms a MIS, but the graph weakly induced by the edges (nucleus,electron) is not always connected. Such cases occur even more frequently in networks with low density. If we have a dense random graph, the MIS will be connected with high probability: several paths exist between a pair of nodes and the probability that all paths do not exist in the restricted WCDS structure is small. To explore this issue, we have simulated random mesh networks and verified that the size of the largest connected component quickly reaches the size of the largest component in the original graph (Fig. 2).

B. Self-stabilizing spanning tree

A spanning tree is a well-known structure to maintain connectivity in networks. We propose to construct a spanningtree with desired properties in three steps.

First, we construct the shortest path spanning tree rooted at the node with the smallest identifier in the network. By propagating the minimum known identifier and its distance in hops in hello packets, each node can update the information so that the network only maintains one spanning tree. The root generates a strictly increasing sequence number in each of its hello packets. Its neighbors forward the sequence number as is thus guaranteeing loop detection when the information about the distance to the root becomes obsolete.

Second, we assign the nucleus role to each node with an even depth in the tree and the electron role otherwise. Hence, we obtain a connected structure: each node has a path alternating nuclei and electrons towards the root.

Third, since we aim at minimizing interference, we must limit the number of interfering atoms, which is equivalent to minimizing the number of nuclei. Thus, we propose a simple pruning rule to eliminate redundant nuclei: a nucleus can safely become electron if simultaneously:

1) it has no child in the tree, 2) one neighbor with a smaller id is nucleus (to break a possible tie), 3) it has no neighbor with a smaller id with the same depth. The proposed protocol is distributed: each node only needs the information transmitted in hello packets by its neighbors to decide which role it should adopt. Moreover, it converges in O(D), D being the network diameter.

Besides, the protocol is self-stabilizing converging to a valid state after a finite number of steps: the root of the spanning tree sends hello packets with an increasing sequence number. If it ceases its operation, the sequence number does not increase and all the nodes will choose another root with the new smallest identifier after a timeout. Similarly, sequence numbers avoid the appearance of loops, which is vital in mesh networks prone to failures or topology changes.

Finally, the spanning tree tends to improve the capacity by keeping a large number of radio links in the molecule (we only remove radio links among nodes with the same depth). Besides, pruning some nuclei tends to limit interference among atoms. Simulations corroborate the efficiency of the molecule construction from the network throughput point of view.

C. Channel assignment

In our distributed approach, we first propose to construct a molecule and then greedily assign channels to each nucleus. A nucleus asks its electrons to provide information about channel activity they can measure. Electrons scan all the channels, measure their activity expressed as the number of transmitted packets and report them to their nucleus. A nucleus proceeds in the following manner to collect statistics:

1) it sends a broadcast with a channel activity request to all neighboring electrons 2) the electrons scan the channels and report channel activity in a unicast frame to the nucleus 3) the nucleus eventually repeats its request in a unicast frame to non-replying electrons (to be robust to packet transmission errors). When it obtains all replies, it chooses a channel according to the following preference: a) if some channels are inactive for all electrons, randomly choose one, b) otherwise, choose the channel that minimizes the maximum activity for all the members of an atom. Nodes assign channels after deciding their roles, because a node should take into account the activity in its vicinity before choosing the best suitable channel. Moreover, the activity

VI. PERFORMANCE EVALUATION

We have simulated the proposed protocols in WsNet [START_REF] Chelius | Wsnet: a modular event-driven wireless network simulator[END_REF] using the COIN-CBC LP library [START_REF]Coin-or branch and cut[END_REF]. We randomly place nodes in a simulation area. Nodes use the IEEE 802.11a network interface to communicate with each other with the radio range of 10 units and the interference range of 30 units. WsNet assumes the free-space model for radio propagation. By default, the mesh network is composed of 50 nodes with the average number of neighbors of 10. We adjust the simulation area to obtain a given density.

The results correspond to statistics averaged over 10 different simulations of 240 seconds. The graphs present averaged values with 95% confidence intervals. We compare the performance of the MILP formulation (OPT), the Maximum Independent Set protocol (MIS), and the self-stabilizing Spanning Tree (ST) (cf. Section V).

A. Route stretch factor

First, we measure the route stretch factor: the ratio of the route lengths in a molecular mesh and in the original graph (cf. Fig. 3). A stretch factor of 1 means that only the shortest routes are used. For MIS, we discard isolated nodes since the stretch factor would become infinite in this case. Thus, we tend to under-estimate the real stretch factor for MIS. We do not have any result for the OPT strategy in networks with more than 40 nodes since MILP does not find a feasible and optimal assignment after a reasonable computing time (i.e. less than 2 hours). We can note that the OPT strategy results in using short routes. Thus, we can legitimately consider that a small stretch factor will optimize the global network throughput. ST uses longer routes than OPT, but the difference tends to decrease when the number of nodes increases: the spanning tree achieves to find short routes. On the contrary, MIS discovers longer routes when the network cardinality increases: two electrons can separate two nuclei thus forcing longer routes.

B. Capacity through channel diversity

Then, we measure network throughput defined as T min in the MILP formulation. Thus, for the ST and MIS strategies, we run the MILP formulation with already assigned roles and channels to obtain the minimum flow for each molecular topology.

We first measure the impact of the network cardinality (cf. Fig. 4) while maintaining constant density. Obviously, the OPT strategy gives us an upper bound. Moreover, we can note that MIS and ST achieve a much lower throughput: since they are distributed, they cannot optimize the global throughput as the OPT strategy does.

Second, we consider the impact of the density on the network capacity (cf. Fig. 5) while maintaining the number of nodes constant. We can observe that the capacity first increases with the density since the routes become shorter and consume less bandwidth. Then, it decreases, because the radio spatial reutilization decreases. We can also note that for high density, MIS performs better than ST: MIS efficiently prunes the network thus reducing the number of interfering nuclei. On the contrary, ST is more suitable for low density, since it maintains a good route length stretch factor helping to improve throughput.

VII. RELATED WORK

Considering multichannel wireless networks has received large attention recently: they multiplex communications over orthogonal channels thus improving the global throughput. One approach consists of dynamically switching channels on a per packet basis [START_REF] So | Multi-channel mac for ad hoc networks: handling multi-channel hidden terminals using a single transceiver[END_REF], [START_REF] Bahl | SSCH: Slotted seeded channel hopping for capacity improvement in ieee 802.11 ad hoc wireless networks[END_REF], [START_REF] Nassiri | Molecular architecture for autonomic wireless mesh networks[END_REF]. In MMAC [START_REF] So | Multi-channel mac for ad hoc networks: handling multi-channel hidden terminals using a single transceiver[END_REF], all nodes periodically reserve the channel for data transmission on a control channel. In SSCH [START_REF] Bahl | SSCH: Slotted seeded channel hopping for capacity improvement in ieee 802.11 ad hoc wireless networks[END_REF], each node chooses a pseudorandom channel sequence to follow and exchange packets with neighbors when they are on the same channel.

The second approach assigns a fixed channel to each radio link when the mesh network includes nodes with multiple radio interfaces. In this case, two nodes are able to communicate iff one of their radio interfaces uses the same channel. Alazemi et al. [START_REF] Alazemi | Fixed channel assignment algorithm for multi-radio multi-channel mesh networks[END_REF] present a MILP formulation of the multiradio multichannel assignment closely related to the problem presented here. The authors try to linearly formulate all the limiting constraints, e.g. the number of channels used per node. However, they do not optimize the global traffic, but rather channel diversity as explained in Section IV, which does not lead to the optimal network capacity. Marina et al. [START_REF] Marina | A topology control approach for utilizing multiple channels in multi-radio wireless mesh networks[END_REF] propose to greedily allocate channels when the assignment is achievable. Other authors further enrich their algorithm [START_REF] Subramanian | Minimum-interference channel assignment in multi-radio wireless mesh networks[END_REF]. This strategy is centralized and complex to transform into a distributed protocol. Avallone et al. [START_REF] Avallone | A channel assignment algorithm for multi-radio wireless mesh networks[END_REF] propose a more sophisticated strategy: they first compute a flow rate in the network without taking into account interference. Then, they extract groups and greedily assign orthogonal channels to groups with interfering links.

Other approaches propose distributed protocols for multichannel networks. Ramachandran et al. [START_REF] Ramachandran | Interference-aware channel assignment in multi-radio wireless mesh networks[END_REF] try to estimate interference to allocate orthogonal channels to interfering edges. Nguyen et al. [START_REF] Nguyen | Channel assignment for multicast in multi-channel multi-radio wireless mesh networks[END_REF] assign channels for multicast mesh networks: the case is less complex than the unicast problem, because a node just receives traffic on a channel and forwards it as a broadcast to all its children in the multicast tree. Moreover, the authors independently optimize the multicast tree and the channel assignment algorithm thus resulting in a suboptimal solution. Naveed et al. [START_REF] Naveed | Topology control and channel assignment in multi-radio multi-channel wireless mesh networks[END_REF] divide the network into clusters and allocate one channel per cluster thus limiting the route length by creating a spanner.

VIII. CONCLUSIONS AND FUTURE WORK

In this paper, we have proposed two distributed protocols for constructing the structure required by Molecular MAC. We have also formulated a MILP problem that provides an upper bound we can achieve to maximize the network throughput. In a more general way, the constraints in the MILP formulation are very common in multichannel mesh networks and can be further used for considering optimal assignment of channels for this type of networks. We are currently working on making the MILP formulation distributed so that the structure can be locally optimized. Besides, we also aim at integrating sophisticated interference measurement protocols to support our channel assignment protocol so that a mesh network selfadapts to interference and traffic variation.

Fig. 1 .

 1 Fig. 1. Two atoms sharing two electrons

Fig. 2 .

 2 Fig. 2. Size of the largest connected component in MIS for random mesh networks

Fig. 3 .

 3 Fig. 3. Route stretch factor for varying network cardinality

Fig. 4 .Fig. 5 .

 45 Fig. 4. Capacity (min-flow objective) for varying network cardinality

ACKNOWLEDGMENTS

This work was partially supported by the European Commission project WIP under contract 27402, the French Ministry of Research project AIRNET under contract ANR-05-RNRT-012-01, and France Telecom contract 3-04-36.