臺灣博碩士論文加值系統

在行動隨意網路中，地域性廣播(Geocast)利用地理資訊將資料封包傳送到特定地理區域中的節點[1]。在轉送過程中，當轉送區域內有大量節點時，會增加傳送封包時碰撞的機率，遺失率也相對提高。本篇論文提出Grid-base-Location-Aided (GLA)與Greedy-Grid-base-Location-Aided (GGLA)方法來改善此問題，GLA方法主要將地域性廣播轉送區域分成數個網格，每個網格只能擁有一個主要節點(gateway)負責轉送的工作，來減少傳送次數，GGLA方法則是加入貪婪路由機制，來減少更多不必要的傳送，以改善在無線網路環境中轉送區域內密集節點傳輸所造成的訊號碰撞與封包遺失的問題。當地域性廣播區域中的節點接收到資料封包後，直接將封包廣播出去，會造成地域性廣播區域中大量的廣播封包，易產生廣播風暴的問題[2]。透過網路編碼將二個以上的封包做編碼的動作後廣播出去，可以減少地域性廣播區域內封包的傳送次數並結合GLA與GGLA方法，來提升整體網路效能。

In MANET, geocasting utilizes geographic information to deliver data packets to nodes within a specific geographical area. During packet forwarding, the probability of signal collision and packet loss are increased when a large number of nodes are within the forwarding zone. In this paper, we propose Grid-base-Location-Aided (GLA) and Greedy-Grid-base-Location-Aided (GGLA) algorithms to solve the problem. GLA partitions the geocast forwarding zone into several 2D logical grids; a node is elected as a gateway in each grid, where the gateway is responsible for forwarding data packets to the geocast region. By using the gateway approach, GLA can reduce the required number of packet forwarding. GGLA introduces a greedy routing mechanism to GLA for reducing the probability of packet loss with high-density nodes in the forwarding zone. When a node is received a date packet in the geocast region, it floods the data packet in the geocast region, which may cause the broadcast storm problem. By using the network coding mechanism, two or more packets can be encoded and then broadcast, which can decrease the required number of packets for loss recovery. In this thesis, GLA and GGLA are further integrated with a network coding mechanism to improve the efficiency of packet transmission in the geocast region.

摘 要 I
ABSTRACT II
致謝 III
目 次 IV
表目錄 V
圖目錄 VI
第一章 簡介 1
第二章 相關研究 4
2.1 地域性廣播相關文獻 4
2.1.1 LAR與LBM技術介紹 4
2.1.2 Voronoi技術介紹 6
2.1.3 Mesh技術介紹 6
2.1.4 Grid技術介紹 8
2.2 網路編碼介紹 9
第三章 論文演算法 13
3.1 GRID-BASE-LOCATION-AIDED (GLA)方法 13
3.2 GREEDY-GRID-BASE-LOCATION-AIDED (GGLA)方法 22
3.3 結合網路編碼機制的地域性廣播 29
第四章 模擬數據 33
第五章 結論 41
參考文獻 42

[1]Ryo Miki, Yoh Shiraishi, Osamu Takahashi. “A Geocast-based Multicast Method for Continuous Information Delivery in MANET.” International Conference on P2P, Parallel, Grid, Cloud and Internet Computing (3PGCIC), pp.511-516, Nov. 2010.
[2]S.•Y. Ni, Y.•C. Tseng, Y.•S. Chen, and J.•P. Sheu, "The Broadcast Storm Problem in a Mobile Ad Hoc Network," MobiCom 99, pp.151-162, Aug. 1999.
[3]X. Jiang and T. Camp, “A Review of Geocasting Protocols for a Mobile Ad Hoc Network.” Proc. Grace Hopper Celebration(GHC), pp.1-5, Oct. 2002.
[4]Tomoyuki Ohta, Takeshi Hashimoto, and Yoshiaki Kakuda, "Self-organizing real-time service dissemination and collection using mobile agents for mobile ad hoc networks," Proc. 14th IEEE International Symposium on Object/Component/Service-oriented Real-time Distributed Computing Workshops (ISORCW), pp.199-206, March 2011.
[5]R. J. Hall and J. Auzins, “A Tiered Geocast Protocol for Long Range Mobile Ad Hoc Networking,” Proceedings of the 2006 IEEE Military Communications Conference, pp.1-8, Oct. 2006.
[6]H. P. Joshi, M. L. Sichitiu, and M. Kihl, “Distributed Robust Geocast: A Multicast
Routing for Inter-Vehicle Communication,” Proceedings of WEIRD Workshop on WiMAX, Wireless and Mobility, pp.9-21, May 2007.
[7]Y.-B. Ko and N. H. Vaidya, “GeoTORA：A Protocol for Geocasting in Mobile Ad Hoc Networks,” Proc. 8th International Conference Network Protocol (ICNP), Osaka, Japan, pp. 240-50, Nov. 2000.
[8]Christian Maihofer, Tim Leinmuller, and Elmar Schoch, “Abiding geocast: time-stable geocast for ad hoc networks”, Proceedings of the 2nd ACM international workshop on Vehicular ad hoc networks (VANET’05), USA, pp. 20-29, 2005.
[9]Y.-B. Ko and N. H. Vaidya, “Flooding-Based Geocasting Protocols for Mobile Ad Hoc Networks,” Mobile Networks and Applications, Vol. 7, No. 6, pp. 471-80, 2002.
[10]Wen-Hwa Liao, Jang-Ping Sheu, Yu-Chee Tseng, “GRID：A Fully Location-Aware Routing Protocol for Mobile Ad Hoc Networks.” Proceedings of Telecommunication System, Vol. 18, No. 1-3, pp.37-60, 2001.
[11]Yuan’an Liu, Hefei Hu, Dongming Yuan, "Link stability-based Routing in mobile Ad Hoc Networks", Proc. 5th IEEE conference on Industrial Electronics and Applications (ICEIA), pp.15-17, June 2010.
[12]C. -Y. Chang, C.' T. Chang, and S. -C. Tu, "Obstacle•Free Geocasting Protocols for Single/Multi• Destination Short Message Services in Ad Hoc Networks," Wireless Networks, Vol. 9, No. 2, pp.143-155, 2001.
[13]Y.-B. Ko and N. H. Vaidya, “Location-aided routing (LAR) in mobile ad hoc networks,” Proc. of the 4th ACM/IEEE Internet. Conference on Mobile Computing and Networking (MOBICOM), Dallas, pp.66-75, October 1998.
[14]Y.-B. Ko and N. H. Vaidya, “Geocasting in Mobile Ad Hoc Networks: Location-Based Multicast Algorithms,” WMCSA 99, USA, pp.101-110, Feb 1999.
[15]C. Maihöfer, “A survey of geocast routing protocols,” IEEE Communications Surveys & Tutorials, Vol. 6, No. 2, pp.32–42, 2004.
[16]I. Stojmenovic, A. P. Ruhil, and D.K. Lobiyal, “Voronoi Dia-gram and Convex Hull-Based Geocasting and Routing in Wireless Networks.” Proc. 8th IEEE Symposium Computer and Communication ISCC, Antalya, Tukey, pp. 51-56, July 2001.
[17]J. Boleng, T. Camp, and V. Tolety. “Mesh-based geocast routing protocols in an ad hoc network,” Proceedings of International Parallel and Distributed Processing Symposium (IPDPS), pp.184.193, April 2001.
[18]Abhishek Kr. Mishra and Birendra Kumar, “Proposed Extended Geocast Adaptive Mesh Environment for Routing (EGAMER),” Proceedings of the 2nd National Conference, pp.225-229, 2008.
[19]T. Camp and Y. Liu. “An Adaptive mesh-based protocol for geocasting routing.” Journal of parallel and Distributed computing: special Issue on routing in mobile and wireless Ad hoc Networks, Vol. 62, No. 2, pp.196-213, 2003.
[20]T-H. Chu and S-I. Hwang, “Efficient Fisheye State Routing Protocol using Virtual Grid in High density Ad Hoc Networks,” Proceedings of the 8th International Communication Conference on Advanced Technology, Vol. 3, pp.1475-1478, February 2006.
[21]R. Ahlswede, N. Cai, S. Y. R. Li, and R. W. Yeung, “Network information flow,” IEEE Trans. on Information Theory, Vol. 46, No. 4, pp.1204-1216, July 2000.
[22]G. J. Yu, C. Y. Chang, T. C. Wang, and T. L. Wang, “A Reliable and Efficient Broadcasting Protocol based on Incremental Network Coding,” National Symposium on Telecommunications (NST 2009), Taiwan, pp.81-85, Dec. 2009.
[23]S.-Y. R. Li, R. W. Yeung, and N. Cai, “Linear network coding,” IEEE Transactions on Information Theory, Vol. 49, pp.371-381, February 2003.
[24]Katti, S., Rahul, H., Wenjun Hu and Katabi, D., Medard, M., Crowcroft, J, “XORs in the Air: Practical Wireless Network Coding,” IEEE/ACM Transactions on Networking, Vol. 16, No. 3, pp.497–510, June 2008.
[25]Ho, T.; Koetter, R., Medard, M., Karger, D.R., Effros, M, “The benefits of coding over routing in a randomized setting,” Proc. of International Symposium on Information Theory (ISIT), pp.442, 29 June-4 July 2003.
[26]B. Karp and H. T. Kung, "GPSR: Greedy Perimeter Stateless Routing for Wireless Sensor Networks", Proc. MobiCom, pp.243 -254, 2000.
[27]Tz-Heng Hsu and Ying-Chen Lo, "A Multi-Forwarding Zone Geocasting in Mobile Ad Hoc Networks", Proceedings of 2010 Workshop on Consumer Electronics, pp.490-496, November 5, 2010.