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

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

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

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

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

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

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

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

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

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

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

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

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

13、器）。
　　每種類型的事件可以在興趣領(lǐng)域被若干傳感器檢測(cè)出來(lái)，并且每個(gè)傳感器能夠把報(bào)告發(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í)會(huì)損耗能量并失去額外可聚合這些數(shù)據(jù)的能量。
　　如果在TI內(nèi)，第三個(gè)傳感器Rel Sens收到了來(lái)自B_Sens的數(shù)據(jù)包，Rel_Sens將把該數(shù)據(jù)包發(fā)送給鄰近的簇頭。另外，如果Rel_Sens出現(xiàn)硬件錯(cuò)誤或存在信道故障，

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

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

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

17、感器上進(jìn)行數(shù)據(jù)傳輸，而不需要大量的簇內(nèi)傳感器。
　　整個(gè)的網(wǎng)絡(luò)能量消耗顯示LEACH協(xié)議在數(shù)據(jù)聚合時(shí)消耗了大量能量，然而在我們的方案保留了足夠的量能，可以讓它持續(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)定時(shí)段和不穩(wěn)定時(shí)段都比LEACH，MH-LEACH，和E-LEACH要長(zhǎng)，

18、這提高了在網(wǎng)絡(luò)中的數(shù)據(jù)傳輸。
　　Vir_ Clu_ Gen的性能評(píng)估顯示，它比E-LEACH和EECR算法更可靠。這是因?yàn)镋-LEACH和EECR的不穩(wěn)定時(shí)段與穩(wěn)定時(shí)段相對(duì)較短。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)定時(shí)段和穩(wěn)定時(shí)段都比Vir_ Clu_