Ghaleb-Seddik A.,National School of Computer Science for Industry and Business |
Ghamri-Doudane Y.,University of Burgundy
Journal of Communications | Year: 2012
Most existing TCP variants cannot distinguish between different packet loss causes within MANETs. TCP was, mainly, developed to deal with network congestion errors. While within MANETs, there are packet loss causes other than congestion. Studying the behaviour of TCP in front of such losses, we notice that TCP doesn't have always the optimum behaviour as it reacts, in most cases, without considering the loss cause. This misbehaviour might cause network performance degradation and resources' waste. To overcome this problem, many LDAs have been designed. However, these LDAs were optimized for data networks where wireless link is only the last hop, meaning that they might be inadequate for MANETs. Also, the proposed LDAs deal only with losses due to wireless channel and/or congestion-induced errors. We show, in this paper, the importance of dealing with a third loss cause that is common in MANETs, which is link failure. We propose a new TCP variant that is called TCP-WELCOME. TCP-WELCOME can: (i) identify the loss cause by coupling loss and delay information, and (ii) trigger the appropriate packet loss recovery according to the identified loss cause. The performance evaluation, through both simulations and experimental tests, shows that TCP-WELCOME optimizes both energy consumption and achievable throughput. TCPWELCOME does not change the standard and can operate with existing TCP variants.
Cherrier S.,University Paris Est Creteil |
Ghamri-Doudane Y.M.,National School of Computer Science for Industry and Business |
Lohier S.,University Paris Est Creteil |
Roussel G.,University Paris Est Creteil
Proceedings - 2011 IEEE International Conferences on Internet of Things and Cyber, Physical and Social Computing, iThings/CPSCom 2011 | Year: 2011
Smartphones, PDA, Sensors, Actuators, Phidgets and Smart Objects (i.e. objects with processing and networking capabilities) are more and more present in everyday's life. Merging all these technologies with the Internet is often described as'Internet of Things' (IoT). In the IoT vision, Things around us provide a pervasive network of interacting and interconnected devices. However building IoT applications is a long and arduous work, reserved for specialists, requiring specific knowledges in terms of network protocols and programming languages. The lack of widespread and easy-to-configure solutions is an obstacle for the development of this area. A universal framework, offering simplification and standardization, could facilitate the emergence of this promising field in terms of applications and business. IoT needs a solid foundation for rapid, simple development and deployment of new services. In this paper, we present DLITe, a universal framework for building IoT applications over heterogeneous sets of small devices. D-LITe offers solutions for deploying application's logic, and executing it on Smart Objects despite their heterogeneity. An implementation of DLITe on tiny devices, such as TelosB motes, allows to show that our framework is realistic even with the constraints of such devices. © 2011 IEEE.
Burel G.,Max Planck Institute for Informatics |
Burel G.,National School of Computer Science for Industry and Business
Logical Methods in Computer Science | Year: 2011
In deduction modulo, a theory is not represented by a set of axioms but by a congruence on propositions modulo which the inference rules of standard deductive systems-such as for instance natural deduction-are applied. Therefore, the reasoning that is intrinsic of the theory does not appear in the length of proofs. In general, the congruence is defined through a rewrite system over terms and propositions. We define a rigorous framework to study proof lengths in deduction modulo, where the congruence must be computed in polynomial time. We show that even very simple rewrite systems lead to arbitrary proof-length speed-ups in deduction modulo, compared to using axioms. As higher-order logic can be encoded as a first-order theory in deduction modulo, we also study how to reinterpret, thanks to deduction modulo, the speed-ups between higher order and first-order arithmetics that were stated by Gödel. We define a first-order rewrite system with a congruence decidable in polynomial time such that proofs of higher-order arithmetic can be linearly translated into first-order arithmetic modulo that system. We also present the whole higher-order arithmetic as a first-order system without resorting to any axiom, where proofs have the same length as in the axiomatic presentation. © G. Burel.
Billionnet A.,National School of Computer Science for Industry and Business
Systematic Biology | Year: 2013
The phylogenetic diversity (PD) of a set of species is a measure of the evolutionary distance among the species in the collection, based on a phylogenetic tree. Such a tree is composed of a root, internal nodes, and leaves that correspond to the set of taxa under study. With each edge of the tree is associated a non-negative branch length (evolutionary distance). If a particular survival probability is associated with each taxon, the PD measure becomes the expected PD measure. In the Noah's Ark Problem (NAP) introduced by Weitzman (1998), these survival probabilities can be increased at some cost. The problem is to determine how best to allocate a limited amount of resources to maximize the expected PD of the considered species. It is easy to formulate the NAP as a (difficult) nonlinear 0-1 programming problem. The aim of this article is to show that a general version of the NAP (GNAP) can be solved simply and efficiently with any set of edge weights and any set of survival probabilities by using standard mixed-integer linear programming software. The crucial point to move from a nonlinear program in binary variables to a mixed-integer linear program, is to approximate the logarithmic function by the lower envelope of a set of tangents to the curve. Solving the obtained mixed-integer linear program provides not only a near-optimal solution but also an upper bound on the value of the optimal solution. We also applied this approach to a generalization of the nature reserve problem (GNRP) that consists of selecting a set of regions to be conserved so that the expected PD of the set of species present in these regions is maximized. In this case, the survival probabilities of different taxa are not independent of each other. Computational results are presented to illustrate potentialities of the approach. Near-optimal solutions with hypothetical phylogenetic trees comprising about 4000 taxa are obtained in a few seconds or minutes of computing time for the GNAP, and in about 30 min for the GNRP. In all the cases the average guarantee varies from 0% to 1.20%. © 2012 The Author(s).
Billionnet A.,National School of Computer Science for Industry and Business
Ecological Modelling | Year: 2011
The Reserve Selection Problem consists in selecting certain sites among a set of potential sites for biodiversity protection. In many models of the literature, the species present and able to survive in each site are supposed to be known. Here, for every potential site and for every species considered, only the probability that the species survives in the site is supposed to be known. The problem to select, under a budgetary constraint, a set of sites which maximizes the expected number of species is known in the literature under the name of probabilistic reserve selection problem. In this article, this problem is studied with species weighting to deal differently with common species and rare species. A spatial constraint is also considered preventing to obtain too fragmented reserve networks. As in Polasky et al. (2000), the problem is formulated by a nonlinear mathematical program in Boolean variables. Camm et al. (2002) developed a mixed-integer linear programming approximation that may be solved with standard integer programming software. The method gives tight approximate solutions but does not allow to tell how far these solutions are from the optimum. In this paper, a slightly different approach is proposed to approximate the problem. The interesting aspect of the approach, which also uses only standard mixed-integer programming software, is that it leads, not only to an approximate solution, but also to an upper limit on the true optimal value. In other words, the method gives an approximate solution with a guarantee on its accuracy. The linear reformulation is based on an upper approximation of the logarithmic function by a piecewise-linear function. The approach is very effective on artificial instances that include up to 400 sites and 300 species. Within an average CPU time of about 12 min, near-optimal solutions are obtained with an average relative error, in comparison to the optimum, of less than 0.2%. © 2010 Elsevier B.V.