全球定位系統（Global Positioning System；GPS），是當前全世界最普及的全球導航衛星系統（Global Navigation Satellite System；GNSS），GPS總共放置了多達32顆高度位於地表20200公里以上的衛星，均勻地分佈在六個以55度傾斜於赤道的軌道面上。如此的設計提供高度的全球覆蓋度，並使得幾乎每一位使用者，在沒有任何遮蔽物阻擋訊號的條件下，都可以擁有至少四顆以上的衛星在可視範圍中以供定位之用。

GPS原先是由美國在20世紀中葉為了軍事相關用途所開發，然而隨著2000年5月美國柯林頓總統宣佈關閉選擇式供應（Selective Availability；SA）所造成的人為誤差後，定位誤差在一夕間從一百公尺降低到十幾公尺，大開GPS方便應用之門。現在GPS已被廣泛應用在其他領域，例如測量科學、航空安全、汽車及行人導航等，現今更成為許多手機的標準配備。GPS會如此盛行的另一個主因就在於它可以提供高精確度， 卻不向使用者收取服務費用。

與傳統AM及FM廣播系統類似，GPS也是從衛星到地面接收機的一種單向傳輸。與廣播系統的差異在於GPS接收機並不只靠單接收以及處理一個衛星的訊號就可以完成定位，相反地，需要同時收到來自多顆衛星的訊號。透過還原隱藏在傳輸訊號中的導航資訊，接收機方可得到定位所需的兩個重要資訊：首先是衛星的位置，接著是衛星到使用者的距離。有了超過四顆衛星的位置以及他們到接收機的距離估測之後，接收機便可以運用這些估測值來進行處理及決定其本身的位置、速度、以及時間（Position、Velocity、and Time；PVT）。一般說來，如果一個接收機可以掌握越多衛星訊號，則其對於位置估測的精確度便可以提高。然而實際上，並非所有的可視衛星皆可被成功接收。其主要的原因在於不同的衛星對於使用者有不同的仰角，導致信號的衰減或是接收訊號的強度並不一致，如果再加上使用者所在環境遭到建築物或是其他物體遮蔽，都可能會造成有部份衛星訊號強度降低到接收機無法成功接收。在冷開機（cold start）的情況下，要知道究竟有哪些衛星可供利用，便得透過複雜且費時的搜尋過程，因此降低搜尋時間或是運算複雜度的方法就變的相當重要。
...
...