Hervé Rivano

Fabrice Théoleyre

Fabrice Valois

A Framework for the Capacity Evaluation of Multihop Wireless Networks

Keywords: network capacity, multihop wireless networks, upper and lower bounds, linear programing

The specific challenges of multihop wireles networks lead to a strong research effort on efficient protocols design where the offered capacity is a key objective. More specifically, routing strategy largely impacts the network capacity, i.e. the throughput offered to each flow. In this work, we propose a complete framework to compute the upper and the lower bounds of the network capacity according to a physical topology and a given routing protocol. The radio resource sharing principles of CSMA-CA is modeled as a set of linear constraints with two models of fairness. The first one assumes that nodes have a fair access to the channel, while the second one assumes that on the radio links. We then develop a pessimistic and an optimistic scenarios for radio resource sharing, yielding a lower bound and an upper bound on the network capacity for each fairness case. Our approach is independent of the network topology and the routing protocols, and provides therefore a relevant framework for their comparison. We apply our models to a comparative analysis of a well-known flat routing protocol OLSR against two main self-organized structure approaches, VSR and localized CDS.

I. INTRODUCTION

Ad hoc networks are spontaneous multihop topologies of wireless nodes. These networks are decentralized and should function autonomously, without any human intervention. All the nodes can be mobile, and create continuously topology changes. An ad hoc network connected to the Internet constitutes a so-called hybrid network. A dedicated device, the wireless access point (AP), is a gateway between the wired world and the ad hoc network.

By nature, ad hoc and hybrid networks forward traffic only via wireless links. Moreover, radio bandwidth is much lower than in wired networks, and interferences complicate the radio resource sharing. Nevertheless, multihop wireless networks with a low network capacity could become irrelevant: most applications require a minimum bandwidth to function normally.

This kind of networks can be either considered in a flat manner or self-organized. Self-organization ( [START_REF] Prehofer | Self-organization in communication networks : principles and design paradigm[END_REF]) was intro-A preliminary version of this work has been published in IEEE IWWAN 2006 [START_REF] Rivano | Capacity evaluation framework and validation of self-organized routing schemes[END_REF]. This work was partially supported by the European Commission project AEOLUS under contract IST-15964, project IST WIP under contract IST-27402 the French Ministry of Research project AIRNET under contract ANR-05-RNRT-012-01, project JC-OSERA, and the INRIA project ARC CARMA.

duced to tackle several key problems in multihop wireless networks (e.g. scalability, robustness, overhead) and to simplify the physical topologies. Flat approaches do not introduce any hierarchy: all the nodes must contribute equally to the network, all the radio links should be used to forward the traffic, no organization is introduced in the network. Oppositely, selforganizations construct a logical topology of the physical topology of the network: e.g. some radio links are pruned from the self-organization and some nodes are elected to contribute more intensively in the network management.

Although self-organization seems a promising way to manage multihop wireless networks, the network capacity estimation of these solutions remains an open-problem. Indeed, a self-organization selects by nature some privileged links and nodes, and exploits them more intensively: this unbalanced selection impacts the network capacity. Besides, to select stable links improves the route robustness, but increases the route length which consumes more bandwidth resource. Moreover, a not-well conceived or exploited self-organization may create bottlenecks. We propose here to quantify the impact of selforganization on the network capacity.

Several articles already analyzed the asymptotical capacity of ad hoc networks [START_REF] Gupta | The capacity of wireless networks[END_REF], [START_REF] Hsieh | Performance comparison of cellular and multi-hop wireless networks: a quantitative study[END_REF], [START_REF] Kozat | Throughput capacity of random ad hoc networks with infrastructure support[END_REF], [START_REF] Wang | A unifying perspective on the capacity of wireless ad hoc networks[END_REF], [START_REF] Zemlianov | Capacity of ad hoc wireless networks with infrastructure support[END_REF]. However, we aim here at comparing the network capacity associated to different routing protocols for a given topology. Moreover, asymptotic studies can only give an upper bound, with an optimal MAC layer and with a fixed modeled forwarding strategy. Thus, we describe here a whole model to formulate the network capacity with a linear programming approach, interfaced with a network simulator to use directly the results of a routing protocol.

The contributions of this article are twofold: 1) We describe a complete model to extract the network capacity from any network topology. Since the paths impact the network capacity, the model directly uses the paths obtained from the routing protocol. Moreover, we present a detailed linear programming model for bandwidth sharing among interfering nodes. Our model incorporates fairness: bandwidth is fairly distributed among either interfering nodes or interfering radio links. 2) We use this model in order to compare the network capacity associated to different routing protocols. We compare in particular flat proactive and self-organized approaches. We directly use the paths computed with different routing protocols in a discrete-event simulator. This comparison highlights the key points that must be improved to optimize the network capacity. The article is organized as follows. The next section introduces hypothesis, notations and a generic model. We define formally in section III the concept of network capacity with two different objectives. Then, sections IV and V introduce the resource sharing models, for two different types of fairness (node-oriented, link-oriented), with lower and upper bounds. Section VI is dedicated to generalizing the models to arbitrary interference models and explaining the global methodology we follow for evaluating protocols. Section VII details simulations results and compare flat and self-organized routing protocols from the network capacity viewpoint. Related work on networks capacity evaluation and routing protocol is presented in section VIII. Last section concludes this article and gives research perspectives.

II. NETWORK MODEL

We consider a wireless network modeled as a graph G(V, E) and a given routing protocol. Each vertex (V ) represents a wireless node, and an edge (E) exists between two vertices iif the corresponding nodes have a radio link with each other. We also assume that a radio link is bidirectional. We use the following notations:

• BW is the available radio bandwidth. This gives the maximum amount of data that can be sent by a node if it is alone to transmit.

• p is a multi-hop path between a source node s and a destination d

• f (p) is the throughput of the data sent on the path p • d(u, v) is the euclidian distance between u and v • T (u) is the total amount of traffic sent by a node u:

T (u) = v∈ν(u) T (u, v) + T c (u) with -ν k (u) is the k-neighborhood of u, i.e. the set of the nodes at most k hops far from u. ν 1 (u) is denoted as ν(u) (u ∈ ν(u), ∀ k). -∆ k (u) is the k-degree of u: ∆ k (u) = |ν(u)|. -T (u, v) is the unicast traffic on the physical radio link (u, v). -T c (u)
is the control traffic broadcasted by u to its neighborhood.

A. Interference models

The interferences impact the network capacity and can be modeled [START_REF] Kumar | Algorithmic aspects of capacity in wireless networks[END_REF] with: We will use in this paper the transmitter/receiver model for all our explanations, for a sake of simplicity. However, we will generalize in section VI-A our LP formulation. The reader will be able to verify that our network capacity formulation works with different interference models, and can use directly the conflict graph.

B. Linear programming models

Our linear programing models fit the generic form described as LP 1. The objective function formalizes our definition of the capacity. Radio resource sharing constraints are defined for each node and take into account fairness and interferences. The data flow load constraints added for each path define global constraints on the transport capacity of the network, i.e. a flow is forwarded by each intermediate node of the path.

Note that it is straightforward to write the traffic management constraints of LP 1 from the composition of T (u, v).

C. Assumptions

In order to develop a linear model of the radio resource sharing, we need to fix some classic hypothesis on the MAC layer:

1) Perfect radio channel: we assume that the medium delivers a constant bandwidth and does not corrupt data transmissions. 2) Ideal MAC layer: no collision occurs, the bandwidth can be optimally used, and all the nodes have the same probability to reserve the radio medium 3) Bi-directional unicast communications: if a node u sends a data traffic to one of its neighbor v, v answers with an acknowledgment: any other node interfering with u or v cannot access to the medium 4) Transmitter-receiver interference model: since we assume communications have to be acknowledged, we block nodes interfering with the transmitter or the receiver 5) Control and topology maintenance traffic is sent by u through a local broadcast. Thus, the interference model prevents all nodes interfering with the broadcaster from sending or receiving any kind of traffic III. DEFINING THE NETWORK CAPACITY

We will first introduce two formal definitions of the network capacity: the first one deals with the classical definition of capacity and the second function introduces fairness.

A. Max-Sum function

The capacity is often described as the maximal throughput achievable in the network. Thus the objective function can be defined as:

M ax   p∈P f (p)   (1)
In this approach, the objective is network-wide, i.e. not individual. Consequently, the network will surely privilege the radio links and nodes which create low interferences. In particular, the multihop flows will create many interferences while their bandwidth will contribute less to the objective than single hop flows. Only a few radio links will receive all the bandwidth. According to us, this objective constitutes a misinterpretation of the real capacity of a multihop wireless network for many applications. Nevertheless, this formulation gives an upper bound of the global achievable capacity.

B. Max-Min function

Fairness should be introduced. In such a case, the objective function can be formulated as:

M ax (M in p∈P f (p)) (2)
We consider that each flow should receive the same bandwidth: multihop flows are not handicapped. The global achievable throughput will surely be inferior to the max-sum function case, since more interfering flows must cohabit. Nevertheless, we model here a multihop wireless networks with quality of service. Additionally, the fairness ratio introduced in [START_REF] Kumar | Algorithmic aspects of capacity in wireless networks[END_REF] could limit unfairness among the different flows: max-min could be trivially modified to integrate this fairness ratio.

IV. NODE-ORIENTED FAIRNESS RESOURCE SHARING

A. A pessimistic scenario

To obtain a lower bound of the capacity, we model a pessimistic MAC layer in the following way. We define the interfering set of a node u as all the nodes which interfere with u (including u). A pessimistic MAC layer considers for each node its interfering set and distributes the same amount of radio bandwidth to each node. By referencing all the possible interfering sets in the network (i.e. one per node), we will define the capacity of a multihop wireless networks in a pessimistic scenario and translate it in linear constraints.

The reader can verify that this approach represents a lower bound since two radio links can be non-interfering with each other but can be referenced in the same interfering set. In this case, these links share the radio bandwidth although they can simultaneously transmit a frame without collision. For example, the radio links (A, B)/(D, E) or (K, B)/(H, I) can communicate simultaneously in the figure 1 although all these nodes are in the interfering set of C. Thus, a pessimistic resource sharing is achieved if the transmission of one node is blocking all its 2-neighborhood since we adopt the transmitter-receiver interference model. If the center or one of its 2-neighbors transmits a data packet, no other node in the 2-neighborhood of the center is allowed to send packets. To model a node-oriented fairness, the same bandwidth is allocated to each 2-neighbors of the center. One can notice that stopping any radio activity includes refusing any incoming connexion request, since it requires to send an acknowledgment for the received packet: it would potentially create a collision.

Control traffic is transmitted in the 1-hop neighborhood using a local broadcast: it blocks also all the 2-neighborhood. Let a node c be the center node of its 2-neighborhood. We obtain the following constraints:

• A transmission of c can only interfere with its 2neighborhood. Thus, we assume that the bandwidth can be distributed fairly among all these contending nodes, i.e. the 2-neighborhood of c, N 2 (c):

∀c, ∀u ∈ N 2 (c), T(u) ≤ BW ∆ 2 (c) (3)
Note, that for each center node c, a set of ∆ 2 (c) equations is given. In consequence, the bandwidth T (u) allocated to a node u is constrained by ∆ 2 (u) equations (one for each possible center node).

• In the bandwidth allocated to one node, all the control traffic and the unicast transmissions must be scheduled. Additionally, a node allocates an equal bandwidth to each of its neighbors:

∀u, ∀v ∈ N (u) -{u}, T(u, v) ≤ T (u) -T c (u) ∆(u) -1 (4)
The equation ( 4) models a fair bandwidth sharing by a node for its neighbors, while how the radio medium bandwidth is shared among the nodes is modeled by the equation (3

B. Illustration with the pessimistic scenario on a line

We propose in this section to illustrate the previous model with the line network. This provides to the reader a step by step illustration of our models. Moreover, the line network helps to compare easily the major differences between the maxsum and max-min objectives. To simplify the explanations, the control traffic is considered null and the radio bandwidth (BW) equal to one unit. In the max-min case, x represents the throughput of each node. Let be the topology illustrated in figure 2. The access point is placed in the middle of the line. The line contains 2n nodes, plus the AP. Let study the network capacity with the max-sum objective. This evaluation function will privilege uniquely the single hop flows, as described previously. Thus, it will maximize two flows from the node 1 and 1 to the AP. The reader can remark that the access point will create the most restrictive interference constraints. AP and each of its 2-neighbors receive 1 5 of the medium bandwidth. For the node 1 (respectively 1'), the link (1,AP) (respectively (1',AP)) receives the whole bandwidth since only one of its radio links support traffic. Finally, max-sum = 2 5 . Let now examine the max-min objective: AP keeps on representing the bottleneck in the network. Let x be the traffic sent by each node. Nodes 1 and 1 must receive and forward the traffic of the (n -1)x other nodes, and send its own traffic to the AP. Moreover, 1 and 1 receive the same bandwidth as in the max-sum case but here to forward the traffic of (n -1) nodes. We obtain the constraint 1 5 ≤ (n-1)x+x, which leads to max-min = 1 5n

2' AP 1' 1 2 n n' ... ...

AP is constrained by 4 other nodes

C. An optimistic resource sharing scenario

The pessimistic radio resource sharing model tends to overestimate the interferences. Some communications could be possible in a realistic protocol (like IEEE 802.11), but are forbidden in our model. For example, in fig. 1, the simultaneous transmissions (K → B) and (H → E) should be authorized since C has not to decipher the packets.

In consequence, we propose here an optimistic resource sharing model. For each node u, we isolate its 2-neighborhood: only these nodes can interfere with u. Then, we reference the radio links which can be activated simultaneously in this set: the attributed bandwidth will consequently be larger than in the pessimistic scenario. This approach constitutes an upper bound since we isolate one node and its 2-neighborhood. We examine node per node the resource sharing: the local constraints could lead to unfeasible global constraints. Indeed, a scheduling can be achievable locally but the combination of all the schedulings (one for each node) could be practically impossible: timeslots attributed to different nodes could overlap.

Let observe the behavior of the MAC layer in the twoneighborhood of a node c (the center). One neighbor, u, of the center sends a packet to v. All neighbors of u will stop any activity. When u finished the transmission, v will send a MAC acknowledgment. Thus, no neighbor of u or v is authorized to send a packet, else a collision would occur. Let now assume that another node u wants to send a packet. u cannot be a neighbor of u or of v. Additionally, it must choose a destination v which is not a neighbor of u or v.

We will now translate this behavior in linear constraints. The medium is modeled as a central entity which allocates bandwidth to each radio links, and avoids interfering links to transmit packets simultaneously. Naturally, we consider here only the radio links which must forward traffic, else we would under-estimate the available bandwidth. Thus, the radio medium distributes bandwidth among links which own to at least one path. The selection of valid transmissions is strongly correlated to the combinatorial concept of independent sets. Indeed, this contention-free communication set is an independent set, maximal for inclusion, of the graph L 1,2 (L (G c )), defined as follows:

• G 2 c is the graph of the 2-neighborhood of c. • L(G 2 c ) is the linegraph of G 2 c
: it is the graph where a vertex is associated to each edge of G c , and an edge between any two vertices whose corresponding edges are adjacent.

• L 1,2 (L(G 2 c
)) is the graph with the same vertices as L(G 2 c ), and a link between any two neighboring or 2-neighboring vertices (its 2-closure). Consequently,

L 1,2 (L(G 2 c
)) represents the conflict graph of G 2 c . Independent vertices (i.e. pairwise of non adjacent vertices) of L 1,2 (L (G c )) correspond to contention-free communications. An inclusion-wise maximal independent set is therefore an inclusion-wise maximal set of communications that can be activated simultaneously.

The MAC layer should achieve a fair sharing of the bandwidth among the maximal independent sets. Let BW (I) be the bandwidth given to the independent set I ∈ I, where I is the set of all maximal independent sets of L 1,2 (L (G c )). BW (I) is proportional to P (I), the probability of I to be selected. The radio bandwidth can be split into:

1) The control traffic of the center: control frames are broadcasted, and broadcast frames block all the 2-neighbors of the source 2) The unicast traffic of the 2-neighborhood of the center: several unicast transmissions can be allowed, as explained above 3) The control traffic of the 1-neighbors and 2-neighbors is assumed to be contained in the unicast transmissions allocation. Since we construct an upper bound, we can consider safely that the broadcast transmissions are contained in the whole bandwidth allocated to the node for its unicast transmissions. Consequently, the bandwidth in the neighborhood of c is finally shared as follows:

BW (I) = P (I) • (BW -T c (c)) (5)
⇒ BW ≥ I∈I BW (I) + T c (c) (6)
The total bandwidth allocated to a communication link (u, v) is the sum of the bandwidth allocated to each independent set including (u, v), for which we deduct the control traffic of the source u:

T (u, v) ≤ (u,v)∈I BW (I) T (u, v) ≤ [BW -T c (c)] (u,v)∈I P (I)
Moreover, (u,v)∈I P (I) is exactly the probability for the communication link (u, v) to be activated by the medium. This quantity is hence denoted P (u, v) in the following:

∀(u, v) ∈ N 2 2 (c) ∧ v ∈ N (u), T (u, v) ≤ [BW -T c (c)] • P (u, v) (7)
Unfortunately, on arbitrary network topologies, P (I) and P (u, v) cannot be computed unless the whole set I is known, and I has an exponential size. We therefore build a stochastic estimation of P (u, v), denoted f req(u, v) in the following. These frequencies f req(u, v) must absolutely take into account the fairness among the nodes. We propose in consequence an algorithm to construct an independent set of radio links. Initially, all the nodes can be activated (none is blocked). Let choose randomly one unblocked node u, and one of its unblocked neighbor v. This radio link (u, v) is marked as activated, and all the neighbors of u and v are marked blocked. Then, reiterate until no unblocked node exists. Finally, we obtain a list of simultaneously active radio links, i.e. an independent set in the conflict graph (algo. 1). If this algorithm is repeated n times, f req(u, v) is equal to the proportion of the cases where the link (u, v) was selected. Note that each link is directed: the link (u, v) will not receive the same amount of traffic as (v, u). Finally:

T (u, v) ≤ (BW -T c (c)) f req(u, v) (8)
In order to complete the model, we must take into account the control generated for routing. When the center broadcasts ∀ link (u, v) ∈ E Equation set [START_REF] Li | Broadcast capacity for wireless ad hoc networks[END_REF] ∀ u ∈ V Traffic management for p ∀ path p its control traffic, all the 2-neighbors are blocked (eq. 8).

Besides, a node broadcasts its traffic using the bandwidth allocated for its unicast transmissions: this constitutes an optimistic view of the control traffic distribution. We obtain consequently:

v∈N (u) T (u, v) ≤ f req(u, v) v∈N (u) [BW -T c (c)] -T c (u) (9)
Besides, the bandwidth is allocated per link: a node cannot redistribute locally the bandwidth between its links. If a node chooses to redistribute the bandwidth of an unloaded link to another of its links, the interference constraints could be violated. The last optimistic aspect of this model is that the combinations of the local constraints might not yield a feasible share of the global capacity. As a matter of fact, the union of the local independent sets might not be a global independent set. In other words, the global constraints are stronger than the union of the local ones since we assume that broadcast frames do not interfere more than an unicast frame. The linear program 3 neglects this fact, yielding an upper bound on the global capacity of the network.

D. Application of the optimistic scenario on a line

Let keep on illustrating our models with the line-network scenario (fig. 3). In a first, time, we will observe the network capacity with the max-sum. If AP is the center, we obtain the strongest constraints. The reader can verify that we obtain the following stables and frequencies:

• f req[(2 , 1 )] = f req[(2, 1)] = 1 2 • f req[(1, AP)] = f req[(1 , AP)] = 1 4
To reach the max-sum objective, only the node 1 and 1 will generate traffic, for the same reasons as in the pessimistic case. Finally, max-sum

= 1 4 • 2 = 1 2 2' AP 1' 1 2 n n' ... ... 1st stable
1st stable center If we study the max-min objective, the neighbors of the access point will keep on constituting the bottleneck. Indeed, 1 and 1 generate x traffic and must forward the traffic of (n-1) nodes. The most-constrained set is the 2-neighborhood of the access point. The following holds:

• Through the link (1, AP) and (1 , AP) must be sent the traffic x(n)

• Through the link (i + 1, i) and (i + 1 , i ) must be sent the traffic x(ni) The frequencies computed for the max-sum objective do not change. We have the following constraints:

• The traffic allocated to the radio link (1, AP) must be inferior to the bandwidth multiplied by the frequency of the link (1, AP):

x(n) ≤ 1 4 (10)
• The traffic allocated to (2, 1) must be inferior to the bandwidth multiplied by the frequency of the link (2, 1):

x(n -2) ≤ 1 2 (11)
Finally, max-min = 1 4n

V. LINK-ORIENTED FAIRNESS RESOURCE SHARING

Here are presented lower and upper bounds with a fairness oriented on links. While the first approach distributed fairly the bandwidth among the nodes, we chose here to distribute much bandwidth to nodes with a large number of neighbors. Consequently, we propose here to distribute fairly the bandwidth among the radio links which share a common interfering set. Since the previous models in section IV are very similar, we chose to present only the major differences.

Let remind that L(G) denotes the linegraph of G, i.e. the conflict graph. Let introduce the following notation:

• ν k (e): the k-neighborhood in L(G e ) of one link e in G.

A. A pessimistic scenario

We keep on proposing a pessimistic radio resource sharing. However, instead of distributing the bandwidth to vertices, we construct for each link in the graph the set of its neighborhood in the conflict graph. If one link is active, it is potentially in conflict with each link in this set. Moreover, the same bandwidth is allocated to each link. In consequence, traffic allocated to one link f supports the following constraint:

∀e ∈ E, ∀f ∈ ν 2 (e), T (f ) ≤ BW -(u,x)∈ν2(e) T c (u) δ 2 (e) (12)
Additionally to data packets, a node must send control traffic. Since a broadcast packet blocks all the 2-neighborhood and we have to forbid interferences, the lower bound is achieved in duplicating a broadcast packet and sending it separately to each neighbor:

∀u, ∀v ∈ N (u) -{u}, T (u, v) ≤ T (u, v) -T c (u) (13)
Finally, we obtain the linear program LP 4. We can remark that the lower bounds with link-oriented and node-oriented fairness are not comparable. A different behavior of the MAC layer is modeled. Thus the capacity of the network depends on the protocol chosen to schedule concurrent medium accesses.

B. Application of the pessimistic scenario on a line

Let illustrate also the link-fairness with the line network (fig. 2 p. 4). Let focus on the interfering constraints created by (1, AP). Since this link interferes with 4 other active links, the bandwidth 1 5 is allocated to each of these links.

• max-sum: The node 1 and 1 sends all their traffic to the AP and receive both a bandwidth of 1. Thus, max-sum = 2 5

• max-min: The nodes 1 and 1 must send their own traffic and forward the traffic of the line (n -1 nodes). In consequence, max-min = 1 5n .

C. An optimistic scenario

The upper bound with a link-oriented fairness knows less modifications. To integrate the link fairness, we just have to modify the algorithm which computes f req(u, v) (the bandwidth allocated to each link in an interfering set). The algorithm 1 (cf. page 5) must integrate the fairness when a node is chosen randomly. Consequently, instead of choosing independently one source and one destination (one of its Algorithm 2 Creation of independent sets with link fairness while (∃ at least one unblocked link) //Chooses a random unblocked radio link

F ← ∅ foreach (f ∈ unblockedLinks) W ← F ∪ {f } e ← RANDOM(W ) //Mark activated/blocked links MARKASACTIVATED(e); foreach (f ∈ ν 2 (e)) MARKASBLOCKED(f )
neighbors), we choose randomly one unblocked radio link. We obtain the algorithm 2.

If this algorithm is repeated n times, f req(u, v) is equal to the proportion of the cases where the link (u, v) was selected. Note that each link is here directed. Besides, each link does not receive the same amount of bandwidth: some links have potentially more interfering links and will be chosen less frequently. However, fairness among links is respected.

The remaining description of the upper bound remains unchanged. The linear program LP 3 keeps on holding, with the new values of f req(u, v).

D. Application of the optimistic scenario on a line

Let assume that the number of nodes (n) is sufficiently large. We will focus on the links interfering with the link (1,AP) (fig. 3). We obtain in particular the following stables:

• stables (2 , 1 ), (2, 1) and (2 , 1 ), (3, 2) 1 the frequencies being denoted in this case by f req case2

• stable (1 , AP ) • stable (1, AP ) • stable (2,
Since we obtain symmetric constraints when we focus on the interfering sets of (1,AP) and (1',AP), maxmin = 1 5n .

VI. GENERALIZED FRAMEWORK AND METHODOLOGY

For the sake of readability, the aforesaid resource sharing equations have been described using the "transmitter-receiver" representation of interferences [START_REF] Kumar | Algorithmic aspects of capacity in wireless networks[END_REF]: two links can be activated simultaneously if they are at least 2 hops apart. However, our approach can be generalized to any binary interference model as explained in the following.

Henceforth, these linear models define a framework for evaluating the transport capacity provided by a given routing strategy on a network topology. To complete the framework, we describe the process articulating a discrete event simulation with the linear models as well as the methodology we have followed exploiting the framework.

A. Generalizing to arbitrary interference model

Even though the linear equations introduced in the preceding sections consider a 2 hop distance binary interference model like the "transmitter-receiver" representation, the approach can be generalized to any other binary interference model.

In particular, a binary interference model is given as a conflict graph describing the pairwise incompatibilities among the radio link: two links can be activated simultaneously if and only if they are not adjacent in the conflict graph [START_REF] Molle | An optimization framework for the joint routing and scheduling in wireless mesh networks[END_REF].

That gives a straightforward way to generalize all the models for bandwidth sharing. For instance, we can extend the link fairness equation (eq. 12). The 2-neighborhood of an edge e, ν 2 (e), is replaced by the neighborhood of e in the conflict graph. Equivalently, the number of interfering links, δ 2 (e), is replaced by the degree of e in the conflict graph. The node fairness equations are generalized similarly. Two nodes are claimed as interfering if and only if they are either adjacent in the network or incident to a pair of links that are adjacent in the conflict graph. The computations and equations stay.

B. Network capacity evaluation methodology

The framework we are developing aims at evaluating the capacity provided by a routing protocol. The linear models need to be given the topology of the network, the paths built by the routing protocol, and the control traffic generated by the protocol. In order to generate these data in a realistic manner, we run a discrete event simulation of a mobile network running the protocol. We define the framework by the following process:

1) A topology of x nodes is simulated (in our case,

x ∈ [20.

.60], with a degree of 10. Nodes are randomly located in a squared simulation area).

2) The routing protocol is simulated and gives the overheads and paths (the paths depends on the traffic pattern).

3) The constraints modeling the radio resource sharing are extracted from the radio topology. 4) The flow constraints are obtained from the paths.

5) The capacity is computed from the list of constraints and the objective functions (cf. section III) In our implementation, the simulations are done using OPNET Modeler [START_REF]OPNET Modeler[END_REF] while the linear programs are solved with CPLEX [START_REF]ILOG CPLEX[END_REF]. For the sake of reproducibility of experiments, the built of the linear programs is distributed as a part of the MASCOPT library [START_REF]Mascopt Library[END_REF].

Our objective is to estimate the capacity inherent to different routing protocols. To reach this goal, the behavior of some routing protocols were simulated. We have also implemented two traffic patterns: in an ad-hoc network, all the possible paths are computed (Any-To-Any), in an hybrid network, only paths toward one Access Point are computed (Any-To-One).

To have a representative view of the different routing approaches, we have simulated the three following major routing protocols.

• OLSR is relevant to represent the behavior of flat routing protocols computing (or approximating) shortest paths routing.

• Localized-CDS: all the traffic is sent through a meshed backbone provided by [START_REF] Wu | Distributed dominant pruning in ad hoc wireless networks[END_REF] • VSR & SOMoM: in the ad hoc approach (VSR version), paths use a cluster topology. In the hybrid approach of VSR (denoted as SOMoM version), paths use uniquely the tree backbone topology, for which the AP represents the root [START_REF] Theoleyre | Mobility management in multihops wireless access networks[END_REF], [START_REF] Theoleyre | Virtual structure routing in ad hoc networks[END_REF]. Our framework allows to quantify the network capacity of these different routing schemes with a neutral point of view in the sense it relies only on the structure of the paths and the volume of the control traffic. In the following section, we present the results of our simulations. We assume that the radio bandwidth is normalized to 1. First, we give general remarks on the evolution of the capacity according to network size. Then, we compare the capacities of different routing protocols in an ad-hoc and hybrid network.

VII. RESULTS

A. General evolution of the capacity

First, we evaluate the general evolution of the capacity in multihop wireless networks with the link-oriented fairness, which maximizes the minimum capacity allocated to each flow in a flat network (fig. 4). In a multihop wireless network, a network with n nodes comprises n(n -1) paths. With a flat routing protocol, we can remark that the bandwidth per flow decreases when the number of nodes increases: the number of flows grows, and this creates more contention. Consequently, the bandwidth allocated to each flow will surely decrease, corroborating the results of [START_REF] Gupta | The capacity of wireless networks[END_REF]. Oppositely, the total aggregated capacity (the sum of traffic of individual flows) remains constant. Indeed, many flows will with high probability pass through the center of the network since OLSR uses shortest paths. Consequently, almost all the flows are limited by the same interfering set, which leads to a constant aggregated capacity. The center will represent a bottleneck, and limit the spatial frequency re-utilization. Finally, we can note that the optimistic and the pessimistic resource sharing present a very close capacity.

B. Ad-hoc networks

We start by maximizing the global network throughput using the max-sum objective (fig. 5). This evaluation doesn't ensure fairness among the flows: short paths will be privileged since they create less radio interferences. Thus, the global capacity does not decrease when the network cardinality increases. We can even remark that with the optimistic bandwidth sharing, the global capacity increases. Indeed, the network size increases since the degree is maintained constant. Thus, more flows can be activated simultaneously since they are spatially distributed. Oppositely, the pessimistic resource sharing tends to over-estimate interferences, and limit the spatial re-utilization in small networks. Besides, we can remark that OLSR and VSR present a very close capacity, whatever the objective function is while the capacity of Localized-CDS protocol remains much lower. In conclusion, in an ad hoc network, a self-organization scheme does not impact severely the capacity since OLSR and VSR offer similar throughputs.

Then, we investigate the capacity with a link-oriented fairness but with the max-min objective (fig. 6). We can remark for the same reason as described previously that the capacity decreases when the number of nodes increases. We can also verify that OLSR and VSR offer the same capacity when we ensure fairness among the different flows. The backbone of Localized-CDS routing keeps on constituting a bottleneck and impact severely on the capacity.

We also evaluated the capacity with the node-oriented fairness (fig. 7). While the capacity of OLSR and VSR remain unchanged, Localized-CDS routing suffers from the node-oriented fairness. Indeed, backbone clients and backbone members receive the same amount of bandwidth although backbone nodes must forward more packets. Thus, linkoriented fairness would improve the capacity by privileging nodes that must forward traffic from a lot of neighbors

C. Hybrid networks

Finally, we study the capacity of an hybrid network with the max-min objective and the link-oriented fairness (fig. 8). In an hybrid network, the Access Point constitutes either the destination or the source of each flow. Thus, in a network with n nodes, exactly 2n flows exist. Consequently, the capacity per flow is much higher than in a multihop wireless network (fig. 8). OLSR offers an higher capacity than SOMoM and Localized-CDS protocol: the access point represents the bottleneck of the hybrid network, but the flat routing protocol distributes efficiently the path. The backbone of Localized-CDS protocol presents an higher throughput than SOMoM: the first one seems more efficient in hybrid networks to distribute the load among the backbone nodes.

In hybrid networks, a self-organization protocol seems to offer a degraded capacity compared to a flat routing protocol. Thus, an efficient backbone construction protocol optimizing

VIII. RELATED WORK

The authors of [START_REF] Gupta | The capacity of wireless networks[END_REF] presented a pioneering work to extract the network capacity based on the protocol interference model (see section II-A). They defined the network capacity as the aggregated achievable throughput, as considered in this paper. The authors defined spatial and scheduling constraints and proved that even if nodes choose an optimal radio range, the capacity per node does not exceed O 1 √ n , with n being the number of nodes.

Several articles extended this work to deal with hybrid networks [START_REF] Kozat | Throughput capacity of random ad hoc networks with infrastructure support[END_REF], [START_REF] Liu | On the capacity of hybrid wireless networks[END_REF], [START_REF] Zemlianov | Capacity of ad hoc wireless networks with infrastructure support[END_REF], broadcast [START_REF] Li | Broadcast capacity for wireless ad hoc networks[END_REF] and multicast [START_REF] Wang | A unifying perspective on the capacity of wireless ad hoc networks[END_REF]. [START_REF] Hsieh | Performance comparison of cellular and multi-hop wireless networks: a quantitative study[END_REF] proposes to use simulations to extract the network capacity. Finally, [START_REF] Qiu | Optimizing the placement of integration points in multi-hop wireless networks[END_REF] proposes to optimize greedily the AP placement but interference models are simplistic: the throughput is assumed to be proportional to the path length.

Thus, none of these propositions was conceived to compare the network capacity achieved with different routing protocols.

A. LP formulation of the network capacity

The authors of [START_REF] Jain | Impact of interference on multi-hop wireless network performance[END_REF] used linear programing to model the capacity of ad hoc networks. Interferences, radio topology and resource sharing are translated in linear constraints. However, the complexity resides in the capacity estimation of each edge. The authors constructed the conflict graph with the protocol interference model. They estimated that the maximum throughput is achieved when a scheduling is contained in an independent set of the radio links in the conflicts graph. Since to reference exhaustively all the maximum independent sets (MIS) is NP hard, the authors propose to find a sufficiently large number of MIS. Then, they proposed a scheduling which allocates a slot time t to each MIS (t ∈ [0..1], the radio capacity is equal to one unit) and maximizes the capacity. Consequently, the authors do not try to model fairness in the radio resource sharing, contrary to our approach described above.

[8] proposed a scheduling of radio links so that two links activated simultaneously never interfere with each other. The authors proposed a greedy allocation algorithm after an ordering of radio links by their euclidean distance. However, they tend to under-estimate the capacity: bandwidth is shared equally among one edge and each of its interfering edges, even if some of these links do not interfere with each other and could transmit a packet simultaneously. Our capacity estimation proposes a finer evaluation of the local resource sharing in studying more precisely the interference interactions among the 2-neighborhood of a node.

B. Routing in multihop wireless networks

Routing protocols are very closely related to the capacity of ad hoc networks. With different paths, a network will achieve dissimilar throughputs. Bottlenecks should be avoided, and the load harmoniously distributed to improve frequency spatial reutilization.

To construct paths in a multihop wireless networks, two main strategies exist. In the first one, the network is considered flat [START_REF] Perkins | Ad hoc on-demand distance vector (AODV) routing[END_REF], [START_REF] Clausen | Optimized link state routing protocol (OLSR)[END_REF]. In this paper, we cope with OLSR since we consider it is representative of the flat approach to compute paths in multihop wireless networks. OLSR limits the broadcast storm problem by using Multi-Point Relays to limit the overhead due to topology packets. In the second approach, the network is self-organized before routing takes place. For instance, some approaches [START_REF] Wu | A dominating-set-based routing scheme in ad hoc wireless networks[END_REF], [START_REF] Wu | Distributed dominant pruning in ad hoc wireless networks[END_REF] aim at constructing a backbone (more precisely, a Connected Dominating Set) to optimize the flooding of topology packets. Consequently, packets are routed through the backbone, and a bottleneck could appear. Besides, VSR [START_REF] Theoleyre | Virtual structure routing in ad hoc networks[END_REF] uses the cluster and backbone topology of [START_REF] Theoleyre | Self-organization through a virtual structure for hybrid networks[END_REF] for routing: each node executes a proactive routing inside its cluster while a reactive protocol uses the stable cluster topology to route packets between different clusters.

Since a self-organization is a subset of the radio topology, it should avoid the apparition of bottlenecks. In other words, we have to verify that self-organization does not reduce the network capacity compared to flat approaches. Thus, we provided in this article models and the associated framework to compare the network capacity for any routing protocol.

IX. CONCLUSION AND FUTURE WORK

This paper focuses on generic methods for evaluating the capacity of multihop wireless networks. Our approach consists in modeling radio resource sharing principles of CSMA-CA protocols as a set of linear constraints. We propose two MAC layer fairness models. One assumes a fair bandwidth repartition among the interfering nodes, while the other one distributes fairly the bandwidth among the radio links. For each of these fairness models, we propose a pessimistic and an optimistic scenario of the spatial-reutilization of the radio resources. This framework is generic, not related to a particular topology or routing algorithm: we can compare quantitatively different routing strategies. We conclude that self-organization protocols can have a negligible impact on the network capacity with a traffic pattern any-to-any. However, efforts have to be done for self-organizations based routing in a many-to-one traffic pattern.

In the close future, we plan to pursue our comparison campaign by including the other main flat routing protocols (AODV, DSR, DSDV), even though we conjecture that their performances should theoretically be similar to those of OLSR. We are also interested in evaluating multi-path routing protocols [START_REF] Bredin | Deploying sensor networks with guaranteed capacity and fault tolerance[END_REF], since they have been proposed for improving the throughput of the network. In this article, we obtained the network capacity of a given routing algorithm and its associated topology. We want now adopt the inverse approach: how to conceive a routing algorithm which optimizes the network capacity?

Fig. 1 .

 1 Fig. 1. The 2-Neighborhood of one node

Fig. 2 .

 2 Fig. 2. Capacity of the line (pessimistic model)

Fig. 3 .

 3 Fig. 3. Capacity of the line (optimistic model)

  1), (2 , 1 ) • stables (3, 2), (1, AP ) and (3, 2), (2 , 1 ) Let denote f req case1 the interfering constraints created by (1,AP). The reader can verify in particular that f req case1 [(1, ap)] = 2 5 and f req case1 [(1 , ap)] = 1 5 . If we take a look on the interfering constraints created by the link (1',AP) 1 , they are symmetric: f req case1 (a, b) = f req case2 (a , b ). Finally, we obtain maxsum = 2 5 . Besides, f req case1 [(2 , 1 )] = 3 10 , f req case1 [(2 , 1 )] = 1 2 . The links (2, 1) and (2 , 1 ) must transmit x(n -1) traffic and the link (1, AP ) xn traffic. Thus we obtain the following constraints when we focus on the interfering constraints on (1,AP): the link (1 , AP ) xn ≤ 3 10 f or the link (1, AP )

Fig. 4 .

 4 Fig. 4. Comparison of the objective functions in an ad-hoc network using flat routing (link-oriented fairness)

Fig. 5 .Fig. 6 .

 56 Fig. 5. Capacity of an ad-hoc network with the max-sum objective (linkoriented fairness)

Fig. 7 .Fig. 8 .

 78 Fig. 7. Capacity of an ad-hoc network with the max-min objective (nodeoriented fairness)

  corresponds to the signal strength of u measured by v, and the noise corresponds to the ambient noise and the interference signals of all other transmitters. This model is the only one that does not assume any fixed radio range.

	Linear Program 1 Generic Model
	Maximize	Objective function on P Subject to
	Resource sharing constraints around u	∀ node u
	Traffic management for p	∀ path p

• Transmitter model: a node u can communicate with a node v if no node w exists closer than (1 + ∆) • (range(u) + range(w)) from u • Protocol model: the transmission (u, v) is successful if no other node w closer than (1 + ∆)d(u, v) of v is also transmitting a packet • Transmitter/receiver model: two radio links can be activated simultaneously if they are more than 2 hops far • SNR: a communication (u, v) is successful if the signal to noise ratio is larger than a threshold. The signal

  Algorithm 1 Creation of independent sets with node fairness while (∃ at least one unblocked node)

	do
	//Chooses a random node
	u ← RANDOM(unblockedNodes)
	//Chooses a random neighbor
	W ← ∅ foreach (w ∈ unblockedN odes and w ∈ N (u)) W ← W ∪ {w} v ← RANDOM(W )
	//Block neighboring transmissions
	if (W = ∅) MARKASBLOCKED(u);
	else
	MARKASACTIVATED(u , v);
	foreach (w ∈ N (u)) MARKASBLOCKED(w)
	endif
	done
	Linear Program 3 Optimistic model
	Maximize	Objective function on P Subject to
	Equation set (8)


Frédéric Mazenc
email: frederic.mazenc@l2s.centralesupelec.fr

Michael Malisoff
email: malisoff@lsu.edu

New Versions of Halanay's Inequality with Multiple Gain Terms

Keywords: Stability, delays, time-varying. Supported

Halanay's inequality in its standard form is a widely used tool for the analysis of systems with delays and uncertainties, but the assumptions needed to use it are sometimes too restrictive to cover applications of interest. This paper provides new generalizations of Halanay's inequality where, instead of the usual supremum in the gain term in standard versions of Halanay's inequality, we use a weighted sum of suprema over different intervals. This allows us to derive sufficient conditions for asymptotic and input-to-state stability. We apply our results to linear systems with switched delays and other examples that illustrate how our results are less restrictive than those of other contributions available in the literature.

I. INTRODUCTION

Delayed systems play an essential role in control theory and control applications, owing to time delayed information transmission (leading to sensor delays) and time delays in control actuation (which can be represented by input delays). Lyapunov-Krasovskii techniques are well suited for systems with known constant delays, but usually are not as easily applied to systems with time-varying or unknown delays. By contrast, Halanay's inequality technique (which was initiated in [START_REF] Halanay | Differential Equations: Stability, Oscillations, Time Lags[END_REF]) is a useful stability analysis tool for the stability analysis of systems with poorly known time-varying delays. This inequality and variants of it, which complement Razumikhin's theorem (which was used in contributions such as [START_REF] Hale | Introduction to Functional Differential Equations[END_REF] and [START_REF] Zhou | Time-varying Razumikhin and Krasovskii stability theorems for time-varying delay systems[END_REF]), have been studied in several papers, such as [START_REF] Grifa | On stability analysis of discrete-time systems with constrained time-delays via nonlinear Halanay-type inequality[END_REF], [START_REF] Hien | New generalized Halanay inequalities with applications to stability of nonlinear non-autonomous time-delay systems[END_REF], [START_REF] Mazenc | Stability analysis using generalized sup-delay inequalities[END_REF], [START_REF] Mazenc | Stability analysis using new variant of Halanays inequality[END_REF], [START_REF] Mazenc | Vector extensions of Halanay's inequality[END_REF], [START_REF] Pepe | A nonlinear version of Halanay's inequality for the uniform convergence to the origin[END_REF], and [START_REF] Wen | A new generalization of Halanaytype inequality and its applications[END_REF], to extend the domain of application of Halanay's stability analysis strategy.

In particular, the paper [START_REF] Ruan | Novel stability results for Halanay inequality and applications to delay neural networks[END_REF] presents notable results for time-varying Halanay inequalities of the type

v(t) ≤ -a(t)v(t) + b(t) sup ∈[t-T,t] v( ) (1)
where T ≥ 0 is a constant, v is nonnegative valued, and the term containing b is called the gain term. In [START_REF] Ruan | Novel stability results for Halanay inequality and applications to delay neural networks[END_REF], sufficient conditions for lim t→+∞ v(t) = 0 to hold are given for cases where [START_REF] Fridman | Introduction to Time-Delay Systems[END_REF] holds and where a(t) can take both positive and negative values and where b(t) is larger than a(t) on some arbitrarily large time intervals. This contrasts with the standard Halanay's inequality (e.g., [1, Lemma 4.2, p. 138]) having the form [START_REF] Fridman | Introduction to Time-Delay Systems[END_REF] where a > 0 and b ∈ [0, a) are constants. Motivated by the fact that inequalities of the type (1) can be used to study time-varying systems with time-varying delays, we revisit the main result of [START_REF] Ruan | Novel stability results for Halanay inequality and applications to delay neural networks[END_REF]. To obtain less restrictive conditions and establish input-to-state stability (or ISS) like inequalities, we consider generalized Halanay's inequalities with multiple gain terms of the type

v(t) ≤ -a(t)v(t) + k i=1 b i (t) sup ∈[t-T2,i,t-T1,i] v( ) + δ(t) (2)
where a, the b i 's, and δ (which can represent an uncertainty) are nonnegative scalar valued piecewise continuous functions; see [START_REF] Sontag | The ISS philosophy as a unifying framework for stabilitylike behavior[END_REF] for a presentation of the ISS notion. The b i 's are the coefficients in our multiple gain terms that are summed in [START_REF] Grifa | On stability analysis of discrete-time systems with constrained time-delays via nonlinear Halanay-type inequality[END_REF]. Later in Section II, we will describe persistence of excitation relations involving a and the b i 's that will ensure ISS conditions. The key idea which guides us consists of taking advantage of the knowledge of the constants T 1,i and T 2,i ≥ T 1,i , which can be derived from information on the delays of a system with poorly known time-varying delays. As in [START_REF] Ruan | Novel stability results for Halanay inequality and applications to delay neural networks[END_REF], our assumptions are satisfied by functions a which take both positive and negative values (which contrasts with our earlier results on generalized Halanay's inequalities from [START_REF] Mazenc | Stability analysis using generalized sup-delay inequalities[END_REF]- [START_REF] Mazenc | Vector extensions of Halanay's inequality[END_REF], which required a to be nonnegative valued) and the largest value of b i can be arbitrarily large over arbitrarily large intervals, provided that the values a(t) of the function a are positive and large on sufficiently long time intervals. Also, our Halanay inequality generalizations [START_REF] Mazenc | Stability analysis using generalized sup-delay inequalities[END_REF]- [START_REF] Mazenc | Vector extensions of Halanay's inequality[END_REF] did not use the comparison function approach that we use here, and they use only one gain term, instead of the multiple gain terms that we use here. By contrast with the main result of [START_REF] Ruan | Novel stability results for Halanay inequality and applications to delay neural networks[END_REF], we establish ISS like inequalities. By the definition of ISS, this ensures that lim t+∞ v(t) = 0 when δ is the zero function. Our examples in Section III below show that the results we obtain are less restrictive than the latest existing results about Halanay's inequality, in several circumstances. For instance, see Section III for an example where our use of multiple gain terms is shown to be useful for obtaining less conservative results than [START_REF] Mazenc | Stability analysis using generalized sup-delay inequalities[END_REF]- [START_REF] Mazenc | Stability and observer designs using new variants of Halanay's inequality[END_REF]. By contrast with [START_REF] Mazenc | Extension of Razumikhin's theorem and Lyapunov-Krasovskii functional constructions for time-varying systems with delay[END_REF], the technique we propose does not use the strictification technique from [START_REF] Malisoff | Constructions of Strict Lyapunov Functions[END_REF].

We use standard notation, which is simplified when no confusion would arise. The dimensions of our Euclidean spaces are arbitrary unless otherwise noted. The standard Euclidean norm and induced matrix norm are denoted by |•|, |•| ∞ is the corresponding sup norm, and |•| S is the supremum over a set S. We set Z ≥0 = {0, 1, . . .}, N = Z ≥0 \{0}, R is the set of all real numbers, [0,+∞) is the set of all nonnegative real numbers, and I is the identity matrix.

II. GENERALIZED HALANAY'S INEQUALITIES

This section provides our main theorems, which we apply to systems with switched delays and other cases in Section III. Our first theorem covers cases of the form (2) with multiple suprema, and is based on a novel comparison approach. Our second theorem only allows one supremum term (i.e., k = 1 in (2)), but it provides very different sufficient conditions as compared with our first theorem.

A. Halanay's result with several sup terms

Consider any k ∈ N and constants T 1,i and T 2,i such that To analyze the behavior of the function v, we fix constants > 0 and t 0 ≥ 0, we define the functions S i by

0 ≤ T 1,i ≤ T 2,i for all i ∈ {1, ..., k} and T 2,1 ≤ .... ≤ T 2,k-1 ≤ T 2,k . (3)
S i (t) = max 0, sup ∈[t-T2,i,t-T1,i] t-T1,i a(m)dm (4)
for i = 1, . . . , k, and we introduce the comparison system

                 ẏ (t) = -a(t)y (t) + δ(t) + k i=1 [b i (t) + ]e Si(t) y (t -T 1,i ) for all t ≥ t 0 y (t) = sup ∈[t0-T 2,k ,t0] v( ) + for all t ∈ [t 0 -T 2,k , t 0 ]. (5)
We prove the following result, whose conclusion ensures that v satisfies an ISS estimate for all t ≥ t 0 when y satisfies such an ISS estimate, and where we will provide sufficient conditions for y to satisfy the required ISS estimates in our ISS corollary below, which also provides explicit ISS estimates for the function v with ( , δ) viewed as the perturbation and which gives an ISS result with respect to δ as → 0:

Theorem 1: Consider the functions v and y defined above. Then the inequality

v(t) ≤ y (t) (6)
holds for all t ≥ t 0 -T 2,k .

Proof: The second equality in ( 5) and the positiveness of imply that v(t) < y (t) for all t ∈ [t 0 -T 2,k , t 0 ]. Next, we proceed by contradiction. Bearing in mind that v and y are continuous, let us suppose that there were a t > t 0 such that v(t ) = y (t ) and v(t) < y (t) for all t ∈ [t 0 -T 2,k , t ), i.e., t is the first time t when v(t) = y (t). Then from (2) and ( 5), it follows that the inequality

v(t ) -ẏ (t ) ≤ k i=1 b i (t ) sup ∈[t -T2,i,t -T1,i] v( ) - k i=1 [b i (t )+ ]e Si(t ) y (t -T 1,i ) (7)
is satisfied. By the second equality in the comparison system [START_REF] Hien | New generalized Halanay inequalities with applications to stability of nonlinear non-autonomous time-delay systems[END_REF] A( )d y (t 0 ) > 0 for all t ≥ t 0 . In the second case, we can apply variation of parameters to the same inequality in a similar way to get y (t) > 0 for all t ∈ [t 0 , t 0 + min i∈N T 1,i ]. Repeating this process in a method of steps in the case where N = ∅ gives y (t) > 0 for all t ∈ [t 0 + min i∈N T 1,i , t 0 + ( + 1) min i∈N T 1,i ] for all ∈ Z 0 . By combining both cases, it now follows that y (t) > 0 for all t ≥ t 0 -T 2,k . Hence, for all i ∈ {1, ..., k}, we have e S i (t ) y (t -T 1,i ) > 0, so

v(t ) -ẏ (t ) < k i=1 b i (t ) sup ∈[t -T2,i,t -T1,i] v( ) -e Si(t ) y (t -T 1,i ) . ( 8
)
Since v is continuous, it follows that for each i ∈ {1, ..., k}, there is an

s i ∈ [t -T 2,i , t -T 1,i ] such that v(s i ) = sup ∈[t -T2,i,t -T1,i] v( ). Then (8) implies that v(t )-ẏ (t ) < k i=1 b i (t ) v(s i )-e Si(t ) y (t -T 1,i ) . (9)
Next consider any i ∈ {1, ..., k}, and three cases. Case 1: s i > t 0 . Recalling the nonnegative valuedness of y and δ, it follows from (5) that we have ẏ (t) ≥ -a(t)y (t) [START_REF] Mazenc | Stability and observer designs using new variants of Halanay's inequality[END_REF] for all t ≥ t 0 . By integrating [START_REF] Mazenc | Stability and observer designs using new variants of Halanay's inequality[END_REF], we obtain

y (t -T 1,i ) ≥ e - t -T 1,i s i a(m)dm y (s i ). (11)
Since s i ∈ (t 0 , t ], we deduce from the definition of t that v(s i ) ≤ y (s i ), which we can combine with [START_REF] Mazenc | Vector extensions of Halanay's inequality[END_REF] to obtain

y (t -T 1,i ) ≥ e - t -T 1,i s i a(m)dm v(s i ). (12)
It follows that [START_REF] Mazenc | Stability and observer designs using new variants of Halanay's inequality[END_REF] gives

y (t -T 1,i ) ≥ e -Si(t ) v(s i ). Case 2: s i ≤ t 0 ≤ t -T 1,i . Integrating
y (t -T 1,i ) ≥ e - t -T 1,i t 0 a(m)dm y (t 0 ) = e - t -T 1,i t 0 a(m)dm sup ∈[t0-T 2,k ,t0] v( ) + . ( 13
) Since t 0 -T 2,i ≤ t -T 2,i ≤ s i ≤ t 0 , it follows that v(s i ) ≤ sup ∈[t0-T 2,k ,t0] v( ).
Also, [START_REF] Ruan | Novel stability results for Halanay inequality and applications to delay neural networks[END_REF] gives

y (t -T 1,i ) ≥ e - t -T 1,i t 0 a(m)dm v(s i ). ( 14
)
Since t -T 2,k ≤ s i * ≤ t 0 , we can use [START_REF] Sontag | The ISS philosophy as a unifying framework for stabilitylike behavior[END_REF] to conclude that

y (t -T 1,i ) ≥ e -Si(t ) v(s i ) (15)
is satisfied. Case 3: s i ≤ t -T 1,i ≤ t 0 . Recalling that our formula (4) for S i ensures that S i is nonnegative valued, we get

v(s i * ) -e Si(t ) y (t -T 1,i ) ≤ v(s i * ) -y (t -T 1,i ) = v(s i * ) -sup ∈[t0-T 2,k ,t0] v( ) -≤ -. (16)
Hence, in all three cases, we have e Si(t ) y (t -T 1,i ) ≥ v(s i ) for i = 1, . . . , k. By combining the preceding inequalities with [START_REF] Mazenc | Stability analysis using new variant of Halanays inequality[END_REF], it follows that v(t ) -ẏ (t ) < 0, so there is t ∈ [t 0 -T 2,k , t ) such that v(t ) -y (t ) > 0, because v(t ) -y (t ) = 0. This contradicts the definition of t . This concludes the proof.

Remark 1: Theorem 1 implies that if there is a constant > 0 such that y satisfies an ISS inequality, then v satisfies an ISS inequality too that is valid for all t ≥ t 0 . Hence, Theorem 1 provides a way to conclude ISS properties from its generalized Halanay's inequalitites; see Corollary 1.

Remark 2: Theorem 1 has the following two crucial advantages. First, when several poorly known delays are present in a studied system, it improves on the stability conditions for the results available in the literature by taking advantage of the information on the delays; see our illustrations below. Second, when the constants T 2,i converge to T 1,i , then the stability conditions we obtain converge to those of the case where T 2,i = T 1,i for all i ∈ {1, ..., k}. This is in sharp contrast with the conditions of [13, Theorem 1].

Remark 3: The preceding theorem is new, even in the special case where the T 1,i 's are all zero and when a and the b i 's all have the same period P > 0 and δ = 0. In that special case, y will exponentially converge to zero provided This follows by first noting that, in this case, g also has period P . Hence, for any N ∈ N such that N P ≥ t 0 , condition (17) gives y ((N + j)P ) ≤ e -jI * y (N P ) for all integers j ≥ 0, where I * is the integral in (17); this follows by applying variation of parameters to the first equation in (5) on the interval [N P, (N + j)P ]. For t ≥ N P , this gives

y (t) = e -t t f P g( )d y (t f P ) ≤ B * e -I * (t f -N ) y (N P ) → 0 as t → +∞, (18)
where t f = Floor(t/P ) and

B * = sup e -t s g( )d : s ≥ 0, 0 ≤ t -s ≤ P , ( 19
)
and Floor is the floor function, i.e., Floor(s) is the largest integer j such that j ≤ s. Similar reasoning shows that (17) implies that v satisfies an ISS estimate with disturbance (δ, ). We illustrate the use of the criteria (17) in Section III.

B. ISS corollary

We next present a consequence of Theorem 1, which provides an ISS estimate with respect to (δ, ) that converges to an ISS estimate with respect to δ as → 0 + . The linear ISS Lyapunov-Krasovskii functional (25) in its proof motivated us to propose its persistence of excitation condition (20) (but see Remark 3 for alternative sufficient persistence of excitation conditions that ensure the required stability property for (5) under periodicity assumptions).

Corollary 1: Let the assumptions of Theorem 1 hold and t 0 ≥ 0 be given. Assume that a and the b i 's are bounded, and that there is a constant c > 0 such that

a(t) - k i=1 [b i (t + T 1,i ) + ]e Si(t+T1,i) ≥ c (20)
holds for all t ≥ t 0 . Then we can find constants

ζ i > 0 for i = 1, 2 such that v(t) ≤ ζ 1 e -ζ2t |v| [t0-T 2,k ,t0] + ζ 2 (δ(t) + e -ζ2t
) for all t ≥ t 0 .

Proof:

Consider the functional V 1, (t, y ,t ) = y (t) + k i=1 t t-T1,i [b i ( + T 1,i ) + ]e Si( +T1,i) y ( )d . ( 21
)
Its time derivative along all solutions of (5) satisfies

V1, (t) = -a(t) + k i=1 [b i (t+T 1,i )+ ]e Si(t+T1,i) y (t) + δ(t) (22)
for all t ≥ t 0 . Then, along solutions of ( 5),

V1, (t) ≤ -cy (t) + δ(t) (23)
for all t ≥ t 0 . Then let

V 2, (t, y ,t ) = V 1, (t, y ,t ) + c 2µ t t-µ t m y (s)ds (24)
with µ = max i∈{1,...,k} {T 1,i }. Then, along solutions of ( 5

v(t) ≤ y (t) ≤ V 2, (t, y ,t ) ≤ e -ςt (1 + cµ)|y | [t0-T 2,k ,t0] + δ(t) ς = e -ςt (1 + cµ)|v| [t0-T 2,k ,t0] + δ(t) ς + e -ςt (1 + cµ) (28)
for all t ≥ t 0 , proving the corollary.

C. Halanay's result with only one sup term

Let T ≥ 0. Consider the inequality

v(t) ≤ -a(t)v(t) + b(t) sup ∈[t-T,t] v( ) + δ(t) (29)
where a : R → R, b : [0, +∞) → [0, +∞), and δ : [0, +∞) → [0, +∞) are locally bounded and piecewise continuous, and where v : [-T, +∞) → [0, +∞) is of class C 1 . We use any constants > 0 and t 0 ≥ 0, the function

Γ(t) = max 0, sup ∈[t-T,t] t [a(r) -b(r)]dr , (30)
and the comparison system

       ẏ (t) = -a(t) + (b(t) + )e Γ(t) y (t) + δ(t) for all t ≥ t 0 y (t) = sup ∈[t0-T,t0] v( )+ for all t ∈ [t 0 -T, t 0 ]. (31)
The system (31) differs from system (5), because (a) there is only one (instead of k) overshoot terms in the y dynamics in (31), (b) the exponential term (4) in ( 5) having the integrand a has been replaced by a new exponential term (30) with the integrand a -b, and (c) the delays T 1,i in ( 5) are not used in (30)-(31). See Section III-C for an example where (30)-(31) lead to less conservative conditions than Theorem 1. We prove the following, which provides ISS properties for v when y satisfies ISS, and where the required stability properties for y can be checked using classical methods like in the preceding subsection, which can lead to explicit ISS like estimates for v as in Corollary 1:

Theorem 2: Consider the v and y defined above. Then

v(t) ≤ y (t) (32)
holds for all t ≥ t 0 -T . Proof: First note that the second equality in (31) implies that v(t) < y (t) for all t ∈ [t 0 -T, t 0 ]. Now, we proceed by contradiction. Bearing in mind that v and y are continuous, suppose that there is a t > t 0 such that v(t ) = y (t ) and

v(t) < y (t) (33)
for all t ∈ [t 0 -T, t ) by choosing t to be the first time t ≥ t 0 when the inequality (33) is violated as before. Then

v(t ) -ẏ (t ) ≤ b(t ) sup ∈[t -T,t ] v( ) -(b(t ) + )e Γ(t ) y (t ). (34)
Since e Γ(t ) y (t ) > 0, we have [a(r)-b(r)]dr y (t 0 )

v(t )-ẏ (t ) < b(t ) sup ∈[t -T,t ] v( )-e Γ(t
≥ e - t t 0 [a(r)-b(r)]dr sup ∈[t0-T,t0] v( ), (40)
by (31). Since s ∈ [t -T, t 0 ] and t ≥ t 0 , we deduce that

y (t ) ≥ e - t t 0 [a(r)-b(r)]dr v(s ) ≥ e - sup ∈[t -T,t ] t [a(r) -b(r)]dr v(s ) ≥ e -Γ(t ) v(s ). (41)
In both cases, we get e Γ(t ) y (t ) ≥ v(s ), which we can combine with (36) to obtain v(t ) -ẏ (t ) < 0. Hence, there is a t ∈ [t 0 , t ) such that v(t ) -y (t ) > 0, because v(t ) -y (t ) = 0. This contradicts the definition of t , so no such t can exist. This concludes the proof.

III. ILLUSTRATIONS A. Systems with switching delays

Systems with switching delays commonly arise when controls need to switch between different sensors or different actuators that have different latencies, and so are of considerable research interest in the control theory community. Therefore, we first illustrate Theorem 1 using the class of systems with switching delays from [START_REF] Mazenc | Stability analysis using generalized sup-delay inequalities[END_REF] and [START_REF] Mazenc | Stability and observer designs using new variants of Halanay's inequality[END_REF], using our less restrictive new generalized Halanay's conditions [START_REF] Grifa | On stability analysis of discrete-time systems with constrained time-delays via nonlinear Halanay-type inequality[END_REF].

Let T > 0 and T ≥ T be any constants, and consider any sequence t i satisfying T ≤ t i+1 -t i ≤ T for all i ≥ 0. As in [8, Section III.B], let τ l and τ s be any constants such that

T > 5(τ l + τ s ) (42)
and τ l > τ s ≥ 0, and we consider the system

ẋ(t) = M x(t) + N x(t -τ (t)) (43)
with x valued in R n , where τ is a time-varying piecewise continuous unknown delay such that

0 ≤ τ (t) ≤ τ s if t / ∈ E, and 0 ≤ τ (t) ≤ τ l if t ∈ E, where E = ∪ i∈N [t i , t i + T ) and T = τ s + τ l , (44)
and M ∈ R n×n and N ∈ R n×n are constant (which includes cases where τ does not switch, e.g., with T = t i+1 -t i for all i). Following [8, Section III.B] and [10, Section 4.2], we also assume the following, where M 1 ≥ M 2 for square matrices means that M 1 -M 2 is nonnegative definite: Assumption 1: There are a symmetric positive definite matrix Q ∈ R n×n and a constant q > 0 such that

Q(M + N ) + (M + N ) Q ≤ -qQ (45)
and I ≤ Q are satisfied.

In terms of the notation

L = 2|N QN |(|M |+|N |) 2 q , (46)
we also use the following lemma, whose proof consists of the first part of the proof of [10, Proposition 1]: Lemma 1: With the preceding notation and under Assumption 1, the time derivative of the function U (x) = x Qx along all solutions of (43) is such that

U (t) ≤ -q 2 U (x(t)) + Lτ 2 s sup m∈[t-τ l -τs,t] U (x(m)) (47)
for all t ∈ [0, +∞) \ E and

U (t) ≤ -q 2 U (x(t)) + 8|N QN | q sup l∈[t-τ l ,t] U (x(l)) (48)
for all t ∈ E.

In terms of the constant a * and the function b * in a * = e -q(τs+τ l )/2 and b * ( ) = 2(1-a * ) q e 2(R-q/2)(τ l +τs) (49)

where R = 8|N QN |/q, the main result in [START_REF] Mazenc | Stability analysis using generalized sup-delay inequalities[END_REF] for (43) is: Proposition 1: With the above notation, let Assumption 1 hold, and assume that

Lτ 2 s ≤ q 2 < 8|N QN | q and a * + b * (Lτ 2 s ) a * + b * 8|N QN | q < 1. (50)
Then the origin of ( 43) is a globally exponentially stable equilibrium point on R n . On the other hand, we can apply Theorem 1 from Section II-A above in the preceding case, by choosing v(t) = U (x(t)), a(t) = q 2 , k = 2, b 1 (t) = 8 q |N QN |χ Sa (t), b 2 (t) = Lτ 2 s χ S b (t), T 1,1 = T 1,2 = 0, T 2,1 = τ l , and T 2,2 = τ l + τ s (51) under suitable conditions on the parameters, where χ S is the indicator (or characteristic) function for each set S ⊆ R, meaning χ S ( ) = 1 if ∈ S and χ S ( ) = 0 if ∈ R \ S, and where S a = E and S b = R \ E. For example, if we choose τ s = 0, τ l = 0.01, t i = i for all i ≥ 0, the matrices

M = 1 2 -2 -1
, Q = 2.68767 0.789041 0.789041 1.70137 ,

and N = -2I, and q = 1.5, then the assumptions of Proposition 1 would not hold, but the assumptions of Theorem 1 would hold with = 0.001, where Q and q can be found by solving the Lyapunov equation Q a (M + N ) + (M + N ) Q a = -I for Q a , and then scaling Q a to obtain a Q that satisfies the requirements of Assumption 1 for a small enough constant q > 0. The fact that the requirements from Theorem 1 hold for any t 0 ≥ 0 in this case follows from Remark 3 above with P = 1.

In Fig. 1, we plot the solutions of (43) with the preceding values and τ (t) = 0.01 for all t ∈ E for three sets of constant initial functions (i.e., initial states), using Mathematica. They show convergence to the desired equilibrium. This illustrates how Theorem 1 can provide less restrictive conditions than the conditions in [START_REF] Mazenc | Stability analysis using generalized sup-delay inequalities[END_REF] for systems with switched delays.

P

  0 g( )d > 0, where g( ) = a( )-k i=1 [b i ( )+ ]e Si( ) . (17)

Fig. 1 .

 1 Fig. 1. Simulations of (43) Showing x 1 (t) (Red) and x 2 (t) (Blue) for Initial States (1, 1) (Solid), (-2, 2) (Dotted) and (3, -3) (Dashed-Dotted)

  Hence, since δ and the b i 's are nonnegative valued, we can collect terms on the right side of the first equality in[START_REF] Hien | New generalized Halanay inequalities with applications to stability of nonlinear non-autonomous time-delay systems[END_REF] to find a continuous function A such that ẏ (t) ≥ A(t)y (t) for all t ≥ t 0 if each T 1,i is zero, or such that ẏ (t) ≥ A(t)y (t) on [t 0 , t 0 + min i∈N T 1,i ] where N ⊆ {1, . . . , k} is the index set of all i values such that T 1,i > 0 if not all of the T 1,i 's are 0. In the first case, we can apply the method of variation of parameters to the inequality ẏ (t) ≥ A(t)y (t) on any interval of the form [t 0 , T

	t t 0

and the positiveness of and the nonnegativity of the v values, we have y (t) > 0 for all t ∈ [t 0 -T 2,k , t 0 ]. * ) to get y (t) ≥ e

  Then we can apply the method of variation of parameters to (26) and recall the structure of V 2, to obtain the required ISS estimate for y . In fact, Theorem 1 gives

), V2, (t, y ,t ) ≤ -c 2 y (t) -c 2µ t t-µ y (s)ds + δ(t) (25) for all t ≥ t 0 . Since the functions a and b i are bounded, there is a constant ς > 0 such that V2, (t, y ,t ) ≤ -ςV 2, (t, y ,t ) + δ(t) (26) for all t ≥ t 0 . For instance, since V 2, (t, y ,t ) ≤ y (t) + c t t-µ y (s)ds (27) holds for all t ≥ t 0 with the choices c = k(|b| ∞ + )e |S|∞ + c 2 and b = (b 1 , . . . , b k ), we can choose ς = c 2 min{1/µ, 1}/ max{c, 1}.

by NSF Grants 1711299 and 2009659 (Malisoff).

F.

B. Example with comparison with

 [START_REF] Ruan | Novel stability results for Halanay inequality and applications to delay neural networks[END_REF]Consider the special case

sup

of ( 2) with k = 2 and δ = 0, and with the choices

100 sin 2 t -49π 100 , T 2,2 = 2π, and b 2 (t) = 4e -π 100 sin 2 t-199π 100 , and

Then the sufficient condition (20) for lim t→+∞ v(t) = 0 to hold is that there is a constant c > 0 such that

for all t ≥ 0. Let us check that this inequality is satisfied for sufficiently small positive values and c.

To this end, notice that using the notation from Theorem 1, it follows that for all t ≥ 0, we have

where the equalities in (56) follow because a is nonnegative valued. Hence, the left side of (55) is bounded below by

for all t ≥ 0. Since

it follows that when > 0 is small enough, we have

which ensures that lim t→+∞ v(t) = 0, by Corollary 1.

On the other hand, [START_REF] Ruan | Novel stability results for Halanay inequality and applications to delay neural networks[END_REF]Theorem 1] would not apply to the preceding example. To see why, first observe that (53)

for all t ≥ 0. Then, with the choice H( ) = sin 2 ( -0.49π) + sin 2 ( -1.99π), the function

satisfies

which follows by using sin 2 ( ) = 1 2 (1 -cos( 2)) to evaluate and then bound the integrals in (62). Since lim t→+∞ G(t) = +∞, it follows that [13, Theorem 1] does not allow us to prove that lim t→+∞ v(t) = 0. By covering the preceding example which is not covered by [13, Theorem 1], it follows that Theorem 1 is less restrictive than [13, Theorem 1].

C. Illustration of Theorem 2

Using the notation from Theorem 2, and considering any constant b 0 ∈ (0, 1), consider the special case where a(t) = sin 2 (t), b(t) = b 0 sin 2 (t), and T = 2π. Then

for all t ≥ 0. It follows that sup

To apply Theorem 2, we use the comparison system

Bearing Theorem 2 and Remark 3 in mind, we obtain the following sufficient condition for stability:

for all t ≥ 0. Condition (66) holds if and only if b 0 e π(1-b0) + 2 e π(1-b0) < 1. By choosing > 0 small enough, we obtain the condition b 0 e -πb0 < e -π .

For a comparison, we next apply Theorem 1, with k = 1, T 1,1 = 0, and T 2,1 = 2π, using the comparison system

Reasoning as in Remark 3, we obtain the stability condition 2π 0

-sin 2 (s) + (b 0 sin 2 (s) + )e π ds < 0 (69)

which is equivalent to -1 + b 0 e π < -2 e π . Since > 0 is arbitrarily small, we obtain the stability condition

Note that e -π e -πe -π < e -π , so if (70) holds, then so does (67) (because xe -πx increases over x ∈ [0, e -π ]), and (67) holds with b 0 = e -π . Hence, (67) is less restrictive than (70). This example shows how Theorem 2 is less restrictive than Theorem 1, because it can cover the case b 0 = e -π that was not covered by Theorem 1.

IV. CONCLUSIONS

We proposed new stability analysis results for functions that satisfy generalized time-varying inequalities of Halanay's type. We illustrated how our results can provide less restrictive conditions than ones in the literature. Since earlier generalizations of Halanay's inequality have been shown to be effective for solving observer design problems that were beyond the scope of the observers literature (e.g., in [START_REF] Mazenc | Stability and observer designs using new variants of Halanay's inequality[END_REF]), we aim to apply our work to observer designs for continuousdiscrete, event-triggered, and switched systems.