改進的分簇路由協(xié)議方案ADEECS

　　1 引言

　　無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network，WSN)是由大量具有特定功能的傳感器節(jié)點通過自組織的無線通信方式，相互傳遞信息，協(xié)同地完成特定功能的智能專用網(wǎng)絡(luò)。傳感器網(wǎng)絡(luò)一般投放在條件惡劣的環(huán)境或者難以涉足的地域中，節(jié)點電池的更換或能量的補充幾乎是不可能的，所以節(jié)能路由協(xié)議的設(shè)計，對無線傳感器網(wǎng)絡(luò)來說意義十分重大。目前，提出的WSN路由協(xié)議主要有平面路由協(xié)議和層次路由協(xié)議兩類，其中基于簇結(jié)構(gòu)的層次路由協(xié)議是當前國內(nèi)外研究的熱點口。

　　1相關(guān)研究

　　WSN分簇路由協(xié)議設(shè)計的首要目標是通過高效的分簇算法形成合理的網(wǎng)絡(luò)結(jié)構(gòu)，通過主動的能量管理阻止網(wǎng)絡(luò)連通性下降，延長網(wǎng)絡(luò)的生命周期。最典型的無線傳感器網(wǎng)絡(luò)分簇路由協(xié)議是LEACH協(xié)議，人們在LEACH協(xié)議的基礎(chǔ)上也研究出很多改進的分簇路由協(xié)議，EECS(Energy Efficient Clustering Scheme)協(xié)議就是其中一種經(jīng)典的改進算法。

　　1.1LEACH協(xié)議

　　LEACH是分布式成簇協(xié)議的代表。每個節(jié)點產(chǎn)生一個0～1的隨機數(shù)，如果這個數(shù)小于閾值，則該節(jié)點向整個網(wǎng)絡(luò)廣播它是簇頭。閾值的計算公式為：

?

　　式中：p是簇頭占所有節(jié)點的百分比，即節(jié)點當選為簇頭的初始概率，實際的簇頭概率以p為中心上下浮動;r是目前循環(huán)進行的輪;G是在最近1/p輪中沒有當選過簇頭的節(jié)點集合。可以看出，當選過簇頭的節(jié)點在接下來的1輪中將不能成為簇頭，而其他節(jié)點，因節(jié)點產(chǎn)生小于T(n)隨機數(shù)的概率隨之增大，所以節(jié)點當選為簇頭的概率也增大。競爭成功的簇頭節(jié)點廣播當選的消息后，其他節(jié)點根據(jù)簇頭廣播信號的強弱決定加入哪個簇。由于簇頭是隨機挑選的，因此LEACH協(xié)議不能保證簇頭在網(wǎng)絡(luò)中分布均勻，而且節(jié)點根據(jù)自身通信代價最小原則選擇加入哪個簇的成簇算法，但不能保證簇的負載均衡。

　　1.2 EECS協(xié)議

　　如前所述，LEACH等算法中，節(jié)點根據(jù)自身通信代價最小原則選擇加入哪個簇，不能保證簇的負載平衡，而且沒有考慮距基站較遠的簇頭能量耗費過快等問題。針對這些問題，EECS提出一個新的通信代價公式(2)來決定節(jié)點加入哪個簇：

?

　　式中：cost(j，i)是節(jié)點Pj加入簇頭i的代價;d(Pj，CHi)是節(jié)點到簇頭的距離。式(3)中f子函數(shù)保證最小化節(jié)點與簇頭之間的通信代價;d(CHi，BS)是簇頭i到基站的距離，式(3)中g(shù)子函數(shù)保證最小化簇頭i到基站的通信代價;權(quán)值w的設(shè)置則根據(jù)具體應(yīng)用，在成員節(jié)點能量與簇頭能量消耗之間折衷，目標是最大化網(wǎng)絡(luò)生命周期。節(jié)點Pj選擇cost(j，i)最小的簇頭i加入，從而保證每個簇頭負載均衡。實驗結(jié)果顯示，EECS協(xié)議的網(wǎng)絡(luò)生命周期較LEACH協(xié)議提高了30%以上。

　　2問題的描述

　　EECS算法的實質(zhì)是在簇頭選擇階段，總是讓剩余能量最大的節(jié)點當選為簇頭;在成簇階段，聯(lián)合考慮普通節(jié)點與簇頭的距離，以及簇頭與基站的距離。其創(chuàng)新之處在于：只有小部分節(jié)點參加簇頭的競選;在局部范圍內(nèi)廣播消息，選舉過程沒有迭代;以節(jié)點的剩余能量為競選參數(shù);設(shè)計了簇頭之間負載均衡的策略。

　　EECS協(xié)議存在的問題：

　　(1)EECS算法在成簇階段讓候選節(jié)點同時廣播競選消息COMPETE_HEAD，容易造成簇頭分布漏洞問題。如圖1所示，節(jié)點C在B的競選半徑內(nèi);節(jié)點B在A的競選半徑內(nèi)，且剩余能量方面A>B>C。在這種情況下，C收到B的競選消息退出競選的同時，B收到A的競選消息退出競選，這就會造成局部簇頭分布漏洞的情況。

　　(2)EECS算法在成簇階段的通信代價只考慮了普通節(jié)點與簇頭的距離，以及簇頭與基站的距離，沒有考慮簇頭的剩余能量。這樣就會造成部分剩余能量相對較少簇頭節(jié)點的早死現(xiàn)象。

　　針對EECS協(xié)議存在的問題提出了ADEECS(Advanced EECS)協(xié)議，該算法在簇頭選舉階段使用了競爭延遲的方法，在成簇階段設(shè)計了新的通信代價計算公式。

?