基于分簇的無線傳感器網絡數據傳遞協議

無線傳感器網絡（wsds）是一種新型的信息獲取和處理形式，構建了信息空間和物理空間的橋梁，廣泛應用于國防和軍事、國家安全、環境、交通管理、衛生、林業、反恐防災等領域。WSNs本質上是一類特殊的自組織(ad-hoc)網絡,具有以下特質:1)網絡規模大,節點密度高;2)節點的能量、計算和存儲能力嚴格受限;3)節點易失效,網絡拓撲結構頻繁變化;4)節點沒有統一的標識;5)節點部署后位置一般不發生變化.一方面,傳感節點依靠電池供電且通常工作在無人值守的環境下,補充能量非常困難,因此,能量優化要貫穿于通信、工作模式、任務協調、數據管理等各個層面;另一方面,無線傳感器網絡的設計是面向具體應用的,不同的應用有不同期望的服務質量要求,網絡設計要首先考慮應用的服務質量.同時,傳感節點所采集的感知數據又有很強的相關性,這種相關性使得數據在時間和空間上都可能存在冗余,減少這種冗余成為設計無線傳感器網絡考慮的一個重點.基于分簇的數據收集方法經常應用在無線傳感器網絡的路由協議中,其優點是方便管理、增強網絡的可擴展性及易于實現數據融合.為此,本文提出了一種基于分簇的數據匯聚傳送協議CDAT(acluster-baseddataaggregationandtransmissionprotocolforwirelesssensornetworks),根據應用期望的服務質量來計算簇頭數,使用輪換簇頭的方法來平衡能耗,通過預測性傳送機制減少數據的傳送次數,進一步降低網絡的傳送能耗,延長網絡的生命期.本文第1節介紹相關工作.第2節對網絡模型進行描述并提出了問題.第3節給出CDAT協議的詳細設計第4節對協議的能耗作出分析.第5節進行模擬驗證.最后總結全文.1打造更均勻的網絡拓撲分簇路由協議一般會根據某種規則把WSNs節點集劃分為多個子集,每個子集為一個簇,每個簇由一個簇頭節點負責全局路由,其他節點通過簇頭接收或發送數據.LEACH(low-energyadaptiveclusteringhierarchy)就是一個典型的分簇協議,通過等概率地隨機循環選擇簇頭,將整個網絡的能耗負載均衡地分配到每個傳感器節點,從而達到降低網絡能耗、延長網絡生命周期的目的.但是,LEACH沒有考慮以下問題:1)簇頭數的選擇沒有考慮應用期望的服務質量問題;2)沒有對數據傳送階段作很好的優化;3)簇頭是隨機選取的,不能保證簇頭在網絡中的均勻分布.HEED(ahybrid,energy-efficient,distributedclusteringapproach)協議在簇頭選擇中考慮了節點的剩余能量,并以主從關系引入了多個約束條件作用于簇頭的選擇過程.HEED在簇頭選擇標準及簇頭競爭機制上都與LEACH不同,實驗結果表明,HEED分簇速度更快,能夠產生更加分布均勻的簇頭、更合理的網絡拓撲.針對LEACH協議的缺點提出的PEGASIS(power-efficientgatheringinsensorinformationsystems),把所有的傳感器節點視為一個簇,根據節點的地理位置形成一條相鄰節點之間距離最短的鏈,所有傳感器節點把數據傳送到簇頭,簇頭執行聚集操作并把結果傳輸到基站.TEEN(thresholdsensitiveenergyefficientsensornetworkprotocol)協議在協議中設置了硬、軟兩個閾值,以減少發送數據的次數.通過設置軟、硬門限可以在精度和能耗之間取得合理的平衡,但存在以下缺陷:1)如果感知的數據達不到硬門限的要求,節點就不會傳送數據,即使網絡中所有的節點能量全部耗盡,用戶也不會知道;2)協議不能反映網絡數據整體的變化情況,在達不到硬門限的情況下,感知數據即使發生劇烈的變化也不能反映出來.此外,文獻是一個使用MPEG-2視頻壓縮算法作預測的數據收集協議,文獻是一個基于雙預測的目標跟蹤協議,文獻使用數據聚合的方法來減少數據的時空相關性,文獻交替使用預測和壓縮兩種方式來減少數據的發送.但這些預測協議大都是平面路由協議,沒有考慮到網絡期望的服務質量,也沒有考慮模型的動態更新等問題.2網絡模型和問題描述2.1無線傳感器網絡的目標本文假設N個無線傳感器節點隨機、均勻地分布在一個L×L的二維方形區域A內,該傳感器網絡具有以下性質:1)無線傳感器網絡為靜態網絡,節點部署后不再移動.2)節點采用布爾感知模型,節點的感知半徑為r,且忽略邊界因素影響.3)唯一的基站部署在區域A以外的一個固定位置,具有強大的能量和計算能力.4)節點是同構的,具有相同的初始能量,且節點的無線發射功率可調.5)應用對于網絡有服務質量的要求,這里主要是指網絡的無縫覆蓋率和感知數據傳送的誤差門限.定義1.有效覆蓋面積.在無線傳感器網絡的監測區域內,一塊區域有可能被幾個節點所覆蓋,如圖1所示.節點C1的有效覆蓋面積SC1為節點C1的覆蓋范圍πr2減去重復覆蓋區域C面積SC的一半,即定義2.文獻證明,在圖2所示的相鄰節點覆蓋拓撲中,當節點A所覆蓋的區域是一個邊長為r的正六邊形時,其所覆蓋的無縫面積最大,即2.2有大量節點能量消耗過快有效的分簇算法應該考慮以下問題:1)應使用分布式的分簇算法,這樣有利于節省網絡能量和提高可擴展性;2)為了實現節點能耗的均衡,簇頭應盡可能均勻地分布在整個網絡,否則會導致監測區域中某些節點能量消耗過快,造成感知空洞;3)無線傳感器網絡大都與應用相關,應根據應用要求的服務質量來設計網絡;4)在滿足誤差要求的情況下,根據感知數據在時間或空間上的相關性進行優化,減少傳送次數,進而減少傳送能耗.目前,對于無線傳感器網絡分簇算法的研究大多集中在前兩項,對于數據傳送的優化涉及較少.為此,在滿足一定網絡服務質量(網絡覆蓋率、數據傳送精度)的前提下,根據感知數據的時間相關性,本文提出了一種基于分簇的數據匯聚傳送協議.3第一階段:取初始概率+數據聚合階段CDAT協議和大部分分簇協議一樣是按輪運行的,每輪分為簇頭節點的選取、數據聚合和數據傳送3個階段.在簇頭選取階段,利用應用期望的無縫覆蓋率與所需要簇頭數的數學關系限制節點競選簇頭的初始概率,以此獲得期望的簇頭數,并聯合節點的剩余能量和最小度來選取簇頭;在數據聚合階段,簇頭廣播消息,接收所有加入該簇的成員節點,然后對簇內數據進行聚合;在數據傳送階段,利用數據的相關性,簇頭在滿足傳送精度的要求下,采用預測傳送機制進行數據傳送.3.1無縫覆蓋面積占總面積的計算假定應用提出的網絡無縫覆蓋率為η,也就是說,每輪監測中網絡需要若干個簇頭(假定數量為k),由這k個簇頭形成的無縫覆蓋面積占總的監測面積||A||之比為η.由公式(2)可知,單個簇頭最大無縫覆蓋的面積為,監測區域A中任意一點a(x,y)沒有被隨機選取的任一簇頭Ci(1≤i≤k)覆蓋的概率為因此,在區域A中隨機選取k個簇頭,任一點a(x,y)至少被其中一個簇頭節點覆蓋的概率Pa-covered也就是網絡無縫覆蓋率,即從而簇頭數k為3.2競爭簇頭的選取簇頭選擇機制采用分布式的算法,單個節點根據概率獨自地選擇是否成為簇頭.為了使能耗均勻地分布到所有的節點,節點i成為簇頭的概率由下式計算:其中,k由公式(5)確定,k/N主要是為了限制初始簇頭的數量,Ei-current表示節點當前的能量,Eorigin表示節點初始的能量.Emin表示簇頭節點能量的最小閾值,當節點的能量小于Emin時,該節點不再參與簇頭的競爭.Emin值主要是由簇頭參與一次數據的接收、聚合和發送能耗決定.本算法采用與LEACH協議相同的能量衰減模型,發送數據和接收的無線通信模型分別為其中,Eelec表示無線收發電路能耗,εfs和εmp分別表示自由空間模型和多路衰減模型的放大器能耗,d0是常數,h為要發送或接收的數據位數.因此,Emin可由下式計算:其中,Eda為聚合單位數據所需能耗.對于任意節點i,在簇頭選取階段需要執行簇生成算法,主體是一段循環代碼,循環的次數與節點的當前能量Ei-current有關.為了更好地均衡網絡能耗,在競爭簇頭的過程中還考慮了節點的度,使得每一輪中具有最小度的節點成為簇頭,算法如圖3所示.由上可知,節點i首先通過接收周圍節點的廣播消息來計算自己的度和Pi-ch.循環開始時,節點i判斷臨時簇頭集合CH_set是否為空,若不空,則選出度數最小的節點來,如果選出來的節點是自己且競爭簇頭的概率為1,則廣播自己為正式簇頭;如果競爭簇頭的概率不為1,則為臨時簇頭.如果臨時簇頭集合為空,且競爭簇頭的概率為1,則廣播自己為正式簇頭;否則,如果隨機生成的數不大于競爭簇頭的概率,則成為臨時簇頭.循環結束后,若還沒有成為簇頭,且臨時簇頭集合不空,則加入以最小度節點為簇頭的簇;否則認為自己沒有被覆蓋,廣播自己為正式簇頭.分簇形成以后,簇頭通過建立一個TDMA調度時隙表來控制本簇內的數據發送,并把這個調度廣播給簇成員,這樣就可以確保簇內各個成員無沖突地發送數據,并且節點在其他節點的發送時隙可以關閉電源以節省能量.簇頭接收完簇成員數據后,對數據進行聚合,其輸出的數據量取決于待聚合數據之間的相關性.3.3預測數據上傳機制在數據傳送階段,根據網絡服務質量選出的k個簇頭,經過本簇內的數據聚合后要和基站進行數據通信,如何優化數據傳送成為減少能耗的關鍵.無線傳感器網絡中,節點的感知數據往往是時間上相關的,相互鄰近的數據在數值上有一定的相關性,也就是時間序列數據.為了減少數據在時間上的冗余,在滿足誤差條件下,本文在數據傳送階段提出了預測數據傳送機制.該機制的基本思路是,把預測數據與模型計算分離,基站根據歷史數據建立模型,并把模型參數發送給各個簇頭.單個簇頭在與基站通信的過程中,通過預測和比較數據,只要預測數據和感知數據聚合值不大于根據應用要求設定的誤差門限,就可以不用傳送數據,而是在基站直接預測即可;為了適應感知數據的變化,傳送機制還可以隨著感知數據的變化作動態的調整.另外,在整個網絡中只有監測對象所在簇的感知數據會發生顯著變化,也只有這些簇頭才會與基站發生數據傳送,其他簇由于沒有監測到對象,它們的感知數據變化不大,從而數據傳送得到抑制.這樣,通過把運算量較大的模型參數計算模塊放在能量相對充足的基站,簇頭只進行簡單的預測和數據比較計算,從而極大地減少了簇頭的計算和傳輸能耗,提高了網絡的生存能力.3.3.1平穩時間序列預測一般的數據預測算法有很多,考慮到簇頭節點的能量有限和數據在時間上的相關性,這里采用簡單的中心化自回歸(AR)模型,并且假定感知數據序列是平穩的,即其中,Xi∈R為簇頭第i次的感知數據聚合值,φi是回歸系數,{at}是服從N(0,σa2)標準正態分布的白噪聲序列,公式(10)表明,第t次感知數據聚合值可以用前p次數據的線性組合加上一個隨機的白噪聲來表示.令由公式(11)、公式(12)可得,由最小二乘法可得系數矩陣和方差的估計,即進而t時刻的l步前向預測值及方差分別為其中,X?t(k)=???X?t(k),k≥1,G=?j??G0=1,j=1,2,...,φk′=??φk,k≤p.由上可知,對于平穩時間序列的預測,實質上就是根據所有已知的歷史信息Xt,Xt-1,...對序列未來某個時期的發展水平Xt+l(l=1,2,...)做出估計.3.3.2模型計算與預測相分離為了使模型對于感知數據的變化具有自適應能力,模型被設計成動態調整的.這主要是通過基站和簇頭的信息交互來完成,即把模型計算與數據預測相分離,由基站完成模型的計算和更新,根據具體應用設定的比率決定是否把模型參數發給簇頭節點;由簇頭節點完成感知數據的聚合和誤差比較,從而決定是否發送感知數據聚合值給基站.具體算法如圖4、圖5所示.4cat協議的能耗評估本節對CDAT協議和未使用預測發送機制的一般分簇GCP(generalclusteringprotocol)協議進行能量消耗比較.假定傳感器節點每次產生的單元數據長度為h,簇頭每一輪聚合這些數據后,要發送給基站的數據量為mh.對于CDAT協議,簇頭使用預測傳送機制只需要發送個數據給基站,為數據預測傳送所需次數,根據第3.3節預測算法可知,若l=1,則其中,為示性函數,Errthreshold為網絡服務質量給定的誤差門限.現在計算每一輪中一個簇的能量消耗,理想情況下,簇的范圍為一個覆蓋半徑R的圓,R可由下式計算:k由公式(5)計算,因此有則簇成員節點的能量花費為對于簇頭節點,能量消耗包括接收、聚合成員節點的感知數據和發送數據給基站,即一個簇在一輪內消耗的能量為所以,總的能量消耗為其中,為沒有受到數據傳送抑制的簇頭個數.對于GCP協議,一輪傳送m個數據的能量消耗為總的能量消耗為由于<k,<m,公式(24)和公式(26)相比較可得,數據傳送能耗在WSNs的整體能耗中所占比重很大,因此使用預測機制對數據傳送進行優化的CDAT協議,其能耗遠小于未采用預測傳送機制的一般分簇協議,后面的實驗也證明了這一點.5氣調與預測的驗證模擬實驗環境是監測區域大小為200m×200m,隨機部署節點總數為200,基站的坐標為(100,300),監測區域的無縫覆蓋率為95%.為了驗證數據預測傳送的性能,選取赤道附近海洋表面空氣溫度作為感知數據,感知間隔為10min.,模擬實驗參數見表1.5.1打造結果比較為了驗證公式(5)的正確性,對理論分析與模擬實驗的結果進行比較.從圖6可知,由公式(5)計算出來的簇頭數與應用期望的無縫覆蓋率的關系曲線與模擬實驗所得結果比較吻合,這說明對于簇頭數量的分析結論是正確的.5.2網絡生命期仿真設置:監測區域面積為200m×200m,部署的節點數量為200,匯聚點的位置為(100,300),監測區域要求95%被覆蓋,誤差門限為0.1,采用文獻中關于網絡生命期的定義,即網絡初始運行到第1個節點死亡之間的時間長度FND(firstnodedie),在LEACH協議的基礎上擴展了CDAT,PEGASIS和DIRECT協議.實驗結果如圖7所示.從圖7可以看出,CDAT協議的網絡生命期比PEGASIS和LEACH分別提高了45%和260%,這主要貢獻于能耗均衡的分布式分簇算法和預測傳送機制.通過限制簇頭初始競選概率,聯合剩余能量和節點的度來選取簇頭使得能耗負載均勻分布,預測傳送機制大大減少了感知數據傳送的次數,大部分長距離的數據傳送能耗被避免(下節實驗顯示,80%左右的數據不用傳送).PEGASIS協議由于要獲得所有節點的全局消息,在節點數量較多的情況下控制開銷較大,所以性能受到一定的影響.不像CDAT協議,LEACH不是通過應用的覆蓋需求得到簇頭數,而是簇頭數量與節點數量成正比.因此,當節點數量較多時,其簇構造的開銷也較大,同時也沒有對數據傳送進行優化,使得協議的性能下降.DIRECT協議中所有的節點直接與基站通信,長距離的通信能耗導致網絡生命期最短.5.3發送次數對算法設計的影響預測數據傳送機制能夠有效地減少數據的傳送次數,主要依賴于誤差門限Errthreshold及主動調節參數β.為此,下面主要對這兩個參數進行研究.5.3.1cdat協議的預測精度分析由第4節能耗比較分析可知,Errthreshold的選擇決定著感知聚合數據值傳送次數的多少,對于預測傳送機制的性能起到決定性作用.在考慮Errthreshold時,不僅要考慮盡可能地少傳數據,而且還要考察合適的預測誤差范圍,取得傳送效率和預測精度的平衡.為此,使用數據發送率和平均相對誤差兩個指標來確定Errthreshold的值.為了比較預測誤差,我們在GCP協議上也加上了預測功能,使用跨距為3的移動平均方法來預測數據.數據發送率Rds定義為因預測失敗而發送的數據占全部要發送數據的比例,即平均相對誤差Errmrd定義為由表2可知,當Errthreshold為0.05時,GCP僅能過濾42%的冗余數據,而CDAT則能濾除66%的冗余數據,CDAT較之GCP的預測精度提高了24%.當Errthreshold為0.1時,CDAT能夠濾除83%的冗余