Optimal Routing and Data Transmission for Multi-Hop D2D Communications

Abstract

Device-to-Device (D2D) communication, which enables direct link communication between nodes without going through the infrastructure, has received considerable attention in recent years, particularly in the context of Internet-of-Things (IoT) and machine-to-machine (M2M) communications. It is also slated to be part of the 5G communication standards. The primary advantages of D2D are enhanced spatial frequency reuse leading to better spectral efficiency, reduced out-of-cell interference, better cell-edge coverage, etc. Once implemented, the D2D mode of communication opens up new and interesting avenues for improving the spectral efficiency of a cellular system. A particularly interesting problem in this context is that of routing data over multiple D2D nodes to maximize the end-to-end throughput between a source and destination, while ensuring that the D2D nodes do not cause detrimental interference to the ongoing transmissions in the cellular network. This can potentially result in significantly higher D2D throughput compared to the hitherto-considered single-hop D2D communications paradigm. The main focus of this thesis is to determine a throughput-optimal route between a given source-destination pair under a probabilistic interference constraint imposed by the cellular network, and to analytically characterize the throughput improvement obtainable by multi-hop D2D communications.

The first part of the thesis proposes an easy-to-implement routing algorithm to maximize the end-to-end throughput of a given source-destination pair. Next, in order to further increase the throughput on the determined route, a link activation algorithm is proposed, which enables links opportunistically, based on the buffer states of the relay nodes and the link feasibility. Theoretical expressions for throughput, delay and system idle probability are derived by modeling the relay buffer state evolution as a Discrete Time Markov Chain (DTMC). Theory and simulation showcase the performance gains obtained by opportunistic link activation compared to the baseline sequential link activation scheme, where the links are enabled in a round-robin fashion. The second part of the thesis proposes a routing algorithm to maximize the end-to-end throughput between D2D source-destination pair, under an additional per-hop delay constraint. The analytical expression derived for throughput on the multi-hop route facilitates the application of Dijkstra's algorithm, again leading to an easy-to-implement optimal routing algorithm. The tradeoff between throughput and delay is illustrated through simulations. Overall, the results in the thesis are useful for (a) determining throughput optimal and delay-constrained throughput optimal routes between a given source and destination communicating in the D2D mode; (b) analytically characterizing the gains obtainable via multi-hop D2D communications; and (c) performance characterization and comparison of opportunistic link activation (which entails data buffering at the individual nodes) and sequential link activation, in terms of both delay and the throughput achieved