Transcript Addresses - Department of Computer Engineering

Architectures and Applications
for Wireless Sensor Networks
(204525)
Naming and Addressing
Chaiporn Jaikaeo
[email protected]
Department of Computer Engineering
Kasetsart University
Materials taken from lecture slides by Karl and Willig
Names vs. Addresses

Names: Refer to “things”



Addresses: Information needed to find these
things



Street address, IP address, MAC address
May or may not be globally unique
Services to map between names and addresses


Nodes, networks, data, transactions, …
May or may not be globally unique
E.g., DNS
Some names are also addresses
2
Naming in WSN

Nodes are not independent


But collaborate to solve a given task
Better to shift view from naming nodes to
naming data
3
Address Management Issues

Address allocation: Assign an entity an
address from a given pool of possible
addresses


Distributed address assignment (centralized
like DHCP does not scale)
Address deallocation: Once address no
longer used, put it back into the address
pool


Because of limited pool size
Graceful or abrupt, depending on node actions
4
Address Management Issues


Address representation
Conflict detection & resolution (Duplicate
Address Detection - DAD)



What to do when the same address is assigned
multiple times?
Can happen e.g. when two networks merge
Binding


Map between addresses used by different
protocol layers
E.g., IP addresses are bound to MAC address
by ARP
5
Uniqueness of Addresses

Globally unique


Network-wide unique


Appears at most once all over the world
Appears at most once in a given network
Locally unique

Appears at most once in a defined
neighborhood
6
Addressing Overhead



The fewer bits per address, the better
Global > Network-wide > Local
Tradeoffs


Address length  management overhead
Typically, address negotiation runs only at
the beginning

Except when there is mobility
7
Distributed Address Assignment

Option 1: Random assignment

Unacceptable high risk of duplicate addresses
No-conflict probability for n addresses and k
nodes is

By Stirlings approximation

Similar to the birthday paradox

8
Distributed Address Assignment

Option 2: Still random, but avoid addresses
used in local neighborhood


By overhearing exchanged packets
Good enough in many WSN apps where data
sent to a certain sink
9
Distributed Address Assignment

Option 3: Repair any observed conflicts





Randomly pick a temporary address and a
proposed fixed address
Send an address request to the proposed
address, using temporary address
If address reply arrives, address already exists
Collisions in temporary address unlikely, as
only used briefly
Option 4: Similar to 3, but use a neighbor
that already has a fixed address to perform
requests
10
Locally Unique Addresses

Fewer bits are needed, due to


Each address can be reused several times
across the same network
Lower-number addresses tend to be used more
frequently


Addresses can be compressed
E.g., using Huffman coding
11
Issues with Asymmetric Links

Assume nodes communicate with bidirectional
neighbors


All bidirectional neighbors of each node must have
distinct addresses
The address of any inbound neighbor must be different
from all bidirectional neighbors
12
Content-Based Addressing


Recall: Paradigm change from id-centric to
data-centric networking in WSN
Supported by content-based
names/addresses


Do not described involved nodes (not known
anyway), but the content itself the interaction
is about
Classical option: Put a naming scheme on
top of IP addresses

Done by some middleware systems
13
Describing Interests

Interests describe relevant data/event


Nodes match these interests with their locally
observed data
Format: Attribute-Value-Operation (AVO)

E.g.: <TEMP, 20°C, GE>

Operations:
14
Describing Interest/Sensor/Data


List of AVOs
E.g.,
<type,temperature,EQ>
<threshold-from-below,20,IS>
<x-coordinate,20,LE>
<x-coordinate,0,GE>
<y-coordinate,20,LE>
<y-coordinate,0,GE>
<interval,0.05,IS>
<duration,10,IS>
<class,interest,IS>
Interest
<type,temperature,IS>
<x-coordinate,10,IS>
<y-coordinate,10,IS>
Sensor
<type,temperature,IS>
<x-coordinate,10,IS>
<y-coordinate,10,IS>
<temperature,20.01,IS>
<class,data,IS>
Data
15
Matching Algorithm

Check whether an interest matches the
locally available data
16
Directed Diffusion

An example of data-centric networking
17
Geographic addressing

Express addresses by denoting physical
position of nodes



Considered a special case of content-based
addresses
Attributes for x and y (and z) coordinates
Options




Single point
Circle or sphere centered around given point
Rectangle by two corner points
Polygon
18
Conclusion



Addresses can be assigned distributedly
Non-id-centric addresses give additional
expressiveness, enables new interaction
patterns than only using standard
addresses
These addresses have to be supported by
specific protocols, in particular, routing
protocols
19