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

徐逸夫，段隆振

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

1 引言

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

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

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

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

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

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

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

圖1 隨機無線傳感網(wǎng)絡部署圖

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

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

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

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

圖2 網(wǎng)絡節(jié)點部署問題分類

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

具體的傳感節(jié)點與目標像素點距離公式為。

(1)

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

(2)

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

D=P×R×(Xb-Xw)

(3)

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

(4)

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

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

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

3.2 節(jié)點的重部署

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

(5)

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

(6)

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

Sall=Sarea+(weight-1)×S1

(7)

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

η=Sarea/S0

(8)

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

fitnessfun(x，y)=max(η)

(9)

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

4 仿真研究

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

圖3 無線傳感器網(wǎng)絡節(jié)點圖

4.1 覆蓋率對比實驗

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

圖4 不同方法的覆蓋率對比圖

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

4.2 網(wǎng)絡節(jié)點連通性對比實驗

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

圖5 不同方法的節(jié)點連通性對比圖

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

4.3 能量有效性對比實驗

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

圖6 不同方法的能量有效性對比圖

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

5 結束語

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