楊艷琦

（西安培華學(xué)院教務(wù)管理中心，陜西 西安 710125）

0 引言

無(wú)線(xiàn)傳感器網(wǎng)絡(luò)（WSNs，Wireless Sensor Networks）是一種無(wú)基礎(chǔ)設(shè)施的無(wú)線(xiàn)自組織網(wǎng)絡(luò)，綜合了傳感器技術(shù)、嵌入式技術(shù)、分布式信息處理技術(shù)和通信技術(shù)，能夠協(xié)作地實(shí)時(shí)監(jiān)測(cè)、感知和采集網(wǎng)絡(luò)分布區(qū)域內(nèi)的各種環(huán)境或監(jiān)測(cè)對(duì)象的信息，并對(duì)這些信息進(jìn)行處理，從而獲得詳細(xì)準(zhǔn)確的信息，傳送給需要這些信息的用戶(hù)。無(wú)線(xiàn)傳感器網(wǎng)絡(luò)被稱(chēng)為對(duì)21世紀(jì)具有巨大影響力的技術(shù)之一[1]。無(wú)線(xiàn)傳感器節(jié)點(diǎn)具有數(shù)量龐大、體積微小、通信和計(jì)算能力弱、電源能量有限且無(wú)法彌補(bǔ)、能量異構(gòu)等特點(diǎn)[2]。

傳感器節(jié)點(diǎn)計(jì)算所消耗的能量要遠(yuǎn)遠(yuǎn)小于數(shù)據(jù)傳輸所消耗的能量，網(wǎng)內(nèi)查詢(xún)處理成為提高網(wǎng)絡(luò)壽命的重要手段，其核心手段就是采取數(shù)據(jù)聚合技術(shù)來(lái)盡可能地減少數(shù)據(jù)傳送的能量消耗，利用節(jié)點(diǎn)對(duì)數(shù)據(jù)的預(yù)處理，可以減少消息傳送的數(shù)量或者大小，從而實(shí)現(xiàn)能量的有效利用。數(shù)據(jù)聚合是WSNs中實(shí)現(xiàn)節(jié)能的關(guān)鍵技術(shù)，通過(guò)去除冗余的數(shù)據(jù)信息，減少網(wǎng)絡(luò)的通信量，提高能量的有效性[3-6]。

分簇算法主要是選擇簇頭以及更好地使用簇頭節(jié)點(diǎn)對(duì)收集到的數(shù)據(jù)進(jìn)行處理然后轉(zhuǎn)發(fā)至Sink節(jié)點(diǎn)，這里如果不對(duì)簇頭節(jié)點(diǎn)收集到的數(shù)據(jù)進(jìn)行聚合處理的話(huà)，簇頭節(jié)點(diǎn)會(huì)很快地消耗掉能量，導(dǎo)致網(wǎng)絡(luò)的負(fù)載不均衡。通過(guò)對(duì)LEACH算法[5]進(jìn)行仿真，如果簇頭不進(jìn)行數(shù)據(jù)聚合而直接收集轉(zhuǎn)發(fā)的話(huà)，在網(wǎng)絡(luò)運(yùn)行一定輪數(shù)之后會(huì)發(fā)現(xiàn)很多節(jié)點(diǎn)的剩余能量很低。

1 最優(yōu)數(shù)據(jù)通信鏈路構(gòu)建算法

1.1 網(wǎng)絡(luò)模型

為了更好地表述所提算法，在這里對(duì)網(wǎng)絡(luò)作以下假設(shè)：

1）在正方形區(qū)域內(nèi)隨機(jī)部署N個(gè)同構(gòu)節(jié)點(diǎn)，節(jié)點(diǎn)布置好之后不再移動(dòng)；

2）每個(gè)節(jié)點(diǎn)具有相同的通信半徑；

3）鄰居節(jié)點(diǎn)信息可知；

4）節(jié)點(diǎn)的初始能量相同；

5）節(jié)點(diǎn)具有壓縮數(shù)據(jù)功能；

6）Sink節(jié)點(diǎn)位置可調(diào)；

7）網(wǎng)絡(luò)運(yùn)行一輪更新一次；

8）只有一種類(lèi)型的攻擊節(jié)點(diǎn)。

本研究的能耗模型同LEACH，假設(shè)一個(gè)節(jié)點(diǎn)傳輸l比特的能耗是：

一個(gè)節(jié)點(diǎn)接收l(shuí)bits比特的能耗是：

其中，εfs代表自由空間下單位距離傳輸數(shù)據(jù)的放大器能耗，Eelec代表節(jié)點(diǎn)收發(fā)一個(gè)單位數(shù)據(jù)包消耗的單位能量，l代表單位數(shù)據(jù)包的大小，εmp代表多路衰減模型下單位距離傳輸數(shù)據(jù)的放大器能耗。

1.2 分簇模型

在簇頭節(jié)點(diǎn)的選擇中，LEACH算法根據(jù)提前設(shè)置好的概率隨機(jī)選擇網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)成為簇頭節(jié)點(diǎn)，本研究在簇頭節(jié)點(diǎn)選擇時(shí)綜合考慮節(jié)點(diǎn)的剩余能量、節(jié)點(diǎn)可通信節(jié)點(diǎn)的數(shù)量以及節(jié)點(diǎn)離Sink節(jié)點(diǎn)的距離。首先根據(jù)以上幾種考慮因素計(jì)算每個(gè)節(jié)點(diǎn)作為簇頭候選節(jié)點(diǎn)的值，然后在滿(mǎn)足最大連通子圖占比90%的條件下從候選簇頭節(jié)點(diǎn)中，按照候選值從高到低依次選擇合適的候選簇頭節(jié)點(diǎn)成為真正的簇頭節(jié)點(diǎn)。

假設(shè)簇頭節(jié)點(diǎn)的候選集合Cadidate_CH{ }，簇頭節(jié)點(diǎn)集合List CH{ }，對(duì)于任意的一個(gè)節(jié)點(diǎn)vi，ERemain-i表示vi節(jié)點(diǎn)的剩余能量，EInitial代表網(wǎng)絡(luò)中所有節(jié)點(diǎn)的初始能量，Degmax表示網(wǎng)絡(luò)中節(jié)點(diǎn)可通信最多的節(jié)點(diǎn)數(shù)，Degi表示節(jié)點(diǎn)vi可通信的節(jié)點(diǎn)數(shù)。

計(jì)算vi節(jié)點(diǎn)作為簇頭的候選值：

其中α，β表示大于零的參數(shù)，滿(mǎn)足α+β=1。

1.3 混合數(shù)據(jù)通信模型

分簇完成之后，網(wǎng)絡(luò)基于上述最大覆蓋、最小能耗問(wèn)題構(gòu)建了本研究提出的最優(yōu)數(shù)據(jù)通信鏈路構(gòu)建算法。按照上述方法對(duì)網(wǎng)絡(luò)進(jìn)行分簇處理之后，接下來(lái)構(gòu)建每一個(gè)簇頭節(jié)點(diǎn)到Sink節(jié)點(diǎn)的路徑。為了降低算法的復(fù)雜，使簇內(nèi)的通信為單向直接通信，即成員節(jié)點(diǎn)直接將收集到的數(shù)據(jù)傳送給簇頭節(jié)點(diǎn)。簇內(nèi)數(shù)據(jù)傳完之后，簇頭節(jié)點(diǎn)此時(shí)需要將數(shù)據(jù)傳送給Sink節(jié)點(diǎn)，研究者經(jīng)常采取以下三種方法：1）Sink節(jié)點(diǎn)使用貪婪算法構(gòu)建到簇頭的多跳路徑，路徑中只有簇頭節(jié)點(diǎn)；2）Sink節(jié)點(diǎn)使用貪婪算法構(gòu)建到簇頭的多跳路徑，路徑中只有非簇頭節(jié)點(diǎn)，所有簇頭節(jié)點(diǎn)均為葉子節(jié)點(diǎn)，不再作為中繼節(jié)點(diǎn)；3）混合路徑，構(gòu)建簇頭到Sink節(jié)點(diǎn)的最優(yōu)路徑，簇頭節(jié)點(diǎn)、非簇頭節(jié)點(diǎn)均可以作為中繼節(jié)點(diǎn)。為了加強(qiáng)節(jié)點(diǎn)的負(fù)載平衡，選擇第三種樹(shù)型-分簇型混合路徑模型進(jìn)行數(shù)據(jù)的傳輸。最優(yōu)數(shù)據(jù)通信鏈路構(gòu)建算法1如下。

輸入：最優(yōu)數(shù)據(jù)通信鏈路Data Trans{ }=NULL，存活節(jié)點(diǎn)數(shù)N，Sink節(jié)點(diǎn)位置S（a，b），存活節(jié)點(diǎn)位置V（xi,yi）,i=1,2,…,N，節(jié)點(diǎn)vi的鄰居節(jié)點(diǎn)信息集合Neighborvi{ }，節(jié)點(diǎn)通信半徑r。

2 仿真實(shí)驗(yàn)

筆者針對(duì)OTCEE算法與經(jīng)典的混合型算法EEICS、PEDAD，樹(shù)型算法GIT以及混合型算法LEACH，將從網(wǎng)絡(luò)壽命、網(wǎng)絡(luò)平均延遲等角度進(jìn)行仿真比較。

各算法網(wǎng)絡(luò)壽命的比較圖如圖1所示，可以從圖1中看出算法OTCEE的壽命明顯優(yōu)于其他幾種比較的算法LEACH、GIT、PEDAP、EEICS。當(dāng)有第一個(gè)節(jié)點(diǎn)死亡時(shí)，OTCEE算法的壽命為8 015輪，EEICS為7 514輪，PEDAP為4 632輪，GIT為4 520輪，LEACH為4 026輪。當(dāng)有10個(gè)節(jié)點(diǎn)死亡時(shí)，OTCEE算法的壽命為10 526輪，EEICS為8 074輪，PEDAP為8 106輪，GIT為7 835輪，LEACH為7 726輪，算法的壽命提升率較EECIS提升了30.36%，較PADAP提升了34.34%。這是因?yàn)楸狙芯克崴惴∣TCEE分簇時(shí)均衡考慮了能量的消耗等，建立了最優(yōu)的分簇拓?fù)浣Y(jié)構(gòu)，并且在最終的數(shù)據(jù)傳輸階段建立了混合型的數(shù)據(jù)傳輸路徑，將網(wǎng)絡(luò)中剩余能量較多的節(jié)點(diǎn)加入數(shù)據(jù)傳輸路徑從而降低了節(jié)點(diǎn)的能耗，延遲了節(jié)點(diǎn)死亡的時(shí)間。

圖1 網(wǎng)絡(luò)壽命

數(shù)據(jù)傳輸?shù)膶?shí)時(shí)性是網(wǎng)絡(luò)開(kāi)銷(xiāo)的重要指標(biāo)，延遲越低數(shù)據(jù)傳輸?shù)男阅茉綇?qiáng)。各算法網(wǎng)絡(luò)平均延遲比較圖如圖2所示。從圖2中可以看出LEACH 算法的延遲最低，因?yàn)長(zhǎng)EACH算法的數(shù)據(jù)傳輸拓?fù)鋯我?，簇?nèi)直接傳播，簇頭節(jié)點(diǎn)到Sink也是單向直接傳播，從而延遲最低。但是延遲低的代價(jià)是網(wǎng)絡(luò)壽命較低，需基于此綜合考慮網(wǎng)絡(luò)開(kāi)銷(xiāo)。從圖2中可以看出幾種算法延遲均隨著網(wǎng)絡(luò)節(jié)點(diǎn)的增加而增加，這是因?yàn)閿?shù)據(jù)量的增加以及拓?fù)渲兄欣^節(jié)點(diǎn)的數(shù)量增加從而導(dǎo)致了延遲的增加。同樣的仿真環(huán)境下本研究所提算法OTCEE的延遲低于其他幾種算法的延遲，這是因?yàn)閺拇仡^到Sink建立了最優(yōu)的混合路徑，從而有效地降低了數(shù)據(jù)的傳輸延遲。

圖2 網(wǎng)絡(luò)平均延遲

3 結(jié)束語(yǔ)

綜上所述，無(wú)線(xiàn)傳感器網(wǎng)絡(luò)被稱(chēng)為對(duì)21世紀(jì)具有巨大影響力的技術(shù)之一，無(wú)線(xiàn)傳感器節(jié)點(diǎn)具有數(shù)量龐大、體積微小、通信和計(jì)算能力弱、電源能量有限且無(wú)法彌補(bǔ)、能量異構(gòu)等特點(diǎn)。構(gòu)建一種能量高效且負(fù)載均衡的分簇算法是研究無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的主要目的。