煤礦井下WSN能量均衡的節(jié)點(diǎn)部署算法研究*

崔麗珍,許凡非,王巧利,李丹陽

(內(nèi)蒙古科技大學(xué)信息工程學(xué)院,內(nèi)蒙古 包頭 014010)

無線傳感器網(wǎng)絡(luò)WSN(Wireless Sensor Network)是由部署于目標(biāo)監(jiān)測場地內(nèi)的大量傳感器節(jié)點(diǎn)組成的網(wǎng)絡(luò)系統(tǒng),這些節(jié)點(diǎn)具有體型小、價(jià)格低、功耗低等特點(diǎn)。傳感器節(jié)點(diǎn)的應(yīng)用環(huán)境通常比較復(fù)雜,且節(jié)點(diǎn)能量有限,因此特定場景下網(wǎng)絡(luò)的生存周期問題成為WSN研究的重要內(nèi)容之一錯(cuò)誤!未找到引用源。。通過WSN的節(jié)點(diǎn)部署和覆蓋控制技術(shù)能夠?qū)?jié)點(diǎn)進(jìn)行靈活部署,滿足不同應(yīng)用場景的需求,可提高網(wǎng)絡(luò)的覆蓋率和連通性,減少網(wǎng)絡(luò)的能量消耗,進(jìn)一步延長網(wǎng)絡(luò)的生存周期,將該技術(shù)應(yīng)用到煤礦井下能夠有效地提高信息傳輸?shù)目煽啃?減少事故發(fā)生隱患,保障煤礦井下生產(chǎn)人員的生命財(cái)產(chǎn)安全[1]。

Wadda等人的研究表明[2],在節(jié)點(diǎn)數(shù)量均勻部署中,由于距離Sink節(jié)點(diǎn)位置越近的節(jié)點(diǎn)能量消耗越快,當(dāng)Sink節(jié)點(diǎn)一跳范圍內(nèi)的節(jié)點(diǎn)因能量耗盡而死亡時(shí),整個(gè)網(wǎng)絡(luò)的傳感器節(jié)點(diǎn)仍然存在高達(dá)93%的能量沒有使用。Perillo等人分析了均勻部署中能量消耗的兩種情況[4],在第一種情況中,節(jié)點(diǎn)通過多跳的方式將感知到的信息發(fā)送給Sink節(jié)點(diǎn),使得中間節(jié)點(diǎn)需要發(fā)送自身信息的同時(shí)還需要轉(zhuǎn)發(fā)其他節(jié)點(diǎn)的感知信息,導(dǎo)致距離基站越近的節(jié)點(diǎn)負(fù)載越大,生存時(shí)間越短。在第二種情況中,網(wǎng)絡(luò)中的節(jié)點(diǎn)都需要將自身感知到的數(shù)據(jù)直接傳輸給Sink節(jié)點(diǎn),導(dǎo)致距離基站越遠(yuǎn)的節(jié)點(diǎn)的能量消耗越快。同時(shí)提出了一種節(jié)點(diǎn)通信半徑可變機(jī)制,但是在實(shí)際應(yīng)用中,節(jié)點(diǎn)的通信半徑是是由硬件及環(huán)境條件決定的。Luo J等人提出一種采用移動(dòng)Sink節(jié)點(diǎn)和數(shù)據(jù)路由結(jié)合的方法[5]來均衡網(wǎng)絡(luò)的能量消耗,避免了網(wǎng)絡(luò)中能耗的不均衡,但是該方法會(huì)導(dǎo)致費(fèi)用的大量增加,并且移動(dòng)Sink節(jié)點(diǎn)無法在井下環(huán)境中得到應(yīng)用。

針對以上問題,本文提出了一種基于能量均衡的節(jié)點(diǎn)部署算法。該算法根據(jù)實(shí)際情況將煤礦井下的巷道劃分成覆蓋面積大小相等的若干個(gè)簇,通過計(jì)算每個(gè)簇的能量消耗來確定簇內(nèi)節(jié)點(diǎn)的部署數(shù)量,同時(shí)利用分簇算法計(jì)算每個(gè)簇內(nèi)的能量消耗情況,盡可能實(shí)現(xiàn)各個(gè)簇的能量同時(shí)耗盡,達(dá)到延長網(wǎng)絡(luò)的生存周期的目的。

1 覆蓋模型

傳感器節(jié)點(diǎn)覆蓋模型采用最基礎(chǔ)的二元感知模型[6],該模型下節(jié)點(diǎn)的感知區(qū)域是一個(gè)以節(jié)點(diǎn)位置為圓心,半徑為Rs的圓,Rs為節(jié)點(diǎn)感知半徑。對于發(fā)生在感知圓范圍內(nèi)的事件的感知概率為1;發(fā)生在感知圓范圍外的事件的感知概率為0,即

(1)

式中:P(i,s)代表節(jié)點(diǎn)i對目標(biāo)s的監(jiān)測概率,d(i,s)代表目標(biāo)s發(fā)生地到節(jié)點(diǎn)i的歐氏距離。

2 分簇算法

針對LEACH算法經(jīng)過多輪選舉后節(jié)點(diǎn)剩余能量存在較大差異的問題,出現(xiàn)了LEACH-B、LEACH-C等改進(jìn)的算法[8-9],本文根據(jù)節(jié)點(diǎn)剩余能量的多少來選取簇頭,節(jié)點(diǎn)剩余的能量越多,當(dāng)選簇頭的機(jī)率越大;反之,當(dāng)選簇頭的機(jī)率越小[10-11]。節(jié)點(diǎn)在t時(shí)刻成為簇頭的概率P(t)的計(jì)算公式為:

(2)

式中:c為簇頭個(gè)數(shù),Ei(t)是第i個(gè)節(jié)點(diǎn)的當(dāng)前剩余能量,Etotal(t)是所有傳感器節(jié)點(diǎn)的剩余能量之和,即

(3)

3 基于能量均衡的部署算法

在巷道節(jié)點(diǎn)均勻部署情況下,每個(gè)簇內(nèi)的節(jié)點(diǎn)除了要感知自身所在區(qū)域的數(shù)據(jù)信息外,還需要接收后一個(gè)簇轉(zhuǎn)發(fā)過來的數(shù)據(jù),并且將所有的數(shù)據(jù)發(fā)送給前一個(gè)簇。因此,離基站越近位置的簇內(nèi),網(wǎng)絡(luò)負(fù)載越大,能量消耗的就越快,容易出現(xiàn)能量空洞[12]。針對這一問題,本文設(shè)計(jì)了一種能量均衡的節(jié)點(diǎn)部署算法。該算法將煤礦井下巷道劃分成面積大小相等的若干子區(qū)域,即劃分成簇的形式,計(jì)算出每個(gè)簇中節(jié)點(diǎn)的能耗情況,依據(jù)各簇節(jié)點(diǎn)能耗比例確定各區(qū)域內(nèi)需部署的節(jié)點(diǎn)數(shù)量,使得所有簇的能量消耗按比例下降,最后所有子區(qū)域中的網(wǎng)絡(luò)能量同時(shí)耗盡,以此延長網(wǎng)絡(luò)的生存周期。

如圖1所示,將巷道等效為長帶區(qū)域,設(shè)離基站最近的簇S1為起點(diǎn),離基站最遠(yuǎn)的簇SM為終點(diǎn),從起點(diǎn)到終點(diǎn)編號(hào)依次是S1,S2,…,SM。

圖1 巷道分區(qū)模型圖

網(wǎng)絡(luò)中節(jié)點(diǎn)能量消耗分為三個(gè)部分,感知信息消耗Psense、發(fā)送信息消耗PTx、接收信息消耗PRx,基本計(jì)算公式如下:

Psense=EDAy

(4)

(5)

PRX=ERXy

(6)

設(shè)Ni,Ei,Ai,M分別表示簇內(nèi)節(jié)點(diǎn)個(gè)數(shù)、單位時(shí)間內(nèi)的能量消耗、面積以及簇的個(gè)數(shù),c表示單位面積內(nèi)產(chǎn)生的數(shù)據(jù)流量。每個(gè)簇分別由感知數(shù)據(jù)能量消耗、接收數(shù)據(jù)能量消耗和發(fā)送數(shù)據(jù)的能量消耗三部分構(gòu)成,最后一個(gè)簇SM不需要接收數(shù)據(jù),所以它消耗的能量為:

(7)

其他子區(qū)域中所消耗的能量為:

(8)

綜合上面兩個(gè)公式可以得到任意一個(gè)簇所消耗的能量為:

(9)

由于每個(gè)簇內(nèi)放置的節(jié)點(diǎn)數(shù)目都不相同,依照每個(gè)簇內(nèi)節(jié)點(diǎn)總消耗能量可確定各簇內(nèi)節(jié)點(diǎn)的部署數(shù)量,因此,每個(gè)簇的網(wǎng)絡(luò)生存時(shí)間應(yīng)滿足關(guān)系式:

(10)

(11)

式中:α是一個(gè)比例系數(shù)

(12)

由于所有簇的面積大小都相等,即Ai=A,有

(13)

4 簇內(nèi)節(jié)點(diǎn)部署

根據(jù)上節(jié)中的方法可計(jì)算出每個(gè)簇內(nèi)需部署的節(jié)點(diǎn)數(shù)量,節(jié)點(diǎn)的具體部署形式采用如圖2所示的方法。

圖2 節(jié)點(diǎn)部署模型圖

圖2中黑色實(shí)線為井下巷道邊界,節(jié)點(diǎn)依次部署在巷道兩側(cè),同時(shí)在巷道盡頭處放置一個(gè)節(jié)點(diǎn)。其中,巷道兩側(cè)節(jié)點(diǎn)分別選用不同的通信頻率(或不同的傳輸信道),可與同側(cè)相鄰節(jié)點(diǎn)直接通信。巷道中間節(jié)點(diǎn)為雙頻節(jié)點(diǎn),可同時(shí)接收巷道兩側(cè)節(jié)點(diǎn)的信號(hào)。這種網(wǎng)絡(luò)部署結(jié)構(gòu)的優(yōu)勢一方面在于一旦某個(gè)節(jié)點(diǎn)失效,可以由巷道另一側(cè)的節(jié)點(diǎn)繼續(xù)通信,進(jìn)而增強(qiáng)了網(wǎng)絡(luò)的健壯性;另一方面由于巷道兩側(cè)節(jié)點(diǎn)采用了不同的通信頻率,這樣可以同時(shí)傳輸數(shù)據(jù),提高了數(shù)據(jù)傳輸效率。

針對相鄰兩個(gè)節(jié)點(diǎn)間的位置部署可分為以下三種情況(圖3中黑粗線輪廓為節(jié)點(diǎn)N1與N2對巷道的覆蓋范圍):

圖3 相鄰兩個(gè)節(jié)點(diǎn)間的位置部署

圖3(a)中,節(jié)點(diǎn)N1與N2的部署結(jié)構(gòu)對巷道的覆蓋存在盲區(qū)(陰影部分),針對井下環(huán)境,通常需要達(dá)到盡可能精確的監(jiān)測,因此這種情況的部署結(jié)構(gòu)不適合實(shí)際應(yīng)用。

圖3(b)中,節(jié)點(diǎn)的部署結(jié)構(gòu)可以對巷道實(shí)現(xiàn)無縫覆蓋。節(jié)點(diǎn)N1與N2的覆蓋圓相交于一點(diǎn)p,且點(diǎn)p位于巷道邊緣上,設(shè)巷道寬度為d,此時(shí)兩節(jié)點(diǎn)對巷道的覆蓋面積S包括3個(gè)部分:中間梯形面積S1和兩端扇形面積S2與S3。即

(14)

(15)

α=arcsin(d/RS)

(16)

S2=S3

(17)

S=S1+S2+S3=3d×L+2S2

(18)

圖3(c)中,節(jié)點(diǎn)的部署結(jié)構(gòu)同樣可以對巷道實(shí)現(xiàn)無縫覆蓋。節(jié)點(diǎn)N1與N2的覆蓋圓相交點(diǎn)位于巷道邊緣外,相比圖3(b),扇形面積S2與S3不變,但由于節(jié)點(diǎn)N1與N2的重疊面積增加導(dǎo)致梯形上底與下底長度縮小,梯形面積S1相應(yīng)減小,因此總面積S小于圖3(b)。

綜合以上三種節(jié)點(diǎn)部署情況的分析,圖3(b)中的部署結(jié)構(gòu)最佳,在確保對巷道進(jìn)行無縫覆蓋的同時(shí),節(jié)點(diǎn)對巷道的有效覆蓋面積最大,覆蓋效率最高。

由第2節(jié)中每個(gè)簇的能耗和節(jié)點(diǎn)數(shù)量比例關(guān)系可知,每個(gè)簇內(nèi)的節(jié)點(diǎn)部署數(shù)量都不一樣,而對于面積相等的各簇,按照圖3(b)中固定的節(jié)點(diǎn)部署結(jié)構(gòu),每個(gè)簇內(nèi)所需要部署的實(shí)際節(jié)點(diǎn)數(shù)量都相等。因此,針對這一問題,本文采用多個(gè)節(jié)點(diǎn)覆蓋集的部署方式,即在最后一層子區(qū)域內(nèi)巷道兩側(cè)部署的節(jié)點(diǎn)數(shù)量取圖3(b)所示部署方式下一重覆蓋所需的節(jié)點(diǎn)數(shù),內(nèi)層各簇依次按比例計(jì)算各自所需部署的節(jié)點(diǎn)數(shù)量,與最后一個(gè)簇的比值即為該層子區(qū)域的覆蓋集數(shù)。同一時(shí)間,只允許其中一個(gè)覆蓋集處于工作狀態(tài),其他覆蓋集休眠,當(dāng)前覆蓋集節(jié)點(diǎn)能量全部消耗完畢時(shí)再喚醒下一個(gè)覆蓋集工作,直至最后一個(gè)覆蓋集工作停止。

圖4 多覆蓋集節(jié)點(diǎn)部署模型圖

對于多個(gè)覆蓋集的節(jié)點(diǎn)部署問題,本文采用錯(cuò)位部署方法,每個(gè)覆蓋集中對應(yīng)位置上的節(jié)點(diǎn)在實(shí)際部署中要錯(cuò)位部放,如圖4所示,以三重部署為例,在某一個(gè)巷道子區(qū)域內(nèi),編號(hào)為1的節(jié)點(diǎn)表示第一重覆蓋集,編號(hào)為2的節(jié)點(diǎn)表示第二重覆蓋集,編號(hào)為3的節(jié)點(diǎn)表示第三重覆蓋集。

5 算法實(shí)現(xiàn)

5.1 算法設(shè)計(jì)

根據(jù)井下巷道相關(guān)物理特性,將其等效成一個(gè)二維的長帶區(qū)域,設(shè)定巷道長度L和寬度W。本文算法具體步驟如下:①結(jié)合巷道長度L及節(jié)點(diǎn)感知半徑Rs對巷道進(jìn)行均勻分區(qū),每個(gè)子巷道都同構(gòu);②根據(jù)能量均衡推導(dǎo)公式計(jì)算各簇所需部署的節(jié)點(diǎn)數(shù)量比值;③計(jì)算在圖3(b)節(jié)點(diǎn)部署模型下一個(gè)簇內(nèi)所需部署的節(jié)點(diǎn)數(shù),并將此數(shù)量作為最外層簇節(jié)點(diǎn)部署的實(shí)際數(shù)量;④將第③步求得的節(jié)點(diǎn)數(shù)作為一個(gè)數(shù)量單位,按照第②步的比值計(jì)算其他簇內(nèi)對應(yīng)的節(jié)點(diǎn)實(shí)際數(shù)量;⑤在每個(gè)簇內(nèi)將固定數(shù)量的節(jié)點(diǎn)按照圖3(b)所示結(jié)構(gòu)進(jìn)行單個(gè)覆蓋集部放,多個(gè)覆蓋集的子區(qū)域內(nèi)各覆蓋集中的節(jié)點(diǎn)實(shí)際位置按照圖4所示形式進(jìn)行部放。⑥根據(jù)式(2)、式(3)選取簇頭,簇成員節(jié)點(diǎn)將感知到的信息發(fā)送給簇頭節(jié)點(diǎn),簇頭節(jié)點(diǎn)將接收到的數(shù)據(jù)信息傳輸給下一個(gè)簇頭,依次傳遞數(shù)據(jù)直到基站。

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

本文算法以CC2530節(jié)點(diǎn)的基本參數(shù)為標(biāo)準(zhǔn),使用MATLAB對混合算法進(jìn)行仿真。在仿真實(shí)驗(yàn)中,設(shè)節(jié)點(diǎn)的初始能量為E0,數(shù)據(jù)包長度為ld,控制包長度為lc。各參數(shù)設(shè)置如表1所示。

表1 算法參數(shù)設(shè)置

圖5 非均勻部署算法覆蓋率變化趨勢圖

圖5為采用均勻部署的分簇算法與本文基于能量均衡的分區(qū)部署分簇算法性能對比圖,分析了兩種算法覆蓋率隨著工作輪數(shù)的變化情況。

由圖5可以看出,均勻部署分簇算法的覆蓋率保持為100%的時(shí)間較短,而本文基于能量均衡的分區(qū)部署分簇算法的覆蓋率持續(xù)為100%的時(shí)較長,說明了本文算法對于網(wǎng)絡(luò)覆蓋具有較好的穩(wěn)定性,可增強(qiáng)網(wǎng)絡(luò)的覆蓋性能。其次,本文算法的覆蓋率比均勻部署分簇算法的覆蓋率的衰減幅度要大,由于本文算法根據(jù)各個(gè)簇的節(jié)點(diǎn)總體能量消耗比值來進(jìn)行節(jié)點(diǎn)部署,使得負(fù)載越大的簇的節(jié)點(diǎn)數(shù)量越多,總體的能量越多,從而均衡了網(wǎng)絡(luò)負(fù)載能耗、延長了網(wǎng)絡(luò)的生存周期。

圖6為均勻部署的分簇算法與本文基于能量均衡的分區(qū)部署分簇算法在網(wǎng)絡(luò)節(jié)點(diǎn)能量均值方面的性能比較。由圖6可以看出,隨著網(wǎng)絡(luò)工作輪數(shù)的增加,兩種算法的能量均值都在下降,但本文算法的下降幅度相對較小,說明了本文算法在每輪工作中所需能耗較低,有效節(jié)約了網(wǎng)絡(luò)能量,進(jìn)而起到延長網(wǎng)絡(luò)生存。

圖6 非均勻部署算法覆蓋率變化趨勢圖

6 結(jié)束語

本文提出了一種基于能量均衡的節(jié)點(diǎn)部署算法,該算法將煤礦井下巷道劃分成覆蓋面積大小相等的若干個(gè)簇,依照每個(gè)簇內(nèi)節(jié)點(diǎn)總體消耗的能量決定簇內(nèi)節(jié)點(diǎn)的部放數(shù)量,即各個(gè)簇的節(jié)點(diǎn)數(shù)量和簇內(nèi)節(jié)點(diǎn)總體的能量消耗成正比,之后依據(jù)節(jié)點(diǎn)覆蓋效率最大化原則在巷道兩側(cè)部署節(jié)點(diǎn),在多個(gè)覆蓋集的簇中采用錯(cuò)位多層覆蓋的方法。實(shí)驗(yàn)結(jié)果表明,該算法可有效的延長網(wǎng)絡(luò)的生存周期,具有較強(qiáng)的理論和應(yīng)用價(jià)值。