能量高效的無線傳感器網(wǎng)絡穩(wěn)定分簇路由協(xié)議

田 勇， 唐 禎 安

（1.大連理工大學 電子科學與技術學院，遼寧 大連 116024；2.大連東軟信息學院 嵌入式系統(tǒng)工程系，遼寧 大連 116024）

0 引 言

分簇路由協(xié)議是目前無線傳感器網(wǎng)絡（wireless sensor network，WSN）研究的熱點之一，這類協(xié)議首先根據(jù)某種規(guī)則把WSN節(jié)點集劃分為多個子集，每個子集成為一個簇，具有一個簇頭[1].分簇路由協(xié)議中如何選取簇頭是最關鍵問題之一，根據(jù)簇頭選取方式的不同，可以把分簇路由協(xié)議分為分布式和集中式兩種[2].分布式路由協(xié)議包括兩類：一類是節(jié)點根據(jù)某個閾值決定是 否 當 選 為 簇 頭，如 LEACH （low－energy adaptive clustering hierarchy）協(xié)議[3]就是這類分布式協(xié)議，它是由節(jié)點根據(jù)隨機數(shù)自主決定是否當選為簇頭，每輪產(chǎn)生的簇頭沒有確定的數(shù)量和位置；另一類是通過節(jié)點之間的信息交互產(chǎn)生簇頭，如 HEED（hybrid energy－efficient distributed clustering）協(xié)議[4]和 HEED－M 協(xié)議[5].HEED協(xié)議將節(jié)點最大剩余能量和平均最小可達能量作為選擇簇頭的參數(shù)，以便簇內(nèi)通信代價達到最小，但是此協(xié)議為了達到簇內(nèi)通信代價最小的目的可能多次進行消息迭代，使得通信開銷顯著增加.HEED－M協(xié)議與HEED協(xié)議的唯一區(qū)別就是HEED協(xié)議使用單跳通信的方式，而HEED－M協(xié)議使用多跳通信的方式.集中式路由協(xié)議是指由基站基于整個網(wǎng)絡信息進行簇拓撲結(jié)構(gòu)的劃分，被建模為帶有特定限制的圖形劃分問題，現(xiàn)已證明是NP問題[6].文獻[7]提出了一種集中式路由協(xié)議LEACH－C（LEACH－centralized）.這類協(xié)議的主要缺點是每個節(jié)點必須向基站傳送地理位置和剩余能量信息，增加了額外的能量開銷.

近年來，隨著 WSN路由協(xié)議研究的不斷深入，又出現(xiàn)了大量的分簇協(xié)議.文獻[8]提出了一種按照網(wǎng)絡生命周期最大化原則計算最優(yōu)傳感器節(jié)點部署圓環(huán)數(shù)的方法，并且設計了EBDG（energy－balanced data gathering）協(xié) 議.Kaur等[9]考慮傳感器節(jié)點的覆蓋范圍是一個任意形狀的區(qū)域，設計了一種帶有多種尺寸的固定形狀區(qū)域的網(wǎng)絡.文獻[10]研究了線性數(shù)據(jù)采集傳感器網(wǎng)絡的均衡能量消耗問題.文獻[11]提出了一種新的非均勻分簇路由協(xié)議EEUC，該協(xié)議利用非均勻的成簇半徑，使得靠近基站的簇成員節(jié)點數(shù)目相對減少.文獻[12]提出了EBCA協(xié)議，將簇內(nèi)剩余能量最多的節(jié)點作為下一輪簇頭節(jié)點.

本文針對WSN能量受限和能量消耗不均衡問題，提出一種能量高效的穩(wěn)定分簇（EESC）路由協(xié)議.該協(xié)議由當前簇頭選擇剩余能量最大的成員節(jié)點為下一輪簇頭，下一輪簇頭上任后，非簇頭節(jié)點根據(jù)能量距離函數(shù)決定加入哪個簇，簇間采用單跳或多跳的通信方式發(fā)送數(shù)據(jù)，以降低能量的消耗.

1 網(wǎng)絡模型

本文研究的WSN由N個隨機分布在正方形區(qū)域內(nèi)的傳感器節(jié)點組成，這些節(jié)點周期性地收集周圍環(huán)境的數(shù)據(jù)，并按照本文給出的路由協(xié)議傳輸至基站.同時假設網(wǎng)絡性質(zhì)如下：

（1）基站位于分布區(qū)域外側(cè)，并且它和傳感器節(jié)點在部署后位置不再發(fā)生變化.

（2）傳感器節(jié)點都是具有唯一標識的同構(gòu)節(jié)點，并且能夠進行數(shù)據(jù)融合.

（3）傳感器節(jié)點可以根據(jù)接收節(jié)點的距離，調(diào)整發(fā)射功率.

（4）傳感器節(jié)點能夠根據(jù)接收到的信號強度來計算它到發(fā)送節(jié)點的近似距離[11].

本文采用的能量消耗模型由發(fā)射電路消耗的能量和功率放大電路消耗的能量兩部分組成.功率放大電路的能耗根據(jù)發(fā)射節(jié)點和接收節(jié)點之間的距離d有所不同，當d小于閾值d0時，采用自由空間模型；大于等于閾值d0時，采用多徑衰落模型.因此，距離為d的兩個節(jié)點，發(fā)射長度為l的數(shù)據(jù)所消耗的能量為

式中：Eelec表示發(fā)射電路的能耗；εfsd2和εmpd4分別為功率放大電路在兩種模型中的能耗.接收這些數(shù)據(jù)所消耗的能量為

另外，用Eda表示融合單位比特數(shù)據(jù)所消耗的能量.

2 EESC路由協(xié)議

EESC路由協(xié)議的基本操作過程是：在網(wǎng)絡部署完成后，基站用給定的功率向網(wǎng)絡廣播一個信號，每個傳感器節(jié)點接收到該信號后，根據(jù)信號強度計算出到基站的近似距離.在WSN開始工作之前需要先產(chǎn)生第一輪的簇頭，由于第一輪傳感器節(jié)點的能量都是一樣的，直接采用LEACH產(chǎn)生簇頭的方法來產(chǎn)生簇頭.每個節(jié)點選擇一個介于0和1的隨機數(shù)，如果這個數(shù)小于閾值p，該節(jié)點成為簇頭.在第一輪的簇頭產(chǎn)生后，協(xié)議進入循環(huán)階段：

（1）簇頭向全網(wǎng)廣播其成為簇頭的消息，非簇頭節(jié)點在收到簇頭廣播的消息后，根據(jù)能量距離函數(shù)確定其屬于的簇，并通知相應的簇頭；

（2）簇頭根據(jù)簇成員節(jié)點發(fā)來的信息，選擇其中剩余能量最大的節(jié)點為下一輪簇頭的接班人；

（3）簇成員節(jié)點按照TDMA（時分復用）時隙發(fā)送數(shù)據(jù)給簇頭，簇頭對接收的信息進行數(shù)據(jù)融合之后，將自己此時的信息廣播給所有簇頭，然后根據(jù)簇頭最小能量耗費判定依據(jù)來選擇通信代價最小的方式將數(shù)據(jù)融合結(jié)果發(fā)送給基站；

（4）基站通知下一輪簇頭的接班人成為簇頭的消息，網(wǎng)絡進入下一輪循環(huán).

2.1 簇的形成

每個簇頭在新一輪循環(huán)開始時，向全網(wǎng)廣播簇頭消息HEAD＿MSG，消息的內(nèi)容為節(jié)點的標識（ID）和當前剩余能量（RE）.非簇頭節(jié)點接收到此消息后，將根據(jù)能量距離函數(shù)決定加入哪個簇頭.首先非簇頭節(jié)點sj計算它到發(fā)送HEAD＿MSG消息的簇頭（CHi）的距離d（sj，CHi），然后計算能量距離函數(shù)f（i，j）為[13]

其中i為簇頭的ID，j為非簇頭節(jié)點的ID，REi為簇頭的剩余能量.節(jié)點sj加入簇頭CHi的條件就是使能量距離函數(shù)f（i，j）最小.

根據(jù)能量距離函數(shù)的公式可知，非簇頭節(jié)點向簇頭發(fā)送信息消耗的能量取決于兩者的距離d（sj，CHi），此距離越小能量距離函數(shù)f（i，j）越小，非簇頭節(jié)點向簇頭發(fā)送消息所消耗的能量就越??；簇頭的剩余能量越多，能量距離函數(shù)f（i，j）越小，就越有利于平衡全網(wǎng)的能量消耗.

當非簇頭節(jié)點sj決定加入簇頭CHi之后，向簇頭CHi發(fā)送JOIN＿MSG消息，消息的內(nèi)容為節(jié)點的ID，以及本輪循環(huán)結(jié)束后該節(jié)點的剩余能量REj，計算如下：

其中REj－cur為節(jié)點sj當前的剩余能量，Ej－sm為向簇頭CHi發(fā)送JOIN＿MSG消息所消耗的能量，Ej－td為向簇頭CHi傳輸數(shù)據(jù)所消耗的能量.簇頭CHi記錄成員節(jié)點的ID及其REj信息，然后簇頭給每個簇成員節(jié)點分配TDMA時隙.

2.2 下一輪簇頭的產(chǎn)生

在簇的形成階段，簇頭CHi記錄了其所有成員節(jié)點的剩余能量REj信息.為了平衡全網(wǎng)的能量，簇頭必須由能量較高的節(jié)點來擔任，所以簇頭可以從成員節(jié)點中選擇剩余能量REj最大的節(jié)點擔任下一輪簇頭的接班人.

2.3 簇間單跳和多跳混合路由協(xié)議

在所有節(jié)點得到其TDMA時隙后，它們按照所分配的TDMA時隙把收集的數(shù)據(jù)傳送給簇頭.簇頭先對簇成員節(jié)點發(fā)來的數(shù)據(jù)以及下一輪的簇頭信息進行融合處理，然后將數(shù)據(jù)以單跳或多跳的通信方式傳輸至基站.

首先采用文獻[11]的思想，引入一個閾值TD＿MAX.若簇頭到基站的距離小于TD＿MAX，則它直接將數(shù)據(jù)傳送給基站；否則使用多跳路由的方式與基站進行通信.在選擇單跳或者多跳傳輸之前，每個簇頭向全網(wǎng)廣播NODE＿MSG消息，內(nèi)容包括其節(jié)點標識、它當前的剩余能量和它到基站的距離.下面介紹使用多跳路由方式時，簇頭選擇中繼節(jié)點的策略.

本文選擇比簇頭CHi更接近基站的區(qū)域中的簇頭作為路由候選節(jié)點，并且建立相應的集合，簇頭CHi的路由候選節(jié)點集合定義如下：

其中CHk表示路由候選節(jié)點，d（CHk，BS）表示路由候選節(jié)點CHk和基站BS之間的距離，d（CHi，BS）表示簇頭CHi和基站BS之間的距離.簇頭CHi將從此集合中選擇一個節(jié)點CHk作為數(shù)據(jù)轉(zhuǎn)發(fā)中繼節(jié)點，選擇的策略分析如下：假設CHk將數(shù)據(jù)直接傳輸至基站，則為了傳輸長度為l的數(shù)據(jù)至基站，CHi和CHk消耗的總能量為

簇頭CHi直接與基站通信消耗的能量為

如果簇頭CHi的路由候選節(jié)點集合RCCHi中僅存在一個候選節(jié)點CHk，使得E2hop小于E1hop，則簇頭CHi將選擇CHk作為其中繼節(jié)點；如果存在多個候選節(jié)點使得E2hop小于E1hop，則簇頭CHi將選擇剩余能量最大的候選節(jié)點作為其中繼節(jié)點；否則簇頭CHi將直接與基站進行通信.

3 EESC路由協(xié)議分析

EESC路由協(xié)議利用集中式路由協(xié)議的思想解決了分布式路由協(xié)議簇頭數(shù)目不確定和簇頭剩余能量難以判斷的問題；同時又利用分布式路由協(xié)議的思想克服了集中式路由協(xié)議必須在基站和節(jié)點之間傳輸信息而耗費額外能量的缺點.下面給出了整個協(xié)議的偽碼：

在此協(xié)議中，簇頭向全網(wǎng)廣播HEAD＿MSG消息和NODE＿MSG消息時，廣播半徑設為此簇頭到網(wǎng)絡覆蓋范圍的4個頂點的最大值；而發(fā)送JOIN＿MSG消息時，發(fā)送半徑為實際到目標節(jié)點的距離.該協(xié)議是消息驅(qū)動的，因此需要分析消息復雜度.

性質(zhì)1 在所選網(wǎng)絡中，EESC路由協(xié)議的消息復雜度為O（N）.

證明 每一輪開始時，有N×p個簇頭共廣播N×p條HEAD＿MSG消息；而N×（1－p）個非簇頭節(jié)點共廣播N×（1－p）條JOIN＿MSG消息；簇頭向全網(wǎng)廣播剩余能量等信息的NODE＿MSG消息共N×p條.因此總的消息開銷為

即消息復雜度為O（N）.

性質(zhì)1說明EESC路由協(xié)議的消息復雜度較小，能量效率較高.文獻[11]提出的EEUC協(xié)議和文獻[14]提出的DEEUC協(xié)議的消息復雜度也為O（N），并且都低于HEED協(xié)議的消息開銷.與文獻[11，14]協(xié)議相比，EESC協(xié)議的消息開銷更低，因此能量效率更高.

4 實驗結(jié)果及分析

為了驗證協(xié)議的有效性，利用MATLAB對協(xié)議進行了仿真測試，實驗所用參數(shù)如表1所示.

表1 實驗參數(shù)Tab.1 Simulation parameters

4.1 參數(shù)p的選擇

協(xié)議中決定簇頭數(shù)目的參數(shù)p的選擇是非常重要的，本文用實驗方法來確定p的取值.令p從0.01到0.1，觀察網(wǎng)絡中第一個死亡節(jié)點和最后一個死亡節(jié)點的輪次（R）隨之變化的情況.每個p值實驗10次取平均值，實驗結(jié)果如圖1所示.由圖可見p＝0.04時，網(wǎng)絡的第一個死亡節(jié)點的輪次最大，當p＝0.02時，網(wǎng)路的最后一個死亡節(jié)點的輪次最大；而當p＝0.04時，從第一個死亡節(jié)點到最后一個死亡節(jié)點的輪次差值最小，這個輪次差值可以反映網(wǎng)絡節(jié)點能量消耗的均衡情況，差值越小說明網(wǎng)絡的能量消耗越均衡.因此本文取p＝0.04，使得網(wǎng)絡的存活時間更長，能量消耗均衡程度更好.

圖1 第一個死亡節(jié)點和最后一個死亡節(jié)點死亡輪次隨參數(shù)p的變化Fig.1 The round changes of the first dead node and the final dead node in networks with the parameter p

4.2 簇頭的能量消耗

為了驗證本文提出的EESC路由協(xié)議能量的高效性和均衡性，將EESC與LEACH、HEED和HEED－M三種分簇路由協(xié)議進行比較.由于分簇路由協(xié)議中簇頭承擔了接收成員數(shù)據(jù)、融合數(shù)據(jù)和將數(shù)據(jù)發(fā)送給基站等多項任務，是WSN中能量消耗的主要部分.圖2顯示了隨機選取10輪，4種協(xié)議的簇頭在一輪里消耗能量之和（Et）的比較結(jié)果.從圖中可以看出，EESC路由協(xié)議的簇頭消耗的能量之和最低而且波動最小，這是因為EESC協(xié)議簇頭的消息開銷較小，并且簇頭采用單跳或多跳的通信方式發(fā)送數(shù)據(jù)至基站，顯著降低了能量的消耗；波動最小是由于EESC路由協(xié)議的簇頭數(shù)量在沒有節(jié)點死亡之前固定不變，簇頭消耗的能量之和沒有明顯的波動.LEACH協(xié)議的簇頭消耗能量最高，波動最大，是因為它采用單跳通信方式，而且構(gòu)造的簇頭數(shù)量較多，導致簇頭消耗的能量增大；另外LEACH構(gòu)造簇頭的數(shù)量不夠穩(wěn)定，導致簇頭消耗的能量之和也有較大差別.HEED和HEED－M協(xié)議簇頭消耗的能量和波動性處于EESC和LEACH協(xié)議之間，而HEED－M協(xié)議簇頭消耗的能量又低于HEED協(xié)議，原因在于HEED－M采用了多跳通信的方式，降低了能量消耗.

圖2 4種協(xié)議的簇頭消耗能量之和Fig.2 The sum of energy dissipated by cluster heads in four protocols

4.3 網(wǎng)絡的生命周期

網(wǎng)絡生命周期的長短是衡量WSN路由協(xié)議優(yōu)劣的首要設計目標.圖3顯示了EESC、LEACH、HEED和HEED－M四種協(xié)議存活節(jié)點數(shù)目（Nlife）隨輪次變化的情況.存活節(jié)點數(shù)目可以反映網(wǎng)絡能量的使用效率，存活節(jié)點越多說明網(wǎng)絡的能量使用效率越高.從圖中可以看出，由于LEACH協(xié)議通過等概率地隨機循環(huán)選擇簇頭，將整個網(wǎng)絡的能量負載平均分配到每個傳感器節(jié)點，使得第一個死亡節(jié)點出現(xiàn)在大約260輪，而最后一個死亡節(jié)點出現(xiàn)在大約600輪.但是，LEACH協(xié)議沒有考慮節(jié)點的剩余能量，并且每輪產(chǎn)生的簇頭沒有確定的數(shù)量，使得網(wǎng)絡的生命周期和能量消耗的均衡性并不理想.HEED協(xié)議在選擇簇頭時考慮了節(jié)點的剩余能量，并以主從關系引入了多個約束條件作用于簇頭的選擇過程，同時也考慮了分簇后簇內(nèi)的通信開銷問題，因此第一個死亡節(jié)點出現(xiàn)在大約330輪，而最后一個死亡節(jié)點出現(xiàn)在大約700輪.與LEACH協(xié)議相比，延長了網(wǎng)絡生命周期.然而，無論是LEACH協(xié)議還是HEED協(xié)議，節(jié)點都是采用單跳的方式與基站進行通信.HEED－M協(xié)議在HEED協(xié)議的基礎上，將節(jié)點與基站的通信方式由單跳改為了多跳，取得了較好的效果.與以上3種協(xié)議相比，本文提出的EESC路由協(xié)議不僅選擇簇內(nèi)能量最大的節(jié)點作為下一輪的簇頭，而且在建簇時利用能量距離函數(shù)來優(yōu)化簇內(nèi)的通信開銷，在傳輸數(shù)據(jù)時采用單跳和多跳相結(jié)合的方式與基站進行通信，因此在大約760輪時才出現(xiàn)第一個死亡節(jié)點，而此時其他3種協(xié)議的節(jié)點已經(jīng)全部死亡，并且最后一個與第一個死亡節(jié)點的差值也遠小于其他3種協(xié)議，這說明EESC路由協(xié)議不僅高效地利用了網(wǎng)絡的能量，延長了網(wǎng)絡的生命周期，而且網(wǎng)絡的能量消耗更加均衡.

圖3 4種協(xié)議的網(wǎng)絡生命周期比較Fig.3 The network lifetime comparison of four protocols

5 結(jié) 語

本文提出了一種能量高效的WSN穩(wěn)定分簇路由協(xié)議，該協(xié)議利用建簇過程傳輸節(jié)點剩余能量信息，簇頭根據(jù)簇成員節(jié)點的剩余能量來選取下一輪的簇頭.這樣，不僅使每次產(chǎn)生的簇頭能量最大，數(shù)目穩(wěn)定，而且不需要在節(jié)點和基站之間傳輸剩余能量等信息，因此具有分布式和集中式分簇路由協(xié)議的共同優(yōu)點.實驗證明了EESC路由協(xié)議能量利用的高效性和能量消耗的均衡性.

[1] 李建中，高 宏.無線傳感器網(wǎng)絡的研究進展[J].計算機研究與發(fā)展，2008，45（1）：1－15.LI Jian－zhong， GAO Hong. Survey on sensor network research[J].Journal of Computer Research and Development，2008，45（1）：1－15.（in Chinese）

[2] 沈 波，張世永，鐘亦平.無線傳感器網(wǎng)絡分簇路由協(xié)議[J].軟件學報，2006，17（7）：1588－1600 SHEN Bo，ZHANG Shi－yong，ZHONG Yi－ping.Cluster－based routing protocols for wireless sensor networks[J].Journal of Software，2006，17（7）：1588－1600.（in Chinese）

[3] Heinzelman W，Chandrakasan A，Balakrishnan H.Energy－efficient communication protocol for wireless microsensor networks [C]// Proceedings of the Hawaii International Conference on System Sciences.Los Alamitos：IEEE，2000：1－10.

[4] Younis O，F(xiàn)ahmy S.HEED：a hybrid，energyefficient，distributed clustering approach for ad hoc sensor networks [J].IEEE Transactions on Mobile Computing，2004，3（4）：366－379.

[5] Younis O，F(xiàn)ahmy S.An experimental study of routing and data aggregation in sensor networks[C]//2nd IEEE International Conference on Mobile Ad－h(huán)oc and Sensor Systems，MASS 2005.Piscataway：Institute of Electrical and Electronics Engineers Computer Society，2005：50－57.

[6] Rhazi A E，Pierre S.A tabu search algorithm for cluster building in wireless sensor networks [J].IEEE Transactions on Mobile Computing，2009，8（4）：433－444.

[7] Heinzelman W，Chandrakasan A，Balakrishnan H.An application－specific protocol architecture for wireless microsensor networks [J]. IEEE Transactions on Wireless Communication， 2002，1（4）：660－670.

[8] ZHANG Hai－bo，SHEN Hong.Balancing energy consumption to maximize network lifetime in datagathering sensor networks[J].IEEE Transactions on Parallel and Distributed Systems，2009，20（10）：1526－1539.

[9] Kaur T，Baek J.A strategic deployment and clusterheader selection for wireless sensor networks [J].IEEE Transactions on Consumer Electronics，2009，55（4）：1890－1897.

[10] ZHANG Hai－bo，SHEN Hong， TAN Ya－suo.Optimal energy balanced data gathering in wireless sensor networks [C] // Proceedings －21st International Parallel and Distributed Processing Symposium，IPDPS 2007.Piscataway：Institute of Electrical and Electronics Engineers Computer Society，2007.

[11] 李成法，陳貴海，葉 懋，等.一種基于非均勻分簇的無線傳感器網(wǎng)絡路由協(xié)議[J].計算機學報，2007，30（1）：27－36 LI Cheng－fa，CHEN Gui－h(huán)ai，YE Mao，etal.An uneven cluster－based routing protocol for wireless sensor networks[J].Chinese Journal of Computers，2007，30（1）：27－36.（in Chinese）

[12] 杜玉紅，張曉敏，蔡成聞.無線傳感器網(wǎng)絡能量均衡自適應分簇算法[J].傳感技術學報，2007，20（7）：1616－1619.DU Yu－h(huán)ong，ZHANG Xiao－min，CAI Cheng－wen.Energy－balanced adaptive clustering algorithm in wireless sensor networks [J].Chinese Journal of Sensors and Actuators，2007，20（7）：1616－1619.（in Chinese）

[13] 洪 利，楊淑玲.一種全局能量均衡的路由協(xié)議[J].計算機工程與應用，2010，46（2）：86－89.HONG Li， YANG Shu－ling. Overall energybalanced routing protocol[J].Computer Engineering and Applications，2010，46（2）：86－89.（in Chinese）

[14] 尚鳳軍，Abolhasan M，Wysocki T.無線傳感器網(wǎng)絡的分布式能量有效非均勻成簇算法[J].通信學報，2009，30（10）：34－43.SHANG Feng－jun，Abolhasan M， Wysocki T.Distributed energy efficient unequal clustering algorithm for wireless sensor networks[J].Journal on Communications，2009，30（10）：34－43. （in Chinese）