GPS-freepositioninginmobileadhocnetworks.pdf资源-CSDN文库

GPS-free;

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

资源推荐

资源详情

资源评论

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

sucient 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

dene 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

sucient 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-



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

(

−

)

(

)

((44

)

(

−

))

(

−

)

(

−

)

(

−

))

(

−

)

(

−

)

(

−

)

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 dene the center and the direction of the Net-

work Co ordinate System. In section 5 we discuss

the inuence 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 Dierence 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 signicant amountofwork has b een rep orted

considering context-aware computer systems. In

these systems, mobile computers automatically

congure themselves based on what was happ en-



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

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

can communicate directly (in one

hop) with no de

is called a one-hop neighbor

. Let

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

work.

, we dene

as the set of one-hop

neighb ors of

. Likewise,

, we dene

, as

a set of distances between

and eachnode

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



detect one-hop neighbors (

)



measure the distances to one-hop neighbors

(

)



send the

and

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

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

such that the

distance b etween

and

(

)isknown and larger

than zero and such that the no des

i p

and

not lie on the same line, no de

denes its Local

Co ordinate System. The latter is dened suchthat

no de

lies on the p ositive x axis of the coordinate

system and no de

has a positive

comp onent.

In this way, the Lo cal Co ordinate System of

uniquely dened as a function of

i p

and

Thus, the co ordinates of the no des

and

are:

=0



=0

cos





sin



(1)

where



is the angle

(

p i q

) and it is obtained by

using a cosines rule for triangles:



= arccos

;

(2)

The positions of the no des

p q

, for

which the distances

d

andd

are known, are

剩余14页未读，继续阅读

评论收藏

内容反馈

活宝贝熊猫

2012-09-20

很久以前下的，东西都做完了，很有用

zh__l

粉丝: 0
资源: 2

GPS-free positioning in mobile ad hoc networks .pdf

最新资源

GPS-free positioning in mobile ad hoc networks .pdf

论文研究-A vehicular ad hoc networks routing algorithm based on clustering.pdf

Service discovery in mobile ad hoc networks-a survey of issues and techniques

Performance comparison of two on-demand routing protocols for ad hoc networks.pdf

Trajectory-Based Data Forwarding for light traffic vehicular ad hoc networks.pdf

论文研究-On-demand gateway broadcast scheme for connecting mobile ad hoc networks to the Internet.pdf

Research on GPS Positioning Timing System Based on FPGA.pdf

WP-LTE-positioning.pdf

UL 1565-2022 Positioning Devices.pdf

Ultra-wideband Positioning Systems.pdf

Multi-Fault Tolerant RAIM Algorithm for Hybrid GPS-TV Positioning

AdHoc Positioning System

[eBook] Robotic - Sensors and methods for mobile robot positioning.pdf

Understanding the GPS - An Introduction to the Global Positioning System

Implementation of Indoor Positioning using IEEE802.15.4a (UWB).pdf

OSG 综合教程 PDF

TF5810-TC3-Hydraulic-Positioning-EN.pdf

恒河YOKOGAWA FA-M3 Positioning Modules with MECHATROLINK-II Interface F3NC96用户手册.pdf

Positioning.in.CSS.Layout.Enhancements.for.the.Web.149193

Ultra-wideband Positioning Systems Theoretical limits,Ranging Algorithms and Protocals

ERP系统信息化资料:SAP专业文档资料Data-Migration-Positioning-flatsteel_2.ppt

Positioning algorithm for vehicular ad hoc networks

Remote positioning system based on GPS_GPRS.pdf

u-blox8-M8_ReceiverDescrProtSpec_(UBX-13003221)_Public.pdf

ZED-F9P_ProductSummary_(UBX-17005151).pdf

解决Win 10与不兼容VirtualBox操作过程文档+（附带软件）.zip

计算机网络知识点总结(谢希仁第八版).pdf

Xshell软件(配色方案&amp;高亮关键字/突出显示集)的相关文件

湖南科技大学《计算机网络》配套课件（PDF版）

《计算机网络自顶向下方法第7版》中文PDF+复习题问题中文版答案

最新资源

Xshell软件(配色方案&高亮关键字/突出显示集)的相关文件