我們在本篇論文提出一個透過多躍距收集資料的路由協定—BHAR(Bidirectional Hierarchy-based Anycast Routing)，和HAR做比較，BHAR加快了建構階層式路由樹及修復路由的速度，並改善其運作機制。在BHAR中，匯集節點及來源節點皆能建立階層式路由樹，各個節點僅需依靠對其自身的親節點及鄰居節點的認識加入路由樹；來源節點所建立的路由樹可藉由與其它相鄰路由樹的路由交換，學到至遠端匯集節點的路由，並透過中繼路由樹節點將資料送達最近的匯集節點；在不依靠位置資訊、不需遠端控制的情況下執行路由修復，同時做局部網路的最佳化調整，以避免定期及條件式重建網路拓樸對網路及資料傳輸所造成的衝擊，並改善HAR在路由修復上修復彈性較差及仍有可能發生迴圈的缺點。我們使用VC++對BHAR與HAR做效能比較，從模擬結果來看，BHAR在匯集節點與來源節點數目增加時，可減少一般節點加入路由樹的平均等待時間；總節點數及網路大小的增加對BHAR的效能衝擊也相對小很多；BHAR的可擴充性(scalable)也比HAR大許多；在修復路由的能力上，BHAR比HAR能容忍更多的節點故障，並維持有效的路由運作，大幅提高了網路的強健性(Robustness)；在節點因各種因素導致分佈不平均的情況下，BHAR在路由修復的能力上比HAR優秀甚多。

In this paper, we present Bidirectional Hierarchy-based Anycast Routing (BHAR), a routing protocol for collecting data over multi-hop. In comparative to HAR, BHAR speeds up and improve the mechanism to construct hierarchical trees and to repair the route. In BHAR, sinks and sources can initial to construct a hierarchical tree. By knowing only its own parent and neighbor, each node in BHAR can join a tree; a tree can learn the routes to a remote sink by exchanging its routes with its neighboring trees, and send data to the nearest sink by intermediate trees; each node can perform route repair without geographical information or being controlled remotely, and perform local network topology optimization simultaneously in order to prevent the impact to the network and to data communication by periodically and conditionally network reconstruction.
We evaluate the performance of BHAR by using VC++ and comparing with those of HAR. The simulation results demonstrate that the average waiting time for a node to join a tree decrease when the number of sinks and sources increase in BHAR. The impact of the increase of the node number and network size to the performance of BHAR is relatively small, which means the scalability is much better. BHAR can endure more nodes to be failed and maintain effective routing operation, which has improve the robustness of BHAR. BHAR achieves much higher performance on route repair in the situation of the unevenly distribution due to different factors.

目錄
第一章  緒論	1
1.1  研究背景	1
1.2  研究動機	1
1.3  研究目的及方法	3
1.4  論文架構	4
第二章  無線網路路由協定	6
2.1  無線感測網路簡介	6
2.2  RUMOR ROUTING	12
2.3  PEGASIS	15
2.4  MCFA	17
2.5  DD	18
2.6  SPIN	20
2.7  EDDD	22
2.8  LEACH	25
2.9  LLC	26
2.10  MECH	28
2.11  PCBRP & PCBRP-OPT	28
2.12  EDGE & HAR	31
2.13  HMRP	34
2.14  運作機制比較	36
第三章  新提出的路由協定	42
3.1  設計目標及假設前提	42
3.2	運作機制說明	44
3.2.1	建立網路拓樸	44
3.2.2	路由修復機制	53
3.3  新路由協定的運作特點	57
第四章  模擬與評比	63
4.1  模擬方式	63
4.2  效能指標	63
4.3  總節點數的影響	65
4.4  網路大小的影響	68
4.5  匯集節點密度的影響	81
4.6  反常態分佈對模擬結果的影響	82
4.7  控制封包產生數評比	92
第五章  結論	99
參考文獻	104
圖目錄
圖2.1：無線網路路由協定分類	7
圖2.2：使用與未使用叢集架構與聚集轉送資料	10
圖2.3：ROUMOR ROUTING運作機制說明	14
圖2.4：PEGASIS使用GREEDY演算法形成鍊結架構	16
圖2.5：MCFA以倒數計時法建立最佳成本域圖示範例	18
圖2.6：圖解DD於不同時態的擴散	20
圖2.7：SPIN的點對點資料傳送機制	21
圖2.8：EDDD以RT及BE過濾器劃分的封包傳送路徑組	25
圖2.9：LEACH每回合的時間線示意圖	26
圖2.10：PCBRP藉由連結方式來認定節點狀態	30
圖2.11：PCBRP-OPT在叢集內使用單播路由請求封包以減少廣播封包	31
圖2.12: HAR狀態轉換示意圖	34
圖2.13：由HAR建立的階層式路由樹	35
圖2.14：HMRP階層建構結果	36
圖3.1：由匯集節點及來源節點發出路由探索封包，開始路由樹的建立	45
圖 3.2：可與不同路由樹節點通訊的節點彼此交換路由	47
圖 3.3：路由樹成員節點會將所接收到至其它路由樹根節點的路由向親節點彙總	48
圖3.4：來源節點依路由表資訊向另一個來源節點更新至匯集節點的路由資訊	48
圖 3.5：根節點可得到自下游或鄰接節點所彙總至其它根節點的路由資訊	49
圖3.6：來源節點透過路由表的查詢將資料逐躍距傳送至匯集節點	50
圖3.7：當節點的路由表單容量較小，會優先儲存至各個根節點較短的路由	52
圖3.8：節點故障發生後，鄰接節點會向路由表單中可至各路由樹根節點的下一躍距節點更新資訊	53
圖3.9：節點故障發生時，其子節點會藉由路由表單尋找適合的親節點候選者	55
圖3.10：若故障節點的子節點找不到合適的親節點候選者，則其與其下遊子節點會解除彼此間從屬關係，並各自尋找新的親節點	57
圖3.11：節點接受到路由探索封包時的運作機制流程圖	61
圖3.12：節點發現鄰接節點故障時的節點運作流程圖	61
圖3.13：節點接收到路由修正資訊時的節點運作流程圖	62
圖3.14：節點接收到親節點探索封包時的節點運作流程圖	62
圖4.1：不同總節點數的平均等待時間比較	67
圖4.2：不同總節點數的平均路徑長度比較	70
圖4.3：不同總節點數的網路強健度比較	72
圖4.4：不同網路大小的平均等待時間比較	76
圖4.5：不同網路大小的平均路徑長度比較	78
圖4.6：不同網路大小的網路強健度比較	80
圖4.7：不同匯集節點密度的平均等待時間比較	84
圖4.8：不同匯集節點密度的平均路徑長度比較	86
圖4.9：不同匯集節點密度的網路強健度比較	88
圖4.10：路由協定在節點反常態分佈時的平均等待時間	91
圖4.11：路由協定在節點反常態分佈時的平均路徑長度	91
圖4.12：路由協定在節點反常態分佈時的網路強健度	92
圖4.13：在網路大小不同時建構網路拓樸的節點平均接收控制封包數	95
圖4.14：建構網路拓樸時BHAR與HAR的節點平均接收控制封包比率	98
表目錄
表2.1：各類型路由協定運作機制比較	38
表3.1：感測器節點中的路由表項目格式	45
表4.1：總節點數影響評估的模擬環境參數	65
表4.2：網路大小影響評估的模擬環境參數	73
表4.3：匯集節點密度影響評估的模擬環境參數	81
表4.4：反常態分佈影響評估的模擬環境參數	90
表4.5：控制封包產生數評估的模擬環境參數	93
表5.1：BHAR運作機制	101
表5.2：BHAR與HAR優劣比較	102

[1].	W. Heinzelman, A. Chandrakasan, and H. Balakrishnan. “Energy-Efficient Communication Protocols for Wireless Microsensor Networks,” in Proc. of Hawaiian Int. Conf. on Systems Science, January 2000.
[2].	T. J. Kwon, M. Gerla, V. K. Varma, M. Barton, and T. R. Shing, “Efficient Flooding with Passive Clustering—An Overhead-Free Selective Forward Mechanism for Ad Hoc/Sensor Networks,” Proc. of the IEEE, vol. 91, no. 8,Aug. 2003, pp.1210-1220.
[3].	B. J. Culpepper, L. Dung, and M. Moh. “Design and Analysis of Hybrid Indirect Transmissions (HIT) for Data Gathering in Wireless Micro Sensor Networks,” in ACM SIGMOBILE Mobile Computing and Communications Review, vol. 8, January 2004, pp. 61-83.
[4].	R. S. Chang and C. J. Kuo. “An Energy Efficient Routing Mechanism for Wireless Sensor Networks,” in Proc. of the 20th Int. Conf. on Advanced Information Networking and Applications, vol 2, June 2006, pp. 308-312.
[5]. Maleq Khan, Bharat Bhargava, and Leszek Lilien, “Self-configuring Clusters, Data Aggregation, and Authentication in Microsensor Networks,” Tech. Rep., CSD TR 03-005, Department of Computer Science, Purdue University, March 2003.
[6]. O. Younis and S. Fahmy., “Distributed Clustering in Ad-hoc Sensor Networks: A Hybrid, Energy-Efficient Approach,” IEEE Transactions on Mobile Computing, pp. 366–379, March 2004.
[7].位元文化，「Visual C++入門進階－從C++、物件導向到視窗程式設計」，文魁資訊股份 有限公司，台北，1999。
[8]. D. Braginsky and D. Estrin, “Rumor routing algorithm for sensor networks,” in Proc. of the 1s Workshop on Sensor Networks and Applications, Atlanta, GA, USA, pp. 22-31, Oct. 2002.
[9]. S. Lindsey and C.S. Raghavendra, “PEGASIS：Power Efficient Gathering in Sensor Information Systems,” in Proc. of IEEE Aerospace Conf., Vol.3 , March 2002. Pages:1125-1130
[10]. F. Ye, A. Chen, S. Lu, L. Zhang, "A Scalable Solution to Minimum Cost Forwarding in Large Sensor Networks," in Proc. of the 10th IEEE Int. Conf. on Computer Communications and Networks (ICCCN 2001), IEEE Computer Society Press, Los Alamitos, California, 2001.
[11]. C. Intanagonwiwat, R. Govindan, D. Estrin, J. Heidemann, and F. Silva, “Directed diffusion for wireless sensor networking,” IEEE/ACM Transactions on Networking, vol. 11, no. 1, pp. 2–16, February 2003.
[12]. J. Kulik, W. Heinzelman, and H. Balakrishnan, “SPIN：Negotiation-Based Protocols for Disseminating Information in Wireless Sensor Networks,” Wireless Networks, Vol. 8, 2002, Pages: 169-185
[13]. M. Chen, T. Kwon and Y. Choi, "Energy-Efficient Differentiated Directed Diffusion (EDDD) in Wireless Sensor Networks," Computer Communications, Vol. 29, No. 2, pp. 231-245, January 2006.
[14]. A. K. Parekh, “Selecting routers in ad hoc wireless networks,” in ITS, 1994.
[15]. M. Gerla and J.-c. Tsai. “Multicluster, Mobile, Multimedia Radio Network,” ACM Journal Wireless Networks, 1(3), July 1995, Page(s): 255-65
[16]. P. Krishna, N. H. Vaidya, M. Chatterjee, and D. K. Pradhan, “A cluster-based approach for routing in dynamic networks,” ACM SIGCOMM Computer Communication Review, pages 49--65, April 1997.
[17]. C.-C. Chiang, "Routing in Clustered Multihop, Mobile Wireless Networks with Fading Channel,” in Proc. of IEEE SlCON '97, pp. 197-211, Apr. 1997.
[18]. C. R. Lin and M. Gerla, “Adaptive Clustering for Mobile Wireless Networks,” IEEE JSAC, vol. 15, Sept. 1997, pp. 1265-75.
[19]. M. Jiang, J. Li, and Y.C. Tay, “Cluster Based Routing protocol (CBRP) functional specification,” Internet Draft, draft-ietf-manet-cbrp-spec-00.txt, 1998.
[20]. Heinzelman W., Chandrakasan A., and Balakrishnan H., “An Application-Specific Protocol Architecture for Wireless Microsensor Networks,” IEEE Transactions on Wireless Communications, Vol. 1, pp. 660-670, October 2002.
[21]. D. Estrin, R. Govindan, J. Heidemann, and S. Kumar, "Next Century Challenges: Scalable Coordination in Sensor Networks," in Proc. of the 5th Annual ACM/IEEE Int. Conf. on Mobile Computing and Networking(MOBICOM), pp. 263-270, 1999
[22]. Ossama Younis, Sonia Fahmy, and Paolo Santi, “An Architecture for Robust Sensor Network Communications,” Int. Journal of Distributed Sensor Networks, volume 1, issues 3-4, pp.305-327, 2005.
[23].	 A. Manjeshwar and D. P. Agrawal. “TEEN: A Routing Protocol for Enhanced Efficiency in Wireless Sensor Networks,” In 1st Int. Workshop on Parallel and Distributed Computing Issues in WirelessNetworks and Mobile Computing, April 2001.
[24]. A. Manjeshwar, and D. P. Agrawal, “APTEEN: A Hybrid Protocol for Efficient Routing and Comprehensive Information Retrieval in Wireless Sensor Networks,” in Proc. of the 16th IEEE Int. Parallel and Distributed Processing Symposium (IPDPS’02), pp. 195-202, Apr. 2002.
[25]. M. Gerla, T. J. Kwon and G. Pei, “On Demand Routing in large Ad Hoc Wireless Networks with Passive Clustering,” in Proc. of WCNC, Sep, 2000.
[26]. A. Rangaswamy and H. K. Pung, “Enhancement of passive cluster based routing protocol for mobile adhoc networks,” in Eleventh Int. Conf. on Computer Communications and Networks, October 2002, pp. 376–381.
[27]. N. Thepvilojanapong, Y. Tobe, and K. Sezaki, “On the construction of efficient data gathering tree in wireless sensor networks,” in Proc. of Int. Symposium on Circuits and Systems, pp. 648-651, 2005.
[28]. Niwat Thepvilojanapong, Tobe, Y., and Sezaki, K. “HAR: Hierarchy-Based Anycast Routing Protocol for Wireless Sensor Networks,” in Proc. of IEEE Symposium on Applications and the Internet, 31 Jan.– 4 Feb. 2005, pp. 204-212.
[29]. Y. Wang, H. Mao, C. Tsai, and C. Chuang, “HMRP: Hierarchy-Based Multipath Routing Protocol for Wireless Sensor Networks,” Tamkang Journal of Science and Engineering, Vol. 9, No 3, pp. 255-264, 2006.
[30]. I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “A Survey on Sensor Networks,” IEEE Communications Magazine, Vol. 40, No. 8, pp. 102-114, August 2002.
[31]. M. Aboelzem and F. Aloul, “Current and Future Trends in Sensor Networks: A Survey,” in Proc. of Wireless and Optical Communication Networks WOCCN05. Dubai, March 2005.
[32]. J. N. Al-karaki and A. E. Kamal, “Routing techniques in wireless sensor networks: a survey,” IEEE Wireless Communications, vol. 11, iss 6, pp. 6-28, Dec. 2004.
[33]. O. Younis, M. Krunz and S. Ramasubramanian, “Node Clustering in Wireless Sensor Networks: Recent Developments and Deployment Challenges,” IEEE Network, vol. 20, no. 3, 2006, pp. 20-25.
[34]. A. Ahmed, H. Shi and Y. Shang, "A survey on network protocols for wireless sensor networks," in Int. Conf. on Information Technology: Research and Education, pp.301-305, 2003.
[35]. Q. Jiang and D. Manivannan, "Routing Protocols for Sensor Networks," in Proc. of the Consumer Communications and Networking Conf., pp.93-98, 2004.
[36]. Y. Tang, M. T. Zhou, X. Zhang. “Overview of routing protocols in wireless sensor networks,” Journal of Software, Vol. 17, No 3, pp.410-421, 2006.
[37]. K. Akkaya and M. Younis , "A Survey on Routing Protocols for Wireless Sensor Networks," Elsevier Ad Hoc Network Journal, Vol. 3, No. 3, pp. 325 – 349, May 2005.
[38]. C. Siva Ram Murthy and B.S. Manoj, Ad Hoc Wireless Networks: Architectures and Protocols, Prentice Hall Press, Vol. 12, pp. 647-689, 2004.