基于限定域-蜂群的光纖物聯(lián)網(wǎng)節(jié)點(diǎn)定位算法研究*

吳瑞勇

(太原學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系，山西 太原030051)

物聯(lián)網(wǎng)(IoT，Internet of Things)[1]是互聯(lián)網(wǎng)在網(wǎng)絡(luò)空間與實(shí)物空間的拓展，其終端是各類可以實(shí)現(xiàn)數(shù)據(jù)交換的客戶端，電腦、手機(jī)、傳感器網(wǎng)絡(luò)等構(gòu)成物聯(lián)網(wǎng)的感知層[2-4]。 由于光纖傳感技術(shù)的日趨成熟，其泛在性和智能性的優(yōu)勢逐漸顯現(xiàn)出來，使光纖物聯(lián)網(wǎng)的構(gòu)建與應(yīng)用成為了新的研究熱點(diǎn)。

由于光纖物聯(lián)網(wǎng)中包含海量數(shù)據(jù)，所以對關(guān)鍵節(jié)點(diǎn)的選取與快速定位將直接影響整體網(wǎng)絡(luò)數(shù)據(jù)處理的性能，故節(jié)點(diǎn)定位算法的優(yōu)劣至關(guān)重要。 目前，主流的物聯(lián)網(wǎng)節(jié)點(diǎn)定位的算法包括粒子群優(yōu)化算法[5]、質(zhì)心定位算法[6]、 節(jié)點(diǎn)跟蹤算法等[7]。 粒子群優(yōu)化算法應(yīng)用最為常見，該算法定位精度較好、收斂速度較高，其針對具有較好先驗(yàn)知識的數(shù)據(jù)網(wǎng)絡(luò)有較高的適應(yīng)能力，但光纖傳感網(wǎng)絡(luò)作為感知層，其測試數(shù)據(jù)的不確定性十分明顯，與傳統(tǒng)物聯(lián)網(wǎng)網(wǎng)絡(luò)層節(jié)點(diǎn)的定位具有較大差異，故針對光纖感知層的定位效果不佳[8]；質(zhì)心定位算法適用于節(jié)點(diǎn)信噪比較高的網(wǎng)絡(luò)環(huán)境，其抗噪聲能力較差，而光纖物聯(lián)網(wǎng)感知層往往存在較大的噪聲，容易導(dǎo)致定位精度差、延時(shí)長的問題[9]；節(jié)點(diǎn)跟蹤算法原理簡單、易實(shí)現(xiàn)，但該方法主要適用于節(jié)點(diǎn)數(shù)較少的網(wǎng)絡(luò)，對大量節(jié)點(diǎn)構(gòu)成的光纖物聯(lián)網(wǎng)其收斂時(shí)間會大幅增加[10]。

綜合比較可知，在光纖物聯(lián)網(wǎng)中為了精確、快速地完成節(jié)點(diǎn)定位，最主要的需要解決兩個(gè)問題，一是提高定位精度，二是縮短收斂時(shí)間。 傳統(tǒng)方法中針對網(wǎng)絡(luò)層數(shù)據(jù)定位精度較高而對感知層定位精度較差的主要原因是初始域選取的邊界限定差異較大造成的，故本文算法在節(jié)點(diǎn)定位選取之前先計(jì)算合理的限定域，從而改善算法定位精度；尋優(yōu)算法采用蜂群算法，利用對蜜源的優(yōu)化設(shè)定實(shí)現(xiàn)大量數(shù)據(jù)節(jié)點(diǎn)迭代對收斂速度不敏感的目的，從而加快收斂速度。

1 光纖物聯(lián)網(wǎng)感知層分析

1.1 物聯(lián)網(wǎng)結(jié)構(gòu)

物聯(lián)網(wǎng)主要分為感知層、網(wǎng)絡(luò)層與應(yīng)用層[11]。感知層由各傳感器件構(gòu)成，用于數(shù)據(jù)獲取，網(wǎng)絡(luò)層用于傳輸與信息交互，應(yīng)用層是直接對管理平臺的，是智能管理的綜合輸出。 其總體結(jié)構(gòu)如圖1 所示。

圖1 物聯(lián)網(wǎng)整體結(jié)構(gòu)

感知層是本文光纖傳感網(wǎng)絡(luò)的重點(diǎn)研究對象，因?yàn)楣饫w傳感網(wǎng)絡(luò)分布在真實(shí)物理環(huán)境中的各個(gè)位置，當(dāng)存在異常數(shù)據(jù)或風(fēng)險(xiǎn)報(bào)警時(shí)，快速定位并排除障礙是保障網(wǎng)絡(luò)正常運(yùn)營的重要手段，結(jié)合感知層數(shù)據(jù)結(jié)構(gòu)特點(diǎn)分析了傳統(tǒng)算法精度低收斂速度慢的原因，針對感知層數(shù)據(jù)多樣性、隨機(jī)性等特點(diǎn)提出了限定域-蜂群算法。

1.2 數(shù)據(jù)特點(diǎn)分析及優(yōu)化思路

由于本系統(tǒng)針對的是光纖傳感網(wǎng)絡(luò)構(gòu)成的感知層，所以數(shù)據(jù)組成以檢測獲得的物理參量為主，溫度、應(yīng)變、濕度等信號都是隨環(huán)境而改變的。 感知層的數(shù)據(jù)是動態(tài)變化的，參數(shù)多、數(shù)據(jù)量大，屬于多維問題優(yōu)化范疇，由此可見，需要完成多變量的優(yōu)化，相比粒子群算法、遺傳算法以及蟻群算法而言，人工蜂群算法(ABC，Artificial Bee Colony algorithm)等具有更好的全局尋優(yōu)特性。

在物聯(lián)網(wǎng)中節(jié)點(diǎn)位置的確定需要依靠信標(biāo)節(jié)點(diǎn)的選取，而信標(biāo)節(jié)點(diǎn)選取的優(yōu)劣直接影響定位精度及運(yùn)算時(shí)間，由于感知層數(shù)據(jù)的隨機(jī)性使在選擇分類數(shù)據(jù)過程中不能單純地依靠先驗(yàn)知識或者某種固定規(guī)律完成判別，這也是傳統(tǒng)定位算法定位精度低、收斂速度慢的主要原因。 傳統(tǒng)方法中常采用3 邊定位法實(shí)現(xiàn)，當(dāng)選擇區(qū)域?yàn)閳A形時(shí)，定位精度高但運(yùn)算量很大，容易造成搜索延遲過長的問題；當(dāng)選擇區(qū)域?yàn)檎叫螘r(shí)，由行列位置計(jì)算，速度快，但定位精度較差。 故在本算法中引入限定域?qū)π艠?biāo)節(jié)點(diǎn)進(jìn)行初篩，從而在保證定位精度的基礎(chǔ)上大幅縮短收斂時(shí)間。 本文在人工蜂群算法的基礎(chǔ)上進(jìn)行了優(yōu)化改進(jìn)，通過限定搜索范圍提高方形區(qū)域的定位精度，從而提出了基于限定域-蜂群定位算法(LD-BC algorithm，Limited Domain-Bee Colony algorithm)。

2 限定域-蜂群算法設(shè)計(jì)

2.1 人工蜂群算法

人工蜂群算法[12-14]是通過模擬蜜蜂采蜜行為的大數(shù)據(jù)優(yōu)化算法，其由蜜源、雇傭蜂和非雇傭蜂組成。 蜜源即待測節(jié)點(diǎn)位置的最優(yōu)解，由數(shù)據(jù)適應(yīng)度判別解的優(yōu)劣。 雇傭蜂與蜜源位置匹配，通過預(yù)設(shè)概率將信息傳遞給跟隨蜂(預(yù)測概率是關(guān)于適應(yīng)度的函數(shù))。 非雇傭蜂由跟隨蜂和偵査蜂構(gòu)成，跟隨蜂根據(jù)雇傭蜂的信息選擇蜜源，偵查蜂在實(shí)時(shí)更新的數(shù)據(jù)中尋找新蜜源，完成貪婪選擇。 若蜜源指標(biāo)持續(xù)降低，將對應(yīng)該蜜源的雇傭蜂改為領(lǐng)蜂變成偵査蜂，偵查蜂尋找新的食物源代替原來的食物源。

設(shè)蜜源i(i＝1，2，…，N)的質(zhì)量適應(yīng)度為fiti，N表示蜜源數(shù)。 若確定光纖物聯(lián)網(wǎng)中待求節(jié)點(diǎn)問題的維度是D，當(dāng)?shù)鷗 次后蜜源位置為Xi＝[xi1，xi2，…，xiD]，xid∈(Ld，Ud)，其中Ld和Ud為搜尋范圍的上、下限(d ＝1，2，…，D)。 搜索范圍為:

開始搜索后，引領(lǐng)蜂在蜜源位置周邊搜索新蜜源，依據(jù)路徑有

式中:j 為蜜源N 中的另一個(gè)蜜源。 φ∈[-1，1]，其為擾動程度。

當(dāng)新蜜源Vi對應(yīng)的適應(yīng)度比原有蜜源更好時(shí)，利用貪婪選擇方法替換原蜜，否則保留原蜜源，引領(lǐng)蜂循環(huán)完成式(2)計(jì)算后，共享蜜源信息。

跟隨蜂分享蜜源信息依據(jù)概率跟隨，跟隨依據(jù)有

2.2 設(shè)定限定域

限定域的設(shè)定采用非測距的方式完成，通過限定邊界范圍完成對未知節(jié)點(diǎn)范圍的限制。 當(dāng)未知節(jié)點(diǎn)到測量的工作距離小于通信半徑時(shí)，其一定在通信半徑圓的外切矩形內(nèi)。 同時(shí)，當(dāng)兩個(gè)以上的測試節(jié)點(diǎn)就能夠?qū)⑽粗?jié)點(diǎn)限定在一個(gè)相交的矩形重疊區(qū)中。 由于是矩形區(qū)域所以數(shù)據(jù)處理要比傳統(tǒng)圓形區(qū)域要簡單很多，同時(shí)，由于其是多個(gè)矩形重疊區(qū)，則能夠保證區(qū)域尺寸不大，對測試精度影響小。 基于此思想，實(shí)現(xiàn)大幅降低運(yùn)算量并保證較好的定位精度。

限定域區(qū)間為B1A2B3A4，則其數(shù)據(jù)集合為

圖2 限定域區(qū)間

2.3 限定域-蜂群算法

采用人工蜂群算法中需要尋找合適的蜜源，而在光纖物聯(lián)網(wǎng)的龐大數(shù)據(jù)中偵查蜂搜索半徑的設(shè)置直接影響了蜜源尋找速度及是否是局部最優(yōu)值。 但光纖物聯(lián)網(wǎng)數(shù)據(jù)中存在數(shù)據(jù)特征的一致性，即相同傳感網(wǎng)絡(luò)中異常數(shù)據(jù)類型具有數(shù)據(jù)特征的一致性，同時(shí)，對于同屬性網(wǎng)絡(luò)區(qū)域都具有相似性，即其測試節(jié)點(diǎn)范圍相近，故在已知網(wǎng)絡(luò)的條件下完全可以通過設(shè)置合適的限定域限制偵查蜂的搜索范圍，以重疊矩形作為限定區(qū)域，運(yùn)算速度快，定位精度高，適用于光纖網(wǎng)聯(lián)網(wǎng)的海量數(shù)據(jù)處理。 算法步驟如下，實(shí)現(xiàn)流程如圖3 所示。

圖3 限定域-蜂群算法流程圖

(1)初始化種群，引領(lǐng)蜂按照式(1)尋找蜜源Xi，計(jì)算適應(yīng)值；

(2)采用貪婪算法優(yōu)化蜜源；

(3)由式(3)求解跟隨蜂選擇Xi的概率；

(4)跟隨蜂根據(jù)閾值分離出新的引領(lǐng)蜂，而新產(chǎn)生的引領(lǐng)蜂根據(jù)式(5)的限定域范圍Ki確定新蜜源Vi，并再次采用貪婪算法優(yōu)化蜜源；

(5)判斷蜜源質(zhì)量，若放棄蜜源則將引領(lǐng)蜂變成偵查蜂執(zhí)行式(1)重新搜索；

(6)標(biāo)記最好的蜜源與終止條件對比，若成立輸出最優(yōu)解，若不成立循環(huán)。

2.4 時(shí)間復(fù)雜度分析

為了通過時(shí)間復(fù)雜度描述算法性能，需要分析算法各個(gè)步驟的耗時(shí)情況。 由算法流程圖可以看出，主程序中屬于高階耗時(shí)類型的循環(huán)指令有兩個(gè)，但其中遺棄蜜源的循環(huán)并不是全數(shù)據(jù)循環(huán)，而只是針對少量舍棄蜜源的操作(小于數(shù)據(jù)總量的10%)，故其仍屬于低階復(fù)雜度，設(shè)一個(gè)for 循環(huán)的時(shí)間復(fù)雜度為O(n)，則算法時(shí)間復(fù)雜度T(n)有

式中:Θ 表示去掉常數(shù)項(xiàng)、低階項(xiàng)以及高階項(xiàng)中的常系數(shù)，包含的四項(xiàng)分別是全數(shù)據(jù)for 循環(huán)項(xiàng)、k 參數(shù)下的限定域數(shù)據(jù)索引、舍棄蜜源嵌套循環(huán)項(xiàng)及最優(yōu)解輸出項(xiàng)；k 為參數(shù)，k∈(0，1)。 由此可見，相比傳統(tǒng)算法中數(shù)據(jù)與優(yōu)化兩個(gè)遍歷過程而言(即T(n)＞n2)，具有更好的性能。

3 實(shí)驗(yàn)

3.1 實(shí)驗(yàn)條件

為了驗(yàn)證本算法的定位精度及速度， 在MATLAB 7.0 環(huán)境中對模擬物聯(lián)網(wǎng)數(shù)據(jù)進(jìn)行測試分析。 設(shè)所有節(jié)點(diǎn)的(x，y)坐標(biāo)范圍取值區(qū)間為(0，0)((1 000，1 000)，共計(jì)106個(gè)點(diǎn)(對應(yīng)于100 m×100 m 范圍內(nèi)定位精度0.1 m 的設(shè)計(jì)要求)。 算法適應(yīng)度設(shè)置為0.4，限定域矩陣尺寸為50×50。 已知節(jié)點(diǎn)個(gè)數(shù)設(shè)置為25，在此基礎(chǔ)上設(shè)該區(qū)域內(nèi)有一個(gè)未知節(jié)點(diǎn)Vi，然后對該節(jié)點(diǎn)進(jìn)行定位計(jì)算。 同時(shí)，對比算法采用粒子群算法(POS，Particle Swarm Optimization)、人工蜂群算法(ABC)和本算法(LDBC)。 針對模擬條件，POS 的初始慣性權(quán)重和結(jié)束慣性權(quán)重分別設(shè)置為0.9 和0.5；ABC 的搜索范圍設(shè)置為(0，0)到(100，100)，fi設(shè)置為0.4。

實(shí)驗(yàn)數(shù)據(jù)重復(fù)運(yùn)行1 000 次后計(jì)算平均誤差形成實(shí)驗(yàn)數(shù)據(jù)的對比值，從而評判算法的優(yōu)劣，絕對定位誤差有

式中:(x，y)為算法定位結(jié)果，(xr，yr)為節(jié)點(diǎn)的真實(shí)值。 當(dāng)di越小時(shí)定位精度越高。 分別從參考節(jié)點(diǎn)數(shù)、種群規(guī)模和收斂速度3 個(gè)方面對比了以上3 種算法。

3.2 穩(wěn)定性分析

在預(yù)設(shè)范圍(100 m，100 m)中，通過增加待測節(jié)點(diǎn)數(shù)分析不同算法的定位精度，仿真結(jié)果如圖4所示。

圖4 不同參考節(jié)點(diǎn)數(shù)的驗(yàn)算誤差

由仿真數(shù)據(jù)可知，LD-BC 算法、ABC 算法和POS 算法的定位誤差限分別為(2.1 m，2.5 m)、(2.6 m，3.3 m)和(3.2 m，3.7 m)，可見隨著測試節(jié)點(diǎn)數(shù)量的增多對定位精度影響不大，故從提高收斂速度的角度，應(yīng)盡量減小參考節(jié)點(diǎn)數(shù)，即通常情況下3 種算法均采用三點(diǎn)定位，僅當(dāng)3 個(gè)參考節(jié)點(diǎn)絕對距離和小于新蜜源判別依據(jù)時(shí)增加參考節(jié)點(diǎn)數(shù)。 由3 組定位誤差限的上下限差值(0.4 m、0.7 m、0.5 m)可知，本算法區(qū)間最小，穩(wěn)定性最好。

3.3 定位精度分析

在參考節(jié)點(diǎn)數(shù)確定的基礎(chǔ)上，種群規(guī)模對定位精度的影響最大，故仿真分析不同種群規(guī)模之間定位精度的差異對分析算法的有效性十分必要。 以迭代次數(shù)100 為例，種群規(guī)模影響規(guī)律如圖5 所示。

圖5 3 種算法定位精度對比

如圖5 所示，隨著種群數(shù)的增多，定位精度會明顯提升，當(dāng)種群數(shù)超過18 以后，定位精度基本保持不變，LD-BC 算法、ABC 算法和POS 算法的平均定位精度分別是2.3 m、3.1 m 和3.4 m。 相比之下，本算法具有更高的定位精度。

3.4 收斂性能分析

設(shè)參考節(jié)點(diǎn)為3，種群數(shù)為18，迭代上限100次。 比較3 種算法的收斂性能，計(jì)算結(jié)果如圖6所示。

由圖6 可知，LD-BC 算法、ABC 算法和POS 算法分別在12 次、15 次和41 次迭代后趨于穩(wěn)定，由此可見，本算法的耗時(shí)成本最小。 而穩(wěn)定后的定位精度與定位誤差限仿真結(jié)果一致。 結(jié)合3.2 節(jié)和3.3 節(jié)的仿真分析結(jié)果可知，本算法定位精度高、收斂速度快、穩(wěn)定性好。

圖6 不同參考節(jié)點(diǎn)數(shù)的驗(yàn)算誤差

4 結(jié)論

針對物聯(lián)網(wǎng)中光纖感知層具有參數(shù)多、數(shù)據(jù)量大等特點(diǎn)，研究了傳統(tǒng)網(wǎng)絡(luò)節(jié)點(diǎn)定位技術(shù)精度低、速度慢的成因，提出了更具針對性的節(jié)點(diǎn)定位算法。限定域-蜂群算法利用矩形限定域的手段提高了節(jié)點(diǎn)定位精度。 實(shí)驗(yàn)從參考節(jié)點(diǎn)數(shù)、種群數(shù)及迭代次數(shù)等方面進(jìn)行數(shù)據(jù)對比，結(jié)果顯示，本算法在穩(wěn)定性、定位精度及收斂速度方面均有一定提高，具有一定的應(yīng)用價(jià)值。