文獻標識碼： A
文章編號： 0258-7998(2012)12-0098-03
針對高速列車移動網絡設計了基于容遲網絡的多宿主列車移動網絡方案，提出資源分配效用模型[1]，然而參考文獻[2]中使用基于神經網絡的遺傳算法，迭代次數較多，不利于實時應用。
同時發現，初始化染色體如果隨機產生，迭代需要平均158.7次；使用上一輪的優化數據作為下一輪輸入，則將降低到23.8次；然而最差仍要迭代89次。由此得到啟發，在上一輪歷史數據的基礎上計算效用的增減，效用增加則接受，效用減少則拒絕。實際上是以局部最優化來逼近全局最優化，從而減小計算量，滿足實時應用。
1 算法改良
對初始化和接納控制的算法實施，如果先排序再滿足隊列中所有業務i的需求[2],算法時間復雜度為O(nlogn)，因為每次分配之后都要重新排序，計算量依然不小。
為此，使用服務等級來分配帶寬，增加服務的子優先級，作為最優選擇的一種近似來設計算法。這實際上是使帶寬分配離散化，以減少重新計算的費用，避免資源分配調整過于頻繁。
效用函數隊列調度簡化算法描述如下：
Procedure_of_Enhanced_initialize ()
Begin
(1) 按用戶i和請求業務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) ≥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%； 如果帶寬無剩余，則終止。//算法中的效用可以是用戶與服務提供商雙方效用函數之和。*/
上述算法對業務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)，并作規律性的停止，從上到下，從左到右。
優化算法相差不大，而各方面均優于N+方案，除新呼叫阻塞率外，也優于S+方案。
這是因為后兩者沒有針對容遲網絡場景做優化，流量沒有達到飽和，尤其是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 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.