A multipoint relay (MPR) wireless network may include spaced apart nodes, with each node including wireless transceiver circuitry, beacon circuitry, and a controller coupled to the wireless transceiver circuitry and beacon circuitry. The controllers may be configured to operate the beacon circuitry to determine a respective link strength metric for each potential link between nodes, assign a set of nodes from among the plurality of nodes to function as gateway nodes and assign other individual nodes to communicate via respective gateway nodes based upon the respective link strength metrics to define the MPR network so that one-hop links have a strongest link strength metric, and operate the wireless transceiver circuitry for communications over the MPR network.