Bluetooth based warning system for ambient assisted living

FACULDADE DE ENGENHARIA DA UNIVERSIDADE DO PORTO Bluetooth based Warning System for Ambient Assisted Living João Pedro Cruz Silva Master in Electrical and Computers Engineering Scientific supervision by: Hugo Sereno Ferreira, Assistant Professor Department of Informatics Engineering Aditional supervision by: Manuel Monteiro, M.Eng. and Filipe Sousa, M.Eng. Fraunhofer Portugal July 21, 2015 © João Pedro Cruz Silva, 2015 Resumo Os idosos são o grupo etário com maior taxa de crescimento, especialmente em países desenvolvidos. Estas pessoas tendem a viver sozinhas, o que, numa situação de emergência, leva a que os serviços de resposta demorem mais tempo a ser notificados da mesma e ainda mais tempo a agir. Seria preferível que estas situações fossem evitadas e não tratadas. As Redes de Sensores Sem Fios têm estado nos interesses de investigação da comunidade académica já há alguns anos e a Internet das Coisas tem crescido mais depressa que nunca. Estes desenvolvimentos podem ser aplicados em Ambient Assisted Living para permitir aos idosos viver no seu ambiente preferido por mais tempo do que o que seria normalmente possível. Isto tem vários impactos positivos: aumenta a qualidade de vida dos idosos, dá-lhes mais independência e alivia a carga dos serviços de emergência. Neste documento propomos um sistema baseado numa tecnologia sem fios relativamente recente: o Bluetooth Low Energy. Esta tecnologia oferece uma largura de banda menor quando comparada com o Bluetooth clássico, mas oferece também vida de bateria muito mais longa. Este sistema funciona com uma arquitectura Peer-to-Peer enquanto fornece possibilidades para que seja expandido de formas mais escaláveis. Um pequeno microcontrolador com conectividade BLE correndo um interpretador customizado permite ao utilizador (um idoso com conhecimentos de informática ou seus acompanhantes) configurar regras que, usando sensores e estimando a distância ao utilizador permitem agir em contextos que correspondam a situações de emergência. Por exemplo, se um idoso estiver a cozinhar e se esquecer do fogão ligado, o microcontrolador pode actuar e desligar o fogão se o idoso em questão se afastar demasiado. Esperamos que a exposição compreensiva de informação neste documento potencie desenvolvimentos futuros nesta área. i ii Abstract The elderly are the fastest growing age group, especially in developed countries. These people tend to live alone, which leads to EMS taking longer to be notified than would be preferred and even longer for them to act. It would be preferable for these emergencies to be prevented rather than treated. Wireless Sensor Networks have been in the research interests of the academic community for a few years now, and the Internet of Things is growing faster than ever. One can take advantage of these new developments and apply them to Ambient Assisted Living in order to allow the elderly to live in their preferred environment for longer. This has several positive effects: it increases elderly people’s quality of life, their independence, and puts less strain on emergency services. In this paper we present a system based on a relatively new wireless technology: Bluetooth Low Energy. This technology offers us smaller bandwidth performance when compared to its older counterpart (classic Bluetooth) but with greatly increased battery life. Our system functions in a peer-to-peer architecture while providing a framework for being expanded into more scalable options. A small Microcontroller with BLE capabilities running a custom interpreter allows the user (a tech-savvy elder or his/her caregiver) to set rules that, using sensors and estimating distance to a connected device, can contextually act in order to prevent emergency situations: e.g. if an elder is cooking and forgets the stove on, this MCU can act and turn it off if the elder gets too far away. We hope that this paper’s comprehensive presentation of information lays the foundation for future developments in this area. iii iv Acknowledgements I’d like to thank: My girlfriend, for putting up with me, and for being a constant in my life. My parents, for supporting me, however annoying they may be. My grandfather, may he rest in peace, for having been a great role model. My grandmother, for the grandmotherly gifts she gives me. My godmother and godfather, for their knowledge and support. My cousin and his wife, Lily, for giving me advice, even though I’m often not willing to take it. Nuno, because sometimes he can be the only person as deranged as I am. Jota, for the group assignments together, the long nights, and the rides home. My dog, for being around for me when I don’t want people around. My coaches, for helping to keep me sane when I’m stressed out beyond imagination. To Hugo for the conversations, ideas and advices; To Manuel for the tough love; To Filipe for the support; And to João Oliveira for the debugging advice. To Barbosa and to João Lima for being thesis buddies... also for the cereal. To all those that I can’t remember right now but that aren’t forgotten. And, finally, to the giants that came before for lending me their shoulders. (João Silva) v xii LIST OF FIGURES 5.12 The naïve algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 5.13 Inflix notation vs postfix notation . . . . . . . . . . . . . . . . . . . . . . . . . . 49 5.14 Flowchart of the shunting yard algorithm . . . . . . . . . . . . . . . . . . . . . . 50 5.15 Step by step solving of an RPN expression . . . . . . . . . . . . . . . . . . . . . 51 5.16 Flowchart of the RPN parser algorithm . . . . . . . . . . . . . . . . . . . . . . . 52 5.17 Main switch block of our Reverse Polish Notation (RPN) parser code . . . . . . 53 5.18 The Smart Companion Launcher . . . . . . . . . . . . . . . . . . . . . . . . . . 54 5.19 Android application UI flow ............................ 56 6.1 Schematic of the power switching circuit incorporating a relay . . . . . . . . . . 60 6.2 The circuit recreated in National Instruments (NI)’s Multisim . . . . . . . . . . . 61 6.3 Oscilloscope plot of voltage at the load . . . . . . . . . . . . . . . . . . . . . . . 62 6.4 Voltage and current for different points in the circuit . . . . . . . . . . . . . . . . 63 6.5 Open space plot of estimated distance . . . . . . . . . . . . . . . . . . . . . . . 63 6.6 Fraunhofer Portugal’s main corridor (first floor) . . . . . . . . . . . . . . . . . . 63 6.7 Corridor plot of estimated distance . . . . . . . . . . . . . . . . . . . . . . . . . 64 6.8 TCPDump utility output during connection with the Nordic MCU ........ 64 7.1 The Pimatic UI ................................... 67 List of Tables 3.1 Comparison of different qualitative characteristics in the MQTT,STOMP and AMQP protocols .................................. 16 3.2 Table of wireless technologies and respective IEEE standards . . . . . . . . . . . 18 3.3 Comparison of different wireless technologies’ characteristics . . . . . . . . . . 22 6.1 Circuit bill of materials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 xiii xiv LIST OF TABLES Acronyms and Abbreviations 6LoWPAN IPv6 over Low power Wireless Personal Area Networks AAL Ambient Assisted Living AC Alternating Current ADC Analog-to-Digital Converter AES Advanced Encryption Standard AMQP Advanced Message Queuing Protocol AP Access Point API Application Program Interface APIPA Automatic Private IP Addressing APK Android application PacKage ARM Advanced RISC Machines ARP Address Resolution Protocol ART Android RunTime BAN Body Area Network BJT Bipolar Junction Transistor BLE Bluetooth Low Energy BNC Bayonet Neill–Concelman BSD Berkeley Software Distribution BSS Basic Service Set CBC Cipher Block Chaining CoAP Constrained Application Protocol CPU Central Processing Unit CRC Cyclic Redundancy Check DC Direct Current xv xvi Acronyms and Abbreviations DDR Double Data Rate DHCP Dynamic Host Configuration Protocol DNS Domain Name Service DSP Digital Signal Processing EDR Enhanced Data Rate EMS Emergency Medical Services EMU Environmental Measurement Unit ESS Enhanced Service Set FFD Full Function Device GPIO General Purpose Input Output GPS Global Positioning System GPU Graphics Processing Unit HART Highway Addressable Remote Transducer protocol HS/EDR High Speed (HS)/Enhanced Data Rate (EDR) HS High Speed HTTP HyperText Transfer Protocol I/O Input/Output IBM International Business Machines Corporation IBSS Independent Basic Service Set (BSS) IC Integrated Circuit ICMP Internet Control Message Protocol IDE Integrated Development Environment IEC International Electrotechnical Commission IEEE Institute of Electrical and Electronics Engineers IEEE-SA IEEE - Standards Association IETF Internet Engineering Task Force IGMP Internet Group Management Protocol IMU Inertial Measurement Unit IoE Internet of Everything IoT/IoE Internet of Things (IoT)/Internet of Everything (IoE) Acronyms and Abbreviations xvii IoT Internet of Things IP Internet Protocol IPv4 IP version 4 IPv6 IP version 6 ISM Industrial, Scientific and Medical JTAG Joint Test Action Group LAN Local Area Network LwIP Lightweight IP M2M Machine to Machine MAC Media Access Control MAN Metropolitan Area Network MCU Micro Controller Unit MEMS Microelectromechanical Systems MIB Management Information Base MIPS Microprocessor without Interlocked Pipeline Stages MIT Massachusetts Institute of Technology MOM Message Oriented Middleware MPR Multi-Point Relay MQTT Message Queue Telemetry Transport MQTT-SN MQTT - Sensor Networks NI National Instruments NIST National Institute of Standards and Technology NP Nondeterministic Polynomial OASIS Organization for the Advancement of Structured Information Standards OLSR Optimized Link-State Routing protocol OOB Out Of Band OSI Open Systems Interconnection OSPF Open Shortest Path First P2P Peer to Peer PAN Personal Area Network xviii Acronyms and Abbreviations PARC Palo Alto Research Center PC Personal Computer PCB Printed Circuit Board PHY Physical PPI Programmable Peripheral Interconnect PPP Point-to-Point Protocol PPPoE Point-to-Point Protocol (PPP) over Ethernet PPPoS PPP over Serial QoS Quality of Service RAM Random Access Memory RF Radio Frequency RFD Reduced Function Device RFID Radio-Frequency IDentification RISC Reduced Instruction Set Computing RPN Reverse Polish Notation RSSI Received Signal Strength Indicator RTT Round Trip Time SASL Simple Authentication and Security Layer SD Soft Device SDK Software Development Kit SIG Special Interest Group SNMP Simple Network Management Protocol SoC System on (a) Chip SO-DIMM Small Outline - Dual In line Memory Module SPEC Standard Performance Evaluation Corporation SPI Serial Peripheral Interface STOMP Simple (or Streaming) Text Orientated Messaging Protocol SWD Serial Wire Debug TCP/IP TCP/Internet Protocol TCP Transmission Control Protocol Acronyms and Abbreviations xix TI Texas Instruments TLS Transport Layer Security TX Transmit UART Universal Asynchronous Receiver/Transmitter UDP User Datagram Protocol UI User Interface ULP Ultra Low Power URL Uniform Resource Locator USB Universal Serial Bus USD United States Dollar UTF8 Universal Character Set + Transformation Format — 8-bit UWB Ultra-Wide Band VCO Voltage-Controlled Oscillator WEP Wired Equivalent Privacy WPA Wi-Fi Protected Access WPAN Wireless PAN WSN Wireless Sensor Networks XML eXtensible Markup Language Chapter 1 Introduction Ambient Assisted Living (AAL) has been a big research interest in current times. Due to the trend of an ever-increasing elderly population measures are needed to allow elderly people to not only cope with their condition but to thrive in their preferred environment. Research projects such as [1] and [2] have been funded by both private and public organizations in the last decade to develop solutions for these problems. In this document we propose a solution by leveraging recent developments in technology. In Chapter 1we provide an introduction to the document by succinctly explaining our Motivation, the Problem and the project’s Objectives. The research problem is further discussed in detail in Chapter 2. 1.1 Motivation The world’s elderly population is currently the fastest growing age group, especially in developed countries. Populational trends also lead to these people living alone in single households [3] which obviously constitutes a health hazard since elderly people usually have memory and physical impairments as a side effect of the ageing process. Healthcare costs with elderly people are highest in their final two years of life, since they require further attention by caregivers and healthcare professionals, including Emergency Medical Services (EMS). These factors combined will lead to increased costs. If alternative solutions aren’t developed the increased costs will be unsustainable. This will lead to either reduced Quality of Service (QoS) for healthcare or to increased costs for the patients. An integrated AAL solution would allow for the elderly to live largely unassisted in their preferred environment, increasing their autonomy and proactively decreasing healthcare costs by preventing possible problems before they even happen. Wireless Sensor Networks (WSN) have taken leaps and bounds in the last decade. They have shown great promise due to them being durable, decentralized (in mesh configuration) and being able to be clustered into highly available configurations [4]. Yet, they still haven’t been realized to their full potential; new technologies are being developed every day in this area and WSN’s are being used in new, interesting applications. These include WSN’s for monitoring farms [5] and 1 8State of the Art time in order to conserve power, so any overhead must be minimized [11]. To do this a creative approach is needed and will be discussed in Section 3.1.3. 3.1.1 Ubiquitous Computing While one discusses Wireless Sensor Networks it is important to note the paradigm shift that eventually lead to the coming of age of this technology and its implications, including the huge research interest that revolves around it. This shift was characterized by a concept that emerged from the mind of a researcher named Mark Weiser at the Xerox Palo Alto Research Center in 1988. Quoting Weiser: “Ubiquitous computing names the third wave in computing, just now beginning. First were mainframes, each shared by lots of people. Now we are in the personal computing era, person and machine staring uneasily at each other across the desktop. Next comes ubiquitous computing, or the age of calm technology, when technology recedes into the background of our lives [13].” The future that Weiser envisioned was one where computing was ubiquitous (seeming to be seen everywhere) [14]. Current trends have proven him to be, at least to an extent), right. Weiser identified three ages of computing: In the first age many users shared a single Mainframe between them. More powerful computers were necessarily just one bigger, more powerful (and power-hungry) machine. In the second age, defined by Weiser as the Personal Computer (PC) age, which we are currently experiencing, computing is achieved by means of individual machines. The "One Person, One Computer" paradigm is the norm and computing is achieved my means of these devices. Supercomputers in this day and age are built from thousands of generic off-the-shelf computer components, and their huge performance is essentially attained by exploiting parallelism [15]. Weiser predicted that there would be a third age of computing characterized by huge numbers of small, cheap, and easily-replaceable wirelessly-connected computing nodes. These nodes would fade out of existence, melding imperceptibly with everyday objects. Everything would be connected and computing would be everywhere (see Fig. 3.1). One would use this Everyware [16] naturally and fluently without even realising it. This concept is obviously still just that, but computing is slowly evolving into it. Other similar concepts such as the Internet of Things/Everything will naturally come first. 3.1.2 Internet of Things/Everything The Internet of Things is a concept that is closely related to Ubiquitous Computing but pertaining more to individual objects rather than ever-present computing. Internet of Things (IoT)/Internet of Everything (IoE) (IoT/IoE) boils down to a scenario where common day objects, people, animals, etcetera, are connected to the Internet and are able to use it to communicate. A thing in the IoT is something that can be issued a unique identifier in order for it to communicate without human 3.1 WSN 9 (a) Quantity computing paradigm (b) Quality computing paradigm Figure 3.1: If one assumes that the cost of computing will fall over time two outcomes are possible: either (Fig. 3.1a) the number of computers increases or (Fig. 3.1b) their quality increases. If current trends continue the first scenario is more likely and fits into the Ubiquitous Computing concept [13]. interaction. This type of communication is known as Machine to Machine (M2M) communication [17]. In a sample system consisting of a vending machine and the company that restocks the vending machine, a machine connected to the IoT would transmit information about stocks to the company’s server and when it would get low on a particular product an automated message would be sent to the employee restocking the machines. This way, the human middle-man is cut out. Products built with this type of capabilities are usually defined as being smart (eg: smart label, smart sensor). The concept of IoT was only coined in 1999 by Massachusetts Institute of Technology (MIT)’s Auto-ID Center and its related publications [18], but it had been in the making long before that: The MIT’s Computer Science Department runs a Coke machine since the ’70s that was the first appliance to have internet connectivity. It allowed users to check the status of the Coke bottles in the machine (quantity and temperature) [19]. As we can see in Fig. 3.2 the fist version of the Internet of things came from a necessity for more efficient logistics by using Radio-Frequency IDentification (RFID) tags. This first iteration consisted mainly of one-way communication: the tags themselves contained no information beyond an ID code that corresponded to an entry in a database. Eventually, this development will lead to Ubiquitous Computing, where everything is connected. 3.1.3 Meshed and Multi-hop Networks Meshed and Multi-hop Networks are incredibly important, enabling technologies for both Ubiquitous Computing and Internet of Things/Everything. Even though wireless technologies have progressed a lot in the last decade the current networking paradigm is still one of infrastructure: wireless devices access the internet through an Access Point that connects to a wired infrastructure network. This type of web access isn’t scalable for huge numbers of ever-present devices: it forces the numbers of Access Points and the size of the wired networks to scale with the number of devices. One can infer that the future will be in ad-hoc, meshed networking (see Fig. 3.3, bottom-right) [21]. since this type of networking allows for data communication without a wired infrastructure 10 State of the Art Figure 3.2: Technology roadmap for the evolution into the Internet of Things[20] network. Each device in the network can be abstracted as a node: it has computing power and can receive or send messages to other nodes. Mesh networks generally allow transmission only to a node’s nearest neighbour. Multiple paths to a same destination give this network configuration immense versatility and robustness. Nodes are considered identical in the general case, but they need not be. Certain nodes can be designated as "group leaders" of some sort and carry out additional functions besides those of their peers (supernodes) . This leads to a network that has a mesh topology and a hierarchy. As nodes are added to a network, the problem of finding the best path for a message to travel (routing) tends toward NP complexity. Breaking up the network into smaller, hierarchical networks helps break up this complex problem into smaller ones that can be solved faster as a whole. In this case, the entry node to a specific cluster is usually designated as the group leader [4]. One can look at the example of the Optimized Link-State Routing protocol (OLSR). OLSR is a routing protocol developed by the Internet Engineering Task Force (IETF) specifically for ad-hoc mobile networks, similar to another Link-State routing protocol: OSPF. The flooding process used by OSPF is not appropriate for wireless ad-hoc networks: if every node floods its routing information the media is not used efficiently and any change in network topology (which in the case of wireless networks is much more common than in wired ones) leads to the network being flooded. Also, in the case of mobile networks one wants to keep the number of transmissions to a minimum in order to conserve battery life. To solve these problems OLSR implements the notion of hierarchical nodes: by sending "Hello" messages each node discovers its two hop neighbours and performs a distributed election of a node to be its Multi-Point Relay (MPR). The MPR acts as the router for a subset of the 3.2 MOM 11 Figure 3.3: Basic Network Topologies[4] network’s nodes and floods the networks with messages pertaining to topology changes on behalf of the other nodes in its group. This means that only the MPR has to send messages and greatly reduces the number and frequency of messages flooding the network [22]. 3.2 Message Oriented Middleware With the continuous advances in networking technology and with current networking paradigms creeping ever-closer to the Internet of Things/Everything multiple heterogeneous systems that once were regarded as completely independent now have to be integrated with one another. Systems have also been becoming distributed. Although this provides us with many advantages it makes systems inherently more complex. This gives us numerous problems when one wants to integrate these completely different systems. Altering every single component to work correctly with each other is simply not practical. A solution that has been proposed in [7] and works by acting like a "glue" of some sort between two different systems (as can be seen in Fig. 3.4) is a Middleware. The idea behind middleware is that it acts like a translator between two or more systems that allow them to talk to one another without them being altered. Using a middleware allows one to easily integrate normally incompatible and often pre-existing systems without altering them. Different applications can be linked by transmitting messages between them. Because of this, this type of middleware based on events, or messages, is usually called Message Oriented Middleware (MOM). 12 State of the Art (a) (b) Figure 3.4: In order to fit two pieces of a puzzle together, one can either: Fig. 3.4a alter them individually so that they fit or Fig. 3.4b create an intermediary that fits both. Some MOM’s are based on the Publish/Subscribe model. In this model each client registers either as a publisher or subscriber of messages. Messages have their own Information Spaces and can be traded between spaces using Message Flow Graphs that specify how the messages are transformed and propagated. This structure can be used to drop obsolete messages, to buffer messages to subscribers that have been off-line and this makes the whole system much more streamlined. The Publish/Subscribe scheme allows for time, space, and synchronization decoupling. Space decoupling allows two parties to share information between them without actually knowing each other. This is achieved because they both transmit and receive their information using the middleware as a proxy. The subscribers need not know where the information they need is located, they just subscribe to a topic or content type and the middleware is responsible to get their messages to them. Time decoupling allows those same two parties to not need to be participating in the interaction with the middleware simultaneously in order for the information to be transferred. In this case the middleware acts as a buffer and stores messages for a subscriber and sends them to that subscriber when it is online. Synchronization decoupling means that publishers need not be blocked when producing events and subscribers can get notified in a non-blocking manner when new messages are available for them. 3.2.1 Protocols A number of different protocols have been developed for MOM. In this section we describe three popular ones: Advanced Message Queuing Protocol (AMQP),Simple (or Streaming) Text Orientated Messaging Protocol (STOMP) and Message Queue Telemetry Transport (MQTT). 3.2 MOM 13 3.2.1.1 AMQP The AMQP is an open standard application layer protocol that has been an Organization for the Advancement of Structured Information Standards (OASIS) standard since May 2014 [23]. It is a binary, application layer, wire-level protocol and was designed to support many messaging applications. It provides flow control, message delivery guarantees and authentication/encryption. AMQP has its own encoding scheme allowing for representation of a wide range of types, while allowing data for being given extra meanings. For example, a string can be appended with additional information for it to be understood as an URL [24]. The protocol uses a set of nine frames to create/destroy connections, transfer data and provide control information, these are: "open", "begin", "transfer", "flow", "disposition", "detach", "end" and "close". Links are the basic connection type in AMQP, they are unidirectional. Sessions are comprised of multiple links and can be used for bidirectional transfer of data. A connection between two peers can have multiple sessions. Links are initiated with "attach" and terminated with "detach" frames. Similarly, sessions use the "begin" and "end" frames and connections the "open" and "close" frames. Messages are sent over a link using the "transfe"r frame. The "flow" frames are used for flow control, in order ensure QoS and prevent deadlocks. The disposition frame is used for the peers to settle on the state of the transfer, for reliability guarantees. Since AMQP is a wire-level protocol that represents data as a stream of octets, it can be used in any application that understands messages in this format. Even though it usually relies on Transmission Control Protocol (TCP) for transport purposes it is independent of the TCP/Internet Protocol (TCP/IP) protocol stack. One should note that in this paper we discuss only version 0.9.1 of AMQP as it is used in RabbitMQ. 3.2.1.2 STOMP The Simple (or Streaming) Text Orientated Messaging Protocol is another open standard messaging protocol that is presented as an alternative to AMQP and other implementation specific protocols. It tries to distinguish itself by being simple and lightweight, offering a small but useful messaging API. Similarly to AMQP STOMP is frame based, but it is modelled on/inspired by HyperText Transfer Protocol (HTTP). Each frame consists of a command and, optionally, headers and a payload. By default, it is text based (Universal Character Set + Transformation Format — 8bit (UTF8)), but supports different encodings, allowing, for example, binary messages to be sent. Like AMQP,STOMP uses a reliable 2-way streaming protocol for its transport needs, such as TCP, when implemented on the TCP/IP stack. STOMP frames follow the structure: COMMAND header1:value1 14 State of the Art header2:value2 Body^@ Several headers may be sent in a single STOMP message, as long if the keys for each header value are distinct. If there are repeated keys, only the first value is used. STOMP supports a function named heart-beating that allows two peers to test the healthiness of the underlying TCP stream, this is useful for QoS purposes [25]. 3.2.1.3 MQTT MQTT is yet another open-source MOM protocol. MQTT was originally developed by IBM and made open-source in the early 2010s. Similarly to the other protocols presented here MQTT is Publish/Subscribe based, and similarly to STOMP is designed with light weight in mind, but, unlike the other protocols, it is specific to the TCP/IP stack. Unlike STOMP,MQTT’s messages are much less verbose and more compact [26]. One specific advantage that MQTT has is a sub-specification: MQTT-SN or MQTT for Sensor Networks. It is an even more trimmed down version of MQTT designed specifically for IoT and Sensor Networking scenarios while being as close to MQTT as possible. It works on non TCP/IP networks such as ZigBee. By using gateways and forwarders an MQTT network can be extended into these sensor networks. MQTT-SN also supports an offline keep-alive procedure that is used for supporting sleeping clients. Clients that go into a sleep mode have their messages buffered at the gateway and are delivered when they wake up [27]. 3.2.2 Applications The protocols that were mentioned in Section 3.2.1 are only that: protocols defined in specifications. In this section we mention three practical MOM implementations that use at least some of these protocols. 3.2.2.1 RabbitMQ RabbitMQ is an open-source MOM message broker written in the Erlang programming language. RabbitMQ uses the AMQP protocol but the project includes gateways for the HTTP,STOMP, and MQTT protocols. It also has a plugin platform that allows one to extend the base functionalities provided. The RabbitMQ server runs on all major operating systems with official clients written in Erlang, C# and Java, but there is a large community supporting the project offering clients written in a multitude of other languages [28]. 3.2 MOM 15 One should note that RabbitMQ offers several features for increased reliability and availability, including queue mirroring. RabbitMQ also includes features that make debugging easy, such as a graphical management User Interface (UI) and tracing support. 3.2.2.2 Mosquitto Mosquitto is an open-source MQTT broker written in C. It is a project with a very small footprint aimed at being deployed on low-power and embedded systems. It includes libraries written in C with C++ and Python wrappers [29]. Mosquitto is perfect for being deployed in very low power systems. In [30] the developer mentions that he had tested Mosquitto on a VIA Cyrix III 600 MHz based system processing 1500 messages per second. 3.2.2.3 ActiveMQ ActiveMQ is yet another open-source message broker, but unlike the others presented here it is written in Java. ActiveMQ supports the AMQP, OpenWire, MQTT and STOMP protocols [31]. Since ActiveMQ is written in Java it is supported in all major operating systems without need for porting. With its compatibility with multiple MOM protocols, it supports clients written in basically every language. It also does not require a broker to function and can be implemented in a purely P2P fashion. However, in benchmarks (such as the ones in Section 3.2.3) ActiveMQ tends to lag behind the competition in performance. 3.2.2.4 ZeroMQ ZeroMQ, often stylized ØMQ is an offshoot project of an AMQP implementation called OpenAMQ. The company that runs the project stopped using AMQP because of concerns that it had become overly complicated. Unlike other MOM implementations presented in this paper, ZeroMQ is not a message broker, it is in fact a small, fast networking library. It does not require a server running a dedicated message broker in order for it to work. ZeroMQ has a base of tradeoffs: by decreasing complexity it has achieved fantastic performance but at the expense of some commodities. 3.2.3 Comparison Publish/Subscribe MOM is usually intended for very scalable applications. Like everything else, how scalable these middlewares actually are must be quantified. For this purpose, in 2007 the Standard Performance Evaluation Corporation (SPEC) developed SPECjms2007: an industry-standard performance test for MOM. The SPECjms2007 was 16 State of the Art Figure 3.5: In [34] the author compared several different MOM solutions, including ActiveMQ, ZeroMQ and RabbitMQ extended in 2009 to form the jms2009-PS benchmark specifically for Publish/Subscribe middleware [32,33]. This benchmark has a real-world scenario behind its thinking and offers a close approximation to how these products should perform in an actual application. Although these standard testing procedures exist to evaluate the actual performance of the middleware, sometimes performance must be sacrificed for useful features and ease of use. In this section a relative comparison of the studied middlewares is presented. In terms of raw performance, we can reference these two tests conducted in a non formal fashion [34,35] (Fig. 3.5 and Fig. 3.6). ZeroMQ is the clear winner, being the fastest with its fast enqueue and dequeue times. RabbitMQ is a close second. In terms of protocols, AMQP seems to outperform STOMP, which is to be expected, given the latter’s increased verbosity. In [36] another comparison between these protocols is made, but considering their features. In Table 3.1 a similar qualitative comparison is made. MQTT STOMP AMQP QoS Levels 3 1 3 Subscription Types Hierarchical topics Topics Exchanges, Queues and bindings Data Serialization — — AMQP type system or user defined Standard OASIS standard OASIS standard — Security Encryption Authentication SASL/TLS SASL — Username/Password SASL Table 3.1: Comparison of different qualitative characteristics in the MQTT,STOMP and AMQP protocols 3.3 Wireless Communication Solutions 17 Figure 3.6: In [35] another comparison is made with similar results to Fig. 3.5 3.3 Wireless Communication Solutions In the last three decades a paradigm shift has taken place in computer networking: the advent and popularization of wireless communication technologies. While certain technologies like Bluetooth and Wi-Fi were developed for the consumer market they soon found other applications. In this section we discuss prominent wireless communication technologies such as Bluetooth,ZigBee and Wi-Fi and in Others we mention technologies that, although they aren’t especially useful for our needs, we feel are worth mentioning. The technologies presented here operate in the unlicensed Industrial, Scientific and Medical (ISM) bands. These include the 2.4 GHz band for all technologies presented here, while others can use multiple bands such as 5 GHz for WiFi and 900 MHz for ZigBee. 3.3.1 What is defined by the IEEE The organization that is responsible for defining and standardizing these wireless technologies is the IEEE trough the IEEE Standards Association (IEEE-SA). All technologies mentioned here have been, to an extent, standardized by this organization under the IEEE 802 standard committee for Local Area Network (LAN)/Metropolitan Area Network (MAN) connectivity with variable sized packets. While these technologies are defined by the IEEE, the IEEE only defines the Physical (PHY) and Media Access Control (MAC) layers as defined by the Open Systems Interconnection (OSI) model (Fig. 3.7), so that these standards can become viable commercial, functioning, products, higher levels of the OSI model must be defined (Fig. 3.8). These are usually defined by company alliances such as the Wi-Fi Alliance and the ZigBee Alliance. 24 State of the Art with integrated antenna, a low-power MCU (8 MHz Texas Instruments (TI) MSP430 microcontroller) with extended memory and an optional sensor suite. The TelosB is made to be powered with two AA batteries [65]. (a) (b) Figure 3.12: In Fig. 3.12a the TelosB module is shown, and it’s respective block diagram in Fig. 3.12b. 3.4.5 TI CC2540 The TI CC2540 is a low cost, low power, SoC chip developed for BLE applications. It combines an RF transceiver with an 8051 MCU in a single package. Integrated in a Printed Circuit Board (PCB) with other components and connectors it can prove a very good solution for low power sensors and actuators that are in sleep mode most of the time [66]. 3.4.6 Nordic nRF51822 The Nordic nRF51822 is a powerful and flexible SoC by Nordic Semiconductor for BLE solutions built around an ARM Cortex-M0 MCU and featuring a 2.4 GHz transceiver designed for the ISM band. It supports several analogue and digital peripherals though 31 General Purpose Input Output (GPIO)s. These peripherals can communicate with each other without CPU intervention though the use of a Programmable Peripheral Interconnect (PPI) system. A specific version of the MCU that is available to us, the nRF51822AA has a total of 256 kB of flash and 16 kB of RAM. This SoC is compatible with Nordic’s Gazelle protocol, ANT protocol and the Bluetooth Smart protocol [67]. 3.5 Indoor Location Solutions Indoor location has been a topic of discussion in academia for quite some time without a conclusion being made as to a good solution for the problem. Global location systems such as GPS aren’t accurate enough or simply not practical in most situations (GPS requires line-of-site to work), so, new specific solutions have to be developed. There is also an interest that these new solutions rely 3.5 Indoor Location Solutions 25 on existing, and commonplace systems, so that new investment to obtain new functionality is kept to a minimum. In this section we discuss several proposed solutions for this problem. 3.5.1 BLE based Although Bluetooth was originally intended for low bitrate communication it can be applied for localization purposes. The Bluetooth specification forces each Bluetooth-enabled device to report Received Signal Strength Indicator (RSSI) to upper protocol layers for power-control purposes, but this information can be used for location through trilateration. This process has two main disadvantages: 1. So that the RSSI value can be used for trilateration, each node participating in the location process needs to be transmitting at full power. This has two more implicit disadvantages: (a) For the node to be constantly transmitting at full power it must be in discovery mode, and therefore cannot be simultaneously used to transmit data. (b) Increased power consumption. 2. Since there is no clock synch mechanism between Bluetooth nodes, measurements used for trilateration may not have been made at the same time. This introduces errors in the measurement, especially if the target is moving [68]. The main advantage of this technology is that it can be found in most consumer-grade electronics equipment that is capable of communication. In [6] the use of this technology is explored for a location-aware sign on system, in [69] a guide application was developed based on this technology and in [70] an application for cat tracking is developed to a certain degree of success. 3.5.2 ZigBee based The ZigBee technology is similar to Bluetooth and most location solutions hover around the same processes proposed in Section 3.5.1, and use the RSSI indicator. However, some diferent interesting approaches have been developed for this technology. In [71] and in [72] two different algorithms have been proposed that increase effectiveness in location systems. In [71] the tree network topology for ZigBee is exploited to allow for a statistical maximum-likelihood location approximation. In [72] the implemented algorithm divides the space in between different ZigBee beacons in different zones that can, themselves, be divided into subzones. The algorithm predicts in what zone the node is more probable to be located. Location errors obtained were generally less than 2 m. 3.5.3 Wi-Fi Similarly to the other alternatives presented here, Wi-Fi location techniques revolve around the same method of trilateration based on RSSI and the placing of beacons. However, due to the 26 State of the Art Figure 3.13: System architecture proposed in [5] nature of the technology and it’s higher transmission power (typically 20 dBm) it is more prone to be affected by multipath propagation and reflection, so huge errors are typically associated with the use of Wi-Fi for location. Therefore, typically Wi-Fi location systems resort to some kind of geotagging system: when the client connects to a different AP it is assumed to be in a certain place [73]. 3.6 Applied Research In this section we present some practical, working, systems that were implemented in real-world scenarios leveraging some of the technologies that were exposed in this chapter. 3.6.1 Health sensor systems This type of system has been applied for health purposes to some extent. In [9] a system to integrate multiple health sensors by creating a rule engine was proposed. In [74] a health monitoring system is fabricated by integrating sensors and transducers into textiles, offering a less intrusive way to collect this type of data. 3.6.2 Agriculture In [5] (see system architecture in Fig. 3.13) a sensor network was developed using the ZigBee protocol along with the Sheevaplug and TelosB hardware platforms. The purpose of this product was wireless monitoring of greenhouses for agricultural purposes. The authors were able to provide an interesting and effective solution, being able to squeeze up to 53 weeks (one year) of battery powered node operation. The companion web and mobile apps that were developed offered a simple interface to the farmers that ran these greenhouses, helping with their management. 3.6 Applied Research 27 3.6.3 Ambient Assisted Living There has been a lot of research interest in the EU, in part due to the Ambient Assisted Living Joint Programme: an ongoing funding effort running since 2006. Some notable projects include: eCAALYX, a project to enable a commercially viable solution to permit remote monitoring of elderly by healthcare professionals and caretakers [1,75]. The Cockwork project used a number of hardware and software platforms, including a WSN with sensors and actuators and was targeted mainly at shift workers that were greatly affected by chronodisruption. The project’s objective was to help users maintain a healthy day-night cycle by manipulating their environment [76]. ALMA was a project with the objective of providing a modular, low-cost, integrated system to support autonomous mobility and orientation for elders [77]. 28 State of the Art Chapter 4 Development tools In this section we present the various tools used to develop our proposed solution. 4.1 Fraunhofer Pandlet Figure 4.1: The Fraunhofer Pandlet CORE (right, square, 28.4 mm wide). 1C coin (left) for reference. The Fraunhofer Pandlet is an integrated sensor and processing platform still in active development at Fraunhofer Portugal, based around the Nordic nRF51822. The modules created with the pandlets are composed of several building blocks, that can be interconnected in order to provide for extra hardware functionality. The base building block is called the pandlet CORE and includes, in a small package (Fig. 4.1) a Nordic nRF51822 SoC with a Bluetooth 4.0 interface and 16 MHz ARM M0+ CPU; support for Qi wireless charging and Inertial (IMU) and Environmental (EMU) Measurement Units. The IMU contains an accelerometer, a gyroscope and a magnetometer. The EMU contains a humidity sensor, an air pressure sensor and a temperature sensor. In addition to the CORE module, currently there are two more modules available: the Memory module and the Sensing+ module (Fig. 4.2). These modules extend the capabilities of the original CORE module. The Memory module adds a Micro USB port for wired charging and a Micro SD card slot to allow for large quantities of local, persistent storage. The Sensing+ module allows for the connection of extra external sensors through various ports, including two BNC connectors. 29 30 Development tools The sensor’s outputs can be connected directly to one of the MCU’s GPIOs for direct reading or for I2C communication or to an external Analog-to-Digital Converter (ADC). With further development of the platform, new form factors and blocks may be developed. Figure 4.2: The Fraunhofer Pandlet, complete with Memory and Sensing+ modules. 4.2 Development Boards 4.2.1 PCA10001 The PCA10001 (Fig. 4.3) is a MBED-enabled development board distributed by Nordic Semiconductor. MBED is a platform and operating system designed for fast development and prototyping of MCU platforms, namely Cortex-M 32 bit MCUs such as the Nordic nRF51822. MBED provides APIs to abstract differences between supported MCUs to make sure that most things work between platforms out of the box. Although the preferred way to program for MBED platforms is with an online Integrated Development Environment (IDE) and compiler provided by MBED, it is also compatible with offline toolchains. We will use the GNU ARM GCC toolchain to develop our application for this board. After the application is successfully compiled, one can simply connect the PCA10001 board to a computer and it will be identified as a thumb drive. The MCU can then be programmed by dragging the resulting binary file into the thumb drive. This is an advantage over traditional programming since no debugger/flasher is necessary, however, despite supporting communication with the MCU with Universal Asynchronous Receiver/Transmitter (UART) over USB, MBED does not support on-chip code debugging [78,79]. Figure 4.3: Nordic’s PCA10001 development board [79] 4.3 The Softdevice 31 Figure 4.4: Nordic’s PCA20006 development board 4.2.2 PCA20006 The PCA20006 (Fig. 4.4) is a development board that, similarly to the PCA10001, is built around the Nordic nRF51822. However, it is much smaller, and is not MBED-enabled. As such, it must be programmed using a Joint Test Action Group (JTAG)/Serial Wire Debug (SWD) emulator such as, and in our case, the SEGGER J-Link EDU. 4.3 The Softdevice The Nordic protocol stacks are called Soft Devices. Nordic SD are pieces of pre-compiled, pre-linked software that implement the required protocol stacks, in this case Bluetooth Low Energy. They give the developer the important ability to not have to implement a full protocol stack and interact with proprietary technology. The SD implements the full Bluetooth stack, so that the developer doesn’t have to. The SD’s functions are accessed through a pure C API. The SD is flashed onto the microcontroler alongside the application and at compile time the linker generates jumps to positions in memory where SD instructions are located. This SD does have its disadvantages. Firstly, it is proprietary, so a developer that relies on it is completely reliant on Nordic Semi for support. Secondly, since it requires the use of pre-compiled binary files, it forces the developer to use the same toolchain that Nordic initially used to produce the binary files, or one will experience linker errors and warnings. Using the SD also severely limits the available resources that the developer has available. In our case, the SD requires half of all the available flash and memory. 1500 B are also used by the SD for its call stack in the RAM region addition to 500 B more used by the application call stack. This means that by using the SD one effectively gets restricted to 128 kB of memory and about 4 kB of RAM [80,81]. Despite these disadvantages we feel that using the SD is more than worth the risk. 32 Development tools Figure 4.5: An example of the full software stack running on the MCU, featuring the SD programmed alongside the application [80] Figure 4.6: The Bluetooth Smart stack that is implemented by the SD [80] 4.4 nRF51 SDK 33 Figure 4.7: An example of an IoT network communicating by using BLE links with 6LoWPAN support [82] Nordic’s BLE SDs come in several flavors: The S100 series and the S300 series SDs. The S100 series SDs only implement a BLE stack; The S110 SD can communicate in a peripheral role and the S120 SD can communicate in a central role, while the S130 SD can switch between those two modes of operation. The S300 series SDs, containing only the S310 SD implement BLE in both modes of operation and also the ANT protocol (proprietary) concurrently. For our specific needs, the S110 SD was chosen, due to its reliability and simplicity. 4.4 nRF51 SDK A Software Development Kit (SDK) is a set of tools that allow for the development of applications for a certain platform. The nRF51 SDK is one such set of tools that is provided by Nordic Semiconductor to developers using their series of nRF51 SoCs. Besides containing all the header files and such that are required for application development for that specific platform using BLE, it also contains relevant SDs, documentation and examples for that specific technology and also other protocols that can be used with this platform that are proprietary to Nordic, mainly featuring low power, simple types of communication. 4.5 IoT SDK The IoT SDK is a prototype (not yet production ready), modified, version of the nRF51 SDK that is capable of communicating via IP version 6 (IPv6) by implementing the 6LoWPAN standard proposed by the IETF. The 6LoWPAN standard proposes encapsulation and header compression mechanisms that allow IPv6 packets to be transfered in IEEE 802.15.4 networks such as BLE and ZigBee. The purpose of this standard is to allow the most low powered devices to be addressable by IPv6, giving them access to the broader Internet and to the Cloud [83]. The IoT SDK also includes a complete Internet Protocol Suite including Internet Control Message Protocol (ICMP), User Datagram Protocol (UDP), TCP, Constrained Application Protocol (CoAP) and MQTT protocols, and examples on how to develop applications using them. Devices using this SDK implement a Bluetooth profile designed specifically for this type of communication, and it is through this profile that packets are transfered between the IoT device and another, WPAN-enabled device, connected to the Internet, that will act as an IPv6 access point and/or router. The SDK also 40 The BlueWarnAAL solution Figure 5.3: The different wireless technologies used for node to node communication. Between the Pandlet and the smartphone, BLE is used, for the connection between the Pandlet and the Raspberry Pi 6LoWPAN and for the Raspberry Pi connection to the internet, Wi-Fi is used. Pandlet Applicaion BLE StackRule Engine RSSI Engine Figure 5.4: Block diagram of the Pandlet’s three components 5.2 Components 41 Figure 5.5: Exploded view showing the structure of an AltBeacon advertisement packet [89] to an LED to provide a visual representation of the characteristic value. These characteristics can also be used as Input Characteristics, fostering composition. These Characteristic User Descriptions must be a name and suffixed with "_Value" (e.g. Actuator_Value or LED_Value). •Rule Characteristic: This is where the actual rules are stored. The rules are stored as UTF8 strings and must be evaluable to boolean values. Rule characteristic’s Characteristic User Descriptions must follow the following convention: the user Description of the Output Characteristic corresponding to this rule must be suffixed with "_Rule" (e.g. TV_Rule or Chandelier_Rule). Our characteristic was named "Actuator_Rule" and by default contained the value "Distance < 10". Advertising In order to enable for future use of the Pandlet as a Beacon, for ranging purposes from a smartphone, its advertisement packets were made to conform to the AltBeacon specification. The structure of an advertisement packet can be seen in Fig. 5.5. Since the fields required by the specification are 31 B one cannot send any more information in this advertisement packet[88]. It was opted to include in the advertisement the device’s name, so that the user could configure friendlier and meaningful names (e.g. "Living Room Pandlet") and have them appear in Bluetooth device searches. For this, the Scan Response, a packet of extra advertisement data sent to the scanner after a scan attempt, was used. 5.2.1.2 Estimating Distance The Bluetooth standard calls for the RSSI to be passed to the application from the Bluetooth stack. In our solution this information is used for ranging. According to [90], RSSI varies with distance with a relationship expressed by 5.1, where d is the distance, n is the signal propagation constant (free space value is 2) and A is the average RSSI as measured at 1 m from the emitter (−61 dBm for the Nordic nRF51822). RSSI(d)=−(10 ·n·log10 (d) + A)(5.1) By solving 5.1 for d, we get 5.2. The IoT SDK allows the developer to implement a handler function that is called every time that the RSSI value in the current link changes. We leveraged 42 The BlueWarnAAL solution this function to estimate a new distance value when the RSSI value changed on the current link. However, we found that this RSSI value changed much too often and with values too large to be used as a reliable measure of distance all by itself: for example, the distance value estimated from this RSSI would often, in the space of just 10 s change in excess of 20 m. d(RSSI)=10(A−R 10·n)(5.2) The chosen solution was to implement a rolling average: Whenever a new RSSI value was read, it was inserted in a circular buffer large enough to hold about 50 samples. The average value of all these samples was then used to estimate the distance. This meant that sudden variations in reported RSSI took longer (a few seconds) to produce visible effects in the distance estimation, however, sudden changes in RSSI were effectively smoothed out. 5.2.1.3 Implementing a Rule Engine One of the challenges of this solution was to allow rules present on the Pandlet to be modified at-will by the user. While there is no lack of solutions for this problem that work in average, modern systems, in our specific case this is non-trivial. For one to evaluate rules in run-time, one has to be able to receive a mathematical expression in string form at run time (e.g. 2 >1) and evaluate it into a result (e.g. true), this is beyond the standard capabilities of the C programming language. One solution to overcome this problem is usually embedding another programming language in our program. Languages such as Lua and Tcl provide for these situations by offering APIs, written in C, to allow for programmers to embed them. When these languages are embedded, they essentially act as virtual machines, running on top of the memory and resources allocated to the underlying application. This would allow us to simply pass an expression to be evaluated to the embedded language’s interpreter. However, either these languages were easily embeddable and their requirements surpassed the nRF51822’s capabilities, or the process of porting them was far too complex. The chosen solution was to use a small number of efficient, tiny libraries that, put together, constituted a, somewhat limited, but functional, interpreter. Having the "intelligence" of the system in the MCU gives us several advantages. The increased battery life that comes with using BLE for communication mainly stems from the fact that it usually communicates at low power and for limited amounts of time. BLE devices can go for weeks or even months without establishing a connection, which is the most taxing in terms of energy use when compared with undirected advertisements. By having all of the processing done locally on the MCU we are, in fact, conserving battery life, since the Android smartphone needs only to be connected for configuration and ranging purposes. This also allows the system to work "offline". Since the smartphone doesn’t need to be connected for data processing to happen, this allows the MCU to do its job without having a connection active either to a central server or to the smartphone. This allows for a "fire and forget" kind of operation, where one leaves rules and simply allows the MCU to apply them. This, together with IP connectivity, gives this system great flexibility. 5.2 Components 43 Example string to evaluate: “Distance < 10” Parse the string for variables corresponding to Characterisic User Descripions Match is found Replace text with value loaded from corresponding characterisic (e.g. 2) Final string: “2 < 10” Figure 5.6: First stage of interpreting a rule 44 The BlueWarnAAL solution Figure 5.7: Flowchart of the different stages of rule processing for an example situation where the user is 5 m away from the Pandlet. The different steps of rule processing are presented in Fig. 5.7. The first stage of processing a rule (e.g. Distance <10), is to find variables, i.e. substrings, that match Characteristic User Descriptions, and replace those substrings with the current values of the corresponding characteristics. A diagram corresponding to this process can be consulted in Fig. 5.6 and the matter is discussed more in-depth in Section 5.2.1.4. The second stage is to convert the resulting mathematical expression from inflix notation (common arithmetic expression notation) into postfix notation or Reverse Polish Notation (RPN). This is necessary because it is far less complex to evaluate expressions in that notation, simply leveraging a basic stack as the underlying data structure. In Fig. 5.8 the example string 2 <10 is converted into its RPN equivalent, 2 10 <. This is further discussed in Section 5.2.1.5. The final stage is to parse the resulting RPN expression into a final result. This is also accomplished with a stack, and is further discussed in Section 5.2.1.6. Once we have the final result, true or f alse one simply loads this value into the corresponding Output Characteristic and sets the corresponding actuator value, as can be seen in Fig. 5.9. 5.2.1.4 String Replacement Algorithms There is no standard C function to search a string for a certain substring and replace it (akin to Java’s String.replace). This is mainly due to the fact that replacing a substring with another substring may or may not involve memory reallocation depending on the size of the new substring in relation to the old substring. Nevertheless, this problem is left to be solved by the programmer. In our case, the Boyer-Moore string search algorithm was initially used to search for substring occurrences and return a pointer to the instance of the substring, being the string subsequently replaced, with memory kept, expanded or freed depending on what was necessary. This approach, however efficient CPU-wise, proved not to be very efficient in terms of used-up RAM. Since this was our main bottleneck (having only about 4 kB free), we opted for a more RAM efficient, custom, alternative. 5.2 Components 45 String “2 < 10” Convert to Reverse Polish Notaion Obtain “2 10 <” Figure 5.8: Second stage of interpreting a rule String “2 10 <” Evaluate string for result Obtain “1” or “true” Set corresponding BLE output characterisic to “1” Set actuator to “on” state Figure 5.9: Third and last stage of interpreting a rule 46 The BlueWarnAAL solution Boyer-Moore string search algorithm The Boyer-Moore string search algorithm was developed by Robert S. Boyer and J Strother Moore, both members of faculty of the University of Texas at Austin. It is a fast algorithm and is considered the standard benchmark for performance in string searching algorithms. The Boyer-Moore algorithm requires pre-computation of a so-called "Bad Match Table", from the pattern that is to be searched. The Bad Match Table is calculated by assigning a value to each unique letter present in the pattern calculated by max(1,patternlength −index −1), only being stored the value for the last occurrence of the letter, the table is then suffixed with the character ∗, repenting "every other letter" and having a value equal to the length of the pattern. A special case is the last letter in the word, that either keeps its value if it has already been defined (having other occurrences), or the length of the pattern is attributed as its value. We will take the pattern "tooth" in the string "trusthardtoothbrushes" as an example, taking inspiration from [91]. The Bad Match Table for "tooth" can be consulted in Fig. 5.10. T O O T H 0 1 2 3 4 Letter T O H * Value 4 1 3 2 5 5 1. T: 5−0−1=4 2. O: 5−1−1=3 3. O: 5−2−1=2 4. T: 5−3−1=1 5. H:length =5 Figure 5.10: Bad Match Table and calculation process One essentially begins the process by aligning the pattern with the string and matching the last character in the pattern with the character in the string (Fig. 5.11a), since there is no match, one looks up the letter from the string in the Bad Match Table. In this case, the letter agains witch there was no match was the letter T, that has a value 1 in Fig. 5.10, so one advances the pattern in relation to the string by 1, this method aligns the T in the text with the last T in the pattern. If the letter isn’t present explicitly in the table, it will match against the asterisk and have a value of 5. After the first iteration, a match is found for the letter H, as can be seen in Fig. 5.11b. One starts to match the pattern against the string backwards. In this case, the pattern matches until we reach the letter S in the string (Fig. 5.11c). When the mismatch is found, one looks up the next "jump" by looking up the value for H, since this was the first letter that was matched. As can be seen in Fig. 5.11d, after the jump the letter H is mismatched against the letter O. Looking up O in the Bad Match Table, we get a next jump of 2, resulting in Fig. 5.11f with yet another mismatch at T. So, we advance the pattern by 1. 5.2 Components 47 T R U S THARDTOOTHBRUSHES T O O T H (a) First algorithm iteration T R U S T HARDTOOTHBRUSHES T O O T H (b) Second algorithm iteration T R U ST H ARDTOOTHBRUSHES T O OT H (c) Backwards matching, mismatch is found at S T R U S T H A R D T OO T H B R U S H E S T O O T H (d) Backwards matching, mismatch is found at S T R U S T H A R D T OO T H B R U S H E S T O O T H (e) Fourth iteration T R U S T H A R D T O O THBRUSHES T O O T H (f) Fifth iteration TRUSTHARDT O O T H B R U S H E S T O O T H (g) Sixth and final iteration, match is found Figure 5.11: The different stages of the Boyer-Moore algorithm on an example string In the algorithm’s sixth iteration (Fig. 5.11g) a match is found for the pattern. The last index of the matched substring can then be returned, and its first index corresponds to lastindex −length. The algorithm can continue until the end of the string is found, thereby returning all occurrences of a particular substring. This algorithm has a good performance for most string searching applications, however it has a worst case On2complexity [92,93]. Custom Alternative The custom alternative we present here is based off the, so called, naïve string search algorithm. One simply iterates over the string’s characters for the first character of a pattern. One then continues iterating over the string for the remaining characters in the pattern. If all characters are successfully matched, a match for the pattern is found, if not, one simply continues iterating over the string. Despite its obvious disadvantages, including an average O(n2) complexity, we found it to be the most simple in ease of implementation, in code footprint and on, already strained, MCU resources. A flowchart for this algorithm can be consulted in Fig. 5.12. 48 The BlueWarnAAL solution Start with string to search, patern to be searched for and index “i=0” Grab character from string’s index “i” Character matches first character of patern? Increment “i”N End of string?N End Y Increment “i” Set index “j=1” Y End of string? Y Grab character from string’s index “i” and patern’s index “j” Characters match? End of patern?Y Match found Y Increment “i” and “j” N N N Figure 5.12: The naïve algorithm 5.2 Components 49 (((3 + 6) ×(2 −4)) + 7) 3 6 + 2 4 − × 7 + Figure 5.13: Arithmetic expression in common inflix notation (above) and its equivalent expression in postfix notation (below) [94] 5.2.1.5 Transforming a mathematical expression into Reverse Polish Notation So that one is able to efficiently parse an expression in a computer, one has to first convert it from inflix notation to postfix, or Reverse Polish, notation (see Fig. 5.13 for an example). In this type of notation no parentheses are used to establish operator precedence, it is solely specified by the order in which the members are ordered. Evaluation of expressions of this type is explained in Section 5.2.1.6. The conversion from inflix notation to postfix notation can be done using the Shunting-Yard algorithm. This stack-based algorithm was invented by Edsger Dijkstra, renown computer scientist, in the ’60s, and first described in [95]. It gets its name from its operation resemblance to the method in which railroad cars are sorted in some railroad yards called "shunting-yards". In addition to supporting unary and binary operations this algorithm also supports functions, making it extremely versatile. The algorithm requires two variables: the input and the output, in addition to an auxiliary stack in which to hold operators that haven’t been added to the output. It also requires a table in which operators are stored and that stores the operator type (unary, binary, or function) and its associativity (left or right). This algorithm has O(n)running time complexity [96]. The operation of this algorithm is descibed in Fig. 5.14. The code that was used in our solution is a modified version of this [97] C Shunting-Yard implementation. 5.2.1.6 The Recursive Descent Parser Having the expression to be evaluated in the correct notation, it is necessary to do the actual evaluating. This is done with a Recursive Descent Parser. Expressions in this notation are evaluated from left to right. One essentially iterates over the expression until one finds an operator. That operator is applied to the two operands (numbers) before it. One goes back to the beginning of the expression and starts over until only one operand is left (the final result) and the expression is successfully evaluated. A step by step evaluation of an equation can be consulted in Fig. 5.15 [98] and the flowchart for this algorithm can be consulted in Fig. 5.16. 56 The BlueWarnAAL solution Applicaion is launched Loading screen Bluetooth device list acivity Bluetooth acive? Y Prompt user to acivate Bluetooth N Connect to Device Device compaible? N Rule List acivity Y Seings prompt Modify Rules Change device name Scan for devices From this point the devices are connected and distance informaion is obtained at the MCU Figure 5.19: Android application UI flow pretty straightforward. After this, the RabbitMQ server is ready to accept connections either using the AMQP protocol or the MQTT protocol. 5.2.3.2 Python application Since support for this kind of connectivity is still very much recent, connecting to 6LoWPAN enabled devices has to be instructed to the Linux kernel running on the Raspberry Pi via commands echoed to the /sys/kernel/debug/bluetooth/6lowpan_psm file, as can be consulted in [102], it was chosen to develop a Python-based application to control to which devices the Raspberry Pi connected and subsequently offered a 6LoWPAN connection to the Internet. This application leverages the hcidump and hcitool lescan shell utilities to obtain a dump of scanned BLE advertisement packets, and then parses them to figure out what packets are pertaining to our application and which packets can be simply discarded. It then calls for the Linux kernel to connect to these selected devices and to allow for them to have an Internet connection for about 30 s. It then promptly disconnects and iterates over to the next BlueWarnAAL device that it has found from advertisements. It repeats this process until all nodes have had 30 s to talk to the Middleware, it then sleeps for about 30 min and repeats this process. This allows for all nodes to be able to talk to the Middleware in regular intervals. Since the MQTT specification calls for every 5.2 Components 57 node to be able to store up to a limited number of messages [103] this introduces some latency in the system, but allows for automated rotation of Internet access for all nodes without any type of user intervention. This is necessary since this connection has to be initiated by the Raspberry Pi. 58 The BlueWarnAAL solution Chapter 6 Testbed and Results In this section we present the process that was undertaken to test out the BlueWarnAAL system. 6.1 The proposed scenario The main use case scenario, as presented in Section 1.1, is considered for testing. To simulate a real-world environment, a testbed was developed. The development process can be consulted in Section 6.1.1. 6.1.1 The testbed The testbed was planned to simulate, on a small scale, real world functioning of the system. Essentially, this testbed is a small table with AC power connections, a power switching circuit and the Fraunhofer Pandlet. Any type of ordinary home appliance can be connected to the AC power outlet and work exactly like it would normally, with one crucial exception: AC power can be switched on or off via the power circuit, that is connected to the Fraunhofer Pandlet, depending on the rule configured on the Pandlet by the user. 6.1.1.1 Planning Planning consisted of two phases: designing the power circuit and designing the table. The power circuit The objective of this circuit is to allow for the MCU, with the help of a relay, to switch the appliance on or off. The schematic for the circuit can be seen in Fig. 6.1. It is very simple and includes only 5 components: a resistor, a NPN Bipolar Junction Transistor (BJT), a diode, a Zenner diode and a relay. All the components besides the relay are only there for protection against current spikes that are common when relays switch on or off. After the circuit’s design was decided on, it was simulated using National Instruments (NI)’s Multisim software (Fig. 6.2). The 10 Ωresistor is meant to simulate a 2.2 kW load. Current 59 60 Testbed and Results Figure 6.1: Schematic of the power switching circuit incorporating a relay probes (virtual devices that convert amperage to voltage, so that one is able to measure current in an oscilloscope) were attached in places deemed critical. The simulation confirmed that the circuit worked as expected. In Fig. 6.3 one can see the output waveform as measured at the load, having the switch S1 been toggled. As expected voltage drops to 0 when the switch is turned off. As can be seen in Fig. 6.4, the current in the diode branch spikes (negatively due to inversed polarity from the oscilloscope referential) when the circuit is switched. However, there are no current spikes in the BJT, it can therefore be concluded that the circuit is working as expected. Finally, having the circuit been validated via simulation, the required components were ordered. The bill of materials is available in Table 6.1. Description Product Zener Diode Central Semiconductor CZ5344B TR BJT Central Semiconductor 2N3904 Diode NXP Semiconductors BYV29FX-600,127 Relay TE Connectivity T9AS1D12-5 Table 6.1: Circuit bill of materials 6.2 Functional tests The system was tested with the following procedure: 1. The system was turned on (with the default rule of Distance <10) and with an led connected to the actuator output; 6.3 Distance estimation tests 61 Figure 6.2: The circuit recreated in NI’s Multisim 2. One stood close to the MCU and progressively stepped back until the LED turned off. One would then measure the distance to the MCU; 3. The distance rule in the MCU was changed, and the procedure repeated. The system was deemed accurate with an error of about 2 m, up to a distance of about 70 m with a clear line of sight. Without line of sight the error rate after a distance of 20 m makes the system unusable. However, for our purposes, the system is reliable enough. 6.3 Distance estimation tests Two tests were conducted to ascertain the accuracy of the distance estimation algorithm: one was conducted in open space (Fig. 6.5), and one, in a 70 m long corridor (Fig. 6.7). The open space results were satisfactory, with a small error in relation to the real distance. The corridor tests showed a behaviour that was expected: Bluetooth location based on RSSI is prone to errors due to reflexions and refractions. The corridor in which the measurements were taken (Fig. 6.6) acts as a wave guide, and leads to stronger RSSI measurements than would be expected in open space. 62 Testbed and Results Figure 6.3: Oscilloscope plot of voltage at the load 6.4 Connectivity tests The connectivity tests that were conducted essencialy consisted on running the Raspberry Pi app and verifying whether there was IPv6 connectivity. As can be seen from Fig. 6.8, this was, effectively the case, since IPv6 Neighbour Solicitations and Router Announcements were traded between the Raspberry Pi and the Norcic MCU. 6.4 Connectivity tests 63 Voltage at BJT collector Current at diode branch Current at BJT collector Not connected Figure 6.4: Voltage and current for different points in the circuit, being the relay switched throughout. For current measurements 1mA =1V Figure 6.5: Open space plot of estimated distance Figure 6.6: Fraunhofer Portugal’s main corridor (first floor) 64 Testbed and Results Figure 6.7: Corridor plot of estimated distance Figure 6.8: TCPDump utility output during connection with the Nordic MCU Chapter 7 Conclusion In this dissertation we were able to develop a complete, peer to peer, assisted living solution to help the elderly in their daily lives. As was discussed in Chapter 5, this solution was developed in three fronts: on the Nordic nRF51822, on the Raspberry Pi and on an Android smartphone. Although these systems are very much different, the BLE technology was instrumental on allowing these systems to talk to each other and to convey state information while keeping energy consumption down. The Smart Companion library allowed us to develop a powerful, yet extremely simple and usable application without having to worry about the tried and tested graphical design. Bleeding edge technology such as the Nordic’s IoT stack and the Linux kernel’s support for 6LoWPAN, allowed us to pave the way for future scalability. Our main achievements are exposed in Section 7.1 and future work in Section 7.2. 7.1 Achievements •Nordic: – Distance: We were able to accurately estimate distance from a Bluetooth client to our MCU based only on RSSI; – Rule engine: A completely functional rule engine was developed that was capable of evaluating rules customizable by the user; –IP stack: The LwIP IP stack was set up correctly and is able to send and receive packets; •Android: A functional UI for interacting with the system was developed; •Raspberry Pi: An application that is able to automate the process of connecting to various nodes was developed; •Scalling:IPv6 connectivity was assured. 65 72 REFERENCES [33] S. Appel, K. Sachs, and A. Buchmann, “Towards benchmarking of AMQP”, in Proceedings of the Fourth ACM International Conference on Distributed Event-Based Systems, ACM, 2010, pp. 99–100. [34] M. Hadlow, Message Queue Shootout!, 2011. [Online]. Available: http://mikehadlow. blogspot.pt/2011/04/message-queue-shootout.html (visited on 02/02/2015). [35] M. Salvan, A quick message queue benchmark: ActiveMQ, RabbitMQ, HornetQ, QPID, Apollo... [Online]. Available: http://blog.x-aeon.com/2013/04/10/a-quickmessage-queue-benchmark-activemq-rabbitmq-hornetq-qpid-apollo/ (visited on 12/07/2014). [36] M. Klas, “Porovnání protokol˚u pro M2M komunikaci.”, Masarykova Univerzita, 2014, p. 42. [37] Gilles Thonet, “ZigBee FAQ”, vol. 1, no. 7, pp. 1–7, 2006. [38] IEEE Computer Society, Part 15.1: Wireless medium access control (MAC) and physical layer (PHY) specifications for wireless personal area networks (WPANs), June. 2005, vol. 2005, ISBN: 0738147079. DOI:10.1109/IEEESTD.2003.94389. [39] G. Fleishman and Ars Technica, UWB group shutters, sends tech to Bluetooth, USB groups, 2009. [Online]. Available: http : / / arstechnica . com / gadgets / 2009 / 03 / ultrawideband-groups-disbands-doesnt-despair/ (visited on 02/03/2015). [40] B. news, Bluetooth rival unveiled by Nokia, 2006. [Online]. Available: http://news. bbc.co.uk/2/hi/technology/5403564.stm. [41] Bluetooth SIG, Bluetooth Smart Beacons in Retail, 2015. [Online]. Available: http : //www.bluetooth.com/Pages/beacons-retail-location.aspx (visited on 02/03/2015). [42] ——, Bluetooth technology creates huge opportunities in medical, 2015. [Online]. Available: http://www.bluetooth.com/Pages/Health-Wellness-Market.aspx (visited on 02/03/2015). [43] ——, Bluetooth Technology Makes Wireless Home Automation Possible, 2015. [Online]. Available: http://www.bluetooth.com/Pages/Smart-Home-Market.aspx (visited on 02/03/2015). [44] ZigBee Alliance, ZigBee Specification FAQ. [Online]. Available: http://old.zigbee. org/Specifications/ZigBee/FAQ.aspx. [45] Nordic Semiconductor, “nRF24L01+ Product specification v1.0”, vol. 21, no. September, pp. 21–22, 2008. DOI:10.1080/09613219308727250. [Online]. Available: https: //www.nordicsemi.com/eng/Products/2.4GHz-RF/nRF24L01P. [46] WPAN IEEE 802.15 3c Task Group, IEEE 802.15 WPAN Task Group 3c (TG3c) Millimeter Wave Alternative PHY, 2009. [Online]. Available: http://www.ieee802.org/ 15/pub/TG3c.html (visited on 02/03/2015). REFERENCES 73 [47] “IEEE Standard for Information Technology - Telecommunications and Information Exchange Between Systems - Local and Metropolitan Area Networks - Specific Requirements Part 15.3: Wireless Medium Access Control (MAC) and Physical Layer (PHY) Specifications f”, IEEE Std 802.15.3-2003, 0_1–315, 2003. DOI:10.1109/IEEESTD. 2003.94395. [48] IEEE Computer Society, 60 GHz WPAN, PHY and MAC. 2009, ISBN: 9780738160504. [49] L. Yuansheng and H. Xi, Analysis of the Maximal Transmission Rate Based on NRF24L01 Chip System, 2010. DOI:10.1109/ICIECS.2010.5678223. [50] C.-H. Hallard, NRF24L01 real life range test, 2013. [Online]. Available: http://hallard. me/nrf24l01-real-life-range-test/ (visited on 02/05/2015). [51] A. Opel, “Bluetooth - Authentication - Authorisation - Encryption”, p. 1, 2003. [52] Atmel, “Atmel AT02845 : Coexistence between ZigBee and Other 2.4GHz Products”, Application Note, 2013. [53] R. Balani, “Energy consumption analysis for bluetooth, wifi and cellular networks”, Networked & Embedded Systems Laboratory, NESL Technical Report TR-UCLA-NESL-20071201, 2007. [54] ATMEL, “AT03663 : Power Consumption of ZigBee End Device”, 2014. [55] D. P. Consumption, D. Halperin, B. Greenstein, A. Sheth, and D. Wetherall, “Demystifying 802.11n Power Consumption”, Proceedings of the 2010 Workshop on Power Aware Computing and Systems (HotPower’10), pp. 2–6, 2010. DOI:10.1.1.173.7044. [56] Android Developers, What is Android, 2011. [Online]. Available: http://developer. android.com/guide/basics/what-is-android.html. [57] AOSP, ART and Dalvik | Android Developers. [Online]. Available: http://source. android.com/devices/tech/dalvik/ (visited on 02/05/2015). [58] Microsoft, Windows 10 for Raspberry Pi 2, 2015. [Online]. Available: https://dev. windows.com/en-us/featured/raspberrypi2support (visited on 02/05/2015). [59] Raspberry Pi Foundation, What is a Raspberry Pi? [Online]. Available: http://www. raspberrypi.org/help/what-is-a-raspberry-pi/ (visited on 02/05/2015). [60] ——, “Raspberry Pi Model B+ datasheet”, p. 1, 2014. [61] ——, Raspberry Pi Compute Module: new product!, 2014. [Online]. Available: http: //www.raspberrypi.org/raspberry-pi-compute-module-new-product/ (visited on 02/05/2015). [62] Marvell Technology Group, “Sheeva Plug”, 2012. [Online]. Available: https://www. globalscaletechnologies.com/p-46-sheevaplug-dev-kit.aspx. [63] Marvel Semiconductor, “Marvell MV78200 SoC with Sheeva Technology”, pp. 1–2, 74 REFERENCES [64] PlugPBX Project, About. [Online]. Available: http://www.plugpbx.org/ (visited on 02/06/2015). [65] Memsic, “TelosB datasheet”, 2013. [Online]. Available: http://www.memsic.com/ userfiles/files/DataSheets/WSN/telosb%5C_datasheet.pdf. [66] Texas Instruments, “2.4-GHz Bluetooth ® low energy System-on-Chip”, no. June, 2013. [67] Nordic Semiconductor, nRF51822 Product Specification v3.1, 2014. [68] J. Figueiras, H. Schwefel, and I. Kovacs, “Accuracy and timing aspects of location information based on signal-strength measurements in Bluetooth”, in Personal, Indoor and Mobile Radio Communications, 2005. PIMRC 2005. IEEE 16th International Symposium on, vol. 4, 2005, 2685–2690 Vol. 4. DOI:10.1109/PIMRC.2005.1651931. [69] M. Barahim, “Low-cost bluetooth mobile positioning for location-based application”, Internet, 2007. ICI 2007. . . ., 2007. [Online]. Available: http://ieeexplore.ieee. org/xpls/abs%5C_all.jsp?arnumber=4401707. [70] S. Malik and H. Maidasani, Cat Gear, College Park, 2014. [Online]. Available: http: //cmsc838f-s14.wikispaces.com/Cat+Gear. [71] C. H. O. Hyunggi, K. Myungseok, K. I. M. Jonghoon, and K. I. M. Hagbae, “Zigbee based location estimation in home networking environments”, IEICE transactions on information and systems, vol. 90, no. 10, pp. 1706–1708, 2007. [72] W.-H. Kuo, Y.-S. Chen, G.-T. Jen, and T.-W. Lu, “An intelligent positioning approach: RSSI-based indoor and outdoor localization scheme in Zigbee networks”, in Machine Learning and Cybernetics (ICMLC), 2010 International Conference on, vol. 6, 2010, pp. 2754–2759. DOI:10.1109/ICMLC.2010.5580783. [73] J. Rekimoto, T. Miyaki, and T. Ishizawa, “LifeTag: WiFi-based continuous location logging for life pattern analysis”, in LoCA, vol. 2007, 2007, pp. 35–49. [74] R. Paradiso, G. Loriga, and N. Taccini, “A wearable health care system based on knitted integrated sensors”, Information Technology in Biomedicine, IEEE Transactions on, vol. 9, no. 3, pp. 337–344, 2005, ISSN: 1089-7771. DOI:10.1109/TITB.2005.854512. [75] Fundació Privada CETEMMSA, Telefónica Investigación y Desarrollo, INESC Porto – Instituto de Engenharia de Sistemas e Computadores do Porto, University of Plymouth Enterprise Ltd, University of Limerick, Corscience GmbH & Co KG, Fundació Hospital Comarcal Sant Antoni Abat, Fraunhofer Portugal, L. TeleMedic Systems, Zentrum für Kardiovaskuläre Telemedizin GmbH, and G. National University of Ireland, “eCAALYX”, 2009. [Online]. Available: http://www.aal-europe.eu/projects/ecaalyx/. [76] Fraunhofer Portugal AICOS, BCB Informática y Control SL, Università degli Studi di Ferrara, KOHS PIMEX, Portugal Telecom Comunicações, Ab.Acus Srl, Grado Zero Espace, and K. RK Tech, “Clockwork”, 2014. [Online]. Available: http://www.aaleurope.eu/projects/clockwork/. REFERENCES 75 [77] Scuola Universitaria Professionale della Svizzera Italiana (SUPSI), D. d. E. e. I. Politecnico di Milano, Info Solution SpA, VCA Technology Ltd., Istituti Sociali di Chiasso, Clinica Hildebrand, and University of Wurzburg, “ALMA”, 2013. [Online]. Available: http://www.aal-europe.eu/projects/alma/. [78] C. Styles and ARM Ltd, mbed FAQs, 2010. [Online]. Available: https://developer. mbed.org/media/uploads/chris/mbedqa%5C_v1.0.pdf. [79] Nordic Semiconductor, “nRF51822 Evaluation Kit User Guide v1.2”, 2013. [80] ——, Introduction to the S110 SoftDevice, 2011. [Online]. Available: https://devzone. nordicsemi.com/documentation/nrf51/4.2.0/html/group%5C_%5C_ nrf518%5C_%5C_lib%5C_%5C_ble%5C_%5C_s110%5C_%5C_intro.html. [81] Region RAM overflowed with stack - Nordic Developer Zone. [Online]. Available: https: //devzone.nordicsemi.com/question/38781/region-ram-overflowedwith-stack/ (visited on 06/15/2015). [82] ——, nRF51 IoT SDK Documentation. [Online]. Available: https : / / developer . nordicsemi . com / nRF51 % 5C _ IoT % 5C _ SDK / doc / iot / html / index . html (visited on 06/16/2015). [83] J. Hui and P. Thubert, “RFC 6282”, 2011. [84] Nordic Semiconductor, nRF51 SDK for Internet of Things applications using Bluetooth Smart. [Online]. Available: https : / / www . nordicsemi . com / eng / Products / Bluetooth - Smart - Bluetooth - low - energy / nRF51 - IoT - SDK (visited on 06/15/2015). [85] lwIP - A Lightweight TCP/IP stack - Summary [Savannah]. [Online]. Available: https: //savannah.nongnu.org/projects/lwip/ (visited on 06/16/2015). [86] E. Stock, Memory, 2015. [Online]. Available: https://github.com/eliotstock/ memory. [87] Fraunhofer Portugal, Smart Companion UI Design & SC-Lib, 2014. [88] What’s the maximum size for an advertisement package? - Nordic Developer Zone. [Online]. Available: https://devzone.nordicsemi.com/question/75/whatsthe-maximum-size-for-an-advertisement-package/ (visited on 06/19/2015). [89] Radius Networks, AltBeacon Protocol Specification v1.0, 2015. [Online]. Available: https: //github.com/AltBeacon/spec. [90] E.-E.-L. Lau, B.-G. Lee, S.-C. Lee, and W.-Y. Chung, “Enhanced RSSI-based high accuracy real-time user location tracking system for indoor and outdoor environments”, International Journal on Smart Sensing and Intelligent systems, vol. 1, no. 2, pp. 534–548, 2008. [91] M. Slade, Boyer Moore Horspool Algorithm - YouTube, 2014. [Online]. Available: https: //www.youtube.com/watch?v=PHXAOKQk2dw (visited on 06/22/2015). 76 REFERENCES [92] R. S. Boyer and J. S. Moore, “A fast string searching algorithm”, Communications of the ACM, vol. 20, no. 10, pp. 762–772, 1977. [93] A. Hume and D. Sunday, “Fast string searching”, Software: Practice and Experience, vol. 21, no. 11, pp. 1221–1248, 1991. [94] L. Olimex, Weekend Programming Challenge Issue 16 – Infix to Postfix converter. [Online]. Available: https://olimex.wordpress.com/2013/07/05/weekendprogramming-challenge-issue-16-infix-to-postfix-converter/ (visited on 06/23/2015). [95] E. W. Dijkstra, ALGOL-60 translation. Mathematisch Centrum, 1961. [96] Stack Overflow, c++ - What is the running time of the translation of infix to postfix using queue and stack? [Online]. Available: https://stackoverflow.com/questions/ 5305215/what-is-the-running-time-of-the-translation-of-infixto-postfix-using-queue-and (visited on 06/28/2015). [97] Rosetta Code, Parsing/Shunting-yard algorithm. [Online]. Available: http://rosettacode. org/wiki/Parsing/Shunting-yard%5C_algorithm (visited on 06/23/2015). [98] S. R. Schmitt, RPN Calculator, 2004. [Online]. Available: http://www.abecedarical. com/javascript/script%5C_reverse%5C_polish.html (visited on 06/23/2015). [99] Rosetta Code, Parsing/RPN calculator algorithm. [Online]. Available: http://rosettacode. org/wiki/Parsing/RPN%5C_calculator%5C_algorithm%5C#C (visited on 06/23/2015). [100] A. Dobie and Android Central, Bluetooth Low Energy support coming to future Android version | Android Central. [Online]. Available: http : / / www . androidcentral . com/bluetooth-low-energy-support-coming-future-android-version (visited on 06/23/2015). [101] Stack Overflow, bluetooth lowenergy - Does BluetoothLeAdvertiser work on a Nexus 5 with Android 5.0? - Stack Overflow. [Online]. Available: https://stackoverflow. com/questions/26441785/doesbluetoothleadvertiserworkonanexus-5-with-android-5-0/26441948%5C#26441948 (visited on 06/28/2015). [102] Nordic Semiconductor, nRF51 IoT SDK Documentation, 2014. [103] OASIS, MQTT Version 3.1.1. [Online]. Available: http://docs.oasis-open.org/ mqtt/mqtt/v3.1.1/mqtt-v3.1.1.html (visited on 06/28/2015). [104] Nordic Semiconductor, IoT SDK v0.8.0 Changelog, 2015. [Online]. Available: https: //www.nordicsemi.com/eng/nordic/Products/nRF51-IoT-SDK/nRF51IoT-SDK-zip/41601 (visited on 06/26/2015). [105] A. Dunkels, uIP, 2013. [Online]. Available: https://github.com/adamdunkels/ uip (visited on 06/29/2015). REFERENCES 77 [106] O. Schneider, Pimatic, 2014. [Online]. Available: http://pimatic.org/ (visited on 06/26/2015).