基于時間片的無線傳感網(wǎng)絡(luò)節(jié)點低功耗分簇算法的研究摘要：無線傳感器網(wǎng)絡(luò)是由一組微型傳感器節(jié)點以自組織方式構(gòu)成的無線網(wǎng)絡(luò)，網(wǎng)絡(luò)中，除了少數(shù)節(jié)點需要移動以外，大部分節(jié)點都是靜止的。為了延長網(wǎng)絡(luò)壽命，設(shè)計有效的協(xié)議和算法是WSN的核心問題之一。本文把網(wǎng)絡(luò)節(jié)點按照時間片進(jìn)行分簇，并通過協(xié)議使不同的節(jié)點處于工作狀態(tài)，其余節(jié)點處于休眠狀態(tài)，從而節(jié)約了節(jié)點的耗能，延長網(wǎng)絡(luò)的壽命。經(jīng)過仿真實驗，該系統(tǒng)可以達(dá)到設(shè)計指標(biāo)，延長無線傳感網(wǎng)絡(luò)的使用壽命，從而提高網(wǎng)絡(luò)的生存能力。關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)；分簇算法；節(jié)能0引言無線傳感器網(wǎng)絡(luò)是由具有計算、存儲和無線通信能力的小型智能設(shè)備組成的分布式感知網(wǎng)絡(luò)。傳感器節(jié)點負(fù)責(zé)收集監(jiān)測區(qū)域內(nèi)的聲音、電磁或地震信號等多種信息，通過無線信道將它們發(fā)送到Sink節(jié)點。Sink節(jié)點具有更強的處理能力，能夠進(jìn)一步處理信息，或擁有更大的發(fā)送范圍，可以將信息送往某個大型網(wǎng)絡(luò)，使遠(yuǎn)程用戶能夠檢索到該信息。通常傳感器節(jié)點體積都非常小，只有有限的計算能力、有限的存儲能力、有限的無線通信能力和有限的電源供應(yīng)，而且在部署后難以一次補充能量，因此無線傳感器網(wǎng)絡(luò)存在嚴(yán)重的能量約束問題，如何提高能量效率成為傳感器網(wǎng)絡(luò)研究的重大問題。在無線傳感器網(wǎng)絡(luò)中分簇被認(rèn)為是延長網(wǎng)絡(luò)壽命的最有效的方法之一。將傳感器節(jié)點劃分為一個個簇，傳感器節(jié)點的角色分為簇頭和簇成員兩種，簇成員監(jiān)測到的數(shù)據(jù)首先傳到簇頭，簇頭可以對采樣數(shù)據(jù)進(jìn)行融合，然后再轉(zhuǎn)發(fā)到Sink節(jié)點，以減少網(wǎng)絡(luò)流量，由于各個簇頭與Sink節(jié)點的距離不同，離Sink節(jié)點距離較遠(yuǎn)的簇頭采取多跳的方式進(jìn)行通信。然而這種做法帶來了一個能量消耗不均衡的“熱區(qū)”問題，即在傳感器網(wǎng)絡(luò)的多對一通信模式中，靠近Sink節(jié)點的網(wǎng)絡(luò)節(jié)點需要大量轉(zhuǎn)發(fā)其它簇的數(shù)據(jù)，節(jié)點能量過快消耗至死亡，造成網(wǎng)絡(luò)分割，降低網(wǎng)絡(luò)生存時間。很多節(jié)能的拓?fù)淇刂品椒ň褪且匝娱L網(wǎng)絡(luò)生存期為主要目的的，其中LEACH［口是最具有影響力的代表性算法。然而，在TinyOS系統(tǒng)支持的TOSSIM仿真器中加入了能量意識功能后進(jìn)行仿真⑶，LEACH往往會出現(xiàn)在網(wǎng)絡(luò)整體能量較多的情形之下少量節(jié)點過早死亡，從而大大降低了網(wǎng)絡(luò)壽命。本文的主要工作是在LEACH的基礎(chǔ)上，使用基于時間片的輪值分簇法，延長網(wǎng)絡(luò)的生存期，從而提高網(wǎng)絡(luò)的生存能力。.LEACH協(xié)議分析網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型采用與LEACH相同的WSN的研究拓?fù)淇刂频牡湫驮O(shè)置，N個具備弱通信能力、計算能力且能量有限的、同構(gòu)的節(jié)點隨機均勻分布在一個正方形區(qū)域A內(nèi)；節(jié)點部署后不再移動，在無人工干預(yù)的情況下自組織地生成對等網(wǎng)絡(luò)，網(wǎng)絡(luò)中存在一個唯一的基站，部署在區(qū)域A以外的某位置。該傳感器網(wǎng)絡(luò)具有如下性質(zhì)：(1)每輪中節(jié)點的能量消耗不一致；(2)節(jié)點不需要知道其具體位置信息；(3)網(wǎng)絡(luò)中維持一個弱同步時鐘；(4)所有的傳感器以固定速率感知周圍環(huán)境，這樣一來總有數(shù)據(jù)要發(fā)送給終端用戶；(5)網(wǎng)絡(luò)壽命指從網(wǎng)絡(luò)啟動到第一個節(jié)點死亡時間。在通信方式上，本文也使用與LEACH算法相同的假設(shè)。使用對稱的通信信道模型和自由空間模型(FreeSpace)，在距離閾值d0(d0是常數(shù)，與具體的應(yīng)用環(huán)境關(guān)系)之間發(fā)送數(shù)據(jù)放大器消耗的能量與發(fā)送節(jié)點到接收點的距離的平方成正比。使用公式(1)，計算發(fā)送方數(shù)據(jù)消耗的能量［38］：E(L,d)=EL+￡Ld2 (1)Tx elecamp接收方接收部件產(chǎn)生的消耗公式(2)所示。E(L,d)=EL (2)Rx elec其中，L是數(shù)據(jù)幀的長度，E是發(fā)送器和接收器無線信號電路小號的能量，￡是發(fā)送放大器電路消耗的能elec amp量。根據(jù)公式(1)可知，信道傳輸?shù)哪芰繐p失為O(d)d為節(jié)點間距離，故應(yīng)該盡量減少發(fā)送距離和接受的次數(shù)。簇頭數(shù)目

LEACH生成的簇頭個數(shù)據(jù)有隨機性，這種數(shù)目的隨機以不可忽略的概率導(dǎo)致簇頭個數(shù)過多或者過少的情形。LEACH每輪中選出的簇頭數(shù)服從二項分布，設(shè)簇頭比例為p=k/N，每輪中選出的簇頭個數(shù)為X，則式（3）成立:P{X=P{X=K}=pk(1—p)N-k（3）根據(jù)公式（3），圖1顯示了當(dāng)N=100，最優(yōu)簇頭數(shù)目k=5,即p=0.05時X的概率分布，圖中簇頭個數(shù)取最優(yōu)值k=5的概率只有0.18002。簇頭過少的情形，如產(chǎn)生的簇頭小于3的概率為0.1183,簇頭的數(shù)目決定了簇的規(guī)模，即有0.1183概率使得簇規(guī)模過大，這樣，簇頭節(jié)點收集了所有的節(jié)點信息后才進(jìn)行融合并轉(zhuǎn)發(fā)融合后的數(shù)據(jù)，在一個輪周期內(nèi)有效地減少了簇頭的轉(zhuǎn)發(fā)次數(shù)，但可能降低了信息服務(wù)質(zhì)量；產(chǎn)生簇頭大于7的概率為0.128，這種簇規(guī)模過小的情形使得簇內(nèi)數(shù)據(jù)的融合效果不明顯，從而簇頭與基站通信的頻率較高，在全網(wǎng)范圍內(nèi)增加了簇頭與基站總體通信耗費，縮短了網(wǎng)絡(luò)使用壽命。圖1簇頭分?jǐn)?shù)概率分布.簇3頭分布LEACH生成的簇頭在分布上是隨機的，這種分布的隨機性也導(dǎo)致輪內(nèi)各簇規(guī)模大小不同。如圖所示。分析認(rèn)為這種不一致性使得LEACH算法有效性的兩個前提條件難以得到保證。圖2LEACH簇分布LEACH有效的前提條件如下：一是簇頭初期，所有節(jié)點當(dāng)前能量一樣多；二是簇形成后，消耗大致相同的能量，在網(wǎng)絡(luò)布置初期第一個工作周期內(nèi)，首輪選舉簇頭時，條件一可以得到滿足；但是當(dāng)簇內(nèi)規(guī)模不一樣時，條件二得不到保證。因為網(wǎng)絡(luò)模型的假設(shè)(即所有的傳感器以固定速率感知周邊環(huán)境，這樣一來總有數(shù)據(jù)發(fā)送給始終用戶)認(rèn)為節(jié)點按照相同的速率傳輸數(shù)據(jù)。這樣簇規(guī)模大小決定了簇頭的工作量將大大不同。LEACH隨機產(chǎn)生簇頭的方式會使規(guī)模簇規(guī)模大小相差較大，不同的簇內(nèi)簇頭消耗的能量有顯著的差距，同時，在同一簇內(nèi)節(jié)點到簇頭的距離差別較大，從而通信功率差距較大，也會導(dǎo)致能耗的較大差距。這樣，在此后每輪選舉的時候，成簇算法很可能會選中上一輪中能量消耗較多的節(jié)點繼續(xù)擔(dān)任簇頭，這無疑又加速了該節(jié)點的死亡。綜上所述，LEACH算法依然存在個別簇頭早死亡從而導(dǎo)致降低網(wǎng)絡(luò)壽命的現(xiàn)象，必須盡量使用剩余能量較多的節(jié)點來充當(dāng)簇頭，必須盡量減少當(dāng)值簇頭的消耗。算法的實現(xiàn)針對LEACH簇頭分布及數(shù)目的隨機性所導(dǎo)致的問題，在成簇階段考慮節(jié)點剩余能量，提出了能量意識的簇頭產(chǎn)生方法，盡量讓剩余能量的節(jié)點擔(dān)任簇頭，在簇的維持階段，采用基于分時復(fù)用思想簇內(nèi)輪值活動節(jié)點(ActiveNodes)，使用活動節(jié)點分?jǐn)偣?jié)點消耗，降低簇頭消耗，這樣增加簇的輪內(nèi)壽命，在整個網(wǎng)絡(luò)生命期內(nèi)減少生成簇的次數(shù)，從而在全局范圍內(nèi)減少消耗，延長網(wǎng)絡(luò)壽命。能量意識的簇頭選舉方法成簇過程分為兩個環(huán)節(jié)，首先是簇頭選舉，然后是剩余節(jié)點根據(jù)和簇頭的交互信息，選擇加入合適的簇頭。大量對等節(jié)點如何分布式的選舉是關(guān)鍵問題。LEACH提供了一個有效的分布式算法，但未能考慮簇規(guī)模的隨機性導(dǎo)致節(jié)點剩余能量不同，每個節(jié)點剩余能量完全相同的假設(shè)會導(dǎo)致能量很低的節(jié)點以不可忽略的概率當(dāng)選簇頭，從而過早死亡。為此，在簇頭選舉階段引入能量因素設(shè)定閾值函數(shù)T(i)：1-prmodG/p)]1y/X八GT(i)=] ⑶0,其他其中，參數(shù)P為預(yù)設(shè)的簇頭節(jié)點占總節(jié)點數(shù)的比例，r為簇頭選舉的當(dāng)前輪數(shù)，i是當(dāng)前節(jié)點的ID,G是到該輪

其值有公式（4）結(jié)出：為止尚未當(dāng)選簇頭的節(jié)點集合，其值有公式（4）結(jié)出：(4)?！狤.(4)/v- i-init—Ei-current其中，E為節(jié)點的初始能量，E 為節(jié)點的當(dāng)前能量。i i一current一init考慮到比例因子不應(yīng)隨節(jié)點能量的降低而很快趨近于零，也不能下降很慢，否則體現(xiàn)不出能量因素。仿真了1、1 、等幾種情況，在設(shè)置網(wǎng)絡(luò)參數(shù)下，經(jīng)過對結(jié)果的大量分析比較選用1比例因子。簇頭產(chǎn)生階段，每個節(jié)點分布式的決定自身在當(dāng)前輪中是否成為簇頭，節(jié)點產(chǎn)生一個0~1之間的隨機數(shù)，然后根據(jù)公式（3）求出閾值T（i），如果這個隨機數(shù)小于閾值，則該節(jié)點成為簇頭。由于節(jié)點成為簇頭。有公式（4）可看出，隨著輪數(shù)的增加門檻值T（i）逐漸增大，且剩余節(jié)點中的能量多的節(jié)點當(dāng)選為簇頭的概率最大。簇形成階段，簇頭通過非持續(xù)CSMAMAC協(xié)議，使用同樣的能量發(fā)出簇頭通知消息給剩余節(jié)點，在這個階段，非簇頭節(jié)點打開接收器，接收通知信息，然后根據(jù)收到的信息的強弱決定這一輪加入哪個簇。非簇頭節(jié)點會收到很多通知信息，已通知信號最強的的那個簇頭所在的簇為選中的簇，這也是最近鄰居聚類法則，具有有效地避免簇間干擾的作用。當(dāng)節(jié)點決定加入某一簇后，需通知簇頭節(jié)點它屬于哪個簇，根據(jù)對稱通信信道的假設(shè)，該節(jié)點可以根據(jù)信號的能量意識選擇可以通信的最小功率發(fā)射恢復(fù)（回復(fù)？）消息給簇頭，也用非持續(xù)CDMAMAC協(xié)議把這個反饋消息發(fā)回給簇頭，表示加入這個簇?；跁r間片的簇內(nèi)能耗輪值方法在LEACH中，給定一個輪周期，第一輪選出若干個節(jié)點當(dāng)簇頭，一個周期后，重新選舉簇頭成簇，考慮到成簇代價太大，因此應(yīng)該盡量延長輪周期。然而，由于簇頭耗費能量遠(yuǎn)遠(yuǎn)大于普通節(jié)點，輪周期過長會導(dǎo)致輪內(nèi)簇頭節(jié)點過早死亡，為此，提出在簇內(nèi)制定信息調(diào)度機制，讓各節(jié)點輪流負(fù)責(zé)。簇頭節(jié)點接收到所有想加入該簇的節(jié)點反饋消息，基于簇中節(jié)點的數(shù)量，簇頭節(jié)點建立TDMA調(diào)度，集中式的決定每個成員輪流充當(dāng)活動節(jié)點（ActiveNodes），讓活動節(jié)點承擔(dān)簇頭的任務(wù)。調(diào)度過程中要用到3個關(guān)于時間的參數(shù)SB、SA與Tround、其中，SB是一個網(wǎng)絡(luò)參數(shù)，取值至少為幀長除以信道速率；SA是簇的參數(shù)，表示簇內(nèi)某節(jié)點擔(dān)任Active節(jié)點的持續(xù)時間，其值為SB乘以簇內(nèi)成員數(shù)（簇內(nèi)總節(jié)點點數(shù)-1）；輪的時間Tround是預(yù)先確定值，簇內(nèi)某節(jié)點在一輪中，可以根據(jù)Tround/SB的值確定擔(dān)任幾次Active節(jié)點，這樣所有節(jié)點擔(dān)任的次數(shù)相差不超過1。簇形成后，當(dāng)選的簇頭根據(jù)簇內(nèi)節(jié)點的個數(shù)N，來確定時隙的分配。該輪中一級時槽SA應(yīng)該是二級時槽SB和N的積的倍數(shù)，每個節(jié)點只在其規(guī)定的時槽SB內(nèi)傳輸信息到Active節(jié)點，從而各個傳感節(jié)點通過TDMA來避免信息競爭沖突，在各個時槽SA簇內(nèi)所有節(jié)點依次當(dāng)選為Active節(jié)點，算法操作的時序如圖3所示。算法實現(xiàn)時，可以不進(jìn)行二級時槽SA的分配，而是在N個SA時槽后，由當(dāng)前Active節(jié)點將領(lǐng)導(dǎo)地位隨機遷移到N個成員之一，自己降格為簇內(nèi)成員，由新的Active節(jié)點進(jìn)行下一個SA時槽的工作。每次以概率P=1/Ncurrent進(jìn)行領(lǐng)導(dǎo)地位的轉(zhuǎn)讓，其中Ncurrent為簇內(nèi)當(dāng)前尚未承擔(dān)Active節(jié)點的節(jié)點個數(shù)，這個值可以包含在網(wǎng)絡(luò)控制幀中。圖3基于時間片的分簇操作時序簇生成后進(jìn)入穩(wěn)定工作階段，簇頭按照預(yù)先確定的二級時槽SB間隔，根據(jù)當(dāng)前簇內(nèi)節(jié)點個數(shù)N，可以確定一級時槽SA的間隔，再根據(jù)預(yù)定的每輪持續(xù)時間Tround確定當(dāng)前簇中一級時槽SA的個數(shù)NA,假設(shè)SA內(nèi)Active節(jié)點耗能為esa(通信能耗)，則簇頭耗能為esana。在本輪實現(xiàn)中，能耗近似平均分?jǐn)偟酱貎?nèi)每個節(jié)點，更準(zhǔn)確地說，其中，NAmodN個節(jié)點每個耗能為［1+(NA/N)］ESA,(N-NAmodN)個節(jié)點每個耗能為［NA/(N+Dl/ESAo可見，該算法在簇內(nèi)將能量消耗近似平攤到簇內(nèi)節(jié)點上，簇內(nèi)各節(jié)點能耗大致平均，避免了簇頭單個承擔(dān)太多的轉(zhuǎn)發(fā)任務(wù)而過早死亡。數(shù)據(jù)傳輸服務(wù)簇內(nèi)時間片信息建立后，可以進(jìn)行數(shù)據(jù)傳輸。假設(shè)節(jié)點總是有數(shù)據(jù)要發(fā)送，在其分配的時槽內(nèi)向Active節(jié)點發(fā)送信息，因為距離較短，只需要較少的能量，在其余時槽內(nèi)關(guān)閉無線信號，減少能耗。Active節(jié)點工作期間必須一直打開無線信號以接收成員信息，接收到所有數(shù)據(jù)后，進(jìn)行信號融合處理功能，壓縮數(shù)據(jù)成單一信號后傳送到基站，由于距離較遠(yuǎn)，Active節(jié)點能耗很大。本輪規(guī)定的時間到后，啟動下一輪的簇頭選舉和簇生成工作。仿真實驗分析與相關(guān)工作比較考慮能耗均勻性、能量有效性、網(wǎng)絡(luò)壽命和系統(tǒng)死亡速度及基站移動對性能的影響等作為性能評價標(biāo)準(zhǔn)，在仿真實驗中與相關(guān)工作進(jìn)行了比較。參數(shù)設(shè)置和評價指標(biāo)在仿真平臺的選擇上，目前存在的WSN仿真方法可以分為兩類，一類是程序代碼模擬器，例如，TOSSIM0、Avrora14］和TOSSFS等；另一類是協(xié)議仿真軟件，例如對NS-2［6］和OPNET［7］進(jìn)行擴展的仿真方法。由于WSN是高度應(yīng)用相關(guān)的，且跨層設(shè)計實現(xiàn)網(wǎng)絡(luò)服務(wù)功能，所以，程序代碼模擬器比NS-2等分層協(xié)議仿真軟件更合適無線傳感器網(wǎng)絡(luò)仿真模擬器，由加州大學(xué)伯克利分校、Intel研究中心和哈佛大學(xué)聯(lián)合開發(fā)，內(nèi)嵌在TinyOS［3］操作系統(tǒng)中，它能夠?qū)蝹€節(jié)點的操作提供高精度模擬，可以準(zhǔn)確的模擬應(yīng)用程序在節(jié)點上的行為。因為成本和部署傳感器網(wǎng)絡(luò)的困難性，必須在部署之前獲得應(yīng)用的能量使用狀況，TOSSIM以前沒有能量意識，在本仿真中使用加入了能量意識的PowerTOSSIM［8］來進(jìn)行仿真，從而能夠較精確的獲得應(yīng)用消耗的能量值。仿真過程如下：(1)仿真啟動，仿真程序從main.exe開始，設(shè)置仿真場景，加入能量參數(shù)；(2)仿真初始化，初始化全局任務(wù)隊列，完成系統(tǒng)初始化設(shè)置；(3)事件隊列處理循環(huán)，實現(xiàn)相應(yīng)功能；(4)仿真結(jié)束階段。實驗中用到的參數(shù)見下表,100個節(jié)點均勻隨機分布的網(wǎng)絡(luò)如圖4所示，基站放置在離最近節(jié)點50m處，位置為(50m,150m),圖4中末給出，根據(jù)下表的參數(shù)能算出二級時槽SB的值(L/Cbw)為3.2ms,在節(jié)點能量達(dá)到0.002J及以下時，算法認(rèn)為該節(jié)點死亡。表模擬中使用的參數(shù)參數(shù)值網(wǎng)絡(luò)大小100m*100m基站位置50m.150m節(jié)點個數(shù)100無線收發(fā)電路能耗50nJ/bit發(fā)送放大器能耗100pJ/(bit.m2)初始能量0.5J數(shù)據(jù)幀大小400Byte廣播幀大小40Byte距離閾值300m數(shù)據(jù)融合能耗5nJ/bit一輪持續(xù)時間18s信道帶寬1Mbit/s二級時槽3.2ms

1009080706050403020100 10 2030 4050 60 708090圖4100個節(jié)點的隨機網(wǎng)絡(luò)仿真實驗中，實現(xiàn)了LEACH、HEED2、DCHS身和基于時間片低功耗算法(TimeSiot-Based),并對性能進(jìn)行比較，主要分析、評價基于時間片低功耗算法的如下幾個衡量標(biāo)準(zhǔn)：(1)、能量消耗均勻性；(2)、網(wǎng)絡(luò)壽命，第一個節(jié)點的死亡時間；(3)、系統(tǒng)死亡速度，指的是從第一個節(jié)點死亡到所有節(jié)點死亡的時間；(4)、能量有效性；(5)、網(wǎng)絡(luò)消耗的能量與基站接收幀個數(shù)之間的關(guān)系。實驗結(jié)果及相關(guān)工作比較經(jīng)過600輪仿真后，可知LEACH中耗能小于10%和大于90%的節(jié)點數(shù)量分別在20%和30%左右，而處于其他能量消耗段的節(jié)點數(shù)量都不大于10%，這說明存在一部分節(jié)點過度使用能量，這部分節(jié)點會率先死亡，盡管LEACH初衷是通過隨機輪轉(zhuǎn)來平衡能耗，但效果不理想。本文提出的TimeSlot-Based協(xié)議主要通過平衡簇內(nèi)節(jié)點的能耗，使得大部分節(jié)點消耗近似相同的能量，與LEACH、DCHS和HEED相比性能有較大的提高，仿真效果基本和預(yù)期性能吻合，能量分布比較緊湊，耗能40%左右的節(jié)點幾乎占到總數(shù)的80%，同時，耗能40%、50%和60%范圍內(nèi)的節(jié)點占到總數(shù)的95%左右，從而解決了LEACH協(xié)議中因為簇頭個數(shù)不合理和分布不均勻而導(dǎo)致能耗不均勻的問題。圖5是活節(jié)點數(shù)量與網(wǎng)絡(luò)工作時間(輪數(shù))之間的關(guān)系，可以看到，與LEACH和DCHS