Patent ID: 8130657

Claim:
A method for computing link costs for a multi-hop wireless network, comprising: receiving topological information associated with the multi-hop wireless network, wherein the topological information specifies a set of nodes, a set of links, and a success probability pi for a respective link i which indicates the probability of successfully transmitting a packet from a first node coupled to the link to a second node coupled to the link; obtaining an average media access time for the multi-hop wireless network, wherein the average media access time is approximately the time from when a media access control (MAC) layer first receives a packet to the time when the packet is transmitted onto a transmission medium, wherein the average media access time correspond to an average value that is link-independent for the multi-hop wireless network; obtaining a retransmission time for a respective node in the set of nodes, wherein the retransmission time is approximately a delay associated with retransmitting a packet by a node after a failed transmission; computing a-an expected retransmission time (ERT) link metric value for a respective link, wherein the ERT link metric value has a direct relationship with the retransmission time associated with the link, with an expected number of failures associated with a successful packet transmission on the link and a constant, wherein the expected number of failures is computed based on the link's success probability, and wherein the constant in the direct relationship is the average media access time; and producing a link cost for the link based on the ERT link metric value for the link, thereby facilitating more efficient routing through the multi-hop wireless network.