 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| n |
Determining
all independent link sets is NP-complete, so
|
|
|
heuristically
determine a few (will generate lower bound
|
|
|
on
network capacity)
|
|
|
| n |
Can
modify LP to account for different radio models, rate-
|
|
|
adaptive
MACs, etc.
|
|
|
| n |
Straightforward
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
|
|
| n |
To
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.
|
|
