Digital Signal Processing Reference
In-Depth Information
JFR
i
,
JFR
i
≤
≤
≤
1
i
n(
QoS Constraints
),
(6.6)
n
R
max
R
i
≤
(
Resource Constraints
),
(6.7)
i
=
1
K
i
,S
i,m
→
R
i
,
1
≤
m
≤
s
Resource Profiles
),
(6.8)
K
i
,S
i,m
→
C
i
(
Cost Profiles
),
(6.9)
Q
i
(
Quality Profiles
).
(6.10)
The solution of the optimization problem yields a set of feasible operating points,
K
K
i
,S
i,m
→
, for the network which fulfill the QoS target, maintain the
shared resource constraint and minimize the system cost. While the profile mapping
and pruning is done during a one-time calibration step, we now propose how the
optimal configuration
={
K
i
,
1
≤
i
≤
n
}
K
is determined efficiently at run-time using those profiles.
6.3.2 Greedy Resource Allocation
As the current system state of all the nodes and flows is only known at run-time,
a light-weight scheme is necessary to assign the best system configurations for each
user, while meeting the QoS requirements. We therefore employ a greedy algorithm
to determine the per-flow resource usage
R
i
for each flow to minimize the total
cost
C
net
while meeting the system constraints. The algorithm first constructs the
optimal local Cost-Resource trade-off curve
C
i
(R
i
)
by taking the optimal points in
both dimensions that meet the run-time average quality constraint
JFR
∗
. Next, the
scheduler traverses all flows' two-dimensional Cost-Resource curves and at every
step consumes resources corresponding to the maximum negative slope across all
flows (taking into account user preference or weight if appropriate). This ensures
that for every additional unit of resources consumed, the additional cost saving is
the maximum across all flows taking into account the agreements made at admission
time. We assume that the current channel states and application demands are known.
The exchange of state information and operating points between nodes and the AP
is obtained by coupling the MAC protocol with the resource manager as explained
in the next section.
We determine the optimal additional allocation to each flow,
R
i
>
0, 1
≤
i
≤
n
,
subject to
i
=
1
R
i
≤
R
. Our greedy algorithm is based on Kuhn-Tucker [87]:
1. Allocate to each flow the smallest resource for the given state,
R
min
. By assump-
tion, all flows are schedulable under worst-case conditions, i.e.,
i
=
1
R
min
≤
R
.
≤
≤
2. Let the current normalized allocation of the resource to flow
F
i
be
R
i
,1
i
n
.
Let the unallocated quantity of the available resource be
R
avl
.
3. Identify the flow with the maximum negative slope,
|
C
i
(R
i
)
|
, representing the
maximum decrease in cost per resource unit (i.e. moving right and downward
the
C
i
(R
i
)
convex minorant in Fig.
6.10
). If there is more than one, pick one
randomly. If the value of the minimum slope is 0, then stop. No further allocation
will decrease the system cost further.
