1. NCCU Academic Hub
  2. Publications
  3. College of Informatics
  4. Theses
  5. Item

Publications-Theses

Article View/Open

Publication Export

Google ScholarTM

NCCU Library

Citation Infomation

Related Publications in TAIR

題名 車載網路緊急訊息傳遞之地理樹狀演算法
A Geo-based tree algorithm for emergency message delivery in 802.11p vehicular networks
作者 王欣祺
Wang, Hsin Chi
貢獻者 蔡子傑
Tzu, Chieh Tsai
王欣祺
Wang, Hsin Chi
關鍵詞 vehicular
Geo-based tree
車載
地理樹狀
日期 2010
上傳時間 4-Sep-2013 17:05:36 (UTC+8)
摘要 在現今車載傳輸安全資訊中最重要的兩個評估效能參數 -- Latency和reliability，要兼顧到這兩個的效能在現今不可靠的無線連接中是很困難的工作。這主要的挑戰是來自於在網路連接層的廣播，使用了不可靠的傳輸，例如:當某點接受到一個訊息時並不會傳輸一個反饋的信息給來源端通知它已接受到此信息。在現今有許多的方法是利用多於的點去增加接受的可靠性，但這將會增加網路頻寬的負載。
在我們的論文中我們提出了一個新的傳輸安全資訊的方法，使用少數relay去完成快速的安全資訊傳輸，並且在相同時間內去保持高效能傳輸的可靠性。在這我們介紹了兩個relay的型式同時地去減少end-to-end 傳輸延遲時間和增加傳輸範圍可靠性。地理樹狀演算法是由樹演算法而來的，它可以減少不必要的relay和傳輸資訊碰撞的發生，而802.11p則是用在優先權比較高的點擁有比較小的重新傳輸延遲時間。
Vehicular environments impose a set of new requirements on today’s wireless communication systems. Latency and reliability are very important means to disseminate safety information like time-sensitive emergency messages (EMs) in Vehicular Ad hoc Networks (VANETs). Providing low-latency, high-coverage and scalable multi-hop EM broadcast is a hard task in VANET with unreliable links. The major challenge comes from the fact that the link-layer broadcast uses unreliable transmissions, i.e., no positive feedback to acknowledge the reception of the message. Many existing works have used redundant relay nodes to enhance the reliability of broadcast packet reception. However they often involve more relays than it is necessary, which increases the network load and undermines the scalability of the protocol. Moreover, large latency is often incurred due to coarse protocol design.
In this thesis, we propose a new EM broadcast scheme that uses a small number of relays to achieve fast multi-hop EM propagation, at the same time to maintain a high level of transmission reliability. Two types of relays are introduced to reduce latency and to enhance reliability simultaneously, so that low-latency, the desired reliability level and small overhead can be achieved at the same time. The inverse tree algorithm (ITA) is based on tree algorithm, the mechanism to select single relay distributive, which features an effective redundant relay suppressing mechanism and very small rebroadcast delay for high priority nodes. Simulation study shows that ITA and multi-channel achieves close to 100% reliability, while using a small number of relays with very low broadcast latency under a wide range of road traffic conditions.
參考文獻 [1] DSRC and IEEE 1609 standard family,
http://www.standards.its.dot.gov/Documents/advisories/dsrc_advisory.htm.
[2] M. Torrent-Moreno, M. Killat, and H. Hartenstein. The challenges of robust
inter-vehicle communications. IEEE VTC 2005, 1:319–323, 28-25 Sept., 2005.
[3] M. Torrent-Moreno, F. Schmidt-Eisenlohr, H. Fussler, and H. Hartenstein. Effects of
a realistic channel model on packet forwarding in vehicular ad hoc networks. IEEE
WCNC, 1:385–391, 2006.
[4] M. Torrent-Moreno, D. Jiang, and H. Hartenstein. Broadcast reception rates and
effects of priority access in 802.11-based vehicular ad-hoc networks. In Proceedings
of VANET ’04, pages 10–18. ACM, 2004.
[5] S.-Y. Ni, Y.-C. Tseng, Y.-S. Chen, and J.-P. Sheu. The broadcast storm problem in a
mobile ad hoc network. In IEEE/ACM MobiCom, pages 151–162, 1999.
[6] N. Wisitpongphan, O. Tonguz, J. Parikh, P. Mudalige, F. Bai, and V. Sadekar.
Broadcast storm mitigation techniques in vehicular ad hoc networks. IEEE Wireless
Communications, 14(6):84–94, December 2007.
[7] S. Oh, J. Kang, and M. Gruteser. Location-based flooding techniques for vehicular
emergency messaging. In IEEE MobiQuitous, pages 1–9, July 2006.
[8] O. Tonguz, N. Wisitpongphan, F. Bait, P. Mudaliget, and V. Sadekart. Broadcasting in
vanet. In MoVE, pages 7–12, May 2007.
[9] O. Tonguz, N. Wisitpongphan, J. Parikh, F. Bai, P. Mudalige, and V. Sadekar. On the
broadcast storm problem in ad hoc wireless networks. In BROADNETS, pages 1–11,
Oct. 2006.
[10] R. Mangharam, R. Rajkumar, M. Hamilton, P. Mudalige, and F. Bai.
Bounded-latency alerts in vehicular networks. In MoVE, pages55–60, May 2007.
[11] M. T-Moreno. Inter-vehicle communications: Assessing information dissemination
under safety constraints. In WONS, pages 59–64. IEEE, January 2007.
[12] H. Alshaer and E. Horlait. Optimized adaptive broadcast scheme for inter-vehicle
communication. In IEEE VTC, pages 2840–2844, May 2005.
[13] IEEE_Std_1609[1].4_2006.
[14] Tree algorithm.
[15] Ns2. http://www.isi.edu/nsnam/ns.
[16] Daniel Jiang, Luca Delgrossi Mercedes-Benz Research & Development North
America, Inc. IEEE 802.11p: Towards an International Standard for Wireless Access
in Vehicular Environments. Pages2036-2040, IEEE, 2008
[17] Ming Li and Wenjing Lou. Opportunistic broadcast of emergency messages in
vehicular ad hoc networks with unreliable links. July 2008.
[18] Shun-Ren Yang and Wei-Hsiang Hung. Efficient Selection of Relay Vehicles for
Broadcasting on Vehicular Ad-hoc NETworks. The International Conference on
Mobile Technology, Applications & Systems 2008 (Mobility Conference), 10-12
September, 2008.
[19] Q. Chen, F. Schmidt-Eisenlohr, D. Jiang, M. Torrent-Moreno, L. Delgrossi, and H.
Hartenstein. Overhaul of ieee 802.11 modeling and simulation in ns-2. In
MSWiM ’07, pages 159–168. ACM, 2007.
[20] 新通訊 2009 年 7 月號 101 期《 技術前瞻 》
描述 碩士
國立政治大學
資訊科學學系
96971016
99
資料來源 http://thesis.lib.nccu.edu.tw/record/#G0096971016
資料類型 thesis
dc.contributor.advisor 蔡子傑zh_TW
dc.contributor.advisor Tzu, Chieh Tsaien_US
dc.contributor.author (Authors) 王欣祺zh_TW
dc.contributor.author (Authors) Wang, Hsin Chien_US
dc.creator (作者) 王欣祺zh_TW
dc.creator (作者) Wang, Hsin Chien_US
dc.date (日期) 2010en_US
dc.date.accessioned 4-Sep-2013 17:05:36 (UTC+8)-
dc.date.available 4-Sep-2013 17:05:36 (UTC+8)-
dc.date.issued (上傳時間) 4-Sep-2013 17:05:36 (UTC+8)-
dc.identifier (Other Identifiers) G0096971016en_US
dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/60237-
dc.description (描述) 碩士zh_TW
dc.description (描述) 國立政治大學zh_TW
dc.description (描述) 資訊科學學系zh_TW
dc.description (描述) 96971016zh_TW
dc.description (描述) 99zh_TW
dc.description.abstract (摘要) 在現今車載傳輸安全資訊中最重要的兩個評估效能參數 -- Latency和reliability，要兼顧到這兩個的效能在現今不可靠的無線連接中是很困難的工作。這主要的挑戰是來自於在網路連接層的廣播，使用了不可靠的傳輸，例如:當某點接受到一個訊息時並不會傳輸一個反饋的信息給來源端通知它已接受到此信息。在現今有許多的方法是利用多於的點去增加接受的可靠性，但這將會增加網路頻寬的負載。
在我們的論文中我們提出了一個新的傳輸安全資訊的方法，使用少數relay去完成快速的安全資訊傳輸，並且在相同時間內去保持高效能傳輸的可靠性。在這我們介紹了兩個relay的型式同時地去減少end-to-end 傳輸延遲時間和增加傳輸範圍可靠性。地理樹狀演算法是由樹演算法而來的，它可以減少不必要的relay和傳輸資訊碰撞的發生，而802.11p則是用在優先權比較高的點擁有比較小的重新傳輸延遲時間。		zh_TW
dc.description.abstract (摘要) Vehicular environments impose a set of new requirements on today’s wireless communication systems. Latency and reliability are very important means to disseminate safety information like time-sensitive emergency messages (EMs) in Vehicular Ad hoc Networks (VANETs). Providing low-latency, high-coverage and scalable multi-hop EM broadcast is a hard task in VANET with unreliable links. The major challenge comes from the fact that the link-layer broadcast uses unreliable transmissions, i.e., no positive feedback to acknowledge the reception of the message. Many existing works have used redundant relay nodes to enhance the reliability of broadcast packet reception. However they often involve more relays than it is necessary, which increases the network load and undermines the scalability of the protocol. Moreover, large latency is often incurred due to coarse protocol design.
In this thesis, we propose a new EM broadcast scheme that uses a small number of relays to achieve fast multi-hop EM propagation, at the same time to maintain a high level of transmission reliability. Two types of relays are introduced to reduce latency and to enhance reliability simultaneously, so that low-latency, the desired reliability level and small overhead can be achieved at the same time. The inverse tree algorithm (ITA) is based on tree algorithm, the mechanism to select single relay distributive, which features an effective redundant relay suppressing mechanism and very small rebroadcast delay for high priority nodes. Simulation study shows that ITA and multi-channel achieves close to 100% reliability, while using a small number of relays with very low broadcast latency under a wide range of road traffic conditions.		en_US
dc.description.tableofcontents CHAPTER 1 Introduction, Application and Motivation 1
1.1. Introduction 1
1.2. Application 3
1.3. Motivation 5
CHAPTER 2 Related Work 6
2.1. Opportunistic Broadcast protocol ---- OBP 6
2.1.1. Forwarder 7
2.1.1.1 How to select 7
2.1.2. Makeups 8
2.1.2.1 How to select 9
2.1.3. Disadvantage 9
2.2 Efficient Directional Broadcast ---- EDIB 錯誤! 尚未定義書籤。
2.2.1. How to select black-burst period and forwarder 錯誤! 尚未定義書籤。
2.2.2 If happen collision 11
2.2.3 System model 12
2.2.4 Disadvantage 12
CHAPTER 3 GEO-based Tree Algorithm (GTA) 13
3.1. Overview 13
3.2. IEEE802.11p multi-channel 16
3.3. Tree Algorithm (TA) 19
3.4. GEO-based Tree Algorithm (GTA) 21
3.4.1 What need Makeup 27
3.4.2 Follow chart 27
CHAPTER 4 Simulation 28
4.1. Simulation setup 28
4.2.. Simulation1 – 3X3 street and 6 paths 29
4.3. Simulation2 – 6X5 street, 3X2 viaduct and 7 paths for real map 36
4.4. Simulation3 – base on simulation2, but use single channel 43
CHAPTER 5 Conclusion 46
References 47		zh_TW
dc.format.extent 2358243 bytes-
dc.format.mimetype application/pdf-
dc.language.iso en_US-
dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0096971016en_US
dc.subject (關鍵詞) vehicularzh_TW
dc.subject (關鍵詞) Geo-based treezh_TW
dc.subject (關鍵詞) 車載en_US
dc.subject (關鍵詞) 地理樹狀en_US
dc.title (題名) 車載網路緊急訊息傳遞之地理樹狀演算法zh_TW
dc.title (題名) A Geo-based tree algorithm for emergency message delivery in 802.11p vehicular networksen_US
dc.type (資料類型) thesisen
dc.relation.reference (參考文獻) [1] DSRC and IEEE 1609 standard family,
http://www.standards.its.dot.gov/Documents/advisories/dsrc_advisory.htm.
[2] M. Torrent-Moreno, M. Killat, and H. Hartenstein. The challenges of robust
inter-vehicle communications. IEEE VTC 2005, 1:319–323, 28-25 Sept., 2005.
[3] M. Torrent-Moreno, F. Schmidt-Eisenlohr, H. Fussler, and H. Hartenstein. Effects of
a realistic channel model on packet forwarding in vehicular ad hoc networks. IEEE
WCNC, 1:385–391, 2006.
[4] M. Torrent-Moreno, D. Jiang, and H. Hartenstein. Broadcast reception rates and
effects of priority access in 802.11-based vehicular ad-hoc networks. In Proceedings
of VANET ’04, pages 10–18. ACM, 2004.
[5] S.-Y. Ni, Y.-C. Tseng, Y.-S. Chen, and J.-P. Sheu. The broadcast storm problem in a
mobile ad hoc network. In IEEE/ACM MobiCom, pages 151–162, 1999.
[6] N. Wisitpongphan, O. Tonguz, J. Parikh, P. Mudalige, F. Bai, and V. Sadekar.
Broadcast storm mitigation techniques in vehicular ad hoc networks. IEEE Wireless
Communications, 14(6):84–94, December 2007.
[7] S. Oh, J. Kang, and M. Gruteser. Location-based flooding techniques for vehicular
emergency messaging. In IEEE MobiQuitous, pages 1–9, July 2006.
[8] O. Tonguz, N. Wisitpongphan, F. Bait, P. Mudaliget, and V. Sadekart. Broadcasting in
vanet. In MoVE, pages 7–12, May 2007.
[9] O. Tonguz, N. Wisitpongphan, J. Parikh, F. Bai, P. Mudalige, and V. Sadekar. On the
broadcast storm problem in ad hoc wireless networks. In BROADNETS, pages 1–11,
Oct. 2006.
[10] R. Mangharam, R. Rajkumar, M. Hamilton, P. Mudalige, and F. Bai.
Bounded-latency alerts in vehicular networks. In MoVE, pages55–60, May 2007.
[11] M. T-Moreno. Inter-vehicle communications: Assessing information dissemination
under safety constraints. In WONS, pages 59–64. IEEE, January 2007.
[12] H. Alshaer and E. Horlait. Optimized adaptive broadcast scheme for inter-vehicle
communication. In IEEE VTC, pages 2840–2844, May 2005.
[13] IEEE_Std_1609[1].4_2006.
[14] Tree algorithm.
[15] Ns2. http://www.isi.edu/nsnam/ns.
[16] Daniel Jiang, Luca Delgrossi Mercedes-Benz Research & Development North
America, Inc. IEEE 802.11p: Towards an International Standard for Wireless Access
in Vehicular Environments. Pages2036-2040, IEEE, 2008
[17] Ming Li and Wenjing Lou. Opportunistic broadcast of emergency messages in
vehicular ad hoc networks with unreliable links. July 2008.
[18] Shun-Ren Yang and Wei-Hsiang Hung. Efficient Selection of Relay Vehicles for
Broadcasting on Vehicular Ad-hoc NETworks. The International Conference on
Mobile Technology, Applications & Systems 2008 (Mobility Conference), 10-12
September, 2008.
[19] Q. Chen, F. Schmidt-Eisenlohr, D. Jiang, M. Torrent-Moreno, L. Delgrossi, and H.
Hartenstein. Overhaul of ieee 802.11 modeling and simulation in ns-2. In
MSWiM ’07, pages 159–168. ACM, 2007.
[20] 新通訊 2009 年 7 月號 101 期《 技術前瞻 》		zh_TW