A system computes link costs for a multi-hop wireless network. During operation, the system receives topological information for the multi-hop wireless network which includes a set of nodes, a set of links, and a success probability for a respective link. The system then obtains an average media access time for the multi-hop wireless network. The system also obtains a retransmission time for a respective node in the set of nodes. Next, the system computes a link metric value for a respective link based on the corresponding link success probability, the average media access time, and the corresponding retransmission time. The system then produces a link cost for the link based on the associated link metric value.