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.

A simple local 3-approximation algorithm for vertex cover

We present a local algorithm (constant-time distributed algorithm) for finding a 3-approximate vertex cover in bounded-degree graphs. The algorithm is deterministic, and no auxiliary information besides port numbering is required. (c) 2009 Elsevier B.V. All rights reserved.

Free vibration of rectangular beams of arbitrary depth

The state space approach is extended to the two dimensional elastodynamic problems. The formulation is in a form particularly amenable to consistent reduction to obtain approximate theories of any desired order. Free vibration of rectangular beams of arbitrary depth is investigated using this approach. The method does not involve the concept of the shear coefficientk. It takes into account the vertical normal stress and the transverse shear stress. The frequency values are calculated using the Timoshenko beam theory and the present analysis for different values of Poisson's ratio and they are in good agreement. Four cases of beams with different end conditions are considered.Die Zustandsraum-Technik wird auf zweidimensionale elastodynamische Probleme ausgedehnt. Die Formulierung ist besonders geeignet für die Aufstellung von Näherungstheorien beliebigen Grades. Freie Schwingungen von Rechteckbalken beliebiger Höhe wurden mit Hilfe dieser Technik untersucht. Das Verfahren umgeht den Begriff des Schubbeiwertsk. Es berücksichtigt die senkrechte Normalbeanspruchung und die Querkraft. Die Frequenzwerte werden mit Hilfe der Balkentheorie von Timoshenko und der vorliegenden Analyse berechnet, und zwar für verschiedene Werte der Querdehnzahl. Die berechneten Werte befinden sich in guter Übereinstimmung. Vier Fälle von Balken mit verschiedenen Endbedingungen werden untersucht.

Structure, dielectric, and magnetic properties of Sr2TiMnO6 ceramics

Sr2TiMnO6, a double perovskite associated with high degree of B-site cation disorder was investigated in detail for its structural, magnetic, and dielectric properties. Though x-ray powder diffraction analysis confirms its cubic structure, first order Raman scattering and infrared reflectivity spectra indicate a breaking of the local cubic symmetry. The magnetization study reveals an anomaly at 14 K owing to a ferrimagnetic/canted antiferromagneticlike ordering arising from local Mn-O-Mn clusters. Saturated M-H hysteresis loops obtained at 5 K also reflect the weak ferromagnetic exchange interactions present in the system and an approximate estimation of Mn3+/Mn4+ was done using the magnetization data for the samples sintered at different temperatures. The conductivity and dielectric behavior of this system has been investigated in a broad temperature range of 10 to 300 K. Intrinsic permittivity was obtained only below 100 K whereas giant permittivity due to conductivity and Maxwell-Wagner polarization was observed at higher temperatures. X-ray photoemission studies further confirmed the presence of mixed oxidation states of Mn and the valence band spectra analysis was carried out in detail. (C) 2010 American Institute of Physics. doi: 10.1063/1.3500369]

Structural Relationships in 2,3-Bis-n-decyloxyanthracene and 12-Hydroxystearic Acid Molecular Gels and Aerogels Processed in Supercritical CO2

Supercritical carbon dioxide is used to prepare aerogels of two reference molecular organogelators, 2,3-bis-n-decyloxyanthracene (DDOA) (luminescent molecule) and 12-hydroxystearic acid (HSA). Electron microscopy reveals the fibrillar morphology of the aggregates generated by the protocol. SAXS and SANS measurements show that DDOA aerogels are crystalline materials exhibiting three morphs: (1) arrangements of the crystalline solid (2D p6m), (2) a second hexagonal morph slightly more compact, and (3) a packing specific of the fibers in the gel. Aggregates specific of the aerogel (volume fraction being typically phi approximate to 0.60) are developed over larger distances (similar to 1000 angstrom) and bear fewer defaults and residual strains than aggregates in the crystalline and gel phases. Porod, Scherrer and Debye-Bueche analyses of the scattering data have been performed. The first five diffraction peaks show small variations in position and intensity assigned to the variation of the number of fibers and their degree of vicinity within hexagonal bundles of the related SAFIN according to the Oster model. Conclusions are supported by the guidelines offered by the analysis of the situation in HSA aerogels for which the diffraction pattern can be described by two coexisting lamellar-like arrangements. The porosity of the aerogel, as measured by its specific surface extracted from the scattering invariant analysis, is only 1.8 times less than that of the swollen gel and is characteristic of a very porous material.

Stiffness Coefficients of Layered Soil Systems

One of the most important dynamic properties required in the design of machine foundations is the stiffness or spring constant of the supporting soil. For a layered soil system, the stiffness obtained from an idealization of soils underneath as springs in series gives the same value of stiffness regardless of the location and extent of individual soil layers with respect to the base of the foundation. This paper aims to develop the importance of the relative positioning of soil layers and their thickness beneath the foundation. A simple and approximate procedure called the weighted average method has been proposed to obtain the equivalent stiffness of a layered soil system knowing the individual values of the layers, their relative position with respect to foundation base, and their thicknesses. The theoretically estimated values from the weighted average method are compared with those obtained by conducting field vibration tests using a square footing over different two- and three-layered systems and are found to be very good. The tests were conducted over a range of static and dynamic loads using three different materials. The results are also compared with the existing methods available in the literature.

Integral method for the calculation of incompressible two-dimensional transitional boundary layers

The method proposed here considers the mean flow in the transition zone as a linear combination of the laminar and turbulent boundary layer in proportions determined by the transitional intermittency, the component flows being calculated by approximate integral methods. The intermittency distribution adopted takes into account the possibility of subtransitions within the zone in the presence of strong pressure gradients. A new nondimensional spot formation rate, whose value depends on the pressure gradient, is utilized to estimate the extent of the transition zone. Onset location is determined by a correlation that takes into account freestream turbulence and facility-specific residual disturbances in test data. Extensive comparisons with available experimental results in strong pressure gradients show that the proposed method performs at least as well as differential models, in many cases better, and is always faster.

Support vector machine for evaluating seismic-liquefaction potential using shear wave velocity

The use of the shear wave velocity data as a field index for evaluating the liquefaction potential of sands is receiving increased attention because both shear wave velocity and liquefaction resistance are similarly influenced by many of the same factors such as void ratio, state of stress, stress history and geologic age. In this paper, the potential of support vector machine (SVM) based classification approach has been used to assess the liquefaction potential from actual shear wave velocity data. In this approach, an approximate implementation of a structural risk minimization (SRM) induction principle is done, which aims at minimizing a bound on the generalization error of a model rather than minimizing only the mean square error over the data set. Here SVM has been used as a classification tool to predict liquefaction potential of a soil based on shear wave velocity. The dataset consists the information of soil characteristics such as effective vertical stress (sigma'(v0)), soil type, shear wave velocity (V-s) and earthquake parameters such as peak horizontal acceleration (a(max)) and earthquake magnitude (M). Out of the available 186 datasets, 130 are considered for training and remaining 56 are used for testing the model. The study indicated that SVM can successfully model the complex relationship between seismic parameters, soil parameters and the liquefaction potential. In the model based on soil characteristics, the input parameters used are sigma'(v0), soil type. V-s, a(max) and M. In the other model based on shear wave velocity alone uses V-s, a(max) and M as input parameters. In this paper, it has been demonstrated that Vs alone can be used to predict the liquefaction potential of a soil using a support vector machine model. (C) 2010 Elsevier B.V. All rights reserved.

Influence of water and thermal history on ion transport in lithium salt-succinonitrile plastic crystalline electrolytes

Important issues of water and thermal history affecting ion transport in a representative plastic crystalline lithium salt electrolyte: succinonitrile (SN)-lithium perchlorate (LiClO4) are discussed here. Ionic conductivity of electrolytes with high lithium salt amounts (similar to 1 M) in SN at a particular temperature is known to be influenced both by the trans-gauche isomerism and ion association (solvation), the two most important intrinsic parameters of the plastic solvent. In the present study both water and thermal history influence SN and result in enhancement of ionic conductivity of 1 M LiClO4-SN electrolyte. Systematic observations reveal that the presence of water in varying amounts promote ion-pair dissociation in the electrolyte. While trace amounts (approximate to 1-15 ppm) do not affect the trans-gauche isomerism of SN, the presence of water in large amounts (approximate to 5500 ppm) submerges the plasticity of SN. Subjugating the electrolyte to different thermal protocol resulted in enhancement of trans concentration only. This is an interesting observation as it demonstrates a simple and effective procedure involving utilization of an optimized set of external parameters to decouple solvation from trans-gauche isomerism. Observations from the ionic conductivity of various samples were accounted by changes in signature isomer and ion-association bands in the mid-IR regime and also from plastic to normal crystal transition temperature peak obtained from thermal studies. (C) 2010 Elsevier B.V. All rights reserved.

Boxicity and Poset Dimension

Let G be a simple, undirected, finite graph with vertex set V(G) and edge set E(C). A k-dimensional box is a Cartesian product of closed intervals a(1), b(1)] x a(2), b(2)] x ... x a(k), b(k)]. The boxicity of G, box(G) is the minimum integer k such that G can be represented as the intersection graph of k-dimensional boxes, i.e. each vertex is mapped to a k-dimensional box and two vertices are adjacent in G if and only if their corresponding boxes intersect. Let P = (S, P) be a poset where S is the ground set and P is a reflexive, anti-symmetric and transitive binary relation on S. The dimension of P, dim(P) is the minimum integer l such that P can be expressed as the intersection of t total orders. Let G(P) be the underlying comparability graph of P. It is a well-known fact that posets with the same underlying comparability graph have the same dimension. The first result of this paper links the dimension of a poset to the boxicity of its underlying comparability graph. In particular, we show that for any poset P, box(G(P))/(chi(G(P)) - 1) <= dim(P) <= 2box(G(P)), where chi(G(P)) is the chromatic number of G(P) and chi(G(P)) not equal 1. The second result of the paper relates the boxicity of a graph G with a natural partial order associated with its extended double cover, denoted as G(c). Let P-c be the natural height-2 poset associated with G(c) by making A the set of minimal elements and B the set of maximal elements. We show that box(G)/2 <= dim(P-c) <= 2box(G) + 4. These results have some immediate and significant consequences. The upper bound dim(P) <= 2box(G(P)) allows us to derive hitherto unknown upper bounds for poset dimension. In the other direction, using the already known bounds for partial order dimension we get the following: (I) The boxicity of any graph with maximum degree Delta is O(Delta log(2) Delta) which is an improvement over the best known upper bound of Delta(2) + 2. (2) There exist graphs with boxicity Omega(Delta log Delta). This disproves a conjecture that the boxicity of a graph is O(Delta). (3) There exists no polynomial-time algorithm to approximate the boxicity of a bipartite graph on n vertices with a factor of O(n(0.5-epsilon)) for any epsilon > 0, unless NP=ZPP.

New Approximation Algorithms for Minimum Cycle Bases of Graphs

We consider the problem of computing an approximate minimum cycle basis of an undirected non-negative edge-weighted graph G with m edges and n vertices; the extension to directed graphs is also discussed. In this problem, a {0,1} incidence vector is associated with each cycle and the vector space over F-2 generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for its cycle space. A cycle basis where the sum of the weights of the cycles is minimum is called a minimum cycle basis of G. Cycle bases of low weight are useful in a number of contexts, e.g. the analysis of electrical networks, structural engineering, chemistry, and surface reconstruction. Although in most such applications any cycle basis can be used, a low weight cycle basis often translates to better performance and/or numerical stability. Despite the fact that the problem can be solved exactly in polynomial time, we design approximation algorithms since the performance of the exact algorithms may be too expensive for some practical applications. We present two new algorithms to compute an approximate minimum cycle basis. For any integer k >= 1, we give (2k - 1)-approximation algorithms with expected running time O(kmn(1+2/k) + mn((1+1/k)(omega-1))) and deterministic running time O(n(3+2/k) ), respectively. Here omega is the best exponent of matrix multiplication. It is presently known that omega < 2.376. Both algorithms are o(m(omega)) for dense graphs. This is the first time that any algorithm which computes sparse cycle bases with a guarantee drops below the Theta(m(omega) ) bound. We also present a 2-approximation algorithm with expected running time O(M-omega root n log n), a linear time 2-approximation algorithm for planar graphs and an O(n(3)) time 2.42-approximation algorithm for the complete Euclidean graph in the plane.

Transverse plane wave analysis of short elliptical chamber mufflers: An analytical approach

Short elliptical chamber mufflers are used often in the modern day automotive exhaust systems. The acoustic analysis of such short chamber mufflers is facilitated by considering a transverse plane wave propagation model along the major axis up to the low frequency limit. The one dimensional differential equation governing the transverse plane wave propagation in such short chambers is solved using the segmentation approaches which are inherently numerical schemes, wherein the transfer matrix relating the upstream state variables to the downstream variables is obtained. Analytical solution of the transverse plane wave model used to analyze such short chambers has not been reported in the literature so far. This present work is thus an attempt to fill up this lacuna, whereby Frobenius solution of the differential equation governing the transverse plane wave propagation is obtained. By taking a sufficient number of terms of the infinite series, an approximate analytical solution so obtained shows good convergence up to about 1300 Hz and also covers most of the range of muffler dimensions used in practice. The transmission loss (TL) performance of the muffler configurations computed by this analytical approach agrees excellently with that computed by the Matrizant approach used earlier by the authors, thereby offering a faster and more elegant alternate method to analyze short elliptical muffler configurations. (C) 2010 Elsevier Ltd. All rights reserved.

Theoretical and Computational Analysis of Static and Dynamic Anomalies in Water-DMSO Binary Mixture at Low DMSO Concentrations

Experiments have repeatedly observed both thermodynamic and dynamic anomalies in aqueous binary mixtures, surprisingly at low solute concentration. Examples of such binary mixtures include water-DMSO, water-ethanol, water-tertiary butyl alcohol (TBA), and water-dioxane, to name a few. The anomalies have often been attributed to the onset of a structural transition, whose nature, however, has been left rather unclear. Here we study the origin of such anomalies using large scale computer simulations and theoretical analysis in water-DMSO binary mixture. At very low DMSO concentration (below 10%), small aggregates of DMSO are solvated by water through the formation of DMSO-(H2O)(2) moieties. As the concentration is increased beyond 10-12% of DMSO, spanning clusters comprising the same moieties appear in the system. Those clusters are formed and stabilized not only through H-bonding but also through the association of CH3 groups of DMSO. We attribute the experimentally observed anomalies to a continuum percolation-like transition at DMSO concentration X-DMSO approximate to 12-15%. The largest cluster size of CH3-CH3 aggregation clearly indicates the formation of such percolating clusters. As a result, a significant slowing down is observed in the decay of associated rotational auto time correlation functions (of the S = O bond vector of DMSO and O-H bond vector of water). Markedly unusual behavior in the mean square fluctuation of total dipole moment again suggests a structural transition around the same concentration range. Furthermore, we map our findings to an interacting lattice model which substantiates the continuum percolation model as the reason for low concentration anomalies in binary mixtures where the solutes involved have both hydrophilic and hydrophobic moieties.

Dynamic scheduling in manufacturing systems using brownian approximations

Recently, Brownian networks have emerged as an effective stochastic model to approximate multiclass queueing networks with dynamic scheduling capability, under conditions of balanced heavy loading. This paper is a tutorial introduction to dynamic scheduling in manufacturing systems using Brownian networks. The article starts with motivational examples. It then provides a review of relevant weak convergence concepts, followed by a description of the limiting behaviour of queueing systems under heavy traffic. The Brownian approximation procedure is discussed in detail and generic case studies are provided to illustrate the procedure and demonstrate its effectiveness. This paper places emphasis only on the results and aspires to provide the reader with an up-to-date understanding of dynamic scheduling based on Brownian approximations.

Effect of substitution of Y on the structural, magnetic, and thermal properties of hexagonal DyMnO3 single crystals

We investigate the structural, magnetic, and specific heat behavior of the hexagonal manganite Dy0.5Y0.5MnO3 in order to understand the effect of dilution of Dy magnetism with nonmagnetic yttrium. In this compound, the triangular Mn lattice orders antiferromagnetic at T-N(Mn) approximate to 68 K observed experimentally in the derivative of magnetic susceptibility as well as in specific heat. In addition, a low-temperature peak at T-N(Dy) similar to 3 K is observed in specific heat which is attributed to rare earth order. The T-N(Mn) increases by 9 K compared to that of hexagonal (h) DyMnO3 while T-N(Dy) is unchanged. A change in slope of thermal evolution of lattice parameters is observed to occur at temperature close to T-N(Mn). This hints at strong magnetoelastic coupling in this geometric multiferroic. In magnetization measurements, steplike features are observed when the magnetic field is applied along the c axis which shift to higher fields with temperature and vanish completely above 40 K. The presence of different magnetic phases at low temperature and strong magnetoelastic effects can lead to such field-induced transitions which resemble metamagnetic transitions. This indicates the possibility of strong field-induced effects in dielectric properties of this material, which is unexplored to date.