跳到主要內容

臺灣博碩士論文加值系統

(44.210.99.209) 您好!臺灣時間:2024/04/15 18:19
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:陳仕堯
研究生(外文):Shi-Yao Chen
論文名稱:以最佳化技術為基礎之減輕IEEE 802.11無線網路飢餓現象演算法
論文名稱(外文):An Optimization-Based Algorithm for Mitigation of Starvation in IEEE 802.11 Wireless Networks
指導教授:林永松林永松引用關係
指導教授(外文):Yeong-Sung Lin
口試委員:林宜隆呂俊賢鍾順平莊東穎
口試日期:2016-07-25
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:資訊管理學研究所
學門:電算機學門
學類:電算機一般學類
論文種類:學術論文
論文出版年:2016
畢業學年度:104
語文別:英文
論文頁數:70
中文關鍵詞:IEEE 802.11飢餓問題傳輸功率控制載波偵測門檻無線隨意網路最佳化演算法數學規劃拉格蘭日鬆弛法
外文關鍵詞:IEEE 802.11Starvation problemTransmission Power ControlCarrier Sense ThresholdWireless Ad Hoc NetworkOptimization AlgorithmMathematical ProgrammingLagrangean Relaxation
相關次數:
  • 被引用被引用:0
  • 點閱點閱:246
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
隨著行動裝置不斷的出現,無線網路的使用率越來越高。 以IEEE 802.11無線網路為標準的通訊協定,其所使用的分散式協調功能(Distributed Coordination Function, DCF) 為了減少訊號傳輸的碰撞,各結點透過競爭的模式以取得資料傳遞的權利。每一個傳送者都必須在送出資料前,偵測所使用的頻道上是否有其他結點在傳送資料。然而,在此傳輸機制下將使部分結點發生飢餓現象(Starvation),造成網路系統的不公平。本篇研究將針對減低Wi-Fi無線隨意網路的飢餓問題以提升無線網路之服務品質為目標。透過調整傳輸訊號範圍、載波偵測門檻來達到減少結點之間的飢餓問題。
我們利用最佳化數學模型形容並解決無線網路飢餓問題。為了減少解決最佳化問題的計算時間,本研究使用了拉格蘭日鬆弛法(Lagrangean Relaxation, LR),其利用拉格蘭日乘數(Lagrangean multipliers)將原問題轉換成近似問題。接著利用Visual Studio 2013搭配C/C++程式語言實行模擬,以取得飢餓問題的實驗結果。我們預期以拉格蘭日鬆弛法為基礎之演算法,將使本研究所取的最佳解距離實際解在百分之二十的落差之內,最終得到一個最小化無線網路飢餓之現象。


Distributed Coordination Function (DCF) is a fundamental MAC mechanism of the IEEE 802.11 based WLAN standard to access the medium and reduce possibility of collisions by Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA). Each flow of sender must check whether the medium is available or not before sending data. However, in some situations, the random access protocol, CSMA/CA, cause serious unfairness or flow starvation. In this research, we focus on mitigating starvation problems in Wi-Fi ad hoc networks for improving the wireless network service. Adapting the transmission power range, carrier sense threshold are used in the work. The objective is to alleviate the starvation problems between nodes in the densely wireless network.
In this thesis, we model the optimal mathematical formulation for describing and mitigating the starvation problems with objective function and some constraints. To fast solve the mathematical optimization, we utilize an approach, Lagrangean Relaxation (LR), which approximates another problem of constrained optimization by a similar problem. The feasible solution is derived from information provided by the Lagrangean multipliers. We are going to use Visual Studio 2013 and C/C++ for computational experiments which some scenarios are designed for evaluating the starvation problems. We anticipate that the expectation results with LR-based approach will be within the twenty-percent gap to the real optimum. Finally, we will get the result which minimizes the starvation problems in IEEE 802.11 wireless networks.


謝誌..........I
論文摘要..........II
THESIS ABSTRACT..........III
List of Figures..........VII
List of Tables..........VIII
Chapter 1 Introduction..........1
1.1 Background..........1
1.2 Motivation..........4
1.3 Literature Survey..........6
1.3.1 System Parameters for Improving the Network Performance..........6
1.3.2 Starvation Problem..........7
1.3.3 Interference..........10
Chapter 2 Problem Formulation..........11
2.1 Network Model..........11
2.1.1 802.11 Network Environment..........11
2.1.2 Distributed Coordination Function..........12
2.1.3 Propagation Model..........13
2.1.4 Interference Model..........15
2.1.5 Channel Capacity Model..........15
2.2 Problem Description..........17
2.2.1 Starvation Problems..........17
2.2.2 Problem Scenario..........19
2.2.3 Weighting Problems..........22
2.2.4 Assumptions and Specific Descriptions..........25
2.3 Mathematical Formulation..........27
2.3.1 Given Parameters and Decision Variables..........27
2.3.2 Mathematical Function..........30
Chapter 3 Solution Approach..........35
3.1 Introduction to Lagrangean Relaxation Method..........35
3.2 Lagrangean Relaxation..........37
3.3 The Langrangean Dual Problem..........48
3.4 Solution Approach..........49
3.4.1 Initial Primal Feasible Solution..........49
3.4.2 Getting Primal Heuristic Algorithm..........50
3.4.3 Routing Heuristic Algorithm..........51
3.4.4 Improvement Heuristic Algorithm..........52
Chapter 4 Computational Experiment..........54
4.1 Experiment Environment..........54
4.2 Simple Algorithm and Metrics..........55
4.3 Experiment Scenarios..........56
4.4 Experiment Results..........58
4.5 Result Discussion..........63
Chapter 5 Conclusions and Future Work..........64
5.1 Conclusions..........64
5.2 Future Work..........65
References..........66


[1]"Visual Networking Index: Global Mobile Data Traffic Forecast Update 2014-2019," Cisco White Paper, Feb. 2015.
[2]B. H. Jung, H. Jin, and D. K. Sung, "Adaptive Transmission Power Control and Rate Selection Scheme for Maximizing Energy Efficiency of IEEE 802.11 Stations," The 2012 IEEE 23rd International Symposium on Personal Indoor and Mobile Radio Communications (PIMRC 2012), pp. 226-271, Sept. 2012.
[3]J. Chen, S. G. Chan, Q. Zhang, W. W. Zhu, and J. Chen, "PASA: Power Adaptation for Starvation Avoidance to Deliver Wireless Multimedia," IEEE Journal on Selected Areas in Communications, Vol. 21, No. 10, pp. 1663-1673, Dec. 2003.
[4]Y. Zhu, Q. Zhang, Z. Niu, and J. Zhu, "On Optimal QoS-Aware Physical Carrier Sensing for IEEE 802.11 Based WLANs: Theoretical Analysis and Protocol Design," IEEE Transactions on Wireless Communications, Vol. 7, No. 4, pp. 1369-1378, Apr. 2008.
[5]E. B. Koh and C. K. Kim, "Mitigating Starvation in CSMA-Based Wireless Ad Hoc Networks Using Carrier Sense Threshold," The 15th International Conference on Software, Telecommunications and Computer Networks (SoftCOM 2007), pp. 1-6, Sept. 2007.
[6]C. Hua and R. Zheng, "Starvation Modeling and Identification in Dense 802.11 Wireless Community Networks," The 27th Conference on Computer Communications (INFOCOM 2008), pp. 1696-1704, Apr. 2008.
[7]R. G. Akl, D. Tummala, and X. Li, "Indoor Propagation Modeling at 2.4 GHz for IEEE 802.11 Networks," The 6th IASTED International Multi-Conference on Wireless and Optical Communications, Jul. 2006.
[8]W. Wang, Q. Wang, W. K. Leong, B. Leong, and Y. Li, "Uncovering a Hidden Wireless Menace: Interference from 802.11x MAC Acknowledgment Frames," The 2014 Eleventh Annual IEEE International Conference on Sensing, Communication, and Networking (SECON 2014), pp. 117-125, Jun. 2014.
[9]M. K. Dholey and A. Khatun, "Reduction of Blockage Node and Hidden Terminal Problem of CSMA/CA MAC Protocol Using Directional Antenna," The 2012 2nd IEEE International Conference on Parallel Distributed and Grid Computing (PDGC 2012), pp. 741-746, Dec. 2012.
[10]D. Nicolescu, "Interference Map for 802.11 Networks," The 7th ACM SIGCOMM Conference on Internet Measurement (IMC 2007), pp. 339-350, Oct. 2007.
[11]J. B. Andersen, T. S. Rappaport, and S. Yoshida, "Propagation Measurements and Models for Wireless Communications Channels," IEEE Communications Magazine, Vol. 33, No. 1, pp. 42-49, Jan. 1995.
[12]S. Sendra, J. Lloret, C. Turro, and J. M. Aguiar, "IEEE 802.11 a/b/g/n Short–Scale Indoor Wireless Sensor Placement," International Journal of Ad Hoc and Ubiquitous Computing, Vol. 15, No. 1-3, pp. 68-82, Oct. 2004.
[13]T. S. Rappaport, "Wireless Communications: Principles and Practice," 2e. Prentice Hall, Jan. 2002.
[14]C. E. Shannon, "A Mathematical Theory of Communication," ACM SIGMOBILE Mobile Computing and Communications Review, Vol. 5, No. 1, pp. 3-55, Jan. 2001.
[15]A. Duda, "Understanding the Performance of 802.11 Networks," The IEEE 19th International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC 2008), pp. 1-6, Sept. 2008.
[16]V. P. Mhatre, K. Papagiannaki, and F. Baccelli, "Interference Mitigation Through Power Control in High Density 802.11 WLANs," The 26th IEEE International Conference on Computer Communications (INFOCOM 2007), pp. 535-543, May 2007.
[17]H. Ehsan and Z. A. Hzmi, "Performance Comparison of Ad Hoc Wireless Network Routing Protocols," Multitopic Conference, 2004. Proceedings of INMIC 2004. 8th International, pp. 457-465, Dec. 2004.
[18]S. H. Wong, H. Yang, S. Lu, and V. Bharghavan, "Robust Rate Adaptation for 802.11 Wireless Networks," The 12th Annual International Conference on Mobile Computing and Networking (MobiCom 2006), pp. 146–157, Sept. 2006.


QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊