没有合适的资源？快使用搜索试试~ 我知道了~

# GPS-free positioning in mobile ad hoc networks .pdf

5星 · 超过95%的资源 需积分: 4 70 浏览量
2008-11-30
12:55:52
上传
评论
收藏 468KB PDF 举报

温馨提示

本文讲述了传感器网络中，传感器节点在没有GPS支持的情况下，节点间自发明确各自在网络中的位置，在WSN定位方面有兴趣的朋友，可以看看，应该会有所收获的。

资源推荐

资源详情

资源评论

Preprint 0 (2001) ?{? 1

GPS-free p ositioning in mobile ad ho c networks

Srdjan

Capkun, Maher Hamdi, Jean-Pierre Hubaux

Institute for computer Communication and Applications (ICA)

Communication Systems Department (DSC)

Swiss Federal Institute of Technology Lausanne (EPFL)

CH-1015 Lausanne, Switzerland

(srdan.capkun, maher.hamdi, jean-pierre.hubaux)@ep.ch

We consider the problem of node positioning in ad hoc networks. We prop ose a distributed, infrastructure-

free positioning algorithm that does not rely on GPS (Global Positioning System). Instead, the algorithm uses

the distances between the nodes to build a relative coordinate system in which the no de positions are computed

in two dimensions. Despite the distance measurement errors and the motion of the no des, the algorithm provides

sucient location information and accuracy to support basic network functions. Examples of applications where

this algorithm can be used include Location Aided Routing 8] and Geodesic Packet Forwarding 7]. Another

example are sensor networks, where mobility is less of a problem. The main contribution of this work is to

dene and compute relative positions of the nodes in an ad ho c network without using GPS. We further explain

how the prop osed approach can be applied to wide area ad ho c networks.

Keywords:

ad ho c, mobile, distributed, wireless networks, p ersonal communication system, self-locating,

radio-location, GPS-free, self-organization.

1. Intro duction

The presented work is a part of the Termin-

ode pro ject, a 10 year ongoing pro ject that in-

vestigates large area, wireless, mobile ad ho c net-

works 1,19,20]. The main design points of the

pro ject are to eliminate any infrastructure and

to build a decentralized, self-organized and scal-

able network where no des perform all networking

functions (traditionally implemented in backbone

switches/routers and servers).

In this pap er, we describ e an algorithm for the

p ositioning of no des in an ad ho c network that do es

not use GPS. The algorithm provides a p osition

information to the nodes in the scenarios where an

infrastructure do es not exist and GPS cannot be

used. GPS-free p ositioning is also desirable, when

the GPS signal is to o weak (e.g., indoor), when it is

jammed, or when a GPS receiver has to b e avoided

for cost or integration reasons.

We intro duce a distributed algorithm that en-

ables the no des to nd their p ositions within the

network area using only their lo cal information.

The algorithm is referred to as the Self-Positioning

Algorithm (SPA). It uses range measurements b e-

tween the no des to build a Network Co ordinate

System (Fig 1.). The Time of Arrival (TOA)

metho d is used to obtain the range between two

mobile devices.

Despite the distance measurement errors and

the motion of the no des, the algorithm provides

sucient lo cation information and accuracy to sup-

p ort basic network functions. Examples of applica-

tions where this algorithm can b e used include Lo-

cation Aided Routing 8] and Geo desic Packet For-

warding 7], both in ad hoc and sensor networks.

In the Geo desic Packet Forwarding algorithm, the

source sends packets in the physical direction of the

destination no de. Given that the no de knows its

p osition and the p ositions of the destination no de

in the relative co ordinate system, it is able to com-

2

Capkun, Hamdi, Hubaux / GPS-freepositioning in mobile ad hoc networks

jj

ll

kk

ii

dd

k

l

dd

l

j

(

−

22

,

3

)

=

>

xx

yy

(

1

,

3

)

((44

,

1

)

(

−

3

,

11

))

mm

nn

aa

bb

cc

dd

(

−

1

,

1

)

(

−

2

,

−

1

)

(

0

.

5

,

−

1

.

5

))

(

−

1

,

−

2

.

5

)

(

−

3

,

−

3

)

(

3

,

−

0

.

5

)

Figure 1. The algorithm uses the distances between the

nodes and builds the relative coordinate system.

pute in which direction (to which next hop no de)

to send packets.

The no des in the ad ho c networks are usually

not aware of their geographical p ositions. As GPS

is not used in our algorithm, we provide relative

p ositions of the nodes with resp ect to the network

top ology.

For the sake of simplicity, we present the algo-

rithm in two dimensions, but it can be easily ex-

tended to provide p osition information in three di-

mensions.

The paper is organized as follows. In section

2 related work in the eld of radio-lo cation tech-

niques is describ ed. In section 3 we present the

algorithm for building a Lo cal Co ordinate System

at each no de. In section 4 we describ e the means

to dene the center and the direction of the Net-

work Co ordinate System. In section 5 we discuss

the inuence of the range errors on the accuracy of

the p osition estimation. We present the simulation

results in section 6.

2. Related work

Following the release of US FCC regulations for

lo cating E911 callers, p ositioning services in mo-

bile systems have drawn much attention recently.

The new regulations intro duce stringent demands

on the accuracy of mobile phone location. The

FCC requires that by Octob er 2001, the wireless

op erators lo cate the p osition of emergency callers

with a ro ot mean square error b elow 125m 9].

Several radio-location metho ds are prop osed for

lo cating the Mobile Stations (MSs) in cellular sys-

tems 2]: the Signal Strength method, the Angle of

Arrival (AOA) metho d, the Time of Arrival (TOA)

and Time Dierence of Arrival (TDOA) metho ds.

The Time of Arrival and Signal Strength metho ds

use range measurements from the mobile device to

several base stations to obtain its p osition. Thus,

the accuracy of the estimated p osition depends on

the accuracy of the range measurements. Distance

measurements are corrupted bytwotyp es of errors:

Non-Line of Sight (NLOS) error and measuring er-

ror. The measurements in cellular systems, taken

by Nokia 3], show that NLOS error dominates the

standard measurement noise, and tends to be the

main cause of the error in range estimation. They

also show that the lo cation estimation error lin-

early increases with the distance error. Following

these measurements, Wylie and Holtzman prop ose

a metho d for the detection and correction of NLOS

errors 5]. They show that it is p ossible to de-

tect a NLOS environment by using the standard

deviation of the measurement noise and the his-

tory of the range measurements. They prop ose a

metho d for LOS reconstruction and they showthat

the correction is only p ossible if the standard mea-

surement noise dominates the NLOS error. A dif-

ferent approach is presented in 4] by Chen. Chen

shows that if the NLOS measurements are unrec-

ognizable, it is still p ossible to correct the lo cation

estimation errors, if the numb er of range measure-

ments is greater than the minimum required. The

algorithm is referred to as the Residual Weighing

Algorithm (Rwgh).

In 6] Rose and Yates give a theoretical frame-

work of the mobility and lo cation tracking in mo-

bile systems. They present a study of mobility

tracking based on user/service/host location prob-

ability distribution.

A signicant amountofwork has b een rep orted

considering context-aware computer systems. In

these systems, mobile computers automatically

congure themselves based on what was happ en-

Capkun, Hamdi, Hubaux / GPS-freepositioning in mobile ad hoc networks

3

ing in the environment around them. Examples

of these systems include Active Badge 14] and

RADAR 15].

Recently, some p osition-based routing and packet

forwarding algorithms for the ad ho c networks have

been prop osed in 7,8,16{18]. In all these algo-

rithms it is assumed that the p ositions of the no des

are obtained through GPS.

To the b est of our knowledge, no algorithms have

b een prop osed for p ositioning of the nodes without

GPS in ad ho c networks.

3. Lo cal Co ordinate System

Wemake the following assumptions on our sys-

tem mo del:

the observed network is an infrastructure-

free network of mobile and wireless devices

all the devices (no des) have the same tech-

nical characteristics

all the wireless links between the nodes are

bidirectional

the no des use omnidirectional antennae

the maximum sp eed of the movement of

no des is limited to 20 m/s

In this section we show how every no de builds

its Lo cal Co ordinate System. The node becomes

the center of its own co ordinate system with the

p osition (0

0) and the positions of its neighbors

are computed accordingly. In section 4 we further

showhow the agreement on a common co ordinate

system (Network Co ordinate System) center and

direction is achieved.

If a node

j

can communicate directly (in one

hop) with no de

i

,

j

is called a one-hop neighbor

of

i

. Let

N

b e the set of all the no des in the net-

work.

8

i

2

N

, we dene

K

i

as the set of one-hop

neighb ors of

i

. Likewise,

8

i

2

N

, we dene

D

i

, as

a set of distances between

i

and eachnode

j

2

K

i

.

The neighbors can be detected by using b eacons.

After the absence of a certain numb er of successive

b eacons, it is concluded that the no de is no longer

a neighb or. The distances between the no des are

measured by some means, e.g. the Time of Arrival

metho d.

The following procedure is performed at every

no de

i

:

detect one-hop neighbors (

K

i

)

measure the distances to one-hop neighbors

(

D

i

)

send the

K

i

and

D

i

to all one-hop neighb ors

Thus, every no de knows its two-hop neighbors and

some of the distances b etween its one-hop and two-

hop neighb ors. A number of distances cannot be

obtained due to the p ower range limitations or the

obstacles between the no des. Fig. 2 shows no de

i

and its one-hop neighbors. Continuous lines repre-

sent the known distances between the no des, while

dashed lines represent the distances that cannot be

obtained.

By cho osing two no des

p q

2

K

i

such that the

distance b etween

p

and

q

(

d

pq

)isknown and larger

than zero and such that the no des

i p

and

q

do

not lie on the same line, no de

i

denes its Local

Co ordinate System. The latter is dened suchthat

no de

p

lies on the p ositive x axis of the coordinate

system and no de

q

has a positive

q

y

comp onent.

In this way, the Lo cal Co ordinate System of

i

is

uniquely dened as a function of

i p

and

q

.

Thus, the co ordinates of the no des

i

,

p

and

q

are:

i

x

=0

i

y

=0

p

x

=

d

ip

p

y

=0

q

x

=

d

iq

cos

q

y

=

d

iq

sin

(1)

where

is the angle

6

(

p i q

) and it is obtained by

using a cosines rule for triangles:

= arccos

d

2

iq

+

d

2

ip

;

d

2

pq

2

d

iq

d

ip

(2)

The positions of the no des

j

2

K

i

,

j

6

=

p q

, for

which the distances

d

ij

d

qj

andd

pj

are known, are

剩余14页未读，继续阅读

资源评论

- 活宝贝熊猫2012-09-20很久以前下的，东西都做完了，很有用

zh__l

- 粉丝: 0
- 资源: 2

上传资源 快速赚钱

- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助

安全验证

文档复制为VIP权益，开通VIP直接复制

信息提交成功