臺灣博碩士論文加值系統

無線網路中基地台之間負載是否平衡對於整體網路的產出量有著極大的影響，若能
分散各基地台的負載，避免部份基地台擁塞而部份基地台閒置的情況發生，將有效地提
升網路產出量。除了負載不均的問題之外，「效能異常現象」也是導致網路產能下降的
另一個主要原因。當不同連線速率的工作站聯結至相同基地台時，連線速率較高工作站
會為了等待連線速率較低之工作站完成傳輸，而喪失原本速率應有的產出量，進而導致
整體產出量大幅下降，此即效能異常現象。不幸地，現行的基地台選擇機制是以RSSI
值作為挑選依據，這使得負載不平衡問題時常發生，而傳統解決負載不均問題的聯結選
擇機制又忽略了效能異常現象的影響，使得即使AP 間負載完全平衡，但整體效能卻可
能因此而大幅下降。在本論文中我們以博奕理論的模型分析傳統無線基地台選擇機制，
並在考慮效能異常現象的前提下針對負載不均問題，提出具有重聯功能的完全資訊靜態
重覆無線基地台選擇賽局，及無重聯功能之完全資訊動態單次無線基地台選擇賽局。此
外，我們證明了完全資訊靜態重覆無線基地台選擇賽局中必定存在納許平衡，並說明了
如何尋找納許平衡之組態。而對於完全資訊動態單次選擇賽局，我們則是以實作的角度
加以探討，並在模擬實驗中呈現此賽局對於整體產出量、公平性之提昇結果及效能異常
現象改善之程度。

In IEEE 802.11 wireless local area networks, overall throughput will be decreased if most of WSs are associated with a few APs while other APs carry only light load or are idle. This is called load unbalancing problem. Another cause of throughput degradation is performance anomaly, which refers to the phenomenon that when multiple WSs associate to one AP with different link rates, the throughput of WSs transmitting at high link rate is degraded below the level of the lower-rate throughput. Few load balancing schemes have considered the impact of performance anomaly on throughput. Consequently, overall throughput may not be improved significantly even if the load between APs is completely balanced. This thesis uses game theory to analyze various ypes of AP association schemes. Particularly, we present complete-information static repeated AP selection game and complete-information dynamic one-shot AP selection game. We have proven that there must be Nash Equilibriums in complete-information static repeated game and show how to find Nash Equilibriums in this game. In addition, we have proposed a new scheme for
complete-information dynamic one-shot game. We also compared experimentally
complete-information and incomplete-information dynamic one-shot games in terms of throughput and fairness.

摘要 i
Abstract ii
致謝 iii
圖片目錄 v
表格目錄 vi
第一章 簡介 1
第二章 背景知識與相關研究 4
2.1 IEEE 802.11 4
2.2 Performance Anomaly 9
2.3 Game Theory 12
第三章 無線基地台選擇賽局的分析與設計 15
3.1 無線基地台選擇賽局的種類與分析 15
3.2 完全資訊靜態重覆無線基地台聯結選擇賽局 21
3.2.1 賽局定義 21
3.2.2 納許平衡存在之證明 24
3.3 完全資訊動態單次無線基地台聯結選擇機制 30
第四章 模擬實驗 33
4.1 實驗環境設定 33
4.2 實驗結果 35
第五章 結論 44
參考文獻 46

[1]I. Papanikos and M. Logothetis. “A study on dynamic load balance for IEEE 802.11b wireless LAN,” in Proc. COMCON, 2001.
[2]T.-C. Tsai and C.-F. Lien. “IEEE 802.11 hot spot load balance and QoS-maintained seamless roaming,” in Proc. National Computer Symposium(NCS), 2003.
[3]L.-H. Yen and T.-T. Yeh. “SNMP-based approach to load distribution in IEEE 802.11 networks,” in Proc. IEEE VTC 2006-Spring, Melbourne, Australia, May 2006, pp. 1196-1200.
[4]H. Velayos, V. Aleo, and G. Karlsson, “Load balancing in overlapping wireless LAN cells,” in Proc. IEEE ICC, Sept. 2004, pp. 3833-3836.
[5]L.-H. Yen, T.-T. Yeh, and K.-H. Chi, “Load balancing in IEEE 802.11 networks,” IEEE Internet Computing, vol. 13, pp. 30-38, Jan-Feb, 2009.
[6]M. Heusse, F. Rousseau, G. Berger-Sabbatel, and A. Duda, “Performance anomaly of 802.11b,” in Proc. INFOCOM 2003, San Francisco, CA, USA, 2003, pp. 836-843.
[7]P. Bahl, M. T. Hajiaghayi, K. Jain, and L. Qiu, “Cell breathing in wireless LANs: algorithms and evaluation,” IEEE Transactions on Mobile Computing, vol.6, pp. 164-178, Feb. 2007.
[8]E. Garcia, D. Viamonte, R. Vidal and J. Paradells. “Achievable bandwidth estimation for stations in multi-rate IEEE 802.11 WLAN cells,” in IEEE WoWMoM’07, Helsinki Finland, June 2007.
[9]D.-Y. Yand, T.-J. Lee, K. Jang, J.-B. Chang, and S. Choi. “Performance enhancement of multirate IEEE 802.11 WLANs with geographically scattered stations,” IEEE Transactions on Mobile Computing, vol. 5, no. 7, pp.906-919, 2006.
[10]G. R. Cantieni, Q. Ni, C. Barakat, and T. Turletti. “Performance analysis under finite load and improvements for multirate 8002.11,” Computer Communications, vol. 28, no. 10, June 2005.
[11]H. Kim, S. Yun, I. Kang, and S. Bahk. “Resolving 802.11 performance anomalies through QoS differentiation,” IEEE Communications Letters, vol. 9, no. 7, pp. 655-657, July 2005.
[12]Y. Bejerano, S.-J. Han, and L. Li. “Fairness and load balancing in wireless LANs using association control,” in Proc. MOBICOM, 2004, pp. 315-329.
[13]Y. Xiao, X. Shan, and Y. Ren “Game theory models for IEEE 802.11 DCF in wireless ad hoc networks,” IEEE Communications Magazine, vol. 43, pp. S22-S26, Mar. 2005.
[14]L. Chen and J. Leneutre, “On the power and rate control in IEEE 802.11 WLANs – A game theoretical approach,” in Proc. ICCCN, 2008, pp. 450-456.
[15]F. Cali, M. Conti, and E. Gregori, “IEEE 802.11 wireless LAN: capacity analysis and protocol enhancement,” in proc. INFOCOM, 1998.
[16]“The network simulator –ns-2,” http://www.isi.edu/nsnam/ns/.