臺灣博碩士論文加值系統

近年來由於無線通訊環境的發展，人們利用無線裝置獲取資訊與交換訊息的方式大為普及與便利。但因為無線裝置(手機或PDA等)電池能源有限，如何讓客戶端有效率的下載資訊，延長電池能源使用的時間，已成為目前需要解決的問題。相關研究大多在廣播週期中，加入額外資訊，縮短客戶端下載資料的時間，主要方法可分為預測式廣播機制與非預測式廣播機制。非預測式廣播機制有雜湊機制與索引機制。雜湊機制將雜湊函數放到廣播週期中，但可能因雜湊函數的溢位問題增加搜尋資料時間；而索引機制將索引資訊放入廣播週期，可能因沿著樹狀索引結構搜尋增加搜尋資料時間。預測式廣播機制有斜率預測法與線性規劃法。斜率預測法利用資料鍵值計算出資料可能廣播位置，但可能因等距分段導致預測誤差加大；線性規劃法利用線性規劃法的限制式求出預測函數以預測資料廣播位置，可有效縮短調整時間，但會造成伺服端極大的負擔。此外，斜率預測法與線性規劃法各有其調整參數，不易進行分析比較，因此本研究以實驗進行預測式廣播機制的模擬比較，同時亦提出最小平方法之預測式廣播機制，改善現有預測式廣播機制的缺點，並做三種預測式廣播機制的模擬比較。評估的指標包括初始等待時間(probe wait time)、調整時間(tuning time)、讀取時間(access time)、索引空間、預測誤差等。實驗模擬結果顯示最小平方法之預測式廣播機制可有效地降低預測誤差，對線性規劃法及斜率預測法分別減少了83.24%、93.40%的誤差；而線性規劃法則有最短的調整時間；至於斜率預測法所需索引空間為最少。

In recent years, the development of wireless communication environment has made it popular to use mobile devices to get information and exchange messages. Because of the limit energy in mobile devices, how to download information efficiently and to save the energy for mobile devices have become essential problems. Related studies used to insert additional information in the broadcast cycle for the purpose. Their solutions can be classified into two categories: predictive and non-predictive broadcast schemes. Non-predictive broadcast schemes, such as the hash schemes and index schemes, insert the hash function or index tree into a broadcast cycle, resulting in longer broadcast cycles and tuning time because of collision or tree traversal. On the other hand, predictive broadcast schemes can reduce tuning time effectively if their prediction errors are minimized or limited.
Existent predictive broadcast schemes include the slope prediction method and the linear-programming prediction method. Since both schemes have a different set of parameters for performance tuning, they are difficult to compare analytically. In this study, we propose a new broadcast scheme, namely least-square prediction method, to improve the prediction errors of both schemes, and conduct a simulation study on the three prediction-based broadcast schemes. The performance metrics include index space, probe wait time, prediction error, tuning time, and access time. Experimental results show that the least-square prediction method can effectively reduce the prediction error, improving 83.24% of the prediction error in the linear-programming prediction method and 93.40% of that in the slope prediction method. The linear-programming prediction method has the shortest tuning time, while the slope prediction method needs the least index space for the broadcast cycle.

第一章 簡介…………………………………………………………1
1.1 研究背景…………………………………………………1
1.2 研究動機…………………………………………………3
1.3 研究問題與研究步驟……………………………………4
1.4 研究成果與論文結構……………………………………4
第二章 相關研究……………………………………………………6
2.1 非預測式廣播機制………………………………………6
2.1.1 雜湊機制…………………………………………6
2.1.2 索引機制…………………………………………7
2.1.2.1 彈性索引機制……………………………8
2.1.2.2 (1,m)與分散式索引機制………………‥9
2.2預測式廣播機制…………………………………………10
2.2.1 資料落點座標系…………………………………10
2.2.2 斜率預測法………………………………………12
2.2.3 線性規劃法………………………………………14
第三章 最小平方法之預測式廣播機制……………………………16
3.1 最小平方法求取預測函數………………………………16
3.2 分段式最小平方法………………………………………18
3.3 廣播週期的結構…………………………………………20
3.4 建立廣播週期的內容……………………………………22
3.5 客戶端讀取資料之狀態轉移圖…………………………25
3.6 客戶端讀取資料演算法…………………………………28
3.7 效能分析…………………………………………………30
第四章 實驗結果與分析……………………………………………33
4.1實驗平台與測試資料………………………………………33
4.2 最小平方法預測式廣播機制之效能……………………36
4.2.1 q值對效能的影響…………………………………36
4.2.2 max_e對效能的影響………………………………41
4.3 線性規劃法預測式廣播機制之效能………………………48
4.4 斜率預測法預測式廣播機制之效能…………………54
4.4.1 基準點個數對效能的影響…………………………54
4.4.2 斜率範圍切割數對效能的影響……………………58
4.4.3 基準鍵值斜率標準差對效能的影響………………63
4.5 預測式廣播機制模擬實驗參數設定………………………68
4.6 索引空間之模擬比較…………………………………69
4.7 初始等待時間之模擬比較……………………………74
4.8 預測誤差之模擬比較…………………………………79
4.9 調整時間之模擬比較…………………………………84
4.10 讀取時間之模擬比較…………………………………90
4.11 實驗結論………………………………………………………95
第五章 結論與未來方向…………………………………………………97
參考文獻…………………………………………………………………99

[1]R. Agrawal, P.K. Chrysanthis, “Efficient Data Dissemination to Mobile Clients in E-Commerce Applications,” Advanced Issues of E-Commerce and Web-Based Information Systems, Third International Workshop on, 2001, pp. 58-65.
[2]D. Barbara, R. Jain and N. Krishnakumar, Database and Mobile Computing, Kluwer Academic Publishers, 1996.
[3]A. Datta, D. E. Vandermeer , A. Celik and V. Kumar, “Broadcast Protocols to Support Efficient Retrieval from Databases by Mobile Users,” ACM Transactions on Database System, Vol. 24, No. 1, 1999, pp. 1-79.
[4]R. L. Eubank, Nonparametric Regression and Spline Smoothing, 2nd ed., Marcel Dekker, 1999.
[5]R. W. Farebrother, Linear Least Squares Computations, Marcel Dekker, 1988.
[6]T. Imielinksi and B. Badrinath, “Mobile Wireless Computing : Challenges in Data Management,” Communication of the ACM, Vol.37, No.10, 1994, pp.18-28.
[7]T. Imielinski and H. F. Korth, Mobile Computing, Kluwer Academic Publishers, 1996.
[8]T. Imielinski, S. Viswanathan, and B. Badrinath, “Energy Efficient Indexing on Air,” Proceedings of ACM SIGMOD Conference, 1994, pp.25-36.
[9]T. Imielinski, S. Viswanathan, and B.R. Badrinath, Data on Air: Organization and Access, Technical Report, Department of Computer Science, Rutgers University, U.S.A., 1994.
[10]T. Imielinski, S. Viswanathan and B.R. Badrinath, ”Power Efficient Filtering of Data on Air,” Proceedings of the International Conference on Extending Database Technology, 1994, pp. 245-258.
[11]K. F. Jea and M. H. Chen, “A Data Broadcast Scheme Based on Prediction for The Wireless Environment,” Proceedings of the Ninth International Conference on Parallel and Distributed Systems, 2002, pp. 551-556.
[12]K. F. Jea and C. L. Wu, “A Data Partition Scheme for Wireless Broadcast Mechanisms Based on Linear Programming,” Proceedings of the International Computer Symposium Workshop on Database and Software Engineering, 2002, E5-3, pp. 1-8.
[13]D. L. Lee, “Data Management in a Wireless Environment,” International Database Systems for Advanced Application Conference, Taiwan, 1999.
[14]K. C. Laudon, C. G. Traver, E-commerce : business. technology. society, Addison Wesley, 2002.
[15]王慧君, 林吉仁, 黃明官, 廖宜誠共譯, 統計學, 高立圖書, 1996.
[16]王敦文, 運用線性規劃之廣播機制, 碩士論文, 國立中興大學, 2001.
[17]邱振崑, EXCEL在統計學與經濟學之應用, 松崗電腦, 2001.
[18]林光賢譯, 機率導論第四版, 華泰書局, 1994.
[19]林丕靜, 數值分析, 儒林書局, 2002.
[20]吳大偉, 楊進丁, 葉官俤, 載任詔共譯, 基礎數值分析—使用C語言實作—, 高立圖書, 1997.
[21]吳俊樂, 利用分段法改善線性規劃式無線廣播機制, 碩士論文, 國立中興大學, 2002.
[22]祝華健譯, 數值分析—由實用的觀點來探討, 儒林圖書, 1984.
[23]張耀祖, 白煌朗, 方偉平編譯, 數值分析, 松崗電腦, 1987.
[24]陳銘輝, 利用鍵值斜率在無線廣播頻道之資料預測機制, 碩士論文, 國立中興大學, 2002.
[25]陳世芳, 陳昭綾, 數值方法入門—使用C語言—, 全華圖書, 1999.
[26]許全福譯, 數值分析, 東華書局, 1995.
[27]載義國, 蔡新春編著, 數值分析, 文京圖書, 1992.
[28]葉序, 網路資訊雜誌, 麥格辛網路出版股份有限公司, 2003.