DOC PREVIEW
UCLA CS 215 - WR2

This preview shows page 1-2-20-21 out of 21 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Min Power Routing in Wireless NetworksOutlineIntroductionPrevious WorkExisting ProblemRadio ModelProblem FormulationModified Bellman-Ford AlgorithmSlide 9Slide 10Simulation SettingsSlide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Conclusion1Min Power Routing in Wireless NetworksHai Jiang and Zhijun HuangMarch 22, 2001CS215 Project Report:2Outline•Introduction•Previous Work•Problem Formulation•Modified Bellman-Ford Algorithm•Simulation Results•Conclusion3Introduction•Why Min Power in Wireless Network? 1. Limited Energy : Battery Operated Network 2. Interference Reduction and Spectrum Reuse •How to minimize power consumption? 1. Physical Level: Low-power CPU/Display High-capacity Battery => Little Room for further reduction 2. Higher Level: Power-aware protocols MAC Layer Network Layer * …4Previous Work•Singh and Raghavendra (98) 1/Eremain : reflect node’s reluctance to forward packets Non-localized Dijkstra’s Algorithm: Shortest Weighted Path•Rodoplu and Meng (98) Power consumption: u(d)= d4  2 108 Non-localized Bellman-Ford Algorithm: Shortest Path•Gomez etc (99) Power cost function: Pi * f(Bi) •Heizelman and Chandrakasan (00) Radio Model: Etx (k, d) = Eelec * k + Eamp * k * d2 Hierarchical Clustering5Existing Problem•Network with minhop algorithm Critical Node, N6, expends power faster => die first Problem: how to balance power consumption? •How to consider hop-count constraint? 102345606Radio Model •Transceiver/Receiver CircuityEelec = 50nJ/bit •Transmit Amplifier Eamp = 100pJ/bit/m2•Transmit Etx (k, d) = Eelec * k + Eamp * k * d2 •Receive Erx (k) = Eelec * k7Problem Formulation•Each Node : Remaining Energy EiEach Edge : Transmission Energy Pi •Object: For each path, Min such that, Ei > Emin and Hop-count < M=> Min , such that Hop-count < MiEiPiiEEiPimin8Modified Bellman-Ford AlgorithmB e l l m a n - F o r d1 . I n i t i a l i z e ( G , s )2 . f o r i = 1 t o V [ G ] - 13 . d o f o r e a c h e d g e ( u , v ) i n E [ G ]4 . d o i f d [ v ] > d [ u ] + w ( u , v )5 . t h e n d [ v ] = d [ u ] + w ( u , v )6 . P [ v ] = u7 . r e t u r n T R U EB e l l m a n - F o r d w / m a x h o p c o n s t r a i n t1 . I n i t i a l i z e ( G , s )2 . f o r i = 1 t o V [ G ] - 13 . d o f o r e a c h e d g e ( u , v ) i n E [ G ]4 . d o f o r e a c h e n t r y k i n n o d e v5 . i f d [ v , k ] > d [ u , k - 1 ] + w ( u , v )6 . t h e n d [ v , k ] = d [ u , k - 1 ] + w ( u , v )7 . P [ v ] = u8 . r e t u r n T R U E9Modified Bellman-Ford Algorithmh o p # f r o ms o u r c ep o w e rc o s tp a r e n tn o d e0123. . .. . .. . .M - 4M - 1M - 2M - 3i n f i n i t y 4i n f i n i t yi n f i n i t yi n f i n i t yi n f i n i t yi n f i n i t yi n f i n i t yi n f i n i t y012 13M - 4M - 3M - 2M - 1h o p # f r o ms o u r c ep o w e rc o s tp a r e n tn o d e0123. . .. . .. . .M - 4M - 1M - 2M - 3i n f i n i t yi n f i n i t yi n f i n i t yi n f i n i t y 1i n f i n i t yi n f i n i t yi n f i n i t yi n f i n i t y01 023M - 4M - 3M - 2M - 1n o d e 1 n o d e 2W1 2 = 3n o d e 0s r cW0 1 = 1W1 2 = 3n o d e 3n o d e 4n o d e 52467381 043510h o p # f r o ms o u r c ep o w e rc o s tp a r e n tn o d e0123. . .. . .. . .M - 4M - 1M - 2M - 3i n f i n i t y 4i n f i n i t yi n f i n i t yi n f i n i t yi n f i n i t yi n f i n i t yi n f i n i t yi n f i n i t y012 13M - 4M - 3M - 2M - 1h o p # f r o ms o u r c ep o w e rc o s tp a r e n tn o d e0123. . .. . .. . .M - 4M - 1M - 2M - 3i n f i n i t yi n f i n i t yi n f i n i t yi n f i n i t y 1i n f i n i t yi n f i n i t yi n f i n i t yi n f i n i t y01 023M - 4M - 3M - 2M - 1n o d e 1 n o d e 2W1 2 = 3W1 2 = 3w2 1 = 411Simulation Settings•Method Simulator : written in C; Algorithms: Min-hop Min-power w/ Hop Constraint Min-power w/o Hop Constraint•Parameters RadioRange : 100 m Network Size : 600 m x 600 m Node Number : 100 - 200 Max Hop : 5, 10, 20, No Constraint Time Steps : 2000 rounds12Min-power prolongs network lifetime!Number of Alive Nodes (Total 100 Nodes)60657075808590951000 500 1000 1500Time Step (Rounds)Alive Nodesminhoppower_5hpower_10hpower_20hpower13Number of Alive Nodes (Total 200 Nodes)1001201401601802000 500 1000 1500Time Step (round)Alive Nodespower_5hpower_10hpower_20hpowerminhopNetwork Density increase => Min-power is more effective14Critical nodes in Minhop die fast => Minhop is the worst ! Successful Connections every 20 rounds (total 100 nodes)05010015020020 420 820 1220 1620Time Step (rounds)#Connectionspower_5hpower_10hpower_20hpowerminhop15Network Density increase => Min-power is more effectiveSuccessful Connections every 20 rounds (total 200 nodes)05010015020020 420 820 1220 1620Time Step (rounds)#Connectionspower_5hpower_10hpower_20hpowerminhop16Original NetworkMinhop: 200_Node Network(Time = 0)01002003004005006000 100 200 300 400 500 600XY17Minhop v.s. Minpower at Time = 1000Minpower: 200-Node Network (Time = 1000)200 Alive Nodes01002003004005006000 100 200 300 400 500 600XYMinhop: 200-Node Network(Time=1000)148 Alive Nodes01002003004005006000 100 200 300 400 500 600XY18Minhop v.s. Minpower at Time …


View Full Document

UCLA CS 215 - WR2

Download WR2
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view WR2 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view WR2 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?