臺灣博碩士論文加值系統

由於在無線網路中相同的頻段的頻寬是有限的，我們要如何將這些頻寬最大化的利用將是這個領域中一個很重要的課題。分群演算法在隨意行動網路下普遍的被用在管理節點，使其成為一個階層化的網路架構。網路階層化可以避免管理訊息在網路中造成泛流的現象，達到將多出來的頻寬拿去做更有效率運用的目的。但是考慮到現今的無線隨意網路分群演算法，往往都只能做到節點短時間的狀態穩定，當有大量的節點處於不穩定的狀態時，網路的整體效能就下降了。於是本論文中提出一種新的想法，想要讓節點盡可能長久的維持一個狀態不輕易的變換。我們發現人們在上班(學) 時，會傾向走同一條路線，若我們將這些歷史軌跡放進分群演算法加以利用，節點彼此之間能知道對方的未來路徑。因此節點在選擇群組首領時能選擇盡可能通訊時間長的加入其群組，於是選出來的群組首領更加穩定，進而提昇整體的網路效能。而本方法要傳送軌跡的這個缺點，本論文中也提出解決方法，使用路徑壓縮使我們的成本盡可能的降低。最後我們與Modified DMAC 演算法比對，在模擬結果顯示我們的方法能減少約20% 左右的重新分群次數。

　　Since wireless network has limited bandwidth spectrum, it is preferable to reuse the same spectrum for wireless nodes that are trying to access this particular network. Clustering algorithm has been widely used in mobile ad hoc network (MANET) which is built as a hierarchical structure.With clustering algorithm, the messages that are transmitted between nodes can avoid the flooding effect. Vehicular ad hoc network (VANET) is an extension to the MANET, which includes high mobility to the MANET. The messages transmitted consist of control message which might include vehicular information such as mobility, location, etc.Steady state is defined as the time the vehicular continuously transfers messages to each other. In current implementations of VANET, the algorithms provided cannot provide a long period of time to obtain a steady state. Once vehicular cannot keep a steady state, the throughput would degrade as well. In this thesis, we propose the Mobility Prediction Clustering Algorithm (MPC). This method uses the history trace to predict vehicular future location. After evaluating the location, vehicular transmit this information to its neighbors. MPC assigns a clusterhead to a specific vehicular that can consistently communicate with other vehicular for a long period of time; thus, providing long period of steady state.Our result shows that with lengthy vehicular steady state, the network can achieve higher throughput. Although the result might increase the throughput, since MPC needs to transmit its history path to its neighbors, there is an overhead that should be minimized. Thus, we designed a path compression algorithm to reduce message cost. Finally, in our simulation, we compare our results with Modified DMAC. The result shows that the proposed algorithm can reduce the number of cluster change per vehicular by 20%.

目錄
指導教授推薦書
口試委員會審定書
授權書. . . . . . . . . . . . . . iii
誌謝. . . . . . . . . . . . . . iv
中文摘要. . . . . . . . . . . . . . v
英文摘要. . . . . . . . . . . . . . vi
目錄. . . . . . . . . . . . . . viii
表目錄. . . . . . . . . . . . . . xi
圖目錄. . . . . . . . . . . . . . xii
1 序論. . . . . . . . . . . . . . 1
1.1 相關背景. . . . . . . . . . . . . . 1
1.2 研究動機. . . . . . . . . . . . . . 2
1.3 研究目的. . . . . . . . . . . . . . 4
1.4 論文架構. . . . . . . . . . . . . . 5
2 相關研究. . . . . . . . . . . . . . 7
2.1 分群程序步驟. . . . . . . . . . . . . . 7
2.1.1 初始階段(Initial Stage). . . . . . . . . . . . . . 7
2.1.2 發送與接收階段(Reception and TransmissionPhase). . . . . . . . . . . . . . 7
2.1.3 維護階段(Maintenance Phase). . . . . . . . . . . . . . 8
2.2 節點狀態. . . . . . . . . . . . . . 8
2.3 現有車用行動通訊網路分群演算法. . . . . . . . . . . . . . 9
2.3.1 最小ID 演算法(Lowest-ID Clustering). . . . . . . . . . . . . . 9
2.3.2 最大連接度演算法(Highest Connectivity Clustering). . . . . . . . . . . . . . 12
2.3.3 分散且可移動調適分群演算法(Distributed and Mobility-Adaptive Clustering). . . . . . . . . . . . . . 14
2.3.4 改良式分散且可移動調適演算法(Modified Distributed and Mobility-Adaptive Clustering. . . . . . . . . . . . . . 16
3 基於行動預測之車用行動通訊網路分群演算法. . . . . . . . . . . . . . 20
3.1 MPC 運作敘述. . . . . . . . . . . . . . 20
3.1.1 MPC 十字路口等待的運作. . . . . . . . . . . . . . 20
3.2 MPC 的演算法流程圖. . . . . . . . . . . . . . 20
3.3 MPC 軌跡記錄格式以及軌跡檔大小估算. . . . . . . . . . . . . . 21
3.4 MPC 路徑壓縮. . . . . . . . . . . . . . 23
3.4.1 路徑壓縮之虛擬碼. . . . . . . . . . . . . . 23
3.4.2 路徑壓縮之實例. . . . . . . . . . . . . . 26
3.5 MPC 分群程式虛擬碼. . . . . . . . . . . . . . 27
3.5.1 初始階段. . . . . . . . . . . . . . 28
3.5.2 接受Hello 訊息. . . . . . . . . . . . . . 29
3.5.3 接收加入訊息. . . . . . . . . . . . . . 35
3.5.4 連結失效. . . . . . . . . . . . . . 35
4 模擬實驗與結果分析. . . . . . . . . . . . . . 37
4.1 模擬環境與參數設定. . . . . . . . . . . . . . 37
4.2 實驗結果與分析. . . . . . . . . . . . . . 37
5 結論與未來研究方向. . . . . . . . . . . . . . 51
參考文獻. . . . . . . . . . . . . . 52
表目錄
4.1 不同環境下每台車輛平均的overhead . . . . . . . . . . . . . . 48
4.2 MPC 在不同壓縮容忍值下的結果. . . . . . . . . . . . . . 48
4.3 MPC 車輛佔不同比例的分群次數結果. . . . . . . . . . . . . . 49
圖目錄
1.1 車用行動通訊網路現有廣播協定分類. . . . . . . . . . . . . . 3
1.2 未分群造成的泛流問題. . . . . . . . . . . . . . 6
1.3 分群結果示意圖. . . . . . . . . . . . . . 6
2.1 三種網路節點狀態. . . . . . . . . . . . . . 9
2.2 Lowest ID 示意圖. . . . . . . . . . . . . . 11
2.3 最大連結度演算法示意圖(一) . . . . . . . . . . . . . . 12
2.4 最大連結度演算法示意圖(二) . . . . . . . . . . . . . . 13
2.5 DMAC 快速超車及會車情境示意圖. . . . . . . . . . . 16
2.6 Modified DMAC 快速超車及會車情境示意圖. . . . . . 18
2.7 十字路口等待紅燈分群示意圖. . . . . . . . . . . . . . 19
3.1 MPC 十字路口等待分群示意圖. . . . . . . . . . . . . . 21
3.2 MPC 演算法流程圖. . . . . . . . . . . . . . 22
3.3 自用小客車最主要用途及其每次行駛時間. . . . . . . . . . . . . . 23
3.4 路徑壓縮之虛擬碼. . . . . . . . . . . . . . 24
3.5 路徑壓縮示意圖. . . . . . . . . . . . . . 26
3.6 初始化虛擬碼. . . . . . . . . . . . . . 29
3.7 接收Hello 訊息虛擬碼. . . . . . . . . . . . . . 31
3.8 路徑預測示意圖. . . . . . . . . . . . . . 34
3.9 接收加入訊息虛擬碼. . . . . . . . . . . . . . 35
3.10 連結失效虛擬碼. . . . . . . . . . . . . . 36
4.1 Greenville 區域模擬地圖. . . . . . . . . . . . . . 38
4.2 Modfied DMAC 與MPC 在方格地圖執行結果. . . . . . . . . . . . . . 39
4.3 Modified DMAC 與MPC 在Greenville 地圖執行結果. . . . . . . . . . . . . . 39
4.4 Modified DMAC 在方格中不同TTL 對分群次數的影響. . . . . . . . . . . . . . 40
4.5 Modified DMAC 在Greenville 中不同TTL 對分群次數的影響. . . . . . . . . . . . . . 40
4.6 MPC 在方格中不同TTL 對分群次數的影響. . . . . . . . . . . . . . 41
4.7 MPC 在Greenville 中不同TTL 對分群次數的影響. . . . . . . . . . . . . . 41
4.8 Modified DMAC 在方格中不同TTL 對群組數量的影響. . . . . . . . . . . . . . 43
4.9 Modified DMAC 在Greenville 中不同TTL 對群組數量的影響. . . . . . . . . . . . . . 43
4.10 MPC 在方格中不同TTL 對群組數量的影響. . . . . . . . . . . . . . 44
4.11 MPC 在Greenville 中不同TTL 對群組數量的影響. . . . . . . . . . . . . . 44
4.12 Modified DMAC 在方格中不同Hello 間隔對分群次數影響. . . . . . . . . . . . . . 46
4.13 Modified DMAC 在Greenville 中不同Hello 間隔對分群次數影響. . . . . . . . . . . . . . 46
4.14 MPC 在方格中不同Hello 間隔對分群次數影響. . . . . . . . . . . . . . 47
4.15 MPC 在Greenville 中不同Hello 間隔對分群次數影響. . . . . . . . . . . . . . 47

[1] S. Corson and J.Mackerm, “Moblie Ad Hoc Networking (MANET): Routing Protocol Performance issues and Evaluation Considerations,” Network Working Group, Jan. 1999.
[2] J. Bersen and D. Manivannan, “Unicast Routing Protocols for Vehicular ad hoc Networks: A Critical Comparison And Classification,” Pervasive and Mobile Computing, Vol. 5, Issue 1, pp. 1-18, 2009.
[3] R. Chris Drane and R. Chris, Positioning Systems in Intelligent Transportation Systems, MA, USA, Artech House, pp. 369-370, 1998.
[4] 李麗君、劉宏飛、楊祖元、葛利嘉, “Broadcasting Methods in Vehicular Ad Hoc Networks,” Journal of Software, Vol.21, No.7, pp.1620-1634, 2010.
[5] A. Bohlooli and K. Jamshidi, “A GPS-free method for vehicle future movement directions prediction using SOM for VANET,” Applied Intelligence, Vol. 36, Issue 3, pp. 685-697, 2012.
[6] Y. Gunter, B. Wiegel and H. P. Grobmann, “Cluster-based Medium Access Scheme for VANETs,” IEEE Intelligent Conference on Transportation Systems , Sept. 30 - Oct. 3, 2007.
[7] G. Wolny, “Modified DMAC Clustering Algorithm for VANETs” Third International Conference on Systems and Networks Comunications, pp. 268-273, Oct. 2008.
[8] E. Souza, I. Nikolaidis and P. Gburzynski, “A New Aggregate Local Mobility (ALM) Clustering Algorithm for VANETs,” IEEE International Conference on Communications, May 23 - May 27, 2010.
[9] D. Gavalas, G. Pantziou, C. Konstantopoulos and B. Mamalis,“Lowest-ID with Adaptive ID Reassignment: A Novel Mobile Ad-Hoc Networks Clustering Algorithm,” Wireless Pervasive Computing,2006 1st International Symposium, 2006.
[10] M. Gerla and J. T. Tsai, “Multiuser, Mobile, Multimedia Radio Network,”Wireless Networks, vol. 1, pp. 255–65, Oct. 1995.
[11] S. Basagni, “Distributed and mobility-adptive clustering for ad hoc networks,” Erik Jonsson School of Engineering and Computer Science,July, 1998.
[12] 中華民國交通部, http:// www.motc.gov.tw/ ch/ home.jsp?id=56&;websitelink=statistics101.jsp&;parentpath=0,6&;qyear=2011.99 年自用小客車使用狀況調查報告.
[13] VanetMobisim, http://vanet.eurecom.fr.
[14] Network Simulator 2, http://www.isi.edu/nsnam/ns/.
[15] United States Census Bureau, http:// www.census.gov/ geo/ www/tiger/tgrshp2010/tgrshp2010.html.