Describing MANETS: principal component analysis of sparse mobility traces

ABSTRACT

Data collected in realistic mobility traces for mobile ad hoc networks (MANETS) is intrinsically high dimensional. Principal Component Analysis (PCA) is a good tool for reducing the data dimemsion by extracting important features of the data. We propose a method for computing principal components using iterative regression for high dimensional matricies with missing values with an application to node degree time series. We expand this method to handle an additional dimension of information for a defined neighborhood ancestry of node degree, exposing patterns when they exist. We test our methodology on node degree data from a simulated university campus model (Pedsims) and real campus data. Results indicate that in both cases, the student's major field of study along with class schedule are strong factors to differentiate mobile node degree time series. The ability to detect differences is a powerful tool for application specific network management, allowing for: optimal placement of routers, design of specialized protocols for various user populations and lending insight to gauging the energy/bandwidth needs of mobile devices

REFERENCES

• 1: A. d'Aspremont, L. Ghaoui, M. Jordan, G. Lanckriet. A direct formulation for sparse PCA using semidefinite programming. June 2004.
• 2: M. W. Berry. Large Scale Sparse Singular Value Computations. International Journal of Supercomputing Applications. 1992, 6:13--49.
• 3: J. Boudec, M. Vojnovic. Perfect Simulation and Stationarity of a Class of Mobility Models. Infocom 2005.
• 4: T. Camp, J. Boleng, V. Davies. A Survey of Mobility Models for Ad Hoc Network Research. Wireless Communications & Mobile Computing (WCMC): Special issue on Mobile Ad Hoc Networking: Research, Trends and Applications, 2(5):483--502, 2002.
• 5: C. Chennubhotla, A. Jepson. Sparse PCA: Extracting Multi-scale Structure from Data, IEEE International Conference on Computer Vision, 2001.
• 6: H. Flores, S. Eidenbenz, N. Hengartner, R. Riedi and J. Smith. PedSims: Building towards Realism of Mobility Models for Wireless Networks. Technical Report Los Alamos National Laboratory, 2006.
• 7: W. Hsu, A. Helmy. Analyzing Principal Characteristics of User Association Patterns and Eigen-behavior in Wireless LAN Traces. 2006.
• 8: A. Jardosh, E. Belding-Royer, K. Almeroth, S. Suri. Real-world Environment Models for Mobile Network Evaluation. Journal on Selected Areas in Communications special issue on Wireless Ad hoc Networks, March 2005.
• 9: J. E. Jackson. A User's Guide to Principal Component Analysis. Wiley Series in Probability and Statistics, 1991.
• 10: Jing Su , Alvin Chin , Anna Popivanova , Ashvin Goel , Eyal de Lara, User Mobility for Opportunistic Ad-Hoc Networking, Proceedings of the Sixth IEEE Workshop on Mobile Computing Systems and Applications (WMCSA'04), p.41-50, December 02-03, 2004 [doi>10.1109/MCSA.2004.29]
• 11: Heung-Yeung Shum , Katsushi Ikeuchi , Raj Reddy, Principal Component Analysis with Missing Data and Its Application to Polyhedral Object Modeling, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.17 n.9, p.854-867, September 1995 [doi>10.1109/34.406651]
• 12: T. Wiberg. Computation of Principle Component Analysis when data are missing. Proceedings of the Second Symposium on Computational Statistics, pp. 229--236, 1976.
• 13: H. Zou, T. Hastie, R. Tibshirani. Sparse Principal Component Analysis. 2004.
• 14: Q. Zheng, X. Hong, J. Liu, "An Agenda Based Mobility Model21" anss, pp. 188--195, 2006.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Multivariate statistics

General Terms:
Algorithms, Measurement, Theory

Keywords:
iterative regression, mobility models, principal component analysis