In this paper we propose a two-step distributed scheduling algorithm for relay-assisted cellular networks where a given user can be either served by the base station or by a relay, in a opportunistic way. Such a distributed approach allows a reduced feedback signaling with respect to the centralized case, especially when a simple scalar feedback is not sufficient for estimating the channel quality. As a result of the reduced feedback signaling requirements the system becomes more scalable, as new relays can be deployed where required without need of a careful network planning. We study the effectiveness of the proposal by means of a multicell simulator.