Repairing wireless sensor network connectivity in damaged environments

A wireless sensor network can become partitioned due to node failure, requiring the deployment of additional relay nodes in order to restore network connectivity. This introduces an optimisation problem involving a tradeoff between the number of additional nodes that are required and the costs of moving through the sensor field for the purpose of node placement. This tradeoff is application-dependent, influenced for example by the relative urgency of network restoration. In addition, minimising the number of relay nodes might lead to long routing paths to the sink, which may cause problems of data latency. This data latency is extremely important in wireless sensor network applications such as battlefield surveillance, intrusion detection, disaster rescue, highway traffic coordination, etc. where they must not violate the real-time constraints. Therefore, we also consider the problem of deploying multiple sinks in order to improve the network performance. Previous research has only parts of this problem in isolation, and has not properly considered the problems of moving through a constrained environment or discovering changes to that environment during the repair or network quality after the restoration. In this thesis, we firstly consider a base problem in which we assume the exploration tasks have already been completed, and so our aim is to optimise our use of resources in the static fully observed problem. In the real world, we would not know the radio and physical environments after damage, and this creates a dynamic problem where damage must be discovered. Therefore, we extend to the dynamic problem in which the network repair problem considers both exploration and restoration. We then add a hop-count constraint for network quality in which the desired locations can talk to a sink within a hop count limit after the network is restored. For each new problem of the network repair, we have proposed different solutions (heuristics and/or complete algorithms) which prioritise different objectives. We evaluate our solutions based on simulation, assessing the quality of solutions (node cost, movement cost, computation time, and total restoration time) by varying the problem types and the capability of the agent that makes the repair. We show that the relative importance of the objectives influences the choice of algorithm, and different speeds of movement for the repairing agent have a significant impact on performance, and must be taken into account when selecting the algorithm. In particular, the node-based approaches are the best in the node cost, and the path-based approaches are the best in the mobility cost. For the total restoration time, the node-based approaches are the best with a fast moving agent while the path-based approaches are the best with a slow moving agent. For a medium speed moving agent, the total restoration time of the node-based approaches and that of the path-based approaches are almost balanced.

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.

The life history and ecology of black scabbardfish (Aphanopus carbo Lowe 1839) in the north-east Atlantic

The black scabbardfish is a deep water species that supports commercial fisheries across a large area of the NE Atlantic shelf. The life history of black scabbardfish is poorly understood and a major unresolved issue is population structure. In this study it was used a combination of methodologies to get further knowledge in the life history and population structure of A. carbo over its wide distribution range in the Northeast Atlantic. The new knowledge acquired during this study, will increase our ability to better manage this species in the NE Atlantic. It has been postulated that fish caught to the west of the British Isles are pre-adults that migrate further south (to Madeira) for spawning, implying a single panmictic population. In this study, specimens of Aphanopus carbo were sampled between September 2008 and May 2010 from two different areas: NW Scotland (French trawlers and deep water surveys) and Madeira Islands (longliners commercial landings). Geographical differences in reproductive state of scabbardfish were evident, supportive of a north-south migration theory. In the northern area, all specimens found were immature, while in Madeira all maturity stages were observed. In Madeira, spawning occurred during the fourth quarter, with peak maturity in October (males) and in November (females). The age of this species has proven difficult and has led to different and contradictory age and growth estimates. For this study, we used two reading interpretations to determine age and estimate the growth parameters. To the west of the British Isles, specimens reached a lower maximum age and had a higher growth rate than those caught off Madeira. These differences are consistent with the theory of a single population of black scabbardfish in the NE Atlantic, highly segregate, with smaller, immature and younger fish caught to the west of the British Isles and bigger and mature caught in Madeira Islands. The feeding ecology showed strong evidence that the diet of black scabbardfish is associated with the spawning migration of blue whiting, which may support a northerly feeding migration theory for black scabbardfish. The stable isotope analyses in the muscle of black scabbardfish identified that black scabbardfish feeds on species with epipelagic and benthopelagic affinities. Comparison with stable isotope analysis in Madeira samples indicated that black scabbardfish feed at a similar trophic level and has the same trophic niche width in both areas, assuming similar baseline isotope compositions. Otolith stable isotopes (oxygen - δ18O and nitrogen - δ15N) analyses were used as a tool to clarify migratory behaviour. Otolith isotope ratios can provide insight into whether adults caught around Madeira fed in an isotopically depleted northerly ecosystem (NW Scotland) during their pre-adult period and then migrate towards south to spawn. Overall, the results support a south-north migration of pre adult fish from spawning areas around Madeira and a north-south migration from the west of Scotland to the spawning areas. Given its life cycle there is an urgent need that the management process recognizes the existence of a continuous widely distributed stock of black scabbardfish between the west of the British Isles and Madeira. The results highlight large scale dispersal in this species which needs to be treated as a highly migratory species and be managed as a single population.