With the proliferation of Internet of Things (IoT), a large number of devices are expected to connect to the Internet over different networks due to various demands and characteristics of IoT devices (IoTDs). One of the networks that will connect IoTDs to the Internet is cellular networks. The 3rd Generation Partnership Project (3GPP) proposes a connectivity model for cellular networks in which IoTDs connect to the network via relay devices. In this model, discovering the relay devices is a challenging task due to energy budget constraints, mobility of devices, and collision of discovery messages. Since IoTDs are constrained devices, it is important that they perform discovery with the minimum energy consumption by intermittently sleeping and waking up. In this paper, we propose signature-based and energy-efficient relay discovery protocol (SERDP) using Zadoff-Chu sequences. Since Zadoff-Chu is a Constant Amplitude Zero Autocorrelation (CAZAC) sequence, we use the sequence for pointing the active slots of the devices within the proposed three-stage original period structure. The probabilistic analysis and simulation results show that SERDP discovers more devices with less energy consumption as well as preventing collisions, as compared with the existing protocols.