The invention relates to a method for accelerating a set-up procedure for wireless connections between at least two devices. The set-up procedure requires a first device to receive an inquiry message initiating said procedure from a second device twice with a back-off time in between before responding to the second device. In order to enable such an acceleration, it is proposed that the first device scans for inquiry messages and measures a value of a parameter associated to a detected inquiry message indicative of the received power level of the inquiry message. Then, the first device determines at least a maximum number as a function of the measured value, or of a pathloss determined based on this measured value. It moreover generates a random number within a number space limited by the maximum number. Finally, the first device scans again for the inquiry message after a back-off time. The length of the back-off time is related to said generated random number.