Digital Signal Processing Reference
In-Depth Information
Fig. 6.10
Bounded deviation
from the optimal in discrete
Cost-Resource curves
4. Increase
R
i
by the amount till the slope changes for the
i
th flow. Decrement
R
avl
by the additional allocated resource and increment the cost
C
by the consequent
additional cost. Return to step 3 until all resources have been optimally allocated
or when
R
avl
is 0.
In our implementation, we sort the configuration points at design-time in the de-
creasing order of the negative slope between two adjacent points. The complexity
of the run-time algorithm is
O(Ln
log
(n))
for
n
nodes
(
∼
20
)
and
L
configuration
points per curve. Further in this chapter, we demonstrate that for a practical system
in each possible system state (i.e., channel and frame size), the number of config-
uration points to be considered at run-time is relatively small
(
30
)
. Taking into
account that the relation
C
i
(R
i
)
is convex, we now prove that the greedy algorithm
leads to the optimal solution for continuous resource allocation. Following that, we
extend the proof for systems with discrete working points to show that the solution
is within a bound from the optimal.
∼
Theorem 4.1
For a continuous resource allocation to be optimal
,
a necessary con-
dition is
∀
i
,1
≤
i
≤
n
,
R
i
=
0,
or for any flows
{
i, j
}
with R
i
>
0
and R
j
>
0,
the
cost slopes C
i
(R
i
)
C
j
(R
j
)
.
=
Proof
For a continuous differentiable function, the Kuhn-Tucker [87] theorem
proves such a greedy scheme is optimal. Suppose for some
i
=
j
, let the optimal
C
i
(R
i
)
C
j
(R
j
)
resources be
R
i
>
0,
R
j
>
0, and
. As the savings in cost per
resource for
F
i
is larger, we can subtract an infinitesimal amount of resource from
F
j
and add it to
F
i
. Total system cost is reduced, contradicting the assumed opti-
mality.
|
|
>
|
|
In a real system, however, the settings for different control dimensions such as
modulation or transmit power are discrete. This results in a deviation,
, from the
optimal resource assignment. We now show this worst-case deviation
from the
optimal strategy is bounded and small.
