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

鄒 虹，彭國龍

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

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

鄒 虹，彭國龍

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

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

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

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

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

1 系統(tǒng)模型

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

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

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

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

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

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

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

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

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

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

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

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

2.1 簇區(qū)域的劃分

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

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

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

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

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

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

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

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

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

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

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

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

圖2 簇頭選舉流程圖

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

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

3 實驗仿真及分析

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

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

3.2 仿真結(jié)果分析

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

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

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

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

4 結(jié)束語

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

:

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

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

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

［4］吳振華，尹志軍.基于優(yōu)化簇半徑的WSNs非均勻分簇路由［J］.計算機(jī)工程與設(shè)計，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é)報，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é)基金項目（61171190）

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

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

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

2012－09－20