The UE-to-Network Relay functionality was introduced to Long Term Evolution (LTE) cellular networks by the 3rd Generation Partnership Project (3GPP) in Release 13. In this technology, User Equipment (UEs) acting as Relay UEs are used to extend network coverage to cell-edge and out-of-coverage Remote UEs. One important part of this functionality is direct discovery, which is used by the Remote UEs willing to reach the network to detect the Relay UEs in proximity that can provide the desired connectivity service. In this paper, we study this protocol considering both discovery models defined in the LTE standard, and we develop analytical models to characterize the average time a Remote UE takes to discover a Relay UE using each discovery model. We validate the analytical models using system level simulations and we study the sensitivity of the metrics to different parameters of the protocol and number of UEs involved in the UE-to-Network Relay discovery.