Tunable Locally-Optimal Geographical Forwarding in Wireless Sensor Networks with Sleep-Wake Cycling Nodes

We consider a wireless sensor network whose main function is to detect certain infrequent alarm events, and to forward alarm packets to a base station, using geographical forwarding. The nodes know their locations, and they sleep-wake cycle, waking up periodically but not synchronously. In this situation, when a node has a packet to forward to the sink, there is a trade-off between how long this node waits for a suitable neighbor to wake up and the progress the packet makes towards the sink once it is forwarded to this neighbor. Hence, in choosing a relay node, we consider the problem of minimizing average delay subject to a constraint on the average progress. By constraint relaxation, we formulate this next hop relay selection problem as a Markov decision process (MDP). The exact optimal solution (BF (Best Forward)) can be found, but is computationally intensive. Next, we consider a mathematically simplified model for which the optimal policy (SF (Simplified Forward)) turns out to be a simple one-step-look-ahead rule. Simulations show that SF is very close in performance to BF, even for reasonably small node density. We then study the end-to-end performance of SF in comparison with two extremal policies: Max Forward (MF) and First Forward (FF), and an end-to-end delay minimising policy proposed by Kim et al. 1]. We find that, with appropriate choice of one hop average progress constraint, SF can be tuned to provide a favorable trade-off between end-to-end packet delay and the number of hops in the forwarding path.

An Efficient Simulated Annealing With a Valid Solution Mechanism For TDMA Brodcast Scheduling problem

This paper presents an efficient Simulated Annealing with valid solution mechanism for finding an optimum conflict-free transmission schedule for a broadcast radio network. This is known as a Broadcast Scheduling Problem (BSP) and shown as an NP-complete problem, in earlier studies. Because of this NP-complete nature, earlier studies used genetic algorithms, mean field annealing, neural networks, factor graph and sum product algorithm, and sequential vertex coloring algorithm to obtain the solution. In our study, a valid solution mechanism is included in simulated annealing. Because of this inclusion, we are able to achieve better results even for networks with 100 nodes and 300 links. The results obtained using our methodology is compared with all the other earlier solution methods.

Entanglement and nonclassicality for multimode radiation-field states

Nonclassicality in the sense of quantum optics is a prerequisite for entanglement in multimode radiation states. In this work we bring out the possibilities of passing from the former to the latter, via action of classicality preserving systems like beam splitters, in a transparent manner. For single-mode states, a complete description of nonclassicality is available via the classical theory of moments, as a set of necessary and sufficient conditions on the photon number distribution. We show that when the mode is coupled to an ancilla in any coherent state, and the system is then acted upon by a beam splitter, these conditions turn exactly into signatures of negativity under partial transpose (NPT) entanglement of the output state. Since the classical moment problem does not generalize to two or more modes, we turn in these cases to other familiar sufficient but not necessary conditions for nonclassicality, namely the Mandel parameter criterion and its extensions. We generalize the Mandel matrix from one-mode states to the two-mode situation, leading to a natural classification of states with varying levels of nonclassicality. For two-mode states we present a single test that can, if successful, simultaneously show nonclassicality as well as NPT entanglement. We also develop a test for NPT entanglement after beam-splitter action on a nonclassical state, tracing carefully the way in which it goes beyond the Mandel nonclassicality test. The result of three-mode beam-splitter action after coupling to an ancilla in the ground state is treated in the same spirit. The concept of genuine tripartite entanglement, and scalar measures of nonclassicality at the Mandel level for two-mode systems, are discussed. Numerous examples illustrating all these concepts are presented.

Supersymmetry In The Two-Anyon Problem

We show that the problem of two anyons interacting through a simple harmonic potential or a Coulomb potential is supersymmetric. The supersymmetry operators map a theory described by statistics parameter θ to one described by π+θ. Thus fermions and bosons go into each other, while semions are supersymmetric by themselves. The simple harmonic problem has a Sp(4) symmetry for any value of θ which explains the energy degeneracies.

Transport coefficients for the shear dynamo problem at small Reynolds numbers

We build on the formulation developed in S. Sridhar and N. K. Singh J. Fluid Mech. 664, 265 (2010)] and present a theory of the shear dynamo problem for small magnetic and fluid Reynolds numbers, but for arbitrary values of the shear parameter. Specializing to the case of a mean magnetic field that is slowly varying in time, explicit expressions for the transport coefficients alpha(il) and eta(iml) are derived. We prove that when the velocity field is nonhelical, the transport coefficient alpha(il) vanishes. We then consider forced, stochastic dynamics for the incompressible velocity field at low Reynolds number. An exact, explicit solution for the velocity field is derived, and the velocity spectrum tensor is calculated in terms of the Galilean-invariant forcing statistics. We consider forcing statistics that are nonhelical, isotropic, and delta correlated in time, and specialize to the case when the mean field is a function only of the spatial coordinate X-3 and time tau; this reduction is necessary for comparison with the numerical experiments of A. Brandenburg, K. H. Radler, M. Rheinhardt, and P. J. Kapyla Astrophys. J. 676, 740 (2008)]. Explicit expressions are derived for all four components of the magnetic diffusivity tensor eta(ij) (tau). These are used to prove that the shear-current effect cannot be responsible for dynamo action at small Re and Rm, but for all values of the shear parameter.

Novel correlations in two dimensions: Two-body problem

We discuss a many-body Hamiltonian with two- and three-body interactions in two dimensions introduced recently by Murthy, Bhaduri and Sen. Apart from an analysis of some exact solutions in the many-body system, we analyse in detail the two-body problem which is completely solvable. We show that the solution of the two-body problem reduces to solving a known differential equation due to Heun. We show that the two-body spectrum becomes remarkably simple for large interaction strengths and the level structure resembles that of the Landau levels. We also clarify the 'ultraviolet' regularization which is needed to define an inverse-square potential properly and discuss its implications for our model.

On the problem of spurious patterns in neural associative memory models

The problem of spurious patterns in neural associative memory models is discussed, Some suggestions to solve this problem from the literature are reviewed and their inadequacies are pointed out, A solution based on the notion of neural self-interaction with a suitably chosen magnitude is presented for the Hebb learning rule. For an optimal learning rule based on linear programming, asymmetric dilution of synaptic connections is presented as another solution to the problem of spurious patterns, With varying percentages of asymmetric dilution it is demonstrated numerically that this optimal learning rule leads to near total suppression of spurious patterns. For practical usage of neural associative memory networks a combination of the two solutions with the optimal learning rule is recommended to be the best proposition.

Mean first passage time approach to the problem of optimal barrier subdivision for Kramer's escape rate

We consider the effect of subdividing the potential barrier along the reaction coordinate on Kramer's escape rate for a model potential, Using the known supersymmetric potential approach, we show the existence of an optimal number of subdivisions that maximizes the rate, We cast the problem as a mean first passage time problem of a biased random walker and obtain equivalent results, We briefly summarize the results of our investigation on the increase in the escape rate by placing a blow-torch in the unstable part of one of the potential wells. (C) 1999 Elsevier Science B.V. All rights reserved.

An inverse problem for the Helmholtz equation involving two semi-infinite fluids

An analytical method is developed for solving an inverse problem for Helmholtz's equation associated with two semi-infinite incompressible fluids of different variable refractive indices, separated by a plane interface. The unknowns of the inverse problem are: (i) the refractive indices of the two fluids, (ii) the ratio of the densities of the two fluids, and (iii) the strength of an acoustic source assumed to be situated at the interface of the two fluids. These are determined from the pressure on the interface produced by the acoustic source. The effect of the surface tension force at the interface is taken into account in this paper. The application of the proposed analytical method to solve the inverse problem is also illustrated with several examples. In particular, exact solutions of two direct problems are first derived using standard classical methods which are then used in our proposed inverse method to recover the unknowns of the corresponding inverse problems. The results are found to be in excellent agreement.

Video coding mode decision as a classification problem

In this paper, we show that it is possible to reduce the complexity of Intra MB coding in H.264/AVC based on a novel chance constrained classifier. Using the pairs of simple mean-variances values, our technique is able to reduce the complexity of Intra MB coding process with a negligible loss in PSNR. We present an alternate approach to address the classification problem which is equivalent to machine learning. Implementation results show that the proposed method reduces encoding time to about 20% of the reference implementation with average loss of 0.05 dB in PSNR.

Scheduling expression trees for delayed-load architectures

In this paper we consider the problem of scheduling expression trees on delayed-load architectures. The problem tackled here takes root from the one considered in [Proceedings of the ACM SIGPLAN '91 Conf. on Programming Language Design and Implementation, 1991. p. 256] in which the leaves of the expression trees all refer to memory locations. A generalization of this involves the situation in which the trees may contain register variables, with the registers being used only at the leaves. Solutions to this generalization are given in [ACM Trans. Prog. Lang. Syst. 17 (1995) 740, Microproc. Microprog. 40 (1994) 577]. This paper considers the most general case in which the registers are reusable. This problem is tackled in [Comput. Lang, 21 (1995) 49] which gives an approximate solution to the problem under certain assumptions about the contiguity of the evaluation order: Here we propose an optimal solution (which may involve even a non-contiguous evaluation of the tree). The schedule generated by the algorithm given in this paper is optimal in the sense that it is an interlock-free schedule which uses the minimum number of registers required. An extension to the algorithm incorporates spilling. The problem as stated in this paper is an instruction scheduling problem. However, the problem could also be rephrased as an operations research problem with a difference in terminology. (C) 2002 Elsevier Science B.V. All rights reserved.

The restriction mapping problem revisited

In computational molecular biology, the aim of restriction mapping is to locate the restriction sites of a given enzyme on a DNA molecule. Double digest and partial digest are two well-studied techniques for restriction mapping. While double digest is NP-complete, there is no known polynomial-time algorithm for partial digest. Another disadvantage of the above techniques is that there can be multiple solutions for reconstruction. In this paper, we study a simple technique called labeled partial digest for restriction mapping. We give a fast polynomial time (O(n(2) log n) worst-case) algorithm for finding all the n sites of a DNA molecule using this technique. An important advantage of the algorithm is the unique reconstruction of the DNA molecule from the digest. The technique is also robust in handling errors in fragment lengths which arises in the laboratory. We give a robust O(n(4)) worst-case algorithm that can provably tolerate an absolute error of O(Delta/n) (where Delta is the minimum inter-site distance), while giving a unique reconstruction. We test our theoretical results by simulating the performance of the algorithm on a real DNA molecule. Motivated by the similarity to the labeled partial digest problem, we address a related problem of interest-the de novo peptide sequencing problem (ACM-SIAM Symposium on Discrete Algorithms (SODA), 2000, pp. 389-398), which arises in the reconstruction of the peptide sequence of a protein molecule. We give a simple and efficient algorithm for the problem without using dynamic programming. The algorithm runs in time O(k log k), where k is the number of ions and is an improvement over the algorithm in Chen et al. (C) 2002 Elsevier Science (USA). All rights reserved.

A waveguide problem involving a thick iris in the theory of electromagnetism

The problem of electromagnetic wave propagation in a rectangular waveguide containing a thick iris is considered for its complete solution by reducing it to two suitable integral equations, one of which is of the first kind and the other is of the second kind. These integral equations are solved approximately, by using truncated Fourier series for the unknown functions. The reflection coefficient is computed numerically from the two integral equation approaches, and almost the same numerical results are obtained. This is also depicted graphically against the wave number and compared with thin iris results, which are computed by using complementary formulations coupled with Galerkin approximations. While the reflection coefficient for a thin iris steadily increases with the wave number, for a thick iris it fluctuates and zero reflection occurs. The number of zeros of the reflection coefficient for a thick iris increases with the thickness. Thus a thick iris becomes completely transparent for some discrete wave numbers. This phenomenon may be significant in the modelling of rectangular waveguides.