以最佳化技術為基礎之減輕IEEE 802.11無線網路飢餓現象演算法

Abstract

隨著行動裝置不斷的出現，無線網路的使用率越來越高。 以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.