Report

Shi Bai, Weiyi Zhang, Guoliang Xue, Jian Tang, and Chonggang Wang University of Minnesota, AT&T Lab, Arizona State University, Syracuse University, NEC Lab 2012 IEEE INFOCOM 1 1. Introduction 2. Algorithm ◦ 2.1 Definition ◦ 2.2 Problem statement ◦ 2.3 DEAR Algorithm 3. Experiment 4. Conclusion 2 Wireless Sensor Networks ◦ Key Issue: Energy Consumption Delay-bounded Energy-constrained Adaptive Routing (DEAR) Problem ◦ Adaptive reliability Splitting the traffic over multiple paths ◦ Differential delay Increased memory and buffer overflow ◦ Deliverable energy constraints Energy consumption of transmitting packet 3 Def 1. Packet Allocation ◦ P is a set of s-BS paths. ◦ The aggregated packet of link e is the sum of the packet allocations on link e of the paths in P: q(e) = ƩL(p) Def 2. Differential delay ◦ dh => the highest path delay ◦ dl => the lowest path delay ◦ => Dp= dh – dl 4 Def 3. Energy Consumption ◦ Transmitting energy consumption E = w*q q => packet size transmitted on link w => Energy consumption of transmitting 1 bit W=[C*(2^b-1)+F]*(1/b) C => the quality of transmission and noise power F => the power consumption of electronic circuitry Def 4. Latency/Delay ◦ Queuing delay The time waiting at output link for transmission ◦ Transmission delay The amount of time required to push all of the packet bits into the transmission media ◦ Propagation delay The time takes for the head of the signal to travel from the sender to the receiver 5 Transmission delay ◦ Ignored transmission and queuing delay ◦ Without considering the transmission delay Allocate of packets have no impact on delivery of packets Path:p1=(A,B,BS), p2=(A,C,BS), p3=(A,BS) Path delay: d(p1)=2, d(p2)=3, d(p3)=2 Ex a) packet split => p1=10, p3 = 2 Ex b) packet split => p1= 6, p3 = 6 Path delay are the same Differential delay d(p1)-d(p3) = 2 – 2 = 0 6 ◦ Considering the transmission delay Allocations of packets on multiple paths will have impact on path delays Path delay d(p1) = Ʃd(e) + ƩƬ(v) Ex a) d(p1) = 2 + (10 pk/(2 pk/s) + 10/2) = 12, d(p3) = 2 + (2/4) = 2.5 Ex b) d(p1) = 2 +(6/2 + 6/2) = 8, d(p3) = 2 + (6/4) = 3.5 Path delay are different Ex a) Differential delay is 9.5=(12 - 2.5) Ex b) Differential delay is 4.5 7 DEAR(Delay-bounded Energy constrained Adaptive Routing) ◦ Seek set of paths P that can provide the following Delay bounded Energy constrained Adaptive reliability Graph G=(V, E, b, d, w, β) ◦ ◦ ◦ ◦ ◦ ◦ V represents the set of sensor nodes and BS. E represents the set of links. b represents bandwidth d represents the delay of the path p w represents transmission energy consumption β represents the residual energy of sensor v 8 Delay Bounded ◦ Any path p in P must satisfy the differential delay constraint: dmin ≤ d(p) ≤ dmax Energy Constrained ◦ The energy consumption of transmitting packet for each sensor i cannot exceed its residual energy level β(i) Adaptive reliability ◦ The size of aggregated packet of all paths in P is no less than Q : q(P) ≥ Q ◦ Route the data such that any single link failure does no affect more than x% of the total packets 9 Feasible and infeasible solution by Adaptive reliability and delay constraint ◦ Ex c) 2,2,8 In case 8 packet drop => 67% ◦ Ex d) 6,4,2 In case delay is 8 over between 4 and 5 ◦ Ex e) 2,10 In case 10 packet drop => over 70% 10 IDEAR 11 Linear Program solution 12 ODEAR problem ◦ Optimization problem SPDEAR problem ◦ (1+α) approximation algorithm 13 ◦ Each u[t] means that node u can transmit packet at time t. ◦ This bandwidth ensures that the packets sent by u at time i can not exceed b(e). ◦ This ensures that only the packet, which arrive at BS no earlier than dmin and no later than dmax. 14 Requirement Condition ◦ Packet Demand: 12 Packet ◦ Reliability requirement x% = 70% ◦ Delay requirement: dmin = 2 and dmax = 5 Maximum flow by IDEAR ◦ ◦ ◦ ◦ P1=(A[0],B[2],BS[4],BS[5]) P2=(A[0],C[3],BS[5]) P3=(A[0],BS[3],BS[4],BS[5]) P4=(A[0],A[1],BS[4],BS[5]) 15 Fully Polynomial Time Approximation Scheme for SPDEAR ◦ Scaling and rounding technique ◦ dΘ= ⌊d(e)*Θ⌋ + 1 16 Approximation algorithm for ODEAR ◦ dmin ≥ 0 17 Efficient Heuristic for DEAR ◦ Round the propagation delay of each link ◦ dmin and dmax 18 Network topologies in an 100 * 100 sq The power of Sensor node was randomly distributed in [16, 20] Bandwidth, propagation delay and transmission energy consumption of each communication link was randomly distributed in [6,10], [1,5], [1,3] 19 Performance of different number of nodes 20 Performance of different reliability requirements 21 Performance of different packet sizes 22 Transmission delay in multipath routing ◦ The previous work ignored Delay-bounded Energy-constrained Adaptive Routing (DEAR) ◦ Adaptive multipath routing ◦ Energy constraint ◦ Differential delay 23 Thank you. 24