用於有效地組構網狀網絡模型的系統和方法

2023-07-16 14:07:56

專利名稱：用於有效地組構網狀網絡模型的系統和方法
技術領域：
本發明一般涉及利用移動電子設備的技術，並且更具體地涉及用於有效地組構 (populate)網狀網絡模型的系統和方法。
背景技術：
實現利用移動電子設備的有效方法是當代電子設備的設計者和製造商需要考慮 的重要事情。然而，有效地實現行動裝置可能給系統設計者帶來巨大挑戰。例如，對提高系 統功能和性能的增強的需求可能需要更多的設備處理能力，並且需要額外的設備資源。在 處理或設備需求方面的增長還可能會由於增長的生產成本和操作的低效而導致相應的不 利經濟影響。此外，雖然用於執行各種高級操作的增強的設備能力可以給設備用戶提供額外的 益處，但是也可能使得對各種設備部件的控制和管理的需求增加。例如，實現向設備用戶有 效地提供精確的設備位置信息的增強電子設備可能由於潛在會遇到的不可預測的操作環 境而面臨某些困難。由於對系統資源的日益增長的需求以及在預測各種設備操作條件和環境時的巨 大困難，顯然，開發用於實現和使用移動電子設備的新技術是相關電子技術所關注的事情。 因此，出於所有上述原因，開發用於實現和使用移動電子設備的有效系統仍然是當代電子 設備的設計者、製造商及用戶需要考慮的重要事情。

發明內容
根據本發明，公開了用於有效地組構網狀網絡模型的系統和方法。根據本發明的 一個實施例，電子網絡中的一個或多個行動裝置利用任何有效的技術執行無線掃描過程以 檢測來自電子網絡中的其它對等(peer)行動裝置或其它適當實體的傳輸信號。(一個或多 個)行動裝置測量並存儲與無線掃描過程相對應的無線掃描數據。無線掃描數據可以包括 任何適當的信息，包括但不限於掃描到的各個對等設備的設備標識符和信號強度。在某些實施例中，(一個或多個)行動裝置利用任何有效的傳輸技術向位置服務 器發送所捕獲的無線掃描數據。位置伺服器的設備位置計算器可以利用預先定義的閾值標 準來判斷是否存在足夠的用於成功地執行位置估計計算過程以確定電子網絡中的一個或 多個實體的位置坐標的無線掃描數據。如果已經收集了足夠的無線掃描數據，則位置伺服器的設備位置計算器分析無線 掃描數據以執行位置估計計算過程從而確定電子網絡中的實體的位置坐標。設備位置計算 器可以利用任何有效的計算或估計技術來執行位置估計計算過程。例如，設備位置計算器 可以利用各種已知的或增強型的三角測量技術來估計適當網絡實體的位置。替代地，設備 位置計算器可以利用各種已知的或增強型的概率鬆弛技術來估計適當網絡實體的位置。另 夕卜，某些網絡實體的位置可以直接被測量或者是已知的。設備位置計算器然後可以利用從位置估計計算過程中估計出的位置坐標以及任何測得的或已知的位置坐標來組構或更新網狀網絡模型。位置伺服器隨後可以利用任何適 當且有效的通信技術將網狀網絡模型提供給行動裝置。最後，行動裝置可以有利地利用網 狀網絡模型來有效地執行任何所希望的設備定位過程。因此，鑑於至少上面的原因，本發明 提供了用於有效地組構網狀網絡模型的經改進的系統和方法。


圖IA是根據本發明一個實施例的電子系統的框圖；圖IB是根據本發明一個實施例的圖IA中的行動裝置的框圖；圖2是根據本發明的圖IA中的接入點的一個實施例的框圖；圖3是根據本發明的圖IA中的行動裝置的一個實施例的框圖；圖4是根據本發明的圖3中的MD存儲器的一個實施例的框圖；圖5是根據本發明的圖IA中的位置伺服器的一個實施例的框圖；圖6是根據本發明的圖5中的伺服器存儲器的一個實施例的框圖；圖7是根據本發明的圖4和圖6中的網狀網絡模型的一個實施例的框圖；圖8是圖示出根據本發明一個實施例的設備定位過程的示圖；以及圖9A-9B表示根據本發明一個實施例的用於有效地使用網狀網絡模型的方法步 驟的流程圖。
具體實施例方式本發明涉及對有效使用移動電子設備的改進。提供下面的描述以使得本領域普通 技術人員能夠製造和使用本發明，並且是在專利申請及其要求的背景中來提供下面的描述 的。本領域技術人員將會很容易明了對所公開的實施例的各種修改，並且這裡的一般原理 可以被應用到其它實施例中。因此，本發明不希望被限定到所示出的實施例，而是與符合在 此描述的原理和特徵的最寬範圍一致。本發明在此被描述為用於組構網狀網絡模型的系統和方法，並且包括被配置為利 用無線廣播過程來發送對等設備信號的對等設備。行動裝置無線地檢測對等設備信號以產 生與對等設備相對應的無線掃描數據。位置伺服器隨後可以接收無線掃描數據，以利用無 線掃描數據執行位置估計計算過程，從而確定用於有效地組構網狀網絡模型的位置坐標。
現在參考圖1A，示出了根據本發明一個實施例的電子系統110的框圖。在圖IA實 施例中，電子系統110可以包括但不限於一個或多個行動裝置114、多個衛星118、多個基站 122、位置伺服器126以及多個接入點130。在替代實施例中，電子系統110除了可以利用結 合圖IA實施例論述的那些組件和配置來實現之外，還可以利用其它各種組件和配置來實 現，或者利用替代結合圖IA實施例論述的那些組件和配置的其它各種組件和配置來實現。為了圖示說明的目的，圖IA實施例是利用一個或多個行動裝置114、四個衛星 118、兩個基站122、一個位置伺服器126以及三個接入點130實現的。然而，在各種其它實 施例中，電子系統110可以被實現為包括任何所希望數目的行動裝置114、衛星118、基站 122、位置伺服器126和接入點130。在圖IA實施例中，(一個或多個)行動裝置114可以被實現為其當前的物理位置 可以被確定並傳送給設備用戶或其它適當實體的任何類型的電子設備。例如，在某些實施例中，行動裝置114可以包括但不限於膝上型計算機設備、個人數字助理(PDA)或蜂窩電話。將在下面結合圖3-4進一步討論與行動裝置114的實現和使用有關的其它細節。在圖IA實施例中，衛星118包括但不限於衛星A 118 (a)、衛星B118 (b)、衛星 C 118(c)和衛星D 118(d)，這些衛星是利用任何適當技術實現的以執行任何所希望的功 能或操作。例如，在某些實施例中，衛星118可以被實現為公知的或增強型全球定位系統 (GPS)的一部分。在圖IA實施例中，衛星118通常發送各種衛星信標信號，行動裝置114可 以接收這些衛星信標信號並且利用已知的位置計算過程(例如三邊測量和/或三角測量) 進行分析以潛在地確定行動裝置114的當前物理位置(例如經度、緯度和海拔信息)。然而，在某些情形中，行動裝置114可能不能夠從足夠數目的衛星118接收衛星信 標信號以成功地執行位置計算過程。例如，行動裝置114可能位於阻止一些或所有衛星信 標信號到達行動裝置114的建築或其它結構內部。或者，一個或多個衛星信標信號可能不 具有足夠的信號質量特性。為了從衛星118以外的位置提供其它信號源，圖IA實施例可以 包括基站A 122(a)和基站B 122 (b)，這兩個基站被實現為發送可由行動裝置114接收的導 頻信號的地面設備。與前面的衛星信標信號一樣，行動裝置114可以利用類似位置計算過 程來分析來自基站122的導頻信號，以潛在地確定行動裝置114的當前物理位置。在圖IA實施例中，基站122可以通過利用任何適當的技術來實現以執行任何所希 望的功能或操作。例如，在某些實施例中，基站122可以通過利用任何適當的技術被實現為 已知的或增強型無線廣域網(WWAN)系統的一部分。此外，在某些實施例中，衛星118和基 站122可以被實現為已知的或增強型輔助性全球定位系統(AGPS)網絡的一部分。在某些 實施例中，電子系統110還可以包括位置伺服器126，行動裝置114利用位置伺服器126來 執行各種類型的計算或處理功能從而保存行動裝置114的處理資源。然而，在某些操作環境中，行動裝置114可能仍然不能接收來自衛星118的衛星信 標信號與來自基站122的導頻信號的令人滿意的組合以成功地執行位置計算過程從而精 確地定位行動裝置114。例如，行動裝置114可能位於阻止某些或所有的衛星信標信號和導 頻信號到達行動裝置114的混凝土停車場或購物中心內部。或者，一個或多個衛星信標信 號或基站導頻信號可能不具有足夠的信號質量特性(信號強度、信噪比等)。在圖IA實施例中，為了從衛星118和基站122以外的信號源提供其它信標信號， 圖IA實施例有利地包括接入點130，接入點130被實現為向行動裝置114發送接入點信標 信號的地面設備。與先前討論的衛星信標信號和導頻信號一樣，行動裝置114也可以利用 類似的位置計算過程來分析接入點信標信號，以更精確更有效地確定行動裝置114的當前 物理位置。在圖IA實施例中，接入點130包括但不限於接入點A 130 (a)、接入點B 130(b)和 接入點C 130(c)，這些接入點是通過利用任何適當的技術實現的，以執行任何所希望的功 能或操作。例如，在某些實施例中，接入點130可以利用任何適當的技術被實現為已知的或 增強型無線區域網(WLAN)系統的一部分。在某些實施例中，可以根據WLAN標準來實現接入 點130，WLAN標準包括但不限於已知的802. IlWLAN標準(例如802. Ila, 802. lib, 802. Ilg, 和802. Iln)中的任一個。在接入點130被實現為公共部署的WiFi 「熱點」或其它類似WLAN節點/系統的 某些實施例中，這種WLAN網絡的普遍存在提供了對許多公共位置處的預先存在的潛在接入點130的現成使用。為了成功地利用接入點130來精確地定位行動裝置114，通常使用接 入點資料庫來具體地指示每個接入點130的物理坐標。由於接入點130具有可容易改變的位置，並且由於接入點130可在任何時間被 添加或移除，因此，一種組構並維護接入點資料庫的傳統方法就是僱用一個或多個人帶著 WiFi掃描儀設備開車繞行一區域，來測量並物理地定位任何可用的接入點130。該過程是 耗時的且昂貴的。另外，由於自上次掃描過程後所發生的改變，使得得到的任何接入點數據 庫都可能是不精確的。此外，在某些情形中，接入點相對於試圖利用這些接入點來確定移動 設備114的物理位置的一個或多個行動裝置114，可能完全位於成功地進行無線通信的範 圍之外。因此，本發明提出有利地利用行動裝置114的無線功能來掃描其位置已知的一個 或多個對等行動裝置114或者以其它方式與其位置已知的一個或多個對等行動裝置114 通信。然後，可以將得到的行動裝置掃描數據用來逐漸地創建出表示電子網絡110的網狀 網絡模型。在某些情形中，順序設備定位過程可以被執行來順序地定位位於已知其具體物 理位置的目標行動裝置114與主體行動裝置114之間的一系列居間對等行動裝置114。在 某些實施例中，行動裝置114可以自動地將掃描到的行動裝置測量數據發送給位置伺服器 126或另外的適當實體，以用於組構和更新網狀網絡模型。在下面將結合圖3-9B進一步討 論與網狀網絡模型的創建有關的其它細節。現在參考圖1B，示出了根據本發明一個實施例的圖IA中的行動裝置 114的框圖。 圖IB實施例包括在行動裝置網絡134中的行動裝置1 (114(a))、行動裝置2 (114(b))至移 動設備N(114(c))。在替代實施例中，行動裝置網絡134除了可以利用結合圖IB實施例論 述的那些組件和配置中的某些來實現之外，還可以利用其它組件和配置來實現，或者利用 替代結合圖IB實施例論述的那些組件和配置中的某些的其它組件和配置來實現。此外，移 動設備網絡134可以被實現為包括任何所希望數目的個體設備。在圖IB實施例中，每個行動裝置114可以利用任何所希望的無線通信技術或其它 有效的通信方法來直接與任何其它行動裝置114進行雙向通信。例如，行動裝置1 (114(a)) 可以直接與行動裝置2(114(b))或行動裝置N(114(c)進行雙向通信。類似地，行動裝置 2(114(b))可以直接與行動裝置N(114(c)進行雙向通信。將在下面結合圖4-9B進一步討 論與圖IB行動裝置114的使用有關的其它細節。現在參考圖2，示出了根據本發明的圖IA的接入點130的一個實施例的框圖。在 圖2實施例中，接入點130可以包括但不限於AP中央處理單元(CPU)212、AP收發機214、 AP顯示器216、AP存儲器220以及一個或多個AP輸入/輸出接口(I/O接口)224。從接入 點130的前述組件中選出的組件可以耦合到AP總線228並且通過AP總線228通信。在替 代實施例中，接入點130除了可以利用結合圖2實施例論述的那些組件和配置中的某些來 實現之外，還可以利用其它各種組件和配置來實現，或者利用替代結合圖2實施例論述的 那些組件和配置中的某些的其它各種組件和配置來實現。在圖2實施例中，AP CPU 212可以被實現為包括任何適當且兼容的微處理器設 備，該微處理器設備優選地執行軟體指令從而控制並管理接入點130的操作。在圖2實施 例中，AP存儲器220可以被實現為包括所希望的存儲設備的任意組合，所希望的存儲設備 包括但不限於只讀存儲器(ROM)、隨機存取存儲器(RAM)，以及諸如軟盤、快閃記憶體或硬碟之類的各種類型的非易失性存儲器。在圖2實施例中，AP I/O接口 224優選地可以包括一個或 多個輸入和/或輸出接口以接收和/或發送接入點130的任何所需類型的信息。例如，在 圖2實施例中，接入點130可以利用AP I/O接口 224與任何所希望類型的外部實體進行雙 向通信，以通過利用任何適當的且有效的技術來接收或發送電子信息。在圖2實施例中，接入點130可以利用AP顯示器216通過使用任何有效類型的顯 示技術來顯示任何所希望類型的信息。在圖2實施例中，AP收發機214可以包括用於通過 利用無線通信技術在接入點130與其它設備之間雙向地傳輸(發送和/或接收)電子信息 的任何適當的裝置。例如，接入點130可以利用AP收發機214將任何所希望類型的接入點 信標信號發送給行動裝置114，如上面結合圖IA所討論的。在圖2實施例中，AP收發機214可以生成包括增強型捕獲碼(acquisition code) 的某些類型的增強型接入點信標信號，然後，行動裝置114可以分析該增強型捕獲碼以識 別特定的接入點130並且評估該特定接入點130的信號質量特性。信號質量特性包括但不 限於信號強度特性。將在下面結合圖3-9B進一步討論與接入點130的實現和使用有關的 其它細節。
現在參考圖3，示出了根據本發明的圖IA的行動裝置114的一個實施例的框圖。在 圖3實施例中，行動裝置114可以包括但不限於MD中央處理單元(CPU)312、MD收發機314、 MD顯示器316、MD存儲器320以及一個或多個MD輸入/輸出接口(I/O接口)324。從移動 設備114的前述組件中選出的組件可以耦合到MD總線328並且通過MD總線328通信。在 替代實施例中，行動裝置114除了可以利用結合圖3實施例論述的那些組件和配置中的某 些來實現之外，還可以利用其它組件和配置來實現，或者利用替代結合圖3實施例論述的 那些組件和配置中的某些的其它組件和配置來實現。在圖3實施例中，MD CPU 312可以被實現為包括任何適當且兼容的微處理器設 備，該微處理器設備優選地執行軟體指令從而控制並管理行動裝置114的操作。在圖3實 施例中，MD存儲器320可以被實現為包括所希望的存儲設備的任意組合，所希望的存儲設 備包括但不限於只讀存儲器(ROM)、隨機存取存儲器(RAM)，以及諸如軟盤、快閃記憶體或硬碟之 類的各種類型的非易失性存儲器。將在下面結合圖4進一步討論與MD存儲器320的實現 和使用有關的其它細節。在圖3實施例中，MD I/O接口 324優選地可以包括一個或多個輸入和/或輸出接 口以接收和/或發送行動裝置114的任何所需類型的信息。例如，在圖3實施例中，移動設 備114可以利用MD I/O接口 324與任何所希望類型的外部實體進行雙向通信，以通過利用 任何適當的且有效的技術來接收或發送電子信息。在圖3實施例中，行動裝置114可以利 用MD顯示器316通過使用任何有效類型的顯示技術來顯示任何所希望類型的信息。在圖3實施例中，MD收發機314可以包括用於通過利用無線通信技術在行動裝置 114與其它設備之間雙向地傳輸(發送和/或接收)電子信息的任何適當的裝置。在某些 實施例中，MD收發機314可以包括但不限於用於與衛星118通信的衛星收發機、用於與基 站126通信的基站收發機、用於與接入點130通信的接入點收發機以及用於與對等的移動 設備114通信的行動裝置收發機。將在下面結合圖4-9B進一步討論與行動裝置114的實 現和使用有關的其它細節。現在參考圖4，示出了根據本發明的圖3的MD存儲器320的一個實施例的框圖。在圖4實施例中，MD存儲器320包括但不限於應用程式412、位置檢測器416、衛星模塊420、基站模塊424、接入點模塊428、網狀網絡模型432、無線掃描控制器436以及無線掃描數據 440。在替代實施例中，MD存儲器320除了可以包括結合圖4實施例討論的那些組件和功 能中的某些以外還可以包括其它組件和功能，或者可以包括替代結合圖4實施例討論的那 些組件和功能中的某些的其它組件和功能。在圖4實施例中，應用程式412可以包括優選地被MD CPU 312(圖3)執行以執行 行動裝置114的各種功能和操作的程序指令。應用程式412的特定性質和功能通常取決於 諸如相應行動裝置114的具體類型和特定功能之類的因素而變化。在圖4實施例中，位置檢測器412可以用來協調並管理增強型行動裝置定位過程， 以利用任何有效的技術來確定行動裝置114的當前物理位置。例如，在某些實施例中，位置 檢測器412可以利用網狀網絡模型432中的信息來執行設備定位過程。在某些實施例中， 位置伺服器126 (圖1A)也可以具有與位置檢測器412類似的軟體模塊，以遠程地執行某些 所需要的處理功能。在圖4實施例中，衛星模塊420可以用來管理與衛星118 (圖1A)的通信，並且基站 模塊424可以用來管理與基站122 (圖1A)的通信。類似地，接入點模塊428可以用來管理 與接入點130(圖1A)的通信，並且行動裝置模塊430可以用來管理與對等行動裝置114 (圖 1A)的通信。在圖4實施例中，無線掃描控制器436自動地執行行動裝置掃描過程，以測量來自 一個或多個對等行動裝置114的傳輸的相關特性。無線掃描控制器436然後將任何所收集 的信息存儲為無線掃描數據440。在圖4實施例中，無線掃描數據440可以包括與對等移動 設備114(圖1B)中的各個有關的任何類型的測量信息、數據或其它信息。這種信息的示例 包括但不限於接入點信標信號的存在/可用性、信號強度、信噪比、信號質量特性、信號延 遲以及實際知道的位置坐標等。在圖4實施例中，公開並討論了將位置檢測器416、無線掃描控制器436以及各種 模塊420、424、428和430實現為軟體。然而，在替代實施例中，一些或所有的這些功能可以 通過適當的電子硬體電路來執行，這些電子硬體電路被配置用於執行與這裡討論的軟體模 塊的這些功能相等同的各種功能。將在下面結合圖5-9B進一步討論無線掃描控制器436 的實現和使用。現在參考圖5，示出了根據本發明一個實施例的圖IA的位置伺服器126的框圖。 在圖5實施例中，位置伺服器126包括但不限於伺服器CPTO14、伺服器存儲器518、伺服器 顯示器538以及(一個或多個)I/O接口 540。在替代實施例中，位置伺服器126除了可以 利用結合圖5實施例討論的那些組件和配置中的某些來實現之外，還可以利用其它組件和 配置來實現，或者可以利用替代結合圖5實施例討論的那些組合和配置中的某些的其它組 件和配置來實現。在圖5實施例中，伺服器CPU 514可以被實現為包括任何適當且兼容的微處理器 設備，該微處理器設備優選地執行軟體指令從而控制和管理位置伺服器126的操作。在圖 5實施例中，伺服器存儲器518可以被實現為包括所希望的存儲設備的任意組合，所希望的 存儲設備包括但不限於只讀存儲器(ROM)、隨機存取存儲器(RAM)，以及諸如軟盤、快閃記憶體或 硬碟之類的各種類型的非易失性存儲器。將在下面結合圖6進一步討論與伺服器存儲器518的實現和使用有關的其它細節。在圖5實施例中，I/O接口 540優選地可以包括一個或多個輸入和/或輸出接口 以接收和/或發送位置伺服器126的任何所需類型的信息。例如，在圖5實施例中，位置服 務器126可以利用I/O接口 540與任何所希望類型的外部實體進行雙向通信，以通過利用 任何適當的且有效的技術來接收或發送電子信息。在圖5實施例中，位置伺服器126可以 利用伺服器顯示器538通過使用任何有效類型的顯示技術來顯示任何所希望類型的信息。 將在下面結合圖6-9B進一步討論與位置伺服器126的實現和使用有關的其它細節。現在參考圖6，示出了根據本發明的圖5的伺服器存儲器518的一個實施例的框 圖。在圖5實施例中，伺服器存儲器518包括但不限於伺服器應用622、設備位置計算器 626、無線掃描數據440、網狀網絡模型432、通信模塊638以及雜項信息654。在替代實施例 中，伺服器存儲器518除了可以包括結合圖6實施例討論的那些組件和功能中的某些以外 還可以包括其它組件和功能，或者可以包括替代結合圖6實施例討論的那些組件和功能中 的某些的其它組件和功能。
在圖6實施例中，伺服器應用622以包括優選地被伺服器CPU 514(圖5)執行以 便執行位置伺服器126的各種功能和操作的程序指令。伺服器應用622的特定性質和功能 通常取決於諸如相應位置伺服器126的具體類型和特定功能之類的因素而變化。在圖6實施例中，位置伺服器126使用設備位置計算器626分析來自無線掃描數 據440的適當信息，以通過任何有效的方式確定一個或多個行動裝置114和/或接入點 130(圖1A)的具體位置。例如，設備位置計算器626可以利用無線掃描數據440通過執行 如下面結合圖8討論的基本三角測量計算來計算給定行動裝置114或接入點130的位置坐 標。在其它實施例中，可以利用更複雜的計算技術，通過利用來自行動裝置114的更大數目 的掃描測量，來構建表示一個或多個行動裝置114和/或接入點130的位置的統計模型。在圖6實施例中，設備位置計算器626可以利用新計算出的一個或多個行動裝置 114和/或接入點130的位置來組構並更新網狀網絡模型432。在下面將結合圖7進一步 討論網狀網絡模型432的一個實施例。位置伺服器126以利用通信模塊638來與包括但不 限於行動裝置114在內的任何外部實體進行雙向通信。雜項信息654以包括供位置伺服器 126使用的任何其它信息或數據。將在下面結合圖7-9B進一步討論位置服務126的使用。現在參考圖7，示出了根據本發明的圖4和圖6中的網狀網絡模型432的一個實施 例的框圖。圖7實施例被呈現來用於說明的目的，並且在替代實施例中，網狀網絡模型432 除了可以包括結合圖7實施例討論的那些組件和功能中的某些以外還可以包括其它組件 和功能，或者可以包括替代結合圖7實施例討論的那些組件和功能中的某些的其它組件和 功能。在圖7實施例中，網狀網絡模型432包括但不限於接入點信息714和行動裝置信 息718。在圖7實施例中，接入點信息714包括但不限於各自與電子網絡中的不同接入點 130相對應的一系列條目。在圖7實施例中，每個條目包括但不限於AP標識符，該AP標識 符具體地標識接入點130中的相對應的一個。每個AP標識符與指示特定接入點130的物 理位置的相對應AP坐標相關聯。AP坐標可以包括任何所希望的位置信息，包括但不限於設 備緯度、設備經度以及設備海拔。在圖7實施例中，行動裝置信息718包括但不限於各自與電子網絡中的不同行動裝置114相對應的一系列條目。在圖7實施例中，每個條目包括但不限於MD標識符，該MD 標識符具體地標識行動裝置114中的相應的一個。每個MD標識符與指示特定行動裝置114 的物理位置的相對應MD坐標相關聯。MD坐標可以包括任何所希望的位置信息，包括但不限 於設備緯度、設備經度以及設備海拔。將在下面結合圖8-9B進一步討論網狀網絡模型432 的組構。現在參考圖8，示出了根據本發明一個實施例的設備定位過程的示圖。圖8實施 例被呈現來用於說明的目的，並且在替代實施例中，定位行動裝置114和/或接入點130除 了可以包括結合圖8實施例討論的那些技術和功能中的某些以外還可以包括其它技術和 功能，或者可以包括替代結合圖8實施例討論的那些技術和功能中的某些的其它技術和功 能。在圖8示例中，新的接入點A4 130(d)新近被加入，但是尚未在網狀網絡模型 432(圖4)中被表示出來。本發明有利地利用行動裝置114的無線功能來掃描已知其位置 的一個或多個對等行動裝置114或者以其它方式與已知其位置的一個或多個對等移動設 備114通信。然後，得到的無線掃描數據440可以用來逐漸地組構或更新網狀網絡模型432， 從而表示相對應的電子網絡。
在圖8示例中，順序設備定位過程可以被執行來順序地定位位於目標行動裝置Dl 114(a)(其具體物理位置為已知的)與主體行動裝置D4114(d)(其位置必須被找到)之間 的一系列居間對等行動裝置D2 114(b)和D3 114(c)。一旦得知了行動裝置D4 114(d)的 位置，就可以利用D4 114(d)以及其它附近的已知行動裝置(例如D5 114(e))來精確地定 位新的接入點A4 130(d)。在某些實施例中，行動裝置114可以自動地將無線掃描數據440 發送給位置伺服器126或另外的適當實體，以用於組構並更新網狀網絡模型432。在圖8示例中，行動裝置Dl 114(a)的位置可以被精確地定義。通過利用任何有 效的手段得知了其位置的三個接入點130 (Al 130(a)、A2130(b)和A3 130(c))已經在網狀 網絡模型432中被定義，並且位於行動裝置Dl 114(a)的無線掃描範圍內。在圖8實施例 中，設備114(a)掃描並檢測來自接入點130(a)、130(b)和130(c)的接入點信號。在圖8 實施例中，設備114(a)然後將每個掃描到的接入點130的AP標識符和信號強度記錄為無 線掃描數據440。行動裝置114(a)然後可以根據測得的無線掃描數據440評估信號強度，以標識 出具有半徑Rl 822的位置圓圈818，半徑Rl 822表示從設備114(a)到掃描到的接入點 130(a)的距離。類似地，行動裝置114(a)可以根據無線掃描數據440評估信號強度以創建 具有半徑R2 828的位置圓圈824，半徑R2 828表示從設備114 (a)到接入點130(b)的距 離。另外，行動裝置114(a)可以根據無線掃描數據440評估信號強度以創建具有半徑R3 836的位置圓圈832，半徑R3 836表示從設備114(a)到接入點130(c)的距離。在圖8示 例中，行動裝置Dl 114(a)的位置可以被定義為所有三個位置圓圈818、824和832相交的 點，或者可以被定義為可以通過利用三個半徑向量822、824和836進行三角測量的唯一點。 一旦得知了 Dl 114(a)的具體位置，就可以將該位置信息用來更新網狀網絡模型432。根據上述的順序設備定位過程，接下來，可以參考已知的行動裝置Dl 114(a)的 位置來估計行動裝置D2 114(b)的位置。實際上，D2 114(b)位於從Dl 114(a)起沿著信 號路徑844的無線傳輸範圍內。因此，D2 114(b)可以利用已知的Dl 114(a)的位置(可能地結合在無線傳輸範圍內的任何其它已知設備)來計算D2 114(b)的估計的位置坐標。類似地，可以參考估計的D2 114(b)的位置來估計行動裝置D3 114(c)的位置。 實際上，D3 114(c)位於從D2 114(b)起沿著信號路徑848的無線傳輸範圍內。因此，D3 114(c)可以利用估計出的D2 114(b)的位置(可能地結合在無線傳輸範圍內的任何其它已 知設備)來計算D3 114(c)的估計的位置坐標。最後，可以參考估計的D3 114(c)的位置來估計行動裝置D4 114(d)的位置。實際 上，D4 114(d)位於從D3 114(c)起沿著信號路徑852的無線傳輸範圍內。因此，D4 114(d) 可以利用估計出的D3 114(c)的位置(結合已知的行動裝置D5 114(e)以及在無線傳輸範 圍內的任何其它已知設備)來計算D4 114(d)的估計的位置坐標。根據本發明，根據順序設備定位過程得到的行動裝置Dl 114(a)、D2 114(b)、D3 114(c)和D4 114(d)的位置可以被發送給位置伺服器126 (圖1)，以便被添加到網狀網絡 模型432中。另外，一旦估計出了 D4 114(d)的位置，則可以估計出新的接入點A4 130(d) 的位置，這是因為如傳輸圓圈836和半徑向量R4 840所示的，設備D4 114(d)位於接入點 A4 130(d)的傳輸範圍內。在某些情形中，還可以利用在傳輸範圍內的任何其它已知設備 (未示出)來改善接入點A4 130(d)的位置坐標。在某些實施例中，行動裝置D4 114(d)可以將與接入點A4 130(d)相對應的無線 掃描數據440發送給位置伺服器126以用於估計接入點A4 130(d)的位置。在估計出了接 入點A4 130(d)的位置坐標之後，該新的位置信息可以被添加到網狀網絡模型432中以更 精確地表示電子網絡。根據本發明，行動裝置114可以執行連續的或定期的掃描過程，以基 於接入點130、行動裝置114或任何其它適當實體的設備位置的最近的改變來動態地更新 或進一步組構網狀網絡模型432。將在下面結合圖9A和9B討論組構網狀網絡模型432的 其它技術。現在參考圖9A-9B，示出了根據本發明一個實施例的用於高效地創建和使用網狀 網絡模型432的方法步驟的流程圖。圖9A-9B的示例被呈現來用於說明的目的，並且在替 代實施例中，本發明可以利用除結合圖9A-9B的實施例討論的那些步驟和序列以外的步驟 和序列。在圖9A實施例中，在步驟912中，電子網絡中的一個或多個行動裝置114通過利 用任何有效技術來執行無線掃描過程，以檢測來自電子網絡中的其它對等行動裝置114或 其它適當實體的傳輸信號。在步驟914，(一個或多個)行動裝置114測量並存儲與無線掃 描過程相對應的無線掃描數據440。無線掃描數據440可以包括任何適當的信息，包括但不 限於各個掃描到的對等設備114的設備標識符和信號強度。在步驟916，(一個或多個)行動裝置114利用任何有效的傳輸技術將捕獲的無線 掃描數據440發送給位置伺服器126。在步驟918，位置伺服器126的設備位置計算器626 利用預定的閾值標準來判斷是否存在足夠的用於成功地執行位置估計計算過程以確定電 子網絡中的一個或多個實體的位置坐標的無線掃描數據440。如果已經收集了足夠的無線 掃描數據440，則圖9A的處理通過連接字符「A」前進到圖9B的步驟920。在步驟920，位置伺服器126的設備位置計算器626分析無線掃描數據440，以執 行位置估計計算過程從而確定電子網絡中的一個或多個實體的位置坐標。在圖9B實施例 中，設備位置計算器626可以利用任何有效的計算或估計技術來執行位置估計計算過程。例如，設備位置計算器626可以利用各種已知的或增強型的三角測量技術來估計適當網絡 實體的位置。替代地，設備位置計算器626可以利用各種已知的或增強型的概率鬆弛技術 來估計適當網絡實體的位置。另外，某些網絡實體的位置可以直接被測量或者是已知的。可以在下面的四個參考文獻中找到與前面的概率鬆弛技術有關的進一步的 細節，通過引用將四個參考文獻結合於此。1) S. Geman和D. Geman的「Stochastic relaxation,Gibbs distributions，and the Bayesian restoration ofimages，，，IEEE Trans. Pattern Analysis and Machine Intelligence，vol.6, pp. 721-741， 1984 ；2)R.A. Hummel 禾口 S. W. Zucker 的 「On the foundationsof relaxation labeling process，，，IEEE Trans. Pattern Analysis and MachineIntelligence, vol. 5， no. 3, pp.267-286, May 1983 ；3)J.Kittler 禾口 E.R.Hancock 的「Combining evidence in probabilistic relaxation,，，Int' 1 J.PatternRecognition and Artificial Intelligence，vol.3，pp. 29-51，1989 ；4)J. Pearl. Probabilistic Reasoning in Intelligent Systems. Networks of Plausible Inference. Morgan Kaufmann，1988。
在步驟922，設備位置計算器626利用從位置估計計算過程中估計出的位置坐標 以及任何測得的或已知的位置坐標來組構或更新網狀網絡模型432。在步驟924，位置服務 器126隨後可以利用任何適當且有效的通信技術將網狀網絡模型432提供給行動裝置114。 最後，在步驟926，行動裝置114可以有利地利用網狀網絡模型432來有效地執行任何所希 望的設備定位過程。因此，鑑於至少上面的原因，本發明提供了用於有效地組構網狀網絡模 型的經改進的系統和方法。已經參考某些實施例說明了本發明。根據本公開，本領域技術人員將會清楚其它 實施例。例如，可以利用除了在上述實施例中描述的那些配置和技術以外的某些配置和技 術來實現本發明。另外，可以結合除了上述那些系統以外的系統來有效地使用本發明。因 此，本發明意圖涵蓋對上述實施例的這些和其它變體，本發明僅僅由所附權利要求來限定。
權利要求
一種用於組構網絡實體的網狀網絡模型的系統，包括對等設備，被配置為通過利用無線廣播過程來發送對等設備信號；以及行動裝置，所述行動裝置無線地檢測所述對等設備信號以產生與所述對等設備相對應的無線掃描數據，所述網狀網絡模型是通過分析所述無線掃描數據、利用所述對等設備和所述行動裝置的位置坐標來組構的。
2.如權利要求1所述的系統，還包括接收所述無線掃描數據的位置伺服器，所述位置 伺服器利用所述無線掃描數據執行位置估計計算過程以確定用於組構所述網狀網絡模型 的所述位置坐標。
3.如權利要求2所述的系統，其中，所述行動裝置和所述對等設備使用所述網狀網絡 模型，參考來自所述網狀網絡模型的所述位置坐標執行設備定位過程。
4.如權利要求3所述的系統，其中，所述網絡實體包括所述行動裝置、所述對等設備和 無線接入點。
5.如權利要求1所述的系統，其中，順序設備定位過程被執行來順序地定位在位置未 知的主體行動裝置與位置已知的目標對等設備之間的一系列居間對等移動設 備，所述順序 設備定位過程順序地確定從所述目標對等設備開始到所述主體行動裝置的所述居間對等 行動裝置的各自的設備位置，直到所述主體行動裝置被定位為止。
6.如權利要求1所述的系統，其中，所述行動裝置和所述對等設備由個人計算機設備 實現，所述無線掃描數據包括所述對等設備的設備標識符和信號強度，所述行動裝置自動 地捕獲所述無線掃描數據而無需設備用戶的輔助。
7.如權利要求1所述的系統，其中，所述位置伺服器通過執行基於所述無線掃描數據 的三角測量過程來執行所述位置估計計算過程。
8.如權利要求1所述的系統，其中，所述位置伺服器通過利用基於所述無線掃描數據 的概率鬆弛技術來執行所述位置估計計算過程。
9.如權利要求4所述的系統，其中，所述網狀網絡模型包括所述行動裝置的行動裝置 位置信息、所述對等設備的對等設備位置信息、和所述接入點的接入點位置信息，所述移動 設備自動且連續地掃描所述對等設備信號以產生並存儲所述無線掃描數據，所述無線掃描 數據包括所述對等設備信號各自的信號檢測指示符、所述對等設備信號的信號強度、所述 對等設備信號的信噪值、所述對等設備信號的信號質量特性、所述對等設備信號的信號延 遲、以及所述對等設備的任何已知的位置坐標。
10.如權利要求9所述的系統，其中，所述行動裝置利用無線傳輸技術向所述位置服務 器發送所述無線掃描數據，所述位置伺服器在執行所述位置估計計算過程之前判定收集了 足夠量的所述無線掃描數據，所述位置伺服器基於根據所述無線掃描數據計算出的所述位 置坐標來逐漸地組構或更新所述網狀網絡模型，所述位置伺服器將更新版本的網狀網絡模 型發送給所述行動裝置，所述行動裝置和所述對等設備將所述更新版本的所述網狀網絡模 型用於執行設備定位過程。
11.一種用於創建和使用網絡實體的網狀網絡模型的行動裝置，包括應用程式，所述應用程式無線地檢測從對等設備發送來的對等設備信號以產生與所述 對等設備相對應的無線掃描數據，所述網狀網絡模型是通過分析所述無線掃描數據利用所 述對等設備和所述行動裝置的位置坐標組構的；以及處理器，用於控制所述應用程式以創建和使用所述網狀網絡模型。
12.如權利要求11所述的行動裝置，其中，位置伺服器接收所述無線掃描數據，所述位 置伺服器利用所述無線掃描數據執行位置估計計算過程以確定用於組構所述網狀網絡模 型的所述位置坐標。
13.如權利要求12所述的行動裝置，其中，所述行動裝置和所述對等設備使用所述網 狀網絡模型，參考來自所述網狀網絡模型的所述位置坐標執行設備定位過程。
14.如權利要求13所述的行動裝置，其中，所述網絡實體包括所述行動裝置、所述對等 設備和無線接入點。
15.如權利要求14所述的行動裝置，其中，順序設備定位過程被執行來順序地定位在 位置未知的所述行動裝置與位置已知的目標對等設備之間的一系列居間對等行動裝置，所 述順序設備定位過程順序地確定從所述目標對等設備開始到所述行動裝置的所述居間對 等行動裝置的各自的設備位置，直到所述行動裝置被定位為止。
全文摘要
本發明公開了用於有效地組構網狀網絡模型的系統和方法。用於組構網狀網絡模型的系統和方法包括被配置為利用無線廣播過程來發送對等設備信號的對等設備。行動裝置無線地檢測對等設備信號以產生與對等設備相對應的無線掃描數據。位置伺服器隨後可以接收無線掃描數據，以用於利用無線掃描數據執行位置估計計算過程，從而確定用於有效地組構網狀網絡模型的位置坐標。
文檔編號H04W84/12GK101835089SQ201010129199
公開日2010年9月15日 申請日期2010年3月9日 優先權日2009年3月9日
發明者周易, 尼考勞斯·喬治斯, 費瑞德瑞克·卡皮奧 申請人:索尼公司;索尼電子有限公司