摘  要： 基于圖論中最小生成樹的思想對LEACH協(xié)議進(jìn)行了改進(jìn)，構(gòu)建了一種降低能耗的Prim分簇算法。其算法采用將普里姆的思想用到分簇中，將能量大或近似大的傳感器節(jié)點(diǎn)，根據(jù)其在網(wǎng)絡(luò)中的位置，將一條最小距離的邊加入樹中。通過多跳結(jié)構(gòu)，減少節(jié)點(diǎn)在傳輸數(shù)據(jù)中的能量消耗，從而延長網(wǎng)絡(luò)的壽命。對改進(jìn)的算法經(jīng)驗證表明能有效降低能量消耗，提高網(wǎng)絡(luò)的生存期。
關(guān)鍵詞： 無線傳感器網(wǎng)絡(luò)；動態(tài)分簇；Prim算法；能量有效

　無線傳感器網(wǎng)絡(luò)（WSN）是較新的研究領(lǐng)域，由于其廣闊的應(yīng)用前景，近年來受到越來越多的關(guān)注，各種面向具體應(yīng)用的WSN路由協(xié)議應(yīng)運(yùn)而生。WSN通常依賴電池供電，而電池能量有限，因此如何延長網(wǎng)絡(luò)的生命周期是WSN中十分重要的問題[1]。
1 基于能量有效網(wǎng)絡(luò)節(jié)點(diǎn)動態(tài)分簇
1.1 動態(tài)分簇基本思想
　分簇思想是采用層次型拓?fù)浣Y(jié)構(gòu)，根據(jù)概率隨機(jī)確定高級節(jié)點(diǎn)即簇頭節(jié)點(diǎn)和普通節(jié)點(diǎn)。根據(jù)規(guī)則確定普通節(jié)點(diǎn)子簇歸屬并建立子簇。簇頭負(fù)責(zé)簇內(nèi)數(shù)據(jù)融合并協(xié)調(diào)簇內(nèi)節(jié)點(diǎn)工作，在簇頭間運(yùn)用Prim算法搜尋簇頭節(jié)點(diǎn)到匯聚節(jié)點(diǎn)的多跳最優(yōu)路徑，采用多跳接力方式將簇頭融合數(shù)據(jù)發(fā)送至匯聚節(jié)點(diǎn)，以進(jìn)行數(shù)據(jù)采集傳輸或動態(tài)分簇及路徑尋優(yōu)，實(shí)現(xiàn)無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)能量均衡管理[2]。本算法是將普里姆的思想用到分簇中，將能量大的傳感器節(jié)點(diǎn)，根據(jù)其在網(wǎng)絡(luò)中的位置，將一條最小距離的邊加入樹中。通過多跳結(jié)構(gòu)，減少節(jié)點(diǎn)在傳輸數(shù)據(jù)中的能量消耗，從而延長網(wǎng)絡(luò)的壽命[3]。

?、茉谘h(huán)中選為高級節(jié)點(diǎn)的無線發(fā)射模塊，可根據(jù)節(jié)點(diǎn)能耗情況和距離遠(yuǎn)近控制發(fā)送功率大小，發(fā)送數(shù)據(jù)的能耗取決于數(shù)據(jù)大小和傳輸距離，接收數(shù)據(jù)的能耗只取決于數(shù)據(jù)大小。
?。?）根據(jù)概率隨機(jī)選取節(jié)點(diǎn)作為高級節(jié)點(diǎn)，其余節(jié)點(diǎn)為普通節(jié)點(diǎn)。匯聚節(jié)點(diǎn)廣播消息并接收各節(jié)點(diǎn)的返回數(shù)據(jù)，讓匯聚節(jié)點(diǎn)知道網(wǎng)絡(luò)基本情況。
?。?）根據(jù)節(jié)點(diǎn)位置信息、距離啟發(fā)因子和簇成員節(jié)點(diǎn)數(shù)量限制，計算普通節(jié)點(diǎn)與相鄰簇頭節(jié)點(diǎn)距離，判定普通節(jié)點(diǎn)歸屬。普通節(jié)點(diǎn)與簇節(jié)點(diǎn)通信并確認(rèn)關(guān)系，由此子簇建立。

?。?）根據(jù)匯聚節(jié)點(diǎn)廣播消息，子簇內(nèi)各節(jié)點(diǎn)的數(shù)據(jù)傳輸?shù)酱仡^，并進(jìn)行數(shù)據(jù)融合。根據(jù)BWAS算法，搜尋最優(yōu)路徑，將簇頭融合后的數(shù)據(jù)以多跳接力方式傳輸?shù)絽R聚節(jié)點(diǎn)。
　（6）根據(jù)一定規(guī)則調(diào)整簇頭傳輸功率或簇內(nèi)根據(jù)剩余能量高低選取新的簇頭節(jié)點(diǎn)等。根據(jù)匯聚節(jié)點(diǎn)廣播要求，循環(huán)步驟（2）~步驟（5）到最大迭代次數(shù)或死亡節(jié)點(diǎn)接近于最初設(shè)定值[4]。
2 基于能量有效的動態(tài)分簇算法
　改進(jìn)的Prim分簇算法考慮了節(jié)點(diǎn)的剩余能量，由于節(jié)點(diǎn)內(nèi)部均有數(shù)據(jù)采集和數(shù)據(jù)融合的功能，則從簇首節(jié)點(diǎn)采集的數(shù)據(jù)已經(jīng)在一定基礎(chǔ)上進(jìn)行優(yōu)化，然后由簇首傳遞給數(shù)據(jù)匯集點(diǎn)。這樣在數(shù)據(jù)匯集點(diǎn)得到的數(shù)據(jù)基本上均為最優(yōu)化數(shù)據(jù)，最后數(shù)據(jù)匯集點(diǎn)再向基站傳輸，減少了無效數(shù)據(jù)的傳輸，節(jié)約了節(jié)點(diǎn)的能量[5-6]。
2.1 算法模型化及定義
　prim分簇算法是在單層分簇的基礎(chǔ)上遵循從底至上的方式繼續(xù)分簇。假設(shè)從第1層到第h層節(jié)點(diǎn)被選為簇首的概率分別為p1，p2，p3，p4。以第1層簇首的選擇為例，以概率選擇出自愿的簇首，在其規(guī)定的k1跳范圍內(nèi)發(fā)送廣播消息，收到廣播消息的節(jié)點(diǎn)，根據(jù)其接收到信號的強(qiáng)度，選擇準(zhǔn)備要加入的簇首；沒有接收到任何廣播消息的節(jié)點(diǎn)將成為強(qiáng)迫的簇首。在第1層構(gòu)造簇首的基礎(chǔ)上以概率選出第2層的簇首，然后依次進(jìn)行下去，直到第h層簇首的選出，就完成了多層分簇的體系。
2.2 算法設(shè)計思路
?。?）簇首的選擇，選擇簇首節(jié)點(diǎn)的個數(shù)為5，此5個簇首為算法的一級簇首，二級簇首在選完一級簇首之后，在剩余節(jié)點(diǎn)中再進(jìn)行選擇。由于本文選擇的節(jié)點(diǎn)個數(shù)為100個，因而節(jié)點(diǎn)數(shù)量不大，分為二級即可，在選擇完二級節(jié)點(diǎn)之后剩余節(jié)點(diǎn)為成員節(jié)點(diǎn)。
?。?）簇首選擇完成之后，再根據(jù)分簇算法將成員節(jié)點(diǎn)分簇。在網(wǎng)絡(luò)G=（V，E）中的節(jié)點(diǎn)均可傳送和接收來自其鄰居節(jié)點(diǎn)的信息。每個節(jié)點(diǎn)v都有一個確定的ID（v），能量值越大，此ID值越大。運(yùn)用普里姆算法的思想選擇ID值大且到簇首跳數(shù)少的節(jié)點(diǎn)就近相連，以減少節(jié)點(diǎn)在傳輸路徑上能量的消耗。
?。?）重復(fù)思路（2）直至所有節(jié)點(diǎn)均發(fā)送過分簇消息。完成節(jié)點(diǎn)分簇，此時完成一輪分簇算法，按照以上步驟重復(fù)直至節(jié)點(diǎn)能量殆盡。
2.3 算法流程
　通過算法的描述如圖1所示，節(jié)點(diǎn)生成的隨機(jī)數(shù)小于閾值的節(jié)點(diǎn)將自動升為簇首并向外發(fā)送簇首信息；小于閾值的節(jié)點(diǎn)將重新生成隨機(jī)數(shù)，根據(jù)產(chǎn)生的隨機(jī)數(shù)和閾值的關(guān)系確定為簇首或普通節(jié)點(diǎn)，和LEACH算法一樣根據(jù)自己的節(jié)點(diǎn)屬性發(fā)送簇首信息或加入簇請求。

3 評價與分析
　分簇算法采用Matlab仿真工具，設(shè)定節(jié)點(diǎn)區(qū)域大小為[100，100]，節(jié)點(diǎn)坐標(biāo)為（100，100），隨機(jī)生成網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)為200。首先要對網(wǎng)中的節(jié)點(diǎn)的能量初始化賦值，算出每個節(jié)點(diǎn)的ID值，根據(jù)算法確定一級簇首（☆）和二級簇首（*），成員節(jié)點(diǎn)用點(diǎn)狀表示。
　初始化節(jié)點(diǎn)之后，可以使用Prim算法開始本輪的分簇，如圖2所示。分簇之后，得到簇是多跳的，使得離簇首較遠(yuǎn)的節(jié)點(diǎn)通過二級簇首節(jié)點(diǎn)傳給簇首，使簇首的能量耗損減小。

　分簇之后再對分簇前后能量進(jìn)行比較，其結(jié)果如圖3所示。從剩余能量看出，所消耗能量與原有能量相差不大。為了明顯看出本算法在能量上的優(yōu)越性，將兩種算法結(jié)果進(jìn)行分析，如圖4所示。剩余總能量和它們到達(dá)能量殆盡時比較可看出，改進(jìn)后的Prim算法在分簇到700輪時能量耗盡，而LEACH算法在500輪時就已耗盡，這說明改進(jìn)的分簇算法確實(shí)延長了網(wǎng)絡(luò)的壽命，仿真結(jié)果也表明這種方法是可行的。

　研究證明WSN分簇的結(jié)構(gòu)存在最優(yōu)的簇首個數(shù)，使網(wǎng)絡(luò)能耗最優(yōu)。LEACH協(xié)議每輪選舉出的簇首個數(shù)的均值是最優(yōu)值k，采用隨機(jī)方法分析指出簇首個數(shù)的均值并不是常數(shù)k，而是函數(shù)。通過實(shí)驗表明，基于改進(jìn)Prim算法較LEACH算法不僅延長了系統(tǒng)生存時間，而且基站能夠接收更多的數(shù)據(jù)，實(shí)現(xiàn)了低能量開銷的目的。
參考文獻(xiàn)
[1] 閻新芳，安娜.無線傳感器網(wǎng)絡(luò)中分級簇的維護(hù)和更新算法[J].傳感技術(shù)學(xué)報，2007，14（7）：33-35.
[2] HEINZELMAN W， CHANDRAKASAN A， BALAKRISHNAN  H. Energy efficient communication protocol for wireless microsensor networks[C]. in proceeding of the 33rd Hawaii international conference on system sciences. 2000：3005-3014.
[3] 劉俊鋒.基于網(wǎng)格的無線傳感器網(wǎng)絡(luò)分簇方法[J].計算機(jī)工程與設(shè)計，2007（5）：55-60.
[4] 張德躍，楊峰，展中華，等.傳感器網(wǎng)絡(luò)的一種能量感知分簇路由算法[J].計算機(jī)技術(shù)與發(fā)展，2007，17（1）：42-45.
[5] 劉云璐，柴喬林，趙晉.無線傳感器網(wǎng)絡(luò)方向性分區(qū)路由算法[J].計算機(jī)應(yīng)用，2006，26（1）：66-70.
[6] BASU P， KHAN N， LITFLE T D C. A Mobility based metrie for clustering in mobile ad hoc networks[C]. Phoenix， AZ， April2001， 413-418.