基于非齊次泊松過程的深空骨干節(jié)點流量分析

王小波 周賢偉 宋俊德

(1.北京科技大學計算機與通信工程學院通信工程系，北京 100083；2.北京郵電大學計算機學院，信息通信網(wǎng)絡與服務工程中心，北京 100876)

引 言

深空通信網(wǎng)絡或深空信息網(wǎng)絡[1](DSINs)主要由行星際衛(wèi)星及空間站組成，用以提供地球、外層空間行星及其子網(wǎng)、月球、衛(wèi)星及中繼站等信息傳輸?shù)耐ㄓ没A架構，包括在具有持久通信能力的元素間直接的與多跳路徑的數(shù)據(jù)鏈路[2]。作為行星際網(wǎng)絡的中繼，深空骨干網(wǎng)絡將各個行星子網(wǎng)聯(lián)系起來稱為一個整體，其承擔著較大的數(shù)據(jù)通信量及各種服務請求，骨干網(wǎng)絡節(jié)點的服務質量(QoS)提供能力將對整個深空通信網(wǎng)絡的通信質量產(chǎn)生決定性的影響。

對深空骨干網(wǎng)絡節(jié)點在一個時間段內(nèi)接收到的服務請求數(shù)量及業(yè)務處理時間進行分析可以有效地估計各個節(jié)點上的數(shù)據(jù)通信及信息處理負擔，從而對節(jié)點的QoS保證能力進行評價，為后續(xù)的路由提供參考，最大限度保障服務請求的QoS要求。然而現(xiàn)有的針對各類網(wǎng)絡節(jié)點業(yè)務量的分析大都是假設服務請求業(yè)務按照齊次泊松過程到達，文獻[3]提出的低軌衛(wèi)星切換管理方法改善了切換阻塞率，但假設呼叫的持續(xù)時間服從負指數(shù)分布，即認為呼叫到達率為常數(shù)；文獻[4]給出了一種自適應的信道分配算法，同樣提高了呼叫阻塞率，不過也一樣認為新的呼叫到達服從恒定參數(shù)的齊次泊松過程；文獻[5]為低軌衛(wèi)星的切換提出了一種新的隊列策略，提高了呼叫的成功率并降低了阻塞率，但文中將呼叫建模為M/M/S隊列系統(tǒng)，同樣認為呼叫到達率λ是常數(shù)。在以上文獻及類似研究中，都將呼叫或服務請求到達率假設為常數(shù)，通過齊次泊松過程對過程建模，然而這與實際情況并不符合，因為服務請求數(shù)量在某個時間段內(nèi)應該是隨時間變化的，在深空通信網(wǎng)絡間斷連接的條件下更是如此。

本文假設服務請求到達率是隨時間變化的函數(shù)λ(t)可以更貼近實際情況，通過計算用戶所關注時間段內(nèi)的節(jié)點業(yè)務到達數(shù)量和時間間隔概率密度，不但可以較為直觀地估計深空骨干網(wǎng)節(jié)點的QoS提供能力，同時可以為地球衛(wèi)星通信中呼叫接入控制及切換提供更切實的理論依據(jù)，并為路由節(jié)點選擇提供一定的參考。

1． 深空通信網(wǎng)絡結構及網(wǎng)絡業(yè)務流量模型

1.1 深空通信網(wǎng)絡結構

基于美國國家航空航天局(NASA)的行星間因特網(wǎng)(IPN Internet)，深空通信網(wǎng)絡基本結構如圖1所示。

圖1 深空通信網(wǎng)絡結構圖

深空通信網(wǎng)絡基礎架構的基本組成部分有[6]：①深空骨干網(wǎng)絡，主要部署在各個被探測星體之間作為各星體間通信的中繼網(wǎng)絡，提供遙遠星體或航天器之間的多跳可靠連接；②行星外層網(wǎng)絡，主要由各行星的衛(wèi)星網(wǎng)絡或航天器組成，用以提供對行星表面的通信覆蓋以及與深空骨干網(wǎng)絡的有效連接；③行星表面網(wǎng)絡，由行星表面的探測器及近地飛行器組成，用以在行星表面提供可靠的無線通信，并且可與行星外層網(wǎng)絡直接或間接通信，進行數(shù)據(jù)傳輸。

深空骨干網(wǎng)絡作為整個深空信息網(wǎng)的中轉站，承擔了大量的數(shù)據(jù)轉發(fā)任務，對其節(jié)點的QoS提供能力進行分析具有重大意義。

1.2 傳統(tǒng)網(wǎng)絡業(yè)務流量模型

網(wǎng)絡業(yè)務流量特征分析是進行高性能通信協(xié)議設計、負載均衡、提供QoS保障的基礎，同時也可對路由選擇提供依據(jù)，深空環(huán)境也是如此。合適的網(wǎng)絡業(yè)務流量模型可以幫助人們針對特定網(wǎng)絡環(huán)境設計更好的協(xié)議、采取更有效的QoS保證手段、保證關鍵業(yè)務得到必要的QoS.傳統(tǒng)的網(wǎng)絡業(yè)務流量模型一般是基于泊松過程的，比較經(jīng)典的主要有以下幾種[7-8]。

1) 泊松(poisson)模型

泊松模型最早是基于電話業(yè)務特征而提出的，可以較為準確地描述電話網(wǎng)中的業(yè)務流量特征從而得到廣泛應用。在早期的網(wǎng)絡業(yè)務流量建模中，泊松模型被廣泛使用。泊松模型是指對任何t,s≥0，N(s,t+s]服從參數(shù)為λt的泊松分布，即

(1)

從而可以計算出其相應的業(yè)務到達時間間隔序列呈負指數(shù)分布。泊松過程的強度λ表示單位時間間隔內(nèi)業(yè)務量出現(xiàn)的期望值，λ越大，單位時間內(nèi)平均出現(xiàn)的業(yè)務量越多，這正是λ稱為泊松過程強度的原因。

2) 馬爾可夫(Markov)模型

馬爾可夫模型是一種基于Poisson過程建模的模型，建立的基礎是無后效性和平穩(wěn)性。無后效性意味著下一個狀態(tài)僅僅依賴于當前狀態(tài)，而與過去的狀態(tài)無關，考慮的只是相鄰兩個狀態(tài)之間的相關性。平穩(wěn)性是指在較長時間后馬爾可夫過程趨于穩(wěn)定狀態(tài)，而與初始狀態(tài)無關。如果把“時刻n”看做“現(xiàn)在”，馬爾可夫性可以解釋為“知道現(xiàn)在”， “過去”與“將來”是相互獨立的，即如果在已知隨機事件An發(fā)生的條件下，An+1,An+2,…,中的某些事件的發(fā)生，與A1,A2,…,An-1中的事件的發(fā)生與否無關，則稱這一串事件{An∶n≥1}具有馬爾可夫性。常見的馬爾可夫模型主要有以下幾種：開-關源模型(On-Off 模型)，中斷泊松過程模型，狀態(tài)交替更新過程，馬爾可夫調(diào)制泊松過程，馬爾可夫調(diào)制流過程。

3) 回歸(regression)模型

回歸模型隨機序列中，下一時刻隨機變量值是由當前和過去若干個隨機變量值以及一個白噪聲的函數(shù)來決定的。常見的回歸模型有：自回歸模型(AR)，離散自回歸模型(DAR)，自回歸滑動平均模型(ARMA)，求和自回歸滑動平均模型(ARMA)，變換擴展采樣模型(TES)。其中自回歸模型、離散回歸模型、自回歸移動平均模型要求流量序列是平穩(wěn)序列，而自回歸移動平均求和模型可以處理有周期性和趨勢性的非平穩(wěn)序列，變換擴展采樣模型則適合用來描述高速突發(fā)業(yè)務流。

以上傳統(tǒng)的業(yè)務流量模型優(yōu)點是概率理論及相關知識體系發(fā)展比較完善，隊列系統(tǒng)性能評價容易得到解析結果。然而，以泊松過程理論為基礎的傳統(tǒng)模型，大多存在一定缺陷，尤其是深空這種業(yè)務量在時間和空間上服從一定規(guī)律性的特定環(huán)境中。例如，實際業(yè)務量到達是相關聯(lián)的且并不嚴格服從泊松分布時，過程強度函數(shù)通常不為常數(shù)，而是隨時間呈現(xiàn)某種規(guī)律。在文獻[9]中，分析了衛(wèi)星網(wǎng)絡的流量負載隨時間變化情況，發(fā)現(xiàn)上傳和下載流量均隨時間呈現(xiàn)某種規(guī)律性變化，說明服務請求數(shù)量也呈現(xiàn)相應變化規(guī)律。深空通信中節(jié)點的流量特性還取決于地面通信需求量，由于地球上的地域差別、不同區(qū)域的人口密度差異，不同區(qū)域的通信需求量也不盡相同，在文獻[10-11]中，就分析了地面系統(tǒng)流量非均勻分布所帶來的影響。因此，需要采用非齊次泊松過程對深空通信中骨干節(jié)點業(yè)務量進行描述和建模，并結合馬爾可夫序列理論進行分析，假設過程強度不為常數(shù)且呈現(xiàn)某種規(guī)律性，以期更為貼近實際情況。

2． 深空骨干網(wǎng)節(jié)點業(yè)務流量分布模型

由于深空網(wǎng)絡具有長傳播延時、高誤碼率等特點，因此對于節(jié)點的業(yè)務到達數(shù)量及時間間隔分布進行估算具有十分重要的意義，同時可為后續(xù)的深空節(jié)點流量負載均衡提供參考。而在節(jié)點QoS能力評價方面，通常采用節(jié)點可用時長、鏈路質量來進行衡量[12]，以流量均衡為目標的路由選擇及決策可以避免擁塞、降低鏈路時延，對于提高鏈路QoS指標具有顯著效果[13-14]。為簡便起見，這里將節(jié)點業(yè)務看作一定數(shù)量的服務請求，節(jié)點對到達業(yè)務的處理即為對服務請求的響應。由于假設業(yè)務的服務請求到達率不為常數(shù)，因此在某個時間段內(nèi)的業(yè)務到達數(shù)量也就不再服從泊松分布，相應的情況將變得更加復雜。下面從一類特殊非齊次泊松過程—帶時倚強度泊松過程的定義入手，得出相關結論。

定義1[15]計數(shù)過程{Nt；t≥0}稱為帶時倚強度的泊松過程，如果它滿足下列條件：

①P(N0=0)=1

② 對任意t≥0和h>0，當h→0時：

P1[t,t+h)=P(Nt,t+h=1)=λ(t)h+o(h)

③ 在互不相交區(qū)間上增量具有獨立性

P(Nt,t+s=n) =exp{-[Λ(t+s)-Λ(t)]}×

[Λ(t+s)-Λ(t)]n/n!

(2)

類似于假設服務請求到達分布服從齊次泊松過程的情形，也能推導出帶時倚強度泊松過程的到達時間和到達時間間隔的一些有關的分布。對于齊次泊松過程，當給定過程在(0,L]時間段內(nèi)有n個服務請求到達時，這n個服務請求到達時間S1,…,Sn的條件聯(lián)合分布和n個在(0,L]上均勻分布的獨立隨機變量的次序統(tǒng)計量的分布相同。利用類似的推理可以把此結果推廣到時倚強度的情形。

定理1：設{Nt,t≥0}是帶時倚強度λ(t)的泊松過程。對于任意正整數(shù)n，過程的前n個到達時間S1,…,Sn的聯(lián)合分布密度函數(shù)為

fS1,…,Sn(t1,…,tn)

(3)

證明：

P(ti-Δti

=P(N0,t1-Δt1=0;

Nti,ti+1-Δti+1=0，1≤i≤n-1;

Nti-Δti,ti=1,1≤i≤n)

根據(jù)聯(lián)合發(fā)生密度的定義有

fS1,…,Sn(t1,…,tn)

類似的，過程的任意n個到達時間的聯(lián)合分布密度函數(shù)可由定理2給出。

fSr+1,…,Sr+n(tr+1,…,tr+n)

(4)

帶時倚強度λ(t)的泊松過程{Nt,t≥0}的到達時間序列S1,…,Sn,…是一馬爾可夫序列，按轉移密度的定義和過程的n個發(fā)生時間的聯(lián)合分布密度函數(shù)可知它的轉移密度為

PSn|Sn-1,…,S1(tn|tn-1,…,t1)

(5)

而

(6)

可見式(5)和式(6)表達式一致。已知具有常數(shù)強度λ的齊次泊松過程的到達時間間距Tn=Sn-Sn-1(n=1,2,…)相互獨立而且都有參數(shù)為λ的指數(shù)分布。當強度不再是常數(shù)而是隨時間變化時，Tn一般就既不是相互獨立，也不再有相同分布了。但是，由過程的無后效性易知當給定了S1,…,Sn時，第n+1個到達時間間距Tn+1=Sn+1-Sn是獨立于S1,…,Sn-1的。因此，由以上結果可以推出給定S1,…,Sn時Tn+1的條件密度函數(shù)為

fTn+1|Sn,…,S1(t|Sn,…,S1)

=fSn+1|Sn,…,S1(Sn+t|Sn,…,S1)

[10]Oxford,R.L.Language Learning Strategies:What Every Teacher Should Know.New York:Newbury House.1990.

=fSn+1|Sn(Sn+t|Sn)

(7)

由式(7)得到條件分布函數(shù)為

P(Tn+1≤t|Sn=sn,…,S1=s1)

(8)

由式(2)可知，在時長h的時間段內(nèi)到達的服務請求數(shù)量小于k的概率為

P(Tt+h-Nt

(9)

從以上分析可知，在已知服務請求到達率函數(shù)λ(t)的情況下，由式(8)可以對節(jié)點到達服務請求時間間隔小于某個限定值的概率進行估算，得出其概率取值范圍。而由式(9)可以得到在某個時間段內(nèi)服務請求到達數(shù)量小于某個閾值的概率。在此基礎上可以對深空骨干網(wǎng)節(jié)點業(yè)務量進行初步的估計，從而為后繼的路由節(jié)點選擇及負載均衡提供依據(jù)。

3．仿真結果與分析

為了更加直觀地展現(xiàn)前文提出的深空通信網(wǎng)絡骨干節(jié)點所收到的業(yè)務流量分布特點，我們進行了進一步的數(shù)值分析。為了估計服務請求在未來的某一時間段Δt內(nèi)得到成功響應的可能性，需要計算下一次請求到達時間間距大于Δt的概率。由于請求的服務時間決定于節(jié)點所收到的請求數(shù)，為了保證系統(tǒng)中的服務請求得到充分響應，必須保證系統(tǒng)中的請求數(shù)小于某一值的概率。

我們分別比較了服務請求到達率符合高斯分布函數(shù)、指數(shù)分布函數(shù)、對數(shù)函數(shù)，以及通常采用的服務請求到達率為常數(shù)時Δt時間段內(nèi)無服務請求到達的概率P(Tn+1>Δt)，以及在時長h的時間段內(nèi)到達的服務請求數(shù)量小于k的概率P(Nt+h-Nt

表1 服務請求到達率函數(shù)

在圖2中仿真時間為24 h，Δt=0.5，即半小時內(nèi)無服務請求到達的概率。用表1所示的函數(shù)模擬了不同的服務請求到達率，在實際中也可以根據(jù)實測統(tǒng)計數(shù)據(jù)采用相應函數(shù)進行擬合。

圖2 Δt時間段內(nèi)無服務請求到達的概率 隨時間變化趨勢

由圖1可以發(fā)現(xiàn)，P(Tn+1>Δt)與到達率函數(shù)變化趨勢相反，即當服務請求到達率增加時，未來Δt內(nèi)無請求到達的概率變小。圖3顯示了間隔時長h在不同時刻對到達的服務請求數(shù)量小于k(k=5)的概率的影響，可以看出，隨著h的增大，概率基本呈現(xiàn)減小的趨勢，且函數(shù)變化趨勢越明顯則減少越劇烈，這意味著間隔時長越長出現(xiàn)更多服務請求的概率越大。圖4展示的是數(shù)量k對請求數(shù)量小于k的概率在不同時刻的影響，Δt=0.5，k與概率值變化趨勢基本一致，而在k一定時，如果λ(t)是增函數(shù)，意味著單位時間內(nèi)到達的服務請求將增加，從而導致Δt內(nèi)服務請求數(shù)量小于k的概率減小，相反，則概率增大。

由以上分析可見，相對于傳統(tǒng)的假設服務請求到達率為常數(shù)的情況，新的方法更具有廣泛性，能適應各種不同條件下的服務請求到達分布，更接近實際情況，對于由地域因素及衛(wèi)星等深空節(jié)點規(guī)律性運動所引起的服務請求到達率變化可以進行較好的數(shù)值擬合。同時，為深空節(jié)點存儲轉發(fā)策略與路由節(jié)點選擇也能提供更可靠的依據(jù)。

4． 總結與展望

深空通信網(wǎng)絡環(huán)境復雜，具有長時延、傳輸距離遠等特點。對骨干節(jié)點的業(yè)務量特點進行分析可以明確節(jié)點的QoS提供能力，從而充分利用整網(wǎng)資源，避免單個節(jié)點負載過重，降低業(yè)務的排隊等待時間。在假設服務請求到達率不為常數(shù)的情況下，某個時間段內(nèi)的服務請求到達率可以由經(jīng)驗數(shù)據(jù)分析得到，采用相應函數(shù)擬合，從而在所關注的時間段內(nèi)更貼近實際情況來分析節(jié)點負載。

文中提供了一個對深空骨干網(wǎng)節(jié)點業(yè)務量估計的較為直觀的參考，其方法為深空通信網(wǎng)絡節(jié)點負載分析提供了一種新的研究思路，為深空通信網(wǎng)絡路由節(jié)點選擇提供了一定的依據(jù)。當然，深空通信網(wǎng)絡的研究仍然處于初期，還有更多的問題等待我們?nèi)ソ鉀Q，文中的方法及思路也還有待探討完善。

[1] ZHOU Xianwei, ZHANG Long, CHENG Zhimi, et al. Hypernetwork model and architecture for deep space information networks[C]//Proceedings of the 2010 IEEE International Conference on Future Information Technology(ICFIT’10). Changsha, China, Dec 14-15, 2010: 448-452.

[2] 周賢偉. 深空通信[M]. 北京: 國防工業(yè)出版社, 2009: 222.

[3] CHO S, AKYILDIZ I F, BENDER M D, et al. A new spotbeam handover management technique for leo satellite networks[C]// IEEE Global Telecommunications Conference. San Francisco, CA, USA, 2000: 1156-1160.

[4] CHO S. Adaptive dynamic channel allocation scheme for spotbeam handover in LEO satellite networks[C]//IEEE Vehicular Technology Conference. Boston, MA, USA, 2000: 1925-1929.

[5] KIAMOUCHE W, BENSLAMA M. Pseudo last useful instant queuing strategy for handovers in low earth orbit mobile satellite networks[J]. International Journal of Information Technology, 2008, 4(5): 369-375.

[6] AKYILDIZ I F, AKAN O B, CHEN C, et al. InterPlaNetary internet: state-of-the-art and research challenges [J]. Computer Networks Journal, Elsevier Science, 2003, 43(2): 75-112.

[7] 張 賓, 楊家海, 吳建平. Internet流量模型分析與評述[J]. 軟件學報, 2011, 22(1): 115-131.

ZHANG Bin, YANG Jiahai, WU Jianping. Survey and analysis on the internet traffic model [J]. Journal of Software, 2011, 22(1): 115-131. (in Chinese)

[8] 周曉瑋. 網(wǎng)絡流量的模型分析和異常檢測[D]. 大連: 大連海事大學, 2006.

ZHOU Xaiowei. The model analysis and anomaly detection of network traffic[D]. Dalian: Dalian Maritime University, 2006. (in Chinese)

[9] SHAO Q. Measurement and analysis of traffic in hybrid satellite-terrestrial network [D]. Burnaby: Simon Fraser University, 2004.

[10] SATO S. A performance analysis on nonuniform traffic in micro cell systems[C]// Proc. IEEE ICC’93. Geneva, Switzerland, May 23-26, 1993(3):1960-1964.

[11] TALEB T , JAMALIPOUR A , KATO N. IP traffic load distribution in NGEO broadband satellite networks[J]. Computer and Information Sciences, 2005, 3733: 113-123.

[12] HADJITHEODOSIOU M H, NGUYEN A T. Using commercial satellites to provide communication support for space missions[C]// IEEE Global Telecommunications Conference. San Francisco, CA, USA, 2000, 2:1135-1139.

[13] YAO Danlin, WANG Cheng, SHEN Jianhui. Traffic-adaptive hybrid routing algorithm for double-layered satellite networks[C]// Biomedical Engineering and Informatics. Tianjin, China, October, 17-19, 2009: 1-6.

[14] YUAN Zhe, ZHANG Jun, LIU Zhongkan. Routing in LEO/MEO double-layered satellite networks[C]// International Conference on Wireless Communications, Networking and Mobile Computing, September，22-24, 2006: 1-4.

[15] 鄧永錄, 梁之舜. 隨機點過程及其應用[M]. 北京: 科學出版社, 1992: 61-71.