( 您好!臺灣時間:2022/08/12 23:29
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::


研究生(外文):Chia-Hung Yen
論文名稱(外文):Broadcast Routing Algorithm Based on Minimum Cost Spanning Tree for Ad-Hoc Networks
指導教授(外文):Hwang-Cheng Wang
外文關鍵詞:ad-hoc networkbroadcast routingforbidden setminimum cost spanning treecost modelbottleneck lifetime
  • 被引用被引用:0
  • 點閱點閱:205
  • 評分評分:
  • 下載下載:25
  • 收藏至我的研究室書目清單書目收藏:0
現今有許多無線網路之應用,例如、團體會議和數位影音串流,都需要利用ad-hoc 無線網路的方式將資料廣播至其它的裝置。在本篇論文中,提出minimum cost broadcast routing (MCBR) 和minimum cost broadcastrouging with forbidden set (MCBRF) 這兩種繞徑演算法。在MCBR 演算法中,先提出一個有考慮節點間距離、節點剩餘電量和電池放電特性的能量成本模型,接者再利用最小生成樹建構出MCBR 的廣播樹,而MCBRF 是在MCBR 中多加入禁止集合的觀念所延伸出來的演算法。 MMLE 是改良minimum longest edge (MLE) 的產生的繞徑演算法,在此方法中,利用兩條較短的鏈結來代替原本在廣播樹中最長的鏈結以降低最大的功率消耗。

最後利用了許多模擬來證實MCBRF 的優勢。由模擬結果可得知,在各種不同大小的拓撲中利用MCBRF 所建構的廣播樹可以得到比BIP 和MMLE 還多的葉節點。雖然利用MWIS 和MCDS 可以得到較多的葉節點,但是這兩種方法皆會造成極大的功率消耗。在MCBR 及MCBRF 這兩種方法中會盡可能的選擇剩餘電池電量較多的節點作為中繼節點以傳遞資料,也因此這兩種演算法會建構出較堅固的廣播樹,再者相對於BIP 和MMLE,MCBRF 使廣播樹可得到較長的網路生存時間及較短的廣播時間。
For many wireless applications such as group conference and digital audio/video broadcast, it is necessary to send data to all devices that form an ad-hoc network. In this thesis, minimum cost broadcast routing (MCBR) and minimum cost broadcast routing with forbidden set (MCBRF) are proposed. We first formulate a new cost model for the underlying graph by considering the distance between nodes, the remaining battery energy, and battery discharge pattern at each node. A minimum cost broadcast routing (MCBR) based on minimum cost graph spanning is described. Then forbidden set is introduced into MCBR to obtain MCBRF. MMLE is modified from minimum longest edge (MLE). It removes the longest edge and replaces it with a pair of shorter links which may raise total route cost but decrease maximum energy consumption. The performance of the algorithms is investigated through extensive simulations and compared to several other routing methods. The results on a variety of topologies of different sizes indicate that the spanning tree constructed by MCBRF algorithm has more leaf nodes than BIP and MMLE. Although the broadcast trees constructed by MWIS and MCDS have more leaf nodes, they suffer serious drawbacks in terms of energy consumption. Also, MCBR and MCBRF generate spanning trees that select nodes with higher remaining battery capacity as relay nodes. Thus more robust broadcast routes are established. Compared to BIP and MMLE, MCBRF also enjoys longer bottleneck lifetime and shorter broadcast latency.
Chapter 1 Introduction 1
1.1. Brief Introduction of Wireless LAN 2
1.2. Transmission Modes of Wireless LAN 5
1.3. Contributions 9
1.4. Thesis Organization 9
Chapter 2 Related Work 11
Chapter 3 The Proposed Broadcast Routing Algorithms 21
3.1. Cost Model 21
3.2. MCBR and MCBRF Algorithms 24
3.3. Information Exchange by Beacons 27
Chapter 4 Comparison of Broadcast Routing Algorithms 29
4.1. BIP Algorithm 29
4.2. MMLE Algorithm 30
4.3. MWIS Algorithm 31
4.4. MCDS Algorithm 33
4.5. Comparison of Broadcast Algorithms 34
Chapter 5 Performance Evaluation 42
5.1. Simulation Setup and Performance Metrics 42
5.2. Simulation Results and Analysis 44
5.2.1. Comparison of MCBRF for Different threshold of value 44
5.2.2. Total Energy Consumption 46
5.2.3. Bottleneck Lifetime 48
5.2.4. Broadcast Delay 49
Chapter 6 Conclusion 51
References 52
Appendix Statistical Results of Experiments 57
Definition 1 of confidence interval: [μ-σ, μ+σ] 57
Definition 2 of confidence interval: [μ- 0.05*μ, μ+0.05*μ] 59
Definition 3 of confidence interval: [μ- 0.1*μ, μ+0.1*μ] 60
Definition 4 of confidence interval: [μ- 0.2*μ, μ+0.2*μ] 61
Definition 5 of confidence interval: [μ- 0.3*μ, μ+0.3*μ] 63
Definition 6 of confidence interval: [μ- 0.4*μ, μ+0.4*μ] 64
[1]P. J. Wan, G. Galinescu, X. Y. Li, and O. Frieder, "Minimum-energy broadcast routing in static ad hoc wireless networks," Proc. IEEE INFOCOM, vol. 2, pp. 1162-1171, 2001.
[2]J. E. Wieselthier, G. D. Nguyen, A. Ephremides, “The energy efficiency of distributed algorithms for broadcasting in ad hoc networks,” Wireless Personal Multimedia Communications, vol. 2, pp. 499 – 503, October 2002.
[3]X. H. Chen, M. Faloutsos, S. V. Krishnamurthy, “Power adaptive broadcasting with local information in ad hoc networks,” Proc. 11th IEEE International Conf. on Network Protocols, pp. 168–178, 2003.
[4]G. Aggelou, Mobile Ad Hoc Networks, McGraw-Hill, 2005.
[5]J. P. Macker, “Mobile Ad Hoc networking and the IETF,” ACM SIGMOBILE Mobile Computing and Communications Review, vol.4, no.1, pp 13-16, Jan 2000.
[6]R. Ramanathan and J. Redi, “A brief overview of ad hoc networks: challenges and directions,” IEEE Communications Magazine, vol. 40, no. 5, pp. 20-22, 2002.
[7]L. Kirousis, E. Kranakis, D. Krizanc, and A. Pelc, “Power consumption in packet radio networks,” Proc. 14th Symp. on Theoretical Computer Science (STACS'97), pp. 363–374, 1997.
[8]J. E. Wieselthier, G. D. Nguyen, and A. Ephremides, “On the construction of energy-efficient broadcast and multicast trees in wireless networks,” Proc. IEEE INFOCOM, pp. 585-594, 2000.
[9]T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 2nd ed., MIT Press and McGraw-Hill, 2001.
[10]X. Y. Cheng, J. H. Sun, M. K. Min, and D. Z. Du, “Energy-efficient broadcast and multicast routing in ad-hoc wireless networks,” Proc. IEEE International Conf. on Performance, Computing, and Communications, pp. 87-94, 2003.
[11]W. Wang and B. H. Soong, “Collision-free and low-latency scheduling algorithm for broadcast operation in wireless ad-hoc networks,” IEEE Communications Letters, pp. 793 – 795, October 2007.
[12]S. Sakai, M. Togasaki, and K. Yamazaki, “A note on greedy algorithm for the maximum weighted independent set problem,” Discrete Applied Mathematics, vol. 126, no. 2-3, pp. 313-322, 2003.
[13]G. Agnarsson and R. Greenlaw, Graph Theory: Modeling, Applications, and Algorithms, Pearson Education, 2006.
[14]S. M. Banik and S. Radhakrishnan, "Minimizing broadcast latency in ad-hoc wireless networks," Proc. 45th Annual Southeast Regional Conference, pp. 533-534, 2007.
[15]W. Lou and J. Wu, “On reducing broadcast redundancy in ad hoc wireless networks,” Proc. 36th Hawaii International Conf. on System Sciences, pp. 305- 314, 2003.
[16]D. B. West, Introduction to Graph Theory, Prentice Hall, 2000.
[17]L. Benini, G. Castelli, A. Macii, E. Macii, M. Poncino, and R. Scarsi, “A Discrete-Time Battery Model for High-Level Power Estimation,” Proc. ACM Conf. on Design, Automation and Test in Europe, pp. 35-39, 2000.
[18]T. F. Fuller, M. Doyle, and J. S. Newman, “Modeling of galvanostatic charge and discharge of the lithium polymer insertion cell,” J. Electrochem Soc., vol. 140, pp. 1526–1533, June, 1993.
[19]D. N. Rakhmatov and S. B. K. Vrudhula, “Energy management for battery-powered embedded systems,” ACM Transactions on Embedded Computing Systems, vol. 2, no. 3, pp. 277-324, 2003.
[20]V. Rao, G. Singhal, A. Kumar, and N. Navet, “Battery Model for Embedded Systems,” Proc. 18th International Conference on VLSI Design, 2005.
[21]J. L. Gross and J. Yellen, Handbook of Graph Theory, CRC, 2003.
[22]S. Singh and M. Woo, “Power-aware routing in mobile ad-hoc networks,” Proc. 4th annual ACM/IEEE International Conference on Mobile Computing and Networking, pp. 181-190, 1998.
[23]L. Campelli, M. Cesana, and R. Fracchia, "Directional broadcast forwarding of alarm messages in VANETs," Fourth Annual Conf. on Wireless on Demand Network Systems and Services, pp. 72 – 79, Jan 24-26, 2007.
[24]O. Tonguz, N. Wisitpongphan, F. Bait, P. Mudaliget, and V. Sadekart, "Broadcasting in VANET," 2007 Mobile Networking for Vehicular Environments, pp. 7-12, May 11-11, 2007.
[25]S. Gold, “A PSPICE macromodel for lithium-ion batteries,” Proc. Twelfth Annual Battery Conf. on Applications and Advances, pp. 215-222, 1997.
[26]H. C. Wang and W. H. Chen, “Maximum path lifetime routing for ad-hoc wireless networks,” Proc. IFIP/IEEE MWCN2007, pp. 166-170, Cork, Ireland, September 19-21, 2007.
[27]H. C. Wang and Y. H. Wang, “Energy-efficient routing algorithms for wireless ad-hoc networks”, Proc. 18th IEEE PIMRC, Athens, Greece, Sept. 2-6, 2007.
[28]C. K. Yen, “Restricted independent domination problems on graphs,” International Journal of Computer Systems Science & Engineering, vol. 23, no. 4, pp. 23-29, 2008.
[29]X. Z. Zhang, “Efficient broadcast scheduling based on fuzzy clustering and Hopfield network for ad-hoc networks,” Proc. International Conf. on Machine Learning and Cybernetics, vol. 6, pp. 3255–3260, 2007.
[30]G. Tan, S. A. Jarvis, J. W. J. Xue, and S. D. Hammond, “Distributed broadcast scheduling in mobile ad-hoc networks with unknown topologies,” Proc. IEEE International Symp. on Parallel and Distributed Processing, pp. 1–7, 2007.
[31]B. Xing, M. Deshpande, N. Venkatasubramanian, S. Mehrotra, and D. Bren, “Towards reliable application data broadcast in wireless ad-hoc networks,” Proc. IEEE Wireless Communications and Networking Conference, pp. 4063-4068, March 11-15, 2007.
[32]B. J. Wolf, J. L. Hammond, D. L. Noneaker, and H. B. Russell, “A protocol for construction of broadcast transmission schedules in mobile ad-hoc networks,” IEEE Wireless Communications, vol. 6, no. 1, pp. 74-78, 2007.
[33]X. H. Chen, M. Faloutsos, and S. V. Krishnamurthy, "Power adaptive broadcasting with local information in ad-hoc networks", Proc. 11th IEEE International Conf. on Network Protocols, pp. 168–178, 2003.
[34]T. R. Andel and A. Yasinsac, “On the credibility of Manet simulations,” IEEE Computer, vol. 39, no. 7, pp. 48-54, July 2006.
[35]J. H. Anthony, Probability and Statistics for Engineers and Scientists, 3rd ed., Section 8, Brooks/Cole Press, 2006.
[36]J. Chang and L. Tassiulas, "Maximum Lifetime Routing in Wireless Sensor Networks," IEEE/ACM Trans. on Networking, vol. 12, no. 4, pp. 609-619, Aug. 2004.
[37]W. Stallings, Data and Computer Communications, 8th ed., Prentice Hall, 2006.
第一頁 上一頁 下一頁 最後一頁 top