跳到主要內容

臺灣博碩士論文加值系統

(54.224.133.198) 您好!臺灣時間:2022/01/29 21:33
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:林清鵬
研究生(外文):Ching-Peng Lin
論文名稱:線性多重選擇性背包問題在網頁內容決選之應用
論文名稱(外文):A Linear Multi-Choice Knapsack Problem with Application in Web Content Adaptation
指導教授:簡榮宏簡榮宏引用關係
指導教授(外文):Rong-Hong Jan
學位類別:碩士
校院名稱:國立交通大學
系所名稱:資訊科學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:中文
論文頁數:44
中文關鍵詞:配備性能適應性動態規劃網路頻寬
外文關鍵詞:LMCKPknapsack problemAdaptationCC/PPdynamic programming
相關次數:
  • 被引用被引用:1
  • 點閱點閱:352
  • 評分評分:
  • 下載下載:63
  • 收藏至我的研究室書目清單書目收藏:1
隨著個人通訊的設備不斷的進步以及Internet的蓬勃發展,WWW的服務漸漸在日常生活中變得重要,透過WWW的服務,人們能夠獲取豐富的全球資訊。因為通訊設備的多樣化(如:個人電腦、掌上型電腦、個人數位助理、手機),如何透過各種不同的通訊設備,有效率地來瀏覽網頁內容;且滿足不同使用者的偏好(Preference),這些就成為Internet的一個新議題。W3C近年提出了設備性能與偏好描述(Composite Capability/Preference Profiles, CC/PP)的標準,用以描述通訊時設備的性能與環境。透過這CC/PP的通訊協定,WWW使用者得以將通訊的配備、環境及個人偏好設定,傳送給網頁伺服器,網頁伺服器藉此得以挑選出適當的網頁內容傳回給瀏覽設備。在本論文中,我們架設一個能夠有效利用網路頻寬及使用者配備性能與偏好設定的Internet存取架構。本論文將網頁內容挑選的問題化成一個多重選擇背包問題,並利用動態規劃方法去挑選適合設備端瀏覽及網路頻寬的網頁內容,以減低網頁伺服器挑選網頁的運算處理時間,提供WWW資訊服務一個有效的解決方案。

In the recent year, Internet becomes very popular and everyone needs it to get the global information from the WWW. WWW client devices vary from low capacity wireless PDA to high performance desktop PC and networks rang from low speed modem links to high speed ATM backbones. This heterogeneity makes user to know the network constraints of different users. Composite Capabilities and Preference Profiles (CC/PP), proposed by W3C recently, is a standard of describing user agent’s capabilities and preferences, and in our early work, we designed a web content adaptation system, which can detect bandwidth dynamically and adapt various capabilities and preferences of clients based on CC/PP. In this thesis, we formulate the web content selection problem as a linear multi-choice knapsack problem (LMCKP). A dynamic programming is proposed to solve it. Then, the optimal solution of LMCKP is used to reduce the processing time of adaptive web server.

1 Introduction .............................................4
2 Related Works ............................................9
2.1 Content Negotiation ..................................9
2.1.1 Composite Capability and Preference Profile ......9
2.2 Bandwidth Measuring Algorithms ......................14
2.2.1 Packet Pair Algorithm ...........................14
2.2.2 Pathchar Algorithm ..............................16
3 Analysis of Adaptive Web System .........................18
3.1 Bandwidth Measuring .................................20
3.2 Processing Time for Content Adaptation ..............20
3.3 Solving Linear Multi-Choice Knapsack Problem ........22
3.3.1 The Transformation ..............................22
3.3.2 Dynamic Programming .............................24
3.4 Numerical Example ...................................25
3.5 Numerical Results ...................................40
4 Conclusion ..............................................42

[1] C. C. Hung, and L. Y. Hong, "Bandwidth Sensitive Content Transformation in Pervasive Computing", In Pro. ISCC 2000, IEEE Computers and Communications, pp. 14 -19.
[2] H. Ohto and J. Hjelm, "CC/PP exchange protocol based on HTTP Extension Framework", W3C note, 24 June 1999.
[3] WAP Forum, "WAP Binary XML Content Format Specification Version 1.2", 4 Nov. 1999.
[4] W3C, [Online]. Available: http://www.w3c.org/.
[5] S. Adler, A. Berglund, J. Caruso, S. Deach, P. Grosso, E. Gutentag, A. Milowski, J. Richman, and S. Zilles, "Extensible Stylesheet Language (XSL) Version 1.0", W3C Candidate Recommendation, 21 Nov. 2000.
[6] H. Nielson, P. Leach, and S. Lawrence, "An HTTP Extension Framework", RFC-2774, Feb 2000.
[7] K. Lai, and M. Baker, "Measuring Bandwidth, "In Proc. INFOCOM '99. IEEE Computer and Communications Societies, vol. 1, pp. 235 -245, 1999.
[8] WAP Forum, [Online]. Available: http://www.wapforum.org/.
[9] "WAG User Agent Profile Specification", 10 Nov. 1999.
[10] W3C, "Document Object Model (DOM) Activity Statement, " [Online]. Available: http://www.w3.org/DOM/Activity.
[11] W3C, "The Resource Description Framework", [Online]. Available: http://www.w3.org/RDF/.
[12] E. Zemel, "The linear multiple choice knapsack problem", Operations Research, vol 28, pp. 1412-1423, Nov. 1980.
[13] V. Cardellini, P. S. Yu, and Y. W. Huang, "Collaborative Proxy System for Distributed Web Content Trascoding", In Proc. 9th Int'l ACM Conf. on Information and Knowledge Management, pp. 520-527, Nov. 2000.
[14] R. Han, V. Perret, and M. Naghshineh, "WebSplitter: A Unified XML Framework for Multi-Device Collaborative Web Browsing", ACM Conference on Computer Supported Cooperative Work (CSCW) 2000, Dec. 2000.
[15] W. H. Chiang, "Internet Content Adaptation for Universal Access", Computer and Information Science College of Electrical Engineering and Computer Science National Chiao Tung
University, pp. 43-45, Dec. 2001.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
1. 42. 李桂秋,「環境污染防治對策之介紹」,逢甲合經系刊,第26期民國83年6月,第95~99頁,1994。
2. 23. 曾平毅,「道路衝擊費之介紹-兼論道路交通衝擊之管」理,都市交通期刊,第70期,民國八十二年六月,第10~17頁,1993。
3. 4. 郭宗孟,「探討國內道路工程工期冗長原因及解決對策」,現代營建,第22卷第9期,民國九十年九月,第49~53頁,2001。
4. 34. 張有恆、施宗佑,「不同道路系統小客車行車耗油模式之研究」,能源季刊,第21卷第1期,民國八十年一月,第21~40頁,1991。
5. 20. 林慧敏,「社會成本問題之研究」,大同商專學報,第6期,民國八十二年一月,第81~117頁,1993。
6. 16. 林俊錄,「加拿大環境污染防治制策略探討」(The Study on the Strategies of Environmental Pollution Control in Canada),永續發展期刊,第10期,民國八十五年三月,第33~37頁,1996。
7. 14. 余文德、劉福勳、李文義、葉珮娟,「營造廠空氣污染防治措施自主檢查之探討」(下),營造天下,第57期,民國八十九年九月,第34~38頁,2000。
8. 2. 余文德、范振成,「公共工程業主最有利排程之探討」,營建管理季刊,第46期,第50~59頁,2001。
9. 15. 張則堯,「環境污染者付費之要諦-外部成本的內部化、亦即社會責任的公平負擔」,保險專刊,第36期,民國八十三年六月,第201~203頁,1994。
10. 13. 余文德、劉福勳、李文義、葉珮娟,「營造廠空氣污染防治措施自主檢查之探討」(上),營造天下,第56期,民國八十九年八月,第23~28頁,2000。
11. 1. 郭斯傑、戴弘燁,「北二高工程合約變更案例之探討研究」,土木水利,第二十五卷,第一期,民國八十七年五月,第79~101頁,1998。
12. 20. 張清亮、陳文欽、蔡志弘,CE 認證之產品風險分析─以一般醫療器材為例,機械工業,第191期,第154-162頁(1999)。
13. 15. 曹健齡、楊義明,失效模式與效應分析的作業方式,品質管制月刊,第三十三卷,第4期,第55-59頁(1997)。
14. 13. 郭榮沛,失效模式與效應分析及應用案例研討,機械工業,第142期,第137-148頁(1995)。
15. 9. 周錫英、張起明,實施失效模式、效應與關鍵性分析之功能、需求與步驟,品質管制月刊,第三十卷,第12期,第75-83頁(1994)。