隨意無線網路之次序距離為基礎定位與網路邊界偵測

在無線隨意網路的定位應用上，研究先進們提出了 MDS-MAP 以及 DV-Hop 兩個典範，兩者演算法皆適用於基於距離測量或者基於連結(connectivity)測距的計算方式。其中基於連結測距定位方式具有普及性及距離量測的不確定性的特色，最為廣泛採用，所以近年來許多研究開始著重於改善連結測距的定位方式。也因此我們提出了基於遠近次序距離量測方式，使用鄰近節點個數之資訊來改善過去連結導向的量測方式，其次，我們的模型也可以延伸套用至距離測量的模式。實驗分析顯示遠近次序距離量測模型顯示相較於連結導向的測量方式更為精準，同時分析指出計算出單一節點與所有鄰近節點的遠距次序距離演算法的時間複雜度為 O(n*log(n))，此分析結果亦表示我們的演算法適用於分散式環境。本論文分析更指出隨著網路節點密度的增加與遠近次序距離量測模型快速收斂到逼近實際測距之間的關係。模擬實驗顯示遠近次序距離量測，相對MDS-MAP 以及DV-Hop有較好的精準度以及強固性。由於連結性質在隨意無線網路上擁有普遍性且深受環境影響之特性，如何在受雜訊影響的環境中正確估算連結特性變成了一重要議題，在本論文，我們提出了一個演算法用以改良此一議題。利用普瓦松點過程 (Poisson point process) 模型的特色以及單一節點與鄰近節點間連結訊息交換，我們的演算法可修正部分錯誤判斷連結的性質。實驗指出不論在低雜訊或者高雜訊的環境下，我們的演算法都比僅依賴通道狀況的連結判斷方式還有更好的精準度。此外，邊界節點由於缺乏足夠的鄰居個數以及資訊條件不同，容易在資訊判斷上造成錯誤，如定位誤差，因次偵測節點是否為邊界節點在隨意無線網路是一重要的課題。Fekete 等研究員在高密度網路條件下，對邊界偵測提出了一個利用鄰居個數作為門檻值來辨識一個節點是否為邊界節點，本研究更進一步提出利用兩個跳躍(hop)之內的節點個數來作為邊界節點偵測的決策融合演算法，藉以提升精準度並且降低對網路密度的需求。此外給定網路形狀，藉由設定成本參數給出特定的成本函數(cost function)，我們的分析指出最佳的門檻值設定是可以預測的。相較於 Fekete的研究，實驗結果指出我們的方發擁有高達 90%的偵測率以及低於 10% 誤判機率，優於Fekete 的研究。

關鍵字

隨意無線網路； MDS-MAP ； DV-Hop ；定位；遠近次序距離量測；邊界偵測；決策融合

並列摘要

In wireless ad hoc networks, the multi-dimensional scaling (MDS) based algorithm named MDS-MAP and hop-size based algorithm named DV-Hop have been proposed for the sensor localizations. Two major types of distance estimation methods, the range-free and the range-based, are applied in the localization schemes. In the range-free scheme, the connectivity is the only information available, and therefore its distance estimation is inaccurate. We propose a novel distance estimation method to improve the accuracy of distance estimation called order distance. Besides the range-free distance estimation, our approach incorporates the range-based distance estimation with the distance inequality property, such as the monotonic RSS-Distance relationship. In our approach, a node ranks the orders of its neighbors through exchanging neighbor information. The order information achieves better accuracy of distance estimation than mere connectivity does. The complexity of a node to obtain all order distances of its neighbors is O(n*log(n)). Moreover, the analysis shows the order distance estimation converges rapidly with the growth of the node density. In the simulations, our scheme achieves better accuracy than the original MDS-MAP and DV-Hop. The results also demonstrate better robustness in our order-based localization scheme than the MDS-MAP under the noisy environment. The property of connectivity among the nodes is widely utilized to reason the information required by the algorithms, so the connectivity of two nodes is an important and fundamental feature in the wireless sensor networks. The accuracy of connectivity is dominated by the distance estimation between two nodes under noisy channel. In this dissertation, we propose novel algorithms to improve the accuracy of the connectivity calculation under noisy channels. By using the feature of Poisson point process and one-hop information of the nodes, a node constructs the core nodes and calculates the number of common nodes between neighboring nodes. By using the two metrics, a node obtains the more accurate connectivity with neighboring nodes. The simulation results demonstrate that the accuracy of the connection is improved significantly in both low-noise and high-noise channels. In addition, the results show that the false negative and false positive rates decrease with the growth of the node density. Besides, the nodes near the boundaries of the networks have poor performance in many distributed algorithm. Due to the inefficient neighboring nodes and partial information, the nodes near the boundary have worse performance, such as localization. Hence, the boundary recognition is an important issue in the ad hoc networks. By the statistical approach in high node density networks, Fekete’s pioneer work identified the boundary node by number of neighboring nodes and a specific threshold. By exploiting the number of nodes in the two-hop region, our proposed algorithm has significant improvement of boundary recognition as opposed to the Fekete’s algorithm in the low-density network. Given the information topology and the cost function, the analyses provide a framework to obtain the optimal threshold for boundary recognition. Besides, the simulation results reveal the proposed algorithm has greater than 90% detection rate and lower than 10% false alarm rate.

並列關鍵字

ad hoc networks ； MDS-MAP ； DV-Hop ； localization ； order distance estimation ； boundary recognition ； and decision fusion

參考文獻

[2] E. Elnahrawy, X. Li, and R. P. Martin, "The limits of localization using signal

[1] N. B. Priyantha, A. Chakraborty, and H. Balakrishnan, "The Cricket

conference on Mobile computing and networking, New York, NY, USA, 2000, pp.

Self-Localization for Antenna Arrays Subject to Bending and Vibrations," IEEE

Sensing: A Nonparametric Iterative Adaptive Approach Based on Weighted

國際替代計量

隨意無線網路之次序距離為基礎定位與網路邊界偵測

全文下載

主題瀏覽