成功大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	廖盈琇 Liao, Ying-hsiu
論文名稱：	在具資源限制的普及網路環境中提出以服務品質驅動之裝置建構方法 A QoS-Driven Approach for Service-Oriented Device Arrangement in Resource-Constrained Ubiquitous Environments
指導教授：	郭耀煌 Kuo, Yau-hwang
學位類別：	碩士 Master
系所名稱：	電機資訊學院 - 資訊工程學系 Department of Computer Science and Information Engineering
論文出版年：	2007
畢業學年度：	95
語文別：	英文
論文頁數：	91
中文關鍵詞：	多維度與多選擇背包問題、普及服務、普及運算、裝置建構
外文關鍵詞：	Ubiquitous service, Multi-dimension Multi-choice Knapsack Problem, Ubiquitous computing, Device arrangement
相關次數：	點閱：105 下載：1
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

隨著科技的發展，利用普及運算技術實現『數位生活』已經不是夢想。在普及網路環境中，使用者可以在任何時間、地點要求各式各樣的普及服務。依據不同的需求，這些普及服務需藉由多個裝置之間的合作來完成。因此，如何在普及網路環境中替每一個被要求的普及服務找到一組符合使用者服務品質要求的裝置建構(即一組執行普及服務的裝置)就變得相當重要。然而，由於裝置資源與網路頻寬是共享的，而且裝置的特性(如穩定性、可得性等)會影響到服務執行時的品質，因此如何在具資源限制的普及網路環境中為所有被要求的普及服務找到品質最佳的裝置建構便成了一個相當困難的最佳化問題。我們將這個問題稱為『資源限制下的裝置建構問題』。
本篇論文中，我們首先透過數學模型來定義『資源限制下的裝置建構問題』。透過數學模型的轉換，我們將此問題轉化為『多維度與多選擇背包問題』。因此，現有用的『多維度與多選擇背包問題』演算法即可直接應用在我們的問題上。此外，我們還定義了服務品質功能函式用以量化不同的裝置建構所能提供的服務品質。根據對服務品質的不同喜好，使用者可以設定服務品質功能函式中各個服務品質參數的權重值。
為了達到裝置建構過程的自動化，我們設計了『服務導向裝置建構系統』。藉由此系統之『普及環境資料庫』及『普及環境資料庫管理子系統』來維護與管理普及服務與普及網路的最新狀態，此系統之『服務導向裝置建構子系統』即可應用『多維度與多選擇背包問題』的近似最佳演算法來有效地解決『資源限制下的裝置建構
問題』。
最後，透過系統複雜度與效能評估實驗分析，『服務導向裝置建構系統』的確可以有效地在具資源與頻寬的限制的普及網路環境中根據裝置的特性替所有被要求的普及服務選擇能夠滿足使用者服務品質要求之最佳裝置建構。

Digital life is no longer a future and is being realized via a lots of research results on ubiquitous computing. In ubiquitous environments, users can access ubiquitous services in an “anyone, anywhere, anytime”, manner. According to the service requirements, each ubiquitous service is carried out by the cooperation among a set of devices, called device composition. Thus, it becomes an important and complex problem to arrange resource-limited devices in bandwidth-limited ubiquitous networks for all requested ubiquitous services with optimized user-demanded service quality. This optimization problem is called Resource-constrained Device Composition Problem (RDCP).
In this thesis, we first formulate RDCP with mathematical models. In our work, RDCP has been reduced to Multi-dimension Multi-choice Knapsack Problem (MMKP) by transforming the model of RDCP into the model of MMKP. Thus, MMKP algorithms can be directly applied for solving RDCP. Moreover, we define a service quality utility function to quantify the quality of a device composition which depends on the user-defined QoS factors, such as reliability and availability, of each device in this device composition. Thus, users could set their preferences on service quality by configuring the weights of QoS factors in defined service quality utility function.
We also propose Service-Oriented Device Arrangement System (SODAS) to automate the service-oriented device arrangement process. In SODAS, Ubiquitous Environment Database (UEDB) is designed for preserving the statuses of ubiquitous services and ubiquitous networks; UEDB Manager (UEDM) is the interface to access UEDB; and Service-Oriented Device Composer (SODC) is the core subsystem to solve RDCP through MMKP algorithms.
Finally, the results of computational complex analysis and performance evaluation show that SODAS is capable of arranging resource-limited devices in bandwidth-limited networks for all requested ubiquitous services. Moreover, the various user-demanded service quality preferences are achieved according to the configured weights of QoS factors in defined service quality utility function.

Content
LIST OF TABLES ...................................................................... 11
LIST OF FIGURES ..................................................................... 12
CHAPTER 1 INTRODUCTION .............................................................. 13
1 BACKGROUND AND MOTIVATION ....................................................... 14
2 ISSUES IN DEVICE ARRANGEMENT .................................................... 17
3 CONTRIBUTIONS OF THIS PAPER ..................................................... 18
4 ORGANIZATION OF THIS PAPER ...................................................... 19
CHAPTER 2 RELATED WORK .............................................................. 20
1 DEVICE DISCOVERY APPROACHES ..................................................... 21
2 DEVICE COMPOSITION APPROACHES ................................................... 22
3 MULTI-DIMENSION MULTI-CHOICE KNAPSACK PROBLEM ................................... 23
3.1 Problem Definition of MMKP .................................................... 24
3.2 Optimal Algorithm of MMKP ..................................................... 25
3.3 Approximation Algorithms of MMKP .............................................. 26
CHAPTER 3 RESOURCE-CONSTRAINED DEVICE COMPOSITION PROBLEM: MODELING AND FORMULATION . 30
1 UBIQUITOUS SERVICE AND UBIQUITOUS NETWORK MODELING .............................. 31
1.1 Modeling of SP ................................................................ 32
1.2 Modeling of UN ................................................................ 34
1.3 Preliminary Discussion on Device Composition .................................. 35
1.4 Service Quality Utility Function............................................... 36
1.5 Policy of Resource and Bandwidth Allocation ................................... 38
2 RDCP FORMULATION ................................................................ 39
2.1 Problem Definition of RDCP .................................................... 39
2.2 Problem Reduction from RDCP to MMKP ........................................... 40
CHAPTER 4 SERVICE-ORIENTED DEVICE ARRANGEMENT SYSTEM ................................ 44
1 SODAS REQUIREMENTS AND ARCHITECTURE ............................................. 44
2 UBIQUITOUS ENVIRONMENT DATABASE (UEDB) .......................................... 46
2.1 Device Status Table (DST) ..................................................... 47
2.2 Supported System Service Table (SST) .......................................... 47
2.3 Link Status Table (LST) ....................................................... 48
2.4 Path Status Table (PST) ....................................................... 49
2.5 Supported Ubiquitous Service Template (SUT) ................................... 49
2.6 Requested Ubiquitous Service Table (RUT) ...................................... 51
3 UEDB MANAGER (UEDM) ............................................................. 53
3.1 Events for Ubiquitous Service Management ...................................... 54
3.2 Events for Ubiquitous Network Management ...................................... 55
4 SERVICE-ORIENTED DEVICE COMPOSER (SODC) ......................................... 55
4.1 Capable Device Composition Determination Phase ................................ 56
4.2 RDCP to MMKP Transformation Phase ............................................. 58
4.3 Device Composition Selection Phase ............................................ 60
4.4 Computational Complexity of SODC .............................................. 62
CHAPTER 5 SYSTEM PERFORMANCE EVALUATIONS ............................................ 66
1 CONFIGURATION OF EXPERIMENTAL ENVIRONMENTS....................................... 66
1.1 Configuration of Experimental Ubiquitous Network............................... 66
1.2 Configuration of the Experimental Ubiquitous Services ......................... 69
2 EXPERIMENT PARAMETERS ........................................................... 71
3 EXPERIMENTAL RESULTS AND ANALYSES ............................................... 72
CHAPTER 6 CONCLUSION AND FUTURE WORK ................................................ 79
1 CONCLUSION OF OUR WORK .......................................................... 79
2 OPEN ISSUES ON SERVICE-ORIENTED DEVICE ARRANGEMENT .............................. 80
REFERENCES .......................................................................... 81
APPENDIX A FORMAL DEFINITIONS OF KP, MCKP, AND MDKP ................................. 84
APPENDIX B DETAILED CONFIGURATION OF EXPERIMENTS .................................... 86
                                    

[AKB01] M. Akbar, E. Manning, G. C. Shoja, and S. Khan, “Heuristic Solutions for Multiple-Choice Multi-Dimension Knapsack Problem”, in Proc. of Int. Conf. on Computational Science, pp. 112-117, 2001.
[ALA05] S. Alam, M. Hasan, M. Hossain, and A.S.M. Sohail, “Heuristic Solution of MMKP in Different Distributed Admission Control and QoS Adaptation Architectures for Video on Demand Service”, in Proc. of 2nd Int. Conf. on Broadband Networks, 2, pp. 896-903, 2005.
[BAR90] P. Barcia and K. Jornsten, “Improved Lagrangian Decomposition: an Application to the Generalized Assignment Problem,” European Journal of Operational Research, 46, pp. 84-92, 1990.
[BAS03-1] P. Basu, W. Ke, and T. D. C. Little, “Dynamic Task-Based Anycasting in Mobile Ad Hoc Networks”, Mobile Networks and Applications, 8(5), pp. 593-612, 2003.
[BAS03-2] P. Basu, “A task based approach for modeling distributed applications on mobile ad hoc networks”, Ph.D. dissertation, Boston University, Boston, MA, 2003.
[BOH05] M. Bohlen, J. Gabian, D. Pfeifer, and J.T. Rinker, “Prototypes in Pervasive computing”, IEEE Pervasive Computing, 4(4), pp. 78-80, 2005.
[DEL93] R. DeLeone, R. Jain, and K. Straus, “Solution of Multiple-choice Knapsack Problem Encounter in High-level Synthesis of VLSI Circuits,” Journal of Computer Mathematics, 47, pp. 163-176, 1993.
[EIK02] M. Ei-Kadi, S. Olariu, and H. Abdel-Wahab, “A Rate-based Borrowing Scheme for QoS Provisioning in Multimedia Wireless Networks,” IEEE Trans. on Parallel and Distributed System, 13(2), pp. 156-166, 2002.
[EVE63] H. Everett III, “Generalized Lagrange Multiplier Method for Solving Problems of Optimum Allocation of Resources”, Operations Research, 11(3), pp. 399-417, 1963.
[HUA06] P.-C. Huang, K.-R. Lee, W.-T. Su, M.-F. Horng, C.-C. Lin, Y.-H. Kuo, and Y.-T. Chen, “Control Component Development of Information Appliances on Networks”, Journal of Information Science and Engineering, 22(4), pp. 771-784, 2006.
[JOY00] B. Joy and W. K. Edwards, “Core Jini”, Prentice Hall, 2000.
[KHA98] S. Khan, “Quality Adaptation in a Multi-Session Adaptive Multimedia System: Model and Architecture”, PhD paper, Department of Electrical and Computer Engineering, University of Victoria, 1998.
[KHA02] S. Khan, K. F. Li, E. G. Manning, and M. M. Akbar, “Solving the Knapsack Problem for Adaptive Multimedia Systems”, Studia Informatica Universalis, 2(1), pp.157-178, 2002.
[KOL67] P. Kolesar, “A Branch and Bound Algorithm for the Knapsack Problem”, Management Science, 13, pp. 723-735, 1967.
[KOZ03] U. C. Kozat and L. Tassiulas, “Network Layer Support for Service Discovery in Mobile Ad Hoc Networks”, in Proc. of IEEE INFOCOM, 22(1), pp. 1965-1975, 2003.
[LAW76] E. L. Lawler, “Combinatorial Optimization: Networks and Matroids”, Holt, Rinehart & Winston, N.Y., 1976.
[LEE03] C. Lee, A. Helal, N. Desai, V. Verma, and B. Arslan, “Konark: A System and Protocols for Device Independent, Peer-to-Peer Discovery and Delivery of Mobile Services”, IEEE Trans. on Sys., Man, and Cybernetics, 33(6), pp. 682-696, 2003.
[MIC06] Microsoft, “LLTD: Link Layer Topology Discovery Protocol”, Windows Rally Specification, 2006.
[MOS97] M. Moser, D. P. Jokanovic, and N. Shiratori, “An Algorithm for the Multidimensional Multiple-Choice Knapsack Problem”, IEICE Trans. on Fundamentals of Electronics, 80(3), pp. 582-589, 1997.
[NAU78] R. Nauss, “The 0-1 Knapsack Problem with Multiple Choice Constraints”, European Journal of Operational Research, 2, pp. 125-131, 1978.
[NOV02] M. Novaes, P. Westerink, and C. Codella, “, in Proc. of Int. Conf. on Communications, 4, pp. 2563-2567, 2002.
[OXY00] MIT Project Oxygen. Available: http://www.oxygen.lcs.mit.edu/
[PAR05] R. Parra-Hernandez and N. Dimopoulos, “A New Heuristic for Solving the Multi-choice Multidimensional Knapsack Problem”, IEEE Trans. on Sys., Man, and Cybernetics, 35(5), pp. 708-717, 2005.
[PET67] C.C. Peterson, “Computational Experience with Variants of the Balas Algorithm Applied to the Selection of R&D Projects,” Management Science, 13, pp. 736-750, 1967.
[REM04] J. Remy, “Resource Constrained Scheduling on Multiple Machines”, Elsevier Information Processing Letters, 91, pp. 177-182, 2004.
[SHI79] W. Shih, “A Branch and Bound Method for the Multiconstraint Knapsack Problem”, Journal of the Operational Research Society, 30, pp. 369-378, 1979.
[SIN79] A. Sinha and A.A. Zoltners, “The Multiple-choice Knapsack Problem,” Operations Research, 27, pp. 503-515, 1979.
[SIV06] S. Sivavakeesar, O. F. Gonzalez, and G. Pavlou, “Service Discovery Strategies in Ubiquitous Communication Environments”, IEEE Communication Magazine, 44(9), pp. 106-113, 2006.
[SU06] C.-C. Su, K.-S. Lu, M.-F. Horng, C.-L. Chen, Y.-H. Kuo, J.-P. Hsu, and W.-H. C, “Service-oriented Device Anycasting using Quality First Search in Wireless Personal Area Network”, in Proc. of 2006 IFIP Int. Conf. on Embedded and Ubiquitous Computing, pp. 620-629, 2006.
[TOY75] Y. Toyoda, “A Simplified Algorithm for Obtaining Approximate Solution to Zero-one Programming Problems”, Management Science, 21, pp. 1417-1427, 1975.
[VEL94] S.L. van de Velde and J.M. Worm, “Multi-period Planning of Road Maintenance: a Multiple-choice Multi-knapsack Problem,” Technical Report LPOM-94-6, Dept. of Mechanical Engineering, University of Twente, 1994.
[VER99] J. Verzades, E. Guttman, C. Perkins, and S. Kaplan, “Service Location Protocol, Version 2”, IETF RFC 2608, 1999.
[WEI66] H.M. Weingartner, “Capital Budgeting of Interrelated Projects: Survey and Synthesis,” Management Science, 12, pp. 485-516, 1966.
[YU05-1] T. Yu and K.-J. Lin, “Service Selection Algorithm for Composing Complex Services with Multiple QoS Constraints”, in Proc. of 3rd Int. Conf. on Service Oriented Computing, pp. 130-143, 2005.
[YU05-2] T. Yu and K.-J. Lin, “Service Selection Algorithms for Web Services with End-to-end QoS Constraints”, Journal of Information Systems and e-Business Management, 3(2), pp. 103-126, 2005.
[YU07] T. Yu, Y. Zhang, and K.-J. Lin, “Efficient Algorithms for Web Services Selection with End-to-end QoS Constraints”, ACM Trans. on the Web, 1(1), Article 6, 2007.

校內：2008-08-27公開
校外：2008-08-27公開

簡易檢索 / 詳目顯示

相關論文