唐一韜，鄧河

(長沙民政職業(yè)技術(shù)學(xué)院 通識教育中心,長沙 410004)

0 引言

隨著智能終端設(shè)備的日增以及無線網(wǎng)絡(luò)的普及，人們的生活與物聯(lián)網(wǎng)關(guān)系也日益緊密[1].由微型傳感節(jié)點(diǎn)構(gòu)成的無線傳感網(wǎng)絡(luò) (WSN)是物聯(lián)網(wǎng)的基石[2-3].傳感節(jié)點(diǎn)先感知環(huán)境數(shù)據(jù)，再通過鄰居節(jié)點(diǎn)的轉(zhuǎn)發(fā)，將數(shù)據(jù)傳輸至控制中心.

節(jié)點(diǎn)感知的數(shù)據(jù)離不開節(jié)點(diǎn)的位置.因此，定位是基于WSN 物聯(lián)網(wǎng)應(yīng)用的關(guān)鍵.盡管衛(wèi)星定位系統(tǒng)已被廣泛應(yīng)用，但將其應(yīng)用于WSN 的成本高，不適合大規(guī)模部署.多數(shù)節(jié)點(diǎn)只能依據(jù)網(wǎng)絡(luò)拓?fù)渲R或者節(jié)點(diǎn)間的連通信息估計(jì)自己的位置信息.

針對WSN 的定位問題，學(xué)者已提出不同的定位算法.這些定位算法可粗略分為基于測距定位(Rangbased)和非測距定位(Rang-free)算法兩類[4].不失一般性，測距定位算法的精度優(yōu)于非測距定位算法的精度.但是非測距定位算法易實(shí)施，部署成本低.

因此，非測距定位算法更適用于低功耗、低成本的物聯(lián)網(wǎng).非測距定位算法不是建立在節(jié)點(diǎn)間距離值，而是網(wǎng)絡(luò)拓?fù)湫畔ⅲ缳|(zhì)心算法[5]、DV-Hop 算法[6]、近似三角形內(nèi)點(diǎn)測試(APIT)算法[7].

因避免直接測量節(jié)點(diǎn)間距離，DV-Hop 算法成為非測距定位算法的代表.DV-Hop 算法先利用距離矢量路由方法估計(jì)錨節(jié)點(diǎn)與未知節(jié)點(diǎn)間的最小跳數(shù)，再結(jié)合平均跳距測量錨節(jié)點(diǎn)與未知節(jié)點(diǎn)間的距離，最后利用三邊測量法估計(jì)未知節(jié)點(diǎn)位置.

簡之，DV-Hop 算法主要涉及到最小跳數(shù)、平均跳距和估計(jì)節(jié)點(diǎn)位置三個(gè)環(huán)節(jié).任一個(gè)環(huán)節(jié)的估計(jì)或者測量誤差，均會降低估計(jì)節(jié)點(diǎn)位置的精度.此外，前兩個(gè)環(huán)節(jié)的誤差會累加至估計(jì)節(jié)點(diǎn)位置的環(huán)節(jié).其中最小跳數(shù)估計(jì)、平均跳距的計(jì)算易受網(wǎng)絡(luò)拓?fù)湟约巴ㄐ虐霃接绊?

針對DV-Hop 算法的定位精度問題，學(xué)者已著手對其進(jìn)行改進(jìn).例如張晶等[8]提出基于DV-Hop 算法的三次修正的定位算法.該算法先根據(jù)接收信號強(qiáng)度值(RSSI)對跳數(shù)進(jìn)行連續(xù)性劃分，再利用平方誤差適應(yīng)度函數(shù)修正跳距值，最后利用泰勒展開式估計(jì)節(jié)點(diǎn)位置.然而，測量發(fā)送端與接收端間RSSI 值容易受環(huán)境影響.同一對收發(fā)端的RSSI 值也可能存在較大差異.同一個(gè)節(jié)點(diǎn)接收的多個(gè)RSSI 值可能波動較大.因此，利用RSSI 修正跳距效果并不好.

針對DV-Hop 算法的問題，提出基于獅群優(yōu)化算法的節(jié)點(diǎn)定位 (NLLSO) 算法.NLLSO 算法根據(jù)DVHop 算法的特點(diǎn)，對其進(jìn)行有針對性地改進(jìn).主要工作如下：1)采用不同通信半徑傳輸Beacon，進(jìn)而提升估計(jì)跳數(shù)的精度；2) 修正平均跳距；3)利用獅群優(yōu)化算法 (LSO) 估計(jì)未知節(jié)點(diǎn)位置.性能分析表明，NLLSO算法提高了定位精度.

1 網(wǎng)絡(luò)模型及LSO 概述

1.1 網(wǎng)絡(luò)模型

N個(gè)傳感節(jié)點(diǎn)隨機(jī)分布于二維網(wǎng)絡(luò)l×l，其中錨節(jié)點(diǎn)占比為p%，未知節(jié)點(diǎn)占比為(100-p)%.令αi表示第i個(gè)錨節(jié)點(diǎn)，其位置坐標(biāo)為令sj表示第j個(gè)未知節(jié)點(diǎn)，其位置坐標(biāo)為如圖1 所示,在100 m×120 m區(qū)域內(nèi)隨機(jī)部署N=50 個(gè)未知節(jié)點(diǎn).錨節(jié)點(diǎn)占比p=10 .

圖1 網(wǎng)絡(luò)模型

1.2 LSO 概述

作為智能優(yōu)化算法，LSO 模擬了自然界中獅群的覓食行為.LSO 中主要涉及三類角色：獅王、母獅和幼獅.它們遵照自然界法則生存，并采用不同的位置更新方式更新自己的位置.相比于母獅和幼獅，獅王的位置更新更快、收斂快、不易陷入局部最優(yōu)，能夠快速地搜索到全局最優(yōu)解[9].因此，選擇LSO 估計(jì)節(jié)點(diǎn)位置.表1 給出LSO 中相關(guān)符號的物理意義.

表1 LSO 的相關(guān)符號

假定在二維空間中分布了M只獅子，其中成年獅的比例為 β .每個(gè)成年獅群中只有一只公獅，余下的成年獅為母獅.幼獅數(shù)量為M(1-β) .

2 NLLSO 算法

2.1 基于多通信半徑的最小跳數(shù)估計(jì)

傳統(tǒng)估計(jì)最小跳數(shù)的算法將通信半徑內(nèi)的跳數(shù)值都看成一跳[10].例如，若節(jié)點(diǎn)1 離節(jié)點(diǎn)2 的距離為30 m，節(jié)點(diǎn)1 離節(jié)點(diǎn)3 的距離為20 m.如果節(jié)點(diǎn)1 的通信半徑大于30 m,節(jié)點(diǎn)2 和3 節(jié)點(diǎn)就在其一跳通信范圍內(nèi).依據(jù)傳統(tǒng)估計(jì)最小跳數(shù)估計(jì)算法，節(jié)點(diǎn)2、3 離節(jié)點(diǎn)1 的跳數(shù)均為1.當(dāng)平均跳距為d時(shí)，節(jié)點(diǎn)1 離節(jié)點(diǎn)2、3 的距離均為d，而實(shí)際上，節(jié)點(diǎn)1 離節(jié)點(diǎn)2、3 的距離分別為30 m、20 m.

為此，采用動態(tài)的通信半徑.通過調(diào)整發(fā)射功率，錨節(jié)點(diǎn)選擇不同的通信半徑.令R表示默認(rèn)的節(jié)點(diǎn)通信半徑.錨節(jié)點(diǎn)采用5 種通信半徑，分別為 0.2R、0.4R、0.6R、0.8R和R.

具體實(shí)現(xiàn)過程如下：最初網(wǎng)絡(luò)中所有錨節(jié)點(diǎn)采用0.2R的通信半徑廣播Beacon 包，Beacon 包攜帶了錨節(jié)點(diǎn)位置以及ID 號.在0～ 0.2R傳播范圍內(nèi)的節(jié)點(diǎn)收到Beacon 包，未知節(jié)點(diǎn)就獲取離錨節(jié)點(diǎn)的最小跳數(shù)為0.2 跳.

然后再逐步增加通信半徑(從 0.4R～ 0.6R，再提升到0.8R～R)，相應(yīng)地，未知節(jié)點(diǎn)獲取不同通信半徑下的跳數(shù)值.

2.2 跳距的修正

利用離其他錨節(jié)點(diǎn)的距離和其他錨節(jié)點(diǎn)位置(已知信息)，錨節(jié)點(diǎn)修正自己的跳距值.即錨節(jié)點(diǎn) αi先利用式(4)計(jì)算平均跳距AHDi

再利用hi j和 AHDi，估計(jì)錨節(jié)點(diǎn) αi離 αj的距離(估計(jì)距離)

不失一般性，實(shí)際距離dij與估計(jì)距離間存在誤差，并且該誤差是已知的.因此，可利用該書籍信息修正平均跳距.即通過最小化誤差對平均跳距進(jìn)行修正

考慮到錨節(jié)點(diǎn)間跳數(shù)影響了AHDi的值，式(1)所估計(jì) AHDi可能存在誤差.為了降低誤差，引用權(quán)值對平均跳距進(jìn)行約束，進(jìn)而降低因平均跳距誤差引起的測距誤差.

依式(5)可知，錨節(jié)點(diǎn) αi離 αj的跳數(shù)越大，估計(jì)距離的誤差越大.因此，將跳數(shù)大的兩節(jié)點(diǎn)間的權(quán)值變小，可降低其對測距的影響.為了求解方便，對式(7)進(jìn)行矩陣化表述

2.3 位置估計(jì)

NLLSO 算法采用獅群優(yōu)化估計(jì)未知節(jié)點(diǎn)位置.為此，先設(shè)定目標(biāo)函數(shù)

式中，fj(x,y)為求解未知節(jié)點(diǎn)sj所建立目標(biāo)函數(shù).

節(jié)點(diǎn)sj建立的適應(yīng)值函數(shù)

具體的基于LSO 求解未知節(jié)點(diǎn)位置的步驟如步驟1～6 所示：

步驟1：在二維空間中隨機(jī)初始化N個(gè)節(jié)點(diǎn)位置，并將其作為獅群中獅子的位置，并設(shè)置最大迭代次數(shù)T和成年獅比例.

步驟2：計(jì)算獅群中不同角色獅子數(shù)量，獅王位置設(shè)置為初始種群最優(yōu)位置，設(shè)置個(gè)體歷史最優(yōu)位置為各獅的當(dāng)前位置.

步驟3：依據(jù)式(1)～(3)更新獅王、母獅和幼獅的位置，并根據(jù)式(12)計(jì)算適應(yīng)度值.

步驟4：更新自身和獅群歷史最優(yōu)位置.檢測兩次最優(yōu)值的差值的絕對值是否小于預(yù)設(shè)的精度值.若小于，則跳轉(zhuǎn)步驟6，否則轉(zhuǎn)入步驟5.

步驟5：每隔10 次重新排序，確認(rèn)獅王、母獅和幼獅的位置，再跳轉(zhuǎn)到步驟3.

步驟6：輸出獅王的位置，即未知節(jié)點(diǎn)的位置.

3 性能仿真

3.1 仿真環(huán)境

利用MATLAB 2018 a 軟件建立仿真平臺，N個(gè)節(jié)點(diǎn)隨機(jī)分布于100 m×100 m，其中錨節(jié)點(diǎn)數(shù)比例p%從10%～31%變化.節(jié)點(diǎn)的傳輸功率從-5～-15 dBm變化，具體的仿真參數(shù)如表2 所示.每次仿真獨(dú)立進(jìn)行20 次，取平均值作為最終定位數(shù)據(jù).

表2 仿真參數(shù)

為了更好地分析NLLSO 定位算法的性能，選同類算法DV-Hop[11]、基于RSSI 測距修正的四邊形加權(quán)質(zhì)心定位(QWCRC)算法[12]進(jìn)行比較.并分析它們的歸一化定位誤差

式中：m為未知節(jié)點(diǎn)數(shù)，即m=N-N×p% ；為節(jié)點(diǎn)的平均通信半徑.

3.2 定位誤差隨錨節(jié)點(diǎn)數(shù)變化情況

先分析定位誤差隨錨節(jié)點(diǎn)數(shù)的變化情況.圖2 顯示歸一化定位誤差隨錨節(jié)點(diǎn)數(shù)的變化曲線.總的節(jié)點(diǎn)數(shù)為150，錨節(jié)點(diǎn)數(shù)占比從0.1～0.31 變化，通信半徑R=36 m.

圖2 歸一化定位誤差隨錨節(jié)點(diǎn)數(shù)變化情況

由圖2 可知，在總的節(jié)點(diǎn)數(shù)一定時(shí)，增加錨節(jié)點(diǎn)數(shù)提升定位精度.但值得注意的是，當(dāng)錨節(jié)點(diǎn)數(shù)達(dá)到一定量后，定位精度的提升也存在“飽和”現(xiàn)象.這也說明，優(yōu)化錨節(jié)點(diǎn)數(shù)也是定位算法須考量的問題之一.

此外，在同等條件下，NLLSO 算法的定位精度優(yōu)于DV-Hop 算法和QWCRC 算法，且分別提高了相比于DV-Hop 和QWCRC 算法，NLLSO 算法9%和5%.這說明NLLSO 算法通過平均跳距的修正和基于LSO，可以有效地提高平均定位精度.

3.3 定位誤差隨通信半徑變化情況

本小節(jié)分析定位誤差隨通信半徑的變化情況.圖3 描述了定位誤差隨通信半徑的變化曲線.總的節(jié)點(diǎn)數(shù)為150，錨節(jié)點(diǎn)數(shù)占比為0.2，通信半徑約為21～45 m 變化.

圖3 定位誤差隨通信半徑的變化情況

由圖3 可知，增加通信半徑可提高定位精度.這主要因?yàn)楣?jié)點(diǎn)通信半徑越大，數(shù)據(jù)傳輸路徑的跳數(shù)越小，這有利于降低估計(jì)最小跳數(shù)和跳距的誤差.更準(zhǔn)確的跳數(shù)值和跳距有利于提高定位精度.此外，相比于DV-Hop 和QWCRC 算法，NLLSO 算法有效地降低定位誤差，且分別降低約8%和3%.

3.4 定位誤差隨節(jié)點(diǎn)數(shù)變化情況

最后分析定位誤差隨總節(jié)點(diǎn)數(shù)的變化情況.圖4描繪了歸一化定位誤差隨總節(jié)點(diǎn)數(shù)的變化曲線.錨節(jié)點(diǎn)數(shù)占比為0.2，總節(jié)點(diǎn)數(shù)從100～200 變化.節(jié)點(diǎn)通信半徑為36 m.

圖4 節(jié)點(diǎn)數(shù)對歸一化定位誤差的影響

由圖4 的曲線走勢可知，增加總節(jié)點(diǎn)數(shù)降低了定位誤差.最初，增加總節(jié)點(diǎn)數(shù)能夠快速地降低定位誤差.但當(dāng)總節(jié)點(diǎn)數(shù)增加到140 后，定位誤差的下降速度變緩慢，趨于直線.原因在于：最初網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)數(shù)的增加，增加測距精度和估計(jì)最小跳數(shù)的精度.但當(dāng)網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)數(shù)達(dá)到一定量后，再增加節(jié)點(diǎn)數(shù)，就增加了網(wǎng)絡(luò)負(fù)擔(dān)，出現(xiàn)“飽和現(xiàn)象”.此外，相比于DV-Hop 和QWCRC 算法，NLLSO 算法有效地提升了定位精度.

3.5 算法復(fù)雜度

在Windows 7 操作系統(tǒng)、8 GB 內(nèi)存，Core i7 CPU的PC 運(yùn)行算法，并記錄運(yùn)算時(shí)間.運(yùn)行50 次，取平均值作為最終的數(shù)據(jù)，如表3 所示.由表3 可知，DVHop 算法的運(yùn)行時(shí)間最短，NLLSO 算法的運(yùn)行時(shí)間次之，QWCRC 算法的運(yùn)行時(shí)間最長.原因在于：NLLSO 算法利用LSO 估計(jì)節(jié)點(diǎn)位置，增加了算法的復(fù)雜度.結(jié)合定位誤差的數(shù)據(jù)可知，NLLSO 算法能夠在定位誤差與復(fù)雜度間達(dá)到較好地平衡.

表3 算法的復(fù)雜度

4 結(jié)束語

NLLSO 算法針對傳統(tǒng)DV-Hop 算法在跳數(shù)估計(jì)、跳距測量和定位三個(gè)環(huán)節(jié)上的問題進(jìn)行了一定的改進(jìn).通過采用不同通信半徑傳輸Beacon 包，提升估計(jì)最小跳數(shù)的精度.并引用權(quán)重對平均跳距的修正，降低測距誤差.通過LSO 估計(jì)節(jié)點(diǎn)位置，性能分析表明，相比于傳統(tǒng)DV-Hop 算法 NLLSO 算法降低了定位誤差.

然而，本文僅關(guān)注了NLLSO 算法在定位精度方面的優(yōu)勢，并沒有考慮了多通信半徑過程中所產(chǎn)生開銷.后期，將考慮如何降低節(jié)點(diǎn)間的通信量，控制節(jié)點(diǎn)能量消耗，這將是后期的工作方向.