淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-1606200618551400
中文論文名稱 無線感測器網路之階層式多重選擇路由路徑協定
英文論文名稱 A Hierarchical Multiple-Choice Routing Path Protocol for Wireless Sensor Networks
校院名稱 淡江大學
系所名稱(中) 資訊工程學系博士班
系所名稱(英) Department of Computer Science and Information Engineering
學年度 94
學期 2
出版年 95
研究生中文姓名 蔡智孝
研究生英文姓名 Chih-Hsiao Tsai
電子信箱 890190092@s90.tku.edu.tw
學號 890190092
學位類別 博士
語文別 英文
口試日期 2006-05-29
論文頁數 100頁
口試委員 指導教授-王英宏
委員-楊熙年
委員-廖弘源
委員-蔣定安
委員-許輝煌
中文關鍵字 無線感測器網路  階層式多重選取路由路徑  能源效率  叢集協定  資料聚集 
英文關鍵字 wireless sensor networks  hierarchical multiple-choice routing path  energy-efficient  clustering protoco  data aggregation 
學科別分類 學科別應用科學資訊工程
中文摘要 無線感測器網路(Wireless Sensor Networks, WSNs)是由大量的感測器節點(Sensor Nodes)所組成的網路,可以讓使用者藉由將個別不同節點所傳送之資料加以結合來達到準確地監控遠端環境的目的。所以這樣的網路需要能提供有能源效率(Energy-Efficient)和較小延遲(Lower Latency)的通訊協定。因此,為了延長感測器節點的生命週期,設計ㄧ個有效率的路由協定是相當重要的。目前已經有很多方法,像是直接通訊(Direct Communication)、平坦式泛播(Flat Flooding)、叢集式協定(Clustering Protocol)等,都已經被提出並用來在隨意散佈的感測器節點上傳遞資料。
本篇論文提出一個階層式多重選擇路由路徑協定(Hierarchical Multiple-Choice Routing Path Protocol, HMRP),這個路由協定經由多重路徑、能源平均、以及資料聚集的方式收集資料,來達到對於系統生命週期和資料成功傳送率有比較好的效能。在設計這個協定時,主要是以滿足無線感測器網路中感測器節點將感應到的資料自發的傳回給資料收集中心(Sink)的需求為目標。所以我們以資料收集中心為樹根,藉由發送自身的節點值(Hop Value)來找出子節點,每一個感測器節點都利用同樣的方式找出自己的子節點。在HMRP中每個節點使用候選資訊表格(Candidates Information Table)紀錄相關父親節點,避免要週期性的以泛播的方式來達成資訊更新。此外,這個樹狀的結構將會在有節點失效或是加入新節點時自動的重新配置(Reconfigure)。由模擬實驗的結果顯示,HMRP可以比一般提出的多點(Multi-hop)叢集式或樹狀基礎的方法更有效率的增加系統生命週期和資料成功傳輸率。
英文摘要 The wireless sensor networks (WSNs), a network comprising the huge number of sensor nodes, allow users to monitor a remote environment accurately by combining the data intelligently from the individual nodes. These networks require robust wireless communication protocols that are energy-efficient and provide lower latency. Therefore, in order to prolong the lifetime of the sensor nodes, designing efficient routing protocols is critical. Several approaches, including direct communication, flat, and clustering protocols, have been proposed to transmit data in randomly deployed sensor nodes.
In this thesis, we present a Hierarchical Multiple-Choice Routing Path Protocol (HMRP), a routing protocol for collecting data over multi-path, energy-balancing, and data aggregation to achieve good performance in terms of system lifetime and data delivery ratio. The design of the protocol aims to satisfy the requirements of sensor networks that every sensor transmits sensed data to the sink spontaneously. The sink constructs hierarchical tree by broadcasting its hop value to find the child nodes. Other nodes discover the child nodes in turn by the same way. The HMRP uses Candidates Information Table to avoid flooding and periodic updating of routing information. Moreover, the tree will automatically reconfigure according to nodes failure or adding the new nodes. The simulation results show that HMRP can increase the system lifetime and data delivery ratio by comparing with other general-purpose multi-hop clustering or tree-based approaches.
論文目次 Contents

Acknowledgements viii
中文摘要 x
Abstract xi
List of Figures xiv
List of Tables xvi
1 Introduction 1
2 Related Work 6
2.1 Wireless Sensor Networks (WSNs) 6
2.2 Classification of Routing Protocols in WSNs 12
2.3 Network-Structure-Based Protocols 13
2.3.1 Flat Routing Protocols 13
2.3.2 Hierarchical Routing Protocols 18
2.3.3 Location-Based Routing Protocols 24
2.4 Protocol-Operation-Based Protocols 26
2.4.1 Multipath Routing Protocols 26
2.4.2 Query-Based Routing Protocols 27
2.4.3 QoS-Based Routing Protocols 28
2.5 Summary 29
3 Hierarchical Multiple-Choice Routing Path Protocol 30
3.1 Network Environments and Assumptions 31
3.2 Three Phases of HMRP 33
3.2.1 Layer Construction Phase (LCP) 33
3.2.2 Data Dissemination Phase (DDP) 36
3.2.3 Network Maintenance Phase (NMP) 40
3.3 Algorithms of HMRP 43
3.3.1 Algorithm of Layer Construction Phase (LCP) 43
3.3.2 Algorithm of Data Dissemination Phase (DDP) 45
3.3.3 Algorithm of Network Maintenance Phase (NMP) 48
3.4 Data Aggregation and Fusion 50
4 Simulation Results and Analysis 52
4.1 Simulation Environment 52
4.2 Results and Analysis 54
5 Conclusion and Future Work 59
5.1 Conclusion 59
5.2 Future Work 60
Bibliography 61
Appendix A. Publication List 65
Appendix B. “A Hierarchical Multiple-Choice Routing Path Protocol
for Wireless Sensor Networks” JOURNAL OF
INFORMATION SCIENCE AND ENGINEERING 67
Appendix C. “HMRP:Hierarchy-Based Multipath Routing Protocol
for Wireless Sensor Networks” TAMKANG
JOURNAL OF SCIENCE AND ENGINEERING 83

List of Figures

Figure 1 1 Mobile Ad Hoc Networks (MANETs). 2
Figure 2 1 Wireless Sensor Networks (WSNs) architecture. 7
Figure 2 2 The components of a sensor node. 9
Figure 2 3 Routing protocols in WSNs. 13
Figure 2 4 Sensor Protocols for Information via Negotiation. 15
Figure 2 5 Directed diffusion. 16
Figure 2 6 An example of rumor routing optimization. 17
Figure 2 7 Flowchart of LEACH. 19
Figure 2 8 PEGASIS data transmission. 20
Figure 2 9 PEDAP minimum spanning tree based routing. 21
Figure 2 10 State transition diagram in HAR. 22
Figure 2 11 The position of the SPAN algorithm. 24
Figure 2 12 State transition diagram in GAF. 25
Figure 2 13 SPEED protocol. 29
Figure 3 1 Example of sensor network environment. 32
Figure 3 2 Layer construction flooding. 34
Figure 3 3 An action flow when node received LCREQ packet. 36
Figure 3 4 Layer construction result.. 37
Figure 3 5 An action flow when a node starts to transmit the data packet. 38
Figure 3 6 Data dissemination Phase. 39
Figure 3 7 An action flow when node received CPREQ packet. 41
Figure 3-8 (a) New node broadcasts CPREQ (b) Neighbor nodes reply LCREQ 42
Figure 3-8 (c) New node transmits LCREQ to lower level nodes. 43
Figure 3 9 Parent reply a RDACK packet with ER value. 51
Figure 4 1 The system lifetime of HMRP and other protocols. 55
Figure 4 2 The average energy dissipation of HMRP and other protocols. 56
Figure 4 3 The number of data message received by sink. 57
Figure 4 4 Average energy dissipation over different network size. 58


List of Tables

Table 2 1 Hierarchical vs. flat topologies routing. 23
Table 3 1 The main protocol packets of HMRP. 31
Table 4 1 Parameters for simulation. 54

參考文獻 [Akyildiz2002] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “A survey on sensor networks,” IEEE Communication Magazine, 40(8), Aug. 2002, pp.102–114.
[Braginsky2002] D. Braginsky and D. Estrin, “Rumor Routing Algorithm for Sensor Networks,” Proceedings of 1st Workshop Sensor Networks and Applications, Oct. 2002, pp. 22-31.
[Callaway2003] Edgar H. Callaway. “Wireless Sensor Networks: Architectures and Protocols,” Auerbach Publications, 2003.
[Chen2002] B. Chen et al., “SPAN: an Energy-efficient Coordination Algorithm for Topology Maintenance in Ad Hoc Wireless Networks,” Wireless Networks, Volume 8, Issue 5, Sept. 2002, pp. 481–494.
[Chang2004] J.-H. Chang and L. Tassiulas, “Maximum Lifetime Routing in Wireless Sensor Networks,” IEEE/ACM Transactions on Networking, Volume 12, Issue 4, Aug. 2004, pp. 609-619.
[He2003] T. He, J. A. Stankovic, C. Lu, and T. Abdelzaher, “SPEED: A Stateless Protocol for Real-time Communication in Sensor Networks,” Proceedings of Int’l. Conference Distribute Computer System, Providence, RI, May 2003.
[Heidemann2002] Wei Ye, Heidemann, J. and Estrin, D. “An energy-efficient MAC protocol for wireless sensor networks,” Proceedings of the 21st Annual Joint Conference of the IEEE Computer and Communications Societies, Volume 3, 23-27 June 2002, pp. 1567-1576.
[Heinzelman2000] Heinzelman, W.R., Chandrakasan, and Balakrishnan, H. “Energy-efficient communication protocol for wireless microsensor networks,” Proceedings of IEEE Annual Hawaii International Conference on Systems Sciences, 4-7 Jan. 2000, pp. 3005–3014.
[Heinzelman2002] W. B. Heinzelman, A. P. Chandrakasan, and H. Balakrishnan, “An Application-Specific Protocol Architecture for Wireless Microsensor Networks,” IEEE Transactions on Wireless Communications, Volume 1, Issue 4, Oct. 2002, pp. 660-670.
[Hill2002] J. Hill and D. Culler. “Mica: a wireless platform for deeply embedded networks,” IEEE Micro, Volume 22, Issue 6, Nov.-Dec. 2002, pp. 12–24.
[Hill2000] J. Hill, R. Szewczyk, A. Woo, S. Hollar, D. Culler, and K. Pister. “System architecture directions for networked sensors,” Proceedings of the Ninth international Conference on Architectural Support for Programming Languages and Operating Systems, 12-15 Nov. 2000, pp. 93–104.
[Hüseyin2003] Hüseyin Özgür Tan and Ibrahim Körpeoglu, “Power Efficient Data Gathering and Aggregation in Wireless Sensor Networks,” ACM SIGMOD Record, Volume 32, Issue 4, Dec. 2003, pp. 66-71.
[Intanagonwiwat2003]C. Intanagonwiwat, R. Govindan, D. Estrin, J. Heidemann, and F. Silva, “Directed Diffusion for Wireless Sensor Networking,” IEEE/ACM Transactions on Networking, Volume 11, Issue1, Feb. 2003, pp. 2–16.
[Iwata1999] A. Iwata, C. C. Chiang, G. Pei, M.Gerla, and T. W. Chen, “Scalable Routing Strategies for Ad Hoc Wireless Networks,” IEEE Journal on Selected Areas in Communications, Special Issue on Ad Hoc Networks, Aug. 1999, pp. 1369-1379.
[Johnson1996] D. B. Johnson and D. A. Maltz, “Dynamic Source Routing in Ad-Hoc Wireless Networks,” Mobile Computing, edited by T. Imielinski and H. Korth, Eds., Kluwer, 1996, pp. 153-181.
[Kalpakis2003] K. Kalpakis, K. Dasgupta, and P. Namjoshi. “Efficient algorithms for maximum lifetime data gathering and aggregation in wireless sensor networks,” Computer Networks: The International Journal of Computer and Telecommunications Networking, Volume. 42, Issue 6, Aug. 2003, pp. 697 – 716.
[Karaki2004] Al-Karaki, J.N. and Kamal, A.E. “Routing techniques in wireless sensor networks: a survey,” IEEE Wireless Communications, Volume. 11, Issue 6, Dec. 2004, pp. 6-28.
[Karp2000] Brad Karp and H. T. Kung, “GPSR: Greedy Perimeter Stateless Routing for Wireless Networks,” Proceedings of the ACM MOBICOM, Aug. 2000, pp. 243-254.
[Kulik2002] J. Kulik, W. R. Heinzelman, and H. Balakrishnan, “Negotiation-Based Protocols for Disseminating Information in Wireless Sensor Networks,” Wireless Networks, Volume 8, Issue 2/3, March-May 2002, pp. 169–185.
[Lindsey2002] Lindsey, S. and Raghavendra, C.S. “PEGASIS: Power Efficient Gathering in Sensor Information System,” Proceedings of IEEE Aerospace Conference, 9-16 Mar. 2002, Volume. 3, pp. 1125–1130.
[Muruganathan2005] Muruganathan, S.D., Ma, D.C.F., Bhasin, R.I., and Fapojuwo, A.O. “A Centralized Energy-Efficient Routing Protocol for Wireless Sensor Networks,” IEEE Communication Magazine, Volume. 43, Issue 3, Mar. 2005, pp. S8-13.
[Niwat2005] Niwat Thepvilojanapong, Tobe, Y., and Sezaki, K. “HAR: Hierarchy-Based Anycast Routing Protocol for Wireless Sensor Networks,” Proceedings of IEEE Symposium on Applications and the Internet, 31 Jan.– 4 Feb. 2005, pp. 204-212.
[Perkins1994] C. E. Perkins and P. Bhagwat, “Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers,” ACM SIGCOMM ’94 Computer Communications Review, Vol. 24, No. 4, Aug. 1994, pp. 234-244.
[Perkins1999] C. E. Perkins and E. M. Royer, “Ad-hoc On-Demand Distance Vector Routing,” Proceedings of the 2nd IEEE Workshop Mobile Computer System and Applications, Feb. 1999, pp. 90-100.
[Qiangfeng2004] Qiangfeng Jiang and Manivannan, D. “Routing protocols for sensor networks,” Proceedings of IEEE Consumer Communications and Networking Conference, 5-8 Jan. 2004, pp. 93-98.
[Royer1999] E. M. Royer and C.-K. Toh, “A review of current routing protocols for ad hoc mobile wireless networks,” IEEE Personal Communication, Volume. 6, Issue 2, Apr. 1999, pp. 46–55.
[Sohrabi2000] K. Sohrabi and J. Pottie, “Protocols for Self-Organization of a Wireless Sensor Network,” IEEE Personal Communication, Volume 7, Issue 5, Oct. 2000, pp. 16–27.
[Xu2001] Y. Xu, J. Heidemann, and D. Estrin, “Geography informed Energy Conservation for Ad-hoc Routing,” Proceedings of the 7th annual international conference on Mobile computing and networking, 2001, pp. 70–84.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2006-06-26公開。
  • 同意授權瀏覽/列印電子全文服務,於2006-06-26起公開。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2281 或 來信