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

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

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

Grid-Scan算法分為3個步驟[15]：

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

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

圖1   外接估計矩形示意圖

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

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

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

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

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

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

(1)初始位置估計

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

(2)判斷可再定位性

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

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

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

(3)柵格二次賦值

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

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

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

圖3   二次柵格掃描示意圖

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

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

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

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

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

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

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

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

圖5   錨節(jié)點個數(shù)對算法定位誤差的影響

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

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

圖6   節(jié)點個數(shù)對算法定位誤差的影響

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

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

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

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

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

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

2018-6-4 15:12 上傳

點擊文件名下載附件
定位算法.pdf