Aleksandr Tvardovskii
email: tvardal@mail.ru

Refining the specification FSM when deriving test suites w.r.t. the reduction relation

Keywords: Finite State Machines (FSM), nondeterministic FSM, test derivation

Finite State Machines (FSMs) are widely used when deriving tests for components of discrete event systems. In general, the specification FSM can be nondeterministic and in this case, a test suite with the guaranteed fault coverage is derived with respect to the reduction relation. However, when deriving such tests for nondeterministic FSMs, the existing methods return rather long test suites which cannot be used for real systems. In order to shorten a test suite, the set of possible implementation FSMs can be reduced. We present an approach for deriving shorter test suites for nondeterministic FSMs with respect to the reduction relation via refining the specification FSM.

Introduction

Finite State Machine (FSM) based test derivation is an active research area that has a long history [START_REF] Gill | Introduction to the Theory of Finite-State Machines[END_REF][START_REF] Chow | Test design modeled by finite-state machines[END_REF]. The well-known method is the W-method [START_REF] Chow | Test design modeled by finite-state machines[END_REF] and many derivatives of this method have been developed including those for FSMs with the nondeterministic behaviour [see, for example, [START_REF] Dorofeeva | FSM-based conformance testing methods: a survey annotated with experimental evaluation[END_REF][START_REF] Petrenko | Conformance Tests as Checking Experiments for Partial Nondeterministic FSM[END_REF][START_REF] Petrenko | Adaptive Testing of Deterministic Implementations Specified by Nondeterministic FSMs[END_REF]. In FSM based testing, the specification behaviour and the behaviour of an implementation under test (IUT) are described by FSMs and by applying input sequences to the IUT and observing the produced outputs a tester should conclude whether the IUT conforms to its specification. Best known conformance relations are the equivalence and reduction relations [START_REF] Petrenko | Conformance Tests as Checking Experiments for Partial Nondeterministic FSM[END_REF]. In the former case, the IUT has to have the same behaviour as the specification FSM; in the latter case, the behaviour of the IUT has to be contained in the behaviour of the specification FSM.

In this paper, we propose to refine the FSM specification via deleting some transitions in such a way that the refined specification has an (adaptive) distinguishing sequence that distinguishes every two different states and all the states are definitely reachable from the initial state [START_REF] Petrenko | Adaptive Testing of Deterministic Implementations Specified by Nondeterministic FSMs[END_REF], i.e., each state is (adaptively) reachable from the initial state. Under such conditions, the length of a test suite against nondeterministic FSMs is comparable with that for deterministic FSMs.

The rest of the paper has the following structure. Section 2 contains the preliminaries. A procedure for deriving complete test suites against nondeterministic FSMs with respect to the reduction relation is presented in Section 3. Section 4 contains a proposed procedure for reducing the specification FSM. Section 5 concludes the paper.

Preliminaries

In this section, we introduce necessary definitions and notations which are mainly taken from the paper [START_REF] Petrenko | Adaptive Testing of Deterministic Implementations Specified by Nondeterministic FSMs[END_REF].

A finite state machine (FSM), or simply a machine, is a 5-tuple S = S, I, O, hS, s0 where S is a finite nonempty set of states with the designated state s0, I and O are finite input and output alphabets, and hS  S  I  O  S is a transition (behavior) relation. FSM S is nondeterministic if for some pair (s, i)  S  I, there can exist several pairs (o, s)  O  S such that (s, i, o, s)  hS; otherwise, the FSM is deterministic. FSM S is complete if for each pair (s, i)  S  I there exists (o, s)  O  S such that (s, i, o, s)  hS; otherwise, the FSM is partial. FSM S is observable if for every two transitions (s, i, o, s1), (s, i, o, s2)  hS it holds that s 1 = s2. In the following, we consider complete observable possibly nondeterministic FSM specifications, while an implementation is a complete deterministic FSM.

Figure 1 shows a FSM A for which I ={i1, i2, i3}, O ={o1, o2, o3}, S ={1, 2, 3} and 1 is the initial state. Suppose that input i1 is applied to this FSM at the state 1. After applying input i1 the FSM can remain at state 1 and produce an output o1. However, the FSM can also stay at state 1 while producing output o2.

Fig. 1. FSM A

A trace of FSM S at state s is a sequence of input/output pairs  = i1/o1 … il/ol of consecutive transitions starting from state s. A sequence of inputs i1 … il is an input sequence, a sequence of outputs o1 … ol is an output sequence.

Given an input alphabet I and an output alphabet O, a test case TC(I, O) is an initially connected observable FSM T = (T, I, O, hT, t0) with an acyclic transition graph such that at each state only one input with all possible outputs is defined. Given a complete FSM S over alphabets I and O, a test case TC(I, O) represents an adaptive experiment with the FSM S. If |I| > 1 then a test case is a partial FSM. A state t  T is a deadlock state of the FSM T if there are no defined inputs at this state. The notion of a test case can be used for representing an adaptive input sequence when the next input depends on the output to the previous input. In general, given a test case T, the length (height) of the test case T is defined as the length of a longest trace from the initial state to a deadlock state of T and it specifies the length of the longest input sequence that can be applied to an FSM S during the experiment.

A test case T is a distinguishing test case (DTC) for an FSM S if for every trace  of T from the initial state to a deadlock state,  is trace at most at one state of S. Sometimes, a distinguishing test case is called an adaptive distinguishing sequence. A distinguishing test case for a submachine of FSM A in Figure 1 without the bold transition (2, i1, o2, 1) is shown in Figure 2. A test case T represents an (adaptive) transfer sequence from the initial state to state s if every trace of T from the initial state to a deadlock state takes the FSM from the initial state to state s. According to [START_REF] Petrenko | Adaptive Testing of Deterministic Implementations Specified by Nondeterministic FSMs[END_REF], if there exists an (adaptive) transfer sequence from the initial state to state s then state s is definitely reachable from the initial state and must be implemented in a conforming implementation [START_REF] Petrenko | Adaptive Testing of Deterministic Implementations Specified by Nondeterministic FSMs[END_REF]. Adaptive transfer sequences to states 2 and 3 for FSM A in Figure 1 is shown in Figure 3. For a deterministic FSM, a transfer sequence is simply an input sequence.

Fig. 3. Transfer test cases for FSM A

Test cases are (adaptive) input sequences which are derived against the given FSM specification to determine whether a given black-box implementation under test (IUT), which is also assumed to have the FSM behavior, conforms to the given specification. In this paper, an IUT conforms to the specification if an implementation FSM is a reduction of the specification FSM. In other words, an IUT conforms to the specification FSM if for each input sequence the output response of the IUT is contained in the set of output responses of the specification FSM to this input sequence. If the observed outputs do not match, then the implementation has a fault, i.e., it is a nonconforming implementation.

Given states s and p of complete FSMs S and P, state p is a reduction of s, p  s, if the set of I/O sequences of FSM P at state p is contained in the set of I/O sequences of FSM S at state s. FSM P is a reduction of FSM S if the reduction relation holds between the initial states of these machines.

We consider the fault domain n which contains every deterministic complete FSM with at most n states and with the same input alphabet as the specification FSM S where n is number of states of the specification FSM. A test suite is a finite set of finite possibly adaptive input sequences of the specification. A test suite is complete with respect to the n if for each FSM P n such that P is not a reduction of S, the test suite has a sequence for which an output response is not in the set of output responses of S to this sequence. In the next section, based on the results of [START_REF] Petrenko | Conformance Tests as Checking Experiments for Partial Nondeterministic FSM[END_REF] we briefly remind how a complete test suite with respect to n can be derived when the specification FSM has a distinguishing test case and each state is definitely reachable from the initial state.

Deriving a complete test

Methods for deriving tests with respect to the reduction relation are based on (adaptive) distinguishing and transfer sequences. A test suite of polynomial length can be derived under the following conditions: 1) an IUT is deterministic and does not have more states than the specification FSM; 2) the specification FSM has an (adaptive) distinguishing test case of polynomial length and each state is definitely reachable from the initial state.

An algorithm below returns a complete test suite with respect to the n if the specification FSM has a distinguishing test case and each state is definitely reachable from the initial state. Since the length of an (adaptive) transfer sequence (if it exists) does not exceed n [START_REF] Petrenko | Adaptive Testing of Deterministic Implementations Specified by Nondeterministic FSMs[END_REF], the length of a returned test suite is polynomial with respect to the number of states of the specification FSM when a DTC possesses this feature. It is known [START_REF] Dorofeeva | FSM-based conformance testing methods: a survey annotated with experimental evaluation[END_REF] that a returned test suite can detect many other faults but the guarantee is only for FSMs with up to n states where n is the number of states of the specification FSM.

Procedure 1 Deriving a complete test suite w.r.t. the fault domain n Input: A complete possibly nondeterministic observable specification FSM S with n states

Output: A complete test suite TS with respect to n

Step-1: If some state of S is not definitely reachable from the initial state or the FSM has no DTC

Then Return the message "The specification FSM does not possess the necessary features"

Else Step-2

Step-2: Derive a state cover of the FSM using (adaptive) transfer sequences; Append every sequence of the state cover with a DTC; Append every sequence of the state cover with all possible inputs which in turn, are appended with a DTC; Denote TS the obtained set of (adaptive) input sequences; Return the obtained set TS of input sequences.

According to the results in [START_REF] Petrenko | Conformance Tests as Checking Experiments for Partial Nondeterministic FSM[END_REF][START_REF] Petrenko | Adaptive Testing of Deterministic Implementations Specified by Nondeterministic FSMs[END_REF], the following proposition holds. Proposition 1. If the specification FSM S has a DTC and each state of S is definitely reachable from the initial state then Procedure 1 returns a complete test suite with respect to n; the length of a test suite is proportional to the product |S| |I| |LDTC| where LDTC is the length of the distinguishing test case DTC.

Refining the specification FSM

If the specification FSM S has no DTC or some state is not definitely reachable from the initial state then we could find a maximal submachine of S (i.e. a submachine with maximum number of transition) that possesses this feature, however, this is not always possible. For example, there is no such submachine if there are at least two states where transitions under the every input are deterministic and the FSM is taken to the same state with the same output. Nevertheless, if this is possible then we could delete some transitions from the specification FSM in order to have an FSM where each state is definitely reachable and there is a DTC of polynomial length. For example, a submachine of the FSM in Figure 1 without the bold transition (2, i1, o2, 1) has a DTC of length 2 and each state is definitely reachable from the initial state.

Given the specification FSM S, let S red be its maximal complete submachine where each state is definitely reachable and there is a DTC of polynomial length. If S = S red then a test suite returned by Procedure 1 is complete with respect to the fault domainn. If S is not equal to S red then Procedure 1 is used for deriving a test suite TS for FSM S red and the following proposition holds.

Proposition 2. If for each input sequence of TS the output response of an IUT P is in the set of output responses of S red , then the IUT is a reduction of the FSM S. If the output response of the IUT to some sequence of TS is not contained in the corresponding set of output responses of the specification FSM S to this input sequence, then the IUT is not a reduction of S.

If the output response of the IUT to some sequence of TS is not contained in the corresponding set of output responses of S red but is contained in the set of output responses of S, then we cannot conclude whether the IUT conforms to its specification. i.e., the verdict is inconclusive.

When deriving distinguishing test cases, merging-free FSMs are often considered. An FSM S is merging-free if for every two transitions (s1, i, o, s) and (s2, i, o, s) it holds that states s1 and s2 coincide. In [START_REF] Yevtushenko | Nondeterministic Merging-free Finite State Machines[END_REF] it is shown, that a merging-free FSM S has a DTC if and only if for each pair of state of S there exists a DTC and moreover, if there exists a DTC then there exists a DTC with the length that is polynomial with respect to the number of states of S. However, in this paper, we do not derive a maximal merging-free submachine of the specification FSM. Another way to find a maximal submachine of S that possesses necessary features could be the enumeration of all submachines of the specification FSM. However, as this number is big enough, we further propose to consider only deterministic submachines of the specification FSM. Another reason for considering deterministic submachines is that if a complete deterministic FSM has an adaptive distinguishing sequence then the length of such sequence is O(n 2 ) [START_REF] Lee | Testing finite-state machines: state identification and verification[END_REF].

Procedure 2 Refining the specification FSM Input: a complete possibly nondeterministic observable specification FSM S with n states Output: a complete submachine S red of FSM S where each state is definitely reachable and there is a DTC of reasonable length or the message "The specification FSM cannot be reduced"

Step-1: Find a set of all complete deterministic submachines of FSM S, determine a submachine S which has a DTC.

If such FSM does not exist

Then Return the message "The specification FSM cannot be reduced"; Else derive a DTC and a transfer sequence for each state of S Step-2: For each transfer sequence  from the initial state to state s of S, remove from S each transition tr such that tr is executed by S when  is applied, and transition tr breaks the property of  to be a transfer sequence to state s in S.

Step-3: For a DTC of S, remove from S each transition tr such that tr is executed by S when any sequence  from TC is applied and transition tr breaks the property of TC to be DTC for S.

Denote S red the FSM obtained from S after removing transitions.

If Procedure 2 returns FSM S red then S red has DTC and each state is definitely reachable from the initial state, i.e., for each state of S red there exists an (adaptive) transfer sequence, then a test suite returned by Procedure 1 for S red has the fault coverage defined by Proposition 2.

Conclusions

In this paper, an approach for deriving test suites of reasonable length for nondeterministic FSMs with respect to the reduction relation has been proposed. A proposed method is based on deriving a submachine of the initial FSM specification that has a distinguishing test case of polynomial length and each state is definitely reachable from the initial state can be derived. Derived for refined specification test is not always complete, but can be used for checking an appropriate subset of implementations.

Fig. 2 .

 2 Fig. 2. A distinguishing test case for a submachine of FSM A without the bold transition (2, i1, o2, 1)

Acknowledgement

This work is partly supported by RSF Project No. 16-49-03012.


Célestin Matte

Mathieu Cunche

Wombat: An experimental Wi-Fi tracking system

In this paper, we present Wombat, a Wi-Fi tracking platform aiming at improving user awareness toward physical tracking technologies and at experimenting new privacy-preserving mechanisms. Elements of this system are presented along with its architecture. We also present the use of Wombat in the context of a demonstration scenario. We introduce a new privacy-enhancing feature developed on top of Wombat: a Wi-Fibased opt-out mechanism that allows users to easily express their opt-out decision.

Introduction

Whether it is through websites or mobile applications, user tracking is a common thing in the digital world. This practice of monitoring users' activity for analytics or profiling purposes has recently been extended to the physical world, where radio and video technologies now allow to accurately detect, recognize and categorize human activities [START_REF] Nguyen | IdentityLink: user-device linking through visual and RF-signal cues[END_REF][START_REF] Musa | Tracking Unmodified Smartphones Using Wi-fi Monitors[END_REF][START_REF] Fung | How stores use your phone's WiFi to track your shopping habits[END_REF].

This work focuses on the radio flavor of physical tracking, in which radio signals emitted by our mobile devices are collected in order to infer our activities in the physical world [START_REF] Musa | Tracking Unmodified Smartphones Using Wi-fi Monitors[END_REF]. Radio-based physical tracking relies on sniffers that collect identifiers contained in messages emitted by radio-enabled devices [START_REF] Freudiger | How talkative is your mobile device?: an experimental study of Wi-Fi probe requests[END_REF]. These identifiers are used to detect users' presence and estimate their mobility. Because Wi-Fi is included in many portable devices and relatively easy to sniff, it is the main radio technology used in the physical tracking industry.

Nowadays, physical tracking systems are deployed in shopping centers [START_REF] Fung | How stores use your phone's WiFi to track your shopping habits[END_REF], urban transportation systems, highways or ring roads [START_REF]Evaluations simultanées de différentes technologies innovantes de recueil de données trafic pour le calcul de temps de parcours en temps réel[END_REF]. Because these systems passively collect identifiers without user consent (and often without their knowledge), they are the source of major privacy concerns [START_REF] Martinez | Franken still unsatisfied with Euclid's privacy practices[END_REF][START_REF] Clifford | Attention, Shoppers: Store Is Tracking Your Cell[END_REF]. Despite some efforts from the industry and close surveillance from data protection authorities, users' privacy is still in jeopardy [START_REF] Demir | Analysing the privacy policies of Wi-Fi trackers[END_REF]1,[START_REF] Higgins | Mobile Tracking Code of Conduct Falls Short of Protecting Consumers[END_REF]. This is aggravated by the fact that this technology is not well known by the general public, usually not aware that such systems exist and that passers-by may have been tracked.

The goal of this work is to remedy to this situation by raising public awareness towards tracking technologies. To this end, we have developed an experimental Wi-Fi-based physical tracking system that can be used for demonstration purposes. This system effectively tracks users through their radio-enabled mobile devices (e.g. smartphones) and can then show the users the type and amount of data that has been collected. In addition, this experimental platform is also used to deploy and test privacy-enhancing features for physical tracking systems.

After presenting some background and related works in section 2 and 3, we present the experimental physical tracking system in section 4. Then, in section 5, we present how this system is used for raising user awareness. Finally, in section 6, we present an example of privacy-preserving feature. Section 7 concludes the paper.

Wi-Fi-based physical tracking

A key element of infrastructure-based Wi-Fi networks is the ability for the stations (devices equipped with a Wi-Fi interface) to discover available networks. This feature called service discovery is enabled by two distinct mechanisms. One of them, called the active service discovery mode, relies on probe request messages that are sent by stations and to which access points reply with probe responses.

Stations using this mechanism thus periodically and automatically broadcast probe requests. As most Wi-Fi frames, probe requests include the MAC address of the sender, a globally unique identifier tied to a device. Because of its superior energy efficiency, the active discovery mode is enabled on most Wi-Fi devices. As a consequence, all mobile devices having their Wi-Fi interface enabled broadcast a unique identifier and expose their owner to tracking [START_REF] Freudiger | How talkative is your mobile device?: an experimental study of Wi-Fi probe requests[END_REF].

This kind of tracking is performed by Wi-Fi-based systems that collect messages coming from Wi-Fi-enabled devices in order to detect the people's presence and track their whereabouts. These systems are typically composed of several sniffing nodes that are in charge of collecting Wi-Fi signals over an area of interest. Each sniffing node collects incoming Wi-Fi frames and extracts a unique identifier along with other technical information. Nodes then report this data to a central server, where it can be stored and processed for further analysis, such as building trajectories and aggregate statistics.

Related Works

Privacy issues in Wi-Fi tracking systems: Because of their passive and pervasive nature, Wi-Fi tracking systems have raised a number of privacy concerns [START_REF] Clifford | Attention, Shoppers: Store Is Tracking Your Cell[END_REF][START_REF] Martinez | Franken still unsatisfied with Euclid's privacy practices[END_REF][START_REF] Sen | Franken Presses Tech Firm to Stop Tracking Consumers without Their Permission | Al Franken[END_REF]. Stakeholders of the Wi-Fi tracking industry have reacted by adopting a Mobile Location Analytics Code of Conduct [16]. The latter is a set of guidelines, including "anonymization" and opt-out, supposed to reduce privacy risks. However, a number of these measures are ineffective in protecting users' privacy [START_REF] Higgins | Mobile Tracking Code of Conduct Falls Short of Protecting Consumers[END_REF]1,[START_REF] Demir | Analysing the privacy policies of Wi-Fi trackers[END_REF].

Data protection authorities have taken actions by fining some Wi-Fi tracking companies [START_REF] Geuss | Creepy but legal phone-tracking company gets wrist slap for empty privacy promise[END_REF] or by blocking the deployment of Wi-Fi tracking systems [START_REF] Bouchenard | JC Decaux's pedestrian tracking system blocked by French data regulator[END_REF]. Parallelwise, the smartphone and computer industry is taking steps to protect users against tracking by deploying MAC randomization mechanisms in their products [START_REF] Wang | Wireless networking in Windows 10[END_REF][START_REF] Grumbach | iwlwifi: mvm: support random MAC address for scanning[END_REF][START_REF]Android 6.0 changes[END_REF][START_REF] Skinner | Privacy and your app[END_REF]. However, these countermeasures are not always sufficient to protect against tracking [START_REF] Vanhoef | Why MAC Address Randomization is Not Enough: An Analysis of Wi-Fi Network Discovery Mechanisms[END_REF][START_REF] Martin | A Study of MAC Address Randomization in Mobile Devices and When it Fails[END_REF].

Experimental Wi-Fi tracking systems: Research and hacking communities have noticed the possibility of tracking users through Wi-Fi signals, which lead to the development of several systems to demonstrate tracking potential. G. Wilkinson proposed Snoopy, a distributed Wi-Fi tracking system that can include a drone as a sniffing node [START_REF] Wilkinson | Digital terrestrial tracking: The future of surveillance[END_REF]2]. CreepyDoll is another Wi-Fi surveillance system that features a distributed data storage [START_REF] Brendan | CreepyDOL: Cheap, Distributed Stalking[END_REF]. Scheuner et al. introduced Probr [START_REF] Scheuner | Probr -A Generic and Passive WiFi Tracking System[END_REF], a Wi-Fi tracking systems providing extensive analytics features. The Digital Marauder's Map [START_REF] Fu | The Digital Marauder's Map: A New Threat to Location Privacy[END_REF] is a system that demonstrates the possibility of getting fine-grained users location, using multiple sniffers.

In [START_REF] Robyns | Noncooperative 802.11 mac layer fingerprinting and tracking of mobile devices[END_REF], Robyns et al. built a tracking system using low-cost MikroTik 5RB912UAG-2HPnD devices as nodes.

Panoptiphone [START_REF] Matte | DEMO: Panoptiphone: How Unique is Your Wi-Fi Device[END_REF] is a prototype that demonstrates fingerprinting of Wi-Fi devices based on technical characteristics of frames.

The closest related work is the effort conducted by Bonne et al. They introduced WiFiPi, a tracking system that have been used to monitor mass events such as a music festival [START_REF] Bonné | WiFiPi: Involuntary tracking of visitors at mass events[END_REF]. Then, they presented a system called SASQUATCH [START_REF] Bonné | Raising Awareness on Smartphone Privacy Issues with SASQUATCH, and solving them with PrivacyPolice[END_REF][START_REF] Bonné | Your Mobile Phone is a Traitor!-Raising Awareness on Ubiquitous Privacy Issues with SASQUATCH[END_REF] which aims at raising awareness by displaying information leaked by smartphones, including information that can be inferred from SSIDs. In addition to the demonstration purposes of their work, our approach possesses a strong emphasis on the experimentation of new privacy features.

Wombat: a Wi-Fi tracking platform

Wombat is a fully functional Wi-Fi tracking platform supporting three main features: collection, storage/processing, query/output. These three features are implemented through a distributed infrastructure composed of:

• Sensor nodes: small devices with wireless monitoring capabilities. They collect information sent on wireless channels and forward it to the server.

• Central server: the central entity of the system. It receives data sent by sensor nodes and then stores it in an internal data structure. It is also in charge of answering queries related to the stored data.

To ensure communication between the sensor nodes and the server, the Wombat system relies on a wired network (Ethernet). In addition, Wombat can be enriched with a user interface and an opt-out node:

• User interface: a device in charge of displaying detailed information about one or several tracked devices (see Figure 2). The device to display can be specified manually by its MAC address or through proximity detection.

• Opt-out node: an element in charge of implementing an opt-out mechanism for users refusing to be tracked by the system (see section 6).

A description of the Wombat system with all its components is presented on Figure 1.

Raising user awareness

Users are generally not aware that Wi-Fi tracking is possible and are even less aware that it is actually used by commercial entities. This can be explained by the fact that tracking is performed using radio signals, a technology that leaves no visible traces. Moreover, the visual notifications displayed by trackers are generally obscure.

For the sake of transparency, it is therefore important to show people that such technologies exist, and to explain their principles and their capabilities. Wombat has been developed in this spirit: to raise user awareness by demonstrating a real-world Wi-Fi tracking system.

Although Wombat lacks some of the functionalities found in industrial Wi-Fi tracking systems, it features their core functionalities: device identification and detection, itinerary tracking. These functionalities are enough to present the principles of a Wi-Fi tracking system and to initiate a discussion on the corre-sponding privacy issues. The Wombat system has been used during demonstrations addressed to different types of audiences: researchers, students, industrials, and general public.

The Wombat system is currently deployed at La Cité des Sciences et de l'Industrie, a museum dedicated to science popularization in France. It is part of a one-year-long exhibition (April 2017 -March 2018) on data and digital technologies called Terra Data1 . Wombat is deployed all over the exhibition using 9 sensor nodes, a server node and an opt-out node. It is accompanied by a user interface developed by a third party.

The demonstration scenario is the following. Visitors exploring the exhibition are tracked through Wi-Fi signals emitted by their personal devices. At the entrance, they are notified of the system's presence and of the opt-out mechanism. In the last part of the visit, they reach the user interface where they can explore the information that has been collected on them. Through a proximity sensor combined with a Wi-Fi interface, the system detects the device that is placed on the stand. From there, an interactive screen displays the collected data: identifier, brand of the device, name of the networks searched by the device, and an approximate representation of the user itinerary inside the exhibition.

This last demonstration has the potential to enlighten a large number of individuals from the general public. People aware of the potential privacy issues will be more inclined to adopt solutions to protect their privacy, and to ask for better privacy protections, either legal or technical.

6 Privacy-enhancing feature: Opt-Out Mechanism

Current opt-out mechanisms and their limitations

Wi-Fi tracking systems have been criticized because they are collecting users' data without their consent. As a result, opt-out mechanisms have been deployed [16] to allow concerned users to escape tracking. These opt-out mechanisms typically involve a webpage on which the user needs to enter its device address2 (see Figure 3). Although, it represents a step toward more user control, this kind of approach presents several issues, mainly related to their usability. The main issues are the following:

1. In order to retrieve the MAC address, users need to navigates deep into the device's settings, which can be a difficult task for non-tech-savvy users.

2. Users need to manually enter this 16-character-long identifier on the optout webpage, which can be a cumbersome task.

3. Subscribing to the opt-out mechanisms means that the device identifier will be sent to a third party which will store it indefinitely. The user needs to enter the address of its device to opt out.

Multiple tracking systems may use different opt-out databases and thus

require users to go through this process for each system.

It is likely that these usability issues will deter users from using this opt-out mechanisms, thus preventing them from protecting their privacy. A more usable opt-out solution is therefore required.

A Wi-Fi-based opt-out mechanism

We propose to use Wi-Fi as a vector to transmit the opt-out decision, by leveraging core Wi-Fi elements. More specifically, on the tracking system side, the opt-out mechanism is implemented by a primitive3 Access Point (AP), to which Wi-Fi stations willing to opt out must connect.

The network name (SSID) announced by this AP is explicitly indicating the purpose of the network: opting out of a Wi-Fi tracking system. For instance, this SSID can be Opt-Out Wi-Fi tracking or Do not track.

A device whose owner wants to opt out will connect to this AP. Upon such an event, the device will contact the AP in order to proceed through the association protocol. During this process, the AP will learn the MAC address of the device by parsing received frames. From this point on, the AP can consider that the corresponding device wants to opt out of the tracking system, and can thus add this address to a local blacklist. This list is maintained locally, and an expiry delay can be configured on the server so that blacklisted identifiers are not kept indefinitely.

For the user, the opt-out procedure can be summarized as follow:

1. Open the Wi-Fi network manager;

2. Identify and select the opt-out network;

3. Connect to the opt-out network.

From a user point of view, this opt-out mechanism involves a small number of simple tasks with which most users are familiar: identifying and connecting to a Wi-Fi network. Thus, we provide a user experience which won't discourage users from actually opting out of the system.

Concerning the device, Wi-Fi-based opt-out is supported by all Wi-Fi devices providing a user interface, which is the case for the majority of devices carried around by people (smartphone, tablets, laptops, ...). In addition it has the big advantage of not requiring any software or hardware modification.

On the Wi-Fi tracking system side, only minor modifications must be performed: a primitive AP must be deployed and must be linked to the Wi-Fi tracking system in order to report opting out MAC addresses.

Another advantage of this method is its persistence and its seamless nature: next time the device will detect an opt-out AP using the same SSID, it will automatically notify its willingness to opt out without requiring any user intervention. Indeed, as the device has already been successfully connected to the opt-out network, the latter is configured and will be remembered by the device's network manager. As a consequence, next time the device will come in range of an AP advertising this opt-out SSID, it will connect to this AP, effectively indicating its intent to opt out.

A global opt-out mechanism for Wi-Fi tracking could be implemented if all stakeholders agree on a common SSID. This mechanism could then be seen as an equivalent of the web-based Do-Not-Track (DNT) mechanism [START_REF] Mayer | Do Not Track: A Universal Third-Party Web Tracking Opt Out[END_REF] for the physical world.

Conclusion

We introduced Wombat, an experimental Wi-Fi tracking system. We showed how it can be used as a demonstration tool in order to raise user awareness. Then we showed how this platform can be used as a basis to develop and test privacy-preserving mechanisms. The first one of such mechanisms, a Wi-Fibased opt-out mechanism, has been presented. It has the advantage of being easy to implement and to use be end users.

We envision to develop the demonstrative aspects of Wombat, by including other radio technologies, improving the trajectory reconstruction algorithm, and extending the user interface. We also plan to integrate other privacy preserving features to Wombat such as privacy-preserving analytics [START_REF] Alaggan | Privacy-Preserving t-Incidence for WiFi-based Mobility Analytics[END_REF].

Figure 1 :

 1 Figure 1: Architecture of the Wombat system in a demonstration configuration.

Figure 2 :

 2 Figure 2: Basic user interface of Wombat displaying the device's MAC address, the list of SSIDs, as well as a mobility trace under a timeline form.

  Figure 3: Screenshot of a the opt-out webpage https://optout.smart-places.org/.The user needs to enter the address of its device to opt out.

http://www.cite-sciences.fr/fr/vous-etes/enseignants/votre-visite/ expositions/terra-data/

https://smart-places.org/

This AP is primitive because it does not provide any service other than announcing its presence and allowing devices connections. In particular, it does not provide IP connectivity, i.e. no network connection is possible. Because of this lack of network connectivity, most devices will disconnect automatically after a certain period of time.


Caetano B Cardeliquio
email: caetano.cardeliquio@l2s.centralesupelec.fr

Matheus Souza
email: msouza@fee.unicamp.br

André R Fioravanti
email: fioravanti@fem.unicamp.br

Stability Analysis and Output-Feedback Control Design for Time-Delay Systems

Keywords: Time-delay Systems, Output-feedback, H ∞ -norm, Comparison System

come

L'archive ouverte

INTRODUCTION

Time delays are intrinsically present in the structure of feedback control loops. Even though these delays are sometimes neglected, they can be responsible for poor performance and they may even lead the system to instability. For that reason, several studies considering the so called time-delay systems have being made through the last decades. Important theoretical results on time-delay systems control can be seen in the books [START_REF] Gu | Stability of Time-Delay Systems[END_REF] and [START_REF] Niculescu | Advances in Time-Delay Systems[END_REF]) and in the survey paper [START_REF] Richard | Time Delay Systems: An Overview of Some Recent Advances and Open Problems[END_REF].

Filtering and output-feedback for time-delay systems can be seen in [START_REF] Fridman | ∞ Control of Linear State-delay Descriptor systems: an LMI Approach[END_REF] and the design of observers in [START_REF] Sename | Observer-based hinfinity Control for Time-delay Systems: a new LMI Solution[END_REF]. State and output feedback stability were dealt in [START_REF] Mahmoud | H ∞ -Controllers for Time-Delay Systems Using Linear Matrix Inequalities[END_REF]. A modified Riccati equation is used in [START_REF] Lee | Memoryless H ∞ Controllers for State Delayed Systems[END_REF] for the design of a memoryless H ∞ controller. The H ∞ control problem for multiple input-output delays was also discussed in [START_REF] Meinsma | H ∞ Control of Systems with Multiple I/O Delays via Decomposition to Adobe Problems[END_REF]. Other important works on the field are, for example, [START_REF] Choi | Observer-Based H ∞ Controller Design for State Delayed Linear Systems[END_REF], [START_REF] Ge | H ∞ Control via Output Feedback for State Delayed Systems[END_REF], (Fridman and Shaked, 2002a) and (de [START_REF] De Oliveira | Synthesis of Non-ratinal Controllers for Linear Delay Systems[END_REF]. In this work, our goal is to increase the maximum delay allowed in time-delay linear systems for a given H ∞ level γ through output-feedback control design. Furthermore, if the delay is given, our goal is to minimize γ. In [START_REF] Korogui | H ∞ Control Design for Time-Delay Linear Systems: A Rational Transfer Function Based Approach[END_REF], which is the main work that we rely on, the Rekasius substitution [START_REF] Rekasius | A stability test for systems with delays[END_REF] for k = 1 was successfully applied to obtain a finite order LTI system, called com-⋆ This work was supported by grants from Smart 2 Erasmus Mundus, Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq/Brazil) grant 303850/2014-0 and Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) grant 2014/17074-0.

parison system which was used to calculate an inferior bound for the H ∞ norm of the time-delay system. Here, we extend this approach finding the linear dependence on the matrices of the system with its comparison system for a substitution of order N . Therefore, our contribution is in designing a controller which depends not only on the output at the present time and maximum delay, but also on an arbitrary number of intermediate values in between, for both minimising H ∞ norm or maximising the allowed delay. Hence, we are able to increase the maximum stable delay using information that is already in the buffer. The new parametrisation for the comparison system proposed here altogether with the design procedure, when compared with results in the literature, is simpler to be implemented and provides more accurate results. One illustrative example is presented.

Notation. Matrices are denoted by capital letters, whilst small letters represent scalars and vectors. For real matrices or vectors the symbol ( ′ ) indicates transpose. Additionally, the maximum singular value of a matrix is denoted by σ(•). The sets of real, nonnegative real and natural numbers are denoted by R, R + and N. The kronecker product is represented by ⊗, the null space of a matrix L by ker(L) = {v ∈ V |L(v) = 0} and vectorisation of a matrix A by vec(A) = [a 1,1 , . . . , a m,1 , a 1,2 , . . . , a m,n ] ′ . Moreover, vec -1 (vec(A)) = A. In particular, rational transfer functions of LTI systems are denoted as

A B C D = C (sI -A) -1 B + D, (1)
in which all matrices are real and of compatible dimensions. The binomial coefficient is denoted by

N k = N ! k!(N -k)! , (2)
which is zero whenever the integers k and N satisfy k < 0 or k > N .

COMPARISON SYSTEM

Consider the time-delay linear system with M commensurate delays, whose minimal realisation is given by

ẋ(t) = A 0 x(t) + M j=1 A j x (t -τ j ) + E 0 w(t), z(t) = C z0 x(t) + M j=1 C zj x (t -τ j ) , (3)
in which, for all t ∈ R + , x(t) ∈ R n is the state, w(t) ∈ R m is the exogenous input, z(t) ∈ R p is the output of interest and τ j = τ (M -j + 1)/M, j = 1 . . . M , for a given constant time delay τ ≥ 0. In this work, we address the problem of the commensurate delayed system (3) by applying the following substitution to the time delay operator concerning the largest delay:

e -τ s = λ -s λ + s N , (4)
which is an exact relation for s = jω, with τ, λ, ω ∈ R + and N ∈ N such that

ωτ = 2N arctan ω λ . (5)
When N = 1 this is known as Rekasius substitution [START_REF] Rekasius | A stability test for systems with delays[END_REF]. For the following developments it will be necessary that the number of delays be the same as the order of the approximation (4). Note however, that whenever N = hM for some h ∈ {1, 2, . . .}, system (3) can be equivalently restated as

ẋ(t) = A 0 x(t) + N k=1 A k x (t -τ k ) + E 0 w(t), z(t) = C z0 x(t) + N k=1 C zk x (t -τ k ) , (6)
with τ k = (N -k + 1)/N , by a suitable change of indices and considering null matrices whenever the respective delay is not present in the original formulation (3). Thus, without loss of generality, hereafter we are going to work with the rearranged system (6) which satisfies N = hM for some h ∈ {1, 2, . . .}.

One of our goals is to determine the maximal time-delay τ ⋆ > 0 that ensures the system is globally asymptotically stable for any τ ∈ [0, τ ⋆ ). To achieve this, one must analyse the non-rational transfer function of ( 6), which is given by

T (s, τ ) = C z0 + N k=1 C zk e -τ k s × × sI -A 0 - N k=1 A k e -τ k s -1 E 0 , (7)
Applying the substitution (4) to the transfer function T (s, τ ) in ( 7), we can define the comparison system with transfer function H(s, λ) such that H(jω, λ) = T (jω, τ ), whenever (5) holds. In this case, the comparison system's transfer function is given by the following two Lemmas Lemma 1. [START_REF] Cardeliquio | Stability Analysis and State-Feedback Control Design for Time-Delay Systems[END_REF]) For any finite s ∈ C and matrices

C k ∈ R p×n , A k ∈ R n×n and E 0 ∈ R n×m H(s) = N k=0 C k s k s N +1 I - N k=0 A k s k -1 E 0 =     C ′ 0 C ′ 1 . . . C ′ N     ′       sI -       0 I 0 • • • 0 0 0 0 I • • • 0 0 . . . . . . . . . . . . . . . . . . 0 0 0 • • • 0 I A 0 A 1 A 2 • • • A N -1 A N             -1       0 0 . . . 0 E 0       . (8)
Lemma 2. The transfer function ( 7), through the substitutions ( 4) and ( 5) can be written in an equivalent form as

H(s, λ) = A λ E C z 0 =         0 λI 0 N k=0 α k (0)A k N k=0 A k Γ k -λΓ λ E 0 N k=0 α k (0)C zk N k=0 C zk Γ k 0         , ( 9
) in which Γ k , Γ λ ∈ R n×N n are given by Γ k = [α k (1) α k (2) α k (3) • • • α k (N -1) α k (N )] ⊗ I, (10)
Γ λ = [α 0 (0) α 0 (1) α 0 (2) • • • α 0 (N -1)] ⊗ I, (11)
and α 0 (i), α k (i), for k = 0 and k ≥ 1, respectively, are given by

α 0 (i) = N i , (12)
α k (i) = k-1 ℓ=0 k -1 ℓ N -k + 1 i -ℓ (-1) i-ℓ . ( 13
)
Proof. Substituting the Rekasius expression (4) in ( 7), we get

H(s, λ) = C z0 + N k=1 C zk λ -s λ + s N -k+1 × × sI -A 0 - N k=1 A k λ -s λ + s N -k+1 -1 E 0 . (14)
Then, we can multiply H(s, λ) by (λ+s) N (λ+s) N to obtain

H(s, λ) = C z0 (λ + s) N + N k=1 C zk (λ -s) N -k+1 (λ + s) k-1 × × (sI -A 0 ) (λ + s) N - N k=1 A k (λ -s) N -k+1 (λ + s) k-1 -1 E 0 . ( 15
)
Expanding the binomials, the previous expression becomes

H(s, λ) = C z (s, λ)(A(s, λ)) -1 E 0 , (16)
where

Cz(s, λ) = C z0 N i=0 N i λ N-i s i + C z1 N i=0 N i λ N-i (-s) i + + C z2 N-1 i=0 N -1 i λ N-1-i (-s) i 1 ℓ=0 1 ℓ λ 1-ℓ s ℓ + • • • + C zN 1 i=0 1 i λ 1-i (-s) i N-1 ℓ=0 N -1 ℓ λ N-1-ℓ s ℓ = C z0 N i=0 N i λ N-i s i + N k=1 C zk N-k+1 i=0 k-1 ℓ=0 × × N + 1 -k i k -1 ℓ λ N-i-ℓ s i+ℓ (-1) i , (17)
and

A(s, λ) =(sI -A 0 ) N i=0 N i λ N -i s i - N k=1 A k N -k+1 i=0 k-1 ℓ=0 × × N + 1 -k i k -1 ℓ λ N -i-ℓ s i+ℓ (-1) i . ( 18
)
One can immediately see that the powers of s are in the interval [0 N ] and that the power of s and the power of λ always adds up to N . Hence, it is possible to group the terms that multiply the same power of s together

H(s, λ) = N i=0 Czi λ N -i s i × × s N +1 I - N i=0 Ãi λ N -i s i -1 E 0 , (19)
where

Czi = N k=0 C zk α k (i), ( 20
) Ãi = N k=0 A k α k (i) -λα 0 (i -1), (21)
where α k (i) is given by ( 12) when k = 0 and by (13) when k ≥ 1. Now, to apply Lemma 1, all we need to do is a similarity transformation on (8) using

L = diag(λ N I, λ N -1 I, • • • , λI, I). (22)
As Lemma 1 is applied to the transformed matrices, we observe that the terms depending on λ in (19) are cancelled. Finally, using ( 10)-( 13), ( 20) and ( 21) we achieve (9) which concludes the proof.

H ∞ Norm Calculation

We will now show how to approximate

T (s, τ ) ∞ = sup ω∈R σ(T (jω, τ )) ( 23
)
for a given τ ∈ [0, τ ⋆ ). The purpose is to show that the rational transfer function H(s, λ) can be successfully used for H ∞ norm calculation.

In the light of the results presented in [START_REF] Korogui | On a Rational Transfer Function-Based Approach to H ∞ Filter Design for Time-Delay Linear Systems[END_REF], we extract an important property relating the H ∞ norm for both the comparison system and the original time-delay one. To this end, we need to define the scalar λ o = inf{λ | A λ is Hurwitz}, which allows us to state the following theorem, extending Theorem 1 of [START_REF] Korogui | On a Rational Transfer Function-Based Approach to H ∞ Filter Design for Time-Delay Linear Systems[END_REF].

Theorem 1. Assume that N i=0 A i is Hurwitz and, for each λ ∈ (λ 0 , ∞), let α = arg sup ω∈R σ(H(jω, λ)),

and determine the time delay τ (λ, α) that satisfies α/λ = tan(ατ

/2N ). If τ (λ, α) ∈ [0, τ ⋆ ) then, H(s, λ) ∞ ≤ T (s, τ (λ, α)) ∞ . (25)
See [START_REF] Korogui | H ∞ Control Design for Time-Delay Linear Systems: A Rational Transfer Function Based Approach[END_REF] for the case N = 1. Similar arguments hold for N ≥ 2 using the Rekasius substitution (4).

OUTPUT FEEDBACK DESIGN

In this section we address the main problem of this work, the output-feedback design. Lets consider the following time-delay system with minimal realisation:

ẋ(t) = A 0 x(t) + M j=1 A j x (t -τ j ) + B 0 u(t) + E 0 w(t), z(t) = C z0 x(t) + M j=1 C zj x (t -τ j ) + D zu u(t), y(t) = C y0 x(t) + M j=1 C yj x (t -τ j ) + D yw w(t), (26)
where, in addition to the assumptions and the variables defined in previous sections, y(t) ∈ R p is the measured signal. The aim at this point is to design a full order dynamic output feedback controller with the following structure

ẋ(t) = Â0 x(t) + N k=1 Âk x (t -τ k ) + B0 y(t), u(t) = Ĉ0 x(t) + N k=1 Ĉk x (t -τ k ) , (27)
where x(t) ∈ R n for all t ∈ R + and N = hM for some h ∈ {1, 2, . . .}. We, once again, through a suitable change of indices and considering null the matrices where the respective delay is not present, rewrite (26) as

ẋ(t) = A 0 x(t) + N k=1 A k x (t -τ k ) + B 0 u(t) + E 0 w(t), z(t) = C z0 x(t) + N k=1 C zk x (t -τ k ) + D zu u(t), y(t) = C y0 x(t) + N k=1 C yk x (t -τ k ) + D yw w(t).
(28)

After connecting ( 27) to (28), we obtain

ξ(t) = F 0 ξ(t) + N k=1 F k ξ (t -τ k ) + G 0 w(t), z(t) = J 0 ξ(t) + N k=1 J k ξ (t -τ k ) , (29) where ξ(t) = [x(t) ′ x(t) ′ ] ′ ∈ R 2n
is the state and the indicated matrices stand for

F k = A k B 0 Ĉk B0 C yk Âk , J k = C zk D zu Ĉk , G 0 = E ′ 0 D ′ yw B′ 0 ′ . ( 30
)
The transfer function T C (s, τ ) from the external input w(t) to the controlled output z(t) becomes exactly (4) if with consider J k ← C zk , F k ← A k and J 0 ← E 0 where the subindex C indicates its dependence on a given controller of the form ( 27). Hence, the goal is to design a controller such that T C (s, τ ) ∞ < γ for a given γ > 0, which is accomplished by the definition of the following rational comparison system

H C (s, λ) = F λ G J 0 =         0 λI 0 N k=0 α k (0)F k N k=0 F k Γ k -λΓ λ G 0 N k=0 α k (0)J k N k=0 J k Γ k 0         . ( 31
)
With this system, we can solve the corresponding H ∞ output feedback design problem for each λ > 0 and extract the corresponding time-delay τ (λ). Note that, even though the matrices of the state space realisation of H C (s, λ) depend on an intricate manner of the control state space realisation matrices by applying the following similarity transformation

S =       I 0 0 0 0 0 I 0 0 I 0 0 0 0 0 I       , ( 32
)
one can rewrite (31) in the equivalent form

H C (s, λ) = SF λ S -1 SG JS -1 0 =   A λ B Ĉ E BC y Âλ BD yw C z D zu Ĉ 0   , (33)
where the system matrices (A λ , E, C z ) have been defined in (9),

B ′ = [0 B ′ 0 ], C y = N k=0 α k (0)C yk N k=0 C yk Γ k , (34)
and the controller matrices are given by

Âλ =    0 λI N k=0 α k (0) Âk N k=0 Âk Γ k -λΓ λ    , B = 0 B0 , Ĉ = N k=0 α k (0) Ĉk N k=0 Ĉk Γ k , (35)
indicating that they are in the comparison form. Hence, the controller (27) whenever connected to the time-delay system (28) produces an LTI comparison system associated to the regulated output (29) whose transfer function can be alternatively determined from the connection of the LTI comparison system of the system (28) and the LTI comparison system of the controller (27).

Given the particular structure of ( 35), we propose a strategy similar to the one presented in [START_REF] Korogui | H ∞ Control Design for Time-Delay Linear Systems: A Rational Transfer Function Based Approach[END_REF] such that the controller matrices ( Âλ , B, Ĉ) will be replaced by general matrix variables (A C , B C , C C ). These two realisations are coupled by a nonsingular matrix V ∈ R (k+1)n×(k+1)n which defines the similarity transformation

Âλ = V A C V -1 , (36) B = V B C , (37)
Ĉ = C C V -1 .
(38) These equalities hold under the conditions stated on the following Theorem. Theorem 2. V be a nonsigular matrix such that

vec(V ) ∈ ker   B ′ C ⊗ I 0 A ′ C ⊗ I 0 -I ⊗ 0 λI   (39) and 2n + n/k > q + 1. (40) Then, V satisfies ( Âλ , B, Ĉ) = (V A C V -1 , V B C , C C V -1 ). ( 41
)
Proof. From (39) we have that

  B ′ C ⊗ I 0 A ′ C ⊗ I 0 -I ⊗ 0 λI   vec(V ) = 0 (42)
Using de fact that vec(ABC) = (C ′ ⊗ A)vec(B), we can rewrite the matrix equality (42) into

I 0 V B C = 0 ( 43
)
and

I 0 V A C = 0 λI V (44)
The first equation ensures that the first kn rows of V B C are zero. Hence, we have knq equations. The second equation says that the first kn rows of V A C V -1 are in the form 0 λI . Hence, we have more kn(k + 1)n equalities. Together, those equations guarantee the desired form of (35) and imply that

((k + 1)n) 2 > knq + kn(k + 1)n, (45)
which can be easily simplified to (40). Therefore, V can be obtained from vec -1 (vec(V )).

To obtain the matrices A C , B C e C C we just solve the traditional LTI H ∞ problem for output-feedback. This can be achieved through Riccati equations [START_REF] Doyle | State Space Solutions to Standard H 2 and H ∞ Control Problems[END_REF] under the usual assumptions D ′ zu C z = 0, ED ′ yw = 0, D yw D ′ yw = I and D ′ zu D zu = I, or via LMIs such as in [START_REF] Gahinet | Explicit Controller Formulas for LMIbased H ∞ synthesis[END_REF]. Now, to finally recover the controller matrices we define

 = N k=0 α k (0) Âk N k=0 Âk Γ k , ( 46
)
where  is obtained from the n last rows of Âλ added to [0 Γ λ ], and

Γ =        α 0 (0) α 0 (1) • • • α 0 (N ) α 1 (0) α 1 (1) • • • α 1 (N ) . . . . . . . . . . . . α N (0) α N (1) • • • α N (N )        , (47)
which is non singular, see [START_REF] Cardeliquio | Stability Analysis and State-Feedback Control Design for Time-Delay Systems[END_REF]. Thus, we may recover the desired matrices as follows

Â0 Â1 • • • ÂN = Â Γ ⊗ I -1 , ( 48
) Ĉ0 Ĉ1 • • • ĈN = Ĉ Γ ⊗ I -1 , ( 49
)
and B0 is immediately obtained from B.

Once we have the controller matrices at hand, it is a simple matter of computation to determine whether T C (s, τ (λ)) ∞ < γ holds, see [START_REF] Fioravanti | A Numerical Method for Stability Windows and Unstable Root-locus Calculation for Linear Fractional Time-delay Systems[END_REF] and [START_REF] Avanessoff | H ∞ -Stability analysis of (fractional) delay systems of retarded and neutral type with the Matlab Toolbox YALTA[END_REF].

EXAMPLE

To illustrate the results for output feedback design we consider a second order example borrowed from (Fridman and Shaked, 2002a) and [START_REF] Korogui | H ∞ Control Design for Time-Delay Linear Systems: A Rational Transfer Function Based Approach[END_REF] where the matrices corresponding to the state space realisation (28) are as follows

A 0 A 1 E 0 = 0 0 -1 -1 0 1 0 0 1 0 -0.9 1 1 0 , B 0 C z0 C z1 D zu = 0 0 1 0 0 0 1 0 0 0 0 0.1 , C y0 C y1 D yw = 0 1 0 0 0 0.1 .
We can now solve two distinct problems, the maximum delay problem and the minimum norm problem. In the first one, for a fixed pre-specified H ∞ level γ, we find the output-feedback controller that maximise the delay. In the second one, for a fixed pre-specified maximum delay τ , we find the output-feedback controller matrices that minimise the H ∞ level γ. In both cases, T (s, τ ) is stable and T (s, τ ) ∞ ≤ γ.

To illustrate the first problem, lets set γ = 1. Using N = 1 in the expansion for the comparison system, we achieve for the maximum delay τ = 1.2324. This result and behaviour of both norms, T c (s, τ (λ)) and H c (s, λ) , as a function of τ is exactly the same as in [START_REF] Korogui | H ∞ Control Design for Time-Delay Linear Systems: A Rational Transfer Function Based Approach[END_REF]. However, increasing the expansion by using N = 2 and N = 3 we get for the maximum delay τ = 1.4268 and τ γ = 1.5117 respectively. Besides the fact that we increased the maximum delay allowed by a factor of 22%, we also have, that for every 0 < τ < τ γ , the norm of the comparison system is the same as the norm of the system with delays as depicted in Figure 1. This results can be better visualised in the table below. We have obtained a sequence of stabilising controllers for each pair (λ N ,τ (λ N )) such that λ N ∈ (λ γ , ∞) and τ (λ N ) ∈ [0, τ γ ). Now, setting τ = 1. We get T c (s, τ (λ)) = 0.2010 which is 26% smaller than the H ∞ norm obtained by [START_REF] Korogui | H ∞ Control Design for Time-Delay Linear Systems: A Rational Transfer Function Based Approach[END_REF] and 76% smaller than the H ∞ norm obtained by [START_REF] Fridman | ∞ Control of Linear State-delay Descriptor systems: an LMI Approach[END_REF]. We also have exactly

CONCLUSION

This work is an extension of [START_REF] Cardeliquio | Stability Analysis and State-Feedback Control Design for Time-Delay Systems[END_REF]. This time, we extended the procedure for time-delay control design based on a comparison system, obtained by Rekasius substitution, to implement output-feedback. To the best of the authors knowledge, this is the first procedure able to better use the buffer necessary for implementing delayed output-feedback, and obtaining simultaneously more stability margin and lower H ∞ level.

  delay T c (s, τ (λ)) = H c (s, λ) = 0.2675. (50)

  Fig. 1. H ∞ performance versus time delay for γ = 1 the same norm for the comparison system, H c (s, λ) = 0.2010. Finally, the controller matrices for this case are

	0.27
	0.265
	0.26
	0.255
	0.25
	0.245
	0.24
		0	0.2	0.4	0.6	0.8	1	1.2	1.4	1.6
						τ [s]
	Â0 Â1 =	-15.1593 18.5286 -11.8869 -0.6430 0.8165 9.5743 1.2467 -1.7115	,
	Â2 Â3 =	0.7977 -2.8727 -1.2294 -1.1746 -1.4215 2.7861 1.2287 1.6388	,
	Ĉ′ 0	Ĉ′ 1 =	39.1349 -5.6235 -24.8696 4.4252	,
	Ĉ′ 2	Ĉ′ 3 =	-1.1655 3.0810 7.2716 2.7257	,
	B0 = -2.0019 6.2982

′ .