無線傳感器網(wǎng)絡(luò)簇類路由協(xié)議的研究

1、無線傳感器網(wǎng)絡(luò)簇類路由協(xié)議的研究李夢(mèng)娥，張登銀 (1南京郵電大學(xué)計(jì)算機(jī)學(xué)院，江蘇省南京市210003；2南京郵電大學(xué)信號(hào)處理與傳輸研究院，江蘇省南京市210003)0引言WSN(無線傳感器網(wǎng)絡(luò))由部署在監(jiān)測(cè)區(qū)域內(nèi)的大量廉價(jià)的微型傳感器節(jié)點(diǎn)組成，通過無線通信方式形成一個(gè)多跳、自組織的網(wǎng)絡(luò)系統(tǒng)，其目的是協(xié)作地感知、采集和處理網(wǎng)絡(luò)覆蓋區(qū)域中感知對(duì)象的信息，并發(fā)送給觀察者。WSN的隨機(jī)布設(shè)、自組織、環(huán)境適應(yīng)等特點(diǎn)使其在軍事國防、工農(nóng)業(yè)、城市管理、生物醫(yī)療、環(huán)境監(jiān)測(cè)、搶險(xiǎn)救災(zāi)、防恐反恐、危險(xiǎn)區(qū)域遠(yuǎn)程控制等領(lǐng)域具有廣闊的應(yīng)用前景和很高的應(yīng)用價(jià)值。而源于WSN自身的特點(diǎn)，路由協(xié)議成為其研究的重點(diǎn)之一。目前，

2、已有很多路由協(xié)議，其目的是要節(jié)省系統(tǒng)的能量，延長系統(tǒng)的生命周期，提高系統(tǒng)的性能。主要有平面路由協(xié)議和層次路由協(xié)議。層次路由協(xié)議的基本思想是選取一些節(jié)點(diǎn)負(fù)責(zé)某個(gè)區(qū)域的路由，相對(duì)于其他節(jié)點(diǎn)具有更大的責(zé)任，而節(jié)點(diǎn)之間不是完全平等的關(guān)系。簇類協(xié)議具有良好的節(jié)能效果和可擴(kuò)展性。具有代表性的、成熟的路由協(xié)議主要有：LEACH(Low-Energy Adaptive Clustering Hierarchy)、TEEN(Thresholdsensitive Energy Efficient sensor Network protocol)、PE-GASIS (Power-Efficient Gatherin

3、g in Sensor InformationSystems)，以及在此基礎(chǔ)上改進(jìn)的協(xié)議。1 LEACH類協(xié)議1.1 LEACH協(xié)議LEACH的基本思想是將整個(gè)網(wǎng)絡(luò)劃分為不同的簇，簇類節(jié)點(diǎn)的數(shù)據(jù)發(fā)送和接收由簇頭負(fù)責(zé)，簇頭節(jié)點(diǎn)以循環(huán)的方式隨機(jī)選擇。LEACH定義了輪的概念，LEACH的運(yùn)行過程就是輪不斷循環(huán)的過程。每個(gè)輪分成兩個(gè)階段：簇的建立階段和傳輸數(shù)據(jù)的穩(wěn)定階段。在簇的建立階段，相鄰節(jié)點(diǎn)動(dòng)態(tài)地形成簇，隨機(jī)產(chǎn)生簇頭；在數(shù)據(jù)通信階段，簇內(nèi)節(jié)點(diǎn)把數(shù)據(jù)發(fā)給簇頭，簇頭進(jìn)行數(shù)據(jù)融合后把結(jié)果發(fā)送給基站。其中，簇的建立過程又可以分成4個(gè)階段：簇首節(jié)點(diǎn)的選擇、簇首節(jié)點(diǎn)的廣播、簇的建立和調(diào)度機(jī)制的生成。關(guān)于簇頭

4、選擇的算法，LEACH采用分布式。選擇簇頭的具體做法是：在每一個(gè)回合即輪的第1階段，傳感器節(jié)點(diǎn)隨機(jī)的選擇01之間的一個(gè)數(shù)值，如果這個(gè)數(shù)值小于某一個(gè)閾值T(n)，那么這個(gè)節(jié)點(diǎn)就被選為簇頭節(jié)點(diǎn)。節(jié)點(diǎn)n的閾值T(n)的計(jì)算公式如下：式中：N為網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)的總數(shù)；k為一輪網(wǎng)絡(luò)中的簇頭節(jié)點(diǎn)數(shù)；r為已完成的輪數(shù)；G為在剩余的r輪中未成為簇頭節(jié)點(diǎn)的傳感器節(jié)點(diǎn)的集合。LEACH這種簇首隨機(jī)選擇機(jī)制的優(yōu)點(diǎn)在于，通過把網(wǎng)絡(luò)的負(fù)載均勻地分布在整個(gè)網(wǎng)絡(luò)上，很大程度上節(jié)約了通信過程中的能量損耗。每一輪中，由不同的節(jié)點(diǎn)充當(dāng)簇頭，從而網(wǎng)絡(luò)中的節(jié)點(diǎn)都有機(jī)會(huì)來擔(dān)當(dāng)遠(yuǎn)距離通信的任務(wù)。而且，簇頭節(jié)點(diǎn)在把簇內(nèi)節(jié)點(diǎn)發(fā)送來的數(shù)據(jù)傳送

5、給BS(基站)之前，先進(jìn)行數(shù)據(jù)融合與壓縮，進(jìn)而減少數(shù)據(jù)的傳輸量，節(jié)省了能量。LEACH實(shí)現(xiàn)起來相對(duì)簡單，操作也比較靈活。LEACH的不足在于，每輪進(jìn)行選擇簇頭并劃分簇，并且簇頭需要一直處于醒著的狀態(tài)以接收數(shù)據(jù)，這樣系統(tǒng)開銷較大，離散式區(qū)域算法雖然對(duì)節(jié)點(diǎn)位置等要求不高，但無法確定最優(yōu)的簇?cái)?shù)目。LEACH采用TDMA的MAC層機(jī)制，而事實(shí)上，在分配給節(jié)點(diǎn)的每個(gè)時(shí)隙，節(jié)點(diǎn)并不是都有數(shù)據(jù)要發(fā)送給簇頭，這樣的通信機(jī)制不能有效利用帶寬，浪費(fèi)了能量。LEACH還要求節(jié)點(diǎn)之間以及節(jié)點(diǎn)與sink之間都可以直接通信，因此局限了網(wǎng)絡(luò)的可擴(kuò)展性，不適用于大型的網(wǎng)絡(luò)。1.2 LEACH-EE協(xié)議高效聚類路由算法LEAC

6、H-EE是在LEACH基礎(chǔ)上改進(jìn)的，不同于LEACH的單跳路徑選擇模式，而LEACH-EE是簇頭間多跳路徑選擇模式。LEACH-EE的基本思想大部分繼承了LEACH的模式，協(xié)議的運(yùn)行過程就是簇不斷循環(huán)重構(gòu)的過程，每一輪也分為簇的建立階段和傳輸數(shù)據(jù)的穩(wěn)定階段，簇的建立階段也分為4個(gè)階段：簇首節(jié)點(diǎn)的選擇、簇首節(jié)點(diǎn)的廣播、簇的建立和調(diào)度機(jī)制的生成。與LEACH不同的是在簇首節(jié)點(diǎn)廣播的階段和傳輸數(shù)據(jù)的穩(wěn)定階段。在簇首節(jié)點(diǎn)的廣播階段，每個(gè)簇頭節(jié)點(diǎn)需要計(jì)算出自己與其他簇頭之間的距離，以及自己與sink之間的距離；在傳輸數(shù)據(jù)的穩(wěn)定階段，由sink發(fā)起，遍歷所有的簇頭節(jié)點(diǎn)，尋找與sink路徑最短的簇頭，找到后

7、，再尋找與這個(gè)簇頭路徑最短的下一個(gè)簇頭，以此類推，直到所有的簇頭節(jié)點(diǎn)遍歷完了，建立一條通往sink的最短路徑，數(shù)據(jù)就可以由這條路徑融合并經(jīng)多跳發(fā)送給sink。LEACH-EE的這種多跳路由模式把能量消耗均勻地分擔(dān)到每個(gè)節(jié)點(diǎn)，網(wǎng)絡(luò)的壽命延長，而且就算Bs與檢測(cè)距離變大，也不會(huì)使得離BS遠(yuǎn)的節(jié)點(diǎn)迅速死亡。而LEACH中離sink較遠(yuǎn)的節(jié)點(diǎn)因?yàn)檫h(yuǎn)距離單跳傳輸數(shù)據(jù)，能量消耗比較多，相對(duì)容易過早地死亡。這一點(diǎn)，LEACH-EE要優(yōu)于LEACH。LEACH-EE也有不足，在簇首節(jié)點(diǎn)的廣播階段和數(shù)據(jù)傳輸階段的簇頭之間距離的計(jì)算和最短路徑的計(jì)算都需要消耗節(jié)點(diǎn)的能量和時(shí)間，增加了每個(gè)節(jié)點(diǎn)的開銷，也沒有考慮到簇頭

8、節(jié)點(diǎn)維護(hù)的開銷，這一點(diǎn)不利于網(wǎng)絡(luò)的負(fù)載平衡。1.3 DEEAC協(xié)議DEEAC是與LEACH類似的分布式能量有效的成簇算法。與LEACH不同的在于DEEAC的簇頭選擇方式上，其數(shù)據(jù)傳輸過程相同。DEEAC的做法是：網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)根據(jù)某個(gè)閾值自主判斷自己是否成為臨時(shí)簇首，這個(gè)閾值由網(wǎng)絡(luò)所決定的最優(yōu)簇首概率Popt確定，然后，臨時(shí)簇首負(fù)責(zé)收集簇內(nèi)節(jié)點(diǎn)的信息，根據(jù)簇內(nèi)通信總能耗最小化原則，選擇一個(gè)使得每一輪簇內(nèi)通信能量消耗最小的節(jié)點(diǎn)作為真正的簇首。臨時(shí)簇首判斷簇類通信總能耗最小，是根據(jù)簇內(nèi)節(jié)點(diǎn)和BS的距離，而簇內(nèi)節(jié)點(diǎn)與BS的距離的計(jì)算，通過在網(wǎng)絡(luò)配置階段，BS向全網(wǎng)廣播的消息hello。臨時(shí)簇首選擇

9、中，節(jié)點(diǎn)si隨機(jī)選擇01之間的一個(gè)值，該值若小于節(jié)點(diǎn)的閾值T(si)，那么這個(gè)節(jié)點(diǎn)就成為臨時(shí)簇首節(jié)點(diǎn)。T(si)計(jì)算公式如下： 式中：r為當(dāng)前的輪數(shù)；G為在最近r mod(1Popt)輪中沒有成為簇首的節(jié)點(diǎn)的集合。DEEAC算法不是通過優(yōu)化LEACH算法達(dá)到網(wǎng)絡(luò)內(nèi)能耗盡可能均勻分布的目標(biāo)，而是通過優(yōu)化LEACH隨機(jī)生成的簇結(jié)構(gòu)來減少每一輪的能量消耗，進(jìn)而不僅使網(wǎng)絡(luò)能耗均勻分布，而且延長網(wǎng)絡(luò)的整體壽命。1.4 LEACH-NEW協(xié)議LEACH-NEW的做法是：基站在距離r內(nèi)廣播查詢消息(NFO)，統(tǒng)計(jì)距離r范圍內(nèi)的傳感器節(jié)點(diǎn)數(shù)，并在這些節(jié)點(diǎn)中選擇簇首，其中r是每個(gè)傳感器節(jié)點(diǎn)的發(fā)射距離。每個(gè)簇頭允

10、許簇內(nèi)最大的跳數(shù)由某個(gè)計(jì)算值k確定。簇的建立過程是：當(dāng)距離基站r范圍內(nèi)的簇頭確定后，簇頭廣播自己的D和k，那些接收到廣播信息的節(jié)點(diǎn)將k減去1，并選擇加入到k0的最近的簇頭節(jié)點(diǎn)中，并不加入到k為0的節(jié)點(diǎn)，如此繼續(xù)廣播。而最終那些既沒有收到廣播信息又不是簇頭的節(jié)點(diǎn)，過一段時(shí)間后，自選為簇頭，稱為被迫簇頭。若在協(xié)議運(yùn)行過程中，某些中間節(jié)點(diǎn)死亡，那么在下一輪的路由選擇中，已經(jīng)死亡的節(jié)點(diǎn)就不再加入任何簇內(nèi)。LEACH-NEW簇的建立過程是在簇內(nèi)節(jié)點(diǎn)到簇頭之間形成了多跳路由。而后的過程與LEACH相似。LEACH-NEW只在距離BS為r的范圍內(nèi)選擇簇首，因此，信息可以經(jīng)簇頭直接發(fā)送至BS，避免了節(jié)點(diǎn)離BS

11、的距離近于節(jié)點(diǎn)離簇頭的距離，從而節(jié)省了能量。實(shí)驗(yàn)仿真證明LEACH-NEW比LEACH更延長了網(wǎng)絡(luò)壽命。但是，LEACH-NEW只在距離BS為r的范圍內(nèi)選擇簇首，這一點(diǎn)并不適用于大型傳感器網(wǎng)絡(luò)。1.5 LEACH-C協(xié)議LEACH-C是一種集中式的簇首選擇機(jī)制，不同于LEACH分布式隨機(jī)選擇簇頭的方式，它要求只有能量高于網(wǎng)絡(luò)平均剩余能量的節(jié)點(diǎn)才有可能被選為簇首。LEACH-C通過每個(gè)節(jié)點(diǎn)與BS直接通信以匯報(bào)自己的位置和能量信息的方式，來評(píng)估網(wǎng)絡(luò)剩余能量的平均值和優(yōu)化簇首的選擇。BS根據(jù)各節(jié)點(diǎn)發(fā)送來的信息選擇簇頭，這樣使得每個(gè)區(qū)域內(nèi)的節(jié)點(diǎn)數(shù)大致相同，實(shí)現(xiàn)負(fù)載均衡，因而LEACH-C的性能要優(yōu)于L

12、EACH。顯然，這個(gè)過程需要消耗較多的通信能量，但卻延長了網(wǎng)絡(luò)第1個(gè)節(jié)點(diǎn)死亡的時(shí)間。2 TEEN協(xié)議LEACH是響應(yīng)型傳感器網(wǎng)絡(luò)，而TEEN是主動(dòng)型傳感器網(wǎng)絡(luò)。所謂主動(dòng)型傳感器網(wǎng)絡(luò)，它持續(xù)監(jiān)測(cè)周圍的物質(zhì)現(xiàn)象，并以恒定速率發(fā)送監(jiān)測(cè)數(shù)據(jù)。所謂響應(yīng)型傳感器網(wǎng)絡(luò)，只在被觀測(cè)變量發(fā)生突變時(shí)才傳送數(shù)據(jù)。后者更適合應(yīng)用在對(duì)時(shí)問敏感的場(chǎng)合中。TEEN的基本思想是設(shè)置硬、軟閾值以減少數(shù)據(jù)的傳輸量。硬、軟閾值在每次簇頭輪換時(shí)廣播出去，節(jié)點(diǎn)監(jiān)測(cè)到的數(shù)據(jù)第1次超過設(shè)置的硬閾值時(shí)，就把這次數(shù)據(jù)設(shè)為新的硬閾值，并在下一個(gè)時(shí)隙發(fā)送給簇頭。然后在下面的過程中，只有當(dāng)監(jiān)測(cè)到的數(shù)據(jù)超過硬閾值并且監(jiān)測(cè)數(shù)據(jù)的變化幅度大于軟閾值時(shí)，節(jié)

13、點(diǎn)才會(huì)傳送最新的監(jiān)測(cè)數(shù)據(jù)，并將它設(shè)為新的硬閾值。 TEEN根據(jù)硬、軟兩個(gè)閾值來確定是否傳送數(shù)據(jù)，傳送的數(shù)據(jù)量要比主動(dòng)網(wǎng)絡(luò)少得多，所以節(jié)點(diǎn)因傳送數(shù)據(jù)消耗的能量也減少。仿真結(jié)果也表明，TEEN在平均能量消耗和存活的總節(jié)點(diǎn)數(shù)這兩個(gè)性能方面要優(yōu)于LEACH。TEEN存在的問題是：一方面，如果節(jié)點(diǎn)監(jiān)測(cè)的數(shù)據(jù)一直不能超過設(shè)定的硬閾值，節(jié)點(diǎn)就不會(huì)傳送數(shù)據(jù)，用戶將無法得到任何數(shù)據(jù)，也不知道這個(gè)節(jié)點(diǎn)是否失效了；另一方面，節(jié)點(diǎn)監(jiān)測(cè)到合適的數(shù)據(jù)會(huì)實(shí)時(shí)傳送數(shù)據(jù)，采用TDMA的機(jī)制會(huì)造成數(shù)據(jù)延遲。3 PEGASIS協(xié)議PEGASIS并不是非常嚴(yán)格的簇類協(xié)議，卻延用了簇的思想。PEGASIS的基本思想是：節(jié)點(diǎn)通過定位裝置

14、或者通過發(fā)送能量遞減的測(cè)試信號(hào)來發(fā)現(xiàn)距自己最近的鄰居節(jié)點(diǎn)，然后從距基站最遠(yuǎn)的節(jié)點(diǎn)開始，采用貪婪算法來構(gòu)造一條鏈，這條基于地理位置的鏈就是PEGASIS中的簇。鏈上的相鄰節(jié)點(diǎn)是地理位置上距離最短的兩個(gè)鄰居節(jié)點(diǎn)，前提是假設(shè)這些節(jié)點(diǎn)都是靜止的。PEGASIS中的數(shù)據(jù)傳輸使用令牌(Token)機(jī)制：簇頭產(chǎn)生一個(gè)令牌，發(fā)送到鏈的一端，通知末梢節(jié)點(diǎn)開始傳輸數(shù)據(jù)，簇頭與末梢之間的每個(gè)節(jié)點(diǎn)接收到數(shù)據(jù)之后，先與自己采集的數(shù)據(jù)進(jìn)行融合處理，再向下一個(gè)節(jié)點(diǎn)轉(zhuǎn)發(fā)，直至數(shù)據(jù)傳輸?shù)酱仡^，簇頭受到一側(cè)的數(shù)據(jù)后再將令牌發(fā)送到鏈的另一端，開始同樣的過程。簇接收到兩側(cè)傳送來的數(shù)據(jù)后再發(fā)送給BS。PEGASIS中的數(shù)據(jù)在距離最短的

15、相鄰節(jié)點(diǎn)之間傳輸，因而節(jié)點(diǎn)只以最小功率發(fā)送數(shù)據(jù)分組，在每個(gè)中間節(jié)點(diǎn)還進(jìn)行了數(shù)據(jù)融合，這樣減少了業(yè)務(wù)流量，整個(gè)網(wǎng)絡(luò)的功耗也就減少了。而事實(shí)上，研究結(jié)果也表明，使用PEGASIS的傳感器網(wǎng)絡(luò)的生命周期是使用LEACH的網(wǎng)絡(luò)的近2倍。PEGASIS采用令牌方式傳送數(shù)據(jù)，先在簇的一側(cè)融合數(shù)據(jù)，再在另一側(cè)融合數(shù)據(jù)，這樣卻增加了延遲。4比較與研究以上介紹的各種WSN中分簇的路由算法，有的優(yōu)化簇頭的產(chǎn)生，有的優(yōu)化簇內(nèi)的拓?fù)浣Y(jié)構(gòu)，有的優(yōu)化簇的數(shù)據(jù)傳輸。表1中，對(duì)具有代表性的簇類協(xié)議LEACH、TEEN、PEGASIS，從幾個(gè)性能標(biāo)準(zhǔn)方面進(jìn)行比較。LEACH、LEACH-EE、DEEAC、LEACH-NEW、P

16、EGASIS都是分布式成簇算法。所謂分布式算法，是指通過節(jié)點(diǎn)之間的信息交互和反饋成簇，而在實(shí)際應(yīng)用中，WSN的傳感器節(jié)點(diǎn)是隨機(jī)分布、不完全均勻的，而這種基于局部信息成簇的方式容易導(dǎo)致網(wǎng)絡(luò)負(fù)載整體不均勻，造成局部網(wǎng)絡(luò)負(fù)載過重。但是，這種分布式算法有較好的擴(kuò)展性、較快的收斂速度和能量的高效性。相對(duì)于分布式成簇算法，LEACH-C是集中式成簇方式。集中式算法基于全局信息由基站選擇簇頭，因而生成的簇比較均衡，避免了分布式算法的不均衡的缺陷，而且集中式算法的健壯性也比較好。但是，LEACH-C中的節(jié)點(diǎn)必須周期性地向BS匯報(bào)它們的能量和位置信息，能量開銷比較大，擴(kuò)展性也不好，一般只適合中小型網(wǎng)絡(luò)。LEACH、TEEN、DEEAC是單跳路由模式，數(shù)據(jù)在TDMA分配的時(shí)隙內(nèi)發(fā)送數(shù)據(jù)，其他時(shí)候節(jié)點(diǎn)關(guān)閉它的通信模塊以節(jié)省能量。LEACH-EE