Model and method for computing performance bounds in multi-hop wireless networks

• US 20050075104A1
• Filed: 10/07/2003
• Published: 04/07/2005
• Est. Priority Date: 10/07/2003
• Status: Active Grant

• Current Assignee: Zhigu Holdings Limited
• Original Assignee: Microsoft Corporation
• Inventors: Jain, Kamal, Padhye, Jitendra D., Padmanabhan, Venkata N., Qiu, Lili
• Granted Patent: US 7,469,143 B2
• Time in Patent Office: Days
• US Class Current: 455/423
• CPC Class Codes: H04W 16/14 Spectrum sharing arrangements between different networks

Abstract

Disclosed is a general model and method for computing performance bounds in multi-hop wireless networks. Rather than focusing on computing asymptotic performance bounds under assumptions of homogeneity or randomness in the network topology and/or workload, the present invention accommodates any given network, technology, interference model, routing paradigm, and workload. Using a conflict graph to formally characterize the impact of wireless interference on the performance of multi-hop wireless networks, methods for computing upper and lower bounds on the capacity of a given wireless network are detailed. Besides computing network capacity, the model and method disclosed can also enable or benefit other applications including maximizing fairness and minimizing maximum link utilization.

Claims

1. A method of modeling wireless interference among wireless links between a plurality of wireless nodes in a wireless network, the method comprising:

accepting connectivity information for the network;

identifying wireless links between nodes of the network from the connectivity information;

representing each identified link as a vertex; and

creating an edge between a first vertex and a second vertex if the corresponding wireless links interfere with one another.

2. The method of claim 1 wherein the connectivity information is represented by a connectivity graph.

3. The method of claim 1 further comprising:

assigning to the edge a weight of zero (0) if the links are not in conflict with each other; and

assigning to the edge a weight of one (1) if the links are in conflict with each other.

4. The method of claim 1 further comprising:

assigning to the edge a direction; and

assigning to the edge a weight equal to a fraction of a maximum permissible noise at a link corresponding to the second vertex contributed by activity on the link corresponding to the first vertex.

5. The method of claim 1 wherein each node is equipped with exactly one radio.

6. The method of claim 1 wherein each node is equipped with a plurality of radios.

7. The method of claim 1 wherein all nodes communicate on exactly one wireless channel.

8. The method of claim 1 wherein each node may communicate on a plurality of wireless channels.

9. The method of claim 1 wherein each node is equipped with exactly one omni-directional antenna.

10. The method of claim 1 wherein each node is equipped with a plurality of directional antennae.

11. The method of claim 1 wherein each node is equipped with a plurality of omni-directional antennae.

12. The method of claim 1 wherein all wireless links have equal capacities.

13. The method of claim 1 wherein the wireless links may have different capacities.

14. The method of claim 1 wherein a receiving node must be free of interference for a transmission to be successful.

15. The method of claim 14 wherein a sending node must be free of interference for a transmission to be successful.

16. The method of claim 1 further comprising making routing decisions based on the created edges and vertices.

17. The method of claim 1 further comprising making network infrastructure decisions based on the created edges and vertices.

18. A computer-readable medium containing instructions for performing a method of modeling wireless interference among wireless links between a plurality of wireless nodes in a wireless network, the method comprising:

accepting connectivity information for the network;

identifying wireless links between nodes of the network from the connectivity information;

representing each identified link as a vertex; and

creating an edge between a first vertex and a second vertex if the corresponding wireless links interfere with one another.

19. A computer-readable medium having stored thereon a conflict graph data structure, the data structure comprising:

a first data field containing data representing a first wireless link;

a second data field containing data representing a second wireless link; and

a third data field containing data representing whether the first and second wireless links are in conflict.

20. The computer-readable medium having stored thereon a conflict graph data structure of claim 19 wherein the conflict graph employs a protocol interference model.

21. The computer-readable medium having stored thereon a conflict graph data structure of claim 19 wherein the conflict graph employs a physical interference model.

22. A method for computing an upper bound on throughput that a wireless network can support using a protocol interference model, the method comprising:

accepting connectivity information for the network;

identifying wireless links between nodes of the network from the connectivity information;

representing each identified link as a vertex;

creating a non-directional edge between a first vertex and a second vertex if the corresponding wireless links interfere with one another;

assigning to the edge a weight of zero (0) if the links are not in conflict with each other;

assigning to the edge a weight of one (1) if the links are in conflict with each other;

formulating a linear program corresponding to a max-flow problem;

identifying at least one clique among the vertices;

formulating a constraint for each identified clique;

incorporating the constraint in the linear program; and

solving the linear program.

23. The method of claim 22 wherein the connectivity information is represented by a connectivity graph.

24. The method of claim 22 wherein there is exactly one sending node.

25. The method of claim 24 wherein the sending node sends data as fast as it can.

26. The method of claim 22 wherein there is exactly one receiving node.

27. The method of claim 26 wherein the receiving node receives data as fast as it can.

28. The method of claim 22 wherein a multi-path routing scheme is employed.

29. The method of claim 22 wherein there is a plurality of sending nodes.

30. The method of claim 29 wherein at least one of the sending nodes may not send data as fast as it can.

31. The method of claim 22 wherein there is a plurality of receiving nodes.

32. The method of claim 31 wherein at least one of the receiving nodes may not receive data as fast as it can.

33. The method of claim 22 wherein a single-path routing scheme is employed.

34. The method of claim 22 further comprising making routing decisions based on the upper bound.

35. The method of claim 22 further comprising making network infrastructure decisions based on the upper bound.

36. A computer-readable medium containing instructions for performing a method for computing an upper bound on throughput that a wireless network can support using a protocol interference model, the method comprising:

accepting connectivity information for the network;

identifying wireless links between nodes of the network from the connectivity information;

representing each identified link as a vertex;

creating a non-directional edge between a first vertex and a second vertex if the corresponding wireless links interfere with one another;

assigning to the edge a weight of zero (0) if the links are not in conflict with each other;

assigning to the edge a weight of one (1) if the links are in conflict with each other;

formulating a linear program corresponding to a max-flow problem;

identifying at least one clique among the vertices;

formulating a constraint for each identified clique;

incorporating the constraint in the linear program; and

solving the linear program.

37. A method for computing a lower bound on throughput that a wireless network can support using a protocol interference model, the method comprising:

accepting connectivity information for the network;

identifying wireless links between nodes of the network from the connectivity information;

representing each identified link as a vertex;

creating a non-directional edge between a first vertex and a second vertex if the corresponding wireless links interfere with one another;

assigning to the edge a weight of zero (0) if the links are not in conflict with each other;

assigning to the edge a weight of one (1) if the links are in conflict with each other;

formulating a linear program corresponding to a max-flow problem;

identifying at least one independent set among the vertices;

formulating a constraint for each identified independent set;

incorporating the constraint in the linear program; and

solving the linear program.

38. The method of claim 37 wherein the connectivity information is represented by a connectivity graph.

39. The method of claim 37 wherein there is exactly one sending node.

40. The method of claim 39 wherein the sending node sends data as fast as it can.

41. The method of claim 37 wherein there is exactly one receiving node.

42. The method of claim 41 wherein the receiving node receives data as fast as it can.

43. The method of claim 37 wherein a multi-path routing scheme is employed.

44. The method of claim 37 wherein there is a plurality of sending nodes.

45. The method of claim 44 wherein at least one of the sending nodes may not send data as fast as it can.

46. The method of claim 37 wherein there is a plurality of receiving nodes.

47. The method of claim 46 wherein at least one of the receiving nodes may not receive data as fast as it can.

48. The method of claim 37 wherein a single-path routing scheme is employed.

49. The method of claim 37 further comprising making routing decisions based on the upper bound.

50. The method of claim 37 further comprising making network infrastructure decisions based on the upper bound.

51. A computer-readable medium containing instructions for performing a method for computing a lower bound on throughput that a wireless network can support using a protocol interference model, the method comprising:

accepting connectivity information for the network;

identifying wireless links between nodes of the network from the connectivity information;

representing each identified link as a vertex;

creating a non-directional edge between a first vertex and a second vertex if the corresponding wireless links interfere with one another;

assigning to the edge a weight of zero (0) if the links are not in conflict with each other;

assigning to the edge a weight of one (1) if the links are in conflict with each other;

formulating a linear program corresponding to a max-flow problem;

identifying at least one independent set among the vertices;

formulating a constraint for each identified independent set;

incorporating the constraint in the linear program; and

solving the linear program.

52. A method for computing an upper bound on throughput that a wireless network can support using a physical interference model, the method comprising:

accepting connectivity information for the network;

identifying wireless links between nodes of the network from the connectivity information;

representing each identified link as a vertex;

creating a directional edge between a first vertex and a second vertex if the corresponding wireless links interfere with one another;

assigning to the edge a weight equal to a fraction of a maximum permissible noise at a link corresponding to the second vertex contributed by activity on the link corresponding to the first vertex;

formulating a linear program corresponding to a max-flow problem;

identifying at least one non-schedulable set among the vertices;

formulating a constraint for each identified non-schedulable set;

incorporating the constraint in the linear program; and

solving the linear program.

53. The method of claim 52 wherein the connectivity information is represented by a connectivity graph.

54. The method of claim 52 wherein there is exactly one sending node.

55. The method of claim 54 wherein the sending node sends data as fast as it can.

56. The method of claim 52 wherein there is exactly one receiving node.

57. The method of claim 56 wherein the receiving node receives data as fast as it can.

58. The method of claim 52 wherein a multi-path routing scheme is employed.

59. The method of claim 52 wherein there is a plurality of sending nodes.

60. The method of claim 59 wherein at least one of the sending nodes may not send data as fast as it can.

61. The method of claim 52 wherein there is a plurality of receiving nodes.

62. The method of claim 61 wherein at least one of the receiving nodes may not receive data as fast as it can.

63. The method of claim 52 wherein a single-path routing scheme is employed.

64. The method of claim 52 further comprising making routing decisions based on the upper bound.

65. The method of claim 52 further comprising making network infrastructure decisions based on the upper bound.

66. A computer-readable medium containing instructions for performing a method for computing an upper bound on throughput that a wireless network can support using a physical interference model, the method comprising:

accepting connectivity information for the network;

identifying wireless links between nodes of the network from the connectivity information;

representing each identified link as a vertex;

creating a directional edge between a first vertex and a second vertex if the corresponding wireless links interfere with one another;

assigning to the edge a weight equal to a fraction of a maximum permissible noise at a link corresponding to the second vertex contributed by activity on the link corresponding to the first vertex;

formulating a linear program corresponding to a max-flow problem;

identifying at least one non-schedulable set among the vertices;

formulating a constraint for each identified non-schedulable set;

incorporating the constraint in the linear program; and

solving the linear program.

67. A method for computing a lower bound on throughput that a wireless network can support using a physical interference model, the method comprising:

accepting connectivity information for the network;

identifying wireless links between nodes of the network from the connectivity information;

representing each identified link as a vertex;

creating a directional edge between a first vertex and a second vertex if the corresponding wireless links interfere with one another;

assigning to the edge a weight equal to a fraction of a maximum permissible noise at a link corresponding to the second vertex contributed by activity on the link corresponding to the first vertex;

formulating a linear program corresponding to a max-flow problem;

identifying at least one schedulable set among the vertices;

formulating a constraint for each identified schedulable set;

incorporating the constraint in the linear program; and

solving the linear program.

68. The method of claim 67 wherein the connectivity information is represented by a connectivity graph.

69. The method of claim 67 wherein there is exactly one sending node.

70. The method of claim 69 wherein the sending node sends data as fast as it can.

71. The method of claim 67 wherein there is exactly one receiving node.

72. The method of claim 71 wherein the receiving node receives data as fast as it can.

73. The method of claim 67 wherein a multi-path routing scheme is employed.

74. The method of claim 67 wherein there is a plurality of sending nodes.

75. The method of claim 74 wherein at least one of the sending nodes may not send data as fast as it can.

76. The method of claim 67 wherein there is a plurality of receiving nodes.

77. The method of claim 76 wherein at least one of the receiving nodes may not receive data as fast as it can.

78. The method of claim 67 wherein a single-path routing scheme is employed.

79. The method of claim 67 further comprising making routing decisions based on the upper bound.

80. The method of claim 67 further comprising making network infrastructure decisions based on the upper bound.

81. A computer-readable medium containing instructions for performing a method for computing a lower bound on throughput that a wireless network can support using a physical interference model, the method comprising:

accepting connectivity information for the network;

identifying wireless links between nodes of the network from the connectivity information;

representing each identified link as a vertex;

creating a directional edge between a first vertex and a second vertex if the corresponding wireless links interfere with one another;

assigning to the edge a weight equal to a fraction of a maximum permissible noise at a link corresponding to the second vertex contributed by activity on the link corresponding to the first vertex;

formulating a linear program corresponding to a max-flow problem;

identifying at least one schedulable set among the vertices;

formulating a constraint for each identified schedulable set;

incorporating the constraint in the linear program; and

solving the linear program.

82. A method for improving throughput in a wireless network, the method comprising:

accepting connectivity information for the network;

identifying wireless links between nodes of the network from the connectivity information;

representing each identified link as a vertex;

creating a directional edge between a first vertex and a second vertex if the corresponding wireless links interfere with one another;

assigning to the edge a weight equal to a fraction of a maximum permissible noise at a link corresponding to the second vertex contributed by activity on the link corresponding to the first vertex;

collecting the edge and weight information at a centralized location; and

using the edge and weight information to determining routing paths.

83. The method of claim 82 wherein the connectivity information is represented by a connectivity graph.

84. A computer-readable medium containing instructions for performing a method for improving throughput in a wireless network, the method comprising:

accepting connectivity information for the network;

identifying wireless links between nodes of the network from the connectivity information;

representing each identified link as a vertex;

creating a directional edge between a first vertex and a second vertex if the corresponding wireless links interfere with one another;

assigning to the edge a weight equal to a fraction of a maximum permissible noise at a link corresponding to the second vertex contributed by activity on the link corresponding to the first vertex;

collecting the edge and weight information at a centralized location; and

using the edge and weight information to determining routing paths.

85. A method for computing a throughput that a wireless network can support, the method comprising:

accepting connectivity information for the network;

identifying at each node of the connectivity information for the network an exclusive outgoing edge having non-zero flow;

formulating a mixed-integer program corresponding to a max-flow problem;

formulating a constraint corresponding to the exclusive outgoing edge having non-zero flow;

incorporating the constraint in the mixed-integer program; and

solving the mixed-integer program.

86. The method of claim 85 wherein the connectivity information is represented by a connectivity graph.

87. The method of claim 85 further comprising making routing decisions based on the throughput.

88. The method of claim 86 further comprising making network infrastructure decisions based on the throughput.

89. A computer-readable medium containing instructions for performing a method for computing a throughput that a wireless network can support, the method comprising:

accepting connectivity information for the network;

identifying at each node of the connectivity information for the network an exclusive outgoing edge having non-zero flow;

formulating a mixed-integer program corresponding to a max-flow problem;

formulating a constraint corresponding to the exclusive outgoing edge having non-zero flow;

incorporating the constraint in the mixed-integer program; and

solving the mixed-integer program.