無線感測器網路(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.