基于有限狀態機的空間信息網絡故障自檢測算法

蔣　媛，李　寧，王發鵬，王　聰

(解放軍理工大學 通信工程學院， 江蘇 南京 210007)

?

基于有限狀態機的空間信息網絡故障自檢測算法

蔣媛，李寧，王發鵬，王聰

(解放軍理工大學 通信工程學院， 江蘇 南京 210007)

討論了空間信息網(SIN)未來發展趨勢并提出了一種新的故障自檢測方法。目前關于空間信息網絡的研究十分有限，尤其是故障檢測方面。針對空間信息網絡發展趨勢介紹了一種新的空間信息網絡體系結構并對該體系結構特點進行了詳細的分析，在此基礎上提出了一種基于有限狀態機的故障自檢測算法。該算法通過創建一個故障探測器使得各衛星節點之間可以通過信息交互完成故障檢測任務。通過故障檢測器，各狀態之間有條件的轉移最終得到檢測結果。每個衛星節點都參與檢測器的狀態轉移過程達到自檢測的目的。利用MATLAB仿真工具對算法進行仿真，結果顯示所提算法具有較好的性能。

自檢測；空間信息網絡；有限狀態機；故障檢測

0　引　言

空間信息網絡[1-2]極大地擴大了觀測范圍，通過衛星和深空平臺實現了不間斷的信息獲取[3]。與目前單個衛星觀測相比，空間信息網絡具有更好的信息探測和傳輸能力。一般來講，空間信息網絡是一個復雜的異構網絡，它以衛星網絡為骨干網囊括了衛星、飛行器、地面站以及各種具有空間通信能力的接入終端[4]。空間信息網仍然是一個比較新的概念，關于它的研究不多，尤其是故障診斷方面。與無線傳感器網絡不同的是，空間信息網因其具有較大的覆蓋范圍、靈活的組網方式、不受環境限制等特點[5]，其故障檢測更為困難。文獻[6]提出了一種新的基于包分組丟失的路由策略。路由維護策略通過交替發送高和低優先級的數據包區分丟包的原因。路由維護機制根據不同的原因來設計相應的方法。文獻[7]在空間信息網絡環境下提出了一種分布式的基于簇和容錯拓撲控制算法來構造一個更有效率和耐故障的拓撲。文獻[8]提出了一種基于簇的算法，該算法介紹了一種基于層次分析法(Analytic Hierarchy Process AHP)的決策模型來選擇簇頭,然后形成重疊的k跳的簇。動態的自我維護機制以節點的移動性和集群均衡為考量。除了簇的合并/分區處理, 關系管理和信息周期的自適應調整使用移動代理以招聘的方式遷移和復制簇頭節點的功能。

然而，隨著空間信息網絡的發展，網絡拓撲結構變得越來越復雜。2013年美國國家航空航天局NASA建立小型航天器技術項目[9](Small Spacecraft Technology Program SSTP)研究越過低軌衛星使用小型飛船完成任務。因此，除了已有的衛星以外未來將有更多的小型衛星加入到空間信息網絡的系統中。而隨著這些小型衛星的加入，現有的故障診斷算法已無法滿足服務需求。鑒于這個情況本文介紹了一種新的空間信息網的系統模型，并對該系統進行了具體的分析。在此基礎上，還提出了一種改進的適用于新模型下的故障檢測算法[10-11]。小型衛星一般在完成既定任務后即墜毀，在軌時間很短。因此對于網絡鏈路故障診斷算法而言極易造成錯誤的判斷。本文提出的算法中首先對所檢測的衛星節點進行在軌時間與設計運行時間的比較判斷。如果在軌時間已經超出設計的周期時間則認為所探測的衛星節點已不存在不判錯，反之則進入主算法。對于在運行周期內的衛星節點，我們設計故障探測器(fault detector)發動所有相關節點一起加入到檢測過程中。故障探測器可以將故障檢測過程轉化為狀態的轉移。每個衛星節點根據本地信息更新探測器的狀態并傳遞探測器的類型和新的狀態到下一個節點直至到達一個穩定的狀態。這里所謂的穩定狀態即為最終狀態，我們可以從最終狀態判斷出故障檢測結果。利用仿真工具MATLAB 2010對所提算法進行仿真，從仿真結果來看，本文所提算法具有較好的性能。

1　系統模型

圖1所示為空間信息網網絡結構圖。從圖可以明顯看出，空間信息網是一個分層的結構[12-13]，可以大致分為骨干網域、接入網域和用戶網域。其中骨干網域由高、中、低軌衛星組成是空間信息網絡系統的核心。骨干網域負責信息的采集、傳輸和簡單的信息處理。接入網域由小型航天器和飛行器組成，負責不同接入終端和業務流的接入。用戶網域由具有空間通信能力的用戶終端組成。與之前所提的空間信息網絡結構模型不同，該網絡模型最大的特點是加入了小型航天器。而隨著小型航天器的加入，空間信息網絡變得更為復雜多變，在原有的基礎上又有了新的特點。

圖1　空間信息網網絡結構

1.1小型航天器

NASA在2014年的一份題為“Small Spacecraft Technology State of the Art”的報告中對小型航天器技術領域目前的研究進展和發展前景進行了總結。從報告可以看出，未來小型航天器將成為研究熱點，而目前所得的成果也表示小型航天器在未來空間通信中將發揮重要作用。多數小型航天器的任務是搜集科學的數據并傳輸給地面研究人員。因此小型航天器的加入使得空間信息網絡的服務質量得到很大的提升。

1.2網絡特征

1.2.1復雜性

空間信息網[14]包括了從深空到地面的所有通信設備。其中不僅包含了這些通信設備還包括了它們所組成的通信系統，更不用說這些設備中還包括了所有的衛星，因此空間信息網的復雜性也是前所未有的。這些通信實體互相協作組成了一個有效的大規模的網絡系統。因為這些原因，與任何以往的網絡系統不同，空間信息網的復雜性可想而知。正是因為如此，空間信息網的故障診斷也比其他任何網絡系統更為復雜和困難。

1.2.2動態性

眾所周知，由于衛星和飛行器的存在空間信息網的網絡拓撲結構變化劇烈。節點位置隨著時間推移而移動，更有甚者，每個節點都按照自己的軌跡運行，軌跡之間還存在重疊部分。節點的移動性增加了網絡系統的動態性，這樣一個動態的拓撲結構又大大增加了空間信息網鏈路故障診斷的研究困難。衛星之間的鏈接也會隨著衛星位置移動消失或者重新出現。更糟糕的是，隨著小型航天器的加入，由于其工作周期較短，完成既定任務后即墜毀，導致網絡拓撲變化更為頻繁。針對這個特點，需要對故障檢測算法進行調整以適用于新的網絡環境。

1.2.3分層結構

從圖1可以很清楚地知道這是一個分層結構。不同層次的節點具有不同的功能和性質，不同的服務請求分配到不同的節點。因此空間信息網可以分成若干任務域，每個任務域之間可能遵循不同的網絡協議，任務域之間通過衛星節點進行通信。長通信距離，長時延和任意約定的網絡結構使得空間信息網的進展緩慢。未來小型飛行器的研究將成為趨勢。可想而知，空間信息網絡將愈加復雜多變。但是無論空間信息網絡變得多么復雜，有一點我們可以肯定的是它的分層結構基本不會改變。

2　故障自檢測算法

圖2所示為整個算法的流程圖。正如前面所提到的，本文所提算法主要關注于小型航天器短工作周期的問題上。假定節點A探測到它與B節點間的鏈路A-->B包重發率異常高。首先，需對B節點做出一個判斷，判斷它是否在其工作周期內。若它的實際工作時長已經超出設計周期則認為該節點已完成既定任務消失，不判錯返回“no error”，更新網絡拓撲。若B節點在其工作周期內則進入故障檢測算法。

圖2　故障自檢測算法流程

圖3為部分網絡拓撲圖，A向B發包，{Ci}表示可以與A和B通信的鄰居。當A探測到它與B之間的鏈路A-->B 的包重發率異常高，所以A創建一個探測器M，M= (E,S,S0,f,F)。其中E表示輸入信息，S表示所有狀態集，S0是初始狀態Start，f表示狀態轉移條件函數，F是所有可接受狀態集，即最終的Accept狀態集。圖4中所示，Si為狀態集S中的參數，每條弧線代表從一個狀態轉移到另一個可能的狀態，弧線上的注釋代表兩個狀態之間轉移的條件。注意，其中有些狀態如S3，S4等有自循環的條件。環形所示的狀態代表Accept狀態，從Accept狀態我們可以得到故障檢測的最終結果。

圖3　部分網絡拓撲圖

圖4　狀態轉移圖

以圖4中所示為例，A創建一個探測器處于初始狀態Start。在A創建的這個探測器中，Start狀態表示A發現它到B的鏈路存在故障。于是A向它的鄰居節點廣播目前的狀態和探測器的類型。兩種類型的節點可能收到A發出的信息，一種是B節點另一種是可以與它們通信的鄰居節點{Ci}。

根據B節點和鄰居節點{Ci}的本地信息可以進行狀態間有條件地轉移。如果B收到來自A的Start狀態，B根據本地信息檢查之前是否有收到來自A的相同的信息。由于記錄所有重復信息較為浪費資源，因此文中算法以B是否能夠收到來自A的信息作為檢測標準。如果B收到來自A的信息并返回一個反饋給A但是仍然收到來自A的相同的信息，意味著A能夠向B發包但是無法接收來自B的包。反之則表示B無法接收來自A的數據包。在圖4中分別用B-/->A和A-/->B來表示這兩種情況。根據B的信息Start狀態可以轉移到S1狀態或S2狀態。以文中圖4圖中虛線轉移線為例，B無法接收來自A的數據包所以B轉移到S2狀態。S2狀態根據鄰居節點{Ci}的信息進行狀態轉移。如果Ci能夠與B正常通信，表明是A-->B間的鏈路發生故障導致A與B間丟包率異常高。因此根據{Ci}的信息可以轉移到一個可接受狀態LA->B，這個狀態即表示A到B的鏈路發生故障。若Ci也無法與B正常通信，S2狀態轉移到S7狀態。S7狀態為一個具有自循環的狀態，當Ci-/->B時將不斷檢測直至檢測到一個Ci能夠與B通信，即存在Ci滿足Ci-->B則轉移到可接受狀態LA->B。若所有Ci都無法與B通信，則NUM轉移到BC狀態。BC狀態表示B節點很可能擁塞。這里我們設置一個狀態自循環的門限值，而由于門限值的存在算法可能存在誤差，但是若檢測所有鄰居節點{Ci}極大地增加了算法運行時間和復雜度。因此，如何正確地選取門限值和正確率的折衷也是我們要考慮的問題。

3　仿真結果及分析

在MATLAB2010環境下對本文提出的算法進行仿真。前面我們提到的，我們將對每個檢測節點先進行工作周期的判斷，因此每個節點結構設置為6個參數，即X= {LA,LB,T,t,RA,RB}。其中LA存儲該節點與A節點當前的鏈接關系，類似的LB存儲該節點與B節點當前的鏈接關系。T表示該節點設計周期，t表示該節點在軌時間。RA,RB分別表示該節點與A、B節點的拓撲關系。因此，可以開始仿真本文提出的算法。當t>T時，表示探測節點在軌時間已經超出設計時間，不判錯返回“no error”。反之則進入主算法。通過節點中LA,LB的信息可以獲得節點間鏈接關系即算法中的轉移條件，RA,RB可以獲得尋找{Ci}的信息。對算法進行仿真比較可以得出如下結果。

表1所示為進行門限選取仿真[15]時所需數據。首先需要知道門限的選取對正判率的結果是否會產生影響。這里的門限是指上文中提到的具有自循環的狀態在相應的轉移條件下需進行的自檢次數，即需要尋找多少個Ci才能合理地在正判率和算法復雜度之間尋求折衷。門限中包含越多Ci的可能狀態時，算法的正確率越高。每個門限在同意故障下運行故障檢測算法1 000次，所得結果如圖5所示。從圖可知，在355個節點的網絡規模下算法總體正判率較高達到90%以上，門限值越大正確率越高。當門限值為5時，正判率高達99%以上。當門限值為7時，算法正判率接近100%。

表1　門限選取仿真參數

圖5　正判率與門限

表2為網絡規模仿真數據。為了維持正確率和計算量的平衡，門限值設為5。圖6為仿真結果，可以明顯看出當網絡規模增加時正確率下降。節點數小于600時，正確率在95%以上，但是當網絡規模達到700個節點時降為81.2%。甚至當網絡規模達到1 000個節點時，正確率降到了73.6%。

表2　網絡規模仿真參數

圖6　正判率與網絡規模

圖7所示為不同網絡規模和門限值情況下正確率的曲線圖。由圖可知，正確率隨著網絡規模的增加而降低，隨著門限值的增加而增高。當網絡規模到達1 000個節點時，若門限值仍設為5正確率低于75%，而通過增加門限值的方法可以提高正確率。如圖，當門限值設為7時，正確率可以增加到80%以上。但是，同時增加了相應的計算量。如何自適應選取合適的門限值將是下一步需要解決的問題。

圖7　正判率與影響因子

4　結　語

本文介紹了一種新的空間信息網絡模型并對其進行了詳盡的分析。其次在該模型下提出了一種基于有限狀態機的故障自檢測算法。通過創建一個故障探測器使得各衛星節點之間可以通過信息交互完成故障檢測任務。從仿真結果來看，本文提出的算法在空間信息網絡環境下具有較好的性能。然而算法中門限值為固定值，在不同網絡規模下性能差異較大。因此，下一步可以針對如何根據網絡規模的變化自適應地設置門限值進行研究。

[1]DAI Kun and ZHU Chang-ming. A New Architecture Design of Space Information Networks[C].2012 Sixth International Conference on Internet Computing for Science and Engineering, Henan: IEEE, 2012:217-220.

[2]WAGN K, ZHAO Z W and YAO L. An Agile Reconfigurable Key Distribution Scheme in Space Information Network[C].2007 Second IEEE Conference on Industrial Electronics and Applications, Harbin: IEEE,2007:2742-2747.

[3]JIANG Chun-xiao, WANG Xue-xia, WANG Jian, et al. Security in Space Information Networks[P].Communications Magazine, IEEE,2015, 53(8): 82-88.

[4]REN Fang, FAN Jiu-lun. An Adaptive Distributed Certificate Management Scheme for Space Information Network[P].Information Security,IET,2013,7(4):318-326.

[5]萬鵬,王瑞軍,黃薇等.空間信息傳輸TCP擴展協議研究與性能分析[J].飛行器測控學報, 2010，29(03):11-16.

WAN Peng, WANG Rui-jun, HUANG Wei, et al. Analysis of the Performance of TCP and Its Extension Protocol for Space Communication[J].Journal of Spacecraft TT&C Technology,2010,29(03):11-16.

[6]LIU Jun, HAN Huan, GENG Rong, et al. Route Maintenance Strategy based on the Packet Lost Distinguish for Space Information Networks[C].2012 International Conference on Computer Science and Service System, Nanjing: IEEE, 2012:1063-1065.

[7]YE Ning, ZHU Zhi-liang, LIU Jun, et al. Distributed Cluster-based Fault-Tolerant Topology Control for Space Information Networks[C].2010 International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery, Huangshan: IEEE, 2010: 210-217.

[8]YE Ning, ZHU Zhi-liang, LIU Jun, et al. A Self-Maintenance Clustering Algorithm based on Decision Model for Space Information Networks[C].Proceedings of ICCTA 2009, Beijing:IEEE,2009:816-820.

[9]http://www.nasa.gov/sites/default/files/files/Small_Spacecraft_Technology_State_of_the_Art_2 014.pdf.

[10]LIU Ke-bin, MA Qiang, ZHAO Xi-bin, et al. Self-Diagnosis for Large-Scale Wireless Sensor Networks[C].IEEE INFOCOM 2011, Shanghai: IEEE, 2011:1539-1547.

[11]LIU Ke-bin, MA Qiang, GONG Wei, et al. Self-Diagnosis for Detecting System Failures in Large-Scale Wireless Sensor Networks[J].IEEE Transactions on Wireless Communications, 2014:13(10): 5535 -5545.

[12]Durresi A, Dash D, Anderson B L,et al. Routing of Real-Time Traffic in a Transformational Communications Architecture[C].2004 IEEE Aerospace Conference Proceedings 2004:2:1086-1104.

[13]Kimura K, Inagaki K, Double Layered Inclined Orbit Constellation for Advanced Satellite Communications Network[J]. IEICE Transaction on Communication, 1997:8(1):93-102.

[14]Fraire J A and Finochietto J M. Design Challenges in Contact Plans for Disruption-Tolerant Satellite Networks[J]. IEEE Communications Magazine, 2015:53(5):163-169.

[15]馬淑麗,趙建平. WSN中基于最佳指數的加權DV-Hop算法[J]. 通信技術, 2015, 48(10):1147-1151.

MA Shu-li, ZHAO Jian-ping. Weighted DV-Hop Algorithm based on Optimal Index in WSN [J]. Communications Technology, 2015，48(10): 1147-1151.

蔣媛(1991—)，女，碩士研究生，主要研究方向為空間信息網絡，故障診斷算法，壓縮感知；

李寧(1967—)，男，副教授，碩士生導師，主要研究方向為ad hoc網絡技術，移動通信；

王發鵬(1991—)，男，碩士研究生，主要研究方向為ad hoc網絡技術，車聯網，壓縮感知；

王聰(1975—)，男，博士，副教授，碩士生導師，主要研究方向為計算機網絡。

SIN Fault Self-Diagnosis Algorithm based on Finite-State Machine

JIANG Yuan, LI Ning, WANG Fa-peng, WANG Cong

(Institute of Communication Engineering,PLA University of Science and Technology,Nanjing Jiangsu 210003,China)

Future development trend of SIN (Space Information Network) is discussed, and a novel fault self-diagnosis method proposed.Nowadays limited research is focused on SIN,particularly in the field of fault diagnosis.In connection with the development tendency of SIN, a novel SIN architecture is introduced,and its characteristics also analyzed in detail. In light of this, a fault self-diagnosis algorithm based on finite-state machine is proposed. This algorithm,with a newly-designed fault detector,enables various satellites nodes to complete fault detection via information interaction. Through fault detectors, conditional transfer of between the states is done,and the detection result finally acquired. Each satellite would participate in state transition process of the detectors and complete the self-diagnosis. MATLAB simulation indicates that the mentioned algorithm enjoys fairly good performance.

self-diagnosis; SIN; finite-state machine; fault diagnosis

10.3969/j.issn.1002-0802.2016.03.016

2015-11-01；

2016-02-04Received date:2015-11-01；Revised date：2016-02-04

TP393

A

1002-0802(2016)03-0335-05