Change search
Refine search result
1234567 51 - 100 of 601
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Rows per page
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sort
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
Select
The maximal number of hits you can export is 250. When you want to export more records please use the Create feeds function.
  • 51.
    Beldiceanu, Nicolas
    et al.
    École des Mines de Nantes, France.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Flener, Pierre
    Uppsala University, Sweden.
    Lorca, Xavier
    École des Mines de Nantes, France.
    Pearson, Justin
    Uppsala University, Sweden.
    Petit, Thierry
    École des Mines de Nantes, France; Worcester Polytechnic Institute, US.
    Prud'homme, Charles
    École des Mines de Nantes, France.
    A Modelling Pearl with Sortedness Constraints2015In: GCAI 2015. Global Conference on Artificial Intelligence / [ed] Georg Gottlob, Geoff Sutcliffe, Andrei Voronkov, 2015, 9, Vol. 36, p. 27-41Conference paper (Refereed)
    Abstract [en]

    Some constraint programming solvers and constraint modelling languages feature the Sort(L,P,S) constraint, which holds if S is a nondecreasing rearrangement of the list L, the permutation being made explicit by the optional list P. However, such sortedness constraints do not seem to be used much in practice. We argue that reasons for this neglect are that it is impossible to require the underlying sort to be stable, so that Sort cannot be guaranteed to be a total-function constraint, and that L cannot contain tuples of variables, some of which form the key for the sort. To overcome these limitations, we introduce the StableKeysort constraint, decompose it using existing constraints, and propose a propagator. This new constraint enables a powerful modelling idiom, which we illustrate by elegant and scalable models of two problems that are otherwise hard to encode as constraint programs.

  • 52.
    Beldiceanu, Nicolas
    et al.
    CNRS, France.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Flener, Pierre
    Uppsala University, Sweden.
    Pearson, Justin
    Uppsala University, Sweden.
    On Matrices, Automata, and Double Counting2010Conference paper (Refereed)
    Abstract [en]

    Matrix models are ubiquitous for constraint problems. Many such problems have a matrix of variables M, with the same constraint defined by a finite-state automaton A on each row of M and a global cardinality constraint gcc on each column of M. We give two methods for deriving, by double counting, necessary conditions on the cardinality variables of the gcc constraints from the automaton A. The first method yields linear necessary conditions and simple arithmetic constraints. The second method introduces the cardinality automaton, which abstracts the overall behaviour of all the row automata and can be encoded by a set of linear constraints. We evaluate the impact of our methods on a large set of nurse rostering problem instances.

  • 53. Beldiceanu, Nicolas
    et al.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Flener, Pierre
    Pearson, Justin
    On matrices, automata, and double counting in constraint programming2013In: Constraints, Vol. 18, p. 108-140Article in journal (Refereed)
    Abstract [en]

    Matrix models are ubiquitous for constraint problems. Many such problems have a matrix of variables M , with the same constraint C defined by a finite-state automaton A on each row of M and a global cardinality constraint "gcc" on each column of M . We give two methods for deriving, by double counting, necessary conditions on the cardinality variables of the "gcc" constraints from the automaton A . The first method yields linear necessary conditions and simple arithmetic constraints. The second method introduces the cardinality automaton, which abstracts the overall behaviour of all the row automata and can be encoded by a set of linear constraints. We also provide a domain consistency filtering algorithm for the conjunction of lexicographic ordering constraints between adjacent rows of M and (possibly different) automaton constraints on the rows. We evaluate the impact of our methods in terms of runtime and search effort on a large set of nurse rostering problem instances.

  • 54. Beldiceanu, Nicolas
    et al.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Flener, Pierre
    Pearson, Justin
    On the Reification of Global Constraints2012Report (Other academic)
    Abstract [en]

    We introduce a simple idea for deriving reified global constraints in a systematic way. It is based on the observation that most global constraints can be reformulated as a conjunction of pure functional dependency constraints together with a constraint that can be easily reified. We first show how the core constraints of the Global Constraint Catalogue can be reified and we then identify several reification categories that apply to at least 82% of the constraints in the Global Constraint Catalogue.

  • 55. Beldiceanu, Nicolas
    et al.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Flener, Pierre
    Pearson, Justin
    On the reification of global constraints2013In: Constraints, Vol. 18, p. 1-6Article in journal (Refereed)
    Abstract [en]

    We introduce a simple idea for deriving reified global constraints in a systematic way. It is based on the observation that most global constraints can be reformulated as a conjunction of total function constraints together with a constraint that can be easily reified.

  • 56.
    Beldiceanu, Nicolas
    et al.
    CNRS INRIA, France.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Flener, Pierre
    Uppsala University, Sweden.
    Rodríguez, María Andreína Francisco
    Uppsala University, Sweden.
    Pearson, Justin
    Uppsala University, Sweden.
    Linking Prefixes and Suffixes for Constraints Encoded Using Automata with Accumulators2014Conference paper (Refereed)
    Abstract [en]

    Consider a constraint on a sequence of variables functionally determining a result variable that is unchanged under reversal of the sequence. Most such constraints have a compact encoding via an automaton augmented with accumulators, but it is unknown how to maintain domain consistency efficiently for most of them. Using such an automaton for such a constraint, we derive an implied constraint between the result variables for a sequence, a prefix thereof, and the corresponding suffix. We show the usefulness of this implied constraint in constraint solving, both by local search and by propagation-based systematic search.

  • 57. Beldiceanu, Nicolas
    et al.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Martin, Julien
    Compiling business rules in a geometric constraint over k-dimensional objects and shapes2009Report (Other academic)
    Abstract [en]

    It is well known that real-life applications rarely admit a constraint model expressed purely in terms of a few global constraints. Usually, the global constraints capture a relaxed form of the problem, but needs additional side-constraints to capture the full problem. Handling such side-constraints inside the global constraints, as opposed to in conjunction with it, improves propagation. Historically, this has been done by extending the global constraints with a host of specific options, each connected to a specific filtering method. Being able to express and filter side-constraints in a more uniform and systematic way would seem a more elegant and manageable solution. This report presents such a mechanism for the global non-overlapping constraint "geost", which handles the location in space of k-dimensional objects. Side-constraints are expressed as rules written in a language based on arithmetic and first-order logic, which should hold among the objects. We explain in detail the way the rules are compiled into a form that is accessed by the constraint's sweep-based filtering algorithm. In a first step, the rules are rewritten to Quantifier-Free Presburger Arithmetic (QFPA) formulas. Secondly, such formulas are transformed to generators of k-dimensional forbidden sets. Thirdly, the generators are transformed to procedures answering queries about candidate coordinate points for a given object. Such queries are at the heart of the filtering algorithm. The business rules allow to express a great variety of packing and placement constraints, while admitting effective filtering of the domain variables of the k-dimensional object, without the need to use spatial data structures. The constraint was used to directly encode the packing knowledge of a major car manufacturer, and was evaluated on several benchmarks.

  • 58. Beldiceanu, Nicolas
    et al.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Petit, Thierry
    Deriving Filtering Algorithms from Constraint Checkers2004Report (Other academic)
    Abstract [en]

    This report deals with global constraints for which the set of solutions can be recognized by an extended finite automaton whose size is bounded by a polynomial in $n$, where $n$ is the number of variables of the corresponding global constraint. By reformulating the automaton as a conjunction of signature and transition constraints we show how to systematically obtain a filtering algorithm. Under some restrictions on the signature and transition constraints this filtering algorithm achieves arc-consistency. An implementation based on some constraints as well as on the metaprogramming facilities of SICStus Prolog is available. For a restricted class of automata we provide a filtering algorithm for the relaxed case, where the violation cost is the minimum number of variables to unassign in order to get back to a solution.

  • 59. Beldiceanu, Nicolas
    et al.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Petit, Thierry
    Deriving filtering algorithms from constraint checkers2004In: Proceedings of Principles and Practice of Constraint Programming – CP 2004, 10th International Conference, Springer , 2004, 1, Vol. 3258, p. 16p. 107-122Conference paper (Refereed)
    Abstract [en]

    This article deals with global constraints for which the set of solutions can be recognized by an extended finite automaton whose size is bounded by a polynomial in n, where n is the number of variables of the corresponding global constraint. By reformulating the automaton as a conjunction of signature and transition constraints we show how to systematically obtain a filtering algorithm. Under some restrictions on the signature and transition constraints this filtering algorithm achieves arc-consistency. An implementation based on some constraints as well as on the metaprogramming facilities of SICStus Prolog is available. For a restricted class of automata we provide a filtering algorithm for the relaxed case, where the violation cost is the minimum number of variables to unassign in order to get back to a solution.

  • 60. Beldiceanu, Nicolas
    et al.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Petit, Thierry
    Régin, Jean-Charles
    An O(n log n) Bound Consistency Algorithm for the Conjunction of an alldifferent and an Inequality between a Sum of Variables and a Constant, and its Generalization2012Conference paper (Refereed)
    Abstract [en]

    This paper gives an O(n log n) bound-consistency filtering algorithm for the conjunction alldifferent(V0,V1,…,Vn−1)∧ f(V0)⌖f(V1)⌖…⌖f(Vn−1) ≤ cst, (V0,V1,…,Vn−1,cst ∊ N+), where (N,⌖) is a commutative group, f is a unary function, and both ⌖ and f are monotone increasing. This complexity is equal to the complexity of the bound-consistency algorithm of the alldifferent constraint.

  • 61. Beldiceanu, Nicolas
    et al.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Poder, Emmanuel
    New filtering for the cumulative constraint in the context of non-overlapping rectangles2008In: CPAIOR 2008, Springer , 2008, 1, Vol. 5015, p. 21-35Conference paper (Refereed)
    Abstract [en]

    This paper describes new filtering methods for the cumulative constraint. The first method introduces bounds for the so called longest cumulative hole problem and shows how to use these bounds in the context of the non-overlapping constraint. The second method introduces balancing knapsack constraints which relate the total height of the tasks that end at a specific time-point with the total height of the tasks that start at the same time-point. Experiments on tight rectangle packing problems show that these methods drastically reduce both the time and the number of backtracks for finding all solutions as well as for finding the first solution. For example, we found without backtracking all solutions to 66 perfect square instances of order 23-25 and sizes ranging from 332 times 332 to 661 times 661.

  • 62.
    Beldiceanu, Nicolas
    et al.
    RISE, Swedish ICT, SICS.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Poder, Emmanuel
    Sadek, Rida
    Truchet, Charlotte
    A Generic Geometrical Constraint Kernel in Space and Time for Handling Polymorphic k-Dimensional Objects2007Conference paper (Refereed)
    Abstract [en]

    This paper introduces a geometrical constraint kernel for handling the location in space and time of polymorphic k-dimensional objects subject to various geometrical and time constraints. The constraint kernel is generic in the sense that one of its parameters is a set of constraints on subsets of the objects. These constraints are handled globally by the kernel. We first illustrate how to model several placement problems with the constraint kernel. We then explain how new constraints can be introduced and plugged into the kernel. Based on these interfaces, we develop a generic k-dimensional lexicographic sweep algorithm for filtering the attributes of an object (i.e., its shape and the coordinates of its origin as well as its start, duration and end in time) according to all constraints where the object occurs. Experiments involving up to hundreds of thousands of objects and 1 million integer variables are provided in 2, 3 and 4 dimensions, both for simple shapes (i.e., rectangles, parallelepipeds) and for more complex shapes.

  • 63. Beldiceanu, Nicolas
    et al.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Rampon, Jean-Xavier
    Global Constraint Catalog2005Report (Other academic)
    Abstract [en]

    This report presents a catalog of global constraints where each constraint is explicitly described in terms of graph properties and/or automata. When available, it also presents some typical usage as well as some pointers to existing filtering algorithms.

  • 64. Beldiceanu, Nicolas
    et al.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Rampon, Jean-Xavier
    Global Constraint Catalog, 2nd Edition2010Report (Other academic)
    Abstract [en]

    This report presents a catalogue of global constraints where each constraint is explicitly described in terms of graph properties and/or automata and/or first order logical formulae with arithmetic. When available, it also presents some typical usage as well as some pointers to existing filtering algorithms.

  • 65. Beldiceanu, Nicolas
    et al.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Rampon, Jean-Xavier
    Global Constraint Catalog, 2nd Edition (revision a)2012Report (Other academic)
    Abstract [en]

    This report presents a catalogue of global constraints where each constraint is explicitly described in terms of graph properties and/or automata and/or first order logical formulae with arithmetic. When available, it also presents some typical usage as well as some pointers to existing filtering algorithms.

  • 66. Beldiceanu, Nicolas
    et al.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Rampon, Jean-Xavier
    Truchet, Charlotte
    Graph invariants as necessary conditions for global constraints2005In: CP'2005, Principles and Practice of Constraint Programming, LNCS, Vol. 3709, p. 92-106Article in journal (Refereed)
    Abstract [en]

    This article presents a database of about 200 graph invariants for deriving systematically necessary conditions from the graph properties based representation of global constraints. This scheme is based on invariants on the graph characteristics used in the description of a global constraint. A SICStus Prolog implementation based on arithmetic and logical constraints as well as on indexicals is available.

  • 67. Beldiceanu, Nicolas
    et al.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Rampon, Jean-Xavier
    Truchet, Charlotte
    Graph Invariants as Necessary Conditions for Global Constraints2005Report (Other academic)
    Abstract [en]

    This report presents a database of about 200 graph invariants for deriving systematically necessary conditions from the graph properties based representation of global constraints. This scheme is based on invariants on the graph characteristics used in the description of a global constraint. A SICStus Prolog implementation based on arithmetic and logical constraints as well as on indexicals is available.

  • 68. Beldiceanu, Nicolas
    et al.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Thiel, Sven
    Cost-Filtering Algorithms for the two Sides of the Sum of Weights of Distinct Values Constraint2002Report (Other academic)
    Abstract [en]

    This article introduces the sum of weights of distinct values constraint, which can be seen as a generalization of the number of distinct values as well as of the alldifferent, and the relaxed alldifferent constraints. This constraint holds if a cost variable is equal to the sum of the weights associated to the distinct values taken by a given set of variables. For the first aspect, which is related to domination, we present four filtering algorithms. Two of them lead to perfect pruning when each domain variable consists of one set of consecutive values, while the two others take advantage of holes in the domains. For the second aspect, which is connected to maximum matching in a bipartite graph, we provide a complete filtering algorithm for the general case. Finally we introduce several generic deduction rules, which link both aspects of the constraint. These rules can be applied to other optimization constraints such as the minimum weight alldifferent constraint or the global cardinality constraint with costs. They also allow taking into account external constraints for getting enhanced bounds for the cost variable. In practice, the sum of weights of distinct values constraint occurs in assignment problems where using a resource once or several times costs the same. It also captures domination problems where one has to select a set of vertices in order to control every vertex of a graph.

  • 69. Beldiceanu, Nicolas
    et al.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Thiel, Sven
    Sweep synchronisation as a global propagation mechanism2006In: Computers & Operations Research, Vol. 3, p. 2835-2851Article in journal (Refereed)
    Abstract [en]

    This paper presents a new generic filtering algorithm that simultaneously considers n conjunctions of constraints as well as those constraints mentioning some variables Y_k of the pairs (X,Y_k) (1 <= k <= n) occurring in these conjunctions. The main benefit of this new technique comes from the fact that, for adjusting the bounds of a variable X according to n conjunctions, we do not perform n sweeps in an independent way but rather synchronize them. We then specialize this technique to the non-overlapping rectangles constraint where we consider the case where several rectangles of height one have the same X coordinate for their origin as well as the same length. For this specific constraint we come up with an incremental bipartite matching algorithm which is triggered while we sweep over the time axis. We illustrate the usefulness of this new pruning method on a timetabling problem, where each task can’t be interrupted and requires the simultaneous availability of n distinct persons. Each person has his own periods of unavailability and can only perform one task at a time.

  • 70.
    Beldiceanu, Nicolas
    et al.
    RISE, Swedish ICT, SICS.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Thiel, Sven
    Sweep synchronization as a global propagation mechanism2003Conference paper (Refereed)
    Abstract [en]

    This paper presents a new generic filtering algorithm that simultaneously considers n conjunctions of constraints as well as those constraints mentioning some variables Yk of the pairs X,Yk (1<=k<=n) occurring in these conjunctions. The main benefit of this new technique comes from the fact that, for adjusting the bounds of a variable X according to n conjunctions, we do not perform n sweeps in an independent way but rather synchronize them. We then specialize this technique to the non-overlapping rectangles constraint where we consider the case where several rectangles of height one have the same X coordinate for their origin as well as the same length. For this specific constraint we come up with an incremental bipartite matching algorithm which is triggered while we sweep over the time axis. We illustrate the usefulness of this new pruning method on a timetabling problem, where each task can not be interrupted and requires the simultaneous availability of n distinct persons. Each person has his own periods of unavailability and can only perform one task at a time.

  • 71.
    Beldiceanu, Nicolas
    et al.
    RISE - Research Institutes of Sweden, ICT, SICS.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Thiel, Sven
    Sweep Synchronization as a Global Propagation Mechanism2003Report (Other academic)
    Abstract [en]

    This paper presents a new generic filtering algorithm that simultaneously considers n conjunctions of constraints as well as those constraints mentioning some variables Yk of the pairs X,Yk (1<=k<=n) occurring in these conjunctions. The main benefit of this new technique comes from the fact that, for adjusting the bounds of a variable X according to n conjunctions, we do not perform n sweeps in an independent way but rather synchronize them. We then specializes this technique to the non-overlapping rectangles constraint where we consider the case where several rectangles of height one have the same X coordinate for their origin as well as the same length. For this specific constraint we come up with an incremental bipartite matching algorithm which is triggered while we sweep over the time axis. We illustrate the usefulness of this new pruning method on a timetabling problem, where each task can’t be interrupted and requires the simultaneous availability of n distinct persons. Each person has its own periods of unavailability and can only perform one task at a time.

  • 72. Beldiceanu, Nicolas
    et al.
    Poder, Emmanuel
    Sadek, Rida
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Truchet, Charlotte
    A Generic Geometrical Constraint Kernel in Space and Time for Handling Polymorphic k-Dimensional Objects2007Report (Other academic)
    Abstract [en]

    This report introduces a geometrical constraint kernel for handling the location in space and time of polymorphic k-dimensional objects subject to various geometrical and time constraints. The constraint kernel is generic in the sense that one of its parameters is a set of constraints on subsets of the objects. These constraints are handled globally by the kernel. We first illustrate how to model several placement problems with the constraint kernel. We then explain how new constraints can be introduced and plugged into the kernel. Based on these interfaces, we develop a generic k-dimensional lexicographic sweep algorithm for filtering the attributes of an object (i.e., its shape and the coordinates of its origin as well as its start, duration and end in time) according to all constraints where the object occurs. Experiments involving up to hundreds of thousands of objects and 1 million integer variables are provided in 2, 3 and 4 dimensions, both for simple shapes (i.e., rectangles, parallelepipeds) and for more complex shapes.

  • 73. Belenguer, J. S.
    et al.
    Lundén, M
    Laaksolahti, Jarmo
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Sundström, Petra
    RISE, Swedish ICT, SICS.
    Immaterial materials: designing with radio2012Conference paper (Refereed)
  • 74.
    Bjurling, Björn
    et al.
    RISE, Swedish ICT, SICS, Decisions, Networks and Analytics lab.
    Rasmusson, Lars
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Johansson, Ulf M
    Qualitative policies for bandwidth priorities in ad-hoc networks2008In: Proc. IEEE 27th Conference on Computer Communications, 2008, 1Conference paper (Refereed)
  • 75. Boano, Carlo Alberto
    et al.
    Brown, James
    He, Zhitao
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Roedig, Utz
    Voigt, Thiemo
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Low-power radio communication in industrial outdoor deployments: the impact of weather conditions and ATEX-compliance2009Conference paper (Refereed)
  • 76. Boano, Carlo Alberto
    et al.
    He, Zhitao
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Li, Yafei
    Voigt, Thiemo
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Zuniga, Marco
    Willig, Andreas
    Controllable radio interference for experimental and testing purposes in wireless sensor networks2009Conference paper (Refereed)
  • 77. Boano, Carlo Alberto
    et al.
    Römer, Kay
    He, Zhitao
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Voigt, Thiemo
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Zuniga, Marco
    Willig, Andreas
    Demo Abstract: Generation of Controllable Radio Interference for Protocol Testing in Wireless Sensor Networks2009Conference paper (Refereed)
  • 78.
    Boano, Carlo Alberto
    et al.
    Graz University of Technology, Austria.
    Römer, Kay
    Graz University of Technology, Austria.
    Tsiftes, Nicolas
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Mitigating the Adverse Effects of Temperature on Low-Power Wireless Protocols2014Conference paper (Refereed)
    Abstract [en]

    Research and industrial installations have shown that the on-board temperature of wireless sensor nodes deployed outdoors can experience high fluctuations over time with a large variability across the network. These variations can have a strong impact on the efficiency of low-power radios and can significantly affect the operation of communication protocols, often compromising network connectivity. In this paper, we show the adverse effects of temperature on communication protocols and propose techniques to increase their resilience. First, we experimentally show that fluctuations of the on-board temperature of sensor nodes reduce the efficiency of data link layer protocols, leading to a substantial decrease in packet reception rate and to a considerable increase in energy consumption. Second, we investigate the reasons for such performance degradation, and show that high on-board temperatures reduce the effectiveness of clear channel assessment, compromising the ability of a node to avoid collisions and to successfully wake-up from low-power mode. After modelling the behaviour of radio transceivers as a function of temperature, we propose two mechanisms to dynamically adapt the clear channel assessment threshold to temperature changes, thus making data link layer protocols temperature-aware. An extensive experimental evaluation shows that our approaches considerably increase the performance of a network in the presence of temperature variations commonly found in real-world outdoor deployments, with up to 42% lower radio duty-cycle and 87% higher packet reception rate.

  • 79. Boano, Carlo Alberto
    et al.
    Römer, Kay
    Voigt, Thiemo
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Zuniga, Marco
    Poster Abstract: Agreement for Wireless Sensor Networks under External Interference2012Conference paper (Refereed)
  • 80. Boano, Carlo Alberto
    et al.
    Römer, Kay
    Österlind, Fredrik
    RISE, Swedish ICT, SICS.
    Voigt, Thiemo
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Demo Abstract: Realistic Simulation of Radio Interference in COOJA2011Conference paper (Refereed)
  • 81.
    Boano, Carlo Alberto
    et al.
    RISE, Swedish ICT, SICS.
    Tsiftes, Nicolas
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Voigt, Thiemo
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Brown, James
    Roedig, Utz
    The Impact of Temperature on Outdoor Industrial Sensornet Applications2010In: IEEE Transactions on Industrial Informatics, ISSN 1551-3203, E-ISSN 1941-0050, Vol. 6, p. 451-459Article in journal (Refereed)
  • 82. Boano, Carlo Alberto
    et al.
    Voigt, Thiemo
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Dunkels, Adam
    RISE, Swedish ICT, SICS.
    Österlind, Fredrik
    RISE, Swedish ICT, SICS.
    Tsiftes, Nicolas
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Mottola, Luca
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Suarez, Pablo
    Poster Abstract: Exploiting the LQI Variance for Rapid Channel Quality Assessment2009Conference paper (Refereed)
  • 83. Boano, Carlo Alberto
    et al.
    Voigt, Thiemo
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Noda, Claro
    Römer, Kay
    Zuniga, Marco
    JamLab: Augmenting Sensornet Testbeds with Realistic and Controlled Interference Generation2011Conference paper (Refereed)
  • 84. Boano, Carlo Alberto
    et al.
    Voigt, Thiemo
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Tsiftes, Nicolas
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Mottola, Luca
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Römer, Kay
    Zuniga, Marco
    Making Sensornet MAC Protocols Robust Against Interference2010Conference paper (Refereed)
    Abstract [en]

    Radio interference may lead to packet losses, thus negatively affecting the performance of sensornet applications. In this paper, we experimentally assess the impact of external interference on state-of-the-art sensornet MAC protocols. Our experiments illustrate that specific features of existing protocols, e.g., hand-shaking schemes preceding the actual data transmission, play a critical role in this setting. We leverage these results by identifying mechanisms to improve the robustness of existing MAC protocols under interference. These mechanisms include the use of multiple hand-shaking attempts coupled with packet trains and suitable congestion backoff schemes to better tolerate interference. We embed these mechanisms within an existing X-MAC implementation and show that they considerably improve the packet delivery rate while keeping the power consumption at a moderate level.

  • 85. Boano, Carlo Alberto
    et al.
    Wennerström, Hjalmar
    Zuniga, Marco
    Brown, James
    Keppitiyagama, Chamath
    RISE, Swedish ICT, SICS.
    Oppermann, Felix
    Roedig, Utz
    Norden, Lars-Åke
    Voigt, Thiemo
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Römer, Kay
    Hot Packets: A Systematic Evaluation of the Effect of Temperature on Low Power Wireless Transceivers2013Conference paper (Refereed)
    Abstract [en]

    Temperature is known to have a significant effect on the performance of radio transceivers: the higher the temper- ature, the lower the quality of links. Analysing this effect is particularly important in sensor networks because several applications are exposed to harsh environmental conditions. Daily or hourly changes in temperature can dramatically reduce the throughput, increase the delay, or even lead to network partitions. A few studies have quantified the impact of temperature on low-power wireless links, but only for a limited temperature range and on a single radio transceiver. Building on top of these preliminary observations, we de- sign a low-cost experimental infrastructure to vary the on- board temperature of sensor nodes in a repeatable fashion, and we study systematically the impact of temperature on various sensornet platforms. We show that temperature af- fects transmitting and receiving nodes differently, and that all platforms follow a similar trend that can be captured in a simple first-order model. This work represents an ini- tial stepping stone aimed at predicting the performance of a network considering the particular temperature profile of a given environment.

  • 86. Boano, Carlo Alberto
    et al.
    Zuniga, Marco
    Römer, Kay
    Voigt, Thiemo
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    JAG: Reliable and Predictable Wireless Agreement under External Radio Interference2012Conference paper (Refereed)
  • 87. Boano, Carlo Alberto
    et al.
    Zuniga, Marco
    Voigt, Thiemo
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Willig, Andreas
    Römer, Kay
    The Triangle Metric: Fast Link Quality Estimation for Mobile Wireless Sensor Networks (Invited Paper)2010Conference paper (Refereed)
  • 88.
    Boman, Magnus
    et al.
    RISE, Swedish ICT, SICS, Decisions, Networks and Analytics lab.
    Laaksolahti, Jarmo
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Espinoza, Fredrik
    RISE - Research Institutes of Sweden, ICT, SICS.
    Cöster, Rickard
    RISE - Research Institutes of Sweden, ICT, SICS.
    Trust in Micro Service Environments2006Report (Other academic)
    Abstract [en]

    Report produced in the project Enabling and Promoting Trust in Micro Service Environments (EPTMSE) with a web site at www.trust-eze.org. The report gives an overview of the concept of trust in domains such as psychology, sociology, philosophy, and computer science, and then describes the current domain of Micro Service Environments - open and unregulated electronic service environments - where users can create, use, and share electronic services, and where the need for decentralized trust mechanisms is high. Some design and implementation choices and solutions for trust mechanisms are suggested.

  • 89.
    Bor, Martin
    et al.
    Lancaster University, UK.
    Roedig, Utz
    Lancaster University, UK.
    Voigt, Thiemo
    RISE, Swedish ICT, SICS, Computer Systems Laboratory. Uppsala University, Sweden.
    Alonso, Juan
    National University of Cuyo, Argentina; National University of San Luis, Argentina.
    Do LoRa Low-Power Wide-Area Networks Scale?2016In: Proceedings of the 19th ACM International Conference on Modeling, Analysis and Simulation of Wireless and Mobile Systems, 2016, p. 59-67Conference paper (Refereed)
    Abstract [en]

    New Internet of Things (IoT) technologies such as Long Range (LoRa) are emerging which enable power efficient wireless communication over very long distances. Devices typically communicate directly to a sink node which removes the need of constructing and maintaining a complex multihop network. Given the fact that a wide area is covered and that all devices communicate directly to a few sink nodes a large number of nodes have to share the communication medium. LoRa provides for this reason a range of communication options (centre frequency, spreading factor, bandwidth, coding rates) from which a transmitter can choose. Many combination settings are orthogonal and provide simultaneous collision free communications. Nevertheless, there is a limit regarding the number of transmitters a LoRa system can support. In this paper we investigate the capacity limits of LoRa networks. Using experiments we develop models describing LoRa communication behaviour. We use these models to parameterise a LoRa simulation to study scalability. Our experiments show that a typical smart city deployment can support 120 nodes per 3.8 ha, which is not sufficient for future IoT deployments. LoRa networks can scale quite well, however, if they use dynamic communication parameter selection and/or multiple sinks.

  • 90.
    Brand, Per
    et al.
    RISE, Swedish ICT, SICS.
    Franzén, Nils
    Klintskog, Erik
    RISE, Swedish ICT, SICS.
    Haridi, Seif
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    A platform for constructing virtual spaces1998Conference paper (Refereed)
    Abstract [en]

    Virtual spaces (worlds) applications are among the most complex of distributed applications. They are both distributed and open. Minimizing network latency, fault-tolerance, persistence, resource control, and security are also important aspects. Designing and implementing virtual spaces is currently difficult in that the already not insignificant complexities of program functionality, distribution, openness, and efficiency are interwound and cannot be tackled separately. We present a distributed programming language, distributed-Oz, that greatly reduces the complexity of distributed programming by clearly separating the different aspects of distributed programming. The design and implementation of distributed-Oz is ongoing work, but considerable progress has been made. The current prototype demonstrates network transparency, that computations behave the same way regardless of how the computation is partitioned between different sites. This is the basis for realizing clean separation of the functionality aspect from other aspects. Network awareness allows the programmer to predict and control network communication patterns. The current system gives the programmer the means to tackle separately the aspects of openness, efficiency (minimizing latency), distribution, and functionality. We have extended distributed-Oz with a tool for graphics in a distributed setting. This extends the idea of network transparency and network awareness to graphics. From the programmers point of view graphics programming for a multi-user application is virtually the same as programming for a single-user application. The differences are necessary extensions for achieving network and site awareness, such as visualization control (deciding which users should see what). Finally we consider virtual space applications, and propose a number of abstractions for use by developers of virtual spaces, relating them to the properties of distributed-Oz upon which they are based.

  • 91. Braun, Torsten
    et al.
    Voigt, Thiemo
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Dunkels, Adam
    RISE, Swedish ICT, SICS.
    Energy-Efficient TCP Operation in Wireless Sensor Networks2005In: PIK Journal Special Issue on Sensor Networks, ISSN 0930-5157, Vol. 28Article in journal (Refereed)
  • 92. Braun, Torsten
    et al.
    Voigt, Thiemo
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Dunkels, Adam
    RISE, Swedish ICT, SICS.
    Tcp support for sensor networks2007Conference paper (Refereed)
  • 93. Brown, James
    et al.
    McCarthy, Ben
    Roedig, Utz
    Voigt, Thiemo
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Sreenan, Cormac J.
    BurstProbe: Debugging Time-Critical Data Delivery in Wireless Sensor Networks2011Conference paper (Refereed)
    Abstract [en]

    In this paper we present BurstProbe, a new technique to accurately measure link burstiness in a wireless sensor network employed for time-critical data delivery. Measurement relies on shared probing slots that are embedded in the transmission schedule and used by nodes to assess link burstiness over time. The acquired link burstiness information can be stored in the node's ash memory and relied upon to diagnose transmission problems when missed deadlines occur. Thus, accurate diagnosis is achieved in a distributed manner and without the overhead of transmitting rich measurement data to a central collection point. For the purpose of evaluation we have implemented BurstProbe in the GinMAC WSN protocol and we are able to demonstrate it is an accurate tool to debug time-critical data delivery. In addition, we analyze the cost of implementing BurstProbe and investigate its effectiveness.

  • 94. Brown, James
    et al.
    Roedig, Utz
    Boano, Carlo Alberto
    Roemer, Kay
    Tsiftes, Nicolas
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Demo Abstract: How Temperature Affects IoT Communication2014Conference paper (Refereed)
    Abstract [en]

    In the future we will rely on applications built on top of the Internet of Things (IoT). Example applications are smart cities, smart grids and smart healthcare. These IoT applications require a reliable service with predictable quality, and that sensor data and actuator commands are delivered reliably and timely. Unfortunately, IoT performance is highly affected by environmental conditions, especially by ambient temperature. It is therefore necessary to configure an IoT system such that sufficient application performance is provided under all environmental conditions that may be encountered. In this demonstration, we show how ambient temperature affects the performance of an IoT application. Specifically, we connect remotely to a large-scale temperature-controlled testbed and show how temperature affects the operation of a state-of-the- art routing protocol. Using a local setup, we further demonstrate how the impact of temperature on communication links can be easily captured and modelled in order to inform the design of communication protocols robust to high temperature fluctuations.

  • 95. Carlson, Björn
    et al.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Compiling and executing disjunctions of finite domain constraints1995In: Proceedings of the Twelfth International Conference on Logic Programming, 13-16 June 1995, Tokyo, Japan / [ed] L. Sterling, The MIT Press , 1995, 1, , p. 15Conference paper (Refereed)
  • 96. Carlson, Björn
    et al.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Diaz, Daniel
    Entailment of finite domain constraints1994Conference paper (Refereed)
  • 97. Carlson, Björn
    et al.
    Janson, Sverker
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    The implementation of AKL(FD)1995Conference paper (Refereed)
  • 98.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    A BDD-based approach to multiple level combinational logic synthesis1992In: Practical Application of Prolog / [ed] Al Roth, 1992, 1Conference paper (Refereed)
  • 99.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    A Prolog compiler and its extension for OR-parallelism1990Report (Other academic)
    Abstract [en]

    This report describes algorithms for the compiler component of the Aurora Or-Parallel Prolog system. The compiler translates one Prolog clause at a time into a sequence of abstract instructions. The instruction set is based on the sequential Warren Ab- stract Machine (WAM) with extensions for full Prolog, shallow backtracking, memory management and garbage collection, and for the SRI model of or-parallel execution of Prolog. Most of the described algorithms apply to compilation of sequential Prolog programs. The extensions introduced to support or-parallelism are minor, and concern pruning operators (cut and commit) and compile-time allocation of binding array offsets for permanent variables (generalised environment trimming). Code generation proper is kept separate from register allocation, and uses heuristics for finding a compilation order which minimises the number of register-register copies. After such copies have been coalesced where possible, register allocation is performed in a single pass over the intermediate code. The various compilation phases are described in detail, and the implementation is compared with some other compilers.

  • 100.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    An implementation of dif and freeze in the WAM1986Report (Other academic)
1234567 51 - 100 of 601
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
v. 2.35.7