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

1、本文研究在高速運行環(huán)境中，基于蜂窩信息站集成網(wǎng)絡(luò)的非均勻?qū)捪聞討B(tài)效用無線報文調(diào)度算法，包括無特定用戶帶寬限制的調(diào)度算法和具有特定用戶帶寬限制的調(diào)度算法。
　　在蜂窩信息站集成網(wǎng)絡(luò)中，蜂窩網(wǎng)路提供低速較大范圍的網(wǎng)絡(luò)覆蓋，在鐵路沿線部署信息站，提供小范圍內(nèi)高速網(wǎng)絡(luò)傳輸，用戶通過蜂窩網(wǎng)絡(luò)請求數(shù)據(jù)，數(shù)據(jù)通過信息站作為網(wǎng)絡(luò)傳輸?shù)闹修D(zhuǎn)站，傳輸?shù)杰囕v站，這種網(wǎng)絡(luò)集成了信息站和傳統(tǒng)蜂窩網(wǎng)絡(luò)各自的優(yōu)點，能夠為高速鐵路環(huán)境提供較大范圍內(nèi)的高速傳輸率。

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

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

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