基于層次劃分的無線傳感網(wǎng)絡(luò)拓?fù)淇刂扑惴ǚ治霭咐夸汿OC\o"1-3"\h\u3294基于層次劃分的無線傳感網(wǎng)絡(luò)拓?fù)淇刂扑惴ǚ治霭咐?1188151.1LEACH算法 1256621.2LEACH算法的改進(jìn)算法 2174811.3HEED算法 3層次劃分的拓?fù)淇刂扑惴ㄒ部梢员唤凶龇执貦C制。1.1LEACH算法LEACH（Low-EnergyAdaptiveClusteringHierarchy）算法是一種典型的分層拓?fù)淇刂扑惴?。LEACH算法會把節(jié)點分簇，再根據(jù)一定的概率選擇簇頭節(jié)點，把相鄰的那些節(jié)點組成和一個簇。在這個簇內(nèi)的節(jié)點會把它們探查到的數(shù)據(jù)發(fā)送到簇頭處，再由簇頭把數(shù)據(jù)融合了以后發(fā)送到基站處。LEACH算法讓網(wǎng)絡(luò)內(nèi)部的所有節(jié)點都能等概率的成為簇頭，以此來節(jié)約所有節(jié)點的平均能量并延長網(wǎng)絡(luò)的生存壽命。 LEACH算法的基本思路就是在每輪的簇頭選舉的時候，節(jié)點能否擔(dān)任簇頭完全是由公式進(jìn)行決定的。公式如下所示：(3-1)式中：——節(jié)點擔(dān)任簇頭節(jié)點所要達(dá)到的概率門限。 ——簇頭數(shù)量在所有節(jié)點數(shù)量當(dāng)中占有的百分比數(shù)。 ——簇頭選舉一共要進(jìn)行的輪數(shù)。 ——在前r-1輪的選舉當(dāng)中都沒有當(dāng)選過簇頭節(jié)點的節(jié)點的集合。所以就代表了本輪到目前為止的所有選舉當(dāng)中當(dāng)選過簇頭的節(jié)點數(shù)量。每輪都會選擇百分之的節(jié)點擔(dān)任簇頭節(jié)點，在先前幾輪當(dāng)中已經(jīng)成為過簇頭的節(jié)點便不能再被選則成為簇頭節(jié)點。在輪之后，網(wǎng)絡(luò)中的所有節(jié)點基本上都成為過簇頭節(jié)點，并且它們剩余的能量應(yīng)當(dāng)相差不多。這時進(jìn)行簇首節(jié)點的重新選舉，重組所有簇結(jié)構(gòu)。簇頭節(jié)點會發(fā)出消息宣布自己成為簇頭節(jié)點，這時其它的節(jié)點在接收到簇頭節(jié)點的消息之后，就會選擇離自己最近、信號最強的那個簇首節(jié)點加入到它的簇中。LEACH算法的流程是先選舉簇頭節(jié)點，選舉完成后簇頭節(jié)點會發(fā)布消息通知其它節(jié)點自己成為了簇頭節(jié)點。這時其它非簇頭節(jié)點會選擇加入距離自己最近的那個簇頭節(jié)點所在的簇，當(dāng)其它節(jié)點都加入到簇中以后簇頭節(jié)點會產(chǎn)生一個TDMA調(diào)度消息，簇頭節(jié)點通過這個調(diào)度信息來控制非簇頭節(jié)點在特定的時間傳輸信息，而非簇頭節(jié)點不在自己傳輸?shù)臅r間內(nèi)會進(jìn)入休眠模式來節(jié)省自身剩余的能量。傳輸了一段時間之后簇頭節(jié)點就會對它收集到的那些數(shù)據(jù)進(jìn)行整合并把整合后的內(nèi)容發(fā)送到基站處。因此簇頭節(jié)點的能量消耗是很大的，所以LEACH算法并不適合長時間的任務(wù)。在傳輸一段時間后，網(wǎng)絡(luò)里的所有節(jié)點都會停止發(fā)送數(shù)據(jù)來進(jìn)行下一次的簇頭選舉。圖3-2LEACH算法流程圖通過了解LEACH算法的選舉過程，我們可以分析出雖然網(wǎng)絡(luò)中的所有節(jié)點都有同樣的機會擔(dān)任簇頭節(jié)點的位置，但是在選舉時并沒有考慮節(jié)點的具體分布，這就容易導(dǎo)致簇頭節(jié)點的分布不均勻同時使得網(wǎng)絡(luò)的剩余能量分布也不均勻，從而使得剩余能量少的節(jié)點過早死亡，使網(wǎng)絡(luò)的覆蓋并不完整，降低了網(wǎng)絡(luò)的生存周期。1.2LEACH算法的改進(jìn)算法對于LEACH算法在選舉簇頭的時候并沒有考慮到節(jié)點當(dāng)前剩余的能量多少的問題，在LEACH的改進(jìn)算法當(dāng)中把節(jié)點當(dāng)選簇頭節(jié)點的概率門限定為：(3-2)式子當(dāng)中的表示節(jié)點在第r輪簇頭選舉當(dāng)中剩余的能量，單位為J。表示當(dāng)前網(wǎng)絡(luò)的總能量，單位為J。k表示簇頭節(jié)點的數(shù)量。把式3-2代入到式3-1中的處，就可以算出在LEACH改進(jìn)算法中算出的節(jié)點的概率門限T（）。1.3HEED算法HEED算法也是以LEACH算法為基礎(chǔ)進(jìn)行了改進(jìn)。它的特點是在進(jìn)行簇頭選舉的時候優(yōu)先考慮節(jié)點剩余的能量，而不是隨機地選取簇頭，這就可以讓有更多剩余能量的節(jié)點選舉成為簇首。進(jìn)而讓節(jié)點的能量消耗平均起來，以防止出現(xiàn)部分節(jié)點提前死亡的情況。延長簇首的工作時間和生存時間。HEED算法的簇頭選舉公式如下所示：(3-3)這兩種算法都是針對能量而言更加有效的分簇算法。但是，對簇頭節(jié)點的分布情況卻沒有任何改變，還是容易導(dǎo)致簇內(nèi)的節(jié)點到簇頭的距離和簇頭到基站的距離有長有短，很不均衡。若是能夠選擇那些能量高的節(jié)點作為簇頭節(jié)點就可以提升無線傳感器網(wǎng)絡(luò)的整體性能。HEED算法就是這樣進(jìn)行選舉工作的。因為傳感器網(wǎng)絡(luò)是面對現(xiàn)實中的具體事件的，所以在監(jiān)測的范圍內(nèi)若是沒有進(jìn)行中的工作就可以選擇休眠。這個休眠的機制在傳感器檢測范圍內(nèi)發(fā)生事件的時候會使傳感器自動工作而在沒有事件發(fā)生的時候可以節(jié)省能量。引入了這種休眠機制使得無線通信模塊通常能夠處于關(guān)閉的狀態(tài)，而傳感器模塊卻是需要一直