Why Topology-based Broadcast Algorithms Do Not Work Well in Heterogeneous Wireless Networks?

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：27

、訪客IP：18.218.75.58

姓名

藍偉綺(Wei-chi Lan) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

Why Topology-based Broadcast Algorithms Do Not Work Well in Heterogeneous Wireless Networks?
(Why Topology-based Broadcast Algorithms Do Not Work Well in Heterogeneous Wireless Networks?)

相關論文

★ Dynamic Overlay Construction for Mobile Target Detection in Wireless Sensor Networks	★ 車輛導航的簡易繞路策略
★ 使用傳送端電壓改善定位	★ 利用車輛分類建構車載網路上的虛擬骨幹
★ 針對移動性目標物的有效率無線感測網路	★ 適用於無線隨意網路中以關節點為基礎的分散式拓樸控制方法
★ A Review of Existing Web Frameworks	★ 將感測網路切割成貪婪區塊的分散式演算法
★ 無線網路上Range-free的距離測量	★ Inferring Floor Plan from Trajectories
★ An Indoor Collaborative Pedestrian Dead Reckoning System	★ Dynamic Content Adjustment In Mobile Ad Hoc Networks
★ 以影像為基礎的定位系統	★ 大範圍無線感測網路下分散式資料壓縮收集演算法
★ 車用WiFi網路中的碰撞分析	★ Exploring Spatial-Temporal Cloaking Against Correlation Attacks for Location-based Services

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

無線網路環境中，forwarding sets的概念被許多廣播協定廣泛得應用來減緩廣播風暴問題(broadcast storm problem)。在這些協定中，當一個節點收到廣播訊息後，會從自己的鄰居當中選擇部分鄰居(即forwarding sets)來協助重傳訊息。在本篇論文，我們發現在異質網路的環境中，存在一個隱藏接收點的問題(the hidden receiver problem)，因為此問題，透過局部拓樸資訊計算出每一個節點的forwarding set之任何廣播協定無法保證100%滲透率(penetration rate)。基於此考量，我們應用skyline sets來設計一個廣播演算法，並且對我們提出的廣播演算法進行優化，讓每一個收到廣播訊息的節點能自行決定是否需要進行重傳。模擬結果顯示，我們提出的廣播演算法不但可以保證100%滲透率，同時能有效降低重傳次數與延遲。除此之外，我們的演算法在計算過程僅需要1-HOP鄰居資訊，這將會有效減少計算forwarding set所造成延遲，同時也適用於車載網路這類型網路拓樸經常改變的環境中。

摘要(英)

The concept of forwarding sets is widely adopted in many broadcast protocols for wireless networks to alleviate the broadcast storm problem. In these protocols, after receiving a broadcast message, each node that is requested to relay the message instructs a subset of its neighbors, a.k.a. the forwarding set, to further relay it. In this thesis, we first demonstrate that, in heterogeneous wireless networks where nodes have different transmission radius, none of the broadcast protocols that select forwarding set based on local topology can guarantee the 100% penetration rate even under the ideal MAC assumption. The reason is because of the hidden receiver problem. To address this problem, we propose an enhanced version of skyline-based broadcast protocol for broadcast in heterogeneous wireless networks. Our protocol further optimizes the skyline-based broadcast protocol by having each receiving node computes whether or not it should relay the broadcast message distributively. The simulation results show that our proposed broadcast protocol is able to reach 100% penetration rate with relatively low number of retransmissions and low delay. This shows that our proposed broadcast protocol is more suitable for environments with a frequently changed network topology, such as vehicular ad hoc networks.

關鍵字(中)

★ 無線異質網路上的應用.
★ 廣播演算法
★ 最小區域圓覆蓋集合

關鍵字(英)

★ heterogeneous wireless networks.
★ broadcast algorithm
★ Minimum disc cover

論文目次

Contents
Chapter 1 Introduction …….……………………………….…………………..1
Chapter 2 Literature Review ….……………………...……………..………….3
2.1. Topology-based broadcast protocols ……….………….....…………..4
2.2. Location-based broadcast protocols ………..………..……………..….5
Chapter 3 Motivation ……..…………………….…………...………………....8
3.1. The hidden receiver problem ……………………………......................8
3.2. Penetration rate under the hidden receiver …….....................................9
3.3. The probability of a hidden receiver ……………….….......................11
Chapter 4 The Enhanced skyline-based Broadcast Algorithm ..…...................14
4.1. The solutions of the hidden receiver problem …….….........................14
4.2. The Enhanced skyline-based broadcast algorithm ...............................16
4.3. Time complexity analysis …………………………..………………...19
Chapter 5 Simulation Study ………………………..…………………………21
5.1. Simulation results and simulation analysis ………………….……….21
5.1.1. The average number of retransmissions ……………….…..…21
5.1.2. The mean difference of the number of retransmissions in heterogeneous networks ……………………………………….25
5.1.3. The average delay in hop count ..…………………………......27
Chapter 6 Conclusions and Future Work …………………………….…………34
6.1. Conclusion ………………………………………………….………...34
6.2. Future Work ..…………………………………………….…....……..35

參考文獻

[1] A.Durresi, and V. Paruchuri, “Geometric Broadcast Protocol for Heterogeneous Sensor Networks,” Journal of Interconnection Networks (JOIN), vol. 6, no.3, pp.193-208, 2005.
[2] A.Durresi, and V. Paruchuri, “Broadcast Protocol for Energy-Constrained Networks,” IEEE Transaction on Broadcasting, vol. 52, no.1, March 2007, pp.112-119.
[3] A. Segall, “Distributed Network Protocols,” IEEE Transactions on Information Theory, vol. IT-29, no. 1, January 1983.
[4] A. Qayyum, L. Viennot, and A. Laouiti, “Multipoint relaying for flooding broadcast message in mobile wireless networks,” in Proceedings of the 35th Hawaii International Conference on System Sciences (HICSS’02), vol. 9, January 2002, pp. 3866–3875.
[5] B. Chen, K. Jamieson, H. Balkrishnan, and R.Morris, “Span: an energy-efficient coordination algorithm for topology maintenance in ad hoc wireless network” in Proceedings of Mobicom, pp. 85-96, 2001.
[6] D. B. Johnson. “Routing in Ad Hoc Networks of Mobile Hosts,” Proceedings of the Workshop on Mobile Computing Systems and Applications, pp. 158–163, IEEE Computer Society, Santa Cruz, CA, December 1994.
[7] K. Obraczka, K. Viswanath, and G. Tsudik, “Flooding for Reliable Multicast in Multi-Hop Ad Hoc Networks,” Wireless Networks, vol. 7, Issue 6, November 2001.
[8] C.-W. Yi, F.-C. Liu, and M.-T. Sun, ”Minimum Local Disk Cover Sets for Broadcasting in Heterogeneous Wireless Ad Hoc Network,” IEEE International Workshop on Ad Hoc and Sensor Networks 2007, Xi An, China, September 2007.
[9] H. Lim, and C. Kim, “Flooding in Wireless Ad Hoc Networks,” Computer Communications, vol. 24, Issues 3-4, February 2001, pp.353-363.
[10] H. Liu, X. Jia, P. Wan, C. Yi, S. K. Makki, and N. Pissinou, “Maximizing Lifetime of Sensor Surveillance Systems,” IEEE/ACM Transactions on Networking, vol. 15, no. 2, April 2007.
[11] H. Luo, F. Ye, J. Cheng, S. Lu, and L. Zhang, “TTDD:Two-Tier Data Dissemination in Large-Scale Wireless Sensor Networks,” Wireless Networks, vol. 11, pp. 161–175, 2005.
[12] J. Agre, L. Clare, “An integrated architecture for cooperative sensing networks,” IEEE Computer Magazine, May 2000, pp. 106–108.
[13] J. Jetcheva, Y. Hu, D. Maltz, and D. Johnson, “A simple protocol for multicast and broadcast in mobile ad hoc networks,” July 2001.
[14] J.M. Kahn, R.H. Katz, K.S.J. Pister, ”Next century challenges: mobile networking for smart dust,” in Proceedings of the ACM MobiCom’99, Washington, USA, 1999, pp. 271–278.
[15] J. Wu and F. Dai, “Broadcasting in Ad hoc Networks Based on self-Puring,” in Proceedings of INFOCOM 2003.
[16] J. Wu,”Extend Dominating-Set-Based Routing in Ad Hoc Wireless Networks with Uni-Directional Links,” IEEE Transactions on Parallel and Distributed Systems, vol. 13, no. 9, September 2002, pp. 868-881.
[17] M. Sun, and T. Lai, “Location Aided Broadcast in Wireless Ad Hoc Network Systems,” in Processing of IEEE Wireless Communications and Networking Conference 2002, Orlando, FL., March 200, 597-602.
[18] N. Ababneh, S. Selvakennedy, and K. Almi’ani, “NBA: A Novel Broadcasting Algorithm for Wireless sensor Networks,” in Proceedings of the Fifth International Conference on Wireless and Optical Communications Networks (WOCN 2008), Surabayam, East Java Indonesia, May 2008.
[19] National Research Council (U.S.). Committee on the Future of the Global Positioning System; National Academy of Public Administration (1995). The global positioning system: a shared national asset : recommendations for technical improvements and enhancements. National Academies Press. p. 16. ISBN 0-309-05283-1., Chapter 1, p. 16.
[20] P. Wan, K. Alzoubi, and O. Frieder, “Distributed construction of connected dominating set in wireless ad-hoc networks,” in Proceedings of the IEEE Infocom, New York, June 2002, pp. 1597–1604.
[21] R. Gandhi, A. Mishra, and S. Parthasarathy, “Minimizing broadcast latency and redundancy in ad hoc networks,” IEEE/ACM Transactions on Networking, pp. 840-851, August 2008.
[22] R. Gandhi, Y. Kim, S. Lee, J. Ryu, and P. Wan, “Approximation Algorithms for Data Broadcast in Wireless Networks,” in INFOCOM, 2009.
[23] S. Cho, A. Chandrakasan, “Energy-efficient protocols for low duty cycle wireless microsensor,” in Proceedings of the 33rd Annual Hawaii International Conference on System Sciences, Maui, HI vol. 2 (2000), p. 10.
[24] S. C.-H. Huang, M-T. Sun, Q. Liang, P. Wan, and X. Jia, “Interference-Aware, Fully-Distributed Virtual Backbone Construction and Its Application in Multi-hop Wireless Networks” IEEE Transactions on Communications, vol. 58, issue 12, pp.3550-3560, December 2010.
[25] S.Y. Ni, Y.C. Tseng, Y.S. Chen, and J.P. Sheu, “The broadcast storm problem in a mobile ad hoc network,” in Proceedings of the 5th Annual ACM/IEEE International Conference on Mobile Computing and Networking, August 1999, pp. 151–162.
[26] T. Yan, T. He, J. A. Stankovic, “Differentiated Surveillance for Sensor Networks.” Transactions on Networking, vol. 15, no. 2, April 2007.

指導教授

孫敏德(Min-te Sun)

審核日期

2011-7-26

推文