Algorithms for BPRN Coloring of a Digraph

A radio network consists of a set of transceiver nodes that make use of radio transmissions to communicate with each other. Because these wireless networks share the communication channel, collisions may occur in transmissions, whether through primary or secondary interference. Considering that to a large extent these networks have multi-hops in their composition, thus it is possible the spatial reuse in the channel sharing, with the prevention of collisions and with this reducing the loss of data transmitted. In the context of these networks, several approaches are used to medium control access, in order to coordinate access to the wireless channel to avoid overlapping of transmissions in the use of the channel. A wireless network can be represented as a digraph, and the PRN (Packet Radio Network) coloring model is applied as a scheduling criterion for MAC protocols. The BPRN (Backbone PRN) model represents a generalization of the PRN coloring, applying a more realistic approach where it is considered only a subset of links that will be colored, which we call the backbone network. The backbone network considers the fact that in a multi-hop wireless network, a transceiver node communicates only with some of its neighbors. In this work, the backbone network is represented by a tree oriented towards a root node, due to its relationship to the domain of the wireless sensor networks. Thus, this work proposes the development of algorithms for coloring graphs based on the BPRN coloring model, with emphasis on the TDMA channel allocation technique, since it will be used for the scheduling of links in the context of multi-hop wireless networks.