· · · Institutional Repository

Wireless sensor networks is a technology that has been used in a vast number of applications and environments with successful results in the past. Therefore increasing nowadays the number of users of this type of devices and their new applications. In this thesis we worked hand-in-hand with the ISIS B.V. Company to provide a proper WSN design to be deployed inside a spacecraft structure and satisfy a group of defined requirements. ISIS or Innovative Solutions in Space is a private company founded in January 2006 that focus on the development of nanosatellites and several space related services.

Model-based diagnosis is a technique where a model of a system is combined with observations from that system, to generate diagnoses for failures of the system. This thesis looks at how model-based diagnosis can be applied to wireless sensor networks (WSNs). WSNs are ad-hoc wireless networks of small form-factor, embedded nodes with limited memory and processor power. Further, they are often battery powered, meaning that energy use must be kept to a minimum. A diagnoser design is proposed that uses the distributed nature of WSNs to find initial symptoms based on a local model, while leaving the more complex computations required to combine these symptoms to a more powerful central sink computer. A proof-of-concept design is then implemented. Results from this implementation show that using model-based diagnosis in sensor networks is certainly a viable solution. The model used in the proof of concept application created during the work on this thesis did have some problems in dense networks, showing that care must be taken when crafting the model to ensure a successful 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.

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.

The advent of small, and cheap sensors provides a wide range of measuring options. By making these sensors operate wirelessly we can now measure more than ever. However, wireless operation also provides new challenges. For example, how can we make these wireless sensors communicate effectively, i.e. without all the sensors trying to talk at the same time. This is the responsibility of the Medium Access Control (MAC) protocol. But the MAC protocol must also ensure energy-efficient operation to save precious battery power. In this thesis we present both new MAC-protocol ideas as well as research into evaluation methods for MAC protocols for Wireless Sensor Networks.

Most current WSN MAC protocol implementations have multiple tasks to perform—deciding on correct timing, sending of packets, sending of acknowledgements, etc. However, as much of this is common to all MAC protocols, there is duplication of functionality, which leads to larger MAC protocol code size and therefore increasing numbers of bugs. Additionally, extensions to the basic functionality must be separately implemented in each MAC protocol. In this paper, we look at a different way to design a MAC protocol, focusing on the providing of interfaces which can be used to implement the common functionality separately. This leaves the core of the MAC protocol, determining only when to send, which is substantially different for each protocol. We also look at some examples of MAC extensions that this approach enables. We demonstrate a working implementation of these principles as an implementation of B-MAC for TinyOS, and compare it with the standard TinyOS B-MAC implementation. We show a 35% smaller code size, with the same overall functionality but increased extensibility, and while maintaining similar performance. We also present results and experiences from using the same framework to implement T-MAC, LMAC, and Crankshaft. All are demonstrated with data from real-world experience using our 24 node testbed.

Accurately and dynamically monitoring energy usage patterns in households forms a first requirement for more efficient and ecofriendly energy management in the future. Monitored energy usage data can be used by power systems engineering—to inform demand-side management systems in the near future term—and in architecture/civil engineering—where it can be used to carry out long-term studies across populations and sectors to estimate future demand and to evaluate prospective (social) policies. This paper presents an agent based prototype of an architecture to meet these needs. The proposed system remains flexible to new functional requirements and adaptable to new edge devices for data collection, as well as offering the potential to ‘close the loop’ and permit remote control of power supplies to individual appliances. Some preliminary analyses of data collected is used to illustrate what may be possible in the longer term.

With the increasing use of information technology for different societal goals, the demand for flexible and multiple-functionality appliances has risen. Making technology reconfigurable could be a way of achieving this. This working paper is written against the background of a large scale research project developing reconfigurable sensors in order to achieve a continuous and affordable infrastructure for both safety and security (STARS). Our role in the project is to explore the ethical challenges reconfigurability raises for sociotechnical systems like sensor networks. We foresee that reconfigurable technology adds an extra challenge to the identification and specification of functional and nonfunctional requirements for the technology.

With the increasing use of sensor technology for different societal goals, like security and safety, the demand for multiple and flexible functionality of the sensors is rising. The expectation is that the development of reconfigurable sensors will lead to a continuous and affordable infrastructure. In this note, we undertake a first exploration of the ethical challenges reconfigurability raises for sensor networks, and more generally, for sociotechnical systems.

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.

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.

Sensor positioning is an important task of location-aware wireless sensor networks. In most sensor positioning systems, sensors and beacons need to emit ranging signals to each other. Sensor ranging energy should be low to prolong system lifetime, but sufficiently high to fulfill prescribed accuracy requirements. This motivates us to investigate ranging energy optimization problems. We address ranging energy optimization for an unsynchronized positioning system, which features robust sensor positioning (RSP) in the sense that a specific accuracy requirement is fulfilled within a prescribed service area. We assume a line-of-sight (LOS) channel exists between the sensor and each beacon. The positioning is implemented by time-of-arrival (TOA) based two-way ranging between a sensor and beacons, followed by a location estimation at a central processing unit. To establish a dependency between positioning accuracy and ranging energy, we assume the adopted TOA and location estimators are unbiased and attain the associated Cramer-Rao bound. The accuracy requirement has the same form as the one defined by the Federal Communication Commission (FCC), and we present two constraints with linear-matrix-inequality form for the RSP. Ranging energy optimization problems, as well as a practical algorithm based on semidefinite programming are proposed. The effectiveness of the algorithm is illustrated by numerical experiments.

Wireless communication and networking technology has facilitated people to be connected with each other closely. Cellular network is evolving now from the third generation to the fourth generation. In the meanwhile we are experiencing the demand for wireless networks which can facilitate the communication between humans and environment, human and machines or even machine and machine. Such networks will help us know more about our surroundings which could lead us towards a better and greener life. Wireless Sensor Networks (WSN) is one candidate among such networks. It turns sensing tasks from small scale, centralized and expensive to large scale, distributed and low-cost by connecting small battery powered sensors with wireless links. We start the thesis by introducing WSN, its background and current status in Chapter 1. Although a lot of work has been reported in the literature on WSN, there are still many challenges. In this thesis, we focus on five of them, namely, (1)energy, (2)reliability, (3)scalability, (4)ease of use and (5)ease of set up. Energy is a challenge since WSNs are powered by batteries or even energy harvested from the ambience. The second, fourth and the fifth challenges are the hindrance in the way of high adaptation of WSNs while the third one will challenge when WSNs are largely deployed. Motivations and contributions of the thesis are also presented in the first chapter. Chapter 2 gives an overview of the literature in the several categories, such as physical layer, MAC layer, networking layer, synchronization and real deployment. Our work in the rest of the thesis is related to the work introduced in this chapter. We present the first result of our research in Chapter 3, which focuses on energy and reliability challenge on link layer. To improve the reliability of a link, we have to know the quality of the link. Thus we firstly analyze and try to improve link quality estimation methods in the chapter. We propose a new method for the estimation of packet delivery ratio which balances estimation accuracy and the overhead it causes. Then Minimum Energy Packet Forwarding (MEPF) protocol is proposed with the purpose of delivering a packet reliable with least amount of energy. MEPF tries to achieve the objective by tuning transmission power online for each packet with respect to the link quality. If a packet is lost, MEPF retransmits it smartly only when the link is considered to be good enough. Experimental results prove that MEPF uses almost the lowest possible transmission power without increasing the packet loss and retransmits a lost packet only once to eventually deliver it. We move a layer up from MAC to the network layer in Chapter 4. We organize a network into a better topology to improve energy efficiency and scalability. Two types of topologies are considered in this chapter, flat and clustered. In the former one each node has the same role while in the latter one nodes are organized into clusters where a node is either a Cluster Head (CH) or a Cluster Member (CM). We firstly analyze why a clustered topology may save energy then we quantify the saving. Since traffic is reduced in a clustered network, less contention or collision is expected and more nodes can communicate simultaneously. Thus a clustered network is highly scalable. To form a cluster topology from a flat one, we propose a cluster forming protocol which selects least amount of CHs which have the highest remaining energy. Thus they can live longer under higher traffic load compared to CMs. Simulation results show the feasibility and performance of the proposed protocol. Chapter 5 improves accuracy of localization, one of the most important WSN applications. One reason for the low accuracy is that the radio coverage of small and inexpensive antennas on sensor nodes, especially those in a Body Area Sensor Networks (BASN), is not omnidirectional. This problem leads to the failure of many localization protocols to achieve good accuracy since they are based on the assumption of omnidirectional antennas. In the chapter we proposed to use multiple receivers to locate a person in the context of a BASN. This method improves localization accuracy from a single receiver by mitigating the errors caused by varied and non-uniform beamwidth of antennas and combating fading with spatial diversity. We test this method in two classes of localization methods. The outcome of experimental results show that the method achieves a higher accuracy than a single receiver. Thus the reliability of localization is improved. Setting up a WSN especially for experiments is cumbersome and time-consuming process. It impacts the ease of use and set up. Thus we propose a framework for flexible and low-cost testbed in Chapter 6. Such a testbed only has sensor motes. Other than experiments, testbed management such as downloading the experimental code, reprogramming, testbed control, logging and collecting experimental results and synchronization are all carried out by the sensor motes wirelessly without extra devices. Thus a low-cost testbed can be set up quickly. A case study which realizes components in the framework is also presented. Finally the results of the thesis are summarized in Chapter 7. Future work is also presented there.

Mobile robots that communicate and cooperate to achieve a common task have been the subject of an increasing research interest in recent years. These possibly heterogeneous groups of robots communicate locally via a communication network and therefore are usually referred to as robotic networks. Their potential applications are diverse and encompass monitoring, exploration, search and rescue, and disaster relief. From a research standpoint, in this thesis we consider specific aspects related to the foundations of robotic network algorithmic development: distributed estimation, control, and optimization. The word “distributed” refers to situations in which the cooperating robots have a limited, local knowledge of the environment and of the group, as opposed to a “centralized” scenario, where all the robots have access to the complete information. The typical challenge in distributed systems is to achieve similar results (in terms of performance of the estimation, control, or optimization task) with respect to a centralized system without extensive communication among the cooperating robots. In this thesis we develop effective distributed estimation, control, and optimization algorithms tailored to the distributed nature of robotic networks. These algorithms strive for limiting the local communication among the mobile robots, in order to be applicable in practical situations. In particular, we focus on issues related to nonlinearities of the dynamical model of the robots and their sensors, to the connectivity of the communication graph through which the robots interact, and to fast feasible solutions for the common (estimation or control) objective.

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.

In this paper, we analyze the problem of acoustic ranging between sensor nodes in an underwater environment. The underwater medium is assumed to be composed of multiple isogradient sound speed profile (SSP) layers where in each layer the sound speed is linearly related to the depth. Furthermore, each sensor node is able to measure its depth and can exchange this information with other nodes. Under these assumptions, we first show how the problem of underwater localization can be converted to the traditional range-based terrestrial localization problem when the depth information of the nodes is known a priori. Second, we relate the pair-wise time of flight (ToF) measurements between the nodes to their positions. Next, based on this relation, we propose a novel ranging algorithm for an underwater medium. The proposed ranging algorithm considers reflections from the seabed and sea surface. We will show that even without any reflections, the transmitted signal may travel through more than one path between two given nodes. The proposed algorithm analyzes them and selects the fastest one (first arrival path) based on the measured ToF and the nodes’ depth measurements. Finally, in order to evaluate the performance of the proposed algorithm we run several simulations and compare the results with other existing algorithms.

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.

The great demand for location-aware wireless sensor networks (WSNs) motivates the research in this thesis. The unique characteristics of WSNs impose numerous challenges on localization and communication. In this thesis, we handle some key challenges and provide affordable solutions. Impulse radio ultra wideband (IR-UWB) is employed as the fundamental technology for both localization and communication due to its distinctive advantages in accurate ranging and reliable communication. The following aspects are treated in this thesis. Transmitted-reference (TR) UWB communication systems: IR-UWB processing in the digital domain usually asks for very high sampling rates. The TR-UWB scheme allows for sub-Nyquist rate sampling by correlating the received pulse sequence with its delayed version in the analog domain. Thus, it avoids the daunting Nyquist sampling rate, relaxes the stringent synchronization requirements, and only asks for aggregate channel coefficients. A data model including various kinds of interferences is employed, and then a complete receiver is proposed including signal detection, channel estimation, synchronization and equalization. Theoretical ranging bounds and practical ranging methods based on IR-UWB: We investigate the theoretical ranging accuracy of a novel method, which exploits the range information in both the amplitude and the time delay of the received signal. The investigations are conducted not only for an additive white Gaussian noise (AWGN) channel with attenuation, but also for an AWGN channel with both attenuation and shadowing. Furthermore, a practical ranging method based on time-of-arrival (TOA) estimation using UWB IRs is developed. Stroboscopic sampling is employed to sacrifice transmission efficiency for a lower sampling rate. Moreover, it can maintain the same ranging resolution as Nyquist sampling can achieve. Due to the long preamble required by stroboscopic sampling, the clock drift, which is an accumulative effect over time caused by the relative clock skew between different clocks, is one of the main error sources in TOA estimation. Therefore, TOA estimation methods with clock drift calibration are explored to dramatically mitigate the influence of the drift. Various localization and tracking methods: Extended multi-dimensional scaling (MDS): Since the classical MDS cannot be applied to general networks with missing links, we extend the classical MDS algorithm to deal with a special kind of network with specific missing links. Our goal is to jointly estimate the positions of all the nodes given partial pairwise distance measurements up to a translation, rotation, and reflection. Reference-free time-based localization: Low-complexity least-squares (LS) estimators based on time-of-arrival (TOA) or time-difference-of-arrival (TDOA) measurements have been developed in literature to locate a target node with the help of anchors (nodes with known positions). They require to select a reference anchor in order to cancel nuisance parameters or relax stringent synchronization requirements, and suffer from a poor reference selection. We propose reference-free localization estimators based on TOA measurements to decouple the reference dependency. Furthermore, we generalize existing reference-based closed-form localization estimators using TOA or TDOA measurements, and shed new light on their relations to clarify some confusions that still persist in recent literature. Robust time-based localization: Time-based localization approaches attract a lot of interest due to their high accuracy and potentially low cost for WSNs. However, time-based localization is tightly coupled with clock synchronization. Thus, the reliability of timestamps in time-based localization becomes an important yet challenging task to deal with. Regardless of the reliability of the timestamps from the target node, we propose a novel ranging protocol, namely asymmetric trip ranging (ATR), which leads to localization methods that are naturally immune to internal attacks mounted by a compromised target node. Robust localization strategies using the ATR protocol based on TOA measurements are proposed to localize a target node with the help of anchors for asynchronous networks. Kalman tracking: Due to the nonlinearity of the localization problem, a Kalman filter (KF) is usually replaced by an extended KF (EKF) for tracking a mobile target. However, the modeling errors inherently contained in the EKF degrade the tracking performance. Therefore, we make use of the ATR protocol again, carry out exact linearizations, and achieve a KF based on a linear measurement model to track a mobile target with the aid of fixed anchors.