行動無線感測網路下基於色彩理論之改良型動態定位技術

Abstract

定位資訊在無線感測網路的應用中是不可或缺的，例如，它可運用於軍事、監測、照護系統上。雖然全球定位系統(GPS)是非常普及而且實用的，但是它卻非常的昂貴並且不適合應用在無線感測網路上。此外，如果感測點嵌入了GPS的裝置，電源的消耗勢必成為一個重要的考量。也就是說，傳統上無線感測網路下所使用的感測點都是屬於小、低負擔、且低耗電的裝置。現有的定位方法中很少探討有感測點可移動之情況。因此在本篇論文中，我們提出了一個適用於行動無線感測網路且基於色彩理論的動態定位演算法(CDL)之改良機制(E-CDL)。原本的CDL演算法會利用所有的參考點廣播的位置資訊和其RGB值來幫助伺服器建構位置資料庫，這些資訊也會傳給感測點來計算它的RGB值。然後所有的感測點會把自己的RGB值傳回給伺服器作為定位用的資訊。然而CDL這個演算法的正確性卻仰賴於計算平均躍點距離 (average hop distance) 的準確性。在本論文中，我們提出了兩個新的方法來估計平均躍點距離。在分析了感測點的通訊行為後，我們計算出平均躍點距離的期望值為7r/9, r 為感測半徑。此外，因為CDL是基於DV-Hop的一個演算法，所以會造成建置的最短路徑長度通常會大於實際距離的問題。根據實際長度與最短路徑長度的比值，我們將最短路徑的長度按此比值作一個調整，因此可以進一步地增加定位的準確性。最後，在行動無線感測網路下，感測點可能會有離群的現象。藉著行動參考點在周邊的移動，離群點的問題可以順利地被解決，並且增加定位的準確性。模擬結果顯示，E-CDL定位的準確性比CDL還要好50% - 55%，比MCL好75% - 80%。此外，我們在MICAz Mote Developer’s Kit上面實作並且驗證我們的演算法。實驗的結果顯示出定位的誤差值大約在0.21r的範圍。由於實驗樣品的不足，所以這個定位誤差要比模擬的結果 (0.1r) 稍大些。

Positioning in wireless sensor networks is essential in many applications, including military, monitoring, and health-care applications. Although GPS is very popular and useful, yet it is very expensive and not feasible in wireless sensor networks. Furthermore, power consumption is a concern if sensor nodes are equipped with GPS devices. That is, wireless sensor networks typically use sensor nodes which are small, low overhead and low power. There are few localization schemes targeted at mobile wireless sensor networks. Therefore, we propose an Enhanced Color-theory-based Dynamic Localization (E-CDL) which is based on the CDL algorithm. The original CDL makes use of the broadcast information from all anchor nodes, such as their locations and RGB values, to help the server create a location database and to assist each sensor node to compute its RGB values. Then, the RGB values of all sensor nodes are sent to the server for localization of the sensor nodes. However, the location accuracy of this algorithm depends on the accuracy of the average hop distance derivation. In this thesis, we present two novel schemes to estimate the average hop distance. We analyzed the behavior of sensor nodes communication, and computed the expected value of the average hop distance, which is 7r/9, where r is the radio range. In addition, since CDL is based on the DV-hop scheme, the derived shortest path length is usually larger than the corresponding Euclidean distance. With this observation, the derived shortest path length can be adjusted by the ratio of the Euclidean distance and the shortest path distance to further enhance the location accuracy. Finally, in mobile wireless sensor networks, sensor nodes may become isolated. By employing mobile anchor nodes, the isolation problem can be relieved and hence the location accuracy can be improved. Simulation results have shown that the location accuracy of E-CDL is 50% - 55% better than that of CDL, and 75% - 80% better than that of MCL. In addition, we have implemented and verified our algorithm on the MICAz Mote Developer’s Kit. Experimental results show that the location error is about 0.21r which is larger than that of the simulation result (0.1r). This is due to small sample sizes.