設計及實作在大型無線網路下的樣本比對定位系統

Abstract

近年來，位置感知服務被視作行動計算的相關應用中，最有機會成為殺手級應用的服務之一。為了要支援位置感知服務，定位機制則為一個重要的基礎。在這份論文中，我將針對一種基於樣本比對技術的定位系統作討論，並將其應用於大範圍網路環境中。與其他定位系統比較起來，樣本比對定位系統具有許多優點，例如他不需要額外的硬體設備，只需依賴使用者的網通設備與已經存在的網路通訊基礎建設，因此硬體成本很低；此外，因為樣本比對的特性，這一類型的定位系統較能克服複雜的訊號衰減環境，提高室內定位準確度。 對於具有即時性需求的位置感知服務，定位系統的定位反應時間是一項重要的評估條件。而樣本比對定位方法更是如此，因為其定位過程需要透過比對物體即時訊號特徵與大量的特徵樣本，這些特徵樣本是在樣本比對定位系統的訓練階段所蒐集，並且存於一定位資料庫中。在這份論文中，我將提出多個群簇改善機制，藉此加速整個樣本比對定位的運算，透過將具有相似特徵的訊號樣本集合起來，我們可以獲得多個群簇並且計算其相對的代表特徵，之後我們便可以減少比對的次數而改善定位的效率。此外，我們更進一步的指出可能因為此加速機制所產生的錯誤群簇選擇之問題，並且提出多個允許一部份成員重疊的改良群簇法。 除此之外，我們嘗試在樣本比對定位系統中進行高精密度的定位運算。在樣本比對系統中，精密定位與快速定位運算是兩個彼此衝突的需求，為了要獲得更精密的定位結果，我們必須在更多的位置上蒐集訊號特徵。然而，這個做法亦會造成在樣本比對的過程中，產生更多的樣本比對次數，因此計算複雜度亦會顯著提升。因此，在本論文中，我提出了一個全新的差異化函式定位方法，這個方法的精神在於設計一個連續且可微的差異化函式以萃取出訓練位置之間樣本特徵的空間相依關係。為了實現這個方法，我們根據梯度搜尋法這個最佳化技術，設計了GDS-PL與GDS-INT這兩個演算法。 除了加速定位運算之外，改善定位準確度是另一個重要的議題。因為訊號具有飄移的特性，這造成了樣本比對系統的定位結果會有一定程度的誤差。為了減輕這個誤差程度，我提出了一個混亂訊號追蹤機制，此機制利用了多個連續蒐集的訊號樣本之間具有時間上的多樣性與空間上的相依性等性質，並且藉由訊號的重新組合，希望獲得較不受到雜訊干擾的訊號特徵，改善定位正確度。我們展示了如何應用這些特性在位置追蹤上，並且可以搭配任何一種定位演算法，並且都能獲得良好的結果。 最後，我們談論有關在定位系統下的維護機制。在多數的定位系統中，都具備一些參考點被部署在環境中，藉由對於這些參考點的各種測量決定物體或事件的發生位置。這些系統中都對這些參考點具有一些隱含的假設：參考點永遠是穩定可信賴的。在這個研究中，我定義了一個新的參考點移動偵測問題。當環境中有一些參考點被移動但是我們未注意到這個情況時，這會降低定位系統的定位準確度，因此我們希望藉由參考點之間的彼此互相觀察，自動辨識出那些被意外移動的參考點。之後，在定位系統中忽略這些參考點所回報的測量值，將可以改善因為意外移動所造成的定位誤差。

Recently, location-based services (LBSs) have emerged as one of the killer ap-plications for mobile computing. To support LBSs, location estimation mechanism is essential. In this dissertation, we are interested in a type of localization systems based on pattern-matching techniques in large-scale wireless networks. Among all localiza-tion systems, the pattern-matching systems are more cost-effective because they can rely on existing wireless network infrastructures and more resilient to the unpredictable signal fading effects. In LBSs, the response time of location determination is critical, especially for real-time applications. This is especially true for pattern-matching localization, which relies on comparing an object's current signal pattern against a pre-established location database of signal patterns collected in the training phase. In this dissertation, we propose some cluster-enhanced schemes to speed up the positioning process while avoid the possible false cluster selection problem caused by this accelerated mechan-ism. Through grouping training locations with similar signal patterns together and characterizing them by a single feature vector, we show how to reduce the associated comparison cost so as to accelerate the pattern-matching process. To deal with signal fluctuations, several clustering strategies allowing overlaps are proposed. Furthermore, we are also interested in achieving fine-grained localization in the pattern-matching localization systems. In such systems, fine-grained location estimation and quick location determination are conflicting concerns. For finer-grained loca-lization, we have to collect signal strength patterns at a larger number of training loca-tions. However, this may incur high computation cost during the pattern-matching process, thus incurring slow response. In this dissertation, we propose a novel discri-minant function (DF)-based localization methodology. Continuous and differentiable discriminant functions are designed to extract the spatial correlation of signal strength patterns of training locations that are close to each other. To realize this methodology, two algorithms are designed, called GDS-PL and GDS-INT, based on the concept of the gradient descent search. Improving positioning accuracy is another important issue. Signal strength fluc-tuation is one of the major problems in a pattern-matching localization system. To al-leviate this problem, we propose a scrambling method to exploit temporal diversity and spatial dependency of collected signal samples. By means of scrambling, we can enlarge the sample space. Through recombining the limited observed signal patterns, samples with less interference are expected to appear. We present a methodology to illustrate how to apply these properties to enhance the positioning accuracy of several existing localization algorithms. Simulation studies and experimental results show that the scrambling method can greatly improve positioning accuracy, especially when the tracked object has some degree of mobility. Finally, we care about the maintenance issue for a localization system. In most localization schemes, there are beacons being placed as references to determine the positions of objects or events appearing in the sensing field. The underlying assumption is that beacons are always reliable. In this work, we define a new Beacon Movement Detection (BMD) problem. Assuming that there are unnoticed changes of locations of some beacons in the system, this problem is concerned about how to automatically monitor such situations and identify such beacons based on the mutual observations among beacons only. Removal of such beacons in the localization engine may improve the localization accuracy.