Transcript Slide 1

Self Organizing and Network
Coding in WSNs
Rennie Archibald
Contents
• Brief description of Wireless Sensor Networks
• Protocols For Self Organization of a Wireless
Sensor Network
• Network Information Flow
– Intro to Network Coding
– Network Coding for Efficient Communication in
Extreme Networks
• Conclusion
Wireless Sensor Networks
• Wireless Sensor Network (WSN) are a wireless
network made up of distinct nodes distributed
over some area and most often take readings of
their environment (e.g. temp, precipitation,
radiation, etc…)
• WSN Characteristics
–
–
–
–
Expected to scale to thousands of nodes
Changing network topology
Robust to failure
Maintenance free
Characteristics of Wireless Sensor
Nodes
• limited power, computation, and communication
capabilities.
• Interact with the physical environment
– Must be robust to their environment
• Maintenance free
• Cheap
WSN example
Courtesy of University of California, Berkeley, and
Wireless Sensor Networks Lab
Other Wireless Networks
• Mobile ad hoc networks (MANETs)
– Nodes interact with one another
– QoS oriented
– Networks of up to 100s of nodes
• Cellular Networks
– Nodes interact only with base station which has high computational
capabilities and virtually unlimited power
– Organization is limited to tower handoffs due to
• Distance
• Chipping code
• Bluetooth
– 10 m range
– Requires a Master-Slave relationship (1-7)
• HomeRF
– Short range (home)
– 802.11 standard communication
Protocols for Self-Organization of a
WSN[1]
• Wireless networking considerations specific to WSNs
– Low power nodes
– Failure of neighboring node(s)
• These issues effect the design of
– Physical layer
– Channel coding and access methods (e.g. CDMA/CA)
– What data is transmitted (raw or processed)
• Tradeoff in power consumed.
• To deal with these issues a protocol must:
– Be energy efficient
– Distributive
– Adapt to changes in topology
Protocols for Self-Organization of a
WSN
• Paper proposes a suite of algorithms to deal
with the networking aspect of WSN.
– Self-Organizing Medium Access Control for Sensor
Networks (SMACS)
• The initial self-organization portion.
– Eavesdrop-And-Register (EAR)
• For mobile agents
– Sequential Assignment Routing (SAR)
• Routing protocol
Link Layer and SMACS
• Issues to address with in Link Layer
1. Formation of a topology
2. Regulation of channel access among the nodes
• The proposed SMACS has the following
benefits
– Distributed algorithm
– Deals with both issues simultaneously, reducing
the communication between nodes
– Simple and somewhat scalable.
SMACS protocol
1.
2.
3.
4.
5.
Wake and listen for a designated amount of time
If no message is received at the end of it’s listening stage a node i
will transmit a TYPE 1 message (essentially a “HELLO” msg)
Listening nodes not already connected to nodei will respond with
a TYPE 2 message
Nodei will send out a TYPE 3 message with the id of the node j
whose response was received first, along with it’s schedule for
communication
Nodej will respond with a mutually open frequency if one exists
**Presumably if any collisions occur during this process the nodes
will sleep for a random amount of time and then restart the
process.**
SMACS example
Node A
wake
L
i
s
t
e
n
Node B
Node C
wake
L
i
s
t
e
n
winner
Node D
Type 1
Type 2
wake
Type 3
wake
L
i
s
t
e
n
Type
L
i
s
t
e
n
EAR algorithm
• The EAR algorithm seeks to allow mobile sensor
connection to the overall WSN
• Algorithm similar to SMACS:
1. Stationary node invites and listens with a Broadcast
Invite (BI) message
2. Mobile node chooses stationary node with best signalto-noise-ratio (SNR) and sends Mobile Invite (MI)
message.
3. Stationary node determines if link is possible and
responds with an Mobile Response (MR) message
detailing when to communicate
4. The mobile node cuts communication with a Mobile
Disconnect (MD) message.
SAR algorithm
• Table-driven multipath approach
– Goal is to have paths to the sink that are disjoint. Thus
robust to failure to the degree of their disjointedness (say
k)
– Assume that the bottleneck in the network will occur at
the one-hop neighbors to the sink.
• Achieved by rooting trees at each of the one-hop
neighbors of the sink and selecting which path based
on the path’s energy resources and QoS.
• Issues:
– How much computation is a node doing EVERY time it
sends a packet(s)?
a) Initial Network
–
–
–
45 nodes
100 frequencies
 = 0.04 nodes/m2
b) Initial connected graph
–
–
–
Avg degree = 2.13
31% of nodes have
multiple paths
Issue: What about final
connected graph?
c) Positions of the mobile
node and its
connections
d-f) Spanning trees
connecting the sensor
to the mobile node
Some comments/questions on the “Protocols for
Self-Organization in WSNs”
• These protocols are a security nightmare
• Continuously make the assumption of random node placement
– When would random node placement occur?
• Ocean, air dropped, …
• By taking the first message received you are giving precedence to local
connections.
– This could lead to the problem addressed by David; The existence of well
connected subgraphs that are connected by very few links.
• Claim that protocols must work on thousands of nodes but only do tests
on 45
• Also Their assumption on the number of available channels is optimistic at
best. Instead of 2600 channels 16 would be a better estimate.
• Is a “Best Effort” approach good enough for the scenarios they mentioned
WSNs could be used?
– Surveillance, environmental sampling, security, health monitoring.
Network Coding Motivation
• In a computer network a broadcast
message originates at some node
origin node v and is propagated
throughout the connected network
(assuming there is no limit on hop
count).
• Multicasting is a directed broadcast
such that the information is only sent
from the origin once but reaches only
certain nodes.
• The commercial application for
multicasting comes mainly from streaming
multimedia (such as IPTV)
Network Coding
• In a given network a max-flow min-cut algorithm
will yield the maximum amount of data that can
be transferred over the network.
• While this optimal transfer is desired it was
shown that traditional routers are not capable of
achieving it.
• Instead the concept of Network Coding is
introduced in [2].
– Instead of simply routing information nodes are
capable of processing.
Network Coding example
• This example, which uses simple linear coding, from [3] shows that
the max-flow min-cut algorithm will show that max-flow to each
sink is 2.
• However, simple routing cannot achieve the max-flow to each sink.
• The max-flow is achievable through the use of network coding
shown in the figure on the right. By using an xor it is possible to
encode the data and then recover it at each sink.
• Note that there is no unique solution to network coding.
Limitations and Issues
• Limitations
– Single source.
– This particular protocol can’t be done on the fly.
• Assumes nodes have knowledge on how to code and
decode
• Issue:
– Multisource multicasting is in general a hard
problem.
Network Coding for Efficient
Communication in Extreme Networks
• Given a delay tolerant network, such as a WSN
or some other ad-hoc network. Widmer et al
outline a routing protocol incorporating
– Distributed Network Coding [4]
– Probabilistic Routing
– Generations
– Information Aging
The Distributed Network Coding
Concept
• Additions from original work on Network Encoding
– The model used in this paper was actually proposed by Chou et
al in [4]. The original network coding algorithm required that
decoders had knowledge of the code sent to them.
– Here the encoding vector is sent with each message, thus there
is overhead in the scheme (we will see how much later)
• Messages are recovered from the decoding matrix Gv
(distinct to each node v), which has 2-tuple rows (encoding
vector, information vector)
– The matrix bounded by m(m+M)
– At the latest the message can be decoded when m original
source vectors are received.
• Only store innovative packets
– An innovative is a packet that increases the rank of the matrix
Efficient Network Coding Terminology
• y(ei) – The message received on link i
– Note that there must be h of these messages to
successfully decode the message.
• y(ei) can be broken into two parts.
1. g(ei) – the encoding vector received link i.
2. xi – The actual data, originally encoded
Network Coding Example
• For this example we look at the node t2
• Incoming links:
– y(e1) = [1 0 | b1]
– y(e3) = [1 1 | b1 + b2]
– Let b1 = b2 = 1
• Remember that b1 could be a string of bits (say 1400 in an IP
packet.
Probabilistic routing
• In order to minimize
redundant traffic Probabilistic
routing is used
• Instead of broadcasting each
packet it receives, a node
broadcasts the current packet
with a certain probability.
• This avoids the scenario
shown on the right. Where all
nodes broadcast with
probability 1.
– Clearly there are redundant
packet transmissions here.
4
3
1
2
Forwarding Factor
• Instead of simply broadcasting a packet on
reception with some probability Widmer et al
take advantage of the network coding by using
a so-called “forwarding factor” d
• When an innovative packet is received, d
vectors will be generated from the decoding
matrix and broadcast, an additional vector is
generated and broadcast with probability
d - d
Generations
• A Generation corresponds to a particular
decoding matrix Gv at node v,
– upper bound of m(m+M) on the size of the matrix
• It may be beneficial to force a smaller generation
(fewer rows) due to memory constraints.
– However to low a size decreases the efficiency of
Network Coding
• The authors chose to use a hash function over
the sender’s address and the packet identifier to
determine the generation
Gain Generation Size
• The graph to the left
shows that there is an
increase in efficiency as
generation sizes grow.
• What must be
balanced is the
overhead incurred by
larger generation sizes.
An example of the
increasing overhead is
shown in the table.
Information Aging
• Due to limited memory capacity on nodes
information aging is employed to decrease the
size of a generation
• This process occurs after a node v has a
complete decoding matrix Gv
• As space is needed two rows can be linearly
combined. Thus information that is feasibly
innovative to a nodes neighbors is not lost.
Dense Network Simulations
• On the left we see the performance for network coding on a static
network.
– Network Coding allows for 100% PDR with a forwarding factor of d =
0.25
– Probabilistic routing requires nearly triple the amount of forwarding to
reach 100% PDR.
• The graph on the right gives the results of a network in which
mobility is present.
Information on the Neighborhood
• The proceeding tests on sparse networks were
done with additional variable, the amount of
knowledge a node has about it’s neighbors
– Without beacons: No information on neighbors
– Normal beacons: Only send a packet if neighbors
exist
– Intelligent beacons: announce the presence of a
neighbor and all information currently in Gv
• Prevents redundant information transfer  less
overhead
Performance in Sparser Networks
Questions on usefulness of WSNs
• Once the battery is drained what happens?
– Just leave a toxic item lying in a field? If not how do you collect
them?
• Questionable usage in an agricultural environment where the sensor
may become difficult to find but must be removed to avoid destroying
crops.
• What kind of QoS can we gurauntee?
– Attacks this Network Coding algorithm allows
• Replay
• Blackhole
• Homing
• Attacker has physical access
– An attack such as the one George discussed on Tuesday would
succeed.
Network Coding
• [1] K. Sohrobi et al., "Protocols for Self-Orgonizotion of o
Wireless Sensor Network,'' IEEE Personal Communication.
vol. 7, no. 5, Oct. 2000, pp. 16-27.
• [2] R. Ahlswede, N. Cai, S. R. Li, and R. W. Yeung. Network
Information flow. IEEE Transactions on Information Theory,
July 2000.
• [3] P.A. Chou, Y. Wu, and K. Jain, “Practical Network
Coding,” Proc. 51st Ann. Allerton Conf. Comm., Control, and
Computing, Oct. 2003.
• [4] Widmer, J. and Le Boudec, J. “Network coding for
efficient communication in extreme networks” In Proc of
the 2005 ACM SIGCOMM Workshop on Delay-Tolerant
Networking August, 2005.