PRIM-LEACH高效聚類路由算法的研究與實際應用

劉 斌

（山東大學外國語學院, 濟南 250000）

隨著微電子技術的快速發展，低成本、小型化、功能集成度和可靠性高的傳感器的生產已經變成現實，這些非常小的傳感器元件已經擁有強大的多種功能，其中包括數據處理、信息收集和無線通信等。部署在監測地點數量龐大的微型傳感器節點組成無線傳感器網絡（w ire less senso r netw o rk ，WSN），各節點之間協同感知、采集和處理覆蓋感知對象的區域信息，通過無線通信系統，形成一個多跳的自組織網絡，并將信息發送給基站[1,2,5]。無線傳感器網絡的這種工作方式是以往所不具備的，可以擴展人類的能力，融合客觀物理世界與邏輯信息世界，改變人類認識世界的方式以及與大自然的互動方式。

1 無線傳感器網絡概述

1.1 無線傳感器網絡的結構

無線傳感器節點、感知對象、觀察者共同組成了無線傳感器網絡的三大要素，承擔著網絡的構建任務，網絡結構如下圖1-1所示。

1.2 無線傳感器網絡的特點

與傳統網絡相比，無線傳感器網絡有以下幾大特點：

1）能量有限

2）計算能力有限

3）存儲能力有限

4）通信范圍有限

5）拓撲結構時刻變化

6）自組織性

2 無線傳感器網絡路由協議

無線傳感器網絡的能源有效性是指消耗單位能量的情況下解決的數據請求數量。無線傳感器節點攜帶的能量很少，減少能量的消耗是設計必須要考慮的問題。

不同于傳統網絡的特點與應用，所以無線傳感器網絡不能照搬傳統網絡的路由協議，需要設計專用的路由協議。路由協議的設計開發過程中有以下幾個困難。

1）沒有唯一的標示符，節點的尋址不方便。

2）所有的節點都可以采集數據，發送到目標節點。

3）有大量冗余的節點存在，采集的數據會有很大一部分是相同的，需要進行數據融合。

4）每個節點的能量是有限的，由于能量的限制，導致每個節點的存儲能力、處理能力和傳輸能力都很有限。

從上述幾個特點可以看出，無線傳感器網絡的路由協議是需要專門設計的。

LEACH協議是一種典型的無線傳感器網絡路由協議，該協議中根據一定的規則進行分簇，然后選取簇首節點，所有的簇首節點都直接與基站進行通信，這樣不可避免地浪費大量的能量，特別是距離基站比較遠的簇首節點，導致整個無線傳感器網絡存活時間縮短。LEACH-EE在LEACH的基礎上，提出了一個新的算法，能夠有效改善LEACH協議的存活時間。LEACH-EE根據一定的算法，在簇首之間形成一條多跳鏈，各簇首的數據沿著多跳鏈傳遞給基站，這樣就能有效節省距離基站遠的簇首節點的能量。但是在拓撲路由信息傳遞時，簇首節點形成的多跳鏈可能會形成迂回，這樣部分能量會消耗在迂回的過程中，導致能量消耗和網絡存活時間的縮短[3,4]。

LEACH-EE協議的網絡拓撲圖如下圖4-1所示，從圖中可以清晰地看出簇首生成的多條鏈所形成的迂回問題。

3 PRIM-LEACH實驗仿真

為了驗證以上算法的正確性，本文以m atlab對實驗過程進行了仿真，比較了PRIM—LEACH，LEACH以及LEACH—EE三種協議，從仿真中可以看出PRIM-LEACH確實能夠延長網絡存活期。

3.1 仿真的目

仿真的目的是為了查看無線傳感器網絡在PRIM-LEACH協議的工作狀況，最關心的問題就是能量的使用情況。

3.2 仿真結果

仿真時首先對PRIM-LEACH的分簇算法進行驗證，根據理論應該是節點剩余能量越大，被選為簇首的可能性越大；節點距離簇首越近，被選為簇首的可能性越大。分簇過程中眾多節點都會發送信息，在通信的過程中都會搶占信道，如果信息發送沖突或者在不合適的時候發送信息，比如普通節點還沒有選擇加入哪個簇時，簇首節點就向基站發送自身的ID標識和位置信息，就會導致信息紊亂，不知道現在的信息到底是發給誰的，應該由誰來接收，所以就需要制定規則，規定各節點發送信息的時間段。

4 教室燈光節能控制系統

以上通過仿真實驗證明PRIM-LEACH算法確實可行，在相同的條件下比以往的算法能夠節省將近一半能量。但是真實的情形與實驗模擬的情形不盡相同，下面將算法應用到實際的項目中，即教室燈光節能控制系統，觀察算法在真實情形下的表現狀況。

該系統利用本文提出的PRIM-LEACH算法對無線傳感器網絡進行簇首選取和簇間路由路徑選擇，能夠較真實的表現出該算法的工作情況。

4.1 項目內容

系統以單片機Am eg16為控制核心，利用nRF24L01無線收發模塊實現節點間通信，通過w5100無線上網模塊實現SINK與上位機通信。

該系統工作示意圖如圖所示。

4.2 項目學術價值

教室燈光節能控制系統是為了驗證本文提出的PRIM-LEACH協議，該協議不僅可以應用在教室燈光節能控制系統中，還可以應用在其他的類似調度控制系統中。教室燈光節能控制系統能夠改進現在高校教室以及類似場所對電力的利用率，在以下幾個方面有所突破。

1）解決了利用紅外熱釋電傳感器感知人體位置所面臨的三個問題：

（1）增強感知精度

（2）設置關燈感知時間

（3）設置開燈感知時間

2）與傳統的教室燈光節能控制系統相比，在對應燈安裝傳感器節點，可獲得人體所在的大體位置，然后相應的打開對應的燈，保證了在滿足照明需要的前提下，大幅度節能。

3）應用PRIM-LEACH算法，能夠有效地節省能源，使整個網絡的存活時間延長。在項目的開展和實際應用中，利用PRIM-LEACH算法會導致整個項目的復雜度有所提升，但是好處也是顯而易見的，那就是網絡的生命周期得到提升，而這也是無線傳感器網絡最為關鍵的評價指標。

4.3 項目實施步驟

項目實施步驟包括構造傳感器節點、部署傳感器節點、放置中央控制器和系統集成四步，其中在構造傳感器節點時，程序控制命令就已經寫在了單片機上。系統集成時會運用前面提到的PRIM-LEACH算法來選取簇首以及選取簇間路由路徑。

5 總結與展望

本文通過理論分析證明協議的高效，同時利用實驗仿真來驗證理論分析的正確，而且還有實際項目證明了協議的可行性。但是協議還相對粗糙，模型定義相對簡單，下一步的工作就是針對不同的情形制定不同的傳輸機制，不同的情況制定不同的能量等級。同時每一輪工作時，都需要進行分簇會過多的消耗能量，未來會考慮應該何時分簇。

[1] 李成法,陳貴海,葉懋,吳杰. 一種基于非均勻分簇的無線傳感器網絡路由協議[J] . 計算機學報,2007,30(1):65-67.

[2] 鄭國桓,周瑤,張柯.高校教室燈光節能控制系統的設計[J] .光明工程學報,2010，2(2):22-27.

[3] 徐進,劉坤.智能化照明系統的研究.光明工程學報[J] .2010,21(2):33-37.

[4] Manjeshwar A, Agrawal DP. TEEN: A routing protocol for enhanced ef f iciency in wireless sensor networks. In:Proceedings of the 15th Paral lel and Dist ributed Processing Symposium. San Francisco: IEEE Computer Societ y, 2001,3(2):54～59.

[5] Wendi B. Heinzelman, Anantha P. Chandrakasan and Hari Balakrishnan. Appl ication-speci fic protocol architecture for wireless microsensor networks, 2003, 4:25-30.