臺灣博碩士論文加值系統

地理路由協定是一個簡單的、有效的與可延伸的路由協定，利用位置資訊來找尋路由使得彼此雙方能夠互相通訊，其優點在於能夠避免泛流 (Flooding) 的成本。然而使用地理路由協定建立路由必須要先知道目的地的位置。事實上，在移動式無線隨意網路中，節點的位置隨時可能改變，所以要有一個位置伺服器 (Location Server) 來記錄所有節點的位置資訊，而節點則必須頻繁地向位置伺服器回報其最新位置資訊，以保持位置伺服器中資訊的正確，因此消耗了網路大量的頻寬與中繼節點的電源，同時不論目標節點的遠近，來源節點都必須詢問位置伺服器以獲知目標節點位置，不僅缺乏效率，也浪費網路頻寬。
在本文裡，我們首先利用信標 (Beacon) 機制使得節點在移動時能沿途遺留下足跡，如此即使位置伺服器中沒有存放節點的最新位置資訊，也可以循著足跡找到節點，所以可以在降低節點回報位置資訊頻率的情況下，保持正確找到節點的能力。此外藉由節點位置的預測與封包資訊的收集，我們的方法可以在不靠位置伺服器的情況下經由較短路徑找到目標節點。初步的實驗顯示我們的方法確能達到我們預期的效果。

Geographic routing protocol is a simple, effective and scalable routing protocol. To find out a route between two nodes by using location information can avoid the cost of flooding. However, a geographic routing protocol has to know the location of the destination node before it can build a route. In fact, in the mobile wireless networks, the location of nodes may change at any time, so there must be a location server to record the location information of all nodes, and nodes must report their up-to-date location information to the location server frequently in order to keep the information recorded in the location server correct. Therefore, the consumption of network bandwidth and the power of rely nodes may be very large. In the mean time, regardless of the location of the destination node, the source node must ask the location server for the location of the destination node; it is time inefficient and wastes the network bandwidth as well.
In this paper, we use the beacon mechanism to allow the mobile nodes leaving their footprint along the moving tracks, so even if the location server does not have the latest locations of the destination nodes, the destination nodes can be tracked by following the footprints they left. Thus we can achieve the same ability to find out the destination node with fewer reporting packets. In addition, by using a prediction mechanism and the information collected from overheard packets, our approach can find out a destination node through a shorter path without the aid of location server. Preliminary results show that our approach indeed achieves the expected effect.

中文摘要
英文摘要
致謝
目錄
圖目錄
表目錄第一章 緒論
1.1. 研究背景
1.2. 研究動機
1.3. 研究目的
1.4. 論文架構
第二章 相關研究
2.1. 位置服務分類
2.2. 相關文獻
2.2.1. EASE
2.2.2. XYLS
2.2.3. 群聚更新
第三章 具有位置預測機制之捷徑優先無線隨意網路地理路由協定
3.1. 動態回報機制
3.2. 位置預測與捷徑優先轉送機制
3.3. 足跡追蹤機制
3.4. 節點運動模型
3.5. 流程圖步驟
第四章 實驗模擬與效能分析
4.1. 實驗環境參數設定與效能指標
4.2. 我們的方法與定時回報機制
4.3. 方法中四種機制的取捨與比較
4.4. 節點速度的影響
4.5. 節點運動模型分析
4.6. 我們的方法與EASE
第五章 結論與未來研究
5.1. 結論
5.2. 未來研究
參考文獻

[1] C. E. Perkins and P. Bhagwat, “Highly dynamic destination-sequenced distance-vector routing (DSDV) for mobile computers,” in Proc. of ACM SIGCOMM, August 1994.
[2] D. B. Johnson and D. A. Maltz, “Dynamic source routing in ad hoc wireless networks,” Mobile Computing, Kluwer Academic, 1996.
[3] C. E. Perkins and E. M. Royer, “Ad hoc on-demand distance vector routing,” in Proc. of IEEE WMCSA, February 1999.
[4] Z. J. Haas and M. R. Pearlman, “The performance of query control schemes for the zone routing protocol,” in Proc. of ACM SIGCOMM, August 1998.
[5] S. M. Das, H. Pucha, and Y. C. Hu. “On the Scalability of Rendezvous-based Location Services for Geographic Wireless Ad Hoc Routing.” Elsevier Computer Networks, 51(13):3693–3714, 2007.
[6] B. Karp and H. Kung, “GPSR: greedy perimeter stateless routing for wireless networks,” Proceedings of the sixth annual international conference on Mobile computing and networking, pp. 243-254, 2000.
[7] Stefano Basagni, Imrich Chlamtac, Violet R. Syrotiuk, and Barry A.Woodward. “A distance routing effect algorithm for mobility (DREAM).” In Proceedings of ACM MobiCom 98, pages 76–84, 1998.
[8] K. Young-Bae and H. V. Nitin, “Location-aided routing (LAR) in mobile ad hoc networks,” Wireless Networks vol. 6, pp. 307-321, 2000.
[9] M. Mauve, J. Widmer, H. Hartenstein, “A survey on position-based routing in mobile ad-hoc networks,” IEEE Network Magazine, 15(6):30 - 39, November 2001.
[10] Christine T. Cheng, H. L. Lemberg, Sumesh J. Philip, E. van den Berg, and T. Zhang. “SLALoM: A scalable location management scheme for large mobile ad-hoc networks.” In Proceedings of IEEE WCNC, March 2002.
[11] I. Stojmenovic, “A scalable quorum based location update scheme for routing in ad hoc wireless networks,” Technical Report TR-99-09, SITE, University of Ottawa, Sep. 1999.
[12] I. Stojmenovic, “Home agent based location update and destination search schemes in ad hoc wireless networks,” Technical Report TR-99-10, SITE, University of Ottawa, Sep. 1999.
[13] J. Li, J. Jannotti, Douglas S. J. De Couto, D. R. Karger and R. Morris, “A scalable location service for geographic ad hoc routing,” Proceedings of the sixth annual international conference on Mobile computing and networking, Aug. 2000.
[14] P.-H. Hsiao, “Geographical Region Summary Service for Geographical Routing,” The ACM Symposium on Mobile ad hoc Networking & Computing Poster Paper, Vol. 5, No. 4, Oct. 2001.
[15] S.-C. M. Woo and S. Singh, “Scalable routing protocol for ad hoc networks,” Wireless Networks, Vol. 7, No. 5, Sep. 2001.
[16] Y. Xue, B. Li, and K. Nahrstedt, “A scalable location management scheme in mobile ad-hoc networks,” Proceedings of 26th Annual IEEE Conference on Local Computer Networks, pp. 102 -111, 2001.
[17] Y Yu, GH Lu, ZL Zhang. “Enhancing location service scalability with HIGH-GRADE” in Proceedings of IEEE Mobile Ad-hoc and Sensor Systems, Oct. 2004.
[18] I. Stojmenovic, D. Liu, and X. Jia. “A Scalable Quorum based Location Service in Ad Hoc and Sensor Networks.” In MASS’06, Vancouver, Canada, Oct. 2006.
[19] Ivan Stojmenovic, Dandan Liu, and X. Jia, “A scalable quorum-based location service in ad hoc and sensor networks,” International Journal of Communication Networks and Distributed Systems. IJCNDS, vol. 1, pp. 71-94, 2008.
[20] Jehn-Ruey Jiang and Wei-Jiun Ling. Seeker: An adaptive and scalable location service for mobile ad hoc networks. Proceedings of International Computer Symposium, 2006.
[21] Z.J. Haas and B. Liang. “Ad hoc mobility management with uniform quorum systems.” IEEE/ACM Transactions on Networking,
7(2):228–240, April 1999.
[22] B. Ihn-Han and L. Honghai, “FHLS: Fuzzy Hierarchical Location Service for Mobile Ad Hoc Networks,” in Fuzzy Systems Conference, IEEE International, 2007, pp. 1-5.
[23] K. Wolfgang, F. Holger, ler, J, W. rg, and M. Martin, “Hierarchical location service for mobile ad-hoc networks,” in Mobile Computing and Communications Review. ACM SIGMOBILE, 2004, pp. 47-58.
[24] L. Te-Neng and H. Shyh-In, “On Design of an Efficient Hierarchical Location Service for Ad Hoc Network,” in 1st International Symposium on Wireless Pervasive Computing, 2006, pp. 1-6.
[25] H. Yang, O. Yuanxin, L. Yunlu, and X. Zhang, “On Design of Mobile Agent Based Location Service for Geographic Routing,” in The 4th International Conference on Mobile Ad-hoc and Sensor Networks, 2008, pp. 195-202.
[26] M. Grossglauser and M. Vetterli, “Locating mobile nodes with EASE: learning efficient routes from encounter histories alone,” IEEE/ACM Transactions on Networking, vol. 14, pp. 457-469, 2006.