無線感測網路(wireless sensor networks, WSN)是由許多資源有限的感測器所組成，感測器可以蒐集並且監測環境上的變化，無線感測網路能夠滿足環境監測上多樣的需求，為了蒐集並儲存這些資訊，無線感測網路必須採取適當的方法來組織並且壓縮感測資料，否則，感測資料必定會佔據大量的存儲空間並且降低資料伺服器(data server)的效能。基於這些原因，我們之前提出類視訊無失真壓縮方法，稱為VLLC (Video-Like Lossless Compression)，目標在於利用感測資料的特性。空間相關性以及時間相關性來提高資料壓縮率和減少資料壓縮的時間；在類視訊無失真壓縮系統中，會參考相關性將原始的感測資料無失真地轉換並排列成固定格式的資料幀(data frame)，而這些資料幀形成一個3D的立體像素(voxel)，並可用H.264進行視訊壓縮，由於立體像素結構的關係，資料能被直接存取而不需要解壓縮所有的壓縮檔案。本論文將針對類視訊無失真壓縮提供有效率的資料查詢流程，並提供語法讓使用者查詢感測資料，除此之外，我們還設計平行處理方法以提高壓縮和解壓縮速率，分析並比較不同資料擺放法(data placement)的效能，提高整體效率。在我們的實驗中，對於4.53GB的感測資料進行類視訊壓縮能較未壓縮省下超過92%的資料空間，並且壓縮時間能低於43秒。另外，感測資料在16台平行處理平台下，採用合適的資料擺放法，將可比隨機擺放節省下62%的處理時間。

Wireless Sensor Networks (WSNs) consist of groups of resource-restricted sensor nodes that collect sensory data and monitor environmental changes. WSN environment services gather sensory data for various purposes. To store the collected information, systems should organize and compress sensory data using proper methods. Otherwise, sensory data will occupy a large amount of storage and decrease the server’s performance. In this thesis, we proposed a video-like lossless compression (VLLC), which aims to adopt the spatial correlation of sensory data in WSNs to enhance the degree of space saving and reduce the data compression time. In VLLC, systems will transform and arrange raw data as formatted video frames without loss according to the spatial correlation. The video frames form 3D voxels that can be highly compressed by H.264. Based on the voxel structure, data can be directly accessed without extracting all the compressed data. VLLC provides an efficient processing flow for querying sensory data and a query command that allows clients to access the proposed database. In our experiment, a space saving of more than 92% was achieved, and the data compression time for 4.53 GB of sensory data was less than 43 seconds. Furthermore, VLLC also offers a parallel processing method to enhance compression and decompression speed. To enhance the efficiency of the system, we also analysis and compare the different data placement methods. In our experiments, if we take proper personal data placement method, we will save 62% processing time with 16 personal computers more than random placement.

目錄
口試委員會審定書 #
誌謝 i
中文摘要 ii
英文摘要 iii
目錄 iv
圖目錄 vi
表目錄 ix
第1章 簡介 1
1.1 研究動機 1
1.2 目標與貢獻 2
1.3 論文架構 2
第2章 文獻探討 6
2.1 資料壓縮方法 6
2.2 資料伺服器 6
2.3 時間相關性與空間相關性 7
第3章 系統概觀 9
3.1 系統架構 9
3.2 VLLC實作方法 11
3.3 Query Process in VLLC 14
3.3.1 Single Query 14
3.3.2 Range Data Query 15
3.3.3 Query Scenario 17
3.4 Parallel computation in data server 19
第4章 模擬結果 23
4.1 類視訊無失真壓縮 23
4.2 資料擺放法 31
第5章 結論與未來研究 39
參考文獻 41

參考文獻
[1]C.F. Garcia-Hernandez, P.H. Ibarguengoytia-Gonzalez, J. Garcia-Hernandez, and J.A. Perez-Diaz, "Wireless Sensor Networks and applications: a survey," International Journal of Computer Science and Network Security, vol. 7, pp. 264-273, March 2007.
[2]D. Culler, D. Estrin, and M. Srivastava, "Guest Editors'' Introduction: Overview of Sensor Networks," Computer, vol. 37, pp. 41-49, 2004.
[3]R. Szewczyk, A. Mainwaring, J. Polastre, J. Anderson and D. Culler, "An Analysis of a Large Scale Habitat Monitoring Application," Embedded Networked Sensor Systems, November 2004.
[4]B. Zhou, C. Hu, H.B. Wang, R. Guo and Q.H. Meng, "A Wireless Sensor Network for Pervasive Medical Supervision," International Conference on Integration Technology, March 2007.
[5]I.F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, "A survey on sensor networks," Communications Magazine, IEEE, vol. 40, pp. 102-114, 2002.
[6]Y. Liang and W. Peng, "Minimizing energy consumptions in wireless sensor networks via two-modal transmission," SIGCOMM Comput. Commun. Rev., vol. 40, pp. 12-18, 2010.
[7]V. Singla, R. Singla and S. Gupta, "Data compression modeling : Huffman and Arithmetic," International Journal of The Computer, vol. 16, pp. 64-48, December 2008.
[8]K.C. Barr and K. Asanovic, "Energy-aware Lossless Data Compression," Transactions on Computer Systems, vol. 24, pp. 250-291, August 2006.
[9]Z. Zhang and O. Berger, "Cluster based data query analysis and optimization for Wireless Sensor Networks," Advanced Communication Technology, February 2008.
[10]S. Zhou, Y. Lin, J. Wang, J. Zhang and J. Ouyang, "Compressing Spatial and Temporal Correlated Data in Wireless Sensor Networks Based on Ring Topology," Lecture Notes in Computer Science, vol. 4016, pp. 337-348, October 2006.
[11]J.M. Miranda, E. Reynaud, F. McGlone, G. Calvert and M. Brammera, "The impact of temporal compression and space selection on SVM analysis of single-subject and multi-subject fMRI data," NeuroImage, vol. 33, pp. 1055-1056, December 2006.
[12]7-Zip. Available: http://www.7-zip.org/
[13]WinRAR. Available: http://www.rarlab.com/
[14]R. Asraf, M. Akbar and N. Jafri, "Statistical analysis of difference image for absolutely Lossless compression of medical images," Engineering in Medicine and Biology Society, September 2006.
[15]D. S. Taubman and M. W. Marcellin, "JPEG2000: Fundamentals, Standards, and Practice," Published by Kluwer Academic Publishers, 2002.
[16]M. J. Weinberger, G. Seroussi, and G. Sapiro, "The LOCO-I lossless image compression algorithm: principles and standardization into JPEG-LS," Image Processing, IEEE Transactions on, vol. 9, pp. 1309-1324, 2000.
[17]R. Starosolski, "Simple fast and adaptive lossless image compression algorithm," Software: Practice and Experience, vol. 37, pp. 65-91, 2007.
[18]F. Marcelloni and M. Vecchio, "An Efficient Lossless Compression Algorithm for Tiny Nodes of Monitoring Wireless Sensor Networks," Comput. J., vol. 52, pp. 969-987, 2009.
[19]C. Tharini and P. V. Ranjan, "Design of modified adaptive Huffman data compression algorithm for wireless sensor network," Journal of Computer Science, vol. 5, pp. 466-470, 2009.
[20]L.D. Chagas, E.P. Lima and P.F.R. Neto, “Real-Time Databases Techniques in Wireless Sensor Networks,” International Conference on Networking and Services, March 2010.
[21]Oracle. Available: http://www.oracle.com/tw/index.html
[22]SQL Server. Available: http://www.microsoft.com/taiwan/sql/default.mspx
[23]MySQL: The world''s most popular open source database. Available: http://www.mysql.com
[24]TINYLIME: LIME FOR SENSOR NETWORKS. Available: http://lime.sourceforge.net/tinyLime/index.html
[25]TinyDB: A Declarative Database for Sensor Networks. Available: http://telegraph.cs.berkeley.edu/tinydb/
[26]COUGAR: The Network Is The Database. Available: http://www.cs.cornell.edu/bigreddata/cougar/index.php
[27]M.H. Li, C.C. Lin, C.C. Chuang and R.I. Chang, “Error-bounded data compression using data, temporal and spatial correlations in Wireless Sensor Networks,” Multimedia Information Networking and Security, November 2010.
[28]C.C. Lin, C.C. Chuang, C.W. Chiang and R.I. Chang, "A Novel Data Compression Method using Improved JPEG-LS in Wireless Sensor Networks," International Conference on Advanced Communication Technology, February 2010.
[29]J. Valdes, R.E. Tarjanand E.L. Lawler, "The recognition of Series Parallel digraphs," ACM symposium on Theory of computing, 1979.
[30]D.K. Madathil, R.B. Thota, P. Paul and T. Xie, "A Static Data Placement Strategy towards Perfect Load-Balancing for Distributed Storage Clusters," International Symposium on Parallel and Distributed Processing, April 2008.
[31]C.M. Wang and S.D. Wang, "Efficient processor assignment algorithms and loop transformations for executing nested parallel loops on multiprocessors," IEEE Transactions on Parallel and Distributed Systems, vol. 3, pp. 71-82, January 1992.
[32]A.N. Choudhary,B. Narahari, D.M. Nicol and R. Simha, "Optimal Processor Assignment for a Class of Pipelined Computations," IEEE Transactions on Parallel and Distributed Systems, vol. 5, pp. 439-445, April 1994.
[33]H. Back, H.S. Chwa and I. Shin, "Schedulability Analysis and Priority Assignment for Global Job-Level Fixed-Priority Multiprocessor Scheduling," IEEE Symposium on Real-Time and Embedded Technology and Applications, April 2012.
[34]Ch. Xu, X. Chen, R.P. Dick and Z.M. Mao, "Cache Contention and Application Performance Prediction for Multi-Core Systems," IEEE International Symposium on Performance Analysis of Systems & Software, March 2010.
[35]D.Q. Ren and R. Suda, "Investigation on the Power Efficiency of Multi-core and GPU Processing Element in Large Scale SIMD Computation with CUDA," Green Computing Conference, August 2010.