跳到主要內容

臺灣博碩士論文加值系統

(18.97.9.172) 您好!臺灣時間:2025/02/16 20:14
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:林曉吟
研究生(外文):Siao-yin Lin
論文名稱:無線廣播環境下應用KL演算法於相關資料排程的配置研究
論文名稱(外文):Using K-L based Algorithm for correlated data allocation in wireless broadcast system
指導教授:蔡德謙蔡德謙引用關係
指導教授(外文):Der-chian Tsaih
學位類別:碩士
校院名稱:南華大學
系所名稱:資訊管理學研究所
學門:電算機學門
學類:電算機一般學類
論文種類:學術論文
論文出版年:2006
畢業學年度:94
語文別:中文
論文頁數:75
中文關鍵詞:無線廣播KL演算法平均查詢讀取時間
外文關鍵詞:average response timewireless broadcastKL algorithm
相關次數:
  • 被引用被引用:0
  • 點閱點閱:540
  • 評分評分:
  • 下載下載:19
  • 收藏至我的研究室書目清單書目收藏:1
  無線網路的環境之下頻寬資源是有限的,透過伺服端以廣播的方式,可以有效率的傳送資料、利用頻寬。伺服端決定出一組較佳的廣播序列,能夠滿足用戶端的查詢需求,讓用戶端快速的取得所需資料。
 
  本文探討的無線廣播排程問題中,以廣播資料項之間存在的相依性為主要考量,使用有向無循環圖形(DAG)表示其順序限制,且每一資料項對應於圖形中每一頂點,並應用加入Greedy方式之拓樸排序演算法、積體電路設計中常被使用的KL演算法,以及SA模擬退火演算法等方法於有向無循環圖形的排序問題,試圖降低頂點之間平均路徑長度,以減少用戶端平均查詢讀取時間,並透過模擬實驗結果的顯示分析,比較這幾種方法的優劣。實驗結果顯示,使用我們所提出加入Greedy方式的拓樸排序演算法,以及KL演算法、SA演算法,確實可以縮短資料項之間的相依性長度,降低用戶端在收取所需資料項時花費的平均查詢讀取時間。
  The resource of transmission bandwidth is limited under the wireless network environment. If data is broadcasted from server, bandwidth utilization can be maximized and data can be transmitted more efficiently. To satisfy the need of many different requests from mobile hosts, the broadcast server must schedule the data item such that most mobile host can read data from broadcast channel in short period of time.
 
  Our context focus on the scheduling problem of wireless broadcast, consider dependence between each data item which are broadcasted. The directed acyclic graph was used with its edges as this dependence limitation and its vertex as its data item. Arrange the vertex set by topological sort with greedy strategy, KL algorithm which are used in integrated circuit design problem and Simulated Annealing (SA) algorithm to minimize the average edge weight across all vertices. This broadcasted order of data item will then minimize the average response time for client’s queries. The results for applying each algorithm in data schedule problem were shown and compared through extensive simulation.
書名頁 ii
博碩士論文授權書 iii
著作財產權同意書 iv
論文指導教授推薦函 v
論文口試合格證明 vi
誌 謝 vii
中文摘要 viii
英文摘要 ix
目  錄 x
表 目 錄 xii
圖 目 錄 xiii
 
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的與限制 4
1.3 研究架構 5
 
第二章 文獻探討 7
2.1 圖形結構 7
2.1.1 無向圖形(Undirected Graphs) 7
2.1.2 有向圖形(directed graph) 8
2.1.3 頂點工作網路(Activity On Vertex Network) 9
2.2 拓樸排序 10
2.2.1 深度優先走訪(Depth-First Algorithm): 11
2.2.2 廣度優先走訪(Breadth-First Algorithm): 12
2.3 KL最佳化演算法 13
2.4 SA模擬退火演算法 14
 
第三章 問題描述 18
3.1 無線廣播排程 18
3.2 平均查詢讀取時間 21
3.3 最小分割問題 22
 
第四章 研究方法 25
4.1 廣播查詢轉換有向圖形 25
4.2 Greedy之拓樸排序演算法 35
4.3 KL最佳化演算法 48
4.4 模擬退火(SA)演算法 56
 
第五章 模擬實驗 65
5.1 模擬環境 65
5.2 實驗資料檔的產生與介紹 65
5.3 實驗結果分析 67
 
第六章 結論 72
 
參考文獻 73
[1] E. H. L. Aarts, F. M. J. De Bont, E. H. A. Haberts and P. J. M. Van Laarhoven,"Statistical Cooling: A General Approach to Combinatorial Optimizations", Philips Journal of Research, Vol. 4,pp.193-226, 1985.
 
[2] N. Abbound, M. Sakawa and M. Inuiguchi, "Statistical Cooling: A General Approach to Combinatorial Optimizations", Philips Journal of Research, Vol. 29, pp.593-611, 1998.
 
[3] S. Acharya, R. Alonso, M. Franklin and S. Zdonik, "Broadcast disks: Data mangement for asymmetric communication environments," Proceedings of ACM SIGMOD Conference, pp. 199-210, 1995.
 
[4] S. Acharya, M. Franklin and S. Zdonik, "Disseminating updates on broadcast disks," in proceedings of Very Large Data Bases Conference, pp. 354-365, 1996.
 
[5] D. Aksoy and M. S. F. Leung, "Pull vs Push: A Quantitative Comparison for Data Broadcast," Global Telecommunications Conference, Vol. 3 ,pp.1464-1468, 2004.
 
[6] A. A. Bertossi, M. C. Pinotti and S. Ramaprasad, "Optimal multi-channel data allocation with flat broadcast per channel," Proceedings of the 18th International Parallel and Distributed Processing Symposium, 2004.
 
[7] O. E. Demir and D. Aksoy, "Energy-Efficient Broadcast-based Event Update Dissemination," Pertormance, Computing, and Communications, 2004 IEEE International Conference ,pp. 477-482, 2004.
 
[8] Q. Fang, S. V. Vrbsky, Y. Dang and W. Ni, "A Pull-Based Broadcast Algorithm that Considers Timing Constraints," Proceedings of the International Conference on Parallel Processing Workshops, 2004.
 
[9] C. M. Fiduccia and R. M. Mattheyses, "A Linear-time Heuristic for Improving Network Partitions", Proc. Design Automation Conf., pp. 175-181, 1982.
 
[10] M. Garey and S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, Freeman, 1979.
 
[11] L. Hagen and A. B. Kahng, "Fast Spectral Methods for Ratio Cut Partitioning and Clustering", Proc. International Conf. on Computer-Aided Design, pp. 10-13, 1991.
 
[12] J. L. Huang and M. S. Chen, "Broadcast Program Generation for Unordered Queries with Data Replication," Proceedings of the ACM Symposium on Applied Computing, pp. 866-870, 2003.
 
[13] J. L. Huang and M. S. Chen, "Dependent Data Broadcasting for Unordered Queries in a Multiple Channel Mobile Environment," IEEE Transaction on Knowledge and Data Engineering ,Vol.16, No.9, pp. 1143-1156, 2004.
 
[14] J. L. Huang, M. S. Chen and W. C. Peng , " Broadcasting Dependent Data for Order Queries Without Replication in a Multi-Channel Mobile Environ ment," Proceedings of the 19th International Conference on Data Engineering, 2003.
 
[15] Y. Huang and Y. H. Lee, "An Efficient Indexing Method For Wireless Data Broadcast With Dynamic Updates," Communications, Circuits and Systems and West sino Expositions, IEEE 2002 International Conference, Vol.29, pp. 358-362, 2002.
 
[16] J. J. Huang and Y. Lee, "Efficient Index Caching Schemes for Data Broadcasting in Mobile Computing Environments," Proceedings of the 14th International Workshop on Database and Expert Systems Applications, 2003.
 
[17] 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.
 
[18] G. Karypis, R. Aggarwal, V. Kumar and S. Shekhar, "Multilevel Hypergraph Partitioning:Applications in VLSI Domain," Department of Computer Science, University of Minnesota, Minneapolis, MN, USA, 1997.
 
[19] G. Karypis and V. Kumar, "METIS: Unstructured Graph Partitioning and Sparse Matrix Ordering-Version 2.0," Department of Computer Science,University of Minnesota, Minneapolis, MN, USA, 1995.
 
[20] B. W. Kernighan and S. Lin, "An Efficient Heuristic for Partitioning Graphs," The Bell System Technical Journal, 49, pp. 291-308, 1970.
 
[21] S. Kirkpatrick, C. D. Gelatt and M. P. Vecchi, "Optimization by Simulated Annealing", Science, pp. 671-680, 1983.
 
[22] G. Lee, M. S. Yeh, S. C. Lo and A. L. Chen, "A Strategy for Efficient Access of Multiple Data Items in Mobile Environments," Proceedings of the Third International Conference on Mobile Data Management , 2002.
 
[23] J. Ma, K. Iwama, T. Takaoka and Q. P. Gu, "Efficient Parallel and Distributed Topological Sort Algorithms," Parallel Algorithms/Architecture Synthesis, Proceedings, Second Aizu International Symposium, pp. 378-383, 1997.
 
[24] W. Ni , Q. Fang and S. V. Vrbsky , "A Lazy Data Request Approach for On-demand Data Broadcasting," Proceedings of the 23rd International Conference on Distributed Systems Workshops , 2003.
 
[25] W. C. Peng, J. L. Huang and M. S. Chen, "Dynamic Leveling: Adaptive Data Broadcasting in a Mobile Computing Environment," Mobile Networks and Applications 8, pp. 355-364, 2003.
 
[26] OBV Ramanaiah and H. Mohanty, "NICD: A Novel Indexless Wireless On-Demand Data Broadcast Algorithm," Proceedings of the Internation Conference on Information Technology: Coding and Computing , 2004 .
 
[27] N. Saxena, K. Basu and S. K. Das, "Design and Performance Analysis of a Dynamic Hybrid Scheduling Algorithm for Heterogeneous Asymmetric Environments," Proceedings of the 18th International Parallel and distributed Processing Symposium , 2004.
 
[28] S. Wang and H. L. Chen, "Near-Optimal Data Allocation Over Multiple Broadcast Channels," Networks, Proceedings. 12th IEEE International Conference on Vol 1, pp. 207-211, 2004.
 
[29] X. Wu and V. C. S. Lee, "Preemptive Maximum Stretch Optimization Scheduling for Wireless On-Demand Data Broadcast," Proceeding of the International Database Engineering and Applications Symposium , 2004.
 
[30] J. Xu, B. Zheng, W. C. Lee and D. L. Lee, "Energy Efficient Index for Querying Location-Dependent Data in Mobile Broadcast Environments," Proceedings of the International Conference on Data Engineering , 2003.
 
[31] J. Zhang and L. Gruenwald , "Optimizing Data Placement Over Wireless Broadcast Channel For Multi-Dimensional Range Query Processing," Proceedings of the International Conference on Mobile Data Management, 2004.
 
[32] G. K. Zipf. Human Behavior and the Principle of Least Effort. Addison-Wesley, Massachusetts, 1949.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
1. 陳亮全,1996,<社區總體營造在台灣>,《空間雜誌》。
2. 陳亮全,2000,<近年台灣社區總體營造之展開>,《住宅學報》。
3. 陳其南、陳瑞樺,1998,<台灣社區營造運動之回顧>,《研考報導》。
4. 曾肅良,2003,<文化圖騰、本土意識與社區總體營造的迷思>,《美育》。
5. 王麗容,1999,社區永續發展與國家政策。社會文化學報,8,141-153。
6. 朱美珍,1999,台灣社區發展的歷史過程與未來發展。人文學報,4:23,61-81。
7. 吳宜蓁,1998,有線電視公用頻道與社區意識—描繪一個「公用頻道運作中心」的藍圖。新聞學研究。56,219-235。
8. 林瑞欽,1994,社區意識的概念、測量與提振策略。社會發展研究學刊,1,1-21。
9. 林瑞欽,1995,「社區意識」凝聚之道。社會福利,118,8-17。
10. 林振春,1994,如何凝聚社區意識、整建社區社會。理論與政策,8(4),117-129。
11. 施教裕,1997,社區參與的理論與實務。社會福利,129,2-8。
12. 侯錦雄、宋念謙,1998,台中市黎明住宅社區居民社區意識之研究。建築學報,24,51-65。
13. 徐震,1995,論社區意識與社區發展。社會建設,90,4-12。
14. 陳麗華,1997,社區參與學習的理念和實施。國教月刊,43(7),44-53。
15. 黃肇新,1998,地方政府的社區組織與社區政策之研究—以高雄縣為例。研考報導,41,44-54。