跳到主要內容

臺灣博碩士論文加值系統

(44.210.77.73) 您好!臺灣時間:2024/02/23 10:35
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:余士元
研究生(外文):Shih-Yuan Yu
論文名稱:服務配對於物聯網系統節能之應用
論文名稱(外文):Energy Aware Service Matchmaking in IoT Systems
指導教授:許永真許永真引用關係
指導教授(外文):Jung-Jen Hsu
口試委員:李允中施吉昇林桂傑紀婉容
口試委員(外文):Jonathan LeeChih-Sheng ShihKwei-Jie LinWan-Rong Jih
口試日期:2014-07-30
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:資訊工程學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2014
畢業學年度:102
語文別:英文
論文頁數:50
中文關鍵詞:服務對應物聯網系統節能
外文關鍵詞:Service MatchmakingService Co-locationMaximum Weighted Independent SetIoT system
相關次數:
  • 被引用被引用:0
  • 點閱點閱:595
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
隨著物聯網科技的進步,將有越來越多物聯網裝置被佈建在人類生 活周遭,去感測、控制進而提升生活品質,裝置數量指數成長將會帶 出未來智慧生活的願景,但卻也衍生了一值得探討的議題-也就是物 聯網運作的能源使用效率。本篇論文討論並提出能提高物聯網裝置系 統節能效率的演算法,核心概念是儘可能將多個智慧服務同位佈建 (佈 建到在同一個裝置上) 以減少裝置在通訊上的電力消耗。

無論室內或戶外的環境,物聯網系統能夠自發性地協同合作並以最 優的方式滿足使用者需求是一個非常重要的功能,本論文運用服務對 應 (Service Matchmaking) 的技術,使得一個物聯網應用程式得以用最 優的方式佈建到實體環境中。

在本篇研究中我們將能源優化服務對應 (Energy aware service matchmaking) 表示成在圖論上常見的最大加權獨立集問題,同時證明我們研 究的問題是一個 NP 完備問題。論文中提出了一套流程將能源優化問 題轉換成另一個我們所定義的同位圖(Colocation Graph),從同位圖上 我們用近似演算法找出最大獨立集合,同時也找到能源優化佈建的最 佳解。論文也論述了轉圖演算法之時間複雜度。本論文改進前人提出 的基礎貪婪演算法,並使用模擬實驗去比較節能效率、計算時間。

The world is seeing more sensing and actuating devices being deployed in our environment. One issue for perpetually running Internet of Things (IoT) services is the energy efficiency. Many new IoT devices are running on more powerful platforms that have sufficient computing and memory capabilities to support multiple sensors. Therefore, one energy saving strategy is to co-locate several energy-hungry services on one device in order to reduce the communication energy cost. This thesis proposes an energy aware service matchmaking approach for deploying an application onto IoT devices. The energy aware service matchmaking problem can be modeled as a Maximum Weighted Independent Set (MWIS) problem and we prove it to be a NP-hard problem. We design the algorithm to transform a service flow to a co-location graph, and then use heuristic algorithms to find the maximum independent set from the graph which will be used for making deployment decisions. The time complexity of transformation algorithm is studied. The performance of different co-locating algorithms are evaluated by simulation in our study. Simulation result shows that our proposed methods can save more 10\% energy than baseline.

Acknowledgements iii
誌謝 v
Abstract vii
摘要 ix
1 Introduction 1
1.1 WuKongProject .............................. 1
1.2 Motivation.................................. 2
1.3 ThesisContribution............................. 3
1.4 ThesisOrganization............................. 3
2 Background and Related Work 5
2.1 Programming Internet of Things ...................... 5
2.2 IoT Service Matchmaking ......................... 6
2.3 Energy Efficiency on Wireless Sensor Network . . . . . . . . . . . . . . 8
2.4 Co-location Optimization Study ...................... 8
3 Background on WuKong 11
3.1 WuKong System Infrastructure....................... 11
3.2 IoT Services................................. 13
3.3 IoT Applications .............................. 14
3.4 IoT Devices and Systems.......................... 14
3.5 IoT Service Matchmaking ......................... 15
4 Energy Aware Service Matchmaking 17
4.1 Energy Model................................ 17
4.2 Problem Definition ............................. 19
4.3 Problem Analysis.............................. 20
5 Energy Aware Service Matchmaking Methodology 21
5.1 Maximum Weighted Independent Set.................... 22
5.2 Graph Construction............................. 23
5.2.1 Co-location Graph ......................... 24
5.2.2 Layer Based Graph Transformation ................ 25
5.2.3 Analysis of Transformation Algorithm. . . . . . . . . . . . . . . 28
5.3 Co-location Selection............................ 28
5.3.1 Selection Strategies......................... 29
5.3.2 Selection Framework........................ 30
5.3.3 Locating Remaining Services ................... 31
6 Performance Study 33
6.1 Simulation Setup .............................. 33
6.1.1 Service Component Generation .................. 34
6.1.2 FBP Application Generation.................... 34
6.1.3 Device System Generation..................... 35
6.2 Performance Metrics ............................ 35
6.3 Performance Comparison.......................... 36
7 Conclusion and Future Work 41
7.1 Conclusion ................................. 41
7.2 Future Work................................. 41
A The proof of NP-Hardness for P1 43
B Time Complexity Inference 45
B.1 Vertex Merging Complexity ........................ 45
B.2 Link Building Complexity ......................... 45
Bibliography ......................... 47

[1] ”cisco connections counter:” dynamic, online widget displays the number of con- nections being made at any one moment in time.
[2] C.-Y. Chang and H.-R. Chang. Energy-aware node placement, topology control and mac scheduling for wireless sensor networks. Comput. Netw., 52(11):2189–2204, Aug. 2008.
[3] G. Ferrari, P. Medagliani, S. D. Piazza, and M. Martalo. Wireless sensor networks: Performance analysis in indoor scenarios. EURASIP J. Wirel. Commun. Netw., 2007(1):41–41, Jan. 2007.
[4] C.-l. Fok, G.-c. Roman, C. Lu, and S. Louis. Rapid Development and Flexible De- ployment of Adaptive Wireless Sensor Network Applications.
[5] A. Gluhak, S. Krco, M. Nati, D. Pfisterer, N. Mitton, and T. Razafindralambo. A survey on facilities for experimental internet of things research. Communications Magazine, IEEE, 49(11):58–67, November 2011.
[6] M. N. Halgamuge, M. Zukerman, K. Ramamohanarao, and H. L. Vu. An estimation of sensor energy consumption. Progress In Electromagnetics Research B, 2009.
[7] M. Halldorsson and J. Radhakrishnan. Greed is good: Approximating independent sets in sparse and bounded-degree graphs. In Proceedings of the Twenty-sixth Annual ACM Symposium on Theory of Computing, STOC ’94, pages 439–448, New York, NY, USA, 1994. ACM.
[8] W. Heinzelman, A. Chandrakasan, and H. Balakrishnan. An application-specific protocol architecture for wireless microsensor networks. Wireless Communications, IEEE Transactions on, 1(4):660–670, 2002.
[9] Z. Huang, W. Jiang, S. Hu, and Z. Liu. Effective pruning algorithm for QoS-aware service composition. In Commerce and Enterprise Computing, 2009. CEC ’09. IEEE Conference on, pages 519–522, 2009.
[10] Z. Huang, K.-J. Lin, and A. Han. An Energy Sentient Methodology for Sensor Map- ping and Selection in IoT Systems. 2014 IEEE International Symposium on Indus- trial Eletronics, 2014.
[11] D. Hughes, K. Thoelen, W. Horre, N. Matthys, J. D. Cid, S. Michiels, C. Huygens, and W. Joosen. Looci: A loosely-coupled component infrastructure for networked embedded systems. In Proceedings of the 7th International Conference on Advances in Mobile Computing and Multimedia, MoMM ’09, pages 195–203, 2009.
[12] K.-J. Lin, N. Reijers, Y.-C. Wang, C.-S. Shih, and J. Y. Hsu. Building Smart M2M Applications Using the WuKong Profile Framework. 2013 IEEE International Con- ference on Green Computing and Communications and IEEE Internet of Things and IEEE Cyber, Physical and Social Computing, pages 1175–1180, Aug. 2013.
[13] G.Lu,N.Sadagopan,B.Krishnamachari,andA.Goel.Delayefficientsleepschedul- ing in wireless sensor networks. In INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings IEEE, volume 4, pages 2470–2481 vol. 4, 2005.
[14] S. Olariu and I. Stojmenovic. Design guidelines for maximizing lifetime and avoid- ing energy holes in sensor networks with uniform distribution and uniform reporting. In INFOCOM 2006. 25th IEEE International Conference on Computer Communi- cations. Proceedings, pages 1–12, 2006.
[15] P. Pradhan, V. Baghel, G. Panda, and M. Bernard. Energy efficient layout for a wire- less sensor network using multi-objective particle swarm optimization. In Advance Computing Conference, 2009. IACC 2009. IEEE International, pages 65–70, 2009.
[16] N. Reijers, K.-J. Lin, Y.-C. Wang, C.-S. Shih, and J. Y. Hsu. Design of an intelligent middleware for flexible sensor configuration in M2M systems. In SENSORNETS, pages 41–46, 2013.
[17] N. Reijers, Y.-C. Wang, C.-S. Shih, J. Y. jen Hsu, and K.-J. Lin. Building intelligent middleware for large scale CPS systems. In IEEE Conference on Service-Oriented Computing and Applications, pages 1–4, 2011.
[18] S. Sakai, M. Togasaki, and K. Yamazaki. A note on greedy algorithms for the max- imum weighted independent set problem. Discrete Applied Mathematics, 126(2 - 3):313 – 322, 2003.
[19] M. Sharifi, A. T. Rahmani, V. Rafe, and H. Momeni. CORBA Components Collo- cation Optimization Enhanced with Local ORB-Like Services Support. pages 1143– 1154, 2004.
[20] J. Wang, D. Li, G. Xing, and H. Du. Cross-layer sleep scheduling design in service-oriented wireless sensor networks. IEEE Transactions on Mobile Comput- ing, 9(11):1622–1633, 2010.
[21] M.-m. Wang. Middleware for Wireless Sensor Networks : A Survey. 23(2006):305– 326, 2008.
[22] Q. Wang, M. Hempstead, and W. Yang. A realistic power consumption model for wireless sensor network devices. In 3rd IEEE Conference on Sensor and Ad Hoc Communications and Networks, SECON ’06., volume 1, pages 286–295, 2006.
[23] Y.-C. Wang, W.-C. Peng, and Y.-C. Tseng. Energy-balanced dispatch of mobile sen- sors in a hybrid wireless sensor network. Parallel and Distributed Systems, IEEE Transactions on, 21(12):1836–1850, 2010.
[24] W. Ye, J. Heidemann, and D. Estrin. An energy-efficient mac protocol for wireless sensor networks. In Proceedings of IEEE INFOCOM, volume 3, pages 1567–1576 vol.3, 2002.
[25] W. Ye, J. Heidemann, and D. Estrin. Medium access control with coordinated adap- tive sleeping for wireless sensor networks. IEEE/ACM Trans. Netw., 12(3):493–506, June 2004.
[26] T. Yu, Y. Zhang, and K.-J. Lin. Efficient algorithms for web services selection with end-to-end QoS constraints. ACM Trans. Web, 1(1), May 2007.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top