簡易檢索 / 詳目顯示

回結果列表
研究生： 楊安國
Yang, An-Guo
論文名稱： 行動隨意網路中使用費瑪點減少區域性群播的繞送距離
Improving Routing Distance for Geographic Multicast with Fermat Points in Mobile Ad Hoc Networks
指導教授： 斯國峰
Ssu, Kuo-Feng
學位類別： 碩士
Master
系所名稱： 電機資訊學院 - 電腦與通信工程研究所
Institute of Computer & Communication Engineering
論文出版年： 2006
畢業學年度： 94
語文別： 英文
論文頁數： 39
中文關鍵詞： 隨意網路 、群播 、行動
外文關鍵詞： mobile, ad hoc network, multicast
相關次數： 點閱：71  下載：3 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 傳統有線網路中具有豐富的計算能力與資源，解決群播問題能夠以複雜精確的演算求得最有效率的傳輸拓樸圖形。然而在行動隨意網路的架構裡，除了裝置具有的能源有限之外，裝置移動使得網路結構呈現不固定的狀態。諸多論文為了達成最低限度的能源損失，著眼在降低建立與維護傳輸拓樸圖形時所需要的資訊量；為了因應裝置移動問題，採納定位系統輔助得到地理位置資訊以達成最低限度的資訊需求。
    本篇論文以費瑪點預測傳輸拓樸圖形的概觀，並且以貪婪式轉送的方法傳遞資料封包。因為無須使用封包溝通來建立與維護拓樸圖形，可完成節省能源之目的。而採取貪婪式轉送資料封包，以適應裝置移動所產生的問題。
    實驗結果證實採取費瑪點事先預測技術可以得到更短的傳輸拓樸圖形，面對變動性高的環境能夠提升封包送達比例，即使傳輸成員增加也可以維持一定的傳輸效能。

    An ad hoc network is a new research area that joins an important factor of mobility. Each node is either randomly or planned moving in the field. These nodes have ability to transmit, receive, and route packets. Reducing routing distance is always an essential issue for the mobile ad hoc network. However, no matter in the ad hoc network or static network, the problem to minimize the overall routing distance for multicasting is NP-complete. Therefore, it is hard to guarantee an optimal solution. This paper presents an efficient geographic multicast protocol, called GMFP, based on Fermat points. GMFP aims to improve overall routing distance for multicast tasks. Our simulation shows that GMFP performs better than PBM that was the best multicast mechanism in mobile ad hoc networks.

    1 Introduction : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 1 2 Related Work : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 3 2.1 Fermat points . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.2 Overview of geocasting algorithms . . . . . . . . . . . . . . . . . . . . . . 4 2.3 Ad hoc multicast routing algorithms . . . . . . . . . . . . . . . . . . . . 4 3 GMFP Algorithm : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 8 3.1 Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.2 Connection reduction phase . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.3 Fermat point calculation phase . . . . . . . . . . . . . . . . . . . . . . . 9 3.4 Backbone construction phase . . . . . . . . . . . . . . . . . . . . . . . . . 12 4 Simulation Results : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 14 4.1 Environment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 4.2 Total routing distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 4.3 Packet transmission delay . . . . . . . . . . . . . . . . . . . . . . . . . . 22 4.4 Packet delivery ratio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.5 Node energy consumption . . . . . . . . . . . . . . . . . . . . . . . . . . 28 5 Conclusion and Future Work : : : : : : : : : : : : : : : : : : : : : : : : : 31 5.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 5.2 Future work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 Appendix : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 33 A Fermat Point Calculation : : : : : : : : : : : : : : : : : : : : : : : : : : : 33 References : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 37 Vita : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 39

    [1] Y.-B. Ko and N. H. Vaidya, “Geocasting in mobile ad hoc networks; location-based
    　　multicast algorithms,” in Proceedings of 2nd IEEE Workshop on Mobile Computing
    　　Systems and Applications (WMCSA’ 99), pp. 101–110, Feb. 1999.
    [2] Y.-B. Ko and N. H. Vaidya, “Location-aided routing (LAR) in mobile ad hoc networks,”
    　　in Proceedings of the 4th annual ACM/IEEE international conference on
    　　Mobile computing and networking, pp. 66–75, Oct. 1998, Dallas, Texas, United
    　　States.
    [3] W.-H. Liao, Y.-C. Tseng, and J.-P. Sheu, “GRID: A fully location-aware routing
    　　protocol for mobile ad hoc networks,” Telecommunication Systems, vol. 18, no. 1,
    　　pp. 37–60, Sept. 2001.
    [4] W.-H. Liao, Y.-C. Tseng, K.-L. Lo, and J.-P. Sheu, “Geogrid: A geocasting protocol
    　　for mobile ad hoc networks based on grid,” Journal of Internet Technology, vol. 1,
    　　no. 2, pp. 23–32, Dec. 2000.
    [5] C.-C. Shen and C. Jaikaeo, “Ad hoc multicast routing algorithm with swarm intelligence,”
    　　Mobile Networks and Applications, vol. 10, no. 1-2, pp. 47–59, Feb. 2005.
    [6] A. Mizumoto, H. Yamaguchi, and K. Taniguchi, “Cost-conscious geographic multicast
    　　on MANET,” in Proceedings of Sensor and Ad Hoc Communications and Networks
    　　(IEEE SECON 2004) (1st Int. Conf. on Sensor and Ad Hoc Communications
    　　and Networks), pp. 44–53, Oct. 2004, Santa Clara, USA.
    [7] M. Mauve, H. F̈ußler, J. Widmer, and T. Lang, “Position-based multicast routing for
    　　mobile ad-hoc networks,” Tech. Rep. TR-03-004, Department of Computer Science,
    　　University of Mannheim, July 2003.
    [8] T. Imielinski and J. Navas, “GPS-based geographic addressing, routing, and resource
    　　discovery,” Communication of the ACM, vol. 42, no. 4, pp. 86–92, Apr. 1999.
    [9] J. W. M. Mauve and H. Hartenstein, “A survey on position-based routing in mobile
    　　ad hoc networks,” IEEE Network Magazine, vol. 15, no. 6, pp. 30–39, Nov. 2001.
    [10] I. Stojmenovic, “Position based routing in ad hoc wireless networks,” IEEE Communications
    　　Magazine, vol. 40, no. 7, pp. 128–134, July 2002.
    [11] A. Rao, C. Papadimitriou, S. Shenker, and I. Stoica, “Geographic routing without
    　　location information,” in Proceedings of the 9th annual International Conference on
    　　Mobile computing and networking (MobiCom’03), pp. 96–108, Sept. 2003, San Diego,
    　　CA, USA.
    [12] S. Giordano and M. Hamdi, “Mobility management: The virtual home region,” Tech.
    　　Rep. SSC/1999/037, EPFL-ICA, Oct. 1999.
    [13] J. Li, J. Jannotti, D. S. J. De Couto, D. R. Karger, and R. Morris, “A scalable
    　　location service for geographic ad hoc routing,” in Proceedings of the 6th annual
    　　ACM/IEEE International Conference on Mobile computing and networking (Mobi-
    　　Com ’00), pp. 120–130, Aug. 2000, Boston, Massachusetts.
    [14] S. Basagni, I. Chlamtac, V. R. Syrotiuk, and B. A. Woodward, “A distance routing
    　　effect algorithm for mobility (DREAM),” in Proceedings of the 4th annual
    　　ACM/IEEE International Conference on Mobile computing and networking (MobiCom
    ’98), pp. 76–84, Oct. 1998, Dallas, Texas, United States.
    [15] H. ̈Uster and R. F. Love, “The convergence of the Weiszfeld algorithm,” Computers
    　　and Mathematics with Applications, vol. 40, no. 4, pp. 443–451, Aug. 2000.
    [16] J. Kruskal, “On the shortest spanning subtree of a graph and the traveling salesman
    　　problem,” In Proceedings of the American Mathematical Society, vol. 7, pp. 48–50,
    　　1956.

    下載圖示 校內：2008-07-24公開
    校外：2008-07-24公開
    QR CODE