International Journal of Scientific & Engineering Research, Volume 2, Issue 3, March-2011 1

ISSN 2229-5518

Parameter Ranking and Reduction in

Communication Systems

M.H. Azmol, M.H. Biswas, and A. Munnujahan

Abstract—Parameter reduction from experimental data is an important issue arising in many frequently encountered problems with different types of applications in communications engineering. However, the computational effort grows drastically with the number of parameters in such types of applications. This paper proposes a technique that reduces the performance parameters of a communication system based on eigenvalues of covariance matrix as well as providing a weighted rank of parameters by an approach called non-negative matrix factorization (NMF). The factorization of original matrix provides a weight metric that offers a means of ranking and selecting meaningful important parameters. The relative importance of each parameter is measured from the sequentially ordered eigenvalues. The main aims of this paper are to determine, identify and reduce the reasonable number of performance parameters which will reflect the best measurement system of a describing network

scenario.

Index Terms—Eigenvalues, Parameter reduction, Non-negative matrix factorization

—————————— • ——————————

1 INTRODUCTION

N the modern era, recent technological developments of telecommunication devices, computer based instru- mentation and electronic data storage have resulted in increasing quantities of data and in a consequence, over- whelm many of the classical data analysis tools available. Processing these huge amounts of data has created many challenges and new concerns of data representation with a few numbers of dimensions. Many researchers have been exploring in these fields and a large portion of these efforts are concerned with the challenging task of evaluat- ing the performances of a network by measuring some quality of service (QoS) support parameters such as bandwidth, load, delay, jitter, error rate etc. However, measuring all of these variables together is very challeng- ing due to the growing complexity of telecommunication systems as well as some constraints on information ga- thering devices. The collected data from these complex phenomena represent the integrated result of several in- terrelated variables since they act together. The original data becomes noisy, overlap and ambiguous. In most phenomena, some parameters may have little effect on model predictions, and the effects of some parameters can be highly correlated with the effects of others, making parameter estimation difficult. As a result, modelers often use simplified models that contain a reduced number of parameters or they estimate only a subset of the parame- ters in their complete model. Moreover, being ignorant experimenters we don’t know which, let alone how many, axes and dimensions are important to measure. Even we often don’t know which measurements best reflect the dynamics of our system. Generally, in many applications, the data set is gathered from a huge number of dimen- sions (variables). This curse of the dimensionality (variables) degrades the query efficiency and accuracy of a system. So, the question is raised, how can we reduce these de- pendent parameters as well as provide a compact system
model which will provide fidelity near the significant level of QoS of the original system without much loss of information’s. A suitable parameter reduction technique may address all of these issues. The problem of parameter reduction has received a broad attention in different areas of research such as computer vision [2], information re- trieval [3], machine learning, pattern recognition etc. Moreover, it has also widespread application in other areas, ranging from ecological systems, power systems, production systems, chemical reactions and biochemical networks to wastewater treatment processes. There exist many parameter reduction techniques such as Principal Component Analysis [6], [7], Singular Value Decomposi- tion [8], Feature Selection [4], Non-negative Matrix Facto- rization (NMF) [5], and Factor Analysis [9]. The main dis- advantage of feature selection and factor analysis ap- proaches are that some combination of parameters may give better results, but could be excluded because of pa- rameters selected at earlier steps. In, principal compo- nents, there are some limitations on non-linear cases. We use NMF algorithms as it is simple-nonparametric me- thod which reveals easily underlying structures in com- plex data set. By using, NMF algorithms of the original data matrix, we derive a weight metric to obtain their ranking. The relative importance of each parameter is obtained from the sequentially ordered eigenvalues of covariance matrix, which in turn expresses the attributive energy of the data. Eigenvalues quantifies the importance of each dimension by describing the variability of a data set. In particular, the measurement of variance along each dimension provides a means for comparing the relative importance of each variable. An implicit hope behind employing this method is that a small number of dimen- sions (i.e. less than the number of measurement types) will provide a reasonable characterization of the complete data set. In fact, categorizing eigenvalues in this manner,

IJSER © 2011 http://www.ijser.org

2 International Journal of Scientific & Engineering Research, Volume 2, Issue 3, March-2011

ISSN 2229-5518

a significant insight of the whole network can be ob- tained. For an illustration, in our network data matrix, we have explored six parameters of a WLAN network scena- rio and compare them. In general, we know that “throughput” and “network load” are the most important parameters for assessing the performance of a network. In our method, we have proved that these two parameters among six exhibit 94% characteristic of the whole net- work. In summary, we have proposed two measurement metrics in this paper: (i) a weighted metric for selecting the parameters that reveals important characteristics of a network (ii) and stipulated eigenvalues, measure the rela- tive importance of each parameter. The primary objec- tives of our work are to determine, identify and reduce significant number of performance parameters in a sys- tematic and representative way, so that a describing net- work scenario will characterize and reflect the best mea- surement system. The rest of this paper is organized as follows. The notations used throughout the rest of this paper are given in section 2. Related works are described in section 3. We outline the steps taken to collect the data in section 4. A brief overview of mathematical measure- ment technique of non-negative matrix factorization is discussed in section 5. In section 6, we discussed our ex- perimental results. Concluding remarks are presented in sections 7.

2 BACKGORUND NOTATIONS

In order to facilitate discussion in subsequent sections we introduce relevant notation first. We use X is a m-by- n measurement matrix in which each column denotes the predicted variables and each row represents the sample observations. 9t is a set of non-negative numbers, P and Q are the factorization of X of size m-by-k and k-by-n

respectively. Y is the new transformation of X , . ,is the
Euclidean norm, 'Ai and vi are the corresponding eigenva- lues and eigenvectors of covariance matrix X respective- ly. In our experiment data, we have taken six variables and 300 observations. So the size of X is 300 by 6. Unless otherwise stated, all the vectors in this paper are column vectors.

3 RELATED WORKS

Our ideas behind parameter reduction in communica- tion systems are motivated by a variety of past studies. Although to our knowledge, parameter reduction in a network using NMF and eigenvalues has not been pre- viously applied directly. Author’s in paper [11] and [12] present a framework for nonlinear systems analysis based upon controllability and observability covariance matric- es. This covariance matrix is used for reduction of the nonlinear model. Sanjay L. et al. [13] introduced a new method of model reduction for nonlinear system with inputs and outputs. A new technique based on Hankel
singular values for reducing the parameter set of a fun- damental model is introduced in paper [14]. The main drawback of this method is that the physical meaning of the parameters is lost during this procedure. There is a little prior work that is closely related to ours. Authors in paper [16] measured the performance of wireless net- works by state space reduction. They propose the stochas- tic method based on the comparison of Markov chains by following three steps: first, choice of the state space of comparison, second, choice of the relation order on the chosen space and finally, construction of bounding mod- els by applying aggregation. Paper [4] describes feature selection algorithm based on measuring similarity be- tween features. A. Lakhina et al. in [17] analyzed the network flow and found that, in a network with over a hundred of origin to destination flows, these flows can be accurately modeled in time using a small number (10 or less) of independent components or dimensions. In [18] and [19] authors proposed different functional test areas to verify next generation broadband network. They classi- fied the equipments into different groups by some scores such as MUST, SHOULD, MAY and CAN. This method can be used in order to compare any device of different vendors with each other but not their own devices, since all tests don’t have the same value. Hence this method will not be as reliable as needed. Most of the existing re- duction techniques based on model reduction and focus on to reduce the number of states, whereas relatively few techniques are available for reduction of the number of parameters in these models.

4 NETWORK ENVIRONMENT AND EXPERIMENTAL

DATA


For network simulations and raw data of different pa- rameters, we use OPNET modeler which is one of the most leading and powerful simulation tools for the analy- sis, planning, optimization and evaluating of communica- tion networks, devices and protocols. The measurement platforms and environment in which we conduct our ex- periments (Fig-1) are described in this section. We use two WLAN fixed nodes separated by 80 meter distance in our test bed. We perform experiments with high resolu- tion video conference as an application in IEEE 802.11b WLAN. The attributes of different performance parame-

IJSER © 2011 http://www.ijser.org

Fig. 1. W LAN network scenario.

International Journal of Scientific & Engineering Research, Volume 2, Issue 3, March-2011 3

ISSN 2229-5518

Data Dropped

(Buffer Overflow)

Transmitter

Higher Layer


Load

Receiver

Higher Layer

load, media access delay, network load and throughput. The configuration of WLAN parameters and measure- ment unit of each parameter are shown in Table-I and Table-II.

Throughput

Network Load

WLAN MAC

Traffic sent

Medium Access Delay

Traffic

Received

5 MATHEMATICAL APPROACH

In this section, we discuss our mathematical approach. Suppose X is our original data set, where each row cor- responds to a set of measurements from one particular

Fig. 2. Attributes of different parameters.

TABLE 1

SIMULATION PARAMETERS OF WLAN

Wireless LAN parameters Values

Physical Characteristics DSSS Data Rate 11 Mbps Channel Settings Auto Assigned

Transmit Power 0.001w

trial (a single sample) and each column of X corresponds to all measurements of a particular type. In our data set X is an m-by-n matrix where m = 300 and n = 6. Our first approach is to find some orthonormal matrix v such that Xv = Y , and Y T Y is a diagonal matrix. Here generally, v is the eigenvector of the covariance matrix X T X and Y

is a new transformed presentation of X , derived from Xv = Y . Generally, the primary motivation behind our first approach is to de-correlate the data set, i.e. to remove second-order dependencies. Y is arranged with

the stipulated eigenvalues

'A1 > ... > 'Ar . Our second ap-

Packet Reception-Power Thre-

shold

-95

proach is to factorize the original data X so that we can find a weight matrix to make some rank of the variables

RTS Threshold None

Fragmentation Threshold None CTS-to-Self Option Enabled Short Retry Limit 7

Long Retry Limit 4

Buffer Size 256000

Large Packet Processing Drop

PCF Parameters Disabled

HCF Parameters Not Supported

in X . Here, we discuss the factorization technique.

5.1 Non-negative Matrix Factorization

In an article in Nature, Lee and Seung, 1999, [20] started a flurry of research and proposed the notion of non-negative matrix factorization algorithm. Prior to its publication several lesser known paper published and actually they deserve more credit for the factorization of non-negative matrix. Given a data ma-

trix X = [ x1, x2 ,......, xn ) 9t , each column of X is a sample

vector and a positive integer k < {m, n} , non-negative ma- trix factorization aims to find two non-negative matrices

m> k

k >n

P = l pij l 9t

and

Q = l qij l 9t

which minimize the

TABLE 2

MEASUREMENT UNITS OF PARAMETERS

following function

f P, Q = 1

X PQ 2

(1)

Collected parameters Units

Data Dropped (Buffer Overflow) bits/sec

Delay sec


where .

2 F

denotes the Frobenius norm. The Frobenius
norm of a matrix

X = l xij l is defined by X F = X ij .

Load bits/sec

Media Access Delay sec Network Load bits/sec Throughput Bits/sec

ters are presented in Fig-2. We collect the global statistics of six parameters: data dropped (data overflow), delay,

ij

The product PQ is called the non-negative matrix factori- zation of X , though X is not necessarily equal to the product of PQ . The product PQ is an approximate facto- rization of X of rank at most k . Usually, an appropriate decision on the value of k is critical, but the choice of k is
often problem dependent. The objective function (1) is
convex in both P and Q only, it is not convex in both

IJSER © 2011 http://www.ijser.org

4 International Journal of Scientific & Engineering Research, Volume 2, Issue 3, March-2011

ISSN 2229-5518

variables together. Therefore, to expect an efficient algo-
matrix which optimized the linear transformation of X .
rithm for finding global minima of

f ( P, Q) is unrealistic.

The outer product of PQ demonstrates how the rows of
This important problem affects the numerical minimiza- tion of (1) since it includes the local minima due to the non convexity. Various minimization methods for the

Q essentially specify the weights of each of the column- vector of P . If we look geometrically, NMF is a conical coordinate transformation. Graphical interpretation of

solution of (1) have been proposed in an effect to speed
up the convergence. Lee and Seung’s iterative multiplica-
tive update algorithms have become a balance algorithm as follows:
NMF is shown in Figure-3. The two basis vectors

P1 and

P t + 1 P t

XQ T

ij

ij ij

P QQ T

ij

X T P

Q t + 1

Q t ij

i j ij

Q T P T P

ij

Multiplicative Update Algorithms:
Lee and Seung [20] proposed the prototype of multiplica- tive algorithm with the mean squared error objective function which is provided below:
P = rand (m, k) % initialize P as random dense matrix Q = rand (k, n) % initialize Q as random dense matrix for i = 1: maxiter

Q = Q. * PT X . /

PT PQ + 10 9 ;

P = P. *

XQT . /

PQQT + 10 9 ;

end

To avoid division by zero, 10-9 is added in each update rule.

5.2 Basic Geometric Review of NMF

NMF essentially tries to find two non negative matrices

P and Q such that X ;: PQ . This approximation can be

k

Fig. 4. Flowchart of reduction procedure.

TABLE 3

WEIGHT MATRIX Q

0.0552 0.1336 0.8836 0.1362 0.2894 0.3099

0.0734 0.1522 0.8868 0.1546 0.2737 0.2938

viewed column by column as

x ;:

p qi

where

p de-

i i i

i =1

notes i-th column vector of P and
qi denotes i-th row of
matrix Q .Thus each data vector

xi is approximated by a

TABLE 4

EIGENVALUES AND THEIR PERCENTAGE

linear combination of the columns of P weighted by the

components of Q . Therefore, P can be considered as basis

Eigenvalues Percentage Cumulative sum


4.6262 75.0049 0.7500
1.0827 18.6317 0.9364
0.2366 04.2039 0.9784
0.0528 01.4876 0.9933
0.0017 00.6498 0.9998

0.0002 00.0221 1.0000

Fig. 3. Geometric behavior of NMF.

IJSER © 2011 http://www.ijser.org

International Journal of Scientific & Engineering Research, Volume 2, Issue 3, March-2011 5

ISSN 2229-5518

Fig. 5. Relative weight of variables in X w.r. to varianles in P.

P2 describe a cone which encloses the approximation data set of X . Due to the non-negative constraints the points

inside this cone can be reconstructed through linear com-

T

Fig. 6. Plot of eigenvalues versus their percentage.

bination of these basis vectors: x =

p1 , p2

. q1.q2

6 EXPERIMENTAL RESULTS

Experimental results are discussed in this section. The flowchart of our experiment is shown in Fig 4. For our experiment, we use a multidimensional data of six va- riables collected from a WLAN network scenario. The sample size of our data is 300 by 6. When we analyze our data set, an important and unmet challenge arises against different units or scales. In real world data set, variables are measured in different units and these discrepancies can distort the calculations also the analysis may lead inaccurate. We mitigate this problem by converting and normalizing all the values of data set by subtracting each column from the minimum value for moving towards center of the data and dividing by corresponding stan- dard deviation of each variable for scaling. We factorize

Fig. 7. Scree plot of the percent variability explained by eigenvalues.

Q provide the relative contributions of the six variables in X to produce the new variables in P. The third varia- ble “load” in X (weight .8836) strongly influences the first predictor in P so we can consider it as the highest contributed variable in producing the matrix P . From the second row of Q the third variable “load” and the sixth variable “throughput” provide relatively strong weights. Since we have chosen “load” as the most contributed va- riable, we can select the sixth variable “throughput” as the second highest contributed variable. Finally, we can rank all the variables by providing weight in this manner. We visualize the relative contributions of the variables in the column space of P in Fig-5. The relative magnitude of the vectors provides the corresponding weights. The de- rived eigenvalues and their percentage of the total varia-

our original matrix [ X )

300>6

to [P)

300>2

and [Q) so

2>6

bility explained are given in Table IV. The bar plot Fig-6
shows the eigenvalues versus their explained variation.

that X ;: PQ . Curious reader may ask why we chose the

value of k is 2. This issue is explained in later. For the space constraints we show only the weight matrix Q in Table-III. The matrix Q represents the coefficients of the linear combinations of the original six variables in X that generate the transformed new variables in P i.e. rows of
The first eigenvalue exhibits the maximum variation compare to others. We plot only three components in Fig-
7 and it clearly shows that the first two components ex- plain 94% energy of the data. Only two variables amongst six variables represent almost whole of the characteristic of original data matrix X . This is the reason why we

IJSER © 2011 http://www.ijser.org

6 International Journal of Scientific & Engineering Research, Volume 2, Issue 3, March-2011

ISSN 2229-5518

choose the values of k is 2.

7 CONCLUSION

In this paper, we have proposed a weight metric, derived from a data matrix of a network scenario to select lesser parameters that consequently leads to a parameter reduc- tion. This method is easy to implement and the results are easily interpreted. The method gives a simple matrix ma- nipulation and the ordered eigenvalues is an inherent property of the method itself. We emphasize the eigenva- lues of the covariance matrix which believed to be impor- tant. Additionally, we provide the importance as well as quantifying contribution of the parameters by discount- ing those eigenvalues that are believed to be unimportant. The weighted metric and eigenvalues of the covariance matrix lead to parameter choices that appear finally pa- rameter reduction. The primary benefit of our method is that, it quantifies the importance of each dimension for describing the variability of a data and provides a means for comparing the relative importance of each dimension. This method is not used just for WLAN but it is more general. From our experiment we have found that only two parameters “network load” and “throughput” among six, exhibit 94% percent contributions of whole network. So to evaluate the performance of a network, we emphasize more on these two parameters. We expect that, our approach will help to demystify the parameter reduc- tion technique of a network and of great use in future.

ACKNOWLEDGMENT

The authors greatly acknowledge the financial support sponsored, in part, by EU-FP7 project OneLab2. We would also like to thank Joao Paulo Barraca and Diogo Gomes for numerous helpful discussions.

REFERENCES

[1] IEEE 802.11 WG, Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specification, IEEE Std. 802.11, Aug. 1999.

[2] K.V.R. Kanth, D. Agarwal, A.E. Abbadi, & A. Singh, “Dimen- sionality Reduction for Similarity Searching in Dynamic Data- bases,” ACM SIGMOD Conference Proceeding, pp. 166-176, 1998.

[3] Ye J. Janardan, R. Li, “An Efficient Dimension Reduction Scheme for Image Compression and Retrieval,” ACM SIGKDD Conference Proceedings. 2004.

[4] P. Mitra, C.A. Murthy, K. Sankar Pal, “Unsupervised Feature Selection Using Feature Similarity,” IEEE transaction on pattern analysis and machine intelligence. vol. 24, no 3, march 2002.

[5] M. Berrya, M. Brownea, A.N. Langvilleb, V.P. Paucac, R.J.

Plemmonsc, “Algorithms and Applications for Approximate

Nonnegative Matrix Factorization,” Computational Statistics and

Data Analysis 52. pp. 155-173, 2007.

[6] J. Shlens, “A Tutorial on Principal Component Analysis”, Center for Neural Science, New York City, NY 10003-6603, April 22,

2009.

[7] I.T. Jolliffe, “Principal Component Analysis,” Springer-Verlag, New York, 2002.

[8] M.A. Hasan, “Low Rank Approximations with Applications to Principal Singular Component Learning Systems,” Proceedings of the 47th IEEE Conference on Decision and Control, Cancun Mex- ico, Dec. 9-11, 2008.

[9] H.H. Harman, Modern Factor Analysis. 3rd Ed. Chicago: Univer- sity of Chicago Press, 1976.

[10] Y. Jieping , “Generalized Low Rank Approximations of Matric- es,” Proceedings of the 21st International Conference on Machine Learning. 2004.

[11] B.C. Moore, “Principal Component Analysis in Linear Systems: Controllability, Observability, and Model Reduction,” IEEE Transactions on Automatic Control 26 (1), 17-32, 1981.

[12] J. Hahn, T.F. Edgar, W. Marquardt, “Controllability and Obser- vability Covariance Matrices for the Analysis and Order Reduc- tion of Stable Nonlinear Systems,” Journal of Process Control , 13,

115-127, 2003.

[13] S. Lall, J.E. Marsden, S. Glavaski, “Empirical Model Reduction of Controlled Nonlinear Systems,” 14th IFAC World Congress, Beijing, 1999.

[14] C. Sun, J. Hahn, “Reduction of Differential-Algebraic Equation Systems Via Projections and System Identification,” Journal of Process Control, 15, 639-650, 2005.

[15] C.L. Sun, J. Hahn, “Parameter Reduction for Stable Dynamical Systems Based on Hankel Singular Values and Sensitivity Analysis,” Chem. Eng.Sci., 61(16), pp. 5393–5403, 2006.

[16] H. Castel-Taleb, L. Mokdad, “Performance Measure Bounds in

Mobile Networks by State Space Reduction,” Proceedings of the

13th IEEE International Symposium on Modeling, Analysis, and Si- mulation of Computer and Telecommunication Systems (MAS- COTS’05), 2005.

[17] A. Lakhina, K. Papagiannaki, M Crovela, C. Diot, Eric D. Kolac- zyk, N. Taft, “Structural Analysis of Network Traffic Flows,” SIGMETRICS/Performance. New York, NY, USA, June 12–16,

2004.

[18] Y. Nasr Harandi, M. Yaghoubi Waskasi, M. Pirhadi, M. Mirza- baghi, A. Iravani Tabrizipoor, “ A Test Methodology for Test- ing Next Generation Broadband IP Access Services,” Interna- tional Conference on Advanced Communication Technology (ICACT

2007), Seoul, Korea, Feb. 2007.

[19] S.M.R. Sadri, M.Pirhadi, Y. N. Harandi, M.Y. Waskasi, A.I.

Tabrizipoor, M. Mirzabaghi, “ Test Strategy For DSL Broad- band IP Access Services,” Highcapacity Optical Networks and

Enabling Technologies (HONET 2007), Dubai UAE, Nov. 2007

[20] D. Lee, H. Seung, “Algorithms for Non-Negative Matrix Facto- rization,” Adv. Neural Inform. Process. Systems 13, pp. 556-562,

2001.

IJSER © 2011 http://www.ijser.org