BOUBEKEUR Fadwa
Supervision : LĂ©lia BLIN
Arbres couvrants de la thĂ©orie Ă la pratique. Algorithmes autostabilisants 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 selfstabilization 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 selfstabilizing algorithms dedicated to sensor networks. The contributions of this thesis are:
In the first part of the thesis, we proposed a selfstabilizing 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.
Defence : 10/12/2016  10h  Site Jussieu 2526/105
Jury members :
DUDA Andrzej, Professeur Grenoble INPEnsimag [rapporteur]
JOHNEN Colette, Professeur Université de Bordeaux [rapporteur]
DIAS DE AMORIM Marcelo, Directeur de recherche CNRS
LEGUAY Jérémie, Ingénieur de recherche Huawei
PETIT Franck, Professeur UPMC
VILLAIN Vincent, Professeur Université de Picardie Jules Verne
BLIN Lélia, MCF HDR UPMC
20152018 Publications

2018
 L. Blin, F. Boubekeur, S. Dubois : “A SelfStabilizing Memory Efficient Algorithm for the Minimum Diameter Spanning Tree under an Omnipotent Daemon”, Journal of Parallel and Distributed Computing, vol. 117, pp. 5062, (Elsevier) (2018)

2016
 F. Boubekeur : “Arbres couvrants de la thĂ©orie Ă la pratique. Algorithmes autostabilisants et RĂ©seaux de Capteurs”, thesis, defence 10/12/2016, supervision Blin, LĂ©lia (2016)
 L. Blin, F. Boubekeur, S. Dubois : “Algorithme autostabilisant efficace en mĂ©moire pour la construction dâ€™un arbre couvrant de diamĂ¨tre minimum”, ALGOTEL 2016  18^{e}s 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. 123130, (ACM) (2015)
 L. Blin, F. Boubekeur, S. Dubois : “A SelfStabilizing 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. 10651074, (IEEE) (2015)