Interference-based routing in a wireless mesh network

• US 7,554,998 B2
• Filed: 01/11/2005
• Issued: 06/30/2009
• Est. Priority Date: 01/11/2005
• Status: Active Grant

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Simonsson, Arne, Pettersson, Jonas
• Primary Examiner(s): Ngo; Ricky
• Assistant Examiner(s): Liu; Ben H
• Application Number:
  US11/032,237
• Publication Number:
  US 20060153081A1
• Time in Patent Office: 1,631 Days
• Field of Search: 370/238, 709/241
• US Class Current: 370/406
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04W 40/16 based on interference
• CPC Class Codes: Y02D 30/00 Reducing energy consumption in communication networks
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

Route selection through a wireless mesh network between a source node and a destination node is based on minimizing generated interference in order to increase the capacity of the network. An interference energy associated with transmitting a packet over each hop in multiple routes from the source node to the destination node is determined. The interference energy for each hop is combined to generate a combined interference energy for each route. One of the routes is selected based on the combined interference energy determined for each route.

Claims

1. A method to select a route for a packet through a wireless mesh network between a source node and a destination node, comprising:

determining an interference energy associated with transmitting the packet over each node hop in multiple routes from the source node to the destination node;

combining the interference energy for each hop to produce a combined interference energy for each route; and

selecting one of the routes based on the combined interference energy for each route,

wherein determining the interference energy includes determining a transmission time associated with transmitting the packet over each hop in multiple routes from the source node to the destination node, and

wherein the transmission time takes into account a size of the packet, an overhead associated with sending the packet, a bit rate associated with transmitting the packet over the hop that depends on current radio conditions for the hop, and a retransmission probability associated with transmitting over the hop.

2. The method in claim 1, wherein combining the interference energies includes summing the interference energies, and

wherein the one route is selected having a lowest summed interference energy.

3. The method in claim 1, further comprising:

for each of the hops, determining a number of nodes that would be affected by interference associated with transmitting the packet over that hop;

combining the transmission time and the number of affected nodes for each hop to produce a corresponding hop result;

combining the hop results for each route; and

selecting one of the routes based on the combined results.

4. The method in claim 3, wherein combining the transmission time and the number of nodes includes multiplying the transmission time and the number of nodes;

wherein combining the hop results includes summing the results, and

wherein the one route is selected having a lowest summed result.

5. The method in claim 3, wherein the number of affected nodes is estimated based on a power level at which the packet would be transmitted over the hop and a propagation function that translates the power level to a caused interference to one or more surrounding nodes.

6. The method in claim 3, wherein the number of affected nodes is estimated based on a power level at which the packet would be transmitted over the hop, a receiver threshold at which the interference is affecting other nodes, and a propagation function that translates the power level to a caused interference to one or more surrounding nodes.

7. The method in claim 6, wherein the number of affected nodes is further based on a probability that nodes that are affected by interference also have data to transmit during the time they are interfered.

8. The method in claim 7, wherein the probability is estimated based on an average channel activity experienced by a transmitting node.

9. The method in claim 3, wherein the transmission time U is determined in accordance with the following:

$U=\frac{D+{\mathrm{OH}}_{L<br><br><br><br>1}}{R_{L<br><br><br><br>1}·<br><br>\left(1-\mathrm{BLER}\right)}·<br><br>N_{\mathrm{CH}}$

where D is a size of the packet, OH_L1 is an overhead associated with the packet transmission, N_CH is a number of channels used for the transmission, R_L1 is a bit rate associated with transmitting the packet over the hop that depends on current radio conditions for the hop, and BLER is a block error probability estimate for the packet transmission.

10. The method in claim 3, wherein the number of affected nodes is estimated based in accordance with:

P^2/α

wherein P is a power level at which the packet would be transmitted over the hop and α

is a propagation factor that adjusts the power level to a caused interference to one or more surrounding nodes.

11. The method in claim 10, wherein the interference energy W for transferring the packet over one hop is determined in accordance with:

W=U·

P^2/α

.

12. The method in claim 10, wherein the interference energy W for transferring the packet over one hop is determined in accordance with:

W=U·

P^2/α

·

P_Jam

where P_Jam is a probability that a node affected by interference also has data to transmit during the time when that node is interfered.

13. The method in claim 1, wherein information used to determine an interference energy associated with one or more hops is obtained from transmissions from other nodes.

14. The method in claim 13, wherein information used to determine an interference energy associated with one or more hops is obtained by the one node monitoring communications between other nodes.

15. The method in claim 1, further comprising:

distributing determined hop interference energies among the multiple nodes.

16. Apparatus for selecting a route for a packet through a wireless mesh network of nodes between a source node and a destination node, comprising electronic circuitry configured to:

determine an interference energy associated with transmitting the packet over each node hop in multiple routes from the source node to the destination node based on a transmission time associated with transmitting the packet over each hop in multiple routes from the source node to the destination node, where the transmission time takes into account a size of the packet, an overhead associated with sending the packet, a bit rate associated with transmitting the packet over the hop that depends on current radio conditions for the hop, and a retransmission probability associated with transmitting over the hop;

combine the interference energy for each hop to produce a combined interference energy for each route; and

select one of the routes based on the combined interference energy for each route.

17. The apparatus in claim 16, wherein the electronic circuitry is further configured to sum the interference energies and select the one route having a lowest summed interference energy.

18. The apparatus in claim 16, wherein the electronic circuitry is further configured to:

for each of the hops, determine a number of nodes that would be affected by interference associated with transmitting the packet over that hop;

combine the transmission time and the number of affected nodes for each hop to produce a corresponding hop result;

combine the hop results for each route; and

select one of the routes based on the combined results.

19. The apparatus in claim 18, wherein the electronic circuitry is further configured to multiply the transmission time and the number of nodes, sum the results, and select the one route having a lowest summed result.

20. The apparatus in claim 18, wherein the electronic circuitry is further configured to estimate the number of affected nodes based on a power level at which the packet would be transmitted over the hop and a propagation function that translates the power level to a caused interference to one or more surrounding nodes.

21. The apparatus in claim 18, wherein the electronic circuitry is further configured to estimate the number of affected nodes based on a power level at which the packet would be transmitted over the hop, a receiver threshold at which the interference is affecting other nodes and a propagation function that translates the power level to a caused interference to one or more surrounding nodes.

22. The apparatus in claim 21, wherein the number of affected nodes is further based on a probability that another node having data to transmit during the transmission time will actually be affected by the packet transmission.

23. The apparatus in claim 18, wherein the transmission time U is determined in accordance with the following:

$U=\frac{D+{\mathrm{OH}}_{L<br><br><br><br>1}}{R_{L<br><br><br><br>1}·<br><br>\left(1-\mathrm{BLER}\right)}·<br><br>N_{\mathrm{CH}}$

where D is a size of the packet, OH_L1 is an overhead associated with the packet transmission, N_CH is a number of channels used for the transmission, R_L1 is a bit rate associated with transmitting the packet over the hop that depends on current radio conditions for the hop, and BLER is a block error probability estimate for the packet transmission.

24. The apparatus in claim 23, wherein the number of affected nodes is estimated based in accordance with:

P^2/α

wherein P is a power level at which the packet would be transmitted over the hop and α

is a propagation factor that adjusts the power level to a caused interference to one or more surrounding nodes.

25. The apparatus in claim 24, wherein the interference energy W for transferring the packet over one hop is determined in accordance with:

W=U·

P<sup>2/α

.</sup>

26. The apparatus in claim 24, wherein the interference energy W for transferring the packet over one hop is determined in accordance with:

W=U·

P^2/α

·

P_Jam

where P_Jam is a probability that one or more nodes having data to transmit during the transmission time will actually be affected by the packet transmission.

27. The apparatus in claim 16, wherein the electronic circuitry is configured to distribute determined hop interference energies among the multiple nodes.

28. The apparatus in claim 16, wherein the apparatus is implemented in each of the multiple nodes.

29. The apparatus in claim 16, wherein one of more of the nodes is a portable communications device.