Supervision : Lélia BLIN

Arbres couvrants de la théorie à la pratique. Algorithmes auto-stabilisants et Réseaux de Capteurs

Sensor networks are composed of ressources constrained equipments. They have low computing power, low transmission power, low bandwidth, limited storage memory and limited battery life.
In order to integrate such networks in the Internet of things, new protocols were standardized such as RPL protocol (for Routing Protocol for Low Power and Lossy Networks). This protocol is intended to build a logical routing topology called DODAG (for Destination Oriented Directed Acyclic Graph). In this thesis, we discuss the data routing aspect by considering a tree routing topology. Thus, the routing of data is hop by hop from a child to its parent (or from a parent to its child). Optimize the construction of the DODAG is therefore to build a spanning tree in a given constraint. A spanning tree is a connecting structure that maintains a unique path between all pairs of nodes while minimizing the number of used communication links. Furthermore, we consider the constraints of sensor networks, such as a dead battery and the variability of the radio link as transient faults. This leads us to build a covering structure tolerant to transient faults. The self-stabilization is a branch of distributed algorithms that ensures that following one or more transient faults, the system will find itself a correct behavior after a finite time. The objective of this thesis is to propose self-stabilizing algorithms dedicated to sensor networks. The contributions of this thesis are:
In the first part of the thesis, we proposed a self-stabilizing algorithm for the construction of a minimum diameter spanning tree. This construction is natural when we want to minimize the communication delay between a root and all other network nodes. Our algorithm has several advantages. First, our algorithm is limited to memory occupation of O(log n) bits per node, reducing the previous result of an n factor while maintaining a polynomial convergence time. Then, our algorithm is the first algorithm for minimum diameter spanning tree that works as an unfair distribution demon. In other words, we make no restriction on the asynchronous network behavior.
In the second part of the thesis, we are interested in the unstable topology built by RPL protocol (DODAG). Our solution is to place an additional constraint on the number of children a node can accept during the construction of the DODAG. This constraint has the effect of reducing the rate of parent change and consequently to improve the protocol performance in terms of packet delivery rate, delay of communication and power consumption. In addition, we implemented a mechanism to update the information of the downward routes in RPL. Furthermore, our solution has the advantage of not generating overhead because we use existing control messages provided by RPL to implement it. Finally, this contribution is twofold since we validated our solution both by simulations and experiments.

2015-2018 Publications

• 2018
  • L. Blin, F. Boubekeur, S. Dubois : “A Self-Stabilizing Memory Efficient Algorithm for the Minimum Diameter Spanning Tree under an Omnipotent Daemon”, Journal of Parallel and Distributed Computing, vol. 117, pp. 50-62, (Elsevier) (2018)
• 2016
  • F. Boubekeur : “Arbres couvrants de la théorie à la pratique. Algorithmes auto-stabilisants et Réseaux de Capteurs”, thesis, defence 10/12/2016, supervision Blin, Lélia (2016)
  • L. Blin, F. Boubekeur, S. Dubois : “Algorithme auto-stabilisant efficace en mémoire pour la construction d’un arbre couvrant de diamètre minimum”, ALGOTEL 2016 - 18^es Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Bayonne, France (2016)
• 2015
  • L. Baron, F. Boubekeur, R. Klacza, M. Rahman, C. Scognamiglio, N. Kurose, T. Friedman, S. Fdida : “Demo: OneLab: Major Computer Networking Testbeds for IoT and Wireless Experimentation”, MobiCom '15: Proceedings of the 21^st Annual International Conference on Mobile Computing and Networking, Paris, France (2015)
  • F. Boubekeur, L. Blin, R. Leone, P. Medagliani : “Bounding Degrees on RPL”, Proceedings of the 11^th ACM Symposium on QoS and Security for Wireless and Mobile Networks, Q2SWinet 2015, Cancun, Mexico, pp. 123-130, (ACM) (2015)
  • L. Blin, F. Boubekeur, S. Dubois : “A Self-Stabilizing Memory Efficient Algorithm for the Minimum Diameter Spanning Tree under an Omnipotent Daemon”, Parallel and Distributed Processing Symposium (IPDPS), 2015 IEEE International, Hyberabad, India, pp. 1065-1074, (IEEE) (2015)