臺灣博碩士論文加值系統

如何讓汽車代理人(Car-Agent, CAG)有效避開擁擠路段與掌握路況並且快速到達目的地是一件很重要的事，然而要達到上述條件的成立，即時性資訊的獲得變成非常重要，本文透過階層式架構方式按照不同的區域分別設立主機加以管理，且按照CAG行走所需範圍交予適當主機進行路徑規劃，利用最短路徑規劃方式，將每條路徑的平均旅行時間設為主要參數，透過主機規劃出最適旅行時間路徑。階層式主機(Hierarchical servers)的各路段資訊透過放置在路旁兩側無線感測器與CAG互動，透過定位方式CAG可以計算出通過路段的車速、時間，將資料傳送到路口單元(Road-Processing Unit, RPU)進行運算處理，了解當前負責路段路況並回傳給該轄區Level-1 servers紀錄，作為路徑規劃重要資訊。上述方法採取RPU歷史紀錄的累積方式，經過長期平均計算CAG車速下如果遇到突發事故例如塞車、車禍等等，通常不會即時性反應目前車況，本文解決上述路況的突發性變化時利用門檻值的公式能簡單換算出目前是由順暢變成擁擠或是擁擠變成順暢的路況，透過實驗成果證明能有效解決脈衝式路況變化下的問題並得到更正確的資訊及成果。

針對階層式主機而言，透過無線感測網路獲得即時性的交通資訊會讓資料量增加，所以透過我們兩種路徑搜尋方式(1)階層式路徑搜尋法(2)區域式路徑搜尋法，針對主機不同負载狀況使用不同方法，可以有效降低主機負载，提升運算效率。

To avoid a traffic jam on the road with a heavy load, it is important to collect the information for a Car-Agent (CAG) to approach the destination. Specially, Real-Time information is significant to help CAG to achieve the purpose mentioned above. Using a hierarchical server structure located at different location and processing the received data from the wireless sensors on the road, this thesis proposes a scheme to describe a shortest path for the CAGs. Besides the short geometric path needed for the CAGs, the shortest time is also needed to describe an optimal path for traveling. Comparing with the Accumulation History, the proposed scheme is with a benefit for a real time processing. Also, comparing with the previous method by Dijkstra, the proposed scheme employing the hierarchical server structure provides a time efficient method in the search of an optimal path.

中文摘要 I
Abstract III
誌 謝 IV
目 錄 V
表 目 錄 VIII
圖 目 錄 X
第一章、緒論 1
1.1 研究背景 1
1.2 研究動機與目的 4
第二章、文獻探討 7
2.1 地理資訊系統(Geographical information system, GIS) 9
2.2 全球定位系統 (Global Positioning System, GPS) 11
2.3 無線感測器(Wireless Sensor, WS) 11
2.4 無線感測器應用於交通監測 14
2.5 最短路徑規劃(Dijkstra) 18
第三章、研究方法 26
3.1 概要 26
3.2 以CAG與各階層主機互動流程 28
3.3 階層式路徑搜尋法(Hierarchical Searching Path Method, HSPM) 32
3.4 區域式路徑搜尋法(Region Searching Path Method, RSPM) 33
3.5 無線區域網路與CAG互動流程 36
3.6 WSN與RPU 運作方式 38
3.7 門檻值(T) 41
第四章、模擬實驗與預期結果 47
4.1累積歷史資料方式 47
4.2 加入門檻值實驗 49
4.3 最短路徑規劃比較成果 52
4.4 各搜尋路徑法之比較 56
4.5以路段權重比較出規劃路徑品質 57
4.5.1 25個節點地圖(終點設在地圖中間) 58
4.5.2 25個節點地圖(終點設在地圖對角) 60
4.5.3 100個節點地圖(終點設在地圖中間) 62
4.5.4 100個節點地圖(終點設在地圖對角) 64
4.5.5 400個節點地圖(終點設在地圖中間) 66
4.5.6 400個節點地圖(終點設在地圖對角) 68
4.6 三種搜尋法在搜尋花費時間上之比較 73
4.6.1 25個節點地圖 75
4.6.2 100個節點地圖 77
4.6.3 400個節點地圖 79
4.7 各搜尋路徑法成果比較 80
第五章、未來工作 83
第六章、總結 85
參考文獻 87

表目錄
表 1、交通部1996~2006年車輛統計表 7
表 2、GIS發展表 10
表 3、節點陣列值 19
表 4、塞車路短與速度設定 49
表 5、點1-13最短路徑的總路徑長度與時間花費 58
表 6、點1-13最快路徑的總路徑長度與時間花費 59
表 7、點1-25最短路徑的總路徑長度與時間花費 60
表 8、點1-25最快路徑的總路徑長度與時間花費 61
表 9、點1-55最短路徑的總路徑長度與時間花費 62
表 10、點1-55最快路徑的總路徑長度與時間花費 63
表 11、點1-100最短路徑的總路徑長度與時間花費 64
表 12、點1-100最快路徑的總路徑長度與時間花費 65
表 13、點1-210最短路徑的總路徑長度與時間花費 66
表 14、點1-210最快路徑的總路徑長度與時間花費 67
表 15、點1-400最短路徑的總路徑長度與時間花費 68
表 16、點1-400最快路徑的總路徑長度與時間花費 69
表 17、總時間比較 71

圖目錄
圖 1、WS架構圖 12
圖 2、無線器材分佈情況 15
圖 3、無線器材分佈情況 16
圖 4、三點交叉定位 17
圖 5、各點關聯權重圖 18
圖 6、與A相鄰之節點 20
圖 7、與B相鄰之節點 21
圖 8、與C相鄰之節點 22
圖 9、與D相鄰之節點 23
圖 10、與E相鄰之節點 24
圖 11、階層式架構 27
圖 12、CAG運作流程圖 30
圖 13、水波擴散搜尋法 32
圖 14、以紅點為中心畫出涵蓋所需節點 34
圖 15、圈選出涵蓋範圍 35
圖 16、RPU運作流程圖 37
圖 17、無線感測元件架構 38
圖 18、交通意外發生路況圖 43
圖 19、意外事故排除路況圖 45
圖 20、交通網路圖 47
圖 21、各路段車速範圍圖 48
圖 22、CAG通過路段速度 50
圖 23、RPU-路段平均速率 50
圖 24、運用T，RPU-路段平均速率 51
圖 25、 累加旅行時間 52
圖 26、各路段平均速率 53
圖 27、 累加旅行時間 54
圖 28、各路段平均速率 54
圖 29、實驗網路架構 56
圖 30、點1-13 DIJKSTRA、階層式、範圍式，規劃出最短路徑 58
圖 31、點1-13 DIJKSTRA、階層式、範圍式，規劃出最快路徑 59
圖 32、點1-25 DIJKSTRA、階層式、範圍式，規劃出最短路徑 60
圖 33、點1-25 DIJKSTRA、階層式、範圍式，規劃出最快路徑 61
圖 34、點1-55 DIJKSTRA、階層式、範圍式，規劃出最短路徑 62
圖 35、點1-55 DIJKSTRA、階層式、範圍式，規劃出最快路徑 63
圖 36、點1-100 DIJKSTRA、階層式、範圍式，規劃出最短路徑 64
圖 37、點1-100 DIJKSTRA、階層式、範圍式，規劃出最快路徑 65
圖 38、點1-210 DIJKSTRA、階層式、範圍式，規劃出最短路徑 66
圖 39、點1-210 DIJKSTRA、階層式、範圍式，規劃出最快路徑 67
圖 40、點1-400 DIJKSTRA、階層式、範圍式，規劃出最短路徑 68
圖 41、點1-400 DIJKSTRA、階層式、範圍式，規劃出最快路徑 69
圖 42、DIJKSTRA與區域式搜尋法之路線比較(以210為終點) 72
圖 43、DIJKSTRA與區域式搜尋法之路線比較(以400為終點) 72
圖 44、25個節點之下三種方法時間比較 75
圖 45、25個節點之下三種方法節點數量比較 75
圖 46、100個節點之下三種方法時間比較 77
圖 47、100個節點之下三種方法節點數量比較 77
圖 48、400個節點之下三種方法時間比較 79
圖 49、400個節點之下三種方法節點數量比較 79

[1] http://www.snowpear.com/viewnews-13516.html, 澳洲新聞網。
[2] http://news.epochtimes.com/b5/8/3/24/n2056055.htm, 大紀元新聞網。
[3]邱景升，周宜強(1996)，地理資訊系統入門與應用MapInfo, 松崗圖書。
[4]林傑斌，劉明德(2002)，地理資訊系統GIS理論與實務, 文魁出版社。
[5]徐世豪、李逢春(2006), 地理資訊系統MapInfo基礎操作自學方案, 松崗圖書。
[6]逢甲大學地利資訊系統研究中心(2000) 編著，地理資訊系統剖析，松崗圖書。
[7]莊智清、黃國興(2001)，電子導航（e-navigation），全華科技圖書司。
[8]余家豪(2007)，行動代理人訊息寄送之容錯，碩士論文，朝陽科技大學，台中。
[9]范智超，邱裕鈞(2006)，用於起迄交通量預估之車牌辨識系統區位規劃模式，碩士論文，逢甲大學，台中。
[10]陳芸伯(2004)，路徑規劃演算法實作，碩士論文，國立中正大學，嘉義。

[11]鄭昆霖，鍾葉青(2002)在PDA上整合GIS之導航系統，碩士論文，逢甲大學，台中。
[12]劉後欣(2004)，行動代理人訊息傳輸之保證，碩士論文，私立朝陽科技大學，臺中。
[13]蔡長俽、簡良益(2004)，GIS系統建置理論與實務, 研勤科技。
[14]謝權信(2002)，智慧型e化車輛導航系統，碩士論文，中華大學機，新竹。
[15] P. Agrawal, S. T. Tan, and A. L. Ananda (2003), “A Lightweight Protocol for Wireless Sensor Networks,” Proceedings of the IEEE Conference on Wireless Communications and Networking, Vol. 2, pp. 1280-1285.
[16]W. Chen, L. Gao, Z. Chai, and S. Tu (2005), “An Intelligent Guiding and Controlling System for Transportation Network Based on Wireless Sensor Network Technology,” Proceedings of the Fifth International Conference on Computer and Information Technology, Shanghai, China , pp. 810-814.
[17]S. Coleri, S. Y. Cheung, and P. Varaiya (2004), “Sensor Networks for Monitoring Traffic,” Proceedings of the 42th Annual Allerton Conference on Communication, Control and Computing, pp. 1-3.
[18]E. D. Dijkstra (1959), “A Node on Two Problems on Connection with Graphs”, Numerical Mathematics, pp. 269-271.

[19]M. Karpiriski, A. Senart, and V. Cahill (2006), “Sensor Networks for Smart Roads,” Proceedings of the Fourth Annual IEEE International Conference on Pervasive Computing and Communications Workshops, pp. 13-17.
[20] S. Krco, V. Tsiatsis, K. Matusikova, M. Johansson, I. Cubic, and R. Glitho (2007), “Mobile Network Supported Wireless Sensor Network Services,” Proceedings of the MASS IEEE International Conference on Mobile Adhoc and Sensor Systems, pp. 1-3.
[21]T. Matsuo, Y. Kaneko, and M. Matanob (1999), “Introduction of Intelligent Vehicle Detection Sensors,” Proceedings of the International Conference on Intelligent Transportation Systems IEEE/IEEJ/JSAI, Tokyo, Japan, pp. 709-713.
[22]D. Niculescu and B. Nath (2003), “DV Based Positioning in Adhoc Networks,” the Telecommunication Systems Journal, Vol. 22, No. 1-4, pp. 267–280.
[23]K. Nagel and M. Schreckenberg (1992), “A Cellular Automaton Model for Freeway Traffic,” Journal of Physical I France, Vol. 2, pp. 2221–2229.
[24] B.W. Parkinson (1994), “History and Operation of NAVSTAR, the Global
Positioning System,” Proceedings of the IEEE Transaction Conference on Aerospace and Electronic Systems, Vol. 30, No. 4, pp. 1143-1162.


[25]C. D. Wang and M. H. Lin (2004), “Data Fusion Methods for Accuracy Improvement in Wireless Location Systems,” Proceedings of the IEEE Conference on Wireless Communications and Networking, Vol. 1, pp. 471-476.
[26]A. K. Ziliaskopoulos and H. S. Mahmassani (1996), “Time-Dependent,Shortest-Path Algorithm for Real-Time Intelligent Vehicle Highway System Applications”, the Transportation Research Record Journal, No. 1408, pp. 94-100.