Mess Networking-motion to form a study group PowerPoint Presentation

Slide 1 -

November 2006 IEEE802.15.5 TG Slide 1 Project: IEEE P802.15 Working Group for Wireless Personal Area Networks (WPANs) Submission Title: [IEEE 802.15.5 WPAN Mesh Tutorial] Date Submitted: [November 11, 2006] Source: [Myung Lee] Company [CUNY] Address [Dept. of EE, 140th St & Convent Ave, New York, NY 10031, USA] Voice:[212-650-7260], FAX: [], E-Mail: [myung.lee@ieee.org] Re: [ A tutorial for IEEE 802.15.5 WPAN Mesh] Abstract: [The tutorial will introduce applications, technical requirements of WPAN Mesh and describe technical contents of current draft. The current draft contains mainly two parts, Mesh functions and MAC enhancement, including architecture, mesh routing, beaconing, and other components both in high rate and low rate mesh.] Purpose: [To introduce IEEE 802.15.5 WPAN Mesh to IEEE 802 community] Notice: This document has been prepared to assist the IEEE P802.15. It is offered as a basis for discussion and is not binding on the contributing individual(s) or organization(s). The material in this document is subject to change in form and content after further study. The contributor(s) reserve(s) the right to add, amend or withdraw material contained herein. Release: The contributor acknowledges and accepts that this contribution becomes the property of IEEE and may be made publicly available by P802.15.

Slide 2 -

November 2006 IEEE802.15.5 TG Slide 2 IEEE 802.15.5 WPAN Mesh A Tutorial Dallas, TX November 14, 2006

Slide 3 -

November 2006 IEEE802.15.5 TG Slide 3 Contents Introduction Purpose & Scope, Applications, Reference Model High Rate WPAN Mesh MAC enhancement, Mesh Routing Low Rate WPAN Mesh Mesh Routing, Multicasting

Slide 4 -

November 2006 IEEE802.15.5 TG Slide 4 Tutorial 802.15.5 Introduction Presenter: M. Lee Contributor: HR Shao, M. Lee

Slide 5 -

November 2006 IEEE802.15.5 TG Slide 5 What is WPAN Mesh? A Wireless PAN that employs one of two connection arrangements: full mesh topology or partial mesh topology.

Slide 6 -

November 2006 IEEE802.15.5 TG Slide 6 WPAN Mesh Networking

Slide 7 -

November 2006 IEEE802.15.5 TG Slide 7 Purpose of the project This project facilitates wireless mesh topologies optimized for IEEE 802.15 WPANs. -Extension of network coverage without increasing transmit power or receive sensitivity -Enhanced reliability via route redundancy -Easier network configuration -Better device battery life due to fewer retransmissions

Slide 8 -

November 2006 IEEE802.15.5 TG Slide 8 Scope of the group To provide a Recommended Practice to provide the architectural framework enabling WPAN devices to promote interoperable, stable, and scaleable wireless mesh topologies. Including mesh support for both High-Rate and low-rate WPANs. High Rate Mesh over 802.15.3b MAC Low Rate Mesh over 802.15.4b MAC

Slide 9 -

November 2006 IEEE802.15.5 TG Slide 9 App1: Multimedia home network Consumer Electronics (CE) Video HDTV, DVD Audio HiFi stream, VoIP Interactive Gaming Mesh for High throughput with QoS Coverage extension with multihop Single- or multi- room residential environment

Slide 10 -

November 2006 IEEE802.15.5 TG Slide 10 App2: Interconnection among PC and peripherals PC and peripherals Human Interface Device (HID) Local file transfer Printing Content download (camera) Single room or small office Mesh for Potentially improving the network capacity

Slide 11 -

November 2006 IEEE802.15.5 TG Slide 11 App3: Interconnection among handheld devices WPAN anywhere Mesh for network reliability power saving Handheld devices Audio (cordless headset) Content download (MP3 player, photo camera) Internet file transfer & audio/video streaming (PDA, cell phone)

Slide 12 -

November 2006 IEEE802.15.5 TG Slide 12 Automation and control: home Factory, warehouse Energy saving (NYC apartment complex project) Monitoring Safety, security Health (BAN) Environments (agriculture, building, aqueous, etc) Situational awareness and precision asset location (PAL) military actions firefighter operations (search and rescue) Ex.use of mice autonomous manifesting real-time tracking of inventory Entertainment learning games interactive toys App4: LR Applications

Slide 13 -

November 2006 IEEE802.15.5 TG Slide 13 Mesh for LR Applications Low transmission power and long battery life for sensor nodes; Large coverage area of monitoring and control; Reliable sensory data transmission via multiple paths.

Slide 14 -

November 2006 IEEE802.15.5 TG Slide 14 HR Reference Model

Slide 15 -

November 2006 IEEE802.15.5 TG Slide 15 LR Reference Model

Slide 16 -

November 2006 IEEE802.15.5 TG Slide 16 Tutorial 802.15.5 High-Rate Mesh WPANs Presenter: S. Max Contributors: S. Max, M. Shim, Y. Liu

Slide 17 -

November 2006 IEEE802.15.5 TG Slide 17 Usage Scenario HR WPAN

Slide 18 -

November 2006 IEEE802.15.5 TG Slide 18 Usage Scenario - Analysis (Semi) stationary backbone PNCs Complex devices Mains powered Mobile clients DEVs Simple devices Battery powered  Convenience  Cable replacement  Coverage extension  Connection everywhere

Slide 19 -

November 2006 IEEE802.15.5 TG Slide 19 Challenges in WPAN Mesh Scenarios Medium Access Control Efficient spatial frequency reuse Hidden and Exposed nodes Interference situation QoS support Mobility Security Ad hoc deployment Access Control Secure distribution of path selection info Path selection (Routing) Self organizing Redundant links Loop prevention Broadcast data

Slide 20 -

November 2006 IEEE802.15.5 TG Slide 20 Hidden entities – Threat to WMN communication C cannot sense A’s transmission (physical carrier sense) C cannot sense neither sense A’s RTS nor B’s CTS frame (virtual carrier sense) C detects wireless medium as idle C transmits to D B’ reception of A is interfered by C’s transmission  collision

Slide 21 -

November 2006 IEEE802.15.5 TG Slide 21 Exposed entities – Limiting capacity of WMNs A sends data to B B & C separated by wall B cannot be interfered by C  Opportunity for spatial frequency reuse (concurrent transmission) C could transmit to D C blocked by RTS from A

Slide 22 -

November 2006 IEEE802.15.5 TG Slide 22 IEEE 802.15.5-HR Recommended Practice Entities, Architecture, Extensions

Slide 23 -

November 2006 IEEE802.15.5 TG Slide 23 Single-Hop WPANs Layer architecture Network architecture Superframe architecture

Slide 24 -

November 2006 IEEE802.15.5 TG Slide 24 Single-Hop WPANs Mesh WPANs Layer architecture Network architecture Superframe architecture Mesh topology among PNCs 2 hierarchy levels

Slide 25 -

November 2006 IEEE802.15.5 TG Slide 25 Mesh WPANs Layer architecture Network architecture Superframe architecture M Wireless Path Selection Extensions to the MAC Multiple Beacons Reservation Negotiation

Slide 26 -

November 2006 IEEE802.15.5 TG Slide 26 Mesh WPANs Layer architecture Network architecture Superframe architecture Space Multiple Beacons per Superframe Negotiation between PNCs about medium occupation Optional: Spatial divided frequency reuse

Slide 27 -

November 2006 IEEE802.15.5 TG Slide 27 Mesh WPANs Layer architecture Network architecture Superframe architecture

Slide 28 -

November 2006 IEEE802.15.5 TG Slide 28 802.15.5 Tutorial High Rate Mesh Service Support

Slide 29 -

November 2006 IEEE802.15.5 TG Slide 29 Network self-organization In order to start a mesh network, an MC shall include a mesh capacity IE in its beacons. Its neighbor MPNCs may join the tree by sending a tree association request to the MC. The MC sends a tree association response back to each neighbor. After an MPNC joins a mesh tree, it shall include a mesh capacity IE in its beacons. Similarly, the neighbors of the MPNC may join the tree by associating with the MPNC.

Slide 30 -

November 2006 IEEE802.15.5 TG Slide 30 Tree topology discovery When the tree is formed, the MC broadcasts a tree topology discovery frame, along the tree branches, to all tree members. Each tree member, from bottom to top, sends a tree topology update frame to its parent to report the number of existing and expected descendants.

Slide 31 -

November 2006 IEEE802.15.5 TG Slide 31 TREEID assignment After receiving topology update frames from all children: the MC first reserves a block of TREEIDs for future descendants; and then, it assigns single TREEIDs to those children who cannot support any descendant; lastly, it divides the remaining TREEIDs among other children based on the descendant ratios of these children. When an MPNC receives a TREEID block allocated from its parent, it divides the TREEID block among its children in the same way as MC does.

Slide 32 -

November 2006 IEEE802.15.5 TG Slide 32 Tree routing To conduct tree routing, an MPNC first checks whether the TREEID of the destination MPNC falls into its own TREEID block. If not, it shall forward the packet to its parent. Otherwise, it checks whether the TREEID of the destination MPNC falls into one of its children’s TREEID blocks. If, for example, the TREEID of the destination MPNC falls into child i ’s TREEID block, the MPNC shall forward the packet to child i.

Slide 33 -

November 2006 IEEE802.15.5 TG Slide 33 Centralized routing One or more MPNCs may serve as topology server to store link state information of all MPNCs. When a topology server is available in the mesh network, all MPNCs shall register their link states at the topology server. A source MPNC may initiate a centralized routing process by sending a route discovery frame to a topology server. The route discovery frame is transmitted by using tree routing. Once the topology server receives the route discovery frame, it calculates the optimal route between the source and destination. The topology server then delivers the information of the optimal route to the destination via a route notification frame. The route notification frame is transmitted by using tree routing. Once the destination receives the route notification frame, it sends a route formation frame to the source along the optimal route. Upon receiving the route formation frame, nodes on the optimal route shall create routing entries for both the source and the destination.

Slide 34 -

November 2006 IEEE802.15.5 TG Slide 34 802.15.5 Tutorial Low Rate WPAN Mesh Presenter: Chunhui (Allan) Zhu* Contributors: Chunhui (Allan) Zhu Jianliang Zheng ** * Samsung Electronics ** EMC Corporation

Slide 35 -

November 2006 IEEE802.15.5 TG Slide 35 Outline Low-Rate WPAN Mesh – The Architecture Tree Formation and Addressing Unicast Routing Multicast Routing

Slide 36 -

November 2006 IEEE802.15.5 TG Slide 36 Management Entity Low-Rate WPAN Mesh – The Architecture PHY Layer PD SAP MAC Common Part Sublayer MCPS SAP Service Specific Convergence Sublayer (SSCS) PLME PLME SAP MLME MLME SAP Layering of 802.15.4/4b Layering of meshed 802.15.4/4b PHY Layer PD SAP PLME PLME SAP Mesh Functions MAC Common Part Sublayer MCPS SAP MLME SAP MLME MAC Enhancement Mesh Routing MAC Enhancement (SSCS) Management Entity of Next Higher Layer (Not Presented)

Slide 37 -

November 2006 IEEE802.15.5 TG Slide 37 Tree Formation and Addressing In a LR-WPAN mesh network, a tree is formed for both addressing and routing purposes. First form an Adaptive Tree (AT) Initialization Phase Operation Phase Then form a Meshed Adaptive Tree (MAT)

Slide 38 -

November 2006 IEEE802.15.5 TG Slide 38 Adaptive Tree Formation – Initialization Phase Stage 1: Association A B J E D C I H K L O G [0] F M N [0] [0] [0] [0] [0] [0] [1] [children#][children#]=[8][6] [5] [5][2] [1][2][1] [1] [3][1] [1][1] Stage 2: Reporting number of children Stage 3: Address assignment An AT is formed. Additional addresses can be reserved. [beg,end,next]=[1,16,1] [beg,end,next]=[17,28,17] [3,12,3] [13,16,13] [19,28,19] [5,6,5] [7,10,7] [11,12,11] [15,16,15] [21,26,21] [27,28,27] [9,10,9] [23,24,23] [25,26,25]

Slide 39 -

November 2006 IEEE802.15.5 TG Slide 39 Adaptive Tree Formation – Operation Phase Normal data transmissions A 0 B 1 J 17 E 7 D 5 C 3 I 15 H 13 K 19 L 21 O 27 G 11 [0] F 9 M 23 N 25 [0] [0] [0] [0] [0] [0] [1] [8][6] [5] [5][2] [1][2][1] [1] [3][1] [1][1] [1,16,1] [3,12,3] [13,16,13] [19,28,19] [5,6,5] [7,10,7] [11,12,11] [15,16,15] [21,26,21] [9,10,9] [23,24,23] [25,26,25] Nodes are still allowed to join the network [17,28,17] [27,28,27] Look at the address blocks for the destination address and route the packet accordingly. If not found, route through parent. Example: Node C  node L

Slide 40 -

November 2006 IEEE802.15.5 TG Slide 40 Meshed AT Formation A 0 B 1 J 17 E D C I H 13 K L O G F M N [5] [5][2] [3,12,3] [13,16,13] [19,28,19] [1] [8][6] [15,16,15] [1,16,1] [17,28,17] [17,28,17] [1,16,1] [17,28,17] [13,16,13] …… Neighbors treat each other as a child. Advantages Shorter paths Elimination of SPOFs

Slide 41 -

November 2006 IEEE802.15.5 TG Slide 41 Unicast Routing Meshed Adaptive Tree Provides the basic functions of routing; Immediately available after MAT is formed. Distributed Link State Optimized routing can be achieved. Requires exchange of link state of information. Two levels Basic link state scheme Extended link state scheme

Slide 42 -

November 2006 IEEE802.15.5 TG Slide 42 The Basic Link State Scheme 3-hop Link State (view of node J)

Slide 43 -

November 2006 IEEE802.15.5 TG Slide 43 The Extended Link State Scheme I J A B C L D K Multiple paths Created through ELS

Slide 44 -

November 2006 IEEE802.15.5 TG Slide 44 The Extended Link State Scheme Link state table is locally determined according to the local node density different nodes may have different link state table size. Expand link state table by exchanging link state table information (using unicast) build multiple paths between nodes that are originally connected through a single path. Differential treatment is provided for neighbors when building local link state table, for example, depending whether a neighbor is an ancestor/descendent or a sibling node.

Slide 45 -

November 2006 IEEE802.15.5 TG Slide 45 Unicast Routing – Summary Simplicity No route discovery No route repair Adaptive address assignment avoiding “running out of addresses” problem Meshed AT (MAT) shorter path robustness Distributed Link State scalability multiple paths and robustness shorter path

Slide 46 -

November 2006 IEEE802.15.5 TG Slide 46 Multicast Routing Utilizing the underlying Meshed Adaptive Tree build by unicast routing algorithm to construct shared multicast trees for different multicast groups; Low control overhead No control traffic is broadcast; In most cases, the Network Coordinator is not bothered for transmitting control and data messages. The introduction of Group Coordinator and simple joining/leaving algorithm guarantee the multicast sub-tree is minimal at any time. Simple and timely data propagation. Data packets do not need to go to the Network Coordinator first. Non-members can also send packets to members;

Slide 47 -

November 2006 IEEE802.15.5 TG Slide 47 Logical Entities Group Member (GM) – a node participating a multicast group On-Tree Router (OnTR) – nodes on the multicast tree but not GMs Group Coordinator (GC) – the top level GM or OnTR of a specific multicast group (sub-tree root). It sets the upper bound of the multicast tree. Network Coordinator (NC) – the root of the MAT. It keeps information of all multicast groups in the network so that it always knows from which child(ren) it can reach the multicast tree for a specific group. Off-Tree Router (OffTR) – nodes that are GC’s direct ancestors (including TC). These nodes are not on the multicast tree but they know from which child they can reach the multicast tree Non-Member (NON-GM) – nodes have knowledge about a specific multicast group.

Slide 48 -

November 2006 IEEE802.15.5 TG Slide 48 Functions and Message Types Joining the Multicast Group JREQ – Join REQuest JREP – Join REPly Leaving the Multicast Group LREQ – Leave REQuest LREP – Leave REPly Switching Role as Group Coordinator GCUD – GC UpDate Terminating the Multicast Session GDIS – Group DISmission

Slide 49 -

November 2006 IEEE802.15.5 TG Slide 49 Joining the Multicast Group – First GM 1 2 3 4 5 6 To join a multicast group, a Non-GM generates a JREQ and unicasts it to its parent node. A GM/OnTR/OffTR/GC/NC shall reply with a JREP; other nodes shall forward to their parent nodes until a GM/OnTR/OffTR/GC/NC is reached. The NC sends the JREP with the GC flag set indicating the sender of the JREQ is the first GM of this group and should be the GC of this group.

Slide 50 -

November 2006 IEEE802.15.5 TG Slide 50 Joining the Multicast Group – Normal Cases Node A join with its direct parent – Node F (OnTR) Node B gets JREP from Node G (GC), Node D becomes an OnTR after Node B joins Node C gets JREP from Node H (GM), Node E becomes an OnTR after Node C joins

Slide 51 -

November 2006 IEEE802.15.5 TG Slide 51 Joining the Multicast Group – Special Cases An OnTR node simply changes its status from OnTR to GM (not shown in the figure); An OffTR and the NC simply changes its status to the GC and sends a GCUD to the current GC to request it to give up the GC status (shown in the figure is the case of OffTR join);

Slide 52 -

November 2006 IEEE802.15.5 TG Slide 52 Leaving the Multicast Group Node A can leave the tree since it is a leaf node (step 1&2). The leave of Node A makes Node B (a OnTR) a leaf node. B will also leave (step 3&4). In the case GC Node C is not a GM, and it finds that it has only one next hop to the group after Node B leaves, it will give up its role as a GC by sending a GCUD to its only child and becomes an OffTR (step 5). Node D forwards GCUD and changes its status from OnTR to OffTR (step 6) The first GM (or OnTR with more than one branches) receives the GCUD will become the new GC for the shrunk multicast tree.

Slide 53 -

November 2006 IEEE802.15.5 TG Slide 53 Switching Role as Group Coordinator – New GM Join The JREQ from A hits a OffTR D. Node D will be the new GC since its tree level is smaller than the current GC Node E changes its status from OffTR to OnTR since it is now on the multicast tree Node F gives up its status as the GC and becomes either a GM or a OnTR The current GC may also leave the group and lead to GC migration (see previous slide)

Slide 54 -

November 2006 IEEE802.15.5 TG Slide 54 Terminating the Multicast Session – Group Dismiss When a group finishes its session, one of the members can issue a GDIS packet (multicast) to all the members to indicate the end of the group communication; The application will determine which member have the right to issue this GDIS packet; Upon receiving the GDIS packet GMs and OnTRs will delete all the information related to this group; GC will issue a LREQ toward NC and follow the operation of the GC leave. All OffTRs along the route to NC and the NC will delete all the information related to this group by this process. The GDIS packet reduce the control traffic led by GM’s leaving process described before.

Slide 55 -

November 2006 IEEE802.15.5 TG Slide 55 Data Transmission Mechanism Multicast packets propagate (via MAC layer broadcast) following the multicast tree; The GC limits the packet propagation to be inside the multicast tree. Nodes process/forward the multicast packets depending on their participation level in the multicast group. GM/GC/OnTR/OffTR/NC/Non-GM Non-members can send packets to the multicast group but cannot receive. Non-GM unicast packets toward the NC until the packets hit a GM/OnTR/OffTR/GC/NC. Not recommended due to security reasons.

Slide 56 -

November 2006 IEEE802.15.5 TG Slide 56 Thank you!! Any Question?