車載網路環境下應用於時效性訊息廣播之路側通訊單元選擇策略

RSU Selection Strategies for Delay-Constrained Broadcasting in VANETs

呂東昱(Tung-Yu Lu)

指導教授 ： 黃啟富

國立中正大學/工學院/資訊工程學系/碩士(2015年)

摘要

在車載網路中，當道路中發生緊急事件時，路側通訊單元可以用來廣播訊息且提供一個有效率的傳播方式。然而如何選擇路側通訊單元來進行廣播，使得訊息傳輸同時保有較高傳輸成功率以及較低的傳輸花費需要權衡考量。在我們的論文中，我們將問題建立成一個具有時效性的路側通訊單元選擇問題，並且我們能確保網路中的車輛能夠在一個允許的訊息延遲時間限制內通過至少一個路側通訊單元並收到廣播訊息。另外我們透過將問題化簡為最小命中集合問題(Minimum hitting set problem)來證明我們的問題是一個NP-Complete的問題。而我們提出了兩個方法來解決這個問題，分別是貪婪挑選的方法以及基因演算法。最後我們使用真實地圖來進行模擬，而結果呈現我們的方法可以達成較高的傳輸成功率且只使用少量的路側通訊單元來進行廣播。

關鍵字

廣播機制 ； 緊急訊息 ； 路側通訊單元 ； 車載網路

並列摘要

When emergency events happen in vehicular ad hoc networks (VANETs), roadside units (RSUs) are used for messages broadcasting and efficient data dissemination. However, how to select broadcasting RSUs with low transmission cost and higher message receiving rate is a tradeoff. In this paper, we model this problem as a delay-constrained RSUs selection problem, which guarantees each vehicle in the network can drive through at least one RSU and receive the broadcasting messages in a given delay constrain. We first prove its NP-Complete by reducing to the minimum hitting set problem. Two solutions, a greedy selection heuristic and a genetic algorithm (GA), are then proposed to solve the problem. Finally, we evaluate the proposed methods in a real-world roadmap. The results show that our methods can achieve a high message receiving rate and a low number of selected RSUs.

並列關鍵字

broadcast ； warning message ； roadside unit (RSU) ； vehicular ad hoc network (VANET)

參考文獻

[2] M.C. Chuang and M.C. Chen, “DEEP: Density-Aware Emergency Message Extension Protocol for VANETs,” in IEEE Transactions on Wireless Communications, Vol. 12, No. 10, pp. 4983-4993, October 2013.

[4] M. Fogue, P. Garrido, F. J. Martinez, J.C. Cano, C. T. Calafate, and P. Manzoni, “An Adaptive System Based on Roadmap Profiling to Enhance Warning Message Dissemination in VANETs,” in IEEE/ACM Transactions on Networking, Vol. 21, No. 3, pp. 883-895, June 2013.

[5] O. Trullols, M. Fiore, C. Casetti, C.F. Chiasserini, and J.M. Barcelo Ordinas, “Planning Roadside Infrastructure for Information Dissemination in Intelligent Transportation Systems,” in Elsevier Computer Communications 33 (2010), pp. 432–442, 2010.

[6] T. Yan, W. Zhang, and G. Wang, Y. Zhang, “Access Points Planning in Urban Area for Data Dissemination to Drivers,” in IEEE Transactions on Vehicular Technology, Vol. 63, No. 1, pp. 390–402, January 2014.

[7] T. Yan and G. Wang, “Roadside Infrastructure Planning for Vehicle Trajectory Collection,” in Proceedings of IEEE Sarnoff Symposium, 2012, pp. 1–5.