劉 軍,高玉嵩,王 皓,姜向宏
(1. 東北大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院,遼寧 沈陽110819;2.湖北工業(yè)大學(xué)工程技術(shù)學(xué)院,湖北 武漢430068)
隨著空間技術(shù)的不斷突破,天基網(wǎng)絡(luò)發(fā)揮的作用已經(jīng)得到了各個(gè)國家的廣泛認(rèn)可。天基網(wǎng)絡(luò)作為空天一體化網(wǎng)絡(luò)的重要一環(huán),在服務(wù)于國家戰(zhàn)略的同時(shí),也悄然的影響著民用和商業(yè)通信領(lǐng)域的建設(shè)與發(fā)展??梢哉f不論是從國家戰(zhàn)略利益,還是航天測控、通信保障,均離不開天基網(wǎng)絡(luò)的服務(wù)保障[1]。
針對靜態(tài)網(wǎng)絡(luò)的拓?fù)洳季忠呀?jīng)有了相當(dāng)深入的研究,但靜態(tài)布局很難保證天基網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的相對穩(wěn)定性。針對天基網(wǎng)絡(luò)的動(dòng)態(tài)特性,需要找出既能突出拓?fù)浣Y(jié)構(gòu)的差異性又能保持視覺上的穩(wěn)定的布局方法,本論文提出了一種基于動(dòng)態(tài)特征的可視化布局方法。天基網(wǎng)絡(luò)的動(dòng)態(tài)特征就是天基網(wǎng)絡(luò)的星間鏈路的變化情況,這種變化是在時(shí)間維度上的。為了將天基網(wǎng)絡(luò)的差異性進(jìn)行突出顯示,提出一種分階段的動(dòng)畫轉(zhuǎn)換策略;同時(shí)為保證拓?fù)浣Y(jié)構(gòu)的穩(wěn)定性提出一種動(dòng)畫布局穩(wěn)定性策略,對天基網(wǎng)絡(luò)的時(shí)空圖模型進(jìn)行展示。通過對動(dòng)畫轉(zhuǎn)換的穩(wěn)定狀態(tài)和過渡狀態(tài)分析,研究天基網(wǎng)絡(luò)的分階段動(dòng)態(tài)可視化方法和動(dòng)畫布局穩(wěn)定策略,實(shí)現(xiàn)天基網(wǎng)絡(luò)的遞進(jìn)式動(dòng)態(tài)可視化方法。
目前,研究者對動(dòng)態(tài)網(wǎng)絡(luò)可視化進(jìn)行了一些研究。劉真等人[2]指出通過動(dòng)態(tài)圖模型解決動(dòng)態(tài)網(wǎng)絡(luò)展示問題的解決辦法,結(jié)合可視化的目標(biāo)和需求,探討動(dòng)態(tài)網(wǎng)絡(luò)可視分析法在不同領(lǐng)域的應(yīng)用。于少波等人[3]闡述了多層網(wǎng)絡(luò)可視化和動(dòng)態(tài)網(wǎng)絡(luò)可視化的特點(diǎn)、發(fā)展現(xiàn)狀和主要技術(shù),并分析了當(dāng)前存在的主要問題。Friedrich和EADES[4]開發(fā)了一款Marey的可視化工具,主要采用線性插值法與分步轉(zhuǎn)換法相結(jié)合的思想實(shí)現(xiàn)動(dòng)畫的過渡。Bach等人[5]構(gòu)建了Graph Diaries的軟件包,實(shí)現(xiàn)方法與Friedrich的方法類似,均采用了先消除舊元素后增加新元素的辦法,不同的是Graph Diaries為突出拓?fù)渥兓闆r采用對新元素的突出顯示加以實(shí)現(xiàn)。Huang等人[6]提出了中間過度實(shí)現(xiàn)動(dòng)畫轉(zhuǎn)化的方法,主要操作是調(diào)整新元素的位置到布局的中心,根據(jù)力導(dǎo)向布局算法對與新元素相連的舊元素進(jìn)行同步移動(dòng)。
現(xiàn)階段的可視化研究僅限于對衛(wèi)星的運(yùn)動(dòng)軌跡的展示,缺乏對邏輯拓?fù)浣Y(jié)構(gòu)及變化規(guī)律等抽象信息的研究。因此很難從天基網(wǎng)絡(luò)中挖掘出需要的信息。而且天基網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)的動(dòng)態(tài)變化展示過程還不夠平穩(wěn)、一些方法也存在迭代次數(shù)過多達(dá)到穩(wěn)態(tài)緩慢的問題。
時(shí)空變化過程實(shí)質(zhì)是一系列沿時(shí)間軸的天基網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變化過程。時(shí)空圖的描述包括節(jié)點(diǎn)、邊和屬性三個(gè)基本方面,因此,時(shí)空變化包括沿時(shí)間軸的節(jié)點(diǎn)變化、邊變化和屬性變化。事實(shí)上,后一時(shí)刻的節(jié)點(diǎn)、邊、屬性特征均與前一狀態(tài)的相應(yīng)值有關(guān)系。在不同的時(shí)刻,時(shí)空圖的節(jié)點(diǎn)、邊和屬性特征可能全部變化、兩項(xiàng)變化或單項(xiàng)變化。
空間變化事件是天基網(wǎng)絡(luò)時(shí)空圖模型演化過程中的關(guān)鍵事件,能通過空間變化事件展現(xiàn)天基網(wǎng)絡(luò)的動(dòng)態(tài)轉(zhuǎn)換過程。天基網(wǎng)絡(luò)的時(shí)空圖序列如圖1所示,G(ti)表示ti時(shí)刻的時(shí)空圖模型的拓?fù)浣Y(jié)構(gòu)圖[7]。在時(shí)空圖的演化過程中網(wǎng)絡(luò)的邊隨著時(shí)間的變化不斷出現(xiàn)、消失。但相鄰時(shí)刻時(shí)空圖模型的拓?fù)浣Y(jié)構(gòu)可能是相同的,也可能是不同的[8]。文章所關(guān)注的是拓?fù)浣Y(jié)構(gòu)的差異性,因此需要將相鄰的具有差異性的拓?fù)浣Y(jié)構(gòu)提取出來,剔除掉相鄰的相同的拓?fù)浣Y(jié)構(gòu)??臻g變化事件主要用于表述相鄰時(shí)刻之間網(wǎng)絡(luò)拓?fù)涞牟町愋?,其原理如圖2所示。
圖1 天基網(wǎng)絡(luò)時(shí)空圖序列
圖2 空間變化事件構(gòu)建示意圖
空間變化事件的主要作用有:
1)將時(shí)空圖中的數(shù)據(jù)進(jìn)行簡化處理,找出相鄰的差異的拓?fù)浣Y(jié)構(gòu);
2)對相鄰時(shí)刻未發(fā)生拓?fù)渥兓慕Y(jié)構(gòu)進(jìn)行弱化處理,減少布局的工作量的同時(shí)對天基網(wǎng)絡(luò)的拓?fù)渥兓闆r進(jìn)行突出顯示。
空間變化事件僅記錄增加或者刪除的邊,不記錄保持不動(dòng)的邊[9]。
根據(jù)空間變化事件構(gòu)建的方法,在天基網(wǎng)絡(luò)時(shí)空圖模型中,兩個(gè)相鄰的時(shí)刻G(ti-1)=(V(ti-1),E(ti-1))和G(ti)=(V(ti),E(ti))的空間變化事件記為D(ti),定義為
D(ti)=ED(ti)=G(ti)-G(ti-1)
(1)
其中,ED(ti)為ti時(shí)刻發(fā)生變化的邊集,DS={D(ti)|i=1,…,n}是空間變事件序列,D(ti)中包括邊的增加狀態(tài)和減少狀態(tài),Eadd(ti)表示增加的邊,Edis(ti)表示刪除的邊,則ED(ti)=Eadd(ti)+Edis(ti)。
僅僅利用針對靜態(tài)網(wǎng)絡(luò)的拓?fù)洳季址椒ㄟM(jìn)行布局,相鄰的兩個(gè)時(shí)刻的布局效果可能會(huì)產(chǎn)生視覺上的跳變,從而很難保證天基網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的相對穩(wěn)定性。針對天基網(wǎng)絡(luò)的動(dòng)態(tài)特性,需要找出既能突出拓?fù)浣Y(jié)構(gòu)的差異性又能保持視覺上的穩(wěn)定的布局方法。本節(jié)提出了一種基于動(dòng)態(tài)特征的可視化布局方法。天基網(wǎng)絡(luò)的動(dòng)態(tài)特征就是天基網(wǎng)絡(luò)的星間鏈路的變化情況,這種變化是在時(shí)間維度上的。為了將天基網(wǎng)絡(luò)的差異性進(jìn)行突出顯示,提出一種分階段的動(dòng)畫轉(zhuǎn)換策略;同時(shí)為保證拓?fù)浣Y(jié)構(gòu)的穩(wěn)定性提出一種動(dòng)畫布局穩(wěn)定性策略。
根據(jù)文章建立的時(shí)空圖模型,將空間變化事件作為動(dòng)畫布局轉(zhuǎn)換的關(guān)鍵幀,簡化了天基網(wǎng)絡(luò)的時(shí)空圖模型的時(shí)間序列,同時(shí)將連續(xù)時(shí)間序列劃分為間斷的區(qū)間,在動(dòng)畫過程中體現(xiàn)為穩(wěn)定和過渡兩個(gè)狀態(tài):
1)穩(wěn)定狀態(tài):天基網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)更新完畢,網(wǎng)絡(luò)的邊不再發(fā)生變化,此時(shí)進(jìn)行天基網(wǎng)絡(luò)拓?fù)洳季?,并根?jù)分階段動(dòng)畫轉(zhuǎn)換布局算法使布局趨于穩(wěn)定。
2)過渡狀態(tài):G(ti)分階段動(dòng)畫轉(zhuǎn)換算法根據(jù)空間變化事件,更新天基網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的布局,此時(shí)主要完成天基網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的更新。
分階段的動(dòng)畫轉(zhuǎn)換策略通過分階段的顯示邊的變化過程,實(shí)現(xiàn)網(wǎng)絡(luò)差異化的突出顯示。因此,分階段動(dòng)畫轉(zhuǎn)換的核心需要對邊的增加和刪除狀態(tài)實(shí)現(xiàn)平穩(wěn)過度,例如“淡入”增加邊,“淡出”減少邊,如圖3所示。通過引入四叉樹空間分解法[10],節(jié)省了排斥力的計(jì)算量[11]。為避免造成長時(shí)間布局,通過引入淬火算法來加速整體的布局效率。淬火算法的基本思想是利用溫度進(jìn)行布局控制,溫度為整體布局的控制函數(shù),當(dāng)溫度降到低于0或者迭代次數(shù)為0時(shí),布局結(jié)束。分階段動(dòng)畫轉(zhuǎn)換包括以下4個(gè)主要步驟:
第1步:上一時(shí)刻的平衡狀態(tài)。為ti時(shí)刻的網(wǎng)絡(luò)布局,通過動(dòng)畫轉(zhuǎn)換布局法的作用下的網(wǎng)絡(luò)節(jié)點(diǎn)受力達(dá)到平衡,得到上一時(shí)刻的布局G(ti-1),如圖3(a)所示;
第2步:刪除邊。受空間變化事件的影響,令Edis(ti)中的邊逐漸消失,生成過渡圖G′。通過將消失的邊e23∈Edis(ti)做淡出處理,布局圖完成平滑過渡,如圖3(b)所示。FR算法是實(shí)現(xiàn)網(wǎng)絡(luò)拓?fù)洳季肿畛S玫姆椒╗12]。根據(jù)快速多層次FR算法[13]和引力公式,設(shè)當(dāng)前溫度值為t,利用溫度對引力進(jìn)行約束,直至溫度降為0引力消失。因此,可以將淡出函數(shù)fdis(d)定義為
(2)
可見,由于溫度的降低,節(jié)點(diǎn)間的引力減小至0,在布局圖中邊e23已經(jīng)徹底消失。在布局過程中,節(jié)點(diǎn)2和節(jié)點(diǎn)3 的引力逐漸減弱,造成受力失衡,兩節(jié)點(diǎn)受斥力的影響而相互遠(yuǎn)離。
圖3 分階段的動(dòng)畫轉(zhuǎn)換模型
第3步:增加邊。受空間變化事件的影響,Eadd(ti)中的邊逐漸出現(xiàn),生成新的過渡圖G′,根據(jù)過渡實(shí)現(xiàn)G(ti-1)的更新。如圖3(c)所示,由于邊e24∈Eadd(ti)的出現(xiàn),天基網(wǎng)絡(luò)拓?fù)洳季蛛S之而變,進(jìn)行平滑過渡。
第4步:形成新的平衡狀態(tài)。布局圖完成平滑過渡,生成下一時(shí)刻ti的布局圖G(ti),如圖3(d)所示??梢詫⒌牒瘮?shù)fadd(d)定義為:
(3)
可見,由于溫度的降低,節(jié)點(diǎn)間的引力逐步增加,在布局圖中邊e24已經(jīng)“淡入”至圖中。在布局過程中,節(jié)點(diǎn)2和節(jié)點(diǎn)4的引力逐漸增強(qiáng),再次造成受力失衡,兩節(jié)點(diǎn)受引力的影響而相互靠近。
因此,以空間變化事件為基礎(chǔ),通過將引力函數(shù)變?yōu)榈龊瘮?shù)為fdis(d)和淡入函數(shù)為fadd(d)實(shí)現(xiàn)動(dòng)畫布局的過渡,以實(shí)現(xiàn)布局過度的平滑穩(wěn)定。
動(dòng)畫布局穩(wěn)定性策略的基本思想是在分階段動(dòng)畫轉(zhuǎn)換過程中約束時(shí)空圖演化過程中的節(jié)點(diǎn)移動(dòng)距離,以保證布局過程的穩(wěn)定性。假設(shè)L(ti-1)為ti-1時(shí)刻拓?fù)洳季諫(ti-1)的位置信息,動(dòng)畫布局穩(wěn)定性策略就是以L(ti-1)為基礎(chǔ),通過節(jié)點(diǎn)的穩(wěn)定度確定各節(jié)點(diǎn)的移動(dòng)范圍,根據(jù)移動(dòng)范圍確定下一時(shí)刻ti的拓?fù)洳季諫(ti)中各個(gè)節(jié)點(diǎn)的位置信息L(ti)。動(dòng)畫布局穩(wěn)定性策略具體步驟如下:
第1步,根據(jù)上一時(shí)刻拓?fù)洳季值奈恢眯畔(ti-1),對此時(shí)刻的拓?fù)洳季諫(ti)中的所有邊進(jìn)行遍歷,根據(jù)空間變化事件,對每個(gè)節(jié)點(diǎn)連接邊的變化情況進(jìn)行計(jì)算計(jì)算,得到節(jié)點(diǎn)穩(wěn)定度ξ(v,ti)。ξ={ξ(vi,ti)|vi∈V(ti)}表示拓?fù)洳季諫(ti)的穩(wěn)定度的集合。節(jié)點(diǎn)穩(wěn)定度的計(jì)算方法如下
首先,根據(jù)空間變化事件D(ti)對各節(jié)點(diǎn)連接邊的變化情況進(jìn)行統(tǒng)計(jì),邊的變化相當(dāng)于與節(jié)點(diǎn)相關(guān)的權(quán)值相應(yīng)的改變。假設(shè)變化的邊ejk∈ED(ti)對應(yīng)的兩個(gè)節(jié)點(diǎn)分別為vj與vk,下面對節(jié)點(diǎn)vj的權(quán)值變化Δwj情況進(jìn)行計(jì)算
(4)
圖4 動(dòng)畫布局穩(wěn)定策略示意圖
其次,wjk(ti)表示節(jié)點(diǎn)vj與vk在時(shí)間片G(ti)邊的權(quán)重。根據(jù)節(jié)點(diǎn)的權(quán)值變化Δwj計(jì)算節(jié)點(diǎn)vj確定穩(wěn)定度ξ(vj,ti),計(jì)算公式如下
(5)
ξ(vj,ti)是歸一化的數(shù)值,0≤ξ(vj,ti)≤1,max(Δwk)為空間變化事件中所有節(jié)點(diǎn)權(quán)重變化最大值。
第2步,依據(jù)節(jié)點(diǎn)穩(wěn)定度ξ(vj,ti),為每個(gè)節(jié)點(diǎn)vj∈V(ti)計(jì)算節(jié)點(diǎn)動(dòng)態(tài)邊界值。根據(jù)節(jié)點(diǎn)動(dòng)態(tài)邊界值對FR算法的節(jié)點(diǎn)位移進(jìn)行約束,生成具有穩(wěn)定性的天基網(wǎng)絡(luò)動(dòng)態(tài)拓?fù)洳季?。?jié)點(diǎn)動(dòng)態(tài)邊界值的計(jì)算方法如下:
(6)
美國的STK(Satellite Tool Kit)作為一款商用航天領(lǐng)域的可視化平臺(tái),是目前航天領(lǐng)域應(yīng)用最為廣泛的仿真和可視化工具,通過其強(qiáng)大的軌道計(jì)算功能可用于分析復(fù)雜的航空航天任務(wù)。
仿真選擇中軌衛(wèi)星和低軌衛(wèi)星雙層星座(MEO/LEO)[14]作為天基網(wǎng)絡(luò)架構(gòu)并建立通信鏈路[15],LEO星座有6個(gè)軌道面,每個(gè)軌道有8顆衛(wèi)星,MEO星座有2個(gè)軌道面,每個(gè)軌道面有4顆衛(wèi)星。利用SQL sever 2008和STK衛(wèi)星仿真軟件實(shí)現(xiàn)天基網(wǎng)絡(luò)拓?fù)溲莼^程的動(dòng)態(tài)展示。
1)啟動(dòng)網(wǎng)絡(luò)可視化布局
通過STK建模獲取到星座模型和星間鏈路數(shù)據(jù),選取任意時(shí)刻的數(shù)據(jù)建立時(shí)空圖模型,對時(shí)空圖模型進(jìn)行拓?fù)涮崛。玫轿雌胶獾某跏疾季?。再根?jù)動(dòng)畫布局穩(wěn)定性策略計(jì)算節(jié)點(diǎn)動(dòng)態(tài)邊界值。以算得的節(jié)點(diǎn)動(dòng)態(tài)邊界值對快速多層次FR算法的節(jié)點(diǎn)位移進(jìn)行約束,F(xiàn)R算法多次迭代后得到平衡的初始布局。
從開始初始布局到布局圖中各個(gè)節(jié)點(diǎn)受力平衡,對初始布局過程進(jìn)行分階段顯示如圖5所示。在算法開始運(yùn)行之前,所有節(jié)點(diǎn)均集中在圖布局的中心,如圖5(a)所示。在經(jīng)過8次迭代后,布局圖已經(jīng)展開,在10-20次后變化已經(jīng)趨于平穩(wěn),如圖5(b)所示;此時(shí)由于節(jié)點(diǎn)與節(jié)點(diǎn)間相距較近,互相之間主要受斥力的影響發(fā)生位移,主要表現(xiàn)為從中心迅速向外擴(kuò)張。隨著節(jié)點(diǎn)的逐步散開,間距逐漸變大,節(jié)點(diǎn)間的引力開始發(fā)揮作用,由于節(jié)點(diǎn)的位移受引力與斥力的合力共同影響,隨著布局逐漸完善節(jié)點(diǎn)的所受的合力逐漸減小,布局逐漸趨于平衡,如圖5(c)和圖5(d)所示。最終所有節(jié)點(diǎn)合力為零,布局結(jié)束,整體的變化過程十分平穩(wěn),達(dá)到初步穩(wěn)定和最終平衡的迭代次數(shù)較小。
圖5 初始布局過程進(jìn)行分階段顯示
圖6(a)~(d)展示了動(dòng)畫初始布局的全過程,20-40次時(shí)已經(jīng)初步穩(wěn)定,100次時(shí)可達(dá)到基本平衡。受迭代次數(shù)的影響,迭代次數(shù)越多布局效果越好高,體現(xiàn)了布局逐漸趨于完善的全部動(dòng)態(tài)流程。
圖6 初始布局移動(dòng)距離變化曲線
2)分階段的動(dòng)畫轉(zhuǎn)換布局
根據(jù)空間變化事件的影響,將動(dòng)畫布局分為刪除邊和增加邊兩個(gè)階段,當(dāng)動(dòng)畫布局處于刪除邊階段時(shí),由于邊的刪除將會(huì)使節(jié)點(diǎn)受力失衡,造成節(jié)點(diǎn)位移,直到節(jié)點(diǎn)受力重新達(dá)到平衡。圖7分別是刪除邊階段動(dòng)畫轉(zhuǎn)換布局動(dòng)畫轉(zhuǎn)換布局的仿真結(jié)果,增加邊階段與之類似??梢钥吹诫S著迭代的進(jìn)行,布局逐漸收斂,所有節(jié)點(diǎn)的位移量趨于平緩;布局經(jīng)過一段時(shí)間后,整體布局自動(dòng)進(jìn)行微調(diào),所有節(jié)點(diǎn)的位移量趨于穩(wěn)定。最終所有節(jié)點(diǎn)的受力達(dá)到平衡。
圖7 減少邊階段移動(dòng)距離變化圖
圖中記錄了刪除變過程中節(jié)點(diǎn)移動(dòng)距離的變化情況。在開始布局之前即圖7(a)點(diǎn),邊未發(fā)生變化,整體動(dòng)畫布局處于平衡狀態(tài),所有節(jié)點(diǎn)的移動(dòng)距離之和為零。當(dāng)邊逐漸消失時(shí)即圖7(b)點(diǎn),各個(gè)節(jié)點(diǎn)受力產(chǎn)生位移,此時(shí)受影響的節(jié)點(diǎn)較多,節(jié)點(diǎn)的位移量迅速發(fā)生變化;從圖7(b)到(c),布局逐漸收斂,所有節(jié)點(diǎn)的位移量趨于平緩;布局經(jīng)過一段時(shí)間后,即從圖7(c)到(d),整體布局自動(dòng)進(jìn)行微調(diào),所有節(jié)點(diǎn)的位移量趨于穩(wěn)定。最終所有節(jié)點(diǎn)的受力達(dá)到平衡,布局結(jié)束。動(dòng)畫布局過程中沒有出現(xiàn)劇烈波動(dòng),而是實(shí)現(xiàn)了整體動(dòng)畫的平穩(wěn)轉(zhuǎn)換,兼顧網(wǎng)絡(luò)結(jié)構(gòu)視圖的動(dòng)態(tài)穩(wěn)定性的同時(shí)實(shí)現(xiàn)了網(wǎng)絡(luò)拓?fù)渥兓闆r的突出展示。
針對天基網(wǎng)絡(luò)的動(dòng)態(tài)特征提出了一種基于空間變化事件的時(shí)空圖模型,再以此提出一種分階段的動(dòng)畫轉(zhuǎn)換策略;同時(shí)為保證拓?fù)浣Y(jié)構(gòu)的穩(wěn)定性提出一種動(dòng)畫布局穩(wěn)定性策略。從布局效果可以發(fā)現(xiàn),通過動(dòng)畫布局使天基網(wǎng)絡(luò)的空間動(dòng)態(tài)特性得以展現(xiàn),減弱了認(rèn)知難度;通過空間變化事件驅(qū)動(dòng)動(dòng)畫轉(zhuǎn)換,突出了天基網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)變化情況,利用分階段動(dòng)畫轉(zhuǎn)換策略以及動(dòng)畫布局穩(wěn)定策略保證了整體布局的穩(wěn)定性。本論文對天基網(wǎng)絡(luò)的研究僅考慮到了通信鏈路變化的情況,某個(gè)衛(wèi)星發(fā)生損壞等突發(fā)情況是下一階段研究的目標(biāo)。