二次柵格掃描的無線傳感器網(wǎng)絡(luò)定位算法

無線傳感器網(wǎng)絡(luò)是由大量的具有信息感知功能的傳感節(jié)點(diǎn)通過無線通信方式形成一個(gè)多跳的自組織網(wǎng)絡(luò)系統(tǒng)[1]。位置是判斷人或物體所處情形和環(huán)境的直接依據(jù)[2]，在無線傳感器網(wǎng)絡(luò)中利用節(jié)點(diǎn)發(fā)送與接收無線信號(hào)確定物體的位置稱為無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位[3]。根據(jù)定位機(jī)制，可將現(xiàn)有的定位算法分為兩類[4]：基于測距(Range-based)的定位算法和無需測距(Range-free)的定位算法[5]。Range-based的定位對(duì)網(wǎng)絡(luò)的硬件設(shè)施提出了較高的要求，各種測量技術(shù)也存在各自的局限性[6]。此外，Range-based的定位經(jīng)常采用多次測量, 循環(huán)求精[7],這些都將產(chǎn)生大量計(jì)算和通信開銷[8]，因而基于測距定位算法并不適用于低功耗、低成本的應(yīng)用領(lǐng)域[9]。與Range-based機(jī)制相比，Range-free定位機(jī)制對(duì)硬件的要求較低，因此，成本和功耗較低，且網(wǎng)絡(luò)生存能力強(qiáng)[10]，定位精度基本滿足實(shí)際需要，是目前研究工作的重點(diǎn)之一[11]。文中將柵格掃描定位算法得到的位置坐標(biāo)作為初始位置估計(jì)，在此基礎(chǔ)上提出了一種改進(jìn)的Range-free定位算法，減小了平均相對(duì)定位誤差。

Grid-Scan算法是在APIT算法中提出的一種典型的無需測距的定位算法[12]，文獻(xiàn)[13]提出的VGrid-Scan算法主要通過改變錨節(jié)點(diǎn)的通信半徑，但不影響未知節(jié)點(diǎn)搜索鄰居錨節(jié)點(diǎn)，從而縮小未知節(jié)點(diǎn)的定位區(qū)域，該方法在一定程度上提高了定位精度。

Grid-Scan算法分為3個(gè)步驟[15]：

第一步：網(wǎng)絡(luò)部署，待定位的未知節(jié)點(diǎn)搜索其通信范圍內(nèi)所有錨節(jié)點(diǎn)，并記錄被搜索到的錨節(jié)點(diǎn)的ID和坐標(biāo)信息，這些被搜索到的錨節(jié)點(diǎn)稱為鄰居錨節(jié)點(diǎn)。

第二步：將未知節(jié)點(diǎn)Uj所有鄰居錨節(jié)點(diǎn)的通信圓交集以其外接矩形代替，得到外接估計(jì)矩形ER (Estimative Rectangle)[14]。如圖1所示，ER的四條邊分別平行于x軸和y軸。ER的大小由式(1)確定。

圖1   外接估計(jì)矩形示意圖

(lx，ly)為未知節(jié)點(diǎn)所屬的ER大小，i為錨節(jié)點(diǎn)下標(biāo)，(xi，yi)為錨節(jié)點(diǎn)的位置坐標(biāo)，r為錨節(jié)點(diǎn)的通信半徑。

第三步：劃分柵格并計(jì)算未知節(jié)點(diǎn)的坐標(biāo)。設(shè)柵格的邊長為l，ER的長為 L×l，寬為 W×l，則ER可表示為L×W個(gè)柵格的集合G。

將網(wǎng)絡(luò)中所有柵格的初始值賦為0，Cm為柵格的中心，若ER內(nèi)柵格Gm和Cm均位于n個(gè)鄰居錨節(jié)點(diǎn)的通信范圍內(nèi)，則將柵格Gm賦值為n。ER內(nèi)賦值最大的所有柵格組成的區(qū)域?qū)��?yīng)為一個(gè)未知節(jié)點(diǎn)的估計(jì)區(qū)域Ej，如圖2所示賦值最大的柵格組成的區(qū)域即為估計(jì)區(qū)域Ej，最后，計(jì)算該估計(jì)區(qū)域Ej的質(zhì)心位置，實(shí)現(xiàn)對(duì)未知節(jié)點(diǎn)的定位。

圖2   ER內(nèi)柵格賦值

文中通過對(duì)Grid-Scan定位算法的研究發(fā)現(xiàn)，該算法允許未知節(jié)點(diǎn)只存在一個(gè)鄰居錨節(jié)點(diǎn)的情況下進(jìn)行定位，且在隨機(jī)產(chǎn)生的網(wǎng)絡(luò)拓?fù)渲�，未知�?jié)點(diǎn)的實(shí)際位置可能位于以估計(jì)位置到鄰居錨節(jié)點(diǎn)的距離為半徑的圓內(nèi)，這樣的未知節(jié)點(diǎn)存在著可再定位性，對(duì)這些有可再定位性的未知節(jié)點(diǎn)，文中利用Grid-Scan算法允許一個(gè)錨節(jié)點(diǎn)定位的特點(diǎn)，采用最近錨節(jié)點(diǎn)對(duì)具有可再定位性的未知節(jié)點(diǎn)進(jìn)行二次定位，提高定位精度。

首先由鄰居錨節(jié)點(diǎn)的位置信息可以得到未知節(jié)點(diǎn)的初始位置估計(jì)，然后利用鄰居錨節(jié)點(diǎn)坐標(biāo)信息與初始位置估計(jì)的坐標(biāo)信息得到未知節(jié)點(diǎn)更小更精確的位置估計(jì)區(qū)域，最后進(jìn)行二次求精。改進(jìn)算法具體分為3個(gè)階段。

(1)初始位置估計(jì)

設(shè)未知節(jié)點(diǎn)的鄰居錨節(jié)點(diǎn)個(gè)數(shù)為n，利用傳統(tǒng)的Grid-Scan算法對(duì)某未知節(jié)點(diǎn)進(jìn)行定位，得到未知節(jié)點(diǎn)的初始位置估計(jì)坐標(biāo)(xe，ye)，此時(shí)對(duì)應(yīng)該未知節(jié)點(diǎn)ER區(qū)域內(nèi)的柵格已被賦值完成，得到Ej區(qū)域所有被賦值為n的柵格Grid。

(2)判斷可再定位性

求出所有鄰居錨節(jié)點(diǎn)到該未知節(jié)點(diǎn)的信號(hào)強(qiáng)度，設(shè)未知節(jié)點(diǎn)接收到所有鄰居錨節(jié)點(diǎn)的信號(hào)強(qiáng)度為RSS，而RSS中的最大信號(hào)強(qiáng)度RSSu對(duì)應(yīng)的錨節(jié)點(diǎn)即為最近錨節(jié)點(diǎn)。由式(3)計(jì)算初始位置估計(jì)到最近錨節(jié)點(diǎn)的距離dist。

(xe，ye)為初始位置估計(jì)坐標(biāo)，(xist，yist)為最近錨節(jié)點(diǎn)坐標(biāo)，將dist代入 (4)可得初始位置到最近錨節(jié)點(diǎn)的理論信號(hào)強(qiáng)度RSSe。

其中，PT為發(fā)送信號(hào)功率；PL(d0)為參考距離d0的路徑損耗功率；η為路徑損耗指數(shù)。當(dāng)RSSu>RSSe時(shí)，判定未知節(jié)點(diǎn)存在可再定位性；當(dāng)RSSu≤RSSe時(shí)，判定未知節(jié)點(diǎn)不可再定位，該未知節(jié)點(diǎn)最終定位的位置即為初始位置估計(jì)。

(3)柵格二次賦值

對(duì)可再定位的未知節(jié)點(diǎn)進(jìn)行二次柵格掃描。計(jì)算Ej區(qū)域內(nèi)所有柵格的Cm到最近錨節(jié)點(diǎn)的距離D。

當(dāng)dm>dist時(shí)，dm對(duì)應(yīng)在Grid內(nèi)的值不變；當(dāng)dm < dist時(shí)，dm對(duì)應(yīng)在Grid內(nèi)的柵格值為n+1，賦值為n+1的柵格集合為Gridmap；由Gridmap產(chǎn)生一個(gè)新的估計(jì)區(qū)域ENj，計(jì)算ENj的質(zhì)心位置得到最終定位的位置。

如圖2所示，設(shè)未知節(jié)點(diǎn)有三個(gè)鄰居錨節(jié)點(diǎn)A1，A2，A3相交區(qū)域?yàn)镋j，A1為最近錨節(jié)點(diǎn)，在Ej區(qū)域內(nèi)得到未知節(jié)點(diǎn)的初始位置估計(jì)，得到Ej區(qū)域內(nèi)柵格賦值為3的Grid，以初始位置到A1的距離dist為半徑對(duì)Ej區(qū)域進(jìn)行柵格掃描得到估計(jì)區(qū)域ENj，ENj區(qū)域內(nèi)柵格值在Grid基礎(chǔ)上加1，得到ENj區(qū)域所有被賦值為4的柵格集合Gridmap，計(jì)算最終定位坐標(biāo)。

圖3   二次柵格掃描示意圖

文中實(shí)驗(yàn)在Matlab平臺(tái)上進(jìn)行，設(shè)節(jié)點(diǎn)個(gè)為N，并在100×100m監(jiān)測區(qū)域內(nèi)產(chǎn)生隨機(jī)的拓?fù)鋱鼍�，�?jié)點(diǎn)通信半徑為r，柵格邊長為l，節(jié)點(diǎn)發(fā)送信號(hào)功率PT=0dB，參考距離d0=1m，參考距離d0的路徑損耗功率PL(d0)=55dB，路徑損耗指數(shù)η=4。將文中改進(jìn)算法記為SGrid-Scan算法，并與傳統(tǒng)的Grid-Scan算法及文獻(xiàn)[13]中的VGrid-Scan算法在歸一化的平均相對(duì)定位誤差上進(jìn)行對(duì)比。其中，VGrid-Scan算法依然采用文獻(xiàn)[13]中錨節(jié)點(diǎn)通信半徑的設(shè)定方法，設(shè)置為節(jié)點(diǎn)通信半徑的0.7倍。

網(wǎng)絡(luò)中每個(gè)可定位節(jié)點(diǎn)的誤差為：

其中：(xes，yes) 為未知節(jié)點(diǎn)最終的估計(jì)坐標(biāo)，(xtr，ytr)為未知節(jié)點(diǎn)的實(shí)際坐標(biāo)，r為節(jié)點(diǎn)的通信半徑。網(wǎng)絡(luò)中所有未知節(jié)點(diǎn)的歸一化的平均相對(duì)定位誤差為:

其中：文中實(shí)驗(yàn)設(shè)k=100，即產(chǎn)生100個(gè)隨機(jī)網(wǎng)絡(luò)拓?fù)洌?i>nr為可定位的節(jié)點(diǎn)個(gè)數(shù)。

為了使兩種算法的仿真誤差更具對(duì)比性，將每次產(chǎn)生的隨機(jī)網(wǎng)絡(luò)拓?fù)鋱鼍胺謩e提供給SGrid-Scan算法、Grid-Scan算法和VGrid-Scan算法進(jìn)行仿真，確保三種算法在相同環(huán)境下進(jìn)行定位誤差的計(jì)算，增加實(shí)驗(yàn)數(shù)據(jù)對(duì)比的可靠性。

通過式(1)可以發(fā)現(xiàn)，節(jié)點(diǎn)的通信半徑可以影響未知節(jié)點(diǎn)的外接矩形的大小，進(jìn)而影響鄰居錨節(jié)點(diǎn)個(gè)數(shù)。設(shè)節(jié)點(diǎn)個(gè)數(shù)N=200，錨節(jié)點(diǎn)個(gè)數(shù)為40，柵格邊長l=2m。

圖4   通信半徑對(duì)算法定位誤差的影響               如圖6所示，柵格邊長越小，三種算法的定位誤差越低，且SGrid-Scan算法的定位誤差較Grid-Scan算法平均減小了2.37%；SGrid-Scan算法較VGrid-Scan算法的定位精度平均提高了1.15%；隨著柵格邊長的增大，三種算法的定位誤差就越接近，但SGrid-Scan算法的定位誤差始終最低。

錨節(jié)點(diǎn)密度影響鄰居錨節(jié)點(diǎn)個(gè)數(shù)，鄰居錨節(jié)點(diǎn)個(gè)數(shù)可以影響估計(jì)區(qū)域Ej的大小。在固定區(qū)域內(nèi)。設(shè)節(jié)點(diǎn)個(gè)數(shù)N=200，節(jié)點(diǎn)通信半徑r=20m，柵格邊長l=2m。

圖5   錨節(jié)點(diǎn)個(gè)數(shù)對(duì)算法定位誤差的影響

如圖5所示，三種算法的定位誤差均隨錨節(jié)點(diǎn)個(gè)數(shù)增加而逐步減小。SGrid-Scan算法的定位誤差較Grid-Scan算法平均減小了3.92%；SGrid-Scan算法較VGrid-Scan算法的定位精度平均提高了1.77%。

節(jié)點(diǎn)總數(shù)是衡量網(wǎng)絡(luò)密集度的一個(gè)重要參數(shù)，因此仿真了節(jié)點(diǎn)總數(shù)對(duì)兩種算法定位性能的影響。設(shè)節(jié)點(diǎn)通信半徑r=20m，錨節(jié)點(diǎn)個(gè)數(shù)為0.2N，柵格邊長l=2m。

圖6   節(jié)點(diǎn)個(gè)數(shù)對(duì)算法定位誤差的影響

如圖6所示，隨著節(jié)點(diǎn)個(gè)數(shù)的增多，網(wǎng)絡(luò)密集度隨之變大，三種算法的定位誤差均隨之減小。SGrid-Scan算法較傳統(tǒng)Grid-Scan算法的定位誤差平均減小了4.11%。當(dāng)節(jié)點(diǎn)個(gè)數(shù)N=150時(shí)，兩種算法定位精度的差值最大，為5.12%；SGrid-Scan算法較VGrid-Scan算法的定位精度平均提高了1.45%。

由Grid-Scan算法的定位原理可知，柵格的邊長會(huì)對(duì)估計(jì)區(qū)域Ej邊緣的柵格數(shù)量產(chǎn)生影響，從而影響Ej質(zhì)心的位置。設(shè)節(jié)點(diǎn)個(gè)數(shù)N=200，錨節(jié)點(diǎn)個(gè)數(shù)為40，節(jié)點(diǎn)的通信半徑r=20m。

圖7   柵格邊長對(duì)算法定位誤差的影響

如圖6所示，柵格邊長越小，三種算法的定位誤差越低，且SGrid-Scan算法的定位誤差較Grid-Scan算法平均減小了2.37%；SGrid-Scan算法較VGrid-Scan算法的定位精度平均提高了1.15%；隨著柵格邊長的增大，三種算法的定位誤差就越接近，但SGrid-Scan算法的定位誤差始終最低。

結(jié)束語文中首先采用傳統(tǒng)的Grid-Scan算法得到一個(gè)初始位置估計(jì)，然后通過對(duì)初始位置估計(jì)到最近錨節(jié)點(diǎn)位置的理論信號(hào)強(qiáng)度與未知節(jié)點(diǎn)到最近錨節(jié)點(diǎn)的信號(hào)強(qiáng)度進(jìn)行對(duì)比，判斷未知節(jié)點(diǎn)的可再定位性，再以最近錨節(jié)點(diǎn)到初始位置的距離為半徑對(duì)可再定位的未知節(jié)點(diǎn)進(jìn)行二次柵格掃描，從而進(jìn)一步縮小了未知節(jié)點(diǎn)的定位區(qū)域，一定程度上提高了定位精度。仿真結(jié)果表明，在變通信半徑、變錨節(jié)點(diǎn)個(gè)數(shù)、變節(jié)點(diǎn)個(gè)數(shù)和變柵格邊長的條件下，改進(jìn)算法均有效降低了平均相對(duì)定位誤差。

完整的Word格式文檔51黑下載地址：
二次柵格掃描的無線傳感器網(wǎng)絡(luò)定位算法.docx (265.47 KB, 下載次數(shù): 6)

2018-6-4 15:12 上傳

點(diǎn)擊文件名下載附件
定位算法.pdf
下載積分: 黑幣 -5