A wireless communication network may include a plurality of mobile nodes each including a wireless transceiver and a controller for controlling the wireless transceiver. The controller may also be for scheduling a respective semi-permanent time slot to establish a communication link with neighboring mobile nodes for transmitting data therebetween, where the data has different priority levels. The controller may also determine respective link utilization metrics for each data priority level for each communication link, and schedule demand assigned time slots for establishing additional communication links with the neighboring mobile nodes for transmitting data therebetween based upon the link utilization metrics and data priority levels. The wireless communication network may also provide enhanced interference avoidance and/or mitigation features in certain embodiments.