Self-Organizing & Network Coding in WSNs: Characteristics & Protocols
The world of Wireless Sensor Networks (WSNs) with a focus on self-organization, network coding, node characteristics, and protocols for efficient communication. Dive into the essentials of WSNs, their unique features, and how protocols facilitate self-organization for optimal performance and adaptability in changing environments."
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
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. 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 3. 4. 5. **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 B Node C wake Node A Node D Type 1 L i s t e n wake Type 2 wake Type 3 L i s t e n wake Type L i s t e n L i s t e n winner
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 signal- to-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 2 1
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
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.
