Optimal sequential wireless relay placement on a random lattice path

Our work is motivated by impromptu (or ``as-you-go'') deployment of wireless relay nodes along a path, a need that arises in many situations. In this paper, the path is modeled as starting at the origin (where there is the data sink, e.g., the control center), and evolving randomly over a lattice in the positive quadrant. A person walks along the path deploying relay nodes as he goes. At each step, the path can, randomly, either continue in the same direction or take a turn, or come to an end, at which point a data source (e.g., a sensor) has to be placed, that will send packets to the data sink. A decision has to be made at each step whether or not to place a wireless relay node. Assuming that the packet generation rate by the source is very low, and simple link-by-link scheduling, we consider the problem of sequential relay placement so as to minimize the expectation of an end-to-end cost metric (a linear combination of the sum of convex hop costs and the number of relays placed). This impromptu relay placement problem is formulated as a total cost Markov decision process. First, we derive the optimal policy in terms of an optimal placement set and show that this set is characterized by a boundary (with respect to the position of the last placed relay) beyond which it is optimal to place the next relay. Next, based on a simpler one-step-look-ahead characterization of the optimal policy, we propose an algorithm which is proved to converge to the optimal placement set in a finite number of steps and which is faster than value iteration. We show by simulations that the distance threshold based heuristic, usually assumed in the literature, is close to the optimal, provided that the threshold distance is carefully chosen. (C) 2014 Elsevier B.V. All rights reserved.

From Selective-ID to Full-ID IBS without Random Oracles

Since its induction, the selective-identity (sID) model for identity-based cryptosystems and its relationship with various other notions of security has been extensively studied. As a result, it is a general consensus that the sID model is much weaker than the full-identity (ID) model. In this paper, we study the sID model for the particular case of identity-based signatures (IBS). The main focus is on the problem of constructing an ID-secure IBS given an sID-secure IBS without using random oracles-the so-called standard model-and with reasonable security degradation. We accomplish this by devising a generic construction which uses as black-box: i) a chameleon hash function and ii) a weakly-secure public-key signature. We argue that the resulting IBS is ID-secure but with a tightness gap of O(q(s)), where q(s) is the upper bound on the number of signature queries that the adversary is allowed to make. To the best of our knowledge, this is the first attempt at such a generic construction.

Approximation of Spatio-Temporal Random Processes Using Tensor Decomposition

A new representation of spatio-temporal random processes is proposed in this work. In practical applications, such processes are used to model velocity fields, temperature distributions, response of vibrating systems, to name a few. Finding an efficient representation for any random process leads to encapsulation of information which makes it more convenient for a practical implementations, for instance, in a computational mechanics problem. For a single-parameter process such as spatial or temporal process, the eigenvalue decomposition of the covariance matrix leads to the well-known Karhunen-Loeve (KL) decomposition. However, for multiparameter processes such as a spatio-temporal process, the covariance function itself can be defined in multiple ways. Here the process is assumed to be measured at a finite set of spatial locations and a finite number of time instants. Then the spatial covariance matrix at different time instants are considered to define the covariance of the process. This set of square, symmetric, positive semi-definite matrices is then represented as a third-order tensor. A suitable decomposition of this tensor can identify the dominant components of the process, and these components are then used to define a closed-form representation of the process. The procedure is analogous to the KL decomposition for a single-parameter process, however, the decompositions and interpretations vary significantly. The tensor decompositions are successfully applied on (i) a heat conduction problem, (ii) a vibration problem, and (iii) a covariance function taken from the literature that was fitted to model a measured wind velocity data. It is observed that the proposed representation provides an efficient approximation to some processes. Furthermore, a comparison with KL decomposition showed that the proposed method is computationally cheaper than the KL, both in terms of computer memory and execution time.

A shortest path tree based algorithm for relay placement in a wireless sensor network and its performance analysis

In this paper, we study a problem of designing a multi-hop wireless network for interconnecting sensors (hereafter called source nodes) to a Base Station (BS), by deploying a minimum number of relay nodes at a subset of given potential locations, while meeting a quality of service (QoS) objective specified as a hop count bound for paths from the sources to the BS. The hop count bound suffices to ensure a certain probability of the data being delivered to the BS within a given maximum delay under a light traffic model. We observe that the problem is NP-Hard. For this problem, we propose a polynomial time approximation algorithm based on iteratively constructing shortest path trees and heuristically pruning away the relay nodes used until the hop count bound is violated. Results show that the algorithm performs efficiently in various randomly generated network scenarios; in over 90% of the tested scenarios, it gave solutions that were either optimal or were worse than optimal by just one relay. We then use random graph techniques to obtain, under a certain stochastic setting, an upper bound on the average case approximation ratio of a class of algorithms (including the proposed algorithm) for this problem as a function of the number of source nodes, and the hop count bound. To the best of our knowledge, the average case analysis is the first of its kind in the relay placement literature. Since the design is based on a light traffic model, we also provide simulation results (using models for the IEEE 802.15.4 physical layer and medium access control) to assess the traffic levels up to which the QoS objectives continue to be met. (C) 2014 Elsevier B.V. All rights reserved.

Memory-induced anomalous dynamics in a minimal random walk model

A discrete-time dynamics of a non-Markovian random walker is analyzed using a minimal model where memory of the past drives the present dynamics. In recent work N. Kumar et al., Phys. Rev. E 82, 021101 (2010)] we proposed a model that exhibits asymptotic superdiffusion, normal diffusion, and subdiffusion with the sweep of a single parameter. Here we propose an even simpler model, with minimal options for the walker: either move forward or stay at rest. We show that this model can also give rise to diffusive, subdiffusive, and superdiffusive dynamics at long times as a single parameter is varied. We show that in order to have subdiffusive dynamics, the memory of the rest states must be perfectly correlated with the present dynamics. We show explicitly that if this condition is not satisfied in a unidirectional walk, the dynamics is only either diffusive or superdiffusive (but not subdiffusive) at long times.

Growing dynamical facilitation on approaching the random pinning colloidal glass transition

Despite decades of research, it remains to be established whether the transformation of a liquid into a glass is fundamentally thermodynamic or dynamic in origin. Although observations of growing length scales are consistent with thermodynamic perspectives, the purely dynamic approach of the Dynamical Facilitation (DF) theory lacks experimental support. Further, for vitrification induced by randomly freezing a subset of particles in the liquid phase, simulations support the existence of an underlying thermodynamic phase transition, whereas the DF theory remains unexplored. Here, using video microscopy and holographic optical tweezers, we show that DF in a colloidal glass-forming liquid grows with density as well as the fraction of pinned particles. In addition, we observe that heterogeneous dynamics in the form of string-like cooperative motion emerges naturally within the framework of facilitation. Our findings suggest that a deeper understanding of the glass transition necessitates an amalgamation of existing theoretical approaches.

Random vibration testing with controlled samples

This paper proposes a novel experimental test procedure to estimate the reliability of structural dynamical systems under excitations specified via random process models. The samples of random excitations to be used in the test are modified by the addition of an artificial control force. An unbiased estimator for the reliability is derived based on measured ensemble of responses under these modified inputs based on the tenets of Girsanov transformation. The control force is selected so as to reduce the sampling variance of the estimator. The study observes that an acceptable choice for the control force can be made solely based on experimental techniques and the estimator for the reliability can be deduced without taking recourse to mathematical model for the structure under study. This permits the proposed procedure to be applied in the experimental study of time-variant reliability of complex structural systems that are difficult to model mathematically. Illustrative example consists of a multi-axes shake table study on bending-torsion coupled, geometrically non-linear, five-storey frame under uni/bi-axial, non-stationary, random base excitation. Copyright (c) 2014 John Wiley & Sons, Ltd.

Finite size scaling in crossover among different random matrix ensembles in microscopic lattice models

Using numerical diagonalization we study the crossover among different random matrix ensembles (Poissonian, Gaussian orthogonal ensemble (GOE), Gaussian unitary ensemble (GUE) and Gaussian symplectic ensemble (GSE)) realized in two different microscopic models. The specific diagnostic tool used to study the crossovers is the level spacing distribution. The first model is a one-dimensional lattice model of interacting hard-core bosons (or equivalently spin 1/2 objects) and the other a higher dimensional model of non-interacting particles with disorder and spin-orbit coupling. We find that the perturbation causing the crossover among the different ensembles scales to zero with system size as a power law with an exponent that depends on the ensembles between which the crossover takes place. This exponent is independent of microscopic details of the perturbation. We also find that the crossover from the Poissonian ensemble to the other three is dominated by the Poissonian to GOE crossover which introduces level repulsion while the crossover from GOE to GUE or GOE to GSE associated with symmetry breaking introduces a subdominant contribution. We also conjecture that the exponent is dependent on whether the system contains interactions among the elementary degrees of freedom or not and is independent of the dimensionality of the system.

BELIEF PROPAGATION FOR OPTIMAL EDGE COVER IN THE RANDOM COMPLETE GRAPH

We apply the objective method of Aldous to the problem of finding the minimum-cost edge cover of the complete graph with random independent and identically distributed edge costs. The limit, as the number of vertices goes to infinity, of the expected minimum cost for this problem is known via a combinatorial approach of Hessler and Wastlund. We provide a proof of this result using the machinery of the objective method and local weak convergence, which was used to prove the (2) limit of the random assignment problem. A proof via the objective method is useful because it provides us with more information on the nature of the edge's incident on a typical root in the minimum-cost edge cover. We further show that a belief propagation algorithm converges asymptotically to the optimal solution. This can be applied in a computational linguistics problem of semantic projection. The belief propagation algorithm yields a near optimal solution with lesser complexity than the known best algorithms designed for optimality in worst-case settings.

Influence of Spatial Variability on Pavement Responses Using Latin Hypercube Sampling on Two-Dimensional Random Fields

Although uncertainties in material properties have been addressed in the design of flexible pavements, most current modeling techniques assume that pavement layers are homogeneous. The paper addresses the influence of the spatial variability of the resilient moduli of pavement layers by evaluating the effect of the variance and correlation length on the pavement responses to loading. The integration of the spatially varying log-normal random field with the finite-difference method has been achieved through an exponential autocorrelation function. The variation in the correlation length was found to have a marginal effect on the mean values of the critical strains and a noticeable effect on the standard deviation which decreases with decreases in correlation length. This reduction in the variance arises because of the spatial averaging phenomenon over the softer and stiffer zones generated because of spatial variability. The increase in the mean value of critical strains with decreasing correlation length, although minor, illustrates that pavement performance is adversely affected by the presence of spatially varying layers. The study also confirmed that the higher the variability in the pavement layer moduli, introduced through a higher value of coefficient of variation (COV), the higher the variability in the pavement response. The study concludes that ignoring spatial variability by modeling the pavement layers as homogeneous that have very short correlation lengths can result in the underestimation of the critical strains and thus an inaccurate assessment of the pavement performance. (C) 2014 American Society of Civil Engineers.

VISUAL OBJECT TRACKING VIA RANDOM FERNS BASED CLASSIFICATION

Designing a robust algorithm for visual object tracking has been a challenging task since many years. There are trackers in the literature that are reasonably accurate for many tracking scenarios but most of them are computationally expensive. This narrows down their applicability as many tracking applications demand real time response. In this paper, we present a tracker based on random ferns. Tracking is posed as a classification problem and classification is done using ferns. We used ferns as they rely on binary features and are extremely fast at both training and classification as compared to other classification algorithms. Our experiments show that the proposed tracker performs well on some of the most challenging tracking datasets and executes much faster than one of the state-of-the-art trackers, without much difference in tracking accuracy.

Direct correlation between non-random distribution of cations and ion transport mechanism in soda-lime silicate glasses

We report a direct correlation between dissimilar ion pair formation and alkali ion transport in soda-lime silicate glasses established via broad band conductivity spectroscopy and local structural probe techniques. The combined Raman and Nuclear Magnetic Resonance (NMR) spectroscopy techniques on these glasses reveal the coexistence of different anionic species and the prevalence of Na+-Ca2+ dissimilar pairs as well as their distributions. The spectroscopic results further confirm the formation of dissimilar pairs atomistically, where it increases with increasing alkaline-earth oxide content These results, are the manifestation of local structural changes in the silicate network with composition which give rise to different environments into which the alkali ions hop. The Na+ ion mobility varies inversely with dissimilar pair formation, i.e. it decreases with increase of non-random formation of dissimilar pairs. Remarkably, we found that increased degree of non-randomness leads to temperature dependent variation in number density of sodium ions. Furthermore, the present study provides the strong link between the dynamics of the alkali ions and different sites associated with it in soda-lime silicate glasses. (C) 2014 Elsevier B.V. All rights reserved.

Matrix Crack Detection in Composite Plate with Spatially Random Material Properties using Fractal Dimension

Fractal dimension based damage detection method is investigated for a composite plate with random material properties. Composite material shows spatially varying random material properties because of complex manufacturing processes. Matrix cracks are considered as damage in the composite plate. Such cracks are often seen as the initial damage mechanism in composites under fatigue loading and also occur due to low velocity impact. Static deflection of the cantilevered composite plate with uniform loading is calculated using the finite element method. Damage detection is carried out based on sliding window fractal dimension operator using the static deflection. Two dimensional homogeneous Gaussian random field is generated using Karhunen-Loeve (KL) expansion to represent the spatial variation of composite material property. The robustness of fractal dimension based damage detection method is demonstrated considering the composite material properties as a two dimensional random field.

Matrix crack detection in spatially random composite structures using fractal dimension

Fractal dimension based damage detection method is studied for a composite structure with random material properties. A composite plate with localized matrix crack is considered. Matrix cracks are often seen as the initial damage mechanism in composites. Fractal dimension based method is applied to the static deformation curve of the structure to detect localized damage. Static deflection of a cantilevered composite plate under uniform loading is calculated using the finite element method. Composite material shows spatially varying random material properties because of complex manufacturing processes. Spatial variation of material property is represented as a two dimensional homogeneous Gaussian random field. Karhunen-Loeve (KL) expansion is used to generate a random field. The robustness of fractal dimension based damage detection methods is studied considering the composite plate with spatial variation in material properties.

Belief propagation for minimum weight many-to-one matchings in the random complete graph

In a complete bipartite graph with vertex sets of cardinalities n and n', assign random weights from exponential distribution with mean 1, independently to each edge. We show that, as n -> infinity, with n' = n/alpha] for any fixed alpha > 1, the minimum weight of many-to-one matchings converges to a constant (depending on alpha). Many-to-one matching arises as an optimization step in an algorithm for genome sequencing and as a measure of distance between finite sets. We prove that a belief propagation (BP) algorithm converges asymptotically to the optimal solution. We use the objective method of Aldous to prove our results. We build on previous works on minimum weight matching and minimum weight edge cover problems to extend the objective method and to further the applicability of belief propagation to random combinatorial optimization problems.