TWI376521B - Collection and construction of training location data of positioning system and positioning method therefor - Google Patents

Description

1376521 _ • 年月日絛正替換頁 九、發明說明： 【發明所屬之技術領域】 一種定位方法，特別是指一種定位系統之訓練位置資 料收集、建構與定位方法。 【先前技術】 請參照圖1，先前技術中’ RADAR (TP. Bahl andV. N.

Padmanabhan. RADAR: An In-Building RF-based User

Location and Tracking System. In IEEE INFOCOM, pages 775 - 784， 2000.) 是一個以比對特徵演算法 (Pattern-Matching Algorithm)為基礎的定位系統。 在定位系統的訓練（Training)階段中，先預定複數 • 個已確定座標之訓練位置£ =仏_”4}，每一訓練位置之座標 ' 係為 ，&=<〜&>.. 乂 =<\’\>。將各訓練位 置鄰近之複數個基地台（Beacons)丑=伙1，…，Μ的訊號強 度’形成複數個特徵樣品（Samples)。根據所有的特徵樣 本建立每一個訓練位置4的特徵向量叫=[Ί切，2, ·__，％„],其中 「〜，j = l…η」代表基地台仏的平均訊號強度。之後，將 這些特徵向量與訓練位置的配對全部儲存到定位系統資料 庫（Database)。 定位（Positioning)階段裡，此待測物需具有一無線 設備及時（Real-Time)接收相鄰基地台的訊號強度特徵 s = h，S2’···，^]，並將之與資料庫内儲資料比對，取得最相似 的特徵向量作為測待物的位置。首先’訓練位置之特徵向 1376521 年月日條正替換頁 量與當前即時訊號強度特徵之差異視為h函式，將樣本比 對的定位過程以一個離散函式表示，找一個訓練 位置使得h函式的值最小。舉例而言，h函式一般被定義 為兩向量的歐幾理德距離（EuclideanDistance)，並在一 個具有兩個基地台的測試空間蒐集三個訓練位置從 三個訓練位置與待測物之歐幾理德距離中，取出最小距離 數值所屬的訓練位置視為待測物的當前位置。 【發明内容】 本發明所提供之技術手段係揭露一種定位系統之訓練 位置資料收集與建構方法，適用於具有複數個基地台與複 數個訓練位置的測試空間。此方法包括步驟：在各訓練位 ^偵測與其相鄰之各基地台之訊號強度以轉換成一訊號向 整合所有訊號向量以計算出每1練位置之—特徵向 =記錄各訓練位置之座標與對應之特徵向量。以及將各 =位置^座標與對應之特徵向量，各別導人—數值擬合 式夺^ -基地台之—訊號強度函式。訊號強度函 表不任—位置接收基地台訊號的對應關係。 【實施方式】 為:㈣本發日㈣目的、構祕徵及其魏有進一步的 纹配合相關實施例及圖式詳細說明如下： 可利所揭露的所有資料收集、建構與定位方法中， 丨練位置之間的「空間相依性」來加快搜尋的速度。 1376521 年月日修正替換頁 «月同4參知、圖2A與® 2B ’假設一個測試空間劃分為50x50 的格狀.祠路’八個基地台配置於此測試空間的四周，且測 試空間具有平均分佈的625個訓練位置。 當用戶利用訊號债測器在座標(42:42)的訓練位置上，蒐 集到比對訊號向量s，即可計算各訓練位置齡⑹函式值。 經由/1⑹函式值計算結果得知，越接近_)的訓練位置（圖 2B中’又才示5己處）’其九⑹函式值會越低，藉由數值漸降的 現象以協助用戶、業者搜尋待測物的所在的待測位置。 基於此概念，本發明係揭露相關定位演算法。當給定 一組訓練位置與其對應之—組特徵向量v和一個比對訊號 向I s ’我們建立一個連續且可微的差異化函式 (Discriminant Function) ，並且對於各個訓 練位置達成/¾) 的目的。差異化函式/的梯度資訊 (Gradient )則可以用來表示訓練位置之間的空間相依 性，因此我們可以藉由找尋函式/的最低點，而避免去計 算每個訓練位置的/1¾)函式值。 請參照圖3，其為本發明實施例之系統簡示圖。此系 統係結合至少一訊號偵測器2〇〇與一定位主機1〇〇，並應 用於-測試空間300。此测試空間3〇〇係隨機配置有複數 個基地台301 (或無線存取器；Access p〇int ; Ap)與複 數個已知座標的訓練位置3〇2。冑位主機1〇〇本身具有收 集與建構訓練位置資料、並利用此等資料進行定位計算的 定位模組110與資料庫120。訊號偵測器2〇〇則可接收不 — ----- 同基地台的無線訊梦 無線連接7υ 1斷訊#b_ ’並與定位主機100 琨订貝訊交換動作。 但本發明所揭露之 流程可歸總如下.妝十巾礼練位置貝料收集的主軸 台之訊號強戶以鐘祕训練位置偵測與其相鄰之各基地 u強度Μ轉換成_ 计算出每—訓練位置之—如^ ^所有訊號向置以 標與對應之特徵向旦,、 置。記錄各訓練位置之座 之特符6曰4。里以及，將各訓練位置之座標與對應 台二入—數值擬合模型，以建構每一基地 對應關係。 4其表不任—位置接收基地台訊號的 可發明所揭露之方法中’待測位置定位的主軸流程 〇 下.偵測在一待測位置，其相鄰之各基地台之訊 琥強度’以轉換成—比對訊號向量。利用比對訊號向量盘 各基地台之訊號強度函式建構出一差異化函式。以及，利 用一最佳化數值搜尋技術找出差異化函式之最小值，此最 小值之所在位置即視為待測位置於測試空間之座標。 數值擬合模型可係經由一路徑衰減法建立而得、或經 由一迴歸法建立而得、或經由一内插法建立而得，或係經 由路徑衰減法、一迴歸法或一内插法之組合，進行計算 而得。但，此等方法在使用路徑衰減模型、迴歸法模型與 内插法模型各有不同的細部流程’因此，以下係各別述％ 此專模型的運行流程。 請參照圖4A，其為本發明第一實施例之訓練方法流程 1376521 •圖，主要揭露定位系統之訓練位置資料 此方法結合路縣減法與最.肖梯度搜尋法，剌如圖3 所不條件的測試空間。此方法具有下列步驟： 圮錄每一基地台301於測試空間3〇〇的座標（步驟 S11〇)。盍因路徑衰減法在計算過程_，定位模組需得知任 一位置304與相鄰基地台301的歐幾理德距離（EucUdean

Distance)° 在各訓練位置302偵測與其相鄰之各基地台3〇1之訊 號強度以轉換成一訊號向量，整合所有訊號向量以計算出 每一訓練位置302之一特徵向量（步驟sl2〇)。 . 此步驟中，需先預定複數個已確定座標之訓練位置 (Training Locations) 302(£ =仏，…，M)，每一訓練位置& 之座標係為A =<%，乃 >，々>，’3 =<〜少3>…/„ =<〜，少m >。利用 訊號偵測器200在每一訓練位置302，收集其鄰近之每— 個基地台（868(：〇115)301(5 = {61，...上})的訊號強度，以轉 換成一訊號向量（每一個基地台301 ^—個），回傳至定位 主機100。 定位主機100係利用定位模組110整合所有的訊號向 量，建立每一個訓練位置厶302的特徵向量 切=[的山认，以「％·，j=l…η」代表基地台^的平均 訊號強度。定位模組110則係記錄基地台301之座標、各 訓練位置302之座標與對應之特徵向量（步驟S130)於定 位主機100的資料庫120。 9 1376521 年月日修正替換百 根據各基地台，將其基地台座標與其關連之各訓練位 置座標與對應之各特徵向量，個別導入一路徑衰減模型（步 驟S140);透過數值分析技術計算各路徑衰減函式之最佳 係數，為各基地台建構一訊號強度函式（步驟S150)。 目前最常用的無遮蔽物空間的Log-Distance路徑衰 減模型係如下所示： PL{d) = PL(d〇) + miog{^-), (公式 1 ) 其中d代表各基地台301與任一位置304之間的距離、d〇 表示一參考距離單位、彡為一環境變數，一般環境下介於2 至6之間。根據這樣的衰減模型，我們可以定義在任一位 置^收到基地台~的訊號強度可表示為如下的訊號強度函 式：

PriLb^^Pt-PLiWLM) = pre/-io^(M), (公式 2) 其中，~為各基地台301，j = l…η，《為測試空間300之中任 一位置304，乃為各基地台301之初始訊號強度、 pre/ = Λ -凡⑹為一距離基地台一參考距離單位之訊號強 度，IKWI為測試空間300之中任一位置304到各基地台~301 之間的歐幾理德距離，彡與心/為^在該測試空間300之環境 參數。然而，與環境相關的4和與硬體相關的Pr<;/係為因計算 而設定的假設值，屬未知的系統參數，故需利用訓練位置 302的資料進行事前的估計。 此時，令此等基地台之未知的最佳系統參數為 1376521 _ 年月日修正替換頁 χ = [Ρί/，ΑΓ ’關連基地台^之各訓練位置302 ’其特徵向 量與座標之對應關係即可表示為Ax=c，其中： "1 -101og(||4,^H)" X \PLf] 丄 'V1,J" _1 -101og(||^m,^||) _ 、 -Φί -— 〆 ^rn.j --^ X v

A C 根據最小平方分析法（Least-Squares Analysis)，即 可找出系統參數x的最佳解： ^=[PiefAj]T = (ATA)-1ATC (公式 3 ) 此0,與C卩可將路徑衰減模型預測的訊號強度與實際上訓 練位置上的特徵向量之間的差距最小化。之後，定位系統 係將A與P4/視為已知的系統參數，將各基地台301之座標 與最佳系統參數，各別導入前述的路徑衰減模型，即可建 構每一基地台301所適用的訊號強度函式（公式2)。至此， 第一實施例的訓練位置資料收集與建構（通稱為訓練階段） 的作業即完成。 請參照圖4B，其為本發明第一實施例之定位方法流程 圖。此定位方法乃使用圖4A方法所建構的訊號強度函式進 行待測物的定位。於此，視待測物為前述的訊號偵測器 200。此定位方法則包含如下步驟： 偵測在一待測位置303，其相鄰之各基地台301之訊 號強度，以轉換成一比對訊號向量（步驟S210)。此步驟 中，訊號偵測器200位於測試空間300中的一個待測位置 303，並將在待測位置303及時（Real-Time)接收到的相 11 1376521 年月日條正替換頁 鄰基地台301的各訊號強度統整形成比對訊號向量 各=[5ι:古2, . . .，5n] 〇 定位模組110即利用基地之座標、比對訊號向量與各 基地台之訊號強度函式建構出一差異化函式（步驟S220 )。 差異化函式係表示如下： η /⑷=—ρ#，〜))2· (公式4) 其中€為測試空間300之中任一位置304，s =[九S2,…，糾為比 對訊號向量，卜為各基地台，j = l…η。 定位模組係利用一最佳化數值搜尋技術找出差異化函 式f之最小值，此最小值之所在位置即視為待測位置303 於測試空間300之座標（步驟S230 )。此數值搜尋技術係 選自由最陡峭梯度搜尋法以及切線搜尋法所組成的技術。 此步驟中，定位模组110係利用梯度搜尋法（Grad i ent Descent Search)以將差異化函式f收斂至最小，在此先 簡易說明梯度搜尋法。 梯度搜尋法為一種遞迴搜尋程序，其較標準的表示式 如下： ^k+1) = + akSk), (公式 5 ) 其中W+υ、W皆是二維向量，而afc則代表一純量。首先， 先隨機挑選一個起始位置_，接下來在各個回合k (^21) 中，我們必須決定一個搜尋方向與一個前進距離办，直到 我們已經足夠靠近目標函式f的最低點。但停止條件有 二：一為檢查連續兩回合搜尋位置的改進幅度是否小於一 12 1376521 _ ' 年月日修正替換頁 個標準值心“，即條件為，+1) - @ ii < ； 一為搜尋次數以 達·個定義的限制值&ma;r ’意即& = fcmaz。 當梯度搜尋法停止後，終止位置即視為目標函式的最 佳解。然在此我們使用最陡ώ肖梯度搜尋法（Steepest Descent Search)來決定,和办。在於每一個回合k，函式 /(州)的最大遞增方向為WW) = ，因此如果我們 [ax ay 選擇，=-▽/俨^則目標函式的函式值將可以以最快的方式 遞減，因此我們可以將（公式5)改寫為 £(fc+1) =£(fc) -afcV/(£(fc)). (公式 6 ) 因此，將差異化函式f微分以計算出任一位置W)304 的前進方向與座標變數，表示式如下： §-Pr{i{k).,b3) dx d 20^0, (s3 - Pr{i(k),b3)) - ^(11^,6,11), 公式7) iy_ =(-2) ^ (sj - P^t^^bj)) —P^i^.bj) =20^φ} (s3 - |-l〇g(||£(fc),6,11). (公式 8 ) i=i y 假定任一位置304當時的梯度為V/M，則定位模組110 即可計算出州-/5V/⑷）： 13 1376521 --日絛正替捣苜 /(^)-^/(^)) <公邮⑷-解(#·))，~))2; i=i =公⑷—A +1岣 i〇g(IK(fc)-所(#))，Ml))2, J-1 fcI：e?. (公式 9) i=i 定位楔級110再利用一切線搜尋法取得β的最收斂 值，切線後尋法之表示式如下： 知=爲一 G;⑹H)G“A)， (公式10 ) 其中 GfcO?) = /，) 1▽州(fc))) 且β係任取二初始值/¾和/¾，再導入 〇[(β) =2〇£a㊀4i〇g(,)—斤州⑹)，〜11).(公式 11) j=l ^ 當计鼻出卢符合1爲十1 _如< △卢胃或（=ima：c，即停止切線搜尋法 其中 5 ^βτηίη^Ο tmax 為預設參數。 之後，定位模組110將卢的最收斂值代入（公式5)之 叫，判斷差異化函式f是否收斂至最低，以判定任一位置 ^)304是否為最收斂的值。若任一位置〆fc)3〇4不為最收敛 的值，則以任一位ϊ^)3〇4為基準，並且重複（公式7)、（八 式8)、（公式9)、（公式1〇)、（公式11)重新取得▽形叫)與 叫+1’再代入（公式5)，重複上述公式’直至取得待測位 置Q03的最收斂值。至此，定位模組110對訊號接收器2〇〇 1376521 _ 年月日修正替換頁 的定位作業即結束。 請參照圖5A，其為本發明第二實施例之訓練方法流程 圖，主要揭露定位系統之訓練位置資料收集與建構方法。 此方法結合線性迴歸法與最陡峭梯度搜尋法，適用如圖3 所示條件的測試空間。此方法具有下列步驟： 在各訓練位置302偵測與其相鄰之各基地台301之訊 號強度以轉換成一訊號向量，以整合所有訊號向量以計算 出每一訓練位置302之一特徵向量（步驟S310 )。此步驟 與步驟S120雷同，在此不贅述。 記錄各訓練位置302之座標與對應之各特徵向量（步 驟S320 )。定位模組係將上述資料儲存於資料庫中。 根據各基地台，將其關連之各訓練位置之座標與對應 之各特徵向量，個別導入一迴歸方程式（步驟S330 );透 過迴歸分析技術計算各迴歸方程式之迴歸係數，為各基地 台建構出一訊號強度函式（步驟S340 )。迴歸方程式的實 施例如下所示： έ Σ αρ^χΡν9^ (公式 12) p=〇 q=〇 其中< x，y >為任一位置<304的座標、，p=0…r、q=0···r， 表示一未知迴歸係數。根據這樣的迴歸方程式，我們可以 定義在任一位置彳收到基地台6』·的訊號強度可以表示為如下 的訊號強度函式： r r 巧(认)=Σ Σ（公式13) 其中，為各基地台3〇1，厂卜… 換頁 \•在該測4咖 置304，^為 〇，U 300之環境參數。然而’與環境相關的參數 阳Ρ〜0··.Γ、㈣…r ’係因計算而設定的假設值 =系統參數’故需利用訓練位置3〇2的資料進行事前的估° 此時’令此等基地台〜之未知的最佳迴歸係數為 x一W。’喏(設定Γ=1)，關連各基地台 ; 其特徵向置與座標之對應關係即可表示為α X=c， 其中： 1而m * · . • ： ： xm X ao,o (i) 1 B 1 Xm yin Ττηϊ/τη ao5i nU) -Vrnj ——V—— A 、 -al’l J 、 〆

X 根據最小平方分析法（Least-S_resAnaiysis)，即 可找出迴歸係數x的最佳解·· x - [«〇^^〇, a〇l；a^l]T = {ATA)~lATC f 八 1 /f、 此係數X = 也)， C A 式 14) a — 了以將迴歸方程式預測的訊號強度 4際上訓練位置上的特徵向量之間的差距最小化。之 後’定位系統係將义視為已知的系統參數將各基地么之 最佳迴歸係數’各別導入前述的迴歸方程式。即可^每 一基地台301所適用的訊號強度函式（公式13)。至此， 第二實施例的訓練位置資料收集與建構（通稱為訓練階 的作業即完成。 請參照圖5β，其為本發明第二實施例之定位方法流程 1376521 _ 年月日條正替換頁 圖。此定位方法乃使用圖5A方法所建構的訊號強度函式進 行待測物的定位。於此，視待測物為前述的訊號偵測器。 此定位方法則包含如下步驟： 偵測在一待測位置303，其相鄰之各基地台301之訊 號強度，以轉換成一比對訊號向量（步驟S410)。此步驟 中，訊號偵測器200位於測試空間300中的一個待測位置 303，並將在待測位置303及時（Real-Time)接收到的相 鄰基地台301的各訊號強度統整形成比對訊號向量 s = [Si，S2, _ · ·，s„] 〇 定位模組110即利用比對訊號向量與各基地台之訊號 強度函式建構出一差異化函式（步驟S420 )。差異化函式 係表示如下： η f(i) = Y^(Sj - PriW)2. (公式 1 5 ) 其中<為測試空間300之中任一位置304，S = [S1，S2，_，〜]為比 對訊號向量，~為各基地台301，j = l…η。 定位模組係利用一最佳化數值搜尋技術找出差異化函 式f之最小值，此最小值之所在位置即視為待測位置303 於測試空間300之座標（步驟S430 )。此數值搜尋技術係 選自由最陡Λ肖梯度搜尋法以及切線搜尋法所組成的技術。 此步驟與步驟S230雷同，在此僅介紹相異處： 17 1376521 年月日條正替換頁 θ y^(~2)(si - Pbj)) — Pr(E, bj) J-1 (公式16) y^(~2)(gj - Pr(^·, bj)) x + , iym d :L(-2)(Sj - Pr{Lbj))—Pr{^bj) j=i J n -y^(~2)(5j - Pr(^,bj)) x + , J=l n j=l =Σ (¾ - (aS+++aS 邱)) i=i n =ΣΘ?· (公式17) (公式18) =Ypf^[k) - PVf(£^)) n rj j=i p n =2^0,(^ + ^-2-¾). (公式 19) 其中

Fj.2 = ^}^{k)) (α〇Λ + allX(k)) 18 1376521 年月日修正替換頁 巧尸2㈣έ/(，|/(洲） 支&位模系且11〇將卢的最收敛值代入（ 之 :;判：差異化函式f是否收敛至最低 ，以判定^一位置 心304是否為最岐的值。若任-位置㈣04不為最收斂 ，值，則以任一位㈣3〇4為基準，並且重複（公式16)、 公式17)、（公式18)、（公式10)、（公式19)重新取得 ▽/(—))與叫+1的最收斂值，再代入（公〇,重複上述公 式’直至取得待測位置侧的最收斂值。至此，定位模組 110對訊號接收器200的定位作業即結束。 4參照圖6A與6B，其為本發明第三實施例之訓練與 定位方法流程圖，主要揭露定位系統之訓練位置資料收集 與建構方法。此方法結合距離反比内插法與最陡峭梯度搜 尋法，適用如圖3所示條件的測試空間。此方法具有下列 步驟： 在各訓練位置302偵測與其相鄰之各基地台3〇1之訊 號強度以轉換成一訊號向量，整合所有訊號向量以計算出 每一訓練位置之一特徵向量（步驟S510)。此步驟與步驟 S120雷同，在此不贅述。 定位模組110在每一個訓練位置A302上’根據其附近的訓練 位置302的特徵向量，計算出一對應之梯度資訊 ▽巧(从)=隖馬严。然而，此梯度資訊係因計算而設定的假 設值，屬未知的系統參數，故需建造出一個連續的平面進行事 前的估計，其表示式為： 1376521 年月日修正替換頁 = + Qh χ (^· - Xi) + Qh x(y- Vi) (公式 20 ) 根據此訓練位置4302與其附近一具有e個訓練位置的 乂⑷群組（乂⑷為會影響所建構之I⑷平面的訓練位置群 組），將所有的座標與特徵向量之對應關係表示為Ax=c，其 中： vUj - -viJ V^J -

C

V\ - Vi X Qh rv .- Xe - Ve - Vi 、 -- X A 利用一最小平方分析法（Least-Squares Analysis)計算 出之後，定位系統係將％與％視為訓 練位置^302之梯度資訊。 記錄各訓練位置之座標與對應之特徵向量與梯度資訊 (步驟S520 );定位模組110將各訓練位置之座標與其對 應之特徵向量與梯度資訊建構成具有空間相依性之一資料 結構（步驟S530 )。一般而言，此等資料被儲存時，所使 用的資料結構為R樹結構，建構成此種資料結構主要是為 加速後續的定位作業，其使用時機請容後說明。 在此先說明，利用内插法最主要的特色在於訊號強度 函式之係數並非固定，而是根據不同的位置而動態改變， 因此在訓練資料蒐集與建構的過程中，並無產生固定之訊 號強度函式，而是在定位的過程中動態產生。 偵測在一待測位置303，其相鄰之各基地台301之訊 號強度，以轉換成一比對訊號向量（步驟S610)。此步驟 20 1376521 年月日修正替換頁 與步驟S210雷同，在此不贅述。 定位模組110係將任一位置座標與具備空間相依性之 一資料結構導入一内插模型，以產生一動態訊號強度函式 (步驟 S620 )。 距離反比内插法的概念在於當要預測任一位置q〇4的 訊號強度時’定位模組110會使用一個加權方式讓離任一 位置〖304較近的訓練位置302有較大的影響，反之讓離任 一位置《304較遠的訓練位置302的影響較小。依據此原則， 我們定義在位置€收到基地台卜的訊號強度函式為

Pr{tb3) = —^— Σ % χτ，Μ (公式 21)

Wi eieNr(e) ^eNr(e) 其中斯= £為任一位置304，6代表訓練位置302，λ則 疋定位系統之一系統參數，一般我們會讓>=2。如此定義的 動態訊號強度模型可以保證連續性及可微性，並且對於所 有k £我們可以保證即= %。而㈣表示一訓練位置群組， 其包含離任一位置〖304最近τ個訓練位置3〇2。此群組之設計乃基 於工作效能的考量，係用於限制訊號強度函式仰A)只會受到一 部份訓練位置的影響。因此，對於任一位置言，為了更快 速的找到這個訓練位置群組·，定位模組1〇u更會利用料 收集、建構（即訓練階段）時，所建構之R樹資料結構存 於貢料庫的資料結構雜）迅速將任—位置讓 的訓練位置相匹配，判定鄰近任一位酬二= 群組队W。 °)丨練位置 21 1376521 年_替換頁 定位模組110利用比對訊號向量與各訊號強度函式建 構出一動態差異化函式（步驟S630)。差異化函式係表示 如下： /(^) = ^2(sj - Pr{^bj)f. (公式 22) i=i ’ 其中彳為任一位置304，《 = [^2,…，s„]為比對訊號向量，^為各 基地台，j = l...n。 定位模組110利用一數值搜尋技術找出差異化函式之 最小值，最小值之所在位置即視為待測位置303於測試空 間300之座標（步驟S64〇)。此數值搜尋技術可選自由最 陡峭梯度搜尋法以及切線搜尋法所組成的技術。 此步驟中，定位模組H0係利用梯度搜尋法（Gradient Descent Search)以將差異化函式f收斂至最小。將差異 化函式f微分以計算出任一位置£3〇4的前進方向與座標變 數，梯度表示式如下： (~2) Σ (¾ - Pr(^\ b,)) ~Pr^k\ bj), (公式23) (-2) έ (ϋ，)Λ)) J=1 υ3Λν3,1 其中 =(~2) Σ (¾ -邱⑷’ ~))矣 pr(”,)， =卜2) έ (〜—只(炉)Λ)) —^y~r>y3·3-^, (公式24) 22 1376521 _ 年月日修正替換頁 一 V υ1χ -- =DL· = Σ Wi·' i,€Av(f(fc>) Df,- =Σ (Wi x Qh £,·£ΛΫ(£(*)) \ + DL· - =53 Ui x Gyi0 f,€Av(€(fc)) V - =DL= Σ if€Av(^fc)) Dx - U3A - ▽ 5 =L· g^Wi·- £,£Av(£(fc)) dya = jA d^Wi- ί,·£Λν(ί(*)) ^ 為了計算梯度搜尋法的前進距離，定位模組110係建立以下 函式 η =Σ (¾ -即⑻-/5ν/(#))Λ·))2， Σ S3 Σ Wi ii^Nr{iW) UeNri,^) Σθ?> (公式25) 其中 l(k) = 1 \\m - βν f

Wi 為了簡化起見，可令定位模組110將和)=糾-〜/(州）， 並根據切線搜尋法，利用（公式10)取得β的最收斂值， (约計算式為 23 1376521 年月日修正替換頁

i=i P =2^Θ严A3+，，，4-%1， (公式 26) 其中 Ε3Λ 五乂2 馬，3 Ε3Λ Ej,r〇 Σ Wi' AeAV(汾 >)[Wix7I，，))， eieNr(eW)J2 — 乙 δβ CieNr-ieW)

Wi, ei6Nr(eW) £ieNr(iw) d w 之後，定位模組110將β的最收斂值代入（公式5)之 afc，判斷差異化函式f是否收斂至最低，以判定任一位置 #)304是否為最收斂的值。若任一位置〆fc)304不為最收斂 的值，則以任一位置/^304為基準，並且透過R樹資料結 構更新訓練位置群組，因此改變各基地台之動態訊號強度 函式與動態差異化函式，之後重複（公式23)、（公式24)、 (公式25)、（公式10)、（公式26)重新取得β的最收斂值， 再代入（公式5)，重複上述公式，直至取得待測位置Q03 的最收斂值。至此，定位模組110對訊號接收器200的定 位作業即結束。 請參照圖7,其為本發明實施例之定位模組定位待測 24 1376521 _ 年月日修正替換頁 位置示意圖。如圖7中，定位模組110根據s與巧建立差 異化函式。在此，我們用等高線的觀點描繪出差異度，差 異化函式f最低點在(42,42)這個位置。起始位置在《(°) = (20=10)， 各個回合所搜尋到的位置州（& = 1·.4)以「三角形」表示。 在第一回合中，定位模組110根據切線搜尋法所搜尋到的 位置則以「圓點」表示為科=州+ /¾ X，（丨=〇_·4)，第一回合 與第二回合的搜尋方向則以「虛線」配合「箭號」表示。 在第一回合中，定位模組110先隨機配置ρ〇與pi，定 位模組110將p〇與pi利用切線搜尋法逐步進行數值收斂動 作，而進行方向係為虛線所示，向上方前進，以逐一取得 P2、P3與P4。此時，P4為當前/(£(。) + X d(。))之最收斂值，再導 入梯度搜尋法取得P4=l(1)，但1(1)不為梯度搜尋法中的最收 敛值。因此，定位模組再以P4=l(1)，導入切線搜尋法逐步 進行數值收斂動作，以尋得1(2)，判斷1(2)是否為梯度搜尋 法中的最收斂值。重複上述步驟，以取得1(4)為梯度搜尋法 中的最收斂值，此1(4)即為差異化函式f最低點（即差異化 函式f的最收斂值），同時代表待測位置303的對應座標。 請參照圖8A與圖8B，其為本發明實施例之特徵比較 示意圖，其係將相鄰訊號強度定位法（Nearest Neighbors Signal Strength，NNSS)與本發明結合之梯度搜尋定位法 (Gradient Descent Search)進行特徵收集比較。 首先，將環境設定為looxioo的大小，然後在四周放置 八個基地台作為定位的訊號源。之後，以格狀網路的型式 25 1376521 年月日修正替換頁 蒐集訓練位置的特徵，每個方格的大小為可調參數，方格 大小越大表示需要蒐集的訓練位置越少。 如圖8A所示，利用上述丽SS比對法與GDS搜尋法各 執行10, 000次定位運算，從下左圖可以看出GDS梯度搜尋 樣本比對演算法所需的定位時間大約都介於1到1.4秒之 間，而NNSS定位法所需要的運算時間則隨著方格大小而有 顯著的變化，在方格最小的設定下，NNSS定位法大約需要 80秒的運算時間（為GDS演算法的66倍），但是隨著方格 的增大，運算的速度就會越來越快，當然，準確度必然會 下降。 圖8B中，右圖顯示了在不同方格大小下，兩種定位法 的定位準確度差異。就GDS比對法，其將訓練位置的特徵 資訊轉換為差異化函式，故不受方格大小的影響。相對的 NNSS比對法的定位誤差會隨著方格增大而增加。蓋因其只 能定位到訓練位置，當訓練位置的精密度越低時，這個限 制就會隱含潛在的定位誤差。綜合以上兩個模擬結果可以 做出以下結論：GDS比對法對於越大的定位環境，其定位 速度與定位精確度的優勢將會越明顯，適合用於不同測試 空間。 雖然本發明以前述之較佳實施例揭露如上，然其並非 用以限定本發明，任何熟習相像技藝者，在不脫離本發明 之精神和範圍内，所作更動與潤飾之等效替換，仍為本發 明之專利保護範圍内。 26 1376521 年月日條正替換百 【圖式簡單說明】 圖1係本發明實施例之定位示意圖； 圖2A與圖2B係本發明實施例之測試空間劃分示意圖； 圖3係本發明實施例之系統結構示意圖； 圖4A係本發明第一實施例之訓練方法流程圖； 圖4B係本發明第一實施例之定位方法流程圖； 圖5A係本發明第二實施例之訓練方法流程圖； 圖5B係本發明第二實施例之定位方法流程圖； 圖6A係本發明第三實施例之訓練方法流程圖； 圖6B係本發明第三實施例之定位方法流程圖； 圖7係本發明實施例之定位模組定位示意圖；以及 圖8A與圖8B係本發明實施例之特徵比較示意圖。 【主要元件符號說明】 100 定位主機 110 定位模組 120 資料庫 200 訊號偵測器 300 測試空間 301 基地台 302 訓練位置 303 待測位置 304 任一位置 27

Claims (1)

1376521 年月日條正替換頁 十、申請專利範圍： 1. 一種定位系統之訓練位置資料收集與建構方法，係適用 於具有複數個基地台與複數個訓練位置的測試空間，該 方法包含下列步驟： 在各該訓練位置偵測與其相鄰之各該基地台之訊號 強度以轉換成一訊號向量，整合該等訊號向量以計算出 每一訓練位置之一特徵向量； 記錄各該訓練位置之座標與對應之該特徵向量； 將各該訓練位置之座標與對應之該特徵向量，導入 一數值擬合模型，以建構每一基地台之一訊號強度函 式，其表示任一位置接收該基地台訊號的對應關係；以 及 一定位方法，其係包含下列步驟： 偵測在一待測位置，其相鄰之各該基地台之訊號強 度，以轉換成一比對訊號向量； 利用該比對訊號向量與各該基地台之訊號強度函式 建構出一差異化函式；以及 利用一最佳化數值搜尋技術找出該差異化函式之最 小值，該最小值之所在位置即視為該待測位置於該測試 空間之座標。 2. 如申請專利範圍第1項所述訓練位置資料收集與建構方 法，其中該數值擬合模型係經由一路徑衰減法建立而得。 3. 如申請專利範圍第1項所述訓練位置資料收集與建構方 28 1376521 _ 年月日修正替換頁 法，其中該數值擬合模型係經由一迴歸法建立而得。 4. 如申請專利範圍第1項所述訓練位置資料收集與建構方 法，其中該數值擬合模型係經由一内插法建立而得。 5. 如申請專利範圍第1項所述訓練位置資料收集與建構方 法，其中該數值擬合模型係經由一路徑衰減法、一迴歸 法或一内插法之組合，進行計算而得。 6. 如申請專利範圍第1項所述訓練位置資料收集、建構與 定位方法，其中該差異化函式係經由一梯度搜尋法尋求 該差異化函式之最小值。 7. 如申請專利範圍第1項所述訓練位置資料收集、建構與 定位方法，其中該數值搜尋技術係選自由最陡峭梯度搜 尋法與切線搜尋法所組成的技術。 8. —種定位系統之訓練位置資料收集與建構方法，係適用 於具有複數個基地台與複數個訓練位置的測試空間，該 方法包含下列步驟： 記錄每一基地台於該測試空間的座標； - 在各該訓練位置偵測與其相鄰之各該基地台之訊號 強度以轉換成一訊號向量，整合該等訊號向量以計算出 每一訓練位置之一特徵向量； 記錄該等基地台之座標、各該訓練位置之座標與對 應之該特徵向量； 根據各該基地台，將各該基地台座標與其關連之各 • 該訓練位置座標與對應之各該特徵向量，導入一路徑衰 29 1376521 年月日修正替換頁 減模型，以透過一數值分析技術計算各路徑衰減函式之 最佳係數，為各該基地台建構一訊號強度函式；以及 一定位方法，其係包含下列步驟： 偵測在一待測位置，其相鄰之各該基地台之訊號強 度，以轉換成一比對訊號向量； 利用該比對訊號向量與各該訊號強度函式建構出一 差異化函式；以及 利用一最佳化數值搜尋技術找出該差異化函式之最 小值，該最小值之所在位置即視為該待測位置於該測試 空間之座標。 9. 如申請專利範圍第8項所述訓練位置資料收集與建構方 法，其中該路徑衰減模型係為凡⑷=凡⑷)+ ίο恤9(4),其中d 代表各該基地台與各該訓練位置之間的距離、d〇表示一 參考距離單位、4為一環境變數。 10. 如申請專利範圍第8項所述訓練位置資料收集與建構 方法，其中該訊號強度函式係為 巧(£為)=乃—尸L(|K，~||) = Pre/ - 10^>l〇g(||(6y||)，其中，~為· 各該基地台，j = l…η，《為任一位置，巧為各該基地台之 初始訊號強度、Pref = Pt - PL(d0)為一參考訊號強度， ||广6彡|丨為該任一位置〖到各該基地台6；•之間的歐幾理德距 離，$與尸re/為該測試空間之系統參數。 11. 如申請專利範圍第10項所述訓練位置資料收集與建構 30 1376521 _ 年月日修正替換頁 方法，其中對一基地台b•各該訓練位置之特徵向量與座標 之 對 應 關 係可 表示為 —nef_ vl.j .Φί - 〆 ，再利用一最小 X C "1 -lOlogdl^i^jll)' ： ： X _1 -101og(||C，M)_ V-v-/ A 平方分析法（Least-Squares Analysis)計算出基地台k 之最佳系統參數 X = [/^e/,A]T = 。 12.如申請專利範圍第8項所述訓練位置資料收集、建構與 定位方法，其中該數值搜尋技術係經由一梯度搜尋法尋 求該差異化函式之最小值。 • 13.如申請專利範圍第8項所述訓練位置資料收集、建構與 定位方法，其中該數值搜尋技術係選自由最陡峭梯度搜 尋法與切線搜尋法所組成的技術。 14. 如申請專利範圍第8項所述訓練位置資料收集、建構與 定位方法，其中該差異化函式係表示為 η f(sj) = -尸7·(认))2· ’ 其中 £為任一位置，s = [h，s2,...，s„]為該 i=i 比對訊號向量，k為各該基地台，j = l…η，6¾¾)為該基 地台b之訊號強度函式。 15. —種定位系統之訓練位置資料收集與建構方法，係適用 於具有複數個基地台與複數個訓練位置的測試空間，該 方法包含下列步驟： 在各該訓練位置偵測與其相鄰之各該基地台之訊號 31 1376521 年月日修正替換頁 強度以轉換成一訊號向量，整合該等訊號向量以計算出 每一訓練位置之一特徵向量； 記錄各該訓練位置之座標與對應之該特徵向量； 根據各基地台，將其關連之各訓練位置之座標與對 應之各特徵向量，導入一迴歸方程式，以透過迴歸分析 技術計算各迴歸方程式之迴歸係數，為各基地台建構一 訊號強度函式；以及 一定位方法，其係包含下列步驟： 偵測在一待測位置，其相鄰之各該基地台之訊號強 度，以轉換成一比對訊號向量； 利用該比對訊號向量與各該訊號強度函式建構出一 差異化函式；以及 利用一最佳化數值搜尋技術找出該差異化函式之最 小值，該最小值之所在位置即視為該待測位置於該測試 空間之座標。 16. 如申請專利範圍第15項所述訓練位置資料收集與建構 方法，其中該迴歸方程式係為A & 其中< x, y >為任 p=〇 g=〇 一位置的座標、，p=0…r、q=0…r，表示一迴歸係數， 而r則是該定位系統之一系統參數。 17. 如申請專利範圍第16項所述訓練位置資料收集與建構 方法，其中對一基地台b•各該訓練位置之特徵向量與座標 32 丄 日條正替換百 之對應關係可表示為 1 Xi yi · · · X S, 1 Vm.尤τη?/τη · · · VinJ A -—^_r V C 再利用敢小平方分析法（Least-Squares Analysis) 十出基地台卜之最佳迴歸係數 Χ =峨，必也 α(ά. ·. Γ = (Λ、)-1代。 申吻專利範圍第1 5項所述訓練位置資料收集、建構 $定位方法，其中該數值搜尋技術係經由一梯度搜尋法 尋求該差異化函式之最小值。 / 19.如申明專利範圍第15項所述訓練位置資料收集、建構 方法其中该數值搜尋技術係選自由最陡山肖梯产 搜尋法與切線搜尋法所組成的技術。 X 20·如申請專利範圍第15項所述訓練位置資料收集、建構 與疋位方法，其中該差異化函式係表示為 输自(SrP撕，其㈣壬一位置，，該 比對訊號向量，~為各該基地台，卜卜·.丨 地台\之訊號強度函式。 21.—種定位系統之訓練位置資料收集、建構與定位方法， 係適用於具有複數個基地台與複數個訓練位置的测試空 間，該方法包含下列步驟： °二 之訊號 以計算 在各該訓練位置偵測與其相鄰之各該基地台 強度以轉換成一訊號向量，以整合該等訊號向量 33 1376521 丰月日修正替換頁 出每一訓練位置之一待徵向量； 估算各該訓練位置之一梯度資料； 將各該訓練位置之座標與對應之該特徵向量與梯度 資訊建構一資料結構，用於儲存内插法所需之資訊；以 及 一定位方法，其係包含下列步驟： 偵測在一待測位置，其相鄰之各該基地台之訊號強 度，以轉換成一比對訊號向量； 將任一估測位置與該資料結構之各訓練位置匹配， 判定鄰近該任一估測位置之一訓練位置群組； 將該訓練位置群組之各訓練位置所對應特徵向量與 梯度資訊導入一内插模型，以產生各基地台之動態訊號 強度函式； 利用該比對訊號向量與各該訊號強度函式建構出一 動態差異化函式；以及 利用一最佳化數值搜尋技術找出該差異化函式之最 小值，該最小值之所在位置即視為該待測位置於該測試 空間之座標。 22.如申請專利範圍第21項所述訓練位置資料收集與建構 方法，其中各該訓練位置之特徵向量與梯度資訊之對應 34 年月 日條正替換頁 關係可表示為Ax=c，其中， A = X = C = Xi χι. Pi — y1 Vi ~ y2 Xi — X€y yi — ΩΨ .L 」 ，uij ，U1-J ^2,i 狄冑小平方》析法（Least-Squares Analysis) 旦二出梯度貝訊▽巧_…’其中’ 為會 〜該梯度資訊的訓練位置群組，且該⑽之群組大小 為f。 申明專利範圍第21項所述訓練位置資料收集與建構 方法’其中該資料結構為R樹結構。 〃 •如U利範圍第21項所述訓練位置資料收集與建構 方法，其令該内插模型係為距離反比内插模型 Σ Wi ii€Arr(f) x Σ i⑹x叫 ei5Nr(e) 其中叫="p^p 4為該任一估 、、J位置A代表各該訓練位置，Λ則是該定位系統之一系 ^ Α⑷=H 6¾ x (丨一而）+ χ (?/ -队）’各該训練位置之 該梯度資訊可表示為▽糊 =降，’队⑷為該训練位置 群組。 25.如申請專利範圍第21項所述訓練位置資料收集、建構 與定位方法，其中該數值搜尋技術係經由一梯度搜尋法 35 1376521 尋求該差異化函式之最小值。 6.如申明專利範圍第21項所述訓練位置資料收集、建構 2位方法’其中該數值搜尋技術係選自由最陡崎梯度 搜尋法與切線搜尋法所組成的技術。 27·如申請專利範圍第21項所述訓練位置資料收集、建構 與定位方法，其中該差異化函式係表示為 /(♦>-尸細2’其中，任一位置…[心，福 該比對訊號向量’ ~為各該基地台，】=1·. 該基地台b之訊號強度函式。 36