基于限定域-蜂群的光纖物聯網節點定位算法研究*

吳瑞勇

(太原學院計算機科學與技術系，山西 太原030051)

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

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

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

1 光纖物聯網感知層分析

1.1 物聯網結構

物聯網主要分為感知層、網絡層與應用層[11]。感知層由各傳感器件構成，用于數據獲取，網絡層用于傳輸與信息交互，應用層是直接對管理平臺的，是智能管理的綜合輸出。 其總體結構如圖1 所示。

圖1 物聯網整體結構

感知層是本文光纖傳感網絡的重點研究對象，因為光纖傳感網絡分布在真實物理環境中的各個位置，當存在異常數據或風險報警時，快速定位并排除障礙是保障網絡正常運營的重要手段，結合感知層數據結構特點分析了傳統算法精度低收斂速度慢的原因，針對感知層數據多樣性、隨機性等特點提出了限定域-蜂群算法。

1.2 數據特點分析及優化思路

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

在物聯網中節點位置的確定需要依靠信標節點的選取，而信標節點選取的優劣直接影響定位精度及運算時間，由于感知層數據的隨機性使在選擇分類數據過程中不能單純地依靠先驗知識或者某種固定規律完成判別，這也是傳統定位算法定位精度低、收斂速度慢的主要原因。 傳統方法中常采用3 邊定位法實現，當選擇區域為圓形時，定位精度高但運算量很大，容易造成搜索延遲過長的問題；當選擇區域為正方形時，由行列位置計算，速度快，但定位精度較差。 故在本算法中引入限定域對信標節點進行初篩，從而在保證定位精度的基礎上大幅縮短收斂時間。 本文在人工蜂群算法的基礎上進行了優化改進，通過限定搜索范圍提高方形區域的定位精度，從而提出了基于限定域-蜂群定位算法(LD-BC algorithm，Limited Domain-Bee Colony algorithm)。

2 限定域-蜂群算法設計

2.1 人工蜂群算法

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

設蜜源i(i＝1，2，…，N)的質量適應度為fiti，N表示蜜源數。 若確定光纖物聯網中待求節點問題的維度是D，當迭代t 次后蜜源位置為Xi＝[xi1，xi2，…，xiD]，xid∈(Ld，Ud)，其中Ld和Ud為搜尋范圍的上、下限(d ＝1，2，…，D)。 搜索范圍為:

開始搜索后，引領蜂在蜜源位置周邊搜索新蜜源，依據路徑有

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

當新蜜源Vi對應的適應度比原有蜜源更好時，利用貪婪選擇方法替換原蜜，否則保留原蜜源，引領蜂循環完成式(2)計算后，共享蜜源信息。

跟隨蜂分享蜜源信息依據概率跟隨，跟隨依據有

2.2 設定限定域

限定域的設定采用非測距的方式完成，通過限定邊界范圍完成對未知節點范圍的限制。 當未知節點到測量的工作距離小于通信半徑時，其一定在通信半徑圓的外切矩形內。 同時，當兩個以上的測試節點就能夠將未知節點限定在一個相交的矩形重疊區中。 由于是矩形區域所以數據處理要比傳統圓形區域要簡單很多，同時，由于其是多個矩形重疊區，則能夠保證區域尺寸不大，對測試精度影響小。 基于此思想，實現大幅降低運算量并保證較好的定位精度。

限定域區間為B1A2B3A4，則其數據集合為

圖2 限定域區間

2.3 限定域-蜂群算法

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

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

(1)初始化種群，引領蜂按照式(1)尋找蜜源Xi，計算適應值；

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

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

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

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

(6)標記最好的蜜源與終止條件對比，若成立輸出最優解，若不成立循環。

2.4 時間復雜度分析

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

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

3 實驗

3.1 實驗條件

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

實驗數據重復運行1 000 次后計算平均誤差形成實驗數據的對比值，從而評判算法的優劣，絕對定位誤差有

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

3.2 穩定性分析

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

圖4 不同參考節點數的驗算誤差

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

3.3 定位精度分析

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

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

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

3.4 收斂性能分析

設參考節點為3，種群數為18，迭代上限100次。 比較3 種算法的收斂性能，計算結果如圖6所示。

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

圖6 不同參考節點數的驗算誤差

4 結論

針對物聯網中光纖感知層具有參數多、數據量大等特點，研究了傳統網絡節點定位技術精度低、速度慢的成因，提出了更具針對性的節點定位算法。限定域-蜂群算法利用矩形限定域的手段提高了節點定位精度。 實驗從參考節點數、種群數及迭代次數等方面進行數據對比，結果顯示，本算法在穩定性、定位精度及收斂速度方面均有一定提高，具有一定的應用價值。