跳到主要內容

臺灣博碩士論文加值系統

(44.201.99.222) 您好!臺灣時間:2022/12/03 13:40
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:藍偉綺
研究生(外文):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?
指導教授:孫敏德
指導教授(外文):Min-te Sun
學位類別:碩士
校院名稱:國立中央大學
系所名稱:資訊工程研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2011
畢業學年度:99
語文別:英文
論文頁數:48
中文關鍵詞:無線異質網路上的應用.廣播演算法最小區域圓覆蓋集合
外文關鍵詞:heterogeneous wireless networks.broadcast algorithmMinimum disc cover
相關次數:
  • 被引用被引用:0
  • 點閱點閱:184
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
無線網路環境中,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.
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.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文