臺灣博碩士論文加值系統

無線感測網路中的路由協定，大部分集中在節點的分佈均衡、節點電量平衡或是優化路由路徑使路徑是最短的，比較少考慮流量負載均衡問題。無線感測網路中的節點因為遭遇到過多的資料流量，使節點之間的負載產生不平衡，最後造成網路瓶頸，因此如何平衡網路中的負載減少網路瓶頸成為設計無線感測網路由協定的中重要關鍵。為了達到負載平衡和減緩網路瓶頸在資料密集的無線感測網路，本篇論文提出負載平衡路由 ( LBR ) 協定。負載平衡路由是基於階層式路由的設計連結節點與資料收集端 ( SINK )。負載平衡路由中包含階層式路由架構 ( LRC )、負載預估演算法 ( LEA )、傳輸平滑機制 ( STM ) 和路由維護 ( RM ) 四個部分。階層式路由架構提供節點擁有多個下一跳節點可以到達SINK且確保各節點到SINK的路徑是最短的，使負載平衡路由有擴展性、強健性及低成本。階層式路由架構 ( LRC ) 與負載預估演算法 ( LEA ) 的合作，達到本地負與全域負載平衡。傳輸平滑機制 ( STM ) 平滑下層節點的傳輸時間，減少短時間多節點的封包傳輸，使負載平衡路由擁有較好的網路傳輸效能。路由維護 ( RM ) 檢測和恢復路徑故障時，不須廣播任何錯誤訊息到整個網路，並能快速適應網路拓樸的改變，使負載平衡路由增強路由的強健性。本論文提出負載平衡路由與AOMDV以及AODV比較，透過模擬結果呈現負載平衡路由提供較好的負載平衡，也有較好的網路傳輸效能以及較好路由維護。

Routing in WSN usually focuses on balanced distribution of nodes, nodes energy balanced and optimizing routing paths to be the shortest, fewer considering traffic load balancing issues. In WSN, some nodes become bottleneck because of encountering excessive data flow. So how to balance the load of network becomes the key of design WSN routing protocol. To achieve load balancing and reduce network bottleneck in data-intensive WSN, we propose Load Balancing Routing (LBR) protocol for WSN. LBR is based on layer routing design to connect sensor nodes and SINK. LBR contains Layering Route Construction ( LRC ), Load Estimation Algorithm ( LEA ), Smooth Transmission Mechanism ( STM ) and Route Maintenance ( RM ). LRC provides multiple next-hop choices from nodes to SINK and ensures each route is shortest that makes LBR scalable, low-overhead and robust. Through the cooperation of LRC and LEA, local and global load-balancing is accomplished. STM reduces a multi-node packets transmission at short time, which provides LBR better network transmission performance. When RM detects and recovers route failures, it does not broadcasts any error message to whole network, and can quickly adapt to network topology changes. RM makes LBR enhanced robustness route. Compared with AODV and AOMDV, simulation results show LBR provides better load balancing than AOMDV and AODV. LBR also achieves better network transmission performance and route maintenance.

ABSTRACT I
目錄 II
表目錄 III
圖目錄 IV
第1章 緒論 Introduction 1
1.1. 研究背景 1
1.2. 研究動機 3
1.3. 研究目的 4
1.4. 論文架構 5
第2章 相關文獻 Related Work 6
2.1. 叢集式 ( Cluster ) 網路 6
2.2. 非叢集式 ( Non-Cluster ) 網路 9
第3章 負載平衡路由 LBR 12
3.1. 階層式路由架構 ( LRC ) 12
3.2. 負載預估演算法 ( LEA ) 20
3.3. 傳輸平滑機制 ( STM ) 26
3.4. 路由維護 ( RM ) 36
第4章 實驗結果 Experiment Results 38
4.1. 網路模擬器Network Simulator version 2 介紹 38
4.2. 環境參數 39
4.3. 流量負載平衡 40
4.4. 不可用節點 47
4.5. 網路傳輸效能 50
4.6. 討論 58
第5章 結論 Conclusion 59
參考文獻 References 60

[1]ZigBee Specification Version 1.0, Zigbee Alliance (2004), Dec. 2004.
[2]IEEE Standard for Part 15.4: Wireless Medium Access Control (MAC) and Physical Layer (PHY) Specifications for Low-Rate Wireless Personal Area Networks (LR-WPANs), IEEE standard 802.15.4, 2003.
[3]C.E. Perkins, E. Belding-Royer and S.R. Das, “Ad hoc on-demand distance vector (AODV) routing,” http://www.ietf.org/rfc/rfc3561.txt, RFC 3561, Jul. 2003.
[4]M. Radi, B. Dezfouli, K.A. Bakar, and M. Lee, “Multipath routing in wireless sensor networks: survey and research challenges,” Sensors (Basel, Switzerland), pp. 650-685, Dec. 2012.
[5]Y. Liao, H. Qi, and W. Li, “Load-Balanced Clustering Algorithm With Distributed Self-Organization for Wireless Sensor Networks,” IEEE Sensors Journal, vol. 13, no. 5, pp.1498-1506, May 2013.
[6]Y. Wu and W. Liu, “Routing protocol based on genetic algorithm for energy harvesting-wireless sensor networks,” IET Wireless Sensor Systems, vol. 3, no. 2, pp.112-118, Jun. 2013.
[7]J. Zhang and T. Yang, “Clustering Model Based on Node Local Density Load Balancing of Wireless Sensor Network,” in Proc. Int. Conf. Emerging Intelligent Data and Web Technologies (EIDWT) 2013, pp.273-276, Sep. 2013.
[8]R. Liu, Q. Guo, Y. Fu, and X. Kong, “A New Cluster Routing Strategy Based on ZigBee,” in Proc. Int. Conf. Web Information Systems and Mining (WISM) 2010, pp271-274, Oct. 2010.
[9]A. Bhatia and P. Kaushik, “A Clster Based Minimum Battery Cost AODV Routing Using Multipath Route for Zigbee,” in Proc. Int. Conf. Networks 2008, pp.1-7, Dec. 2008.
[10]N. Amini, S.G. Miremadi, and M. Fazeli, “A Hierarchical Routing Protocol for Energy Load Balancing in Wireless Sensor Networks,” in Proc. Can. Conf. Electrical and Computer Engineering 2007, pp.1086-1089, Apr. 2007.
[11]M. Hammoudeh, O. Aldabbas, S. Mount, S. Abuzor, M. Alfawair and S. Alratrout, “Algorithmic construction of optimal and load balanced clusters in Wireless Sensor Networks,” in Proc. Int. Conf. Systems Signals and Devices (SSD) 2010, pp.1-5, Jun. 2010.
[12]G. Gupta and M. Younis, “Performance evaluation of load-balanced clustering of wireless sensor networks,” in Proc. Int. Conf. Telecommunications 2003, vol. 2, pp.1577-1583, Mar. 2003.
[13]K. Huang, C. Tseng, J. Wang and T. Yang, “A Controller-Assisted Distributed (CAD) Load Balancing Scheme for Zigbee Networks,” in Proc. Int. Conf. Parallel Processing Workshop (ICPPW) 2011, pp.1-5, Sep. 2011.
[14]Y.-J. Chu, C.-P. Tseng, K.-C. Liao, Y.-C. Wu, F.-M. Lu, Y.-C. Wang, C.-L. Tseng, E.-C. Yang, and K.-Y. Ho, “The First Order Load-Balanced Algorithm with Static Fixing Scheme for Centralized WSN System in Outdoor Environmental Monitoring,” IEEE Sensor, pp.1810-1813, Oct. 2009.
[15]H. Dai and R. Han, “A Node-Centric Load Balancing Algorithm for Wireless Sensor Networks,” in Proc. IEEE Global Telecommunications Conf. GLOBECOM’03 , vol. 1, pp.548-552, Dec. 2003.
[16]H. Fariborzi and M. Moghavvemi, “EAMTR: energy aware multi-tree routing for wireless sensor networks,” IET Communications, vol. 3, no. 5, pp.733-739, May 2009.
[17]T.-P. Chung, T.-S. Lin, X.-Y. Zheng, P.-L. Yen and J.-A. Jiang, “A Load Balancing Algorithm Based on Probabilistic Multi-Tree for Wireless Sensor Networks,” in Proc. Int. Conf. Sensing Technology (ICST) 2011, pp.527-532, Dec. 2011.
[18]S.C. Huang and R.H. Jan, “Energy-aware, load balanced routing schemes for sensor networks,” in Proc. Int. Conf. Parallel and Distributed Systems 2004, pp.419-425, Jul. 2004.
[19]H. Lui, T. Hou, and W. Hou, “Dynamic Weight based Hierarchical Routing Protocol in Wireless Sensor Networks,” in Proc. Int. Conf. Electrical and Control Engineering (ICECE) 2011, pp.3905-3908, Sep. 2011.
[20]C. Diallo, M. Marot, and M. Becker, “Link Quality and Local Load Balancing Routing Mechanisms in Wireless Sensor Networks,” in Proc. Int. Conf. Telecommunications (AICT) 2010, pp.306-315, May 2010.
[21]M.K. Marina and S.R. Das, “Ad hoc on-demand multipath distance vector routing,” Wireless Communications and Mobile Computing, vol. 6, no. 7, pp. 969–988, Nov. 2006.
[22]Wikipedia, “ZigBee,” from http://en.wikipedia.org/wiki/ZigBee
[23]Wikipedia, “IEEE 802.15.4,” from http://en.wikipedia.org/wiki/IEEE_802.15.4
[24]Wikipedia, “Exponential Weighted Moving Average,” from http://en.wikipedia.org/wiki/Mving_average#Expinential_moving_averagee
[25]The Netowrk Simulator – ns-2, from http://www.isi.edu/nsnam/ns/
[26]K. Fall and K. Varadhan, “The ns Manual ( formerly ns Notes and Documentation ) ,” from http://www.isi/edu.nsnam/ns/doc/ns_doc.pdf, 2011.
[27]Wikipedia, “AWK,” from http://en.wikipedia.org/wiki/AWK
[28]D. Marandin, “Simulation of IEEE 802.15.4/ZigBee with Network Simulator-2 (ns-2) ,” form http://www.ifn.et.tu-dresden.de/~marandin/ZigBeeSimulation.html
[29]鄭立, Zigbee 開發手冊, 初版一刷, 全華圖書股份有限公司, 2008.
[30]程榮祥, 柯志亨, 鄧德雋和丁建文, NS2網路模擬實驗, 初版一刷, 學貫行銷股分有限公司, 2009.