Distributed Computing in Sensor Networks
The fundamentals of wireless ad-hoc networks and sensor networks, examining the challenges and autonomous nature of these systems. Discover how nodes communicate, self-manage, and form dynamic topologies, enabling applications in various fields. Delve into the cross-layered design of sensor networks and the autonomous operation of distributed systems, paving the way for efficient networking solutions.
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
Lecture Note 10 Application I Distributed Computing on Sensor Networks
Cross-Layered Design of Sensor Networks I. Fundamentals - Basics of Wireless Ad-Hoc Networks - Autonomous Systems - Communication Models and Algorithms II. Design of Wireless Sensor Networks - Reconfigurable Networking Architecture - Routing Protocol and Communication Algorithms - Network Self-Reconfiguration Algorithms - Sensor Network Deployment
I. Fundamentals What is A Wireless Ad-Hoc Network (AD-NET)? An AD-NET is a self-managing/autonomous system of cooperating mobile and/or stationary nodes connected by unreliable wireless links. Each node operates not only as an end-system, but also as a router to process and forward application data. Usually, the nodes are inexpensive and have limited computation and communication capability. They can be used to cover a large terrain and has great potential in civic and military applications. A Wireless Ad-Hoc Network Due to severe energy, environmental, timing constraints and dynamic topological changes, design a wireless AD-NET is a big challenge.
Basics of A Wireless Ad-Hoc Network There is no fixed communication infrastructures. Tasks are self-organized without central control Autonomous tracking in Sensor Network f /c Network is dense: control and communication overlap Control and communication patterns are specific: one-to-many, many-to-one Network topology is dynamic: topology self-reconfiguration is necessary Autonomous failure detecting & power re- assigning in Power supply network
How Can Distributed Systems Work Autonomously? (What are centralized/decentralized systems?) Example 50 kids are playing in a ground. How can they form a circle when their teacher asks them to do? Condition 1: Each kid can see all other kids. Condition 2: Each kid can see some kids. Questions: In which case, will a circle be formed faster? Observations: More global information a node has, the easier the work will be done. It is expensive to get global information form dynamic distributed systems
Communication on Wireless AD-NETs Network Model Directed Graph G=(V,E) V={nodes} E={edge (u,v): if node u can transmit data to node v} Nodes with different communication range
Communication on Wireless AD-NETs Continue Example of communication tasks : Broadcast Algorithm 1: Broadcast by flooding Each node v: if v received the message then transmit the message Source How to solve collision problem? -- using randomized algorithm: generate a random number k, transmit data at kth time slot. It may need long time in a dense network !!!
Algorithm 2: Broadcasting using Euclidean Circle Asynchronous algorithm Each node v: if v received the message (u, x, d) then if x is not v, then ignore the message. Otherwise, select a neighbor w whom v hasn t sent the message to yet and transmit the message (v,w,d). If v has sent the message to all its neighbor, v sent the message (v, parent, d) Forming a spanning tree T (Each node keeps a neighbor list in T) Transmitting data in depth-first style v (Sender, receiver, data) Source u Observations: It is a Deterministic algorithm: only one node transmits in one time slot. It is an asynchronous algorithm Communication complexity: Totally 2(n-1) time slots with n nodes It is expensive in a large scale of network!!!
Communication on Wireless AD-NETs Continue Another example - How to get a neighbor list(suppose there is a global clock at each node) ? Algorithm: Building neighbor list by using Round Robin 6 Each node v: Node v transmits its id at the time slot same as its id s. 4 5 1 2 9 8 3 7 Observations: Each node can have a neighbor list after n time-slot. Synchronization is needed. Questions: 1. How to get a neighbor list if the Ids of nodes are not numbered contiguously? 2. Counting problem: How to number n nodes from 1 to n? 3. Leader selection problem: how to select a leader?
II. Design of Wireless Sensor Networks (WSNs) Basics of AD-Net Design Issues in WSNs Medium Access Control (MAC) Routing Multi-casting Network Self-organization Security Energy Management Query/Addressing Scalability Deployment Methods Quality of Service Task Management Mobility Management Application Layer Power Management Transport Layer Cross-layer control Network Layer Data Link Layer Physical Layer Sensor Node Protocol Stack
Overall Networking Process Application Layer Application Layer Application Protocol Presentation Layer Correlation-based Communication Layer Session Layer Transport Layer (end-to-end transfer of message) Transport Protocol Network Layer (Transfer of packets across network) Data Link Layer (Transfer of blocks across a link) Physical Layer Physical Layer Wireless Ad-Hoc Model ISO/OSI Reference Model
Embed Network into Nodes protocol protocol driven driven Application (Configurable Service) Layer Application (Configurable Service) Layer Task Task Network Management and Cross-Layer Control Network Management and Cross-Layer Control Network Layer Network Layer Power management Power management Node move-in/out detection Node move-in/out detection Network Management Tasks Architecture/rout ing protocol reconfiguration reconfiguration Network Management Tasks Architecture/rout ing protocol Networking (Application) Functions Networking (Application) Functions Topology-based or attribute-based subnet Topology-based or attribute-based subnet communication communication Data Data collection collection Data Data Dissemination Dissemination Data Data Aggregation Aggregation Node physical condition detection Node physical condition detection Routing Operations Routing Operations Query-based routing routing routing Query-based Query-based multipath-based multipath-based multipath-based routing routing routing QoS-based routing routing routing QoS-based QoS-based synchronization synchronization Addressing Protocols Addressing Protocols Attribute-based protocol protocol protocol Attribute-based Attribute-based Topology-based protocol protocol protocol Topology-based Topology-based Global addressing protocol protocol protocol Global addressing Global addressing Network status detection Network status detection Link Abstraction Layer Routing table (Adaptive hierarchical structure) Cluster Head: Neighbors: *Parents: Link Abstraction Layer Routing table (Adaptive hierarchical structure) Routing table Routing table (Flat Structure) (Flat Structure) Send Send Receive Receive Backbone Backbone Neighbors: *Parents: *Children: *Children: Neighbor: Neighbor: Cluster Head: Member: Member: Message pool Message pool Localization Localization Multiple Link (MAC) and Physical Layer Multiple Link (MAC) and Physical Layer
Correlation-based Communication Layer Fusion-Oriented Application Layer Communication Tasks Broadcasting System Maintenance Tasks Global Synchronization Network Reconfiguration Multicasting Hierarchical Communication/Routing Protocols Highest Level Lowest Level Structured (Hierarchical)Communication Network Static/Dynamic Grained-Clustering Physical Layer (Flat Communication Network)
Architecture of Sensor Nodes RF Transceiver Power tracking unit Communication System Power System Data path Micro controller Sensor array Control and computing System System timers Sensor System Data memory Tradeoffs between power consumption, bandwidth, and latency Interrelationship between transmission rates, processor speed and power consumption. Interface between an application and its communication protocols
Types of Nodes in Sensor Networks (1) Homogeneous Sensor Network Uniform sensor nodes & sink nodes No base station (2) Heterogeneous Sensor Network Sensing nodes, processing nodes, mobile nodes, sink nodes Mixed with base station Wireless Stands IEEE 802.11 (Wi-Fi): Mainly used for the access between wireless devices and base stations. Possible for the access between wireless devices. IEEE 802.15 (based on Bluetooth): Used forAd-hoc network without base station.
Comparison between standards Frequency (unlicensed) standard Data rate MAC Protocol 802.11b 2.3-2.485 GHz Up to 11 Mbps Random access CSMA/CA 802.11a 5.1-5.8 GHz Up to 54 Mbps Same as above 802.11g 802.15(based on Bluetooth) 2.4-2.485 GHz 2.4 GHz Up to 54 Mbps Same as above Up to 1 Mbps TDM CSMA/CA CAMA/CA: carrier sense multiple access with collision avoidance TDM: time division multiplexing 802.11(a,g) 802.11b 802.15 54 Mbps 5-11 Mbps 1 Mbps UMTS/WCDMA,CDMA2000 IS-95 CDMA, GSM 384 Kbps 56 Kbps Indoor 10-30 m Outdoor 50-200 m Mid range 200m-4km Long range 5Km-20Km
Communication Unit Application control MAC (Media access control ) protocol Protocol processing Synchronizer Channel coding RF transceiver Transmission power control
802.15.4 The physical layer (PHY) PHY manages the physical RF transceiver and performs channel selection and energy and signal management functions. It operates on one of three possible unlicensed frequency bands: 868.0-868.6 MHz: Europe, allows one communication channel (2003, 2006) 902-928 MHz: North America, up to ten channels (2003), extended to thirty (2006) 2400-2483.5 MHz: worldwide use, up to sixteen channels (2003, 2006) http://upload.wikimedia.org/wikipedia/commons/thumb/b/b5/IEEE_802.15.4_protocol_stack.svg/260px-IEEE_802.15.4_protocol_stack.svg.png The medium access control (MAC) enables the transmission of MAC frames through the use of the physical channel. Besides the data service, it offers a management interface and itself manages access to the physical channel and network beaconing. It also controls frame validation, guarantees time slots and handles node associations. Finally, it offers hook points for secure services.
Networking Architecture/Topology Flat architecture Completely decentralized Large communication overlap Difficult to select local control and data aggregation point Almost impossible to organize a real-time application Easy (Cheap) for topology management Cluster-based (Hierarchical) architecture Centralized control in local and decentralized control in global Easy for schedule a routing without or with less overlap Easy to select local control and data aggregation point Expensive for topology management
Design of Networking Architecture Flat and Structured AD-Nets Flat (unstructured) Network Cluster-based (structured) Network MAC takes care collision problem but needs time and energy! e.g., Broadcast storm problem
Flat and Structured Sensor Network: An Example Local way (cluster) Highway (Back bone) Sink Primary sensor node Communicable sensor node
Trade-offs in Network Architecture -Balance between communication and network self-organization Flat (unstructured) Network Architecture Complete decentralized control Cluster-Based Network Architecture Combining the centralized control in local with the decentralized control in global head cluster Observations: Control architecture and communication protocols should support both (time and energy) efficient autonomous distributed control and communication and easy network self- organization. So far, control/communication and network reconfiguration are considered separately !
Comprehensively Design AD-Nets (1) Clustering architecture which support the functionalities for both of communication and network self-organization. (2) Design efficient algorithms for network self-organization (3) Design efficient algorithms for key control and communication functions
Architecture Self-Clustering/ Reconfiguration head Self-Clustering cluster backbone gateway cluster When self-clustering finished, each node has 1-hop information: (1) In a cluster, head knows members ids, and members know head s id. (2) In backbone, each backbone node knows its neighbors in the backbone. (3) Each node knows its neighbors ids.
Self-reconfiguration Nodes may get out of or turn back to the network because of running out of battery or being recharged. (1) Node move-in Want to join
(2) Node move-Out Backbone is re-built !!! Want to move out Backbone is broken!!!
Routing Protocols and Communication Algorithms (1) Broadcasting (i) Broadcast via depth-first-search of backbone (Asynchronized) Euclid circuit traveling s
(ii) Broadcast via collision-free flooding (Synchronized) (power saving and robust) cluster head gateway node cluster pure cluster member Using time division scheme to avoid collision (synchronized) 2 1 1 depth i depth i+1 v
cluster head (2)Multicast gateway node cluster pure cluster member Outline of Algorithm (Asynchronized)_ Self-building group-backbone tree for each group One to many: broadcasting on group-backbone tree
Summary (Assuming the size of one packet is 280 bytes and transmitting speed is 1 MB/second) Algorithm Time (rounds) Time (second) Energy needed at each node (rounds) O(d) Self-clustering O(n) O(0. 07186n) Self-reconfiguration (get-in) Self-reconfiguration (get-out) O(d) O(0.07168d) O(d) O(d), O(0.07168d), O(0.07168|T|) get-out node is in the backbone O(d), O(|T|) get-out node in the backbone 2 |C| O(|T|) get- out node is in the backbone Broadcasting (Depth-first) 2 |C| 0. 14336|C| Broadcasting (collision-free flooding) 1 D2 03584 . 0 h D2 h 2 D 2 1 Multicast 2 2h D 03584 . 0 ' D 2h ' D 2 Data Collection (unit graph) O(D+h) O(0.07186Dh) Number of the descendants in the cluster- based network Notations n: number of nodes; d: number of neighbors, |T|: size of the backbone tree T; |C|: the number of clusters; h: height of the backbone tree; h : height of the multicast backbone tree g; D: maximum degree in the network
Crossbow Sensor Network Deployment for Research Integration Sensor board + wireless module Research Focus A network of Crossbow mote that can detect and track vehicles fast enough so that the base station can activate the camera systems before the vehicles close to the building.
Technical Approach Sensing and Networking Sensor Selection Acceleration Sensor Doesn t work Magnet sensor range 11m Acoustic sensor range 8.89 m to 17.78 m sensitive to vehicle speed and background noise 570 520 470 420 370 320 270 10:54 10:55 10:56 10:57 10:58 10:59 11:00 11:01 11:02 11:03 11:04 10:54 10:55 10:56 10:57 10:58 10:59 11:00 11:01 11:02 11:03 11:04 Time (sec)
Technical Approach Sensing and Networking Sensor Deployment DEPLOYMENT 1 Cost optimal for vehicle detection by using poles 4 sensor boards 10 wireless modules longest path = 7 distance between poles = 45 50 m Transmission range = 43m Sensing range = 11m Gateway
Technical Approach Sensing and Networking Sensor Deployment DEPLOYMENT 2 Cost optimal for vehicle detection without poles 4 sensor boards 20 wireless modules longest path = 13 Transmission Rage = 43m Sensing range = 11m If latency < 1 second, listening > 12 times/s Network lifetime = wireless mote lifetime = 99 hours < 5days even no one vehicle passing through! Gateway
Technical Approach Sensing and Networking Sensor Deployment DEPLOYMENT 3 Cost optimal for vehicle tracking 25 sensor boards 25 wireless modules longest path = 9 Transmission Rage = 43m Sensing range = 11m gateway
Technical Approach Sensing and Networking Sensor Deployment DEPLOYMENT 4 Longer network lifetime with redundancy 2 cluste r cluste r < 18.5m 22m 24 sensor boards 32 wireless modules gateway
Technical Approach Sensing and Networking Sensor Deployment DEPLOYMENT 5 Longer network lifetime with redundancy 4 cluste r cluste r gateway
Exercises: 1. What are wireless ad-hoc/mobile/sensor networks? 2. What are the challenge for the networks of low cost and small-sized sensor nodes? 3. Explain the tradeoff of centralized system and decentralized system 4. How to get a neighbor list if the Ids of nodes are not numbered contiguously? 5. Counting problem: How to number n nodes from 1 to n? 6. Leader selection problem: how to select a leader?
