成功大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	曾彥杰 Tseng, Yen-Chieh
論文名稱：	應用多目標效益函數理論解決資源有限的普及網路中之服務導向裝置配置問題 Applying Multi-Objective Utility Theory to Service-Oriented Device Allocation in Resource-constrained Ubiquitous Networks
指導教授：	郭耀煌 Kuo, Yau-Hwang
學位類別：	碩士 Master
系所名稱：	電機資訊學院 - 資訊工程學系 Department of Computer Science and Information Engineering
論文出版年：	2008
畢業學年度：	96
語文別：	英文
論文頁數：	75
中文關鍵詞：	普及服務、多維度多選擇的背包問題、資源配置、允入控制、微型網路
外文關鍵詞：	Device arrangement, Ubiquitous service, Multi-dimension Multi-choice Knapsack Problem, Ubiquitous computing
相關次數：	點閱：243 下載：1
分享至:	分享至facebook 分享至twitter

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

近幾年，有許多普及計算的研究著重在有限的普及網路中之服務自動化。服務自動化的目的就是自動地去組織一組裝置，又稱為微型網路，來實現使用者所提出的普及服務。在多使用者的環境中，服務自動化最大的挑戰就是解決服務品質及資源利用的衝突。在之前的研究，這類的挑戰可以被公式化及證明成一個多維度多選擇的背包問題。此外，服務導向之裝置調節藉由多維度多選擇的背包問題演算法應用支援服務自動化。服務導向之裝置調節藉由一般的效益函數來量化普及服務之服務品質。然而實際上單一個效益函數是不夠來量化多不同目標的普及服務的品質，譬如:彈性，即時性，以及急迫性。服務導向之裝置調節直接利用多維度多選擇的背包問題在資源有限的環境下求得從最多要求普及服務中最大累積的服務效益。然而，這些服務品質可能隨著越來越多要求的普及服務允許被執行而減少。
在這篇文章中，藉由以上的議題來使用修改的服務導向裝置調節進一步的改善服務導向裝置調節的效能。普及服務首先根據服務品質的目標分類，服務品質的目標包括彈性，即時性以及急迫性。接著多目標效益函數理論根據普及服務的服務品質目標應用於資源配置及服務排程來達到有效的網路資源配置。最後，允入控制也加入修改的服務導向裝置調節來避免當允許新進來的普及服務時，服務品質會被顯著的降低。模擬結果指出在不同的情況中，修改的服務導向裝置調節有效改善服務導向裝置調節的效能約80~300百分比。

In recent years, a lot of researches on ubiquitous computing focus on the service automation in resource-constrained ubiquitous networks. The objective of service automation is to automatically organize a set of devices, called a piconet, to carry out the ubiquitous services requested by users. The main challenge of service automation in multi-user environments is resolving the conflict between Quality of Service (QoS) and resource utilization. In our previous work, this challenge was formulated and then proved as a Multi-dimension Multi-choice Knapsack Problem (MMKP). In addition, Service-Oriented Device Composer (SODC) was proposed to support service automation by applying existing MMKP algorithms. SODC adopts a generic utility function to quantify the quality of all ubiquitous services. However, in practical, one identical utility function is insufficient to quantify the quality of the ubiquitous services with distinct QoS objectives, such as flexibility, real-time, and urgency. By directly applying MMKP algorithms, SODC maximizes the aggregated service utility of the most requested ubiquitous services under the resource constraints. However, the service quality will be reduced while more and more requested ubiquitous services are admitted to execute.
In this paper, Modified SODC (M-SODC) is proposed to further improve the performance of SODC by fixing above issues. In M-SODC, the ubiquitous services are first classified according to their QoS objectives, including flexibility, real-time, and urgency. The multi-objective utility theory is then applied to resource allocation and service scheduling for efficiently allocating network resources according to the QoS objectives of requested ubiquitous services. Finally, the admission control is embedded into M-SODC to prevent the service quality from being significantly decreased while admitting any new-arrived requested ubiquitous service. The simulation results show that M-SODC effectively improve the performance of SODC by 80 to 300 percent in various cases.

LIST OF TABLES ........................................................................................................................................ 11
LIST OF FIGURES ...................................................................................................................................... 12
CHAPTER 1 INTRODUCTION ........................................................................................................... 13
CHAPTER 2 RELATED WORK .......................................................................................................... 16
1 DEVICE COMPOSITION APPROACHES ............................................................................................... 17
2 THE ISSUES ON QOS OBJECTIVES OF THE UBIQUITOUS SERVICES .................................................... 19
3 THE ISSUE ON THE MMKP PROBLEM ............................................................................................... 20
CHAPTER 3 MULTI-OBJECTIVE DEVICE ALLOCATION PROBLEM IN
RESOURCE-CONSTRAINED UBIQUITOUS NETWORKS: MODELING AND FORMULATION 22
1 UBIQUITOUS SERVICES AND UBIQUITOUS NETWORK MODELING .................................................... 22
1.1. Service Profile: Modeling of Ubiquitous Service ................................................................... 23
1.2. Network Profile: Modeling of Ubiquitous Network ............................................................... 24
2 THE TAXONOMY OF UBIQUITOUS SERVICE ..................................................................................... 25
2.1 QoS Objective: Flexibility .......................................................................................................... 27
2.2 QoS Objective: Real-time ........................................................................................................... 29
2.3 QoS Objective: Urgency ............................................................................................................. 31
2.4 Piconet Quality.......................................................................................................................... 32
3 RESOURCE-CONSTRAINED DEVICE COMPOSITION PROBLEM FORMULATION ................................... 34
CHAPTER 4 MODIFIED SERVICE-ORIENTED DEVICE COMPOSER (M-SODC) ................. 37
1 UBIQUITOUS ENVIRONMENT DATABASE ......................................................................................... 37
1.1 Requested Ubiquitous Service Table (RUT) ............................................................................... 38
1.2 Ubiquitous Service Template (UST) ........................................................................................... 39
1.3 Available Requested Ubiquitous Service Table (ARUST) .......................................................... 40
2 MODIFIED SERVICE-ORIENTED DEVICE COMPOSER ........................................................................ 41
2.1 Capable Piconet Determination ................................................................................................. 42
2.2 RDCP to MMKP Transformation .............................................................................................. 43
2.3 Schedule by QoS Objectives ....................................................................................................... 45
2.4 MMKP Solution .......................................................................................................................... 46
2.5 Post-processing .......................................................................................................................... 48
3 THE ANALYSIS OF COMPUTATION COMPLEXITY OF M-SODC .......................................................... 51
CHAPTER 5 SIMULATION RESULT ................................................................................................ 54
1 SIMULATED ENVIRONMENT ............................................................................................................. 54
2 SIMULATED UBIQUITOUS SERVICES ................................................................................................ 56
3 PERFORMANCE METRIC................................................................................................................... 59
4 SIMULATION CONFIGURATION AND RESULT ................................................................................... 61
4.1 For single objective .................................................................................................................... 61
4.2 For multi-objective ..................................................................................................................... 65
CHAPTER 6 CONCLUSION AND FUTURE WORK ....................................................................... 69
REFERENCES .............................................................................................................................................. 71
APPENDIX A FORMAL DEFINITIONS OF KP, MCKP, AND MDKP ................................................ 73
                                    

[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
[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
[CHE01] H. Chen, T. Yu and K.J. Lin “QCWS: An Implementation of QoS-Capable Multimedia Web Services”, Journal of Multimedia Tools and applications, pp 140-148, 2001
[CU05] C. Curescu and S. Nadim-Tehrani, “Time-aware utility-based resource allocation in wireless networks,” in Sensor and Ad Hoc Communications and Networks, pp. 85-95, 2005.
[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.
[LI07] C. Li and L. Li, “Utility-based QoS optimisition strategy for multi-criteria scheduling on the grid,” in Journal of Parallel and Distributed Computing, pp. 142-153, 2007.
[LIA07] I. H. Liao and Y. H. Kuo, “A QoS approach for service-oriented device arrangement in resource-constrained ubiquitous environments,” Department of Computer Science and Information Engineering, National Cheng Kung University, Tainan, Taiwan, ROC, 2007.
[LU06] N. Lu and J. Bigham,” An optimal bandwidth adaptation algorithm for multi-class traffic in wireless networks,” in ACM International Conference Proceeding Series, Vol. 191, 2006.
[LU07] N. Lu and J. Bigham, “On utility-fair bandwidth adaptation for multi-class traffic QoS provisioning in wireless networks,” in Computer Networks, pp.2554-2564, 2007.
[OSG99] OSGi. The Open Services Gateway initiative. http://www.OSGi.org.
[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.
[SON05] G. Song and Y. Li, ”Utility-Based Resource Allocation and Scheduling in OFDM-Based Wireless Broadband Networks,” IEEE Communication Magazine, 2005.
[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.
[SU08] W. T. Su, I. H. Liao, K. R. Lee, and Y. H. Kuo, “Service-oriented device composition in resource-constrained ubiquitous environments,” in Wireless Communications and Networking Conference, 2008.
[UPN99] UPnP. Universal Plug and Play. http://www.UPnP.org.
[WEB04] Web Services http://www.w3.org/TR/ws-arch/
[WEI66] H.M. Weingartner, “Capital Budgeting of Interrelated Projects: Survey and Synthesis,” Management Science, 12, pp. 485-516, 1966.
[YU04] Tao Yu and Kwei-Jay Lin, “Service selection algorithms for Web services with end-to-end QoS constraints,” in Proceeding of IEEE International Conference on e-Commerce Technology, pp.129-136, 2004.
[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

2013-08-25公開

簡易檢索 / 詳目顯示

相關論文