車輛自組織網絡中基於道路網格的查詢方法

2023-05-14 21:36:56

專利名稱：車輛自組織網絡中基於道路網格的查詢方法
技術領域：
本發明屬於信息科學技術領域，具體涉及一種在車輛自組織網絡中基於道路網格的査 詢方法。
背景技術：
目前，車輛之間通過有限距離的無線通訊交換數據。這些車輛組成車輛自組織網絡。 不同車輛之上的數據組織為一個虛擬資料庫。用戶可以利用這種網絡獲取交通信息，從而 指導用戶選擇合適的交通道路，避免道路擁塞。在車輛自組織網絡環境中，利用車輛之間的通訊獲取交通信息，減少對交通基礎設施 的依賴，是目前日益得到重視的一種方法。傳統的方法在構建査詢計劃的時候，更多地考 慮結點之間的距離情況，選擇和目標結點距離較小的臨近結點形成査詢計劃，執行查詢。 但是，由於車輛的頻繁移動，導致通過這種技術構造的査詢計劃調整頻繁，査詢的散播和 結果的回收都面臨很多問題。因此，傳統自組織網絡環境中的查詢方法不能夠適應車輛網 絡的動態變化，導致查詢結果丟失，或者査詢消息發送過多。發明內容本發明的目的在於提供一種基於道路網格的査詢方法，通過相對固定的道路網格解決 自組織網絡環境中的動態變化的問題。本發明的車輛自組織網絡中基於道路網格的查詢方法，各網絡節點攜帶GPS定位系統，其步驟包括1) 查詢發起節點按照路由選擇算法，確定其到目標區域的路徑；2) 查詢發起節點按照預定規則選擇位於上述路徑的後繼節點，將攜帶該查詢發起節點 位置信息的査詢消息發送至該後繼節點；3) 所述後繼節點按照相同路由選擇算法，確定其到目標區域的路徑，並按照相同規則 選擇位於該路徑上的下一後繼節點，將攜帶發起節點位置信息的查詢消息發送至該下一後 繼節點，直至該下一後繼節點為位於目標區域的目標節點；4) 位於目標區域的目標節點接收到發起節點的査詢消息後，按照與發起節點路由選擇 算法匹配的路由選擇算法確定其到發起節點的路徑；5) 目標節點按照與上述預定規則相匹配的規則選擇位於上述路徑上的下一節點，將攜 帶發起節點位置信息的數據信息發送至該路徑上的下一後繼節點；6) 該下一後繼節點按照相同的與發起節點路由選擇算法匹配的路由選擇算法確定其到 發起節點的路徑，將攜帶發起節點位置信息的數據信息發送至該路徑上的下一後繼節點， 直至將信息發送至發起節點。當發起節點離開當前區域之前，按照相同方法選擇位於當前區域的節點作為下一節 點，將新的位置信息發送至該下一節點，並按照發送査詢消息的方式，向一下節點傳送， 直至發送至位於目標區域的目標節點。或當發起節點離開當前區域時，向所有能直接通信的位於該發起節點選定的到目標區 域路徑上的節點集合N發送位置變更信息，由收到該信息的路徑上的節點按相同方式向位 於該節點所選定的到目標區域路徑上的所有能直接通信的節點集合N發送發起節點的位置 變更信息。如目標節點接收到發起節點的新位置信息，按照與發起節點路由選擇算法匹配的路由 選擇算法確定其到發起節點新位置的路徑，發送攜帶發起節點新位置信息的數據信息發送 至該路徑上的下一後繼節點。當一中間節點既收到來自發起節點的新位置信息，又收到來自目標節點的數據信息 時，按照與發起節點路由選擇算法匹配的路由選擇算法確定其到發起節點新位置的路徑， 發送攜帶發起節點新位置信息的數據信息發送至該路徑上的下一後繼節點。當目標區域內進入新的節點，或當前目標節點自身移動，或目標區域內其他節點移動 而不再作為按照所述規則選定的目標節點時，當前目標節點將攜帶的發起節點位置信息和 自身的數據信息發送至新的目標節點。所述發起點的路由選擇算法採用發起點到目標區域的路徑最短的算法，所述與發起點 路由選擇算法相匹配的算法為採用該算法使得在返回方向上選擇的一區域的下一節點與 採用發起節點路由算法在發送方向上選擇的一區域上的下一節點相同。所述發起點的路由選擇算法釆用Dijkstra算法。按照所述發起點的路由選擇算法存在多條由發起節點到目標區域的路徑時，按照設定 的規則選擇一條路徑作為發起節點至目標區域的實際路徑；目標節點按照與所述設定規則 相匹配的規則選擇其至發起節點的實際路徑，以使兩條路徑是吻合的。選擇所述下一節點的規則為選擇能夠直接通信的選擇價值最大且選擇價值大於零的 節點。當不存在符合上述條件的節點時，當前節點等待直至出現上述下一節點。 所述消息設定生命周期，當超過生命周期時丟棄該消息。 為了解決現有的問題，本發明的設計思路是1. 為了減少車輛自組織網絡中車輛節點動態移動對查詢計劃的影響，本發明提供一 種新的基於道路網格的查詢計劃構建和執行策略。這種策略以相對固定的查詢計劃克服動 態環境所帶來的問題，提高了査詢計劃執行的穩定性。2. 本發明提供了一種査詢發起者位置移動的控制信息，利用控制信息，來動態調整 査詢計劃。3. 本發明提出一種基於時間窗口的數據消息收集機制。如圖1所示，本發明的查詢系統分為3個層次，第一個層次是查詢層，接受用戶提交的 查詢，轉換到消息層，同時從消息層中獲取數據，展示給用戶；第二個層次是消息層，包 括査詢消息、數據消息和控制消息，査詢消息主要包括查詢自身和查詢發起者的信息，數 據消息主要描述查詢的部分結果或者査詢的全部結果，控制消息主要用來維護查詢執行計 劃等；第三個層次是網絡層，是消息傳輸的網絡層支持，包括路由協議和連接協議。本發明支持的査詢是關係資料庫SQL查詢的子集，支持聚集函數，支持道路編號的條 件，支持持續時間last,支持採樣時間interval 。例如select count(*) from car where location=，t， lasUOOOs interval 20s。其含義是針對t道路上的車輛匯總情況，做出統計，整個査詢在網絡 中執行1000s，每隔20s向查詢發起者反饋道路中車輛的匯總情況。每個車輛節點即車輛上配備的系統包括GPS系統，能夠判定出某個節點所在的空間 位置；道路網格，包含查詢範圍的城市交通圖；計算能力，能夠完成最短路的計算。其中道路網絡從電子地圖中提取出來，結點表示道路的交叉路口，道路r表示兩個交叉 路口之間的道路。道路網絡f表示為tf= GV,￡)，其中vV表示為結點集合，￡表示為道路 集合。每條道路r^^^為(j'《凡& & d，其中j^表示道路/怖標示，(a刃)表 示,起點，(x2, /2)表示r的終點，"表示r的長度。車輛v能夠根據GPS的數據，判定v所在的道路r。本發明中査詢和數據的路由採用基於道路網格的路由選擇算法。路由方法具體描述如下A)在道路網格中路由路徑的發現給定源節點v和目標路徑r，路徑path(v，r)表示從v到r的最短路徑，最短路徑可以從Dijkstra算法(參見文獻E. Dijkstra. A note on two problems in connection with graphs. Numerical Mathematics, 1:395~412, 1959.)或者A承算法(參見文獻S. Russell and P. Norvig. Artificial Intelligence: A Modern Approach. Prentice-Hall, Englewood Cliffs, NJ, 2nd edition edition, 2003.)來發現。考慮到源節點和目標節點的位置，發現的路徑是有方向的。採集 的路徑發現算法發現的路徑需要滿足下列要求給定當前位置Pw和目標位置PM，對於任 意在path(P[1], pw)上的節點k， k的位置為p[k],則k到t的路徑path(p[k], p[t])是path(pw, p[t]) 的後綴。B)選擇消息傳播的下一個節點給定査詢傳播的中間節點a和其位置pw，査詢目標t和其位置pw,中間節點a選擇位於 發現路由路徑path(pw,pw)的道路上的一個節點b來傳遞査詢。節點b需要滿足下列要求節 點b是節點a直接可通信的鄰居節點；如果節點a存在多個滿足條件的節點b，則由選擇價值 為正值並且最大的節點b來傳遞査詢。節點b的價值定義為b.d* (b.s + dist(a， b))，其 中b位於path(pw,pw)的道路上，當運行方向和路徑path(pw,pw)—致的情況下，b.d= l，否 則，b.d^1; b.s表示b運動的速度，dist(a, b)表示節點a和節點b之間的距離。如果沒有滿足這一條件的鄰居節點，節點a將保留這個消息，同時不斷測試直接鄰居節 點是否滿足這一條件。如果節點a移動出了原有路由路徑path(p恥pw)，其中pw是節點a原有 的位置路徑，pw是目標位置，則節點a傳遞消息到同一路徑的後繼節點c，通過c繼續擴展消 息到p[t]。每個車輛節點都包含一個消息隊列，按照固定的時間間隔處理消息隊列。消息包括一 個通用的消息屬性和特定的消息屬性。對於某消息msg,通用的消息屬性包含一個生命周期 屬性msg.life，當msg.life為O的時候，msg從消息隊列中刪除。本發明利用消息類型屬性msg.type，來區分不同的類型的消息。針對本發明的三類不 同的消息，包括查詢消息、數據消息和控制消息，其屬性描述如下査詢消息qmsg表示為qmsg= (life, q[id], q[e], sid]， s[咖d], s[t]): 其中，q關可以認為是由車 輛的ID和査詢的啟動時間戳組成；q[e]是査詢q的查詢表達式；s[id]是查詢發起者的編號； s[roadi表示查詢發起者所在的道路網格中的道路編號；s[t]是査詢的啟動時間。査詢q的數據消息dmsg表示為dmsg=(life,q[id]，q[e],D,tp，s[id]，s[r。ad]): q[id]是査詢q的ID; q[e]表示査詢q的查詢表達式；D表示結果集合；tp表示數據產生的時間戳，s[id]表示查詢發 起者的編號，W。一表示査詢發起者所在的道路編號。控制信息包括和直接鄰居交換的消息，以及通知其他節點査詢發起者位置變化的消 息。位置變化消息的格式是cmsg氣s降life，oldpos,newpos)。其中，s[id]表示查詢發起者 的編號；oldpos表示査詢發起者在道路網格中原有的位置，以街道為粒度；newpos表示査 詢發起者在道路網格中的新位置，以街道為粒度。如圖2，在查詢過程中，節點可以根據其在某個査詢中的作用不同分為4類節點，包括 查詢發起者、查詢中間節點、査詢目標節點和無關節點。對於每個移動節點，都能根據其 所在的位置和查詢表達式中的位置謂詞判定其在査詢處理過程中的作用。每個節點帶有消息隊列。當節點n處理消息隊列中的每條消息msg的時候，都要判定針 對這條消息msg的節點n的角色。根據節點在處理這個消息所承擔的不同角色實現不同的動 作。如圖3，査詢發起者接受用戶提交的查詢，該查詢q用來探測特定道路r上的交通情況， 這個査詢通過車輛自組織網絡的不同節點協同操作收集相關的數據反饋給用戶。當査詢者接受用戶的查詢q的時候，查詢發起者根據當前的時間sw，節點的編號SM, 節點所在道路網格的道路編號s[r。ad]，生命周期Life等價於last/Interval(Last和interval來源於 査詢表達式)，查詢的編號q問由車輛編號和發起時間組成，產生査詢消息qmsg-(life, q[id],q[e], S間,S[r。ad], S[t]),査詢消息基於道路網格路由發送到下一個節點。若一個節點接受一個數據消息，且該數據消息中的SM標識等價於當前節點的s^標識，則這個節點是查詢發起者。這樣，接受的數據消息中包含査詢的結果，需要解析數據消息 中的結果，將結果反饋給用戶。如果查詢發起者從道路^到道路r2，可能導致査詢結果反饋的時候結果丟失，査詢發起 者組合一個控制信息cm堪=(S[id], life, ri, r2)，並沿著原有路由路徑發到目標路徑中。其中s關 標識等價於節點標識，life等價於last/Interval。如圖4，當一個車輛v接收到一個查詢消息或者數據消息，如果v不是査詢發起者，或 者v不滿足査詢的條件，貝Uv是一個查詢中間結點。v將繼續擴散查詢消息或者回送結果到 査詢發起者。査詢中間節點所採用的具體動作依賴於其接受消息的類型1.如果v接收到的msg是一個查詢消息，v從msg中査詢表達式qw中提取查詢的目標路 徑t， v計算當前位置到目標路徑t的位置之間的道路path(pM,pw)。選擇價值最大的直接鄰居 節點vH專遞消息。msg從v的消息隊列增加到^的消息隊列。Msg的lifetime屬性設置為l。2. 如果v接收到的msg是一個數據消息，v按照路由選擇算法和節點選擇算法將數據消 息發送到査詢發起者所在的街道印。一，其中S[^d]從數據消息中獲取。3. 如果v接收到的msg是一個控制消息，v檢查msg是否存在於v的消息隊列中，若存 在，則這個消息會被忽略；否則，將msg存儲在消息隊列中，繼續在當前道路上擴散msg。 同時，v檢査其消息隊列中是否存在數據消息dmsg，其中dmsg的s間和msg的s[id]—致， 如果存在，將dmsg中的s[r。ad]修改為msg的newpos。如圖5:當節點v接收到從m節點發送的一個査詢消息，v判定自身是査詢的目標節點， 同時m節點不是査詢的目標節點，貝ljv是第一個進入目標道路的節點，針對這個消息，設置 v的第一個進入目標區域的標記為True。v根據當前v自身的速度s，抽取査詢消息中的相關數據項，形成一個數據消息 dmSg=(life，q[id]，q[e],D,tp,S[id]，s[r。ad])，其中，D數據集合不僅包含v的數據，同時帶有v進入 目標道路的時間t和v在當前道路上的平均速度s。由於對D進行了擴展，所以這個數據消息 稱為擴展數據消息。v將自身產生的數據消息dmsg、接收到的同一街道其他節點發送的擴展數據消息，和 査詢消息發送到同一路徑的後繼節點。後繼節點按照同樣的策略來處理產生擴展數據消 息，傳遞擴展數據消息。如果時間滿足査詢表達式中的時間間隔，貝Uv需要向査詢發起節點反饋一個查詢結果。 v分析獲取到的所有擴展數據消息，針對每個擴展數據消息dmsg，判定擴展數據的有效性， 對有效的擴展數據，執行查詢表達式中的聚集操作或者檢索操作，形成査詢結果，按照路 由選擇算法和中間節點選擇算法，回送査詢結果到查詢發起者。擴展數據消息dmsg有效性 的標準是(t-t2) 2《是否為真，其中t是當前時刻，t2是dmsg中的車輛進入街道的時刻，L 是路徑的長度。若節點v是査詢目標節點，同時接收到控制消息，v檢査消息隊列中SM等價於控制消息 的s間的査詢消息。如果存在，將查詢消息中的s—d]替換為控制消息中的newpos。同時，v 將這個控制消息擴散到目標區域中。如圖6，展示了說明了目標節點的數據收集策略如果al是第一個接收到査詢消息的目 標節點，則al產生一個擴展數據消息，連同al所接收的査詢消息，發送到後繼節點中；同 時，如果滿足査詢時間間隔，則根據接收到的全部擴展數據消息，形成一個包含査詢結果的數據消息，按照路由策略和節點選擇策略，發送回査詢發起者中。整個目標節點集合中 只有一個節點組織產生最終的査詢結果。本發明技術的優點和積極效果如下1) 本發明不需要集中式的網絡體系結構的支持，通過車輛自身的計算能力和通訊能 力實現遠程道路情況的監控。2) 本發明充分利用交通道路網格和交通道路規則，其查詢計劃建立在道路網格基礎 上，從而減少了査詢路由和數據路由的丟失率。3) 本發明在査詢處理過程中引入控制消息，避免了査詢發起者移動帶來的結果反饋 失效的問題，支持査詢計劃的動態調整，提高査詢處理的穩定性。4) 本發明採用目標區域節點一次消息傳遞來獲取査詢的結果，減少了消息的傳遞數 量，提高了數據的可用性。


圖l本發明的査詢執行的層次圖；圖2節點角色判定示意3査詢發起者處理流程4査詢中間節點處理流程5査詢目標節點處理流程6目標節點的數據收集策略示意7查詢處理的說明8目標節點數據收集l圖9目標節點數據收集具體實施方式
本發明的方法，給定當前位置卯]和目標位置p[t]，對於任意在path(p[i], p[t])上的節點 k， k的位置為p[k],則k到t的路徑path(p[k]， pw)是path(P[1]， p[t)的後綴。以圖1為例，節點1發現的到目標區域的路徑是1-9-6-7-2.節點6在發現的路徑中， 如果節點6希望發送數據到節點2，則節點6發現的路徑是6-7-2。在路徑發現過程中，採用的算法是Dijkstra算法或者其他滿足所發現路徑特性的算法。如在路徑發現過程中，存在多條滿足要求的道路，則對現有發現算法增加限定規則。 如發現査詢發起者到查詢目標的過程中，存在多條長度一致的路徑，則按照右手原則，優 先選擇當前節點右面的路徑。反之，在數據消息從目標發送回查詢發起者的過程中，存在 多條長度一致的路徑，則按照左手原則，優先選擇當前節點左面的路徑，以使兩條路徑是 吻合的。給定査詢傳播的中間節點a和其位置pw,査詢目標t和其位置pw，中間節點a選擇位 於發現路由路徑path(p^， PM)的道路上的一個節點b來傳遞査詢。節點b需要滿足下列要 求節點b是節點a直接可通信的鄰居節點；如果節點a存在多個滿足條件的節點b，則 選擇價值為正值並且最大的節點b。節點b的價值定義為b.d * (b.s + dist(a, b))，其中b位 於path(pw,p閃)的道路上，當運行方向和路徑path(p[a]，pw)—致的情況下，b.cK,否貝iJ， b.d =-1; b.s表示b運動的速度，dist(a， b)表示節點a和節點b之間的距離。該價值計算公 式，考慮了中間節點的運動速度，和當前節點的距離以及方向，目的是提高査詢擴散和數 據傳遞的效率。按照圖1的示例，如果節點1向目標路徑發送査詢消息，直接可達的鄰居包括節點6 和節點9，由於節點6距離節點1更遠，按照價值計算，則節點1選擇的節點是6。如果當前節點n不能夠發現合適的中間節點傳輸査詢消息或者包含結果的數據消息， 則當前節點保持査詢消息或者數據消息。當n離開當前位置和目標區域的路徑時，n將查 詢結果或者數據保存到當前節點同一方向的其他節點上。由於査詢消息傳遞和數據消息反 饋建立在道路網格上，而車輛都在道路網格上運行，按照這種方法實現消息傳遞丟失率較 低。查詢過程中，每個節點保持一個消息隊列。消息隊列按照特定的時間來處理，每處理 一次，消息中的life值減l。這樣，life值可以控制整個系統發送的消息。當life值設置高， 則査詢更加穩定，但是査詢消息代價高；如果life值設置為1，則在系統中同一時刻不會 存在相同的查詢消息和數據消息，這樣減少了系統的消息數量，但是可能導致査詢結果的 不完備。實施例1以圖7為例，第一個節點發出查詢，第一個節點是査詢發起者，2， 3， 4在査詢的目 標路徑上，根據最優路徑算法，查詢發起者到目標道路的路徑是l 9 6 7 2。查詢發起者l 號節點選擇的節點是6。接收到查詢消息的節點6檢査自身的位置是否滿足査詢的要求。如果不滿足，則還需要選擇下一個節點來擴散査詢。選擇規則等同於查詢發起者選擇後繼 節點的規則，首先根據道路網絡路由的方法發現傳遞路經，之後根據最高價值的方法選擇 下一個節點，則節點6選擇節點7。反覆選擇下一個節點，直到査詢消息擴散到目標區域。 接收到查詢消息的節點檢查自身位置是否滿足査詢要求，如果滿足，則該節點是查詢 目標節點。査詢目標節點收集數據，形成一個査詢結果的數據消息dmsgKlife,q卩d]，q妙D,SM， S[road])，其中，Life表示消息的存在周期，q[id]表示從査詢消息中抽取的査詢編號，q[e]表示從查詢消息中抽取的査詢表達式，D表示從節點2計算出來的結果數據，印d]表示從査詢消息中抽取的査詢發起者的編號，S[r。叫表示査詢發起者所在的街道。査詢目標節點按照基於道路網格的路徑發現算法，發現査詢結果從目標區域到查詢發起者的反饋路徑，將數據消息dmsg按照該路徑反饋到查詢發起者中。按照圖7的示例，節點2檢査自身的位置，滿足查詢的條件，則節點2是查詢的目標 節點。節點2產生數據消息，發現當前位置到查詢發起者的路徑2-7-6-9-1。査詢目標節點產生數據結果的反饋路徑之後，按照步驟2的方法選擇滿足該路徑要求 的節點作為中間節點，傳輸數據結果的數據消息到查詢發起者。按照圖7的示例，節點2選擇節點7作為査詢結果回送的中間節點。接收到數據消息的節點，根據數據消息中SM和節點自身的s間，判定這個數據是否是 該節點所提交的查詢。如果不是，則繼續傳遞數據消息，直到節點r的s問等同於數據消息 中的s關。節點r是査詢發起者，節點r從數據消息中獲取結果D的信息，顯示給最終用 戶。以圖7為例，節點7收到數據消息，根據數據消息中的晌和節點7自身的s[id],發現 節點7不是查詢發起者。節點7選擇節點6，節點6選擇節點1，最後節點1判定數據消 息是自身査詢的結果。實施例2當査詢發起者從位置n移動到r2所在的區域之前，査詢發起者產生一個控制信息cmsg =(s[ld], life, n, r2)。其中s間標識等價於節點標識，life設置為一個超過1的數據，如3， n 是查詢發起者原有位置，r2是査詢發起者新的位置。査詢發起者按照道路網格路由選擇算 法發現傳遞到目標區域的路徑path和節點選擇算法，選擇合適的節點擴散控制信息到目標 區域。以圖7為例，當節點1從位置1轉移到位置l'的時候，節點1組合產生一個控制消息 cmsg，發送到節點9，節點9繼續發送，直到發送到節點2中。實施例3為了提高數據消息反饋的概率，控制消息按照特定道路廣播的方式來進行。控制消息的生命周期設置為大於1的數值，如3，按照道路網格路由選擇算法發現路由路徑，選擇路徑上所有直接可達鄰居節點，發送位置變更消息。如果某個節點收到多次同一個位置變更消息，則直接忽略重複的位置變更消息。 以圖7為例，當節點1從位置1轉移到位置l'的時候，節點1組合產生一個控制消息cmsg,發送到節點6和節點9，節點6和節點9繼續發送，直到目標節點2中。其中，節點6如果收到節點9的控制消息，直接忽略。(上述節點6變動時的兩種方式，其一是按照權利要求3的方式，點對點發送，其二是廣播的方式發送)實施例4目標節點在收到控制信息之後，更新原來査詢發起者的位置信息。目標節點在產生新的數據消息的過程中，數據消息的S[r。afl設置為新的位置信息。目標節點重新計算結果反饋 路徑，數據消息的傳遞按照新的反饋路徑發送。按照圖7的示例，在查詢發起者的位置從i移動到r的時候，節點2收到位置變化消息，其發現的新的路徑是2-7-6-9-l，； 實施例5如果某個中間節點，如節點7同時接收到查詢發起者節點1的位置變動的控制消息和 目標節點2反饋的數據結果消息，則節點7根據控制消息中的查詢發起者新的位置s[road] 和當前節點7的位置，計算結果傳遞的路徑和下一個中間節點，並更改節點7發送的數據消息中的S[r。一項。實施例6如果查詢定義中査詢執行時間是連續的，則目標節點按照査詢中給定的間隔時間產生 結果數據反饋給査詢發起者。在目標節點收集數據的過程中，需要考慮目標節點本身的移動性、目標節點通訊範圍的有限性、以及收集過程中消息量。
以圖8為例，如果負責發送結果數據的查詢目標節點2發生移動，則節點2探測同一 方向的後繼節點12，將自身數據信息D2、進入道路時刻t2、以及平均速度V2，發送到後
繼節點12。節點12根據目標道路的長度L，節點2進入目標道路的時刻t2，當前時刻t, 節點2的速度V2，判定(t-t2) 2〈L。如果為真，則節點2判定為依然存在於査詢的目標區 域中，節點12利用自身數據和節點2的數據，產生一個數據消息，反饋到査詢發起者。 如果為假，則節點2已經離開目標區域，節點12近利用自身的數據產生一個數據消息， 反饋到査詢發起者。
如圖9當節點12移動，發現節點13進入目標區域，節點12將自身數據和接收到的節 點2的數據發送到節點13。節點13按照上述規則，判定節點12和節點2當前位置的有效 性。在滿足査詢時間間隔的情況下，節點13根據所收到的所有有效數據和自身數據，產 生一個數據消息，負責將數據消息反饋到查詢發起者。
此過程持續，直到査詢持續時間滿足為止。
權利要求
1.一種車輛自組織網絡中基於道路網格的查詢方法，各網絡節點攜帶GPS定位系統，其步驟包括1)查詢發起節點按照路由選擇算法，確定其到目標區域的路徑；2)查詢發起節點按照預定規則選擇位於上述路徑的後繼節點，將攜帶該查詢發起節點位置信息的查詢消息發送至該後繼節點；3)所述後繼節點按照相同路由選擇算法，確定其到目標區域的路徑，並按照相同規則選擇位於該路徑上的下一後繼節點，將攜帶發起節點位置信息的查詢消息發送至該下一後繼節點，直至該下一後繼節點為位於目標區域的目標節點；4)位於目標區域的目標節點接收到發起節點的查詢消息後，按照與發起節點路由選擇算法匹配的路由選擇算法確定其到發起節點的路徑；5)目標節點按照與上述預定規則相匹配的規則選擇位於上述路徑上的下一節點，將攜帶發起節點位置信息的數據信息發送至該路徑上的下一後繼節點；6)該下一後繼節點按照相同的與發起節點路由選擇算法匹配的路由選擇算法確定其到發起節點的路徑，將攜帶發起節點位置信息的數據信息發送至該路徑上的下一後繼節點，直至將信息發送至發起節點。
2. 如權利要求1所述的方法，其特徵在於當發起節點離開當前區域時，按照相同方法選 擇位於當前區域的節點作為下一節點，將新的位置信息發送至該下一節點，並按照發送査 詢消息的方式，向下一節點傳送，直至發送至位於目標區域的目標節點。
3. 如權利要求1所述的方法，其特徵在於當發起節點離開當前區域時，向所有能直接通 信的位於該發起節點選定的到目標區域路徑上的節點發送位置變更信息，由收到該信息的 路徑上的節點按相同方式向位於該節點所選定的到目標區域路徑上的所有能直接通信的 節點發送發起節點的位置變更信息。
4. 如權利要求2或3所述的方法，其特徵在於如目標節點接收到發起節點的新位置信息， 按照與發起節點路由選擇算法匹配的路由選擇算法確定其到發起節點新位置的路徑，發送 攜帶發起節點新位置信息的數據信息發送至該路徑上的下一後繼節點。
5. 如權利要求2或3所述的方法，其特徵在於當一中間節點既收到來自發起節點的新位 置信息，又收到來自目標節點的數據信息時，按照與發起節點路由選擇算法匹配的路由選 擇算法確定其到發起節點新位置的路徑，發送攜帶發起節點新位置信息的數據信息發送至 該路徑上的下一後繼節點。
6. 如權利要求1所述的方法，其特徵在於當目標區域內進入新的節點，或當前目標節點自身移動，或目標區域內其他節點移動而不再作為按照所述規則選定的目標節點時，當前 目標節點將攜帶的發起節點位置信息和自身的數據信息發送至新的目標節點。
7. 如權利要求1所述的方法，其特徵在於所述發起點的路由選擇算法為發起點到目標區 域的路徑最短的算法，所述與發起點路由選擇算法相匹配的算法為採用該算法使得在返回 方向上選擇的一區域的下一節點與採用發起節點路由算法在發送方向上選擇的一區域上 的下一節點相同。
8. 如權利要求7所述的方法，其特徵在於所述評發起點的路由選擇算法採用Djksra算法。
9. 如權利要求1或7或8所述的方法，其特徵在於按照所述發起點的路由選擇算法存在 多條由發起節點到目標區域的路徑時，按照設定的規則選擇一條路徑作為發起節點至目標 區域的實際路徑；目標節點按照與所述設定規則相匹配的規則選擇其至發起節點的實際路 徑，以使兩條路徑是吻合的。
10. 如權利要求1或7或8所述的方法，其特徵在於選擇所述下一節點的規則為選擇能夠 直接通信的選擇價值最大且選擇價值大於零的節點。
11. 如權利要求10所述的方法，其特徵在於當不存在符合上述條件的節點時，當前節點 等待直至出現上述下一節點。
12. 如權利要求l所述的方法，其特徵在於所述消息設定生命周期，當超過生命周期時丟 棄該消息。
全文摘要
本發明公開了一種在車輛自組織網絡中基於道路網格的查詢方法，支持通過自組織網路實現多跳距離街道情況的信息獲取。本發明通過相對固定的道路網格建立查詢執行計劃，解決自組織網絡環境中的車輛動態變化所帶來的問題，提高了查詢計劃執行的穩定性；同時引入了一種表明查詢發起者位置移動的控制信息，利用控制信息，來動態調整查詢計劃；又提出一種基於時間窗口的數據消息收集機制。本發明的查詢方法在自組織網絡環境中能夠適應車輛網絡的動態變化，減少了查詢過程中的消息傳輸代價。
文檔編號G01C21/34GK101257443SQ200810057749
公開日2008年9月3日 申請日期2008年2月15日 優先權日2008年2月15日
發明者孫勇義, 楊冬青, 王騰蛟, 軍 高 申請人:北京大學