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.

A Modified Dubins Method for Optimal Path Planning of a Miniature Air Vehicle Converging to a Straight Line Path

This paper presents a Dubins model based strategy to determine the optimal path of a Miniature Air Vehicle (MAV), constrained by a bounded turning rate, that would enable it to fly along a given straight line, starting from an arbitrary initial position and orientation. The method is then extended to meet the same objective in the presence of wind which has a magnitude comparable to the speed of the MAV. We use a modification of the Dubins' path method to obtain the complete optimal solution to this problem in all its generality.

Autonomous Line Scanning for SPC Telephone Switching Systems

An Autonomous Line Scanning Unit (ALSU) for completely autonomous detection of call originations in the SPC Telephone Switching System is described. Through its own memories, ALSU maintains an up-to-date record of subscribers' statuses, detects call originations, performs 'hit timing check' and informs the Switching System of the identity of calling subscribers. The ALSU needs minimum interaction with the Central Processor, resulting in increased call handling capacity

On the elimination of DC in reconstructed wavefronts from in-line holograms

New experimental results to demonstrate that the annoying DC in the reconstructed wavefronts from in-line holograms could be successfully eliminated are presented in this paper. The complete elimination of DC has been achieved by making proper use of a Mach-Zehnder interferometer. The results for an in-line hololens and an in-line Fourier transform hologram are discussed.

Kinetic characterization of rat brain type IIA sodium channel alpha-subunit stably expressed in a somatic cell line

1. The rat brain type IIA Na+ channel alpha-subunit was stably expressed in Chinese hamster ovary (CHO) cells. Current through the expressed Na+ channels was studied using the whole-cell configuration of the patch clamp technique. The transient Na+ current was sensitive to TTX and showed a bell-shaped peak current vs. membrane potential relation. 2. Na+ current inactivation was better described by the sum of two exponentials in the potential range -30 to +40 mV, with. a dominating fast component and a small slower component. 3. The steady-state inactivation, h(infinity), was related to potential by a Boltzmann distribution, underlying thr ee states of the inactivation gate. 4. Recovery of the channels from inactivation at different potentials in the range -70 to -120 mV were characterized by al? initial delay which decreased with hyperpolarization. The time course was well fitted by the sum of two exponentials. In this case the slower exponential was the major component, and both time constants decreased with hyperpolarization. 5. For a working description of the Na+ channel inactivation in this preparation, with a minimal deviation from the Hodgkin-Huxley model, a three-state scheme of the form O reversible arrow I-1 reversible arrow I-2 was proposed, replacing the original two-state scheme of the Hodgkin-Huxley model, and the rate constants are reported. 6. The instantaneous current-voltage relationship showed marked deviation from linearity and was satisfactorily fitted by the constant-field equation. 7. The time course of activation was described by an m(x) model. However, the best-fitted value of x varied with the membrane potential and had a mean value of 2. 8. Effective gating charge was determined to be 4.7e from the slope of the activation plot, plotted on a logarithmic scale. 9. The rate constants of activation, alpha(m) and beta(m), were determined. Their functional dependence on the membrane potential was investigated.

The line transect method for estimating densities of large mammals in a tropical deciduous forest: An evaluation of models and field experiments

We have evaluated techniques of estimating animal density through direct counts using line transects during 1988-92 in the tropical deciduous forests of Mudumalai Sanctuary in southern India for four species of large herbivorous mammals, namely, chital (Axis axis), sambar (Cervus unicolor), Asian elephant (Elephas maximus) and gaur (Bos gauras). Density estimates derived from the Fourier Series and the Half-Normal models consistently had the lowest coefficient of variation. These two models also generated similar mean density estimates. For the Fourier Series estimator, appropriate cut-off widths for analysing line transect data for the four species are suggested. Grouping data into various distance classes did not produce any appreciable differences in estimates of mean density or their variances, although model fit is generally better when data are placed in fewer groups. The sampling effort needed to achieve a desired precision (coefficient of variation) in the density estimate is derived. A sampling effort of 800 km of transects returned a 10% coefficient of variation on estimate for chital; for the other species a higher effort was needed to achieve this level of precision. There was no statistically significant relationship between detectability of a group and the size of the group for any species. Density estimates along roads were generally significantly different from those in the interior af the forest, indicating that road-side counts may not be appropriate for most species.

Thermo-mechanical characterization of surface-micromachined microheaters using in-line digital holography

This paper describes the application of lensless in-line digital holographic microscopy (DHM) to carry out thermo-mechanical characterization of microheaters fabricated through PolyMUMPs three-layer polysilicon surface micromachining process and subjected to a high thermal load. The mechanical deformation of the microheaters on the electrothermal excitation due to thermal stress is analyzed. The numerically reconstructed holographic images of the microheaters clearly indicate the regions under high stress. A double-exposure method has been used to obtain the quantitative measurements of the deformations, from the phase analysis of the hologram fringes. The measured deformations correlate well with the theoretical values predicted by a thermo-mechanical analytical model. The results show that lensless in-line DHM with Fourier analysis is an effective method for evaluating the thermo-mechanical characteristics of MEMS components.

On-line Dynamic Security Assessment: Determination of Critical Transmission Lines

The main objective of on-line dynamic security assessment is to take preventive action if required or decide remedial action if a contingency actually occurs. Stability limits are obtained for different contingencies. The mode of instability is one of the outputs of dynamic security analysis. When a power system becomes unstable, it splits initially into two groups of generators, and there is a unique cutset in the transmission network known as critical cutset across which the angles become unbounded. The knowledge of critical cutset is additional information obtained from dynamic security assessment, which can be used for initiating preventive control actions, deciding emergency control actions, and adaptive out-of-step relaying. In this article, an analytical technique for the fast prediction of the critical cutset by system simulation for a short duration is presented. Case studies on the New England ten-generator system are presented. The article also suggests the applications of the identification of critical cutsets.

Acyclic edge coloring of subcubic graphs

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and it is denoted by a′(G). From a result of Burnstein it follows that all subcubic graphs are acyclically edge colorable using five colors. This result is tight since there are 3-regular graphs which require five colors. In this paper we prove that any non-regular connected graph of maximum degree 3 is acyclically edge colorable using at most four colors. This result is tight since all edge maximal non-regular connected graphs of maximum degree 3 require four colors.

A note on the Hadwiger number of circular arc graphs

The intention of this note is to motivate the researchers to study Hadwiger's conjecture for circular arc graphs. Let η(G) denote the largest clique minor of a graph G, and let χ(G) denote its chromatic number. Hadwiger's conjecture states that η(G)greater-or-equal, slantedχ(G) and is one of the most important and difficult open problems in graph theory. From the point of view of researchers who are sceptical of the validity of the conjecture, it is interesting to study the conjecture for graph classes where η(G) is guaranteed not to grow too fast with respect to χ(G), since such classes of graphs are indeed a reasonable place to look for possible counterexamples. We show that in any circular arc graph G, η(G)less-than-or-equals, slant2χ(G)−1, and there is a family with equality. So, it makes sense to study Hadwiger's conjecture for this family.

Promotion of a cancer-like phenotype, through chronic exposure to inflammatory cytokines and hypoxia in a bronchial epithelial cell line model

Globally, lung cancer accounts for approximately 20% of all cancer related deaths. Five-year survival is poor and rates have remained unchanged for the past four decades. There is an urgent need to identify markers of lung carcinogenesis and new targets for therapy. Given the recent successes of immune modulators in cancer therapy and the improved understanding of immune evasion by tumours, we sought to determine the carcinogenic impact of chronic TNF-α and IL-1β exposure in a normal bronchial epithelial cell line model. Following three months of culture in a chronic inflammatory environment under conditions of normoxia and hypoxia (0.5% oxygen), normal cells developed a number of key genotypic and phenotypic alterations. Important cellular features such as the proliferative, adhesive and invasive capacity of the normal cells were significantly amplified. In addition, gene expression profiles were altered in pathways associated with apoptosis, angiogenesis and invasion. The data generated in this study provides support that TNF-α, IL-1β and hypoxia promotes a neoplastic phenotype in normal bronchial epithelial cells. In turn these mediators may be of benefit for biomarker and/or immune-therapy target studies. This project provides an important inflammatory in vitro model for further immuno-oncology studies in the lung cancer setting.

d-Regular Graphs of Acyclic Chromatic Index at Least d+2

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a'(G). It was conjectured by Alon, Suclakov and Zaks (and earlier by Fiamcik) that a'(G) <= Delta+2, where Delta = Delta(G) denotes the maximum degree of the graph. Alon et al. also raised the question whether the complete graphs of even order are the only regular graphs which require Delta+2 colors to be acyclically edge colored. In this article, using a simple counting argument we observe not only that this is not true, but in fact all d-regular graphs with 2n vertices and d>n, requires at least d+2 colors. We also show that a'(K-n,K-n) >= n+2, when n is odd using a more non-trivial argument. (Here K-n,K-n denotes the complete bipartite graph with n vertices on each side.) This lower bound for Kn,n can be shown to be tight for some families of complete bipartite graphs and for small values of n. We also infer that for every d, n such that d >= 5, n >= 2d+3 and dn even, there exist d-regular graphs which require at least d+2-colors to be acyclically edge colored. (C) 2009 Wiley Periodicals, Inc. J Graph Theory 63: 226-230, 2010.

Line removal and restoration of handwritten strokes

In document images, we often find printed lines over-lapping with hand written elements especially in case of signatures. Typical examples of such images are bank cheques and payment slips. Although the detection and removal of the horizontal lines has been addressed, the restoration of the handwritten area after removal of lines, persists to be a problem of interest. lit this paper, we propose a method for line removal and restoration of the erased areas of the handwritten elements. Subjective evaluation of the results have been conducted to analyze the effectiveness of the proposed method. The results are promising with an accuracy of 86.33%. The entire Process takes less than half a second for completion on a 2.4 GHz 512 MB RAM Pentium IV PC for a document image.