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 < MiEiPiiEEiPimin8Modified 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