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

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ǎng)絡(luò)基于類的簇頭選擇算法改進摘 要：分析了LEACH協(xié)議簇頭選擇算法的不足，針對能量與節(jié)點不均衡分布的WSN，提出了一種基于類的簇頭選擇優(yōu)化算法，進行了分析和仿真。結(jié)果表明，優(yōu)化算法改進了簇和簇頭的分布方式，提高了負

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

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

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

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

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

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

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

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

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

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

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

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

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

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

17、階段不需要其他的計算，對硬件要求更低；HeeD有可能使節(jié)點加人不了任何簇，成為網(wǎng)絡(luò)孤島(見上文分析)。與HeeD算法相比，本文算法的缺點是延時計算比較復(fù)雜；HeeD算法加人的通信代價因素，使簇內(nèi)的通信代價更?。籋eeD算法將節(jié)點由剩余能量簡單分為8個段，在能量計算更為簡單。本算法適應(yīng)了節(jié)點初始能量不同與節(jié)點分布密度不均勻的WSN，具有一定的工程實用性。參考文獻：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