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

• Introduction to Cyber-ethics Issues for ICT Professionals ... Ethical analysis of plagiarism Identify and list as many different forms of plagiarism as possible Select four of the most egregious forms of plagiarism What are the main ethical issues? ... ethics...
• Types of Congressional Committees. Standing Committees. Where all bills are referred. Select Committees. accomplish a particular task. Joint Committees. members of each chamber . Conference Committees. Settles differences between versions of bills. House Rules Committee. makes rules that will govern...
• To Solve Exponential Equations: Rewrite the Equation/Inequality so that the BASES are the same number. If the base is a number, just break it down with a factor tree. If the base is a fraction, FIRST write as a whole...
• Arduous (adj) hard to do, requiring much effort. Synonyms: hard, difficult, laborious, fatiguing. Antonyms: easy, simple, effortless
• The historically accurate flag would have been the Grand Union Flag, officially hoisted by Washington himself on January 2, 1776 at Cambridge, Massachusetts, as the standard of the Continental Army and the first national flag. Artistic concerns motivated further deviations...
• Marketing Management Module 1 Mark Lieberman Foundations of Business Practice 2 Marketing Defined Marketing is a societal process by which individuals and groups obtain what they need and want through creating, offering, and freely exchanging products and services of value...
• The marbled page also has unusual literary significance. As the Sterne Trust puts it, on the preceding page "Sterne tells the reader that the next marbled page is the 'motly emblem of my work'—the page communicating visually that his work...
• Development of Cell Theory 1858- Rudolf Virchow, German physician, after extensive study of cellular pathology, concluded that cells must arise from preexisting cells. The Cell Theory Complete The 3 Basic Components of the Cell Theory were now complete: 1. All...