[發明專利]一種基于三角形內點測試的邊界節點判定方法及裝置

有效

• 申請號: 202010216119.8
• 申請日: 2020-03-25
• 公開（公告）號: CN111405631B
• 公開（公告）日: 2022-08-12
• 發明（設計）人: 衛琳娜;鄭嘯;吳宣夠;郭會
• 申請（專利權）人: 安徽工業大學
• 主分類號: H04W40/02
• 分類號: H04W40/02;H04W40/24
• 代理公司: 南京九致知識產權代理事務所(普通合伙) 32307
• 代理人: 嚴巧巧

本發明提供的基于三角形內點測試的邊界節點判定方法及裝置，涉及通信技術領域，利用無線節點之間的通信關系，組合單個節點一跳通信范圍內的鄰居節點構成三角形，首先通過單個三角形的內點測試法判定節點是否為三角形內部節點，隨后通過對組成三角形的邊進行邊合格判定確認節點是否在三角形內部，準確實現對邊界節點的判定。本發明方法應用于網絡節點的一跳局部范圍，無需獲取測試節點的地理坐標或者節點之間的通信距離，可有效避免因節點定位和節點間隔測距帶來的誤差，提高邊界節點判定的準確性。

技術領域

本發明涉及通信技術領域，具體涉及一種基于三角形內點測試的邊界節點判定方法及裝置。

背景技術

在無線領域內無線設備的覆蓋關系到網絡各項任務執行指標的采集和分析。通過檢測位于網絡邊界的無線設備有助于后續檢測網絡對預定區域的覆蓋以及輔助其它后續工作進行。現有邊界節點的判定方法需要無線網絡的全局信息或者需要通過局部無線節點之間的大量通信，可能導致單個節點上的通信能量損耗過大或者計算任務過重。現有基于局部區域的判定方法大多需要單個節點的詳細坐標，不適用于很多節點精確坐標難以獲取的無線網絡和無線網絡的迅速發展。因此需要一種單節點執行基于局部信息但不依賴節點精確坐標的邊界節點判定方法。

發明內容

本發明目的在于提供一種基于三角形內點測試的邊界節點判定方法及裝置，該方法或裝置基于判定測試三角形和節點之間的關系，在一次獲取局部區域鄰居節點信息之后無需反復通信、計算和判定，判定方法計算量主要集中于集合的生成和元素是否包含于集合中，操作簡單。

為達成上述目的，本發明提出如下技術方案：一種基于三角形內點測試的邊界節點判定方法，包括

構建第一節點集合，所述第一節點集合為無線網絡中任一節點A在其通信范圍內所有一跳鄰居節點的集合；

判斷第一節點集合中一跳鄰居節點的數量，若一跳鄰居節點的數量小于3，節點A為邊界節點，判斷結束，否則進入以下步驟；

發送第一節點集合至集合內所有一跳鄰居節點，以便獲取第一節點集合中任一一跳鄰居節點在其通信范圍內與節點A共享的一跳鄰居節點的標識和數量；

構建第二節點集合，所述第二節點集合為第一節點集合中不包含與節點A共享一跳鄰居節點數量小于2的一跳鄰居節點；

構建第一三角形集合，所述第一三角形集合為遍歷第二節點集合內任意3個一跳鄰居節點構成的所有三角形；

判斷第一三角形集合內三角形的數量，若第一三角形集合為空集，節點A為邊界節點，判斷結束，否則進入以下步驟；

構建第二三角形集合，所述第二三角形集合為第一三角形集合中根據三角形內點測試法測試獲得的圍繞節點A的所有三角形；

判斷第二三角形集合內三角形的數量，若第二三角形集合為空集，節點A為邊界節點，判斷結束，否則進入以下步驟；

判斷第二三角形集合內是否存在合格三角形，若第二三角形集合內不存在任一合格三角形，節點A為邊界節點，判斷結束；

所述合格三角形為三角形的任一條邊為合格邊；

所述合格邊包括第一類型邊、第二類型邊和第三類型邊；所述第一類型邊滿足邊的兩側端節點互為一跳鄰居，所述第二類型邊滿足邊的兩側端節點包含相同的一跳鄰居節點，所述第三類型邊滿足邊的兩側端節點包含互為一跳鄰居的一跳鄰居節點。

進一步的，所述合格邊還包括第四類型邊，所述第四類型邊滿足第二三角形集合內不存在以第四類型邊的端節點以及第三節點為頂點的三角形；所述第三節點為第四類型邊兩側端節點通信的最短路徑上的節點。

一種基于三角形內點測試的邊界節點判定裝置，包括第一構建模塊，用于構建第一節點集合，所述第一節點集合為無線網絡中任一節點A在其通信范圍內所有一跳鄰居節點的集合；