臺灣博碩士論文加值系統

With advances in numerous technologies, our world is moving towards an ``always connected" paradigm. Internet of Things (IoT) is a tangible realization in this new paradigm and enables connectivity from “anytime, anywhere for anyone” toward “anytime, anywhere for anything”. With IoT, objects (e.g., toothbrush, door, window, etc.) in our daily lives are able to be connected with each other. These connected objects can sense the environment, communicate with each other and even transport various information to cloud servers, allowing service providers to make better decisions and take more appropriate actions.

Home automation is a promising application in IoT that provide users a more convenient, comfortable and secure living environment through connected objects. There are generally two steps involved to set up a home automation system. The first step is to establish physical connections between objects in the house and a gateway that is connected to the Internet. The second step is to set up logical connections between objects so that the system can provide service accordingly. Setting up physical connections in current home automation systems usually requires professional installation, which is expensive and difficult to modify once they are set up.

In this thesis, we propose an automatic solution for both steps. In our solution, clustering algorithms are used, base on the received signal strength measurements, to group objects that are in the same control zone. In home automation, the topology of control zones follows certain patterns, which are different from the random topology in other applications such as the intelligent transportation system (ITS). Based on this observation, hierarchical clustering algorithm is adopted. Simulation and experiment results show that more than 90 percent of objects can be automatically set up.

ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii
LIST OF TABLES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v
LIST OF FIGURES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi
CHAPTER 1 INTRODUCTION . . . . . . . . . . . . . . . . . . . . . 1
1.1 Evaluation Towards the Internet of Things . . . . . . . . . . . . . . 1
1.2 Application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.1 Home Automation . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.2 Home Automation System Architecture . . . . . . . . . . . . 5
1.2.3 Setting Up the Home Automation System . . . . . . . . . . . 6
1.3 Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.4 Thesis Overview and Organization . . . . . . . . . . . . . . . . . . . 11
CHAPTER 2 RELATED WORK . . . . . . . . . . . . . . . . . . . . . 13
2.1 Indoor Localization in Wireless Sensor Network . . . . . . . . . . . . 13
2.1.1 Anchor-based Techniques . . . . . . . . . . . . . . . . . . . . 14
2.1.2 Anchor-free Techniques . . . . . . . . . . . . . . . . . . . . . 22
2.2 Summary of Indoor Localization Techniques . . . . . . . . . . . . . . 23
CHAPTER 3 GROUPING SCHEME . . . . . . . . . . . . . . . . . . 25
3.1 Home Automation Properties . . . . . . . . . . . . . . . . . . . . . . 25
3.2 Grouping Scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.3 Clustering Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.3.1 Partitioning-based Clustering . . . . . . . . . . . . . . . . . . 28
3.3.2 Hierarchical-based Clustering . . . . . . . . . . . . . . . . . . 30
3.3.3 Density-based Clustering . . . . . . . . . . . . . . . . . . . . 32
3.3.4 Model-based Clustering . . . . . . . . . . . . . . . . . . . . . 32
3.3.5 Grid-based Clustering . . . . . . . . . . . . . . . . . . . . . . 34
3.3.6 Summary of Clustering Algorithms . . . . . . . . . . . . . . 34
3.4 Classi cation Algorithms . . . . . . . . . . . . . . . . . . . . . . . . 35
3.4.1 Neural Networks . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.4.2 Support Vector Machines . . . . . . . . . . . . . . . . . . . . 36
CHAPTER 4 SIMULATION AND EXPERIMENT RESULTS . . 38
4.1 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.1.1 Performance Metric . . . . . . . . . . . . . . . . . . . . . . . 39
4.1.2 Multi-room Scenarios . . . . . . . . . . . . . . . . . . . . . . 39
4.1.3 Single Room Scenarios . . . . . . . . . . . . . . . . . . . . . 41
4.2 Experiment Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.2.1 Experiment Setting . . . . . . . . . . . . . . . . . . . . . . . 44
4.2.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
CHAPTER 5 DISCUSSIONS . . . . . . . . . . . . . . . . . . . . . . . 45
5.1 Correction through User Feedbacks . . . . . . . . . . . . . . . . . . 45
5.2 E ectiveness of Clustering Algorithms under Di erent Topologies . . 47
5.2.1 Spherical Topologies and Line-shaped Topologies . . . . . . . 47
CHAPTER 6 CONCLUSIONS . . . . . . . . . . . . . . . . . . . . . . 50

[1] A. Gavras, A. Karila, S. Fdida, M. May, and M. Potts, “Future internet research and experimentation: there initiative," Computer Communication Review, vol. 37, no. 3, pp. 89-92, 2007.
[2] B. M. Leiner, V. G. Cerf, D. D. Clark, R. E. Kahn, L. Kleinrock, D. C. Lynch, J. Postel, L. G. Roberts, and S. Wol , “Brief history of the internet," Oct. 2012. http://www.internetsociety.org/internet/what-internet/history-internet/brief-history-internet.
[3] Statista, “Number of monthly active facebook users world-wide from 3rd quarter 2008 to 4th quarter 2013 (in millions)," 2014. http://www.statista.com/statistics/264810/number-of-monthly-active-facebook-users-worldwide/.
[4] I. T. Union, “Key ict indicators for developed and developing countries and the
world (totals and penatration rates)," Geneva, Februrary 2013.
[5] K. Bonsor and C. Keener, “Howstuworks "how rfid works," 2010. http://electronics.howstuffworks.com/gadgets/high-tech-gadgets/rfid.htm.
[6] T. O''Brien, “In a nutshell: What are qr codes?," 2010. http://www.switched.com/2010/06/21/in-a-nutshell-what-are-qr-codes/.
[7] A. J. Jara, L. Ladid, and A. Skarmeta, “The internet of everything through ipv6:
An analysis of challenges, solutions and opportunities," Journal of Wireless Mobile Networks, Ubiquitous Computing, and Dependable Applications (JoWUA), vol. 4, pp. 97{118, 9 2013.
[8] K. Ashton, “That ''internet of things'' thing," RFID Journal, July 2009.
[9] I. T. Union, “ITU Internet Report 2005: The Internet of Things." http://ictlogy.net/bibliography/reports/projects.php?idp=501, 2005. [Online; accessed 1-March-2014].
[10] L. Coetzee and J. Eksteen, “The internet of things - promise for the future? An introduction," in IST-Africa Conference Proceedings, 2011, pp. 1-9, May 2011.
[11] A. Gluhak, S. Krco, M. Nati, D. Psterer, N. Mitton, and T. Razandralambo, “A survey on facilities for experimental internet of things research," Communications Magazine, IEEE, vol. 49, pp. 58-67, November 2011.
[12] “Vera smarter home control." http://getvera.com/. Accessed: 2014-07-10.
[13] “Home automation systems - homeseer." http://www.homeseer.com/. Accessed: 2014-07-10.
[14] “Wemo home automation." http://www.belkin.com/us/Products/home-automation/c/wemo-home-automation/. Accessed: 2014-07-10.
[15] “Incontrol home automation." www.incontrolha.com/. Accessed: 2014-07-10.
[16] D. Evans, “The Internet of Things - How the Next Evolution of the Internet Is Changing Everything." https://www.cisco.com/web/about/ac79/docs/innov/IoT_IBSG_0411FINAL.pdf, 2011. [Online; accessed 1-March-2014].
[17] “Elan: Total home control." http://www.elanhomesystems.com/. Accessed:2014-07-10.
[18] “Home automation | smart home technology | savant systems." http://www.savantsystems.com/. Accessed: 2014-07-10.
[19] “Control systems for home automation, campus &; building control by Crestron electronics." http://www.crestron.com/. Accessed: 2014-07-10.
[20] “Home automation review 2014 - reviewed and ranked." http://www. topconsumerreviews.com/home-automation/. Accessed: 2014-07-10.
[21] “Home automation review 2014 - reviewed and ranked." http://www.topconsumerreviews.com/home-automation/. Accessed: 2014-07-10.
[22] “Revolv|the universal smart home automation hub and app." http://revolv.com/. Accessed: 2014-07-10.
[23] “Webee: The real smart home | indiegogo." https://www.indiegogo.com/projects/webee-the-real-smart-home. Accessed: 2014-07-10.
[24] “Smartthings | easy, open, limitless smart home platform." http://www.smartthings.com/. Accessed: 2014-07-10.
[25] “Iris smart home management system: Thermostats and more." http://www.lowes.com/cd_Iris_239939199_. Accessed: 2014-07-10.
[26] S. Jain, A. Sabharwal, and S. Chandra, “An improvised localization scheme using active rfid for accurate tracking in smart homes," in Computer Modelling andSimulation (UKSim), 2010 12th International Conference on, pp. 51-56, March 2010.
[27] F. Viani, F. Robol, A. Polo, P. Rocca, G. Oliveri, and A. Massa, “Wireless architectures for heterogeneous sensing in smart home applications: Concepts and real implementation," Proceedings of the IEEE, vol. 101, pp. 2381-2396, Nov 2013.
[28] R. Zetik, G. Shen, and R. Thoma, “Evaluation of requirements for uwb localization systems in home-entertainment applications," in Indoor Positioning and Indoor Navigation (IPIN), 2010 International Conference on, pp. 1-8, Sept 2010.
[29] Y.-M. Huang, D.-C. Wang, and C.-C. Chen, “A verication-based localization method for unstable radio sensor networks in smart home environments," in Multimedia and Ubiquitous Engineering, 2008. MUE 2008. International Conference on, pp. 390-393, April 2008.
[30] K. Langendoen and N. Reijers, “Distributed localization in wireless sensor networks: A quantitative comparison," Comput. Netw., vol. 43, pp. 499-518, November 2003.
[31] D. Estrin, R. Govindan, J. Heidemann, and S. Kumar, “Next century challenges: Scalable coordination in sensor networks," in Proceedings of the 5th Annual ACM/IEEE International Conference on Mobile Computing and Net- working, MobiCom ''99, (New York, NY, USA), pp. 263-270, ACM, 1999.
[32] X. Xu, N. S. V. Rao, and S. Sahni, “A computational geometry method for localization using differences of distances," ACM Trans. Sen. Netw., vol. 6, pp. 10:1-
10:25, Mar. 2010.
[33] Z. Yang and Y. Liu, “Quality of trilateration: Condence-based iterative localization.," IEEE Trans. Parallel Distrib. Syst., vol. 21, no. 5, pp. 631-640, 2010.
[34] A. Savvides, H. Park, and M. B. Srivastava, “The bits and ops of the n-hop multilateration primitive for node localization problems," in Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications, WSNA ''02, (New York, NY, USA), pp. 112-121, ACM, 2002.
[35] J. Hightower, R. Want, and G. Borriello, “SpotON: An indoor 3d location sensing technology based on RF signal strength," UW CSE 00-02-02, University of ashington, Department of Computer Science and Engineering, Seattle, WA, February 2000.
[36] A. Savvides, C.-C. Han, and M. B. Strivastava, “Dynamic ne-grained localization in ad-hoc networks of sensors," in Proceedings of the 7th Annual International Conference on Mobile Computing and Networking, MobiCom ''01, (New York, NY, USA), pp. 166-179, ACM, 2001.
[37] J. A. Costa, N. Patwari, and A. O. Hero, III, “Distributed weighted multidimensional scaling for node localization in sensor networks," ACM Trans. Sen. Netw., vol. 2, pp. 39-64, feb 2006.
[38] N. Patwari, A. O. H. Iii, and J. A. Costa, “Learning sensor location from signal strength and connectivity."
[39] Y. Ji, S. Biaz, S. Pandey, and P. Agrawal, “Ariadne: A dynamic indoor signal map construction and localization system," in Proceedings of the 4th International Conference on Mobile Systems, Applications and Services, MobiSys ''06, (New York, NY, USA), pp. 151-164, ACM, 2006.
[40] C. Peng, G. Shen, Y. Zhang, Y. Li, and K. Tan, “Beepbeep: A high accuracy acoustic ranging system using cots mobile devices," in Proceedings of the 5th International Conference on Embedded Networked Sensor Systems, SenSys ''07, (New York, NY, USA), pp. 1-14, ACM, 2007.
[41] S. Ganeriwal, R. Kumar, and M. B. Srivastava, “Timing-sync protocol for sensor networks," in Proceedings of the 1st International Conference on Embedded Networked Sensor Systems, SenSys ''03, (New York, NY, USA), pp. 138-149, ACM, 2003.
[42] M. Mar oti, B. Kusy, G. Simon, and A. L edeczi, “The flooding time synchronization protocol," in Proceedings of the 2Nd International Conference on Embedded Networked Sensor Systems, SenSys ''04, (New York, NY, USA), pp. 39-49, ACM,2004.
[43] N. B. Priyantha, A. K. Miu, H. Balakrishnan, and S. Teller, “The cricket compass for context-aware mobile applications," in Proceedings of the 7th Annual International Conference on Mobile Computing and Networking, MobiCom ''01, (New York, NY, USA), pp. 1-14, ACM, 2001.
[44] N. Bulusu, J. Heidemann, and D. Estrin, “Gps-less low-cost outdoor localization for very small devices," Personal Communications, IEEE, vol. 7, pp. 28-34, Oct 2000.
[45] M. Rudafshani and S. Datta, “Localization in wireless sensor networks," in Proceedings of the 6th International Conference on Information Processing in Sensor Networks, IPSN ''07, (New York, NY, USA), pp. 51-60, ACM, 2007.
[46] S. Schuhmann, K. Herrmann, K. Rothermel, J. Blumenthal, and D. Timmermann, “Improved weighted centroid localization in smart ubiquitous environments," in Proceedings of the 5th International Conference on Ubiquitous Intelligence and Computing, UIC ''08, (Berlin, Heidelberg), pp. 20-34, Springer-Verlag, 2008.
[47] J. B. Tenenbaum, V. de Silva, and J. C. Langford, “A global geometric framework for nonlinear dimensionality reduction," Science, vol. 290, no. 5500, p. 2319, 2000.
[48] Y. Shang, W. Ruml, Y. Zhang, and M. P. J. Fromherz, “Localization from mere connectivity," in Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking &;Amp; Computing, MobiHoc ''03, (New York, NY, USA), pp. 201-212, ACM, 2003.
[49] X. Ji and H. Zha, “Sensor positioning in wireless ad-hoc sensor networks using multidimensional scaling," in INFOCOM 2004. Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies, vol. 4, pp. 2652-2661 vol.4, March 2004.
[50] M. J. Greenacre, Theory and applications of correspondence analysis. London: Academic Press, 1984.
[51] S. Guha, R. Rastogi, and K. Shim, “Cure: An efficient clustering algorithm for large databases," in Proceedings of the 1998 ACM SIGMOD International Conference on Management of Data, SIGMOD ''98, (New York, NY, USA), pp. 73-84, ACM, 1998.
[52] R. T. Ng and J. Han, “Clarans: A method for clustering objects for spatial data mining," IEEE Trans. on Knowl. and Data Eng., vol. 14, pp. 1003-1016, September 2002.
[53] R. Xu and I. Wunsch, D., “Survey of clustering algorithms," Neural Networks, IEEE Transactions on, vol. 16, pp. 645-678, May 2005.
[54] T. Zhang, R. Ramakrishnan, and M. Livny, “Birch: An efficient data clustering method for very large databases," in Proceedings of the 1996 ACM SIGMOD
International Conference on Management of Data, SIGMOD ''96, (New York, NY, USA), pp. 103-114, ACM, 1996.
[55] A. Hinneburg and H.-H. Gabriel, “Denclue 2.0: Fast clustering based on kernel density estimation," in Proceedings of the 7th International Conference on Intelligent Data Analysis, IDA''07, (Berlin, Heidelberg), pp. 70-80, Springer-Verlag,2007.
[56] G. Sheikholeslami, S. Chatterjee, and A. Zhang, "Wavecluster: A wavelet-based clustering approach for spatial data in very large databases," The VLDB Journal, vol. 8, pp. 289{304, Feb. 2000.