P Finet

B Gibaud

O Dameron

R Le Bouquin Jeannès

Interoperable Infrastructure and Implementation of a Health Data Model for Remote Monitoring of Chronic Diseases with Comorbidities

Keywords: Telemedicine, Interoperability, Health data model

To adopt a common health data model compatible with chronic diseases and their comorbidities. • To implement an interoperable telemedicine platform. • Data structure of our health data model based on HL7 CDA (Clinical Document Architecture). • Context-aware generic model suitable for most acquisition devices.

Introduction

The ageing of the population is associated with the development of chronic diseases [START_REF] Finet | Review of current telemedicine applications for chronic diseases. Toward a more integrated system?[END_REF], which were responsible for 36 of the 57 million deaths worldwide in 2008 [START_REF]Global status report on non communicable diseases[END_REF]. The United Nations estimated that this category is expected to reach 406 million by 2050 [START_REF]World population prospects: the 2006 revision[END_REF]. The aging of the population will result in an increase of the number of chronic diseases with comorbidity factors [START_REF] Mathers | Global burden of disease in 2002: data sources, methods and results[END_REF]. For example, compared with people who do not have diabetes, the diabetic patients have a higher risk of cardiovascular morbidity. Type 2 diabetes is associated with a two-fold to fourfold increased risk of coronary artery disease, and a twofold to eight-fold increased risk of heart failure [START_REF] Martín-Timon | Type 2 diabetes and cardiovascular disease: have all risk factors the same strength?[END_REF]. Chronic diseases typically require regular follow-up and are therefore expected to have a strong impact on the medical organization of care and on the cost for society. This is further exacerbated by co-morbidities. The use of telemedicine facilitates patient follow-up outside of the hospital. Telemedicine applications can contribute to reduce healthcare costs by reducing the number of hospital consultations and transports. However, most existing telemedicine projects focus on a single chronic disease and few actors. In such cases, comorbidities are usually not explicitly considered. In fact, taking comorbidities into ac-count requires the ability to share medical data among health care information systems. For having access to care anywhere and anytime with telemedicine, it is necessary to create a fully interoperable infrastructure [START_REF] Craft | Toward technical interoperability in telemedicine[END_REF]. The expected benefits of such an architecture are two-fold: first, avoid the redundancy of medical information systems as isolated islands, and second, enable chronic disease telemedicine applications to take into account parameters from the comorbidities. After reviewing communication standards, it also seemed important to define the contents of patient data to share with the medical personnel in order to ensure that the provided information is sufficient for clinical diagnosis.

The aim of our project is to devise an interoperable telemedicine system suitable for monitoring article consists in identifying a model of data structure that meets the medical needs of remote monitoring for several chronic diseases with various medical devices. This led us to propose in a second part a new implementation of interoperable telemedicine systems which allows healthcare professionals to share patient information.

Materials and method

To analyze patient's data, health professionals need to access the context description (e.g. information about the type of examination), the important background information (e.g. the type of collected measurements from medical devices and the date and the time of the measurements) and the acquisition context (e.g. sensor characteristics).

Furthermore, if ex-changed information is limited to raw data captured by patients, it is not possible to interpret it meaningfully. Patient's data are context-dependent [START_REF] Baas | To-wards a context model for human-centered design of contextual data en-try systems in healthcare domain[END_REF], and measurement results (weigh, blood pressure, oxygen saturation oxygen, etc.) have different meanings depending on the time of measurement [START_REF] Baas | To-wards a context model for human-centered design of contextual data en-try systems in healthcare domain[END_REF]. They cannot be properly interpreted by a remote medical staff without specific contextual information. In this case, we define a health data model available for different chronic diseases and containing the necessary information for the vital signs analyzed. Our health data model must be able to provide the medical needs for several chronic diseases. To improve our health data model, an environment should be implemented to share and exchange patient's data in order to facilitate cooperation between healthcare professionals. As HL7 Clinical Document Architecture (CDA) [START_REF] Dolin | The HL7 clinical document architecture[END_REF] is the appropriate standard for sharing medical documents, we decided to use its structure to build our health data model. To achieve our goal, we must communicate all data of our health data model from patient's data to the remote computer system. In this case, the telemedicine systems must be fully interoperable from the technical (between two different technology systems), syntactic (between two different communication systems) and semantic points of view.

In order to address the challenges of fully interoperable sys-tem for information sharing and sufficient context information for remote diagnosis, we propose the use of standard data ex-change formats, interoperable services and standard transport protocols to send structured data to a remote location addresses. To verify our system modeling, we perform the mapping between data of our health data model and the data models from the communication standards used. Laboratory experimentations have enabled to validate our modeling system for the following sensors: a blood pressure monitor, a pulse oximeter and a weighing scale. These three sensors allow us to obtain all possible configurations of our health data model. In fact, the weighing scale DIM model has only one numeric object, whereas the blood pressure monitor DIM model and the pulse oximeter DIM model have two numeric objects. A laboratory trial gave us the opportunity to demonstrate interoperability between the sensors and the smartphone, based on the ISO/IEEE 11073 family of standards [START_REF] Aravind | Developing software for IEEE 11073 device specializations using antidote library[END_REF]. To test the medical data exchange, we have specified a HL7 CDA compliant document structure for collecting several vital signs. We have tested this document structure with the Gazelle platform tool1 [START_REF] Boufahja | Model-based analysis of HL7 CDA R2 conformance and requirements coverage[END_REF].

Proposed telemedicine system

Conception of the health data model

To define a health data model suitable for telemedicine projects, we selected an appropriate modeling framework from the international standard HL7 Clinical Document Architecture (CDA) [START_REF] Dolin | The HL7 clinical document architecture[END_REF]. The aim of this standard which is derived from the HL7 Reference Information Model (RIM) [START_REF] Dolin | The HL7 clinical document architecture[END_REF] is to share inter-operable clinical documents between healthcare professionals. This standard supports acquisition, transfer and exchange of both qualitative and quantitative data captured in a telemedicine context. The CDA R2 version includes structured elements in the document header and in the document body [START_REF] Ferranti | The clinical document architecture and the continuity of care record: a critical analysis[END_REF]. This type of documents may include several sections that contain human readable narrative forms or codified structures for an automatic processing. Thus, it contains health data that can be easily integrated into databases of healthcare facilities [START_REF] Dolin | The HL7 clinical document architecture[END_REF]. With the last version of CDA, the body text sections include Fig. 1. CDA structure codified entries to recover external data (Fig. 1) [START_REF] Ferranti | The clinical document architecture and the continuity of care record: a critical analysis[END_REF]. The implementation of a CDA document requires to select an existing model that contains templates and rules sets. Templates are designed to create standardized clinical documents that are specifically intended to support clinical workflows in various use cases [START_REF]HL7 implementation guide: S&I framework transitions of care companion guide to consolidated-CDA for meaningful use stage 2, release 1 -US realm[END_REF]. For our telemedicine project and our health data model, we chose a CDA document model which aims to get vital signs: the "Personal Healthcare Monitoring Report" (PHMR) [START_REF]HL7 implementation guide for CDA release 2: Personal Healthcare Monitoring Report (PHMR)[END_REF]. This type of document contains different templates and values. For each medical device used at the patient's home, the creation of the health context model consists of describing variables, constants and codes which are present in the CDA header, in a CDA section, in a CDA subsection or in a predefined entry. To define the context of the data within the health data model, we have used information contained within section of CDA documents that contain collections of vital signs. We have re-lied, on the one hand, on implementation guides that deal with patient measurement data generated by medical devices, and on the other hand, on the Health Information Systems Interoperability Framework (HIS-IF) by ASIP. The selected implementation guides are the "Continuity of Care Document" (CCD) [START_REF]HL7 implementation guide: CDA release 2 -Continuity of Care Document (CCD), standard specification for Continuity of Care Record (CCR)[END_REF], the PHMR [START_REF]HL7 implementation guide for CDA release 2: Personal Healthcare Monitoring Report (PHMR)[END_REF], as well as the document provided by ASIP "CI-SIS Couche Contenu Volet Structuration_Minimale" [START_REF] Santé | Cadre d'Interopérabilité SIS -couche contenuvolet modèle de contenu CDA[END_REF]. These documents identified the relevant information related to vital signs: the measurement descriptions, the various nomenclature codes, the codes for measurement units and the date and time (cf. Fig. 2). In order to include all the data necessary in the health data model, we need sensor data identification to ensure traceability. Our health data model also contains a section with sensor information. The body of our health data model consists of two sections: one entitled "medical equipment" to describe the sensor used [START_REF]HL7 implementation guide for CDA release 2: Personal Healthcare Monitoring Report (PHMR)[END_REF][START_REF]HL7 implementation guide: CDA release 2 -Continuity of Care Document (CCD), standard specification for Continuity of Care Record (CCR)[END_REF] and another section entitled "Vital signs measurement" to display patient's vital signs taken at a specific time. The "Medical equipment" section contains all the information required for identifying the sensor: the manufacturer's name, the model, the sensor type nomenclature, its identifier or its serial number. The "Vital signs measurement" section has one or more predefined entries according to the number of vital signs measured by the sensor [START_REF]HL7 implementation guide for CDA release 2: Personal Healthcare Monitoring Report (PHMR)[END_REF][START_REF]HL7 implementation guide: CDA release 2 -Continuity of Care Document (CCD), standard specification for Continuity of Care Record (CCR)[END_REF]. Indeed, some medical equipment can analyze two vital signs or more (e.g. blood pressure and pulse rate for a blood pressure monitor) [START_REF] Santé | Cadre d'Interopérabilité SIS -couche contenuvolet modèle de contenu CDA[END_REF]. In such cases, the health data model has several entries in the same section which correspond to different measured vital signs. Each en-try also contains the date and time of the self-measurement, the measurement's type nomenclature code and the measurement unit. Moreover, some vital sign may require several measurements. In HL7 CDA document, all measurements required to obtain the vital sign are linked by the HL7 element "entry relationship" [START_REF]HL7 implementation guide for CDA release 2: Personal Healthcare Monitoring Report (PHMR)[END_REF][START_REF] Dolin | HL7 clinical document architecture, release 2[END_REF]. At all stages of patient's data transfer, all data of the health context model must be communicated to the different receivers.

Interoperability of the telemedicine systems

To guarantee quality and safety of patient's care our telemedicine application combines three different systems: (1) the patient system for the medical monitoring and patient selfmeasurements, (2) the data processing and archiving system, which is generally located in the hospital and (3) the data transmission system between the two structures. These three systems describe the workflow of the patient's data from his home to the hospital and must be interoperable. Continua Health Alliance (CHA) is a non-profit organization that promotes standard data exchange formats, integration profiles and standard transport protocols. The Guidelines of the CHA [START_REF] Wartenaf | Continua: the impact of a personal telehealth ecosystem[END_REF] help to ensure interoperability between all the components of the three systems of our telemedicine architecture, based on international standards and Integrating the Health-care Enterprise (IHE) technical frameworks. To guarantee plug & play capability, the CHA prescribes for the patient system the use of the ISO/IEEE 11073 standards family [START_REF] Wartenaf | Continua: the impact of a personal telehealth ecosystem[END_REF] for communication between medical devices and application hosting devices, such as mobile phones and set-top boxes. For the data transmission system, an IHE profile and the Health Level 7 (HL7) V2.6 [START_REF] Frohner | Development of an Android app in compliance with the continua health alliance design guidelines for medical device connectivity in health[END_REF] standard is used to transfer securely health data from patient's home to health professionals. The IHE DEC (Device Enterprise Communication) profile defined in the IHE PCD (Patient Care Device) technical frame-work allows a point-to-point communication between a hosting device and a remote server [START_REF]IHE patient care device (PCD) technical framework[END_REF]. A HL7 v2.6 message is transmitted to the remote server based on the information contained in the hosting device. For the data processing and archiving sys-tem, IHE has proposed the XDS (Cross-enterprise Document Sharing) profile Fig. 2. The health context model of vital sign measurement. [START_REF] Duftschmid | The EHRARCHE project: satisfying clinical information needs in a shared electronic health record system based on IHE XDS and archetypes[END_REF], which comes from the IHE IT Infrastructure technical framework (ITI TF) [START_REF] Duftschmid | The EHRARCHE project: satisfying clinical information needs in a shared electronic health record system based on IHE XDS and archetypes[END_REF]. This profile describes how to share medical documents appropriately. It specifies the transactions supporting the registration, distribution and access to shared documents between healthcare facilities [START_REF] Duftschmid | The EHRARCHE project: satisfying clinical information needs in a shared electronic health record system based on IHE XDS and archetypes[END_REF]. Fig. 3 summarizes the different steps of data transport by the three interoperable systems with the use of communication standards, standard health data exchange formats and integration profiles.

Models and data structure based on the communication standards

To represent data and to define data access, the ISO/IEEE 11073 family of standards provides models containing objects and attributes. They help us to describe the data reception and transfer processes from one system to another. The system model of the ISO/IEEE standard 11073-20601 is divided into three main components: the domain information model (DIM), the service model, and the communication model [START_REF] Korsakov | On demand plugins for X73-PHD manager[END_REF]. These objects and their attributes represent the elements that control the behavior of the

The DIM model

For the patient system interoperability and the trans-

Models comparison

To verify the first step of transport of all structured data of the medical device (data transport with the ISO/IEEE standards), we analyzed the relation between the DIM data model and our health context model. The aim of this study was to verify the appropriate mapping of all components between the two models (see Table1). The only difference between these models was the use of different nomenclature systems for medical terms. To achieve semantic interoperability of the telemedicine application, it was required to elaborate a mapping between the ISO/IEEE 11073-10101 numeric codes and the equivalent LOINC term(s) [22]. About sensor specific items, the DIM model from ISO/IEEE 11073 standards, the HL7 V2.6 standard and the HL7 CDA R2 standard [10a] all contain the following items: the manufacturer's name, the sensor model, a unique identifier and a serial number [START_REF]IHE patient care device (PCD) technical framework[END_REF]22,[START_REF] Dolin | HL7 clinical document architecture, release 2[END_REF]. All these data are communicated by the sensor itself [START_REF]Continua design guidelines, version[END_REF].

The health data model

The

HL7 V2.6 message

To transfer the health context model data from the patient's home to a remote location, the IHE DEC profile advises the use of a HL7 v2.6 message which contains patient's information in encoding syntax based on segments [START_REF]IHE patient care device (PCD) technical framework[END_REF]. This type of message has two main characteristics: it can be sent without solicitation from the remote location and its structure covers all observations and results which come from the patient's home. The name of the message type is "ORUˆR01ˆORU_R01" [START_REF]IHE patient care device (PCD) technical framework[END_REF]. It consists of several optional or mandatory data segments: the Message Header (MSH), The Observation Result segment (OBX) and the Observation Request segment (OBR).

The MSH defines the identification of message, the sender and receiver, the message type, and some specifics of the syntax of a message [START_REF]IHE patient care device (PCD) technical framework[END_REF]. The OBX is used to transmit a single observation or observation fragment [23]. All results of patient's measurements should be contained in OBX segments. The third component is the observation Request segment (OBR). It contains the re-quest of the medical act (ordering information) and the context for observation (i.e., whether the request was done in-clinic or remote). When a set of observations is ordered, the order message contains an OBR segment [START_REF]The HL7 version 2.6 standard; definitive version[END_REF]. Some fields in the OBR segment only apply to the ordering message.

For remote monitoring systems, the message structure of "ORUˆOR01ˆORUˆR01" is suitable to transmit data between the patient's home and a remote health care facility [START_REF]IHE patient care device (PCD) technical framework[END_REF]. In the message header, the patient's identification and contact information may be transmitted in the Patient Identification (PID) segment. All results of patient's measurements are contained in OBX segments. The identification of the device will be present in an OBX segment. In this case, the suffix of the OBX-3-observation identifier is DEV [START_REF]The HL7 version 2.6 standard; definitive version[END_REF]. In the OBR-4 of the OBR segment, we have the identifier codes for the requested patient's measurements. For the transfer of the message, it is advised to use a secure standard protocol such as HTTPS [START_REF]IHE patient care device (PCD) technical framework[END_REF]. The HL7 message sent from the patient's home allows the patient's data to be processed and stored on a remote server. When a patient's measurement threshold is exceeded, the data processing and archiving system must be able to generate and display alerts or to indicate the actions to be implemented in case of emergency. In this case, a CDA document can be created.

CDA document

The CDA document can be automatically generated by an information system and made accessible by medical professionals. The document sharing management system can be built with the XDS profile functional architecture [START_REF] Duftschmid | The EHRARCHE project: satisfying clinical information needs in a shared electronic health record system based on IHE XDS and archetypes[END_REF]. This profile describes appropriate sharing of medical documents. It specifies the transactions supporting the registration, distribution and access to shared documents between healthcare facilities [START_REF] Duftschmid | The EHRARCHE project: satisfying clinical information needs in a shared electronic health record system based on IHE XDS and archetypes[END_REF]. With the IHE XDS profile, sending and receiving clinical documents can be achieved with standard communication protocols as HTTP or HTTPS [24]. The created CDA documents consist of a header and a body, that include structured elements in both parts of the CDA documents. With the CDA R2, the body may contain health encoded data that can be easily integrated into databases of healthcare facilities. This ensures the interoperability between clinical systems and data integration of all parts of our proposed health data model. For implementation of a CDA document, we have selected an existing model that contains templates, rule sets and value sets for vital signs: PHMR [START_REF]HL7 implementation guide for CDA release 2: Personal Healthcare Monitoring Report (PHMR)[END_REF].

The implementation guides for CDA [START_REF]HL7 implementation guide for CDA release 2: Personal Healthcare Monitoring Report (PHMR)[END_REF][START_REF]HL7 implementation guide: CDA release 2 -Continuity of Care Document (CCD), standard specification for Continuity of Care Record (CCR)[END_REF][START_REF] Santé | Cadre d'Interopérabilité SIS -couche contenuvolet modèle de contenu CDA[END_REF] contain templates that address specific uses. They can represent professional recommendations, or national clinical practice guidelines.

To optimize our model, we selected an implementation guide with minimal CDA structure "Minimal structuration of medical documents" [START_REF] Santé | Cadre d'Interopérabilité des SIS couche contenu, volet structuration minimale de documents médicaux[END_REF]. For the proposed CDA document header, it is required to add only one template "assigned Authoring Device" for the identification of the sensor model [START_REF]HL7 implementation guide for CDA release 2: Personal Healthcare Monitoring Report (PHMR)[END_REF][START_REF]HL7 implementation guide: CDA release 2 -Continuity of Care Document (CCD), standard specification for Continuity of Care Record (CCR)[END_REF][START_REF] Santé | Cadre d'Interopérabilité SIS -couche contenuvolet modèle de contenu CDA[END_REF]. As with the health model data, the proposed CDA document consists of two sections. One of which is called "Medical Equipment" and the other "Patient vital signs" [START_REF]HL7 implementation guide for CDA release 2: Personal Healthcare Monitoring Report (PHMR)[END_REF][START_REF]HL7 implementation guide: CDA release 2 -Continuity of Care Document (CCD), standard specification for Continuity of Care Record (CCR)[END_REF]. The "Medical Equipment" section contains the sensors characteristics described in the health data model [START_REF]HL7 implementation guide for CDA release 2: Personal Healthcare Monitoring Report (PHMR)[END_REF][START_REF]HL7 implementation guide: CDA release 2 -Continuity of Care Document (CCD), standard specification for Continuity of Care Record (CCR)[END_REF]. In the "Patient signs" section, each measured vital sign is introduced as a predefined entry. All measurements required to obtain the vital sign are described ac-cording to the "observation" template [START_REF]HL7 implementation guide for CDA release 2: Personal Healthcare Monitoring Report (PHMR)[END_REF][START_REF]HL7 implementation guide: CDA release 2 -Continuity of Care Document (CCD), standard specification for Continuity of Care Record (CCR)[END_REF][START_REF] Santé | Cadre d'Interopérabilité SIS -couche contenuvolet modèle de contenu CDA[END_REF].

Experiments in progress

Laboratory experimentations have enabled to validate this health data model for the following sensors: a blood pressure monitor UA-767PBT, A&D Company Ltd, a pulse oximeter 3150 Wirstworn, Nonin Medical Inc, and a weighing scale UC-321PBT, A&D Company Ltd. They are all CHA certified 2 . These three sensors provide all possible configurations of our health data model: the weighing scale DIM model has only one numeric object,

2
The list of CHA certified medical devices is presented on the following website: http://www.pchalliance .org /certified -productshowcase.

whereas the blood pressure monitor DIM model and the pulse oximeter DIM model have two numeric objects. For the weighing scale and the pulse oximeter, only one measurement is sufficient to obtain the vital sign. By contrast, the blood pressure vital sign is composed of several measurements (the systolic and diastolic blood pressure measurements). The three sensors are provided by two different manufacturers (A&D Company Ltd and Nonin medical). In a laboratory trial, an open source implementation Antidote software [START_REF] Aravind | Developing software for IEEE 11073 device specializations using antidote library[END_REF] provides an opportunity to achieve interoperability between the sensors and the smartphone which are compliant with the ISO/IEEE 11073 family of standards [START_REF] Aravind | Developing software for IEEE 11073 device specializations using antidote library[END_REF].

Various communication tests of vital signs have been conducted with the three sensors to prove the interoperability of the patient system. We also checked the data completeness for a proper remote interpretation. To test the data transfer to a re-mote system, we used a function of the Antidote software [START_REF] Aravind | Developing software for IEEE 11073 device specializations using antidote library[END_REF] which allows to send the patient's data by e-mail. To test the medical data exchange, we have developed one HL7 CDA document which collects several vital signs. We have tested this document validity with the Gazelle platform tool [START_REF] Boufahja | Model-based analysis of HL7 CDA R2 conformance and requirements coverage[END_REF]. The first results of the experiments prove that implementing interoperable infrastructure for the three systems of our telemedicine application is achievable.

Discussion

A fully interoperable infrastructure of a telemedicine system and health data model provides a Telemedicine Systems Interoperability Framework for the monitoring of chronic diseases. They cover the needs of patients suffering from one or several chronic diseases. Currently, only research work on the relationship between the DIM of the IEEE standard 11073 family and the RIM which is the source of CDA have been done [START_REF] Yuksel | Interoperability of medical device information and the clinical applications: an HL7 RMIM based on the ISO/IEEE 11073 DIM[END_REF]. These works contribute to achieve an interoperable telemedicine system. They enable data transmission from only a medical device (internally-implanted device: a cardiac defibrillator, or a pacemaker) to a medical application software by sending a HL7 V3 message. To build the message HL7 V3 con-tent, the link between both models (DIM and RIM) allows to get data from the implanted device with ISO IEEE 11073 standards. Our research provides an interoperable infrastructure of a telemedicine system at patient's home for chronic disease monitoring. The list of usable medical devices at patient's home corresponds to the equipment described in specialization standards of the ISO/IEEE 11073 (ISO/IEEE 11073-104zz) [22]. All these medical devices address the needs of patients for several chronic diseases. Despite this, this list contains only simple devices. No medical device is able to deliver medical wave-forms, such as electrocardiogram for chronic heart failure or spirometry waveform for chronic respiratory failure.

Likewise, our proposed health data model is not suitable for this type of medical device. In fact, the DIM of this medical device type [START_REF]IEEE. Std 11073-10201 health informatics -point-of-care medical device communication -part 10201: domain information model[END_REF] is different and includes other objects for modeling of the real-time collection of data. To be close to real-time communication, these devices must in specific cases continuously send data. In such cases, they must be equipped with alarm systems. Alarms are thus generated if the curve exceeds one or several thresholds fixed by the medical team. IHE proposed a trial implementation about the inclusion of waveform data in IHE PCD profiles: Waveform Content Module (WCM). This technical framework supplement describes a method near real time to send waveform data through HL7 V2 messages [START_REF]IHE patient care device (PCD) technical framework supplement, waveform content module (WCM)[END_REF]. This guide also promotes WCM model for the description of the data structure and semantics to be used for communication of waveforms which follows the IEEE 11073 DIM. It provides attributes which are similar to that of the IEEE 11073 Real Time SA object [START_REF]IHE patient care device (PCD) technical framework supplement, waveform content module (WCM)[END_REF]. They are used to describe, for example, the waveform type, the curve settings, such as sampling rate, resolution, encoding and data range and information on alarms. To be able to transmit waveforms, the health data model of medical devices must contain the same information as the WCM model [START_REF]IHE patient care device (PCD) technical framework supplement, waveform content module (WCM)[END_REF]. For the communication of medical waveforms, the medical equipment type requires another patient system configuration. In fact, to be close to real-time communication, medical devices must have the ability to send a message approximately every second [START_REF]IHE patient care device (PCD) technical framework supplement, waveform content module (WCM)[END_REF]. In this case, it is necessary to have broad-band access to avoid the network congestion and to have a speed of at least 128kbit/s [START_REF] Norris | Low-bandwidth, lowcost telemedicine consultations in rural family practice[END_REF]. As the minimal speed is 384kbit/s, a standard broadband network (such as ADSL or3G) meets the requirements of the patient system for the communication of medical waveforms. On the other hand, these medical devices must also have additional modules for the reception and processing of the patient's data. They must be equipped with alarm systems. Alarms are thus generated if the curve exceeds one or several thresholds fixed by the medical team. Furthermore, such facilities are costly to introduce. Depending on the level of patient disease, real-time remote continuous monitoring can improve through the early detection of worsening of the disease and symptoms. For example, to detect cardiac arrhythmias, some continuous cardiac monitoring can provide automatic wireless transmission of abnormal ECG waveforms at the time of event, from the patient's home [START_REF] Anderson | New methodologies in arrhythmia monitoring[END_REF]. This system for the most high-risk patients can reduce the risk of sudden death (with the implantation of a pacemaker or cardiac defibrillator) [START_REF] Anderson | New methodologies in arrhythmia monitoring[END_REF]. The problem is the lack of interoperability of this system with other medical devices and hospital information systems. The use of WCM data model is to improve the integration of this medical device type in a technology platform in patient's home. The increase of home care should contribute to a continuation of this work.

Conclusion and perspectives

Telemonitoring is a key element for at home preventive care of vulnerable population with chronic health conditions. The data collected at the patient's home must be exhaustive to sup-port adequate interpretation and follow up of vital signs and medical data exchange between healthcare professionals. We propose an implementation of a health data model to support adequate interpretation and to facilitate medical data exchange between healthcare professionals. We have modeled an inter-operable solution for the three systems of telemedicine applications. This ecosystem promotes the use of the ISO/IEEE 11073 standards family for communication between medical devices and computer systems, and the use of HL7 standards and of IHE integration profiles for exchanging clinical data among information systems. To extend the implementation of most complex medical equipment, the proposed health data model of medical devices must contain other modules to describe the new functions.

Fig. 3 .

 3 Fig.3. The data communication. of our data structure model, each of the installed sensors must support the ISO/IEEE 11073 standards. The first step is to describe the DIM to analyze its objects and attributes which number of physiological measurements to exchange and on the device status at the host device [22]. These components are essential items of the communication protocol between the sensor and the hosting device. The most important object is the Medical Device System (MDS) [22]. It represents the properties and services of the medical device. The attributes of the MDS object allow to identify the device, to describe its technical characteristics and state. Besides the MDS object, there are Persistent Metric Store (PMstore) objects and other objects (zero or more per object type) which are derived from the metric class [22]. These different objects are numeric objects which represent episodic measurements, Real Time Sample Array (RT-SA) objects which represent continuous samples or waveforms, enumeration objects which represent event annotations and PMstore which provides a persistent storage mechanism [22]. The medical devices at patient's home do not necessitate internal storage memory. All vital signs are transmitted automatically after acquisition. Consequently, the "Persistent Metric Store" and the "Permanent metric segment" objects [22] are not required. The proposed generic DIM model for all sensors at patient's home comprises two types of objects: one MDS object and one or more numeric objects (depending on the number of measured vital signs: cf. Fig.4) [22].

Fig. 4 .

 4 Fig. 4. DIM model for sensors at patient's home.

The vital sign requires only one measurement CDA body : • Vital signs measurement section: Entriesx [1 by n] :

		The vital sign requires several measurements
	CDA body :
	• Vital signs measurement section: [1 by n • Date and time of the	Date and time of the measurement		Absolute-Time-Stamp	MDC_ATTR_ID_ABS et MDC_ATTR_TIME_STAMP_ABS	Attribute included in numeric sign vitalx object
	vital signx measurement
	CDA body :					Code included in
	• Vital signs measurement					numeric sign vitalx
	section: Entriesx [1 by n] • Date and time of the vital signx measurement	Nomenclature code of vital sign x measurement	Type	MDC_ATTR_ID_TYPE	object (with nomenclature: ISO/IEEE 11073-10101)
	CDA body : • Vital signs measurement				DIM model
	Location field in the health data model section: Entriesx [1 by n] • Relationship between the analysed vital sign with:	Item in the health data model	Attribute name	Attribute Identification	Attribute included Location field in the model DIM in numeric sign vitalx object. This
	CDA HEADER : • Sensor model Identifier CDA body : • Equipment section: • Nomenclature code of the medical device type 0 by nx performed measurement y, linked by each other by « entryrelationship » element: • Nomenclature code of measurement y (y • measurement y value (y varies from de 0 to nx)	Model and manufacturer System-Model Nomenclature code of the medical device type System-Type List of different Nomenclature codes of the Metric-Id-List different measurements to obtain the vital signs	MDC_ATTR_ID_MODEL MDC_ATTR_SYS_TYPE MDC_ATTR_ID_PHYSIO_LIST	Attributes included in MDS object Attribute included in MDS object (with nomenclature: ISO/IEEE 11073-10101) attribute is used when a compound value is used. The order of the metric-Id-List is the same than the order of the compound observed value
	varies from de 0 to nx CDA body : • Equipment section: • Model and manufacturer CDA body : • Equipment section: CDA body : • Vital signs measurement section: Entriesx [1 by n] • vital signx measurement unit	Model and manufacturer System-Model Identifier or/and serial System-Id Measurement unit Unit-Code	MDC_ATTR_ID_MODEL MDC_ATTR_SYS_ID MDC_ATTR_UNIT_CODE	Attribute included in MDS object Code included in numeric sign vitalx object (with nomenclature: ISO/IEEE 11073-10101)
	• Identifier or/and Serial number	number		Production-Specification Table1 (continued) MDC_ATTR_ID_PROD_SPECN
	CDA body : • Equipment section: • Date and time	Date and time		Date and time	MDC_ATTR_TIME_ABS	Attributes included in MDS object
						Attribute included
	• Date and time of the vital signx measurement	Date and time of the measurement	Absolute-Time-Stamp	MDC_ATTR_TIME_STAMP_ABS	in numeric sign vitalx object defines the date and time of observation
	CDA body : • Vital signs measurement					Code included in numeric sign vital
	section: Entriesx [1 by n] • Nomenclature code of vital signx measurement	Nomenclature code of vital sign x measurement		Type	MDC_ATTR_ID_TYPE	object (with nomenclature: ISO/IEEE 11073-10101)
	CDA body : • Vital signs measurement section: Entriesx [1 by n] • vital signx measurement value	Measurement value	Simple-Nu-Observed-value or Basic-Nu-Observed-value or Nu-Observed-value	MDC_ATTR_NU_VAL_OBS_SIMP or MDC_ATTR_NU_VAL_OBS_BASIC or MDC_ATTR_NU_VAL_OBS	Attribute included in numeric sign vitalx object defines the measurement value.
	CDA body : • Vital signs measurement					Code included in numeric sign vital
	section: Entriesx [1 by n] • vital signx measurement unit	Measurement unit		Unit-Code	MDC_ATTR_UNIT_CODE	object (with nomenclature: ISO/IEEE 11073-10101)
		Table1: Comparison between the health context model and DIM.

Gazelle is an open source platform that allows a wide set of tools to test information exchange.

Acknowledgements

We would like to thank Dr Mohammad HAYDAR, cardiologist in Alençon, for his willingness to take part in this study, the AZNnetwork company for its participation in experimentation and Eric Poiseau (INRIA) for his assistance in the choice of CDA implementation and test tools.

Conflict of interest statement

The authors have not declared any conflicts of interest.


Ghazanfar Asadi
email: gasadi@ece.neu.edu

Mehdi B Tahoori
email: mtahoori@ece.neu.edu

An Accurate SER Estimation Method Based on Propagation Probability

In this paper, we present an accurate but very fast soft error rate (SER) estimation technique for digital circuits based on error propagation probability (EPP) computation. Experiments results and comparison of the results with the random simulation technique show that our proposed method is on average within 6% of the random simulation method and four to five orders of magnitude faster.

Introduction

Soft errors are intermittent malfunctions of the hardware that are not reproducible [START_REF] Nguyen | A Systematic Approach to SER Estimation and Solutions[END_REF]. These errors, which occur more often than permanent errors, arise from Single Event Upsets (SEU). These SEUs, in turn, arise from energetic particles, namely neutrons and alpha particles. Soft Error Rate (SER) for a device is defined as the error rate due to SEUs. So far, memory elements have been more susceptible to soft errors than the combinational logic. However, analytical models predict that the SER in the combinational logic will be comparable to that of memory elements by 2011 [START_REF] Shivakumar | Modeling the Effect of Technology Trends on the Soft Error Rate of Combinatorial Logic[END_REF]. The first step in developing soft error reliable designs with minimum performance and area penalties is to accurately estimate system SER and the contribution of each component to the overall soft error vulnerability.

The error rate of a circuit node, ni, is broken into three terms and computed as RSEU (ni) × P latched (ni) × P sensitized (ni) [START_REF] Mohanram | Cost-Effective Approach for Reducing Soft Error Failure Rate in Logic Circuits[END_REF]. RSEU (ni) is the bit-flip rate at node ni which depends on the particle flux, the energy of the particle, type and size of the gate, and the device characteristics. P latched (ni) is the probability that an erroneous value on node ni is captured in a flip-flop. P sensitized (ni) is the probability that node ni is functionally synthesized by the input vectors to propagate the erroneous value from the error site to primary outputs (POs) or flip-flops (FFs). Estimating the last parameter is the most time-consuming part since in this step, several random vectors are applied to the circuit inputs to determine the Error Propagation Probability (EPP) from an error site to outputs. All previous SER estimation methods use the random vector simulation approach [START_REF] Maheshwari | Techniques for Transient Fault Sensitivity Analysis and Reduction in VLSI Circuits[END_REF][START_REF] Mohanram | Cost-Effective Approach for Reducing Soft Error Failure Rate in Logic Circuits[END_REF][START_REF] Nguyen | A Systematic Approach to SER Estimation and Solutions[END_REF][START_REF] Shivakumar | Modeling the Effect of Technology Trends on the Soft Error Rate of Combinatorial Logic[END_REF]. The SER estimation time of a node in large circuits exponentially increases with the size of the circuit. Hence, SER estimation of larger circuits becomes intractable with these techniques.

In this paper, we present a new EPP computation technique based on circuit topological traversal and signal probabilities. This paper is organized as follows. Sec. 2 presents our EPP computation technique. Sec. 3 presents the experimental results. Finally Sec. 4 concludes the paper.

Gate-level SER Estimation

We consider all circuit nodes as possible error sites. In our approach, we first extract the structural paths from each error site to all reachable outputs. Then, we traverse these paths to compute the propagation probability of the erroneous value from the error site to reachable primary outputs or flip-flops. An on-path signal is a net on a path from the error site to a reachable output. An on-path gate is defined as the gate with at least one on-path input. Finally, an off-path signal is a net that is not on-path and is an input of an on-path gate. These three are shown in Fig. 1.

For EPP calculation, as we traverse the paths, we use signal probability for off-path signals and use our propagation probability rules for on-path signals. The signal probability (SP) of a line l indicates the probability of l having logic value "1" [START_REF] Parker | Probabilistic Treatment of General Combinational Networks[END_REF]. If there is only one path from the error site to an output, the error propagation probability from an on-path input of a gate to its output depends on the type of the gate and the signal probability of other off-path signals.

In the general case in which reconvergent paths might exist, EPP from the error site to the output of the reconvergent gate depends on the polarities of the propagated error on the on-path signals, as well. To address this issue, we need error propagation rules for reconvergent gates. First, we define the following parameters:

• Pa(Ui) and Pā(Ui) are defined as the probabilities of the output of node Ui being a and ā, respectively. (a is an erroneous values and ā is the inverted of a). In other words, Pa(Ui) (Pā(Ui)) is the probability that the erroneous value is propagated from the error site to Ui with an even (odd) number of inversions.

• P1(Ui) and P0(Ui) are the probabilities of the output of node Ui being 1 and 0, respectively. In these cases, the error is blocked and not propagated. Note that for an on-path signal Ui, P (Ui) = Pa(Ui) + Pā(Ui) + P1(Ui) + P0(Ui) = 1, while for an off-path signal Uj, P (Uj) = P1(Ui)+P0(Ui) = 1. Since we have considered the polarity of error propagation, this will take care of reconvergent fanouts. EPP computation rules for elementary gates are shown in Table 1.

Consider the example shown in Fig. 1. Assume that an SEU with sufficient energy hits gate A. After computing P (E) = 1(ā), P (G) = 0.7(ā) + 0.3(0), and P (D) = 0.2(a) + 0.8(0)1 , we follow these steps for EPP calculation. On-Path Gates: Darkened gates

Figure 1. EPP calculation on reconvergent paths

For a general case, the following algorithm shows how we can extract and then traverse all paths from a given error site to all reachable outputs and how we apply the EPP rules as we traverse the paths.

For every node, ni, do:

1. Path Construction: Extract all on-path signals (and gates) from ni to every reachable primary output P Oj and/or flip-flop F F k using the forward Depth-First Search (DFS) algorithm [START_REF] Cormen | Introduction to Algorithms[END_REF].

2. Ordering: Levelize signals on these paths using the topological sorting algorithm [START_REF] Cormen | Introduction to Algorithms[END_REF].

EPP Computation:

Select the on-path gates in a topological order, from the error site to reachable outputs, and apply propagation rules (Table 1) for EPP computation. Using a topological order enable us to compute EPP in just one pass (linear time complexity).

After completing the above steps, Pa(P Oj) and Pā(P Oj) are computed for every P Oj reachable from ni. P sensitized (ni) is calculated as follows:

P sensitized (ni) = 1 - k j=1 1 -(Pa(P Oj) + Pā(P Oj))
, where k is the number of outputs reachable from ni.

Experimental Results

The proposed approach was implemented and applied to ISCAS'89 benchmark circuits using a DELL Precision 2 shows the results for our systematic approach as well as the random simulation for selected circuits (due to space limitations). For larger circuits, a limited number of gates of the circuits are simulated due to exorbitant run time of the random-simulation method. The speedups of our approach are reported with and without including the SP computation time in the total execution time. When SP time is excluded, the speedups are 4-5 orders of magnitude. When included, our approach is still 2-3 orders of magnitude faster than the random simulation method. The accuracy of our approach versus random-simulation is 94%, in average.

Conclusions

In this paper, an accurate error propagation probability computation technique for soft error rate estimation has been developed. The proposed approach leverages the signal probability calculation, which is already used in other steps of the design flow. This technique can be used to identify the most vulnerable components to be protected by soft error hardening techniques.

  (Xi) + Pa(Xi)] -P1(out) Pā(out) = n i=1 [P1(Xi) + Pā(Xi)] -P1(out) P0(out) = 1 -[P1(out) + Pa(out) + Pā(out)] (Xi) + Pa(Xi)] -P0(out) Pā(out) =n i=1 [P0(Xi) + Pā(Xi)] -P0(out) P1(out) = 1 -[P0(out) + Pa(out) + Pā(out)] NOT P1(out) = P0(input), Pa(out) = Pā(input) Pā(out) = Pa(input) , P0(out) = P1(input)

Table 1 .

 1 EPP calculation rules for elementary gates

	P 0 (H) = P 0 (C) × P 0 (D) × P 0 (G) = 0.7 × 0.8 × 0.3 = 0.168
	Pa(H) = (0.7) × (0.2 + 0.8) × (0.3) -0.168 = 0.042
	Pā(H) = (0.7) × (0.8) × (0.7 + 0.3) -0.168 = 0.392
	P 1 (H) = 1 -(0.168 + 0.042 + 0.392) = 0.398
	→ P(H) = 0.042(a) + 0.392(ā) + 0.168(0) + 0.398(1)
		off-path signals
		SP B =0.2		SP C =0.3
	SEU	B	C
		erroneous			PO
		value (a)	D	On-Path	H
	A			Signals
			E	G
		F
			SP F =0.7

Table 2 .

 2 Our approach vs. random simulation

	Circuit	SysT	SimT	%Dif	SPT	ISP	ESP
	s953	0.354	28.3	4.3	150	74.4	79950
	s1196	0.750	54.6	3.6	313	92.2	72800
	s1238	0.532	36.9	3.4	207	90.3	69510
	s1423	2.230	53.1	3.9	250	138.5	23810
	s1488	0.425	7.3	4.4	14	316.3	17220
	s1494	0.704	10.8	4.4	22	303.7	15480
	s9234	9.368	817.2	11.3	4659	970.8	87230
	s15850	34.18	972.1	12.6	5270	1695	28440
	s35932	7.020	1904	4.5	9648	3133	271240
	s38584	13.860	2317	7.1	12833	3405	167180
	s38417	14.180	2412	6.0	12951	3480	170126
	average	3.243	325.0	5.4	110.7	549.1	93072
	SysT: Our approach run time(ms),SimT: Rand-Simul. run time(s)
	Dif.: Difference of our approach vs. random simulation
		SPT: Signal probability computation time (s)
	ISP: Speedup including SP time, ESP: Speedup excluding SP time
	450 c system equipped with 2 GB memory. Table

This means: Pa(D) = 0.2, and P 0 (D) = 0.8

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE


Arne Hamann
email: hamann|ernst@ida.ing.tu-bs.de

Rolf Ernst

TDMA Time Slot and Turn Optimization with Evolutionary Search Techniques

In this paper we present arithmetic real-coded variation operators tailored for time slot and turn optimization on TDMA-scheduled resources with evolutionary algorithms. Our operators implement a heuristic strategy to converge towards the solution space and are able to escape local minima. Furthermore, we explicitly separate the variation of the admitted loads and the turn-length in order to give the designer increased control over the optimization process. Experimental results show that our variation operators have advantages over string-coded binary variation operators which are frequently used to solve continuous optimization problems.

I. INTRODUCTION

Design space exploration for heterogeneous MpSoC or distributed systems is a tedious task due to many design parameters with very different effects. Parameter selection is difficult enough for discrete design parameters, such as task priorities, but becomes even more challenging for continuous parameters, such as TDMA timing.

One popular approach in walking through the search space is the use of evolutionary search techniques. However, their effectiveness strongly depends on the coding of the problem variables as well as the used crossover and mutation operators.

While for discrete and permutation problems efficient coding techniques and variation operators are known to achieve good solutions, continuous optimization problems, like TDMA time slot assignment, challenge the searchpower of string-coded binary evolutionary algorithms.

In this paper we propose arithmetic real-coded variation operators tailored for time slot and turn optimization on TDMA-scheduled resources. Thereby, our strategy of walking through the search space is split into two aspects: optimizing the admitted loads of the mapped tasks as well as optimizing the TDMA turn-length. Both factors together define the quality of a time slot assignment. According to these two important factors we introduce four variation operators. One crossover and one mutation operator that vary the admitted loads of the mapped tasks while letting the turn-length constant as well as one crossover and one mutation operator that vary the turn-length and make sure that the admitted loads of the tasks stay constant.

The crossover operators implement a heuristic strategy of converging towards solutions lying "between" individuals currently considered by the evolutionary algorithm, whereas the mutation operators serve to break out of local minima by increasing or decreasing the admitted loads and the turn-length, respectively, within certain limits.

For experiments, this approach is used for local optimization of TDMA-scheduled resources within a design space exploration framework for global optimization of heterogeneous MpSoC and distributed systems [START_REF] Hamann | Design Space Exploration and System Optimization with SymTA/S -Symbolic Timing Analysis for Systems[END_REF].

II. DESIGN SPACE EXPLORATION FRAMEWORK

Figure 1 shows the design space exploration loop performed in our framework [START_REF] Hamann | Design Space Exploration and System Optimization with SymTA/S -Symbolic Timing Analysis for Systems[END_REF]. The Optimization Controller is the central element. It is connected to scheduling analysis and to an evolutionary multi-objective optimizer. Scheduling analysis checks the validity of a given system parameter set, that is represented by an individual, in the context of the overall heterogeneous system. The evolutionary multi-objective optimizer is responsible for the problem-independent part of the optimization problem, i.e. elimination of individuals and selection of interesting individuals for variation. Currently, we use SPEA2 (Strength Pareto Evolutionary Algorithm 2) [START_REF] Zitzler | SPEA2: Improving the Strength Pareto Evolutionary Algorithm[END_REF] for this part, which is coupled via PISA (Platform and Programming Language Independent Interface for Search Algorithms) [START_REF] Bleuler | PISA -a platform and programming language independent interface for search algorithms[END_REF].

Fig. 1 -EXPLORATION FRAMEWORK Different parameters of a system, such as time slots or priorities, are encoded on separate chromosomes. The user selects a subset of all parameters for optimization. The chromosomes of these parameters form an individual and are included in the evolutionary optimization while all others are fixed and immutable. The variation operators of the evolutionary algorithm are applied chromosomewise for these individuals. More details on the optimization system can be found in [START_REF] Hamann | Design Space Exploration and System Optimization with SymTA/S -Symbolic Timing Analysis for Systems[END_REF].

In this paper we explain in detail one possible search parameter in our exploration framework, the time slot assignment on TDMA-scheduled resources. The results are, however, applicable beyond this exploration system.

The remainder of this paper is structured as follows. After an overview of related work, we introduce the proposed variation operators which are used within the framework to optimize the time slot assignments of tasks mapped on TDMA-scheduled resources. By means of extensive experiments we then compare the new operators with binary-coded single-point crossover and binary-coded mutation.

III. RELATED WORK

There is a large body of work in the area of design space exploration and optimization of heterogeneous MpSoC and distributed systems. In the following we give a small overview of approaches for the optimization of different system parameters as well as frameworks allowing to explore given systems at different levels of abstraction.

The approach described in [START_REF] Thiele | A framework for evaluating design tradeoffs in packet processing architectures[END_REF] introduces an analysis technique to estimate end-to-end packet delays and queuing memory in network processor architectures. Based on this information a measure is defined to characterize the performance of such architectures under different usage scenarios. By means of design space exploration paretooptimal architectures are searched trading good performance under several usage scenarios versus cost. In [START_REF] Maxiaguine | Rate analysis for streaming applications with on-chip buffer constraints[END_REF] the authors treat the reverse problem. Instead of determining worst-case buffer requirements and output stream properties for given input streams and scheduling policies, the authors search for the input stream rates that can be supported by a given stream processing architecture without violating on-chip buffer constraints. The authors propose the integration of this technique into a tool for automated design space exploration for fast performance evaluation of different stream processing architectures.

[3] presents a heuristic algorithm for priority assignments in distributed hard real-time systems to optimize end-to-end deadlines. The algorithm iteratively decomposes the global deadlines into artificial local deadlines and then assigns deadline monotonic priorities on each resource. This approach is thus not applicable to more general priority assignments or other types of scheduling policies.

The approach in [START_REF] Pop | Design optimization of multi-cluster embedded systems for real-time applications[END_REF] focuses on bus access optimization (TDMA and static priority preemptive) in multi-cluster embedded systems interconnected via gateways. Thereby, the application structure is feed-forward. Optimization objectives are end-to-end deadlines. The authors propose a partitioning and mapping heuristic and a heuristic adjusting TDMA slot sizes in time-triggered clusters. For the priority assignments in event-triggered clusters a heuristic presented in [START_REF] Garcia | Optimized priority assignment for tasks and messages in distributed real-time systems[END_REF] is used.

[4] describes the Platune framework allowing performance and power tuning of a specific parameterized SoC platform. For a given application to be mapped on the target SoC, Platune determines all sets of architectural parameter values representing pareto-optimal solutions regarding power and performance. The detection of all pareto-optimal solutions is achieved effectively by clustering the search space into independent parts, for which pareto-optimal solutions can be determined separately.

The Spacewalker [START_REF] Snider | Automated design space exploration for embedded computer systems[END_REF], part of the PICO project from HP Labs, pursuits a similar approach. For given applications, it searches for pareto-optimal embedded systems. The search space is explored using a divide-and-conquer approach. In the first step different subsystem are explored independently. From the sets of obtained pareto-optimal subsystems, global systems are constructed and evaluated. This hierarchical exploration approach seems to work well for the architecture presented in the paper. However, for performance dependent subsystems the combination of local pareto-optima rarely leads to global pareto-optima.

The Sesame framework, part of the Artemis [START_REF] Pimentel | Exploring embedded-systems architectures with Artemis[END_REF] project, is used in [START_REF] Erbas | A Multiobjective Optimization Model for Exploring Multiprocessor Mappings of Process Networks[END_REF] to tackle the mapping decision problem of complex applications on heterogeneous embedded systems. The authors use evolutionary techniques to search for solutions which are pareto-optimal regarding maximum processing time, power consumption and total cost. These solutions are then input to a simulation framework for further evaluation. An interesting aspect in this approach is the explicit distinction of pareto-optimal individuals and pareto-optimal individuals fulfilling given constraints. By this means a possible convergence of the evolutionary optimizer towards a set of pareto-optimal infeasible solutions is prevented.

IV. TDMA TIME SLOT CHROMOSOME

The search space of all time slot assignments for the tasks on a TDMA-scheduled resource is very large, even if we fix the turn-length and the arithmetic precision. Turn-length variation, which is often necessary to find good solutions, adds another search dimension. Since it is unrealistic to try all possible time slot assignments and turn-lengths, a good strategy to walk through the search space is indispensable. In this section we first motivate our choice for the coding of the problem parameters. Then we present the algorithms, i.e. creation of initial population (section IV-B) and variation operators (section IV-C), of the TDMA time slot chromosome used by our exploration framework to walk through the search space of TDMA time slot assignments.

A. Representation of the Chromosome

There are at least two basically different possibilities for coding parameters in continuous optimization problems for the use with an evolutionary algorithm: discretizing the search space into a power of 2 and using a binary string representation, or using a real number representation.

Encoding the problem parameters as real numbers seems to be a suitable approach because of the value dynamic which is appropriate for a continuous optimization problem. We decided to use arithmetic variation operators, as mutation or crossover on the floating point representation has drastic effects even beyond the "hamming cliff" problem of binary encoding.

B. Initial population

For the creation of the initial population we specify an initial TDMA turn-length turn init . Note that choosing a sub-optimal initial turn-length for the initial population does not lead to the incapability of the time slot chromosome to find valid solutions because the variation operators proposed in section IV-C are capable of adapting the turn-length in the course of optimization. Nevertheless, if the designer chooses a good initial turn-length the chromosome converges faster towards the solution space.

Let R be a TDMA scheduled resource subjected to optimization with the tasks T 0 ,...,T k-1 mapped on it. The worst-case execution time, i.e. assuming no interrupts, of T i is denoted by WCET i , its activating period by period i and the length of its time slot by slot i . In the following we refer to a specific time slot assignment as individual and to the set of individuals used by the evolutionary algorithm as population.

In order to create only valid (i.e. resource not overloaded, etc.) individuals for the initial population, we have to ensure that for each task T i its maximum load load max;i does not exceed its admitted load load adm;i .

load adm;i ≥ load max;i ⇔ slot i turn init ≥ WCET i period i ⇔ slot i ≥ WCET i period i * turn init
This implies for T i a minimum time slot

slot min;i = WCET i period i * turn init .
Algorithm 1 is used to create the initial population which is uniformly distributed in the search space of all valid time slot assignments with a turn-length of turn init . To do so, it randomly distributes the initial turn to the tasks T 0 ,...,T k-1 . It respects above mentioned minimum time slot length to prevent the creation of non-schedulable individuals.

Algorithm 1 (Create valid initial individual) .

Input:

initial turn-length turn init minimum time slots slot min;0 ,...,slot min;k-1 Output: valid time slot assignment for T 0 ,...,T k-1

1. f ree = turn init ; 2. set = {0, 1,...,k -1}; 3. while (set = / 0) { 4. choose random r ∈ set; 5. set = set \ r; 6. if (set = / 0) slot r = f ree; 7.
else { 8.

slot max = f ree -∑x ∈ set slot min;x ; 9.

slot r = random(slot min;r , slot max ); 10.

f ree = f reeslot r ; 11. } 12. }

C. Variation Operators

The quality of a time slot assignment on a TDMAscheduled resource is determined by two factors: the admitted loads of the mapped tasks and the turn-length. According to these two problem parameters we introduce in this section two real-coded crossover and two realcoded mutation operators for the time slot optimization on TDMA-scheduled resources. While one crossover and mutation operator, respectively, varies the admitted loads of the mapped task and holds the turn-length constant, the other crossover and mutation operator, respectively, varies the turn-length and leaves the admitted loads untouched.

Thereby, the two crossover operators implement a heuristic strategy to converge towards the solution space, whereas the mutation operators serve to break out of local minima by decreasing or increasing the problem parameters by up to a configurable maximum percentage.

The reason for separating these two problem parameters is the increased control over the optimization process. By configuring the probabilities for the use of the two different operator types for crossover and mutation, the designer can decide which of them is the preferred search parameter. In the extreme case, she can, for example, hold the turn-length constant and optimize only by varying the admitted loads. Note that for the experiments performed in section V, both types of operators are used with the same probability, giving the evolutionary algorithm maximum freedom in walking through the search space.

1) Crossover Operators: Algorithm 2 describes the crossover operator varying the admitted loads while letting the turn-length constant. As input it takes two parent individuals from which it creates two offsprings. Its optimization strategy is related to a binary search method.

The admitted loads of the offsprings are placed evenly (i.e. at 1 3 and 2 3 ) in the respective admitted load interval defined by the two parents. The time slots of offsprings 1 and offspring 2, respectively, are then calculated according to the turn-length given by parent 1 and parent 2, respectively.

Figure 2(a) gives an example for this crossover operator. The crossover operator varying the turn-length is described by algorithm 3. It also pursuits a binary search related strategy. Given the two parent individuals it calculates their average turn-length (lines 1-7). Offspring 1 and offspring 2, respectively, is then created by adapting the time slots of parent 1 and parent 2, respectively, to the average turn-length letting the admitted loads untouched (lines 8-11). turn p 1 = turn p 1 + slot p 1 ;i ; 5.

Algorithm 2 (Crossover Admitted Load)

turn p 2 = turn p 2 + slot p 2 ;i ; 6. } 7. turn new = (turn p 1 + turn p 2 )/2; 8. for

(i = 0; i <= k -1; i = i + 1) { 9.
slot o 1 ;i = slot p 1 ;i /turn p 1 * turn new ; 10.

slot o 2 ;i = slot p 2 ;i /turn p 2 * turn new ; 11. } (a) Admitted Load Crossover (b) Turn Crossover Fig. 2 -CROSSOVER OPERATORS 2) Mutation Operators: The crossover operators described in section IV-C.1 lead to the convergence of the obtained time slot assignments towards (locally) optimal solutions contained "between" individuals considered by the evolutionary algorithm. Of course, it is possible that the variety of the initial population is insufficient to find good solutions only by using these crossover operators. Additionally, the exploration may get stuck in a local optimum, without the possibility to reach globally better solutions.

In this section we introduce two mutation operators, enabling the evolutionary algorithm to break out of local optima and to reach parts of the search space not yet considered.

The mutation operator varying the admitted load while letting the turn-length constant is described by algorithm 4. As input it takes one parent individual from which it creates one offspring. After initialization, r 2 pairs of tasks are chosen (line 6-7). For each of these pairs the first task gives a part of its disposable time slot (i.e. the time slot it can dispense without overloading the resource) to the second (lines 8-13). The percentage of the disposable time slot dispensed is randomly chosen in the interval ]0, d max ], where d max is configurable. Figure 3(a) shows the functionality of this mutation operator by means of an example.

Algorithm 4 (Mutate Admitted Load)

; i <= k -1; i = i + 1) { 3.
slot o;i = slot p;i ; 4.

turn p = turn p + slot p;i ; 5. } 6. choose pair random r ∈ [2,...,k]; 7. choose r distinct integers q 0 ,...,q r-1 ∈ [0, k -1]; 8. for (i = 0; i <= r -

1; i = i + 2) { 9.
slot disposable = slot p;q iload max;q i * turn p ; 10.

choose random double d applied ∈ ]0, d max ]; 11.

slot o;q i = slot o;q id applied * slot disposable ; 12.

slot o;q i+1 = slot o;q i+1 + d applied * slot disposable ; 13. } Algorithm 5 describes the mutation operator varying the turn-length. First the target turn-length is chosen, by increasing or decreasing the turn-length of the parent by a percentage randomly chosen in the interval ]0, d max ], where d max is configurable (lines 1-7). The offspring's time slot assignments are then calculated to sum up in the target turn-length without altering the admitted loads given by the parent's time slot assignment (lines 8-9).

Figure 3(b) shows the functionality of this mutation operator for a turn-length reduction of 20 %. The experiments are conducted with our exploration framework [START_REF] Hamann | Design Space Exploration and System Optimization with SymTA/S -Symbolic Timing Analysis for Systems[END_REF] using SPEA2 (Strength Pareto Evolutionary Algorithm 2) [START_REF] Zitzler | SPEA2: Improving the Strength Pareto Evolutionary Algorithm[END_REF] as selector. The initial population is constructed according to algorithm 1 described in section IV-B with an initial turn-length turn init = 10. The operators varying the admitted loads and the operators varying the turn-length are used with the same probability. For the mutation operators we use d max = 40%.

Algorithm 5 (Mutate Turn)

We conduct three different experiments. In the first experiment we compare both approaches regarding the time needed to find a solution for random task sets. In the second and third experiment we investigate their convergence in the search for valid solutions for systems with global constraints.

A. Needed time to find a solution

In the first experiment we compare the binary-coded operators with the proposed real-coded operators regarding the time, expressed by the number of evaluated individuals, they need to find a working time slot assignment. We use random task sets containing 10 tasks with the following attributes:

• Activating period P between 200 and 600 time units • Jitter J between 10 and 400 time units

• Minimum distance between successive events within bursts d between 0 and 100 time units

• Core execution time between 5 and 15 time units • Constraint 100 + 10 * core execution time Figure 4 shows the average results of 100 evaluated random task sets. Compared to the binary-coded operators, the proposed real-coded operators perform approximately 33, 5% better in the average case. In the second experiment we take into account the 3 task sets described in table I. Each task in each system is constrained by a hard deadline given in table II. We assume that all tasks within a system are mapped on the same TDMA-scheduled resource. Note that the systems are chosen so that it is easiest to find a working time slot assignment for system 1, whereas system 3 is the most difficult to optimize.

We perform an optimization loop of 30 generation each containing 100 individuals. Thereby we use the following optimization objective:

minimize 9 ∑ i=0 1.5 R i -D i ,
where R i , resp. D i , denotes the response time, resp. the deadline, of task T i .

During optimization we are interested in the best individual after each generation. This gives us an idea of how fast the compared operators converge to working time slot assignments. Figures 5(a We observe that the binary variation operators perform well in the first few generations, whereas they stagnate in later ones, leading to a slow convergence against the solutions space. The new operators converge slower in the beginning but sustain a steady improvement in later generations.

The new operators perform much better for all 3 example systems. Particularly with regard to system 3 we see a big difference in the quality of the obtained results. Where the binary-coded operators do not reach an average fitness value below 10 8 , the proposed realcoded operators perform six orders of magnitude better in the average case. We will see in section V-C that the performance difference between the two operator sets grows with increasing difficulty to optimize a given system (which is e.g. caused by narrow deadlines).

C. Needed time to find a solution: narrow deadlines

In the last experiment we compare the binary-coded operators with the proposed real-coded operators regarding their performance in optimizing a system with narrow hard deadlines. Fig. 5 -EVOLUTION OF BEST SOLUTION Therefore, we consider the task set described in table III. We perform several optimization runs, whereas we tighten the constraints of the tasks in each of them (table IV). We measure the time, expressed as number of evaluated individuals, until the first solution is obtained.

Figure 6 shows the average results obtained by 20 optimization runs per constraint set.

We observe that the binary-coded as well as the proposed real-coded operators have more difficulties in finding working individuals as the deadlines decrease, which is not surprising. However, the binary-coded operators need comparatively more time to find working time slot assignments. Thereby, the performance difference between the binarycoded and the proposed real-coded operators is increasing with decreasing deadlines. VI. CONCLUSION In this paper we have presented arithmetic real-coded variation operators, which can be used in conjunction with an evolutionary algorithm to optimize time slot assignments and turn-lengths on TDMA-scheduled resources. Our operators implement a heuristic strategy to converge towards the solution space and are able to escape local minima. One special characteristic of our approach is the separated variation of the turn-length and the admitted loads of the mapped tasks, giving the designer increased control over the optimization process.

Extensive experiments using synthetic applications have shown that the proposed variation operators are superior to standard binary-coded operators, in respect of time needed to find valid time slot assignments for given systems. Thereby, the performance difference is particularly noticeable for systems with narrow deadlines.

The approach presented in this paper was recently integrated in our exploration framework for global optimization of heterogeneous MpSoC and distributed systems [START_REF] Hamann | Design Space Exploration and System Optimization with SymTA/S -Symbolic Timing Analysis for Systems[END_REF]. In future we will further investigate its performance in combination with other system parameters in the optimization of large systems with complex performance dependencies.

Algorithm 3 (

 3 Figure 2(b) visualizes the functionality of this crossover operator by means of an example. Crossover Turn) . Input: time slots of parent p 1 : [slot p 1 ;0 ,...,slot p 1 ;k-1 ] time slots of parent p 2 : [slot p 2 ;0 ,...,slot p 2 ;k-1 ] Output: time slots of offspring o 1 : [slot o 1 ;0 ,...,slot o 1 ;k-1 ] time slots of offspring o 2 : [slot o 2 ;0 ,...,slot o 2 ;k-1 ] 1. turn p 1 = 0; 2. turn p 2 = 0; 3. for (i = 0; i <= k -1; i = i + 1) { 4.

  Input: time slots of parent p: [slot p;0 ,...,slot p;k-1 ] max. % of disposable time slot dispensed: d max Output: time slots of offspring o: [slot o;0 ,...,slot o;k-1 ] 1. turn p = 0; 2. for (i = 0

  Fig. 3 -MUTATION OPERATORS V. EXPERIMENTAL RESULTS In this section we compare the variation operators introduced in section IV-C with binary-coded single-point crossover and binary-coded mutation operator.The experiments are conducted with our exploration framework[START_REF] Hamann | Design Space Exploration and System Optimization with SymTA/S -Symbolic Timing Analysis for Systems[END_REF] using SPEA2 (Strength Pareto Evolutionary Algorithm 2)[START_REF] Zitzler | SPEA2: Improving the Strength Pareto Evolutionary Algorithm[END_REF] as selector. The initial population is constructed according to algorithm 1 described in section IV-B with an initial turn-length turn init = 10. The operators varying the admitted loads and the operators varying the turn-length are used with the same probability. For the mutation operators we use d max = 40%.We conduct three different experiments. In the first experiment we compare both approaches regarding the time needed to find a solution for random task sets. In the second and third experiment we investigate their convergence in the search for valid solutions for systems with global constraints.

Fig. 4 -

 4 Fig. 4 -AVERAGE NUMBER OF TESTED INDIVIDUALS TO FIND A SOLUTIONB. Convergence towards the solution spaceIn the second experiment we take into account the 3 task sets described in table I. Each task in each system is constrained by a hard deadline given in table II. We assume that all tasks within a system are mapped on the same TDMA-scheduled resource. Note that the systems are chosen so that it is easiest to find a working time slot assignment for system 1, whereas system 3 is the most difficult to optimize.We perform an optimization loop of 30 generation each containing 100 individuals. Thereby we use the following optimization objective:

  ), 5(b) and 5(c) give an overview of the average results obtained by 50 optimization runs per system.

Fig. 6 -

 6 Fig. 6 -AVERAGE NUMBER OF TESTED INDIVIDUALS TO FIND A SOLUTION -DECREASING DEADLINES

TABLE I -

 I EXAMPLE SYSTEMS WITH 10 TASKS

		T0	T1	T2	T3	T4	T5	T6	T7	T8	T9
	System 1	180 110 185 100 120 110 100 120 90 115
	System 2	100 105 125 78	85	75 105 95 200 120
	System 3	110 140 115 145 180 140 200 120 140 100

TABLE II -

 II CONSTRAINTS OF EXAMPLE SYSTEMS

TABLE IV -

 IV DECREASING DEADLINES

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

Proceedings of the Design, Automation and in Europe Conference and Exhibition (DATE'05)

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05)