Optimisation Problems in Wireless Sensor Networks : Local Algorithms and Local Graphs

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.

Development of a transient gradient enhanced non local continuum damage mechanics model for masonry

Due to the advent of varied types of masonry systems a comprehensive failure mechanism of masonry essential for the understanding of its behaviour is impossible to be determined from experimental testing. As masonry is predominantly used in wall structures a biaxial stress state dominates its failure mechanism. Biaxial testing will therefore be necessary for each type of masonry, which is expensive and time consuming. A computational method would be advantageous; however masonry is complex to model which requires advanced computational modelling methods. This thesis has formulated a damage mechanics inspired modelling method and has shown that the method effectively determines the failure mechanisms and deformation characteristics of masonry under biaxial states of loading.

Inhibition of Human Two-Pore Domain K+ Channel TREK1 by Local Anesthetic Lidocaine: Negative Cooperativity and Half-of-Sites Saturation Kinetics

TWIK-related K+ channel TREK1, a background leak K+ channel, has been strongly implicated as the target of several general and local anesthetics. Here, using the whole-cell and single-channel patch-clamp technique, we investigated the effect of lidocaine, a local anesthetic, on the human (h) TREK1 channel heterologously expressed in human embryonic kidney 293 cells by an adenoviral-mediated expression system. Lidocaine, at clinical concentrations, produced reversible, concentration-dependent inhibition of hTREK1 current, with IC50 value of 180 mu M, by reducing the single-channel open probability and stabilizing the closed state. We have identified a strategically placed unique aromatic couplet (Tyr352 and Phe355) in the vicinity of the protein kinase A phosphorylation site, Ser348, in the C-terminal domain (CTD) of hTREK1, that is critical for the action of lidocaine. Furthermore, the phosphorylation state of Ser348 was found to have a regulatory role in lidocaine-mediated inhibition of hTREK1. It is interesting that we observed strong intersubunit negative cooperativity (Hill coefficient = 0.49) and half-of-sites saturation binding stoichiometry (half-reaction order) for the binding of lidocaine to hTREK1. Studies with the heterodimer of wild-type (wt)-hTREK1 and Delta 119 C-terminal deletion mutant (hTREK1(wt)-Delta 119) revealed that single CTD of hTREK1 was capable of mediating partial inhibition by lidocaine, but complete inhibition necessitates the cooperative interaction between both the CTDs upon binding of lidocaine. Based on our observations, we propose a model that explains the unique kinetics and provides a plausible paradigm for the inhibitory action of lidocaine on hTREK1.

Chapter 1: Precarious creativity: Global media, local labor

In most parts of the world, screen media workers—actors, directors, gaffers, and makeup artists—consider Hollywood to be glamorous and aspirational. If given the opportunity to work on a major studio lot, many would make the move, believing the standards of professionalism are high and the history of accomplishment is renowned. Moreover, as a global leader, Hollywood offers the chance to rub shoulders with talented counterparts and network with an elite labor force that earns top-tier pay and benefits. Yet despite this reputation, veterans say the view from inside isn’t so rosy, that working conditions have been deteriorating since the 1990s if not earlier. This grim outlook is supported by industry statistics that show the number of good jobs has been shrinking as studios outsource production to Atlanta, London, and Budapest, among others...

On the computation of two-dimensional compressible flow fields by the modified local stability scheme

The modified local stability scheme is applied to several two-dimensional problems—blunt body flow, regular reflection of a shock and lambda shock. The resolution of the flow features obtained by the modified local stability scheme is found to be better than that achieved by the other first order schemes and almost identical to that achieved by the second order schemes incorporating artificial viscosity. The scheme is easy for coding, consumes moderate amount of computer storage and time. The scheme can be advantageously used in place of second order schemes.

Characterization of a local isolate of Bombyx mori nuclear polyhedrosis virus

Polyhedral bodies of Bombyx mori nuclear polyhedrosis virus, BmNPV (BGL) isolated from infected silkworms around Bangalore were propagated either in the cultured B. mori cell line, BmN or through infection of larvae. Electron microscopic (EM) observations of the polyhedra revealed an average length of 2 mu m and a height of 0.5 mu m. The purified polyhedra derived virions (PDV) showed several bands in sucrose gradient centrifugation, indicating the multiple nucleocapsid nature of BmNPV. Electron microscopic studies of PDV revealed a cylindrical, rod-shaped nucleocapsid with an average length of 300 nm and a diameter of 35 nm. The genomic DNA from the PDV was characterized by extensive restriction analysis and the genome size was estimated to be 132 kb. The restriction pattern of BmNPV (BGL) resembled that of the prototype strain BmNPV-T3. Distinct differences due to polymorphic sites for restriction enzyme HindIII were apparent between BmNPV (BGL) and the virus isolated from a different part of Karnataka (Dharwad area), BmNPV (DHR).

A combination of local inflammation and central memory T cells potentiates immunotherapy in the skin

Adoptive T cell therapy uses the specificity of the adaptive immune system to target cancer and virally infected cells. Yet the mechanism and means by which to enhance T cell function are incompletely described, especially in the skin. In this study, we use a murine model of immunotherapy to optimize cell-mediated immunity in the skin. We show that in vitro - derived central but not effector memory-like T cells bring about rapid regression of skin-expressing cognate Ag as a transgene in keratinocytes. Local inflammation induced by the TLR7 receptor agonist imiquimod subtly yet reproducibly decreases time to skin graft rejection elicited by central but not effector memory T cells in an immunodeficient mouse model. Local CCL4, a chemokine liberated by TLR7 agonism, similarly enhances central memory T cell function. In this model, IL-2 facilitates the development in vivo of effector function from central memory but not effector memory T cells. In a model of T cell tolerogenesis, we further show that adoptively transferred central but not effector memory T cells can give rise to successful cutaneous immunity, which is dependent on a local inflammatory cue in the target tissue at the time of adoptive T cell transfer. Thus, adoptive T cell therapy efficacy can be enhanced if CD8+ T cells with a central memory T cell phenotype are transferred, and IL-2 is present with contemporaneous local inflammation. Copyright © 2012 by The American Association of Immunologists, Inc.

Beyond fractional derivatives: local approximation of other convolution integrals

Dynamic systems involving convolution integrals with decaying kernels, of which fractionally damped systems form a special case, are non-local in time and hence infinite dimensional. Straightforward numerical solution of such systems up to time t needs O(t(2)) computations owing to the repeated evaluation of integrals over intervals that grow like t. Finite-dimensional and local approximations are thus desirable. We present here an approximation method which first rewrites the evolution equation as a coupled in finite-dimensional system with no convolution, and then uses Galerkin approximation with finite elements to obtain linear, finite-dimensional, constant coefficient approximations for the convolution. This paper is a broad generalization, based on a new insight, of our prior work with fractional order derivatives (Singh & Chatterjee 2006 Nonlinear Dyn. 45, 183-206). In particular, the decaying kernels we can address are now generalized to the Laplace transforms of known functions; of these, the power law kernel of fractional order differentiation is a special case. The approximation can be refined easily. The local nature of the approximation allows numerical solution up to time t with O(t) computations. Examples with several different kernels show excellent performance. A key feature of our approach is that the dynamic system in which the convolution integral appears is itself approximated using another system, as distinct from numerically approximating just the solution for the given initial values; this allows non-standard uses of the approximation, e. g. in stability analyses.

Inter-helical Interactions in Membrane Proteins: Analysis Based on the Local Backbone Geometry and the Side Chain Interactions

The availability of a significant number of the Structures of helical membrane proteins has prompted us to investigate the mode of helix-helix packing. In the present study, we have considered a dataset of alpha-helical membrane proteins representing Structures solved from all the known superfamilies. We have described the geometry of all the helical residues in terms of local coordinate axis at the backbone level. Significant inter-helical interactions have been considered as contacts by weighing the number of atom-atom contacts, including all the side-chain atoms. Such a definition of local axis and the contact criterion has allowed us to investigate the inter-helical interaction in a systematic and quantitative manner. We show that a single parameter (designated as alpha), which is derived from the parameters representing the Mutual orientation of local axes, is able to accurately Capture the details of helix-helix interaction. The analysis has been carried Out by dividing the dataset into parallel, anti-parallel, and perpendicular orientation of helices. The study indicates that a specific range of alpha value is preferred for interactions among the anti-parallel helices. Such a preference is also seen among interacting residues of parallel helices, however to a lesser extent. No such preference is seen in the case of perpendicular helices, the contacts that arise mainly due to the interaction Of Surface helices with the end of the trans-membrane helices. The Study Supports the prevailing view that the anti-parallel helices are well packed. However, the interactions between helices of parallel orientation are non-trivial. The packing in alpha-helical membrane proteins, which is systematically and rigorously investigated in this study, may prove to be useful in modeling of helical membrane proteins.

Bounding Run-Times of Local Adiabatic Algorithms

A common trick for designing faster quantum adiabatic algorithms is to apply the adiabaticity condition locally at every instant. However it is often difficult to determine the instantaneous gap between the lowest two eigenvalues, which is an essential ingredient in the adiabaticity condition. In this paper we present a simple linear algebraic technique for obtaining a lower bound on the instantaneous gap even in such a situation. As an illustration, we investigate the adiabatic un-ordered search of van Dam et al. [17] and Roland and Cerf [15] when the non-zero entries of the diagonal final Hamiltonian are perturbed by a polynomial (in log N, where N is the length of the unordered list) amount. We use our technique to derive a bound on the running time of a local adiabatic schedule in terms of the minimum gap between the lowest two eigenvalues.