Optimizing Multi-Hop Routing Protocols in Urban Vehicular Ad-Hoc Networks: Problem Identification, Analysis and Design

摘要 車用無線隨意網路的多重跳躍路由協定能提供有效的傳輸方式來克服傳輸範圍之限制，期使車用通訊傳輸之訊息能夠傳往更遠的節點。基於車用網路的移動性和一般隨意網路之不同，原有的多重跳躍路由協定並沒有辦法在車用隨意網路下運作得到可以接受的效能。目前相關之研究較少討論到道路條件對於路由效能之影響，因此本論文針對車用環境參數提出一個路由存活時間預測機制來改善一般多重跳越路由協定在車用隨意網路下之效能。由於車用環境的移動性主要受限於道路的條件限制，例如：車道之數目或是紅綠燈的週期時間，首先本論文針對車用環境的不同條件參數來探討車用環境和多重跳躍路由協定效能之間的關係。經由探討分析後得知，路由協定的效能低落主要是由於封包傳輸的路由存活時間易受到車輛相對的移動而縮短，如車輛的轉彎或是停下等因素皆易造成路由可提供的傳輸時間中斷。基於這些相對移動而造成路由中斷之原因，本論文提出一個預測模型針對不同車輛之相對位置關係來推算出可能的路由存活時間。基於此模型推算出的路由存活時間，本論文提出一個分散式路由選擇優先機制，基於路由存活時間預測模型計算出不同鄰近車輛作為中繼點之優先順序，選擇較不易受到中斷的中繼節點幫助封包的傳輸，並以此機制提升路由之傳輸品質。除了能藉由選擇較長路由存活時間提升多重跳躍路由協定之效能，此機制亦能解決路由建立時期封包擁塞之問題。經由模擬結果分析，此機制可在不同道路參數條件下，相對於原本之多重跳越路由協定提升約百分之二十左右之效能。由此可知，本論文所提出之架構能針對車用隨網路之多重跳躍路由協定有效的改善路由存活時間以達到最佳化之提升。ABSTRACT Vehicular Ad Hoc Network (VANET) is the technique for overcoming the limit of transmission range in wireless vehicular communication. Traditional ad hoc multi-hop routing protocols may not achieve optimal performance in VANET, because specified mobility pattern affects the packets transmission. However, the effect of road conditions on performance of routing protocols is seldom discussed in current related work. Hence, this thesis proposes a route lifetime predicting mechanism with road parameters of vehicular environment to improve the performance of ad-hoc routing protocols under VANET environment. Because mobility pattern of vehicles is limited by road conditions, such as numbers of lanes and waiting time of traffic light, we first discuss the relationship between routing performance and these different road conditions. After study and analysis, it is concluded that the main problem is shorter route lifetime because of route failure which is caused by inter-vehicle mobility. Turning or stopping at the intersections of the vehicles which participate in the route would cause the route failure. Based on mobility pattern, we propose a route lifetime predicting model that can predict the inter-vehicle lifetime with inter-vehicle geographical information. Based on this predicted route lifetime model, we also propose a distributed route lifetime priority mechanism that can help to select the route with longer route lifetime to increase the delivery ratio of packet transmission. After simulation under topology with different road conditions, the proposed route lifetime mechanism can increase about 20\% performance. The proposed route lifetime mechanism can optimally improve the performance of routing protocol under vehicular environment.ABSTRACT . . . . . . . . . . . . . . . . ii LIST OF TABLES .....................v LIST OF FIGURES ...................vi CHAPTER 1 INTRODUCTION . . . . . . .1 CHAPTER 2 BACKGROUND . . . . . . . .4 2.1 DSRC . . . . . . . . . . . . . . .4 2.1.1 History . . . . . . . . . . 4 2.1.2 DSRC Architecture Overview .5 2.1.3 MAC Extension . . . . . . . 6 2.1.4 Applications of DSRC . . . .7 2.2 Routing under MANET . . . . . . . 7 2.2.1 Dissemination . . . . . . . 9 2.2.2 Traditional Ad Hoc Routing .9 2.3 Routing under VANET . . . . . . . 11 2.3.1 Based on Broadcasting . . . 11 2.3.2 Based on Probability . . . .13 2.3.3 Based on Mobility Pattern . 13 2.3.4 Based on Mobility Prediction . 14 CHAPTER 3 SIMULATION SETUP . . . . . . .15 3.1 SUMO . . . . . . . . . . . . . . . . .15 3.2 TransTCL . . . . . . . . . . . . . . .18 3.3 Simulation Scenarios . . . . . . . . .20 CHAPTER 4 PROBLEM IDENTIFICATION . . . .26 4.1 Reasons of Dropped Packets . . . . . .26 4.1.1 Classification of Dropped Packets . . 27 4.1.2 Statistics Tool . . . . . . . . . . . 30 4.1.3 Summary . . . . . . . . . . . . . . . 33 4.2 Numbers of Lanes . . . . . . . . . . . . . . 34 4.2.1 Delivery Ratio . . . . . . . . . . . .34 4.2.2 Statistics for Reason of Dropping Packets . .38 4.2.3 Statistics for Multiple Simulataneous Flows .40 4.3 Waiting Time of Traffic Light . . . . . . . . . . . .42 4.3.1 Delivery Ratio . . . . . . . . . . . . . . . 42 4.3.2 Statistics for Reason of Dropping Packets . .43 4.4 Conclusion . . . . . . . . . . . . . . . . . . . . .47 CHAPTER 5 ANALYSIS OF ROUTE LIFE TIME MODEL 49 5.1 Real Route Life Time . . . . . . . . . . . . 49 5.2 Route Life Time Model . . . . . . . . . . . .51 5.2.1 Definition and Assumption . . . . . . 52 5.2.2 Pair of Nodes are at Same Road . . . .55 5.2.3 Pair of Nodes are on Different Roads .65 5.2.4 Summary . . . . . . . . . . . . . . . 68 5.3 Prediction of Route Life Time . . . . . . . .70 CHAPTER 6 PROTOCOL DESIGN AND EVALUATION . . .74 6.1 Geographical Information Mechanism . . . . .74 6.1.1 Distance Priority Mechanism . . . . .76 6.1.2 Direction Priority Mechanism ....78 6.2 Route Life Time Mechanism . . . . . . . . . 80 6.3 Performance Evaluation . . . . . . . . . . .82 6.3.1 Overhead . . . . . . . . . . . . . . 82 6.3.2 Grid Topology . . . . . . . . . . . .84 6.3.3 City Topology . . . . . . . . . . . .86 CHAPTER 7 CONCLUSION AND FUTURE WORK . . . . .91 REFERENCES . . . . . . . . . . . . . . . . . . . . 9