無(wú)線(xiàn)傳感器網(wǎng)絡(luò )的動(dòng)態(tài)拓撲能量有效成簇算法

1 引言

無(wú)線(xiàn)傳感器網(wǎng)絡(luò )（Wireless Sensor Network，WSN）作為下一代的信息獲取技術(shù)引起了世界各國的重視，日漸成為國內外學(xué)術(shù)機構的研究熱點(diǎn)。無(wú)線(xiàn)傳感器網(wǎng)絡(luò )通常是由大量傳感器節點(diǎn)通過(guò)射頻通信形成的一個(gè)自組織網(wǎng)絡(luò )系統。它通過(guò)對被監測對象目標信息的感知，獲取和處理，提供給管理者以有用的信息，可以廣泛地應用于智能家居、醫療衛生、工業(yè)控制、農業(yè)種植、軍事預警以及防洪救災等特殊場(chǎng)合。但是，WSN與移動(dòng)Ad Hoc網(wǎng)絡(luò )（MANET）是有著(zhù)很大區別的，它們的通信方式、通信目的和網(wǎng)絡(luò )拓撲很不相同，尤其在能量來(lái)源方面，WSN是采用電池供電，路由算法對傳感器網(wǎng)絡(luò )的存活周期起著(zhù)重要的影響，所以移動(dòng)Ad Hoc網(wǎng)絡(luò )的路由協(xié)議不能完全適應于WSN，我們需要單獨研究適合于無(wú)線(xiàn)傳感器網(wǎng)絡(luò )的通信協(xié)議。

2動(dòng)態(tài)拓撲能量有效成簇算法

針對層次路由協(xié)議中存在的各種問(wèn)題，本文提出了適用于WSN的動(dòng)態(tài)拓撲能量有效成簇算法(DTEE)。此算法引入基于能量因子的低復雜度的簇頭選擇機制，同時(shí)通過(guò)協(xié)議的設計使其支持節點(diǎn)部分離去或有新節點(diǎn)加入的拓撲動(dòng)態(tài)傳感器網(wǎng)絡(luò )。在簇間數據傳輸上通過(guò)多跳算法使數據以最優(yōu)路徑傳向匯聚節點(diǎn)，系統能耗很小，網(wǎng)絡(luò )的生命周期最大化。

3．1網(wǎng)絡(luò )模型

本文中假設傳感器節點(diǎn)隨機分布在一個(gè)長(cháng)方形形監測區域內，并且該傳感器網(wǎng)絡(luò )具有以下性質(zhì)：

1) 網(wǎng)絡(luò )中所有傳感器節點(diǎn)都是同構的，具有相同的初始能量，并且能量有限；

2) 傳感器節點(diǎn)的發(fā)送功率可以進(jìn)行離散調節，可以根據傳輸距離的遠近來(lái)調節其發(fā)射功率

3) 匯聚節點(diǎn)具有較強的計算能力和較大的存儲容量，且能量無(wú)限制，其無(wú)線(xiàn)信號可以覆蓋整個(gè)傳感器網(wǎng)絡(luò )。

4) 傳感器網(wǎng)絡(luò )部署以后，可以出現部分節點(diǎn)隨著(zhù)時(shí)間的推移而移動(dòng)；

5) 傳感器節點(diǎn)具有數據融合功能。

6) 位置上相鄰的節點(diǎn)采集到的數據具有很大的關(guān)聯(lián)性。

3．2能量模型

在無(wú)線(xiàn)傳輸中，信號強度隨著(zhù)傳輸距離的增加而呈指數衰減。文獻[3]提出了兩種信道模型：自由空間(free space)模型和多路衰減(multi-path fading)模型。當發(fā)射器與接收器的距離d小于閾值時(shí)，采用自由空間模型，信號功率呈d2衰減；否則采用多路衰減模型，信號功率呈d⁴ 衰減。

3．3成簇策略

在LEACH算法中執行過(guò)程是周期性進(jìn)行的，每一輪包括簇的建立階段和穩定的數據傳輸階段。在簇的建立階段，通過(guò)選舉使某個(gè)節點(diǎn)成為簇首節點(diǎn)，成為簇首的節點(diǎn)向周?chē)濣c(diǎn)廣播消息，其他節點(diǎn)根據接收到的廣播消息的強度來(lái)選擇它所要加入的簇，并告知相應的簇首。在本文提出的DTEE算法中，也是以輪為形式周期進(jìn)行的，但在簇頭選舉引入了能量因子，同時(shí)第一輪和以后輪的算法過(guò)程是不同的，從第二輪開(kāi)始在成簇階段可以不用計算公式，相比LEACH及一些改進(jìn)算法需要計算復雜公式的開(kāi)銷(xiāo)，降低了復雜度，使簇頭選舉能量開(kāi)銷(xiāo)最低，成簇過(guò)程中采用的非均勻成簇方法更是使網(wǎng)絡(luò )能量分布更加均衡。

由于本文采用的是簇內單跳，簇間多跳的數據傳輸，因此離Sink節點(diǎn)遠的簇頭節點(diǎn)，數據轉發(fā)量越少，能量消耗的慢；而離Sink節點(diǎn)越近的簇頭，其所承擔的數據轉發(fā)業(yè)務(wù)越多，消耗能量越大，所以更容易出現能量耗盡而死亡的情況。為此，本文拋棄了傳統算法中采用的均勻分簇的方法，而是采用非均勻成簇的策略。使離Sink節點(diǎn)越近的簇，其規模越小一些，從而這些簇其簇內路由及數據融合開(kāi)銷(xiāo)小，又因為其所承擔的簇頭間數據轉發(fā)開(kāi)銷(xiāo)多，綜合起來(lái)無(wú)論離Sink遠還是近的簇頭都將能量相對均衡消耗，網(wǎng)絡(luò )生命周期得以最大化。

非均勻分簇的實(shí)現過(guò)程是這樣的：首先，Sink節點(diǎn)向網(wǎng)絡(luò )所在區域廣播一個(gè)NOTICE報文，網(wǎng)絡(luò )中所有節點(diǎn)根據接收到的此報文能量強度信息確定自己與Sink節點(diǎn)的距離d(i)。根據監測區域范圍、傳感器節點(diǎn)個(gè)數以及能量自由空間模型確定網(wǎng)絡(luò )分層數n, 然后，本文采用文獻[14]中的均勻分層的方法，各節點(diǎn)所在的層號i=d(i)*n/R，R為監測區域半徑。因為靠近Sink節點(diǎn)的簇規模小，簇內節點(diǎn)少，也就是所在不同層次的節點(diǎn)成為簇頭的概率不一樣，各節點(diǎn)成為簇頭的最佳概率為pi=p/(i*i)。其中p為第一層節點(diǎn)成為簇頭的概率。將傳感區域進(jìn)行劃分這個(gè)動(dòng)作只出現在第一輪循環(huán)開(kāi)始的時(shí)候，以后的循環(huán)過(guò)程不用再進(jìn)行傳感區域劃分。

3．4簇頭選擇

之后開(kāi)始第一輪的選舉，各節點(diǎn)產(chǎn)生一個(gè)隨機數 r(n) ，并與T(n)進(jìn)行比較，若r(n)小于T(n)，則節點(diǎn)自選舉成為簇頭。

G為這一輪循環(huán)中未成為簇首的節點(diǎn)的集合。

當節點(diǎn)成為簇頭后，以適當的半徑RC廣播簇頭加入消息，周?chē)墓濣c(diǎn)根據接收信號強度決定加入哪個(gè)簇并發(fā)送一個(gè)請求加入消息。之后簇頭在接收到相關(guān)節點(diǎn)的請求加入消息后，建立TDMA調度表并廣播出去。簇內節點(diǎn)在收到此消息后，在屬于自己的時(shí)隙內打開(kāi)無(wú)線(xiàn)電模塊開(kāi)始數據傳送，在其它不屬于自己的時(shí)隙內關(guān)掉通信功能以最大限度節省能量。在簇內節點(diǎn)向簇頭發(fā)送數據報文時(shí)，在其中加入一個(gè)本節點(diǎn)此刻剩余能量的數據信息，供之后算法使用。

第二輪及以后輪的簇頭產(chǎn)生過(guò)程中，首先是上一輪的舊簇頭對收到各節點(diǎn)報文中含有的各節點(diǎn)能量信息及自己的剩余能量進(jìn)行比較，從中選出剩余能量最大的節點(diǎn)為新簇頭，之后舊簇頭以半徑RC發(fā)出new_CH報文，報文中包括報文類(lèi)型及新簇頭的ID，當指定的新簇頭收到此報文后發(fā)現ID與之相匹配，就廣播簇頭加入報文，其余節點(diǎn)再根據接收信號強度決定加入哪個(gè)簇頭，之后過(guò)程與第一輪相同。但在實(shí)際應用中，網(wǎng)絡(luò )節點(diǎn)有可能意外被移動(dòng)了，或者出故障死亡了，這樣指定的新簇頭就可能不存在了，從而這一簇范圍內節點(diǎn)由于沒(méi)收到簇頭加入報文就會(huì )整體停止工作，使網(wǎng)絡(luò )出現死區?？紤]此方面，本文設定舊簇頭節點(diǎn)在一定的時(shí)間閾值內若沒(méi)有指定的新節點(diǎn)發(fā)來(lái)的簇頭加入報文，它就確認指定的新節點(diǎn)被意味移動(dòng)走了，從而它指定剩余能量第二多的節點(diǎn)為新節點(diǎn)，并發(fā)送新的new_CH報文。這樣新算法就支持了部分節點(diǎn)移動(dòng)或者有新節點(diǎn)加入的動(dòng)態(tài)拓撲的網(wǎng)絡(luò )。

同時(shí)本文設計所有節點(diǎn)在任一輪循環(huán)中，從收到簇頭加入報文或new_CH報文開(kāi)始，啟動(dòng)一個(gè)計時(shí)器Timer，若在最大時(shí)限Tmax內沒(méi)有收到新的簇頭加入報文或new_CH報文，則啟動(dòng)從第一輪開(kāi)始新的簇頭選擇過(guò)程，相對于大多數算法只支持靜態(tài)網(wǎng)絡(luò )，本文的算法支持了小范圍地理位置變動(dòng)的傳感器網(wǎng)絡(luò )。