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.

Lesser auger beetle Heterobostrychus aequalis(Coleoptera: Bostrichidae) in Australia: absent or elusive?

The lesser auger beetle, Heterobostrychus aequalis (Waterhouse), is a serious pest of seasoned hardwood timber throughout the Oriental region and several areas beyond. Some early collection records of H. aequalis from Australia in the 1950s and 1960s indicated that the insect was present in northern Queensland, but no confirmed breeding population has been found in the past few decades suggesting either that it may have not established permanently or it is difficult to detect. The ambiguity about the breeding status of the pest in Australia has caused confusion for regulating authorities needing to respond to each new post-border detection. We examined records of H. aequalis in Australian insect collections and from intensive plant pest surveillance activities in Queensland and northern Australia over the past 48 years to resolve this confusion. Until very recently, available evidence suggested that H. aequalis was not established in Australia, despite multiple introductions and apparently suitable climate and hosts. Collection records of the pest are predominantly linked to intercepted items or are recorded as of unknown origin, and no established populations have been found during many years of targeted surveillance. However, a detection of H. aequalis in suburban Cairns, north Queensland, in late 2013 and two more in mid-2015 in the same general locality do not appear to be linked to any imported material, indicating that there is at least a tenuously established local population. Investigations are underway to confirm this, but the insect is not widely established in Australia and, if present, remains elusive. Our recommended response to any future detection of H. aequalis is to fumigate or destroy the infested material, conduct tracing enquiries and limit surveys to the immediate vicinity of the detection.

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.

EU Multi-level Governance in the Making - The Community Initiative LEADER+ in Finland and Germany

In order to fully understand the process of European integration it is of paramount importance to consider developments at the sub-national and local level. EU integration scholars shifted their attention to the local level only at the beginning of the 1990s with the concept of multi-level governance (MLG). While MLG is the first concept to scrutinise the position of local levels of public administration and other actors within the EU polity, I perceive it as too optimistic in the degree of influence it ascribes to local levels. Thus, learning from and combining MLG with other concepts, such as structural constructivism, helps to reveal some of the hidden aspects of EU integration and paint a more realistic picture of multi-level interaction. This thesis also answers the call for more case studies in order to conceptualise MLG further. After a critical study of theories and concepts of European integration, above all, MLG, I will analyse sub-national and local government in Finland and Germany. I show how the sub-national level and local governments are embedded in the EU s multi-level structure of governance and how, through EU integration, those levels have been empowered but also how their scope of action has partially decreased. After theoretical and institutional contextualisation, I present the results of my empirical study of the EU s Community Initiative LEADER+. LEADER stands for Liaison Entre Actions de Développement de l'Économie Rurale , and aims at improving the economic conditions in Europe s rural areas. I was interested in how different actors construct and shape EU financed rural development, especially in how local actors organised in so-called local action groups (LAGs) cooperate with other administrative units within the LEADER+ administrative chain. I also examined intra-institutional relations within those groups, in order to find out who are the most influential and powerful actors within them. Empirical data on the Finnish and German LAGs was first gathered through a survey, which was then supplemented and completed by interviewing LAG members, LAG-managers, several civil servants from Finnish and German decision-making and managing authorities and a civil servant from the EU Commission. My main argument is that in both Germany and Finland, the Community Initiative LEADER+ offered a space for multi-level interaction and local-level involvement, a space that on the one hand consists of highly motivated people actively contributing to the improvement of the quality of life and economy in Europe s countryside but which is dependent and also restricted by national administrative practices, implementation approaches and cultures on the other. In Finland, the principle of tri-partition (kolmikantaperiaatte) in organising the executive committees of LAGs is very noticeable. In comparison to Germany, for instance, the representation of public administration in those committees is much more limited due to this principle. Furthermore, the mobilisation of local residents and the bringing together of actors from the local area with different social and institutional backgrounds to become an active part of LEADER+ was more successful in Finland than in Germany. Tri-partition as applied in Finland should serve as a model for similar policies in other EU member states. EU integration changed the formal and informal inter-institutional relations linking the different levels of government. The third sector including non-governmental institutions and interest groups gained access to policy-making processes and increasingly interact with government institutions at all levels of public administration. These developments do not necessarily result in the empowering of the local level.

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.