基于WOA-SOS的無線傳感器網絡節點定位

傅 彬

（紹興職業技術學院，浙江 紹興 312000）

0 引 言

隨著5G通信技術的快速發展，物聯網（Internet of Things，IoT）技術[1]已經成為當前信息技術發展的新的組成部分。無線傳感網絡（Wireless Sensor Network，WSN）作為物聯網中一種重要的應用技術發揮著舉足輕重的作用。在實際場景的應用中，節點定位技術是WSN的重要基礎，這是因為無線傳感網絡中的節點在獲得準確的信息后，才能將自身攜帶的數據進行發送和接收，才能使所攜帶的數據發揮最大的應用價值。因此，如何獲得節點的精確位置以及提高定位精度，已經成為WSN研究的焦點。文獻[2]提出了基于斯蒂芬森迭代改進DVHop的無線傳感器節點定位算法，仿真實驗說明該算法相比于改進前的算法無論是在未知節點的定位時間上，還是在節點的定位準確率上都有明顯的提升，但缺乏與較新定位算法的對比。文獻[3]提出了一種改進樽海鞘群算法優化的DV-Hop定位算法，算法的定位精度較高，具有更好的定位能力，但算法的復雜度有所提升，提高了節點能耗。文獻[4]提出一種基于改進粒子群算法優化LSSVR模型的定位方法，在定位效果方面具有較好的穩定性與實時性。文獻[5]提出一種改進的人工免疫算法（AIA）優化DV-Hop未知節點坐標，具有較高的定位精度和較好的定位穩定性，同時也改善了算法的收斂性，但缺乏與更多算法效果的對比，實驗效果有待進一步驗證。文獻[6]提出了改進的加權質心算法節點定位方法，仿真實驗說明該算法相較傳統質心算法具有定位精度高、用時少等優勢，但缺乏與其他優化后的質心算法的對比。文獻[7]提出基于反向學習的群居蜘蛛優化WSN節點定位算法，該算法收斂速度更快，節點定位精度更高，但提高了算法的復雜度，影響了節點定位時間。文獻[8]提出了基于量子退火算法的無線傳感器網絡節點定位方法，該方法相比于傳統的遺傳算法和模擬退火算法來說，在定位精度和節點定位能耗上都有顯著的提升；文獻[9]提出了一種基于灰狼算法的節點定位模型，該模型使用灰狼算法優化DV-HOP算法中的節點位置，仿真實驗說明該算法在節點定位中的指標獲得較好的結果。文獻[10]提出了一種基于butterfly optimization algorithm的節點定位算法，仿真實驗說明該算法能夠改善節點的定位效果。文獻[11]提出了基于優化的粒子群的混合算法用于節點定位，仿真說明優化后的算法定位效果相比于單一算法具有更好的定位效果。文獻[12]提出使用貓群算法用于節點定位，通過對貓群算法進行不同程度的優化，使得改進后的貓群算法在節點定位中獲得了較好的效果.

在以上的研究中，學者們使用了元啟發式算法用于無線傳感器網絡的節點定位，取得了較好的效果。本文在以上研究成果的基礎上，提出了基于鯨魚算法和生物共生演算法的融合算法（Whale Optimization Algorithm-Symbiotic Organisms Serarch，WOA-SOS）用于節點定位的研究。仿真實驗說明該算法具有較好的性能，能夠有效地降低節點定位誤差。

1 節點定位優化函數

無線傳感的定位問題本質上是一個多約束優 化 問 題[13]。設 定n（n＞3）個 錨 節 點P1(x1,y1)，P2(x2,y2)，…，Pn(xn,yn)與未知節點P(x,y)之間的實際測量距離為d1,d2,…,dn，因此表達如下：

使用線性方程組表示AL=b

實際環境過程中肯定會存在一些誤差因素ε，因此以上的線性方程組可修正為AL+ε=b，通過最小二乘法表示如下：

因此優化問題轉換為如下表達：

因此定義目標函數為：

通過上面的推導過程可以發現，式（6）的解在一個可行解的區域中，而處于這個可行解區域一定包含了最優解，因此，根據式（7）來計算整體上獲得最小值的坐標，也就是需要求解的未知節點的坐 標(x,y)。

2 基本算法

2.1 鯨魚算法

2016年，MIRJALILI S[14]根據鯨魚在大海中的捕食行為提出了鯨魚算法（Whale Optimization Algorithm，WOA）。主要分為包圍捕食、氣泡攻擊、尋覓食物三個階段。

2.1.1 包圍捕食

在算法的初級階段，座頭鯨將距離食物最近的鯨魚當作當前的一個最優解，數學模型表達為：式中：表示搜索代理座頭鯨到目標食物之間的距離向量，t用來表示當前算法執行的迭代次數，和分別表示系數向量，X*為當前迭代次數下的局部最優解，表示當前座頭鯨的位置向量，和的表達數學公式如下：

式中：表示一個線性遞減向量，其值從2到0，r表示0到1之間的隨機數。

2.1.2 氣泡攻擊

本階段主要闡述座頭鯨進行氣泡攻擊，通過收縮包圍和螺旋更新位置來設計鯨魚捕食吐出氣泡的行為過程，逐步達到鯨魚局部尋優的目的。

（1）收縮包圍原理

在式（9）中，當|A|＜1時，鯨魚個體向著當前位置最優的鯨魚靠近，并且|A|越大鯨魚游走的步伐越大，當|A|越小，鯨魚游走的步伐就越小。

（2）螺旋更新位置

座頭鯨個體計算與當前最優鯨魚的距離，然后再以螺旋方式游走，其數學模型公式如下：

2.1.3 尋覓食物階段

座頭鯨個體向著參考座頭鯨的位置靠近，鯨魚個體朝著隨機選取的座頭鯨更新位置，獲得全局最優解，其數學公式模型如下：

式中：Xrand是隨機獲得的參考座頭鯨的位置向量。

2.2 共生演算法

2014年，CHENG M Y等人根據大自然中的生物生活的特性，并結合大自然規律，提出生物共生演算法（Symbiotic Organisms Serarch，SOS）[15]。該算法根據生物生活特性主要分為共生、共棲、寄生三個階段。

（1）共生階段。設置Xi表示第i個生物個體，Xj表示隨機和Xi進行相互作用的個體。這兩種Xi與Xj是基于相互共生的候選解的關系，表達如下：

式中：BF1和BF2表示相關的利益因素，Xbest代表當前解中適應度最高的個體。如果當前第i個生物個體的適應度數值高于當前適應度值最高的個體，則Xi變為Xinew，否則，Xj變為Xjnew，否則保持不變。

（2）共棲階段。Xi產生的新候選解是根據生物Xi和Xj生物之間的共生關系來獲得，表達如下：

在該階段中，該Xi對應的個體適應度值優于適應度最高的個體，則Xi個體變為Xinew，否則保持 不變。

（3）寄生階段。算法設定人工的寄生蟲Parasite來避免算法過早地陷入過早的收斂。它的設計來源是在搜索空間中對個體Xi復制而來，設定為[0，1]之間的隨機數與該生物個體Xi乘積。

在該階段中，算法隨機選擇一個生物個體Xj作為設定的人工寄生蟲的載體。在算法迭代過程中，一旦這個人工寄生蟲個體的適應度值優于當前最優個體，則會取代該生物個體，否則該生物個體獲得進一步的免疫，從而去除人工的寄生蟲Parasite，能夠有效地避免算法陷入過早的收斂。

3 基于WOA-SOS算法的節點定位

類似大部分元啟發式算法的特點，WOA算法同樣也會存在容易陷入局部停滯、導致算法收斂速度慢、解的精度有待提升的問題。本文提出3個反面的鯨魚算法的優化策略：（1）利用混沌映射進行種群初始化，保持種群具有多樣性；（2）構建自適應權重因子改進螺旋更新位置，避免算法陷入局部最優；（3）利用生物共生演算法進行個體的更新。

3.1 種群初始化

種群的初始化在很大程度上影響著算法的效果。隨機產生的初始化并無法保證種群具有的多樣性，因此本文在混沌映射思想的基礎上進行種群初始化，公式如下：

設置種群規模N、維度D和最大混沌迭代步數K，種群初始化方法具體如下：

其中，xk-1,j表示在k-1次迭代中的第j維中的第i個個體，xk,j表示采用了混沌映射后的第k次迭代中j維中的第i個個體，xi,j表示第j維中的第i個個體，xmax,j和xmin,j分別表示j維空間的上下界。

3.2 自適應收斂因子

在基本的WOA算法公式（11）發現，A值在很大程度上受到a的影響，當a值較大，算法具有較好的全局搜索能力，反之則容易陷入局部最優。因此a值就顯得非常重要。因此，本文設定a值表達如下：

式中：tmax為算法設定的最大迭代次數，t表示個體在當前的迭代次數，fobj(xi)表示當前鯨魚個體i在當前迭代次數下的適應度值。a0為初始值為1。

3.3 節點定位步驟

步驟1：將無線傳感網絡中的節點問題與鯨魚個體進行一一對應，選出最優的座頭鯨，就是最優的節點定位方案。將鯨魚個體的適應度函數設定為式（7）的節點定位優化函數。

步驟2：對WOA算法設置算法的基本參數，設置迭代次數。

步驟3：采用改進的混沌映射進行種群初始化和自適應因子參數。

步驟4：在每一個迭代完成后，對個體采用共生共演算法優化，選擇更優的鯨魚個體進入下一次 迭代。

步驟5：判斷迭代次數是否達到Tmax，如果達到，則算法結束，獲得最優的鯨魚個體即最好的定位效果，反之則轉到步驟3。

4 算法仿真

為了更好地說明本文算法在節點定位中的效果，將實驗分為兩個部分展開研究。第一部分闡述本文算法（WOA-SOS）的性能，第二部分闡述本文算法在節點定位中的效果。

4.1 性能對比

本文將WOA-SOS算法和WOA算法在不同維度（2維、5維、30維）的6個基準測試函數（如 表1所示）下進行對比，算法選擇各自參數并設置相同的迭代次數，借助Matlab 2012仿真平臺得到仿真結果，如表2所示。

表1 基準函數

表2顯示了兩種算法在6個基準函數的不同維度下的最優值和方差對比，從表中的數據可以發現WOA-SOS相比于WOA算法具有更好的性能，這也說明其在種群初始化、自適應因子和個體篩選方面能夠顯著地提高算法的性能，尤其在維度較高的方面表現更加明顯。

表2 兩種算法在不同基準函數的優化結果

4.2 節點定位指標對比

為了說明WOA-SOS算法在節點定位中的效果，本文從節點密度、錨節點比例、通信半徑及區域面積4個指標方面與WOA算法進行比較。本文選擇100個傳感器節點隨機分布于10 m×10 m的二維區域中，錨節點個數占據20%，通信半徑設置為1～3 m。

圖1顯示了兩種算法在不同的節點密度下的節點定位帶來的誤差效果的對比。從圖1可以發現，隨著節點密度的不斷增加，使用兩種算法產生的節點定位曲線都呈現誤差逐漸減小的趨勢。從效果上看，使用本文算法產生的定位誤差影響更小，說明WOA-SOS算法的性能得到了提升，因此在定位誤差方面具有一定的優勢。

圖1 不同節點密度的定位誤差對比

圖2顯示了兩種算法在錨節點數量不同的情況下的節點定位對比。從圖2可以發現，隨著錨節點數量的增加，定位誤差會逐漸減少，但是由于WOA-SOS算法具有良好的性能，定位效果明顯優于WOA算法，這也說明了使用WOA-SOS算法在節點定位中能夠有效地減少誤差。

圖2 不同錨節點數量下的定位誤差對比

圖3顯示了不同的通信半徑下兩種算法的定位誤差對比效果。從圖3可以發現，隨著節點通信半徑逐漸增大，錨節點數量逐漸增大，定位效果具有明顯的提升。但是WOA-SOS算法性能的提升在一定程度上提高了節點定位的精度，從圖3的效果來看，WOA-SOS算法性能明顯優于WOA.

圖3 不同通信半徑下的定位誤差對比

圖4顯示了兩種算法在不同區域面積下的定位誤差對比效果。從效果來看，隨著區域面積逐漸增大，兩種算法的定位誤差都有不同程度的上升，這說明節點定位和區域面積具有一定的關系。盡管WOA-SOS算法性能具有較大的優勢，但是也不能彌補區域面積增大帶來的影響。但是從整體上看，WOA-SOS算法具有明顯的優勢。

圖4 不同區域面積下的定位誤差對比

5 結 語

針對無線傳感網絡中節點定位存在誤差大、精度低的問題，本文提出了基于WOA-SOS的節點定位算法。該算法通過種群的初始化、自適應因子調節和個體篩選提高了算法性能，在節點定位中的節點密度、錨節點比例、通信半徑及區域面積四個指標中具有較好的定位效果，有效地降低了定位誤差。