Optimisation problems in wireless sensor networks

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.

Studies on the optimisation of unbalanced magnetron sputtering cathodes

The optimisation is reported on the design of unbalanced magnetron (UBM) sputtering cathodes. For the study, a planar circular cathode backed by a double-coil electromagnet (compatible for a 100 mm diameter target) was developed. The variation of the structure and strength of the magnetic field in front of the target was investigated for different current combinations in the electromagnetic coils, and its effect on the sputtering process was analysed. The observations on the magnetic field geometry revealed some interesting features, such as the balancing point of the fields along the axis (null-point), and the zero axial region over the target surface (B-z = 0 ring). The positions of both could be controlled by adjusting the ratio of the electric current in the coils. The magnetic field null-point could be used as a reference for the region of homogeneous film growth. The B-z = 0 ring was the location where the glow discharge concentrated (or where the maximum target erosion occurred). The diameter of the ring determined the area covered by the discharge and thus the sputtering efficiency. The optimum substrate position can be fixed according to the position of the null-point and optimisation of sputtering can be achieved by adjusting the diameter of the B-z = 0 ring. The results of this study should be helpful in the designing of an ideal UBM using permanent magnets as well as electromagnets. (C) 1999 Elsevier Science Ltd. All rights reserved.

Quasicrystalline Coatings Through Laser Processing: A Study on Process Optimisation and Microstructure Evolution

Composite coatings containing quasicrystalline (QC) phases in Al-Cu-Fe alloys were prepared by laser cladding using a mixture of the elemental powders. Two substrates, namely pure aluminum and an Al-Si alloy were used. The clad layers were remelted at different scanning velocities to alter the growth conditions of different phases. The process parameters were optimized to produce quasicrystalline phases. The evolution of the microstructure in the coating layer was characterized by detailed microstructural investigation. The results indicate presence of quasicrystals in the aluminum substrate. However, only approximant phase could be observed in the substrate of Al-Si alloys. It is shown that there is a significant transport of Si atoms from the substrate to the clad layer during the cladding and remelting process. The hardness profiles of coatings on aluminum substrate indicate a very high hardness. The coating on Al-Si alloy, on the other hand, is ductile and soft. The fracture toughness of the hard coating on aluminum was obtained by nano-indentation technique. The K1C value was found to be 1.33 MPa m1/2 which is typical of brittle materials.

Surrogate based design optimisation of composite aerofoil cross-section for helicopter vibration reduction

Design optimisation of a helicopter rotor blade is performed. The objective is to reduce helicopter vibration and constraints are put on frequencies and aeroelastic stability. The ply angles of the D-spar and skin of the composite rotor blade with NACA 0015 aerofoil section are considered as design variables. Polynomial response surfaces and space filling experimental designs are used to generate surrogate models of the objective function with respect to cross-section properties. The stacking sequence corresponding to the optimal cross-section is found using a real-coded genetic algorithm. Ply angle discretisation of 1 degrees, 15 degrees, 30 degrees and 45 degrees are used. The mean value of the objective function is used to find the optimal blade designs and the resulting designs are tested for variance. The optimal designs show a vibration reduction of 26% to 33% from the baseline design. A substantial reduction in vibration and an aeroelastically stable blade is obtained even after accounting for composite material uncertainty.

Multi-objective optimization of satellite image registration using discrete Pparticle swarm optimisation

A new multi-sensor image registration technique is proposed based on detecting the feature corner points using modified Harris Corner Detector (HDC). These feature points are matched using multi-objective optimization (distance condition and angle criterion) based on Discrete Particle Swarm Optimization (DPSO). This optimization process is more efficient as it considers both the distance and angle criteria to incorporate multi-objective switching in the fitness function. This optimization process helps in picking up three corresponding corner points detected in the sensed and base image and thereby using the affine transformation, the sensed image is aligned with the base image. Further, the results show that the new approach can provide a new dimension in solving multi-sensor image registration problems. From the obtained results, the performance of image registration is evaluated and is concluded that the proposed approach is efficient.

Heterogeneous locational optimisation using a generalised Voronoi partition

In this paper a generalisation of the Voronoi partition is used for locational optimisation of facilities having different service capabilities and limited range or reach. The facilities can be stationary, such as base stations in a cellular network, hospitals, schools, etc., or mobile units, such as multiple unmanned aerial vehicles, automated guided vehicles, etc., carrying sensors, or mobile units carrying relief personnel and materials. An objective function for optimal deployment of the facilities is formulated, and its critical points are determined. The locally optimal deployment is shown to be a generalised centroidal Voronoi configuration in which the facilities are located at the centroids of the corresponding generalised Voronoi cells. The problem is formulated for more general mobile facilities, and formal results on the stability, convergence and spatial distribution of the proposed control laws responsible for the motion of the agents carrying facilities, under some constraints on the agents' speed and limit on the sensor range, are provided. The theoretical results are supported with illustrative simulation results.

Optimisation of an asymmetric polymerase chain reaction assay for the amplification of single-stranded DNA from Wuchereria bancrofti for electrochemical detection

Single-stranded DNA (ssDNA) is a prerequisite for electrochemical sensor-based detection of parasite DNA and other diagnostic applications. To achieve this detection, an asymmetric polymerase chain reaction method was optimised. This method facilitates amplification of ssDNA from the human lymphatic filarial parasite Wuchereria bancrofti. This procedure produced ssDNA fragments of 188 bp in a single step when primer pairs (forward and reverse) were used at a 100:1 molar ratio in the presence of double-stranded template DNA. The ssDNA thus produced was suitable for immobilisation as probe onto the surface of an Indium tin oxide electrode and hybridisation in a system for sequence-specific electrochemical detection of W. bancrofti. The hybridisation of the ssDNA probe and target ssDNA led to considerable decreases in both the anodic and the cathodic currents of the system's redox couple compared with the unhybridised DNA and could be detected via cyclic voltammetry. This method is reproducible and avoids many of the difficulties encountered by conventional methods of filarial parasite DNA detection; thus, it has potential in xenomonitoring.

Target reliability-based optimisation for internal seismic stability of reinforced soil structures

In this paper, an approach for target component and system reliability-based design optimisation (RBDO) to evaluate safety for the internal seismic stability of geosynthetic-reinforced soil (GRS) structures is presented. Three modes of failure are considered: tension failure of the bottom-most layer of reinforcement, pullout failure of the topmost layer of reinforcement, and total pullout failure of all reinforcement layers. The analysis is performed by treating backfill properties, geometric and strength properties of reinforcement as random variables. The optimum number of reinforcement layers and optimum pullout length needed to maintain stability against tension failure, pullout failure and total pullout failure for different coefficients of variation of friction angle of the backfill, design strength of the reinforcement and horizontal seismic acceleration coefficients by targeting various system reliability indices are proposed. The results provide guidelines for the total length of reinforcement required, considering the variability of backfill as well as seismic coefficients. One illustrative example is presented to explain the evaluation of reliability for internal stability of reinforced soil structures using the proposed approach. In the second illustration (the stability of five walls), the Kushiro wall subjected to the Kushiro-Oki earthquake, the Seiken wall subjected to the Chiba-ken Toho-Oki earthquake, the Ta Kung wall subjected to the Ji-Ji earthquake, and the Gould and Valencia walls subjected to Northridge earthquake are re-examined.