200850056 九、發明說明： 【發明所屬之技術領域】 本系統及方法係關於決策樹中機率的重新計算，其中將 節點自動指派給其在網路内的正確空間位置，例如無線控 制燈照陣列。 【先前技術】 典型無線燈照陣列包含大量電性驅動燈源，例如，其通 常係定位成提供均勻光分佈。陣列内之燈源通常位於房間200850056 IX. Description of the Invention: [Technical Field of the Invention] The system and method relate to the recalculation of the probability in a decision tree in which nodes are automatically assigned to their correct spatial locations within the network, such as a wireless control light array. [Prior Art] A typical wireless light illumination array contains a large number of electrically driven light sources, for example, which are typically positioned to provide a uniform light distribution. The light source in the array is usually located in the room
天花板内的格柵或晶格配置中，以便其間具有均勻間隔。 將此一燈照陣列内的個別燈源之各者調適成能夠在無線 通信網路上與其他燈源通信，其係藉由相關聯通信節點之 陣列形成。網路内之通信節點之各者位於燈照陣列内其相 關聯燈源的位置。因此，燈照陣列與通信網路之空間結構 等效。 k信網路提供燈照陣列可在安裝後自動委任的構件。然 而，網路内之個別節點無法提供其本身之位置資訊，所 以，不知道哪一燈源與哪一節點相關聯。可委任陣列前， 經由各種熟知方法建立各節點在通信網路内之空間位置， 例如包括經由手動操作者輸人，以便可將各節點指派給正 確燈源。 藉由三角測量程序找到通信節點之位置，例如U 於由無線通信網路提供之範圍資料。範圍資料係以以二 :㈣内，通信節點對之間採用的範圍測量之形式提供:、直 妾攸该等範圍測量導出兩個節點間之範圍的計算，其係使 130169.doc 200850056 用熟知技術執行，例如使用在各種節點及/或燈源間交換 的信號之接收信號強度指示（RSSI)或飛行時間資訊。 RSSI情形中，在一對通信節點間交換之無線電信號的接 收強度用於計算其間範圍。發射信號的強度之降低速率與 行進距離成反比且與信號波長成正比。因此，考慮到波 長，可根據接收節點處發射之信號的衰減計算節點對間的 距離。 在飛行時間測量情形中，藉由測量無線電信號在其間行 進所用的時間計算一對通信節點間的範圍。由於無線電信 號以光速行進，節點對間的飛行時間之準確測量致能其間 距離的準確計算。 然而’該等類型之範圍測量經歷錯誤，因此通信節點之 所導出位置通常與配置燈源之格柵或晶格配置上的位置未 完全匹配。所以，關於哪一光源與各節點相關聯仍存在某 些不確定性。 為了成功委任無線燈照陣列，必須將通信節點指派給其 正確格栅或晶格位置，從而指派給燈照陣列内之燈源。若 將通信節點指派給不對應於其實際晶格位置的晶格位置， 通信網路之所導出空間結構將係錯誤的，因此燈照陣列不 會正確運作。 為了解析通信節點之位置的此類不確定性，可將藉由三 角測量導出之位置與一樣板比較，其定義燈照陣列内之燈 源的晶格位置。藉由此方法，可將通信節點指派給與所二 出位置最接近之燈源。接著可將新位置用作其他通信節點 130169.doc 200850056 之三角測量中的參考點。依此方式，藉由三角測量程序導 出之位置的錯誤不會累積。 然而，存在將個別通信節點指派給錯誤位置的風險，即 不對應於其實際位置的位置。此情形中，使用該位置以建 他通乜節點之位置導致較大錯誤之累積。此類錯誤可 變知很大，使彳于其阻止建立燈照陣列之總體佈局。 【發明内容】 用於無線燈照之自動委任的各種系統及方法係熟知的， fl 例如屬於以爪❻旧且讓渡給Koninklijke Philips Electr〇nics N.V·之國際公開案第w〇 2〇〇6/〇953 17號中所述，該案之全 文以引用的方式併入本文中，其中系統將各偵測之器件指 派給建築物内之特定位置。特定言之，藉由為從測量器件 間範圍而導出之位置提供樣板，建築平面圖用於幫助解析 疋位程序。已將各種技術應用於從範圍測量決定器件位 置，如Simons等人在2007年3月5曰申請之國際專利申請案 序號PCT/IB2007/05 0707中所述，其主張2006年3月6日申 I 請的歐洲專利申請案序號0611 0706.6(代理人檔案號碼 PH004189、ID405269)之權利，該二申請案之全文以引用 之方式併入本文中。 機率模型已用於決定無線網路内器件之位置，如屬於 Misikangas之美國專利申請公開案第2〇〇5/〇128139號中所 述，該案之全文以引用之方式併入本文中。可使用各種演 算法實現位置決定，例如Donald B. Reid所著論文内所述 者’標題為”用於追縱多個目標之演算法（An Algorithm f〇r 130169.doc 200850056In the grille or lattice configuration in the ceiling so that there is even spacing between them. Each of the individual light sources within the array of illuminations is adapted to be capable of communicating with other light sources over a wireless communication network, which is formed by an array of associated communication nodes. Each of the communication nodes within the network is located at the location of its associated light source within the array of lights. Therefore, the array of illuminations is equivalent to the spatial structure of the communication network. The k-network provides a set of lights that can be automatically commissioned after installation. However, individual nodes within the network are unable to provide their own location information, so it is not known which light source is associated with which node. Before the array can be commissioned, the spatial locations of the nodes within the communication network are established via various well known methods, including, for example, by manual operator input so that each node can be assigned to the correct light source. The location of the communication node is found by a triangulation procedure, such as U over the range data provided by the wireless communication network. The scope data is provided in the form of a range measurement between pairs of communication nodes in two: (four): the calculation of the range between the two nodes is directly measured by the range, and the system is made known to 130169.doc 200850056. Technical execution, such as using Received Signal Strength Indication (RSSI) or time of flight information for signals exchanged between various nodes and/or light sources. In the RSSI scenario, the received strength of a radio signal exchanged between a pair of communication nodes is used to calculate the range therebetween. The rate of decrease in the intensity of the transmitted signal is inversely proportional to the travel distance and proportional to the signal wavelength. Therefore, considering the wavelength, the distance between the pair of nodes can be calculated from the attenuation of the signal transmitted at the receiving node. In the case of time-of-flight measurement, the range between a pair of communication nodes is calculated by measuring the time during which the radio signal travels. Since the wireless signal travels at the speed of light, an accurate measurement of the time of flight between the pairs of nodes enables an accurate calculation of the distance therebetween. However, the range measurements of these types are subject to errors, so the derived locations of the communication nodes typically do not exactly match the locations on the grid or lattice configuration of the configured light source. Therefore, there is still some uncertainty as to which light source is associated with each node. In order to successfully appoint a wireless light array, the communication node must be assigned to its correct grid or lattice location to be assigned to the light source within the light array. If a communication node is assigned to a lattice location that does not correspond to its actual lattice location, the derived spatial structure of the communication network will be erroneous, so the array of illuminations will not function properly. To resolve such uncertainties in the location of the communication node, the position derived by the triangulation measurement can be compared to the same plate, which defines the lattice position of the light source within the illumination array. By this method, the communication node can be assigned to the light source closest to the two locations. The new location can then be used as a reference point in the triangulation of other communication nodes 130169.doc 200850056. In this way, errors in the position derived by the triangulation program do not accumulate. However, there is a risk of assigning individual communication nodes to an erroneous location, i.e., a location that does not correspond to its actual location. In this case, using this location to build the location of the wanted node results in the accumulation of larger errors. Such errors can be so significant that they prevent the overall layout of the array of lights from being created. SUMMARY OF THE INVENTION Various systems and methods for automatic commissioning of wireless lighting are well known, fl, for example, belonging to the international publication of Koninklijke Philips Electr〇nics NV·w第2〇〇6/ As described in 〇 953, the entire contents of which is hereby incorporated herein by reference in its entirety in its entirety in the the the the the the the In particular, the floor plan is used to help resolve the clamp program by providing a template for the location derived from the range of measurement devices. Various techniques have been applied to determine the position of the device from the range measurement, as described in the International Patent Application Serial No. PCT/IB2007/05 0707 filed by Marchs et al. The right of the European Patent Application No. 0611 0706.6 (Attorney Docket No. PH 004 189, ID 405 269), the entire disclosure of which is hereby incorporated by reference. The probability model has been used to determine the location of the devices within the wireless network, as described in U.S. Patent Application Publication No. 2/5/128,139, the entire disclosure of which is incorporated herein by reference. Position calculations can be implemented using a variety of algorithms, such as those described in the paper by Donald B. Reid, entitled "An Algorithm for Tracking Multiple Targets" (An Algorithm f〇r 130169.doc 200850056)
Tracking Multiple Targets)"’ 1979年12月把即自動控制學 報第AC-24卷第6期第843至854頁，其用於帛終移動物體， 該論文之全文以引用的方式併人本文中。Reid演算法廣泛 應用於防禦系統，尤其用於目標追縱領域。如㈣所述， 將假設樹建構成代表用於將進人f料指派給現有循跡的可 能選項。保持該等利開啟允許將最終決策延遲至更多資 訊可用。 'Tracking Multiple Targets)"' December 1979, Journal of Automatic Control, Vol. AC-24, No. 6, pp. 843-854, which is used to end moving objects. The full text of this paper is cited in this article. . The Reid algorithm is widely used in defense systems, especially in the field of target tracking. As described in (d), it is assumed that the tree construction represents a possible option for assigning incoming materials to existing tracking. Keeping these benefits open allows the final decision to be delayed until more information is available. '
二、、、先及方法之目的係改善委任網路内目標器件（例 如燈源）之已知系統及方法。 依據說明性具體實施例，提供用於決定決策樹中機率之 方法及系統’纟包含根據從第一器件至兩個器件之距離產 生第一假設，#具有第-器件位於第-位置之第一機率； :據從第二器件至第一器件及兩個器件之距離產生第二假 ^其具有第二器件位於第二位置之第二機率；以及根據 4第-件至第—器件及至兩個已知器件之距離重新計算 第一機率以形成一重新計算之第一機率。 應用本系統及方法之其他區域將從下文提供之詳細說明 中明白。應瞭解，詳細說明及特定範例雖然指示系統及方 法之不範性具體實施例，但僅用於說明㈣，而非限制本 發明之範圍。 【實施方式】 以下特^不範性具體實施例的說明本f上僅為範例性， 並絕非意欲限制本發明及其應用或其使用。以下本系統及 方法的具體實施例之心朗中將參考關，其形成本發 130I69.doc 200850056 明的一部分，且其中藉由說明其中實現所述系統及方法之 特定具體實施例來顯示。該等具體實施例的說明已充分詳 細能使熟悉技術人士音够士 议仍八士貫騃本文所揭不之系統及方法，且應 瞭解也可以利用他目J-A U) >Λ J⑺，、他具體實施例，並可以作出結構、邏輯 及電機方面的變化而不致背離本發明的範圍。 因此’下m羊細說明不應視為限制意義，本發明之範嘴 係藉由隨附申請專利範圍來定義。本文中圖式内參考數字 f 的左側數子通常對應於圖式編號，例外係出現於多個圖式 内的相同組件係藉由相同參考數字識別。另外，出於清楚 目的’為不混淆本發明的說明而省略熟知之器件、電路、 及方法之詳細說明。 本系統及方法使用假設樹以代表及解析網路内目標器件 之自動委任期間的指派決策樹，例如用於燈照網路或 内的燈源。 、 t 決策樹用於評估其中可能有多個結果的問題，以便幫助 決定貌似最可信的解決方案。樹包括假設階層，各階 特定機率指派給特定信念。具有最高總體機率之分支^ 正雄解決方案下之最佳猜測。本系統及方法包括改善用； 各假設之機率之估計的技術，其對目標器件之自動委任至 關重要，例如網路内燈源，包括燈照系統。 特定言之，按照在首次建立假設時尚不 視較早假設。本系統及方法提供改良之三角測量，= 多資料變得可用，其產生較佳機率計算， = 消除正確假設的機率。另外，當資訊可用性通常有ΓΓ 130169.doc 200850056 本系統及方法校正決策樹建築 完整決策樹之結果的顯著改良 立信念之順序較不敏感。 物之較早階段。因此可實現 。另外，本系統及方法對建 決策樹用於代表解決特定問題之替代假設。為各假設指 派-機率’其指示特定信念係正確的可能性，例如特定器 件位於建築物平面圖上和^ & 榇圯的扣疋位置。將假設組織成樹 結構’以便沿樹的特定分支之假設組合指示目標器件⑽ 如燈源）對位置之一組指派的組合視圖。 f 攸範圍貝料導出特^信念之可能性，範圍資料係從藉由 樹内較早假設定位的器件位置測量。樹的各分支代表器件 對位置的一組可能的指派。根據用作參考點之兩個已知器 :，其係經由使用者手動輸入提供或者經由熟知方法決 —_H 一角測里用於根據第三/新或新目標器件盥各 參考點間的測定距離決定未知位置第三/新或： 相對位置。 〜 各：角測量操作使用其本身分支上之指派歷史作為應添 口 4益件放置的開始配置。各分支構成用於三角測量操作 各唯開始配置。该分支上之較早指派視為用於建立新信 舛左^參考位置。從器件至參考點之各者之範圍用於估 二4器件之位置。決定新器件位於建築平面圖或地圖内指 疋之各位置的可能性時，考慮該位置與建築平面 之各種位置間的距離。 曰疋 機當決定各新假設之總體機率時，亦考慮各假設之父代的 ^率-旦已消除特定假設之信念的可能性，藉由將此可 130169.doc 200850056 能性乘以父代假設之機率指派一組合機率。此構成從較早 假設轉遞的饋送資訊，以輔助估計隨後假設之機率。 本系統及方法提供沿相反方向返回之饋送資訊，以改善 較早假設之估計機率。藉由使用子代假設以及父代假設之 指派，比建立較早假設時更多的參考位置可用。其他優點 中，此點使該技術對解決指派的順序較不敏感。The purpose of the second, method, and method is to improve the known systems and methods for appointing target devices (such as light sources) within the network. In accordance with an illustrative embodiment, a method and system for determining a probability in a decision tree is provided '纟 comprising generating a first hypothesis based on a distance from a first device to two devices, # having a first device located at a first position Probability; according to the distance from the second device to the first device and the two devices, a second probability that has a second probability that the second device is in the second position; and according to the 4th to the first device and to the two The distance of the known device recalculates the first probability to form a first probability of recalculation. Other areas in which the system and method are applied will be apparent from the detailed description provided below. It should be understood that the detailed description and specific examples are not intended to The following description of the specific embodiments is merely exemplary and is not intended to limit the invention and its application or its use. The following is a description of a specific embodiment of the present system and method, which is incorporated herein by reference. The description of the specific embodiments has been fully described in detail so that the skilled person can still use the system and method disclosed in this article, and it should be understood that he can also use his subject JA U) >Λ J(7), It is a matter of particular embodiments, and structural, logical, and electrical changes may be made without departing from the scope of the invention. Therefore, the description of the present invention should not be construed as limiting, and the scope of the present invention is defined by the scope of the accompanying claims. The left-hand side of the reference numeral f in the drawings herein generally corresponds to the drawing number, except that the same components appearing in multiple drawings are identified by the same reference numerals. In other instances, detailed descriptions of well-known devices, circuits, and methods are omitted for clarity of the description. The system and method use a hypothesis tree to represent and resolve an assignment decision tree during automatic appointment of a target device within the network, such as for a light source or a light source within. The t decision tree is used to evaluate issues that may have multiple outcomes in order to help determine the seemingly most credible solution. The tree includes hypothetical classes, with specific orders assigned to specific beliefs. The best guess under the branch of the Zhengxiong solution with the highest overall probability. The system and method include improvements; techniques for estimating the probability of each hypothesis are critical to the automatic commissioning of the target device, such as an in-network source of light, including a lighting system. In particular, the assumptions are based on the assumption that fashion is first established. The system and method provide improved triangulation, = multiple data becomes available, which yields a better probability calculation, = eliminates the probability of a correct hypothesis. In addition, when information availability is usually ΓΓ130169.doc 200850056 The system and method corrects the decision tree construction. The result of the complete decision tree is significantly less sensitive. The earlier stage of the object. So it can be achieved. In addition, the present system and method are used to represent alternative hypotheses that address specific problems. Assigning a probability to each hypothesis' indicates that the particular belief is correct, such as the specific device being located on the floor plan of the building and the deduction position of ^ & The hypothesis is organized into a tree structure' so that a hypothetical combination of specific branches along the tree indicates a combined view of the target device (10), such as a light source, assigned to one of the locations. f 攸 Range The ability to derive special beliefs, the range data is measured from the position of the device that is assumed by the earlier assumption in the tree. Each branch of the tree represents a set of possible assignments of devices to locations. According to two known devices used as reference points: they are provided by manual input by the user or by well-known methods - _H angle measurement for measuring distances between reference points according to the third/new or new target device Decide on the unknown location third/new or: relative position. ~ Each: The angular measurement operation uses the assignment history on its own branch as the starting configuration for the placement of the component. Each branch is configured for triangulation operations. The earlier assignment on this branch is considered to be used to establish a new signal left reference location. The range from the device to the reference point is used to estimate the location of the 2 4 device. When deciding on the likelihood that a new device will be located in a building plan or in a location within a map, consider the distance between that location and the various locations of the building's plane. When deciding the overall probability of each new hypothesis, it also considers the probability that the father of each hypothesis has eliminated the belief of a particular hypothesis by multiplying the energy of the 130169.doc 200850056 by the parent. Assume the probability of assigning a combined probability. This constitutes feed information from earlier assumptions to aid in estimating the probability of subsequent hypotheses. The system and method provide feed information that is returned in the opposite direction to improve the estimated probability of earlier assumptions. By using the child hypothesis and the assignment of the parent hypothesis, more reference locations are available than when the earlier hypothesis was established. Among other advantages, this point makes the technique less sensitive to the order in which assignments are resolved.
決策樹用於解析無線器件之位置，例如，其使用在器件 間執行的範圍測量。範圍測量可併入較大範圍錯誤，並且 決策樹幫助處理所得不確定性。決策樹提供檢驗器件對建 築平面圖内之位置的所有貌似可信配置的機制。 圖1顯示㈣平面圖或地圖’其包括無線網路1〇〇,例 如，其具有位於已知位置A、B、c、D、E&F之六個節 點，以及六個無線器件，例如其使用zigBaTM協定或其他 無線協定，如六個燈源i、2、3、4、5及6。無線網路之掃 描顯現無線器件1、2、3、4、5及6之識別。任務或自動委 任涉及決定哪一識別或目標器件（例如燈源}1、2、3、4、$ 及6與（例如）建築物或任何其他環境内之網路的哪一位置 A、B、C、D、E及F相關聯。應瞭解，儘管使用燈源作為 目標器件，本系統及方法可應用於任何網路及任何目標器 件之自動委任。 參考圖2，無線燈照網路100之區段的方塊圖包括電性驅 動之燈源210及節點220，例如位置a、B、c、D、£及？之 六個節點，以及圖1内所示的六個燈源}至6。節點2i〇及/ 或燈源係調適成透過無線通信網路1 〇〇與彼此通信，該無 130169.doc 12 200850056 圖1所示的位置 通信節點220之 線通信網路包含無線通信節點22〇，例如 A、B、C、D、E及F之六個節點。例如， 並且與電性驅動之燈源 各者包含ZigBee狀無線電模組， 210之一相關聯。 如圖2所示，存在於各燈源之位置的硬體包含電源供應 皁元230、無線通信節點22G及燈源21()。將電源供應單元 230:適成提供電源至通信節點22〇及或燈源21〇。電源供 應單元230可係連接至主電源供應（例如12〇賣、鑛z或 230V、職），並且可包含電連接，例如用於操控住供應 並提供功率至節點220及燈源210的變壓器。 委任燈源210之燈照陣列❸第一階段係建立通信網路。 此點係藉由網路發現程序實現，其係在開啟電源後藉由所 有通仏節點220啟動。如所示，網路丨〇〇内之每一通信節點 220調諧至控制頻道並廣播，，廣告”訊息，其包含節點類型 以及所有其他節點識別本身之請求。特定時㈣節點彼 此以其識別及功能性回覆訊息。然而，節點22〇及/或燈源 210通常無法供應其位置資訊。因此在此階段中，網路100 之空間結構係未知的。 圖3顯示用於器件之自動委任的系統3〇〇，例如燈源 21〇，包括關於節點200在環境内之位置決定燈源的位置， 例如建築物或網路100。系統300包含儲存於記憶體内以藉 由圖4内所示之處理器或cpu 41〇執行的放置演算法31〇。 可利用放置演算法310建立節點22〇在網路1〇〇内之位置。 放置演算法310經組態用以使用由無線通信網路1〇〇提供之 130169.doc -13- 200850056 範圍資料係以在無 的範圍測量之形式 範圍資料計算各節點220之相對位置。 線網路100内之通信節點22〇對之間採用 六個節點A至F間的範 例如接收信號強度指 提供。直接從該等範圍測量導出一對 圍之計算，其係使用某些技術執行， 示（RSSI)或飛行時間資訊。 例如’放置演算法310係調適成可藉由處理器件彻(如 圖4内所示)來實施’例如膝上型電腦或pDA，其透過閘道 器介面320與無線網路⑽之節點22q通冑。處理器件彻可 包括閘道器介面320 1於儲存放置演算法31()之記憶體、 以及其他演算法及資料，例如作業系統等等。 閘道裔介面320包含在圖4所示之處理器件4〇〇之處理器 410上運行的電腦或處理器可執行程式，其透過由通信節 點220之一提供的閘道器從通信網路1〇〇請求及收集資料。 收集之貧料包括各節點220之功能性以及各對節點22〇之間 的範圍測篁。閘道器介面320持續監視網路丨〇〇，並且經組 態用以偵測新節點是否被添加至網路i 〇〇或從網路丨〇〇消 失0 參考圖4，處理器件400之硬體包括處理器，例如用於執 行放置演算法310以及用於管理及控制電腦4〇〇之運作的中 央處理單元（CPU)410。經由匯流排420將CPU 410連接至若 干器件，該等器件包括儲存器件，例如硬碟機43〇，以及 吕己,fe體态件’其包括ROM 44〇及RAM 450，其用於儲存藉 由CPU 41 0執行及處理之應用程式演算法及資料。電腦硬 體進一步包括網路卡450，其提供用於介接至通信網路1〇〇 130169.doc 14 200850056 之構件，以及顯示器460，其使使用者可監視電腦4〇〇之運 作。當然，亦可提供任何其他輸入/輸出器件，例如鍵 盤、滑鼠等。電腦400經組態用以經由（例如）串列或乙太網 路電纜與閘道器通信。然而，電腦400可以無線方式與閘 道器通信。 ^ 另一具體實施例中，將放置演算法3丨〇調適成可藉由整 • 合至無線通信網路100中之電腦硬體來實施。例如，此類 硬體可為通信節點220及/或燈源2 10之部分。 ( 在委任燈照陣列或網路時，電腦4〇〇之處理器410透過由 通信節點220之一提供的閘道器從無線通信網路1〇〇請求及 接收範圍資料。電腦400接著使用範圍資料以實施放置演 鼻法3 1 0。 圖5至1〇說明放置演算法31〇使用範圍測量來導出網路 100内之四個燈源Ϊ、2、3、5的位置之方法，其始於藉由 (例如）系統操作者或使用者手動提供或者經由任何其他構 件決定燈源4及6之已知位置。 ( 出於使用六個燈源1、2、3、4、5及6以及位於位置A、 B C、D、E及F的六個網路節點之說明性範例的目的，假 疋已知燈源4及6分別位於位置A及B，其可藉由熟知方法 來决疋，例如包括經由系統使用者之手動輸入，以及例如 使用國際專利申請案序號PCT/IB2007/050707中所說明之 方法。當執行放置演算法31〇時，處理器41〇接著可使用來 自°亥等苓考位置八及B之範圍測量以決定器件1、2、3及5 在剩餘位置C、D、F内的最可能識別。眾所周知，節 130169.doc -15- 200850056 點2 2 0及/或燈源21 〇之收發器及彳貞測器彼此通信及交換传 號’藉此可決定距離，例如使用RSSI或飛行時間資訊。 圖5顯示決策樹500及假設H1&H2之第一位準，其分別 具有如參考數字510、520所指示之機率，並顯示圓53〇、The decision tree is used to resolve the location of the wireless device, for example, using range measurements performed between devices. Range measurements can incorporate a wide range of errors, and decision trees help to handle the resulting uncertainty. The decision tree provides a mechanism to verify that the device looks at all seemingly trusted configurations for locations within the building plan. Figure 1 shows a (four) plan or map 'which includes a wireless network 1 ', for example, it has six nodes at known locations A, B, c, D, E & F, and six wireless devices, for example, zigBaTM protocol or other wireless protocols, such as six light sources i, 2, 3, 4, 5, and 6. The scanning of the wireless network reveals the identification of the wireless devices 1, 2, 3, 4, 5 and 6. Task or auto-commission involves determining which identification or target device (eg, light source} 1, 2, 3, 4, $, and 6 and, for example, which location of the network in the building or any other environment, A, B, C, D, E, and F are associated. It should be understood that although the light source is used as the target device, the system and method can be applied to the automatic commissioning of any network and any target device. Referring to Figure 2, the wireless lighting network 100 The block diagram of the section includes an electrically driven light source 210 and a node 220, such as six nodes of positions a, B, c, D, £ and ?, and six light sources} to 6 shown in FIG. The nodes 2i and/or the light source are adapted to communicate with each other through the wireless communication network 1 . The wireless communication network 22 includes the wireless communication node 22 . For example, six nodes of A, B, C, D, E, and F. For example, and associated with one of the electrically driven light sources including one of the ZigBee shaped radio modules, 210. As shown in Figure 2, there is The hardware at the position of each light source includes a power supply soap unit 230, a wireless communication node 22G, and Source 21 (). The power supply unit 230: is adapted to provide power to the communication node 22 and or the light source 21. The power supply unit 230 can be connected to the main power supply (for example, 12 sale, mine z or 230V, job And may include an electrical connection, such as a transformer for manipulating the supply and providing power to the node 220 and the light source 210. The light source array of the light source 210 is commissioned to establish a communication network in the first stage. The network discovery program is implemented by all the overnight nodes 220 after the power is turned on. As shown, each communication node 220 in the network is tuned to the control channel and broadcasts, and the advertisement "message" The request includes the node type and all other nodes identifying themselves. The nodes (4) respond to each other with their identification and functionality. However, the node 22 and/or the light source 210 are generally unable to supply their location information. Therefore, in this phase, The spatial structure of network 100 is unknown. Figure 3 shows a system for automatic commissioning of devices, such as light source 21A, including determining the location of the light source with respect to the location of node 200 within the environment, Such as a building or network 100. System 300 includes a placement algorithm 31 stored in memory for execution by the processor or CPU 41 shown in Figure 4. Placement algorithm 310 can be utilized to establish node 22 The location within the network 1. The placement algorithm 310 is configured to use the 130169.doc -13-200850056 range data system provided by the wireless communication network 1 to calculate the form range data in the range measurement without the range The relative position of each node 220. The communication node 22 in the line network 100 is provided with a range between six nodes A to F, for example, a received signal strength finger. The calculation of the pair is derived directly from these range measurements, using some techniques to perform, display (RSSI) or time-of-flight information. For example, the placement algorithm 310 can be adapted to be implemented by a processing device (as shown in FIG. 4), such as a laptop or pDA, which communicates with the node 22q of the wireless network (10) through the gateway interface 320. helmet. The processing device may include a gateway interface 320 1 for storing the memory of the placement algorithm 31(), as well as other algorithms and materials, such as operating systems and the like. The gateway interface 320 includes a computer or processor executable program running on the processor 410 of the processing device 4 shown in FIG. 4, which is transmitted from the communication network 1 via a gateway provided by one of the communication nodes 220. Request and collect information. The poor materials collected include the functionality of each node 220 and the range measurements between pairs of nodes 22〇. The gateway interface 320 continuously monitors the network port and is configured to detect whether a new node is added to or removed from the network i. Referring to FIG. 4, the processing device 400 is hard. The body includes a processor, such as a central processing unit (CPU) 410 for executing the placement algorithm 310 and for managing and controlling the operation of the computer. The CPU 410 is connected to a plurality of devices via a bus bar 420, the devices including a storage device, such as a hard disk drive 43A, and a body member, which includes a ROM 44A and a RAM 450 for storage by The application algorithm and data executed and processed by the CPU 41 0. The computer hardware further includes a network card 450 that provides means for interfacing to the communication network 1130169.doc 14 200850056, and a display 460 that allows the user to monitor the operation of the computer. Of course, any other input/output device, such as a keyboard, a mouse, etc., can also be provided. Computer 400 is configured to communicate with the gateway via, for example, a serial or Ethernet cable. However, computer 400 can communicate with the gateway wirelessly. In another embodiment, the placement algorithm 3 is adapted to be implemented by computer hardware integrated into the wireless communication network 100. For example, such hardware can be part of communication node 220 and/or light source 2 10. (When a lamp array or network is commissioned, the computer 410 processor 410 requests and receives range data from the wireless communication network 1 through a gateway provided by one of the communication nodes 220. The computer 400 then uses the range. The data is used to implement the placement of the nasal method 3 1 0. Figures 5 to 1 〇 illustrate the placement algorithm 31 〇 use range measurement to derive the position of the four light sources Ϊ, 2, 3, 5 in the network 100, the beginning The known positions of the light sources 4 and 6 are determined manually by, for example, a system operator or user or via any other means. (For the use of six light sources 1, 2, 3, 4, 5 and 6 and The purpose of the illustrative example of six network nodes located at locations A, BC, D, E, and F is that the known light sources 4 and 6 are located at positions A and B, respectively, which can be determined by well-known methods. For example, including manual input via a system user, and for example using the method described in International Patent Application Serial No. PCT/IB2007/050707. When the placement algorithm 31 is executed, the processor 41 can then be used from Test position 8 and B range measurements to determine device 1, 2, 3 5 The most likely identification in the remaining positions C, D, F. It is well known that the transceivers and detectors of the section 130169.doc -15- 200850056 point 2 2 0 and/or the light source 21 communicate with each other and exchange the marks 'Through this, the distance can be determined, for example using RSSI or time-of-flight information. Figure 5 shows the decision tree 500 and the first level of hypothesis H1 & H2, which have the probability as indicated by reference numerals 510, 520, respectively, and display circle 53 Oh,
C 540 ’其具有代表距離或範圍資料之半徑，例如該等資料 係經由RSSI或飛行時間來測量。例如，一個圓53 〇係從位 置未知器件1與位置已知或第一參考器件4間的測定範圍資 料產生。圓530在位於位置A之節點具有一中心，其中亦定 位位置已知燈源4,以及等於燈源4(或節點A)與位置未知 燈源1間的測定距離之半徑，該位置未知燈源在網路或建 築平面圖、地圖或燈照陣列内之位置或定位正在決定。燈 源1係選自其他未知或待決定位置的燈源，因為其係最接 近兩個參考燈源或已知位置之目標器件4、6(即分別位於 位置A及B)的燈源。例如，亦可使用RSSI*飛行時間方法 決定燈源1與兩個參考燈源4、6之至少—者的此接近性。 一旦決定燈源i之位置，則選擇下一最接近三個位置已知 原4 6之至一者的燈源，以便決定此下一最接近 燈源之位置。 另-圓540(根據位置未知器件2與位置已知或參考琴❹ 間的距離或範圍測量產生）在位於位置B之節點具有—中 〜，其中亦定位參考燈源6，以及等^ ^ ^ ^ ^ ^ ^ 寻於參考垃源6(或節點 B)與待決定位置之最接近燈源 — 原1之間的測定距離之半徑。 在第一位置已知器件4盥位罟去 /、位置未知盗件間執行初始範圍 或距離測置，及/或在第— 弟—位置已知器件6與位置未知器件 130I69.doc 200850056 間執仃範圍測里。根據此類接近性測量，選擇與兩個位置 已头器件4 6之至少_者最接近的位置未知器件，以便決 定其位置，即®5内所示說明性範例中的燈源1。 如圖5内所示，初始範圍測量指示目標器件或燈源」最接 近已知參考點4及6，因此選擇其以放置在附近。在位置未 知器件i與第一位置已知器件4間以幻立置未知器件！與第 一位置已知器件6間執行其他範圍測量。兩個範圍圓530、 540產生兩個範圍圓53〇、54〇之交叉點55〇，如圖$所示。 將此交叉點550與未指派目標器件之四個位置c、D、e、 及F比較。為清楚起見，僅說明用於位置未知器件丨的最近 兩個目標或可能位置〇及£。另外，慣常地修剪樹以防止 具有極低機率之假設的不必要膨脹。假設m代表器件工至 位置D之指派，假設H2代表器件1至位置E之指派。 根據k父又點550至目標位置D或E之距離計算各假設 HI、H2之可能性或機率。如圖5所示，決策樹5〇〇具有兩 個結果、機率或分支56〇、57〇，其代表假設Hl(具有機率 5 10)及假5又H2(具有機率520)。由於與位置e相比交叉點 550更接近位置D，然後代表假設H1(具有機率51〇)之第一 分支560分配較高可能性或機率，即0.75，其高於用於與 決策樹500之第二分支57〇相關聯的假設H2(具有機率52〇) 之機率0.25。 圖6顯示決策樹6〇〇之下一位準，其考慮器件2之指派。 建立四個新可能結果或假設H3、H4、H5、H6(分別具有計 异之機率610、620、63 0、640)，即從來自父代假設H1 (具 130169.doc 200850056 有機率510)之第一分支560建立的兩個子代假設H3、H4以 及從來自父代假設H2(具有機率520)之第二分支570建立的 兩個子代假設H5、H6。三個參考點現在可用，即三個位 置已知器件1、4、6，從而致能繪製三個範圍圓650、 65 5、660以產生用於假設H3、H4之交叉點665。 第一圓650代表從器件2/位置E至器件4/位置A之範圍區 域；第二圓655代表從器件2/位置E至器件6/位置B的範圍 區域；第三圓660代表從器件2/位置E至器件1/位置D之範 圍區域。就是說，第一圓650具有位於器件4/位置A之中心 以及等於器件2(及或位置E之節點）與器件4(及或位置A之 節點）間的測定距離之半徑，例如經由來自在器件2/位置E 與器件4/位置A間交換之信號的RSSI或飛行時間測定資 料；第二圓655具有位於器件6/位置B之中心以及等於器件 2/位置E與器件6/位置B間的測定距離之半徑；第三圓660 具有位於器件1/位置D之中心以及等於器件2/位置E與器件 1 /位置D間的測定距離之半徑。三個圓在各種位置交叉。 藉由平均化從最佳交點集導出之位置決定平均交叉點或位 置665，如2006年12月18曰申請之國際專利申請案序號 PCT/IB2006/054921内所述，該申請案主張Pitchers等人在 2005年12月20日申請之歐洲專利申請案序號05 112465.9的 權利（代理人檔案號碼PH003 798，ID405 346及ID406150)， 標題為”用於決定無線網路中節點之位置的方法及裝置（A Method and Apparatus for Determining the Location of Nodes in a Wireless Network)’’，該案之全文以弓I用之方式 併入本文中。 130169.doc -18- 200850056 對於假設H5、H6同樣地產生三個其他圓670、675、 680，並且其具有估計位置685，其中假定器件1之位置位 於節點E，而非用於假設H3、H4之節點D。如所示，第四 圓670具有位於器件4/位置A之中心及等於器件4/位置A與 器件2/位置F間之測定距離的半徑；第五圓675具有位於器 ' 件6/位置B之中心及等於器件6/位置B與器件2/位置F間之 - 測定距離的半徑；第六圓680具有位於器件1/位置E之中心 及等於器件1 /位置E與器件2/位置F間之測定距離的半徑。 f 從圖6可看出，交叉點665、685取決於父代假設，因為 各分支560、570指定一不同開始位置或父代假設H1、 H2。特定言之，假設H3、H4(具有機率610、620)具有作 為父代之假設H1(具有0.75之機率510)，其假定（具有0.75 之可能性或機率）器件1位於位置D(對於分支560，1=D)， 其中三個圓650、65 5、660具有估計位置665。另外，假設 H5、H6(具有機率630、640)具有作為父代之假設H2(具有 0.25之機率520)，其假定（具有0.25之機率）器件1位於位置 ( E(對於分支570，1=E)，其中三個圓670、675、680具有估 計位置685。 同樣，四個子代假設H3、H4、H5、H6之各者的可能性 或機率610、620、63 0、640與從交叉點665、685至目標位 ' 置之距離成正比或基於該等距離。此外，藉由將特定分支 或子代之此可能性乘以父代假設之機率指派總體或組合機 率。如圖6所示，關於器件2位於位置E之可能性的分支 560、690之總體機率係0.5，其中器件1位於位置D(1=D且 130169.doc -19- 200850056 2=E);分支560、692之總體機率（1=D且2=f)係0·24 ;分支 570、694之總體機率（ι=ε且2=D)係0.05 ;分支570、696之 總體機率（1=E且2=F)係0.21。 假設H3(具有機率610)具有〇·5〇之最高總體機率，因為其 k假設Η1 (具有機率5 10)繼承（〇·75之）良好機率，並產生接 近目標位置E(假設H3)之交又點665，其比從假設H4的交叉 點665至目；f示位置F之距離更接近，其中假設或假定器件2 位於位置F。相應地，將燈源丨指派給位置D，並將燈源二指 派給位置E，因為與位於相同樹位準（即決策樹6〇〇之第二 位準）之其他機率620、630、64〇相比，假設H3具有最高機 率610。當然，視需要，若機率超過預定值可選擇假設 H3，其可取決於特定樹位準下的分支數目。例如，在決策 樹600之第二位準具有四個分支的情形中，預定位準=為 1/4,因此選擇具有大約1/4或0.25之機率的分支或假設: 以便為節點或位置提供燈源之正確指派。同樣，可修剪或 廢棄具有小於預定位準之機率的分支或假設，該預定位準 可係固定，例如(M，或者可取決於分支數目，例如一除 以分支數目之-倍數（例如5倍），舉例而言，對於具有四: 分支之決策樹600的第二位準，1/(4χ5卜1/2〇或〇〇5。 為產生改良假設樹產生，太糸鉍β 士 4 & 本糸統及方法包括額外步 其藉由重新評估假設之先前位準改善機率之計算。 二：：子代假设代表器件至位置之指纟’重新評估 用子代假設以提供額外參考位置。圖7回歸在已建= H3、H4、H5及H6後的假設出及犯之機又又 β丨升，其中其 130169.doc •20- 200850056 總體機率 610、620、63 0、640係 0·50、0·24、0·05及 0.21， 如圖6所示。如圖7所示，並且與圖5比較，現在產生顯示 為圓710、720、73〇、74〇之額外範圍測量，並且其可用於 重新評估假設（例如圖5内所示假設Η1)以及使用其子代假 設（例如圖6内顯示為假設Η1之子代的假設Η3)重新計算其 機率。 參考圖7，分離地處理決策樹7〇0之各分支，因為一般各 假设可具有許多後代。例如，當重新計算假設Η1之機率 510時’子代假設Η3，（具有機率61〇，）將提供與子代假設 Η4 (具有機率MO’）參考位置配置不同之參考位置配置。 分離地計算新可能性確保整個分支之總體機率反映其本身 的唯一信念集。 如圖7所示，重新計算用於假設Η3,之機率610,包括產生 新圓710，其在位於位置ε之器件2具有一中心，以及等於 器件2(及/或節點Ε)與器件丨（及/或節點D)間之測定距離的 一半徑。評估此圓710與先前產生之圓530、540(如結合圖 5所述）之交點，以及三個圓53〇、540、710之其他交點。 修剪或廢棄具有較低機率之交點，即遠離器件1之可能節 點或位置（例如位置D)，並從接近可能位置d之剩餘交點決 定平均交又點750，例如，以提供改良三角測量。 從三個產生之圓530、540、710之交叉點750至器件1(位 置D)的距離小於從交又點55〇至圖5所示之器件丨（位置〇)的 距離。因此，位於位置D(即假設H1，）之器件！的重新計算 之機率510’大於用於假設出之〇75之機率51〇，從而產生用 130169.doc 21 200850056 於0·57之假設H3’（如圖7所示）的較大總體機率610，，其大於 先前計算的用於假設H3之0.50的總體機率610，如圖6所 示。相應地，更可能器件1之正確位置係位置D，而器件2 之正確位置係位置E。 就是說，一旦重新計算之機率成為用於各分支之總體機 率的因數’應注意用於假設H3 ’之總體三角測量結果已改 善’從而將其總體可能性610’（從圖6内所示的〇·5)增加至 0·57，如圖7内所示。同樣，重新計算機率62〇,、63〇,、 640’，以經由相似三角測量，結合圓53〇、54〇使用額外圓 720、730、740分別產生用於其他三個假設Η4,、Η5,、Η6, 之 0·24、0.02及 0.21° 如圖7所示，用於假設Η4’及Η6,之三角測量結果620，、 640’實質上分別保持不變於〇·24及〇 21(與圖6内所示的機率 620、640相比）。假設Η5’從假設H2,繼承更差三角測量結 果，從而將其機率630,（從圖6所示的〇.〇5之機率63〇)減小 至僅為0.02，如圖7所示。重新計算指示假設Η3，係内部最 一致之指派集’即器件1位於位置D，器件2位於位置ε， 而器件4及6分別位於位置八及Β。如圖7所示，最差三角測 量755用於假設Η2,，其中假定器件2位於位置〇而器件“立 於位置E。 可將此重新評估技術應用為建立之假設的各新位準，其 恆疋地回饋資汛以改善用於樹内各假設的父代假設。事實 上，最重要的係該等葉或子代假設H3、H4、H5&H6之機 率。右總體總機率係沿決策樹之各分支獨立地加以重新計 130169.doc -22- 200850056 算’實際上不必修改中間假設之機率。藉由推遲重新評估 直至樹已完全完成’可大幅減少處理時間數量。然而，可 有利地在樹建構期間每隔幾個位準重新評估，以便作出較 佳修剪決策，其取決於機率之良好估計。因此機率估計： 佳’越可能執行正確修剪。相應地，需要在修剪前重新 算機率。 看起來此範例僅對機率造成細微變化，但在已建立許多 假設位準時可應用此技術。向後饋送之能力不僅係_參= 點’如給定範例中-樣，而是許多參考點進一步改善^角 測量之可靠性。同樣在許多位準上計算時機率之細微變化 可導致更劇烈變化，因為修訂機率係在假設結構上從父代 至子代向上回饋，直至到達頂部位準。 圖8至10顯示三角測量之另-範例，以決定網路内之哭 件位置’即將器件1至10(圖10内所示）指派給節點或位置: 至J ’如圖8之陣列8〇〇所示。 圖9顯示建構決策樹時 巧W里释禾y〇〇。器件5 視為用於位置E的貌似可信指派，但用於位置⑴之°° 尚待建立0因此，由承士4几a 旦 LI此由千均化父又點910、920顯示之三角測 2：結果具有較差幾何形狀，如 忏5之兩個可能位置 、920所指示’其中—個平均交又點或位置91〇接近位 =，而另一平均交又點920接近位置F。因此，無重新評 估之典型二角測量導致更二 守双文低一角測里結果，即使指派之一 P态件5至位置E之指派）事實上係正確者。 圖1。顯示映射胸，其考慮一旦藉由子代假設放置剩餘 130169.doc -23- 200850056 位置則重新評估交叉點。使用新資訊已擴展用於三角測量 ^考位置集，其改善幾何形狀，從而改善機率計算之可 罪性。實務中，用於器件5之兩個可能結 则、義位於正確位置，即位以。假設樹之建構期 間，重新評估提供機率之準確估計，並減小修剪正確解決 方案的機會。完成樹時的重新評估在決定貌似最可信解決 方案時提供最準確的機率。 、 藉由反向回饋資訊以改善較早假設之估計機率來重新評 估結果的本系統及方法可應用於需要面對不確定性而作出 決策的任何情況。重新評估技術可顯著地改善用於各替代 解決方案之機率的估計。 *應瞭解，重新評估系統之各種組件，例如各種節點、目 標器件、處理器410、記憶體44〇、45〇 '硬碟43〇、各種電 路卡，如圖4所示的網路卡45〇及顯示器46〇，例如，可透 過任何類型之匯流排加以互連，或者藉由任何類型之鏈路 可刼作地彼此耦合’例如，包括有線或無線鏈路。另外， 可將處理器410、記憶體44〇、45〇、及硬碟43〇集中化或分 佈於各種系統組件間，其中，例如，各目標器件可具有其 本身之控制器或處理器及記憶體。 當然，熟習通信技術人士從本說明可明白，用於通信之 ”先或網路組件内可包括各種元件，例如電晶體、接收 器、或收發器、天線、調變器、解調變器、轉換器、雙工 H皮器、多工器等。各種系統組件間之通信或鍵路可 藉由任何構件，例如有線或無線。系統元件可分離或整合 130169.doc -24· 200850056 在一起，例如與處理器整合。频周知，處理器執行健存 於記憶體内之指令，例如，其亦可儲存其他資料，如關: 系統控制之預定或可程式化設置。 熟習技術人士從本文之說明可認識到，亦可提供各種修 改。本方法之操作動作特別適合於藉由電腦軟體程式執 行。例如，電腦軟體程式可包含對應於方法之個別步驟或 動作的模組。應用程式資料及其他資料由控制器或處理器 接收，以便將其配置成根據本系統及方法執行操作動作。 當然，可將此類軟體、應用程式資料以及其他資料具體化 於電腦可讀取媒體中’例如積體晶片、周邊器件或記憶 體，例如耗合至控制器或光模組之處理器的記憶體 記憶體。 電細可3貝取媒體及/或記憶體可為任何可錄製媒體（例如 續：職、可抽取記憶體、CD-ROM、硬碟機、DVD、 軟碟或記憶卡）或者可為傳輸媒體（例如包含光纖光學之網 =、全球貧訊網、電纔及/或無線頻道，例如，其使用分 t:向近接、分碼多向近接、或其他無線通信系統）。任 何热：或發展之媒體可用作電腦可讀取媒體及/或記憶 體’只要其可儲存適合詩電腦系統之資訊。 也:使用額外記憶體。電腦可讀取媒體、記憶體及/或 :他記憶體可為長期、短期、或長與短期記憶體之組 口 憶體將處理器/控制器配置成實施本文所揭示 广：、操作動作、及功能。記憶體可為分佈式或本地， 並且處理器，其中可提供額外處理器，可為分佈式或單 130169.doc -25- 200850056 =可將記憶體實施為電性、磁性或光學記憶體、或該等 貞型錯存器件之任一組合。另外，術語"記憶體"應 “地視作涵蓋在處理器所存取之可定址空間内能夠 址讀取或寫人-位址之任何資訊。採用此定義，網 ;(例:：際網路)上的資訊仍在記憶體内或係記憶體之部 刀因為處理器可從網路中擷取資訊。 處理器及記憶體可為任何類型之處理器/控制器以 憶體。處理哭可妒釣拙一々 ° 執仃各種說明的操作並執行儲存於記 =内之指令。處理器可為特定應用或_般用途積體電 卜’處理器可為用於根據本系統執行的專用處理 可為通用處理器’其中僅運作用於根據本系統執 仃的岭夕功能之-。處理器可利用程式部分、多個程式片 ::運作’或者可係利用專用或多用途積體電路之硬體器 4二二上論述僅欲說明本系統，而不應視為將隨附* :專利補限於任何特定具體實施例或具體實施例群组。 =，雖然本系統已參考特定示範性具體實施例詳細加以 也應明白熟習技術人士可設計許多修改及替代具體 、也卜而不背離由以下申請專利範圍提出的本系統之更 廣闊及期望的精神與料。該說明及圖例係例證之方式， 並非限制該附加請求項之範疇。 在解釋該附加請求項時，應明白： )包“亥s司並不排除不同於-給定請求項所列之直它元 件或動作的出現； 夕』之其匕兀 130169.doc -26 - 200850056 b)元件前之冠詞” 〇)ψ Μ - ι^ι 、非除出現複數個此類元件· ㈠甲明專利乾圍令的任 仵， 句數個”構件，，可藉：考付號並不限制其範缚，· 功能表示； 了猎由該相同項目或硬體或軟體執行結構或 e)任何揭示之元件會包含硬體 的電子電路）、軟體部分(例如 合； 部分（例如，包括離散及整合 ，電腦程式化）、及其任何: f)硬體部分可由一個或兩個類比及數位部分組成； 二)饤揭不之器件及部分會互相組合或分離 除非另行指出；以1 -他。P刀， h)除非明確指出’否則不需要衫動作或步驟序列。 【圖式簡單說明】 攸後面的說明、隨附的申請專利範圍及隨附的圖式中， 將可更瞭解本發明的裝置、系統及方法的該等及其他特 徵、觀點及優點，其中： 圖1顯不平面圖，其顯示依據一項說明性具體實施例之 網路節點位置及目標器件；以及 圖2顯示圖i所示之無線燈照網路之區段的方塊圖； 圖3顯示依據一說明性具體實施例之器件的自動委任之 糸統； 圖4顯示依據一說明性具體實施例之處理器件；以及 圖5至10顯示範例，其說明依據說明性具體實施例之機 率的重新計算。 【主要元件符號說明】 130169.doc -27- 200850056 1 第一器件 2 第二器件 4 器件 6 器件 100 無線網路 210 燈源 220 節點 230 電源供應單元 300 系統 310 放置演算法 400 處理器件 410 處理器 430 硬碟機 440 ROM 450 RAM/網路卡 460 顯示器 510 第一機率 510f 重新計算之第一機率 520 機率 530 第一圓 540 第二圓 550 交叉點 560 分支 570 分支 130169.doc -28- 200850056C 540 ' has a radius representing the distance or range of data, for example, the data is measured via RSSI or time of flight. For example, a circle 53 is generated from the measurement range information between the location unknown device 1 and the known position or the first reference device 4. The circle 530 has a center at the node at position A, wherein the position known as the light source 4, and the radius of the measured distance between the light source 4 (or node A) and the position unknown light source 1 is unknown. The location or location within the network or building plan, map or light array is being determined. Light source 1 is selected from other unknown or to-be-determined light sources because it is the light source closest to the two reference light sources or target devices 4, 6 of known locations (i.e., locations A and B, respectively). For example, the proximity of the light source 1 to at least one of the two reference light sources 4, 6 can also be determined using the RSSI* time of flight method. Once the position of the source i is determined, the next closest source to the nearest three positions is selected to determine the position of the next closest source. Another-circle 540 (generated according to the position unknown device 2 and the position or reference distance or range measurement) has a - in the node located at position B, which also locates the reference light source 6, and etc. ^ ^ ^ ^ ^ ^ ^ Find the radius of the measured distance between the reference source 6 (or node B) and the closest source to the determined position - the original 1. In the first position, it is known that the device 4 is in/out, the position is unknown, the initial range or distance measurement is performed, and/or the first-part-position known device 6 and the position-unknown device 130I69.doc 200850056 are executed.仃 Scope measurement. Based on such proximity measurements, a location unknown device that is closest to at least the two of the two locations of the headed device 46 is selected to determine its position, i.e., source 1 in the illustrative example shown in ®5. As shown in Figure 5, the initial range measurement indicates that the target device or light source is closest to known reference points 4 and 6, so it is selected to be placed nearby. An unknown device is placed between the position unknown device i and the first position known device 4! Other range measurements are performed between the known device 6 at the first location. The two range circles 530, 540 produce an intersection 55 〇 of two range circles 53 〇, 54 〇, as shown in FIG. This intersection 550 is compared to the four locations c, D, e, and F of the unassigned target device. For the sake of clarity, only the last two targets or possible locations for the location unknown device 丨 are described. In addition, the tree is routinely trimmed to prevent unnecessary expansion of the hypothesis with very low probability. Assuming m represents the assignment of device to position D, it is assumed that H2 represents the assignment of device 1 to position E. The probability or probability of each hypothesis HI, H2 is calculated according to the distance between the k parent and the point 550 to the target position D or E. As shown in Figure 5, decision tree 5 has two results, probabilities or branches 56 〇, 57 〇, which represent hypotheses H1 (with probability 5 10) and false 5 and H2 (with probability 520). Since the intersection 550 is closer to the location D than the location e, then the first branch 560 representing the hypothesis H1 (with probability 51 〇) is assigned a higher probability or probability, ie 0.75, which is higher than for the decision tree 500. The probability of the second branch 57 〇 associated hypothesis H2 (with probability 52 〇) is 0.25. Figure 6 shows the decision tree 6 〇〇, which considers the assignment of device 2. Establish four new possible outcomes or hypotheses H3, H4, H5, H6 (with probability of 610, 620, 63 0, 640, respectively), ie from the parent hypothesis H1 (with 130169.doc 200850056 organic rate 510) The two child generations established by the first branch 560 assume H3, H4 and the two child hypotheses H5, H6 established from the second branch 570 from the parent hypothesis H2 (with probability 520). Three reference points are now available, i.e. three locations known devices 1, 4, 6, enabling three range circles 650, 65 5, 660 to be created to produce an intersection 665 for assuming H3, H4. The first circle 650 represents the range region from device 2/position E to device 4/position A; the second circle 655 represents the range region from device 2/position E to device 6/position B; the third circle 660 represents slave device 2 / Location E to the range of the device 1 / position D. That is, the first circle 650 has a radius at the center of the device 4/position A and equal to the measured distance between the device 2 (and or the node of position E) and the device 4 (and or the node of position A), for example via RSSI or time-of-flight measurement data for the signal exchanged between device 2/position E and device 4/position A; second circle 655 has a center at device 6/position B and is equal to device 2/position E and device 6/position B The radius of the measured distance; the third circle 660 has a radius at the center of the device 1/position D and equal to the measured distance between the device 2/position E and the device 1 / position D. The three circles intersect in various positions. The average intersection or location 665 is determined by averaging the location derived from the set of optimal intersections, as described in International Patent Application Serial No. PCT/IB2006/054921, filed on Dec. 18, 2006, which is incorporated herein by reference. The right of the European Patent Application No. 05 112465.9 (Attorney Docket No. PH003 798, ID 405 346 and ID 406150), filed on Dec. 20, 2005, entitled "Method and Apparatus for Determining the Location of Nodes in a Wireless Network" A Method and Apparatus for Determining the Location of Nodes in a Wireless Network) '', the full text of which is incorporated herein by reference. 130169.doc -18- 200850056 For the assumption that H5, H6 produce the same three Other circles 670, 675, 680, and having an estimated position 685, assuming that the location of device 1 is at node E, rather than for node D of hypothesis H3, H4. As shown, fourth circle 670 has a device 4/ The center of position A and the radius equal to the measured distance between device 4/position A and device 2/position F; fifth circle 675 has the center of device 6/position B and is equal to device 6/position B and device 2/ Position F - The radius of the distance is measured; the sixth circle 680 has a radius at the center of the device 1 / position E and equal to the measured distance between the device 1 / position E and the device 2 / position F. f can be seen from Figure 6 Points 665, 685 depend on the parent hypothesis, since each branch 560, 570 specifies a different starting position or parent hypothesis H1, H2. In particular, assume that H3, H4 (with probability 610, 620) have the assumption of being a parent. H1 (with a probability of 510 of 510), which assumes (with a probability or probability of 0.75) that device 1 is at position D (for branch 560, 1 = D), with three circles 650, 65 5, 660 having an estimated position 665. In addition, assume that H5, H6 (with probability 630, 640) have the hypothesis H2 as a parent (with a probability of 520 of 520), which assumes (with a probability of 0.25) that device 1 is in position (E (for branch 570, 1=E) ), three of the circles 670, 675, 680 have an estimated position 685. Similarly, the four children assume the likelihood or probability of each of H3, H4, H5, H6 610, 620, 63 0, 640 and from the intersection 665 , 685 to the target position is proportional to or based on the distance. In addition, by This possibility of branching or progeny is multiplied by the probability of the parent hypothesis to assign the overall or combined probability. As shown in Figure 6, the overall probability of branch 560, 690 with respect to the likelihood of device 2 being at position E is 0.5, where device 1 Located at position D (1=D and 130169.doc -19- 200850056 2=E); the overall probability of branch 560, 692 (1=D and 2=f) is 0·24; the overall probability of branch 570, 694 (I = ε and 2 = D) is 0.05; the overall probability of branches 570, 696 (1 = E and 2 = F) is 0.21. Suppose H3 (with probability 610) has the highest overall probability of 〇·5〇, because its k assumes Η1 (with probability of 5 10) to inherit (〇·75) a good probability and produces a close to the target position E (assumed H3) Again point 665, which is closer than the distance from the intersection 665 of the hypothesis H4 to the destination; f, where the position F is assumed or assumed to be at position F. Correspondingly, the light source 丨 is assigned to the position D, and the light source two is assigned to the position E because of other chances 620, 630, 64 located at the same tree level (ie, the second level of the decision tree 6〇〇). In contrast, H3 is assumed to have the highest probability of 610. Of course, if desired, if the probability exceeds a predetermined value, the hypothesis H3 may be chosen, which may depend on the number of branches under a particular tree level. For example, in the case where the second level of the decision tree 600 has four branches, the predetermined level = 1/4, so a branch or hypothesis having a probability of about 1/4 or 0.25 is selected: to provide a node or location The correct assignment of the light source. Likewise, a branch or hypothesis having a probability less than a predetermined level may be trimmed or discarded, the predetermined level may be fixed, such as (M, or may depend on the number of branches, such as a multiple of the number of branches divided by (eg, 5 times) For example, for a second level of decision tree 600 with four: branches, 1/(4χ5 bu 1/2〇 or 〇〇5. To produce a modified hypothesis tree, too 糸铋β士4 & The system and method include an additional step of calculating the probability of improvement by re-evaluating the previous level of hypothesis. Second: The progeny hypothesis represents the device-to-location index' re-evaluation using the sub-generation hypothesis to provide additional reference locations. 7Regression After the establishment of = H3, H4, H5 and H6, the hypothesis and the chance of committing the crime are further increased, of which 130169.doc •20- 200850056 The overall probability is 610, 620, 63 0, 640 series 0·50 , 0·24, 0·05, and 0.21, as shown in Figure 6. As shown in Figure 7, and compared to Figure 5, an additional range measurement showing circles 710, 720, 73〇, 74〇 is now produced, and Can be used to re-evaluate hypotheses (such as the hypothesis Η1 shown in Figure 5) and to use their offspring Let (for example, the hypothesis Η3 shown in Figure 6 as a child of the hypothesis Η1) recalculate its probability. Referring to Figure 7, the branches of the decision tree 7〇0 are processed separately, since generally each hypothesis can have many descendants. For example, when re The calculation assumes a probability of Η1 when the 'childhood hypothesis Η3, (with probability 61〇,) will provide a reference position configuration different from the reference hypothesis Η4 (with probability MO') reference position configuration. Separately calculate new possibilities to ensure the whole The overall probability of a branch reflects its own unique set of beliefs. As shown in Figure 7, recalculating the probability 610 for hypothesis Η3, including generating a new circle 710 having a center at device 2 at position ε, and equal to the device a radius of the measured distance between 2 (and/or node Ε) and device 丨 (and/or node D). The intersection of this circle 710 with previously generated circles 530, 540 (as described in connection with Figure 5) is evaluated, and The other intersections of the three circles 53〇, 540, 710. Trim or discard the intersection with a lower probability, ie away from the possible nodes or positions of the device 1 (eg position D), and decide from the remaining intersections close to the possible position d Equally point 750, for example, to provide improved triangulation. The distance from the intersection 750 of the three generated circles 530, 540, 710 to the device 1 (position D) is less than the distance from the point 55 to the The distance of the device 〇 (position 〇). Therefore, the probability of recalculation 510' of the device at position D (ie, assumed H1) is greater than the probability of using 假设75 for the assumed 〇75, resulting in 130169.doc 21 200850056 The larger overall probability 610 of hypothesis H3' (shown in Figure 7) at 0.57, which is greater than the previously calculated overall probability 610 for hypothesis H3 of 0.50, as shown in FIG. Accordingly, it is more likely that the correct position of device 1 is position D and the correct position of device 2 is position E. That is, once the probability of recalculation becomes a factor for the overall probability of each branch 'should be noted for the hypothesis that H3 'the overall triangulation results have improved' and thus its overall likelihood 610' (from Figure 6 〇·5) Increase to 0·57 as shown in Figure 7. Similarly, the re-computer rates of 62〇, 63〇, and 640' are used to generate the other three hypotheses Η4, Η5, respectively, using similar triangulation, combined with the circle 53〇, 54〇, using additional circles 720, 730, and 740, respectively. , Η6, 0·24, 0.02, and 0.21° As shown in Fig. 7, for the assumption that 三角4' and Η6, the triangulation results 620, 640' remain substantially unchanged from 〇·24 and 〇21 (with The probability shown in Figure 6 is 620, 640). Suppose Η5' inherits the worse triangulation result from hypothesis H2, thereby reducing its probability 630, (from the probability of 〇.〇5 shown in Fig. 6 to 63〇) to only 0.02, as shown in Fig. 7. The recalculation indication hypothesis Η3 is the most consistent set of assignments within the device, ie device 1 is at position D, device 2 is at position ε, and devices 4 and 6 are at positions VIII and 分别, respectively. As shown in Figure 7, the worst triangulation 755 is used to assume Η2, where it is assumed that device 2 is in position and the device is "located at position E. This re-evaluation technique can be applied as a new level of assumptions established, Constantly returning funds to improve the parent hypothesis for each hypothesis in the tree. In fact, the most important is the probability that these leaves or progeny assume H3, H4, H5 & H6. Right overall total probability is along the decision The branches of the tree are independently re-counted 130169.doc -22- 200850056 Calculate 'actually without having to modify the probability of the intermediate hypothesis. By delaying the re-evaluation until the tree is fully completed' can significantly reduce the amount of processing time. However, advantageously Re-evaluate every few levels during tree construction to make a better pruning decision, which depends on a good estimate of the probability. Therefore, the probability estimate: the better it is possible to perform the correct pruning. Correspondingly, it is necessary to recalculate the probability before pruning. It seems that this example only makes subtle changes to the probability, but this technique can be applied when many hypothetical levels have been established. The ability to feed backwards is not only _parameter = point 'as given example - However, many reference points further improve the reliability of the angle measurement. Also, the slight change in the probability of calculation at many levels can lead to more dramatic changes, because the revision probability is from the parent to the child up on the hypothetical structure. Feedback until the top level is reached. Figures 8 through 10 show another example of triangulation to determine the location of the crying in the network 'As soon as the devices 1 to 10 (shown in Figure 10) are assigned to the node or location: to J 'Figure 8 is shown in Figure 8〇〇. Figure 9 shows the construction of the decision tree when it is wise. The device 5 is considered as a seemingly trusted assignment for position E, but for position (1) ° ° ° It has yet to be established 0. Therefore, by the Chengshi 4 a a LI, this is the triangulation shown by the thousand-averaged father and points 910, 920. 2: The result has a poor geometry, such as two possible positions of 忏5, 920 indicates ' Among them, the average intersection point or position 91〇 is close to the position =, and the other average intersection point 920 is close to the position F. Therefore, the typical two-angle measurement without re-evaluation leads to the result of the second-level double-dot low-angle test, even if Assigning one of the P-states 5 to the assignment of position E) is in fact positive True. Figure 1. Shows the mapping chest, which considers re-evaluating the intersection once the remaining 130169.doc -23- 200850056 position is placed by the child hypothesis. The new information has been extended for the triangulation test set, which improves geometry Shape, thereby improving the suspicion of probability calculation. In practice, the two possible knots for device 5 are located at the correct position, ie, bit. Under the assumption of the construction of the tree, re-evaluate the accurate estimate of the probability of supply and reduce The opportunity to prun the correct solution. The re-evaluation at the completion of the tree provides the most accurate probability in determining the seemingly most trusted solution. The system that re-evaluates the results by back-feeding information to improve the estimated probability of earlier assumptions And methods can be applied to any situation where decisions need to be made in the face of uncertainty. Reassessment techniques can significantly improve the estimates of the probability of use for each alternative solution. * It should be understood that the various components of the system are re-evaluated, such as various nodes, target devices, processor 410, memory 44 〇, 45 〇 'hard disk 43 〇, various circuit cards, such as the network card 45 shown in FIG. And displays 46, for example, may be interconnected by any type of bus, or may be coupled to each other by any type of link 'eg, including wired or wireless links. In addition, the processor 410, the memory 44〇, the 45〇, and the hard disk 43〇 may be centralized or distributed among various system components, wherein, for example, each target device may have its own controller or processor and memory. body. Of course, those skilled in the art will appreciate from this description that various components, such as transistors, receivers, or transceivers, antennas, modulators, demodulators, etc., may be included in the "first or network components" used for communication. Converters, duplex H-piers, multiplexers, etc. Communication or bonding between various system components can be by any component, such as wired or wireless. System components can be separated or integrated 130169.doc -24· 200850056 together, For example, it is integrated with the processor. It is known that the processor executes instructions stored in the memory, for example, it can also store other data, such as: system control scheduled or programmable settings. It will be appreciated that various modifications may be provided. The operational actions of the method are particularly well-suited for execution by a computer software program. For example, a computer software program may include modules corresponding to individual steps or actions of the method. Application data and other materials Received by a controller or processor to configure it to perform operational actions in accordance with the present system and method. Of course, such software, applications can be used The data and other materials are embodied in computer readable media such as integrated memory chips, peripheral devices or memory, such as memory memory that is consumed by the controller or optical module processor. And/or the memory can be any recordable medium (eg, resume, removable memory, CD-ROM, hard drive, DVD, floppy or memory card) or can be a transmission medium (eg, a fiber optic network) =, global poor network, electricity and / or wireless channels, for example, its use of t: proximity, code-by-multiple proximity, or other wireless communication systems.) Any heat: or development of the media can be used as a computer Read media and/or memory 'as long as it can store information suitable for poetry computer systems. Also: use extra memory. Computer can read media, memory and / or: his memory can be long-term, short-term, or long The processor/controller is configured to implement a wide variety of operations, operations, and functions disclosed herein. The memory can be distributed or local, and the processor can provide additional processors. Can be distributed or single 130169.doc -25- 200850056 = The memory can be implemented as any combination of electrical, magnetic or optical memory, or such defective memory devices. In addition, the term "memory"; should be considered "as to cover any information that can be read or written to the address-address in the addressable space accessed by the processor. With this definition, the information on the network (eg, the Internet) is still in the memory or in the memory of the memory because the processor can extract information from the network. The processor and memory can be any type of processor/controller. Handle the crying and catch the fish. ° Perform the various instructions and execute the instructions stored in the note =. The processor can be a specific application or a general purpose processor. The processor can be a dedicated processor for performing in accordance with the system. The general purpose processor can operate only for the function of the system. . The processor can utilize the program part, multiple pieces of code:: operation 'or can be used to use the special or multi-purpose integrated circuit hardware 4 4 2 to discuss the system only, and should not be considered as attached* The patent supplement is limited to any particular embodiment or group of specific embodiments. While the system has been described in detail with reference to the specific exemplary embodiments, it should be understood by those skilled in the art that many modifications and alternatives may be devised without departing from the spirit of the invention. With materials. The manner in which the description and the drawings are exemplified does not limit the scope of the appended claims. In interpreting the additional request item, it should be understood that: ) The package "Hai Si does not exclude the occurrence of a different component or action listed in the given request item; 夕 』 匕兀 130169.doc -26 - 200850056 b) The article before the component " 〇) ψ Μ - ι^ι, except for the occurrence of a plurality of such components. (1) The responsibilities of the patent stipulations of the stipulations of the stipulations of the stipulations of the stipulations of the stipulations of the stipulations It does not limit its stipulations, · functional representation; the hunting of the same item or hardware or software to perform the structure or e) any disclosed components will contain hardware electronic circuits), software parts (such as joint; parts (for example, Including discrete and integrated, computer stylized), and any of them: f) the hardware part may consist of one or two analogy and digit parts; b) the device and parts will be combined or separated from each other unless otherwise stated; - He. P-knife, h) Unless otherwise stated, 'There is no need for a shirt movement or a sequence of steps. [Simple description of the diagram] The descriptions that follow, the scope of the accompanying patent application and the accompanying drawings will be better understood. The device, system and method of the present invention And other features, aspects, and advantages, wherein: FIG. 1 shows a plan view showing a network node location and a target device in accordance with an illustrative embodiment; and FIG. 2 shows a wireless light network as shown in FIG. FIG. 3 shows an automatic commissioning of a device in accordance with an illustrative embodiment; FIG. 4 shows a processing device in accordance with an illustrative embodiment; and FIGS. 5 through 10 show examples, illustrating Recalculation of the probability of an illustrative embodiment. [Description of main component symbols] 130169.doc -27- 200850056 1 First device 2 Second device 4 Device 6 Device 100 Wireless network 210 Light source 220 Node 230 Power supply unit 300 System 310 Placement Algorithm 400 Processing Device 410 Processor 430 Hard Disk Drive 440 ROM 450 RAM/Network Card 460 Display 510 First Probability 510f Recalculated First Probability 520 Probability 530 First Circle 540 Second Circle 550 Intersection Point 560 Branch 570 branch 130169.doc -28- 200850056
600 決策樹 610 機率 610f 機率 620 機率 620丨 機率 630 機率 630? 機率 640 機率 640， 機率 650 第一圓 655 第二圓 660 第三圓 665 交叉點 670 第四圓 675 第五圓 680 第六圓 685 估計位置/交叉點 690 分支 692 分支 694 分支 696 分支 700 決策樹 710 圓 720 圓 130169.doc -29- 200850056 730 圓 740 圓 750 交叉點 800 陣列 900 三角測量 910 交叉點 920 交叉點 1010 交叉點 1020 交叉點 D 第一位置 E 第二位置 HI 假設 ΗΓ 假設 H2 假設 H2f 假設 H3 假設 H3f 假設 H4 假設 H4， 假設 H5 假設 H5! 假設 H6 假設 H61 假設 130169.doc -30-600 decision tree 610 probability 610f probability 620 probability 620 丨 probability 630 probability 630? probability 640 probability 640, probability 650 first circle 655 second circle 660 third circle 665 intersection 670 fourth circle 675 fifth circle 680 sixth circle 685 Estimated position/intersection 690 branch 692 branch 694 branch 696 branch 700 decision tree 710 circle 720 circle 130169.doc -29- 200850056 730 circle 740 circle 750 intersection point 800 array 900 triangulation 910 intersection point 920 intersection point 1010 intersection point 1020 intersection Point D First position E Second position HI Hypothesis ΗΓ Hypothesis H2 Hypothesis H2f Hypothesis H3 Hypothesis H3f Hypothesis H4 Hypothesis H4 Hypothesis H5 Hypothesis H5! Hypothesis H6 Hypothesis H61 Hypothesis H61 Hypothesis 130169.doc -30-