· · · Institutional Repository

Writing software for Wireless Sensor Networks (WSN) is hard, as programmers have to write robust, distributed, highly concurrent applications on extremely resource limited devices. Virtual machines offer among other things support for high-level object-oriented languages, dynamic memory management and protection, hardware abstraction, and efficient code distribution. The main challenge is to ensure good programming tools and a minimal footprint for the virtual machine to match the limited amounts of memory available on typical WSN platforms. This thesis describes the design and implementation of Darjeeling, a virtual machine modelled after the Java VM and capable of executing a substantial subset of the Java language, but designed specifically to run on 8- and 16-bit microcontrollers with 2-10kB of RAM. The Darjeeling VM uses a 16- rather than a 32-bit architecture, which is more efficient on the targeted platforms. Darjeeling features a novel memory organisation with strict separation of reference from non-reference types that eliminates the need for run-time type analysis in the underlying precise garbage collector. Darjeeling also includes a linked stack model that provides light-weight threads, compacting garbage collection, and synchronization. The VM has been implemented on three different platforms, and was evaluated with micro benchmarks as well as a real-world monitoring application. The latter includes a pure Java implementation of the Collection Tree Protocol (CTP) conveniently programmed as a set of cooperating threads, and a reimplementation of an existing environmental monitoring application. The results show that Darjeeling is a viable solution for deploying large-scale, heterogeneous sensor networks.

Team members of the Hydrogen Racing Team Delft have participated in the development and building of the fourth generation Forze fuel cell powered racing vehicle. This report describes the development process of the software for this vehicle.

In recent years, large-scale systems have become mainstream at a very high pace. Typical examples of large-scale systems are MANETs, Wireless Sensor Networks, Pervasive Computing, Swarm Robotics, etc. These systems distinguish them- selves by the large number of devices they embody, and emergent behaviors they exhibit: Behavior that is globally perceivable, but that is made up of only local interactions of the system elements. Because of the vast amount of devices that make up a large-scale system, it is infeasible to exhibit centralized control. As an alternative, we need to leverage distributed algorithms to create and control emergent behaviors for the global goal we want the system to exhibit. Since there is no linear mapping from local interactions to global behavior, we present a global-to-local compiler to automatically generate these distributed algorithms for large-scale systems. By using Genetic Programming to combine already known building blocks from other distributed algorithms, we provide a high-level, goal-driven framework for algorithm designers to design distributed algorithms. Evaluation shows that the framework we present is indeed a valuable tool for designing distributed algorithms for large-scale systems. Improving the develop- ment speed, allowing the designer to be agnostic to the underlying details, but nevertheless providing a flexible interface, to acquire the algorithm desired.

In recent years, application domains outside information technology such as architecture have shown an increasing interest in the capabilities of networked systems such as localized computation, reduced power-consumption, and distributed interaction. These capabilities incline the design of interactive environments towards the IT-domain. In particular the employment of large scale distributed systems in interactive designs bring along new challenges for architects/designer such as distributed algorithm design, programming skills, embedded platform knowledge. As a consequence of this new trend, adequate software tools to bridge the gap between the IT-world and the field of interactive design are scarce. In order to fill that gap we propose a framework called Interactive Design Studio(IDS) which aims to provide the necessary tools to hide the technological aspects from the end-user when designing interactive environments. To tackle the problem of handling large scale networks of embedded platforms we are convinced that spatial computing is a promising paradigm. The main reasons are the scalability(network size does not influence node behavior) and resiliency to network dynamics(network is hidden by space abstraction). Therefore we present a spatial computing framework for non-IT specialists. We provide a way to specify agent-level behavior and to generate the corresponding code for a specific embedded platform. In our case, we use the eLua VM enhanced with the necessary spatial computing capabilities. We show that spatial computing is a good methodology for Industrial Design and Architecture. Moreover, we show that spatial computing is possible using off-the-shelf virtual machines for embedded platforms. In conclusion, we demonstrate that IDS succeeds within a certain extent in abstracting or hiding the underlying technological aspects(spatial computing) from end-users.

At Mechatronics in Medicine (MiM) Laboratory of Imperial College London, a neurosurgical steerable flexible probe ( STING) that is used to access deep brain lesions through curved trajectories is currently being developed. The focus of my research project is mainly on trajectory planning of the flexible probe i.e. investigation on how to increase efficiency and performance of the trajectory planning. Some experiments have been thoroughly done to measure the performance of a well known sampling based path planning method, Reachability-Guided Rapidly-exploring Random Tree (RG-RRT). The first step to improve the performance was to migrate from MATLAB to Python-C++ which yielded 12-13 times performance speedup. Besides taking a close look at the software implementation details, the second step was to improve the algorithm by implementing a waypoint cache and exploiting some parallelization techniques. The parallelization techniques cover multi-core CPU (OR parallel, AND parallel, OR+AND parallel and Manager-Worker) and GPGPU techniques. At the end of my research project, RG-RRT with waypoint cache was experimentally able to reach 4 times performance speedup, while parallelization on multi-core CPU with AND parallel technique has shown the most significant result by obtaining approximately 5 times performance speedup. The other parallelization, which was done through the use of an NVIDIA CUDA-enabled GPU, has successfully obtained 10 times performance speedup. Despite its higher rate of performance speedup, later it was shown that GPGPU technique suffers the most from inefficiency due to I/O bottleneck that is caused by device-host memory transfer.

We can foresee a near-future scenario where a huge number of semi-intelligent devices are part of our everyday environment, our homes, the public places and the office as well. The intelligent thermostat uploads the temperature readings to an online database; the fridge sends a tweet when we are out of milk; the coffee machine texts us when the coffee is ready. Each device has a unique and individual purpose. But what if they could be grouped together as a so-called accidental infrastructure to serve a more advanced cause? We have set out to demonstrate the possibilities of such an accidental infrastructure in the field of indoor localization. An ambient device in itself is not intentionally prepared for localization purposes, but using many of them together and combining the collected data can surpass the devices' limited individual capabilities. Our approach was to build a prototype system based on a homogeneous array of radio-connected nodes and an additional entity with a higher magnitude of computing power. This central entity then controls the data collection from the nodes and executes a custom localization algorithm, based on probabilistic methods and a Kalman filter. We have evaluated our system both by simulations with ideal input data and by real-world measurements. The results show that the system is able to track and update the location estimates, but due to the heavy multipath effect it is only capable of very moderate improvements.

A fundamental problem in networked embedded systems is to know the runtime behaviour. Especially, the behaviour of self-organizing and adaptive systems is difficult to predict, because of the strong coupling with the environment. Monitoring this at runtime is difficult, because the only access is via the network. However, some properties need to be satisfied irrespective of the situation. Therefore the goal of this thesis is to monitor correctness properties at runtime efficiently. The focus is on temporal and distributed system-level properties. The system is modelled as a network of communicating finite-state machines, that operate asynchronous. Each node produces a stream of locally observable primitive events. High-level knowledge can be obtained by specifying an interest in temporal and distributed patterns in the events. From the specification an event detection tree is generated, which monitors the runtime behaviour by detecting the patterns. We show that event ordering is of fundamental importance for the implementation. To make efficient use of the scarce resources the tree is distributed in the network with a centralized distribution algorithm. A proof-of-concept is developed to evaluate the taken approach. Experiments run on a network of wireless nodes show that the cost of distributed monitoring is lower than when centralized in certain topologies. Simulations show that this is not the case with a random topology. Further, in the experiments only a few seconds delay is measured in the detection process. A limitation of the taken approach is that the unreliability of the network has a negative impact on the performance; missing events is an issue. Finally, the applicability is shown to the verification of an application for structural integrity monitoring.

The number of wireless sensor networks is constantly increasing. In the deployment phase of the WSNs projects it is common for failures to appear. These can be caused by software or hardware faults or by environmental factors. In order to find the source of these problems, the WSN needs to be inspected. Since the deployments of WSN are often made in inaccessible or hazardous area, the inspection operation can have a high degree of risk. In order to facilitate these intervention, the design and implementation of a WSN mobile monitoring tool is proposed.The tool is composed of an application built for a Neo FreeRunner smartphone which interfaces a TelosB mote via USB. The TelosB mote acts a sniffer and sends the data to the smartphone which analyzes it and displays packet information. The system is also able to use passive or active monitoring and track other nodes using a method of estimating distances to nodes using the RSSI value. The tool can be also used as a debugger for WSNs by replaying the last session and setting breakpoints. To evaluate this prototype, the localizing method is tested, together with the capacity of the sniffer mote process packets and the collision detection accuracy.

Wireless sensor and actuator networks (WSANs) suffer from interference making them unfeasible for actuators that require reliability. This asks for an IEEE 802.15.4 behavior analysis for building automation actuators and a robust WSAN solution. This thesis uses the IEEE 802.15.4 based JenNet communication stack for experiments to define, measure, and create robustness. Failures are classified between soft and hard to identify the impact on the system. Equations are introduced to show the failure probabilities based on packet arrival probabilities. Experiments show the impact of interference on the failure rate with an increased failure rate during office hours, and a ratio between hard and soft failures ranging from 1:5 to 1:25 for single hops depending on the link quality. A setpoint based heartbeat solution is proposed that solves hard failures and copes with soft failures. Equations show the impact of different heartbeat properties on the performance of the heartbeat solution. The solution is implemented and experiments show that it meets the robust properties required by WSANs. To make a WSAN predictable and adaptive to its environment, future implementations could monitor the environment and reconsider timing properties, based on gathered data and hopcount.

Software for networked embedded systems faces several challenges when the deployed network is subject to changing circumstances during operation. Typically, inter-node communication and network connectivity are two crucial aspects that are directly affected by dynamics such as failing wireless links and node mobility. Therefore, the embedded software has to adapt at runtime in order to account for these dynamics. This thesis investigates the possibilitiy of using decentralized algorithms for run-time adaptability in dynamic wireless networks. Aimed at real-world scenarios, this thesis presents a class of decentralized algorithms that exploit the power of collaborative processing between nodes to achieve adaptability.

Sensor nodes are small, autonomous, battery-powered devices that use a wireless network interface to communicate with other sensor nodes. Together these sensor nodes form a Wireless Sensor Network (WSN), which has the purpose to sense information about the environment. Before a WSN is deployed, it is tested using simulators and testbeds. Both simulators and testbeds are not able to fully capture all non-deterministic behaviour of the environment in which the WSNs are deployed. Passive inspection is an approach that detects problems within a WSN during deployment. Passive inspection makes use of the broadcast nature of wireless communication and is realised by overhearing messages sent by sensor nodes. The limitation of passive inspection is that operator of the WSN has to wait until a sensor node transmits a message and that this message contains the specific information is needed. To overcome this limitation active inspection can be used, and is realised by injecting messages into the deployment to force a reaction from a sensor node. The concept of passive inspection is not new and has already been evaluated in a simulator and presented in a demo. In this thesis we will further evaluate the practical use of passive inspection using real hardware and we will try to extend passive inspection with active inspection. In order to evaluate passive and active inspection, we designed and implemented an inspection network and an analysis tool. The evaluation compared the normal operation of a deployment with an operation containing a previously resolved bug. The result of this evaluation is that the analysis tool is clearly capable of detecting the previously resolved bug. In this way we showed that passive inspection would have been able to detect that problem when it occurred in a real-life deployment. The evaluation of active inspection showed that active inspection can be used without negatively effecting the behaviour of the sensor nodes in the deployment.

Wireless sensor networks (WSNs) are ad-hoc wireless networks of small form-factor embedded nodes with limited memory, processing, and energy resources. Certain applications, like security and art monitoring,require reliable data transport. Current work for WSNs only provides stochastic reliability or guaranteed reliability for bulk transfer. This thesis describes the design, implementation, and evaluation of Reliable Transport AODV (RT-AODV). RT-AODV is a protocol that provides guaranteed reliability for individual messages. Both routing and reliable transport are covered in this work. End-to-end positive acknowledgements with timeouts and retransmissions are used to provide guaranteed reliability. NST-AODV, an existing any-to-any routing protocol, is used to route the data and acknowledgement messages through the network. To enhance the stability and quality of NST-AODV some adjustments are done: the hardware specifc Link Quality Indicator (LQI) is replaced by a statistical link estimator, and a loop detection mechanism and route quality monitoring are added. A proof of concept implementation has been done on the Embedded Software group's testbed. Experiments of larger scale and longer duration were done in TOSSIM simulations. For evaluation, Reliable Transport AODV (RT-AODV) is compared to the Collection Tree Protocol (CTP) and NST-AODV. Results show that RT-AODV performs well compared to both NST-AODV and CTP. A serious cost increase (in terms of transmissions) is involved with using end-to- end acknowledgements. The strength of RT-AODV is not pure delivery ratio. For larger networks, it performs slightly less than NST-AODV. However, RT-AODV guarantees that a message is delivered to its destination if an acknowledgement is received. The work described in this thesis shows that using end-to-end acknowledgements and any-to-any routing in wireless sensor networks is certainly viable.

Massive sales of smartphones and tablets have enabled more people to access the internet with a 3G connection than ever before. Predictions indicate an exponential growth of mobile data traffic world-wide reaching 6.3 exabytes per month by 2015, a 26-fold increase over 2010. Unfortunately, the current infrastructure will not be able to meet these demands. Already now, a speed reduction or even lack of connection can be noticed in crowded places. Service providers are addressing the problem by deploying Femtocells and Wi-Fi Access Points (APs) around cities. However, due to their limited connection range, the projected redirected traffic, including free APs at home and office, is expected to be only 39% by 2015. The intention of this thesis is to extend the range of Wi-Fi APs as internet gateways through multi hopping. Furthermore, phone calls and data exchange between devices in proximity are supported and also offloaded from the 3G data network. Therefore, we offload part of the traffic from the mobile data network to Wi-Fi. An added benefit is a reduction in energy consumption. However, current Mobile Ad-hoc Network (MANET) techniques are unable to scale or to handle high mobility. Therefore, we propose a novel approach called “Mobile Assisted Ad-hoc Networking”. MASS-ANET can be applied to any kind of mobile ad-hoc network where nodes can use both a global and a local transmission link. In this project, Wi-Fi local connectivity is used to create a mobile ad-hoc network. 3G links act as a global coordination medium with the help of a central server. The feasibility of the MASS-ANET is determined with the help of simulations. Subsequently modern commodity smartphones are used as prototypes in validation experiments. The proposed solution is verified using a real-world application: exchanging real-time voice traffic over several hops in a mobile ad-hoc Wi-Fi network.

With the release of RGBD-cameras (cameras that provide both RGB as well as depth information) researchers have started evaluating how these devices can be used in fields of localization, mapping and ubiquitous computing. Intel Seattle Research proposed an indoor mapping algorithm making use of such a camera. The algorithm itself is vulnerable to violations of the static environment assumption and image based localization failures that can be caused by, for example, featureless environments. The goal of this master thesis is to augment the indoor mapping algorithm with additional Inertial Measurement Unit (IMU) data to enhance the robustness to these vulnerabilities. To this end the characteristics and limitations of the Microsoft Kinect are investigated and an enhanced mapping algorithm is proposed. IMU orientation estimates are fused with pose estimates based on image data, which give an initial guess to the Iterative Closest Point (ICP) algorithm that is used to align point cloud data to create a final map. In case visual localization fails, the algorithm of Intel uses a constant velocity assumption as fallback mechanism while the IMU data provide more accurate orientation estimations than the constant velocity assumption can provide. The IMU-enhanced algorithm shows similar mapping quality in ideal mapping conditions compared to the plain mapping algorithm. While a series of corner case tests show that the IMU-enhanced algorithm was unable to improve the results compared with the plain mapping algorithm, it potentially generates improvements in mapping quality when dealing with non-static environments.

Model-based testing is a technique to automatically generate test cases and oracles in order to test an implementation. A typical behavrial model used for model-based testing is a Labeled Transition System9LTS). However cre-ating the LTS models needed for testing is a complex task, and especially when data is involved the number of states and thus the complexity will explode fast. Incorporating data in an LTS leads to a Symbolic Transitions System (STS), where data is stored in variables and actions have guards and updates. The result is that the number of states is reduced and the complexity is moved to the update rules and guards. In order to simplify the construction of STS an algorithm is presented that is capable of extracting data form an implementation and enriching the LTS model in order to from an STS. A domain expert can than inspect the model for possible faults and in the future the model can be used for regression testing of the implementation.