本學位論文針對無線網狀網路環境提出基於Weil Pairing的安全匿名路由協定。本研究考慮無線網狀網路存在多種具備不同通訊能力的無線裝置，造就了無線網狀網路中存在非對稱式通訊之情形，因此進行無線通訊時常常同時出現對稱式通訊及非對稱式通訊。如何提升無線網狀網路中的安全性及使用者隱私已是近幾年重要的研究議題，然而大部分的研究僅提供在對稱式通訊模式下路由及資料的安全傳輸及匿名性，非對稱式通訊模式幾乎從未被納入考慮。本研究提出了全新的無線網狀網路路由協定，該路由協定在設計時同時考慮了對稱式通訊及非對稱式通訊兩種模式混和的狀態，本研究提出之協定確保了在路由過程中的安全性、匿名性及高可靠性。而因納入在實務上存在的非對稱式通訊模式，本研究不但兼顧安全傳輸與隱私保護亦建立出較過去之路由技術更短路由路徑。在路由及資料交換的過程當中，本研究在提供使用者驗證的同時，也確保通訊雙方及路由路徑中的參與者的身分不會被他人得知，即便是網路中的網狀路由器也無法做到。透過本研究，使用者可以安全且匿名的建立一條與網狀路由器間較短的通訊的路徑，並同時確保資料傳輸的安全性及匿名性；而本研究也因同時考慮對稱式通訊及非對稱式通訊兩種模式提升了無線網狀網路的涵蓋率。

This dissertation proposes an efficient, secure, and anonymous routing protocol based on Weil pairing for wireless mesh networks (WMNs). The proposed protocol considers symmetric and asymmetric links during wireless communication in WMNs. A WMN integrates several types of wireless devices and induce the asymmetric links that result from different transmission ranges of wireless devices. Enhancing the security and privacy of WMNs has been an important research focus in recent years. Most research on this topic has focused on providing security and anonymity for routing and data in symmetric links. However, the asymmetric links in these protocols have not been addressed. This dissertation proposes a novel distributed routing protocol suitable for WMNs that include symmetric and asymmetric links. The proposed protocol guarantees security, anonymity, and high reliability in WMNs. The proposed protocol generates routes that are shorter than those in previous research. The proposed scheme protects the real identity of the source and of intermediate user, which remain unknown even to the mesh router, while still providing node authentication. Using the proposed protocol, mesh clients anonymously discover a secure route to the mesh router. This protocol also ensures data transmission anonymity and enhances WMN coverage, in addition to assuring security and anonymity.

Contents
Chapter 1 Introduction	1
Chapter 2 Related Works	8
2.1 Secure and Anonymous Routing	8
2.2 Threats and Problem Statement	10
2.3 Design Goal	11
2.4 Preliminaries and Notations	12
Chapter 3 Neighbor Discovery scheme	15
3.1 Regular-Neighbor Discovery Phase	16
3.2 Semi-neighbor Discovery Phase	19
3.3 Data Forwarding to Rev-Semi-Neighbor protocol	21
Chapter 4 Secure routing protocol	22
4.1 Secure Route Request Phase	22
4.2 Secure Route Reply Phase	25
4.3 Secure Data Transmission Phase	27
4.4 Secure Route Maintenance	28
Chapter 5 Anonymous Routing Protocol	30
5.1 Anonymous Route Request Phase	31
5.2 Anonymous Route Reply Phase	34
5.3 Anonymous Data Transmission Phase	36
5.4 Anonymous Route Maintenance	37
Chapter 6 Security Analysis	39
6.1 Authentication	39
6.2 Confidentiality	42
6.3 Integrity	43
6.4 Anonymity	43
6.5 Untraceability	44
6.6 Sybil Attack	45
6.7 Rushing Attack	45
6.8 Impersonate Attack	46
6.9 Spoofed or Altered Message	46
Chapter 7 Comparison and Performance Evaluation	48
7.1 Simulation environment	48
7.2 Comparison	49
7.3 Improvement of Neighbor Discovery Rate	50
7.4 Average Route Hop Count and Route Establishment Success rate	51
Chapter 8 Conclusions and Future Works	54
Reference	56

Figures
Figure 1. The architecture of Wireless Mesh Networks	2
Figure 2. Scenario of Communication in Symmetric and Asymmetric Links	4
Figure 3. Regular-neighbor Discovery Phase	16
Figure 4. Semi-neighbor Discovery Phase	18
Figure 5. Secure Route Request Phase	23
Figure 6. Secure Route Reply Phase	25
Figure 7. Anonymous Route Request Phase	31
Figure 8. Anonymous Route Reply Phase	34
Figure 9. Onion-layer Encryption Message	36
Figure 10. Improvement of neighbor discovery rate of Normal user	50
Figure 11. The comparison of Route length (400 users)	51
Figure 12. The comparison of Route length (200 users)	51
Figure 13. Comparison of route establishment success rate (400 users)	52
Figure 14. Comparison of route establishment success rate (200 users)	53
 
Tables
Table 1. Security Features for Secure and Anonymous Routing	12
Table 2. Notations	14

[1] Ian F. Akyildiz; Xudong Wang; "A survey on wireless mesh networks," IEEE Communications Magazine, vol.43, no.9, pp. S23- S30, Sept. 2005
[2] Azzedine Boukerche, Khalil El-Khatib, Li Xu, Larry Korba, "An efficient secure distributed anonymous routing protocol for mobile and wireless ad hoc networks, " Computer Communications, vol. 28, Issue 10, Performance issues of Wireless LANs, PANs and ad hoc networks, 16 June 2005, pp. 1193-1203,
[3] Yigal Bejerano, Seung-Jae Han, Amit Kumar, "Efficient load-balancing routing for wireless mesh networks," Computer Networks, vol. 51, Issue 10, 11 July 2007, pp. 2450-2466
[4] D. Boneh and M. Franklin. "Identity based encryption from the Weil pairing," SIAM J. of Computing, Vol. 32, No. 3, pp. 586-615, 2003
[5] Perkins, C.; Belding-Royer, E.; Das, S. "Ad hoc On-Demand Distance Vector (AODV) Routing," IETF. RFC 3561. Retrieved 2010-06-18.
[6] Jiefeng (Terence) Chen, Roksana Boreli, Vijay Sivaraman, "Improving the efficiency of anonymous routing for MANETs," Computer Communications, vol. 35 ,no.5, pp. 619-627. 2012
[7] Sisheng Chen; Li Xu; Zhide Chen; , "Secure Anonymous Routing in Trust and Clustered Wireless Ad Hoc Networks," Communications and Networking in China, 2007. CHINACOM '07. Second International Conference on , vol., no., pp.994-998, 22-24 Aug. 2007
[8] Lanjun Dang; Jie Xu; Hui Li; Nan Dang; , "DASR: Distributed Anonymous Secure Routing with Good Scalability for Mobile Ad Hoc Networks," Services Computing Conference (APSCC), 2010 IEEE Asia-Pacific , pp.454-461, 6-10 Dec. 2010
[9] Jing Deng, Richard Han, Shivakant Mishra, "INSENS: Intrusion-tolerant routing for wireless sensor networks, " Computer Communications, vol. 29, Issue 2, Dependable Wireless Sensor Networks, 10 January 2006, pp. 216-230,
[10] Ying Dong, Tat Wing Chim, Victor O.K. Li, S.M. Yiu, C.K. Hui, "ARMR: Anonymous routing protocol with multiple routes for communications in mobile ad hoc networks," Ad Hoc Networks, vol. 7, Issue 8, Privacy and Security in Wireless Sensor and Ad Hoc Networks, November 2009, pp. 1536-1550
[11] J. R. Douceur, J. S. Donath,(2002) "The Sybil Attack," The 1st International WorkShop on Peer-to-Peer Systems - IPTPS , pp. 251-260, 2002.
[12] D. Djenouri, L. Khelladi and A.N. Badache,(2005) "A survey of security issues in mobile ad hoc and sensor networks," IEEE on Communications Surveys & Tutorial, , vol.7, no.4, pp. 2- 28, Fourth Quarter, 2005.
[13] Jakob Eriksson; Michalis Faloutsos; Srikanth V. Krishnamurthy, "DART: Dynamic Address RouTing for Scalable Ad Hoc and Mesh Networks," Networking, IEEE/ACM Transactions on , vol.15, no.1, pp.119-132, Feb. 2007
[14] Y.-C. Hu, A. Perrig, and D. B. Johnson (2002) "Ariadne: a secure on-demand routing protocol for ad hoc networks," In Proceedings of the 8th annual international conference on Mobile computing and networking (MobiCom '02). ACM, New York, NY, USA, pp.12-23.
[15] Celia Li, Zhuang Wang, and Cungang Yang, "Secure Routing for Wireless Mesh Networks, " International Journal of Network Security, Vol.13, No.2, pp.109-120, Sept. 2011
[16] Tingyao Jiang, Qinghua Li, and Youlin Ruan. 2004. "Secure Dynamic Source Routing Protocol," in Proceedings of the The Fourth International Conference on Computer and Information Technology (CIT '04), Washington, DC, USA, Pages 528-533.
[17] David B. Johnson, David A. Maltz, and Josh Broch. "The Dynamic Source Routing Protocol for Multihop Wireless Ad Hoc Networks," In Ad Hoc Networking, edited by Charles E. Perkins, chapter 5, pages 139.172. Addison-Wesley, 2001.
[18] Frank Kargl, Alfred Geis, Stefan Schlott, and Michael Weber. "Secure Dynamic Source Routing," In Proceedings of the Proceedings of the 38th Annual Hawaii International Conference on System Sciences - vol. 09 (HICSS '05), Washington, DC, USA, 2005
[19] Yih-Chun Hu, Adrian Perrig, and David B. Johnson, "Rushing attacks and defense in wireless ad hoc network routing protocols," In Proceedings of the 2nd ACM workshop on Wireless security (WiSe '03), New York, NY, USA, pp. 30-40. 2003
[20]Y., Hu, D. Johnson, and A. Perrig. "SEAD: Secure Efficient Distance Vector Routing for Mobile Wireless Ad hoc Networks," In Proceedings Workshop on Mobile Computing Systems and Applications, June 2002.
[21] C. Karlof, and D. Wagner, " Secure routing in wireless sensor networks: attacks and countermeasures," Ad Hoc Networks, Vol. 1, No. 2-3, September, 293-315.
[22] J. Kong and X.Y. Hong, "ANODR: anonymous on demand routing with untraceable routes for mobile ad-hoc networks," In Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing (MobiHoc '03). ACM, New York, USA, September 14-19, 2003, pp.291-302.
[23] Paterson, K.G. , "ID-based signatures from pairings on elliptic curves," Electronics Letters , vol.38, no.18, pp. 1025- 1026, 29 Aug 2002
[24] Jihye Kim, Gene Tsudik, "SRDP: Secure route discovery for dynamic source routing in MANETs," Ad Hoc Networks, vol. 7, Issue 6, August 2009, pp. 1097-1109.
[25] L.A.Martucci, A.Zuccato, S.Fischer-Hubner. "Identity Deployment and Management in Wireless Mesh Networks," In: The Future of Identity in the Information Society - Proceedings of the 3rd IFIP WG 9.2, 9.6/11.6, 11.7/FIDIS International Summer School. Springer. Aug. 2007. Karlstad, Sweden. pp.223-234.
[26] Rosa Mavropodi, Panayiotis Kotzanikolaou, Christos Douligris, "SecMR - a secure multipath routing protocol for ad hoc networks," Ad Hoc Networks, vol. 5, Issue 1, January 2007, pp. 87-99,
[27] Krichene, N.; Boudriga, N., "Intrusion Tolerant Routing for Mesh Networks," 2007 IFIP International Conference on Wireless and Optical Communications Networks, 2-4 July 2007, Singapore, pp. 1-7.
[28] Jung Ha Paik; Bum Han Kim; Dong Hoon Lee, "A3RP : Anonymous and Authenticated Ad Hoc Routing Protocol," International Conference on Information Security and Assurance, 2008. ISA 2008, pp.67-72, 24-26 April 2008
[29] Nagesh S. Nandiraju; Deepti S. Nandiraju; Dharma P. Agrawal; , "Multipath Routing in Wireless Mesh Networks," 2006 IEEE International Conference on Mobile Adhoc and Sensor Systems (MASS), Vancouver , Canada, pp. 741-746, 9-12 Oct. 2006.
[30] Ronggong Song, Larry Korba, and George Yee, "AnonDSR: efficient anonymous dynamic source routing for mobile ad-hoc networks," In Proceedings of the 3rd ACM workshop on Security of ad hoc and sensor networks (SASN '05), New York, NY, USA, pp. 33-42. 2005
[31] Ming-Yang Su, "WARP: A wormhole-avoidance routing protocol by anomaly detection in mobile ad hoc networks," Computers & Security, vol. 29, Issue 2, March 2010, pp. 208-224,
[32] Zhiguo Wan; Kui Ren; Bo Zhu; Preneel, B.; Ming Gu; , "Anonymous User Communication for Privacy Protection in Wireless Metropolitan Mesh Networks," IEEE Transactions on Vehicular Technology , vol.59, no.2, pp.519-532, Feb. 2010
[33] Jianliang Zheng, Myung J. Lee, "A resource-efficient and scalable wireless mesh routing protocol," Ad Hoc Networks, vol. 5, Issue 6, August 2007, pp. 704-718.