基於群聚演算法之無線感測網路目標定位與追蹤

Swarm Algorithm Based Target Localization and Tracking in Wireless Sensor Networks

林建誌(Chien-Chih Lin)

指導教授 ： 鄭佳炘

國立虎尾科技大學/電機資訊學院/電機工程系碩士班/碩士(2016年)

摘要

在無線感測網路技術應用中，目標定位及追蹤一直是被探討的問題之一，眾多研究於目標定位追蹤之應用與研究如接收信號角度法(Angle of Arrival, AOA)、到達時間法(Time of Arrival, TOA)與到達時間差定位法(Time Difference of Arrival, TDOA)等。其中TOA、AOA與TDOA其目標位置估測之效能相較於RSS更好，但在實際應用上，TOA、AOA與TDOA其所需設備較為昂貴，且運算複雜度相較於RSS更為複雜，而RSS之優點在於設備取得容易、運算複雜度較低，因此在後續研究中，我們將使用RSS作為估測目標點與演算法個體(感測器)距離的依據。許多目標定位及追蹤相關研究都使用接收訊號強度(Received Signal Strength Indicator, RSSI)作為估測目標點與參考節點距離的依據。實際應用上，無線訊號從發射端發送出時，因訊號接觸到建築物及各種障礙物後的反射、散射和其他物理特性，使得接收端接收到的訊號會有相當大的誤差値，因此本論文藉由群聚演算法個體(感測器)移動的特性，進行室內空間之目標定位及追蹤，如此便可減少因參考節點布置不當對目標定位及追蹤造成的影響。本研究使用MatLab軟體建立RSSI通道模型模擬實際環境訊號之變化並使用於本論文的目標定位及追蹤之模擬分析。
群聚演算法源於自然界生物群體活動的觀察，模擬鳥群、魚群之覓食的行為(Social behavior)所發展出的演算法，這類源自模擬生物群體活動來找尋最佳解方法也稱為群體智能(Swarm Intelligent, SI)，有人更廣泛的稱為Nature Inspired Computing(NIC)，其求目標函式最佳解的原理為，利用生物社會中資訊分享的概念，提供演算法個體互相溝通與資料交流的機制，來引導演算法個體最終能朝全域最佳解的區域前進，進而使演算法個體聚集於適應值(fitness)最佳的位置，此類演算法也加入個體的隨機行為，使演算法個體有機會跳脫當前的狀態，避免陷入區域最佳解(Local Optimum)。
本論文使用人工魚群演算法(Artificial Fish Swarm Algorithm, AFSA)與粒子群最佳化演算法(Particle Swarm Optimization, PSO)朝最佳解群聚之特性，搭配RSSI通道模型作為目標函式來進行室內空間目標定位及追蹤之模擬分析，並比較兩種演算法於目標定位與目標追蹤系統之效能優劣。本研究中演算法個體(感測器)為接收端，目標點為發射端，將接收端與發射端之距離透過RSSI通道模型得到相對模糊的初始RSSI値來模擬實際環境之狀況，再利用演算法模擬生物覓食之習性，演算法個體會向食物源(RSSI値)最大的方向移動，透過個體多次移動後估測出目標點位置，如此便可藉由多個演算法個體相互交換資訊來降低因RSSI的波動所造成的誤差，但這也衍生出另一問題，要使目標位置估測及追蹤的精準度提升，勢必要增加演算法個體的使用數量，如此才能保證有足夠的資料能夠分析及比較，因此要在不影響目標定位及追蹤之精準度上減少演算法個體使用的數量也是本研究所探討的問題之一。本論文提出區域分割方法(Region Segmentation Method, RSM)，此方法將整個感測網路分割成四相等區域並於每區域中心放置一錨節點，透過在目標定位與追蹤程序開始前使用四個區域的錨節點估測目標點大致位置，就可僅使用該區域之個體進行演算法行為，減少演算法搜尋範圍。模擬結果顯示，在不影響目標定位及追蹤之精準度下，此方法能大幅減少演算法個體使用數量也可提升定位及追蹤之速度。

關鍵字

無線感測網路 ； 目標定位 ； 目標追蹤 ； 人工魚群演算法 ； 粒子群演算法 ； 接收訊號強度

並列摘要

The Research of target localization and tracking is always the remarkable problem in the application of Wireless Sensor Networks (WSNs) technology. Many Researches and application of target localization and tracking, such as Angle of Arrival (AOA), Time of Arrival (TOA) and Time Difference of Arrival (TDOA) all used Received Signal Strength Indicator (RSSI) to estimate the location of target. In the actual application, the signal that receiver received would have huge variation when there are objects (such buildings or trees) between transmitter and receiver. In this case, some part of transmitted signal strength is lost through absorption, reflection, scattering, and diffraction. It’s the hard problem to improve the accuracy of target localization and tracking with RSSI. In ours research, we used MATLAB to simulate the signal variation in actual environments by RSSI channel model and used the RSSI channel model to implement target localization and tracking.
Swarm algorithm is based on the observation of animal behavior in natural world like birds and fish. The algorithm imitated the prey behavior of animal to find the global optimum. It also called Swarm Intelligent (SI) or Nature Inspired Computing (NIC). The principle of seeking the global solution of objective function is to adopt the information sharing mechanism of animal society, so that the individuals could exchange the information with this mechanism to make the individuals could move forward to the section of global optimum eventually. In addition, this kind of algorithm also have random behavior for individuals to make the individuals have ability to depart from the current status. Therefore, the individuals could avoid sinking into local optimum further.
In this thesis, we utilized the characteristics of Artificial Fish Swarm Algorithm (AFSA) and Particle Swarm Optimization (PSO) which used the individual’s ability of communication among individuals for target localization and tracking. In addition, we used the RSSI value as objective function to implement target localization and tracking and compared the target localization and tracking performance of two algorithms. In this thesis, we set algorithm individuals (mobile beacon) as receiver and target point as transmitter. We transferred the distant between receiver and transmitter to RSSI value through RSSI channel model to simulate the signal variation in actual environments. Then we used characteristic of SI seeking global optimum to obtain the estimation point through the individuals move forward to section of high food consistency (RSSI). We could reduce the estimation error that caused by RSSI variation via the information sharing mechanism. On the other hand, we have to use more individuals to increase the accuracy of target localization and tracking. Ergo, this study focused on improving the accuracy of target localization and tracking with less amount of individuals. We proposed the Region Segmentation Method (RSM) to estimate the probably section of target so that we could only use the individuals in this section and reduced the algorithm searching space further. The simulation result demonstrated that RSM could reduce the time of target localization and tracking significantly with good performance of accuracy.

並列關鍵字

WSNs ； Target localization ； Target tracking ； AFSA ； PSO ； RSSI

參考文獻

[5] 吳伯彥，2014，模糊邏輯技術在XBee無線感測網路之RSSI定位演算法”，國立虎尾科技大學電機工程研究所碩士論文，頁 1~96。

[6] 李紹瑋，2015，”雙層棋盤架構Zigbee網路應用於任意室內面積定位法之研究”，國立虎尾科技大學電機工程研究所碩士論文，頁 1~40。

[8] Eny-Yang Xu, Zhi Ding, and Soura Dasgupta, “Target Tracking and Mobile Sensor Navigation in Wireless Sensor Networks”, IEEE Transactions on Mobile Computing, vol. 12, no. 1, pp. 177-186, 13 Dec. 2011.

[9] Sandy Mahfouz, Farah Mourad-Chehade, Paul Honeine, and Hichem Snoussi, “Target Tracking Using Machine Learning and Kalman Filter in Wireless Sensor Networks”, IEEE Sensor Journal, vol. 14, no. 10, pp. 3715-3725, 20 June 2014.

[10] Zhi-Kun Liu, and Zhong Liu, “Node Self-Localization Algorithm for Wireless Sensor Networks Based on Modified Particle Swarm Optimization”, Proc. of the 27th Chinese Control and Decision Conference, Qingdao, pp. 5968-5971, 23-25 May 2015.