Energy Efficient Clustering,Optimum Data Forwarding for Wireless Sensor Networks.pdf

1、近年來，隨著微機(jī)電技術(shù)(Micro-Electro-Mechanical Systems，MEMS)的不斷發(fā)展，無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，WSN）在國際上備受關(guān)注并取得了廣泛應(yīng)用。典型的無線傳感器網(wǎng)絡(luò)通常無基礎(chǔ)設(shè)施，并將大量的無線傳感器節(jié)點(diǎn)隨機(jī)部署于無人看管的惡劣環(huán)境中，用于采集各種數(shù)據(jù)。每個傳感器的傳感能力、處理能力和通信能力都是有限的。傳感單元可以測量傳感器感知到的周圍環(huán)境參數(shù)并將其轉(zhuǎn)換成電信號

2、。在實(shí)際應(yīng)用中，為了降低開銷，往往需要設(shè)備至少生存幾年，因此我們面臨著一個挑戰(zhàn)，因?yàn)椴渴鹪趷毫迎h(huán)境中的傳感器不能被充電或者更換電池。
　　因此，如何有效使用傳感器的能量是延長網(wǎng)絡(luò)壽命的關(guān)鍵點(diǎn)，因?yàn)楫?dāng)一個傳感器的能量耗盡時會與整個網(wǎng)絡(luò)斷開連接，進(jìn)而影響實(shí)際應(yīng)用的效果。
　　把網(wǎng)絡(luò)中的傳感器分為互不重疊的部分，并通過每一部分的頭節(jié)點(diǎn)來向基站發(fā)送數(shù)據(jù)的方法被稱為分簇，分簇可以有效地節(jié)省網(wǎng)絡(luò)能量、提高系統(tǒng)的可擴(kuò)展性。
　　分簇

3、技術(shù)可以有效降低能耗是因?yàn)槊總€簇頭可以控制簇內(nèi)活動性，并與其他簇頭和基站進(jìn)行通信。分簇協(xié)議涉及兩個重要的方面，一個是簇頭的選擇，另一個是節(jié)點(diǎn)如何選擇其所歸屬的簇頭。由于簇頭可以控制該簇的活動性，因此簇內(nèi)節(jié)點(diǎn)大多數(shù)時間可切換為低功耗的睡眠模式，從而降低能耗。
　　在無線傳感器網(wǎng)絡(luò)中，傳感器節(jié)點(diǎn)所采集的數(shù)據(jù)無線傳輸至Sink節(jié)點(diǎn)。通過監(jiān)測節(jié)點(diǎn)地理位置，傳感器節(jié)點(diǎn)可將所采集的感知信息無線傳送至中繼節(jié)點(diǎn)。為了實(shí)現(xiàn)節(jié)能的目的，可在簇頭或Si

4、nk節(jié)點(diǎn)上采用適當(dāng)?shù)臄?shù)據(jù)聚合函數(shù)來處理從傳感器發(fā)來的大量數(shù)據(jù)。在數(shù)據(jù)聚合過程中，一些信息可被整合在一起并由相同的位數(shù)表示，從而實(shí)現(xiàn)通信過程中的節(jié)能，數(shù)據(jù)發(fā)送的頻率則取決于特定的應(yīng)用。
　　無線傳感器網(wǎng)絡(luò)中會出現(xiàn)多對一的情況，這將導(dǎo)致靠近Sink節(jié)點(diǎn)的節(jié)點(diǎn)比遠(yuǎn)離Sink節(jié)點(diǎn)的節(jié)點(diǎn)更容易引發(fā)嚴(yán)重的競爭和擁塞。當(dāng)競爭和擁塞加劇，丟包率也會隨之加大，因?yàn)榭拷黃ink的節(jié)點(diǎn)承擔(dān)巨大的數(shù)據(jù)包傳輸任務(wù)，因而需要消耗更多的能量，導(dǎo)致能量過早耗完，

5、使此Sink節(jié)點(diǎn)與網(wǎng)絡(luò)的其它部分?jǐn)嚅_連接。
　　由于單個傳感節(jié)點(diǎn)的性能差異，數(shù)據(jù)融合技術(shù)還存在一些障礙，網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)面臨著一些挑戰(zhàn):
　　傳感器節(jié)點(diǎn)的低可靠性問題。網(wǎng)絡(luò)層中的問題，如傳感器的內(nèi)存、處理能力及電池壽命有限。處理技術(shù)和通信協(xié)議需容忍單個節(jié)點(diǎn)故障、適應(yīng)不斷變化的環(huán)境、檢查傳感數(shù)據(jù)的完整性，并在有限的條件下，提取有效信息并進(jìn)行時-空數(shù)據(jù)聚合。還有傳感數(shù)據(jù)中的異常與噪聲、NP難數(shù)據(jù)聚合時間、數(shù)據(jù)傳輸中的能耗，另外

6、由于數(shù)據(jù)流是每次一條消息，所以如何獲取完整的鄰居節(jié)點(diǎn)信息和聚合信息也是一個挑戰(zhàn)。
　　針對傳感器能量有限的問題，本文提出了一系列解決此問題的算法。
　　首先，我們提出了一種新型聚類算法:高效能源聚類算法(EECR)，通過有效利用傳感器的能源，以延長無線傳感器網(wǎng)絡(luò)壽命。EECR延長網(wǎng)絡(luò)生存期并且提高性能，這是因?yàn)樗心芰μ幚泶罅侩S機(jī)分布的傳感器，同時能夠處理特殊形狀的簇，適應(yīng)于各種不同大小的簇。
　　EECR采用一個小數(shù)

7、量的傳感器網(wǎng)絡(luò)，每個傳感器都代表一個簇。如果在任何一對傳感器節(jié)點(diǎn)中兩個簇之間的距離是最短的，合并兩個簇。然后從每個簇中選擇數(shù)量恒定的一小部分節(jié)點(diǎn)作為簇代表，傳感器彼此之間盡可能遠(yuǎn)（位于簇的邊界）。一般來說，簇內(nèi)傳感器的恒定數(shù)量應(yīng)大于10。如果值小于10，那么代表節(jié)點(diǎn)將不能真實(shí)反映簇的結(jié)構(gòu)。接著，如果兩個簇內(nèi)各有一個代表性的傳感器，且這兩個傳感器足夠接近，那么合并兩個簇。重復(fù)這一合并的步驟，直到不再有足夠接近的簇。這樣每個傳感器Si與簇代

8、表傳感器進(jìn)行比較，如果某個代表傳感器與Si距離較近，則Si被分配到此代表傳感器相應(yīng)的簇。
　　每個簇的質(zhì)心（協(xié)調(diào)中心）是已知的，最接近質(zhì)心的傳感器將被選為簇頭，用來平衡所有傳感器和其簇頭間的距離。這樣可以減少在傳感器和簇頭之間進(jìn)行長距離數(shù)據(jù)分組傳輸?shù)哪芰肯摹Ｔ谶@點(diǎn)的WSN簇形成，簇頭為每個傳感節(jié)點(diǎn)分配了一個TDMA時隙。
　　在每一次EECR聚類算法中，傳感器監(jiān)測環(huán)境、記錄事件，并將其報告給它的簇頭。如果簇頭的剩余能量低于

9、其閾值，在非簇頭節(jié)點(diǎn)中選出一個比簇頭節(jié)點(diǎn)能量高的點(diǎn)作為下一輪的備用簇頭，以此避免分簇的額外開銷。由于傳感器在感知、處理數(shù)據(jù)以及將數(shù)據(jù)包傳輸?shù)酱仡^的過程中，其能量會不斷消耗殆盡以致失效，所以當(dāng)一半以上的傳感器失效時，會啟動重聚類過程，根據(jù)新的參數(shù)，如傳感器數(shù)量、傳感器能量以及融合閾值來重新聚合未失效的傳感器。
　　EECR算法的時間復(fù)雜度為O(1)，空間復(fù)雜度與n成線性關(guān)系，這要優(yōu)于LEACH算法。
　　我們根據(jù)事件等級將事件

10、分為三種類:正常事件，重要事件，關(guān)鍵事件（事件分類取決于具體應(yīng)用）。本文采用Cuckoo Search Optimization, CSO算法，讓每種類型的事件能高效地找到最佳的傳感節(jié)點(diǎn)來轉(zhuǎn)發(fā)記錄的數(shù)據(jù)包。
　　CSO算法的靈感來自于Xin-she Yang和Suash Deb提出的元啟發(fā)式優(yōu)化算法，即巢里每個蛋代表一種解決方法，而一個蛋代表一種新的解決方法。這樣做的目地在于用新的以及可能的更好的方法（杜鵑）來取代在巢比較差的方法

11、。CSO算法有以下三個基本原則:
　　1、每個杜鵑一次只下一個蛋，并把蛋隨機(jī)放在一個巢中。
　　2、具有高質(zhì)量的蛋的巢將會延續(xù)給下一代。
　　3、可用的主巢的數(shù)量是固定的，主巢中的鳥找到以固定概率下蛋的杜鵑所下的蛋。
　　隨機(jī)游動和萊維飛行應(yīng)用于通用方程的新的解決方案的計算，并且隨機(jī)游動與杜鵑蛋和主巢的鳥蛋間的相似性有聯(lián)系。
　　一個重要的問題是如何在通用方程中應(yīng)用萊維飛行和隨機(jī)游動，來產(chǎn)生新的解決方案。對

12、于一個固定的迭代次數(shù)，步長決定隨機(jī)游動能走多遠(yuǎn)。如果步長太大，則產(chǎn)生的新方法離原來的方法太遠(yuǎn)（甚至跳出了邊界），所以這樣的移動是不能接受的。如果步長太小，變化太小以至于變化沒有意義，從而導(dǎo)致這樣搜索的效率不高。因此，適當(dāng)?shù)牟介L對于盡可能維持搜索的高效性是很重要的。
　　其次，本文提出利用CSO算法的離散形式作為一個自然啟發(fā)的元啟發(fā)式算法，用來尋找最佳傳感節(jié)點(diǎn)，該節(jié)點(diǎn)將把感知的本地事件數(shù)據(jù)包轉(zhuǎn)發(fā)給簇頭（每種類型的事件有不同數(shù)量的傳感

13、器）。
　　每種類型的事件可以在興趣領(lǐng)域被若干傳感器檢測出來，并且每個傳感器能夠把報告發(fā)送給匯聚節(jié)點(diǎn)或其簇頭，但是這樣做將傳送冗余數(shù)據(jù)，從而導(dǎo)致傳感節(jié)點(diǎn)浪費(fèi)能量去轉(zhuǎn)發(fā)重復(fù)數(shù)據(jù)，造成網(wǎng)絡(luò)擁塞，簇頭在接收數(shù)據(jù)時會損耗能量并失去額外可聚合這些數(shù)據(jù)的能量。
　　如果在TI內(nèi)，第三個傳感器Rel Sens收到了來自B_Sens的數(shù)據(jù)包，Rel_Sens將把該數(shù)據(jù)包發(fā)送給鄰近的簇頭。另外，如果Rel_Sens出現(xiàn)硬件錯誤或存在信道故障，

14、沒有收到該數(shù)據(jù)包，那么Rel_Sens將給Cont_Sens發(fā)送一個控制信息來通知Rel_Sens沒有獲得該數(shù)據(jù)包并要求獲得這個數(shù)據(jù)包。Cont_Sens將會接收到來自Rel_Sens的控制信息并發(fā)送數(shù)據(jù)包給Rel_Sens。然后Rel_Sens將接收到的數(shù)據(jù)包發(fā)送給其簇頭。
　　運(yùn)用杜鵑優(yōu)化算法通過以下的元組R=尋找以最小能耗發(fā)送數(shù)據(jù)包到簇頭的最佳傳

15、感器。
　　在TNS中，每個巢有許多蛋，每個蛋代表一種解決方法，最好的解決方法是杜鵑，將傳遞給下一代。
　　這個函數(shù)返回三個最優(yōu)傳感器，這個返回結(jié)果將會被如下利用:最優(yōu)傳感器表示很可靠傳輸數(shù)據(jù)包的傳感器，而次優(yōu)傳感器表示可靠的交換和接力傳感器的控制消息，第三個最優(yōu)傳感器將數(shù)據(jù)包轉(zhuǎn)發(fā)至基站。
　　對于多節(jié)點(diǎn)的選擇，本文和具有代表性的兩種算法進(jìn)行了比較，和LEACH協(xié)議進(jìn)行比較時，我們的算法在在降低能耗、提高網(wǎng)絡(luò)生命周期與

16、網(wǎng)絡(luò)吞吐率上有著較高的優(yōu)勢。
　　MNS選擇方案包括雙節(jié)點(diǎn)選擇和三節(jié)點(diǎn)選擇，也通過能量消耗、網(wǎng)絡(luò)生命周期、網(wǎng)絡(luò)吞吐率來衡量其性能。
　　短時間內(nèi)，LEACH的穩(wěn)定時期和不穩(wěn)定時期分別比MNS少70％和30％，而到具體的事件時，就會有5％的丟包率，這也影響了網(wǎng)絡(luò)的生命周期。
　　通過存活節(jié)點(diǎn)數(shù)目衡量網(wǎng)絡(luò)生命周期時，我們的DNS，MNS方案在70％的特殊事件和30％的重要事件上比LEACH有明顯的優(yōu)勢，因?yàn)樗麄冎辉诤苌俚膫?/p>

17、感器上進(jìn)行數(shù)據(jù)傳輸，而不需要大量的簇內(nèi)傳感器。
　　整個的網(wǎng)絡(luò)能量消耗顯示LEACH協(xié)議在數(shù)據(jù)聚合時消耗了大量能量，然而在我們的方案保留了足夠的量能，可以讓它持續(xù)運(yùn)行更多的周期。
　　最后比較了整體吞吐量（所有從常規(guī)節(jié)點(diǎn)到簇頭節(jié)點(diǎn)和從簇頭節(jié)點(diǎn)到基站的傳輸?shù)臄?shù)據(jù)包）。EECR的整體吞吐量比LEACH，MH-LEACH，和E-LEACH要高，因?yàn)镋ECR穩(wěn)定時段和不穩(wěn)定時段都比LEACH，MH-LEACH，和E-LEACH要長，

18、這提高了在網(wǎng)絡(luò)中的數(shù)據(jù)傳輸。
　　Vir_ Clu_ Gen的性能評估顯示，它比E-LEACH和EECR算法更可靠。這是因?yàn)镋-LEACH和EECR的不穩(wěn)定時段與穩(wěn)定時段相對較短。Vir_ Clu_Gen可提高網(wǎng)絡(luò)內(nèi)存活節(jié)點(diǎn)的數(shù)量，這也就提高了網(wǎng)絡(luò)壽命。在整體網(wǎng)絡(luò)能耗方面，E-LEACH和EECR消耗能量的速度比Vir_Clu_Gen快得多。在整體吞吐量方面，由于E-LEACH和EECR的不穩(wěn)定時段和穩(wěn)定時段都比Vir_ Clu_