用于高速列車移動網絡的資源分配實時算法*

張永暉,蔣新華,林漳希

(1.福建工程學院 福建省汽車電子與電驅動技術重點實驗室,福建 福州 350118;2.中南大學 信息科學與工程學院,湖南 長沙 410083;3.德克薩斯理工大學 商學院，TX 79409-2101,美國）

針對高速列車移動網絡設計了基于容遲網絡的多宿主列車移動網絡方案，提出資源分配效用模型[1]，然而參考文獻[2]中使用基于神經網絡的遺傳算法，迭代次數較多，不利于實時應用。

同時發現，初始化染色體如果隨機產生，迭代需要平均158.7次；使用上一輪的優化數據作為下一輪輸入，則將降低到23.8次；然而最差仍要迭代89次。由此得到啟發，在上一輪歷史數據的基礎上計算效用的增減，效用增加則接受，效用減少則拒絕。實際上是以局部最優化來逼近全局最優化，從而減小計算量，滿足實時應用。因為每次分配之后都要重新排序，計算量依然不小。

為此，使用服務等級來分配帶寬，增加服務的子優先級，作為最優選擇的一種近似來設計算法。這實際上是使帶寬分配離散化，以減少重新計算的費用，避免資源分配調整過于頻繁。

1 算法改良

對初始化和接納控制的算法實施，如果先排序再滿足隊列中所有業務i的需求[2],算法時間復雜度為O(nlogn)，

由協議和端口號可得到服務種類j。令Bj,m(j=0～3，m=0～h)表示第j種業務的可用帶寬等級,按效用值映射基本帶寬子級m，仿真中取 h=9，則 m=0～9。然而 Bj,m與 Bj,m+1總是相差 diffj%(m=0～8)。j=4、5 時，定義為實時通信，沒有帶寬變化。設Bt為當前網絡總帶寬，BA為當前網絡可用總帶寬，定義當前帶寬忙閑度：δbusy=INT((h+1)*BA/Bt)，則分給請求 i帶寬 Bj,m，業務子級 m=h-δbusy。 網絡越繁忙，δbusy越大，從而分配給的帶寬子級越小。因此可自適應調節業務子級。 j=5、4 時，依次分派指定帶寬；j=3，2，1，0 時，分配Bj,m的帶寬。

效用函數隊列調度簡化算法描述如下：

上述算法對業務i進行分級計算后,劃分到group(j,m)。在group(j,m)中不進行排序，而是按照隊列或者鏈表串起來，因此，算法大大改進。雖然有嵌套循環，但實際執行次數不大于 Int(bandwidth(queue)/min(B(i)))，總的算法時間復雜度是O(n)。優于參考文獻[2]提出的算法O(nlogn)。

利用效用函數分級的優點在于可以針對每一類業務甚至具體的業務實行不同的策略,以及可讓預留信道的閾值精確適應話務量變化，例如對切換掉話率的處理。常規方法是假定掉話用戶很難接受，通常優先級設置很高，并以之衡量系統服務質量。然而事實上不同類業務掉線的負效用不一樣，同一類業務優先級不同的業務掉線的負效用也不一樣，以效用函數不同的參數描述就能有針對性地靈活處理。

2 仿真和分析

使用NS2仿真，比較參考文獻[2]的最優化算法、參考文獻[3]的 NEMO優化算法（簡稱 N+）、參考文獻[4]的SIP+SCTP+NEMO的方案(簡稱S+)以及與本文兩種算法的性能。模型為兩條100 km的正交十字型，采用WiFi小區沿途不完全覆蓋,直徑為 1 km(站點數 k=20、40、80、140、200)仿真。 速度 350 km/h(v)，并作規律性的停止，從上到下，從左到右。

設WiFi網絡帶寬為54 Mb/s，蜂窩網絡帶寬為3.84 Mb/s，假定有 500個 MSj，各類業務的到達時間服從泊松分布，用戶的到達相互獨立，移動站MSp1請求業務tp精確到 0.1 s。不同的業務組合確定如下:時長 (t0～t4都服從負指數分布,均值 1/μ 分別為3 000 s、100 s、200 s、100 s、200 s)，信令業務 5響應所有請求，因此定 34 kb/s；對于語音固定優先級，取帶寬rv-min=12.0 kb/s;取參數Umin=1.5;Uv=4；a=0.1;b=55;c=7。設WiFi網絡帶寬為54 Mb/s，蜂窩網絡帶寬為 3.84 Mb/s，假定有 500個 MSj，各類業務的到達時間服從泊松分布，用戶的到達相互獨立，移動站MSp1請求業務tp精確到 0.1 s。

不同的業務組合確定如下:時長(t0～t4都服從負指數分布, 均值 1/μ 分別為 3 000 s、100 s、200 s、100 s、200 s)，信令業務5響應所有請求，因此定 34 kb/s；對于語音固定優先級，取帶寬rv-min=12.0 kb/s;取參數Umin=1.5;Uv=4；a=0.1;b=55;c=7。此外多媒體流網絡中傳輸350 kb/s，Bj4電子郵件類 30 kb/s，數據庫類200 kb/s，交互式應用200 kb/s，每一級別正負5%。設資源預取設命中率為0.85，結果見圖1～圖3。在普通微機上執行實時性對比結果見表1。

可以看出，對于實時性而言，所提出的次優化算法是四種算法中最好的。而執行效率與參考文獻[2]中最優化算法相差不大，而各方面均優于N+方案，除新呼叫阻塞率外，也優于S+方案。

表1 算法實時性比較

這是因為后兩者沒有針對容遲網絡場景做優化，流量沒有達到飽和，尤其是NEMO成群切換移出WiFi熱區時，流量可能下降到0。NEMO方案根據信號和帶寬來選擇接入基站，之后又爭用蜂窩窄帶，導致流量改變較為劇烈。新呼叫阻塞率比S+差是因為次優化算法是以切換優先的策略，但兩者相差0.05，還可以忍受。

本文提出的實時性資源分配次優算法，用于容遲網絡的初始化過程和接納控制過程，在不明顯降低性能的前提下，達到了O(n)算法時間復雜度，能在極端環境下提供移動互聯網的實時應用。算法針對路徑可預知下的容遲網絡環境,如配合GPS路徑預測算法，可擴展到一般的容遲網絡。

[1]張永暉,蔣新華,林漳希.基于中斷和時延效用函數的多宿主分級DTN列車移動網絡資源分配模型[J].鐵道學報，2010,32(6):15-22.

[2]CHEN L W,TSENG Y C,WANG Y C et al.Exploiting spectral reuse in routing,resource allocation,and scheduling for IEEE 802.16 mesh networks[J].IEEE Transactions on Vehicular Technology.2009,58(1):301-313.

[3]任彥，蘇偉，張思東.列車移動網絡關鍵技術的研究[J].鐵道學報，2006,28(1):121-124.

[4]Leu Fangyie.A novel network mobility handoff scheme using SIP and SCTP for multimedia applications[J].Journal of Network and Computer Applications.2009,32(5):1073-1091.