梯度下降算法在時間同步中的優(yōu)化
2018-10-17 11:25:18劉云，肖雪
西北大學(xué)學(xué)報(自然科學(xué)版) 2018年5期
劉 云，肖 雪
(昆明理工大學(xué) 信息工程與自動化學(xué)院, 云南 昆明 650500)
無線傳感網(wǎng)已被廣泛應(yīng)用于地下隧道監(jiān)測系統(tǒng)中,但因隧道封閉空間的特點,在長距離范圍內(nèi)所部署的傳感器無法通過外部信號進(jìn)行聯(lián)系,而傳感器節(jié)點之間的時間同步對于實時分析和判定至關(guān)重要[1-2]。另因傳感器節(jié)點資源受限的特點,內(nèi)置硬件時鐘由于不穩(wěn)定的低成本晶體振蕩器而產(chǎn)生時鐘偏移,導(dǎo)致節(jié)點之間的同步丟失[3-7]。因此,每個傳感器節(jié)點從中收集時間信息并構(gòu)建網(wǎng)絡(luò)全局時間函數(shù)(即邏輯時鐘)[8-9],通過調(diào)整邏輯時鐘的偏移和頻率,使得任何時刻的誤差最小化。
Wang等人提出了基于Voronoi圖的泛洪廣播時間同步算法(FBTS,Flooding broadcast time synchronization algorithm)[10],該算法的基本同步思想是在發(fā)送者和接收者之間記錄具有時間戳的廣播消息,并且通過K均值方法將數(shù)據(jù)聚集在一起,然后使用線性回歸來消除數(shù)據(jù)偏離后的時鐘偏移正常的誤差范圍。Yildirim等人提出了基于比例積分(PI)控制器的分布式時間同步算法(PISync,Synchronization algorithm based upon a Proportional-Integral(PI) controller)[11],節(jié)點通過在測量的相對偏移量上應(yīng)用比例反饋(P)和積分反饋(I)補(bǔ)償節(jié)點接收的參考時間的時鐘偏移和時鐘速度差來實現(xiàn)節(jié)點時間同步。
本文提出一種同步時鐘的迭代方法,基于梯度下降法的多跳時間同步算法(GDTS,time synchronization algorithm based on the gradient descent),采用梯度下降算法[12]對誤差函數(shù)的步長進(jìn)行迭代更新,調(diào)整接收節(jié)點的邏輯時鐘頻率和偏移值,得到使誤差函數(shù)最小化的邏輯時鐘頻率和偏移比值的最優(yōu)估計值。仿真結(jié)果表明,與FBTS和PISync相比, GDTS可擴(kuò)展性良好,收斂速度更快,同步誤差更小。
1 系統(tǒng)模型
將傳感器節(jié)點隨機(jī)分布的地下封閉隧道抽象成一個基礎(chǔ)數(shù)學(xué)模型,假定WSN 是一個拓?fù)浣Y(jié)構(gòu)圖G=(V,E),頂點集合V={1，2，…,n}代表傳感器節(jié)點的標(biāo)識符,邊集合E=V×V表示這些節(jié)點之間的雙向通信鏈路,傳輸消息的任意節(jié)點u∈V,接收消息的節(jié)點v∈V,{u,v}∈E，鄰居節(jié)點用Nu表示[13-16]。
在任何時刻t>t0,任意節(jié)點u硬件時鐘表示為
(1)
其中，fu(σ)∈[f0-fmax,f0+fmax]，為硬件時鐘振蕩器頻率,f0表示標(biāo)稱頻率,±fmax表示頻率偏差的上下限。時鐘動態(tài)偏移表示為f(t)=f0+u(t),u(t)是[-fmax,fmax]中的均勻隨機(jī)變量[15]。
(2)
在無約束優(yōu)化問題中,目標(biāo)是最小化函數(shù)f(x),其中，f:Rn→R是可微分的凸函數(shù)。假設(shè)函數(shù)可解,因此存在最優(yōu)解x*。由于f是可微分的凸函數(shù),所以f(x*)=0。下降法產(chǎn)生一個序列xk+1=xk+αkΔxk,使得f(xk+1)
當(dāng)搜索方向被確定為負(fù)梯度Δx=-f(x)時,所得到的算法被稱為梯度下降算法[12]。設(shè)給定初始值x0,梯度下降法通過在負(fù)梯度-f(x)的方向上逐步地向下移動到較小的函數(shù)值,假定函數(shù)為凸函數(shù),最后算法收斂到局部最小值。圖1為梯度下降執(zhí)行3次迭代過程。
圖1 梯度下降算法執(zhí)行過程Fig.1 The execution of the gradient descent algorithm
2 GDTS算法分析
考慮兩個傳感器節(jié)點u和r的成對時間同步,其中，r是訪問實時時間t的參考節(jié)點。假設(shè)節(jié)點r以B秒為周期傳輸實時消息給接收節(jié)點u。令th=Bh(h=0,1,…),表示從節(jié)點r到節(jié)點u的消息包接收次數(shù),接收時鐘lr(th)=Bh+Th,其中Th表示傳輸延遲。在任何消息包接收時間th=Bh時,u相對于參考節(jié)點r的同步誤差計算為
eu(th)=lu(th)-lr(th)-Th=
lu(th)-Bh-Th。
(3)
(B+Th+1-Th)。
(4)
(5)
(6)
(7)
下面證明收斂性并計算穩(wěn)態(tài)誤差。
(8)
式(8)兩邊求期望得
E[x(h+1)]=
(9)
通過|A-λI|=0求矩陣A的特征值,即
解得
(10)
當(dāng)且僅當(dāng)|λ1,2|<1,矩陣A漸近穩(wěn)定,得到漸近收斂。通過不等式(11)選擇步長
(11)
得出系統(tǒng)收斂于漸近穩(wěn)定點。
(12)
因此
(13)
同理
(14)
式(14)表明同步時間最后實現(xiàn)穩(wěn)態(tài)誤差eu(∞)=0。
(15)
根據(jù)wh+1的定義和均勻隨機(jī)變量u(t)得
e(h+1)=
(16)
同理
(17)
令gh+1=Bf0+ωh+1，得
zh(1-2αBf0gh+1)-2αBf0gh+1+
同理
所以
(18)
由
{E[e(h+1)]}2=E[e(h+1)2]
得
var(e(∞))=
(19)
只要滿足不等式(11),就會形成收斂。然而,α值越小,漸近方差越小。另一方面,收斂時間與式(10)中特征值λ2的大小成反比。因此,α越小,λ2越大,收斂時間越長。
GDTS算法多跳時間同步代碼如下:
1) 一經(jīng)收到〈lv,seqv〉,seqv>sequ；
2) seqv←sequ；
3)eu←lu←lv；
4)lu←lv；
5) 更新αu；
7)hu=kB,k∈N；
8) 如果u=r，那么sequ←sequ+1；
9) 廣播〈lu,sequ〉。
步長α影響同步誤差和收斂速度,長的恒定步長雖然收斂速度快,但穩(wěn)態(tài)同步誤差較大。另一方面,選擇小的恒定步長,雖然穩(wěn)態(tài)同步誤差較小,但是收斂緩慢。當(dāng)考慮到無線傳感器網(wǎng)絡(luò)的環(huán)境動態(tài)時,修改文獻(xiàn)[11]中的自適應(yīng)算法,自適應(yīng)調(diào)整步長以實現(xiàn)快速收斂和較小穩(wěn)態(tài)誤差,步長表達(dá)式為
(20)
th是新同步信息的接收時間,e(th)是該時間的誤差導(dǎo)數(shù)。如果e(th)和前一輪誤差導(dǎo)數(shù)e(th-1)同號,即它們的方向相同,那么遠(yuǎn)離最優(yōu)值需要加快調(diào)整盡快達(dá)到如果e(th)和e(th-1)反號,在附近擺動,為了更接近最優(yōu)值,需要減慢調(diào)整。
3 仿真分析
為了驗證本文所提算法的性能，將所提GDTS算法與類似的常規(guī)算法FBTS和PISync在Matlab 7.0中進(jìn)行仿真分析,試驗中對算法的收斂速度、同步誤差及可擴(kuò)展性3個性能指標(biāo)進(jìn)行了分析。
圖2 頻率隨迭代增加變化圖Fig.2 The relation between logical clock frequency and iterative times
在多節(jié)點的線性拓?fù)浣Y(jié)構(gòu)環(huán)境中對最大瞬時全局同步誤差隨時間的變化性能進(jìn)行仿真分析,執(zhí)行2×104s,與FBTS算法和PISync算法對比,GDTS算法的收斂速度最快,同步誤差最小，如圖3所示。
圖3 瞬時誤差隨時間變化圖Fig.3 The relation between synchronization errors and time
為了評估GDTS算法的可擴(kuò)展性能,在不同的網(wǎng)絡(luò)直徑環(huán)境中將GDTS算與其他算法進(jìn)行同步誤差分析,每個網(wǎng)絡(luò)進(jìn)行10次仿真,每次仿真執(zhí)行20萬秒,最后將觀察到的偏差值取平均值，3種算法的全局偏移隨網(wǎng)絡(luò)直徑呈線性增長,但GDTS算法同步誤差最小,如圖4所示。
圖4 同步誤差隨網(wǎng)絡(luò)直徑變化圖Fig.4 The relation between synchronization errors and different network diameters
4 結(jié) 語
針對節(jié)點同步精度和收斂速度的問題,本文提出一種基于梯度下降法的多跳時間同步(GDTS)算法,通過采用梯度下降算法對誤差函數(shù)的步長進(jìn)行迭代更新,調(diào)整接收節(jié)點的邏輯時鐘頻率和偏移值,得到使誤差函數(shù)最小化的邏輯時鐘頻率和偏移比值的最優(yōu)估計值。仿真結(jié)果表明,對比FBTS和PISync算法, GDTS算法具有良好的可擴(kuò)展性且收斂速度更快,同步精度更高。下一步的研究可以將所提出的方法與無線傳感器網(wǎng)絡(luò)中的占空比MAC協(xié)議相結(jié)合,研究其對能量消耗的影響。
