用於無線通信系統的定位方法及其相關裝置的製作方法

2023-05-29 16:33:46 1

專利名稱：用於無線通信系統的定位方法及其相關裝置的製作方法
技術領域：
本發明是指一種用於無線通信系統的定位方法及其相關裝置，尤指一種用於無線 通信系統中根據接收信號強度數據，以圖形模型估測一目標裝置的位置的方法及其相關裝置。
背景技術：
在無線通信系統中，定位(Positioning)技術廣泛應用於急難救助系統、位置導 向式付費系統(Location-based Billing Service)、長者及病患的看護服務、以及消防或 戰地勤務中人員的定位等，以取得目標物(Target)的位置。收訊時間法(或稱信號傳送時 |1]， Time ofArrival, T0A)(AngleofArrival, Α0Α) ^^itl^iSfe (Received Signal Strength, RSS)為常見的定位技術，收訊時間法是以三個基站所測量的接收信號 的傳播時間乘上傳播速度，分別求得基站與目標物的距離，接著以各個基站為圓心，與目標 物的距離為半徑畫圓，三圓的交會點即目標物的位置；收訊角度法是決定兩個基站所測量 的接收信號的來源方向，並以各個基站的位置為起點形成直線，兩直線的交會點即目標物 的位置；收訊強度法是利用三個基站所測量的接收信號強度及預先建立的信號傳輸衰減模 型，分別求得基站與目標物的距離，接著以各個基站為圓心，與目標物的距離為半徑畫圓， 決定目標物的位置。在後文中，可進行定位運算的無線通信系統簡稱為定位系統。在室內環境中，由於擺設複雜，其中的無線電信號傳播多屬於非直視(或稱非視 線可及，Non-Line of Sight,NL0S)傳播，並且多路徑(Multipath)效應也相當明顯。上述 收訊時間法及收訊角度法受多路徑效應的影響較大，估測目標物的位置時容易產生誤差。 相對來說，當目標物移動時，其接收信號強度的變化容易預測，因此收訊強度法較收訊時間 法及收訊角度法更適用於室內定位系統。在室內定位系統中，使用接收信號強度數據定位的算法主要分為兩類樣式辨認 (Pattern-recognition)算法及模型式(Model-based)算法。在樣式辨認算法中，目標物 的位置是根據目標物的接收信號強度與已知的多個訓練序列點(Training Point)所對應 的接收信號強度推算而得，如RADAR算法及LANDMARC算法，詳細內容請參考論文「RADAR An in-building RF-baseduser location and tracking system" in Proc. IEEE INF0C0M 2000, vol. 2, Mar. 2000 R ^"LANDMARC Jndoor location sensing using active RFID」in PerCom' 03，Mar. 2003。請參考圖1，圖1為現有技術的無線通信網路10的示意 圖。無線通信網路10包含有定位系統100、目標裝置102及基站(BaseStation)AP1 AP4。 圖1中定義基站AP1 AP4所在的室內環境為測試區域，劃分為多個方形且面積均等的單 元，每個單元的四個頂點即訓練序列點。於目標裝置102尚未進入測試區域時，各基站會先 進行離線訓練(OfflineTraining)，以取得每一訓練序列點的位置所對應的接收信號強度 數據，並將這些接收信號強度數據傳送至定位系統100中的位置資料庫。訓練序列點所對 應的接收信號強度數據假設為零誤差。當目標裝置102進入測試區域，目標裝置102將會 回報對應於各個基站的接收信號強度數據至定位系統100 ；接著，定位系統100根據接收到的接收信號強度數據，進行RADAR算法或LANDMARC算法，求出目標裝置102的位置。RADAR算法是從位置資料庫中，找出與目標裝置102所傳送的接收信號強度數據 最接近的k個接收信號強度數據所對應的k個訓練序列點，進行訓練序列點的位置的平 均運算，以決定目標裝置102的位置。然而，每個進行平均的k個訓練序列點的數據可靠 度不一定相同，取平均將導致定位結果與實際的目標位置之間的誤差很大。LANDMARC算 法則是進一步對k個訓練序列點的位置分配以不同的權重值，再對加權過後的位置取加 權平均值，以決定目標裝置102的位置；權重值為目標裝置102所傳送的接收信號強度數 據與k個訓練序列點中各個訓練序列點所對應的接收信號強度數據之間的歐幾裡得距離 (Euclidean Distance)。然而，接收信號強度的歐幾裡得距離無法正確反映地理上的距離。 此外，上述RADAR算法及LANDMARC算法皆未考慮接收信號強度的測量誤差，對於定位的精 確度的提升效果有限。另一方面，模型式算法是根據預先建立的無線信號傳輸模型(RadioPropagation Model)及測得的接收信號強度，先計算出目標物與三個基站之間的距離，再以三角算法決 定目標位置。模型式算法的缺點在於需要龐大的信道測量數據才能建立室內的無線信號傳 輸模型，並且由於室內環境的複雜度高，精確的無線信號傳輸模型不容易建立，將影響定位 的準確度。除了上述樣式辨認算法及模型式算法之外，室內定位系統還可根據最大相似度 (Maximum Likelihood)算法求得目標位置，但最大相似度算法的運算複雜度極高，對室內 定位系統來說是一大負荷。由上可知，現有技術算法所能提供的定位精確度有限。

發明內容
因此，本發明的主要目的即在於提供一種用於無線通信系統的定位方法及裝置， 以精確地對目標裝置進行定位，同時降低運算複雜度。本發明公開一種用於無線通信系統的定位方法，用來估測目標裝置的位置，該定 位方法包含有接收該目標裝置進入一區域時所測量的對應於多個基站的多個接收信號強 度數據；以及根據該多個接收信號強度數據，利用圖形模型估測該目標裝置的位置。本發明還公開一種用於無線通信系統的裝置，用來執行前述方法，以對目標裝置 進行定位。


圖1為現有技術的無線通信網路的示意圖。圖2為本發明實施例一流程的示意圖。圖3為本發明實施例一功率衰減圖的示意圖。圖4為本發明實施例一因子圖的示意圖。圖5A為無線區域網路的路由器在室內空間中的平面配置圖。圖5B、圖5C及圖5D為圖5A中路由器所對應的功率衰減圖。主要組件符號說明10無線通信網路100定位系統102目標裝置
AP1 APn 基站20 流程200、202、204、206、208、210、212、214、216 步驟
具體實施例方式本發明根據接收信號強度數據的軟信息(即對應於接收信號強度數據的高斯機 率密度函數)，利用一圖形模型(Graphical Model)對一目標裝置進行定位。請參考圖2，圖2為本發明實施例一流程20的示意圖，流程20用於一定位系統，用 來對一目標裝置進行定位。流程20假設定位系統設於一區域中，其中設有基站AP1 APn。 基站AP1 APn可檢測到進入測試區域的目標裝置並且傳送無線電信號至目標裝置，同時， 定位系統可接收來自各基站及目標裝置的接收信號強度數據。流程20包含以下步驟步驟200:開始。步驟202 取得每一基站APi進行離線訓練所得的測試區域中所有訓練序列點的 接收信號強度數據，以建立基站AP1 APn的功率衰減圖(Power DecayProfile)PDP1 PDPn, i = 1，2，…，N。步驟204 接收一目標裝置進入該測試區域時所測量的對應於基站AP1 APn的接 收信號強度數據Αα, ~ Pw,ν,。步驟206 找出對每一基站APi而言該目標裝置所在的該測試區域其中一單元。步驟208 根據該單元的四個頂點的坐標及其對應的對數的接收信號強度數據 P1Jj-WA，產生對應於基站APi的一超平面方程式，進而產生對應於基站AP1 APn的N個超 平面方程式。步驟210 對接收信號強度數據Aai ~ Λ，,,的每一接收信號強度數據進行對 數運算，產生對數的接收信號強度數據A,, ~ Pn,。步驟212 產生對應於對數的接收信號強度數據為,，~ Av,的高斯機率密度函數 Gz(Z)1 Gz (ζ) Ν。步驟214 利用一因子圖(Factor Graph)估測該目標裝置的位置。步驟216:結束。在流程20中，步驟202是定位系統於目標裝置進入測試區域之前進行的工作。測 試區域是定位系統及基站AP1 APn所在的區域，劃分為多個方形且面積均等的單元，每一 單元的四個頂點即訓練序列點，相關示意圖請參考圖1。在目標裝置進入測試區域之前，每 一基站APi會先進行離線訓練，取得每一訓練序列點(\，yp的位置所對應的零誤差的接收 信號強度數據，傳送至定位系統中的位置資料庫，j表示訓練序列點的序號。因此，對定 位系統來說，每一訓練序列點的坐標以及對應的接收信號強度數據為已知。根據步驟202， 定位系統根據每一訓練序列點的坐標以及離線訓練所得的多個接收信號強度數據建 立基站APi的功率衰減圖PDPi,因此得以建立基站AP1 APn的功率衰減圖PDP1 PDPN。請 參考圖3，圖3為本發明實施例一功率衰減圖的示意圖。每一功率衰減圖是一坐標系統為 (X，1，P)的連續的三維曲面，(X，y)表示測試區域中的位置坐標，P軸為對數(Logarithm) 的接收信號強度數據。以&表示訓練序列點(Xph)所對應的接收信號強度數據取對數的值，則(弋，兄，A,,)為功率衰減圖PDPi的三維曲面上的一點。為了簡化功率衰減圖中位置坐標與對數的接收信號強度數據之間的非線性關係， 本發明使用局部線性(Local Linearization)技術仿真功率衰減圖，將功率衰減圖的三維 曲面視為多個單位曲面的集合，如圖3所示。每一單位曲面的四個頂點的(X，y)坐標等於 測試區域的一單元的四個頂點，即訓練序列點。本發明令每一單位曲面趨近於三維平面，稱 為超平面(Hyperplane)，此超平面方程式表示如下ax · x+ay · y+ap · ρ = c，(1)其中ax，ay, ap為超平面方程式的係數，c為非零的常數。步驟204至步驟208，簡言之，是產生對應於目標裝置所在的單元的超平面方程 式，詳述如下。在目標裝置進入測試區域時，定位系統接收目標裝置所測量的對應於基站 AP1 APn的接收信號強度數據~ Knf，在考慮測量誤差的情形下，對應於基站APi的 接收信號強度數據A^i表示如下列方程式Pw^t = pWA! + Hi 』(2)其中A^i等於零誤差的接收信號強度^viv,,與一測量誤差Ii1的總和，測量誤差Ii1為 一高斯機率密度函數。接著，定位系統在測試區域中找出一單元Ci,單元Ci的四個頂點坐標所對應的接 收信號強度數據Λ，_=,,2,3,4與目標裝置所測量的接收信號強度數據/V,，,之間的歐幾裡得距 離的總和為最小值，由此可知目標裝置位於單元Ci中。由於訓練序列點的坐標及其對應的 對數的接收信號強度數據可根據已建立的功率衰減圖而得知，得到以下的聯立方程式αχ ι ■ Xj + ay i · y} + αρ ι ■ pt j = c , i = Y,2,…N, j = 1,2,3,4 ,(3)其中(\，yp為第j個訓練序列點的坐標，A，,為對應的對數的接收信號強度數據。 因此，係數ax, 」 ay, 」 ap,,可根據式3取得，進而產生一超平面方程式如下ax, i · x+ay, i · y+ap, j · Pijt = c,(4)其中Pi, t表示目標裝置所測量的接收信號強度數據的變量，χ, y表示目標位置的 變量。類似地，定位系統利用式3的聯立方程式，取得對應於基站AP1 APn的所有平面方 程式。在流程20中，步驟210至步驟212可與前述的步驟206至步驟208同時間進行。 在步驟210中，定位系統分別對接收信號強度數據Am, ~ A^v,,進行對數運算，產生對數的 接收信號強度數據A, ~ pn,，每一對數的接收信號強度數據式,表示如下列方程式pht = 101ogl0(pW ! t + ,) 『(5)由式5可知，在考慮測量誤差的情形下，對數的接收信號強度數據A,,的機率密度 函數趨近於一高斯機率密度函數。在步驟212中，定位系統進一步根據A,, ~鄉~產生相對 應的高斯機率密度函數Gz (ζ)工 Gz (ζ) N。最後，本發明利用因子圖估測目標裝置的位置。因子圖為圖形模型的一種，用 來處理變量與函式間的關係，可簡化位置估測及追蹤時所需的複雜運算。請參考圖4， 圖4為本發明實施例一因子圖的示意圖。在圖4中，各函式以方塊表示，又稱為限制節 點(Constraint Node)或代理節點(Agent Node)，用來表示局部的限制條件(Local Constraint)；變量以圓形表示，稱為變量節點(Variable Node)。圖4的因子圖中有兩種限制節點，Pi&Mi，Pi表示根據對數的接收信號強度數據眾,產生高斯機率密度函數Gz(Z)i的 函式，Mi表示式4的超平面方程式。由圖4可知，變數節點Pi, t即高斯機率密度函數Gz(Z) i ；式4中的所有變量，包含坐標X，y,皆是高斯機率密度函數形式的軟信息。本領域技術人 員可根據圖4的因子圖推導得知變量節點與限制節點間互相傳送的軟信息的相關函式，在 此不詳述。當因子圖的執行次數達到預定的次數時，最後的χ坐標的機率密度函數的平均 值及y坐標的機率密度函數的平均值，即是定位系統所估測的目標裝置的坐標。請注意，利用因子圖估測目標位置僅為本發明的一實施例，在本發明其它實施例 中，可用其它圖形模型如常態圖(Normal Graph)或坦納圖(TarmarGraph)以進行目標裝置 的定位。上述兩種圖形模型皆為因子圖的轉換表示。在無線通信網路中，基站與被定位的 目標裝置是根據不同的需求而定義。就硬體實現而言，定位系統可能是獨立設置，亦可能設 置於基站側或目標裝置側。例如，對全球衛星定位系統(Global Position System)而言， 基站是定位衛星，目標裝置則是導航裝置或接收天線，定位系統通常設置於目標裝置；對無 線區域網路系統而言，基站是無線網絡接取器(Access Point)，目標裝置是無線網卡或相 關網絡設備，定位系統通常設置於基站；另外，對射頻辨識(RFID)系統而言，射頻辨識讀取 器(Reader)是基站，射頻辨識標籤(Tag)則是目標裝置，定位系統可能設置於基站或獨立 設置。請注意，由於本發明可顯著改善多路徑效應造成的定位不準確，因此較合適用於室內 定位系統，但不局限用於室內定位系統。請參考圖5A至第5D圖，圖5A為無線區域網路的路由器(Router)在一室內空間 中的平面配置圖，此室內空間中設置有3個路由器AP1 AP3，可估測一無線網絡卡的位置。 第5B、5C、5D圖分別為路由器APpAPyAP3K對應的功率衰減圖。在圖5A至第5D圖所示的 環境及接收信號強度的測量誤差固定為0. 2483X10_8瓦特的條件下，根據本發明實施例的 流程20、現有技術4-NN(4Nearest Neighbor)算法(類似RADAR算法)、LANDMARC算法及 最大相似度算法所估測的目標位置的精確度分別為1. 01m、2. 52m、l. 42m、0. 97m。使用流程 20所得定位精確度明顯優於現有技術4-NN算法及LANDMARC算法，並且與最大相似度算法 所得相當接近。綜上所述，本發明考慮了接收信號強度數據的可靠度，在因子圖中根據目標裝置 測量的接收信號強度數據所對應的高斯機率密度函數，估測目標裝置的位置。借著因子圖 的可簡化運算的特性，本發明大幅降低了定位系統的複雜度，同時使定位精確度接近最佳 化。以上所述僅為本發明的較佳實施例，凡依本申請權利要求範圍所做的均等變化與 修飾，都應屬本發明的涵蓋範圍。
權利要求
一種用於無線通信系統的定位方法，用來估測目標裝置的位置，該定位方法包含有接收該目標裝置進入一區域時所測量的對應於多個基站的多個接收信號強度數據；以及根據該多個接收信號強度數據，利用圖形模型估測該目標裝置的位置。
2.如權利要求1所述的方法，其中該圖形模型包含有多個限制節點，用來表示多個平 面方程式及多個用來產生對應於該多個接收信號強度數據的多個高斯機率密度函數的函 式，該多個平面方程式中每一平面方程式用來根據該多個高斯機率密度函數其中一對應的 高斯機率密度函數，估測該目標裝置的位置。
3.如權利要求2所述的方法，其另包含有根據該多個接收信號強度數據及多個功率衰減圖，產生該多個平面方程式，該多個功 率衰減圖中每一功率衰減圖用來表示該區域中多個預設位置與該多個預設位置相對於該 多個基站其中一基站的多個零誤差的接收信號強度數據間的關係。
4.如權利要求3所述的方法，其中該多個平面方程式中每一平面方程式所形成的平面 趨近於該多個功率衰減圖中一對應的功率衰減圖的曲面的一部分。
5.如權利要求2所述的方法，其中該多個用來產生該多個高斯機率密度函數的函式， 是根據對數形式的該多個接收信號強度數據，產生該多個高斯機率密度函數。
6.如權利要求1所述的方法，其另包含有在該目標裝置進入該區域之前，根據該區域中多個預設位置以及該多個預設位置相對 於該多個基站中每一基站的多個零誤差的接收信號強度數據，建立多個功率衰減圖。
7.如權利要求1所述的方法，其中該圖形模型是一因子圖或該因子圖的轉換型。
8.一種用於無線通信系統的裝置，用來執行權利要求1所述的方法，以對目標裝置進 行定位。
全文摘要
用於無線通信系統中估測目標裝置的位置的定位方法，包含有接收該目標裝置進入一區域時所測量的對應於多個基站的多個接收信號強度數據；以及根據該多個接收信號強度數據，利用圖形模型估測該目標裝置的位置。
文檔編號H04W64/00GK101924986SQ20091014065
公開日2010年12月22日 申請日期2009年6月10日 優先權日2009年6月10日
發明者吳承軒, 陳俊才, 黃金增 申請人:雷凌科技股份有限公司