[發明專利]擁塞感知的路網移動對象連續K近鄰查詢方法

有效

• 申請號: 202110494786.7
• 申請日: 2021-05-07
• 公開（公告）號: CN113377828B
• 公開（公告）日: 2022-04-19
• 發明（設計）人: 董天陽;劉洋;胡鋯
• 申請（專利權）人: 浙江工業大學
• 主分類號: G06F16/2458
• 分類號: G06F16/2458;G06F16/9537;G06F16/29
• 代理公司: 杭州天正專利事務所有限公司 33201
• 代理人: 王兵

1.擁塞感知的路網移動對象連續K近鄰查詢方法，包括如下步驟：

1初始時刻擁塞感知的K近鄰查詢；

初始時刻擁塞感知的K近鄰查詢用于獲得在連續查詢時間段[t_i，t_j]開始時刻t_i距離查詢點帶權路網距離最近的K個移動對象；該階段采用基于擁塞感知的增量式路網擴展策略；在路網擴展的同時判斷出道路的擁塞性，確定道路擁塞性系數，對道路長度進行加權處理；具體包括：

11)根據車輛面積密度對道路的擁塞性進行判斷；利用了一種基于道路交通流特征參數設計道路擁堵判斷方法，具體為基于車輛面積密度Φ的道路擁堵判斷方法；以路口劃分出路網中的每條道路，將道路上汽車總占地面積和道路面積之比定義為車輛面積密度Φ；根據Φ劃分了四種擁堵級別，以及對應的道路擁塞系數ω，即道路長度加權系數；當Φ＜0.3時，該路段運行暢通，擁塞系數ω設為1；當0.3≤Φ＜0.41時，該路段處于輕度擁堵狀態，所以ω設為1.5；當0.41≤Φ≤0.53時，該路段處于中度擁堵狀態，所以ω設為2；當Φ＞0.53時，該路段處于重度擁堵狀態，通過性很差，車輛通過該路段要花費很長的時間，所以ω設為5；

12)根據擁塞系數ω對每條道路的長度進行加權處理；使用DijKstra算法預計算各個路網節點到查詢點的單源最短帶權路網距離；在路網的擴展過程中，會維持一個優先隊列決定路網節點擴展優先級；優先隊列中存儲的是路網節點距查詢點的最短帶權路網距離，權重代表道路的擁塞性；距離查詢點路網距離更近的路網節點的鄰接邊會被先進行擴展，直到獲得距離查詢點帶權路網距離最近的K個移動對象才停止路網擴展；

13)將得到的K個距離查詢點帶權路網距離最近的移動對象加入結果集；假設按照距離查詢點帶權路網距離由近到遠排序的K個移動對象為：p₁，p₂，...，p_k，其中p₁為距離查詢點帶權路網距離最近的對象，p₂為距離查詢點帶權路網距離第二近的對象，p_k為距離查詢點帶權路網距離最遠的對象；初始時刻擁塞感知的K近鄰查詢結果集為：P＝{p₁，p₂，...，p_k}；

2獲取需要監測的候選對象；

該階段是為了獲取構建或擴展局部路網所需的監測范圍，并在局部路網內監測候選移動對象；如果對整個路網進行監測查詢，那么計算成本太高，查詢效率會很低；本方法以監測范圍為基礎進行局部路網的構建和擴展，篩選掉大量不滿足查詢條件的移動對象；首先利用初始時刻擁塞感知的K近鄰查詢結果確定局部路網的監測范圍；然后在查詢點進行局部路網的構建與擴展，并在局部路網內進行移動對象距離查詢點最短帶權路網距離的計算；最后以帶權路網距離為標準進行候選移動對象的篩選，進而獲得滿足條件的候選移動對象集合；具體包括：

21)計算監測范圍；連續查詢時間區間[t_i，t_j]，查詢點q的監測范圍記為MD_q(t_i，t_j)，計算公式如下：

MD_q(t_i，t_j)＝ND_q，pk(t_i)+v_q*(t_j-t_i)*ω(q)+addDist (1)

addDist＝max{e_i.maxV*(t_j-t_i)*ω(i)}(e_i∈E) (3)

式中t_i，t_j表示連續查詢時間區間的起始終止時刻，Length(i)表示每條道路的長度，ω(i)表示每條道路的擁塞系數，E表示路網中所有邊的集合；ND_q，pk(t_i)表示在連續查詢時間區間[t_i，t_j]開始時刻t_i，此時查詢結果集P＝{p₁，p₂，...，p_k}中距離查詢點最遠的帶權路網距離，即p_k的帶權路網距離；v_q為查詢點的運動速度，v_q*(t_j-t_i)*ω(q)表示的是在連續查詢時間區間[t_i，t_j]內查詢點移動的帶權路網距離；addDist表示額外監測距離，目的是保證查結果的準確性，避免漏掉可能影響查詢結果的移動對象；

22)獲取候選對象；以距離查詢點帶權路網距離小于監測范圍的節點的鄰接邊為基礎構建局部路網，局部路網內包含了所有可能是連續K近鄰查詢結果的候選移動對象；然后以查詢點為中心開始進行路網擴展，將距離查詢點帶權路網距離小于監測范圍的移動對象添加到候選移動對象集合中，用于后續驗證；

3驗證候選對象，完成連續K近鄰查詢；

由于候選對象在不斷運動，位置信息在不斷發生改變；候選移動對象可能在連續查詢時間[t_i，t_j]內的某一時刻取代t_i時刻的結果集P＝{p₁，p₂，...，p_k}中最遠的移動對象p_k；該階段的目的就是確定結果集P每次發生更新的時刻，然后將連續查詢時間[t_i，t_j]劃分成多個子查詢時間區間[t_i，t_i+1]，[t_i+1，t_i+2]…，[t_j-1，t_j]，保證在每個子查詢時間段內任意時刻查詢結果都是相同的；

31)第一次連續查詢時間段劃分；根據局部路網內所有候選移動對象到達路網節點的時刻劃分多個子查詢時間區間，不僅保證每個子查詢時間區間內所有對象都在同一條路段上，還可以使帶權路網距離的計算更加準確；

32)第二次連續查詢時間段劃分；當候選移動對象p′到查詢點的帶權路網距離小于結果集中最大帶權路網距離時，結果集會發生更新，用p′替換p_k；將步驟31)中劃分的子查詢時間區間記為[t_m，t_n]，通過等式ND_q，p′(t)＝ND_q，p(t)確定結果集發生更新的時刻t；在此基礎上將[t_m，t_n]進一步劃分并將結果集進行更新：[t_m，t]：Res＝{p₁，p₂，...，p_k}；[t，t_n]：Res＝{p₁，p₂，...，p′}；

33)返回連續K近鄰查詢結果集；完成驗證后返回查詢結果集，連續查詢一段時間[t_i，t_j]內距離查詢點最近的K個移動對象返回的結果集為[t_i，t_i+1]，{p₁，p₂，...，p_k}，[t_i+1，t_i+2]，{p_k+1，p_k+2，…，p_2k}，…，[t_j-1，t_j]，{p_n，p_n+1，...，p_n+k-1}。