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 heuristic clustering algorithm using union of overlapping pattern-cells

Relative geometric arrangements of the sample points, with reference to the structure of the imbedding space, produce clusters. Hence, if each sample point is imagined to acquire a volume of a small M-cube (called pattern-cell), depending on the ranges of its (M) features and number (N) of samples; then overlapping pattern-cells would indicate naturally closer sample-points. A chain or blob of such overlapping cells would mean a cluster and separate clusters would not share a common pattern-cell between them. The conditions and an analytic method to find such an overlap are developed. A simple, intuitive, nonparametric clustering procedure, based on such overlapping pattern-cells is presented. It may be classified as an agglomerative, hierarchical, linkage-type clustering procedure. The algorithm is fast, requires low storage and can identify irregular clusters. Two extensions of the algorithm, to separate overlapping clusters and to estimate the nature of pattern distributions in the sample space, are also indicated.

Segmenting point-sampled surfaces

Extracting features from point-based representations of geometric surface models is becoming increasingly important for purposes such as model classification, matching, and exploration. In an earlier paper, we proposed a multiphase segmentation process to identify elongated features in point-sampled surface models without the explicit construction of a mesh or other surface representation. The preliminary results demonstrated the strength and potential of the segmentation process, but the resulting segmentations were still of low quality, and the segmentation process could be slow. In this paper, we describe several algorithmic improvements to overcome the shortcomings of the segmentation process. To demonstrate the improved quality of the segmentation and the superior time efficiency of the new segmentation process, we present segmentation results obtained for various point-sampled surface models. We also discuss an application of our segmentation process to extract ridge-separated features in point-sampled surfaces of CAD models.

A Smooth Finite Element Method Based on Reproducing Kernel DMS-Splines

The element-based piecewise smooth functional approximation in the conventional finite element method (FEM) results in discontinuous first and higher order derivatives across element boundaries Despite the significant advantages of the FEM in modelling complicated geometries, a motivation in developing mesh-free methods has been the ease with which higher order globally smooth shape functions can be derived via the reproduction of polynomials There is thus a case for combining these advantages in a so-called hybrid scheme or a `smooth FEM' that, whilst retaining the popular mesh-based discretization, obtains shape functions with uniform C-p (p >= 1) continuity One such recent attempt, a NURBS based parametric bridging method (Shaw et al 2008b), uses polynomial reproducing, tensor-product non-uniform rational B-splines (NURBS) over a typical FE mesh and relies upon a (possibly piecewise) bijective geometric map between the physical domain and a rectangular (cuboidal) parametric domain The present work aims at a significant extension and improvement of this concept by replacing NURBS with DMS-splines (say, of degree n > 0) that are defined over triangles and provide Cn-1 continuity across the triangle edges This relieves the need for a geometric map that could precipitate ill-conditioning of the discretized equations Delaunay triangulation is used to discretize the physical domain and shape functions are constructed via the polynomial reproduction condition, which quite remarkably relieves the solution of its sensitive dependence on the selected knotsets Derivatives of shape functions are also constructed based on the principle of reproduction of derivatives of polynomials (Shaw and Roy 2008a) Within the present scheme, the triangles also serve as background integration cells in weak formulations thereby overcoming non-conformability issues Numerical examples involving the evaluation of derivatives of targeted functions up to the fourth order and applications of the method to a few boundary value problems of general interest in solid mechanics over (non-simply connected) bounded domains in 2D are presented towards the end of the paper

Effect of wall thickness on the end corrections of the extended inlet and outlet of a double-tuned expansion chamber

Simple expansion chambers, the simplest of the muffler configurations, have very limited practical application due to the presence of periodic troughs in the transmission loss spectrum which drastically lower the overall transmission loss of the muffler. Tuned extended inlet and outlet can be designed to nullify three-fourths of these troughs, making use of the plane wave theory. These cancellations would not occur unless one altered the geometric lengths for the extended tube in order to incorporate the effect of evanescent higher-order modes (multidimensional effect) through end corrections or lumped inertance approximation at the area discontinuities or junctions. End corrections of the extended inlet and outlet have been studied by several researchers. However the effect of wall thickness of the inlet/outlet duct on end correction has not been studied explicitly. This has significant effect on the tuning of an extended inlet/outlet expansion chamber. It is investigated here experimentally as well as numerically (through use of 3-D FEM software) for stationary medium. Crown Copyright (C) 2010 Published by Elsevier Ltd. All rights reserved.

A geodesic constant method for computing high-frequency mutual coupling between antennas on general quadric cylinders

A Geodesic Constant Method (GCM) is outlined which provides a common approach to ray tracing on quadric cylinders in general, and yields all the surface ray-geometric parameters required in the UTD mutual coupling analysis of conformal antenna arrays in the closed form. The approach permits the incorporation of a shaping parameter which permits the modeling of quadric cylindrical surfaces of desired sharpness/flatness with a common set of equations. The mutual admittance between the slots on a general parabolic cylinder is obtained as an illustration of the applicability of the GCM.

Phenyl-Ring-Bearing Cationic Surfactants: Effect of Ring Location on the Micellar Structure

A series of isomeric cationic surfactants (S1-S5) bearing a long alkyl chain that carries a 1,4-phenylene unit and a trimethyl ammonium headgroup was synthesized; the location of the phenyl ring within the alkyl tail was varied in an effort to understand its influence on the amphiphilic properties of the surfactants. The cmc's of the surfactants were estimated using ionic conductivity measurements and isothermal calorimetric titrations (ITC); the values obtained by the two methods were found to be in excellent agreement. The ITC measurements provided additional insight into the various thermodynamic parameters associated with the micellization process. Although all five surfactants have exactly the same molecular formula, their micellar properties were seen to vary dramatically depending on the location of the phenyl ring; the cmc was seen to decrease by almost an order of magnitude when the phenyl ring was moved from the tail end (cmc of S1 is 23 mM) to the headgroup region (cmc of S5 is 3 mM). In all cases, the enthalpy of micellization was negative but the entropy of micellization was positive, suggesting that in all of these systems the formation of micelles is both enthalpically and entropically favored. As expected, the decrease in cmc values upon moving the phenyl ring from the tail end to he headgroup region is accompanied by an increase in the thermodynamic driving force (Delta G) for micellization. To understand further the differences in the micellar structure of these surfactants, small-angle neutron scattering (SANS) measurements were carried out; these measurements reveal that the aggregation number of the micelles increases as the cmc decreases. This increase in the aggregation number is also accompanied by an increase in the asphericity of the micellar aggregate and a decrease in the fractional charge. Geometric packing arguments are presented to account for these changes in aggregation behavior as a function of phenyl ring location.

Planar subgraphs without low-degree nodes

We study the following problem: given a geometric graph G and an integer k, determine if G has a planar spanning subgraph (with the original embedding and straight-line edges) such that all nodes have degree at least k. If G is a unit disk graph, the problem is trivial to solve for k = 1. We show that even the slightest deviation from the trivial case (e.g., quasi unit disk graphs or k = 1) leads to NP-hard problems.

A maximal operator, Carleson's embedding, and tent spaces for vector-valued functions

This thesis is concerned with the area of vector-valued Harmonic Analysis, where the central theme is to determine how results from classical Harmonic Analysis generalize to functions with values in an infinite dimensional Banach space. The work consists of three articles and an introduction. The first article studies the Rademacher maximal function that was originally defined by T. Hytönen, A. McIntosh and P. Portal in 2008 in order to prove a vector-valued version of Carleson's embedding theorem. The boundedness of the corresponding maximal operator on Lebesgue-(Bochner) -spaces defines the RMF-property of the range space. It is shown that the RMF-property is equivalent to a weak type inequality, which does not depend for instance on the integrability exponent, hence providing more flexibility for the RMF-property. The second article, which is written in collaboration with T. Hytönen, studies a vector-valued Carleson's embedding theorem with respect to filtrations. An earlier proof of the dyadic version assumed that the range space satisfies a certain geometric type condition, which this article shows to be also necessary. The third article deals with a vector-valued generalizations of tent spaces, originally defined by R. R. Coifman, Y. Meyer and E. M. Stein in the 80's, and concerns especially the ones related to square functions. A natural assumption on the range space is then the UMD-property. The main result is an atomic decomposition for tent spaces with integrability exponent one. In order to suit the stochastic integrals appearing in the vector-valued formulation, the proof is based on a geometric lemma for cones and differs essentially from the classical proof. Vector-valued tent spaces have also found applications in functional calculi for bisectorial operators. In the introduction these three themes come together when studying paraproduct operators for vector-valued functions. The Rademacher maximal function and Carleson's embedding theorem were applied already by Hytönen, McIntosh and Portal in order to prove boundedness for the dyadic paraproduct operator on Lebesgue-Bochner -spaces assuming that the range space satisfies both UMD- and RMF-properties. Whether UMD implies RMF is thus an interesting question. Tent spaces, on the other hand, provide a method to study continuous time paraproduct operators, although the RMF-property is not yet understood in the framework of tent spaces.

Inverse problem for the wave equation : partial data and novel boundary sources

An inverse problem for the wave equation is a mathematical formulation of the problem to convert measurements of sound waves to information about the wave speed governing the propagation of the waves. This doctoral thesis extends the theory on the inverse problems for the wave equation in cases with partial measurement data and also considers detection of discontinuous interfaces in the wave speed. A possible application of the theory is obstetric sonography in which ultrasound measurements are transformed into an image of the fetus in its mother's uterus. The wave speed inside the body can not be directly observed but sound waves can be produced outside the body and their echoes from the body can be recorded. The present work contains five research articles. In the first and the fifth articles we show that it is possible to determine the wave speed uniquely by using far apart sound sources and receivers. This extends a previously known result which requires the sound waves to be produced and recorded in the same place. Our result is motivated by a possible application to reflection seismology which seeks to create an image of the Earth s crust from recording of echoes stimulated for example by explosions. For this purpose, the receivers can not typically lie near the powerful sound sources. In the second article we present a sound source that allows us to recover many essential features of the wave speed from the echo produced by the source. Moreover, these features are known to determine the wave speed under certain geometric assumptions. Previously known results permitted the same features to be recovered only by sequential measurement of echoes produced by multiple different sources. The reduced number of measurements could increase the number possible applications of acoustic probing. In the third and fourth articles we develop an acoustic probing method to locate discontinuous interfaces in the wave speed. These interfaces typically correspond to interfaces between different materials and their locations are of interest in many applications. There are many previous approaches to this problem but none of them exploits sound sources varying freely in time. Our use of more variable sources could allow more robust implementation of the probing.

Local variability and base sequence effects in DNA crystal structures.

The importance and usefulness of local doublet parameters in understanding sequence dependent effects has been described for A- and B-DNA oligonucleotide crystal structures. Each of the two sets of local parameters described by us in the NUPARM algorithm, namely the local doublet parameters, calculated with reference to the mean z-axis, and the local helical parameters, calculated with reference to the local helix axis, is sufficient to describe the oligonucleotide structures, with the local helical parameters giving a slightly magnified picture of the variations in the structures. The values of local doublet parameters calculated by NUPARM algorithm are similar to those calculated by NEWHELIX90 program, only if the oligonucleotide fragment is not too distorted. The mean values obtained using all the available data for B-DNA crystals are not significantly different from those obtained when a limited data set is used, consisting only of structures with a data resolution of better than 2.4 A and without any bound drug molecule. Thus the variation observed in the oligonucleotide crystals appears to be independent of the quality of their crystallinity. No strong correlation is seen between any pair of local doublet parameters but the local helical parameters are interrelated by geometric relationships. An interesting feature that emerges from this analysis is that the local rise along the z-axis is highly correlated with the difference in the buckle values of the two basepairs in the doublet, as suggested earlier for the dodecamer structures (Bansal and Bhattacharyya, in Structure & Methods: DNA & RNA, Vol. 3 (Eds., R.H. Sarma and M.H. Sarma), pp. 139-153 (1990)). In fact the local rise values become almost constant for both A- and B-forms, if a correction is applied for the buckling of the basepairs. In B-DNA the AA, AT, TA and GA basepair sequences generally have a smaller local rise (3.25 A) compared to the other sequences (3.4 A) and this seems to be an intrinsic feature of basepair stacking interaction and not related to any other local doublet parameter. The roll angles in B-DNA oligonucleotides have small values (less than +/- 8 degrees), while mean local twist varies from 24 degrees to 45 degrees. The CA/TG doublet sequences show two types of preferred geometries, one with positive roll, small positive slide and reduced twist and another with negative roll, large positive slide and increased twist.(ABSTRACT TRUNCATED AT 400 WORDS)

Is tetramethyleneethane a ground state triplet?

We have examined a number of possible ways by which tetramethyleneethane (TME) can be a ground state triplet, as claimed by experimental studies, in violation of Ovchinnikov’s theorem for alternant hydrocarbons of equal bond lengths. Model exact π calculations of the low-lying states of TME, 3,4-dimethylenefuran and 3,4-dimethylenepyrrole were carried out using a diagrammatic valence bond approach. The calculations failed to yield a triplet ground state even after (a) tuning of electron correlation, (b) breaking alternancy symmetry, and (c) allowing for geometric distortions. In contrast to earlier studies of fine structure constants in other conjugated systems, the computedD andE values of all the low-lying triplet states of TME for various geometries are at least an order of magnitude different from the experimentally reported values. Incorporation of σ-π mixing by means of UHF MNDO calculations is found to favour a singlet ground state even further. A reinterpretation of the experimental results of TME is therefore suggested to resolve the conflict.

Squeezed states, photon-number distributions, and U(l) invariance

We study the photon-number distribution in squeezed states of a single-mode radiation field. A U(l)-invariant squeezing criterion is compared and contrasted with a more restrictive criterion, with the help of suggestive geometric representations. The U(l) invariance of the photon-number distribution in a squeezed coherent state, with arbitrary complex squeeze and displacement parameters, is explicitly demonstrated. The behavior of the photon-number distribution for a representative value of the displacement and various values of the squeeze parameter is numerically investigated. A new kind of giant oscillation riding as an envelope over more rapid oscillations in this distribution is demonstrated.

Studies on a stove for powdery biomass

The sawdust stove, classically known for several decades, is considered here in a scientific study. The poor ignition characteristics and smoky start up are related to improper geometric dimensions. Based on a parametric study, the startup procedure and the dimensions of the stove were modified to achieve a smooth start up. Also, the range of acceptable fuels was enlarged to include tiny unprocessed dry twigs, weeds and wood sticks o the extent of about 50%, with the rest being sawdust-like material. The efficiency of the stove was measured to be 30–40%, depending on the relative size and shape of the vessel and the power level of the stove. A simple procedure for designing this class of stove for various power levels, as well as burning times, is presented. A new concept of multiport design is also discussed.

AB-initio study of alpha-silyl and beta-silyl substituent effects on vinyl radicals

The geometries of alpha- and beta-silyl substituted vinyl radicals and of alpha,beta-disilylvinyl radical have been optimised with the STO-3G and the STO-3G* basis sets. The relative stabilities of various conformers have been determined at the UMP2/6-31G* level. The stabilisation of vinyl radicals through alpha-silyl substitution is larger than that due to corresponding alkyl groups. The presence of an alpha-silyl group also leads to a tendency towards linearisation of the vinyl radical centre and a corresponding reduction in the inversion barrier. In marked contrast, the beta-silyl effect is negligible. The geometric, conformational and energetic consequences are insignificant. Overall, the silyl substituent effect at vinyl radicals is very different from that computed earlier for the vinyl cations, but qualitatively similar to that found in carbanions.