一種基于LEACH改進(jìn)的均勻分簇路由算法

鄒 虹，彭國龍

（重慶郵電大學(xué)通信與信息學(xué)院，重慶 400065）

一種基于LEACH改進(jìn)的均勻分簇路由算法

鄒 虹，彭國龍

（重慶郵電大學(xué)通信與信息學(xué)院，重慶 400065）

針對(duì)LEACH分簇算法簇頭分布位置不均勻以及節(jié)點(diǎn)耗能不均衡等缺點(diǎn)，提出一種雙SINK節(jié)點(diǎn)均勻分簇算法DSUC。該算法首先利用無信標(biāo)節(jié)點(diǎn)ABC定位算法，計(jì)算出每個(gè)節(jié)點(diǎn)的坐標(biāo)位置，再根據(jù)理論得出的最佳簇頭數(shù)將整個(gè)無線網(wǎng)絡(luò)區(qū)域盡可能地劃分成均等的區(qū)域，然后SINK節(jié)點(diǎn)通過各節(jié)點(diǎn)坐標(biāo)選舉各區(qū)域內(nèi)離質(zhì)心最近的節(jié)點(diǎn)作為第一輪簇頭節(jié)點(diǎn)。在區(qū)域的對(duì)稱位置上設(shè)置2個(gè)SINK節(jié)點(diǎn)，輪流交替工作，能有效解決“熱區(qū)”問題。

LEACH;雙SINK節(jié)點(diǎn);ABC無信標(biāo)節(jié)點(diǎn)定位;均勻分簇

經(jīng)過大量國內(nèi)外研究人員的努力已經(jīng)在LEACH（Low Energy Adaptive Clustering Hierarchy）算法的基礎(chǔ)上研究出很多路由改進(jìn)算法。LEACH作為第一個(gè)基于分簇的路由算法，該算法采用集中式分簇方式，通過每個(gè)節(jié)點(diǎn)產(chǎn)生一個(gè)0～1的隨機(jī)數(shù)，與一個(gè)設(shè)定好的門限值T（n）相比較，小于當(dāng)前輪的T（n）的節(jié)點(diǎn)就當(dāng)選為簇頭，LEACH沒有考慮節(jié)點(diǎn)的剩余能量，能量少的節(jié)點(diǎn)當(dāng)選簇頭時(shí)會(huì)快速的消耗能量，而且很有可能兩個(gè)簇頭相隔很近甚至是鄰居節(jié)點(diǎn)，造成簇頭節(jié)點(diǎn)的重疊現(xiàn)象［1］。文獻(xiàn)［2］提出一種以節(jié)點(diǎn)剩余能量和隨機(jī)數(shù)共同來控制產(chǎn)生T（n）的算法DCHS，該算法進(jìn)一步改進(jìn)解決了當(dāng)所有節(jié)點(diǎn)的能量都變的很少時(shí)，T（n）會(huì)變小從而導(dǎo)致當(dāng)選簇頭的機(jī)率變小的問題。文獻(xiàn)［3］中提出一種基于雙簇首的路由算法，主簇首負(fù)責(zé)接收簇內(nèi)節(jié)點(diǎn)的數(shù)據(jù)，然后再由主簇首把數(shù)據(jù)發(fā)送給副簇首進(jìn)行數(shù)據(jù)融合，該算法把接收和融合的步驟分開，節(jié)省簇頭選舉開銷，但是大量數(shù)據(jù)從主簇首到副簇首的傳輸耗能非常大。文獻(xiàn)［4］中針對(duì)熱區(qū)問題提出一種非均勻的分簇方式，即離SINK節(jié)點(diǎn)越近組成的簇越小，越遠(yuǎn)簇越大，大簇中簇內(nèi)節(jié)點(diǎn)通過多跳與簇頭通信，且遠(yuǎn)簇頭通過近簇頭中繼和SINK節(jié)點(diǎn)通信，該算法確實(shí)能起到均衡能量的作用，但是算法過于復(fù)雜，控制開銷較大。

本文針對(duì)LEACH算法分簇不均勻以及靠近SINK節(jié)點(diǎn)和遠(yuǎn)離SINK節(jié)點(diǎn)的簇能耗不均衡等問題提出一種基于雙SINK節(jié)點(diǎn)均勻分簇算法DSUC（Double Sink Uniform Clustering），通過 ABC定位算法確定節(jié)點(diǎn)坐標(biāo)，SINK節(jié)點(diǎn)把網(wǎng)絡(luò)區(qū)域盡量分成均等的若干小區(qū)域，選取處于各區(qū)域質(zhì)心的節(jié)點(diǎn)或離質(zhì)心最近的節(jié)點(diǎn)作為簇頭節(jié)點(diǎn)，然后簇頭節(jié)點(diǎn)廣播當(dāng)選簇頭信息，節(jié)點(diǎn)根據(jù)接收到信息的強(qiáng)弱來決定加入到哪個(gè)簇，雙SINK以固定時(shí)間間隔輪流工作，這個(gè)算法能使能量消耗更加均衡。

1 系統(tǒng)模型

1.1 網(wǎng)絡(luò)模型

本文研究的網(wǎng)絡(luò)為一個(gè)a×a的正方形區(qū)域，2個(gè)SINK節(jié)點(diǎn)位于區(qū)域左右邊中垂線之上，處于對(duì)稱位置上，如圖1所示，為了便于研究和仿真，對(duì)網(wǎng)絡(luò)參數(shù)和節(jié)點(diǎn)做如下假設(shè):

1）所有節(jié)點(diǎn)同構(gòu)，具有數(shù)據(jù)處理融合功能，能量有限且相等，處于同一平面上。

圖1 DSUC算法網(wǎng)絡(luò)區(qū)域劃分圖

2）節(jié)點(diǎn)能通過RSSI（接收信號(hào)強(qiáng)度指示）來計(jì)算與鄰居節(jié)點(diǎn)以及基站的距離，發(fā)射功率可控。

3）普通節(jié)點(diǎn)較均勻布置，一旦布置就不再移動(dòng)。

4）雙SINK節(jié)點(diǎn)能量無限，位于網(wǎng)絡(luò)區(qū)域外對(duì)稱位置，且有一定的距離。

1.2 無線通信耗能模型及改進(jìn)算法耗能分析

DSUC算法中節(jié)點(diǎn)的能量消耗采用無線傳輸能量消耗模型計(jì)算，發(fā)送數(shù)據(jù)耗能要稍大于接收數(shù)據(jù)所需能量，通信距離大于d0采用多徑衰落信道模型，小于d0則使用自由空間模型。節(jié)點(diǎn)發(fā)送kbit數(shù)據(jù)的耗能為

式中:k為數(shù)據(jù)比特?cái)?shù)，d為通信的距離，Eelse為收發(fā)電路的基本功耗系數(shù)，εfs，εamp分別為自由空間和多徑衰落信道模型功率放大器的能量消耗常數(shù)。

節(jié)點(diǎn)接收節(jié)點(diǎn)發(fā)送kbit數(shù)據(jù)的耗能為作為DSUC算法的中SINK節(jié)點(diǎn)輪流工作的時(shí)間間隔。

2 改進(jìn)算法描述及實(shí)現(xiàn)

2.1 簇區(qū)域的劃分

2.2 ABC無信標(biāo)節(jié)點(diǎn)定位算法

信標(biāo)節(jié)點(diǎn)是已知自身絕對(duì)位置的節(jié)點(diǎn)，其坐標(biāo)可通過GPS、北斗衛(wèi)星導(dǎo)航等系統(tǒng)確定，通過信標(biāo)節(jié)點(diǎn)為其他節(jié)點(diǎn)提供參考坐標(biāo)，能得到各個(gè)節(jié)點(diǎn)在地球上的確切位置。帶信標(biāo)節(jié)點(diǎn)定位方法雖然能較精確地定位，但由于對(duì)節(jié)點(diǎn)的硬件條件要求高以及GPS等導(dǎo)航系統(tǒng)接收設(shè)備的成本高等不足，而且很多情況下不需要確切的位置，所以低成本的無信標(biāo)定位算法得到了較好的研究和發(fā)展［8］。

ABC定位算法是一種基于無信標(biāo)定位的算法，至少知道2個(gè)節(jié)點(diǎn)的坐標(biāo)位置，從而推知其他節(jié)點(diǎn)的坐標(biāo)，節(jié)點(diǎn)發(fā)送信息包括自己的坐標(biāo)、離SINK節(jié)點(diǎn)的距離、節(jié)點(diǎn)ID號(hào)等，未確定坐標(biāo)的節(jié)點(diǎn)接收其他節(jié)點(diǎn)的信息，若接收到的坐標(biāo)信息為空，說明該節(jié)點(diǎn)亦未定位，則丟棄該信息，接到2個(gè)帶坐標(biāo)節(jié)點(diǎn)的信息后就可以確實(shí)自己的坐標(biāo)。在正式進(jìn)行坐標(biāo)計(jì)算之前，假設(shè):設(shè)最左下角的節(jié)點(diǎn)為坐標(biāo)原點(diǎn)，所有其他的節(jié)點(diǎn)都在原點(diǎn)的右上方，且各節(jié)點(diǎn)通過RSSI已知到SINK節(jié)點(diǎn)的距離。由2個(gè)節(jié)點(diǎn)確定第三個(gè)節(jié)點(diǎn)坐標(biāo)時(shí)有以下3種處理情況:

1）簡單舍去多余值:A，B節(jié)點(diǎn)坐標(biāo)以及2個(gè)點(diǎn)到C的距離已知，求C點(diǎn)的坐標(biāo)，根據(jù)距離關(guān)系，除了C點(diǎn)以外還會(huì)有一個(gè)C'點(diǎn)，這2個(gè)節(jié)點(diǎn)關(guān)于AB直線對(duì)稱，C'點(diǎn)可能只是C點(diǎn)一個(gè)鏡像，也有可能正好有這么一個(gè)點(diǎn)，如果C'點(diǎn)的橫坐標(biāo)值為負(fù)，可以簡單地舍去。

2）距離判斷取值:若C'點(diǎn)的橫坐標(biāo)為正值，如果真有C'這個(gè)節(jié)點(diǎn)且2個(gè)點(diǎn)的橫坐標(biāo)不相等，那么可以通過節(jié)點(diǎn)和SINK節(jié)點(diǎn)的距離大小來判斷到底哪個(gè)橫坐標(biāo)是屬于節(jié)點(diǎn)C哪個(gè)是屬于C'，即距離越小，橫坐標(biāo)就越大，相反就越小。

3）A，B節(jié)點(diǎn)處于同一水平面上，因此根據(jù)距離得到的C和C'的橫坐標(biāo)相等，那么就說明這2個(gè)點(diǎn)位于SINK節(jié)點(diǎn)的同一個(gè)輻射圓上，那么它們距SINK節(jié)點(diǎn)的距離相等，因此就無法判斷出到底哪個(gè)坐標(biāo)是屬于哪個(gè)節(jié)點(diǎn)了。應(yīng)該避免這種情況發(fā)生，具體做法是:節(jié)點(diǎn)對(duì)接收到的2個(gè)坐標(biāo)信息比較其縱坐標(biāo)，如果相等，則要丟棄一個(gè)，重新接收一個(gè)，直到不相等為止。

建立平面直角坐標(biāo)系，如圖1的坐標(biāo)系，擬定2個(gè)節(jié)點(diǎn)的坐標(biāo)位置，為了使計(jì)算通用化，設(shè)A（a，b），B（c，d）兩點(diǎn)已知，其到節(jié)點(diǎn)C（x，y）的距離為l1，l2，根據(jù)距離公式得到

利用坐標(biāo)移位技巧，即把ABC組成的三角形整體移位，將一個(gè)節(jié)點(diǎn)（選接收到第一個(gè)帶坐標(biāo)信息的節(jié)點(diǎn)）移到原點(diǎn)，計(jì)算出C的坐標(biāo)后再逆向移回。把A點(diǎn)移到原點(diǎn)，得到下面2個(gè)等式:

令m=c－a，n=d－b，解得x，y后再分別加上a，b，最終得到的x，y為

確定好所有節(jié)點(diǎn)的坐標(biāo)位置，是選舉離質(zhì)心最近的簇頭的關(guān)鍵步驟，接下來的任務(wù)就是SINK節(jié)點(diǎn)把區(qū)域內(nèi)各節(jié)點(diǎn)的坐標(biāo)和已確定好的質(zhì)心相比較，選一個(gè)最近的節(jié)點(diǎn)作為簇頭，因?yàn)榫W(wǎng)絡(luò)剛建立階段各節(jié)點(diǎn)的能量是相等的，所以可以只考慮位置信息。

2.3 簇頭節(jié)點(diǎn)的確定

簇區(qū)域劃分后，然后利用定位算法把所有節(jié)點(diǎn)的坐標(biāo)計(jì)算出來，各節(jié)點(diǎn)根據(jù)分簇區(qū)域的邊界值數(shù)據(jù)，確定自己屬于哪個(gè)簇區(qū)域，SINK節(jié)點(diǎn)再把各區(qū)域的質(zhì)心確定出來，然后SINK節(jié)點(diǎn)將各個(gè)區(qū)域的質(zhì)心坐標(biāo)和區(qū)域內(nèi)的節(jié)點(diǎn)依次比較，得到一個(gè)離質(zhì)心最近的一個(gè)節(jié)點(diǎn)作為簇頭，這樣就完成了簇頭節(jié)點(diǎn)的第一輪選舉，接下來的第二輪、第三輪……，DSUC算法將由本輪簇頭通過節(jié)點(diǎn)剩余能量以及離簇頭節(jié)點(diǎn)的距離參數(shù)進(jìn)行下輪簇頭的選舉。改進(jìn)算法簇頭選舉經(jīng)過劃分均等區(qū)域、節(jié)點(diǎn)定位、簇頭選舉等過程，為了便于理解，畫出算法簇頭選舉流程圖如圖2所示。

圖2 簇頭選舉流程圖

2.4 簇形成及數(shù)據(jù)傳輸

簇頭選舉好之后，簇頭以區(qū)域半徑廣播當(dāng)選信息給周圍節(jié)點(diǎn)，節(jié)點(diǎn)根據(jù)接收信號(hào)強(qiáng)度決定加入哪個(gè)簇，邊界上的節(jié)點(diǎn)存在競爭現(xiàn)象，可能加入其他簇中，數(shù)據(jù)傳輸采用和傳統(tǒng)的LEACH相同傳輸方法，即簇頭節(jié)點(diǎn)直接和SINK節(jié)點(diǎn)通信，簇內(nèi)節(jié)點(diǎn)在自己的TDMA時(shí)隙單跳內(nèi)發(fā)送數(shù)據(jù)給簇頭節(jié)點(diǎn)，在其他節(jié)點(diǎn)時(shí)隙處于睡眠狀態(tài)。

3 實(shí)驗(yàn)仿真及分析

本文采用NS2網(wǎng)絡(luò)仿真工具進(jìn)行仿真，對(duì)LEACH算法和DSUC算法進(jìn)行性能比較，主要分析在單個(gè)SINK節(jié)點(diǎn)以及雙個(gè)SINK節(jié)點(diǎn)下2個(gè)算法第一個(gè)節(jié)點(diǎn)死亡的時(shí)間和最后一個(gè)節(jié)點(diǎn)死亡時(shí)間，以及網(wǎng)絡(luò)總能量的消耗等信息。

3.1 仿真場景及參數(shù)設(shè)置

3.2 仿真結(jié)果分析

圖3對(duì)LEACH協(xié)議、DSUC協(xié)議下單個(gè)SINK節(jié)點(diǎn)情況和雙SINK節(jié)點(diǎn)情況分別進(jìn)行仿真，得出存活節(jié)點(diǎn)個(gè)數(shù)與仿真輪數(shù)的關(guān)系，從圖中可以看出LEACH在300輪左右的時(shí)候就出現(xiàn)了第一個(gè)節(jié)點(diǎn)死亡，而單個(gè)SINK節(jié)點(diǎn)的改進(jìn)算法第一個(gè)節(jié)點(diǎn)死亡出現(xiàn)在350輪左右的時(shí)候，有一定的提高，但雙SINK節(jié)點(diǎn)的改進(jìn)算法仿真到640輪的時(shí)候第一個(gè)節(jié)點(diǎn)才死亡，大大延長了網(wǎng)絡(luò)的壽命，比LEACH第一個(gè)節(jié)點(diǎn)死亡延長一倍多，這是因?yàn)镈SUC算法簇頭選舉不但參考了剩余能量，還使用了雙SINK節(jié)點(diǎn)均衡節(jié)能解決了熱區(qū)問題，之所以和理論有差別是因?yàn)镾INK節(jié)點(diǎn)之間交替工作會(huì)產(chǎn)生額外的能量消耗，單SINK節(jié)點(diǎn)下的改進(jìn)算法也比LEACH的時(shí)間延長了16%，當(dāng)LEACH算法和單SINK節(jié)點(diǎn)的改進(jìn)算法結(jié)束網(wǎng)絡(luò)生命期時(shí)，DSUC算法還剩余100多個(gè)可用節(jié)點(diǎn)，可以看到LEACH節(jié)點(diǎn)的個(gè)數(shù)死亡的速度最快，單SINK節(jié)點(diǎn)的改進(jìn)算法次之，雙SINK節(jié)點(diǎn)下的DSUC算法下降最平緩。

圖3 剩余節(jié)點(diǎn)個(gè)數(shù)隨輪數(shù)變化的關(guān)系

圖4是網(wǎng)絡(luò)中整個(gè)網(wǎng)絡(luò)消耗能量的多少和仿真輪數(shù)的變化關(guān)系，在仿真的開始發(fā)現(xiàn)DSUC算法單SINK節(jié)點(diǎn)和雙SINK節(jié)點(diǎn)兩種情況下耗能都要比LEACH算法稍多，這是因?yàn)槌跏蓟A段改進(jìn)算法要進(jìn)行區(qū)域的劃分及節(jié)點(diǎn)的定位會(huì)消耗少部分能量，隨著仿真時(shí)間的延長，改進(jìn)算法單SINK節(jié)點(diǎn)相對(duì)于LEACH有一定改善，這是因?yàn)椴捎米罴逊执財(cái)?shù)進(jìn)行均勻分簇，從而縮短了通信距離，但是不能解決“熱區(qū)問題”，因此在500輪之后，改進(jìn)算法的雙SINK節(jié)點(diǎn)情況優(yōu)勢越來越明顯，這主要是因?yàn)椴捎秒pSINK節(jié)點(diǎn)使得簇頭發(fā)送給SINK節(jié)點(diǎn)的平均距離減少，有效解決了“熱區(qū)問題”，消耗的能量也減少了，相比后面延長網(wǎng)絡(luò)壽命的功勞，DSUC算法初始化階段所消耗的能量代價(jià)是值得的。將圖3和圖4相比較，當(dāng)運(yùn)行到1 800輪左右時(shí)，剩余節(jié)點(diǎn)的個(gè)數(shù)100多個(gè)，剩余能量應(yīng)小于50 J，因?yàn)檫@100個(gè)節(jié)點(diǎn)運(yùn)行時(shí)也要消耗能量，而從圖4中的結(jié)果正好驗(yàn)證了理論的正確性，運(yùn)行到1 600輪的時(shí)候能量就已經(jīng)消耗了60 J了，說明剩余節(jié)點(diǎn)剩余的能量為節(jié)點(diǎn)初始能量的4/5左右。

圖4 網(wǎng)絡(luò)能量的消耗隨輪數(shù)的變化

4 結(jié)束語

本文對(duì)LEACH算法進(jìn)行了改進(jìn)，提出了一種分簇均勻更加節(jié)能的路由協(xié)議，采用信標(biāo)節(jié)點(diǎn)定位算法確定所有節(jié)點(diǎn)的位置，從而確定簇頭節(jié)點(diǎn)的位置，達(dá)到均勻分簇，其次是采用雙SINK節(jié)點(diǎn)均衡能量。該算法雖然能有效搞高網(wǎng)絡(luò)壽命等性能，但也存在些許不足，比如定位以及仿真模型都定位在一個(gè)正方形的規(guī)則圖形之內(nèi)，現(xiàn)實(shí)中傳感器的網(wǎng)絡(luò)布置區(qū)域很少會(huì)有這個(gè)規(guī)則，因此如何計(jì)算不規(guī)則區(qū)域的節(jié)點(diǎn)坐標(biāo)和簇區(qū)域的劃分將是本課題下一步所要研究的內(nèi)容。

:

［1］孫利民，李建中.無線傳感器網(wǎng)絡(luò)［M］.北京:清華大學(xué)出版社，2005.

［2］沈波，張世永，鐘亦平.無線傳感器網(wǎng)絡(luò)分簇路由協(xié)議［J］.軟件學(xué)報(bào)，2006，29（9）:57-60.

［3］李輝，李臘元，李方云.一種基于低能量的雙簇首WSN路由算法［J］.武漢理工大學(xué)學(xué)報(bào)，2009，33（3）:450-453.

［4］吳振華，尹志軍.基于優(yōu)化簇半徑的WSNs非均勻分簇路由［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2010，31（15）:3374-3378.

［5］鐘智，樊曉平，羅大庸，等.一種基于網(wǎng)格的無線傳感器網(wǎng)絡(luò)分簇路由協(xié)議研究［J］.傳感器與微系統(tǒng)，2011，30（12）:18-20.

［6］HEINZELMAN W R，KULIK J，BALAKRISHNAN H.Adaptive protocols for information dissemination in wireless sensor networks［EB/OL］.［2012-06-20］.http://nms.1cs.mit.edu/papers/spin-mobicom99.html.

［7］何國圓，陳滌.基于最優(yōu)簇首的高能效傳感器網(wǎng)絡(luò)路由協(xié)議［J］.傳感器技術(shù)學(xué)報(bào)，2008，21（10）:1739-1743.

［8］黃小軍，鄭霖.無線傳感器網(wǎng)絡(luò)物理層的主從同步技術(shù)研究［J］.電視技術(shù)，2011，35（11）:92-94.

Improved Uniform Clustering Routing Algorithm Based on LEACH

ZOU Hong，PENG Guolong

（Communication and Information Sciences，Chongqing University of Posts and Telecommunications，Chongqing 400065，China）

In order to solve the problems that the position of cluster nodes distribute uneven and the nodes energy consumption imbalance，a uniform clustering algorithm with double SINK nodes（DSUC）is proposed.This algorithm includes three steps.Firstly，the no beacon node positioning algorithm ABC is used to calculating coordinate for each node.Then，according to the optimal cluster head nodes from survey papers，the entire wireless area divided into several small areas as much as possible the measure of each area is equal.Finally，the SINK node chose the node which is closest to the centroid of each small area as cluster head node in first round.In the region of the symmetric position two SINK nodes are set down，the two SINK nodes can effectively solve the problem of unbalanced energy consumption by work alternate.

LEACH;double SINK nodes;no beacon node positioning algorithm ABC;uniform clustering

TP393

A

【本文獻(xiàn)信息】鄒虹，彭國龍.一種基于LEACH改進(jìn)的均勻分簇路由算法［J］.電視技術(shù)，2013，37（3）.

國家自然科學(xué)基金項(xiàng)目（61171190）

彭國龍（1985— ），碩士生，主研無線傳感器網(wǎng)絡(luò);

鄒 虹（1970— ），女，副教授，碩士生導(dǎo)師，主研移動(dòng)通信和無線傳感器網(wǎng)絡(luò)。

責(zé)任編輯:任健男

2012－09－20