摘 要： 基于圖論中最小生成樹的思想對LEACH協議進行了改進，構建了一種降低能耗的Prim分簇算法。其算法采用將普里姆的思想用到分簇中，將能量大或近似大的傳感器節點，根據其在網絡中的位置，將一條最小距離的邊加入樹中。通過多跳結構，減少節點在傳輸數據中的能量消耗，從而延長網絡的壽命。對改進的算法經驗證表明能有效降低能量消耗，提高網絡的生存期。
關鍵詞： 無線傳感器網絡；動態分簇；Prim算法；能量有效
無線傳感器網絡（WSN）是較新的研究領域，由于其廣闊的應用前景，近年來受到越來越多的關注，各種面向具體應用的WSN路由協議應運而生。WSN通常依賴電池供電，而電池能量有限，因此如何延長網絡的生命周期是WSN中十分重要的問題[1]。
1 基于能量有效網絡節點動態分簇
1.1 動態分簇基本思想
分簇思想是采用層次型拓撲結構，根據概率隨機確定高級節點即簇頭節點和普通節點。根據規則確定普通節點子簇歸屬并建立子簇。簇頭負責簇內數據融合并協調簇內節點工作，在簇頭間運用Prim算法搜尋簇頭節點到匯聚節點的多跳最優路徑，采用多跳接力方式將簇頭融合數據發送至匯聚節點，以進行數據采集傳輸或動態分簇及路徑尋優，實現無線傳感器網絡節點能量均衡管理[2]。本算法是將普里姆的思想用到分簇中，將能量大的傳感器節點，根據其在網絡中的位置，將一條最小距離的邊加入樹中。通過多跳結構，減少節點在傳輸數據中的能量消耗，從而延長網絡的壽命[3]。
④在循環中選為高級節點的無線發射模塊，可根據節點能耗情況和距離遠近控制發送功率大小，發送數據的能耗取決于數據大小和傳輸距離，接收數據的能耗只取決于數據大小。
（3）根據概率隨機選取節點作為高級節點，其余節點為普通節點。匯聚節點廣播消息并接收各節點的返回數據，讓匯聚節點知道網絡基本情況。
（4）根據節點位置信息、距離啟發因子和簇成員節點數量限制，計算普通節點與相鄰簇頭節點距離，判定普通節點歸屬。普通節點與簇節點通信并確認關系，由此子簇建立。
（5）根據匯聚節點廣播消息，子簇內各節點的數據傳輸到簇頭，并進行數據融合。根據BWAS算法，搜尋最優路徑，將簇頭融合后的數據以多跳接力方式傳輸到匯聚節點。
（6）根據一定規則調整簇頭傳輸功率或簇內根據剩余能量高低選取新的簇頭節點等。根據匯聚節點廣播要求，循環步驟（2）~步驟（5）到最大迭代次數或死亡節點接近于最初設定值[4]。
2 基于能量有效的動態分簇算法
改進的Prim分簇算法考慮了節點的剩余能量，由于節點內部均有數據采集和數據融合的功能，則從簇首節點采集的數據已經在一定基礎上進行優化，然后由簇首傳遞給數據匯集點。這樣在數據匯集點得到的數據基本上均為最優化數據，最后數據匯集點再向基站傳輸，減少了無效數據的傳輸，節約了節點的能量[5-6]。
2.1 算法模型化及定義
prim分簇算法是在單層分簇的基礎上遵循從底至上的方式繼續分簇。假設從第1層到第h層節點被選為簇首的概率分別為p1，p2，p3，p4。以第1層簇首的選擇為例，以概率選擇出自愿的簇首，在其規定的k1跳范圍內發送廣播消息，收到廣播消息的節點，根據其接收到信號的強度，選擇準備要加入的簇首；沒有接收到任何廣播消息的節點將成為強迫的簇首。在第1層構造簇首的基礎上以概率選出第2層的簇首，然后依次進行下去，直到第h層簇首的選出，就完成了多層分簇的體系。
2.2 算法設計思路
（1）簇首的選擇，選擇簇首節點的個數為5，此5個簇首為算法的一級簇首，二級簇首在選完一級簇首之后，在剩余節點中再進行選擇。由于本文選擇的節點個數為100個，因而節點數量不大，分為二級即可，在選擇完二級節點之后剩余節點為成員節點。
（2）簇首選擇完成之后，再根據分簇算法將成員節點分簇。在網絡G=（V，E）中的節點均可傳送和接收來自其鄰居節點的信息。每個節點v都有一個確定的ID（v），能量值越大，此ID值越大。運用普里姆算法的思想選擇ID值大且到簇首跳數少的節點就近相連，以減少節點在傳輸路徑上能量的消耗。
（3）重復思路（2）直至所有節點均發送過分簇消息。完成節點分簇，此時完成一輪分簇算法，按照以上步驟重復直至節點能量殆盡。
2.3 算法流程
通過算法的描述如圖1所示，節點生成的隨機數小于閾值的節點將自動升為簇首并向外發送簇首信息；小于閾值的節點將重新生成隨機數，根據產生的隨機數和閾值的關系確定為簇首或普通節點，和LEACH算法一樣根據自己的節點屬性發送簇首信息或加入簇請求。
3 評價與分析
分簇算法采用Matlab仿真工具，設定節點區域大小為[100，100]，節點坐標為（100，100），隨機生成網絡節點數為200。首先要對網中的節點的能量初始化賦值，算出每個節點的ID值，根據算法確定一級簇首（☆）和二級簇首（*），成員節點用點狀表示。
初始化節點之后，可以使用Prim算法開始本輪的分簇，如圖2所示。分簇之后，得到簇是多跳的，使得離簇首較遠的節點通過二級簇首節點傳給簇首，使簇首的能量耗損減小。
分簇之后再對分簇前后能量進行比較，其結果如圖3所示。從剩余能量看出，所消耗能量與原有能量相差不大。為了明顯看出本算法在能量上的優越性，將兩種算法結果進行分析，如圖4所示。剩余總能量和它們到達能量殆盡時比較可看出，改進后的Prim算法在分簇到700輪時能量耗盡，而LEACH算法在500輪時就已耗盡，這說明改進的分簇算法確實延長了網絡的壽命，仿真結果也表明這種方法是可行的。
研究證明WSN分簇的結構存在最優的簇首個數，使網絡能耗最優。LEACH協議每輪選舉出的簇首個數的均值是最優值k，采用隨機方法分析指出簇首個數的均值并不是常數k，而是函數。通過實驗表明，基于改進Prim算法較LEACH算法不僅延長了系統生存時間，而且基站能夠接收更多的數據，實現了低能量開銷的目的。
參考文獻
[1] 閻新芳，安娜.無線傳感器網絡中分級簇的維護和更新算法[J].傳感技術學報，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] 劉俊鋒.基于網格的無線傳感器網絡分簇方法[J].計算機工程與設計，2007（5）：55-60.
[4] 張德躍，楊峰，展中華，等.傳感器網絡的一種能量感知分簇路由算法[J].計算機技術與發展，2007，17（1）：42-45.
[5] 劉云璐，柴喬林，趙晉.無線傳感器網絡方向性分區路由算法[J].計算機應用，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.