1. NCCU Academic Hub
  2. Publications
  3. College of Informatics
  4. Theses
  5. Item

Publications-Theses

Article View/Open

Publication Export

Google ScholarTM

NCCU Library

Citation Infomation

Related Publications in TAIR

題名 對於環境監管規則之時間感知衝突偵測方法
Temporal-aware conflict detection method for environmental regulation
作者 侯宇澤
Hou, Yu Tse
貢獻者 郭耀煌<br>廖峻鋒
Kuo, Yau Hwang<br>Liao, Chun Feng
侯宇澤
Hou, Yu Tse
關鍵詞 衝突偵測
時間感知
智慧環境
Conflict detection
Temporal-aware
Smart environments
日期 2017
上傳時間 31-Jul-2017 11:13:00 (UTC+8)
摘要 此篇論文中提出了一個新的環境監管規則衝突偵測方法，其運用於偵測智慧環境中使用者所制定的各種服務（在此稱為「規則」）。不同於傳統的偵測方法，此篇論文考量時間的因素，使具有時間感知的規則也能夠進行偵測。當考慮到時間的關係，這可能會使得原本衝突的規則變成有機會發生衝突或是不發生衝突，而且這也將會影響到整個系統的運作。我們基於特徵交互作用將衝突類型分成矛盾以及循環兩種，並且將時間因素也考慮到衝突類型當中，再針對這兩種衝突分別進行偵測。在矛盾這類型的衝突中，此篇論文利用時間邏輯的歸結原理來找出矛盾的規則；在循環這類型的衝突中，此篇論文將規則轉換成圖，然後再利用深度優先搜索找出圖中的返回邊，若是有返回邊存在也就能說明圖中存在著循環。此方法主要有兩個優點，第一個是在不考慮時間因素的傳統規則中，能夠有效的偵測出衝突。第二個是考慮時間因素的時間感知規則中，也能夠有效的偵測出衝突。在我們的實驗中，除了在模擬的規則資料庫中進行偵測外，我們也針對在實際的農業養殖場域中所使用的規則資料庫進行偵測。我們所提出的方法成功的偵測出智慧環境中使用者所制定的服務。
A novel temporal-aware conflict detection method for environmental regulation which is used to detect the various services (referred to as “rules”) prescribed by users in a smart environment is proposed in this thesis. This method is different from the traditional detection methods. This thesis considers the temporal-aware so that temporal rules can be detected. When we take the temporal relationship into account, it is possible that the conflicting rules are turned into opportunistic conflicting rules or non-conflicting rules, and it also affects the operation of the entire system. We divide the conflict type into contradiction and cycle based on the feature interaction and take the temporal relationship into account, and then detect these two kinds of conflict types. In the conflict type of contradiction, this thesis uses the temporal resolution to detection conflicting rules. In the conflict type of cycle, this thesis transforms the rules into graphs, and then detect the cycles through the depth-first search (DFS) to find back edges. This method has two main advantages, the first one is that the conflict can be detected among the traditional rules which do not consider the temporal. The second is that the conflict can be effectively detected among the temporal rules. In our experiments, in addition to detecting in simulated rule databases, we also detect the rule databases used in the real greenhouse. The method we proposed successfully detect the services prescribed by the users in the intelligent environment.
參考文獻 Barringer, H., Fisher, M., Gabbay, D., Gough, G., & Owens, R. (1990). METATEM: A framework for programming in temporal logic. In Stepwise Refinement of Distributed Systems Models, Formalisms, Correctness (pp. 94-129). Springer Berlin/Heidelberg.
Degiovanni, R., Ricci, N., Alrajeh, D., Castro, P., & Aguirre, N. (2016, August). Goal-conflict detection based on temporal satisfiability checking. In Proceedings of the 31st IEEE/ACM International Conference on Automated Software Engineering (pp. 507-518). ACM.
Dongliang, L., Kanyu, Z., & Xiaojing, L. (2008, October). ECA rule-based IO agent framework for greenhouse control system. In Computational Intelligence and Design, 2008. ISCID`08. International Symposium on (Vol. 1, pp. 482-485). IEEE.
Fisher, M. (1991, August). A Resolution Method for Temporal Logic. In IJCAI(Vol. 91, pp. 99-104).
Fisher, M. (1997). A normal form for temporal logics and its applications in theorem-proving and execution. Journal of Logic and Computation, 7(4), 429-456.
Harada, D., Fujiwara, H., & Ohta, T. (2006, October). Avoidance of feature interactions at run-time. In Software Engineering Advances, International Conference on (pp. 6-6). IEEE.
Huang, J., & Cakmak, M. (2015, September). Supporting mental model accuracy in trigger-action programming. In Proceedings of the 2015 ACM International Joint Conference on Pervasive and Ubiquitous Computing (pp. 215-225). ACM.
Kolberg, M., Magill, E. H., & Wilson, M. (2003). Compatibility issues between services supporting networked appliances. Communications Magazine, IEEE,41(11), 136-147.
Leelaprute, P. (2007, October). Resolution of feature interactions in integrated services of home network system. In Communications, 2007. APCC 2007. Asia-Pacific Conference on (pp. 363-366). IEEE.
Leelaprute, P., Matsuo, T., Tsuchiya, T., & Kikuno, T. (2008, August). Detecting feature interactions in home appliance networks. In Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing, 2008. SNPD`08. Ninth ACIS International Conference on (pp. 895-903). IEEE.
Luo, H., Wang, R., & Li, X. (2013, December). A rule verification and resolution framework in smart building system. In Parallel and Distributed Systems (ICPADS), 2013 International Conference on (pp. 438-439). IEEE.
Ma, M., Preum, S. M., Tarneberg, W., Ahmed, M., Ruiters, M., & Stankovic, J. (2016, May). Detection of runtime conflicts among services in smart cities. In Smart Computing (SMARTCOMP), 2016 IEEE International Conference on (pp. 1-10). IEEE.
Qiu, T., Xiao, H., & Zhou, P. (2013, August). Framework and case studies of intelligence monitoring platform in facility agriculture ecosystem. In Agro-Geoinformatics (Agro-Geoinformatics), 2013 Second International Conference on (pp. 522-525). IEEE.
Ren, Y., Luo, H., & Liu, L. (2014, August). A Dimension Model for Conflict-Free Service Management in Smart Environment Control System. In Intelligent Information Hiding and Multimedia Signal Processing (IIH-MSP), 2014 Tenth International Conference on (pp. 757-761). IEEE.
Schöning, U. (2008). Logic for computer scientists (Vol. 8). Springer Science & Business Media.
Sun, Y., Wang, X., Luo, H., & Li, X. (2015). Conflict Detection Scheme Based on Formal Rule Model for Smart Building Systems. Human-Machine Systems, IEEE Transactions on, 45(2), 215-227.
Sun, Y., Wu, T. Y., Li, X., & Guizani, M. (2016). A Rule Verification System for Smart Buildings. IEEE Transactions on Emerging Topics in Computing.
Tarjan, Robert. "Depth-first search and linear graph algorithms." SIAM journal on computing 1.2 (1972): 146-160.
Ur, B., McManus, E., Pak Yong Ho, M., & Littman, M. L. (2014, April). Practical trigger-action programming in the smart home. In Proceedings of the SIGCHI Conference on Human Factors in Computing Systems (pp. 803-812). ACM.
Wang, X., Sun, Y., & Luo, H. (2014, August). Service Conflict Detection and Avoidance Based on Scene with Urgency Degree. In Intelligent Information Hiding and Multimedia Signal Processing (IIH-MSP), 2014 Tenth International Conference on (pp. 753-756). IEEE.
描述 碩士
國立政治大學
資訊科學學系
103753039
資料來源 http://thesis.lib.nccu.edu.tw/record/#G0103753039
資料類型 thesis
dc.contributor.advisor 郭耀煌<br>廖峻鋒zh_TW
dc.contributor.advisor Kuo, Yau Hwang<br>Liao, Chun Fengen_US
dc.contributor.author (Authors) 侯宇澤zh_TW
dc.contributor.author (Authors) Hou, Yu Tseen_US
dc.creator (作者) 侯宇澤zh_TW
dc.creator (作者) Hou, Yu Tseen_US
dc.date (日期) 2017en_US
dc.date.accessioned 31-Jul-2017 11:13:00 (UTC+8)-
dc.date.available 31-Jul-2017 11:13:00 (UTC+8)-
dc.date.issued (上傳時間) 31-Jul-2017 11:13:00 (UTC+8)-
dc.identifier (Other Identifiers) G0103753039en_US
dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/111504-
dc.description (描述) 碩士zh_TW
dc.description (描述) 國立政治大學zh_TW
dc.description (描述) 資訊科學學系zh_TW
dc.description (描述) 103753039zh_TW
dc.description.abstract (摘要) 此篇論文中提出了一個新的環境監管規則衝突偵測方法，其運用於偵測智慧環境中使用者所制定的各種服務（在此稱為「規則」）。不同於傳統的偵測方法，此篇論文考量時間的因素，使具有時間感知的規則也能夠進行偵測。當考慮到時間的關係，這可能會使得原本衝突的規則變成有機會發生衝突或是不發生衝突，而且這也將會影響到整個系統的運作。我們基於特徵交互作用將衝突類型分成矛盾以及循環兩種，並且將時間因素也考慮到衝突類型當中，再針對這兩種衝突分別進行偵測。在矛盾這類型的衝突中，此篇論文利用時間邏輯的歸結原理來找出矛盾的規則；在循環這類型的衝突中，此篇論文將規則轉換成圖，然後再利用深度優先搜索找出圖中的返回邊，若是有返回邊存在也就能說明圖中存在著循環。此方法主要有兩個優點，第一個是在不考慮時間因素的傳統規則中，能夠有效的偵測出衝突。第二個是考慮時間因素的時間感知規則中，也能夠有效的偵測出衝突。在我們的實驗中，除了在模擬的規則資料庫中進行偵測外，我們也針對在實際的農業養殖場域中所使用的規則資料庫進行偵測。我們所提出的方法成功的偵測出智慧環境中使用者所制定的服務。zh_TW
dc.description.abstract (摘要) A novel temporal-aware conflict detection method for environmental regulation which is used to detect the various services (referred to as “rules”) prescribed by users in a smart environment is proposed in this thesis. This method is different from the traditional detection methods. This thesis considers the temporal-aware so that temporal rules can be detected. When we take the temporal relationship into account, it is possible that the conflicting rules are turned into opportunistic conflicting rules or non-conflicting rules, and it also affects the operation of the entire system. We divide the conflict type into contradiction and cycle based on the feature interaction and take the temporal relationship into account, and then detect these two kinds of conflict types. In the conflict type of contradiction, this thesis uses the temporal resolution to detection conflicting rules. In the conflict type of cycle, this thesis transforms the rules into graphs, and then detect the cycles through the depth-first search (DFS) to find back edges. This method has two main advantages, the first one is that the conflict can be detected among the traditional rules which do not consider the temporal. The second is that the conflict can be effectively detected among the temporal rules. In our experiments, in addition to detecting in simulated rule databases, we also detect the rule databases used in the real greenhouse. The method we proposed successfully detect the services prescribed by the users in the intelligent environment.en_US
dc.description.tableofcontents 1 Introduction 1
1.1 Motivation 1
1.2 Contributions 4
1.3 Organization 4
2 Backgrounds and Related Work 5
2.1 Rule Syntax 5
2.2 Conflict Types and Feature Interaction (FI) 7
2.3 Detection for Conflict 8
2.4 Solution for Conflict 9
2.5 Cognition for Rules 9
3 Approach 10
3.1 System Architecture 10
3.2 Conflict Detection 12
3.3 Temporal Rule Syntax 14
3.4 Conflict Types 16
3.4.1 Contradiction 16
3.4.2 Cycle 20
3.5 Temporal Logic (TL) Expression 23
3.6 Separated Normal Form (SNF) 26
3.7 Detection Methods 32
3.7.1 Detection for contradiction 32
3.7.2 Detection for cycle 36
3.8 Opportunistic Conflict 38
3.8.1 Opportunistic contradiction 38
3.8.2 Opportunistic cycle 40
4 Evaluation 41
4.1 Experiments 41
4.1.1 Real database 41
4.1.2 Experiment results and discussion 44
4.2 Simulation 49
4.2.1 Database without conflicting rule 49
4.2.2 Database with some conflicting rules 51
4.2.3 Database with temporal rules 52
4.3 Performance 57
5 Conclusion 60
References 62		zh_TW
dc.format.extent 1006696 bytes-
dc.format.mimetype application/pdf-
dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0103753039en_US
dc.subject (關鍵詞) 衝突偵測zh_TW
dc.subject (關鍵詞) 時間感知zh_TW
dc.subject (關鍵詞) 智慧環境zh_TW
dc.subject (關鍵詞) Conflict detectionen_US
dc.subject (關鍵詞) Temporal-awareen_US
dc.subject (關鍵詞) Smart environmentsen_US
dc.title (題名) 對於環境監管規則之時間感知衝突偵測方法zh_TW
dc.title (題名) Temporal-aware conflict detection method for environmental regulationen_US
dc.type (資料類型) thesisen_US
dc.relation.reference (參考文獻) Barringer, H., Fisher, M., Gabbay, D., Gough, G., & Owens, R. (1990). METATEM: A framework for programming in temporal logic. In Stepwise Refinement of Distributed Systems Models, Formalisms, Correctness (pp. 94-129). Springer Berlin/Heidelberg.
Degiovanni, R., Ricci, N., Alrajeh, D., Castro, P., & Aguirre, N. (2016, August). Goal-conflict detection based on temporal satisfiability checking. In Proceedings of the 31st IEEE/ACM International Conference on Automated Software Engineering (pp. 507-518). ACM.
Dongliang, L., Kanyu, Z., & Xiaojing, L. (2008, October). ECA rule-based IO agent framework for greenhouse control system. In Computational Intelligence and Design, 2008. ISCID`08. International Symposium on (Vol. 1, pp. 482-485). IEEE.
Fisher, M. (1991, August). A Resolution Method for Temporal Logic. In IJCAI(Vol. 91, pp. 99-104).
Fisher, M. (1997). A normal form for temporal logics and its applications in theorem-proving and execution. Journal of Logic and Computation, 7(4), 429-456.
Harada, D., Fujiwara, H., & Ohta, T. (2006, October). Avoidance of feature interactions at run-time. In Software Engineering Advances, International Conference on (pp. 6-6). IEEE.
Huang, J., & Cakmak, M. (2015, September). Supporting mental model accuracy in trigger-action programming. In Proceedings of the 2015 ACM International Joint Conference on Pervasive and Ubiquitous Computing (pp. 215-225). ACM.
Kolberg, M., Magill, E. H., & Wilson, M. (2003). Compatibility issues between services supporting networked appliances. Communications Magazine, IEEE,41(11), 136-147.
Leelaprute, P. (2007, October). Resolution of feature interactions in integrated services of home network system. In Communications, 2007. APCC 2007. Asia-Pacific Conference on (pp. 363-366). IEEE.
Leelaprute, P., Matsuo, T., Tsuchiya, T., & Kikuno, T. (2008, August). Detecting feature interactions in home appliance networks. In Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing, 2008. SNPD`08. Ninth ACIS International Conference on (pp. 895-903). IEEE.
Luo, H., Wang, R., & Li, X. (2013, December). A rule verification and resolution framework in smart building system. In Parallel and Distributed Systems (ICPADS), 2013 International Conference on (pp. 438-439). IEEE.
Ma, M., Preum, S. M., Tarneberg, W., Ahmed, M., Ruiters, M., & Stankovic, J. (2016, May). Detection of runtime conflicts among services in smart cities. In Smart Computing (SMARTCOMP), 2016 IEEE International Conference on (pp. 1-10). IEEE.
Qiu, T., Xiao, H., & Zhou, P. (2013, August). Framework and case studies of intelligence monitoring platform in facility agriculture ecosystem. In Agro-Geoinformatics (Agro-Geoinformatics), 2013 Second International Conference on (pp. 522-525). IEEE.
Ren, Y., Luo, H., & Liu, L. (2014, August). A Dimension Model for Conflict-Free Service Management in Smart Environment Control System. In Intelligent Information Hiding and Multimedia Signal Processing (IIH-MSP), 2014 Tenth International Conference on (pp. 757-761). IEEE.
Schöning, U. (2008). Logic for computer scientists (Vol. 8). Springer Science & Business Media.
Sun, Y., Wang, X., Luo, H., & Li, X. (2015). Conflict Detection Scheme Based on Formal Rule Model for Smart Building Systems. Human-Machine Systems, IEEE Transactions on, 45(2), 215-227.
Sun, Y., Wu, T. Y., Li, X., & Guizani, M. (2016). A Rule Verification System for Smart Buildings. IEEE Transactions on Emerging Topics in Computing.
Tarjan, Robert. "Depth-first search and linear graph algorithms." SIAM journal on computing 1.2 (1972): 146-160.
Ur, B., McManus, E., Pak Yong Ho, M., & Littman, M. L. (2014, April). Practical trigger-action programming in the smart home. In Proceedings of the SIGCHI Conference on Human Factors in Computing Systems (pp. 803-812). ACM.
Wang, X., Sun, Y., & Luo, H. (2014, August). Service Conflict Detection and Avoidance Based on Scene with Urgency Degree. In Intelligent Information Hiding and Multimedia Signal Processing (IIH-MSP), 2014 Tenth International Conference on (pp. 753-756). IEEE.		zh_TW