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.

A radio network consists of a set of transceiver nodes in space that communicate using broadcast radio. Since communication is done over a shared medium, transmissions are subject to collisions. Different Medium Access Control techniques are used to avoid such collisions and subsequent data loss. In this article, we study Time Division Multiple Access link scheduling in Wireless Multihop Networks. We generalize the packet radio network (PRN)‐coloring model that was used in previous works to obtain the Backbone PRN (BPRN)‐coloring. The BPRN‐coloring captures the fact that typically only a subset of links need to be scheduled, corresponding to the backbone network. We study the BPRN‐coloring and the corresponding BPRN‐chromatic index considering a rooted tree as backbone, motivated by applications in Wireless Sensor Networks. The BPRN‐chromatic index is determined when the whole graph is either a complete graph or a cycle, and we give partial results in the case of a bipartite graph. We show that determining the BPRN‐chromatic index is NP‐hard even when the network graph is bipartite, and the backbone is an oriented tree toward a root vertex. Finally, we model a ring topology as the power of a cycle graph and give an upper bound on the BPRN‐chromatic index. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 71(4), 403–411 2018

Wireless Sensor Networks (WSN) consist in a set ofsensor nodes that collect data in the environment and send it to a Base Station that processes the final data. Some challenges may be found, such as minimizing energy consumption and maximize the network lifetime. Many protocols achieve energy savings through network clustering. This paper presents a new modeling graph using flow network to improve the routing protocols using the clustering technique, improving the routing of data between clusters-head, as well as by setting a time for a round in the clustering process. With this agnostic technique, our proposal may increase the network lifetime, balance the power consumption among the nodes and better distribute the data transmissions. Through simulations in network simulator Omnet++, Castalia, the proposal is validated and its efficiency is verified by comparing it to other protocols which work with clustering techniques.