《電子技術應用》
您所在的位置：首頁 > 通信與網絡 > 設計應用 > 用于高速列車移動網絡的資源分配實時算法
用于高速列車移動網絡的資源分配實時算法
來源：電子技術應用2012年第12期
張永暉1,2, 蔣新華1, 林漳希3
1. 福建工程學院 福建省汽車電子與電驅動技術重點實驗室, 福建 福州350118; 2. 中南大學 信息科學與工程學院, 湖南 長沙 410083; 3. 德克薩斯理工大學 商學院， TX 79409-2101,美國
摘要： 誤碼率高、頻繁中斷的高速列車移動場景宜采用多宿主容遲網絡。但其資源分配計算復雜，實時性較差?；谛в貌罘址ㄔO計初始化過程資源分配算法，以保證過程中每一步的效用單調不減，算法時間復雜度降至O(n)。
中圖分類號： TP393
文獻標識碼： A
文章編號： 0258-7998(2012)12-0098-03
Real-time resource allocation algorithm on high-speed train mobile network
Zhang Yonghui1,2, Jiang Xinhua1, Lin Zhangxi3
1.Key Lab For Automobile Electronics & Electric Drive of Fujian Province, Fujian University of Techrology, Fuzhou 350108, China； 2. School of Information Science & Engineering, Central-South University, Changsha 410083, China； 3. The Rawls College of Business Admin, Texas Tech University, TX 79409-2101, USA
Abstract： High-speed train mobile scenarios is fitted to adopted multi-homing delay tolerant mobile network, alleviating high error rate and frequent disruptions effectively. However, its resource allocation algorithms on it are of computational complexity and poor real-time. Give an Initialization resource allocation algorithm, and ensure every step utility of processes non-decreasing with utility differential, gains O(n) algorithm time complexity.
Key words : high-speed mobile internet access; resource allocation algorithm; utility; delay tolerant network; multi-homing

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

    同時發(fā)現(xiàn)，初始化染色體如果隨機產生，迭代需要平均158.7次；使用上一輪的優(yōu)化數(shù)據(jù)作為下一輪輸入，則將降低到23.8次；然而最差仍要迭代89次。由此得到啟發(fā)，在上一輪歷史數(shù)據(jù)的基礎上計算效用的增減，效用增加則接受，效用減少則拒絕。實際上是以局部最優(yōu)化來逼近全局最優(yōu)化，從而減小計算量，滿足實時應用。
1 算法改良
    對初始化和接納控制的算法實施，如果先排序再滿足隊列中所有業(yè)務i的需求[2],算法時間復雜度為O(nlogn)，因為每次分配之后都要重新排序，計算量依然不小。
    為此，使用服務等級來分配帶寬，增加服務的子優(yōu)先級，作為最優(yōu)選擇的一種近似來設計算法。這實際上是使帶寬分配離散化，以減少重新計算的費用，避免資源分配調整過于頻繁。
 
 
    效用函數(shù)隊列調度簡化算法描述如下：
    Procedure_of_Enhanced_initialize ()
    Begin
    (1) 按用戶i和請求業(yè)務j映射最小帶寬等級minB(i,j)。按客戶實際請求和服務提供商的收費標準升降子等級m。//O(n)
    (2) If (Bremainder>0) and (count<sizeof(queue)) then // 帶寬有余且隊列不空
    (3)   For j=5 to 0 step -1 //從信令開始分配資源
    (4)     For m=9 to 0 step -1
    (5)       For Each e In group  (j,m)
    (6)         If bandwidth (queue) &ge;minB(i,j)  Then
    (7)           llocation(bandwidth(queue),e,minB(i,j)                            //分配資源
    (8)           bandwidth(queue)=bandwidth(queue)                              -minB(i,j)
    (9)         Else
    (10)           置標志skip(e)=1;累加器count+1                            //將i剔出隊列。
    (11)         End if
    (12)       Next e
    (13)     Next  m
    (14)   Next  j
    (15) End If
    End      /*首次計算按最小帶寬需求分配；類似的，如果帶寬有剩余,對隊列中所有skip(e)=0從高到底分配邊際帶寬：+diffj%； 如果帶寬無剩余，則終止。//算法中的效用可以是用戶與服務提供商雙方效用函數(shù)之和。*/
    上述算法對業(yè)務i進行分級計算后,劃分到group(j, m)。在group(j,m)中不進行排序，而是按照隊列或者鏈表串起來，因此，算法大大改進。雖然有嵌套循環(huán)，但實際執(zhí)行次數(shù)不大于Int(bandwidth(queue)/min(B(i)))，總的算法時間復雜度是O(n)。優(yōu)于參考文獻[2]提出的算法O(nlogn)。
    利用效用函數(shù)分級的優(yōu)點在于可以針對每一類業(yè)務甚至具體的業(yè)務實行不同的策略,以及可讓預留信道的閾值精確適應話務量變化，例如對切換掉話率的處理。常規(guī)方法是假定掉話用戶很難接受，通常優(yōu)先級設置很高，并以之衡量系統(tǒng)服務質量。然而事實上不同類業(yè)務掉線的負效用不一樣，同一類業(yè)務優(yōu)先級不同的業(yè)務掉線的負效用也不一樣，以效用函數(shù)不同的參數(shù)描述就能有針對性地靈活處理。
2 仿真和分析
    使用NS2仿真，比較參考文獻[2]的最優(yōu)化算法、參考文獻[3]的NEMO優(yōu)化算法（簡稱N+）、參考文獻[4]的SIP+SCTP+NEMO的方案(簡稱S+)以及與本文兩種算法的性能。模型為兩條100 km的正交十字型，采用WiFi小區(qū)沿途不完全覆蓋,直徑為1 km(站點數(shù)k=20、40、80、140、200)仿真。速度350 km/h(v)，并作規(guī)律性的停止，從上到下，從左到右。
 

 

 

優(yōu)化算法相差不大，而各方面均優(yōu)于N+方案，除新呼叫阻塞率外，也優(yōu)于S+方案。
    這是因為后兩者沒有針對容遲網絡場景做優(yōu)化，流量沒有達到飽和，尤其是NEMO成群切換移出WiFi熱區(qū)時，流量可能下降到0。NEMO方案根據(jù)信號和帶寬來選擇接入基站，之后又爭用蜂窩窄帶，導致流量改變較為劇烈。新呼叫阻塞率比S+差是因為次優(yōu)化算法是以切換優(yōu)先的策略，但兩者相差0.05，還可以忍受。
    本文提出的實時性資源分配次優(yōu)算法，用于容遲網絡的初始化過程和接納控制過程，在不明顯降低性能的前提下，達到了O(n)算法時間復雜度，能在極端環(huán)境下提供移動互聯(lián)網的實時應用。算法針對路徑可預知下的容遲網絡環(huán)境,如配合GPS路徑預測算法，可擴展到一般的容遲網絡。
參考文獻
[1] 張永暉, 蔣新華, 林漳希. 基于中斷和時延效用函數(shù)的多宿主分級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 schedulng 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.

此內容為AET網站原創(chuàng)，未經授權禁止轉載。