近年來無線網狀網路在嵌入式平台上的應用已經越來越廣泛。基於能量的考量下，如何能夠以較低的能量消耗且同時擁有穩定的資料傳輸也就漸漸的成為一個重要的課題。為了使嵌入式平台達到低功耗且擁有穩定的長距離資料傳輸，必須擁有合適的路由協定。本論文提出具循序修復與備用路由建立之協定(Ad Hoc On-Demand Distance Vector Routing- Sequential Repair and Backup Routing Protocol, AODV-SRBR Protocol)，可有效降低網路中節點的收發次數和建立穩定的連線。在提出的路由協定中，網路中的節點可經由解讀封包內的路徑資訊來建立出多條路由資訊，藉由完整的路由資訊可有效降低發送路由請求封包，在路徑斷裂時可利用循序修復或選擇備用路由來回復資料傳輸。在本論文中我們利用硬體實作來驗證我們的路由協定確實可在一般環境下建立多跳的連線並傳輸資料，並由NS2模擬工具來對AODV-SRBR進行效能測試並和AODV做比較，由測試結果發現在同樣的接收率之下，我們的路由協定能夠以較少的路徑請求、較少的路由維護封包、較少的收發次數來達到相同的傳輸效率。未來我們希望使用此路由協定的嵌入式平台，利用其穩定的連線、低功耗和多跳傳輸的特性，來完成建立大型感測網狀網路的目標。

In recent years, the applications of wireless mesh network in the embedded systems have become more widely. It''s an important issue that how to consume lower energy and transfer data stably based on energy considerations. The embedded systems must have the appropriate routing protocol for low power consumption and stable long-distance data transmission. In this paper, a routing protocol is proposed with sequential repair and backup routing protocol(Ad Hoc On-Demand Distance Vector Routing-Sequential Repair and Backup Routing Protocol, AODV-SRBR Protocol), that can reduce the number of transceivers and have a stable connection. In the proposed routing protocol, the node of network can create multi-route message through decoding the path information of packets. Using a complete routing information can reduce the number of route request packets efficiently. when the link is broken, the proposed protocol can repair the data transmission by sequential repair or select backup routing. In this paper, we implement the routing protocol to verify a multi-hop connection and data transfer in the general environment. The performance of AODV-SRBR and AODV is compared and simulated by NS2. The proposed routing protocol can achieve same transmission efficiency in the fewer route request packets, fewer maintance packets and fewer transmit and receive times according to the simulation result. By stable connection、low power consumption and multi-hop data transfer, we expect that the proposed routing protocol on the embedded systems platform can be extended in large sensor mesh network.

目 錄
誌謝 i
摘要 ii
Abstract iii
目 錄 iv
圖目錄 vii
表目錄 xii
第一章 簡介 1
1-1 研究動機 1
1-2 研究目的 1
1-3 論文架構 2
第二章 相關研究 3
2-1 Zigbee 協定 3
2-1-1 實體層 3
2-1-2 MAC層 5
通道存取方式 5
超框(Superframe) 6
資料傳輸模式 9
框結構 12
2-1-3 網路拓撲 17
星型拓撲(Star Topology) 17
網狀拓撲(Mesh Topology) 18
2-2 路由策略研究與分析 19
2-2-1 路由策略簡介 19
2-2-2 DSDV 20
2-2-3 DSR 21
2-2-4 TORA 22
2-2-5 AODV 24
2-2-6 AODV-BR[12] 26
2-2-7 路由策略比較與分析 27
第三章 AODV-SRBR 29
3-1 路由建立 30
3-1-1 封包格式 30
RREQ(Route Request) 30
RREP(Route Reply) 32
RERR(Route Error) 33
資料傳輸封包 34
3-1-2 鄰居表(Neighbor Table) 35
3-1-3 路由表(Routing Table) 35
3-1-4 路由請求(Route Request) 36
3-1-5 路由回應(Route Reply) 40
3-1-6 決定路由 42
3-2 路由維護 45
3-3 資料傳輸 49
3-4 封包傳遞延遲分析 51
第四章 實作平台和模擬平台介紹 52
4-1 實作平台 52
4-2 模擬平台 57
4-2-1 NS2介紹 57
4-2-2 Mobile Node 模組 60
4-2-3 在NS2上實現循序修復與備用路由建立協定 62
第五章 資料分析與探討 65
5-1 實作分析 65
5-2 模擬分析 71
5-2-1 模擬參數 71
5-2-2 效能測試 73
封包接收率(Packet Deliver Ratio, PDR 74
端對端延遲(End-to-End Delay) 75
路由請求封包數 76
路由維護封包數 77
所有節點的收發次數 80
特殊情況測試 83
第六章 結論 86
參考文獻 87

[1]Akyildiz Ian F., Xudong Wang, “A survey on wireless mesh networks,” Communications Magazine, IEEE Volume: 43 , Issue: 9, pp. S23-S30, Sept. 2005.
[2]ZigBee Alliance, http://www.zigbee.org/
[3]IEEE Std 802.15.4™-2006
[4]Perkin, Charles E. and Bhagwat, Pravin, “Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobil Computers,” In Proc, ACM SIGCOMM Conference (SIGCOMM 94), pages 234-244, August 1993
[5]David B. Johnson, David A. Maltz, and Yih-Chun Hu, “The Dynamic Source Routing Protocol for Mobile Ad Hoc etworks(DSR),” <draft-ietf-manet-dsr-10.txt> Internet-draft, 19 July 2004.
[6]C. E. Perkins and E. M. Royer, “Ad Hoc On-Demand Distance Vector Routing,” Second IEEE Workshop on Mobile Computing Systems and Applications, pp. 90-100, Feb. 1999.
[7]C. E. Perkins, Royer, and S. Das, “Ad Hoc On-Demand Distance Vector (AODV) Routing,” Internet Draft, draft-ietf-manet-aodv -13.txt, February 2003.
[8]V.D. Park and M.S. Corson, “Temporally-Ordered Routing Algorithm (TORA) Version 1,” IETS Internet draft (draft-ietfmanet-tora-spec-04.txt), July 2001.
[9]V.D. Park, J.P. Macker and M.S. Corson, “Applicability of the temporally-ordered routing algorithm for use in mobile tactical networks[C],” Proceedings of MILCOM 98. Boston Marseilles: IEEE, 1998: 426-430.
[10]Z. J. Haas and M. R. Pearlman, “The Zone Routing Protocol(ZRP)for Ad Hoc Networks,” Internet draft, draft-zone-routing-protocol-01.txt, Aug, 1998.
[11]M. R. Pearlman, Z. J. Haas and Syed I. Mir, “Using Routing Zones to Support Route Maintenance in Ad Hoc Networks,” Wireless Communications and Networking Conference, 2000. WCNC. 2000 IEEE, 2000.
[12]S. J. Lee and M. Gerla, “AODV-BR: Backup Routing in Ad Hoc Networks,” Proceedings of IEEE WCNC 2000, Chicago, IL, Sep. 2000.
[13]Tsung-Chuan Huang, Sheng-Yu Huang and Lung Tang, “AODV-Based Backup Routing Scheme in Mobile Ad Hoc Networks,” in proc. IEEE 2010 International Conference on Communications and Mobile Computing, 2010 IEEE.
[14]P Chenna Reddy, Dr. P. Chandrasekhar Reddy, “Performance Analysis of Ad Hoc Network Routing Protocols,” Academic Open Internet Journal, ISSN 1311-4360, Vol-17,2006.
[15]S. Gowrishankar, S.K. Sarkar, and T.G. Basavaraju, “Performance Analysis of AODV, AODVUU, AOMDV and RAODV over IEEE 802.15.4 in Wireless Sensor Networks,” In Proc. IEEE International Conference on Computer Science and Information Technology (ICCSIT), August 2009.
[16]Asma Toteja, Raynees Gujral, Sunil Thalia, “Comparative performance Analysis of DSDV, AODV and DSR Routing Protocols in MANETs, using NS2,” 2010 International Conference on Advances in computing Engineering, IEEE Computer Society.
[17]Tao Yang, et al. “Performance Behavior of AODV, DSR and DSDV Protocols for Different Radio Models in Ad-Hoc Sensor Networks,” In Proceeding International Conference on Parallel Processing Workshops, Sept. 2007.
[18]Huang R., Zhuang Y., Cao Q., “Simulation and Analysis of Protocols in Ad Hoc Network,” 2009 International Conference on Electronic Computer Technology c 2009 IEEE.
[19]Vikas Singla, Rakesh Singla and Ajay Kumar, “Performance Evaluation and Simulation of Mobile Ad-hoc Network Routing Protocols,” International Journal of Engineering and Information Technology ,Volume 1 No. 1 October 2009.
[20]Shiau-Wen Yu, “A Design of Zigbee Routing For Street Light Control System,” The Master Thesis of Department of Electrical Engineering, National SunYat-Sen University, Taiwan, July 2009.
[21]Microchip . (2010). dsPIC30F4011/4012Data Sheet [Online]. Available: http://ww1.microchip.com/downloads/en/DeviceDoc/70135G.pdf
[22]Microchip .(2009, Jan 1) . MPLAB R 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
[23]CHIRKAL TECHNOLOGY CO., LTD. http://www.chirkal.com.tw
[24]TEXAS INSTRUMENTS, http://www.ti.com/
[25]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
[26]Texas Instruments. (2006). IAR IDE User Manual Rev. 1.2 [Online]. Available:http://focus.tij.co.jp/jp/lit/ug/swru038/swru038.pdf
[27]Network Simulator 2, http://nsnam.isi.edu/nsnam/index.php/Main_Page
[28]An Awk Primer, http://www.vectorsite.net/tsawk.html
[29]Nam: Network Animator, http://www.isi.edu/nsnam/nam/
[30]OTcl, http://otcl-tclcl.sourceforge.net/otcl/
[31]Kevin Fall and Kannan Varadhan, The ns Manual, January 2009, http://www.isi.edu/nsnam/ns/doc/ns_doc.pdf
[32]Teerawat Issariyakul and Ekram Hossain, Introduction to Network Simulator NS2, pp. 38-39, USA: Springer, July 2008.
[33]Charlotte See. (2007, Dec 21). Programming Output Power on CC243x [Online]. Available: http://focus.ti.com/lit/an/swra171/swra171.pdf
[34]Kai-ming Yang, Ming-Shiou Wu, Po-Hsun Pan and Jih-ching Chiu,"Dynamic Multi-channel Multi-path Routing Protocol for Wireless Mesh Networks," 2010 International Computer Symposium (ICS), pp. 865-868, Dec. 2010.