A method of wirelessly connecting a communication device to other devices using a communication protocol, wherein the communication device searches for external devices known to the communication device, so as to find a pre-selected one of the external devices known to the communication device, by executing a search activity in which the search effort to be spent by the communication device increases with the number of known external devices to be searched, wherein the search activity of the communication device is a procedure to find a known and pre-selected external device and comprises Bluetooth classic paging or Bluetooth Low Energy directed advertising, wherein a device known to the communication device is a device which has been previously connected at least once to the communication device based on the communication protocol or is at least paired with the communication device based on the communication protocol; wherein the communication device adjusts the search effort spent on the search activity for each one of the external devices according to the relevance of that external device, with a higher relevance of the external device resulting in a higher search effort; wherein the search effort is determined by at least one of the following parameters of the search activity: scheduling frequency, duty cycle and transmission power, wherein the scheduling frequency indicates how often a given external device is searched for within a given time period; the duty cycle indicates how long a given external device is searched for over a given time period; and the transmission power indicates how much transmission power is invested in the search for a given external device; and wherein the relevance of the external device is determined by at least one of an age of last usage of the external device by the communication device, a relevance value previously assigned to the external device by a user, a physical proximity of the external device to the communication device, the number of devices other than the external device connected to the communication device, knowledge, by the communication device, of a search activity by the external device for the communication device, and the relevance of the services provided by the external device. wherein the communication device adjusts the search effort spent on the search activity for each one of the external devices according to the relevance of that external device, with a higher relevance of the external device resulting in a higher search effort; wherein the search effort is determined by at least one of the following parameters of the search activity: scheduling frequency, duty cycle and transmission power, wherein the scheduling frequency indicates how often a given external device is searched for within a given time period; the duty cycle indicates how long a given external device is searched for over a given time period; and the transmission power indicates how much transmission power is invested in the search for a given external device; and wherein the relevance of the external device is determined by at least one of an age of last usage of the external device by the communication device, a relevance value previously assigned to the external device by a user, a physical proximity of the external device to the communication device, the number of devices other than the external device connected to the communication device, knowledge, by the communication device, of a search activity by the external device for the communication device, and the relevance of the services provided by the external device.