優(yōu)化分簇及簇首選擇的WSN路由算法.doc

COLEH:優(yōu)化分簇及簇首選擇的WSN路由算法林觀康 程良倫（廣東工業(yè)大學(xué) 自動(dòng)化學(xué)院，廣州 510006）摘 要 如何有效地使用傳感器節(jié)點(diǎn)的能量以延長(zhǎng)WSN（Wireless sensor networks）的生存時(shí)間，一直是WSN路由協(xié)議研究所關(guān)注的焦點(diǎn)。本文基于分簇協(xié)議提出一種新的路由算法COLEH（Clustering Optimized Low Energy Hierarchy）,采用非均勻分簇的思想來優(yōu)化簇的劃分，并根據(jù)節(jié)點(diǎn)的剩余能量來選擇簇首。仿真實(shí)驗(yàn)結(jié)果表明該路由算法有效地使節(jié)點(diǎn)能量消耗均衡化，延長(zhǎng)了整個(gè)網(wǎng)絡(luò)的壽命。關(guān)鍵詞 無線傳感器網(wǎng)絡(luò)，路由，能量，壽命中圖法分類號(hào) TP393 COLEH: a optimized clustering wireless sensor networks hierarchical routing algorithmLIN Guan-kang CHENG Liang-lun（Faculty of Automation, Guangdong University of Technology, Guangzhou 510006, China）Abstract How to use nodes energy effectively to prolong the networks lifetime is one of research emphasis for Wireless Sensor Networks. This paper propose a new hierarchical routing algorithm: COLEH（Clustering Optimized Low Energy Hierarchy）,it adopt the uneven way to optimize the partition of cluster, chose the cluster head by nodes residual energy . Simulation results show that the routing algorithm proportion the energy consumption of nodes effectively, thus extended the lifetime of the entire network.Keywords wireless sensor networks, routing, energy, static收稿日期 - - 收修改稿日期 - - Received , ; in revised from , 基金項(xiàng)目：國(guó)家自然科學(xué)基金項(xiàng)目（No.60673132），廣東省自然科學(xué)基金項(xiàng)目（No.07117421），廣東省自然科學(xué)基金研究團(tuán)隊(duì)項(xiàng)目（No.8351009001000002），廣東省重大科技專項(xiàng)(No.2009A080207008)隨著技術(shù)的不斷進(jìn)步，無線傳感器網(wǎng)絡(luò)的重要性日益突出，并且在醫(yī)療、軍事、環(huán)境檢測(cè)、工業(yè)等領(lǐng)域有著廣泛的應(yīng)用前景1，2。由于無線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)采用微型電池供電，且放置在惡劣的環(huán)境中工作，一般很難進(jìn)行充電或是替代，系統(tǒng)的能量資源非常有限，故設(shè)計(jì)中常先考慮節(jié)能問題以延長(zhǎng)網(wǎng)絡(luò)的壽命，很多路由協(xié)議也是基于這一原理設(shè)計(jì)的。特別是以基于簇路由協(xié)議為代表的網(wǎng)絡(luò)層協(xié)議，是目前國(guó)際上研究的熱點(diǎn)和重點(diǎn)內(nèi)容之一3。對(duì)于大規(guī)模無線傳感器網(wǎng)絡(luò)，分簇協(xié)議更能節(jié)省無線傳感器網(wǎng)絡(luò)的總能量損耗。在分簇協(xié)議中，簇的生成及把特定工作分配到簇首，極大地提高了整個(gè)系統(tǒng)的可擴(kuò)展性和延長(zhǎng)了網(wǎng)絡(luò)壽命4。LEACH5協(xié)議是最早提出的分簇路由協(xié)議，其基本思想是以循環(huán)的方式隨機(jī)選擇簇首節(jié)點(diǎn)，將整個(gè)網(wǎng)絡(luò)的量負(fù)載平均分配到每個(gè)節(jié)點(diǎn)上，從而降低能耗、延長(zhǎng)網(wǎng)絡(luò)的生存時(shí)間。它的基本思路為后來的一系列基于簇的路由協(xié)議的提出做出了重大貢獻(xiàn)。LEACH-C6將目標(biāo)區(qū)域劃分成等面積的幾個(gè)區(qū)域，分區(qū)域進(jìn)行管理。一個(gè)區(qū)域內(nèi)的簇首只需要管理本區(qū)域內(nèi)的其他節(jié)點(diǎn)的信息，使整個(gè)無線傳感器網(wǎng)絡(luò)的能量分布較為均衡， 達(dá)到延長(zhǎng)網(wǎng)絡(luò)壽命的目的。EEUC7是一個(gè)能量高效的非均勻分簇算法，它通過非均勻的方式來構(gòu)造大小不同的簇?？拷镜拇匾?guī)模遠(yuǎn)小于遠(yuǎn)離基站的簇，因此基站附近的簇首可以為簇間的數(shù)據(jù)轉(zhuǎn)發(fā)保留能量，從而解決了“熱區(qū)”問題。但該算法在分簇時(shí)并未考慮到簇內(nèi)各節(jié)點(diǎn)間的距離，導(dǎo)致分簇過大，在簇內(nèi)通信時(shí)，它采用單跳方式，邊緣節(jié)點(diǎn)與簇首通信要消耗很大的能量。本文提出一個(gè)對(duì)分簇及簇首選擇進(jìn)行優(yōu)化的路由算法，總體上把所有節(jié)點(diǎn)按節(jié)點(diǎn)與基站的距離劃分，同一距離等級(jí)的節(jié)點(diǎn)組成簇，靠近基站的簇規(guī)模小于遠(yuǎn)離基站的簇。然后根據(jù)節(jié)點(diǎn)的剩余能量及節(jié)點(diǎn)在簇內(nèi)的位置選擇簇首；最后，簇首通過簇間的路由把融合后的數(shù)據(jù)發(fā)送到基站1.分層路由協(xié)議分析分層路由算法的基本思想是將傳感節(jié)點(diǎn)分簇，每個(gè)簇由一個(gè)簇首和多個(gè)簇內(nèi)成員組成接收到分組的簇內(nèi)節(jié)點(diǎn)直接將分組轉(zhuǎn)發(fā)至簇首節(jié)點(diǎn)，分組轉(zhuǎn)發(fā)下一跳節(jié)點(diǎn)為到簇首節(jié)點(diǎn)的最小路徑上的節(jié)點(diǎn)。簇首節(jié)點(diǎn)通過數(shù)據(jù)聚集減少傳輸信息量，最后簇首節(jié)點(diǎn)把聚集數(shù)據(jù)轉(zhuǎn)發(fā)給終端節(jié)點(diǎn)。分層路由協(xié)議的每輪循環(huán)大致包括兩個(gè)階段：建立階段及穩(wěn)定狀態(tài)階段(如圖1所示)。建立階段里，算法進(jìn)行簇首的選舉及分簇的形成；在穩(wěn)定狀態(tài)階段里，進(jìn)行收集數(shù)據(jù)和給簇首傳輸數(shù)據(jù)。簇首節(jié)點(diǎn)在收到簇內(nèi)成員的數(shù)據(jù)之后會(huì)對(duì)這些數(shù)據(jù)進(jìn)行聚合后傳送給Sink。經(jīng)過一段時(shí)間之后，網(wǎng)絡(luò)就會(huì)再一次回到協(xié)議的建立階段，開始新一輪的工作。圖1.分層協(xié)議操作的1輪時(shí)間結(jié)構(gòu)圖Fig. 1. hierarchical algorithm operation structure of a time分層路由算法的優(yōu)點(diǎn)有：(1)成員節(jié)點(diǎn)大部分時(shí)間可以關(guān)閉通信模塊，由簇頭構(gòu)成一個(gè)更上一層的連通網(wǎng)絡(luò)來負(fù)責(zé)數(shù)據(jù)的長(zhǎng)距離路由轉(zhuǎn)發(fā)。這樣既保證了原有覆蓋范圍內(nèi)的數(shù)據(jù)通信，也在很大程度上節(jié)省了網(wǎng)絡(luò)能量；(2) 簇頭融合了成員節(jié)點(diǎn)的數(shù)據(jù)之后再進(jìn)行轉(zhuǎn)發(fā)，減少了數(shù)據(jù)通信量，從而節(jié)省了網(wǎng)絡(luò)能量；(3) 成員節(jié)點(diǎn)的功能比較簡(jiǎn)單，無須維護(hù)復(fù)雜的路由信息。這大大減少了網(wǎng)絡(luò)中路由控制信息的數(shù)量，減少了通信量；(4) 分簇拓?fù)浣Y(jié)構(gòu)便于管理，有利于分布式算法的應(yīng)用，可以對(duì)系統(tǒng)變化做出快速反應(yīng)，具有較好的可擴(kuò)展性，適合大規(guī)模網(wǎng)絡(luò)；傳統(tǒng)的分層協(xié)議也存在三個(gè)潛在的問題。一是無法保證簇的大小，有些區(qū)域的簇首個(gè)數(shù)過少，簇首與成員節(jié)點(diǎn)的通訊距離過大，而使簇首的負(fù)擔(dān)過重，能量消耗過快。二是每次都要在大范圍里競(jìng)選簇首，然后成簇，額外耗費(fèi)了能量和時(shí)間。三是熱區(qū)問題，即靠近基站的節(jié)點(diǎn)不但要發(fā)送自己的傳感數(shù)據(jù)，還要轉(zhuǎn)發(fā)遠(yuǎn)端節(jié)點(diǎn)的傳感數(shù)據(jù)，致使越靠近基站的節(jié)點(diǎn)能量損耗得越快。2. COLEH協(xié)議設(shè)計(jì)本文提出的COLEH協(xié)議，把目標(biāo)區(qū)域內(nèi)的節(jié)點(diǎn)按節(jié)點(diǎn)與基站的距離劃分等級(jí)，同一個(gè)距離等級(jí)間的節(jié)點(diǎn)進(jìn)行簇首競(jìng)爭(zhēng)并產(chǎn)生若干簇首，每個(gè)分簇設(shè)立一個(gè)簇首，保證一定區(qū)域內(nèi)的簇首數(shù)量。2.1 前提條件本算法應(yīng)用于靜態(tài)無線傳感器網(wǎng)絡(luò)中，有以下特點(diǎn)：(1)傳感器節(jié)點(diǎn)是同構(gòu)的，具有相同的初始能量，相同的通信范圍，且每個(gè)傳感器節(jié)點(diǎn)都有自己的ID號(hào)；(2)傳感器節(jié)點(diǎn)通過RSSI等工具可以計(jì)算出與基站的距離，節(jié)點(diǎn)能夠感知自己的剩余能量；(3)成員節(jié)點(diǎn)與簇首、簇首與簇首之間的通信滿足自由空間通信模型8，本算法中通信距離較近，取P=2；(4) 研究區(qū)域?yàn)? 0 03 0 0的方形區(qū)域。網(wǎng)絡(luò)中基站 B S位于( 0,0 ) 。之所以不選在中心位置，是因?yàn)榛静辉谥行氖且环N網(wǎng)絡(luò)分布不理想的情況， 在這種極端的假設(shè)下，更能體現(xiàn)網(wǎng)絡(luò)性能的優(yōu)劣。2.2協(xié)議設(shè)計(jì)2.2.1簇首的選擇及簇的形成如圖2所示，以基站為中心點(diǎn)，建立極坐標(biāo)，先按等距離把目標(biāo)區(qū)域劃分為若干個(gè)圓環(huán)，距離的大小與節(jié)點(diǎn)的最大通信有關(guān)，離基站越近的圓環(huán)級(jí)別越低。級(jí)別低的圓環(huán)里簇首既要集合簇內(nèi)節(jié)點(diǎn)的數(shù)據(jù)信息，又要轉(zhuǎn)發(fā)級(jí)別高的圓環(huán)的數(shù)據(jù)，因此級(jí)別低的圓環(huán)的簇首密度要比級(jí)別高的圓環(huán)的簇首密度大，才能降低級(jí)別低圓環(huán)里的簇首的負(fù)擔(dān)，才能中和熱區(qū)問題。由于按等距離劃分圓環(huán)，級(jí)別高的圓環(huán)面積比級(jí)別低的圓環(huán)面積大，且節(jié)點(diǎn)均勻分布，每個(gè)圓環(huán)里的簇首數(shù)量一樣，則圓環(huán)級(jí)別越低，其單位面積里的簇首數(shù)量越大，亦即簇首密度越大。如此進(jìn)行圓環(huán)劃分，可以中和熱區(qū)問題，滿足設(shè)計(jì)要求。圖2. COLEH路由的分簇Fig.2. COLEH clustering基站先向全部節(jié)點(diǎn)發(fā)送廣播圓環(huán)區(qū)域劃分情況，各個(gè)節(jié)點(diǎn)通過RSSI或GPS等工具計(jì)算出與基站的距離，再與收到的圓環(huán)區(qū)域劃分情況進(jìn)行比較，得出自己屬于哪一個(gè)圓環(huán)區(qū)域。在圓環(huán)區(qū)域劃分的基礎(chǔ)上，各個(gè)區(qū)域開始獨(dú)立形成簇，互不干涉，每個(gè)圓環(huán)區(qū)域競(jìng)選預(yù)定個(gè)數(shù)的簇首，簇首競(jìng)選中限于同一圓環(huán)區(qū)域內(nèi)，從而避免了通過網(wǎng)絡(luò)重復(fù)傳遞動(dòng)態(tài)信息到遠(yuǎn)端基站，縮小通信代價(jià)。同時(shí)各區(qū)域并行運(yùn)行成簇算法，大大縮短了網(wǎng)絡(luò)初始化時(shí)間，提高網(wǎng)絡(luò)響應(yīng)的快速性。同圓環(huán)區(qū)域內(nèi)簇首競(jìng)選時(shí)，每個(gè)節(jié)點(diǎn)經(jīng)過延時(shí)后廣播自己的剩余能量，延時(shí)的時(shí)間與節(jié)點(diǎn)的ID號(hào)有關(guān)，避免沖突。節(jié)點(diǎn)以剩余能量進(jìn)行排列，剩余能量最大的節(jié)點(diǎn)優(yōu)先成為簇首并向同級(jí)節(jié)點(diǎn)廣播這個(gè)消息。本輪未成為簇首的剩余能量最大的節(jié)點(diǎn)（候選節(jié)點(diǎn)）判斷與本輪已存在簇首的距離是否大于預(yù)設(shè)的閥值，閥值與節(jié)點(diǎn)密度及節(jié)點(diǎn)的最大通信距離有關(guān)。當(dāng)候選節(jié)點(diǎn)與已存在簇首的距離大于閥值時(shí)，表明該候選節(jié)點(diǎn)與已存在簇首的成簇空間重疊小，或無重疊，此時(shí)該候選節(jié)點(diǎn)也成為簇首并發(fā)送廣播消息。否則當(dāng)候選節(jié)點(diǎn)與已存在簇首的距離小于閥值時(shí)，表明該候選節(jié)點(diǎn)與已存在簇首的成簇空間重疊大，簇首的利用率低，此時(shí)該候選節(jié)點(diǎn)放棄成為簇首，并直接通知下一個(gè)候選節(jié)點(diǎn)進(jìn)行判斷，依次循環(huán)至圓環(huán)內(nèi)的簇首達(dá)到預(yù)定數(shù)量。當(dāng)圓環(huán)內(nèi)的簇首達(dá)到預(yù)定數(shù)量時(shí)，停止簇首競(jìng)選。各節(jié)點(diǎn)選擇距離最近的簇首并組成簇。2.2.2簇的路由簇的路由包括簇內(nèi)路由及簇間路由兩個(gè)方面。簇內(nèi)路由即每個(gè)簇的成員節(jié)點(diǎn)通過單跳把數(shù)據(jù)發(fā)送到簇首，簇首接收這些數(shù)據(jù)并進(jìn)行數(shù)據(jù)融合。成員節(jié)點(diǎn)向簇首發(fā)送的數(shù)據(jù)主要包括：傳感器采集的信息、節(jié)點(diǎn)剩余能量、節(jié)點(diǎn)ID等，為避免數(shù)據(jù)沖突，各成員節(jié)點(diǎn)基于TDMA的低能耗MAC協(xié)議給每個(gè)成員節(jié)點(diǎn)分配通訊時(shí)槽，只有在自己的時(shí)槽內(nèi)，節(jié)點(diǎn)才打開無線發(fā)送模塊和簇首節(jié)點(diǎn)通信，其余通訊時(shí)槽內(nèi)此模塊一直處于關(guān)閉狀態(tài)，從而節(jié)省能量。由于節(jié)點(diǎn)通訊采用廣播方式，因此節(jié)點(diǎn)在和自己的CH通信時(shí)，其余鄰居簇的節(jié)點(diǎn)也可能接收到此信息，為避免簇間干擾，每個(gè)簇在通訊過程中都使用域代碼為唯一的通訊標(biāo)識(shí)碼，節(jié)點(diǎn)根據(jù)該編碼過濾掉收到的非本簇簇內(nèi)路由信息。根據(jù)自由空間通信模型可知發(fā)送bit能耗和接收能耗分別為： (1) (2)其中表示發(fā)送bit數(shù)據(jù)到距離為的接收端的能耗，為接收bit數(shù)據(jù)的能耗。簇首接收完全部成員節(jié)點(diǎn)的數(shù)據(jù)包后進(jìn)行數(shù)據(jù)融合，消耗的能量為 (3)其中為融合每bit所用的能量。簇頭將數(shù)據(jù)融合后，進(jìn)入簇間路由階段。簇間路由時(shí)，各簇的簇首不直接和遠(yuǎn)端基站通訊，而是通過鄰居簇首以多跳方式向基站發(fā)送。路由方向?yàn)閳A環(huán)等級(jí)高的簇首向圓環(huán)等級(jí)低的簇首發(fā)送融合后的數(shù)據(jù)包，圓環(huán)等級(jí)低的簇首接收到融合數(shù)據(jù)包后加入本級(jí)別節(jié)點(diǎn)的傳感數(shù)據(jù)，再轉(zhuǎn)發(fā)到圓環(huán)等級(jí)更低的簇首。圓環(huán)等級(jí)最低的簇首，把轉(zhuǎn)接到的及自身簇內(nèi)數(shù)據(jù)直接發(fā)送到基站。由于簇首以剩余能量進(jìn)行競(jìng)選，簇首在簇內(nèi)的位置不定，即在圓環(huán)內(nèi)的位置也不定。在簇間路由時(shí)，高級(jí)圓環(huán)里的簇首要把數(shù)據(jù)轉(zhuǎn)發(fā)到低級(jí)圓環(huán)簇首，兩者的通信距離必須小于節(jié)點(diǎn)的最大通信距離?？紤]最不理想狀況，相鄰圓環(huán)等級(jí)簇首間的距離最大為R，其中R為每級(jí)圓環(huán)劃分的徑向距離（見圖2），即 (4)其中Rmax為圓環(huán)劃分的最大徑向距離，dmax為節(jié)點(diǎn)的最大通信距離。簇間路由完成后，此輪的通信亦完成，基站再根據(jù)節(jié)點(diǎn)分布情況，廣播圓環(huán)劃分規(guī)則，進(jìn)入下一輪通信。3.仿真及分析3.1仿真環(huán)境及參數(shù)在本實(shí)驗(yàn)中，采用NS2進(jìn)行系統(tǒng)仿真，設(shè)有150個(gè)節(jié)點(diǎn)，隨機(jī)部署于3 0 03 0 0的方形區(qū)域，初始能量設(shè)為5J，數(shù)據(jù)包長(zhǎng)度為500 bit, , ，節(jié)點(diǎn)單跳最大通信范圍設(shè)為150m，則目標(biāo)區(qū)域中圓環(huán)的徑向跨度最大為75m。根據(jù)非均勻分簇的思想，距離等級(jí)越低的圓環(huán)其徑向跨度越小，本算法中徑向跨度比例為1.2:1，即每向外一級(jí)，其徑向跨度擴(kuò)大0.2倍。在仿真中，將本文提出的COLEH與LEACH協(xié)議進(jìn)行比較分析。3.2仿真結(jié)果及分析定義網(wǎng)絡(luò)壽命為從網(wǎng)絡(luò)開始工作時(shí)刻起到最后一個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)死亡那一刻的時(shí)間跨度。圖3為兩種算法的時(shí)間與生存的節(jié)點(diǎn)數(shù)的關(guān)系仿真結(jié)果。從圖中可以看到，LEACH協(xié)議的網(wǎng)絡(luò)壽命為4518輪，而COLEH算法的網(wǎng)絡(luò)壽命為5673輪，延長(zhǎng)了約25%。在LEACH協(xié)議里，出現(xiàn)第一個(gè)死亡節(jié)點(diǎn)的時(shí)間是第1854輪，而在COLEH算法里，時(shí)間是3481輪,比LEACH協(xié)議延長(zhǎng)了約87%。圖3.生存節(jié)點(diǎn)數(shù)Fig.3. Survival nodes圖4為時(shí)間與網(wǎng)絡(luò)中全部節(jié)點(diǎn)的剩余能量關(guān)系仿真結(jié)果圖，從圖中可以看出COLEH協(xié)議節(jié)省了每輪的分簇能耗，節(jié)約了能量，從而延長(zhǎng)了整個(gè)網(wǎng)絡(luò)的壽命。圖4.剩余能量Fig.4. residual energy4.結(jié)論本文針對(duì)無線傳感器網(wǎng)絡(luò)中低能耗的要求，對(duì)傳統(tǒng)的分層協(xié)議進(jìn)行分析，提出了一種新的對(duì)分簇及簇首選擇進(jìn)行優(yōu)化的路由算法，使節(jié)點(diǎn)的能量消耗更均衡，有效地避免了個(gè)別節(jié)點(diǎn)死亡過快。仿真結(jié)果表明，COLEH算法比LEACH協(xié)議具有更長(zhǎng)的網(wǎng)絡(luò)壽命，大大提高了無線傳感器網(wǎng)絡(luò)的整體性能。References1 孫利民，李建中，陳渝等無線傳感器網(wǎng)絡(luò) M 北京： 清華大學(xué)出版社，20052 Younis O，F(xiàn)ahmy SHeed：a hybrid，energy -efficient，distributed clustering approach for Ad Hoc sensor networksJIEEE Transactions on Mobile Computing,2004，a(4)：366-3793沈波.無線傳感器網(wǎng)絡(luò)分簇路由協(xié)議J. Journal of Software，Vo117，No7，July 2006，PP1588-1600.4 Eimon A R A，Hong C S，Suda TEAREC：energy aware routing with efficient clustering for sensor networksCIn：Proceedings of the 3rd IEEE Consumer Communications and Networking ConferenceLasvegas , USA：IEEE，2006330-3355 Wendi Rabiner Heinzelman,Anantha Chandrakasan, and HariBalakrishnan. Energy-Efficient Communication Protocol for Wireless Micro sensor NetworksC. In :HICSS Proceedings of the 33rd Hawaii International Conference on System Sciences，Hawaii,USA,2000.6 Muruganathan S D，Ma D C F，Bhasin R I，F(xiàn)apojuwo A OA centralized energy-efficient routing protocol for wireless sensor networksJIEEE Radio Communication Magazine，2005，43(3)：8-l37 李成法，陳貴海，葉懋，吳杰. 一種基于非均勻分簇的無線傳感器網(wǎng)絡(luò)路由協(xié)議J.計(jì)算機(jī)學(xué)報(bào)，Vo1.30 No.1 Jan.2007, pp.28-36.8 Heinzelman W R, Chandrakasan A, Balakrishnan HEnergy-efficient communication