臺灣博碩士論文加值系統

　　不穩定的環境情況以及能量限制是無線感測網路中的兩個挑戰，所以在設計無線感測網路的繞送演算法中兩個需要關心的議題是錯誤容忍以及能量有效的利用。所以在本篇文獻中我們提出了一個可靠且能量有效利用的繞送演算法稱為在叢集式無線感測網路中的封包傳輸可靠以及能量意識的路徑挑選演算法，該演算法可以增進整體網路存活時間以及同時保證資料傳送的可靠度，藉由多路徑傳輸以及李德－所羅門碼來對資料進行保護來達到高可靠度的資料傳輸；實現的部分則是透過建立在最佳李德－所羅門碼的編碼率以及多路徑繞送的負載平衡方程式來達成，另外該演算法藉由將原始問題轉換成背包問題的來看待，所以提出兩個不同的負載平衡方程式，分別是透過貪婪演算法以及動態規劃來針對不同的目的以及通道環境來進行應用。最後，評估該演算法的整體網路存活時間以及資料傳送的可靠度則是透過了模擬的方式來進行。

Unstable environmental condition and energy constraint are the fundamental challenges for the wireless sensor networks (WSN). Two major concerns for routing protocol design in WSN are error-tolerance and energy efficiency. In this paper, we proposed a reliable and energy efficient routing protocol called Packet Transmission Reliability and Energy Awareness Path Selection Algorithm (PTREAPSA) for the Clustering WSN. In order to prolong network lifetime while guaranteeing the integrity of collected data, PTREAPSA improves performance in terms of network lifetime and data reliability. PTREAPSA uses multiple paths to route data, and on each path the Reed-Solomon code (RS-code) and scrambling techniques are used to improve the data reliability. In particular, the proposed PTREAPSA can determine the optimal RS-code rate on each path, and use multiple paths to relay data with the consideration of load balancing and reliability. PTREAPSA are formulated as a knapsack problem and solved by the greedy algorithm and dynamic programming techniques. Two different load balancing functions are applied to different environmental situations. The performances of PTREAPSA in terms of network lifetime and data reliability are evaluated and the analytical model is also verified by simulation.

誌謝辭 I
摘要 II
Abstract III
目錄 IV
圖目錄 VI
方程式目錄 VIII
第一章　緒論 1
1.1 研究動機 1
1.2 研究目的 2
1.3 論文架構 3
第二章　相關研究 4
第三章　相關背景介紹 8
3.1 Zigbee 規格及協定 8
3.1.1 超級訊框架構 ( Superframe Structure ) 10
3.1.2 訊息框架之種類 11
3.1.2.1 資料訊框( Data Frame ) 12
3.1.3 網路拓樸方式( Network Topologies ) 13
3.2 LEACH演算法 15
3.2.1 叢集頭挑選方法 16
3.2.2 一階層之無線電模型( First Order Radio ) 20
3.3 路徑損失模型( Path Loss Model ) 21
3.3.1 位元錯誤率( Bit Error Rate ) 23
3.4 Reed-Solomon 編碼[26] 24
3.4.1 場(Field)、有限場(Finite Field)以及二元場(Binary Field) 25
3.4.2 本質多項式以及加洛瓦場的建置 26
3.4.2.1 二元多項式( Binary Polynomial ) 26
3.4.2.2 二元不可分解多項式( Binary Irreducible Polynomial ) 27
3.4.2.3 本質多項式( Primitive Polynomial ) 27
3.4.2.4 加洛瓦場建構( Construction of Galois Field ) 27
3.4.3 RS編碼的特性以及性能 28
3.5 封包交織編碼 (Packet Interleaving) 29
第四章　系統架構與方法 32
4.1 系統模型 34
4.2 最佳化李德－所羅門碼之編碼率 38
4.3 建構於貪婪演算法 (Greedy Algorithm Based) 41
4.4 建構於動態規劃 (Dynamic Programming Based) 43
4.5 複雜度比較 47
第五章　模擬結果與討論 48
第六章　結論與未來工作 57
參考文獻 58

[1]P. Corke, T.Wark, R. Jurdak, D. Moore, and P. Valencia, “Environmental wireless sensor networks,” Proceedings of the IEEE: Vol.98, Issue.11, 1903-1917, 2010.
[2]J. Yick, B. Mukherjee, D. Ghosal, “Wireless sensor network survey,” The International Journal of Computer and Telecommunications Networks, Vol. 52, No.12 pages 2292-2330, 2008.
[3]Y. Yao and J. E. Gehrke, "Query processing in sensors networks,"　Proc. 1st Biennial Conf. Innovative Data Systems Research (CIDR 2003), 2003.
[4]H. Alwan and A. Agrarwal, “A Survey on Fault Tolerant Routing Techniques in Wireless Sensor networks,”International Conference on Sensor Techniligies and Aplications:366-371, 2009.
[5]H. Wen, C. Lin, F. Ren, Y. Yue and X. Huang, ”Retransmission or Redundancy: Transmission Reliability in Wireless Sensor Networks,”IEEE international Conference on Mobile Adnoc and Sensor Systems:1-7, 2007.
[6]P. Djukic, S. Valaee, “Reliable Packet Transmission in Multipath Routing Wireless Networks”, IEEE Transaction on Mobile Computing, VOL.5, No.5, 548-559, 2006.
[7]J.S. Ahn, J.H. Yoon and K.W. Lee, “Performance and Energy Consumption Analysis of 802.11 with FEC Codes over Wireless Sensor Networks,”Jounal of Communication and Network: Vol.9, Issue.3 2012.
[8]J.Wu, S. Dulman, P. Havinga, and T. Nieberg, “Multipath Routing with Erasure Coding forWireless Sensor Networks,”15th Annual Workshop on Circuits, Systems and Signal Processing: 181-188, 2004.
[9]N.A. Pantazis, S.A. NikoLidakis and D.D. Vergados, “Energy-Efficient Routing Protocols in Wireless Sensor Networks: A Survey,”IEEE Communication Surveys & Tutorials: Vol.15, Issue.2, 551-591, 2013.
[10]W. An, H. Luo, S. Ci and J. Lin,”The Maximized Relay Capacity and Optimal Data Transmission for Wireless Sensor Networks,”Global Telecommunication Conference: 1-5, 2011.
[11]F. Bouabdallah, N. Bouabdallah and R. Boutaba, “On Balancing Energy Consumption in Wireless Sensor Networks,”IEEE Transactions on Vehicular Technology: Vol.58, No.6, 2909-2924, 2008.
[12]Y.M. Lu and V.W.S.Wong, “An Energy-Efficient Multipath Routing Protocol for Wireless Sensor Networks,”IEEE 64th Vehicular Technology Conference: 1-5, Fall, 2006.
[13]P. Djukic and S. Valaee,”Minimum Energy Fault Tolerant Sensor Networks,”IEEE Global Telecommunication Conference Workshops: 22-26, 2004.
[14]P. Djukic and S. Valaee,“Maximum Network Lifetime in Fault Tolerant Sensor Networks,”IEEE Global Telecommunication Conference: Vol.5, 3102-3106, 2005.
[15]LAN/MAN Standards Committee of the IEEE Computer Society, “802.15.4-2006-IEEE Standard for Information technology-- Local and metropolitan area networks-- Specific requirements-- Part 15.4: Wireless Medium Access Control (MAC) and Physical Layer (PHY) Specifications for Low Rate Wireless Personal Area Networks (WPANs), ”IEEE-SA Standards Board, page1-320, 2006.
[16]ZigBeeTM Alliance, “Zigbee Architecture Overview,”Embedded Systems Conference, 2006.
[17]J.S.Liu and C.H.R.Lin, “Bandwidth Constrained Energy Efficient Transmission Protocol,”IEICE Trans. Commun, Vol.E86-B, No.10,pp.3039-3049, Oct. 2003.
[18]M.J. Handy, M. Haase and D. Timmermann, “LEACH-C：Low Energy Adaptive Clustering Hierarchy with Deterministic Cluster-head Selection,”Mobile and Wireless Communications Network, pp. 368-372, 2002.
[19]W. Heinzelman, A. Chandrakasan, and H. Balakrishnan, “Energy- Efficient Communication Protocol for Wireless Microsensor Networks,”Proc. Hawaii Conf. System Sciences, Jan. 2000.
[20]W. B. Heinzelman, A. P. Chandrakasan, and H. Balakrishnan, “An Application-Specific Protocol Architecture for Wireless Microsensor Networks,”IEEE Trans. Wireless Commun, Vol. 1, No. 4, pp. 660–70, Oct. 2002.
[21]李志鵬、江弘志、林垂彩，“WCDMA 基頻訊號處理與系統設計實務”，滄海書局、 2007.
[22]T. Rappapon, “*Wkless Communications: Principles and Reclice:,” PrrnnCc Hall, 19%. Znd edition 2002.
[23]"ASH Transceiver Designer's Guide, "RFM-TRIMM Tronsceive:, ”Novcmbel 2001.
[24]Y. Sankarasubramaniam. I.F. Akyildiz, and S.W. McLaughlin, “Energy Efficiency Based Packet Size Optimization in Wireless Sensor Networks,” in Proc. First IEEE 2003International Workshop on Sensor Network Protocols and Application, 2003.
[25]H. Karvonen, Z. Shelby, and C. Pomalaza-Ráez, “Coding for energy efficient wireless embedded networks,” in 2004 International Workshop on Wireless Ad-hoc Networks: 300-304, 2004.
[26]P. Sweeney. “Error Control Coding Error Control Coding: From Theory to Practice,” John Wiley & Sons, LTD, 2002.
[27]B. Vucetic and J. Yuan, “Turbo Codes: Principles and Applications,” Kluwer, Dordrecht. 2000.
[28]W. R. Heinzelman, A. P. Chandrakasan, and H. Balakrishnan, “Energy-Efficient Communication Protocol for Wireless Microsensor Networks,” in Proc. 33rd Annual Hawaii International Conference on System Seciences, Jan. 2000.
[29]L. Rizzo, “Effective erasure codes for reliable computer communication protocol, ” in ACM Computer communication Review, VOL.27 No.2, pp.24-36, April, 1997.
[30]J. H Chang, L. Tassiulas, “Energy Conserving Routing in Wireless Ad-hoc Networks, ”in Proc. Nineteeth Annual Joint Conference of the IEEE Computer and Communications Societies, INFOCOM 2000, Vol. 1, 22-31, 2000.