[發明專利]一種基于輪狀圖的無線網絡終端的定位方法

有效

• 申請號: 201110031172.1
• 申請日: 2011-01-28
• 公開（公告）號: CN102143580A
• 公開（公告）日: 2011-08-03
• 發明（設計）人: 楊錚;劉云浩;何源;李向陽
• 申請（專利權）人: 北京浩陽華夏科技有限公司
• 主分類號: H04W64/00
• 分類號: H04W64/00;H04W84/18
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明屬于無線自組織網絡與傳感器網絡領域，涉及無線網絡定位技術，用于對無線網絡終端進行定位，以最后計算出無線網絡終端的各個節點的具體位置和信息。

背景技術

隨著通信技術、傳感器技術和嵌入式計算技術的快速發展和日益成熟，具有通信、傳感和計算能力的微型傳感器節點開始出現，并且被逐漸的應用到生產和生活之中。這種傳感器網絡能夠協調地感知、采集和處理網絡覆蓋區域內的各種環境或監測對象信息，并發布給需要這些信息的用戶。傳感器網絡將邏輯上的信息世界與真實的物理世界融合在一起，深刻地改變了人與自然的交互方式，可廣泛地應用于環境監測、工農業控制、生物醫療、國防軍事等諸多領域。

在傳感器網絡中，大量傳感器節點以自組織(ad-hoc)的方式組成無線網絡，協同將感知數據傳送到基站(sink)。感知數據必須結合采集這些數據的位置信息，才能為各種應用服務。因此，獲取傳感器節點位置成為傳感器網絡應用的關鍵技術。由于傳感器通常部署在環境險惡或者遠離人類控制的區域，部署方式也并非手工完成(例如飛機播撒等)，傳感器位置在部署前不可設定或預知，需要在部署后通過節點進行物理測量和計算完成自動化的定位。

全球定位系統(GPS)是一個較成熟的定位方案，但是為大量傳感器裝配GPS接收器耗資巨大，不適用于傳感器網絡。另外，GPS方案并不是普適的，它不能應用于室內或者地下等環境。近些年，許多研究機構和人員對無線自組織網絡中的節點定位問題展開研究，提出了一種合作式節點定位方法(cooperative?localization)，或稱為網絡定位(network?localization)。在這種方法中，一部分稱為信標(beacon)的特殊節點知道自身位置(例如使用GPS接收器)，而其余大部分普通節點通過測量節點間物理距離來計算其位置。節點間距離可以通過信號強度(received?signal?strength)、信號傳播時間(time?of?arrival)、信號傳播時間差(time?difference?of?arrival)等技術測量。

基于這些測量技術，無線自組織網絡可以抽象為距離圖(distance?graph)G＝(V，E)，其中V是無線網絡節點集合，如果邊(i，j)屬于E中當且僅當節點i和節點j之間的距離d(i，j)可以測量。在距離圖中，信標節點之間是連通的因為它們之間的距離可以計算出來。

在本發明中，我們只考慮二維空間中的網絡定位，涵蓋了傳感器網絡定位的主要內容。

傳統基于測距的定位方法(range-based?localization)一般采用三邊測量技術(trilateration)，也稱為多邊測量技術(multilateration)。

三邊測量技術的原理十分簡單。一個未知位置的物體，通過測量到三個已知位置(參考點)的距離，可以計算出自己的位置。圖1是現有技術中三邊測量方法的示意圖，其主要展示了三邊測量的一個例子，其中，圓點代表未知位置物體，方塊代表參考點。三邊測量計算簡單、完全分布式、易于在各種平臺實現，因此廣泛應用于無線網絡定位。然而，三邊測量方法只能定位出所有可定位網絡的子集，換句話說，存在一些理論上可定位的網絡不能通過三邊測量計算節點位置。圖2是現有技術中三邊測量的局限性的示意圖，其主要描述了三邊測量的局限性。如圖所示，圖中節點1和2為未知位置節點，而節點3、4、5為已知位置節點。如果使用三邊測量方法，節點1和2都不可定位因為它們都沒有與3個已知位置節點相鄰并測距。

然而，節點1和2在理論上卻可定位，根據節點間距離限制，它們在空間中只存在唯一的位置。知道哪些節點在理論上可定位后，如何計算出它們的位置就是定位問題。可定位性與定位既有聯系也有區別。一個理論上不可定位的網絡，無論使用任何定位方法，都不能將這個網絡定位(準確的說，不能將這個網路中的所有節點定位)。另一方面，如果一個網絡可定位，那么這個網絡中的所有節點在空間中有唯一的位置，但是獲知這個位置的計算過程可能是復雜的或者不可行的。已經證明對于一般圖來說，其定位問題是NP-hard。