# Minimizing the Average Waiting Time of Unequal-Size Data Items in a Mobile Computing Environment

Authors: Jen-Ya Wang
Journal: Mobile Information Systems
 (2016)

---

## Abstract

In a mobile computing environment, waiting time is an important indicator of customer satisfaction. In order to achieve better customer satisfaction and shorter waiting times, we need to overcome different constraints and make the best use of limited resources. In this study, we propose a minimization problem, allocating unequal-size data items to broadcast channels with various bandwidths. The main idea is to solve the problem in the continuous spaceR
n. First, we map the discrete optimization problem from Z
n to R
n. Second, the mapped problem is solved in R
n optimally. Finally, we map the optimal solution from R
n back to Z
n. With the theoretical analyses, we can ensure the solution quality and execution speed. Computational experiments show that the proposed algorithm performs well. The worst mean relative error can be reduced to 0.353 for data items with a mean size of 100. Moreover, almost all the near-optimal solutions can be obtained within 1 millisecond, even for N
=
500, where N is the number of data items, that is, the problem size.


---

## Body

## 1. Introduction

Broadcasting is an efficient mechanism to transmit information in a mobile computing environment. Popular messages (e.g., weather reports) or instant information (e.g., stock quotes) can be widely disseminated via the broadcast mechanism. This success is mainly due to the high bandwidths of downlinks, which are used for the transmission of data items from a broadcast server to unlimited mobile users. Note that the bandwidths of channels and the sizes of data items might be unequal. The simplest strategy is to equally allocate data items to all channels, or load balance, but it is not the best way to reduce waiting time. Consequently, sophisticated broadcast scheduling or data partition algorithms are called for.Waiting time, or expected delay, is an important indicator for measuring broadcast performance, for the waiting times of mobile users directly influence their customer satisfaction [1–5]. For example, Chien and Lin [3] found that customers’ waiting experiences may negatively affect their attitudes towards a given service. Moreover, improving the service implies the improvement of user experiences. Therefore, a good broadcast mechanism that is able to reduce waiting time can achieve better customer satisfaction.Let us observe the simplest form of such problems, that is,∑
i
∑
j
a
j
∑
j
1. These problems feature single-item queries, multiple channels, and skewed data preferences. Several equal-bandwidth broadcast channels and multiple equal-size data items need to be broadcast over multiple channels periodically. In a mobile computing environment, users can download their desired items via their mobile devices, such as smartphones. Imagine that we allocate a few popular items to a channel, that is, a short cycle length, and other ordinary items to another channel, that is, a long cycle length. Most users can download popular items in a short time, without a long wait. Clearly, access probability and cycle length directly influence broadcast scheduling. Note the unbalanced workloads of these channels (i.e., the different amounts of data) in an optimal allocation. Once the optimal schedule is found, we can achieve shorter waiting times and better customer satisfaction. However, determining optimal schedules requires much execution time. That is, the time complexity excludes the related optimization algorithms from practical use.Now we consider some complicated forms of such problems, that is,∑
i
∑
j
a
j
∑
j
b
j. These problems may have unequal-size data items or various bandwidths. There are still multiple channels and skewed preferences for data items. For example, in [6], the authors assumed that the bandwidths were different. This consideration makes this problem more difficult. In [7], the authors considered another problem, in which the sizes of data items are unequal. This assumption makes the problem more flexible and practical.In recent years, various other forms have also been studied. In [8], mobile users could download multiple items at a time by sending a simple query. The authors assumed that two queries might have some items in common. To shorten the broadcast cycle length, the duplicate items were centralized and allocated to the same channel. In [9], video was broadcast on a single channel, so the data size was variable. In [10], mobile users could download multiple items in a multichannel environment. However, the wireless links were unreliable, so disconnections occurred frequently. In that study, reducing the waiting time was not the first priority. Instead, the authors aimed to minimize the deadline miss rate. All of the above considerations make the problems more complicated. Obviously, these problems cannot be solved easily or optimally when the problem size is large, so we need some more efficient algorithms to deal with these problems.Such problems are usually time-consuming or even NP-hard, so several intuitive or metaheuristic algorithms have been proposed. However, traditional algorithms have some shortcomings. For example, although dynamic programming [7, 12] and branch-and-bound algorithms [13, 14] can provide optimal solutions, they are time-consuming and cannot be applied to large problem instances; for example, N
=
500. On the other hand, some metaheuristic algorithms [8] or greedy approaches [12, 15, 16] generate solutions very quickly. Nevertheless, their solution qualities are not stable. The reason is that their searches are done by random walks in their solution spaces. For the same problem instance, multiple executions of an identical algorithm can generate different solutions. Moreover, as in the case of tabu search, a great amount of memory is needed for keeping track of past experiences. Such algorithms are also unsuitable for large problem instances.In this study, we consider a waiting time minimization problem (abbreviated as WTM). To make this problem more flexible and practical, meaning that unequal bandwidths and various data sizes are allowed, we propose a linearly convergent algorithm based on a steepest decent technique. First, WTM is mapped fromZ
n (the discretized space) to R
n (the continuous space). Next, WTM′ in R
n is solved optimally in linear time. Finally, the optimal solution is mapped from R
n back to Z
n.The rest of this study is organized as follows. Section2 gives the formal definition of the proposed problem. Section 3 establishes the theoretical basis for the problem. Section 4 presents the linearly convergent algorithm. This study is compared with past research in Section 5. In Section 6, computational experiments are conducted to evaluate the performance of the proposed algorithm. Finally, conclusions are drawn in Section 7.


## 2. Problem Formulation

The waiting time minimization problem (WTM) is formulated as follows. There is a databaseD
=
{
d
1
,
d
2
,
…
,
d
N
} to be broadcast in a mobile computing environment, where d
jis the jth data item for j
=
1,2
,
…
,
N. Let p
j and λ
j denote the access probability and the size of d
j, respectively. The total amount of data is Λ
(
=
∑
j
=
1
N
λ
j
). Assume that the access pattern S, that is, the sequence of (
p
j
,
λ
j
), is given in advance. Assume that a broadcast server is equipped with C channels, numbered from 1 to C. We let the bandwidth of channel i be w
i. Without loss of generality, assume that w
i
≥
w
j for all i
<
j. Each channel is divided into time slices of equal size, called buckets. We need to partition D into C parts based on the access pattern S and assign each part to one of the C channels, one item to several consecutive buckets. Then C broadcast programs are formed, and each of them will be broadcast cyclically. The average waiting time is defined as the average amount of waiting time spent by each user before he/she receives the desired data item. Finally, the objective is to minimize the average waiting time of the C programs under the above assumptions. The objective function can be written as min∑
i
=
1
C
[
(
∑
d
j
∈
M
i
λ
j
)
(
∑
d
j
∈
M
i
p
j
)
/
w
i
], where d
j
∈
M
i means d
j is allocated to channel i or machine i.Three properties regarding WTM are discussed as follows. First, for each single channeli, its corresponding broadcast program cycle length is Λ
i
=
∑
d
j
∈
M
i
λ
j. Then the expected waiting time in receiving d
j on the channel is (
0.5
Λ
i
+
λ
j
)
/
w
i. If Λ
i is much larger than λ
j, the expected waiting time can be simplified to 0.5
Λ
i
/
w
i. Namely, the position order of data items makes no difference on the final result, that is, the average waiting time. Second, the average waiting time can be determined only by data partition. That is, the average waiting time is the weighted sum of the average waiting time on each channel, that is, 0.5
∑
i
=
1
C
(
Λ
i
∑
d
j
∈
M
i
p
j
)
/
w
i. Third, such minimization problems are time-consuming or even NP-hard [6, 16, 17]. Consequently, some efficient minimization algorithms are called for. With the above observation, we can define proper objective functions in the next section.


## 3. Theoretical Basis

In this section, a steepest decent technique is employed to solve the problem. First, we map the WTM problem fromZ
n to a new problem WTM′ in R
n. Second, we employ a steepest decent technique [11, 18] to obtain the optimal solution to WTM′ in R
n. Finally, we map the optimal solution from R
n back to Z
n. The main idea behind the transformation is to improve the solution quality and execution speed. Although WTM can be solved optimally by some optimization algorithms (e.g., a branch-and-bound algorithm) in Z
n, it is too time-consuming when N is large. On the other hand, though some metaheuristic algorithms (e.g., GA) are able to provide instant solutions in Z
n, their solution quality is not guaranteed. For the same problem instance, they may provide different solutions. Consequently, instead of directly optimizing WTM in Z
n, we map WTM to R
n and take advantage of the linear convergence and optimality of the gradient-based technique in R
n.The parameters used in this study are summarized in Parameters at the end of the paper. ParametersN, C, and S are defined earlier. Parameters S
0 and S
1 are the access patterns used in different spaces, that is, Z
n and R
n. We also need two cumulative functions, P
(
j
), Q
(
j
), and two interpolating functions, F
(
x
), H
(
x
), to define the objective functions α
S
(
n
) in R
n and  β
S
(
x
) in Z
n, respectively. Moreover, n
∈
Z
n and x
∈
R
n are partition vectors or position vectors.


### 3.1. Mapping WTM fromZ
n to R
n

First, two objective functions for both WTM and WTM′ are defined. Then we show how to map WTM fromZ
n to WTM′ in R
n. Finally, we prove that the geometric properties, such as concavity, of both WTM and WTM′ are similar. These proofs ensure that both solution spaces are close to each other.The relationship between WTM and WTM′ is similar to that between the 0-1 knapsack problem and the fractional knapsack problem [19]. If we can solve the problems in R
n optimally, then the rounded solutions mapped back to Z
n are therefore near-optimal solutions to the original problems. To show this relationship, two proper objective functions play an important role. Namely, the objective functions of WTM and WTM′ must resemble each other. Once the two similar objective functions are determined, we can claim that the optimal solution of WTM′ is very close to that of WTM.Definition1 helps us to transform thedata partition problem into asequence partition problem. Since the position order of an access pattern will lead to different results, we need the following definition to help us to ensure the optimality of WTM and WTM′.Definition 1.
Given an optimal solution, theC programs can be concatenated into an optimal program. Let S
0 denote the sequence of (
p
i
,
λ
i
) that has the same order as the optimal program for WTM. Similarly, let S
1 denote the sequence of (
p
i
,
λ
i
) that has the same order as the optimal program for WTM′.WTM and WTM′ have different preferences for the order of access pattern. Consider the relationship between the 0-1 knapsack problem and the fractional knapsack problem again. For the fractional knapsack problem, if we take the items of greatest unit value one by one in a preemptive manner, we can easily achieve the maximum objective cost [19]. Thus we try to solve the continuous-case WTM′ by sorting the items d
i in descending order of (
p
i
/
λ
i
). That is, the sequence S
1 is obtained by sorting (
p
i
/
λ
i
) in nonincreasing order. On the other hand, for the 0-1 knapsack problem, we may achieve the optimal solution but sacrifice some valuable items because they are too big to fit the knapsack. Clearly, the optimal item partition of the 0-1 knapsack problem cannot be solved by using simple sorting rules. That is, when we reduce an item partition problem to a sequence partition problem, it is difficult to determine the optimal sequence for partition. Consequently, we do not aim to find the optimal sequence S
0 for WTM. Instead, we just use S
1 for WTM′ to simulate S
0.Definitions2 and 3 introduce two cumulative functions regarding the access pattern S. With the two cumulative functions, we can define a new objective function in R
n in a more comprehensive way for later transformation.Definition 2.
GivenS, the function P
(
j
) of cumulative probability is defined by(1)
P
j
=
∑
k
=
1
j
p
k
,
1
≤
j
≤
N
,
0
,
j
=
0
.
Similarly, we define another function to express the cycle length of a broadcast program. The functionQ
(
j
) is defined as follows.Definition 3.
GivenS, the function Q
(
j
) of the cumulative data size is defined by(2)
Q
j
=
∑
k
=
1
j
λ
k
,
1
≤
j
≤
N
,
0
,
j
=
0
.
Now we redefine the objective function for the original problem WTM inZ
n. The original objective function ∑
i
=
1
C
[
(
∑
d
j
∈
M
i
λ
j
)
(
∑
d
j
∈
M
i
p
j
)
/
w
i
] is defined from the viewpoint ofdata partition, whereas the new objective function is formulated from the viewpoint ofsequence partition. With the cumulative functions P
(
j
) and Q
(
j
), we can determine a proper sequence in advance and then perform partition on the sequence. For simplicity, the leading coefficient of expected waiting time of each channel, 0.5, is omitted in the rest of this study.Definition 4.
GivenS and two constants n
0
=
0, n
C
=
N for any column vector n
=
n
1
,
n
2
,
…
,
n
C
-
1
t
∈
1
,
2
,
…
,
N
C
-
1 with n
i
-
1
≤
n
i, the objective function α
S
(
n
) of WTM is defined by(3)
α
S
n
=
∑
i
=
1
C
Q
n
i
-
Q
n
i
-
1
P
n
i
-
P
n
i
-
1
w
i
,where w
i is the bandwidth of channel i.Note that data items numberedn
i
-
1
+
1
,
n
i
-
1
+
2
,
…
,
n
i are allocated to channel i. Therefore, the access probability of channel i is P
(
n
i
)
-
P
(
n
i
-
1
) and the program cycle length of the channel is Q
(
n
i
)
-
Q
(
n
i
-
1
).An interpolating functionF
(
x
) regarding access probability is defined for mapping WTM from Z
n to R
n. To preserve the geometric properties, we interpolate the N
+
1 points (
j
,
P
(
j
)
), j
=
0
,
1
,
…
,
N, by using N separate line segments. The interpolating function F
(
x
) is defined as follows.Definition 5.
Forj
=
1
,
2
,
…
,
N, consider the jth interval [
j
-
1
,
j
] and let the straight line f
j
(
x
) pass through the two points (
j
-
1
,
P
(
j
-
1
)
) and (
j
,
P
(
j
)
). The interpolating function F
(
x
) is given by (4)
F
x
=
f
1
x
,
if
x
∈
0,1
,
f
2
x
,
if
x
∈
1,2
,
⋮
f
N
-
1
x
,
if
x
∈
N
-
2
,
N
-
1
,
f
N
x
,
if
x
∈
N
-
1
,
N
.
An interpolating functionH
(
x
) regarding program cycle length is also defined as follows. We let it interpolate the N
+
1 points (
j
,
Q
(
j
)
), j
=
0
,
1
,
…
,
N, by using N separate line segments.Definition 6.
Forj
=
1
,
2
,
…
,
N, consider the jth interval [
j
-
1
,
j
] and let the straight line h
j
(
x
) pass through the two points (
j
-
1
,
Q
(
j
-
1
)
) and (
j
,
Q
(
j
)
). The interpolating function H
(
x
) is given by (5)
H
x
=
h
1
x
,
if
x
∈
0,1
,
h
2
x
,
if
x
∈
1,2
,
⋮
h
N
-
1
x
,
if
x
∈
N
-
2
,
N
-
1
,
h
N
x
,
if
x
∈
N
-
1
,
N
.
Just as we define the objective functionα
S
(
n
) for WTM in Z
n, we define a dummy objective function β
S
(
x
) for WTM′ in R
n as follows.Definition 7.
GivenS and two constants x
0
=
0, x
C
=
N, for any position vector x
=
x
1
,
x
2
,
…
,
x
C
-
1
t
∈
0
,
N
C
-
1 with x
i
-
1
<
x
i, the objective function β
S
(
x
) of WTM′ is defined by(6)
β
S
x
=
∑
i
=
1
C
H
x
i
-
H
x
i
-
1
F
x
i
-
F
x
i
-
1
w
i
,where F
(
x
), Q
(
x
) are the interpolating functions and w
i is the bandwidth of channel i.Sinceα
S
(
n
) and β
S
(
x
) have the same objective costs at all grid points, the solution spaces of WTM and WTM′ are of similar geometric properties, for example, slope, extreme, and concavity. Lemma 8 shows that both functions agree with each other at all grid points.Lemma 8.
GivenS, for any n
∈
1
,
2
,
…
,
N
C
-
1, α
S
(
n
)
=
β
S
(
n
)
.Proof.
Note thatf
j
+
1
(
j
)
=
P
(
j
) and h
j
+
1
(
j
)
=
Q
(
j
) for all j
=
1
,
2
,
…
,
N. Then (7)
β
S
n
=
∑
i
=
1
C
H
n
i
-
H
n
i
-
1
F
n
i
-
F
n
i
-
1
w
i
=
∑
i
=
1
C
H
n
i
-
H
n
i
-
1
f
n
i
+
1
n
i
-
f
n
i
-
1
+
1
n
i
-
1
w
i
by Definition
5
=
∑
i
=
1
C
h
n
i
+
1
n
i
-
h
n
i
-
1
+
1
n
i
-
1
f
n
i
+
1
n
i
-
f
n
i
-
1
+
1
n
i
-
1
w
i
by Definition
6
=
∑
i
=
1
C
Q
n
i
-
Q
n
i
-
1
P
n
i
-
P
n
i
-
1
w
i
=
α
S
n
.The proof is complete.By Lemma8, α
S
(
n
) and β
S
(
x
) have the same function values at grid points. That is, they have similar geometric properties. Therefore, the optimal solution to WTM in Z
n is close to that of WTM′ in R
n. The optimal solutions to WTM and WTM′ are also close to each other.


### 3.2. Optimal Solutionx
∗ to WTM′

In this subsection, we solve WTM′ optimally and obtain the optimal solutionx
∗ in R
n. First, we introduce the concept of gradient. Then the optimality and convergence speed are discussed.The steepest decent technique we employed is based on the concept of the gradient [11]. Unlike other metaheuristic algorithms, the steepest decent technique always converges at the global minimum instead of piecing several local minimums. Moreover, this steepest decent technique converges in n dimensions in linear time instead of performing meaningless random walks. The notation of the gradient is defined as follows.Definition 9.
Letg: R
n
→
R be a continuous differentiable multivariable function. The gradient of g at x
=
x
1
,
x
2
,
…
,
x
n
t is denoted by ∇
g
(
x
) and defined by(8)
∇
g
x
=
∂
g
x
∂
x
1
,
∂
g
x
∂
x
2
,
…
,
∂
g
x
∂
x
n
t
.
BecauseF
(
x
) is not differentiable at x
=
0
,
1
,
2
,
…
,
N
-
1, we remedy this shortcoming by improper limit. The ith element of ∇
g
(
x
) is modified slightly and redefined as(9)
∂
g
x
∂
x
i
=
l
i
m
h
→
0
+
g
x
1
,
x
2
,
…
,
x
i
+
h
,
…
,
x
C
-
1
-
g
x
1
,
x
2
,
…
,
x
i
,
…
,
x
C
-
1
h
,
if
x
i
is an integer
,
l
i
m
h
→
0
g
x
1
,
x
2
,
…
,
x
i
+
h
,
…
,
x
C
-
1
-
g
x
1
,
x
2
,
…
,
x
i
,
…
,
x
C
-
1
h
,
otherwise
.Note that F
(
x
) and H
(
x
) are therefore right-hand differentiable for x
∈
{
0
,
1
,
2
,
…
,
N
-
1
}. Thus, the gradient of  β
S
(
x
) can be obtained for any x
∈
0
,
N
C
-
1, and the ith element of ∇
β
S
(
x
) becomes(10)
∂
β
S
x
∂
x
i
=
1
w
i
H
′
x
i
F
x
i
-
F
x
i
-
1
+
H
x
i
-
H
x
i
-
1
F
′
x
i
-
1
w
i
+
1
H
′
x
i
F
x
i
+
1
-
F
x
i
+
H
x
i
+
1
-
H
x
i
F
′
x
i
=
1
w
i
λ
b
F
x
i
-
F
x
i
-
1
+
H
x
i
-
H
x
i
-
1
p
b
-
1
w
i
+
1
λ
b
F
x
i
+
1
-
F
x
i
+
H
x
i
+
1
-
H
x
i
p
b
=
1
w
i
λ
b
P
b
+
x
i
-
b
p
b
+
1
-
P
a
+
x
i
-
1
-
a
p
a
+
1
+
Q
b
+
x
i
-
b
λ
b
+
1
-
Q
a
+
x
i
-
1
-
a
λ
a
+
1
p
b
-
1
w
i
+
1
λ
b
P
c
+
x
i
+
1
-
c
p
c
+
1
-
P
b
+
x
i
-
b
p
b
+
1
+
Q
c
+
x
i
+
1
-
c
λ
c
+
1
-
Q
b
+
x
i
-
b
λ
b
+
1
p
b for three integers a
≤
b
≤
c with x
i
-
1
∈
[
a
,
a
+
1
), x
i
∈
[
b
,
b
+
1
), and x
i
+
1
∈
[
c
,
c
+
1
). More specifically, when programming, we do not need to find the derivative of H
(
x
i
) for obtaining the corresponding slope. Instead, we obtain the slope λ
b by letting x
i
=
b. Hence, we eliminate annoying differentiation procedures in the proposed algorithm.Similar algorithms are found in [2, 11, 20, 21]. We can modify them slightly in order to obtain the optimal solution x
∗ in R
n. The details of the algorithm will be presented in the next section. Here, we show only the basic steps of the steepest decent technique as follows:(1)
Evaluateβ
S
(
x
) at an initial position x
(
0
).
(2)
Determine the steepest decent direction fromx
(
0
) that results in a decrease in the value of β
S.
(3)
Move an appropriate amountδ (i.e., step size) in this direction, and the new position is x
(
1
).
(4)
Setx
(
1
)
=
x
(
0
)
-
δ
∇
β
S
(
x
(
0
)
).
(5)
Repeat steps (1) through (4) until the optimal solutionx
∗ is obtained.In order to implement the algorithm easily, we reduce the equation (11)
x
1
=
x
0
-
δ
∇
β
S
x
0to a single variable function(12)
v
δ
=
β
S
x
0
-
δ
∇
β
S
x
0
.Note that the value δ
0 that minimizes v
(
δ
) is also the value needed for (11). Because the root-finding process in (12) requires much execution time, Burden and Faires [11] employed a quadratic polynomial to interpolate v
(
δ
) in order to accelerate the root-finding process. The details regarding the quadratic polynomial will be shown in the next section.The proposed algorithm converges linearly and the proofs of convergence are omitted. Readers can refer to [11, 18]. Even if this algorithm converges rapidly, an accurate initial solution can accelerate the convergence speed more. The following definition and lemma help us to choose an accurate initial solution.Definition 10.
Letx
0
=
0, x
C
=
N be two constants. For any position vector x
=
x
1
,
x
2
,
…
,
x
C
-
1
t
∈
0
,
N
C
-
1, the length of the ith interval [
x
i
-
1
,
x
i
] is denoted by Δ
x
i and defined by(13)
Δ
x
i
=
x
i
-
x
i
-
1for i
=
1
,
2
,
…
,
C. Likewise, the difference of H caused by Δ
x
i is defined by(14)
Δ
H
i
=
H
x
i
-
H
x
i
-
1for i
=
1
,
2
,
…
,
C.
The following lemma shows how to obtain an accurate initial solution by determining the elements of a position vector or partition vectorx.Lemma 11.
If the optimal solutionx
∗ to the dummy objective function β
S
1
(
x
) is given, then Δ
H
i
∗
/
w
i
≤
Δ
H
i
+
1
∗
/
w
i
+
1 for i
=
1
,
2
,
…
,
C
-
1.Proof.
We show it by contradiction. SupposeΔ
H
i
∗
/
w
i
>
Δ
H
i
+
1
∗
/
w
i
+
1 for some i. Since x
∗ is the optimal solution to β
S
1
(
x
), the sum of products(15)
S
∗
=
H
x
i
∗
-
H
x
i
-
1
∗
F
x
i
∗
-
F
x
i
-
1
∗
w
i
+
H
x
i
+
1
∗
-
H
x
i
∗
F
x
i
+
1
∗
-
F
x
i
∗
w
i
+
1 should be the minimal in the interval [
x
i
-
1
∗
,
x
i
+
1
∗
]. On the other hand, since Δ
H
i
∗
/
w
i
>
Δ
H
i
+
1
∗
/
w
i
+
1, there exists a number x
i
<
x
i
∗ such that (
H
(
x
i
)
-
H
(
x
i
-
1
∗
)
)
/
w
i
=
(
H
(
x
i
+
1
∗
)
-
H
(
x
i
)
)
/
w
i
+
1. We claim that(16)
S
=
H
x
i
-
H
x
i
-
1
∗
F
x
i
-
F
x
i
-
1
∗
w
i
+
H
x
i
+
1
∗
-
H
x
i
F
x
i
+
1
∗
-
F
x
i
w
i
+
1
<
S
∗
.Let H
(
x
i
∗
)
-
H
(
x
i
-
1
∗
)
=
a, F
(
x
i
∗
)
-
F
(
x
i
-
1
∗
)
=
A, H
(
x
i
+
1
∗
)
-
H
(
x
i
∗
)
=
b, F
(
x
i
+
1
∗
)
-
F
(
x
i
∗
)
=
B, H
(
x
i
∗
)
-
H
(
x
i
)
=
δ, F
(
x
i
∗
)
-
F
(
x
i
)
=
Δ, and (
H
(
x
i
)
-
H
(
x
i
-
1
∗
)
)
/
w
i
=
(
H
(
x
i
+
1
∗
)
-
H
(
x
i
-
1
)
)
/
w
i
+
1
=
π. Since the sequence S
1 is sorted by (
p
i
/
λ
i
) in descending order, Δ
H
i
∗
/
w
i
>
Δ
H
i
+
1
∗
/
w
i
+
1 implies that (
F
(
x
i
∗
)
-
F
(
x
i
-
1
∗
)
)
/
w
i
>
(
F
(
x
i
+
1
∗
)
-
F
(
x
i
∗
)
)
/
w
i
+
1. That is, if a
/
w
i
>
b
/
w
i
+
1, then A
/
w
i
>
B
/
w
i
+
1. Then(17)
S
=
1
w
i
a
-
δ
A
-
Δ
+
1
w
i
+
1
b
+
δ
B
+
Δ
=
π
A
-
Δ
+
π
B
+
Δ
=
π
A
+
π
B
=
1
w
i
a
-
δ
A
+
1
w
i
+
1
b
+
δ
B
=
a
A
w
i
+
b
B
w
i
+
1
-
δ
A
w
i
+
δ
B
w
i
+
1
<
a
A
w
i
+
b
B
w
i
+
1
=
S
∗
.It contradicts that x
∗ is the optimal solution. The proof is complete.By the above lemma, the proposed algorithm is therefore able to start from a better initial positionx
(
0
). We find x
1
(
0
)
,
x
2
(
0
)
,
…, and x
C
-
1
(
0
) such that Δ
H
i
∗
/
w
i
≤
Δ
H
i
+
1
∗
/
w
i
+
1
=
Λ
/
W, where W
=
∑
i
=
1
C
w
i. In the next section, we set x
(
0
)
=
x
1
0
,
x
2
0
,
…
,
x
C
-
1
0
t instead of randomly choosing x
(
0
). This initial position will also enhance the convergence speed.Note that the partition vectorx
∗ is aglobal minimizer of WTM′. We prove this property by showing that β
S
1
(
x
) is concave upward for all x
∈
0
,
N
C
-
1. Namely, for any initial vector, the algorithm converges to the global minimum.Lemma 12.
Let the algorithm converge locally at somex
∗
∈
0
,
N
C
-
1. Then x
∗ is the global optimal solution to WTM′.Proof.
We prove the property by showing that, for anyx
∈
0
,
N
C
-
1, β
S
1
(
x
) is concave upward. From (10), we get(18)
∂
β
S
1
x
∂
x
i
=
1
w
i
H
′
x
i
F
x
i
-
F
x
i
-
1
+
H
x
i
-
H
x
i
-
1
F
′
x
i
-
1
w
i
+
1
H
′
x
i
F
x
i
+
1
-
F
x
i
+
H
x
i
+
1
-
H
x
i
F
′
x
i
,for i
=
1
,
2
,
…
,
C
-
1. Note that x
0
=
0 and x
C
=
N are two constants. Then the second partial derivative is(19)
∂
β
S
1
2
x
∂
x
i
2
=
1
w
i
H
′
′
x
i
F
x
i
-
F
x
i
-
1
+
2
H
′
x
i
F
′
x
i
+
H
x
i
-
H
x
i
-
1
F
′
′
x
i
-
1
w
i
+
1
H
′
′
x
i
F
x
i
+
1
-
F
x
i
-
2
H
′
x
i
H
′
x
i
+
H
x
i
+
1
-
H
x
i
F
′
′
x
i
=
2
w
i
H
′
x
i
F
′
x
i
+
2
w
i
+
1
H
′
x
i
H
′
x
i
.Because F
(
x
) interpolates the strictly increasing function P
(
i
), it is clear that F
′
(
x
)
>
0. We have F
′
′
(
x
)
=
0, since F
(
x
) is composed of straight lines. Similarly, H
(
x
) has the same properties. Therefore, ∂
β
S
1
2
(
x
)
/
∂
x
i
2
>
0 for all x
∈
0
,
N
C
-
1. The proof is complete.


### 3.3. Near-Optimal Solutionn
† to WTM

We show how to obtain a near-optimal solution of WTM in this subsection. First, we remap the optimal solutionx
∗ in R
n back to Z
n by rounding off all elements of x
∗, and a rounded solution n
†
∈
1,2
,
…
,
N
C
-
1 is obtained. The following lemma shows the magnitude order of β
S
1
(
x
∗
), α
S
0
(
n
∗
), α
S
1
(
n
#
), and α
S
1
(
n
†
), where n
#
∈
1,2
,
…
,
N
C
-
1 minimizes α
S
1
(
n
) and n
∗
∈
1,2
,
…
,
N
C
-
1 minimizes α
S
0
(
n
).Lemma 13.
Letn
†
∈
1,2
,
…
,
N
C
-
1 be the rounded resulting solution to WTM. Then β
S
1
(
x
∗
) and α
S
1
(
n
†
) are two bounds of α
S
0
(
n
∗
) with(20)
β
S
1
x
∗
≤
α
S
0
n
∗
≤
α
S
1
n
#
≤
α
S
1
n
†
,and the Euclidean distance between x
∗ and n
† is(21)
x
∗
-
n
†
2
≤
0.5
C
-
1
.Proof.
Sincen
# minimizes α
S
1
(
n
)
,
α
S
1
(
n
#
)
≤
α
S
1
(
n
†
). On the other hand, we need to show α
S
0
(
n
∗
)
≤
α
S
1
(
n
#
). Note that S
0 is the optimal sequence to the discrete-case problem WTM and that it is difficult to determine. We just assume that n
∗ is the optimal solution to α
S
0
(
n
). Since S
1 is obtained by some simple sorting rule and dedicated to the continuous-case problem WTM′, the sequence S
0 is more suitable for the discrete-case objective function, α
S
(
n
), than S
1. Therefore, we obtain α
S
0
(
n
∗
)
≤
α
S
1
(
n
#
).
We showβ
S
1
(
x
∗
)
≤
α
S
0
(
n
∗
) by contradiction. Suppose α
S
0
(
n
∗
)
<
β
S
1
(
x
∗
). On the other hand, by Lemma 8, β
S
0
(
n
∗
)
=
α
S
0
(
n
∗
), since n
∗
∈
1
,
2
,
…
,
N
C
-
1. Therefore, β
S
0
(
n
∗
)
=
α
S
0
(
n
∗
)
<
β
S
1
(
x
∗
). However, β
S
1
(
x
∗
) is the optimal solution to WTM′. It is a contradiction.
Since eachn
i
† is rounded from x
i
∗, it is obvious that |
x
i
∗
-
n
i
†
|
≤
0.5 and thus x
∗
-
n
†
2
≤
0.5
C
-
1. The proof is complete.By Lemma13, we know that α
S
0
(
n
∗
) is bounded by β
S
1
(
x
∗
) and α
S
1
(
n
†
) or β
S
1
(
n
†
), since α
S
1
(
n
†
)
=
β
S
1
(
n
†
) by Lemma 8. This guarantees that the proposed algorithm will output near-optimal broadcast programs.


## 3.1. Mapping WTM fromZ
n to R
n

First, two objective functions for both WTM and WTM′ are defined. Then we show how to map WTM fromZ
n to WTM′ in R
n. Finally, we prove that the geometric properties, such as concavity, of both WTM and WTM′ are similar. These proofs ensure that both solution spaces are close to each other.The relationship between WTM and WTM′ is similar to that between the 0-1 knapsack problem and the fractional knapsack problem [19]. If we can solve the problems in R
n optimally, then the rounded solutions mapped back to Z
n are therefore near-optimal solutions to the original problems. To show this relationship, two proper objective functions play an important role. Namely, the objective functions of WTM and WTM′ must resemble each other. Once the two similar objective functions are determined, we can claim that the optimal solution of WTM′ is very close to that of WTM.Definition1 helps us to transform thedata partition problem into asequence partition problem. Since the position order of an access pattern will lead to different results, we need the following definition to help us to ensure the optimality of WTM and WTM′.Definition 1.
Given an optimal solution, theC programs can be concatenated into an optimal program. Let S
0 denote the sequence of (
p
i
,
λ
i
) that has the same order as the optimal program for WTM. Similarly, let S
1 denote the sequence of (
p
i
,
λ
i
) that has the same order as the optimal program for WTM′.WTM and WTM′ have different preferences for the order of access pattern. Consider the relationship between the 0-1 knapsack problem and the fractional knapsack problem again. For the fractional knapsack problem, if we take the items of greatest unit value one by one in a preemptive manner, we can easily achieve the maximum objective cost [19]. Thus we try to solve the continuous-case WTM′ by sorting the items d
i in descending order of (
p
i
/
λ
i
). That is, the sequence S
1 is obtained by sorting (
p
i
/
λ
i
) in nonincreasing order. On the other hand, for the 0-1 knapsack problem, we may achieve the optimal solution but sacrifice some valuable items because they are too big to fit the knapsack. Clearly, the optimal item partition of the 0-1 knapsack problem cannot be solved by using simple sorting rules. That is, when we reduce an item partition problem to a sequence partition problem, it is difficult to determine the optimal sequence for partition. Consequently, we do not aim to find the optimal sequence S
0 for WTM. Instead, we just use S
1 for WTM′ to simulate S
0.Definitions2 and 3 introduce two cumulative functions regarding the access pattern S. With the two cumulative functions, we can define a new objective function in R
n in a more comprehensive way for later transformation.Definition 2.
GivenS, the function P
(
j
) of cumulative probability is defined by(1)
P
j
=
∑
k
=
1
j
p
k
,
1
≤
j
≤
N
,
0
,
j
=
0
.
Similarly, we define another function to express the cycle length of a broadcast program. The functionQ
(
j
) is defined as follows.Definition 3.
GivenS, the function Q
(
j
) of the cumulative data size is defined by(2)
Q
j
=
∑
k
=
1
j
λ
k
,
1
≤
j
≤
N
,
0
,
j
=
0
.
Now we redefine the objective function for the original problem WTM inZ
n. The original objective function ∑
i
=
1
C
[
(
∑
d
j
∈
M
i
λ
j
)
(
∑
d
j
∈
M
i
p
j
)
/
w
i
] is defined from the viewpoint ofdata partition, whereas the new objective function is formulated from the viewpoint ofsequence partition. With the cumulative functions P
(
j
) and Q
(
j
), we can determine a proper sequence in advance and then perform partition on the sequence. For simplicity, the leading coefficient of expected waiting time of each channel, 0.5, is omitted in the rest of this study.Definition 4.
GivenS and two constants n
0
=
0, n
C
=
N for any column vector n
=
n
1
,
n
2
,
…
,
n
C
-
1
t
∈
1
,
2
,
…
,
N
C
-
1 with n
i
-
1
≤
n
i, the objective function α
S
(
n
) of WTM is defined by(3)
α
S
n
=
∑
i
=
1
C
Q
n
i
-
Q
n
i
-
1
P
n
i
-
P
n
i
-
1
w
i
,where w
i is the bandwidth of channel i.Note that data items numberedn
i
-
1
+
1
,
n
i
-
1
+
2
,
…
,
n
i are allocated to channel i. Therefore, the access probability of channel i is P
(
n
i
)
-
P
(
n
i
-
1
) and the program cycle length of the channel is Q
(
n
i
)
-
Q
(
n
i
-
1
).An interpolating functionF
(
x
) regarding access probability is defined for mapping WTM from Z
n to R
n. To preserve the geometric properties, we interpolate the N
+
1 points (
j
,
P
(
j
)
), j
=
0
,
1
,
…
,
N, by using N separate line segments. The interpolating function F
(
x
) is defined as follows.Definition 5.
Forj
=
1
,
2
,
…
,
N, consider the jth interval [
j
-
1
,
j
] and let the straight line f
j
(
x
) pass through the two points (
j
-
1
,
P
(
j
-
1
)
) and (
j
,
P
(
j
)
). The interpolating function F
(
x
) is given by (4)
F
x
=
f
1
x
,
if
x
∈
0,1
,
f
2
x
,
if
x
∈
1,2
,
⋮
f
N
-
1
x
,
if
x
∈
N
-
2
,
N
-
1
,
f
N
x
,
if
x
∈
N
-
1
,
N
.
An interpolating functionH
(
x
) regarding program cycle length is also defined as follows. We let it interpolate the N
+
1 points (
j
,
Q
(
j
)
), j
=
0
,
1
,
…
,
N, by using N separate line segments.Definition 6.
Forj
=
1
,
2
,
…
,
N, consider the jth interval [
j
-
1
,
j
] and let the straight line h
j
(
x
) pass through the two points (
j
-
1
,
Q
(
j
-
1
)
) and (
j
,
Q
(
j
)
). The interpolating function H
(
x
) is given by (5)
H
x
=
h
1
x
,
if
x
∈
0,1
,
h
2
x
,
if
x
∈
1,2
,
⋮
h
N
-
1
x
,
if
x
∈
N
-
2
,
N
-
1
,
h
N
x
,
if
x
∈
N
-
1
,
N
.
Just as we define the objective functionα
S
(
n
) for WTM in Z
n, we define a dummy objective function β
S
(
x
) for WTM′ in R
n as follows.Definition 7.
GivenS and two constants x
0
=
0, x
C
=
N, for any position vector x
=
x
1
,
x
2
,
…
,
x
C
-
1
t
∈
0
,
N
C
-
1 with x
i
-
1
<
x
i, the objective function β
S
(
x
) of WTM′ is defined by(6)
β
S
x
=
∑
i
=
1
C
H
x
i
-
H
x
i
-
1
F
x
i
-
F
x
i
-
1
w
i
,where F
(
x
), Q
(
x
) are the interpolating functions and w
i is the bandwidth of channel i.Sinceα
S
(
n
) and β
S
(
x
) have the same objective costs at all grid points, the solution spaces of WTM and WTM′ are of similar geometric properties, for example, slope, extreme, and concavity. Lemma 8 shows that both functions agree with each other at all grid points.Lemma 8.
GivenS, for any n
∈
1
,
2
,
…
,
N
C
-
1, α
S
(
n
)
=
β
S
(
n
)
.Proof.
Note thatf
j
+
1
(
j
)
=
P
(
j
) and h
j
+
1
(
j
)
=
Q
(
j
) for all j
=
1
,
2
,
…
,
N. Then (7)
β
S
n
=
∑
i
=
1
C
H
n
i
-
H
n
i
-
1
F
n
i
-
F
n
i
-
1
w
i
=
∑
i
=
1
C
H
n
i
-
H
n
i
-
1
f
n
i
+
1
n
i
-
f
n
i
-
1
+
1
n
i
-
1
w
i
by Definition
5
=
∑
i
=
1
C
h
n
i
+
1
n
i
-
h
n
i
-
1
+
1
n
i
-
1
f
n
i
+
1
n
i
-
f
n
i
-
1
+
1
n
i
-
1
w
i
by Definition
6
=
∑
i
=
1
C
Q
n
i
-
Q
n
i
-
1
P
n
i
-
P
n
i
-
1
w
i
=
α
S
n
.The proof is complete.By Lemma8, α
S
(
n
) and β
S
(
x
) have the same function values at grid points. That is, they have similar geometric properties. Therefore, the optimal solution to WTM in Z
n is close to that of WTM′ in R
n. The optimal solutions to WTM and WTM′ are also close to each other.


## 3.2. Optimal Solutionx
∗ to WTM′

In this subsection, we solve WTM′ optimally and obtain the optimal solutionx
∗ in R
n. First, we introduce the concept of gradient. Then the optimality and convergence speed are discussed.The steepest decent technique we employed is based on the concept of the gradient [11]. Unlike other metaheuristic algorithms, the steepest decent technique always converges at the global minimum instead of piecing several local minimums. Moreover, this steepest decent technique converges in n dimensions in linear time instead of performing meaningless random walks. The notation of the gradient is defined as follows.Definition 9.
Letg: R
n
→
R be a continuous differentiable multivariable function. The gradient of g at x
=
x
1
,
x
2
,
…
,
x
n
t is denoted by ∇
g
(
x
) and defined by(8)
∇
g
x
=
∂
g
x
∂
x
1
,
∂
g
x
∂
x
2
,
…
,
∂
g
x
∂
x
n
t
.
BecauseF
(
x
) is not differentiable at x
=
0
,
1
,
2
,
…
,
N
-
1, we remedy this shortcoming by improper limit. The ith element of ∇
g
(
x
) is modified slightly and redefined as(9)
∂
g
x
∂
x
i
=
l
i
m
h
→
0
+
g
x
1
,
x
2
,
…
,
x
i
+
h
,
…
,
x
C
-
1
-
g
x
1
,
x
2
,
…
,
x
i
,
…
,
x
C
-
1
h
,
if
x
i
is an integer
,
l
i
m
h
→
0
g
x
1
,
x
2
,
…
,
x
i
+
h
,
…
,
x
C
-
1
-
g
x
1
,
x
2
,
…
,
x
i
,
…
,
x
C
-
1
h
,
otherwise
.Note that F
(
x
) and H
(
x
) are therefore right-hand differentiable for x
∈
{
0
,
1
,
2
,
…
,
N
-
1
}. Thus, the gradient of  β
S
(
x
) can be obtained for any x
∈
0
,
N
C
-
1, and the ith element of ∇
β
S
(
x
) becomes(10)
∂
β
S
x
∂
x
i
=
1
w
i
H
′
x
i
F
x
i
-
F
x
i
-
1
+
H
x
i
-
H
x
i
-
1
F
′
x
i
-
1
w
i
+
1
H
′
x
i
F
x
i
+
1
-
F
x
i
+
H
x
i
+
1
-
H
x
i
F
′
x
i
=
1
w
i
λ
b
F
x
i
-
F
x
i
-
1
+
H
x
i
-
H
x
i
-
1
p
b
-
1
w
i
+
1
λ
b
F
x
i
+
1
-
F
x
i
+
H
x
i
+
1
-
H
x
i
p
b
=
1
w
i
λ
b
P
b
+
x
i
-
b
p
b
+
1
-
P
a
+
x
i
-
1
-
a
p
a
+
1
+
Q
b
+
x
i
-
b
λ
b
+
1
-
Q
a
+
x
i
-
1
-
a
λ
a
+
1
p
b
-
1
w
i
+
1
λ
b
P
c
+
x
i
+
1
-
c
p
c
+
1
-
P
b
+
x
i
-
b
p
b
+
1
+
Q
c
+
x
i
+
1
-
c
λ
c
+
1
-
Q
b
+
x
i
-
b
λ
b
+
1
p
b for three integers a
≤
b
≤
c with x
i
-
1
∈
[
a
,
a
+
1
), x
i
∈
[
b
,
b
+
1
), and x
i
+
1
∈
[
c
,
c
+
1
). More specifically, when programming, we do not need to find the derivative of H
(
x
i
) for obtaining the corresponding slope. Instead, we obtain the slope λ
b by letting x
i
=
b. Hence, we eliminate annoying differentiation procedures in the proposed algorithm.Similar algorithms are found in [2, 11, 20, 21]. We can modify them slightly in order to obtain the optimal solution x
∗ in R
n. The details of the algorithm will be presented in the next section. Here, we show only the basic steps of the steepest decent technique as follows:(1)
Evaluateβ
S
(
x
) at an initial position x
(
0
).
(2)
Determine the steepest decent direction fromx
(
0
) that results in a decrease in the value of β
S.
(3)
Move an appropriate amountδ (i.e., step size) in this direction, and the new position is x
(
1
).
(4)
Setx
(
1
)
=
x
(
0
)
-
δ
∇
β
S
(
x
(
0
)
).
(5)
Repeat steps (1) through (4) until the optimal solutionx
∗ is obtained.In order to implement the algorithm easily, we reduce the equation (11)
x
1
=
x
0
-
δ
∇
β
S
x
0to a single variable function(12)
v
δ
=
β
S
x
0
-
δ
∇
β
S
x
0
.Note that the value δ
0 that minimizes v
(
δ
) is also the value needed for (11). Because the root-finding process in (12) requires much execution time, Burden and Faires [11] employed a quadratic polynomial to interpolate v
(
δ
) in order to accelerate the root-finding process. The details regarding the quadratic polynomial will be shown in the next section.The proposed algorithm converges linearly and the proofs of convergence are omitted. Readers can refer to [11, 18]. Even if this algorithm converges rapidly, an accurate initial solution can accelerate the convergence speed more. The following definition and lemma help us to choose an accurate initial solution.Definition 10.
Letx
0
=
0, x
C
=
N be two constants. For any position vector x
=
x
1
,
x
2
,
…
,
x
C
-
1
t
∈
0
,
N
C
-
1, the length of the ith interval [
x
i
-
1
,
x
i
] is denoted by Δ
x
i and defined by(13)
Δ
x
i
=
x
i
-
x
i
-
1for i
=
1
,
2
,
…
,
C. Likewise, the difference of H caused by Δ
x
i is defined by(14)
Δ
H
i
=
H
x
i
-
H
x
i
-
1for i
=
1
,
2
,
…
,
C.
The following lemma shows how to obtain an accurate initial solution by determining the elements of a position vector or partition vectorx.Lemma 11.
If the optimal solutionx
∗ to the dummy objective function β
S
1
(
x
) is given, then Δ
H
i
∗
/
w
i
≤
Δ
H
i
+
1
∗
/
w
i
+
1 for i
=
1
,
2
,
…
,
C
-
1.Proof.
We show it by contradiction. SupposeΔ
H
i
∗
/
w
i
>
Δ
H
i
+
1
∗
/
w
i
+
1 for some i. Since x
∗ is the optimal solution to β
S
1
(
x
), the sum of products(15)
S
∗
=
H
x
i
∗
-
H
x
i
-
1
∗
F
x
i
∗
-
F
x
i
-
1
∗
w
i
+
H
x
i
+
1
∗
-
H
x
i
∗
F
x
i
+
1
∗
-
F
x
i
∗
w
i
+
1 should be the minimal in the interval [
x
i
-
1
∗
,
x
i
+
1
∗
]. On the other hand, since Δ
H
i
∗
/
w
i
>
Δ
H
i
+
1
∗
/
w
i
+
1, there exists a number x
i
<
x
i
∗ such that (
H
(
x
i
)
-
H
(
x
i
-
1
∗
)
)
/
w
i
=
(
H
(
x
i
+
1
∗
)
-
H
(
x
i
)
)
/
w
i
+
1. We claim that(16)
S
=
H
x
i
-
H
x
i
-
1
∗
F
x
i
-
F
x
i
-
1
∗
w
i
+
H
x
i
+
1
∗
-
H
x
i
F
x
i
+
1
∗
-
F
x
i
w
i
+
1
<
S
∗
.Let H
(
x
i
∗
)
-
H
(
x
i
-
1
∗
)
=
a, F
(
x
i
∗
)
-
F
(
x
i
-
1
∗
)
=
A, H
(
x
i
+
1
∗
)
-
H
(
x
i
∗
)
=
b, F
(
x
i
+
1
∗
)
-
F
(
x
i
∗
)
=
B, H
(
x
i
∗
)
-
H
(
x
i
)
=
δ, F
(
x
i
∗
)
-
F
(
x
i
)
=
Δ, and (
H
(
x
i
)
-
H
(
x
i
-
1
∗
)
)
/
w
i
=
(
H
(
x
i
+
1
∗
)
-
H
(
x
i
-
1
)
)
/
w
i
+
1
=
π. Since the sequence S
1 is sorted by (
p
i
/
λ
i
) in descending order, Δ
H
i
∗
/
w
i
>
Δ
H
i
+
1
∗
/
w
i
+
1 implies that (
F
(
x
i
∗
)
-
F
(
x
i
-
1
∗
)
)
/
w
i
>
(
F
(
x
i
+
1
∗
)
-
F
(
x
i
∗
)
)
/
w
i
+
1. That is, if a
/
w
i
>
b
/
w
i
+
1, then A
/
w
i
>
B
/
w
i
+
1. Then(17)
S
=
1
w
i
a
-
δ
A
-
Δ
+
1
w
i
+
1
b
+
δ
B
+
Δ
=
π
A
-
Δ
+
π
B
+
Δ
=
π
A
+
π
B
=
1
w
i
a
-
δ
A
+
1
w
i
+
1
b
+
δ
B
=
a
A
w
i
+
b
B
w
i
+
1
-
δ
A
w
i
+
δ
B
w
i
+
1
<
a
A
w
i
+
b
B
w
i
+
1
=
S
∗
.It contradicts that x
∗ is the optimal solution. The proof is complete.By the above lemma, the proposed algorithm is therefore able to start from a better initial positionx
(
0
). We find x
1
(
0
)
,
x
2
(
0
)
,
…, and x
C
-
1
(
0
) such that Δ
H
i
∗
/
w
i
≤
Δ
H
i
+
1
∗
/
w
i
+
1
=
Λ
/
W, where W
=
∑
i
=
1
C
w
i. In the next section, we set x
(
0
)
=
x
1
0
,
x
2
0
,
…
,
x
C
-
1
0
t instead of randomly choosing x
(
0
). This initial position will also enhance the convergence speed.Note that the partition vectorx
∗ is aglobal minimizer of WTM′. We prove this property by showing that β
S
1
(
x
) is concave upward for all x
∈
0
,
N
C
-
1. Namely, for any initial vector, the algorithm converges to the global minimum.Lemma 12.
Let the algorithm converge locally at somex
∗
∈
0
,
N
C
-
1. Then x
∗ is the global optimal solution to WTM′.Proof.
We prove the property by showing that, for anyx
∈
0
,
N
C
-
1, β
S
1
(
x
) is concave upward. From (10), we get(18)
∂
β
S
1
x
∂
x
i
=
1
w
i
H
′
x
i
F
x
i
-
F
x
i
-
1
+
H
x
i
-
H
x
i
-
1
F
′
x
i
-
1
w
i
+
1
H
′
x
i
F
x
i
+
1
-
F
x
i
+
H
x
i
+
1
-
H
x
i
F
′
x
i
,for i
=
1
,
2
,
…
,
C
-
1. Note that x
0
=
0 and x
C
=
N are two constants. Then the second partial derivative is(19)
∂
β
S
1
2
x
∂
x
i
2
=
1
w
i
H
′
′
x
i
F
x
i
-
F
x
i
-
1
+
2
H
′
x
i
F
′
x
i
+
H
x
i
-
H
x
i
-
1
F
′
′
x
i
-
1
w
i
+
1
H
′
′
x
i
F
x
i
+
1
-
F
x
i
-
2
H
′
x
i
H
′
x
i
+
H
x
i
+
1
-
H
x
i
F
′
′
x
i
=
2
w
i
H
′
x
i
F
′
x
i
+
2
w
i
+
1
H
′
x
i
H
′
x
i
.Because F
(
x
) interpolates the strictly increasing function P
(
i
), it is clear that F
′
(
x
)
>
0. We have F
′
′
(
x
)
=
0, since F
(
x
) is composed of straight lines. Similarly, H
(
x
) has the same properties. Therefore, ∂
β
S
1
2
(
x
)
/
∂
x
i
2
>
0 for all x
∈
0
,
N
C
-
1. The proof is complete.


## 3.3. Near-Optimal Solutionn
† to WTM

We show how to obtain a near-optimal solution of WTM in this subsection. First, we remap the optimal solutionx
∗ in R
n back to Z
n by rounding off all elements of x
∗, and a rounded solution n
†
∈
1,2
,
…
,
N
C
-
1 is obtained. The following lemma shows the magnitude order of β
S
1
(
x
∗
), α
S
0
(
n
∗
), α
S
1
(
n
#
), and α
S
1
(
n
†
), where n
#
∈
1,2
,
…
,
N
C
-
1 minimizes α
S
1
(
n
) and n
∗
∈
1,2
,
…
,
N
C
-
1 minimizes α
S
0
(
n
).Lemma 13.
Letn
†
∈
1,2
,
…
,
N
C
-
1 be the rounded resulting solution to WTM. Then β
S
1
(
x
∗
) and α
S
1
(
n
†
) are two bounds of α
S
0
(
n
∗
) with(20)
β
S
1
x
∗
≤
α
S
0
n
∗
≤
α
S
1
n
#
≤
α
S
1
n
†
,and the Euclidean distance between x
∗ and n
† is(21)
x
∗
-
n
†
2
≤
0.5
C
-
1
.Proof.
Sincen
# minimizes α
S
1
(
n
)
,
α
S
1
(
n
#
)
≤
α
S
1
(
n
†
). On the other hand, we need to show α
S
0
(
n
∗
)
≤
α
S
1
(
n
#
). Note that S
0 is the optimal sequence to the discrete-case problem WTM and that it is difficult to determine. We just assume that n
∗ is the optimal solution to α
S
0
(
n
). Since S
1 is obtained by some simple sorting rule and dedicated to the continuous-case problem WTM′, the sequence S
0 is more suitable for the discrete-case objective function, α
S
(
n
), than S
1. Therefore, we obtain α
S
0
(
n
∗
)
≤
α
S
1
(
n
#
).
We showβ
S
1
(
x
∗
)
≤
α
S
0
(
n
∗
) by contradiction. Suppose α
S
0
(
n
∗
)
<
β
S
1
(
x
∗
). On the other hand, by Lemma 8, β
S
0
(
n
∗
)
=
α
S
0
(
n
∗
), since n
∗
∈
1
,
2
,
…
,
N
C
-
1. Therefore, β
S
0
(
n
∗
)
=
α
S
0
(
n
∗
)
<
β
S
1
(
x
∗
). However, β
S
1
(
x
∗
) is the optimal solution to WTM′. It is a contradiction.
Since eachn
i
† is rounded from x
i
∗, it is obvious that |
x
i
∗
-
n
i
†
|
≤
0.5 and thus x
∗
-
n
†
2
≤
0.5
C
-
1. The proof is complete.By Lemma13, we know that α
S
0
(
n
∗
) is bounded by β
S
1
(
x
∗
) and α
S
1
(
n
†
) or β
S
1
(
n
†
), since α
S
1
(
n
†
)
=
β
S
1
(
n
†
) by Lemma 8. This guarantees that the proposed algorithm will output near-optimal broadcast programs.


## 4. Proposed Algorithm

Algorithm1 shows the proposed algorithm GRA. In the first step, we prepare the cumulative functions P
(
i
) and Q
(
i
) according to p
i and λ
i, respectively. Then we also construct the dummy objective function β
S
1
(
x
), and we set the initial value of x
=
x
1
0
,
x
2
0
,
…
,
x
C
-
1
0
t. All these C
-
1 elements of x need to satisfy that Δ
H
i
∗
/
w
i
=
Δ
H
i
+
1
∗
/
w
i
+
1 (see Lemma 11). In Steps 3 and 4, we evaluate the magnitude of β
S
1 at x and determine the steepest decent direction. If a zero gradient occurs, the algorithm will stop. In Steps 5–8, we need to find a new position whose magnitude of β
S
1 is smaller than the current one. Then we move a distance of δ towards the steepest decent direction, and x is replaced with the new position (Steps 9–13). We check if any stopping criterion is met in Step 14. In Step 15, we employ K
max
⁡ to limit the total iterations; thus, the algorithm will stop anyway.Algorithm 1:The algorithm of GRA.
ProcedureGRA (C, D, S
1, TOL, K
m
a
x)
INPUT: the number of channelsC, the database D, the sorted access pattern S
1,
the tolerance TOL, the maximal number of iterationsK
m
a
x.
OUTPUT: the near-optimal solutionn
† to WTM.
Step  1  Calculate P
(
i
), Q
(
i
), and construct corresponding F
(
x
), H
(
x
);
Construct the dummy objective functionβ
S
1
(
x
);
Setk
=
1; x
=
[
x
1
(
0
)
,
x
2
(
0
)
,
…
,
x
C
-
1
(
0
)
]
t.
Step  2
While (k
≤
K
m
a
x) do Steps  3–15.
Step  3Set β
1
=
β
S
1
(
x
); z
=
∇
β
S
1
(
x
); z
0
=
z
2.
//Note thatz
2 is the Euclidean distance of z.
Step  4
If (z
0
=
0) then
Output “x
1
,
x
2
,
…
,
x
C
-
1
,
β
1”, “Zero gradient!”;
Stop.
Step  5Set z
=
z
/
z
0; δ
1
=
0; δ
3
=
1; β
3
=
β
S
1
(
x
-
δ
3
z
).
Step  6
While
(
β
3
≥
β
1) do Steps  7 and 8.
Step  7Set δ
3
=
δ
3
/
2; β
3
=
β
S
1
(
x
-
δ
3
z
).
Step  8
If (δ
3
<
T
O
L
/
2) then
Output “x
1
,
x
2
,
…
,
x
C
-
1, β
1”, “No more improvement!”;
Stop.
Step  9Set δ
2
=
δ
3
/
2; β
2
=
β
S
1
(
x
-
δ
2
z
).
Step  10     Setv
1
=
(
β
2
-
β
1
)
/
δ
2; v
2
=
(
β
3
-
β
2
)
/
(
δ
3
-
δ
2
); v
3
=
(
v
2
-
v
1
)
/
δ
3.
//Note that we use Newton’s forward divided-difference formula [11] to find a quadratic
//polynomialV
(
δ
)
=
β
1
+
v
1
δ
+
v
3
δ
(
δ
-
δ
2
) which interpolates v
(
δ
) at δ
=
0, δ
=
δ
2, δ
=
δ
3.
Step  11      Setδ
0
=
0.5
(
δ
2
-
v
1
/
v
3
); β
0
=
β
S
1
(
x
-
δ
0
z
).
//Note that the critical point ofV occurs at δ
0.
Step  12     Findδ from δ
0
,
δ
3 so that β
=
β
S
1
(
x
-
δ
z
)
=
min
⁡
β
0
,
β
3.
Step  13     Setx
=
x
-
δ
z.
Step  14If (β
-
β
1
<
T
O
L) then
Setn
1
†
=
R
o
u
n
d
(
x
1
)
,
n
2
†
=
R
o
u
n
d
(
x
2
)
,
…
,
n
C
-
1
†
=
R
o
u
n
d
(
x
C
-
1
);
Output “n
1
†
,
n
2
†
,
…
,
n
C
-
1
†, β
S
1
(
n
†
), k”, and “Success!”;
Stop.
Step  15     Setk
=
k
+
1.
Step  16  Output “x
1
,
x
2
,
…
,
x
C
-
1, β”, “Maximum iterations exceeded!”.
Stop.


## 5. Comparison with Other Research

In the real world, such minimization problems usually call for instant and near-optimal solutions, especially for large problem instances. As a result, many metaheuristic algorithms have been proposed for providing instant and near-optimal solutions, for example, [22–24]. Although these algorithms achieved better execution time, their solution quality cannot be ensured or bounded.Therefore, we need deterministic algorithms that are able to converge linearly and achieve near-optimality. Jea et al. [20] solved a basic similar problem, DAP, that is, m
i
n
∑
i
=
1
m
[
(
∑
d
j
∈
M
i
1
)
(
∑
d
j
∈
M
i
p
j
)
]. Here, the number of machines or channels is denoted by m, literally meaning C in this study. The terms in the square bracket are in a very simple form. Even so, the partition problem is also time-consuming for obtaining an optimal solution when the problem size is larger than 50. This problem was solved near-optimally by their proposed algorithm [20]. Wang and Jea [21] proposed another partition problem, SPP, that is, m
i
n
∑
i
=
1
m
[
(
∑
d
j
∈
M
i
c
j
)
(
∑
d
j
∈
M
i
p
j
)
]. The terms in the square bracket become slightly complicated. This problem was also solved near-optimally in linear time. Jea and Wang [2] introduced another partition problem, DBAP; that is, m
i
n
∑
i
=
1
m
[
a
i
(
∑
d
j
∈
M
i
b
j
)
(
∑
d
j
∈
M
i
1
/
n
)
]. The terms in the square bracket look similar to those of SPP. However, the transformation between Z
n and R
n becomes more difficult. After establishing a complete theoretical basis, this problem was also solved near-optimally.On the other hand, Wang and Chen [25] proposed another minimization problem, m
i
n
∑
i
=
1
m
|
(
∑
d
j
∈
M
i
q
j
)
-
r
| subject to ∑
i
=
1
m
[
(
∑
d
j
∈
M
i
q
j
)
(
∑
d
j
∈
M
i
p
j
)
]
≤
T and ∑
d
j
∈
M
i
1
≤
v for all nonempty M
i. The constraints and absolute values make the problem harder. It is interesting that the discretized problem could also be solved by the same technique in R
n.In this study, we propose the WTM problem, that is,m
i
n
∑
i
=
1
m
[
(
∑
d
j
∈
M
i
λ
j
)
(
∑
d
j
∈
M
i
p
j
)
/
w
i
]. As shown in Figure 1, WTM is the most complicated form. WTM relates to not only partition but also permutation. In the three problems, DAP, SPP, and DBAP, the position orders of items in n
∗ and x
∗ are the same. However, for WTM, the position orders of items in n
∗ and x
∗ might be different. This makes transformation between Z
n and R
n more difficult, so we sacrifice some accuracy of position order and force the transformation to be done. Even so, WTM describes a general form of such problems and still achieves near optimality.Figure 1
The relationship diagram.


## 6. Computational Experiments

The experiments are divided into three parts. First, since the real-world situations are complicated, we need to determine some significant system settings. We develop a basic genetic algorithm (GA) to conduct a pilot experiment for determining these settings. Second, when the problem size is small, both algorithms (i.e., GRA and GA) are compared with an exhaustive search algorithm. Third, when the problem size is large, we compare GA and GRA to evaluate their solution quality and execution speed.Table1 summarizes the parameters used in the experiments. Parameters N, C, p
j, λ
j, and w
i have already been defined in Section 2. Access probability p
j follows a Zipf distribution with parameter θ [20]. Item size λ
j follows a discrete normal distribution with parameters 200
μ and 50
σ. Bandwidth w
i follows a discrete uniform distribution D
U
(
1
-
0.25
R
,
1
+
0.25
R
). For GA, the population size, crossover rate, and mutation rate are 100, 0.8, and 0.05. For GRA, the maximum iteration number and tolerance are 10,000 and 0.01, respectively. All the proposed algorithms were implemented in PASCAL and executed in a Windows 7 environment on an Intel Xeon E3 1230 @ 3.20 GHz with 8 GB RAM. For each setting, 30 random trials were conducted and recorded.Table 1
System settings in the experiments.
Parameter
Default
Range
Meaning
N
1
,
2
,
…
,
1000
Number of data items
C
1,2
,
…
,
50
Number of channels
p
j
Z
i
p
f
(
θ
)
Access probability of data itemj
λ
j
N
(
200
μ
,
50
σ
)
Size of data itemj
w
i
(
1
-
0.25
R, 1
+
0.25
R
)
Bandwidth of channeli
R
0.0, 0.25, 0.5, 0.75
Parameter for bandwidth
θ
0.0, 0.25, 0.5, 0.75
Parameter for access probability
μ
0.0, 0.25, 0.5, 0.75
Parameter for item size
σ
0.0, 0.25, 0.5, 0.75
Parameter for item size
r
c
0.8
Crossover rate for GA
r
m
0.05
Mutation rate for GA
L
100
Population size for GA
K
m
a
x
10000
Maximum iteration number for GRA
TOL
0.01
Tolerance for GRAIn the first part, we develop a basic genetic algorithm (GA) to test the performance. Each chromosome is randomly generated. For example, letN
=
4, C
=
2 and generate 5
(
=
N
+
C
-
1
) random values, 0.42, 0.95, 0.13, 0.21, and 0.36. According to their magnitudes, the largest number 0.95 means a channel separator. That is, item 4 (having the fourth smallest value, 0.42) is allocated to channel 1, and items 1, 2, and 3 are allocated to channel 2. For each population, there are 100 random chromosomes. The fitness is defined as f
i
=
c
i
-
0.5
/
∑
k
=
1
L
c
k
-
0.5, for i
=
1,2
,
…
,
L, where c
i is the objective cost achieved by the ith chromosome. A standard roulette wheel selection is employed, and two parent chromosomes are selected for generating two child chromosomes by a two-point crossover. Moreover, a simple single-point mutation is adopted. GA will terminate if the run time is over 100
n milliseconds or no improvement is made during the recent 100 generations.In the second part, Figure2 shows the effect of C on the performance for N
=
10. The relative error is defined by (
c
GA
-
c
OPT
)
/
N or (
c
GRA
-
c
OPT
)
/
N, where c
GA, c
GRA, and c
OPT are objective costs obtained by GA, GRA, and an exhaustive search algorithm. It is seen that GA takes more run time when C increases. Moreover, C does not influence GRA and most instances can be solved within 1 millisecond. On the other hand, GA can easily become trapped in local minimums, since there are many local minimums for such an optimization problem. Consequently, the relative error of GA is relatively higher. Since the setting of C
=
2 has the least significance, we omit it in later experiments.Figure 2
The effect ofC on performance (N
=
10).
(a)
Run time
(b)
Solution qualitySimilarly, Figures3–6 show various effects on the performance for N
=
10. As shown in Figures 3 and 4, identical access probability (
θ
=
0
) and equal bandwidth (
R
=
0
) make the problem easier, so we only observe larger θ and R in later experiments. In Figures 5 and 6, when μ and σ increase, the relative errors increase slightly. The worst mean relative error is 0.353 when μ
=
0.75; that is, the data items are large. Therefore, we only test the instances with larger item sizes in later experiments.Figure 3
The effect ofR on performance (N
=
10).
(a)
Run time
(b)
Solution qualityFigure 4
The effect ofθ on performance (N
=
10).
(a)
Run time
(b)
Solution qualityFigure 5
The effect ofμ on performance (N
=
10).
(a)
Run time
(b)
Solution qualityFigure 6
The effect ofσ on performance (N
=
10).
(a)
Run time
(b)
Solution qualityFigure7 compares two algorithms for N
=
12 in terms of execution speed and solution quality. Again, GRA almost takes no time to obtain near-optimal solutions, whereas GA needs 3 seconds on average. For the setting of N
=
12, there are more local minimums than N
=
10. It becomes more difficult to locate the optimal solution. Therefore, GA takes more run time but still has larger relative errors.Figure 7
Comparison of two algorithms (N
=
12, θ
=
0.5).
(a)
Run time
(b)
Solution qualityIn the third part, Figures8 and 9 show the performance of two algorithms when the problem size is large. Since we cannot obtain optimal solutions when n is large, we compute their relative deviations. The relative deviations are defined by (
c
G
A
-
c
m
i
n
)
/
N and (
c
G
R
A
-
c
m
i
n
)
/
N, where c
m
i
n
=
m
i
n
{
c
G
A
,
c
G
R
A
}. GRA outperforms GA greatly in terms of solution quality and execution speed. For most instances, they can be solved within 1 millisecond for C
=
5 and N
=
500. Even for the worst case, GRA takes only 16 milliseconds. On the other hand, GA cannot jump out of local minimums, no matter how many trials it tries. Its solution quality depends highly on the initial population. If there are no high-quality solutions at the beginning, it is difficult for GA to locate the optimal solution in the n-dimensional solution space.Figure 8
Comparison of two algorithms (N
=
250, θ
=
0.5).
(a)
Run time
(b)
Solution qualityFigure 9
Comparison of two algorithms (N
=
500, θ
=
0.5).
(a)
Run time
(b)
Solution qualityFigure10 shows the effect of C on execution time. To observe the average execution time of GRA, we set N
= 1,000, θ
=
0.0
,
0.1
,
0.5
,
1.0
,
2.0, R
=
0.5, μ
=
0.5, σ
=
0.5, and C
=
1 to 50. Since GA cannot compete with GRA for solution quality when N
=
500, we do not examine the behavior of GA for such a large problem size. As shown in the figure, when C increases, the run time of GRA slightly increases. It means the number of channels is directly proportional to the run time of GRA. In fact, the number of channels of a mobile environment is far lower than 50. It implies that GRA is able to deal with scheduling 1000 data items for any real-world broadcast server.Figure 10
The effect ofC on the execution time of GRA.Figure11 shows the effect of θ on convergence speed. In this experiment, we set N
=
1000, C
=
2
,
5
,
10
,
20
,
50, R
=
0.5, μ
=
0.5, σ
=
0.5, and θ
=
0.0 to 1.0. When θ
=
0.0 and C
=
50, all the data items are of the same popularity. However, the sizes of the data items are different and the bandwidths of the channels are also distinct. These variations make it difficult for GRA to converge. On the other hand, as θ
=
1.0, there are only a few popular data items which should be allocated to channel 1 (i.e., that with the highest bandwidth). The other items with very low access probabilities can be roughly allocated to the remaining channels. Therefore, GRA converges very rapidly when θ
>
0.8.Figure 11
The effect ofθ on the execution time of GRA.In Figure12, we implement an optimization algorithm, that is, a branch-and-bound algorithm (B&B), and compare it with GA and GRA. Since B&B is very time-consuming, we only observe the results for N
≤
15. Both B&B and GRA can provide optimal solutions when N
≤
15. On the other hand, the average run time of B&B for N
=
15 is 30 seconds, whereas the run time of GRA is always less than 4 seconds, even for N
=
200. It is clear that the time complexity will exclude such optimization algorithms from practical use.Figure 12
Comparison of three algorithms (m
=
3, θ
=
0.5, μ
=
0.5, and σ
=
0.5).
(a)
Run time
(b)
Solution qualityIn sum, GRA is a practical algorithm, even forN
=
500. As compared with the other two algorithms, GRA is more suitable for application in the real world. Moreover, we also guarantee that each solution is generated within a linear time and give an error bound.


## 7. Conclusion

Minimization problems are usually time-consuming, especially for large problem instances. Consequently, most traditional studies have employed metaheuristic algorithms to solve such problems. However, such algorithms have several shortcomings. First, their solutions are obtained by trial and error, so solution quality is not guaranteed. Second, their approximation algorithms cannot converge linearly. Third, some traditional methods need to keep track of partial results, so they are memory-consuming. Fourth, some traditional methods, such as dynamic programming and branch-and-bound algorithms, are not scalable. Once the problem size increases, it may take several days to generate an optimal solution, and such a delay is impractical.Mapping a discretized problem fromZ
n to R
n is an interesting idea. In this study, a gradient-based algorithm is proposed to deal with WTM. We first map it from Z
n to R
n. Then the mapped problem is solved optimally in R
n. Finally, the optimal solution is mapped from R
n back to Z
n. Moreover, the theoretical basis ensures that the proposed algorithm can converge linearly, provide high-quality solutions, and require less memory.In the near future, we will extend the concept to other optimization problems. By mapping a problem from its original domain to another domain, we are likely to find a more time-efficient and cost-effective way to achieve similar results.



---

*Source: 9371563-2016-04-30.xml*