Maximum

Maximum Lifetime Routing in Wireless Ad Hoc Networks Riku Jäntti University of Vaasa, Finland University of Vaasa Depar...

0 downloads 243 Views 112KB Size
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