| 摘要(英) |
Geographic routing algorithms are an attractive alternative to traditional ad hoc routing algorithms. Although geographic routing like Greedy Perimeter Stateless Routing (GPSR) is efficient to mobile ad hoc wireless networks, it requires that nodes be aware of their physical positions to inform their neighbors. In addition, if there are exist geometric holes within the network topology, which is called “dead end”, routing across dead ends in GPSR [5] will lead to a lot of redundant routing paths during data transmission and overloaded nodes in the boundaries of dead ends. In this thesis, we proposed an approach, according to virtual coordinate system based on detecting possible dead ends among nodes to improve the routing performance of existing geographic routing algorithms. When exchanging beacon message among nodes, each node will construct a local Voronoi diagram on the basis of the message information which receives from its neighbors simultaneously, each node draws perpendicular bisectors with all of its neighbors and then it checks if any segments on its transmission circle are not covered, which is called “dead end area”. Encountering those nodes which is existed the dead end area when data packets were greedily forwarded. It may cause transmission end up. In order to reduce this kind of situation, we assume every mobile node within network was a positive electron and destination node is a negative electron. In accordance with field theory [25] the packet forwarding among the shortest path from source node to destination node is inevitable, if the node exist one or more dead end area within its broadcast range, there was existed an pseudo positive electron which locate out of node’’s broadcast range, the pseudo electron’s location was sum of two vectors, one is mobile node to the start point of dead end area, and the other is mobile node to the end of dead end area. And pseudo electron will give a repulsive force to mobile node which will force virtual coordinate of nodes moving away from the dead end area. For the purpose of reducing the risk of encountering dead end situation. After the mention above, the nodes in the network are aware of the relative virtual coordinates and each of them was notified to the neighbors by exchanging beacon message. In the final of this study, results of the simulation show that our approach can improve geographic routing more efficient, In addition, our approach is resilient to various network shapes especially for U-shaped-like topology within the sparse network. In this thesis, some programming effort was implemented for comparison using the NS2 simulator platform[17]. The simulation results show that the average number of dead end occurrences was significantly reduced about 5 to 10 times of packet to encounter the dead end situation. When our dead end avoidance enhanced mechanism was applied. The packet delivery ratio was improved also. |
| 參考文獻 |
[1] Charles E. Perkins and Pravin Bhagwat. Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV). In Proceedings of the conference on Communications architectures, protocols and applications (SIGCOMM ’94), London, United Kingdom, August 1994.
[2] D. B. Johnson and D. A. Maltz. Dynamic source routing in ad hoc wireless networks. In Mobile Computing, volume 353. 1996.
[3] C Perkins, EM Royer. Ad hoc On-Demand Distance Vector (AODV) Routing, IETF Internet Draft, June 2002
[4] Kuhn, R. Wattenhofer, Y. Zhang, and A. Zollinger. Geometric ad-hoc routing: Of theory and practice. In Proceedings of PODC 2003, July 2003.
[5] 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.
[6] B. Leong, B. Liskov, and R. Morris. Geographic routing without planarization. In Proceedings of NSDI 2006, May 2006.
[7] B. Leong, S. Mitra, and B. Liskov. Path vector face routing: Geographic routing with local face information. In Proceedings of ICNP 2005, November 2005.
[8] Chou, C.-H. Ssu, K.-F. Jiau, H. C. Geographic Forwarding with Dead end Reduction in Mobile Ad Hoc Networks, appears in Vehicular Technology, IEEE Transactions on Publication Date: July 2008
[9] FRANZ AURENHAMMER. Voronoi Diagrams —A Survey of a Fundamental Geometric Data Structure, In Proceedings of ACM Computing Surveys, Vol. 2.3, No. 3, September 1991
[10] Nakagawa, H.; Ishida, K.; Ohta, T.; Kakuda, Y.; GOLI: Greedy On-Demand Routing Scheme Using Location Information for Mobile Ad Hoc Networks, Proceedings of Distributed Computing Systems Workshops, 2006. ICDCS Workshops 2006. 26th IEEE International Conference on 04-07 July 2006 Page(s):1 - 1
[11] Ben Leong; Liskov, B.; Morris, R.; Greedy Virtual Coordinates for Geographic Routing Network Protocols, 2007. ICNP 2007. IEEE International Conference on 16-19 Oct. 2007 Page(s):71 - 80
[12] G. G. Finn,;“Routing and Addressing Problems in Large MetropolitanScale Internetworks,” Tech. Rep. ISI/RR87180,Information Sciences Institute, University of Southern California, Mar. 1987.
[13] Xiaoyan Hong Kaixin Xu Gerla, M. California Univ., Los Angeles, CA; Scalable routing protocols for mobile ad hoc networks This paper appears in: Network, IEEE Publication Date: Jul/Aug 2002
[14] S. Basagni, I. Chlamtac, V. R. Syrotiuk, and B. A.Woodward, “A Distance Routing Effect Algorithm for Mobility (DREAM),” Proceedings of the IEEE International Conference on Mobile Computing and Networking, pp. 76–84, Oct. 1998.
[15] N. Arad and Y. Shavitt, “Minimizing Recovery State in Geographic AdHoc Routing,” Tech. Rep. EE49, School of Electrical Engineering, Tel Aviv University, Sept. 2005.
[16] Q. Fang, J. Gao, and L. Guibas, “Locating and Bypassing Holes in Sensor Networks,” ACM/Springer Journal of Mobile Networks and Applications, vol. 11, no. 2, pp. 187–200, Apr. 2006.
[17]K. Fall and K. Varadhan (editors), The ns Manual (ns Notes and Documentation).TheVINTproject,www.isi.edu/nsnam/ns/nsdocumentation. html,Nov. 2005.
[18] PalChaudhuri, S. Le Boudec, J.-Y. Vojnovic, M. Comput. Sci., Rice Univ., Houston, TX, USA; Perfect simulations for random trip mobility models; appears in: Simulation Symposium, 2005. Proceedings. 38th AnnualPublication Date: 4-6 April 2005 On page(s): 72- 79
[19] B. Hofmann-Wellenhof, H. Lichtenegger, and J. Collins, “Global Positioning System: Theory and Practice,” 4th Edited, Springer Verlag, 1997.
[20] F. P. Preparata and M. I. Shamos, Computational Geometry: An Introduction (Monographs in Computer Science). Springer, New York, Aug. 1985.
[21] R. Fonseca, S. Ratnasamy, J. Zhao, C. T. Ee, D. Culler, S. Shenker, and Stoica. Beacon vector routing: Scalable point-to-point routing in wireless sensornets. In Proceedings of NSDI 2005, May 2005.
[22] Q. Fang, J. Gao, L. J. Guibas, V. de Silva, and L. Zhang. GLIDER:Gradient landmark-based distributed routing for sensor networks. In Proceedings of IEEE Infocom '05, March 2005.
[23] Ben Leong; Liskov, B.; Morris, R.; Greedy Virtual Coordinates for Geographic Routing Network Protocols, 2007. ICNP 2007. IEEE International Conference on 16-19 Oct. 2007 Page(s):71 - 80 Digital Object Identifier 10.1109/ICNP.2007.4375838
[24] Jinyang Li John Jannotti Douglas S. J. De Couto David R. Karger ; A Scalable Location Service for Geographic Ad Hoc Routing in M.I.T. Laboratory for Computer Science
[25] http://en.wikipedia.org/wiki/Field_theory_%28mathematics%29
[26] http://en.wikipedia.org/wiki/Coulomb%27s_law
[27] http://en.wikipedia.org/wiki/Law_of_cosines |
[Endnote RIS 格式]
[相關文章]
[文章引用]
[完整記錄]
[館藏目錄]
[檢視]
plurk
funp
live
udn
HD
myshare
netvibes
friend
youpush
delicious
baidu
Google bookmarks
del.icio.us
hemidemi
facebook
twitter
google
reddit