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

(內蒙古科技大學信息工程學院,內蒙古 包頭 014010)

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

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

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

1 覆蓋模型

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

(1)

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

2 分簇算法

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

(2)

式中:c為簇頭個數,Ei(t)是第i個節(jié)點的當前剩余能量,Etotal(t)是所有傳感器節(jié)點的剩余能量之和,即

(3)

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

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

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

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

網絡中節(jié)點能量消耗分為三個部分,感知信息消耗Psense、發(fā)送信息消耗PTx、接收信息消耗PRx,基本計算公式如下:

Psense=EDAy

(4)

(5)

PRX=ERXy

(6)

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

(7)

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

(8)

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

(9)

由于每個簇內放置的節(jié)點數目都不相同,依照每個簇內節(jié)點總消耗能量可確定各簇內節(jié)點的部署數量,因此,每個簇的網絡生存時間應滿足關系式:

(10)

(11)

式中:α是一個比例系數

(12)

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

(13)

4 簇內節(jié)點部署

根據上節(jié)中的方法可計算出每個簇內需部署的節(jié)點數量,節(jié)點的具體部署形式采用如圖2所示的方法。

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

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

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

圖3 相鄰兩個節(jié)點間的位置部署

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

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

(14)

(15)

α=arcsin(d/RS)

(16)

S2=S3

(17)

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

(18)

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

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

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

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

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

5 算法實現(xiàn)

5.1 算法設計

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

5.2 實驗結果分析

本文算法以CC2530節(jié)點的基本參數為標準,使用MATLAB對混合算法進行仿真。在仿真實驗中,設節(jié)點的初始能量為E0,數據包長度為ld,控制包長度為lc。各參數設置如表1所示。

表1 算法參數設置

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

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

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

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

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

6 結束語

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