PRIM-LEACH高效聚類路由算法的研究與實(shí)際應(yīng)用

劉 斌

（山東大學(xué)外國語學(xué)院, 濟(jì)南 250000）

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

1 無線傳感器網(wǎng)絡(luò)概述

1.1 無線傳感器網(wǎng)絡(luò)的結(jié)構(gòu)

無線傳感器節(jié)點(diǎn)、感知對象、觀察者共同組成了無線傳感器網(wǎng)絡(luò)的三大要素，承擔(dān)著網(wǎng)絡(luò)的構(gòu)建任務(wù)，網(wǎng)絡(luò)結(jié)構(gòu)如下圖1-1所示。

1.2 無線傳感器網(wǎng)絡(luò)的特點(diǎn)

與傳統(tǒng)網(wǎng)絡(luò)相比，無線傳感器網(wǎng)絡(luò)有以下幾大特點(diǎn)：

1）能量有限

2）計(jì)算能力有限

3）存儲能力有限

4）通信范圍有限

5）拓?fù)浣Y(jié)構(gòu)時(shí)刻變化

6）自組織性

2 無線傳感器網(wǎng)絡(luò)路由協(xié)議

無線傳感器網(wǎng)絡(luò)的能源有效性是指消耗單位能量的情況下解決的數(shù)據(jù)請求數(shù)量。無線傳感器節(jié)點(diǎn)攜帶的能量很少，減少能量的消耗是設(shè)計(jì)必須要考慮的問題。

不同于傳統(tǒng)網(wǎng)絡(luò)的特點(diǎn)與應(yīng)用，所以無線傳感器網(wǎng)絡(luò)不能照搬傳統(tǒng)網(wǎng)絡(luò)的路由協(xié)議，需要設(shè)計(jì)專用的路由協(xié)議。路由協(xié)議的設(shè)計(jì)開發(fā)過程中有以下幾個(gè)困難。

1）沒有唯一的標(biāo)示符，節(jié)點(diǎn)的尋址不方便。

2）所有的節(jié)點(diǎn)都可以采集數(shù)據(jù)，發(fā)送到目標(biāo)節(jié)點(diǎn)。

3）有大量冗余的節(jié)點(diǎn)存在，采集的數(shù)據(jù)會有很大一部分是相同的，需要進(jìn)行數(shù)據(jù)融合。

4）每個(gè)節(jié)點(diǎn)的能量是有限的，由于能量的限制，導(dǎo)致每個(gè)節(jié)點(diǎn)的存儲能力、處理能力和傳輸能力都很有限。

從上述幾個(gè)特點(diǎn)可以看出，無線傳感器網(wǎng)絡(luò)的路由協(xié)議是需要專門設(shè)計(jì)的。

LEACH協(xié)議是一種典型的無線傳感器網(wǎng)絡(luò)路由協(xié)議，該協(xié)議中根據(jù)一定的規(guī)則進(jìn)行分簇，然后選取簇首節(jié)點(diǎn)，所有的簇首節(jié)點(diǎn)都直接與基站進(jìn)行通信，這樣不可避免地浪費(fèi)大量的能量，特別是距離基站比較遠(yuǎn)的簇首節(jié)點(diǎn)，導(dǎo)致整個(gè)無線傳感器網(wǎng)絡(luò)存活時(shí)間縮短。LEACH-EE在LEACH的基礎(chǔ)上，提出了一個(gè)新的算法，能夠有效改善LEACH協(xié)議的存活時(shí)間。LEACH-EE根據(jù)一定的算法，在簇首之間形成一條多跳鏈，各簇首的數(shù)據(jù)沿著多跳鏈傳遞給基站，這樣就能有效節(jié)省距離基站遠(yuǎn)的簇首節(jié)點(diǎn)的能量。但是在拓?fù)渎酚尚畔鬟f時(shí)，簇首節(jié)點(diǎn)形成的多跳鏈可能會形成迂回，這樣部分能量會消耗在迂回的過程中，導(dǎo)致能量消耗和網(wǎng)絡(luò)存活時(shí)間的縮短[3,4]。

LEACH-EE協(xié)議的網(wǎng)絡(luò)拓?fù)鋱D如下圖4-1所示，從圖中可以清晰地看出簇首生成的多條鏈所形成的迂回問題。

3 PRIM-LEACH實(shí)驗(yàn)仿真

為了驗(yàn)證以上算法的正確性，本文以m atlab對實(shí)驗(yàn)過程進(jìn)行了仿真，比較了PRIM—LEACH，LEACH以及LEACH—EE三種協(xié)議，從仿真中可以看出PRIM-LEACH確實(shí)能夠延長網(wǎng)絡(luò)存活期。

3.1 仿真的目

仿真的目的是為了查看無線傳感器網(wǎng)絡(luò)在PRIM-LEACH協(xié)議的工作狀況，最關(guān)心的問題就是能量的使用情況。

3.2 仿真結(jié)果

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

4 教室燈光節(jié)能控制系統(tǒng)

以上通過仿真實(shí)驗(yàn)證明PRIM-LEACH算法確實(shí)可行，在相同的條件下比以往的算法能夠節(jié)省將近一半能量。但是真實(shí)的情形與實(shí)驗(yàn)?zāi)M的情形不盡相同，下面將算法應(yīng)用到實(shí)際的項(xiàng)目中，即教室燈光節(jié)能控制系統(tǒng)，觀察算法在真實(shí)情形下的表現(xiàn)狀況。

該系統(tǒng)利用本文提出的PRIM-LEACH算法對無線傳感器網(wǎng)絡(luò)進(jìn)行簇首選取和簇間路由路徑選擇，能夠較真實(shí)的表現(xiàn)出該算法的工作情況。

4.1 項(xiàng)目內(nèi)容

系統(tǒng)以單片機(jī)Am eg16為控制核心，利用nRF24L01無線收發(fā)模塊實(shí)現(xiàn)節(jié)點(diǎn)間通信，通過w5100無線上網(wǎng)模塊實(shí)現(xiàn)SINK與上位機(jī)通信。

該系統(tǒng)工作示意圖如圖所示。

4.2 項(xiàng)目學(xué)術(shù)價(jià)值

教室燈光節(jié)能控制系統(tǒng)是為了驗(yàn)證本文提出的PRIM-LEACH協(xié)議，該協(xié)議不僅可以應(yīng)用在教室燈光節(jié)能控制系統(tǒng)中，還可以應(yīng)用在其他的類似調(diào)度控制系統(tǒng)中。教室燈光節(jié)能控制系統(tǒng)能夠改進(jìn)現(xiàn)在高校教室以及類似場所對電力的利用率，在以下幾個(gè)方面有所突破。

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

（1）增強(qiáng)感知精度

（2）設(shè)置關(guān)燈感知時(shí)間

（3）設(shè)置開燈感知時(shí)間

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

3）應(yīng)用PRIM-LEACH算法，能夠有效地節(jié)省能源，使整個(gè)網(wǎng)絡(luò)的存活時(shí)間延長。在項(xiàng)目的開展和實(shí)際應(yīng)用中，利用PRIM-LEACH算法會導(dǎo)致整個(gè)項(xiàng)目的復(fù)雜度有所提升，但是好處也是顯而易見的，那就是網(wǎng)絡(luò)的生命周期得到提升，而這也是無線傳感器網(wǎng)絡(luò)最為關(guān)鍵的評價(jià)指標(biāo)。

4.3 項(xiàng)目實(shí)施步驟

項(xiàng)目實(shí)施步驟包括構(gòu)造傳感器節(jié)點(diǎn)、部署傳感器節(jié)點(diǎn)、放置中央控制器和系統(tǒng)集成四步，其中在構(gòu)造傳感器節(jié)點(diǎn)時(shí)，程序控制命令就已經(jīng)寫在了單片機(jī)上。系統(tǒng)集成時(shí)會運(yùn)用前面提到的PRIM-LEACH算法來選取簇首以及選取簇間路由路徑。

5 總結(jié)與展望

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

[1] 李成法,陳貴海,葉懋,吳杰. 一種基于非均勻分簇的無線傳感器網(wǎng)絡(luò)路由協(xié)議[J] . 計(jì)算機(jī)學(xué)報(bào),2007,30(1):65-67.

[2] 鄭國桓,周瑤,張柯.高校教室燈光節(jié)能控制系統(tǒng)的設(shè)計(jì)[J] .光明工程學(xué)報(bào),2010，2(2):22-27.

[3] 徐進(jìn),劉坤.智能化照明系統(tǒng)的研究.光明工程學(xué)報(bào)[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.