臺灣博碩士論文加值系統

因應近年低速無線個人區域網路(Low-Rate Wireless Personal Area Networks, LR-WPANs)被廣泛的使用在IOT系統，Chiu and Wang提出具蟲洞之串鍊式路由演算法，包含串鍊式網路的建立、節點斷裂之資料跳躍機制、新節點加入機制、以Modbus協定為基礎建立適合於資料蒐集的Modbus延伸指令和蟲洞網路的建立，為一個適用於IOT資料蒐集演算法。但其中仍存在著許多不適切性。第一，在網路初始化問題上，離線節點交握位址訊息封包和插斷交握位址封包中節點，致使節點只能逐一開機完成建網，當大量節點存在於網路上時無法同時開機的演算法根本不具適切性；第二為連續節點斷裂問題，斷鏈端將隨機廣播大量詢問和加入封包欲重新加入網路中致使廣播風暴發生，干擾仍在網路上運作的節點，導致整個網路的崩潰；第三為節點離群問題，節點在沒有先行穩定路由的前提下即進行退場，將導致資料封包遺失；最後為封包處理問題，未規劃完整的重送封包佇列和建立封包處理旗標，將分別導致重送封包錯誤及封包的Race Condition。
於本論文中提出具適切性之蟲洞串鍊式路由演算法，包含以Lock-address機制實現可同時開機的建網演算法，讓路由的初始化更適切於節點數量龐大的環境中；再者，本演算法提出了穩定斷鏈、依序重置和計時切割節點斷裂判斷機制，當路由中有連續節點斷裂進而導致斷鏈時，讓斷鏈端節點群得以先行穩定斷鏈並依序廣播加入封包加入網路中，避免廣播風暴和鏈結錯誤的問題發生；第三，本論文提出了節點離群機制，當節點長期處於感測資料異常時，節點將依循離群機制穩定路由後再進行重置，避免導致資料封包的遺失；最後，本演算法規劃了完整的重送封包佇列和建立封包處理旗標，解決重送錯誤和封包的Race Condition問題。
在驗證上，論文中以NS3模擬軟體針對具蟲洞之串鍊式路由演算法中的開機建網程序和簡單氾濫式的廣播建網方式做網路初始化的效能評估，由模擬結果可以發現，在節點相距五公尺、節點數量從7*7至15*15的矩陣模型中，具適切性之蟲洞串鍊式路由演算法的建網程序之效能皆優於簡單氾濫的廣播建網方式達兩倍左右。未來我們希望具適切性之蟲洞串鍊式路由演算法不只在LR-WPANs的環境中實現，也得以實現在IEEE802.15.1或是IEEE802.11等等的協定上，建立無線網路資料蒐集演算法之標準。

Due to Low-Rate Wireless Personal Area Networks(LR-WPANs) is universally used in Internet of Things(IOT) in recent years, Chiu and Wang proposed a linked list routing algorithm with wormhole mechanism. The algorithm includes the manner of construction linked list network, data jumping for routing broken, a new node join mechanism, the manner of construction wormhole network and aim at the modbus protocol as application layer, set up suitable Modbus extension instructions for data collection. It’s an algorithm for IOT data collection. However, there are still a lot of non-adaptive in algorithm. First, on network initialization problem, because exchange address information packet with offline nodes and interrupt nodes which are exchanging address information, nodes must turn on respectively to finish construction network. When numerous nodes existing in network, the algorithm without nodes turn on simultaneously mechanism is non-adaptive. Second, the problem on continuous nodes broken, chain scission nodes will broadcast ask and join packet randomly for adding back to the network. The broadcast storm will be occurred and interference the nodes which are still working on network leads to the collapse of the entire network. Third, on node outliers problem, node exits without stabling routing first will cause data packets loss. Finally is packet processing problem, without planning a complete resend packet queue and establishing packet processing flag, will cause resend packet extracting error and packet race condition.
In this paper, we proposed an adaptive linked-list routing algorithm with wormhole mechanism. Included implementation the manner of turn on nodes simultaneously with Lock-address mechanism. Let the initialization of the routing more adaptive in a large number of nodes environment. Then the algorithm proposed the stable chain scission, reset sequentially and cutting timer mechanism for broken nodes determination. So that chain scission nodes can stable routing first then brocast join packet sequentially when continuous nodes broken occurred to avoid broadcast storm and linked error happen. Third we proposed the node outliers mechanism. Nodes will follow the node outliers mechanism to stable routing first, and then executing reset when node in sensoring data abnormally for a long time to avoid data packets loss. Finally, the algorithm planned a complete resend packet queue and established packet processing flag to solve resend packet extracting error and packet race condition.
In simulation, the performance of network initialization of adaptive linked-list routing algorithm with wormhole mechanism and flooding is compared and simulated by NS3 in this paper. The simulations results reveal that the initialization of adaptive linked-list routing algorithm with wormhole mechanism is more efficient than flooding when nodes are 5 meters apart and a matrix model of nodes number from 7*7 to 15*15. In the future, we expect that adaptive linked-list routing algorithm with wormhole mechanism not only implement in LR-WPANs environment, also in IEEE802.15.1 or IEEE802.11 etc. protocols. Establish the standard of the algorithm for wireless network data collection.

論文審定書 i
誌謝 ii
摘要 iii
Abstract iv
目錄 vi
圖次 viii
表次 xi
第1章 簡介 1
1.1 研究動機 1
1.2 研究目的 2
1.3 論文架構 2
第2章 背景知識與相關研究 3
2.1 Zigbee協定 3
2.1.1 實體層 3
2.1.2 MAC層 5
2.2 Modbus協定[15] 14
2.3 具蟲洞之串鍊式路由演算法[1] 16
2.3.1 封包格式 16
2.3.2 路由建立 19
2.3.3 路由維護 24
2.3.4 資料傳輸 28
2.4 具蟲洞之串鍊式路由演算法分析與討論 30
第3章 具適切性之蟲洞串鏈式路由演算法 32
3.1 封包格式 32
3.2 路由建立 34
3.2.1 可同時開機的建網程序 34
3.3 路由維護 46
3.3.1 節點離群機制 46
3.3.2 連續節點斷裂修復機制 49
3.4 封包處理 59
3.4.1 重送機制 59
3.4.2 封包Race Condition 62
第4章 實作平台與模擬平台介紹 64
4.1 實作平台 64
4.1.1 實作模組 64
4.1.2 實作平台 65
4.1.3 人機介面 66
4.2 模擬平台 67
4.2.1 NS3介紹 67
4.2.2 NS3實現具適切性之蟲洞串鍊式路由演算法 69
第5章 資料分析與探討 71
5.1 建網效能 71
5.2 資料蒐集時間 74
5.3 蟲洞網路建網時間和Scatter指令下傳時間 75
第6章 結論 77

[1]Jih-ching Chiu, Wen-Shin Wang, “Linked List Routing Algorithm With Wormhole Mechanism For Data Collecting Wireless Network,” 2014 International Computer Symposium (ICS), 2014.
[2]Yu-Chee Tseng, Sze-Yao Ni, Yuh-Shyan Chen, Jang-Ping Sheu, “The Broadcast Storm Problem in a Mobile Ad Hoc Network,” COMPUTER SCIENCE Wireless networks, Volume 8, Page.153- Page.167, Numbers 2-3 ,2002.
[3]Network Simulator 3, https://www.nsnam.org/docs/release/3.20/doxygen
[4]ZigBee Alliance, http://www.zigbee.org/
[5]IEEE Std 802.15.4™-2006.
[6]Microchip . (2010). dsPIC30F3014/4013Data Sheet [Online]. Available: http://ww1.microchip.com/downloads/en/devicedoc/70138c.pdf
[7]CHIRKAL TECHNOLOGY CO., LTD. http://www.chirkal.com.tw
[8]TEXAS INSTRUMENTS, http://www.ti.com/
[9]Texas Instruments. (2007, Jun 06). A True System-on-Chip solution for 2.4 GHz IEEE 802.15.4 / ZigBee(TM) (Rev. F) [Online]. Available: http://focus.ti.com/lit/ds/symlink/cc2430.pdf
[10]Microchip .(2009, Jan 1) . MPLAB ® IDE User’s Guide with MPLAB Editor and MPLAB SIM Simulator [Online]. Available: http://ww1.microchip.com/downloads/en/DeviceDoc/MPLAB_User_Guide_51519c.pdf
[11]Texas Instruments. (2006). IAR IDE User Manual Rev. 1.2 [Online]. Available:http://focus.tij.co.jp/jp/lit/ug/swru038/swru038.pdf
[12]C.-Y. Zheng; Y.-C. Huang; J.-C. Chiu,”Design and Implementation of Sequential Repair Backup Routing Protocol for Wireless Mesh Network,” In Proc. National Computer Symposium Conf. NCS’11, Chia-Yi, Taiwan, ROC, Dec. 2011.
[13]Jih-ching Chiu, Yao-Chin Huang,”Network Initialization Protocol for Smart Grid,” 2012 Taiwan Power Electronics Conference & Exhibition(TPECE).
[14]Jih-Ching Chiu, Kai-Ming Yang, Yao-Chin Huang, Ming-Shiou Wu, "Dynamic Multi-channel Multi-path Routing Protocol for Smart Grid," The 3rd FTRA International Conference on Computer Science and its Applications (CSA 2011) at Korea, Dec. 2011.
[15]“Modicon Modbus Protocol Reference Guide”, http://modbus.org/docs/PI_MBUS_300.pdf