一種多傳感器網(wǎng)絡(luò)全向全向同步協(xié)議

一種多傳感器網(wǎng)絡(luò)全向全向同步協(xié)議

1分時洪泛聯(lián)網(wǎng)同步協(xié)議隨著微型機械、集成電路和高密度電池等關(guān)鍵技術(shù)的發(fā)展，具有無線通信能力的廉價傳感器節(jié)點可以建立，這可以促進無線傳感器網(wǎng)絡(luò)的發(fā)展。其通過大量高密度的自組織傳感器節(jié)點協(xié)同監(jiān)測大范圍的外部環(huán)境,適用于軍隊、環(huán)境監(jiān)測、醫(yī)院、科學(xué)研究等領(lǐng)域。在大部分應(yīng)用場景中,節(jié)點能源的更換非常困難甚至不可能,因此能效問題是限制其應(yīng)用的重要因素,自然也是傳感器網(wǎng)絡(luò)協(xié)議的首要指標(biāo)。在無線傳感器網(wǎng)絡(luò)中,數(shù)據(jù)的無線收發(fā)是主要的能源消耗,所以節(jié)能協(xié)議應(yīng)該盡量減少節(jié)點的平均收發(fā)時間(包括空閑監(jiān)聽(idlelistening)時間)。全網(wǎng)范圍的時鐘同步協(xié)議不僅是大多數(shù)傳感器網(wǎng)絡(luò)工作的前提,同時也是使用TDMA協(xié)議的基礎(chǔ)。近年來雖然已提出過不少的同步協(xié)議如RBS、TPSN、DMTS、FTSP等,但它們并未在能效上進行充分的優(yōu)化。在RBS協(xié)議中,節(jié)點通過兩兩間交換接收到同一消息包時的本地時間計算出接收節(jié)點間的時鐘差異,這需要大量額外的消息交換,更重要的是發(fā)送節(jié)點并未與接收節(jié)點間取得同步,因此很難實現(xiàn)全網(wǎng)范圍的同步。在TPSN協(xié)議中,n層節(jié)點采用NTP方法與所有n+1層的鄰居節(jié)點進行雙向消息交換以完成同步。因此擁有N個子節(jié)點的n層節(jié)點必須完成N次同步包的接收和發(fā)送,這在高密度的傳感器網(wǎng)絡(luò)中也是極為耗費能源的。DMTS及FTSP在能效上有了很大的提升,在單個同步周期內(nèi),節(jié)點僅需發(fā)送一個同步包,但可能需要接收多個同步包以從中選擇合適的構(gòu)建參考點。除此之外,以上協(xié)議普遍存在更為嚴(yán)重的能耗問題,即長時間的空閑監(jiān)聽。造成空閑監(jiān)聽的原因是:在以隨機競爭為基礎(chǔ)的洪泛機制中,不同同步周期內(nèi)同步包擴散速度存在差異,且該差異將隨著節(jié)點跳數(shù)的增加而變得愈發(fā)嚴(yán)重,導(dǎo)致長期處于睡眠狀態(tài)的節(jié)點無法預(yù)知喚醒到接收狀態(tài)的準(zhǔn)確時間,被迫提前蘇醒。本文稱其為“喚醒時間不確定性”問題。在圖1所示拓撲中,陰影部分為根節(jié)點,并假定網(wǎng)絡(luò)使用CSMA形式的MAC協(xié)議,那么在A,B同步周期的起始時刻,根節(jié)點向外廣播同步包,1層節(jié)點(1,2,3,4等)收到同步包后通過隨機競爭方式搶占信道,假定它們處于同一碰撞域內(nèi),則同一時刻僅允許單個節(jié)點發(fā)送,由于競爭結(jié)果的隨機性,周期A時,處于3層的節(jié)點19在第3個單位時間接收到同步包,而周期B時節(jié)點19則在第8個單位時間內(nèi)接收到同步包,為了避免同步包丟失,節(jié)點19必須在第3個單位時間前喚醒至接收狀態(tài),因此對周期B而言,從第3個單位時間至第7個單位時間均屬于空閑監(jiān)聽時間。隨著節(jié)點層的增大,空閑監(jiān)聽將更加嚴(yán)重。本文提出了一種分時洪泛全網(wǎng)同步協(xié)議,簡稱TDFS(timedivisionfloodingnetwork-wideclocksynchronizationprotocol)。該協(xié)議通過降低空閑監(jiān)聽時間達到了更高的能源利用率。它將時間分割為多個等長時隙,并給節(jié)點分配獨一的專用時隙進行同步包發(fā)送,從而有效消除了喚醒時間的不確定性,仿真結(jié)果表明其具有極高的能效;協(xié)議還采用了新的時鐘頻偏校正技術(shù)以獲得更低的頻偏估計誤差。另外,由于協(xié)議的分時特性,它可與大多數(shù)現(xiàn)有的MAC協(xié)議協(xié)同工作。2tdfs協(xié)議關(guān)于同步源節(jié)點的選擇在TDFS協(xié)議中,認為:(1)網(wǎng)絡(luò)中的節(jié)點具有惟一的標(biāo)識號。(2)節(jié)點使用全向半雙工射頻模塊,并具有載波檢測功能。上述假設(shè)在大多數(shù)傳感器網(wǎng)絡(luò)中都是成立的。一般而言,同步協(xié)議由以下3部分組成:根節(jié)點選取、同步方法以及同步擴散。其中,同步方法定義如何實現(xiàn)一跳范圍內(nèi)節(jié)點的時鐘同步,同步擴散則負責(zé)將同步擴展至所有網(wǎng)絡(luò)節(jié)點,TDFS協(xié)議使用分時洪泛機制進行同步擴散。由于篇幅限制,本文對“根節(jié)點選取”不作介紹。TDFS協(xié)議使用如下同步方法:定義已獲得同步的節(jié)點為同步源節(jié)點,同步源節(jié)點依照發(fā)送機制向周圍節(jié)點廣播嵌入了其本地時鐘的同步消息包,接收節(jié)點記錄下同步包到達時的本地時鐘,并將其調(diào)整為同步源本地時鐘值加上傳輸延時估計值,從而實現(xiàn)與同步源節(jié)點間的同步。同步源發(fā)送范圍內(nèi)的任何未同步節(jié)點通過接收同步消息包與同步源同步,進而與根節(jié)點取得同步。下面先介紹一下協(xié)議的整體框架。2.1tdfs同步周期TDFS采用分時方法與其他協(xié)議分享信道,其時間分配如圖2所示。由于節(jié)點時鐘頻率的偏差,為了維持指定的同步精度,節(jié)點需要一定間隔后重新進行同步,該間隔稱為同步周期。圖2中Tp即是同步周期,而To則是同步周期內(nèi)TDFS協(xié)議占用時間,其余時間由MAC協(xié)議支配。實際應(yīng)用中,占用比率To/Tp非常小,僅為千分之幾(見仿真結(jié)果)。TDFS在每個同步周期可確定的指定時間范圍內(nèi)獲得信道支配權(quán)以執(zhí)行同步操作。由于它與MAC協(xié)議分時工作,因此可方便整合到MAC協(xié)議中。2.2節(jié)點層的劃分全網(wǎng)同步協(xié)議的核心是同步擴散,即如何將單跳內(nèi)同步方法擴展到多跳網(wǎng)絡(luò)中。TDFS使用分時洪泛機制進行同步擴散,協(xié)議按照到達根節(jié)點的跳數(shù)將節(jié)點分為不同的層,根節(jié)點層指定為0,其他節(jié)點的層則通過如下方法獲得:節(jié)點在同步包中填入其層值,接收節(jié)點則將其層設(shè)定為同步包中相應(yīng)值加1。一旦節(jié)點收到多個層值,節(jié)點將選取其中的最小值。全網(wǎng)同步由惟一的根節(jié)點發(fā)起,它在每個同步周期的起始時刻發(fā)送同步包,1層節(jié)點通過單跳內(nèi)同步方法直接與根節(jié)點取得同步,同步后的1層節(jié)點則按照分時洪泛機制發(fā)送自己的同步包,下級節(jié)點通過同步到上級節(jié)點間接與根節(jié)點同步。2.2.1節(jié)點接收同步機制To長度的TDFS協(xié)議占用時間分為以下4部分(如圖3所示)。顧名思義,節(jié)點在“接收時間段”內(nèi)喚醒到接收狀態(tài),在“發(fā)送時間段”內(nèi)競爭信道進行同步包發(fā)送?！扒凹壗邮諘r間段”和“后級發(fā)送時間段”則分別指示前一級節(jié)點處于接收時間段和后一級節(jié)點處于發(fā)送時間段,此期間節(jié)點不允許發(fā)送,否則將分別影響前級節(jié)點的接收和后級節(jié)點的發(fā)送。顯然根節(jié)點不存在“前級節(jié)點接收時間段”及“接收時間段”。于是可以得到不同層節(jié)點各時間段的關(guān)系(如圖4所示)。回到喚醒時間的不確定性問題,在傳統(tǒng)的洪泛機制下,節(jié)點接收同步消息包后立即嘗試發(fā)送新的同步包,由于在同一碰撞域內(nèi),相同時刻僅允許單個同級節(jié)點發(fā)送,其它節(jié)點則被迫延遲發(fā)送,因此同步時間差異性將隨層的增大而迅速惡化。與其它協(xié)議不同,在TDFS中,節(jié)點在“接收時間段”中取得同步后,無論先后,都必須等待至發(fā)送時間段內(nèi)才允許發(fā)送,通過限定節(jié)點發(fā)送的時間范圍,協(xié)議有效地遏制了不確定性的傳遞。選定發(fā)送時間段長度為Tc,根節(jié)點在同步周期的起始時刻進入“發(fā)送時間段”,由此得出:第i周期中,根節(jié)點的“發(fā)送時間段”為[iTp,iTp+Tc],因此n層節(jié)點的“發(fā)送時間段”為[iTp+nTc,iTp+(n+1)Tc],n層節(jié)點的“接收時間段”與n-1層節(jié)點的“發(fā)送時間段”相同,即為[iTp+(n-1)Tc,iTp+nTc]。同理“前級接收時間段”和“節(jié)點發(fā)送時間段”分別為[iTp+(n-2)Tc,iTp+(n-1)Tc]和[iTp+(n+1)Tc,iTp+(n+2)Tc]。2.2.2tdfs:非認同發(fā)送節(jié)點所有發(fā)送子時隙未被激發(fā)傳統(tǒng)CSMA形式的發(fā)送機制將造成節(jié)點發(fā)送次序的隨機性,引發(fā)喚醒時間不確定性問題,且機制在密集分布的傳感器網(wǎng)絡(luò)中效率較低,碰撞概率高,因此我們設(shè)計了一種全新高效的發(fā)送機制,將TDMA與CSMA相結(jié)合。TDFS將“發(fā)送時間段”進一步劃分為Ns段Ts間隔的發(fā)送子時隙,每個發(fā)送子時隙僅允許單個節(jié)點進行發(fā)送。發(fā)送子時隙由保護間隔,競爭信道時間及實際發(fā)包時間組成(如圖5所示)。同理,接收時間段亦可分為Ns段Ts長度的接收子時隙,與前級節(jié)點的發(fā)送子時隙對應(yīng)。由于同步誤差的存在,實際中各節(jié)點相應(yīng)時隙不可能完全對齊,因此需要使用保護間隔進行保護,一般同步誤差為幾十微秒量級,而協(xié)議使用的保護間隔為百微妙量級,因此不會對協(xié)議造成影響。首先定義在某發(fā)送子時隙擁有優(yōu)先發(fā)送權(quán)的節(jié)點為該子時隙的“默認發(fā)送節(jié)點”,而該發(fā)送子時隙則稱為此節(jié)點的“默認發(fā)送子時隙”。發(fā)送優(yōu)先級通過在競爭信道時間內(nèi)選取不同的退避時間產(chǎn)生,其中退避時間等于節(jié)點隨機選取的退避值乘以單位退避時間Tm。默認發(fā)送節(jié)點從“默認退避窗口”中隨機選擇退避值,而非默認發(fā)送節(jié)點則從“非默認退避窗口”中取值。設(shè)定默認退避窗口范圍為[0,W1],非默認退避窗口范圍為[W1+1,W2],其中,W2>W1+1。因此,相對非默認發(fā)送節(jié)點而言,默認發(fā)送節(jié)點擁有絕對優(yōu)先的發(fā)送權(quán)利。TDFS采用TDMA與隨機競爭相結(jié)合的發(fā)送機制,動態(tài)地為節(jié)點分配獨一的默認發(fā)送子時隙,保證其有序發(fā)送,最大限度地避免碰撞。首先,節(jié)點將初始默認發(fā)送子時隙設(shè)置為標(biāo)識號除Ns的余數(shù)。當(dāng)然該初始值并不能保證分配的獨一性,因此協(xié)議采用以下動態(tài)更新機制進行調(diào)整。某周期的發(fā)送時間段內(nèi),節(jié)點在其默認發(fā)送子時隙中從[0,W1]隨機選取退避值Wb,等待WbTm時間后監(jiān)測載波;倘若沒有監(jiān)測到載波,該節(jié)點獲得信道使用權(quán)并隨后發(fā)送同步包;否則,節(jié)點設(shè)置默認發(fā)送子時隙為-1并取消發(fā)送。默認發(fā)送子時隙為-1的節(jié)點將在本周期剩余的發(fā)送子時隙及下周期的所有子時隙中繼續(xù)競爭信道,但此時節(jié)點只能在非默認退避窗口[W1+1,W2]中選擇退避值。一旦節(jié)點在某個發(fā)送子時隙中成功發(fā)送,他便重新設(shè)置其默認發(fā)送子時隙重新為該子時隙號。如果兩周期后節(jié)點仍未取得信道使用權(quán)(說明所有子時隙均被占用),它將在Nr同步周期后重新競爭信道。舉例說明:令Ns為5,并假定同一碰撞域中存在相同層且標(biāo)識號分別是5,6,8,13,9的5個節(jié)點。那么,它們的初始默認發(fā)送子時隙分別為5%5=0、6%5=1、8%5=3、13%5=3、9%5=4。有且只有節(jié)點5的默認發(fā)送子時隙為0,在發(fā)送子時隙0中,它將在[0,W1]中隨機選擇退避值,因為沒有其他的競爭者,它獲得信道使用權(quán)并成功發(fā)送同步包;在發(fā)送子時隙1中,同理節(jié)點6將獲得信道使用權(quán)成功發(fā)送。發(fā)送子時隙2沒有默認發(fā)送節(jié)點且不存在默認發(fā)送子時隙為-1的節(jié)點,因此沒有節(jié)點在該時隙中發(fā)送。在發(fā)送子時隙3中,節(jié)點8和13分別從[0,W1]中隨機選擇退避值,值小者將獲得信道的使用權(quán),而值大者(假定為節(jié)點13)將設(shè)置默認發(fā)送子時隙為-1。在最后的子時隙4中,由于此時節(jié)點13的默認發(fā)送子時隙已經(jīng)變?yōu)?1,所以它將和節(jié)點9競爭該子時隙,顯然默認發(fā)送節(jié)點9將獲勝。在該同步周期內(nèi)沒有獲得發(fā)送機會的節(jié)點13被迫在下個同步周期內(nèi)的所有發(fā)送子時隙重新嘗試發(fā)送,恰好發(fā)送子時隙2沒有默認發(fā)送節(jié)點,于是它在子時隙2中成功發(fā)送并重新設(shè)置默認發(fā)送子時隙為2。此后,該5個節(jié)點將在自己的默認發(fā)送子時隙中無碰撞地發(fā)送同步包。當(dāng)然在擁有多個默認發(fā)送節(jié)點的發(fā)送子時隙(如子時隙3)中,節(jié)點有可能因為選取相同退避值而發(fā)生碰撞,但這只是暫時的,只要在下一周期選擇不同的退避值(不可能每次都相同),多余節(jié)點將被踢出該子時隙,最終在同一碰撞域內(nèi),該發(fā)送子時隙中只存在惟一的默認發(fā)送節(jié)點。因此只要沒有新節(jié)點加入,節(jié)點將始終在其固定的默認發(fā)送子時隙中無碰撞地發(fā)送,這對確定喚醒時間是十分有利的。節(jié)點通過每隔一定周期監(jiān)聽整個接收時間段動態(tài)了解所有能夠有效接收同步包的子時隙號,在以后的周期內(nèi),節(jié)點僅需在感興趣的某個有效接收子時隙中切換到接收狀態(tài),無需監(jiān)聽整個接收時間段,所以,節(jié)點的喚醒時間可精確到子時隙長度。注意,雖然協(xié)議的占用時間為4Tc,但實際處于發(fā)送或接收狀態(tài)的時間僅約為Ts。Ns取值對協(xié)議性能有一定的影響:取值過小會減少允許發(fā)送節(jié)點的數(shù)量,增加網(wǎng)絡(luò)級數(shù),造成同步精度的降低;而取值太大,雖然不會影響能效,但會增加占用時間,降低帶寬利用率。假定Na節(jié)點均勻分布在Sd面積的區(qū)域內(nèi),節(jié)點的傳輸距離為Rt,那么可以使用如下經(jīng)驗公式選取Ns。取值偏大帶來的影響較小,因此實際應(yīng)用中推薦選擇稍大的Ns值。2.2.3節(jié)點的調(diào)整層nr更新為適應(yīng)傳感器網(wǎng)絡(luò)的拓撲變化(新節(jié)點加入或舊節(jié)點失效),節(jié)點需要適時進行層更新以獲取最佳的層值,實現(xiàn)更小的同步誤差。節(jié)點在以下2種情況下,執(zhí)行更新操作。(1)持續(xù)Ne同步周期未接收到同步包。該情況表明n層節(jié)點周圍已經(jīng)不存在n-1層的鄰居,因此節(jié)點需要調(diào)整層以重新保持同步。(2)每隔Nr同步周期。實際應(yīng)用中,Nr的取值需在耗能及反應(yīng)速度上進行折衷。在本協(xié)議中,由于發(fā)送、接收時間段由節(jié)點所在層惟一決定,因此節(jié)點可計算出任意層對應(yīng)的發(fā)送時間段范圍,通過在相應(yīng)時間段內(nèi)監(jiān)聽信道就能獲取可能的新層,即達到層更新的目的。通常n層節(jié)點的接收范圍內(nèi)只可能存在層為[n-2,n+2]范圍節(jié)點,因此更新操作實際就是在[n-2,n+2]層節(jié)點對應(yīng)發(fā)送時間段內(nèi)監(jiān)聽信道,然后將層更新為最小的可選值。在更新過程中,節(jié)點還將記錄所有的有效接收子時隙號。需要指出的是,更新操作除了消耗一定能源和少量帶寬外,并不會對網(wǎng)絡(luò)造成任何新的負載。2.3同步周期內(nèi)dp的估計精度由于晶體頻偏的影響,同步誤差將隨著時間的推移而增大,因此為滿足一定的同步精度要求,需要進行周期性同步。更長的同步間隔則意味著更少的能源消耗,為了節(jié)約能源,就需要在軟件上對時鐘頻率進行校正。TDFS采用下式對頻偏?f進行估計其中,f為晶體特征頻率,dp為第p個同步周期內(nèi),同步包到達時節(jié)點本地時鐘與全局時鐘的誤差,采用q次dp進行平均能夠有效提高估計精度?？梢宰C明,對于層值為n的節(jié)點,其dp的均方差與sqrt(n)成正比,為了保證不同層節(jié)點達到同樣的估計精度,q的選擇同樣應(yīng)該與sqrt(n)成正比。協(xié)議中q的選取如下其中,Td是最大累計誤差閾值,Dqo是1層節(jié)點的默認q值。實際應(yīng)用中,q的選擇還與硬件平臺的內(nèi)存容量有關(guān)。采用式(3)不但可以降低頻偏估計的方差,更重要的是能夠根據(jù)不同程度的頻偏自適應(yīng)調(diào)整。在同步起始階段節(jié)點間頻偏較大,q由前半項決定,加快了頻偏估計的收斂速度;隨著頻偏估計誤差的降低,q將選取為以獲得更小的估計誤差。3性能評價3.1傳輸延遲參數(shù)設(shè)置本文所使用的仿真平臺為NS-2(ns-2.28),表1給出了仿真中使用的部分物理信道參數(shù)和協(xié)議參數(shù)設(shè)置。為了更準(zhǔn)確地仿真同步誤差,仿真中所使用的傳輸延時參數(shù)均從實際場景中提取而得。使用TI公司的CC1020芯片制作了硬件模塊,并實現(xiàn)了部分協(xié)議功能。模塊被放置在一跳之內(nèi),采用示波器測量其傳輸延時,可以得出:傳輸延時可近似分解為延時均值Dn1->n2加上隨機項nn1->n2,其中延時均值可近似為Un(58.3μs,58.9μs)均勻分布的隨機變量,而延時隨機項則可抽象成均值為0,方差為0.9μs的正態(tài)高斯,因此協(xié)議中傳輸延時估計值選取為58.6μs。3.2被圈檢驗的根節(jié)點仿真中分別使用了A、B兩種場景,見圖6和圖7。兩圖中被圓圈包圍的節(jié)點為根節(jié)點。因為仿真中接收范圍設(shè)置為20m,所以場景A中,節(jié)點只能與鄰近的8個節(jié)點進行通信。3.3節(jié)點時鐘同步誤差影響以下仿真主要基于如下4種配置:場景A同步周期為15s,場景A同步周期為30s,場景B同步周期為15s,場景B同步周期為30s。選取Ns為6,可得出單周期內(nèi)節(jié)點處于接收(包括載波檢測)、發(fā)送狀態(tài)的平均時間與層的關(guān)系如圖8所示。從圖8可以看出,單周期內(nèi)節(jié)點平均發(fā)送時間小于2ms,接收時間小于3.8ms,略大于子時隙時間3ms(單個同步包的物理發(fā)送時間為1.875ms)。選取同步周期為30s,則平均發(fā)送、接收時間僅占總時間的0.06‰及0.127‰,由此可見,協(xié)議擁有極其卓越的能源利用率。由于占用時間To為72ms,因此To/Tp僅為2.4‰。另外,平均接收時間基本與同步周期、層值(根節(jié)點除外)及場景無關(guān),而平均發(fā)送時間受拓撲結(jié)構(gòu)輕微影響,這是因為同一碰撞域中,相同層僅有Ns節(jié)點能夠成功發(fā)送同步包,因此在節(jié)點密度較高的區(qū)域中一些節(jié)點不需要發(fā)送,造成平均發(fā)送時間相應(yīng)下降。一致的發(fā)送和接收時間保證了網(wǎng)絡(luò)中節(jié)點能源消耗的一致性,避免了由于耗能不平衡造成部分節(jié)點提前失效。圖9、圖10分別給出了網(wǎng)絡(luò)相對穩(wěn)定后時鐘同步誤差的均方差及頻率校正誤差的均方差與節(jié)點層值的關(guān)系?？梢宰C明節(jié)點時鐘同步誤差dp的均方差與節(jié)點層值的平方根成線性關(guān)系,圖9恰恰驗證了這一點。進一步可以發(fā)現(xiàn),不同的場景及同步周期對時鐘同步誤差影響很小。從圖10可以看出,使用新的頻率校正方法后,頻偏校正誤差的均方差不會隨著節(jié)點層發(fā)生變化。當(dāng)然,同步周期越大,為滿足同樣的精度要求,頻偏校正誤差的均方差應(yīng)該越小,因此,同步周期提高一倍后,頻率誤差均方差也降為原來的一半。TDFS協(xié)議中需要根據(jù)節(jié)點的密度來確定子時隙長度Ns的值,在場景B中,分別選取Ns為3、4、5、6、7、8并得到圖11?？梢钥闯?Ns為3時網(wǎng)絡(luò)中的最大層為19,且少數(shù)節(jié)點未被同步。當(dāng)Ns增加至5時,最大層值下降為8,此后Ns的進一步增長對層分布的影響較小,通過經(jīng)驗式(1)所得出的最小Ns值恰好為5,增大Ns雖然會造成占用時間的增大,但并不會帶來多余的能源消耗,而Ns過小則將導(dǎo)致節(jié)點層增加,降低同步精度,甚至造成部分節(jié)點不能被同步,因此實際應(yīng)用中,應(yīng)該選取稍大的Ns值。圖12給出了網(wǎng)絡(luò)節(jié)點拓撲結(jié)構(gòu)改變對同步層結(jié)構(gòu)的影響。在場景B中,某時刻關(guān)閉四分之一的節(jié)點,一段時間后