Maximizing Broadcast Tree Lifetime in Wireless Ad Hoc Networks Guofeng Deng, Sandeep Gupta IMPACT Lab, Arizona State University http://impact.asu.edu Broadcast in WANETs Minimum energy broadcast (minimizing total transmission power) NP-hard BIP [Wieselthier Infocom 2000], EWMA [Cagalj Mobicom 2002] Maximum lifetime broadcast (minimizing maximum transmission power) Solvable in polynomial time MST [Camerini IPL 1978][Kang ICC 2003], sub-network solution [Lloyd Mobihoc 2002][Floreen DIALM-POMC 2003] and MDLT [Das Globecom 2003] Consideration of transmission power alone is insufficient. Receiver power matters. CORP: constant receiver power model

TREPT: transmitter-receiver power tradeoff model G. Deng & S. Gupta, Globecom'06 2 IMPACT Arizona State Outline Maximizing Broadcast Tree Lifetime (MaxBTL) Network model CORP model TREPT model Problem statement MaxBTL under the CORP model

An optimal solution MaxBTL under the TREPT model An optimal solution to a special case problem Conclusion G. Deng & S. Gupta, Globecom'06 3 IMPACT Arizona State Maximizing Broadcast Tree Lifetime Network model Power consumption is the sum of transmission and receiving power consumption Transmission power control Wireless multicast advantage (WMA) Receiving power will be discussed shortly Finite battery power capacity and linear battery power model, i.e., the lifetime of a node is the ratio between the amount of battery

energy and power consumption. Problem statement Broadcast tree lifetime: the period of time for the first node to die MaxBTL: find a broadcast tree that maximizes the broadcast tree lifetime among all the broadcast trees rooted at the given source node. G. Deng & S. Gupta, Globecom'06 4 IMPACT Arizona State Receiver Power Models CORP The receiver power, which may vary from node to node, is fixed regardless of the signal strength at the receiver. E.g., paT = 16mW If paR = 5mW, then pa = 21mW

TREPT [Cui ICC 2003][Vasudevan et al. Infocom06] The receiver power for decoding a signal is a function of the transmission power of the transmitter as well as the distance between them. E.g., paR = d3/psT and d = 5m. paR = 10.4mW when psT = 12mW; when psT increases to 20mW, paR reduces to 6.25mW. G. Deng & S. Gupta, Globecom'06 5 IMPACT Arizona State Roadmap Maximizing Broadcast Tree Lifetime (MaxBTL)

Network model CORP model TREPT model Problem statement MaxBTL under the CORP model An optimal solution MaxBTL under the TREPT model An optimal solution to a special case problem Conclusion G. Deng & S. Gupta, Globecom'06 6 IMPACT Arizona State MaxBTL under the CORP model Define longevity of a transmitter-receiver pair as:

Eu Ev l u, v min , R R p u, v pu pv Lemma 1: The lifetime of any broadcast tree T is the minimum longevity of any transmitter-receiver pair in T. Lemma 2: Given a node v in a link weighted digraph, the spanning tree rooted at v generated using Prims algorithm minimizes the maximum link weight among all spanning trees rooted at the same node. WANET Inverse longevity graph (ING) Theorem 1: A rooted spanning tree generated by Prims algorithm in an ING is the maximum lifetime broadcast tree. Lemma 2 ING Lemma 1

Prim tree min max weight min max inverse longevity max min longevity max tree lifetime G. Deng & S. Gupta, Globecom'06 7 IMPACT Arizona State Roadmap Maximizing Broadcast Tree Lifetime (MaxBTL) Network model CORP model TREPT model Problem statement MaxBTL under the CORP model

An optimal solution MaxBTL under the TREPT model An optimal solution to a special case problem Conclusion G. Deng & S. Gupta, Globecom'06 8 IMPACT Arizona State MaxBTL under the TREPT model Given a broadcast tree, what is the maximum lifetime? Power setting of a broadcast tree is a snapshot of transmission and receiving power of each node. Given a tentative tree lifetime, we can check if there is any valid power setting that satisfies connectivity constraints, i.e., if the given lifetime is feasible. For example, for a tentative lifetime

s: ps = psT = Es / , s is OK only if ps p(s,a). a: paR = f(psT,d), paT = Ea / paR , a is OK only if paT max{p(a,c),p(a,b)}. G. Deng & S. Gupta, Globecom'06 9 IMPACT Arizona State MaxBTL under the TREPT model Theorem 2: Under the TREPT model, the binary search algorithm returns the lifetime of any given broadcast tree within of the optimal lifetime in O(n log(T/)) time, where n is the number of nodes in the WANET and T is an upper bound lifetime. We suspect that the general problem of finding a maximum lifetime broadcast tree under the TREPT model is NP-hard. G. Deng & S. Gupta, Globecom'06

10 IMPACT Arizona State Roadmap Maximizing Broadcast Tree Lifetime (MaxBTL) Network model CORP model TREPT model Problem statement MaxBTL under the CORP model An optimal solution MaxBTL under the TREPT model

An optimal solution to a special case problem Conclusion G. Deng & S. Gupta, Globecom'06 11 IMPACT Arizona State Conclusion Receiver power matters An optimal solution to MaxBTL under the CORP model An optimal solution to a special case problem of MaxBTL under the TREPT model Future directions include a solution to the general MaxBTL problem under the TREPT model or proving it to be NP-hard, and distributed solutions to MaxBTL. G. Deng & S. Gupta, Globecom'06

12 IMPACT Arizona State Thank You! G. Deng & S. Gupta, Globecom'06 13 IMPACT Arizona State

## Recently Viewed Presentations

• HAP (112 g) PAL. Special Permits. De Minimis. Minor NSR* Flexible. PSD, GHG PSD. Nonattainment. HAP (112 g) PAL. Special Permits. De Minimis* Minor indicates State-issued permit rather than Federal (Major) Permit. Title V major sites should use the PI-1...
• Mandatory Government sources (8.002) Services on the Procurement List (AbilityOne) Use of Other Sources (8.004) Federal Supply Schedules, Governmentwide acquisition contracts, multi-agency contracts, Federal Strategic Sourcing Initiative (FSSI) agreements, Federal Prison Industries, Inc. or any other procurement instruments intended for...
• Genesis of Project. House Bill 61. Passed in 2017. Allows for the creation of a Statewide Plan that needs to address: Setting of Priorities for the Montana 9-1-1 System
• a function name can be passed as an argument. think a function name as a pointer (like an array) (*f)(x) f is a pointer to a function *f is a function (*f)(x) is a call to the function. if you...
• noc 30. dubna. filipojakubská noc. Valpuržina noc. Valpurga: anglická světice z 8. st. mimo jiné patronka proti vzteklině a za bouřky. V ČR nese rodné jméno Valpurga 5 lidí, věkový průměr je 64 let včetně osoby narozené roku 2008.
• EQUILIBRIUM OF RIGID BODIES IN TWO DIMENSIONS When a rigid body is in equilibrium, both the resultant force and the resultant couple must be zero. Forces and moments acting on a rigid body could be external forces/moments or internal forces/moments.
• NMC mentor domain: Establish effective working relationships. Demonstrate effective relationship building skills sufficient to support learning, as part of a wider inter-professional team, for a range of students in both practice and academic learning environments.
• The Replication Test framework idea is taken from Mysql code base. The Mysql replication framework has all the advantages of syncing/stopping/resuming the logs with master. With this framework, user can control internals of the replication process.