We investigate the theoretical fundamentals of the Kolmogorov-Wiener filter construction for the continuous telecommunication traffic prediction. The traffic is treated as a continuous fractional Gaussian noise. The integral equation for the filter weight function is solved with the help of the Galerkin method in the framework of which the unknown function is sought as a truncated series in orthogonal functions. The investigation is different to our previous papers based on the polynomial functions, in this paper we propose to realize the Galerkin method on the basis of truncated Walsh function expansion, which is the method enhancement. Such an enhancement is based on the idea that the Walsh functions are step ones, which allows one to obtain the analytical expressions for the integral brackets. So, the corresponding numerical calculation of the double integrals is not needed. Moreover, the proposed approach does not require the calculation of the products of very large and very small numbers. So, the proposed enhancement allows one to investigate a wider range of parameters and higher numbers of functions in contrast to the polynomial realizations. The approach developed in the paper may be applied to the practical telecommunication traffic prediction.
1. Introduction and related works
The Kolmogorov-Wiener filter weigh function obeys the Wiener–Hopf integral equation, which is
a Fredholm integral equation of the first kind [
In our previous paper [
In order to overcome the above-mentioned drawbacks, we use a truncated Walsh function
expansion instead of a polynomial one. The Walsh functions are step ones [
expansion and to compare the both sides of the corresponding integral equation for the obtained weight function.
This paper is structured as follows. In Sec. 1 an introduction is given, in Sec. 2 the Wiener–Hopf integral equation, the Galerkin method and the Walsh functions are described, Sec. 3 contains the derivation of an algorithm for
obtaining the above-mentioned weight function, Sec. 4 contains a numerical comparison of both sides of the Wiener-Hopf integral equation for the obtained weight function, in Sec. 5 conclusions are formulated, and Sec. 6 contains the refrences. 2. Wiener-Hopf integral equation, Galerkin method and Walsh functions The unknown
Kolmogorov–Wiener
filter
weight
function
ℎ( )
for the
continuous
telecommunication traffic prediction in the fractional Gaussian noise model obeys the following
integral equation [
ℎ( )| − |2 −2 = ( + )2 −2
This equation may be solved via the Galerkin method, the idea of which is as follows [
The unknown weight function is sought in the form coefficients. From (1) and (2) one can obtain where ( ) are the functions orthogonal on the time interval ∈ [0, ] and are the unknown
( )| − |2 −2 = ( + )2 −2.
On multiplying both sides of (3) by ( ), = 1,2, . . , and integrating over , one can obtain
Let us introduce the following designations: the quantities are the integral brackets. So (4) can be rewritten as ( ) ( )| − |2 −2 =
( )( + )2 −2 , = 1, .
The obtained expression (6) is a system of linear algebraic equations for the unknown coefficients . is the column vector of the free terms: where is the matrix of the integral brackets, is the column vector of the unknown coefficients, and 1 2 ⋮ , = , = 1 terms of the Hadamard matrix (2 ) by rearranging the rows in ascending order of sign changes. For example, the matrices (4) and (4) are as follows: function approximation.
The functions ( ) in the expansion (2) form a complete orthogonal function system, which usually contains an infinite number of functions. Nevertheless, the number of functions in expansion (2) should be artificially truncated; otherwise, the system (6) would contain an infinite number of equations and could hardly be treated. The solution in the form (2) is called the solution in the
In this paper we propose to choose the functions ( ) as the Walsh functions. As is known [
interval ∈ [0, ]: The Walsh functions in the Hadamard numeration walh ( ) are defined as follows on the time (2) = 1 1 1 −1 , (2 +1) = (2 ) (2 ) (2 ) − (2 ) ,
∈ ℕ. 1 is the least natural number that obeys the where
(2 ) are the Hadamard matrix elements and inequality ≤ 2 . The set of Walsh functions in the Walsh numeration coincides with that in the Hadamard numeration, but the numerations differ from each other. In the Walsh numeration, the Walsh functions wal ( ) are numerated in ascending order of sign changes on the time interval ∈ (0, ). The first Walsh function wal1( ) = 1 = const has 0 sign changes, the second Walsh function The Walsh functions wal ( ) are defined as follows: so the first row in (4) has 0 sigh changes, the second row in (4) has 1 sign change, and so on. −1 , 1 −1 (2 ) ⎩ ,2 , ∈ ((2 = wal 1 2 ∙ = wal As can be seen from (14), wal
so the integral brackets (14) may be rewritten as = ⁄
⁄ ( −1) ( −1) Mathematica package, in the framework of which the Walsh matrix is expressed as (2 ) are the Walsh matrix elements and is the least natural number which obeys the (13) (14) (15) (16) (17) (18) (19) (20) (21) 3. Derivation of the weight function calculated, for example, as follows: = 2
First of all, let us derive the integral brackets (see (5)). Let us consider the approximation of
Walsh functions. The Walsh functions wal ( ) are step ones, they are constant on each time interval ∈ ( ⁄ , ( + 1) ⁄ ), = 0, − 1. That is why the integral brackets (5) may be , =1 are the corresponding values of the Walsh functions on the corresponding intervals: method with the help of a truncated Walsh function expansion. In other words, we put
The use of the Walsh functions is convenient because they are step ones, which significantly
simplifies the calculation in comparison with the polynomial solution derivation [
= 0 if and have opposite parities. So let us consider the quantities where and have opposite parities: following properties:
To prove the property (41), first of all we should stress that the Walsh functions obey the and = 0 0
+ which leads to the property (41). It should be stressed the following fact is used in (44): wal − wal = −wal + wal
+ , and have opposite parities, 2 2 where ≥ and , are of the same parity.
the approximation of = 2
To summarize the above-mentioned, let us write the algorithm of the weight function derivation in
Calculate the quantities 11 and 1 , = 2, by formulas (35).
Form the matrix from the elements , , = 1, by formula (26).
In contrast to the previous investigations [
The following section contains a numerical comparison for both sides of the Wiener–Hopf integral and form the corresponding matrix (see (8)).
Make a straightforward calculation of the integral brackets by formula (21) for ≥ and
Calculate the free terms by formula (39) and form the column vector of the free terms In order to verify the above-mentioned algorithm, in this section we calculate the MAPE (mean average percentage error) of the residual (the difference of the left-hand and the right-hand sides) of the Wiener-Hopf integral equation for the obtained weight functions.
The left-hand side of the integral equation (1) is as follows: where and (46) (47) (48) (49) (50) Let us consider different cases: < <
see (32), here the fact that ℎ( ) is a step function is used. . In such a case, the limits of integration in (48) are of opposite signs, and
Left( ) = ℎ( )| − |2 −2 =
ℎ ( ) ℎ = ℎ 1 ( − 1) + ( −1) 0 −( −1)
0 1 (− )2 −2 +
2 −2 = { = − } = = 2 −2 + 2 −2 =
2 −2 = given by formula (33).
To summarize the above-mentioned, 3. ≤
( −1) . In such a case, both limits of integration in (48) are non-positive, and ( ) is − − − ,
.
The integral (53) is the only integral that cannot be calculated analytically. We use the method of trapezoids in order to calculate an approximate value of (53):
MAPE ≈ =1 1 ∙ = =1
To summarize the above-mentioned, let us write the algorithm of calculation of the MAPE for the derived weight function in the approximation of = 2 1.
In what follows, some numerical results are given. The following parameters were considered:
it should be stressed that these parameters were investigated in our previous work [
MAPE,% 15 6.4 2.6 The MAPE values in Table 1 are rounded off to two significant digits. The corresponding graphs are given for the approximation of 256 Walsh functions (see Fig. 1).
The MAPE values in Table 2 are also rounded off to two significant digits, the graphs for the approximation of 256 Walsh functions is given on Fig. 2.
As can be seen from Table 1 and Table 2, the approximations of rather small numbers of Walsh functions are not accurate, but the approximations of rather large numbers of Walsh functions are rather accurate. Both sides of the integral equation (1) almost coincide for the approximation of 256
The investigation of the polynomial solutions [
The problem of prediction of telecommunication traffic is important for telecommunications; in
particular, it is important for information security because security attacks may be detected if the
traffic behavior significantly differs from the predicted one [
We investigate the theoretical fundamentals of the Kolmogorov–Wiener filter construction for the continuous telecommunication traffic prediction. Our goal is to develop a method of the filter weight function derivation as a solution of the Wiener–Hopf integral equation. The traffic is taken in the model where it is treated as continuous fractional Gaussian noise.
The corresponding Wiener–Hopf integral equation for the unknown weight function is solved via
the Galerkin method. The idea of the Galerkin method is to seek the unknown weight function in the
form of an expansion into an artificially truncated series in orthogonal functions. In our previous work
[
The integral brackets can be obtained analytically, and the corresponding analytical expressions are applicable even for a rather large number of Walsh functions; the numerical calculation of the double integrals in the integral brackets is not needed.
An easy-to-use analytical expression for the function Left( ), which is the left-hand side of the corresponding Wiener-Hopf integral equation, may be obtained; the numerical calculation of the corresponding integral is not needed.
The products of very large and very small numbers are absent in the framework of the proposed method based on the
approximations of large numbers of Walsh functions.
It should also be noted that the only integral that should be calculated numerically is the integral (53) for the MAPE. The other integrals are calculated analytically.
The approximations of = 2
(56). The investigation is conducted up to the approximation of 256 Walsh functions. For comparison,
it should be noted that the investigation of polynomial solutions [
approximations of more polynomials adequately. The parameters (56) were not investigated on the basis of polynomial functions, the corresponding investigation on the basis of Walsh functions is given in order to stress that the proposed Walsh function approach is applicable in a rather wide range of parameters.
The accuracy of the approximations rises with the number of Walsh functions, and the coincidence of both sides of the integral equation under consideration is very good for rather large numbers of
It should be noted that in this paper we investigate only the theoretical fundamentals of the
Kolmogorov–Wiener filter construction. This filter may be applied to the prediction of stationary
processes, so it is logical enough to use the approach based on this filter for the prediction of the
stationary telecommunication traffic, for example, in the model where the traffic is treated as
fractional Gaussian noise and in the model where the traffic is treated as a process with a power-law
structure function. There are plenty of different approaches to traffic prediction [
One more plan for the future is the application of the developed approach to other stationary traffic
models. For example, the polynomial solutions need a significant enhancement for the power-law
structure function model (see [