Thomas Kunz
Systems and Computer Engineering
6
More Complex Networks
nDetermining all independent link sets is NP-complete, so
heuristically determine a few (will
generate lower bound on network
capacity)
nCan modify LP to account for different radio models,
rate-adaptive MACs, etc.
nStraightforward to extend to multiple flows
ØFor N nodes, S flows, and M independent sets, the
maximum number of variables
will be (N-1)*(N-1)*S + S + M, and N*S + M + 1 constraints
nTo model actual network, numbers depend on topology:
Ø100 nodes in a 1500 m x 1500 m area and 50 flows,
attempting to find 10,000
independent scheduling sets: the maximum number of variables is 500,100, with 15,001 constraints. Using
randomly generated static
topologies, we counted between 46,000 to 70,000 variables and around 5,200-5,700 constraints.