Multi-Relay Networks should accommodate mobile users of various speeds. The cellular system should meet the minimum residency time requirements for handover calls while considering an efficient use of available channels. In this paper, we design speed-sensitive handover under dynamic hierarchical cellular systems, in which mobile users are classified according to the mean speed of mobile users and each class has its cellular layer. In order to meet the minimum residency time, the cell size of each cellular layer is dynamically determined depending on the distributions of mean speeds of mobile users. Since the speed-dependent non-preferred cell can provide a secondary resource, overflow and take-back schemes are adopted in the system. We develop analytical models to study the performance of the proposed system, and show that the optimal cell size improves the blocking probability.