基于蛙跳算法的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)重部署

徐逸夫，段隆振

(南昌大學(xué)信息工程學(xué)院，江西 南昌 330031)

1 引言

無(wú)線傳感網(wǎng)絡(luò)技術(shù)是一項(xiàng)分布式的傳感網(wǎng)絡(luò)技術(shù)，能夠感知并檢查外部世界傳感器，主要通過(guò)無(wú)線的方式實(shí)現(xiàn)通信，其網(wǎng)絡(luò)設(shè)置非常靈活，并且能夠任意更改，同時(shí)還可以通過(guò)有線或者無(wú)線的方式與互聯(lián)網(wǎng)連接[1]。無(wú)線連接是一種多跳性的組織網(wǎng)絡(luò)模式，將數(shù)以萬(wàn)計(jì)的傳感節(jié)點(diǎn)自由結(jié)合，構(gòu)成一種網(wǎng)絡(luò)形式。該項(xiàng)技術(shù)的特點(diǎn)在于規(guī)模大、自組織強(qiáng)，且是動(dòng)態(tài)化的形式，因此能夠應(yīng)用在各行各業(yè)，例如軍事領(lǐng)域、醫(yī)療領(lǐng)域、環(huán)境監(jiān)測(cè)領(lǐng)域等。但傳統(tǒng)無(wú)線傳感網(wǎng)絡(luò)節(jié)點(diǎn)部署方法，存在覆蓋率較低，且移動(dòng)步長(zhǎng)較長(zhǎng)，不穩(wěn)定等問(wèn)題[2]。

文獻(xiàn)[3]提出無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位與漂移檢測(cè)方法，基于測(cè)距的MDS和非測(cè)距的MDS方法，整合完成節(jié)點(diǎn)定位，比較相對(duì)坐標(biāo)矩陣的差異完成漂移節(jié)點(diǎn)檢測(cè)，通過(guò)提升定位精度較高的普通節(jié)點(diǎn)為臨時(shí)信標(biāo)的方式，解決節(jié)點(diǎn)重定位過(guò)程中可用信標(biāo)不足的問(wèn)題，將節(jié)點(diǎn)定位、漂移節(jié)點(diǎn)檢測(cè)和節(jié)點(diǎn)重定位過(guò)程無(wú)縫結(jié)合，實(shí)現(xiàn)網(wǎng)絡(luò)節(jié)點(diǎn)的重部署。該方法具備有效性和實(shí)用性，但是穩(wěn)定性能較差；文獻(xiàn)[4]提出基于SR-CKF的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位研究方法，利用極大似然估計(jì)法初步定位未知節(jié)點(diǎn)，引入平方根容積卡爾曼濾波算法，實(shí)現(xiàn)對(duì)未知節(jié)點(diǎn)的精確定位，采用閾值選擇的更新策略來(lái)，減小非線性因素的影響。該方法精度和穩(wěn)定性較高，但處理后的網(wǎng)絡(luò)節(jié)點(diǎn)覆蓋范圍依舊較小，不能大規(guī)模的使用。

上述所提方法雖然具有一定有效性，但在實(shí)際應(yīng)用時(shí)，仍不能較好地實(shí)現(xiàn)對(duì)無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的重部署。本次研究提出基于蛙跳算法的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)重部署方法，模擬青蛙群覓食的方式，將網(wǎng)絡(luò)節(jié)點(diǎn)子群分類，完成各信息傳遞的流程，將全局信息交換與子群局部搜索結(jié)合，將全部子群內(nèi)的青蛙混合，重新劃分子群，采集網(wǎng)絡(luò)覆蓋區(qū)域中的某個(gè)地點(diǎn)，利用最近節(jié)點(diǎn)采集相關(guān)數(shù)據(jù)信息，減少重復(fù)性采集情況出現(xiàn)，計(jì)算無(wú)線網(wǎng)絡(luò)節(jié)點(diǎn)的部署，在網(wǎng)絡(luò)區(qū)域范圍內(nèi)，劃分成面積大小相等的小區(qū)域，其中節(jié)點(diǎn)能夠覆蓋的區(qū)域，即是被監(jiān)測(cè)的區(qū)域，需要特殊監(jiān)測(cè)，以此完成無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)重部署[5]。

2 無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)初始化

傳感器網(wǎng)絡(luò)的基本構(gòu)造及功能包含傳感單元(組成有傳感器以及模數(shù)轉(zhuǎn)換功能模塊)、處理單元(是嵌入式系統(tǒng)：主要有嵌入式操作系統(tǒng)、CPU以及存儲(chǔ)器等)、通信單元(組成有無(wú)線通信模塊)以及電源部分。其它能夠選擇的功能有發(fā)電設(shè)備、運(yùn)動(dòng)系統(tǒng)和定位系統(tǒng)等[6]。

假設(shè)網(wǎng)絡(luò)的探測(cè)范圍是長(zhǎng)度為m，寬度為n的一個(gè)區(qū)域范圍，即探測(cè)區(qū)域范圍是m×n。設(shè)定無(wú)線傳感網(wǎng)絡(luò)節(jié)點(diǎn)都是相同的，其部署無(wú)法移動(dòng)，不能補(bǔ)償新的節(jié)點(diǎn)。并假設(shè)一個(gè)傳感節(jié)點(diǎn)在一個(gè)周期中固定處理kbit數(shù)據(jù)，具體感知是“R”，能夠感受到的范圍面積為2πR2，兩個(gè)傳感節(jié)點(diǎn)的通信距離d設(shè)置成2R[7]。

在采集網(wǎng)絡(luò)覆蓋區(qū)域中的某個(gè)地點(diǎn)時(shí)，其最近節(jié)點(diǎn)會(huì)收集其相關(guān)數(shù)據(jù)信息，減少重復(fù)性采集情況出現(xiàn)，假設(shè)網(wǎng)絡(luò)內(nèi)的路由數(shù)據(jù)信息是初始化階段，即不在變化。需要把N個(gè)傳感點(diǎn)任意部署在該網(wǎng)絡(luò)區(qū)域范圍，具體如圖1所示，其中基站(指匯聚節(jié)點(diǎn))是均勻的分布在此區(qū)域中。

圖1 隨機(jī)無(wú)線傳感網(wǎng)絡(luò)部署圖

傳感器網(wǎng)絡(luò)節(jié)點(diǎn)是一個(gè)微型化的嵌入式系統(tǒng)，主要通過(guò)部署無(wú)線傳感網(wǎng)絡(luò)，實(shí)現(xiàn)無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的初始化[8]。

3 無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)重部署

3.1 基于蛙跳算法求解節(jié)點(diǎn)最優(yōu)解

傳感器節(jié)點(diǎn)部署能夠分成隨機(jī)和確定性兩類，其主要的部署策略取決于傳感器種類、實(shí)際背景和環(huán)境情況[9]。其主要問(wèn)題分類如圖2所示。

圖2 網(wǎng)絡(luò)節(jié)點(diǎn)部署問(wèn)題分類

在網(wǎng)絡(luò)目標(biāo)設(shè)置范圍內(nèi)重部署，利用C=(C1，C2，…，Cn)代表初始化傳感節(jié)點(diǎn)集，Ci=(xi，yi，R)代表每個(gè)節(jié)點(diǎn)的坐標(biāo)。其中：4xi，yi兩者分別代表中心節(jié)點(diǎn)在二維區(qū)域中的坐標(biāo)對(duì)象，0

具體的傳感節(jié)點(diǎn)與目標(biāo)像素點(diǎn)距離公式為。

(1)

網(wǎng)絡(luò)節(jié)點(diǎn)的感知半徑是R。p(n)代表像素點(diǎn)(u，v)能否被傳感節(jié)點(diǎn)Cn覆蓋，如果p(n)=1，代表節(jié)點(diǎn)i是對(duì)像素點(diǎn)的感知度為1，p(n)=0代表節(jié)點(diǎn)i是對(duì)像素點(diǎn)的感知度為0，具體表達(dá)式為

(2)

dn表示像素點(diǎn)感知半徑；rs表示節(jié)點(diǎn)感知半徑。設(shè)定目標(biāo)探測(cè)的區(qū)域范圍，是被劃分成面積大小相等、面積是為u×v的小區(qū)域，能夠?qū)崿F(xiàn)對(duì)所有子群的局部搜索。如果此區(qū)域被解集C內(nèi)的一個(gè)節(jié)點(diǎn)所監(jiān)測(cè)到，則說(shuō)明青蛙的適用度最好，并將其標(biāo)記成Xw；如果監(jiān)測(cè)不到，則說(shuō)明青蛙的適用度最差，將其標(biāo)記成Xb。重復(fù)性更新子群內(nèi)的Xw和Xb，其具體的更新公式為

D=P×R×(Xb-Xw)

(3)

X′=Xg+D(Dmin≤D≤Dmax)

(4)

式中：D代表移動(dòng)距離，R代表0與1兩者之間的隨機(jī)數(shù)值，Dmin與Dmax代表青蛙能夠允許更改位置的最大值以及最小值[11]。

結(jié)束更新后，若獲得X′優(yōu)于Xw的結(jié)果，那么則需要使Xw=X′。反之，則要利用Xg替代Xb來(lái)重復(fù)性的執(zhí)行更新式(3)、式(4)。若X′仍然不能夠優(yōu)于Xw，則任意生產(chǎn)另一個(gè)新的青蛙代替Xw。再次重復(fù)性的更新操作，最終到達(dá)所設(shè)定的最大子群局部搜索次數(shù)。

全部的子群完成局部搜索后，將全部子群內(nèi)的青蛙混合，重新劃分子群(全局的信息互換)，再重新對(duì)所有子群采用局部搜索(將子群內(nèi)Xw通過(guò)式(3)、式(4)完成重復(fù)性的更新)，直到搜索到最優(yōu)解或者是最大全局的信息交換次數(shù)，完成網(wǎng)絡(luò)節(jié)點(diǎn)最優(yōu)解的求解，以實(shí)現(xiàn)節(jié)點(diǎn)重部署。

3.2 節(jié)點(diǎn)的重部署

覆蓋程度是衡量傳感網(wǎng)絡(luò)節(jié)點(diǎn)部署的一個(gè)重要參數(shù)，即全部節(jié)點(diǎn)所覆蓋的面積并集和目標(biāo)區(qū)域總比值，因此節(jié)點(diǎn)重部署首先要計(jì)算最優(yōu)解節(jié)點(diǎn)的覆蓋率，通過(guò)覆蓋率搜索到覆蓋區(qū)域，實(shí)現(xiàn)節(jié)點(diǎn)重新部署[12]。具體無(wú)線傳感網(wǎng)絡(luò)覆蓋率能夠利用下列公式表示

(5)

pi表示無(wú)線傳感網(wǎng)絡(luò)所能夠覆蓋的總面積，基于在網(wǎng)絡(luò)模型探測(cè)范圍規(guī)則區(qū)內(nèi)，假設(shè)沒有遮擋物，全部區(qū)域都在監(jiān)控內(nèi)，具體公式表達(dá)式為

(6)

若在探測(cè)的區(qū)域范圍內(nèi)，要重點(diǎn)監(jiān)控某個(gè)區(qū)域Sarea，則此時(shí)的Sarea計(jì)算方法需要通過(guò)不同權(quán)值進(jìn)行計(jì)算。如果只有一個(gè)區(qū)域要特殊監(jiān)控，那么該節(jié)點(diǎn)覆蓋面積Sall需要通過(guò)公式表示

Sall=Sarea+(weight-1)×S1

(7)

式中：S1代表重點(diǎn)監(jiān)控區(qū)域的面積，weight代表權(quán)重，能夠根據(jù)不同特殊區(qū)域進(jìn)行改變。依據(jù)網(wǎng)絡(luò)探測(cè)范圍是否規(guī)則區(qū)域面積能夠分成兩種，一種是在規(guī)則區(qū)域的總面積，能夠采用公式S0=m×n進(jìn)行計(jì)算，另一種是不規(guī)則的區(qū)域，需要利用微積分方法，將其分解成不同的若干幾何圖形，求解出幾何圖形的面積之和，即可以獲得最終結(jié)果。無(wú)線傳感網(wǎng)絡(luò)節(jié)點(diǎn)的重部署，主要目地是在于擴(kuò)大網(wǎng)絡(luò)的覆蓋率，具體覆蓋率是節(jié)點(diǎn)集C已覆蓋面積和其探測(cè)范圍面積S0總比值，利用公式進(jìn)行表示為

η=Sarea/S0

(8)

其函數(shù)定義的適應(yīng)值公式為

fitnessfun(x，y)=max(η)

(9)

式中：fitnessfun(x，y)取最大值時(shí)，能夠獲取全部的最優(yōu)解節(jié)點(diǎn)坐標(biāo)信息，即無(wú)線傳感網(wǎng)絡(luò)內(nèi)的節(jié)點(diǎn)最佳位置，完成對(duì)無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的重部署。

4 仿真研究

為了驗(yàn)證基于蛙跳算法的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)重部署方法的整體有效性，需要進(jìn)行仿真對(duì)比實(shí)驗(yàn)，采用C語(yǔ)言進(jìn)行編程，獲得仿真數(shù)據(jù)利用Matlab完成繪圖。其PC機(jī)的主頻是2.83GHz。設(shè)置一個(gè)200m×200m檢測(cè)區(qū)域，原始隨意部署56個(gè)節(jié)點(diǎn)。具體的實(shí)驗(yàn)蛙群參數(shù)為p=400，慣性權(quán)重w=1.6，而兩加速因子為c1=c2=2.0。以基于蛙跳算法的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)重部署方法為實(shí)驗(yàn)組，以文獻(xiàn)[3]方法和文獻(xiàn)[4]方法為對(duì)照組，其中傳統(tǒng)方法的混合迭代次數(shù)參數(shù)為wA=1，節(jié)點(diǎn)最大移動(dòng)距離為1m，網(wǎng)絡(luò)節(jié)點(diǎn)覆蓋半徑為r=12，研究方法的參數(shù)節(jié)點(diǎn)覆蓋半徑為r=12，相對(duì)誤差半徑為re=3，通信半徑為R=24。無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)圖如圖3所示。

圖3 無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)圖

4.1 覆蓋率對(duì)比實(shí)驗(yàn)

覆蓋率是區(qū)域內(nèi)全部節(jié)點(diǎn)覆蓋范圍并集和全部單個(gè)節(jié)點(diǎn)能夠覆蓋范圍對(duì)比值，可以衡量節(jié)點(diǎn)的覆蓋范圍，主要反映網(wǎng)絡(luò)覆蓋區(qū)域所消耗能量，以及節(jié)點(diǎn)的冗余程度。覆蓋率越高，網(wǎng)絡(luò)節(jié)點(diǎn)的冗余程度就越小，相反網(wǎng)絡(luò)節(jié)點(diǎn)的冗余就越大。圖4為研究方法與文獻(xiàn)[3]、文獻(xiàn)[4]方法的覆蓋率對(duì)比圖，所能夠覆蓋的區(qū)域隨迭代次數(shù)的變化情況如圖4所示。

圖4 不同方法的覆蓋率對(duì)比圖

通過(guò)圖4可知，文獻(xiàn)[3]方法覆蓋率在76%-90%之間，文獻(xiàn)[4]方法覆蓋率在55%-73%之間，而研究方法的最大覆蓋率在84%-97%之間，始終高于傳統(tǒng)方法的覆蓋率，覆蓋率越高表示方法的冗余程度越小，獲得的適應(yīng)值越大，可以證明研究方法能夠有效提高覆蓋率，對(duì)于網(wǎng)絡(luò)節(jié)點(diǎn)的重部署效果更好。

4.2 網(wǎng)絡(luò)節(jié)點(diǎn)連通性對(duì)比實(shí)驗(yàn)

網(wǎng)絡(luò)節(jié)點(diǎn)是通過(guò)自組織的模式來(lái)完成中心指令的，需要以無(wú)線多跳的方式進(jìn)行互相通信，完成協(xié)助工作，連通性主要能夠確保自身的無(wú)線多跳組織通信開展，確定無(wú)線傳感網(wǎng)絡(luò)的監(jiān)視、通信、傳感等質(zhì)量。節(jié)點(diǎn)連通性越好，方法的重部署有效性越高。不同方法的節(jié)點(diǎn)連通性對(duì)比圖如圖5所示。

圖5 不同方法的節(jié)點(diǎn)連通性對(duì)比圖

對(duì)比圖5可知，文獻(xiàn)[3]方法和文獻(xiàn)[4]方法的節(jié)點(diǎn)連通效果較差，存在連接混亂現(xiàn)象，并且難以保證所有節(jié)點(diǎn)的互相連接，而研究方法的所有節(jié)點(diǎn)都能規(guī)律的連接，可以保證信息的準(zhǔn)確傳輸，更好地實(shí)現(xiàn)網(wǎng)絡(luò)節(jié)點(diǎn)的重部署。

4.3 能量有效性對(duì)比實(shí)驗(yàn)

在實(shí)際使用時(shí)，環(huán)境條件較為復(fù)雜，難以更換失效電池，因此保證節(jié)點(diǎn)能量有效性是實(shí)現(xiàn)重部署的重要指標(biāo)。節(jié)點(diǎn)能量越高表示的能量有效性越好，實(shí)驗(yàn)對(duì)比圖如圖6所示。

圖6 不同方法的能量有效性對(duì)比圖

通過(guò)圖6可知，文獻(xiàn)[4]方法的節(jié)點(diǎn)能量值較低，始終在13-29J范圍內(nèi)，文獻(xiàn)[3]方法的節(jié)點(diǎn)能量值在7-32J范圍內(nèi)，波動(dòng)性較大，而研究方法的節(jié)點(diǎn)能量值最高，且均在30-34J范圍內(nèi)，表明該方法的網(wǎng)絡(luò)節(jié)點(diǎn)能量有效性更好，重部署效果更理想。綜上可以證明，研究方法的全部節(jié)點(diǎn)連通性較好，致使節(jié)點(diǎn)的移動(dòng)有效距離很小，能夠降低消耗的能量，保證節(jié)點(diǎn)能量。同時(shí)研究方法的覆蓋率較好，能夠更好地實(shí)現(xiàn)無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的重部署。

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

網(wǎng)絡(luò)的快速發(fā)展，使得無(wú)線網(wǎng)絡(luò)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)部署也獲得了大力發(fā)展，但傳統(tǒng)方法覆蓋面較小，不能大規(guī)模使用，提出一種基于蛙跳算法的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)重部署方法，通過(guò)對(duì)蛙跳算法對(duì)全部子群進(jìn)行局部搜索獲得最優(yōu)解，探測(cè)到節(jié)點(diǎn)所覆蓋的位置，將目標(biāo)設(shè)定的區(qū)域分成許多面積相同的小區(qū)域，以此完成無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)重部署。實(shí)驗(yàn)結(jié)果表明，研究方法相比于傳統(tǒng)方法，覆蓋率更高，節(jié)點(diǎn)連通性更好，節(jié)點(diǎn)能量更高，具有更好的魯棒性。本次研究為無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)重部署方案的設(shè)計(jì)提供了新思路，促進(jìn)了無(wú)線傳感器網(wǎng)絡(luò)領(lǐng)域研究成果的深入挖掘，為相關(guān)專家與學(xué)者對(duì)該領(lǐng)域的研究提供參考性意見。雖然本次研究取得了較為理想的成果，但是未進(jìn)行實(shí)踐驗(yàn)證，下一步可將該問(wèn)題作為重點(diǎn)進(jìn)行深入談?wù)?，以提升無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)重部署方法的實(shí)用性。