Algorithm 2: Broadcasting using Euclidean Circle Each node v: Forming a spanning tree T if v received the message (Each node keeps (u, x, d) the a neighbor list in T) if x is not v then Transmitting data in ignore The message. depth-first style Otherwise. select a neighbor w whom v hasn't sent the Sender receiver data message to yet and transmit the message (v, w, d). If v has sent the message to all its Source u eighbor v sent the message (v, parent, d) Observations It is a Deterministic algorithm: only one node transmits in one time slot Communication complexity: Totally 2 (n-1)time slots with n nodes It is expensive in a large scale of network
Algorithm 2: Broadcasting using Euclidean Circle Source u Observations: • It is a Deterministic algorithm: only one node transmits in one time slot. •Communication complexity: Totally 2(n-1) time slots with n nodes It is expensive in a large scale of network!!! • Forming a spanning tree T (Each node keeps a neighbor list in T) • Transmitting data in depth-first style v (Sender, receiver, data) 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)
Communication on Wireless on 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 Each node: Node v transmits its id at the time slot same as its ⑨ id's ⑦ 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?
9 4 3 5 8 2 6 1 7 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 Each node v: Node v transmits its id at the time slot same as its id’s. Observations: • Each node can have a neighbor list after n time-slot. • Synchronization is needed. Communication on Wireless on AD-NETs – Continue 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(W<Rs) Basics of AD-Net Design Issues in WSNs o Medium Access Control(MAC) Routing ◆Mult- casting Network Self-organization ◆ Security Application E 6o Layer 令 Energy management Transport EG ◆ Query/ Addressing Layer至 Cross-layer Network到豆 ◆ Scalability control Layer ◆ Deployment Methods Data Link g o ◆ Quality of Service Layer Physical Layer
Medium Access Control (MAC) Routing Multi-casting Network Self-organization Security Energy Management Query/Addressing Scalability Deployment Methods Quality of Service Issues in WSNs Physical Layer Data Link Layer Network Layer Transport Layer Application Layer Power Management Mobility Management Task Management Sensor Node Protocol Stack Cross-layer control Basics of AD-Net Design II. Design of Wireless Sensor Networks (WSNs)
Overall Networking Process application layer Application Layer Presentation Layer Correlation-based Session layer Communication Layer Transport Layer end-to-end transfer of message) Network Layer c Transfer of packets across network) 8 Data link layer (Transfer of blocks across a link) Physical layer Physical layer ISO/OSI Reference Model Wireless Ad-Hoc Model
Overall Networking Process ISO/OSI Reference Model Physical Layer Application Layer Wireless Ad-Hoc Model Correlation-based Communication Layer Physical Layer Data Link Layer (Transfer of blocks across a link) Network Layer (Transfer of packets across network) Transport Layer (end-to-end transfer of message) Session Layer Presentation Layer Application Layer Ap plic atio n P r oto c ol T ra n s p o rt P r oto c ol
Embed Network into nodes pplication( Configurable Service) Layer Network e Network Management Networking(Application)Functions Tasks Topology-based Architecture/rout or attribute based ing protocol Data Data Data reconfiguration collection Dissemination Aggregation subnet Routing Operations Query-based multipath-based QoS-based ddressing protocols Attribute-based Topology-based Global addressing Oronoco protoco rotocol Link abstraction Laver Routing table Routing table(adaptive (Flat Structure) hierarchical structure Send Receive Neighbor Cluster Back bone Message pool Neighbors Member: *Parents Childre Multiple link Mac) and Physical layer
Network Management and Cross-Layer Control Node physical condition detection Node move-in/out detection Localization synchronization Power management Task driven protocol Network status detection Multiple Link (MAC) and Physical Layer Neighbor: Cluster Head: Member: Backbone Neighbors: *Parents: *Children: Link Abstraction Layer Send Receive Message pool Routing table (Flat Structure) Routing table (Adaptive hierarchical structure) Addressing Protocols Attribute-based protocol Topology-based protocol Global addressing protocol Routing Operations Query-based routing multipath-based routing QoS-based routing Networking (Application) Functions Data collection Data Dissemination Data Aggregation Topology-based or attribute-based subnet communication Network Layer Application (Configurable Service) Layer Network Management Tasks Architecture/rout ing protocol reconfiguration Network Management and Cross-Layer Control Node physical condition detection Node move-in/out detection Localization synchronization Power management Task driven protocol Network status detection Multiple Link (MAC) and Physical Layer Neighbor: Cluster Head: Member: Backbone Neighbors: *Parents: *Children: Link Abstraction Layer Send Receive Message pool Routing table (Flat Structure) Routing table (Adaptive hierarchical structure) Addressing Protocols Attribute-based protocol Topology-based protocol Global addressing protocol Attribute-based protocol Topology-based protocol Global addressing protocol Routing Operations Query-based routing multipath-based routing QoS-based routing Query-based routing multipath-based routing QoS-based routing Networking (Application) Functions Data collection Data Dissemination Data Aggregation Topology-based or attribute-based subnet communication Network Layer Application (Configurable Service) Layer Network Management Tasks Architecture/rout ing protocol reconfiguration Embed Network into Nodes