Almost disjoint spanning trees

International audience; In this extended abstract, we only consider connected graphs. Let k ≥ 2 be an integer and T 1 ,. .. , T k be spanning trees in a graph G. A vertex is said to be an inner vertex in a tree T if it has degree at least 2 in T. We denote by I(T) the set of inner vertices of tree T. The spanning trees T 1 ,. .. , T k are completely independent spanning trees if any vertex from G is an inner vertex in at most one tree among T 1 ,. .. , T k and the trees T 1 ,. .. , T k are pairwise edge-disjoint. Completely independent spanning trees were introduced by Hasunuma [4] and then have been studied on different classes of graphs, such as underlying graphs of line graphs [4], maxim…

A Restricted-Weakly Connected Dominating Set for Role Assignment in a Multichannel MAC for Wireless Mesh Network

International audience; We propose an efficient way of constructing the wireless mesh structure associated with Molecular MAC, a multichannel access method designed for efficient packet forwarding. We base our role assignment on a restricted Weakly Connected Dominating Set structure. After presenting a formal definition of the role assignment problem, we prove its NP-completeness. Then, we propose a centralized 2-approximation algorithm that maximizes the sum of radio link capacities in the molecular structure. Finally, we extend this protocol so that it can operate in a distributed way still providing the same guarantee. This distributed protocol is self-stabilizing thus robust to topology…

A Novel Multi-hop Broadcasting Method for VANETs Based on Autonomic Computing Paradigm

One of the three best papers, Selected for the Annals of Telecommunications journal; International audience; Broadcasting is widely used in Vehicular Ad hoc Networks (VANETs) but it is hard to achieve efficiently since it depends on the network density, i.e. may cause network congestion if the protocols are not well designed. This paper introduces a novel Autonomic Dissemination Method (ADM) which delivers messages in accordance with given priority and density levels. The proposed approach is based on two steps: an offline optimization process and an online adaptation to the network characteristics. The aim is to make effective use of radio resources when there are many messages to send imu…

Almost disjoint spanning trees: relaxing the conditions for completely independent spanning trees

International audience; The search of spanning trees with interesting disjunction properties has led to the introduction of edge-disjoint spanning trees, independent spanning trees and more recently completely independent spanning trees. We group together these notions by dening (i, j)-disjoint spanning trees, where i (j, respectively) is the number of vertices (edges, respectively) that are shared by more than one tree. We illustrate how (i, j)-disjoint spanning trees provide some nuances between the existence of disjoint connected dominating sets and completely independent spanning trees. We prove that determining if there exist two (i, j)-disjoint spanning trees in a graph G is NP-comple…

Recherche d'arbres couvrants complètement indépendants dans des graphes réguliers

International audience; Nous étudions l'existence de $r$ arbres couvrants complètement indépendants dans des graphes $2r$-réguliers et $2r$-connexes, et énonçons des conditions nécessaires à leur existence. Nous déterminons le nombre maximum d'arbres dans les produits cartésiens d'une clique et d'un cycle. Nous montrons que ce nombre n'est pas toujours $r$.

Approximation algorithm for constrained coupled-tasks scheduling problem

International audience; We tackle the makespan minimization coupled-tasks problem in presence of compatibility constraints. In particular, we focus on stretched coupled-tasks, i.e. coupled-tasks having the same sub-tasks execution time and idle time duration. In such context, we propose some complexity results according to several parameters and we design an efficient polynomial-time approximation algorithm.

De l'existence d'arbres couvrants complètement disjoints dans les réseaux sans fil

International audience; Les arbres couvrants complètement disjoints (CIST) présentent un réel intérêt dans les réseaux, aussi bien pour des opérations d'augmentation de robustesse que d'équilibrage de charge, de fractionnement du trafic, ...Leur étude théorique a montré de nombreux challenges liés à leur calcul et leur quantification. Nous proposons ici une formulation ILP originale et montrons par des résultats de simulation sur des modèles représentatifs des réseaux sans fil que plusieurs CIST peuvent être calculés lorsque la densité du réseau est suffisamment élevée. Nous montrons que dans ce type de réseaux, la densité et le nombre de noeuds sont proportionnels au nombre de CIST qui peu…

WiseEye: A Platform to Manage and Experiment on Smart Camera Networks

International audience; Embedded vision is probably at the edge of phenomenal expansion. The smart cameras are embedding some processing units which are more and more powerful. Last decade, high-speed image processing can be implemented on specifically designed architectures [1] nevertheless the designing time of such systems was quite high and time to market therefore as well. Since, powerful chips (i.e System On Chip) and quick prototyping methodologies are contently emerging [2],[3],[4] and enable more complex algorithms to be implemented faster. Moreover, smart cameras which are embedding flexible and powerful multi-core processors or Graphic Processors Unit (GPU) are now available and …

Capacity and Energy-Consumption Optimization for the Cluster-Tree Topology in IEEE 802.15.4

International audience; 802.15.4 proposes to use a cluster-tree hierar- chy to organize the transmissions in Wireless Sensor Networks. In this letter, we propose a framework to analyze formally the capacity and the energy consumption of this structure. We derive a Mixed Integer Linear Programming (MILP) formulation to obtain a topology compliant with the standard. This formulation provides the optimal solution for the network capacity: this con- stitutes an upper bound for any distributed algorithms permitting to construct a cluster-tree. This framework can also be used to evaluate the capacity and to compare quantitatively different cluster-tree algorithms.

Assignment of Roles and Channels for a Multichannel MAC in Wireless Mesh Networks

International audience; A multichannel MAC improves throughput in wireless mesh networks by multiplexing transmissions over orthogonal channels. In this paper, we propose an efficient way for constructing the wireless mesh structure associated with Molecular MAC, a multichannel MAC layer designed for efficient packet forwarding. Molecular MAC outperforms other classical approaches, but requires a specific structure for efficient operation. First, we propose a centralized protocol that provides an upper bound for constructing such a molecular structure through a MILP (Mixed Integer Linear Programming) formulation that maximizes network capacity. Then, we present two distributed self-stabiliz…

Priority Levels Based Multi-hop Broadcasting Method for Vehicular Ad hoc Networks

International audience; This paper deals with broadcasting problem in vehicular ad hoc networks (VANETs). This communication mode is commonly used for sending safety messages and traffic information. However, designing an efficient broadcasting protocol is hard to achieve since it has to take into account some parameters related to the network environment, for example, the network density, in order to avoid causing radio interferences. In this paper, we propose a novel Autonomic Dissemination Method (ADM) which delivers messages in accordance with given priority and density levels. The proposed approach is based on two steps: an offline optimization process and an adaptation to the network …

Some complexity and approximation results for coupled-tasks scheduling problem according to topology

International audience; We consider the makespan minimization coupled-tasks problem in presence of compatibility constraints with a specified topology. In particular, we focus on stretched coupled-tasks, i.e. coupled-tasks having the same sub-tasks execution time and idle time duration. We study several problems in framework of classic complexity and approximation for which the compatibility graph is bipartite (star, chain,. . .). In such a context, we design some efficient polynomial-time approximation algorithms for an intractable scheduling problem according to some parameters.

Completely independent spanning trees in some regular graphs

International audience; Let k >= 2 be an integer and T-1,..., T-k be spanning trees of a graph G. If for any pair of vertices {u, v} of V(G), the paths between u and v in every T-i, 1 <= i <= k, do not contain common edges and common vertices, except the vertices u and v, then T1,... Tk are completely independent spanning trees in G. For 2k-regular graphs which are 2k-connected, such as the Cartesian product of a complete graph of order 2k-1 and a cycle, and some Cartesian products of three cycles (for k = 3), the maximum number of completely independent spanning trees contained in these graphs is determined and it turns out that this maximum is not always k. (C) 2016 Elsevier B.V. All righ…

A New Development Framework for Multi-Core Processor based Smart-Camera Implementations

International audience; The exponential evolution of the smart camera processing performances is directly linked to the improvements on hardware processing elements. Nowadays, high processing performances can be reached considering hardware targets which enables a high level of task parallelism to be implemented. Highly regular tasks are good candidate for a reconfigurable logic implementation and less regular parts of the algorithm could be described on the processor. Meanwhile the prototyping time is related to the selected target and the associated development methodology. The implementation on reconfigurable logic is highly efficient in exploiting the intrinsic task parallelism neverthe…

Autonomic Computing and VANETs