[發明專利]一種路徑優化的方法、系統及裝置

在審

• 申請號: 201610358837.2
• 申請日: 2016-05-27
• 公開（公告）號: CN107438030A
• 公開（公告）日: 2017-12-05
• 發明（設計）人: 姜子炎;代允闖;徐雷
• 申請（專利權）人: 鄰元科技（北京）有限公司
• 主分類號: H04L12/733
• 分類號: H04L12/733
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種基于無中心網絡的用時最短路徑的優化計算方法，所述無中心網絡由若干個節點單元互連而成，所述節點單元為具有信息接收、處理、發送功能的計算機，其特征在于：所述方法包括如下步驟：

S1：所述無中心網絡中的任意一個或幾個節點單元觸發計算任務；

S2：所述無中心網絡中的某一個或某幾個節點單元成為計算的起始點，并向其所有的鄰居節點單元發送一個初始數據；

S3：所述無中心網絡中每一個節點單元與其鄰居節點單元進行數據的交互；

S4：經過若干次數據交互后每個節點單元計算收斂，每個所述節點單元的輸出結果是其到達計算起始點中的一個的用時最短路徑上的鄰居節點單元。

2.根據權利要求1所述的方法，其特征在于：所述步驟S3中節點單元間交互的數據直接或間接地包括從一個節點單元到其鄰居節點單元的預估時間。

3.根據權利要求1所述的方法，其特征在于：所述觸發計算任務的是檢測到危險情況的節點單元或檢測到導航請求的節點單元。

4.根據權利要求1所述的方法，其特征在于，所述計算的起始點為導航請求的起始點或目標點，所述初始數據為零或起始點/目標點到達其鄰居節點的預估時間。

5.根據權利要求1所述的方法，其特征在于，所述計算的起始點為疏散請求的出口點或室外的節點單元，所述初始數據為零或從出口點到達安全區域的時間。

6.根據權利要求1所述的方法，其特征在于：所述步驟S3包括如下子步驟：

S31.監聽是否收到鄰居節點單元發送的數據；

S32.判斷計時器T與預設值T_set的關系；

其中S31包括如下子步驟：

S311.如果收到鄰居節點單元發送的數據t_in，則：

a.計時器T置零；

b.計算 ，其中,所述t_i為該節點單元到t_in所對應的節點單元的預估時間；

c.記錄t對應的鄰居節點單元；

d.判斷t是否小于上一次的計算結果t_last：

如果t<t_last或者t_last不存在,則

e.將t發送給所有的鄰居節點單元；

重復步驟a；

如果t≧t_last,則

f.計時器T累加；

S312.如果未收到鄰居節點單元發送的數據，則：

重復步驟f；

其中S32包括如下子步驟：

如果T<T_set，則重復步驟S11；

如果T≧T_set，則該節點單元計算收斂，將步驟c中的記錄結果作為輸出結果；所述輸出結果表示該節點單元到達計算的起始節點的用時最短路徑的鄰居節點單元。

7.根據權利要求1所述的方法，其特征在于：所述步驟S3包括如下子步驟：

S31’:監聽鄰居節點單元發送的數據；

S32’:判斷計時器T1與預設值T_set1的關系，若T1≦T_set1，則返回步驟S31，若T1>T_set1則進入步驟S33；

S33’:根據監聽到的所有數據計算t=min(t_in,j+t_j)，其中,所述t_in,j為第j個鄰居發送來的數據，t_j是該節點單元到其第j個鄰居的預估時間，然后進入步驟S34；

S34’:判斷t與上一個時間步長內的數據t_last的關系，若t<t_last，則令計時器T2清零，將t發送給所有鄰居，并返回步驟S31；若t≧t_last或不存在t_last，則計時器T2累加，然后進入步驟S35；

S35’:判斷計時器T2與預設值T_set2的關系，若T2<T_set2，則返回步驟S31，若T2≧T_set2，則該節點單元計算收斂，記錄t對應的鄰居并作為結果輸出，所述輸出結果表示該節點單元到達計算的起始節點的用時最短路徑的鄰居節點單元。