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

王鎮(zhèn)

摘 要 介紹了無線傳感器網(wǎng)絡(luò)分簇路由協(xié)議的相關(guān)技術(shù)及其優(yōu)點(diǎn)，總結(jié)了近年來提出的各種分簇協(xié)議及主要設(shè)計(jì)思想.首先介紹了無線傳感器網(wǎng)絡(luò)分簇協(xié)議的相關(guān)技術(shù)及優(yōu)點(diǎn)；然后介紹了近幾年代表性的分簇路由算法研究工作，并且對其涉及的主要方法進(jìn)行分類分析；最后進(jìn)行了各種分簇路由協(xié)議的綜合比較，并指出了無線傳感器網(wǎng)絡(luò)分簇路由協(xié)議面臨的問題和挑戰(zhàn)以及今后的發(fā)展方向。

關(guān)鍵詞 無線傳感器網(wǎng)絡(luò) 分簇算法 路由協(xié)議

無線傳感器網(wǎng)絡(luò)（WSN）是一種無線自組織網(wǎng)絡(luò)，它包含成百上千的傳感器節(jié)點(diǎn)，每一個節(jié)點(diǎn)有感知環(huán)境、執(zhí)行簡單的計(jì)算與其他臨近節(jié)點(diǎn)或基站（ase station，簡稱BS）直接通信的能力，能在事先沒有構(gòu)建網(wǎng)絡(luò)基礎(chǔ)設(shè)施的環(huán)境下，由傳感器節(jié)點(diǎn)臨時組成的一種自組織、自管理的網(wǎng)絡(luò)[1，2]。

路由是指從源節(jié)點(diǎn)選擇一條節(jié)能、距離短的路徑到目的節(jié)點(diǎn)，在形式上，可以將無線傳感器網(wǎng)絡(luò)看做無向圖，從源節(jié)點(diǎn)到目的節(jié)點(diǎn)選擇一條最短的路徑是一個復(fù)雜組合問題（即NP完全問題）[3]，這其中要考慮很多因素，諸如：能量消耗、數(shù)據(jù)包傳輸時延、能量有效性。由于傳感器節(jié)點(diǎn)的電源能量、計(jì)算能力和通信能力都非常有限，所以節(jié)能路由協(xié)議的設(shè)計(jì)，對無線傳感器網(wǎng)絡(luò)來說極其重要。

近來，科學(xué)界對無線傳感器網(wǎng)路分簇協(xié)議[4]進(jìn)行了深入的研究，分簇網(wǎng)絡(luò)結(jié)構(gòu)由于具有良好的網(wǎng)絡(luò)擴(kuò)展性，便于能量管理、平衡負(fù)載、資源分配等，成為目前國內(nèi)外延長WSN生命周期、降低每一個節(jié)點(diǎn)的能耗的主要方法之一。

1 分簇算法相關(guān)的技術(shù)

1.1 定位技術(shù)

位置信息是傳感器網(wǎng)絡(luò)節(jié)點(diǎn)采集數(shù)據(jù)中不可缺少的部分，沒有位置的監(jiān)測信息通常是毫無意義的，因此定位技術(shù)對于要求有精確位置信息的無線傳感器網(wǎng)絡(luò)分簇協(xié)議來說具有重要的意義。根據(jù)定位過程中是否測量節(jié)點(diǎn)間的距離和角度，把無線傳感器網(wǎng)絡(luò)中的定位技術(shù)分為基于距離的定位技術(shù)和距離無關(guān)的定位技術(shù)。

1.1.1 基于距離的定位技術(shù)

基于距離的定位機(jī)制是通過測量相鄰節(jié)點(diǎn)間的實(shí)際距離或方位來確定位置節(jié)點(diǎn)的位置，通常采用測距、定位和修正等步驟實(shí)現(xiàn)?；诰嚯x的定位機(jī)制分為基于TOA[5]的定位、基于TDOA[1]的定位、基于AOA[6]的定位和基于RSSI[7]的定位等。

1.1.2 距離無關(guān)的定位技術(shù)

距離無關(guān)的定位機(jī)制無須實(shí)際測量節(jié)點(diǎn)間的絕對距離或方位就能夠確定未知節(jié)點(diǎn)的位置，目前提出的定位機(jī)制主要有質(zhì)心算法[1]、DV-Hop[8]算法、Amorphous[9]算法和APIT[10]算法等。

1.2 同步技術(shù)

時間同步是需要協(xié)同工作的傳感器網(wǎng)絡(luò)分簇協(xié)議的一個關(guān)鍵機(jī)制。目前已提出了多個時間同步機(jī)制，其中RBS、TINY/MINI-SYNC和TPSN被認(rèn)為是三個基本的同步機(jī)制。

（1）RBS機(jī)制[11，12]是基于接收者-接收者的時鐘同步：一個節(jié)點(diǎn)廣播時鐘參考分組，廣播域內(nèi)的兩個節(jié)點(diǎn)分別采用本地時鐘記錄參考分組的到達(dá)時間，通過交換記錄時間來實(shí)現(xiàn)他們之間的時鐘同步。

（2）TINY/MINI-SYNC是簡單的輕量級的同步機(jī)制[1]：假設(shè)節(jié)點(diǎn)的時鐘漂移遵循線性變化，那么兩個節(jié)點(diǎn)之間的時間偏移也是線性的，可通過交換時標(biāo)分組來估計(jì)兩個節(jié)點(diǎn)間的最優(yōu)匹配偏移量。

（3）TPSN[13，14]采用層次結(jié)構(gòu)實(shí)現(xiàn)整個網(wǎng)絡(luò)節(jié)點(diǎn)的時間同步：所有節(jié)點(diǎn)按照層次結(jié)構(gòu)進(jìn)行邏輯分級，通過基于發(fā)送者——接收者的節(jié)點(diǎn)對方式，每個節(jié)點(diǎn)能夠與上一級的某個節(jié)點(diǎn)進(jìn)行同步，從而實(shí)現(xiàn)所有節(jié)點(diǎn)都與根節(jié)點(diǎn)的時間同步。

1.3 數(shù)據(jù)融合技術(shù)

數(shù)據(jù)融合技術(shù)[15]是指從各個傳感器節(jié)點(diǎn)收集數(shù)據(jù)的過程中，可利用節(jié)點(diǎn)的本地計(jì)算和存儲能力處理數(shù)據(jù)的融合，去除冗余信息。目前數(shù)據(jù)融合技術(shù)已經(jīng)在目標(biāo)跟蹤、目標(biāo)自動識別等領(lǐng)域得到了廣泛的應(yīng)用。在無線傳感器分簇網(wǎng)絡(luò)的設(shè)計(jì)中，只有面向應(yīng)用需求設(shè)計(jì)具有針對性的數(shù)據(jù)融合方法，才能最大限度地獲益。

2 基于分簇的傳感器路由協(xié)議的優(yōu)點(diǎn)

與傳統(tǒng)的無線傳感器網(wǎng)絡(luò)路由協(xié)議相比，基于分簇的無線傳感器路由協(xié)議優(yōu)點(diǎn)有[16，17]：

（1）自適應(yīng)性：通過簇頭節(jié)點(diǎn)的周期性輪換以及簇成員的加入或者退出來實(shí)現(xiàn)持續(xù)的監(jiān)測和數(shù)據(jù)采集。

（2）節(jié)能性：由于基站遠(yuǎn)離網(wǎng)絡(luò)，節(jié)點(diǎn)與基站的通信是能耗最高的操作，對網(wǎng)絡(luò)進(jìn)行分簇后，簇頭負(fù)責(zé)將整個簇的數(shù)據(jù)發(fā)送到基站，減少了與基站通信的節(jié)點(diǎn)數(shù)，大大降低了網(wǎng)絡(luò)能耗。

（3）消除數(shù)據(jù)冗余：WSN中存在著大量的數(shù)據(jù)冗余，簇頭在將本簇的數(shù)據(jù)發(fā)送到基站之前可進(jìn)行數(shù)據(jù)融合和壓縮操作以消除冗余，進(jìn)一步減少與基站的通信量。

（4）魯棒性：節(jié)點(diǎn)通過一種自組織的方式當(dāng)選為簇首，收集當(dāng)前簇內(nèi)信息并在融合后轉(zhuǎn)發(fā)給基站，把網(wǎng)絡(luò)的負(fù)載均勻的分布在整個網(wǎng)絡(luò)中，大大降低了通信過程中的能量消耗，也增強(qiáng)了網(wǎng)絡(luò)的健壯性。

（5）局部/全局優(yōu)化：與其他路由協(xié)議相比，分簇算法不僅能夠?qū)植啃畔⑦M(jìn)行融合優(yōu)化，而且還能夠?qū)θ中畔⑦M(jìn)行優(yōu)化。

（6）可擴(kuò)展性：分簇算法容易與其他路由算法相結(jié)合，從而提高路由算法的性能。

3 基于分簇的無線傳感器路由協(xié)議

LEACH[18]協(xié)議是一個典型的自適應(yīng)分簇協(xié)議，它采用“輪”的概念，每輪分為簇的建立和數(shù)據(jù)傳輸兩個階段。簇的建立階段：每個傳感節(jié)點(diǎn)隨機(jī)選擇一個0～1 之間的值，如果小于給定的閾值T（n），則選擇為簇首。T（n）的計(jì)算方法如下：

其中： P 為節(jié)點(diǎn)中成為簇頭的百分?jǐn)?shù)（大約占節(jié)點(diǎn)總數(shù)的5%-6%左右）[19]， r 是當(dāng)前的輪數(shù)， G 是在過去的1/ P 輪沒有被選擇為簇頭節(jié)點(diǎn)的集合，mod 是求模運(yùn)算。一旦簇首被選定，它們便向周圍節(jié)點(diǎn)廣播這一信息，非簇首節(jié)點(diǎn)依據(jù)接收信號的強(qiáng)弱來選擇它所要加入的簇，并通知相應(yīng)的簇首節(jié)點(diǎn)，完成簇的建立。數(shù)據(jù)傳輸階段：節(jié)點(diǎn)周期性的采集監(jiān)測數(shù)據(jù)，基于時分復(fù)用（TDMA）的方式發(fā)送給簇首，簇首在進(jìn)行必要的數(shù)據(jù)聚集和融合之后，將處理過的數(shù)據(jù)發(fā)送到基站。數(shù)據(jù)傳輸持續(xù)一段時間后，整個網(wǎng)絡(luò)進(jìn)入下一輪，不斷循環(huán)。L EACH協(xié)議使用了分布式算法，使得任務(wù)被分散到每個傳感器節(jié)點(diǎn)上，有效地減少了每個節(jié)點(diǎn)的負(fù)載，延長了傳感器網(wǎng)絡(luò)的生存時間?；贚 EACH的路由協(xié)議是無線傳感器網(wǎng)絡(luò)中分簇路由協(xié)議中的研究基礎(chǔ)，它采用隨機(jī)簇頭選擇機(jī)制，能夠較好地實(shí)現(xiàn)能量均衡消耗，但L EACH協(xié)議還存在以下缺點(diǎn)：①每一輪都進(jìn)行一次簇重組，帶來了大量額外開銷；②根據(jù)公式（1）的簇首選舉策略來選取簇首，可能造成簇首分布不均，簇內(nèi)成員個數(shù)差異較大，使得各簇首負(fù)載不均衡，造成個別簇首較早死亡；③簇內(nèi)的節(jié)點(diǎn)都直接與簇首通信，增加了簇首的能量消耗；④簇首采用單跳的方式直接和基站通信，當(dāng)網(wǎng)絡(luò)規(guī)模很大時，通信的距離很大，對于能量受限的傳感器網(wǎng)絡(luò)節(jié)點(diǎn)來說，加速了節(jié)點(diǎn)的能量消耗，降低了網(wǎng)絡(luò)的生存時間。

HEED[20]協(xié)議主要根據(jù)主、次兩個參數(shù)，通過將能耗平均分布到整個網(wǎng)絡(luò)來延長網(wǎng)絡(luò)生存時間。其中簇首選擇的主參數(shù)依賴于剩余能量，用于隨機(jī)選取出簇首集合，具有較多剩余能量的節(jié)點(diǎn)將有較大的概率成為簇首；次參數(shù)依賴于簇內(nèi)通信代價，用于確定落在多個簇范圍內(nèi)的節(jié)點(diǎn)最終屬于哪個簇，以及平衡簇首間的負(fù)載。HEED協(xié)議主要改進(jìn)之處是在簇首的選擇中考慮了節(jié)點(diǎn)的剩余能量， 并以主次關(guān)系引入了多個約束條件。HEED協(xié)議分簇更快，能產(chǎn)生分布更加均勻的簇首、更合理的網(wǎng)絡(luò)拓?fù)洹?/p>

HEED協(xié)議與LEACH協(xié)議類似，但在簇首收集完數(shù)據(jù)后，簇首之間通過多跳的方式與基站通信。由于簇首的負(fù)擔(dān)較重，LEACH和HEED協(xié)議都按“輪”進(jìn)行，即周期性地重新選擇簇首，分配TDMA時隙。但是基于簇的TDMA協(xié)議同時帶來了簇間干擾問題。因?yàn)閷τ诜植际降拇厮惴?，最后形成簇的覆蓋區(qū)域是有重疊的，即一個節(jié)點(diǎn)有可能在多個簇的覆蓋之下，為此Xiong Zhuang[21]等人提出了一種消除無線傳感器網(wǎng)絡(luò)簇間干擾的TDMA協(xié)議，該協(xié)議分為三個階段：第一階段為簇建立階段，在該階段中采取LEACH改進(jìn)算法DCHS[22] （Determ- inistic cluster-head selection）中的T（n）計(jì)算公式產(chǎn)生簇首，T（n）計(jì)算公式為：