無線傳感器網絡分簇路由協(xié)議研究

無線傳感器網絡分簇路由協(xié)議研究

無線傳感器網絡（wsd）是一個由大量電子傳感器以自組織和跳轉方式構建的網絡。其特點是檢測范圍廣、持續(xù)時間長、感知能力強、信息傳遞及時等,目的是協(xié)作地感知、采集、處理和傳輸感知對象的監(jiān)測信息,并報告給所需用戶,起到物理世界和電子世界便捷溝通的橋梁。在工農業(yè)控制、城市污染監(jiān)測、軍事領域、電子感知醫(yī)療、搶險救災、智能交通等領域具有廣闊的應用前景,是當前國際科技競爭的焦點和制高點,已經成為國內外研究的熱點。1基于分簇網絡的路由協(xié)議路由協(xié)議在WSN體系結構中,具有非常重要的地位,路由協(xié)議的好壞直接影響WSN的性能,要實現網絡快速及動態(tài)構建,行之有效的方法是采用分簇機制。在分簇網絡中,所有節(jié)點根據簇首(clusterhead)選舉辦法,形成一個基于分簇的自組織網絡。該網絡不受網絡規(guī)模限制,路由開銷較小,抗毀性強,容易實現移動管理和網絡的局部同步?；诜执芈酚傻木W絡中,由一個簇首節(jié)點(sink)和多個簇成員節(jié)點(clustermember)構成,形成一個樹狀結構,自下而上的傳遞信息,最終由簇首節(jié)點與基站BS(basestation)進行信息通信,其拓撲結構如圖1所示。與傳統(tǒng)的無線傳感器網絡路由協(xié)議相比,分簇路由協(xié)議具有拓撲結構便于管理,無需維護復雜的路由表,較高的網絡能量利用率,較好的可擴展性以及適合大規(guī)模網絡等特點,因此以分簇為基礎的路由協(xié)議在無線傳感器網絡中已得到了廣泛的應用,是目前路由協(xié)議研究的熱點,其優(yōu)點是具有自適應性、節(jié)能性、消除健壯性和擴展性等。本文對當前的分簇路由協(xié)議進行分類、分析,剖析典型分簇路由協(xié)議的設計思想、優(yōu)點及缺點,并從多個性能參數進行比較和總結,目的是為進一步研究作指引和參考。2分簇路由協(xié)議的核心問題是什么?WSN分簇協(xié)議較傳統(tǒng)的無線路由協(xié)議更為復雜,好的分類方法和比較分析有利于研究人員對分簇路由協(xié)議進行研究和改進。分簇路由協(xié)議中簇的結構、大小、數量以及節(jié)點的能耗和網絡生命周期,決定因素是簇頭的產生方法、數量及位置。分簇路由協(xié)議工作過程中最關鍵的核心問題是如何合理選舉簇首節(jié)點、如何快速有效地構建分簇結構、如何節(jié)約能量和延長網絡生命周期。目前研究者已經做了大量的工作[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22],按照簇首節(jié)點的選舉依據與實現機制,分簇路由協(xié)議劃分為3種類型,分別為基于隨機選舉、基于地理位置和基于剩余能量。2.1隨機選舉后的集群協(xié)議該協(xié)議是最簡單的一種選舉簇首方法,網絡隨機地按照一定概率選舉簇首,形成簇結構。典型協(xié)議如下。2.1.1打造網絡實名協(xié)議,控制網絡結構LEACH(low-energyadaptiveclusteringhierarchy)是一個典型自適應分簇協(xié)議,是最早的基于層次結構的路由協(xié)議,其后的大部分協(xié)議是在它的基礎上進行改進及發(fā)展的。該協(xié)議采用分布式算法,使各節(jié)點的任務均等、消耗的能量均衡,很好地減輕了節(jié)點的負載,達到了延長整個網絡運行時間的目的。運行機理是采用“輪”循的方式隨機選取簇首,每一輪由簇的建立和數據傳輸兩個階段組成。選舉簇首時,每個節(jié)點都產生一個之間的隨機數,并且按照當前輪數計算出一個門限值,當隨機數小于該門限值時,該節(jié)點就被選為簇首。隨后,簇首向全網廣播消息,讓其余節(jié)點加入到與之最近的簇,簇成員按TDMA時隙采集數據并發(fā)送給簇首,簇首融合數據后報告給sink節(jié)點。這樣不停地輪循工作。協(xié)議的關鍵是門限值計算,公式為:式中,p為簇首數占總節(jié)點數的百分比;S為最近1/p輪中未當選過簇首的節(jié)點的集合;r為當前輪數。優(yōu)點:1)簇首的選舉用“輪”循的方式和分布式算法,使得各節(jié)點機會均等,能量消耗均衡,有效避免了簇首過快消耗能量,達到了延長網絡運行時間的目的;2)數據融合因在簇內完成,減少了傳輸距離,節(jié)省了能量。缺點:1)每一輪都進行一次簇重組,選舉簇首的開銷量比較大;2)在整個網絡中,簇首的分布不太均勻,且簇內的成員節(jié)點也不均勻,簇首間負載不均衡,造成有的簇首早死亡有的被閑置;3)簇內各成員節(jié)點因直接和簇首傳遞信息,加速了簇首的能量消耗,降低了網絡的生存壽命,也造成了每個簇的規(guī)模有限,網絡的擴展性不強,不適用于大型網絡。針對這個典型協(xié)議的缺點,改進措施是在簇首選舉過程中,分兩個步驟進行:1)上一輪剩余能量多的節(jié)點作為下一輪候選簇首;2)設計一個隨機數和閾值,根據這兩個參數選舉候選簇首,然后,該節(jié)點向簇內各節(jié)點進行廣播自己的信息,再根據候選簇首的剩余能量和個數決定成為簇首,這樣保證了網絡的穩(wěn)定性和低功耗。2.1.2letch協(xié)議ERC(ERPefficientroutingprotocol)主要適合于大規(guī)模無線網絡中,在分簇算法中引入了智能算法。該算法采用兩層路由,在第一層中采用LEACH協(xié)議的分布式算法,也是采用隨機選舉簇首,簇成員直接將數據傳遞給它們的簇首;在第二層中,這些簇首用蟻群優(yōu)化算法,找最佳的路徑去感知、采集和處理各節(jié)點的數據。優(yōu)點:1)協(xié)議采用雙層路由,爭強了網絡結構的穩(wěn)定性;2)簇內采用蟻群優(yōu)化算法,減少了網絡時延。缺點:1)隨機選舉簇頭造成簇首分布不均勻;2)每一輪都進行一次簇重組,簇頭的開銷量較大?？傊?此類協(xié)議,因隨機選舉簇首,使得簇首節(jié)點分布不均衡,造成節(jié)點能量的消耗差異性很明顯,對整個網絡的壽命很不利。2.2基于剩余能量的集群協(xié)議簇首節(jié)點的選舉,主要是依據每個候選節(jié)點的剩余能量而定,剩余能量值大的被選為簇首節(jié)點。典型的協(xié)議如下。2.2.1多跳+letchHEED(hybridenergy-efficientdistributedclustering)協(xié)議在選舉簇首時,依據主、次參數進行選舉,主參數的選取主要依賴于節(jié)點的剩余能量。初始時隨機選舉出簇首節(jié)點,剩余能量多的節(jié)點成為簇首節(jié)點的概率最大,能否成為簇首要看該節(jié)點比周圍節(jié)點的能量大多少而定。而次參數依賴于簇內通信代價,主要是平衡簇首間的負載,確定節(jié)點屬于的簇。HEED協(xié)議與LEACH協(xié)議類似,均采用“輪”循方法選舉簇首,簇成員按TDMA時隙采集數據并發(fā)送給簇首,帶來了簇間干擾問題。HEED協(xié)議通過多跳方式與基站通信,而LEACH協(xié)議采用單跳方式與基站通信。優(yōu)點:1)簇首的分布均勻,分簇效率更快,網絡結構更加合理;2)簇首的選舉主要依賴于剩余能量,并以主次參數引入多個約束條件,很好地控制了報文開銷。缺點:1)每一輪都進行一次簇重組,簇首的開銷量比較大;2)因形成簇的覆蓋區(qū)域有重疊,存在嚴重的簇間干擾,為了解決這個問題,文獻提出DCHS協(xié)議算法,該協(xié)議減少因簇間干擾導致的數據碰撞。2.2.2無區(qū)分區(qū)分節(jié)點間競爭半徑和網絡能量EEUC(energy-efficientunevenclustering)協(xié)議簇首的選舉也是依賴于剩余能量,為解決均勻分簇協(xié)議,在轉發(fā)遠距離sink的簇首消耗較大的能量,導致過早耗盡能量而死亡的問題。為了解決簇首將節(jié)約的能量供簇間轉發(fā)數據時使用,該協(xié)議采用非均勻的競爭機制規(guī)劃大小不等的簇,而靠近sink的簇內成員較少,具有競爭半徑小的特點,因此該協(xié)議關鍵點是簇半徑的計算,其計算公式為:式中,R0是候選簇首競爭半徑的最大值;c在之間,是簇半徑控制參數;dmax和dmin分別表示節(jié)點到sink距離的最大值和最小值;d表示簇首i到sink的距離。優(yōu)點:1)簇首的選舉考慮了能量消耗不平衡的問題,提高了網絡生存時間;2)簇間選用多跳通信,節(jié)約了網絡流量。缺點:1)簇的生成過程復雜,代價較大;2)因與sink距離不同的簇具有不同的簇半徑,所以,傳輸數據和采集數據的精確度有很大的差異和誤差產生。2.2.3第4輪機制的優(yōu)缺點EBLP(energybalancedcluster-basedroutingprotocol)協(xié)議針對LEACH協(xié)議的缺點,結合PEGASIS協(xié)議優(yōu)點,提出一種能量均衡的分簇路由協(xié)議。基本思想是網絡運行采用“輪”機制,每輪進行簇首選擇和數據傳輸,每隔一定時間周期性地進行一次簇的重組。在簇首選舉時,先要計算出最優(yōu)簇首數,并根據網絡的范圍確定每個簇首間的最短距離,然后根據剩余能量確定初始簇首;建立簇時,簇首采用貪心算法將簇成員節(jié)點形成鏈式結構,簇首控制簇內成員節(jié)點數,使整個簇結構合理和最優(yōu);簇首負責構建一個層次結構的路由樹,選擇最佳路由將采集、融合到的數據傳給基站;數據傳輸時,每周期第一輪用初始選舉的簇首傳遞數據,簇首的選舉根據剩余能量多的而定,這樣不停地輪詢進行簇首的更新和重組。優(yōu)點:1)因結合能量均衡和最優(yōu)分布,網絡的生命周期延長,能耗降低;2)簇首選舉合理,建簇路由最優(yōu),數據傳輸速度快。缺點:1)延遲方面還要進一步改進;2)沒有考慮安全因素。2.2.4節(jié)點k-dijpstor算法EQR(energy-awareQoSrouting)協(xié)議簇首的選舉,是依據剩余能量、整個鏈路的誤碼率和簇首到鄰節(jié)點的距離3個條件來計算出整個鏈路的開銷,用分類排隊模型,將節(jié)點設置成兩種隊列,即非實時隊列和實時隊列,用k-Dijkstra算法找出k條開銷小的路徑,將數據端到端的傳輸。優(yōu)點:1)最大化地提高了網絡的吞吐量,達到了實時業(yè)務的QoS要求;2)采用k-Dijkstra算法使開銷的計算更加準確,簇首的選擇更加合理。缺點:1)因采用集中式路由策略,使節(jié)點保留了整個網絡的信息,不適合大型網絡;2)各節(jié)點帶寬一樣,導致負載均衡差;3)開銷的計算量大,花銷值大。總之,此類協(xié)議能確保簇首節(jié)點最優(yōu)、最佳地獲得能量,來承擔數據采集和數據轉發(fā)工作。但簇首間的路由相對復雜,也很難保證簇首節(jié)點的合理分布和均衡性。2.3基于地理的集群協(xié)議在選舉簇首節(jié)點時主要依據地理位置信息,典型協(xié)議如下。2.3.1節(jié)點傳輸方法PEGASIS(power-efficientgatheringinsensorinformationsystems)協(xié)議借鑒了LEACH的思想,通過貪心算法將網絡中的節(jié)點利用定位技術串成基于地理位置的一條鏈,簇首也是周期性選舉,節(jié)點只與距離它最近的鄰居節(jié)點通信,采用令牌進行數據傳輸,鄰節(jié)點將收到的數據連同自己的數據一起進行融合處理,然后傳輸給下一個節(jié)點,依次傳輸到目的節(jié)點,簇首負責將最后融合的數據傳輸給基站。優(yōu)點:1)基于地理位置,使節(jié)點平均通信距離較短,減少了成簇開銷;2)采用令牌,確保數據傳輸的可靠性;3)采用數據融合,減少了數據分送次數,降低了能量消耗。缺點:1)因節(jié)點基于地理位置,形成一條鏈,數據傳輸時的延長比較大;2)簇首的選舉基本是均勻的,導致簇間干擾大、開銷大。2.3.2距離節(jié)點數據傳輸在TTDD(two-tierdatadissemination)協(xié)議中,簇首的選舉是由數據源節(jié)點的地理位置而定,簇首由距離發(fā)送數據最近的節(jié)點承擔,該協(xié)議主要是為了解決匯聚節(jié)點頻繁移動情況下的數據傳遞問題。協(xié)議工作過程由網格構建階段、查詢發(fā)送節(jié)點和數據傳輸3個階段組成。優(yōu)點:1)解決了匯聚節(jié)點頻繁移動的問題;2)基于地理位置,使得節(jié)點平均通信距離較短。缺點:1)在快速移動的監(jiān)測目標時,數據延遲大,數據采集的實時性較差;2)數據源太多,網絡的構建重復比較大,開銷太大。2.3.3節(jié)點位置和距離閾值LACA(locationawareclusteringalgorithm)是針對LEACH協(xié)議的缺點,提出的一種基于地理位置感知的分簇協(xié)議。該協(xié)議引入角度比和距離比兩個感知參數,使節(jié)點通過其所在的位置自主地決定是否作為簇首。主要是計算出節(jié)點間的距離和連線與水平線之間的夾角,角度、角度比和距離比的計算公式分別為式中,R為通信距離;Nx和Ny分別為節(jié)點N的橫縱坐標;Mx和My分別為節(jié)點M的橫縱坐標。通過上述公式,就可以確定節(jié)點偏離理想簇首位置的程度。簇首的選舉主要根據角度比n和距離比uf064而定,所以,合理設置角度和距離的閾值是非常重要的,這樣才能構建理想的分簇結構,保證能量的有效性和網絡的可靠性。優(yōu)點:1)能量有效性高、網絡壽命長、網絡能量和負載均衡性好;2)無需構建網絡拓撲結構,路由表的建立、維護和存儲實現簡單。缺點:1)協(xié)議有局限性,可擴展性較差;2)協(xié)議根據網絡規(guī)模自適應地改變角度比和距離比閾值差。2.3.4節(jié)點間通信優(yōu)化GAF(geographicadaptivefidelity)協(xié)議是根據地理而選擇路由的算法,所有節(jié)點通過GPS定位獲知自己的“位置”,把所有這樣的“位置”連接起來就形成了一個虛擬網絡。在網絡中,根據節(jié)點“位置”是否相同來決定節(jié)點是否工作。如兩個節(jié)點“位置”相同,則看作是等價路由,這樣的節(jié)點只需其中之一工作,剩下的節(jié)點就進入到休眠狀態(tài),這樣大大節(jié)約了能量。優(yōu)點:1)節(jié)點定位比較準確,節(jié)能性好;2)無需建立、維護和存儲路由表,無需網絡拓撲信息,實現簡單。缺點:1)算法只考慮了地理位置的平面關系,而沒有考慮實際網絡中節(jié)點通信與節(jié)點間的距離沒有關系的問題,因為,實際網絡應該是邏輯的而與物理位置無關;2)硬件要求高,適用性差。總之,此類協(xié)議的簇首節(jié)點分布合理,路由間通信簡單,但沒有考慮到節(jié)點的剩余能量,可能會存在新當選的簇首節(jié)點因能量不夠而無法勝任數據轉發(fā)任務的情況。還有,簇中的節(jié)點如想工作必須要定位好自身的地理位置,這樣會增加系統(tǒng)的負擔,所以適用于需要地理信息的應用。3當前wsn路由協(xié)議性能分析綜上所述,本文總結、分析了3類目前典型的分簇路由協(xié)議的運行機理、優(yōu)缺點。在已有的算法中,HEED、EBLP、GAF節(jié)能性較好;LEACH、HEED、ERC因采用分布式算法,擴展性、能量有效性和收斂性較好,但算法健壯性較差。綜合影響協(xié)議的多個因素,對典型的分簇路由協(xié)議進行綜合對比,如表1所示。表中,A為協(xié)議類型;B為簇頭產生速度;C為數據融合;D為簇負載平衡性;E為簇形成速度;F為簇維護開銷;G為健壯性;H為擴展性;I為算法節(jié)能性;J為延遲;K為控制方式;“…”表示當前該參數不清楚。從表1中發(fā)現,現有的WSN路由協(xié)議在節(jié)能、數據融合、收斂速度等方面都有很多優(yōu)勢,但僅僅是體現在某一個