Devices, such as tracking devices, cooperate with one another to establish the routing necessary for a relay network in which a device having power-efficient and data-reliable communication with an access portal, operates to relay messages from devices which do not have an acceptable communication path to and/or from the access portal. In one aspect of the present invention, a plurality of devices synchronously determine whether an acceptable communication path can be established between themselves and one or more access portals by measuring the signal strength of an access portal beacon. In another aspect of the present invention, one or more devices, which have determined that an acceptable communication path can be established between themselves and an access portal, transmit information regarding their availability to relay messages on behalf of devices which have determined that an acceptable communication path cannot be established between themselves and an access portal.