劉彩霞 李樹(shù)德

1 桂林航天工業(yè)學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院，廣西 桂林 541004；2 桂林航天工業(yè)學(xué)院 電子信息與自動(dòng)化學(xué)院，廣西 桂林 541004

隨著無(wú)線傳感器技術(shù)的進(jìn)步，無(wú)線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks, WSN)的應(yīng)用越來(lái)越廣泛。但是，對(duì)于在野外或者復(fù)雜環(huán)境中部署的網(wǎng)絡(luò)而言，由于網(wǎng)絡(luò)中的節(jié)點(diǎn)大都是由電池供電，能量有限，能量消耗情況決定了網(wǎng)絡(luò)的生存時(shí)間，因此如何在當(dāng)前 WSN節(jié)點(diǎn)電量有限的前提下，有效延長(zhǎng)WSN的使用壽命，是當(dāng)前亟須解決的重要問(wèn)題。在無(wú)線傳感器網(wǎng)絡(luò)的實(shí)際應(yīng)用中，節(jié)點(diǎn)的部署有多種形式，但絕大多數(shù)無(wú)線傳感器網(wǎng)絡(luò)都是隨機(jī)部署的 ( 如森林防火、水質(zhì)監(jiān)測(cè)等)，網(wǎng)絡(luò)拓?fù)湟话銥榫W(wǎng)狀拓?fù)浣Y(jié)構(gòu)，其中絕大多數(shù)節(jié)點(diǎn)既要進(jìn)行數(shù)據(jù)采集，又要中轉(zhuǎn)轉(zhuǎn)發(fā)數(shù)據(jù)，對(duì)于這類節(jié)點(diǎn)(路由節(jié)點(diǎn))來(lái)說(shuō)，能量消耗比只進(jìn)行數(shù)據(jù)采集的節(jié)點(diǎn)(非路由節(jié)點(diǎn))要大很多。而當(dāng)路由節(jié)點(diǎn)的電量耗盡后，即使非路由節(jié)點(diǎn)仍然電量充足，整個(gè)網(wǎng)絡(luò)也無(wú)法正常工作了，因此，為了有效延長(zhǎng)網(wǎng)絡(luò)壽命，需要平衡路由節(jié)點(diǎn)與非路由節(jié)點(diǎn)之間的能量消耗。

1 研究現(xiàn)狀

針對(duì)延長(zhǎng)無(wú)線傳感器網(wǎng)絡(luò)壽命的研究成果比較多，截至目前，較典型的方案有以下幾種類型：

1.1 通過(guò)節(jié)點(diǎn)休眠方式延長(zhǎng)網(wǎng)絡(luò)壽命

文獻(xiàn)[1]提出一種基于統(tǒng)一時(shí)間的休眠機(jī)制，原理是根據(jù)網(wǎng)內(nèi)的統(tǒng)一時(shí)鐘來(lái)設(shè)置休眠。一旦時(shí)鐘計(jì)時(shí)到達(dá)時(shí)間，所有節(jié) 點(diǎn)統(tǒng)一進(jìn)入休眠狀態(tài)。對(duì)于無(wú)線傳感器網(wǎng)絡(luò)來(lái)說(shuō)，有一個(gè)統(tǒng)一的時(shí)鐘是很難做到的。文獻(xiàn)[2]和[3]提出了改進(jìn)方法，通過(guò)網(wǎng)內(nèi)節(jié)點(diǎn)定時(shí)與鄰居進(jìn)行數(shù)據(jù)包的交換來(lái)統(tǒng)一時(shí)鐘，一旦可以進(jìn)入休眠狀態(tài)，則全網(wǎng)統(tǒng)一休眠。數(shù)據(jù)包交換導(dǎo)致節(jié)點(diǎn)通信負(fù)擔(dān)加重，但也未必能保證節(jié)點(diǎn)時(shí)鐘的完全統(tǒng)一。

文獻(xiàn)[4]-[6]是以節(jié)點(diǎn)剩余能量多少作為判斷依據(jù)，提出各種節(jié)點(diǎn)調(diào)度算法；文獻(xiàn)[7]提出在簇型結(jié)構(gòu)中，以節(jié)點(diǎn)的剩余能量和網(wǎng)絡(luò)剩余能量的比值作為選擇簇頭節(jié)點(diǎn)的標(biāo)準(zhǔn)，剩余能量多的節(jié)點(diǎn)，被選為簇頭節(jié)點(diǎn)的概率大，進(jìn)而平衡整個(gè)網(wǎng)絡(luò)的能量消耗，延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間；文獻(xiàn)[8]則針對(duì)網(wǎng)絡(luò)內(nèi)部和邊界的節(jié)點(diǎn)進(jìn)行不同的調(diào)度，提出了一種冗余節(jié)點(diǎn)休眠調(diào)度算法，稱為RNSSA算法;文獻(xiàn)[9]使網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)輪流工作，降低了冗余覆蓋面積，有效地減少了網(wǎng)絡(luò)中的能量消耗，以上節(jié)點(diǎn)的休眠時(shí)間在整個(gè)節(jié)點(diǎn)調(diào)度過(guò)程中都采用固定的休眠設(shè)置，這樣會(huì)導(dǎo)致網(wǎng)絡(luò)中部分節(jié)點(diǎn)的能量消耗過(guò)快，引起節(jié)點(diǎn)過(guò)早失效;文獻(xiàn)[10]提出了動(dòng)態(tài)調(diào)整休眠時(shí)間的方法，根據(jù)節(jié)點(diǎn)以及節(jié)點(diǎn)剩余能量延長(zhǎng)或者縮短節(jié)點(diǎn)休眠時(shí)間，在此基礎(chǔ)上設(shè)計(jì)出節(jié)點(diǎn)休眠時(shí)間動(dòng)態(tài)調(diào)整的能量節(jié)約算法( STDA)；文獻(xiàn)[11]提出了一種基于廣播的節(jié)點(diǎn)休眠機(jī)制，并給出了廣播休眠方法的網(wǎng)絡(luò)控制策略，節(jié)點(diǎn)是否休眠是通過(guò)服務(wù)器來(lái)判斷的，減少了節(jié)點(diǎn)的負(fù)擔(dān)，且休眠時(shí)間是可以動(dòng)態(tài)調(diào)整的，可以有效延長(zhǎng) WSN 的壽命。

1.2 通過(guò)調(diào)整節(jié)點(diǎn)能耗來(lái)延長(zhǎng)網(wǎng)絡(luò)壽命

文獻(xiàn)[12]提出了一種節(jié)點(diǎn)協(xié)作的節(jié)能路由傳輸(ECGR)算法，將能耗平衡分布于諸多節(jié)點(diǎn),進(jìn)而延長(zhǎng)了網(wǎng)絡(luò)壽命。文獻(xiàn)[13]提出一種能耗均衡的自適應(yīng)拓?fù)洳┺乃惴ǎ撍惴ǜ鶕?jù)節(jié)點(diǎn)平均壽命調(diào)整自身的功率,幫助最短壽命節(jié)點(diǎn)降低功率,延長(zhǎng)整個(gè)網(wǎng)絡(luò)的生存時(shí)間． 文獻(xiàn)[14]針對(duì)異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)簇頭節(jié)點(diǎn)能耗大、網(wǎng)絡(luò)壽命較低等問(wèn)題,提出一種路由分簇算法，以均衡簇頭節(jié)點(diǎn)的能耗為目標(biāo),采用引力搜索算法對(duì)網(wǎng)絡(luò)簇頭的通信鏈路進(jìn)行規(guī)劃,從而降低簇頭節(jié)點(diǎn)間通信的負(fù)載能耗。

2 改進(jìn)的算法

2.1 算法描述

無(wú)線傳感器網(wǎng)絡(luò)的特點(diǎn)是組網(wǎng)靈活，待部署完畢，組網(wǎng)工作完成以后，網(wǎng)絡(luò)內(nèi)處于邊界位置的終端節(jié)點(diǎn)負(fù)責(zé)數(shù)據(jù)采集，而絕大多數(shù)處于中間位置的節(jié)點(diǎn)不僅負(fù)責(zé)數(shù)據(jù)采集，還要負(fù)責(zé)數(shù)據(jù)轉(zhuǎn)發(fā)，因此，處于中間位置的節(jié)點(diǎn)很容易比處于邊界位置的節(jié)點(diǎn)提前耗盡能量，并且，越靠近協(xié)調(diào)器的節(jié)點(diǎn)耗能越快，針對(duì)這種情況，本文提出了一種針對(duì)中間位置節(jié)點(diǎn)的休眠算法，將中間節(jié)點(diǎn)分成兩類，一類節(jié)點(diǎn)只負(fù)責(zé)采集數(shù)據(jù)，另一類節(jié)點(diǎn)只負(fù)責(zé)轉(zhuǎn)發(fā)數(shù)據(jù)，從而更好地平衡各節(jié)點(diǎn)之間的能量消耗。休眠節(jié)點(diǎn)的算法流程圖如圖1所示。算法步驟如下：

圖1 休眠節(jié)點(diǎn)算法

(1)首先判斷節(jié)點(diǎn)是否冗余，如果是則轉(zhuǎn)到(2)，否則轉(zhuǎn)到(4)；

(2)進(jìn)入休眠；

(3)本輪休眠結(jié)束，查看消息隊(duì)列，如果收到鄰居節(jié)點(diǎn)的休眠消息，則轉(zhuǎn)到(4)，否則轉(zhuǎn)到(2)；

(4)轉(zhuǎn)入預(yù)工作狀態(tài)；

(5)處理消息，如果發(fā)現(xiàn)有節(jié)點(diǎn)需要被替換，則轉(zhuǎn)到(6)，否則，清空消息列表，隨后轉(zhuǎn)到(2)；

(6)選擇一個(gè)目標(biāo)節(jié)點(diǎn)，并回復(fù)替換消息；

(7)查看是否收到被替換節(jié)點(diǎn)的確認(rèn)消息，如果收到確認(rèn)消息，則替換相應(yīng)節(jié)點(diǎn)進(jìn)入工作狀態(tài)，否則，清空消息列表，隨后轉(zhuǎn)到(2)。

工作節(jié)點(diǎn)的算法流程圖如圖2所示。步驟如下：

(1)節(jié)點(diǎn)正常工作；

(2)間隔一定時(shí)間，節(jié)點(diǎn)判斷一次自身剩余電量，如果剩余電量低于設(shè)定的值K1,則轉(zhuǎn)到(3)，否則轉(zhuǎn)到(1)；

(3)仍然正常工作并發(fā)送休眠消息，同時(shí)清空消息隊(duì)列；

(4)監(jiān)測(cè)消息隊(duì)列中是否收到替換消息，如果收到了替換消息，則發(fā)送確認(rèn)休眠消息，隨后處理完當(dāng)前數(shù)據(jù)后進(jìn)入休眠，否則等待時(shí)間T1后，轉(zhuǎn)到(3)。

圖2 工作節(jié)點(diǎn)算法

2.2 算法中部分步驟詳解

在休眠節(jié)點(diǎn)的算法的步驟(5)中，處理消息這個(gè)環(huán)節(jié)較復(fù)雜，需要判斷消息列表中是否有同一個(gè)節(jié)點(diǎn)發(fā)來(lái)的預(yù)休眠和確認(rèn)休眠消息。如果有，說(shuō)明這個(gè)節(jié)點(diǎn)已經(jīng)找到了替換節(jié)點(diǎn)；如果沒(méi)有，則按照消息來(lái)源將消息分成路由節(jié)點(diǎn)的和普通節(jié)點(diǎn)的兩類。選擇被替換節(jié)點(diǎn)時(shí)優(yōu)先選擇路由節(jié)點(diǎn)，每類節(jié)點(diǎn)中優(yōu)先選擇剩余電量最低的節(jié)點(diǎn)。但是，如果被替換節(jié)點(diǎn)的電量接近于或者明顯高于當(dāng)前節(jié)點(diǎn)的，則認(rèn)為沒(méi)有節(jié)點(diǎn)需要被替換。

在工作節(jié)點(diǎn)的算法步驟(2)中，對(duì)于正常工作的路由節(jié)點(diǎn)來(lái)說(shuō)，判斷剩余電量時(shí)設(shè)置的K1可以適當(dāng)大一些，比如可以設(shè)置為30%～40%，當(dāng)該路由節(jié)點(diǎn)休眠又蘇醒后，可以繼續(xù)用來(lái)替換其他需要休眠的節(jié)點(diǎn)，這樣做還可以保證初期進(jìn)入休眠的節(jié)點(diǎn)盡可能被用來(lái)替換路由節(jié)點(diǎn)，從而更好地平衡整個(gè)網(wǎng)絡(luò)的能耗；對(duì)于正常工作的普通節(jié)點(diǎn)來(lái)說(shuō)，判斷剩余電量時(shí)設(shè)置的K1盡量小一些，比如可以設(shè)置為5%左右，當(dāng)該普通節(jié)點(diǎn)休眠后，直接停止工作，不再用來(lái)替換任何節(jié)點(diǎn)，這樣做的好處是減少了節(jié)點(diǎn)的狀態(tài)轉(zhuǎn)換次數(shù)，明顯減少了因轉(zhuǎn)換狀態(tài)而進(jìn)行通信的次數(shù)，從而有效地為普通節(jié)點(diǎn)節(jié)約了能量。

在工作節(jié)點(diǎn)的算法步驟(4)中，若收到的替換消息只有一條，則直接發(fā)送確認(rèn)休眠消息；若收到的消息較多，則需要選擇一個(gè)電量最高的節(jié)點(diǎn)并發(fā)送確認(rèn)休眠消息；正常工作的普通節(jié)點(diǎn)剩余電量低于K1時(shí)，開(kāi)始發(fā)送預(yù)休眠消息，若收到的替換消息只有一條，也是直接發(fā)送確認(rèn)休眠消息；若收到的消息較多，則需要選擇一個(gè)電量最低的節(jié)點(diǎn)并發(fā)送確認(rèn)休眠消息；這樣做可以保證整個(gè)網(wǎng)絡(luò)在控制能耗平衡的情況下，更好地保證網(wǎng)絡(luò)的覆蓋率。

2.3 針對(duì)本算法對(duì)協(xié)議做相應(yīng)調(diào)整

為每個(gè)節(jié)點(diǎn)增加消息隊(duì)列，用于接收并保存鄰居節(jié)點(diǎn)發(fā)送的預(yù)休眠消息和確認(rèn)休眠消息。

預(yù)休眠消息中，應(yīng)該有一個(gè)字段標(biāo)記當(dāng)前節(jié)點(diǎn)編號(hào)，有一個(gè)字段用于標(biāo)記節(jié)點(diǎn)是路由節(jié)點(diǎn)還是普通節(jié)點(diǎn)，有一個(gè)字段標(biāo)記節(jié)點(diǎn)當(dāng)前剩余電量。

替換消息中，應(yīng)該有一個(gè)字段標(biāo)記當(dāng)前節(jié)點(diǎn)編號(hào)，有一個(gè)字段標(biāo)記被替換節(jié)點(diǎn)編號(hào)。

確認(rèn)休眠消息中，應(yīng)該有一個(gè)字段標(biāo)記當(dāng)前節(jié)點(diǎn)編號(hào)，應(yīng)該有一個(gè)字段用于標(biāo)記節(jié)點(diǎn)是路由節(jié)點(diǎn)還是普通節(jié)點(diǎn)，有一個(gè)字段標(biāo)記替換節(jié)點(diǎn)編號(hào)。

3 算法分析

3.1 本算法的創(chuàng)新點(diǎn)

(1)由于節(jié)點(diǎn)路由過(guò)程的能量消耗比數(shù)據(jù)采集的要高，尤其是靠近Sink節(jié)點(diǎn)的路由節(jié)點(diǎn)，能量消耗更快，因此，本算法在能滿足網(wǎng)絡(luò)覆蓋度要求的情況下，將布網(wǎng)后處于中間位置的節(jié)點(diǎn)分成兩類，一類節(jié)點(diǎn)只負(fù)責(zé)數(shù)據(jù)采集，另一類節(jié)點(diǎn)只負(fù)責(zé)數(shù)據(jù)轉(zhuǎn)發(fā)，冗余節(jié)點(diǎn)則直接進(jìn)入休眠狀態(tài)。

(2)為了保持整個(gè)網(wǎng)絡(luò)的有效覆蓋并減少鄰居節(jié)點(diǎn)間的通信，路由節(jié)點(diǎn)在電量低于一個(gè)較高值時(shí)，發(fā)送預(yù)休眠消息，選擇一個(gè)電量更高的休眠節(jié)點(diǎn)進(jìn)行替換；對(duì)于普通節(jié)點(diǎn)，當(dāng)其電量快耗盡時(shí)，才發(fā)送預(yù)休眠消息，找一個(gè)節(jié)點(diǎn)來(lái)替換。

3.2 本算法的適用范圍

本算法用于網(wǎng)絡(luò)中的冗余節(jié)點(diǎn)調(diào)度過(guò)程中，在網(wǎng)絡(luò)中存在大量冗余節(jié)點(diǎn)的情況下，相比于沒(méi)有休眠策略的網(wǎng)絡(luò)而言，毫無(wú)疑問(wèn)可以延長(zhǎng)網(wǎng)絡(luò)的生存時(shí)間；而對(duì)于應(yīng)用了休眠策略，但其中頻繁更換工作節(jié)點(diǎn)的算法，本算法通過(guò)合理設(shè)置K1值，可以有效地減少節(jié)點(diǎn)間的通信及路由調(diào)整帶來(lái)的開(kāi)銷，從而達(dá)到延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間的目的。

3.3 下一步需要深入研究的問(wèn)題

本算法中設(shè)置了消息隊(duì)列，用于收集節(jié)點(diǎn)處于休眠狀態(tài)時(shí)鄰居節(jié)點(diǎn)發(fā)送的消息，對(duì)于消息隊(duì)列的實(shí)現(xiàn)機(jī)制還需要進(jìn)一步的深入研究。

4 總結(jié)

本文提出一種算法，首先將中間位置節(jié)點(diǎn)分成只負(fù)責(zé)采集數(shù)據(jù)和只負(fù)責(zé)發(fā)送數(shù)據(jù)兩類節(jié)點(diǎn)，并使布網(wǎng)完成后的冗余節(jié)點(diǎn)直接進(jìn)入休眠狀態(tài)，之后，通過(guò)合理設(shè)置K1值，來(lái)有效調(diào)度休眠節(jié)點(diǎn)。通過(guò)性能分析，本算法在網(wǎng)絡(luò)中存在大量冗余節(jié)點(diǎn)的情況下，可以達(dá)到更好地延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間的效果。但對(duì)于消息隊(duì)列的實(shí)現(xiàn)機(jī)制還需要進(jìn)一步的深入研究。