EE 565 - Computer Communication Networks - Winter 2008
Project Option II: Minimum Energy Broadcast in Wireless Networks
In this project, we will investigate the problem of energy-efficient broadcast routing in wireless networks. It is a challenging environment because every node operates with limited resources and multihop routing paths are used. The network lifetime is defined as the duration of time until the first node failure due to battery energy exhaustion. In case all the nodes have identical initial energy level, the node that spends the battery power at the highest rate will exhaust its battery first. If we want to extend the lifetime of the network, it is critical to incorporate the residual battery energy into route selection criteria. The purpose of this project is to implement, compare, and improve upon several routing protocols for broadcast routing. As background reading, please read the following papers:
- J. E. Wieselthier, G. D. Nguyen, and A. Ephremides, On the Construction of Energy-Efficient Broadcast and Multicast Trees in Wireless Networks, Proc. IEEE INFOCOM 2000.
- M. Cagalj, J.-P. Hubaux, and C. Enz, Minimum-Energy Broadcast in All-Wireless Networks: NP-Completeness and Distribution Issues, MOBICOM'02, September, 2002, Atlanta, Georgia, USA.
- I. Kang and R. Poovendran, Maximizing Static Network Lifetime of Wireless Broadcast Adhoc Networks, ICC 2003.
- I. Maric and R. D. Yates, Maximum Lifetime of Cooperative Broadcast in Wireless Networks....
For each part of the project, you will be responsible for writing the necessary simulation code (reusing code from previous projects is recommended) and answer the questions asked of you. You may use any reasonable programming language. Prepare a detailed project write-up (ideally 8-12 pages, 15 pages max) containing the following:
- A brief summary of each part of the project,
- Any assumptions you had to make, including parameter values,
- A summary of your results and explanation of any figures, and
- A description of your implementation.
Suppose that 15 nodes with ID i=1,...,15 are arranged in a 1 km2 area. The locations (xi,yi) and initial battery energy Ei(0) are given in the following table.
xi | yi | Ei(0) |
354.8362900534410 | 250.2570844774740 | 5251704.59447224 |
438.4321201555710 | 13.3022272883175 | 6692879.52888797 |
550.0110164077460 | 887.8491649456980 | 1287551.59784981 |
107.5495943295510 | 659.0044584106590 | 4902370.30008543 |
313.3668135835570 | 74.8530069877588 | 2248586.67950461 |
783.3575769932690 | 38.0534740787984 | 4569994.09625906 |
663.8796904087930 | 401.9369380978370 | 1374686.88295816 |
909.5058920451220 | 532.2049212516060 | 2142446.24328069 |
227.2589367950470 | 704.0167380403700 | 5344439.53623574 |
76.7954636944207 | 276.6969336071860 | 3305735.08480975 |
566.6904236004090 | 187.2763895687610 | 7996570.38278599 |
182.7267344665840 | 626.7235170766010 | 7972141.72899902 |
531.4362326765130 | 600.3265425046810 | 3732224.28844496 |
826.2190881929880 | 833.7977352824070 | 7437897.77291161 |
788.3175434671790 | 537.0760668922540 | 6578464.01114772 |
Assume that there is no limit on the maximum transmission power Pmax and the path loss factor α = 2 in this project. Using these assumptions, construct a broadcast routing tree rooted at the source node 1. You are responsible for the following:
- Read the above papers in detail.
- Implement the Minimum Spanning Tree (MST) algorithm (Prim or Kruskal), and generate a final tree in graphic output similar to the figure below. Calculate the total power required to maintain the tree (for purposes of correctness of the rest of the project, this result should be 482113.9406).
- Implement the Broadcast Incremental Power (BIP) algorithm, and generate a final tree in graphic output. Calculate the total power required to maintain the tree (should be 462210.6609).
- Implement the Embedded Wireless Multicast Advantage (EWMA) algorithm, and generate a final tree in graphic output. Calculate the total power to maintain the tree (should be 358388.4894). Note that EWMA requires MST as an initial tree construction stage. In addition, at each stage, print out how the sets C, F and E change over time.
- Compare the performance of three algorithms (MST, BIP, EWMA) in terms of total transmit power. The value from each algorithm should be submitted. Generate 100 random topologies of 15 nodes and calculate the average of total transmit power of each algorithm. Compare with the results in the corresponding reference papers.
- Using the initial battery energy Ei(0) of each node given in the table above and assuming a constant bit rate traffic, compare the performance in terms of static network lifetime. Again, generate 100 random topologies with random initial energy distribution, uniform over the interval [0,3x105], and calculate the average of static network lifetime.
- Implement the DMST algorithm in Ref 3 for the same perameters. Compare the performance to MST, BIP, and EWMA in terms of both total transmit power and network lifetime.
- Implement the cooperative broadcast algorithm in Ref 4 for the same parameters.
- Discuss the advantage and disadvantage of each algorithm when they are used in wireless adhoc network environment.
- Create a table that lists all the performance features that will best summarize your understanding of the algorithms.
- Consider developing a new metric for selecting broadcast routes. What would be the primary consideration of your metric?
- Comment on the scalability of these algorithms and that of your new metric.
- Do you think these algorithms are useful in a realistic setting? In what ways? What needs to be changed to make them applicable? Can you reason about whether or not these algorithms have distributed implementations?