非均勻帶寬下動態(tài)效用無線報文調度算法研究.pdf

1、本文研究在高速運行環(huán)境中，基于蜂窩信息站集成網絡的非均勻寬下動態(tài)效用無線報文調度算法，包括無特定用戶帶寬限制的調度算法和具有特定用戶帶寬限制的調度算法。
　　在蜂窩信息站集成網絡中，蜂窩網路提供低速較大范圍的網絡覆蓋，在鐵路沿線部署信息站，提供小范圍內高速網絡傳輸，用戶通過蜂窩網絡請求數據，數據通過信息站作為網絡傳輸的中轉站，傳輸到車輛站，這種網絡集成了信息站和傳統(tǒng)蜂窩網絡各自的優(yōu)點，能夠為高速鐵路環(huán)境提供較大范圍內的高速傳輸率。

2、高速鐵路等高速運行的環(huán)境中，無線網絡用戶的按需請求服務數據，通過路邊的信息站發(fā)送到用戶終端設備上，而往往該段的調度是整個網絡系統(tǒng)的瓶頸所在。為了提高在該環(huán)境下用戶網絡服務體驗，為用戶提供穩(wěn)定高效的按需網絡服務，同時提高網絡提供者獲得的總收益，提出了按需服務的無線報文最優(yōu)調度問題。
　　本文分析兩種問題的模型：無特定用戶帶寬限制的調度問題和具有特定用戶帶寬限制的調度問題。通過分析兩種調度問題的特殊結構，將問題轉化為一個整形規(guī)劃問題，

3、進而將問題轉化為0-1規(guī)劃問題。能夠證明，該調度問題是NP問題，不能通過現有算法在多項式時間內求得最優(yōu)解。我們提出了一種基于新效用函數的貪心算法，并且提出再調度函數，為當前正在調度的數據包找出再調度路徑，增加調度的數據包的數量。
　　針對具有特定用戶帶寬限制的調度問題，將其轉化為求解二分圖的最大權匹配問題，利用Kuhn-Munkres算法可以在多項式時間內求得近似最優(yōu)解。首先，我們提出了新的更加一般化的價格(效用)函數，即用戶愿意

4、為在不同時間內被調度的數據包所支付的價格是不同的，數據包服務的動態(tài)效用化。第二，我們分析了求解非均勻寬下動態(tài)效用無線報文調度問題的貪心算法；其次，我們將非均勻寬下動態(tài)效用無線報文調度問題轉化為加權二分圖的最大權匹配問題。通過分析具體問題中的限制條件，修改轉化為加權二分圖的規(guī)則，使得修改后的二分圖的一個匹配集合是原調度問題可行解集的一個子集，而最優(yōu)匹配在原問題中可能不是最優(yōu)的，但是可以求得近似最優(yōu)解。
　　最后，我們利用仿真來證明各