面向煤礦井下WSN低功耗雙向時間同步算法研究與實現*

崔麗珍,員曼曼,李 璋,赫佳星

(內蒙古科技大學信息工程學院,內蒙古 包頭 014010)

?

面向煤礦井下WSN低功耗雙向時間同步算法研究與實現*

崔麗珍*,員曼曼,李 璋,赫佳星

(內蒙古科技大學信息工程學院,內蒙古 包頭 014010)

針對傳統時間同步算法通過交換較多數據包來獲取同步精度而導致能耗過大的現象,結合煤礦井下網絡結構的特殊性,在分析雙向成對同步機制和單向廣播同步機制基礎上,利用廣播傳輸特性將2種機制有效結合起來,提出一種基于簇狀結構的主被動式低功耗雙向時間同步算法。實驗表明,基于簇狀結構的主被動式同步方式可有效解決傳統雙向報文交互頻繁的問題,在誤差允許范圍內達到減少消息開銷和平衡整個網絡能量損耗的目的。

煤礦井下;時間同步;無線傳感器網絡;低功耗;分簇

我國是產煤大國,煤炭工業是關系國家經濟命脈的重要基礎產業,但由于煤礦井下環境惡劣,地質條件復雜多樣,隨著煤礦開采的不斷延深和開采強度的增大,礦難等災害還是屢屢發生[1],因此作為煤礦安全生產最重要保障之一的煤礦監控系統日益受到重視。

無線傳感器網絡WSN(Wireless Sensor Network)作為一種新興低功耗、低數據、低成本、短距離無線技術已成為物聯網應用中的關鍵。時間同步技術作為WSN支撐技術之一在煤礦井下的應用日益廣泛[2]。在WSN分布式系統中要完成數據融合、功率管理、傳輸調度、TDMA定時、測距定位等應用時,都需要保證網絡中節點時鐘同步。而煤礦巷道一般深處地下幾百米到幾十千米,導致無法收到地面上廣為應用的GPS(Global Positioning System)以及其他基礎時間服務信號,從而需要網絡本身可提供一定精度的時間同步服務。因此WSN時間同步技術在煤礦井下的應用受到較大關注。

目前,WSN時間同步技術已成為國內外學者研究的熱點之一[3],將現有WSN時間同步協議劃分為集中式算法和分布式算法兩類。

集中式同步算法包括:基于發送者的同步機制,典型算法有DMTS(Delay Measurement Time Synchronization)算法和FTSP(The Flooding Time Synchronization Protocol)算法;基于發送者-接受者的同步機制,典型算法有TPSN(Timing-sync Procol for Sensor Networks)算法;基于接受者-接受者的同步機制,典型算法有RBS(Referenced Broadcast Synchronization)算法。

分布式同步算法包括:利用觀察脈沖信號,通過調整脈沖信號發射間隔以達到與周圍節點保持同步的螢火蟲同步算法[4];利用隨機矩陣方程來解決同步問題的ATS(Average Time Sync)算法[5];通過利用鄰居節點信息的交互,使整個網絡達到同一狀態的一致性同步算法[6]。

集中式算法雖然不能夠適應網絡拓撲的變化,但算法收斂性強,同步精度高。因此本文采用集中式算法。通過對集中式算法協議的分析和研究得出:①利用無線傳輸廣播特性來降低同步能耗;②利用雙向報文交換來提高同步精度。

煤礦井下通信環境有巷道和工作面等區域劃分。巷道環境較為狹長而工作面環境面積較大且環境復雜多變[7],因此研究井下節點在不同環境中的部署情況,提出一種面向煤礦井下的低功耗雙向時間同步算法,使節點在保持較低能耗的同時保證同步精度,具有一定的科研意義和使用價值。

1 雙向時間同步算法

雙向時間同步算法TPSN[7](Timing-sync Protocol for Sensor Networks)是由加州大學網絡和嵌入式實驗室Saurabh Ganeriwal等人提出的。TPSN算法采用發送端-接收端同步SRS(Sender-Receiver Synchronization)模型,利用雙向報文交換實現兩節點間時間同步。

圖1 SRS時鐘同步模型

(1)

(2)

Ui

(3)

Vi

(4)

(5)

(6)

由式(5)、式(6)可知,當只進行一次信息交換時,TPSN時鐘相偏估計也是指數模型和高斯模型下的最大似然估計式,如式(7)、式(8)所示:

(7)

(8)

2 低功耗雙向時間同步CRTS算法

TPSN算法采用發送者-接受者同步機制,通過MAC層時間戳技術消除訪問時間帶來的同步誤差從而提高同步精度,但為保證兩節點間時鐘相偏小于某個門限值,需頻繁運用TPSN算法來進行報文的雙向交互[8]。在WSN中,數據通信是系統最重要的操作之一,但所需能量遠大于數據處理所需能量[9]。

因此本文針對煤礦井下WSN中節點在巷道和工作面的特殊分布情況,研究一種可適用于井下節點分布的時間同步算法CRTS。針對煤礦井下節點分布在巷道且需進行持續循環多跳時間同步的情況,構建基于TPSN算法的新型主動式時間同步多跳模型;針對煤礦井下工作面環境的節點,由于工作面是屬于較大范圍空間,人和機器等設備在工作面環境中進行作業,因此在井下工作面環境布設傳感器網絡是屬于密集型大范圍的傳感器網絡。針對分布在工作面的節點,算法分為網絡成簇階段和同步階段。在網絡成簇階段中,利用自適應分簇拓撲算法選舉簇頭以均衡網絡中節點所消耗的能量;在同步階段中,根據簇狀結構分為簇間同步和簇內同步。簇間同步采用本文提出的新型多跳模型進行主動式時間同步;簇內同步采用單向廣播機制與雙向報文交換相結合的算法進行被動式時間同步,在誤差允許范圍內對能耗方面進行進一步的研究與改進。

2.1 網絡成簇階段

針對井下工作面環境的特點,采用一種自適應的分簇拓撲算法。LEACH協議是比較成熟且常用的分簇路由協議[10],以選舉形式產生簇首,可均衡網絡中的能耗,是一種為無線傳感器網絡設計的低功耗路由協議。

①簇頭選舉。設置閾值T(n),每個節點產生一個0～1的隨機數,如果該數值小于閾值T(n),則該節點在本輪循環中成為簇頭。在本輪循環中當選過簇頭的節點會把閾值T(n)設置為0以避免該節點再次成為簇頭,而未當選簇頭的節點將以T(n)為概率當選。T(n)隨著當選過簇頭節點數目的增加而增大,同時節點產生小于T(n)隨機數的概率也增大,使節點當選簇頭的概率增加[11]。T(n)可表示為:

(9)

其中,P為一輪中簇頭在所有節點中所占百分比;r為所完成循環次數;rmod(1/P)為本輪循環中成為簇頭節點的個數;Gr為本輪循環中未成為簇頭節點的集合;n為網絡中節點數目。

節點當選簇頭以后,發布消息告知其他節點自己成為簇頭節點。

②子節點收集。簇頭節點確定后,需建立以時間基準節點為根的廣度優先生成樹拓撲結構。根據節點自身獲得級別與周圍同級別鄰居節點之間報文交互情況進行拓撲建立。

選取時間基準節點并設置其層次號為0,其余節點均為無窮大并由根節點廣播拓撲建立報文。若簇頭節點接到該報文,則設置自己層次號為1并由該簇頭節點繼續廣播拓撲建立報文,其他節點收到報文后將報文中的層次號提取出來加1作為自己的層次號;如果已有層次號且層次號比消息包中的層次號小,則將該節點的節點號加入到自己的下層鄰居節點列表中。重復這個過程直到所有節點都被賦予層次號,完成網絡拓撲結構的建立。

2.2 同步階段

2.2.1 主被動時間同步算法

①主動式同步。煤礦井下巷道部分狹長,節點采用鏈狀拓撲結構進行布放,在此基礎上建立新型多跳時間同步模型進行雙向報文交互。簇間時間同步過程采用如圖2所示的主動式時間同步算法。

節點N-1稱為節點N的時間源鄰居節點,節點N稱為節點N-1的時間目標鄰居節點。算法具體實現過程如圖3所示。

節點首先發送同步請求報文,被其所在簇的簇頭節點接收并回復同步應答報文,目標鄰居節點收到同步應答后計算它和時間源鄰居節點之間的時鐘偏差(注意:節點之前發送的同步請求報文和當前收到的同步應答報文構成一對雙向報文)并返回給時間源鄰居節點,此時的時鐘偏差如式(10)所示:

(10)

時間源鄰居節點收到時鐘偏差后,據此修改自己的時間以達到與目標鄰居節點之間的直接同步,并同時觸發向其時間源鄰居節點發送同步請求,最終使得在同步路徑上的所有節點均達到同步。

②被動式同步。對于煤礦井下工作面環境的節點,針對節點眾多且分布具有隨機性的特點,將廣播傳輸特性與雙向報文交換算法結合達到利用較低功耗同步較多節點的目的。在該階段,根節點從自己的下層鄰居節點列表中隨機選取一個子節點作為響應節點并廣播同步消息。單個節點廣播范圍內只有一個簇首節點執行雙向報文交互過程,其他節點通過監聽簇頭節點同步過程來進行被動同步。圖4為被動式時間同步算法模型的單跳示例。整個單跳網絡同步機制可看作是發送者-接受者和接受者-接受者的混合機制[12]。從能耗角度看,被動式時間同步算法在一個單跳網絡中傳輸的報文數為僅為3個。

圖3 主動式時間同步算法流程

圖4 被動式時間同步算法模型

節點O為時間基準節點,節點A,B,和C處于節點O的一跳范圍內并可與其進行同步,這里假設各節點之間都可進行直接通信。具體過程如下:

①同步請求

②同步應答

③同步數據收集

④同步校正

(11)

(12)

圖5 分簇網絡拓撲結構

將算法擴展至多跳,通過網絡成簇階段對網絡進行分簇,構建一個如圖5所示的分級分簇樹形拓撲結構[13]。每個節點及其子節點形成一個可直接進行單跳算法的連通區域。在該拓撲結構中,對于簇頭節點和應答節點之間進行主動式時間同步算法達到瞬時簇間同步;簇成員節點間利用被動式時間同步算法達到簇內同步,完成整個網絡節點的時間同步校正。

在實際應用中可根據網絡需求對節點進行部署,將大功率節點作為簇首進行分布從而覆蓋更大的通信范圍并減少簇首個數,對網絡中其他節點可實現更為有效的低功耗運行。

選用簇頭節點間進行主動式時間同步,其他簇內節點采用被動式監聽同步的方式,相對于傳統雙向報文算法可大大降低通信開銷,尤其是子節點數目越多時通信開銷越明顯[14],解決了對于大規模節點分布,逐個進行雙向報文交互耗能巨大的問題。

2.2.2 計算復雜度分析

主要從算法的低通信開銷來定性分析算法的計算復雜度。首先算法采用主被動式同步方式,根據井下環境來設定選取不同的同步算法。這相對于傳統的TPSN算法,減少通信開銷。其次,CRTS算法利用廣播傳輸特性,使得處于工作面的一些簇成員節點,只需通過報文監聽來獲取偏差達到與簇頭節點同步,而不必通過報文交換來計算偏差,這樣,就不需要全網每個節點通過計算偏差來保持同步,以此來減少某些節點不必要的能量開銷。因此,同步階段中CRTS算法相對于TPSN算法,在計算復雜度上具有優勢,在同步誤差允許的范圍內,減少了節點的通信開銷。

2.2.3 同步開銷分析

通過對算法的復雜度分析,CRTS算法在保持了雙向同步算法特征的基礎上大大減少了通信開銷,在每個同步周期中只需2n個同步報文交互,n為拓撲結構中非子節點數目。CRTS算法與其他同步算法在每個同步周期所需要的報文交互數如表1所示。m為除去參考節點外所需要同步節點的個數。

表1 不同算法同步報文開銷對比

由表1可知,以上算法在網路中報文交互數目隨節點數目的增加而增加,而CRTS算法由于采用被動監聽方式獲取偏差信息,因此通信開銷和計算復雜度要小于其他算法,在保證同步精度的前提下有效的降低了通信開銷。

3 算法實現及結果分析

3.1 實驗環境

為了真實地反映客觀物理環境,本文對時間同步能耗和精度的測試通過實驗完成。實驗采用實驗室自主研制的傳感器節點。該節點處理器芯片采用以AVR為核心的微處理器ATmega128L;RF射頻芯片采用CC2420射頻芯片,支持MAC層時間戳技術;采用TinyOS操作系統。

實驗平臺由9個節點組成,每個節點均采用頻率為7.3728MHz晶振。對于涉及計數器的精確操作,本實驗未使用TinyOS提供的通用計數器TimerMilliC,而采用ATmega128L的3號計數器HplAtm128Timer3C并對其晶振進行1024分頻作為時鐘源,從而獲得分辨率為2.5μs的時鐘源。

為驗證CRTS算法的性能,實驗基于本文提出的層次拓撲結構,在實驗平臺上實現了TPSN和CRTS算法,并對這2種算法獲得的測試數據進行處理和分析比對。在模擬井下工作面環境進行了實驗,選取8 m×2.4 m的區域布放9個節點,如圖6所示。根節點布放在測試區域的中央,其余節點隨機分布。為獲取算法的測試數據具有可比性,實驗均在相同的環境和平臺中獲得。

圖6 模擬井下實驗設置

網絡中使用可覆蓋全網的查詢節點和監聽節點,查詢節點以固定周期向全網廣播同步查詢報文,網絡中的同步節點收到查詢報文后,用本地時間記錄下接收到查詢報文的時刻并立刻發送響應報文,此時監聽節點監聽到各節點的響應報文并把這些報文上傳到上位機,上位機對數據進行處理和分析。

3.2 實驗結果分析

使用如圖6所示的拓撲結構進行同步精度測試。實驗中同步報文周期為5 s,分別對一跳、兩跳節點與時間源節點的同步誤差進行統計分析,每隔一個同步周期進行一次統計,測試所得誤差以同步周期個數為單位進行計算,獲得如圖7所示的同步誤差曲線圖。

為查看子節點與時間源節點的同步情況,實驗選取拓撲結構中的子節點進行同步實驗。從實驗結果可以看出:各跳節點同步誤差基本一致,同步誤差隨同步周期的增加變化不明顯,各跳平均誤差均在40 μs以內,誤差呈交錯波動形式,在與全網節點同步后同步誤差波動減小且穩定,可見該算法具有較好的收斂性,子節點可與時間源節點較好的保持同步。

對比CRTS算法與傳統TPSN算法的精度差異,分別給出了2種算法在相同實驗條件下的同步誤差分布對比曲線圖,如圖8所示。由實驗結果可看出:2種算法的同步精度相差不大,平均誤差在30 μs～50 μs之間。相對于TPSN算法,CRTS算法在滿足一定精度的前提下,大大減少了消息交換開銷,節約了能量,表現在數值上如表1所示。

圖7 不同跳數同步誤差曲線圖

圖8 不同算法同步誤差分布

在建立網絡拓撲后,不同算法在每個同步周期需發送同步報文個數隨網絡中節點數目的增加而增加[15]。由表2可知,TPSN算法的精度略高于CRTS算法,但根據同步開銷分析可知CRTS算法在通信開銷上要明顯低于TPSN算法。

表2 不同算法同步精度對比 單位:ms

4 結論

時間同步作為WSN應用的一項關鍵技術,對其算法的設計、實現和應用都非常重要[16]。對于煤礦井下WSN的應用,研究同步誤差范圍內如何降低通信開銷更為重要。本文針對這種情況并結合煤礦井下環境的特殊性提出一種面向煤礦井下的主被動式時間同步算法CRTS。對于分布在巷道的節點,構建新型多跳模型并進行主動式同步。對于分布在工作面環境的節點,通過建立分級分簇樹形拓撲網絡結構,對簇頭節點采用主動式同步實現簇間同步;簇內節點通過監聽簇頭節點的時間同步信息來進行被動式同步實現簇內同步,最終實現全網節點同步。與TPSN算法相比,該算法在滿足一定精度的前提下大大降低了通信開銷。通過WSN實驗平臺測試,結果表明與傳統TPSN算法相比該算法更適用于煤礦井下,且利用較少能耗達到所需同步精度。本文的研究對于煤礦井下時間同步具有一定的理論指導意義和實際應用價值。

[1] 崔麗珍,于洤. 基于ZigBee自適應通信在礦井瓦斯監控系統中的設計與實現[J]. 礦業安全與環保,2012,39(2):19-21.

[2]崔麗珍,李蕾,員曼曼,等. 基于核函數法及粒子濾波的煤礦井下定位算法研究[J]. 傳感技術學報,2013,26(12):1728-1733.

[3]Akyildiz I F,Su W,Sankarasubramaniam Y,et al. A Survey on Sensor Networks[J]. Communications Magazine,IEEE,2002,40(8):102-114.

[4]Werner-Allen G,Tewari G,Patel A,et al. Firefly-Inspired Sensor Network Synchronicity with Realistic Radio Effects[C]//Proceedings of the 3rd International Conference on Embedded Networked Sensor Systems. New York,NY,USA:ACM,2005:142-153.

[5]Schenato L,Gamba G. A Distributed Consensus Protocol for Clock Synchronization in Wireless Sensor Network[C]//Decision and Control,2007 46th IEEE Conference on. IEEE. New Orleans,LA,USA:IEEE,2007:2289-2294.

[6]Maggs M K,O’Keefe S G,Thiel D V. Consensus Clock Synchroni-zation for Wireless Sensor Networks[J]. Sensors Journal,IEEE,2012,12(6):2269-2277.

[7]王玉秀,黃劍,石欣,等. 基于分簇的低功耗多跳無線傳感器網絡層次時間同步算法[J]. 計算機應用,2013,33(2):369-373.

[8]Jeske D R. On Maximum-Likelihood Estimation of Clock Offset[J]. IEEE Transactions on Communications,2005,53(1):53-54.

[9]王越,萬洪. 一種節能的無線傳感器網絡多跳自適應時間同步算法[J]. 傳感技術學報,2013,26(11):1557-1563.

[10]吳寶明,李聲飛. 基于最優線性擬合的WSN時間同步算法研究[J]. 傳感技術學報,2010,23(12):1787-1791.

[11]張偉華,李臘元,張留敏,等. 無線傳感器網絡LEACH協議能耗均衡改進[J]. 傳感技術學報,2009,22(11):1918-1922.

[12]關新平,張曉靜,劉志新. 基于分簇的低功耗多跳WSN時間同步機制[J]. 計算機工程,2010,36(9):111-113.

[13]江禹生,樊宇. 無線傳感器網絡雙向成對時間同步優化方法[J]. 計算機工程,2013,123(5):126-131.

[14]吳成偉,黃文君. 無線傳感器網絡比對廣播時間同步算法[J]. 傳感技術學報,2009,22(12):1789-1794.

[15]汪付強,曾鵬,于海斌. 一種低開銷的雙向時間同步算法[J]. 儀器儀表學報,2011,32(6):1357-1363.

[16]孫德云,沈杰,劉海濤. 基于擴散機制的無線傳感器網絡時間同步協議[J]. 通信學報,2009,29(11):40-49.

崔麗珍(1968-),女,1990年畢業于北京交通大學通信工程專業。內蒙古科技大學信息工程學院副院長,碩士生導師,教授。研究方向為寬帶無線通信、無線傳感器網絡。承擔科研課題7項,發表科研論文30余篇。近年來專注于煤礦井下通信及監測系統的研究與開發,lizhencui@163.com;

員曼曼(1988-),女,內蒙古包頭人,碩士,研究方向為煤礦井下無線傳感器網絡時間同步算法研究與實現。

ResearchandImplementationofLowPowerTwo-WayWSNTimeSynchronizationAlgorithmforCoalMine*

CUILizhen*,YUANManman,LIZhang,HEJiaxing

(School of Information Engineering,Inner Mongolia University of Science and Technology,Baotou Inner Mongolia 014010,China)

The energy consumption problem that exists in traditional time synchronization algorithm because of exchanging more packets to obtain synchronization accuracy. According to the special network structure in underground coal mine,on the basis of the analysis of bidirectional pair and one-way broadcast synchronization mechanism,combine both synchronization mechanisms with the transmission characteristics of radio effectively,and a two-way synchronization algorithm based on clusters structure which at the characteristics of the passive and low power is proposed. Experiments show that,synchronization algorithm which been proposed can solve the problems of exchanging packets frequently effectively,in the range of allowable error can reduce message consumption and balance the network energy.

coal mine;time synchronization;wireless sensor network(WSN);Low power consumption;clustering

項目來源:包頭市科技發展項目(2012Z1006-5)

2014-04-16修改日期:2014-07-15

10.3969/j.issn.1004-1699.2014.09.018

TD76

:A

:1004-1699(2014)09-1253-07