臺灣博碩士論文加值系統

本論文提出了一創新的方法來將行動環境下的使用者依照興趣群組分類，透過此方法可以延長興趣群組的存活時間與增加行動環境下使用者間的交流量。另外本論文發展了於興趣區間中的細胞自動機之興趣本體論機制來將行動環境下的使用者依照興趣群組分類，各個使用者的興趣依據著我們所設計的細胞自動機規則來加以分類群組。而根據提出的方法所做的實驗結果顯示，本方法能延長興趣群組的存活時間與增加行動環境下使用者間的交流量。
IEEE 802.16 WiMax是近年來備受矚目的無線網路傳輸機制，其中分為PMP(Point-to-multipoint)以及Mesh兩種模式。Mesh是FBWA(Fixed broadband wireless access)的系統，被視為下一代的無線都會網路的解決方案，採用的是TDMA排程方法，其中排程又分為集中式(centralized mode)以及分散式(distributed mode) ，集中式是由BS來掌控所有資源並且決定SS之間的傳輸排程。
本論文提出了一個在WiMax Mesh 內部的多播串流機制，透過二階段式的方法，建立有效率的multicast tree。第一階段先利用我們提出的Priority-Based Algorithm來建立 multicast sub-trees，第二階段再利用Interference-Aware Steiner Tree的方法，建立Source node到所有 multicast sub-trees的串流路徑。實驗結果顯示，我們提出的兩階段式建樹方法，不管是在 multicast sub-tree的建立上面，還是減少multicast tree對整體網路interference 影響上面，都能夠有很大的提升。

推薦系統在日常生活中處處可見，諸如電子商務、線上購物、數位學習等等。推薦系統不僅提供身處在資訊爆炸時代的我們在選擇事物參考指標，也提升了在大量資料裡搜尋相關資訊的能力。近年來，推薦系統的發展已引起各領域學者的興趣與關注，在各種不同領域的大量數位內容中取得對貼近所求，也是多數研究鑽研的目標。
本論文之目的在於提出一套適用於各種領域的個人化推薦機制，結合本體論的技術可使得應用領域更有彈性。
從使用者過去對某些項目的評分，系統可分析出使用者的喜好，而透過不同領域定義好的語意，系統可以推論出在這眾多資料中還有哪些是使用者也會有興趣的項目。因此在本研究中，除了找出相關項目的推薦機制是研究重點之外，對使用者的喜好分析也是探索的目標之一。從使用者過去對選擇項目的評分，推論出使用者對於某些分類的關注值與喜好值，進而產生出推薦名單以供使用者做決策參考。
本論文主要採用的方式是以使用者過去評分記錄為分析對象，分析得之使用者對該領域的各分類關切度，並以基於知識系統的推薦技術為基準，透過本體論定義的屬性序列尋找相關項目，並在尋得項目時以使用者關切度計算出對該項目的喜好度。而在個人化模組訓練方面則是採用基因演算法使得架構模式具有學習能力，在訓練的過程中試圖找出最符合該使用者的參數值，藉以達到個人化的最終結果。

This thesis proposes a novel approach to clustering the interests of mobile users, increasing the lifetime of interest groups, and increasing the throughput in mobile user-to-mobile user (M2M) environments for mobile IPTV (MOTV) societies. This thesis develops an interest ontology of cellular automata (CA) clustering using the zone of interest (ZOI) for mobicast communications in mobile ad hoc network (MANET) environments. The key to the proposed method is to integrate CA clustering with the ontology of users’ interests. This thesis proposes that both an interest profile (ontology) of users and information about mobile devices can help form a group of MANET-related interests. The current study evaluates the performance of the approach by conducting computer simulations. Simulation results reveal the strengths of the proposed CA-clustering algorithm in terms of increased group lifetime and increased ZOI throughput for MANETs.
IEEE 802.16 WiMAX is a rapidly developing technology for broadband wireless access systems. The IEEE 802.16 MAC layer defines two operational modes, point-to-multipoint (PMP) mode and mesh mode. In the centralized protocol, all resources are controlled by base station (BS). In this thesis, we propose a novel two-stage scheme for constructing an effective multicast tree. The first stage applies a significance-based algorithm to find suitable multicast points and construct effective multicast sub-trees. The second stage applies an interference-aware Steiner tree to connect the source to each multicast sub-tree. Finally, an algorithm generates the final multicast tree topology. Simulation results reveal that the proposed approach outperforms others in the construction of a multicast tree and significantly reduces the interference of a mesh network.
Recommender systems provide strategies that help users search or make decisions within the overwhelming information spaces nowadays. They have played an important role in various areas such as e-commerce and e-learning. In this thesis, we propose a hybrid recommendation strategy of content-based and knowledge-based methods that are flexible for any field to apply. By analyzing the past rating records of every user, the system learns the user’s preferences. After acquiring users’ preferences, the semantic search-and-discovery procedure takes place starting from a highly rated item. For every found item, the system evaluates the Interest Intensity indicating to what degree the user might like it. Recommender systems train a personalized estimating module using a genetic algorithm for each user, and the personalized estimating model helps improve the precision of the estimated scores. With the recommendation strategies and personalization strategies, users may have better recommendations that are closer to their preferences. In the latter part of this thesis, a real-world case, a movie-recommender system adopting proposed recommendation strategies, is implemented.

Table of Contents
摘 要 I
Abstract III
List of Tables ii
List of Figures iii
List of Figures iv
Chapter 1. Introduction 1
Chapter 2. Background and Related Work 8
2.1. An MOTV Society in Mobile Ad-hoc Networks 8
2.2. A Multicast Mechanism for Intra WiMAX Mesh Network 12
2.3. The Adaptive Ontology-based Personalized Recommender System 14
Chapter 3. Using Cellular Automata to Form an MOTV Society in Mobile Ad-hoc Networks 20
3.1. System Model 20
3.2. Performance Evaluation 33
Chapter 4. A Multicast Mechanism Using Significance- Based and Interference-Aware Algorithm for Intra WiMAX Mesh Network 38
4.1. Proposed Scheme 38
4.2. Performance Analysis 48
4.3. Simulation Results 51
Chapter 5. The Adaptive Ontology-based Personalized Recommender System 54
5.1. Adaptive Ontology-Based Personalized Recommender System 54
5.2. Implementation of The Movie AOPRS 67
Chapter 6. Conclusions 85
References 87

List of Tables
Table 1: Recommendation Techniques 17
Table 2: Simulation parameters and range of values 33
Table 3: The user ratings as a transaction table 58
Table 4: The 2x2 contingency table for X--〉Y 58
Table 5: An example of a fragmented rating record 72
Table 6: An example of fragmented genre records 73
Table 7: Example of 2*2 contingency tables 73
Table 8: The GA controlling parameters in the Movie AOPRS 76
Table 9: The Enhancement of weighting vector training using GA 80
Table 10: Relationship between selected items and expected items 81



List of Figures
Figure 1: Channel zapping time 2
Figure 2: (a) Cellular like PMP mode; (b) Mesh mode. 4
Figure 3: Control tree rooted in BS. 5
Figure 4: Rules for the game of life 10
Figure 5: Cultural Portal Information in RDF 17
Figure 6: An interest-ontology service scenario 22
Figure 7: System structure diagram 22
Figure 8: The interest-item reordering. 24
Figure 9: Interest ontology for an MOTV society 25
Figure 10: IEEE802.11p channel distribution [44] 27
Figure 11: Multi-channel multi-group interest 28
Figure 12: Operations of mobicasting for ZOIs: (a) ZOI(t); (b) ZOI(t+1) 32
Figure 13: Network lifetime. 34
Figure 14: Average packet loss 35
Figure 15: Updated group-head cost rate 35
Figure 16: Dissemination success rate for communication range 36
Figure 17: The probability of collision relative to the number of mobile users 37
Figure 18: Build tree process 40
Figure 19: (a) B as multicast node; (b) node A and C as multicast node 41
Figure 20: Example of Significance-based algorithm 43
List of Figures
Figure 21: Interference-aware value 47
Figure 22: The decision of minimize multicast node model 50
Figure 23: Number of subtrees 52
Figure 24: Total interference of Steiner tree 52
Figure 25: Number of nodes in multicast tree. 53
Figure 26: The AOPRS Architecture 54
Figure 27: An example using SPARQL 61
Figure 28: The search-and-discovery process 62
Figure 29: Process of personalized weighting vector training using GA 66
Figure 30: The system architecture of the Movie AOPRS 68
Figure 31: The data-cleaning process 69
Figure 32: Part of the MMO classes and properties view 71
Figure 33: The mapping between MMO and user ratings. 72
Figure 34: An example of semantic search and discovery. 75
Figure 35: The fitness values average over all permutations 77
Figure 36: The RMSE predictive-accuracy metrics with and without GA training 80
Figure 37: Impact on recall from different cutoffs in randomly selected users 82
Figure 38: Impact on precision from different cutoffs in randomly selected users 82
Figure 39: The ROC curve of the Movie AOPRS. 84

References
[1]Thompson G. and Chen Y.-F. R., “IPTV: Reinventing television in the Internet age, IEEE Internet Comput., vol. 13, no. 3, pp. 11–14, May/Jun. 2009.
[2]Sharpe R., Heiles J., Liu H., Deschanel M., Wu Y., Maisonneuve J., and Li W., “An overview of IPTV standards development, IEEE Trans. Broadcast., vol. 55, no. 2, pp. 315–328, Jun. 2009.
[3]Kim J., Hahm J. H., Kim Y. S., and Choi J. K., “NGN architecture for IPTV service without effect on conversational services, in International Conference on Advanced Communication Technology, Feb. 2006, vol. 1, pp. 465–469.
[4]Park W., Choi C., Kim D., Jeong Y., and Park K., “IPTV-aware multiservice home gateway based on FTTH access network, in International Symposium on Consumer Electronics, Jun. 2005, pp. 285–290.
[5]Tekla S., “The trial and travails of interactive TV, IEEE Spectrum, no. 4, pp. 22–28, 1996.
[6]Shirazi Hamidreza, Cosmas John, and Cutts David, “A Cooperative Cellular and Broadcast Conditional Access System for Pay-TV Systems, IEEE Trans. On Broadcasting, Vol. 56, No. 1, pp. 44–57, 2010.
[7]Agilent Technologies, “Ensure IPTV Quality of Experience, White Paper, 2005.
[8]Begen A. C., Glazebrook N., and Steeg W. Ver, “A unified approach for repairing packet loss and accelerating channel changes in multicast IPTV, in IEEE Consum. Commun. Netw. Conf., 2009.
[9]Zhu Y., Liu W., Dong L., Zeng W., and Yu H., “High performance adaptive video services based on bitstream switching for IPTV systems, in IEEE Consum. Commun. Netw. Conf., 2009.
[10]Joo H., Song H., Lee D. B., and Lee I., “An effective IPTV channel control algorithm considering channel zapping time and network utilization, IEEE Trans. Broadcast., vol. 54, no. 2, 2008.
[11]Cho C., Han I., Jun Y., and Lee H., “Improvement of channel zapping time in IPTV services using the adjacent groups join-leave method, in 6th Int. Conf. Adv. Commun. Technol., 2004, pp. 971–975.
[12]Chen Harry, Finin Tim, Joshi Anupam, Kagal Lalana, Perich Filip, Chakraborty Dipanjan, “Intelligent Agents Meet the Semantic Web in Smart Spaces, IEEE Internet Computing, vol. 8, no. 6, pp. 69–79, Nov./Dec. 2004.
[13]Protégé Home Page, http://protege.stanford.edu/.
[14]Liu Yan, “Modelling Urban Development with Grographical Information Systems and Cellular Automata, 2009, CRC press, Taylar ＆ Francis Group.
[15]Wolfram, S., “Cellular automata as models of complexity, 1984, Nature. v.311, pp.419-424
[16]Missoum S., Gürdal Z., Setoodeh S., “Study of a new local update scheme for cellular automata in structural design, Structural and Multidisciplinary Optimization, Vol. 29, No. 2, 2005, DOI: 10.1007/s00158-004-0464-2.
[17]Mamei M., Roli A., Zambonelli F., “Emergence and control of macro-spatial structures in perturbed cellular automata, and implications for pervasive computing systems, IEEE Trans. on Systems, Man and Cybernetics, Part A: Systems and Humanps, 2005, Vol. 35, Issue: 3, pp. 337–348.
[18]Gardner, The fantastic combinations of John Conway’s new solitaire game Life, 1972, Scientific American v233,pp.120-123
[19]Etoh M., Yoshimura T., “Wireless Video Applications in 3G and Beyond, IEEE Wireless Comm., vol. 12, no. 4, pp. 66–72, Aug. 2005.
[20]Fitzek F., Reisslein M., “A Prefetching Protocol for Continuous Media Streaming in Wireless Environments, IEEE J. Selected Areas in Comm., vol. 19, no. 10, pp. 2015–2028, Oct. 2001.
[21]Kyriakidou A., Karelos N., and Delis A., “Video-streaming for Fast Moving Users in 3G Mobile Networks, Proc. Fourth ACM Int’l Workshop Data Eng. for Wireless and Mobile Access, pp. 65–72, 2005.
[22]Xue G.-t., Jia Z. qing, You J. Y., and Li M. lu, “Group Mobility Model in Mobile Peer-to-peer Media Streaming System, Proc. 2004 IEEE Int’l Conf. Services Computing, pp. 527–530, Sept. 2004.
[23]Jenkac H., Stockhammer T., Xu W., “Asynchronous and Reliable On-demand Media Broadcast, IEEE Network, vol. 20, no. 2, pp. 14–20, Mar./Apr. 2006.
[24]Leung M.-F., Chan S.-H. G., “Broadcast-based Peer-to-peer Collaborative Video Streaming among Mobiles, IEEE Trans. Broadcasting, vol. 53, no. 1, pp. 350–361, Mar. 2007.
[25]Woo S., Singh S., “Scalable routing protocol for ad hoc networks, in Wireless Networks, vol. 7. Norwell, MA: Kluwer, 2001, pp. 513–529.
[26]Liu D., Stojmenovic I., Jia X., “A scalable quorum-based location service in ad hoc and sensor networks, in Proc. IEEE MASS, 2006, pp. 489–492.
[27]Gerla, M., On-demand multicast routing protocol (ODMRP) for ad hoc networks, Internet Draft, 2000.
[28]Shen, C.-C. and C. Jaikaeo, Ad hoc multicast routing algorithm with swarm intelligence, Mob. Netw. Appl., 2005. 10(1-2): pp. 47-59.
[29]Penttinen, A. Minimum cost multicast trees in ad hoc network, IEEE ICC, International Conference, 2006.
[30]Ruiz, P.M. and A.F. Gomez-Skarmeta, Approximating optimal multicast trees in wireless multihop networks, 10th IEEE Symposium on Computers and Communications, ISCC, 2005.
[31]L. Kou1, G.M.a.L.B., A fast algorithm for Steiner trees, Acta Informatica, Received: 14, 1979.
[32]Hung-Yu, W., et al., Interference-aware IEEE 802.16 WiMAX mesh networks, IEEE 61st. Vehicular Technology Conference, VTC Spring, 2005.
[33]Kuran, M.S., et al., Cross-layer routing-scheduling in IEEE 802.16 mesh networks, ICST 1st international conference on MOBILe Wireless MiddleWARE, Operating Systems, and Applications, 2007.
[34]Fei, X., K.A. Hua, and J. Ning., Achieving True Video-on-Demand Service in Multi-Hop WiMAX Mesh Networks, 32nd IEEE Conference on Local Computer Networks, LCN 2007.
[35]Jianfeng, C., et al., A Multicast Mechanism in WiMAX Mesh Network, Asia-Pacific Conference on Communications (APCC), 2006.
[36]Robin Burke, “Hybrid recommender systems: survey and experiments, User Modeling and User-Adapted Interaction, 2002, pp. 331-370.
[37]The Semantic Web, http://semanticweb.org/wiki/Main_Page
[38]K. Anyanwu, A. Sheth, “ρ-Queries: enabling querying for semantic associations on semantic web, in: Proceedings of the 13th International World Wide Web Conference, 2003, pp. 117-127.
[39]OWL Web Ontology Language, http://www.w3.org/TR/owl-features/
[40]Y. Blanco-Fernandez et al., “A flexible semantic inference methodology to reason about user preferences in knowledge-based recommender systems, in Knowledge-Based Systems, 2008, pp. 305-320.
[41]Zang Y.P., Stibor L., Walke B., Reumerman H. J, Barroso A., “Towards Broadband Vehicular Ad-hoc networks: The Vehicular Mesh Network (VMESH) MAC Protocol, in Proc. IEEE WCNC’07, pp. 417–422, March 11-15, 2007.
[42]Committee SCC32, IEEE P1609.4 Standard for Wireless Access in Vehicular Environments (WAVE): Multi-channel Operation, draft standard, IEEE Intelligent Transportation Systems Council, 2006.
[43]Task Group p, IEEE P802.11p: Wireless Access in Vehicular Environments (WAVE), draft standard ed., IEEE Computer Society, 2006.
[44]Bi Yuanguo, Liu Kuang-Hao, Shen Xuemin, Zhao Hai, “A Multi-channel Token Ring Protocol for Inter-Vehicle Communications, IEEE Global Telecommunications Conference, 2008, pp.1–5.
[45]FCC Report and Order: FCC-03-324, Feb. 2004, URL: http: //hraunfoss.fcc.gov/edocs public/attachmatch/FCC-03-324A1.pdf
[46]Younis O., Fahmy S., “HEED: A hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks, IEEE Trans. Mobile Computing, vol. 3, no. 4, pp. 366–379, Oct.–Dec. 2004.
[47]Alessandro Santuari, “Steiner Tree NP-completeness Proof, 2003.
[48]IMDb, the Internet Movie Database. http:// www.imdb.com/
[49]SPARQL Query Language for RDF http://www.w3.org/TR/rdf-sparql-query/
[50]B. Aleman-Meza, C. Halaschek-Wiener, I.B. Arpinar, C. Ramakrishnan, and A. Sheth, Ranking Complex Relationships on the Semantic Web, IEEE Internet Computing, vol. 9, issue 3, May/June, 2005.
[51]P. Ganesan, H. Garcia-Molina, J. Widom, Exploiting hierarchical domain structure to compute similarity, ACM Transactions on Information Systems 2003, pp. 64-93.
[52]J. L. Herlocker, J. A. Konstan, L. G. Terveen, and J. T. Riedl, “Evaluating Collaborative Filtering Recommender Systems, ACM Transactions on Information Systems, Vol. 22, No. 1, January 2004, pp. 5-53.
[53]Jena – A Semantic Web Framework for Java, http://jena.sourceforge.net/
[54]I. Cantador, A. Bellogín and P. Castells, “A multilayer ontology-based hybrid recommendation model, AI Communications 21 (2008), pp. 203-210.
[55]J. Ben Schafer1 Contact Information, Joseph A., “Konstan Contact Information and John Riedl, E-Commerce Recommendation Applications, Data Mining and Knowledge Discovery 2010, pp.115-153
[56]Sarwar, B. M., Konstan, J. A., Borchers, A., Herlocker, J., Miller, B. and Riedl, J., “Using Filtering Agents to Improve Prediction Quality in the GroupLens Research Collaborative Filtering System, Computer Supported Cooperative Work, 1998.
[57]Cheng Sheng-Tzong, Horng Gwo-Jiun, Chou Chih-Lun, “Using cellular automata to form car society in vehicular ad hoc network, IEEE Trans. Intell. Transp. Syst., , Vol. 12, No. 4, 2011, pp. 1374 - 1384.
[58]Lee Chae Young, Hong Chang Ki, and Lee Kang Yong, “Reducing Channel Zapping Time in IPTV Based on User’s Channel Selection Behaviors, IEEE Trans. Broadcast., Vol. 56, No. 3, pp. 321–330,2010.
[59]Wu Shiow-yang, and He Cheng-en, “QoS-aware Dynamic Adaptation for Cooperative Media Streaming in Mobile Environments, IEEE Trans. Parallel and Distributed Systems, Vol. 22, No. 3, pp. 439–450, 2011.
[60]Zhang, Y., H. Hu, and H.-H. Chen, QoS differentiation for IEEE 802.16 WiMAX mesh networking, Mob. Netw. Appl., 13(1-2): pp. 19-37, 2008.
[61]Lim, A.O., et al., A hybrid centralized routing protocol for 802.11s WMNs, Mob.Netw. Appl., 13(1-2): pp. 117-131, 2008.
[62]Nahle, S., N. Malouch, and S. Fdida., Dimensioning WiMAX Mesh Networks with Multiple Channels, IEEE INFOCOM Workshops, 2009.
[63]Peng-Yong, K., et al., A Routing Protocol for WiMAX Based Maritime Wireless Mesh Networks, IEEE 69th.Vehicular Technology Conference, VTC Spring, 2009.
[64]Michael R. Garey and David S. Johnson, “Computers and Intractabil-ity: A Guide to the Theory of NP-Completeness, W.H. Freeman and Company, 1979.
[65]J. Konstan, B. Miller, D. Maltz, J. Herlocker, L. Gordon, J. Riedl, “GroupLens: applying collaborative filtering to usenet news, Communications.
[66]SWETS, J. A. 1963. “Information retrieval systems, Science 141, pp. 245-250.
[67]SWETS, J. A. 1969. “Effectiveness of information retrieval methods, Amer. Doc. 20, pp. 72-89.
[68]Protégé a free, open source ontology editor and knowledge-based framework, was developed by the Stanford Center for Biomedical Informatics Research at the Stanford University School of Medicine. http://protege.stanford.edu
[69]Sarwar, B. M., Karypis, G., Konstan, J. A., and Riedl, J. 2001. “Item-based collaborative filtering recommendation algorithms, In Proceedings of the 10th International World Wide Web Conference (WWW10).
[70]Balabanovic, M. and Shoham, Y., “Fab: Content-based, Collaborative Recommendation, Communications of the ACM, Vol. 40, No. 3, March 1997, pp. 66-72.
[71]Thomas R. Gruber, “Toward Principles for the Design of Ontologies Used for Knowledge Sharing, International Workshop on Formal Ontology, March, 1993, Padova, Italy.
[72]Breese, J. S., Heckerman, D. and Kadie, C., “Empirical Analysis of Predictive Algorithms for Collaborative Filtering, Proceedings of the Fourteenth Annual Conference on Uncertainty in Artificial Intelligence (UAI-98), 1998, pp. 43-52.
[73]J. Tang, B.Y. Liang, J.Z. Li, “Toward Detecting Mapping Strategies for Ontology Interoperability, The Semantic Computing Initiative (SeC 2005).
[74]R. Burke., “Knowledge-based recommender systems, Encyclopedia of Library and Information Systems, 69(32), 2000.
[75]A. D. Ali, I. M. M. El Emary, and M. M. Abd El-Kareem, “Application of Genetic Algorithm in Solving Linear Equation Systems, MASAUM Journal of Basic and Applied Science, Vol.1, No.2 September 2009.