物聯(lián)網(wǎng)中異常通信情形下目標跟蹤算法的設(shè)計?

余 庚 張 潔

（1福建工程學(xué)院國脈信息學(xué)院·互聯(lián)網(wǎng)經(jīng)貿(mào)學(xué)院 福州 350007）

（2.福州理工學(xué)院 福州 350506）（3.福建農(nóng)業(yè)職業(yè)技術(shù)學(xué)院 福州 350007）

1 引言

傳感網(wǎng)作為一種高效的模糊物聯(lián)網(wǎng)絡(luò)［1］，因網(wǎng)中節(jié)點間信息關(guān)聯(lián)性帶來的定位評估優(yōu)勢而廣受歡迎。目前關(guān)于該網(wǎng)絡(luò)［2］的各類研究也多數(shù)是圍繞定位評估精度來開展。就目前而言，常見的研究有兩大類，分別是測距/非測距算法。關(guān)于測距的應(yīng)用研究中，算法要求事先精確地評估出已知節(jié)點和未知目標節(jié)點之間的間距方可計算出待測目標的信息域。而關(guān)于非測距的研究方案，則僅需通過GPS裝置廣播出已知節(jié)點自身的方位即可分析出待測目標的信息域。相比之下，無論從能耗、時效、計算復(fù)雜度而言，后者非測距研究方案更能引起人們的關(guān)注。

當(dāng)前，有關(guān)非測距的評估研究主旨思想［3］是通過將跳數(shù)范圍內(nèi)跳距做平均處理，然后將該平均跳距和跳數(shù)相乘值直接寫入信息域作為已知節(jié)點和待測目標節(jié)點的實際距離。再由此獲得待測目標節(jié)點的方位信息。然而這樣的研究對已知節(jié)點的規(guī)模、網(wǎng)絡(luò)節(jié)點密度均衡［4］度等網(wǎng)絡(luò)狀態(tài)依賴程度較高。并且在一定程度上精確度和通信范圍內(nèi)的跳數(shù)呈反比。顯然這樣的情形在現(xiàn)實網(wǎng)絡(luò)布局中具有較大偶然性?；诖?，本文構(gòu)思在全局節(jié)點分布和通信半徑范圍內(nèi)跳數(shù)無法預(yù)測的模糊物聯(lián)網(wǎng)絡(luò)中，開展異常目標節(jié)點評估的跟蹤算法。

2 非測距評估的局限性

實施非測距評估方案的目的是通過向全網(wǎng)其他節(jié)點廣播［5］彼此的信息域來獲得跳數(shù)值，并求得平均跳距。以此推算出錨節(jié)點和待測目標節(jié)點的長度，進而跟蹤鎖定異常目標的方位。

整個評估方案的實施過程如下：1）初始化全網(wǎng)。為錨節(jié)點i分配含有方位和跳數(shù)的信息域，并將Ti初始為零；2）將信息域廣播至全網(wǎng)，使全網(wǎng)節(jié)點存儲最優(yōu)信息域。對于每一個接收節(jié)點而言，每收到上游節(jié)點廣播的信息域計數(shù)器均需為Ti執(zhí)行一次加1操作。當(dāng)該節(jié)點收到相同的上游節(jié)點廣播來的信息域時，首先判斷新信息域和舊信息域中的Ti值。如果新信息域中的Ti更大，新信息域被丟棄；反之，新信息域?qū)⒏采w該節(jié)點內(nèi)存中的舊信息域。隨后將信息域再次廣播至下游站。3）測算信標節(jié)點跳距均值。其中tij表示兩個信標節(jié)點之間的跳數(shù)。4）測算待測目標和信標間距。獲取目標的信息域。

根據(jù)上述分析，非測距評估過程對于信標比例和信標分布［6］的偏好度較高。若要顯著提高待測目標和信標間距的準確度，無疑要求信標數(shù)量不但要多且部署的密度務(wù)必要均衡。然而在實際應(yīng)用中，由于成本和環(huán)境等因素局限使得所部署的節(jié)點只有少部分載有GPS裝置，且分布毫無規(guī)律可言。為了進一步提高評估在模糊物聯(lián)網(wǎng)絡(luò)中的實用性和可行性，需建立一個目標跟蹤評估算法。

3 目標跟蹤算法思想

3.1 優(yōu)化信息域

鑒于節(jié)點分布不均衡引發(fā)了被廣播的信息域中，跳數(shù)誤差較大的問題。目標跟蹤評估［7］算法通過分布式擴大廣播區(qū)域的方式來優(yōu)化信息域。廣播信息域之前先將廣播的最大半徑R分為m個層次，錨節(jié)點依次按照1/m，2/m，...，m/m的半徑向信宿廣播信息域，并記錄信宿節(jié)點和信源節(jié)點的跳數(shù)1/m，2/m，...，m/m。在結(jié)束第一次廣播并開始第二次廣播時，信宿節(jié)點讀取內(nèi)存確認是否曾經(jīng)保存過該信源信標信息域的跳數(shù)。如果保存過，則丟棄該信息域，并將內(nèi)存中既有的信息域轉(zhuǎn)發(fā)給下游站。反之，保存將該信息域并記錄跳數(shù)2/m。依次循環(huán)直至第z次（1＜z≤m）廣播，使得所有信宿節(jié)點均精確地獲得與信標間的最小跳數(shù)t，進而優(yōu)化信息域。令錨節(jié)點i和周邊節(jié)點n的物理長度為Lin，廣播過程中信息域內(nèi)的跳數(shù)模型［8］遵循：

可知，所求得信息域中的最小跳數(shù)值不再取整。顯然優(yōu)化［9］后的信息域在一定程度上精確地量化了信標與目標間的重要參數(shù)。

3.2 優(yōu)化間距

非測距研究方案對全局網(wǎng)絡(luò)節(jié)點的密度［10］均衡性較為依賴。這不利于客觀地評估未知節(jié)點和信標節(jié)點的間距。假設(shè)待測模糊物聯(lián)網(wǎng)絡(luò)現(xiàn)有兩個GPS裝置的錨節(jié)點m1和m2。m1和m2連線的物 理［11］長 度LWm1-m2為 36m，其 他 未 知 節(jié) 點uk(k≤5)間的物理間距依次是：LWm1-u1=2m，LWu1-u2=4m，LWu2-u3=6m，LWu3-u4=8m，LWu4-u5=10m，LWu5-m2=12m；當(dāng)m1的廣播半徑為36m時，可知m1和m2僅一跳。此時算法將這一跳所對應(yīng)的36m直接視為m1和u1的評估距離，然而事實上LWm1-u1=2m；當(dāng)m1的廣播半徑為3m時，由于通信范圍太小使得m1必須先廣播信息域至m2，再由m2廣播給下一站，以此類推直至廣播到m2。廣播過程共發(fā)生6跳。此時算法將記錄的42m平均化，算得每跳的評估距離為7m，這也就作為m1和u1的評估距離來使用。相對于m1和u1的實際距離2m，該評估距離誤差較小。根據(jù)上述描述可知，此類評估間距的精度［12］隨模糊物聯(lián)網(wǎng)絡(luò)節(jié)點密度復(fù)雜性增加而急劇下降。

為優(yōu)化間距評估方案，目標跟蹤評估算法在權(quán)衡間距時做加權(quán)處理。權(quán)值指數(shù)σi表征為進而估算［13］出權(quán)值間距：

同時為了消除模糊物聯(lián)網(wǎng)絡(luò)節(jié)點部署的隨機性給目標跟蹤評估算法帶來的干擾，增設(shè)一個隨機因子，表征為

據(jù)此計算出錨節(jié)點和待測目標的評估距離：

4 目標跟蹤算法實施

根據(jù)目標跟蹤算法思想描述可知，目標能否被精確地跟蹤評估的關(guān)鍵在于跳數(shù)和節(jié)點間距的權(quán)衡。為使評估更加客觀地接近物理參數(shù)值，本文構(gòu)思的算法在計算跳數(shù)和間距期間分別引入多層次廣播、權(quán)值、隨機因子等環(huán)節(jié)。算法實施于模糊網(wǎng)絡(luò)中開展分布式過程如下：

1）全局初始化。將載有GPS的已知節(jié)點信息域初始化為D(Xi，Yi，Ti)，并賦跳數(shù)零值。

2）廣播信息域。已經(jīng)節(jié)點首次向周邊節(jié)點發(fā)起廣播，信宿節(jié)點將信息域?qū)懭雰?nèi)存。隨后發(fā)起第二次全局廣播，若信宿節(jié)點已接收過信息域，將跳數(shù)記作1；若沒有接收過，則保持1/m。以此類推，發(fā)起第m次全局廣播，若信宿節(jié)點已接收過信息域，將跳數(shù)記作3/m...1；若沒有接收過，則保持原跳數(shù)參數(shù)不變。直至全局信宿均獲得包含與信標節(jié)點間最小跳數(shù)在內(nèi)的最優(yōu)信息域D'(Xi，Yi，t)。

3）優(yōu)化權(quán)值間距。通過計算每個已知節(jié)點跳距均值、權(quán)值指數(shù)σi求取權(quán)值間距。

4）優(yōu)化已知節(jié)點和待測目標的距離。通過計算隨機因子Siu，進一步算得評估距離Liu'。

5）獲得目標方位。

5 目標跟蹤算法測試

5.1 測試模型

為了客觀地測評［14］所設(shè)計的目標跟蹤算法，本次借助仿真平臺搭建模糊物聯(lián)網(wǎng)絡(luò)模擬環(huán)境展開相關(guān)指標測試。測試模型［15］部署如下：1）在面積為100m×100m的待測區(qū)域內(nèi)隨機撒布25個載有GPS裝置的錨節(jié)點和75個普通節(jié)點；2）測試過程通過變換節(jié)點廣播半徑來評價通信范圍與目標跟蹤算法的關(guān)聯(lián)度；3）為使模擬環(huán)境高度接近模糊物聯(lián)網(wǎng)絡(luò)特征，測試在每一次結(jié)束后均需重新隨機撒布這個25個錨節(jié)點和75個普通節(jié)點；4）為了避免測試數(shù)據(jù)的偶然性，每組測試均在300次仿真［16］后開展數(shù)據(jù)收集和對比。5）假設(shè)全局節(jié)點規(guī)模為N個，其中待測目標節(jié)點的實際方位和算法評估方位分別為 (Xs，Ys)，(Xp，Yp)。本次測試引入偏差因子用于分析目標跟蹤算法的可行性，表示為

5.2 測試分析

在Matlab平臺上將100個已經(jīng)/未知節(jié)點隨機部署在如圖1所示的網(wǎng)絡(luò)中，預(yù)置廣播半徑25m?；疑翘柡蜕詈谏切畏謩e代表錨節(jié)點和普通節(jié)點。圖中可見，兩種類型的節(jié)點分布毫無規(guī)律。同時存在錨節(jié)點附近密度很低以及目標節(jié)點附近未有錨節(jié)點的情形。對于非測距評估研究方案而言，這樣的情形也恰恰造成了評估的嚴重偏差。

圖1 模糊物聯(lián)網(wǎng)絡(luò)布局

圖2 錨節(jié)點規(guī)模對算法的影響力

由非測距評估的局限性和目標跟蹤算法思想的描述可知，目標節(jié)點方位的評估在很大程度上依賴于載有GPS的已知節(jié)點規(guī)模。當(dāng)已知節(jié)點規(guī)模越大，向全局節(jié)點廣播的信息域越精確，計算所得數(shù)據(jù)越可靠，則評估結(jié)果也就越客觀。這樣的特征在圖2所示的兩種算法曲線走勢圖中均有所體現(xiàn)。該圖描述了在預(yù)置的25m廣播半徑內(nèi)錨節(jié)點規(guī)模對算法的影響力。圖中不難看出，兩種算法均隨著錨節(jié)點數(shù)量不斷增加，算法評估目標方位的偏差［17］因子總體顯著下降。但受限于非測距評估方案對全局節(jié)點密度的偏好，而本文所設(shè)計的目標跟蹤算法在通信機制上采用分布式廣播，且將模糊物聯(lián)網(wǎng)絡(luò)隨機特征對計算的干擾納入考慮范圍，同時目標節(jié)點可提取到較為可靠的最小跳數(shù)信息。因此相對于前者，目標跟蹤算法在評估偏差因子方面的表現(xiàn)較有優(yōu)勢。

圖3 分布式廣播對算法的貢獻度

目標跟蹤算法的優(yōu)勢之一是采用分布式廣播機制。通過在通信半徑范圍內(nèi)開展分布式廣播有助于全網(wǎng)節(jié)點接收到優(yōu)化信息域，尤其是跳數(shù)參數(shù)的最小化對目標方位計算具有良好的貢獻度。這樣的優(yōu)勢在圖3所示的分布式廣播對算法貢獻度中同樣得到了詮釋。圖3所示為在預(yù)置的25m廣播半徑內(nèi)，變換不同的半徑層次m來考察目標跟蹤算法的分布式廣播對算法的貢獻度。顯而易見，半徑層次越多，分布式廣播越頻繁，越有益于凈化［18］全網(wǎng)節(jié)點收集到的信息域，尤其是優(yōu)化的跳數(shù)參數(shù)對評估的精度起了至關(guān)重要的影響，可顯著降低算法的偏差因子。正如圖3中的第四條曲線1/5，所對應(yīng)的偏差因子最低。

如目標跟蹤算法思想所述，通信半徑的擴大將伴隨著跳數(shù)和跳距的模糊化。這是由于在錨節(jié)點規(guī)模固定的前提下，當(dāng)廣播半徑范圍增加，通信范圍內(nèi)錨節(jié)點比例下降，節(jié)點布局越加隨機化。由此帶來權(quán)值間距和隨機因子計算的波動，不可避免地降低算法的精度。為了驗證廣播半徑變化和目標跟蹤算法計算偏差的關(guān)聯(lián)度，本項測試統(tǒng)一選用5個層次的廣播機制。如圖4所示的曲線走勢圖表明，在相同數(shù)量錨節(jié)點的前提下，偏差因子和半徑呈現(xiàn)正比關(guān)系。當(dāng)半徑從25m增至30m，目標跟蹤算法的偏差因子總體呈現(xiàn)上升趨勢。

圖4 廣播半徑和目標跟蹤算法偏差的關(guān)聯(lián)度

6 結(jié)語

本文通過分析非測距評估方案在復(fù)雜網(wǎng)絡(luò)中應(yīng)用的局限性，提出一種在節(jié)點布局隨機和信標比例較低的模糊物聯(lián)網(wǎng)絡(luò)中開展目標跟蹤評估的算法。該算法運用分布式廣播機制為全局節(jié)點傳播可靠的跳數(shù)和跳距信息，進而推測出QoS異常的目標節(jié)點方位。同時，通過一系列指標考察算法實施的性能。最終驗證了目標評估算法在模糊物聯(lián)網(wǎng)絡(luò)中具備可行性。