Publications

Mobile Ad Hoc Networks

  • A. Piyatumrong and P. Bouvry and F. Guinand and K. Lavangnananda. Trusted Spanning Tree for Delay Tolerant MANETs. Proceedings of the 2008 IEEE/IFIP International Conference on Embedded and Ubiquitous Computing (EUC-08). December 17-20, 2008. Shanghai, China.   BibTeX

    Abstract:
    Quality of service is an important issue in Delay Tolerant MANETs. This work aims at increasing the QoS in such networks by relying on spanning forests (DA-GRS). The existing algorithms are improved by introducing the notion of trust into the spanning forest and choosing the most robust (trustable) spanning trees among existing opportunities. The robustness/quality of the tree can be assessed based on two cost functions. Two heuristics are proposed "G-TRUST" (a greedy-based heuristic) and "G-TRUST BREAK" (including an automatic tree reconfiguration heuristic) and evaluated.

  • J. Franzolini, F. Guinand and D. Olivier. DT-MANET for Rescue Information Services. Proceedings of the European Simulation and Modelling Conference (ESM'08), pages 516-520. 27-29 Octobre 2008, Le Havre, France. BibTeX

    Abstract:
    In case of natural or industrial disaster, alert and communication systems become an essential tool for rescue services and a way to inform and to alert population. The traditional communication and alert systems need static infrastructure. Mobiles devices are now ubiquitous and offer a free support for a spontaneous network. The goal of our project is to perform a delay tolerant network based on mobile devices. In this network mobile nodes are able to transmit data only with their neighborhood, it is an ad-hoc network. It gives no guarantee that a path between any couple of stations can be found. The network used a flooding method to propagate data which is called DFCN - standing for delayed flooding with cumulative neighborhood. This protocol uses two thresholds for avoiding the well-known "broadcast-storm". This flooding model gives the ability to self-adapt to the environment when the distribution of devices is unknown and not uniform. In this document we present an experimentation of DFCN on mobile ad-hoc network applied to the risk management

  • J. Franzolini and F. Guinand and D. Olivier. Circulation d'informations liées à la gestion du risque par réseaux mobiles ad-hoc. Actes de la conférence Lambda Mu. 5-9 octobre. Avignon, France. 2008.   BibTeX

    Résumé :
    En cas de désastre naturel ou industriel, les systèmes de communication et d'alerte deviennent un outil essentiel pour le personnel de secours et un moyen d'alerter la population. Généralement, ces systèmes de communication et d'alerte ont besoin d'infrastructure fixe. De nos jours, les appareils mobiles sont de plus en plus présents et peuvent offrir un support réseau à moindre coût. Le but du projet est de développer un nouveau support de communication acceptant les délais basé sur l'utilisation d'appareils mobiles sans-fil. Dans ce type de réseaux, les stations mobiles (PDA, Pocket PC, Smartphone...) sont capable de communiquer avec leurs voisins directs. Dans certains réseaux, il n'y a aucune garantie, qu'un chemin existe entre les différents couples de stations. La méthode de routage utilisée est le protocole de communication appelé DFCN (pour Delayed Flooding with Cumulative Neighborhood). Il est basé sur l'utilisation de 2 seuils de diffusion pour s'affranchir du phénomène "d'orage de diffusion". Ce protocole a la capacité de s'adapter à son environnement quand la distribution n'est pas uniforme et connue uniquement localement. Nous présentons une utilisation de réseaux mobiles ad-hoc appliquée à la maîtrise du risque.

  • P. Bouvry, J. Franzolini, F. Guinand, L. Hogie, D. Olivier and Y. Pigné. Broadcasting in DT-MANETs form Simulation to Real-life. Demonstration session during the Seventh International Conference on Ad-Hoc Networks and Wireless (AdHoc-Now 2008). September 10-13, 2008. Sophia-Antipolis, France.
  • L. Hogie and G. Danoy and P. Bouvry and F. Guinand. Context-Aware Broadcast Protocol for Mobile Wireless Networks. In Modelling, Computation and Optimization in Information Systems and Management Sciences. Second International Conference MCO 2008. September 8-10, 2008. Metz, France - Luxembourg. Proceedings Series: Communications in Computer and Information Science , Vol. 14, pages 507-519. L. T. Hoai An, P. Bouvry, T. Pham Dinh (editors).   BibTeX

    Abstract:
    Delay Tolerant Networks (DTNs) are a sub-class of mobile ad hoc networks (MANETs). They are mobile wireless networks that feature inherent connection disruption. In particular such networks are generally non-connected. In this paper we focus on defining a broadcast service which operate on DTNs. A number of protocols solving the problem of broadcasting across DTNs have been proposed in the past, but all of them exhibit a static behavior, i.e. they provide no control parameter. However, at the application level, flexible broadcasting schemes are desirable. In particular, it is important that the user (the source of the broadcast message) can control the way the message gets spread across the network. This paper introduces a new broadcasting protocol dedicated to DTNs, called Context-Aware Broadcasting Protocol (CABP), which adapts its greediness according to the "urgency" (priority) of the broadcast message. A formal presentation of its strategy is proposed and through preliminary experiments, the cost-effectiveness of CABP is enlightened.

  • J. Franzolini, F. Guinand, D. Olivier and Y. Pigné. Information Gathering and Sharing in DT-MANETs. Demonstration session during the International Conference on Pervasive Services (ICPS'2008). 6-10 July 2008. Sorrento, Italy.
  • P. Bouvry and F. Guinand and K. Lavangnananda and A. Piyatumrong. Trusted Spanning Trees for Delay Tolerant AdHoc Networks. To appear in the proceedings of the IEEE Conference on Soft Computing in Industrial Applications (SMCia 2008). June 25-27, 2008. Muroran, Japan.   BibTeX

    Abstract:
    Delay Tolerant Networks (DTN) are an extension of Mobile Ad-Hoc Networks (MANETs). Global knowledge in DTNs cannot be obtained or guaranteed due to their dynamicity, decentralized nature and non-permanent structure. Managing such networks optimally is very difficult, if not impossible. Trust management in such networks receives much attention recently due to their potential application. One solution for managing information within DTNs consists in building and maintaining spanning forests. DA-GRS is a local computation based model for the description of decentralized algorithms designed for dynamic distributed environments like are Delay-Tolerant MANETs (DTMs). DA-GRS proposes a framework for building and maintaining a spanning forest in such an environment. This work introduces the notion of trust into DA-GRS resulting in T-DA-GRS algorithm. Three cost functions are suggested as means to assess robustness of trusted spanning trees. T-DA-GRS is also further improved by incorporating greedy algorithm to become T-GDA-GRS. These algorithms were tested with four different networks generated by a DTM simulator known as Madhoc. Efficiency of these algorithms is compared with optimal values.

  • E. Alba and P. Bouvry and G. Danoy and F. Guinand and L. Hogie. Simulating Realistic Mobility Models for Large Heterogeneous MANETs. Poster during the 9th ACM/IEEE International Symposium on Modeling, Analysis and Simulation of Wireless and Mobile Systems. Torremolinos, Spain. October 2-6, 2006. 12 pages.   BibTeX.

    Abstract:
    Mobile ad hoc networks (MANETs) are composed of communicating mobile devices capable of spontaneously interconnecting without any pre-existing infrastructure. The wide spread of mobile devices (i.e. phones, PDAs, laptops) enables the deployment of metropolitan ad hoc networks, referred to as MobileMANs. Until recently, MobileMAN simulation suffered from a lack of appropriate tools. Therefore a new class of simulators dedicated to MobileMANs is appearing. This paper presents Madhoc, a MANETs simulator which belongs to this class. In addition to providing particular models for the simulation of numerous nodes evolving in a metropolitan environment, Madhoc comes with appropriate tools for the development and the monitoring of ad hoc applications. Madhoc's appliations are presented.

  • P. Bouvry and F. Guinand and L. Hogie and M. Seredynsky. A Bandwidth-Efficient Broadcasting Protocol for Mobile Multi-Hop Ad Hoc Networks. In proceedings of the Fifth IEEE International Conference on Networking and the International Conference on Systems (ICN / ICONS / MCL 2006). Page 71. April, 23-29 2006. Mauritius.   BibTeX.

    Abstract:
    This paper presents a new broadcasting protocol called Delayed Flooding with Cumulative Neighborhood (DFCN) designed for wireless ad hoc networks. DFCN enables bandwidth-efficient broadcasting in wide area network composed of large number of mobile devices. The protocol was validated through simulation which proved its efficiency and cost-effectiveness. Comparison with other well known protocols has shown that the proposed protocol outperforms them in such terms as a number of emissions and redundant receptions.

  • L. Hogie and F. Guinand and P. Bouvry. An Overview of MANETs Simulation. Electronic Notes in Theoretical Computer Science, vol. 150, pages 81-101, 2006. This volume corresponds to the proceedings of MTCoord'05, Workshop on Methods and Tools for Coordinating Concurrent, Distributed and Mobile Systems. April 20-23, 2005. Namur, Belgium.   BibTeX.

    Abstract:
    Mobile Ad hoc NETworks (MANETs) are dynamic networks populated by mobile stations. Stations in MANETs are usually laptops, PDAs or mobile phones. These devices feature Bluetooth and/or IEEE 802.11 (WiFi) network interfaces and communicate in a decentralized manner. Mobility is a key feature of MANETs. Because of their high cost and their lack of flexibility of such networks, experimentation is mostly achievable through simulation. Numerous tools exist for MANETs simulation, including ns-2 and GloMoSim which are the two most popular ones. This paper provides a State of the Art of MANETs simulators and associated simulation techniques. First it gives an overview of the domain. Then it provides a map of the main characteristics that MANETs simulation tools should feature and the current support of these. Finally, a description for each simulator is provided, including an explanation of what make them appealing solutions.

  • L. Hogie and F. Guinand and P. Bouvry. A Heuristic Strategy for Efficient Broadcasting in Metropolitan Ad Hoc Networks. LNAI, Volume 3213, pages 727-733, proceedings of the 8th International Conference on Knowledge-Based Intelligent Information and Engineering Systems (KES'04), Wellington, New-Zealand, September 22-24, 2004.   BibTeX

    Abstract:
    The recent rise of wireless networking technologies let us envision the metropolitan ad hoc network (MAHN). MAHNs are built on-the-fly by user's mobile stations which communicate in a peer-to-peer mode. Communications within the network hence do not rely on any fixed infrastructure. This paper tackles the message broadcasting problem in such networks. Unlike most of the studies on this issue, we do consider that the network is very likely to be split in several partitions and that the steady mobility of the nodes allows the broadcasting process to reach previously inaccessible partitions. This article presents the Delayed Flooding with Cumulative Neighbourhood (DFCN) algorithm as an algorithm for message broadcasting on metropolitan ad hoc networks and, through experiments, analyses its performance.

Dynamic Graphs and Complex Systems

  • C. Bertelle and A. Dutot and F. Guinand and D. Olivier. Organization Detection for Dynamic Load Balancing in Individual-based Simulations. Multiagent and Grid Systems. Volume 3, Number 1, pages 142-163. 2007.   BibTeX

    Abstract:
    Large-scale individual-based simulations can benefit a lot from high performance computing environments. The benefit that can be hopped for depends greatly on a good load distribution among the processing resources together with the minimization of the communication overhead. However, minimizing both idle time and communication overhead requires the search for a trade-off. Inspired by complex systems, the approach described in this paper aims at minimizing the volume of data exchanged over the networks between tasks of a distributed applications, while balancing the load between available computing resources. The method lies on the trail-laying trail-following paradigm used in algorithms based on artificial ants.

  • S. Balev and F. Guinand and Y. Pigné Maintaining Shortest Paths in Dynamic Graphs. In proceedings of the International Conference on Non-Convex Programming: Local and Global Approaches Theory, Algorithms and Applications (NCP'O7). December 17-21, 2007. Rouen, France. abstract BibTeX

    Abstract:
    This paper deals with the problem of finding and maintaining shortest paths networks where the topology evolves with the time. A lot of applications may refer to the Dynamic Shortest Path Problem (DSPP) and a lot of algorithms have been proposed these last years to cope with this problem. A classification is made according to the way these methods deal with the evolution during the time of the networks. Two contributions are proposed. One in the fiels of re-optimization processes, and the other in the field of routing in mobile ad hoc networks.

  • A. Dutot, F. Guinand, D. Olivier and Y. Pigné. GraphStream: A Tool for bridging the gap between Complex Systems and Dynamic Graphs. In proceedings of EPNACS: Emergent Properties in Natural and Artificial Complex Systems, Satellite conference within the 4th European Conference on Complex Systems. Pages 63-72. October 4-5, 2007. Dresden, Germany.   BibTeX

    Abstract:
    The notion of complex systems is common to many domains, from Biology to Economy, Computer Science, Physics, etc. Often, these systems are made of sets of entities moving in an evolving environment. One of their major characteristics is the emergence of some global properties stemmed from local interactions between the entities themselves and between the entities and the environment. The structure of these systems as sets of interacting entities leads researchers to model them as graphs. However, their understanding requires most often to consider the dynamics of their evolution. It is indeed not relevant to study some properties out of any temporal consideration. Thus, dynamic graphs seem to be a very suitable model for investigating the emergence and the conservation of some properties.

  • A. Dutot, F. Guinand, D. Olivier and Y. Pigné. On the Decentralized Dynamic Graph-Coloring Problem. In proceedings of COSSOM: Complex Systems and Self-Organization Modelling. Satellite workshop within European Simulation and Modelling Conference (ESM'2007). Pages 259-261. October 22-24, 2007. St Julian's, Malta. Abstract BibTeX

    Abstract:
    The central topic of this contribution is the conception of decentralized methods for dynamic graph processing. The approach is illustrated on the well-known graph coloring problem. Proposed dynamic methods compared favorably with static greedy algorithms like Welsh-Powell.

  • F. Guinand and Y. Pigné. Problem Solving and Complex System. Chapter 3 of the book (pages 55-88): Emergent Properties in Natural and Artificial Dynamical Systems published by Springer in the book series Understanding Complex Systems, co-edited by A. Alaoui and C. Bertelle (BibTeX of the book).   BibTeX

    Abstract:
    The observation and modeling of natural Complex Systems (CSs) like the human nervous system, the evolution or the weather, allows the definition of special abilities and models reusable to solve other problems. For instance, Genetic Algorithms or Ant Colony Optimizations are inspired from natural CSs to solve optimization problems. This paper proposes the use of ant-based systems to solve various problems with a non assessing approach. This means that solutions to some problem are not evaluated. They appear as resultant structures from the activity of the system. Problems are modeled with graphs and such structures are observed directly on these graphs. Problems of Multiple Sequences Alignment and Natural Language Processing are addressed with this approach.

Bio-Inspired Methods - Ant Algorithms

  • F. Guinand. Nature-Inspired Approaches for Complex Biological Systems. In proceedings of EURO 2007. Prague, Czech Republic, july 2007.

    Abstract:
    Complex biological systems are made of large numbers of interacting heterogeneous entities evolving in an open environment crossed by flows. Such systems exhibit global properties obtained solely from the interactions between entities. The detection of these properties is sometimes very close to some optimization problems with two additional constraints: the problem is dynamic and it is unlikely to find a relevant evaluation function. It seems, however, that Nature may help us since decentralized nature-inspired approaches can produce solutions for these kinds of problems.

  • F. Guinand and Y. Pigné. An Ant-based Model for Multiple Sequence Alignment. In Ivan Lirkov, Svetozar Margenov, and Jerzy Wasniewski (editors) Proceedings of the 6th SIAM International Conference on "Large-Scale Scientific Computations" (LSSC'07). Springer-Verlag, LNCS vol. 4818, pages 553-560. June 5-7, 2007. Sozopol, Bulgaria. BibTeX

    Abstract:
    Multiple sequence alignment is a key process in today's biology, and finding a relevant alignment of several sequences is much more challenging than just optimizing some improbable evaluation functions. Our approach for addressing multiple sequence alignment focuses on the building of structures in a new graph model: the factor graph model. This model relies on block-based formulation of the original problem, formulation that seems to be one of the most suitable ways for capturing evolutionary aspects of alignment. The structures are implicitly built by a colony of ants laying down pheromones in the factor graphs, according to relations between blocks belonging to the different sequences.

  • C. Bertelle and A. Dutot and F. Guinand and D. Olivier. Organization Detection Using Emergent Computing. International Transactions on Systems Science and Applications. Volume 2, Number 1, pages 61-69. 2006.   BibTeX

    Abstract:
    Organization is a central concept in systems. In this paper an ant algorithm for detecting organizations is presented. In a discrete-time context, at each time-step, an organization corresponds to a set of closely interacting entities in a system. This system is mapped to a graph where nodes represent entities and edges represent interrelations. Several colonies of ants compete, and inside each colony, ants collaborate in order to colonize the graph. Detected organizations emerge from the global behavior of the ants. The proposed approach is compared to other methods on a graph where the organizations are already known. It is then tested on two real world graphs studied in the related litterature.

  • A. Cardon, A. Dutot, F. Guinand and D. Olivier. Competing Ants for Organization Detection Application to Dynamic Distribution. Chapter 2 of the book (pages 27-54): Emergent Properties in Natural and Artificial Dynamical Systems published by Springer in the book series Understanding Complex Systems, co-edited by A. Alaoui and C. Bertelle (BibTeX of the book).   BibTeX

    Abstract:
    A simulation application may be modeled as a set of interacting entities within an environment. Such applications can be represented as a graph with a one-to-one mapping between vertices and entities and between edges and communications. As for classical applications, performances depend directly on a good load balancing of the entities between available computing devices and on the minimization of the impact of the communications between them. However, both objectives are contradictory and good performances may be achieved if and only if a good trade off is found. Our method for finding such a trade off leans on a bio-inspired method. We use competitive colonies of numerical ants, each one depositing colored pheromones, to find organizations of highly communicating entities.

  • F. Guinand and Y. Pigné. Problem Solving and Complex System. Chapter 3 of the book (pages 55-88): Emergent Properties in Natural and Artificial Dynamical Systems published by Springer in the book series Understanding Complex Systems, co-edited by A. Alaoui and C. Bertelle (BibTeX of the book).   BibTeX

    Abstract:
    The observation and modeling of natural Complex Systems (CSs) like the human nervous system, the evolution or the weather, allows the definition of special abilities and models reusable to solve other problems. For instance, Genetic Algorithms or Ant Colony Optimizations are inspired from natural CSs to solve optimization problems. This paper proposes the use of ant-based systems to solve various problems with a non assessing approach. This means that solutions to some problem are not evaluated. They appear as resultant structures from the activity of the system. Problems are modeled with graphs and such structures are observed directly on these graphs. Problems of Multiple Sequences Alignment and Natural Language Processing are addressed with this approach.

  • M. Lafourcade, F. Guinand. Algorithme de fourmis pour le traitement de la langue naturelle, Actes du Congrès de la Société Française de Recherche Opérationnelle et Aide à la Décision (ROADEF'05). Pages 239-240. 14-16 février 2005. Tours, France.   BibTeX

  • C. Bertelle, A. Dutot, F. Guinand, D. Olivier. Colored Ants for Distributed Simulations, Marco Dorigo, Mauro Birattari, Christian Blum, Luca Maria Gambardella, Francesco Mondada, Thomas Stützle (Eds.): Ant Colony Optimization and Swarm Intelligence, 4th International Workshop, ANTS 2004, Brussels, Belgium, September 5-8, 2004, Proceedings. LNCS Volume 3172, Springer 2004, ISBN 3-540-22672-9, pages 326-333, 2004.   BibTeX

    Abstract:
    A simulation may be modeled as a set of interacting entities within an environment. Such applications can be represented by a graph which evolves with a one-to-one mapping between vertices and entities and between edges and communications. As for classical applications, performances depend directly on a good load balancing of the entities between available computing devices and on the minimization of the impact of the communications between them. However, both objectives are contradictory and good performances may be achieved if and only if a good trade-off is found. Our method for finding such a trade-off leans on an extension of the ant-based approach. We use competing colonies of ants, each depositing distinctly colored pheromones, to find clusters of highly communicating entities. Ants are attracted by communications and their own colored pheromones, while repulsion interactions between colonies allow to preserve a good distribution. Colors are mapped to processing resources and colored entities are placed on them, allowing to put highly communicating clusters on the same processing resource without overloading it. Several graphs categories (grids, scale-free, random, static or not) are studied.

  • C. Bertelle, A. Dutot, F. Guinand, and D. Olivier. Color ant population algorithm for dynamic distribution in simulation, Proceedings of ESS 2003, Delft, Netherland, October, pages 47-54, 2003.   BibTeX

    Abstract:
    Most distributed simulations are applications composed of numerous mobile communicating entities that continuously evolve. Such entities are organized or organize themselves in groups or societies of cooperating agent or processes. To keep these simulations efficient, it may be necessary to migrate entities of highly communicating groups so that they remain close, ideally on the same processing unit, while at the same time, we need to maintain a reasonable load for each processor. We have previously proposed a method to hint migration of entities making a trade-off between communication and load-balancing based on a variant of ant algorithms. We use a dynamic communication graph to model distributed simulations where vertices represent entities and edges communications. Several colonies of ants, each of a distinct color representing a computing resource, compete to mark vertices of the graph using colored pheromones. A color change on a vertex hints the entity it represents to migrate on the corresponding processor. In some cases, the solution obtained is not satisfying. We try to show in this paper the reasons and to give improvements to solve it.

  • C. Bertelle, A. Dutot, F. Guinand, and D. Olivier. Dynamic placement using ants for objects based simulations, DOA 2003, Catania, Italy, LNCS Volume 2888, pages 1263-1274, 2003.   BibTeX

    Abstract:
    A distributed application may be considered as a set of interacting entities continuously evolving. Such application can be modeled as a graph with one-to-one mappings between vertices and entities and between edges and communications. Performances depend directly on a good load balancing of the entities between available computing devices and on the minimization of the impact of the communications between them. However, both objectives are contradictory and good performances are achieved if and only if a good tradeoff is found. Our method for finding such a tradeoff is new and based on colored ant colonies. Each computing resource is associated to one ant colony characterized by a color, allowing an implicit consideration of the load balancing constraint. Then, using colored pheromones, ants are just seeking for communicating structures. The method operates on graphs which structural and numerical parameters may change dynamically during the execution.

  • C. Bertelle, A. Dutot, F. Guinand, D. Olivier. Simulations distribuées par un algorithme fourmi, Actes de RenPar 2003, La Colle sur Loup, France, October 15-17, pages 56-63, 2003.   BibTeX

    Abstract:
    On considère des simulations distribuées sur un ensemble de ressources de calcul. Elles sont composées d'un grand nombre d'entités informatiques communicantes en perpétuelle évolution (objets, acteurs, agents...). A l'aide d'un algorithme fourmi nous détectons les organisations présentes afin de rapprocher par migration les entités qui les constituent, en respectant l'équilibrage de charge. Nous utilisons un graphe dynamique de communication pour modéliser les applications. Plusieurs colonies de fourmis, chacune d'une couleur distincte représentant une ressource (ex : un processeur), entrent en compétition pour marquer les sommets du graphe en utilisant des phéromones colorées. Lorsque la couleur d'un sommet change, cela signifie que l'entité correspondante peut éventuellement migrer, ceci en fonction des contraintes de l'application.

  • C. Bertelle and A. Dutot and F. Guinand and D. Olivier. DIMANTS: a Distributed Multi-Castes Ant System, Proceedings of BixMAS workshop, held during AAMAS conference, Bologna, Italy, July 15-19, 2002. Pages 1-7.   BibTeX

    Abstract:
    The problem of DNA sequencing by hybridation methods is considered in this paper when all kinds of errors are taken into account. A distributed method based on dynamic organizations of reactive agents is used in an environment composed by a SBH-graph (Sequencing by Hybridation). Explorations of such graphs are studied with contraints representing the possible errors comming from the DNA sequencing operation. With these explorations, we finally find a set of sequences that we try to minimize and which have to containt the original sequence.

  • C. Bertelle and A. Dutot and F. Guinand and D. Olivier. DNA-Sequencing by Hybridization based on a Multi-Castes Ant System, NETTAB 2002: Workshop on Agents in Bioinformatics, 2002. This poster was also presented as a regular talk during BixMAS Workshop. poster.

Bioinformatics

  • F. Guinand and Y. Pigné. An Ant-based Model for Multiple Sequence Alignment. In Ivan Lirkov, Svetozar Margenov, and Jerzy Wasniewski (editors) Proceedings of the 6th SIAM International Conference on "Large-Scale Scientific Computations" (LSSC'07). Springer-Verlag, LNCS vol. 4818, pages 553-560. June 5-7, 2007. Sozopol, Bulgaria. BibTeX

    Abstract:
    Multiple sequence alignment is a key process in today's biology, and finding a relevant alignment of several sequences is much more challenging than just optimizing some improbable evaluation functions. Our approach for addressing multiple sequence alignment focuses on the building of structures in a new graph model: the factor graph model. This model relies on block-based formulation of the original problem, formulation that seems to be one of the most suitable ways for capturing evolutionary aspects of alignment. The structures are implicitly built by a colony of ants laying down pheromones in the factor graphs, according to relations between blocks belonging to the different sequences.

  • A. Rabia, F. Guinand. Sequençage par hybridation : modélisation et reconstruction FRANCORO 2004, Fribourg, Suisse, 18-21 Août 2004. abstract  BibTeX

  • S. Lemoulan, R. Marion, F. Duchaussoy, R. Charlionet, F. Guinand, P. Ducrotté, P. Déchelotte, S. Thébault. Analyse comparative fonctionnelle des effets de la glutamine sur le protéome intestinal dans la lignée cellulaire HCT-8, 5e Journées Francophones de Nutrition, 2004.

  • S. Thébault, S. Lemoulan, F. Duchaussoy, R. Marion, F. Guinand, R. Charlionet, P. Ducrotté, P. Déchelotte. Proteome Analysis of Glutamin-Treated Human Intestinal Epithelial Cell Line HCT-8, 6th SIENA Meeting from Genome to Proteome - Biomarker Discovery \& Proteome Imaging, 2004.

  • S. Thébault, S. Lemoulan, R. Marion, F. Duchaussoy, F. Guinand, R. Charlionet, P. Ducrotté, P. Déchelotte. Proteome Analysis of Glutamin-Treated Human Intestinal Epithelial Cell Line HCT-8, 26th European Society of Enteral and Parenteral Nutrition Congress, 2004.

  • F. Guinand, L. Mouchard, A. Rabia. A new model for sequencing by hybridization, RECOMB 2003: Currents in computational molecular biology. Berlin, Germany, April 10-13, 2003. Poster session. Poster booklet pages 11-12.   BibTeX

  • J. Blazewicz and P. Formanowicz and F. Guinand and M. Kazsprzak. Heuristic Managing Errors for DNA-Sequencing, Bioinformatics, Volume 18, Issue 5, pages 652-660, 2002.   BibTeX

    Abstract:
    Motivation: A new heuristic algorithm for solving DNA sequencing by hybridization problem with positive and negative errors.
    Results: A heuristic algorithm providing better solutions than algorithms known from the literature based on tabu search method.

  • C. Bertelle and A. Dutot and F. Guinand and D. Olivier. DIMANTS: a Distributed Multi-Castes Ant System, Proceedings of BixMAS workshop, held during AAMAS conference, Bologna, Italy, July 15-19, 2002. Pages 1-7.   BibTeX

    Abstract:
    The problem of DNA sequencing by hybridation methods is considered in this paper when all kinds of errors are taken into account. A distributed method based on dynamic organizations of reactive agents is used in an environment composed by a SBH-graph (Sequencing by Hybridation). Explorations of such graphs are studied with contraints representing the possible errors comming from the DNA sequencing operation. With these explorations, we finally find a set of sequences that we try to minimize and which have to containt the original sequence.

  • C. Bertelle and A. Dutot and F. Guinand and D. Olivier. DNA-Sequencing by Hybridization based on a Multi-Castes Ant System, NETTAB 2002: Workshop on Agents in Bioinformatics, 2002. This poster was also presented as a regular talk during BixMAS Workshop. poster.

  • F. Guinand, G. Parmentier and D. Trystram. Integration of Multiple Alignment and Phylogeny Reconstruction, European Conference on Computational Biology (ECCB'02), Saarbrücken, Germany, October 6-9, 2002. Poster session. Poster booklet page 78. 2002.

  • F. Guinand, L. Mouchard and A. Rabia. Impact of repetitions on Sequencing By Hybridization, European Conference on Computational Biology (ECCB'02), Saarbrücken, Germany, October 6-9, 2002. Poster session. Poster booklet page 77. 2002.

  • D. Lavenier and H. Leroy and M. Hurfin and R. Andonov and L. Mouchard and F. Guinand. Le projet GénoGRID : une grille expérimentale pour la génomique, Actes des Journées Ouvertes Biologie, Informatique et Mathématiques (JOBIM 2002), Saint-Malo France, 10-12 Juin, pages 27-31, 2002.

  • F. Guinand and G. Parmentier and D. Trystram. Construction of Phylogenetic Trees on Parallel Clusters, Proceedings of the 4th Parallel Processing and Applied Mathematics Conference, Naleczow, Poland, September 4-11 2001. LNCS Volume 2328, pages 218-227, 2001.

  • F. Guinand. Parallel Algorithms for Molecular Biology, Proceedings of ISThmus 2000, Poznan Poland, pages 69-76, 2000.

  • J. Blazewicz and P. Formanowicz and F. Guinand and M. Kasprzak. A Parallel Approximation Algorithm for DNA-Sequencing, ECCO XII, Bendor Island, France, 1999.

Scheduling for Distributed and Parallel Systems

  • M. Drozdowski, M. Lawenda and F. Guinand. Scheduling Multiple Divisible Loads. International Journal of High Performance Computing Applications, Volume 20, Number 1, pages 19-30, 2006 (DOI: 11.1177/1094342006061879).   BibTeX

    Abstract
    In this paper we study the scheduling of multiple divisible loads on a star network of processors. We show that this problem is computationally hard. Special cases solvable in polynomial time are identified.

  • F. Guinand, A. Moukrim, E. Sanlaville. Sensitivity Analysis of Tree Scheduling on Two Machines with Communication Delays, Parallel Computing, Volume 30, pages 103-120, 2004. DOI: 10.1016/S0167-8191(03)00091-7   BibTeX

    Abstract
    This paper presents a sensitivity analysis for the problem of scheduling trees with communication delays on two identical processors, to minimize the makespan. Tasks are supposed to have unit execution time (UET), and the values associated to communication delays are supposed unknown before the execution. The paper compares the optimal makespans with and without communication delays. The results are used to obtain sensitivity bounds for algorithms providing optimal schedules for graphs with unit execution and communication times (UECT). The notion of processor-ordered schedules, for two-processor systems, is introduced. It describes schedules in which all communications are oriented from one processor to the other. It is shown that these schedules are dominant for unit delays, for zero delays, but not for delays of less than or equal to one. We establish that algorithms building optimal processor-ordered schedules for image graphs admit an absolute sensitivity bound equal to the difference between the maximum and the minimum actual communication delays: W-W* ≤ Commax-Commin (where W denotes the makespan of the schedule and W* the optimal schedule). This bound is tight.

  • A. Moukrim and E. Sanlaville and F. Guinand. Parallel Machine Scheduling with Uncertain Communication Delays, RAIRO Operations Research, Volume 37, Issue 1, pages 1-16, 2003. DOI: 10.1051/ro:2003011   BibTeX

    Abstract
    This paper is concerned with scheduling when the data are not fully known before the execution. In that case computing a complete schedule off-line with estimated data may lead to poor performances. Some flexibility must be added to the scheduling process. We propose to start from a partial schedule and to postpone the complete scheduling until execution, thus introducing what we call a stabilization scheme. This is applied to the m machine problem with communication delays: in our model an estimation of the delay is known at compile time; but disturbances due to network contention, link failures, ... may occur at execution time. Hence the processor assignment and a partial sequencing on each processor are determined off-line. Some theoretical results for tree-like precedence constraints and an experimental study show the interest of this approach compared with fully on-line scheduling.

  • A. Moukrim, F. Guinand, E. Sanlaville. Sensitivity Snalysis of Scheduling UECT Trees on Two Processors, 8th International Workshop on Project Management and Scheduling (PMS 2002), Valencia, Spain, April 3-5, 2002. An extended version of this work was published in Parallel Computing in 2004.

  • J. Blazewicz and F. Guinand and B. Penz and D. Trystram. Scheduling Complete Trees on 2 Uniform Processors with Integer Speed Ratios and Communication Delays, Parallel Processing Letter, Volume 10, Issue 4, pages 267-277, 2000.   BibTeX

    Abstract
    In this paper, we present an algorithm that builds optimal schedules for complete in-trees on two uniform processors, with arbitrary integer speed ratios, in the presence of communication delays.

  • F. Guinand and D. Trystram. Optimal Scheduling of UECT Trees on 2 Processors, RAIRO (Operation Research), Volume 34, Issue 2, pages 131-144, 2000. DOI: 10.1051/ro:2000101   BibTeX

    Abstract
    In this paper, we present a new linear time algorithm for scheduling UECT (Unit Execution and Communication Time) trees on two identical processors. The chosen criterion is the makespan. The used strategy is based on clustering of tasks. We show that this algorithm builds optimal schedules. Some extensions are discussed for non UECT tasks.

  • F. Guinand. Sensitivity Analysis for Deterministic Scheduling, European Chapter on Combinatorial Optimization (ECCO XIII), Capri, Italy, May 18-20, 2000.

  • J. Blazewicz and M. Drozdowski and F. Guinand and D. Trystram. Scheduling a Divisible Task in a 2-Dimensional Toroïdal Mesh, Discrete Applied Mathematics, Volume 94, Issues 1-3, pages 35-50, 1999.   BibTeX

    Abstract:
    In this paper, a problem of scheduling an arbitrarily divisible task is considered. Taking into account both communication delays and computation time we propose a scheduling method which minimizes total execution time. We focus on two dimensional processor networks assuming a circuit-switching routing mechanism. The scheduling method uses a scattering scheme proposed in Peters and Syska (IEEE Trans. Parallel Distributed Systems 7(3) (1996) 246-255) to distribute parts of the task to processors in a minimum time. We show how to model and solve this problem with a set of algebraic equations. A solution of the latter allows one to analyze the performance of the network depending on various actual parameters of the task and the parallel machine. Though the method is defined for a particular architecture and scattering scheme it can be generalized to analyze other architectures of parallel computer systems.

  • J.-Y. Colin and P. Colin and F. Guinand and M. Nakechbandi. Scheduling Parallel Programs with Communication Delays on Multi-Level Virtual Distributed Systems, In Hamid R. Arabnia (Ed.): Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA 1999), June 28 - July 1, 1999, Las Vegas, Nevada, USA. CSREA Press 1999, ISBN 1-892512-15-7. Pages 2608-2614. 1999.   BibTeX

    Abstract:
    A set of tasks has to be scheduled on the parallel identical processors of the clusters of a multi-levels distributed memory multiprocessor, subject to precedence constraints and small communication delays inside the lowest-level clusters. The architecture model includes networks of shared memory multiprocessors. In this paper, we present a new critical-path like algorithm that nds an optimal solution to this new problem in polynomial time, if task duplication is allowed and the number of available processors is not limited. The solution found is an earliest schedule that spreads the tasks between the multi-levels clusters and the processors.

  • A. Moukrim and E. Sanlaville and F. Guinand. Scheduling With Communication Delays and On-Line Disturbances, EuroPar'99, LNCS Volume 1685, pages 350-357, 1999. ps  BibTeX An enhanced version of this work was published in RAIRO in 2003.

    Abstract:
    This paper considers the problem of scheduling tasks on multiprocessors. Two tasks linked by a precedence constraint and executed by two different processors must communicate. The resulting delay depends on the tasks and on the processor network. In our model an estimation of the delay is known at compile time; but disturbances due to network contention, link failures,... may occur at execution time. Algorithms computing separately the processor assignment and the sequencing on each processor are considered. We propose a partially on-line scheduling algorithm based on critical paths to cope with the possible disturbances. Some theoretical results and an experimental study show the interest of this approach compared with fully on-line scheduling.

  • F. Guinand and C. Rapine and D. Trystram. Worst-Case Analysis of Algorithms for Scheduling UECT Trees on m Processors, IEEE Transactions on Parallel and Distributed Systems, Volume 8, Issue 10, pages 1085-1086, 1997. pdf (extended version)  BibTeX

    Abstract:
    This paper is devoted to the analysis of an algorithm proposed by Lawler [Law93] for scheduling unit execution times trees on m identical processors in the presence of communication delays. Lawler proved that a schedule computed by his algorithm exceeds an optimal solution by no more than (m - 2) time units. We improve this bound by a factor of 2 and propose a family of trees which reaches it for any number of processors.

  • E. Bampis and F. Guinand and D. Trystram. Some Models for Scheduling Parallel Programs with Communication Delays, Discrete Applied Mathematics, Volume 72, Issues 1-2, pages 5-24, 1997.   BibTeX

    Abstract:
    The aim of this paper is to present and analyze models for designing parallel programs. In the context of some extensions of the most popular execution models (precedence graphs, dataflow, PRAM), we describe scheduling techniques which take into account the communication delays. We illustrate all these models by two families of representative precedence graphs, namely, grids and complete trees.

  • E. Bampis and F. Guinand and D. Trystram. Minimizing the Overhead for some Tree-Scheduling Problems, European Journal of Operational Research, Volume 94, Issue 2, pages 261-270, 1996.   BibTeX

    Abstract:
    This paper is devoted to the study of tree-scheduling problems within the execution model described by Anderson, Beame and Ruzzo. We first prove the NP-completeness of the problem of minimizing the overhead for scheduling trees on m processors, and then we propose an algorithm that provides optimal schedules when complete trees are considered.

  • J. Blazewicz and P. Bouvry and F. Guinand and D. Trystram. Scheduling Complete Intrees on 2 Uniform Processors with Communication Delays, Information Processing Letters, Volume 5, Issue 58, pages 255-263, 1996.   BibTeX

    Abstract:
    We present an optimal algorithm for scheduling a complete k-at-y tree on two uniform processors of different speeds in order to minimize schedule length. We consider the basic case of unit standard execution times and unit communication times.