| 摘要 |
A method of routing data from a source node to a destination node in a multi-hop network of nodes interconnected by links comprises: (a) determining that a link-flow vector satisfies one or more necessary scheduling conditions for achievability, wherein the link-flow vector represents a set of flows to be routed on one or more links from the source node to the destination node; (b) generating a scheduling multi-graph for the network, wherein the scheduling multi-graph comprises a graph having at least one pair of nodes with multiple edges therebetween; (c) deriving one or more sufficient scheduling conditions for achievability of the link-flow vector by edge-coloring the scheduling multi-graph; (d) solving a linear optimization problem over the one or more necessary scheduling conditions to obtain an upper bound on the achievability of the link-flow vector; (e) generating, based on the scheduling multi-graph, a solution comprising a set of routes and an associated schedule for achieving the link-flow vector, the solution being a lower bound on the achievability of the link-flow vector; and (f) implementing a routing method using the set of routes and the associated schedule to route the link-flow vector from the source node to the destination node. At least one node v of the network is adapted to receive transmissions from a specified plurality Omega(v) of other nodes, and at least one of the scheduling conditions depends on Omega(v).
|
