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

• US 7,469,143 B2
• Filed: 10/07/2003
• Issued: 12/23/2008
• 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
• Primary Examiner(s): Appiah; Charles N
• Assistant Examiner(s): AJIBADE AKONAI, OLUMIDE
• Application Number:
  US10/680,549
• Publication Number:
  US 20050075104A1
• Time in Patent Office: 1,904 Days
• Field of Search: 455/446, 455/447, 455/453, 455/560, 455/561, 455/562.1, 455/445, 455/67.11, 455/422.1, 455/423, 455/67.13, 455/63.1, 370/229, 370/238, 370/230, 370/230.1, 370/237, 370/242, 370/254, 370/328, 370/329, 370/351, 370/406, 370/431, 709/223, 709/224, 709/225, 709/226, 709/227, 709/228, 709/229, 709/230, 709/232, 709/235, 709238-242, 379/221.01, 379/221.03, 379/221.06
• US Class Current: 455/446
• 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; and

creating a graph from the connectivity information, wherein

each identified wireless link is represented as a vertex in the graph,

an edge is created between a first vertex and a second vertex in the graph if the corresponding wireless links interfere with one another,

a direction is assigned to the edge, and

a weight is assigned to the edge, the weight being 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.

2. The method of claim 1 wherein the graph is a conflict graph, and wherein the act of accepting connectivity information further comprises accepting a connectivity graph.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

accepting connectivity information for the network;

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

creating a graph from the connectivity information, wherein

each identified link is represented as a vertex in the graph,

an edge is created between a first vertex and a second vertex in the graph if the corresponding wireless links interfere with one another,

a direction is assigned to the edge, and

a weight is assigned to the edge, the weight being 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.