物聯網內以拓樸為基礎之自動設定演算法

Topology based Automatic Configuration for the Internet of Things

鄧安哲(An-Che Teng)

指導教授 ： 周俊廷

國立臺灣大學/電機資訊學院/電信工程學研究所/碩士(2017年)

https://doi.org/10.6342/NTU201702027

摘要

在未來的無線通訊領域中，物聯網將成為下一個世代中的主角。不同於以往的人對人通訊，物聯網是由數以萬計的裝置和物件所連通而成的網路。也因為這龐大的數量，如何設定、管理與維護此難以想像的龐大網路成為了實現物聯網的關鍵。很明顯的，傳統人工或半自動的解決方案無法有效的解決上述問題。
在許多設定與管理的物聯網議題中，知曉某一已知位置上安裝的裝置之虛擬邏輯地址非常重要。舉例來說，使用者期望鄰近廚房電燈之開關能夠控制廚房之電燈，而此家用物聯網路之控制邏輯需要同時知道開關和電燈的實際位置和網路地址。雖然以人工的方式設定能解決小規模的實際位置和網路地址隻配對問題，但對於大規模之物聯網路來說，人工的方式依然無法規模化且不便進行管理
為了解決此問題，我們提出了分散式且可規模化的基於拓樸之自動設定演算法。有別於傳統以定位演算法之解決方案，此配對問題被我們視為一種排序問題。在我們的演算法下，N個已知邏輯地址的裝置根據鄰近裝置之無線訊號資訊進行排序成為一個序列，而N個已知的實際位置根據安裝拓樸排序而成另一個序列。因此，此問題從二維配對問題轉化為一維的排序問題，相較於傳統定位演算法與圖像演算法來說進而更加簡單、更能被規模化以及具有更低的複雜度。
我們所研究模擬的結果顯示，在網狀拓樸中，我們提出的演算法在高達0.8測量誤差 (Measurement Error Rate, MER) 的條件限制下，能夠達到80%的成功率；而基於定位之三角定位演算法與MDS-ICP演算法只能在0.5與0.2的較低測量誤差下達到80%的成功率。在其他拓樸中我們的演算法依然較為可靠且複雜度更低。為了證明演算法在實際室內環境的可應用性，我們設計了類環令牌且基於Simple Flooding之通訊協定，並將其實作於安裝了IEEE 802.15.4模組與STM32F0晶片之FCM2401上。實驗結果也顯示我們的演算法於現實環境中運行良好且有效解決自動設定之問題。

關鍵字

物聯網 ； 自動設定

並列摘要

The Internet of Things (IoT) is becoming main drive of the growth of wireless networks. Different from the human-to-human communication, IoT is a huge network that connects an enormous amount of physical objects. As a result, how to configure, manage, and maintain such a huge network becomes the key to realizing IoT. Obviously, the traditional manual or semi-automatic solutions will not be applicable to the emerging IoT networks.

Among many configuration/management issues in an IoT network, knowing the network (logical) address of a device installed at a certain physical position is important. For example, one would like a switch on the wall near the entrance of a kitchen to control the light fixtures in the kitchen. The control logic of this home network would need to know the network addresses of the switch and light fixtures at these two specific locations. Although one can manually provide the logical address and location "tuple" of each device to the control logic, such a solution is not scalable for an IoT network.

In this thesis, we propose a distributed, and scalable algorithm to solve this problem. Unlink the traditional positioning approaches, the problem is treated as a sorting problem. With the help of our algorithm, N known logical addresses (i.e., MAC addresses) are sorted as a sequence based on radio neighborhood information collected by the devices, while the N known physical addresses (installation locations) are sorted as another sequence based on the installation topology. As a result, the problem becomes a one-dimensional problem and is more scalable and simpler, in terms of computation complexity, than the traditional positioning-based or image-based approaches.

The simulation results show that our algorithm can achieve 80\% success rate with 0.8 Measurement Error Rate (MER), while the trilateration and MDS-ICP can achieve the same success rate with only 0.5 MER and 0.2 MER, respectively t for a grid topology. In order to demonstrate the feasibility, we also implement this algorithm in IEEE 802.15.4 wireless modules using a simple flooding protocol with a majority voting rule. The experiment results show that the algorithms work well in a real indoor environment.

並列關鍵字

Internet of Things ； automatic configuration

參考文獻

[1] S. Chen, H. Xu, D. Liu, B. Hu, and H. Wang, “A vision of iot: Applications,　challenges, and opportunities with china perspective,” IEEE Internet of Things　journal, vol. 1, no. 4, pp. 349–359, 2014.

[3] A. Al-Fuqaha, M. Guizani, M. Mohammadi, M. Aledhari, and M. Ayyash, “Internet of things: A survey on enabling technologies, protocols, and applications,” IEEE Communications Surveys & Tutorials, vol. 17, no. 4, pp. 2347–2376, 2015.

[7] L. Doherty, L. El Ghaoui, et al., “Convex position estimation in wireless sensor networks,” in INFOCOM 2001. Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE, vol. 3, pp. 1655–1663, IEEE, 2001.

[9] K. A. Khalid and T. A. Gulliver, “Range-based localization in wireless networks using decision trees,” in GLOBECOM Workshops (GC Wkshps), 2010 IEEE, pp. 131–135, IEEE, 2010.

[10] R. Nagpal, H. Shrobe, and J. Bachrach, “Organizing a global coordinate system　from local information on an ad hoc sensor network,” in Information Processing in Sensor Networks, pp. 333–348, Springer, 2003.