改進(jìn)型最小二乘法的RBS時間同步算法

RBS Time Synchronization Algorithm using Improved Least Square Method

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

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

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

改進(jìn)型最小二乘法的RBS時間同步算法

RBS Time Synchronization Algorithm using Improved Least Square Method

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

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

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

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

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

1RBS時間同步算法簡介

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

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

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

圖1　RBS同步機(jī)制基本原理

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

2改進(jìn)型最小二乘法

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

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

(1)

(2)

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

(3)

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

2.2　改進(jìn)型最小二乘法

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

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

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

圖2　改進(jìn)型最小二乘法算法流程圖

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

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

3RBS誤差分析

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

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

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

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

4試驗(yàn)仿真

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

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

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

圖3　Matlab仿真RBS同步示意圖

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

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

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

5結(jié)束語

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

參考文獻(xiàn)

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

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

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

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

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

[6] 王文峰.基于LINGO的最小一乘線性回歸的參數(shù)估計(jì)[J].貴州財經(jīng)學(xué)院學(xué)報，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

文獻(xiàn)標(biāo)志碼：A

DOI:10.16086/j.cnki.issn1000-0380.201507003

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

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