1 Lecture Note 10 Application I – Distributed Computing on Sensor Networks

2 Cross-Layered Design of Sensor NetworksI. 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

3 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. Due to severe energy, environmental, timing constraints and dynamic topological changes, design a wireless AD-NET is a big challenge. A Wireless Ad-Hoc Network

4 Basics of A Wireless Ad-Hoc NetworkAutonomous tracking in Sensor Network Basics of A Wireless Ad-Hoc Network There is no fixed communication infrastructures. Tasks are self-organized without central control 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 f /c

5 An Example of Wireless Sensor Network

6 How Can Distributed Systems Work AutonomouslyHow 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

7 Communication on Wireless AD-NETsNetwork 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

8 Communication on Wireless AD-NETs – ContinueExample 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 !!!

9 Algorithm 2: Broadcasting using Euclidean CircleAsynchronous 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!!!

10 Communication on Wireless AD-NETs – ContinueAnother example - How to get a neighbor list (suppose there is a global clock at each node) ? Algorithm: Building neighbor list by using Round Robin Each node v: Node v transmits its id at the time slot same as its id’s. 9 4 3 5 8 2 6 1 7 Observations: Each node can have a neighbor list after n time-slot. Synchronization is needed. Questions: How to get a neighbor list if the Ids of nodes are not numbered contiguously? Counting problem: How to number n nodes from 1 to n? Leader selection problem: how to select a leader?

11 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 Physical Layer Data Link Network Transport Application Power Management Mobility Management Task Management Cross-layer control Sensor Node Protocol Stack

12 Overall Networking ProcessApplication Layer n o l i t o a c c o i t Presentation Layer l o p r p P A Correlation-based Communication Layer Session Layer Transport Layer (end-to-end transfer of message) l o c o Network Layer (Transfer of packets across network) t o r P r t o Data Link Layer (Transfer of blocks across a link) p s n a r T Physical Layer ISO/OSI Reference Model Wireless Ad-Hoc Model

13 Embed Network into Nodes

14 Correlation-based Communication LayerFusion-Oriented Application Layer Communication Tasks System Maintenance Tasks Broadcasting Global Synchronization Multicasting Network Reconfiguration Hierarchical Communication / Routing Protocols Highest Level Lowest Level Structured (Hierarchical) Communication Network Static/Dynamic Grained-Clustering Physical Layer (Flat Communication Network)

15 Architecture of Sensor NodesControl and computing System Sensor System Communication System Power System System timers Data memory Power tracking unit RF Transceiver Sensor array Micro controller Data path Tradeoffs between power consumption, bandwidth, and latency Interrelationship between transmission rates, processor speed and power consumption. Interface between an application and its communication protocols

16 Types of Nodes in Sensor NetworksHomogeneous 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 (Wi-Fi): Mainly used for the access between wireless devices and base stations. Possible for the access between wireless devices. IEEE (based on Bluetooth): Used for Ad-hoc network without base station.

17 Comparison between standardsFrequency (unlicensed) Data rate MAC Protocol 802.11b GHz Up to 11 Mbps Random access CSMA/CA 802.11a GHz Up to 54 Mbps Same as above 802.11g GHz Up to 54 Mbps Same as above 802.15(based on Bluetooth) 2.4 GHz Up to 1 Mbps TDM CSMA/CA CAMA/CA: carrier sense multiple access with collision avoidance TDM: time division multiplexing Indoor 10-30 m Outdoor m Mid range 200m-4km Long range 5Km-20Km 802.11(a,g) 802.11b 802.15 UMTS/WCDMA,CDMA2000 IS-95 CDMA, GSM 54 Mbps 5-11 Mbps 1 Mbps 384 Kbps 56 Kbps

18 (Media access control )Communication Unit Application control MAC (Media access control ) protocol Protocol processing Synchronizer Channel coding RF transceiver Transmission power control

19 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: MHz: Europe, allows one communication channel (2003, 2006) MHz: North America, up to ten channels (2003), extended to thirty (2006) MHz: worldwide use, up to sixteen channels (2003, 2006) 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.

20 View of WSN at Different Level

21 Networking Architecture/TopologyFlat 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

22 Design of Networking ArchitectureFlat 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

23 Broadcast on A Cluster-Based Network

24 Flat and Structured Sensor Network: An ExampleHighway (Back bone) Local way (cluster) Sink Primary sensor node Communicable sensor node

25 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 cluster head 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 !

26 Comprehensively Design AD-NetsClustering architecture which support the functionalities for both of communication and network self-organization. Design efficient algorithms for network self-organization Design efficient algorithms for key control and communication functions

27 Architecture Self-Clustering/ Reconfigurationhead Self-Clustering backbone cluster gateway When self-clustering finished, each node has 1-hop information: In a cluster, head knows members’ ids, and members know head’s id. In backbone, each backbone node knows its neighbors in the backbone. Each node knows its neighbors’ ids.

28 Self-reconfigurationNodes 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

29 Want to join

30 (2) Node move-Out Backbone is re-built !!! Want to move outBackbone is broken!!!

31 Routing Protocols and Communication Algorithms(1) Broadcasting (i) Broadcast via depth-first-search of backbone (Asynchronized) Euclid circuit traveling s

32 (ii) Broadcast via collision-free flooding (Synchronized) (power saving and robust) cluster head gateway node pure cluster member cluster depth i depth i+1 v Using time division scheme to avoid collision (synchronized)

33 (2) Multicast Outline of Algorithm (Asynchronized)_cluster head gateway node cluster (2) Multicast pure cluster member Outline of Algorithm (Asynchronized)_ Self-building group-backbone tree for each group One to many: broadcasting on group-backbone tree

34 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) Self-clustering O(n) O( n) O(d) Self-reconfiguration (get-in) O( d) Self-reconfiguration (get-out) O(d), O(|T|) get-out node is in the backbone O( d), O( |T|) get-out node is in the backbone O(|T|) get-out node in the backbone Broadcasting (Depth-first) 2×|C| |C| Broadcasting (collision-free flooding) Multicast Data Collection (unit graph) O(D+h) O( Dh) 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

35 Crossbow Sensor Network Deployment for Research IntegrationSensor 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.

36 Sensing and Networking – Sensor SelectionTechnical Approach Sensing and Networking – Sensor Selection Acceleration Sensor – Doesn’t work Magnet sensor – range 11m Acoustic sensor – range 8.89 m to m sensitive to vehicle speed and background noise 270 320 370 420 470 520 570 1 3 5 7 9 11 13 15 17 19 21 10: : : : : : : : : : :04 Time (sec)

37 Sensing and Networking – Sensor DeploymentTechnical Approach Sensing and Networking – Sensor Deployment DEPLOYMENT 1 Cost optimal for vehicle detection by using poles 110 m 122.5 m 4 sensor boards 10 wireless modules longest path = 7 distance between poles = 45 – 50 m Transmission range = 43m Sensing range = 11m Gateway

38 Sensing and Networking – Sensor DeploymentTechnical Approach Sensing and Networking – Sensor Deployment DEPLOYMENT 2 Cost optimal for vehicle detection without poles 110 m 122.5 m 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

39 Sensing and Networking – Sensor DeploymentTechnical 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

40 Sensing and Networking – Sensor DeploymentTechnical Approach Sensing and Networking – Sensor Deployment cluster DEPLOYMENT 4 Longer network lifetime with redundancy 2 22m < 18.5m < 29 m 24 sensor boards 32 wireless modules gateway

41 Sensing and Networking – Sensor DeploymentTechnical Approach Sensing and Networking – Sensor Deployment cluster DEPLOYMENT 5 Longer network lifetime with redundancy 4 gateway

42 Exercises: What are wireless ad-hoc/mobile/sensor networks? What are the challenge for the networks of low cost and small-sized sensor nodes? Explain the tradeoff of centralized system and decentralized system How to get a neighbor list if the Ids of nodes are not numbered contiguously? Counting problem: How to number n nodes from 1 to n? Leader selection problem: how to select a leader?