基于雙移動錨節點的無線傳感器網絡定位算法

崔煥慶，趙君宜，羅漢江

(山東科技大學 計算機科學與工程學院，山東 青島 266590)

0 引 言

本文主要針對移動錨節點輔助定位算法進行研究。目前，已經有學者對相關算法進行了研究。SLMAT[1]，H-Curves[2]和M-Curves[3]均使用單個錨節點掃描部署區域。∑-SCAN[4]對Z-Curves和SCAN進行了改進，提高了定位精度。SSD[5]通過減少虛擬錨節點來節省能耗。GSCAN[6]、GTURN和PP-MMAN[7]均使用3個移動錨節點，并使虛擬錨節點成等邊三角形分布，提高了定位精度。其中，GSCAN的虛擬錨節點數量較多，而GTURN的路徑較長。文獻[8，9]設計路徑的目的均為減少共線錨節點的數量，提高定位精度。

目前，元啟發式優化算法已經非常普遍，并且也廣泛應用于無線傳感器網絡定位中的未知節點位置估計。MGDV-Hop[10]利用混合策略對螢火蟲群優化算法進行了改進，提高未知節點的定位精度。文獻[11]使用粒子群優化算法(particle swarm optimization，PSO)來估計未知節點的位置。文獻[12]采用鯨魚優化算法對接收信號強度與信號傳輸距離之間的關系公式進行優化，降低了測量誤差。文獻[13]提出了一種新的非視距的定位算法，并通過改進的粒子群優化算法估算目標的位置。文獻[14]使用改進的灰狼優化算法估計未知節點的坐標。文獻[15]將改進樽海鞘群算與DV-Hop結合，提高了定位精度。

本文的主要貢獻有：

(1)設計了一種雙移動錨節點協作的路徑規劃算法DASCAN(Dual-Anchor SCAN)，縮短了路徑長度并且使用較少的虛擬錨節點，降低了能耗。

(2)使用加權質心算法和鯨魚優化算法估算未知節點的坐標，提高了定位精度。

1 系統模型

在無線傳感器網絡中，已知自身位置的節點稱為錨節點，其它節點稱為未知節點，錨節點分為靜態錨節點和移動錨節，后者在移動過程中需定期廣播自身位置等信息。錨節點廣播的這些信息稱為虛擬錨節點。假設無線傳感器網絡由NU個部署在高H、寬L的矩形區域內的未知節點組成。第i個節點Ui的真實坐標為(xi，yi)，利用定位算法求得的估計坐標為 (i，i)。 兩個移動錨節點分別記為MA1、MA2，它們廣播的虛擬錨節點信息包含實時位置和發送信號強度兩個字段。

在RSSI測距中，無線信號在傳播過程中強度會隨著距離的增加而降低，并且會受到環境因素的影響。通常假設在理想的自由空間中，RSSI與發送器和接收器之間的距離的平方成反比。令Pr(d)表示在距離d處的接收功率，其值遵循弗里斯方程

Pr(d)=(λ4πd)2PtGtGr

(1)

其中，Pt是發射功率，Gt和Gr分別是發射和接收天線的天線增益，λ是發射器信號的波長(以米為單位)。

但實際上，一些因素(例如陰影和反射)可能會影響無線電信號的傳播以及接收功率，因素取決于環境并且是不可預測的。由于無法精確跟蹤陰影效果，因此通常將其建模為對數正態分布的隨機變量?？紤]到隨機性，信號強度根據冪定律隨距離而減小。一種用于無線電的模型如式(2)所示

Pr(d)=P0(d0)-η10log10(dd0)+Xσ

(2)

其中，P0(d0) 表示在某個參考距離d0處的接收功率，η表示路徑損耗指數，Xσ表示對數正態隨機變量，其方差為σ2。通過該模型，距離d的最大似然估計如式(3)所示

d^=d0(PrP0(d0))(-1/|η)

(3)

假設錨節點與未知節點的通信范圍是一個半徑為R的圓。實際應用中，傳感器節點的信號傳播容易受周圍環境的影響，通信范圍不是一個規則的圓，所以將通信信號不規則度(degree of irregularity，DOI)加入到無線通信傳播模型中。DOI表征了無線電射程受多徑、陰影等衰弱影響而導致的傳輸范圍的各向異性，數值越高表示傳輸范圍受環境影響越嚴重，其定義如式(4)所示

(4)

其中，Ki是第i個方向上的不規則度，Rand是在[0，1]內服從均勻分布的隨機數，N是正整數集合。

使用定位算法定位的未知節點個數占未知節點總數的比例稱為定位率LR，即

LR=NldNU

(5)

其中，Nld表示被定位節點的個數。平均定位誤差e為

e=1Nld∑Nldi=1(xi-i)2+(yi-i)2

(6)

2 本文算法

2.1 錨節點路徑規劃算法

為了更合理地部署虛擬錨節點，先將監視區域進行網格狀劃分。縱向上等間距劃分為n+1行，并從下向上依次編號為第0、1、2、……、n行，相鄰兩行之間的間距為h，即每個單元格的高為h。橫向上等間距劃分m+1列，從左向右依次編號為第0、1、2、……、m列，相鄰兩列之間的間距為d，即每個單元格的寬為d，網格劃分和虛擬錨節點部署結果如圖1所示。

圖1 部署區域劃分及虛擬錨節點位置

DASCAN要求奇數行和偶數行采用不同的部署方式。在圖1中，偶數行和奇數行的虛擬錨節點分別用A和B表示。 ΔAi，jAi，j+1Bi+1，j和ΔAi，jAi，j+1Bi-1，j是等邊三角形。因此，h=32d。 以左下角為坐標原點(0，0)，第i行的虛擬錨節點坐標為：

(1)i≤n且為偶數時，Ai，j=(j×d，i×h)， 其中j=0，1，2，…，m。

(2)i≤n且為奇數時，Bi，k=((k+12)×d，i×h)， 其中k=0，1，2，…，m-1。

如果僅用一個移動錨節點，則需要交替遍歷偶數行和奇數行，路徑較長。所以DASCAN采用兩個移動錨節點以分別遍歷偶數行和奇數行的虛擬錨節點。算法1給出了DASCAN算法。

算法1：路徑規劃算法

輸入：H、L、h、d。

輸出：MA1、MA2的移動路徑

(1) Put MA1and MA2inA0,0andB0,0

(2) SetList1←Φ,List2←Φ

(3)flag←1,i←0,j←1,k←0

(4)whilei

(5)ifflag=1

(6)List1←List1∪{Ai,0,Ai,1,…,Ai,m}

(7)List2←List2∪{Bi+1,0,Bi+1,1,…,Bi+1,m-1}

(8)flag←2

(9)elseifflag=2

(10)List1←List1∪{Ai,m,Ai,m-1,…,Ai,0}

(11)List2←List2∪{Bi+1,m-1,Bi+1,m-2,…,Bi+1,0}

(12)flag←1

(13)endif

(14)i←i+2

(15)endwhile

(16)ifn%2=0 &&flag=1

(17)List1←List1∪{An,0,An,1,…,An,m}

(18)elseifn%2=0 &&flag=2

(19)List1←List1∪{An,m,An,m-1,…,An,0}

(20)endif

算法1中，List1、List2分別用來儲存MA1、MA2遍歷的虛擬錨節點列表。第(1)～第(3)行初始化各變量，第(4)～第(15)行計算List1和List2，其中flag=1表示錨節點從左向右移動(第(5)～第(8)行)，flag=2表示錨節點從右向左移動(第(9)～第(13)行)。當n為偶數時，MA1需要額外遍歷最后一行，移動方向取決于此時flag的值(第(16)～第(20)行)。

算法1生成的4種移動路徑如圖2所示，其中“flag值”是指執行到第(16)行時flag的值。算法1執行結束后，MA1和MA2分別沿List1、List2遍歷整個部署區域，并在指定虛擬錨節點處廣播信息。

圖2 算法1產生的4種不同路徑

2.2 鯨魚優化算法

鯨魚智能優化算法是2016年由澳大利亞格里菲斯大學的Mirjalili等提出的一種新的群體智能優化算法，該算法具有實現簡單、參數少以及不易陷入局部最優等優點。

在鯨魚優化算法中，每個鯨魚被看作是一個可行解。鯨魚在狩獵時，會沿著“9”字形或者圓形路徑吐出氣泡包圍獵物，這種狩獵行為稱為bubble-net捕食策略。該算法包括環繞獵物、螺旋泡泡網獵食以及搜索獵物3個階段。

在狩獵階段，WOA假設當前算法的最優解為目標獵物，其它鯨魚個體會向著當前適應度值最佳的鯨魚的位置移動，該行為的數學模型如下所示

D=|C·X*(t)-X(t)|

(7)

X(t+1)=X*(t)-A·D

(8)

A=2a·r1-a

(9)

C=2·r2

(10)

其中，t為當前迭代次數；A和C是協同系數向量；X*表示當前最優的鯨魚的位置向量；X(t)表示鯨魚當前的位置向量；在整個迭代過程中，a由2線性降到0；r1和r2是[0，1]中的隨機向量。C為[0，2]內的隨機值構成的向量，此系數提供了隨機權重，以避免算法陷入局部最優。

鯨魚在獵食的過程中會進行兩種不同的行為來包圍獵物，分別是縮小包圍圈和沿螺旋狀路徑吐氣泡驅趕獵物，每只鯨魚選擇這兩種該行為的概率是相等的。數學模型如式(11)所示

(11)

其中，b為常數，l和p為均勻分布在[-1，1]中的隨機數。

隨著迭代的進行，a的值會從2線性減小到0，a的值的變化會引起A的變化，當 |A|<1時，鯨魚會向最優個體移動，當 |A|>1時，鯨魚會隨機移動。鯨魚隨機移動的數學模型如式(12)和式(13)所示

D=|C·Xrand(t)-X(t)|

(12)

X(t+1)=Xrand(t)-A·D

(13)

其中，Xrand是隨機選擇的鯨魚位置向量，通過此方式可以讓WOA進行全局搜索，避免陷入局部最優。

2.3 節點位置估算算法

在定位階段，使用加權質心和鯨魚優化算法估算未知節點坐標，具體步驟如下。

結合所設計的路徑，先使用加權質心算法來估算未知節點位置。假設移動錨節點在部署區域內產生的虛擬錨節點的數量為NV，未知節點Ui(i=1，…，Nu) 維護一個虛擬錨節點列表Li，如果Ui接收到虛擬錨節點Vj的信標信息，則將Vj的坐標 (xj，yj)、 信號強度RSSIi，j以及根據RSSI測距模型計算得到的估計距離dei，j添加至Li中。將所有的虛擬錨節點按RSSIi，j值排成遞減序，選擇虛擬錨節點V1、V2、V3的方法為：

(1)選擇Li中前兩個最大RSSIi，j對應的虛擬錨節點作為V1、V2，在Li中從前往后依次查找可與V1、V2構成邊長為d的等邊三角形的虛擬錨節點Vk(k>2)作為V3。

(2)如果利用步驟(1)不能找到滿足此條件的V3，則選擇剩余虛擬錨節點中最大RSSIi，j對應的虛擬錨節點作為V3。

未知節點Ui在選擇V1、V2、V3后，使用加權質心算法估計未知節點Ui的位置

(′i，′i)=∑3j=1ωj×(xj，yj)∑3j=1ωj

(14)

其中，ωj=RSSIj為加權因子，第i個節點的定位誤差為ei，WCL=(xi-′i)2+(yi-′i)2。 找出所有可定位節點的定位誤差中的最大值，記為emax。

根據使用加權質心得到的Ui的估算坐標 (′i，′i) 和最大定位誤差emax確定對應的WOA算法搜索空間SPi，即：[′i-emax，′i+emax]×[′i-emax，′i+emax]， 如圖3所示。

圖3 根據質心確定搜索空間SPi

在二維的無線傳感器網絡中，第i個未知節點與第j個虛擬錨節點估計距離的平均誤差定義如下

ei，j=|(xi-xj)2+(yi-yj)2-dei，j|

(15)

其中，(xj，yj) 為虛擬錨節點Vj的坐標，(xi，yi) 為傳感器節點Ui的實際位置，dei，j為虛擬錨節點Vj與傳感器節點Ui的測量距離。通過這種方法，我們可以得到如下的目標函數

minf(x，y)=1Ni∑Nij=1|(x-xj)2+(y-yj)2-dei，j|

(16)

其中，Ni是傳感器節點Ui可以接收到的信標信息數。

最后，在SPi中隨機產生鯨魚種群，使用以上目標函數估算Ui的最終坐標。算法2給出了計算第i個傳感器節點坐標Ui的過程。

算法2：節點位置估算算法

輸入：Li，MaxIter

(1)SortLiin descending order according toRSSIi,j

(2)ifdist(Li(1),Li(2))=dist(Li(1),Li(k))=dist(Li(2),Li(k))=d

(3)V1←Li(1);V2←Li(2);V3←Li(k)

(4)else

(5)V1←Li(1);V2←Li(2);V3←Li(3)

(6)endif

(8)Calculate localization error of each node and findemax

(9)SPi←[′i-emax,′i+emax]×[′i-emax,′i+emax]

(10)Initialize whales populationXi(i=1,2,…,n) inSPi

(11)Calculate fitness of each whale using Eq.(16)

(12)X*←the best search agent

(13)while(t

(14)foreach whale

(15) Updatea,A,C,l, andp

(16)ifp<0.5

(17)if|A|<1

(18) Update current whale by Eq.(11)(p<0.5)

(19)elseif|A|>1

(20) Select a random whale (Xrand)

(21) Update current whale by Eq.(13)

(22)endif

(23)elseifp>0.5

(24) Update current whale by the Eq.(11)

(25)endif

(26)endfor

(27) Check if any whale goes beyond theSPiand amend it

(28) Calculate fitness of each whale

(29) UpdateX*if there is a better solution

(30)t←t+1

(31)endwhile

(32)returnX*

算法2中的第(1)～第(6)行根據Ui找到對應的V1、V2、V3。第(7)～第(9)根據式(14)得到 (′i，′i)， 然后計算每個未知節點的定位誤差并找到最大值emax。最后根據 (′i，′i) 和emax確定出對應的搜索空間SPi，限制WOA的初始化區域，加快算法收斂速度。第(10)～第(12)行在SPi中初始化鯨魚的位置，使用式(16)計算每一個個體的適應度值，找出適應度最好的個體記為X*。第(13)～第(31)行是鯨魚優化算法的執行過程，MaxIter為最大迭代次數。先更新a、A、C、l和p的值，當p<0.5且 |A|<1時，鯨魚群向最優鯨魚位置移動，使用式(11)更新每只鯨魚的位置。當p<0.5且 |A|>1時，鯨魚群隨機移動，使用式(13)更新每只鯨魚的位置。當p>0.5時，鯨魚沿螺旋狀路徑吐出氣泡包圍獵物，使用式(11)更新每只鯨魚的位置。修正超出搜索空間SPi的鯨魚個體。使用式(16)更新每只鯨魚的適應度值，并更新X*的值。在迭代循環結束前重復執行以上步驟。第(32)行返回X*的值即為 (i，i)。

3 仿真實驗

使用MATLAB 2016a進行仿真實驗。部署區域為100 m×100 m的正方形二維區域，對SCAN[1]、GTURN[7]、GSCAN[7]、PP-MMAN[4]、H-Curves[2]、M-Curves[3]以及本文提出的DASCAN在路徑長度、定位精度和定位率方面進行對比。

3.1 路徑對比

d取值為10 m、15 m、20 m、25 m。實驗結果如圖4所示?？梢钥闯?，d相同時，GTURN和GSCAN都是最長的，原因在于它們使用3個移動錨節點，并且GSCAN存在重復路徑。H-Curves、SCAN和M-Curves由于只有一個移動錨節點，并且路徑結構較為簡單，所以移動路徑較短。DASCAN短于PP-MMAN，比最長的GTURN路徑平均縮短了44%，比最短的SCAN路徑平均長了26.5%。

圖4 路徑長度比較

下面對不同路徑規劃算法的虛擬錨節點數目進行對比。實驗結果如圖5所示，7種路徑規劃算法的虛擬錨節點的平均數量排序為GSCAN>GTURN>PP-MMAN=DASCAN>H-Curves>M-Curves>SCAN。GSCAN的虛擬錨節點數量是最多的，這是因為GSCAN的移動錨節點會在某些位置重復廣播信標信息。DASCAN產生的虛擬錨節點數目均少于GSCAN、GTURN、PP-MMAN以及M-Curves，但是比起H-Curves和SCAN要更多。因為在相同d的情況下，DASCAN的路徑相鄰兩行之間的距離比SCAN和H-curve更小，所以在部署區域均為100 m2的情況下，DASCAN會產生更多的虛擬錨節點。雖然M-Curves的虛擬錨節點更密集，但是該算法不需要在部署區域邊界生成虛擬錨節點。從圖中可以看出，本算法產生的虛擬錨節點數目相比GSCAN平均減少了53%，相比SCAN平均增加了32%。

圖5 虛擬錨節點數量比較

綜合路徑長度以及虛擬錨節點數量，分別計算7種路徑規劃算法產生的總能耗。實驗結果如圖6所示，7種路徑規劃算法的能耗從高到低為GTURN、GSCAN、PP-MMAN、DASCAN、H-Curves、M-Curves、SCAN。由于GSCAN和GTURN的虛擬錨節點數量較多，路徑較長，所以這兩種算法的能耗比其它算法更高，由于DASCAN的路徑長度比PP-MMAN更短，所以能耗相對更低。H-Curves、M-Curves和SCAN的虛擬錨節點數量較少，路徑較短，產生的能耗也更低。本文算法相比能耗最高的GTURN能耗平均降低了42.7%，相比能耗最低的SCAN能耗平均增加了35.4%。

圖6 能耗比較

3.2 定位精度對比

取R=15 m，DOI=0，實驗結果如圖7所示?？梢钥闯?，無論使用哪一種路徑規劃算法，使用加權質心算法計算得到的結果誤差最大，而使用WOA得到的結果誤差最小。在使用加權質心定位未知節點時，H-Curves、M-Curves 和SCAN的定位誤差要遠遠高于其它路徑規劃算法，當使用三邊定位時，所有路徑規劃算法的定位誤差大幅降低，H-Curves、M-Curves和SCAN的定位誤差仍略高于其它路徑規劃算法。在使用PSO和WOA定位節點時，所有路徑規劃算法的定位誤差進一步下降，并且WOA的平均定位誤差略低于PSO，此時H-Curves和SCAN的定位誤差仍要高于其它算法。

將所有路徑與WOA算法聯合來對比性能。實驗結果如圖8所示。從圖中可以看出，隨著DOI的增加，每個未知節點接收到的廣播信息數量減少，每種路徑規劃算法的定位誤差均受到了DOI的影響，但影響幅度有所差別。由于SCAN和H-Curves存在大量的共線虛擬錨節點，所以定位誤差相比其它路徑更大，而且更容易受DOI的影響。而DASCAN和其余的路徑受DOI影響相對較小。

圖8 路徑在不同DOI下的定位精度

最后不考慮DOI的影響，比較每種路徑在不同的通信半徑R下的定位精度。實驗結果如圖9所示。可以看出，當d=15 m時，每種路徑的平均定位誤差均隨著通信半徑R的增大而增加。雖然通信半徑越大，每個未知節點接收到的信標信息越多，但是由于RSSI的缺陷，未知節點與距離較遠的虛擬錨節點之間的測距誤差較大。所以當通信半徑增大時，定位誤差會變大。H-Curves和SCAN在不同R下的定位誤差均高于其它定位算法，DASCAN的定位誤差以及受通信半徑的影響較小。

圖9 路徑在不同通信半徑下的定位精度

3.3 定位率對比

取d=15 m，R取0.8d、1.0d、1.2d、1.4d，DOI=0、0.05、0.1、0.15、0.2。實驗結果如圖10所示。

圖10 路徑在不同通信半徑下的定位率

整體來看，每種路徑的定位率隨著Rd的增大而增大。在每種取值的情況下，DASCAN、GTURN、GSCAN和PP-MMAN的定位率十分接近，其余路徑的定位率從高到低依次為M-Curves、H-Curves、SCAN。當R=0.8d時，7種路徑的定位率差距最大，此時DASCAN、GTURN、GSCAN和PP-MMAN的定位率約為50%，H-Curves和SCAN僅能定位20%左右的未知節點。當R=1.4d時，7種路徑均可定位所有未知節點。

最后，比較了在不同DOI、R對定位率的影響，實驗結果如圖11、圖12、圖13和圖14所示。整體來看，每種DOI取值下，每種路徑的定位率隨著Rd的增大而增大。每種取值情況下，DASCAN、GSCAN、GTURN和PP-MMAN的定位率都十分接近，均高于H-Curves、M-Curves、SCAN的定位率。DASCAN、GSCAN、GTURN、PP-MMAN的定位率接近，高于其它路徑。整體來看，DASCAN的定位率比M-Curves、H-Curves、SCAN分別平均高出3%、15%、19%。R=0.8d，DOI=0.2時，7種路徑的平均定位率最低，此時DASCAN的定位率約30%，H-Curves和SCAN的定位率低于10%。R=1.4d，DOI=0.05時，7種路徑的定位率均為100%。當R=d，DOI=0.2時，DASCAN的定位率相比其它路徑平均提升最大，為30%；R=d，DOI=0.05時，DASCAN的定位率相比其它路徑平均提升最小，為20%。

圖11 路徑在不同通信半徑下的定位率(DOI=0.05)

圖12 路徑在不同通信半徑下的定位率(DOI=0.1)

圖13 路徑在不同通信半徑下的定位率(DOI=0.15)

圖14 路徑在不同通信半徑下的定位率(DOI=0.2)

綜上，DASCAN比GTURN、GSCAN、PP-MMAN路徑短，避免了重復廣播信息，從而降低了移動錨節點的能耗。同時，比H-Curves、M-Curves和SCAN有更高的定位率和定位精度，配合WOA可以進一步提高算法的定位精度。

4 結束語

本文提出了一種基于雙移動錨節點和鯨魚優化的無線傳感器網絡定位算法，設計了一種雙移動錨節點路徑，并使用加權質心算法輔助鯨魚優化算法估算未知節點的坐標，提高了定位精度。實驗結果表明，DASCAN比其它采用多個移動錨節點的路徑更短，定位誤差更小，比H-Curves等采用單個移動錨節點的定位率、定位精度更高，并且受DOI和RSSI測距誤差的影響更小。

但是，本文所提出的算法在部署區域的邊緣位置的定位精度較低，下一步需提出用于區域邊緣未知節點定位的補償算法。