技術(shù)領(lǐng)域

本發(fā)明涉及無(wú)線(xiàn)網(wǎng)技術(shù)領(lǐng)域，特別是一種計(jì)算未知節(jié)點(diǎn)的可能位置區(qū)域的切分定位方法。

背景技術(shù)

無(wú)線(xiàn)網(wǎng)和傳感網(wǎng)在機(jī)場(chǎng)中的應(yīng)用非常普遍，這些應(yīng)用對(duì)位置信息的依賴(lài)也越來(lái)越嚴(yán)重，因此依托于這類(lèi)網(wǎng)絡(luò)的定位方法一直很受重視。目前，一般把無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)定位算法分為兩類(lèi)：一類(lèi)是基于測(cè)量距離(range-based）的定位方法；另一種是非測(cè)距（range-free）的定位方法。基于測(cè)距的定位方法雖然定位精度高，但一般需要專(zhuān)門(mén)的硬件來(lái)實(shí)現(xiàn)對(duì)節(jié)點(diǎn)間的距離或角度的測(cè)量，成本較高；而非測(cè)距定位方法雖然定位精度有限，但由于不需要額外的硬件支撐，因此成本較低。由于不同的應(yīng)用對(duì)定位精度有不同的要求，非測(cè)距定位算法能夠滿(mǎn)足很多應(yīng)用系統(tǒng)對(duì)定位精度的要求，且其成本最低，因此這類(lèi)算法越來(lái)越受到青睞。然而，現(xiàn)有非測(cè)距定位算法的定位精度都很有限，比如：Bounding-Box、DV-HOP、APIT、SOM等等，它們的定位精度都不高，這限制了這些方法在實(shí)際系統(tǒng)中的應(yīng)用。

在2002年由Simic?提出的Bounding-Box算法?(Simic?S.,?and?Sastry?S.:?‘Distributed?localization?in?wireless?ad?hoc?networks’,?UC?Berkeley,?Tech.?Rep.,?UCB/ERL?M02/26,?2002)屬于非測(cè)距算法，通過(guò)求未知節(jié)點(diǎn)的直接錨點(diǎn)鄰居的輻射范圍的交集實(shí)現(xiàn)了對(duì)未知節(jié)點(diǎn)的定位。它首先將未知節(jié)點(diǎn)的直接錨點(diǎn)鄰居的輻射范圍簡(jiǎn)化為一個(gè)正方形，然后求出未知節(jié)點(diǎn)的所有直接錨點(diǎn)鄰居的正方形輻射范圍的重疊區(qū)域，并將重疊區(qū)域的中心作為未知節(jié)點(diǎn)的位置。Bounding-Box算法只利用了未知節(jié)點(diǎn)的一跳錨點(diǎn)鄰居，其定位精度和定位覆蓋率都不高，且Bounding-Box計(jì)算其未知節(jié)點(diǎn)可能位置區(qū)域的簡(jiǎn)化方法使其定位精度與理論精度有較大偏差。

DV-hop算法是Niculescu于2003年提出的非測(cè)距定位算法（Niculescu?D.?and?Nath?B.:?‘DV?based?positioning?in?ad?hoc?networks’?Telecommun.?Syst.,?2003,?22,?(1-4),?pp.?267-280）。該算法由3個(gè)階段組成：首先，通過(guò)鄰居發(fā)現(xiàn)算法讓每個(gè)錨節(jié)點(diǎn)獲得除自己以外的其他每一個(gè)錨節(jié)點(diǎn)距離自己的跳數(shù)，并讓每個(gè)未知節(jié)點(diǎn)獲得每一個(gè)錨節(jié)點(diǎn)距離自己的跳數(shù)；其次，每個(gè)錨節(jié)點(diǎn)分別計(jì)算除自己以外的其他每一個(gè)錨節(jié)點(diǎn)到自己的平均每跳距離，并將該信息發(fā)送給它周邊的未知節(jié)點(diǎn)，未知節(jié)點(diǎn)則以距離自己的跳數(shù)最少且最先收到消息的錨點(diǎn)計(jì)算所得的平均每跳距離作為各錨點(diǎn)到自己的平均每跳距離，并乘以相應(yīng)的跳數(shù)得到各錨點(diǎn)距離自己的估計(jì)距離；最后使用三邊測(cè)量法確定節(jié)點(diǎn)的位置。該方法的定位覆蓋率得到了較大提高，但該方法所達(dá)到的定位精度也不高，應(yīng)用范圍有限。

APIT算法是Tian在2003年提出的非測(cè)距定位算法，并于2005年發(fā)表在ACM?Trans.Embed.?Comput.?Syst上（He?T.,?Huang?C.,?Blum?B.M.,?Stankovic,?J.A.,?and?Abdelzaher,?T.F.:?‘Rangefree?localization?and?its?impact?on?large?scale?sensor?networks’,?ACM?Trans.Embed.?Comput.?Syst.,?2005,?4,?(4),?pp.?877-906.）。該算法首先收集未知節(jié)點(diǎn)所有鄰居錨節(jié)點(diǎn)的信息，然后測(cè)試未知節(jié)點(diǎn)是否位于不同的三個(gè)錨節(jié)點(diǎn)組成的三角形內(nèi)，計(jì)算所有包含該未知節(jié)點(diǎn)的三角形的重疊區(qū)域，最后用該區(qū)域的質(zhì)心作為未知節(jié)點(diǎn)的坐標(biāo)。該方法獲得了較高的精度，但是其定位覆蓋率有限。尤其對(duì)于那些不在任何由三個(gè)錨點(diǎn)組成的三角形內(nèi)的未知節(jié)點(diǎn)，該方法無(wú)法定位。APIT將定位區(qū)域分成很多小網(wǎng)格，并對(duì)網(wǎng)格進(jìn)行編號(hào)，通過(guò)獲得出現(xiàn)在所有包含未知節(jié)點(diǎn)的三角形區(qū)域的網(wǎng)格編號(hào)而得到重疊區(qū)域，該方法需要全網(wǎng)絡(luò)標(biāo)號(hào)，計(jì)算過(guò)程繁瑣。