Wireless sensor networks (WSN) are inherently multi - constrained. They need to preserve energy while offering reliable and timely data reporting for a non-negligible number of scenarios. This is particularly true when a node should decide which forwarder has to be chosen for routing a packet. Nevertheless, solving multi-constrained routing problems is NP-complete. Most approaches involve transforming the problem into a single constrained problem using a cost function, although this may lead to suboptimal solutions. Some other solutions are based on heuristics. However, their high implementation complexity prevents their online use. Hence, they are not suitable for highly dynamic WSNs. In this paper we make use of Operator Calculus (OC) methods on graphs to solve path selection in the presence of multiple constraints. OC has lower resolution time complexity compared to other techniques. Based on OC, we develop a distributed algorithm for path selection in a graph. We develop a new routing protocol which makes use of this algorithm: the Operator Calculus based Routing Protocol (OCRP). In OCRP, a node selects the set of eligible next hops based on the given constraints and the distance to the destination. It then sends the packet to all eligible next hops. The protocol is implemented in Contiki OS and emulated for TelosB motes using Cooja. We compare its performance against tree and directional flooding routing and show the advantages of our technique.

An innovative minimal paths algorithm based on operator calculus in graded semigroup algebras is described. Classical approaches to routing problems invariably require construction of trees and the use of heuristics to prevent combinatorial explosion. The operator calculus approach presented herein, however, allows such explicit tree constructions to be avoided. Moreover, the implicit tree structures underlying the problem are pruned automatically by the inherent properties of the semigroup algebras used in this approach. The operator calculus algorithm proposed here is applied to the problem of precomputed routing in a store-and-forward (S&F) satellite constellation, which provides message communication services by relaying messages between satellites through gateways on the ground. The minimum end-to-end delay paths obtained are compared with the best existing heuristics-based results. The best existing results were obtained from a greedy algorithm designed to explore only a portion of the solution space in order to avoid combinatorial explosion and memory overload. In all test cases, the operator calculus is shown to return paths whose minimum end-to-end delay is either equal to or less than that of the best existing result. In some cases, in which the tree pruning algorithm did not find a solution, the operator calculus does. These results correspond to a one-single constraint case considering the end-to-end delay as the cost of the links, if the case of multi constraints is considered (e.g. bandwidth, rapidity,...) the operator calculus approach can be similarly used.

When a local optimal solution is reached with classical Particle Swarm Optimization (PSO), all particles in the swarm gather around it, and escaping from this local optima becomes difficult. To avoid premature convergence of PSO, we present in this paper a novel variant of PSO algorithm, called MPSOM, that uses Metropolis equation to update local best solutions (lbest) of each particle and uses mutation operator to escape from local optima. The proposed MPSOM algorithm is validated on seven standard benchmark functions and used to solve the problem of reducing memory energy consumption in embedded systems (Scratch-Pad Memories SPMs). The numerical results show that our approach outperforms several recently published algorithms.

The deployment strategy for achieving differentiated coverage and probabilistic connectivity in wireless sensor networks is studied in this paper. A novel solution based on elitist non-dominated sorting genetic algorithm (NSGA-II) is proposed. Simulation results show that NSGA-II based strategy can meet the desired coverage requirements and maintain connectivity in a probabilistic manner with a relatively small number of sensors. In addition, for the applications in which the coverage requirement varies in some subareas, a local genetic operation is more time efficient and needs less variation in the original disposal than a renewed global optimization.

We propose a novel algorithm called GA-MDP for solving the frequency assignment problem. GA-MDP inherits the spirit of genetic algorithms with an adaptation of Markov decision processes (MDPs). More precisely policy iteration (PI) and value iteration (VI) are used as mutation operators. Experimental results show that for our application, GA-MDP that uses PI as a mutation operator improves the quality and time performances of the hybrid algorithms and hybrid MDP designed previously by the authors for solving the same problem

This paper presents a new hybrid genetic algorithm used to solve a frequency assignment problem. The hybrid genetic algorithm presented in this paper uses two original mutation operators. The first mutation operator is based on a greedy algorithm and the second one on an original probabilistic tabu search. The results obtained by our algorithm are better than the best known results obtained by other methods like tabu search and hybrid genetic algorithm. Our results are validated in the field of radiobroadcasting and compared to the best existing solutions in this domain.

Markov decision processes have been successfully used in robotics for indoor robot navigation problems. They allow the computation of optimal sequences of actions in order to achieve a given goal, accounting for actuator uncertainties. However, MDPs are unsatisfactory at avoiding unknown obstacles. On the other hand, reactive navigators are particularly adapted to that, and don't need any prior knowledge about the environment, but they are unable to plan the set of actions that will permit the realization of a given mission. We present a new state aggregation technique for Markov decision processes, such that part of the work usually dedicated to the planner is achieved by a reactive navigator. Thus some characteristics of our environments, such as the width of corridors, have not been considered, which allows to cluster states together, significantly reducing the state space. As a consequence, policies are computed faster and are shown to be at least as efficient as optimal ones.

Given a set of n elements each of which is either red or blue, it is known that in the worst case $n-\nu(n)$ pairwise equal/not equal color comparisons are necessary and sufficient to determine the majority color, where $\nu(n)$ is the number of 1-bits in the binary representation of n. We prove that $\frac{2n}{3} - \sqrt\frac{8n}{9\pi} + O(\log n)$ such comparisons are necessary and sufficient in the average case.

The purpose of this paper is to analyze the maxima properties (value and position) of some data structures. Our theorems concern the distribution of these random variables. Previously known results usually dealt with the mean and sometimes the variance of the random variables. Many of our results rely on diffusion techniques. This is a very powerful tool that has already been used with some success in algorithm complexity analysis.

Bounds are obtained for the solution to the divide-and-conquer recurrence \[ M( n ) = \max \limits_{k_1 + \cdots + k_p = n} ( M( k_1 ) + M( k_2 ) + \cdots + M( k_p )+ \min ( f ( k_1 ), \cdots ,f ( k_p ) ) ), \] for nondecreasing functions f. Similar bounds are found for the recurrence with “min” replaced by “sum-of-all-but-the-max.” Such recurrences appear in the analysis of various algorithms. The bounds follow from analyses of partition trees.

A mobile robot needs to represent and to reason about the approximate relationships between itself and other objects. In addition, the robot must be able to use sensor information to reduce locational uncertainty. In this paper we present a general probabilistic model which permits to represent the motions of 2-D or 3-D mobile robots and to estimate the distribution of a chain of relative transforms without strong assumptions.