We investigate the problem of computing Completely Independent Spanning Trees (CIST) under a practical approach. We aim to show that despite CISTs are very challenging to exhibit in some networks, they present a real interest in ad-hoc networks and can be computed to enhance the network robustness. We propose an original ILP formulation for CISTs and we show through simulation results on representative network models that several CISTs can be computed when the network density is sufficiently high. These results tend to reinforce the interest of CISTs for various network operations such as robustness, load-balancing, traffic splitting, . . . As an important point, our results show that both the density and the number of nodes have an impact on the number of CISTs that can be found on ad-hoc networks.

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.

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-stabilizing heuristic protocols derived from the protocols for constructing respectively a Maximum Independent Set and a Spanning Tree. We compare the performance of the proposed protocols in terms of network capacity and route length.

A multi-channel MAC is a promising approach for improving network throughput by multiplexing transmissions over orthogonal channels. Molecular MAC has recently adopted this approach by proposing to modify the standard IEEE 802.11 DCF. It requires role and channel assignment to nodes: some of them use a static channel while others dynamically switch to neighbor channels on-demand. To assign roles and channels, we extend the notion of the Weakly Connected Dominating Set, a structure already used in clustering. We adapt it by introducing new constraints to define what we call a reversible WCDS (r-WCDS), which is particularly suitable for Molecular MAC. We propose a divide-and-conquer scheme that partitions the network into clusters with one leader per cluster solving a MILP formulation to assign roles in its cluster. By appropriately defining the roles at the border of clusters, we maintain global connectivity in the r-WCDS. Our simulations show that the performance of our strategy is close to a centralized algorithm.

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 changes. Our simulation results show that the 2-approximation distributed protocol provides an improvement in throughput with respect to other protocols.

This article presents an original tree-based broadcasting technique in known-topology radio networks. The main advantage of our strategy is it can be performed in asynchronous communication models using a protocol without acknowledgment. Considering this strategy, we introduce first results for the problem of finding a broadcasting solution which minimizes the time cost.