一種星載計算機自穩(wěn)定容錯時間同步算法*

馮 丹，江耿豐，劉 波，衣學慧，劉超偉

(北京控制工程研究所，北京 100190)

?

一種星載計算機自穩(wěn)定容錯時間同步算法*

馮 丹，江耿豐，劉 波，衣學慧，劉超偉

(北京控制工程研究所，北京 100190)

提出一種新的時間同步方法，將軟同步和硬同步結合，通過單機間的信息交互完成時間同步.單機之間通過初始化同步建立初始同步狀態(tài)，然后進入同步保持狀態(tài).當單機由于臨時故障失去同步后，可通過同步搜索算法自恢復與其他單機的同步.本算法可應用于多機熱備份體系結構的星載計算機的時間同步中，用于提高系統的自恢復能力.

自穩(wěn)定；容錯；時間同步

0 引 言

多機冗余熱備份是星載計算機通常采用的一種提高系統可靠度的方式.對于離散的冗余熱備份計算機，需要采用時間同步機制使各個離散單機之間保持時間同步.

自從1985年Lamport等[1]提出在拜占庭故障下保持時間同步的理論以來，時間同步一直是離散式分布系統的重要研究部分之一.時間同步可按照同步源和同步模式進行分類.

從同步源來說，分為外部公共同步源和無外部同步源系統內自同步兩種方法.公共同步源通過一個統一的外部時鐘公共源對各個單機進行時間同步，此方法可以簡化分布式系統內部的交互邏輯，但是對公共同步源的可靠度提出了很高的要求.公共時鐘源硬件設計復雜且不適用于規(guī)模較大的系統.無外部同步源系統內自同步通過系統內單機的互相聯系(硬件或軟件聯系)使系統內的單機時間在一定范圍內保持一致，此方法不受限于外部公共源，且算法靈活，可分別適用于全連接或不全連接網絡、大型網絡等，但其算法比較復雜.

從同步模式分類，時間同步主要包括硬件同步、軟件同步和混合同步3種[2].

硬件同步主要采用壓控振蕩器通過鎖相環(huán)完成互相同步[2].采用硬件時間同步的優(yōu)點在于系統具有較高的同步精度，缺點在于對網絡的連接性能和硬件鎖相環(huán)提出了較高的需求，增加了網絡硬件成本.

軟件同步主要通過系統內單機互相交換時間完成時間校正[2].時間校正算法主要包括：平均收斂算法、非平均收斂算法和連貫性算法等[3].其中，Lamport等[1]于1985年提出平均收斂算法，通過其他單機反饋的時間平均值校正本地時間；Lamport等[4]于1988年提出拋棄最大最小可能錯誤后取中值的算法.在此基礎上，Pfluegl等[5]在1995年采用滑動窗口法判斷取中值范圍，提高了系統容錯能力；Dolev等[6]在2004年討論了通過跳頻實現自建立同步算法.軟件同步的優(yōu)點在于系統靈活，硬件成本低，缺點在于由于時延和處理協議導致的同步精度低[7].目前在網絡分布系統中應用最為廣泛的是IEEE1588協議[8]，通過網絡中的主機廣播時間戳的方式同步其他從機，協議簡單且在對稱網絡中可屏蔽延時導致的誤差.

混合算法是在硬件算法和軟件算法的基礎上，在同步精度、網絡連接形式、硬件成本和算法復雜性之間互相取舍，以達到的折中效果.

1 同步算法

本文針對的研究對象為星載計算機，星載計算機經常采用熱備份多機的方式實現系統冗余，要求時間同步具有精度高、可靠性高和硬件資源開銷低的特點.

本文提出一種自穩(wěn)定容錯時間同步算法，基于軟硬件混合算法，通過單機之間的信息交互完成時間同步.該算法具有同步精度較高(可優(yōu)于us量級)、可靠性較高(可以容忍多重故障)和軟硬件消耗較低的特點，尤其適用于星載計算機的時間同步.此自穩(wěn)定容錯時間同步算法包括初始同步、同步鎖定和同步搜索3個部分.

設系統內單機數量為N，系統內最大可能出錯的單機數目為M(N≥4M，N和M為整數).則該方法建立于雙向傳輸時間相等的全連接網絡，可適用于系統內單機數量為N的容錯系統，具備可容忍最多數目為M的單機任意故障的容錯能力，具備在故障單機恢復后使其自主重新加入系統的能力，可靠性較高.該算法中各機保持地位平等互相通信，不依賴于主機廣播時間或外部公共脈沖，提高了系統可靠性，避免了主機或公共脈沖故障對系統時間的影響.

N=4的全連接架構示意如圖1所示：

圖1 N=4網絡連接架構Fig.1 Net connection of N=4

系統設置如下：

(1)設系統內存在單機數目為N，N為不小于4的整數；

(2)設置系統內最多數目為M的單機出現故障，其中N≥4M；

(3)系統時間設為t；

(4)t時刻離散化后對應單機N的本地時間為Tn(k)，k為正整數；

(5)由于采用了初始同步，為化簡公式，設置系統起始時間為0；

(6)單機N以周期T對外廣播初始同步信息CN和同步信息SN；

(7)各單機采用三線制同步串口完成全連接，包括門控、時鐘和數據.

1.1 初始同步

為了避免單機在初始運行時產生較大的時間回卷或跳變，需要單機在加電運行后建立初始同步.傳統的軟件同步算法大多建立在初始同步已經建立的基礎上.傳統算法多通過單機同時加電或者外部輸入的同步復位信號保持單機初始同步.

由于星載計算機多機常采用遙控指令依次加電的方式，且電源建立時間存在偏差，不能保證單機同時啟動.因此，本文設計了不依賴于外部輸入且能容忍一定加電啟動時間間隔(時間偏差小于Ω)的初始同步算法.

本算法設置了初始同步算法的有效時間窗口[0, 2Ω]，實際使用中Ω通常設置為秒量級.在初始同步時間窗口之內，通過多機之間相互廣播初始同步信息進行初始同步，算法如下：

(1)單機上電后在[0,Ω]時間內以周期T對外廣播初始同步信息碼CN；

(2)單機在[0, 2Ω]時間內對接收的“初始同步信息碼”進行有效性判斷，確認有效后認為本機仍處于初始信息同步狀態(tài)，對本地時間計數器進行復位；

(3)多機在[0, 2Ω]內將最后到來的“初始同步信息碼”作為啟動本地時間計數器的基準；

(4)如果單機在[0, 2Ω]時間內均未發(fā)現其他單機的“初始同步信息”，則以2Ω時間為基準啟動本地時間計數器；

(5)單機對2Ω時間以后的“初始同步信息碼”認為無效，不作響應.

初始同步流程如圖2所示.

圖2 初始同步流程Fig.2 Initializing synchronization

根據上述算法，多機均以有效時間[0,Ω]內最后啟動的單機的最后一次“初始同步信息碼”作為本地時間計數器的基準啟動計數器，可以滿足多機之間的初始時間同步.該初始同步算法可以不受系統中錯誤單機數目不大于M的約束，使任意數目正常啟動的單機保持初始同步，并且不受2Ω時間以后啟動單機的初始同步的影響.2Ω時間以后啟動的單機初始不能和系統保持同步，將通過后續(xù)的同步搜索與系統保持同步.

1.2 同步鎖定

同步鎖定是指初始同步建立或者同步搜索成功狀態(tài)下的同步保持行為，由硬件同步和軟件同步組成.其中硬件同步建立在硬件邊沿精確測定的基礎上，具有較高的同步精度.軟件同步建立在軟件協議同步的基礎上，可防止單機由于宇宙環(huán)境輻照的單粒子事件或復位所導致的時間跳變.在軟件同步和硬件同步結合的基礎上對精度和硬件資源進行折中，可滿足星載計算機對性能和硬件資源的需求.自穩(wěn)定容錯時間同步算法的軟硬件結合的同步鎖定算法，流程主要包括同步信息的廣播、同步信息的接收處理和本地校時3個方面.

(1)同步信息的廣播

本地時間的產生包括硬件生成的時間當量(周期為T)和軟件在時間當量的基礎上進行的時間計數K(K為正整數).

設置T為同步周期.在同步定時時刻TN=KT(K為正整數)來臨時，單機N對外廣播同步碼.同步碼包括幀頭、本地時間信息SN、校驗和幀尾等信息，用于軟件同步.對外廣播的三線制同步串口的門控信號起始邊沿與本單機TN時刻對齊，用于硬件同步.

(2)軟件同步和硬件同步的接收

同步信息的接收包括軟件同步的接收和硬件同步的帶容差接收.設置時間容差為±Y.

在具有容差的同步定時時刻[KT-Y，KT+Y]內，單機N接收包括自己在內的所有單機的同步串口S1-SN信息，[KT-Y，KT+Y]范圍外的廣播信息被認定為無效.

硬件接收方面：單機N通過硬件鎖存有效同步串口的門控信號到來的準確本地時間，設置單機1～N 在門控信號到來時本機計數得到的時間為Δ1,Δ2,…,ΔN.

軟件接收方面：軟件通過幀頭幀尾和校驗碼判斷信息有效性，接收同步串口傳輸的同步碼Q1,Q2,…,QN并存儲.

(3)本地校時

本地校時分為硬件同步校時和軟件同步校時兩種.

硬件同步校時通過(2)中計算的時間Δ1,Δ2,…,ΔN精確調整硬件的時間當量計數器.將 Δ1～ΔN進行大小排序，拋棄M個最大值和M個最小值，生成新序列σ1,σ2,…,σN-2M.求其平均值，并將本地時間修正.以p單機為例，則修正為：

(1)

考慮到系統全連接之間的最大路徑延遲為θ和單機硬件接收同步串口的硬件偏差為ε，單機得到的結果為：

(2)

當硬件計數器從T-Y跨越到T+Y時，產生計數當量脈沖，可保證硬件時間計數不會由于時間調整多產生或少產生當量脈沖，保證軟件計時的正確性.

軟件同步主要保證出現臨時故障的單機能夠進行修正軟件時間計數值K.因此，軟同步校時算法對同步碼Q1,Q2,…,QN進行比較.拋棄最多M錯誤的同步碼，通過類似的平均算法選舉出正確的軟件計算時間，如果本地時間與選舉時間不同，將本地時間修改為選舉時間.

各單機使用的晶振存在一定的精度偏差和時間漂移，設置漂移率最大偏差為ρ.

在單機具備初始同步的背景下，在T時間內，正確單機之間時間偏差小于ρT.設置時間容差為ΔT：

ΔT=θ+ε+ρT

(3)

因此，在k時刻，任意不出現故障的單機p和q(p、q均為整數，小于N)可保證時間差在

2ΔT誤差內，即

(4)

在下一時刻K+1，修正前的

|Tp(k+1)-Tq(k+1)|

=|Tp(k)-Tq(k)+(ρp-ρq)T|<4ΔT

(6)

按照修正公式，修正后的結果

(7)

(9)

由于系統最大容忍M重故障，因此序列σpi和σqi中最多有M個序列不一致，且：

|σpi-σqj|<4ΔT，i∈N，j∈N

(10)

(11)

即K+1時刻校正后的時間也能保持p和q單機時間差在2ΔT內.該算法可保證時間同步，系統最大時間偏差為：

2ΔT=2(θ+ε+ρT)

(12)

1.3 同步搜索

在自穩(wěn)定容錯時間同步算法的算法中，保持同步狀態(tài)的單機由于臨時故障(單粒子翻轉、單機復位等)脫離同步狀態(tài)后，可通過同步搜索與與其他單機重新建立同步，進入同步系統，使系統具備一定的自恢復能力.同步搜索算法包括同步狀態(tài)判斷和同步搜索跟蹤兩個狀態(tài).

(1)同步狀態(tài)判斷

單機通過[KT-Y，KT+Y]時間內收到其他單機有效時間信息的個數L判斷本單機是否與其他單機保持一致.如果在L≥N-M，則表示單機處于保持同步的狀態(tài)；如果L≤M，則表明單機處于失鎖狀態(tài).如果單機處于失鎖狀態(tài)，則通過同步跟蹤搜索重新建立本單機與其他單機的鎖定.

(2)同步搜索跟蹤

失鎖后的單機不再限定接收其他單機時間信息的時間窗口[KT-Y，KT+Y]，而改為在全時間范圍內觀測其他單機的時間信息.當發(fā)現有H(H>M)個單機的時間同步信息出現的時間差在2ΔT范圍內，則以這些單機的時間平均值校正本地時間，參照本地校時中的算法，將M1-MK按照多數選舉法則選出的時間碼修改本地時間，拋棄M個最大最小值后的平均值修正本地精確時間，完成同步搜索跟蹤.

2 系統仿真

對上述算法進行仿真.參數設置如下：

a)N=4M

b)ρ為隨機數，其中ρ最大為15×10-5

c)ε為絕對值小于200 ns的系統誤差

仿真不同同步周期條件下最大的時間偏差，如圖3所示，由仿真結果可知，在N≥4M條件下，均能滿足系統時間偏差在2ΔT內.同步周期越小系統時間偏差越小，考慮到軟硬件資源和時間精度，T通常取ms量級，ε<<ρT、δ<<ρT.

圖3 同步周期-時間偏差仿真圖Fig.3 Time difference with different synchronization period

仿真不同N和M進行設置，仿真得到算法系統同步精度如圖4所示.由仿真結果可知，M越小系統精度越好，在N≥4M條件下系統同步精度小于2ΔT.

圖4 系統單機數目-同步精度仿真圖Fig.4 Relationship between the amount of computer and the synchronization precision

3 結 論

本文提出了一種時間同步方法，通過單機之間的信息交互完成時間同步.單機之間通過初始化同步保持初始同步狀態(tài)，然后進入同步保持狀態(tài).當單機由于臨時故障失去同步后，可通過同步搜索算法恢復與其他單機的同步，一定程度上提高了系統的自恢復能力，可應用于星載計算機的時間同步中.

[1] Leslie L, MelliarS. Synchronizing clocks in the presence of faults[J]. Journal of the ACM,1985, 32(1): 52-78.

[2] Todd A A. A network element based fault tolerant processor[D]. Massachusetts Institute of Technology, 1988.

[3] Ramanathan P, Shin K G. Fault-tolerant clock synchronization in distributed systems[J]. Computer, 1990, 23(10): 33-44.

[4] Lundelius J, LynchN. A new fault-tolerant algorithm for clock synchronization[J]. Information and Computation,1988,77(1): 1-36.

[5] Pfluegl M J, Blough DM.A newandimprovedalgorithmforfault-tolerantclocksynchronization[J]. Journal of Parallel and Distributed Computing，1995, 27(1): 1-14.

[6] Dolev S, Welch JL.Self-stabilizing clock synchronization in the presence of Byzantine faults[J]. Journal of the ACM, 2004, 51(5): 780-799.

[7] Lenzen C,Locher T,Wattenhofer R. Tight bounds for clock synchronization[J]. Journal of the ACM, 2010, 57(2): 1-42.

[8] Ouellette M, Ji K, Liu S, Li H. Using IEEE 1588 and boundary clocks for clock synchronization in telecom networks[J]. IEEE Communications Magazine: Articles, News, and Events of Interest to Communications Engineers, 2011, 49(2): 164-171.

[9] John C S, Benjamin P K, James W C, Hasan B. Clock synchronization on the RAX spacecraft[J]. Acta Astronautica, 2014, 98(5-6): 111-119.

A Self-Stabilization Fault-Tolerant Time-SynchronizationAlgorithm for an On-Board Computer

FENG Dan, JIANG Gengfeng, LIU Bo, YI Xuehui, LIU Chaowei

(Beijing Institute of Control Engineering， Beijing 100190， China)

A new time-synchronization algorithm is presented, which combines software synchronization and hardware synchronization. Time synchronization is achieved via information interchange between two computers. With this algorithm, initial time synchronization is established among different stand-alone computers after initial synchronizing process. And then the systemmaintainsthe synchronized state. If one of the computers falls out of the synchronism due to temporary fault, it can autonomously synchronize with other computers with the algorithm. This algorithm is applicable for the time synchronization of multiple hot redundant on-board computers, and improvesthe self-recovery ability of the system.

self-stabilization； fault-tolerant； time synchronization

*總裝備部預研資助項目(513200704).

2015-03-17

V446

A

1674-1579(2015)06-0058-05

10.3969/j.issn.1674-1579.2015.06.011

馮 丹(1983—)，女，工程師，研究方向為高可信容錯空間計算機；江耿豐(1982—)，男，工程師，研究方向為空間綜合電子系統等；劉 波(1977—)，男，研究員，研究方向為星載容錯計算機；衣學慧(1978—)，男，高級工程師，研究方向為星載容錯計算機；劉超偉(1982—)，男，高級工程師，研究方向為星載容錯計算機。