一種基于空間相關(guān)性的WSNs 節(jié)點(diǎn)睡眠調(diào)度算法*

程明月，馬婭婕，趙 蕾，肖 凡

(1.武漢科技大學(xué) 信息科學(xué)與工程學(xué)院，湖北 武漢430081;2.武漢科技大學(xué) 冶金工業(yè)過(guò)程系統(tǒng)科學(xué)湖北省重點(diǎn)實(shí)驗(yàn)室，湖北 武漢430081)

0 引 言

為了有效地分析大氣污染的分布與地理環(huán)境、人類(lèi)活動(dòng)、天氣變化之間的關(guān)系，有必要將傳感器節(jié)點(diǎn)密集分布，但這種部署會(huì)帶來(lái)采樣數(shù)據(jù)的急劇增長(zhǎng)［1］。由于龐大的采樣數(shù)據(jù)在同一時(shí)間傳送至匯聚節(jié)點(diǎn)而導(dǎo)致網(wǎng)絡(luò)擁塞、數(shù)據(jù)延時(shí)等問(wèn)題。同時(shí)，由于傳感器節(jié)點(diǎn)的電池能量有限，更換電池困難，這就使節(jié)能成為無(wú)線傳感器網(wǎng)絡(luò)(WSNs)中需要考慮的重要因素。基于以上考慮，需要建立一個(gè)完善的節(jié)點(diǎn)調(diào)度機(jī)制來(lái)避免擁塞并延長(zhǎng)網(wǎng)絡(luò)的壽命。

影響節(jié)點(diǎn)調(diào)度策略的因素眾多，國(guó)內(nèi)外研究學(xué)者在這個(gè)領(lǐng)域進(jìn)行了一系列的研究，其中，最早、最典型的分簇調(diào)度算法之一是一種低功耗自適應(yīng)分簇路由協(xié)議，即LEACH算法［2］。LEACH 算法減小了節(jié)點(diǎn)能量消耗，但是在簇頭選舉時(shí)忽略了節(jié)點(diǎn)自身的能量，容易出現(xiàn)低能量簇頭節(jié)點(diǎn)而引發(fā)數(shù)據(jù)傳輸中斷、傳感器網(wǎng)絡(luò)數(shù)據(jù)失真等缺點(diǎn)。文獻(xiàn)［3］提出PEGASIS 算法，核心思想是盡量減少直接與Sink 節(jié)點(diǎn)進(jìn)行通信的節(jié)點(diǎn)，這種算法需要清楚所有節(jié)點(diǎn)的地理位置信息，嚴(yán)重提高了網(wǎng)絡(luò)開(kāi)銷(xiāo)。為此，文獻(xiàn)［4］基于“1∶1 雙簇容錯(cuò)技術(shù)”和“層次簇頭概率”等技術(shù)及概念提出了ECHNL(equal cluster head distribution based on network level)算法，并在分層的網(wǎng)絡(luò)區(qū)域內(nèi)對(duì)網(wǎng)絡(luò)的信息采集過(guò)程進(jìn)行優(yōu)化。該算法在簇頭分布合理的情況下最大限度降低了網(wǎng)絡(luò)能耗，但是忽略了網(wǎng)絡(luò)的通信質(zhì)量這一重要指標(biāo)，在實(shí)際應(yīng)用中的效果并不太理想。

本文基于WSNs 中的流量和能耗問(wèn)題，設(shè)計(jì)了一種基于空間相關(guān)性的節(jié)點(diǎn)睡眠調(diào)度算法(spatial correlationbased algorithm for node sleeping scheduling，SCASS)。該算法使用空間相關(guān)性和節(jié)點(diǎn)剩余能量組成權(quán)值函數(shù)來(lái)選擇最優(yōu)節(jié)點(diǎn)作為監(jiān)測(cè)區(qū)域的代表節(jié)點(diǎn)進(jìn)行數(shù)據(jù)傳送，未被選中節(jié)點(diǎn)則處于睡眠狀態(tài)，以此來(lái)降低節(jié)點(diǎn)能耗，延長(zhǎng)網(wǎng)絡(luò)壽命，提高通信性能。

1 SCASS 描述

1.1 大氣污染物等級(jí)劃分

根據(jù)國(guó)家環(huán)境局研究分析，大氣污染具有極其明顯的時(shí)空相關(guān)性。污染物的濃度變化是一個(gè)微小而緩慢持續(xù)的過(guò)程，在時(shí)間上，相對(duì)較短時(shí)間內(nèi)大氣污染物濃度的變化幾乎為零;在空間上，空間距離越相近的節(jié)點(diǎn)數(shù)據(jù)更具有相似性。首先將污染物濃度轉(zhuǎn)換為API 指數(shù)(污染標(biāo)準(zhǔn)指數(shù))［5］，并進(jìn)一步將污染程度劃分如表1 所示的7 個(gè)等級(jí)。

表1 污染標(biāo)準(zhǔn)指數(shù)等級(jí)劃分Tab 1 Pollution standard index grade partition

1.2 節(jié)點(diǎn)睡眠調(diào)度算法

1.2.1 節(jié)點(diǎn)狀態(tài)轉(zhuǎn)換

本算法利用傳感器節(jié)點(diǎn)感知數(shù)據(jù)的空間相關(guān)性除去冗余節(jié)點(diǎn)，同時(shí)減少數(shù)據(jù)量的傳送，避免過(guò)重的信道競(jìng)爭(zhēng)，在保證滿足用戶需求的前提下，延長(zhǎng)網(wǎng)絡(luò)壽命，同時(shí)提高服務(wù)質(zhì)量。

SCASS 中節(jié)點(diǎn)的狀態(tài)轉(zhuǎn)換模型如圖1 所示。

圖1 節(jié)點(diǎn)狀態(tài)轉(zhuǎn)換圖Fig 1 Node state transform diagram

1)睡眠狀態(tài):處于睡眠狀態(tài)的節(jié)點(diǎn)只進(jìn)行數(shù)據(jù)采集，而不進(jìn)行數(shù)據(jù)傳輸。經(jīng)過(guò)延時(shí)Δt 后，轉(zhuǎn)入半睡眠狀態(tài)。

2)半睡眠狀態(tài):處于半睡眠狀態(tài)的節(jié)點(diǎn)基于調(diào)度算法選舉出最具有代表性的節(jié)點(diǎn)，該代表節(jié)點(diǎn)進(jìn)入活動(dòng)狀態(tài)，否則，回到睡眠狀態(tài)。

3)活動(dòng)狀態(tài):處于活動(dòng)狀態(tài)的節(jié)點(diǎn)進(jìn)行數(shù)據(jù)采集，并將采集到的數(shù)據(jù)傳送至Sink 節(jié)點(diǎn)。工作一定時(shí)間Δt 后轉(zhuǎn)入睡眠狀態(tài)，且不參與下一輪的選舉。

處于半睡眠狀態(tài)的各個(gè)傳感器節(jié)點(diǎn)采集污染數(shù)據(jù)，并判斷出本節(jié)點(diǎn)所處的污染等級(jí)，則其通信半徑內(nèi)的區(qū)域都屬于該等級(jí)區(qū)域塊。若相鄰節(jié)點(diǎn)處于同一等級(jí)，則其所在的區(qū)域?qū)⒖梢院喜橥坏燃?jí)區(qū)域塊。針對(duì)每一個(gè)獨(dú)立的區(qū)域，選擇最具有代表性的節(jié)點(diǎn)進(jìn)入活動(dòng)狀態(tài)，并將采集到的數(shù)據(jù)作為該區(qū)域污染濃度的采樣值發(fā)送至Sink 節(jié)點(diǎn);而其他節(jié)點(diǎn)則都回到睡眠狀態(tài)。

1.2.2 空間相關(guān)性的計(jì)算

根據(jù)表1 所示的污染標(biāo)準(zhǔn)指數(shù)等級(jí)劃分，對(duì)于其中某一塊區(qū)域A，V 是該區(qū)域內(nèi)的節(jié)點(diǎn)集合，i∈V。

定義1 鄰居節(jié)點(diǎn)集:假設(shè)每個(gè)傳感器節(jié)點(diǎn)的通信半徑相等且為r，則以該節(jié)點(diǎn)為圓心，半徑為r 的圓內(nèi)所有節(jié)點(diǎn)都可以與該節(jié)點(diǎn)建立通信連接。這些點(diǎn)組成的集合即為該節(jié)點(diǎn)的鄰居節(jié)點(diǎn)集。

定義2 根據(jù)表1 所示的污染標(biāo)準(zhǔn)指數(shù)等級(jí)劃分，若N 是i∈V 的鄰居節(jié)點(diǎn)集，j∈N 是i 的某鄰居節(jié)點(diǎn)。在連續(xù)t 個(gè)采樣時(shí)間點(diǎn)內(nèi)，節(jié)點(diǎn)i 的采樣數(shù)據(jù)為X=［x1，x2，…，xt］，j 的采樣數(shù)據(jù)為Y=［y1，y2，…，yt］。

X 的期望表示為

X 的方差表示為

同理

X 與Y 的協(xié)方差表示為

其中，pij為X 取值xi和Y 取值yj時(shí)的聯(lián)合分布概率。

X 與Y 的空間相關(guān)系數(shù)表示為

利用上述算法過(guò)程，將節(jié)點(diǎn)i 與其鄰居節(jié)點(diǎn)集的每一個(gè)鄰居節(jié)點(diǎn)進(jìn)行相關(guān)系數(shù)的運(yùn)算，則該節(jié)點(diǎn)的平均空間相關(guān)系數(shù)ρxi(0≤ρxi≤1)可以表示為

其中，|N(j)|表示i 的鄰居節(jié)點(diǎn)集的個(gè)數(shù)。

根據(jù)實(shí)際給定門(mén)限值ρ0和ρ'0，有兩種情況:

1)若ρXi∈(0，ρ0)，說(shuō)明該節(jié)點(diǎn)具有相對(duì)較強(qiáng)的空間相關(guān)性，則可以得到候選節(jié)點(diǎn)集S;

2)若ρXi≥ρ'0，說(shuō)明該節(jié)點(diǎn)所處環(huán)境特殊或者其他情況，則將此節(jié)點(diǎn)作為特殊代表節(jié)點(diǎn)單獨(dú)列出，所采集數(shù)據(jù)直接發(fā)送至Sink 節(jié)點(diǎn)。

1.2.3 基于能量的權(quán)值計(jì)算

由于每個(gè)傳感器節(jié)點(diǎn)的能量有限，為了均衡網(wǎng)絡(luò)能耗，本算法基于剩余能量在候選節(jié)點(diǎn)集S 中選擇最終的代表節(jié)點(diǎn)。

定義3 假設(shè)每個(gè)傳感器節(jié)點(diǎn)的初始能量都相同，記為Ein;無(wú)線傳感器網(wǎng)絡(luò)工作一段時(shí)間以后的剩余能量為Ese，則節(jié)點(diǎn)i 在進(jìn)行代表節(jié)點(diǎn)選舉過(guò)程中的權(quán)重wi為

對(duì)每一個(gè)候選代表節(jié)點(diǎn)做如式(8)所示的權(quán)重處理，空間相關(guān)系數(shù)越大，權(quán)重越大，所采集到的數(shù)據(jù)越具有代表性;剩余能量比例越大，權(quán)重也會(huì)越大，通過(guò)均衡節(jié)點(diǎn)剩余能量，從而達(dá)到延長(zhǎng)WSNs 壽命的目的。最終所選取代表節(jié)點(diǎn)為

在區(qū)域A 中滿足條件ρXi≥ρ'0和式(9)的節(jié)點(diǎn)，即為最終的代表節(jié)點(diǎn)。

被選擇的代表節(jié)點(diǎn)從半睡眠態(tài)轉(zhuǎn)為活躍狀態(tài)，未被選擇的節(jié)點(diǎn)則由半睡眠態(tài)轉(zhuǎn)換為睡眠態(tài)。待整個(gè)系統(tǒng)網(wǎng)絡(luò)穩(wěn)定工作Δt 時(shí)間后，進(jìn)行新一輪的代表節(jié)點(diǎn)的選舉。其中，上一輪被選中的代表節(jié)點(diǎn)將直接轉(zhuǎn)為睡眠態(tài)，其余節(jié)點(diǎn)由睡眠態(tài)進(jìn)入半睡眠態(tài)，并參與新一輪的代表節(jié)點(diǎn)的選舉。

2 算法性能分析

2.1 復(fù)雜度分析

在對(duì)區(qū)域中每個(gè)節(jié)點(diǎn)進(jìn)行空間相關(guān)性運(yùn)算的時(shí)間復(fù)雜度是O(n2)，在根據(jù)每個(gè)節(jié)點(diǎn)的空間相關(guān)性進(jìn)行代表節(jié)點(diǎn)選舉階段的時(shí)間復(fù)雜度是O(n)。因此，整個(gè)算法的時(shí)間復(fù)雜度是O(n2)。假設(shè)WSNs 在該區(qū)域最大拓?fù)涞墓?jié)點(diǎn)個(gè)數(shù)為|V|，該算法在根據(jù)各個(gè)節(jié)點(diǎn)的空間相關(guān)性進(jìn)行代表節(jié)點(diǎn)的選舉時(shí)有信息交換，因此，該睡眠調(diào)度算法的消息復(fù)雜度是O|V|。

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

2.2.1 仿真環(huán)境

仿真實(shí)驗(yàn)采用Omnet++作為仿真平臺(tái)，版本為4.3。仿真實(shí)驗(yàn)所使用的數(shù)據(jù)選擇的是倫敦東區(qū)某區(qū)域中所采集到的大氣污染數(shù)據(jù)，每個(gè)節(jié)點(diǎn)均可采集到NO，NO2，SO2，O3四種污染物的濃度，采集的數(shù)據(jù)單位是PPM。每個(gè)采樣點(diǎn)從早上8:00 到下午18:00，每隔1 min 對(duì)四種污染物的濃度進(jìn)行一次采樣。由于，大氣污染物濃度15 min 內(nèi)的變化較小，因此，本文中Δt 的值選取為15 min，采樣頻率為1 次/min。實(shí)際地理環(huán)境和節(jié)點(diǎn)分布如圖2 所示。

圖2 實(shí)驗(yàn)數(shù)據(jù)采樣地點(diǎn)圖Fig 2 Experimental data sampling location map

2.2.2 實(shí)驗(yàn)結(jié)果分析

通過(guò)運(yùn)行SCASS 對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)的平均剩余能量、穩(wěn)定工作一段時(shí)間后的活躍節(jié)點(diǎn)數(shù)，以及網(wǎng)絡(luò)通信中所產(chǎn)生的時(shí)延進(jìn)行了仿真，并與文獻(xiàn)［4］中的算法進(jìn)行了對(duì)比。其中，仿真使用10×14 的方格拓?fù)浣Y(jié)構(gòu)，采用CGD 路由協(xié)議［6］。節(jié)點(diǎn)初始化能量為100 J，帶寬為20 kbps，偵聽(tīng)功率0.02 W，接收功率為0.1 W，傳輸功率為0.3 W。

節(jié)點(diǎn)剩余能量隨時(shí)間變化仿真結(jié)果如圖3 所示。從圖3所示的仿真結(jié)果可以看出:隨著時(shí)間的推移，節(jié)點(diǎn)剩余能量逐漸減小，總體而言，SCASS的剩余能量值始終比ECHNL 的高，并且時(shí)間越長(zhǎng)，顯示差距越大。

圖3 節(jié)點(diǎn)剩余能量與時(shí)間關(guān)系Fig 3 Relationship between node residual energy and time

從圖4 所示的仿真結(jié)果可以看出:隨著網(wǎng)絡(luò)穩(wěn)定工作時(shí)間的延續(xù)，網(wǎng)絡(luò)死亡節(jié)點(diǎn)數(shù)不斷增多，這是由于部分節(jié)點(diǎn)因能量消耗過(guò)多，不能維持傳感器節(jié)點(diǎn)的持續(xù)工作而死亡。并且由圖4 明顯看到，SCASS 的死亡節(jié)點(diǎn)數(shù)低于ECHNL 算法。

圖4 死亡節(jié)點(diǎn)數(shù)與時(shí)間關(guān)系Fig 4 Relationship between node numders and time of death

從圖5 所示的仿真結(jié)果可以看出:隨著節(jié)點(diǎn)數(shù)的增多，網(wǎng)絡(luò)數(shù)據(jù)量和負(fù)載也隨之增加，導(dǎo)致網(wǎng)絡(luò)時(shí)延不斷增大，二者算法差距并不大，但是SCASS 始終優(yōu)于ECHNL 算法，并且隨著節(jié)點(diǎn)數(shù)的增多，優(yōu)勢(shì)越來(lái)越明顯。

圖5 數(shù)據(jù)包延遲與節(jié)點(diǎn)數(shù)量關(guān)系Fig 5 Relationship between data packet delay and number of nodes

3 結(jié) 論

本文基于傳感器節(jié)點(diǎn)的空間相關(guān)性，并綜合考慮節(jié)點(diǎn)的剩余能量，提出了針對(duì)高密度部署的WSNs 的節(jié)點(diǎn)調(diào)度算法。該算法與ECHNL 算法相比，在一定程度上減少了網(wǎng)絡(luò)平均能量消耗，同時(shí)緩解了數(shù)據(jù)量過(guò)大而造成的網(wǎng)絡(luò)擁塞。通過(guò)仿真實(shí)驗(yàn)可知:本文算法在節(jié)省網(wǎng)絡(luò)能耗，延長(zhǎng)網(wǎng)絡(luò)壽命的同時(shí)，還降低了數(shù)據(jù)傳輸?shù)臅r(shí)延。

［1］ Ezovski G M，Watkins E V.The electronic sensor node and the future of government－issued RFID－Based Identification［C］∥IEEE International Conference，United states，IEEE Press，2007:15－22.

［2］ Ma Y，Richards M，Ghanem M，et al.Air pollution monitoring and mining based on sensor grid in London［J］.Sensors，2008，11(2):3601－3623.

［3］ Li B P，Zhang X Q.Research and improvement of LEACH protocol for wireless sensor networks［C］∥International Conference on Information Engineering(ICIE)Singapore，2012:234－239.

［4］ 王愛(ài)美.基于LEACH 協(xié)議的無(wú)線傳感器網(wǎng)絡(luò)分簇算法研究［D］.蘭州:蘭州交通大學(xué)，2013.

［5］ Reddy A，Kumar A，Janakiram D.Wireless sensor networks operating systems:A survey［J］.International Journal of Sensor Networks，2009，5(4):236－255.

［6］ Mamidisetty K K，Duan M L，Sastry S.Multipath dissemination in regular mesh topologies［J］.IEEE Transactions on Parallel and Distributed Systems，2009，20(8):1188－1201.