Formal verification of safety protocol in train control system

In order to satisfy the safety-critical requirements, the train control system (TCS) often employs a layered safety communication protocol to provide reliable services. However, both description and verification of the safety protocols may be formidable due to the system complexity. In this paper, interface automata (IA) are used to describe the safety service interface behaviors of safety communication protocol. A formal verification method is proposed to describe the safety communication protocols using IA and translate IA model into PROMELA model so that the protocols can be verified by the model checker SPIN. A case study of using this method to describe and verify a safety communication protocol is included. The verification results illustrate that the proposed method is effective to describe the safety protocols and verify deadlocks, livelocks and several mandatory consistency properties. A prototype of safety protocols is also developed based on the presented formally verifying method.

Extended formulations, nonnegative factorizations, and randomized communication protocols

An extended formulation of a polyhedron P is a linear description of a polyhedron Q together with a linear map π such that π(Q)=P. These objects are of fundamental importance in polyhedral combinatorics and optimization theory, and the subject of a number of studies. Yannakakis’ factorization theorem (Yannakakis in J Comput Syst Sci 43(3):441–466, 1991) provides a surprising connection between extended formulations and communication complexity, showing that the smallest size of an extended formulation of $$P$$P equals the nonnegative rank of its slack matrix S. Moreover, Yannakakis also shows that the nonnegative rank of S is at most 2^c, where c is the complexity of any deterministic protocol computing S. In this paper, we show that the latter result can be strengthened when we allow protocols to be randomized. In particular, we prove that the base-2 logarithm of the nonnegative rank of any nonnegative matrix equals the minimum complexity of a randomized communication protocol computing the matrix in expectation. Using Yannakakis’ factorization theorem, this implies that the base-2 logarithm of the smallest size of an extended formulation of a polytope P equals the minimum complexity of a randomized communication protocol computing the slack matrix of P in expectation. We show that allowing randomization in the protocol can be crucial for obtaining small extended formulations. Specifically, we prove that for the spanning tree and perfect matching polytopes, small variance in the protocol forces large size in the extended formulation.

On the performance limits of slotted CSMA/CA in IEEE 802.15.4 for broadcast transmissions in wireless sensor networks

The IEEE 802.15.4 has been adopted as a communication protocol standard for Low-Rate Wireless Private Area Networks (LRWPANs). While it appears as a promising candidate solution for Wireless Sensor Networks (WSNs), its adequacy must be carefully evaluated. In this paper, we analyze the performance limits of the slotted CSMA/CA medium access control (MAC) mechanism in the beacon-enabled mode for broadcast transmissions in WSNs. The motivation for evaluating the beacon-enabled mode is due to its flexibility and potential for WSN applications as compared to the non-beacon enabled mode. Our analysis is based on an accurate simulation model of the slotted CSMA/CA mechanism on top of a realistic physical layer, with respect to the IEEE 802.15.4 standard specification. The performance of the slotted CSMA/CA is evaluated and analyzed for different network settings to understand the impact of the protocol attributes (superframe order, beacon order and backoff exponent), the number of nodes and the data frame size on the network performance, namely in terms of throughput (S), average delay (D) and probability of success (Ps). We also analytically evaluate the impact of the slotted CSMA/CA overheads on the saturation throughput. We introduce the concept of utility (U) as a combination of two or more metrics, to determine the best offered load range for an optimal behavior of the network. We show that the optimal network performance using slotted CSMA/CA occurs in the range of 35% to 60% with respect to an utility function proportional to the network throughput (S) divided by the average delay (D).

Building a person home behavior model based on data from smart house sensors 2015

Dissertação para a obtenção do grau de Mestre em Engenharia Electrotécnica Ramo de Energia

Environmental/Regatta Buoy: Telemetry and Configuration

A monitorização ambiental é essencial para a tomada de decisões tanto na ciência como na indústria. Em particular, uma vez que a água é essencial à vida e a superfície da Terra é composta principalmente por água, a monitorização do clima e dos parâmetros relacionados com a água em ecossistemas sensíveis, tais como oceanos, lagoas, rios e lagos, é de extrema importância. Um dos métodos mais comuns para monitorar a água é implantar bóias. O presente trabalho está integrado num projeto mais amplo, com o objetivo de projectar e desenvolver uma bóia autónoma para a investigação científica com dois modos de funcionamento: (i) monitorização ambiental ; e (ii) baliza ativa de regata. Assim, a bóia tem duas aplicações principais: a coleta e armazenamento de dados e a assistência a regatas de veleiros autónomos. O projeto arrancou há dois anos com um grupo de quatro estudantes internacionais. Eles projetaram e construíram a estrutura física, compraram e montaram o sistema de ancoragem da bóia e escolherem a maioria dos componentes electrónicos para o sistema geral de controlo e medição. Este ano, durante o primeiro semestre, dois estudantes belgas - Jeroen Vervenne e Hendrick Verschelde – trabalharam nos subsistemas de recolha e armazenamento de dados (unidade de controlo escrava) e de telemetria e configuração (unidade de controlo mestre) assim como definiram o protocolo de comunicação da aplicação. O trabalho desta tese continua o desenvolvimento do subsistema de telemetria e configuração. Este subsistema _e responsável pela configuração do modo de funcionamento e dos sensores assim como pela comunicação com a estacão de base (controlo ambiental), barcos (baliza ativa de regata) e com o subsistema de recolha e armazenamento de dados. O desenvolvimento do subsistema de recolha e armazenamento de dados, que coleta e armazena num cartão SD os dados dos sensores selecionados, prossegue com outro estudante belga - Mathias van Flieberge. O objetivo desta tese é, por um lado, implementar o subsistema de telemetria e de configuração na unidade de controle mestre e, por outro lado, refinar e implementar, conjuntamente com Mathias van Flieberge, o protocolo de nível de aplicação projetado. Em particular, a unidade de controlo mestre deve processar e atribuir prioridades às mensagens recebidas da estacão base, solicitar dados à unidade de controlo escrava e difundir mensagens com informação de posição e condições de vento e água no modo de regata. Enquanto que a comunicação entre a unidade de controlo mestre e a estacão base e a unidade de controlo mestre e os barcos é sem fios, a unidade de controlo mestre e a unidade de controlo escrava comunicam através de uma ligação série. A bóia tem atualmente duas limitações: (i) a carga máxima é de 40 kg; e (ii) apenas pode ser utilizada em rios ou próximo da costa dada à limitação de distância imposta pela técnica de comunicação sem fios escolhida.

SOLAP+: extending the interaction model

Thesis submitted to Faculdade de Ciências e Tecnologia of the Universidade Nova de Lisboa, in partial fulfillment of the requirements for the degree of Master in Computer Science

Environmental/Regatta Buoy: Sensing System

Um dos principais objetivos da ciência é perceber a natureza, i.e., descobrir e explicar o funcionamento do mundo que nos rodeia. Para tal, os cientistas precisam de coligir dados e monitorar o meio ambiente. Em particular, considerando que cerca de 70% da Terra é coberta por água, a coleta de parâmetros de caracterização da água de grandes superfícies é uma prioridade. A monitorização das condições da água é feita principalmente através de bóias. No entanto, as bóias disponíveis no mercado não satisfazem as necessidades existentes. Esta é uma das principais razões que levaram o Laboratório de Sistemas Autónomos (LSA) do Instituto Superior de Engenharia do Porto a lançarem um projeto para o desenvolvimento de uma bóia reconfigurável e com dois modos de funcionamento: monitorização ambiental e baliza ativa de regata. O segundo modo é destinado a regatas de veleiros autónomos. O projeto começou há um ano com um projeto do European Project Project [1] (EPS), realizado por quatro estudantes internacionais, destinado à construção da estrutura da bóia e à selecção dos componentes mais adequados para o sistema de medição e controlo. A arquitetura que foi definida para este sistema é do tipo mestre-escravo e é composta por uma unidade de controlo mestre para a telemetria e configuração e uma unidade de controlo escrava para a medição e armazenamento de dados. O desenvolvimento do projeto continuou com dois estudantes belgas que trabalharam na comunicação e no armazenamento de dados. Este projeto, que prossegue com o desenvolvimento da medição e do armazenamento de dados do lado da unidade de controlo escrava, tem os seguintes objetivos: (i ) implementar o protocolo de comunicação na unidade de controlo escrava; (ii ) coligir e armazenar os dados dos sensores no cartão SD em tempo real; (iii ) fornecer dados em tempo útil; e (iv) recuperar dados do cartão SD em tempo diferido. As contribuições anteriores foram estudadas e foi feito um levantamento dos projetos congéneres existentes. O desenvolvimento do projeto atual começou com o protocolo de comunicação. Este protocolo, que foi projetado pelos alunos anteriores, foi um bom ponto de partida. No entanto, o protocolo foi atualizado e melhorado com novas funcionalidades. Esta última componente foi um trabalho conjunto com Laurens Allart, que esteve a trabalhar no subsistema de telemetria e de configuração durante este semestre. O protocolo foi implementado do lado da unidade de controlo escrava através de uma estrutura de múltiplas actividades paralelas (multithreaded). Esta estrutura recebe as mensagens da unidade mestre, executa as ações solicitadas e envia de volta o resultado. A bóia é um dispositivo reconfigurável multimodo que pode ser expandido com novos modos de operação no futuro. Infelizmente, sofre de algumas limitações: suporta uma carga máxima de 40 kg e tem uma área de implantação limitada pela distância máxima à estacão base.

Formation Control Driven by Cooperative Object Tracking

In this paper we introduce a formation control loop that maximizes the performance of the cooperative perception of a tracked target by a team of mobile robots, while maintaining the team in formation, with a dynamically adjustable geometry which is a function of the quality of the target perception by the team. In the formation control loop, the controller module is a distributed non-linear model predictive controller and the estimator module fuses local estimates of the target state, obtained by a particle filter at each robot. The two modules and their integration are described in detail, including a real-time database associated to a wireless communication protocol that facilitates the exchange of state data while reducing collisions among team members. Simulation and real robot results for indoor and outdoor teams of different robots are presented. The results highlight how our method successfully enables a team of homogeneous robots to minimize the total uncertainty of the tracked target cooperative estimate while complying with performance criteria such as keeping a pre-set distance between the teammates and the target, avoiding collisions with teammates and/or surrounding obstacles.

Teleoperation of a service robot using a mobile device

Teleoperation is a concept born with the rapid evolution of technology, with an intuitive meaning "operate at a distance." The first teleoperation system was created in the mid 1950s, which were handled chemicals. Remote controlled systems are present nowadays in various types of applications. This dissertation presents the development of a mobile application to perform the teleoperation of a mobile service robot. The application integrates a distributed surveillance (the result of a research project QREN) and led to the development of a communication interface between the robot (the result of another QREN project) and the vigilance system. It was necessary to specify a communication protocol between the two systems, which was implemented over a communication framework 0MQ (Zero Message Queue). For the testing, three prototype applications were developed before to perform the test on the robot.

Desenvolupament d'un sistema de transferència de software per una placa entrenadora

El departament d’electrònica i telecomunicacions de la Universitat de Vic ha dissenyat un conjunt de plaques entrenadores amb finalitat educativa. Perquè els alumnes puguin utilitzar aquestes plaques com a eina d’estudi, és necessari disposar d’un sistema de gravació econòmic i còmode. La major part dels programadors, en aquest cas, no compleixen amb aquests requeriments. L’objectiu d’aquest projecte és dissenyar un sistema de programació que utilitzi la comunicació sèrie i que no requereixi d'un hardware ni software específics. D’aquesta manera, obtenim una placa autònoma i un programador gratuït, de muntatge ràpid i simple d’utilitzar. El sistema de gravació dissenyat s’ha dividit en tres blocs. Per una banda, un programa que anomenem “programador” encarregat de transferir codi de programa des de l’ordinador al microcontrolador de la placa entrenadora. Per altra banda, un programa anomenat “bootloader”, situat al microcontrolador, permet rebre aquest codi de programa i emmagatzemar-lo a les direccions de memòria de programa corresponents. Com a tercer bloc, s’implementa un protocol de comunicació i un sistema de control d’errors per tal d’assegurar una correcta comunicació entre el “programador” i el “bootloader”. Els objectius d’aquest projecte s’han complert i per les proves realitzades, el sistema de programació ha funcionat correctament.

LANGATTOMAN MITTAUS- JA VALVONTAJÄRJESTELMÄN PROTOKOLLAKEHITYS

Tässä diplomityössä esitellään langattoman mittaus- ja valvontajärjestelmän protokollakehitys. Työssä selvitetään protokollakehityksessä huomioon otettavat asiat ja esitetään langattoman tilavalvontaan perustuvan pilottijärjestelmän toteutus. Pilottijärjestelmänä käytetään Ensto Busch-Jaeger Oy:n Jussi-kosteusvahtijärjestelmää, joka muutetaan langattomaksi. Järjestelmän tiedonsiirto on yksisuuntaista ja tapahtuu radioyhteydellä. Käytetty taajuus on 433,92 MHz. Tavoitteena työssä oli kehittää yksinkertainen, mutta luotettava signalointijärjestelmä. Siihen toteutettu protokolla koodaa lähetettävän datan NRZ-L -koodauksen tapaisesti. Virheenkorjaus tehdään pariteettibittiä ja Hamming-etäisyyttä hyväksi käyttäen. Lisäksi tiedonsiirron yhteyskäytäntöön on lisätty rinnakkaisuutta yksisuuntaisen tiedonsiirron varmistamiseksi. Kehitetylle protokollalle tehdyt testit osoittavat sen olevan luotettava valitussa tiedonsiirtoympäristössä.

Lyhyen kantaman radiolähettimien soveltuvuus sähkökäyttöjen kunnon-valvonnan ja etädiagnostiikan tiedonsiirtotarpeisiin

Lyhyen kantaman radiolähettimien käyttö on kasvanut muutaman viime vuoden aikana huomattavasti. Osaltaan tähän on vaikuttanut uusien taajuusalueiden allokointi lupavapaiden radiolähettimien käyttöön, standardoitujen tekniikoiden yleistyminen ja laitteiden parempi saatavuus. Tässä työssä tarkastellaan lyhyen kantaman radiolähettimien soveltuvuutta sähkökäyttöjen kunnonvalvonnan ja etädiagnostiikan tiedonsiirtotarpeisiin. Työssä luodaan katsaus teollisuusympäristön vaikutuksiin langattomassa tiedonsiirrossa ja tarkastellaan sähkökäyttöjen kunnonvalvonnan ja etädiagnostiikan vaatimuksia tiedonsiirrolle ja tiedonsiirtojärjestelmälle. Työssä käydään läpi lyhyen kantaman radiolähettimiin liittyvät säädökset ja luodaan katsaus standardoituihin sekä valmistajakohtaisiin lyhyen kantaman radiotekniikoihin. Tiedonsiirtojärjestelmän suunnittelun kannalta tarkastellaan tiedonsiirtojärjestelmän topologiaa, protokollaa ja saatavilla olevia tekniikoita ja niiden implementoimista järjestelmään. Valmistajakohtaisia lyhyen kantaman radiomoduulien toimintaa ja Bluetoothin sisältävää älypuhelinta tutkitaan laboratoriomittauksin. Lopuksi kootaan yhteen langattoman tiedonsiirron ja eri tekniikoiden soveltuvuus sähkökäyttöjen kunnonvalvonnan ja etädiagnostiikan sovelluksiin.

Älykäs viestintäjärjestelmä

TeliaSoneran SME-viestintäjärjestelmän tarkoituksena on toimia demo- ja kehitysalustana uusille viestintäpalveluille. Näitä palveluita ovat esimerkiksi tilatiedon seuraaminen ja muuttaminen sekä pikaviestien lähettäminen ja vastaanottaminen eri alustoilla, kuten matkapuhelimilla, PDA-laitteilla, PC:eillä. Järjestelmän tulee myös toimia helppona yhteysrajapintana mahdollisille tuleville tiedonsiirtoteille. Pikaviestien lähetys- ja puhelujensignalointiprotokollana järjestelmässä toimii SIP. Järjestelmän sisäisenä kommunikaatioprotokollana toimii CORBA. Työn osuus ja tämän dokumentin fokus ovat järjestelmäytimessä eli Core:ssa. Core:n avulla järjestelmän eri komponentit, kuten SIP-, WAP- ja WWW-viestinvälityspalvelimet sidotaan toisiinsa sekä tietokantaan. Ytimen tehtäviin kuuluu myös käyttäjien tilatietojen ylläpito, viestien reititys eri päätelaitteisiin, ryhmäviestintä sekä pikaviestikomentojen toiminnallisuus, eli sanalla sanoen älykkyys. Lisäksi työssä tarkastellaan ytimen käyttämiä rajapintoja ja niiden toteutustekniikoita, projektin toteutukseen käytettyjä työkaluja sekä järjestelmän tarjoamia palveluita yksityiskohtaisemmin ytimen kannalta. Lopuksi luodaan silmäys tulevaisuuden näkymiin ja järjestelmän nykytilaan sekä kokonaisuutena hyvin menneen projektin tavoitteisiin.

Protocolo de comunicación trabajador-robot mediante imágenes

La idea del proyecto viene del concepto de “fábricas del futuro”, donde las barreras entre robots y humanos se rompen para que la colaboración entre ambos sea como en un equipo. Para la realización de este proyecto se ha utilizado el brazo robótico IRB120 de la marca ABB de 6 Grados de libertad, Matlab y el software Robot Studio. El Objetivo principal de este proyecto es establecer el protocolo de comunicación trabajador-robot mediante imágenes. El trabajador debería poder controlar el robot mediante dibujos realizados en la mesa de trabajo. En el desarrollo de la comunicación trabajador-robot cabe distinguir tres partes: · El análisis y tratamiento de imágenes para el cual se ha utilizado el software Matlab. · Transmisión de los datos desde Matlab al robot. · Programación de las acciones a realizar por el robot mediante el software “Robot Studio”. Con el protocolo de comunicación desarrollado y las imágenes realizadas por el trabajador el robot es capaz de detectar lo siguiente: · la herramienta que debe utilizar (rotulador, boli o ventosa) · si lo que tiene que dibujar en la mesa de trabajo son puntos o trazo continuo. · la localización de los puntos o del trazo continuo en la mesa de trabajo. Se ha alcanzado el objetivo propuesto con éxito, el protocolo de comunicación trabajador-robot mediante imágenes ha sido establecido. Mediante el análisis y tratamiento de imágenes se puede conseguir la información necesaria para que el robot pueda ejecutar las acciones requeridas por el trabajador.

Desenvolupament d'un sistema de transferència de software per una placa entrenadora

El departament d’electrònica i telecomunicacions de la Universitat de Vic ha dissenyat un conjunt de plaques entrenadores amb finalitat educativa. Perquè els alumnes puguin utilitzar aquestes plaques com a eina d’estudi, és necessari disposar d’un sistema de gravació econòmic i còmode. La major part dels programadors, en aquest cas, no compleixen amb aquests requeriments. L’objectiu d’aquest projecte és dissenyar un sistema de programació que utilitzi la comunicació sèrie i que no requereixi d'un hardware ni software específics. D’aquesta manera, obtenim una placa autònoma i un programador gratuït, de muntatge ràpid i simple d’utilitzar. El sistema de gravació dissenyat s’ha dividit en tres blocs. Per una banda, un programa que anomenem “programador” encarregat de transferir codi de programa des de l’ordinador al microcontrolador de la placa entrenadora. Per altra banda, un programa anomenat “bootloader”, situat al microcontrolador, permet rebre aquest codi de programa i emmagatzemar-lo a les direccions de memòria de programa corresponents. Com a tercer bloc, s’implementa un protocol de comunicació i un sistema de control d’errors per tal d’assegurar una correcta comunicació entre el “programador” i el “bootloader”. Els objectius d’aquest projecte s’han complert i per les proves realitzades, el sistema de programació ha funcionat correctament.