Planning the deployment of fault-tolerant wireless sensor networks

Since Wireless Sensor Networks (WSNs) are subject to failures, fault-tolerance becomes an important requirement for many WSN applications. Fault-tolerance can be enabled in different areas of WSN design and operation, including the Medium Access Control (MAC) layer and the initial topology design. To be robust to failures, a MAC protocol must be able to adapt to traffic fluctuations and topology dynamics. We design ER-MAC that can switch from energy-efficient operation in normal monitoring to reliable and fast delivery for emergency monitoring, and vice versa. It also can prioritise high priority packets and guarantee fair packet deliveries from all sensor nodes. Topology design supports fault-tolerance by ensuring that there are alternative acceptable routes to data sinks when failures occur. We provide solutions for four topology planning problems: Additional Relay Placement (ARP), Additional Backup Placement (ABP), Multiple Sink Placement (MSP), and Multiple Sink and Relay Placement (MSRP). Our solutions use a local search technique based on Greedy Randomized Adaptive Search Procedures (GRASP). GRASP-ARP deploys relays for (k,l)-sink-connectivity, where each sensor node must have k vertex-disjoint paths of length ≤ l. To count how many disjoint paths a node has, we propose Counting-Paths. GRASP-ABP deploys fewer relays than GRASP-ARP by focusing only on the most important nodes – those whose failure has the worst effect. To identify such nodes, we define Length-constrained Connectivity and Rerouting Centrality (l-CRC). Greedy-MSP and GRASP-MSP place minimal cost sinks to ensure that each sensor node in the network is double-covered, i.e. has two length-bounded paths to two sinks. Greedy-MSRP and GRASP-MSRP deploy sinks and relays with minimal cost to make the network double-covered and non-critical, i.e. all sensor nodes must have length-bounded alternative paths to sinks when an arbitrary sensor node fails. We then evaluate the fault-tolerance of each topology in data gathering simulations using ER-MAC.

Functional metagenomic analysis of the human gut microbiome to identify novel salt tolerance genes

The ability to adapt to and respond to increases in external osmolarity is an important characteristic that enables bacteria to survive and proliferate in different environmental niches. When challenged with increased osmolarity, due to sodium chloride (NaCl) for example, bacteria elicit a phased response; firstly via uptake of potassium (K+), which is known as the primary response. This primary response is followed by the secondary response which is characterised by the synthesis or uptake of compatible solutes (osmoprotectants). The overall osmotic stress response is much broader however, involving many diverse cellular systems and processes. These ancillary mechanisms are arguably more interesting and give a more complete view of the osmotic stress response. The aim of this thesis was to identify novel genetic loci from the human gut microbiota that confer increased tolerance to osmotic stress using a functional metagenomic approach. Functional metagenomics is a powerful tool that enables the identification of novel genes from as yet uncultured bacteria from diverse environments through cloning, heterologous expression and phenotypic identification of a desired trait. Functional metagenomics does not rely on any previous sequence information to known genes and can therefore enable the discovery of completely novel genes and assign functions to new or known genes. Using a functional metagenomic approach, we have assigned a novel function to previously annotated genes; murB, mazG and galE, as well as a putative brp/blh family beta-carotene 15,15’-monooxygenase. Finally, we report the identification of a completely novel salt tolerance determinant with no current known homologues in the databases. Overall the genes identified originate from diverse taxonomic and phylogenetic groups commonly found in the human gastrointestinal (GI) tract, such as Collinsella and Eggerthella, Akkermansia and Bacteroides from the phyla Actinobacteria, Verrucomicrobia and Bacteroidetes, respectively. In addition, a number of the genes appear to have been acquired via lateral gene transfer and/or encoded on a prophage. To our knowledge, this thesis represents the first investigation to identify novel genes from the human gut microbiota involved in the bacterial osmotic stress response.