A method for using proxy messages in a neighbor aware network, comprising: receiving, by a first proxy station, a service advertisement of a provider station, the service advertisement indicating services provided by the provider station; selectively transmitting in response to the receiving, a first proxy broadcast message, the first proxy broadcast message comprising the service advertisement; and receiving, in response to the transmitting, a discovery request from a seeker station, the seeker station being more than one hop from the provider station, the discovery request requesting services from the provider station, the first proxy station configured to selectively transmit the first proxy broadcast message based on at least one of the following parameters: a number of hops from the provider station through the first proxy to the seeker station; whether the provider station is a parent provider of the first proxy station; the first proxy station has found the service advertised by the provider station; a distance between the provider station and the seeker station; whether the first proxy station is one of a group of eligible stations in range of the service advertisement or a second proxy broadcast message, wherein the second proxy broadcast message comprises the service advertisement; whether the service advertisement indicates a service that is one of a list of eligible services; the second proxy broadcast message is received at the first proxy station from a second proxy station within a close range; and whether the second proxy broadcast message is received at the first proxy station from three or more neighboring proxy stations within a medium range, wherein the medium range is longer than the close range. receiving, by a first proxy station, a service advertisement of a provider station, the service advertisement indicating services provided by the provider station; selectively transmitting in response to the receiving, a first proxy broadcast message, the first proxy broadcast message comprising the service advertisement; and receiving, in response to the transmitting, a discovery request from a seeker station, the seeker station being more than one hop from the provider station, the discovery request requesting services from the provider station, the first proxy station configured to selectively transmit the first proxy broadcast message based on at least one of the following parameters: a number of hops from the provider station through the first proxy to the seeker station; whether the provider station is a parent provider of the first proxy station; the first proxy station has found the service advertised by the provider station; a distance between the provider station and the seeker station; whether the first proxy station is one of a group of eligible stations in range of the service advertisement or a second proxy broadcast message, wherein the second proxy broadcast message comprises the service advertisement; whether the service advertisement indicates a service that is one of a list of eligible services; the second proxy broadcast message is received at the first proxy station from a second proxy station within a close range; and whether the second proxy broadcast message is received at the first proxy station from three or more neighboring proxy stations within a medium range, wherein the medium range is longer than the close range. a number of hops from the provider station through the first proxy to the seeker station; whether the provider station is a parent provider of the first proxy station; the first proxy station has found the service advertised by the provider station; a distance between the provider station and the seeker station; whether the first proxy station is one of a group of eligible stations in range of the service advertisement or a second proxy broadcast message, wherein the second proxy broadcast message comprises the service advertisement; whether the service advertisement indicates a service that is one of a list of eligible services; the second proxy broadcast message is received at the first proxy station from a second proxy station within a close range; and whether the second proxy broadcast message is received at the first proxy station from three or more neighboring proxy stations within a medium range, wherein the medium range is longer than the close range.