無(wú)線傳感器網(wǎng)絡(luò)基于類的簇頭選擇算法改進(jìn)

1、Improved Arithmetic in Choice of Head-Note Based on Clustering of W SNAbstract：This paper analyzes the shortness of algorithm-LEACH and shows a new arithmetic based on theclustering which depended on the asymmetrical distributions of energy and nodeIt can be testified that theimproved arithmetic ref

2、ines the distributions of cluster and head-nodeSO itS much better than LEACH inlifetime and LBF。as well as in the suitability of W SN beginningKey words：W SN head-note；LEACH ；LBF lifetime無(wú)線傳感器網(wǎng)絡(luò)基于類的簇頭選擇算法改進(jìn)摘 要：分析了LEACH協(xié)議簇頭選擇算法的不足，針對(duì)能量與節(jié)點(diǎn)不均衡分布的WSN，提出了一種基于類的簇頭選擇優(yōu)化算法，進(jìn)行了分析和仿真。結(jié)果表明，優(yōu)化算法改進(jìn)了簇和簇頭的分布方式，提高了負(fù)

3、載均衡度，并延長(zhǎng)了無(wú)線傳感器網(wǎng)絡(luò)的生存時(shí)間，適應(yīng)更多的網(wǎng)絡(luò)初始條件。關(guān)鍵詞：無(wú)線傳感器網(wǎng)絡(luò)；簇頭；LEACH；負(fù)載均衡度；生存時(shí)間 LEACH(1ow energy adaptive clustering hierarchy)協(xié)議是WSN中一種基于聚類(clustering)的低功耗自適應(yīng)路由協(xié)議I1 。它是建立在所有節(jié)點(diǎn)都是平等且無(wú)線信號(hào)在各個(gè)方向上能耗相同的假設(shè)基礎(chǔ)之上。LEACH協(xié)議將整個(gè)WSN分為若干個(gè)簇，每個(gè)簇選取一個(gè)簇頭，其它節(jié)點(diǎn)將自己所采集的信號(hào)傳輸給所屬簇的簇頭，簇頭將所有接收的信號(hào)和自己采集的信號(hào)通過(guò)數(shù)據(jù)融合后，傳給接收器。由于簇頭消耗的能量遠(yuǎn)遠(yuǎn)高于其它節(jié)點(diǎn)，因此，在LEAC

4、H協(xié)議中建立了輪次方式。每個(gè)輪次分為建立階段和穩(wěn)定階段，由于建立階段所耗能量對(duì)于信號(hào)采集來(lái)說(shuō)為無(wú)效能耗，所以穩(wěn)定階段要遠(yuǎn)遠(yuǎn)大于建立階段。通過(guò)輪次變化重新選擇簇頭節(jié)點(diǎn)，從而把簇頭高消耗的能量平均分?jǐn)偟礁鱾€(gè)節(jié)點(diǎn)上。LEACH協(xié)議相比平面協(xié)議來(lái)說(shuō)，較好的解決了能量有效問(wèn)題，能夠較好地實(shí)現(xiàn)能量均衡消耗。但是協(xié)議的缺點(diǎn)也是很明顯的，協(xié)議中的簇頭都是隨機(jī)產(chǎn)生的，難免出現(xiàn)簇頭的分布不均勻，導(dǎo)致網(wǎng)絡(luò)能量消耗不平均，從而影響WSN生存時(shí)間l5 。為了改進(jìn)LEACH協(xié)議，國(guó)內(nèi)外學(xué)者進(jìn)行了相關(guān)的研究工作。Younis等人提出了HeeD(Hybridenergy-eficient Distributed cluste

5、ring)協(xié)議l2J，該協(xié)議主要根據(jù)主、次兩個(gè)參數(shù)，通過(guò)將能耗平均分布到整個(gè)網(wǎng)絡(luò)來(lái)延長(zhǎng)網(wǎng)絡(luò)生命周期。其中簇頭選擇的主參數(shù)依賴于剩余能量，用于隨機(jī)選取出簇頭集合，具有較多剩余能量的節(jié)點(diǎn)將有較大的概率成為簇頭，而最終該節(jié)點(diǎn)是否一定是簇頭取決于剩余能量是否比周圍節(jié)點(diǎn)多得多，即迭代過(guò)程是否比周圍節(jié)點(diǎn)收斂得快；次參數(shù)依賴于簇內(nèi)通信代價(jià)，用于確定落在多個(gè)簇范圍內(nèi)的節(jié)點(diǎn)最終屬于哪個(gè)簇，以及平衡簇頭之間的負(fù)載。HeeD以AMRP(簇內(nèi)平均可達(dá)能量)作為衡量簇內(nèi)通信代價(jià)的標(biāo)準(zhǔn)。HeeD協(xié)議中簇頭選擇算法有以下特點(diǎn)：完全分布式的簇頭產(chǎn)生方式；簇頭選擇在有限次迭代內(nèi)完成；最小化控制報(bào)文開(kāi)銷；簇頭分布均衡。它的主要改

6、進(jìn)是在簇頭選擇中考慮了節(jié)點(diǎn)的剩余能量，并以主從關(guān)系引人多個(gè)約束條件。實(shí)驗(yàn)結(jié)果表明，HeeD分簇更快，能產(chǎn)生分布更加均勻的簇頭、更合理的網(wǎng)絡(luò)拓?fù)?。李晶等人改進(jìn)了HeeD路由協(xié)議，提高了網(wǎng)絡(luò)的生存周期7；孫天一將節(jié)點(diǎn)的剩余能量加入LEACH協(xié)議簇頭選擇的閥值設(shè)置中，使剩余能量大的節(jié)點(diǎn)有更多的幾率成為簇頭，并將一些新的機(jī)制加入CSMACD，減少M(fèi)AC層的信號(hào)沖突【8。張悅把簇頭的撤銷與增補(bǔ)算法加入簇頭選擇機(jī)制中，使簇頭的地理分布更加合理與均勻【9。金驥分析了LEACH協(xié)議的優(yōu)點(diǎn)和局限性，并對(duì)進(jìn)一步的研究提出了展望.推薦精選 本文將研究并提出基于節(jié)點(diǎn)初始能量與分布密度不均勻條件下的協(xié)議改進(jìn)算法。1 L

7、EACH協(xié)議中存在的問(wèn)題 LEACH協(xié)議提出了簇頭輪換機(jī)制，較好的解決了能量有效性問(wèn)題，但是此協(xié)議簇頭的選擇完全依賴于簇形成時(shí)期節(jié)點(diǎn)形成的隨機(jī)數(shù)，對(duì)其余參數(shù)(比如剩余能量、分布位置)并沒(méi)有加慮從而導(dǎo)致以下問(wèn)題： 協(xié)議中簇頭的選擇沒(méi)有考慮節(jié)點(diǎn)的初始能量與剩余能量，有可能導(dǎo)致某些初始能量小的節(jié)點(diǎn)或剩余能量小的節(jié)點(diǎn)能量提早耗盡。 其簇頭的產(chǎn)生并不考慮節(jié)點(diǎn)的地理分布，不能保證簇頭節(jié)點(diǎn)的均勻分布，從而不能保證簇的規(guī)模的合理性，可能出現(xiàn)節(jié)點(diǎn)密集的地方簇頭節(jié)點(diǎn)多，節(jié)點(diǎn)稀疏的地方簇頭節(jié)點(diǎn)少或者沒(méi)有產(chǎn)生簇頭，甚至部分節(jié)點(diǎn)可能沒(méi)有在任何簇內(nèi)，這將造成網(wǎng)絡(luò)的不完全連通。另外節(jié)點(diǎn)密集處如果產(chǎn)生了多個(gè)簇頭節(jié)點(diǎn)，也會(huì)產(chǎn)生

8、冗余，造成能量的不合理消耗，從而影響網(wǎng)絡(luò)壽命。 LEACH協(xié)議的能量消耗均衡機(jī)制要求所有節(jié)點(diǎn)的初始能量相同，但在工程應(yīng)用中保證此初始條件比較困難。2 改進(jìn)算法針對(duì)LEACH協(xié)議中出現(xiàn)的問(wèn)題，本文分別就其能量，地理分布以及負(fù)載均衡度提出改進(jìn)辦法，并將算法融合，形成一個(gè)綜合考慮以上問(wèn)題的改良算法。21 算法思路(1)針對(duì)能量的算法： 選取能量較多節(jié)點(diǎn)為簇頭，將節(jié)點(diǎn)的剩余能量作為選擇簇頭的一個(gè)重要衡量標(biāo)準(zhǔn)，使剩余能量較多的節(jié)點(diǎn)成為簇頭。(2)針對(duì)節(jié)點(diǎn)地理分布不均的算法 每個(gè)簇頭發(fā)射信號(hào)，其他節(jié)點(diǎn)根據(jù)接收到的信號(hào)判斷離簇頭的距離，離簇頭距離小于設(shè)定值R的節(jié)點(diǎn)不再選為簇頭。從而保證所有簇頭之間距離不小于

9、R。(3)針對(duì)負(fù)載均衡度進(jìn)行的優(yōu)化由于節(jié)點(diǎn)地理分布不均，簇頭負(fù)載的簇內(nèi)節(jié)點(diǎn)數(shù)量必然多寡不一，導(dǎo)致簇頭的負(fù)載不均衡。若要提高負(fù)載均衡度，只有增加簇內(nèi)節(jié)點(diǎn)數(shù)小于平均數(shù)的簇的負(fù)載節(jié)點(diǎn)，或者減少簇內(nèi)節(jié)點(diǎn)數(shù)大于平均數(shù)的簇的負(fù)載節(jié)點(diǎn)。對(duì)于簇內(nèi)節(jié)點(diǎn)數(shù)較少的簇，由于簇頭信號(hào)覆蓋范圍以及簇的分布原因，從原理上可證明不能增加其簇內(nèi)節(jié)點(diǎn)。本文通過(guò)將簇內(nèi)節(jié)點(diǎn)數(shù)較多的少數(shù)簇，分離出距離簇頭較遠(yuǎn)的節(jié)點(diǎn)，重新選擇簇頭，以提高負(fù)載均衡度。22 改進(jìn)后算法的實(shí)施步驟綜合考慮能量及其簇頭間距以及負(fù)載均衡度等約束條件，提出改進(jìn)后的簇頭選擇方式實(shí)施步驟如下，流程圖如圖1所示。推薦精選圖1 改進(jìn)后簇形成算法流程圖 根據(jù)最優(yōu)簇頭個(gè)數(shù)算法

10、【2】。 得到簇頭個(gè)數(shù)M，根據(jù)網(wǎng)絡(luò)覆蓋面積確定簇頭覆蓋范圍R。 所有節(jié)點(diǎn)全部將自己選為簇頭，供下一步撤銷使用。 每個(gè)節(jié)點(diǎn)根據(jù)自身的剩余能量E生成一個(gè)1，2，. ， )中整數(shù)i(n為節(jié)點(diǎn)總數(shù))，使剩余能量越多的節(jié)點(diǎn)生成的i越小。剩余能量與i值成反比。 所有節(jié)點(diǎn)同時(shí)開(kāi)始倒計(jì)時(shí)i個(gè)時(shí)間單位，倒計(jì)時(shí)結(jié)束時(shí)向周圍節(jié)點(diǎn)發(fā)射撤消指令，并確定其簇頭身份。 若某節(jié)點(diǎn)倒計(jì)時(shí)未結(jié)束，且收到在其R范圍內(nèi)節(jié)點(diǎn)發(fā)出的撤銷信號(hào)，則停止倒計(jì)時(shí)，撤銷其本身的簇頭身分。 普通節(jié)點(diǎn)根據(jù)收到簇頭信號(hào)強(qiáng)弱向最近簇頭發(fā)送加入信號(hào)。 簇頭計(jì)算簇內(nèi)節(jié)點(diǎn)數(shù)，若簇內(nèi)節(jié)點(diǎn)數(shù)超過(guò)平均簇內(nèi)節(jié)點(diǎn)數(shù)，根據(jù)節(jié)點(diǎn)加入信號(hào)的強(qiáng)弱，由遠(yuǎn)至近排除簇內(nèi)節(jié)點(diǎn)。推薦精選

11、 被排除節(jié)點(diǎn)重復(fù)25步。 所有非簇頭節(jié)點(diǎn)重復(fù)第6步。 簇頭向簇內(nèi)節(jié)點(diǎn)發(fā)送時(shí)隙分配信號(hào)。3 MArILAB仿真31 評(píng)價(jià)參數(shù) 在傳感器網(wǎng)絡(luò)中，評(píng)價(jià)一種分層算法好壞的參數(shù)主要為網(wǎng)絡(luò)生存時(shí)間、負(fù)載均衡度。在不考慮其它外界可能破壞因素的前提下，當(dāng)一個(gè)傳感器節(jié)點(diǎn)的能量小于0時(shí)，就認(rèn)為這個(gè)節(jié)點(diǎn)死亡；當(dāng)網(wǎng)絡(luò)中出現(xiàn)節(jié)點(diǎn)能量小于0，網(wǎng)絡(luò)就死亡。所以將網(wǎng)絡(luò)中第一個(gè)節(jié)點(diǎn)死亡時(shí)間定義為網(wǎng)絡(luò)生存時(shí)間。在分層算法中，除了分簇時(shí)的能量消耗外，每輪中簇覆蓋節(jié)點(diǎn)的平均程度也會(huì)影響網(wǎng)絡(luò)的生存時(shí)間。而且由于簇中包含節(jié)點(diǎn)數(shù)目不平衡會(huì)導(dǎo)致不同簇之間數(shù)據(jù)容量不同，因此簇的負(fù)載平衡程度也是衡量算法性能的重要標(biāo)準(zhǔn)之一，負(fù)載平衡因子的計(jì)算公式

12、如下：其中：head_num為WSN中實(shí)際的簇頭數(shù)，五為第i個(gè)簇所包含的節(jié)點(diǎn)個(gè)數(shù)， 為本輪簇平均包含的節(jié)點(diǎn)個(gè)數(shù)。LBF的數(shù)值越大說(shuō)明簇的負(fù)載越平衡 。32 仿真計(jì)算 本文用MATLAB生成一個(gè)不均勻節(jié)點(diǎn)分布圖，將一個(gè)介于(z一0， O)與(z一100， 一100)的區(qū)域分為四個(gè)方塊，在(z一0， O)至(z一50， 一50)區(qū)域與(z一50， 一50)至(z一100，Y一100)區(qū)域內(nèi)各隨機(jī)分布5O個(gè)節(jié)點(diǎn)，在(z一0，一50)至(z一50， 一100)區(qū)域與(z一50， O)至(z一100，Y一50)區(qū)域內(nèi)各隨機(jī)分布5個(gè)節(jié)點(diǎn)，如圖2所示。Sink點(diǎn)置于(50，100)處，其能量可連續(xù)供給。圖2

13、 節(jié)點(diǎn)分布圖在無(wú)限傳感器網(wǎng)絡(luò)中，相對(duì)于數(shù)據(jù)無(wú)線發(fā)送接收來(lái)說(shuō)，節(jié)點(diǎn)進(jìn)行運(yùn)算和儲(chǔ)存的耗能基本可以忽略不計(jì)。所以網(wǎng)絡(luò)的生存時(shí)間主要取決于數(shù)據(jù)傳輸。假定每個(gè)節(jié)點(diǎn)最初的能量在03 JO7 J間均勻隨機(jī)分布，設(shè)定。為了將數(shù)據(jù)傳輸?shù)米銐蜻h(yuǎn)，放大器消耗的能量為推薦精選，每個(gè)數(shù)據(jù)包的大小固定為5O bit，設(shè)定數(shù)據(jù)融合機(jī)制參數(shù)為7O 。所有節(jié)點(diǎn)不能移動(dòng)，節(jié)點(diǎn)能量耗盡則視為死亡。根據(jù)文獻(xiàn)2的通訊模型中的短距離模型，兩節(jié)點(diǎn)間距離為d，通信能量消耗與d 成正比。則節(jié)點(diǎn)傳送kbit數(shù)據(jù)到與之距離為d的另外一個(gè)節(jié)點(diǎn)所消耗能量表示為： 其中第一項(xiàng) 表示數(shù)據(jù)編碼，調(diào)制解調(diào)等過(guò)程消耗的能量，第二項(xiàng)為根據(jù)通信距離d所消耗的能量，

14、其中為信號(hào)放大器耗能參數(shù)。節(jié)點(diǎn)接收kbit長(zhǎng)度數(shù)據(jù)所消耗的能量為：與距離無(wú)關(guān)。將LEACH協(xié)議與改進(jìn)后協(xié)議進(jìn)行比較，簇頭分布如圖3、圖4所示： LEACH協(xié)議簇頭隨機(jī)分布，呈不均勻狀態(tài)，從而導(dǎo)致某些地區(qū)簇頭過(guò)少，極端情況甚至某些節(jié)點(diǎn)無(wú)法連接任何簇頭，使網(wǎng)絡(luò)未完全連通。改進(jìn)后算法對(duì)簇頭的地理分布優(yōu)化結(jié)果明顯，簇頭分布情況顯著改善，分布較均勻，保證網(wǎng)絡(luò)完全連通，即連通率為100%。而LEACH協(xié)議隨簇頭比例變化，節(jié)點(diǎn)連通比例保持在722% 725% 左右，隨著簇頭比例的增大而增大，增幅不明顯。推薦精選 設(shè)定每輪穩(wěn)定傳輸30次，將簇頭百分比在范圍為2% 28% 之間均勻設(shè)定20個(gè)比例點(diǎn)。由于模型設(shè)置

15、隨機(jī)量較多，本文采取每種簇頭比例進(jìn)行100次仿真的方式，求出每種簇頭比例生存輪數(shù)與LBF的平均值。為減小隨機(jī)因素帶來(lái)的影響，對(duì)圖像采取最小二乘法進(jìn)行擬合。原LEACH協(xié)議與改進(jìn)后協(xié)議的網(wǎng)絡(luò)生存時(shí)間和LBF的比較分別如圖5、圖6所示：圖5顯示了兩種算法在不同的簇頭比例下的網(wǎng)絡(luò)生存時(shí)間，顯然改進(jìn)后的算法可以有更長(zhǎng)的生存時(shí)間。改進(jìn)后峰值出現(xiàn)的簇頭比例比LEACH協(xié)議稍高，峰值增幅為81% 。考慮到LEACH協(xié)議的不完全連通性，改進(jìn)算法在工程應(yīng)用中優(yōu)勢(shì)更加明顯。圖6表明了兩種算法在不同簇頭比例下的LBF值。改進(jìn)后的算法簇頭的地理分布平均，每個(gè)簇的成員數(shù)量更均勻，負(fù)載均衡程度更好。4 結(jié)論本文分析了傳統(tǒng)

16、LEACH路有算法，針對(duì)能量與節(jié)點(diǎn)不均衡分布的WSN提出了新的簇頭選擇方案。該算法方案保證了簇的平均分布和網(wǎng)絡(luò)的完全聯(lián)通，提高了簇的負(fù)載均衡度從而減小了單個(gè)節(jié)點(diǎn)的能量消耗，延長(zhǎng)了網(wǎng)絡(luò)生存時(shí)間。相比LEACH協(xié)議來(lái)說(shuō)，簇頭的地理分布更加合理，并增加了網(wǎng)絡(luò)的LBF值，大幅度地減少了節(jié)點(diǎn)與簇頭的平均距離。 與HeeD算法相比，本文算法的優(yōu)點(diǎn)是不需要迭代，只需要延時(shí)設(shè)置，減少計(jì)算過(guò)程；HeeD在成簇階段，每個(gè)節(jié)點(diǎn)都需要廣播自身信息(剩余能量和通信代價(jià))，本文算法只需要能量最高節(jié)點(diǎn)在最終自我選為簇頭時(shí)廣播成簇信號(hào)，不需要每個(gè)節(jié)點(diǎn)都廣播信息，能量節(jié)省相當(dāng)可觀；本算法除了計(jì)算節(jié)點(diǎn)自身延時(shí)之外，在成推薦精選簇

17、階段不需要其他的計(jì)算，對(duì)硬件要求更低；HeeD有可能使節(jié)點(diǎn)加人不了任何簇，成為網(wǎng)絡(luò)孤島(見(jiàn)上文分析)。與HeeD算法相比，本文算法的缺點(diǎn)是延時(shí)計(jì)算比較復(fù)雜；HeeD算法加人的通信代價(jià)因素，使簇內(nèi)的通信代價(jià)更??；HeeD算法將節(jié)點(diǎn)由剩余能量簡(jiǎn)單分為8個(gè)段，在能量計(jì)算更為簡(jiǎn)單。本算法適應(yīng)了節(jié)點(diǎn)初始能量不同與節(jié)點(diǎn)分布密度不均勻的WSN，具有一定的工程實(shí)用性。參考文獻(xiàn)：1 Heinzelman W，Chandrakasan A，Balakrishnan H。Energy-Efficient Communication Protocol for W ireless M icrosensorNetwork

18、s-CProceedings of the 33rd Annual Hawaii International Conference on System Sciences，Hawaii，USA，2000472Younis O，F(xiàn)ahmy sHeeD：a Hybrid，Energy-Efficient，Distributed Clustering Approach for Ad-Hoc Sensor Networks EJIEEE Trans on M obile Co mputing，2004，3(4)：6606693 Jamal N Al-karakl，Ahmed E Kama1Routing Techniques inWireless Sensor Networks：a SurveycIEEE WirelessCo mmunicationgsDecember 2004，l1(6)：6-284 Wendi Rabiner Heinzelman，Anantha Chandraksan，Haft Balakrishnan Energy-Efficient Co mmunication Protocol forWireless Microsensor Net