Towards Low-complexity Relay Selection and Scheduling in Wireless Networks
- Author(s): Essa, Yahya Hussain Ezzeldin
- Advisor(s): Fragouli, Christina
- et al.
Next-generation wireless networks are expected to usher in a revolution of communication systems in terms of the network capabilities, technologies used, and serviced applications. A key aim in these networks is to expand available bandwidth and enable multi-gigabit emerging applications that range from ultra-high-definition video to autonomous vehicle platoons and Industry 4.0 low latency communication. The focus of this dissertation is to study two technologies that are envisioned to drive the physical layer in the next generation of networks - multi-hop relay selection and mmWave transmission - in terms of fundamental theoretical guarantees on performance and the efficiency of operation and scheduling.
We study the problem of relay selection for routing in a wireless full-duplex relay network. We derive fundamental worst-case guarantees on the performance of routing in wireless relay networks operating in full-duplex with arbitrary topology. This extends the state of the art in terms of these fundamental guarantees which were previously only studied for the diamond network topology. These worst-case guarantees provide guidance for heuristic and optimal routing approaches in full-duplex wireless networks.
Second, we study the problem of efficiently selecting a subset of relays in a diamond network operating in half-duplex and the fundamental guarantees that follow from the selection of the best relay subset. We prove fundamental guarantees on the retained capacity when a subset of N-1 relays are retained out of N relays in a diamond topology, For selecting k
Next, we show that selecting the simple route with the highest approximate capacity with a half-duplex network with arbitrary topology is in general an NP-hard problem (unlike its full-duplex counterpart). Additionally, we provide sufficient properties on the network topology that ensure that finding the best route can be done in polynomial-time in the number of nodes in the network. These results are enabled by a closed-form expression that we derive for the approximate capacity of a half-duplex network that enabled the study of its NP-hardness as well as deriving an efficient routing algorithm.
Finally, we study the impact of directional communication which is envisioned in mmWave communication networks. To tackle this, we propose a new information-theoretic model for multi-hop wireless networks referred to as "1-2-1 network". In a 1-2-1 network, at any time instance, two nodes can communicate only if they point beams (which need to be scheduled) at each other, while if they do not point beams at each other, no signal can be exchanged. We used this model to approximate the Shannon capacity for mmWave networks with arbitrary topology operating with full-duplex or half-duplex mmWave nodes. Additionally, we develop a provably optimal polynomial-time algorithm to compute the approximate capacity and an optimal beam-orientation schedule in full-duplex and half-duplex mmWave networks.