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

文库首页移动开发其它无线传感器网络算法Roger Wattenhofer

无线传感器网络算法Roger Wattenhofer

无线传感器网络

5星 · 超过95%的资源需积分: 9 11 下载量 72 浏览量 2011-12-01 09:12:18 上传评论收藏 5.62MB PDF 举报

温馨提示

试读

72页

是大牛Roger Wattenhofer在EWSN上的一个报告的PPT，内容很多包含路由算法，定位算法，拓扑控制。强烈推荐。内容有287页，涵盖了很多内容，当做综述来看看很不错。

资源推荐

资源详情

资源评论

Roger Wattenhofer

EWSN 2006 Tutorial ETH Zurich Switzerland

ALGORITHMS

for Wireless Sensor Networks

Chapter 0

INTRODUCTION

EWSN 2006

Distributed

Computing

Group

Roger Wattenhofer, EWSN 2006 Tutorial 0/3

Introductory comments

• Way too many slides...

– But don’t worry, we won’t do all of them

• Heterogeneous audience

– Some students, some industry folks, some famous professors, …

– I assume everybody knows 101 of sensor networking

– Instead of a real introduction, I will show some “opinion” slides

• This tutorial has a quite narrow definition of the term “algorithm”

• An algorithm is an algorithm only if it features an analytical

proof of efficiency.

• If performance is proved by simulation only, we call it a heuristic.

• We look a distributed algorithms mostly.

Roger Wattenhofer, EWSN 2006 Tutorial 0/4

My Own Private View on Networking Research

5%Worst-case

unusual

Any (worst-

case)

UDG, and

Theorem/

proof

Algorithm

10%

Existential

(no protocols)

RandomSINR,

and more

Theorem/

proof

Scaling

law

80%

Many…! (no

benchmarks)

Random,

and more

UDG to

SINR

SimulationHeuristic

“Too specific”Reality(?)RealityTestbedImple-

mentation

Popu

larity

Other

drawbacks

Node

distribution

Communi

cation

model

AnalysisClass

Roger Wattenhofer, EWSN 2006 Tutorial 0/5

Algorithm Classes

Global Algorithm

Distributed Algorithm

Local Localized

• For some problems we don’t even

understand the non-distributed case

•“ReiceivemsgX  Transmit msg Y”

•Everyalgo can be made distributed

+ Node can only

communicate with

neighbors k times.

+Strict time bounds

– Often synchronous

Unstructured

+Often simple

– Nodes can wait for

neighbor actions

– Often linear chain

of causality

+ Implement MAC

layer yourself; you

control everything

– Often complicated

– Argumentation

overhead

Roger Wattenhofer, EWSN 2006 Tutorial 0/6

Some algorithmic communication models

• Some of them we will see in this lecture, most of them not…

Roger Wattenhofer, EWSN 2006 Tutorial 0/7

What has been studied?

Link Layer

Network Layer

Services

Theory/Models

• MAC Layer and Coloring

• Topology and Power Control

• Interference and Signal-to-Noise-Ratio

• Clustering (Dominating Sets, etc.)

• Deployment (Unstructured Radio Networks)

• New Routing Paradigms (e.g. Link Reversal)

• Geo-Routing

• Broadcast and Multicast

• Data Gathering

• Location Services and Positioning

• Time Synchronization

• Models and Mobility

• Lower Bounds for Message Passing

• Selfish Agents, Economic Aspects, (Security)

Roger Wattenhofer, EWSN 2006 Tutorial 0/8

What has received most attention?

• MAC Layer and Coloring

• Topology and Power Control

• Interference and Signal-to-Noise-Ratio

• Clustering (Dominating Sets, etc.)

• Deployment (Unstructured Radio Networks)

• New Routing Paradigms (e.g. Link Reversal)

• Geo-Routing

• Broadcast and Multicast (“energy-efficient BC”)

• Data Gathering

• Location Services and Positioning

• Time Synchronization

• Models and Mobility

• Lower Bounds for Message Passing

• Selfish Agents, Economic Aspects, Security

What is really

important?!?

(Opinion…)

Roger Wattenhofer, EWSN 2006 Tutorial 0/9

Philosophy

• Understand algorithmic fundamentals of sensor networks.

– See some algorithms with implementation appeal

• Find models that capture reality

– No random distribution

– No random mobility

• Show a few examples

– Mix between well-studied and “important” topics

• More material

– Reading list on www.dcg.ethz.ch

Roger Wattenhofer, EWSN 2006 Tutorial

Chapter 1

GEOMETRIC ROUTING

EWSN 2006

Distributed

Computing

Group

Roger Wattenhofer, EWSN 2006 Tutorial 0/11

• Geometric routing

• Greedy geometric routing

• Euclidean and planar graphs

• Unit disk graph

• Gabriel graph and other planar graphs

• Face Routing

• Greedy and Face Routing

• Geometric Routing without Geometry

Overview – Geometric Routing

Roger Wattenhofer, EWSN 2006 Tutorial 0/12

Geometric (geographic, directional, position-based) routing

• …even with all the tricks there will be flooding every now and then.

• In this chapter we will assume that the nodes are location aware

(they have GPS, Galileo, or an ad-hoc way to figure out their

coordinates), and that we know where the destination is.

• Then we

simply route

towards the

destination

Roger Wattenhofer, EWSN 2006 Tutorial 0/13

Geometric routing

• Problem: What if there is no path in the right direction?

• We need a guaranteed way to reach a destination even in the case

when there is no directional path…

• Hack: as in flooding

nodes keep track

of the messages

they have already

seen, and then they

backtrack* from there

*backtracking? Does this

mean that we need a stack?!?

Roger Wattenhofer, EWSN 2006 Tutorial 0/14

Alice

Bob

Geo-Routing: Strictly Local

???

Roger Wattenhofer, EWSN 2006 Tutorial 0/15

Greedy Geo-Routing?

Alice

Bob

Roger Wattenhofer, EWSN 2006 Tutorial 0/16

Greedy Geo-Routing?

Carol

Bob

Roger Wattenhofer, EWSN 2006 Tutorial 0/17

What is Geographic Routing?

• A.k.a. geometric, location-based, position-based, etc.

• Each node knows its own position and position of neighbors

• Source knows the position of the destination

• No routing tables stored in nodes!

• Geographic routing makes sense

– Own position: GPS/Galileo, local positioning algorithms

– Destination: Geocasting, location services, source routing++

– Learn about ad-hoc routing in general

Roger Wattenhofer, EWSN 2006 Tutorial 0/18

Greedy routing

• Greedy routing

looks promising.

• Maybe there is a

way to choose the

next neighbor

and a particular

graph where we

always reach the

destination?

Roger Wattenhofer, EWSN 2006 Tutorial 0/19

Examples why greedy algorithms fail

• We greedily route to the neighbor

which is closest to the destination:

But both neighbors of x are

not closer to destination D

• Also the best angle approach

might fail, even in a triangulation:

if, in the example on the right,

you always follow the edge with

the narrowest angle to destination

t, you will forward on a loop

, w

, v

, w

, …, v

, w

, v

, …

Roger Wattenhofer, EWSN 2006 Tutorial 0/20

Euclidean and Planar Graphs

• Euclidean: Points in the plane, with coordinates

• Planar: can be drawn without “edge crossings” in a plane

• Euclidean planar graphs (planar embeddings) simplify geometric

routing.

剩余71页未读，继续阅读

评论收藏

内容反馈

资源评论

资源反馈

评论星级较低，若资源使用遇到问题可联系上传者，3个工作日内问题未解决可申请退款~

yuerkaixin

2012-09-11

挺有用的，启蒙+入门，谢谢提供

kkmmnn

粉丝: 7
资源: 7

上传资源快速赚钱

我的内容管理展开

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

前往需求广场，查看用户热搜

无线传感器网络算法Roger Wattenhofer

无线传感器网络算法代码

无线传感器网络定位算法代码大全.rar

无线传感器网络所有定位算法matlab仿真代码+包含各个算法的论文

无线传感器网络节点定位算法

基于粒子群优化算法的无线传感器网络节能覆盖研究_张娟

无线传感器网络LEACH算法的MATLAB代码

基于RSSI的无线传感器网络定位算法研究

无线传感器网络中的同步算法及能耗研究（博士）

无线传感器网络分簇算法

无线传感器网络经典LEACH算法MATLAB程序

无线传感器网络_路由_无线传感器_网络路由算法_

无线传感器网络中覆盖控制理论与算法

无线传感器定位算法代码

论文研究-无线传感器网络中ERARP拓扑控制算法.pdf

无线传感器网络定位算法matlab代码

无线传感器网络所有定位算法matlab仿真代码

分布式布谷鸟算法在无线传感器网络布局优化中的应用

vdhcoapp-windows-x86-64-installer 2.0.19

大麦抢票+源代码+辅助工具+详细文档教程

嵌入式，PL2303-win11驱动程序

aurora-v3.0.4s-release.exe

labview入门开发100实例及对应部分vi

Unityhub 国际版 Windows版本 下载时间：2022年9月9日 10:35

CANdb++Admin完整安装包

MC大龙老师新版scratch3.0编程素材（第四版）

蓝桥杯第十四届省赛真题源码

INFI75 Driver V2.exe

Arduino+CH340模块驱动+esp8266开发板（3.0.2）

最新资源

Unityhub 国际版 Windows版本下载时间：2022年9月9日 10:35