【免费】range-freelocalizationbeyondconnectivity资源-CSDN文库

需积分: 0 123 浏览量 2009-11-18 10:42:21 上传评论收藏 4.88MB PDF 举报

资源详情

资源评论

资源推荐

Achieving Range-Free Localization Beyond Connectivity

Ziguo Zhong

Department of Computer Science

University of Minnesota

zhong@cs.umn.edu

Tian He

Department of Computer Science

University of Minnesota

tianhe@cs.umn.edu

Abstract

Wireless sensor networks have been proposed for many

location-dependent applications. In such applications, the re-

quirement of low system cost prohibits many range-based meth-

ods for sensor node localization; on the other hand, range-free

localization that d e pend only on connectivity may underutilize

the proximity information embedded in ne ighborhood sensing.

In resp onse to the above limitatio ns, th is paper pr esents a novel

range-free appro ach to c apturing a relative distance between 1-

hop neighboring nodes from their neighborhood orderings that

serve as unique high-dimensional location signatures for nodes

in the network. With little additional overhead, the de sig n in

this p a per can b e conveniently applied as a transparent support-

ing layer for many state-of-the- art connectivity-based outdoor

sensor node loca liza tion solutions to achieve better positioning

accuracy than c onnectivity alone. We implemen ted our design

with three well-known localization algorithms and tested it in

two types of outdoor test-bed experiments: an 850- foot-long lin-

ear network composed of 54 MICAz motes, and a regular 2D

network covering an area of 10000 square feet with 49 motes.

System evaluation results show considerable performance gains

from the proposed design, which helps eliminate estimation am-

biguity with sub-hop resolution, and reduces localization errors

by as much as 3 5%. In addition, extensive simulations reveal an

interesting feature of robustness for our design under unevenly

distributed radio propagation path loss, and conﬁrm its effec-

tiveness for large-scale outdoor networks.

Categories and Subject Descriptor s

C.2.4 [Computer Communication Networks]: Distributed

systems

General Terms

Algorithms, Design, Performa nce, Exper imentation

Keywords

Wireless Sensor Networks, Localization, Neighborhood Or-

dering, Regulated Signature Distance (RSD)

Permission to make digital or hard copies of all or part of this work for personal or

classroom use is granted without fee provided that copies are not made or distributed

for proﬁt or commercial advantage and that copies bear this notice and the full citation

on the ﬁrst page. To copy otherwise, to republish, to post on servers or to redistribute

to lists, requires prior speciﬁc permission and/or a fee.

SenSys’09,

November 4–6, 2009, Berkeley, CA, USA.

1 Introduction

Wireless sensor networks (WSN) have been considered as a

promising tool for many location-de pendent applications [ 1, 2],

e.g., battleﬁeld surveillance [3], e nvironment data collection [4],

event or human localization [5, 6]. In addition, some of the r out-

ing protocols [7, 8] and network management mechanisms pro-

posed for such networks are built on the assumption that geo-

graphic param eters of each sensor node are available. Although

sensor node localization plays an important r ole in all such sys-

tems, it is itself a challenging problem due to extremely limited

resources available at each low-cost and tiny sensor nod e .

Many excellent ideas have been proposed for node localiza-

tion in WSN. Based on whether accura te ranging is required,

there are basically two types of methods: (i) range-based loc al-

ization and (ii) range-free localizatio n. Range-based localiza-

tion could achieve good accuracy but is costly, requiring either

per-node ranging hardware [10, 12, 14, 16, 22] or careful sys-

tem calibration and environment pro ﬁling [9, 11, 40], and thus is

not appr opriate for large-scale outdoor sensor networks. Range-

free approac hes localize nodes based on simple sensing, such

as wireless connectivity [26, 27, 29, 32, 33], anchor proxim-

ity [25, 28, 30], or localization events detec tion [36, 37]. Amo ng

these, connectivity-based solutions featu re a low overall system

cost, but by sacriﬁcing localization a ccuracy.

Our work is motivated by the ﬁnding that localization by

means of mere connectivity may underutilize the proximity in-

formation available from n e ighborhood sensing. Although ra-

dio signal strength (RSS) is no t consid ered a good choice for

physical distance estimation in many scenario s because of un-

known radio path loss factors, mu lti-path effects, hardware dis-

crepancies, antenna orientation, and so forth [40, 41, 42], it

does provide some useful distance-related information beyond

indicating connectivity among neighboring nodes. Our experi-

mental study conﬁrms th a t in outdoor open-air scenarios, the ra-

dio signal stren gth weakens approx imately monotonically with

the physical distance, especially from the v iewpoint of a sin-

gle no de, where RSS m ight provide heuristic inf ormation about

which neighboring nodes are closer and which are further.

Based on o ur empirical study, this p aper introduces a novel

range-free approach to extracting relative distance informa-

tion from neighborhood orderings which serve as unique high-

dimensional location signatures for sensor nodes in the net-

work. In stead of offering yet another new localization method,

the design described in this p aper can be conveniently ap-

plied as a transparent su pporting layer for many state-of-the-art

connectivity-based localization algorithms, provid ing a low-cost

but effective solutio n for greatly improving system accuracy.

We augmen te d three range-free localization algorithms -

MDS-MAP [26], DV-Hop [27], RPA [33], with our de sig n, and

evaluated the effectiveness of the proposed design in two types

of outdoor test-bed systems: an 850-fo ot-long linear network

with 54 MICAz motes, and a regular 2-dimensional network

covering an ar ea of 10000 square feet w ith 49 motes. System

evaluation showed noticeable performance g ains including elim-

inating estimation ambiguity and reducing localization errors b y

as much as 35%. In additio n, extensive simulation demonstrated

the effectiveness of our design for large-scale networks and re-

vealed an interesting feature of robustness to th e unkn own and

spatially unevenly distributed radio path loss.

The rest of the paper is organized as follows: Section 2 brieﬂy

surveys related work. Sec tion 3 explains the motivation behind

our work with empirical data. Th e main design is introduced in

Section 4. Section 5 briefs three range-free protocols on which

we evaluated our work. Section 6 reports outdoor test-bed exper-

iments. Section 7 summaries results from extensive simulations.

Finally, Section 8 concludes the whole paper.

2 Related Work

Based on wheth er ranging is conducted at the resource-

constrained sensor nodes, most of the previous work about

node localization can be categorized into one of following two

classes: (i) range-based [ 9, 10, 11, 14, 12, 15, 16, 17, 18, 19, 20,

21, 22, 24], and (ii) range-free localization [25, 26, 27, 28, 30,

29, 31, 32, 34, 35, 36, 3 7, 38].

Range-based solutions tr y to estimate absolute distances

or angles among randomly deployed sensor nodes and then

apply triangulation or multilateration for location calculation.

Many range -based method s use techniques such as Time of

Arrival (ToA) [13], Time Difference of Arrival (TDoA) (e.g.,

Cricket [10], AHLos [11], TPS [12]) and Ang le of Arrival

(AOA) (e.g., A PS [22], SpinLoc [18]) to measure distance or an-

gles a mong nodes and anchors (also called beacons or reference

nodes with pre-known location information). Those methods

can be accurate but costly by adding per-node additional hard-

ware [10, 12, 14], requir ing intensive tuning [17] or not suitable

for large- scale systems due to their limited effective range [ 10].

Although some research has tried to utilize RSS (Receive Sig-

nal Str ength) with noise ﬁltering for distance estimation or for

wireless ﬁngerprin t match ing (e.g., Radar [ 9], wM D S [43], Spo-

tOn [45], Indoor GPS [46], Sequence [48], Ranking [49]), em-

pirical studies [39, 40, 41] have concluded that unless careful

calibration and environment proﬁling can be accomplished, RSS

is not a good choice for accu rate ranging.

Range-free methods have applied many smart ideas for pur-

suing a low-cost design. E a rly range-free solutions made use

of the proximity inf ormation to anchor no des. Typical exam-

ples are Centroid [25], APIT [28], Concave [35] and Self [30],

in which the high cost of anchors is supposed to be amor-

tized with a large number of low-cost ordinary senor nodes.

To achieve good accuracy, however, a high anchor density is

required, which is impractica l for large-scale systems. Con-

currently, wireless connectivity-based protocols such as DV-

Hop [27], M D S-MAP [26], RPA [33], Amorphous [32] and so

on, proposed using local neighborhood sensing to build h op-

based virtual distances for large-scale sensor ne twork localiza-

tion. In those sy stems, only a small number of anchors are

necessary for constru cting the globa l coordinates, which sig-

niﬁcantly reduces the system cost. Recent work helps solve

the problems of “holes” [31, 34] and “complex shapes” [29],

contributing to connectivity-based solutions in practical irregu-

lar node deployment with obstacles. However, we found that

localization by means of connectivity alone does not make full

use of inform ation available from local neighborhood sensing.

Another important branch of range- free localization includ es

event-driven methods such as Lighthouse [36], Spotlight [37]

and etc., in which loc a lization events embedding temporal-

spatial relatio nships are generated and distributed across the net-

work area for determining nodes’ positions. Although event-

driven localiza tion p rovides tradeoffs between localization ac-

curacy and sy stem cost, generating localization events may not

be easy and convenient in some scenarios.

Instead of proposing yet another localization algorithm, this

paper presents the idea of regulated signature distance (RSD), as

a metric of the proximity among 1-hop neighboring nodes. Act-

ing as a transparent supporting layer, our design can effectively

improve the system accuracy of state-of-the-art connectivity-

based localization algor ithms with little extra cost.

3 Empirical Data as Motivation

This paper is motivated by our experim ental data showing

that in the ou tdoor environments,

• Network -wide m onotonic relationship between radio sig-

nal strength (RSS) a nd physical distance does not h old, but

• Per-node monotonic RSS-Distance relationship holds well,

i.e., any single node’s RSS sensing results fo r its neigh-

boring nodes can be used as an indic a tor for the relative

“near-far” relationship among neighbors.

In the following, we ﬁrst explain results from a prelimin ary

test, and then pr ovide data obtained from large- scale outdoor

experiments for veriﬁcation.

3.1 Preliminary Experiments

Figure 1 shows RSS sensing results from MICAz nodes in

several outdoor experiments conducted in two types of e nviron-

ment: grass land and parking lot. In the test, we placed 9 sender

nodes at different distances from a receiver node. Each sender

node broadcast 100 packets with 0dBm sending power, and the

receiver node recorded the RSS upon rece iving the packet. In

the grass-land scenario, we perform ed the test twice w ith two

different receiver nodes place d at the same location and without

moving or switchin g sender nodes (Grass Land Test1 and Grass

Land Test 2, respectively). In the parking lot scenario, id e ntical

sets of nodes were tested during day-time (Parking Lot Test 1)

and at night (Parking Lot Test 2). Tests were con ducted multiple

times, and results did not show signiﬁcant changes in the overall

shapes of the curves shown in Figure 1.

0 10 20 30 40 50 60 70 80

−90

−85

−80

−75

−70

−65

−60

−55

Distance (in feet)

RSS (in dBm)

Grass Land Test 1

Grass Land Test 2

Parking Lot Test 1

Parking Lot Test 2

Figure 1. Experimental Results: RSS vs. Distance

From Figure 1, we can see that at the system level, using

absolute values of RSS for distance estimation is not reason-

able, because identical RSS values may correspond to different

distances. However, for each individual curve (i.e. from the

0 16 32 48 64 80 96 112 128 144

−100

−80

−60

−90dBm

↓

RSS vs. Physical Distance in Linear Network

Distance Between Node Pairs (in feet)

RSS (in dBm)

0 16 32 48 64 80 96 112

−100

−80

−60

−90dBm

↓

RSS vs. Physical Distance in Regular 2D Network

Distance Between Node Pairs (in feet)

RSS (in dBm)

(a) System Level View: RSS vs. Physical Distance

0 5 10 15 20 25 30 35 40 45 50 55

0.5

RSS Ordering vs. Distance Ordering in Linear Network

node ID

Similarity

0 5 10 15 20 25 30 35 40 45 50

0.5

RSS Ordering vs. Distance Ordering in Regular 2D Network

node ID

Similarity

(b) Each Node’s Point of View: Feature of RSS Monotonic At tenuation

Figure 2. Empirical Date from Large Scale Experiments

viewpoint of each sensing node), RSS values mostly decreased

monotonically with increasing distance, conveying information

about relative “near-far” relationships among 1-hop neighbors.

3.2 Large-Scale Experiments

We then conducted large-scale outdo or experimen ts with two

types of networks to verify the phenomena found in the prelim-

inary test. The ﬁrst experiment was a linear network containing

54 MICAz nodes with a 1 6-foot intermediate distance between

adjacent nodes covering a 850-foot length along a road. In the

second experiment, we constructed a regular 2D network with a

7×7 grid-shaped layout including 49 nodes occupying an open-

air par king lot area of 10000 square feet. The setup of the large-

scale experiments will be further detailed in Section 6.

Figure 2 reports the empirical data obtained from the two

test-beds. Figure 2(a) plots the sensed RSS value for each pair

of nodes against the distance between the m, which veriﬁes that

monotonic RSS-distance relationship doesn’t hold for the whole

network. In both the line ar network and the regular 2D network,

on one hand, RSS may vary dramatically f or identical distance.

For example, as shown in the right sub-ﬁgure of Figure 2(a),

RSS r anges from -60dBm to -90d Bm for a 16-foot distance in

the 2D network. On the other han d, a single RSS value may cor-

respond to a wide range of distances. For instance, as shown in

the left sub-ﬁgure, -90dBm could range from 32 fee t to 112 feet

in the linear network; even worse, -90 dBm RSS covers almost

all of the distance spectrum, i.e. from 16 feet to 112 feet, in the

2D network showing in the right sub-ﬁgure of Fig ure 2(a).

However, examining the data from the viewpoint of a single

node te lls a different story. For any node u

, we can obtain an

ordered node list, say A, by listing u

’s 1-hop neigh bors accord-

ing to their RSS values sensed at u

in decreasing order; and

another node list, say B, by ordering u

’s 1-hop neighbors by in-

creasing physical distance. Ideally, if the sensed RSS decreases

monotonically with increasing distance, A and B should be ide n-

tical. We d eﬁne the similarity between two lists A and B as the

percentage of ac c ordant node pairs between them. For exam-

ple, let A = (u

) and B = (u

), then {u

, u

} is an

accordant node pair since in both A and B, node u

is ordered

ahead of u

; while { u

, u

} is not since their ordering gets re-

versed from A to B. We can see that if A and B are consistent

with their similarity close to 1, the monotonic feature holds.

Figure 2(b) illustrates the similarity results for all nodes in

two test-beds. We can see from the left sub-ﬁgure that in the

linear network, most of the n odes have a similarity close to

1 (the min imum, mean and maximum values of similarity are

0.86, 0.96 and 1, respec tively). It means th at in the linear net-

work, from single node’s po int of view, the RSS values for 1-hop

neighbors are approximately monotonic with the distance. This

ﬁnding still holds for the 2D regular network as shown in the

right sub-ﬁgure of Figure 2(b), wh e re the minimum, mean and

maximum similarities are 0.81 , 0.88 and 0.96, respectively.

Above experimen ts conﬁrm that (i) RSS-distance relation-

ship does not hold at the system level, but (ii) the monotonic

feature approximately holds from the viewpoint of a single node.

3.3 Analysis and Discussion

This subsection discusses why the mo notonic RSS-distance

feature could hold from the viewpoint of a single node.

In addition to the physical distance between two nodes, there

are m a ny factors that affect RSS sensing results. Table 1 lists

some major aspects. We mar ked an aspect with a “

√

” if pre-

deploy en gineering efforts could possibly be applied to reduce

its impact, or a “×” if it would be hard or c ostly to address.

Table 1. Major Factors Affecting RSS Sensing

Types of Factors P

RF Transmit Parameters: Sending Power, Frequency, Modulation, Baud Rate ...

√

Antenna Issues: Transceiver Gain, Isotropic/directioinal, Orientation, He ight .. .

√

Random Noise: Interference, Nature Events, Mobile Effects, Electronic Pulse . ..

√

Propagation Path Loss: Terrain, Vegetation, Obstac le, Magnetic Field .. . ×

Node-level Sensing Discrepancy: LNA, IF, ADC Ref. Voltage, Ground Noise ... ×

At th e sender side, besides the sending power, th e carrier

frequency, modulation, baud rate a nd etc, determine the band-

width, center frequency and spectrum shape [47], which all af-

fect the RSS at the receiver side . Most of those parameters can

be co nﬁgured with small offset errors and maintain relatively

stable during the run time. Antenna issues such as isotropic

gain, orientation and etc, can also be carefully engineered in the

design phase. For transient random noise, traditional ﬁlter ing

methods are able to help reduce its impact. All of the above are

considered addressable without signiﬁcant in-ﬁeld calibra tion.

On the contrary, unpredictable e nvironmental factors are

much harder to handle. For example, radio path loss is unknown

and costly to proﬁle in most cases because it is temporally dy-

namic and spatially unevenly distributed. Another difﬁcult is-

sue is the sensing discrepancy among nodes. At the receiver

side, RSS sensing results are sensitive to small variance among

different nodes. For examp le , a tiny bias at the reference volt-

age of ADC or small variance of the LNA (low noise ampliﬁer)

gain caused by different ground noise levels, may lead to dif-

ferent RSS values at two nodes even when their received signal

strengths are equivalent. Runtime sensing discr epancy among

剩余13页未读，继续阅读

评论收藏

内容反馈

jzkstc

粉丝: 2
资源: 8

range-free localization beyond connectivity

评论0

最新资源

range-free localization beyond connectivity

评论0

snamp.rar_localization_range-free_sensor_snamp_wireless networks

Achieving Range-free Localization Beyond Connectivity

Accurate Device-Free Localization with LittleHuman Cost

wifi 人体定位Multi-Person Localization via RF Body Reflections

Cross-platform Localization for Native Mobile Apps with Xamarin 无水印pdf

Expression and sub-cellular localization of leucine-rich repeats and immunoglobulin-like domain 1 is related to antioxidant enzymes in human ependymoma and oligodendroglioma

api-ms-win-core-localization-l1-2-0.dll

Implications of target diversity for organic device-free localization

Laravel开发-laravel-localization

Laravel开发-laravel-js-localization

The Banana Distribution is Gaussian- A Localization Study

Laravel开发-laravel-localization-automation

Fire Localization Based On Range-Range-Range Model for Limited Interior Space

Time-bounded Localization Algorithm based on

Probing many-body localization by spin noise spectroscopy.pdf

Grad-CAM：Visual Explanations from Deep Networks via Gradient-based Localization

Qt 5实现串口调试助手 （源工程文件、0积分下载）

【SystemVerilog】路科验证V2学习笔记（全600页）.pdf

AutoSAR标准协议4.2.2

光伏-储能并网系统仿真.rar

NPPJSONViewer.zip

GD32替换STM32注意事项.pdf

XCP协议的规范文档

VS2015安装证书，JavaScript_ProjectSystem.msi，JavaScript_LanguageService.msi

CANoe通过CAPL脚本实现自动测试

蓝牙BLE协议中文版.pdf

BaiduOCR.zip

AD20官方中文教程.pdf

电路分析基础第二版PDF电子书免费下载

最新资源

Qt 5实现串口调试助手（源工程文件、0积分下载）