王鎮(zhèn)

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

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

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

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

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

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

1.1 定位技術(shù)

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

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

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

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

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

1.2 同步技術(shù)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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