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

馮 丹，江耿豐，劉 波，衣學(xué)慧，劉超偉

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

?

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

馮 丹，江耿豐，劉 波，衣學(xué)慧，劉超偉

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

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

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

0 引 言

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

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

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

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

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

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

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

1 同步算法

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

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

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

N=4的全連接架構(gòu)示意如圖1所示：

圖1 N=4網(wǎng)絡(luò)連接架構(gòu)Fig.1 Net connection of N=4

系統(tǒng)設(shè)置如下：

(1)設(shè)系統(tǒng)內(nèi)存在單機數(shù)目為N，N為不小于4的整數(shù)；

(2)設(shè)置系統(tǒng)內(nèi)最多數(shù)目為M的單機出現(xiàn)故障，其中N≥4M；

(3)系統(tǒng)時間設(shè)為t；

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

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

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

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

1.1 初始同步

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

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

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

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

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

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

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

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

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

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

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

1.2 同步鎖定

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

(1)同步信息的廣播

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

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

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

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

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

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

軟件接收方面：軟件通過幀頭幀尾和校驗碼判斷信息有效性，接收同步串口傳輸?shù)耐酱aQ1,Q2,…,QN并存儲.

(3)本地校時

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

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

(1)

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

(2)

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

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

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

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

ΔT=θ+ε+ρT

(3)

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

2ΔT誤差內(nèi)，即

(4)

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

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

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

(6)

按照修正公式，修正后的結(jié)果

(7)

(9)

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

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

(10)

(11)

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

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

(12)

1.3 同步搜索

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

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

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

(2)同步搜索跟蹤

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

2 系統(tǒng)仿真

對上述算法進行仿真.參數(shù)設(shè)置如下：

a)N=4M

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

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

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

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

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

圖4 系統(tǒng)單機數(shù)目-同步精度仿真圖Fig.4 Relationship between the amount of computer and the synchronization precision

3 結(jié) 論

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

[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

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

2015-03-17

V446

A

1674-1579(2015)06-0058-05

10.3969/j.issn.1674-1579.2015.06.011

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