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.

Coupled electrostatic-elastic analysis for topology optimization using material interpolation

In this paper, we present a novel analytical formulation for the coupled partial differential equations governing electrostatically actuated constrained elastic structures of inhomogeneous material composition. We also present a computationally efficient numerical framework for solving the coupled equations over a reference domain with a fixed finite-element mesh. This serves two purposes: (i) a series of problems with varying geometries and piece-wise homogeneous and/or inhomogeneous material distribution can be solved with a single pre-processing step, (ii) topology optimization methods can be easily implemented by interpolating the material at each point in the reference domain from a void to a dielectric or a conductor. This is attained by considering the steady-state electrical current conduction equation with a `leaky capacitor' model instead of the usual electrostatic equation. This formulation is amenable for both static and transient problems in the elastic domain coupled with the quasi-electrostatic electric field. The procedure is numerically implemented on the COMSOL Multiphysics (R) platform using the weak variational form of the governing equations. Examples have been presented to show the accuracy and versatility of the scheme. The accuracy of the scheme is validated for the special case of piece-wise homogeneous material in the limit of the leaky-capacitor model approaching the ideal case.

Topology of wolfgram proteins and 2?, 3?-cyclic nucleotide 3?-phosphodiesterase in CNS myelin: Studies with proteases

The topological disposition of Wolfgram proteins (WP) and their relationship with 2', 3'-cyclic nucleotide 3'-phosphodiesterase (CNPase) in human, rat, sheep, bovine, guinea pig and chicken CNS myelin was investigated. Controlled digestion of myelin with trypsin gave a 35KDa protein band (WP-t) when electrophoresed on dodecyl sulfate-polyacrylamide gel in all species. Western blot analysis showed that the WP-t was derived from WP. WP-t was also formed when rat myelin was treated with other proteases such as kallikrein, thermolysin and leucine aminopeptidase. Staining for CNPase activity on nitrocellulose blots showed that WP-t is enzymatically active. Much of the CNPase activity remained with the membrane fraction even after treatment with high concentrations of trypsin when WP were completely hydrolysed and no protein bands with M.W > 14KDa were detected on the gels. Therefore protein fragments of WP with M.W < 14KDa may contain CNPase activity. From these results, it is suggested that the topological disposition of all the various WP is such that a 35KDa fragment is embedded in the lipid bilayer and the remaining fragment exposed at the intraperiod line in the myelin structure which may play a role in the initiation of myelinogenesis.

Solid-state photobehaviour and crystal packing of o-chlorobenzylidene-DL-piperitone: influence of molecular topology on photobehaviour

C17H19ClO, M(r) = 274.7, triclinic, P1BAR, a = 11.154 (3), b = 12.685 (2), c = 12.713 (2) angstrom, alpha = 100.68 (1), beta = 113.58 (1), gamma = 104.50 (2)-degrees, V = 1511.1 (6) angstrom3, Z = 4, D(m) = 1.22, D(x) = 1.215 Mg m-3, Cu K-alpha, lambda = 1.5418 angstrom, mu = 2.16 mm-1, F(000) = 584, T = 293 K, R = 0.057 for 3481 observed reflections. The title compound is photostable in the crystalline state and lattice-energy calculations have been employed to rationalize the photobehaviour. The well-known beta-steering ability of the chloro group is not operative in this system as there are no Cl...Cl interactions in the crystal lattice. All five benzylidene-DL-piperitone structures so far studied are alpha-packed and the molecular topology appears to be a deciding factor even in the presence of steering groups.

Parallel implementation of alternate quadrant interlocking factorisation method on star topology

This paper discusses the parallel implementation of the solution of a set of linear equations using the Alternative Quadrant Interlocking Factorisation Methods (AQIF), on a star topology. Both the AQIF and LU decomposition methods are mapped onto star topology on an IBM SP2 system, with MPI as the internode communicator. Performance parameters such as speedup, efficiency have been obtained through experimental and theoretical means. The studies demonstrate (i) a mismatch of 15% between the theoretical and experimental results, (ii) scalability of the AQIF algorithm, and (iii) faster executing AQIF algorithm.

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.

Synthesis of workspaces of planar manipulators with arbitrary topology using shape representation and simulated annealing

This paper presents a general methodology for the synthesis of the external boundary of the workspaces of a planar manipulator with arbitrary topology. Both the desired workspace and the manipulator workspaces are identified by their boundaries and are treated as simple closed polygons. The paper introduces the concept of best match configuration and shows that the corresponding transformation can be obtained by using the concept of shape normalization available in image processing literature. Introduction of the concept of shape in workspace synthesis allows highly accurate synthesis with fewer numbers of design variables. This paper uses a new global property based vector representation for the shape of the workspaces which is computationally efficient because six out of the seven elements of this vector are obtained as a by-product of the shape normalization procedure. The synthesis of workspaces is formulated as an optimization problem where the distance between the shape vector of the desired workspace and that of the workspace of the manipulator at hand are minimized by changing the dimensional parameters of the manipulator. In view of the irregular nature of the error manifold, the statistical optimization procedure of simulated annealing has been used. A number of worked-out examples illustrate the generality and efficiency of the present method. (C) 1998 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.

A Novel VSI- and CSI-Fed Dual Stator Induction Motor Drive Topology for Medium-Voltage Drive Applications

A new configuration is proposed for high-power induction motor drives. The induction machine is provided with two three-phase stator windings with their axes in line. One winding is designed for higher voltage and is meant to handle the main (active) power. The second winding is designed for lower voltage and is meant to carry the excitation (reactive) power. The excitation winding is powered by an insulated-gate-bipolar-transistor-based voltage source inverter with an output filter. The power winding is fed by a load-commutated current source inverter. The commutation of thyristors in the load-commutated inverter (LCI) is achieved by injecting the required leading reactive power from the excitation inverter. The MMF harmonics due to the LCI current are also cancelled out by injecting a suitable compensating component from the excitation inverter, so that the electromagnetic torque of the machine is smooth. Results from a prototype drive are presented to demonstrate the concept.

A Seven-Level Inverter Topology for Induction Motor Drive Using Two-Level Inverters and Floating Capacitor Fed H-Bridges

A multilevel inverter topology for seven-level space vector generation is proposed in this paper. In this topology, the seven-level structure is realized using two conventional two-level inverters and six capacitor-fed H-bridge cells. It needs only two isolated dc-voltage sources of voltage rating V(dc)/2 where V(dc) is the dc voltage magnitude required by the conventional neutral point clamped (NPC) seven-level topology. The proposed topology is capable of maintaining the H-bridge capacitor voltages at the required level of V(dc)/6 under all operating conditions, covering the entire linear modulation and overmodulation regions, by making use of the switching state redundancies. In the event of any switch failure in H-bridges, this inverter can operate in three-level mode, a feature that enhances the reliability of the drive system. The two-level inverters, which operate at a higher voltage level of V(dc)/2, switch less compared to the H-bridges, which operate at a lower voltage level of V(dc)/6, resulting in switching loss reduction. The experimental verification of the proposed topology is carried out for the entire modulation range, under steady state as well as transient conditions.

Topology Optimization of Micromachined Structures with the Manufacturing Constraints of KOH Etching of (110) Silicon

The focus of this paper is on designing useful compliant micro-mechanisms of high-aspect-ratio which can be microfabricated by the cost-effective wet etching of (110) orientation silicon (Si) wafers. Wet etching of (110) Si imposes constraints on the geometry of the realized mechanisms because it allows only etch-through in the form of slots parallel to the wafer's flat with a certain minimum length. In this paper, we incorporate this constraint in the topology optimization and obtain compliant designs that meet the specifications on the desired motion for given input forces. Using this design technique and wet etching, we show that we can realize high-aspect-ratio compliant micro-mechanisms. For a (110) Si wafer of 250 µm thickness, the minimum length of the etch opening to get a slot is found to be 866 µm. The minimum achievable width of the slot is limited by the resolution of the lithography process and this can be a very small value. This is studied by conducting trials with different mask layouts on a (110) Si wafer. These constraints are taken care of by using a suitable design parameterization rather than by imposing the constraints explicitly. Topology optimization, as is well known, gives designs using only the essential design specifications. In this work, we show that our technique also gives manufacturable mechanism designs along with lithography mask layouts. Some designs obtained are transferred to lithography masks and mechanisms are fabricated on (110) Si wafers.

A Comparative Study of the Formulations for Topology Optimization of Compliant Mechanisms

The topology optimization problem for the synthesis of compliant mechanisms has been formulated in many different ways in the last 15 years, but there is not yet a definitive formulation that is universally accepted. Furthermore, there are two unresolved issues in this problem. In this paper, we present a comparative study of five distinctly different formulations that are reported in the literature. Three benchmark examples are solved with these formulations using the same input and output specifications and the same numerical optimization algorithm. A total of 35 different synthesis examples are implemented. The examples are limited to desired instantaneous output direction for prescribed input force direction. Hence, this study is limited to linear elastic modeling with small deformations. Two design parameterizations, namely, the frame element based ground structure and the density approach using continuum elements, are used. The obtained designs are evaluated with all other objective functions and are compared with each other. The checkerboard patterns, point flexures, the ability to converge from an unbiased uniform initial guess, and the computation time are analyzed. Some observations are noted based on the extensive implementation done in this study. Complete details of the benchmark problems and the results are included. The computer codes related to this study are made available on the internet for ready access.

Cojoined Irregular Topology and Routing Table Generation for Network-on-Chip

Scalable Networks on Chips (NoCs) are needed to match the ever-increasing communication demands of large-scale Multi-Processor Systems-on-chip (MPSoCs) for multi media communication applications. The heterogeneous nature of application specific on-chip cores along with the specific communication requirements among the cores calls for the design of application-specific NoCs for improved performance in terms of communication energy, latency, and throughput. In this work, we propose a methodology for the design of customized irregular networks-on-chip. The proposed method exploits a priori knowledge of the applications communication characteristic to generate an optimized network topology and corresponding routing tables.