臺灣博碩士論文加值系統

　　在無線網路的拉式架構之下，客戶端向伺服器端請求播送資料，為了解決冷、熱門資料不同點播率及客戶端請求之後等待時間過久的問題，伺服器端同時考慮資料項的被點播率與客戶端請求資料的等待時間之後，再決定播送的資料項。在真實的環境之下，資料項的被點播率與客戶端請求的等待時間會隨著時間而不斷改變。若同時考慮上述兩個因素，伺服器端在每次廣播前必需重算全部資料項的權重值，再決定廣播的資料項，這是非常耗資源且低效率的方法。為了解決這樣的問題，我們提出動態排程演算法(DYSA)來解決上述的問題。DYSA使用資料項的權重值來維護最大堆積樹，以供快速廣播資料項。此外，我們利用索引的技巧來加速堆積樹裡資料項的存取。在最後的模擬實驗結果顯示，在動態環境的要求下，DYSA比一般演算法有更好的執行效能。

　　In the pull-based wireless network, clients request data items from a server. In order to solve cold and hot data, and reduce clients'' waiting timer, server considers hit rate of data items and waiting time of requests for broadcasting. The hit rate of data items and the waiting time of requests always changed along with time elapsed. Therefore, server has to calculate overall weight value of data items and decides maximum weight value of data items before broadcasting. In order to increase performance of server, we propose a dynamically schedule algorithm (DYSA) for wireless broadcast. The DYSA uses weight value of data items and maintains them in a maximum heap tree for quickly broadcasting. Furthermore, we present a indexing for accessing a data item''s information faster. The experiment results show that our method has more effectively than a common algorithm in the dynamic wireless environment.

書名頁 i
博碩士論文授權書 ii
著作財產權同意書 iii
論文指導教授推薦函 iv
論文口試合格證明 v
誌 謝 vi
中文摘要 vii
英文摘要 viii
目　　錄 ix
表 目 錄 xi
圖 目 錄 xii
　
第一章 序論 1
第一節 研究背景與動機 1
第二節 研究主題 2
第三節 研究限制 3
第四節 研究架構 4
第五節 簡介 5
　
第二章 文獻探討 8
第一節 背景環境 9
第二節 相關文獻 16
　
第三章 問題描述 23
第一節 符號定義與說明 23
第二節 無線廣播的運作 26
第三節 動態環境 28
第四節 資料廣播的問題 29
　
第四章 動態排程演算法 35
第一節 主要概念 35
第二節 運作程序 41
第三節 動態排程演算法 44
第四節 堆積樹的運作 46
第五節 時間複雜度 52
　
第五章 模擬實驗 56
第一節 模擬環境 56
第二節 模擬參數 58
第三節 實驗結果 60
　
第六章 結論 70
　
參考文獻 71

中文部份
　
[1]林士揚, "適用於無線隨意網路下之分散式差異性服務", 碩士論文, 七月, 2003.
　
[2]周雨韻, "以電力能源為基礎的蜂巢式階層管理", 碩士論文, 五月, 2005.
　
[3]夏銘君, "在移動隨意網路下支援多對多群播及廣播服務", 碩士論文, 七月, 2003
　
西文部份
　
[4]Demet Aksoy and Michael Franklin, "R*W: A Scheduling Approach for Large-Scale On-Demand Data Broadcast," IEEE/ACM Transactions on Networking, vol. 7, no. 6, pp.846-860, 1999.
　
[5]Tomonori Asano, Hiroyuki Unoki and Hiroaki Higaki, "LBSR:Routing Protocol for MANETs with Unidirectional Links," IEEE, Proceedings of the 18th International Conference on Advanced Information Networking and Application, vol. 1, pp.219-224, 2004.
　
[6]Ruay-Shiung Chang, Wei-Yeh Chen and Yean-Fu Wen, "Hybrid Wireless Network Protocols," IEEE Transactions on Vehicular Technology, vol. 52, no. 4, pp.1099-1109, 2003.
　
[7]Ye-In Chang and Wu-Han Hsieh, "An Efficient Scheduling Method for Query-Set-based Broadcasting in Mobile Environments," IEEE, Proceedings of the 24th International Conference on Distributed Computing Systems Workshops, pp.478-483, 2004.
　
[8]David B. Johnson and David A. Maltz, "Dynamic Source Routing in Ad Hoc Wireless Networks," IEEE Transactions on Mobile Computing, vol.353, pp.153-181, 1996.
　
[9]Chiu-Kuo Liang and Hsi-Shu Wang, "An Ad Hoc On-Demand Routing Protocol with High Packet Delivery Fraction," IEEE, International Conference on Mobile Ad-hoc and Sensor Systems, pp. 594-596, 2004.
　
[10]Charles E. Perkins and Elizabeth M. Royer, "Ad Hoc On-demand Distance Vector Routing," IEEE, Workshop on Mobile Computing Systems and Applications, pp. 90-100, 1999.
　
[11]Fumiaki Sato and Tadanori Mizuno, "A Route Reconstruction Method Based on Support Group Concept for Mobile Ad hoc Networks," IEEE, Proceedings of the 19th International Conference on Advanced Information Networking and Applications, pp. 84-89, 2005.
　
[12]Navrati Saxena, Kalyan Basu and Sajal K. Das, "Design and Performance Analysis of a Dynamic Hybrid Scheduling Algorithm for Heterogeneous Asymmetric Environments," IEEE, Proceedings of the 18th International Parallel and Distributed Processing Symposium, pp.223-229, 2004.
　
[13]Haw-Yun Shin, Jean-Lien C. Wu and Yi-Hsien Wu, "A Packet Scheduling Scheme for Broadband Wireless Networks with Heterogeneous services," IEEE, Proceedings of the 18th International Conference on Advanced Information Networking and Application, vol. 2, pp.355-358, 2004.
　
[14]Yi-Yu Su, Shiow-Fen Hwang and Chyi-Ren Dow, "An Efficient Multi-Source Multicast Routing Protocol in Mobile Ad Hoc Networks," IEEE, International conference on parallel and Distributed Systems, vol. 1, pp.8-14, 2005.
　
[15]Weiwei Sum, Weibin Shi, Bole Shi and Yijun Yu, "A cost-efficient scheduling algorithm of on-demand broadcasts," Manufactured in The Netherlands, Wireless Networks 9, pp.239–247, 2003.
　
[16]Juki Wirawan Tantra, Chuan Heng Foh, and Bu Sung Lee, "An Efficient Scheduling Scheme for High Speed IEEE 802.11 WLANs," IEEE, Vehicular Technology Conference, vol. 4, pp.2589-2593, 2003.
　
[17]Hsin-Wen Wei, Pei-Chi Huang, Hsung-Pin Chang and Wei-Kuan Shih, "Scheduling Real-Time Information in a Broadcast System with Non-Real-Time Information," IEEE, Proceedings of the 11th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, pp.289-292, 2005.
　
[18]Xiao Wu and Victor C. S. Lee, "Preemptive Maximum Stretch Optimization Scheduling for Wireless On-Demand Data Broadcast," IEEE, Proceedings of the International Database Engineering and Applications Symposium, pp.413-418, 2004.
　
[19]Yiqiong Wu and Guohong Cao,"Stretch-Optimal Scheduling for On-Demand Data Broadcasts," IEEE, Proceedings of the IEEE International Conference on Computer Communications and Networks, pp.500-504, 2001.
　
[20]Etsuko Yajima, Takahiro Hara, Masahiko Tsukamoto and Shojiro Nishio, "Scheduling and Caching Strategies for Broadcasting Correlated Data," Symposium on Applied Computing archive Proceedings ACM, pp.504-510, 2001.