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

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

?

一種星載計(jì)算機(jī)自穩(wěn)定容錯(cuò)時(shí)間同步算法*

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

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

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

自穩(wěn)定；容錯(cuò)；時(shí)間同步

0 引 言

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

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

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

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

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

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

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

1 同步算法

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

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

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

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)存在單機(jī)數(shù)目為N，N為不小于4的整數(shù)；

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

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

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

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

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

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

1.1 初始同步

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

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

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

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

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

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

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

(5)單機(jī)對(duì)2Ω時(shí)間以后的“初始同步信息碼”認(rèn)為無(wú)效，不作響應(yīng).

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

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

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

1.2 同步鎖定

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

(1)同步信息的廣播

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

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

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

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

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

硬件接收方面：?jiǎn)螜C(jī)N通過(guò)硬件鎖存有效同步串口的門控信號(hào)到來(lái)的準(zhǔn)確本地時(shí)間，設(shè)置單機(jī)1～N 在門控信號(hào)到來(lái)時(shí)本機(jī)計(jì)數(shù)得到的時(shí)間為Δ1,Δ2,…,ΔN.

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

(3)本地校時(shí)

本地校時(shí)分為硬件同步校時(shí)和軟件同步校時(shí)兩種.

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

(1)

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

(2)

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

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

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

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

ΔT=θ+ε+ρT

(3)

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

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

(4)

在下一時(shí)刻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個(gè)序列不一致，且：

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

(10)

(11)

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

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

(12)

1.3 同步搜索

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

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

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

(2)同步搜索跟蹤

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

2 系統(tǒng)仿真

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

a)N=4M

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

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

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

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

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

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

3 結(jié) 論

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

[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ù)研資助項(xiàng)目(513200704).

2015-03-17

V446

A

1674-1579(2015)06-0058-05

10.3969/j.issn.1674-1579.2015.06.011

馮 丹(1983—)，女，工程師，研究方向?yàn)楦呖尚湃蒎e(cuò)空間計(jì)算機(jī)；江耿豐(1982—)，男，工程師，研究方向?yàn)榭臻g綜合電子系統(tǒng)等；劉 波(1977—)，男，研究員，研究方向?yàn)樾禽d容錯(cuò)計(jì)算機(jī)；衣學(xué)慧(1978—)，男，高級(jí)工程師，研究方向?yàn)樾禽d容錯(cuò)計(jì)算機(jī)；劉超偉(1982—)，男，高級(jí)工程師，研究方向?yàn)樾禽d容錯(cuò)計(jì)算機(jī)。