無線傳感網絡節點Amorphous-GA搜索定位算法及性能分析

王偉萍

關鍵詞：無線傳感網絡；節點定位；遺傳算法；通信半徑

0引言

在無線通信技術不斷革新的進程中，科技飛速發展，近距離無線組網及低功耗技術發揮的作用越來越大，推動了社會經濟發展。在定位節點時，根據是否需要進行節點距離測試，定位算法被劃分為兩種：無距離測試和有距離測試。在完成定位運算的過程中，硬件性能需要達到一定標準，但這樣會導致成本大幅增加，因此有必要探究如何高效率完成定位運算。

由于通信半徑每跳距離的偏差過大，因此選取不定形（Amorphous）算法對定位誤差的差異性進行重點探討。為保證Amorphous算法定位狀態的精確度更高，依次處理并優化了節點總數、通信半徑及錨節點數量等參數。通過Amorphous算法可降低定位誤差，但實用性不高。胡偉等提出基于Amorphous算法的遺傳一禁忌搜索算法（improvedamorphous genetic-algorithm tabu-search location，IAmorphous-GATS），利用遺傳禁忌搜索算法優化初始解得到未知節點的最優位置，提高了未知節點的定位精度。宋海聲等在利用Amorphous算法離線計算網絡平均連通度的基礎上，建立了閾值模型來降低Amorphous算法在不同通信模型下的定位誤差。

本文在遺傳算法（genetic algorithm，GA）搜索定位基礎上結合AmorDhous算法，設計了一種無線傳感網絡節點Amorphous-GA搜索定位算法，并對其開展性能分析。

1Amorphous-GA搜索定位算法

1.1Amorphous算法改進

在應用Amorphous算法的過程中無須測試距離，未知節點方位可通過節點之間的最低跳數進行估算。具體操作流程為：先計算節點與未知節點間的最小跳數，之后通過錨節點向無線傳感網絡的鄰居節點傳輸跳數。

在應用Amorphous算法時，以節點距離為計算結果，在運算未知節點間位置的過程中容易產生較大誤差。例如，0節點通信范圍內同時存在P、Q兩個節點，同時QO與PO不同，兩個節點距O節點的距離差距較大。這種情況下通常會作為一跳完成計算，默認QO與PO的數值相等。在無線傳感網絡運行中也會產生此類問題。本文對Amorphous算法進行了改進。按照強度不同將信號劃分為多個區間，然后對特定節點信號強度進行測試。該過程需要在40～80dBm內劃分信號強度區間，然后分別用0.8、1設定40～50dBm、50～60dBm內的跳數，該方法同樣適用于其他情況。

1.2Amorphous-GA搜索定位算法

搜索優化時采取GA方式，同時按照兩個流程實施Amorphous算法：先計算未知節點的初始值；按照人工智能算法優化前期獲取的初始解。Amorphous-GA搜索定位算法流程如圖1所示。首先，利用Amorphous算法并結合錨節點坐標獲取未知節點坐標，節點數據為GA最初輸入值。其次，GA是否終止通過初始坐標適應度進行判斷。滿足終止條件后立即輸出結果，不符合則按后續處理流程對結果進行選擇與交叉操作。最后，根據輸出結果形成候選集，分析藐視準則是否符合情況。在滿足藐視準則的情況下，禁忌表立即完成更新，用當前解代替最優解；若不滿足則需細致分析候選解的屬性，同時將當前解用包含非禁忌對象的解代替，更新禁忌表。按上述流程完成處理后，再判斷結果是否滿足GA終止條件。若滿足則返回到上一步；若不滿足則采取循環處理方式，直至滿足終止條件。

2仿真分析

2.1仿真環境

為了驗證本文算法在實際操作中的應用效果，利用MATLAB軟件對本文算法在實際操作過程中的運行效果進行驗證，重點仿真測試Amorphous-GA搜索定位算法。迭代運算次數共100次，禁忌表長度與交叉概率的數值分別為10和0.6。使用歸一化定位誤差比較不同算法的定位性能。

2.2仿真實驗與分析

在不同錨節點比例的條件下，對不同算法的性能展開測試，控制節點總數為100個，覆蓋的通信半徑為30mo不同通信半徑下的算法性能變化如圖2所示，在錨節點比例增加后定位誤差大幅降低，定位精度得到顯著提升。設置錨節點比例大于30%時，能夠獲得較小的定位誤差，之后趨于穩定。在錨節點比例增長的條件下，未知節點與錨節點間的跳數降低，導致不同節點間的距離差持續降低，整體誤差得到有效控制。分析對比仿真測試結果得出，在錨節點比例達到30%時，采取Amorphous-GA搜索定位算法得到的定位誤差穩定性更高。相較于移動錨節點（moving anchor node，MAN）定位算法和Amorphous定位算法，優化未知節點信息的速率可通過Amorphous-GA搜索定位算法得到有效提升，搜索定位效果更佳，定位誤差也更小。

2.3算法復雜度分析

離線網絡連通度主要通過Amorphous算法獲取，進而完成閾值分析模型的設置，并分析每個通信模型的定位誤差，這個過程有利于定位誤差的大幅下降，然而實現過程相對復雜。為了有效控制本文算法在運行過程中占用的資源，分析了不同算法運行時間和定位精度誤差。如表1所示，3種算法的運行時間差異不明顯，但Amorphous-GA搜索定位算法精度誤差最小，即使受到了通信半徑的影響?？梢娋哂泻艽蟮膽脺蚀_性和適應范圍。

3結論

本文研究了無線傳感網絡節點Amorphous-GA搜索定位算法的性能，結果如下。

（1）定位精度在錨節點比例增加后得到顯著提升，定位誤差大幅降低，設置錨節點比例大于30%能夠獲得較小的定位誤差。

（2）在錨節點比例為30%時，采取Amorphous-GA搜索定位算法得到的定位誤差的穩定性更高。相較于傳統定位算法，Amorphous-GA的搜索定位效果更佳，定位誤差也更小。

該研究有助于提高網絡信號控制精度，但異常數據處理方面仍存在計算冗長問題，未來可引入深度學習算法進行深入研究。