· · · Institutional Repository

Localization has an import role in wireless sensor networks, as it adds context to gathered data. The goal of this thesis is to create an application that determines the location of a mobile sensor node in an indoor environment. A secondary goal is to get practical experience with indoor localization. Previously, in a literature review, we selected two localization algorithms for this purpose. RIPS was selected since it was tested in practice, uses no additional hardware and has a very good accuracy. CAB was selected because it is a range-free localization algorithm and has low computational complexity. RIPS turned out to be too hardware specific and was not portable to the target hardware. CAB failed because of multipath effects. However, by transmitting beacons on multiple frequencies and averaging over the received signal strength, these multipath effects can be mitigated. In this thesis, we tested the effect of multiple frequencies on a simple proximity algorithm. Although the accuracy did not improve as we expected, it did improve the robustness against temporal disturbances. We also tested the effect of multiple frequencies on two different fingerprinting systems, with the fingerprint database constructed in two ways: a small database, where samples are averaged over all channels and a large database, where samples are averaged per channel. We show that the small database provides the best accuracy with a mean localization error of 2.19 meters.

Field biologists and ecologists have started to open a new avenue of inquiry at greater spatial and temporal resolution, allowing them to “observe the unobservable” through the use of wireless sensor networks. Study of birds has helped to develop fundamental knowledge of bird behavior, foraging pattern and migration. The acquired knowledge of birds has contributed to build concepts, like evolution, and applications, such as mitigating risk of bird-strikes and protecting endangered species. Traditional bird life monitoring approaches, like satellite telemetry are not capable to provide the insights in a greater resolution and suffer from large delay to deliver data. In this thesis we present the communication mechanism of BirdTracking, a wireless sensor network to observe bird life for a complete annual bird-cycle. One of the main challenges of a sensor network formed by devices attached to birds is the disrupted connectivity due to mobility and habitat of birds. We propose CHIRP, a routing protocol that utilizes the behavior and mobility of birds to transmit sensor data to a collection point. In order to evaluate CHIRP, we implemented it on a wireless network simulator over a mobility model created by real life traces of a colonial bird (gull) and a territorial bird (honey buzzard). We compare CHIRP against direct transmission and an epidemic routing scheme. Our simulation results show that CHIRP achieves significant improvement in data delivery as compared to direct transmission while consuming less resources than the epidemic routing scheme.

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 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.

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.

A compiler translates one representation of a software program into another. Beside translation compilers often have other tasks such as optimizating the result and warning the programmer for mistakes. Internally a compiler uses an Intermediate Representation (IR) for analysis and manipulation of the program at hand. Data dependencies in most programming languages are implicit. Some compilers use an IR in Static Single Assignment (SSA) in which each local variable is only defined once to simplify analysis of data dependencies. If the number of assignments in the IR is not restricted, it is said to be in normal form. Input of a compiler is in normal form and translation is needed to bring the IR in SSA form. SSA-form contains phi functions to merge values based on control flow. After optimizations on SSA-form are performed it is not trivial to translate SSA-form back to normal form because the properties of phi nodes cannot be translated directly to processor instructions. The algorithms of Briggs and Sreedhar are the two major methods of back-translation. This thesis presents a modification that can be applied to the methods of Briggs and Sreedhar. The original methods append copy instructions to the end of existing source blocks. The presented modification splits edges between source and target by inserting phiblocks where the algorithms of Sreedhar and Briggs emit copy operations to replace phi functions. For this study a bridge between LLVM and CoSy was built such that LLVM can be used for the optimizations on SSA-form and CoSy for the post back-translation optimizations. Four back-translation algorithms are implemented in CoSy. The methods are compared through experiments with six testcases from the SPEC benchmark suite. On average the presented modification reduces the execution time of the resulting code with 5% for Briggs’ method and 3% for Sreedhar’s method. Experiments also show that the result of back-translation with or without phiblocks is suboptimal: repeating optimizations after back-translation that were already done on the IR in SSA-form can reduce the execution time on average with 18%.

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.

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.

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.

A wireless sensor network is an embedded computer network formed by small cheap devices, prone to errors. Communication in such a network in a single-hop range is provided by a Medium Access Control (MAC) Protocol. Chess has developed one such a MAC protocol, Gossip-MAC (G-MAC), specifically designed to service gossiping-based traffic. G-MAC was put to the test in a previous research study, in which two major defects were discovered. The first defect is inefficient direct communication in large neighborhoods, caused by hidden terminals. The second is a capacity problem when too many nodes are in one neighborhood. In this research we introduce an improved Gossip-MAC protocol that does not suffer from these two defects. The new MAC protocol has been made collision-free and herein two TDMA scheduling algorithm variations are introduced. The first swarms over a time frame, trying to locate other nodes. The second listens to consecutive intervals relative to the beginning of a frame. Both allow a dynamic number of neighbors in contrast with the original MAC. Both variations are put to the test and Distributed G-MAC turns out to be the best option for Gossiping in terms of both energy consumption and the rate in which news is spread globally.

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 are being deployed extensively to collect sensory data in various environments under different conditions. A wireless sensor network consists of multiple nodes, each with the ability to communicate using radio waves. The characteristics of the radio link between nodes are largely influenced by their environment. For instance, a radio link between two nodes with obstructed line-of-sight behaves more erratic than one that is not obstructed. This thesis focuses primarily on the characteristics of radio wave propagation in metal train compartments from a Computer Science standpoint. It means that the electrical aspects of this subject are not discussed in detail. In this work, we focus mainly on matters such as transmission output power, signal strength, preamble length, and packet reception rate. Various tests were performed throughout the length of the project. The purpose of the tests was to gain insights on the characteristics of radio wave propagation under various circumstances. We examine the effect exerted on radio wave propagation by varying transmission output power, antenna orientation, and antenna position. The characteristics reported in this thesis are signal strength, preamble length, and packet reception rate. The tests were carried out in an open field and in metal train compartments. The open field tests were used to create benchmark data for which data from metal train compartments could be compared with. The tests have led to several important findings. They show that radio links could be established within metal train compartments and even between two compartments. The latter seems to contradict rational belief that radio waves cannot propagate from one train compartment to the other, because of the metallic structure. Furthermore, there are some indications that antenna orientation may greatly influence radio wave propagations in compartments for low transmission output powers. This thesis also examines the preamble length. It finds that the preamble length could potentially be reduced to two bytes without affecting packet reception rates. And finally, the results show that higher transmission output power leads to greater packet reception rates and stronger received signal strengths, regardless of the environment. These and other findings are discussed in detail in the remainder of this thesis.