Distributed Time Slots Assignment Protocol in Dynamic Networks

This paper addresses the problem of communication in resource-limited broadcast/receive wireless networks. In large scale and resource-limited wireless networks, such as the Internet of Things (IoT), a massive amount of data is becoming increasingly available. Therefore, implementing protocols achieving error-free communication channels presents an important challenge. Indeed, in this new kind of network, the prevention of message conflicts and message collisions is a crucial issue. In terms of graph theory, solving this issue amounts to solve the distance-2 coloring problem on the network. This paper presents a first study on dynamic management in distance-2 coloring in resource-limited wireless networks. We propose a distributed distance-2 coloring in a dynamic network where (one) new node can join the network. Our protocol assigns to the new node a correct color without re-running the whole algorithm of time slot assigning. Our protocol is time-efficient and uses only local information with a high probability.