一种车辆自组织网络中路由协议的设计与实现
摘要
车载自组织网络(VANET)有很多自己的特点:网络中没有可靠的网络基础设施可供使用,车辆间必须建立起自组织网络来实现相互通信,可能无法使用无线基站;车辆的快速运动使得网络的拓朴结构和状态变化很快,节点间没有较长的通信会话期;相对而言节点功耗和内存等因素不是最关键因素。车辆间也许会有很多障碍物,使得本可通信的节点变得不能传送数据。
论文描述一种车载自组织网络的被动地理路由算法(Passive Geographical Routing protocol)的设计、实现和模拟实验进行性能测试的过程,该路由算法基于可用的城市交通地图和节点地理位置信息。路由算法使用从车辆的GPS设备上收集到的实时地理位置信息和城市交通图做路由决策。地理位置信息用来预测节点的位置,以便路由决策。城市交通图用以计算节点速度的稳定时间和协助预测节点位置,使用实时的交通数据来评估PGR协议。
论文使用上海市交通局提供的实时车辆GPS信息,并在NS2(Network Simulator 2)仿真平台中设计并实现协议。通过与当前流行的无线路由协议进行性能比较与分析。在不同测试指标下均表现出可观的性能:与AODV相对比,只有1/5的路由开销,而达到了同样的高包递送率(约75%)。由于未使用广播路由机制,路径长度过(1.5倍)和点到点延迟(3倍)则有所增涨。
Vehicular ad hoc networks(VANET) have some characteristics: No stable infrastructures are available, vehicles must setup an ad hoc network to communication and may not use any base stations. Due to the high speed of vehicles, network topology and states may change rapidly. Nodes may perhaps have no long communication session time, while power and memory are not problems in VANET. VANET may have many obstacles between nodes, which makes potential network data exchange availability impossible.
In this work, we present a routing mechanism for VANET, the Passive Geographical Routing protocol, which uses prior location information of the nodes and city road map. Our routing mechanism is to use geographical location information, obtained from on-board GPS devices, and city road map. Geographical location information will be used to prognosticate nodes’new posi-tions in the network, which make routing strategy. City road map is used to determine nodes’direction stable dura-tion and assist the prognostication. We evaluate PGR with realistic traffic data.
In this work, we use the GPS data collecting from Department of Transportation in Shang hai, design and implementing the protocol in NS2 simulation platform. From the simulating results, we show that, compare with AODV, PGR results only 1/5 overhead but also gives the same delivery performance(75%). Since it does not use broadcasting, average path(1.5 times) and point-to-point delay(3 times) are longer.
论文描述一种车载自组织网络的被动地理路由算法(Passive Geographical Routing protocol)的设计、实现和模拟实验进行性能测试的过程,该路由算法基于可用的城市交通地图和节点地理位置信息。路由算法使用从车辆的GPS设备上收集到的实时地理位置信息和城市交通图做路由决策。地理位置信息用来预测节点的位置,以便路由决策。城市交通图用以计算节点速度的稳定时间和协助预测节点位置,使用实时的交通数据来评估PGR协议。
论文使用上海市交通局提供的实时车辆GPS信息,并在NS2(Network Simulator 2)仿真平台中设计并实现协议。通过与当前流行的无线路由协议进行性能比较与分析。在不同测试指标下均表现出可观的性能:与AODV相对比,只有1/5的路由开销,而达到了同样的高包递送率(约75%)。由于未使用广播路由机制,路径长度过(1.5倍)和点到点延迟(3倍)则有所增涨。
Vehicular ad hoc networks(VANET) have some characteristics: No stable infrastructures are available, vehicles must setup an ad hoc network to communication and may not use any base stations. Due to the high speed of vehicles, network topology and states may change rapidly. Nodes may perhaps have no long communication session time, while power and memory are not problems in VANET. VANET may have many obstacles between nodes, which makes potential network data exchange availability impossible.
In this work, we present a routing mechanism for VANET, the Passive Geographical Routing protocol, which uses prior location information of the nodes and city road map. Our routing mechanism is to use geographical location information, obtained from on-board GPS devices, and city road map. Geographical location information will be used to prognosticate nodes’new posi-tions in the network, which make routing strategy. City road map is used to determine nodes’direction stable dura-tion and assist the prognostication. We evaluate PGR with realistic traffic data.
In this work, we use the GPS data collecting from Department of Transportation in Shang hai, design and implementing the protocol in NS2 simulation platform. From the simulating results, we show that, compare with AODV, PGR results only 1/5 overhead but also gives the same delivery performance(75%). Since it does not use broadcasting, average path(1.5 times) and point-to-point delay(3 times) are longer.
引文
[1] JOHNSON, D. B., AND MALTZ, D. A. Dynamic source routing in ad hoc wireless neworks. In Mobile Computing, T. Imielinski and H. Korth, Eds.,vol. 353. Kluwer Academic Publishers, 1996.
[2] KARP, B., AND KUNG, H. Gpsr: Greedy perimeter stateless routing for wireless networks. Proceedings of the Annual International Conference on Mobile Computing and Networking, MOBICOM (2000), 243–254.
[3] http://www.cn.uni-duesseldorf.de/staff/kiess/so- -ftware/hls-ns2-patch.
[4] PERKINS, C. Ad hoc on demand distance vector(AODV)routing.Internet-Draft, draft-ietf-m- -anet-aodv-04.txt, Oct. 1999.
[5] Josh Broch, David A. Maltz, etc. A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols. MobiCom, October 1998.
[6] JAIN, S., FALL, K., AND PATRA, R. Routing in a delay tolerant network. vol. 34, pp. 145– 157.
[7] PERKINS, C. E., AND BHAGWAT, P. Highly dynamic destination-sequenced distance-vector routing (dsdv) for mobile computers. Computer Communications Review 24, 4 (1994).
[8] Young-BaeKo and Nitin H. Vaidya. Location-Aided Routing (LAR) in Mobile Ad Hoc Networks. MOBICOM, pages 66–75, November 1998.
[9] Utku Günay Acer, Shivkumar Kalyanaraman, Alhussein A. Abouzeid.Weak State Routing for Large Scale Dynamic Networks.MobiCom’07, September 9–14, 2007.
[10] A.Vahdat and D. Becker. Epidemic Routing for Partially Connected Ad Hoc Networks. Technical Report CS-200006, Duke University, April 2000.
[11] Vladimir Byc., Bret Hul., Allen Miu., Hari Bal., and Samuel Mad..A Measurement Study of Vehicular Internet Access Using In Situ WiFi Networks. MobiCom’06, Sep 24–29, 2006.
[12] Philippe Golle, Dan Greene, and Jessica Staddon. Detecting and correcting malicious data in VANETs. In Proceedings of the first ACM workshop on Vehicular ad hoc networks, pages 29–37. ACM Press, 2004.
[13] Francisco J. Ros, Pedro M. Ruiz. Implementing a New Manet Unicast Routing Protocol in NS2. December, 2004.
[14] CMU Monarch Project. ftp.monarch.cs.cmu.Edu /pub/monarch/wireless-sim/ns-cmu.ps,Aug 1999.
[15] Network simulator. ns-2. http://www.isi.edu/nsn- -am/ns.
[16] Gary R.Wright and W.Richard Stevens. TCP/IP Illustrated, Volume 2: The Implementation. Addison-Wesley, Reading, Massachusetts, 1995.
[17] W. Richard Stevens. TCP/IP Illustrated, Volume 1: The Protocols, Addison-Wesley, 1994.
[18] David C. Plummer. An Ethernet address resolution protocol: Or converting network protocol addresses to 48.bit Ethernet addresses for transmission on Ethernet hardware. RFC 826, November 1982.
[19] Josh Broch, David B. Johnson, and David A. Maltz. The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks. Internet-Draft,draft-ietf-manet-dsr- 00.txt, March 1998. Work in progress.
[20] Dmitri D. Perkins, Herman D. Hughes, and Charles B. Owen.Factors Affecting the Performance of Ad Hoc NetworksCommunications,IEEE, 2002
[21] B.Hull, V.Bychkovsky, Y.Zhang, K.Chen, etc. CarTel: A Distributed Mobile Sensor Computing System. In Proc. ACM SenSys,Nov.
[22] The FleetNet project. http://www.fleetnet.de.
[23] R. Morris , J. Janotti , F. Kaashoek , J. Li, and D. S. DeCouto.Carnet: A scalable ad hoc wireless network system. In Proc. of 9th ACM SIGOPS, page 127ff, Kolding, Denmark, September 2000.
[24] Raghavendra, Cauligi S.; Sivalingam, Krishna M.; Znati, Taieb (Eds.). Wireless Sensor Networks 1st ed. 2004.Corr 2nd printing, 2005, 442 p.
[25] LI, J., JANNOTTI, J., DECOUTO, D., KARGER, D., AND MORRIS, R. A scalable location service for geographic ad-hoc routing. In Proceedings of the Sixth Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom 2000) (Boston, MA, USA, Aug. 2000).
[26] Das, S.R., Perkins, C.E., Royer, E.M. Performance comparison of two on-demand routing protocols for adhoc networks. INFOCOM,2000.
[2] KARP, B., AND KUNG, H. Gpsr: Greedy perimeter stateless routing for wireless networks. Proceedings of the Annual International Conference on Mobile Computing and Networking, MOBICOM (2000), 243–254.
[3] http://www.cn.uni-duesseldorf.de/staff/kiess/so- -ftware/hls-ns2-patch.
[4] PERKINS, C. Ad hoc on demand distance vector(AODV)routing.Internet-Draft, draft-ietf-m- -anet-aodv-04.txt, Oct. 1999.
[5] Josh Broch, David A. Maltz, etc. A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols. MobiCom, October 1998.
[6] JAIN, S., FALL, K., AND PATRA, R. Routing in a delay tolerant network. vol. 34, pp. 145– 157.
[7] PERKINS, C. E., AND BHAGWAT, P. Highly dynamic destination-sequenced distance-vector routing (dsdv) for mobile computers. Computer Communications Review 24, 4 (1994).
[8] Young-BaeKo and Nitin H. Vaidya. Location-Aided Routing (LAR) in Mobile Ad Hoc Networks. MOBICOM, pages 66–75, November 1998.
[9] Utku Günay Acer, Shivkumar Kalyanaraman, Alhussein A. Abouzeid.Weak State Routing for Large Scale Dynamic Networks.MobiCom’07, September 9–14, 2007.
[10] A.Vahdat and D. Becker. Epidemic Routing for Partially Connected Ad Hoc Networks. Technical Report CS-200006, Duke University, April 2000.
[11] Vladimir Byc., Bret Hul., Allen Miu., Hari Bal., and Samuel Mad..A Measurement Study of Vehicular Internet Access Using In Situ WiFi Networks. MobiCom’06, Sep 24–29, 2006.
[12] Philippe Golle, Dan Greene, and Jessica Staddon. Detecting and correcting malicious data in VANETs. In Proceedings of the first ACM workshop on Vehicular ad hoc networks, pages 29–37. ACM Press, 2004.
[13] Francisco J. Ros, Pedro M. Ruiz. Implementing a New Manet Unicast Routing Protocol in NS2. December, 2004.
[14] CMU Monarch Project. ftp.monarch.cs.cmu.Edu /pub/monarch/wireless-sim/ns-cmu.ps,Aug 1999.
[15] Network simulator. ns-2. http://www.isi.edu/nsn- -am/ns.
[16] Gary R.Wright and W.Richard Stevens. TCP/IP Illustrated, Volume 2: The Implementation. Addison-Wesley, Reading, Massachusetts, 1995.
[17] W. Richard Stevens. TCP/IP Illustrated, Volume 1: The Protocols, Addison-Wesley, 1994.
[18] David C. Plummer. An Ethernet address resolution protocol: Or converting network protocol addresses to 48.bit Ethernet addresses for transmission on Ethernet hardware. RFC 826, November 1982.
[19] Josh Broch, David B. Johnson, and David A. Maltz. The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks. Internet-Draft,draft-ietf-manet-dsr- 00.txt, March 1998. Work in progress.
[20] Dmitri D. Perkins, Herman D. Hughes, and Charles B. Owen.Factors Affecting the Performance of Ad Hoc NetworksCommunications,IEEE, 2002
[21] B.Hull, V.Bychkovsky, Y.Zhang, K.Chen, etc. CarTel: A Distributed Mobile Sensor Computing System. In Proc. ACM SenSys,Nov.
[22] The FleetNet project. http://www.fleetnet.de.
[23] R. Morris , J. Janotti , F. Kaashoek , J. Li, and D. S. DeCouto.Carnet: A scalable ad hoc wireless network system. In Proc. of 9th ACM SIGOPS, page 127ff, Kolding, Denmark, September 2000.
[24] Raghavendra, Cauligi S.; Sivalingam, Krishna M.; Znati, Taieb (Eds.). Wireless Sensor Networks 1st ed. 2004.Corr 2nd printing, 2005, 442 p.
[25] LI, J., JANNOTTI, J., DECOUTO, D., KARGER, D., AND MORRIS, R. A scalable location service for geographic ad-hoc routing. In Proceedings of the Sixth Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom 2000) (Boston, MA, USA, Aug. 2000).
[26] Das, S.R., Perkins, C.E., Royer, E.M. Performance comparison of two on-demand routing protocols for adhoc networks. INFOCOM,2000.