車載網路可以藉由車輛之間彼此分享交通事件訊息, 來提升駕駛行車的安全性以及用路效率。為了提高車載網路訊息傳遞的成功率，佈署路側單元以協助訊息傳遞是主要的方法之一。然而，路側單元的佈署與維護成本昂貴。如何將路側單元佈署在適當的位置進而增加車載網路訊息傳遞的成功率是車載網路的一大研究議題。
我們針對耐延遲應用程式，將路側單元佈署問題轉化成耐延遲問題(Delay Tolerant Problem)，目標是讓越多車子能夠在一個合理的時間內收到訊息。我們期望在佈署相同的路側單元數量下，找出對耐延遲應用程式傳輸效能最好的部署位置。由於耐延遲問題是NP-hard的問題，我們運用基因演算法(Genetic Algorithm)來解決這個問題。藉由真實城市地圖模擬實驗產生的數據結果顯示，以封包遺失率和平均傳輸延遲做為考量，相較於另一種路側單元佈署演算法，針對耐延遲問題所佈署的路側單元對於車載網路擁有較佳的封包傳輸效能。

A Vehicular Ad Hoc Network (VANET) is a network which consists of moving vehicles equipped with wireless communication technology. To enhance the VANET connectivity, a special kind of infrastructure called Roadside Unit (RSU) has been proposed to be deployed to improve VANET connectivity. Effective placement of the RSUs is a significant requirement in improving reliability of VANET services.
Considering delay-tolerant applications, we model the RSU deployment problem as a Delay Tolerant Problem (DTP) and we seek to maximize the number of vehicles that can get information in a reasonable amount of time. The DTP is known to be NP-hard in its standard formulation. We therefore propose a genetic algorithm to solve it. Our evaluations show that our algorithm finds better results than another deployment algorithm in terms of packet loss rate and average transmission delay.

[1] S. Biswas and J. Mišić, "Establishing trust on VANET safety messages," Ad Hoc Networks, pp. 314-327, 2010.
[2] E. S. Cavalcante, A. L. Aquino, G. L. Pappa, and A. A. Loureiro, "Roadside unit deployment for information dissemination in a VANET: an evolutionary approach," in Proc. fourteenth international conference on Genetic and evolutionary computation conference companion, pp. 27-34, 2012.
[3] M. J. Piran and G. R. Murthy, "A Novel Routing Algorithm for Vehicular Sensor Networks," Wireless Sensor Network, vol. 2, pp. 919-923, 2010.
[4] P. Kamat, W. Xu, W. Trappe, and Y. Zhang, "Temporal privacy in wireless sensor networks," in Proc. 27th International Conference on Distributed Computing Systems (ICDCS'07), pp. 23-23, 2007.
[5] A. Bouch, M. A. Sasse, and H. DeMeer, "Of packets and people: a user-centered approach to quality of service," in Proc. Eighth International Workshop on Quality of Service (IWQOS), pp. 189-197, 2000.
[6] N. Wisitpongphan, F. Bai, P. Mudalige, V. Sadekar, and O. Tonguz, "Routing in sparse vehicular ad hoc wireless networks," Selected Areas in Communications, vol. 25, pp. 1538-1556, 2007.
[7] O. Trullols, M. Fiore, C. Casetti, C.-F. Chiasserini, and J. M. Barcelo Ordinas, "Planning roadside infrastructure for information dissemination in intelligent transportation systems," Computer Communications, vol. 33, pp. 432-442, 2010.
[8] B. Aslam, F. Amjad, and C. C. Zou, "Optimal roadside units placement in urban areas for vehicular networks," in Proc. IEEE Symposium on Computers and Communications (ISCC), pp. 000423-000429, 2012.
[9] P. Patil and A. Gokhale, "Improving the Reliability and Availability of Vehicular Communications Using Voronoi Diagram-Based Placement of Road Side Units," in Proc. IEEE 31st Symposium on Reliable Distributed Systems (SRDS), pp. 400-401, 2012.
[10] S.-I. Sou, "A power-saving model for roadside unit deployment in vehicular networks," Communications Letters, vol. 14, pp. 623-625, 2010.
[11] F. Zou, J. Zhong, W. Wu, D.-Z. Du, and J. Lee, "Energy-efficient roadside unit scheduling for maintaining connectivity in vehicle ad-hoc network," in Proc. 5th International Conference on Ubiquitous Information Management and Communication, pp. 64, 2011.
[12] S.-I. Sou and O. K. Tonguz, "Enhancing VANET connectivity through roadside units on highways," IEEE Transactions on Vehicular Technology, vol. 60, pp. 3586-3602, 2011.
[13] O. K. Tonguz, N. Wisitpongphan, and F. Bai, "DV-CAST: A distributed vehicular broadcast protocol for vehicular ad hoc networks," Wireless Communications, vol. 17, pp. 47-57, 2010.
[14] U.S.Census Bureau-TIGER/Line 2006 Second ed. Available: http://www.census.gov/geo/www/tiger/
[15] Centre for Applied Informatics (ZAIK) and the Institute of Transport Research German Aerospace Centre, Sumo—Simulation of Urban Mobility. Available: http://sourceforge.net/
[16] C. Lochert, B. Scheuermann, C. Wewetzer, A. Luebke, and M. Mauve, "Data aggregation and roadside unit placement for a vanet traffic information system," in Proc. fifth ACM international workshop on VehiculAr Inter-NETworking, pp. 58-65, 2008.
[17] S. Yao, B. Mukherjee, S. Yoo, and S. Dixit, "A unified study of contention-resolution schemes in optical packet-switched networks," Journal of Lightwave Technology, vol. 21, pp. 672, 2003.
[18] F. Bai, T. Elbatt, G. Hollan, H. Krishnan, and V. Sadekar, "Towards characterizing and classifying communication-based automotive applications from a wireless networking perspective," in Proc. IEEE Workshop on Automotive Networking and Applications (AutoNet), pp. 1-25, 2006.