一種基于LEACH改進的均勻分簇路由算法

鄒 虹，彭國龍

（重慶郵電大學通信與信息學院，重慶 400065）

一種基于LEACH改進的均勻分簇路由算法

鄒 虹，彭國龍

（重慶郵電大學通信與信息學院，重慶 400065）

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

LEACH;雙SINK節點;ABC無信標節點定位;均勻分簇

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

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

1 系統模型

1.1 網絡模型

本文研究的網絡為一個a×a的正方形區域，2個SINK節點位于區域左右邊中垂線之上，處于對稱位置上，如圖1所示，為了便于研究和仿真，對網絡參數和節點做如下假設:

1）所有節點同構，具有數據處理融合功能，能量有限且相等，處于同一平面上。

圖1 DSUC算法網絡區域劃分圖

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

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

4）雙SINK節點能量無限，位于網絡區域外對稱位置，且有一定的距離。

1.2 無線通信耗能模型及改進算法耗能分析

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

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

節點接收節點發送kbit數據的耗能為作為DSUC算法的中SINK節點輪流工作的時間間隔。

2 改進算法描述及實現

2.1 簇區域的劃分

2.2 ABC無信標節點定位算法

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

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

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

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

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

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

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

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

確定好所有節點的坐標位置，是選舉離質心最近的簇頭的關鍵步驟，接下來的任務就是SINK節點把區域內各節點的坐標和已確定好的質心相比較，選一個最近的節點作為簇頭，因為網絡剛建立階段各節點的能量是相等的，所以可以只考慮位置信息。

2.3 簇頭節點的確定

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

圖2 簇頭選舉流程圖

2.4 簇形成及數據傳輸

簇頭選舉好之后，簇頭以區域半徑廣播當選信息給周圍節點，節點根據接收信號強度決定加入哪個簇，邊界上的節點存在競爭現象，可能加入其他簇中，數據傳輸采用和傳統的LEACH相同傳輸方法，即簇頭節點直接和SINK節點通信，簇內節點在自己的TDMA時隙單跳內發送數據給簇頭節點，在其他節點時隙處于睡眠狀態。

3 實驗仿真及分析

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

3.1 仿真場景及參數設置

3.2 仿真結果分析

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

圖3 剩余節點個數隨輪數變化的關系

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

圖4 網絡能量的消耗隨輪數的變化

4 結束語

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

:

［1］孫利民，李建中.無線傳感器網絡［M］.北京:清華大學出版社，2005.

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

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

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

［5］鐘智，樊曉平，羅大庸，等.一種基于網格的無線傳感器網絡分簇路由協議研究［J］.傳感器與微系統，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］何國圓，陳滌.基于最優簇首的高能效傳感器網絡路由協議［J］.傳感器技術學報，2008，21（10）:1739-1743.

［8］黃小軍，鄭霖.無線傳感器網絡物理層的主從同步技術研究［J］.電視技術，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

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

國家自然科學基金項目（61171190）

彭國龍（1985— ），碩士生，主研無線傳感器網絡;

鄒 虹（1970— ），女，副教授，碩士生導師，主研移動通信和無線傳感器網絡。

責任編輯:任健男

2012－09－20