Model and method for computing performance bounds in multi-hop wireless networks
View Patent ↗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.
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.