RBS Time Synchronization Algorithm using Improved Least Square Method

閆安斌1,2　劉文怡1,2　石永亮1,2　關(guān)詠梅3

(中北大學電子測試技術(shù)國家重點試驗室1， 山西 太原　030051；

儀器科學與動態(tài)測試教育部重點試驗室2，山西 太原　030051；北京宇航系統(tǒng)工程研究所3,北京 100076)

改進型最小二乘法的RBS時間同步算法

RBS Time Synchronization Algorithm using Improved Least Square Method

閆安斌1,2劉文怡1,2石永亮1,2關(guān)詠梅3

(中北大學電子測試技術(shù)國家重點試驗室1， 山西 太原030051；

儀器科學與動態(tài)測試教育部重點試驗室2，山西 太原030051；北京宇航系統(tǒng)工程研究所3,北京 100076)

摘要：傳統(tǒng)最小二乘法對奇異點比較敏感。當樣本中存在奇異點時，不能客觀反映數(shù)據(jù)的真實分布情況；而傳統(tǒng)最小一乘法計算量太大，不能實時處理數(shù)據(jù)。針對經(jīng)典RBS算法在確定節(jié)點本地時鐘之間的相對時鐘漂移率和偏移值時，采用傳統(tǒng)最小二乘法會導致時鐘同步收斂速度太慢的問題，提出了一種改進型的最小二乘法。該算法能夠有效地識別和剔除樣本容量中的奇異點。經(jīng)試驗證明，該方法能夠改進節(jié)點之間的時鐘同步效果和收斂速度。

關(guān)鍵詞：最小二乘法最小一乘法RBS時間同步算法時鐘漂移時鐘偏移

Abstract：The traditional least square method is comparatively sensitive to singular points, when singular point exists in sample, real actual distribution of the data cannot be reflected; while the traditional least one multiplication method is too computationally intensive, data cannot be processed in real time. Aiming at classical reference-broadcast synchronization (RBS) algorithm, due todetermine the relative clock drift rate and offset value between local clock of the nodes by adopting traditional least square method may lead to the convergence speed is too slow, thus the improved least square method is proposed. With this method, the singular points in sample size can be effectively recognized and excluded. The tests prove that by using this method, clock synchronous effect and convergence speed between nodes can be greatly improved.

Keywords：Least square methodLeast one multiplication methodRBS time synchronization algorithmClock driftClock offset

0引言

分布式無線傳感網(wǎng)絡(wireless senor network,WSN)機制中，各節(jié)點之間本地時間的同步是網(wǎng)絡進行目標定位、跟蹤的首要條件，很多建立在這些分布式網(wǎng)絡之上的系統(tǒng)，都要求網(wǎng)絡中的節(jié)點之間能有一個統(tǒng)一的、準確的時鐘，保證正常的協(xié)調(diào)工作和運行。目前國內(nèi)外已經(jīng)出現(xiàn)了較多WSN時間同步算法，(reference broadcast synchronization，RBS)是較為典型且使用較為普遍的一種。本文結(jié)合設計節(jié)點的實際使用環(huán)境和節(jié)點使用時對時間同步精度的要求，綜合考慮各種因素，采用RBS時間同步算法作為節(jié)點時間同步的基本算法。

1RBS時間同步算法簡介

參考廣播同步算法RBS適用于分布式節(jié)點之間的時間同步，是目前分布式節(jié)點時間同步算法中使用最為普遍的一種。使用者往往根據(jù)自己所設計的節(jié)點及節(jié)點使用環(huán)境的不同，基于RBS算法融入不同的數(shù)學思想，衍生出了許多不同的算法。相比較而言，該算法較LTS、TPSN等算法協(xié)議，同步精度更高。

RBS算法利用了無線信號在鏈路層傳輸?shù)膹V播信道特性[4]，將分布式無線節(jié)點分為發(fā)送節(jié)點和接收節(jié)點兩種。發(fā)送節(jié)點發(fā)送一組廣播消息，周圍的接收節(jié)點監(jiān)測發(fā)送節(jié)點發(fā)出的廣播信號，當接收節(jié)點檢測到廣播信號之后，將接收時刻的時間戳存儲起來，各接收節(jié)點之間相互交換各自接收到的廣播消息的時間戳。各節(jié)點根據(jù)接收到的其他節(jié)點的一組時間戳信息，結(jié)合自身對應的一組時間戳信息，利用線性回歸法計算兩節(jié)點時鐘的相對時間漂移。通過計算，采用對時鐘晶振進行補償?shù)姆椒?，減小兩節(jié)點之間的時鐘漂移，多次修正使節(jié)點間的時鐘漂移值趨近于0。再利用兩節(jié)點相對應的兩組本地時間戳信息，計算兩節(jié)點每次同步之后的時間相對偏移，并求取這些數(shù)據(jù)的平均值。該平均值即作為兩節(jié)點之間的本地時間的時鐘偏移量，從而對其中一個節(jié)點的本地時間進行修正，以使兩節(jié)點的本地時間偏移量趨近于0。

經(jīng)過多次交換時間戳信息，可以得到多組相應的數(shù)據(jù)。利用上述計算方法對節(jié)點時間進行多次修正，最終實現(xiàn)接收節(jié)點之間的時間同步。同步示意圖如圖1所示。

圖1　RBS同步機制基本原理

RBS算法中，發(fā)送節(jié)點廣播一個信標分組，廣播域中的一組(此處示意為兩個)接收節(jié)點都能接收到這個分組，并記下信標到達時間戳。接收節(jié)點間相互交換接收時間，兩個接收時間的差值相當于兩個接收節(jié)點間的時間差值，其中一個節(jié)點可以根據(jù)這個時間差值更改它的本地時間，從而實現(xiàn)兩個節(jié)點的時間同步。區(qū)域中其他節(jié)點的同步與此類似。

2改進型最小二乘法

RBS時間同步算法要求能夠準確快速地利用采集得到的時間戳信息，擬合出關(guān)于時間的一次函數(shù)。根據(jù)得到的各節(jié)點的時間函數(shù)，確定節(jié)點間的時鐘漂移率和偏移值，從而實現(xiàn)時間同步。較常使用的線性擬合方法有最小一乘法和最小二乘法兩種。

2.1　傳統(tǒng)最小一乘法與最小二乘法

(1)

(2)

求解該函數(shù)中a與b的值，只需對式(2)中的a與b分別求偏導并令其為零，即令：

(3)

若其系數(shù)行列式不為零，則可求得唯一的a、b的值。該值即為所求的線性回歸的回歸系數(shù)[5]。

2.2　改進型最小二乘法

RBS同步算法中提出了對待同步節(jié)點的本地時鐘，進行時鐘漂移和時鐘偏移補償?shù)囊蟆＿@就需要采用線性擬合的運算方法對采樣得到的時間點集合進行擬合運算，從而得到節(jié)點本地時鐘相對于參照節(jié)點的時鐘漂移率和時鐘偏移值。近年來，圍繞線性擬合運算不斷有新的研究成果，其中較為典型的有最小一乘法和最小二乘法[1-2]。這兩種擬合運算對線性的擬合各有優(yōu)劣。最小一乘法數(shù)據(jù)運算量太大，對數(shù)據(jù)不能夠?qū)崟r處理，導致耗能多，與節(jié)點的節(jié)能設計思想相背離；最小二乘法數(shù)據(jù)運算量雖小，但個別奇異點對其計算結(jié)果的影響比較大[3]，而節(jié)點數(shù)據(jù)傳輸中難免出現(xiàn)奇異點，故本文采用改進型的最小二乘法計算節(jié)點的時鐘斜率和時鐘偏移量，提高節(jié)點時鐘同步的收斂速度。

選手參賽類節(jié)目或活動中，在最終評委打分的環(huán)節(jié)，常?？梢月牭街鞒秩酥v：去掉一個最高分，去掉一個最低分。為什么需要去掉最高分和最低分，就是為了減小最高分和最低分對選手成績的影響。在這不妨認為最高分和最低分就是樣本容量中的奇異點。參照這種思路，在使用RBS同步算法進行節(jié)點同步時，樣本容量中難免會有奇異點的存在。

鑒于最小一乘法計算量太大，對數(shù)據(jù)不能實時處理，節(jié)點耗能也不滿足節(jié)能的設計思想；最小二乘法對奇異點敏感度太高，當有奇異點存在時，不能客觀反映真實情況。綜合考慮，提出了一種改進型的最小二乘法。本次改進型最小二乘法的算法示意圖如圖2所示。

圖2　改進型最小二乘法算法流程圖

圖2中，判斷采集樣本中的采樣點是否為奇異點，是通過計算該點與其相鄰的下一個采樣點的差值，并判斷這個差值是否為負數(shù)。若為負數(shù)，則認為該點為奇異點；否則，將不是奇異點。

由于本次最小二乘線性擬合的使用環(huán)境為RBS算法的時間同步，時間是不可逆的，故在本次算法改進中只需判斷下一個節(jié)點的數(shù)據(jù)是否大于上一個節(jié)點的數(shù)據(jù)即可。經(jīng)大量試驗證明，上述判斷準則對該算法中的奇異點的去除效果很明顯，且誤判率很低。該改進型最小二乘算法對含有奇異點的樣本容量的直線擬合效果很好，能夠真實地反映這些數(shù)據(jù)樣本的真實情況。

3RBS誤差分析

全面而準確地分析傳感節(jié)點之間時間同步誤差產(chǎn)生因素，是正確使用RBS[7]同步算法的前提。根據(jù)RBS同步示意圖，結(jié)合其他同步協(xié)議，不難看出利用RBS同步，接收節(jié)點不需要與發(fā)送節(jié)點同步，其忽略了發(fā)送節(jié)點發(fā)送數(shù)據(jù)產(chǎn)生的發(fā)送延時誤差和發(fā)送報文形成的延時誤差。下面是引起RBS同步誤差的主要因素。

① 晶振頻率引起的誤差：晶振的振蕩頻率與其形狀、材料、切割方向等密切相關(guān)，雖然根據(jù)目前的技術(shù)，晶振的幾何尺寸可以做到很精密，但晶振的振蕩頻率尚不能實現(xiàn)完全相等，仍存在一定的頻率偏差。

② 信標分組在介質(zhì)中傳播產(chǎn)生時間誤差：信標分組為無線電磁波信號，該信號在空氣中傳播極易受外界的影響，傳播過程中所用的傳播時間不確定；其次，該無線傳感器網(wǎng)絡節(jié)點是隨機地使用播撒方式散布在監(jiān)測區(qū)域中，所以每個接收節(jié)點距離發(fā)送節(jié)點的距離為不確定的值，這兩者使得信標分組在介質(zhì)中傳播時間的不確定性增大，直接影響節(jié)點時間同步的精度。

③ 接收節(jié)點數(shù)據(jù)處理延時誤差：由于節(jié)點要求體積盡量小，其自身攜帶的能量有限，所以節(jié)點的數(shù)據(jù)處理能力有限，在接收到信息的時候，難免會由于各種因素導致節(jié)點的反應時間不同而產(chǎn)生誤差。

4試驗仿真

采用OMNET++模擬無線傳感網(wǎng)絡節(jié)點之間的時間同步，同步方式采用RBS方式，模擬節(jié)點之間每間隔5 ms同步一次，并在此次同步中強加一次同步錯誤，生成一個奇異點。本次模擬同步10次，相關(guān)數(shù)據(jù)如表1所示。

表1　時間采樣數(shù)據(jù)容量

表1中,給定節(jié)點A和B各一個初始值，值的大小不定且不等，利用Matlab,對上述數(shù)據(jù)分別使用最小一乘法、最小二乘法和本文中提出的改進型最小二乘法進行線性擬合，擬合后的結(jié)果如圖3所示。

圖3　Matlab仿真RBS同步示意圖

從圖3可以看出，利用最小一乘法和改進型最小二乘法擬合出的直線相接近，能夠比較真實地反映出樣本點分布的真實情況。而最小二乘法因為奇異點的存在，擬合出的直線與最小一乘法和改進型最小二乘法擬合出的直線相偏離，不能客觀地反映出樣本點分布的真實情況。圖4是節(jié)點A與B分別根據(jù)最小二乘法和改進型最小二乘法擬合出的直線，經(jīng)一次同步后的兩節(jié)點本地時鐘模型示意圖。

圖4　一次同步后的節(jié)點之間的本地時鐘模型

從圖4可以很直觀地看出，當有奇異點存在時，采用最小二乘法擬合出的直線，對時鐘進行漂移和偏移補償?shù)男Ч懿幻黠@，甚至使得補償出現(xiàn)偏差；采用改進型的最小二乘法，補償后的效果較為明顯，節(jié)點之間的時間同步有很大的改觀。

5結(jié)束語

節(jié)點時間同步是無線傳感網(wǎng)絡的一項重要的支撐技術(shù)，不同的使用環(huán)境，需要選用不同的同步算法。根據(jù)本次設計的無線傳感網(wǎng)絡的使用環(huán)境，綜合考慮后，選擇使用RBS時間同步算法，但由于經(jīng)典RBS算法中對節(jié)點本地時間的線性擬合，采用傳統(tǒng)最小二乘法，而傳統(tǒng)最小二乘法對奇異點太敏感，使得同步效果不太明顯，故本文提出了一種改進型的最小二乘法。該方法能有效地判定并去除奇異點，對時鐘同步的收斂速度有了很明顯的改觀。

參考文獻

[1] 李雄軍.幾種線性回歸方法的比較[J].計量技術(shù)，2005(8)：52-54.

[2] 李仲來.最小一乘法介紹[J].數(shù)學通報，1992(2)：42-45.

[3] 王文平.從算術(shù)平均數(shù)談最小一乘法與最小二乘法的區(qū)別[J].武漢船舶職業(yè)技術(shù)學院學報，2009(6)：40-41.

[4] 王汝傳，孫力娟.無線傳感器網(wǎng)絡技術(shù)及其應用[M]．北京：人民郵電出版社，2011:168-169.

[5] 張旭峰，王志斌，王秉仁.大學物理試驗[M].北京：機械工業(yè)出版社，2010.

[6] 王文峰.基于LINGO的最小一乘線性回歸的參數(shù)估計[J].貴州財經(jīng)學院學報，2006(6):106-108.

[7] Zhen Chengfang,Liu Wenyi,Hou Yulong.An accurate on-demand reference broadcast synchronization protocol for wireless sensor network[J].Sensor & Transducers,2013,154(7):42-50.

中圖分類號：TN92;TH89

文獻標志碼：A

DOI:10.16086/j.cnki.issn1000-0380.201507003

修改稿收到日期：2014-08-27。

第一作者閆安斌(1989-)，男，現(xiàn)為中北大學電子與通信工程專業(yè)在讀碩士研究生；主要從事聲定位無線傳感網(wǎng)絡的研究。