一種空間飛行器控制系統(tǒng)軟件協(xié)同演化方法*

周 宇，沈怡颹，張 磊，張增安

(上海航天控制技術研究所·上?！?01109)

0 引 言

空間飛行器控制系統(tǒng)軟件屬于特殊領域軟件，同時也是定制型軟件，每個型號的控制系統(tǒng)軟件都需要根據(jù)型號的任務需求進行定制開發(fā)，因此控制系統(tǒng)軟件的研制工作與控制系統(tǒng)本身的研制工作是緊密結合在一起的，系統(tǒng)設計人員和軟件設計人員都處于協(xié)同研制的狀態(tài)下。特別是隨著軟件規(guī)模的擴大，軟件復用程度的提高，同一軟件中往往存在多個開發(fā)組開發(fā)的模塊同時存在的情況。而傳統(tǒng)的基于瀑布模型的軟件演化流程并不能很好地協(xié)調(diào)各模塊間的開發(fā)順序，不可避免地導致相關參與人員一擁而上，繼而出現(xiàn)資源浪費、管理混亂的問題。

當前對軟件的協(xié)同開發(fā)、協(xié)同演化進行的研究主要集中在對開源軟件的社區(qū)協(xié)同、異地協(xié)同領域[1-4]。此外在國內(nèi)，余敦輝等提出了基于眾包的軟件協(xié)同開發(fā)方法[5]，王懷民等提出名為Trustie的可信軟件協(xié)同開發(fā)環(huán)境[6]，陳洪龍等對面向服務對象的軟件演化進行了研究[7]。

另一方面，由于空間飛行器控制系統(tǒng)軟件的高可信度的要求以及其瀑布開發(fā)模型的固有特性[8]，導致在一個軟件開發(fā)階段中就需要達到一定的可信程度，而不能依賴多次迭代來解決軟件存在的缺陷。同時控制系統(tǒng)軟件的高復雜性也導致了參與人員多、模塊間的耦合度高的情況。因此，在空間飛行器控制系統(tǒng)軟件在對單一模塊或功能進行演化的過程中必須有效識別其影響域，對可能受影響的模塊、功能性能等都在一個迭代周期內(nèi)完成適應修改、驗證的工作，從而避免后續(xù)高昂的迭代周期，并保證軟件在任意開發(fā)過程時的可信程度。

為在空間飛行器控制系統(tǒng)軟件的演化過程中避免上述的人力資源浪費，同時保證軟件可信程度，就必然要求一種能協(xié)調(diào)各類演化活動有序開展，進而保證人員的有序調(diào)配的協(xié)同演化方法。圖算法中的拓撲排序方法已經(jīng)被廣泛應用于各領域的項目人員調(diào)度、管理領域[9-13]，因此，本文提出一種基于拓撲排序的軟件協(xié)同演化路徑確定方法，來實現(xiàn)對空間飛行器控制系統(tǒng)軟件的軟件演化過程進行有效組織。通過對演化路徑的有序化，來保證各演化活動的有序開展，一方面避免了各個演化活動的無序開展所可能導致的資源占用、返工浪費，另一方面，確保了任何演化活動所引入的軟件錯誤及缺陷能被立刻檢驗和修復。

1 協(xié)同演化的方案設計

1.1 軟件協(xié)同演化的整體架構

本方法是一種適用于空間飛行器控制系統(tǒng)軟件的協(xié)同演化方法，對軟件演化的協(xié)同主要表現(xiàn)在兩個方面，一是在演化過程中各個演化活動進行步驟的協(xié)同，另一方面是相應的軟件研制的參與方的工作流程進行協(xié)同。而這主要依托于如表1所示的軟件開發(fā)基本要素和要素間的關聯(lián)關系[14]。

表1 軟件演化基本關聯(lián)關系表

如圖1所示，軟件在其演化過程中，根據(jù)演化策略提煉出一個初始的演化活動，再基于各演化活動間的RS關系，得到演化過程的活動路徑。同時協(xié)調(diào)各相關參與的角色，最終得到可執(zhí)行的軟件演化過程。其中，軟件可信證據(jù)來源于軟件測試、應用中的數(shù)據(jù)，將其中一部分能標識軟件問題、缺陷的證據(jù)作為演化活動的依據(jù)。

圖1 協(xié)同演化過程圖

1.2 對空間飛行器控制系統(tǒng)軟件演化活動的分析

空間飛行器控制系統(tǒng)軟件的演化活動從類別來分，主要包含了對軟件需求、設計、編碼、測試等多種類型的活動。同時隨著當前軟件工程化程度的提高，軟件開發(fā)、測試工作針對的對象粒度逐漸達到了模塊級別。此時，軟件的演化活動間關系存在如下兩類情況。

(1)針對單一對象的軟件開發(fā)測試工作，由于領域特點，采用瀑布模型，因此其遷移關系首尾相接，演化路徑呈一條直線。

(2)在存在模塊間耦合等相互依賴的情況下，針對某一模塊的演化活動會導致依賴于它的其他模塊進行相應的演化。這種模塊間相互依賴的情況，可以通過模塊設計時定義模塊間RS關系來確定。如對模塊A進行設計更改會導致依賴模塊A的模塊B進行設計復查，若需要則進行適應性更改。

在同時考慮上述兩類演化活動關系時，可以發(fā)現(xiàn)，空間飛行器控制系統(tǒng)軟件的演化路徑并不一定是一條直線或是樹狀，由于模塊間耦合的情況多變，也可能出現(xiàn)回溯、交叉等現(xiàn)象。

在此能確定的只有存在一組節(jié)點，代表不同的演化活動，同時存在一組邊，連接兩節(jié)點，并存在方向，通過這種形式來描述演化活動間的相互關系。因此，演化路徑可以用有向圖的形式來進行表示。

1.3 對演化策略的建立

對軟件協(xié)同演化的策略一方面是建立一組策略集，基于一定的閾值、條件等判斷標準對可信證據(jù)進行篩查，確定不滿足判斷條件的可信證據(jù)，并提供指導性的演化目標，指示軟件所亟待進行的演化活動。此種方法自動化程度高，標準明確，僅通過一組“證據(jù)-條件-初始演化活動”策略集便可進行，但同時該方法存在適用范圍窄的問題，其僅適用軟件功能-模塊對應良好的情況，若功能模塊分割不合理或功能過于復雜，這種方法并不能很好地適應。另一方面，通過在證據(jù)采集等過程中增加人力判斷、分析等方法，則能有效地滿足對演化過程的指導，也與軟件工程化中軟件變更的問題分析流程相一致。

2 軟件協(xié)同演化的演化路徑構建

2.1 演化路徑的模型構建

如上述的軟件演化過程中，根據(jù)演化策略得到的是指向軟件的某一演化活動。依據(jù)1.2節(jié)中所敘述的各模塊的依賴影響關系，軟件的演化活動將從一個軟件模塊的演化活動作為入口出發(fā)，依次完成對依賴該演化活動的軟件其他演化活動，如對某一個模塊的需求設計更改，會引發(fā)對該模塊的測試和基于該模塊的其他功能模塊進行修改、驗證等演化活動，直到所有受影響的演化活動完成。

因此，本文中采用一種有向圖來描述這種軟件協(xié)同演化路徑。如圖2所示，圖中每一個節(jié)點定義為軟件的演化活動，每一條邊則用于連接存在依賴或影響的兩個演化活動，方向指向受影響的一方。由于本文主要關注于演化路徑的構建，因此定義所有邊的權重均一致。

圖2 對演化路徑的有向圖轉換

2.2 演化路徑圖的拓撲排序

為了演化過程的有序開展，有必要對各項演化活動的開展順序進行求解，確定各模塊對應演化活動的先后開展次序，進而才能協(xié)調(diào)項目組中各相關方的行動?；?.1節(jié)中利用有向圖定義的演化路徑圖，若假設在演化路徑圖中不存在環(huán)的情況，則演化活動的先后次序可以依靠對該有向圖進行拓撲排序得到，如圖3所示。常見的有向圖的拓撲排序方法包括Kahn算法[15]及深度優(yōu)先算法，在此基于對后續(xù)環(huán)處理的便利性，采用Kahn算法對演化路徑圖進行拓撲排序。

圖3 有向圖的拓撲排序

Kahn算法基于貪心思想，通過重復遍歷所有節(jié)點，將沒有入度的節(jié)點從圖中移除并加入FIFO中，最終實現(xiàn)對所有節(jié)點的拓撲排序，其具體偽代碼可如下所示。

在傳統(tǒng)邏輯中，“類比推理是根據(jù)兩個(或兩類)對象在一系列屬性上相同或相似，而且已知其中的對象還具有其他特定屬性，由此推出另一個對象也具有同樣的其他特定屬性的結論。[2]”在這個定義中，類比的對象可以是個別的事物，也可以是一類事物，還可以是兩種觀點或理論。這種對類比對象的描述是簡單的定性說明，缺乏細致的分析。類比所依據(jù)的是事物屬性方面的相似性，沒有進一步探討類比對象在結構上的相似性?？梢妵鴥?nèi)邏輯學領域對類比推理研究還相對薄弱，既缺乏深耕也較少遠拓，尤其是對人工智能中類比推理的研究成果關注不夠。

算法:Kahn算法輸入:依賴關系表中存儲的演化活動間的依賴關系,每條依賴關系中,左節(jié)點代表被依賴活動,右節(jié)點代表存在依賴的活動。輸出:排序FIFO中的演化活動的拓撲排序。1 FOREACH 依賴關系 IN 依賴關系表2 節(jié)點HASH表[右節(jié)點].入度 +=13 節(jié)點HASH表[左節(jié)點].出隊列. APPEND(右節(jié)點)4 WHILE 排序FIFO.長度 < 總節(jié)點數(shù)5 FOREACH 節(jié)點 IN 節(jié)點HASH6 IF 節(jié)點.入度=0 THEN7 排序FIFO.APPEND(節(jié)點)8 FOREACH 出節(jié)點 IN 節(jié)點.出隊列9 節(jié)點HASH表[出節(jié)點].入度 -=1

2.3 演化路徑圖的并行化

在2.2節(jié)中，針對不存在環(huán)的演化路徑圖給出了基于Kahn算法的拓撲排序實現(xiàn)演化路徑的構建。在Kahn 算法進行遍歷所有沒有入度的節(jié)點，此時作為節(jié)點的演化活動被加入排序隊列中。但由于在軟件協(xié)同演化過程中，同一次Kahn算法遍歷到的節(jié)點，其相互之間并沒有依賴順序，因此可以作為并行的演化活動進行。

圖4 拓撲排序的并行化

為實現(xiàn)Kahn算法對并行化的支持，在此修改Kahn算法中FIFO的數(shù)據(jù)結構，將其修改為一個桶數(shù)組。其中每一個桶指向存儲演化活動的鏈表，數(shù)據(jù)結構如圖5所示。

圖5 支持并行的拓撲排序數(shù)據(jù)結構示意圖

通過增加并行處理，保證了演化活動的緊湊性，如當多個模塊互相之間沒有依賴關系時，完全可以使其同步進行演化，避免了串行處理造成的效率降低。支持并行化的Kahn算法的偽代碼可以被修改為如下所示。

算法:支持并行化的Kahn算法輸入:依賴關系表中存儲的演化活動間的依賴關系,每條依賴關系中,左節(jié)點代表被依賴活動,右節(jié)點代表存在依賴的活動。輸出:桶數(shù)組中的二維的演化活動排序。

1 FOREACH 依賴關系 IN 依賴關系表2 節(jié)點HASH表[右節(jié)點].入度 +=13 節(jié)點HASH表[左節(jié)點].出隊列. APPEND(右節(jié)點)4 SET 桶指針 指向 桶數(shù)組的頭位置5 WHILE 排序FIFO.長度 < 總節(jié)點數(shù)6 FOREACH 節(jié)點 IN 節(jié)點HASH7 IF 節(jié)點.入度=0 THEN8 桶指針->APPEND(節(jié)點)9 FOREACH 出節(jié)點 IN 節(jié)點.出隊列10 節(jié)點HASH表[出節(jié)點].入度 -=111 桶指針+=1

2.4 演化路徑圖的環(huán)處理

在演化路徑圖中作為節(jié)點的演化活動其互相之間的依賴有可能會導致出現(xiàn)如圖6所示的依賴環(huán)，形成有向有環(huán)圖。此時，通常的拓撲排序并不能適用。

圖6 有向圖的環(huán)

但基于2.3節(jié)中所設計的數(shù)據(jù)結構，此處提出一種新的方法來將環(huán)轉化為一種并行化排序隊列。該方法如圖7所示。

圖7 支持環(huán)的拓撲排序策略

首先，通過考察是否存在沒有入度的節(jié)點，來判斷當前有向圖中是否形成環(huán)。若發(fā)現(xiàn)圖形成環(huán)后，則根據(jù)上一次遍歷時圖中最后被指向的節(jié)點，對其所有的入度的邊進行變形，轉換為指向一臨時新節(jié)點的邊。之后繼續(xù)進行Kahn算法遍歷。最后，將被指向節(jié)點與其生成的臨時節(jié)點都被加入同數(shù)組后，在這兩個節(jié)點間的所有桶內(nèi)增加該項演化活動。

通過這種新算法可以有效地描述演化過程中，演化活動互相存在依賴環(huán)的情況，通過協(xié)調(diào)某些演化活動同時進行，可以保證，任何軟件模塊在進行演化時，其依賴的演化活動都已經(jīng)進行完畢或是正處于進行過程中。增加環(huán)處理后的Kahn算法如下所示。

算法:增加環(huán)處理的Kahn算法輸入:依賴關系表中存儲的演化活動間的依賴關系,每條依賴關系中,左節(jié)點代表被依賴活動,右節(jié)點代表存在依賴的活動。輸出:桶數(shù)組中的二維的演化活動排序。1 FOREACH 依賴關系 IN 依賴關系表2 節(jié)點HASH表[右節(jié)點].入度 +=13 節(jié)點HASH表[右節(jié)點].入隊列.APPEND(左節(jié)點)4 節(jié)點HASH表[左節(jié)點].出隊列.APPEND(右節(jié)點)5 SET 桶指針 指向 桶數(shù)組的頭位置6 SET 初始節(jié)點FIFOA 為 隨機一節(jié)點7 WHILE 排序FIFO.長度 < 總節(jié)點數(shù)8 SET 初始節(jié)點FIFOB 為 空9 FOREACH 節(jié)點 IN 節(jié)點HASH 10 IF 節(jié)點.入度=0 THEN11 // 環(huán)入口節(jié)點從并行FIFO移出。12 IF 節(jié)點為帶?節(jié)點 THEN13 并行FIFO.REMOVE(節(jié)點)14 桶指針->APPEND(節(jié)點)15 初始節(jié)點FIFOB.APPEND(節(jié)點)16 FOREACH 出節(jié)點 IN 節(jié)點.出隊列17 節(jié)點HASH表[出節(jié)點].入度 -=118 IF 初始節(jié)點FIFOB=空 THEN // 檢測到環(huán)的存在。19 FOREACH 初始節(jié)點 IN 初始節(jié)點FIFOA20 FOREACH 入節(jié)點 IN 初始節(jié)點.入隊列21 IF 入節(jié)點.入度 !=0 THEN // 該節(jié)點仍在圖中存在22 // 將入節(jié)點.出隊列中的初始節(jié)點更改為帶?節(jié)點。23 入節(jié)點.出隊列.REPLACE(初始節(jié)點, 初始節(jié)點?) 24 初始節(jié)點.入度=025 并行FIFO.APPEND(初始節(jié)點)26 ELSE27 初始節(jié)點FIFOA 拷貝 初始節(jié)點FIFOB 的內(nèi)容28 // 向排序FIFO中增加并行進行的節(jié)點29 FOREACH 并行節(jié)點 IN 并行FIFO30 排序FIFO.APPEND(并行節(jié)點)31 桶指針+=1

2.5 演化路徑圖在協(xié)同演化過程的應用

通過對空間飛行器控制系統(tǒng)軟件的演化過程進行建立演化路徑圖后，可以得到其各項演化活動的進行次序，進而能確定相應的各個參與方的“入場”順序，從而使參與方的資源調(diào)配和計劃能有效開展。保證了演化活動的有序開展和緊湊進行。

如當其中所有模塊都由一個單一開發(fā)組進行開發(fā)時，在完成模塊A開發(fā)工作后分為兩組分別對模塊B、C進行開發(fā)，并在之后分為三組對D、E、F模塊進行開發(fā)，從而有效提升了軟件演化效率。而當各模塊由不同開發(fā)組進行開發(fā)時，其參與演化過程的時機也可以基于此進行調(diào)配，避免了項目演化過程出現(xiàn)空轉或等待的情況。

表2 范例軟件演化路徑表

3 結 論

通過對演化路徑的構建，建立了空間飛行器控制系統(tǒng)軟件的系統(tǒng)演化方法，特別是解決了演化活動并行進行的表示問題以及有向圖存在環(huán)的問題，有效保證了軟件開展有序過程的有序性。進而確保了軟件在進行演化活動時的可信程度，同時避免了演化活動無序導致的人力資源浪費，有效提高軟件演化的效率。