Device-to-device communication in 5G networks will require fast and efficient neighbour discovery. This Letter shows that with an initial knowledge of proximity, devices can increase discovery probability. However, in out-of-coverage scenarios, devices do not have information about neighbourhood which decreases the discovery probability. Hence, this Letter proposes an algorithm that enables neighbourhood-awareness in out-of-coverage environments, and increases discovery probability.