Optimisation Problems in Wireless Sensor Networks : Local Algorithms and Local Graphs

This thesis studies optimisation problems related to modern large-scale distributed systems, such as wireless sensor networks and wireless ad-hoc networks. The concrete tasks that we use as motivating examples are the following: (i) maximising the lifetime of a battery-powered wireless sensor network, (ii) maximising the capacity of a wireless communication network, and (iii) minimising the number of sensors in a surveillance application. A sensor node consumes energy both when it is transmitting or forwarding data, and when it is performing measurements. Hence task (i), lifetime maximisation, can be approached from two different perspectives. First, we can seek for optimal data flows that make the most out of the energy resources available in the network; such optimisation problems are examples of so-called max-min linear programs. Second, we can conserve energy by putting redundant sensors into sleep mode; we arrive at the sleep scheduling problem, in which the objective is to find an optimal schedule that determines when each sensor node is asleep and when it is awake. In a wireless network simultaneous radio transmissions may interfere with each other. Task (ii), capacity maximisation, therefore gives rise to another scheduling problem, the activity scheduling problem, in which the objective is to find a minimum-length conflict-free schedule that satisfies the data transmission requirements of all wireless communication links. Task (iii), minimising the number of sensors, is related to the classical graph problem of finding a minimum dominating set. However, if we are not only interested in detecting an intruder but also locating the intruder, it is not sufficient to solve the dominating set problem; formulations such as minimum-size identifying codes and locating dominating codes are more appropriate. This thesis presents approximation algorithms for each of these optimisation problems, i.e., for max-min linear programs, sleep scheduling, activity scheduling, identifying codes, and locating dominating codes. Two complementary approaches are taken. The main focus is on local algorithms, which are constant-time distributed algorithms. The contributions include local approximation algorithms for max-min linear programs, sleep scheduling, and activity scheduling. In the case of max-min linear programs, tight upper and lower bounds are proved for the best possible approximation ratio that can be achieved by any local algorithm. The second approach is the study of centralised polynomial-time algorithms in local graphs these are geometric graphs whose structure exhibits spatial locality. Among other contributions, it is shown that while identifying codes and locating dominating codes are hard to approximate in general graphs, they admit a polynomial-time approximation scheme in local graphs.

Two Stage Transform Vector Quantization of LSFs for Wideband Speech Coding

We investigate the use of a two stage transform vector quantizer (TSTVQ) for coding of line spectral frequency (LSF) parameters in wideband speech coding. The first stage quantizer of TSTVQ, provides better matching of source distribution and the second stage quantizer provides additional coding gain through using an individual cluster specific decorrelating transform and variance normalization. Further coding gain is shown to be achieved by exploiting the slow time-varying nature of speech spectra and thus using inter-frame cluster continuity (ICC) property in the first stage of TSTVQ method. The proposed method saves 3-4 bits and reduces the computational complexity by 58-66%, compared to the traditional split vector quantizer (SVQ), but at the expense of 1.5-2.5 times of memory.

Design of multimedia surveillance systems

This article addresses the problem of how to select the optimal combination of sensors and how to determine their optimal placement in a surveillance region in order to meet the given performance requirements at a minimal cost for a multimedia surveillance system. We propose to solve this problem by obtaining a performance vector, with its elements representing the performances of subtasks, for a given input combination of sensors and their placement. Then we show that the optimal sensor selection problem can be converted into the form of Integer Linear Programming problem (ILP) by using a linear model for computing the optimal performance vector corresponding to a sensor combination. Optimal performance vector corresponding to a sensor combination refers to the performance vector corresponding to the optimal placement of a sensor combination. To demonstrate the utility of our technique, we design and build a surveillance system consisting of PTZ (Pan-Tilt-Zoom) cameras and active motion sensors for capturing faces. Finally, we show experimentally that optimal placement of sensors based on the design maximizes the system performance.

Design and characterization of in-plane MEMS yaw rate sensor

In this paper, we present the design and characterization of a vibratory yaw rate MEMS sensor that uses in-plane motion for both actuation and sensing. The design criterion for the rate sensor is based on a high sensitivity and low bandwidth. The required sensitivity of the yawrate sensor is attained by using the inplane motion in which the dominant damping mechanism is the fluid loss due to slide film damping i.e. two-three orders of magnitude less than the squeeze-film damping in other rate sensors with out-of-plane motion. The low bandwidth is achieved by matching the drive and the sense mode frequencies. Based on these factors, the yaw rate sensor is designed and finally realized using surface micromachining. The inplane motion of the sensor is experimentally characterized to determine the sense and the drive mode frequencies, and corresponding damping ratios. It is found that the experimental results match well with the numerical and the analytical models with less than 5% error in frequencies measurements. The measured quality factor of the sensor is approximately 467, which is two orders of magnitude higher than that for a similar rate sensor with out-of-plane sense direction.

Subspace intersection method of high-resolution bearing estimation in shallow ocean using acoustic vector sensors

The subspace intersection method (SIM) provides unbiased bearing estimates of multiple acoustic sources in a range-independent shallow ocean using a one-dimensional search without prior knowledge of source ranges and depths. The original formulation of this method is based on deployment of a horizontal linear array of hydrophones which measure acoustic pressure. In this paper, we extend SIM to an array of acoustic vector sensors which measure pressure as well as all components of particle velocity. Use of vector sensors reduces the minimum number of sensors required by a factor of 4, and also eliminates the constraint that the intersensor spacing should not exceed half wavelength. The additional information provided by the vector sensors leads to performance enhancement in the form of lower estimation error and higher resolution.

Elliptical summary randomisation for sensor-based human activity recognition

Many conventional statistical machine learning al- gorithms generalise poorly if distribution bias ex- ists in the datasets. For example, distribution bias arises in the context of domain generalisation, where knowledge acquired from multiple source domains need to be used in a previously unseen target domains. We propose Elliptical Summary Randomisation (ESRand), an efficient domain generalisation approach that comprises of a randomised kernel and elliptical data summarisation. ESRand learns a domain interdependent projection to a la- tent subspace that minimises the existing biases to the data while maintaining the functional relationship between domains. In the latent subspace, ellipsoidal summaries replace the samples to enhance the generalisation by further removing bias and noise in the data. Moreover, the summarisation enables large-scale data processing by significantly reducing the size of the data. Through comprehensive analysis, we show that our subspace-based approach outperforms state-of-the-art results on several activity recognition benchmark datasets, while keeping the computational complexity significantly low.

Prediction of Candidate Primary Immunodeficiency Disease Genes Using a Support Vector Machine Learning Approach

Screening and early identification of primary immunodeficiency disease (PID) genes is a major challenge for physicians. Many resources have catalogued molecular alterations in known PID genes along with their associated clinical and immunological phenotypes. However, these resources do not assist in identifying candidate PID genes. We have recently developed a platform designated Resource of Asian PDIs, which hosts information pertaining to molecular alterations, protein-protein interaction networks, mouse studies and microarray gene expression profiling of all known PID genes. Using this resource as a discovery tool, we describe the development of an algorithm for prediction of candidate PID genes. Using a support vector machine learning approach, we have predicted 1442 candidate PID genes using 69 binary features of 148 known PID genes and 3162 non-PID genes as a training data set. The power of this approach is illustrated by the fact that six of the predicted genes have recently been experimentally confirmed to be PID genes. The remaining genes in this predicted data set represent attractive candidates for testing in patients where the etiology cannot be ascribed to any of the known PID genes.

Compact fiber Bragg grating dynamic strain sensor cum broadband thermometer for thermally unstable ambience

An instrument for simultaneous measurement of dynamic strain and temperature in a thermally unstable ambience has been proposed, based on fiber Bragg grating technology. The instrument can function as a compact and stand-alone broadband thermometer and a dynamic strain gauge. It employs a source wavelength tracking procedure for linear dependence of the output on the measurand, offering high dynamic range. Two schemes have been demonstrated with their relative merits. As a thermometer, the present instrumental configuration can offer a linear response in excess of 500 degrees C that can be easily extended by adding a suitable grating and source without any alteration in the procedure. Temperature sensitivity is about 0.06 degrees C for a bandwidth of 1 Hz. For the current grating, the upper limit of strain measurement is about 150 mu epsilon with a sensitivity of about 80 n epsilon Hz(-1/2). The major source of uncertainty associated with dynamic strain measurement is the laser source intensity noise, which is of broad spectral band. A low noise source device or the use of optical power regulators can offer improved performance. The total harmonic distortion is less than 0.5% up to about 50 mu epsilon, 1.2% at 100 mu epsilon and about 2.3% at 150 mu epsilon. Calibrated results of temperature and strain measurement with the instrument have been presented. Traces of ultrasound signals recorded by the system at 200 kHz, in an ambience of 100-200 degrees C temperature fluctuation, have been included. Also, the vibration spectrum and engine temperature of a running internal combustion engine has been recorded as a realistic application of the system.

A Slotted Aloha joint MAC-cum-Routing protocol for data gathering sensor network applications

In this paper we have proposed and implemented a joint Medium Access Control (MAC) -cum- Routing scheme for environment data gathering sensor networks. The design principle uses node 'battery lifetime' maximization to be traded against a network that is capable of tolerating: A known percentage of combined packet losses due to packet collisions, network synchronization mismatch and channel impairments Significant end-to-end delay of an order of few seconds We have achieved this with a loosely synchronized network of sensor nodes that implement Slotted-Aloha MAC state machine together with route information. The scheme has given encouraging results in terms of energy savings compared to other popular implementations. The overall packet loss is about 12%. The battery life time increase compared to B-MAC varies from a minimum of 30% to about 90% depending on the duty cycle.

Developing an Unmanned Aerial Vehicle (UAV) multi-sensor payload carrier for air quality monitoring

Emissions of gases and particles from sea-faring ships have been shown to impact on the atmospheric chemistry and climate. To efficiently monitor and report these emissions found from a ship’s plume, the concept of using a multi-rotor or UAV to hover inside or near the exhaust of the ship to actively record the data in real time is being developed. However, for the required sensors obtain the data; their sensors must face into the airflow of the ships plume. This report presents an approach to have sensors able to read in the chemicals and particles emitted from the ship without affecting the flight dynamics of the multi-rotor UAV by building a sealed chamber in which a pump can take in the surrounding air (outside the downwash effect of the multi-rotor) where the sensors are placed and can analyse the gases safely. Results show that the system is small, lightweight and air-sealed and ready for flight test.

Green Falcon IV: An Unmanned Aerial System and an integrated Wireless Sensor Network for remote sensing tasks

This report summarises the development of an Unmanned Aerial System and an integrated Wireless Sensor Network (WSN), suitable for the real world application in remote sensing tasks. Several aspects are discussed and analysed to provide improvements in flight duration, performance and mobility of the UAV, while ensuring the accuracy and range of data from the wireless sensor system.