Network Coding in Military Wireless Ad Hoc and Sensor Networks: Experimentation with GardiNet Ichrak Amdouni * , Cedric Adjih * , Thierry Plesse † * Inria, France, Email: firstname.name@inria.fr † DGA, Bruz, France, Email: thierry.plesse@intradef.gouv.fr Abstract-Network coding is a communication paradigm that allows intermediate nodes to mix packets instead of simply relaying them. Motivated by applications in military tactical networks, this paper explores the use of the network coding. It has been proved that network coding has many benefits in wireless communications such as optimal capacity achievement and packet loss recovery. In this paper, we present a generic architecture for network coding for broadcast in wireless networks called GardiNet. GardiNet is generic; its design is divided into building blocks in order to enable it to adapt to different application scenarios. In this paper, we start by describing GardiNet for wireless ad hoc networks and in particular for wireless sensor networks (WSNs). Then, we present experiment results of GardiNet in FIT IoT-LAB, a real testbed of WSNs. Results show that network coding performs well under real wireless conditions. In addition, we highlight the benefit of the Sliding Encoding Window scheme of GardiNet (SEW) to allow sensors to decode packets in real time.

I. INTRODUCTION AND CONTEXT OF THIS WORK

The work presented here was done in the context of the GETRF project [10]. This project targets efficient transmissions in wireless military tactical networks. When sharing information in a military tactical network, it is often necessary to transmit data from one source to multiple destinations. This means that multicast and broadcast are important communication paradigms in military networks. Hence, we focus on these types of communications applied to wireless ad hoc and sensor networks. Our focus to ensure the efficiency of these communications is the use of the network coding. Unlike classical routing methods, the network coding allows intermediate nodes between a source and a destination to send linear combinations of the received packets, instead of simply relaying them. The destination should decode the packets it receives, in order to retrieve the original packets sent by the source. More explanations about this mechanism are provided in Section II-A. Now, we describe our motivations and methodology.

A. Broadcast and Multicast in Tactical Military Networks

In military tactical networks, the transmission optimization is a crucial need. Optimized transmissions reduce overhead and power consumption. Broadcast and multicast transmissions can improve the efficiency of wireless links when transmitting multiple copies of messages using the inherent radio broadcast property.

These two types of communications are used in both control plan and user plan. Concerning the control plan, routing protocols for instance are used in tactical military networks and are based on Mobile Adhoc NETworks (MANET) technologies and architectures. These MANET protocols use broadcast mechanisms for control plan information exchange. As an example, we can site the messages exchanged in OLSR: HELLO and TC (Topology Control) messages.

From a user point of view, a majority of services in a military tactical network are multicast or broadcast in nature as Commands, Situation Awareness information and Push-To-Talk voice services. These services may be present before, during or after the military operation. As examples of these services, we provide the following scenarios:

• The deployment of the forces requires position/status update messages. These messages are of different nature: voice, sensor data, Blue Force Tracking (BFT) and short messages. • During the operation, most of the data traffic consists of automatic messages (location, status). Speech is used to deliver orders. • After the military intervention, most of the traffic consists of data, mainly related to the maintenance and logistics.

B. Challenges of Broadcast in Wireless Military Tactical Networks

It appears that the multicast and broadcast are prevalent in military networks. However, some issues need to be solved. First, due to the lossy nature of wireless links, and in the absence of acknowledgement, this type of communication is not reliable. Different TDMA approaches have been proposed in order to implement completely distributed and scalable resource reservation mechanisms for military tactical ad hoc networks. They present certain limitations related to the reliability of the transmissions and the allocation of the radio resources. None of them includes a mechanism to verify the result of the broadcast transmissions (explicit ACK signaling from the receivers), which is an important problem due to the lack of reliability of radio medium. In this paper, we propose a network coding solution that is naturally packet loss resilient. Indeed, a packet has many opportunities to reach the destination as it may appear in many coded packets. Furthermore, the network coding provides an implicit mechanism for acknowledging the broadcast transmissions (via the rank information, as explained in Section II-A).

The second challenge is the efficiency. When multicast/broadcast messages are transmitted in a tactical military MANET, several mechanisms make it likely that a node receives duplicate copies of a message. To ensure an efficient usage of the bandwidth, it is essential to stop a node from transmitting the same message more than once. Thus, the duplicates of a message needs to be detected and eliminated. This is a methodology which is often referred as DPD (Duplicate Packet Detection). The DPD mechanism implies that multicast/broadcast messages are uniquely identifiable. In our work, by applying the network coding, intermediate nodes in the network transmit linear combinations of the received packets and do not forward them directly. This operation significantly reduces the duplication of packets in the network.

C. Our Methodology

Following the context of the GETRF project, we have kept in mind tactical military applications, and focused on two use cases:

• Mobile ad-hoc networks (as used in tactical military networks with microwave or VHF radio communication equipment for instance). • Wireless sensor networks (used for instance with the goal of monitoring intrusions in strategic areas). These two cases are characterized by a common feature: they are multi-hop wireless networks. This fact has implications on the design of network coding solutions.

During this work, we focused on two objectives:

• Specifying and developing a generic solution for network coding communications: the solution has the name of GardiNet. Our emphasis is on providing a modular and universal solution that can be adopted in the previously cited scenarios and also in many other ones. • Evaluating the performance of the solution of network coding in general, in the context of multi-hop wireless networks.

II. RELATED WORK A. Network Coding

In classical wired or wireless networks, coding is restricted to the sources and the end receivers, whereas the intermediate nodes are only in charge of routing and copying payloads. Network coding departs from this traditional end-to-end forwarding paradigm by enabling intermediate nodes to mix the received payloads. Hence, the intermediate nodes may recombine several input payloads into one or several output payloads. The idea of network coding has been introduced by Ahlswede, Cai, Li and Yeung in [START_REF] Ahlswede | Network information Flow, Information Theory[END_REF]. Since then, research on network coding has attracted significant interest from the research community.

B. Fundamentals of Network Coding

In this section, we present terminology and fundamentals of network coding. We introduce a general framework using the terminology adopted in the network coding taxonomy draft [START_REF] Firoiu | Network Coding Taxonomy, draft-firoiu-nwcrgnetwork-coding-taxonomy-01[END_REF].

1) Linear Coding and Random Linear Coding: In network coding, there is a source that transmits information to the network. This information is called a "flow". The flow represents a sequence of bytes at the source that needs to be broadcast. The source divides the flow in a sequence of payloads. The payloads are numbered, and can be identified by their payload index. The payloads of one flow may optionally be divided in several coding blocks (one by default). The source may have an arbitrary number of flows. We speak about intra-flow coding when each flow is coded independently from other flows. We speak about inter-flow coding when payloads from different flows can be coded together.

One possible coding algorithm is linear coding that performs only linear transformations through addition and multiplication (see Li et al. [START_REF] Li | Linear network coding[END_REF] and Koetter et al. [START_REF] Koetter | An algebraic approach to network coding[END_REF]). Precisely, linear coding assumes identically sized payloads. These payloads are vectors on a fixed Galois field. Let consider any source that multicasts k payloads (p j ) j=1,...,k . At any time, any node v receives a payload that is a linear combination of payloads p j ; that is:

i th received coded payload at node v: y (v) i = j=k j=1 g i,j p j
The sequence of coefficients for a coded payload y

(v) i at the node v denoted [g i,1 , g i,2 , ..., g i,k ] is called the "coding vector" of payload y (v) i . The matrix of coefficients [g i,j ] i=1...n,j=1...k ,
where n is the number of payloads received by any node v is called the coding matrix. Consider the example depicted in Equation 1. The vector P = [p 1 , p 2 , . . . , p n ] represents the original payloads generated by the source. Node v has the vector y v 1 , . . . , y v n of coded payloads. This vector is obtained by multiplying the matrix G by the vector P .

     y v 1 y v 2 • • • • • • y v n      Y = =     g 1,1 g 1,2 • • • g 1,k g 2,1 g 2,2 • • • g 2,k . . . . . . . . . . . . g n,1 g n,2 • • • g n,k     G × ×      p 1 p 2 • • • • • • p n      P (1)
To generate a coded payload with linear coding, any node should select coefficients. Whereas centralized deterministic methods exist, Ho and al. [START_REF] Ho | The benefits of coding over routing in a randomized setting[END_REF] presented a novel coding algorithm, which does not require any central coordination. This algorithm is called random linear coding: when a node transmits a payload, it computes a linear combination of all data it possesses with randomly selected coefficients and sends the result of the linear combination. In practice, a special header containing the coding vector of the transmitted payload may be added as proposed by Chou et al. [START_REF] Chou | Practical Network Coding, 43 th Annual Allerton Conference on Communication, Control, and Computing[END_REF].

Thinking in terms of coding vectors, at any point of time, it is possible to associate any node v with the vector space, Π v spawned by its coding vectors, and which is identified with its coding matrix. The dimension of that vector space, denoted

D v , D v dim(Π v )
, is also the rank of the matrix. By abuse of language, we call rank of any node v the rank of its coding matrix. There are many network coding methods. We speak for instance about block coding when the original payload sequence is divided into blocks, called coding blocks (as known as generations). Coding is performed only over payloads within the same block.

There is also, the sliding encoding window when the coding blocks are selected based on a sliding window. For instance, for a window size = [START_REF] Lun | Further results on coding for reliable communication over packet networks[END_REF]19], the node should code payloads having indices between 5 and 19 (from p 5 to p 19 ). In this case, coding blocks of nodes may be partially overlapping, and, over time, moving to higher original payload sequence numbers. This method has the advantage to allow a real-time decoding; any node is not obliged to wait for the reception of a whole coding block to be able to decode payloads, as in the block coding method. The solution we propose for the network coding is based on a sliding window as we will see in the remaining of this article.

2) Decoding and Rank: The rank of a node is a direct metric for the amount of useful received payloads, and a received payload is called innovative when it increases the rank of the receiving node. Ultimately, a node can decode all source payloads when its rank is equal to the total number of source payloads. In this case, we say that the decoding matrix has full rank. Decoding is done by inverting the coding matrix formed by the coding coefficients. As seen in the example of Equation 1, Y = G × P . Hence, the original payloads (p i , i = 1 . . . n) can be determined by inverting the matrix G: P = G -1 × Y (see Equation 2). Matrix inversion can be performed by Gauss Elimination.

G -1 G -1 × ×      y v 1 y v 2 • • • • • • y v n      Y = =     1 0 • • • 0 0 1 • • • 0 . . . . . . . . . . . . 0 0 • • • 1     I × ×      p 1 p 2 • • • • • • p n      P (2)

C. Benefits of Network Coding

The efficiency provided by network coding in multicast and broadcast communications has been studied for instance, by Lun et al. [START_REF] Lun | Minimum-cost multicast over coded packet networks[END_REF], and Wu et al. [START_REF] Wu | Minimum-energy multicast in mobile ad hoc networks using network coding[END_REF]. In particular, they provide methods for determining optimal network coding parameters for a given network with specific model assumptions. The work of Fragouli et al. [START_REF] Fragouli | Efficient Broadcasting Using Network Coding[END_REF] gives insights for all-to-all broadcast and illustrates how gains could be obtained compared to classical routing.

It has been argued that the network coding is best suited to multi-hop wireless networks. Indeed, compared to wired networks, they have specific properties, see for instance [START_REF] Baccelli | Multi-hop Ad Hoc Wireless Communication[END_REF], including:

• Wireless 'neighborcast': one wireless transmission by a node may reach several receivers. This property may be used to optimize broadcast.

• Time-variation: the visibility between two nodes may evolve with time, due to node mobility, physical changes in the propagation environment or other reasons. • Unreliability of wireless communications: due to wireless channel conditions or properties, transmission losses (packet erasures) potentially occur. Intuitively, by combining the received packets, a coded packet sent by an intermediate node could benefit multiple receivers simultaneously, thus improving the bandwidth efficiency. In [START_REF] Ahlswede | Network information Flow, Information Theory[END_REF], it was shown that the multicast capacity (that is the maximum number of packets that can be sent from the source to a set of terminals per time unit) can be achieved by performing network coding at the intermediate nodes. A few years later, in [START_REF] Li | Linear network coding[END_REF], it was shown that for multicast networks, linear coding suffices to achieve the capacity limit, which is the max-flow from the source to each receiving node.

The authors of [START_REF] Lun | Further results on coding for reliable communication over packet networks[END_REF] show that random linear coding technique performs asymptotically as efficiently as any other network coding method in terms of capacity, for the case of single source multicast [START_REF] Lun | Further results on coding for reliable communication over packet networks[END_REF], and its performance is determined entirely by the average rate of nodes [START_REF] Lun | On coding for reliable communication over packet networks[END_REF].

By reducing the number of transmissions required to transmit some amount of information, network coding achieves energy efficiency. In [START_REF] Masucci | Capacité de Diffusion avec Codage Réseau dans les Grilles Torique[END_REF], authors analyse the performance of network coding in torus networks. Results show that the capacity in a torus grid is equal to the number of neighbors of a node. Moreover, network coding in such networks is "near optimal" in terms of energy efficiency, in the sense that each transmission will provide innovative information (outside the vicinity of the source).

D. DRAGONCAST

DRAGONCAST [START_REF] Cho | Wireless Broadcast with Network Coding: Dynamic Rate Selection[END_REF], [START_REF] Adjih | Broadcast With Network Coding: DRAGONCAST, draft-adjih-dragoncast-00[END_REF] is a protocol for broadcasting a set of packets from one source to the entire network with network coding. The base functioning is simple: the broadcast is initiated by transmissions from the source. Every node in the network retransmits coded payloads with a changing interval between transmissions. At the same time, every node collects received coded payloads and performs decoding as they are received. Finally, termination is automatically detected when all the nodes have successfully received all data.

In this work, we have developed a solution called GardiNet which specifies and completes the different modules of DRAG-ONCAST by the information base and the signaling required to perform network coding in a wireless network.

III. GARDINET: GENERIC SOLUTION FOR NETWORK CODING A. Overview

GardiNet is a generic framework for network coding in wireless networks. It is based on intra-flow coding where the source divides the flow in a sequence of payloads of equal size (padding may be used). The design keys of GardiNet are simplicity and universality; GardiNet does not use explicit or implicit knowledge about the topology (such as the direction or distance to the source, the loss rate of the links, etc). Hence, it is perfectly suited to the most dynamic wireless networks. The protocol is distributed and requires minimal coordination. GardiNet architecture is modular, it is based on 5 building blocks (LIB, SIG, Protocol, SEW and DRAGON). Each block is almost independent. This makes GardiNet generic and hence adaptable to many application scenarios.

GardiNet derives from an existing protocol called DRAG-ONCAST. Indeed, GardiNet shares the same principles and theoretical overview of DRAGONCAST. It enriches DRAG-ONCAST by the information base and signaling required to perform broadcast in wireless networks and in wireless sensor networks in particular. Furthermore, GardiNet specifies the different blocks of DRAGONCAST. The IRTF draft [START_REF] Adjih | Broadcast With Network Coding: DRAGONCAST, draft-adjih-dragoncast-00[END_REF] is a detailed description of GardiNet and the material of this paper derives from this draft. Notice however, that in this draft, the same acronym of DRAGONCAST is kept. For clarity reasons, we replace it by GardiNet for the remaining of this paper. Also, some acronyms are changed compared to this draft.

B. The Building Blocks of GardiNet

Figure 1 illustrates the different building blocks of GardiNet. To make GardiNet the most universal possible, we separate the design of its building blocks into two categories: the protocol and the policy. The protocol category defines the general protocol aspects themselves and includes the information base LIB, the signalisation SIG and the Protocol itself. The policy category defines the higher protocol behavior and it includes the sliding encoding window SEW and the dynamic rate adaptation DRAGON. In the following, we give a brief description of all these building blocks.

1) LIB: Local Information Base: This module is responsible for maintaining all information required for the functioning of the protocol. This information base maintains information about the flows, the decoding process, and the state of the neighbors.

2) SIG: SIGnalisation: This module provides the signaling for the control plane for GardiNet. The signaling consists mainly on the specification of a header for each coded payload (e.g piggybacking). It includes information relative to the state of the node, in addition to the packet encoding information. This allows each node to maintain information about the state of its neighbors.

3) Protocol: This module is the protocol itself with message generation and message processing.

4) SEW: Sliding Encoding Window: SEW is a real-time decoding method. This method relies on implicit cooperation between neighbor nodes, in order to allow recovery of some source payloads without requiring to decode all source payloads at once. Technically, as described in [START_REF] Cho | Wireless Broadcast with Network Coding: Dynamic Rate Selection[END_REF], it ensures the existence of a low triangle in the coding matrix during the online Gauss elimination process. The method SEW relies on two principles:

• SEW coding rule: generates only coded payloads that are linear combinations within a given window. The determination of this window is a policy for SEW. • SEW decoding rule: when decoding, performs a Gaussian elimination in such a way that one coded payload is only used to eliminate the source payload with the highest possible index (i.e. the latest source payload). 5) DRAGON: Dynamic Rate Adaptation from Gap with Other Nodes: DRAGON is a dynamic payload rate adjustment policy. Every node transmits coded payloads with a specific payload rate. With DRAGON, this rate is adjusted dynamically. Essentially, the rate of the node increases if it detects that some nodes in the current neighborhood are "falling behind" in the decoding process. This is called a "dimension gap". DRAGON provides a heuristic to avoid this gap.

C. General Functioning

Figure 2 illustrates the general functioning of GardiNet. The source initiates broadcasting by sending its original data payloads. These payloads have a predefined, constant size; padding can be used if necessary. Other nodes initiate transmission of encoded payloads upon receiving the first coded payload. As an example, we observe that the node u in Figure 2 has received payloads Q 1 , Q 2 and Q 3 and has rank=3. These payloads are stored locally in the decoding information base as we will specify later. In addition to payloads, any node stores information relative to its neighbors. As an example, the node v has information about its neighbor u: (the rank and the number of neighbors). Notice that received coded payloads are stored only when they are innovative. Then, nodes transmit payloads periodically. The transmission periodicity is decided by payloads rate selection algorithms. Precisely, when intermediate nodes receive a data payload that is a source payload or a coded payload, they start scheduling encoded data transmission. The scheduling interval is decided by the policy DRAGON. Payloads transmitted by intermediate nodes are coded payloads generated using random linear coding with a specified header. This header contains information needed for decoding. For instance, we see in Figure 2 that node u piggybacks its message by adding its rank, the number of its neighbors, the encoding vector and the coded payload. Data transmission continues until nodes detect the termination condition, i.e. when themselves and all their neighbors have successfully decoded the data stream. However, a node may re-enter the transmission state. This happens when it receives a notification indicating that one neighboring node requires more coding vectors to recover some source payloads.

D. GardiNet in Practice: Heuristics

In this section, we propose two heuristics for GardiNet. First, we explain how SEW encodes and decodes payloads. Second, we describe how DRAGON adjusts rates.

1) Coding Rule of SEW: We introduce the following definitions.

Definition 1 (highest (resp. lowest) index of a coded payload): The highest (resp. lowest) index of a coded payload, is the maximum (resp. minimum) index of original encoded payloads (payloads generated by the source).

Example: For the payload Q = P 3 + P 5 + P 7 + P 8 , the highest index is 8 and the lowest index is 3.

Because all coded payloads have their own highest index and lowest index, we can also compute the maximum of the highest indices of all undecoded payloads at any node, as well as the minimum of the lowest indices. Hence, we define:

Definition 2 (The high (resp. low) index of any node): The high (resp. low) index of any node is the maximum (minimum) index of all its undecoded payloads.

Notice that a node will generally decode the source payloads from 1 up to its low index.

To ensure real-time decoding, SEW uses knowledge about the state of neighbors of one node, namely their low index. Any node restricts the generated payloads to a subset of payloads of the source such that its perceived neighbors are able to decode nearly all of them, up to a margin K. Notice that once all these neighbors may decode up to the first L-K payloads, it is unnecessary for the node to include payloads P 1 , . . . P L in its generated combinations.

Hence, the general idea of SEW is to encode payloads with indices within a given window a fixed size K. In other words, the i-th generated payload q(v, i) of any node v is given by: i-th generated payload q(v, i) = a(v, i, k)P k + .... + a(v, i, k + K)P k+K , where (P j , j = k, . . . k + K) is the set of payloads generated by the source, The sequence of coefficients for q(v, i) is the following coding vector: [0, 0, ..., a(v, i, k), a(v, i, k + 1), ..., a(v, i, k + K), ..., 0, 0]. As an example, we consider the state of node A in Figure 3. Node A has decoded payloads until index 10. Its neighbors B, C and D have lowest indices equal to 12, 10 and 13 respectively. Hence, node A codes payloads starting from index 10 which is the minimum low index of its neighbors.

A node will repeat transmissions of new random combinations within the same window, until its neighbors progress in the decoding process.

2) Decoding Rule of SEW: The intent of the SEW decoding rule, is to guarantee proper functioning of the Gaussian elimination. An example of SEW decoding rule is the following: assume that node v has received payloads q 1 and q 2 , for instance q 1 = P 1 + P 9 and q 2 = P 1 + P 2 + P 3 . Then q 1 would be used to eliminate P 9 for newly incoming payloads (the highest possible index is 9), and q 2 would be used to eliminate P 3 from further incoming payloads. On the contrary, if the SEW decoding rule was not applied and if q 1 were used to eliminate P 1 , then it would be used to eliminate it in q 2 , and would result into the computation of q 2 -q 1 = P 2 + P 3 -P 9 ; this quantity now requires elimination of P 9 , a higher index than the initial one in q 2 . In contrast, the SEW decoding rule guarantees the following invariant: during the Gaussian elimination process, the highest index of every currently undecoded payload will always stay identical or decrease.

Provided that the neighbor state is properly exchanged and known, the combination of the SEW coding rule and the SEW decoding rule, guarantees that ultimately every node will be able to decode the payloads in the window starting from its lowest index; that is, they guarantee early decoding.

Notice that improper knowledge of neighbor state might impact the performance of the method but not its correctness: if a node detects a previously unknown neighbor (for instance due to mobility), it will properly adjust its encoding window. Similarly, in GardiNet, obsolete neighbor information, for instance about disappeared neighbors, will ultimately expire.

3) DRAGON: Packet Rate Selection: The heuristic DRAGON has proposed and analyzed in [START_REF] Cho | Wireless Broadcast with Network Coding: Dynamic Rate Selection[END_REF] is inspired by Fragouli et al. [START_REF] Fragouli | A Network Coding Approach to Energy Efficient Broadcasting[END_REF]. We briefly summarize it in this section. The starting point of our heuristic DRAGON is the following observation. Indeed, for real-time decoding, the rank of nodes inside the network should be close to the index of the last source payload, and that in any case, they should at least evolve in parallel. Thus, one would expect the rank of any node to grow at the same pace as the source transmission, as in the example of optimal rate selections for static networks. Decreasing the rates of intermediate nodes by a too large factor, would not permit the proper propagation of source payloads in real time. On the contrary, increasing excessively their rates, would not increase the rate of the decoded payloads (naturally bounded by the source rate) while it would decrease energy-efficiency (by increasing the amount of redundant transmissions). The idea of the proposed rate selection is to find a balance between these two inefficient states. As we have seen, ideally the rank of a node would be comparable to the lastly sent source payload. Since we wish to have a simple decentralized algorithm, instead of comparing with the source, we compare indirectly the rank of a node with the rank of all its perceived neighbors. The key idea is to perform a control so that the rank of neighbor nodes would tend to be equalized: if a node detects that one neighbor had a rank which is too low compared to its own, it would tend to increase its rate. Conversely, if all its neighbors have greater ranks than itself, the node does not need to send payloads in fact.

Hence, DRAGON uses the following heuristic. Let present first these definitions:

• D(v, t) denotes the rank of any node v at time t.

• N (v, t) denotes the number of neighbors of the node v at time t. • g(v, t) denotes the maximum rank gap of v compared to its neighbors, normalized by the number of these neighbors. Then g(v, t) is evaluated as:

g(v, t) = M ax f or all u neighbor of v D(v, t) -D(u, t) N (u, t)
• We determine C(v, t): the payload rate of any node v at time t as follows:

• if g(v, t) > 0 then: C(v, t) = A g(v, t) where A is some constant. • Otherwise, the node stops sending encoded payloads until g(v, t) becomes larger than 0.

When computing the payload rate selection, the node uses information about its neighbors stored in the Neighbor Information Base. Indeed, any node needs the rank of each of its neighbors as well as their total number. This information is deduced from the last received payload. Although this payload might not necessarily reflect the exact values at the computation time, they provide an estimate.

IV. EXPERIMENTATION OF GARDINET IN FIT IOT-LAB

We evaluate the performance of GardiNet, we run experiments on a real WSN testbed. we implemented SEW heuristic defined in Section III-D1. The rate adaptation DRAGON is not activated in this version.

A. WSN platform FTT IoT-LAB

IoT-LAB [START_REF] Wu | Minimum-energy multicast in mobile ad hoc networks using network coding[END_REF] is a very large scale testbed, remotely accessible, and includes a total number of 2728 nodes (in 6 sites); the nodes are mostly of type "wireless sensor nodes" with a wireless radio, and are well suited to perform wireless protocol experiments.

B. Setting of the Experiment

We run experiment on the Euratech testbed in the region of Lille using 20 nodes arranged in a line. Figure 4 shows a part of this testbed. A source generates periodically payloads. Nodes receiving this payload discard it if it is not innovative and try to decode payloads. Then, they generate a random linear combination and broadcast it. The nodes are equipped with MSP430F1611 microcontroller (16-bit, 48kB flash and 10kB RAM) and CC2420 radio.

In the configuration tested, the cumulative distribution of the loss rate is illustrated in Figure 5. Notice that the network is highly lossy. Less than 20% of the links have less than 18% loss rate, and in the same spirit, more than 40% have a loss rate greater than 40%.

C. Results

We first study the evolution of the network in terms of rank and number of decoded packets. These results are depicted in Figures 6, 7 and8. We set the window size to 15.

From these figures, we notice the following remarks. • The rank and the decoding process evolve progressively in time, which means that the GardiNet nodes are not blocked.

• The rank and the number of decoded payloads evolve very closely (see Figure 8). This is the advantage of the real time decoding of GardiNet. Whereas, with classical random linear coding, decoding might occur at the end. • However, we still notice some plateau in the number of decoded packets plot. This is expected and corresponds to the instants where the neighbors of selected nodes advance their encoding window. Indeed, nodes code packets from their low index to low index+K, where K is the window size. When this index in incremented, the receiver nodes cannot decode the received packets immediately because these packets have not been seen previously. This is confirmed by the result in Figure 9 that illustrates the evolution of the lowest index at nodes 97, 102 and 137. • Notice that, globally, the progress of the rank at the selected nodes is not very different. Same remark applies for the number of decoded packets. This means that the network nodes evolve in parallel. Of course, this result is positive when the nodes progress is good. It is the case here. The window mechanism of SEW allows nodes to have near progress speed which is beneficial mainly for real time applications. However, we notice that the progress of the rank of node 167 is the slowest one (see Figure 6). This is because this node is the farthest node from the source compared to other nodes (see Figure 10 where the source is node 97). Indeed, the probability to receive innovative packets is higher at nodes close to the source. Hence, these nodes would decode earlier. Now, we set the window size to 25 and run the same experiment. We want to determine the impact of the window size. We observe that the rank evolution is almost not impacted by the window size (see Figures 11 and12). The number of decoded packets is slightly impacted (see Figures 13 and14). When the window size increases, the decoding is relayed. For instance, node 102 decodes almost 41 packets at instant 300 seconds if the window size is 15, and decodes the same number of packets at 350 seconds if the window size is 25. This is because, when the window size increases, the number of undecoded packets at any node increases (new column in the coding matrix), and hence more time is needed for the node to decode them.

V. CONCLUSION

In this paper we described GardiNet, a generic architecture for network coding applied to broadcast in wireless networks.

We conducted an experimental study on a real testbed of wireless sensor networks. Results prove that GardiNet works well under real conditions even on wireless sensor nodes with limited resources. Also, we noticed that the network coding operates well even with highly lossy and unreliable links found in our testbed. This confirms that GardiNet meets the known benefits of network coding in wireless networks. We also illustrate the sliding encoding window mechanism SEW. Recall that according to SEW, nodes encode payloads regarding only the first undecoded payload at neighbors. However, in the network, nodes may have heterogeneous encoding rates. Hence, we may find late nodes, that is nodes whose first undecoded payload is very smaller than the first undecoded index of all their neighbors. Such late nodes may prevent their neighbors from increasing their sliding window and then slow their decoding progress. As a future work, we plan to enhance SEW to handle this heterogeneity issue. Also, we will consider the buffer overflow problem.

Fig. 1 .

 1 Fig. 1. Organization of the different building blocks of GardiNet.

Fig. 2 .

 2 Fig. 2. The general functioning of GardiNet.

Fig. 3 .

 3 Fig. 3. Illustration of coding rule of SEW

Fig. 4 .

 4 Fig. 4. Euratech testbed in Inria Lille.

Fig. 5 .Fig. 6 .Fig. 7 .

 567 Fig. 5. Cumulative distribution of the loss rate.

Fig. 8 .

 8 Fig. 8. The evolution of the rank and the number of decoded packets at node 137.

Fig. 9 .Fig. 10 .

 910 Fig. 9. Low index of generated packets at nodes 97, 102 and 137.

Fig. 11 .Fig. 12 .Fig. 13 .Fig. 14 .

 11121314 Fig. 11. The rank of nodes 102, 137 and 167 for window size = 15.

ACKNOWLEDGMENT

This

work has been partly supported by DGA/ASTRID/ANR-11-ASTR-0033 under the GETRF project.


Mihai Turinici

FUNCTION VARIATIONAL PRINCIPLES AND NORMED MINIMIZERS

Keywords: 2010 Mathematics Subject Classification. 49J53 (Primary), 54H25 (Secondary) Metric space, bounded from below lsc function, variational principle, normal and comparison function, maximal element, Zorn order, inductive and regular order, Hilbert space, Gâteaux derivative, minimizer, Palais-Smale condition

The function variational principle due to El Amrouss [Rev. Col. Mat., 40 (2006), 1-14] may be obtained in a simplified manner. Further applications to existence of minimizers for Gâteaux differentiable bounded from below lsc functions over Hilbert spaces are then provided.

Introduction

Let (M, d) be a complete metric space; and ϕ : M → R be (M, d)-regular; i.e., (a01) ϕ is bounded below (inf ϕ(M ) > -∞) (a02) ϕ is d-lsc on M (lim inf n ϕ(x n ) ≥ ϕ(x), whenever x n d -→ x). Define for each θ ≥ 0 ulev(ϕ; M ; θ) = {x ∈ M ; ϕ(x) ≤ inf ϕ(M ) + θ}; this will be referred to as the θ-upper level set of ϕ with respect to M ; in particular, ulev(ϕ; M ; 0) is nothing else than the (global) minimizers set of ϕ over M . The following 1974 statement in Ekeland [START_REF] Ekeland | On the variational principle[END_REF] (referred to as Ekeland's variational principle; in short: EVP) is well known. This principle found some basic applications to control and optimization, generalized differential calculus, critical point theory and global analysis; we refer to the 1979 paper by Ekeland [START_REF] Ekeland | Nonconvex minimization problems[END_REF] for a survey of these. So, it cannot be surprising that, soon after its formulation, many extensions of (EVP) were proposed. For example, the abstract (order) one starts from the fact that, with respect to the Brøndsted order [START_REF] Brøndsted | Fixed points and partial orders[END_REF] (on M ) (x, y ∈ M ): x ≤ y iff (ε/δ)d(x, y) ≤ ϕ(x) -ϕ(y) the point v ∈ M appearing in the second conclusion above is maximal; so that, (EVP) is nothing but a variant of the Zorn-Bourbaki maximal principle [START_REF] Zorn | A remark on method in transfinite algebra[END_REF][START_REF] Bourbaki | Sur le théorème de Zorn[END_REF]; see Hyers et al [START_REF] Hyers | Topics in Nonlinear Analysis and Applications[END_REF]Ch 5] for a number of technical aspects. The dimensional way of extension refers to the ambient space (R) of ϕ(M ) being substituted by a (topological or not) vector space; an account of the results in this area is to be found in the 2003 monograph by Goepfert et al [START_REF] Goepfert | Variational Methods in Partially Ordered Spaces[END_REF]Ch 3]. Further, the (pseudo) metrical one consists in conditions imposed to the ambient metric over M being relaxed. The basic result in this direction was obtained in 1992 by Tataru [START_REF] Tataru | Viscosity solutions of Hamilton-Jacobi equations with unbounded nonlinear terms[END_REF], via Ekeland type techniques; subsequent extensions of it may be found in the 1996 paper by Kada et al [START_REF] Kada | Nonconvex minimization theorems and fixed point theorems in complete metric spaces[END_REF]. Finally, we must add to this list the functional extension of (EVP) obtained in 1997 by Zhong [START_REF] Zhong | A generalization of Ekeland's variational principle and application to the study of the relation between the weak P.S. condition and coercivity[END_REF] (and referred to as Zhong's Variational Principle; in short: ZVP). Let again ϕ : M → R be a (M, d)-regular function. Further, take

a normal function t → b(t) from R + := [0, ∞[ to R 0 + :=]0, ∞[; i.e., (a03) b(.) is increasing and continuous (a04) B(∞) = ∞, where B(t) = t 0 (1/b(τ ))dτ, t ≥ 0. Theorem 1.2.
Let ε > 0 be given, as well as some u ∈ ulev(ϕ; M ; ε). Further, let x 0 ∈ M and δ, ρ > 0 be taken according to δ ≤ B(r + ρ) -B(r), where r := d(x 0 , u).

There exists then v = v(ε, u; x 0 , δ, ρ) in M , with (12-a) ϕ(u) ≥ ϕ(v), d(x 0 , v) ≤ r + ρ (12-b) (ε/δ)d(v, x)/b(d(x 0 , v)) > ϕ(v) -ϕ(x), for each x ∈ M \ {v}.
Now, evidently, (ZVP) includes (for b = 1, x 0 = u, and δ = ρ) the local version of (EVP) based upon (11-a) (the second half). The relative form of the same, based upon (11-a) (the first half) also holds (but indirectly); see Bao and Khanh [START_REF] Bao | Are several recent generalizations of Ekeland's variational principle more general than the original principle?[END_REF] for details. Summing up, (ZVP) includes (EVP); but the provided argument is rather involved. A simplification of the proposed reasoning was given in Turinici [START_REF] Turinici | Function variational principles and coercivity[END_REF], by a technique developed in Park and Bae [START_REF] Park | On the Ray-Walker extension of the Caristi-Kirk fixed point theorem[END_REF]; note that, as a consequence of this, (ZVP) is nothing but a logical equivalent of (EVP).

Recently, a local functional version of (EVP) was established by El Amrouss [START_REF] Amrouss | Variantes du principle variationnel d'Ekeland et applications[END_REF]. Let ϕ : M → R be a (M, d)-regular function. Further, let the function a : R + → R 0 + be admissible, in the sense (a05) a(.) is increasing and continuous (a06) a(.) is a comparison function, of order k > 0 (∀q ≥ k, ∃λ, µ ≥ 0 : a((t + 1)s) ≤ a(t)[λs q + µ], ∀t, s ≥ 0).

Denote also, for

u ∈ M , ρ > 0, M [u, ρ] = {x ∈ M ; d(u, x) ≤ ρ}, M (u, ρ) = {x ∈ M ; d(u, x) < ρ}
(referred to as: the closed/open sphere with center x and radius ρ). Finally, take some x 0 ∈ M and some function γ :

M → R 0 + , with (a07) u → γ(u)/(1 + d(x 0 , u)) is bounded on M .
The following result (referred to as El Amrouss Ordering Principle; in short: EAOP) is now available. Theorem 1.3. Let ε, δ > 0 be given, as well as some u ∈ ulev(ϕ; M ; ε). There exists then a sequence

(z n ; n ≥ 0) in M [u, γ(u)] and a point v ∈ M [u, γ(u)], with the properties (13-a) z 0 = u, lim n z n = v and (d(x 0 , z n ); n ≥ 0) is ascending (13-b) j n=0 d(z n , z n+1 )/a(d(x 0 , z n+1 )) < 2δ, for all j ≥ 0 (13-c) ϕ(u) ≥ ϕ(v) and d(u, v) ≤ min{γ(u), δa(d(x 0 , v))} (13-d) (ε/δ)d(v, w)/a(d(x 0 , w)) ≥ ϕ(v) -ϕ(w), for all w ∈ M [u, γ(u)] \ M (x 0 , d(x 0 , v)).
In particular, the constant function a = 1 is admissible. Note that the variational conclusion (13-d) above (retainable for certain points of a closed sphere in M ) is effectively stronger than the variational conclusion (12-b) (valid for all elements of M ). Despite this local character, (EAOP) found some nice applications in Variational Analysis; see the quoted paper for details. So, a technical analysis of its basic lines may be not without profit. It is our aim in this exposition to show (in Section 3) that a simplification of this reasoning is possible, by reducing (EAOP) to the metrical version of (EVP) in Turinici [START_REF] Turinici | Maximality principles and mean value theorems[END_REF] (cf. Section 2). This, among others, allows a re-consideration of the admissibility concept; in fact, we simply show that the comparison type condition (a06) may be dropped. Further, Section 4 is devoted to a differential version of our main result, in Hilbert spaces. Finally, in Section 5, an application of the differential result above to existence of minimizers for Gâteaux differentiable regular functions acting over Hilbert spaces is considered. Some other aspects of this problem will be discussed elsewhere.

Metrical ordering principles

Let (M, d) be a metric space; and ( ) be an order (reflexive, transitive, antisymmetric relation) over it; the resulting triple (M, d; ) will be termed an ordered metric space. A point z ∈ M is called ( )-maximal, when w ∈ M , z w =⇒ z = w; and the order ( ) is termed a Zorn one, when:

for each x ∈ M there exists a ( )-maximal z ∈ M with x z. For a number of both practical and theoretical reasons, it would be useful to establish under which conditions is such a property retainable. The standard way of solving this question is based upon the chains (i.e.: totally ordered subsets) of the structure (M, ); cf. Bourbaki [START_REF] Bourbaki | Sur le théorème de Zorn[END_REF]. However, under the precise metrical setting, a denumerable version of such principles is more appropriate for our purposes. This will necesitate a few conventions and auxiliary facts. Let (x n ) be a sequence in M ; we shall term it ascending (resp.: descending), if

x i x j (resp.: x i x j ) when i ≤ j. Further, a point u ∈ M is called an upper bound of our sequence (x n ), provided

x n u, for all n (written as: (x n ) u); when such elements u exist, we say that (x n ) is bounded above (modulo ( )).

The following 1984 answer to the above problem (referrred to as: metrical Zorn-Bourbaki principle; in short: (ZB-m)) is provided in Turinici [START_REF] Turinici | A generalization of Altman's ordering principle[END_REF]:

Proposition 2.1. Suppose that (b01) ( ) is inductive: each ascending sequence is bounded above (modulo ( )) (b02) ( ) is regular: each ascending sequence is a d-Cauchy one. Then, ( ) is a Zorn order.
Note that the semimetric variant of (ZB-m) includes the 1976 ordering principle due to Brezis and Browder [START_REF] Brezis | A general principle on ordered sets in nonlinear functional analysis[END_REF] (in short: BB); which in turn, includes Ekeland's Variational principle [START_REF] Ekeland | Nonconvex minimization problems[END_REF] (i.e.: EVP). It is worth remarking that, by developments like in Cârjȃ et al [8, Ch 2, Sect 2.1], (ZB-m) is deductible from the Principle of Dependent Choices (in short: DC) due to Bernays [START_REF] Bernays | A system of axiomatic set theory: Part III. Infinity and enumerability analysis[END_REF] and Tarski [START_REF] Tarski | Axiomatic and algebraic aspects of two theorems on sums of cardinals[END_REF]; see also Wolk [START_REF] Wolk | On the principle of dependent choices and some forms of Zorn's lemma[END_REF]. Finally, (EVP) includes (DC), as results from the 1987 paper by Brunner [START_REF] Brunner | Topologische Maximalprinzipien[END_REF], and its refinement in Turinici [START_REF] Turinici | Sequential maximality principles[END_REF]. Summing up, we have

(DC) =⇒ (ZB-m) =⇒ (BB) =⇒ (EVP) =⇒ (DC);
whence, all members of this inclusion chain are mutually equivalent. This assertion comprises as well the variational statements in Altman [START_REF] Altman | A generalization of the Brezis-Browder principle on ordered sets[END_REF], Kang and Park [START_REF] Kang | On generalized ordering principles in nonlinear analysis[END_REF], or Turinici [START_REF] Turinici | Metric variants of the Brezis-Browder ordering principle[END_REF]; we do not give details.

A basic particular case of these developments is the following. Let again (M, d; ) be an ordered metric space. Call the subset Z ⊆ M , ( )-closed if:

the limit of each ascending (modulo ( )) sequence in Z belongs to Z. For example, this holds whenever Z is closed; but the reciprocal is not in general true. Further, let us say that ( ) is self-closed, when;

M (x, ) := {y ∈ M ; x y} is ( )-closed, for each x ∈ M ; or, equivalently: the limit of each ascending sequence is an uper bound of it (modulo ( )). In particular, this holds whenever (cf. Nachbin [START_REF] Nachbin | Topology and Order[END_REF]Appendix]):

( ) is closed from the right: M (x, ) is closed, for each x ∈ M ; but, the converse is not in general valid. Finally, call d, ( )-complete if each ascending (modulo ( )) d-Cauchy sequence in M is d-convergent. For example, this always happens when d is complete (in the usual sense). The reciprocal is not in general true; just take M =]0, 1], endowed with the standard metric and order.

The following maximal type statement (referred to as: strong metrical Zorn-Bourbaki principle; in short: (ZB-m-s)) established in 1981 by Turinici [START_REF] Turinici | Maximality principles and mean value theorems[END_REF], will be useful for us. The proof consists in verifying that, under (b03) (the second half) and (b04), the ambient order ( ) is inductive; we do not give details.

Extension of (EAOP)

With this information at hand, we may now return to the posed questions of introductory part.

Let (X, d) be a complete metric space; and ϕ : X → R be a function with the (X, d)-regular properties; i.e.:

(

c01) ϕ is bounded below (inf ϕ(X) > -∞) (c02) ϕ is d-lsc on X (lim inf n ϕ(x n ) ≥ ϕ(x), whenever x n d -→ x).
Further, let the function a : R + → R 0 + be taken as (c03) a(.) is increasing (t 1 ≤ t 2 implies a(t 1 ) ≤ a(t 2 )). Finally, take some point x 0 ∈ X (fixed in the sequel).

(A) Let (≤) stand for the relation (in X) (z, w ∈ X): z ≤ w iff d(x 0 , z) ≤ d(x 0 , w). Clearly, it is reflexive and transitive; i.e., it is a quasi-order on X. Further, let us fix ε, δ > 0 and consider the relation (z, w ∈ X): z ⊥ w iff (ε/δ)d(z, w)/a(d(x 0 , w)) ≤ ϕ(z) -ϕ(w). For the moment, (⊥) is reflexive and antisymmetric. Further properties of this (and the preceding) object are contained in

Lemma 3.1. The couple (≤, ⊥) is transitively compatible, in the sense u ≤ v ≤ w, u ⊥ v, v ⊥ w =⇒ u ⊥ w.
Proof. Let u, v, w ∈ X be as in the premise of this implication; that is

(i) d(x 0 , u) ≤ d(x 0 , v) ≤ d(x 0 , w) (ii) (ε/δ)d(u, v)/a(d(x 0 , v)) ≤ ϕ(u) -ϕ(v), (ε/δ)d(v, w)/a(d(x 0 , w)) ≤ ϕ(v) -ϕ(w)
. By the increasing property of a(.), we have

a(d(x 0 , v)) ≤ a(d(x 0 , w)) [whence, 1/a(d(x 0 , w)) ≤ 1/a(d(x 0 , v))];
so that, the second half of working condition gives

(ε/δ)d(u, v)/a(d(x 0 , w)) ≤ ϕ(u) -ϕ(v), (ε/δ)d(v, w)/a(d(x 0 , w)) ≤ ϕ(v) -ϕ(w);
wherefrom (by the triangular property of d)

(ε/δ)d(u, w)/a(d(x 0 , w)) ≤ (ε/δ)(d(u, v) + d(v, w))/a(d(x 0 , w)) ≤ ϕ(u) -ϕ(w);
i.e., u ⊥ w; hence the conclusion.

As a consequence of this, the "product" relation ( ) over X (z, w ∈ X): z w iff z ≤ w, z ⊥ w is reflexive, transitive and antisymmetric; hence, an ordering on X. Our next objective is to establish that the strong metrical Zorn-Bourbaki principle (ZB-m-s) is applicable on each structure (M, ; d); where M is a (nonempty) closed bounded part of X. This is clearly the case with the ( )-completeness property; because (as M is closed) we necessarily have

d is complete on M ; hence, d is ( )-complete on M .
So, it remains to verify that ( ) is regular and self-closed (over this class of subsets). (B) We start with the verification of regularity condition. A positive answer to this is given in Lemma 3.2. The introduced order ( ) is boundedly regular; i.e., each ascending (modulo ( )) bounded sequence in X is d-Cauchy. And, as such, ( ) is regular over each (nonempty) closed bounded part M of X.

Proof. Let (y n ) be some bounded sequence in X with y n y n+1 , ∀n; or, equivalently: y n y m , whenever n ≤ m. By the very definition of our order ( ), this amounts to the couple of conditions below being fulfilled (asc-1) d(x 0 , y n ) ≤ d(x 0 , y m ), whenever n ≤ m (asc-2) (ε/δ)d(y n , y n+1 )/a(d(x 0 , y n+1 )) ≤ ϕ(y n ) -ϕ(y n+1 ), ∀n. The boundedness condition upon (y n ) means µ := sup{d(y i , y j ); i ≤ j} < ∞; hence d(x 0 , y n ) ≤ d(x 0 , y 0 ) + d(y 0 , y n ) ≤ ν := d(x 0 , y 0 ) + µ, ∀n. Combining with (asc-2) yields (by the increasing property of a(.)) Proof. Let (y n ) be some ascending (modulo ( )) sequence in X; i.e., conditions (asc-1) and (asc-2) (see above) are fulfilled. In addition, assume that (for some y ∈ X) y n d -→ y (i.e.: d(y n , y) → 0) as n → ∞. By (asc-1) and continuity of u → d(x 0 , u), one gets (passing to limit as m → ∞) d(x 0 , y n ) ≤ d(x 0 , y) (i.e.: y n ≤ y), for all n. So, combining with (asc-2) (and a(.) being increasing) (ε/δ)d(y n , y n+1 )/a(d(x 0 , y)) ≤ ϕ(y n ) -ϕ(y n+1 ), for all n. This, by the triangular property of d, gives

(ε/δ)d(y n , y n+1 )/a(ν) ≤ ϕ(y n ) -ϕ(y n+1 ), ∀n.
(ε/δ)d(y n , y m )/a(d(x 0 , y)) ≤ ϕ(y n ) -ϕ(y m ), for n ≤ m.
Passing to lim inf as m → ∞, one derives (by the d-lsc property of ϕ)

(ε/δ)d(y n , y)/a(d(x 0 , y)) ≤ ϕ(y n ) -ϕ(y) (i.e.: y n ⊥ y), for all n.
Hence, (y n ) y; and this ends the argument.

We are now in position to formulate an appropriate variational result involving these data. Let the general conditions above be accepted. Precisely, let (X, d) be a complete metric space; and ϕ : X → R be a function with (regu) ϕ is (X, d)-regular (see above). Remember that, for each θ ≥ 0 we denoted ulev(ϕ; X; θ) = {x ∈ X; ϕ(x) ≤ inf ϕ(X) + θ};

this will be referred to as the θ-upper level set of ϕ with respect to X; in particular, ulev(ϕ; X; 0) is nothing else than the (global) minimizers set of ϕ over X. Further, let the function a : R + → R 0 + be chosen according to (incr) a(.) is increasing (t 1 ≤ t 2 implies a(t 1 ) ≤ a(t 2 )). Finally, pick some point x 0 ∈ X; and let u → γ(u) be a function from X to R 0 + . The following extended El Amrouss Ordering Principle (in short: (EAOP-ext)) is now available: Theorem 3.1. Let ε, δ > 0 be given, as well as some point u ∈ ulev(ϕ; X; ε).

There exists then another point

v = v(ε, δ; u) ∈ X[u, γ(u)], with (31-a) d(x 0 , u) ≤ d(x 0 , v), (ε/δ)d(u, v)/a(d(x 0 , v)) ≤ ϕ(u) -ϕ(v); hence d(u, v) ≤ min{γ(u), δa(d(x 0 , v))} (31-b) w ∈ X[u, γ(u)] \ {v}, d(x 0 , v) ≤ d(x 0 , w) imply (ε/δ)d(v, w)/a(d(x 0 , w)) > ϕ(v) -ϕ(w); hence, (ε/δ)d(v, w)/a(d(x 0 , v)) > ϕ(v) -ϕ(w).
Proof. Denote for simplicity M = X[u, γ(u)], where u is as before. Clearly, M is closed bounded; as well as nonempty (since u ∈ M ). Let also ( ) stands for the (product) order (z, w ∈ X): z w iff z ≤ w (i.e.: d(x 0 , z) ≤ d(x 0 , w)), and z ⊥ w (i.e.: (ε/δ)d(z, w)/a(d(x 0 , w)) ≤ ϕ(z) -ϕ(w)). By the preliminary facts above, the strong metrical Zorn-Bourbaki principle (ZBm-s) applies to (M, d; ); so that (the restriction to M of) ( ) is a Zorn order (over M ). This means that, for the starting point u ∈ M , there exists another

point v = v(u) ∈ M , with (31-c) u v (i.e.: u ≤ v and u ⊥ v) (31-d) v w ∈ M =⇒ v = w (i.e.: w ∈ M, v ≤ w, v ⊥ w ⇒ v = w).
The former of these means, by definition (31-e) d(x 0 , u) ≤ d(x 0 , v), (ε/δ)d(u, v)/a(d(x 0 , v)) ≤ ϕ(u) -ϕ(v). Note that, as a consequence of its second half, ϕ * ≤ ϕ(v) ≤ ϕ(u), where ϕ * := inf ϕ(X); so that (by the choice of u)

ϕ(u) -ϕ(v) ≤ ϕ(u) -ϕ * ≤ ε.
This, again combined with (31-e) (the second half), gives

d(u, v) ≤ δa(d(x 0 , v)); hence d(u, v) ≤ min{γ(u), δa(d(x 0 , v))};
which, along with (31-e), is just our first conclusion in the statement. On the other hand, (31-d) may be written as (by definition)

(31-f) whenever w ∈ M fulfills d(x 0 , v) ≤ d(x 0 , w) and (ε/δ)d(v, w)/a(d(x 0 , w)) ≤ ϕ(v) -ϕ(w), then v = w; or, equivalently,
for each w ∈ M \ {v} with d(x 0 , v) ≤ d(x 0 , w), we must have (ε/δ)d(v, w)/a(d(x 0 , w)) > ϕ(v) -ϕ(w); which is just the first half of second conclusion in the statement. The second half of the same is immediate, in view of

d(x 0 , v) ≤ d(x 0 , w) =⇒ a(d(x 0 , v)) ≤ a(d(x 0 , w)) =⇒ 1/a(d(x 0 , v)) ≥ 1/a(d(x 0 , w)).
The proof is thereby complete.

Technically speaking, this result may be viewed as a refinement of El Amrouss Ordering Principle (EAOP). Remember that, in the quoted statement, the extra regularity conditions below were considered (in our notations) (c04) a(.)

is continuous on R + (c05) a(.) is a comparison function, of order k > 0 (∀q ≥ k, ∃λ, µ ≥ 0 : a((t + 1)s) ≤ a(t)[λs q + µ], ∀t, s ≥ 0) (c06) u → γ(u)/(1 + d(x 0 , u))
is bounded on X. The proposed argument tells us that, in the refined principle (EAOP-ext), all these regularity conditions may be dropped. This may have some theoretical impact upon the quoted result; but, in general, not a practical one.

Finally, the obtained "relaxed" principle (EAOP-ext) allows us (in a limited sense) some comparison type operations with Zhong's Variational Principle (ZVP). For, as precise, a direct consequence of conclusion (31-b) is (by the increasing property of a(.))

(31-g) w ∈ X[u, γ(u)] \ {v}, d(x 0 , v) ≤ d(x 0 , w) imply (ε/δ)d(v, w)/a(d(x 0 , v)) > ϕ(v) -ϕ(w)
. This, added to the fact that (12-b) =⇒ (31-g) under b = a, tells us that the variant of (EAOP-ext) -with (31-g) in place of (31-b) -is obtainable from (ZVP), whenever (c06) the function a(.) is normal (see above). However, a general inclusion of this type is not accessible for the moment. Further aspects will be discussed elsewhere.

Differential versions

The usefulness of our main result above is to be judged in a differential context only. For, as we shall see further, this setting has an essential role in solving the minimizers problem for such (nonlinear) functions.

Having these precise, it is our aim in the following to establish a differential version of extended El Amrouss Ordering Principle (EAOP-ext), within the class of Gâteaux differentiable regular maps acting on a Hilbert space. Note that, such a context is not the most general one; but, for the applications to be considered, this will suffice.

Let H be a (real) Hilbert space with respect to the scalar product (x, y) → x, y . As usually, we denote by ||.|| the norm induced by this scalar product; and by d, its associated metric:

(||x|| = x, x 1/2 ; x ∈ H), (d(x, y) = ||x -y||; x,
(d01) ϕ is bounded below (inf ϕ(H) > -∞) (d02) ϕ is d-lsc on H (lim inf n ϕ(x n ) ≥ ϕ(x), whenever x n d -→ x)
. Define for each θ ≥ 0 ulev(ϕ, H; θ) = {x ∈ H; ϕ(x) ≤ inf ϕ(H) + θ}; this will be referred to as the θ-upper level set of ϕ with respect to H; in particular, ulev(ϕ; H; 0) is nothing else than the (global) minimizers set of ϕ over H. The differential setting we just evoked is to be introduced as follows. Let z ∈ H be arbitrary fixed. We say that ϕ is Gâteaux differentiable at z when there exists an element ϕ (z) ∈ H (the Gâteaux differential of ϕ at z), with lim t→0+ (1/t)(ϕ(z + th) -ϕ(z)) = ϕ (z), h , for all h ∈ H. Suppose that (in addition to (d01)+(d02)) (d03) ϕ is Gâteaux differentiable over H: ϕ (z) exists (cf. this definition), ∀z ∈ H. Denote, for each z ∈ H,

C(z) = {h ∈ H; z, h ≤ 0}; C 1 (z) = C(z) ∩ ∂H 1 . Clearly, C(z) is a convex cone in H; i.e.: C(z) + C(z) ⊆ C(z), R + C(z) ⊆ C(z).
On the other hand, C 1 (z) is always non-degenerate; precisely,

C 1 (0) = ∂H 1 ; C 1 (z) -z/||z|| = 0, z ∈ H \ {0}. Denote also (for each z in H) ν(ϕ (z)) = sup{ ϕ (z), h ; h ∈ C 1 (z)}, |ν|(ϕ (z)) = max{ν(ϕ (z)), 0}. Note that, in view of | ϕ (z), h | ≤ ||ϕ (z)|| • ||h|| ≤ ||ϕ (z)||, ∀h ∈ C 1 (z)
, ∀z ∈ H, we must have (for all such z) ν(ϕ (z)) ∈ R; hence, |ν|(ϕ (z)) ∈ R + . Finally, take some function a : R + → R 0 + , according to (d04) a(.) is increasing (t 1 ≤ t 2 implies a(t 1 ) ≤ a(t 2 )); and introduce the mappings (from

H to R 0 + ) β(u) = ||u|| + 1, γ(u) = 2β(u) = 2||u|| + 2, u ∈ H.
As a direct application of extended El Amrouss Ordering Principle (EAOP-ext), we have the following statement, referred to as: differential El Amrouss Ordering Principle (in short: (EAOP-dif)): Theorem 4.1. Let ε > 0 be given, as well as some u ∈ ulev(ϕ; H; ε). Further, let δ > 0 be taken according to (d05) δ < β(u)/a(3β(u)) (hence, δa(3β(u)) < β(u)). There exists then v = v(ε, u, δ) ∈ H, with the properties (41-a) ||u|| ≤ ||v||, ϕ(u) ≥ ϕ(v), and ||u -v|| ≤ min{γ(u), δa(||v||)}

(41-b) ||u -v|| < β(u) < γ(u); hence, v ∈ H(u, β(u)) ⊆ H(u, γ(u)) (41-c) (ε/δ)t/a(||v||) > ϕ(v) -ϕ(v -th), for 0 < t < β(u), whenever h ∈ C 1 (v) (i.e.: h ∈ ∂H 1 and v, h ≤ 0) (41-d) ε/δa(||v||) ≥ |ν|(ϕ (v)) ≥ ν(ϕ (v)).
Proof. Choose in the following x 0 = 0 (the null element of H). By the imposed conditions, (EAOP-ext) is applicable to the data (H, d; ϕ; a; γ). So, for (ε, u) and δ as before, there exists v = v(ε, u, δ) ∈ H[u, γ(u)], with the properties given by its conclusion; i. i.e., (41-b) is verified. This, in particular, tells us that v is an interior point of H[u, γ(u)]; moreover (from the above), we must have

v + th ∈ H[u, γ(u)], ∀t ∈ [-β(u), β(u)], ∀h ∈ ∂H 1 .
In fact, let the couple (t, h) be as before; then

||v + th -u|| ≤ ||v -u|| + |t| < β(u) + β(u) = γ(u);
and the claim follows. On the other hand, ||v -th|| > ||v||, for 0 < t < β(u), whenever h ∈ C 1 (v) (i.e.: h ∈ ∂H 1 and v, h ≤ 0); because (from the properties of scalar product) 2 , for all such (t, h).

||v -th|| 2 = ||v|| 2 + t 2 -2t v, h > ||v||
Putting these together gives (44-c), if one takes (41-f) into account. Finally, let h ∈ C 1 (v) be arbitrary fixed; hence, h ∈ ∂H 1 , v, h ≤ 0. From (41-c), one gets an evaluation like ε/δa(||v||) > (1/t)(ϕ(v) -ϕ(v -th)), when 0 < t < β(u).

So, passing to limit as t → 0+ and taking the Gâteaux differentiable property of ϕ into account, one derives ε/δa(||v||) ≥ ϕ (v), h . This, by the arbitrariness of h in C 1 (v), yields ε/δa(||v||) ≥ ν(ϕ (v)); hence, ε/δa(||v||) ≥ |ν|(ϕ (v)); and establishes the final conclusion (41-d) in the statement.

The differential principle (EAOP-dif) is comparable with a related one in El Amrouss and Tsouli [START_REF] El Amrouss | A generalization of Ekeland's variational principle with applications[END_REF]. However, some basic differences between these results must be noted.

I) As precise, the extra regularity conditions imposed by the quoted authors (d06) a(.) is continuous (in the usual sense) (d07) a(.) is a comparison function, of order k > 0 (∀q ≥ k, ∃λ, µ ≥ 0 : a((t + 1)s) ≤ a(t)[λs q + µ], ∀t, s ≥ 0)

are not needed here.

(II) The final differential relation above is written by the quoted authors as (41-d-var) ε/δa(||v||) ≥ ||ϕ (v)||. Formally, this is better that (41-d) above, in view of

||ϕ (z)|| ≥ |ν|(ϕ (z)), ∀z ∈ H.
Unfortunately, (41-d-var) is not true under authors' directional context; and this is retainable as well for our statement we just exposed.

Note finally that some extensions of these results are possible, in the class of quasi-ordered normed spaces; see Turinici [START_REF] Turinici | Normed coercivity for monotone functionals[END_REF] for details.

Existence of minimizers

In the following, an application of the result above to existence of minimizers for Gâteaux differentiable regular functionals is considered. The basic instrument for our investigations is the well known Palais-Smale condition [START_REF] Palais | A generalized Morse theory[END_REF].

Let H be a (real ) Hilbert space with respect to the scalar product (x, y) → x, y . Further, let ϕ : H → R be a (H, d)-regular function; i.e., (e01) ϕ is bounded below (inf ϕ(X) > -∞) (e02) ϕ is d-lsc on X (lim inf n ϕ(x n ) ≥ ϕ(x), whenever x n d -→ x). Remember that, for each θ ≥ 0 we denoted ulev(ϕ; H; θ) = {x ∈ H; ϕ(x) ≤ inf ϕ(H) + θ}; this will be referred to as the θ-upper level set of ϕ with respect to H; in particular, ulev(ϕ; M ; 0) is nothing else than the (global) minimizers set of ϕ over H. In addition, suppose that (e03) ϕ is Gâteaux differentiable over H. Further, take some function a : R + → R 0 + according to (e04) a(.) is increasing (t 1 ≤ t 2 implies a(t 1 ) ≤ a(t 2 )). Roughly speaking, the differential El Amrouss Ordering Principle (EAOP-dif) we just established is a local one; because, given the starting point u ∈ H, the associated variational point v = v(u) is to be found in a (closed) sphere H[u, γ(u)] around u. But, for an appropriate solving of our problem, a global version of this ordering principle, relative to the class of (closed) bounded parts of H is needed. Call the subset K of H, admissible (modulo ϕ), provided ulev(ϕ; H; ε) ∩ K is nonempty, for each ε > 0; hence, necessarily, K is nonempty. Assume in the following that (e05) (H, ϕ) is admissible: there exist bounded admissible (modulo ϕ) parts of H. Fix in the following such an object, K; as well as some number δ > 0 with (e06) δ < 1/a(3(ρ + 1)); where ρ = sup{||u||; u ∈ K}. A direct consequence of this is the following. Let us introduce the mappings β(u) = ||u|| + 1, γ(u) = 2β(u) = 2||u|| + 2, u ∈ H. By the imposed condition, we have β(u) ≤ ρ + 1, γ(u) ≤ 2ρ + 2, ∀u ∈ K; and this yields (via a(.)=increasing)

Theorem 1 . 1 .

 11 Let ε > 0 be given; as well as some u ∈ ulev(ϕ; M ; ε). Then, for each δ > 0, there existsv = v(ε, u; δ) ∈ M with (11-a) (ε/δ)d(u, v) ≤ ϕ(u) -ϕ(v); hence [ϕ(u) ≥ ϕ(v), d(u, v) ≤ δ] (11-b) (ε/δ)d(v, x) > ϕ(v) -ϕ(x), for all x ∈ M \ {v}.

Proposition 2 . 2 .

 22 Suppose that (b03) ( ) is regular and self-closed (b04) d is ( )-complete (over M ). Then, for each u ∈ M there exists v ∈ M with (22-1) u v (i.e.: v ∈ M (u, )) (22-2) w ∈ M and v w imply v = w.

  The (real) sequence (ϕ(y n )) is descending and bounded from below; hence the series n (ϕ(y n ) -ϕ(y n+1 )) converges (in R + ). This, added to the previous relation, assures us that the series n d(y n , y n+1 ) converges (in R + ); whence, (y n ) is d-Cauchy; as claimed.(C) Finally, we are passing to the verification of self-closeness condition. An appropriate answer is contained in Lemma 3.3. Under the imposed conditions, ( ) is self-closed on X; hence, a fortiori, ( ) is self-closed over each (nonempty) closed bounded part M of X.

  e., (41-e) ||u|| ≤ ||v||, (ε/δ)||u -v||/a(||v||) ≤ ϕ(u) -ϕ(v); hence ||u -v|| ≤ min{γ(u), δa(||v||)} (41-f) w ∈ H[u, γ(u)] \ {v}, ||v|| ≤ ||w|| imply (ε/δ)||v -w||/a(||w||) > ϕ(v) -ϕ(w); hence, (ε/δ)||v -w||/a(||v||) > ϕ(v) -ϕ(w).By the former of these [i.e.: (41-e)], one gets (41-a). As a direct consequence,||v|| ≤ ||v -u|| + ||u|| ≤ γ(u) + ||u|| ≤ 3||u|| + 2 < 3β(u);and this, in combination with (d05), gives (via (41-a) above) ||u -v|| ≤ δa(3β(u)) < β(u) < γ(u);

  y ∈ H); remember that, by the very definition of our structure, (H, ||.||) is a Banach space; hence, (H, d) is a complete metric space. Put also, for simplicity, H 1 = {h ∈ H; ||h|| ≤ 1} (the unitary closed sphere in H) ∂H 1 := {h ∈ H 1 ; ||h|| = 1} (the boundary of H 1 ). Let the function ϕ : H → R be (H, d)-regular; i.e. (see above)

δ < 1/a(3β(u)) (hence, δa(3β(u)) < 1), for each u ∈ K.

The following global differential type variational statement (referred to as: global differential El Amrouss Ordering Principle; in short: (EAOP-dif-g)) is our main step towards the desired answer.

Theorem 5.1. Let ε > 0 be given, as well as some u ∈ ulev(ϕ; H; ε) ∩ K. Further, let δ > 0 be taken as before. There exists then some v ∈ H, such that (51-a)

Proof. Let ε > 0, u ∈ ulev(ϕ; H; ε) ∩ K and δ > 0 be taken as before. From the above relations involving the constant δ > 0 and the couple of functions (a(.), β(.)), it follows that the (local) differential El Amrouss Ordering Principle (EAOP-dif) is applicable to the data (H; ε, u; δ; β(.), γ(.)); and gives us all conclusions in the statement. The proof is thereby complete.

In particular, when a : R + → R 0 + fulfills the extra conditions (ec-1) a(.) is continuous (in the usual sense) (ec-2) a(.) is a comparison function, of order k > 0 (∀q ≥ k, ∃λ, µ ≥ 0 : a((t + 1)s) ≤ a(t)[λs q + µ], ∀t, s ≥ 0) the global differential El Amrouss Ordering Principle (EAOP-dif-g) is nothing but the statement in El-Amrouss [START_REF] Amrouss | Variantes du principle variationnel d'Ekeland et applications[END_REF] proved under different methods. However, we must say that its differential conclusion (51-d) ||ϕ (v)||a(||v||) ≤ ε/δ is not true under author's directional context; we do not give further details.

An application of (EAOP-dif-g) to existence of (global) minimizers for the function ϕ may now be given along the lines below. Let us say that (H, ϕ) satisfies the Palais-Smale condition (modulo a), when (PS-a) each bounded sequence (x n ) ⊆ H such that ϕ(x n ) → ϕ * and |ν|(ϕ (x n ))a(||x n ||) → 0 has a convergent subsequence. In particular, when a = 1, this is referred to as (H, ϕ) fulfilling the standard Palais-Smale condition:

(PS) each bounded sequence (x n ) ⊆ H such that ϕ(x n ) → ϕ * and |ν|(ϕ (x n )) → 0 has a convergent subsequence. Concerning the relationship between these, note that (under the choice of our function a(.)), the following double inequality holds

where σ := sup{||x n ||; n ≥ 0}. This tells us that

(PS-a) is equivalent with (PS). We are now in position to formulate the announced answer. Let the general conditions of this section be admitted. Precisely, take a function ϕ : H → R, endowed with the properties:

ϕ is (H, d)-regular and Gâteaux differentiable (see above).

Moreover, let the function a : R + → R 0 + be increasing. Theorem 5.2. Suppose, in addition, that (H, ϕ) is admissible and fulfills the Palais-Smale condition (PS-a) (or, equivalently, the standard Palais-Smale condition (PS)). Then, ϕ admits at least one minimizer on H.

Proof. As (H, ϕ) is admissible, it admits at least a bounded admissible subset K, in the sense:

(adm-1) K is bounded; hence, ρ := sup{||u||; u ∈ K} < ∞ (adm-2) K is admissible: ulev(ϕ; H; ε) ∩ K = ∅, ∀ε > 0. Further, pick the number δ > 0 in accordance with δ < 1/a(3(ρ + 1)); hence, δa(3(ρ + 1)) < 1. For the arbitrary fixed ε > 0, take some (starting) point u ε ∈ ulev(ϕ; H; ε) ∩ K.

From the global differential El Amrouss Ordering Principle (EAOP-dif-g), there must be some associated point v ε ∈ H fulfilling its conclusions (51-a)-(51-c); i.e. (for any such

In particular, taking the sequence (ε n = 2 -n ; n ≥ 0), it results that, for each n ≥ 0 and each starting u n := u εn ∈ ulev(ϕ; H; ε n ) ∩ K, there exists or, in other words: y ∈ H is a minimizer for ϕ. The proof is thereby complete.

In particular, under the extra regularity conditions (er-1) a(.) is continuous (in the usual sense) (er-2) a(.) is a comparison function of order k > 0 (see above) the obtained existence result yields a related statement in El-Amrouss [START_REF] Amrouss | Variantes du principle variationnel d'Ekeland et applications[END_REF]. Further aspects may be found in Motreanu et al [START_REF] Motreanu | Topological and Variational Methods with Applications to Nonlinear Boundary Value Problems[END_REF]Ch 5].