臺灣博碩士論文加值系統

因為現在WiFi需求增加，對於使用無線網路的效能要求也提高，為了提供更好的QoS (Quality of Service)，我們需要在多速率且多AP的環境下提供最佳效能。此處討論及分析效能時以throughput跟delay為主，並參考目前的無線網路環境，使用IEEE 802.11標準。考慮在多AP的環境下，當一個node可能同時可連線到多個AP，這時選擇哪一個AP連線就要考慮對整體throughput跟delay的影響，就是網路選擇(network selection)問題。在這個問題下，我們想要決定一個架構使得系統整體效能最大，換句話說就是系統throughput最大及每個封包的delay最小。將此網路選擇問題寫成數學式，並用最佳化的方式解決。為了解最佳化問題，我們根據模擬觀察及分析，寫出可代表不同情況下系統效能的utility function，並使用utility代表實際的網路效能。我們提出了疊代法(iterative method)做為解多速率環境下網路選擇問題的方法。經由設計適合的初始狀態及改變現在連線狀態的政策，我們就可在有限時間內得到或逼近最佳的網路架構使得整體效能最大。
決定utility function時，首先考慮系統裡只有一個AP的情形，加上由於無線網路的環境，node與AP的距離不同會造成不同的傳輸速率。考慮在多速率的環境下，我們可以將不同傳輸速率的node分時傳輸，避免了高速率跟低速率node一起傳輸所下降的throughput，這個方法稱為分群 (grouping)。上述的在單一AP下會影響throughput的各種參數和多速率的問題下使用分群的情形一併考慮進來就可得出utility function。
決定使用疊代法解最佳化問題後，我們比較在不同網路架構下疊代法跟其他方法所得出的結果差異，無論是改變系統的使用者數目還是改變封包產生的速率，疊代法都是最接近最佳解的方法。並且在最好的情況下疊代法比其他方法高出約15%的效能。

Due to increasing requirements of wireless network, users’ requirements of performance in wireless network also increase. To provide better Qos (Quality of Service), we have to provide good performance in multi-rate and multiple APs scenario. Here we discuss throughput and delay for performance, and use IEEE 802.11 standard for wireless network in the following discussion and analysis. Consider that there are many APs in the system, each client can choose which station to connect now, and different connections affect throughput and delay of system. This is a network selection problem of multi-rate system. In this problem, we want to find a configuration such that the system performance is maximal, which means maximal throughput and minimal delay. We can solve the network selection problem in optimization, and use utility function to represent real performance in this problem. With utility function, we can find optimal configuration which causes maximal performance by using iterative method of utility function optimization in multi-rate network selection problem. After design of iterative algorithm, it is ensure the method can get or close to optimal configuration, and has the best performance than other methods.
To decide utility function, consider there are one AP in the system, find the variables which affect performance. In addition, different distances from client to AP cause different transmission rate. In multi-rate environment, we can divide the stations by transmission rate into different groups, so it reduces the reduction of throughput if high rate stations and low rate stations transmit together. The method is called grouping. The analysis of the variables effect on multi-rate system are used to utility function.
After design of iterative algorithm, we compare this method with other methods in different configurations. Iterative method is the best method which is the closest to optimal performance even if changing client number in the system or changing arrival rate. Also, the performance is higher than other methods by 15% in the best case.

摘 要 i
Abstract ii
致 謝 iv
目 錄 v
表目錄 vii
圖目錄 viii
I. Introduction 1

II. Background of wireless LAN IEEE 802.11 3
A. Introduction of IEEE 802.11 and DCF mechanism 3
B. Performance of IEEE 802.11 DCF basic mode 5
C. Grouping for enhanced performance 8
D. Performance anomaly of multi-rate system 10

III. Network selection problem in multiple APs scenario 13
A. Background of network selection problem in wireless LAN 13
1) Multiple APs scenario: 13
2) Network selection problem: 14
B. Optimization modeling for network selection problem 14
1) Definition of performance: 14
2) Variables of network selection problem modeling: 15
3) General optimal form: 16
4) Time complexity of general optimal form: 18
C. Existing methods for optimization 18

IV. Design of utility function and iterative method 22
A. Using utility function to represent performance 22
1) Variables in utility function: 22
2) Relations of criteria and utility function according to simulation: 23
3) Utility optimization for multiple APs network selection problem: 30
B. Problems of solving optimal utility function methods 33
C. Iterative method 35
1) Iterative algorithm and flow chart: 35
2) Time complexity of iterative algorithm: 36
3) Convergence of iterative method: 38
V. Simulation result 40
A. Verification of utility function 40
B. Iterative method in simple configurations 43
C. Performance analysis of iterative method 47
1) Effect on check number of AP: 47
2) Comparison of real performance and utility value: 49
3) Comparison of iterative method with other network selection methods: 50

VI. Discussion and conclusion 60

VII. Future works 61

Reference 62

[1] IEEE Standard for Information technology – Local and metropolitan area networks – Specific requirements – Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications Amendment 5: Enhancements for Higher Throughput, “IEEE Std 802.11n-2009, pp.1-565, Oct. 2009
[2] Abhinav Kumar, Ranjan K. Mallik, Robert Schober, “A probabilistic Approach to modeling users' network selection in presence of Heterogeneous Wireless Networks,” IEEE Trans. on Vehicular Technology, vol. 63, pp. 3331-3341, January 2014
[3] Hongzhi Xing, Dawei Mu, Xianlei Ge, Rong Chai, “An NN-based access network selection algorithm for heterogeneous networks,” Wireless and Optical Comm. Conf. (WOCC), 2013 22nd, pp. 378-383, Chongqing, 16-18 May 2013
[4] Daniel P. Palomar and Mung Chiang “A Tutorial on Decomposition Methods for Network Utility Maximization,” IEEE Journal on Selected Areas in Comm., vol. 24, pp. 1439-1451, Aug. 2006.
[5] Dusit Niyato and Ekram Hossain “Dynamics of Network Selection in Heterogeneous Wireless Networks: An Evolutionary Game Approach,” IEEE Trans. Vehicular Technology, vol. 58, pp. 2008-2017, Aug. 2008.
[6] IEEE Standard for Information Technology- Telecommunications and Information Exchange Between Systems-Local and Metropolitan Area Networks-Specific Requirements-Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications," IEEE Std 802.11-1997 , vol., no., pp.i,445, 1997
[7] Giuseppe Bianchi, “Performance Analysis of the IEEE 802.11 Distributed Coordination Function,” IEEE Journal on Selected Areas in Comm., vol. 18, no. 3, March 2000
[8] Haitao Wu, Shiduan Cheng, Yong Peng, Keping Long, Jian Ma, “IEEE 802.11 Distributed Coordination Function (DCF): Analysis and Enhancement,” IEEE International Conf. on Comm., vol. 1, pp. 605-609, New York, 28 Apr. – 2 May 2002
[9] Der-Jiunn Deng, Chih-Heng Ke, Hsiao-Hwa Chen, Yueh-Min Huang, “Contention Window Optimization for IEEE 802.11 DCF Access Control,” IEEE Trans. On Wireless Comm., vol.7, no. 12, December 2008
[10] Chonggang Wang, Weiwen Tang, “A Probability-based Algorithm to Adjust Contention Window in IEEE 802.11 DCF,” IEEE International Conf. on Comm., Circuits and Systems, vol. 1, pp. 418-422, Chengdu, 27-29 June 2004
[11] Younggoo Kwon, Yuguang Fang, Haniph Latchman, “Design of MAC Protocols With Fast Collision Resolution for Wireless Local Area Networks,” IEEE Trans. On Wireless Comm., vol. 3, no. 3, May 2004
[12] Chonggang Wang, Bo Li, Lemin Li, “A New Collision Resolution Mechanism to Enhance the Performance of IEEE 802.11 DCF,” IEEE Trans. On Vehicular Technology, vol. 53, no. 4, July 2004
[13] Frederico Cali, Marco Conti, Enrico Gregori, “Dynamic Tuning of the IEEE 802.11 Protocol to Achieve a Theoretical Throughput Limit,” IEEE/ACM Trans. On Networking, vol. 8, no. 6, December 2000
[14] M. Heusse, F. Rousseau, G. Berger-Sabbatel, A. Duda, “Performance anomaly of 802.11b,” INFOCOM 2003. Twenty-Second Annual Joint Conference of the IEEE Computer and Comm. IEEE Societies, vol.2, pp. 836-843, July 2008
[15] Shao-Yu Tan, “Rate-based Clustering Distributed Coordination Function for Qos – WiFi Technology,” Master Dissertation, Univ. of National Chiao Tung, Comm. Engineering Dept., Hsinchu, Taiwan, June 2014
[16] V. Gazis, N. Houssos, N. Alonistioti, and L. Merakos, “On the complexity of “Always Best Connected” in 4G mobile networks,” in Proc. of IEEE Vehicular Technology Conf. (VTC), Oct. 2003.
[17] C. Chang, T. Tsai, and Y. Chen, “Utility and Game-Theory Based Network Selection Scheme in Heterogeneous Wireless Networks,” in Proc. IEEE WCNC, Budapest, pp.1-5, April 5-8, 2009
[18] E. K. P. Chong and S. H. Zak, “An introduction to optimization,” John Wiley and Sons, Inc, 2001.
[19] Q. Nquyen-Vuong, Y. Ghamri-Doudane, and N. Agoulmine “On Utility Models for Access Network Selection in Wireless Heterogeneous Networks,” in Proc. 2008 IEEE NOMS, Salvador, Brazil, pp. 144-151.
[20] Narendra, K.S., Gallman, P., “An iterative method for the identification of nonlinear systems using a Hammerstein model,” IEEE Trans. Automatic Control, vol. 11, pp. 546-550, July 1966
[21] David C. Dobson, Curtis R. Vogel, “Convergence of an Iterative Method for Total Variation Denoising,” SIAM Journal on Numerical Analysis, vol. 34, pp. 1779-1791, July 2006