基於圖結構任務調度的並行測距方法與流程

2023-05-24 08:33:16

本發明屬於定位技術領域，特別是一種並行測距方法，可用於對多行動裝置的定位。

技術背景

隨著移動終端的普及與快速發展，行動裝置的定位需求也越來越大，目前最流行的定位技術即依靠gps衛星並結合網絡信號、基站進行綜合定位。通常在信號良好的室外條件下，基站與衛星的信號都能穩定的給行動裝置提供位置信息，能精確到十幾米甚至幾米的範圍。但是，一旦進入有信號幹擾的地方，衛星信號則不再能夠提供上述程度的精確度，其定位精度將降至幾百米的範圍。而網絡信號抗幹擾能力甚至不如衛星信號，在受到較嚴重的幹擾時通常都是網絡信號與衛星信號同時失效，使得定位精度進一步下降。因此，利用其它方式進行定位的技術在近年來開始逐步發展，並取得了初步的成果，其中利用聲學測距來進行定位倍受人們關注。

現有聲學測距方法主要有以下幾種：

專利公開號為cn104101863a的「基於智能行動裝置的定位系統和定位方法」，該方法提供了一種基於智能行動裝置的定位系統和定位方法，通過設置發送音頻信號的若干個定位器，利用智能行動裝置接受所述定位器發出的音頻信號，進而實現智能行動裝置的定位。該方法的不足之處在於定位器至少需要若干個，增加了系統搭設成本。且需要固定在某個地方才能在該區域進行定位，每次更換地方都需要將多個定位器重新設置，消耗時間久，從而造成目前不便推廣的現狀。

專利公開號為cn104459703a的「一種聲納測距方法和行動裝置」，該方法的實現步驟是：先發射超聲波信號；再利用超聲波信號與反射信號的發射和接收時間差，根據時間差獲得時間值，最後根據時間值以及超聲波信號的傳播速度，獲得測距距離。該方法的不足之處在於只能在兩臺設備之間進行互相定位，無法處理多點定位。

技術實現要素：

本發明的目的在於針對上述現有技術的不足，提出一種基於圖結構任務調度的並行測距方法，以減少信號幹擾環境中的測距耗時和降低設備成本的前提下，進行多點測距定位。

本發明的技術方案是：通過行動裝置wifi自建區域網，利用行動裝置將測距任務映射成圖結構來生成並行測距任務進行測距，其實現步驟包括如下：

(1)根據行動裝置數量設網絡中有n個節點，並在在眾多設備中選定一個行動裝置作為主節點m，其它節點作為從節點，並分別與主節點連接構成整個測距網絡；

(2)主節點m發布測距任務，生成測距的總任務集γ＝{tij}，再由並行測距調度算法生成單步測距任務集γq，其中tij表示第i個節點與第j個節點之間的待測距離，1≤i≤n,1≤j≤n,i≠j；

(2a)將當前總任務集γ映射為一個圖g，圖中頂點即測距任務的節點，邊則對應於測距任務；設置測距任務重試次數上限r，將所有測距任務的重試次數初始化為1；

(2b)初始化單步測距任務集γq和發射節點集iq，使其全為空集，設置節點測量次數m，將所有節點的被測次數m初始化為0；

(2c)從圖g中選擇至少有一條臨邊且m為0的節點作為發射節點i，將節點i加入到發射點集iq，任取與發射節點i連接的一點作為應答節點j，將節點i與節點j被測次數m置1，生成測距任務tij，並將其加入到單步測距任務集γq；

以此方法繼續尋找下一個發射點以及其對應的應答節點，將所有節點進行配對生成測距任務加入到單步測距任務集，對剩下的獨立節點則保留至下次測距任務；

(3)依據單步測距任務集γq及其中的發射節點集iq和各發射節點對應的應答節點進行測距：

(3a)指示所有發射節點集中的節點i∈iq通過發射器發射相應的聲音信號si，同時節點自身對該信號通過接收器進行接收，記錄發射節點i自身接收到信號si的時間t1i；

(3b)指示所有發射節點對應的應答節點j通過接收器接收發射節點i的標示信號si，並記錄接收到信號si的時間t2i；

(3c)應答節點j收到信號si後發射應答信號sj，同時對該信號進行接收，並記錄應答節點j自身接收到信號sj的時間t1j；

(3d)發射節點i接收應答節點j的應答信號sj，並記錄接收到相應信號的時間t2j；

(4)根據(3)中所記錄的時間信號，計算出發射節點與應答節點之間的距離；

(5)判斷單步任務集γq與總任務集γ的狀態，直至任務全部測完；

(5a)將測距成功和測距失敗但到達重試次數上限的任務tij從單步測距任務集和總任務集γ中刪除；

(5b)判斷單步測距任務集γq是否為空：

如果不為空，說明存在測距失敗且重試次數未達到上限的測距任務tij，將該任務重試次數加1，並將該測距任務tij重新加入到總任務集γ，再返回步驟(2b)生成下一次單步測距任務集γq重新測試；

如果為空，則進一步判斷總任務集γ是否為空，若總任務集γ不為空，則返回步驟(2b)，若總任務集γ為空，則測距完成。

本發明具有如下優點：

1)本發明由於只需要多部行動裝置測距，不需要其他的輔助設備及儀器，設備成本低。

2)本發明由於只用主節點行動裝置開啟wifi模塊，建立區域網來進行通信，不需要依賴運營商的各種通信網絡，不僅保證了通信的實時性，而且連接速度快，對外界的依賴小。

3)本發明由於是利用行動裝置來進行聲波定位，對測距定位的環境及地點沒有限定，同時由於行動裝置可隨意移動，故靈活方便，適應性強。

4)本發明由於是由並行測距來進行定位，測距時間比傳統的串行測距時間要短數倍，故能節約時間成本，提高了定位效率。

附圖說明

圖1為本發明的實現流程圖；

圖2為本發明中測距總任務集映射示意圖；

圖3為本發明中的兩臺行動裝置之間測距示意圖。

具體實施方式

下面結合附圖對本發明做進一步的描述。

參照圖1，本發明的具體實現步驟如下：

步驟1，利用行動裝置搭建測距網絡。

假設有12個行動裝置，通過12個行動裝置搭建測距網絡：

本實例中要求利用行動裝置發射信號進行測距，其中的行動裝置為手機或平板電腦或者其他具有聲音收發功能、wifi模塊以及具有計算能力的設備，本實例中的行動裝置採用的是手機，據此，本步驟的實現如下：

根據行動裝置數量設網絡中有n個節點，並在在眾多設備中選定一個具有接收和發布功能的行動裝置作為主節點m，其它節點作為從節點，主節點行動裝置開啟wifi模塊建立熱點，用於管理整個測距定位的過程，從節點通過wifi搜索功能找到熱點並加入該測距網絡，以此構成整個測距網絡。

步驟2，主節點m發布測距任務。

(2a)主節點生成測距的總任務集γ＝{tij}，即該總任務集γ由行動裝置的測距任務tij構成，在對多點定位時，每個節點與另外三個任意節點的待測距離tij作為測距任務加入到總任務集γ，為了提高定位的精確性，本實例中的總任務集由每個節點與另外四個任意節點的待測距離tij構成，其中tij表示第i個節點與第j個節點之間的待測距離，1≤i≤n,1≤j≤n,i≠j，再由並行測距調度算法生成單步測距任務集γq：

(2b)參照圖2(a)，將當前總任務集γ映射為一個圖g，圖中的頂點即測距任務的節點，邊則對應於測距任務；設置測距任務重試次數上限r＝3，將所有測距任務的重試次數初始化為1；

(2c)初始化單步測距任務集γq和發射節點集iq，使其全為空集，設置節點測量次數m，將所有節點的被測次數m初始化為0；

(2d)在圖(2a)中任意選擇節點1作為發射節點，將節點1加入到發射節點集iq中去，隨機選擇與節點1相連的節點2作為應答節點，將節點1與節點2的測量次數置1，生成測距任務t1,2加入到單步測距任務集γq；

接下來尋找下一個測量次數為0的發射節點並生成測距任務加入到單步測距任務集，直至剩餘一個測量次數為0的節點或沒有節點剩餘，最後生成的單步測距任務集，如圖2(b)所示，得到圖2(b)中單步測距任務集:γq＝{t1,2,t3,9,t5,4,t7,6,t12,11,t8,10}，此時發射點集為iq＝{1,3,5,7,8,12}。

步驟3，依據單步測距任務集γq及其中的發射節點集iq和各發射節點對應的應答節點進行測距。

此處每個節點的發射器與接收器，由揚聲器和麥克風構成，或者由其他能發射聲波和接受聲波的設備構成，其中節點的發射信號應該具有良好的自相關性，以便在噪聲環境中能夠更容易被檢測到。

發射節點i與應答節點j之間收發信號並記錄時間戳的過程如圖3所示，據此，本步驟實現如下：

(3a)指示所有發射節點集中的節點i∈iq通過發射器發射相應的聲音信號si，同時節點自身對該信號通過接收器進行接收，記錄發射節點i自身接收到信號si的時間t1i；

(3b)指示所有發射節點對應的應答節點j通過接收器接收發射節點i的標示信號si，並記錄接收到信號si的時間t2i；

(3c)應答節點j收到信號si後發射應答信號sj，同時對該信號進行接收，並記錄應答節點j自身接收到信號sj的時間t1j；

(3d)發射節點i接收應答節點j的應答信號sj，並記錄接收到相應信號的時間t2j。

步驟4，計算出發射節點與應答節點之間的距離。

根據步驟(3)中所記錄的四個時間戳t1i、t2i、t1j、t2j，代入到beepbeep算法的距離計算公式中，計算出發射節點與應答節點之間的距離：

dij＝c·[(t2i-t1i)-(t2j-t1j)]+dii+djj

其中c為測距時的聲速，dii表示發射結點i的麥克風和揚聲器之間的距離，djj表示應答節點j的麥克風和揚聲器之間的距離。

步驟5，判斷單步測距任務集γq與總任務集γ的狀態，直至任務全部測完。

(5a)將測距成功和測距失敗但到達重試次數上限的任務tij從單步測距任務集和總任務集γ中刪除；

(5b)判斷單步測距任務集γq是否為空：

如果不為空，說明存在測距失敗且重試次數未達到上限的測距任務tij，此時測距結束後，單步測距任務集γ如圖2(c)所示，有一個測距任務t3,9失敗，且重試次數為1，未超過最大重試次數3次，故需將任務t3,9重新加入到總任務集γ，如圖2(d)所示，並返回步驟(2b)繼續測距，直至任務集γ為空；

如果為空，則進一步判斷總任務集γ是否為空，若總任務集γ不為空，則返回步驟(2b)，若總任務集γ為空，則測距完成。

以上描述僅是本發明的一個具體實例，顯然對於本領域的專業人員來說，在了解了本發明內容和原理後，都可能在不背離本發明原理、結構的情況下，進行形式和細節上的各種修正和改變，但是這些基於本發明思想的修正和改變仍在本發明的權利要求保護範圍之內。