Design of Joint Relay Placement and Scheduling Algorithms for Time-Slotted Networks with Half-Duplex Constraints

Industrial Internet-of-Things, automation, and process control applications require communication networks with a high degree of reliability, low energy expenditure, and low latency. Convergecast communication wherein all nodes in the network transmit data to a common base station is a common paradigm for such applications. Time slotted networks which support deterministic scheduling, such as 802.15.4e Time Slotted Channel Hopping (TSCH) multiple access (MAC) protocol, are well suited for such applications. In this paper, we consider a joint relay selection and scheduling problem for convergecast on a multihop wireless network using single channel TSCH MAC protocol. The objective of the problem is to reduce both the number of relay nodes required for network connectivity as well as the slot-frame duration for a periodic deterministic convergecast schedule. For tree networks with half-duplex constraints we obtain a lower bound on the minimum slot-frame duration and show that the relay selection and scheduling problem can be decoupled. We propose a heuristic scheduling algorithm which is shown to achieve the above lower bound using simulations. For the NP-hard relay selection problem, we propose a polynomial time relay selection algorithm with an improved approximation ratio. The performance of our relay selection and scheduling algorithms are studied via simulations on randomly generated graphs.