Maximum Lifetime Routing in Wireless Ad Hoc Networks Riku Jäntti University of Vaasa, Finland
University of Vaasa Department of Computer Science
1
1
Contents • • • • •
System model Maximum life-time routing problem Iterative algorithm Numerical example Conclusions
University of Vaasa Department of Computer Science
2
2
System model •
Parameters – – – –
pmax maximum radiated power φi activity factor of link i (fraction of time the link is used) gij link gain between link i and link j Link i hij normalized link gain • If link j causes interference to link i hij=gij/gii • Otherwise hij=0;
gij
– ηi normalized received noise power ηi=pnoise/gii Link j – Other user interference is treated as noise. – Perfect link adaptation: Mean data rate of the link i achieves Shannon limit: ⎛ ⎞ ⎜ ⎟ 1 ⎟ ri = φiW log 2 ⎜1 + η ⎜ i ⎟ SINR ⎜ ∑ hijφ j + p ⎟ j max ⎠ Signal-to-Interference+Noise ratio ⎝ University of Vaasa Department of Computer Science
3
3
System model •
Multi-path-routing – – – – – –
Data rate of a path: r(p) Data rate between source-and destination pair w: R(w) Set of paths utilized by pair w: P(w) Data rate of source destination pair: R(w)=Σp∈ P(w) r(p) Set of paths utilizing link i: Pi Data rate of a link i: ri=Σp∈ P r(p) rL2=r(1)+r(3) i N3 w=1 : Pair (N1,N5) w=2 : Pair (N2,N5) p=1 : Path {L1,L2,L4} p=2 : Path {L1,L3,L5} p=3 : Path {L2,L4} p=4 : Path {L3,L4}
p=1
p=3
N1
p=4
N5 L3
R(1)=r(1)+r(2) University of Vaasa Department of Computer Science
L4
N2 L1
p=2
L2
L5 N4
4
4
System model • • • •
Nodes are battery operated Power consumption =transmitter power consumption + receiver power consumption + power consumption of the terminal Lifetime=Battery energy / Power consumption Lifetime of a node n: τn =
En
∑φ (P
i∈On
– – – – – – –
En pi Ptx,base Prx,base PCPU On Tn
i
tx ,base
+ pi ) + ∑ φi Prx ,base + PCPU i∈Tn
Energy of the battery used by node n Air interface radiated power in link i Base band power consumption of the transmitter Base band power consumption of the receiver Power consumption of the terminal equipment Set of links originating from node n Set of links terminated by node n
University of Vaasa Department of Computer Science
5
5
Maximum life-time routing problem •
Maximize the operation time of the worst node in the system ⎧⎪ ⎧ 1 ⎫⎫⎪ max r ( p ) {min n {τ n }} = min r ( p ) ⎨max n ⎨ ⎬⎬ { } { }⎪ ⎩τ n ⎭⎪⎭ ⎩ ⎫⎫ ⎞ ⎪⎪ ⎪⎧ ⎪⎧ 1 ⎛ = min r ( p ) ⎨max n ⎨ ⎜ ∑ φi ( Ptx ,base + pi ) + ∑ φi Prx ,base + PCPU ⎟ ⎬⎬ { } i∈Tn ⎠ ⎭⎪⎪⎭ ⎪⎩ ⎩⎪ En ⎝ i∈On
subject to Data rate constraints
∑
r ( p ) ≥ R ( w)
p∈P ( w )
∑r
( p)
p∈Pi
= ri
−1 ⎛ ⎛ ηi ⎞ ⎞ ri = φiW log 2 ⎜1 + ⎜ ∑ hijφ j + ⎟ ⎟ ⎜ ⎝ j pmax ⎠ ⎟ ⎝ ⎠
Transmission time constraints
∑ φ +∑ φ
i∈On
i
i∈Tn
i
≤ δ ≤1
φi ≥ 0
University of Vaasa Department of Computer Science
δ = Edge coloring cost 6
6
Solution procedure •
•
Data rate of a link
⎛ ⎜ 1 ri = φiW log 2 ⎜1 + ηi ⎜ h φ + ∑ ij j ⎜ pmax j ⎝
⎞ ⎟ ⎟ ⎟ ⎟ ⎠
Rate control mapping For fixed rate-to-path allocation {r(p)}, we can solve the time fractions that links need to be used can be solved in each link by iteration.
Fixed transmission power University of Vaasa Department of Computer Science
7
7
Solution procedure •
For sufficiently small R=(r(1) r(2) …)' the mapping
is a contraction (i.e. ||J(R,φ)-J(R,φ')||W∞<||φ-φ'||W∞) – It follows from the mean-value theorem that
– Let J=(Ji) and Z(R)=diag(ζi(R)). It can be shown that there exists nonnegative diagonal weight matrix W such that
University of Vaasa Department of Computer Science
8
8
Solution procedure 1. Start from feasible rate to path allocation R(0)=(r(p)) and time fractions {φi(0)}. 2. Substitute
into the objective function
⎫⎫ ⎞ ⎪⎪ ⎪⎧ ⎪⎧ 1 ⎛ min r ( p ) ⎨max n ⎨ ⎜ ∑ φi ( Ptx ,base + ptx ) + ∑ φi Prx ,base + PCPU ⎟ ⎬⎬ { } i∈Tn ⎠ ⎭⎪⎪⎭ ⎪⎩ ⎩⎪ En ⎝ i∈On and into the time constraints. The resulting optimization problem can be solved e.g. by using linear programming. Denote the optimal solution by R(n+1)=(r(p)) . 3. For a resulting R(n+1) determine new time fractions {φi(n+1)} by using
4. If ||R(n+1)-R(n)||<ε, stop; otherwise goto 2. University of Vaasa The above iteration is a special case of non-linear Gauss-Seidel method, Department of Computer Science and can be shown to converge for the given problem.
9
9
Numerical example (1/4) • System parameters W = 1 MHz Γ = 5 dB
3
Route 1 (w=1)
N 0 = − 174 dBm/Hz Noise density
Route 2 (w=2)
PCPU = 800 mW
4
2 mW ≤ pi ≤ 1000 mW Ptx ,base = 400 mW Prx ,base = 50 mW Ei = E , i ≠ 5 E5 = 0.1E
1
2
5
8
9
6
User data rate: R (1) = R (2) = 30 kbit/s Signalling data rate:
7
R ( signal ) = 1 kbit/s University of Vaasa Department of Computer Science
10
10
Numerical example In all the cases, the algorithm converges solutions that circumvent node 5. E=0.9
1
1
0.9
0.9 0.8 0.7
0.7
Normalized lifetime
Normalized lifetime
0.8
0.6 0.5 0.4
0.6 0.5 0.4 0.3
0.3
0.2
0.2 0.1 -5
0.1 0
5 10 15 20 Maximum transmit power (dBm)
25
0 -5
30
1
1
0.9
0.9
0.8
0.8
0.7
0.7 Normalized lifetime
Normalized lifetime
R{signal}=1 kbit/s
E=0.1
R{signal}=0.1 kbit/s
•
0.6 0.5 0.4 0.3
5 10 15 20 Maximum transmit power (dBm)
25
30
0.6 0.5 0.4 0.3
0.2
0.2
0.1
0.1
University of Vaasa Department of Computer Science 0 -5
0
0
5 10 15 20 Maximum transmit power (dBm)
25
30
0 -5
0
5 10 15 20 Maximum transmit power (dBm)
25
30
11
11
Concluding remarks • Our analysis suggest that if the rate is a linear function of the instantaneous SIR, then the lifetime of the worst node is a non-decreasing function of the maximum air interface power p . • The routing problem can be solved using a simple iterative algorithm. max
– Energy, time, and power can be solved in a distributed fashion for each link separately using a scheme similar to traditional distributed power control – Rate allocation (routing) is based on linear programming and must be solved in centralized fashion.
University of Vaasa Department of Computer Science
12
12
Maximum life-time routing in IEEE802.11b •
Assumptions – Network layer solution (MAC layer is not changed). – Battery state can be measured – Reactive routing where only a single path is utilized at the time
•
Hardware – Laptops: 2 x Toshiba Satellite Model S1800 - 804 – PDAs: 5 x iPAQ Pocket pc Model 3630 – WLAN cards: 7 x Compaq Wireless LAN Version 4.0
•
Software – Linux operation system • • •
Laptops: RedHat 8.0 (Linux Kernel Version:2.4.18-14.9) PDAs: Familiar flavour of Linux for handhelds (Version 0.7.1 Linux Kernel Version: 2.4.18-14.19-rmk6pxa1-hh13) Driver for WLAN: wavlan_cs
– Reference AODV implementation: Erik Nordström, Uppsala University AODV-UU v0.7.2 (http://core.it.uu.se/AdHoc/ImplementationPortal) University of Vaasa Department of Computer Science
13
13
Expected life-time •
Lifetime of a node is estimated as follows
τ=
ETotal φTx PTx + φRx PRx + φIdle PIdle
where
φTx φRx
Transmitted Traffic = Transmitted Bytes/ Data Rate / Time Interval Received Traffic = Receives Bytes/ Data Rate / Time Interval
ETotal
Total energy of the battery
PTx
Transmitter power consumption
PRx
Receiver power consumption
PIdle
Power consumption in idle state
University of Vaasa Department of Computer Science
PIdle = (1 − φTx − φRx ) PIdle,radio + PCPU
14
14
Maximum lifetime routing • • • • • •
• •
Each mobile estimates its life-time based on the traffic volume and battery state. The extension field in route-request RREQ and route reply RREP packets are utilized to carry the life-time (LT) information. LT field is also included into the routing tables. When a RREQ packet is send, LT is set to maximum value (all ones). When an intermediate node receives the RREQ, it compares the LT field of the packet to its own LT. Smallest of the two is set to forwarded RREQ packet. When a node having a path to the destination hears the RREQ packet, it will compare the LT field of the RREQ with the LT field in its routing table and put the smallest of the two into RREP. In case destination hears the RREQ, it will simply send RREP with the lifetime field equal to the LT in the RREQ. All intermediate nodes that hear RREP store the path along with the life time information. In case the source receives several RREPs, it select the path having the largest LT.
University of Vaasa Department of Computer Science
15
15
Maximum lifetime routing RR E P |LT = EP| RR
LT==40
LT=35
EPL RR
0
0
40
== 4
40
LT=120
= LT=
LT==45
T ==
== 4
LT=120
35
RR E P |LT = =40 RR E P |LT = =40
|LT EQ RR
LT=45
LT =
LT=55
=3 5
RR EP |
RREP|LT==35
R R EQ |LT =
|LT EQ RR
RR E Q |LT = =40
LT=40
LT=35
=3 5
RREQ|LT==55
RR EQ LT=55 |L T= ∞
Rejected path
Selected path University of Vaasa Department of Computer Science
16
16
References • • • • • • • • • • •
R. Jäntti and S.-L. Kim, "Joint data rate and power allocation for lifetime maximization in interference limited ad hoc networks," To appear in IEEE Transactions of Wireless Communications, 2005. S. Singh, M. Woo and C. S. Raghavendra, "Power-aware routing in mobile ad hoc networks," in Proc. MOBICOM, 1998. J.-H. Chang and L. Tassiulas, "Maximum lifetime routing in wireless sensor networks," IEEE/ACM Trans. Networking, Vol. 12, No. 4, pp. 609 - 619, 2004. C.-K. Toh, H. Cobb and D. A. Scott, "Performance evaluation of battery-life-aware routing schemes for wireless ad hoc networks," in Proc. IEEE ICC, 2001. S. Banerjee and A. Misra, "Minimum energy paths for reliable communication in multi-hop wireless networks," in Proc. ACM MOBIHOC, 2002. W. Cho and S.-L. Kim, "A fully distributed routing algorithm for maximizing lifetime of a wireless ad hoc network," in Proc. IEEE MWCN, 2002. P. Floreen, P. Kaski, J. Kohonen, and P. Orponen, "Multicast time maximization in energy constrained wireless networks," in Proc. ACM DIALM-POMC, 2003. T. ElBatt and A. Ephremides, "Joint scheduling and power control for wireless ad-hoc networks," IEEE Trans. Wireless Commun., Vol. 3, No. 1, pp. 74-85, 2004. C. Comaniciu and H. V. Poor "QoS Provisioning for Wireless Ad Hoc Networks." in Proc. 42nd IEEE Conference on Decision and Control, Vol. TuA03-4 pp. 92-97, 2003. C. E. Perkins, E. M. Royer and S. Das, "Ad hoc on demand distance vector (AODV) routing," IETF Internet draft, Mobile Ad-hoc Networking Group, IETF, 2001, (work in progress). D. P. Bertsekas and J. N. Tsitsiklis, Distributed Computation: Numerical Methods Athena Scientific, Belmont, Massatussets, 1997.
University of Vaasa Department of Computer Science
17
17