Mạng không dây 2

Chia sẻ: 4 4 | Ngày: | Loại File: PDF | Số trang:234

Thêm vào BST

Báo xấu

91
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Definition – Ad Hoc Network • Ad hoc is a Latin phrase which means "for this [purpose]" • The purpose is to interconnect computational nodes for information exchange i f ti h • I t Interconnection is being realized d ti i b i li d decentralized, without t li d ith t pre-existing infrastructure, e.g. routers, access points • Nodes participate in routing of packets, deciding dynamically, dynamically based on connectivity to neighbour nodes nodes. 11 12 .Definition – Sensor Network • Sensor from the Latin word sentire which means “to feel” or “to perceive” • A Sensor measures a physical quantity and...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Mạng không dây 2

Outline Wireless Ad Hoc & Sensor Networks - Introduction - • Terms of Lecture • Lecture Overview • History A E • Definition B F S • Applications D D • Repetition – Physical Layer C • Issues WS 2010/2011 • Summary Prof. Dr. Dieter Hogrefe Dr. Omar Alfandi 2 Terms of Lecture Terms of Lecture • Learning Goals: • Weekly lecture (2 SWS, 5 Credits) – Understanding, application & critical evaluation of wireless Ad Hoc Sensor network principles H &S t k i i l • Problem Sheets (self solution) • Basics • Issues • Written Exam: 90 minutes at end of semester • Current solutions • Open research questions • Target audience: AI BSc (5++ sem.); AI MSc (1++ sem.); sem ); sem ); • Wh t we expect: What t IT IS MSc (1++ sem.) – Be prepared for each lecture i.e. read announced chapter (text book) and lecture slides (published as soon as possible) • A di / id recording of th l t Audio/video di f the lecture ( ft th l t ) (after the lecture) – Autonomously solve problem sheets, feel free to ask questions (office hours, email) 3 4
Terms of Lecture Outline • Literature • Terms of Lecture • Lecture Overview – Ad Hoc Wireless Networks: Architectures and Protocols; C. • History Murthy & B. Manoj, Prentice Hall, 2004 ISBN: 013147023X (First is the basic text book used for the lecture structure) • Definition • Applications – Protocols and Architectures for Wireless Sensor Networks; H. Karl & A.Willig; 2005; Wiley & Sons; ISBN 0470095102 • Repetition – Physical Layer (Second is also used for Sensor Networks) • Issues • Summary – Further Literature and papers, will be announced in lecture slides. 5 6 Lecture Overview – OSI Reference Model Lecture Overview • Introduction - Today Application • A layer is a collection of • External Invited Talk (1 lecture, CS Colloquium) conceptually similar functions that • Medium Access Schemes (1 lecture) Transport Protocol provide services to the layer above • Routing and Secure Routing (2 lectures) it and receives service from the layer below it • Energy Management (1 lecture) Network Protocol • Transport Layer Protocols & QoS ( lecture) p y (1 ) • Conceptually two instances at one • Security (2 lectures) Media Access Protocol layer are connected by a horizontal • Sensor Networks (3 lectures) ( ) protocol connection on that layer Physical Channel (Radio) • Final written Exam (last lecture date) ( ) 7 8
Outline History • Terms of Lecture 500 B.C. 1970‘s 1980‘s 1990‘s Today • Lecture Overview • History Ad Hoc Voice ALOHAnet MANET Bluetooth Mesh • Definition Communication PRNET Hybrid • Applications ! ! ! Sensor … • Repetition – Physical Layer S D • Issues • Summary King Darius DARPA IETF Ericsson … of Persia 9 10 Outline Definition – Ad Hoc Network • Terms of Lecture • Ad hoc is a Latin phrase which means "for this [purpose]" • Lecture Overview • History • The purpose is to interconnect computational nodes for • Definition information exchange i f ti h • Applications • Repetition – Physical Layer • I t Interconnection is being realized d ti i b i li d decentralized, without t li d ith t • Issues pre-existing infrastructure, e.g. routers, access points • Summary • Nodes participate in routing of packets, deciding dynamically, dynamically based on connectivity to neighbour nodes nodes. 11 12
Definition – Sensor Network Definition – Cellular vs. Ad Hoc • Sensor from the Latin word sentire which means “to Cellular Networks feel” or “to perceive” • A Sensor measures a physical quantity and converts it A D into i t a signal, d ti d f an observing i t i l destined for b i instrument t S D • S Sensors use Ad H networking t communicate Hoc t ki to i t Ad Hoc Multihop Networks observed information E A C D S B D 13 14 Cellular vs Ad Hoc Outline Cellular Networks Ad Hoc Wireless Networks • Terms of Lecture Fixed infrastructure based Infrastructure less • Lecture Overview Single-hop wireless links Multi-hop wireless links • History Centralized routing Distributed routing High reliability Frequent path breaks due to mobility • Definition Low complexity mobile hosts Mobile hosts also routers • Applications Geographical reuse of spectrum Carrier sense bases reuse of • Repetition – Physical Layer spectrum Widely deployed, currently 4G Remaining issues, low commercial • Issues deployment, widespread i d f d l t id d in defense • Summary 15 16
Applications Applications - Military • Military Applications • Why? Establish communication among a group of • Transportation Communication soldiers/vehicles for tactical operations • Wireless Sensor Networks (Monitoring) • Collaboration/Distributed Computing • Where? Areas with impossible infrastructure set up • Emergency Operations g y p • Wireless Mesh Networks • Security is crucial, eavesdropping and other attacks can • Hybrid Wireless Networks y compromise information and personel safety. 17 18 Applications – Transportation (C2C) Applications – Sensor Networks • Why? Primary reduce number of lethal accidents. • Why? Monitoring of physical parameters and Secondary enable new kinds of services. S d bl ki d f i transmitting to a sensor sink • How? Enable Car to Car (C2C) and Car to Infrastructure • Where? Health care, home security, military, (C2I) communication for road safety messages. environmental monitoring • Issues: mobility, network size, deployment density, power constraints t i t 19 20
Applications - Animal Monitoring Applications – Collaboration 1. Biologists put sensors in • Why? Required instant communication underground nests of storm petrel • Where? Conference (file exchange), Lecture (notes 2. And on 10cm stilts distribution) using laptops/smart phones 3. Devices record data about birds • Properties: Lower security than military, energy constraints, uni- and multicast. 4. Transmit to research station 5. And from there via satellite to lab 21 22 Applications – Emergency Operations Applications – Wireless Mesh Networks • Why? Required communication for rescue, crowd • Why? Provision of alternate communication capability to control, commando operations activities mobile/fixed nodes, opposed to cellular networks. • Where? Areas with no/destroyed infrastructure due to • Where? Areas with no/low cable coverage or cost natural calamities, war, etc. constraints or quick deployment needs. • Properties: self configurable, decentralized, capable of • Properties: Simple expandability, high availability voice communication i i ti 23 24
Applications – Hybrid Wireless Networks Applications – Hybrid Wireless Networks Cellular Multi-Hop Networks • What? Multi-hop cellular networks • Why? Exponential growth in subscriber base of cellular networks, over 4 bn in 2008. E A D • Properties: mobile nodes are involved in routing, High capacity/coverage, centric routing topology maintenance S B D (BTS), Problem: energy constrained mobile nodes (BTS) P bl t i d bil d 25 26 Outline Physical Layer - OSI Reference Model • Terms of Lecture Application • Lecture Overview • History Transport Protocol • Definition • Applications Network Protocol • Repetition – Physical Layer • Issues Media Access Protocol • Summary Physical Channel (Radio) 27 28
Physical Layer - Spectrum Physical Layer - Frequencies and Regulations regulated Europe (CEPT/ETSI) USA (FCC) Japan Mobile GSM ≈ 800, 1700, CDMA ≈ 800 MHz, PDC ≈ 800, 900, 1400 phones 1800 Mhz 1800 Mh Mhz Mh CDMA, GSM ≈1800 MHz, 1900 MHz Cordless DECT PACS ≈ 1800, 1900 Mhz PHS ≈ 1900 Mhz telephones 1880-1900 MHz 1 Mm 10 km 100 m 1m 10 mm 100 m 1 m JCT ≈ 200 – 400 Mhz 300 Hz 30 kHz 3 MHz 300 MHz 30 GHz 3 THz 300 THz Wireless IEEE 802.11 IEEE 802.11 IEEE 802.11 LANs 2400-2483 MHz 2400-2483 MHz 2471-2497 MHz VLF LF MF HF VHF UHF SHF EHF infrared visible light UV ISM 29 30 Physical Layer - Signal Propagation Ranges Physical Layer – Signal Propagation • Straight line propagation Free space propagation • Transmission range Pr = Pt Gt Gr ( λ / 4πd )2 – communication possible • Simplest path loss model, a direct-path signal. – low error rate • The following definitions are assumed: • Detection range sender – Pr - The received signal power. – detection possible transmission – Pt - The transmitted signal power. – no communication comm nication – Gr - Th gain of the receiving antenna. The i f h i i distance • Interference range detection – Gt - The gain of the transmitting antenna. – no signal detection interference i t f – λ - The wavelength of the carrier (i e the center frequency of the (i.e., – Signal part of background noise radiated signal) – d - The distance between the transmitting and receiving antennas. 31 32
Physical Layer - Antennas Physical Layer - Attenuation by Objects z y • Shadowing (3-30 dB): directed x/y x antenna – textile (3 dB) – concrete walls (13-20 dB) side (xz)/top (yz) views side view (yz-plane) – floors (20-30 dB) • reflection at large obstacles y y • scattering at small obstacles • diffraction at edges x sectorized x antenna top view, 3 sector top view, 6 sector shadowing h d i reflection fl ti scattering tt i diffraction diff ti 33 34 Physical Layer - Effects of Mobility Physical Layer - Modulation and Demodulation • Channel characteristics change over time and location analog – signal paths change digital baseband – distance to sender changes power data digital signal analog 101101001 modulation modulation radio transmitter – obstacles position changes radio short long term carrier fading • Fading term fading analog – short term t baseband b b d digital signal – long term analog synchronization data demodulation decision 101101001 radio receiver radio • Doppler shift: carrier change/shift in the frequency 35 36
Physical Layer - Digital Modulation 1 0 1 Outline • Modulation of digital signals • Terms of Lecture t • Amplitude Shift Keying (ASK): • Lecture Overview – very simple 1 0 1 • History – low bandwidth requirements – very susceptible t i t f tibl to interference • Definition t • Applications • Frequency Shift Keying (FSK): – needs larger bandwidth • Repetition – Physical Layer 1 0 1 • Issues • Phase Shift Keying (PSK): t • Summary – more complex – robust against interference 37 38 Issues Outline • Medium Access Scheme • Terms of Lecture • Routing • Lecture Overview • Multicasting • History • Transport Layer Protocols • Definition • Pricing Scheme • Applications • Quality of Service Provisioning y g • Repetition – Physical Layer • Self Organization • Issues • Security y • Summary • Energy Management • Scalability y 39 40
Summary Summary • Ad Hoc networks serve the purpose of connecting nodes • A vast area of applications is possible for ad hoc instantly, without infrastructure networks – Military • Ancient use in natural societies with voice, drums, – Car2Car trumpets for high speed communication p g p – Mesh – Sensors • Sensors use ad hoc networks to communicate registered – … physical parameters to a monitoring sink • Physical Layer has highly special characteristics • Compared to cellular networks ad hoc nodes are more • Issues exist in all layers due to distribution and dynamics y y complex and deal with dynamic topology and resource constraints • Outlook: Next lecture will tackle properties and issues of MAC layer and possible solutions 41 42 Summary – Next Session Application Transport Protocol Network Protocol Media Access Protocol Physical Channel (Radio) 43
Outline Wireless Ad Hoc & Sensor Networks • Multiple Access Technique Medium Access Control Application • Designing Issues of MAC protocols • Classification of MAC protocols Transport Protocol • Protocols examples Network P N k Protocol l • Characteristics of Link layer protocols • The lower layers in detail WS 2010/2011 Media Access Protocol • Summary Prof. Dr. Dieter Hogrefe Physical Channel (Radio) Dr. Omar Alfandi 2 Media Access Control (Intro.) Multiple Access Technique • Wireless medium is shared • Reservation-based (Recall: mobile communication 1) • Many nodes may need to access the wireless medium to – FDMA : Frequency Division Multiple Access send or receive messages – TDMA : Time Division Multiple Access – CDMA : Code Division Multiple Access • Concurrent message transmissions may interfere with – SDMA : Space Division Multiple Access each other  collisions  message drops • Random – ALOHA : University of Hawaii Protocol – CSMA : Carrier Sense Multiple Access – MACA : Multiple Access with Collision Avoidance • Random with reservation – DAMA : Demand Assigned Multiple Access – PRMA : Packet Reservation Multiple Access 3 4
Reservation-based FDD and TDD • FDMA (Frequency Division Multiple Access) • In case of tow communicating parties sharing the – assign a certain frequency to a transmission channel medium: – permanent (radio broadcast), slow hopping (GSM), fast hopping – Simplex : one way communication from sender to receiver (FHSS, Frequency Hopping Spread Spectrum) – Duplex : two way communication between two parties • TDMA (Time Division Multiple Access) – assign a fixed sending frequency for a certain amount of time – Frequency division duplex (FDD) • CDMA (Code Division Multiple Access) • Combination of two simplex channels with different carrier frequencies • SDMA (Space Division Multiple Access) – Time division duplex (TDD) – segment space into sectors, use directed antennas g p , • Time sharing of a single channel achieves quasi-simultaneous quasi simultaneous – Use cells to reuse frequencies duplex transmission • Combinations 5 6 Random Access Multiple Access • However, wireless communication is often much more Characteristics: ad-hoc • Shared medium : radio channel is shared by an priori – New terminals have to register with the network unknown number of stations – Terminals request access to the medium spontaneously • Broadcast medium: all stations within transmission range – In many cases there is no central control of a sender receive the signal Challenge: Other access methods such as distributed and • Wireless communication channel is prone to errors and non arbitrated non-arbitrated = random access problems, e.g., hidd / bl hidden/exposed node problems & signal d d bl i l attenuation 7 8
Wired vs. Wireless Outline • Ethernet uses 1-persistent CSMA/CD • Multiple Access Technique – carrier sense multiple access with collision detection • Designing Issues of MAC p g g protocols • Sense if the medium is free and start sending as soon as it becomes free • While sending listen to the medium to detect other senders • Classification of MAC protocols • In case of a collision immediately stop sending and wait for the random amount of time • Protocols examples • Problems in wireless networks • Characteristics of Link layer protocols – signal strength decreases quickly with distance • The lower layers in detail – senders apply CS and CD, but the collisions happen at receivers pp y , pp – Energy efficiency: having the radio turned on costs almost as • Summary much energy as transmitting, so to seriously save energy one needs to turn the radio off! 9 10 Need for MAC Protocols ? Hidden Terminal Problem • Popular CSMA/CD (Carrier Sense Multiple • A sends to B, C cannot receive A Access/Collision Detection) scheme is not applicable to wireless networks • C wants to send to B, C senses a “free” medium (CS • CSMA suffers hidden terminal & exposed terminal fails) problems • collision at B, A cannot receive the collision (CD fails) • Collision Detection is impossible in wireless • A is “hidden” for C communication Specific MAC protocols for the access to the physical layer A B C 11 12
Exposed Terminal Problem Near and Far Terminals • B sends to A, C wants to send to D • Terminals A and B send, C receives • C has to wait, CS signals a medium in use – the signal of terminal B hides A’s signal – C cannot receive A • since A is outside the radio range of C waiting is not necessary • C is “exposed” to B A B C – This is also a severe problem for CDMA networks – precise power control required A B C D 13 14 Outline Classification of MAC protocols • Multiple Access Technique • Designing Issues of MAC p g g protocols • Classification of MAC protocols • Protocols examples • Characteristics of Link layer protocols • The lower layers in detail • Summary 15 16
In general (1/2) In general (2/2) • Contention-based protocols: • Contention-based with scheduling – A node does not make any resource reservation a priori. – These protocols focus on packet scheduling at nodes, and also – Whenever a node receives a packet to be transmitted, it scheduling nodes f access t th channel h d li d for to the h l contends with its neighbour nodes for access – Used for enforcing priorities among flows whose packets are – Can not provide QoS (Quality of Service) guarantees to session q queued at nodes since nodes not guaranteed regular access to the channel – Some of them take into consideration battery characteristics (remaining battery power) • Contention-based with reservation • Oth protocols Other t l – Wireless networks may need to support real-time traffic – R Reservation mechanisms f reserving b d idth a priori ti h i for i bandwidth i i – Such protocols can provide QoS support to time-sensitive traffic sessions 17 18 Outline Multiple Access with Collision Avoidance (MACA) A B C D • Multiple Access Technique • MACA uses a two step signaling • Designing Issues of MAC p g g protocols procedure to address the hidden RTS and exposed t d d terminal problems i l bl • Classification of MAC protocols • Use short signaling packets for CTS • Protocols examples collision avoidance – Request (or ready) to send RTS: a b u sender requests the right to send q g • Characteristics of Link layer protocols from a receiver with a short RTS s y Data b u • The lower layers in detail packet before it sends a data packet s y – Clear to send CTS: the receiver • Summary grants the right to send as soon as it is ready to receive ACK 19 20
MACA (cont.) MACA examples • Signaling packets contain • MACA avoids the problem of hidden terminals – sender address – A and C want to – receiver address send t B d to – packet size – A sends RTS first RTS • Network allocation vector (NAV) – C waits after receiving CTS CTS • Duration during which other sender have to keep quiet to avoid a CTS from B A B C collision • If control (RTS-CTS) messages collide with each other • MACA avoids the problem of exposed terminals or with data packets, a backoff procedure is activated – B wants to send to A, (backoff is binary exponential) and C t D d to • Example: Wireless LAN (IEEE 802.11) – now C does not have RTS RTS to wait as C cannot CTS receive CTS from A A B C D 21 22 MACA extensions (1/2) MACA extensions (2/2) • MACAW extends MACA : RTS-CTS-DS-DATA-ACK • MACA –by invitation (MACA-BI) : RTR-DATA – DLL (Data Link Layer) acknowledgements – Is a receiver-initiated MAC protocol, the receiver node initiate – An improved backoff mechanism data t d t transmission i i – DS (Data Sending) message: – It reduces the number of control packets used in the MACA • Say that a neighbour of the sender overhears an RTS but not a CTS p protocol (from the receiver) – MACA-BI eliminate the need for the RTS packet, it uses RTR • In this case it can not tell if RTS-CTS was successful or not (ready to receive) control packet to the sender. • Wh it overhears th DS it realizes th t th RTS CTS was When h the DS, li that the RTS-CTS – RTR packets carries information about the time interval during k t i i f ti b t th ti i t ld i successful, and it defers its own transmission which the DATA packet would be transmitted – The efficiency of the MAC-BI scheme is mainly dependent on the y y p ability of the receiver node to predict accurately the arrival rates of the traffic at the sender nodes. 23 24
Media Access with Reduced Handshake (MARCH) Reservation-based MAC protocol - DAMA • MARCH is receiver-initiated protocol • Demand Assigned Multiple Access (DAMA) • Unlike MACA-BI does not require any traffic prediction • Practical systems therefore use reservation whenever mechanism possible. • In MARCH the RTS packet is used only for the first – But: Every scalable system needs an Aloha style component. packet of the stream. From the second packet onward, • DAMA allows a sender to reserve timeslots. Two phase only the CTS packet is used approach • Th protocol exploits the broadcast nature of the traffic The t l l it th b d t t f th t ffi • R Reservation phase: ti h to reduce the number of the handshakes involved in data – a sender reserves a future time-slot transmission – sending within this reserved time-slot is possible without collision – reservation also causes higher delays • Termination phase: collision-free transmission using p g reserved timeslots 25 26 DAMA: Explicit Reservation PRMA: Implicit Reservation • Aloha mode for reservation: competition for small • Packet Reservation Multiple Access (PRMA) reservation slots, collisions possible. • A certain number of slots form a frame, frames are repeated. • Reserved mode for data transmission within successful • Stations compete for empty slots according to the slotted aloha St ti t f t l t di t th l tt d l h principle. reserved slots (no collisions possible). • Once a station reserves a slot successfully, this slot is automatically y, y • It is important for all stations to keep the reservation list assigned to this station in all following frames. consistent at any point in time and, therefore, all stations • Competition for this slots starts again as soon as the slot was empty have to synchronize from time to time time. in the last frame . reservation 1 2 3 4 5 6 7 8 time-slot collisions ACDABA-F frame1 A C D A B A F ACDABA-F frame2 A C A B A AC-ABAF- frame3 A B A F collision at t reservation Aloha Aloha Aloha Aloha A---BAFD frame4 A B A F D attempts reserved reserved reserved reserved ACEEBAFD frame5 A C E E B A F D t 27 28
Distributed PRMA Schedule-based MAC protocols – SMACS I • Every frame consists of n mini-slots and x data-slots • Given • Every station has its own mini-slot and can reserve up to – Many radio channels k data-slots using this mini-slot (i.e. x = nk). – super-frames of known length  Time synchronisation required • Other stations can send data in unused data-slots • Goal: set up directional links between neighbouring according to a round-robin sending scheme (best-effort nodes traffic) – Link: radio channel + time slot at both sender and receiver N mini slots mini-slots Nk data slots data-slots n=6, n=6 k=2 – Free of collisions at receiver – Channel is picked randomly, slot is searched greedily until a collision free slot is found • Receivers sleep and only wake up in their assigned time slots, once per super-frame reservations other stations can use free data-slots data slots for data-slots based on a round-robin scheme 29 30 Schedule-based MAC protocols – SMACS II Schedule-based MAC protocols – TRAMA • Link Setup • TRAMA: Traffic-adaptive medium access protocol – Case 1: Node A and B are both not connected • Nodes are synchronised • Node A sends invitation message • Time is divided into cycles that consists of • Node B answers that it is not connected to any other node – Random access periods • Node A tells B to pick slot/frequency for the link p q y – Scheduled access periods • Node B returns the link specification • Nodes exchange neighbourhood information – Case 2: Node A has neighbours and node B does not – Learning about their two-hop neighbourhood by using the • N d A creates th link specification and instructs Node B to use it Node t the li k ifi ti di t t N d t ‘neighbourhood exchange protocol’ – Case 3: Node A has no neighbours, but node B has some • In random access period send small incremental neighbourhood • Node B creates the link specification and instructs node A to use it p update information in randomly selected time slots – Case 4: Both nodes have links to neighbours • Nodes exchange schedules • Nodes exchange their schedules and pick free slots/frequencies in – Using the ‘schedule exchange protocol’ mutual agreement • Similar to neighbourhood information exchange 31 32
Schedule-based MAC protocols – TRAMA II Outline • As a result: Each node knows its two-hop neighbourhood and • Multiple Access Technique the schedule • Problem • Designing Issues of MAC p g g protocols – How to decide which slot (in scheduled access period) to use? • Classification of MAC protocols • Solution: ‘Adaptive Election’ • Protocols examples – Use node identifier x and globally known hash function h – For time slot t, compute priority p as follows: p = h(x  t) • Characteristics of Link layer protocols – Compute this priority for next k time slots for the node itself and all two-hop neighbours – Node can use those time slots for which it has the highest priority • The lower layers in detail t=0 t=1 t=2 t=3 t=4 Example: • Summary Priorities of node A A 23 9 56 3 26 and its two-hop B 64 8 12 44 6 neighbours B and C C 18 6 33 57 2 33 34 Link Layer Protocols Error control • Link Layer protocols cover the following topics • Error control has to ensure that data transport is – Error Control – Error-free  deliver exactly the sent bits/packets • Make sure that the sent bits arrive and no other – In-Sequence  deliver them in the original order  forward and backward error control – Duplicate-free  and at most once – Framing g – Loss free  and at least once Loss-free • Group bit sequence into packets/frames  format, size • Causes: fading, interferences, loss of bit synchronisation – Flow Control – Results in bit errors, packet losses errors • Ensure that a fast sender does not overrun a slower receiver • Mostly occurring in bursts – Link Management – In wireless networks high average bit error rates: 10-2 .. 10-4 • Discovery and management of links to neighbouring nodes • Approaches Goal: Create a reliable communication link – Backward error control: ARQ (Automatic Repeat Request) – Forward error control: FEC (Forward Error Correction) 35 36