一種空間飛行器控制系統軟件協同演化方法*

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

(上海航天控制技術研究所·上海·201109)

0 引 言

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

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

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

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

1 協同演化的方案設計

1.1 軟件協同演化的整體架構

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

表1 軟件演化基本關聯關系表

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

圖1 協同演化過程圖

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

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

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

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

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

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

1.3 對演化策略的建立

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

2 軟件協同演化的演化路徑構建

2.1 演化路徑的模型構建

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

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

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

2.2 演化路徑圖的拓撲排序

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

圖3 有向圖的拓撲排序

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

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

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

2.3 演化路徑圖的并行化

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

圖4 拓撲排序的并行化

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

圖5 支持并行的拓撲排序數據結構示意圖

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

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

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

2.4 演化路徑圖的環處理

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

圖6 有向圖的環

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

圖7 支持環的拓撲排序策略

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

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

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

2.5 演化路徑圖在協同演化過程的應用

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

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

表2 范例軟件演化路徑表

3 結 論

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