[發明專利]一種無線傳感器網絡節點定位檢測方法

有效

• 申請號: 201611208209.2
• 申請日: 2016-12-23
• 公開（公告）號: CN106792981B
• 公開（公告）日: 2019-10-29
• 發明（設計）人: 吳賀俊;丁奧
• 申請（專利權）人: 中山大學
• 主分類號: H04W40/24
• 分類號: H04W40/24;H04W64/00;H04W84/18
• 代理公司: 廣州粵高專利商標代理有限公司 44102
• 代理人: 林麗明

本發明提供了一種無線傳感器網絡節點定位檢測方法，該方法減輕單個節點資源消耗的同時還可以保證找到網絡中絕大多數可定位節點，進一步地，該方法只要求節點掌握其鄰域拓撲，因此在時間和空間上的開銷更小。

技術領域

本發明涉及無線傳感器技術領域，更具體地，涉及一種無線傳感器網絡節點定位檢測方法。

背景技術

傳感器網絡可定位狀態在傳感器定位、節點高效部署以及作為類似物體追蹤和事件檢測等位置相關應用的前置條件中是必不可少的，然而對于WSN來說，現存的定位性檢測方法要么在不同網絡條件下的適應性差，要么太復雜繁瑣。網絡的可定位問題實際上是把傳感器網絡抽象為一個平面圖進行討論的：

每個傳感器代表圖中一個節點，圖中一條邊意味著對應節點間距離已知。如果給定一個圖，以及圖中三個非共線點的位置且要求所有節點在滿足邊集合所指定的相對位置關系的情況下，對于圖中未指定位置的節點如果只存在一個合理的位置，那么這個圖就是可定位的。

圖的可定位性質已被證實和圖的剛性是緊密相關的，然而在實際的節點部署中可能只有部分子圖是有這樣的可定位性質的。考慮到這一點，實用性的算法都是考慮單個節點的可定位問題。給定圖中節點之間的位置關系和部分節點的位置，如果對于一個節點只存在一個可能的位置，那么該節點就是可定位的。

圖的剛性是指對于一個圖來說，其繪制在平面上的形式的個數是有限的。形式可以定義成這樣：給定圖中三個點的在平面中的坐標后，若存在一個圖中點到一個坐標集合的雙射關系，使得相鄰兩個點所對應的位置之間的距離等于兩點之間的邊所指定的距離，該坐標集合以及其旋轉平移變化的變體稱為一個形式。例如，添加一條對角線的矩形是剛性圖。一個全局剛性的圖則是指圖只有一個形式，對于一個全局剛性圖來說如果其中三個點的位置確定，那么其形式也只有一個坐標集合，也就是說圖是可定位的。例如，添加兩條對角線的矩形就是一個全局剛性圖。

在無線傳感器領域，為了檢測節點的可定位性質或是位置，已經有很多需要利用全局拓撲信息的中心化算法，比如RR3P算法。當然也有一些可以被配置在單個節點上的分布式算法，主要有ITP算法以及WE算法。

ITP算法的基本原理就是用三個位置已知的節點來定位一個未知節點。WE算法使用更為復雜的鄰域拓撲結構，對于每個節點分別嘗試以自身為輪式圖中心，在鄰居中找到一條回路用于構成一個完整的輪式圖，然后開始檢測該輪式圖，如果其中有多于兩個可定位節點，那么整個輪式圖是可定位的。RR3P算法給出了根據圖的拓撲結構尋找圖中可定位節點的充分必要條件，在一個冗余剛性圖中，如果對于一個點存在三條指向三個不同可定位節點的不交叉路徑，那么可以判定該節點是可定位的。

實際應用在WSN定位性判斷時，這三種算法都有各自的局限性質。ITP算法在稀疏部署的傳感器網絡中只有通過部署更多位置已知的節點才能完成定位檢測工作。WE算法本身算是對ITP算法的一個補充和改良，WE算法在網絡中傳播可定位狀態，在不同網絡配置下WE算法總是可以比ITP算法找到更多的可定位節點，但是這種提升是有限的，而且建立輪式圖是一個耗時耗力的過程，每個節點先要收集鄰居然后再向鄰居廣播，中心節點則需要獲取鄰居的鄰居并完成回路搜索。而在WSN中應用RR3P算法時，建立冗余剛性子圖就需要對應子圖的完整拓撲，此外三條路徑也要求了數據包的多跳傳輸，換言之，作為一個圖論算法RR3P算法完美解決了問題，但是該方法并不適用于不夠穩定的傳感器網絡。

發明內容

本發明為解決以上現有技術的難題，提供了一種無線傳感器網絡節點定位檢測方法，該方法減輕單個節點資源消耗的同時還可以保證找到網絡中絕大多數可定位節點，進一步地，該方法只要求節點掌握其鄰域拓撲，因此在時間和空間上的開銷更小。

為實現以上發明目的，采用的技術方案是：

一種基于全局剛性圖的無線傳感器網絡節點定位檢測方法，包括以下步驟：