電力協(xié)同仿真設計中三維模型點對點分層快速調度算法

黃 良，曾華榮，陳沛龍(貴州電力試驗研究院，貴陽 550002)

0 引 言

電力設備是一類大型復雜系統(tǒng)，因此電力協(xié)同仿真設計越來越普及，然而隨著仿真系統(tǒng)的要求越來越高，設備模型的復雜度與精度越來越高，分布式站點中的模型傳輸開始成為電力協(xié)同仿真設計系統(tǒng)的一個瓶頸，然而目前極少有研究涉及分布式站點中的三維模型的快速共享問題。

在工業(yè)領域當中，為了保證協(xié)同設計效率，提高三維模型的傳輸速率，很多CAD模型轉換為三維面片模型，并且 通過降低模型面片數(shù)來降低傳輸模型的數(shù)據(jù)量[1]， 這種方法雖然在一定程度上提高了三維模型的傳輸效率，然而轉換后的模型無法進行進一步編輯，而且模型的精度大大降低，嚴重影響了協(xié)同仿真設計的效果。為了提高模型的傳輸效率，多分辨率特征CAD模型作為更加有效的方法被用于三維模型共享[2,3]。多分辨率特征CAD模型是由Koo與Lee[4]最早提出的，即將特征模型按照其特征層次進行劃分，然后根據(jù)需要將不同層次的特征模型進行傳輸，這樣可以大大提高模型傳輸效率，同時也可以對模型敏感信息進行一定程度的保護。

在協(xié)同設計中，三維模型的共享與傳輸存在各種各樣的情況，不同的情況對應著特殊的需求，因此各種對應方法也被相應提出。在電力協(xié)同仿真設計中，如何正確而且快速的傳輸模型到指定站點以保證仿真實時性與效果是誠待解決的關鍵問題。由于三維模型數(shù)據(jù)間的約束關系(例如不同子模型間的依賴關系)，現(xiàn)有的網(wǎng)絡環(huán)境中數(shù)據(jù)快速路由方法并不能直接應用該問題[5]。因此本文提出了一種電力協(xié)同仿真設計中三維模型點對點分層快速調度算法，該方法通過對組成設備的各個子模型間按照其依賴關系進行層次劃分，當某站點對于某個三維模型提出請求后，系統(tǒng)將根據(jù)相應層次關系以及各個站點中保存的該三維模型子模型的情況進行最優(yōu)傳輸路徑規(guī)劃，使得該模型能夠在最短時間內進行分布式傳輸。

1 三維模型點對點分層快速調度算法

在電力協(xié)同仿真設計中，隨著設計過程的推移，很多站點都保存有一定量的局部三維模型，而且這些局部三維模型在一定程度存在重疊。因此，為了實現(xiàn)某站點對某局部三維模型的快速調度，如果能夠從最近站點獲取越多的子模型數(shù)據(jù)，則能夠越快的實現(xiàn)局部三維模型傳輸，然而由于不同子模型之間存在復雜依賴關系，因此傳輸路徑與傳輸站點必須進行最優(yōu)規(guī)劃。

1.1 三維模型點對點傳輸

圖1顯示了在電力協(xié)同仿真設計過程中，局部三維模型傳輸情況，即根據(jù)各個站點的不同需求，不同站點中保存有設備模型的不同局部三維模型。因此在此情況下，當某個站點對于設備模型的某個局部三維模型進行請求時，可以從該模型的初始生成站點獲取，也可以從不同的站點通過點對點方式獲取該局部三維模型的不同子模型，然后在本地站點進行重新組裝而成。當站點數(shù)越多，而且分布越遠的情況下，后一種方式就越能夠體現(xiàn)其優(yōu)越性。

如圖1所示，隨著協(xié)同仿真設計的進行，不同站點分別獲取了該模型不同局部三維模型。

1.2 三維模型的分布式傳輸

在協(xié)同仿真設計中，不同站點根據(jù)設計需求，會對三維模型的不同局部有需求。因此在設計過程中，不同的設計人員會根據(jù)需求訪問模型的不同區(qū)域。將模型按照其最小子模型進行表示，然后根據(jù)子模型間的依賴關系，生成該模型的多層次模型。當某站點提出需求時，根據(jù)其角色及負責任務，發(fā)生相關的子模型表示文件，這些子模型按照其層次關系自上而下進行傳輸，而在請求站點，根據(jù)這些子模型文件以及各個子模型間次結構自上而下進行重建與裝配，最終在本站的生成需要的局部三維模型。這樣的好處是傳輸?shù)氖亲幽Ｐ捅硎疚募?，而非模型本身，這些表示文件數(shù)據(jù)量將遠小于相應的面片模型，這樣會大大降低網(wǎng)絡傳輸數(shù)據(jù)量。

圖1 多分辨率模型數(shù)據(jù)流傳輸

1.2.1問題形式化分析

假設當前電力協(xié)同仿真設計環(huán)境中具有m個站點Peer={P1,P2,P3,…,Pm}，如圖2所示， 而且每個站點作為一個三維模型的傳輸站點。請求模型由n個子模型構成F={F1,F2, …,Fm}。P1是整個協(xié)同仿真設計任務的管理者，而且具有三維模型的完整數(shù)據(jù)以及模型處理的最高權限。而其他站點要么不具有任何三維模型數(shù)據(jù)或者只保存有局部三維模型。為了簡化起見，假設該協(xié)同仿真設計環(huán)境中各個站點的計算機計算能力相同，而不同站點的網(wǎng)絡帶寬根據(jù)具體情況有所不同，不同站點的網(wǎng)絡傳輸速度可以表示為S={S1,S2, …,Sm}，每個站點傳輸一個子單元的時間為T={t1,t2, …,tm}。網(wǎng)絡中任意兩個站點Pi與Pj之間，min(Si,Sj)越小表示兩站的間傳輸速度越高。表1表示一個具有5個站點的協(xié)同仿真設計環(huán)境參數(shù)，其網(wǎng)絡連接拓撲圖如圖2所示。整個三維模型是由11子模型分布式構成，如圖3所示。最優(yōu)的數(shù)據(jù)傳輸規(guī)劃能夠保證局部三維模型能夠快速的傳輸給目標站點，因此可以認為，具有最短傳輸時間的局部三維模型傳輸規(guī)劃即為最優(yōu)的傳輸規(guī)劃。

表1 協(xié)同環(huán)境參數(shù)值

圖2 網(wǎng)絡拓撲圖

圖3 模型結構

1.2.2傳輸路徑最優(yōu)規(guī)劃

為了實現(xiàn)三維模型的傳輸時間最短，本文提出一個結合戴克斯特拉算法與啟發(fā)式規(guī)則的傳輸路徑最優(yōu)規(guī)劃算法。戴克斯特拉算法用于計算最小生成樹(Minimal Spanning Tree，MST)。圖4顯示了上述5個站點協(xié)同仿真設計環(huán)境中的最小生成樹，該生成樹中P1為根節(jié)點，該站點提供了需要進行共享的三維模型數(shù)據(jù)。在MST，顯示了不同站點間的傳輸路徑，其中粗線條表示了最短傳輸路徑。在MST中，一個節(jié)點可能為根節(jié)點、葉子節(jié)點或者中間節(jié)點三種類型(如表2所示)，根據(jù)某節(jié)點的上下游節(jié)點數(shù)目，所有的節(jié)點狀態(tài)如表3所示。

圖4 MST(最小生成樹)

表2 節(jié)點類型表

表3 MST中的節(jié)點狀態(tài)表

在MST中，除了根節(jié)點，其他節(jié)點無論是哪種類型，都作為數(shù)據(jù)傳輸?shù)闹修D節(jié)點。而中轉任務即將數(shù)據(jù)從上游接收然后傳輸給下游節(jié)點。在傳輸過程中根節(jié)點同時向所有的下游節(jié)點傳輸數(shù)據(jù)；對于任何一個節(jié)點，一旦接收到數(shù)據(jù)，立即將數(shù)據(jù)轉發(fā)給下游節(jié)點；如果有多個下游節(jié)點存在，則數(shù)據(jù)將同時發(fā)送給所有下游節(jié)點。

1.3 三維模型的點對點分層優(yōu)化傳輸

對于模型請求站點而言，必須要將從各個站點傳輸來的模型文件數(shù)據(jù)進行重新創(chuàng)建與裝配。因此在協(xié)同仿真設計中，除了能夠實現(xiàn)三維模型的快速調度之外，還存在以下兩種情況。(1) 在進行數(shù)據(jù)傳輸過程中，由于某些原因，根節(jié)點中斷與網(wǎng)絡的連接，此時每個站點已經(jīng)接收到部分或者全部三維模型數(shù)據(jù)，當某個站點需要獲取某個局部三維模型時，可以立刻通過其他站點獲取。(2) 當中央服務器系統(tǒng)崩潰時，其數(shù)據(jù)可以通過其他站點的數(shù)據(jù)進行恢復。由于三維模型內子模型關系的復雜性，子模型從哪個站點接收，通過哪個路徑傳輸?shù)葐栴}成為關鍵問題。

1.3.1問題形式化分析

假設(不失一般性)所有站點的情況均相同。當某個需求站點請求某個局部三維模型時，不同的站點將根據(jù)本站點中保存的局部三維模型數(shù)據(jù)為該站點提供相應的局部子模型數(shù)據(jù)。表4給出了一個5站點系統(tǒng)中的模型傳輸速度的測試數(shù)據(jù)，假設該需求站點從其他站點請求一個完整模型(如圖3)。

表4 模型接收環(huán)境條件

局部三維模型接收算法同樣基于戴克斯特拉算法與啟發(fā)式規(guī)則，通過MST計算出每個站點與需求站點的數(shù)據(jù)傳輸時間，以及其對應路由。表5顯示了該5站點系統(tǒng)中的所有路由。該路由保證了任何站點到達目標需求站點所需要時間是最短的。

表5 MST路徑表(最小生成樹路徑表)

根據(jù)三維模型中子模型的依賴關系，可以生成相應層次模型，如圖5所示。為了保證模型傳輸時間最短，模型接收路徑必須遵循以下規(guī)則：① 為了保證模型的正確性，所有子模型的到達次序必須遵循三維模型的層次結構自上而下進行。② 對于每個子模型而言，每次選擇到達時間最短的路徑。③將同一站點中的多個傳輸任務合并為一個傳輸任務?；谏鲜鲆?guī)則，5站點系統(tǒng)中的局部模型接收參數(shù)如表6所示。最終的三維模型接收規(guī)劃，代碼如下：

-

-

-

--

--

--

--

--

--

--

--

表6 模型接收參數(shù)表

1.3.2局部三維模型接收算法

局部模型接收算法依賴樹見圖5。

圖5 局部模型依賴樹

3 結 語

本文針對電力協(xié)同仿真設計中，三維模型數(shù)據(jù)量過大的問題，以及子模型間存在復雜依賴關系的特殊性，提出了一種電力協(xié)同仿真設計中三維模型點對點分層快速調度算法，基于該算法，三維模型的傳輸不再是從某個源站點發(fā)往某個需求站點，而是根據(jù)系統(tǒng)中不同站點中保存的局部三維模型的情況，計算出最優(yōu)的模型傳輸路徑，并制定最優(yōu)的子模型接收規(guī)劃，在保證目標三維模型正確性的前提下實現(xiàn)三維模型的最短傳輸時間。

該方法有效地解決了電力協(xié)同仿真設計中模型數(shù)據(jù)傳輸速率低下以及效果不理想的問題，對實時仿真提供了有效保障。下一步研究目標為如何進一步加強子模型的并行傳輸，從而進一步提高數(shù)據(jù)傳輸率，為以后高精度電力設備模型傳輸?shù)膶崟r性提供技術支持。

□

[1] M Eck, T DeRose, T Duchamp, et al. Multi-resolution analysis of arbitrary meshes[J]. ACM SIGGRAPH, 1995:173-182.

[2] 鄒萬紅,陳志楊,潘 翔,等. 多分辨率層次點模型分片[J].計算機輔助設計與圖形學學報，2008,1(20):1-5.

[3] K C Kim, S B Yoo. Collaborative design by sharing multiple-level encryption files[J]. Concurrent Engineering, 2014,22(1):29-37.

[4] S H Lee, K Lee. Simultaneous and incremental feature based multi-resolution modeling with feature operations in part design[J]. Computer-Aided Design, 2012,44(5):457-483.

[5] 楊必勝，李清泉，龔健雅. 一種快速生成和傳輸多分辨率三維模型的穩(wěn)健算法[J].科學通報，2006,13(51):1 589-1 594.