Premium
The Backbone Packet Radio Network coloring for Time Division Multiple Access link scheduling in Wireless Multihop Networks
Author(s) -
Rocha Leonardo,
Sasaki Diana
Publication year - 2018
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21767
Subject(s) - computer science , computer network , bipartite graph , edge coloring , fractional coloring , packet radio , backbone network , wireless network , network packet , graph coloring , graph , wireless , theoretical computer science , line graph , graph power , telecommunications
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