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.

Further development of discrete computational techniques for calculation of restricted diffusion propagators in porous media

Magnetic resonance is a well-established tool for structural characterisation of porous media. Features of pore-space morphology can be inferred from NMR diffusion-diffraction plots or the time-dependence of the apparent diffusion coefficient. Diffusion NMR signal attenuation can be computed from the restricted diffusion propagator, which describes the distribution of diffusing particles for a given starting position and diffusion time. We present two techniques for efficient evaluation of restricted diffusion propagators for use in NMR porous-media characterisation. The first is the Lattice Path Count (LPC). Its physical essence is that the restricted diffusion propagator connecting points A and B in time t is proportional to the number of distinct length-t paths from A to B. By using a discrete lattice, the number of such paths can be counted exactly. The second technique is the Markov transition matrix (MTM). The matrix represents the probabilities of jumps between every pair of lattice nodes within a single timestep. The propagator for an arbitrary diffusion time can be calculated as the appropriate matrix power. For periodic geometries, the transition matrix needs to be defined only for a single unit cell. This makes MTM ideally suited for periodic systems. Both LPC and MTM are closely related to existing computational techniques: LPC, to combinatorial techniques; and MTM, to the Fokker-Planck master equation. The relationship between LPC, MTM and other computational techniques is briefly discussed in the paper. Both LPC and MTM perform favourably compared to Monte Carlo sampling, yielding highly accurate and almost noiseless restricted diffusion propagators. Initial tests indicate that their computational performance is comparable to that of finite element methods. Both LPC and MTM can be applied to complicated pore-space geometries with no analytic solution. We discuss the new methods in the context of diffusion propagator calculation in porous materials and model biological tissues.

Least path criterion (LPC) for unique indexing in a two-dimensional decagonal quasilattice

The least path criterion or least path length in the context of redundant basis vector systems is discussed and a mathematical proof is presented of the uniqueness of indices obtained by applying the least path criterion. Though the method has greater generality, this paper concentrates on the two-dimensional decagonal lattice. The order of redundancy is also discussed; this will help eventually to correlate with other redundant but desirable indexing sets.

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.

Boosting optimum-path forest clustering through harmony Search and its applications for intrusion detection in computer networks

In this paper we propose a nature-inspired approach that can boost the Optimum-Path Forest (OPF) clustering algorithm by optimizing its parameters in a discrete lattice. The experiments in two public datasets have shown that the proposed algorithm can achieve similar parameters' values compared to the exhaustive search. Although, the proposed technique is faster than the traditional one, being interesting for intrusion detection in large scale traffic networks. © 2012 IEEE.

Space–time zero-inflated count models of Harbor seals

Environmental data are spatial, temporal, and often come with many zeros. In this paper, we included space–time random effects in zero-inflated Poisson (ZIP) and ‘hurdle’ models to investigate haulout patterns of harbor seals on glacial ice. The data consisted of counts, for 18 dates on a lattice grid of samples, of harbor seals hauled out on glacial ice in Disenchantment Bay, near Yakutat, Alaska. A hurdle model is similar to a ZIP model except it does not mix zeros from the binary and count processes. Both models can be used for zero-inflated data, and we compared space–time ZIP and hurdle models in a Bayesian hierarchical model. Space–time ZIP and hurdle models were constructed by using spatial conditional autoregressive (CAR) models and temporal first-order autoregressive (AR(1)) models as random effects in ZIP and hurdle regression models. We created maps of smoothed predictions for harbor seal counts based on ice density, other covariates, and spatio-temporal random effects. For both models predictions around the edges appeared to be positively biased. The linex loss function is an asymmetric loss function that penalizes overprediction more than underprediction, and we used it to correct for prediction bias to get the best map for space–time ZIP and hurdle models.

Lattice preferred orientation in omphacite: Examples from the Tauern Window, Austria and the Western Gneiss Region, Norway

It is lively debated how eclogites find their way from deep to mid-crustal levels during exhumation. Different exhumation models for high-pressure and ultrahigh-pressure rocks were suggested in previous studies, based mainly on field observations and less on microstructural studies on the exhumed rocks. The development and improvement of electron microscopy techniques allows it, to focus interest on direct investigations of microstructures and crystallographic properties in eclogites. In this case, it is of importance to study the applicability of crystallographic measurements on eclogites for exhumation processes and to unravel which processes affect eclogite textures. Previous studies suggested a strong relationship between deformation and lattice preferred orientation (LPO) in omphacite but it is still unclear if the deformation is related to the exhumation of eclogites. This study is focused on the questions which processes affect omphacite LPO and if textural investigations of omphacite are applicable for studying eclogite exhumation. Therefore, eclogites from two examples in the Alps and in the Caledonides were collected systematically and investigated with respect to omphacite LPO by using the electron backscattered diffraction (EBSD) technique. Omphacite textures of the Tauern Window (Austria) and the Western Gneiss Region (Norway) were studied to compare lattice preferred orientation with field observations and suggested exhumation models from previous studies. The interpretation of omphacite textures, regarding the deformation regime is mainly based on numerical simulations in previous studies. Omphacite LPO patterns of the Eclogite Zone are clearly independent from any kind of exhumation process. The textures were generated during omphacite growth on the prograde path of eclogite development until metamorphic peak conditions. Field observations in the Eclogite Zone show that kinematics in garnet mica schist, surrounding the eclogites, strongly indicate an extrusion wedge geometry. Stretching lineations show top-N thrusting at the base and a top-S normal faulting with a sinistral shear component at the top of the Eclogite Zone. The different shear sense on both sides of the unit does not affect the omphacite textures in any way. The omphacite lattice preferred orientation patterns of the Western Gneiss Region can not be connected with any exhumation model. The textures were probably generated during the metamorphic peak and reflect the change from subduction to exhumation. Eclogite Zone and Western Gneiss Region differ significantly in size and especially in metamorphic conditions. While the Eclogite Zone is characterized by constant P-T conditions (600-650°C, 20-25 kbar), the Western Gneiss Region contains a wide P-T range from high- to ultrahigh pressure conditions (400-800°C, 20-35 kbar). In contrast to this, the omphacite textures of both units are very similar. This means that omphacite LPO is independent from P-T conditions and therefore from burial depth. Further, in both units, omphacite LPO is independent from grain and subgrain size as well as from any shape preferred orientation (SPO) on grain and subgrain scale. Overall, omphacite lattice preferred orientation are generated on the prograde part of omphacite development. Therefore, textural investigations on omphacite LPO are not applicable to study eclogite exhumation.

Supersymmetric quantum mechanics on the lattice: I. Loop formulation

Simulations of supersymmetric field theories on the lattice with (spontaneously) broken supersymmetry suffer from a fermion sign problem related to the vanishing of the Witten index. We propose a novel approach which solves this problem in low dimensions by formulating the path integral on the lattice in terms of fermion loops. For N=2 supersymmetric quantum mechanics the loop formulation becomes particularly simple and in this paper – the first in a series of three – we discuss in detail the reformulation of this model in terms of fermionic and bosonic bonds for various lattice discretisations including one which is Q-exact.

Race and equity in higher education : A harder path for Indigenous academics

Our experiences as Indigenous academics within universities often reflects the experiences we have as Indigenous people in broader society, yet I am still surprised and angered when it is others working in higher education who espouse notions of justice and equity with whom we experience tension and conflict in asserting our rights, values and cultural values. At times it is a constant struggle even when universities have Reconciliation Statements as most of them do now, Indigenous recruitment or employment strategies and university wide anti-racism and anti-discrimination policies and procedures.

Computational approach to localization using global energy minimization

Damage localization induced by strain softening can be predicted by the direct minimization of a global energy function. This article concerns the computational strategy for implementing this principle for softening materials such as concrete. Instead of using heuristic global optimization techniques, our strategies are a hybrid of local optimization methods with a path-finding approach to ensure a global optimum. With admissible nodal displacements being independent variables, it is easy to deal with the geometric (mesh) constraint conditions. The direct search optimization methods recover the localized solutions for a range of softening lattice models which are representative of quasi-brittle structures

Robot path planning in dynamic environments using a simulated annealing based approach

Mobile robots are widely used in many industrial fields. Research on path planning for mobile robots is one of the most important aspects in mobile robots research. Path planning for a mobile robot is to find a collision-free route, through the robot’s environment with obstacles, from a specified start location to a desired goal destination while satisfying certain optimization criteria. Most of the existing path planning methods, such as the visibility graph, the cell decomposition, and the potential field are designed with the focus on static environments, in which there are only stationary obstacles. However, in practical systems such as Marine Science Research, Robots in Mining Industry, and RoboCup games, robots usually face dynamic environments, in which both moving and stationary obstacles exist. Because of the complexity of the dynamic environments, research on path planning in the environments with dynamic obstacles is limited. Limited numbers of papers have been published in this area in comparison with hundreds of reports on path planning in stationary environments in the open literature. Recently, a genetic algorithm based approach has been introduced to plan the optimal path for a mobile robot in a dynamic environment with moving obstacles. However, with the increase of the number of the obstacles in the environment, and the changes of the moving speed and direction of the robot and obstacles, the size of the problem to be solved increases sharply. Consequently, the performance of the genetic algorithm based approach deteriorates significantly. This motivates the research of this work. This research develops and implements a simulated annealing algorithm based approach to find the optimal path for a mobile robot in a dynamic environment with moving obstacles. The simulated annealing algorithm is an optimization algorithm similar to the genetic algorithm in principle. However, our investigation and simulations have indicated that the simulated annealing algorithm based approach is simpler and easier to implement. Its performance is also shown to be superior to that of the genetic algorithm based approach in both online and offline processing times as well as in obtaining the optimal solution for path planning of the robot in the dynamic environment. The first step of many path planning methods is to search an initial feasible path for the robot. A commonly used method for searching the initial path is to randomly pick up some vertices of the obstacles in the search space. This is time consuming in both static and dynamic path planning, and has an important impact on the efficiency of the dynamic path planning. This research proposes a heuristic method to search the feasible initial path efficiently. Then, the heuristic method is incorporated into the proposed simulated annealing algorithm based approach for dynamic robot path planning. Simulation experiments have shown that with the incorporation of the heuristic method, the developed simulated annealing algorithm based approach requires much shorter processing time to get the optimal solutions in the dynamic path planning problem. Furthermore, the quality of the solution, as characterized by the length of the planned path, is also improved with the incorporated heuristic method in the simulated annealing based approach for both online and offline path planning.