無線傳感器網(wǎng)絡(luò)低功耗分簇路由算法研究

引 言
    無線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks，WSN)是由一組微型傳感器節(jié)點(diǎn)以自組織方式構(gòu)成的無線網(wǎng)絡(luò)，其目的是協(xié)作地感知、采集和處理網(wǎng)絡(luò)覆蓋的地理區(qū)域中感知對(duì)象的信息，并發(fā)布給觀察者。近年來，隨著通信技術(shù)、嵌入式計(jì)算技術(shù)和傳感器技術(shù)的飛速發(fā)展和日益成熟，傳感器網(wǎng)絡(luò)的應(yīng)用越來越廣泛。在無線傳感器網(wǎng)絡(luò)中，除了少數(shù)節(jié)點(diǎn)需要移動(dòng)以外，大部分節(jié)點(diǎn)都是靜止的。它們通常運(yùn)行在人無法接近的惡劣甚至危險(xiǎn)的遠(yuǎn)程環(huán)境中，能源補(bǔ)充非常困難，因此，設(shè)計(jì)有效的協(xié)議和算法以延長(zhǎng)網(wǎng)絡(luò)的生命周期是WSN的核心問題之一。

1 相關(guān)研究
    針對(duì)無線傳感器網(wǎng)絡(luò)能量受限的特點(diǎn)，對(duì)適應(yīng)其特點(diǎn)的低功耗算法研究也一直繼續(xù)著。Heinzelman提出了LEACH(Low—Energy Adaptive Clustering Hierarchy，低能耗自適應(yīng)分簇層次)算法。其核心思想是讓每個(gè)節(jié)點(diǎn)輪流擔(dān)當(dāng)簇首，從而使得網(wǎng)絡(luò)中的能量消耗盡可能均勻，減少網(wǎng)絡(luò)失效時(shí)刻的能量浪費(fèi)。LEACH算法只考慮了單跳模型，因此只適合于小型wSN網(wǎng)絡(luò)。參考文獻(xiàn)提出了M—LEACH(Multi—hop variant of LEACH，多跳LEACH)算法，簇內(nèi)的節(jié)點(diǎn)不是以單跳的方式傳輸數(shù)據(jù)到簇首，而是通過簇內(nèi)其他節(jié)點(diǎn)轉(zhuǎn)發(fā)。參考文獻(xiàn)提出了一個(gè)多跳簇首模型，采用從下到上的策略，逐層生成每一層的簇首，最終得到一個(gè)多層結(jié)構(gòu)的WSN網(wǎng)絡(luò)。參考文獻(xiàn)采用基于代價(jià)的目標(biāo)函數(shù)對(duì)傳感器網(wǎng)絡(luò)設(shè)計(jì)進(jìn)行了分析，推導(dǎo)出單跳和多跳的適用范圍，最后提出一種單跳多跳混合的路由算法，以解決網(wǎng)絡(luò)中的“能量熱點(diǎn)”問題。本文在前人研究的基礎(chǔ)上提出一種適合無線傳感器網(wǎng)絡(luò)能量受限特點(diǎn)的低功耗路由算法。

2 網(wǎng)絡(luò)模型
    無線傳感器網(wǎng)絡(luò)是由大量部署在觀測(cè)環(huán)境中的微型、廉價(jià)、低功耗的傳感器節(jié)點(diǎn)，以無線、自組織的方式，通過多跳通信而快速形成的網(wǎng)絡(luò)系統(tǒng)。WSN的典型布撒是通過飛行器撒播、人工埋置和火箭彈射等方式來完成的。圖1給出了傳感器網(wǎng)絡(luò)體系結(jié)構(gòu)一般形式的描述。

    假定傳感器網(wǎng)絡(luò)中的各節(jié)點(diǎn)隨機(jī)均勻分布在一個(gè)方形區(qū)域內(nèi)，并且具有如下性質(zhì)：
    ①惟一的基站部署在網(wǎng)絡(luò)外部較遠(yuǎn)的位置；
    ②每個(gè)節(jié)點(diǎn)有惟一的標(biāo)識(shí)；
    ③傳感器節(jié)點(diǎn)部署后不再移動(dòng)；
    ④所有節(jié)點(diǎn)平等，具有相同的計(jì)算和通信能力；
    ⑤節(jié)點(diǎn)的地理位置信息不可知；
    ⑥發(fā)射節(jié)點(diǎn)與不同距離的接收節(jié)點(diǎn)通信時(shí)，可以調(diào)整發(fā)射功率。

3 算法描述
    本算法采用LEACH算法中“輪”的思想，每一輪工作由2個(gè)階段組成：一是簇的建立階段；二是數(shù)據(jù)傳輸階段。在簇的建立階段，主要完成簇首的選取、簇的生成，以及時(shí)限的分配；在數(shù)據(jù)傳輸階段，主要完成的是各個(gè)傳感器節(jié)點(diǎn)把采集到的數(shù)據(jù)逐層上傳到基站，其中包括必要的數(shù)據(jù)融合、數(shù)據(jù)加密等處理。
3．1 簇的結(jié)構(gòu)及首輪簇首選舉
    在無線傳感器網(wǎng)絡(luò)分簇算法的研究中，大部分都是在網(wǎng)絡(luò)簇的同構(gòu)模型上進(jìn)行研究，例如如何使各個(gè)簇的節(jié)點(diǎn)數(shù)目盡量相同、簇的大小盡量相同，在此基礎(chǔ)上有效地降低能量的消耗。多數(shù)的分簇算法都采用簇首多跳將數(shù)據(jù)傳輸?shù)交荆沟镁嚯x基站較近的節(jié)點(diǎn)不但要收集本簇內(nèi)節(jié)點(diǎn)傳送上來的數(shù)據(jù)，而且同時(shí)要轉(zhuǎn)發(fā)其他比它距離基站遠(yuǎn)的簇首節(jié)點(diǎn)發(fā)送的數(shù)據(jù)，這就使得距離基站較近的節(jié)點(diǎn)要比遠(yuǎn)離基站的簇首節(jié)點(diǎn)消耗更多的能量。如果采用簇結(jié)構(gòu)同構(gòu)的分簇方法，往往距離基站較近的簇首能量消耗要相對(duì)大，導(dǎo)致新一輪的簇首選舉，造成整個(gè)網(wǎng)絡(luò)暫停工作，甚至于節(jié)點(diǎn)早期進(jìn)入死亡階段。為了避免這種情況發(fā)生，本算法初步采用簇大小異構(gòu)的方法，即距離基站遠(yuǎn)的簇結(jié)構(gòu)比距離基站近的簇結(jié)構(gòu)大，來均衡轉(zhuǎn)發(fā)數(shù)據(jù)的能量消耗。
    在網(wǎng)絡(luò)部署階段，基站用一個(gè)給定的發(fā)送功率向網(wǎng)絡(luò)內(nèi)廣播一個(gè)信號(hào)。每個(gè)傳感器節(jié)點(diǎn)在接收到此信號(hào)后，根據(jù)接收信號(hào)的強(qiáng)度計(jì)算它到基站的近似距離。獲得這個(gè)距離，不僅有助于傳感器節(jié)點(diǎn)向基站傳輸數(shù)據(jù)時(shí)選擇合適的發(fā)送功率以降低能量消耗，而且它還是算法構(gòu)造大小非均勻的簇的必需信息之一。非均勻分簇網(wǎng)絡(luò)結(jié)構(gòu)如圖2所示。

    靠近基站的候選簇首的競(jìng)爭(zhēng)半徑應(yīng)該較小。隨著候選簇首到基站距離的減小，其競(jìng)爭(zhēng)半徑亦應(yīng)隨之減小。設(shè)候選簇首的競(jìng)爭(zhēng)半徑的最大取值為R0c。其中，c用于控制取值范圍的參數(shù)，在0～1之間取值。候選簇首si確定其競(jìng)爭(zhēng)半徑Rc的計(jì)算公式如下：

   
式中：dmax是距離基站最大的距離；dmin是距離基站最小的距離；d(si，DS)是簇首si到基站DS的距離。
    首輪簇首選舉相對(duì)簡(jiǎn)單。根據(jù)簇首節(jié)點(diǎn)比例在網(wǎng)絡(luò)中選舉出簇首，在競(jìng)爭(zhēng)半徑內(nèi)不允許存在其他簇首，接著競(jìng)選產(chǎn)生的簇首向全網(wǎng)廣播其競(jìng)選獲勝的消息CH_ADV_MSG；普通節(jié)點(diǎn)選擇簇內(nèi)通信代價(jià)最小(即接收信號(hào)強(qiáng)度最大)的簇首，發(fā)送加入消息JOIN_CLUSTER_MSG通知該簇首。
3．2 簇首生成樹的建立及數(shù)據(jù)傳輸
    本文采用簇首多跳數(shù)據(jù)傳輸?shù)姆椒ǎ绾芜x舉下一跳簇首節(jié)點(diǎn)是本部分要重點(diǎn)闡述的問題。首先引入一個(gè)閾值TD_MAX，若簇首到匯聚點(diǎn)的距離小于TD_MAX，則直接與匯聚點(diǎn)進(jìn)行通信；否則，應(yīng)該盡量使用多跳路由的方式將數(shù)據(jù)傳送給匯聚點(diǎn)。
    假設(shè)d(A，DS)>TD_MAX，則在簇首A的臨近簇首集里計(jì)算各個(gè)若簇首，帶來的鏈路質(zhì)量開銷指標(biāo)Erelay=d2(A，X)+d2(X，DS)。其中，d(A，X)是簇首A到簇首X的距離；d(X，DS)是簇首X到基站距離；d(A，DS)是簇首A到基站的距離。在Erelay值小的簇首節(jié)點(diǎn)中選擇剩余能量最大的節(jié)點(diǎn)作為中繼轉(zhuǎn)發(fā)的簇首節(jié)點(diǎn)，將數(shù)據(jù)按照簇首生成樹轉(zhuǎn)發(fā)到基站。
3．3 各輪簇首選舉
    為了延長(zhǎng)網(wǎng)絡(luò)的生命周期，應(yīng)該盡量選擇簇內(nèi)節(jié)點(diǎn)中剩余能量最高的節(jié)點(diǎn)為簇首節(jié)點(diǎn)，并且讓不同的節(jié)點(diǎn)輪轉(zhuǎn)當(dāng)選。本部分采用基于剩余能量的簇首簇內(nèi)輪換的方法進(jìn)行簇首選舉。其主要思想：簇首在簇內(nèi)負(fù)責(zé)收集簇內(nèi)節(jié)點(diǎn)的數(shù)據(jù)。在節(jié)點(diǎn)向簇首發(fā)送數(shù)據(jù)時(shí)，在數(shù)據(jù)位后附加上本節(jié)點(diǎn)的剩余能量值位。簇首將數(shù)據(jù)進(jìn)行處理轉(zhuǎn)發(fā)后，對(duì)各節(jié)點(diǎn)的能量進(jìn)行簡(jiǎn)單的排序，因?yàn)椴挥镁S持所有節(jié)點(diǎn)能量的全排序，只需要知道剩余能量比較高的幾個(gè)節(jié)點(diǎn)，所以采用最大堆的排序方法。在通過數(shù)據(jù)應(yīng)答包或者命令包中附加位的方法把這個(gè)排序中的前3名節(jié)點(diǎn)號(hào)及能量值廣播到整個(gè)簇內(nèi)，這樣做就不會(huì)增加廣播次數(shù)，只是以附帶的方式就可以使整個(gè)簇內(nèi)節(jié)點(diǎn)都有本簇內(nèi)剩余能量較高節(jié)點(diǎn)的信息。即使簇首節(jié)點(diǎn)突然失效或發(fā)生異常，其他的節(jié)點(diǎn)可以很快根據(jù)能量信息選出新簇首。簇內(nèi)節(jié)點(diǎn)保留的都是最近一次的能量信息，由于傳感器網(wǎng)絡(luò)休眠的時(shí)同比較長(zhǎng)，即使簇首突然失效，信息的變化也不會(huì)很大，完全可以根據(jù)這次排序來選舉出新的簇首。新簇首選出后，負(fù)責(zé)完成數(shù)據(jù)收發(fā)處理及能量排序等工作。
    通過本算法每次都選出剩余能量最多的節(jié)點(diǎn)當(dāng)選簇首，使簇內(nèi)信息收集和主干網(wǎng)絡(luò)通信更加穩(wěn)定，并避免了每輪簇首選舉時(shí)所有節(jié)點(diǎn)相互交換能量信息所需的大量開銷。

4 性能分析
    本部分比較各種分簇協(xié)議對(duì)網(wǎng)絡(luò)存活時(shí)間的影響。圖3顯示了網(wǎng)絡(luò)中存活節(jié)點(diǎn)數(shù)目的各輪變化情況。從圖中可以看出，無論是第一個(gè)節(jié)點(diǎn)死亡的時(shí)間還是最后一個(gè)節(jié)點(diǎn)死亡的時(shí)間，本文算法均優(yōu)于其他3種協(xié)議。節(jié)點(diǎn)死亡時(shí)間的跨度可以反映出網(wǎng)絡(luò)中節(jié)點(diǎn)的能量均衡情況，時(shí)間跨度短說明網(wǎng)絡(luò)的能量使用高效。本文算法不僅顯著地延長(zhǎng)了網(wǎng)絡(luò)的生存時(shí)間，而且時(shí)間跨度也小于其他3種協(xié)議，這說明該算法很好地均衡了網(wǎng)絡(luò)中所有節(jié)點(diǎn)的能量消耗。

    通過試驗(yàn)結(jié)果可以看出，本文提出的算法具有如下優(yōu)點(diǎn)：分簇算法穩(wěn)定，所生成簇的簇個(gè)數(shù)不變，能量消耗低，且有效平衡了簇首能量消耗，顯著延長(zhǎng)路網(wǎng)絡(luò)的生存時(shí)間?？傊镁W(wǎng)絡(luò)的生存時(shí)間這一重要指標(biāo)來衡量，其性能顯著優(yōu)于其他3種分簇協(xié)議。

5 總 結(jié)
    本文算法在初始化簇結(jié)構(gòu)時(shí)，采用非均勻分簇的方法，避免了由于數(shù)據(jù)沿簇首生成樹多跳傳輸而導(dǎo)致近基站簇首多余能量的消耗，解決了簇首能量不均衡的問題；采用基于剩余能量的簇首簇內(nèi)選舉的方法，避免了所有節(jié)點(diǎn)參與每輪的簇首選舉過程帶來的不必要的能量消耗，保證了剩余能量最多的節(jié)點(diǎn)擔(dān)任下一任簇首；用簇首建立主干網(wǎng)絡(luò)進(jìn)行數(shù)據(jù)多跳傳輸，合理選擇下一跳簇首節(jié)點(diǎn)，減少了簇頭長(zhǎng)距離傳輸數(shù)據(jù)的能量消耗。